REASONING FROM SCRATCH · CHAPTER 02

Test-time search
& verifiers

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.

~20 min read1 interactiveTested Python

What you'll learn

  • The split between a proposal (the model) and a verifier (the judge)
  • Self-consistency as majority vote, and when the vote is fooled
  • Best-of-N with an outcome reward model versus a process reward model
  • Beam search over steps, and budget forcing as a cheap “keep going”

Before you start

One clerk, six slips

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.

Who proposes, who grades

Proposal

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

MANIM Test-time search: spend decode compute on many slips.

Verifier

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.

Count the answers, or score them

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:

Sample383828384238
ORM0.910.840.620.880.710.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.

Grade the steps, not only the last line

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:

  1. North = 14. Score 0.95 — true.
  2. East = \(14 + 6 = 20\). Score 0.40 — the slip. We should have subtracted.
  3. West = \(2 \times 20 = 40\). Score 0.70 — the doubling is locally fine, the input is not.

How do you turn three scores into one rank? Common aggregators:

AggregatorOn (0.95, 0.40, 0.70)What it punishes
Mean0.683Soft on one bad step
Product0.266Any weak step (Lightman’s default)
Min0.40The 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.

Expand, score, keep a few

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.

Just say “wait”

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.

Mistakes learners make

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

What to remember

  • Proposal writes candidates. A verifier votes, scores, or prunes.
  • Six harbor samples: vote is 4–1–1 for 38. Best-of-N also picks 38 at ORM 0.91.
  • A PRM on (0.95, 0.40, 0.70) has mean 0.683, product 0.266, min 0.40.
  • Beam: \(N\) survivors × \(M\) children. Budget forcing appends “Wait” instead of resampling.

Check yourself

1. The six totals are 38, 38, 28, 38, 42, 38. What does majority vote return?

38, with 4 votes.

2. Why might best-of-N disagree with the vote?

The ORM can give its highest score to a fluent wrong total. The vote only counts the parsed answer.

3. A PRM scores (0.95, 0.40, 0.70). Which aggregator is harshest?

The product, 0.266. Min is 0.40. Mean is 0.683.

4. With \(N = 2\) and \(M = 2\), how many candidates are scored at one layer?

4.

5. What does budget forcing change, diversity or length?

Length. It continues one trace. It does not draw a new one.

The code

search_methods.pyvote, best-of-N, PRM aggregators, beam width
"""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")

Go to the source

Keep going