A small draft model guesses a token; the big model checks it in a single parallel pass — and the sampled output is bit-for-bit the big model's own distribution, never altered. The trick is a rejection rule: accept the guess x with probability min(1, p(x)/q(x)), and when you reject, emit from the residual that repairs the gap exactly. Down the center the tokens go in, the accept/reject engine runs, the proven-equal distribution comes out. The blue team builds and defends it; the red team tries to break it.
source Leviathan, Kalman & Matias, Fast Inference from Transformers via Speculative Decoding (2023) — arxiv.org/abs/2211.17192. Rendered, not quoted.
Correctness is not a hope; it is an algebraic identity. The draft proposes x ∼ q. Accept with probability a(x)=min(1, p(x)/q(x)). On the leftover rejection mass, emit from the residual r = norm(max(0, p−q)).
Per-token accept probability and the residual it draws from, live:
| token | p | q | a=min(1,p/q) | residual r |
|---|
This is the-rejection-sampling applied to decoding. Classic rejection sampling draws from a proposal and accepts to match a target; here the proposal is a cheap draft model and the target is the expensive one.
The one new idea: after a rejection, don't just retry — emit from the residual max(0, p−q) so no draft call is wasted. Many tokens are verified in one forward pass, and the sample is provably from exactly the big model's distribution. Each sphere is the next one's premise.
The blue team's live check: recompute the emitted distribution P_emit(x) for the current p, q and for eight seeded pairs, and confirm it equals the target p to 1e-12. If red tampers with the rejection path, this badge is where it shows.
Over a small vocabulary, two next-token distributions: the draft q (cheap, fast) and the target p (the true, expensive model). Both are proper distributions — non-negative, summing to 1.
The draft samples one token x ∼ q and hands it up to the panel. The panel decides whether to keep it — without ever changing what the target would have produced. Feed p and q into the engine below.
Each control recomputes the accept probabilities, the residual, and the emitted distribution on the spot — never looked up. Draw a token to watch one accept/reject decision play out under a fixed-seed PRNG.
| token | p | q | accepted min(p,q) | P_emit |
|---|
What the machine produces, proven: the emitted distribution equals the target p exactly (to 1e-12) — speculative decoding is a lossless speedup, not an approximation. Its expected acceptance equals the overlap ∑ min(p, q): the more the cheap draft agrees with the true model, the more tokens land per pass.
The blue team's witness (left) confirms the identity live; the red team (right) tries to make the output drift.
And the speedup is at the mercy of the draft: a poorly-aligned q gives low acceptance (∑min(p,q) small), so most guesses are rejected and you pay for the draft with little gain. The distribution is always exact; the economics are conditional.
"Speculative decoding is a faster approximation of the big model." Cut. It is exact — the sampled distribution is identical to standard decoding, provable as an algebraic identity (window 0).
"Rejected draft tokens are just wasted work, so you resample from q." Cut. On rejection you emit from the residual max(0,p−q). Resampling from q or p breaks exactness — that is the tamper below.
"A better draft always means a bigger speedup." Kept, corrected. Acceptance rises with overlap, but a slower draft can erase the gain; the win is a ratio of costs, not of accuracy.
The red team's move: on rejection, emit from the raw target p instead of the residual max(0,p−q). It looks reasonable — and it silently drifts the output off the target. The blue team's witness (window 7) is watching.
Swap the residual for the raw target and P_emit no longer equals p — the witness recomputes, the max deviation blows past 1e-12, and it turns red. Nothing is faked; the attack is real and it is caught.