Speculative decoding: faster generation with an exact proof

Generating text with a large model is slow in a peculiar way: the GPU is mostly waiting. Each new token needs a full pass over the model’s weights, and reading those weights from memory takes far longer than the arithmetic done on them. Speculative decoding exploits that idle compute. A small model guesses several tokens ahead, the large model checks all the guesses in one pass, and a careful acceptance rule makes the output exactly what the large model would have produced on its own.

That last property is what makes it remarkable. It is not an approximation or a quality trade-off. It is a sampling algorithm with a short, complete proof. This article covers why decoding is memory-bound, the algorithm, the proof, the expected speedup, and the newer variants (Medusa, EAGLE, lookahead and tree verification) that dispense with the separate draft model.

Decoding is memory-bound

During generation, each step produces one token per sequence. For that token, every weight in the model is read from GPU memory and used for roughly two floating-point operations (a multiply and an add). A 70B-parameter model in 16-bit precision is 140 GB of weights. An H100 reads memory at about 3.35 TB/s, so a single decoding step takes at least 140 / 3,350 ≈ 42 ms, a ceiling of around 24 tokens per second, however fast the arithmetic units are. They spend most of each step idle.

The key observation: processing several tokens at once costs almost the same as processing one, because the weights are read once either way. Prompt processing (prefill) exploits this already, handling thousands of tokens per pass. Decoding can’t, because token t+1 depends on token t. Unless you can guess token t+1 in advance.

Draft, then verify

Speculative decoding (Leviathan et al., 2022; Chen et al., 2023, independently) pairs the large target model p with a small, fast draft model q that shares its tokenizer. Each round:

1. The draft generates γ tokens autoregressively. It is small, so this is cheap.
2. The target runs one forward pass over the prompt plus all γ draft tokens, producing its own distribution at every position, plus one more beyond the last.
3. Going left to right, each draft token x is accepted with probability min(1, p(x) / q(x)).
4. At the first rejection, a replacement is sampled from the residual distribution max(0, p − q), normalised, and the rest of the draft is discarded. If all γ are accepted, one bonus token is sampled from the target’s last distribution.

Every round produces at least one token, because a rejection still yields a replacement. So speculative decoding is never slower in tokens per target pass. The only cost is the draft’s own compute, and the wasted target compute on positions after a rejection.

Why it is exact

Fix one position and consider any token x. There are two ways the round can output x there: the draft proposes x and it is accepted, or the draft proposes something that is rejected and the replacement is x.

Summing over all tokens, the overall acceptance probability is β = Σ min(p, q), so a rejection happens with probability 1 − β. Because both distributions sum to one, 1 − β = Σ max(0, p − q), which is exactly the normalising constant of the residual. So:

The argument applies at every position conditioned on the prefix, so the whole generated sequence has exactly the target’s distribution. With greedy decoding the rule collapses to something simpler: accept a draft token if and only if it is the target’s argmax at that position. Either way the output is identical to running the target alone. The draft model can only affect speed.

How much faster

Let α be the expected acceptance rate per token and assume, as the paper’s analysis does, that acceptances are independent. A round stops at the first rejection, so the number of tokens it yields is a truncated geometric variable:

If one draft step costs a fraction c of a target step, a round costs γc + 1 target steps, and the wall-clock speedup is that expression divided by (γc + 1). Fig. 3 plots both.

Three lessons from the curves:

• α dominates. Going from 0.7 to 0.9 matters far more than any tuning of γ. Drafter quality is the main lever.
• γ has an optimum. Long drafts are wasted when α is low, because the chain almost certainly breaks early. Adaptive schemes pick γ per round from the draft’s confidence.
• Reported speedups are 2–3×. Leviathan et al. measured 2–3× on T5-XXL. Chen et al. reported 2–2.5× on the 70B Chinchilla. Both had identical outputs.

Where drafts come from

A separate small model is the classic drafter, but it has to be trained, served and kept in sync. Alternatives:

• Medusa (Cai et al., 2024) adds several extra decoding heads to the target model itself. Head k predicts the token k positions ahead from the same final hidden state. There is no second model, and the heads are cheap to train. The paper reports more than 2.2× with a frozen backbone and 2.3–3.6× when fine-tuned jointly. Its optional “typical acceptance” rule trades exactness for speed.
• EAGLE (Li et al., 2024) drafts at the feature level: a single light layer predicts the target’s next second-to-top-layer feature from the current feature plus the already-sampled next token. Features are smoother to extrapolate than tokens. It reports around 2.7–3.5× on LLaMA2-Chat 70B and stays lossless. EAGLE-2 makes the draft tree dynamic based on confidence, and EAGLE-3 trains the drafter on the target’s own multi-layer features.
• Self-speculation (for example LayerSkip) uses the target’s own early layers, exiting early, as the drafter, and the full model as the verifier.
• Prompt lookup drafts by copying: if the last few generated tokens match an n-gram in the prompt, propose what followed it. This is free, and very effective for code edits, summaries and RAG answers, where output repeats the input.
• Lookahead decoding (Fu et al., 2024) needs no drafter at all. It runs Jacobi-style parallel guesses inside the target and caches n-grams that converge, then verifies them like drafts.

Trees instead of chains

A chain of γ guesses dies at its first wrong token. A tree hedges: at uncertain positions, keep the top two or three candidates, so the draft becomes a tree of possible continuations. The target can verify the whole tree in one pass by flattening it into a sequence and using a tree attention mask, so each node attends only to its own ancestors (SpecInfer, Medusa and EAGLE all do this). The longest accepted path wins. Trees raise the expected accepted length per pass at the cost of verifying more tokens, which is a good trade while the target pass is still memory-bound.

In practice

• It helps most at small batch sizes. The free compute exists because decoding is memory-bound. Large batches already fill the GPU’s arithmetic units, and verifying extra tokens then costs real time. Serving systems often enable speculation only when load is light.
• Roll back the KV cache. Rejected positions have already written keys and values into the cache, and those entries must be discarded. Paged KV caches make this cheap.
• Measure α on your traffic. Acceptance depends heavily on the task. Code and structured output are predictable, open-ended chat less so. Watch per-request acceptance: a drafter trained on the wrong distribution quietly costs throughput.
• Sampling settings must match. The proof requires the acceptance test to use the distributions actually sampled from, after temperature, top-p and any penalties, for both models.

The algorithm in code

One round, complete: draft, single verification pass, left-to-right acceptance, residual resampling and the bonus token.

// One round of speculative sampling. Distributions are arrays over the vocabulary.
type Dist = number[];
type Model = (prefix: number[]) => Dist;                      // next-token distribution
type ModelBatch = (prefix: number[], draft: number[]) => Dist[]; // gamma + 1 distributions, ONE pass

const sample = (d: Dist, u = Math.random()) => {
  let acc = 0;
  for (let i = 0; i < d.length; i++) if ((acc += d[i]) > u) return i;
  return d.length - 1;
};

export function speculativeStep(prefix: number[], draft: Model, target: ModelBatch, gamma = 5) {
  // 1. The draft proposes gamma tokens, one at a time (cheap and sequential).
  const proposed: number[] = [], qs: Dist[] = [];
  for (let i = 0; i < gamma; i++) {
    const q = draft([...prefix, ...proposed]);
    qs.push(q);
    proposed.push(sample(q));
  }

  // 2. The target scores every position at once: p_1 .. p_{gamma+1}.
  const ps = target(prefix, proposed);

  // 3. Accept left to right with probability min(1, p/q); stop at the first rejection.
  const out: number[] = [];
  for (let i = 0; i < gamma; i++) {
    const x = proposed[i], p = ps[i][x], q = qs[i][x];
    if (Math.random() < Math.min(1, p / q)) { out.push(x); continue; }

    // Rejected: sample a replacement from the residual max(0, p - q), renormalised.
    const residual = ps[i].map((pi, j) => Math.max(0, pi - qs[i][j]));
    const z = residual.reduce((a, b) => a + b, 0);
    out.push(sample(residual.map((r) => r / z)));
    return out; // everything after the rejection is discarded
  }

  // 4. All gamma accepted: the target's last distribution gives one bonus token for free.
  out.push(sample(ps[gamma]));
  return out;
}

References

1. Leviathan, Y., Kalman, M. & Matias, Y. (2022). Fast Inference from Transformers via Speculative Decoding. ICML 2023. arXiv:2211.17192
2. Chen, C. et al. (2023). Accelerating Large Language Model Decoding with Speculative Sampling. arXiv:2302.01318
3. Cai, T. et al. (2024). Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads. arXiv:2401.10774
4. Li, Y. et al. (2024). EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty. arXiv:2401.15077
5. Li, Y. et al. (2024). EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees. arXiv:2406.16858
6. Miao, X. et al. (2023). SpecInfer: Accelerating Generative LLM Serving with Tree-based Speculative Inference and Verification. arXiv:2305.09781
7. Fu, Y. et al. (2024). Break the Sequential Dependency of LLM Inference Using Lookahead Decoding. arXiv:2402.02057
8. Elhoushi, M. et al. (2024). LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding. arXiv:2404.16710