Why the Output Stays Exact
Lesson 2 of 3 in Speculative Decoding.
“Faster, and the output is unchanged” should trip your alarm. Nearly every acceleration in this domain buys speed with a quality trade: Quantization nudges the Weights, aggressive Sampling caps reshape the distribution, shrinking the model changes everything. Speculative decoding claims something stronger — the committed tokens follow exactly the target model’s distribution, as if the draft model never existed. Not approximately, not “close enough in practice”: the same distribution, provably (Leviathan et al. 2022; Chen et al. 2023).
The whole guarantee lives in one small rule applied at each drafted position. Call p the target model’s probability for the drafted token, and q the draft model’s probability for it — the probability under which it was proposed.
- If p ≥ q — the target likes this token at least as much as the draft did — accept it.
- If p < q — the draft over-proposed it — accept with probability p/q. Otherwise reject: discard this token and everything drafted after it, and resample this position from the target’s leftover preference — the distribution proportional to max(0, p − q) across the vocabulary, i.e. probability mass the target wanted but the draft under-supplied.
Rejection is not a failure state. It is the correction step — the mechanism that turns a biased proposal stream into unbiased output.
Bar chart of eight speculation cycles with committed token counts of 5, 2, 4, 1, 5, 3, 1, and 4. Tall bars of five tokens mark cycles where all four drafts were accepted plus a bonus token; bars of one token mark cycles where the first draft was rejected and resampled.
Why accept-with-p/q plus resampling reproduces the target exactly
No equations needed — an accounting argument does it. Fix any token x in the Vocabulary and ask: across many runs, how often does the scheme commit x at this position? There are only two doors x can come through.
Door one: the draft proposed x. That happens with frequency q(x). If the draft over-proposes it — q(x) > p(x) — the acceptance rule keeps only a p/q fraction, trimming the committed frequency to q(x) · p(x)/q(x) = p(x): exactly what the target wanted. If the draft under-proposes it, every proposal is accepted, contributing q(x) — which is not enough.
Door two: the resample. The correction distribution is built from max(0, p − q), which is nonzero precisely for the under-proposed tokens, and supplies each one in proportion to its shortfall p(x) − q(x). Add the two doors: under-proposed tokens get q(x) + (p(x) − q(x)) = p(x), over-proposed tokens get p(x) from door one alone. Every token lands on exactly p — the target distribution, reproduced without ever running the target serially.
This is rejection sampling with the waste engineered out: a classical rejection sampler would retry until something is accepted, while here the leftover distribution is computed in closed form, so a rejection still commits a token in one shot. Two boundary cases make it concrete. With Greedy decoding, the rule collapses to string equality: accept if the draft picked the target’s argmax, otherwise emit the argmax. And if the draft were the target (q = p), p/q is always 1 — nothing is ever rejected, which is the sanity check that rejections measure disagreement, nothing else.
One honest caveat: exactness is a property of the algorithm on paper, applied to whatever distribution the target’s sampling settings define (Temperature, Top-p (nucleus) sampling and friends must be applied consistently before the comparison). A specific engine implementation can still deviate — through floating-point differences or how it composes the rule with its sampling filters. That gap between theorem and shipped code is why lesson three ends with “test it yourself”.
Exactness is unconditional; the speedup is anything but. Two dials govern it.
Acceptance rate — how often the target agrees with a drafted token. High agreement means long committed spans per verify pass (the tall bars in the figure); low agreement means you pay for drafting and verifying tokens that get thrown away. Agreement is high exactly when the next token is predictable: boilerplate, code syntax, quoted context, low-Temperature settings that concentrate the target distribution. Turn the temperature up and both distributions flatten — the probability of drafting the specific token the verifier will favor drops, and acceptance falls with it.
Draft cost — the small model runs k serial steps per cycle, every cycle. A draft too weak tanks acceptance; a draft too close to the target eats the savings. The draft length k rides the same trade-off: each extra drafted token is cheap, but one early rejection discards everything after it, so long drafts only pay when acceptance is high. Engines expose k as a tunable for exactly this reason.
The punchline for operators: speculative decoding moves your TPOT meter — never your quality meter. If quality changed after enabling it, something is misconfigured or the implementation is broken. Speed is the only honest axis of evaluation, and acceptance rate is the diagnostic that explains whatever the speed meter shows.
Interactive checkpoint quiz (1 questions) — open this page in a browser to take it.