Research map / Large language models / Reasoning and chain of thought
Provable Scaling Laws for the Test-Time Compute of Large Language Models
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.
Proposes knockout-style and league-style test-time compute aggregation algorithms using only a black-box LLM for pairwise comparisons, with theorems giving provable exponential or power-law decay of failure probability, validated on GPQA, MMLU-Pro and MATH-500.
Problem
Test-time compute scaling for LLMs typically lacks guarantees when verifiers are imperfect and majority voting can fail; the paper seeks algorithms whose success probability provably approaches 100% as compute grows, without verifiers or reward models.
Approach
Generate N candidates, then aggregate them using only LLM pairwise comparisons, either via a knockout tournament (single-elimination with majority-of-K comparisons) or a league scheme that ranks candidates by average win rate against sampled opponents; under explicit assumptions on non-zero correct-generation probability and better-than-chance pairwise comparison, failure probability provably deca
Key results
- Mixed-LLM knockout accuracy on GPQA improves from 45% to 55% as N scales to 64.
- QwQ-32B accuracy on GPQA-diamond improves from 60% to 72% as N scales to 16 with the knockout-style algorithm.
- On a filtered subset of GPQA problems satisfying the assumptions (approximately), knockout accuracy rises from 55% to 80% with scaling N.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of initial candidates from 1 to 64 | Knockout (Mixed) · GPQA | accuracy: 45% to 55% | Helped |
| Increase the number of initial candidates from 1 to 16 | Knockout · GPQA-diamond | accuracy: 60% to 72% | Helped |
| Increase the number of initial candidates from 1 to 16 | League (Mixed) · GPQA | accuracy: 45% to 53% | Helped |
| Use a mixture of Llama3.1 and Qwen2.5 instead of either model alone | Knockout · GPQA | accuracy | Helped |
| Use knockout aggregation instead of majority voting at the same number of initial candidates | Test-time inference · GPQA and GPQA-diamond | accuracy | Helped |
| Use knockout with N=8 instead of majority voting with N=64 | Mixed · GPQA | accuracy | Helped |
| Use knockout with N=4 instead of majority voting with N=16 | QwQ-32B · GPQA-diamond | accuracy | Helped |
| Use league aggregation instead of knockout aggregation with the same initial candidates | Test-time inference · GPQA | accuracy | Mixed |
| Add zero-shot chain-of-thought prompting for pairwise comparisons (ablation) | Knockout · GPQA and other evaluated settings | accuracy | Helped |
| Vary the number of pairwise comparisons K (ablation) | Knockout · Evaluated settings | accuracy | No clear effect |
| Increase the number of subsampled opponents per candidate (ablation) | League (N=16) · GPQA | accuracy | Mixed |
| Use subsampled opponents instead of round-robin comparisons (ablation) | League (N=16) · GPQA | accuracy | No clear effect |
Surprising findings
- Majority voting may converge to zero success probability if an incorrect answer has a higher single-call probability than the correct one.
- Knockout with N=8 (about 40 calls) outperforms majority voting at N=64 for the Mixed option.
Limitations
- Theoretical assumptions (non-zero correct-generation probability and better-than-chance pairwise comparison for every correct-incorrect pair) may not hold for hard problems.
- Experiments run once per model-dataset pair without error bars due to cost.
- Scaling plateaus because the empirical proxies only approximate the assumption parameters.
Experimental setup
Datasets: GPQA MMLU-Pro MATH-500
Benchmarks: GPQA GPQA-diamond MMLU-Pro-S MATH-500
Metrics: accuracy
Baselines: majority voting Llama3.1-70B-Instruct Qwen2.5-72B-Instruct QwQ-32B GPT-4o
Builds on: chain-of-thought prompting majority voting best-of-N sampling round-robin tournament
Closest papers by meaning
- Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.93)
- AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks (NeurIPS 2025 · similarity 0.91)
- Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck (NeurIPS 2026 · similarity 0.91)
- OptScale: Probabilistic Optimality for Inference-time Scaling (AAAI 2026 · similarity 0.90)
- Resolving Discrepancies in Compute-Optimal Scaling of Language Models (NeurIPS 2024 · similarity 0.90)
- Scaling Inference-Efficient Language Models (ICML 2025 · 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.