Test-Time Scaling

Chapter 1: The Proposal & the Verifier

Chapter 0 left "spend it wide" and "spend it deep" as loose phrases. Time to make them precise, because the paper's entire analysis is organized around exactly two mechanisms, and confusing them is the single easiest way to misread every result that follows.

The proposal distribution

Every time a language model generates an answer, it is sampling from some distribution over possible output sequences — call this the proposal distribution. Ordinarily this distribution is fixed by the model's weights: give it the same prompt twice at nonzero temperature and it draws two different samples from the same underlying distribution. The first lever for test-time compute is to change what that distribution is, at inference time, using more computation — for instance, by showing the model its own previous, flawed attempt and asking it to try again. The distribution the model samples the second time is different from the distribution it sampled the first time, even though the weights never moved. Chapter 4 builds this mechanism in full: it is called revision.

It is worth naming why this cannot just be done by prompting an off-the-shelf model to critique itself. Techniques like this — usually called self-critique — do exist in the literature, and the instinct behind them is reasonable: ask the model "was that right? if not, fix it," in plain English, no extra training required. In practice, simply prompting existing LLMs to correct their own mistakes tends to be largely ineffective on genuinely hard reasoning problems — a model that got a hard step wrong the first time is often not reliably better at spotting that same mistake when asked to look again, unless it has specifically been trained for the skill of revision. Chapter 4 is that training recipe.

The verifier

The second lever leaves the proposal distribution untouched and instead spends compute on selecting among candidates it already produced. Sample several complete answers independently, score each one somehow, and keep the best-scoring one. The scoring mechanism is the verifier. The simplest possible verifier just asks the model itself, or a separate trained model, "is this final answer correct?" — one score per whole answer. A more powerful verifier, and the one this paper spends most of its search chapters on, is a process reward model, or PRM: instead of one score for the whole answer, it scores every individual step of the solution as the model writes it.

Why bother scoring every step instead of just the final answer? Because a wrong final answer usually has an identifiable moment where it went wrong — a dropped negative sign, an invalid algebraic step, a wrong case split — and a step-level score lets you catch that moment before the model has spent its entire budget finishing a doomed solution. An ORM only tells you the destination was wrong; a PRM tells you roughly where the wrong turn happened.

How the PRM is actually trained, and why the obvious way failed

Training a PRM sounds like it needs human annotators marking every step of every solution as right or wrong — and an earlier dataset built exactly that way, called PRM800k, already exists (Lightman et al., 2023). The authors tried using it directly on their PaLM 2 models and it did not work: naive strategies like plain best-of-N sampling could exploit a PRM trained on that data, almost certainly because PRM800k's step labels came from GPT-4-generated solutions, and the distribution of what a PaLM 2 model actually writes is different enough that the PRM's judgments transferred badly.

The fix is to generate step labels without any human annotation at all, following an approach from Wang et al. (2023): run many Monte Carlo rollouts continuing from each step in a solution, and use how often those rollouts eventually reach the correct final answer as a soft, automatically-computed correctness label for that step. A step is "good" if continuing from it usually leads somewhere correct; "bad" if it usually doesn't. The PRM is then trained as a binary classifier — predicting a value between 0 and 1 at every step — against these soft labels with a binary cross-entropy loss.

Here y is the soft ground-truth value from the Monte Carlo rollouts (a number between 0 and 1, not just 0 or 1), and ŷ is the PRM's own prediction at that step. Every single step of every training solution gets exactly this kind of label, generated entirely by rolling the base model forward and checking final answers — not by paying a human to read the step and judge it.

A worked check on the loss, by hand

Make the formula concrete with one made-up but representative pair of numbers, exactly the way you would sanity check any classifier's loss before trusting a training run. Suppose one training step has a Monte-Carlo soft label of y = 0.80 (80% of rollouts from this step reached the correct answer), and the PRM — still early in training — currently predicts ŷ = 0.55 for that same step:

Now check the limiting case that makes binary cross-entropy trustworthy in the first place: if the PRM's prediction had matched the label exactly (ŷ = 0.80), the loss drops to about 0.50 — lower, as it should be, since a closer prediction is always penalized less. Push the prediction further away, say ŷ = 0.10 against the same y = 0.80 label, and the loss jumps to roughly 1.86 — confidently wrong costs much more than uncertain. This is the exact loss every single step of every training solution is scored against, at scale, across the whole PRM800k-replacement dataset.

The practical training details, for the record

Concretely, the PRM is finetuned from the same base model using AdamW, learning rate 3e-5, batch size 128, dropout 0.05, and Adam betas (0.9, 0.95) — unremarkable, standard finetuning hyperparameters, worth naming because they underline a point easy to miss: nothing exotic about the optimizer makes this work. The genuinely novel piece is entirely in how the training labels get generated (via Monte Carlo rollouts, not human annotation), not in any special machinery layered on top of ordinary supervised finetuning. Early stopping selects the checkpoint with lowest validation loss on a held-out 10% of the original PRM800k questions — reused here only as a fixed set of problems to validate on, not as a source of step labels.

What the PRM's score actually represents

Because the label at each step is "probability that continuing from here eventually gets the right answer," the PRM's per-step prediction has a precise interpretation: it is an estimate of reward-to-go — how much reward you should expect from this point forward, given everything written so far. This matters for aggregation: when the authors need to turn a full solution's many per-step scores into one number (to rank candidate answers against each other), they tried several combination rules — taking the product of all step scores, taking the minimum — and found that simply using the PRM's prediction at the very last step worked best of everything they tried. That single number already summarizes the whole trajectory, because reward-to-go at the last step already reflects everything that came before it, propagated forward through every earlier step's own reward-to-go estimate.

It is worth reasoning through why the alternatives underperform, even without a stated explanation from the authors. Taking the product of every step's score compounds a penalty: multiply enough numbers each a little below 1.0 together, and a long, entirely correct solution can end up with a lower aggregate score than a short one, purely from having more steps to multiply through — the metric starts penalizing thoroughness itself. Taking the minimum has the opposite problem: it lets a single momentary dip in confidence, even one the model fully recovers from two steps later, dominate the entire answer's score, discarding everything the later steps corrected. The last-step score sidesteps both failure modes by construction, since it is defined to already reflect the accumulated state of the whole trajectory, not a raw combination of independent per-step numbers.

This is exactly what lets the search methods in Chapter 3 prune a bad trajectory at step 3, rather than only discovering the mistake once the whole answer is finished at step 4. A verifier that could only look at the finished product would never have seen this drop happening in real time.

The verifier's own compute cost, accounted for honestly

Tie this back to Chapter 0's framing of FLOPs as the common currency: running a verifier is not free. An ORM adds one extra forward pass per finished candidate — cheap, a single scalar score read off the model's final hidden state at the end of the sequence. A PRM is more expensive by construction: to get a reward-to-go estimate at every step, it needs, in principle, one prediction per step boundary, though in practice these are batched together efficiently rather than run as fully separate forward passes. Either way, every search method built in Chapter 3 pays for two things every round: the generator producing candidate steps, and the verifier scoring them. Any FLOPs accounting of "how much did this search cost" that only counts the generator's tokens is undercounting — a detail easy to lose sight of once the algorithms get more elaborate.

Hold both mechanisms side by side one more time before moving on, because Chapter 4 is about to build the proposal side in full, and it helps to already know exactly what shape that construction is aiming for. A verifier is comparatively simple to reason about: it never changes what gets generated, only what gets kept, so its entire job is to be an accurate judge. A proposal-distribution change is a fundamentally different kind of engineering problem: it has to actually produce better candidates in the first place, not merely judge existing ones — which is exactly why, as the next section already previewed, it needs its own dedicated finetuning rather than a prompt trick.

Checked against an ORM baseline, not just asserted

It is reasonable to ask whether the extra machinery this chapter builds — Monte Carlo rollouts, soft per-step labels, a full per-step classifier — is actually worth it, compared to training the simpler verifier from this chapter's own opening comparison: an outcome reward model (ORM) that scores only the finished answer. The paper runs exactly this check, training an ORM on the same base model and comparing it directly against the PRM at matched search budgets. The finding, stated plainly: their PRM consistently outperforms the ORM baseline, which is exactly why every search experiment in the chapters ahead uses the PRM, not an ORM standing in for it.

Trace why this makes sense using the same toy four-step solution from earlier in this chapter (Step 1–4, sign error introduced at step 3). An ORM sees exactly one thing: the finished answer at step 4, wrong. It has no way to represent "the first two steps were fine; something went wrong specifically at step 3." A PRM, by construction, produces the full trajectory of four numbers — 0.91, 0.88, 0.12, 0.09 — and that trajectory is itself the signal a search method like beam search (Chapter 3) prunes on mid-generation. Collapse those four numbers down to the ORM's single end-of-sequence score, and the specific location of the mistake — along with everything a beam search or lookahead search could do with that location — disappears entirely. An ORM can still rank finished answers reasonably well; what it categorically cannot do is guide search while an answer is still being written, because it has nothing at all to say about a solution that isn't finished yet.

A second worked check on the loss, further along in training

Earlier this chapter worked one BCE loss example early in training, where the PRM's prediction (ŷ = 0.55) was still far from the label (y = 0.80). Worth checking the same formula once more at a point representing a PRM further along in training, to see the loss actually behave the way a real training curve should. Suppose, later in training, the PRM has learned to predict ŷ = 0.77 for that same step, with y = 0.80 unchanged:

Compare directly against the chapter's original number: loss drops from 0.638 (at ŷ = 0.55) to 0.503 (at ŷ = 0.77) — a real, checkable improvement as the prediction moved closer to the 0.80 label, exactly the shape a training curve should show, worked by hand rather than just asserted. This single computation, repeated across every step of every training solution, thousands of times over a full PRM training run, is the training curve; there is no additional machinery hiding underneath it.

One more piece worth naming explicitly, since the hero prerequisites for this session name reinforcement learning directly: the term reward-to-go is not PRM-specific vocabulary, borrowed and renamed. It is exactly the RL concept of the same name — the expected sum of future reward from a given state onward under a fixed policy — applied here to a policy that is simply "the base LLM's own token-sampling distribution," and a reward that is simply "1 if the eventual final answer is correct, 0 otherwise." The PRM is, underneath the training-data engineering, a learned value function for that specific policy and that specific sparse, end-of-episode reward — the exact object this session's stated RL prerequisite already equipped you to recognize.

Framed that way, Chapter 3's beam search is nothing more exotic than greedy, value-guided rollout selection against a fixed, pre-trained value function — a description that should sound entirely familiar to anything you already know about acting greedily with respect to a learned value estimate. No new RL machinery gets introduced anywhere in this session; every mechanism reuses concepts a first pass through policy-gradient RL already builds.

Chapter 2: Difficulty Is the Hidden Variable

Every result in this session eventually traces back to one methodological choice: instead of asking "does method X beat method Y on average," the authors ask "does method X beat method Y for this specific question." That reframing needs a way to measure how hard a question is — and it needs to be a way that doesn't secretly require already knowing the answer.

Difficulty, defined operationally

The definition follows Lightman et al. (2023): take the base LLM, and for every question in the test set, sample it 2,048 times and check what fraction of those samples land on the correct final answer — this is the question's pass@1 rate from the model's own perspective. A question the model gets right in 1,800 of 2,048 tries is easy for it; a question it gets right in 4 of 2,048 tries is hard for it — not hard in some abstract mathematical sense, hard specifically for this model. Sort every question in the test set by this pass@1 rate and split them into five equal-sized groups, or quantiles: Bin 1 is the easiest fifth of questions, Bin 5 is the hardest fifth.

The arithmetic, worked by hand for one question

Nothing about pass@1 is mysterious once you see it computed once. Suppose a single MATH question gets sampled 2,048 times from the base model, and 410 of those samples land on the correct final numeric answer:

That single number, one per question, is the entire input to the binning procedure. With 500 test questions split into 5 equal quantiles, each bin ends up holding exactly 100 questions — sorted by this pass@1 number, the 100 questions with the lowest pass@1 land in Bin 5 (hardest), the 100 with the highest land in Bin 1 (easiest). A question with pass@1 = 0.200, like the one just computed, would land somewhere in the middle of the distribution, not at either extreme — genuinely medium difficulty for this specific model, on this specific question.

Why 2,048 samples, and not far fewer

Pass@1, estimated from a finite number of samples, is itself a noisy measurement — it is a sample proportion, and sample proportions get more reliable the more samples go into them, exactly the way flipping a coin 2,048 times gives you a far tighter estimate of its true bias than flipping it 8 times would. A question with a true pass@1 of 20% estimated from only 8 samples might easily show 1 or 2 out of 8 (12.5% or 25%) purely from sampling noise, potentially shuffling that question into a neighboring difficulty bin by accident. Estimated from 2,048 samples, that same true 20% rate is going to land within a percentage point or two of 20% almost every time — the bin assignment becomes a property of the question and the model, not an artifact of how unlucky or lucky one particular small batch of samples happened to be. The entire compute-optimal strategy downstream depends on bins being assigned correctly and consistently; a noisy difficulty estimate would quietly corrupt every strategy choice built on top of it.

Why bin by the model's own success rate instead of, say, the difficulty labels the MATH dataset itself ships with? Because the authors found their model-specific pass@1 bins were more predictive of which test-time strategy would work well than the dataset's own hand-labeled difficulty categories were. A problem a human grader calls "hard" might still be one a specific model already solves reliably; what matters for choosing a test-time strategy is the model's own relationship to the problem, not an outside opinion about it.

One consequence worth drawing out explicitly: because pass@1 is a property of the pair — this model, on this question — not of the question alone, difficulty bins are not a fixed, universal labeling of the MATH test set. Swap in a stronger base model and recompute pass@1 across all 500 questions, and the bins would very plausibly reshuffle: a question that sat in bin 4 for a weaker model might land in bin 2 for a stronger one, simply because the stronger model solves it more often now. Every difficulty-conditioned result in this session is therefore implicitly tied to the one base model (PaLM 2-S*) it was measured against — upgrading the base model would mean recomputing the bins from scratch, not simply reusing the old assignments with a better model dropped in underneath them.

This is also the clearest illustration of why a single averaged accuracy number, reported across an entire benchmark, hides more than it reveals. Two search methods that land on the exact same overall MATH accuracy could be getting there in completely different ways — one winning comfortably on easy questions and losing badly on hard ones, the other doing the reverse — and an aggregate score would report them as tied. Only by looking difficulty bin by difficulty bin, exactly as this chapter sets up, does the actual shape of each method's strengths and weaknesses become visible at all. Every table in Chapters 3 through 6 that reports results "by difficulty bin" rather than as one blended number is making this exact choice on purpose.

There is a quieter throughline connecting this chapter back to Chapter 1, worth noticing explicitly: both are, structurally, the same move. The PRM was trained by generating many Monte Carlo rollouts from a step and using how often they eventually reach the correct answer as that step's soft correctness label. Pass@1 is the exact same computation, one level up: generate many rollouts from an entire question and use how often they reach the correct answer as that question's difficulty label. One measures the reliability of a partial solution; the other measures the reliability of the whole model on a whole question. Underneath, both are the same operation — sample repeatedly, check against ground truth, average — applied at two different granularities of the same problem.

The problem: you can't cheat and look at the answer

There is an obvious hole in this scheme: computing pass@1 requires checking every one of those 2,048 samples against the true correct answer — something you obviously don't have at real deployment time, when a user asks a genuinely new question you don't already know the answer to. The authors call this version oracle difficulty: useful for research, because it isolates "does difficulty-conditioning work at all" from "can you estimate difficulty without cheating," but not something you could ship.

The practical substitute is model-predicted difficulty: run the same binning procedure, but instead of checking against ground truth, average the PRM's own final-answer score across the same 2,048 samples. No ground truth required — just the verifier you were probably already going to run anyway. The two difficulty measures are compared directly throughout the paper's later result curves, and they track each other closely: model-predicted difficulty recovers nearly all the benefit of oracle difficulty, without ever touching the correct answer.

Avoiding a subtle statistical trap

One more piece of care worth naming: if you use the same test set both to decide which strategy wins in each difficulty bin and to report how well that winning strategy performs, you're peeking at the answer twice with the same data — a classic overfitting trap. The fix is two-fold cross validation: split each difficulty bin's questions into two halves, pick the best-performing strategy using half A, then measure that chosen strategy's performance on half B (and vice versa), averaging the two results. Every reported compute-optimal number in this session is built this way — the strategy selection and the strategy evaluation never touch the same data.

Trace the split with real numbers: each bin holds 100 questions. Two-fold cross-validation splits that into fold A (50 questions) and fold B (50 questions). Every candidate strategy — every search configuration from Chapter 3, every sequential/parallel ratio from Chapter 4 — gets scored on fold A alone, and whichever wins on fold A gets reported using its accuracy on the completely separate fold B. Then the roles swap: select on B, report on A. The final number for that bin is the average of the two folds' reported accuracies. Fifty held-out questions is not a huge evaluation set, which is exactly why this careful bookkeeping matters — with fewer bins (say, 3 instead of 5), each fold would hold more questions and give a less noisy estimate, at the cost of coarser difficulty resolution; the choice of 5 bins is itself a tradeoff between those two pressures, not a number handed down from nowhere.

One more practical note worth making explicit: this exact same binning procedure — sample 2,048 times, compute pass@1, sort into 5 quantiles, two-fold cross-validate — is not specific to search. It is reused, unchanged, as the backbone for Chapter 4's revision experiments too. The difficulty machinery this chapter builds is genuinely shared infrastructure across the entire session, not a piece specific to beam search or PRMs; anywhere this session says "compute-optimal," it is leaning on exactly this one procedure underneath.

The formal target, for the record

Written out precisely, once, so the rest of the session has something exact to point back to: for a question q with true answer y*(q), a test-time strategy has some hyperparameters θ (which method, how much budget, what ratio of search to revision) and a compute budget N. The compute-optimal strategy θ*(N) is simply the one that maximizes accuracy for that specific question at that specific budget:

This is unreachable exactly — you'd need to already know, per question, which hyperparameters work best — but the difficulty-bin scheme is a tractable, honest approximation of it: instead of optimizing per question, optimize per bin, using a held-out validation fold, then apply the bin-level winner at test time. That single substitution — "optimize per question" downgraded to "optimize per difficulty bin" — is what makes every compute-optimal result in Chapters 3 through 6 something you could actually run.

Quantifying "the estimate gets tighter," not just asserting it

The earlier claim that 2,048 samples pins down pass@1 far more reliably than 8 samples can be checked with the standard formula for the uncertainty of a sample proportion — the same formula behind why a political poll needs a certain number of respondents before its margin of error is trustworthy. For a true success probability p estimated from n independent samples, the standard error of the estimate is:

Plug in the true pass@1 = 0.20 example worked earlier in this chapter, first at n = 8:

Now at n = 2,048, the sample count the paper actually uses:

The gap between those two numbers — 14 percentage points of noise versus under 1 — is the entire quantitative content behind the earlier claim that 8 samples "might easily show 1 or 2 out of 8 purely from sampling noise." At n = 8, a true 20% question could easily be measured anywhere from roughly 6% to 34% just from noise, comfortably crossing into a neighboring difficulty bin. At n = 2,048, that same true 20% question is measured within about a percentage point of its real value nearly every time — the bin assignment becomes trustworthy specifically because standard error shrinks with the square root of the sample count, and 2,048 was chosen large enough to make that shrinkage decisive rather than merely helpful.

The cost the authors flag, and the fix they name but don't build

This chapter's earlier callout already named the honest cost: estimating difficulty this way requires generating a real batch of samples before you even know which strategy to apply. The paper is specific about one concrete alternative, named directly rather than left vague: instead of averaging a PRM's score over 2,048 samples per question, finetune a dedicated model to predict a question's correctness rate directly from the question text alone, with no sampling required at inference time at all. The authors are explicit that they do not build or test this alternative themselves — it is named as future work, not a delivered result — but naming it precisely still matters, because it draws a clean three-way line: oracle difficulty (research only, needs ground truth), PRM-averaged difficulty (deployable, but still sampling-heavy — the technique this session actually uses), and a hypothetical third technique, a directly-finetuned difficulty predictor, that would need its own training run and its own validation before anyone could trust it in production.

One more angle on the same tradeoff: bin count itself

The choice of exactly 5 bins, mentioned earlier only in passing, deserves one more pass now that the standard error math above is on the table. Every bin holds 100 questions; two-fold cross-validation then splits each bin into two folds of 50. A coarser choice — say, 3 bins instead of 5 — would put roughly 167 questions per bin, and roughly 83 per validation fold, directly shrinking the standard error on every strategy's measured accuracy within that fold by the same square-root-of-n logic just worked through above. The tradeoff is exact and symmetric: fewer, larger bins buy a more reliable per-bin accuracy estimate at the cost of a cruder difficulty resolution (easy and medium-easy questions lumped into one bin, sharing one strategy even if their true optimal strategies differ slightly); more, smaller bins buy sharper difficulty resolution at the cost of noisier per-bin accuracy estimates, from smaller validation folds. Five bins is a specific point chosen on that curve, not a number that falls out of any other part of the method.

Chapter 3: Beam Search Against a PRM

Chapter 1 introduced the PRM as a per-step scorer. This chapter builds the actual search algorithms that use it — three of them, in increasing sophistication and increasing cost — and shows the result that motivates everything after it: the best search method is not fixed, it flips depending on budget and difficulty.

Best-of-N, the baseline everything else is measured against

The simplest possible way to spend a search budget: sample N complete answers independently from the base model, score each finished answer with the PRM (using its final-step score, per Chapter 1), and keep the highest-scoring one. This is best-of-N. It never looks at a partial solution — every one of the N candidates is generated all the way to the end before any comparison happens.

Beam search: search that can prune early

Beam search against a PRM works step by step instead of answer by answer, using two numbers: a total beam count N and a beam width M. The algorithm, exactly as specified:

1. Sample N candidate first steps.
2. Score every one of those N steps with the PRM's per-step reward-to-go estimate.
3. Keep only the top N/M highest-scoring steps — discard the rest.
4. From each of those N/M survivors, sample M new next-steps, bringing the pool back up to (N/M) × M = N candidates. Repeat from step 2.

Trace it with real numbers: N = 16 candidates, beam width M = 4 (the exact fixed width the paper uses for its main difficulty-bin comparison). Step 1 produces 16 first steps. Step 3 prunes down to the top 16/4 = 4 survivors. Step 4 expands each survivor into 4 children, landing back at 4 × 4 = 16 candidates for the next round. The pool size never changes; what changes is which 4 branches get to keep growing.

Push the trace one round further with actual toy scores attached, so "keep the top N/M" is not just an abstract instruction. Round 1 produces 16 first steps; suppose the PRM scores them (reward-to-go estimates) and, sorted descending, the top four are 0.91, 0.88, 0.85, 0.79, with the remaining twelve trailing off below 0.60. Step 3 keeps exactly those top four, discarding the other twelve regardless of how close some of them were — beam search is a hard cutoff, not a soft reweighting. Step 4 then expands each of those four survivors into 4 new children apiece: the branch that scored 0.91 might now produce children scoring 0.93, 0.90, 0.87, 0.81, while the branch that scored 0.79 might produce children scoring only 0.72, 0.68, 0.65, 0.60. Both branches get exactly the same number of children (4 each) regardless of how promising they looked — the pruning already happened at the parent level, and every surviving parent gets an equal shot at producing the next generation.

The paper does not commit to one single beam width either — its broader sweep tests beam search with width fixed at M = 4 (the setting behind the difficulty-bin table below) alongside a second configuration where the width itself scales with the budget, set to √N. At a budget of N = 256, for instance, √256 = 16, giving 16 survivors kept per round instead of 4 — a wider, less aggressively-pruning beam. Comparing a fixed narrow beam against a budget-scaled wider one is how the authors check that their central finding (beam search's late-budget struggles) isn't just an artifact of one particular width choice.

Lookahead search: paying extra to see further ahead

Lookahead search is beam search with one modification: instead of trusting the PRM's score at the current step, it first simulates k additional steps forward (at temperature 0, to keep the simulation deterministic and cheap to reason about), stopping early if the solution finishes, and uses the PRM's score at the end of that simulated rollout to judge the current step. More lookahead should mean a more accurate judgment of a step's true value — at a real cost. Since scoring one step now requires generating k extra steps of simulation, the true compute cost of lookahead search is:

Set k = 0 and this collapses exactly back to ordinary beam search — beam search is the special case of lookahead search that looks zero steps ahead. Lookahead search is, in turn, a special case of a more general algorithm called Monte Carlo Tree Search (MCTS), with the usual stochastic exploration machinery stripped out — because that machinery exists in MCTS to help learn a value function through exploration, and here the PRM is already trained and frozen. There is nothing left to explore for; only a fixed value estimate to exploit.

Trace the cost formula at the widest budget the paper's sweep actually tests, N = 256, across the lookahead depths it tries — k = 0 (plain beam search), k = 1, and k = 3:

At k = 3, lookahead search is spending four times the raw generation calls of plain beam search at the same nominal budget N, for a value estimate that — per this chapter's next section — still generally underperforms the cheaper options. That gap between "more compute spent" and "better result obtained" is precisely the shape of result this whole session keeps circling back to: more compute is not automatically better compute.

The result that complicates everything: beam search does not simply win

At small generation budgets, beam search significantly outperforms best-of-N — pruning early pays off when you can't afford to finish many full answers anyway. But as the budget scales up, that advantage shrinks, and beam search often ends up performing worse than plain best-of-N at large budgets. Lookahead search, meanwhile, generally underperforms both other methods at a matched generation budget — its extra simulated steps cost more than the more-accurate value estimate is worth, at least in this setting.

The mechanism behind beam search's late-budget collapse is over-optimization: the PRM is a learned, imperfect proxy for "is this step actually good," and beam search is specifically designed to hunt down and exploit whatever the highest-scoring path is. Give it enough budget and enough rounds of pruning, and it starts finding paths that score well on the PRM's particular quirks rather than paths that are actually correct — sometimes producing degenerate, repetitive, or suspiciously short solutions that happen to satisfy the PRM's scoring function without actually solving the problem.

What this actually looks like in a generated transcript is worth naming concretely, not just abstractly. Sometimes it is a solution that ends with several low-information, repetitive steps — lines that restate the previous line in slightly different words, adding nothing, but which the PRM does not penalize because they do not contain anything obviously wrong either. Other times it is the opposite failure: an overly short solution, just one or two steps, that jumps straight to a plausible-looking final answer without doing the intermediate work a correct solution would actually require — short enough that there was little surface area for the PRM to catch a mistake in, precisely because there was barely any solution there to score.

Where over-optimization bites, split by difficulty

This is exactly where Chapter 2's difficulty bins earn their keep. Comparing beam search (M = 4) against best-of-N across four increasing generation budgets — 4, 16, 64, and 256 — split by difficulty bin:

The intuition, stated plainly: on easy questions, the PRM's judgments are mostly correct, so a search method aggressive enough to fully exploit those judgments just amplifies whatever spurious signal the PRM does have. On harder questions, the PRM's judgments have more genuine signal left to extract, so aggressive search keeps paying off longer before it runs out of real signal to exploit. There is no single search method that is correct in general — only a method that is correct for a given difficulty and a given budget.

The property best-of-N has that beam search does not

Worth naming the flip side of this whole chapter's finding, since it explains why best-of-N remains the default anyone reaches for first, even after everything above: best-of-N is not capable of the same kind of targeted over-optimization, because it never prunes anything mid-solution. Every one of its N candidates gets generated all the way to completion, independently, before any comparison happens at all — there is no intermediate point where a PRM's noisy judgment can steer generation away from a path it merely looked bad on. That is precisely why best-of-N does not show the degrading-with-more-budget pattern on easy questions: it has no mechanism through which the PRM's imperfections can compound across a solution's construction. The tradeoff is exactly the one this chapter has been building toward — that same hands-off property is what makes best-of-N unable to prune a bad trajectory early, the very capability that lets beam search win convincingly on harder questions at low budgets.

The three methods, side by side

No row in this table is a strictly dominant choice — each one's "main risk" column is precisely the reason Chapter 5 needs a difficulty- and budget-conditioned rule for picking between them, rather than a single default this chapter could simply recommend outright.

When does the search actually stop?

Every round of beam search costs another batch of generation calls, so it needs an explicit stopping rule, not just "keep going forever." The implementation runs the expand-and-prune loop from earlier in this chapter until either every surviving candidate reaches the end of its solution, or a hard cap of 40 rounds of beam expansion is hit, whichever comes first. Once the loop exits, the final pool of N candidate full answers gets passed through best-of-N weighted selection — the exact same PRM-scored aggregation rule Chapter 1 already built — to pick the one answer beam search actually returns.

That detail quietly resolves a question a careful reader might already be asking: what does beam search actually output, an intermediate step or a finished answer? The answer is a finished answer, always. Beam search prunes intermediate steps internally, but its N surviving candidates all get carried through to full solutions (or the 40-round cap) before the very last decision, which is a Chapter-1-style best-of-N vote over whichever finished answers made it that far. Beam search, in other words, is not a replacement for best-of-N selection at the very end; it is a smarter way of deciding which N candidates get to compete in that final vote.

Counting the true cost of one full beam search run, end to end

Chapter 1 already flagged that any FLOPs accounting of "how much did this search cost" needs to count the verifier's forward passes, not just the generator's. Put a full number on it for beam search specifically. At N = 16 total beams, M = 4 width, each round does two things: sample the pool back up to 16 candidate next-steps (16 generation calls), then score every one of those 16 steps with the PRM (16 verifier calls). A run that actually needs all 40 rounds to finish — the worst case the cap is guarding against — costs roughly 40 × (16 + 16) = 1,280 total forward passes, generator and verifier combined, before best-of-N selection even runs its own final PRM pass over the finished candidates. A run that finishes in, say, 6 rounds because every surviving beam reaches an end-of-solution token early costs closer to 6 × 32 = 192. The 40-round cap is specifically a worst-case safety bound, not a typical outcome; most solutions to a MATH problem do not need anywhere near 40 reasoning steps, and the cap exists mainly to guard against the rare degenerate case — exactly the kind of repetitive, low-information solution this chapter's over-optimization discussion already named — rather than to describe how long a normal search actually runs.

Where the generated candidates actually come from

One detail worth not taking for granted: every candidate step or candidate answer in this chapter, across all three search methods, is sampled from the same base LLM used everywhere else in this session — PaLM 2-S* — prompted with a handful of worked examples in its context window (a few-shot prompt), not a specially finetuned model. Contrast this directly with Chapter 4's revision model, which required dedicated finetuning to be any good at its job at all. Search methods, this chapter's whole point, spend their compute entirely on how many candidates get sampled and which get kept — not on making the underlying proposal distribution itself any better. This is exactly Chapter 1's "verifier changes what gets kept, not what gets generated" distinction, now visible in a very literal, practical sense: not one weight of the generating model changes anywhere in this chapter, only the PRM does the work of steering which candidates survive.

One question worth previewing, since it is the natural next one to ask: could you combine both levers — run beam search against a revision model's own sequence of attempts, rather than against independent samples? The paper is direct about this being untested territory in its own writeup, not a result it delivers.

Chapter 4: Teaching a Model to Revise Itself

Chapter 3 changed which answers get kept. This chapter changes what answers get proposed in the first place — the other lever from Chapter 1. Instead of sampling N independent attempts and picking the best, let the model look at its own previous attempt, in context, and try again. This is revision: the model's proposal distribution literally shifts, attempt to attempt, without a single weight changing.

Why prompting alone doesn't work

The obvious first thing to try is just prompting an off-the-shelf model: "here is your previous answer, find the mistake and fix it." This is largely ineffective on hard reasoning problems — models are not reliably good at spotting their own errors from a prompt alone. The paper's fix is to specifically finetune a model for the skill of revision, building on a recipe from Qu et al. (2024).

Building training data for a skill nobody demonstrated

There is a chicken-and-egg problem: to finetune a model to revise well, you need examples of good revision chains, but nobody handed you a dataset of "here is a wrong attempt, here is how an expert fixes it." The solution is to construct that data automatically. Sample 64 responses in parallel, at a higher temperature, for each training question. Then pair every correct answer in that batch with a sequence of up to four incorrect answers, presented as if they were the model's own earlier attempts in a multi-turn conversation — the correct answer becomes the "final" turn, the incorrect ones become the turns before it.

Which incorrect answers get paired with which correct one is not random: the authors use a character edit-distance heuristic to favor pairing incorrect answers that are textually close to the eventual correct one. The intuition is that a training example is only useful for teaching revision if the "mistake" looks like something a plausible, almost-right attempt would actually contain — not an unrelated wrong answer to a different line of reasoning entirely.

Make the intuition concrete with a toy pair. Imagine the correct final answer to a problem is "x = 7." Two candidate incorrect answers from the same batch of 64 samples: one arrives at "x = 7.02" after an arithmetic rounding slip three steps in; another arrives at "x = −3" after picking the wrong branch of a case split in step one, taking the whole derivation somewhere unrelated. The edit-distance heuristic favors pairing the first one — "x = 7.02" — as the in-context "previous attempt," because the fix it demonstrates (catch a late, local slip) is exactly the kind of correction a revision model actually needs to learn. Pairing the second one would mostly teach the model to notice "this entire derivation is unrelated to the target," which is a much less useful and much rarer skill for revision to specialize in.

pseudocode
# building one training example for the revision model
samples = sample_in_parallel(question, n=64, temperature=high)
correct  = [s for s in samples if is_correct(s, question)]
wrong    = [s for s in samples if not is_correct(s, question)]

for target in correct:
    k = random_uniform_int(0, 4)                    # how many "prior attempts" to include
    prior = top_k_by_edit_distance(wrong, target, k)  # closest-looking wrong answers
    training_example = build_multiturn(prior + [target])  # prior turns, then the fix

Worth being explicit about what does not need to be novel here: the actual finetuning loss applied to this constructed data is ordinary next-token cross-entropy, the exact same objective any supervised finetuning run uses — nothing PRM-style or reward-based about it. Every bit of the real novelty in teaching a model to revise lives entirely in how the training data gets constructed (Chapter 1's Concept & Realization pattern showing up again): dress up a batch of independent samples as a fake multi-turn conversation, correlate the "mistakes" by edit distance so they look plausible, and ordinary supervised finetuning does the rest. No new loss function, no new architecture — just a cleverly constructed dataset.

Contrast this with Chapter 1's PRM one more time, now that both training recipes are fully on the table. The PRM needed a genuinely new label-generation procedure (Monte Carlo rollouts to soft-label each step) precisely because its target — "is this step correct" — had no natural home in ordinary next-token training data. The revision model's target — "given a wrong attempt, produce a right one" — already has a natural home in next-token prediction, once the training examples are arranged to look like a conversation that ends correctly. Two different engineering problems, solved by two different amounts of machinery, and the amount of machinery each one needed tracks directly with how unnatural its target was for a model already trained to just predict the next token.

What happens when you actually run the revision chain

Once finetuned, sample a chain of revisions at inference time: attempt, revise, revise again. The model was only trained with up to four prior attempts in context, but longer chains are still possible at inference by truncating the context to just the four most recent revisions. And it works: pass@1 improves steadily with each revision step — and keeps improving even past the four steps the model was explicitly trained on, evidence that it learned something closer to a general "notice and fix mistakes" skill rather than memorizing a fixed four-step routine.

The truncation mechanic is worth being precise about, since it is the piece that lets a model trained on chains of at most four ever run a chain of sixty-four. At revision step 20, say, the model is not shown attempts 1 through 19 in full — it is shown only attempts 16 through 19, exactly the same context shape (four prior attempts) it was trained on, just relabeled to whichever four are the most recent. The model never has to process a context length longer than what it saw in training; the chain's total length grows only because this fixed-size window keeps sliding forward, one attempt at a time, indefinitely.

The honest failure mode: revision sometimes breaks a correct answer

Revision is not monotonically safe. Roughly 38% of correct answers get converted back into incorrect ones at the very next revision step, under a naive scheme that always just takes whatever the last step in the chain says. That is a serious failure rate for something meant to be an improvement mechanism.

Worth checking: do these two selection mechanisms — majority voting (no verifier needed, just count which answer appears most often across the chain) and verifier-based selection (score every attempt with the PRM or an ORM, keep the top-scoring one) — actually agree with each other, or does the choice between them matter a lot? Run both across the same difficulty-bin sweep, and they show largely similar trends throughout — which is reassuring for anyone deploying this without a trained verifier handy: plain majority voting over a revision chain recovers most of what a full verifier gets you, at a fraction of the extra machinery.

And, just as Chapter 2 distinguished oracle from model-predicted difficulty for search, the same check gets run here: compute difficulty bins for the revision experiments using the PRM's own predictions instead of ground-truth correctness, and the resulting trends — which ratio of sequential to parallel wins at which difficulty — look largely the same as with the oracle bins. Difficulty-conditioning survives without cheating in the revision setting too, not just in the search setting Chapter 2 originally introduced it for.

Sequential beats parallel — at a matched budget

With that selection mechanism in place, the paper runs the cleanest possible comparison: given the exact same generation budget N, is it better to spend it on N independent parallel samples (ordinary best-of-N), or on one chain of N sequential revisions? Using either verifier-based or majority-based selection over the results, sampling sequentially narrowly but consistently outperforms sampling the same number of attempts in parallel. Each new attempt in a chain gets to see and correct the previous one; each new attempt sampled in parallel starts from nothing every single time.

It is worth being precise about how narrow this "narrowly but consistently" win actually is, because it is easy to over-read. Sequential revision is not a dramatically more powerful mechanism than parallel sampling in some abstract sense — both are drawing from the same finetuned model. The advantage comes entirely from the information each new sample gets to condition on: a sequential attempt sees a concrete, specific previous mistake to react to, while a parallel attempt sees only the original question again, exactly as blank as the first sample was. That is a real, exploitable edge, but it is an edge built on conditioning, not on the revision model somehow being fundamentally smarter when sampled in a chain versus sampled independently.

The ideal mix is not "all sequential"

Sequential winning outright at a matched budget does not mean the answer is "always go fully sequential." Sweep the ratio of budget spent on sequential revisions versus parallel independent chains, and a genuine sweet spot appears: more sequential revision tends to outperform more parallel sampling in general, but at higher total budgets, some balance between the two extremes beats either extreme alone. And that ideal ratio is itself difficulty-dependent — easier questions get their best performance from spending the entire budget on one long sequential chain, while harder questions do best with a genuine split between sequential depth and parallel breadth, rather than committing everything to one revision path that might be heading the wrong direction.

Make this concrete with the exact generation budget the paper's own ratio sweep uses: 128. At the fully sequential extreme, that is 1 chain × 128 revisions deep; at the fully parallel extreme, it is 128 chains × 1 attempt each (which is just plain best-of-128). A middle setting might be 8 chains × 16 revisions deep each — eight independent starting points, each one allowed to revise itself sixteen times before the verifier picks a winner within that chain, and then across the eight chains. On easy questions, the sweep finds the 1×128 extreme wins outright: there is no benefit to diversifying starting points when the first attempt was probably already close. On harder questions, some split in between — more chains, each individually shallower — consistently beats both extremes, because a single long chain risks compounding down one unproductive line of reasoning for all 128 steps, with no second starting point to fall back on if it does.

Why revision has "global search" and "local refinement" modes worth distinguishing

It is worth putting a name on why parallel sampling and sequential revision might have genuinely different strengths, not just different average scores. Parallel sampling acts more like a global search process: because every one of the N samples starts fresh from the original question, in principle they can cover many completely different high-level approaches to the same problem, not just variations on one approach. Sequential revision acts more like a local refinement process: each new attempt is anchored to a specific previous attempt, so it can polish and correct that one approach, but it is far less likely to suddenly jump to a structurally different way of solving the problem than an independent fresh sample would be. Neither is universally better; they are complementary tools that cover different kinds of mistakes.

This distinction sharpens exactly what the difficulty-dependent split found earlier in this chapter is actually buying you. An easy question rarely needs a different high-level approach at all — the model's first instinct is probably already the right strategy, and what it needs is local polish, exactly what a long sequential chain provides. A harder question is more likely to need a genuinely different approach if the first one was wrong, exactly the coverage that spreading budget across multiple independent starting points (more chains, less depth per chain) provides. The compute-optimal split this chapter measures is not an arbitrary sweep result; it tracks this global-search-versus-local-refinement tradeoff directly.

Why the 38% number is not a mystery, once you see the training/test mismatch

It is worth explaining the mechanism behind that 38% regression rate, not just citing it. The revision model was trained exclusively on sequences ending correctly — every training example is some number of wrong answers, in order, followed by one right one. At test time, though, a sampled revision chain has no such guarantee: an early attempt in the chain might already land on the correct answer, and the model, having never seen a training example where a correct answer sits mid-chain rather than at the very end, has no reliable trained behavior for what to do with it. It can, and often does, "revise" a correct answer into something else — not because the correction logic is wrong, but because the model's whole training signal only ever taught it "the previous attempts in context are wrong, fix them," and it has learned that lesson well enough to sometimes apply it to an attempt that happens to already be right.

Framed this way, the fix already built earlier in this chapter — select from the whole chain rather than trusting the last link — is not a hack layered on top of a broken model. It is the correct response to a real, structural mismatch between the training distribution (always ends correctly) and the test-time distribution (may pass through a correct answer partway through, then keep going anyway). No amount of extra finetuning on the current recipe removes this mismatch entirely, because the recipe, by construction, never shows the model a training example where revising further is the wrong move to make.

How "pass@1 improves with each revision step" was actually measured

The claim that pass@1 improves with each revision step, and keeps improving past the four steps the model was explicitly trained on, comes from a specific measurement worth naming precisely: for each test question, the authors sample 4 separate revision trajectories, each one run out to 64 revision steps deep, and average pass@1 at each step position across those trajectories and across the full test set. Averaging over 4 independent trajectories per question, rather than reporting one trajectory's specific path, is the same statistical instinct Chapter 2 built an entire chapter around: one chain's specific path is noisy; averaging several damps that noise enough to trust the resulting per-step curve as a real trend rather than one chain's lucky streak.

Neither chapter, on its own, tells you when to reach for search versus when to reach for revision in the first place — that comparison has not been made yet. It is the very next thing this session builds.

Chapter 5: The Compute-Optimal Allocation

Chapters 3 and 4 each found the same shape of result on their own axis: no single strategy is universally best; the right choice depends on difficulty and on budget. This chapter is where those two separate findings get combined into one deployable rule, and where the headline "4× less compute" number from Chapter 0 finally gets derived rather than just stated.

Before the full sweep: a reasonable starting guess

Before running the exhaustive per-bin sweep that produces the lookup table below, it is worth naming the sensible default the authors reach for first, because it frames just how much the fully-tuned compute-optimal rule improves on a reasonable person's first guess. Given a budget N to split between parallel chains and sequential depth, a natural starting point is to split it evenly in the geometric sense: use √N parallel chains, each √N steps deep — balancing breadth and depth rather than committing fully to either. At N = 128, that is roughly 11 chains of 11 steps each. This even split is a reasonable prior, not a derived optimum — and the whole point of this chapter's sweep is that the actual optimal ratio, once measured per difficulty bin, is rarely exactly this even split; it is usually pulled toward more sequential depth on easy questions and only closer to this balanced default on the harder ones.

Hold onto this pattern — sweep every reasonable configuration, keep whichever wins for a given setting, rather than trust one universal default — because it is not unique to search and revision. Chapter 8's ablation table, still two chapters away, is built out of exactly the same discipline applied to a completely different method: rather than assume the entropic objective or PUCT reuse must be beneficial, the authors strip each one out individually and measure what breaks. "Sweep and measure, don't assume" turns out to be this entire session's real methodological throughline, not just a technique specific to compute-optimal allocation.

The rule, stated exactly

For search (Chapter 3): at each difficulty bin, independently pick whichever search configuration — best-of-N, beam search with some width, lookahead with some k — performed best on a held-out validation fold, using Chapter 2's two-fold cross-validation to avoid peeking. For revisions (Chapter 4): at each difficulty bin, pick the sequential-to-parallel ratio that performed best on the validation fold. In both cases, the compute-optimal strategy at test time is: look up the question's difficulty bin, then apply that bin's winning configuration.

pseudocode
def compute_optimal_strategy(question, budget_N, bin_lookup_table):
    difficulty_bin = estimate_difficulty(question)      # oracle, or PRM-predicted (Ch 2)
    strategy = bin_lookup_table[difficulty_bin][budget_N] # chosen on a held-out fold, ahead of time
    return apply_strategy(question, strategy, budget_N)  # search config, or seq:par ratio

Every entry in bin_lookup_table is filled in once, offline, by exactly the sweeps Chapters 3 and 4 already ran — nothing new gets learned at deployment time. Compute-optimal scaling is a lookup, not a new algorithm; its cost is entirely in the careful offline sweep that built the table.

Fill in that lookup table concretely, one row per bin, using nothing but the qualitative patterns Chapters 3 and 4 already established:

Notice that bins 1–2 and bin 5 point toward the same practical conclusion from opposite directions: don't spend aggressively on either extreme. Easy questions don't need aggressive search because they're already mostly solved; the hardest questions don't reward aggressive search because there is little real signal left to find. The genuine payoff of allocating more budget lives specifically in the middle bins — exactly where a uniform, one-size-fits-all strategy would have been wasting the least useful spending pattern on the bins that could have used it most.

Why the two curves have different shapes

The paper's own Figure 1 caption puts this in two phrases worth holding side by side: for revisions, "the gap between standard best-of-N … and compute-optimal scaling gradually widens"; for search, it reports only "significant early improvements," narrowing at large budgets. That difference in shape is not an accident — it follows directly from what Chapters 3 and 4 each already found. Revision's ideal sequential-to-parallel ratio keeps paying off further into the budget because the underlying mechanism (conditioning on a specific, informative previous mistake) does not degrade as spent budget grows — there is no analogue of the PRM's imperfect proxy being exploited harder with more search. Beam search's gains, by contrast, are capped by exactly the over-optimization dynamic Chapter 3 diagnosed: the compute-optimal curve for search wins early because it correctly avoids over-optimizing on easy questions where plain beam search would already be degrading, but once the budget is large enough that even best-of-N is doing well on its own, there is less room left for smarter allocation to add on top.

The 4× result, with real anchor numbers

Compare this compute-optimal, per-bin strategy against the plain best-of-N baseline at matched accuracy, and the efficiency gap the paper reports is concrete: in the PRM search setting, compute-optimal scaling nearly matches best-of-N's accuracy using 16 generations where best-of-N needs 64 — a 4× reduction. In the revisions setting, the same pattern holds at a different scale: compute-optimal scaling matches best-of-N using 64 samples where best-of-N needs 256 — again roughly 4×. Both oracle difficulty and PRM-predicted (model-predicted) difficulty bins produce curves that largely overlap with each other in the low-budget regime, meaning the 4× win survives even without cheating and looking at the ground-truth answer to assign difficulty — the one caveat is that at very large budgets, some of the gap narrows when using predicted rather than oracle bins, since predicted difficulty is itself a noisier signal than the ground truth.

Be precise about which baseline each 4× figure is actually measured against, since the two settings use different reference points. The search-setting result (16 vs 64) is measured against ordinary PRM best-of-N — independent samples from the base model, scored and ranked by the PRM, with no revision involved at all. The revisions-setting result (64 vs 256) is measured against parallel sampling using the same finetuned revision model — not the vanilla, non-revision-trained base model. In other words, revision's 4× is not claiming an advantage over an unrelated weaker baseline; it is a genuinely apples-to-apples comparison, same finetuned model, same verifier, with the only difference being how the budget is spent (sequential structure and ratio versus flat parallel sampling).

Read the abstract's "more than 4×" alongside the paper's own closing summary, which states the general range more conservatively: applying a compute-optimal scaling strategy improves the efficiency of test-time compute scaling “by a factor of 2–4×.” Both numbers are honest, describing different things — 4× (and "more than 4x" at points) is the best-case gap observed at specific favorable budgets and difficulty bins; 2–4× is the more representative range across the full sweep of settings tested. A responsible reading of this chapter carries the range, not just the headline peak.

Efficiency is not just a cost line item — it's latency

It is worth naming a second, less obvious benefit of the same 4× number, beyond the dollar cost per query. Generations in a search or revision budget are not free in time, either — a user waiting on a response experiences every one of those 64 (or 16) generations as real wall-clock latency, especially under sequential revision, where each step in the chain has to finish before the next one can even start. Cutting the required budget from 64 down to 16 is not only cheaper; for a sequential strategy, it can also mean a noticeably faster response, which matters just as much for a real product as the compute bill does.

What happens when the difficulty estimate is simply wrong

Compute-optimal scaling's entire value depends on correctly routing a question to the right bin's strategy. Worth asking directly: what happens when that routing is wrong — when model-predicted difficulty places a question in, say, bin 2 when it actually belongs in bin 4? The failure is not catastrophic, because adjacent bins tend to have similar optimal strategies rather than wildly different ones — a question misrouted by one bin gets a strategy that is merely suboptimal for it, not actively harmful, the way using bin 1's minimal-search strategy on a genuinely bin-5 question might quietly waste an opportunity but would not make that question's outcome any worse than not searching at all. This graceful-degradation property is part of why model-predicted difficulty, despite being noisier than oracle difficulty, still recovers most of the oracle's benefit in practice (Chapter 2): small misclassifications cost only a little, not everything.

What compute-optimal allocation is not

It is worth closing this chapter by naming, precisely, what this rule is not claiming to be, since the name "compute-optimal" invites over-reading. It is not a new search algorithm, not a new way to train a verifier or a revision model, and not a claim that any individual strategy from Chapters 3 or 4 is better than previously understood. It is entirely a allocation result: given the exact same set of tools this session already built, choosing which tool to reach for, conditioned on difficulty and budget, closes most of the gap to an unreachable per-question optimum (Chapter 2's formal target) using far less compute than treating every question identically would require. The tools did not get smarter. The way of choosing between them did.

Why this isn't a free lunch, restated honestly

Two costs are worth keeping in view, both already named in earlier chapters and worth restating together here. First, Chapter 2's honest caveat: estimating difficulty itself costs inference compute, and the reported 4× number does not charge that cost against the budget — in a real deployment, some of this gap would need to be spent estimating difficulty before you even know which strategy to apply. Second, the 4× figure is measured relative to best-of-N specifically; it says nothing yet about how test-time compute of any kind compares to simply training a bigger model in the first place. That is exactly the question Chapter 6 takes on next, and it is a genuinely different comparison — not "which test-time strategy is most efficient," but "is spending on test-time compute worth it at all, compared to spending the same FLOPs on pretraining."

Tracing the lookup table end to end, on one concrete question

Walk the compute_optimal_strategy pseudocode from earlier in this chapter through one concrete case, start to finish. Suppose a new MATH question arrives, a compute budget of N = 64 is available, and the model-predicted difficulty routine from Chapter 2 (averaging the PRM's own final-answer score across a batch of samples, no ground truth needed) places this question in bin 3 — solidly medium difficulty, neither the easiest fifth nor the hardest. The lookup table built earlier in this chapter says: for search, lean toward beam search with M = 4, since bin 3 sits in the "beam search consistently wins" row; for revisions, lean toward a balanced sequential/parallel split rather than either extreme. If the deployment is using search, the strategy actually applied at N = 64 is beam search with N = 64, M = 4 — not best-of-64, even though best-of-64 is a perfectly valid strategy the lookup table simply did not select for this bin at this budget. Nothing about this question's specific content mattered to the choice; only its measured relationship to the base model, expressed as a bin number, and the budget available, decided which of Chapters 3 and 4's tools got applied.

The honest limitation the authors name for hard problems specifically

This chapter's earlier table already noted that "no configuration tested makes much difference" on bin 5, the hardest fifth of questions. The paper's own closing discussion states this same finding directly, worth reading in its own words rather than paraphrased: across the board, these schemes provided only small gains on hard problems, and the authors explicitly flag developing new ways of using test-time compute to get around this limitation as future work — not something this paper itself delivers. Worth being precise about what that leaves unresolved: this is not a claim that hard questions are permanently unreachable by test-time compute in any form. It is a claim that none of the specific mechanisms this session has built so far — best-of-N, beam search, lookahead search, revision, every one of them operating at the search-and-selection granularity — moves the needle much on bin 5. Chapter 7's entirely different mechanism, test-time training, is closer to the paper's own eventual answer to exactly this gap — though it arrives from a different paper, published a year and a half later, not from this one's own future-work section.

A second worked check on the geometric-mean starting guess

Earlier this chapter worked the √N heuristic at N = 128, getting roughly 11 chains of 11 steps each. Check it again at the other budget this chapter's headline 4× figure uses, N = 64 for search: √64 = 8 exactly, meaning the "reasonable starting guess" for search would split evenly into something like 8 candidates kept per beam-search round out of a budget of 64 — not far in spirit from the beam width M = 4 the paper's own fixed-width sweep actually uses, though not identical to it. The point of checking this a second time is not that the heuristic and the paper's chosen configuration always match exactly; it is that a geometric-mean split is a sane, order-of-magnitude starting point for reasoning about any new budget this session has not explicitly worked through, even where the fully-tuned compute-optimal answer (Chapter 3's own M = 4 sweep) ends up landing somewhere slightly different once real validation data gets involved.

That caveat is not a weakness unique to this method; it is true of any lookup table ever fit to held-out data. Naming it here matters mainly because "compute-optimal" is such an inviting label to over-trust — the word "optimal" makes it easy to forget that the table behind it is an empirical measurement, not a law.

Every claim this chapter has made stays inside one fixed model, one fixed benchmark, one fixed set of tools. Chapter 6 keeps the model and benchmark fixed too, but finally lets a second knob move — the model's own parameter count — the one lever untouched by everything built so far.

Chapter 6: Trading Test-Time Compute for Parameters

Every result so far has been internal to test-time compute — which way of spending an inference budget beats which other way. This chapter asks the much bigger question this session opened with in Chapter 0: is it better to spend a fixed total compute budget on training a bigger model, or on giving a smaller model more test-time compute? To answer it fairly, both options need to be measured in the same currency: FLOPs.

Counting FLOPs, the standard way

Two well-established approximations do the counting. Pretraining a model with N parameters on D_pretrain tokens costs, in FLOPs (the standard Kaplan et al. approximation):

And running inference — generating D_inference tokens with that same model — costs:

Now suppose you scale up the model's parameter count by a factor M — a bigger pretrained model, same training data, same inference workload. Both X and Y scale by exactly M, because both formulas have N as a simple multiplicative factor. Total FLOPs across pretraining and inference for the bigger model: M · (X + Y).

Deriving the exchange rate

Here is the actual question: if you keep the small model's parameters fixed at N, and instead spend extra FLOPs by generating more inference tokens (test-time compute), how many extra tokens does it take to burn through exactly M · (X + Y) total FLOPs — matching what the bigger model would have cost? Set the small model's total FLOPs equal to the big model's total FLOPs and solve for the new, larger D_inference^′:

Divide through by 2N and rearrange for D_inference^′ (the algebra is mechanical; what matters is the shape of the result):

Divide both sides by the original D_inference to get the multiplier — "how many times more test-time compute the small model is allowed to spend, to FLOP-match the bigger model" — and define R = D_inference / D_pretrain, the ratio of how many tokens you expect to run at inference versus how many you spent in pretraining:

The "3" sitting in front of that term is not an arbitrary tuning constant — it falls straight out of the two FLOPs formulas this chapter opened with. Pretraining costs 6 FLOPs per parameter per token; inference costs 2 FLOPs per parameter per token. The ratio between them, 6 ÷ 2, is exactly 3. Every extra token of pretraining data is three times as expensive, in FLOPs, as an extra token of inference — which is exactly why growing D_pretrain's contribution to the bigger model's cost frees up disproportionately more room on the small model's inference side once you re-solve for D_inference^′. Trace back through the algebra and this "3" is the same 3 every time: it is the pretraining-to-inference FLOPs ratio, smuggled into the final formula by nothing more exotic than dividing both sides of the equation by 2N.

Sanity-check the formula at its extremes

Before trusting an algebraic result, push it to its limits and confirm the answer matches intuition — the same discipline worth applying to any derived formula, not just this one. As R → ∞ (inference completely dominates the workload, pretraining tokens are negligible by comparison), the 1/R term vanishes entirely, and the multiplier collapses to just M — meaning the small model only gets to spend exactly the same multiple of extra tokens as the parameter multiplier itself, no bonus room at all. That makes sense: when inference cost already dominates the total budget, growing the model by M already multiplies almost the entire budget by M, leaving nothing extra free for the small model to spend beyond matching that same factor.

As R → 0 (pretraining tokens vastly outnumber inference tokens, the self-improvement-pipeline extreme), 1/R → ∞, and the multiplier grows without bound — the small model is allowed an essentially unlimited test-time compute budget before it FLOP-matches the bigger model. This also makes sense: if inference was already a vanishingly small slice of the total budget, then scaling the model up by M barely touches the inference side of the ledger in absolute terms, leaving enormous room on that side for the small model to spend before catching up to the bigger model's now-much-larger pretraining cost.

Three worked cases, using the paper's own tested ratios

The paper tests M ≈ 14 (roughly a 14× larger parameter count) against three concrete values of R, chosen to represent genuinely different deployment situations. Work all three by hand:

Case 1 — R = 0.16 (very little inference relative to pretraining — representative of a self-improvement pipeline, where a model is queried far less than it was trained):

Case 2 — R = 0.79 (roughly matched inference and pretraining token counts):

Case 3 — R = 22 (heavy inference load relative to pretraining — representative of a model serving enormous production traffic over its lifetime):

Read the trend across the three cases: when inference is a small fraction of a model's lifetime workload (R = 0.16), the small model gets an enormous 258× test-time compute budget to spend before matching the big model's FLOPs — huge room to try to close the gap. When inference dominates the workload (R = 22), that room shrinks to under 16× — barely more than the parameter multiplier itself.

The formula generalizes to any M, not just the paper's headline 14× case — worth checking with a much smaller, more modest jump. Suppose the only bigger model actually available is 2× the parameters (M = 2), at the middling ratio R = 0.79:

Compare this to Case 2 above (M = 14 at the same R = 0.79, multiplier 63.4×): a much smaller parameter jump earns a much smaller test-time compute allowance, because the (M − 1) factor in the formula shrinks along with M itself. Doubling a model's size is a far less FLOPs-expensive move than growing it fourteenfold, so it correspondingly buys the small model far less room to spend at test time before matching it — the formula's behavior scales sensibly with however big a jump in parameters is actually on the table, not just the one specific multiplier the paper happened to headline.

What the extra compute actually buys, and where it doesn't

A bigger multiplier does not automatically mean test-time compute wins — it just means the small model is allowed to spend more before running out of matched budget. Whether spending it actually catches up to the bigger model's accuracy depends on the question's difficulty, exactly as Chapters 3 through 5 established. Putting both dimensions together, the finding is:

The paper's own figure for this comparison plots the compute-optimal test-time-compute curve per difficulty bin as a line, and marks the 14×-bigger pretrained model's accuracy as a single star positioned at the FLOP-matched point on that same x-axis. The read is purely geometric: if the star falls below the line, test-time compute on the small model already beats the bigger pretrained model at that matched FLOPs budget; if the star falls above the line, the bigger model wins outright. Sweeping this across bins and across the three R values is literally how the table above was produced — on bins 1 through 3 (and often 4), at the lower R values, the star tends to sit below the line; on bins 4 and 5, or at the largest R, it tends to sit above it.

The reasoning behind the second row is not just "harder questions need more compute somewhere" — it's that on the hardest questions, the small model's own proposal distribution rarely contains a correct answer at all, no matter how many times you resample or revise it. All of Chapters 3 through 6 have operated strictly inside a frozen model's existing distribution; test-time compute can search that distribution more efficiently, but it cannot manufacture correctness the distribution never had a chance of producing. Extra pretraining compute, by contrast, can actually shift what the distribution contains in the first place. This is precisely the gap Chapter 7 opens next.

The paper's own bridge to what Chapter 7 will do

This chapter has kept the model itself completely off-limits — extra pretraining compute grows a new, separately-trained bigger model; extra test-time compute searches or revises the same, unchanged small model. The paper's own closing discussion names a third possibility, one it does not build but flags directly as a natural next step: distilling the outputs of test-time compute back into the base model itself, so that what a costly search or revision chain discovers on one question becomes something the model knows outright on the next one, without needing to re-search it every time. The authors' own phrase for this is an “iterative self-improvement loop.” Framed against the language this whole session has been using, that is a proposal to eventually let inference-time results feed back into training — blurring the sharp line this chapter has drawn between "spent once, at training time" and "spent per query, at inference time."

Worth being precise that this stays a proposed direction in that 2024 paper, not a delivered result. Chapter 7 is not that distillation loop; it is a different, more direct route to a related goal (letting a model actually get better at one specific problem, not just search a frozen version of itself harder), from an entirely separate paper, arriving a year and a half later, built around reinforcement learning at test time rather than distillation after the fact. Both are answers to the same gap this chapter has just spent its second half establishing: search over a frozen distribution is bounded by what that distribution already contains.

What "scaling parameters and data together" would have changed

The scope-limit callout above names the road not taken plainly: this chapter's whole derivation holds pretraining data fixed and grows only the parameter count, matching how the open LLaMA series scaled. The alternative — scaling parameters and training data together, in the ratio that minimizes loss for a given compute budget — is the recipe associated with the Chinchilla scaling-laws finding (Hoffmann et al., 2022): rather than "train the biggest model you can afford on whatever data happens to be around," find the parameter count and data count that jointly minimize loss under a fixed FLOPs budget, which in practice means training smaller models on far more data than earlier scaling recipes assumed. Redoing this chapter's exchange-rate derivation under that alternative regime is exactly the extension the authors leave open: the 6ND and 2ND FLOPs formulas used here are agnostic to how N and D got chosen, but the specific multiplier derived earlier assumes only N moves while D_pretrain holds fixed. A jointly-scaled comparison would need its own version of the same derivation, with D_pretrain as a second moving variable rather than a constant — a strictly harder algebra problem than the one this chapter solved, and one the paper explicitly does not attempt.

How sensitive is the 14× headline to a slightly different M?

Result 2's "outperforms a 14× larger model" is a specific, measured fact about one particular pair of models the authors happened to have on hand — not a claim that 14 is a magic number. Worth checking how the exchange rate reads at two neighboring multiples this session has not yet worked, to build intuition for how sensitive the multiplier actually is to a small change in M, at the paper's own middling R = 0.79 case:

The multiplier grows roughly linearly with M in this range, not explosively — each additional 4× jump in parameter count adds roughly another 19× to the test-time compute allowance at this fixed R. That near-linear relationship is visible directly in the formula itself: for fixed R, the multiplier is M + constant × (M − 1), which is linear in M by construction. Nothing about the specific number 14 makes it a discontinuity or a special case; it is simply the multiple the two particular PaLM 2 checkpoints the authors happened to have on hand differed by.

Chapter 7: Beyond the Frozen Model

Picture your own first genuinely hard programming assignment — not a homework problem with a formula to plug into, but something that asked for more than the textbook and its exercises ever covered. You tried to guess your way to a solution; those first attempts produced barely a flicker of progress. Eventually you had to stop guessing, sit with what had actually gone wrong in your failed attempts, and let that failure teach you something the textbook never had. Only then did the next attempt actually work. This is the exact opening analogy the second paper of this session uses to motivate itself — and it is worth sitting with, because it names precisely what every method in Chapters 0 through 6 cannot do: none of them let the model learn from its own failed attempts in the way you just did. They let the model try more attempts, and choose better among them, but the model discovering the assignment's hard idea for itself, mid-attempt, was never on the table.

Chapter 6 ended on a specific gap: on the hardest questions, no amount of resampling a frozen model's distribution manufactures an answer that distribution never had a chance of producing. Every method covered so far — best-of-N, beam search, lookahead search, revision — changes what you sample or what you keep, but never touches a single weight. This chapter opens the second paper of the session, Learning to Discover at Test Time (Yuksekgonul et al., January 2026), which removes exactly that restriction.

The framing, in the authors' own words

Their proposed fix: perform reinforcement learning at test time, so the model continues to train — not on some general corpus, but specifically on its own experience attempting this one problem. They call the method Test-Time Training to Discover, or TTT-Discover.

Why this is a genuinely different problem than ordinary RL

It would be easy to assume "just run RL at test time" means dropping in a standard algorithm like PPO or GRPO and letting it optimize the model's expected reward on the one problem at hand. The authors are explicit that this does technically fall under the umbrella of reinforcement learning — but standard RL was designed with a different goal in mind, and that mismatch creates real, specific failure modes. Two structural differences separate a discovery problem from ordinary RL:

That second row deserves a direct comparison back to Chapter 4: the revision model built there is meant to generalize — it gets trained once and then reused across every new MATH question a deployment ever sees. TTT-Discover's policy is the opposite: it gets trained fresh, from scratch, per problem, and its trained weights are never expected to be useful for any other problem afterward. That is a deliberate design choice, not a limitation to be fixed later — the whole point is to produce experience specific to this one problem, and generalizing away from that experience would defeat the purpose.

The authors give one more piece of reasoning for why learning, not just search, is worth the extra machinery: while both search and learning are known to scale well with more compute, learning has repeatedly ended up superseding search for genuinely hard problems throughout the history of AI — the shift from handcrafted search heuristics to learned value functions in game-playing systems like AlphaZero being one well-known example, and learned structure-prediction methods overtaking search-based approaches in protein folding being another. Their bet is that the same shift applies to scientific and engineering discovery problems at test time: search a frozen model harder for a while, but eventually, learning wins.

The discovery problem, formalized as an MDP

To apply RL at all, the problem needs to be cast as a Markov Decision Process. Across every domain the paper tests, this cast is remarkably uniform:

Before getting to the cast itself, it is worth naming why the four domains Chapter 9 reports on (mathematics, GPU kernels, algorithm design, biology) were chosen at all, since the criteria say something about how seriously the paper takes validating its own results. Two conditions had to both hold: the domain needed a way to compare against genuine human expert performance — a competition leaderboard, or a benchmark's best published result — and it needed existing AI baselines to compare against too, so a claimed improvement is measured against the state of the art on both fronts at once, not just against whichever comparison happens to look most favorable.

Notice the word continuous doing real work in that last box — Chapter 9 names this explicitly as the method's current boundary, and it is worth seeing why it matters this early rather than treating it as a footnote. A continuous reward can distinguish a kernel that runs in 1,900 microseconds from one that runs in 1,950, which is exactly the graded signal the entropic objective (Chapter 8) needs to tell "good" from "slightly less good" and push toward the best. A purely binary pass/fail reward collapses that entire gradient of information into two buckets, taking away most of what both the entropic objective and the PUCT reuse heuristic actually lean on to decide which states are worth building on. The MDP cast above is not incidentally continuous-reward-shaped; every mechanism Chapter 8 builds depends on that gradedness being there.

Three flavors of search, before any learning is added

The paper is careful to lay out a small taxonomy of ways to search this MDP without touching the weights at all, because TTT-Discover's baselines — and Chapter 8's ablation — are built directly out of these pieces. Best-of-N here means exactly what it meant in Chapter 3: sample every attempt independently, always starting from the same empty state, no memory of past attempts at all. State reuse adds a buffer and samples the starting state for each new attempt from it — the mechanism this chapter already introduced. State-action reuse goes one step further, reusing not just the previous state but the previous action too — the actual thinking tokens and code — translated into extra natural-language context for the next attempt. This last category is what the evolutionary-search literature, including AlphaEvolve, calls its approach: it typically requires hand-designed, domain-specific operations for how to translate a past action into useful context (the "mutation" and "crossover" language borrowed from genetic algorithms).

Where past attempts go: the reuse buffer

Rather than starting every single attempt from nothing, the algorithm keeps an archive H of every state discovered so far, along with its reward. A reuse heuristic samples a starting state from this archive — favoring high-reward states, but never with zero probability on lower-reward ones — and the model's next attempt continues from there, effectively adding an extra timestep to that state's history rather than starting cold. This buffer is exactly the mechanism the paper contrasts against prior evolutionary-search methods like AlphaEvolve, which reuse past attempts via hand-crafted, domain-specific heuristics (mutation, crossover) — useful, but requiring a human to design them per domain. TTT-Discover still needs a reuse heuristic (Chapter 8 builds it), but the model doing the actual proposing is being trained, not just re-prompted.

Two other pieces of work landed on the same high-level idea around the same time — MiGrATe (Phan et al.) and, closer in spirit, ThetaEvolve (Wang et al.), both concurrent with TTT-Discover. Chapter 9's results table already shows the direct comparison in one domain (the autocorrelation inequalities), but the framing worth carrying forward here is this: at a matched base model and matched compute budget, TTT-Discover still produces meaningfully better results than ThetaEvolve, a gap the authors attribute specifically to the learning objective and search subroutine Chapter 8 builds — not to any difference in raw compute or model scale between the two methods.

Notice, too, how directly this MDP cast connects back to the very first thing Chapter 0 asked you to hold onto: whether a method's weights stay frozen or keep moving. Every box in the flow diagram above — state, action, transition, reward — is silent on that question by itself; the MDP is just a shared language for describing "try something, see what happens, get a score." What Chapters 0 through 6 and what Chapters 7 through 9 disagree about is not the shape of the problem, which this MDP cast makes identical for both, but what happens to πθ between one attempt and the next. Chapter 8 makes that difference precise.

The full loop, as pseudocode

Algorithm 1: Test-Time Training to Discover
# Input: problem description d, initial policy weights theta_0
R, T = get_env(d)                         # reward + transition fns from the problem
H_0 = {(empty, R(empty), {})}             # archive starts with the trivial solution

for i in range(N):
    s_i, c_i = reuse(H_i)                 # pick a starting state from the archive
    a_i = policy_theta_i(d, s_i, c_i)     # sample an action -- thinking + code
    s_i_next = T(a_i)                     # execute it to get the next candidate
    r_i = R(s_i_next)                     # score it with the task's real metric
    H_i_next = H_i + {(s_i, a_i, s_i_next, r_i)}   # archive the attempt
    theta_i_next = train(theta_i, (d, s_i, c_i, a_i, r_i))  # update the WEIGHTS

return best state s_i_star found across all i   # not the final policy -- the best artifact

Compare this line by line against Chapter 3's beam search: both maintain a pool of candidates and both prune toward the promising ones. The single line that changes everything is theta_i_next = train(...) — every earlier method in this session held theta fixed for the entire search. This loop updates it, every single iteration, using exactly the experience gathered on this one problem.

The formal definition of "a discovery," precisely

Before the MDP cast, the paper pins down what counts as success with a definition worth stating exactly, since everything downstream — the reward, the archive, the objective Chapter 8 builds — is built to serve this one criterion. Let s_sota denote the best-known solution among all existing candidates for a problem, and r_sota = R(s_sota) its reward under the problem's own metric. A discovery is an event where a state s is found such that R(s) > r_sota — and the larger the difference R(s) − r_sota, the more significant the discovery. Read literally: the entire method exists to produce exactly one number, one artifact, that beats whatever the best-known answer already was. Everything else — the archive of past attempts, the reuse heuristic, the training loop — is machinery in service of finding that one state, not an end in itself.

This definition sharpens the second row of the earlier table one level further. "The trained policy is not expected to generalize" is really a restatement of this same definition from a different angle: since success is measured entirely by whether some s with R(s) > r_sota was ever produced, and not by any property of the policy that produced it, there is no reason the training process needs to leave behind a policy that is good at anything beyond having stumbled onto that one state. A policy that gets lucky once, on this one problem, and never again, is a complete success by this definition. A policy that reliably performs well on average across many attempts, but never quite reaches a new r_sota, is a complete failure by it — even though that same policy would be a clear win under standard RL's own success criterion.

The reward, made concrete per domain

The paper's own Table 1 spells out exactly what s, a, and R(s) are for each of the four domains Chapter 9 reports results on — worth seeing the actual reward formulas, not just the qualitative description used so far, since the "continuous" property named a moment ago is not an abstraction; it is a literal reciprocal or ratio computed from a real, measurable quantity:

Every row in that table shares one structural property worth naming: most of these are literally a reciprocal of something you want to minimize — a bound, a runtime, an error — turned into something you want to maximize, purely so that "bigger reward is better" holds uniformly across every domain the paper touches. That uniformity is not a coincidence; it is what lets one single training objective (Chapter 8's entropic objective) and one single reuse heuristic (Chapter 8's PUCT rule) apply unchanged across mathematics, kernel engineering, algorithm design, and biology, without needing a domain-specific reward convention for each one.

And the table's own footnote deserves stating plainly, since it closes a loophole a careful reader might otherwise wonder about: the reward is defined as exactly 0 if a candidate state fails any of the problem's own validity checks — a kernel that doesn't compile, code that throws an exception, a bound that isn't actually a valid certificate. There is no partial credit for an invalid state under this reward, no matter how close it looked to working; a discovery problem's reward function is built to be as strict on validity as it is generous on comparing valid solutions against each other.

A third piece of concurrent work, alongside MiGrATe and ThetaEvolve

This chapter's earlier mention of concurrent work named two other papers landing on a similar high-level idea around the same time: MiGrATe (Phan et al.) and ThetaEvolve (Wang et al.). The authors name a third: EvoTune (Surina et al.), also concurrent, also combining learning with evolutionary-style search at test time. Naming all three matters for the same reason Chapter 9's honest-results table matters: TTT-Discover was not the only group to notice that "keep training at test time, on this one problem" was worth trying once search-over-a-frozen-model's limits — this chapter's central claim — became visible. Multiple independent teams converging on a similar idea, in the same narrow window of time, is itself weak but real evidence that the underlying insight — learning eventually supersedes pure search on hard enough problems — was ready to be found, not one lab's idiosyncratic bet.

Chapter 8: Learning to Discover at Test Time

Chapter 7 showed that a discovery problem technically fits the RL framework, but with a goal (one best state, no generalization needed) that standard RL algorithms were never designed around. This chapter builds the two components TTT-Discover adds on top of naive test-time RL to actually close that gap — and then proves, with one clean ablation table, that both components matter.

Why the naive version fails, concretely

The naive baseline — plug in an ordinary policy-gradient method, optimize expected reward, always start from the empty state — has three specific, named failure modes:

Fix 1: an objective that chases the maximum, not the average

The entropic objective reweights the standard policy-gradient objective so it favors maximum-reward outcomes rather than average ones:

The exponential inside is the key move: as β → ∞, this expression provably approaches the maximum reward achievable from state s, rather than the average — exactly what a discovery problem's real objective should be, per Chapter 7's Row 1. But β can't just be set to a huge constant: too large early in training causes instability (the reweighting becomes so extreme that a handful of lucky samples dominate every gradient step), while too small later makes the advantage signal vanish entirely once further gains become genuinely hard to find. A single fixed β that works well across every task type proved difficult to find.

The fix is to set β(s) adaptively, per state, by constraining how far the reweighted distribution is allowed to drift from the policy's own current distribution — a KL divergence budget, fixed at γ = ln 2 throughout every experiment in the paper. Increase β only until that KL budget is exhausted, then stop. This keeps the update from being dominated by a small number of outlier trajectories, while still consistently preferring above-average rollouts over below-average ones.

What the entropic objective looks like as an actual gradient update

J_β is defined as a log-of-expectation, which is not itself something you can directly plug into a policy-gradient update. Differentiating it works out to a familiar-looking policy-gradient form, with one crucial reweighting term:

This is ordinary REINFORCE-style policy gradient, except every action's contribution gets reweighted by w_β(s)(a) — the higher an action's reward relative to the rest of the batch, the more exponentially it dominates this weight, exactly the "chase the maximum" behavior the objective was designed for. In practice, the advantage used in the actual update also subtracts a baseline and adds a KL penalty against the original, pre-test-time-training policy π_θ0:

The −1 is a legitimate baseline, not an arbitrary constant: because w_β(s) is built to average to exactly 1 across actions sampled from the current policy, subtracting 1 centers the advantage at zero for an average action, exactly the role a baseline is supposed to play in reducing gradient variance. The extra log-ratio term penalizes drifting too far from the model's own original, pre-test-time- training behavior — a second, complementary safeguard against instability alongside the KL-budgeted β(s) itself.

Finding β(s) in practice is a small numerical search, not a closed-form formula: given a batch of rollouts from state s, the implementation searches (via bisection) for the smallest β that drives the KL divergence between the reweighted batch distribution and the plain empirical batch distribution up to exactly the γ = ln 2 budget. States where every rollout scores about the same reward tolerate a larger β before hitting that budget; states where one or two rollouts wildly outscore the rest hit the budget at a much smaller β, automatically protecting against those outlier rollouts dominating the update.

Fix 2: reuse that favors the best child, not the average child

The second fix replaces naive reuse with a PUCT-inspired scoring rule (the same family of formula AlphaZero uses to balance exploration and exploitation in tree search) for choosing which archived state to resume from:

Three deliberate departures from AlphaZero's original version, each tuned for a discovery problem's actual goal:

Plug in one small, illustrative toy archive to see the score formula actually decide something. Suppose the archive holds three candidate kernels, and exploration coefficient c = 1, with T = 10 total expansions so far:

Read the winner carefully: it is C, the never-expanded, only mediocre-reward state — not A, the state with by far the best reward. Zero prior visits (n(C) = 0) puts the largest possible denominator-shrinking bonus behind C's score, overwhelming its comparatively modest 0.55 reward. This is PUCT behaving exactly as designed: an untried state gets prioritized for at least one look, almost regardless of how promising it seems on paper, because n(s) = 0 is precisely the situation the exploration term is built to correct for. Once C gets expanded and n(C) climbs to 1, its bonus collapses toward B's, and from there its actual reward has to start earning its keep the way A's already has. Exploration is front-loaded by this formula, not sustained indefinitely.

The archive itself is kept bounded and manageable: after expanding a state, only its top-2 highest-reward children get inserted into the archive, and the archive as a whole is capped at the top 1,000 states by reward (with the original seed states always protected from eviction). Reuse, in other words, is not "try everything ever generated" — it is a deliberately curated, reward-ranked shortlist.

The ablation that proves both pieces earn their place

The cleanest evidence for this chapter comes from one table: the GPUMode TriMul kernel-engineering competition, timed on an H100 GPU, reporting the best kernel runtime found under each configuration (lower is better):

Read this table as a story, not just a leaderboard. Adding PUCT reuse alone, with the weights still completely frozen, takes best runtime from 5,352 down to 2,061 — more than 2.5× faster, from smarter search alone, before a single gradient step is taken. But 2,061 μs is still slower than the best human's 1,371 μs — search over a frozen model, however well-curated the reuse, cannot close that gap on its own. Only once real learning is layered on top — first a plain expected-reward objective (1,986), then a constant-β entropic objective (1,484), then the full adaptive-β entropic objective (1,203) — does the method actually beat the best human submission. Each piece, removed one at a time, costs real performance; no single component does all the work alone.

What it actually costs to run

The full recipe: gpt-oss-120b, an open-weight model, trained via LoRA at rank 32 on Tinker (an API by Thinking Machines). Fifty training steps, 512 rollouts generated per step (organized as 8 groups of 64 rollouts, each group sharing one starting context from the reuse buffer), a single on-policy gradient step per full batch — no off-policy updates at all, with an importance-sampling correction applied for the small sampler/learner mismatch that RL infrastructure introduces. Reasoning effort set to "high," with the prompt-plus-thinking budget capped at 26,000 of the model's 32,768-token context window, leaving room to force a final response. At an average prompt length of about 3,000 tokens and 16,000 sampling tokens, one full 50-step run costs roughly $500 on Tinker.

Watching β actually concentrate on the best rollout, by hand

It is worth watching the "chases the maximum, not the average" behavior happen in actual numbers, at small scale. Take three toy rollouts from the same state, with rewards 0.5, 0.7, and 0.9 (illustrative round numbers, not paper-reported values), and compute the reweighted batch distribution q_β(n) = e^β·r_n / ∑ e^β·r_m at two different β values:

At β = 1, the reweighting barely favors the best rollout over the others — 40% of the weight on r = 0.9, still a substantial 27% left on the worst one. At β = 10, the weight collapses almost entirely onto the single best rollout — 87% of the mass on r = 0.9, with the worst rollout's weight shrunk to under 2%. This is exactly the behavior the log-sum-exp form of J_β was built to produce: push β large enough, and the objective effectively reduces to "reward the best rollout in the batch and mostly ignore the rest," precisely the maximum-chasing behavior a discovery problem's own reward structure calls for. The adaptive KL-budget mechanism exists specifically to keep β from running all the way to this extreme on every state, every step — only where a batch's rewards are similar enough to tolerate it without one lucky rollout swamping the update.

A useful mathematical property: reward-invariance

One more property of the entropic objective is worth naming, because it explains why the same method is safe to apply across four wildly different domains — a kernel's runtime in microseconds, a math bound accurate to six decimal places, a competition score in the hundreds of millions — without rescaling rewards to some common range first. The advantage estimator this chapter built is invariant to shifting or scaling the reward by a positive constant: for any reward r(τ) and any transformed reward r′(τ) = w·r(τ) + b, with w > 0 and b any real number, the resulting advantage comes out identical either way.

The intuition behind why, without the full batch-estimator algebra: the weight w_β(s)(a) only ever depends on differences in reward within a batch, because the normalizer in its denominator sums over the exact same batch's exponentials. Shift every reward in a batch up by some constant b, and every term in both the numerator and the recomputed denominator picks up the identical multiplicative factor e^βb, which cancels out of the ratio entirely. Scale every reward by a positive constant w, and β simply re-solves to a different value under the same KL-budget constraint, producing the same relative weighting. Either way, what actually drives the advantage is how much better one rollout's reward was than the batch's typical reward, in relative terms — never the raw units the reward happened to be measured in. That is precisely why the same entropic objective and the same fixed γ = ln 2 KL budget can be dropped, unmodified, into a kernel-runtime task and a math-bound task with completely different reward scales, and behave sensibly in both.

How the KL budget behaves differently early versus late in training

This chapter's earlier description of the adaptive β already named the mechanism: states with roughly uniform reward across their rollouts tolerate a larger β before hitting the γ budget; states with a few standout rollouts hit the budget at a smaller β. Worth adding one more layer the paper names explicitly: this split correlates with where a state sits relative to the current best-known solution, not just what its rewards look like in isolation. States near the current best-known solution — already fairly refined — tend to produce rollouts that all score similarly close to each other, so β can grow large there without blowing the KL budget. States earlier in training, or states with genuine headroom still left to exploit, are exactly where an occasional large improvement shows up among otherwise-mediocre rollouts — and it is precisely those states where a smaller, more conservative β keeps that one lucky rollout from dominating the entire gradient update. The adaptive mechanism is not a single fixed correction; it responds differently depending on how close a given state already is to being fully optimized.

Chapter 9: Limits & Connections

Chapter 8 proved the mechanism works on one kernel-engineering competition. This closing chapter asks the question this entire session has been building toward: does it hold up across genuinely different domains, where does it fall short even by the authors' own admission, and how do the two papers fit together into one coherent picture of what "test-time scaling" actually means.

The record, domain by domain, every result reported honestly

The authors' own stated policy is to report the result on every problem they attempted — wins and losses both. Four domains, using the open gpt-oss-120b model throughout unless noted:

A worked check on the "16 times larger" claim

The paper makes a striking claim about the Erdős problem: their improvement over AlphaEvolve is 16 times larger than AlphaEvolve's own improvement over the previous state of the art. Verify it by hand, using only the three numbers in the table above plus the original human bound of 0.380927:

Exact. The claim survives hand arithmetic. It is also worth noting how that bound was found: a 600-piece, asymmetric step function, where every prior state-of-the-art construction (including AlphaEvolve's own 95-piece result and the best human's 51-piece construction) was symmetric. TTT-Discover found a structurally different kind of solution, not just a more careful version of the same one.

Same method, a deliberately weaker model, still wins

One more result worth isolating, because it separates "the method works" from "the method works because gpt-oss-120b happens to be a strong model." For a closer head-to-head against the concurrent ThetaEvolve result, the authors reran TTT-Discover on the autocorrelation inequalities using Qwen3-8B instead of gpt-oss-120b — a far smaller model, and specifically the plain Qwen3-8B rather than the stronger DeepSeek-R1-distilled variant ThetaEvolve itself used (which was not available on Tinker), putting TTT-Discover at a genuine model-strength disadvantage in this comparison. TTT-Discover with the weaker Qwen3-8B still certified tighter bounds than ThetaEvolve on both autocorrelation inequalities — using 50 training steps of 512 rollouts each, versus ThetaEvolve's own 65 steps of 512 rollouts, a smaller compute budget on top of the weaker model. The gap the authors attribute this to is exactly Chapter 8's two additions: the entropic objective and PUCT reuse, not raw model capability or raw compute.

Circle packing (maximize the summed radii of n non-overlapping circles in a unit square, at n = 26 and n = 32) is the one math result reported purely for completeness rather than as a new discovery: TTT-Discover (again with Qwen3-8B) matches, but does not beat, the best known constructions at both sizes. Worth including anyway, because the algorithm it discovers — initializing circles on a simple staggered or hexagonal grid, then refining with constrained least-squares — is noticeably simpler than the initialization scheme used by the closest competing method, ShinkaEvolve, which relies on simulated annealing just to set up its starting positions. Matching state of the art with a simpler recipe is itself a small, honest data point about what the method is and is not adding.

Where the method honestly does not work

The negative results in the table above are not footnotes — they are the honest edges of what this method can do, and worth reading as carefully as the wins:

And one structural limitation, stated by the authors as their own most important direction for future work: the current method only applies to problems with continuous rewards — a certified numeric bound, a runtime, a score. Problems with sparse or binary rewards, or problems in domains with no automatic way to verify a candidate solution at all, are explicitly out of scope for this version of the method.

Why "continuous rewards only" is not just a footnote

Trace this limitation back to Chapter 7's reward table and the entropic objective Chapter 8 built, because the boundary is not arbitrary — it falls directly out of how those two pieces are built. The entropic objective's β(s) search bisects on a KL-divergence constraint computed from a batch of real-valued rewards; feed it a batch where every rollout scores exactly 0 or exactly 1 (a binary pass/fail reward), and the reweighting has almost nothing left to distinguish: every failing rollout gets the same weight, every passing one gets the same weight, and if nothing in the batch passed at all there is no gradient signal separating any two failing attempts from each other whatsoever. The PUCT reuse rule has the same dependency: Q(s), the maximum reward among a state's children, only orders candidates usefully if reward values actually vary in a way that reflects "closer to solving it" versus "further from solving it." A binary reward gives PUCT nothing finer than "solved" or "not solved" to rank unsolved attempts by. Both of this method's two real additions, in other words, need a graded signal to function at all — which is exactly why sparse or binary-reward problems are named as the method's most important open limitation, not a minor footnote to fix later.

What the domain experts actually said

Beyond leaderboard numbers, the paper had independent domain experts review the discovered solutions directly — worth reading because expert reaction is a different, more qualitative kind of validation than a benchmark score. On the Erdős and autocorrelation constructions, a reviewing mathematics professor (Davide Torlo, Università di Roma La Sapienza) confirmed the bounds are straightforward to verify by direct evaluation of the certifying step function against the stated constraints — the discovered answer is checkable, not just claimed. On the TriMul kernels, the GPUMode competition organizers themselves reviewed the winning submission and confirmed the diagnosis was correct (the workload is memory-bound because of surrounding elementwise operations, not the matmul itself) and the fusion strategy matches what the best human submissions already did, just executed more thoroughly and consistently — while also flagging a real caveat: storing activations in fp16 is within the competition's stated tolerances, but could be a numerical-stability risk in a broader production workload outside those exact tolerances. On the single-cell denoising result, a reviewing biologist (Eric Sun, MIT) confirmed the technique is a sensible, smoothing-based extension of MAGIC that yields genuine improvements on the stated metrics — while explicitly cautioning that metric improvements on a benchmark do not automatically guarantee improved biological insight downstream, a limitation the discovery itself cannot resolve and the paper does not pretend it does.

The cost, and what it buys

Every result above — every new state of the art — was produced with an open model, gpt-oss-120b, at roughly $500 of compute per problem. The paper's own framing of why that matters: prior best results in several of these same domains (AlphaEvolve, ShinkaEvolve) required closed frontier models. Beating a frontier-model ensemble's result with an open 120B model and a few hundred dollars of test-time training is itself part of the result, not just a footnote about reproducibility.

The three-way compute picture, put together

Zoom all the way back out. There are now three genuinely different places to spend a compute budget, and this session has built the case for when each one wins:

The bridge between the second and third rows is the exact gap Chapter 6 identified and Chapter 7 named directly: search over a frozen model can only ever find what that model's distribution already assigns some probability to. On the hardest MATH questions (bin 5), Chapter 3 found that nothing — not better search, not compute-optimal allocation — moved the needle much. TTT-Discover exists precisely for that regime: genuinely novel, previously-unsolved problems, where the fix is not a smarter way to search the model's existing knowledge, but new experience, generated and trained on, specific to the one problem that matters.

What you should be able to do now

If this session worked, you should be able to, without looking anything up: explain precisely why beam search against a PRM sometimes gets worse with more budget; derive the FLOP-matched exchange rate between pretraining and test-time compute from the two Kaplan-style FLOPs formulas; explain why a discovery problem's objective is structurally different from ordinary RL's; and state, in one sentence, what test-time training can reach that test-time search alone cannot — and why.

“To solve hard problems, humans often need to try, fail, stumble upon partial successes, and then learn from their experiences.” — opening line, Learning to Discover at Test Time, 2026

References

1. C. Snell, J. Lee, K. Xu, A. Kumar. “Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters.” 2024. arXiv:2408.03314
2. M. Yuksekgonul, D. Koceja, X. Li, F. Bianchi, J. McCaleb, X. Wang, J. Kautz, Y. Choi, J. Zou, C. Guestrin, Y. Sun. “Learning to Discover at Test Time.” 2026. arXiv:2601.16175
3. H. Lightman et al. “Let's Verify Step by Step.” (source of the PRM800k dataset and the pass@1 difficulty-binning methodology this session builds on.) 2023.
4. P. Wang et al. “Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations.” (the Monte Carlo rollout method used to train the PRM in this session's Chapter 1.) 2023.
5. Y. Qu et al. “Recursive Introspection: Teaching Language Model Agents How to Self-Improve.” (the revision-model finetuning recipe this session's Chapter 4 builds on.) 2024.
6. J. Kaplan et al. “Scaling Laws for Neural Language Models.” (source of the 6ND FLOPs approximation used in this session's Chapter 6.) 2020.
7. D. Silver et al. “Mastering the Game of Go without Human Knowledge.” (source of the PUCT formula this session's Chapter 8 adapts.) 2017.
8. Novikov et al. “AlphaEvolve: A coding agent for scientific and algorithmic discovery.” (the evolutionary-search, frozen-model baseline this session's Chapters 7–9 compare against throughout.) 2025.

A name worth disambiguating: two different "test-time training"s

The term test-time training already existed in machine learning before this paper, and it is worth being precise about the difference, since the name is shared but the mechanism is not. Classic test-time training (Sun et al.) adapts a model to a single new input using a self-supervised auxiliary task — some proxy objective computed without any task-specific reward, just to nudge the model's internal representations toward the specifics of the one example in front of it. TTT-Discover shares the "keep training at test time" instinct, but the mechanism is genuinely different: it uses real, task-specific reinforcement learning, driven by an actual verifiable reward signal (a certified bound, a runtime, a score), not a self-supervised proxy. One adapts representations to an input; the other learns, via trial, reward, and reuse, to solve one specific problem outright.

Connections on this site

This session assumed you already understand how an LLM samples tokens and how policy-gradient RL updates weights. If either felt shaky, or you want to go deeper on any single piece built here, these are the lessons underneath and around this one:

• Scaling Test-Time Compute (Snell 2024) (Veanors) — the full paper-grade walkthrough of this session's first paper, with additional figures and appendix detail this course-format session compressed.
• AlphaEvolve (Veanors) — the frozen-model, evolutionary-search baseline that Chapter 7 names directly as the method TTT-Discover is built to go beyond.
• AB-MCTS and Monte Carlo Tree Search (Gleams) — the tree-search family that lookahead search (Ch 3) and PUCT reuse (Ch 8) both draw from.
• Self-Consistency (Wang 2023) (Veanors) — majority voting as a selection mechanism, the same idea Chapter 4 uses to pick an answer from a revision chain.
• DeepSeek-R1 (Veanors) — reasoning capability built in at training time via large-scale RL, a useful contrast to Chapter 8's RL applied at test time on a single problem.
• CS224N: Reasoning I and CS224N: Reasoning II (Gleams) — the broader landscape of chain-of-thought and inference-time reasoning techniques this session's search and revision methods sit inside.
• CS 8803-LLM Session 07: Agent Harness — where an agent's own tool-use loop becomes another place test-time compute gets spent, beyond single-turn search or revision.