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

Modern LLM agents are increasingly tasked with 'high-entropy queries' (HEQs)—open-ended requests that require searching vast, fragmented information spaces. Current evaluation methods for these tasks, such as GAIA or WideSearch, rely on manually curated answer sets. This creates an 'evaluation paradox': because exhaustive ground truth is impossible to obtain for these tasks, benchmarks often penalize agents for discovering valid items that were omitted by human annotators, while rewarding those that simply replicate human blind spots. Consequently, performance metrics are bounded by the quality of the annotation rather than the agent's actual search capability.

To resolve this, the authors propose VERITAS (Verifiable Traversal Assessment for Search). Instead of relying on subjective human labels, VERITAS reformulates search tasks using cryptographic hash constraints. By requiring agents to find items whose identifiers satisfy a specific, non-optimizable hash (e.g., MD5), the framework forces the agent to perform a genuine, exhaustive traversal of the search space. Because the hash constraint is 'semantically null'—meaning it provides no information to a search engine—the agent cannot use shortcuts. It must systematically enumerate candidates and verify each one locally, effectively turning the search task into a computationally pure, verifiable challenge.

VERITAS provides a principled way to control task difficulty by manipulating the search space size (N) and the number of target items (k). The authors demonstrate that the probability of success for a budget-constrained agent scales inversely with the search space, following a predictable statistical distribution. The framework implements four tiers of difficulty:

• Easy: Single-source enumeration (e.g., searching one author's repository).
• Medium: Composite search across seven independent sources.
• Hard: Deep attribute extraction requiring the agent to visit items to retrieve hidden data before hashing.
• Extra Hard: Nested multi-task hierarchies that combine deep extraction with complex synthesis.

This structure allows researchers to isolate and measure an agent's systematic exploration discipline, independent of the brittle requirements of traditional, partially-labeled benchmarks.