Rejection sampling and speculative decoding

Sample from a distribution you can evaluate but not easily draw from, by proposing from an easier one and sometimes saying no. The same idea makes LLM inference 2–3× faster without changing a single output probability.

Key idea: Rejection sampling, the speculative sampling acceptance rule, and acceptance rate as total variation
Real world: A junior editor drafts headlines quickly; the senior editor approves or rewrites each. If the junior's style is close to the senior's, most drafts pass and the desk moves fast. The paper's headlines still read exactly as if the senior had written them all.
In an LLM: A small draft model proposes the next 4 tokens. The large model checks all 4 in a single forward pass and accepts a prefix of them. Output follows the large model's distribution exactly, but it needs far fewer slow forward passes.

Rejection sampling

Suppose you can evaluate a target distribution $p$ but can't easily sample from it, and you can sample from a proposal $q$ . Rejection sampling:

Draw $x$ from $q$ .
Accept it with probability proportional to $p(x)/q(x)$ , scaled so the largest ratio gives probability 1.
If rejected, start again.

Accepted samples follow $p$ exactly. The price is wasted proposals: the further $q$ is from $p$ , the more you throw away. Unlike importance sampling, which keeps every sample with a weight, rejection sampling produces honest, unweighted samples.

example · random points in a circle

To pick a uniformly random point inside a circle, pick a random point in the surrounding square (easy) and throw it away if it lands outside the circle. About 79% of points are kept, the circle's share of the square. The kept points are perfectly uniform over the circle.

example · rejection sampling for fine-tuning data

"Rejection sampling" in LLM papers usually means something looser: generate many answers, keep the ones a verifier or reward model accepts, and fine-tune on them. If you keep everything that passes a correct/incorrect check, the kept set is an exact sample from the model's distribution conditioned on being correct: $p(y \mid \text{correct})$ . That's conditional probability by sampling, and the basis of STaR and expert iteration (distillation).

Speculative decoding

Generating text with a large model is slow mostly because each token needs a full forward pass, one after another. But checking several tokens at once costs about the same as generating one. Speculative decoding exploits this:

A small draft model $q$ quickly writes $\gamma$ tokens.
The large target model $p$ computes its probabilities for all $\gamma$ positions in one pass.
Go through the drafted tokens in order. Keep token $x$ with probability $\min\big(1, p(x)/q(x)\big)$ .
At the first rejection, sample a replacement from the residual distribution, proportional to $\max(0,\ p - q)$ , and discard the rest of the draft.

The rule is designed so that the token that comes out at each position, accepted or replaced, is distributed exactly as $p$ . Not approximately: exactly. A bad draft model costs speed, never quality.

example · the editor and the junior

The junior drafts "Mayor unveils budget plan". The senior would have written "Mayor" with 60% chance; the junior wrote it with 50%. Since the senior likes it at least as much, it's kept. The junior's "unveils" has 40% from the junior but only 10% from the senior: kept a quarter of the time. When it's rejected, the senior picks a replacement only from words they like more than the junior does.

example · drafting 'the' and 'a'

The target gives "the" 0.42 and "a" 0.22; an overeager draft gives "the" 0.18 and "a" 0.40. A drafted "the" is always kept (the target likes it more). A drafted "a" is kept with probability $0.22/0.40 = 55\%$ . When it's rejected, the replacement is drawn mostly from "the", which the draft under-proposes. The bookkeeping works out to exactly 42% "the" and 22% "a" in the output.

How fast?

The chance that a drafted token is accepted is

\alpha = \sum_x \min\big(p(x),\ q(x)\big) = 1 - \mathrm{TV}(p, q)

where TV is the total variation distance (divergences). The better the draft matches the target, the higher $\alpha$ , and the more tokens each expensive pass produces: about $(1 - \alpha^{\gamma+1})/(1 - \alpha)$ with $\gamma$ drafted tokens. Real systems see acceptance rates of 0.6–0.9 and speedups of 2–3×.

Try it

how closely the draft matches0.50draft tokens per check γ4

drafted and kept: min(p, q)drafted but rejectedrefilled from the residual: max(0, p − q)target p

100%kept71%kept100%kept100%kept41%kept100%kept

One call of the big model: the draft writes 4 words, the target checks them all at once

the✓mythefixedmydroppedthisdropped

1 call, 2 words: 2.00 per call (expected 3.43)

acceptance rate α = Σ min(p, q)81.0%

total variation 1 − α0.190

tokens per target call3.43

Read each word’s pair of bars. Left, the draft: the amber part is kept, the red part (where the draft is keener than the target) is rejected. Right, what comes out: the kept amber part, plus green refills drawn from the residual where the target wants more than the draft offered. Together they rebuild the target p exactly. Run it to check.

A large target model p and a small draft model q, both predicting the next word. The draft proposes; the target checks.

Where this shows up

Speculative decoding in inference engines (vLLM, SGLang, TensorRT-LLM), and variants like EAGLE and Medusa that predict drafts from the target's own features.
Rejection-sampling fine-tuning, STaR, and best-of-n data filtering: distillation, latent variables.
DAPO's dynamic sampling rejects prompt groups where every answer got the same reward: GRPO fixes.
The same ratio $p/q$ is an importance weight; here it becomes an acceptance probability instead of a multiplier.

going deeper