When Independent Sampling Outperforms Agentic Reasoning

• URL: http://arxiv.org/abs/2605.08478v1
• Date: Fri, 08 May 2026 20:53:51 GMT
• Title: When Independent Sampling Outperforms Agentic Reasoning
• Abstract summary: We study how to allocate inference-time compute for competitive programming under fixed budgets.<n>We compare agent-based reasoning with repeated independent sampling (k-shot) as a function of both cost and number of model calls.
• Score: 4.226475360842309
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study how to allocate inference-time compute for competitive programming under fixed budgets. Evaluating 216 Codeforces problems across Divisions 1-3, we compare agent-based reasoning with repeated independent sampling (k-shot) as a function of both cost and number of model calls. Across models and difficulty levels, k-shot consistently achieves a better accuracy-cost and accuracy-query tradeoff. This gap persists despite prompt caching in agent frameworks, indicating lower per-call effectiveness. Our results show that, for self-contained algorithmic tasks, independent exploration can outperform deeper agentic reasoning under realistic resource constraints. We also provide a budget-allocation analysis when the inference budget is fixed, and prove that a cost-optimal solver minimizes the principled metric log failure likelihood per dollar.

Related papers

• Variable Selection for Feature-Based Newsvendor [1.9851118379257533]
  Feature-based newsvendor models balance holding and shortage costs under demand uncertainty.<n>High-dimensional feature sets often hinder interpretability and inflate data collection and implementation costs.<n>This paper studies variable selection for the feature-based newsvendor problem under a hard cardinality constraint on the number of selected features.
  arXiv  Detail & Related papers  (2026-09-01T17:10:24Z)
• Inference-Time Budget Control for LLM Search Agents [21.14983754890843]
  We study the problem in multi-hop question answering (QA) and formulate it as two-stage inference-time budget control.<n>At search time, our controller assigns each feasible action a task-level Value-of-Information (VOI) score.<n>After search, a selective evidence-grounded finalizer compares the trajectory answer with a refined candidate and rewrites only when the residual error appears to be a low-risk answer-form error.
  arXiv  Detail & Related papers  (2026-05-07T05:45:58Z)
• Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs [1.7499351967216341]
  Budget-Adaptive Curriculum Reasoning (BCAE) is a unified framework that jointly optimize reasoning quality and token efficiency.<n>BCAE includes a emphbudget-conditioned unified policy, a emphcurriculum-aware budget scheduler, and a emphtruncation-aware dense reward mechanism.
  arXiv  Detail & Related papers  (2026-03-29T18:31:09Z)
• Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents [40.18150559561834]
  Budget-Aware Value Tree (BAVT) is a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree.<n>BAVT consistently outperforms parallel sampling baselines.
  arXiv  Detail & Related papers  (2026-03-13T04:10:27Z)
• ODAR: Principled Adaptive Routing for LLM Reasoning via Active Inference [60.958331943869126]
  ODAR-Expert is an adaptive routing framework that optimize the accuracy-efficiency trade-off via principled resource allocation.<n>We show strong and consistent gains, including 98.2% accuracy on MATH and 54.8% on Humanity's Last Exam.
  arXiv  Detail & Related papers  (2026-02-27T05:22:01Z)
• Conformal Thinking: Risk Control for Reasoning on a Compute Budget [60.65072883773352]
  Reasoning Large Language Models (LLMs) enable test-time scaling, with dataset-level accuracy improving as the token budget increases.<n>We re-frame the budget setting problem as risk control, limiting the error rate while minimizing compute.<n>Our framework introduces an upper threshold that stops reasoning when the model is confident and a novel lower threshold that preemptively stops unsolvable instances.
  arXiv  Detail & Related papers  (2026-02-03T18:17:22Z)
• Labels or Preferences? Budget-Constrained Learning with Human Judgments over AI-Generated Outputs [17.028710603629026]
  We show how to optimally allocate a fixed annotation budget between ground-truth labels and pairwise preferences in AI.<n>We introduce Preference-Calibrated Active Learning (PCAL), a novel robustness method that learns optimal data acquisition strategy.<n>This work provides a principled and statistically efficient approach for budget-constrained learning in modern AI.
  arXiv  Detail & Related papers  (2026-01-19T23:23:29Z)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• Distributionally Robust Optimization with Adversarial Data Contamination [49.89480853499918]
  We focus on optimizing Wasserstein-1 DRO objectives for generalized linear models with convex Lipschitz loss functions.<n>Our primary contribution lies in a novel modeling framework that integrates robustness against training data contamination with robustness against distributional shifts.<n>This work establishes the first rigorous guarantees, supported by efficient computation, for learning under the dual challenges of data contamination and distributional shifts.
  arXiv  Detail & Related papers  (2025-07-14T18:34:10Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Frugal inference for control [2.20480252274709]
  Key challenge in advancing artificial intelligence is achieving the right balance between external movement and resource use.<n>We develop a version of the POMDP framework where the information gained through inference is treated as a resource that must be optimized alongside task performance and motion effort.<n>This work provides a foundation for a new type of rational computation that both brains and machines could use for effective but resource-efficient control under uncertainty.
  arXiv  Detail & Related papers  (2024-06-20T15:50:38Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  We introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of Large Language Model (LLM) We propose a decoding algorithm integrating the self-evaluation guidance via beam search. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34%$, $9.56%$, and $5.46%$ on the GSM8K, AQuA, and StrategyQA.
  arXiv  Detail & Related papers  (2023-05-01T02:37:59Z)
• Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
  We introduce a new regularizer for empirical value functions and show that it lower bounds the Wasserstein distributionally robust value function. It suggests using regularization as a practical tool for dealing with $textitexternal uncertainty$ in reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-05T19:56:23Z)

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.