Highly accurate protein structure prediction with AlphaFold

URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8371605/pdf/41586_2021_Article_3819.pdf

🎯 Pitch

1. Executive Summary

This paper studies how to optimally allocate test-time computation for large language models on the MATH benchmark using PaLM 2-S* models, analyzing two primary mechanisms — searching against process-based verifiers (PRM-guided beam search vs. best-of-N sampling) and iteratively revising model outputs (sequential revisions vs. parallel sampling) — and introducing a compute-optimal test-time scaling strategy that adaptively selects how to spend an inference budget based on the estimated difficulty of each prompt. The framework yields more than 4× efficiency gains over standard best-of-N baselines (matching best-of-256 performance with only 64 generations in the revision setting and best-of-64 with 16 generations in the search setting), and in a FLOPs-matched comparison demonstrates that a smaller model augmented with compute-optimal test-time strategies can outperform a ~14× larger pretrained model — establishing that test-time compute can substitute for pretraining scale only on problems within the base model's capability range, while offering no benefit on problems where the base model's pass@1 rate is near zero.

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 you give an LLM extra computation at inference time, what is the best way to use it? This matters because, unlike training—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 paper highlights in 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 with additional inference-time processing.
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.
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.

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

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. This paper's central insight 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) reached opposite conclusions.

Where Existing Approaches Fall Short

The paper identifies specific limitations in prior work along two axes:

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). This is simple but treats every token of compute identically regardless of the problem. There's no adaptation to the nature of the prompt—easy problems get the same treatment as hard ones.

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 means that to get revisions to work, you need purpose-built fine-tuned models, which the paper develops following the recipe of Qu et al. (2024).

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. However, prior work had not systematically studied how to search against these verifiers at test time—which search algorithm to use, how the choice depends on compute budget, or when search over-optimizes the verifier signal.

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.

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). This is explicitly analogized to MCMC sampling, where a simple proposal distribution is combined with a score function to sample from a more complex target distribution.

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, PRM-guided search for the verifier—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:

"Although the scaling of pretraining compute has been well-studied through scaling laws... analogous scaling laws for test-time computation do not yet exist."

The paper also explicitly connects to the training-inference tradeoff literature (Jones, 2021; Villalobos and Atkinson, 2023; Sardana and Frankle, 2023), but notes that prior FLOPs-matched comparisons in the language modeling domain largely assumed access to ground-truth answers. This paper's FLOPs-matched analysis operates in the realistic setting where the correct answer is unknown, making the comparison more practically relevant. The authors position their work as addressing the question:

"Given a fixed FLOPs budget, should a practitioner spend it on training a larger model or on applying more inference-time compute to a smaller model?"

3. Technical Approach

3.1 Reader Orientation

This is primarily an empirical analysis paper whose core contribution is not a single new architecture or training method, but rather a meta-strategy for adaptively allocating inference-time computation based on estimated prompt difficulty. The system being built is a decision policy: given a math problem and a compute budget, it selects which inference strategy (search algorithm, revision depth, parallel sampling ratio) to deploy so that the probability of producing the correct answer is maximized. The problem it solves is that no single test-time strategy works best across all prompts — beam search can hurt easy problems, sequential revisions can waste compute on hard problems — and the solution is a difficulty-conditioned policy that routes each prompt to the strategy most likely to succeed, yielding up to 4× compute efficiency gains over uniform allocation.

3.2 Big-Picture Architecture (Diagram in Words)

The system has five major components, arranged in a feedforward pipeline with a lookup-based meta-controller:

Base LLM (PaLM 2-S*, also called Codey): The pretrained language model that generates candidate solutions. It serves as the "proposal distribution" from which all answers originate, functioning both as the few-shot prompted generator for search experiments and as the starting point for fine-tuning revision models.
Process Reward Model (PRM): A fine-tuned variant of the base LLM that scores every intermediate step of a multi-step solution, producing a scalar value between 0 and 1 representing the probability that a correct final answer can be reached from that step. Trained via Monte Carlo rollout supervision (no human labels). Used both to guide search algorithms and to select the best answer from multiple candidates via best-of-N weighted aggregation.
Revision Model: A separately fine-tuned variant of the base LLM that conditions on its own previous (incorrect) answers in context and produces improved answers sequentially. Trained on synthetic multi-turn trajectories where incorrect answers (selected for small edit distance to the correct answer) precede correct answers.
Search Algorithms: Procedures — best-of-N weighted, beam search, lookahead search — that use the PRM's per-step scores to navigate the space of possible solution paths. Different algorithms trade off exploration (how many distinct beams to evaluate) against exploitation (how aggressively to prune based on PRM scores).
Compute-Optimal Allocation Policy: A meta-strategy that, given an estimate of the prompt's difficulty and a total generation budget, selects which search algorithm (for PRM-based experiments) or which sequential-to-parallel sampling ratio (for revision experiments) to deploy. Implemented as a lookup table pre-computed via two-fold cross-validation on the test set, mapping (difficulty bin, budget) pairs to the strategy that maximizes accuracy.

Information flow: A prompt enters → the difficulty estimator bins it into one of five quintiles based on the PRM's average final-answer score across many samples (or, in oracle mode, based on the base model's ground-truth pass@1 rate) → the allocation policy looks up the best strategy for that (bin, budget) pair → the selected strategy executes (base LLM generates candidates, PRM scores them, aggregation selects the final answer) → the final answer is returned.

3.3 Roadmap for the Deep Dive

First, the formal compute-optimal objective (Equation 1 in the paper), which defines mathematically what "optimal" means, why it depends on prompt identity, and how difficulty enters as the conditioning variable.
Second, the difficulty estimation mechanism, since it is the linchpin that enables adaptive allocation — both the oracle version (using ground-truth pass@1) and the predicted version (using the PRM's own score distribution), and the cross-validation protocol that prevents overfitting.
Third, the PRM verifier — how it is trained (Monte Carlo rollouts with soft labels), how it scores solutions at inference time, how step-level scores are aggregated into a single solution-level score, and how solution-level scores are aggregated across candidates (best-of-N weighted selection).
Fourth, the three search algorithms (best-of-N weighted, beam search, lookahead search) — their precise mechanics, their cost models (what counts as "one generation"), and their difficulty-dependent behavior.
Fifth, the revision model — how training data is constructed (edit-distance-based pairing, multi-turn trajectory synthesis), how inference proceeds (sequential chain generation, context window management), how the correct-to-incorrect reversion problem is mitigated, and how sequential and parallel sampling are combined into a unified budget allocation.
Sixth, the FLOPs-matched comparison framework — how total compute (pretraining + inference) is accounted for, how the ratio $R = D_{\text{inference}} / D_{\text{pretrain}}$ governs the tradeoff, and how the $14\times$ larger baseline model is constructed.

3.4 Detailed, Sentence-Based Technical Breakdown

The Compute-Optimal Objective

The paper formalizes the test-time compute allocation problem as a constrained optimization over strategy hyperparameters, drawing an explicit parallel to compute-optimal pretraining scaling laws (Hoffmann et al., 2022) but applied at inference time. The objective appears in Section 3.1 of the paper.

Let $q$ be a prompt (a specific question drawn from the test distribution), let $y^*(q)$ be the ground-truth correct answer, let $N$ be the total compute budget measured in number of generated solutions (so $N = 4$ means the system is allowed to generate 4 complete candidate answers), and let $\theta$ be a vector of hyperparameters that determines how that budget is spent — which search algorithm, what beam width, what ratio of sequential to parallel sampling, depending on which family of methods is being used.

Define $\text{Target}(\theta, N, q)$ as the probability distribution over output tokens induced by the model under strategy $\theta$ with budget $N$ on prompt $q$ . This is not the raw base model distribution — it is the distribution after the strategy modifies it through search, revision, verifier-based selection, or any combination thereof. The compute-optimal strategy for prompt $q$ is:

$\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 vector for this specific question and budget, $\arg\max_\theta$ means "choose the $\theta$ that maximizes the following quantity," $\mathbb{E}_{y \sim \text{Target}(\theta, N, q)}$ means "take the expected value over answers $y$ drawn from the strategy-induced distribution," and $\mathbb{1}_{y = y^*(q)}$ is the indicator function that equals 1 if the sampled answer matches the ground truth and 0 otherwise.

What it computes: for a given question $q$ and budget $N$ , it evaluates every candidate strategy $\theta$ by simulating what happens when that strategy is executed — generating answers, scoring them, selecting the final answer — and measuring the fraction of the time the selected final answer is correct. The optimal strategy is the one that maximizes this correctness probability. Operationally, this means the system needs to pre-compute, for each question and each budget level, which $\theta$ works best, and then at test time, given a new question, select that $\theta$ .

Why this form: the key insight encoded in the subscript $q, y^*(q)$ is that the optimal strategy depends on the specific question, not just on the budget $N$ . A strategy that maximizes correctness on an easy algebra problem may be suboptimal on a hard geometry problem at the same budget. The optimization is defined per-question to make this dependence explicit. The use of expectation over the strategy-induced distribution (rather than, say, the maximum-likelihood answer under the distribution) is important because these strategies are stochastic — beam search with sampling, best-of-N with temperature, revision chains with random sampling — and the system needs to optimize the long-run success rate, not just the best-case behavior. The indicator function $\mathbb{1}_{y = y^*(q)}$ makes this a 0-1 loss, which is appropriate for MATH where answers are scored as correct or incorrect with no partial credit.

Because solving this exact optimization for every prompt at deployment time is intractable (it would require running every candidate strategy on every question to see which works best, which consumes the compute budget many times over), the paper approximates it by conditioning on a single sufficient statistic: estimated question difficulty. The approximation replaces $\theta_{q, y^*(q)}^*(N)$ with $\theta_{\text{bin}(q)}^*(N)$ , where $\text{bin}(q)$ maps the prompt to one of five difficulty quintiles, and the optimal strategy is selected per bin rather than per question. This collapses the infinite space of possible questions into five discrete categories, making the optimization tractable at the cost of some granularity — all questions within the same difficulty bin receive the same strategy.

Difficulty Estimation

The difficulty of a prompt is defined relative to the base LLM's capabilities, not relative to the MATH dataset's hand-labeled difficulty levels (which range from Level 1 to Level 5 based on human judgments of problem complexity). The paper explicitly states in Section 3.2 that the model-specific difficulty bins are more predictive of test-time compute efficacy than the dataset's built-in labels, because a problem that is "Level 5 hard" for humans might be easy for PaLM 2-S* if it appears frequently in the pretraining data, and vice versa.

What difficulty means operationally: the difficulty of question $q$ is the base model's pass@1 rate — the fraction of 2048 independently sampled complete solutions that are correct. A question where the base model gets the right answer 80% of the time on a single attempt (pass@1 = 0.8) is "easy"; a question with pass@1 = 0.001 is "hard." The threshold between easy and hard is not an absolute number but a relative ranking: questions are sorted by pass@1 and partitioned into five equal-sized quintiles, with quintile 1 containing the 20% of questions with the highest pass@1 and quintile 5 containing the 20% with the lowest.

Oracle difficulty (used for analysis and as an upper bound): for each of the 500 test questions, the authors generate 2048 full solutions from the base model (few-shot prompted, at sampling temperature likely elevated to ensure diversity — the paper does not specify the exact sampling parameters for difficulty estimation, but the base model's standard few-shot prompt with 4 exemplars is described in Appendix G). They then compute the fraction of these 2048 answers that match the ground-truth answer using the MATH grading function. Questions are binned into five quintiles of 100 questions each based on this fraction. This requires knowing which answers are correct, hence "oracle" — it cannot be done at deployment time without ground-truth labels, but it provides a clean difficulty signal for analyzing how strategies behave as a function of difficulty.

Predicted (model-based) difficulty (used for practical deployment): since oracle difficulty requires ground-truth labels, the paper approximates it by replacing the ground-truth correctness check with the PRM's own confidence. Specifically, for each question, they generate the same 2048 samples, score each one with the PRM using last-step aggregation (the PRM's predicted correctness probability at the final step of the solution), and average these 2048 scores. This average score — the PRM's average confidence that the base model produces correct answers for this question — serves as a proxy for the true pass@1 rate. Questions are then binned into five quintiles based on this average score. The intuition is that if the PRM is well-calibrated, questions where the PRM assigns high average scores will be questions where the base model actually has high pass@1, and vice versa.

Why this works (and when it might not): the PRM's scores correlate with true difficulty because the PRM is trained on the base model's own outputs via Monte Carlo rollouts — it learns to predict, for each step, the probability that completing from that step yields the correct answer. When averaged over many complete solutions, this per-solution score becomes an estimate of the base model's success rate on that question. The paper shows in Figures 4 and 8 that the predicted bins track the oracle bins closely, with the curves "largely overlapping" for search and showing a modest gap (roughly 3 percentage points at the highest budgets) for revisions. However, the calibration is not perfect — a PRM that systematically overestimates the base model's capability on certain question types would produce mis-ranked difficulty bins, potentially routing questions to suboptimal strategies.

The cost problem: generating 2048 samples and scoring them with the PRM is extremely expensive — more expensive than many of the test-time budgets being studied (which range from 1 to 512 generations). The paper explicitly acknowledges this 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"

This means the difficulty estimation cost is not included in the reported generation budgets. The $4\times$ efficiency gains are computed after difficulty is already known, so they represent an upper bound on what is achievable in a deployment where difficulty must be estimated from scratch for each prompt. The authors frame this as an exploration-exploitation tradeoff — compute spent assessing difficulty versus compute spent solving the problem — and flag it as a key direction for future work, suggesting that difficulty might be predictable directly from the question text using a lightweight classifier, eliminating the need for costly sampling.

Cross-validation protocol (preventing strategy selection from overfitting to the test set): if the authors simply tried every strategy on all 500 test questions for each difficulty bin and reported the best one, the reported accuracy would be optimistically biased — the "best" strategy might capitalize on noise specific to those 100 questions. To avoid this, they use two-fold cross-validation within each difficulty bin (Section 3.2). The 100 questions in a bin are randomly split into two folds of 50 each. On fold A, they evaluate all candidate strategies and select the one with the highest accuracy. They then evaluate that selected strategy on fold B and record the accuracy. The process is repeated symmetrically: select the best strategy on fold B, evaluate on fold A. The reported accuracy for that bin is the average of the two cross-validated accuracies. This means the strategy selection and evaluation are performed on disjoint subsets of questions, providing an unbiased estimate of how well the selected strategy generalizes within that difficulty bin. The same cross-validation is applied to both oracle and predicted difficulty bins.

Five difficulty quintiles (rather than continuous or finer-grained): the choice of exactly five bins is a discretization that balances two competing demands: (1) having enough questions per bin to reliably estimate which strategy works best (with 100 questions per bin and two-fold cross-validation, strategy selection is based on 50 questions), and (2) having enough bins to capture the qualitative differences in how strategies behave at different difficulty levels. Using more bins (say, 10) would give finer difficulty resolution but reduce the per-bin sample size, making strategy selection noisier. Using fewer bins (say, 3) would collapse distinct behavioral regimes — the paper shows that strategies behave qualitatively differently in bins 1 (easiest), 3 (medium), and 5 (hardest), so at least some separation is needed. Five bins is a pragmatic choice that the paper does not formally ablate.

Static bins vs. dynamic difficulty adjustment: the difficulty bins are computed once per question (using the full 2048 samples) and treated as fixed for the duration of the experiment. There is no mechanism for updating the difficulty estimate during the solution process — for instance, generating a few initial samples, observing the PRM's scores, and deciding in real-time whether to continue with the current strategy or switch. This static design simplifies the analysis but leaves on the table the possibility of adaptive policies that interleave difficulty estimation and problem-solving, which the paper flags as future work.

Process Reward Model (PRM) Training and Usage

The PRM is the central verifier component — the learned scoring function that all search methods depend on to decide which candidate solutions are promising and which are not. Unlike an Outcome Reward Model (ORM) that assigns a single scalar score to an entire completed solution, a PRM assigns a score to each intermediate step of a multi-step reasoning chain. These per-step scores represent the model's estimate of the probability that a correct final answer can eventually be reached if the solution is completed from that intermediate state — effectively a value function or "reward-to-go" estimate for the base model's sampling policy.

Why a PRM rather than an ORM? The paper provides both empirical and conceptual motivation. Empirically, Section 5.1 and Appendix F (Figure 14) show that the PRM consistently outperforms a separately trained ORM at best-of-N weighted selection, with the gap widening as the number of samples increases (at 2048 samples, PRM achieves roughly 40% accuracy vs. ORM's roughly 35%). Conceptually, a PRM provides a richer training signal because it must learn to evaluate partial reasoning — a much harder task that requires understanding the logical structure of solutions, not just pattern-matching final answers. The paper's finding that "last-step aggregation" (using only the PRM's final-step prediction, effectively treating the PRM like an ORM at inference time) works best suggests that the PRM's advantage comes from representation learning during training — the step-level supervision forces the model to develop internal representations that capture solution quality, even if only the final-step output is used at test time.

Training Procedure: Monte Carlo Rollout Supervision

The PRM is trained using the method of Wang et al. (2023), which the authors adopted after finding that the PRM800k dataset (Lightman et al., 2023) — which contains GPT-4 generated solutions with human-annotated step-level correctness labels — was "largely ineffective" for their PaLM 2 models. The authors attribute this to distribution shift: the PRM800k solutions were generated by GPT-4, which has a different output style, error distribution, and reasoning pattern from PaLM 2-S*, so a PRM trained on GPT-4 outputs does not transfer well to scoring PaLM 2 outputs. The Monte Carlo approach avoids this problem by training on the base model's own outputs.

Step 1: Generate solution candidates. For each question in the MATH training set (12,000 questions), sample 16 complete solutions from the few-shot prompted base LLM. Each solution consists of a sequence of reasoning steps terminated by a final answer. The paper does not specify the exact few-shot prompt format for PRM training data generation, but the base model's few-shot prompt with 4 exemplars is described in Appendix G for the main experiments, and it is reasonable to assume a similar format is used here.

Step 2: Generate Monte Carlo rollouts for each step. For each intermediate step of each of the 16 solutions, sample 16 completions from that step onward using the same base model (temperature presumably elevated to ensure diversity, though exact sampling parameters are not specified in the PRM training section). Each completion continues the partial solution to a final answer. The ground-truth grading function is applied to determine whether each completion's final answer is correct (matches $y^*(q)$ ) or incorrect.

Step 3: Compute soft labels. For each step, compute the fraction of the 16 rollouts that reached the correct final answer. This fraction is a number between 0 and 1 (inclusive) and serves as the soft target label for that step. A step from which all 16 rollouts produce correct answers gets a label of 1.0; a step from which none produce correct answers gets 0.0; a step from which 6 of 16 produce correct answers gets 0.375. These are "soft" labels because they are continuous probabilities rather than binary correct/incorrect judgments — they capture the stochasticity of the base model's sampling: even from a "good" intermediate step, the model might produce an incorrect answer some fraction of the time.

Why soft labels rather than binary? Binary labels (correct step vs. incorrect step, as in Lightman et al., 2023) require human judgment about whether a step is logically valid regardless of what comes after. This is expensive to collect and introduces annotator subjectivity — is a step that contains a minor arithmetic slip but correct reasoning "correct" or "incorrect"? Monte Carlo soft labels sidestep this by operationalizing "step quality" as an empirical quantity: what fraction of completions from this state succeed? This is objective, automatable, and directly relevant to search (where the PRM's job is to predict which partial solutions are likely to lead to correct answers under the base model's sampling policy). The downside is that soft labels conflate the model's capability (can it complete this reasoning correctly?) with the step's logical validity — a step that is logically flawless but leads to a conclusion the model struggles to reach will get a lower score than it "deserves," but this is exactly the information that matters for guiding search against this specific model.

Step 4: Fine-tune as a binary classifier. The base model (PaLM 2-S*) is fine-tuned to predict the soft label at each step. The model takes as input the question text and the partial solution up to and including the current step, and outputs a single scalar $\hat{y} \in [0, 1]$ representing the predicted probability that a correct final answer can be reached from this state. Training uses binary cross-entropy loss computed at every step of every solution (not just the final step):

$\mathcal{L} = -\left(y \log(\hat{y}) + (1 - y) \log(1 - \hat{y})\right)$

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

What it computes: the standard binary cross-entropy between the model's predicted correctness probability and the empirically observed success rate from Monte Carlo rollouts. For each step individually, the first term $-y \log(\hat{y})$ penalizes the model when the true success probability $y$ is high but the model's prediction $\hat{y}$ is low — the model is being too pessimistic about a good step. The second term $-(1-y) \log(1-\hat{y})$ penalizes the model when the true success probability is low but the model's prediction is high — the model is being too optimistic about a bad step. The total loss for a training example is the sum (or average, depending on implementation) of these per-step losses across all steps of all 16 solutions for that question. The result is a single non-negative scalar that drives the model to produce well-calibrated probability estimates at every step.

Why this form: binary cross-entropy is the maximum-likelihood objective for a Bernoulli target, making it the standard choice for training probabilistic binary classifiers. Since the soft labels $y$ are themselves probabilities (empirical fractions from 16 rollouts), they are well-modeled as the parameter of a Bernoulli distribution — each of the 16 rollouts is a binary trial, and $y$ is the maximum-likelihood estimate of the success probability. The binary cross-entropy objective is proper scoring rule, meaning the model's optimal prediction under infinite data and capacity is exactly the true conditional probability $\mathbb{E}[y | \text{step}]$ , which is what the PRM is trying to learn. Using mean squared error instead would produce a different calibration — MSE weights errors symmetrically across the probability range, while cross-entropy naturally penalizes confident mistakes (predicting 0.99 when the true probability is 0.1) more heavily than uncertain mistakes (predicting 0.6 when the true probability is 0.5), which is desirable for a verifier that will be used to make hard pruning decisions during search.

Training hyperparameters (from Appendix D): the optimizer is AdamW, which extends Adam with decoupled weight decay regularization. The learning rate is $3 \times 10^{-5}$ , which is a moderately small value appropriate for fine-tuning a large pretrained model. The batch size is 128 (this likely refers to 128 steps across multiple solutions, though the exact batching strategy — whether steps from the same solution are kept in the same batch or shuffled — is not specified). Dropout probability is 0.05, applied to the model's hidden representations during training to prevent overfitting. The Adam betas (coefficients for computing running averages of gradient and squared gradient) are $(0.9, 0.95)$ , which are standard values that give more weight to recent gradients in the second-moment estimate than the default $\beta_2 = 0.999$ . Early stopping is based on validation loss computed on a random 10% held-out split of the PRM800k training questions — when validation loss stops improving, training halts. Samples where the base model fails to produce a parsable final answer (e.g., the solution ends without a boxed answer, or the answer string cannot be extracted) are filtered out of the training data entirely — they provide no useful supervision signal since their correctness cannot be determined.

Why AdamW with these hyperparameters? AdamW is the de facto standard for LLM fine-tuning because it combines adaptive per-parameter learning rates (Adam) with proper weight decay that doesn't interact with the adaptive learning rates (decoupled weight decay). The learning rate $3 \times 10^{-5}$ is typical for fine-tuning models in the PaLM 2 scale range — high enough to make meaningful updates in a reasonable number of steps, low enough to avoid catastrophic forgetting of pretrained knowledge. The dropout rate of 0.05 is relatively low, appropriate when fine-tuning for a short number of epochs on a task-specific dataset where overfitting is less of a concern than underfitting. The beta parameters $(0.9, 0.95)$ reduce the memory horizon of the second-moment estimate compared to defaults, which can help when the training data distribution is non-stationary (as it might be when mixing steps from easy and hard questions).

A subtlety about validation: the validation split is taken from the PRM800k training questions, not from the MATH training split — meaning the validation data is drawn from a different distribution than the training data (PRM800k questions vs. MATH questions). This is unusual: typically validation data should be from the same distribution as training data to provide an unbiased estimate of generalization. The authors do not explain this choice, but it may reflect a practical constraint — using MATH questions for validation would reduce the already-limited training data, and the PRM800k questions serve as a "close enough" proxy for monitoring training progress, even if the absolute validation loss values are not directly comparable to training loss.

Step-Wise Score Aggregation at Inference Time

Once the PRM is trained, at inference time it produces a scalar score for every step of every generated solution. To use these per-step scores for selecting the best overall solution, the system must aggregate them into a single solution-level score. The paper compares three aggregation methods (Appendix E, Figure 13):

Minimum ("min"): take the lowest PRM score across all steps in the solution. The intuition, inherited from Lightman et al. (2023), is that a solution is only as strong as its weakest step — a single logical error should disqualify the entire chain, and the minimum score identifies the step the PRM is least confident about.
Product ("prod"): multiply all per-step scores together. Since each score is a probability (between 0 and 1), the product is the joint probability that every step is correct, assuming independence. This penalizes long solutions that have many opportunities for error, even if each individual step has high confidence.
Last ("last"): use only the PRM's prediction at the final step of the solution. This discards all intermediate step scores and reduces the PRM to effectively an ORM at aggregation time — the final score is an end-to-end correctness probability that should capture everything the PRM knows about the full solution.

The empirical finding (Figure 13): last-step aggregation performs best, achieving roughly 37% accuracy at 256 samples, compared to approximately 35% for min and 27% for product. The product performs substantially worse, likely because multiplying many probabilities produces extremely small numbers that are numerically unstable and because the independence assumption is violated — errors in consecutive steps are often correlated, so the product underestimates the true probability that all steps are correct. The min is better than product but worse than last, suggesting that the PRM's intermediate step scores contain noise that degrades the aggregate signal — a single step receiving a spuriously low PRM score (perhaps due to an unusual but valid reasoning move) drags down the min score and causes the solution to be rejected even if the PRM is confident about the final answer.

Why "last" outperforms "min," contrary to prior work: Lightman et al. (2023) and Wang et al. (2023) found that min aggregation worked best with their PRMs, which were trained with binary human labels. This paper's PRM is trained with soft Monte Carlo labels, which changes the semantics of the intermediate step scores. With binary labels, a step score near 0 means "this step is logically incorrect," and min aggregation correctly identifies solutions containing an error. With soft Monte Carlo labels, a step score near 0.3 might mean "from this state, the model succeeds 30% of the time" — not that the step is wrong, but that completing the reasoning from here is difficult for the model. Taking the minimum of such scores penalizes solutions with ambitious intermediate steps that are valid but challenging, even if the model ultimately succeeds. Last-step aggregation avoids this by looking only at the model's final assessment of the complete reasoning chain, which incorporates all the information the PRM has processed.

The PRM as representation learning: the fact that last-step aggregation (which ignores all intermediate predictions) outperforms a separately trained ORM (Appendix F, Figure 14 — PRM reaches roughly 40% at 2048 samples vs. ORM's roughly 35%) is a key finding. It suggests that the benefit of PRM training is not primarily in providing per-step guidance during search (though that is also useful), but in forcing the model to learn better internal representations by predicting correctness at every step. The step-level supervision during training acts as an auxiliary task that improves the quality of the model's understanding of solution quality, which benefits the final-step prediction even though the intermediate predictions are discarded at aggregation time. This is analogous to how multi-task learning can improve performance on a primary task by training on related auxiliary tasks.

Inter-Answer Aggregation: Best-of-N Weighted Selection

When the system generates $N$ candidate solutions (either independently for best-of-N, or as the leaves of a beam search tree), it needs to select a single final answer from among the candidates. The paper adopts the best-of-N weighted method from Li et al. (2023), which is more sophisticated than simply selecting the single highest-scoring solution.

The procedure: first, score every candidate solution using the PRM with the chosen aggregation method (last-step, in practice). Then, group solutions by their final answer — all solutions that produce the same answer string (after normalization by the MATH grading function) form a group. For each group, sum the PRM scores of all solutions in that group. The group with the largest total sum wins, and its associated answer is returned as the system's final output.

Why this works better than picking the single highest-scoring solution: the weighted sum incorporates a form of consensus. If 20 different solutions all arrive at the same correct answer, each with a moderate PRM score (say, 0.7 each), their total sum is 14.0, which will likely exceed the score of a single high-scoring incorrect solution (say, one solution with PRM score 0.95 arriving at a wrong answer — total 0.95). This makes the selection more robust to PRM errors: a single mis-scored solution cannot dominate unless its score is astronomically higher than all others. The method also naturally handles solution diversity — if the model generates many different incorrect answers each with one or two solutions, their individual group sums remain small, while the correct answer group accumulates score from all correct-leaning solutions. This is analogous to margin-based voting: the final answer is the one that has the greatest total "support" from the verifier across all sampled solutions.

Connection to the PRM aggregation choice: best-of-N weighted with last-step aggregation means the group sum for answer $a$ is $\sum_{s \in \text{solutions yielding } a} \text{PRM}_{\text{last}}(s)$ , where $\text{PRM}_{\text{last}}(s)$ is the PRM's predicted probability at the final step of solution $s$ . This is equivalent to using the PRM as an ORM for each individual solution, then summing ORM scores within answer groups — a verifier-augmented version of majority voting.

PRM vs. ORM: Direct Empirical Comparison

The paper trains a separate ORM as a baseline (Appendix F). The ORM is fine-tuned on complete solutions only, predicting a single correctness score for the entire solution, trained with binary cross-entropy against the Monte Carlo rollout success labels (same label generation procedure, but applied only at the final step). The key comparison (Figure 14): at 2048 samples, PRM best-of-N weighted achieves roughly 40% accuracy, ORM best-of-N weighted achieves roughly 35%, and majority voting (no learned verifier, just counting answer frequencies) achieves roughly 30%. The gap between PRM and ORM widens with the number of samples, suggesting that the PRM's superior scoring quality becomes more important as the search space grows and the selection decision becomes harder. This also validates the representation learning hypothesis: the PRM's step-level training produces better final-step predictions than training an ORM directly on final-step labels, even though both models see the same complete solutions and the same correctness labels at training time.

Search Algorithms Against the PRM

The paper studies three distinct search algorithms that use the PRM's step-level scores to navigate the space of possible solutions. All algorithms are illustrated in Figure 2 of the paper. They share the same input (a prompt $q$ , a generation budget $N$ ) and the same output (a selected final answer), but differ in how they allocate the budget between exploration (trying many different solution prefixes) and exploitation (deepening the most promising prefixes).

The generation budget as a universal cost unit: all search methods are compared at equal generation budgets, where one "generation" is defined as one complete sampled solution from the base LLM. This is an imperfect but pragmatic cost metric: different methods have different overheads (beam search requires PRM evaluations at each step, which cost additional forward passes, while best-of-N requires only final-step scoring), but "number of full-solution generations" captures the dominant cost — the LLM forward passes for autoregressive token generation — and keeps the comparison fair in terms of FLOPs. The paper sweeps budgets in powers of 2, typically from $2^0 = 1$ to $2^9 = 512$ generations.

Best-of-N Weighted

This is the simplest method and serves as the primary baseline throughout the paper.

Procedure:

Sample $N$ complete solutions independently from the few-shot prompted base LLM. The sampling uses temperature $T$ (the exact value is not specified in the search section but context suggests elevated temperature — probably $T > 0$ — to ensure diversity across samples).
Score each of the $N$ solutions using the PRM with last-step aggregation. The score for solution $i$ is $\hat{y}_i = \text{PRM}_{\text{last}}(s_i)$ , the PRM's predicted probability at the final step of solution $s_i$ .
Apply best-of-N weighted selection: group solutions by their final answer string, sum the scores within each group, and return the answer from the group with the highest total sum.

Cost model: exactly $N$ generations. The PRM scoring cost (one forward pass per solution) is negligible compared to the generation cost (one autoregressive forward pass per token generated) and is not included in the budget.

What this method does well: it explores the full diversity of the base model's output distribution. Each of the $N$ solutions is generated completely independently, so the method samples from the unconditional proposal distribution and relies solely on the verifier to distinguish good solutions from bad ones. This is robust when the base model produces correct solutions at a reasonable rate — if pass@1 is 10%, then with $N = 100$ , roughly 10 correct solutions are expected, and best-of-N weighted will likely identify the correct answer.

What this method does poorly: it wastes compute on solutions that are doomed from the first step. If the model's first step is nonsensical, generating the remaining 10 steps of that solution is wasted effort — a smarter algorithm would identify the bad first step early and redirect compute to more promising branches. Best-of-N has no mechanism for early pruning or adaptive allocation; every solution receives equal compute regardless of quality.

Beam Search

Beam search modifies best-of-N by introducing step-level pruning: the algorithm evaluates partial solutions after each step and discards unpromising ones before investing compute in completing them. The version implemented in this paper (Section 5.2) is a simplified variant of standard NLP beam search, adapted for the MATH setting where solutions have variable numbers of steps.

Procedure (illustrated in Figure 2, middle panel):

Initialization: sample $N$ candidate first steps from the base LLM. Each candidate is a text string representing the first reasoning step of a solution (e.g., "Let $x$ be the number of apples.").
Scoring: score each first step with the PRM's step-level prediction. The PRM takes as input the question text and the first step, and outputs $\hat{y}_{1,i} \in [0, 1]$ — the predicted probability that, starting from this first step, the model can eventually reach a correct answer.
Pruning: keep only the top $N/M$ highest-scoring first steps, where $M$ is the beam width — the number of candidate next steps to generate from each surviving prefix. The remaining steps are discarded.
Expansion: for each surviving prefix, sample $M$ candidate next steps from the base LLM conditioned on the question and the prefix so far. This produces $N/M \times M = N$ candidate prefixes of length 2, restoring the total number of active candidates to $N$ (the beam budget).
Iteration: repeat steps 2–4: score the $N$ length-2 prefixes, prune to the top $N/M$ , expand with $M$ next steps from each survivor, producing $N$ length-3 prefixes, and so on. This continues until solutions are complete (the model generates an end-of-solution token or a final answer box) or a maximum of 40 expansion rounds is reached (to prevent infinite loops on problems where the model never converges).
Selection: apply best-of-N weighted selection to the $N$ completed solutions (or the completed subset if some beams were terminated early).

Cost model: exactly $N$ generations total, same as best-of-N. The beam search generates $N$ first steps, then $N$ second steps (across all surviving beams), then $N$ third steps, etc. Since each "step" is a fraction of a full solution, the total number of tokens generated is roughly equivalent to generating $N$ complete solutions — assuming the average solution length is similar across methods. The PRM must be evaluated at every step (roughly $N \times (\text{avg steps})$ times), which is more expensive than best-of-N's single PRM evaluation per solution, but the paper treats this as negligible relative to generation cost.

Beam width configurations: the paper sweeps two beam width settings:

$M = \sqrt{N}$ (growing with budget): as the budget increases, each surviving beam gets more branching factor, allowing deeper exploration from promising prefixes. At $N = 16$ , $M = 4$ ; at $N = 64$ , $M = 8$ ; at $N = 256$ , $M = 16$ .
$M = 4$ (fixed): the branching factor stays constant regardless of budget, meaning more beams survive pruning as $N$ increases. At $N = 16$ , $N/M = 4$ beams survive; at $N = 64$ , $N/M = 16$ beams survive; at $N = 256$ , $N/M = 64$ beams survive.

What beam search does differently from best-of-N: it introduces a bias-variance tradeoff in solution space. Best-of-N has high variance — it samples $N$ completely independent trajectories, some of which are excellent and some of which are terrible. Beam search reduces variance by pruning obviously bad trajectories early, focusing compute on the most promising prefixes. However, this introduces bias if the PRM makes systematic errors — trajectories that the PRM scores poorly but that would have led to correct answers are pruned and never completed. The difficulty-dependent results in Figure 3 (right) show exactly this tradeoff: on medium problems (bins 3–4) where the PRM's guidance is reliable, beam search improves over best-of-N; on easy problems (bins 1–2) where the PRM's scores are less informative (because most steps are high-scoring and the signal-to-noise ratio is poor), beam search over-optimizes and hurts performance at high budgets.

Over-optimization failure mode: the paper provides qualitative evidence in Appendix M (Figure 29) that beam search can produce degenerate solutions that score highly under the PRM but are incorrect. Specific patterns include repetitive low-information steps at the end of solutions (the model generates padding text that the PRM scores as "safe" because it doesn't introduce errors) and overly short 1–2 step solutions that jump to a plausible-sounding but wrong answer. These exploit the PRM's blind spots — the PRM is trained on the base model's natural output distribution, and beam search's aggressive pruning produces a different distribution that the PRM is not calibrated for.

Lookahead Search

Lookahead search is a modification of beam search that improves the accuracy of step-level scoring by giving the PRM more context before making pruning decisions. The intuition is that the PRM's score at step $t$ might be unreliable because the partial solution is incomplete — but if the system simulates a few more steps forward (using a deterministic or low-temperature rollout), the PRM's score at the end of that rollout will be more informed, since it sees more of the reasoning chain.

Procedure (illustrated in Figure 2, right panel):

At each pruning step, instead of using the PRM's raw score $\hat{y}_t$ at the current prefix to decide which beams to keep, the algorithm performs a $k$ -step lookahead rollout from each candidate prefix.
The rollout uses the base LLM at temperature 0 (greedy decoding) to generate $k$ additional steps beyond the current prefix. Temperature 0 is chosen to minimize variance — if the rollout were stochastic, the score would be noisy and require multiple rollouts per beam to average, multiplying the cost.
The PRM's prediction at the end of this $k$ -step lookahead — i.e., $\hat{y}_{t+k}$ , the score after $k$ additional greedily-generated steps — is used as the score for the original prefix at step $t$ .
The surviving beams are then the top $N/M$ prefixes according to this lookahead-informed score.
The actual solution steps (the ones kept in the beam) are generated by the normal sampling process, not by the temperature-0 lookahead — the lookahead is only for scoring, not for constructing the solution.

Cost model: a lookahead search with lookahead depth $k$ costs $N \times (k+1)$ generations. The $+1$ accounts for the actual solution step, and the $k$ accounts for the lookahead steps generated (and discarded) for scoring. This means that at the same nominal budget $N$ , lookahead search generates $(k+1)$ times as many tokens as beam search. For a fair comparison, the paper adjusts the budget: a lookahead search with $k = 3$ and nominal budget $N_{\text{nominal}} = 64$ has an effective cost of $64 \times 4 = 256$ generations, so it is compared against beam search and best-of-N at $N = 256$ . This makes lookahead search substantially more expensive per beam explored, which is why it underperforms at equal budget in Figure 3 (left) — the extra cost of lookahead reduces the number of distinct beams that can be explored, and the improved scoring accuracy does not compensate for the loss of exploration breadth.

Specific configurations swept (Section 5.3):

Lookahead search with $k = 3$ applied to beam search with $M = \sqrt{N}$
Lookahead search with $k = 3$ applied to beam search with $M = 4$
Lookahead search with $k = 1$ applied to beam search with $M = \sqrt{N}$

The maximum budget is 256 generations (with the effective cost adjustment for lookahead).

Relationship to Monte Carlo Tree Search (MCTS): the paper notes that lookahead search is a special case of MCTS where the stochastic exploration elements (like UCT for balancing exploration and exploitation) are removed. In full MCTS, the algorithm would maintain visit counts and value estimates for each node in the search tree, using an exploration bonus (e.g., UCB) to decide which branches to expand. Here, the PRM is already a learned value function, so the algorithm simply uses it greedily for pruning and expansion — there is no exploration bonus because the goal is to exploit the PRM's knowledge, not to learn a better value function through search. This is appropriate because the PRM is frozen at test time.

Why lookahead underperforms (Figure 3, left): at equal effective budgets, lookahead search generally achieves lower accuracy than beam search and sometimes even lower than best-of-N. The authors attribute this to the cost of lookahead reducing the effective number of beams: for $k = 3$ , a budget of 256 generations yields only $256 / 4 = 64$ distinct beams explored, while beam search at the same budget explores 256 beams. The improved scoring accuracy from the 3-step lookahead is not sufficient to overcome the factor-of-4 reduction in exploration. This is an important negative result: more sophisticated search does not automatically translate to better performance — the cost of sophistication must be accounted for, and simple beam search with more beams often beats complex lookahead with fewer beams.

Difficulty-Dependent Behavior of Search

The paper's key empirical finding about search (Figure 3, right panel) is that the relative performance of beam search vs. best-of-N reverses depending on problem difficulty. The plot breaks results into five difficulty quintiles and shows accuracy at four budget levels (4, 16, 64, 256 generations) for beam search with $M = 4$ and best-of-N weighted:

Bin 1 (easiest, highest base-model pass@1): beam search accuracy decreases from roughly 78% to 77% as budget increases from 4 to 256, while best-of-N weighted increases from roughly 68% to 88%. This is the clearest evidence of PRM over-optimization — the PRM makes mostly correct assessments on easy problems, but aggressive beam search optimization amplifies residual errors in the PRM's scoring, finding solutions that score highly but are actually wrong. Best-of-N, which does not aggressively optimize the PRM signal, continues to benefit from more samples.
Bin 2: beam search improves with budget (roughly 14% → 32%) but best-of-N weighted improves faster (roughly 14% → 60%), maintaining or widening its advantage at high budgets. The over-optimization effect is weaker than in bin 1 but still present — beam search's aggressive pruning sacrifices diversity that would have produced correct answers.
Bin 3 (medium difficulty): beam search consistently outperforms best-of-N weighted across all budgets, reaching roughly 34% vs. 23% at 256 generations. Here, the PRM's guidance is accurate enough to be useful, and the problems are hard enough that random sampling (best-of-N) has trouble finding correct solutions — the "signal" from the PRM outweighs the "noise" from over-optimization.
Bin 4: beam search shows its strongest relative advantage, reaching roughly 17% vs. 10% for best-of-N at 256 generations. The pattern from bin 3 continues — PRM guidance is essential for finding the few correct solutions among many incorrect ones.
Bin 5 (hardest, near-zero base-model pass@1): both methods hover at 1–3% accuracy regardless of budget. No method makes meaningful progress because the base model essentially never produces correct solutions even in 2048 attempts — there are no correct solutions for search to find or for PRM guidance to navigate toward. This confirms a hard boundary: test-time compute cannot create capability that the base model lacks.

Implication for the compute-optimal policy: the optimal strategy is to use best-of-N weighted on easy problems (bins 1–2) to avoid over-optimization, and beam search on medium-hard problems (bins 3–4) to exploit the PRM's guidance where it helps. The policy is implemented as a per-bin per-budget lookup: on the cross-validation fold, evaluate both methods (and both beam widths) at each budget level for each bin, select the one with highest accuracy, and apply that selection to the evaluation fold.

The Revision Model: Modifying the Proposal Distribution

While the PRM and search algorithms modify how outputs are selected (the verifier axis in the paper's two-axis framework), the revision model modifies what the model generates (the proposal distribution axis). Rather than generating independent samples and hoping the verifier picks the right one, the revision model learns to iteratively improve its own answers by conditioning on previous incorrect attempts — effectively performing a local search in answer space guided by the model's learned revision capability.

Why Fine-Tuning Is Necessary

The paper explicitly acknowledges in Section 6 that "simply prompting existing LLMs to correct their own mistakes tends to be largely ineffective for obtaining performance improvements on reasoning problems," citing Huang et al. (2023). Off-the-shelf PaLM 2-S*, when given its own previous answer and asked to improve it via few-shot prompting, does not reliably produce better answers — it often repeats the same mistake, introduces new errors, or makes cosmetic changes without fixing the core issue. The hypothesis is that the model has not been trained on the specific task of "given an incorrect answer, produce a corrected version," so it does not have the right inductive bias to perform this operation reliably.

The solution is supervised fine-tuning (SFT) on synthetic multi-turn revision trajectories, teaching the model explicitly what a good revision looks like. This follows the approach of Qu et al. (2024) but with modifications to the data generation procedure (described below).

Training Data Generation

The revision model is trained on data constructed from the base model's own outputs, following a multi-step pipeline designed to teach the model to make targeted, effective corrections. The procedure is described in Section 6.1 and Appendix H.

Step 1: Generate candidate solutions. For each question in the MATH training set (12,000 questions), sample 64 complete responses from the base LLM at "elevated temperature" (the exact value is not specified, but the purpose is to increase diversity beyond typical few-shot sampling, likely $T \geq 0.8$ or top-p sampling with $p < 1.0$ ). This produces a pool of 64 candidate answers per question, some correct and some incorrect.

Step 2: Identify correct and incorrect responses. Apply the MATH grading function to each of the 64 solutions to determine which are correct (exact answer match after normalization) and which are incorrect. The grading function normalizes answer formatting (e.g., stripping whitespace, handling equivalent fraction representations) before comparison, as described in Appendix G.

Step 3: Construct multi-turn training sequences. Each training example is a sequence of 0–4 incorrect answers followed by exactly 1 correct answer. The number of incorrect answers in the sequence (0, 1, 2, 3, or 4) is sampled uniformly at random — so 20% of training examples have 0 incorrect answers (the model just sees a question and a correct answer, like standard SFT), 20% have 1 incorrect answer followed by the correct answer, 20% have 2 incorrect, etc., up to 4 incorrect. This teaches the model to revise from varying amounts of context.

For sequences with at least one incorrect answer, the last incorrect answer (the one immediately preceding the correct answer) is selected using a specific criterion: it is the incorrect answer with the smallest character-level edit distance (Levenshtein distance) to the correct answer among all incorrect answers in the pool. The remaining incorrect answers (if any, for sequences with 2+ incorrect answers) are sampled randomly from the incorrect pool (excluding the one already chosen).

Why edit-distance-based selection? The goal is to teach the model to make targeted corrections. If the incorrect answer is completely unrelated to the correct answer (e.g., "apples" vs. "quantum mechanics"), the revision task is essentially "ignore the context and generate the correct answer from scratch" — the model doesn't learn to identify and fix specific errors. If the incorrect answer is very close to the correct answer (e.g., the same reasoning chain with one arithmetic error in the third step), the model must learn to attend to the specific mistake, preserve the correct parts of the reasoning, and modify only the erroneous part. The edit distance serves as a cheap proxy for structural similarity: an incorrect answer with small edit distance to the correct answer is likely to share the same overall approach and contain a localized error, which is exactly the kind of revision the model should learn.

A crucial difference from Qu et al. (2024): the original approach in Qu et al. (2024) used on-policy multi-turn rollouts: the model would generate an answer, receive feedback, generate a revision, receive feedback, etc., and the resulting trajectory (with intermediate incorrect answers naturally produced by the model) was used for training. This was "computationally infeasible" for the authors (likely because it requires running the full multi-turn generation loop for every training question, which is expensive at scale). Instead, they approximate the multi-turn structure post-hoc by independently sampling 64 solutions per question (which can be done in parallel), then pairing correct and incorrect answers after the fact, using edit distance to simulate the coherence of a real trajectory. The approximation means the training data is somewhat artificial — in a real revision trajectory, the incorrect revision at step $t+1$ would be the model's actual response to seeing the incorrect answer at step $t$ , so the errors would be correlated. In the post-hoc construction, the incorrect answers are independently sampled, so the correlation structure may differ from what the model encounters at inference time.

Step 4: Fine-tune the base model. The base PaLM 2-S* model is fine-tuned with standard next-token prediction (SFT) on these multi-turn sequences. Importantly, the loss is computed only on the tokens of the correct answer — the model is not trained to predict the incorrect answers, only to produce the correct answer given the question and the preceding incorrect answer(s) as context. This is a standard technique in conditional SFT: the model sees the incorrect context as input but is only optimized to generate the correct output.

Training hyperparameters (Appendix H): the optimizer is AdamW. The learning rate is $1 \times 10^{-5}$ , which is lower than the PRM's learning rate of $3 \times 10^{-5}$ — the revision task is more delicate (the model must learn to condition on and correct errors without overfitting to the specific edit-distance-selected patterns), so a lower learning rate may help preserve the base model's general reasoning capabilities. The batch size is 128. Dropout is 0.0 — no dropout is applied. The paper does not explain this choice, but it may be because the training data is already noisy (the pairing of incorrect and correct answers is artificial) and additional regularization would hurt the model's ability to fit the revision patterns. Adam betas are $(0.9, 0.95)$ , same as the PRM.

A subtlety about early stopping: the authors note that "standard validation loss is not a good signal for early stopping because, after fine-tuning, the validation trajectories become off-policy" (paraphrased from the paper). The validation set consists of trajectories constructed from the base model's outputs (same procedure as training data). But after fine-tuning, the revision model generates different outputs than the base model — if you were to construct validation trajectories using the fine-tuned model's outputs, they would be on-policy, but constructing them from the base model's outputs (which is what the fixed validation set contains) means the validation data no longer matches the fine-tuned model's behavior. The incorrect answers in the validation set were generated by a different model (the base model) than the one being evaluated (the revision model), so the validation loss measures something different from what the model actually needs to do at inference time. The authors therefore select the checkpoint "slightly after the point where validation loss begins increasing" — they allow some overfitting to the training data because the validation signal is unreliable, picking a checkpoint that has trained longer than the validation loss minimum.

Inference with the Revision Model

At test time, the revision model operates in an autoregressive loop (illustrated in Figure 5 of the paper):

Initial generation: the model receives the question text and generates an initial answer (step 0). This is equivalent to a standard single-pass generation.
Revision loop: the model receives the question text followed by its own previous answer(s) as context, and generates a revised answer. This can be repeated: the model sees the question + initial answer + first revision, and generates a second revision; then the question + initial answer + first revision + second revision, and generates a third revision; and so on.
Context window management: the model was trained with a maximum of 4 previous answers in context (the sequences had 0–4 incorrect answers preceding the correct answer). At test time, the revision chain can be longer than 4 steps (the paper tests chains up to 64 revisions). To handle this, context is truncated to the most recent 4 answers — the question is always included, plus answers from steps $t-4, t-3, t-2, t-1$ (if they exist), and the model generates the answer at step $t$ . This sliding window prevents the context from growing unboundedly (which would increase computational cost and potentially exceed the model's context length) while still giving the model access to recent revision history.
Pass@1 at each step: Figure 6 (left) of the paper shows that the revision model's per-step pass@1 (the fraction of answers at step $t$ that are correct, without any verifier selection) improves from approximately 18.2% at step 1 to roughly 24–25% by steps 15–20, and remains in the 23–25% range out to 64 steps. The model's revision capability generalizes beyond its 4-step training horizon — it continues to make small improvements even in very long chains. There is a small drop at step 2 (the first revision): some correct initial answers get "revised" to incorrect answers (the reversion problem, discussed next), causing a temporary dip before the net improvement trend takes over.
The correct-to-incorrect reversion problem: a significant practical issue arises because the model was trained only on sequences where all in-context answers are incorrect (followed by a correct answer). At test time, the model may generate a correct answer at step $t$ , then at step $t+1$ , it sees this correct answer in context and — having never been trained on what to do when the context contains correct answers — may incorrectly "revise" it to a wrong answer. The paper reports (Section 6.1) that approximately 38% of correct answers get converted back to incorrect ones in the next revision step when using a naive approach that always takes the last revision's output.

Mitigation: within-chain answer selection. Instead of always taking the final revision as the system's output, the system considers all answers in the revision chain as candidates and applies verifier-based selection or majority voting across the entire chain. For a chain of $L$ revisions, there are $L+1$ candidate answers (the initial answer plus $L$ revisions). The verifier (the revision-specific ORM, discussed next) scores each candidate, and best-of-N weighted selection is applied across the chain. This means that if a correct answer appears at step 5 and gets ruined at step 6, the verifier can still select the step-5 answer as the final output, mitigating the reversion problem. The paper does not report the exact reduction in reversion rate from this mitigation, but the overall system accuracy results suggest it is effective.

Sequential vs. Parallel Sampling: The Unified Budget Allocation

The revision model introduces a new dimension to the budget allocation problem: the generation budget $N$ can be split between parallel chains (independent revision trajectories, each starting from a fresh initial answer) and sequential depth (the number of revisions within each chain). The extremes are:

Fully parallel ( $N$ chains of length 1): equivalent to best-of-N with the revision model as the generator — generate $N$ independent initial answers, score them with the verifier, select the best. No revisions are performed.
Fully sequential (1 chain of length $N$ ): generate one initial answer, then revise it $N-1$ times, producing a chain of $N$ answers. The verifier selects the best answer within the chain.
Hybrid ( $C$ chains of length $L$ , with $C \times L = N$ ): generate $C$ independent initial answers, revise each one $L-1$ times, producing $C \times L$ total answers. The verifier first selects the best answer within each chain (applying best-of-N weighted to the $L$ answers in that chain), then selects the best answer across chains (applying best-of-N weighted to the $C$ chain-best answers). This is a hierarchical aggregation procedure (described in Appendix I).

Figure 5 (right panel) of the paper illustrates this tradeoff as a two-dimensional grid: the x-axis is the number of parallel chains (decreasing left to right), and the y-axis is the sequential depth per chain (increasing left to right). The total budget is fixed at $N$ , so moving right means fewer but deeper chains.

Verifier for revisions: the PRM trained on base model outputs does not transfer well to the revision model's outputs (Appendix J, Figure 15a). This is because the revision model's output distribution is different from the base model's — the revision model has been fine-tuned to produce revisions, so its solutions have different statistical properties (e.g., they may be more verbose due to including the correction markup, or they may have different error patterns). To address this distribution shift, the authors train a separate outcome reward model (ORM) specifically on the revision model's outputs. This revision ORM is trained similarly to the base ORM: Monte Carlo rollouts from the revision model's outputs, soft labels, binary cross-entropy, same hyperparameters. The revision ORM additionally receives previous revisions in its context (the same context the revision model sees), giving it access to the same information the revision model used when generating the current answer. Appendix J, Figure 15b shows that including revision history improves verifier performance by roughly 1–2 percentage points at 64 generations — a modest but consistent gain.

Difficulty-Dependent Optimal Sampling Ratio

When results are broken out by difficulty bin (Figure 7, right panel, at a fixed budget of 128 generations), the optimal sequential-to-parallel ratio varies systematically:

Bin 1 (easiest): performance is essentially flat across all ratios, around 90–92% accuracy. Easy problems are robust to the allocation strategy — whether the system generates one long chain or many short chains, the base capability is high enough that the correct answer emerges reliably.
Bin 2: there is a slight advantage for higher sequential ratios (more revisions, fewer chains), with roughly 63% accuracy at fully sequential vs. 58% at fully parallel. The model benefits from iterative refinement on problems where its initial answers are mostly on the right track but need polishing.
Bin 3 (medium): a clear optimal ratio emerges at moderate sequential-to-parallel values (around $2^1$ to $2^3$ , meaning 2:1 to 8:1 sequential-to-parallel), reaching roughly 42% accuracy. Both extremes perform worse: fully parallel achieves roughly 35%, and fully sequential also drops off from the peak. The optimal strategy balances exploration (multiple chains to cover different high-level approaches) with exploitation (within-chain revisions to refine promising but imperfect solutions).
Bin 4: similar pattern to bin 3, with the peak at a moderate ratio achieving roughly 18% vs. 14% at fully parallel. The absolute accuracies are lower, but the qualitative shape is the same.
Bin 5 (hardest): all ratios produce roughly 2–3% accuracy. No allocation strategy helps — the base model simply does not produce correct initial answers, and revisions cannot correct what is fundamentally beyond the model's capability.

The key insight: the optimal sequential-to-parallel ratio mirrors the search algorithm findings. Easy problems benefit from exploitation (sequential refinement of roughly-correct answers — analogous to best-of-N, which avoids over-optimizing the PRM). Hard-but-solvable problems benefit from a balance of exploration and exploitation (hybrid sequential-parallel — analogous to beam search, which explores multiple beams while exploiting PRM guidance). Impossible problems benefit from neither.

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

Section 7 of the paper asks a practical resource-allocation question: given a fixed total FLOPs budget, should a practitioner spend it on training a larger model (scaling pretraining) or on giving a smaller model more inference-time compute (scaling test-time compute)? This is the training-inference tradeoff, and the paper provides a framework for comparing the two on equal footing.

FLOP Accounting

The paper uses standard approximations from the scaling laws literature (Kaplan et al., 2020; Hoffmann et al., 2022) to estimate FLOPs for both pretraining and inference. For a dense transformer model, the FLOPs per token (forward pass) are approximately $2N$ , where $N$ is the number of non-embedding parameters — one multiply-add per parameter for the forward pass (the factor of 2 accounts for the backward pass during training, which is roughly twice the forward pass).

Pretraining FLOPs: to pretrain a model, each training token requires both a forward and backward pass, plus the backward pass requires roughly twice the computation of the forward pass. The standard approximation is:

$X = 6ND_{\text{pretrain}}$

where $X$ is total pretraining FLOPs, $N$ is the number of model parameters, and $D_{\text{pretrain}}$ is the number of pretraining tokens. The factor 6 comes from: one forward pass (2 FLOPs per parameter) plus one backward pass (roughly 4 FLOPs per parameter, since the backward pass computes gradients for both activations and parameters). This is additive: $2N + 4N = 6N$ per token. So $X$ is linear in both model size and data quantity — training a model twice as large on the same data costs twice as many FLOPs; training the same model on twice as much data also costs twice as many FLOPs.

Inference FLOPs: inference requires only a forward pass (no backward pass, no gradient computation), so:

$Y = 2ND_{\text{inference}}$

where $Y$ is total inference FLOPs and $D_{\text{inference}}$ is the total number of tokens generated at inference time across all queries. The factor 2 accounts for one multiply-add per parameter per token. Total inference FLOPs scale linearly with both model size and the number of tokens generated.

Comparing a Small Model with Test-Time Compute to a Large Model

Consider two scenarios:

Scenario A (test-time compute): a "small" model with $N_S$ parameters, pretrained on $D_{\text{pretrain}}$ tokens, generating $D_{\text{inference}}$ tokens at inference time (including all the extra generation from test-time compute strategies).
Scenario B (pretraining): a "large" model with $N_L = M \times N_S$ parameters (i.e., $M$ times more parameters), pretrained on the same $D_{\text{pretrain}}$ tokens (so only model size is scaled, not data — a LLaMA-style scaling, not Chinchilla-optimal), generating the same $D_{\text{inference}}$ tokens at inference time (but without any test-time compute augmentation — just a single greedy decoding pass per query, so $D_{\text{inference}}$ is the same as the small model's single-pass inference tokens, not its augmented tokens).

The total FLOPs for each scenario are:

Scenario A total: $X_S + Y_{S,\text{augmented}} = 6N_S D_{\text{pretrain}} + 2N_S D_{\text{inference},\text{augmented}}$

Scenario B total: $X_L + Y_{L,\text{single}} = 6N_L D_{\text{pretrain}} + 2N_L D_{\text{inference},\text{single}}$

To make the comparison fair, the total FLOPs must be equal: $X_S + Y_{S,\text{augmented}} = X_L + Y_{L,\text{single}}$ . Substituting $N_L = M \cdot N_S$ :

$6N_S D_{\text{pretrain}} + 2N_S D_{\text{inference},\text{augmented}} = 6M N_S D_{\text{pretrain}} + 2M N_S D_{\text{inference},\text{single}}$

Dividing through by $2N_S$ (common factor):

$3D_{\text{pretrain}} + D_{\text{inference},\text{augmented}} = 3M D_{\text{pretrain}} + M D_{\text{inference},\text{single}}$

Solving for $D_{\text{inference},\text{augmented}}$ (the total inference tokens the small model is allowed to generate to match the large model's total FLOPs):

$D_{\text{inference},\text{augmented}} = M D_{\text{inference},\text{single}} + 3D_{\text{pretrain}}(M - 1)$

The first term, $M D_{\text{inference},\text{single}}$ , is the large model's inference token count scaled by $M$ — this is the "budget" the small model gets from the large model's inference cost. The second term, $3D_{\text{pretrain}}(M - 1)$ , is the savings from pretraining the small model — the large model's extra pretraining FLOPs get converted into additional inference tokens for the small model.

The ratio $R = D_{\text{inference}} / D_{\text{pretrain}}$ governs the tradeoff. Define $R$ as the ratio of single-pass inference tokens to pretraining tokens (for the small model):

$D_{\text{inference},\text{single}} = R \cdot D_{\text{pretrain}}$

Substituting into the budget equation and simplifying, the small model's augmented inference token budget, expressed as a multiple of its single-pass inference tokens, is:

$\frac{D_{\text{inference},\text{augmented}}}{D_{\text{inference},\text{single}}} = M + \frac{3(M - 1)}{R}$

Interpreting $R$ :

When $R$ is small ( $R \ll 1$ ), inference tokens are scarce relative to pretraining tokens. This is the regime of self-improvement pipelines or one-time evaluation — you pretrain the model once, then use it for a relatively small amount of inference. The pretraining FLOPs dominate the total budget. In this regime, the term $\frac{3(M-1)}{R}$ is large, so the small model gets a large multiplier on its inference budget. For example, with $M = 14$ and $R = 0.16$ , the multiplier is $14 + 3(13)/0.16 = 14 + 243.75 = 257.75$ — the small model can generate 258 times more inference tokens than its single-pass budget.
When $R$ is large ( $R \gg 1$ ), inference tokens are abundant relative to pretraining tokens. This is the regime of high-throughput production deployments — the model processes many queries during its lifetime. In this regime, the term $\frac{3(M-1)}{R}$ is small, so the small model's inference budget advantage shrinks. For example, with $M = 14$ and $R = 22$ , the multiplier is $14 + 39/22 \approx 14 + 1.77 = 15.77$ — only about 16 times more inference tokens.

The experimental setup: the paper uses three values of $R$ : $0.16$ (corresponding to $R \ll 1$ , the "self-improvement" regime), $0.79$ ( $R \approx 1$ , a balanced regime), and $22$ ( $R \gg 1$ , the "high-throughput" regime). For each $R$ , the small model's total inference token budget is computed using the formula above, and this budget is then used to determine how many generations $N$ the compute-optimal policy can deploy (since each generation produces a roughly fixed number of tokens, determined by the average solution length on MATH). The comparison is between PaLM 2-S* (the small model) with compute-optimal test-time scaling at budget $N$ , and a model with approximately $14\times$ more parameters (the large model) using greedy decoding (no test-time compute augmentation).

Important caveat about the large model: the paper scales only parameters, holding pretraining data fixed, following the LLaMA paradigm. This is not compute-optimal pretraining in the Chinchilla sense, where data and parameters should be scaled equally (doubling total compute should double parameters and data). A compute-optimally trained $14\times$ larger model would have more data as well, potentially performing better than the parameter-only-scaled model used here. The paper acknowledges this limitation:

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

This means the FLOPs-matched comparison may be somewhat favorable to test-time compute — the large model baseline could be stronger if it were trained compute-optimally.

Results interpretation (Figure 9): the line plots show the small model's accuracy under compute-optimal test-time scaling as a function of the generation budget (x-axis, log scale). The large model's greedy-decoding accuracy is shown as a horizontal star marker at three x-axis positions corresponding to the three values of $R$ — the x-coordinate of the star is the budget the small model can afford under that $R$ , and the y-coordinate is the fixed large model accuracy. If the small model's scaling curve at that x-coordinate is above the star, test-time compute wins; if below, pretraining wins. The findings are described in detail in the experimental analysis section of this summary; in brief, test-time compute wins on easy-to-medium problems at low-to-moderate $R$ , and pretraining wins on hard problems and at high $R$ .

4. Key Insights and Innovations

Innovation 1: Difficulty-Conditioned Compute-Optimal Test-Time Scaling as a Unified Framework

The paper's most fundamental conceptual contribution is the meta-strategy of adaptively allocating test-time compute based on prompt difficulty, framed as a direct analog of compute-optimal pretraining scaling laws (Hoffmann et al., 2022) but applied at inference time. Prior to this work, the dominant paradigm treated test-time compute as a uniform knob: turn it up, and performance improves monotonically. The few systematic studies of test-time scaling (e.g., best-of-N sampling with verifiers; Cobbe et al., 2021) assumed a single strategy applied identically to every prompt, with no mechanism for per-prompt adaptation beyond the verifier's scoring of individual solutions.

What makes this innovation fundamental rather than incremental is the finding that the relationship between compute and performance is qualitatively non-monotonic and strategy-dependent based on difficulty. The paper demonstrates that beam search — a strictly more powerful optimization method than best-of-N — actually degrades performance on easy problems at high budgets due to verifier over-optimization (Figure 3, right, bin 1), while simultaneously improving performance on medium-difficulty problems (bins 3–4). Similarly, sequential revisions dominate on easy problems, but a balanced sequential-parallel ratio is optimal on hard ones (Figure 7, right). These are not subtle quantitative differences — they are sign reversals. A practitioner using beam search uniformly because it "should be better" would be actively harming performance on a subset of their queries.

The paper's framing converts this empirical observation into a principled allocation problem by formalizing the compute-optimal objective (Equation 1), which encodes the idea that the optimal strategy $\theta^*$ is a function of the specific prompt $q$ , not just the budget $N$ . This is a conceptual shift from "how much compute should I spend?" to "how should I spend compute differently on different prompts?" — a question the field had not previously asked in a systematic way. The direct parallel to pretraining scaling laws is deliberate and clarifying: just as Chinchilla showed that pretraining FLOPs should be allocated between model size and data quantity in a budget-dependent ratio, this paper shows that inference FLOPs should be allocated between search algorithms, revision depth, and parallel sampling in a difficulty-dependent ratio.

The significance of this reframing extends beyond the empirical gains (4× efficiency improvements in Figures 4 and 8). It provides a unified explanation for conflicting prior results. The observation that self-correction works on easy problems but fails on hard ones (Section 6), combined with the finding that search helps on medium problems but over-optimizes on easy ones (Section 5.3), reconciles why Huang et al. (2023) concluded "LLMs cannot self-correct reasoning" while Madaan et al. (2023) found self-refinement helpful. These studies were implicitly testing on different difficulty distributions, and the compute-optimal framework makes the dependence explicit. This is a diagnostic contribution: it tells the field how to design experiments that produce interpretable results, by controlling for or reporting prompt difficulty.

The fact that predicted difficulty bins (using the PRM's own score distribution, without ground-truth labels) track oracle bins closely (Figures 4 and 8, "largely overlapping" curves) is what elevates this from an analytical insight to a practical contribution. If the gains required ground-truth answers to estimate difficulty, the approach would be circular. The PRM's ability to serve as its own difficulty estimator — by revealing, through its average confidence, which problems the base model struggles with — means the framework is deployable without access to labels, even though the current difficulty estimation cost (2048 samples per prompt) remains prohibitive and unaccounted for in the efficiency claims.

Innovation 2: Verifier Over-Optimization as the Primary Bottleneck in Test-Time Scaling

A second conceptual contribution — and arguably the paper's most important negative result — is the identification of verifier over-optimization as the central limiting factor that prevents test-time compute from scaling monotonically. While reward hacking and over-optimization are well-documented in the RLHF literature (Gao et al., 2022; Casper et al., 2023), this paper provides some of the first systematic evidence that the same phenomenon governs test-time search scaling and is not merely a nuisance but the dominant constraint on what test-time compute can achieve.

The evidence is layered and mutually reinforcing. At the aggregate level, beam search outperforms best-of-N at low budgets but plateaus and falls below best-of-N at high budgets (Figure 3, left), contrary to the naive expectation that more powerful optimization should yield monotonic gains. At the per-difficulty level, beam search degrades easy-problem performance as the budget increases (Figure 3, right, bin 1: accuracy drops from ~78% to ~77% as budget grows 4→256), which can only be explained by the search algorithm exploiting imperfections in the PRM's scoring — finding solutions that score highly under the PRM but are actually wrong. At the qualitative level, Appendix M documents degenerate behaviors (repetitive low-information steps, overly short solutions) that "hack" the PRM's scoring without producing genuine reasoning. And at the method-comparison level, lookahead search — the most sophisticated optimizer, which invests extra computation in making better pruning decisions — paradoxically performs worst overall (Figure 3, left), because its higher per-beam cost reduces the number of beams explored, and the improved scoring accuracy does not compensate for the lost exploration breadth.

This finding is significant beyond its empirical novelty because it redirects research priorities. Prior to this work, the natural assumption was that developing more sophisticated search algorithms (e.g., full MCTS with exploration bonuses, deeper lookahead, adaptive branching) would improve test-time scaling. The paper's evidence suggests the opposite: given the current verifier quality, simpler search with more beams beats complex search with fewer beams, and further progress requires better verifiers, not better search algorithms. The compute-optimal policy can be understood partly as a way to stay below the over-optimization threshold per difficulty level — using weaker optimization (best-of-N) where the verifier signal is fragile (easy problems) and stronger optimization (beam search) only where the signal has room to provide genuine guidance (medium problems). This frames verifier robustness as the key bottleneck for the entire test-time compute paradigm, analogous to how reward model quality emerged as the bottleneck in RLHF.

Innovation 3: Empirical Characterization of the Boundary Where Test-Time Compute Substitutes for Pretraining

The FLOPs-matched comparison in Section 7 provides the first empirical evidence — in a realistic setting without access to ground-truth answers — that a smaller model with compute-optimal test-time strategies can outperform a ~14× larger model on problems within its capability range, but fails entirely on problems beyond that range. This is not a method contribution but an empirical characterization with sharp boundary conditions that has direct implications for how compute budgets should be allocated.

Prior work on the training-inference tradeoff (Jones, 2021; Villalobos and Atkinson, 2023; Sardana and Frankle, 2023) largely assumed access to ground-truth answers at inference time (e.g., in code generation with unit tests, or in game-playing with environment rewards), which is a substantially easier setting. The paper's contribution is to demonstrate that the tradeoff still holds — but with sharp restrictions — when correctness must be estimated by a learned verifier rather than checked against ground truth. The $R = D_{\text{inference}} / D_{\text{pretrain}}$ parameterization operationalizes the tradeoff in a way that maps directly to deployment scenarios: $R \ll 1$ corresponds to self-improvement pipelines where a model is trained once and used sparingly; $R \gg 1$ corresponds to high-throughput production deployments.

What distinguishes this from a straightforward scaling experiment is the difficulty-dependent characterization of where the substitution fails. The paper does not claim universal substitutability — it shows that test-time compute provides essentially zero benefit on the hardest problems (bin 5, near 0–3% accuracy regardless of budget; Figure 9, bottom lines), even at $R \ll 1$ where the compute budget is most favorable. This establishes a clear boundary condition: test-time compute amplifies existing capability but does not create it. If the base model's pass@1 is near zero on a problem class, no amount of search or revision will help — there are no correct solutions in the proposal distribution to find or refine. This boundary is not obvious a priori: one might have hoped that revisions could bootstrap from partial progress, or that search with a PRM could guide the model toward correct reasoning even if it never samples a fully correct answer in one shot. The evidence shows this is not the case — at least for MATH with PaLM 2-S* — and this negative result is as informative as the positive results on easier problems.

The finding has immediate practical implications: for deployments where the problem distribution skews toward easy-to-medium tasks (which is likely common in production), investing in test-time infrastructure may be more cost-effective than scaling pretraining. For deployments that must handle genuinely hard problems, pretraining remains the only viable path. The paper provides a concrete framework (the $R$ parameterization, the difficulty binning, the FLOP accounting) that practitioners can use to make this determination for their specific use cases.

Innovation 4: The Proposal-Verifier Decomposition as an Empirical Organizing Principle

While the conceptual decomposition of test-time compute into proposal distribution modifications and verifier modifications (Section 2) is not itself novel — it echoes the proposer-scorer decomposition familiar from MCMC and reinforcement learning — the paper's contribution is the empirical demonstration that these two axes have complementary, difficulty-dependent strengths, and that treating them as independent dimensions produces insights that studying either in isolation would miss.

Concretely: revisions (modifying the proposal distribution) work best on easy problems where the model's initial output is roughly correct and just needs refinement — a local search in answer space (Figure 7, right, bins 1–2). Search against the PRM (modifying the verifier/selection mechanism) works best on medium-hard problems where the model needs to explore qualitatively different solution strategies — a global search (Figure 3, right, bins 3–4). Prior work studied these mechanisms independently, often reaching pessimistic conclusions about each (Huang et al., 2023 on self-correction failures; various papers on the limited gains from tree-search). The paper's framework shows these conclusions were premature: each mechanism succeeds on the right difficulty tier, and they fail on the wrong tier for different, mechanistically distinct reasons (revisions fail on hard problems because there's no correct answer to revise toward; search fails on easy problems because of verifier over-optimization).

This is more than a taxonomic exercise. It implies that future systems should not choose between revisions and search, but should deploy both and route prompts based on difficulty. The paper does not fully realize this vision — Section 8 acknowledges that PRM tree-search was not combined with revisions, leaving the combined potential as a lower bound — but the empirical characterization of their complementary strengths provides the intellectual scaffolding for doing so. The decomposition also provides a diagnostic lens: when a new test-time method is proposed, the framework suggests asking whether it modifies the proposal, the verifier, or both, and on which difficulty tier it provides gains — a structured way to understand its contribution relative to existing methods that the field previously lacked.

5. Experimental Analysis

Evaluation Methodology

Dataset. All experiments use the MATH benchmark (Hendrycks et al., 2021), a collection of high-school competition-level mathematics problems spanning seven subjects (algebra, geometry, probability, etc.). The paper uses the specific split from Lightman et al. (2022): 12,000 training questions and 500 test questions. The choice of MATH is deliberate — the authors argue test-time compute is most likely to help when the model already possesses necessary knowledge and the challenge lies in drawing complex inferences, making mathematical reasoning an ideal testbed. Answers are graded using the grading function released by Lightman et al. (2022), which normalizes formatting (whitespace, equivalent fraction representations, etc.) before comparison.
Base model(s). All experiments use PaLM 2-S* (Codey) (Anil et al., 2023). The authors state this model is "representative of the capabilities of many contemporary LLMs" and sits in a useful performance regime: non-trivial but far-from-saturated accuracy on MATH (roughly 10–19% pass@1 depending on prompting and sampling configuration), leaving substantial room for test-time compute to make a difference. For the FLOPs-matched comparison, a second model with approximately 14× more parameters is used as the pretraining-scaled baseline; this larger model is trained on the same data as PaLM 2-S* but with scaled parameter count, following the LLaMA paradigm of scaling parameters while holding data fixed.
Metrics. The primary metric throughout is MATH test accuracy (%), defined as the fraction of the 500 test questions for which the selected final answer matches the ground-truth answer according to the grading function. This is a 0–1 per-question score averaged over the test set. For difficulty-dependent analyses, accuracy is reported separately within each of the five difficulty quintiles. For the revision model's per-step analysis, pass@1 at each revision step is also reported — the fraction of answers at that step that are correct under greedy or single-sample decoding without any verifier-based selection.
Baselines. The paper uses several baselines spanning both naive and learned approaches:
- Majority voting: select the most common final answer among N independently sampled solutions, with no learned verifier. This is the simplest test-time aggregation method.
- ORM best-of-N weighted: score N complete solutions with an Outcome Reward Model (trained on the base model's final-answer correctness via Monte Carlo rollouts), then apply best-of-N weighted selection (aggregating scores by answer group and selecting the group with the highest total score). This represents the standard verifier-based approach from prior work (Cobbe et al., 2021).
- PRM best-of-N weighted: score N complete solutions with the Process Reward Model (using last-step aggregation) and apply best-of-N weighted selection. This is the verifier that all search algorithms build upon.
- Parallel sampling (for revisions): generate N independent solutions from the revision model (each solution is a single-pass generation, no iterative refinement) and select the best via verifier-based or majority-based aggregation. This is the revision model's equivalent of best-of-N — parallel exploration without sequential refinement.
Generation budget / compute accounting. The universal unit of test-time compute is one "generation," defined as one complete sampled solution from the base LLM (or revision model). For beam search and best-of-N, the budget equals the number of samples or beams N. For lookahead search with k lookahead steps, the effective cost is N × (k+1) generations to account for the additional rollout computation — so a lookahead search with k=3 and nominal N=64 beams has an effective budget of 256 generations and is compared against beam search and best-of-N at N=256. Budgets are swept in powers of 2, typically from 1 to 512 generations. The PRM's scoring cost (additional forward passes at each step) is treated as negligible relative to generation cost and is not included in the budget. For the FLOPs-matched comparison, budgets are converted to total inference FLOPs using the formula $Y = 2ND_{\text{inference}}$ and matched against pretraining FLOPs $X = 6ND_{\text{pretrain}}$ at three values of the ratio $R = D_{\text{inference}} / D_{\text{pretrain}}$ .
Cross-validation / statistical protocol. To prevent the compute-optimal policy selection from overfitting to the test set, the paper uses two-fold cross-validation within each difficulty bin on the 500-question test set. The 100 questions in each bin are randomly split into two folds of 50. For each fold independently, all candidate strategies (search algorithms, beam widths, sequential-to-parallel ratios) are evaluated on that fold, the best-performing strategy is selected, and its performance is measured on the held-out fold. This is repeated symmetrically (select on fold A, evaluate on fold B; select on fold B, evaluate on fold A), and the reported accuracy for each (bin, budget) pair is the average of the two cross-validated evaluations. This ensures strategy selection and evaluation use disjoint question sets, providing an unbiased estimate of generalization within each difficulty bin. The same protocol is applied to both oracle and predicted difficulty bins.

Main Quantitative Results

Search Against PRM Verifiers (Section 5, Figures 3 and 4)

Aggregate comparison of search algorithms (Figure 3, left). Across all 500 test questions:

At low generation budgets (2–8 generations), beam search with M=4 (fixed beam width of 4) significantly outperforms PRM best-of-N weighted. At 4 generations, beam search achieves roughly 27% accuracy versus roughly 16% for best-of-N weighted — an absolute gap of approximately 11 percentage points. This is the regime where PRM guidance provides the most leverage: when the budget is tiny, exploring many complete solutions randomly (best-of-N) has low probability of hitting a correct answer, but beam search's step-level pruning concentrates the limited budget on the most promising prefixes.
At high budgets (64–256 generations), the advantage flips. Best-of-N weighted continues to improve, reaching approximately 38% at 512 generations, while beam search (M=4) plateaus around 34% and actually falls slightly. The crossover occurs around 32–64 generations, after which beam search's aggressive pruning hurts more than it helps.
Lookahead search unperforms all methods at equal effective budget. The 3-step lookahead variants (applied to both M=sqrt(N) and M=4 beam search) generally achieve lower accuracy than either beam search or best-of-N at the same effective cost. At 256 effective generations, lookahead search with k=3 and M=4 reaches roughly 34%, comparable to beam search but not surpassing it. The 1-step lookahead with M=sqrt(N) performs similarly. The paper attributes this to the cost of lookahead reducing the effective number of beams explored — a budget of 256 generations with k=3 means only 64 distinct beams are explored, while beam search at the same budget explores 256 beams.
Majority voting trails all verifier-based methods substantially, reaching only about 29% at 512 generations — roughly 9 percentage points below best-of-N weighted and confirming that the learned verifier provides meaningful signal beyond simple answer frequency.

What these aggregate numbers hide: difficulty-dependent reversals (Figure 3, right). The panel breaks out beam search (M=4) versus best-of-N weighted at four budget levels (4, 16, 64, 256 generations) across the five difficulty quintiles. The pattern is not a uniform advantage for either method — it reverses depending on difficulty:

Bin 1 (easiest, base model pass@1 highest): Beam search accuracy decreases from roughly 78% to 77% as budget increases from 4 to 256, while best-of-N weighted increases from roughly 68% to 88%. At 256 generations, best-of-N weighted holds an 11 percentage point advantage. This is the clearest quantitative evidence of PRM over-optimization: the verifier's residual errors, which are minor at low budgets, get systematically exploited by beam search's aggressive pruning at high budgets, producing solutions that score highly but are incorrect.
Bin 2: Beam search improves from roughly 14% to 32% across the budget range, but best-of-N weighted improves faster, from roughly 14% to 60%. At 256 generations, best-of-N holds a roughly 28 percentage point advantage — larger than the gap in bin 1. The PRM over-optimization effect is still dominant: beam search prunes diversity that would have yielded correct answers.
Bin 3 (medium difficulty): Beam search consistently outperforms best-of-N weighted at all budget levels. At 256 generations, beam search achieves roughly 34% versus 23% for best-of-N — an 11 percentage point advantage. Here, the PRM's guidance is sufficiently reliable, and the problems are hard enough that random sampling (best-of-N) has low probability of finding correct answers without guidance. The PRM's value as a search heuristic outweighs the over-optimization risk.
Bin 4: Beam search shows its strongest relative advantage. At 256 generations, beam search reaches roughly 17% versus 10% for best-of-N — a 7 percentage point gap that represents a 70% relative improvement. The PRM is essential for navigating the sparse space of correct solutions.
Bin 5 (hardest, near-zero base model pass@1): Both methods hover at 1–3% accuracy regardless of budget. The lines are essentially flat and overlapping. There are no correct solutions for either method to find — the base model's pass@1 is so low that even with 256 attempts, neither strategy reliably produces a correct answer.

Compute-optimal search results (Figure 4). By selecting the best search strategy per difficulty bin at each budget level (using two-fold cross-validation to choose between best-of-N weighted, beam search with M=4, and beam search with M=sqrt(N)):

At 16 generations, compute-optimal scaling (oracle difficulty bins) achieves approximately 27% accuracy. PRM best-of-N weighted at 64 generations achieves roughly the same accuracy. This is a 4× reduction in required generations to match baseline performance.
At 256 generations, compute-optimal oracle reaches approximately 39.5%, surpassing PRM best-of-N weighted at the same budget (roughly 37%) and ORM best-of-N weighted (which peaks around 34% at 512 generations — not shown at 256 in Figure 4 but implied by the scaling trend).
Compute-optimal with predicted difficulty bins (using the PRM's average final-answer score, not ground-truth pass@1) tracks the oracle version closely. The two curves "largely overlap" per Figure 4, with the predicted version reaching approximately 37% at 256 generations — roughly 2.5 percentage points below oracle. This gap is small relative to the 4× efficiency gain over baselines and confirms that ground-truth labels are not necessary for the adaptive allocation to work.
Both compute-optimal variants consistently outperform majority voting (roughly 29% at 512 generations) and ORM best-of-N weighted at all budget levels above roughly 8 generations.

Key nuance about the 4× claim for search: the efficiency gain is computed as matching baseline performance with fewer generations — 16 generations achieving what takes 64 generations under the uniform best-of-N strategy. The claim holds across both oracle and predicted difficulty settings, though with a small gap at the highest budgets. The gain comes primarily from routing easy problems (bins 1–2) away from beam search (which hurts them) and routing medium-hard problems (bins 3–4) toward beam search (which helps them). On bin 5 problems, neither strategy helps, so the routing decision is moot.

Revision Model Results (Section 6, Figures 6–8)

Pass@1 trajectory of the revision model (Figure 6, left). Without any verifier-based selection — just measuring the per-step correctness of the answers as they emerge from the revision chain:

At step 1 (the initial answer, equivalent to a single-pass generation from the revision model), pass@1 is approximately 18.2%.
Pass@1 improves to roughly 24–25% by steps 15–20 — a gain of roughly 6–7 percentage points, or a ~35% relative improvement.
The trajectory shows a small dip at step 2 (the first revision), consistent with the correct-to-incorrect reversion problem: some correct initial answers get "revised" to incorrect ones, causing a temporary accuracy decrease before the net improvement trend dominates.
Beyond step 20, pass@1 remains in the 23–25% range out to 64 steps, showing no significant degradation from very long chains. The model generalizes beyond its 4-step training horizon, though the gains saturate around step 15–20.
This measurement is without any within-chain selection (no majority voting, no verifier). It demonstrates that the revision model genuinely learns to improve answers through iteration — the per-step accuracy increase is not an artifact of selection bias.

Sequential vs. parallel sampling (Figure 6, right). At 64 total generations, comparing fully sequential (1 chain of 64 revisions, verifier selects best within chain) against fully parallel (64 independent initial answers from the revision model, verifier selects best across them):

Sequential + best-of-N weighted: approximately 41.5%
Parallel + best-of-N weighted: approximately 39%
Sequential + majority voting: approximately 38%
Parallel + majority voting: approximately 35%

Sequential outperforms parallel under both selection mechanisms. The verifier-based gap (roughly 2.5 percentage points, 41.5% vs. 39%) is narrower than the majority-based gap (roughly 3 percentage points, 38% vs. 35%). The revision model's ability to iteratively improve answers is real and persists when controlling for the selection mechanism. The verifier adds roughly 3.5–4 percentage points over majority voting across both regimes.

Sequential-to-parallel ratio sweep (Figure 7, left). For a fixed generation budget, the paper sweeps the ratio of sequential depth to parallel breadth, from fully parallel (rightmost point on the x-axis in Figure 7 — actually leftmost in the paper's convention where they use number of chains decreasing left to right) to fully sequential. Key results at various budgets:

At 256 generations, the optimal ratio is around $2^1$ to $2^3$ (meaning 2:1 to 8:1 sequential-to-parallel — e.g., 128:2 or 32:8 in terms of chains and depth). This achieves roughly 43–44% accuracy.
Fully parallel (no revisions, all chains of length 1) yields approximately 40%.
Fully sequential (one chain of length 256) yields approximately 42%.
The curve shows a clear inverted-U shape: moderate hybrid ratios outperform both extremes, with the peak being roughly 3–4 percentage points above fully parallel.
At lower budgets (8–32 generations), the optimal ratio shifts toward fully sequential — the curves are monotonically increasing with the sequential-to-parallel ratio, suggesting that when the budget is small, iterative refinement within a single chain is more valuable than exploring multiple chains.

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

Bin 1 (easiest): Performance is essentially flat across all ratios, around 90–92% accuracy. The model's base capability is high enough that the allocation strategy doesn't matter — any approach that samples a few answers will likely find a correct one.
Bin 2: There is a slight advantage for higher sequential ratios, roughly 63% at fully sequential vs. 58% at fully parallel. The benefit is modest but consistent — easy problems that aren't trivially solvable benefit from a few rounds of refinement.
Bin 3: A clear optimal ratio emerges at moderate sequential-to-parallel values (around $2^1$ to $2^3$ ), reaching roughly 42% accuracy. Both extremes drop: fully parallel to roughly 35% and fully sequential dropping from the peak. The shape is a pronounced inverted-U.
Bin 4: Similar inverted-U shape, with the peak at a moderate ratio achieving roughly 18% versus 14% at fully parallel. The absolute accuracies are lower, but the qualitative pattern — moderate hybridization beats either extreme — replicates.
Bin 5: All ratios produce roughly 2–3% accuracy. The line is flat, confirming that no allocation strategy helps on problems where the base model never produces correct answers.

Compute-optimal revision results (Figure 8). Selecting the optimal sequential-to-parallel ratio per difficulty bin (using two-fold cross-validation):

At 64 generations, compute-optimal oracle achieves approximately 40%. This roughly matches parallel best-of-N weighted at 256 generations (which achieves roughly 41% in Figure 6 right, approximated at 256 in Figure 8) — a 4× reduction in compute to match the parallel baseline.
At 256 generations, compute-optimal oracle reaches approximately 44%, compared to roughly 41% for best-of-N weighted (the uniform parallel strategy) and roughly 37% for the parallel-only baseline.
Compute-optimal with predicted difficulty bins performs slightly below oracle at high budgets: approximately 41% at 256 generations versus oracle's 44% — a gap of roughly 3 percentage points. This is larger than the oracle-predicted gap for search (which was roughly 2.5 points) but still represents a substantial improvement over the parallel baseline.
Critically, the parallel baseline appears to plateau around 36–37% at the highest budgets tested, while compute-optimal scaling continues to improve. This suggests that the gains from adaptive allocation compound as budgets grow: at very high budgets, uniform parallel sampling saturates (more independent samples don't help if the model's single-pass accuracy has a ceiling), but adaptive allocation can redirect compute toward revisions, which continue to yield marginal improvements, or toward deeper parallel search on hard problems.

FLOPs-Matched Comparison: Pretraining vs. Test-Time Compute (Section 7, Figure 9, Figure 1 bar charts)

This comparison asks: given a fixed total FLOPs budget (pretraining + inference), is it better to train a larger model or to keep the smaller model and spend the savings on test-time compute? The PaLM 2-S* with compute-optimal test-time scaling is compared against a model with approximately 14× more parameters using greedy decoding (no test-time compute augmentation). The FLOPs are equalized using the formula described in the technical approach, with three regimes parameterized by $R = D_{\text{inference}} / D_{\text{pretrain}}$ .

Revision model vs. larger pretrained model (Figure 9, left; Figure 1, top-right bar chart). The bar chart in Figure 1 reports relative advantage of test-time compute over pretraining, broken into three aggregated difficulty groups (easy: bin 1, medium: bins 2–3, hard: bins 4–5 — note this aggregation differs from the five individual bins):

Difficulty	$R \ll 1$ (0.16)	$R \approx 1$ (0.79)	$R \gg 1$ (22)
Easy (bin 1)	+11.8%	+3.5%	−11.9%
Medium (bins 2–3)	+27.8%	+16.7%	+5.4%
Hard (bins 4–5)	+21.6%	(negative, implied)	−37.2%

These are relative improvements: positive means the small model with test-time compute outperforms the larger model; negative means the larger model outperforms.

At $R \ll 1$ (self-improvement regime), test-time compute outperforms pretraining across all difficulty levels, including hard problems (+21.6%). The massive inference budget advantage — the small model gets roughly 258× more inference tokens than its single-pass budget — overwhelms the larger model's per-token capability advantage.

At $R \approx 1$ (balanced), test-time compute wins on easy and medium problems but begins to lose on hard problems. The advantage narrows substantially: +3.5% on easy, +16.7% on medium, but the hard-problem advantage flips negative (the exact percentage is not quoted but is implied to be negative from the bar chart).

At $R \gg 1$ (high-throughput production), test-time compute only remains preferable on medium problems (+5.4%) and is substantially worse on hard problems (−37.2%). On easy problems, the small margin flips negative (−11.9%). The large model's advantage in per-token capability dominates when the inference budget multiplier is small (only ~16×).

Figure 9 (left) shows the continuous scaling curves. For each difficulty bin, the small model's accuracy under compute-optimal test-time scaling is plotted as a function of generation budget (log scale). The large model's fixed greedy-decoding accuracy is shown as a horizontal star at three x-axis positions corresponding to the three $R$ values. On bin 1 (easiest, topmost line), the scaling curve rises from roughly 82% at low budgets to roughly 90% at high budgets, above all three stars — test-time compute wins at all $R$ . On bin 5 (hardest, bottom line), the curve is essentially flat near 0–5%, below all three stars — pretraining wins universally.

PRM search vs. larger pretrained model (Figure 9, right; Figure 1, bottom-right bar chart). The results are systematically weaker for PRM search than for revisions:

Difficulty	$R \ll 1$ (0.16)	$R \approx 1$ (0.79)	$R \gg 1$ (22)
Easy	+19.1%	+2.2%	+2.0%
Medium	0.0%	−35.3%	−30.8%
Hard	−3.6%	−35.3%	−52.9%

At $R \ll 1$ , PRM search wins on easy problems (+19.1%) but barely breaks even on medium (0.0%) and loses slightly on hard (−3.6%). At $R \approx 1$ and $R \gg 1$ , PRM search loses on medium and hard problems by substantial margins (−30% to −53%). On easy problems, PRM search maintains a small advantage (+2.0–2.2%) even at high $R$ .

The revision model consistently outperforms the PRM search approach in the FLOPs-matched comparison. The paper suggests this is because revisions more directly modify the proposal distribution — generating better candidates — while PRM search only filters among candidates from an unchanged proposal distribution. When the base model's proposal distribution is weak (as on hard problems), filtering cannot compensate; when it's strong (easy problems), filtering is less necessary. Revisions, by improving the proposal distribution itself, provide gains across a broader range of difficulties.

Interpretation of the FLOPs-matched results: the core finding is the sharp boundary condition. Test-time compute with a 14× smaller model:

Can match or exceed the larger model on easy-to-medium problems, especially when inference volume is low relative to pretraining (R ≪ 1).
Cannot compensate on hard problems (bin 5) regardless of R — the scaling lines are flat near zero, meaning no amount of test-time compute helps, confirming that pretraining is the only path to capability on problems fundamentally beyond the base model's reach.
For revisions specifically, the medium-difficulty advantage persists even at R ≫ 1 (+5.4%), suggesting iterative refinement is particularly well-suited to problems the model almost-but-not-quite solves in one pass.

Ablation Studies and Robustness Checks

PRM step-wise aggregation strategy (Appendix E, Figure 13): Comparing "min" (take the lowest per-step score), "prod" (multiply all per-step scores), and "last" (use only the final-step score) for aggregating per-step PRM predictions into a single solution-level score. At 256 samples, "last" achieves approximately 37%, "min" achieves approximately 35%, "prod" achieves approximately 27%, and a separately trained ORM achieves approximately 34%. "Last" outperforms "min" by roughly 2 percentage points and "prod" by roughly 10 percentage points. This is notably contrary to prior work (Lightman et al., 2023; Wang et al., 2023), which found "min" to be best with binary human-labeled PRMs. The paper attributes the discrepancy to the soft Monte Carlo labels: with soft labels, intermediate step scores reflect completion difficulty rather than logical validity, so the minimum penalizes ambitious-but-valid steps.

PRM vs. ORM (Appendix F, Figure 14): The PRM with last-step aggregation consistently outperforms a separately trained ORM. At 2048 samples, PRM best-of-N weighted reaches approximately 40% accuracy, ORM best-of-N weighted reaches approximately 35%, and majority voting reaches approximately 30%. The gap between PRM and ORM widens with sample count: at 256 samples the gap is roughly 2–3 percentage points; at 2048 it is roughly 5 percentage points. This supports the "PRM as representation learning" hypothesis — step-level supervision during training improves the model's internal representations, which benefits final-step predictions even though intermediate predictions are discarded at aggregation time.

Revision model verifier choice (Appendix J, Figure 15a): The PRM trained on base model outputs underperforms a revision-specific ORM when scoring revision model outputs. At 64 generations, sequential + base-LM PRM achieves roughly 40% versus sequential + revision ORM at roughly 42%. This confirms distribution shift as a practical concern: the revision model's fine-tuning changes its output distribution enough that a verifier trained on base model outputs loses calibration.

Revision history in verifier context (Appendix J, Figure 15b): Including previous revisions in the ORM's context (so the verifier sees the same information the revision model used) provides a small but consistent improvement over a no-history ablation. At 64 generations, history-included reaches roughly 42% versus roughly 40.5% for no-history. Both variants outperform the parallel baseline (roughly 39%), confirming that the sequential sampling benefit is not solely attributable to the verifier seeing more context.

Oracle vs. predicted difficulty bins (Figures 4, 8; Appendix C, Figures 11–12): Both binning approaches yield qualitatively identical trends across difficulty levels. For search (Figure 4), oracle and predicted curves largely overlap, with predicted falling roughly 2.5 percentage points below oracle at the highest budgets. For revisions (Figure 8), the gap is slightly larger: roughly 3 percentage points at 256 generations (41% predicted vs. 44% oracle). Appendix C (Figures 11–12) confirms that the optimal strategy selections are similar under both binning methods — the predicted bins route problems to the same strategy category (beam search vs. best-of-N; sequential-heavy vs. balanced) as oracle bins for most budget levels. This is the critical robustness check: the compute-optimal framework works without ground-truth labels, though with a small efficiency penalty at the highest budgets.

Majority voting for revisions (Appendix B, Figure 10): The sequential-to-parallel ratio trends observed with verifier-based selection are replicated when using simple majority voting instead of the revision ORM. The same inverted-U shape appears on medium-difficulty problems, and fully sequential marginally outperforms fully parallel in aggregate. This demonstrates that the revision model's improvement from sequential sampling is not dependent on the verifier's quality — it is a genuine property of the iterative refinement process.

ReST^EM revision model (Appendix K, Figure 16): An attempt to further optimize the revision model using ReST^EM (Singh et al., 2024) — a reinforcement learning approach that iteratively trains on on-policy data — backfires substantially. At 256 generations, fully sequential performance with the ReST^EM model drops to approximately 33.5%, compared to roughly 38.5% at the optimal hybrid ratio. The sequential revision advantage collapses: the model fails to learn the revision task properly under on-policy data collection, instead amplifying spurious correlations in the training trajectories. This is a notable negative result that highlights the sensitivity of revision training to the data generation procedure — offline construction with edit-distance-based pairing appears crucial.

Critical Assessment

Claim 1: Compute-optimal scaling improves efficiency by more than 4× over best-of-N baselines. This claim is well-supported for the specific regimes where it is reported, but with important caveats about what the 4× figure actually measures.

For search (Figure 4), compute-optimal at 16 generations matches best-of-N at 64 generations on the oracle bins. For revisions (Figure 8), compute-optimal at 64 generations matches parallel best-of-N at 256 generations on oracle bins. These comparisons are valid in the narrow sense: at those specific budget levels, the adaptive strategy achieves equivalent accuracy with 4× fewer generations. However, the 4× figure is not uniform across all budget levels — at very low budgets (4 generations) and at very high budgets (512 generations), the relative advantage compresses, and the compute-optimal and baseline curves converge in some regions. A more accurate characterization would be "up to 4× improvement in the 16–256 generation range," not a universal 4× multiplier.

More importantly, the difficulty estimation cost is entirely excluded from the budget. Generating 2048 samples per question to estimate difficulty costs more than the largest test-time budgets studied (512 generations). The paper acknowledges this explicitly but does not amortize this cost in any of the efficiency claims. A deployment where difficulty must be estimated from scratch for each prompt would see far smaller net efficiency gains — potentially negative gains if the estimation cost dominates. The 4× figure is therefore an upper bound on achievable efficiency assuming difficulty can be estimated cheaply, which the paper has not demonstrated how to do. This does not invalidate the finding — the adaptive allocation is clearly better than uniform allocation once difficulty is known — but it substantially overstates the practical deployability of the method without a cheap difficulty estimator.

The cross-validation protocol is appropriate and prevents overfitting, but the per-bin sample sizes are small: 100 questions per bin, split into 50 for strategy selection, means the optimal strategy is chosen based on the performance on 50 questions. The reported accuracy for that strategy on the held-out 50 is then used as the bin's accuracy estimate. With such small evaluation sets, the sampling variance of the accuracy estimates is non-trivial — a difference of 2–3 percentage points (like the oracle-vs-predicted gaps at high budgets) may fall within one standard error. The paper does not report confidence intervals, making it difficult to assess whether the compute-optimal gains are statistically distinguishable from the baselines at individual budget levels.

Claim 2: Test-time compute with a smaller model can outperform a ~14× larger model. The claim is supported but conditional — and the conditions matter enormously. At R ≪ 1 with revisions, test-time compute wins across all difficulty levels (easy: +11.8%, medium: +27.8%, hard: +21.6%). This is the strongest evidence for the claim and represents a genuinely impressive result if the R ≪ 1 regime is realistic. However, at R ≫ 1 — which is arguably the more common deployment scenario (high-throughput production) — test-time compute loses on medium and hard problems by large margins (-30% to -53% for PRM search; -37.2% for hard problems with revisions). The claim holds only in the low-inference-volume regime, which the paper correctly identifies as corresponding to self-improvement pipelines and one-time evaluation tasks.

There are additional concerns about the strength of the pretraining baseline. The ~14× larger model is trained with the LLaMA paradigm (parameters scaled, data fixed), not with Chinchilla-optimal scaling (parameters and data scaled equally). A compute-optimally trained larger model would likely perform better, making the pretraining baseline stronger and potentially reversing some of the positive results at low R. The paper acknowledges this but does not bound the magnitude of the effect. Additionally, the larger model uses greedy decoding — no test-time compute augmentation whatsoever. A fairer comparison might give the larger model some modest test-time budget (e.g., best-of-8 or majority voting), which could close the gap on easy problems even at low R. The paper's results show what test-time compute can achieve against a static larger model, not against a larger model that also benefits from test-time compute.

Claim 3: Efficacy depends critically on prompt difficulty. This is the most robustly supported claim in the paper, replicated across search algorithms (Figure 3, right), revision strategies (Figure 7, right), and FLOPs-matched comparisons (Figure 9). The qualitative reversals — beam search hurts easy problems but helps medium ones; fully sequential is optimal on easy problems but suboptimal on medium-hard ones — are striking and consistent. The difficulty-bin analysis is the paper's strongest empirical contribution because it explains conflicting prior results and provides actionable guidance.

However, the difficulty bins are defined relative to PaLM 2-S* on the MATH dataset. The paper does not demonstrate that the same five-category discretization generalizes to other models or domains. A different model with different pass@1 distributions would produce different bin boundaries; a different task might require more or fewer bins to capture the relevant behavioral regimes. The paper's claim is that difficulty matters, not that five bins are universally optimal — and it strongly supports that claim. But the specific bin boundaries and strategy-to-bin mappings should not be expected to transfer.

Missing experiments that would have strengthened the paper:

Combined search + revisions. The paper studies PRM search and iterative revisions independently but never combines them — using the revision model as the proposal distribution within beam search, or using the PRM to guide revision decisions. This is the most obvious missing experiment and is acknowledged in Section 8. Given that the two mechanisms have complementary difficulty-dependent strengths, combining them could yield gains beyond either alone, and the current results represent a lower bound on what an integrated system could achieve.
Difficulty estimation ablation. The paper uses 2048 samples for difficulty estimation but never ablates this number. How few samples are needed for the predicted bins to remain reliable? Can difficulty be estimated from 16 or 64 samples with acceptable accuracy? This ablation would directly address the cost concern and is essential for assessing practical deployability.
Verifier quality sensitivity. The over-optimization findings are verifier-dependent. How do the difficulty-dependent patterns change as the PRM's quality improves or degrades? Training PRMs of different quality (e.g., with varying amounts of Monte Carlo rollouts) and measuring the resulting compute-optimal policies would characterize the robustness of the approach to verifier quality.
Cross-model replication. All experiments use PaLM 2-S*. Replicating the difficulty-dependent search and revision patterns on a different model family (e.g., LLaMA, Gemma, or GPT-3.5-level models) would establish whether the findings are model-specific or general. Without this, the claim that PaLM 2-S* is "representative" remains unsubstantiated.
Alternative reasoning benchmarks. MATH is a single benchmark with specific properties (competition math, exact-answer grading). Extending to code generation (HumanEval, MBPP), multi-step logical reasoning (ARC, FOLIO), or scientific QA would test the generality of the difficulty-dependent strategy patterns. In particular, tasks where correctness is harder to verify automatically (open-ended generation, creative writing) pose challenges for the verifier-based approach that are unexplored.
Latency-aware analysis. The paper measures compute in generations, ignoring wall-clock time. A strategy that allocates 128 generations as 8 parallel chains of 16 revisions each takes roughly 16× longer than 128 parallel independent samples. For latency-sensitive applications, the sequential-heavy strategies favored by the compute-optimal policy on easy problems may be impractical. A latency-matched comparison (e.g., strategies constrained to complete within a fixed time budget) would reveal the practical tradeoffs.

Overall assessment. The paper's central claim — that adaptive, difficulty-conditioned allocation of test-time compute yields substantial efficiency gains over uniform allocation — is convincingly demonstrated on MATH with PaLM 2-S*. The 4× improvement figure is real under the specific experimental conditions (oracle or PRM-predicted difficulty, excluding estimation cost), and the difficulty-dependent strategy reversals are a genuine empirical discovery that reconciles conflicting prior findings. The FLOPs-matched comparison correctly identifies the boundary conditions where test-time compute substitutes for pretraining (easy-to-medium problems, low R) and where it does not (hard problems, high R).

The primary weaknesses are the unaccounted cost of difficulty estimation (which inflates the practical efficiency gains), the single-model single-benchmark evaluation (which limits generality), the absence of combined search + revision experiments (which leaves performance on the table), and the relatively permissive pretraining baseline (parameter-scaled only, no test-time compute). These weaknesses do not undermine the paper's core contributions — they define the scope of what has been demonstrated and point clearly to the next experiments needed. The paper's value is primarily in establishing the compute-optimal test-time scaling framework and characterizing the difficulty-dependent behavior of existing methods, not in providing a turnkey deployment solution.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Excluded from All Efficiency Claims

The assumption or constraint. The entire compute-optimal framework depends on knowing the prompt's difficulty before allocating the inference budget. The paper's method for estimating difficulty — generating 2048 samples per question, scoring each with the PRM, and binning based on the average score — is extraordinarily expensive. 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"

This 2048-sample estimation procedure costs more than the largest test-time budgets studied (256–512 generations), yet it is excluded from every generation budget and efficiency calculation in the paper.

The consequence. The headline 4× efficiency gain — matching best-of-256 with only 64 generations — is computed after difficulty is already known. In a realistic deployment where difficulty must be assessed for each new prompt, the total cost would be difficulty estimation (2048 generations) + strategy execution (64 generations) = 2112 generations, compared to the uniform best-of-N baseline at 256 generations. This would represent roughly an 8× increase in total cost, not a 4× reduction. The paper's efficiency claims are therefore upper bounds that assume a cheap difficulty oracle — an oracle that does not exist and that the paper does not develop.

What evidence exists in the paper. The predicted difficulty bins (using PRM scores) track the oracle bins closely in Figures 4 and 8, confirming that the PRM can estimate difficulty without ground-truth labels. However, no experiment ablates the number of samples used for difficulty estimation — the paper never tests whether 16, 64, or 256 samples would produce sufficiently calibrated bins. The cost of the 2048-sample procedure is mentioned in Section 3.2 but never quantified in FLOPs or generations, and is not amortized across questions in any budget calculation.

Mitigation status. The paper acknowledges this gap and frames it as future work, suggesting that "pretraining or finetuning models to directly predict difficulty of a question" (Section 8) could eliminate the sampling cost. It also mentions the possibility of adaptive difficulty estimation that interleaves assessment with problem-solving. Neither approach is developed or evaluated. As presented, the limitation is entirely unresolved — a practitioner cannot deploy the compute-optimal framework as described without incurring a prohibitive difficulty estimation overhead that would negate the reported efficiency gains.

All Results Are on a Single Benchmark with a Single Model Family

The assumption or constraint. Every experiment in the paper uses PaLM 2-S* (Codey) as the base model and the MATH benchmark (500 test questions) as the evaluation dataset. The authors state in Section 4 that they "believe this model is representative of the capabilities of many contemporary LLMs" and that MATH is appropriate because test-time compute should help most when "the model has the required knowledge to solve the problem." These are assertions, not demonstrated facts — no experiments with any other model family (LLaMA, GPT, Gemma, Mistral) or any other reasoning benchmark (code generation, logical reasoning, scientific QA) are reported.

The consequence. Several findings could be model-specific or benchmark-specific in ways that materially affect their generality. The PRM's over-optimization behavior (Figure 3, right, bins 1–2) depends on the PRM's calibration properties, which are a function of the base model's output distribution and the Monte Carlo training procedure — a different base model with different error patterns could produce different over-optimization thresholds. The revision model's ability to learn from incorrect in-context examples (Section 6) 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 with exact-answer grading — it is unclear whether the difficulty-dependent strategy patterns (beam search hurting easy problems, sequential revisions helping easy problems) generalize to other reasoning domains (code generation where partial solutions can be executed and tested, multi-step planning where correctness is graded on intermediate states, open-ended tasks without clean verifiability). A practitioner using a different model on a different task cannot assume the specific bin-to-strategy mappings (e.g., "use beam search on bins 3–4, best-of-N on bins 1–2") will transfer.

What evidence exists in the paper. None. The paper contains no cross-model or cross-benchmark experiments. The claim that PaLM 2-S* is "representative" is stated without supporting evidence — no comparison to other models' pass@1 distributions, error patterns, or in-context learning behavior. The choice of MATH is motivated conceptually (reasoning-heavy, exact-answer grading) but not validated against alternatives. This is a scope limitation, not a flawed experiment — the paper demonstrates what it demonstrates on MATH with PaLM 2-S*, and the question of whether it demonstrates the same thing elsewhere is entirely unanswered.

Mitigation status. The paper does not attempt to address this limitation. It does not frame the single-model single-benchmark scope as a limitation in Section 8 (future work), focusing instead on combining search with revisions and developing cheaper difficulty estimation. A practitioner would need to replicate the key experiments — particularly the difficulty-dependent strategy comparisons — on their specific model and task before trusting the compute-optimal policy selections.

Hard Problems Remain Fundamentally Unsolved Regardless of Compute Budget

The assumption or constraint. The paper's framework assumes that test-time compute can improve accuracy by amplifying the base model's existing capability — finding correct solutions that exist in the proposal distribution but are rare, or refining nearly-correct solutions through revision. This assumption breaks down when the base model's capability on a problem class is effectively zero.

The consequence. On the hardest questions (difficulty bin 5), every method studied — PRM search, beam search, lookahead search, sequential revisions, hybrid sequential-parallel strategies — achieves near-zero improvement regardless of compute budget. In Figure 3 (right, bin 5), accuracy hovers at 1–3% for both beam search and best-of-N at all budgets from 4 to 256 generations. In Figure 7 (right, bin 5), all sequential-to-parallel ratios produce roughly 2–3% accuracy at 128 generations. In Figure 9 (bottom lines, bin 5), the compute-optimal scaling curves are essentially flat near 0–5% even as the budget increases across orders of magnitude. This is not a gradual diminishing returns — it is a hard ceiling. The paper states this explicitly in Section 7:

"on the hardest questions... essentially no amount of extra test-time compute is able to match the performance of the larger pretrained model"

For a deployment where a non-trivial fraction of queries fall into this "hard" category, the compute-optimal framework provides no pathway to acceptable performance — the system will fail regardless of how the budget is allocated, and the only remedy is to scale pretraining (a larger model, more data, or both).

What evidence exists in the paper. The evidence is stark and consistent across every figure that breaks results out by difficulty bin. Bin 5 accuracy is effectively zero (within sampling noise) for all methods and all budgets. The FLOPs-matched comparison (Figure 9; Figure 1 bar charts) confirms that on hard problems, the ~14× larger pretrained model substantially outperforms any test-time compute strategy at all values of R, with relative disadvantages of −37.2% to −52.9% for PRM search and −37.2% for revisions at R ≫ 1.

Mitigation status. The paper acknowledges this limitation honestly and does not overclaim — it frames test-time compute as amplifying existing capability, not creating it from nothing. Section 8 does not propose solutions, and none are obvious: if the base model's pass@1 is near zero on a class of problems, no search or revision strategy can find correct answers because there are no correct answers in the proposal distribution to find. This is a fundamental capability boundary that defines the scope of test-time compute's applicability. The paper's contribution is to characterize this boundary empirically, not to solve it.

Search and Revisions Are Studied Independently, Not Combined

The assumption or constraint. The paper studies PRM-guided search (beam search, lookahead search, best-of-N) and iterative revisions as separate, independent mechanisms for spending test-time compute. The search experiments (Section 5) use the few-shot prompted base model as the proposal distribution, generating independent candidate solutions that are then scored and selected by the PRM. The revision experiments (Section 6) use the fine-tuned revision model to generate chains of sequentially improved answers, with a separately trained ORM for answer selection. These two pipelines are never integrated — the revision model is never used as the proposal distribution within beam search, and the PRM is never used to guide revision decisions or prune unpromising revision chains.

The authors acknowledge this explicitly in Section 8:

"we did not experiment with PRM tree-search techniques in combination with revisions"

The consequence. The paper's results represent a lower bound on what test-time compute can achieve when both mechanisms are available. The revision model produces better candidate solutions than the base model (higher pass@1, solutions that are closer to correct), while PRM-guided search more efficiently navigates the solution space than independent sampling. Combining them — using the revision model as the generator within beam search, or using the PRM to score partial revisions and allocate compute toward the most promising chains — could yield gains beyond what either mechanism achieves alone. This is particularly relevant on medium-difficulty problems (bins 3–4), where both mechanisms individually show complementary strengths: revisions improve the proposal distribution (Section 6, Figure 7 right, showing an optimal hybrid sequential-parallel ratio) and search improves candidate selection (Section 5, Figure 3 right, showing beam search outperforming best-of-N). The paper's compute-optimal policy selects between search strategies OR revision strategies, but never combines them — meaning the true compute-optimal frontier may be higher than what is reported.

Additionally, the difficulty-dependent optimal strategies are estimated independently for search and revisions. A unified policy that could allocate budget between search, revisions, and hybrid approaches per difficulty bin was not explored, meaning the reported 4× efficiency gains may underestimate what a fully integrated system could achieve.

What evidence exists in the paper. The paper provides indirect evidence that combination would be beneficial: the revision model's pass@1 is higher than the base model's (Figure 6, left, roughly 24–25% vs. the base model's ~10–19% depending on prompting), and beam search outperforms best-of-N on medium problems (Figure 3, right, bins 3–4). But no experiment directly tests combined search + revision. This is a missing experiment, not a negative result — the paper does not claim combination would fail; it simply did not attempt it.

Mitigation status. The paper identifies this as a key direction for future work in Section 8: "future work should study the combination of both mechanisms." No preliminary results or analysis are provided to bound what the combined gains might be. A practitioner building on this work would need to design and evaluate the combined system from scratch, with no guidance from the paper on how to integrate the two mechanisms or what difficulty-dependent behavior to expect.

The Revision Model Suffers from a 38% Correct-to-Incorrect Reversion Rate

The assumption or constraint. The revision model is trained exclusively on sequences where all in-context answers are incorrect (followed by a correct target answer). This data construction choice — sampling 0–4 incorrect answers uniformly and pairing the last incorrect answer with the correct answer based on edit distance — means the model never sees examples of correct answers in context during training. As a result, it has no learned behavior for what to do when it encounters a correct answer in its revision history.

The consequence. At test time, when the revision model generates a correct answer at step t, and this correct answer appears in the context at step t+1, the model frequently "revises" it into an incorrect answer. The paper reports in Section 6.1 that approximately 38% of correct answers get converted back to incorrect ones in the subsequent revision step when using a naive approach that always takes the last revision. This reversion problem directly limits the effectiveness of long revision chains — every time the model lands on a correct answer, there is a substantial probability it will ruin that answer in the next step. Without mitigation, longer chains can oscillate between correct and incorrect answers, reducing the net benefit of sequential revisions.

The paper mitigates this by applying verifier-based or majority-based selection across the entire chain rather than always taking the final revision. This means correct answers produced at any step can be recovered even if they are later corrupted. However, this mitigation is a patch — it does not fix the underlying model behavior. The revision model continues to produce reversions at a 38% rate; the system simply selects around them. This wastes generation budget (steps spent generating and then discarding incorrect revisions of correct answers) and reduces the effective depth of revision chains that produce net improvements.

What evidence exists in the paper. The 38% reversion rate is reported in Section 6.1 without a dedicated figure, suggesting it was measured during model development. Figure 6 (left) shows a small dip in pass@1 at step 2 (the first revision), consistent with some correct initial answers being reverted. The revision model's pass@1 trajectory plateaus around steps 15–20 (Figure 6, left), which may partly reflect that beyond a certain depth, the rate of new correct answers being discovered is balanced by correct answers being reverted. The within-chain selection mitigation is described in Section 6.1 but its effectiveness at reducing the net impact of the reversion problem is not quantified — the paper does not report what the end-to-end accuracy would be without within-chain selection, making it difficult to assess how much the reversion problem costs in practice.

Mitigation status. The paper partially mitigates the problem through within-chain answer selection (verifier or majority voting across all steps in the chain), but this is an inference-time patch that does not address the root cause. A more principled solution — such as training the revision model on trajectories that include correct answers in context with a "no revision needed" output, or training with a stopping criterion that terminates the chain when confidence is high — is not explored. The ReST^EM experiment (Appendix K, Figure 16) suggests that the revision training procedure is fragile: attempting to optimize the model further with on-policy data caused performance to degrade substantially, indicating that the reversion problem may be hard to eliminate through straightforward training improvements. The paper does not propose specific mitigations for future work.

The FLOPs-Matched Comparison Uses a Weakened Pretraining Baseline

The assumption or constraint. The comparison between test-time compute (PaLM 2-S* with compute-optimal strategies) and pretraining (a ~14× larger model) in Section 7 makes two choices that favor test-time compute. First, the larger model is trained by scaling parameters while holding pretraining data fixed, following the LLaMA paradigm (Touvron et al., 2023). The authors acknowledge this explicitly:

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

Under Chinchilla-optimal scaling (Hoffmann et al., 2022), a model trained with 14× more total FLOPs would scale both parameters and data equally, likely achieving better performance than a parameter-only-scaled model at the same total FLOPs budget. Second, the larger model uses only greedy decoding — no test-time compute augmentation whatsoever (no majority voting, no best-of-N, no verifier-based selection). The paper compares a small model with an optimized test-time strategy against a large model with no test-time strategy, rather than giving both models comparable test-time budgets.

The consequence. The reported advantages of test-time compute over pretraining — for example, +27.8% relative improvement on easy questions with revisions at R ≪ 1 — are measured against a baseline that is arguably weaker than what a practitioner would actually deploy if they chose to scale pretraining. A compute-optimally trained 14× larger model would likely perform better than the parameter-scaled model used here, potentially reversing some of the positive results, especially at borderline R values (R ≈ 1) where the reported advantages are modest (+3.5% on easy, +16.7% on medium). Additionally, giving the larger model even a modest test-time budget — say, best-of-8 with majority voting or an ORM — would substantially improve its accuracy, particularly on easy and medium problems where additional samples provide the most benefit. The paper's comparison is between "small model + optimized inference" and "large model + no inference optimization," which stacks the deck in favor of test-time compute. A fairer comparison would be "small model + optimized inference" vs. "large model + modest inference optimization," reflecting what a practitioner would actually do in either regime.

What evidence exists in the paper. The paper provides no ablation of the pretraining baseline — no results for a Chinchilla-optimal scaled model, no results for the larger model with any form of test-time compute (even simple majority voting). The FLOPs accounting in Section 7 assumes the larger model's inference FLOPs are exactly the single-pass generation tokens — none of the FLOPs budget is allocated to test-time strategies for the larger model. The paper is transparent about the parameter-only scaling choice but does not discuss the no-test-time-compute-for-large-model choice as a limitation.

Mitigation status. The paper flags the parameter-only scaling limitation and defers to future work, but does not acknowledge the asymmetry in test-time compute allocation between the two models. A full accounting of the training-inference tradeoff would require a two-dimensional comparison: varying both pretraining scale (model size, data) and test-time compute budget (for both small and large models) under a total FLOPs constraint. The current comparison is a specific slice through this space that is informative but not dispositive — it shows what test-time compute can achieve against a static larger model, not what the optimal allocation between pretraining and inference compute looks like when both can be optimized simultaneously.

🎯 Pitch

1. Executive Summary

2. Context and Motivation

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

Conflicting Prior Evidence

Where Existing Approaches Fall Short

How This Paper Positions Itself

3. Technical Approach

3.1 Reader Orientation

3.2 Big-Picture Architecture (Diagram in Words)

3.3 Roadmap for the Deep Dive

3.4 Detailed, Sentence-Based Technical Breakdown

The Compute-Optimal Objective

Difficulty Estimation

Process Reward Model (PRM) Training and Usage

Training Procedure: Monte Carlo Rollout Supervision

Step-Wise Score Aggregation at Inference Time

Inter-Answer Aggregation: Best-of-N Weighted Selection

PRM vs. ORM: Direct Empirical Comparison

Search Algorithms Against the PRM

Best-of-N Weighted

Beam Search

Lookahead Search

Difficulty-Dependent Behavior of Search

The Revision Model: Modifying the Proposal Distribution

Why Fine-Tuning Is Necessary

Training Data Generation

Inference with the Revision Model

Sequential vs. Parallel Sampling: The Unified Budget Allocation

Difficulty-Dependent Optimal Sampling Ratio

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

FLOP Accounting

Comparing a Small Model with Test-Time Compute to a Large Model

4. Key Insights and Innovations

Innovation 1: Difficulty-Conditioned Compute-Optimal Test-Time Scaling as a Unified Framework

Innovation 2: Verifier Over-Optimization as the Primary Bottleneck in Test-Time Scaling

Innovation 3: Empirical Characterization of the Boundary Where Test-Time Compute Substitutes for Pretraining

Innovation 4: The Proposal-Verifier Decomposition as an Empirical Organizing Principle

5. Experimental Analysis

Evaluation Methodology

Main Quantitative Results

Search Against PRM Verifiers (Section 5, Figures 3 and 4)

Revision Model Results (Section 6, Figures 6–8)

FLOPs-Matched Comparison: Pretraining vs. Test-Time Compute (Section 7, Figure 9, Figure 1 bar charts)

Ablation Studies and Robustness Checks

Critical Assessment

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Excluded from All Efficiency Claims

All Results Are on a Single Benchmark with a Single Model Family

Hard Problems Remain Fundamentally Unsolved Regardless of Compute Budget

Search and Revisions Are Studied Independently, Not Combined

The Revision Model Suffers from a 38% Correct-to-Incorrect Reversion Rate

The FLOPs-Matched Comparison Uses a Weakened Pretraining Baseline

Adjacent in domain

MMLU: Measuring Massive Multitask Language Understanding

MLQA: Evaluating Cross-lingual Extractive Question Answering