Speculative Decoding

A draft model proposes, the target model verifies — and a rejection-sampling argument makes the output distribution exactly the target's, with no approximation.

LLM OpsGraduate⏱ 1 hour13 min readspeculative decodingrejection samplingtotal variationacceptance ratelatency

2 problems →

AssumesInference Arithmetic and the Roofline · Expectation, Variance and Conditional Expectation · Language Modelling, Cross Entropy and Perplexity

The algorithm

Algorithm — Speculative sampling, one round

Given context $x_{<t}$ , sample $\gamma$ draft tokens autoregressively from the draft model: $\tilde x_{t+i} \sim q(\cdot \mid x_{<t}, \tilde x_{t:t+i-1})$ for $i = 0,\dots,\gamma-1$ .
Run the target model once, in parallel over all $\gamma+1$ positions, to obtain $p(\cdot \mid x_{<t}, \tilde x_{t:t+i-1})$ for every $i$ .
For $i = 0,1,\dots,\gamma-1$ in order, draw $u \sim \mathrm{Unif}(0,1)$ and accept $\tilde x_{t+i}$ if $u \ \le\ \min\left(1,\ \frac{p(\tilde x_{t+i})}{q(\tilde x_{t+i})}\right).$ Stop at the first rejection.
If a rejection occurred at position $i$ , emit one token drawn from the residual distribution $p'(x) \ \propto\ \max\big(0,\ p(x) - q(x)\big),$ and discard the remaining drafts. If all $\gamma$ were accepted, emit one extra token from $p(\cdot \mid x_{<t}, \tilde x_{t:t+\gamma-1})$ , which step 2 already computed.

Every round costs $\gamma$ draft passes plus one target pass, and yields between $1$ and $\gamma+1$ tokens.

Exactness

TheoremSpeculative sampling is exact

Fix distributions $p$ and $q$ on a finite vocabulary $\mathcal V$ with $q(x) > 0$ wherever $p(x) > 0$ . Draw $X \sim q$ , accept with probability $\min(1, p(X)/q(X))$ , and on rejection draw $Y \sim p'$ where $p'(x) = \max(0, p(x)-q(x))/\beta$ with $\beta = \sum_{x}\max(0, p(x)-q(x))$ . Then the emitted token is distributed exactly as $p$ .

Assumptions

Absolute continuity of $p$ with respect to $q$ on the support — if the draft assigns zero probability to a token the target wants, that token can never be proposed, and the residual step is what repairs it. Note the theorem assumes nothing about how good $q$ is: a uniform draft model gives an exact sampler, just a slow one.

Key idea

The draft model affects speed only, never quality. This is what separates speculative decoding from approximations like early exit or cascades: there is no quality/latency dial to tune, because there is no quality loss to trade. A deployment can adopt it without re-running evaluations.

How often do we accept?

PropositionAcceptance probability equals one minus total variation distance

The probability that a proposal from $q$ is accepted is

\alpha = \sum_{x}\min\big(p(x), q(x)\big) = 1 - \mathrm{TV}(p,q), \qquad \mathrm{TV}(p,q) = \tfrac12\sum_x |p(x)-q(x)| .

This is a clean statement of what makes a good draft model: not low perplexity in the usual sense, but small total variation distance to the target's conditional, token by token. A draft that is confidently wrong is worse than one that is diffusely uncertain, because TV punishes mass placed where the target puts none.

Expected yield per round

PropositionExpected tokens per verification round

Suppose each draft position is accepted independently with probability $\alpha \in [0,1)$ . Then a round with draft length $\gamma$ emits

\E[\,\text{tokens}\,] = \frac{1 - \alpha^{\gamma+1}}{1-\alpha}

tokens in expectation.

Assumptions

Independence and a common $\alpha$ across positions. Both are idealisations: acceptance at later positions is conditioned on the earlier draft tokens being accepted, which correlates the events, and $\alpha$ varies token by token — easy continuations accept far more often than hard ones. Treat this as a first-order model, and see the caveat at the end.

As $\gamma \to \infty$ this saturates at $1/(1-\alpha)$ : however long you draft, you cannot average more than $1/(1-\alpha)$ tokens per target pass. At $\alpha = 0.8$ the ceiling is 5 tokens per round, and $\gamma = 8$ already achieves $4.6$ of them.

Speedup, and how far to draft

CorollarySpeedup and the optimal draft length

Let the draft model cost a fraction $c \in (0,1)$ of a target forward pass. Relative to ordinary decoding, the wall-clock speedup is

\mathcal S(\gamma) = \frac{1-\alpha^{\gamma+1}}{(1-\alpha)\,(\gamma c + 1)} ,

which for $c > 0$ is maximised at a finite $\gamma$ .

Empirical observation

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

Reported end-to-end speedups for well-matched draft/target pairs cluster around $2$ – $3\times$ on standard generation workloads, with acceptance rates in the range $0.7$ – $0.9$ — consistent with the model above once correlation is accounted for. Gains are smaller on tasks where the target's conditionals are high-entropy, which is exactly what $\alpha = 1 - \mathrm{TV}$ predicts.

What this does not say

This analysis is about latency for a single stream. Speculative decoding spends extra FLOPs to buy back idle memory-bandwidth time, so its advantage shrinks as batch size grows and the system moves towards compute-bound — precisely the regime a throughput-oriented server tries to reach. It is a latency technique, and on a saturated server it can reduce total throughput.

References

PaperY. Leviathan, M. Kalman, Y. Matias (2023). Fast Inference from Transformers via Speculative Decoding
PaperC. Chen et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremSpeculative sampling is exactproof includedModified rejection sampling with a residual fallback produces samples distributed exactly according to the target model, for any draft model.
PropositionAcceptance probability equals one minus total variation distanceproof includedThe per-token acceptance rate is exactly 1 − TV(p, q), tying speedup directly to how well the draft matches the target.
PropositionExpected tokens per verification roundproof includedWith draft length γ and i.i.d. acceptance rate α, each round emits (1 − α^(γ+1))/(1 − α) tokens in expectation.
CorollarySpeedup and the optimal draft lengthproof includedWall-clock gain is the expected token count divided by γc + 1, which is maximised at a finite γ whenever the draft is not free.

Problems (2)

All problems