Elamur Research⌕
☰
home / papers / 2026 / Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints

Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints

Paper · 2026 · Juntao Wu, Wei Wen, Xianting Huang et al.

Summary

Benchmarks for search agents that must enumerate large, open-ended answer sets face a paradox. Judging completeness needs a full ground truth, but humans cannot reliably build one for such high-entropy queries. As a result, agents that find valid items missing from the annotated pool get marked as hallucinating.

The authors propose VERITAS (Verifiable Traversal Assessment for Search). Instead of asking agents to list everything, it asks for the single item in a real web domain whose identifier matches a cryptographic hash, for example the MD5 of a song title. Because a hash gives no semantic signal that search engines or LLMs could exploit, the agent must still gather and check essentially every candidate. The authors argue this makes the task computationally equivalent to exhaustive enumeration, while the answer stays trivially checkable.

The framework generates unlimited instances with exact labels and adjustable difficulty, at a cost mostly limited to hashing. Experiments show that even frontier agents struggle as the search space grows. VERITAS therefore provides a sharp stress test of exhaustive search and a possible source of training data.

Key points

  • Evaluation design: tasks come in Medium, Hard and Extra Hard tiers and are scored with Pass@4 and Avg@4. No human annotation or LLM judge is needed.
  • Frontier models: GPT-5 falls from 47.5% on Medium to 20.0% on Extra Hard, and Gemini-3-Pro falls from 36.7% on Hard to 6.7% on Extra Hard.
  • Other models: seven other models score only 2.5–17.9% on Medium and 2.4–14.3% on Hard. GPT-4o and Kimi-K2 reach 0% on Extra Hard.
  • Effort versus outcome: agents work hard but still fail. GLM-4 averages 31.3 tool calls per query, Kimi-K2 28.5 and DeepSeek-v3.1 21.9, yet these models stay below 12% success. VERITAS also triggers 1.4×–4.2× more tool calls than WideSearch.
  • Limitation: VERITAS has so far been used only for evaluation. Using its generated data for RL or other post-training is left for future work.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢TencentShenzhen · China134 works · 19,743 citations🎓Chinese University of Hong KongHong Kong · China126 works · 14,073 citations🎓Jinan UniversityGuangzhou · China5 works · 11 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 works

🧭 Topics 1Research subjects and languages the work is about.Evaluation & benchmarks · 1,220 works

Cite

Cite as Juntao Wu, Wei Wen, Xianting Huang, Shuai Pang, Ruizhi Qiao, Xing Sun and Ke Wang. 2026. Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1406

@inproceedings{wu2026breaking,
  title = {{Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints}},
  author = {Juntao Wu, Wei Wen, Xianting Huang, Shuai Pang, Ruizhi Qiao, Xing Sun and Ke Wang},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1406},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1406}
}

References

20 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. arXiv preprint arXiv:2011.01060.
  2. Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Sercan Arik, Dong Wang, Hamed Zamani, and Jiawei Han. 2025. Search-r1: Training llms to reason and leverage search engines with reinforcement learning. arXiv preprint arXiv:2503.09516.
  3. Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. 2017. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint arXiv:1705.03551.
  4. Kimi. 2025. Kimi deep research. find
  5. Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, and 1 others. 2019. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Lin…
  6. Tian Lan, Bin Zhu, Qianghuai Jia, Junyang Ren, Haijun Li, Longyue Wang, Zhao Xu, Weihua Luo, and Kaifu Zhang. 2025. Deepwidesearch: Benchmarking depth and width in agentic information seeking. arXiv preprint arXiv:2510.20168. — [arXiv:2510.20168](https://arxiv.org/abs/2510.20168) find
  7. Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. 2022. Measuring and narrowing the compositionality gap in language models. arXiv preprint arXiv:2210.03350. find
  8. Huatong Song, Jinhao Jiang, Yingqian Min, Jie Chen, Zhipeng Chen, Wayne Xin Zhao, Lei Fang, and Ji-Rong Wen. 2025. R1-searcher: Incentivizing the search capability in llms via reinforcement learning. arXiv preprint arXiv:2503.05592.
  9. Zhengwei Tao, Jialong Wu, Wenbiao Yin, Junkai Zhang, Baixuan Li, Haiyang Shen, Kuan Li, Liwen Zhang, Xinyu Wang, Yong Jiang, and 1 others. Webshaper: Agentically data synthesizing via information-seeking formalization, 2025. URL https://arxiv.org/abs/2507.15061. — [arXiv:2507.15061](https://arxiv.org/abs/2507.15061) ↗
  10. Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022. Musique: Multi-hop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539–554. find
  11. Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, and 1 others. 2024. A survey on large language model based autonomous agents. Frontiers of Computer Science, 18(6):186345.
  12. J Wei, Z Sun, S Papay, S McKinney, J Han, I Fulford, HW Chung, AT Passos, W Fedus, and A Glaese. Browsecomp: A simple yet challenging benchmark for browsing agents, 2025a. URL https://arxiv.org/abs/2504.12516. ↗
  13. Jason Wei, Zhiqing Sun, Spencer Papay, Scott McKinney, Jeffrey Han, Isa Fulford, Hyung Won Chung, Alex Tachard Passos, William Fedus, and Amelia Glaese. 2025. Browsecomp: A simple yet challenging benchmark for browsing agents. arXiv preprint arXiv:2504.12516. find
  14. Ryan Wong, Jiawei Wang, Junjie Zhao, Li Chen, Yan Gao, Long Zhang, Xuan Zhou, Zuo Wang, Kai Xiang, Ge Zhang, and 1 others. 2025. Widesearch: Benchmarking agentic broad info-seeking. arXiv preprint arXiv:2508.07999.
  15. Jialong Wu, Baixuan Li, Runnan Fang, Wenbiao Yin, Liwen Zhang, Zhengwei Tao, Dingchu Zhang, Zekun Xi, Gang Fu, Yong Jiang, and 1 others. 2025. Webdancer: Towards autonomous information seeking agency. arXiv preprint arXiv:2505.22648. x.ai. 2025. Grok 3 beta — the age of reasoning agents.
  16. Yunjia Xi, Jianghao Lin, Yongzhao Xiao, Zheli Zhou, Rong Shan, Te Gao, Jiachen Zhu, Weiwen Liu, Yong Yu, and Weinan Zhang. 2025. A survey of llm-based deep search agents: Paradigm, optimization, evaluation, and challenges. arXiv preprint arXiv:2508.05668. — [arXiv:2508.05668](https://arxiv.org/abs/2508.05668) find
  17. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv:1809.09600.
  18. Weizhi Zhang, Yangning Li, Yuanchen Bei, Junyu Luo, Guancheng Wan, Liangwei Yang, Chenxuan Xie, Yuyao Yang, Wei-Chieh Huang, Chunyu Miao, Henry Peng Zou, Xiao Luo, Yusheng Zhao, Yankai Chen, Chunkit Chan, Peilin Zhou, Xinyang Zhang, Chenwei Zhang, Jingbo Shang, and 4 others. 2025. From web search to… — [arXiv:2506.18959](https://arxiv.org/abs/2506.18959) find
  19. Peilin Zhou, Bruce Leon, Xiang Ying, Can Zhang, Yifan Shao, Qichen Ye, Dading Chong, Zhiling Jin, Chenxuan Xie, Meng Cao, and 1 others. 2025. Browsecomp-zh: Benchmarking web browsing ability of large language models in chinese. arXiv preprint arXiv:2504.19314. — [arXiv:2504.19314](https://arxiv.org/abs/2504.19314) find
  20. Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, and 1 others. 2023. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307.13854.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wu-2026-breaking-evaluation-paradox-evaluating-high/