Verifier Scaling

The setup: generate many, keep one

Test-time scaling gives a model more than one shot. The generator samples N candidate solutions y_1 … y_N for a prompt (temperature > 0 so they differ), and a selector chooses one to return. Three selectors dominate: majority vote (self-consistency — return the most common final answer), best-of-N with a verifier (return the candidate the verifier scores highest), and weighted combinations. The verifier is a learned scorer V(x, y) → ℝ — often a reward model or a model fine-tuned to predict ‘is this solution correct?’. The question this article answers: how does accuracy grow with N, and what caps it?

Two ceilings: coverage and selection

Every best-of-N system is squeezed between two numbers. Coverage (also called pass@N) is the chance that at least one of the N samples is correct — the best you could possibly do with a perfect selector. If a single sample is correct with probability p, then for independent samples

coverage(N) = pass@N = 1 − (1 − p)^N

which rises fast toward 1. The selection accuracy is what you actually get: the chance the selector picks a correct one. A perfect verifier achieves coverage; a useless verifier (random pick) achieves p. Real verifiers sit in between, and the gap between the coverage curve and the achieved curve is the verifier’s tax.

The best-of-N accuracy curve

Model the verifier as assigning a score to every candidate, correct or not. Best-of-N returns the argmax score. Accuracy is the probability the top-scored candidate is correct, which depends on how well the verifier separates correct from incorrect solutions. With a strong verifier, accuracy tracks the coverage curve and keeps climbing with N. With a weak, noisy verifier, accuracy rises then falls: past some N, the growing pile of wrong candidates eventually contains one that the noisy verifier scores higher than any correct one (an adversarial-sampling effect — the same Goodhart failure as reward over-optimization). So more samples is not always better; the optimal N depends on verifier quality.

A worked example

Take p = 0.3 (30% single-shot). Coverage climbs as:

A perfect verifier would deliver that top row — 94% at N=8. Majority vote lands lower, near the model’s single most-likely answer, and saturates at the model’s inherent consistency (often well under coverage). A good but imperfect verifier might realize, say, 0.30 → 0.48 → 0.63 → 0.74 → 0.80 — beating majority vote by rescuing minority-correct answers, but short of the 0.94 ceiling. The three curves (coverage > verifier-BoN > majority vote) are the whole story.

Why a verifier beats majority vote

Majority vote can only be right if the correct answer is the plurality answer. On hard problems the model is often confidently wrong in a consistent way — the same seductive mistake recurs, and it wins the vote. A verifier is not bound by popularity: it can select a correct solution that appeared only once, as long as it scores it above the wrong ones. This is why verification is generically easier and more powerful than generation for problems where checking is easier than solving (math, code with tests, formal proofs). It is also why majority vote plateaus while a strong verifier keeps benefiting from more samples.

Outcome vs process reward models

Verifiers come in two flavors. An outcome reward model (ORM) scores only the final answer — one label per solution. A process reward model (PRM) scores each reasoning step, giving dense feedback along the chain. A PRM is more expensive to train (needs step-level labels) but is stronger: it catches a solution that reaches the right answer by faulty reasoning, and it can prune bad branches early during search rather than only judging completed solutions. Lightman et al.’s ‘Let’s Verify Step by Step’ found PRMs substantially outperform ORMs at best-of-N on hard math. The PRM step scores are typically aggregated (product or minimum of per-step correctness probabilities) into a single solution score for selection.

Verifier-guided search

Best-of-N verifies completed solutions. A PRM lets you verify as you go, turning selection into search: expand a tree of partial solutions and use the step scores to decide which branches to keep. Beam search over reasoning keeps the top-b partial chains by PRM score at each step. Tree search / MCTS goes further, balancing exploration and exploitation. Guided search spends compute where it matters (promising branches) instead of sampling N full solutions blindly, so it often reaches a target accuracy with fewer generated tokens — the same idea behind reasoning models that ‘think’ along a searched trajectory.

The compute split: samples vs verification

Inference budget is finite, so you must divide it. Generating N samples of length T costs about N·2P·T FLOPs for a P-parameter generator; scoring them with a verifier of size P_v adds roughly N·2P_v·T. A cheap verifier (small ORM) barely adds cost, so N can be large; a full-size PRM run at every step can cost as much as generation itself. The practical questions: is your verifier good enough that more N still helps (or does accuracy roll over)? And at a fixed budget, is it better to draw more samples, or to spend that compute making the verifier bigger/better? Empirically, verifier quality usually buys more than raw sample count once N is moderate.

Weighted selection: the best of both

Majority vote and best-of-N are the endpoints of a spectrum. Verifier-weighted voting sits in between: group the N candidates by their final answer, sum the verifier scores within each group, and return the answer with the largest total score

answer* = argmax_a  Σ_{i : answer(y_i)=a}  V(x, y_i)

This blends the two strengths: like majority vote it pools evidence across many samples that agree (robust to a single lucky-high verifier score on a wrong answer), and like best-of-N it lets a confident verifier override a popular-but-wrong plurality. On math benchmarks, verifier-weighted voting typically edges out both plain majority vote and plain best-of-N, because it is less fooled by verifier noise on any one candidate. Plain best-of-N remains the right choice when answers are free-form (no natural grouping) or checkable outright (unit tests), where a single verified-correct solution is all you need.

Train vs test-time compute

Verifier scaling is one lever in the broader trade between training a bigger model and ‘thinking’ harder at inference. Snell et al. showed that for many problems, a smaller model plus verifier-guided search can match a much larger model’s single-shot accuracy at equal or lower total FLOPs — but the crossover depends on difficulty: easy prompts barely benefit from search, hard ones benefit a lot. So the compute-optimal policy is difficulty-adaptive: spend little test-time compute on easy queries and a lot on hard ones, rather than a fixed N everywhere.

Pitfalls, and the CPU-SLM angle

The failure mode to respect is verifier over-optimization: at large N the generator is effectively adversarial against the verifier, surfacing solutions that exploit its blind spots — so a mediocre verifier makes accuracy peak then decline. Mitigations mirror reward-hacking fixes: better/larger verifiers, ensembling, and capping N. For small models on CPU, verifier scaling is attractive precisely because it trades cheap parallel samples for capability — but a verifier that is itself a full forward pass per candidate can erase the budget, so lightweight ORMs or reusing the generator’s own log-probabilities as a weak verifier are common compromises. Match N and verifier size to how much better verification is than generation on your task. A useful rule of thumb: if checking a solution is far cheaper and more reliable than producing one — code with tests, or math with a known answer format — verifier scaling pays off handsomely; if verification is nearly as hard as generation, best-of-N buys little and a bigger generator is the better spend.