Core Idea: Draft & Verify

Speculative decoding turns the sequential decode bottleneck into a parallel verification problem: a fast draft model proposes multiple tokens, and the target model checks them all in one forward pass. When the draft is good, you get multiple tokens for the cost of ~one decode step.

1. The Serial Bottleneck

Standard autoregressive decoding generates one token per step. Each step loads the entire model’s weights from HBM — regardless of whether you generate 1 token or 100, the weight-loading cost is the same.

\text{Decode time} = \frac{\text{model weights}}{\text{HBM bandwidth}} \quad \text{(per step, regardless of tokens generated)}

The insight: If we could verify $K$ candidate tokens in one forward pass (similar to prefill), we’d get $K$ tokens for roughly the cost of one. The model weights are loaded once, but do useful work for $K$ positions.

2. The Draft-Verify Loop

Speculative Decoding Round

Each speculative decoding round:

1. DRAFT: Fast model generates γ candidate tokens autoregressively
   y₁, y₂, ..., yγ  (each conditioned on history + previous candidates)

2. VERIFY: Target model processes all γ candidates in ONE forward pass
   Computes p₁(·), p₂(·), ..., pγ(·), p_{γ+1}(·)
   (using causal attention — each position sees only prior tokens)

3. ACCEPT/REJECT: Check candidates left-to-right
   Accept y₁ if it passes → check y₂ → ... → stop at first rejection

4. COMMIT: Submit accepted prefix + one corrected token
   If all γ accepted → also sample from p_{γ+1} → submit γ+1 tokens
   If rejected at position k → submit y₁..y_{k-1} + resample from pₖ → k tokens

Why the target can verify in parallel: The candidates form a known sequence. Like prefill, the target computes all positions simultaneously via causal attention — position $i$ only sees the history and candidates $y_1..y_{i-1}$ , never peeking at future candidates.

3. The Acceptance Rule

Greedy Decoding (temperature = 0)

Simple: accept candidate $y_i$ if it equals the target’s argmax at that position:

\text{Accept } y_i \iff y_i = \arg\max_x \; p_i(x)

Stop at the first mismatch; replace with the target’s choice.

Random Sampling (temperature > 0)

The standard speculative sampling rule — accept with probability proportional to how well the draft matches the target:

a_i(y_i) = \min\left(1, \frac{p_i(y_i)}{q_i(y_i)}\right)

Draw $u \sim \text{Uniform}(0, 1)$ . Accept if $u < a_i(y_i)$ .

If $p_i(y_i) \geq q_i(y_i)$ : target likes this token at least as much as draft → always accept
If $p_i(y_i) < q_i(y_i)$ : draft overestimates → accept with probability $p_i/q_i$

The Rejection Resample (Critical for Correctness)

When a candidate is rejected, you cannot simply sample from $p_i$ . The correct resample distribution compensates for the probability mass already “consumed” by the acceptance path:

r_i(x) = \frac{[p_i(x) - q_i(x)]_+}{\sum_z [p_i(z) - q_i(z)]_+}, \qquad [v]_+ = \max(v, 0)

Key insight: The acceptance path contributes tokens with probability $\min(p, q)$ . The rejection path must contribute the remaining probability mass $[p - q]_+$ to make the overall distribution exactly $p$ . Skipping this correction — e.g., just sampling from $p$ on rejection — subtly changes the output distribution.

4. Why This Is Mathematically Lossless

For any token $x$ at position $i$ , the probability of outputting $x$ is:

\Pr(\text{output } x) = \underbrace{\Pr(\text{accept } x)}_{\min(p_i(x), q_i(x))} + \underbrace{\Pr(\text{reject, resample } x)}_{[p_i(x) - q_i(x)]_+} = p_i(x)

The two paths sum to exactly $p_i(x)$ — the target model’s distribution. The output distribution is identical to running the target model alone. No quality degradation, no approximation.

This guarantee holds per-token. For sequences, once a token is accepted, the subsequent positions are conditioned on it — the chain of correct single-position distributions produces correct sequence distributions.

5. KV Cache Management

A subtle but important detail: draft tokens are candidates, not committed history.

Before round: KV cache has committed tokens [t₁, t₂, ..., tₙ]

Draft generates: [c₁, c₂, c₃, c₄]
  Draft model has its own KV cache (or shares with target)

Verify: target processes [c₁, c₂, c₃, c₄] with causal attention
  Target KV cache temporarily has [t₁..tₙ, c₁, c₂, c₃, c₄]

Accept: c₁, c₂ accepted, c₃ rejected → resample c₃'
  Keep KV for [t₁..tₙ, c₁, c₂, c₃']
  Discard KV for [c₃, c₄] from target cache

After round: KV cache = [t₁..tₙ, c₁, c₂, c₃']

The engine must roll back KV cache entries for rejected tokens. This is straightforward with PagedAttention — just don’t advance the sequence length past the accepted prefix.

For draft strategies and how to choose between them, see Draft Strategies. For speedup analysis, see Acceptance Rate & Speedup Bounds.

Self-Check

Explain why the target can verify γ candidates in one forward pass (causal attention, like prefill)
Write the acceptance probability formula for random sampling
Explain why rejection resampling from $[p-q]_+$ is necessary (not just from $p$ )
Prove that the output distribution equals the target’s: $\min(p,q) + [p-q]_+ = p$
Describe KV cache management: what happens to rejected candidates’ KV entries
Explain the difference between greedy and sampling acceptance rules