Speculative Decoding & Parallel Token Generation

Draft-then-verify speculative decoding, Medusa multi-head prediction, EAGLE speculative decoding, lookahead decoding. Acceptance rate, speedup formula, and when speculation hurts.

Overview

Autoregressive generation produces exactly one token per forward pass, however predictable that token is. Speculative decoding lets a fast draft model propose several tokens, then has the large target model verify them all in one parallel pass, so several tokens come out for the cost of one target pass.

The algorithm

The core method (Leviathan et al., 2022; Chen et al., 2022) pairs a small draft model (speculator) with a large target model (verifier).

For each draft token x_i:

p_target(x_i) >= p_draft(x_i) — Accept with probability 1
p_target(x_i) [!IMPORTANT] The procedure is lossless: the output distribution is identical to running the target model without speculation.

Expected speedup

The speedup equals the average acceptance length, the number of tokens accepted before the first rejection. For acceptance rate alpha and draft length K, the expected accepted tokens per draft is alpha * (1 - alpha^K) / (1 - alpha).

0.8 — 4 — ~3.4 tokens — One target pass verifies 3.4 tokens, 3.4x throughput over pure autoregressive

Medusa and EAGLE

Draft source — Extra prediction heads on the target model itself; no separate draft model — Small autoregressive draft model
What it predicts — Tokens at future positions t+1, t+2, and so on — Target model feature embeddings, not tokens
Verification — Tree-structured attention mask — Draft tree; EAGLE-2 builds it dynamically from acceptance probability estimates
Acceptance rate — 0.75-0.80 — 0.85-0.90
Cost and gain — 5-10% parameter overhead, 2-3x speedup at batch=1 — Higher acceptance from working in embedding space

When it helps and when it hurts

Batch size — Batch 1 or small: memory-bandwidth-bound, and verifying K+1 tokens costs nearly the same bandwidth as one token — Large batches: the target is already compute-bound, so draft overhead and longer target passes cut throughput
Draft size — The draft model is at least 10x smaller than the target — The draft is less than 10x smaller, so drafting eats into the gain
Predictability — Code, structured data — Creative writing or high-temperature sampling, where acceptance falls below 0.5

> [!WARNING] Speculative decoding is a latency optimization for interactive serving at low batch sizes. It trades throughput for latency and is counterproductive at high batch sizes where throughput is the priority.

Interview questions

Explain the speculative sampling acceptance procedure and prove it produces the correct distribution.