LLM & VLM courseBlog
129Track 5: LLM inference and serving · session 52 of 65

Speculative decoding 2: drafts and verification (Medusa, EAGLE, Lookahead, SpecInfer)

Session 128 proved that a draft-then-verify loop keeps the target model’s exact output. This session is about the drafter: a separate small model, extra heads on the target itself (Medusa), a tiny head that predicts the target’s own features (EAGLE), no model at all (prompt lookup and Lookahead decoding), or multi-token prediction heads trained with the model (DeepSeek-V3). You also learn tree verification: how one forward pass checks many candidate branches at once with a special attention mask (SpecInfer, Medusa).

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Session 128 (speculative decoding: the math), Session 80 (the KV cache), Session 82 (why inference is slow)

What you will learn

  • The four kinds of drafter (separate model, self-drafting heads, feature-level drafting, no model) and what each one costs
  • How Medusa heads are built and trained, and why their guesses for different positions combine into a Cartesian-product tree
  • Tree attention: the mask and position ids that let one target pass verify every branch, and how to count tree tokens
  • Why a wide tree helps a weak drafter and a long chain helps a strong one, with a small expected-length model
  • How EAGLE drafts at the feature level, why it feeds the sampled token shifted by one step, and what EAGLE-2 and EAGLE-3 changed
  • Prompt lookup decoding and Lookahead decoding: speculation with no draft model at all
  • Multi-token prediction heads (Gloeckle et al., DeepSeek-V3) used as built-in drafters, and their reported acceptance rates

Why this matters

In session 128 we proved a strong result: if a cheap drafter guesses a few tokens and the big model checks them in one pass, the output has exactly the big model’s distribution. The math does not care where the guesses come from. The speed does. This session is about the drafter, and about checking many guesses at once.

Decoding one token at a time is slow because each step reads all the weights from memory to produce just one token (session 82). The GPU has spare compute in every step. Speculative decoding uses that spare compute to check several tokens per weight read. How many tokens you gain per step depends on two things: how often the guesses are right, and how much the guessing costs. Every method in this session is a different answer to “how do we get good guesses cheaply?”

  • A separate draft model: a small model of the same family (for example a 4B draft for the 70B Chinchilla model in Chen et al. [Likely]). Simple, but you must train, host and keep in sync a second model.
  • Self-drafting heads (Medusa): a few extra output heads on the big model guess tokens 2, 3, 4 … steps ahead from the same hidden state.
  • Feature-level drafting (EAGLE): one small decoder layer predicts the big model’s next hidden feature, not its next token.
  • No draft model at all: copy candidate tokens from the prompt (prompt lookup decoding), or from n-grams the model itself produced in parallel (Lookahead decoding).
  • Multi-token prediction (MTP) heads trained together with the model, as in DeepSeek-V3, which serve as a free drafter at inference.

The second idea is tree verification. Instead of one chain of guesses, the drafter proposes a small tree of alternatives. A special attention mask lets the big model check every branch in the same single pass (SpecInfer, Medusa). Trees are why a weak drafter can still give a large speedup.

These are not research toys. vLLM, SGLang, TensorRT-LLM and Hugging Face transformers ship several of these drafters [Likely], and DeepSeek-V3 reports that its MTP module, used as a drafter, gives 1.8 times the tokens per second of plain decoding [Certain].

What a drafter must deliver

Recall the two numbers from session 128. Let \(\alpha\) be the chance that the target accepts one drafted token (assume it is the same at each position), and let \(\gamma\) be the number of drafted tokens per step. One target pass then produces on average

\[ \E[\text{tokens per target pass}] = \frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} \tag{129.1} \]

tokens: the accepted prefix of the draft plus one token that the target always adds itself (the correction token, or a “bonus” token when all guesses pass). Drafting is not free. If one draft step costs a fraction \(c\) of one target pass, a full step costs \(1 + \gamma c\) target passes, and the speedup over plain decoding is

\[ \text{speedup} = \frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(1 + \gamma c)} \tag{129.2} \]
Read the symbols
\(\alpha\)
acceptance rate: the chance that one drafted token survives verification
\(\gamma\)
how many tokens the drafter proposes before each target pass
\(c\)
cost of one draft step divided by the cost of one target pass (0.05 means the drafter is 20 times cheaper)

Formula (129.2) is the scorecard for every method in this session. A good drafter has a high \(\alpha\) and a small \(c\). A separate draft model has a medium \(\alpha\) and a medium \(c\). Medusa heads have \(c\) close to 0 (they run inside the target pass) but a lower \(\alpha\) for far positions. EAGLE spends a little more \(c\) for a much higher \(\alpha\). Prompt lookup has \(c \approx 0\) and an \(\alpha\) that is near 1 when the output copies the input and near 0 when it does not. This formula assumes that verification of \(\gamma + 1\) tokens costs the same as one decode step; that is true only while decoding is memory-bound (small batches). We return to this in “Common mistakes”.

speedup, formula (129.2)tokens per target pass, formula (129.1)
Figure 1. The drafter scorecard. For a given acceptance rate and draft cost, the curves show tokens per target pass and the real speedup as the draft length grows. The dot marks the chosen \(\gamma\).
How to read Figure 1

Tokens per pass (orange) always rises with \(\gamma\) but saturates at \(1/(1 - \alpha)\). The speedup (red) rises, peaks, and then falls, because every extra draft step costs \(c\) but is accepted less and less often. Set \(c = 0\) (Medusa-like heads, prompt lookup): the speedup equals the tokens per pass. Set \(c = 0.2\): the best \(\gamma\) moves down and the peak drops. Lower \(\alpha\) to 0.5: even a free drafter gives less than 2×. This is why the rest of the session is about raising \(\alpha\) without raising \(c\).

Worked example: one drafter, two costs

Take \(\alpha = 0.8\) and \(\gamma = 4\). Formula (129.1): \((1 - 0.8^5)/(1 - 0.8) = (1 - 0.32768)/0.2 = 3.36\) tokens per target pass.

With a draft model that costs \(c = 0.05\): speedup \(= 3.36 / (1 + 4 \times 0.05) = 3.36/1.2 = 2.80\). The best draft length for this \(c\) is \(\gamma = 8\), with speedup 3.09.

With a heavier draft, \(c = 0.2\): the best is \(\gamma = 4\), and the speedup is only \(3.36 / 1.8 = 1.87\). Same acceptance, much less gain. With a weaker drafter, \(\alpha = 0.6\), \(\gamma = 4\), \(c = 0.05\): \(2.31\) tokens per pass and speedup 1.92.

Four ways to draft

Figure 2 puts the drafters side by side. The key question for each one is: what information does the drafter see, and what extra thing must you train or host?

Figure 2. Four drafters. Red boxes are the target model, green boxes are what you must add. A separate model sees only tokens. Medusa heads see the target’s last hidden state \(\mathbf{h}_t\). EAGLE sees the hidden features and the already chosen next token. Prompt lookup sees only the text and needs no new weights.
DrafterInput to the drafterExtra weightsDraft cost \(c\)Typical weakness
Separate small modelthe tokensa full small LM with the same tokenizermedium (its own forward passes)must be kept aligned with the target; second KV cache
Medusa headslast hidden state \(\mathbf{h}_t\)\(K\) small heads (one layer each)near 0 (run with the target)heads guess position \(t + k\) without seeing tokens \(t+1, \dots\), so far heads are weak
EAGLEhidden features + the next tokenone decoder layer (under 1B for a 70B target)small (one layer per draft step)needs training per target model
Prompt lookup / n-gramthe text so farnonenear 0helps only when the output repeats the input
Lookahead decodingthe target’s own parallel guessesnoneextra tokens in each target passuses spare compute; gains shrink at large batch
MTP heads (DeepSeek-V3)hidden state + next-token embeddingone transformer block per depth, trained in pretrainingsmallmust be part of pretraining

A separate draft model

This is the original design of Leviathan et al. and Chen et al. The drafter is a smaller language model that uses the same tokenizer, because the target verifies token ids. Chen et al. used a 4B draft model [Likely] for the 70B Chinchilla model and report a 2 to 2.5× decoding speedup in a distributed setup [Certain]. The drafter runs \(\gamma\) ordinary decoding steps, keeping its own KV cache, then the target scores all \(\gamma\) tokens in one pass. After verification, both caches are cut back to the accepted length.

The cost is operational more than mathematical: a second model to host, a second KV cache in GPU memory, and a drafter that may drift away from the target after you fine-tune the target. A common fix is to distill the drafter on the target’s own outputs (session 119), which raises \(\alpha\).

Medusa: extra heads on the target model

Medusa removes the second model. The target already computes a last hidden state \(\mathbf{h}_t\) at position \(t\), and its normal LM head turns it into the next token \(t+1\). Medusa adds \(K\) more heads. Head \(k\) reads the same \(\mathbf{h}_t\) and predicts the token at position \(t + k + 1\):

\[ p_t^{(k)} = \softmax\!\Big( W_2^{(k)} \big( \operatorname{SiLU}(W_1^{(k)} \mathbf{h}_t) + \mathbf{h}_t \big) \Big) \tag{129.3} \]
Read the symbols
\(\mathbf{h}_t \in \R^{d}\)
the target’s last hidden state at position \(t\), the same vector the normal LM head uses
\(W_1^{(k)} \in \R^{d \times d}\)
one feed-forward layer per head, with a residual connection; it starts at zero
\(W_2^{(k)} \in \R^{V \times d}\)
the head’s output matrix over the vocabulary of size \(V\); it starts as a copy of the original LM head
\(p_t^{(k)}\)
head \(k\)’s guess for the token \(k + 1\) steps ahead

Because \(W_1\) starts at zero and \(W_2\) copies the LM head, every head starts by predicting the same thing as the normal head, and training moves it from there [Certain]. Medusa-1 freezes the target and trains only the heads, with a loss that gives far heads less weight:

\[ \mathcal{L}_{\text{Medusa-1}} = \sum_{k=1}^{K} -\lambda_k \log p_t^{(k)}\big(y_{t+k+1}\big), \qquad \lambda_k = 0.8^{k} \tag{129.4} \]

The paper suggests about five heads, and reports that Medusa-1 on Vicuna-7B trains in about five hours on one A100 with 60k ShareGPT samples [Certain]. Medusa-2 trains the heads and the target together (with care so the target’s own quality does not drop). The reported speedups are over 2.2× for Medusa-1 and 2.3 to 3.6× for Medusa-2 [Certain].

The weakness is visible in formula (129.3): head 3 must guess token \(t+4\) without knowing which tokens \(t+2\) and \(t+3\) will be. Its guess cannot depend on the branch. Medusa’s answer is to take the top few guesses of each head and verify all their combinations: a tree.

Typical acceptance (an optional, lossy rule)

With sampling, Medusa can verify with the exact rule from session 128. The paper also proposes a looser rule called typical acceptance: accept a candidate token \(x\) if the target gives it enough probability,

\[ p_{\text{target}}(x \mid \text{context}) \gt \min\!\big(\varepsilon,\ \delta \, e^{-H(p_{\text{target}})}\big) \tag{129.5} \]

where \(H\) is the entropy of the target’s distribution at that position, and \(\varepsilon\), \(\delta\) are thresholds. When the target is unsure (high entropy), the bar is lower. This accepts more tokens, but the output no longer has exactly the target’s distribution. Know the difference in an interview: greedy verification and the rejection-sampling rule are lossless; typical acceptance is not.

Tree verification: many branches in one pass

Suppose head 1 offers its top 2 tokens and head 2 its top 3. All combinations give \(2 \times 3 = 6\) candidate continuations. Verifying them one by one would take 6 target passes. Tree verification checks all of them in one pass, and shares the common prefixes so each distinct node is computed once.

Put every tree node into the input sequence after the accepted prefix. Each node must “see” the prefix and its own ancestors, and nothing else: a token on one branch must not attend to a token on a sibling branch. That is a custom attention mask:

\[ M_{ij} = \begin{cases} 0 & \text{if } j \text{ is in the prefix, or } j \text{ is an ancestor of } i \text{, or } j = i \\ -\infty & \text{otherwise} \end{cases} \tag{129.6} \]

The mask is added to the attention scores before the softmax, so \(-\infty\) entries get zero weight. Each node also gets the position id of its depth (prefix length + depth − 1), not its index in the flattened sequence; siblings share a position. With these two changes, the output at each node is exactly what the target would compute if that branch were the only text. SpecInfer introduced this tree-based parallel decoding for serving, with trees built from one or more small draft models [Certain], and Medusa uses the same idea for its heads.

If head \(i\) offers its top \(s_i\) tokens and the tree is the full Cartesian product, the number of nodes to verify and the number of complete candidates are

\[ N_{\text{nodes}} = \sum_{d=1}^{D} \prod_{i=1}^{d} s_i, \qquad N_{\text{candidates}} = \prod_{i=1}^{D} s_i \tag{129.7} \]

For \((s_1, s_2) = (2, 3)\): \(2 + 6 = 8\) nodes and 6 candidates. For \((3, 3, 3)\): \(3 + 9 + 27 = 39\) nodes. Real systems do not use full products; they prune the tree to the branches most likely to be accepted, under a node budget [Likely].

Why a tree helps: a small model

For greedy decoding, a branch survives at depth \(d\) if the target’s own choice is among the \(s_d\) guesses at that depth. Assume a toy drafter whose guesses at depth \(d\) are right with probability \(a_d\), and whose wrong guesses miss independently, so that the top \(s\) contain the right token with probability \(1 - (1 - a_d)^{s}\). Then the expected number of accepted draft tokens is

\[ \E[\text{accepted}] = \sum_{d=1}^{D} \prod_{i=1}^{d} \Big( 1 - (1 - a_i)^{s_i} \Big), \qquad a_i = a \cdot r^{\,i-1} \tag{129.8} \]
Read the symbols
\(a\)
top-1 accuracy of the drafter at the first draft position
\(r\)
how fast accuracy drops with depth (Medusa’s far heads are weaker, so \(r \lt 1\))
\(s_i\)
how many guesses the tree keeps at depth \(i\)

This is a teaching model, not a measured curve: real top-\(s\) hit rates come from running the drafter on data. But it shows the trade-off. Each target pass returns \(1 + \E[\text{accepted}]\) tokens. Explore it in Figure 3.

selected node and its pathallowed attention (mask 0)blocked (mask \(-\infty\))
Figure 3. A Medusa-style candidate tree (left) and its tree attention mask among the tree tokens (right). Node labels give the head and the rank of the guess: “2b” is head 2’s second-best token. Click a node to see its row in the mask: it may attend only to its ancestors and itself (and to the whole prefix, not drawn).
How to read Figure 3

The readout counts nodes and candidates with formula (129.7) and the expected accepted length with formula (129.8). It also compares the tree with a plain chain that uses the same number of nodes (the same verification compute). With the defaults (\(a = 0.6\), \(r = 0.85\)), the tree \((2, 2, 2)\) of 14 nodes accepts 1.91 tokens per pass on average, while a 14-token chain accepts only 1.11: with a weak drafter, width beats depth. Now raise \(a\) to 0.9 and \(r\) to 0.95: the 14-token chain accepts 3.77 and the tree 2.89. A strong drafter wants a long, thin tree. This is why EAGLE-2 changes the tree shape at run time from the drafter’s confidence.

Worked example: the default tree in Figure 3

\(a_1 = 0.6\), \(a_2 = 0.6 \times 0.85 = 0.51\), \(a_3 = 0.6 \times 0.85^2 = 0.4335\). With two guesses per depth, the survival chances are \(1 - 0.4^2 = 0.84\), \(1 - 0.49^2 = 0.7599\), and \(1 - 0.5665^2 = 0.6791\).

Formula (129.8): \(0.84 + 0.84 \times 0.7599 + 0.84 \times 0.7599 \times 0.6791 = 0.84 + 0.638 + 0.433 = 1.91\) accepted tokens, so 2.91 tokens per target pass. The tree has \(2 + 4 + 8 = 14\) nodes. A chain of 3 (one guess per depth) accepts only 1.04, and even a chain of 14 accepts 1.11, because \(0.6 \times 0.51 \times 0.43 \times \dots\) shrinks fast.

Stochastic verification of a tree

For greedy decoding, verification is easy: walk down from the root, and at each node follow the child equal to the target’s argmax; stop when no child matches, then append the target’s own token. For sampling, SpecInfer proposes multi-step speculative sampling: at a node, try the children one at a time with the usual accept test \(\min(1, p(x)/q(x))\); after each rejection, replace the target distribution by the normalized residual \(\max(0, p - q)\) before testing the next child; if all children fail, sample from the final residual [Likely]. The paper proves that this keeps the target’s distribution [Certain], so trees do not force you to give up exact sampling.

Algorithm 1: one decoding step with tree verification (greedy)
  1. input: accepted tokens \(x_{1:n}\), the target’s KV cache for them, a drafter, per-depth widths \(s_1, \dots, s_D\)
  2. drafter proposes the top-\(s_d\) tokens for each depth \(d\) // Medusa: heads on \(\mathbf{h}_n\); EAGLE: a few draft-layer steps
  3. build the tree nodes (every prefix path), formula (129.7)
  4. build the mask (129.6) and position ids (\(n + \text{depth} - 1\)) for the nodes
  5. run the target once on all nodes, attending to the cached prefix // the only expensive step
  6. \(y \leftarrow\) target argmax after \(x_n\); path \(\leftarrow\) empty
  7. while the node path + \(y\) exists in the tree: path \(\leftarrow\) path + \(y\); \(y \leftarrow\) target argmax at that node
  8. append path and then \(y\) to the output // at least one new token per step
  9. keep the KV entries of the accepted path, drop the rest of the tree’s entries

Figure 4 runs Algorithm 1 for real, pass after pass, on a toy you can follow word by word. The target is a trigram model: its next word depends on the last two words it can see. The drafter is a weaker bigram model (it sees only the last word), plus optional noise. Both are counted from the same tiny football corpus (one 23-token sentence written twice, plus seven short distractor sentences written three times each), so every guess and every check is an actual computation in your browser. You can switch the drafter between two styles. Medusa-style: each head proposes its top-\(s_d\) words once, from the prefix only, so every parent gets the same children. EAGLE-style: the drafter runs again on every branch, so each child list depends on its parent word (we come back to this in the EAGLE section). You can also break the mask on purpose.

Output (grey: prompt; green: accepted draft words; dashed: the target’s own word)
Algorithm 1, running
  1. input: accepted words \(x\), drafter, widths \(s_1 \dots s_D\)
  2. drafter proposes the top-\(s_d\) words for depth \(d\)
  3. build the tree nodes (every path), count (129.7)
  4. build the mask (129.6) and position ids \(n + \text{depth} - 1\)
  5. ONE target pass over all nodes // argmax at every node
  6. \(y \leftarrow\) target argmax after \(x\); path \(\leftarrow\) empty
  7. while path + \(y\) is a node: extend path; \(y \leftarrow\) its argmax
  8. append path, then \(y\)
  9. keep the KV of the accepted path, drop the rest
draft word (proposed)target’s argmax at that nodeaccepted path / allowed attentioncheck failed
Figure 4. Tree verification computed live. A trigram target and a weaker bigram drafter generate a 21-word sentence. Each node of the tree shows a draft word (top) and, after the single target pass, the target’s own next word at that node (blue, bottom). The walk of line 7 then follows the target’s choices down the tree. Under the tree: the attention mask among the tree nodes (rows look at columns).
How to read Figure 4

Press Play, or Step to run one line of Algorithm 1 at a time (Back goes back). The tree grows one depth at a time (line 2), then the mask and position ids are built (line 4), then one target pass writes the blue word under every node (line 5): that is what the target would say next if that branch were the text so far. The walk (line 7) starts from the target’s word after the prefix and goes down while some child equals it; each green node is an accepted draft word, and the first missing word is the target’s own token. With the defaults, a plain chain (set all widths to 1) needs 12 target passes for the 21 words, the Medusa-style tree \((2,2,2)\) needs 8, and the EAGLE-style tree needs 6, because its children follow the branch (look at the second pass: under “a” and “the” it offers different words). Set the noise \(\sigma\) to 1 to make the drafter worse: Medusa-style falls to 10 passes, while the EAGLE-style tree still needs 6. Now switch the mask to “plain causal”: every node also sees its earlier siblings, the target’s blue words become wrong, and the output stops matching plain greedy decoding (red words). This is the bug behind the “wrong mask” and “wrong position ids” mistakes below.

EAGLE: draft the features, not the tokens

EAGLE starts from an observation: predicting the target’s next hidden feature (the vector just before the LM head) is easier than predicting its next token, because features change smoothly while tokens jump. Its drafter is small: the target’s own embedding layer and LM head (frozen, reused), plus one fully connected layer and one decoder layer that are trained. For LLaMA2-Chat 70B this is under 1B trainable parameters, trained in 1 to 2 days on 4 A100 (40 GB) GPUs [Certain].

There is a catch. With sampling, the feature \(\mathbf{f}_i\) does not tell the drafter which token was actually sampled at position \(i+1\); many tokens are possible. The next feature depends on that choice. EAGLE removes this uncertainty by feeding the drafter the token sequence advanced by one step: to predict \(\mathbf{f}_{i+1}\), it sees the features up to \(i\) and the tokens up to \(i + 1\):

\[ \hat{\mathbf{f}}_{i+1} = g_\phi\big(\mathbf{f}_{1:i},\ e(t_{2:i+1})\big), \qquad \mathcal{L} = \operatorname{SmoothL1}\big(\hat{\mathbf{f}}_{i+1}, \mathbf{f}_{i+1}\big) + w_{\text{cls}} \, \mathrm{CE}\big(\mathrm{LMHead}(\hat{\mathbf{f}}_{i+1}),\ t_{i+2}\big) \tag{129.9} \]
Read the symbols
\(\mathbf{f}_i\)
the target’s top hidden feature at position \(i\) (input of its LM head)
\(e(t)\)
the target’s embedding of token \(t\); the drafter fuses it with \(\mathbf{f}\) through the FC layer
\(g_\phi\)
the drafter: one FC layer plus one decoder layer, with trainable weights \(\phi\)
\(w_{\text{cls}}\)
weight of the token loss; EAGLE uses 0.1

At inference, the drafter runs a few cheap steps, each one turning a predicted feature into token guesses through the frozen LM head, and builds a tree. EAGLE reports a 2.7 to 3.5× latency speedup on LLaMA2-Chat 70B, with the target generating 3.2 to 4.5 tokens per forward pass, while keeping the output distribution [Certain]. Compared with Medusa, the key difference is that each EAGLE draft step does know the tokens chosen before it, so far positions stay accurate. You can see this effect in Figure 4: switch the drafter to “EAGLE-style”. The toy drafter there works on words, not features, but it has the property that matters: the guesses for depth 2 are made after choosing the depth-1 word of that branch. With the same 14-node tree, the 21 words need 6 target passes instead of 8.

  • EAGLE-2 keeps the drafter and makes the tree dynamic: the drafter’s confidence is a good estimate of the acceptance rate, so it expands the most promising branches for each context instead of using one fixed tree shape. It reports speedups of 3.05× to 4.26×, 20% to 40% faster than EAGLE-1 [Certain].
  • EAGLE-3 drops the feature-prediction loss, predicts tokens directly, fuses features from several target layers (low, middle, high), and trains with “training-time test”: during training the drafter is fed its own earlier predictions, as it will be at inference. It reports up to 6.5× speedup, about 1.4× over EAGLE-2, and a 1.38× throughput gain at batch size 64 in SGLang [Certain].

Multi-token prediction heads as drafters

Medusa and EAGLE add a drafter after the model is trained. Multi-token prediction (MTP) trains the model from the start to predict several future tokens. Gloeckle et al. put \(n\) output heads on a shared trunk and train with the sum of the losses:

\[ \mathcal{L}_n = -\sum_{t} \sum_{i=1}^{n} \log P_\theta\big(x_{t+i} \mid x_{1:t}\big) \tag{129.10} \]

They report better code models and that, with 4-token prediction, the extra heads used for self-speculative decoding make inference up to 3 times faster [Certain]. DeepSeek-V3 uses a sequential MTP module instead of parallel heads. The module at depth \(k\) combines the previous depth’s hidden state with the embedding of the next known token, then runs one transformer block:

\[ \mathbf{h}_i'^{\,k} = M_k \big[ \operatorname{RMSNorm}(\mathbf{h}_i^{k-1});\ \operatorname{RMSNorm}(\operatorname{Emb}(t_{i+k})) \big], \qquad \mathbf{h}^{k}_{1:T-k} = \operatorname{TRM}_k\big(\mathbf{h}'^{\,k}_{1:T-k}\big) \tag{129.11} \]
Read the symbols
\(\mathbf{h}_i^{k-1}\)
hidden state of token \(i\) at depth \(k - 1\) (depth 0 is the main model)
\([\,\cdot\,;\,\cdot\,]\)
concatenation of two \(d\)-dimensional vectors into one of size \(2d\)
\(M_k \in \R^{d \times 2d}\)
projection back to size \(d\)
\(\operatorname{TRM}_k\)
one transformer block; the embedding layer and output head are shared with the main model

This is very close to EAGLE’s drafter (features plus the next token), but trained during pretraining. DeepSeek-V3 uses depth \(D = 1\), reports that the second token is accepted 85% to 90% of the time, and that this gives 1.8 times the tokens per second [Certain].

Worked example: does 85–90% explain 1.8×?

With one drafted token (\(\gamma = 1\)), formula (129.1) gives \(1 + \alpha\) tokens per target pass: \(1.85\) for \(\alpha = 0.85\) and \(1.90\) for \(\alpha = 0.90\). The reported 1.8× is a little lower, which fits a small cost for the MTP block and the verification overhead (\(c \gt 0\) in formula 129.2). The numbers are consistent.

No draft model: prompt lookup and Lookahead decoding

Prompt lookup decoding

Many outputs copy the input: a summary repeats names and phrases, a code edit repeats most of the file, a RAG answer quotes the retrieved passage. Prompt lookup decoding (Saxena, 2023) uses this. Take the last few tokens generated, search for the same n-gram earlier in the text, and propose the tokens that followed it there. The target verifies them as usual. There are no new weights and the draft costs almost nothing. The reference implementation uses n-grams of up to 3 tokens and proposes 10 tokens [Certain]; the author reports about 2.4× average speedup on summarization and context QA with Mistral-7B, and smaller gains on open-ended chat [Certain]. Hugging Face transformers exposes it as prompt_lookup_num_tokens, and vLLM as an “ngram” speculative method [Likely].

Algorithm 2: prompt lookup drafting
  1. input: all tokens so far \(x_{1:n}\) (prompt + output), max n-gram size \(n_{\max}\), proposal length \(K\)
  2. for \(m = n_{\max}\) down to 1:
  3.   tail \(\leftarrow x_{n-m+1:n}\)
  4.   find the latest \(j \lt n - m + 1\) with \(x_{j:j+m-1} =\) tail
  5.   if found: return \(x_{j+m : j+m+K-1}\) // the tokens that followed the match
  6. return no proposal // fall back to one normal decoding step
  7. verify the proposal with one target pass; keep the matching prefix plus the target’s next token
Prompt (a Video-RAG style request with a retrieved clip description)
Output
matched n-gramproposed and rejectedaccepted (dashed: target’s own token)
Figure 5. Prompt lookup decoding on a 21-token answer. Each step searches for the last n-gram (up to 3 tokens) of the text so far, proposes the next 4 tokens after the match, and keeps those that agree with the target, plus one token from the target itself.
How to read Figure 5

The target’s greedy answer is fixed in advance, so every step is exact. Early steps find only weak 1-token matches and gain little. Once the answer starts quoting the clip description (“the striker”), 2- and 3-gram matches propose the right words and every proposal is accepted: 5 tokens per target pass. The whole answer takes 7 target passes instead of 21. On text that does not repeat the input, the proposals would be rejected and each step would produce just the 1 target token: no gain, but almost no loss.

Lookahead decoding

Lookahead decoding (Fu et al.) also needs no drafter, but it does not rely on the prompt. It builds on Jacobi decoding: guess the next \(m\) tokens at once (even randomly), then update all of them in parallel with the target until they stop changing:

\[ y_i^{(j+1)} = \argmax_{y}\ p_\theta\big(y \mid x,\ y_{1:i-1}^{(j)}\big), \qquad i = 1, \dots, m \tag{129.12} \]

The fixed point of this iteration is exactly the greedy output. Plain Jacobi decoding rarely fixes more than one token per iteration, but the half-converged guesses contain useful n-grams. Lookahead decoding keeps a window of these parallel guesses (the “lookahead branch”), collects the n-grams they produce into a pool, and in the same target pass verifies the pool’s n-grams that start with the current last token (the “verification branch”). The output stays exactly greedy. It reports up to 1.8× on MT-bench and up to 4× with several GPUs on code completion [Certain]. The cost is many extra tokens in each pass, so it uses the spare compute of small-batch decoding and helps less when the GPU is already busy.

Lookahead decoding does not run plain Jacobi steps on one row of guesses. It keeps a 2D window: \(W\) future columns and the last \(N - 1\) levels (rows) of the guess trajectory. In each target pass, the new guess at column \(i\) looks at the prefix and at the earlier tokens on its own diagonal, one from each older level:

\[ y_i^{(j+1)} = \argmax_{y}\ p_\theta\big(y \mid x,\ y_{i-N+1}^{(j-N+2)}, \dots,\ y_{i-2}^{(j-1)},\ y_{i-1}^{(j)}\big) \tag{129.13} \]

So each diagonal of the window is a short greedy continuation that the model itself produced, started from a guessed token. The window then gives \(W - N + 1\) n-grams, one per diagonal, which go into the pool under their first token:

\[ g_i = \big(y_i^{(j-N+2)},\ y_{i+1}^{(j-N+3)},\ \dots,\ y_{i+N-1}^{(j+1)}\big), \qquad \text{pool}\big[y_i^{(j-N+2)}\big] \leftarrow g_i \tag{129.14} \]
Read the symbols
\(y_i^{(j)}\)
the guess in column \(i\) (the \(i\)-th future position) at level \(j\) (after \(j\) updates)
\(W,\ N\)
window size (how many future columns) and n-gram size (levels kept + 1)
\(g_i\)
the n-gram read along diagonal \(i\); its first token is the pool key
\(G\)
the most candidates the verification branch checks per pass; the pass processes about \(W(N-1) + G(N-1)\) extra tokens

The verification branch takes up to \(G\) pool n-grams whose first token equals the last accepted token, and checks them greedily in the same pass, with a mask that keeps the two branches apart. Fu et al. describe the 2D window, the diagonal n-grams and the first-token match [Certain]; the exact column-to-column wiring in our toy is a simplified version [Likely]. Figure 6 runs it on the trigram target of Figure 4, with a window filled with random words at the start.

Algorithm 3: one Lookahead decoding step
  1. input: accepted tokens \(x\), window levels \(y^{(j-N+2)}, \dots, y^{(j)}\) of width \(W\), n-gram pool, cap \(G\)
  2. candidates \(\leftarrow\) up to \(G\) pool n-grams whose first token is the last token of \(x\)
  3. run the target once on the lookahead branch (new level, formula 129.13) and the verification branch (all candidates)
  4. accept the candidate with the longest prefix that matches the target’s greedy choices, then add the target’s own next token
  5. add the \(W - N + 1\) diagonal n-grams (129.14) to the pool
  6. drop the oldest level; the new level becomes the newest
Output (grey: prompt; green: accepted from a pool n-gram; dashed: the target’s own token)
Algorithm 3, running
  1. input: \(x\), window levels, pool, \(G\)
  2. candidates \(\leftarrow\) pool n-grams starting with the last token
  3. ONE target pass: new level (129.13) + check candidates
  4. accept the longest match, then the target’s token
  5. add the diagonal n-grams (129.14) to the pool
  6. drop the oldest level
n-gram pool (blue: key that matches the last token; orange: added in this pass)
Figure 6. Lookahead decoding computed live on the trigram target of Figure 4, with no draft model. Left: the 2D window (oldest level on top, the new level at the bottom), with the diagonal n-grams of formula (129.14) drawn as colored lines; below it, the verification branch, which checks pool n-grams that start with the last accepted token. Bottom: the pool.
How to read Figure 6

Press Play or Step. The window starts with random words. Each pass computes a new level (the bottom row): column \(i\) uses the prefix and the two tokens on its diagonal, formula (129.13), so column 1 is always the target’s true next token, while later columns are continuations of guessed words. After a few passes, the diagonals contain real phrases of the target, such as “two defenders and”. When the last accepted token is the first token of a pool n-gram, the verification branch checks it in the same pass: green ticks are accepted, a red cross ends the check. With the defaults, 21 tokens take 15 target passes (1.40 tokens per pass), and the output is exactly the greedy output. Shrink the window to \(W = 3\): fewer diagonals, the pool is hit only once, and the run needs 19 passes. Set \(G = 1\): only the newest n-gram for the key is checked, a good older one is missed, and the run needs 17 passes. Real LLM text has many more repeated phrases than this short sentence, which is where the reported gains (up to 1.8× on MT-bench) come from [Likely].

Putting it together in code

Algorithm 4: choosing a drafter for a deployment
  1. measure the batch size you serve; if decoding is compute-bound at that batch, expect small gains and maybe stop here
  2. if outputs copy the input (summaries, code edits, RAG): start with prompt lookup, it is free
  3. if the model was trained with MTP heads: use them as the drafter
  4. else if you can train a little: EAGLE-style drafter (best \(\alpha\) per unit of cost), or Medusa heads (simplest)
  5. else if a small model of the same family and tokenizer exists: separate draft model
  6. tune \(\gamma\) or the tree budget on real traffic: maximize formula (129.2), not the acceptance rate

The code below builds a tiny target model that accepts any attention mask and position ids, makes a slightly noisy copy of it as the drafter, imitates Medusa heads (top-\(s_k\) guesses for each future position, fixed per step), builds the Cartesian tree, the mask (129.6) and the position ids, and verifies all branches in one target pass. The final check: the output is identical to plain greedy decoding, for every tree shape.

import itertools, torch, torch.nn as nn
torch.manual_seed(0)
V, D = 40, 64

class TinyLM(nn.Module):
    """A small causal LM that accepts any attention mask and any position ids."""
    def __init__(self):
        super().__init__()
        self.emb, self.pos = nn.Embedding(V, D), nn.Embedding(128, D)
        self.attn = nn.ModuleList([nn.MultiheadAttention(D, 4, batch_first=True) for _ in range(2)])
        self.mlp = nn.ModuleList([nn.Sequential(nn.Linear(D, 4 * D), nn.GELU(), nn.Linear(4 * D, D)) for _ in range(2)])
        self.norm, self.head = nn.LayerNorm(D), nn.Linear(D, V)
    def forward(self, ids, pos, allow):            # allow[i, j] = True: token i may look at token j
        x = self.emb(ids)[None] + self.pos(pos)[None]
        for a, m in zip(self.attn, self.mlp):
            h = self.norm(x)
            x = x + a(h, h, h, attn_mask=~allow)[0]
            x = x + m(self.norm(x))
        return self.head(self.norm(x))[0]          # (tokens, V) logits

def causal(n):
    return torch.ones(n, n, dtype=torch.bool).tril()

target = TinyLM().eval()
draft = TinyLM().eval()
draft.load_state_dict(target.state_dict())
with torch.no_grad():                              # the draft = the target plus noise: often right, not always
    for p in draft.parameters():
        p.add_(0.05 * torch.randn_like(p))

@torch.no_grad()
def greedy(prefix, n):                             # reference: plain one-token-at-a-time greedy decoding
    ids = list(prefix)
    for _ in range(n):
        t = torch.tensor(ids)
        ids.append(target(t, torch.arange(len(ids)), causal(len(ids)))[-1].argmax().item())
    return ids[len(prefix):]

@torch.no_grad()
def medusa_like_heads(ids, ks):                    # head k gives top-ks[k] guesses for position +k+1
    ids, cand = list(ids), []
    for k in ks:                                   # imitate heads: roll the draft greedily, keep top-k per step
        t = torch.tensor(ids)
        logits = draft(t, torch.arange(len(ids)), causal(len(ids)))[-1]
        cand.append(logits.topk(k).indices.tolist())
        ids.append(cand[-1][0])
    return cand

def build_tree(cand):                              # Cartesian product, formula (129.7): one node per prefix path
    nodes = []                                     # each node = a tuple of tokens from the root
    for d in range(1, len(cand) + 1):
        nodes += list(itertools.product(*cand[:d]))
    return nodes

def tree_mask(n_prefix, nodes):                    # formula (129.6)
    n = n_prefix + len(nodes)
    allow = torch.zeros(n, n, dtype=torch.bool)
    allow[:n_prefix, :n_prefix] = causal(n_prefix)
    index = {path: n_prefix + i for i, path in enumerate(nodes)}
    for path, i in index.items():
        allow[i, :n_prefix] = True                 # every node sees the whole prefix
        for d in range(1, len(path) + 1):
            allow[i, index[path[:d]]] = True       # ... and its ancestors and itself, nothing else
    return allow, index

@torch.no_grad()
def tree_step(ids, ks):
    nodes = build_tree(medusa_like_heads(ids, ks))
    allow, index = tree_mask(len(ids), nodes)
    toks = torch.tensor(list(ids) + [p[-1] for p in nodes])
    pos = torch.tensor(list(range(len(ids))) + [len(ids) + len(p) - 1 for p in nodes])
    pred = target(toks, pos, allow).argmax(-1)     # ONE target pass checks every branch
    path, nxt = (), pred[len(ids) - 1].item()      # the target's own next token after the prefix
    while path + (nxt,) in index:                  # walk down while the target agrees with a child
        path = path + (nxt,)
        nxt = pred[index[path]].item()
    return list(path) + [nxt], len(nodes)          # accepted tokens + one bonus token from the target

prefix, N = [1, 2, 3, 4], 40
for ks in [(1, 1, 1, 1), (2, 2, 2), (3, 2, 2)]:
    out, steps, nodes = list(prefix), 0, 0
    while len(out) - len(prefix) < N:
        new, n = tree_step(out, ks)
        out += new; steps += 1; nodes = n
    out = out[len(prefix):len(prefix) + N]
    print(ks, "tree nodes", nodes, "target passes", steps,
          "tokens/pass", round(N / steps, 2), "same as greedy:", out == greedy(prefix, N))
# (1, 1, 1, 1) tree nodes 4 target passes 29 tokens/pass 1.38 same as greedy: True
# (2, 2, 2) tree nodes 14 target passes 20 tokens/pass 2.0 same as greedy: True
# (3, 2, 2) tree nodes 21 target passes 20 tokens/pass 2.0 same as greedy: True

The printed lines show the lossless property directly (“same as greedy: True”), and that the 14-node tree needs 20 target passes for 40 tokens instead of 29 for a 4-token chain. The 21-node tree is no better here: extra width helps only where the drafter’s second and third guesses are actually right, which is what EAGLE-2’s dynamic trees try to predict. In a real system, the prefix would come from the KV cache instead of being recomputed, and the rejected nodes’ KV entries would be discarded.

Where this is used

SettingDrafter that fitsWhy
Chat serving at small batch (vLLM, SGLang, TensorRT-LLM)EAGLE-style drafter or Medusa heads, with a tree [Likely]Decode is memory-bound, so verification of a small tree is nearly free
DeepSeek-V3 and other MTP-trained modelsthe model’s own MTP moduleNo extra training; 85–90% acceptance for the second token [Certain]
Code editing, summarization, document QAprompt lookup (n-gram) draftingThe output repeats long spans of the input
Video-RAG answers and video QA over transcriptsprompt lookup over the retrieved transcript or clip captionsAnswers quote names, times and events from the retrieved text (Figure 5)
Dense video captioning and key-moment reportsprompt lookup over earlier captions, or a small draft modelCaptions of nearby segments repeat entities and phrases [Speculation]
VLM chat (image or video + text)an EAGLE-style drafter trained on the VLM’s features, or a small VLM of the same family [Likely]After the visual prefill, decoding is the same memory-bound loop as for text LLMs
On-device and laptop inference (llama.cpp)a small draft model of the same family [Likely]Memory bandwidth is very limited, so each saved target pass matters
Offloaded or distributed servingtree drafts from small models (SpecInfer)Each target pass is very slow, so checking many branches per pass pays well: 2.6–3.5× reported for offloading [Certain]

Common mistakes

  • Measuring acceptance instead of speed. A bigger drafter or a bigger tree raises acceptance but also raises \(c\) or the verification cost. Optimize formula (129.2) on wall-clock time.
  • Expecting the same gain at large batch. At large batch, decoding becomes compute-bound and the extra tree tokens are no longer free. Gains shrink and can become a slowdown. Many servers turn speculation off or shrink \(\gamma\) as load grows [Likely].
  • Wrong position ids in the tree. Sibling nodes must share the position of their depth. Using flattened indices gives different numbers from normal decoding, and the “lossless” property silently breaks.
  • Calling typical acceptance lossless. Medusa’s typical acceptance (129.5) changes the output distribution. Only greedy matching and the rejection-sampling rule (and SpecInfer’s multi-step version) are exact.
  • Forgetting to roll back the KV cache. After verification, the KV entries of rejected nodes (and of the drafter’s rejected steps) must be removed, or the next step attends to tokens that were never accepted.
  • A drafter with a different tokenizer. The target verifies token ids. A drafter from another family produces ids that mean other strings.
  • Training the drafter on the wrong data. A drafter learns to predict the target. Training it on generic text instead of the target’s own outputs (or its features) lowers \(\alpha\), especially after the target was fine-tuned.
  • Prompt lookup on open-ended chat. When the answer does not copy the input, nearly every proposal is rejected; you pay the extra verification tokens for nothing.

Interview questions

Name the main kinds of drafter for speculative decoding and one trade-off of each.basic
(1) A separate small model with the same tokenizer: flexible, but you host and align a second model with its own KV cache, and its draft steps cost \(c \gt 0\). (2) Medusa heads on the target: almost free to run and simple to train, but far heads guess without knowing the intermediate tokens, so they are weak. (3) EAGLE feature-level drafter: one decoder layer that sees the target’s features and the next token; high acceptance, small cost, but needs training per target. (4) No model (prompt lookup, Lookahead): no training at all; prompt lookup only helps when the output copies the input, Lookahead spends extra compute in every pass. (5) MTP heads trained in pretraining (DeepSeek-V3): a free, well-aligned drafter, but only if you control pretraining.
How is a Medusa head built, and how is it initialized?core
Head \(k\) is one residual feed-forward layer followed by an output matrix: \(p^{(k)}_t = \softmax(W_2^{(k)}(\operatorname{SiLU}(W_1^{(k)}\mathbf{h}_t) + \mathbf{h}_t))\). It reads the target’s last hidden state and predicts the token \(k + 1\) positions ahead. \(W_1\) starts at zero and \(W_2\) as a copy of the LM head, so at the start every head equals the normal next-token head. Medusa-1 trains only the heads, with loss weights \(0.8^k\); Medusa-2 also fine-tunes the backbone.
Explain tree attention. What must change in the attention mask and in the positions?core
All tree nodes are appended after the accepted prefix in one sequence. Each node may attend to the whole prefix, to its ancestors and to itself, and to nothing else, so branches do not see each other (formula 129.6). Each node gets the position id of its depth (prefix length + depth − 1), so siblings share a position. With these two changes, the output at every node equals what normal decoding would compute for that branch, and one target pass verifies all branches. Afterwards only the accepted path’s KV entries are kept.
How many tokens does the target process for a Medusa tree with top-3, top-2, top-2 guesses? How many candidates are there?basic
Formula (129.7): nodes \(= 3 + 3 \cdot 2 + 3 \cdot 2 \cdot 2 = 3 + 6 + 12 = 21\); candidates \(= 3 \cdot 2 \cdot 2 = 12\) complete paths. The target processes 21 tree tokens (plus the prefix from the KV cache) in one pass.
What does EAGLE predict, and why does it also take the token one step ahead as input?advanced
EAGLE predicts the target’s next top-layer feature (the input to the LM head), then turns it into token guesses with the frozen LM head. Features are smoother and easier to predict than tokens. But with sampling, the feature \(\mathbf{f}_i\) does not determine which token was sampled next, and the next feature depends on that token. Feeding the token sequence advanced by one step, \(e(t_{2:i+1})\), together with \(\mathbf{f}_{1:i}\), removes that uncertainty. Training uses a Smooth L1 loss on the feature plus 0.1 times a cross-entropy on the token.
When is a wide tree better than a long chain?advanced
When the drafter’s top-1 guess is often wrong but the right token is often in its top few. Then a chain dies early, while a tree keeps several alternatives alive at each depth. With the toy model (129.8), \(a = 0.6\), \(r = 0.85\): a 14-node tree \((2,2,2)\) accepts 1.91 tokens per pass versus 1.11 for a 14-node chain. With a strong drafter (\(a = 0.9\), \(r = 0.95\)) the chain wins (3.77 vs 2.89). EAGLE-2 uses the drafter’s confidence to pick the shape per context.
You verify a draft tree with the normal causal mask and flattened position ids. What happens?core
Each node then also attends to every node placed before it in the flattened order, including siblings and cousins on other branches, and gets a position id that is too large. The target computes its next-token distribution for a text that never existed, so the predictions at the nodes are wrong. The walk down the tree still accepts some tokens, but they are not the target’s greedy choices: the output silently differs from plain decoding. In Figure 4 the “plain causal” setting turns “took the ball past two defenders …” into “took the ball went wide . a ball went wide …”. The fix is the tree mask (129.6) plus depth-based position ids.
Is Medusa lossless?core
With greedy verification or the standard rejection-sampling rule, yes: the heads only propose, the target decides. With Medusa’s typical acceptance rule (accept if \(p_{\text{target}}(x) \gt \min(\varepsilon, \delta e^{-H})\)), no: it accepts tokens the exact rule would sometimes reject, trading exactness for speed. Medusa-2 also changes the target itself, because the backbone is fine-tuned jointly, so the “target distribution” is that of the fine-tuned model.
What is prompt lookup decoding, and when would you turn it on?basic
It drafts by string matching: find the last n-gram of the text so far earlier in the prompt, and propose the tokens that followed it. No new weights and nearly zero draft cost. Turn it on for input-grounded tasks: summarization, RAG and Video-RAG answers that quote sources, code editing, document QA. The author reports about 2.4× on summarization and context QA with Mistral-7B; on open-ended chat the gain is small.
How does Lookahead decoding get guesses without any draft model?advanced
It runs Jacobi iterations inside the decoding loop: it keeps a window of guessed future tokens and updates them all in parallel with the target (formula 129.12). These half-converged trajectories produce n-grams, which go into a pool. In the same pass, a verification branch checks pool n-grams that start with the current last token, using a suitable attention mask. Accepted n-grams advance the output several tokens at once, and the result equals greedy decoding. It spends extra compute per pass, so it suits memory-bound decoding.
DeepSeek-V3 reports 85–90% acceptance of the second token and 1.8× tokens per second. Are these numbers consistent?core
Yes. With one drafted token, each target pass yields \(1 + \alpha\) tokens on average, which is 1.85 to 1.90. The reported 1.8× is slightly below, which matches a small cost for running the MTP block and verifying (the \(1 + \gamma c\) term). The MTP module itself is one transformer block on \([\operatorname{RMSNorm}(\mathbf{h}); \operatorname{RMSNorm}(\operatorname{Emb}(t_{i+1}))]\) with a shared embedding and output head.
Your speculative decoding gives 2.5× at batch 1 but a slowdown at batch 64. Why, and what do you do?advanced
At batch 1 decoding is memory-bound: verifying 5 or 20 tokens costs about the same as 1, so accepted tokens are almost free. At batch 64 the GPU is closer to compute-bound; every extra tree token now costs real compute for every sequence, and rejected tokens are pure waste. Fixes: shrink \(\gamma\) or the tree budget as the batch grows, turn speculation off above a threshold, use a drafter with higher acceptance so less compute is wasted, and measure end-to-end throughput, not acceptance.

Exercises

  1. A drafter has \(\alpha = 0.7\) and \(c = 0.1\). Compute the tokens per target pass and the speedup for \(\gamma = 3\). Check in Figure 1.
  2. Count the nodes and candidates of a Medusa tree with \((s_1, s_2) = (4, 2)\) and of \((3, 3, 3)\).
  3. In the toy model (129.8) with \(a = 0.6\) and one head (\(D = 1\)), what is the survival chance with \(s_1 = 2\) and with \(s_1 = 3\)?
  4. Write the tree attention mask among the tree tokens for \((s_1, s_2) = (2, 2)\), with nodes ordered 1a, 1b, 1a-2a, 1a-2b, 1b-2a, 1b-2b. Which position ids do they get after a prefix of 10 tokens?
  5. Why does a Medusa head for position \(t + 3\) usually have lower accuracy than an EAGLE draft step for the same position?
  6. In Figure 5, which step is the first one with a 3-gram match, and how many tokens does it add?
Answerscheck
1. \((1 - 0.7^4)/0.3 = 0.7599/0.3 = 2.53\) tokens per pass; speedup \(= 2.53/(1 + 0.3) = 1.95\). 2. \((4, 2)\): \(4 + 8 = 12\) nodes, 8 candidates. \((3,3,3)\): \(3 + 9 + 27 = 39\) nodes, 27 candidates. 3. \(1 - 0.4^2 = 0.84\) and \(1 - 0.4^3 = 0.936\). 4. Rows (who looks) and columns (looked at), 1 = allowed: 1a: [1,0,0,0,0,0]; 1b: [0,1,0,0,0,0]; 1a-2a: [1,0,1,0,0,0]; 1a-2b: [1,0,0,1,0,0]; 1b-2a: [0,1,0,0,1,0]; 1b-2b: [0,1,0,0,0,1]. All rows also see the 10 prefix tokens. Position ids: 10, 10, 11, 11, 11, 11 (counting from 0). 5. The Medusa head reads only \(\mathbf{h}_t\) and must guess \(t+3\) without knowing the tokens at \(t+1\) and \(t+2\); its guess is the same for every branch. An EAGLE draft step for \(t + 3\) is conditioned on the tokens already drafted for \(t + 1\) and \(t + 2\), and on predicted features, so it follows the branch. 6. Step 5: the tail “the final minute” matches, the proposal “of extra time and” is fully accepted, and the target adds “the”: 5 tokens.

Key takeaways

  • All drafters are judged by formula (129.2): high acceptance \(\alpha\) at low draft cost \(c\), while verification stays cheap (memory-bound, small batches).
  • Medusa (129.3) adds cheap heads that guess several positions from one hidden state; since far heads cannot see the branch, it verifies a Cartesian tree of their top guesses.
  • Tree attention (129.6) plus depth position ids lets one target pass verify every branch exactly; tree size follows (129.7). Wide trees help weak drafters, long chains help strong ones (129.8).
  • EAGLE (129.9) drafts the target’s features with one decoder layer and feeds the next token to remove sampling uncertainty; EAGLE-2 makes trees dynamic, EAGLE-3 fuses several layers.
  • MTP heads (129.10, 129.11) trained in pretraining are a built-in drafter: DeepSeek-V3 reports 85–90% second-token acceptance and 1.8× tokens per second.
  • Prompt lookup (copy from the input) and Lookahead decoding (Jacobi n-grams read along the diagonals of a 2D window, 129.12–129.14) need no draft model at all.
  • Greedy matching and rejection sampling (including SpecInfer’s multi-step version) are lossless; Medusa’s typical acceptance is not.

Key formulas

\[ \text{speedup} = \frac{1 - \alpha^{\gamma+1}}{(1-\alpha)(1+\gamma c)}, \qquad N_{\text{nodes}} = \sum_{d=1}^{D}\prod_{i=1}^{d} s_i \]
\[ p_t^{(k)} = \softmax\big(W_2^{(k)}(\operatorname{SiLU}(W_1^{(k)}\mathbf{h}_t)+\mathbf{h}_t)\big), \qquad \hat{\mathbf{f}}_{i+1} = g_\phi\big(\mathbf{f}_{1:i}, e(t_{2:i+1})\big) \]

References for this session

  1. Cai et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads
  2. Li et al. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty
  3. Fu et al. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding
  4. Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
  5. Gloeckle et al. (2024). Better & Faster Large Language Models via Multi-token Prediction
  6. Cai et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads
  7. Li et al. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty
  8. Li, Wei, Zhang, Zhang (2024). EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees
  9. Li et al. (2025). EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test
  10. Fu et al. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding
  11. Saxena (2023). Prompt Lookup Decoding (GitHub repository)
  12. Miao et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification
  13. Gloeckle et al. (2024). Better & Faster Large Language Models via Multi-token Prediction
  14. DeepSeek-AI (2024). DeepSeek-V3 Technical Report
  15. Leviathan et al. (2022). Fast Inference from Transformers via Speculative Decoding
  16. Chen et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling
  17. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models