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

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

## Key facts

- Cited by 26 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 34 of its 53 references that are in the map.
- First posted on arXiv 29 Nov 2024.

## 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 34)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [Large Language Models are not Fair Evaluators](https://mlsanity.com/paper/2305.17926/) (2023)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [LLM-Blender: Ensembling Large Language Models with Pairwise Ranking and Generative Fusion](https://mlsanity.com/paper/2306.02561/) (2023)
- [From Generation to Judgment: Opportunities and Challenges of LLM-as-a-judge](https://mlsanity.com/paper/2411.16594/) (2024)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [Mixture-of-Agents Enhances Large Language Model Capabilities](https://mlsanity.com/paper/2406.04692/) (2024)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Statistical Rejection Sampling Improves Preference Optimization](https://mlsanity.com/paper/2309.06657/) (2023)
- [AI Agents That Matter](https://mlsanity.com/paper/2407.01502/) (2024)
- [More Agents Is All You Need](https://mlsanity.com/paper/2402.05120/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [AgentScope: A Flexible yet Robust Multi-Agent Platform](https://mlsanity.com/paper/2402.14034/) (2024)
- [Exchange-of-Thought: Enhancing Large Language Model Capabilities through Cross-Model Communication](https://mlsanity.com/paper/2312.01823/) (2023)
- [Aligning Large Language Models by On-Policy Self-Judgment](https://mlsanity.com/paper/2402.11253/) (2024)

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

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification](https://mlsanity.com/paper/2502.01839/) (2025)
- [How Do Large Language Monkeys Get Their Power (Laws)?](https://mlsanity.com/paper/2502.17578/) (2025)
- [Can Slow-thinking LLMs Reason Over Time? Empirical Studies in Time Series Forecasting](https://mlsanity.com/paper/2505.24511/) (2025)
- [ROC-n-reroll: How verifier imperfection affects test-time scaling](https://mlsanity.com/paper/2507.12399/) (2025)
- [VideoGameQA-Bench: Evaluating Vision-Language Models for Video Game Quality Assurance](https://mlsanity.com/paper/2505.15952/) (2025)
- [Rethinking the Role of Prompting Strategies in LLM Test-Time Scaling: A Perspective of Probability Theory](https://mlsanity.com/paper/2505.10981/) (2025)
- [Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning](https://mlsanity.com/paper/2503.01642/) (2025)
- [Reasoning or Overthinking: Evaluating Large Language Models on Financial Sentiment Analysis](https://mlsanity.com/paper/2506.04574/) (2025)
- [From Mathematical Reasoning to Code: Generalization of Process Reward Models in Test-Time Scaling](https://mlsanity.com/paper/2506.00027/) (2025)
- [A Short Survey on Small Reasoning Models: Training, Inference, Applications and Research Directions](https://mlsanity.com/paper/2504.09100/) (2025)
- [Scaling Laws for Energy Efficiency of Local LLMs](https://mlsanity.com/paper/2512.16531/) (2025)
- [Beyond Consensus: Trace-Level Synthesis in Mixture of Agents](https://mlsanity.com/paper/2605.29116/) (2026)
- [Critical-Questions-of-Thought: Steering LLM reasoning with Argumentative Querying](https://mlsanity.com/paper/2412.15177/) (2024)
- [ARTIS: Agentic Risk-Aware Test-Time Scaling via Iterative Simulation](https://mlsanity.com/paper/2602.01709/) (2026)
- [Partially Correlated Verifier Cascades in LLM Harnesses: Concave Log-Odds, Polynomial Reliability, and Blind-Spot Ceilings](https://mlsanity.com/paper/2607.13918/) (2026)
- [Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoning](https://mlsanity.com/paper/2505.17829/) (2025)
- [Accurate Table Question Answering with Accessible LLMs](https://mlsanity.com/paper/2601.03137/) (2026)
- [Continued AI Scaling Requires Repeated Efficiency Doublings](https://mlsanity.com/paper/2603.28507/) (2026)
- [Adaptive Test-Time Scaling for Zero-Shot Respiratory Audio Classification](https://mlsanity.com/paper/2604.12647/) (2026)
- [Large Language Models Explore by Latent Distilling](https://mlsanity.com/paper/2604.24927/) (2026)
- [Connect the Dots: Training LLMs for Long-Lifecycle Agents with Cross-Domain Generalization Via Reinforcement Learning](https://mlsanity.com/paper/2606.20002/) (2026)
- [OptiCom : A Unified Framework for State-Conditioned Composition in LLM-Driven Optimization](https://mlsanity.com/paper/2609.37221/) (2026)
- [From Discovery to Decision: Finite-Budget Recoverability in LLM Voting](https://mlsanity.com/paper/2610.01014/) (2026)
- [How Much Can Language Models Gain from Test-Time Computation?](https://mlsanity.com/paper/2610.01110/) (2026)
- [Tail Competition Explains Scaling in Best-of-N Sampling for Verifiable Problems](https://mlsanity.com/paper/2610.19362/) (2026)

## 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.