Best-of-N Sampling: The Simplest Test-Time Scaling There Is

Generate N answers, keep the best one. No training, no search tree, no new component except the thing that decides what “best” means — and that thing turns out to be the entire problem.

The shape of the technique

Sample the same prompt N times at non-zero temperature, then select. The selector is one of three kinds and the distinction dominates everything else: a sound verifier (a test suite, a compiler, a solver, a schema), a learned verifier (a reward model that scores candidates), or a consistency vote (take the answer that appears most often, which is what self-consistency does).

The technique’s appeal is operational rather than intellectual. The N calls are independent, so they run in parallel: N times the tokens, roughly one call’s worth of wall-clock time. Compared with a reasoning model, which buys quality with serial latency, best-of-N buys it with money and leaves the clock alone. For a batch job that is a straight trade in your favour.

The coverage arithmetic

Assume for a moment that each sample independently has probability p of being correct. The chance that at least one of N samples is correct — the quantity the literature calls coverage, or pass@N — is:

coverage(N) = 1 - (1 - p)^N

p = 0.30                     p = 0.60
  N=1    0.300                 N=1    0.600
  N=2    0.510                 N=2    0.840
  N=4    0.760                 N=4    0.974
  N=8    0.942                 N=8    0.999
  N=16   0.997                 N=16   1.000

Each doubling of N buys less than the last. Going 1 -> 2 at p=0.3
adds 21 points; going 8 -> 16 adds 5.

Two things fall out immediately. Diminishing returns are structural, not a property of any model — the curve is an exponential approach to 1 and always was. And the technique is worth most when p is low but not tiny: at p = 0.9 there is almost nothing to recover, and at p = 0.01 you need hundreds of samples before coverage becomes interesting.

Brown and colleagues’ 2024 paper Large Language Monkeys: Scaling Inference Compute with Repeated Sampling examined this empirically across models and tasks and reported that coverage kept rising over several orders of magnitude of N. Their most-quoted figure is on SWE-bench Lite, where they reported an open-weights coding model solving 15.9% of issues with a single sample and 56% when allowed 250 samples — an enormous gap, and the paper is careful to note that this is coverage, i.e. what is achievable if you can identify the right sample.

Coverage is not accuracy

That caveat is the whole practical story. Coverage is the ceiling. What you actually ship is coverage multiplied by your ability to pick, and the two can be very far apart.

On SWE-bench-style tasks you have a sound verifier — run the tests — and the gap narrows sharply. On a maths problem with a numeric answer, majority voting is a decent picker because wrong answers scatter and right ones coincide. On an open-ended writing task there is no picker at all, and 250 samples of which one is excellent leaves you exactly where you started, having paid 250 times.

So before increasing N, answer the picker question. If your selector is a learned reward model, its accuracy caps yours; verifiers at inference time is about making that component good enough to be worth the samples you are feeding it.

Why real curves flatten sooner

The independence assumption in the formula is false, and its falsity is systematic. Samples from one model on one prompt at moderate temperature are strongly correlated — they share the same misunderstanding of the question, the same missing fact, the same wrong approach. When a model is wrong, it is usually wrong in the same way N times, which is why measured coverage curves bend below the exponential.

The second effect is more dangerous because it points downward rather than merely flattening. Gao, Schulman and Hilton’s 2023 study Scaling Laws for Reward Model Overoptimization characterised what happens when you select hard against an imperfect reward model: the proxy score keeps rising while the true objective peaks and then declines. In best-of-N terms, a large N is a strong optimisation against your verifier, and past some point you are selecting the candidate that best exploits the verifier’s blind spots rather than the best candidate.

Practical reading: with a sound verifier, push N as far as the budget allows. With a learned one, be suspicious of large N, and check whether quality on a held-out human-judged sample still tracks the reward score as N grows.

Temperature is the other lever people get wrong, and it trades against N directly. Too low and the samples are near-copies, so coverage barely moves and you have paid N times for one answer. Too high and per-sample correctness p falls, which pushes the whole curve down — you have more diversity across worse candidates. The usable band is task-dependent and worth finding empirically: sweep temperature at fixed N and read coverage, rather than assuming the value that worked for single-sample generation is right here. It usually is not, because single-sample generation was tuned for the best expected answer and this is tuned for the best maximum.

Using it well

• Diversify the samples deliberately. Raising temperature is the crude lever. Varying the prompt framing, or sampling from two different models, breaks correlation far more effectively and moves you closer to the independence the formula assumes.
• Stop early when you can. With a sound verifier you do not need all N — sample until one passes. Expected cost is 1/p samples rather than N, which at p = 0.5 is two rather than eight.
• Combine with, do not replace, a reasoning model. Best-of-N over reasoning traces is expensive but legitimate; the two techniques address different parts of the problem, one by deliberating and one by re-rolling.
• Report pass@1 as well as pass@N in any evaluation. A benchmark figure quoted at N = 64 with no picker described is a coverage number wearing an accuracy number’s clothes.