mlsanityData to 14 Oct 2026

When Independent Sampling Outperforms Agentic Reasoning

arXiv 2605.08478 ↗First posted 8 May 2026cs.LGcited by 0

On the map: LLM reasoning → Reasoning for agents, planning and code

also in 1 more
Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning. Builds on 19 of its 23 references that are in the map. First posted on arXiv 8 May 2026.

Builds on

19 of 23 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Towards a Science of Scaling Agent Systems9 Dec
  2. 2025Debate or Vote: Which Yields Better Decisions in Multi-Agent Large Language Models?24 Aug
  3. 2025ICPC-Eval: Probing the Frontiers of LLM Reasoning with Competitive Programming Contests5 Jun
  4. 2025CodeElo: Benchmarking Competition-level Code Generation of LLMs with Human-comparable Elo Ratings2 Jan
  5. 2024Improving Multi-Agent Debate with Sparse Communication Topology17 Jun
  6. 2023Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate30 May

Other references · 13

  1. 2017Attention Is All You Needcited by 60,361
  2. 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
  3. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  4. 2024SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineeringcited by 1,737
  5. 2024A Survey on LLM-as-a-Judgecited by 1,423
  6. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  7. 2024AI Agents That Mattercited by 219
  8. 2023Theory of Mind for Multi-Agent Collaboration via Large Language Modelscited by 135
  9. 2024Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategiescited by 45
  10. 2025Cost-of-Pass: An Economic Framework for Evaluating Language Modelscited by 35
  11. 2025ELABORATION: A Comprehensive Benchmark on Human-LLM Competitive Programmingcited by 16
  12. 2025Humanity's Last Code Exam: Can Advanced LLMs Conquer Human's Hardest Code Competition?cited by 6
1 more
  1. 2025Evaluating and Improving Large Language Models for Competitive Program Generationcited by 3

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Multi-Agent Reasoning Improves Compute Efficiency: Pareto-Optimal Test-Time Scaling
  2. 2026Scaling Inference-Time Compute with Teams of Coding Agents
  3. 2026Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning in Agents
  4. 2026Thinking Before Thinking: Scaling Agentic Inference Through Meta-Reasoning
  5. 2026Agentic Systems as Boosting Weak Reasoning Models
  6. 2026DIANOIA: Diagnostic Decomposition and Joint Optimization for Multi-Agent Reasoning
  7. 2026Belief-Calibrated Optimization: An Explicit World Model for Agentic Optimization
  8. 2026What If We Allocate Test-Time Compute Adaptively?