MTP and Speculative Decoding

The “Impossible” Ceiling, Revisited

We ended Lecture 1 with a hard floor. One decode step must read all \(P\) weights once, so a single-request step cannot take less than \[ T_{step} \ge \frac{2P}{\beta} \approx \frac{140\ \text{GB}}{3.35\ \text{TB/s}} \approx 41.8\ \text{ms} \] for a 70B model in FP16 on an H100. That is a ceiling of about 24 tok/s, at \(I \approx 1\) FLOP/byte, 300× below the ridge. Everything since (paging, batching, disaggregation, parallelism, kernel fusion) has lived above that line, trying to amortize the weight read across more requests or more work. None of it touched the wall itself.

Why Verification Is (Exactly) Free

Here is the one fact the whole module rests on. A forward pass over \(k\) tokens reads each weight matrix once and does \(k\) times the arithmetic: verification converts a GEMV into a GEMM with \(M = k\) rows for the same memory traffic. As long as the \(k\times\) extra compute fits inside the idle compute budget (recall that the compute utilization of single-request decode is \(\beta/\pi \approx 1/295 \approx 0.34\%\)), the step time does not move. Formally: \[ T_{verify}(k) = \max\!\Big( \underbrace{\frac{2P + B \cdot kv}{\beta \cdot MBU}}_{\text{memory: unchanged}},\; \underbrace{\frac{k \cdot 2P \cdot B}{\pi \cdot MFU}}_{\text{compute: grows linearly}} \Big) \quad\Longrightarrow\quad k \le \frac{\pi}{\beta}\cdot\frac{MFU}{MBU}\cdot\frac{2P + B \cdot kv}{2P\,B}. \] At \(B = 1\) and \(kv \cdot L \ll 2P\) (70B at \(L\) = 4K: the KV read is \(320\ \text{KB} \times 4096 \approx 1.3\) GB vs 140 GB of weights), the last factor is \(\approx 1\), and the ceiling collapses to \(k^* \approx \text{ridge} \times MFU/MBU\).

The Framework: Draft → Verify → Accept

So: if verifying \(k\) tokens costs one decode step, can we find tokens worth verifying? Each speculative round goes:

1. Draft. A cheap mechanism proposes \(k\) candidate continuations \(\hat{x}_{t+1}, \dots, \hat{x}_{t+k}\), as a chain or a candidate tree.
2. Verify. One forward pass of the target model yields its next-token distributions at all \(k\) positions simultaneously, \(p(\cdot \mid x_{\le t}), p(\cdot \mid x_{\le t}, \hat{x}_{t+1}), \dots\) This is the same causal-mask trick as prefill, legal by the cache-legality induction of Lecture 1.
3. Accept. Position by position, accept a candidate if it passes a test against the target distribution; truncate at the first failure. The verify pass at the failure position still yields the target's own distribution there, so every round emits at least 1 and at most \(k+1\) tokens. The “+1” is the bonus token computed for free by the same pass.

The whole thing now rests on two questions: is the acceptance test exact, and how many tokens does a round yield on average? The next two sections answer them in order.

Not Cheating: Speculative Decoding Is Exact

This is the mathematical heart of the lecture, and the property that sets speculative decoding apart from every approximate acceleration (quantization, distillation, pruning): the output distribution is strictly identical to decoding with the target model alone. We prove it twice, because greedy and sampling need different tests.

Greedy: induction over rounds

Target greedy decoding is a deterministic function \(g(\text{prefix}) = \arg\max_x p(x \mid \text{prefix})\). A round drafts \(k\) tokens and the verify pass hands us \(g_i = g(\text{prefix}, \hat{x}_1, \dots, \hat{x}_{i-1})\) for all \(i = 1..k{+}1\) at once. The rule: accept \(\hat{x}_i\) iff \(\hat{x}_i = g_i\); stop at the first mismatch \(j\) and emit \(g_j\); if all \(k\) match, also emit the bonus \(g_{k+1}\).

Claim. The emitted sequence equals the target-greedy sequence exactly. Proof (sketch). Invariant: at the start of every round, the committed prefix equals the target-greedy prefix. Base: the shared prompt. Step: for every \(i < j\), the accepted \(\hat{x}_i\) equals \(g(\text{committed prefix}, \hat{x}_{<i})\), which by the invariant is the next greedy token; at position \(j\) we emit \(g_j\), the target's greedy token given the (now correct) prefix. Invariant restored, and \(1 \le r \le k{+}1\). ∎ Note the structural reason even total rejection is free: the verify forward wastes nothing.

Sampling: a rejection test that repairs the gap

Greedy comparison fails when we sample \(x \sim p\). The correct test, due to Leviathan, Kalman, and Matias, and independently Chen et al. (2023), is rejection sampling against the draft distribution. The draft drew \(x \sim q\); both \(p\) (from the verify pass) and \(q\) (from the draft) are known exactly:

• Accept \(x\) with probability \(\min\!\big(1,\; p(x)/q(x)\big)\).
• On rejection, resample from the residual and truncate the round: \[ \tilde{p}(x) = \frac{\max\big(0,\; p(x) - q(x)\big)}{Z}, \qquad Z = \sum_{x'} \max\big(0,\; p(x') - q(x')\big). \]

Two one-line identities make it exact. Watch. First, the normalizer is the rejection probability: \[ Z = 1 - \sum_x \min(p(x), q(x)) = \tfrac{1}{2}\lVert p - q \rVert_1 = \Pr[\text{reject}], \] because \(\sum_x q(x)\min(1, p(x)/q(x)) = \sum_x \min(p(x), q(x))\), and \(\sum \max(0, p-q) = \sum p - \sum\min(p,q)\) pointwise (the two positive parts of \(p - q\) have equal mass, hence the \(\tfrac12\lVert p - q\rVert_1\) form). Second, the emitted token's law: \[ \Pr[\text{final} = x] = \underbrace{q(x)\min\!\big(1,\; p(x)/q(x)\big)}_{\text{accepted draft}} + \underbrace{Z\,\tilde{p}(x)}_{\text{rejection} \times \text{residual}} = \min(p, q) + \max(0, p - q) = p(x). \]

Sanity checks (the two limits). If \(q = p\): acceptance is 1 everywhere, \(Z = 0\), never reject: pure speedup. If \(q\) and \(p\) have disjoint support: acceptance is 0 everywhere, \(Z = 1\), the residual \(\tilde{p} = p\), and every round degenerates to sampling from the target directly. Still correct, just no gain. The scheme interpolates between “free tokens” and “ordinary decode” as a function of draft quality \(\tfrac12\lVert p - q\rVert_1\). Lifting one position to whole sequences is an induction over committed positions: the invariant (the committed prefix has exactly the target's law) makes the chain-rule product telescope to the target's sequence distribution.

The Speedup Law: τ Over (1 + c_draft)

Exactness settled. Now, how fast is it? Model acceptance as i.i.d. per position with probability \(\alpha\) (a first-order approximation; real acceptance correlates through the prefix, and we will honour that later). A round with \(k\) draft positions accepts a geometric run up to the first rejection, plus the bonus token: \[ \tau = \sum_{i=0}^{k} \alpha^i = \frac{1 - \alpha^{k+1}}{1 - \alpha} \quad \xrightarrow[k \to \infty]{} \quad \frac{1}{1 - \alpha}. \] The asymptote is the field's fundamental tension: for \(\alpha = 0.85\) it caps at 6.67, and no chain length escapes it. Raising \(k\) buys less and less, while (for autoregressive drafters) costing more and more.

Per round, time is \(T_{tgt} \cdot (1 + c_{draft})\): the target step plus the draft cost in units of a target step, verification free inside the ceiling. Tokens per round: \(\tau\). Baseline: \(\tau\) tokens cost \(\tau\,T_{tgt}\). Hence the course's canonical formula: \[ \text{speedup} \approx \frac{\tau}{1 + c_{draft}}, \] with exactly two levers that organize everything that follows: raise \(\tau\) (draft quality and alignment) and lower \(c_{draft}\) (draft efficiency, especially its scaling in \(k\)).

Draft Trees: Spend the Budget Where Uncertainty Is

A chain has a concrete flaw: it commits the draft budget to one guess per position. But language is not equally predictable everywhere. When the target distribution is peaked, one candidate suffices; when it is spread over a few plausible continuations, no single one is likely to match. A tree draft keeps several candidates per position and lets verification pick the longest passing branch.

The math generalizes the chain: writing \(a(v)\) for the acceptance probability of node \(v\) given its parent is accepted, at most one node per level can continue the committed sequence, so the level events are disjoint and \[ \mathbb{E}[\tau_{tree}] - 1 = \sum_{v \ne root} \prod_{u \in path(root, v)} a(u) \xrightarrow{\text{i.i.d. } \alpha} \sum_{v \ne root} \alpha^{\,\text{depth}(v)}. \] Note the honesty constraint: sibling acceptance events are (nearly) disjoint, so children of a node sum to \(\lesssim 1\). A branching node helps only to the extent its children partition probability mass. Trees pay precisely when the distribution is entropic.

And the cost side argues back. A tree of \(n\) nodes is verified in one forward over \(n{+}1\) tokens, so the ceiling binds when \(B \cdot (n{+}1) \approx 150\text{–}300\) tokens per step. At \(B = 32\) that is a budget of 5–9 tokens per request: a chain of \(k \le 4\text{–}8\), or only a small tree. Production systems choose chain vs small tree as a function of current load, and EAGLE-2's confidence-based dynamic trees (expand branches exactly where the draft itself is uncertain) are as much a load-management feature as an accuracy feature.

Four Generations of Drafts: the Road to Alignment

The speedup law said \(\tau\) and \(c_{draft}\) are everything; the field's history is a four-generation push on both axes at once. Walk it the way the flaws dictate.

Gen 1: an independent small model (a 1B of the same family drafts for 70B). The easiest thing you can do... and you probably can guess the flaws: a second model to train and deploy, \(k\) serial autoregressive draft steps, and a softmax geometry never aligned with the target's. Poor \(\tau\), real \(c_{draft}\). Largely obsolete.

Gen 2: Medusa deletes the second model: \(k\) lightweight heads sit on the target's last hidden state, head \(i\) predicting token \(t{+}i\). Extremely cheap. But now the flaw is coordination: all heads condition on the same hidden state and predict independently, so the joint plausibility of the \(k\)-gram suffers. Alignment, not speed, is the bottleneck.

Gen 3: EAGLE fixes the conditioning: a single small transformer layer runs autoregressively over the target's features: (last-layer hidden state, embedding of last token) in, next feature out, the target's own LM head on top. The move from token-level to feature-level autoregression is the single biggest alignment jump: the hidden state is a sufficient statistic of the prefix; a sampled token is a lossy projection of it. One small-layer step per candidate, dynamic trees (EAGLE-2), multi-layer feature fusion (EAGLE-3). This is the widely deployed baseline in vLLM and SGLang.

Gen 4: MTP (DeepSeek-V3) asks: why should the draft be learned outside the default?

• Training: MTP module \(i\) takes the current feature plus the next token's embedding, runs one transformer layer, predicts the second future token. So every position supervises two (or more) targets, a denser signal the V3 report credits as a quality gain in its own right.
• Inference: the same module is structurally isomorphic to an EAGLE draft head, so it is directly the speculative draft: 85–90% second-token acceptance, \(\tau \in [1.85, 1.90]\) at \(k = 1\), one small layer per extra token of \(c_{draft}\), zero separate training or deployment, because the weights ship inside the checkpoint. Speculation stops being an optimization the deployer performs and becomes a capability built into the model; DeepSeek enables it by default, deliberately conservatively at \(k = 1\).

DFlash: deleting the draft's for-loop

Every draft so far is autoregressive: \(k\) candidates cost \(k\) sequential draft forwards, so \(c_{draft}\) grows linearly in \(k\) and caps how far \(\tau\) can be pushed (the interior optima above). DFlash attacks the seriality itself: the draft is a lightweight block-diffusion model that processes one anchor token plus several mask tokens and fills in the whole block of typically 8–16 candidates in parallel, the way masked-diffusion LMs denoise a block at once. Conditioning on the target's multi-layer features keeps alignment high; outputs are projected through the target's LM head, as in EAGLE/MTP. Reported (DFlash paper, ICML 2026): lossless speedups of 6× or more across models and tasks, up to 2.5× over EAGLE-3; NVIDIA's Blackwell evaluation reports up to 15× throughput at equal interactivity on gpt-oss-120b vs EAGLE-3; integrations in SGLang, vLLM, TensorRT-LLM; official draft checkpoints for mainstream open-model families; a UCSD team completed a TPU implementation.

Speculation Meets the Rest of the System

Speculative decoding is not a kernel you bolt on; it changes the shape of decode (rounds commit a random \(r \in \{1, \dots, k{+}1\}\) tokens), and every layer of Lectures 2–7 feels it. Walk the stack with me.

Batching: the gain inverts with load

Free verification presumes spare compute, and spare compute is a small-batch luxury. Small batch: \(I \approx 1\), 300× under the ridge, speculation pays up to the full \(\tau/(1+c_{draft})\). Large batch: verify multiplies tokens per step by \(k{+}1\), and once \(B(k{+}1) \gtrsim 150\text{–}300\), decode crosses the ridge and goes compute-bound. The extra verify FLOPs crowd out paying work they would otherwise have served \(k\times\) over. Break-even batch (70B on H100, \(L\) = 4K, \(MFU = 0.5\), \(MBU = 1\)):

Production consequence: engines continuously estimate batch size and realized acceptance, and adjust \(k\), or switch speculation off entirely when loaded. A static \(k\) is a bug under drifting load. And one more hygiene rule: an acceptance number without a task distribution is uninterpretable. DSpark's \(\tau\) moved from 4.73 to 2.61 between coding and creative traffic.

KV management: reserve for the worst case, roll back the rest

• Reservation. Before a round, the pager reserves worst-case capacity: \(k{+}1\) extra tokens per request. 70B: \((k{+}1) \times 320\) KB, i.e. 1.6 MB at \(k = 4\) and 3.0 MB at \(k = 8\), at most one extra 5.2 MB block under 16-token paging. DeepSeek-V3's MLA cache makes this nearly free: \(k = 1\) reserves \(2 \times 34\) KB \(= 70\) KB per request.
• Rollback. Rejected positions had KV written during verify; roll it back: truncate the logical length, release blocks that become empty. Expected rollback per round is \(k - (\tau - 1)\) tokens. At \(k = 4,\ \alpha = 0.85\): \(4 - 2.71 = 1.29\) tokens ≈ 423 KB. Forgetting rollback does not corrupt output (rejected KV is never attended to after truncation). It leaks blocks silently and shrinks your capacity.

Streaming: ITL becomes bimodal

A worked micro-example on our running 70B (MTP, \(k = 1\), \(\alpha = 0.85\), \(c_{draft} = 0.10\)): a round takes \(41.8 \times 1.1 = 46.0\) ms and emits 1 token with probability 0.15 or 2 tokens with probability 0.85. Per-token inter-arrival times are bimodal: ≈ 46 ms within a round, ≈ 0 ms for the second token of a 2-token round. Meanwhile the mean ITL drops to \(46.0/1.85 = 24.9\) ms from 41.8 ms. Remember Lecture 1: TPOT is a mean, ITL is a distribution. Mean-only monitoring misreads speculative systems twice: it hides the bursts from users watching the stream, and the per-round granularity from capacity planners.

CUDA graphs and EP: multipliers everywhere

CUDA graphs: the draft forward (\(M = B\)) and the verify forward (\(M = B(k{+}1)\), plus tree-mask variety) have different shapes, each needing its own captured buckets. The forward inventory doubles, and a variable \(k\) multiplies it again. Practical systems capture a small fixed set of \(k\) values, or run the (small) draft eagerly and capture only verify. Expert parallelism: per-step all-to-all volume scales with tokens in the step, so \[ V^{spec}_{a2a} = (k{+}1)\cdot V^{plain}_{a2a}. \] For DeepSeek-V3 (top-8 of 256 routed experts, \(d_{model} = 7168\)): ≈ 57 KB FP8 dispatch plus ≈ 115 KB BF16 combine ≈ 172 KB per token, and MTP at \(k = 1\) doubles it. This lands on links 3.7–67× narrower than HBM (900 GB/s NVLink down to 50 GB/s IB, vs \(\beta = 3.35\) TB/s). DeepSeek's production \(k = 1\) is exactly this three-way trade: high acceptance, minimal verify compute, only 2× communication, instead of chasing \(\tau\)-gains paid in all-to-all volume. (Larger expert batches partly self-correct GEMM efficiency; the network does not.)

Rollback without a KV: speculation on linear attention

Everything above assumed per-token KV: rejected positions own identifiable entries, and rollback is truncation. The 2026 hybrid models break that assumption structurally. Kimi K3's 69 KDA layers carry a rolling recurrent state \(S \in \mathbb{R}^{128 \times 128}\) per head: 3.0 MiB BF16 per layer, ≈ 0.2 GiB per request across all KDA layers, fixed regardless of context length. It is updated in place by the gated delta rule: \[ S_t = (I - \beta\, k k^\top)\, \mathrm{Diag}(\alpha)\, S_{t-1} + \beta\, k v^\top. \] There is no per-token entry to free: processing \(k\) draft tokens overwrites the committed state, diffusing the draft's contribution into every element of \(S\). Rejecting a suffix requires a state rewind, not a pointer truncation. It is the same logical requirement as KV rollback, with different mechanics and a different cost model.

The 2026 solution space:

• Snapshot + replay (SGLang ReplaySSM). Snapshot the state at the round boundary; on rejection, restore and replay the accepted raw inputs to advance \(S\). This is legal because \(S\) is a deterministic function of the input sequence (cache legality, recurrence edition). ReplaySSM further compresses the draft-window working state from 512 KB to 16 KB (≈ 32×), so speculative scratch stops competing with the KV pool.
• Feature-level drafting upstreamed (vLLM EAGLE3-on-KimiLinear, v0.28.0). The EAGLE-3 recipe on KimiLinear-family hybrids, the engine owning draft/verify state. Speculation on a hybrid becomes a config flag, not a research project.
• Trees without snapshots (TreeWY, Aug 2026). Restructures tree verification for GDN-family linear layers so branches never materialize per-branch state snapshots, removing the \(O(\text{tree size})\) snapshot cost that made trees unattractive on hybrids.
• The MTP path on a hybrid (GLM-5.3-Flash). Zhipu's hybrid (34 KDA + 11 sparse-MLA layers) ships 1 MTP layer in the checkpoint, which vLLM unfolds into 5 speculative tokens; ≈ 25–30 tok/s on 2× DGX Spark with MTP-5. Sanity check in Lecture-1 terms: 18B activated params in FP8 ≈ 18 GB at ≈ 273 GB/s unified bandwidth ⇒ ≈ 15 tok/s plain ceiling; a \(\tau \approx 2\) MTP-5 round lands at ≈ 30. That is the speedup law operating right at the memory floor, exactly as the free-verification argument predicts.

Common Pitfalls

Research Thinking

How to: read the starting point; read the question and think, for a minute, a day, a week... and only then open the answers. You are not supposed to reinvent several months of someone's research; each of these was someone's paper. It's the habit of thinking that counts: you have ideas, you try; if they don't work, you think again.

Have Fun! Be the Verifier

Enough theory. Now you run some rounds. Set an acceptance probability \(\alpha\), a draft length \(k\), and a draft cost \(c_1\) per token, watch the theoretical numbers, then press the button to simulate real rounds: green bars are accepted draft tokens, the amber ★ is the bonus, red ✗ are the aborted tail. Can you make the empirical speedup beat theory? (It happens; small samples are generous.)

Seminar & Homework

Take Lab 8: Speculative Decoding from the hands-on pack. One GPU, three server configs: baseline (no speculation), prompt-lookup n-gram (--speculative-config '{"method":"ngram","num_speculative_tokens":5,"prompt_lookup_max":4}'), and an EAGLE head (--speculative-config '{"model":"<eagle-head-repo>","num_speculative_tokens":5}'; SGLang equivalent: --speculative-algorithm EAGLE --speculative-draft-model-path ... --speculative-num-steps 5 --speculative-eagle-topk 4 --speculative-num-draft-tokens 8). Two datasets: code completion (near-deterministic boilerplate) and open-domain chat; fix ignore_eos, 256 outputs, seed 0.

• Measure throughput/TPOT at \(B \in \{1, 8, 32, 64\}\) for all three configs; read acceptance stats from engine logs and compute your measured \(\tau\).
• Overlay the canonical law: e.g. \(\tau = 2.5,\ c_{draft} = 0.1 \Rightarrow 2.27\times\); \(\tau = 3.5 \Rightarrow 3.18\times\); a weak draft (\(\tau = 2.0,\ c_{draft} = 0.3\)) only 1.54×. Expect code ≫ chat in \(\tau\), and map the gap to task entropy.
• Find the inversion: effective intensity \(I_{spec} = \frac{2P\,B(k{+}1)}{2P + B L\, kv}\) reaches 104 FLOP/byte at \(B=32, k=4\) and 204 at \(B=128\) (\(L = 2048\)), closing on ridge 295, where speculative tokens stop being free. Your speedup curve should peak at small \(B\) and cross 1.0.
• Answer the analysis questions: back out \(c_{draft}\) from measured \(\tau\) and speedup: does it match the draft's standalone step time? Why does \(\tau\), not draft speed, dominate on code? Where does your curve invert, and does the intensity argument predict it? Write the dynamic-\(k\) rule; which signal saturates first? Does ITL P99 show the verify-burst spikes?

Lab pitfalls to self-audit: benchmarking on unpredictable prompts and crediting the engine; comparing spec-on vs spec-off across engines and calling it an engine comparison; ignoring the draft model's VRAM (it eats cache capacity); and reporting a \(B = 1\) speedup as a serving result. In the seminar, present your τ-table next to the theory table and defend one dynamic-\(k\) rule on your own telemetry.

Summary

• One parallel verify pass reads the weights once for \(k\) candidates: free while \(B(k{+}1) \lesssim \text{ridge} \times MFU/MBU \approx 150\text{–}300\) tokens/step (\(k^* \approx 148\) at batch 1 for 70B/H100; systems use \(k \in [1, 16]\)).
• Draft → verify → accept emits \(r \in \{1, \dots, k{+}1\}\) tokens per round; even total rejection yields the bonus token. Wastes nothing, risks nothing.
• Exactness is a theorem, twice. Greedy: induction over rounds. Sampling: accept with \(\min(1, p(x)/q(x))\), resample the residual \(\tilde{p} \propto \max(0, p-q)\), and \(Z = \tfrac12\lVert p-q\rVert_1\) is the rejection probability. The emitted law is exactly \(p\). Lossless means distributional, not bit-exact; never skip the test.
• Speedup \(\approx \tau/(1+c_{draft})\), \(\tau = (1-\alpha^{k+1})/(1-\alpha)\): two levers (alignment, draft cost), an interior optimum in \(k\), and a \(\tau\)-asymptote \(1/(1-\alpha)\) no chain escapes. Trees spend the budget where entropy lives (1.11 vs 1.40 at the same 4-token budget).
• Draft sources evolved by flaw: independent small model (misaligned, second deployment) → Medusa (heads can't coordinate) → EAGLE (feature-level autoregression; the deployed baseline) → MTP (draft trained into the checkpoint; 85–90% acceptance, \(k=1\) by default) → DFlash/DSpark (block diffusion removes seriality; K3: 118 → 370 tok/s at TP16, a lossless 3.14×).
• Every system layer pays a share: gain inversion past \(B(k{+}1) \approx 150\text{–}300\); KV reservation \((k{+}1)\times kv\) and paged rollback of \(k-(\tau-1)\) tokens; bimodal ITL; doubled CUDA-graph inventory; EP all-to-all volume ×\((k{+}1)\); state rewind, not truncation, on hybrid linear-attention models.
• Report \(\tau\) with its task distribution, temperature, and \(c_{draft}\), or don't report it at all. Your move :)