Skip to content
Last Dictionary
Plane
Training & Post-trainingMathematics & StatisticsLanguage Models & Transformers

rejection sampling

nounAlso: acceptance–rejection method, accept–reject algorithm, rejection sampling fine-tuning, rejection-sampled fine-tuning

In plain wordsGenerating 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.

  1. 1

    Post-training

    A data-generation technique in which a model samples several responses per prompt, 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. or 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. scores them, and only the best (or all that pass a threshold) are kept, typically as targets for further supervised fine-tuningsupervised fine-tuning, n.: Teaching a pretrained AI model by showing it many examples of good answers to requests, so it learns to imitate them — like learning a job by studying worked examples. — a procedure called rejection sampling fine-tuning. Iterated, it is a simple, stable alternative or complement to policy-gradient RL: Meta's Llama 2-Chat used rejection-sampling fine-tuning alone in early rounds and then applied proximal policy optimizationproximal policy optimization, n.: A widely used method for training AI by trial and error that improves the strategy in small, safe steps; it was the workhorse behind training chatbots like ChatGPT with human feedback. on top of it, and reasoning pipelines use it to harvest correct chains of thoughtchain of thought, n.: Getting an AI to write out its reasoning step by step before giving an answer, the way a student shows their working. This often makes answers to math and logic problems more accurate. for SFT, as in STaRself-taught reasoner, n.: A training method in which a language model writes step-by-step explanations for problems, keeps the ones that led to correct answers, and learns from them, so it gradually teaches itself to reason. and expert iterationexpert iteration, n.: A learning loop in which a slow, careful search finds better moves or solutions than the AI's quick instincts, and the AI is then trained to imitate them, so each round's search starts smarter.. Because only successes are kept, the model learns nothing from its failures, and the data concentrate on problems it can already sometimes solve. Used at inference time without retraining, the same select-the-best step is usually called best-of-n samplingbest-of-n sampling, n.: Asking 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..

    We ran three rounds of rejection sampling, keeping only solutions whose final answers matched the key.

  2. 2

    Statistics

    A Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating. for drawing samples from a target distribution p that is hard to sample directly: draw a candidate x from an easy proposal distribution q, scaled by a constant M so that M·q(x) ≥ p(x) everywhere, and accept it with probability p(x)/(M·q(x)); accepted draws follow p exactly. Efficiency falls as M grows, severely so in high dimensions.

Pr⁡[accept x]=p(x)M q(x),p(x)≤M q(x)    ∀x\Pr[\text{accept } x] = \frac{p(x)}{M\,q(x)}, \qquad p(x) \le M\,q(x) \;\; \forall x

Origin

The statistical method was described by John von Neumann in 1951 in a note on techniques for using random digits. Its machine-learning namesake, filtering a model's samples with a reward, appears in OpenAI's WebGPT (December 2021), which used rejection sampling against a reward model for best-of-n selection, and was popularized as a training step by Meta's Llama 2 report (July 2023).

Usage note

The LLM sense borrows the name loosely: nothing guarantees that kept samples follow a particular target distribution. The abbreviation RFT can mean rejection sampling fine-tuning or reinforcement fine-tuningreinforcement fine-tuning, n.: Improving a trained AI model by trial and error instead of examples to copy: it tries answers, a grader scores them, and the model shifts toward whatever earned high scores.; check which is meant.

Related

See also
  • best-of-n samplingbest-of-n sampling, n.: Asking 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.
  • expert iterationexpert iteration, n.: A learning loop in which a slow, careful search finds better moves or solutions than the AI's quick instincts, and the AI is then trained to imitate them, so each round's search starts smarter.
  • self-taught reasonerself-taught reasoner, n.: A training method in which a language model writes step-by-step explanations for problems, keeps the ones that led to correct answers, and learns from them, so it gradually teaches itself to reason.
  • 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.
  • Monte Carlo methodMonte Carlo method, n.: Estimating an answer by running many random trials and averaging the results — like estimating the odds in a card game by dealing thousands of hands instead of calculating.
  • supervised fine-tuningsupervised fine-tuning, n.: Teaching a pretrained AI model by showing it many examples of good answers to requests, so it learns to imitate them — like learning a job by studying worked examples.
Contrast with
  • reinforcement fine-tuningreinforcement fine-tuning, n.: Improving a trained AI model by trial and error instead of examples to copy: it tries answers, a grader scores them, and the model shifts toward whatever earned high scores.

Sources

  1. von Neumann, J. (1951). Various Techniques Used in Connection with Random Digits. National Bureau of Standards Applied Mathematics Series 12, 36–38.
  2. Nakano, R. et al. (2021). WebGPT: Browser-assisted question-answering with human feedback. arXiv:2112.09332. arxiv.org/abs/2112.09332
  3. Touvron, H. et al. (2023). Llama 2: Open Foundation and Fine-Tuned Chat Models. arXiv:2307.09288. arxiv.org/abs/2307.09288

Mentioned in

synthetic datasynthetic data, n.: Data created by computer programs or AI models rather than collected from the real world — such as practice math problems written by a model, or simulated street scenes for self-driving cars., best-of-n samplingbest-of-n sampling, n.: Asking 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., reinforcement fine-tuningreinforcement fine-tuning, n.: Improving a trained AI model by trial and error instead of examples to copy: it tries answers, a grader scores them, and the model shifts toward whatever earned high scores., 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., self-improvementself-improvement, n.: When an AI gets better by learning from material it produces itself — its own answers, critiques or practice problems — rather than only from new human-made examples., expert iterationexpert iteration, n.: A learning loop in which a slow, careful search finds better moves or solutions than the AI's quick instincts, and the AI is then trained to imitate them, so each round's search starts smarter., self-taught reasonerself-taught reasoner, n.: A training method in which a language model writes step-by-step explanations for problems, keeps the ones that led to correct answers, and learns from them, so it gradually teaches itself to reason., WebGPTWebGPT, prop. n.: A 2021 OpenAI research system that answered questions by searching and browsing the web in a simple text browser, collecting sources and citing them — an early ancestor of today's research agents.