Speculative Decoding — Draft, Verify, Repeat

Speculative decoding is a way to generate tokens from a large model faster: a small draft model proposes several tokens ahead, and the large model, called the verifier, checks all of them in a single forward pass.

The arithmetic: a 70B LLM sampling one token takes ~30 ms on an H100, and a 3B draft model takes ~3 ms. If the 3B drafts 5 tokens ahead and the 70B runs once to verify all 5, the total is 5×3 + 30 = 45 ms for up to 5 accepted tokens, versus 5×30 = 150 ms for straight-line generation. That is the whole pitch: spend a little extra GPU memory on the draft model and get 2–4× lower decode latency.

The trick has to preserve the distribution. Speculative sampling, introduced by Leviathan et al. (2023) and by Chen et al. concurrently, guarantees that the output sequence is identically distributed to what the big model would have produced on its own. No quality tradeoff. Just faster.

Four families of draft-verifier pairs dominate 2026 inference:

1. Vanilla speculative (Leviathan 2023). A separate draft model (e.g., Llama 3 1B) plus a verifier (e.g., Llama 3 70B).
2. Medusa (Cai 2024). Multiple decoding heads on the verifier predict positions t+1..t+k in parallel. No separate draft model.
3. EAGLE family (Li 2024, 2025). A lightweight draft that reuses the verifier's hidden states. Its acceptance rate is higher than vanilla's, and a 3–4× speedup is typical.
4. Lookahead decoding (Fu 2024). Jacobi iteration with no draft model at all. This is self-speculation: niche, but dependency-free.

Production inference stacks ship speculative decoding by default in 2026. vLLM, TensorRT-LLM, SGLang, and llama.cpp all support at least vanilla and EAGLE-2.

The core algorithm

Given a verifier M_q and a cheaper draft M_p:

1. Let x_1..x_k be the prefix already decoded.
2. Draft: use M_p to autoregressively propose d_{k+1}, d_{k+2}, ..., d_{k+N} with draft probabilities p_1..p_N.
3. Verify in parallel: run M_q once on x_1..x_k, d_{k+1}, ..., d_{k+N}, getting verifier probabilities q_1..q_{N+1} for positions k+1..k+N+1.
4. Accept or reject each draft token left to right: for each i, accept with probability min(1, q_i(d_i) / p_i(d_i)).
5. On the first rejection at position j: sample t_j from the "residual" distribution (q_j - p_j)_+, normalized. All drafts after j are discarded.
6. If all N are accepted: sample one extra token t_{N+1} from q_{N+1} (the free bonus token).

The residual distribution is the mathematical insight that keeps the output distributed exactly as if M_q had sampled from scratch.

What determines speedup

Let α be the expected acceptance rate per draft token and c the draft-to-verifier cost ratio. Per step, naive generation makes 1 big-model call per token. Speculative decoding makes 1 big-model call per (1 - α^{N+1}) / (1 - α) ≈ 1/(1-α) tokens when α is high.

A rule of thumb at α = 0.75 and N = 5: 3× fewer big-model calls. The draft costs 5× less per call, and total wall-clock drops ~2.5×.

α depends on:

• How well the draft approximates the verifier. Same family or same training data raises α significantly.
• Decoding strategy. A greedy draft against a greedy verifier gives high α. Temperature sampling is harder to match, and acceptance drops.
• Task type. Code and structured output accept more because they are predictable. Free-form creative writing accepts less.

Medusa: drafts without a draft model

Medusa replaces the draft model with extra output heads on the verifier. At position t:

shared trunk → hidden h_t
    ├── head_0: predict token at t+1  (standard LM head)
    ├── head_1: predict token at t+2
    ├── head_2: predict token at t+3
    ├── head_3: predict token at t+4

Each head outputs its own logits. At inference you sample from each head to get a candidate sequence, then verify with one forward pass using a tree-attention scheme that considers all candidate continuations at once.

The upside is that there is no second model to host. The cost is extra trainable parameters and a supervised fine-tuning stage (~1B tokens), and the acceptance rate runs a bit lower than vanilla speculative decoding with a good draft.

EAGLE: a better draft from reused hidden states

EAGLE-1/2/3 (Li et al., 2024–2025) makes the draft model a tiny transformer (typically 1 layer) that ingests the verifier's last-layer hidden states. Because the draft sees the verifier's feature representation, its predictions correlate strongly with the verifier's output distribution. Acceptance rates climb from ~0.6 (vanilla) to 0.85+.

EAGLE-3 (2025) added tree search over candidate continuations. vLLM and SGLang ship EAGLE-2/3 as the default spec pathway for Llama 3/4 and Qwen 3.

The KV cache dance

Verification feeds N draft tokens into the verifier in one forward pass, which extends the verifier's KV cache by N entries. If some drafts are rejected, you must roll the cache back to the accepted prefix length.

Production implementations (vLLM's --speculative-model, TensorRT-LLM's LookaheadDecoder) handle this with scratch KV buffers: write first, commit on acceptance. The idea is not conceptually hard, but the bookkeeping is fiddly.

See code/main.py. It implements the core speculative-sampling algorithm (rejection step plus residual distribution) with:

• A "big model" that is a deterministic softmax over a hand-coded distribution, so the acceptance math can be checked analytically.
• A "draft model" that is a perturbation of the big model.
• An acceptance and rejection loop that produces the same marginal distribution as direct sampling.

The snippets below are illustrative. In main.py the accept test is inline, and the functions are residual(q, p), spec_step_one_token(q, p, rng) and spec_step_n(q, p, N, rng). They take fixed q and p probability vectors per call, so there is no prefix, no model callables, and no KV cache.

Step 1: the rejection step

def accept_or_reject(q_prob, p_prob, draft_token, u):
    ratio = q_prob / p_prob if p_prob > 0 else float("inf")
    return u < min(1.0, ratio)

u is a uniform random number. q_prob is the verifier's probability for the drafted token and p_prob is the draft model's. The Leviathan theorem says this Bernoulli decision, followed by sampling from the residual on rejection, preserves the verifier's distribution exactly.

Step 2: residual distribution

def residual_dist(q, p):
    raw = [max(0.0, qi - pi) for qi, pi in zip(q, p)]
    s = sum(raw)
    return [r / s for r in raw]

Subtract p from q element-wise, clamp negative values to zero, and renormalize. On a rejection, sample from this. main.py's residual(q, p) returns list(q) when the clamped sum is 0 (which only happens when q == p), where the snippet above would divide by zero.

Step 3: one speculative step

def spec_step(prefix, q_model, p_model, N, rng):
    drafts = []
    p_probs = []
    ctx = list(prefix)
    for _ in range(N):
        p_dist = p_model(ctx)
        d = sample(p_dist, rng)
        drafts.append(d)
        p_probs.append(p_dist[d])
        ctx.append(d)
 
    q_dists = [q_model(prefix + drafts[:i]) for i in range(N + 1)]
 
    for i, d in enumerate(drafts):
        u = rng.random()
        q_prob = q_dists[i][d]
        p_prob = p_probs[i]
        if u < min(1.0, q_prob / p_prob if p_prob > 0 else float("inf")):
            prefix = prefix + [d]
        else:
            res = residual_dist(q_dists[i], p_model(prefix))
            prefix = prefix + [sample(res, rng)]
            return prefix
    prefix = prefix + [sample(q_dists[N], rng)]
    return prefix

Five accepted → one bonus → six tokens produced in one verifier pass.

This snippet is a sketch of the full algorithm with model callables, not code from main.py; the file's spec_step_n(q, p, N, rng) runs the same accept loop on fixed vectors. One detail worth getting right: on rejection at position i, the p in the residual must be the draft distribution that produced the rejected draft, which is the draft's distribution at context prefix + drafts[:i]. Here that works because prefix has already been extended by each accepted draft by the time the rejection branch runs, but storing the draft distributions from the drafting loop and reusing p_dists[i] is clearer and harder to break.

Step 4: measure acceptance rate

main.py runs 5,000 one-token speculative steps at each of six draft-noise levels and prints a table of acceptance rate next to the KL divergence between verifier and draft distributions. It prints a table rather than a plot, so plot it yourself if you want the curve. The relationship comes out monotone: more KL, lower acceptance. It then prints expected tokens per verifier call for N of 1, 3, 5, 7 and 10 at five values of α, and its takeaway line (α = 0.85, N = 5 gives about 4.1 tokens per call) is a count of verifier calls. It measures no wall-clock time, so the rule of thumb in The Concept (α = 0.75, N = 5, about 3× fewer calls and ~2.5× wall-clock) is a figure to check on your own workload.

Step 5: verify distribution equivalence

The histogram of tokens produced by the speculative loop should match the histogram from sampling directly from the verifier. This is the Leviathan theorem in practice. main.py draws 50,000 tokens each way using spec_step_one_token (not the N-token path), computes a chi-square statistic, and prints PASS when it is under 30 on 7 degrees of freedom. It does not compute a p-value.

In production you launch a server with the speculative settings:

# vLLM with EAGLE
vllm serve meta-llama/Llama-3.1-70B-Instruct \
    --speculative-model /models/llama-3.1-eagle-70b \
    --speculative-draft-tensor-parallel-size 1 \
    --num-speculative-tokens 5
 
# vLLM with vanilla draft model
vllm serve meta-llama/Llama-3.1-70B-Instruct \
    --speculative-model meta-llama/Llama-3.2-1B-Instruct \
    --num-speculative-tokens 5

TensorRT-LLM has the fastest Medusa path as of mid-2026. faster-whisper wraps speculative decoding for Whisper-large with a small draft.

Picking a draft:

When NOT to spec-decode:

• Single-sequence generation of 1–5 tokens. Overhead dominates.
• Wildly creative or high-temperature sampling (α drops).
• Memory-constrained deployments (the draft model adds VRAM).

The skill in outputs/skill-spec-decode-picker.md picks a speculative decoding strategy (vanilla / Medusa / EAGLE / lookahead) and tuning parameters (N, draft temperature) for a new inference workload.

1. Easy. Run code/main.py. Confirm the speculative token distribution matches the verifier's direct-sample distribution on 50,000 tokens. main.py prints the chi-square statistic and PASS under 30; to test p > 0.05 yourself, compare the statistic against the 7-degree-of-freedom critical value of 14.07.
2. Medium. Plot speedup (tokens per big-model forward) as a function of N for α = 0.5, 0.7, 0.85. Identify the optimal N for each α. (Hint: expected tokens per verify call = (1 - α^{N+1}) / (1 - α).)
3. Hard. Implement a tiny Medusa: take the capstone GPT from Lesson 14, add 3 extra LM heads that predict positions t+2, t+3, t+4. Train on tinyshakespeare with a joint multi-head loss. Compare acceptance rates vs a vanilla draft made by truncating the same model.
4. Hard. Implement rollback: start with a 10-token prefix KV cache, feed 5 draft tokens, simulate a rejection at position 3. Verify your cache reads correctly match "prefix + first 2 accepted drafts" at the next iteration.

• Leviathan, Kalman, Matias (2023). Fast Inference from Transformers via Speculative Decoding: the core algorithm and the equivalence theorem.
• Chen et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling: concurrent introduction; clean Bernoulli-rejection proof.
• Cai et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads: Medusa paper; tree-attention verification.
• Li et al. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty: EAGLE-1; hidden-state-conditioned draft.
• Li et al. (2024). EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees: EAGLE-2; dynamic tree depth.
• Li et al. (2025). EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test: EAGLE-3.
• Fu et al. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding: lookahead, no-draft approach.
• vLLM docs: Speculative Decoding: canonical production reference with all four strategies wired up.
• SafeAILab / EAGLE reference implementation: the reference code for EAGLE-1/2/3.