Speculative Decoding

1. What is it?#

Use a cheap model to guess the next few tokens, then use the expensive model to verify all of them in one forward pass. Accept the guesses that match what the big model would have produced; discard the rest.

Draft model (small, fast):   guesses "the cat sat on the"        5 tokens, ~1 ms
Target model (big, slow):    verifies all 5 IN ONE PASS          ~40 ms
                             accepts "the cat sat on" (4 of 5)

Result: 4 tokens in ~41 ms instead of 4 × 40 = 160 ms.   ~3.9x faster.

The output distribution is provably identical to running the target model alone. It is not an approximation.

Diagram — Draft cheaply, verify in one pass#

flowchart LR
  C["Context"] --> DR["Draft model or head<br/>proposes k tokens cheaply"]
  DR --> V["Target model verifies<br/>all k in ONE forward pass"]
  V --> A{"Accept the longest<br/>matching prefix"}
  A -->|"n accepted"| OUT["Emit n + 1 tokens<br/>target supplies the correction"]
  OUT --> C
  A -.->|"low acceptance"| W["Draft + verify work wasted<br/>speculation loses"]

  class DR io
  class V compute
  class A queue
  class OUT memory
  class W warn
  class C neutral

2. Why does it exist?#

Because decode is memory-bound with 99%+ of the GPU’s arithmetic idle (Section I.07).

Verifying 1 token:  read 140 GB of weights, do 140 GFLOPs
Verifying 5 tokens: read 140 GB of weights, do 700 GFLOPs
                    ↑ SAME memory traffic          ↑ 5x compute, which was free

You have spare compute and no spare bandwidth. Speculative decoding converts the spare compute into fewer weight reads per token. It is the purest expression of the memory-bound insight in the entire curriculum.

3. Simple analogy#

A junior assistant drafting and a senior partner reviewing.

The junior drafts five sentences quickly. The senior reads all five in one pass — reading five sentences takes barely longer than reading one — and accepts the first four, rewriting the fifth.

Net: four sentences produced in the time the senior would have spent on one. The senior’s judgment is fully preserved: nothing is accepted that the senior wouldn’t have written.

The economics depend on: how often the junior is right (acceptance rate), and how much cheaper the junior is (draft cost).

4. Tiny example#

The algorithm, in full:

// LM returns, for every position of ids, the probability distribution over the next token.
type LM interface {
	Probs(ids []int) [][]float64 // shape (len(ids), V)
}

// SpeculativeDecode generates n tokens; k = speculative tokens per iteration.
func SpeculativeDecode(target, draft LM, ids []int, n, k int) (output []int) {
	for len(output) < n {
		// ---- 1. DRAFT: generate k tokens with the small model ----
		cand := append([]int{}, ids...)
		draftProbs := make([][]float64, k) // the draft's full distribution at each step
		for i := 0; i < k; i++ {
			all := draft.Probs(cand)
			draftProbs[i] = all[len(all)-1]
			cand = append(cand, sample(draftProbs[i]))
		}

		// ---- 2. VERIFY: ONE forward pass of the target over all k+1 positions ----
		all := target.Probs(cand)
		targetProbs := all[len(ids)-1:] // targetProbs[i] = target's distribution for draft token i

		// ---- 3. ACCEPT/REJECT (modified rejection sampling) ----
		accepted := 0
		for ; accepted < k; accepted++ {
			t := cand[len(ids)+accepted]
			pTarget, pDraft := targetProbs[accepted][t], draftProbs[accepted][t]
			if rand.Float64() >= min(1, pTarget/pDraft) {
				break
			}
			output = append(output, t)
		}

		var extra int
		if accepted == k {
			// all k accepted → a FREE bonus token from the target's prediction at position k
			extra = sample(targetProbs[k])
		} else {
			// rejected: sample from the RESIDUAL distribution max(0, target - draft).
			// This correction is what makes the output distribution EXACTLY the target's.
			resid := make([]float64, len(targetProbs[accepted]))
			for v := range resid {
				resid[v] = max(0, targetProbs[accepted][v]-draftProbs[accepted][v])
			}
			extra = sample(resid) // sample normalizes
		}
		output = append(output, extra)
		ids = append(cand[:len(ids)+accepted], extra)
	}
	return output[:n]
}

// sample draws an index in proportion to the (unnormalized) weights.
func sample(w []float64) int {
	var sum float64
	for _, p := range w {
		sum += p
	}
	r := rand.Float64() * sum
	for i, p := range w {
		if r -= p; r <= 0 {
			return i
		}
	}
	return len(w) - 1
}

The rejection-sampling correction (step 3) is the whole trick. Without it you’d be sampling from the draft model. With it, the output distribution is provably exactly the target model’s. Leviathan et al. prove this; it’s a short and elegant argument worth reading.

5. Technical explanation#

The speedup formula#

Let:
  α = acceptance rate (probability a drafted token is accepted)
  k = speculation length
  c = cost ratio (draft forward pass / target forward pass)

Expected tokens per iteration:
  E[tokens] = (1 - α^(k+1)) / (1 - α)

Cost per iteration:
  C = k·c + 1        (k draft passes + 1 target pass, in units of target passes)

Speedup = E[tokens] / C

Worked:

α=0.8, k=4, c=0.05 (a 400M draft for a 70B target):
  E[tokens] = (1 - 0.8^5)/(1 - 0.8) = (1-0.328)/0.2 = 3.36
  C = 4(0.05) + 1 = 1.2
  Speedup = 3.36/1.2 = 2.8x

α=0.6, k=4, c=0.05:
  E[tokens] = (1-0.0778)/0.4 = 2.31
  C = 1.2
  Speedup = 1.92x

α=0.4, k=4, c=0.2 (draft too expensive):
  E[tokens] = (1-0.0102)/0.6 = 1.65
  C = 4(0.2) + 1 = 1.8
  Speedup = 0.92x       ← SLOWER than not speculating!

Speculative decoding can lose. If the draft is inaccurate or expensive, you pay more than you gain. This is the answer to the classic interview question.

Choosing k#

Larger k:  more potential tokens per iteration
           but α^k falls fast, so extra tokens are rarely accepted
           and you pay k draft passes regardless

Optimal k ≈ 1 / (1 - α)   roughly

α = 0.9 → k ≈ 5-8
α = 0.8 → k ≈ 4-5
α = 0.6 → k ≈ 2-3

Adaptive-k schemes adjust per request based on recent acceptance — worth doing, since acceptance varies enormously by content (code and structured text draft well; creative prose doesn’t).

The variants#

1. DRAFT MODEL (classic)                                   [ESTABLISHED]
   A small model of the same family (e.g. Llama-3-1B drafting for 70B).
   α: 0.6-0.85.  Needs a separate model in memory.

2. N-GRAM / PROMPT LOOKUP                                  [ESTABLISHED]
   Look for the current suffix in the prompt; propose the continuation.
   Zero draft cost. Excellent for summarization, editing, RAG, code
   completion — anywhere output copies from input.
   α: 0.2-0.9 depending on workload. Free to try.

3. MEDUSA                                                  [EMERGING]
   Extra prediction heads on the target model predict tokens t+1, t+2, ...
   No separate model. Requires training the heads.
   Uses a tree of candidates rather than a single chain.

4. EAGLE / EAGLE-2                                         [EMERGING]
   Predict at the FEATURE level (the hidden state) rather than the token
   level, using the target's own last-layer features. Higher α (0.8-0.9)
   with a very small head.

5. SELF-SPECULATION / LAYER SKIP                           [EMERGING]
   Use a subset of the target's own layers as the draft.
   No extra memory, but α is usually lower.

6. MULTI-TOKEN PREDICTION (MTP)                            [EMERGING]
   The model is trained to predict several future tokens at once
   (DeepSeek-V3 does this). Effectively built-in speculation.

N-gram/prompt-lookup deserves special mention: it costs nothing, needs no extra model, and for the right workload (any task where the output quotes the input) gives 2-3x. It should be the first thing you try.

Tree speculation#

Instead of one chain of k tokens, propose a tree:

              the
            /  |  \
          cat dog  bird
         / \   |     \
       sat ran sat   flew

Verify all paths in ONE forward pass using a carefully constructed attention mask.
Accept the longest matching path.

Higher acceptance for the same number of target passes, at the cost of more verification compute (which is free-ish). Medusa and EAGLE-2 both use trees.

Interaction with batching — the critical caveat#

Batch 1:   GPU is memory-bound, compute is free  →  speculation is a big win
Batch 64:  GPU is closer to compute-bound        →  the extra verification compute COSTS
Batch 256: compute-bound                          →  speculation likely LOSES

Speculative decoding trades compute for bandwidth, so it helps exactly when you have spare compute — i.e. at low batch. At high batch you’ve already used your spare compute on other users.

Production systems handle this by enabling speculation adaptively based on current batch size. Some engines do this automatically; check yours.

6. Under the hood#

Verification requires a special attention mask. For a chain of k drafted tokens:

Positions:  [prompt...][d1][d2][d3][d4]
The target must compute, in ONE pass:
  logits at prompt_end  → what it would predict for d1's position
  logits after d1       → what it would predict for d2's position
  ...
So the mask is standard causal — it just happens that d1..d4 are guesses.

For tree speculation the mask is non-standard: each node attends only to its ancestors, not to its siblings. This requires a custom attention mask per step, which is why tree speculation is harder to implement efficiently.

7. Performance implications#

Reported speedups (highly workload-dependent):

Method              Batch 1    Batch 8    Batch 64   Notes
Draft model (1B/70B) 2.0-3.0x  1.5-2.2x   0.9-1.3x   needs the draft in memory
N-gram lookup        1.5-3.0x  1.3-2.0x   1.0-1.2x   free; workload dependent
Medusa               2.0-2.8x  1.6-2.2x   1.0-1.4x   needs trained heads
EAGLE-2              2.5-4.0x  2.0-3.0x   1.2-1.6x   best reported

Note the batch-64 column. At high batch several methods approach or fall below 1.0x.

8. Production implications#

• Try n-gram/prompt-lookup speculation first. It’s free, and for summarization, editing, RAG, and code it often gives 2x.
• Measure acceptance rate in production, per workload. It varies enormously and is the single number that determines whether this pays.
• Enable adaptively by batch size. Speculation at batch 128 can be a regression.
• The draft model costs memory — a 1B draft for a 70B target is 2 GB, which is KV cache you don’t have.
• Verify output distribution equivalence in testing. A buggy rejection-sampling implementation silently changes your model’s behavior.
• It complicates everything else: CUDA graphs (variable accepted counts), continuous batching (variable tokens per step per sequence), and scheduling. Budget engineering time.

9. Common mistakes#

Assuming it always helps. At high batch or low acceptance, it hurts. Do the arithmetic.

Skipping the rejection-sampling correction. You’re now sampling from the draft model, which is a silent quality regression.

Choosing k too large. α^k decays fast; you pay for draft passes that are almost never accepted.

Using a poorly-matched draft model. A draft from a different family or tokenizer has low acceptance. The draft should share the target’s tokenizer, and ideally be distilled from it.

Not measuring acceptance rate. Flying blind.

Ignoring the memory cost of the draft model.

10. Hands-on exercise#

A. Implement it. Write speculative decoding with a real draft/target pair (e.g. a 0.5B draft for a 7B target). Verify that with temperature 0 it produces identical output to plain greedy decoding from the target.

B. Measure acceptance. Instrument your implementation to record the acceptance rate. Measure it on: creative writing, code completion, summarization (where output quotes input), and Q&A. Explain the differences.

C. Verify the formula. Measure actual speedup for k ∈ {1,2,4,8} and compare to the formula in section 5 using your measured α and c. How close is the prediction?

D. Find the losing case. Construct a configuration where speculative decoding is slower than plain decoding. Verify empirically.

E. N-gram speculation. Implement prompt-lookup decoding (find the current suffix in the prompt, propose the continuation). Measure the speedup on a summarization task where the output heavily quotes the input.

F. Batch interaction. Measure speculative speedup at batch 1, 8, 32, 64. Plot. At what batch size does it stop helping on your hardware?

11. Interview questions#

1. Explain speculative decoding and why it’s a bandwidth optimization.
2. Why is the output distribution provably identical to the target model’s?
3. Derive the speedup formula. When is speculation slower than not speculating?
4. How would you choose k?
5. Why does speculative decoding help less at large batch size?
6. What is n-gram/prompt-lookup speculation and when is it the best choice?
7. What does the draft model cost you besides compute?
8. How does tree speculation improve on chain speculation?

12. Further reading#

• [ESTABLISHED] Leviathan, Kalman, Matias, “Fast Inference from Transformers via Speculative Decoding” (2022) — read the proof of distribution equivalence
• [ESTABLISHED] Chen et al., “Accelerating LLM Decoding with Speculative Sampling” (2023)
• [EMERGING] Cai et al., “Medusa” (2024); Li et al., “EAGLE” and “EAGLE-2” (2024)
• [REFERENCE] vLLM speculative decoding documentation
• Next: 13 — Sampling and decoding strategies