How Speculative Decoding Works (and When It Doesn't)

The standard transformer-based large language model produces one token at a time ^[1]. Each generated token requires a full forward pass through the network, and each pass streams the model weights from GPU memory. During decoding, the GPU spends much of its time waiting on memory bandwidth rather than computation, leaving the tensor cores underutilized ^[3]. Speculative decoding changes this by adding a small amount of extra computation: a lightweight draft model proposes several tokens before each verifier forward pass. A small, fast draft model predicts the next few tokens; and our large base model (the verifier) verifies them all in a single forward pass, accepting the longest prefix that it agrees with before sampling a replacement for the first rejected token.

When the draft model predicts well, one verifier pass can emit multiple tokens. When it doesn’t, the verifier still produces the same next token it would have generated without speculation. Done correctly, speculative decoding speeds up generation while leaving the output distribution exactly unchanged ^[4]. The rest of the post covers where the speedup comes from, why the output is identical (lossless), and when speculation stops helping.

Prefill and Decode

Every linear layer in a transformer multiplies an activation matrix by a fixed weight matrix. The weight dimensions $d$ and $d_{out}$ are set by the architecture; the only thing that varies between forward passes is $M$, the number of tokens flowing through the layer. Because each token corresponds to one row of the activation matrix and every row reuses the same weights, the cost of the feed-forward and projection layers scales linearly with $M$. This naturally splits inference into two phases.

Prefill processes the prompt all at once. For a batch of $B$ sequences of length $S$, every matmul sees $M = B \times S$ tokens (often many thousands of rows). The activation matrix is tall, the weights are reused across all of those rows, and the result is exactly the kind of large matrix–matrix multiplication that accelerator tensor cores are built for. Decode generates the response one token at a time, each conditioned on everything before it. A single step emits one token per sequence, so $M = B$, and in latency-sensitive settings $B$ is often $1$. The multiplication effectively collapses to a matrix–vector product (or a very skinny matrix–matrix multiply when $B > 1$). To produce that handful of tokens, the step must still stream the model's entire weight set (typically tens of gigabytes) from memory, while performing only a relatively little amount of arithmetic on it.

To make the contrast precise we use arithmetic intensity ^[2]: the number of floating-point operations an operation performs per byte it reads from memory. The arithmetic intensity of a linear layer is easy to derive. A matrix multiplication performs two floating-point operations per multiply–accumulate and reads the weight matrix once, at $b$ bytes per element:

The layer dimensions cancel completely. Arithmetic intensity depends only on the number of tokens in the pass and the numerical precision. With $bf16$ ($b = 2$) it is approximately $M$, roughly one FLOP per byte per token. Every accelerator has a hardware-specific ratio of peak compute to memory bandwidth, its ridge point. An operation whose intensity sits below the ridge cannot keep the arithmetic units fed: it waits on memory and is memory-bound. Above the ridge it is compute-bound. Prefill, with $M$ in the thousands, sits comfortably in the compute-bound region. Decode with $M = 1$ has intensity near $1$, so the matmul runs far below peak compute while the weights stream in.

Attention layers also read the KV cache: the keys and values computed for all previous tokens, stored so they do not have to be recomputed at every decoding step. At each decoding step, the new token’s query attends over the entire cached context, so it reads the whole cache. For one sequence at context length $S$ the memory read in bytes is

with the factor of two accounting for keys and values, and it grows with both context length and batch size. The dominant matrix operations in decode-time attention have arithmetic intensity

roughly one FLOP per byte for standard attention. The context length $S$ cancels out. Decode-time attention remains memory-bound regardless of context length. And because each sequence reads its own cache while the weights are shared across the whole batch, at long context or large batch the KV traffic can outweigh weight traffic entirely.

The cost of a decoding step is therefore dominated by moving data: reading the model weights and the KV cache, with comparatively little arithmetic performed on either. This leaves compute units underutilized. Speculative decoding exploits that imbalance by using the otherwise idle compute to generate multiple candidate tokens per verifier pass, increasing the amount of useful work done for each trip through memory.

How speculative decoding works

Speculative decoding uses two models ^[5]. The first is the target, the model whose output you actually want. The second is a drafter, a much smaller and faster model. The drafter generates the next $k$ tokens one at a time, but because it is small this is cheap. It speculates a guess at what the target would have generated. The target then verifies all $k$ proposed tokens in a single forward pass. It runs over the $k$ proposed tokens and, at each position, computes its own distribution for the next token. It walks through the proposed tokens from left to right, accepts the longest prefix whose tokens pass the verification test. At the first token it rejects, it discards the rest of the draft and resamples that one position from its own distribution. If it rejects the very first token, it still emits a token there, so a step never produces fewer tokens than plain decode. Because the pass also yields a distribution for the position just past the last proposed token, a draft of $k$ tokens accepted in full commits $k+1$ tokens.

The verify pass performs essentially the same memory reads (the same model weights and nearly the same KV cache) but now carries $k$ tokens per sequence instead of one. The arithmetic grows with $k$; the memory traffic barely changes. On the roofline, increasing $M$ by roughly $k$ shifts the verify pass $k$ times to the right, toward the compute-bound region. As long as it remains below the roofline the runtime is still dominated by memory traffic, which has changed very little. One verification pass can process several tokens for nearly the cost of a single decode step. As long as the larger pass is still memory-bound, its time is set by the reads, and the reads did not grow. So the $k+1$ tokens of a fully accepted draft come out of a single step. And that’s the speedup: more tokens per read of the model.

However, the drafter is not free. Producing the $k$ draft tokens is its own work, the small model runs $k$ times. The cost is paid on every step, whether or not the drafted tokens are accepted or rejected. And this is where the tradeoff in picking a drafter comes up. $\alpha$ is the rate at which the target accepts a draft token. The tokens committed per step climb with $\alpha$ while the per-step overhead climbs with how expensive the drafter is to run. A cheap, less accurate drafter will keep the overhead small but guesses worse so the target rejects earlier. A larger more accurate drafter is likely to have a longer prefix accepted per draft and commits more per step, but each rejected token is now more wasted compute. The ideal drafter is therefore not the most accurate possible model. It is the model that produces the largest increase in accepted tokens for the smallest additional compute. In practice, that means matching the target closely on the easy, predictable tokens while remaining inexpensive to run.

Why the output doesn't change

The drafter and the target are different models with different next-token distributions, so why doesn't sampling from the drafter change the output? The answer is the accept/reject rule ^[4]. Let the target’s distribution at a position be $p$ and the drafter’s be $q$. The rule transforms a sample from $q$ into one distributed exactly as $p$. For a proposed token:

1. Sample $x \sim q$.
2. Accept with probability $\min!\left(1,\ \dfrac{p(x)}{q(x)}\right)$ and emit it.
3. Otherwise, draw the emitted token from the residual

Intuitively, the residual puts back exactly the probability mass that was “missing” from the drafter.

This emits $x$ with probability exactly $p(x)$. A token can be emitted in only two ways.

1. It is proposed and accepted. The drafter proposes it with probability $q(x)$ and accepts it with probability $\min(1, p(x)/q(x))$, contributing $\min(p(x), q(x))$.
2. The proposal is rejected. Then $x$ is drawn from the residual. The total probability of rejection is exactly the normalization constant of the residual distribution, so the normalization cancels leaving $\max(0,\ p(x) - q(x))$.

Adding the two contributions:

When $p(x) \ge q(x)$ the terms are $q(x)$ and $p(x) - q(x)$; when $p(x) < q(x)$ they are $p(x)$ and zero. Either way the emitted probability is $p(x)$.

The probability that a drafted token is accepted is the mass the two distributions share:

where $\mathrm{TV}$ denotes the total variation distance between the two distributions. A drafter that closely matches the target has small $\mathrm{TV}$ distance and therefore high acceptance. Acceptance rate is the only thing the drafter’s quality controls. A bad drafter is slow, never wrong: rejected tokens are replaced by exact draws from $p$, so the output is identical to what plain decoding would have produced. The same quantity that guarantees correctness also determines performance. Suppose, as a simple approximation, that each drafted token is accepted independently with probability $a$, and we draft $g$ tokens. A step commits the token at position $i$ whenever the first $i$ drafts were all accepted, which happens with probability $a^{i}$ — for $i$ from $0$ (the guaranteed token) up to $g$. The expected number of committed tokens per step is therefore

Since a verification pass costs roughly the same as a single decode step while committing this many tokens on average, the expectation is also the idealized speedup. There are two things to note. First, speedup is far more sensitive to acceptance than to draft length: increasing $a$ lifts every term in the sum, whereas increasing $g$ only adds new terms at the tail. Second, returns diminish with larger drafts: once $a^{g+1}$ is negligible, proposing more tokens contributes almost nothing, because those positions are rarely accepted.

Exactness is a choice

The exact accept/reject rule is not the only possible choice. The $\min(1, p/q)$ test plus residual resampling is just one way to make the emitted token come out as a draw from $p$. If you’re willing to give up exact sampling from $p$, you can accept proposals more aggressively. Medusa's typical acceptance ^[6] drops rejection sampling for a single test: keep a drafted token if the target gives it a probability above a threshold, and let that threshold scale with the entropy of the target. Typical acceptance compares the target probability of the proposed token against a threshold that depends on the entropy of the target distribution:

with $\epsilon$ a hard floor and $\delta$ setting how fast the bar moves with entropy. When the target is confident, the bar is high and only the dominant token clears it. When the target is uncertain, probability mass is spread across many tokens. The threshold therefore drops; otherwise, nearly every proposal from a high-entropy distribution would be rejected.

This accepts more drafted tokens and avoids exact rejection sampling, making the overall procedure faster. But the output is no longer $p$: some tokens survive that the exact rule would have replaced. In practice, the drift is small at low temperatures and grows as sampling becomes more stochastic. At temperature zero the target distribution collapses to its argmax, so both schemes select the same token and produce identical output. Differences appear only once sampling is enabled and multiple tokens carry meaningful probability mass. Losslessness is therefore a design choice, not a requirement. The exact rule preserves the target distribution exactly; typical acceptance trades some fidelity for higher throughput.

When speculation stops helping

The speedup from speculative decoding assumes the verify pass is memory-bound. In that regime, runtime is dominated by moving model weights from memory, so verifying additional candidate tokens adds relatively little cost. This assumption breaks once the verify pass crosses the roofline into the compute-bound regime. As batch size increases, the weight matrix multiplications reach the roofline, the GPU runs out of idle FLOPs, and verifying $k$ tokens costs roughly $k$ times as much as decoding one. At that point the amortization disappears: every additional draft token requires proportionally more compute, leaving only drafting overhead and rejected work. Speedup falls toward $1\times$, and speculation can even become slower than plain decoding.

This is why speculative decoding is primarily a latency optimization. Small batches tend to be memory-bound, while large batches are often chosen specifically to saturate compute and maximize throughput. But batch size is not the whole story. Long contexts increase KV-cache traffic, and enough KV traffic can push decoding back into the memory-bound regime. In other words, speculation helps when the bottleneck is data movement, whether that data is model weights or the KV cache.

The practical rule is simple: speculate whenever the decoding step is memory-bound, not merely when the batch is small. Whether decoding is memory-bound depends jointly on batch size and context length. That’s why serving systems such as vLLM enable speculation only below configurable thresholds. Speculative decoding doesn’t make the model smarter or reduce the amount of information it must process. It simply exploits a hardware imbalance: during memory-bound decoding, GPUs have idle compute. As models, hardware, and serving systems evolve, the details of the speculation algorithm may change, but that underlying idea remains the same.

In future posts, I’ll look at different drafter designs, ranging from lightweight model-based approaches to model-free methods.

References