Best-of-n sampling: Definition and Examples

Best-of-n sampling generates $n$ independent responses to a prompt and keeps the single response that a reward model or verifier rates highest. It improves output quality at inference time without changing the model's weights, and it is often used as a strong, simple baseline for RLHF.

How it works

Sample $y_{1}, \dots, y_{n} \sim π_{ref} (\cdot ∣ x)$ , score each with $r (x, y_{i})$ , and return $ar g max_{i} r (x, y_{i})$ . The selected outputs can also be used as fine-tuning data, which is sometimes called rejection-sampling fine-tuning or expert iteration.

How far does it move the distribution?

Best-of-n defines a new policy, and its distance from the base model has a well-known formula:

KL (π_{BoN} ∥ π_{ref}) \approx lo g n - \frac{n - 1}{n}

where $n$ is the number of samples. Beirami et al. (2024) showed this widely used expression is an upper bound rather than an exact value in general, but it remains a handy guide. KL grows only logarithmically in $n$ , so best-of-n is a gentle optimiser.

Worked example

With $n = 4$ the KL is at most $lo g 4 - 0.75 \approx 0.64$ nats; with $n = 16$ it is about $2.77 - 0.94 \approx 1.84$ nats. Quadrupling compute buys less than three times the KL. On a verifiable task where the model is right 20 percent of the time, the chance that at least one of 8 samples is correct is $1 - 0. 8^{8} \approx 0.83$ , the same quantity as pass@k. A perfect verifier would turn that into 83 percent accuracy; a learned reward model will pick a wrong answer some of the time.

Limits

Inference cost scales linearly with $n$ .
Selection exploits reward-model errors: Gao et al. (2022) found that gold-standard quality under best-of-n rises and then falls as $n$ grows, a clean demonstration of reward overoptimisation.
It cannot produce anything the base model would not already sample.

Why it matters

Best-of-n is the cleanest way to measure how much a reward model or verifier is worth before investing in RL, and its log-n KL formula gives a common axis for comparing it with RL methods under the KL penalty. For evals, it is a reminder that reported scores should state how many samples and what selection rule were used, since best-of-16 and single-sample numbers are not comparable.

Sources

Reiichiro Nakano, Jacob Hilton, Suchir Balaji, et al.. WebGPT: Browser-assisted question-answering with human feedback, 2021. arxiv.org
Leo Gao, John Schulman, Jacob Hilton. Scaling Laws for Reward Model Overoptimization, 2022. arxiv.org
Ahmad Beirami, Alekh Agarwal, Jonathan Berant, et al.. Theoretical guarantees on the best-of-n alignment policy, 2024. arxiv.org