Search papers, labs, and topics across Lattice.
This paper addresses the evaluation paradox in large language models (LLMs) by introducing VERITAS, a framework that constructs computationally irreducible constraints for high-entropy search tasks. By shifting the evaluation paradigm from incomplete human-annotated datasets to verifiable sparse-answer tasks, the authors enable a more accurate assessment of LLMs' exhaustive search capabilities. The key finding is that VERITAS allows for the generation of an infinite number of test cases with perfect ground truth, facilitating robust evaluation and training for systematic exploration under uncertainty.
High-entropy search tasks can now be evaluated without the constraints of incomplete ground truth, thanks to a novel framework that ensures LLMs genuinely traverse entire search spaces.
Evaluating the exhaustive search capabilities of large language models (LLMs) is plagued by a fundamental paradox: verifying completeness requires complete ground truth, yet high-entropy 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, LLM-based 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.
