Research map / Large language models / Reasoning and chain of thought
Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formulates test-time search rollout allocation as a Bayesian resource allocation problem and proposes DORA, which allocates rollouts at the reasoning-direction level via soft semantic clustering to correct the candidate-count bias of REBASE.
Problem
How to allocate a fixed rollout budget across candidate reasoning paths in parallel test-time search so as to maximize the probability of obtaining a correct solution, given that candidates are correlated within reasoning directions.
Approach
Derives an optimal allocation under a Beta-prior model of step success probabilities (recovering beam search, temperature sampling, and REBASE-like rules as limiting cases), then shows solution-level allocation over-weights directions with many candidates and fixes this by down-weighting each candidate by its semantic uniqueness (diagonal of a row-softmax over embedding cosine similarities) before
Key results
- On MATH500 with LLaMA-3.2-1B-Instruct, DORA at 64 rollouts reaches 68.7% accuracy vs 67.4% for REBASE at 256 rollouts (higher accuracy with fewer rollouts).
- Compared with REBASE at 256 rollouts, DORA at 64 rollouts reduces total FLOPs by about 3.5x (8.92e14 vs 3.11e15) and latency by about 4x (124s vs 490s) on MATH500.
- With LLaMA-3.1-8B-Instruct and Qwen2.5-Math-PRM-72B at 64 rollouts, DORA achieves 80.6% on MATH500 vs 79.2% for REBASE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| allocate rollouts at the direction level using DORA instead of solution-level REBASE | parallel test-time search · HMMT24, HMMT25, and AMC24; LLaMA-3.2-3B-Instruct and Qwen2.5-1.5B-Instruct | accuracy: 4.7 -> 6.7; 0.0 -> 2.0; 27.5 -> 31.1; 5.3 -> 6.7; 2.7 -> 4.0; 32.0 -> 34.2 | Helped |
| allocate rollouts at the direction level using DORA instead of solution-level REBASE | parallel test-time search · AMC23, LLaMA-3.2-1B-Instruct; HMMT24, AMC23, LLaMA-3.2-3B-Instruct; AMC23, Qwen2.5-1.5B-Instruct | accuracy: 45.0 vs 45.0; 59.0 vs 59.0; 55.0 vs 54.0 | No clear effect |
| allocate rollouts at the direction level using DORA instead of solution-level REBASE | parallel test-time search · HMMT25, LLaMA-3.2-1B-Instruct | accuracy: 0.0 vs 0.0 | No clear effect |
| allocate rollouts at the direction level using DORA instead of solution-level REBASE | LLaMA-3.2-1B-Instruct search · MATH500 | accuracy: 67.4(0.8) -> 68.7(0.8) | Helped |
| allocate rollouts at the direction level using DORA instead of solution-level REBASE | LLaMA-3.2-1B-Instruct search · AIME24 | accuracy: 14.7(2.3) vs 14.7(2.3) | No clear effect |
| use soft clustering instead of hard clustering alternatives (ablation) | DORA · MATH500 | accuracy: 67.6 -> 68.7; 68.0 -> 68.7; 67.8 -> 68.7; 67.0 -> 68.7; 66.6 -> 68.7; 66.0 -> 68.7 | Helped |
| set quality temperature Tb=1.0 instead of Tb=0.1 (ablation) | DORA · MATH500 | accuracy: 68.7 -> 57.2 | Hurt |
| vary semantic similarity temperature Ts from 0.01 to 0.001 or 0.1–1.0 (ablation) | DORA · MATH500 | accuracy: 68.7; 67.8; 68.0; 67.5 | No clear effect |
| replace BGE-M3 with GTE-multilingual-base (ablation) | DORA · MATH500, LLaMA-3.2-1B-Instruct | accuracy: 68.7 -> 68.2 | No clear effect |
| replace BGE-M3 with E5-base-4k (ablation) | DORA · MATH500, LLaMA-3.2-1B-Instruct | accuracy: 68.7 -> 66.8 | Hurt |
Surprising findings
- Solution-level allocation (REBASE) is shown to be suboptimal; the paper proves it deviates from the optimal direction-level allocation whenever directions have unequal candidate counts.
- Hard clustering methods (KMeans, hierarchical) were less effective than the soft clustering used in DORA in the reported ablation.
Limitations
- Requires a process reward model to score partial trajectories; the framework is not validated with other intermediate signals.
- Theoretical analysis assumes a low-confidence (kappa to 0) regime and does not model confidence accumulation over multi-step reasoning.
- Experiments are limited to mathematical reasoning benchmarks, where PRMs are primarily available.
Experimental setup
Datasets: MATH500 AIME2024 AIME2025 HMMT24 HMMT25 AMC23 AMC24
Benchmarks: MATH500 AIME2024 AIME2025 HMMT24 HMMT25 AMC23 AMC24
Metrics: accuracy pass rate FLOPs inference latency intermediate success rate
Baselines: Temperature Sampling Beam Search DVTS REBASE
Builds on: REBASE Beam Search DVTS Process Reward Model
Closest papers by meaning
- SCALE: Selective Resource Allocation for Overcoming Performance Bottlenecks in Mathematical Test-time Scaling (AAAI 2026 · similarity 0.92)
- Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.91)
- AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks (NeurIPS 2025 · similarity 0.91)
- Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models (ICLR 2026 · similarity 0.91)
- Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods (NeurIPS 2025 · similarity 0.91)
- Provable Test-Time Scaling for Beam Search in LLM Reasoning (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.