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

• URL: http://arxiv.org/abs/2606.22783v1
• Date: Mon, 22 Jun 2026 02:45:01 GMT
• Title: Breaking the Evaluation Paradox: Evaluating High-Entropy Search with Computationally Irreducible Constraints
• Abstract summary: evaluating the exhaustive search capabilities of large language models is plagued by a paradox.<n> verifying completeness requires complete ground truth, yet high-entropy enumeration tasks make such ground truth impossible for humans to create.<n>We introduce VERITAS, a framework built on the principle of computationally irreducible constraints.
• Score: 24.33065543278173
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Tool-Adaptive LLM Reranker [6.360159778061184]
  TALRanker is a novel framework that formalizes pointwise relevance scoring as an agentic Markov decision process.<n>It achieves state-of-the-art performance across standard and reasoning-intensive retrieval benchmarks.
  arXiv  Detail & Related papers  (2026-07-12T04:04:59Z)
• Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints [0.6524460254566904]
  We systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity.<n>We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube.<n>We observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs.
  arXiv  Detail & Related papers  (2026-04-15T00:35:22Z)
• Not All Queries Need Deep Thought: CoFiCot for Adaptive Coarse-to-fine Stateful Refinement [24.721024438862553]
  CoFiCot is a coarse-to-fine adaptive framework that tailors inference strategies to problem difficulty.<n>We implement a multi-metric classifier that triages queries by semantic entropy, consensus reliability, and predicted reasoning depth.<n>This enables a differentiated refinement stage that applies efficient aggregation for simple queries while routing complex ones to a context-aware correction loop.
  arXiv  Detail & Related papers  (2026-03-09T11:23:07Z)
• HotelQuEST: Balancing Quality and Efficiency in Agentic Search [6.1626572270420334]
  Agentic search has emerged as a promising paradigm for adaptive retrieval systems powered by large language models (LLMs)<n>We introduce HotelQuEST, a benchmark comprising 214 hotel search queries that range from simple factual requests to complex queries.<n>We find that LLM-based agents achieve higher accuracy than traditional retrievers, but at substantially higher costs due to redundant tool calls and suboptimal routing.
  arXiv  Detail & Related papers  (2026-02-27T11:50:57Z)
• RE-Searcher: Robust Agentic Search with Goal-oriented Planning and Self-reflection [55.125987985864896]
  We present a systematic analysis that quantifies how environmental complexity induces fragile search behaviors.<n>We propose a simple yet effective approach to instantiate a search agent, RE-Searcher.<n>This combination of goal-oriented planning and self-reflection enables RE-Searcher to resist spurious cues in complex search environments.
  arXiv  Detail & Related papers  (2025-09-30T10:25:27Z)
• seqBench: A Tunable Benchmark to Quantify Sequential Reasoning Limits of LLMs [1.0519693622157462]
  We introduce seqBench, a benchmark for probing sequential reasoning limits in Large Language Models (LLMs)<n>We find that even top-performing models systematically fail on seqBench's structured reasoning tasks despite minimal search complexity.
  arXiv  Detail & Related papers  (2025-09-21T01:32:13Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• The Ability of Large Language Models to Evaluate Constraint-satisfaction in Agent Responses to Open-ended Requests [0.6249768559720121]
  We develop and release a novel Arithmetic Constraint-Satisfaction (ACS) benchmarking dataset. This dataset consists of complex user requests with corresponding constraints, agent responses and human labels indicating each constraint's satisfaction level in the response. We show that most models still have a significant headroom for improvement, and that errors primarily stem from reasoning issues.
  arXiv  Detail & Related papers  (2024-09-22T09:27:42Z)
• Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models [56.32800938317095]
  Existing verifiers are sub-optimal for tree search techniques at test time.<n>We propose token-supervised value models (TVMs)<n>TVMs assign each token a probability that reflects the likelihood of reaching the correct final answer.
  arXiv  Detail & Related papers  (2024-07-12T13:16:50Z)
• Shortcomings of Question Answering Based Factuality Frameworks for Error Localization [51.01957350348377]
  We show that question answering (QA)-based factuality metrics fail to correctly identify error spans in generated summaries. Our analysis reveals a major reason for such poor localization: questions generated by the QG module often inherit errors from non-factual summaries which are then propagated further into downstream modules. Our experiments conclusively show that there exist fundamental issues with localization using the QA framework which cannot be fixed solely by stronger QA and QG models.
  arXiv  Detail & Related papers  (2022-10-13T05:23:38Z)
• Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity [51.476337785345436]
  We study a pessimistic variant of Q-learning in the context of finite-horizon Markov decision processes. A variance-reduced pessimistic Q-learning algorithm is proposed to achieve near-optimal sample complexity.
  arXiv  Detail & Related papers  (2022-02-28T15:39:36Z)
• Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
  Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
  arXiv  Detail & Related papers  (2021-10-21T07:28:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.