Home / Fundamentals / Inference & Serving

Inference & ServingSeniorQuestion 6 of 7

How does speculative decoding work, why is it lossless, and how much does it speed things up?

30-second answer

A cheap draft (small model, extra heads like Medusa/EAGLE, or n-gram lookup) proposes k tokens; the target scores all of them in one forward pass, which costs about one decode step because decode is memory-bound. Each draft token is accepted with probability min(1, p/q); at the first rejection a replacement is sampled from normalize(max(0, p − q)), which provably preserves the target's distribution. With acceptance α, expected tokens per target pass are (1 − α^{k+1})/(1 − α): ~3.4 for α = 0.8, k = 4, typically a 2–3× latency gain. Gains shrink at large batch sizes and high temperatures.

Try answering out loud before reading on. The walkthrough below is paced for a 40-minute interview round.

0–5 min Clarify and frame

Framing: "I'll explain why it works at all (memory-bound decode), the algorithm, prove it preserves the distribution, compute the expected speedup, and then discuss drafts and when it doesn't help."

5–15 min Core explanation

Why it's possible: a decode step at small batch is memory-bound; scoring k + 1 positions in one forward pass costs almost the same as scoring one, because the weights are read once.

Algorithm (one round):

  1. The draft model generates k tokens autoregressively: x_1..x_k, with probabilities q(x_i | ·).
  2. The target runs one forward pass over the context plus x_1..x_k, giving p(· | ·) at all k + 1 positions.
  3. For i = 1..k: accept x_i with probability min(1, p(x_i) / q(x_i)). On the first rejection, sample a replacement from p'(x) = normalize(max(0, p(x) − q(x))) and stop.
  4. If all k are accepted, sample a bonus token from p at position k + 1.

Scroll sideways to see the whole diagram.

One round of speculative decodingEngine → Draft model: context …“The cat”; Draft model: draft 4 tokens: sat · on · a · mat; Draft model → Engine: tokens + draft probs q; Engine → Target model: one forward pass over context + 4 drafts; Target model → Engine: target probs p at 5 positions; Note: accept with prob min(1, p/q): sat ✓ on ✓ a ✓ mat ✗; Engine: sample correction from norm(max(0, p − q)): “the”; Note: 4 tokens emitted for one target pass; next round starts from “… sat on a the”.EngineDraft model~1B or extra headsTarget model70Bcontext …“The cat”draft 4 tokens: sat · on · a · mattokens + draft probs qone forward pass over context + 4 draftstarget probs p at 5 positionsaccept with prob min(1, p/q): sat ✓ on ✓ a ✓ mat ✗sample correction from norm(max(0, p − q)): “the”4 tokens emitted for one target pass; next round starts from “… sat on a the”
One round of speculative decoding. The draft proposes four tokens autoregressively. The target scores all of them in a single forward pass, which costs about one decode step because decode is memory-bound. Tokens are accepted left to right with probability min(1, p/q); at the first rejection a correction is sampled from the residual distribution, so the output distribution exactly matches the target's.

15–25 min Deep dive: correctness and speedup

Why the output distribution equals p. For a single position, the probability of emitting token x:

P(x) = q(x) · min(1, p(x)/q(x))  +  P(reject) · p'(x)
     = min(q(x), p(x))  +  (1 − Σ_y min(q(y), p(y))) · max(0, p(x) − q(x)) / Σ_y max(0, p(y) − q(y))

Since Σ_y max(0, p − q) = 1 − Σ_y min(p, q), the second term is max(0, p(x) − q(x)), and min(q, p) + max(0, p − q) = p(x). So it's lossless, not an approximation. (With greedy decoding, simply accept while draft and target argmaxes agree.)

Expected tokens per target pass. With per-token acceptance probability α (assume independent):

E[tokens] = 1 + α + α² + … + α^k = (1 − α^(k+1)) / (1 − α)
α = 0.6, k = 4 → 2.3      α = 0.8, k = 4 → 3.4      α = 0.9, k = 6 → 5.2

Speedup ≈ E[tokens] / (1 + k · c), where c is the cost of a draft step relative to a target step. With α = 0.8, k = 4, c = 0.05: 3.4 / 1.2 ≈ 2.8×. Choose k to maximize this; adaptive k (stop drafting when draft confidence drops) helps.

25–32 min Drafts and limits

Draft Pros Cons
Small model, same family Good α; no target changes Extra model to serve; must share tokenizer
Medusa heads No separate model; multiple heads predict future tokens Needs training; tree verification
EAGLE-style feature drafter High α using target's hidden states Training; tied to target model
N-gram / prompt lookup Free; great when output copies input Only helps for repetitive/copying outputs

Tree verification: verify several candidate continuations at once with a tree-structured attention mask, raising expected accepted length.

When it helps less:

  • Large batches: the target step becomes more compute-bound, so the extra k tokens per sequence aren't free; gains shrink and can turn negative.
  • High temperature / creative tasks: lower α.
  • Memory: the draft's weights and KV cache compete with the target's batch.

32–37 min Production example

A coding assistant served at low concurrency used a 1B draft for a 70B target: α ≈ 0.75 on code, k = 5, and 2.4× lower per-token latency. For their refactoring feature, prompt-lookup decoding (copying spans of the input file) gave α > 0.9 and a further gain at no model cost. At peak load, the system automatically reduced k because large batches erased the benefit.

37–40 min Likely follow-ups

  • Does it change outputs with sampling? No: the distribution is identical (the specific samples differ due to randomness).
  • How do you measure α? Log accepted lengths per request type; it varies by domain.
  • Can you train the draft to match the target? Yes, distill on target outputs to raise α.

What interviewers listen for

  • Why verification is cheap (memory-bound decode).
  • The acceptance rule and why it's lossless.
  • The expected-tokens formula and batch-size caveat.

Red flags

  • "The draft's tokens are approximately right, so quality drops slightly."
  • Not knowing it helps less at high batch sizes.