Speculative Decoding Explained: Draft, Verify, Accept

A large language model writes one token per forward pass, and each pass waits for the one before it. Speculative decoding breaks that chain without changing what the model says: a small, fast draft model guesses several tokens ahead, and the large target model checks them all in a single pass. Good guesses turn one expensive pass into several tokens; bad ones cost a little time and nothing else, because the target always has the final word.

The problem it solves

Generating text is sequential: token 5 depends on token 4. For a single request, each step reads essentially every weight from memory to produce one token, and the arithmetic units mostly wait for those bytes. The useful consequence: scoring several positions in one pass reads the same weights once, so checking five tokens costs little more than generating one.

The bottleneck is the number of target passes. Speculative decoding spends cheap draft passes to save expensive ones.

The intuition

Each round has three steps:

• Draft. The small model proposes k tokens, one after another, which is cheap because it is small.
• Verify. The target model runs once over the prompt plus all k guesses. Because a transformer produces a prediction at every position, that single pass says what the target would have written after each prefix.
• Accept. Walk the guesses left to right and keep them while they agree. At the first disagreement, write the target's own token instead, which the same pass already computed, and throw away every guess after it: those were conditioned on a wrong token. If all k are accepted, the pass also yields one bonus token.

Every round produces at least one token, the same as normal decoding, and up to k + 1.

With greedy decoding "agree" means "the target's top token equals the guess", and the output is identical to greedy decoding with the target alone. With sampling, exact agreement would be too strict, so a guess x with draft probability q(x) and target probability p(x) is accepted with probability min(1, p(x) / q(x)). On rejection, the replacement is sampled from the leftover, the positive part of p - q, renormalised. That rule makes the accepted token distributed exactly as p: the draft changes the speed, never the text's distribution.

Watch it run

The animation opens on the problem: producing one token at a time is sequential, and each one has to wait for the one before it. But checking a sequence you already have is parallel, and that asymmetry is the whole trick. So a small, cheap model drafts four tokens ahead: "the kiln cooled slowly". The large model scores all four positions in a single forward pass. The first two match what it would have written itself, so they are kept. The third disagrees, and the target's own token, "held", is written in its place, free, from the same pass. Everything after the correction was conditioned on a wrong token, so it goes: three tokens for one pass. The last two frames are the tradeoff. Your speedup rides on the acceptance rate, and a weak drafter is rejected constantly, yielding one token per pass. And a drafter good enough to always be right is nearly as slow as the model it was meant to save, with both models held in memory.

The code

A toy model of the greedy version. Each "model" is a lookup table from prefix to next token, and the verification step scores all k + 1 positions at once, as one target pass would. It reproduces the animation's round:

def table(d):
    """A toy greedy model: the next token for each prefix, from a lookup table."""
    return lambda tokens: d.get(" ".join(tokens), "<end>")

target = table({"": "the", "the": "kiln", "the kiln": "held", "the kiln held": "its",
                "the kiln held its": "heat", "the kiln held its heat": "overnight"})
draft = table({"": "the", "the": "kiln", "the kiln": "cooled", "the kiln cooled": "slowly",
               "the kiln held": "its", "the kiln held its": "heat",
               "the kiln held its heat": "all", "the kiln held its heat all": "night"})

def speculative_greedy(target, draft, n_tokens, k=4, log=False):
    """Toy model: greedy draft-and-verify. Returns the tokens and the target passes used."""
    out, passes = [], 0
    while len(out) < n_tokens:
        guess = []
        for _ in range(k):                                     # cheap: k small-model steps
            guess.append(draft(out + guess))
        passes += 1                                            # expensive: ONE target pass
        wanted = [target(out + guess[:i]) for i in range(k + 1)]   # scores every position
        i = 0
        while i < k and guess[i] == wanted[i]:                 # keep the agreeing prefix
            i += 1
        out += guess[:i] + [wanted[i]]                         # plus the target's own token
        if log:
            print("drafted", guess, "kept", i, "->", " ".join(out))
    return out[:n_tokens], passes

tokens, passes = speculative_greedy(target, draft, 6, log=True)
print(passes, "target passes for", len(tokens), "tokens")
# drafted ['the', 'kiln', 'cooled', 'slowly'] kept 2 -> the kiln held
# drafted ['its', 'heat', 'all', 'night'] kept 2 -> the kiln held its heat overnight
# 2 target passes for 6 tokens

The sampling rule, computed exactly with fractions. The drafter badly over-rates "cooled", yet the output distribution is the target's, to the last digit:

from fractions import Fraction as F

def speculative_step(p, q):
    """Exact output distribution of one sampled position under the acceptance rule."""
    accept = {x: q[x] * min(F(1), p[x] / q[x]) if q[x] else F(0) for x in p}
    rejected = 1 - sum(accept.values())
    leftover = {x: max(F(0), p[x] - q[x]) for x in p}          # where the drafter under-shot
    total = sum(leftover.values())
    return {x: accept[x] + (rejected * leftover[x] / total if total else 0) for x in p}

p = {"held": F(6, 10), "cooled": F(3, 10), "shone": F(1, 10)}   # target
q = {"held": F(2, 10), "cooled": F(7, 10), "shone": F(1, 10)}   # drafter
print({x: str(v) for x, v in speculative_step(p, q).items()})
# {'held': '3/5', 'cooled': '3/10', 'shone': '1/10'}

The speed side. If each drafted token is accepted independently with probability alpha, a round yields (1 - alpha^(k+1)) / (1 - alpha) tokens on average. A round costs one target pass plus k draft passes, each costing c target passes, so the speedup is that yield divided by k·c + 1:

def tokens_per_pass(alpha, k):
    """Expected tokens per target pass if each drafted token is accepted with probability alpha."""
    return (1 - alpha ** (k + 1)) / (1 - alpha)

for alpha, cost in [(0.2, 0.05), (0.8, 0.05), (0.95, 0.5)]:
    e = tokens_per_pass(alpha, 4)
    print(alpha, cost, round(e, 2), "tokens per pass, speedup", round(e / (4 * cost + 1), 2))
# 0.2 0.05 1.25 tokens per pass, speedup 1.04
# 0.8 0.05 3.36 tokens per pass, speedup 2.8
# 0.95 0.5 4.52 tokens per pass, speedup 1.51

The weak drafter barely helps; the accurate but slow one loses most of its gain. Checked on 300 seeded random model pairs: greedy speculation must reproduce plain greedy decoding exactly, with no more passes; the sampling rule must return the target distribution exactly for random p and q; and a simulation must match the yield formula:

import random

def random_model(seed, follow=None, agree=0.0, vocab=("a", "b", "c", "d")):
    """A deterministic toy model; with `follow`, it copies that model with probability `agree`."""
    def model(tokens):
        r = random.Random("%s|%s" % (seed, " ".join(tokens)))
        if follow is not None and r.random() < agree:
            return follow(tokens)
        return r.choice(vocab)
    return model

random.seed(29)
ok = True
for trial in range(300):
    t = random_model(trial)
    d = random_model(-trial - 1, follow=t, agree=random.choice([0.0, 0.5, 0.9, 1.0]))
    n, k = random.randint(1, 30), random.randint(1, 6)
    plain = []
    for _ in range(n):                                          # brute force: one pass per token
        plain.append(t(plain))
    spec, passes = speculative_greedy(t, d, n, k)
    ok &= spec == plain and passes <= n
    vocab = "abcde"[:random.randint(2, 5)]
    pw = [random.randint(0, 9) for _ in vocab]
    qw = [random.randint(1, 9) for _ in vocab]
    pw[0] += 1                                                  # at least one nonzero weight
    p = {x: F(w, sum(pw)) for x, w in zip(vocab, pw)}
    q = {x: F(w, sum(qw)) for x, w in zip(vocab, qw)}
    ok &= speculative_step(p, q) == p                           # exactly the target's distribution
    alpha, runs, total = random.choice([0.3, 0.6, 0.9]), 4_000, 0
    for _ in range(runs):
        i = 0
        while i < k and random.random() < alpha:
            i += 1
        total += i + 1
    ok &= abs(total / runs - tokens_per_pass(alpha, k)) < 0.15
print(ok)                                                       # True

The complexity

• Target passes: at most one per generated token, and as few as one per k + 1 tokens.
• Draft cost: k small-model passes per round, which is why c, the drafter's relative cost, sits in the denominator.
• Memory: both models' weights, plus a KV cache for each; entries for rejected guesses must be rolled back.
• Quality: unchanged. Greedy output is identical, and sampled output has the target's distribution.

Where it goes wrong

• A drafter from another family. If the two models tokenize text differently, their guesses cannot be compared token by token.
• A long draft with low acceptance. Every guess after the first rejection is wasted work; shorter drafts suit weaker drafters.
• Large batches. When many requests already share each weight read, the arithmetic is no longer idle and the free verification is gone.
• Forgetting the sampling settings. The acceptance rule must use the same temperature and top-p distribution the target would have sampled from.

As of September 2026, common variants draft with extra prediction heads on the target itself, with n-gram lookups from the prompt, or verify a small tree of alternatives in one pass; the acceptance idea is the same.

When it shows up in interviews

In ML engineering and inference-serving interviews: "how would you cut latency for a chat model without changing its answers?" It pairs with quantization and the KV cache as the three levers of fast decoding, and the follow-up is almost always "what does it cost?": drafter memory, draft compute, and gains that shrink at high batch sizes.

How to say it in an interview

"Decoding is sequential and memory-bound, but verifying known tokens takes one parallel pass. A small drafter proposes k tokens, the target scores all positions at once, and I keep the longest agreeing prefix plus the target's own token at the first mismatch. For sampling, a guess is accepted with probability min(1, p/q) and a rejection resamples from the leftover of p - q, which keeps the output distribution exactly the target's. The speedup is tokens per round over the round's cost, so the drafter must be cheap and usually right."