Verifier-Guided Search and Best-of-N
Sampling many candidate solutions is only useful if you can pick the right one, and the gap between what sampling can reach and what selection can find is the central constraint on test-time scaling.
Repeated sampling raises the fraction of SWE-bench Lite issues DeepSeek-Coder-V2-Instruct solves from 15.9 percent with one sample to 56 percent with 250, well past the 43 percent single-sample state of the art at the time (Brown et al., 2024, Large Language Monkeys, arXiv:2407.21787). That is a striking number, and it comes with an equally striking asterisk: it measures coverage, the fraction of problems solved by any sample, which requires an oracle to identify which sample was right.
The distance between coverage and usable accuracy is the whole subject.
Two different quantities
Coverage (pass@k) is a property of the generator. It scales remarkably well: Brown et al. found coverage log-linear in sample count over four orders of magnitude, fitting an exponentiated power law.
Selected accuracy is a property of the generator and the verifier. It scales only as well as the verifier, and this is where the field's results diverge sharply by domain.
Where a formal verifier exists, coverage converts directly. Unit tests, a proof checker, a compiler, a numeric answer key: run every sample, keep what passes. Best-of-N with a perfect verifier is exactly coverage.
Where the verifier is learned, it does not. Brown et al. report that majority voting and reward-model scoring both plateau beyond a few hundred samples, so most of the coverage gain is unrealisable. The bottleneck is not generation.
Verifier designs
Three families, in increasing sophistication.
Majority voting (self-consistency). Sample \(N\) chains, take the most common final answer. Free, requires no training, and works because wrong answers are more diverse than right ones. It caps out early because it cannot distinguish a confidently wrong consensus from a correct one, and it needs answers that are comparable for equality.
Outcome reward models. Train a verifier on (problem, solution, correct?) triples. Cobbe et al. showed on GSM8K that verification scales better with data than a fine-tuning baseline, and reported that 6B verification slightly outperforms a fine-tuned 175B model, "approximately equivalent to a 30x model size increase" (Cobbe et al., 2021, Training Verifiers to Solve Math Word Problems, arXiv:2110.14168). The weakness is credit assignment: a single label for a long solution gives no signal about where it went wrong.
Process reward models. Score each reasoning step. Lightman et al. collected 800,000 step-level human labels for the PRM800K dataset and found process supervision decisively better than outcome supervision, solving 78 percent of a MATH test subset against 72 percent under best-of-N with an outcome-supervised verifier (Lightman et al., 2024, Let's Verify Step by Step, arXiv:2305.20050, ICLR 2024). A PRM also enables search, not just reranking, because it can score partial solutions.
Search beats reranking, at the same budget
Given a step-level verifier, you can spend compute on tree search rather than independent samples: beam search over reasoning steps, or lookahead search that rolls forward before committing.
Snell et al. made the budget-matched comparison and found that the right strategy depends on problem difficulty, with a compute-optimal policy improving efficiency by more than 4x over a best-of-N baseline at the same compute (Snell et al., 2024, arXiv:2408.03314). The pattern is intuitive once stated: on easy problems the model's first attempt is usually nearly right, so sequential revision wins; on hard problems it is qualitatively wrong, so parallel search over diverse attempts wins. A fixed strategy is leaving substantial compute on the table in one of the two regimes.
They also compare test-time compute against pretraining compute directly, and find test-time compute can substitute for a larger model on easy and medium problems, but not on the hardest ones, where capability is missing rather than merely unfound.
When it breaks
Verifier hacking. Best-of-N against a learned verifier is an optimisation against that verifier, and at large \(N\) it finds its errors reliably. This is Goodhart's law with an explicit knob: the larger the sample budget, the harder the search for adversarial inputs to your reward model. Measured accuracy against the verifier keeps rising while true accuracy falls.
Correlated samples. Coverage scaling assumes diverse attempts. Samples from one model at moderate temperature share failure modes, so the log-linear curve flattens where diversity runs out rather than where the model's ability ends. Raising temperature buys diversity at the cost of per-sample quality.
PRM labels are expensive and drift. Human step labels do not scale, and automatic labelling by rollout success is noisy and biased toward steps that appear in successful trajectories for unrelated reasons.
The economics are unforgiving. 250 samples is 250 times the inference cost for one answer, and the coverage curve is log-linear, so each doubling of cost buys a constant increment. Test-time scaling is a way to spend money for accuracy, and whether that is a good trade is a product decision. See inference scaling laws and budgets and test-time compute scaling.
14 flashcards for this concept
Click a card to reveal the answer.