A language model that samples one chain of thought and commits to it is doing the cheapest possible thing with its inference budget. Search scaling is the alternative: spend that budget generating many partial or complete reasoning paths, score them with a verifier, and let the scores decide where to spend the next token. The crucial ingredient is not the sampling — it is the scorer. Given a signal that separates good reasoning from bad, you can turn compute into accuracy without touching a weight, right up until the verifier runs out of discrimination. This article covers verifier-guided search specifically: Best-of-N against a reward model, tree search over reasoning steps, process versus outcome supervision, how to split a fixed token budget, and why a mediocre verifier makes search actively harmful. Unverified majority vote is a different mechanism and a different article.
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.
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.000Coverage 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.
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.102Over 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 constantThe 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.
Allocating a fixed token budget: a worked example
Budgets are what actually constrain deployment, so allocate one. Take B = 16,384 generated tokens for a single question, a solution of S = 8 steps at 64 tokens each (512 tokens per full solution), and q = 0.8 per-step accuracy.
A) Best-of-N, flat: N = 16384 / 512 = 32 samples
coverage = 1 - (1-0.168)^32 = 0.997
realized = 0.997 × (ORM top-1 hit rate, ~0.60) ≈ 0.60
B) Beam search, stepwise: W = 8, K = 4
per step: W·K = 32 candidates × 64 tok = 2,048 tok
total: 2,048 × 8 steps = 16,384 tok (same budget)
per-step survival with a good PRM → end-to-end ≈ 0.85-0.95Same tokens, very different outcomes, because option B spends its budget where the uncertainty is. Two costs the arithmetic hides: the verifier’s own forward passes (256 PRM calls here), and the fact that B’s 32 candidates per step share a prefix, so a shared KV cache makes them much cheaper in wall-clock than 32 independent runs.
Depth vs breadth, and search vs parameters
Given more budget, you can go wider (more candidates per step, larger N) or deeper (more refinement rounds, longer rollouts, sequential revision). The right split depends on problem difficulty. On easy problems the first draft is nearly right, so sequential depth (revise, check, revise) pays; on hard problems the first draft is on the wrong track entirely and breadth pays, because you need a different starting idea rather than a polished wrong one.
The larger question is whether to spend the budget at inference at all rather than on parameters. Roughly: for questions within reach of the base model, a few thousand extra inference tokens can beat a model an order of magnitude larger — a very good deal for a CPU-hosted SLM that cannot fit the larger model anyway. For questions the base model essentially never solves, coverage is near zero and search has nothing to select from. Search amplifies capability; it does not create it.
The verifier is the ceiling, and search finds its holes
Search applies optimization pressure against the verifier, so any gap between what it scores and what is correct is a gap search will exploit. This is Goodhart’s law with a compute knob. Best-of-N pulls the effective policy off the base distribution by a measurable amount:
KL(BoN ‖ base) = log N - (N-1)/N nats
N=8 → 1.95 N=32 → 2.50 N=128 → 4.85
gold reward (empirical, d = √KL): R(d) ≈ d(α - βd)That quadratic peaks and then falls: past some N, the proxy score keeps climbing while true accuracy declines. Practically this shows up as confidently formatted nonsense — solutions hitting every surface feature the reward model likes. Mitigations: cap N at the observed peak, ensemble two verifiers, and add a hard ground-truth check wherever one exists (unit tests, a symbolic solver, a proof checker). On CPU, budget honestly too: search multiplies latency, and a large accuracy-per-token win is worthless if the answer arrives in ninety seconds.
1 - (1-p)^N, which saturates within a few dozen samples, and selection accuracy, which does not improve with N and quietly becomes the binding constraint. Flat Best-of-N wastes budget re-rolling the entire q^S product; stepwise beam or MCTS search with a process reward model spends the same tokens where the uncertainty is, converting an exponential decay into a per-step repair. Process supervision is what makes that possible — an outcome model can only rank finished solutions. Allocate breadth to hard problems and depth to easy ones, remember that search amplifies capability rather than creating it, and watch the verifier: KL = log N - (N-1)/N grows with search pressure, and past the peak of that curve you are optimizing the scorer’s blind spots instead of the answer.