REASONING FROM SCRATCH · CHAPTER 02
One chain of thought can still be wrong. Sample several. Then let a vote, a score, or a search pick the survivor. The weights stay frozen.
The harbor clerk from chapter 01 now writes six answers to the same crate puzzle. Four say 38. One dropped West and wrote 28. One added instead of subtracting and wrote 42. You do not retrain the clerk. You look at the slips.
A vote says 38. A quality score on the whole slip might also pick a 38. A step-by-step grader can throw out the chain that added 6. That is test-time search: spend more samples, then verify.
Snell et al. (2024) split the job in two. The model is a proposal: it writes candidates. The verifier ranks or prunes them. You can scale either side. This chapter is the site’s home for that split.
Sample traces at temperature \(T > 0\). More samples, more diversity — until the model collapses to one phrasing. A single greedy decode is a proposal of size 1.
slips · scorer · decode · BoN
A vote counts answers. An outcome reward model (ORM) scores the finished reply. A process reward model (PRM) scores each step. A program can do the same job when the answer is checkable.
DeepSeek-R1 tried PRMs and Monte-Carlo tree search and dropped both for training. That does not make them useless at inference. It means a learned process judge is expensive and easy to game. Keep the distinction in mind when later chapters put a verifier in the reward.
Self-consistency (Wang et al. 2022) is majority vote over sampled finals. On our six slips:
38 appears four times. 28 and 42 appear once each. The vote is 38.
Best-of-N keeps the sample with the highest ORM score instead of counting. Same six slips, made-up but consistent scores:
| Sample | 38 | 38 | 28 | 38 | 42 | 38 |
|---|---|---|---|---|---|---|
| ORM | 0.91 | 0.84 | 0.62 | 0.88 | 0.71 | 0.55 |
Best-of-N picks the first 38, score 0.91. Same winner, different rule. The vote would still win if the ORM had fallen in love with a fluent 42.
Interactive · Same six slips
Does the judge change the winner?
Vote fails when the model has a systematic bias — six wrong chains that all say 28. Best-of-N fails when the ORM likes style more than truth. A later chapter will call that reward hacking. Compute: both methods cost \(O(N)\) full traces.
An ORM is a single number on the finished answer. A PRM (Lightman et al. 2023, PRM800K) scores each step. Take a chain that goes wrong on purpose:
How do you turn three scores into one rank? Common aggregators:
| Aggregator | On (0.95, 0.40, 0.70) | What it punishes |
|---|---|---|
| Mean | 0.683 | Soft on one bad step |
| Product | 0.266 | Any weak step (Lightman’s default) |
| Min | 0.40 | The worst step only |
The product is harsh, which is the point. A chain that is locally fluent after a bad East should not beat a shorter honest chain. Last-step-only is another option: it behaves more like an ORM.
Vote and best-of-N generate whole traces, then pick. Beam search interleaves proposal and verify. Notation here follows the search-and-learn convention:
each round, every survivor writes M next steps. Score all N·M, keep the best N, repeat.
On the page we use \(N = 2\), \(M = 2\), so 4 candidates per layer, for 3 layers of the harbor puzzle (East, West, total). Cost is \(O(L \cdot N \cdot M)\) step-generations, not \(O(N)\) full traces. Harder problems often prefer beams; easy ones prefer best-of-N. That crossover is Snell’s main empirical point.
Tree-of-Thought is the same idea with a more general tree and a thought-level scorer. We will not build it here. The verifier you pick matters more than the tree shape.
A cheaper trick: do not sample a new trace. Append a token that means keep thinking. The s1 paper (Muennighoff et al. 2025) does this with “Wait”. The model, already trained to write long traces, continues instead of closing the answer.
On the harbor puzzle a first draft might stop after “East is 8”. Forcing one more beat can get “West is 16. Total 38.” You are buying length, not diversity. It fails when the model has already locked the wrong total, and it does nothing for a model that was never trained to use extra tokens.
Verifiers do double duty later. The same checker that picks among samples at test time can be the reward in RL. Chapter 10 calls that RL with verifiable rewards.
“R1 uses a PRM at inference.” The R1 paper tried PRMs and MCTS and abandoned them. Do not write that o1-style verification into R1.
Mean-pooling a PRM and calling it Lightman. The paper’s main aggregator is the product. Mean, min, and last-step all rank differently.
Beam width defined three ways. Say \(N\) survivors and \(M\) children. Then each layer scores exactly \(N \cdot M\) candidates. That is 4 when \(N = M = 2\).
Voting a biased model. Six copies of the same slip are not six independent thoughts. Temperature near 0 makes this worse.
“Test-time FLOPs beat training FLOPs on one query.” Not as a blanket claim. A long beam is expensive. It is not a pre-training run.
38, with 4 votes.
The ORM can give its highest score to a fluent wrong total. The vote only counts the parsed answer.
The product, 0.266. Min is 0.40. Mean is 0.683.
4.
Length. It continues one trace. It does not draw a new one.
"""Test-time search on the harbor crate puzzle.
Six sampled finals, plus one process-scored chain. Every number is the
one printed on the page.
"""
from statistics import mean
# Six completions of the harbor puzzle. 38 is correct.
# The wrong ones are typical slips: dropping West, or adding instead of subtracting.
SAMPLES = [38, 38, 28, 38, 42, 38]
# Outcome-reward scores for the same six (an ORM that likes confident totals).
ORM_SCORES = [0.91, 0.84, 0.62, 0.88, 0.71, 0.55]
def majority(values):
"""Self-consistency: pick the answer that appears most often."""
counts = {v: values.count(v) for v in set(values)}
return max(counts, key=lambda v: (counts[v], -v)), counts
def best_of_n(values, scores):
"""Best-of-N: pick the sample with the highest outcome score."""
i = max(range(len(scores)), key=lambda k: scores[k])
return values[i], scores[i]
# A chain that goes wrong at step 2. The PRM should catch it.
# Step 1 is right (North = 14). Step 2 adds 6 instead of subtracting.
# Step 3 doubles the wrong East. The final is 70, not 38.
PRM_STEPS = (0.95, 0.40, 0.70)
def prm_mean(steps=PRM_STEPS):
return mean(steps)
def prm_product(steps=PRM_STEPS):
p = 1.0
for s in steps:
p *= s
return p
def prm_min(steps=PRM_STEPS):
return min(steps)
# Beam search over reasoning steps. Each survivor expands into M children.
# We keep the N highest-scoring of those N*M candidates.
BEAM_N = 2 # survivors kept at each layer
BEAM_M = 2 # children per survivor
BEAM_LAYERS = 3
def candidates_per_layer(n=BEAM_N, m=BEAM_M):
return n * m
if __name__ == "__main__":
winner, counts = majority(SAMPLES)
assert winner == 38 and counts[38] == 4
pick, score = best_of_n(SAMPLES, ORM_SCORES)
assert pick == 38 and score == 0.91
assert round(prm_mean(), 3) == 0.683
assert round(prm_product(), 3) == 0.266
assert prm_min() == 0.40
assert candidates_per_layer() == 4
print("search methods ok")