Generator and verifier: the split that makes search possible

Search over reasoning needs two things that a plain decoder does not separate: a generator that proposes continuations and a verifier that ranks them. The generator is the policy π(y | x); the verifier is a learned scorer r(x, y) → R — usually the same base model with a scalar head, trained to predict whether a solution (or a step) is correct.

The split matters because verification is easier than generation. Checking that a proposed algebraic step follows from the previous one is a shallower task than inventing the whole derivation, so a verifier the same size as the generator is typically more reliable at its job than the generator is at its own. Search exploits that asymmetry: it converts cheap, high-variance proposals into a decision made by the more reliable model. Everything that follows — Best-of-N, beam search, MCTS — is a different schedule for how many proposals to draw, at what granularity, and how aggressively to prune on the verifier’s opinion.

Advertisement

Best-of-N and the coverage ceiling

Best-of-N is the minimal search: draw N independent complete solutions, score each with an outcome reward model, return argmax_i r(x, y_i). Two distinct quantities govern how well it does. Coverage (equivalently pass@N) is the chance the pool contains at least one correct solution:

coverage(N) = 1 - (1 - p)^N        p = per-sample accuracy

p = 0.15:  N=1  → 0.150    N=8  → 0.728
           N=32 → 0.994    N=128 → 1.000

Coverage saturates fast — that is the good news and the trap. Realized Best-of-N accuracy is coverage multiplied by the verifier’s ability to actually pick the correct member out of the pool, and that second factor gets harder as N grows, because a bigger pool contains more plausible-looking wrong answers for the scorer to be fooled by. The gap between the pass@N curve and the Best-of-N curve is a direct read-out of verifier quality, and past a few dozen samples it is almost the only thing that matters.

Advertisement

Why flat sampling burns tokens on doomed prefixes

Best-of-N has a structural inefficiency: it only learns anything after a solution is complete. Model a solution as S sequential steps, each correct with probability q and independent. Then p = q^S, and the failure is usually concentrated early:

q = 0.80, S = 8   →   p = 0.80^8 = 0.168
P(first error at step k) = 0.8^(k-1) · 0.2
  k=1: 0.200   k=2: 0.160   k=3: 0.128   k=4: 0.102

Over half of all failures are already determined by step 4, yet flat Best-of-N pays the full eight-step generation cost on every one of them: at 64 tokens a step, a sample that died at step 1 still costs 512 tokens before anyone notices. The exponential q^S is what makes long reasoning chains brittle, and no amount of N repairs it cheaply — you re-roll the entire eight-step product instead of the one step that broke.

Tree search over reasoning steps

The fix is to make the reasoning step the unit of search rather than the whole solution. Treat the partial solution as a node, a candidate next step as an edge, and run a beam. With beam width W and branching factor K, each round samples W × K candidate next steps, scores them with a step-level verifier, and keeps the top W prefixes.

This changes the arithmetic in a fundamental way. The chance that a given beam has at least one correct child is 1 - (1 - q)^K; at q = 0.8, K = 4 that is 0.9984. If the scorer can reliably identify it, the per-step survival probability rises from 0.8 to near 1, and the end-to-end product 0.9984^8 ≈ 0.987 instead of 0.168. Search has converted an exponential decay into a per-step repair. The width W > 1 exists to survive scoring mistakes: it keeps a runner-up alive so one bad ranking does not end the search.

Process supervision vs outcome supervision

The step-level scorer that makes tree search work is a process reward model (PRM), trained on per-step correctness labels. An outcome reward model (ORM) sees only the final answer and one bit of feedback. The distinction is not cosmetic — it decides which searches are even possible.

An ORM gives you a terminal signal, so it can rank complete solutions and nothing else; it is compatible with Best-of-N and useless for pruning at step 3. A PRM gives you a dense signal, which is exactly what beam search and rollout methods consume. Process supervision also removes a pathology of outcome labels: a chain that reaches the right answer through a wrong intermediate step gets full credit from an ORM, teaching the scorer to reward luck. Empirically, process-supervised verifiers beat outcome-supervised ones on hard math benchmarks at equal search budget. The cost is labels, which is why PRMs are often bootstrapped automatically: roll each prefix out many times and label the step by its continuations’ success rate.

MCTS-style rollouts and the exploration term

Beam search is greedy about the verifier’s current opinion. MCTS-style search adds a principled way to revisit that opinion: from the root, repeatedly descend by a selection rule, expand a leaf, estimate its value by rollout or by a value model, and back up the result along the path. The standard selection rule is PUCT:

a* = argmax_a [ Q(s,a) + c · P(s,a) · √N(s) / (1 + N(s,a)) ]

Q(s,a) = mean backed-up value of child a
P(s,a) = policy prior = π(a | s)  (the LM’s own token probability)
N(s), N(s,a) = visit counts;  c = exploration constant

The first term exploits, the second explores; the √N(s) numerator keeps under-visited siblings attractive and the visit count in the denominator decays that pull as evidence accumulates. Because Q is an average over rollouts rather than a single verifier call, MCTS tolerates a noisy scorer far better than beam search — at the price of many more forward passes per node.