Faster Decoding

A frontier model running at batch size one spends most of its time waiting. To produce a single token it streams every weight from high-bandwidth memory into the accelerator's compute units, multiplies once, and discards them. The matrix multiplications are skinny, a vector against each weight matrix, so the chip finishes the math long before the next slab of weights arrives, then sits idle waiting on memory. Chapter 31 and Chapter 32 establish this wall from the serving side: decode is memory-bound, its arithmetic intensity far below what the hardware can sustain. Faster decoding uses that idle arithmetic to break the one-token-per-pass rule: a cheap process guesses several future tokens, and one target pass verifies several guesses at once. Decoding a token means sampling it from the probability distribution the model places over its vocabulary, so the target distribution is just those next-token probabilities the expensive model produces. speculative decoding is the exact version of that pattern: a draft model proposes tokens, the target model verifies them in parallel, and the target distribution stays unchanged. Medusa, Hydra, the EAGLE line, lookahead decoding, and multi-token prediction differ mainly in where the guess comes from. The speedup is not a property of the method alone. It holds in the small-batch memory-bound regime where spare FLOPs are real, and can disappear once serving becomes compute-bound.

The Common Move

Autoregressive generation has a sequential bottleneck that looks fundamental: decoding $K$ tokens takes $K$ forward passes, each waiting on the one before it. The bottleneck bites hardest exactly where latency is felt most. Reasoning models from Chapter 30 emit long chains of intermediate tokens before an answer, so wall-clock latency is dominated by the sheer count of sequential decode steps.

The single idea behind everything in this chapter is to trade extra parallel compute for fewer sequential steps. A cheap process guesses several future tokens, the expensive model checks all of them in one forward pass, and every guess that survives the check is a token produced without its own sequential step. Because a forward pass over $\gamma$ candidate tokens costs almost the same as a pass over one, the spare compute is nearly free.

Two quantities govern the payoff. The acceptance rate $\alpha$ is the fraction of draft tokens the target keeps; the draft cost is how much cheaper the guesser is than the target. The expected number of tokens produced per target pass rises with $\alpha$, so the whole game is to make the draft both cheap and well aligned with the target, and to verify many candidates at once. Two questions organize the rest of the chapter: where the guess comes from, and how the check stays correct.

Figure 33.1 makes the payoff concrete. With acceptance rate $\alpha$ and a draft of $\gamma$ tokens checked in one pass, the expected tokens emitted per target pass is the geometric sum $(1 - \alpha^{\gamma+1}) / (1 - \alpha)$, rising from one when nothing is accepted toward $\gamma + 1$ when everything is. A longer draft helps only when $\alpha$ is high, because an early rejection wastes the whole tail.

Try simulating the accept/reject loop directly and watch the Monte Carlo average converge to the closed-form geometric sum.

import numpy as np
rng = np.random.default_rng(0)
alpha, gamma, trials = 0.7, 4, 50000

def simulate():
    emitted = np.ones(trials)            # the corrected/bonus token
    alive = np.ones(trials, dtype=bool)  # runs not yet rejected
    for _ in range(gamma):
        accept = (rng.random(trials) < alpha) & alive
        emitted += accept                # count each accepted draft token
        alive &= accept                  # stop at first rejection
    return emitted.mean()

closed_form = (1 - alpha**(gamma + 1)) / (1 - alpha)
print(f"simulated mean tokens/pass: {simulate():.4f}")
print(f"closed-form  tokens/pass:   {closed_form:.4f}")

Keeping the check exact

The decisive design choice is how the verification preserves correctness, and the answer that made the method safe to deploy is that it can be made exact. speculative decoding, introduced independently by Leviathan et al. (Leviathan et al. 2023) and Chen et al. (Chen et al. 2023), guarantees this. A small draft model proposes a continuation of $\gamma$ tokens. The target model scores all $\gamma$ positions in one parallel pass, yielding its own distribution $p$ at each position alongside the draft's distribution $q$. A modified rejection sampling rule then accepts or rejects each draft token left to right: token $x$ proposed from $q$ is accepted with probability $\min(1, p(x)/q(x))$, and on the first rejection a corrected token is resampled from the residual distribution $\max(0, p - q)$, renormalized. That residual keeps only the probability mass the target wanted that the draft under-supplied, which is exactly what repairs the distribution at the rejected position. The theorem behind the rule is that the accepted stream is distributed exactly as if it had been sampled from $p$ token by token (Leviathan et al. 2023). The speedup is real and the output distribution is untouched. The method is not an approximation of the model, it is the same model sampled in a different order.

Figure 33.3 draws this loop. The line of accept/reject decisions it shows is the simplest case, a single linear continuation. The self-draft methods below replace that line with a tree.

The search for the guess

The lineage of these methods tracks where the guess comes from, moving from a separate model toward parts of the target itself, and finally into how the target is trained.

A second, smaller model

The first answer was a second, smaller model. Leviathan et al. and Chen et al. both used an off-the-shelf draft model from the same family as the target, for example a small Chinchilla drafting for a 70B Chinchilla (Chen et al. 2023). This needs no change to the target and is provably lossless, but it requires training, hosting, and aligning a second model, and a poorly matched draft has a low acceptance rate.

Heads on the target itself

Medusa (Cai et al. 2024) removed the separate model. Instead of a draft network it bolts several lightweight decoding heads onto the target's last hidden state, each head predicting one further future token in parallel. The candidates the heads produce form a tree, and a tree-structured attention mask lets the target verify many branches of that tree in a single pass rather than a single linear continuation. Medusa's heads predict each future token independently of the others, which caps how coherent a multi-token guess can be. It also offers a typical-acceptance scheme that relaxes exact sampling for more speed, so Medusa in that mode is deliberately not distribution-preserving, a different bargain from speculative decoding's exactness (Cai et al. 2024).

Hydra (Ankner et al. 2024) fixed the independence limitation. Its draft heads are sequentially dependent: the head predicting the third token sees what the second head proposed, so the multi-token guess is internally coherent and the acceptance rate rises. The EAGLE line pushed further on what the draft should predict. EAGLE (Li et al. 2024) observed that autoregression is more regular at the feature level, the second-to-top-layer hidden state, than at the token level, so it drafts by predicting the next feature and then mapping it to a token, resolving the uncertainty by feeding in the token already sampled one step ahead. Its successor, EAGLE-2 (Li et al. 2024), turned the verification tree dynamic: because a draft token's acceptance depends on context and not only on its position, it expands the draft tree where the draft is confident and prunes it where it is not. By EAGLE-3 (Li et al. 2025), feature prediction was gone, replaced by direct token prediction over a fusion of low, middle, and high layers, trained with a procedure the authors call training-time test, which lets the drafter keep improving as its training data grows.

The Draft-Free Route

A parallel branch removed the draft entirely. Lookahead decoding (Fu et al. 2024) reframes autoregressive generation as solving a nonlinear system by Jacobi iteration, a fixed-point sweep that updates a whole window of future positions at once and collects the n-grams the iteration produces along the way. A verification branch then checks those n-grams against the target in the same step. There is no draft model and no extra trained heads; the parallelism comes from the fixed-point structure of the problem, and the method is exact.

The guess can also be retrieved rather than computed. Prompt-lookup decoding matches the last few tokens of the generation against the prompt and proposes the n-gram that followed there, a drafter with no model at all (Saxena 2023). It ships as a standard speculative method in vLLM and TensorRT-LLM and is strongest where output copies input: retrieval-augmented answers, editing, and code.

Training the guess in

The last move folds the guess into training. Multi-token prediction (Gloeckle et al. 2024) trains the base model with several output heads on a shared trunk so that each position predicts the next $n$ tokens at once. The authors found this improves sample efficiency as an auxiliary objective, and crucially the extra heads double as a built-in drafter at inference time. DeepSeek-V3 (DeepSeek-AI 2024) carries this into a frontier system: its MTP module is trained alongside the main model and then reused for speculative decoding, reported to accept its second predicted token 80% to 90% of the time and to raise generation throughput by roughly 1.8 times.

Figure 33.4 traces that search.

When the Speedup Holds

Every method here buys fewer sequential steps with more parallel compute and more memory traffic for verification. The boundaries are where that trade stops paying, and the sharpest of them is set by the serving regime rather than the method.

Figure 33.5 shows why the same method can help or hurt. At small batch the accelerator's compute units sit idle waiting on weights, so the FLOPs speculation spends to verify candidates were going to waste anyway, and they are free. At large batch the weights are amortized across many sequences and the compute units are already saturated, so verifying tokens that then get rejected competes with real work for FLOPs and can lower total throughput. The premise of the whole chapter, that decode is memory-bound, holds only in the small-batch regime.

Three further trades sit underneath this one, and they are worth naming because they explain why the lineage moved the way it did.

• Acceptance versus draft cost. A larger or better-trained drafter raises the acceptance rate but costs more per proposal. The optimal draft is the cheapest one whose acceptance is high enough that the saved target passes outweigh the draft's own cost. This is why self-draft heads and feature-level drafting won out: they are nearly free yet aligned with the target. Figure 33.6 shows the optimum this implies: as the draft grows longer the cost-adjusted speedup rises, peaks, then falls, because past some length the extra verification work outweighs the tokens it wins back, and a cheaper drafter pushes that peak to longer drafts.
• Tree width versus waste. Verifying a wider tree of candidates accepts more tokens per pass but burns compute on branches that will be rejected. Dynamic trees, as in EAGLE-2, exist to spend that width only where the draft is confident.

• Lossless versus lossy. Speculative decoding, lookahead, and the EAGLE line preserve the target's output distribution exactly. Medusa's typical-acceptance mode trades that exactness for speed. Multi-token prediction changes training, not the sampling guarantee. Whether a lossy shortcut is acceptable is an application decision, not a property the serving system gets for free.

Inside the verification step

The verification step is the part worth seeing concretely, because it is where correctness lives. Given draft tokens $x_1, \dots, x_\gamma$ from $q$ and the target's distributions $p_1, \dots, p_{\gamma}$ from one parallel pass, the accept loop is short:

for i in range(gamma):
    r = uniform(0, 1)
    if r < min(1, p[i][x[i]] / q[i][x[i]]):
        emit(x[i])              # accepted, no extra target step
    else:
        emit(sample(normalize(relu(p[i] - q[i]))))  # corrected token
        break                   # stop at first rejection
# if all gamma accepted, sample one bonus token from p[gamma]

The two details that make it exact are the residual $\max(0, p - q)$ resampling on rejection and the bonus token after a full-accept run; together they are what the distribution-preservation theorem requires. For the self-draft and tree-based methods, the same accept logic runs over a tree rather than a line: a tree attention mask lets the single target pass score every branch, and the longest accepted path through the tree is emitted. Figure 33.7 shows why this beats a linear draft. A linear draft commits to one continuation, so a single early rejection wastes everything after it. A tree hedges across several continuations at each position, and the tree attention mask scores all of them in the one target pass for almost the cost of one. The target then emits the longest path whose every token was accepted.

Operationally, serving stacks expose this as a drafter choice. A separate draft model is a second checkpoint to load and schedule. With EAGLE-style and Medusa-style drafters, the artifact shrinks to a small head module trained against a frozen target and loaded beside it. Multi-token-prediction drafting, as in DeepSeek-V3, needs no separate artifact at all because the heads were trained into the model. The practical failure mode is a drafter whose acceptance rate is too low for the workload, at which point speculation adds latency instead of removing it, which is why acceptance rate is the metric to watch in production rather than the headline speedup from a paper.

Further reading