Best-of-N Sampling

Best-of-N (BoN) sampling generates N candidate responses to the same prompt and selects one using a verifier or reward model — "a verifier selects the best out of a set of LLM-generated responses" (Chow et al.). It is a decoding-time technique: no retraining, no weight access required, just more inference compute per task. The core trade-off: success rates climb with N only as far as the selector can be trusted — against an imperfect reward model, true quality first rises and then falls as N grows (Khalaf et al.).

Problem

A single attempt understates what a model can do across attempts. The gap is large and old: OpenAI's Codex paper (July 2021) reported that its model solved 28.8% of HumanEval problems with one sample but 70.2% with 100 samples per problem (Chen et al.). "Large Language Monkeys" (Brown et al., July 2024) turned this into an inference-time scaling law: coverage — the fraction of problems solved by any generated sample — grows with sample count over four orders of magnitude, often log-linearly, modeled by an exponentiated power law (arXiv 2407.21787). Their headline agentic result: on SWE-bench Lite, DeepSeek-Coder-V2-Instruct went from 15.9% of issues resolved with one sample to 56% with 250 samples, beating the then single-attempt state of the art of 43% held by stronger frontier models (Brown et al.).

For an agent operator the problem BoN attacks is converting that latent coverage into one deliverable answer. When an oracle exists (unit tests, a compiler), conversion is mechanical. When it does not, you need a selector — and the selector becomes the binding constraint.

Best-of-N vs pass@k: read the labels

The two headline numbers above — 70.2% and 56% — are not best-of-N results. Both are coverage, i.e. pass-at-k with an oracle verifier (test execution) doing the selection. The Codex paper states this explicitly, and Brown et al. report that in domains without automatic verifiers, the practical selection methods they tested — majority voting and reward models — "plateau beyond several hundred samples and fail to fully scale with the sample budget" (arXiv 2407.21787).

The practitioner consequence: a leaderboard or paper number is only a BoN number if the selection was done by a deployable verifier, not by the benchmark's own ground truth. Quoting oracle pass@k as "best-of-N" inflates what a production harness will achieve, because production rarely has the oracle. When evaluating a claim, ask what selected the winning sample and whether that selector exists at inference time.

How to apply

1. Classify your verifier before choosing N. Oracle-grade signal (test suite, type checker, execution success) supports large N — you are on the coverage curve, where gains follow the power law (Brown et al.). A learned reward model or LLM judge is a proxy, and proxies get hacked (below): keep N modest and validated.
2. Sample for diversity. BoN presumes the N candidates differ; sample at nonzero temperature rather than replaying one greedy decode.
3. Tune N against true quality, not proxy score. Under an imperfect reward model, measured proxy reward keeps rising while true performance peaks and declines — the inverted-U. Khalaf et al. prove this is "an inevitable property of a broad class of inference-time mechanisms," including BoN and Best-of-Poisson, and provide HedgeTune, an algorithm for finding the optimal inference-time parameter before the hacking threshold (arXiv 2506.19248).
4. Regularize selection if you must use a proxy. MBR-BoN adds a Minimum Bayes Risk term to the reward objective, which acts as a proximity regularizer over the sample distribution; it outperforms both vanilla BoN and MBR decoding on AlpacaFarm and hh-rlhf in most — not all — settings (Jinnai et al., NAACL 2025).
5. If you own the weights, fine-tune for BoN. Inference-aware fine-tuning optimizes the model directly for performance under BoN selection: on Gemma 2B it lifted Bo32 on Hendrycks MATH from 26.8% to 30.8% and pass@32 from 60.0% to 67.0%, and pass@16 on HumanEval from 61.6% to 67.1% (Chow et al., December 2024) — small-model results, illustrative of the mechanism rather than frontier-scale.
6. Price it as a cheap-model amplifier. Under mid-2024 API pricing, Brown et al. found that five samples from the cheaper DeepSeek-V2-Coder solved more SWE-bench Lite issues at lower cost than one sample from GPT-4o or Claude 3.5 Sonnet (Stanford Scaling Intelligence Lab). The specific models and prices are superseded; the durable mechanism is that when a verifier exists, a cheap model times N can dominate an expensive model times one on price-performance.

When to use / When not to

Use it when:

• an automatic, execution-grade verifier exists for the task — tests, compilation, structured-output validation — so selection approaches oracle quality (Brown et al.);
• you can trade dollars and latency for reliability on hard, high-value tasks where the single-attempt rate is unacceptable;
• a cheaper model plus verification beats a frontier model single-shot on your cost curve (validate on current pricing — the published case study is from 2024, per the project page).

Do not use it when:

• your only selector is a learned reward model and you have no way to measure true quality at increasing N — you cannot see the inverted-U you are climbing (Khalaf et al.);
• the loop is latency-bound and interactive: N candidates cost roughly N times the tokens of one, and even though candidates can be generated in parallel, wall-clock still grows under concurrency caps or rate limits and the selector adds its own latency on top;
• verifying a candidate is as hard as producing it — then the verifier consumes the budget the sampling was supposed to leverage;
• selection already plateaued: past several hundred samples, non-oracle selectors stop converting extra coverage into extra wins (Brown et al.).

Trade-offs and failure modes

Linear cost in N. Tokens and spend scale roughly linearly with the candidate count. Wall-clock does not have to: candidates can be generated in parallel, so latency depends on available concurrency and rate limits — it approaches N-times only when generation is sequential or parallelism is capped, and the selector pass adds its own latency either way. The technique only pays off where the success-rate delta is worth an N-times inference bill.

Selection plateau without an oracle. Coverage keeps growing over four orders of magnitude, but majority voting and reward-model selection stall beyond several hundred samples — the gap between coverage and deliverable accuracy is the open problem, not the sampling (Brown et al.).

Mitigations are partial. MBR-BoN wins in most, not all, evaluated settings, and its preference-tuning evidence is DPO-only (Jinnai et al.); inference-aware fine-tuning requires training access and is demonstrated at 2B scale (Chow et al.).

Benchmark misreading. The recurring failure in the wild is treating oracle pass@k as achievable BoN performance — see the labeling section above. This matters directly when reading agentic leaderboards such as swe-bench and terminal-bench.

Variants and related

• LLM verifiers as the selector — the current frontier. "LLM-as-a-Verifier" (Kwok et al., posted 2026-07-06) proposes a general-purpose probabilistic verification framework with a ranking algorithm for selecting the best candidate, self-reporting 86.5% on Terminal-Bench V2 and 78.2% on SWE-Bench Verified as of 2026-07-15 (arXiv 2607.05391). This is a recent, non-peer-reviewed preprint with self-reported numbers — a direction to watch, not adjudicated state of the art. Mechanically it makes the selector an llm-as-judge instance, inheriting judge failure modes; agent-as-a-judge extends the same idea to judging full agent trajectories.
• Best-of-Poisson — draws the candidate count from a Poisson distribution instead of fixing N; analyzed alongside BoN in the reward-hacking results (Khalaf et al.).
• MBR-BoN — regularized selection, above (Jinnai et al.).
• reward-hacking — the underlying dynamic, which BoN triggers at inference time rather than during training.
• evaluator-optimizer — the sequential sibling: one candidate iteratively refined against evaluator feedback, versus BoN's N independent parallel draws.
• pass-at-k — the oracle-verified ceiling that BoN selection tries, and so far fails, to reach without an oracle.