mlsanityData to 7 Oct 2026

Provable Scaling Laws for the Test-Time Compute of Large Language Models

arXiv 2411.19477 ↗First posted 29 Nov 2024cs.CL cs.AI cs.LGcited by 25

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

We propose two simple, principled and practical algorithms that enjoy provable scaling laws for the test-time compute of large language models (LLMs). The first one is a two-stage knockout-style algorithm: given an input problem, it first generates multiple candidate solutions, and then aggregate them via a knockout tournament for the final output. Assuming that the LLM can generate a correct solution with non-zero probability and do better than a random guess in comparing a pair of correct and incorrect solutions, we prove theoretically that the failure probability of this algorithm decays to zero exponentially or by a power law (depending on the specific way of scaling) as its test-time compute grows. The second one is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents, rather than eliminated upon loss to a single opponent. Under analogous but more robust assumptions, we prove that its failure probability also decays to zero exponentially with more test-time compute. Both algorithms require a black-box LLM and nothing else (e.g., no verifier or reward model) for a minimalistic implementation, which makes them appealing for practical applications and easy to adapt for different tasks. Through extensive experiments with diverse models and datasets, we validate the proposed theories and demonstrate the outstanding scaling properties of both algorithms.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 34 of its 53 references that are in the map. First posted on arXiv 29 Nov 2024.

Builds on

34 of 53 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024Scaling LLM Inference with Optimized Sample Compute Allocation29 Oct
  2. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters6 Aug
  3. 2023Large Language Models Cannot Self-Correct Reasoning Yet3 Oct
  4. 2023Self-Refine: Iterative Refinement with Self-Feedback30 Mar
  5. 2022Language Models (Mostly) Know What They Know11 Jul

Other references · 29

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  3. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  4. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,393
  5. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  7. 2022Large Language Models are Zero-Shot Reasonerscited by 4,323
  8. 2023Let's Verify Step by Stepcited by 3,598
  9. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,748
  10. 2024MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmarkcited by 1,758
  11. 2023Improving Factuality and Reasoning in Language Models through Multiagent Debatecited by 1,739
  12. 2023The Rise and Potential of Large Language Model Based Agents: A Surveycited by 1,422
17 more
  1. 2023Large Language Models are not Fair Evaluatorscited by 1,050
  2. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 946
  3. 2023LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusioncited by 550
  4. 2024From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judgecited by 480
  5. 2024Generative Verifiers: Reward Modeling as Next-Token Predictioncited by 465
  6. 2024Mixture-of-Agents Enhances Large Language Model Capabilitiescited by 420
  7. 2023SLiC-HF: Sequence Likelihood Calibration with Human Feedbackcited by 395
  8. 2023Statistical Rejection Sampling Improves Preference Optimizationcited by 321
  9. 2024AI Agents That Mattercited by 199
  10. 2024More Agents Is All You Needcited by 174
  11. 2024From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Modelscited by 136
  12. 2024AgentScope: A Flexible yet Robust Multi-Agent Platformcited by 120
  13. 2023Exchange-of-Thought: Enhancing Large Language Model Capabilities through Cross-Model Communicationcited by 78
  14. 2024Aligning Large Language Models by On-Policy Self-Judgmentcited by 20
  15. 2024Networks of Networks: Complexity Class Principles Applied to Compound AI Systems Designcited by 13
  16. 2024Rationale-Aware Answer Verification by Pairwise Self-Evaluationcited by 8
  17. 2024Designing Algorithms Empowered by Language Models: An Analytical Framework, Case Studies, and Insightscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 13; 2026: 11.

25 papers.

Sort:

By area:

  1. 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Modelscited by 381
  2. 2025Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verificationcited by 49
  3. 2025How Do Large Language Monkeys Get Their Power (Laws)?cited by 40
  4. 2025Can Slow-thinking LLMs Reason Over Time? Empirical Studies in Time Series Forecastingcited by 19
  5. 2025VideoGameQA-Bench: Evaluating Vision-Language Models for Video Game Quality Assurancecited by 11
  6. 2025ROC-n-reroll: How verifier imperfection affects test-time scalingcited by 11
  7. 2025Rethinking the Role of Prompting Strategies in LLM Test-Time Scaling: A Perspective of Probability Theorycited by 10
  8. 2025Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoningcited by 8
  9. 2025From Mathematical Reasoning to Code: Generalization of Process Reward Models in Test-Time Scalingcited by 5
  10. 2025Reasoning or Overthinking: Evaluating Large Language Models on Financial Sentiment Analysiscited by 5
  11. 2025A Short Survey on Small Reasoning Models: Training, Inference, Applications and Research Directionscited by 4
  12. 2025Scaling Laws for Energy Efficiency of Local LLMscited by 4
13 more
  1. 2026Beyond Consensus: Trace-Level Synthesis in Mixture of Agentscited by 3
  2. 2024Critical-Questions-of-Thought: Steering LLM reasoning with Argumentative Queryingcited by 2
  3. 2026ARTIS: Agentic Risk-Aware Test-Time Scaling via Iterative Simulationcited by 2
  4. 2026Partially Correlated Verifier Cascades in LLM Harnesses: Concave Log-Odds, Polynomial Reliability, and Blind-Spot Ceilingscited by 2
  5. 2025Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoningcited by 0
  6. 2026Accurate Table Question Answering with Accessible LLMscited by 0
  7. 2026Continued AI Scaling Requires Repeated Efficiency Doublingscited by 0
  8. 2026Adaptive Test-Time Scaling for Zero-Shot Respiratory Audio Classificationcited by 0
  9. 2026Large Language Models Explore by Latent Distillingcited by 0
  10. 2026Connect the Dots: Training LLMs for Long-Lifecycle Agents with Cross-Domain Generalization Via Reinforcement Learningcited by 0
  11. 2026OptiCom : A Unified Framework for State-Conditioned Composition in LLM-Driven Optimizationcited by 0
  12. 2026From Discovery to Decision: Finite-Budget Recoverability in LLM Votingcited by 0
  13. 2026How Much Can Language Models Gain from Test-Time Computation?cited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models
  2. 2025The Art of Scaling Test-Time Compute for Large Language Models
  3. 2025Test-time Scaling of LLMs: A Survey from A Subproblem Structure Perspective
  4. 2025Scaling Test-time Compute for LLM Agents
  5. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?
  6. 2026Predicting and improving test-time scaling laws via reward tail-guided search
  7. 2025AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks
  8. 2025Can 1B LLM Surpass 405B LLM? Rethinking Compute-Optimal Test-Time Scaling