Speculative Decoding — The Math

Why decoding is slow in the first place

To see why speculation helps, you have to see what wastes time. During generation the model runs in decode mode: one token in, one token out, repeated. Each step loads the full parameter set — for a 70B model in 16-bit that is ~140 GB of weights — and does a tiny amount of arithmetic against a single new position. The bottleneck is memory bandwidth, not compute: the matmuls are skinny (a length-1 sequence), so the hardware spends its time streaming weights, not multiplying.

The consequence is stark. A modern accelerator might sustain hundreds of TFLOP/s but only a few TB/s of bandwidth, so processing one token and processing several tokens in one pass cost almost the same wall-clock time — the weights are loaded once either way. That is the exploitable gap. If you could somehow present the target model with several candidate tokens at once and check them together, you would pay one memory-bound pass and potentially advance several positions. Speculative decoding is precisely a scheme for manufacturing those candidates cheaply, with a draft model, and verifying them for free, in the pass you were going to pay for anyway.

The core loop: propose k, verify in parallel

Fix two models over the same vocabulary: a small draft q (fast, approximate) and the large target p (slow, the one whose distribution we must match). One cycle of speculative decoding runs as follows.

1. Draft: run q autoregressively for k steps, sampling
   x_1 ~ q(·|prefix), x_2 ~ q(·|prefix,x_1), ... x_k.
   (k small serial draft passes, each cheap.)

2. Verify: run p ONCE over the whole block
   [prefix, x_1, ..., x_k]  →  p(·|prefix), p(·|prefix,x_1), ...
   One target forward pass returns the target's next-token
   distribution at ALL k+1 positions in parallel.

3. Accept/reject x_1..x_k left to right by the rule below.
4. Emit the accepted prefix + one bonus token from p.

The engine that makes step 2 possible is the same causal masking used in training. Because a transformer with a causal mask computes, for every position, its next-token distribution conditioned only on earlier positions, one forward pass over the k-token block simultaneously yields p(·) at each position — exactly the distributions we need to judge each draft token. Verification is teacher forcing: the guesses become the inputs, and the target grades them all at once.

The wrong idea: exact-match verification

The naive verifier is tempting and wrong. It says: at each position take the target’s most likely token argmax p, and accept the draft token only if it matches. This works for pure greedy decoding, but it silently changes the sampling distribution the moment you use any temperature above zero. Sampling is supposed to explore the tail of p; an exact-match rule only ever accepts the mode, so it biases generation toward greedy output and destroys the diversity you asked for.

Worse, a strict match is needlessly stingy. Suppose the target assigns probability 0.4 to token A and 0.35 to token B, and the draft happened to propose B. Under exact-match against argmax you reject B even though the target would itself have sampled B roughly a third of the time — a perfectly good token thrown away, forcing another expensive cycle. What we want is a rule that accepts a draft token in proportion to how much the target actually likes it, not merely when the target likes it most. That rule exists, it is exact for sampling at any temperature, and it comes from classical rejection sampling adapted to two discrete distributions.

The acceptance rule: modified rejection sampling

Here is the rule. For each drafted token x_i, drawn from the draft with probability q(x_i), look up the target probability p(x_i) at the same position and accept with probability

P(accept x_i) = min( 1, p(x_i) / q(x_i) ).

Read it intuitively. If the target likes x_i at least as much as the draft did (p ≥ q), the ratio is ≥ 1 and you accept unconditionally — the draft, if anything, under-proposed this token. If the target likes it less (p < q), you accept only with probability p/q, throttling the draft’s over-eagerness back down to the target’s taste. You walk the block left to right; the first rejection stops the run, and everything before it is committed.

On a rejection at position i, you do not simply discard and restart. You resample the replacement token from the residual distribution, the normalized positive part of the gap between target and draft:

x_i' ~ norm( (p - q)_+ ),   where (p - q)_+ (t) = max(0, p(t) - q(t)),
        norm( (p - q)_+ )(t) = (p(t) - q(t))_+ / Σ_t (p(t) - q(t))_+ .

This correction token is the ‘bonus’ that keeps every cycle productive: even a cycle that accepts zero draft tokens still emits one genuine target-distributed token, so you never go backwards.

Why it is exact: the one-line proof

The claim is that a token produced by this accept-or-resample procedure is distributed exactly as p. Consider any token value t. There are two disjoint ways it can be emitted at a position: it was drafted and accepted, or something was drafted, rejected, and t came from the residual.

P(emit t)
  = P(draft t)·P(accept t)          [drafted & accepted]
  + P(reject anything)·P(residual = t) [drafted, rejected, corrected]

  = q(t)·min(1, p(t)/q(t))  +  β_rej · (p(t)-q(t))_+ / β_rej
  = min(q(t), p(t))            +  (p(t) - q(t))_+
  = p(t).

The two pieces telescope: min(q,p) plus (p−q)_+ is p for every token, because when p ≤ q the second term is zero and min = p, and when p > q the first term is q and the second is p−q. The overall rejection mass β_rej = Σ_t (p(t) − q(t))_+ cancels against the residual’s normalizer, which is why the correction has to be drawn from that specific distribution and no other. The output is target-exact for any draft q — even a bad draft only costs you speed, never correctness.

Acceptance rate = 1 minus total-variation distance

How often does a single draft token survive? Average the acceptance probability over the draft’s own proposals at a position:

α = Σ_t q(t) · min(1, p(t)/q(t))
  = Σ_t min( q(t), p(t) )
  = 1 - Σ_t (q(t) - p(t))_+
  = 1 - D_TV(p, q).

So the per-token acceptance rate α equals one minus the total-variation distance between the target and draft distributions. This is the single most important quantity in the whole method, and the identity makes the design goal crisp: make the draft’s next-token distribution as close as possible to the target’s. Everything that improves a draft — distilling it from the target, training it on the target’s outputs, sharing the target’s tokenizer and hidden features — is ultimately an effort to shrink D_TV and push α toward 1. A draft that perfectly mimicked the target would have α = 1 and accept everything; a draft uncorrelated with the target would have α near the collision probability of the target’s own distribution, and speculation would barely help.

Expected accepted tokens per cycle

Model the k positions in a block as independent Bernoulli trials, each accepted with rate α — a simplification, since real acceptances are correlated, but an excellent guide. Acceptance stops at the first failure, so the number of accepted draft tokens is a truncated geometric variable. Adding the one guaranteed bonus token, the expected tokens produced per cycle is

E[tokens / cycle] = 1 + α + α^2 + ... + α^k
                 = (1 - α^(k+1)) / (1 - α).

This is the yardstick from Leviathan et al. (2023). Sanity-check the endpoints. If α = 1 (perfect draft), the sum is k + 1 — you accept the whole block plus the bonus, the best possible. If α = 0 (useless draft), the sum collapses to 1 — you get only the bonus token and speculation neither helps nor hurts throughput (though it wastes the draft compute). The formula also shows diminishing returns in k: each extra speculative position contributes α^(k), a term that shrinks geometrically, so past a point longer blocks add expected tokens too slowly to justify their draft cost. That tension is the whole tuning problem.

The speedup formula

Wall-clock speedup is expected tokens per cycle divided by the cost of a cycle, measured in units of one target forward pass. Let c be the cost of a single draft step relative to a target step (for a draft an order of magnitude smaller, c ≈ 0.1). A cycle runs k serial draft steps plus one target verification pass, so its cost is about (1 + k·c) target-passes, and

              E[tokens / cycle]       1 - α^(k+1)
speedup  =  -----------------  =  ---------------------
                cost / cycle       (1 - α)(1 + k·c)

The numerator is the reward (tokens harvested per cycle), the denominator the price (target pass plus draft overhead). Set c = 0 and you recover the idealized ceiling (1 − α^(k+1))/(1 − α) — the speedup you would get if drafting were free. The (1 + k·c) factor is the tax reality imposes: every speculative position you add costs c of draft compute whether or not it is accepted. Maximizing this expression over k for a given (α, c) is how serving systems pick a block length, and the optimum is usually a modest k — often 3 to 8.

A worked expected-speedup example

Take a draft roughly 10× cheaper than the target, so c = 0.1, a block of k = 4, and an acceptance rate α = 0.75 (a realistic figure for a well-distilled draft on in-domain text). First the expected tokens per cycle:

E[tokens/cycle] = (1 - 0.75^5) / (1 - 0.75)
               = (1 - 0.2373) / 0.25
               = 0.7627 / 0.25
               = 3.05 tokens.

So on average each expensive target pass advances generation by about three tokens instead of one. Now charge the draft overhead: the cost of the cycle is 1 + k·c = 1 + 4×0.1 = 1.4 target-passes, giving

speedup = 3.05 / 1.4 ≈ 2.18×.

The gap between the 3.05× idealized ceiling and the ~2.2× realized speedup is exactly the draft tax. Push α to 0.9 with the same k and c and expected tokens jump to (1 − 0.9^5)/0.1 = 4.10, for a speedup near 4.10/1.4 ≈ 2.9×; drop α to 0.5 and it falls to (1 − 0.5^5)/0.5 = 1.94 tokens, or 1.94/1.4 ≈ 1.4×. That sensitivity — acceptance rate swinging the answer from 1.4× to 2.9× — is why published results cluster in the 1.5–3× range and depend heavily on how well the draft matches the workload.

The cost/benefit trade: draft overhead vs acceptance

Speculative decoding is a bet, and like any bet it can lose. Every cycle you pay k·c of guaranteed draft compute up front, hoping to win back more than that in accepted tokens. Two regimes make the bet bad. If the draft is too weak (α low), most guesses are rejected, you harvest few tokens per cycle, and the draft cost is pure loss — you can end up slower than plain decoding. If the draft is too expensive (c large, e.g. a draft only 2× smaller than the target), even a high acceptance rate cannot cover the overhead.

This creates a sweet spot. You want a draft small enough that c is tiny yet accurate enough that α is high — goals in tension, since shrinking a model usually widens D_TV. Block length k is the other dial: too short and you leave accepted tokens on the table; too long and you burn draft compute on speculative positions whose acceptance probability α^k has already decayed toward zero. In practice teams profile α on representative traffic and tune k to the peak of the speedup curve. Batching complicates it further: as batch size grows, decode drifts from memory-bound toward compute-bound, the free parallel-verify assumption weakens, and speculation’s edge narrows.

Practical levers: temperature, drafts, and domains

Several knobs move α in the field. Temperature: lower sampling temperature sharpens both distributions and tends to raise agreement, so speculation typically works better at low temperature and greedy-ish decoding than at high temperature where the target’s tail is broad and the draft struggles to match it. Draft training: the highest-leverage move is distilling the draft on the target’s own outputs so their next-token distributions align — recall α = 1 − D_TV, so distribution matching is literally the objective.

Domain match matters as much as raw draft quality: a draft trained on general web text will show high α on prose and low α on, say, dense code or a rare language, so the realized speedup is workload-dependent and worth measuring per use case. Vocabulary and tokenizer must be shared, since the acceptance rule compares p(t) and q(t) over the same token set. And on CPU-hosted small models the calculus is friendlier than it looks: decode there is even more bandwidth-starved, the idle-compute slack speculation exploits is larger, and a tiny draft that fits in cache can verify against a larger model with a genuinely favorable c.

Beyond a separate draft: self-drafting

Running two models is operationally awkward — two sets of weights, two memory footprints, a tokenizer you must keep identical. A newer family removes the standalone draft entirely and lets the target model draft for itself, reusing the representations it already computes. The verification math is unchanged; what changes is where the candidate tokens come from and how several candidate continuations are checked at once.

The key enabling idea is tree attention. Instead of verifying a single linear block of k tokens, self-drafting methods propose a tree of candidate continuations (several alternatives at each step) and verify the whole tree in one target pass using an attention mask that respects each branch’s ancestry. This raises the expected number of accepted tokens per pass because the target can pick whichever branch it agrees with, rather than being stuck with one linear guess that fails at position two. Two systems dominate this space, Medusa and EAGLE, and both are worth knowing as the practical state of the art.

Medusa: extra heads on the target

Medusa bolts a handful of lightweight decoding heads onto the target model’s final hidden state. Where the original model has one head predicting the next token, Medusa adds heads that predict the token two, three, and four positions ahead, all from the same forward pass. Each head emits several top candidates, their Cartesian product forms a tree of proposed continuations, and tree attention verifies the tree in a single target pass — no second model required, just a few small trained heads.

Because the heads are cheap and share the backbone’s computation, Medusa’s draft overhead c is very small. Its notable twist is the acceptance scheme: rather than strict modified rejection sampling, Medusa often uses a typical acceptance criterion that admits any candidate whose target probability clears a temperature-scaled threshold. This trades the exact distribution-preservation guarantee for a higher acceptance rate and simpler sampling — a deliberate, and usually acceptable, relaxation for chat workloads. Medusa is attractive precisely because it retrofits onto an existing model by training only the extra heads, leaving the expensive backbone frozen.

EAGLE: drafting in feature space

EAGLE (Extrapolation Algorithm for Greater Language-model Efficiency) sharpens the draft by autoregressing at the feature level rather than the token level. Its insight is that predicting the next hidden-state feature vector is a more regular, more predictable problem than predicting the next token id, and that feeding the draft the target’s own second-to-top-layer features (together with the previously sampled token to resolve ambiguity) makes the draft far more faithful. A better-aligned draft means a lower D_TV, and so a higher acceptance rate α.

EAGLE keeps exact target verification and uses a draft tree, so it inherits the correctness of the rejection rule while pushing α higher than a generic small draft achieves. EAGLE-2 adds a dynamic draft tree whose shape adapts to the model’s per-step confidence — growing branches where the draft is unsure, pruning where it is certain — which lifts the expected accepted tokens per pass further. Together with Medusa, EAGLE marks the shift from ‘bring your own draft model’ to self-contained speculative decoding, where the acceptance math of this article stays exactly the same and the gains come from feeding it better, cheaper candidates.

Pitfalls and where the speedup hides

A few traps recur. First, ignoring draft overhead: quoting ‘3×’ from expected-tokens-per-cycle while omitting the (1 + k·c) denominator overstates real speedup, sometimes badly. Second, assuming independence: the geometric model treats acceptances as i.i.d., but a draft that goes off the rails tends to fail in runs, so measured acceptance can trail the per-token estimate on hard prompts. Third, batch interference: speculation shines in the low-batch, memory-bound regime; at high batch sizes the parallel-verify pass stops being ‘free’ and the advantage erodes.

Fourth, distribution drift between draft and target: a mismatched tokenizer, a different quantization of the two models, or an out-of-domain workload silently lowers α and can turn a win into a loss — always measure α on real traffic, never assume it. The reassuring counterweight to all of this is the exactness proof: because modified rejection sampling reproduces the target distribution for any draft, a poor draft can only cost you throughput, never quality. That asymmetry — upside in speed, no downside in correctness — is what makes speculative decoding a default in modern inference stacks.