Speculative Decoding: Mathematical Foundations, Rejection Sampling Dynamics, Draft Architectures, and Serving Latency

Autoregressive language models generate text sequentially, producing one token per forward pass. Because each forward pass must load hundreds of billions of parameters from high-bandwidth memory (HBM) into compute registers to calculate the next token for a small batch, decoding operates in a memory-bandwidth-bound regime with low arithmetic intensity.

Speculative decoding resolves this bottleneck. Introduced independently by Leviathan et al. (2022) and Chen et al. (2023), the technique uses a lightweight mechanism (a draft model, multi-head speculative heads, or prompt lookups) to propose a sequence of candidate tokens. The primary target model then verifies all proposed tokens simultaneously in a single forward pass.

Because modern GPU tensor cores have surplus arithmetic capacity during low-batch inference, verifying $K$ candidate tokens in parallel takes virtually the same wall-clock time as generating a single token sequentially. When combined with a modified rejection sampling algorithm, speculative decoding provides speedups between 2x and 3.5x while mathematically guaranteeing that the output distribution remains identical to standard autoregressive generation from the target model.

The Hardware Bottleneck: Arithmetic Intensity in Autoregressive Decoding

To understand why speculative decoding works, consider the operational mechanics of standard autoregressive generation on modern hardware.

Memory Bandwidth vs. Compute Saturation

The arithmetic intensity of an operation is defined as the ratio of floating-point operations (FLOPs) to memory bytes transferred:

Arithmetic Intensity = FLOPs / Memory Access (Bytes)

During the prefill phase (processing the input prompt), all prompt tokens are processed concurrently. The matrix multiplication involves a weight matrix of size $(d_{in}, d_{out})$ and an activation matrix of size $(B \times L, d_{in})$, where $B$ is batch size and $L$ is sequence length. Because $B \times L$ is large, each loaded weight byte is reused across many token positions, resulting in high arithmetic intensity that fully saturates GPU compute engines.

During the decode phase (generating new tokens one by one), $L = 1$. Generating a single token requires streaming every weight parameter of the target model from HBM to on-chip SRAM/registers to perform vector-matrix products:

FLOPs per token ≈ 2 * P Bytes transferred per token ≈ P * bytes_per_param

For a 70-billion parameter model in 16-bit precision (140 GB of weights), generating a single token requires reading 140 GB from memory to perform 140 GFLOPs of computation. On an NVIDIA H100 SXM GPU with 3.35 TB/s of memory bandwidth and 989 TFLOPS of FP16 tensor core compute:

• Theoretical minimum memory read time: 140 GB / 3350 GB/s ≈ 41.8 milliseconds
• Actual compute time required: 140 GFLOPs / 989 TFLOPS ≈ 0.14 milliseconds

Over 99% of the GPU execution time is spent waiting for memory transfers, while tensor cores remain largely idle.

The Parallel Verification Insight

Transformer architectures compute attention and feedforward transformations across all sequence positions simultaneously when evaluating a multi-token sequence.

If a draft mechanism generates a candidate sequence of $K$ tokens $(x_1, x_2, \dots, x_K)$, the target model can evaluate all $K$ tokens in a single forward pass. The memory bandwidth cost remains identical (loading 140 GB of weights once), while the compute requirement scales to $K \times 140\text{ GFLOPs} = 700\text{ GFLOPs}$ (for $K=5$).

Because 700 GFLOPs still takes less than 1 millisecond of raw compute on an H100, the target model's forward pass duration is virtually unchanged. If multiple candidate tokens are accepted, the system produces several output tokens in the time previously required for one.

Mathematical Foundations: Rejection Sampling Without Distribution Shift

The central achievement of speculative decoding is preserving the exact output distribution of the target model $p(x)$ using samples from an arbitrary draft distribution $q(x)$.

The Modified Rejection Sampling Algorithm

Let $p(x) = P_{target}(x | x_{<i})$ be the target model probability distribution over vocabulary $V$ for the current position, and $q(x) = P_{draft}(x | x_{<i})$ be the draft model probability distribution.

The algorithm proceeds as follows:

1. The draft model generates a sequence of $\gamma$ speculative tokens $(x_1, x_2, \dots, x_\gamma)$ autoregressively, where each $x_i \sim q(\cdot | x_{<i})$.
2. The target model computes logits in parallel for all prefix positions $(x_0, x_1, \dots, x_\gamma)$, obtaining target distributions $p_1, p_2, \dots, p_{\gamma+1}$.
3. For each candidate token $x_i$ from $i = 1$ to $\gamma$:

• Draw a uniform random variable $r \sim \mathcal{U}(0, 1)$.
• Accept $x_i$ if $r \le \min\left(1, \frac{p_i(x_i)}{q_i(x_i)}\right)$.
• If $x_i$ is rejected, stop the verification loop at index $k = i$, reject all subsequent candidate tokens $(x_{k+1}, \dots, x_\gamma)$, and sample a replacement token $x_k$ from the adjusted distribution $p'_k(x)$:

p'_k(x) = max(0, p_k(x) - q_k(x)) / sum_{y in V} max(0, p_k(y) - q_k(y))

1. If all $\gamma$ candidate tokens are accepted, sample an additional token $x_{\gamma+1} \sim p_{\gamma+1}(\cdot)$ directly from the target distribution.

Proof of Exact Distribution Matching

To prove that the generated token at the rejection point $k$ follows target distribution $p(x)$ exactly, analyze the marginal probability of emitting token $x$:

Pr(emitted = x) = Pr(draft accepts x) + Pr(rejection occurs) * Pr(sample x from p')

First, the probability that the draft model proposes $x$ and the target model accepts it is:

Pr(draft accepts x) = q(x) * min(1, p(x) / q(x)) = min(q(x), p(x))

Second, the overall probability of accepting any proposed token is:

alpha = sum_{x in V} min(q(x), p(x))

Consequently, the total rejection probability is:

Pr(rejection) = 1 - alpha = 1 - sum_{x in V} min(q(x), p(x))

Using the identity $p(x) - \min(q(x), p(x)) = \max(0, p(x) - q(x))$, we have:

1 - alpha = sum_{x in V} max(0, p(x) - q(x))

The normalization constant of the adjusted distribution $p'(x)$ exactly equals the rejection probability $1 - \alpha$. When a rejection occurs, sampling from $p'(x)$ yields:

Pr(sample x from p') = max(0, p(x) - q(x)) / (1 - alpha)

Multiplying by the probability of rejection gives:

Pr(rejection) * Pr(sample x from p') = (1 - alpha) * (max(0, p(x) - q(x)) / (1 - alpha)) = max(0, p(x) - q(x))

Summing the acceptance and rejection branches yields the marginal probability:

Pr(emitted = x) = min(q(x), p(x)) + max(0, p(x) - q(x)) = p(x)

The distribution of the emitted token matches $p(x)$ identically. No approximation, distillation penalty, or quality degradation occurs.

Theoretical Efficiency and Speedup Bounds

The performance of speculative decoding is governed by the alignment between the draft and target models, the speculation horizon $\gamma$, and the relative execution cost of the draft step.

Acceptance Rate and Total Variation Distance

The per-token acceptance probability $\alpha$ is directly related to the Total Variation distance $D_{TV}(p, q)$ between the target and draft distributions:

D_TV(p, q) = 0.5 * sum_{x in V} |p(x) - q(x)| = 1 - sum_{x in V} min(p(x), q(x)) = 1 - alpha

alpha = 1 - D_TV(p, q)

When $q(x)$ matches $p(x)$ perfectly, $D_{TV}(p, q) = 0$ and $\alpha = 1$. In practical pairings (e.g. Llama-3-70B verified against Llama-3-8B), typical values of $\alpha$ range between 0.60 and 0.85 depending on task temperature and domain entropy.

Expected Number of Accepted Tokens

Assuming independent acceptance probabilities across positions with mean $\alpha$, the number of tokens accepted before the first rejection follows a truncated geometric distribution. The expected number of accepted candidate tokens plus the final corrective/bonus token emitted per speculative cycle is:

E[N] = sum_{i=0}^{gamma} alpha^i = (1 - alpha^(gamma + 1)) / (1 - alpha)

• If $\alpha = 0.70$ and $\gamma = 5$: $E[N] = (1 - 0.70^6) / (1 - 0.70) \approx 2.94$ tokens per verification cycle.
• If $\alpha = 0.85$ and $\gamma = 5$: $E[N] = (1 - 0.85^6) / (1 - 0.85) \approx 4.15$ tokens per verification cycle.

Theoretical Wall-Clock Speedup

Let $T_{target}$ be the time required for one forward pass of the target model, and $T_{draft}$ be the time for one forward pass of the draft model. Define the relative cost ratio $c = T_{draft} / T_{target}$.

A speculative cycle requires generating $\gamma$ draft tokens sequentially (cost $\gamma \cdot T_{draft}$) plus one target verification pass (cost $T_{target}$). The total wall-clock time per cycle is $(\gamma c + 1) T_{target}$.

Standard decoding generates $E[N]$ tokens in $E[N] \cdot T_{target}$ time. The net speedup $S(\alpha, \gamma, c)$ is:

S(alpha, gamma, c) = E[N] / (gamma * c + 1) = (1 - alpha^(gamma + 1)) / ((1 - alpha) * (gamma * c + 1))

As $\gamma \to \infty$, if $c = 0$ (costless drafting), the speedup approaches the theoretical upper bound:

S_max = 1 / (1 - alpha)

For $\alpha = 0.75$, the maximum possible acceleration is 4.0x. This demonstrates that token-level speculative decoding has an asymptotic ceiling determined entirely by the distribution divergence between the drafter and the verifier.

Architectural Paradigms for Draft Generation

Several drafting mechanisms have emerged to maximize $\alpha$ while minimizing the cost ratio $c$.

[Target Model Only (Standard Autoregressive)]
Step 1: Load Weights -> Generate Token 1 (41.8 ms)
Step 2: Load Weights -> Generate Token 2 (41.8 ms)
Step 3: Load Weights -> Generate Token 3 (41.8 ms)
Total for 3 tokens = 125.4 ms

[Speculative Decoding (Independent Drafter)]
Step 1: Small Draft Model generates 3 tokens (3 x 2.1 ms = 6.3 ms)
Step 2: Target Model verifies 3 tokens in parallel (42.1 ms)
Total for 3 tokens = 48.4 ms (2.59x speedup)

1. Independent Small Draft Models

The standard formulation pairs a large target model with a smaller model from the same family (e.g. Llama-3-70B verified by Llama-3-8B, or Qwen2.5-72B verified by Qwen2.5-7B).

• Advantages: Off-the-shelf deployment with no architectural changes or specialized training.
• Limitations: Requires storing two complete models in GPU memory; vocabulary and tokenizer must match identically; memory bandwidth overhead from loading draft model parameters.

2. Multi-Head Speculation (Medusa)

Introduced by Cai et al. (2024), Medusa eliminates the separate draft model by appending $K$ parallel decoding heads directly on top of the target model's final hidden state.

Head $k$ predicts the token at offset $t + k + 1$ simultaneously using the base model's representations. Because standard autoregressive representations suffer from conditional independence when predicting future offsets, Medusa constructs a tree of candidate continuations evaluated via tree-based attention masks.

3. Feature-Recurrent Speculation (EAGLE and EAGLE-2)

Li et al. (2024) observed that drafting at the token level introduces high uncertainty. EAGLE (Extrapolation Algorithm for Greater Language-model Efficiency) feeds the target model's second-to-top hidden features into a single lightweight transformer decoder layer.

By operating in the continuous feature space rather than discrete token space, EAGLE conditions draft generation on top-level representations, achieving acceptance rates above 80% on standard benchmarks with negligible draft overhead.

4. Non-Parametric Drafters (Prompt Lookup and Lookahead)

For tasks exhibiting high local n-gram redundancy (such as code generation, JSON restructuring, document summarization, or multi-turn retrieval-augmented generation), candidate tokens can be retrieved directly from the prompt context without model parameters.

• Prompt Lookup Decoding: Uses string pattern matching to find matching n-grams in the prompt and speculates the tokens that followed previous occurrences.
• Lookahead Decoding (Fu et al., 2024): Employs Jacobi-iteration style parallel branch rollouts within the target model's attention mechanism to extract local n-gram sequences without a draft model.

Tree-Based Verification and Custom Attention Masks

Early speculative decoding generated a single linear chain of $\gamma$ tokens. If the second token failed verification, all subsequent $\gamma - 2$ tokens were discarded, wasting the target model's remaining verification capacity.

Modern implementations evaluate speculative trees. A draft mechanism generates a branching tree of candidates (e.g. 3 candidates for position 1, 2 branches for each candidate at position 2).

Draft Tree Topology:
         [Root: Token t]
         /      |      \
     [A_1]    [B_1]   [C_1]
     /   \      |       |
   [A_2] [A_3] [B_2]  [C_2]

To verify an arbitrary tree structure in a single target forward pass without cross-branch contamination, the attention matrix uses a custom 2D causal tree mask:

M_{i, j} = 0   if node j is an ancestor of node i in the candidate tree
M_{i, j} = -inf otherwise

Using tree attention, the target model verifies all candidate paths concurrently, selecting the longest valid prefix path accepted by the rejection sampler. This substantially increases the expected accepted length $E[N]$ per cycle without increasing wall-clock verification time.

Serving Economics and Production Trade-Offs

While speculative decoding provides significant single-stream latency reductions, its economic viability depends heavily on serving regime and batch size.

Latency vs. Throughput Trade-Offs

• Low Concurrency (Batch Size 1 to 4): Memory bandwidth is the primary system bottleneck. GPU compute units are underutilized. Speculative decoding delivers 2x to 3x reductions in Time Per Output Token (TPOT) with zero impact on output quality.
• High Concurrency (Batch Size 32 to 128+): As continuous batching aggregates many concurrent requests, aggregate matrix-vector operations become large matrix-matrix multiplications (GEMMs). Arithmetic intensity increases, shifting the system from memory-bandwidth-bound to compute-bound.
• Compute Contention: In compute-bound regimes, generating and verifying speculative tokens consumes FLOPs that would otherwise process tokens for other active requests, reducing total serving throughput (requests per second per GPU).

Memory Footprint and KV Cache Pressure

Deploying speculative decoding introduces additional VRAM requirements:

1. Draft Model Weights: An 8B draft model for a 70B target requires an additional 16 GB of VRAM.
2. Dual KV Caches: In separate-model setups, both the draft model and target model must maintain KV caches for active sequences.
3. Speculation Tree KV Cache: Verifying tree candidates requires allocating KV cache slots for speculative branches before pruning, increasing peak KV memory allocation.

In production engines such as vLLM, TensorRT-LLM, and SGLang, speculative decoding is typically configured dynamically: enabled during low-traffic periods to minimize interactive latency, and dialed down or bypassed during peak traffic to maximize aggregate token throughput.

Sources

• Leviathan, Y., Kalman, M., & Matias, Y. (2022). Fast Inference from Transformers via Speculative Decoding. International Conference on Machine Learning (ICML 2023).
• Chen, C., Borgeaud, S., Irving, G., Lespiau, J. B., Sifre, L., & Jumper, J. (2023). Accelerating Large Language Model Decoding with Speculative Sampling. arXiv preprint arXiv:2302.01318.
• Stern, M., Shazeer, N., & Uszkoreit, J. (2018). Blockwise Parallel Decoding for Deep Autoregressive Models. Advances in Neural Information Processing Systems (NeurIPS 2018).
• Cai, T., Li, Y., Geng, Z., Peng, B., Lee, J. D., Chen, D., & Dao, T. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. arXiv preprint arXiv:2401.10774.
• Li, Y., Wei, F., Zhang, C., & Zhang, H. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty. International Conference on Machine Learning (ICML 2024).
• Fu, Y., Bailis, P., Stoica, I., & Zhang, H. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding. arXiv preprint arXiv:2402.02057.
• Google Research (2024). Looking Back at Speculative Decoding.