ArXiv: 2408.03314

🎯 Pitch

On problems that a smaller LLM can occasionally solve, test-time compute optimally allocated can match a model over ten times larger—yet on questions far beyond its reach, extra thinking backfires. A 2x efficiency gain isn't from better methods alone, but from adaptively matching the strategy to the prompt's difficulty tier.

1. Executive Summary

This paper systematically analyzes how to optimally allocate a fixed test-time computation budget for LLMs on challenging reasoning prompts, studying two primary mechanisms — searching against process-based verifier reward models (beam search vs. best-of-N sampling) and adaptively updating the model's proposal distribution through iterative revisions (sequential refinement vs. parallel generation) — on the MATH benchmark using PaLM 2-S* models. The core contribution is a compute-optimal scaling strategy that selects the best test-time method per prompt based on estimated difficulty, yielding more than 4× improved efficiency over a best-of-N baseline (matching 256-generation performance with only 64 generations in both the search and revision settings). In a FLOPs-matched evaluation, the authors demonstrate that on easy-to-medium difficulty problems, a smaller model augmented with compute-optimal test-time compute can outperform a ~14× larger pretrained model, establishing that test-time and pretraining compute are not uniformly exchangeable — test-time compute amplifies performance more effectively than scaling parameters only when problems fall within the base model's existing capability range.

2. Context and Motivation

The Core Problem: We Don't Know How to Spend Inference Compute Wisely

The fundamental question this paper tackles is deceptively simple: if an LLM is allowed to use a fixed but non-trivial amount of inference-time computation, how much can it improve its performance on a challenging prompt? This matters because, unlike pretraining — where scaling laws are relatively well-understood thanks to work like Chinchilla (Hoffmann et al., 2022) — the scaling behavior of test-time computation is poorly characterized. Prior to this work, there was no systematic understanding of which test-time strategy works best when, or how test-time compute scales compare to simply training a bigger model.

This gap is significant for several practical reasons the authors highlight (Section 1):

  • On-device deployment: If test-time compute can substitute for model size, smaller models could replace datacenter-scale LLMs for certain tasks, running on edge devices or phones with additional inference-time processing. The authors explicitly state the ambition: "if pre-trained model size can be traded off for additional computation during inference, this would enable LLM deployment in use-cases where smaller on-device models could be used in place of datacenter scale LLMs."
  • Self-improvement pipelines: An LLM that can reliably improve its own outputs using extra computation opens the door to automated self-improvement loops that reduce dependence on human supervision. The paper frames this as "a path towards a general self-improvement algorithm that can function with reduced human supervision."
  • Resource allocation decisions: Organizations deciding how to split their compute budget between pretraining and inference need principled guidance — this paper provides some of the first empirical evidence for that tradeoff. The abstract framing is direct: "if an LLM is allowed to use a fixed but non-trivial amount of inference-time compute, how much can it improve its performance?"

Conflicting Prior Evidence

The paper is motivated by a genuine contradiction in the literature. On one side, several works show that LLMs can use test-time compute productively — self-critique and debate approaches (Bai et al., 2022; Du et al., 2023; Madaan et al., 2023; Saunders et al., 2022), verifier-guided sampling (Cobbe et al., 2021), and tree-of-thought style search (Yao et al., 2023; Feng et al., 2024). On the other side, other studies paint a much more pessimistic picture: Huang et al. (2023) showed that "large language models cannot self-correct reasoning yet," Stechly et al. (2023) found GPT-4 fails to recognize its own reasoning errors through iterative prompting, and Valmeekam et al. (2023) demonstrated that self-critiquing plans largely doesn't work.

The paper explicitly states that "despite its importance, little research attempted to understand the scaling behaviors of various test-time inference methods. Moreover, current work largely provides negative results for a number of these strategies." This framing is crucial — the authors are not claiming prior work is wrong, but rather that the field has produced confusing, sometimes contradictory findings without a unifying framework to reconcile them.

These conflicting findings are not necessarily contradictory — they likely reflect different methods being applied to different difficulty levels under different conditions — but the field lacked a framework for reconciling them. The paper's central insight, previewed in the introduction, is that the effectiveness of any given test-time strategy is highly dependent on prompt difficulty, which explains why different papers (testing on different distributions of problems) reach opposite conclusions.

Where Existing Approaches Fall Short

The paper identifies specific limitations in prior work along two axes that map to their unified proposer-verifier framework (Section 2):

Best-of-N sampling is the dominant but crude baseline. The most studied approach to test-time compute scaling is best-of-N: generate N complete solutions, score them with a verifier, and pick the best one (Cobbe et al., 2021). The paper acknowledges that "arguably the simplest and most well-studied approach for scaling test-time computation is best-of-N sampling." But this is simple in a way that treats every token of compute identically regardless of the problem — there's no adaptation, no consideration of whether the model's initial answer is close or far from correct. The paper argues: "this approach is not the only way to use test-time compute to improve LLMs. By modifying either the proposal distribution from which responses are obtained... or by altering how the verifier is used... the ability scale test-time compute could be greatly improved."

Self-correction via prompting doesn't work for reasoning. Off-the-shelf LLMs prompted to "check their work" or "revise their answer" show minimal improvement on math reasoning tasks (Huang et al., 2023; Section 6). The paper explicitly acknowledges this: "Simply prompting existing LLMs to correct their own mistakes tends to be largely ineffective for obtaining performance improvements on reasoning problems." This is acknowledged as a capability gap that exists "even in strong proprietary LLMs." To get revisions to work, you need purpose-built fine-tuned models that have been specifically trained on the skill of identifying errors in context and producing corrections.

Process reward models (PRMs) exist but their search-time behavior is unexplored. Lightman et al. (2023) and Wang et al. (2023) introduced PRMs that score individual solution steps rather than just final answers. This opens the door to step-by-step search algorithms — beam search, lookahead search, MCTS — that could theoretically be more efficient than exhaustive parallel sampling. However, prior work had not systematically studied how to search against these verifiers at test time — which algorithm to use, how the choice depends on compute budget, or when search over-optimizes the verifier signal. The paper notes in Section 5 that they specifically "study different approaches for performing test-time search with process verifiers (PRMs) and analyze the test-time compute scaling properties of these different approaches."

No unified analysis framework. Perhaps most critically, prior work studied these mechanisms (verifiers, revisions, search algorithms) in isolation. There was no framework for comparing them on equal footing, understanding their complementary strengths, or combining them adaptively. The paper's Section 2 constructs this framework explicitly: "First, we view the use of additional test-time compute through the lens of modifying the model's predicted distribution adaptively at test-time, conditioned on a given prompt." This decomposition — modifying the proposal distribution vs. optimizing the verifier — provides the intellectual architecture for the entire paper.

The RL and inference-tradeoff literature has not addressed language models. The paper acknowledges prior work on training-inference compute tradeoffs that largely focused on board games (Jones, 2021, studying Monte-Carlo tree search applied to Hex) or settings where ground-truth answers are known during inference (Villalobos and Atkinson, 2023). The authors note that "much of their language-model analysis focused on test-time compute scaling in settings where the ground-truth answer is known. In contrast, our analysis focuses on the setting when the ground-truth answer is not known." This is a crucial distinction — the realistic deployment setting has no oracle answer checker, which means verifiers and difficulty estimators must operate without ground truth.

How This Paper Positions Itself

The paper frames all test-time compute methods through a unifying lens described in Section 2: any approach modifies the LLM's output distribution through either (1) changes to the proposal distribution (what the model generates — e.g., by conditioning on previous attempts via revisions) or (2) changes to how outputs are selected/verified (scoring and filtering generated candidates — e.g., via PRM search). The analogy is explicitly to MCMC sampling (Andrieu et al., 2003), where a simple proposal distribution is combined with a score function to sample from a more complex target distribution. Modifying the proposal distribution directly and using a verifier "form two independent axes of our study."

Within this framework, the paper's position is not to propose a single new method, but rather to provide the first systematic scaling analysis of representative methods from each axis — revisions for the proposal distribution (Section 6), PRM-guided search for the verifier (Section 5) — and then show that adaptive, difficulty-aware allocation (what they call "compute-optimal scaling") is the key missing ingredient. The paper draws a direct parallel to compute-optimal pretraining scaling laws (Hoffmann et al., 2022) but applied at inference time, filling a gap that the authors argue is equally important for the future of LLM deployment.

The paper also explicitly positions itself relative to the training-inference tradeoff literature. While prior work in this area (Jones, 2021; Villalobos and Atkinson, 2023; Sardana and Frankle, 2023) explored whether inference compute could substitute for training compute, the paper argues these analyses either (a) operated in domains very different from language model math reasoning (e.g., board games), or (b) assumed access to ground-truth answers during inference. The paper's FLOPs-matched analysis (Section 7) operates in the realistic setting where the correct answer is unknown, making the comparison more practically relevant and, as they frame it, presenting "for the first time that using test-time computation with seemingly simple methods (i.e., revisions and search) can already scale well on certain types of prompts, providing gains over spending those FLOPs in pretraining."

A subtle but important positioning: the paper does not claim test-time compute can universally replace pretraining. Instead, they establish sharp boundary conditions — it works on easy-to-medium problems that are within the base model's capability range, and fails on hard problems where the base model has near-zero pass@1. This careful, condition-dependent claim distinguishes the paper from more sweeping arguments about inference-time scaling and reflects a more mature empirical approach.

The Need for Capability-Specific Fine-Tuning

An important methodological motivation the paper addresses upfront is why fine-tuning is necessary. The authors acknowledge that verification and revision capabilities "are absent even in strong proprietary LLMs" and therefore "in order to make progress towards understanding scaling of test-time computation, we must use models finetuned for these capabilities." This is not presented as a limitation but as a practical necessity — to study how test-time compute could scale if models had these capabilities, you first need models that actually possess them. The paper expresses the expectation that "future LLMs will be more effective at verification and revision due to both increased scale and the inclusion of additional data targeted specifically towards these capabilities" and "future models to be pretrained for such capabilities directly, therefore avoiding the need for capability-specific finetuning." This positions the work as studying a frontier that will become more naturally accessible as base models improve, rather than as an artifact of the specific models used.

3. Technical Approach

3.1 Reader Orientation

The paper constructs a system for deciding how to spend a fixed budget of test-time computation on a given math problem so that a language model produces the correct answer as often as possible. The core idea is that no single test-time strategy — whether searching against a verifier or iteratively revising answers — dominates across all problems; instead, the paper develops a compute-optimal scaling policy that estimates each prompt's difficulty and then selects the best combination of search algorithm, revision depth, and parallel sampling ratio accordingly.

3.2 Big-Picture Architecture (Diagram in Words)

The system has five major components, each with a distinct responsibility in the pipeline from raw prompt to final answer:

  1. Base LLM (PaLM 2-S*) — The pretrained language model that generates candidate solutions. It serves as the "proposal distribution" from which all answers originate, whether those answers are generated in parallel, sequentially, or as steps in a search tree.

  2. Process Reward Model (PRM) — A learned verifier fine-tuned from the same base model that scores every intermediate step of a solution, producing a value estimate between 0 and 1 representing the probability that a correct final answer can be reached from that partial solution. Used to guide search and select answers.

  3. Revision Model — A separately fine-tuned variant of the base LLM that takes its own previous (incorrect) answers as context and produces improved answers sequentially. This model learns to identify errors in in-context examples and make targeted corrections.

  4. Search Algorithms — Procedures (best-of-N, beam search, lookahead search) that use the PRM's step-level scores to navigate the space of possible solutions at test time, deciding which partial solutions to expand and which to prune.

  5. Compute-Optimal Allocation Policy — A meta-strategy that, given an estimate of the prompt's difficulty (from one of five bins) and a compute budget (measured in number of generations), selects which search algorithm and which sequential-to-parallel sampling ratio to deploy.

Information flows as follows: a prompt enters the system → the difficulty estimator bins it into one of five difficulty levels using either ground-truth pass@1 (oracle) or the PRM's average final-answer score (predicted) → the allocation policy looks up the pre-computed best strategy for that difficulty-budget pair → the base LLM or revision model generates candidate solutions under those hyperparameters → the PRM or revision-specific ORM scores the candidates → an aggregation procedure (best-of-N weighted selection or majority voting) selects the final answer.

3.3 Roadmap for the Deep Dive

  • First, the formal compute-optimal objective (Equation 1), which defines what "optimal" means and why difficulty is the key conditioning variable rather than optimizing strategy per individual prompt.
  • Second, the difficulty estimation mechanism, since it is the linchpin that enables adaptive allocation and is shared across both the search and revision pipelines — without it, the entire compute-optimal framework collapses to a uniform baseline.
  • Third, the PRM verifier — how it is trained using Monte Carlo rollouts without human labels, how it scores solutions step-by-step, and how per-step scores are aggregated into a final answer score — since all search methods depend on this component.
  • Fourth, the three search algorithms (best-of-N weighted, beam search, lookahead search), their precise mechanics including the beam expansion and pruning procedure, their cost model in terms of generation budget, and their difficulty-dependent behavior.
  • Fifth, the revision model — how training data is constructed by pairing incorrect answers with correct answers using edit distance as a heuristic for correlation, how sequential revisions are generated at inference time, and how sequential and parallel sampling are combined through hierarchical verifier selection.
  • Sixth, the FLOPs-matched comparison framework that enables the pretraining-vs-inference tradeoff analysis, including the precise FLOPs accounting formula and the role of the inference-to-pretraining token ratio $R$.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily an empirical analysis paper whose core idea is that the optimal way to allocate test-time compute is prompt-dependent, and that a difficulty-conditioned allocation policy can recover large efficiency gains over uniform strategies like best-of-N. The paper does not propose a single new method but rather studies how existing mechanisms — search against verifiers and iterative revisions — scale as a function of compute budget and problem difficulty, then uses this understanding to construct adaptive policies.

The Compute-Optimal Objective

The paper formalizes the test-time compute allocation problem as an optimization over strategy hyperparameters (Section 3.1). The goal is to select, for a specific prompt, the test-time strategy that maximizes the probability of producing the correct answer given a fixed generation budget.

Let $q$ be a prompt (a specific math question), let $y^*(q)$ be the ground-truth correct answer for that prompt, let $N$ be the total compute budget measured in number of generations (complete sampled answers from the base LLM), and let $\theta$ be a vector of hyperparameters that determines how that budget is spent. The hyperparameters $\theta$ capture choices such as: which search algorithm to use (best-of-N, beam search with a specific beam width $M$, or lookahead search with $k$ lookahead steps), or for revisions, what ratio of the budget to allocate to sequential revisions versus parallel sampling.

Define $\text{Target}(\theta, N, q)$ as the distribution over natural language output tokens induced by the model under strategy $\theta$ with budget $N$ on prompt $q$. This target distribution is not the base model's raw output distribution — it is the distribution that results after applying the test-time compute strategy, which may involve generation, pruning, revision, and verifier-based selection.

The compute-optimal strategy is then defined as:

θq,y∗(q)∗(N)=arg⁡max⁡θ(Ey∼Target(θ,N,q)[1y=y∗(q)])\theta^*_{q, y^*(q)}(N) = \arg\max_\theta \left( \mathbb{E}_{y \sim \text{Target}(\theta, N, q)} \left[ \mathbb{1}_{y = y^*(q)} \right] \right)

where $\theta^*_{q, y^*(q)}(N)$ is the optimal hyperparameter configuration for prompt $q$ at budget $N$, the expectation $\mathbb{E}_{y \sim \text{Target}(\theta, N, q)}[\cdot]$ is taken over outputs $y$ sampled from the target distribution induced by strategy $\theta$, and $\mathbb{1}_{y = y^*(q)}$ is the indicator function that returns 1 if $y$ matches the ground-truth answer and 0 otherwise.

What it computes: For a given prompt $q$ and a fixed total generation budget $N$, the equation selects the strategy hyperparameters $\theta$ that maximize the expected accuracy — the probability that the final selected answer equals the ground-truth correct answer. Since the expectation is over outputs from the target distribution (which incorporates all the test-time processing), this is effectively asking: among all possible ways to spend $N$ generations on this prompt (beam search vs. best-of-N, sequential vs. parallel, various beam widths and lookahead depths), which one gives the highest chance of producing the right answer?

Why this form: The key insight is that $\theta^*$ is subscripted with $q$ and $y^*(q)$ — it depends on the specific prompt and its correct answer. This formalizes the intuition that no single universal strategy is optimal for all prompts. A strategy that works best on easy problems (e.g., purely sequential revisions because the initial answer is close to correct and just needs refinement) may be suboptimal on hard problems (where broad parallel search over different high-level approaches is needed). The optimization is over a discrete, combinatorial space of strategy hyperparameters rather than continuous parameters, which means the paper approximates this by conditioning on a sufficient statistic — the estimated difficulty of the prompt.

The paper explicitly states that "the compute-optimal strategy is defined as a function of the difficulty of this prompt. Despite being only an approximate solution to the problem shown in Equation 1, we find that it can still induce substantial improvements in performance over a baseline strategy of allocating this inference-time compute in an ad-hoc or uniformly-sampled manner." The approximation replaces the per-prompt optimization with a per-difficulty-bin optimization: find the best $\theta$ averaged across all prompts in a given difficulty quintile, rather than for each prompt individually. This is a coarser approximation than the ideal, but it is practical and the cross-validation results show it works well.

Difficulty Estimation: The Oracle and Predicted Bins

The difficulty of a prompt is defined relative to the base LLM's capabilities, not the MATH dataset's hand-labeled difficulty levels (e.g., Level 1 through 5 from the original Hendrycks et al. benchmark). The paper explicitly states that their notion of "model-specific difficulty bins" was "more predictive of the efficacy of using test-time compute in contrast to the hand-labeled difficulty bins in the MATH dataset." This is because test-time compute amplifies what the model already knows — a problem that is hard for one model may be easy for another, and the relevant question for strategy selection is whether the base model can produce reasonable answers at all.

The paper defines two versions of difficulty estimation: one that requires ground-truth labels (oracle) and one that does not (predicted).

Oracle difficulty. For each question in the test set, the authors sample 2048 complete solutions from the base LLM, check each one against the ground-truth correct answer, and compute the pass@1 rate — the fraction of those 2048 solutions that are correct. They then sort all 500 test questions by this pass@1 rate and bin them into five quintiles (each containing approximately 100 questions). Quintile 1 contains the easiest questions (highest pass@1 — the model gets them right frequently even with random sampling), and quintile 5 contains the hardest (lowest pass@1 — the model almost never produces the correct answer without assistance). This requires knowing which answers are correct, hence "oracle" — it assumes access to the ground-truth correctness function $\mathbb{1}_{y = y^*(q)}$ for all 2048 samples per question.

Predicted (model-based) difficulty. Since oracle difficulty requires ground-truth labels unavailable at deployment, the paper approximates it by replacing the ground-truth correctness check with the PRM's final-answer score. Specifically, for each question, they sample the same 2048 solutions from the base LLM, but instead of checking against the ground-truth answer, they average the PRM's predicted final-answer correctness score (a scalar between 0 and 1) across all 2048 samples. They then sort by this average score and bin into five quintiles using the identical procedure. This removes the need for ground-truth labels — the PRM itself provides a proxy for "how likely is the model to answer this correctly" — but it still requires the computational cost of generating 2048 samples and scoring them.

The authors explicitly acknowledge this cost (Section 3.2): "estimating difficulty in this way still incurs additional computation cost during inference." They frame this as an exploration-exploitation tradeoff — compute spent assessing difficulty versus compute spent solving the problem — and flag it as a key avenue for future work. They also note that "our experiments do not account for this cost largely for simplicity, since our goal is to present some of the first results of what is in fact possible by effectively allocating test-time compute." This means the reported efficiency gains (e.g., 4× over best-of-N) do not include the 2048-generation difficulty estimation cost, which could dominate the actual budget. In a practical deployment, one would need to amortize this cost across many uses of the same difficulty estimates or develop a cheaper difficulty predictor.

A subtle point about the binning granularity: The paper uses exactly five difficulty bins (quintiles of the 500-question test set). This is a coarse discretization — within a single bin, questions at the top and bottom may have meaningfully different optimal strategies, but they receive identical treatment. The choice of five bins balances granularity (more bins would give finer-grained allocation but less statistical power for estimating the optimal strategy per bin) against data constraints (with ~50 questions per bin per cross-validation fold, finer bins would make strategy selection unreliable). The paper does not conduct an ablation over the number of bins.

Cross-validation protocol. To avoid the circularity of selecting the best strategy and evaluating it on the same data, the paper uses two-fold cross-validation within each difficulty bin on the 500-question test set. Concretely, they split the questions in each difficulty bin into two folds (roughly 50 questions each). They select the best-performing strategy (e.g., which beam width, which sequential-to-parallel ratio) based on performance on fold 1, then evaluate that strategy on fold 2, and vice versa. The final reported accuracy is the average across both test folds. This ensures that the strategy selection procedure cannot overfit to specific test questions — the strategy evaluated on each fold was chosen using a different set of questions.

The sufficient statistic interpretation. The paper frames difficulty bins as "a sufficient statistic of a question when designing the compute-optimal strategy." In statistical terms, this means that once you know a question's difficulty bin, the optimal strategy does not depend on any other properties of the question (or at least, conditioning on additional properties provides negligible additional benefit). This is an assumption — not proven but empirically validated by the fact that the bin-conditioned strategies substantially outperform uniform baselines. If difficulty were not a sufficient statistic (e.g., if two questions in the same difficulty bin required qualitatively different strategies), the compute-optimal policy would underperform.

Process Reward Model (PRM) Training and Usage

The PRM is the central verifier component. Unlike an Outcome Reward Model (ORM) that assigns a single correctness score to a complete solution, a PRM assigns a score to each intermediate step in a solution. These per-step scores represent the model's estimate of the probability that a correct final answer can be reached from the current partial solution — essentially a value function or reward-to-go estimate for the base model's sampling policy.

Why avoid human labels. Prior PRM training (Lightman et al., 2023; Uesato et al., 2022) used human crowd-workers to label each step as correct or incorrect. The PRM800k dataset released by Lightman et al. contains GPT-4 generated solutions with human step-level labels. The authors found this data to be "largely ineffective" for their PaLM 2 models. They state: "We found that it was easy to exploit a PRM trained on this dataset via even naïve strategies such as best-of-N sampling. We hypothesize that this is likely a result of the distribution shift between the GPT-4 generated samples in their dataset and our PaLM 2 models." This is a critical practical finding: verifier training data must come from the same model that will be used at test time, otherwise the verifier learns features that do not transfer and can be exploited by search algorithms optimized against the verifier's (misaligned) signal.

Monte Carlo rollout supervision. Instead of human labels, the authors follow the approach of Wang et al. (2023) and use Monte Carlo rollout supervision to produce per-step correctness estimates automatically. The procedure works as follows:

  1. For each question in the training set (12,000 MATH training questions), sample 16 solutions from the few-shot prompted base LLM. Each solution is output in a step-by-step format enforced by the prompt (solutions are separated into steps by newline splitting).

  2. For each individual step in each of these 16 solutions, sample 16 Monte Carlo rollouts. A rollout means: starting from that step as a prefix, continue generating tokens autoregressively from the same base LLM until the end of the solution is reached (the model outputs a final answer or the maximum length is exceeded). The temperature used for these rollouts is not explicitly stated but likely matches the training data generation temperature.

  3. For each step, compute the fraction of its 16 rollouts that reach the correct final answer. This fraction — a number between 0 and 1 — becomes the soft label (training target) for that step. If a step's rollouts almost always lead to the right answer, it gets a label close to 1. If they rarely do, it gets a label close to 0. Intermediate values (e.g., 0.5) indicate genuine uncertainty — sometimes the model recovers from that step, sometimes it doesn't.

  4. Fine-tune the base LLM as a binary classifier that predicts a scalar value $\hat{y} \in [0, 1]$ at each step. The model is trained to minimize the binary cross-entropy between its predictions and the soft rollout-derived labels:

L=−(ylog⁡(y^)+(1−y)log⁡(1−y^))\mathcal{L} = -\left(y \log(\hat{y}) + (1 - y) \log(1 - \hat{y})\right)

where $y \in [0, 1]$ is the soft target from Monte Carlo rollouts (the empirical fraction of rollouts that reach the correct answer from that step) and $\hat{y} \in [0, 1]$ is the model's predicted value for the step.

What it computes: This loss penalizes the model when its predicted probability $\hat{y}$ diverges from the empirical success rate $y$. If $y$ is high (the step reliably leads to correct answers) but the model predicts a low probability $\hat{y}$, the term $-y\log\hat{y}$ produces a large loss. Conversely, if $y$ is low but the model is overconfident (high $\hat{y}$), the term $-(1-y)\log(1-\hat{y})$ produces a large loss. The loss is computed per step and summed across all steps in all training solutions.

Why this form: Binary cross-entropy with soft labels is the standard maximum-likelihood objective for a Bernoulli target where the target is itself a probability rather than a hard 0/1 label. This is important because the rollout-derived labels are empirical frequencies — they carry uncertainty information (a label of 0.5 means "50% of rollouts succeeded," which is different from a label of 0 or 1). Using hard binary labels (thresholding at 0.5) would discard this uncertainty signal. Mean squared error, by contrast, would weight calibration errors near 0.5 equally to errors near 0 or 1, which is the wrong inductive bias — a prediction of 0.9 when the true probability is 0.99 is a much more severe miscalibration than 0.55 vs 0.5, and binary cross-entropy captures this through its asymmetry.

Training hyperparameters. The PRM is fine-tuned from the PaLM 2-S* base model using the AdamW optimizer with learning rate $3 \times 10^{-5}$, batch size 128, dropout 0.05, and Adam betas $(0.9, 0.95)$. Early stopping is based on validation loss on a random 10% held-out split of the PRM800k training questions. The authors filter out all training samples that fail to output a valid, parsable final answer because "we found these to hurt PRM performance in initial experiments."

A critical property of the soft labels. The PRM's per-step predictions correspond to value estimates of reward-to-go for the base model's sampling policy. This means the PRM is not evaluating whether a step is "objectively correct" in some mathematical sense — it is evaluating the probability that the base model, continuing to sample from its own distribution, will produce the correct answer given this prefix. This is a subtle but important distinction: the PRM is a policy-dependent value function, not an absolute correctness oracle. If the base model has systematic biases or blind spots, the PRM's value estimates will reflect those. This has implications for search: optimizing against the PRM is optimizing against the base model's own estimate of answer quality, which may diverge from true correctness.

Step-wise score aggregation. Given a complete solution with per-step PRM scores, the system needs a single scalar score for the whole solution to compare candidates. The paper compares three aggregation methods (Appendix E):

  • "min": Take the minimum PRM score across all steps. This is the method used in Lightman et al. (2023) and Wang et al. (2023), motivated by the intuition that a solution is only as strong as its weakest step — if any step has a low probability of leading to the correct answer, the whole solution is suspect.
  • "prod": Take the product of per-step correctness probabilities (treating each step's correctness as conditionally independent). This computes $\prod_i \text{PRM}(\text{step}_i)$.
  • "last": Use only the PRM's prediction at the final step of the solution. This ignores all intermediate step scores entirely and treats the PRM like an ORM — only the final assessment matters.

Contrary to prior work (Lightman et al., 2023; Wang et al., 2023) which found "min" to be the best aggregation strategy, this paper finds "last" performs best (Figure 13). The authors hypothesize that "the discrepancy is due to the fact that our verifier was trained with soft MC return labels, which surface very differently from binary correctness labels, and therefore other aggregation strategies may not have the same effect." With soft labels, the per-step scores have different calibration properties — a step might have a "low" score simply because the base model is uncertain, not because the step is objectively wrong.

An interesting consequence: using the last-step prediction effectively makes the PRM behave like an ORM at aggregation time (you only look at the final step's score). Yet the PRM still outperforms a separately trained ORM (Figure 14, Appendix F). The authors' interpretation is that "per-step PRM training may be largely useful as a form of representation learning" — the model learns better internal representations by being forced to predict correctness at every intermediate step, even if at test time only the final prediction is used. The intermediate-step supervision acts as a dense training signal that improves the quality of the features the model develops, benefiting the final-step prediction as a side effect.

Inter-answer aggregation (best-of-N weighted). When selecting among $N$ complete candidate solutions, the paper does not simply pick the one with the highest PRM score. Instead, following Li et al. (2023), it uses best-of-N weighted selection: all solutions that arrive at the same final answer (as determined by string matching after parsing) have their PRM scores (from last-step aggregation) summed together, and the final answer with the greatest total sum is selected. This is more robust than picking the single highest-scoring solution because it incorporates a form of consensus — if many solutions agree on an answer, their scores accumulate even if no single one is the top scorer. The intuition is that a correct answer may be reached via many different reasoning paths (each with moderate but not extreme scores), while an incorrect answer might have one highly-scoring but misleading solution. Best-of-N weighted downweights the latter by requiring consensus.

Search Algorithms Against the PRM

The paper studies three search methods that use the PRM to navigate the space of possible solutions at test time. All three sample outputs from a few-shot prompted base LLM (the same PaLM 2-S* model, prompted with 4 randomly selected correct answer examples from PRM800k to enforce step-by-step formatting). Figure 2 in the paper provides an illustration of the three approaches.

Best-of-N weighted. This is the simplest baseline: sample $N$ complete solutions independently from the base LLM (each solution is generated from scratch without conditioning on any other solution), score each with the PRM using last-step aggregation, and apply best-of-N weighted selection to pick the final answer. The generation budget equals $N$ — there are exactly $N$ complete generations. There is no interaction between the solutions during generation; they are all produced independently in parallel.

Beam search. This is a step-by-step search algorithm that prunes unpromising partial solutions at each step, concentrating the generation budget on the most promising prefixes. The algorithm is similar to BFS-V (Feng et al., 2024; Yao et al., 2023). The procedure uses two parameters: the total number of beams $N$ (the generation budget — analogous to the number of parallel samples in best-of-N) and the beam width $M$ (the branching factor — how many next-step proposals are generated from each surviving beam). The algorithm operates as follows:

  1. Initial step: Sample $N$ candidate first steps from the base LLM (each is the beginning of a solution — the first reasoning step). These $N$ candidates are sampled independently.

  2. Scoring: For each candidate first step, compute the PRM's predicted step-wise reward-to-go estimate. This is a scalar between 0 and 1 representing the PRM's estimate of the probability that a correct answer can be reached from this prefix. Since the reward is sparse (only the final answer correctness matters), this per-step estimate also corresponds to the total expected reward from the prefix.

  3. Pruning: Keep only the top $N/M$ highest-scoring steps. The rest are discarded. This means if $N = 256$ and $M = 4$, you keep only the top $256/4 = 64$ steps. The beam width $M$ controls how aggressively you prune — a larger $M$ means more candidates survive each round but fewer next-step proposals per candidate.

  4. Expansion: From each of the surviving $N/M$ candidate prefixes, sample $M$ proposals for the next step in the solution. This produces $(N/M) \times M = N$ candidate prefixes again (each now two steps long). This maintains a constant total number of active candidates at each step, equal to the generation budget $N$.

  5. Repeat: Return to step 2 with the expanded prefixes. Score them, prune to keep the top $N/M$, expand each with $M$ proposals, and continue.

  6. Termination: The algorithm runs until each beam reaches the end of a solution (the model outputs a final answer) or a maximum of 40 rounds of beam expansion are reached. At the end, there are $N$ completed solutions (or as many as were generated before hitting the cap). Apply best-of-N weighted selection to these $N$ completed solutions to pick the final answer.

The paper sweeps two beam width settings: $M = \sqrt{N}$ (where the beam width grows with the total budget — at $N = 64$, $M = 8$; at $N = 256$, $M = 16$) and $M = 4$ (fixed regardless of budget). With $M = \sqrt{N}$, the number of surviving beams $N/M = \sqrt{N}$ also grows with budget, so more distinct prefixes are explored in parallel at each step. With $M = 4$, the number of surviving beams is $N/4$, which grows linearly with $N$, so at higher budgets many more distinct prefixes are maintained.

Why beam search might help: The key difference from best-of-N is that beam search interleaves generation and pruning. Best-of-N generates all $N$ solutions independently and only scores them at the end — if a solution goes off-track at step 2, it still consumes a full generation budget producing an incorrect answer. Beam search, by contrast, identifies promising prefixes early and allocates more generations to extending them, abandoning unpromising directions before they consume a full solution's worth of generation. The price is that beam search is more reliant on the PRM's accuracy — if the PRM incorrectly prunes a prefix that would have led to the correct answer, that answer is lost forever.

Lookahead search. This modifies beam search by improving the accuracy of step-level scoring at the cost of additional computation. In standard beam search, the PRM's score for a given step is computed based only on that step's prefix. But the quality of a prefix may not be fully apparent from its immediate content — sometimes a step looks fine but leads to a dead end, or looks suspicious but recovers. Lookahead search addresses this by simulating forward before deciding which prefixes to keep.

Specifically, at each step in the beam search, instead of using the PRM score at the current step to select the top candidates, lookahead search performs a rollout: it generates up to $k$ additional steps forward from the current prefix (using the base LLM at temperature 0 to minimize variance in the simulation), and then uses the PRM's prediction at the end of this rollout as the score for the current step. The intuition is that the PRM has more information at the end of the rollout — it can see whether the next few steps are coherent, whether the reasoning is converging, or whether it's going off the rails — and this additional context makes its assessment more accurate.

The authors note that this is a special case of Monte Carlo Tree Search (MCTS) with the stochastic exploration elements removed. Standard MCTS (Kocsis and Szepesvári, 2006) uses stochastic rollouts and exploration bonuses (like UCB) because it needs to simultaneously learn the value function (through tree expansion) and exploit the best-known actions. Here, the value function is already learned (the PRM is frozen and trained offline), so the exploration elements are unnecessary — at test time, the goal is pure exploitation. Lookahead search is therefore "largely representative of how MCTS-style methods would be applied at test-time."

Cost model for lookahead search. The cost is higher than beam search because each step evaluation requires $k$ additional generation steps. The paper defines the cost of lookahead search with $k$ lookahead steps as $N \times (k + 1)$ generations — the $N$ beams each require a $k$-step rollout plus the actual step generation. For a fair comparison at a given total generation budget, lookahead search must therefore explore fewer beams than standard beam search. For example, at a budget of 256 generations with $k = 3$, the effective number of beams explored is only $256 / 4 = 64$.

The paper sweeps the following specific configurations with a maximum budget of 256 generations:

  • Beam search with $M = \sqrt{N}$
  • Beam search with $M = 4$
  • Lookahead search with $k = 3$ applied to both beam width settings
  • Lookahead search with $k = 1$ applied to $M = \sqrt{N}$

These sweeps are described as not "extensively sweeping every single configuration" — the authors acknowledge this is not an exhaustive search over all possible $(M, k)$ combinations, but rather a representative set intended to reveal qualitative trends in how search algorithm sophistication interacts with compute budget and problem difficulty.

Key results that motivated the compute-optimal search policy. The paper's search analysis (Section 5.3) found a non-obvious pattern: beam search significantly outperforms best-of-N at low generation budgets, but its advantage diminishes and sometimes reverses at high budgets. The explanation is PRM over-optimization — beam search, as the stronger optimizer, finds solutions that score highly under the PRM but are actually incorrect. Specific failure modes include low-information repetitive steps at the end of solutions (visible in Figure 29 where the model repeatedly states "The answer is 10" with slight variations) and overly short 1–2 step solutions. This explains why lookahead search — the most powerful optimizer — paradoxically underperforms the most: it over-optimizes the PRM most aggressively.

When broken out by difficulty (Figure 3, right), a clear pattern emerges:

  • On easy questions (bins 1–2), beam search degrades performance with increasing budget — a hallmark of verifier exploitation, since the PRM makes mostly correct assessments and aggressive optimization amplifies any residual errors.
  • On medium questions (bins 3–4), beam search consistently outperforms best-of-N — the PRM's guidance genuinely helps navigate toward correct solutions the model wouldn't find by random sampling alone.
  • On the hardest questions (bin 5), no method makes meaningful progress — the base model simply lacks the capability to produce correct solutions regardless of how the budget is allocated.

This difficulty-dependence is what motivates the compute-optimal allocation for search: use best-of-N on easy problems (to avoid over-optimization) and beam search on medium-hard problems (where the PRM provides genuine guidance), adapting per-question based on estimated difficulty.

The Revision Model: Training and Inference

Rather than relying solely on the verifier to select among independently generated solutions, the paper also studies modifying the proposal distribution itself so that the model generates better candidates in the first place. The mechanism is iterative revision: the model conditions on its own previous (incorrect) answers as context and produces an improved answer sequentially. The paper builds on the recipe of Qu et al. (2024) but introduces crucial modifications for practicality.

Why fine-tuning is necessary. The paper explicitly acknowledges that prompting off-the-shelf LLMs to self-correct on reasoning tasks is "largely ineffective" (citing Huang et al., 2023). The reason is that standard pretrained LMs have not been trained to identify errors in their own outputs in context and produce targeted corrections — when prompted to "revise your answer," they tend to either produce a completely new answer that may share similar errors, or make superficial word-level changes without fixing the underlying reasoning mistake. To make revisions work, the model must be fine-tuned specifically on the skill of revising: seeing an incorrect answer in context, identifying what went wrong, and producing a corrected answer that fixes the specific mistake while preserving correct reasoning.

Training data generation. The procedure builds on Qu et al. (2024) but with a critical difference in how data is collected. The goal is to produce multi-turn training trajectories where each trajectory consists of a sequence of incorrect answers followed by a correct answer, and the model is trained (via SFT) to predict only the correct answer tokens given the incorrect answers as context.

The paper's data generation procedure (Section 6.1) works as follows:

  1. For each question in the MATH training set, sample 64 responses in parallel from the base LLM at elevated temperature (higher than the default sampling temperature, to encourage diversity). These are complete solutions — each is a full answer from start to finish.

  2. Identify which of these 64 responses are correct and which are incorrect (using the ground-truth answer for training data construction).

  3. For each correct answer, construct a multi-turn training sequence by selecting a sequence of incorrect answers to include in context. The number of incorrect answers in context is sampled uniformly from {0, 1, 2, 3, 4}. Including sequences with 0 incorrect answers means the model is also trained on standard single-turn answer generation, which prevents catastrophic forgetting.

  4. The last incorrect answer in the context sequence (the one immediately preceding the correct target answer) is selected to be the one with the smallest character-level edit distance to the correct answer among the available incorrect answers. The intuition is that this incorrect answer is "close" to the correct one — similar in structure and reasoning approach but containing a specific mistake. This ensures the model learns to make targeted edits (fixing the specific error) rather than ignoring the context and starting from scratch. The remaining incorrect answers in the sequence are sampled randomly from the other incorrect answers.

  5. Fine-tune the base LLM with supervised fine-tuning (SFT) on these trajectories, training only on the correct answer tokens (the incorrect in-context answers do not contribute to the loss). The model learns to produce the correct answer given the problem and the sequence of incorrect attempts.

Why edit distance as a heuristic? The paper explicitly states: "Note that token edit distance is not a perfect measure of correlation, but we found this heuristic to be sufficient to correlate incorrect in-context answers with correct target answers to facilitate training a meaningful revision model, as opposed to randomly pairing incorrect and correct responses with uncorrelated responses." The idea is that if the incorrect answer is structurally similar to the correct one (e.g., same approach but wrong arithmetic at one step), the model can learn the revision skill of "identify where the previous answer went wrong and fix that specific part." If the incorrect answer were completely unrelated (a totally different solving approach), the model would have no signal about what specifically to fix, and might just learn to ignore the context.

A crucial difference from Qu et al. (2024). The original approach in Qu et al. used on-policy multi-turn rollouts: the model would generate an answer, receive feedback (whether it was correct or not), generate a revision, receive feedback, and so on, producing a coherent multi-turn trajectory where each revision was genuinely conditioned on the previous attempt. This was "not entirely feasible in our infrastructure due to compute costs associated with running multi-turn rollouts." Instead, the paper approximates the multi-turn structure by post-hoc constructing trajectories from independently sampled solutions, using edit distance as a proxy for trajectory coherence. This is an approximation — the incorrect answers were not actually generated by conditioning on previous incorrect answers — but the edit-distance heuristic makes the pairing non-random, so the in-context examples are at least somewhat related to the target correct answer.

Training hyperparameters (Appendix H). The revision model is fine-tuned from the PaLM 2-S* base model using the AdamW optimizer with learning rate $1 \times 10^{-5}$, batch size 128, dropout 0.0, and Adam betas $(0.9, 0.95)$. A subtle training detail: "we find that generally evaluating loss on an evaluation set consisting of trajectories generated as described above, does not provide a good signal for early stopping." This is because after fine-tuning, the evaluation set represents off-policy data — the trajectories were generated by the base model, not the fine-tuned revision model, so they are out-of-distribution for the fine-tuned model. The authors select the revision model checkpoint "slightly after the point where we observe overfitting on the validation set" — effectively, they use validation loss as a rough guide but intentionally pick a checkpoint that is slightly overtrained on the training data, because the validation set is not representative of the model's own on-policy revision behavior.

Inference with the revision model. At test time, the revision model is used to generate a chain of revisions. The process works as follows:

  1. The model receives the problem prompt and generates an initial answer (with no previous answers in context).

  2. The initial answer is appended to the context. The model then generates a revision — a new answer conditioned on the problem and the previous (first) answer.

  3. This second answer is appended to the context. The model generates a third answer, conditioned on the problem and both previous answers. And so on.

  4. The model was trained with a maximum of 4 previous incorrect answers in context. To support longer chains, the context is truncated to the most recent 4 revised responses — older answers are dropped. This means the model's revision behavior for steps beyond step 4 is an extrapolation beyond its training distribution, but Figure 6 (left) shows it works — pass@1 at each step gradually improves out to 64 steps, demonstrating "we are able to effectively teach the model to learn from mistakes made by previous answers in context."

The correct-to-incorrect reversion problem. A significant practical issue arises from a distribution shift between training and inference. During training, the model only sees sequences where all in-context answers are incorrect (followed by a correct target). At test time, the model may generate a correct answer at some point in the revision chain. This correct answer then appears in the context for the next revision step. Since the model has never seen a correct answer in context during training (and never learned to say "this is already correct, don't change it"), it may incorrectly "revise" the correct answer into an incorrect one in the next step. The paper reports that "around 38% of correct answers get converted back to incorrect ones with our revision model using a naïve approach."

To mitigate this, the system does not simply take the final revision in the chain as the answer. Instead, it uses a selection mechanism across the entire chain: either sequential majority voting (take the most common final answer across all revisions in the chain) or verifier-based selection (score each revision independently with an ORM trained specifically on revision model outputs, and select the highest-scoring one). This way, if a correct answer appears at step 5 but gets reverted to incorrect at step 6, the selection mechanism can still recover it.

The revision-specific ORM (Appendix J). The paper found that "the PRM we finetuned on the PaLM 2-S* base model outputs was not as effective when applied to the PaLM 2-S* revision model's outputs" (Figure 15a). This is due to distribution shift — the revision model produces a different distribution of outputs than the base model, and the PRM trained on base model outputs does not transfer well. Therefore, a separate ORM (not PRM) is trained specifically on the revision model's outputs. The ORM is modified to include previous revisions in context, "such that the verifier has access to the same context as the revision model, allowing the verifier see the revision model's previous answer attempts when scoring the current answer." Including revision history in the ORM's context provides a small improvement (Figure 15b), but even without it, sequential revisions still outperforms parallel sampling, "demonstrating improvements from sequential sampling are not just due to the verifier's context."

Hierarchical aggregation for sequential and parallel combinations. The paper explores strategies that combine sequential revisions and parallel sampling. For a fixed generation budget $N$, the system can allocate some generations to parallel independent chains and the rest to sequential revisions within each chain. For example, with budget $N = 256$, one configuration is 16 parallel chains, each of length 16 (so $16 \times 16 = 256$ total generations). The sequential-to-parallel ratio is $16/1 = 16$, or $2^4$ in the paper's notation.

When using the verifier for selection, the paper deploys a hierarchical strategy: first, select the best answer within each revision chain using best-of-N weighted aggregation (the PRM scores each answer in the chain, and the highest-scoring answer within that chain is chosen as its representative). Then, across the representatives from all chains, perform a second round of best-of-N weighted selection to pick the final answer. For majority voting, the paper found hierarchical aggregation problematic when chain lengths or number of chains are small (not enough samples for reliable majority selection), so they instead take all answers from all chains simultaneously and compute the majority across the entire set.

Why not train a PRM for revisions? The paper uses an ORM rather than a PRM for the revision model because of "the high cost of generating per-step PRM labels" — training a PRM requires Monte Carlo rollouts from each step, which is expensive, and the revision model's outputs add another layer of distribution shift. The ORM is a simpler, cheaper alternative that suffices for answer-level selection.

The ReSTEM^{EM} negative result (Appendix K). The paper attempted to further optimize the revision model using ReSTEM^{EM} (Singh et al., 2024), a simplified RL algorithm: generate 64 revision trajectories of maximum length 5 for each training question, stop at the first correct answer in each trajectory, and fine-tune the base model on the correct answer data from these trajectories. This substantially hurt performance (Figure 16) — additional sequential revisions caused major degradation with this model. The authors hypothesize that "the online data obtained from running ReSTEM exacerbates spurious correlations in revision data, causing the optimized model to fail to learn the revision task." This is a notable negative result: the revision model is fragile, and the precise data collection methodology (offline post-hoc pairing with edit distance vs. online multi-turn rollouts) matters significantly. The paper suggests that "a more offline data collection strategy, as done in Qu et al. [28], may be more effective."

The Compute-Optimal Allocation for Revisions

The paper's revision analysis (Section 6.2) studies the tradeoff between fully sequential and fully parallel generation from the revision model, and finds that the optimal ratio depends on difficulty.

Aggregate sequential vs. parallel comparison (Figure 6, right). At 64 generations, fully sequential revisions (one chain of length 64) marginally outperforms fully parallel sampling (64 independent samples) under both verifier-based selection (approximately 41.5% vs. 39%) and majority voting (approximately 38% vs. 35%). The gap is small but consistent.

Sequential-to-parallel ratio sweep (Figure 7, left). For a fixed generation budget, the authors sweep the ratio of sequential to parallel computation. At a budget of 256 generations, the optimal ratio is around $2^1$ to $2^3$ (2:1 to 8:1 sequential-to-parallel), achieving approximately 43–44% accuracy, compared to about 40% for fully parallel and about 42% for fully sequential. At lower budgets (8–32 generations), fully sequential is optimal — the curves are monotonically increasing with the sequential-to-parallel ratio, meaning that when the total budget is small, every generation should be a revision rather than an independent sample.

Difficulty-dependent ratio (Figure 7, right). At a fixed budget of 128 generations, broken out by difficulty:

  • Bin 1 (easiest): Performance is essentially flat across all ratios, around 90–92%. Easy questions are insensitive to how the budget is allocated — the model gets them right regardless.
  • Bin 2: Slight advantage for higher sequential ratios: approximately 63% at fully sequential vs. 58% at fully parallel.
  • Bin 3: A clear optimal ratio emerges at moderate sequential-to-parallel values (around $2^1$ to $2^3$), reaching approximately 42% vs. 35% at the extremes. The model needs both the diversity of parallel chains (to explore different approaches) and the refinement of sequential revisions (to fix errors within each approach).
  • Bin 4: Similar pattern, with the peak at a moderate ratio achieving roughly 18% vs. 14% at fully parallel.
  • Bin 5: All ratios produce roughly 2–3% accuracy. No allocation strategy helps.

This mirrors the finding from search: easy problems benefit from exploitation (local refinement via revisions), hard problems benefit from a balance of exploration (parallel chains) and exploitation (revisions within chains), and the hardest problems are beyond help regardless of strategy. The intuition is that "sequential revisions may work more as a local refinement process, revising responses that are already somewhat on the right track," while "sampling answers in parallel may act as more of a global search process, that could in principle, provide coverage over many totally different approaches for solving a problem."

FLOPs-Matched Comparison: Pretraining vs. Test-Time Compute

Section 7 establishes a framework for comparing whether additional compute is better spent on pretraining a larger model or on applying test-time compute with a smaller model. The comparison is conducted under a fixed total FLOPs constraint.

FLOP accounting. The paper uses standard approximations from the scaling laws literature (Hoffmann et al., 2022; Sardana and Frankle, 2023). For pretraining:

X=6NDpretrainX = 6 N D_{\text{pretrain}}

For inference:

Y=2NDinferenceY = 2 N D_{\text{inference}}

where $N$ is the number of model parameters, $D_{\text{pretrain}}$ is the number of tokens used for pretraining, and $D_{\text{inference}}$ is the total number of tokens generated at inference time (across all queries for the intended deployment workload).

What these approximate: Pretraining FLOPs $X$ are approximately $6 N D_{\text{pretrain}}$ because each token in the training data requires roughly 6 FLOPs per parameter (3 for the forward pass and 3 for the backward pass, using the standard estimator). Inference FLOPs $Y$ are approximately $2 N D_{\text{inference}}$ because each generated token requires roughly 2 FLOPs per parameter (one forward pass with no backward pass). These are approximations, not exact measurements, but they are standard in the scaling laws literature and sufficient for first-order comparisons.

Why these forms: The factor of 2 vs. 6 captures the fundamental asymmetry between training and inference: training requires both forward and backward passes (≈6N FLOPs per token), while inference requires only a forward pass (≈2N FLOPs per token). This means that for a model of a given size, inference is roughly 3× cheaper per token than training — but the total number of inference tokens can be much larger, depending on the deployment scenario.

The exchange rate derivation. Suppose we have a smaller model with parameters $N$ and a larger model with parameters $M \times N$ (where $M$ is the scaling factor — in the paper's experiments, $M \approx 14$). The larger model's total pretraining FLOPs are:

Xlarge=6(MN)Dpretrain=M⋅6NDpretrain=MXX_{\text{large}} = 6 (M N) D_{\text{pretrain}} = M \cdot 6 N D_{\text{pretrain}} = M X

The larger model's inference FLOPs (for the same total inference tokens $D_{\text{inference}}$) are:

Ylarge=2(MN)Dinference=M⋅2NDinference=MYY_{\text{large}} = 2 (M N) D_{\text{inference}} = M \cdot 2 N D_{\text{inference}} = M Y

So the larger model costs $M(X + Y)$ total FLOPs across pretraining and inference. To match this total with the smaller model, we can spend additional test-time compute on inference. The smaller model's baseline inference FLOPs (greedy decoding) are already $Y = 2 N D_{\text{inference}}$. We can multiply this by a factor $F$ (generating $F$ times more tokens via parallel sampling, beam search, revisions, etc.) to bring the total FLOPs up to the larger model's total:

X+FY=M(X+Y)X + F Y = M (X + Y)

Solving for $F$:

FY=MX+MY−XF Y = M X + M Y - X FY=(M−1)X+MYF Y = (M - 1) X + M Y F=(M−1)XY+MF = \frac{(M - 1) X}{Y} + M

Substituting $X = 6 N D_{\text{pretrain}}$ and $Y = 2 N D_{\text{inference}}$:

F=(M−1)⋅6NDpretrain2NDinference+M=6(M−1)Dpretrain2Dinference+M=3(M−1)DpretrainDinference+MF = \frac{(M - 1) \cdot 6 N D_{\text{pretrain}}}{2 N D_{\text{inference}}} + M = \frac{6 (M - 1) D_{\text{pretrain}}}{2 D_{\text{inference}}} + M = 3 (M - 1) \frac{D_{\text{pretrain}}}{D_{\text{inference}}} + M

The inference compute multiplier for the smaller model (compared to greedy decoding) that matches the larger model's total FLOPs is therefore:

F=M+3(DpretrainDinference)⋅(M−1)F = M + 3 \left(\frac{D_{\text{pretrain}}}{D_{\text{inference}}}\right) \cdot (M - 1)

What this equation computes: Given the ratio of pretraining to inference tokens $D_{\text{pretrain}} / D_{\text{inference}}$ and the parameter scaling factor $M$, this gives the factor by which the smaller model's inference compute can be multiplied (through additional test-time strategies) while still matching the total FLOPs of the $M \times$ larger model. The first term $M$ accounts for the larger model's proportionally higher per-token inference cost. The second term $3 (D_{\text{pretrain}} / D_{\text{inference}}) (M - 1)$ accounts for the pretraining FLOPs savings from using the smaller model — the pretraining savings are proportional to $(M - 1)$ (how much smaller the model is), scaled by the pretraining-to-inference token ratio. When $D_{\text{pretrain}} / D_{\text{inference}}$ is large (few inference tokens relative to pretraining), the second term dominates, giving the smaller model a large inference budget to work with.

The critical role of $R = D_{\text{inference}} / D_{\text{pretrain}}$. The paper defines $R$ as the inverse of the pretraining-to-inference ratio: $R = D_{\text{inference}} / D_{\text{pretrain}}$. When $R \ll 1$ (few inference tokens relative to pretraining — typical for self-improvement pipelines where you generate a modest amount of inference data), the smaller model receives a large inference budget because the pretraining savings are huge. When $R \gg 1$ (many inference tokens — typical for large-scale production deployments where the model serves millions of queries), the inference budget for the smaller model is more constrained because the larger model's per-token inference cost is a bigger fraction of total compute.

Experimental setup for the comparison. The paper compares PaLM 2-S* with compute-optimal test-time scaling against a model with approximately 14× more parameters (greedy decoding, no extra test-time compute). Three values of $R$ are tested:

  • $R = 0.16$ ($R \ll 1$): The ratio of inference to pretraining tokens is 0.16.
  • $R = 0.79$ ($R \approx 1$): Roughly equal numbers of inference and pretraining tokens.
  • $R = 22$ ($R \gg 1$): Many more inference tokens than pretraining tokens.

In the paper's Figure 9, the performance curves for compute-optimal test-time scaling (one curve per difficulty bin, showing accuracy as a function of inference compute budget) are plotted alongside the 14× larger model's greedy performance (shown as stars). The stars are placed at three x-axis positions corresponding to the three $R$ values — each position represents the FLOPs-equivalent inference budget the smaller model can use before exceeding the larger model's total compute. If the star is below the compute-optimal scaling curve for that difficulty bin, test-time compute wins. If the star is above the curve, pretraining wins.

Design choice: scaling parameters only, not data. The paper scales model parameters while keeping training data fixed, following the LLaMA model family approach (Touvron et al., 2023) rather than Chinchilla-optimal scaling (Hoffmann et al., 2022) where both parameters and data are scaled equally. The authors "choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work." This is an important caveat: a Chinchilla-optimal 14× larger model (scaling both parameters and data) would likely outperform a parameter-only scaled model, meaning the comparison may somewhat favor test-time compute. The paper's results should be interpreted as comparing against a "typical" larger model trained in the LLaMA paradigm, not a theoretically optimal one.

4. Key Insights and Innovations

Innovation 1: Difficulty-Conditioned Compute-Optimal Test-Time Scaling as an Inference-Time Analog to Pretraining Scaling Laws

The paper's most fundamental conceptual contribution is not any single method — it is the meta-strategy of adaptively allocating test-time compute based on prompt difficulty, and the empirical demonstration that this simple conditioning recovers large efficiency gains that uniform strategies leave on the table. This insight recasts test-time compute from a blunt knob ("more samples = better performance") into a resource allocation problem where the optimal strategy is a function of both the compute budget and the prompt characteristics, directly paralleling how Chinchilla scaling laws (Hoffmann et al., 2022) recast pretraining from "train the biggest model possible" into an optimal allocation problem between model size and data quantity.

What makes this genuinely novel rather than an obvious observation is that the difficulty-dependent behavior is often counterintuitive and would not be predictable a priori from aggregate scaling curves. Beam search, the stronger optimizer, actually hurts performance on easy problems at high budgets due to verifier over-optimization (Figure 3, right), while it substantially helps on medium-difficulty problems. Similarly, sequential revisions dominate on easy problems but a balanced sequential-parallel ratio is optimal on hard ones (Figure 7, right). These are not monotonic relationships where "more powerful method = better performance" — they are non-monotonicities that only become visible when data is disaggregated by difficulty. The compute-optimal policy exploits these non-monotonicities to achieve 4× better efficiency than best-of-N (Figures 4 and 8), but the deeper contribution is the discovery that these non-monotonicities exist systematically, driven by a single sufficient statistic (model-relative difficulty) that predicts which strategies will work where.

Prior to this work, the field treated test-time compute strategies as universal tools to be compared in the aggregate. Best-of-N was the default (Cobbe et al., 2021), and when more sophisticated methods like tree search (Yao et al., 2023; Feng et al., 2024) or self-refinement (Madaan et al., 2023) were proposed, they were evaluated against baselines on full benchmark averages. This paper argues — and demonstrates — that aggregate comparisons mask the signal: a method that looks mediocre overall may be the best choice for a specific difficulty tier, and deploying it selectively can outperform any single method deployed uniformly. This is a fundamental shift from "which method is best?" to "which method is best for this specific prompt?"

The practical significance of this reframing extends beyond the specific methods studied. Any future test-time compute technique — whether it involves tool use, chain-of-thought variants, retrieval augmentation, or entirely new mechanisms — can in principle be plugged into this difficulty-conditioned allocation framework. The paper provides not just a result but a template for how to think about test-time compute: estimate difficulty, sweep strategies per difficulty bin, and deploy adaptively. This is an inference-time analog of the Chinchilla insight, and it has the same structural implication: the optimal way to spend a fixed compute budget depends on context, and systematic empirical analysis of that dependence yields large efficiency gains.

The evidence for this innovation is the consistent pattern across both mechanisms studied — search and revisions — that difficulty bins predict strategy efficacy (Figures 3 right, 7 right), and that predicted (non-oracle) difficulty bins track oracle bins closely (Figures 4, 8), making the approach practical. This replication across two independent axes of test-time compute strengthens the claim that difficulty-conditioned allocation is a general principle, not an artifact of a specific method.

Innovation 2: The Proposal-Verifier Decomposition as a Framework for Understanding Complementary Scaling Axes

The paper's Section 2 introduces a unifying lens through which to view all test-time compute methods: they either modify the proposal distribution (what the model generates, e.g., through iterative revisions that condition on previous attempts) or optimize the verifier (how outputs are selected, e.g., through search against a process reward model). While the proposer-scorer decomposition is not new conceptually — it echoes MCMC sampling (Andrieu et al., 2003) and is implicit in any system that generates candidates and then filters them — what the paper contributes is an empirical demonstration that these two axes have complementary, difficulty-dependent strengths, and that understanding this complementarity is essential for optimal allocation.

The key empirical finding is that revisions (proposal modification) and PRM search (verifier optimization) excel on different types of problems. Revisions are most effective on easy problems where the model's initial output is roughly correct and needs local refinement — this is exploitation in answer space, making small targeted fixes. PRM search is most effective on medium-difficulty problems where the model needs to explore qualitatively different solution strategies — this is global search over high-level approaches. The paper doesn't just observe this; it shows that the ratio of sequential to parallel sampling has a difficulty-dependent optimum (Figure 7, right), with easy questions favoring fully sequential revisions and hard questions requiring a balanced mix.

This insight reconciles what appeared to be contradictory findings in the prior literature. Huang et al. (2023) found that "LLMs cannot self-correct reasoning yet," while Madaan et al. (2023) and others found that self-refinement helps. These studies were implicitly testing on different difficulty distributions: Huang et al. likely had a harder problem mix where the base model's initial answers were far from correct (making revision ineffective), while Madaan et al.'s tasks may have included easier problems where local refinement worked. The difficulty-dependent framework provides a unified explanation: self-correction does work, but only on easy problems; search does help, but only on medium problems with the right algorithm at the right budget. The conflicting prior results were an artifact of testing different methods on different (implicitly difficulty-biased) problem distributions.

This is more than a taxonomic contribution. The practical implication is that future systems should not choose between revisions and search — they should deploy both, switching between them per-prompt based on estimated difficulty, or combining them in difficulty-dependent ratios. The paper doesn't fully realize this vision (Section 8 acknowledges that PRM tree-search was not combined with revisions — a significant gap), but the framework provides the intellectual scaffolding for doing so. The proposal-verifier decomposition also suggests that improvements to either axis independently (better revision models, more robust verifiers) should compound when combined, opening a research direction beyond the paper's current results.

The evidence is the consistent pattern across Sections 5 and 6: search and revisions show complementary difficulty profiles, and the compute-optimal policy for each axis independently recovers 4× gains (Figures 4 and 8). The fact that both axes benefit from difficulty conditioning — but for different reasons and at different difficulty levels — supports the claim that they are genuinely complementary, not redundant.

Innovation 3: Verifier Over-Optimization as the Primary Bottleneck Limiting Test-Time Compute Scaling

While reward hacking and over-optimization are well-documented phenomena in the RLHF literature (where optimizing against a learned reward model eventually produces outputs that score highly but are not actually better), this paper provides the first clear, systematic evidence that the same phenomenon governs test-time search against verifiers and is the primary bottleneck preventing unbounded improvements from additional compute. This is a diagnostic contribution: it identifies what breaks when test-time compute is scaled up, and this diagnosis redirects research attention from developing better search algorithms to developing more robust verifiers.

The evidence for over-optimization is concrete and multi-pronged. Beam search degrades easy-problem performance at high budgets (Figure 3, right, bins 1-2) — the stronger optimizer finds solutions that exploit the PRM's spurious correlations rather than producing genuinely correct answers. Lookahead search, the most powerful optimizer studied, paradoxically performs worst overall (Figure 3, left) — it over-optimizes the PRM most aggressively, and this hurts performance. Qualitative examples in Appendix M show search producing degenerate outputs that score highly under the PRM but are clearly wrong: repetitive low-information steps at the end of solutions (Figure 29) and overly short 1-2 step solutions that skip necessary reasoning.

What makes this finding significant beyond its empirical documentation is that it shifts the narrative around test-time compute from "more sophisticated search = better results" to "more sophisticated search = better results only up to the verifier's reliability frontier, after which it backfires." Prior work on tree search with LLMs (Yao et al., 2023; Feng et al., 2024) implicitly assumed that better search algorithms would yield monotonic improvements, limited primarily by compute cost. This paper shows that the limit is not compute but verifier quality: with a given verifier, there is an optimal level of optimization aggressiveness, and pushing past it actively hurts. The compute-optimal policy can be understood partly as a strategy for staying below this over-optimization threshold per difficulty level — using weaker optimization (best-of-N) where the verifier is most reliable (easy problems, where it makes mostly correct assessments) and stronger optimization (beam search) only where the verifier signal has more room to provide genuine guidance (medium problems, where the base model rarely produces correct answers by chance).

This insight has direct implications for research prioritization. It suggests that improving verifier robustness — through better training data, adversarial training, ensemble methods, or calibration techniques — is a more leveraged investment than developing more sophisticated search algorithms. If the verifier over-optimizes under beam search, making beam search more aggressive (e.g., with deeper lookahead or wider branching) will only make things worse. The paper's finding that lookahead search underperforms is not a failure of lookahead search as an algorithm — it is a diagnostic that the PRM cannot support that level of optimization. This redirects the conversation from "what's the best search algorithm?" to "how do we build verifiers that can support aggressive search?"

The paper also identifies a subtle mechanism for over-optimization: the PRM is trained with soft Monte Carlo labels (not binary correctness labels), and the authors find that last-step aggregation outperforms the standard "min" aggregation used in prior work (Appendix E, Figure 13). This suggests that the PRM's intermediate-step scores are less reliable than its final-step scores when used for pruning decisions during search — but search algorithms like beam search rely heavily on intermediate-step scores to decide which prefixes to keep. This is a specific, actionable diagnostic: improving intermediate-step score calibration could directly improve search performance by reducing premature pruning of promising prefixes.

Innovation 4: Empirical Boundary Conditions on the Exchangeability of Test-Time and Pretraining Compute

The FLOPs-matched comparison in Section 7 is not merely a benchmark result — it is a conceptual contribution that establishes where test-time compute can and cannot substitute for pretraining, providing the first empirical characterization of this boundary for language model math reasoning. Prior work on training-inference tradeoffs either operated in very different domains (Jones, 2021, on the board game Hex; Villalobos and Atkinson, 2023, largely in settings with known ground-truth answers) or provided theoretical frameworks without empirical instantiation (Sardana and Frankle, 2023). This paper provides concrete numbers for a specific model and benchmark, but more importantly, it identifies the governing variables that determine which side of the tradeoff is favorable.

The key finding is that test-time and pretraining compute are not 1-to-1 exchangeable — and the paper characterizes exactly when each is preferable. On easy-to-medium problems where the base model has non-trivial pass@1, test-time compute with a smaller model can outperform a ~14× larger model (Figure 9, bins 1-3 especially at low R values). On the hardest problems (bin 5), test-time compute provides essentially zero benefit regardless of budget, meaning some capabilities can only be acquired through pretraining. The dependence on R = D_inference / D_pretrain adds further structure: when R << 1 (few inference tokens relative to pretraining, as in self-improvement pipelines), test-time compute is strongly favored; when R >> 1 (high-volume production deployments), pretraining becomes more competitive because the larger model's per-token inference cost dominates the total compute budget less.

What makes this a conceptual advance beyond a simple measurement is the framework it establishes for future comparisons. The paper defines a specific FLOPs accounting methodology (pretraining = 6ND, inference = 2ND) and an exchange rate formula (F = M + 3(D_pretrain/D_inference)(M-1)) that can be applied to any model, benchmark, or test-time strategy. Any future paper proposing a new test-time compute method can compute its FLOPs-equivalent comparison against a larger model using this formula, with the specific R value determined by the deployment scenario. This transforms a one-off empirical comparison into a reusable analysis tool.

The sharp boundary condition — test-time compute fails on problems outside the base model's capabilities — has significant practical implications. It means that for genuinely novel or out-of-distribution reasoning tasks, there is no substitute for pretraining scale. Test-time compute amplifies existing capability; it does not create capability from nothing. This is consistent with the paper's difficulty-bin results (Figure 3 right, bin 5; Figure 7 right, bin 5), where no amount of compute moves the needle on the hardest problems. The FLOPs-matched analysis simply operationalizes this in a resource-allocation context: if your problem distribution includes a non-trivial fraction of bin-5 problems, you need a larger model, period.

The paper's caveat about scaling only parameters (not data) when increasing pretraining compute — following the LLaMA paradigm rather than Chinchilla-optimal scaling — is an important nuance. A Chinchilla-optimal 14× larger model (scaling both parameters and data) would likely be stronger than the parameter-only-scaled model used in the comparison, meaning the reported advantage for test-time compute may be an upper bound. However, this does not undermine the conceptual contribution: the paper establishes the framework for the comparison, and future work can instantiate it with Chinchilla-optimal baselines to refine the specific numerical tradeoffs.

5. Experimental Analysis

Evaluation Methodology

  • Dataset. All experiments use the MATH benchmark (Hendrycks et al., 2021), consisting of high-school competition-level math problems. The authors use the specific split from Lightman et al. (2022): 12,000 training questions for model development (PRM training, revision model fine-tuning) and 500 test questions for evaluation. The choice of MATH is deliberate — test-time compute is expected to help most when the model already possesses the necessary knowledge and the challenge is drawing complex inferences, which characterizes mathematical reasoning.

  • Base model(s). All primary experiments use PaLM 2-S* (Codey) (Anil et al., 2023). The authors argue this model is "representative of the capabilities of many contemporary LLMs" and sits in a useful intermediate regime: it attains "a non-trivial performance on MATH and yet has not saturated," with pass@1 rates varying substantially across difficulty levels. The base model is few-shot prompted with 4 randomly selected correct answer examples from the PRM800k data (phase 1 training split) to output answers in a newline-separated step-by-step format. For the FLOPs-matched comparison (Section 7), a second model with approximately 14× more parameters is used as the pretraining-scaled baseline, evaluated with greedy decoding only (no test-time compute augmentation).

  • Metrics. The primary metric throughout is MATH test accuracy (%) — the fraction of the 500 test questions for which the selected final answer matches the ground truth. Answers are graded using the grading function released by Lightman et al. (2022). When analyzing difficulty-dependent behavior, the paper reports accuracy within each of the five difficulty quintiles separately (approximately 100 questions per bin). For the FLOPs-matched comparison, relative improvement percentages are computed as the difference between the test-time compute approach and the larger model's greedy performance, normalized appropriately.

  • Baselines. The paper compares against several baselines, some with and some without learned verifiers:

    • Majority voting: Select the most common final answer among N independently sampled solutions — no learned verifier involved. This serves as a lower bound on what can be achieved without reward model training.
    • ORM best-of-N weighted: Sample N solutions from the few-shot prompted base LLM, score each with an outcome reward model (trained by fine-tuning the base model as a binary classifier on complete solution correctness), and apply best-of-N weighted selection (Li et al., 2023) to pick the final answer. This represents the standard verifier-based approach from prior work (Cobbe et al., 2021) and is the primary baseline that the paper aims to substantially beat.
    • PRM best-of-N weighted: Same as ORM best-of-N weighted but using the process reward model's last-step prediction as the solution score instead of a separately trained ORM. This isolates whether the PRM architecture alone (even without search) provides benefits over an ORM.
    • Parallel sampling (in revision experiments): Generate N independent solutions from the revision model (no sequential conditioning) and select the best via the revision-specific ORM or majority voting. This is the "no-revision" baseline that isolates the benefit of sequential conditioning.
    • Greedy decoding (14× larger model): Used in the FLOPs-matched comparison — the larger model produces one answer deterministically with no test-time compute augmentation.

  • Generation budget / compute accounting. Test-time compute is measured in units of generations, where one generation equals one complete sampled answer from the base LLM. For best-of-N and beam search, the budget simply equals the number of beams or samples N. For lookahead search with k lookahead steps, the cost is N × (k + 1) generations to account for the additional rollout computation at each step. Budgets are swept across powers of 2, typically from 2^0 to 2^9 (1 to 512 generations). For the FLOPs-matched comparison, compute is measured in total FLOPs using standard approximations: pretraining FLOPs = 6ND_pretrain and inference FLOPs = 2ND_inference (Hoffmann et al., 2022), allowing a direct comparison between scaling model parameters versus scaling inference generations.

  • Cross-validation / statistical protocol. To avoid contamination between strategy selection and evaluation, the paper uses two-fold cross-validation within each difficulty bin on the 500-question test set. The best-performing strategy is selected on one fold and evaluated on the other fold, and vice versa, with results averaged across both test folds. This means strategy selection for each difficulty bin is based on approximately 50 questions per fold — a relatively small sample that could introduce variance. The paper does not report confidence intervals or standard errors on any accuracy measurements, which makes it difficult to assess the statistical reliability of observed differences, particularly when comparing strategies that differ by only 1–2 percentage points.

Main Quantitative Results

Search Against PRM Verifiers (Section 5)

The central finding of the search analysis is that no single search algorithm dominates across all compute budgets and difficulty levels — beam search excels at low budgets and on medium-difficulty problems, best-of-N weighted excels at high budgets and on easy problems — and a compute-optimal policy that selects the best method per difficulty bin can nearly match best-of-N performance using 4× less compute.

Aggregate search algorithm comparison (Figure 3, left). Across all 500 test questions with a maximum budget of 256 generations, the paper finds that at low generation budgets (2–8 generations), beam search significantly outperforms both best-of-N weighted and majority voting. As the budget scales up, the advantage of beam search diminishes and eventually reverses: at 256 generations, beam search with M = 4 falls slightly below best-of-N weighted, and at 512 generations the gap widens further. Lookahead search (both k = 1 and k = 3) generally underperforms other methods at the same generation budget due to its higher per-step cost — the additional simulation rollouts reduce the effective number of beams explored, and the stronger optimization amplifies PRM exploitation. Majority voting trails all verifier-based methods substantially across all budget levels.

The paper attributes the diminishing returns of beam search to PRM over-optimization — beam search, as the stronger optimizer, finds solutions that exploit spurious correlations in the PRM's predictions, producing outputs that score highly but are incorrect. Specific failure modes include low-information repetitive steps at the end of solutions and overly short 1–2 step solutions (examples in Appendix M, Figures 24–29). This explains why lookahead search, the most powerful optimizer, paradoxically underperforms the most: it over-optimizes the PRM most aggressively.

Difficulty-bin analysis for search (Figure 3, right). The most striking and consequential result of the search analysis emerges when performance is disaggregated by difficulty. Comparing beam search (M = 4) against best-of-N weighted at four budget levels (4, 16, 64, and 256 generations) across the five difficulty quintiles:

  • Bin 1 (easiest questions): Beam search degrades in performance as the budget increases, while best-of-N weighted steadily improves. At 256 generations, best-of-N weighted dramatically outperforms beam search. This is the clearest evidence of verifier over-optimization: on easy questions where the base model already produces correct answers frequently, aggressive search amplifies residual PRM errors rather than finding genuinely better solutions.

  • Bin 2: A similar but less extreme pattern — beam search shows modest improvements but is outpaced by best-of-N weighted at higher budgets, which maintains a clear advantage.

  • Bin 3: Beam search consistently outperforms best-of-N weighted across all budget levels, with the gap widening at higher budgets. The PRM's guidance genuinely helps navigate toward correct solutions that random sampling would miss.

  • Bin 4: Beam search shows the strongest relative advantage over best-of-N weighted, particularly at 256 generations where the gap is substantial. On these difficult questions where the base model rarely produces correct answers by chance, the PRM's step-level guidance is most valuable.

  • Bin 5 (hardest questions): Both methods hover near 1–3% accuracy regardless of budget. No method makes meaningful progress — the base model simply lacks the capability to produce correct solutions on these problems, and no amount of search can compensate.

This difficulty-dependent pattern — beam search helps on medium problems, hurts on easy problems, and does nothing on the hardest — is the empirical foundation for the paper's compute-optimal search policy.

Compute-optimal search results (Figure 4). By selecting the best search strategy (from the swept configurations) per difficulty bin at each budget level, the paper constructs the compute-optimal scaling curve. The key quantitative claim: at 16 generations, compute-optimal search (oracle difficulty bins) achieves approximately the same accuracy as PRM best-of-N weighted at 64 generations — a ~4× efficiency improvement. At 256 generations, compute-optimal oracle reaches approximately 39.5%, surpassing PRM best-of-N weighted at the same budget (approximately 37%). Compute-optimal scaling with predicted difficulty bins (using the PRM's average final-answer score rather than ground-truth correctness to bin questions) tracks the oracle version closely — the curves "largely overlap with each other" — which is critical because it demonstrates that the approach works without access to ground-truth labels. The predicted-bin curve reaches approximately 37% at 256 generations, slightly below the oracle curve but still substantially above the best-of-N baseline. Both compute-optimal variants consistently outperform ORM best-of-N weighted and majority voting.

PRM vs. ORM comparison (Appendix F, Figure 14). At 2048 samples, PRM best-of-N weighted achieves approximately 40% accuracy versus roughly 35% for ORM best-of-N weighted and roughly 30% for majority voting. The gap between PRM and ORM widens as the number of samples increases, confirming the PRM's superior scaling properties. This comparison uses the few-shot prompted base LLM to generate outputs and compares the two verifier architectures (PRM with last-step aggregation vs. separately trained ORM) on the same set of candidate solutions.

Revision Model Results (Section 6)

The central finding of the revision analysis is that sequential revisions (modifying the proposal distribution) provide complementary benefits to parallel sampling, that the optimal ratio of sequential to parallel compute depends on question difficulty, and that a compute-optimal allocation of sequential and parallel generations can outperform the parallel baseline by ~4×.

Revision model pass@1 trajectory (Figure 6, left). Starting from approximately 18.2% pass@1 at step 1 (the first answer generated by the revision model), the model's per-step accuracy gradually improves, reaching roughly 24–25% by steps 15–20, and remaining in the 23–25% range out to 64 steps. This improvement trajectory is notable for two reasons: (1) the model was only trained with up to 4 previous answers in context, yet it continues to benefit from longer revision chains — evidence of generalization beyond the training distribution; and (2) the improvement is gradual and eventually plateaus, suggesting diminishing returns from additional revisions on any single chain.

Sequential vs. parallel comparison (Figure 6, right). At 64 generations, aggregated across all test questions:

  • Sequential revisions + best-of-N weighted (revision-specific ORM): approximately 41.5%
  • Parallel sampling + best-of-N weighted: approximately 39%
  • Sequential revisions + majority voting: approximately 38%
  • Parallel sampling + majority voting: approximately 35%

Sequential revisions narrowly but consistently outperform parallel sampling under both selection mechanisms. The gap is small (roughly 2.5 percentage points with the verifier, roughly 3 points with majority voting) but consistent. The paper frames this as evidence that "generating answers sequentially with the revision model narrowly outperforms generating them in parallel."

Sequential-to-parallel ratio sweep (Figure 7, left). For a fixed generation budget, the paper sweeps the ratio of sequential to parallel compute by varying the number of parallel chains and the length of each chain while keeping the total generations constant. At 256 generations:

  • Fully parallel (all 256 generations as independent samples): approximately 40%
  • Fully sequential (one chain of length 256): approximately 42%
  • Optimal intermediate ratio (around 2:1 to 8:1 sequential-to-parallel, corresponding to 2^1 to 2^3 on the paper's log-scale x-axis): approximately 43–44%

At lower budgets (8–32 generations), the curves are monotonically increasing with the sequential-to-parallel ratio — fully sequential is optimal, meaning every generation should be a revision when the total budget is small. At higher budgets, an intermediate ratio becomes optimal, suggesting that parallel diversity and sequential refinement have complementary benefits that manifest when sufficient total compute is available.

Difficulty-dependent optimal ratio (Figure 7, right). At a fixed budget of 128 generations with verifier-based selection, broken out by difficulty bin:

  • Bin 1: Performance is essentially flat across all sequential-to-parallel ratios, around 90–92%. Easy questions are insensitive to allocation strategy — the model gets them right regardless of how the budget is deployed.
  • Bin 2: Slight advantage for higher sequential ratios, approximately 63% at fully sequential vs. approximately 58% at fully parallel. Easy-to-medium questions benefit from local refinement.
  • Bin 3: A clear optimal ratio emerges at moderate sequential-to-parallel values (around 2^1 to 2^3), reaching approximately 42% vs. approximately 35% at the extremes. The model needs both exploration (parallel chains for different high-level approaches) and exploitation (sequential revisions to fix errors within each approach).
  • Bin 4: A similar pattern with the peak at a moderate ratio achieving roughly 18% vs. approximately 14% at fully parallel. Even on relatively hard questions, a balance of exploration and refinement helps.
  • Bin 5: All ratios produce roughly 2–3% accuracy. No allocation strategy makes a difference — the base model has essentially zero capability on these problems.

This pattern supports the paper's hypothesis that "sequential revisions may work more as a local refinement process, revising responses that are already somewhat on the right track," while "sampling answers in parallel may act as more of a global search process."

Compute-optimal revision results (Figure 8). By selecting the optimal sequential-to-parallel ratio per difficulty bin at each budget level, the paper constructs the compute-optimal scaling curve for revisions. The key quantitative claims:

  • At 64 generations, compute-optimal oracle achieves approximately 40%, roughly matching parallel best-of-N weighted at 256 generations — a ~4× improvement.
  • At 256 generations, compute-optimal oracle reaches approximately 44%, compared to roughly 41% for best-of-N weighted and approximately 37% for the parallel-only baseline.
  • At higher generation budgets, the parallel sampling baseline appears to plateau around 36–37%, while compute-optimal scaling continues to improve, suggesting that the gains from adaptive allocation compound at higher budgets rather than saturating.
  • Compute-optimal predicted difficulty bins perform slightly below oracle bins at high budgets (approximately 41% at 256 generations vs. ~44% for oracle), but still substantially outperform the parallel baseline. The gap between oracle and predicted bins is larger for revisions than for search (compare Figure 4 vs. Figure 8), which may reflect that the PRM-based difficulty estimator is less accurate for predicting revision model behavior than for predicting search behavior.

FLOPs-Matched Comparison: Test-Time Compute vs. Pretraining (Section 7)

The central finding of the FLOPs-matched comparison is that test-time and pretraining compute are not uniformly exchangeable — test-time compute can outperform a ~14× larger model on easy-to-medium problems and in low-inference-volume settings, but pretraining remains preferable on the hardest problems and in high-inference-volume settings.

Revisions (Figure 9, left; Figure 1, top-right bar chart). Comparing PaLM 2-S* with compute-optimal revisions against the ~14× larger model (greedy decoding, no test-time compute):

Difficulty groupingR = 0.16 (R << 1)R = 0.79 (R ≈ 1)R = 22 (R >> 1)
Easy questions+11.8%+3.5%−11.9%
Medium questions+27.8% (bins 2–3)+16.7%+5.4%
Hard questions (bins 4–5)+21.6%(implied negative from bar chart)−37.2%

The paper's bar chart in Figure 1 (top-right) presents these as "relative improvement in accuracy from test-time compute" with the larger model's greedy performance as the baseline. Positive numbers mean test-time compute wins; negative numbers mean pretraining wins. The pattern is clear: at R << 1 (low inference volume relative to pretraining — typical of self-improvement pipelines), test-time compute is preferable across all difficulty levels. At R >> 1 (high inference volume — typical of large-scale production deployments), test-time compute remains preferable only on easy and medium questions, with hard questions showing a dramatic −37.2% disadvantage.

The line plots in Figure 9 (left) show the compute-optimal revision scaling curves for each difficulty bin, with the 14× larger model's greedy performance shown as stars at three x-axis positions corresponding to the three R values. On bin 1 (purple, topmost line), the scaling line is above all three stars — test-time compute wins across all R values for easy questions. On bin 5 (blue, bottommost line), the line is below all three stars and essentially flat near 0–5% — no amount of test-time compute helps on the hardest problems, and pretraining with a larger model is always preferable.

PRM search (Figure 9, right; Figure 1, bottom-right bar chart). The same comparison for PRM search:

Difficulty groupingR = 0.16 (R << 1)R = 0.79 (R ≈ 1)R = 22 (R >> 1)
Easy questions+19.1%+2.2%+2.0%
Medium questions0.0%−35.3%−30.8%
Hard questions−3.6%−35.3%−52.9%

PRM search shows substantially weaker benefits than revisions in the FLOPs-matched comparison. On medium questions, test-time compute is only neutral at R << 1 and shows large negative margins at higher R values. On hard questions, it is negative across all R values, with a catastrophic −52.9% at R >> 1. Only on easy questions does PRM search consistently match or beat the larger model, with a strong +19.1% advantage at R << 1 narrowing to a marginal +2.0% at R >> 1. The authors note this comparison uses the oracle difficulty bins for the compute-optimal strategy (since the purpose is to measure the best possible test-time compute performance), making these results an upper bound on what could be achieved in a deployed setting without ground-truth difficulty information.

The line plots in Figure 9 (right) show the PRM search scaling curves with stars for the 14× larger model. On bin 1 (easy questions), the stars are at or below the compute-optimal curve, especially at R << 1. On bin 5 (hardest questions), the compute-optimal curve is essentially flat near 0–5% while the larger model achieves markedly higher performance, making pretraining the clear winner.

Ablation Studies and Robustness Checks

  • PRM step-wise aggregation strategy (Appendix E, Figure 13). The paper compares three methods of aggregating per-step PRM scores into a single solution score: taking the minimum across all steps ("min"), taking the product of all step correctness probabilities ("prod"), and using only the last step's prediction ("last"). "Last" performs best (approximately 37% at 256 samples), followed by "min" (approximately 35%), with "prod" substantially worse (approximately 27%). An ORM baseline achieves approximately 34%. This finding contradicts prior work (Lightman et al., 2023; Wang et al., 2023) that found "min" to be optimal, and the authors attribute the discrepancy to their use of soft Monte Carlo return labels rather than binary correctness labels, which "surface very differently." An interesting implication: using "last" aggregation effectively reduces the PRM to ORM-like behavior at test time, yet the PRM still outperforms a separately trained ORM, suggesting the per-step training provides beneficial representation learning even when intermediate predictions are not directly used.

  • PRM vs. ORM comparison (Appendix F, Figure 14). The PRM consistently outperforms a separately trained ORM in best-of-N weighted evaluations, with the gap widening at higher sample counts. At 2048 samples, PRM best-of-N weighted reaches approximately 40% vs. ORM's approximately 35% and majority voting's approximately 30%. This confirms that the step-level training signal — even with last-step aggregation at test time — produces a better verifier than training only on final-answer correctness.

  • Revision model verifier choice (Appendix J, Figure 15a). The PRM trained on PaLM 2-S* base model outputs does not transfer well to the PaLM 2-S* revision model's outputs. Sequential revisions scored with the base-LM PRM achieve approximately 40% at 64 generations, while sequential revisions scored with a revision-specific ORM achieve approximately 42%. The gap, while modest, demonstrates that distribution shift is a practical concern — verifiers should be trained on the same model distribution that will be used at test time. The parallel baseline (no sequential revisions) achieves approximately 39% under the revision-specific ORM.

  • Revision history in verifier context (Appendix J, Figure 15b). The revision-specific ORM is trained with and without previous revisions in context (so the verifier either sees or does not see the revision model's prior attempts when scoring the current answer). Including revision history provides a small improvement (approximately 1–2 percentage points at 64 generations), but both settings outperform the parallel baseline. This demonstrates that the benefit of sequential revisions is not solely attributable to the verifier seeing more context — even when the verifier is blind to the revision chain, sequential sampling still helps, meaning the revision model genuinely produces better answers sequentially.

  • Oracle vs. predicted difficulty bins (Figures 4, 8, and Appendix C, Figures 11–12). For PRM search, both oracle and predicted difficulty bins yield qualitatively similar trends and the compute-optimal curves "largely overlap" (Figure 4). For revisions, predicted bins show similar trends to oracle bins (Appendix C, Figure 11) but with a larger performance gap at high budgets (approximately 41% vs. 44% at 256 generations in Figure 8). This is the critical robustness check: the compute-optimal strategy works without ground-truth labels, though the degradation is larger for revisions than for search.

  • Majority voting for revisions (Appendix B, Figure 10). The sequential-to-parallel ratio trends observed with verifier-based selection are replicated with majority voting: easy questions are largely insensitive to ratio, harder questions show an optimal intermediate ratio, and fully sequential marginally outperforms fully parallel in aggregate. This demonstrates that the difficulty-dependent ratio finding is not an artifact of the verifier — it holds with a simpler, verifier-free selection mechanism.

  • ReSTEM^{EM} revision model (Appendix K, Figure 16). An attempt to further optimize the revision model using ReSTEM^{EM} (Singh et al., 2024) — generating 64 revision trajectories per training question, stopping at the first correct answer, and fine-tuning on this data — backfires substantially. Additional sequential revisions hurt performance with this model: as the sequential-to-parallel ratio increases, accuracy drops (the curve slopes downward, opposite to the original revision model's upward trend). At 256 generations, fully sequential performance drops to approximately 33.5% compared to roughly 38.5% at the optimal (low-sequential) ratio. The authors hypothesize that "the online data obtained from running ReSTEM exacerbates spurious correlations in revision data, causing the optimized model to fail to learn the revision task." This is a notable negative result: revision model training is fragile, and the specific data collection methodology (offline post-hoc pairing with edit distance vs. online iterative generation) matters critically for learning a useful revision capability.

Critical Assessment

Claim: Compute-optimal scaling improves test-time compute efficiency by more than 4× over best-of-N.

This claim is supported with evidence from both the search and revision pipelines, but its quantitative interpretation requires careful qualification. For PRM search (Figure 4), compute-optimal scaling at 16 generations matches best-of-N at 64 generations — a 4× reduction. For revisions (Figure 8), compute-optimal scaling at 64 generations matches best-of-N at 256 generations — also a 4× reduction. However, these comparisons are between the compute-optimal curves (which use the best search strategy or sequential-to-parallel ratio per difficulty bin) and the parallel best-of-N baselines.

Two important caveats limit the strength of this claim. First, the reported comparisons use the test set for both strategy selection (via cross-validation within folds) and evaluation. With only ~50 questions per fold per difficulty bin, the selected strategies may be overfit to the specific test questions, and the 4× figure might not generalize to new problems drawn from the same distribution. The paper does not report confidence intervals, which would help assess whether the observed gains are statistically reliable given the small per-bin sample sizes.

Second, and more fundamentally, the difficulty estimation cost is not included in any budget calculation. For both oracle and predicted difficulty bins, the paper generates 2048 samples per question to estimate difficulty — a cost that can exceed the largest test-time budgets studied (256–512 generations) by an order of magnitude. Even in the predicted-bin setting, where ground-truth labels are not needed, the 2048-generation cost per question makes the approach impractical for deployment without additional work. The paper acknowledges this ("our experiments do not account for this cost largely for simplicity") but the 4× efficiency claim should be understood as an upper bound on what is achievable if difficulty could be estimated for free, not as a realized deployment gain. A fairer evaluation would amortize the difficulty estimation cost across multiple uses of the same difficulty estimates, or would include the cost of a cheaper difficulty predictor (which does not yet exist as of this work).

Claim: Test-time compute with a smaller model can outperform a ~14× larger model.

This claim is supported by the FLOPs-matched comparison (Section 7, Figure 9, Figure 1), but the support is highly conditional. The claim holds convincingly for easy-to-medium difficulty questions at R << 1 (low inference-to-pretraining token ratio). For revisions on medium questions at R << 1, the relative improvement is +27.8% — a substantial margin. At R ≈ 1, the advantage shrinks (+16.7% for medium questions with revisions) and at R >> 1 it narrows further (+5.4% for medium questions) — still positive but much less compelling. For hard questions, the advantage flips to a large disadvantage at R >> 1 (−37.2% for revisions, −52.9% for PRM search).

Several experimental design choices make this comparison somewhat favorable to test-time compute. The 14× larger model is evaluated with greedy decoding only — no best-of-N, no majority voting, no search. A fairer comparison would give the larger model some modest test-time compute budget (e.g., best-of-8) since any deployed model would likely use at least some inference-time augmentation. Additionally, the larger model is scaled in parameters only (following the LLaMA paradigm) rather than in both parameters and data (Chinchilla-optimal). A Chinchilla-optimal 14× larger model would likely be stronger, making the comparison less favorable to test-time compute. The paper acknowledges this caveat but does not correct for it.

Furthermore, the FLOPs accounting uses approximations (6ND for pretraining, 2ND for inference) that are standard but rough. The actual FLOPs ratio between pretraining and inference depends on implementation details (attention kernel efficiency, sequence length distributions, KV-cache management) that can shift the exchange rate by constant factors. The paper's qualitative conclusions (test-time compute better at low R, worse at high R, fails on hard problems) are likely robust to these constant factors, but the specific crossover points (e.g., exactly where R is high enough that pretraining becomes preferable) are not.

Claim: The effectiveness of test-time compute strategies depends critically on prompt difficulty.

This is the paper's most robustly supported claim. The difficulty-bin analyses for both search (Figure 3, right) and revisions (Figure 7, right) show qualitatively different — and sometimes opposite — effects of the same strategy at different difficulty levels. Beam search degrades easy-problem performance while improving medium-problem performance. Sequential revisions dominate on easy problems while a balanced ratio is optimal on harder ones. These non-monotonicities are consistent across both axes of test-time compute and across both selection mechanisms (verifier and majority voting), which strengthens the claim that difficulty-dependent behavior is a general property rather than a method-specific artifact.

The cross-validation protocol within difficulty bins ensures that the reported per-bin results are not due to overfitting strategy selection to test data. However, the paper establishes difficulty bins using the same 2048 samples per question that would be used for strategy selection in a deployment — this is not a confound but does mean the difficulty bins learned on the 500-question test set might not transfer perfectly to new questions from a different distribution (e.g., different MATH problem types). The paper does not test generalization of the difficulty-binning procedure to out-of-distribution prompts.

Missing experiments and analyses. Several experiments would have strengthened the paper's conclusions:

  • Combined PRM search with revisions. The paper studies search and revisions independently but never combines them — e.g., using the revision model as the proposal distribution within beam search, or using the PRM to guide which revision branches to pursue. Section 8 acknowledges this gap. Without this experiment, the paper cannot claim that the 4× gains from each axis are complementary or could be combined for even larger improvements.

  • A single, unified compute-optimal policy across both axes. The paper presents separate compute-optimal policies for search and revisions, but never constructs a policy that chooses between search and revisions per prompt. Given that revisions excel on easy problems and search on medium problems, a unified policy could outperform either approach alone. The lack of this experiment makes the paper's results a lower bound on what compute-optimal scaling could achieve.

  • Ablation over the number of difficulty bins. The paper uses five bins (quintiles) with no justification or sensitivity analysis. Would three bins capture most of the benefit? Would ten bins provide finer-grained allocation at the cost of less reliable strategy estimation? This is a hyperparameter that matters for the practical deployment of the method, and the paper provides no guidance.

  • Scaling the larger model's test-time compute. The FLOPs-matched comparison gives the 14× larger model zero test-time compute. A comparison where both models receive the same multiplicative factor of additional inference compute (e.g., the smaller model gets 64× more generations and the larger model gets 8× more, both matching the same total FLOPs increase) would be a much stronger test of whether test-time compute genuinely substitutes for parameters or whether it simply augments them.

  • Replication on a second benchmark or model family. All results are on MATH with PaLM 2-S*. The paper claims PaLM 2-S* is "representative of the capabilities of many contemporary LLMs" and that the findings should transfer — but this is an untested assumption. Different model families have different calibration properties, different error patterns, and different in-context learning capabilities, all of which could affect the difficulty-dependent scaling curves, the over-optimization threshold, and the efficacy of revisions.

Where the claims hold conditionally. The paper's central narrative — that compute-optimal test-time scaling can substantially improve efficiency and sometimes outperform pretraining scale — holds for the specific combination of (MATH, PaLM 2-S*, fine-tuned PRM and revision models, ≤256 generation budgets) under the condition that difficulty estimation cost is either amortized or ignored. The results do not demonstrate that this approach works on problems outside the base model's capability range (bin 5 is a hard ceiling), on models without fine-tuned verification and revision capabilities, or in deployment settings where the inference-to-pretraining token ratio favors pretraining. The paper is transparent about these boundaries, particularly the failure on hard problems, which actually strengthens the credibility of the conclusions by acknowledging where the method does not work.

6. Limitations and Trade-offs

Assumption: Prompt Difficulty Can Be Estimated From a Computationally Cheap Statistic

The assumption or constraint. The entire compute-optimal framework requires knowing each prompt's difficulty before deciding how to allocate the inference budget. The paper's method for estimating difficulty — generating 2048 samples per question, scoring them with either ground-truth correctness checks (oracle) or the PRM's average final-answer score (predicted), and binning into quintiles — consumes vastly more compute than the test-time budgets being optimized. The authors acknowledge this explicitly in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

The 2048-generation cost per question exceeds the largest test-time budgets studied (256-512 generations) by a factor of 4-8×, and even exceeds the budget at which the 4× efficiency gains are claimed (16-64 generations) by a factor of 32-128×.

The consequence. The headline 4× efficiency improvement over best-of-N is computed after difficulty is already known, without amortizing the cost of learning it. In any realistic single-use deployment, the total cost would be difficulty estimation (2048 generations) + strategy execution (e.g., 16-64 generations), making the total compute far worse than simply running best-of-N at a higher budget from the start. The paper frames this as "an exploration-exploitation tradeoff" (Section 3.2) but provides no amortization scheme, no method for reducing the estimation cost, and no analysis of how many queries must share the same difficulty estimates before the approach becomes net-positive.

What evidence exists in the paper. The paper is transparent about this gap (Section 3.2, Section 8) but provides no measurement of the breakeven point. The difficulty estimation cost of 2048 samples per question is stated explicitly in Section 3.2, and the test-time budgets where gains are claimed are shown in Figures 4 and 8 (16-256 generations). The ~100× gap between estimation cost and claimed-efficiency budget is clear from these numbers but never directly contrasted. No experiment varies the number of samples used for difficulty estimation to find a cheaper sufficient statistic.

Mitigation status. The paper does not attempt to mitigate this limitation in the reported results. Section 8 suggests future work on "pretraining or finetuning models to directly predict difficulty of a question" or "dynamically switching between assessing difficulty and attempting to solve a question," but neither approach is developed or evaluated. The paper also notes that "this one-time inference cost can be subsumed within the cost for actually running an inference-time strategy" — for instance, when using a verifier, the same inference computation could serve both purposes — but this argument is not operationalized. The reported gains should be understood as an upper bound on achievable efficiency if difficulty were known for free, not as a realized deployment improvement.

No Progress on the Hardest Problems (Bin 5 Remains Unsolved)

The constraint. Across all methods — PRM search, iterative revisions, and their compute-optimal combinations — the hardest questions (difficulty bin 5, where the base model's pass@1 is near zero) show essentially no improvement regardless of compute budget. Test-time compute amplifies existing capability but does not create it from nothing, and when the base model cannot produce correct answers at any non-trivial rate, no amount of search or revision helps.

The consequence. This is a hard ceiling on the approach. The paper demonstrates that test-time compute can substitute for pretraining scale on easy-to-medium problems (Figure 9, bins 1-3), but the same analysis shows that on bin 5 problems, test-time compute provides near-zero benefit while a 14× larger pretrained model achieves markedly higher performance (the stars in Figure 9 are far above the scaling curves for bin 5). In the FLOPs-matched comparison (Section 7, Figure 1 bottom-right), hard problems show a −37.2% to −52.9% relative disadvantage from using test-time compute instead of pretraining. For any deployment where the problem distribution includes a non-trivial fraction of genuinely difficult questions (outside the base model's capability range), this approach offers no path forward — pretraining a larger model is the only option.

What evidence exists in the paper. This limitation is documented consistently across every analysis. In PRM search (Figure 3, right), bin 5 accuracy hovers at 1-3% for all methods and all budgets (4, 16, 64, 256 generations). In revisions (Figure 7, right), bin 5 shows roughly 2-3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0-5% while the 14× larger model's greedy performance (stars) is substantially above this line for all values of R. The paper is candid about this: "On the most difficult questions (level 5), no method makes much meaningful progress" (Section 5.3) and "on challenging questions which are outside a given base model's capabilities... pretraining is likely more effective for improving performance" (Section 7 takeaway).

Mitigation status. The paper acknowledges this limitation explicitly in Section 8: "across the board these schemes provided small gains on hard problems; future work should work to develop new ways of using test-time compute which can circumvent this limitation." No mitigation is attempted within the current work. The limitation is fundamental rather than methodological — it reflects the nature of test-time compute as an amplifier of existing capability rather than a generator of new capability — and overcoming it likely requires fundamentally different approaches (e.g., retrieval augmentation, tool use, or multi-step planning) that are outside the paper's scope.

Single Benchmark and Single Model Family (Unknown Generalization)

The constraint. All experiments are conducted on a single benchmark (MATH, 500 test questions) with a single model family (PaLM 2-S*). The paper states that it "believe[s] this model is representative of the capabilities of many contemporary LLMs, and therefore think that our findings likely transfer to similar models" (Section 4), but this is an untested assumption.

The consequence. Multiple aspects of the findings could be model- or benchmark-specific. The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s specific output distribution, calibration properties, and error patterns — a model with different characteristics might exhibit different difficulty-dependent scaling curves, earlier or later over-optimization thresholds, or entirely different optimal strategy rankings. The revision model's ability to learn from in-context incorrect examples depends on the base model's in-context learning capabilities, which vary substantially across model families. The MATH benchmark consists exclusively of competition-level math problems requiring symbolic reasoning — it is unclear whether the central finding (beam search hurts easy problems due to verifier over-optimization, revisions help easy problems) generalizes to code generation, logical reasoning, scientific QA, or tasks requiring factual knowledge rather than multi-step inference. The specific 4× efficiency improvement and the crossover points in the FLOPs-matched comparison (where exactly R is high enough that pretraining becomes preferable) are almost certainly specific to this model-benchmark pair.

What evidence exists in the paper. No cross-model or cross-benchmark experiments are conducted. The paper's only argument for generalization is the stated belief that PaLM 2-S* is representative (Section 4), which is unsupported. The paper does cite prior work showing that PRM training on GPT-4-generated data (PRM800k) was "largely ineffective" for PaLM 2 models due to distribution shift (Section 5.1), which ironically demonstrates that verifier behavior does depend on model-specific properties — undermining the claim that findings from PaLM 2-S* will transfer directly to other models.

Mitigation status. Not addressed. The paper does not replicate on a second model family (e.g., LLaMA, Gemma) or a second reasoning benchmark (e.g., GSM8K, MBPP, ARC). Section 8 does not flag this as a limitation or suggest cross-model validation as future work; it focuses on extending the approach to new methods (combining PRM search with revisions) rather than new models or domains. This is a significant gap for practitioners who would need to know whether these findings hold for their specific model and task before adopting the compute-optimal framework.

The 14× Larger Model Baseline Is Not Compute-Optimally Trained and Receives No Test-Time Compute

The constraint. The FLOPs-matched comparison in Section 7 scales model parameters while keeping training data fixed, following the LLaMA paradigm (Touvron et al., 2023) rather than Chinchilla-optimal scaling (Hoffmann et al., 2022) where both data and parameters are scaled equally. Additionally, the 14× larger model is evaluated with only greedy decoding — no best-of-N, no majority voting, no search, no test-time compute augmentation of any kind. The paper acknowledges the first issue:

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work." (Section 7)

The consequence. The comparison systematically favors test-time compute in two ways. First, a Chinchilla-optimal larger model (scaling both parameters and data) would likely be stronger than a parameter-only-scaled model trained on the same amount of data, meaning the pretraining baseline is weaker than it could be. The reported advantages of test-time compute over pretraining (e.g., +27.8% relative improvement on medium questions at R << 1 for revisions) would likely shrink or reverse against a properly compute-optimal larger model. Second, and more importantly, giving the 14× larger model even a modest test-time compute budget — say, best-of-8 sampling with majority voting — would create a dramatically stronger baseline at minimal additional FLOPs cost. Any deployed large model would likely use at least some inference-time augmentation, making the greedy-decoding-only comparison unrealistic.

What evidence exists in the paper. The paper explicitly states the parameter-only scaling choice (Section 7) and provides the FLOPs accounting that enables the comparison, but does not include an ablation where the larger model receives test-time compute. No experiment compares a model with moderate parameters + heavy test-time compute against a model with heavy parameters + moderate test-time compute — which would be the fair comparison for determining whether test-time compute genuinely substitutes for pretraining or merely augments it. The fact that the 14× larger model is evaluated only with greedy decoding is not flagged as a limitation.

Mitigation status. The parameter-only-vs-Chinchilla issue is acknowledged but left to future work (Section 7, Section 8). The lack of test-time compute for the larger model is not acknowledged at all. A fairer comparison — where both models receive the same multiplicative factor of additional inference compute under the FLOPs-matched constraint — would require additional experiments that the paper does not report. The current results should be interpreted as comparing compute-optimal test-time scaling against a "naive" larger model deployment, not against a larger model that is itself making effective use of inference-time computation.

Revisions and PRM Search Are Studied Independently (Missing the Combined System)

The constraint. The paper studies two complementary axes for scaling test-time compute — modifying the proposal distribution via iterative revisions (Section 6) and optimizing the verifier via PRM search (Section 5) — but never combines them. Section 8 explicitly acknowledges this:

"While we combined verifiers with revisions in Section 6, we did not experiment with PRM tree-search techniques in combination with revisions."

The revision model experiments (Section 6) use an ORM for answer selection (not the PRM), and the PRM search experiments (Section 5) use the few-shot prompted base model as the proposal distribution (not the revision model). The two mechanisms are complementary in their difficulty-dependent strengths — revisions excel on easy problems, PRM search on medium problems — but the paper never deploys them jointly.

The consequence. The paper cannot claim that the 4× gains from each axis are independent, additive, or achievable simultaneously. It is possible — and even suggested by the difficulty-dependent patterns — that combining PRM search with the revision model as the proposal distribution could yield larger gains than either approach alone, particularly on medium-difficulty problems where both mechanisms show complementary strengths. Conversely, it is possible that the two approaches interfere: the PRM trained on base model outputs may not transfer to revision model outputs (a distribution shift the paper already documents in Appendix J, Figure 15a), and search over revision model outputs might lead to different over-optimization patterns. Without this experiment, the paper's results represent a lower bound on what a fully integrated system could achieve, but they also leave open the question of whether such integration is straightforward or requires additional methodological development.

What evidence exists in the paper. The paper acknowledges this gap in Section 8 but provides no experimental data. The revision model experiments do use a verifier (a revision-specific ORM), but this is for answer selection from parallel chains or within revision sequences — it is not the step-level PRM tree search studied in Section 5. The PRM search experiments use the few-shot prompted base model, not the revision model. The only evidence suggesting combination might work is the difficulty-bin analysis: revisions work best on easy problems (Figure 7, right, bins 1-2) where PRM search over-optimizes (Figure 3, right, bins 1-2), and PRM search works best on medium problems (Figure 3, right, bins 3-4) where revisions show an optimal intermediate ratio (Figure 7, right, bins 3-4). These complementary profiles suggest a combined system could outperform either approach alone, but this is speculative without experimental validation.

Mitigation status. Identified as future work in Section 8: "Future work should investigate how test-time compute scaling can be further improved by combining a variety of these approaches." No attempt at combination is made in the current paper. For a practitioner, this means the paper provides separate recipes for optimizing search and optimizing revisions, but not a recipe for integrating them into a single system — and the practical gains from doing so remain unknown.

The Revision Model Has a Structural Correct-to-Incorrect Reversion Rate of ~38% With No Principled Solution

The constraint. The revision model was trained exclusively on trajectories where all in-context answers are incorrect followed by a correct target answer (Section 6.1). At test time, the model may generate a correct answer mid-chain, which then appears in the context for the next revision step. Since the model has never been trained to recognize correct answers or to "do nothing" when the current answer is already correct, it may incorrectly revise a correct answer into an incorrect one. The paper reports:

"around 38% of correct answers get converted back to incorrect ones with our revision model using a naïve approach" (Section 6.1)

The consequence. The revision model cannot be used naively (just taking the final answer in the chain) — it requires a separate selection mechanism (verifier-based selection or majority voting across the entire chain) to recover correct answers that were generated mid-chain but subsequently reverted. This adds inference overhead (every revision in the chain must be scored or counted) and means the effective accuracy of the revision model is lower than the peak pass@1 at any given step in the chain. More fundamentally, it reflects a training data distribution mismatch that the paper patches at inference time rather than solving. The model has not learned the meta-cognitive skill of recognizing that its current answer is correct and stopping — a capability that would be essential for efficient test-time compute allocation, since continuing to revise an already-correct answer wastes budget and risks reversion.

What evidence exists in the paper. The 38% reversion rate is reported in Section 6.1, and the authors note that "similar to Qu et al. [28]," this is a known issue. The paper mitigates the problem via selection mechanisms (sequential majority voting or verifier-based selection to pick the best answer from the chain rather than always taking the last revision), and Figures 6-8 demonstrate that these mechanisms recover reasonable performance. However, the paper provides no ablation quantifying how much performance is lost due to reversion (e.g., comparing accuracy when taking the last revision vs. the best revision in the chain) and no experiment testing whether models trained with correct-answer-in-context examples would avoid the reversion problem.

Mitigation status. The paper applies a post-hoc selection patch (majority voting or verifier selection across the chain) that mitigates the symptom but does not address the root cause. Section 6.1 describes the mechanism: "we employ a mechanism based on sequential majority voting or verifier-based selection to select the most correct answer from the sequence of revisions made by the model." This is effective enough to produce the reported gains, but it adds complexity (every revision must be independently scored or voted on) and does not prevent the model from wasting compute on revising already-correct answers. A more principled solution — training the model with correct answers in context and teaching it to output a "stop" or "no revision needed" token — is not explored. The negative ReSTEM^{EM} result (Appendix K, Figure 16), where additional optimization caused the revision model to degrade, suggests that revision training is fragile and that the specific data construction procedure (incorrect-only context) is load-bearing for the model's performance — making it unclear whether adding correct-answer-in-context training examples would improve or break the revision capability.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper reshapes how the field should think about inference-time computation — not as a uniform, monolithic knob that monotonically improves performance when turned up, but as a resource to be allocated across multiple competing mechanisms in a prompt-dependent way. Before this work, the dominant paradigm for test-time compute was best-of-N sampling: generate N answers, pick the best one via a verifier, and scale by increasing N. This paper demonstrates conclusively that this uniform approach leaves enormous efficiency on the table — a factor of 4× or more — and that the optimal strategy for spending a given inference budget varies systematically with prompt difficulty. The conceptual shift is from "how much test-time compute should I use?" to "which test-time compute strategy should I use for this specific prompt?"

This is an inference-time analog of the Chinchilla scaling laws for pretraining (Hoffmann et al., 2022). Just as Chinchilla showed that the optimal allocation of pretraining compute between model size and data quantity depends on total budget, this paper shows that the optimal allocation of test-time compute between search algorithms, sequential revisions, and parallel sampling depends on prompt difficulty. The parallel is structural, not superficial: both findings replace a uniform heuristic ("train the biggest model possible" / "sample as many times as you can") with a condition-dependent optimization problem whose solution yields large efficiency gains. The paper does not present a full scaling law in the Chinchilla sense — it does not fit a power-law relationship between compute and accuracy with fitted exponents — but it provides the conceptual foundation and empirical methodology for developing such laws. Future work can parameterize the difficulty-dependent scaling curves (e.g., fitting separate exponents for easy vs. medium vs. hard questions) and derive closed-form optimal allocations, just as the original Chinchilla paper parameterized the tradeoff between parameters and tokens.

Beyond establishing this new paradigm, the paper resolves a genuine contradiction in the prior literature that had produced confusing, seemingly incompatible findings. Huang et al. (2023) found that "LLMs cannot self-correct reasoning yet," while Madaan et al. (2023) and others demonstrated that self-refinement improves outputs. The paper's difficulty-bin analysis provides a unified explanation: self-correction (revisions) works on easy problems where the initial answer is roughly on the right track but fails on hard problems where the initial answer is fundamentally wrong. Similarly, the paper explains why some prior work found tree search helpful (Yao et al., 2023) while others found it underwhelming — search helps on medium-difficulty problems where the verifier provides genuine guidance but harms easy-problem performance due to over-optimization. These conflicting prior results were not wrong; they were testing on different (implicitly difficulty-biased) problem distributions. The paper's explicit difficulty conditioning converts a confusing set of contradictory claims into a coherent picture with clear boundary conditions, which is a genuine service to the field. Future researchers studying test-time compute methods should now report difficulty-stratified results as a matter of course — aggregate benchmarks like MATH average accuracy can mask the very effects that determine whether a method is useful.

The paper also establishes verifier over-optimization as the primary bottleneck for test-time compute scaling, which redirects research attention in a concrete way. Prior work on tree search with LLMs (Feng et al., 2024; Yao et al., 2023) implicitly assumed that more sophisticated search algorithms would yield monotonic improvements, limited primarily by compute cost. This paper shows that the limit is not compute but verifier quality: with a given verifier, there is an optimal level of optimization aggressiveness, and pushing past it actively hurts performance (Figure 3, left — lookahead search, the most powerful optimizer, performs worst). The finding that improving search algorithms can be counterproductive — because stronger optimization amplifies verifier errors — suggests that research investment should flow toward building more robust verifiers (through better training data, adversarial robustness, ensemble methods, or calibration techniques) rather than toward more sophisticated search procedures. If the verifier over-optimizes under beam search, making beam search more aggressive will only make things worse. This is analogous to how the RLHF community's recognition of reward hacking redirected effort from better policy optimization to better reward modeling — the same structural lesson applies here.

Finally, the FLOPs-matched comparison (Section 7, Figure 9) provides the first empirical evidence in a realistic language-model setting (no ground-truth answer access at inference) that test-time compute can substitute for pretraining scale, but only within well-defined boundaries. The paper demonstrates that on easy-to-medium problems where the base model already has non-trivial performance, a smaller model with compute-optimal test-time strategies can outperform a ~14× larger model. However, on the hardest problems (bin 5) where the base model has near-zero pass@1, test-time compute provides essentially no benefit regardless of budget. This establishes a clean boundary condition: test-time compute amplifies existing capability but does not create it. For decisions about where to allocate compute budgets — pretraining vs. inference — this paper provides the first concrete empirical guidance that is specific to problem difficulty and inference volume (R = D_inference / D_pretrain), rather than relying on generic extrapolations or theoretical frameworks.

Follow-Up Research This Work Enables

Training a lightweight difficulty predictor to eliminate the 2048-sample estimation cost. The most immediate bottleneck the paper identifies is the cost of estimating question difficulty. The current method — generating 2048 samples per question and averaging either ground-truth correctness or PRM final-answer scores — is completely impractical for deployment (Section 3.2). The paper explicitly calls for "pretraining or finetuning models to directly predict difficulty of a question" (Section 8). A concrete follow-up would train a small classifier — perhaps a lightweight model distilled from the PRM, or even a linear probe on top of the base model's hidden representations — that takes only the question text as input and predicts the difficulty bin. The training data already exists: the 500 test questions have been labeled with difficulty bins (both oracle and predicted). The evaluation would measure (a) the correlation between predicted and true difficulty bins, and (b) the actual test-time performance achieved when using the predictor's bins instead of the full 2048-sample procedure. If a cheap predictor could achieve difficulty-bin accuracy comparable to the PRM-based method (which already tracks oracle bins closely in Figures 4 and 8), the compute-optimal framework becomes immediately practical. The key metric is not just bin agreement but downstream accuracy: does the compute-optimal strategy selected using predicted bins match the accuracy of the strategy selected using oracle bins? This would close the largest gap between the paper's demonstrated potential and its deployability.

Combining PRM tree search with the revision model as the proposal distribution, with difficulty-conditioned allocation between them. The paper studies two complementary axes — PRM search (Section 5) and iterative revisions (Section 6) — but explicitly acknowledges they were never combined (Section 8). The difficulty-bin analysis reveals they have complementary strengths: revisions excel on easy problems (Figure 7, right, bins 1-2) where PRM search degrades due to over-optimization (Figure 3, right, bins 1-2), and PRM search excels on medium problems (Figure 3, right, bins 3-4) where revisions benefit from a balanced sequential-parallel ratio (Figure 7, right, bins 3-4). A natural experiment would construct a unified system with three strategy options per prompt: (1) purely sequential revisions, (2) PRM beam search with the revision model as the proposal distribution (generating steps autoregressively with previous incorrect revisions in context), and (3) a hybrid combining parallel revision chains with beam search within each chain. The compute-optimal policy would select among these strategies per difficulty bin. The key measurement would be whether the unified policy outperforms the best single-axis policy at the same total compute budget — the hypothesis being that difficulty-conditioned switching between complementary mechanisms yields gains beyond optimizing either mechanism alone. A negative result (no improvement from combining) would be equally informative, suggesting that the two mechanisms are substitutable rather than complementary, or that distribution shift between the revision model and the PRM (documented in Appendix J, Figure 15a) prevents effective combination.

Developing verifier training procedures that are robust to over-optimization under aggressive search. The paper's most important diagnostic finding is that verifier over-optimization is the primary bottleneck preventing unbounded test-time compute scaling. Beam search degrades easy-problem performance at high budgets (Figure 3, right), and lookahead search — the strongest optimizer — paradoxically performs worst overall (Figure 3, left). A systematic follow-up would characterize when and how the PRM fails under optimization pressure. The paper provides qualitative examples of failure modes (repetitive low-information steps, overly short solutions; Appendix M, Figures 24-29), but a quantitative analysis is missing. A strong follow-up would train PRMs with interventions designed to improve robustness: (a) adversarial training where the PRM is fine-tuned on beam-search-generated solutions rather than i.i.d. samples, (b) ensemble PRMs where multiple independently trained models vote on per-step scores, (c) constrained search methods that penalize solutions with low likelihood under the base model (a KL-penalty analogous to RLHF), and (d) training the PRM with auxiliary losses that encourage calibrated uncertainty estimates (e.g., by predicting not just correctness probability but also a confidence interval). The evaluation would plot PRM best-of-N accuracy vs. beam search accuracy at matched budgets as a function of budget, with the ideal verifier showing beam search consistently above best-of-N (no crossover). A negative result — that no intervention eliminates the crossover — would suggest that the over-optimization is fundamental to learned verifiers and that test-time compute scaling requires a fundamentally different approach (e.g., training the proposal distribution itself rather than relying on post-hoc verification).

Replicating the difficulty-dependent scaling analysis on code generation benchmarks with execution-based verifiers. The paper's entire analysis is on MATH, where the verifier is a learned neural network (PRM/ORM) and correctness is determined by string matching against a ground-truth answer. Code generation offers a critically different setting: verification can be done via execution against unit tests, which provides a ground-truth correctness signal without the over-optimization problems that plague learned verifiers. A replication on HumanEval (Chen et al., 2021) or MBPP (Austin et al., 2021) using PaLM 2-S* or an equivalent model would test whether the paper's central findings — difficulty-dependent optimal strategy selection, 4× efficiency gains from compute-optimal allocation, and verifier over-optimization as a bottleneck — are specific to learned verifiers or generalize when a reliable execution-based verifier is available. The hypothesis would be that with ground-truth execution feedback, beam search and lookahead search do not degrade at high budgets (no over-optimization), and the compute-optimal strategy collapses to "always use the strongest search method." Alternatively, if difficulty-dependent patterns persist even with execution-based verification — for instance, if beam search still hurts easy problems because it explores unpromising branches that happen to pass unit tests — this would suggest the patterns are driven by proposal distribution quality rather than verifier quality, requiring a different diagnosis. The experiment would also test whether the difficulty-binning procedure (based on pass@1 rate over 2048 samples) transfers to code generation, where pass@k is a standard metric.

Dynamic, online difficulty estimation and strategy switching within a single inference budget. The paper's compute-optimal policy is static: difficulty is estimated once upfront, and then a fixed strategy is deployed for the full budget. A more sophisticated approach — which the paper flags as an exploration-exploitation tradeoff (Section 3.2) — would interleave difficulty assessment with problem-solving. Concretely, a dynamic policy might: (1) generate 4-8 initial samples in parallel, (2) score them with the PRM and compute the average score as a quick difficulty estimate, (3) decide mid-inference whether to switch to beam search, sequential revisions, or continue parallel sampling, and (4) allocate the remaining budget accordingly. This amortizes difficulty estimation into the solution process itself, eliminating the separate 2048-sample estimation step. A concrete experiment would compare dynamic policies against the paper's static compute-optimal policy (which uses pre-computed difficulty bins) and against uniform best-of-N at the same total budget. The key metric would be whether dynamic policies recover the 4× efficiency gains without the separate difficulty estimation cost. A more ambitious variant would use the PRM's scores on early samples not just to bin difficulty but to continuously re-allocate budget — e.g., if initial samples show high variance in scores (suggesting a hard problem), the policy might shift toward more parallel exploration; if initial samples show consistent moderate scores (suggesting an easy problem where the model is close but not quite there), it might shift toward sequential refinement. This connects naturally to multi-armed bandit and Bayesian optimization literatures, and would test whether the paper's discretized difficulty-bin approach is a necessary simplification or whether continuous, adaptive allocation can improve further.

Evaluating whether test-time compute gains compound across self-improvement iterations. The paper's FLOPs-matched comparison (Section 7) shows that in settings where R = D_inference / D_pretrain << 1 — typical of self-improvement pipelines where a modest amount of inference data is generated to fine-tune the model — test-time compute is strongly favorable over pretraining. This suggests a concrete self-improvement experiment: take the base PaLM 2-S* model, use compute-optimal test-time strategies to generate high-quality solutions on the MATH training set, fine-tune the base model on these solutions, then repeat for multiple iterations (STaR/ReSTEM^{EM}-style; Zelikman et al., 2022; Singh et al., 2024). The paper's negative ReSTEM^{EM} result (Appendix K, Figure 16) shows that naive application of RL-style optimization to the revision model can backfire, but using compute-optimal allocation during data generation (rather than during inference on the test set) might produce higher-quality training data that avoids the spurious correlation degradation. The key measurement would be whether the test-time compute gains are one-shot (boosting performance on the current model's outputs but not improving the model itself) or compounding (the fine-tuned model becomes a stronger base model for the next round of test-time compute). If the gains compound, this would demonstrate that compute-optimal test-time scaling is not just an inference-time trick but a mechanism for iteratively improving the base model's capabilities — potentially shifting the allocation of compute even further toward inference over time.

Practical Applications and Downstream Use Cases

Cost-efficient batch inference for math education and automated grading. Organizations that run large-scale batch inference on math problems — such as online learning platforms that auto-grade student answers, or educational technology companies that generate solution explanations — typically process thousands of questions against a fixed model. In this setting, the inference-to-pretraining token ratio R is small (each question is processed once or a few times), which is exactly the regime where the paper's FLOPs-matched analysis most strongly favors test-time compute over larger models (Section 7, Figure 9, R << 1). A concrete deployment would: (1) run the base PaLM 2-S* model with compute-optimal allocation per question, estimated either via a pre-computed difficulty predictor (if developed) or by spending a modest upfront cost to bin questions by difficulty; (2) allocate budgets adaptively: easy questions might receive 4-8 generations of sequential revisions, medium questions 32-64 generations of beam search with the PRM, and hard questions either the full budget or a flag for human review. The paper's results suggest this could achieve accuracy comparable to a ~14× larger model running greedy decoding, at a fraction of the total cost — the larger model would require proportionally more FLOPs for both the one-time inference cost and, critically, for the pretraining that produced it. For a deployment processing 100,000 questions, the pretraining FLOPs savings alone could be substantial.

On-device deployment of small models with cloud fallback for hard questions. The paper's demonstration that test-time compute can make a small model competitive with a ~14× larger model on easy-to-medium questions (Section 7, Figure 9, bins 1-3 at R << 1) has direct implications for on-device AI. A deployment architecture could run a small PaLM 2-S*-class model locally on a phone or laptop, apply compute-optimal test-time strategies (sequential revisions for easy questions, moderate beam search for medium questions), and only route genuinely hard questions to a cloud-based larger model. The difficulty estimator serves double duty: it determines how much local test-time compute to allocate and whether to escalate to the cloud. The paper provides concrete numbers: on easy questions (bin 1), the small model with compute-optimal revisions achieves 90-92% accuracy (Figure 7, right), which may be sufficient for many use cases without hitting the cloud. On medium questions (bin 3), the small model achieves ~42% with optimal allocation (Figure 7, right) — if this is below the required accuracy threshold, those questions get escalated. The hard limit is bin 5, where the small model achieves 2-3% regardless of strategy — these questions always escalate. This architecture reduces cloud inference costs and latency for the majority of queries while maintaining overall accuracy through selective escalation.

Data generation for math reasoning fine-tuning datasets. When curating fine-tuning data for math reasoning — e.g., to train a specialized model for competition math or to improve a general model's reasoning capabilities — the quality and diversity of generated solutions matter enormously. Using compute-optimal test-time strategies during data generation would allocate the inference budget where it is most productive: spending more compute on medium-difficulty questions (where beam search and balanced sequential-parallel ratios push the model to produce correct solutions it would not find by random sampling) and less on easy questions (where a few sequential revisions suffice to clean up minor errors) or hard questions (where no amount of compute helps and the question should perhaps be excluded from the training set). Concretely, a data generation pipeline could: (1) estimate difficulty for each question in the training set using the PRM-based procedure, (2) apply the compute-optimal strategy for that difficulty bin at a fixed per-question budget (e.g., 64 generations), (3) collect all correct solutions (filtered by ground-truth answer checking, which is available at training time), and (4) fine-tune the base model on this high-quality data. The paper's results (Figure 8) suggest that for a fixed generation budget of 64, compute-optimal allocation produces ~40% accuracy vs. ~36% for parallel best-of-N — a ~4 percentage-point absolute improvement in correct solution yield, which could meaningfully improve the quality of the resulting fine-tuning dataset. This is a direct application of the paper's core finding that difficulty-conditioned allocation extracts more correct answers per unit of inference compute.

When to Prefer This Method

The paper's FLOPs-matched analysis (Section 7) provides explicit conditions under which compute-optimal test-time scaling is preferable to scaling pretraining, and conditions under which pretraining remains the better investment. These are not vague heuristics — they are grounded in specific empirical results:

  • Prefer compute-optimal test-time scaling with a smaller model when:

    • The problem distribution includes a substantial fraction of easy-to-medium questions (difficulty bins 1-3/4, where the base model's pass@1 is non-trivially above zero). On easy questions, test-time compute can achieve 90%+ accuracy (Figure 7, right, bin 1); on medium questions, the 4× efficiency gains over best-of-N are most pronounced (Figures 4, 8); on hard questions (bin 5), test-time compute provides near-zero benefit and pretraining is essential.
    • The inference-to-pretraining token ratio R = D_inference / D_pretrain is low (R << 1 or R ≈ 1). This is typical of self-improvement pipelines, one-time evaluation tasks, and low-volume high-stakes applications. At R << 1, test-time compute outperforms a ~14× larger model across all difficulty levels for revisions (Figure 9, left); at R ≈ 1, the advantage persists on medium questions (+16.7% relative improvement).
    • A reliable verifier (PRM or revision-specific ORM) can be trained on the smaller model's output distribution using the Monte Carlo rollout procedure (Appendix D) or equivalent. The paper found that PRM800k data from GPT-4 did not transfer to PaLM 2 (Section 5.1), and the base-LM PRM did not transfer to the revision model (Appendix J, Figure 15a) — verifiers must be trained on the specific model distribution they will evaluate.

  • Prefer scaling pretraining (training a larger model instead) when:

    • The problem distribution includes a non-trivial fraction of hard questions (difficulty bin 5, where the base model's pass@1 is near zero). On these questions, test-time compute provides 1-3% accuracy regardless of strategy or budget (Figure 3, right; Figure 7, right), while a ~14× larger pretrained model achieves substantially higher performance. The paper is explicit: "on challenging questions which are outside a given base model's capabilities... pretraining is likely more effective for improving performance" (Section 7 takeaway).
    • The inference-to-pretraining token ratio R is high (R >> 1). In large-scale production deployments serving millions of queries, the larger model's per-token inference cost is a smaller fraction of total compute, and the FLOPs-matched comparison flips: on hard questions at R >> 1, test-time compute shows a −37.2% to −52.9% relative disadvantage (Figure 1, bottom-right bar charts).
    • The domain lacks clean correctness signals for training verifiers (open-ended generation, dialogue, creative writing), or the cost of training and running a PRM exceeds the budget. The paper's approach requires verifier training via Monte Carlo rollouts (Section 5.1, Appendix D), which adds a non-trivial training cost that must be amortized over inference usage.
    • Latency is critical and the workload cannot be parallelized. Sequential revision strategies (which the compute-optimal policy favors on easy-to-medium problems) are inherently serial — a chain of 64 revisions takes ~64× longer wall-clock time than 64 parallel samples on sufficient hardware. The paper measures compute in generations but does not account for wall-clock time, making sequential strategies potentially impractical for interactive applications.