Research Paper Teardown
arXiv:2211.17192

Speculative Decoding Paper Breakdown: Lossless Draft-and-Verify Acceleration for Autoregressive Transformers

Definitive mathematical and systems teardown of Speculative Decoding (Leviathan et al., arXiv:2211.17192): overcoming the memory-bandwidth roofline via small draft speculation, parallel target verification, lossless modified rejection sampling, and residual distribution renormalization.

16 min readVerified 2026-09-292 primary sourcesOriginal Paper
Technical paper breakdown illustration.

Paper Methods

  • Draft-Then-Verify Parallel Speculative Execution
  • Lossless Modified Rejection Sampling min(1, p(x) / q(x))
  • Residual Distribution Renormalization norm(max(0, p(x) - q(x)))
  • Expected Token Acceptance Rate (alpha) Wall-Clock Speedup Analysis

Engineering Limitations

  • •Speedup degrades sharply when the draft model acceptance rate alpha drops on out-of-distribution or high-entropy tasks
  • •Requires co-hosting draft and target model weights plus dual KV caches in GPU High Bandwidth Memory
  • •In high-batch saturation regimes where target decoding is already compute-bound, extra verification tokens reduce net throughput

Speculative Decoding Paper Breakdown

A mathematical and hardware-roofline breakdown of Fast Inference from Transformers via Speculative Decoding (Leviathan, Kalman, & Matias, ICML 2023 / arXiv:2211.17192), the foundational paper that proved autoregressive LLM decoding can be accelerated 2x–3x in wall-clock latency while guaranteeing mathematically identical output distributions to standard target-model sampling.

1. The Autoregressive Memory-Bandwidth Roofline

During standard autoregressive generation, generating K tokens from a target model M_p requires K sequential forward passes. At low-to-moderate batch sizes, each decode step reads 100% of the model weights from GPU High Bandwidth Memory (HBM) into SRAM just to process a single token per sequence:

text(3 lines)
1Arithmetic Intensity (Decode, Batch=1) = (2 * P FLOPs) / (2 * P Bytes in FP16) = 1 FLOP / Byte
2H100 SXM5 Ridge Point = 989 TFLOPS / 3.35 TB/s = ~295 FLOPs / Byte

Because 1 FLOP/Byte << 295 FLOPs/Byte, standard decoding utilizes less than 0.5% of Tensor Core compute capacity. Crucially, verifying gamma + 1 tokens in parallel during a single target forward pass takes virtually the same wall-clock HBM weight-transfer time as decoding a single token.

2. Draft-and-Verify Execution Pipeline

Speculative Decoding pairs a fast, lightweight approximation (draft) model M_q with the large target model M_p:

text(13 lines)
1Step 1: Draft Speculation (Sequential, Low HBM Footprint)
2 M_q autoregressively generates gamma draft tokens: x_1, x_2, ..., x_gamma
3 saving draft probability distributions q_1(x), q_2(x), ..., q_gamma(x)
4
5Step 2: Target Parallel Verification (Single Batched Forward Pass)
6 M_p evaluates prefix + [x_1, ..., x_gamma] in ONE forward pass,
7 producing target distributions p_1(x), p_2(x), ..., p_gamma(x), p_{gamma+1}(x)
8
9Step 3: Lossless Rejection Sampling (Left-to-Right Prefix Acceptance)
10 Accept prefix x_1 .. x_{n} using acceptance criterion min(1, p_i(x_i) / q_i(x_i)).
11 On the first rejection at index i, resample x'_i from the residual distribution p'(x).
12 If all gamma tokens are accepted, sample bonus token x_{gamma+1} ~ p_{gamma+1}(x).

Every speculative cycle is guaranteed to advance the sequence by at least 1 token and at most gamma + 1 tokens.

3. Lossless Modified Rejection Sampling & Exact Distribution Proof

Why not simply threshold greedy matches? In temperature/nucleus sampling (T > 0), naively accepting high-probability draft tokens distorts the target probability distribution p(x). Leviathan et al. introduce Modified Rejection Sampling that recovers X ~ p(x) exactly for any arbitrary p(x) and q(x).

The Algorithm at Position i

Given draft token x ~ q(x) and uniform random number r ~ Uniform(0, 1):

  1. Acceptance Rule: If r <= min(1, p(x) / q(x)), accept x.
  2. Rejection & Residual Resampling: Otherwise, reject x (and discard all subsequent draft tokens x_{i+1} ... x_gamma), and sample a replacement token x' directly from the adjusted residual distribution p'(x):
text(2 lines)
1p'(x) = norm( max(0, p(x) - q(x)) ) = max(0, p(x) - q(x)) / sum_{v in V} max(0, p(v) - q(v))

Proof of Exact Distribution Equivalence (P(X = x) = p(x))

The probability of emitting token x from a speculative step is the sum of (a) drafting x and accepting it, plus (b) drafting any token, rejecting it, and resampling x from p'(x).

First, note that the overall acceptance probability alpha equals the overlap integral between p and q:

text(3 lines)
1P(accepted) = sum_{y} q(y) * min(1, p(y) / q(y)) = sum_{y} min(p(y), q(y))
21 - P(accepted) = sum_{y} ( p(y) - min(p(y), q(y)) ) = sum_{y} max(0, p(y) - q(y))

Therefore, the normalization denominator of p'(x) is identically 1 - P(accepted)! Substituting this into the total marginal probability of outputting x:

text(5 lines)
1P(X = x) = q(x) * min(1, p(x) / q(x)) + (1 - P(accepted)) * p'(x)
2 = min(p(x), q(x)) + (1 - P(accepted)) * [ max(0, p(x) - q(x)) / (1 - P(accepted)) ]
3 = min(p(x), q(x)) + max(0, p(x) - q(x))
4 = p(x)

Whether p(x) >= q(x) (where min = q(x) and max = p(x) - q(x)) or p(x) < q(x) (where min = p(x) and max = 0), the sum is identically p(x). Speculative decoding is 100% mathematically lossless.

Reference Implementation: Lossless Speculative Verification Kernel

python(39 lines)
1def speculative_verify_step(
2 draft_tokens: list[int],
3 q_probs: list[list[float]], # [gamma, V] draft distributions
4 p_probs: list[list[float]], # [gamma + 1, V] target distributions
5 uniform_r: list[float], # [gamma] uniform(0, 1) draws
6) -> dict:
7 gamma = len(draft_tokens)
8 vocab_size = len(p_probs[0])
9 accepted_tokens: list[int] = []
10
11 for i in range(gamma):
12 tok = draft_tokens[i]
13 p_x = p_probs[i][tok]
14 q_x = q_probs[i][tok]
15 accept_prob = 1.0 if q_x <= 0.0 else min(1.0, p_x / q_x)
16
17 if uniform_r[i] <= accept_prob:
18 accepted_tokens.append(tok)
19 else:
20 # Compute residual distribution p'(x) = norm(max(0, p(x) - q(x)))
21 raw_residual = [max(0.0, p_probs[i][v] - q_probs[i][v]) for v in range(vocab_size)]
22 norm_z = sum(raw_residual)
23 residual_dist = [val / norm_z for val in raw_residual]
24 # Deterministic argmax or inverse-CDF sample from residual_dist
25 resampled_tok = max(range(vocab_size), key=lambda v: residual_dist[v])
26 return {
27 "emitted_tokens": accepted_tokens + [resampled_tok],
28 "num_accepted_draft": i,
29 "residual_dist": residual_dist,
30 }
31
32 # All gamma draft tokens accepted -> emit bonus token from p_{gamma+1}
33 bonus_tok = max(range(vocab_size), key=lambda v: p_probs[gamma][v])
34 return {
35 "emitted_tokens": accepted_tokens + [bonus_tok],
36 "num_accepted_draft": gamma,
37 "residual_dist": None,
38 }
19 lines hidden

4. Wall-Clock Speedup Bounds & Optimal Lookahead gamma

Let alpha = E[min(p(x), q(x))] be the expected token acceptance rate across the sequence, and let c be the cost ratio between a single forward pass of the draft model M_q and the target model M_p (c = T(M_q) / T(M_p)).

  1. Expected Tokens Generated per Cycle: Because consecutive acceptances follow a truncated geometric distribution of length gamma:
text(2 lines)
1E[# tokens generated] = (1 - alpha^(gamma + 1)) / (1 - alpha)
  1. Net Wall-Clock Speedup Factor: One cycle executes gamma sequential draft steps (gamma * c) plus 1 parallel target verification step (1), yielding:
text(2 lines)
1Speedup(alpha, c, gamma) = (1 - alpha^(gamma + 1)) / ( (1 - alpha) * (gamma * c + 1) )

| Draft Model Cost Ratio c | Acceptance Rate alpha | Optimal Lookahead gamma* | Theoretical tokens/step | Net Wall-Clock Speedup | |---|---|---|---|---| | c = 0.02 (Draft 50x faster) | alpha = 0.80 | gamma = 7 | 4.16 tokens | 3.65x | | c = 0.05 (Draft 20x faster) | alpha = 0.75 | gamma = 5 | 3.29 tokens | 2.63x | | c = 0.10 (Draft 10x faster) | alpha = 0.70 | gamma = 4 | 2.53 tokens | 1.81x | | c = 0.00 (Multi-Token Medusa/MTP) | alpha = 0.80 | gamma = 5 | 3.69 tokens | 3.69x |

5. Production Engineering Takeaways

  1. KV Cache Rollback Mechanics: In PagedAttention engines (vLLM), speculative verification appends gamma candidate slots to the physical KV cache. When token k < gamma is rejected, the KV cache manager simply rewinds the sequence's logical length pointer seq_len = base_len + k + 1 in O(1) metadata time without zeroing physical HBM pages.
  2. Tokenizer & Vocabulary Alignment: p(x) and q(x) must share the exact same vocabulary and BPE tokenizer. Cross-family drafting requires expensive token-to-string-to-token remapping that breaks per-token rejection math.
  3. Transition to Native Multi-Token Prediction (MTP): Modern frontier architectures (such as DeepSeek-V3) eliminate the separate draft model M_q entirely (c -> 0) by training lightweight sequential MTP prediction heads directly on top of the target backbone.