A Field Guide to Speculative Decoding Methods

Part 3 of 6 — Speculative Decoding series. Start with The Need for Speed.

1. The Need for Speed — Why LLMs are memory-bandwidth-bound and how speculation exploits the GPU's idle compute.
2. Speculative Decoding, Formally — The draft-then-verify algorithm, the rejection-sampling proof, and the metrics that matter.
3. A Field Guide to Speculative Decoding Methods (this post) — Separate models, Medusa, n-gram, and trees: a taxonomy of every drafting approach.
4. The EAGLE Family — How predicting hidden states instead of tokens reshaped the field, across three generations.
5. Parallel Drafting with Block Diffusion — DFlash collapses γ draft passes into one; DDTree turns that pass into a 7× verification tree.
6. Putting It to Work — Enabling EAGLE, n-gram, and Medusa speculation in vLLM and SGLang, with a guide to measuring real speedup.

---

Speculative decoding accelerates an LLM losslessly — a small, cheap draft model proposes several tokens, the large target model verifies them all in a single parallel forward pass, and a rejection-sampling rule guarantees the output is distributed exactly as the target's. Its payoff is captured by the speedup formula $S \approx \bar k / (1 + \gamma\rho)$: accepted tokens per step ($\bar k$) over the relative cost of drafting ($\gamma\rho$).

Every advance in the field can be read as an attempt to push one of two levers: raise $\bar k$ (better, longer-reaching drafts) or lower the cost $\gamma\rho$ (cheaper drafting, cheaper verification).

This post is the landmark tour. Since the original 2023 papers, researchers have explored a rich design space along four axes: who drafts, how they draft, what structure the draft takes, and how verification proceeds. Here are the major families.

1. Vanilla speculative decoding

The original formulation, introduced independently by Leviathan et al. (2023) and Chen et al. (2023), uses a smaller model from the same family as the draft.

• Target $M_p$: e.g. LLaMA-70B. Draft $M_q$: e.g. LLaMA-7B (same tokenizer, independently trained). Draft length $\gamma$: typically 3–5.
• Draft $\gamma$ tokens autoregressively, run $M_p$ on prefix + draft in one pass, apply the rejection-sampling scheme from the previous post.

Speedup. With $\alpha \approx 0.7$, $\gamma = 5$: $\bar k = (1 - 0.7^6)/(0.3) \approx 2.94$. If the draft costs 5% of the target ($\rho = 0.05$): $S = 2.94 / (1 + 5\times0.05) \approx 2.35\times$.

Strengths: simple, lossless, no training (reuse an existing small model). Weaknesses: needs a compatible draft model in the same family; quality is capped by the small model's capability gap.

2. Medusa: parallel draft heads

Medusa (Cai et al., 2024) eliminates the separate draft model. Instead it bolts $K$ lightweight prediction heads onto the target, where head $k$ predicts the token $k{+}1$ positions ahead — i.e. $y_{t+k+1}$ — from the same hidden state $h_t$ (the base LM head already supplies the immediate next token $y_{t+1}$):

$\text{Head}_k(h_t) = \text{softmax}\!\Big(W_k^{(2)}\big(\text{SiLU}(W_k^{(1)} h_t + b_k) + h_t\big)\Big),$

a single SiLU block with a residual skip in feature space, where $W_k^{(2)}$ is initialized to the original LM head (and $W_k^{(1)}$ to zero) so each head starts out reproducing the base model's prediction. Only the heads are trained (base frozen), minimizing $\mathcal{L}_k = -\sum_t \log \text{Head}_k(h_t)[y_{t+k+1}]$.

Crucially, the heads do not propose a single chain but a tree of candidates: if head $k$ keeps its top-$s_k$ tokens, the tree has $\prod_k s_k$ leaves, pruned to the most probable branches. The tree is verified in one pass via tree attention — a mask where a node attends only to its ancestors:

$M_{ij} = \begin{cases} 0 & \text{if } j \text{ is an ancestor of } i \text{ (or } j=i)\\ -\infty & \text{otherwise.}\end{cases}$

Plus: no separate draft weights, fully parallel drafting (all heads read one hidden state), trainable in a few hours. Minus: requires training; head accuracy decays for larger $k$; tree size grows combinatorially. (Vanilla Medusa is approximately lossless because the heads sample from their own distribution rather than the target's.)

3. Lookahead decoding

Lookahead decoding (Fu et al., 2024) takes a radically different tack: it frames autoregressive generation as solving a fixed-point system by Jacobi iteration. View $\gamma$ future tokens as unknowns $y_t = f(y_1, \ldots, y_{t-1})$, initialize them randomly, and update all positions in parallel:

$y_t^{(s+1)} = f\big(y_1^{(s)}, \ldots, y_{t-1}^{(s)}\big) \quad \text{for all } t \text{ simultaneously.}$

A position that stops changing ($y_t^{(s+1)} = y_t^{(s)}$) has converged; several can converge at once. The iterations are not wasted: they deposit n-gram trajectories into a growing pool, which then serve as candidate continuations verified in parallel via tree attention.

Plus: training-free, model-agnostic, no draft model, and it improves as the n-gram pool grows. Minus: higher per-step overhead; acceptance depends heavily on how repetitive/predictable the text is; pool management adds complexity.

4. Staged speculative decoding

Staged speculative decoding (Spector & Ré, 2023) uses a cascade of progressively larger models — a tiny model drafts for a small model, which drafts for the target. Early stages are nearly free (a tiny model fits in L2 cache), and because each stage boundary applies the exact rejection-sampling rule, the composition of exact samplers is still exact. The speedup compounds across stages.

5. SpecInfer: tree-structured parallel decoding

In SpecInfer (Miao et al., 2024), multiple Small Speculative Models (SSMs) independently propose sequences, which are merged by common prefix into a single tree. For instance, if SSM1 proposes A→B→C and A→B→D while SSM2 proposes A→B→C and A→E→F, the shared prefixes collapse into one tree:

Figure: four candidate sequences from two SSMs, merged by shared prefix into a single draft tree the target verifies in one pass.

The target verifies all paths at once with topology-aware causal attention (each node attends only to its ancestors). Plus: diverse candidates from several SSMs widen the explored token space. Minus: memory cost of multiple draft models; tree-size management.

6. Sequoia: optimal trees by dynamic programming

Sequoia (Chen et al., 2024) asks the structural question directly: what tree maximizes expected accepted tokens for a fixed node budget? Let $T(m, d)$ be the optimal expected tokens for a subtree of $m$ nodes at depth $d$:

$T(m, d) = \max_{(m_1, \ldots, m_c):\,\sum_i m_i = m-1} \Big[\,1 + \sum_{i=1}^{c} p_i \cdot T(m_i, d+1)\,\Big],$

where $p_i$ is the acceptance probability of the $i$-th child. The root contributes 1, and the children contribute additively — every branch of the tree accumulates acceptance mass, not just the single best one. The optimal solution is wider at the top (hedge against early rejection) and narrower at depth (deep nodes have lower cumulative acceptance $\alpha^d$). Sequoia also picks the hardware-optimal total tree size $m^\star$ as a function of bandwidth, compute throughput, and sequence length — an early example of sizing a draft tree to the hardware, a concern that returns in Parallel Drafting with Block Diffusion when draft-tree budgets meet verifier overhead.

7. Online speculative decoding

Standard SD fixes the draft model. Online speculative decoding (Liu et al., 2024) adapts it during inference, exploiting a free supervision signal: verification already computes both $p(v)$ and $q(v)$ for every token. After each step it nudges the draft toward the target,

$\theta_q \leftarrow \theta_q - \eta\,\nabla_{\theta_q}\,\text{KL}\big(p \,\Vert\, q_{\theta_q}\big),$

using a distillation buffer of recent (context, target-distribution) pairs. Plus: draft quality rises over a session and specializes to the live distribution. Minus: training-in-the-loop overhead; needs careful tuning of update frequency.

8. Self-speculative decoding

Draft & Verify (Zhang et al., 2023) and LayerSkip (Elhoushi et al., 2024) both let the target model draft for itself by skipping layers. LayerSkip runs the first $L'$ of $L$ layers and applies the LM head to that intermediate state as the draft; verification runs the full stack and reuses the draft's KV cache for the first $L'$ layers. (The related Draft & Verify instead drafts through a sparse, automatically selected subset of layers and uses a confidence threshold to decide when to stop drafting — an adaptive draft length — rather than a fixed exit layer.) Plus: zero extra parameters, no separate KV cache. Minus: early-layer predictions are often weak; needs trained early-exit heads or a confidence predictor. (It remains exactly lossless — verification still applies the standard rejection-sampling rule, so skipping layers only affects speed, never the output.)

The comparison matrix

Read down the columns and a pattern emerges. The field is steadily moving toward drafts that need no separate model, trees instead of chains, and training-free deployment — three currents that converge in the most influential line of work to date. That work has its own arc worth telling in full: in The EAGLE Family we follow the EAGLE family, whose central bet — that hidden states are more predictable than tokens — reshaped how the field thinks about drafting.

---

References

1. Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. ICML. arXiv:2211.17192.
2. Chen, C., et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling. arXiv:2302.01318.
3. Cai, T., Li, Y., Geng, Z., Peng, H., Lee, J. D., Chen, D., & Dao, T. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. ICML. arXiv:2401.10774.
4. Fu, Y., Bailis, P., Stoica, I., & Zhang, H. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding. arXiv:2402.02057.
5. Spector, B., & Ré, C. (2023). Accelerating LLM Inference with Staged Speculative Decoding. arXiv:2308.04623.
6. Miao, X., et al. (2024). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification. ASPLOS. arXiv:2305.09781.
7. Chen, Z., May, A., Svirschevski, R., Huang, Y., Ryabinin, M., Jia, Z., & Chen, B. (2024). Sequoia: Scalable, Robust, and Hardware-aware Speculative Decoding. arXiv:2402.12374.
8. Liu, X., et al. (2024). Online Speculative Decoding. ICML. arXiv:2310.07177.
9. Zhang, J., et al. (2023). Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding. arXiv:2309.08168.
10. Elhoushi, M., et al. (2024). LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding. arXiv:2404.16710.