Research map / Large language models / Reasoning and chain of thought

Strategic Scaling of Test-Time Compute: A Bandit Learning Approach

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

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 LLM test-time compute allocation across queries as a pure-exploration bandit problem and proposes elimination-based adaptive algorithms (with UCB, gap, and a new entropy rule) that allocate best-of-N samples on the fly, with theory showing better budget complexity than uniform allocation.

Problem

Uniform test-time compute allocation across queries wastes budget on easy queries and under-serves hard ones; the goal is to allocate a fixed total budget adaptively across queries to maximize the fraction answered correctly.

Approach

Treat each query as a bandit arm and sample responses sequentially; eliminate a query once a response meets the correctness threshold, with optional UCB, gap-based, or entropy-based exploration rules, so compute shifts from solved to unsolved-but-solvable queries.

Key results

• On MATH-500 with Llama-3.1-8B-Instruct at average budget 8, the method gains 11.10% absolute (15.04% relative) over uniform allocation.
• On AIME25 with Qwen3-4B, coverage at budget 16 improves by 10.82% absolute (14.44% relative).
• On LiveCodeBench with DeepSeek-R1-Distill-Llama-8B at budget 8, the method gains 9.97% absolute (12.30% relative).

Surprising findings

• The vanilla elimination variant performs poorly on MATH-500-Hard because many queries are unsolvable by the base model, while the entropy-based rule performs much better by prioritizing solvable queries.
• The entropy-based rule works because unsolvable queries produce more invalid, low-entropy outputs.

Limitations

• Assumes the reward oracle is accurate and its threshold matches correctness (approximately satisfied by PRMs).
• Hyperparameters (K, gamma, max_samples, lambda) require tuning, some via validation or per-setting selection.
• Theory assumes independent Bernoulli per-query correctness with fixed Delta_x, a simplified model.

Experimental setup

Datasets: MATH-500 AIME25 LiveCodeBench

Benchmarks: MATH-500 AIME25 LiveCodeBench MATH-500-Hard-16

Metrics: coverage accuracy

Baselines: Uniform Best-of-N Two Stage (explore-then-commit)

Builds on: Best-of-N successive elimination upper confidence bound explore-then-commit self-consistency

Closest papers by meaning

• Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.90)
• SCALE: Selective Resource Allocation for Overcoming Performance Bottlenecks in Mathematical Test-time Scaling (AAAI 2026 · similarity 0.89)
• Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.89)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models (NeurIPS 2025 · similarity 0.89)
• What If We Allocate Test-Time Compute Adaptively? (ICML 2026 · similarity 0.89)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.89)