You Could Have Come Up with Speculative Decoding

Speculative Decoding is a great example of how good systems understanding can lead to performance increases; in some case around $2-3\times$ decode throughput.¹ It is kind of a perfect study since it involves knowing the entire inference stack from batch scheduling, hardware limitations to the model internals to make it work well.

Starting with the Constraints#

Lets dive into how you could have also come up Speculative Decoding. Whenever you think of optimization, you might imagine various axes of freedom the problem has e.g. to get a specific result you might be able to add more compute, this is a variable you could change; although the relation might not be linear, but the idea is there is a relation. Start with the boundary conditions for our problem; first, you might know that autoregressive decoding is

1. Memory-bound, you can’t just add more compute and expect better results² for small number of batches and

2. you have to generate the $n$-th token before you can generate the $n+1$-th token, meaning decode is inherently sequential.

Note that boundary conditions are just arbitrary here, they are soft conditions to simplify the systems model³. Here is what I think our axes might be.

1. You could find a way to reduce what is loaded from memory, you would stop being memory limited and get closer to the memory/compute roofline. This is where ideas around various attention variants (MQA, GQA etc.) and KV compression techniques lie.⁴

2. Use more of the compute available, since anyways the model needs to be loaded from memory, might as well do more compute for that load.

3. Batch scheduling; when serving a model to a lot of users, you can schedule a number of these decode requests together to a) amortize the cost of loading the full model across all the requests⁵ and b) more efficiently use more of the available compute.

In some techniques, the axes might be coupled e.g. with quantization you get a better FLOPs/bytes both due to higher FLOPS being possible on low bit data types and reduced memory movement due to small size.

Not Every Token is Equal#

Another observation about natural language; which I think almost everybody would know intuitively; is that language has a lot of redundancies and easy repeatable patterns around grammar, repeated phrases and writing conventions.⁶ And you are spending full model’s worth compute and memory to predict something that might locally be very easy to predict, lets take a side quest first to understand this more.

At each decode step, the model has a next token distribution $p$ sample from

$$Y_{i+1} \sim p( \cdot \mid c_i), c_i = (y_{\le i}, x)$$

Here Information Theory gives a way to quantify how predictable this next token is. For the realized token $y_{i+1}$, define its information content (or surprisal), under the model as

$$h_p (y_{i+1} \mid c_i) = - \log_2 p(y_{i+1} \mid c_i)$$

Higher the probability, lesser the new information the token carries and vice versa. Here is a heatmap visualization of how the information content varies with as the sentence becomes syntactically richer.

But the amount of information is know only after a token is sampled from the distribution. To gauge the a sense of the next token information without selecting a token, you would think about aggregate metrics like what would be the expected information value under $p$. This is the conditional entropy of the token

$$H_p (Y_{i+1} \mid c_i) = - \displaystyle\sum_{y \in V} {p (y \mid c_i) \log_2 p (y \mid c_i)}$$

Entropy therefore measures how uncertian is the model about its own outcomes. An entropy of $H$ bits corresponds very loosely to a choice among $2^H$ equally likely choices. Although the full vocabulary may have a lot many tokens, at many positions grammar, repitition, formatting and semantic context reduces a lot choices.

Guessing is Enough?#

This observation suggests another systems opportunity. If a lot of next-token distributions have low entropy, perhaps you don’t need the full large model to predict every token. Remember that decode is memory-bound and has some unused compute capacity.

A cheap proposal mechanism could predict the easy patterns in natural language and manufacture a provisional block of $k$ future tokens, $\hat{y}_{i+1}, \hat{y}_{i+2}, ..., \hat{y}_{i+k}$. It could be a smaller autoregressive model, a parallel prediction model, an n-gram lookup, or a continuation copied from the existing context. Its purpose is to provide the future tokens needed to expose parallel work for the large model. For example, say “The cat” is $c_i$ and the proposed next tokens are “sat on a mat” ($\hat{y}$s).

Now these proposals might be totally wrong. How do you verify them cheaply? First, simply run a causally masked forward pass on the $\hat{y}$ sequence and get distributions from the large model conditioned on the preceding draft prefix. These are calculated at a better arithmetic intensity than vanilla decode. Assuming you are using greedy decoding⁷, you would get

$$\begin{aligned} y_{i+1} &= \operatorname*{arg\,max}_y p(\,\cdot \mid c_i) \\ y_{i+2} &= \operatorname*{arg\,max}_y p(\,\cdot \mid c_i, \hat{y}_{i+1}) \\ y_{i+3} &= \operatorname*{arg\,max}_y p(\,\cdot \mid c_i, \hat{y}_{i+1}, \hat{y}_{i+2}) \\ &\vdots \\ y_{i+k+1} &= \operatorname*{arg\,max}_y p(\,\cdot \mid c_i, \hat{y}_{i+1}, \hat{y}_{i+2}, \dots, \hat{y}_{i+k}) \end{aligned}$$

What do you do with these? Notice how you can verify the entire sequence using this forward pass by comparing $y$s and $\hat{y}$s. If they match the draft prediction, keep the token; at the first mismatch, emit the large model’s token and drop the remaining draft tokens. The expectation is that more often than not a good chunk of the draft sequence will match. In the example above, say verification gives “sat”, “on”, “the” while the draft proposed “sat on a mat”. The first two tokens match and are kept, “the” is emitted from the large model, and “a mat” is dropped because it was conditioned on a token that was not accepted.

If all $k$ proposals are accepted, the final distribution computed by the same forward pass,

$$p(\cdot \mid c_i, \hat y_{i+1}, \ldots, \hat y_{i+k}),$$

provides one additional target token. A successful round can therefore produce $k+1$ tokens even though the proposer supplied only $k$. This greedy construction is closely related to earlier work on blockwise parallel decoding.⁸

Preservation of Target Distributon#

But greedy decoding is just a special case. It removes diversity from the output and can produce repetitive, degenerate continuations. Real deployments use temperature, top-k, or top-p sampling⁹. If speculative decoding is only a systems-level optimization, it should not change the target model’s sampling distribution.

Suppose the proposer samples a token $\hat{y}$ from a distribution $q$, while $p$ is the target model’s distribution. Here $p$ and $q$ mean the final distributions after applying temperature and any top-k or top-p transformation, not necessarily the raw softmax distributions. Instead of comparing single tokens, ask how you can retain the proposed token from $q$ without changing its frequency under $p$. Imagine running the sampling step many times, where the proposer outputs $y$ with probability $q(y)$ and the target model wants it to appear with probability $p(y)$. If $q(y) \le p(y)$, every proposal of $y$ can be accepted since the draft does not propose $y$ more frequently than the target permits. If $q(y) > p(y)$, accepting every proposal would overindex it. Retain only the fraction $\frac{p(y)}{q(y)}$ of these proposals¹⁰. Combining these cases, draft tokens are accepted with probability

$$a(\hat y) = \min\left(1,\frac{p(\hat y)}{q(\hat y)}\right)$$

To turn this acceptance probability into a yes/no decision, sample $u\sim U(0,1)$ and accept when

$$u \le a(\hat y).$$

This works because, for any $a\in[0,1]$, the fraction of the unit interval below $a$ is exactly $a$:

$$\Pr_{u\sim U(0,1)}(u\le a)=a.$$

The uniform draw therefore gives us a Bernoulli event with exactly the acceptance probability required above. This accepts as much of the draft distribution as possible without assigning any token more probability than the target model does. The accepted tokens have the probability mass

$$q(y)a(y) = \min\left(q(y), p(y)\right)$$

This is not yet all of $p$. The target probability still missing for token $y$ is

$$p(y) - \min\left(p(y), q(y)\right) = \max\left(0, p(y) - q(y)\right)$$

This implies that when a proposal is rejected, a replacement can be sampled from the remaining normalized mass.

$$p_{\text{res}}(y) = \frac{\max(0, p(y) - q(y))}{\sum_z \max(0, p(z) - q(z))}$$

The residual distribution when the proposal is rejected plus the distribution where the proposal is accepted both combine to give the original target distribution $p$. With this, the final token has the same distribution as a token sampled directly from the large model. To know how often this succeeds, take the expected acceptance

$$\begin{aligned} \alpha &= \mathbb{E}_{y \sim q} [a(\hat{y})] \\ &= \sum_y q(y)a(y) \\ &= \sum_y q(y)\min\left(1,\frac{p(y)}{q(y)}\right) \\ &=\sum_y\min(p(y),q(y)). \end{aligned}$$

Since $\min(p(y),q(y))=\frac{p(y)+q(y)-|p(y)-q(y)|}{2}$

$$\begin{aligned} \alpha &=1-\frac12\sum_y|p(y)-q(y)|\\ &=1-\operatorname{TV}(p,q), \end{aligned}$$

Here $\operatorname{TV}(p,q)=\frac12\sum_y|p(y)-q(y)|$ is the total variation distance¹¹ between the draft and target distributions. This has a very meaningful implication. The shared probability mass is accepted, while the non-overlapping mass is rejected and corrected. So

$$\Pr(\text{accept})=1-\operatorname{TV}(p,q), \qquad \Pr(\text{reject})=\operatorname{TV}(p,q).$$

Note that greedy decoding is a special case for this where $p$ collapses to

$$\text{For } g = \operatorname*{arg\,max}_y p(y \mid c) \\ p'(y) = \begin{cases} 1 & \text{if } y = g \\ 0 & \text{otherwise} \end{cases}$$

A matching draft token is accepted with probability one, while every other token is rejected.

When is it Actually Faster?#

Lets refocus on performance. Every speculative decoding round produces at least one token, either a correction at first rejection or an additional target token when every proposal is accepted. Say $A_j$ is the event that the first $j$ draft tokens are accepted, and let $Z$ be the number of tokens produced by the round. Then

$$G = \mathbb{E}[Z] = 1 + \sum_{j=1}^{k}\Pr(A_j).$$

The initial $1$ is the token that the target pass always produces. Each additional term is another draft token that survives verification. As a simplification, assume independent events with average probability $\alpha$; then $\Pr(A_j)=\alpha^j$. This gives

$$\begin{aligned} G = \mathbb{E}[Z] &= 1 + \alpha + \alpha^2 + \cdots + \alpha^k \\ &= \frac{1-\alpha^{k+1}}{1-\alpha}. \end{aligned}$$

Do a sanity check: $\alpha=0$ implies just one token and speculation gives us nothing, while as $\alpha\to1$ the round produces close to $k+1$ tokens. Increasing $k$ also has diminishing effect on $G$: as $k\to\infty$, $G$ approaches $1/(1-\alpha)$. For $\alpha=0.7$, this means a round produces at most $3.33$ tokens on average under this approximation. For example, with $k=4$, $W=5$, and $\alpha=0.7$,

$$G = 1 + 0.7 + 0.7^2 + 0.7^3 + 0.7^4 \approx 2.77.$$

Speedup#

Higher number of tokens per decode is not itself the full systems speedup, other latencies need to be taken into account. Say $T_p$ is the latency on one decode step on target model, $T_v$ is the verification latency, $T_d$ the latency of producing all drafts and $G = \mathbb{E}[Z]$ the expected number of useful output tokens. For speedup its easy to say time to produce useful draft token should be less than the decode step. Based on the system there might be another $T_comms$ for scheduling the drafting or verification operations, for sake of this model, lets assume its very small.

$$\frac{T_d + T_v}{G} < T_p \\ \implies S = \boxed{\frac{GT_p}{T_d + T_v}}$$

Analyze this a little deeper and setup the consequent dependencies of each time term.

$B$	Batch Size
$N$	# of target model parameters
$s$	Number of bytes per weight
$F$	Peak FLOP/s of the accelerator
$M$	Memory Bandwidth of the accelerator
$W$	Target-equivalent positions evaluated during verification ($k+1$)
$L$	Context length
$\kappa(L)$	Existing KV-cache bytes read per sequence per decode step
$\kappa_v(W, L)$	Existing-prefix bytes read per sequence per verification pass.
$c(L)$	Compute FLOPs per token
$T_p(B, L)$	Latency of one target decode step
$T_v(B, W, L)$	Latency for target verification over k proposals
$T_d(B, W, L)$	Latency of producing the draft

Think of a simplified roofline model on a single device and assuming perfect memory / compute overlap. Now lets build out the $T_p$ and $T_v$ values

$$T_p(B, L) \approx \max\left(T_p^{mem}, T_p^{compute}\right) = \max\left( \frac{sN + B\kappa(L)}{M}, \frac{Bc(L)}{F} \right)$$

The critical batch size where decode becomes compute bound $B_p^*$ is when

$$\frac{B_p^* c(L)}{F} = \frac{sN + B_p^* \kappa(L)}{M} \implies B_p^* = \frac{FsN}{Mc(L) - F\kappa(L)}$$

$F/M$ is a constant and substituing $\rho = F/M$

$$B_p^* = \frac{\rho sN}{c(L) - \rho\kappa(L)}$$

Similarly for $T_v$, same weight traffi but $W$ times more compute is done to verify the drafts

$$T_v(B, W, L) = \max\left( \frac{sN + B\kappa_v(W,L)}{M}, \frac{WBc(L)}{F} \right)$$

and consequently its easy to derive that the critical batch $B_v^*$ is

$$B_v^* = \frac{\rho sN}{Wc(L) - \rho\kappa_v(W, L)}$$

For short context the KV cache traffics $\kappa(L) \to 0$ and $\kappa_v(W, L) \to 0$ which means.

$$\begin{aligned} \frac{B_p^*}{B_v^*} &= \frac{Wc(L) - \rho\kappa_v(W,L)}{c(L) - \rho\kappa(L)} \\[1em] \frac{B_p^*}{B_v^*} &\approx W \qquad (\text{short context}) \end{aligned}$$

This means verification becomes compute-bound much earlier than ordinary decoding, confirming that block verification has higher arithmetic intensity. But $B_v^*$ is only where verification becomes compute-bound; this is not the break-even point where speculative decoding becomes helpful. Using $G=\mathbb{E}[Z]$ from above, speedup for short contexts can be defined as

$$\begin{aligned} S &= \frac{G \cdot T_p}{T_d + T_v} \\ &= \frac{G \cdot \max(T_{mem}, 2BN / F)}{T_d + \max(T_{mem}, 2BNW/F)} \qquad \text{extracting } T_{mem} \\ &= \frac{G \cdot \max(1, B / B_p^*)}{\delta(B) + \max(1, B / B_v^*)} \qquad \text{where } \delta(B) = T_d(B) / T_{mem} \end{aligned}$$

Here $T_d$ and therefore $\delta$ can generally depend on batch size. Generaly, $\delta$ will increase with $B$. Under this approximation, you might see three regimes coming out of this.

Regime	Batch	Decode	Verification	Speedup
I	$B < B_v^*$	Memory-Bound	Memory-Bound	$\frac{G}{1 + \delta(B)}$
II	$B_v^* \le B < B_p^*$	Memory-Bound	Compute-Bound	$\frac{G}{B/B_v^* + \delta(B)}$
III	$B \ge B_p^*$	Compute-Bound	Compute-Bound	$\text{bounded by } G/W$

Regime I can be flat to slightly decreasing since $T_d$ depending on the drafing mechanism might not change much. At fixed acceptance, regime II loses speedup as verification becomes more expensive, provided draft latency does not decrease. In regime III, the trend depends on drafting’s cost relative to ordinary decoding.

Absolute throughput can increase with batch size while the relative speedup of speculative decoding decreases. Liu et al. observe this distinction in their vLLM evaluation: for Llama 3.1 8B on GSM8K, EAGLE’s speedup drops from $1.73\times$ at batch 1 to $1.21\times$ at batch 128.¹² Speculation still helps at both endpoints.

Long-Context effects#

While short-context gives a decreasing trend; for medium-to-long context length there is a transition towards a memory bound regime again because while the weight loading can be amortized over a batch, KV cache needs to be loaded for each request.

This creates another interesting relation. $S$ can also be written as

$$S = \frac{G}{T_d/T_p + T_v/T_p}$$

If existing KV reads dominate both decode and verification latency, and both achieve comparable memory bandwidth, this is true

$$\frac{T_v}{T_p} \approx \frac{\kappa_v(W, L)}{\kappa(L)}$$

Verifcaiton and target decode do share a prefix so the ratio depends on how well does our inference engine support this KV reuse. At one end where $\kappa_v(W, L) = W \cdot \kappa(L)$ there is no KV reuse the penalty is paid in speedup. At the other end where $\kappa_v(W, L) = \kappa(L)$, KV values are loaded once and resuse for all $W$ proposals. Reality is often somewhere between these. Assuming the best KV resuse $T_v/T_p$ is about constant in the long context regime.

With fixed $G$ now speedup mainly depends on $T_d/T_p$ ratio only, where $T_p$ grows with the context length and batch, but $T_d$ is highly dependeny on the proposal mechanism. $T_d/T_p$ falls when draft latency grows more slowly as compared to the target latency and can flatten when both scale with B.

Choosing drafting width#

Another interesting question to ask is: What is the optimal $W$? A wider draft exposes more parallel target work, but later proposals are useful only when every proposal before them survives. At the same time, both drafting and verification generally become more expensive. Intuition would say that small width is bad since you are not doing enough work, while large $W$ is also bad since $G$ saturates very quickly. There should be a middle ground. Simply, the optimal $W^*$ would be

$$\begin{aligned} W^* &= \operatorname*{arg\,max}_W S \\ &= \operatorname*{arg\,max}_W \frac{G(W)}{T_d(W) + T_v(W)} \qquad T_p \text{ doesn't depend on } W. \end{aligned}$$

Let $T(W)=T_d(W)+T_v(W)$. Adding one more speculative position is useful while

$$\frac{\Delta G(W)}{G(W)} > \frac{\Delta T(W)}{T(W)}.$$

At the crossover the two sides are equal. This isn’t easy to solve analytically, but there are insights that can be extracted from it. Since $W=k+1$,

$$G(W) = 1 + \alpha + \alpha^2 + \cdots + \alpha^{W-1},$$

and therefore

$$G(W+1)-G(W)=\Delta G(W)=\alpha^W.$$

This means the benefit of adding new tokens drops exponentially ($\alpha\le1$). On the other hand, $T$ is expected to increase as $W$ grows, with $T_v$ eventually growing linearly once verification becomes compute-bound and $T_d$ depending on the proposal mechanism.

The optimal width is controlled by both an algorithmic limit, where prefix-survival probability becomes too small, and a hardware limit, where verification consumes the remaining compute capacity. In practice the algorithmic limit usually arrives first, which is why useful draft widths remain in the single digits even when an ideal roofline suggests capacity for hundreds of positions¹³. This also suggests that $W$ should not necessarily be fixed. A serving system can draft farther when the proposer is confident and stop early when the estimated survival probability of the next token no longer repays its marginal cost.¹⁴

Optimization Design Space#

Lets sum up the design space that follows directly from the speedup equation:

• $\uparrow G$: better drafts.
• $\downarrow T_d$: faster proposal mechanisms, n-grams, prompt lookups, retrieval, etc.
• $\uparrow G/T_v$: adaptive $W$, trees, and dynamic speculation that increase useful output per unit of verification time.¹⁵
• $\downarrow T_v$ at fixed $G$: better block kernels and KV reuse.
• Specialize the drafting and verification stages: disaggregated drafting.

Trees and wider candidate sets can increase both $G$ and $T_v$, so $G/T_v$ is the relevant verifier-efficiency ratio rather than $T_v$ alone. End to end, the objective is still $G/(T_d+T_v)$.

The last axis can even become a hardware topology. NVIDIA describes an external-drafter configuration where Groq 3 LPX runs the draft model and Vera Rubin NVL72 verifies and commits tokens.¹⁶ Each rack maintains its own model’s KV cache. Draft tokens are sent to the verifier, which returns rejected-position feedback for the next chunk. This is the same algorithmic decomposition expressed physically: one system manufactures future tokens and another verifies them.

I think this should be enough of an introduction to speculative decoding to convince you that it is not just some weird trick that came out of non-obvious concepts. It is a systems technique for converting predictable future work into concurrency while preserving the original decoder distribution.

Footnotes#

1. The two foundational works are Leviathan et. al., Fast Inference from Transformers via Speculative Decoding and Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling. They independently report roughly $2–3\times$ latency improvements while preserving the target distribution. ↩

2. At low token batches, autoregressive decoding is commonly dominated by parameter and KV-cache movement rather than arithmetic. See Pope et al., Efficiently Scaling Transformer Inference and Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling. ↩

3. You can actually say that you would change the model architecture to do parallel decode, in turn increasing the arithmetic intensity of the decode operation. This would also, theorectially, be a new axis to look at. ↩

4. See Shazeer, Fast Transformer Decoding: One Write-Head is All You Need for multi-query attention, vLLM for PagedAttention, and SGLang for RadixAttention. ↩

5. You might still be bound by KV-cache bytes per token since they must be loaded separately for each request in the batch. ↩

6. Shannon’s Prediction and Entropy of Printed English is the classic information-theoretic study of redundancy and predictability in natural language. ↩

7. For this first intuition, both the proposer and target use greedy decoding. ↩

8. Stern, Shazeer, and Uszkoreit, Blockwise Parallel Decoding for Deep Autoregressive Models developed this idea for greedy decoding before lossless speculative sampling generalized it to stochastic decoding. ↩

9. Temperature, top-k, and top-p can all be viewed as transformations that produce the final distribution from which a token is sampled. ↩

10. This resembles rejection sampling, but standard rejection sampling uses a global envelope $M$ and repeatedly samples from $q$, accepting with probability $p(y)/(Mq(y))$. Speculative sampling instead accepts the maximal shared mass $\min(p,q)$ and, on rejection, samples once from the residual target mass $\max(0,p-q)$. This is why Chen et al. call it modified rejection sampling. ↩

11. Wiki Total Variational Distance. ↩

12. Liu et al., Speculative Decoding: Performance or Illusion?, Section 3.2 and Figure 1. Speedup is measured as the ratio of generated-token throughput with and without speculative decoding. See Tables 5 and 6 for hardware and proposal configurations. ↩

13. At $B=1$, an ideal H100 BF16 roofline gives $\rho=F/M\approx295$ FLOP/byte and, for short context with $c(L)\approx2N$ and $s=2$, $W_{\mathrm{ridge}}\approx\rho s/2\approx295$. This is a theoretical hardware ridge, not a useful draft width. ↩

14. Dynamic Speculation Lookahead Accelerates Speculative Decoding of Large Language Models shows that a fixed lookahead is generally suboptimal and reports improvements from selecting it dynamically. ↩

15. Tree verification explores several candidate futures instead of one chain. See SpecInfer and Sequoia. ↩

16. NVIDIA, How NVIDIA Groq 3 LPX Unlocks Ultrafast Interactivity at Long Context on NVIDIA Vera Rubin. NVIDIA calls this configuration external-drafter speculative decoding. ↩