Speculative Decoding

Spare arithmetic

A decode step for one sequence leaves most of a GPU's arithmetic unused (prefill and decode). Scoring five positions at once costs about the same time as scoring one, because the weights are read once either way. Speculative decoding spends that spare capacity on guesses.

Leviathan and colleagues observed that hard language-modelling tasks often include easier steps that a much smaller model can approximate well, and used speculative execution with a new sampling rule to make exact decoding from the large model faster Established.

Draft, then verify

1. A small draft model $q$ proposes $\gamma$ tokens, one after another (cheap).
2. The large target model $p$ scores all $\gamma$ positions, plus one more, in a single parallel pass.
3. Walk through the drafts. Keep draft token $x$ with probability $\min(1, p(x)/q(x))$.
4. At the first rejection, sample a replacement from the leftover distribution $\max(0, p - q)$, normalized, and stop. If every draft is kept, take one more token from the target's extra position.

Each round produces between 1 and $\gamma + 1$ tokens for one pass of the target model.

Why the output doesn't change

The accept-or-resample rule is a form of rejection sampling. When the draft over-proposes a token ($q > p$), it is kept only part of the time; when it under-proposes one ($q < p$), the shortfall comes back through the resampling step. Both papers prove the procedure samples from exactly the target model's distribution Established, so unlike distillation or quantization, it trades nothing in output quality.

Tiny example. Target $p = [0.5, 0.25, 0.15, 0.10]$ over four words, draft $q = [0.3, 0.4, 0.2, 0.1]$. The draft is accepted with probability $\sum \min(p, q) = 0.3 + 0.25 + 0.15 + 0.1 = 0.8$. Run the rule many times and the words come out in the proportions of $p$, not $q$: try it in the lab below.

How much faster

If each drafted token is accepted with probability $\alpha$ (independently, a simplifying assumption the paper makes),

$$\mathbb{E}[\text{tokens per target pass}] = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}, \qquad \text{speed-up} = \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)},$$

where $c$ is the cost of a draft step relative to a target step Established. With $\alpha = 0.8$, $\gamma = 4$ and $c = 0.05$: 3.36 tokens per pass and a 2.8× speed-up, in theory.

On T5-XXL, speculative decoding ran 2–3× faster than the standard T5X implementation with identical outputs Established, and speculative sampling sped up decoding of the 70B-parameter Chinchilla by 2–2.5× in a distributed setup Established.