Definition
Plain language
A way of drawing samples that match a desired pattern by proposing candidates and accepting or rejecting each with just the right odds.
As stated in the literature
A sampling method that accepts proposed draws with a probability calibrated so the accepted set matches a target distribution exactly; in speculative decoding it makes the drafter-plus-verifier output provably identical in distribution to the base model's.
Why it matters: It matters because it lets you produce samples that exactly match a target pattern, which is how speculative decoding stays faithful to the original model.
For example, to draw points evenly from an odd shape, you scatter points in a box around it and simply keep the ones that land inside.
Heard on the show
“And there's a piece of math underneath — rejection sampling — that makes it exactly lossless.”Episode 179 — How DeepSeek Made One User Faster Without Slowing Down the Crowd