Speculative decoding

Draft, verify, and the expected tokens per step.

Concept

Decode is memory-bound: a step spends its time reading the weights, and the arithmetic units mostly wait. So a step that checks several positions costs about the same as one that produces a single token. Speculative decoding exploits that.

A small, fast draft model (or a cheap extra head on the big model) guesses the next $\gamma$ tokens, one after another.
The large target model runs one forward pass over all $\gamma$ guesses at once, as if they were a short prompt, which gives its own distribution at every one of those positions.
A verify rule walks the guesses in order, accepting each with probability $\min(1, p(x)/q(x))$ , where $p$ is the target's probability of the guessed token and $q$ the draft's. At the first rejection it draws a replacement from the leftover distribution and stops. If all $\gamma$ are accepted, the target's pass also gives one more token for free.

Each target pass therefore yields between 1 and $\gamma + 1$ tokens. And the rule is built so that the tokens come out with exactly the target model's distribution. Speculative decoding changes the speed, never the output distribution: the draft only decides how much of the target's work is reused. (Under greedy decoding this reduces to "keep the guesses that match the target's argmax".)

What it costs: the draft's own steps, and some wasted target work on rejected guesses. It pays when the draft agrees with the target often (acceptance $\alpha$ high) and is cheap (cost ratio $c$ low). It helps most at small batch sizes; at large batches the target step is no longer so memory-bound, and the verified positions compete with other users'.

Variants. Medusa adds several extra decoding heads to the target itself, each predicting a token further ahead, and verifies a tree of candidates in one pass. EAGLE drafts at the level of the target's hidden features rather than tokens, with a light head. Both avoid running a separate draft model.

Interactive

Draft γ tokens, verify them in one pass

Top: Leviathan et al.'s closed forms (i.i.d. acceptance α; one draft step costs c of a target step). Bottom: 4,000 rounds of the real accept/reject rule on an 8-token toy vocabulary.

Acceptance α0.80

Draft length γ4

Draft cost c0.05

Tokens / target pass

3.36

Speed-up

2.80×

Best γ here

3.09×

Tokens if all accepted

Draft–target mismatch0.60

α = Σ min(p, q)

0.639

Measured acceptance

0.642

Tokens / pass

2.49

formula 2.48

tok 041.6 / 41.5%

tok 122.8 / 22.6%

tok 213.8 / 13.9%

tok 39.3 / 9.1%

tok 45.6 / 5.6%

tok 53.4 / 3.6%

tok 62.1 / 2.2%

tok 71.4 / 1.3%

Grey: the target distribution p. Blue: what speculative decoding actually emitted. They match whatever the draft is: only the speed changes.

Maths

Let the target be $p$ and the draft $q$ . A drafted $x \sim q$ is accepted with probability $\min(1, p(x)/q(x))$ , so the per-token acceptance is

\beta = \sum_x q(x)\min\!\left(1, \frac{p(x)}{q(x)}\right) = \sum_x \min(p(x), q(x)).

On rejection the replacement comes from $r(x) = \frac{\max(0, p(x) - q(x))}{1 - \beta}$ . The emitted token's distribution is then

\min(p(x), q(x)) + (1 - \beta)\,r(x) = p(x),

exactly the target's (Leviathan et al., §3; Chen et al.). With i.i.d. acceptance $\alpha = \mathbb{E}[\beta]$ and $\gamma$ drafts, the expected tokens per target pass are

\mathbb{E}[\text{tokens}] = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha},

and if a draft step costs $c$ target steps, the expected speed-up is $\frac{1 - \alpha^{\gamma+1}}{(1-\alpha)(\gamma c + 1)}$ (their Theorem 3.8). For example $\alpha = 0.8$ , $\gamma = 4$ gives 3.36 tokens per pass, and with $c = 0.05$ a 2.80× speed-up.

Code

// src/lib/inference/speculative.ts (excerpt)
export function verify(
  p: Vector,
  q: Vector,
  x: number,
  u: number,
  rng: () => number,
) {
  if (u < Math.min(1, p[x]! / q[x]!)) return { accepted: true, token: x };
  return { accepted: false, token: sampleFromProbs(residual(p, q), rng) };
}

The tests check the emitted distribution equals $p$ to $10^{-14}$ , and run 40,000 Monte Carlo rounds whose acceptance, tokens per pass and token histogram match the formulas.