# 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.

Source: https://www.mlfoundry.in/learn/speculative-decoding  
Section: Deep Learning › Large Language Models (LLMs)  
Level: advanced · 15 min read · updated 2026-10-13

**Speculative decoding:** is a way to sample from a large autoregressive model $M_p$ faster without changing its output distribution. A small **draft** model $M_q$ proposes $\gamma$ tokens one at a time. The target $M_p$ then scores all of them in **one** forward pass. Each draft token $x$ is accepted with probability $\min(1, p(x)/q(x))$. At the first rejection, a replacement is sampled from the normalised residual $\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.

> Figure: 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 $p$ and the draft's is $q$. The draft samples $x\sim q$. Then:

$$
\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,\ q$: target and draft distributions at the same position, given the same prefix (temperature, top-p etc. applied to both)
- $p(x)\ge q(x)$: the draft *under*-proposes $x$: always accept
- $p(x)<q(x)$: the draft *over*-proposes $x$: keep it only a fraction $p/q$ of the time
- $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 $p$ that the accepted draws are missing.

## Why the output is exactly p

Write $\alpha=\sum_y\min(p(y),q(y))$. The probability that a draft is accepted is $\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-\alpha$. The residual's normaliser is $\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 $x$ can come out:

$$
\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)
$$

- $\alpha=\sum_y\min(p,q)$: acceptance probability; equals $1-\mathrm{TV}(p,q)$, one minus the total-variation distance
- $\min+\max(0,\cdot)$: for any $a,b$: $\min(a,b)+\max(0,a-b)=a$

The argument is per position and holds for any $q$, 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 $p$. By induction the whole sequence is distributed exactly as if $M_p$ had generated it alone. In greedy decoding, $p$ and $q$ 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.

$$
\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 $\mathbb E[\sum\min(p,q)]$, measured on real prompts
- $c$: cost of one draft step relative to one target step; one speculative step costs $\gamma c+1$ target-step equivalents
- $\gamma\to\infty$: tokens per call saturate at $1/(1-\alpha)$; at $\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 $c$ to the denominator. So there is an optimal $\gamma$ that rises with $\alpha$ and falls with $c$. The price is extra arithmetic: the target scores $\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\sim U(0,1)$, accept iff $r<p(x)/q(x)$; one uniform per draft token
- **Target pass:** one forward over $\gamma$ drafts returns $\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: $p$ and $q$ 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

> Figure: 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)$ and draft $q=(0.3,0.5,0.1,0.1)$ over tokens A, B, C, D.

Acceptance and residual for each token (computed in Python)

| token | p | q | min(p, q) | accept prob. min(1, p/q) | max(0, p − q) | residual p′ |
| --- | --- | --- | --- | --- | --- | --- |
| A | 0.50 | 0.30 | 0.30 | 1 | 0.20 | 0.8 |
| B | 0.30 | 0.50 | 0.30 | 0.6 | 0 | 0 |
| C | 0.15 | 0.10 | 0.10 | 1 | 0.05 | 0.2 |
| D | 0.05 | 0.10 | 0.05 | 0.5 | 0 | 0 |
| sum | 1 | 1 | α = 0.75 |  | 0.25 = 1 − α | 1 |

**Checking the output and the speedup**

1. The 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.6$.
2. A rejection happens with probability $1-\alpha=0.25$ in total: $0.5\cdot0.4$ from B plus $0.1\cdot0.5$ from D. The replacement is A with probability $0.2/0.25=0.8$ and C with $0.05/0.25=0.2$. B and D are never resampled.
3. Output probabilities: A $=0.30+0.25\cdot0.8=0.50$, B $=0.30$, C $=0.10+0.25\cdot0.2=0.15$, D $=0.05$. This is exactly $p$.
4. With $\gamma=4$ and $\alpha=0.75$: $\mathbb E[\text{tokens}]=(1-0.75^5)/(1-0.75)=(1-0.2373)/0.25=3.0508$ tokens per target call.
5. With a draft costing $c=0.1$: speedup $=3.0508/(4\cdot0.1+1)=2.179\times$. Trying other lengths gives $1.591$ ($\gamma=1$), $2.103$ ($\gamma=3$), $2.192$ ($\gamma=5$, the optimum) and $2.166$ ($\gamma=6$).

```python
import numpy as np

rng = np.random.default_rng(0)
V = 50                                    # toy vocabulary
logits_p = rng.normal(0, 2.0, (V, V))     # target: a bigram model p(x_t | x_{t-1})
logits_q = logits_p + rng.normal(0, 1.0, (V, V))   # draft: a noisier copy of it

def softmax(z):
    z = z - z.max(-1, keepdims=True)
    e = np.exp(z)
    return e / e.sum(-1, keepdims=True)

P, Q = softmax(logits_p), softmax(logits_q)   # row i = next-token distribution after token i

def target_forward(ctx):                  # ONE call scores every position of ctx in parallel
    return P[np.array(ctx)]               # shape (len(ctx), V): p(. | ctx[:j+1]) for each j

def speculative_step(ctx, gamma, rng):
    """Draft gamma tokens with q, verify with one target call. Returns the new tokens."""
    drafts, qs, last = [], [], ctx[-1]
    for _ in range(gamma):                # serial, but the draft is cheap
        q = Q[last]
        last = rng.choice(V, p=q)
        drafts.append(last); qs.append(q)
    ps = target_forward(ctx + drafts)[len(ctx) - 1:]   # p for positions 1..gamma+1
    out = []
    for i, x in enumerate(drafts):
        p, q = ps[i], qs[i]
        if rng.random() < min(1.0, p[x] / q[x]):       # accept with prob min(1, p/q)
            out.append(x)
            continue
        resid = np.maximum(p - q, 0.0)                 # reject: resample from norm(max(0, p - q))
        out.append(rng.choice(V, p=resid / resid.sum()))
        return out
    out.append(rng.choice(V, p=ps[gamma]))             # all accepted: one bonus token from p
    return out

gamma, calls, emitted = 4, 0, 0
first = np.zeros(V)                       # distribution of the first token after context [7]
for _ in range(20000):
    new = speculative_step([7], gamma, rng)
    calls += 1; emitted += len(new); first[new[0]] += 1

alpha = np.minimum(P[7], Q[7]).sum()      # acceptance rate of the first draft after token 7
alpha_avg = np.minimum(P, Q).sum(-1).mean()
print(f"alpha after token 7: {alpha:.3f}, mean alpha over contexts: {alpha_avg:.3f}")  # 0.530, 0.652
print(f"tokens per target call: {emitted / calls:.3f}")                                 # 2.163
print(f"TV(first token, p(.|7)) = {0.5 * np.abs(first / first.sum() - P[7]).sum():.4f}")  # 0.0102
# 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 $k$ predicts the token $k+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 $p$.

**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.

> **Batch size eats the speedup:** The free lunch is spare compute during memory-bound decoding. In a server running large batches, decoding is already closer to compute-bound. There the $\gamma+1$ positions per sequence are real extra work, and rejected tokens waste it. Reported speedups are mostly for batch size 1 or small batches. At high load the gain shrinks and can turn into a slowdown, which is why serving engines enable it selectively.

> **Lossless, whatever the draft:** The proof above never uses any property of $q$. A terrible draft lowers $\alpha$ and therefore the speed, but the output is still exactly $p$. This separates correctness from efficiency. You can tune, swap, quantise or prune the draft freely, and only throughput changes. Contrast this with **Quantization** or **Pruning** of the target itself, which change what it samples.

> **Same sampling settings on both sides:** $p$ and $q$ must be the distributions actually sampled from, after temperature, top-k and top-p, and over the same vocabulary. Accepting with raw-logit $p$ but sampling from a truncated $p$ breaks the guarantee. Numerical differences also matter: the target's batched verification pass can differ in the last bits from a one-token pass, so bit-identical greedy outputs are not guaranteed in floating point, even though the distributions agree.

**Strengths**

- 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

**Limitations**

- Extra compute: $\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

- **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.

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

- A. It is always accepted, because the draft proposed it
- B. It is accepted with probability 0.25; otherwise a replacement is drawn from norm(max(0, p − q))
- C. It is accepted with probability 0.1
- D. It is always rejected because p(x) < q(x)

**Answer:** B. It is accepted with probability 0.25; otherwise a replacement is drawn from norm(max(0, p − q)) — The acceptance probability is $\min(1,p/q)=0.1/0.4=0.25$. On rejection, the replacement comes from the residual, which puts zero mass on $x$ since $p(x)<q(x)$. Overall, $x$ comes out with probability $q(x)\cdot0.25=0.1=p(x)$.

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

- A. 0.8
- B. 4
- C. 5
- D. Unbounded: it grows linearly with γ

**Answer:** C. 5 — $\mathbb E=(1-\alpha^{\gamma+1})/(1-\alpha)\to1/(1-\alpha)=1/0.2=5$ as $\gamma\to\infty$. Every extra draft position is reached only if all earlier ones passed, so its contribution $\alpha^{\gamma}$ shrinks geometrically.

**Key points**

- 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)$. At the first rejection, resample from $\max(0,p-q)/(1-\alpha)$ and stop. If all pass, add a bonus token from $p$.
- $\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 $\alpha=\sum\min(p,q)=1-\mathrm{TV}(p,q)$: tokens per call $=(1-\alpha^{\gamma+1})/(1-\alpha)$, speedup $=$ that $/(\gamma c+1)$.
- Medusa, EAGLE, lookahead decoding and prompt lookup replace the separate draft model. Gains shrink at large batch sizes.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
