Autoregressive decoding in large language models exhibits a severe computational asymmetry. Generating text token by token requires loading every parameter of a multi-billion-parameter network into high-bandwidth memory (HBM) for every forward pass. In low-batch or single-stream inference regimes, the compute units spend the majority of execution cycles waiting for memory transfers, yielding an arithmetic intensity of order O(1) FLOP per byte.
Speculative decoding resolves this bottleneck by decoupling draft token proposal from verification. Introduced by Leviathan et al. (2023) and Chen et al. (2023), the technique uses an efficient draft mechanism to generate multiple candidate tokens, which are subsequently verified in parallel by the target model in a single forward pass. Crucially, through a specialized modified rejection sampling procedure, speculative decoding guarantees zero statistical divergence from the target distribution.
The Memory-Bandwidth Bottleneck in Autoregressive Generation
In standard autoregressive inference, generating a sequence of N tokens from a target model M_p requires N sequential forward passes. For a transformer model with P parameters stored in 16-bit precision (2P bytes), each decoding step fetches 2P bytes from GPU memory to compute a single token update.
On modern accelerators such as the NVIDIA H100 SXM5 (offering 3.35 TB/s of memory bandwidth and 989 TFLOPS of FP16 Tensor Core compute), decoding a single batch (batch size B = 1) on a 70-billion-parameter model requires:
- Memory read per step: 140 GB
- Minimum latency per token: 140 GB / 3.35 TB/s ≈ 41.8 milliseconds
- Theoretical peak generation speed: ~24 tokens per second
During these 41.8 milliseconds, the GPU executes approximately 140 GFLOPs of computation. Given the hardware capacity of nearly 1,000 TFLOPS, the hardware operates at less than 1% of its arithmetic capability.
Speculative decoding leverages this underutilized compute capacity. Because evaluating K candidate tokens concurrently in a single forward pass takes virtually the same wall-clock time as evaluating a single token (as both are dominated by the fixed 140 GB weight-loading overhead), a target model can verify an entire candidate sequence for free if the draft tokens are valid.
The Speculative Sampling Protocol
Let M_p denote the large target model with probability distribution p(x | x_{<t}), and let M_q denote a smaller, computationally inexpensive draft model with probability distribution q(x | x_{<t}).
The generation loop proceeds in iterative draft-and-verify cycles:
- Draft Generation: Starting from context prefix x_{<t}, the draft model M_q autoregressively generates K candidate tokens:
x_t, x_{t+1}, ..., x_{t+K-1} ~ q(·)
- Parallel Target Evaluation: The target model M_p performs a single parallel forward pass over the candidate sequence to evaluate the conditional probabilities:
p(x_t | x_{<t}), p(x_{t+1} | x_{<t+1}), ..., p(x_{t+K} | x_{<t+K})
- Sequential Rejection Sampling: For each candidate index i from 1 to K:
- Draw a uniform random variable u_i ~ U(0, 1).
- Evaluate the acceptance threshold:
α(x_{t+i-1}) = min(1, p(x_{t+i-1} | context) / q(x_{t+i-1} | context))
- If u_i ≤ α(x_{t+i-1}), the candidate token is accepted.
- If u_i > α(x_{t+i-1}), the candidate token is rejected. The remaining draft tokens x_{t+i}, ..., x_{t+K-1} are discarded. A replacement token is immediately sampled from the normalized positive residual distribution:
p'(x) = max(0, p(x) - q(x)) / ∑_{x'} max(0, p(x') - q(x'))
- The current speculative cycle terminates upon the first rejection.
- Bonus Token Generation: If all K draft tokens are accepted, an additional (K+1)-th token is sampled directly from the target distribution p(· | x_{<t+K}), which is already available from the parallel forward pass at zero incremental cost.
Mathematical Proof of Exact Distribution Preservation
A core theoretical property established by Leviathan et al. (2023) is that speculative sampling does not approximate the target model. It samples from the exact target distribution p(x), maintaining an identical output distribution with zero total variation divergence.
Formal Theorem
Let p(x) and q(x) be probability distributions over a discrete vocabulary V. Let X be the random variable produced by the speculative sampling procedure. Then for all x ∈ V: P(X = x) = p(x)
Derivation and Proof
The probability that the procedure outputs token x is the sum of two disjoint events: accepting x during the draft proposal, or rejecting the draft proposal and sampling x from the residual distribution p'(x).
P(X = x) = P(accepted ∧ X = x) + P(rejected ∧ X = x)
Step 1: Probability of Acceptance
The draft model proposes token x with probability q(x). The candidate is accepted with probability α(x) = min(1, p(x)/q(x)). Therefore, the joint probability of proposing and accepting x is:
P(accepted ∧ X = x) = q(x) · min(1, p(x) / q(x)) = min(q(x), p(x))
Step 2: Total Acceptance Rate and Total Rejection Rate
Summing the acceptance probabilities across the entire vocabulary yields the overall acceptance rate β:
β = ∑_{x ∈ V} min(q(x), p(x))
The total probability of rejecting a draft token is 1 - β:
1 - β = 1 - ∑_{x ∈ V} min(q(x), p(x)) 1 - β = ∑_{x ∈ V} p(x) - ∑_{x ∈ V} min(q(x), p(x)) 1 - β = ∑_{x ∈ V} (p(x) - min(q(x), p(x)))
Using the algebraic identity a - min(b, a) = max(0, a - b), this simplifies directly to:
1 - β = ∑_{x ∈ V} max(0, p(x) - q(x))
This confirms that the normalization constant for the residual distribution p'(x) is identically equal to the total rejection probability (1 - β).
Step 3: Probability of Rejection and Resampling
When a rejection occurs (with probability 1 - β), a new token is drawn from the normalized residual distribution:
p'(x) = max(0, p(x) - q(x)) / (1 - β)
The joint probability of rejecting the candidate and drawing token x during resampling is:
P(rejected ∧ X = x) = (1 - β) · p'(x) = (1 - β) · [max(0, p(x) - q(x)) / (1 - β)] = max(0, p(x) - q(x))
Step 4: Combining Acceptance and Resampling Terms
Adding the two disjoint probabilities yields:
P(X = x) = min(q(x), p(x)) + max(0, p(x) - q(x))
Applying the identity min(a, b) + max(0, a - b) = a:
P(X = x) = p(x)
This completes the proof. The total variation distance between the output distribution of speculative decoding P_X and the target distribution P is identically zero: D_TV(P_X, P) = (1/2) ∑_{x ∈ V} |P(X = x) - p(x)| = 0
Acceptance Dynamics and Speedup Equations
The expected speedup of speculative decoding depends directly on the alignment between the draft and target models.
Total Variation Distance and Mean Acceptance Rate
The average single-token acceptance rate β satisfies the relation: β = 1 - D_TV(p, q)
where D_TV(p, q) = (1/2) ∑_{x ∈ V} |p(x) - q(x)|. When the draft model perfectly mimics the target model, D_TV(p, q) = 0 and β = 1.
Expected Generated Tokens per Iteration
In each iteration with lookahead parameter K, the number of accepted tokens follows a truncated geometric progression. If all K tokens are accepted, the bonus token is emitted, yielding K + 1 tokens. If rejection occurs at step i ≤ K, exactly i tokens are emitted (i - 1 accepted drafts plus 1 resampled replacement token).
Assuming independent token acceptance probabilities across positions with mean rate β:
E[N] = ∑_{i=1}^K β^i + 1 = (1 - β^{K+1}) / (1 - β)
For representative acceptance rates observed in practice:
- At β = 0.60 and K = 5: E[N] = 2.38 tokens per iteration
- At β = 0.75 and K = 5: E[N] = 3.29 tokens per iteration
- At β = 0.85 and K = 5: E[N] = 4.14 tokens per iteration
Wall-Clock Speedup Formulation
Let t_q denote the latency of a single draft forward pass, and let t_p denote the latency of a target forward pass. The cost ratio is c = t_q / t_p (typically between 0.03 and 0.10 for small drafter models).
The expected wall-clock speedup S over standard autoregressive decoding is given by:
S = E[N] / (1 + c · K) = (1 - β^{K+1}) / ((1 - β) · (1 + c · K))
This formulation illustrates the fundamental trade-off: increasing K increases the numerator E[N], but also linearly increases the drafting overhead c · K in the denominator while encountering diminishing returns due to β^{K+1}. In practice, optimal K values typically lie between 3 and 6 for independent draft models.
Tree-Structured Speculative Verification
While linear draft sequences generate one token candidate per lookahead step, advanced speculative architectures construct candidate trees to evaluate multiple branching possibilities in parallel.
SpecInfer and Tree Attention Masks
Miao et al. (2023) introduced SpecInfer, which generalizes linear drafting to directed acyclic trees of candidate tokens. Rather than betting on a single sequence, the drafter expands the top-M branching hypotheses.
To verify a tree of candidate tokens in a single target forward pass without cross-branch interference, the target transformer uses a customized 2D Tree Attention Mask.
In standard causal decoding, token i attends to all preceding tokens j ≤ i. In tree verification:
- A candidate token node i in the draft tree attends only to its direct ancestors along its path from the root.
- Tokens in rival branches are masked out (attention weight set to -∞).
- All tree nodes share the common prefix key-value cache.
This custom attention masking enables the target model to evaluate dozens of candidate paths concurrently within a single GEMM operation, boosting the effective acceptance rate per target forward pass by 40% to 70% over linear chains.
Medusa: Multi-Head Speculative Drafters
Rather than deploying an independent small model that requires separate memory allocations and kernel launches, Cai et al. (2024) introduced Medusa. Medusa attaches multiple lightweight linear decoding heads directly on top of the target model's final hidden state:
- Head 1 predicts token t+1
- Head 2 predicts token t+2
- Head k predicts token t+k
During generation, the target model's top hidden state produces multiple token candidates simultaneously. These predictions are assembled into a fixed candidate tree and verified in the subsequent step using tree attention. Because Medusa eliminates the separate draft model entirely, it eliminates inter-model communication overhead and simplifies production deployments.
EAGLE: Feature-Level Speculative Sampling
Li et al. (2024) observed that predicting tokens directly from higher-order heads introduces significant uncertainty. In EAGLE (and EAGLE-2), the draft model operates on the feature representations (hidden vectors) of the target model rather than discrete token sequences alone.
By taking the target model's top-layer hidden states and passing them through a single lightweight transformer decoder layer, EAGLE stabilizes draft quality. EAGLE achieves acceptance rates exceeding β = 0.80 on complex benchmarks, enabling 2.5x to 3.5x wall-clock speedups on standard 8B to 70B parameter models.
Production Trade-offs and Serving Regimes
Deploying speculative decoding in high-throughput enterprise infrastructure introduces specific architectural considerations:
- Batch Concurrency and Throughput Inversion: In high-concurrency serving (where batch sizes exceed 32 or 64), GPU compute utilization is already high. In this regime, the compute cost of verifying rejected tokens begins to compete with genuine batch throughput. Speculative decoding delivers maximum speedup in latency-sensitive, low-batch environments (batch sizes 1 to 8).
- KV Cache Rollback Management: When candidate tokens are rejected, their corresponding key-value cache entries must be evicted or overwritten. Serving engines such as vLLM and SGLang maintain explicit slot-mapping tables to enable zero-overhead rollback of unaccepted draft states.
- Drafter Placement in Multi-GPU Topologies: In tensor-parallel configurations (e.g., 8-GPU tensor parallelism for 70B models), running a small 1B draft model across all 8 GPUs can cause communication latency to dominate computation. Modern serving engines frequently run the drafter on a single dedicated GPU or execute draft heads asynchronously.
Sources
- Fast Inference from Large Language Models via Speculative Decoding - Yaniv Leviathan, Matan Kalman, Yossi Matias (ICML 2023 / arXiv:2211.17192)
- Accelerating Large Language Model Decoding with Speculative Sampling - Charlie Chen, Sebastian Borgeaud, Alireza Ghaffarkhah, Samuel Stanton, Cassian L. Wong, Nicholas Tung, Rishabh Joshi, Matthew R. O'Reilly (DeepMind, 2023)
- SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification - Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, Zhihao Jia (ASPLOS 2024 / arXiv:2305.09781)
- Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads - Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng, Jason D. Lee, Deming Chen, Tri Dao (arXiv:2401.08500)
- EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty - Yuhui Li, Fangyun Wei, Chao Zhang, Hongyang Zhang (ICML 2024 / arXiv:2401.15077)
- Looking Back at Speculative Decoding - Google Research Blog
