Spending compute at inference: sampling, Best-of-N and coverage

A trained model's weights are fixed, but how much computation you spend per question is not: you can sample many answers, revise, search, or iterate a recurrent block longer. This lesson sets out the arithmetic of that choice — what repeated sampling buys (coverage), what it does not buy on its own (accuracy), and how the field learned to tell them apart.

Two ways to spend compute after training

Test-time compute comes in two broad shapes.

• Parallel: draw $N$ independent samples and pick one — by a verifier (Best-of-N), by voting (self-consistency), or by an external check such as unit tests.
• Sequential: let one attempt run longer — a longer chain of thought, revisions conditioned on earlier drafts, tree search, or more iterations of a weight-tied block.

Snell et al. (2024) compared these head-to-head on maths problems and found the best mix depends on difficulty: easier problems benefited more from sequential revision, harder ones from a balance of revision and parallel sampling. Allocating compute adaptively per prompt beat a Best-of-N baseline while using about 4× less computation, and in a FLOPs-matched comparison a small model plus test-time compute outperformed a 14× larger model — but only on problems where the small model already had non-trivial success.^[1] That qualifier matters: extra inference cannot conjure a capability the model almost never shows.

Reasoning models fold much of the sequential axis into training itself; see /academy/reasoning-and-rl/reasoning-models. This lesson concentrates on the parallel axis, because its mathematics is clean and its failure mode is instructive.

Coverage: the probability that some sample is right

Suppose a model answers a given problem correctly with probability $p$ per sample, and samples are independent. The probability that at least one of $N$ samples is correct — coverage, or pass@$N$ — is

For small $p$, coverage reaches one half at roughly $N \approx 0.69/p$. A problem the model solves once in a hundred tries is covered more often than not by $N = 69$.

Brown et al. (2024), in "Large Language Monkeys", measured how far this goes in practice. Across tasks and models, coverage kept rising over four orders of magnitude of $N$, often log-linearly, and was well modelled by an exponentiated power law. On SWE-bench Lite, the fraction of GitHub issues solved by DeepSeek-V2-Coder-Instruct rose from 15.9% with one sample to 56% with 250 samples, above the then single-attempt state of the art of 43%.^[2]

Why the curve is log-linear rather than exponential

For a single problem, $1-(1-p)^N$ saturates exponentially fast. A benchmark is a mixture of problems with very different $p$. Averaging exponentials with rates spread across many orders of magnitude produces a curve that climbs steadily in $\log N$: each tenfold increase in samples "unlocks" the next band of harder problems.

Worked example. Take a three-problem benchmark with per-sample success rates $p = 0.5,\ 0.02,\ 0.001$.

Each tenfold step in $N$ adds roughly a quarter to mean coverage, because each problem's steep rise lands in a different decade. That is the shape Brown et al. observed at scale.

Coverage is not accuracy

Coverage counts a problem as solved if any sample is right. A deployed system must commit to one answer. Turning coverage into accuracy needs a selection rule, and every rule has its own ceiling.

• An oracle check. When answers can be verified exactly — unit tests that genuinely specify the task, a proof checker — coverage converts directly to accuracy. This is why repeated sampling shines on code and formal maths.
• A learned verifier. Cobbe et al. (2021) introduced GSM8K and trained a verifier to score candidate solutions, selecting the top-ranked one out of many. They reported that verification gave roughly the same boost as a 30× increase in model size over a fine-tuning baseline.^[3]
• Voting. Wang et al. (2022) sampled diverse chains of thought and took the most common final answer — self-consistency — improving chain-of-thought accuracy on GSM8K by 17.9 percentage points.^[4]

Brown et al. also reported the limit of the non-oracle rules: without an automatic verifier, majority voting and reward-model selection plateaued beyond several hundred samples, while coverage kept climbing.^[2] The gap between the two curves is the subject of the next lesson, /academy/test-time-compute-and-verification/verifiers-and-exploitability.

The NeuroGenesys selection model makes the gap concrete. At $p = 0.10$, a verifier of moderate discrimination, and a 1% rate of wrong answers it scores highly, coverage at $N = 64$ is 0.9988 while Best-of-N accuracy peaks at about 0.70 — and by $N = 8192$, with coverage indistinguishable from 1, accuracy has fallen to about 0.36.^[5]

Three caveats on the coverage curve

Samples are not independent. The formula assumes i.i.d. draws. Real samples from one model at one temperature share failure modes, so measured pass@$N$ falls below $1-(1-p)^N$. The lab's earlier draft notes one instance: an i.i.d. model implied coverage at $N=4$ of 0.997 for a Gemini GSM8K setting where the reported pass@4 was about 0.90.^[6] Treat the i.i.d. curve as an upper bound.

Coverage depends on what the base model can already reach. Yue et al. (2025) compared reinforcement-learned reasoning models with their base models across maths, code and visual reasoning. The RL-trained models won at pass@1, but the base models matched or exceeded them at large $k$; coverage analyses suggested RL mostly concentrated probability on reasoning paths already in the base model's distribution rather than adding new ones.^[7] This is a contested reading — large-$k$ pass rates on small benchmarks can be inflated by lucky guesses — but it shows why a pass@1 gain and a coverage gain are different claims. The trade-off is discussed further in /academy/reasoning-and-rl/what-rl-buys.

Compute must be counted honestly. "Model A with 64 samples beats model B" means little unless B was offered the same FLOPs. Snell et al.'s 14× result is meaningful precisely because it was FLOPs-matched.^[1]

Sequential depth as a separate dial

Parallel sampling is not the only way to spend inference. A weight-tied, recurrent-depth network applies the same block repeatedly, so "thinking longer" is literally more iterations. In the lab's experiments on graph-reachability tasks, such a network matched a matched-compute feedforward network in-distribution with one eighth of the parameters, beat it out of distribution by $+0.36 \pm 0.13$ over ten seeds, and extrapolated to roughly 8× the trained problem size. The same work found the mechanism bounded: a plain residual update diverged on unbounded regression and "overthought" on parity, while a gated, contractive update fixed both.^[8] The general lesson carries over to sampling: every test-time axis has a regime where more compute helps and a regime where it does not, and the boundary is set by a specific mechanism.

Key takeaways

• Coverage $1-(1-p)^N$ rises steadily with samples; across a benchmark of mixed difficulty it often climbs log-linearly in $N$.
• Coverage is not accuracy. Converting one into the other needs a selector — oracle check, learned verifier, or vote — and the selector sets the ceiling.
• Repeated sampling is strongest where exact verification exists (tests, proofs) and plateaus elsewhere.
• Correlated samples make real coverage lower than the i.i.d. formula; compare methods at matched compute.
• Sequential depth is a second dial with its own stability conditions.

Sources