Speculative Decoding, Derived: Draft Models, N-grams, Medusa and EAGLE

Generating one token with a large model reads every weight once (Small and Specialized Models): at batch 1 the GPU spends a decode step waiting on memory, its arithmetic units mostly idle. Feeding the model several positions at once costs almost nothing extra, as long as they fit in the time the weights take to arrive. Speculative decoding uses that slack: a cheap guesser proposes the next few tokens, and the large model checks all of them in one step, keeping as many as it agrees with. Done right, the output is exactly what the large model alone would have produced, in distribution, only faster.

Table of contents

Why verification is nearly free

One decode step of an 8B model reads 16 GB of weights; at 3.35 TB/s that is 4.8 ms, while the arithmetic for one token, about 16 GFLOP at 989 TFLOPS, takes about 16 µs. Running the model on $k + 1$ positions instead of 1 adds $k$ tokens of arithmetic and a little KV-cache reading to a step whose time was set by the weights. The positions go through together, as in prefill: the causal mask lets each one see only the tokens before it, so one forward pass gives the target’s distribution $p$ at every drafted position, each conditioned on the drafted tokens before it. Until $k$ is large, or the batch already fills the compute (for a BF16 model on this GPU, from a batch of about 295 sequences, as Quantization from Scratch works out), the step takes about as long. So if a guess for the next $k$ tokens is often right, the target model can confirm several tokens for the price of one.

The acceptance rule, and why it is exact

The guesser, a draft model, proposes token $x$ from its distribution $q$; the target’s distribution at the same position is $p$. Accept $x$ with probability $\min(1, p(x)/q(x))$ (the draft only proposes tokens with $q(x) > 0$, so the ratio is defined). If it is rejected, sample instead from the residual $\max(0, p - q)$, renormalized, and stop: later drafted tokens were conditioned on a rejected one. Leviathan et al. (2023) and Chen et al. (2023) showed the result is distributed exactly as $p$.

The proof is two lines. The probability of outputting $x$ is the chance it is drafted and accepted, plus the chance of a rejection followed by $x$ from the residual:

The first term is $\min(p(x), q(x))$. In the second, $1 - \sum_y \min(p, q) = \sum_y \max(0, p - q)$, since both sides measure how much of $p$ lies above $q$, so the fraction cancels to $\max(0, p(x) - q(x))$. And $\min(p, q) + \max(0, p - q) = p$.

That is one position. A step chains them: the first drafted token is judged against $p$ given the text so far, so the first output token is distributed exactly as $p$; if it was accepted, the second drafted token is judged against $p$ given the text plus that token, and so on. At the first rejection the step outputs the residual sample and stops, and if all $k$ are accepted the target’s own distribution at position $k + 1$, already computed, gives one more. Each output token is therefore an exact sample from $p$ given everything before it, which by the chain rule makes the whole sequence an exact sample from the target.

Two practical conditions. Whatever sampling settings are in use (temperature, top-$p$, top-$k$) must be applied to both $p$ and $q$ before the rule, since the guarantee is about the distributions actually compared. And with greedy decoding the rule reduces to “accept if the draft’s token is the target’s top token”. Checked by sampling, with a draft that is deliberately bad:

import numpy as np

# 1. The acceptance rule makes the output exactly the target's distribution,
#    whatever the draft. Target p and draft q over 6 tokens: sample from q,
#    accept with probability min(1, p/q), otherwise sample from the residual
#    max(0, p - q), renormalized. Check by sampling a million times.
rng = np.random.default_rng(0)
p = np.array([0.40, 0.25, 0.15, 0.10, 0.07, 0.03])
q = np.array([0.10, 0.10, 0.30, 0.30, 0.10, 0.10])           # a bad draft, on purpose
n = 1_000_000
x = rng.choice(6, n, p=q)
accept = rng.random(n) < np.minimum(1, p[x] / q[x])
resid = np.maximum(p - q, 0); resid /= resid.sum()
x = np.where(accept, x, rng.choice(6, n, p=resid))
print("target p:          ", np.round(p, 3))
print("output frequencies:", np.round(np.bincount(x, minlength=6) / n, 3))
print(f"acceptance rate {accept.mean():.3f}; theory: sum of min(p, q) = {np.minimum(p, q).sum():.3f}")

# 2. Tokens per verification step. If each drafted token is accepted with
#    probability alpha, independently, a step with k drafts yields
#    (1 - alpha^(k+1)) / (1 - alpha) tokens on average: the accepted run,
#    plus the one token the target always contributes (a correction, or a
#    bonus token after k acceptances). Check against simulation.
def simulate(alpha, k, steps=200_000):
    acc = rng.random((steps, k)) < alpha
    run = np.where(acc.all(1), k, acc.argmin(1))              # accepted before the first rejection
    return (run + 1).mean()
print("\nalpha  k   formula  simulated")
for alpha in (0.6, 0.8, 0.9):
    for k in (2, 4, 8):
        f = (1 - alpha ** (k + 1)) / (1 - alpha)
        print(f"{alpha:5.1f} {k:2d} {f:9.2f} {simulate(alpha, k):10.2f}")

# 3. Speedup, counting the draft's cost: c = one draft step's time relative
#    to one target step. A step costs k draft steps plus one target step that
#    verifies all k (decode is memory-bound, so verifying k+1 positions costs
#    about one step).
print("\nspeedup over plain decoding, by draft cost c (alpha = 0.8)")
print("  k " + "".join(f"  c={c:<5g}" for c in (0.0, 0.05, 0.1, 0.3)))
for k in (1, 2, 4, 8, 16):
    f = (1 - 0.8 ** (k + 1)) / (1 - 0.8)
    print(f"{k:3d} " + "".join(f"{f / (k * c + 1):8.2f}" for c in (0.0, 0.05, 0.1, 0.3)))

Full script: spec_math.py

target p:           [0.4  0.25 0.15 0.1  0.07 0.03]
output frequencies: [0.4  0.25 0.15 0.1  0.07 0.03]
acceptance rate 0.550; theory: sum of min(p, q) = 0.550

alpha  k   formula  simulated
  0.6  2      1.96       1.96
  0.6  4      2.31       2.31
  0.6  8      2.47       2.48
  0.8  2      2.44       2.44
  0.8  4      3.36       3.36
  0.8  8      4.33       4.32
  0.9  2      2.71       2.71
  0.9  4      4.10       4.10
  0.9  8      6.13       6.13

speedup over plain decoding, by draft cost c (alpha = 0.8)
  k   c=0      c=0.05   c=0.1    c=0.3  
  1     1.80    1.71    1.64    1.38
  2     2.44    2.22    2.03    1.52
  4     3.36    2.80    2.40    1.53
  8     4.33    3.09    2.40    1.27
 16     4.89    2.72    1.88    0.84

How many tokens a step yields

If each drafted token is accepted with probability $\alpha$, the number accepted before the first rejection is geometric, capped at $k$; the target always adds one more token, a correction after a rejection or a bonus token after $k$ acceptances, since it computed that position anyway. The expected tokens per step:

At $\alpha = 0.8$ and $k = 4$, 3.36 tokens per target step; the second table above checks the formula against simulation. The draft isn’t free: if a draft step costs $c$ of a target step, a speculative step costs $kc + 1$, and the speedup is the tokens per step divided by that. The third table shows the trade: with $c = 0.05$, drafting 8 tokens gives 3.1 times; with $c = 0.3$ the gain peaks at about 1.5 times for 2 to 4 drafted tokens, 8 is slower than 4, and 16 drafts lose to plain decoding. The rule of thumb: the cheaper the draft and the higher $\alpha$, the longer the draft should be. Try it:

When a guess is rejected, the cache entries computed for the tokens after it are discarded: the KV cache (The KV Cache) is truncated back to the last accepted token.

Where the guesses come from

• A draft model: a small model with the same tokenizer, run autoregressively for $k$ steps. The classic setup; its acceptance depends on how well the small model imitates the large one.
• Prompt lookup (Saxena, 2023): no model at all. Find the last few generated tokens earlier in the prompt or the output, and propose what followed them there. Free, and very good when the answer copies from the input: summaries, edits, code changes, retrieval-grounded answers.
• Medusa (Cai et al., 2024): extra heads on the target model itself (four or five by default), each predicting the token 2, 3, 4, … positions ahead from the last hidden state. Their top candidates form a tree of possible continuations, and tree attention, a mask letting each candidate attend only to its own ancestors, verifies the whole tree in one step. Two caveats against this post’s guarantee: Medusa’s default rule for sampling, typical acceptance, accepts any candidate the target finds plausible enough, which is faster but no longer exactly the target’s distribution; and Medusa-2 fine-tunes the target along with the heads, which changes the target. Verifying a tree exactly under sampling needs a multi-candidate version of the rejection rule (as in SpecInfer).
• EAGLE (Li et al., 2024): a one-layer autoregressive draft model that works on the target’s features, its second-to-top-layer hidden states, rather than only its tokens. Its input at each step is the feature sequence together with the token sequence advanced by one step, which tells the draft which token was actually sampled and removes much of the uncertainty in predicting the next feature. EAGLE-2 grows the draft tree dynamically, using the draft’s confidence as a stand-in for the chance of acceptance. EAGLE-3 (2025) drops feature prediction, drafts tokens directly from a fusion of low, middle and high-layer features, and trains on its own drafted sequences (“training-time test”).
• Multi-token prediction (MTP): a model trained to predict more than one next token, like DeepSeek-V3 and V4 (Anatomy of a Frontier Model), can use those extra predictions as its own draft at inference.

vLLM, SGLang and TensorRT-LLM all ship several of these: draft models, n-gram lookup, EAGLE-style heads, and MTP for models trained with it.

Measured acceptance

How often guesses are accepted, on real models: Qwen2.5-1.5B-Instruct as the target, the 0.5B base model as the draft (the instruction-tuned 0.5B would be the natural partner; the base model shares its tokenizer), and prompt lookup, on two kinds of task:

@torch.no_grad()
def measure(prompts):
    greedy, sampled, lookup, n = 0, 0.0, 0, 0
    for prompt in prompts:
        ids = tok.apply_chat_template([{"role": "user", "content": prompt}], add_generation_prompt=True,
                                      return_tensors="pt", return_dict=True)["input_ids"].to(DEV)
        out = target.generate(ids, max_new_tokens=120, do_sample=False, temperature=None, top_p=None, top_k=None,
                              repetition_penalty=1.0)
        full, start = out, ids.shape[1]
        p = target(full).logits[0, start - 1:-1].float().softmax(-1)
        q = draft(full).logits[0, start - 1:-1].float().softmax(-1)
        nxt = full[0, start:]
        greedy += (q.argmax(-1) == nxt).sum().item()
        sampled += torch.minimum(p, q).sum(-1).sum().item()
        seq = full[0].tolist()
        for i in range(start, len(seq)):
            a, b = seq[i - 2], seq[i - 1]
            guess = next((seq[j + 2] for j in range(i - 3, -1, -1) if seq[j] == a and seq[j + 1] == b), None)
            lookup += guess == seq[i]
        n += len(nxt)
    return greedy / n, sampled / n, lookup / n, n

Full script: accept.py

measure runs each prompt through the target once, greedily, then scores every position of the answer three ways. The rest of accept.py loads the two models at pinned revisions on the CPU (DEV), and builds the prompts: six paragraphs from blog_val.txt to rewrite, and six open questions. On a GPU the greedy answers, and so every count below, can change.

rewrite a paragraph  (666 tokens): draft model, greedy 79%, sampled 75%; prompt lookup 42%
open question        (720 tokens): draft model, greedy 72%, sampled 70%; prompt lookup 6%

• A small model guesses most tokens. Even a base model, not instruction-tuned, matches the target’s greedy choice for 79% of the rewrite’s tokens and 72% of the open answers’. The sampled column is $\sum \min(p, q)$, Leviathan et al.’s $\alpha$ for sampling at temperature 1, but measured here on the target’s greedy text.
• Prompt lookup depends entirely on the task. When the answer rewrites a paragraph from the prompt, the token that followed the last two tokens earlier in the text is right 42% of the time, for free. For open questions, where nothing earlier is copied, 6%.

Those are per-position rates on one kind of text. Three things in them could mislead, so a second script measures each directly, on the same prompts (six per task, about 700 tokens each; the line with the two vocabulary sizes, the per-prompt lines and the two-token-only lookup line per task are left out of the output below). The two scripts, accept.py and spec_steps.py, download about 4 GB of models, then take about 10 minutes in all on an Apple M4 laptop:

def spec_steps_greedy(match, k):
    # match[i] = draft argmax == target token at answer position i
    i, steps, n = 0, 0, len(match)
    while i < n:
        r = 0
        while r < k and i + r < n and match[i + r]:
            r += 1
        i += r + 1
        steps += 1
    return n / steps


def lookup_propose(seq, i, max_ng=3, num=10):
    for ng in range(max_ng, 0, -1):
        if i - ng < 0:
            continue
        pat = seq[i - ng:i]
        for j in range(i - ng - 1, -1, -1):  # most recent earlier occurrence
            if seq[j:j + ng] == pat:
                return seq[j + ng:min(j + ng + num, i)]  # continuation from known prefix
    return []


def lookup_steps(seq, start, max_ng, num):
    i, steps, proposed_steps, hits_first = start, 0, 0, 0
    while i < len(seq):
        prop = lookup_propose(seq, i, max_ng, num)
        r = 0
        while r < len(prop) and i + r < len(seq) and prop[r] == seq[i + r]:
            r += 1
        if prop:
            proposed_steps += 1
            hits_first += r > 0
        i += r + 1
        steps += 1
    return (len(seq) - start) / steps, proposed_steps / steps, hits_first / max(proposed_steps, 1)

Full script: spec_steps.py

spec_steps_greedy replays greedy speculation from the per-position matches; lookup_propose and lookup_steps replay prompt lookup as deployed. The rest of spec_steps.py generates the answers as accept.py does, adds a sampled answer per prompt, and prints the summary per task.

== rewrite: n=666; greedy agree 0.787 (per-prompt min 0.58 max 0.99)
   smin on greedy text 0.754; smin on T=1 sampled text 0.715
   lookup 1-token 2-gram 0.422
   greedy spec tokens/step k=4: actual 3.27, iid formula 3.28; k=8 actual 4.32, formula 4.15
   prompt lookup pl (tokens/step, frac steps with a proposal, frac proposals with >=1 accepted): (2.937, 0.715, 0.456)
== open: n=720; greedy agree 0.718 (per-prompt min 0.68 max 0.76)
   smin on greedy text 0.702; smin on T=1 sampled text 0.722
   lookup 1-token 2-gram 0.060
   greedy spec tokens/step k=4: actual 2.82, iid formula 2.87; k=8 actual 3.34, formula 3.37
   prompt lookup pl (tokens/step, frac steps with a proposal, frac proposals with >=1 accepted): (1.125, 0.403, 0.179)

• Tokens per step. For greedy decoding, speculation can be simulated exactly from the target’s own text. At $k = 4$ it yields 3.27 tokens per step on the rewrite and 2.82 on open questions, within 0.05 of the independent-$\alpha$ formula. At $k = 8$, the rewrite does better than the formula (4.32 against 4.15): acceptances cluster, because easy runs of tokens are easy for both models, and long drafts profit from the long runs. A rerun on an NVIDIA RTX 3090 (its saved outputs) generated slightly different text, and there the rewrite fell short of the formula at $k = 4$ (3.28 against 3.37) and beat it at $k = 8$ (4.40 against 4.35). So the formula is within about 0.1 of the simulation at $k = 4$ and within 0.2 at $k = 8$, either way.
• Sampled text. On text the target sampled at temperature 1, the acceptance is 71.5% for the rewrite and 72.2% for open questions, against 75% and 70% on its greedy text. On the rerun the rewrite’s sampled acceptance was 65.3% against 75.4%: sampled text is not the same thing.
• Real prompt lookup. As deployed, prompt lookup proposes up to ten tokens from the longest earlier match. On the rewrite it then yields 2.9 tokens per step (2.5 on the rerun), far more than the single-token 42% suggests, because copied text comes in long runs. On open questions, 1.1: almost nothing.

What would this pair actually gain? Not 3 times. The 0.5B draft reads about a third of the bytes the 1.5B target does, so in the memory-bound model each draft step costs $c \approx 0.32$ of a target step, and with $\alpha \approx 0.75$ the speedup peaks at about 1.4 times at $k = 2$. A draft this close in size to its target is a poor draft; the 3× regime needs a draft ten or more times cheaper, or prompt lookup on text that copies. Prompt lookup costs almost nothing to propose, so its tokens per step is close to its speedup: about 2.5 to 2.9 times on the rewrite, 1.1 on open questions. All of these are modeled from measured acceptance; none is a wall-clock measurement. Production servers offer several kinds of guesser, and the right one depends on the traffic.

When it doesn’t help

• A draft too close to the target. The larger the draft relative to the target, the more of the gain goes to paying for it: at a third of the target’s size, the measured pair above gains only about 1.4 times.
• Large batches. Verification is free only while the step is memory-bound. With many sequences in a batch, the step is already compute-bound, and every extra drafted position costs real arithmetic. Speculation buys latency for each request with extra total compute, so at high load it can lower throughput; serving systems turn it down or off as the batch grows. Batching also makes acceptance ragged: in one step, one sequence may accept four tokens and its neighbor none, and the engine has to handle sequences advancing by different amounts.
• Low acceptance. Creative, high-temperature, or out-of-domain text makes guesses wrong, and a step that accepts nothing has spent the draft’s time for one token.
• An expensive draft. As the table shows, the draft’s cost caps the gain and turns long drafts into losses.

Where this leads

• Running LLMs on a Laptop runs models on a laptop, where batch 1 is the normal case and speculation pays most.
• Watermarking LLM Text returns to the distribution-preserving property, for watermarking.

Takeaways

• Decoding is memory-bound, so verifying $k$ guessed tokens in one target step costs about as much as generating one; speculative decoding turns that slack into tokens.
• Accepting a draft token with probability $\min(1, p/q)$ and resampling from the residual on rejection reproduces the target’s distribution exactly, whatever the draft; a million samples from a bad draft matched the target to three decimals.
• A step yields $(1 - \alpha^{k+1})/(1 - \alpha)$ tokens on average; the draft’s cost caps the speedup, and long drafts from a costly draft model lose to plain decoding.
• Measured: a 0.5B base model matched a 1.5B instruct model’s tokens 72 to 80% of the time, giving 2.8 to 3.3 tokens per step at $k = 4$, but as a draft only a third the target’s size it would speed decoding by about 1.4 times. Prompt lookup gave 2.5 to 2.9 tokens per step when rewriting given text and 1.1 on open questions.
• Speculation helps at small batches and high acceptance, and fades as batches make each step compute-bound.

References

Start with Leviathan et al. for the rule and its proof, then EAGLE for the guessers production servers use.

• Leviathan, Kalman and Matias, Fast Inference from Transformers via Speculative Decoding (ICML, 2023): the acceptance rule, its proof and the expected tokens per step.
• Chen, Borgeaud, Irving, Lespiau, Sifre and Jumper, Accelerating Large Language Model Decoding with Speculative Sampling (2023): the same rule, found independently, with its proof of exactness.
• Saxena, Prompt Lookup Decoding (2023): prompt lookup, the model-free guesser.
• Cai et al., Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads (ICML, 2024): Medusa heads, tree verification and typical acceptance.
• Miao et al., SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification (ASPLOS, 2024): verifying a tree of candidates exactly under sampling.
• Li, Wei, Zhang and Zhang, EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty (ICML, 2024); EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees (EMNLP, 2024); EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test (2025): drafting from the target’s features, dynamic draft trees, and training-time test.