SPECULATIVE DECODING

The loop:

1. DRAFT   run a cheap model autoregressively for gamma steps,
           producing candidate tokens x1..x_gamma and its
           distributions q(.|prefix), q(.|prefix,x1), ...

2. VERIFY  run the target model ONCE on [prefix, x1, ..., x_gamma].
           Because attention is causal, one pass gives you the target's
           distribution p at every one of those positions simultaneously.

3. ACCEPT  walk left to right, accepting or rejecting each x_i by the
           rule in the next concept. Stop at the first rejection.

4. On rejection at position i, sample a corrected token from a residual
   distribution. On accepting all gamma, sample one bonus token from
   p(.|prefix, x1..x_gamma) -- which you already have.

Step 2 is the crux. A single forward pass over γ+1 positions costs the same weight traffic as a forward pass over one position. You read all 15 GB either way. The extra positions cost extra arithmetic — which you had in surplus.

Per accepted token, the cost falls dramatically. If you accept 3 of 4 drafts plus a bonus token, you produced 4 tokens for one target-model pass instead of four passes. Four times fewer weight reads.

Note also step 4's bonus token. If every draft is accepted, the verification pass has already computed p at the final position, so you get one extra token for free. This is why the expected yield formula has γ+1 in it rather than γ, and it is a meaningful contribution at high acceptance rates.

Two things this does not do, worth being clear about. It does not reduce total FLOPs — it increases them, since drafts that get rejected were computed for nothing. And it does not help when you are already compute-bound, because then there is no idle arithmetic to spend. Both qualifications become important later in this module.

The naive approach — accept the draft token if the target agrees, otherwise take the target's token — is wrong. It biases the output toward tokens the draft model likes, because the draft gets a veto over which tokens are even considered.

The correct rule is modified rejection sampling. Let q be the draft's distribution and p the target's, at some position, with draft token x:

1. accept x with probability  min(1, p(x) / q(x))
2. if rejected, sample from the residual:

       p'(z) = max(0, p(z) - q(z)) / sum_w max(0, p(w) - q(w))

Read the intuition first. If the target likes x at least as much as the draft did (p(x) ≥ q(x)), accept unconditionally. If the target likes it less, accept with probability p/q — proportionally to how much less. When you reject, you must not simply sample from p, because you would double-count the mass p and q already agreed on. The residual max(0, p−q) is precisely the mass p wanted that q under-supplied.

The proof. Compute the total probability of emitting token z.

Accepting z requires drafting it and then accepting:

P(draft z and accept) = q(z) * min(1, p(z)/q(z)) = min(q(z), p(z))

Rejection happens with probability:

P(reject) = 1 - sum_w min(q(w), p(w))

And a useful identity, since both p and q sum to 1:

sum_w max(0, p(w) - q(w)) = sum_w [ p(w) - min(p(w), q(w)) ]
                          = 1 - sum_w min(p(w), q(w))
                          = P(reject)

The normalizer of the residual is exactly the rejection probability. So:

P(emit z) = min(q(z), p(z))  +  P(reject) * max(0, p(z) - q(z)) / P(reject)
          = min(q(z), p(z))  +  max(0, p(z) - q(z))

Two cases. If p(z) ≤ q(z): = p(z) + 0 = p(z). If p(z) > q(z): = q(z) + p(z) − q(z) = p(z).

P(emit z) = p(z) in both cases. The output distribution is the target model's, exactly, regardless of how bad the draft model is. ∎

This is why speculative decoding is free performance rather than a quality trade. A poor draft model does not corrupt your output — it just gets rejected more often and saves you less. The draft affects speed only. That property is unusual enough in this field to be worth pausing on: almost every other optimization here asks you to give something up.

(One caveat for practice: the proof assumes p and q are the distributions you are actually sampling from. If you apply top-p or temperature, both must see the same processed distribution, or you lose the guarantee. Implementations that apply sampling parameters to the target but not the draft are subtly wrong — and it is a common bug because the output still looks fine.)

Let α be the acceptance rate: the probability that a given draft token survives. Leviathan et al. show that under a reasonable independence assumption, the expected number of tokens produced per verification pass is:

E[tokens] = (1 - alpha^(gamma+1)) / (1 - alpha)

The γ+1 accounts for the bonus token you get when all γ drafts are accepted.

Tabulate it:

Two patterns matter.

Returns diminish sharply. At α = 0.5, going from γ = 3 to γ = 10 improves yield from 1.88 to 2.00 — 7% more tokens for 233% more draft work. The limit as γ → ∞ is 1/(1−α), so α = 0.5 can never exceed 2 tokens per pass no matter how far you draft.

Acceptance rate matters far more than draft length. Moving α from 0.7 to 0.9 at γ = 4 takes you from 2.77 to 4.10 — a 48% gain. Moving γ from 4 to 10 at α = 0.7 gains 18%. If you are tuning, tune the draft model, not the draft length.

Now the actual speedup, which must account for the cost of drafting. Let c be the draft model's cost as a fraction of the target's:

                E[tokens]           (1 - alpha^(gamma+1)) / (1 - alpha)
speedup  =  ----------------  =  ------------------------------------
             gamma * c + 1                  gamma * c + 1

The denominator is the cost of one speculation round in units of target passes: γ draft passes at cost c each, plus one verification.

Break-even is where the speedup equals 1:

(1 - alpha^(gamma+1)) / (1 - alpha)  =  gamma * c + 1

Worked cases at γ = 4:

alpha = 0.8, c = 0.05 (a 1B draft for a 70B target):
    3.36 / (0.20 + 1) = 2.80x    strong win

alpha = 0.8, c = 0.15 (a 7B draft for a 70B target):
    3.36 / (0.60 + 1) = 2.10x    still good

alpha = 0.5, c = 0.15:
    1.94 / (0.60 + 1) = 1.21x    marginal

alpha = 0.4, c = 0.30:
    1.64 / (2.20)     = 0.75x    LOSS -- slower than not speculating

The last row is the important one. Speculation can make you slower, and it does so silently — the output is still correct, it just costs more. Any deployment should measure the realized acceptance rate rather than assume it.

Acceptance rate is not a constant, either. It varies by domain (code drafts better than creative prose, because it is more predictable), by position (the token after "def " is easy, the token starting a new idea is hard), and by sampling temperature (higher temperature flattens p, which reduces agreement). Good implementations adapt γ dynamically based on recent acceptance.

Classical speculative decoding needs a second model, and that has real costs: extra weights in memory competing with your KV cache, extra weight bytes streamed per draft step, and the requirement that the draft be well-aligned with the target — a 1B model drafting for a 70B model from a different family will have poor α. Self-speculation avoids all three.

Medusa attaches extra decoding heads to the target model's final hidden state. Head k predicts the token k positions ahead. One forward pass produces the current token plus several speculative future tokens, with no separate model at all. Because the heads are individually weak, Medusa proposes multiple candidates per position and verifies them as a tree rather than a single chain. The heads are cheap to train — the backbone is frozen.

The trade: independent heads cannot condition on each other, so head 3's guess does not know what head 2 guessed. Accuracy falls off with distance.

EAGLE fixes that by autoregressing at the feature level rather than the token level. It runs a small autoregressive head over the target model's second-to-top-layer hidden states, using both the feature sequence and the token sequence one step shifted. Because the features are far more informative than tokens, a very small head achieves high acceptance — EAGLE reports substantially better acceptance rates than Medusa, and successive versions (EAGLE-2's dynamic draft trees, EAGLE-3's training changes) have pushed it further. EAGLE is currently the strongest general self-speculation approach and is supported in the major serving engines.

N-gram / prompt lookup decoding is the cheapest idea in the family and requires no model at all. Search the existing context for the current suffix; if you find it, propose whatever followed it last time. Zero training, zero extra parameters, near-zero cost.

It sounds too crude to work, and for open-ended chat it largely does not. But for high-repetition workloads it is excellent: code editing where most of a file is unchanged, summarization that quotes the source, RAG where the answer copies from retrieved documents, structured output with a fixed schema. In those settings acceptance rates can be very high, and since c ≈ 0 the break-even condition is trivially satisfied. It is worth trying first precisely because it costs nothing to try.

Tree attention is the shared machinery for Medusa and EAGLE. Rather than verifying one candidate sequence, verify a tree of them in a single pass, using a carefully constructed attention mask so each node attends only to its ancestors. Verifying 64 tree nodes costs one forward pass, and the probability that some path through the tree is accepted is much higher than for a single chain. The cost is a more complex mask and more arithmetic — again, arithmetic you were not using.

The single most important practical caveat, and the one most often missed.

Speculation is free because decode has idle arithmetic. But batching consumes that same idle arithmetic — recall from Module 4 that decode arithmetic intensity equals batch size. The two techniques are drawing on one pool of spare compute.

batch 1, no speculation:      intensity ~1     ridge 295   0.3% used
batch 1, gamma=4 speculation: intensity ~5                 1.7% used
batch 64, no speculation:     intensity ~64               22%   used
batch 64, gamma=4:            intensity ~320             OVER the ridge

At batch 64 with γ = 4, verification processes 64 × 5 = 320 positions per pass. You have crossed the ridge point and become compute-bound — at which point the extra positions are no longer free, they cost time proportional to their count.

Now add the second problem: rejected drafts are wasted work. At batch 1 that waste falls into idle capacity and costs nothing. At batch 64, where you are compute-bound, a rejected draft consumes arithmetic that another sequence's real token needed. Speculation stops being free and starts being a tax.

The empirical picture:

This creates a genuine architectural tension. Throughput-oriented serving wants large batches. Latency-oriented serving wants speculation. You usually cannot have both, and which you choose should follow from your SLO:

• Low-latency, low-concurrency (local inference, interactive coding, a single user on dedicated hardware): speculate aggressively, keep the batch small.
• High-throughput, high-concurrency (a public API optimizing cost per token): large batches, speculation off or adaptive.
• In between: adapt. Modern schedulers monitor batch occupancy and acceptance rate and adjust γ per step, disabling speculation when the batch is full. Doing this well is an open problem — see Module 10.

One nuance worth adding: reasoning models change the calculation. A long chain-of-thought trace is thousands of decode tokens whose content is never shown to the user, so per-token latency matters less than total time, and the tokens are often highly predictable. That combination favours aggressive speculation even at moderate batch, and it is an active area.