Process rewards and test-time compute

Here is a model that solves a certain competition problem 30% of the time. You can afford to run it 64 times. What should you do with the 64 answers? Submit the most common one? Ask a second model to grade them and submit the best? If you had a perfect grader, you would almost surely find a correct answer: all 64 attempts fail with probability $0.7^{64} \approx 1.2 \times 10^{-10}$. With an imperfect grader, the answer is less obvious. As you will see, more samples can make it worse.

Now flip to training. The model writes a 20-step solution and gets the final answer wrong. Chapter 15’s GRPO gives every token of that solution the same negative advantage, including the 15 steps that were fine. Which step was the mistake? If you could tell, you could push down only that step.

Both questions need the same tool: a verifier, a model that judges solutions, and in particular one that judges each step of a solution rather than only the final answer. This chapter is about such step-level judges, called process reward models, and about the other half of the story they made possible: test-time compute, spending extra computation at inference time to get better answers. You will see where the ideas come from (a Monte Carlo value estimate from Chapter 5, an advantage from Chapter 8, tree search from Chapter 10), what they buy, and why the large reasoning-model runs of 2025 mostly did not train with them.

Two ways to spend compute

Until 2024 the main way to get a better language model was to spend more compute before deployment: a bigger model, more pretraining data, more post-training. Test-time compute (also called inference-time compute) is the other knob: keep the model fixed and spend more computation per question when it is asked.

When OpenAI announced o1 in September 2024, its central claim was that accuracy kept improving along both axes: with more reinforcement-learning compute during training, and with more time spent “thinking” at test time. OpenAI did not disclose how. Chapter 15 told the training half of the story through DeepSeek-R1. This chapter tells the test-time half, and the two halves meet at the end.

There are two basic ways to spend test-time compute:

• Parallel: sample $N$ independent solutions, then pick one. The ways to pick are majority vote, best-of-$N$ with a verifier, and weighted voting.
• Sequential: make one solution better by spending more on it: revise it, check it, or think longer before answering.

Search mixes the two: grow many partial solutions in parallel, extend the promising ones step by step, and prune the rest. To prune, you need a judge of partial solutions, which is exactly what a process reward model is.

A note on letters. In this chapter $N$ is the number of samples drawn at test time. Chapter 15’s $G$ is the group size used during training. Both count samples per prompt, but they serve different purposes. We write $p$ for the probability that one sample is correct.

Parallel sampling: the ceiling

Start with the most optimistic case. Suppose an oracle could look at your $N$ samples and tell you which ones are right. Then you succeed whenever at least one sample is right. The probability of that is called pass@N.

Take the hook’s numbers: $p = 0.3$ and $N = 4$. A single sample is wrong with probability $0.7$. All four samples are wrong with probability $0.7^4 = 0.2401$, so

In general, for independent samples,

It rises quickly to 1 for any $p > 0$. On a benchmark, each problem has its own $p_j$, and pass@N is the average of $1 - (1 - p_j)^N$ over problems. Problems with $p_j = 0$ never get solved. On problems with small $p_j$, the term $e^{-p_j N}$ falls slowly, so averaged over a realistic mix of easy and hard problems pass@N tends to grow roughly linearly in $\log N$ for a long time. Brown et al. (2024, “Large Language Monkeys”) measured this across four orders of magnitude of samples. For example, they report that DeepSeek-Coder-V2 solves 15.9% of SWE-bench Lite issues with one sample and 56% with 250.

pass@N is a ceiling, not a strategy. It assumes you can recognize the right answer. Sometimes you can: a unit-test suite or a proof checker is close to an oracle, so for code with good tests “sample until the tests pass” works. (Even then, weak tests let wrong programs through. We return to this below.) For most questions you need some way to choose, and every way of choosing falls short of the ceiling.

Majority vote: let the samples vote

The simplest way to choose needs no grader at all. Sample $N$ reasoning chains, read off each one’s final answer, and return the most common answer. Wang et al. (2022) called this self-consistency: different chains of thought that reach the same answer support each other. They report that it improved chain-of-thought prompting on GSM8K by 17.9 percentage points. It is also called majority voting, or maj@N (DeepSeek’s reports write cons@N).

Right or wrong: the jury theorem

Start with the simplest case, where every sample is either right or wrong, so there are only two possible answers. With $N = 3$ samples, the vote is right when at least 2 of the 3 are right:

For $p = 0.6$ this is $0.216 + 0.432 = 0.648$, better than 0.6. For $p = 0.4$ it is $0.064 + 0.288 = 0.352$, worse than 0.4. In general, with $c$ the number of right samples,

This is the Condorcet jury theorem: if each juror is right more often than not, a large jury is almost always right. If each is wrong more often than not, a large jury is almost always wrong. For $p = 0.6$, maj@11 is 0.753 and maj@101 is 0.979. The physics is the law of large numbers. The fraction of right votes concentrates around $p$ with width about $\sqrt{p(1-p)/N}$, so the vote’s outcome freezes onto whichever side of $\tfrac12$ the mean $p$ sits on.

Many possible answers: you only need to be the most popular

Real answers are not binary. A wrong answer to a math problem can be any of many numbers. Majority vote doesn’t need a majority of right samples, only a plurality: the right answer must be more common than each wrong answer separately.

Take $p = 0.3$. Suppose 30% of the wrong samples share one popular wrong answer (a common slip), so that answer has probability $0.3 \times 0.7 = 0.21$, and the remaining wrong samples scatter over many different numbers. The right answer (0.3) is the single most likely answer. As $N$ grows, the empirical frequencies converge to these probabilities, so majority vote converges to the right answer even though 70% of the samples are wrong. Now change the common slip’s share to 60%. The popular wrong answer then has probability 0.42, more than 0.3, and majority vote converges to that answer with certainty.

Majority vote has two other limits. It needs answers you can compare for equality: a number, a multiple-choice letter, the output of a program. It does nothing for proofs or essays, where no two samples are identical. And it spends no effort judging anything. It trusts the model’s own distribution. That is a strength, because there is nothing to fool. It is also why a different idea is needed to get past the ceiling.

Verifiers: best-of-N and weighted voting

A verifier is a model that reads a problem $x$ and a solution $y$ and outputs a score, ideally the probability that $y$ is correct. Because it scores the outcome of a whole solution, it is also called an outcome reward model (ORM). It is the same object as Chapter 12’s reward model, trained on correct/incorrect labels instead of preferences. Cobbe et al. (2021) introduced the GSM8K benchmark together with this idea: they trained verifiers on model-written solutions labeled by whether the final answer was right, then used them to rerank samples.

Two ways to use a verifier on $N$ samples:

• Best-of-N: return the answer of the single highest-scoring sample.
• Weighted majority vote (Snell et al. call it “best-of-N weighted”): add up the scores of all samples that give the same final answer, and return the answer with the largest total. With equal scores it reduces to majority vote. With a perfect 0/1 verifier it reduces to “any verified answer”.

A model of an imperfect verifier

To reason about verifiers, you need a model of how they err. Use the simplest one from signal detection theory. The verifier computes a hidden score $z$ for each sample:

The single number $d'$ (read “d-prime”) measures how far apart the two score distributions are, in units of their spread. $d' = 0$ is a useless verifier. $d' = 3$ separates the two groups well. For weighted voting you want a probability rather than a raw score. The demo and the lab report $v = \sigma\big(d'(z - d'/2)\big)$, which is exactly the posterior probability that the sample is correct when right and wrong samples are equally common a priori. (Check this with Bayes’ rule: the log-likelihood ratio of the two Gaussians at $z$ is $d' z - d'^2/2$.)

Here is a worked example. Take $N = 2$, one correct and one wrong sample. Best-of-2 picks the correct one when $z_\text{right} > z_\text{wrong}$. The difference $z_\text{right} - z_\text{wrong}$ is Gaussian with mean $d'$ and variance 2, so

where $\Phi$ is the standard normal CDF. (This number is also the verifier’s AUC, the probability that it ranks a random right answer above a random wrong one.) For $d' = 2$, $\Phi(1.414) = 0.921$. Now average over what the two samples turn out to be, with $p = 0.3$. Both are right with probability $p^2 = 0.09$, and one is right with probability $2p(1-p) = 0.42$:

That beats one sample (0.30) and majority vote at $N = 2$ (also 0.30: a 1–1 split is a coin flip). It falls short of pass@2 (0.51).

Why an imperfect verifier eventually hurts

In this Gaussian model more samples only help: best-of-N climbs toward 1. Real experiments tell a different story. Cobbe et al. found that their 6B verifier’s accuracy improved as they reranked up to 400 completions per problem, and then decreased. They wrote that “the benefits of search are eventually outweighed by the risk of finding adversarial solutions that fool the verifier.” Stroebl, Kapoor and Narayanan (2024) found the same for code. Unit tests with limited coverage let some wrong programs pass (false positives), and resampling until the tests pass often peaks within 10 attempts before the curves bend down.

The missing ingredient is convincing wrong answers: rare wrong solutions that the verifier likes more than typical right ones. Add them to the model. Each wrong sample is convincing with a small probability $f$, and then $z \sim \mathcal N(d' + 1, 1)$.

Best-of-N is an extreme-value problem. It returns the maximum of $N$ scores, and the maximum comes from whichever group has the heaviest upper tail, weighted by how many members it has. While $N$ is small, the pool probably contains no convincing wrong answer, and the right answers’ tail wins. That is the rising part of the curve. The expected number of convincing wrong answers among $N$ samples is $f(1 - p)N$. Once that number reaches order 1, at

the pool usually contains one, and it outscores the honest answers. From there accuracy falls, toward zero as $N \to \infty$. With $p = 0.3$ and $f = 2\%$, $N^\star \approx 71$: the demo shows the peak somewhat before that and a steady decline after.

Weighted voting resists this failure. A single convincing wrong answer contributes one score to its answer’s total. To win, a wrong answer must collect more total score than the right answer, which typically appears many times. So in the demo, weighted voting keeps most of best-of-N’s early gain and does not decline. It does inherit a version of majority vote’s plateau. This is one reason Snell et al. (2024), and many systems after them, aggregate with weighted voting rather than plain best-of-N.

Outcome versus process: grading the steps

Return to the training question. A reasoning model writes a chain of steps $z_1, z_2, \dots, z_T$ (a “step” might be one line of math or one paragraph) and then a final answer. (These $z_j$ are pieces of text. They have nothing to do with the verifier score $z$ of the previous section.) Rewards come in two kinds:

• Outcome supervision: one label for the whole solution, usually whether the final answer is correct. That is what an ORM predicts and what Chapter 15’s verifiable rewards provide.
• Process supervision: a label for each step: is this step correct (and useful)? A model trained to predict these labels is a process reward model (PRM).

Process labels help with credit assignment, the problem you met in Chapter 1: when an outcome is bad, which decision caused it? An outcome label says that something in the 20 steps went wrong. A process label says which step.

Uesato et al. (2022, DeepMind) ran the first careful comparison, on GSM8K. Outcome supervision reached similar final-answer accuracy with fewer labels. But solutions that reach the right answer can still contain wrong reasoning, and getting the reasoning right needed process supervision, or a reward model trained to imitate it. They report improving the best results from 16.8% to 12.7% final-answer error, and from 14.0% to 3.4% reasoning error among solutions with correct final answers.

Let’s Verify Step by Step

Lightman et al. (2023, OpenAI) scaled this up. Human labelers marked each step of model-written solutions to MATH problems as positive, negative or neutral. Labeling stopped at the first mistake. For a correct solution, the process labels then carry the same information as the outcome label (“all fine”). For a wrong one, they add where it broke. The result is PRM800K: 800,000 step labels on 75,000 solutions to 12,000 problems.

To compare whole solutions, they need one score per solution. They used the probability that every step is correct, computed as the product of the PRM’s per-step probabilities $\hat p_j$:

They generated 1,860 solutions per problem and picked the best by each method, on a 500-problem subset of the MATH test set. The PRM solved 78.2%, the ORM 72.4% and majority voting 69.6%. They also found that active learning, which spends the labeling budget on convincing wrong solutions (ones the current PRM rates highly but that reach a wrong answer), made the labels 2.6× more data-efficient.

Other papers aggregate the step scores differently. Math-Shepherd takes the minimum step score: a chain is only as strong as its weakest link. Snell et al. use the PRM’s prediction at the last step, which works when the PRM predicts values (next section) rather than step correctness.

Process labels for free: roll out from each step

Human step labels are expensive. PRM800K took a large labeling effort for one domain and one model’s style of solutions. Wang et al. (2024, Math-Shepherd) replaced the labeler with Monte Carlo rollouts.

Take a solution and cut it after step $j$. From that prefix, let a model (the completer) finish the solution $k$ times, and check each final answer against the known answer. Then label step $j$ with one of the two labels below. (Math-Shepherd writes them $y^\text{SE}$ and $y^\text{HE}$, for soft and hard estimation. We use $\ell$, because $y$ is the response in this course.)

You have seen this before. Chapter 5’s Monte Carlo prediction estimates $V^\pi(s)$ by averaging the returns of episodes that start from $s$. Here the state is “problem plus the first $j$ steps”, the policy is the completer, and the return is 1 for a right final answer and 0 otherwise. So the soft label is a Monte Carlo estimate of a value function:

Equivalently, it estimates the Q-value of writing step $z_j$ after the prefix $z_{< j}$, since in a language model the next state is fully determined by the action (the text just gets appended). A PRM trained on these labels is a learned value function, a critic. Snell et al. say so directly: their PRM’s per-step predictions “correspond to value estimates of reward-to-go for the base model’s sampling policy”.

A worked example

Make it concrete with the toy task used in this chapter’s second demo and in the lab. The problem: “Start with 4. Add 7, 3, 9, 5, 8, 2 in turn, writing only the last digit each time.” The right running digits are 1, 4, 3, 8, 6, 8. The policy slips at each step with a probability that grows with the number being added, $e = 0.04 + 0.03 \times (\text{number})$: 25% for $+7$, 13% for $+3$, 31% for $+9$, then 19%, 28% and 10%. A slip writes one of the 9 wrong digits, chosen uniformly. After a slip it carries on from its own wrong digit, so one slip usually ruins the answer. Now and then a second slip lands back on the right track by luck.

Here is a solution that slips at step 3: it writes 1, 4, 2, 7, 5, 7 (4 + 9 = 13, so it should have written 3). Its final answer is 7, not 8. The exact value of each prefix, computed from the two-state Markov chain in the lab’s chain.py, is:

Check one entry by hand. After step 2 the solution is on track, and the remaining four steps succeed with probability about $0.69 \times 0.81 \times 0.72 \times 0.90 = 0.362$. The exact 0.385 is a little higher because of lucky recoveries. After step 3 the solution is off track, and only a lucky slip can bring it back: for a step with slip probability $e$, the chance of slipping onto exactly the right digit is $e/9$. So the value collapses to 0.052.

Now define the process reward of step $j$ as the change in value it causes:

For our solution: $r = (+0.068, +0.041, -0.333, -0.013, -0.028, -0.011)$. The blame lands on step 3, as it should. Steps 1 and 2 get small positive rewards: they were good moves, each surviving a risky step. Compare outcome-only training with a baseline (Chapter 15’s group mean estimates $V_0$). Every step gets the same advantage, $0 - 0.276 = -0.276$, so steps 1 and 2 are punished too.

The rollouts also bring their own errors. With few rollouts the soft labels are noisy, and a noisy drop can land on the wrong step. Hard labels have a subtler flaw. From the bad prefix after step 3 the true value is 0.052, but with $k = 16$ rollouts the chance that at least one gets lucky is

so more than half the time the hard label calls the mistaken step “good”. With $k = 64$ it rises to 0.97. The hard label’s expectation is $1 - (1 - V)^k$, which is pass@k from that prefix. It answers “can this prefix still reach the right answer?” rather than “is this a good step?”. Hard labels get worse at flagging mistakes as $k$ grows. Math-Shepherd saw exactly this. Checked against 160 human-labeled steps, their hard labels were 86% accurate with 4 rollouts and became less accurate with more rollouts, which the authors attribute to false positives. They trained on hard labels anyway, and report that verifiers trained on soft or hard labels performed about the same.

What can go wrong with automatic labels

• The labels belong to the completer. $V^\pi$ depends on $\pi$. A strong completer can recover from a sloppy step and rates it well. A weak completer fails even after a good step and rates it badly. Setlur et al. turn this into a design choice: they measure progress under a separate “prover” policy, and argue that a well-chosen prover can be weaker than the policy being improved.
• Value is not correctness. A step can be correct but unpromising, or a lucky wrong step can still lead to the right number. Zhang et al. (2025, Qwen, “The Lessons of Developing PRMs in Mathematical Reasoning”) report that Monte Carlo labels gave worse PRMs than labels from an LLM judge or from humans. They also report that evaluating PRMs only by best-of-N accuracy gives a biased picture. ProcessBench (Zheng et al., 2024) asks PRMs to find the earliest error in competition-level solutions. It found that existing PRMs generalized poorly beyond GSM8K and MATH, and did worse than LLMs prompted to critique.
• Steps are hard to define. Math solutions have lines. A long chain of thought that wanders, backtracks and says “wait” does not split cleanly into steps.

Using a PRM: search

A PRM scores partial solutions, so you can use it during generation, not only after. This is decision-time planning, the idea behind Chapter 10’s Monte Carlo tree search, applied to text.

Step-level beam search

Step-level beam search with a PRM (beam width B, M proposals per beam)
beams ← [ empty solution ]
repeat until every beam has a final answer:
    candidates ← []
    for each prefix in beams:
        sample M next steps from the policy; append each to the prefix
        add the extended prefixes to candidates (drop duplicates)
    score every candidate with the PRM
    beams ← the B highest-scoring candidates
return the best-scoring finished solution

At each step, partial solutions the PRM dislikes are dropped before you spend any more tokens on them. The compute that best-of-N would have spent finishing doomed solutions goes into extending promising ones. With an accurate PRM this is a large saving. In the lab’s toy problem, beam search with a good PRM solves about 80% of problems using the compute of two full samples, where best-of-2 solves about half.

The catch is that the search is a stronger optimizer against the PRM than best-of-N is, so it finds the PRM’s mistakes faster. Snell et al. (2024) observed both sides on MATH, with a PRM trained from Monte Carlo labels:

• At small generation budgets, beam search clearly beat best-of-N. As the budget grew, the advantage shrank, and beam search often fell behind.
• On easy questions, beam search got worse with more budget, a sign of exploiting the PRM. They found search producing low-information repetitive steps, or solutions of only one or two steps. On harder questions it consistently beat best-of-N.
• An even stronger search, lookahead (rolling out a few steps ahead before scoring, a little like MCTS), did worst at equal compute.

Tree search and AlphaZero

Chapter 10’s MCTS is the natural next step: select partial solutions with a UCB rule, expand with the policy, evaluate with a value function (a PRM) or a rollout, and back up. For board games this, plus learning, gave AlphaZero. For language it has been harder. DeepSeek-R1’s report describes an MCTS attempt guided by a learned value model and lists why it didn’t scale: the token-level search space is vastly larger than chess’s, and “training a fine-grained value model is inherently difficult”. Their conclusion: MCTS “can improve performance during inference when paired with a pre-trained value model”, but using self-search to improve the model iteratively, as AlphaZero does, “remains a significant challenge.”

Sequential revision, and which strategy to use when

Parallel samples are independent: sample 17 knows nothing about the first 16. Sequential revision conditions each new attempt on earlier ones: “here is your previous answer; find the error and try again.” Snell et al. fine-tuned a model to revise its own answers and compared spending a budget on parallel samples against sequential revisions. On easier questions revisions did better: the model was near a right answer and needed polishing. On harder questions parallel sampling did better: it had to explore entirely different approaches. The best mix depended on difficulty.

That gives the key idea of the paper, compute-optimal test-time scaling: estimate how hard a question is, then pick the strategy and budget per question. Snell et al. report that this allocation matches best-of-N while using up to 4× less test-time compute. In a FLOPs-matched comparison, a small model with optimal test-time compute could outperform a 14× larger model, but only on questions where the small model already had non-trivial success. On the hardest questions, a bigger pretrained model was the better use of compute. Exercise 17.6 builds the intuition with two problems and a fixed budget.

Using a PRM in training: dense rewards

Back to the original training question. A PRM, or Monte Carlo values, can turn a single end-of-solution reward into a reward per step, giving dense rewards. Plugged into a policy gradient, step $j$‘s tokens get an advantage built from rewards at and after step $j$ (reward-to-go, Chapter 7), instead of one shared number.

• Math-Shepherd trained Mistral-7B with “step-by-step PPO”, giving the PRM’s reward at the end of each step. They report GSM8K rising from 77.9% to 84.1% and MATH from 28.6% to 33.0%. Adding Math-Shepherd reranking at test time raised these further.
• DeepSeekMath, the paper that introduced GRPO (Chapter 15), also describes a process-supervision variant. Each step’s PRM reward is normalized across the group, and the advantage of a token is the sum of the normalized rewards of all steps that end at or after it.
• VinePPO (Kazemnejad et al., 2024) skips the learned PRM entirely. It keeps PPO (Chapters 8–9) but replaces the learned critic with Monte Carlo value estimates: a few rollouts from intermediate states. Language makes this possible, because you can “reset” generation to any prefix.

Why the big 2025 runs used outcome rewards

DeepSeek-R1’s report lists PRMs among its “unsuccessful attempts”, for three reasons: it is hard to define a step in general reasoning, hard to judge whether an intermediate step is correct (automatic labels were unsatisfactory and human labels don’t scale), and “once a model-based PRM is introduced, it inevitably leads to reward hacking”, with retraining the PRM adding cost and complexity. They conclude that PRMs are good at reranking and guided search, but that during large-scale RL the gains were small compared with the extra compute. Kimi k1.5, released the same week, likewise trained without MCTS, value functions or PRMs. Chapter 15’s rule-based outcome rewards won at scale.

Reward hacking is easy to picture. Suppose the PRM gives each step a reward near +1 when it looks correct. Then a policy can farm reward by writing many short steps that are correct but say nothing (“Let me restate the problem.”), padding a solution without making progress. Snell et al. saw search produce exactly this kind of low-information repetition. Defining step rewards as advantages (changes in value) instead of absolute scores removes the incentive to pad, because a step that changes nothing earns zero. This is part of Setlur et al.’s argument for rewarding progress.

Implicit PRMs and PRIME

A different fix makes the PRM cheap enough to retrain online. Yuan et al. (2024, “Free Process Rewards without Process Labels”) borrowed the parameterization of Chapter 13’s DPO. Train an outcome reward model whose reward is a log-likelihood ratio between two language models,

using only response-level correct/incorrect labels. Because $\log \pi(y)$ is a sum over tokens, the partial sums

are defined for every prefix, and their differences give per-token (or per-step) rewards “for free”. They prove that $q_t$ is a soft value of the prefix, so these are process rewards in the sense of this chapter. They report that this implicit PRM beat a Math-Shepherd-trained PRM using less than 1/38 of the training data.

PRIME (Cui et al., 2025) puts this into RL. The policy samples solutions, an outcome verifier labels them, and those same labels update the implicit PRM online with a cross-entropy loss. The dense token rewards from the PRM are combined with the outcome rewards in an RLOO-style advantage (Chapter 16). Because the PRM keeps training on the current policy’s samples, the policy has a harder time exploiting a frozen PRM’s blind spots. The paper names online PRM updates as the key ingredient. Starting from Qwen2.5-Math-7B-Base, they report a 15.1% average improvement over the SFT model across reasoning benchmarks, and a 2.5× gain in sample efficiency and a 6.9% improvement over outcome-only RL.

Generative verifiers and the generator–verifier gap

So far the verifier has been a classifier: a language model with a head that outputs one number. A generative verifier checks the solution in words, writing a critique step by step, and ends with a verdict such as “Is the answer correct? Yes”. Zhang et al. (2024, “Generative Verifiers”) train verification as ordinary next-token prediction, so a verifier can reason with chain of thought, and can sample several verification rationales and vote. Test-time compute then goes into checking as well as generating. ThinkPRM (Khalifa et al., 2025) applies the same idea to process verification. A long-chain-of-thought verifier checks every step, and with about 1% of PRM800K’s labels it beat discriminative PRMs in their experiments. Chapter 14 covers LLM judges and generative reward models more broadly.

Every method in this chapter rests on one assumption: checking is easier than generating. Call the difference the generator–verifier gap. When it is large, a model can usefully sample, judge and select, and even train on its own filtered outputs. Song et al. (2024, “Mind the Gap”) formalized self-improvement in terms of this gap and found that a version of it grows steadily with pretraining compute. Sudoku, code with tests and proofs with a checker have a large gap. Recalling a fact has almost none: if the model doesn’t know a capital city, asking it to check one won’t help. DeepSeekMath-V2 (2025) trains a proof verifier and then a generator rewarded by it. It spends extra compute on verification to keep the gap open as the generator improves. With heavy test-time compute it reports gold-level IMO 2025 performance and 118/120 on Putnam 2024.

Long chains of thought: search inside a single sample

There is a third way to spend test-time compute, and it is the one o1 and R1 use: one long sample. Chapter 15’s R1-Zero learned, from outcome rewards alone, to write longer and longer chains of thought that try an approach, check it, notice a problem (“Wait…”), backtrack and try again. That is search, but done by the policy inside its own context, not by an external algorithm. In a sense, RL with outcome rewards trains the model to be its own generator, verifier and search procedure at once.

This is AlphaZero’s idea in a new form. AlphaZero trains its policy network toward the move distribution found by tree search, so over training the network absorbs the search. Long-CoT RL trains the policy on the outcomes of its own extended reasoning, so the policy absorbs a search procedure, with the context window acting as the search tree.

Sequential test-time compute is then a dial on chain length. Budget forcing (Muennighoff et al., 2025, “s1”) turns it directly. To stop thinking early, append the end-of-thinking delimiter. To make the model think longer, suppress the delimiter when the model tries to stop and append “Wait”, which often makes it re-check its work. With only 1,000 curated training examples on top of Qwen2.5-32B-Instruct, budget forcing extended s1-32B’s AIME24 accuracy from 50% to 57%. The authors also report that the gains eventually flatten. Suppressing the end too often can push the model into repetitive loops.

Parallel and sequential compute combine. DeepSeek-R1’s first report gives R1-Zero 71.0% pass@1 on AIME 2024 and 86.7% with majority voting over 64 samples (cons@64). That is a self-consistency gain stacked on top of long chains of thought.

Summary

• pass@N $= 1 - (1-p)^N$ is the ceiling for any way of picking one of $N$ samples. Estimate pass@k without bias with $1 - \binom{n-c}{k}/\binom{n}{k}$.
• Majority vote (self-consistency) converges to the mode of the answer distribution: it amplifies when the right answer is the most common one and plateaus at the fraction of problems where it is. No verifier is needed, but answers must be comparable.
• Best-of-N with a verifier can beat majority vote, but it is an extreme-value selection. Once the pool is likely to contain a wrong answer the verifier over-rates (around $N \approx 1/(f(1-p))$), accuracy falls. Weighted voting is more robust.
• Process supervision labels steps, not just outcomes. Lightman et al.’s PRM beat both an ORM and majority vote for reranking (78.2% vs 72.4% vs 69.6% on a MATH subset).
• Math-Shepherd labels (fraction of rollouts from a prefix that succeed) are Monte Carlo value estimates. Their differences $V_j - V_{j-1}$ are step-level advantages, which telescope to outcome minus baseline. Hard labels estimate pass@k from the prefix and miss mistakes as $k$ grows.
• A PRM enables step-level search (beam search, lookahead, MCTS). It saves compute when the PRM is accurate, but a stronger optimizer exploits the PRM’s errors sooner. Compute-optimal allocation depends on question difficulty (Snell et al.).
• In large-scale RL, PRMs have mostly lost to verifiable outcome rewards: steps are ill-defined, labels are noisy, and PRMs get hacked (DeepSeek-R1). Implicit PRMs / PRIME and Monte Carlo values (VinePPO) are ways to get dense rewards without a frozen, hackable PRM.
• Long chain of thought is search learned by the policy itself. Budget forcing and majority voting turn the test-time dial further. Everything rests on a generator–verifier gap.

Exercises

def pass_at_k(n, c, k):
    if n - c < k:
        return 1.0
    return 1.0 - comb(n - c, k) / comb(n, k)

def majority_vote_accuracy(p, n):
    total = 0.0
    for c in range(n + 1):
        prob = comb(n, c) * p**c * (1 - p) ** (n - c)
        total += prob if 2 * c > n else 0.5 * prob if 2 * c == n else 0.0
    return total

def weighted_vote(answers, scores):
    total = defaultdict(float)
    for a, s in zip(answers, scores):
        total[a] += float(s)
    best = max(total.values())
    return next(a for a in answers if total[a] == best)

beams, n_generated = [[]], 0
for _ in range(len(problem.ops)):
    candidates, seen = [], set()
    for prefix in beams:
        for _ in range(expand):
            new = prefix + [task.policy_step(problem, prefix, rng)]
            n_generated += 1
            if tuple(new) not in seen:
                seen.add(tuple(new))
                candidates.append(new)
    scores = [prm(problem, c) for c in candidates]
    order = sorted(range(len(candidates)), key=lambda i: -scores[i])
    beams = [candidates[i] for i in order[:beam_width]]
return beams[0], n_generated

cd 17-process-rewards
python -m pytest -q          # your code: tests fail until you fill in the TODOs
RL_SOLUTIONS=1 python -m pytest -q   # reference solutions: all pass

Further reading

• Snell, Lee, Xu & Kumar (2024), Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. The clearest map of test-time strategies (best-of-N, beam search, lookahead, revisions) and of how the best choice depends on difficulty. Sections 5–7.
• Lightman et al. (2023), Let’s Verify Step by Step. The PRM800K paper: process vs outcome supervision for reranking, with careful experimental design. Short and readable.
• Wang et al. (2024), Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations. Process labels from Monte Carlo rollouts, used for both reranking and step-by-step PPO. Section 3 is the labeling method.
• Cobbe et al. (2021), Training Verifiers to Solve Math Word Problems. GSM8K, the original ORM recipe, and the first report of best-of-N turning down as N grows.
• Wang et al. (2022), Self-Consistency Improves Chain of Thought Reasoning in Language Models. Majority voting over reasoning chains. A short paper that set the baseline everyone compares against.
• Setlur et al. (2024), Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning. Process rewards as advantages (“progress”) under a prover policy, for both search and dense RL rewards.
• Cui et al. (2025), Process Reinforcement through Implicit Rewards (PRIME), with Yuan et al. (2024), Free Process Rewards without Process Labels. Dense rewards from an implicit, online-updated PRM.
• Muennighoff et al. (2025), s1: Simple test-time scaling. Budget forcing and the minimal recipe for sequential test-time scaling. Also read Stroebl, Kapoor & Narayanan, The Limits of Inference Scaling Through Resampling, on why imperfect verifiers cap resampling.

Next, Chapter 18 takes the model out of the single-answer setting: agentic and multi-turn RL, where a trajectory includes tool calls and observations, and credit assignment over long horizons becomes the central problem.