Lune

ACL Findings2026

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

Juntao Wu, Wei Wen, Xianting Huang, Shuai Pang, Ruizhi Qiao, Xing Sun, Ke Wang

Abstract

Evaluating the exhaustive search capabilities of large language models (LLMs) is plagued by a fundamental paradox: verifying completeness requires complete ground truth, yet highentropy enumeration tasks make such ground truth impossible for humans to create. This causes benchmarks to systematically penalize models for outperforming their human annotators. Despite rapid progress in web-search and deep research agents-which now issue hundreds of queries, traverse diverse sites, and synthesize long reports-evaluation still largely relies on partially annotated answer sets, LLMbased judges, or single-answer questions that avoid genuinely exhaustive search scenarios.

We break this paradox by shifting the evaluation paradigm from simulating a messy reality to constructing computationally pure challenges. We introduce VERITAS (Verifiable Traversal Assessment for Search), a framework built on the principle of computationally irreducible constraints. By introducing novel, non-optimizable constraints, we create verifiable, sparse-answer search tasks that are computationally equivalent to exhaustive enumeration. These constraints are easy to verify but impossible for LLMs or search engines to optimize, forcing agents to genuinely traverse the entire search space. VERITAS can automatically generate a virtually infinite number of test cases with perfect ground truth and precise difficulty control, with marginal instance cost dominated by hash computations. This provides not only a robust benchmark for evaluating systematic exploration under uncertainty but also a scalable method for generating training data to improve these crucial, yet underdeveloped, capabilities.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • WebThinker: Empowering Large Reasoning Models with Deep Research Capability cites GAIA: a benchmark for General AI Assistants
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on7

  1. WebArena: A Realistic Web Environment for Building Autonomous AgentsShuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou et al.ICLR 2024 · 1,197 citations
  2. AgentBench: Evaluating LLMs as AgentsXiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu et al.ICLR 2024 · 748 citations
  3. GAIA: a benchmark for General AI AssistantsGrégoire Mialon, Clémentine Fourrier, Thomas Wolf, Yann LeCun et al.ICLR 2024 · 716 citations
  4. WebThinker: Empowering Large Reasoning Models with Deep Research CapabilityXiaoxi Li, Jiajie Jin, Guanting Dong, Hongjin Qian et al.NeurIPS 2025 · 354 citations
  5. Measuring and Narrowing the Compositionality Gap in Language ModelsOfir Press, Muru Zhang, Sewon Min, Ludwig Schmidt et al.EMNLP Findings 2023 · 296 citations

Related papers

  1. Open Data Synthesis for Deep ResearchZiyi Xia, Kun Luo, Hongjin Qian, Siqi Bao et al.ICLR 2026 · 14 citations
  2. VCSearch: Bridging the Gap Between Well-Defined and Ill-Defined Problems in Mathematical ReasoningShi-Yu Tian, Zhi Zhou, Kun-Yang Yu, Ming Yang et al.EMNLP 2025
  3. LongWeave: A Long-Form Generation Benchmark Bridging Real-World Relevance and VerifiabilityZikai Xiao, Fei Huang, Jianhong Tu, Jianhui Wei et al.EMNLP Findings 2025 · 1 citation
  4. UHGEval: Benchmarking the Hallucination of Chinese Large Language Models via Unconstrained GenerationXun Liang, Shichao Song, Simin Niu, Zhiyu Li et al.ACL 2024 · 15 citations
  5. Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial OptimizationXia Jiang, Jing Chen, Cong Zhang, Jie Gao et al.ACL Findings 2026
Dusk over the sea between two cliffs drawn in fine vertical lines