Speculative Decoding

For NAO + anyone who has ever watched tokens dribble out of an LLM and wondered why a 70B model can't just go faster. Speculative decoding is the single most important "free lunch" in LLM serving: a 2–3× latency speedup with mathematically identical output — no quantization, no distillation, no quality loss. This is the inference-internals companion to [[model-routing]] (which picks which model to run) and to [[quantization]] / [[flash-attention]] (which make a single forward pass cheaper). Speculative decoding instead attacks the number of sequential forward passes — the thing that actually bounds autoregressive latency.

What it is (intuition first)

Generating text from a transformer is autoregressive: to produce token N+1 you must already have token N. So a 70B model emitting 200 tokens does 200 sequential forward passes, each one a full march through the network. Crucially, each pass is memory-bandwidth bound, not compute bound: at batch size 1 you load all ~140 GB of weights from HBM just to compute one token. The GPU's matrix units sit mostly idle. You are paying to read the weights, not to do math.

Here is the trick. The same forward pass that costs ~one token of latency can score many tokens in parallel for almost the same price — because scoring is one big matmul over a sequence, which finally uses those idle matrix units, and the dominant cost (loading the weights) is paid once either way.

So: get a cheap, fast "draft" model to guess the next few tokens, then have the big "target" model check all of them in a single pass. If the guesses are good, you got several tokens for the price of one big forward pass. If a guess is wrong, you throw away the rest and try again. The genius is a modified rejection-sampling rule that makes the accepted output exactly the same distribution the big model would have produced on its own. It is not an approximation. It is lossless.

The vending-machine analogy. A junior assistant (draft) writes a fast first draft of the next sentence. The senior editor (target) reads the whole draft in one glance, keeps the prefix that matches what they'd have written, fixes the first word that diverges, and hands it back. The editor still does all the real judging — they just stopped writing one word at a time. The final text is byte-for-byte what the editor alone would have produced; they just got there faster by reading instead of writing.

Why it matters

• Latency is the product. For interactive Alice, time-to-first-token and inter-token latency are what users feel. A 2–3× speedup is the difference between sluggish and snappy, with zero change to what Alice says.
• It's lossless. Unlike [[quantization]] (trades bits for quality) or distillation (trades a smaller model for quality), speculative decoding's output is provably identical to the target model "within hardware numerics" (DeepMind, Chen et al. 2023). You don't have to re-run your evals.
• It exploits hardware you already paid for. Memory-bound decode leaves the GPU's FLOPs idle; speculation converts that idle compute into thrown-away-but- cheap parallel scoring. It is, almost uniquely, a systems win that needs no ML compromise.
• It's now table stakes. vLLM, SGLang, TensorRT-LLM, and llama.cpp all ship it. EAGLE-3 (NeurIPS'25) is the current SOTA and is built into vLLM/SGLang. If you serve your own weights, this is the first optimization to reach for after paged attention.

Reported real numbers: 2–2.5× on Chinchilla 70B (DeepMind 2023), 2–3× on T5X (Google 2023), 2.2–3.6× for Medusa, 2.7–3.5× for EAGLE-1 on Llama2-70B, and up to ~6.5× for EAGLE-3.

How it works (real mechanics)

Setup

Two distributions over the vocabulary at each position:

• `p(x)` — the target model (the big, correct one you want to sample from).
• `q(x)` — the draft model (small/fast, approximates p).

Pick γ (gamma) = how many tokens the draft guesses per round (typically 3–7).

One speculation round

1. Draft (γ sequential cheap passes). From the current context, autoregress the draft model to propose x₁, … , x_γ, recording its probabilities q(x₁), … , q(x_γ).

1. Verify (1 big parallel pass). Run the target model once over the context plus all γ proposed tokens at once. Thanks to the causal mask, a single forward pass yields p(x₁), … , p(x_γ) and p(x_{γ+1}) — the target's own distribution for the token after the last accepted one. This is the whole point: γ+1 target distributions for the latency of ~one decode step.

1. Accept / reject left-to-right (modified rejection sampling). For each proposed token xᵢ, draw r ~ Uniform(0,1) and accept if

   r  <  min( 1,  p(xᵢ) / q(xᵢ) )

- If the target likes the token at least as much as the draft did (p ≥ q), it's always accepted. - If the target likes it less (p < q), accept with probability p/q.

Accept tokens until the first rejection, then stop the round.

1. Repair on rejection (resample from the residual). At the first rejected position, don't just drop the token — resample one token from the normalized positive difference of the two distributions:

   x'  ~  norm( max(0, p(x) − q(x)) )
        = max(0, p(x) − q(x)) / Σ_x max(0, p(x) − q(x))

This "residual" puts mass exactly where the target wanted more than the draft gave. This single corrected token replaces the rejected one.

1. Bonus token. If all γ tokens were accepted, you also get a free extra token sampled from p(x_{γ+1}) (already computed in step 2). So a fully-accepted round yields γ+1 tokens from one big forward pass.

Why it's lossless (the key theorem)

The acceptance rule + residual resampling are constructed so that the marginal distribution of the emitted token is exactly `p(x)`. Sketch: the probability of emitting token x =

P(propose x) · P(accept x)  +  P(reject step) · P(residual draws x)
= q(x)·min(1, p(x)/q(x))  +  (rejection mass)·norm(max(0,p−q))(x)
= min(q(x), p(x))  +  max(0, p(x) − q(x))
= p(x)                                  ✓

The two terms min(p,q) and max(0, p−q) always sum to p(x). So whatever draft you use, the output is sampled from the target — a bad draft only makes you slower (more rejections), never wrong. (Formal proof: Theorem 1 in Leviathan et al. 2023 and Chen et al. 2023.)

Pseudocode

def speculative_decode(prompt, target, draft, gamma, n_tokens):
    tokens = list(prompt)
    while len(tokens) < n_tokens:
        # 1. draft proposes gamma tokens (gamma cheap sequential passes)
        draft_toks, q = [], []
        ctx = tokens[:]
        for _ in range(gamma):
            qi = draft.next_dist(ctx)          # q(.) at this position
            t  = sample(qi)
            draft_toks.append(t); q.append(qi)
            ctx.append(t)

        # 2. ONE target pass scores all gamma proposals + the next position
        p = target.dists(tokens + draft_toks)  # p[0..gamma], length gamma+1

        # 3 & 4. accept/reject left-to-right
        n_accepted = 0
        for i, t in enumerate(draft_toks):
            r = uniform()
            if r < min(1.0, p[i][t] / q[i][t]):
                tokens.append(t); n_accepted += 1
            else:
                # resample the corrected token from the residual
                resid = normalize(relu(p[i] - q[i]))
                tokens.append(sample(resid))
                break

        # 5. all accepted -> free bonus token from p[gamma]
        if n_accepted == gamma:
            tokens.append(sample(p[gamma]))
    return tokens

Expected speedup — the acceptance rate α

Let `α` = expected per-token acceptance probability (how well the draft matches the target on this workload). Leviathan et al. derive the expected number of tokens produced per round (one big forward pass) as a geometric series:

E[tokens per round]  =  (1 − α^(γ+1)) / (1 − α)

The speedup vs. plain decoding is that number divided by the relative cost c of a draft step:

speedup  ≈  (1 − α^(γ+1)) / ( (1 − α)(γc + 1) )

Read off the intuition: higher α (better draft) and a cheaper draft (c→0) both help; pushing γ too high gives diminishing returns because each extra slot only pays off if all preceding ones were accepted (the α^(γ+1) term). In practice α≈0.7–0.8 with a good EAGLE head and γ≈4–6 lands the 2–3× regime.

Key ideas & tradeoffs — the family of methods

The original method needs a separate, aligned draft model. Most progress since has been about getting the draft for free or drafting more than one sequence at a time.

Tree attention (Medusa, EAGLE-2/3, vLLM) is the second big lever: instead of one γ-length guess, the draft proposes a tree of candidate continuations and the target verifies all branches in a single masked forward pass, accepting the longest matching path. This raises the effective acceptance rate per target call.

Self-speculation in one model. Medusa and EAGLE are "self-speculative": the draft lives inside the target deployment, so you don't host two models, manage two sets of weights, or fight tokenizer/vocab mismatches. This is why they won in production — the operational cost of a separate aligned draft model was the real blocker.

Honest caveats & open questions

• Latency win, not a throughput win. At batch size 1 (interactive chat), the GPU is idle and speculation is pure profit. At high batch size the GPU is already compute-saturated — there is no idle compute to spend, and the extra draft + verify work can reduce total throughput. Spec decoding shines for low-latency, low-batch serving; for max-tokens-per-second batch inference it can hurt. Tune per workload. (This is the single most common misunderstanding.)
• A bad draft is slow, never wrong. Losslessness is guaranteed by the math, so the only failure mode is a low acceptance rate α — you spend draft compute and throw it away. Out-of-distribution inputs (a code model drafting for prose) tank α. The draft must be aligned to the target on the actual traffic.
• "Lossless" needs an asterisk. It's lossless for exact sampling at a given temperature. Medusa's "typical acceptance" and some fast variants relax the exact rule for speed and are not distribution-identical — read the fine print before claiming "no quality change." Greedy decoding is a special case that's straightforward; nucleus/top-p interacts with the rejection rule and must be handled carefully (vLLM does).
• Tokenizer / vocabulary mismatch breaks naive separate-draft setups; you need the draft and target to share a vocabulary (or a heterogeneous-vocab variant).
• Memory & training cost. Medusa/EAGLE heads add parameters and require training the heads (cheap relative to pretraining, but not free). EAGLE-3's scaling law means more draft-training data keeps buying speedup — a new axis of spend. Tree attention adds KV-cache and kernel complexity.
• `γ` tuning is workload-specific. Too small wastes the parallel verify; too large wastes draft passes on tokens that won't be reached. The optimum depends on α and c and drifts across tasks; adaptive-γ schemes exist but add machinery.
• Open questions (2025–26): dynamic draft selection per request (bandit-style drafter choice), spec decoding for reasoning / long chains (see [[test-time-compute-reasoning]] — long generations are exactly where latency hurts most), batched/continuous-batching-friendly speculation, and a reported side-channel: acceptance patterns can leak information about other requests sharing a batch.

How it connects to OpenAlice

• Alice's latency budget. Alice's responsiveness is a first-class product metric (see the memory rule on staying responsive). Wherever OpenAlice serves its own open weights — not a hosted API — speculative decoding is the highest-leverage knob for inter-token latency, with no personality or quality risk. This matters for [[agentic-loops]] where a single user turn may emit many tokens across tool calls.
• It's a different lever than routing. [[model-routing]] answers "which model should serve this request"; speculative decoding answers "how do I make the chosen model emit tokens faster." They compose: route to the right model, then speculatively decode it. Both are M13 cost/latency-ladder concerns.
• Provider reality check. OpenAlice's default path is the Codex OAuth / GPT-5.x hosted provider — there speculation is the vendor's concern, invisible to us; we can't tune γ on someone else's endpoint. Spec decoding becomes our lever the moment we self-host a model (a future openalice-runner / on-prem inference path), which is exactly when an interactive product wants every millisecond back. Worth knowing now so the architecture leaves room for it.
• N-gram speculation for RAG-heavy turns. Many Alice turns quote the context heavily (summaries, "based on the doc above…", code edits). Prompt-lookup / n-gram drafting is nearly free and can be a big win on exactly those turns — a cheap thing to reach for first if/when we run our own inference.
• Related internals. This article is the autoregressive-latency counterpart to [[flash-attention]] (cheaper attention per pass), [[quantization]] (cheaper weights per pass), and [[mixture-of-experts]] (fewer active params per pass). Those shrink the cost of one forward pass; speculative decoding cuts the number of sequential passes. For the mechanics of what a forward pass actually computes, see [[attention-and-transformers]].

Cross-links to siblings that exist in this library: [[model-routing]], [[quantization]], [[flash-attention]], [[mixture-of-experts]], [[attention-and-transformers]], [[test-time-compute-reasoning]], [[agentic-loops]]. An `llm-inference-internals` overview article does not exist yet — the KV-cache / memory-bandwidth framing it would cover is summarized inline above.