Speculative Decoding: Lossless Multi-Token Generation

Let $q_i$ be the draft distribution at position $i$ and $p_i$ be the target distribution. This page follows Leviathan et al.'s notation, where $p$ is the target and $q$ is the draft; Chen et al. use the opposite symbols. If the draft proposes token $x_i$, it is accepted with probability:

If a proposed token is rejected, you sample from a residual distribution that corrects for what the draft already "used up":

This rejection-and-residual mechanism is what makes the method lossless: accepted tokens come from $q$ but are filtered to match $p$, and the residual sample at a rejected position supplies exactly the probability the filter removed.

How much faster?

Averaged over the draft's proposals, a position is accepted with probability $\beta = \sum_x \min\big(p(x), q(x)\big)$, which is 1 when the two distributions agree and 0 when they do not overlap (Leviathan et al., 2023, Theorem 3.5). Let $\alpha$ be the average of $\beta$ over positions. Leviathan et al. make the simplifying assumption that acceptances are independent, each with probability $\alpha$. Then one target pass with $k$ draft tokens produces on average $\mathbb E[\text{tokens per target pass}] = \dfrac{1-\alpha^{k+1}}{1-\alpha}$ tokens.

This counts the accepted prefix plus one token from the target: either the residual sample at the first rejection or a new token when all $k$ are accepted. The count ranges from 1 (the first draft token is rejected) to $k+1$.

Each round also runs the draft model $k$ times. If one draft pass takes $c$ times as long as one target pass, the expected wall-clock speedup is $\dfrac{1-\alpha^{k+1}}{(1-\alpha)(kc+1)}$ (Leviathan et al., 2023, Theorem 3.8). For example, with $\alpha = 0.8$, $k = 4$ and $c = 0.05$, a target pass yields about 3.36 tokens and the speedup is about 2.8×. A longer draft helps only while $\alpha$ is high; when the draft is often wrong, the extra draft passes cost more than the extra accepted tokens save. The formula also assumes the target can score $k+1$ positions in about the time of one, which holds when decoding is limited by memory bandwidth, not when the hardware is already busy with large batches.

Worked example: where the rejected probability goes

Take four tokens A, B, C, D with the target and draft from the code below, $p=(0.45,\,0.30,\,0.15,\,0.10)$ and $q=(0.30,\,0.45,\,0.20,\,0.05)$. A proposed token is kept with probability $\min(1,p/q)$, which is $(1,\,2/3,\,3/4,\,1)$. The probability that each token is proposed and kept is $q\cdot\min(1,p/q)=\min(p,q)$:

A rejection therefore happens with probability $1-\beta=0.20$, and the residual it samples from is

Rejections add $0.20\cdot(0.75,0,0,0.25)=(0.15,0,0,0.05)$, and kept plus repaired is $(0.45,0.30,0.15,0.10)=p$. The residual is a distribution over the tokens the draft under-proposed, A and D, in proportion to their shortfalls, $0.15$ and $0.05$; scaled by the rejection probability $0.20$, it adds back exactly each shortfall. When $p=q$ every proposal is kept and the residual is never sampled; when $p$ and $q$ differ, however slightly, it must be normalized and used, or the output loses that probability.

When acceptance changes along the draft

The token count above assumes every position is accepted independently with the same $\alpha$. Without that assumption, let $a_i$ be the probability that draft position $i$ is accepted given that positions $1,\ldots,i-1$ were, and let $L$ be the number of draft tokens accepted. By the chain rule,

With $k=4$ and $a=(0.80,\,0.75,\,0.50,\,0.25)$, the survival probabilities are $(0.80,\,0.60,\,0.30,\,0.075)$, so $\mathbb E[L]=1.775$ and one target pass yields $2.775$ tokens on average. Reverse the order to $a=(0.25,\,0.50,\,0.75,\,0.80)$: the mean acceptance is the same $0.575$, but the survival probabilities are $(0.25,\,0.125,\,0.09375,\,0.075)$ and $\mathbb E[L]=0.54375$. A rejection ends the draft, so the early positions count most, and the mean acceptance alone does not determine the expected length; independent acceptance at $\alpha=0.575$ gives a third value, $\mathbb E[L]=1.205$.

These are tokens per target pass, not speedups. The speedup also depends on the draft's cost and on how long the target takes to score the draft, as above.