Speculative Decoding: Speeding Sequential Generation

During the 2026 IPL season, a Bengaluru startup fine-tunes a 13-billion-parameter model to generate ball-by-ball Hindi-English commentary — "Kohli steps out, drives it straight past the bowler, that's four!" — streamed to a match-tracking app the moment each delivery is logged. The product requirement is brutal: a cricket over takes roughly 90 seconds to bowl, and each ball needs a two-to-three-sentence burst of commentary generated and displayed before the next delivery lands, or the text visibly lags the game. The engineering team profiles their serving stack on a single NVIDIA A100 GPU and finds something that looks like a bug: the GPU's compute utilization during generation sits under 1%. The chip that can do 312 trillion floating-point operations per second is running at a fraction of a percent of that, and the text is still coming out too slowly. Nothing is broken. This is what autoregressive decoding looks like on modern hardware, and understanding exactly why is the key to understanding speculative decoding — not just that it works, but why the specific engineering choices inside a real implementation (which draft tokens to generate, how many, and how to verify them) are dictated by a hardware constraint that has nothing to do with the model's accuracy.

Why Generation Is Slow: A Roofline View

A companion chapter in this course proves, via rejection sampling, that speculative decoding can produce tokens statistically indistinguishable from what the target model would have generated on its own. That correctness argument is necessary but it is not sufficient to explain why speculative decoding is worth building — for that, you need to know what a single decoding step actually costs on a GPU, because that cost is what determines how much "free" extra work the hardware can absorb.

Generating one token autoregressively means computing a full forward pass through the model for a batch of one, with a sequence length of one new token. Every one of the model's parameters must be read out of GPU high-bandwidth memory (HBM) and multiplied against the current hidden state. For a 13B-parameter model stored in FP16 (2 bytes per parameter), that read is:

bytes_per_token = 13e9 params × 2 bytes = 26e9 bytes = 26 GB

An A100 80GB SXM GPU has roughly 2039 GB/s of HBM bandwidth. Moving 26 GB at that rate takes:

t_memory = 26e9 bytes / 2039e9 bytes/s ≈ 0.01275 s = 12.75 ms

That implies a ceiling of roughly 1000/12.75 ≈ 78 tokens per second at batch size 1 — in the right range for what a 13B model actually achieves on this hardware, once you allow for the KV-cache traffic and kernel overhead this estimate deliberately ignores. Now compare that to how long the same forward pass takes to compute, as opposed to load. A standard approximation (used throughout the scaling-laws literature, e.g. Kaplan et al., 2020) is that one forward pass over one token costs about 2N FLOPs for an N-parameter model:

flops_per_token = 2 × 13e9 = 26e9 FLOPs
t_compute = 26e9 / 312e12 FLOPs/s ≈ 8.33e-5 s = 0.0833 ms

The forward pass needs 0.0833 ms of arithmetic but 12.75 ms of memory transfer — a ratio of about 153. The GPU's tensor cores sit idle for 99.35% of every decoding step, waiting for weights to arrive from HBM. In roofline-model terms, the workload's arithmetic intensity — FLOPs performed per byte moved — is 26e9 / 26e9 ≈ 1 FLOP/byte, far below the A100's ridge point of roughly 312e12 / 2039e9 ≈ 153 FLOPs/byte, the intensity at which compute and memory bandwidth are equally limiting. Any workload with intensity below the ridge point is memory-bandwidth-bound: you pay for the weights every step whether you use the extra compute or not.

This is the fact that makes speculative decoding a systems idea, not just a sampling trick. If the GPU is going to spend 12.75 ms reading weights regardless, and only 0.083 ms of that time is spent on useful arithmetic for one token, then computing forward passes for several candidate tokens at once, in the same memory-bound step, costs almost nothing extra — up to the point where the added compute time catches up to the fixed memory time. Solving for that crossover:

K = t_memory / t_compute_per_token ≈ 12.75 / 0.0833 ≈ 153

In principle, verifying up to roughly 153 draft tokens in one forward pass would still be dominated by the memory-bound floor of 12.75 ms. In practice nobody drafts 153 tokens — acceptance rates collapse long before that — but the headroom is the reason it is worth spending draft compute generously rather than stingily: on this hardware, a verification pass over 20 candidate tokens instead of 1 barely moves the wall-clock time of the step at all.

Tree-Based Drafting: Testing More Than One Guess

Chain-based speculative decoding, as introduced by Leviathan, Kalman, and Matias (ICML 2023) and independently by Chen et al. (DeepMind, 2023), drafts a single linear sequence of γ candidate tokens and verifies them in one forward pass, accepting a prefix of that chain. Given the roofline result above, chain drafting leaves the GPU's slack almost entirely unused: a chain of γ=4 tokens costs about 4 × 0.083 ms ≈ 0.33 ms of compute, well under the 153-token crossover. If one guess at each position is nearly free, why guess only once per position?

Tree-based speculative decoding answers that directly. Instead of one chain, the draft step proposes a tree of candidate continuations — several alternative next tokens at each position, each with its own children — and verifies the entire tree in a single forward pass using a custom attention mask that keeps sibling branches invisible to one another. Medusa (Cai et al., 2024) generates this tree by attaching K extra linear prediction heads directly on top of the base model's final hidden state, one head per future offset, each trained to propose several candidate tokens for that position without running the model autoregressively to get them. SpecInfer (Miao et al., 2024) builds trees from one or more small draft models and merges their proposals into a single verification tree, explicitly built for multi-tenant LLM-serving clusters. Sequoia (Chen et al., 2024) goes further and treats the tree's shape itself — how wide, how deep, how the branching factor should taper with depth — as an optimization problem solved per hardware target, because the "free" compute budget from the roofline argument is different on an A100 than on a phone-class NPU.

The mechanical challenge tree-based drafting introduces is not sampling — that reduces to the same accept/reject test used for a single chain, applied per node — it is attention. If you simply concatenate all the tree's draft tokens into one sequence and run ordinary causal attention over it, a token in one branch would incorrectly attend to tokens in a sibling branch that were never actually generated together. The fix is a tree attention mask.

The Mechanism, End to End

Constructing the Tree Attention Mask in Code

The mask above is not hand-drawn — it follows directly from the tree's parent pointers. Below is a self-contained construction that produces exactly the grid shown in the diagram (the prefix column, which every node attends to unconditionally, is added afterward for the same reason every node in the diagram has an unbroken line to the prefix box).

import numpy as np

nodes = ["A", "B", "A1", "A2", "B1", "B2"]
parent = {
    "A": None, "B": None,        # level 1: parent is the prefix itself
    "A1": "A", "A2": "A",        # level 2, drafted under A
    "B1": "B", "B2": "B",        # level 2, drafted under B
}
depth = {"A": 1, "B": 1, "A1": 2, "A2": 2, "B1": 2, "B2": 2}

def ancestors(node):
    chain = []
    cur = node
    while parent[cur] is not None:
        cur = parent[cur]
        chain.append(cur)
    return chain

num_nodes = len(nodes)
tree_mask = np.zeros((num_nodes, num_nodes), dtype=int)
for i, ni in enumerate(nodes):
    for j, nj in enumerate(nodes):
        if i == j or nj in ancestors(ni):
            tree_mask[i, j] = 1

print(tree_mask)
print([depth[node] for node in nodes])

Tracing it by hand: ancestors("A") and ancestors("B") are both empty (their parent is the prefix, not a tree node), so rows A and B only mark themselves. ancestors("A1") and ancestors("A2") both return ["A"], so those rows mark themselves and column A — but not each other, since neither is the other's ancestor. Symmetrically for B1 and B2 with column B. That gives exactly:

[[1 0 0 0 0 0]
 [0 1 0 0 0 0]
 [1 0 1 0 0 0]
 [1 0 0 1 0 0]
 [0 1 0 0 1 0]
 [0 1 0 0 0 1]]
[1, 1, 2, 2, 2, 2]

(prepend a column of all 1s for the shared prefix and you get the seven-column grid in the diagram). The second printed line is the key to position encoding: A and B, though they occupy positions 1 and 2 in the flattened sequence fed to the model, both receive rotary position id n (n = prefix length), because both are candidates for the same slot in the eventual output. All four depth-2 nodes receive position id n+1 for the same reason. Position ids track depth in the tree, not offset in the flattened buffer — get this wrong and the model's rotary embeddings will treat sibling branches as if they were sequential continuations of each other, corrupting every logit the verification pass produces.

Expected Tokens per Verification Round: Chain vs. Tree

The roofline argument says extra tree nodes are nearly free in wall-clock time; it says nothing about whether they are worth drafting at all. That depends on how many additional tokens, in expectation, a wider tree actually gets accepted per round, compared to a chain built from the same total node budget.

Take a full binary tree of depth D=3 (branching factor b=2 at every level: 2 nodes at level 1, 4 at level 2, 8 at level 3, 14 nodes total), and suppose each individual candidate token is independently accepted by the target model's rejection test with probability p=0.6. At any level, the branch survives if at least one of its b siblings is accepted — the verification pass computed logits for all of them, so it can walk down whichever child actually matches. The per-level survival probability is:

q = 1 - (1 - p)^b = 1 - (1 - 0.6)^2 = 1 - 0.16 = 0.84

and reaching depth d requires surviving all d levels, so P(reach depth d) ≈ q^d (treating levels as independent, a simplification worth flagging: real acceptance probabilities correlate across a branch because they share a drafting model and a topic, but the qualitative comparison below is unaffected by that simplification). Expected depth reached over D=3 levels:

E_tree = q^1 + q^2 + q^3 = 0.84 + 0.7056 + 0.592704 = 2.138

Compare a plain chain of the same depth (branching factor 1, budget 3 nodes instead of 14), where survival to depth d needs p^d directly:

E_chain = p^1 + p^2 + p^3 = 0.6 + 0.36 + 0.216 = 1.176

Every verification round, regardless of drafting strategy, also yields one additional "bonus" token: after the last accepted draft node, the target model's own logits at that position are sampled directly, since the verification pass already computed them. So the total expected tokens per round are 3.138 for the tree and 2.176 for the chain — a 1.44× advantage in tokens produced per round, for 14 nodes of draft/verify compute instead of 3.

Now apply the roofline numbers from the first section. Compute time for 14 nodes ≈ 14 × 0.083 ms ≈ 1.17 ms; for 3 nodes ≈ 0.25 ms. Both are trivial next to the 12.75 ms memory floor, so both rounds still take approximately 12.75 ms wall-clock regardless of tree size. The tree therefore delivers 3.138 tokens per 12.75 ms (≈246 tokens/s) versus the chain's 2.176 tokens per 12.75 ms (≈171 tokens/s) — a real throughput gain purchased almost entirely with the GPU's idle cycles, not with additional wall-clock time. This is the concrete version of the claim in the previous section: because the hardware floor is fixed by memory bandwidth, the only "cost" of a wider tree is wasted draft computation on branches that turn out to be rejected, and that computation was sitting well under the 153-node crossover to begin with.

Medusa Heads and Typical Acceptance

Medusa (Cai et al., 2024) builds its tree without a separate draft model at all. It freezes the base ("target") model and attaches K extra linear heads to its final hidden state, each head trained to predict the token K positions ahead directly from that single hidden state — not autoregressively, but as K independent classification problems trained jointly with a shared backbone. Each head's top few candidates become one level of the draft tree, and Medusa's calibration step chooses a sparse, sorted-by-value tree shape (not a full binary tree) so that the branches most likely to matter get the largest share of the compute budget. Because the heads sit on top of the same model whose verification pass will check them, no second set of weights needs to be loaded, versioned, or kept aligned with the target model as it is fine-tuned or updated.

Medusa also offers an optional relaxed acceptance rule it calls typical acceptance, distinct from the strict rejection-sampling test proven elsewhere in this course. Rather than accepting a candidate only with probability min(1, p_target(x)/p_draft(x)) — the rule that guarantees the output distribution exactly matches running the target model alone — typical acceptance accepts any candidate whose target-model probability clears a threshold that adapts to the local entropy of the distribution, in the spirit of locally typical sampling (Meister et al., 2023). This discards the exact-distribution guarantee: the accepted text is plausible under the target model, not provably sampled from it. For a chat product where the goal is fluent, sensible output rather than statistically calibrated log-likelihoods, that trade is usually worth it, because it raises the acceptance rate — and therefore the tokens-per-round number computed above — beyond what strict rejection sampling permits.

Self-Speculative Decoding: Drafting Without a Second Model

Every tree-drafting method discussed so far still needs some source of candidate tokens: a separate small model (SpecInfer), extra trained heads (Medusa), or a purpose-built tree search (Sequoia). LayerSkip (Elhoushi et al., Meta, ACL 2024) removes even that requirement. The model is trained with layer dropout and an early-exit loss so that its own shallow sublayers — say, the first eight of thirty-two transformer blocks — can produce a usable, if lower-quality, next-token prediction by exiting straight to the LM head instead of running the full stack. At inference time, drafting means running only those first eight layers (fast, since most of the memory-bound weight traffic never happens); verification means running the full thirty-two layers on the same input.

The systems payoff is twofold. First, there is no second model competing for GPU memory — critical in a serving cluster running many models or LoRA adapters per GPU, where every gigabyte devoted to a draft model's weights is a gigabyte not available for KV cache or another tenant. Second, because the draft pass is literally a prefix of the verification pass's computation, the activations and KV entries computed for the first eight layers during drafting can be reused directly during verification instead of recomputed, shaving the verification pass's own cost further. The acceptance rate from an eight-layer early exit is typically lower than a well-tuned dedicated draft model would achieve, but the operational simplicity — one set of weights, one training pipeline, no drift between draft and target as the model is updated — is often the deciding factor in a production system, which is exactly the kind of trade the roofline arithmetic above cannot settle on its own: it tells you the ceiling, not which floor is cheapest to build.

Common Misconception

A natural but wrong intuition, once you have seen that extra draft nodes are nearly free, is: "so I should always make the tree as wide and as deep as GPU memory allows — more candidates can only help." Three things break this. First, the free-compute headroom is bounded — the K≈153 crossover computed earlier is a ceiling, not an invitation to grow without limit; past that point the verification pass genuinely becomes slower, not free. Second, acceptance probability is not constant with depth: draft and target distributions diverge the further out you predict, both because a shallow draft head (or an early-exit layer) gets noisier the more it has to extrapolate, and because errors early in a branch propagate — a token accepted at level 2 was conditioned on whatever was drafted at level 1, so a bad level-1 guess poisons every child under it even before you ask whether the child itself would be accepted. Third, and easy to miss, is that drafting itself is not literally zero-cost: Medusa's heads and SpecInfer's small model still spend real time producing the candidates that get fed into the mask, and a wider tree means more candidate tokens to generate before verification can even start. The right tree size is the point where marginal expected accepted tokens (which shrinks with depth, per the q^d calculation above) stops paying for the marginal drafting and bookkeeping overhead — not the largest tree the memory-bandwidth ceiling would technically tolerate.

Active Recall

Attempt each question before reading its answer.

1. Why is single-token autoregressive decoding at batch size 1 memory-bandwidth-bound rather than compute-bound on a modern GPU, in general (not just for the 13B example)?
2. Redo the chain-vs-tree expected-tokens comparison from the worked example with p=0.8 instead of p=0.6, keeping b=2 and D=3. Does tree drafting help more or less than it did at p=0.6, and why does that direction make sense?
3. A degenerate "tree" with branching factor 1 at every level is just a chain of 3 drafted nodes: A → X → Y, each node's only child being itself extended by one token. What does its tree attention mask look like, and what does that tell you about the relationship between chain-based and tree-based speculative decoding?
4. Suppose the cricket-commentary team upgrades from an A100 (2039 GB/s HBM bandwidth) to an H100 (≈3350 GB/s), keeping the model, batch size, and the 14-node tree from the worked example unchanged, and — as a simplifying assumption for this exercise — holding peak FLOPs/s constant so you can isolate the bandwidth effect. Trace the full ripple: what happens to the memory-bound token latency, the compute/memory crossover K, whether the 14-node tree is still "free," and the relative (tree vs. chain) speedup?
5. Why might a serving team choose LayerSkip-style self-speculative decoding over a separate, better-tuned draft model, even knowing it will accept fewer draft tokens on average?
6. Why would a production chatbot ever choose Medusa's typical acceptance over strict rejection sampling, and what is the actual risk of doing so?

Answers

1. A single-token forward pass needs to read every model parameter from HBM exactly once (≈2N bytes in FP16) but performs only ≈2N FLOPs of arithmetic with them — an arithmetic intensity of about 1 FLOP/byte. Any GPU's ridge point (peak FLOPs/s divided by peak bytes/s) is far higher than that for large dense models — around 153 FLOPs/byte for an A100. Since the workload's intensity sits far to the left of the ridge point, time is dominated by how long it takes to move the weights, not by how long it takes to multiply them; the compute units finish almost instantly and then wait. This holds for any N large enough that weight traffic dwarfs a batch-of-one computation, not just the 13B case.

2. With p=0.8, b=2, D=3: q = 1-(1-0.8)^2 = 1-0.04 = 0.96. E_tree = 0.96+0.9216+0.884736 = 2.766. E_chain = 0.8+0.64+0.512 = 1.952. Adding the bonus token: tree total 3.766, chain total 2.952, ratio 3.766/2.952 ≈ 1.276×. At p=0.6 the ratio was ≈1.44×. So tree drafting helps less in relative terms as base acceptance probability rises. This makes sense: when a single guess already succeeds most of the time (p=0.8), a second sibling candidate mostly duplicates a bet that would likely have paid off anyway, so 1-(1-p)^2 is only marginally above p. When p is lower (0.6), a single guess fails often enough that a second independent guess meaningfully raises the chance at least one of them lands, so branching buys much more.

3. ancestors(X) = ["A"], ancestors(Y) = ["X","A"] (Y's parent is X, whose parent is A). The mask becomes lower-triangular: A sees {A}; X sees {A, X}; Y sees {A, X, Y} — identical in structure to ordinary causal attention over a 3-token sequence appended to the prefix. This shows chain-based speculative decoding is not a different mechanism from tree-based decoding; it is the special case of a tree with branching factor 1 at every level, using the plain causal mask that falls out of the same construction once there is only one child per node.

4. Memory-bound token latency: t_memory' = 26e9 / 3350e9 ≈ 7.76 ms (down from 12.75 ms). Holding t_compute_per_token at 0.0833 ms (the stated simplification), the new crossover is K' = 7.76 / 0.0833 ≈ 93 (down from ≈153) — the crossover shrinks because a faster memory system reaches the point where compute becomes limiting sooner. The 14-node tree's compute time is unchanged at ≈1.17 ms, still far under the new 93-node crossover and under the new 7.76 ms memory floor, so it remains comfortably "free" — verification is still memory-bound, just with a lower floor. Because both the chain and the tree round are still dominated by the (now smaller) memory floor, both speed up by the same factor, 12.75/7.76 ≈ 1.64×: tree throughput rises from ≈246 to ≈404 tokens/s and chain from ≈171 to ≈280 tokens/s. The relative speedup of tree over chain, 1.44×, is unchanged — it depends only on the acceptance probabilities and tree shape, not on the memory bandwidth, since both strategies are being scaled by the same hardware factor.

5. A separate draft model, however small, still occupies GPU memory for its own weights and needs its own maintenance — retraining or re-validating whenever the target model is updated, and competing for memory against KV cache and other tenants on a shared serving GPU. Self-speculative decoding via early exit uses the target model's own shallow layers, so there are no extra weights to store and no drift risk between draft and target. It also lets the verification pass reuse the KV entries and activations the draft pass already computed for those shallow layers, cutting verification cost further. The team accepts a lower per-round acceptance rate in exchange for a simpler, cheaper-to-operate serving stack — a classic engineering trade, not a strictly dominant choice.

6. Strict rejection sampling caps acceptance at min(1, p_target(x)/p_draft(x)), which discards a candidate whenever the draft model's confidence in it, even slightly, exceeds the target model's — a common occurrence for any reasonable draft token, since it only has to be plausible, not exactly probability-matched. Typical acceptance instead asks only whether the candidate is plausible under the target distribution, which passes more candidates and raises tokens-per-round, directly increasing throughput by the same mechanism worked out in the tree-vs-chain comparison above. The risk is that the guarantee proven for strict rejection sampling — that the output is statistically indistinguishable from always running the target model alone — no longer holds; the generated text can drift slightly in style or in how often it selects lower-probability tokens. That is an acceptable trade for a conversational product judged on fluency, but not for a setting that needs calibrated, provably faithful sampling, such as research benchmarking or computing exact log-likelihoods.

Think About It

Think about this: How would you explain speculative decoding: speeding sequential generation to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind speculative decoding: speeding sequential generation, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.