Speculative Decoding

Generating text from a large language model is slow for a structural reason unrelated to raw hardware speed: each new token depends on every token before it, so tokens must be produced strictly one at a time — you cannot generate token 51 before knowing token 50. That sequential dependency means large-model generation is memory-bandwidth-bound, not compute-bound: the GPU spends most of its time waiting to move weights through memory for each single-token step, while its compute capacity sits mostly idle, since one token at a time barely uses the parallelism a GPU is built for. Speculative decoding attacks this mismatch directly: use a smaller, cheaper model to guess several tokens ahead quickly, then use the large model's spare compute capacity to check all of those guesses at once, in parallel, in roughly the time it would take to generate just one token normally.

The analogy: a junior associate drafting, a partner reviewing in bulk

Picture a law partner who reviews carefully but is slow to draft from scratch, and a junior associate who drafts quickly but less reliably. Instead of the partner writing every sentence themselves, the associate drafts the next five quickly, and the partner reads all five at once, approving them (reading five at once isn't much slower than reading one) or stopping at the first sentence they'd have written differently, discarding everything after. Whenever the associate's guesses hold up, the partner's expensive time verifies five sentences' worth of work in roughly the time it takes to write one themselves.

The mechanism

A small draft model generates $k$ candidate tokens autoregressively, one at a time (cheap, since it's small). The large target model then runs a single forward pass over the entire draft sequence at once — verifying $k$ tokens in parallel, given they're already fixed, is one pass through the network, not $k$ sequential passes — computing, for each position, the probability it itself would have assigned.

Each draft token is accepted with probability $\min\!\left(1, \dfrac{p_{\text{target}}(x)}{p_{\text{draft}}(x)}\right)$, and generation stops accepting at the first rejection, resampling that position from a corrected distribution and discarding everything guessed after it.

In words: a draft token is kept if the big model would have been at least as likely to produce it, and even when less confident, it's kept with a probability matched exactly to preserve the target model's true output distribution — designed so the final output is statistically identical to what the large model would have generated alone, just faster.

Worked example 1: an accept-reject pass

Draft model proposes 4 tokens: The, cat, sat, quietly. The target model's single parallel pass returns its own probabilities for each position: it agrees strongly on The (accept) and cat (accept), but assigns sat only a 0.4 acceptance ratio — suppose this draw fails, so sat is rejected. At that point the target model resamples the position from its own corrected distribution, say producing slept, and everything guessed afterward (quietly) is discarded, since it was conditioned on a token that never got accepted. Net result: 2 tokens accepted, 1 generated fresh, in a single verification pass — 3 tokens for roughly the cost of one target-model forward pass, versus 3 sequential passes normally.

Worked example 2: expected speedup from acceptance rate

If the draft model's proposals are accepted with average probability $\alpha$ per token and the draft proposes $k=5$ tokens per round, the expected number of tokens accepted per round is $\frac{1-\alpha^{k+1}}{1-\alpha}$ (a standard geometric-series result). At $\alpha=0.7$, $k=5$: expected accepted tokens $\approx \frac{1-0.7^6}{1-0.7} = \frac{1-0.1176}{0.3} \approx 2.94$ tokens per single target-model verification pass, versus 1 token per pass the normal way — roughly a 2.9× speedup in the number of target-model passes needed, before accounting for the (cheap) draft model's own cost.

Expected tokens accepted per round falls off as draft acceptance probability drops — a curve with roughly this shape — which is why speculative decoding pays off most when the small draft model closely mimics the large target model's behaviour.

What this means in practice

Speculative decoding is now standard in production LLM serving stacks, typically paired with Multi-Query and Grouped-Query Attention and FlashAttention and IO-Aware Attention since all three attack different parts of the same generation-latency problem. The draft model is usually a much smaller version of the target model, or a distilled version trained specifically to mimic it — the better the draft matches the target's behaviour, the higher the acceptance rate, and the larger the realised speedup.

Practice

1. With draft acceptance probability $\alpha=0.9$ and $k=4$ proposed tokens per round, compute the expected number of accepted tokens per target-model pass.
2. Why must the target model's single parallel verification pass see the entire draft sequence at once, rather than verifying tokens one at a time, for the speedup to materialise?