Best-of-N Sampling (and RFT / ReST)

Definition

Best-of-N (BoN) is the simplest way to spend compute on quality: sample $n$ completions from the policy, score all with a reward model or verifier, return the top-1. No training. It is a strong baseline and the inference-time member of a family that harvests the asymmetry that recognizing a good answer is easier than generating one. RFT and ReST amortize that harvest back into the weights so you stop paying $n\times$ at inference.

Key math

BoN’s induced distance from the reference is analytic, letting you place it on the same $d=\sqrt{\mathrm{KL}}$ axis as RL (Gao et al.):
${\mathrm{KL}}_{\text{BoN}}\approx \log n-\frac{n-1}{n}.$
Its gold-reward curve $R^{\text{BoN}}(d)=d(\alpha -\beta d)$ often dominates RL per unit KL at small-to-moderate budgets. Two structural limits: BoN pays $n\times$ inference forever, and it is support-bounded — it only re-weights toward the top of the existing sampling distribution, so it can never reach a sequence the base policy essentially never produces (unlike PPO, which moves the parameters). Doubling $n$ buys ever less distance ($\log n$ growth).

Amortizing BoN into weights:

• RFT (rejection-sampling fine-tuning) — Yuan et al., arXiv:2308.01825: sample many completions, filter to correct/verified ones (dedupe to distinct reasoning paths), SFT on them. Driver of quality is the number of distinct paths (diversity); combining samples from multiple models pushed LLaMA-7B 35.9% → 49.3% on GSM8K. Helps less-performant models most.
• ReST / ReST-EM — Singh et al., “Beyond Human Data,” arXiv:2312.06585: iterated RFT framed as EM — E/Grow (sample + filter by binary reward) then M/Improve (SFT the original base model, not the previous iterate — curbs drift). Beats SFT on human data; but overfits after a couple of iterations (few-round procedure, not an indefinite loop). Predecessor ReST (Gulcehre et al., arXiv:2308.08998) used offline RL in Improve.
• Expert iteration is the umbrella: (E) expert improvement via search/sampling+filter, (M) policy distillation via SFT. Havrilla et al. (arXiv:2403.04642) found plain expert iteration nearly as sample-efficient as PPO for reasoning.

Why it matters

BoN/RFT/ReST get much of RL’s benefit with none of its machinery — no value head, no adversarial inner loop, just sample + filter + SFT — so they win when the reward is verifiable/cheap, you want simplicity, or RL infra is limited. The trade: they are support-bounded (can’t exceed base-policy reach) and RFT/ReST overfit after few iterations. This is the bridge between offline SFT and full RLVR: RFT/ReST already use verifiable rewards in the filter step; RLVR is that signal run through online RL instead. PRM reranking on BoN candidates is where process supervision historically shone (“Let’s Verify”). Also the amortization target for DPO models scoring with their own implicit reward.

Taught in

• 08-scaling-rlhf-and-alternatives — §7 BoN, RFT, ReST-EM, expert iteration; the generate-vs-judge asymmetry and when they beat RL.
• 10-frontier-and-infra — rejection sampling in the multi-stage frontier pipeline.

See also

• reward-overoptimization — the $d=\sqrt{\mathrm{KL}}$ curve BoN sits on
• rlvr — verifiable rewards as the BoN/RFT filter
• process-reward-model — PRM as a BoN reranker
• reward-model / ppo — the RL alternative it competes with
• chain-of-thought-rl — reasoning traces harvested by RFT/ReST
• rl-for-llms