Speculative Decoding

Definition

Speculative decoding (Leviathan et al., ICML 2023; arXiv:2211.17192, and concurrently arXiv:2302.01318) accelerates autoregressive decode by having a small, cheap draft model propose $k$ tokens, which the large target model then verifies in a single forward pass. A rejection-sampling acceptance test accepts the longest correct prefix and provably preserves the target’s output distribution — it is exact, not an approximation.

Key math / How it works

The draft proposes tokens $x_1,\dots ,x_k$ with probabilities $q(\cdot )$; the target scores them in parallel (one prefill-like, higher-intensity pass) giving $p(\cdot )$. Each proposed token is accepted with probability $\min \left(1,\frac{p(x_i)}{q(x_i)}\right)$; on the first rejection you resample from the normalized residual $\propto \max (0,p-q)$ and stop. The composition is exactly a sample from $p$.

Why it wins despite more FLOPs. Decode is memory-bound: a plain step reads all target weights to emit one token, leaving the tensor cores idle. Speculation turns one memory-bound step into a batched verification of $k$ candidates for the same single weight read — spending the wasted compute headroom to save scarce HBM bandwidth. If decode were compute-bound, it would not help.

Speedup is set by the mean accepted length (the acceptance rate) minus draft cost: typically ~2–3× with negligible quality change (workload- and draft-dependent); a poor draft can even slow you down.

Draft-free variants.

• Medusa (arXiv:2401.10774): extra decoding heads on the target predict several future tokens, verified with tree attention.
• EAGLE / EAGLE-2 (arXiv:2401.15077, arXiv:2406.16858): draft at the feature (hidden-state) level for higher acceptance; among the strongest reported ([recent — verify current SOTA]).

Why it matters

It attacks decode latency (TPOT/ITL) directly, exactly where serving cost concentrates, without changing model outputs — the rare optimization that is both free of quality tradeoff and complementary to batching/quantization.

Taught in

• 12-llm-inference-systems — §6 draft+verify, acceptance rate, Medusa/EAGLE.
• 13-gpu-engineer-roadmap — §10 a “go deeper” thread for inference engineers.

See also

• prefill-decode — why decode has idle compute to exploit
• kv-cache · arithmetic-intensity · roofline-model
• continuous-batching · quantization-inference
• gpu-systems-for-llms