Skip to content
Last Dictionary
Plane
Training & Post-trainingInference & EfficiencyLanguage Models & Transformers

best-of-n sampling

nounAlso: best-of-n, BoN, best-of-n reranking

In plain wordsAsking an AI the same question several times and keeping whichever answer a scoring model or checker rates highest — a simple way to trade extra computing for better answers.

  1. An inference-time method that draws n independent samples from a model for the same prompt and returns the one scored highest by a reward modelreward model, n.: A separate AI model trained to score responses the way people would, so it can stand in for human judges while another model is trained on millions of examples., verifierverifier, n.: A program or AI model that checks whether a proposed answer is correct — by running tests, comparing with a known result or judging the reasoning — so that good answers can be picked or rewarded. or other scoring function. It is the simplest form of test-time computetest-time compute, n.: The computing effort an AI model spends while answering a question, as opposed to while being trained. Letting a model think longer or try many answers can make it markedly smarter. scaling and a strong baseline in alignment research: with a good scorer, quality improves with n, with diminishing returns, while cost grows linearly. Viewed as a policy, best-of-n tilts the base distribution toward high reward with bounded divergence — at most log n − (n−1)/n nats of KL, a widely quoted figure later shown to be an upper bound rather than exact — which makes it a reference point for comparing RL methods. Large n exploits the scorer's errors, producing reward overoptimizationreward overoptimization, n.: What happens when an AI is trained too hard to please an imperfect scoring model: its scores keep climbing while the real quality of its answers stops improving and then gets worse.. Distilling best-of-n outputs back into the model is a form of rejection samplingrejection sampling, n.: Generating many candidate answers and keeping only those that pass a check — a scoring model, a test or a correct final answer — often so the AI can then be trained on its own best work. fine-tuning, and majority voting over answers (self-consistencyself-consistency, n.: Asking an AI the same question many times, letting it reason differently each time, then going with the answer it reaches most often — a vote among its own attempts.) is a scorer-free relative.

    Best-of-16 against the reward model beat our PPO policy, at sixteen times the inference cost.

KL(πBoN ∥ πref)≤log⁡n−n−1n\mathrm{KL}\big(\pi_{\mathrm{BoN}} \,\|\, \pi_{\mathrm{ref}}\big) \le \log n - \frac{n-1}{n}

Origin

Generating several outputs and reranking them is old practice in speech recognition and machine translation (n-best reranking). In language-model alignment, best-of-n against a learned reward model appears in OpenAI's summarization (2020) and WebGPT (2021) work; Leo Gao, John Schulman and Jacob Hilton (2022) used it as a reference optimizer in their study of reward-model overoptimization.

Usage note

Ahmad Beirami and colleagues (2024) proved that the standard KL formula overstates the true divergence. Not to be confused with beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility., which builds a single sequence token by token, or with pass@kpass@k, n.: A score for code-writing AI: the chance that at least one of k attempts at a problem is correct, as checked by actually running tests on the code., which counts a problem solved if any of k samples is correct.

Related

See also
  • rejection samplingrejection sampling, n.: Generating many candidate answers and keeping only those that pass a check — a scoring model, a test or a correct final answer — often so the AI can then be trained on its own best work.
  • reward modelreward model, n.: A separate AI model trained to score responses the way people would, so it can stand in for human judges while another model is trained on millions of examples.
  • verifierverifier, n.: A program or AI model that checks whether a proposed answer is correct — by running tests, comparing with a known result or judging the reasoning — so that good answers can be picked or rewarded.
  • test-time computetest-time compute, n.: The computing effort an AI model spends while answering a question, as opposed to while being trained. Letting a model think longer or try many answers can make it markedly smarter.
  • self-consistencyself-consistency, n.: Asking an AI the same question many times, letting it reason differently each time, then going with the answer it reaches most often — a vote among its own attempts.
  • reward overoptimizationreward overoptimization, n.: What happens when an AI is trained too hard to please an imperfect scoring model: its scores keep climbing while the real quality of its answers stops improving and then gets worse.
  • pass@kpass@k, n.: A score for code-writing AI: the chance that at least one of k attempts at a problem is correct, as checked by actually running tests on the code.
Contrast with
  • beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility.
  • self-consistencyself-consistency, n.: Asking an AI the same question many times, letting it reason differently each time, then going with the answer it reaches most often — a vote among its own attempts.

Sources

  1. Gao, L., Schulman, J. & Hilton, J. (2022). Scaling Laws for Reward Model Overoptimization. ICML 2023. arXiv:2210.10760. arxiv.org/abs/2210.10760
  2. Beirami, A. et al. (2024). Theoretical guarantees on the best-of-n alignment policy. arXiv:2401.01879. arxiv.org/abs/2401.01879

Mentioned in

temperaturetemperature, n.: A setting that controls how adventurous an AI model's word choices are. Low temperature makes it pick the safest, most likely words; high temperature makes it more varied and surprising, but more error-prone., decodingdecoding, n.: The method a language model uses to turn its predictions into actual text — for example, always picking the most likely next word, or choosing somewhat at random among the likely ones., pass@kpass@k, n.: A score for code-writing AI: the chance that at least one of k attempts at a problem is correct, as checked by actually running tests on the code., rejection samplingrejection sampling, n.: Generating many candidate answers and keeping only those that pass a check — a scoring model, a test or a correct final answer — often so the AI can then be trained on its own best work., reward modelreward model, n.: A separate AI model trained to score responses the way people would, so it can stand in for human judges while another model is trained on millions of examples., reward overoptimizationreward overoptimization, n.: What happens when an AI is trained too hard to please an imperfect scoring model: its scores keep climbing while the real quality of its answers stops improving and then gets worse., samplingsampling, n.: Picking some items at random from a larger set or from a range of possibilities — surveying 1,000 voters, say, or letting an AI choose its next word by a weighted lottery., self-consistencyself-consistency, n.: Asking an AI the same question many times, letting it reason differently each time, then going with the answer it reaches most often — a vote among its own attempts., test-time computetest-time compute, n.: The computing effort an AI model spends while answering a question, as opposed to while being trained. Letting a model think longer or try many answers can make it markedly smarter., verifierverifier, n.: A program or AI model that checks whether a proposed answer is correct — by running tests, comparing with a known result or judging the reasoning — so that good answers can be picked or rewarded., capability elicitationcapability elicitation, n.: The work of drawing out the best an AI can do on a test — with better instructions, tools, retries or extra training — so that its abilities are not underestimated., evaluator–optimizerevaluator–optimizer, n.: A pairing in which one AI produces a draft and another AI grades it and suggests fixes, repeating the cycle until the work is good enough., outcome reward modeloutcome reward model, n.: A model that judges only whether an AI's final answer is right, ignoring how it got there — like a teacher who checks just the answer box., process reward modelprocess reward model, n.: A model that grades each step of an AI's worked solution, not just the final answer, so mistakes can be caught where they happen — like a teacher marking every line of a proof., process supervisionprocess supervision, n.: Training an AI by grading each step of its reasoning or work, not just whether the final answer came out right, so that it learns sound methods instead of lucky shortcuts., quantilizerquantilizer, n.: An AI decision rule that, instead of picking the single highest-scoring action, picks at random among the top few percent of ordinary, human-like actions — limiting how badly a flawed goal can backfire., RewardBenchRewardBench, prop. n.: A public test that checks whether the scoring models used to train chatbots can tell a better answer from a worse one, by counting how often they prefer the right response.