Speculative decoding

Summary

A small “draft” model proposes K candidate tokens cheaply; a single parallel forward pass of the large target model verifies them using a rejection-sampling rule that provably preserves the target model’s output distribution.

Low-batch autoregressive decoding can be memory-bound: reading weights for the next token leaves arithmetic capacity underused. That is a workload condition, not a rule for every serving configuration. Large batches, long contexts, and KV-cache traffic can change the bottleneck.

Speculation batches target verification of several proposed positions into one pass. That pass is not necessarily as cheap as ordinary one-token decoding, and rejected drafts still cost work. The exact acceptance/correction scheme preserves the target distribution; latency improves only when accepted output amortizes the extra work.

The original Leviathan et al. study reported 2-3x acceleration for T5-XXL against its T5X baseline. That is a result for the paper’s configuration, not a speed guarantee for another model, accelerator, or batch size.

Learning objective · one cycle with K = 5

The first rejected draft invalidates its suffix and requires a corrected replacement

Derivation

the rejected A is replaced by C under the illustrated residual distribution q. Later drafts followed A, so they cannot survive that change. Accepted mass plus the rejection correction recovers the target law; the picture does not predict speedup.

Check: Why can draft positions four and five not be committed after position three is replaced? Which corrected distribution supplies that replacement?

Read it this way: After accepting A and rejecting draft B, later draft C cannot survive unchanged. Draw the corrected replacement and restart from the valid prefix.
Can draft C remain committed unchanged after its preceding draft B is rejected?

The mechanism

Setup: large target model M (the one whose distribution we want to sample from), small draft model m (cheap; e.g., a 1B distilled version of a 70B M).

Per cycle:

Draft. Run m for $K$ autoregressive steps, retaining each proposal and its conditional draft distribution $D$ .
Verify. Evaluate M on the proposed continuation in parallel, obtaining the target conditionals $P$ for the proposals and the possible bonus position.
Accept/reject. At each proposed position, accept token $x$ with probability $min (1, P (x) / D (x))$ . On the first rejection, sample from the normalized positive part of $P - D$ , discard the remaining proposals, and restart from the corrected prefix.
Bonus token. If every proposal is accepted, sample one additional target token. The cycle emits accepted proposals plus exactly one replacement-or-bonus target token, at the cost of drafting and verification.

Why it’s lossless

The accept/reject rule is a special case of rejection sampling chosen specifically so that the marginal distribution of the output token at each position is exactly pḘ. The proof is one page of careful algebra; the upshot is the output stream is statistically indistinguishable from sampling from M directly.

This is a distributional guarantee in exact arithmetic under the stated conditional probabilities and correction rule, not a speed guarantee. Apply the intended sampling transformations consistently, maintain the correct accepted-prefix KV state, and distinguish mathematical exactness from bit-for-bit reproducibility. An implementation error is not excused as a harmless property of speculation.

Speedup analysis

For an illustrative model, assume independent acceptance with constant probability $α$ at every position. Expected emitted tokens, including the replacement or bonus, are

E [N] = j = 0 \sum K α^{j} = \frac{1 - α ^{K + 1}}{1 - α}, 0 \leq α < 1.

For $α = 1$ , the limit is $K + 1$ . Do not add a second bonus to this count. Real acceptance can depend on position and prefix, so measure accepted-prefix lengths for the serving workload.

Normalize ordinary target-token latency to one. Let $d$ be a draft-step cost and $v_{K}$ the measured verification-pass cost in those units. Under this serial cost model, the speed ratio is $E [N] / (K d + v_{K})$ . Improvement requires $E [N] > K d + v_{K}$ ; batch scheduling and overlap can require a richer model.

Predict before revealing: use $K = 4$ , $d = 0.1$ , $v_{K} = 1$ , and disjoint draft/target support, so the first proposal always rejects. Does exact correction still make the cycle faster?

Separate output correctness from cost

No. Each cycle emits one corrected token for cost 1.4, giving speed ratio $1/1.4 \approx 0.714$ . The target sampling law remains correct, but this toy configuration is slower. The verifier cost of one is an optimistic illustrative assumption, not a benchmark measurement.

Tune $K$ against measured draft, verification, acceptance, memory, and batching costs rather than relying on a universal block length.

Variants

Self-speculation / Medusa. Internal prediction heads can propose continuations without a separate draft model. Training and acceptance schemes vary; preserving measured generation quality is not the same claim as preserving the original sampling distribution.
EAGLE. Predicts target-model features to produce proposals. Its benefit depends on proposal quality and implementation costs, not a universal ordering over other methods.
Tree speculation. Verifies branching candidates together. A valid acceptance scheme must choose the continuation; simply selecting the longest plausible branch does not establish sampling exactness.
Lookahead decoding. Uses parallel lookahead/n-gram proposals. State the decoding rule and its guarantee rather than assuming every variant implements the rejection sampler above.

Compare a named implementation on a dated, matched model/hardware/workload configuration before ranking variants by speed or engineering cost.

What an interviewer expects you to say

If asked about speculative decoding:

State the workload and why low-batch decoding may be memory-bound.
Explain proposal, parallel verification, accepted-prefix retention, and first-rejection correction.
State the exact sampler’s distributional guarantee and its assumptions.
Derive a break-even condition from acceptance and measured costs instead of promising a speedup multiple.
Compare variants by their proposal mechanism, acceptance guarantee, memory use, and scheduling overhead.

Common confusions

“Every speculative method is exact.” The rejection/correction sampler above preserves the target law in exact arithmetic; a different acceptance heuristic needs its own analysis.
“It only helps for greedy decoding.” No, it works for sampling too, the rejection rule is defined in terms of probabilities precisely because sampling is the general case.
“The draft must be fine-tuned for correctness.” Matching the target helps acceptance, but the stated correction rule, not fine-tuning, establishes the target law.
“Any small model is plug-compatible.” The algorithm above assumes a shared token vocabulary. Cross-tokenizer methods require explicit alignment and their own correctness conditions.
“It must save FLOPs.” Drafting and rejected proposals can add computation. Lower latency, when achieved, does not imply less arithmetic.

Why interviewers care

This question tests whether you understand:

When weight bandwidth, arithmetic, or KV-cache traffic limits decoding.
The difference between batched and sequential workloads on GPU.
Lossless vs. lossy optimizations (a common confusion).
That you’ve kept up with serving developments since 2023.

Explain how rejected-prefix KV state is discarded and how batching changes the cost comparison. Those concrete mechanisms are stronger evidence of understanding than quoting a speedup or a method name.

Reading list

Fast Inference from Transformers via Speculative Decoding (Leviathan et al., 2023)
Accelerating Large Language Model Decoding with Speculative Sampling (Chen et al., 2023)
Medusa: Simple LLM Inference Acceleration with Multiple Decoding Heads (Cai et al., 2024)
EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty (Li et al., 2024)