Speculative Decoding

If you've been reading this arc, you know the situation. Autoregressive decoding is sequential and memory-bound. Each new token requires a full forward pass through the model, reading every weight from memory, and most of the GPU's compute sits idle while that happens. We established this in Prefill vs. Decode and The One New Row.

So can we do anything about it?

You can't really make individual decode steps faster. The bottleneck is memory bandwidth, and that's a hardware constraint. Each step loads the entire weight set to produce a single token. The math is the math.

But here's a different question: what if you could get multiple tokens out of a single target-model forward pass?

That's speculative decoding. And the genuinely surprising part is that the output distribution is mathematically identical to running the target model normally. It's not approximately the same or "close enough." There's an actual proof, and we'll walk through it later in the post.

Prerequisites

You'll want to have read Prefill vs. Decode (Post 5.2) for the prefill/decode asymmetry, and The One New Row (Post 5.3) for why decode steps are so wasteful. A working sense of probability distributions over vocabularies helps too. If you're comfortable with the idea that a language model outputs a probability distribution at each position, you're good.

The core asymmetry

I want to start with the insight that makes speculative decoding possible, because everything else follows from it.

We already know from Post 5.2 that processing a prompt (prefill) is parallel. You hand the model 1,000 tokens and it processes all 1,000 in one forward pass, computing attention across all positions simultaneously. The cost of processing 1,000 tokens isn't much more than processing 1 token, because the bottleneck during decode is reading the weights, and you're reading them either way.

So verification is cheap. If someone hands you $k$ candidate tokens and says "what would you have predicted at each of these positions?", the target model can answer that question for all $k$ positions in a single forward pass, at roughly the cost of processing a prompt of length $k$.

Generation, on the other hand, is expensive precisely because you have to produce tokens one by one, autoregressively, with each token depending on the last. You can't parallelize it because each token depends on the previous one.

But verification has no such constraint. Given a sequence of candidate tokens, you can check all of them at once because you're just computing "what would the model have predicted at each position?" and that's a parallel operation.

Speculative decoding exploits this asymmetry. A small model generates candidates fast, and the big model checks them all in one shot.

Draft, then verify

So how do you actually exploit this asymmetry? Here's the concrete setup. You have two models:

1. A draft model that's small and fast. Something like a 1B parameter distilled version of your target, or even a separate lightweight model. The important thing is that it's quick.
2. A target model that's the big one you actually want output from. Think 70B parameters.

The draft model generates $k$ candidate tokens autoregressively, the normal way, one at a time, each conditioned on the previous. Because the model is small, this is fast. Maybe 5 tokens in the time it would take the target model to produce 1. A common pairing is something like Llama-2-7B drafting for Llama-2-70B, or a purpose-built 1B distilled model drafting for a 70B+ target.

Then you hand all $k$ candidates to the target model and say: check these.

The target model runs a single forward pass over the candidates (just like prefill), producing a probability distribution at each position. Now you have two distributions at every position: what the draft model predicted, and what the target model would have predicted. You compare them.

This is the part that surprised me most when I first learned about it. The verification step is basically free. You're already loading all the weights for a decode step anyway, so you might as well use them on $k$ tokens instead of 1. As we saw in Post 5.3, a single decode step is massively memory-bound, operating at roughly 1 FLOP per byte of data read. Processing $k$ tokens during verification bumps the arithmetic intensity to $k$ FLOPs per byte, still well within the memory-bound regime, so it costs almost nothing extra. The prefill/decode asymmetry becomes a tool instead of a problem.

The acceptance criterion

So the target model processes all $k$ draft tokens in one forward pass and produces logits at every position. At each position $i$, you now have two probability distributions:

• $q(x_i)$: the probability the draft model assigned to the token it chose
• $p(x_i)$: the probability the target model assigns to that same token

The rule works left to right, position by position:

If $p(x_i) \geq q(x_i)$: accept. The target model is at least as confident as the draft model was. No issue.

If $p(x_i) < q(x_i)$: accept with probability $\frac{p(x_i)}{q(x_i)}$, reject otherwise. If you reject, you don't just throw the token away. You resample from an adjusted distribution:

This adjusted distribution captures the probability mass that the target model wants to assign but the draft model didn't. You sample one token from $p'$, use it as the replacement, and discard everything after the rejection point.

And then you start a new round. The draft model picks up from the last accepted (or resampled) token and guesses another $k$ tokens. This cycle repeats until the target model produces an end-of-sequence token.

The correctness guarantee

This is the section that matters most.

Leviathan et al. and Chen et al. both independently proved that this accept/reject scheme produces an output distribution that is exactly the same as sampling directly from the target model. The two distributions are identical, not approximately close or statistically close, but identical at the distribution level.

I want to be precise about why, because the proof is elegant and not as complicated as you might expect. At each position, one of two things happens. Either the draft token is accepted (which happens when the target model agrees or when you win the $p/q$ coin flip), or it's rejected and you resample from the residual distribution $\max(0, p - q)$. The combination of these two cases, weighted by their probabilities of occurring, recovers exactly $p(x)$ at every position.

It's a form of rejection sampling. The draft distribution $q$ acts as the proposal, and the acceptance criterion corrects for the mismatch between $q$ and the target $p$. The math guarantees that you never introduce bias, no matter how bad the draft model is. A terrible draft model just means you reject more often, which is slower but still correct.

To see why the residual distribution matters, think about what would happen if you just rejected the draft token and sampled directly from $p$ instead. That would bias the output, because you'd be overweighting the tokens that $q$ doesn't favor (the cases where rejection happens). The $\max(0, p - q)$ correction is specifically designed to handle this: it only samples from the part of $p$ that $q$ "missed," so the combined accept-or-resample process exactly recovers $p$.

This is worth sitting with for a second, because it's genuinely unusual. Most inference optimizations involve tradeoffs. Quantization trades precision for speed, pruning trades capacity, KV cache compression trades context fidelity. Speculative decoding doesn't trade anything. The output is identical. You're betting that a cheap model can predict what the expensive model would have said, and when the bet fails, you catch the error and fix it before it matters. The worst case is no worse than not trying at all.

How much faster?

So how much does this actually buy you?

The speedup depends on the acceptance rate $\alpha$, the probability that any given draft token gets accepted. If the draft model closely matches the target model's distribution, $\alpha$ is high and most tokens sail through.

The expected number of tokens generated per target-model forward pass is:

where $k$ is the number of draft tokens per round. Let me plug in some numbers.

• $\alpha = 0.8$, $k = 4$: about 3.4 tokens per step. That's a 3.4x speedup over standard decoding.
• $\alpha = 0.9$, $k = 5$: about 4.7 tokens per step.
• $\alpha = 0.5$, $k = 4$: about 1.9 tokens per step. Better than 1, but the draft model is struggling.

The $k+1$ in the exponent accounts for the bonus token. Even when a draft token is rejected, you resample one new token from the target model's adjusted distribution. So the worst case (every draft token rejected immediately) still gives you 1 token per step, exactly the same as standard decoding. You never do worse.

That "never worse" property is important. It means you can turn on speculative decoding unconditionally. If the draft model is terrible for a particular piece of text, you fall back to exactly standard performance. There's no downside case where speculation makes things slower than baseline (assuming the draft model overhead is small relative to the target model's decode latency, which it usually is for the 10x+ size ratios people use in practice).

In real deployments, people report 2-3x speedups on average across mixed workloads. Code generation tends to see the highest gains (sometimes 3-4x), while open-ended conversation sees more modest improvements (1.5-2x). The key variable is always the acceptance rate, which depends on how well the draft model matches the target model's distribution for the specific kind of text being generated.

A worked example

Let me trace through a concrete round to make the mechanics tangible. The numbers are made up but realistic.

Say we're mid-generation. The context so far is "The big dog" and the draft model proposes five tokens: "The", "cat", "sat", "on", "the".

The target model processes all five in one forward pass and produces its own probability distribution at each position. Going left to right:

1. "The" — target gives it $p = 0.85$, draft had $q = 0.70$. Since $p \geq q$, accept.
2. "cat" — target gives $p = 0.40$, draft had $q = 0.35$. Since $p \geq q$, accept.
3. "sat" — target gives $p = 0.30$, draft had $q = 0.25$. Since $p \geq q$, accept.
4. "on" — target gives $p = 0.10$, draft had $q = 0.30$. Since $p < q$, we flip a coin with probability $p/q = 0.33$. The coin comes up reject. We resample from $\text{norm}(\max(0, p - q))$ across the full vocabulary and get "down".
5. "the" — discarded. Everything after the rejection point gets thrown away.

Net result: 3 accepted tokens + 1 resampled token = 4 tokens from one target forward pass. The generation continues from "down", and the draft model starts a new round from there.

The target model didn't just say "no" to "on." It said "I only put 10% probability there, but you put 30%, so I'm going to reject with probability $1 - p/q = 0.67$." And when it rejected, it didn't pick its top token. It sampled from the residual distribution, which captures all the probability mass the target wanted to assign to other tokens. This is what preserves the output distribution exactly: the resampling doesn't just pick the mode of $p$, it samples from $p$ corrected for what $q$ already handled.

When it works and when it doesn't

Not all text is created equal from a speculation standpoint.

The acceptance rate varies enormously depending on what kind of text is being generated. Speculative decoding works best when the draft model is a good predictor of the target model, which means predictable text:

• Code completion: syntax is highly constrained. for i in range( is easy to guess.
• Boilerplate and templates: formulaic prose, structured data, common phrasings.
• Continuation of established patterns: mid-sentence, conventional phrasing, the draft model nails it.

It works less well for:

• Creative writing: unusual word choices, surprising turns. The draft model's guesses diverge.
• Reasoning steps: when the target model is "thinking hard" about a problem and the small model simply can't keep up.
• Highly specific factual recall: names, numbers, domain-specific terms where the small model's knowledge is weaker.

At very low temperatures (near-greedy decoding), both models tend to agree on the top-1 token, which pushes acceptance rates up. But at moderate temperatures where the distribution is spread out, the draft and target models might disagree on the shape of the tail, leading to more rejections. High temperature is generally worse for speculative decoding because the randomness makes both models' predictions less predictable to each other.

The practical consequence is that the acceptance rate varies within a single generation. The first few tokens of a response might run at $\alpha = 0.9$ (common phrasing), then drop to $\alpha = 0.4$ for a tricky insight in the middle, then climb back up for the closing sentence. Good implementations handle this by adjusting $k$ dynamically, drafting more tokens when acceptance is high and fewer when it's low. Some systems even maintain a running estimate of $\alpha$ and use it to pick the optimal $k$ for each round.

Beyond draft models: Medusa

There's an obvious operational downside to the draft-model approach. You need a second model. It has to be small enough to be fast, good enough to have a high acceptance rate, and it needs to share the target model's tokenizer. You have to deploy it alongside the target model, manage the GPU memory split between the two, and keep it loaded and warm. For serving teams already struggling with GPU memory budgets, adding a second model is a real ask.

Cai et al. proposed a different approach called Medusa. Instead of a separate draft model, you add extra prediction heads to the target model itself. Alongside the standard language-model head that predicts position $t+1$, you train additional lightweight heads that predict positions $t+2$, $t+3$, $t+4$, and so on.

Each Medusa head is just a small feedforward network (one or two layers) sitting on top of the target model's last hidden state. During a single forward pass, the base head predicts the next token at position $t+1$, and the Medusa heads predict positions $t+2$, $t+3$, and so on. You then verify those multi-position predictions in a subsequent pass.

The advantage is simplicity: no second model to deploy, and the heads can be trained cheaply on top of a frozen base model (the base weights don't change). And because the predictions come from the target model's own representations, the acceptance rates tend to be solid.

Medusa also introduced tree-structured verification. Instead of proposing a single linear sequence of $k$ tokens, you generate a tree of candidates. At position $t+2$, you might have three candidates (from the Medusa head's top-3 predictions). At $t+3$, each of those branches has its own top candidates. You verify the entire tree in one forward pass using carefully constructed attention masks. The best path through the tree gives you the longest accepted prefix. This is more efficient than linear verification because a single bad prediction at one position doesn't necessarily waste all subsequent positions.

The earlier work by Stern et al. explored a similar idea called blockwise parallel decoding. Medusa refined it with better training objectives and the tree attention mechanism.

The tradeoff with Medusa (and similar head-based approaches) is that prediction quality degrades with distance. The head for position $t+2$ is reasonably accurate. The head for $t+5$ is much worse, because predicting five tokens ahead from a single hidden state is inherently harder than predicting one token ahead. Draft models don't have this problem as severely because each draft token is conditioned on the previous ones. In practice, Medusa tends to use 3-5 heads, not 10.

One more thing about Medusa: the training cost is low. You freeze the base model's weights entirely and only train the new heads, which are tiny. This means you can add Medusa heads to an existing deployment without retraining the main model. The heads train in a few hours on a single GPU, using a small dataset of the target model's own outputs.

Common misconceptions

"Speculative decoding is an approximation." This is the big one, and it's wrong. The output distribution is mathematically identical to sampling from the target model alone. The proofs are in Leviathan et al. and Chen et al. If you run speculative decoding with temperature $T$ and top-$p$ filtering on the target model, you get exactly the same distribution as running the target model alone with those same settings. The algorithm doesn't approximate anything. It just reorganizes the computation to extract more tokens per forward pass.

"The draft model needs to be the same architecture." No. Any model works as long as it shares the tokenizer (or at least the token vocabulary). You could use a tiny 2-layer transformer as a draft for a giant 80-layer MoE model. The architecture is irrelevant because the acceptance criterion only compares probability distributions over tokens, not internal representations. What matters is that both models produce distributions over the same vocabulary.

"Speedup is always $k\times$." The theoretical maximum speedup approaches $k + 1$ (if the acceptance rate were 100%), but real speedup depends heavily on $\alpha$. And you have to account for the overhead of running the draft model. If the draft model's full $k$-step round (all 4 drafts together, not per draft) takes about 20% of the time of one target-model step, your effective speedup at $\alpha = 0.8, k = 4$ is roughly $3.4 / 1.2 \approx 2.8\times$, not $3.4\times$. Still good, but not magic.

"It helps equally with throughput and latency." Speculative decoding primarily helps latency for individual requests. In high-throughput serving with large decode batches, the GPU utilization is already decent from batching, and the draft model competes for the same GPU resources. For throughput-optimized workloads with large batch sizes, the benefit is often minimal. It shines most for latency-sensitive, low-batch scenarios.

What's next

Every optimization in this arc exploits some specific property of the decode loop. The KV cache exploits redundant computation. Batching exploits underutilized bandwidth. Speculative decoding exploits the gap between verification cost and generation cost. They're all responses to the same one-new-row problem from Post 5.3, just attacking it from different angles.

The next post covers continuous batching, how inference engines schedule many requests at once by interleaving their prefill and decode steps, so no GPU cycles sit idle between users.

Additional reading (and watching)

• Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast Inference from Transformers via Speculative Decoding. ICML 2023. First proof that draft-then-verify preserves the exact target distribution.

• Chen, C., et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling. Independent derivation of speculative sampling with the same correctness guarantee.

• Cai, T., et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. Introduced multi-head prediction and tree-structured verification.

• Stern, M., et al. (2018). Blockwise Parallel Decoding for Deep Autoregressive Models. NeurIPS 2018. Early precursor to Medusa-style parallel prediction heads.

• Li, Y., et al. (2024). Eagle: Speculative Sampling Requires Rethinking Feature Uncertainty. Feature-level draft prediction using the target model's hidden states.

• Xia, H., et al. (2024). Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding. Survey covering the full taxonomy of speculative methods as of early 2024.