Part IV · Faster & cheaperChapter 17 / 37

Speculative Decoding

Guess several tokens cheaply, then let the big model check them all in a single pass. Same output distribution, often 2–3× faster decoding.

Decode is slow for a strange reason. The GPU is mostly idle. Every step streams all the weights from memory to produce one token per sequence, and the tensor cores spend most of that time waiting for data. Speculative decoding puts that spare compute to work.

The core trick

Checking a guess is cheaper than producing one. A forward pass over 5 tokens costs almost the same as a pass over 1 token, because both are dominated by reading the weights (see the roofline). So we:

Let a cheap drafter guess the next k tokens.
Run the target model once over the context plus all k guesses. Thanks to the causal mask, that single pass yields the target’s own prediction at every one of the k + 1 positions.
Keep the longest prefix where the draft agrees with the target. At the first disagreement, take the target’s token instead. If everything matched, take the bonus token from the last position for free.

LiveDraft → verify → accept

Each round always makes progress: at worst, 0 drafts are accepted and you still get the target’s own token, the same as a normal decode step. At best you get k + 1 tokens for one target pass. The wall-clock bar shows the effect: a few big passes plus tiny draft passes, instead of one big pass per token.

Why it’s lossless, even when sampling

With greedy decoding, “accept if the draft equals the target’s argmax” obviously reproduces the target’s output. With sampling (temperature > 0) we need more care: we want the output to be distributed exactly like the target’s distribution $p$ , while proposals come from the draft’s distribution $q$ .

The fix is a small rejection-sampling rule. For a drafted token $x$ :

\text{accept } x \text{ with probability } \min\!\left(1, \frac{p(x)}{q(x)}\right)

On rejection, sample a replacement from the residual distribution

r(x) = \frac{\max(0,\; p(x) - q(x))}{\sum_{y} \max(0,\; p(y) - q(y))}

Tokens the draft under-proposes are always accepted. Tokens it over-proposes are thinned down, and the residual exactly fills in the missing mass. The probability of accepting a draft is $\alpha = \sum_x \min(p(x), q(x))$ , the overlap of the two distributions.

ExploreRejection sampling keeps the target distribution intact

Slide the draft quality down and the overlap (green) shrinks, so acceptance drops. Press Sample and the output histogram (amber) still matches p. A bad drafter makes you slower, never wrong.

How many tokens do you get per pass?

Assume each draft token is accepted independently with probability $\alpha$ . The expected number of tokens per target pass, including the correction or bonus token, is

\mathbb{E}[\text{tokens}] = \frac{1 - \alpha^{k+1}}{1 - \alpha}

With $\alpha = 0.8$ and $k = 4$ that is about 3.4 tokens per pass. The drafter costs time too. If one draft step costs a fraction $c$ of a target step, then at batch size 1:

\text{speedup} \approx \frac{\mathbb{E}[\text{tokens}]}{1 + k\,c}

Longer drafts help only while α is high, because each extra guess is less likely to survive. That is why most deployments use k between 2 and 6.

Where the drafts come from

Family	How it drafts	Draft cost	Notes
Separate draft model	A small model from the same family (e.g. 1B for a 70B)	Medium	Needs the same tokenizer; extra weights and KV cache to manage
Draft heads: EAGLE, Medusa	Light heads on the target’s own hidden states predict future tokens	Low	High acceptance; heads must be trained for each target model
MTP (multi-token prediction)	Model trained with extra next-next-token modules, reused as drafter	Low	Comes “built in” with some models (e.g. DeepSeek-V3)
n-gram / prompt lookup	Copy continuations of matching n-grams from the prompt or history	~zero	Great for code edits, RAG, summarization; useless for free text
Suffix decoding	Match against a cache of earlier outputs	~zero	Shines on repetitive, agentic workloads

The catch: it needs idle compute

Verification is “free” only while decode is memory-bound. In a big batch, the target already does real math for every sequence. Verifying k + 1 tokens per sequence then multiplies the compute, and rejected drafts become pure waste.

CalculatorSpeedup collapses as the batch fills the GPU

A simple roofline model of Llama 3.1 8B on one H100. Each step costs max(time to read weights, time to compute B × (k+1) tokens). Below the knee, extra verified tokens are nearly free; above it, every rejected draft burns compute that other users needed. Try a high batch with a long draft and watch the speedup fall below 1×.

What the engine has to handle

KV cache for rejected tokens. The target writes K/V for all k + 1 positions during verification. Slots for rejected tokens must be rolled back or overwritten. With paged KV this just means moving the sequence’s length pointer back.
Tree drafts. Instead of one chain, propose a small tree of alternatives and verify every branch in one pass with a tree-shaped attention mask. More candidates per pass means more accepted tokens.
Scheduling. Verification steps carry k + 1 tokens per sequence, which eats into the token budget shared with prefill chunks.
Draft model state. A separate draft model needs its own weights and KV cache in GPU memory, which competes with the target’s KV cache.

Interview checkTry answering before you expand.

coreWhy can the target verify k tokens for roughly the cost of generating one?

Decode is memory-bandwidth-bound: each step’s time is dominated by streaming the weights. A pass over k+1 tokens reads the same weights once and does k+1 times the math, which still fits in the idle compute. The causal mask gives the target’s prediction at every position from that one pass.

coreDoes speculative decoding change the model's outputs?

No, up to floating-point noise. With greedy decoding, accepted tokens equal the target’s argmax. With sampling, the min(1, p/q) acceptance rule plus resampling from the residual max(0, p − q) gives output distributed exactly as p.

midAcceptance rate 0.7, k = 4. Expected tokens per target pass?

(1 − 0.7⁵) / (1 − 0.7) = (1 − 0.168) / 0.3 ≈ 2.77 tokens. With a drafter costing 5% of a target step: speedup ≈ 2.77 / (1 + 4 × 0.05) ≈ 2.3×.

midWhy might speculative decoding hurt throughput at high load?

In big batches decode is closer to compute-bound, so verifying k+1 tokens per sequence costs real FLOPs. Rejected drafts waste capacity that could have served other users, and drafter passes add more time. Many engines reduce k or disable speculation as the batch grows.

seniorCompare a separate draft model with EAGLE/Medusa-style heads.

A separate draft model is generic but adds weights, its own KV cache, scheduling complexity, and must share the tokenizer. Draft heads reuse the target’s hidden states, so they are tiny and usually more accurate, often with tree drafts. They must be trained per target model and are tied to its internals.

seniorWhich workloads benefit most from n-gram / prompt-lookup speculation?

Workloads where the output copies spans of the input: code editing and refactoring, RAG answers quoting documents, summarization, and data transformation. The drafter costs nothing, so even modest acceptance is a win. For free-form generation it rarely matches and adds little.