Abstract
The dominant paradigm in large language model (LLM) development has concentrated intelligence in training: more parameters, more data, more compute applied before deployment. Recent empirical and theoretical work challenges this assumption by demonstrating that allocating additional compute at inference time—rather than solely during training—can yield substantial and sometimes dramatic improvements in model capability, particularly on reasoning-intensive tasks. This paper examines the theoretical underpinnings and practical mechanisms of test-time compute scaling, including best-of-N sampling, sequential refinement, tree search over reasoning steps, and process reward model (PRM)-guided search. We analyze the sample complexity, diversity-accuracy tradeoffs, and verification bottlenecks that govern when and why inference-time scaling works. We situate these methods within the broader landscape of reasoning-augmented LLM systems, discuss their relationship to speculative decoding and chain-of-thought prompting, and identify open research problems—particularly the verifier gap, the cost-accuracy Pareto frontier, and the question of whether inference-time scaling constitutes a fundamentally new axis of the neural scaling laws.
1. Introduction
The scaling laws of Kaplan et al. (2020) established a now-canonical picture of language model improvement: loss decreases predictably as a power law in training compute, number of parameters, and dataset size. This framing placed nearly all emphasis on training-time investment—on building larger, better-trained models—and treated inference as a fixed-cost deployment artifact.
This picture is incomplete. A growing body of evidence, crystallized in work on OpenAI’s o1 and o3 models (OpenAI, 2024), Google’s Gemini Thinking variants, and academic research into tree-search augmented generation, demonstrates that inference-time compute can be traded against training-time compute to achieve comparable or superior results on difficult tasks. The o3 model, for instance, achieves dramatically improved performance on mathematical olympiad problems and code generation benchmarks by spending substantially more tokens on internal reasoning before committing to an answer.
This development reopens fundamental questions. Is there an inference-time analog of the training scaling laws? What mechanisms drive inference-time improvement—diversity of samples, iterative self-correction, search over solution spaces, or some combination? When does more inference compute actually help, and when does it fail? And what does a world look like in which AI systems dynamically allocate reasoning effort based on task difficulty?
This paper provides a structured analysis of these questions. We begin with related work situating test-time compute within prior research on sampling strategies and reasoning augmentation. We then develop a technical analysis of the core mechanisms—best-of-N, sequential refinement, tree search, and reward-guided search—with attention to the mathematical structure governing their behavior. We discuss implications for system design and the emerging verifier problem, and conclude with open research directions.
2. Related Work
Sampling and diversity in generation. The basic intuition that sampling multiple outputs and selecting the best improves quality dates to self-consistency prompting (Wang et al., 2023), which showed that majority voting over multiple chain-of-thought reasoning paths substantially improves accuracy on arithmetic and commonsense reasoning benchmarks. This work established empirically that generation diversity is a valuable resource at inference time, even without learned verifiers.
Process reward models. Lightman et al. (2023) introduced process reward models (PRMs) trained on step-level human annotations of mathematical reasoning in the PRM800K dataset. Unlike outcome reward models that score only final answers, PRMs assign credit to individual reasoning steps, enabling fine-grained guidance of search processes. This work demonstrated that PRM-guided beam search substantially outperforms outcome-reward-guided search on MATH benchmarks, establishing the verification quality as a key bottleneck.
Tree search over reasoning. Yao et al. (2023) introduced Tree of Thoughts (ToT), which applies tree search (breadth-first or depth-first) over intermediate reasoning steps represented as “thoughts.” The model both generates candidate thoughts and evaluates their promise, enabling backtracking and exploration of multiple solution paths. ToT demonstrated substantial gains on planning and creative writing tasks that benefit from non-linear search.
Monte Carlo Tree Search for language models. Feng et al. (2023) adapted Monte Carlo Tree Search (MCTS) to LLM reasoning, formulating token or sentence generation as a sequential decision process and using rollouts to estimate state values. This line of work connects LLM reasoning augmentation to the reinforcement learning literature on planning in large state spaces, and foreshadows the more recent use of MCTS in AlphaCode 2 and similar systems.
Inference-time scaling laws. Snell et al. (2024) and Brown et al. (2024) provide systematic empirical analyses of inference-time compute scaling, characterizing how performance improves with additional samples, search depth, and verifier quality. These papers attempt to characterize the inference-time analog of training scaling laws and identify the conditions under which inference-time and training-time compute are substitutable.
3. Technical Analysis
3.1 Best-of-N Sampling
The simplest test-time compute strategy generates $N$ independent samples from a model and selects the best according to some scoring function $s: \mathcal{Y} \to \mathbb{R}$. Formally, given a prompt $x$ and model $p_\theta(y | x)$:
$$\hat{y} = \arg\max_{y \in \{y_1, \ldots, y_N\}} s(y), \quad y_i \sim p_\theta(\cdot | x)$$
The performance of best-of-N depends on three factors: the base rate of correct solutions in the model’s distribution, the diversity of samples, and the quality of the scorer $s$. When the scorer is an oracle (i.e., $s(y) = 1$ iff $y$ is correct), best-of-N performance is governed by:
$$P(\text{at least one correct in } N) = 1 – (1 – p)^N$$
where $p = P_{y \sim p_\theta}(y \text{ is correct} | x)$. This expression reveals the critical importance of base rate $p$: if $p$ is very small (the model rarely generates correct answers), even large $N$ provides limited benefit. Conversely, when $p > 0.1$, best-of-N provides substantial gains achievable with modest $N$.
In practice, the scorer is never an oracle. Outcome reward models (ORMs) trained to predict answer correctness serve as approximate scorers, introducing a fundamental tension: the scorer must be accurate enough to select the genuinely best sample, not merely the sample that appears best to the scorer. This discrepancy—scorer accuracy versus true quality correlation—is the first major source of failure in best-of-N scaling.
Diversity is a second critical factor. If $p_\theta$ assigns high probability to a narrow mode, all $N$ samples may be near-identical, and the effective sample complexity does not increase with $N$. Temperature scaling at inference time is the standard intervention: generating with temperature $T > 1$ increases entropy and sample diversity at the cost of individual sample quality. The optimal temperature for best-of-N exhibits a non-trivial tradeoff that depends on $N$, $p$, and the scorer quality.
3.2 Sequential Refinement and Self-Correction
An alternative to parallel sampling is sequential refinement: generating an initial response $y_0$, then iteratively revising it based on feedback $f_t$:
$$y_{t+1} = p_\theta(\cdot | x, y_0, f_1, y_1, \ldots, f_t, y_t)$$
The feedback $f_t$ may come from an external verifier (code execution, unit tests, symbolic checking), a separate critic model, or the generating model itself (self-refinement). Madaan et al. (2023) demonstrated that self-refinement with natural language feedback improves performance on code generation, dialogue response quality, and mathematical reasoning, though the gains are task-dependent.
A critical finding, emphasized in Huang et al. (2023), is that self-refinement without external feedback is unreliable: models tend to “refine” correct answers into incorrect ones at non-trivial rates, as they lack grounded feedback to distinguish genuine errors from superficial stylistic differences. This establishes a key principle: sequential refinement is most effective when grounded in external or verifiably correct feedback signals. In code generation, execution feedback provides exactly this signal; in mathematical reasoning, step-by-step process reward models serve a similar role.
3.3 Tree Search with Process Reward Models
The most general framework for test-time compute scaling treats generation as a sequential decision process and applies search over the space of partial solutions. Let $s_t$ denote a partial reasoning state (e.g., a sequence of reasoning steps up to step $t$), $A(s_t)$ the set of possible next steps, and $V(s_t)$ a value function estimating the probability of reaching a correct final answer from state $s_t$.
Beam search maintains a set of $B$ beams (partial solutions), at each step expanding each beam by sampling $K$ candidate next steps from $p_\theta$ and pruning to the top $B$ by $V$:
$$\mathcal{B}_{t+1} = \text{TopB}\left(\{(s_t, a) : s_t \in \mathcal{B}_t, a \in \text{sample}_K(p_\theta(\cdot | s_t))\}, V\right)$$
The value function $V$ is the process reward model, trained on human or synthetically annotated step-level correctness labels. The key insight of Lightman et al. (2023) is that step-level reward is substantially more informative than outcome-level reward for guiding search: an outcome model knows only whether the final answer is correct, while a process model identifies where reasoning goes wrong, enabling more targeted exploration.
Monte Carlo Tree Search (MCTS) extends beam search by incorporating exploration bonuses and rollout-based value estimation. The UCT (Upper Confidence bound for Trees) selection criterion balances exploitation and exploration:
$$a^* = \arg\max_{a \in A(s)} \left[ Q(s, a) + c \cdot \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$
where $Q(s, a)$ is the estimated value of taking action $a$ from state $s$, $N(s)$ is the visit count of state $s$, $N(s, a)$ is the visit count of the $(s, a)$ pair, and $c$ is an exploration constant. The key difference from beam search is that MCTS allocates compute adaptively based on the uncertainty of value estimates, revisiting promising branches when rollout estimates are noisy.
3.4 The Verifier Gap and Compute-Accuracy Tradeoffs
Across all test-time compute strategies, verifier quality is the binding constraint. Define the verifier gap as the difference between oracle best-of-N performance (using a perfect scorer) and practical best-of-N performance (using a learned PRM or ORM):
$$\Delta_V(N) = P(\text{oracle selects correct} | N) – P(\text{model selects correct} | N)$$
Empirically, $\Delta_V(N)$ tends to increase with $N$ for imperfect verifiers. As $N$ grows, the oracle can identify the single correct answer among an increasingly large pool; but an imperfect verifier is increasingly likely to find a plausible-looking but incorrect answer that fools it—an instance of reward hacking in the test-time setting. This creates a characteristic shape in the scaling curve: initial gains flatten and eventually reverse as $N$ grows beyond the verifier’s reliability threshold.
This phenomenon is structurally analogous to reward hacking in RLHF training (Skalse et al., 2022): in both cases, a learned proxy reward is optimized more aggressively than it can support, leading to adversarial exploitation of its errors. The mitigation strategies are also analogous: ensemble verification, uncertainty-aware reward modeling, and calibrated reward models that abstain when uncertain.
The compute-accuracy Pareto frontier—the set of (compute, accuracy) pairs achievable by varying inference strategy—reveals whether inference and training compute are substitutable. Snell et al. (2024) find that a smaller model with more inference compute can match a larger model with less inference compute on certain task distributions, but that the substitutability is imperfect: some capabilities appear to require training-time learning and cannot be recovered by search alone.
3.5 Adaptive Compute Allocation
A natural extension of fixed-budget test-time scaling is adaptive allocation: spending more compute on harder problems. Given a difficulty estimator $d(x)$ for prompt $x$, one can allocate inference budget $N(x) = f(d(x))$ proportionally to estimated difficulty, keeping average compute constant while improving performance on the hardest instances.
The challenge is that difficulty is not known a priori and must be estimated from features of the prompt or from preliminary model outputs. In practice, confidence-based early exit (generating until the model’s confidence exceeds a threshold) and learned difficulty classifiers both provide workable difficulty proxies. The optimal allocation function $f$ under a compute budget constraint is a nontrivial optimization problem that depends on the joint distribution of task difficulty and model error rates.
4. Discussion
4.1 Is Inference-Time Scaling a New Axis?
The training scaling laws describe power-law improvement in loss as a function of compute $C$, parameters $N$, and data $D$. The natural question is whether inference-time compute $C_i$ constitutes a fourth, independent axis of this relationship, or whether it is better understood as a recovery mechanism—recovering performance that a smaller model could not achieve through training alone.
The evidence points toward a nuanced answer. On tasks with clear verifiers (mathematics, code), inference-time compute genuinely extends model capabilities beyond what training compute alone achieves at fixed model size. On tasks without reliable verifiers (open-ended writing, commonsense reasoning), inference-time compute provides more modest and less consistent benefits. This asymmetry suggests that the inference-time axis is real but verifier-constrained: its effective scope is limited to the subset of tasks where correctness can be reliably evaluated.
4.2 Relationship to Reasoning and Chain-of-Thought
Chain-of-thought prompting (Wei et al., 2022) can be viewed as a special case of inference-time compute scaling: by generating explicit reasoning steps before a final answer, the model allocates more tokens—and thus more computation—to difficult problems. The test-time scaling literature extends this by making the search over reasoning explicit, treating intermediate steps as actions in a search process rather than fixed sequential outputs.
The o1/o3 model family represents a further integration: the model learns, through reinforcement learning on reasoning traces, to autonomously allocate reasoning depth proportional to task difficulty. This combines the benefits of learned reasoning strategies (from training) with dynamic inference-time compute allocation, blurring the training/inference distinction in a fundamental way.
4.3 Cost Implications and Practical Deployment
Test-time compute scaling is not free. The compute cost of best-of-N scales linearly in $N$; tree search scales as $O(B \cdot K^D)$ in the worst case for depth $D$ and branching factor $K$. For systems serving millions of queries, the cost implications are significant. This motivates research into adaptive compute allocation, distillation of reasoning capabilities from search-augmented models into smaller models (Zelikman et al., 2022, STaR), and efficient search algorithms that reduce effective branching factor through learned pruning.
Speculative decoding (Leviathan et al., 2023) addresses a different but related efficiency problem: reducing the wall-clock latency of inference without changing the output distribution. It is complementary to test-time compute scaling in that both concern inference efficiency, but they operate on different objectives—speculative decoding preserves output distribution while test-time scaling explicitly changes it in favor of higher-quality outputs.
4.4 The Verifier Training Problem
The verifier gap analysis reveals that verifier quality is the central bottleneck in test-time compute scaling. This redirects research investment from generation quality to verification quality—a significant shift. Training high-quality process reward models requires step-level annotations, which are expensive and may not scale to all domains. Automated approaches to generating process supervision labels—including synthetic annotation via Monte Carlo rollouts, reward model ensembles, and self-verification—are active research areas with significant implications for the practical deployment of test-time compute scaling.
5. Conclusion
Test-time compute scaling represents a genuine and practically significant axis of large language model capability, one that the dominant training-centric scaling narrative has underemphasized. The core mechanisms—best-of-N sampling, sequential refinement, and PRM-guided tree search—are theoretically well-grounded and empirically validated, particularly on reasoning tasks with clear verifiers. The verifier gap emerges as the fundamental constraint: inference-time search is only as powerful as the verifier guiding it, and imperfect verifiers create characteristic failure modes that mirror reward hacking in RLHF training.
Three open problems stand out. First, whether inference-time and training-time compute are truly substitutable on the long-horizon scaling curve, or whether certain capabilities require training-time learning that search cannot recover. Second, how to train reliable process reward models at scale without expensive human annotation, and whether automated approaches can close the verifier gap. Third, how to optimally allocate inference-time compute across a distribution of query difficulties in production systems where average compute budgets are constrained.
The broader implication is that future AI systems will likely be designed with dynamic, difficulty-adaptive inference pipelines rather than fixed-cost generation. This changes the engineering and economic calculus of AI deployment, and raises new theoretical questions about the structure of the capability-compute relationship across both training and inference axes.
References
- Brown, B., et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv preprint arXiv:2407.21787.
- Feng, X., et al. (2023). Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training. arXiv preprint arXiv:2309.17179.
- Huang, J., et al. (2023). Large Language Models Cannot Self-Correct Reasoning Yet. arXiv preprint arXiv:2310.01848.
- Kaplan, J., et al. (2020). Scaling Laws for Neural Language Models. arXiv preprint arXiv:2001.08361.
- Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. Proceedings of ICML 2023.
- Lightman, H., et al. (2023). Let’s Verify Step by Step. arXiv preprint arXiv:2305.20050.
- Madaan, A., et al. (2023). Self-Refine: Iterative Refinement with Self-Feedback. Advances in Neural Information Processing Systems (NeurIPS 2023).
- OpenAI. (2024). Learning to Reason with LLMs. OpenAI Technical Blog.
- Skalse, J., et al. (2022). Defining and Characterizing Reward Hacking. Advances in Neural Information Processing Systems (NeurIPS 2022).
- Snell, C., et al. (2024). Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters. arXiv preprint arXiv:2408.03314.
- Wang, X., et al. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. Proceedings of ICLR 2023.
- Wei, J., et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. Advances in Neural Information Processing Systems (NeurIPS 2022).
- Yao, S., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. Advances in Neural Information Processing Systems (NeurIPS 2023).
- Zelikman, E., et al. (2022). STaR: Bootstrapping Reasoning With Reasoning. Advances in Neural Information Processing Systems (NeurIPS 2022).