Speculative decoding

Speculative decoding (Leviathan et al.; Chen et al., 2023) lets a cheap draft propose γ tokens that the target checks in one pass, accepting each with prob. min(1, p/q) and resampling a rejection from norm(max(0, p − q)). Output is exactly p; each call yields (1 − α^{γ+1})/(1 − α) tokens.

15 min read1431 wordsadvanced0 viewsupdated 2026-10-13

Definition

Speculative decoding is a way to sample from a large autoregressive model MpM_p faster without changing its output distribution. A small draft model MqM_q proposes γ\gamma tokens one at a time. The target MpM_p then scores all of them in one forward pass. Each draft token xx is accepted with probability min⁡(1,p(x)/q(x))\min(1, p(x)/q(x)). At the first rejection, a replacement is sampled from the normalised residual max⁡(0,p−q)\max(0,p-q) and the rest is discarded. If all γ\gamma drafts pass, one bonus token comes from the target's last distribution. The method was published independently by Leviathan, Kalman and Matias, "Fast Inference from Transformers via Speculative Decoding" (Google, ICML 2023, arXiv November 2022), and by Chen, Borgeaud, Irving, Lespiau, Sifre and Jumper, "Accelerating Large Language Model Decoding with Speculative Sampling" (DeepMind, February 2023).

A Decoder-only transformer generates one token per forward pass, and each pass depends on the previous one. At small batch sizes that pass is limited by memory bandwidth, not arithmetic. Every step streams all the weights and the KV cache from HBM to compute a single new position. Running the same pass over 5 positions instead of 1 costs almost the same wall-clock time, because the weights are read once either way. The GPU has spare arithmetic and nothing to spend it on.

Speculative decoding spends that spare arithmetic on guesses. Many next tokens are easy: the end of a common word, a closing bracket, a phrase copied from the prompt. A model 10 to 100 times smaller predicts these as well as the big one. If the draft is right, the target confirms several tokens in the time it normally takes to produce one. If it is wrong, the target's own pass already contains the information needed to correct it, so at least one token still comes out of every call.

The idea has a precursor. Stern, Shazeer and Uszkoreit, "Blockwise Parallel Decoding for Deep Autoregressive Models" (NeurIPS 2018), added heads that predict several future tokens and kept the longest prefix that agreed with greedy decoding. That works only for greedy (argmax) decoding. The 2023 papers extended the idea to sampling with a rejection rule that leaves the target distribution exactly intact. That is what made it practical for chat models sampled at temperature above zero.

one speculative step, γ = 4: draft serially, verify in one parallel pass, keep a prefixprefix: “the cat”draft model M_qγ cheap serial stepsx1 = satq = 0.60x2 = onq = 0.50x3 = aq = 0.30x4 = matq = 0.45target model M_p1 forward, γ + 1 outputsparallel forward on [the cat, sat, on, a, mat]p1 = 0.72p2 = 0.40p3 = 0.06p4p5verify left → rightaccept w.p. min(1, p/q)min(1,p/q)= 1.00r = —✓ acceptmin(1,p/q)= 0.80r = 0.31✓ acceptmin(1,p/q)= 0.20r = 0.67✗ rejectdiscardedafter rejectbonus ~ p5only if all4 acceptedx3′ = the ~ norm(max(0, p3 − q3))emittedthis target callsatonthe3 tokens for 1 target call;next step drafts after “the”E[tokens/call] = (1 − α^(γ+1))/(1 − α), α = Σ min(p, q); the output is distributed exactly as p
fig.One speculative step with γ = 4. The draft proposes “sat, on, a, mat” serially. The target then scores the prefix and all four drafts in one parallel forward, producing p₁ … p₅. “sat” has p ≥ q and is always accepted. “on” passes with probability 0.40/0.50 = 0.80 (uniform draw r = 0.31). “a” has p/q = 0.06/0.30 = 0.20 and fails (r = 0.67). Its replacement is drawn from norm(max(0, p₃ − q₃)), and “mat” is dropped because it was conditioned on the rejected token. This call emits three tokens. Had all four drafts passed, a fifth (bonus) token would have been drawn from p₅.

The acceptance rule

Fix one position. The target's next-token distribution there is pp and the draft's is qq. The draft samples x∼qx\sim q. Then:

accept x with prob. min⁡ ⁣(1,p(x)q(x)),else sample x′∼p′(⋅)=max⁡(0, p(⋅)−q(⋅))∑ymax⁡(0, p(y)−q(y))\text{accept } x \text{ with prob. } \min\!\Big(1,\frac{p(x)}{q(x)}\Big),\qquad \text{else sample } x'\sim p'(\cdot)=\frac{\max\big(0,\,p(\cdot)-q(\cdot)\big)}{\sum_{y}\max\big(0,\,p(y)-q(y)\big)}
p, qp,\ q
target and draft distributions at the same position, given the same prefix (temperature, top-p etc. applied to both)
p(x)≥q(x)p(x)\ge q(x)
the draft under-proposes xx: always accept
p(x)<q(x)p(x)<q(x)
the draft over-proposes xx: keep it only a fraction p/qp/q of the time
p′p'
the residual distribution: the probability mass the target wants and the draft did not supply

This is rejection sampling with a twist. Ordinary rejection sampling throws away rejected draws and tries again, which would need another target call. Here the rejected mass is replaced in one shot by sampling from exactly the part of pp that the accepted draws are missing.

Why the output is exactly p

Write α=∑ymin⁡(p(y),q(y))\alpha=\sum_y\min(p(y),q(y)). The probability that a draft is accepted is ∑xq(x)min⁡(1,p(x)/q(x))=∑xmin⁡(q(x),p(x))=α\sum_x q(x)\min(1,p(x)/q(x))=\sum_x\min(q(x),p(x))=\alpha. So a rejection happens with probability 1−α1-\alpha. The residual's normaliser is ∑ymax⁡(0,p(y)−q(y))=∑y(p(y)−min⁡(p(y),q(y)))=1−α\sum_y\max(0,p(y)-q(y))=\sum_y\big(p(y)-\min(p(y),q(y))\big)=1-\alpha. Now add up the two ways token xx can come out:

Pr⁡[out=x]=q(x)min⁡ ⁣(1,p(x)q(x))⏟drafted and accepted+(1−α) max⁡(0,p(x)−q(x))1−α⏟rejected, then resampled=min⁡(p(x),q(x))+max⁡(0,p(x)−q(x))=p(x)\Pr[\text{out}=x]=\underbrace{q(x)\min\!\Big(1,\tfrac{p(x)}{q(x)}\Big)}_{\text{drafted and accepted}}+\underbrace{(1-\alpha)\,\frac{\max(0,p(x)-q(x))}{1-\alpha}}_{\text{rejected, then resampled}}=\min(p(x),q(x))+\max(0,p(x)-q(x))=p(x)
α=∑ymin⁡(p,q)\alpha=\sum_y\min(p,q)
acceptance probability; equals 1−TV(p,q)1-\mathrm{TV}(p,q), one minus the total-variation distance
min⁡+max⁡(0,⋅)\min+\max(0,\cdot)
for any a,ba,b: min⁡(a,b)+max⁡(0,a−b)=a\min(a,b)+\max(0,a-b)=a

The argument is per position and holds for any qq, however bad. A poor draft makes generation slower, never wrong. Positions after the first rejection are discarded because they were conditioned on a token that did not survive. Every kept token was conditioned on a prefix that is itself an exact sample from pp. By induction the whole sequence is distributed exactly as if MpM_p had generated it alone. In greedy decoding, pp and qq are one-hot, and the rule reduces to "accept while the draft equals the target's argmax".

How many tokens per target call

Leviathan et al. analyse the simple case where each draft is accepted independently with the same probability α\alpha. The number of accepted drafts before the first rejection is a geometric variable capped at γ\gamma. One more token always comes out: either the residual sample or the bonus.

E[#tokens per target call]=∑k=0γαk=1−αγ+11−α,walltime improvement=1−αγ+1(1−α)(γc+1)\mathbb E[\#\text{tokens per target call}]=\sum_{k=0}^{\gamma}\alpha^{k}=\frac{1-\alpha^{\gamma+1}}{1-\alpha},\qquad \text{walltime improvement}=\frac{1-\alpha^{\gamma+1}}{(1-\alpha)(\gamma c+1)}
γ\gamma
draft length: tokens proposed per step
α\alpha
expected acceptance rate E[∑min⁡(p,q)]\mathbb E[\sum\min(p,q)], measured on real prompts
cc
cost of one draft step relative to one target step; one speculative step costs γc+1\gamma c+1 target-step equivalents
γ→∞\gamma\to\infty
tokens per call saturate at 1/(1−α)1/(1-\alpha); at α=0.8\alpha=0.8 that is 5

The trade-off in γ\gamma is visible in the formula. A longer draft adds a term αγ\alpha^{\gamma} to the numerator, which shrinks geometrically. It also adds a fixed cc to the denominator. So there is an optimal γ\gamma that rises with α\alpha and falls with cc. The price is extra arithmetic: the target scores γ+1\gamma+1 positions per call, and the rejected ones are wasted work. The method pays off when spare compute is free, which is when decoding is memory-bound.

From the papers

Leviathan et al. 2023
T5-XXL (11B) target with smaller T5 drafts on translation and summarisation; reported a 2X–3X speedup over the standard T5X implementation, with identical outputs
Chen et al. 2023
Chinchilla 70B target and a 4B-parameter draft model; 2–2.5× decoding speedup in a distributed setup, with sample quality unchanged and no change to the target model
Acceptance test
r∼U(0,1)r\sim U(0,1), accept iff r<p(x)/q(x)r<p(x)/q(x); one uniform per draft token
Target pass
one forward over γ\gamma drafts returns γ+1\gamma+1 distributions; the KV cache of rejected positions is rolled back in both models
Draft choices
a smaller model of the same family sharing the tokenizer (required: pp and qq must be over the same vocabulary); n-grams copied from the prompt (prompt lookup); extra heads on the target (Medusa); a light feature-level head (EAGLE)
Hugging Face
"assisted generation": model.generate(..., assistant_model=draft); prompt_lookup_num_tokens=k uses n-grams from the prompt as drafts
accept x ~ q with prob. min(1, p(x)/q(x)); on reject resample from norm(max(0, p − q))target p vs draft q (w = 0.50)theacatdogsatranon.— p · ┆ q · ■ min(p,q) · ■ p − q > 0α = Σ min(p, q) = 0.7550 = 1 − TV(p, q)emitted tokens, 4000 steps (12361 tokens)theacatdogsatranon.TV(emitted, p) = 0.0057 (sampling noise ≈ 0.01)exact per-position output: TV to p = 0.0000 (equals p)per target call, vs draft length γ0123412345678910● E[tokens] · ● speedup · ○ simulatedE = (1 − α^(γ+1)) / (1 − α)3.080simulated tokens / call3.090speedup = E / (γc + 1), c = 0.052.567×best γ for this α and cγ = 7 (2.704×)drafted tokens kept8361 / 16000 = 0.523q = (1 − w)·p + w·u, the same p and q at every position (i.i.d. acceptances, as the formula assumes)each checked draft passes w.p. α, but drafts after a rejection are thrown away
on rejection
fig.One fixed target distribution p over eight words and a draft q = (1 − w)·p + w·u that drifts toward a different distribution u. The same p and q are used at every position, so acceptances are i.i.d. and the formula applies exactly. The simulator runs the real algorithm for 4000 steps. At the default (w = 0.50, γ = 4, c = 0.05), α = Σ min(p, q) = 0.7550. The formula gives 3.080 tokens per target call and the simulation 3.090 (12,361 tokens). The emitted tokens sit within sampling noise of p (TV 0.0057), and the exact output distribution equals p. The walltime speedup is 3.080 / (4·0.05 + 1) = 2.567×, and the best draft length is γ = 7 at 2.704×. Only 8361 of the 16,000 drafted tokens are kept. Switch the rejection branch to “resample from p” and the output is biased (exact TV 0.0658): “dog” comes out with probability 0.149 instead of 0.12 because the draft over-proposes it. At w = 0 the draft is perfect: α = 1, every draft passes and 5.000 tokens come per call. At w = 1, α = 0.51, only 1.970 tokens per call, and the best γ drops to 3 (1.655×). A costlier draft (c = 0.2) also moves the optimum to γ = 3 (1.722×), while a free draft (c = 0) makes longer drafts always better.

Worked example: one position, four tokens

Take a 4-token vocabulary with target p=(0.5,0.3,0.15,0.05)p=(0.5,0.3,0.15,0.05) and draft q=(0.3,0.5,0.1,0.1)q=(0.3,0.5,0.1,0.1) over tokens A, B, C, D.

tokenpqmin(p, q)accept prob. min(1, p/q)max(0, p − q)residual p′
A0.500.300.3010.200.8
B0.300.500.300.600
C0.150.100.1010.050.2
D0.050.100.050.500
sum11α = 0.750.25 = 1 − α1
Acceptance and residual for each token (computed in Python)

Checking the output and the speedup

  1. 1The draft over-proposes B and D, so those are the only tokens that can be rejected. If the draft says B, it survives with probability 0.3/0.5=0.60.3/0.5=0.6.
  2. 2A rejection happens with probability 1−α=0.251-\alpha=0.25 in total: 0.5⋅0.40.5\cdot0.4 from B plus 0.1⋅0.50.1\cdot0.5 from D. The replacement is A with probability 0.2/0.25=0.80.2/0.25=0.8 and C with 0.05/0.25=0.20.05/0.25=0.2. B and D are never resampled.
  3. 3Output probabilities: A =0.30+0.25⋅0.8=0.50=0.30+0.25\cdot0.8=0.50, B =0.30=0.30, C =0.10+0.25⋅0.2=0.15=0.10+0.25\cdot0.2=0.15, D =0.05=0.05. This is exactly pp.
  4. 4With γ=4\gamma=4 and α=0.75\alpha=0.75: E[tokens]=(1−0.755)/(1−0.75)=(1−0.2373)/0.25=3.0508\mathbb E[\text{tokens}]=(1-0.75^5)/(1-0.75)=(1-0.2373)/0.25=3.0508 tokens per target call.
  5. 5With a draft costing c=0.1c=0.1: speedup =3.0508/(4⋅0.1+1)=2.179×=3.0508/(4\cdot0.1+1)=2.179\times. Trying other lengths gives 1.5911.591 (γ=1\gamma=1), 2.1032.103 (γ=3\gamma=3), 2.1922.192 (γ=5\gamma=5, the optimum) and 2.1662.166 (γ=6\gamma=6).
python
1import numpy as np
2
3rng = np.random.default_rng(0)
4V = 50 # toy vocabulary
5logits_p = rng.normal(0, 2.0, (V, V)) # target: a bigram model p(x_t | x_{t-1})
6logits_q = logits_p + rng.normal(0, 1.0, (V, V)) # draft: a noisier copy of it
7
8def softmax(z):
9 z = z - z.max(-1, keepdims=True)
10 e = np.exp(z)
11 return e / e.sum(-1, keepdims=True)
12
13P, Q = softmax(logits_p), softmax(logits_q) # row i = next-token distribution after token i
14
15def target_forward(ctx): # ONE call scores every position of ctx in parallel
16 return P[np.array(ctx)] # shape (len(ctx), V): p(. | ctx[:j+1]) for each j
17
18def speculative_step(ctx, gamma, rng):
19 """Draft gamma tokens with q, verify with one target call. Returns the new tokens."""
20 drafts, qs, last = [], [], ctx[-1]
21 for _ in range(gamma): # serial, but the draft is cheap
22 q = Q[last]
23 last = rng.choice(V, p=q)
24 drafts.append(last); qs.append(q)
25 ps = target_forward(ctx + drafts)[len(ctx) - 1:] # p for positions 1..gamma+1
26 out = []
27 for i, x in enumerate(drafts):
28 p, q = ps[i], qs[i]
29 if rng.random() < min(1.0, p[x] / q[x]): # accept with prob min(1, p/q)
30 out.append(x)
31 continue
32 resid = np.maximum(p - q, 0.0) # reject: resample from norm(max(0, p - q))
33 out.append(rng.choice(V, p=resid / resid.sum()))
34 return out
35 out.append(rng.choice(V, p=ps[gamma])) # all accepted: one bonus token from p
36 return out
37
38gamma, calls, emitted = 4, 0, 0
39first = np.zeros(V) # distribution of the first token after context [7]
40for _ in range(20000):
41 new = speculative_step([7], gamma, rng)
42 calls += 1; emitted += len(new); first[new[0]] += 1
43
44alpha = np.minimum(P[7], Q[7]).sum() # acceptance rate of the first draft after token 7
45alpha_avg = np.minimum(P, Q).sum(-1).mean()
46print(f"alpha after token 7: {alpha:.3f}, mean alpha over contexts: {alpha_avg:.3f}") # 0.530, 0.652
47print(f"tokens per target call: {emitted / calls:.3f}") # 2.163
48print(f"TV(first token, p(.|7)) = {0.5 * np.abs(first / first.sum() - P[7]).sum():.4f}") # 0.0102
49# For scale: 20000 direct samples from p(.|7) have TV 0.0148 to p, so the gap is pure noise.
Speculative sampling with toy bigram models in numpy (run; the printed values are from that run)

In the toy run, α\alpha differs by context, from 0.530 after token 7 to 0.652 on average, so the i.i.d. formula is only a guide. Real deployments measure α\alpha on their own traffic. Code, structured output and summarisation of the prompt accept many more drafts than open-ended creative text.

Beyond a separate draft model

A separate draft has costs. It must share the tokenizer, it uses memory, it keeps its own KV cache, and its predictions are made without the target's hidden state. Several later methods draft from the target itself.

Medusa (Cai et al., ICML 2024) adds a few extra decoding heads on the target's last hidden state. Head kk predicts the token k+1k+1 positions ahead. Their top candidates form a tree, and tree attention verifies many candidate continuations in one pass with a custom attention mask. Medusa-1 trains only the heads on a frozen backbone and reports more than 2.2× speedup. Medusa-2 fine-tunes the backbone jointly and reports 2.3–3.6×. Medusa also proposes a "typical acceptance" rule that accepts plausible tokens without the exact rejection test. That is faster but no longer exactly pp.

EAGLE (Li, Wei, Zhang and Zhang, ICML 2024) drafts at the feature level. A single light transformer layer predicts the target's next second-to-top-layer feature from the current feature and the already-sampled next token. The target's own LM head then turns it into a token. Feeding in the sampled token removes the uncertainty about which branch the sequence took. It keeps the exact acceptance rule and verifies a tree of drafts. EAGLE-2 makes the tree shape depend on the draft's confidence.

Lookahead decoding (Fu, Bailis, Stoica and Zhang, ICML 2024) needs no draft at all. It runs Jacobi-style fixed-point iterations on a window of future positions, collects the n-grams these iterations produce in a pool, and verifies matching n-grams in the same forward pass. Prompt lookup is the simplest version: copy the n-gram that followed the current suffix earlier in the prompt. This works very well for editing and retrieval-augmented answers.

Use when

  • +Exactly the target's output distribution, for sampling as well as greedy decoding
  • +No change to the target model's weights or training
  • +Typical 2–3× lower latency for single-stream decoding when α\alpha is high
  • +Works with any draft source: a small model, prompt n-grams, extra heads or a feature-level head

Avoid when

  • −Extra compute: γ+1\gamma+1 target positions per call, with rejected positions wasted
  • −Gains shrink at large batch sizes where decoding is compute-bound
  • −A separate draft needs the same tokenizer, extra memory and its own KV cache
  • −Speed depends on α\alpha, which varies by task and prompt; creative sampling at high temperature accepts less

Where it's used

Interactive chat latency

Lower time per output token for single users, where decoding is memory-bound.

Code completion and editing

Highly predictable continuations and copied spans give high acceptance; prompt lookup is especially effective.

Serving engines

vLLM, TensorRT-LLM and Hugging Face TGI support draft models, n-gram drafting and EAGLE- or Medusa-style heads.

Check yourself

A draft token x has q(x) = 0.4 while the target gives p(x) = 0.1. What happens?

Check yourself

With α = 0.8 and a free draft (c = 0), how many tokens per target call can you expect at most, however long the draft?

Remember

  • ✓A cheap draft proposes γ\gamma tokens. The target scores them all in one memory-bound forward pass, which costs about the same as scoring one token.
  • ✓Accept each draft with prob. min⁡(1,p/q)\min(1,p/q). At the first rejection, resample from max⁡(0,p−q)/(1−α)\max(0,p-q)/(1-\alpha) and stop. If all pass, add a bonus token from pp.
  • ✓Pr⁡[out=x]=min⁡(p,q)+max⁡(0,p−q)=p(x)\Pr[\text{out}=x]=\min(p,q)+\max(0,p-q)=p(x): the output is exactly the target's distribution for any draft.
  • ✓With acceptance rate α=∑min⁡(p,q)=1−TV(p,q)\alpha=\sum\min(p,q)=1-\mathrm{TV}(p,q): tokens per call =(1−αγ+1)/(1−α)=(1-\alpha^{\gamma+1})/(1-\alpha), speedup == that /(γc+1)/(\gamma c+1).
  • ✓Medusa, EAGLE, lookahead decoding and prompt lookup replace the separate draft model. Gains shrink at large batch sizes.
← back to Deep Learning roadmap