Open Studio
paper breakdown

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.

FullStack AI Hub Editorial16 min readPublished 29 Sep 20262 primary sources
Speculative Decoding Paper Breakdown: Lossless Draft-and-Verify Acceleration for Autoregressive Transformers

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.

Continue Reading

All Blog Posts