Fast Inference from Transformers via Speculative Decoding

A small model guesses the next few tokens, the large model checks all of them in one pass, and the output distribution does not change.

Speculative decoding runs the large model once over several drafted tokens, keeps the prefix that a probabilistic test accepts, and decodes T5-XXL 2.3 to 3.4 times faster with no retraining and no change to what it generates.

Why a decode step is idle most of the time, the accept/reject rule that keeps the output exact, and the two numbers (α and c) that decide how much faster you get.

A language model like T5 or GPT-3 generates text one token at a time. Each token is produced by a full forward pass through the model, conditioned on everything generated so far, and the next pass cannot start until this one has finished, because its input includes the token just sampled. Decoding $K$ tokens takes $K$ serial runs of the model. For an 11B-parameter model that is 11B multiply-adds per token, and a serial chain of them.

Speculative decoding is a way to run that chain in fewer serial steps without changing the model or what it outputs. A small, cheap draft model proposes the next $\gamma$ tokens. The large model, the target whose output you want, then scores all $\gamma$ proposals in a single forward pass, which costs it about as much as scoring one. A probabilistic test decides how many of the proposals to keep, and the large model supplies one more token of its own. Each serial run of the large model therefore produces between 1 and $\gamma+1$ tokens, and the tokens that come out are distributed exactly as if the large model had generated them alone.

The paper measures the method on T5-XXL, an 11B-parameter encoder-decoder, with the 77M-parameter T5-small as the proposer: 3.4 times faster on English-to-German translation and 3.1 times on news summarization with argmax decoding, 2.6 and 2.3 times with sampling at temperature 1, against Google's own T5X implementation on one TPU v4 chip. The same idea was derived independently at DeepMind a few months later for Chinchilla 70B, with 2 to 2.5 times, and Google reports it in production behind AI Overviews in Search.

Four ideas explain the method: why a decode step has spare arithmetic capacity, how the draft-and-verify loop uses that capacity, the sampling rule that makes the output exact, and the two numbers that predict the speedup, the acceptance rate $\alpha$ and the cost coefficient $c$.

Decoding waits on memory, not arithmetic

Every forward pass of a Transformer reads every weight matrix out of accelerator memory and multiplies it by the activations. During decoding with a batch of one, the activations for a step are a single vector per layer, so the multiply is a matrix-vector product: each weight is read once and used once. On a TPU v4 chip the memory system delivers 1200 GB/s while the matrix units can do 275 TFLOP/s, so a weight that costs 2 bytes to fetch is used for 2 floating-point operations, and the chip could have done about 230 operations per byte fetched, or 460 per weight, in the time the fetch took.

Shazeer worked the ratio out for incremental decoding in the multi-query attention paper: the memory traffic per arithmetic operation is $\Theta(n/d + 1/b)$ with $n$ the sequence length, $d$ the model width, and $b$ the batch size, which is close to 1 at batch size 1, when hardware wants it around 1/100. Pope and colleagues say the same thing for large models in 2022: at small batch sizes, the time to load the weights dominates.

Concretely for T5-XXL: 11B parameters in bfloat16 are 22 GB, and streaming them through 1200 GB/s takes 18 ms. The arithmetic for one position is 2 × 11B = 22 GFLOP, which is 0.08 ms at peak and 0.16 ms at half of peak. Scoring 8 positions in the same pass costs 1.3 ms of arithmetic, still hidden under the 18 ms of weight traffic, because the weights are read once for the whole pass. Figure 1 draws this idealized model. Drag $\gamma$ and watch the pass time stay flat; the model only becomes compute-bound past about a hundred positions, and the crossover is the same for every model size because both lines scale with the parameter count.

Two things follow. A single target pass over $\gamma+1$ positions costs about one pass, so verifying several guesses at once is nearly free. And the same picture bounds the draft model's cost: T5-small's 77M parameters are 154 MB, 0.13 ms of traffic, so one draft run is about 0.7% of a target run in this model. The paper measures it at 2% with profiler traces, the gap being fixed per-call overheads that a tiny model cannot amortize; this ratio, draft time over target time, is the cost coefficient $c$ in the walltime formula below.

The loop: draft, verify in one pass, keep a prefix

Write $M_p$ for the target model, the one whose outputs you want, and $p(x)$ for the distribution it assigns to the next token given the prefix so far. Write $M_q$ for the approximation model, or draft, and $q(x)$ for its next-token distribution on the same prefix. Both are ordinary next-token distributions over the vocabulary, already adjusted for whatever sampling method is in use: argmax is a distribution with all its mass on one token, top-k and nucleus zero out the tail and renormalize, temperature rescales the logits (the raw scores before the softmax). The paper handles all of them by treating the adjusted $p$ and $q$ as the distributions and sampling from them plainly.

One step of speculative decoding, Algorithm 1 in the paper, with draft length $\gamma$:

1. Run $M_q$ autoregressively $\gamma$ times to draft tokens $x_1,\dots,x_\gamma$, recording each draft distribution $q_i$. These are $\gamma$ serial runs, but of the cheap model.
2. Run $M_p$ once on the prefix extended by all $\gamma$ drafts. With the causal mask a single forward pass returns the target's distribution at every one of the new positions, so this one pass yields $p_1,\dots,p_{\gamma+1}$: the target's view of the first draft, of the second given the first, and so on, plus $p_{\gamma+1}$, its distribution for the token after all $\gamma$ drafts.
3. Walk the drafts left to right. Accept draft $x_i$ with probability $\min(1, p_i(x_i)/q_i(x_i))$. Stop at the first rejection; call the number accepted $n$.
4. Emit one token from the target itself. If a draft was rejected, sample it from the residual distribution $p'$ built from $p_{n+1}$ and $q_{n+1}$ (next section). If every draft was accepted, sample it from $p_{\gamma+1}$, which the verification pass already computed.

The step returns $x_1,\dots,x_n$ followed by the target's token: at least 1 new token, at most $\gamma+1$. Because every step produces at least one token from one target run, the number of serial target runs can never exceed plain decoding, even when the draft is useless. The draft runs are serial too, but each is a fraction $c$ of a target run.

# one speculative decoding step (Algorithm 1), gamma = 3
prefix = tokens_so_far                          # [T]
# 1. draft: gamma serial runs of the SMALL model M_q
xs, qs = [], []
for i in range(gamma):
    q_i = softmax(M_q(prefix + xs))             # [V]
    x_i = sample(q_i)
    xs.append(x_i); qs.append(q_i)
# 2. verify: ONE run of the LARGE model M_p over the gamma new positions
ps = softmax(M_p(prefix + xs))                  # [gamma + 1, V], causal mask
# 3. keep a prefix of the drafts
n = 0
for i in range(gamma):
    if rand() <= ps[i][xs[i]] / qs[i][xs[i]]:   # accept w.p. min(1, p/q)
        n += 1
    else:
        break
# 4. the target's own token
if n < gamma:
    p_res = relu(ps[n] - qs[n]); p_res /= p_res.sum()   # residual
    t = sample(p_res)
else:
    t = sample(ps[gamma])                       # all accepted: bonus token
return prefix + xs[:n] + [t]                    # 1 .. gamma + 1 new tokens

Figure 2 runs the loop on a sentence. Each group between ticks is one serial run of the target: teal boxes are drafts it accepted, a struck box is the first rejected draft, and the amber box is the token the target supplied, either the correction after a rejection or the bonus token after a clean sweep. The header counts target runs against tokens produced; plain decoding would need one run per token. Slide $\alpha$ down to 0.3 and the groups shrink to one or two tokens; slide it to 0.95 and most runs produce all $\gamma+1$.

The KV cache, the per-layer keys and values a Transformer stores for every token in the prefix so it does not recompute them, needs one extra rule: the verification pass appends $\gamma$ entries, and after the accept test the entries beyond the accepted prefix are discarded, so the next step's prefix is exactly the tokens that were emitted. In the Hugging Face implementation this is one crop call after the sampling function returns.

Speculative sampling: the accept/reject rule

The rule in step 3 makes the output exact; it is what the paper adds to speculative execution, the processor technique of starting work before knowing whether its result will be needed. There a guess is right or wrong; here a drafted token is a sample, and the rule decides whether keeping it leaves the target's distribution intact. Given a token $x$ drawn from the draft's $q$, how do you turn it into a token distributed as the target's $p$, using only the two probability vectors?

Where the draft under-proposes a token, $q(x) \le p(x)$, keep it every time. Where the draft over-proposes, $q(x) > p(x)$, keep it with probability $p(x)/q(x)$ and otherwise reject it. On a rejection, draw a replacement from the residual distribution

which puts mass only on the tokens the draft under-proposed, in proportion to the shortfall. The accepted draws fill the region under $\min(p,q)$; the residual draws fill the rest of $p$. Appendix A.1 checks that the two add up to $p$ for every token $x$. A draft proposal lands on $x$ and survives with probability

and a rejection happens with probability $1-\beta$, where $\beta$ is the sum of $\min(p,q)$ over the vocabulary. That $1-\beta$ is also the normalizer in (2), so

and the sum of the two is $p(x)$. This holds for any $p$ and $q$, any vocabulary, and any sampling adjustment, which is why the draft model needs no training and no relation to the target beyond sharing a tokenizer.

Take a four-token vocabulary, with a target $p$ and a draft $q$ over tokens 0 to 3:

Three draft proposals in four survive. The shortfalls sum to 0.25, which is $1-\beta$, and normalizing them gives $p'$. Now check token 0: it is proposed and accepted with probability 0.30 (proposed 0.30 of the time and always kept), and it is produced on a rejection with probability 0.25 × 0.80 = 0.20; total 0.50, which is $p$ for token 0. Token 1: proposed 0.50 of the time, kept with probability 0.30 / 0.50, so 0.30, and never produced on a rejection; total 0.30.

# speculative sampling of ONE token, 4-token vocabulary
p = [0.50, 0.30, 0.15, 0.05]     # target
q = [0.30, 0.50, 0.10, 0.10]     # draft
x = sample(q)                    # say x = 1 (q gave it 0.50)
if rand() <= min(1, p[x] / q[x]):   # 0.30 / 0.50 = 0.6
    return x                     # accepted
p_res = [max(0, p[i] - q[i]) for i in range(4)]   # [0.20, 0, 0.05, 0]
p_res = [v / sum(p_res) for v in p_res]           # [0.80, 0, 0.20, 0]
return sample(p_res)             # never token 1 or 3 on a rejection

Figure 3 draws the same construction on a six-token vocabulary. The overlap band is the acceptance probability; the bottom panel is $p'$. The Sample button pushes tokens through the rule and marks their frequencies as ink ticks on the target's bars; after a few thousand draws they sit on $p$ whatever the sliders say. Push the temperature to 0.05 and both distributions collapse onto their top tokens: when the two argmaxes agree, $\beta$ goes to 1, and when they disagree it goes to 0 and the residual becomes the target's argmax, which is argmax decoding with a verify step.

Ordinary rejection sampling from $p$ with proposal $q$ accepts with probability $p(x)/(r_{\max}\,q(x))$ where $r_{\max}$ is the largest ratio $p(x)/q(x)$ over the vocabulary, so its overall acceptance rate is $1/r_{\max}$, which is at most $\beta$ and usually far below it: in the example above $r_{\max}$ is 0.50 / 0.30 and $1/r_{\max}$ is 0.60 against a $\beta$ of 0.75, and a single rare token with a ratio of 20 would drive it to 0.05. Speculative sampling gets to accept more because it does not retry the proposal; it falls back to the residual, a distribution it can compute because it has both probability vectors in hand (Appendix A.2).

The acceptance rate is the overlap of p and q

For a given prefix, the probability that a draft token is accepted is the overlap computed above. The paper states it through a divergence it defines, $D_{LK}(p,q) = \sum_x |p(x) - M(x)|$ with $M = (p+q)/2$, and proves in Lemma 3.3 that

The middle expression is the total variation distance between the two next-token distributions, a standard quantity in $[0,1]$: 0 when the draft agrees with the target exactly, 1 when they never put mass on the same token. The paper does not use the name.

$\beta$ changes from position to position. The prefix "the capital of France is" leaves both models near-certain of the next token and $\beta$ near 1; an open-ended position spreads both distributions and they overlap less. The paper's analysis makes one simplifying assumption: the $\beta$s along a generation are independent and identically distributed, with mean

$\alpha$ is a property of the two models and the task, and it can be measured without running the algorithm: generate text with the target, and at each position compute the overlap of the two next-token distributions. The paper does this over 10K tokens per setting (Table 3). Approximation models about two orders of magnitude smaller than the target land between 0.5 and 0.9: T5-small against T5-XXL gives 0.75 on translation and 0.65 on summarization at temperature 0; a 6M GPT-like model against a 97M one gives 0.88; LaMDA 100M against LaMDA 137B gives 0.61, and LaMDA 8B gives 0.75. Even a bigram table, which costs nothing to evaluate, reaches 0.20 on translation, and a unigram table 0.08.

Sharper distributions overlap more. On the T5 pairs argmax raises $\alpha$ over temperature 1 by 0.11 to 0.18 points, and on the LaMDA pairs by 0 to 0.04; the paper states the trend as holding for all models, but its own Table 3 has one exception, the 6M GPT-like draft at 0.88 with argmax against 0.89 at temperature 1. Overlap is measured between full distributions, and concentrating both on their top tokens removes the spread over the tail where two different models disagree most. Appendix A.5 pushes the same lever deliberately with a lenience factor $l$: multiply $q(x)$ by $l$ before the comparison, which accepts more and moves T5-small on translation at temperature 1 from 0.62 to 0.84 at $l=0.1$, at the cost of the exactness guarantee (no token can then be sampled more than $1/l$ times more often than the target would). Every headline number in the paper uses $l=1$.

Tokens per target run, equation (1)

With i.i.d. acceptances, the number of tokens one step produces is 1 plus the length of the accepted prefix, and the prefix is accepted token by token with probability $\alpha$ each until a failure or until all $\gamma$ are in. That is a geometric count capped at $\gamma$: the probability that the first $k$ drafts are all accepted is $\alpha^k$, so the expected number of tokens is

This is also the factor by which serial target runs shrink, and by which the weight and KV-cache reads shrink, since each run reads them once. At $\alpha = 0.75$ and $\gamma = 7$, the T5-small translation setting, (1) gives 3.60 tokens per target run. At $\alpha = 0.9$ and $\gamma = 10$ it gives 6.86. As $\gamma \to \infty$ the sum tends to $1/(1-\alpha)$, so $\alpha = 0.75$ can never yield more than 4 tokens per run on average however long the draft, and $\alpha = 0.9$ tops out at 10.

Figure 4 plots (1) against $\alpha$ for several draft lengths, and next to it the full distribution of tokens per run at the chosen setting: $\alpha^{k-1}(1-\alpha)$ for $k \le \gamma$ and $\alpha^\gamma$ for the clean sweep. At the default setting a run yields all 8 tokens 13% of the time and a single token 25% of the time.

The paper also notes an upper bound on what a smarter schedule could add: if an oracle chose $\gamma$ at each step to be exactly the number of drafts about to be accepted, the expected tokens per run would be the uncapped $1/(1-\alpha)$, and the authors estimate the walltime gain from such a schedule at up to about 60% over a fixed $\gamma$ for typical $c$ and $\alpha$, left as future work.

Walltime, the cost of the draft, and choosing γ

Let $T$ be the walltime of one target run and define the cost coefficient $c$ as the walltime of one draft run divided by $T$. One step of Algorithm 1 runs the draft $\gamma$ times and the target once, so it costs $T(c\gamma + 1)$, assuming the $\gamma+1$ target evaluations fit in one pass at no extra time, which Figure 1 justifies when the hardware has spare arithmetic. Dividing (1) by that cost gives Theorem 3.8, the expected walltime improvement:

Unlike $\alpha$, $c$ depends on the hardware and the implementation. The paper says $c$ stayed below 0.05 for drafts a couple of orders of magnitude smaller than the target, and was often close to 0; its own Table 4 lists 0.11 for T5-large, which is 14× smaller than the 11B target. The T5-small translation setting again: $\alpha = 0.75$, $\gamma = 7$, $c = 0.02$ give 3.60 / 1.14 = 3.16, which the paper rounds to 3.2× predicted against 3.4× measured. Setting $\gamma = 1$ in (5) gives $(1+\alpha)/(1+c)$, so whenever $\alpha > c$ the smallest draft length already helps (Corollary 3.9), and when $\alpha \le c$ no draft length does, because each extra draft costs at least as much time as its expected contribution.

$\gamma$ is an integer, so the paper picks it by evaluating (5) numerically. Longer drafts raise the numerator toward $1/(1-\alpha)$ but the denominator grows linearly, so the speedup peaks and then falls. The total arithmetic moves the other way. With $\hat c$ the draft's operations per token as a fraction of the target's, Theorem 3.11 gives the factor by which total operations increase,

because every step scores $\gamma+1$ positions with the target and only some of them turn into tokens; the rest is speculative work thrown away. Table 1 of the paper, with $c = \hat c = 0$: at $\alpha = 0.8$, $\gamma = 2$ gives 2.44× speed for 1.23× the operations, and $\gamma = 5$ gives 3.69× for 1.63×; at $\alpha = 0.9$, $\gamma = 10$ gives 6.86× for 1.60×. Figure 5 draws both curves against $\gamma$ and circles the best draft length. Push $c$ past $\alpha$ and the whole speedup curve drops under 1×.

The operations factor is why the method needs spare capacity. On the roofline of Figure 1 the extra positions are free because the arithmetic units were idle; on a server already saturated by large batches they are not idle, the extra operations cost real time, and (5) no longer describes the walltime, which the paper names as the method's main limitation.

T5-XXL: 2.3× to 3.4× with the same outputs

The walltime experiments use T5 version 1.1: T5-XXL (11B) as the target, and T5-large (800M), T5-base (250M), and T5-small (77M) as drafts, all existing checkpoints, fine-tuned on WMT English-German translation and on CNN/Daily Mail summarization. Batch size 1, one TPU v4, argmax (temperature 0) and standard sampling (temperature 1), timed against the T5X implementation. $\alpha$ was measured for each pair and $\gamma$ chosen from it.

T5-small wins in every setting: 3.4× and 2.6× on translation, 3.1× and 2.3× on summarization. It has the lowest $\alpha$ of the three drafts (0.75 against 0.80 and 0.82 on translation at temperature 0) but also the lowest cost ($c = 0.02$ against 0.04 and 0.11), and (5) is more sensitive to $c$ at these values: with $\gamma = 7$, the numerator of (5) is 4.42 for T5-large against 3.60 for T5-small, 23% more, while the denominator is 1.77 against 1.14, 55% more. The paper's rule of thumb is a draft about two orders of magnitude smaller than the target.

The predictions of (5) track the measurements to within a few tenths in most rows. The appendix names two sources for the rest: differences between the authors' implementation and the T5X baseline, and the i.i.d. assumption on $\beta$, which is only an approximation because acceptances cluster: easy stretches of text accept many drafts in a row and hard ones reject early. The average acceptance rate can stay at $\alpha$ while the number of tokens per run changes in both spread and expected value, so (1) evaluated at that $\alpha$ is off.

Cheaper drafts also work, at smaller gains. A bigram model, a table lookup with $c \approx 0$, has $\alpha \approx 0.2$ on translation, and (5) with $\gamma = 3$ gives 1.25×. The paper lists other zero-cost drafts it did not test: copying spans from the context when the output is likely to repeat it (summarization, chat turns that edit earlier text), non-autoregressive proposers that draft all $\gamma$ tokens in one call, and, as a theoretical curiosity, uniformly random tokens, which give a positive but tiny $\alpha$ for any target.

Where it does not help, and what came next

The method trades arithmetic for latency, so it needs idle arithmetic. It applies to the memory-bound regime of small batches, the regime of interactive serving, and not to a throughput-oriented server that already fills its matrix units with a batch of hundreds; every measurement in the paper is at batch size 1. It also needs a draft with a usable $\alpha$ and a small $c$ on the same hardware; Chen et al. at DeepMind, whose Chinchilla 70B result the intro mentioned, report that below a certain size a draft cannot be served efficiently enough on their 16-chip target setup, and they trained a 4B-parameter, 8-layer draft specifically for sampling latency. Beam search is only partly covered: Appendix A.4 sketches a version that keeps the exact beam-search result by running the draft with a wider beam and checking that the target's top-$w$ stays inside the draft's top-$u$, at some performance penalty, and the paper leaves it as future work.

The method spread because it asks nothing of the deployed model: no retraining, no architecture change, no change to the output distribution, and any draft with the same tokenizer. Chen and colleagues at DeepMind published the same accept rule and residual in February 2023 for Chinchilla 70B, with a speedup of 1.92× to 2.46×. Later work replaced the separate draft model with extra prediction heads on the target, with retrieved n-grams, or with the target's own early layers, and speculative decoding is now a standard option in inference libraries, including the Hugging Face implementation cited in the Provenance panel, and, per Google's 2024 retrospective, in the serving stack behind AI Overviews in Search.

The paper closes with the observation that speculative sampling is more general than decoding: given any two slow functions where the first produces a distribution and the second consumes a sample from it, the same accept/reject rule lets the two run concurrently on a cheap guess of the sample, with the exact distribution preserved, a pattern the authors point at physics simulation and at reinforcement learning, where a large policy proposes actions and a simulator consumes them.