# Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling

arXiv: https://arxiv.org/abs/2506.15707 · HTML: https://mlsanity.com/paper/2506.15707/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 31 of its 59 references that are in the map.
- First posted on arXiv 30 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 31)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Improve Mathematical Reasoning in Language Models by Automated Process Supervision](https://mlsanity.com/paper/2406.06592/) (2024)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [ProcessBench: Identifying Process Errors in Mathematical Reasoning](https://mlsanity.com/paper/2412.06559/) (2024)
- [The False Promise of Imitating Proprietary LLMs](https://mlsanity.com/paper/2305.15717/) (2023)
- [Making Large Language Models Better Reasoners with Step-Aware Verifier](https://mlsanity.com/paper/2206.02336/) (2022)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling](https://mlsanity.com/paper/2502.06703/) (2025)
- [Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning](https://mlsanity.com/paper/2412.09078/) (2024)
- [Let's reward step by step: Step-Level reward model as the Navigators for Reasoning](https://mlsanity.com/paper/2310.10080/) (2023)
- [RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold](https://mlsanity.com/paper/2406.14532/) (2024)
- [PRMBench: A Fine-grained and Challenging Benchmark for Process-Level Reward Models](https://mlsanity.com/paper/2501.03124/) (2025)
- [A Sober Look at Progress in Language Model Reasoning: Pitfalls and Paths to Reproducibility](https://mlsanity.com/paper/2504.07086/) (2025)
- [Scaling Test-Time Compute Without Verification or RL is Suboptimal](https://mlsanity.com/paper/2502.12118/) (2025)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding](https://mlsanity.com/paper/2309.15028/) (2023)
- [Enhancing LLM Reasoning with Reward-guided Tree Search](https://mlsanity.com/paper/2411.11694/) (2024)
- [Can Pruning Improve Reasoning? Revisiting Long-CoT Compression with Capability in Mind for Better Reasoning](https://mlsanity.com/paper/2505.14582/) (2025)
- [ETS: Efficient Tree Search for Inference-Time Scaling](https://mlsanity.com/paper/2502.13575/) (2025)

## Built on by (most cited first, 15 of 15)

- [Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation](https://mlsanity.com/paper/2509.25849/) (2025)
- [Do Not Waste Your Rollouts: Recycling Search Experience for Efficient Test-Time Scaling](https://mlsanity.com/paper/2601.21684/) (2026)
- [Fact-Augmented Lookahead Planning for LLM Agents](https://mlsanity.com/paper/2506.09171/) (2025)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [CyclicReflex: Improving Reasoning Models via Cyclical Reflection Token Scheduling](https://mlsanity.com/paper/2506.11077/) (2025)
- [Mitigating Premature Exploitation in Particle-based Monte Carlo for Inference-Time Scaling](https://mlsanity.com/paper/2510.05825/) (2025)
- [PETS: A Principled Framework Towards Optimal Trajectory Allocation for Efficient Test-Time Self-Consistency](https://mlsanity.com/paper/2602.16745/) (2026)
- [Believe Your Model: Distribution-Guided Confidence Calibration](https://mlsanity.com/paper/2603.03872/) (2026)
- [Share More, Search Less: Collaborative Parallel Thinking for Efficient Test-Time Scaling](https://mlsanity.com/paper/2605.27030/) (2026)
- [MILES: Modular Instruction Memory with Learnable Selection for Self-Improving LLM Reasoning](https://mlsanity.com/paper/2607.06974/) (2026)
- [ParaTempo: Efficient Parallel Reasoning via Temporal Confidence](https://mlsanity.com/paper/2608.16425/) (2026)
- [Adaptive Uncertainty-Aware Tree Search for Robust Reasoning](https://mlsanity.com/paper/2602.06493/) (2026)
- [HyPER: Bridging Exploration and Exploitation for Scalable LLM Reasoning with Hypothesis Path Expansion and Reduction](https://mlsanity.com/paper/2602.06527/) (2026)
- [Consilience for Verifier-Free Test-Time Scaling](https://mlsanity.com/paper/2608.09898/) (2026)
- [Recursive Agentic Reasoning](https://mlsanity.com/paper/2608.23956/) (2026)

## Abstract (arXiv)

Test-Time Scaling (TTS) improves the performance of Large Language Models (LLMs) by using additional inference-time computation to explore multiple reasoning paths through search. Yet how to allocate a fixed rollout budget most effectively during search remains underexplored, often resulting in inefficient use of compute at test time. To bridge this gap, we formulate test-time search as a resource allocation problem and derive the optimal allocation strategy that maximizes the probability of obtaining a correct solution under a fixed rollout budget. Within this formulation, we reveal a core limitation of existing search methods: solution-level allocation tends to favor reasoning directions with more candidates, leading to theoretically suboptimal and inefficient use of compute. To address this, we propose Direction-Oriented Resource Allocation (DORA), a provably optimal method that mitigates this bias by decoupling direction quality from candidate count and allocating resources at the direction level. To demonstrate DORA's effectiveness, we conduct extensive experiments on challenging mathematical reasoning benchmarks including MATH500, AIME2024, and AIME2025. The empirical results show that DORA consistently outperforms strong baselines with comparable computational cost, achieving state-of-the-art accuracy. We hope our findings contribute to a broader understanding of optimal TTS for LLMs.