Speculative decoding, annotated

2.1 Overview · original

The three steps

Reading it: start at the top with the text generated so far. The small draft model proposes γ tokens (γ is a setting, typically 3 to 7). The big target model then evaluates every drafted position at once, in a single parallel pass, the same way it processes a prompt. The accepted drafts are kept, the first rejected one is replaced by a corrected token, and the loop repeats from the new end of the text. Every round produces at least one token, so it can never be slower in big-model runs than ordinary decoding.

2.2 Standardized sampling · original

Everyday picture: greedy decoding, temperature, top-k and top-p look like different algorithms, but each is really “adjust the probability list, then draw from it”. Greedy, for example, sets every probability except the largest to zero. So the paper only needs to handle one case, drawing from a probability list, and it works for all of them. Throughout, p is the big model's adjusted list and q is the small model's.

2.3 Speculative sampling · original

Everyday picture

How can guesses from a sloppier model ever give exactly the big model's randomness? Think of the draft's probabilities as a proposal. Wherever the draft is not over-enthusiastic about a token (q ≤ p), take its guess as is. Where it is over-enthusiastic (q > p), accept its guess only part of the time, just enough to bring that token down to the right rate. The probability freed up by those rejections is then handed to exactly the tokens the draft under-rated.

In words: “take the draft's token if the big model likes it at least as much; if the big model likes it less, keep it only with probability p over q; when you reject, draw from what's left of the big model's list after subtracting the draft's.”

With the numbers: three possible next words, target p = (cat 0.5, dog 0.3, fish 0.2), draft q = (0.6, 0.2, 0.2). If the draft says “cat” (q 0.6 > p 0.5), keep it with probability 0.5 / 0.6 = 0.833. If it says “dog” or “fish”, always keep it. When a “cat” is rejected (probability 0.6 × 0.167 = 0.1), redraw from max(0, p − q) = (0, 0.1, 0), normalized: “dog” for certain. Final chances: cat 0.6 × 0.833 = 0.5, dog 0.2 + 0.1 = 0.3, fish 0.2: exactly p.

In Python:

# the target model
p = {"cat": 0.5, "dog": 0.3, "fish": 0.2}
# the draft model
q = {"cat": 0.6, "dog": 0.2, "fish": 0.2}
# min(1, p(x) / q(x))
keep = {x: min(1, p[x] / q[x]) for x in p}
round(keep["cat"], 3)  # → 0.833
# 0.6 × 0.167
rejected = sum(q[x] * (1 - keep[x]) for x in p)
round(rejected, 1)  # → 0.1
# max(0, p(x) − q(x))
left = {x: max(0, p[x] - q[x]) for x in p}
# norm(...)
p_prime = {x: left[x] / sum(left.values()) for x in p}
p_prime["dog"]  # → 1.0
final = {x: round(q[x] * keep[x] + rejected * p_prime[x], 3) for x in p}
# exactly p
final  # → {'cat': 0.5, 'dog': 0.3, 'fish': 0.2}

Try it: draft, verify, repeat

Reading it: the two models here are tiny illustrative “bigram” models over an eight-word vocabulary (each next word depends only on the previous word), with the draft model deliberately a bit off. Press “Run one round”: the top line shows that round. Green drafts were accepted by the rule above, a struck-through orange draft was rejected, and the blue token is the one the big model supplied (a correction after a rejection, or a bonus token when every draft was accepted). The line below accumulates the generated text, and the counter compares big-model runs with tokens produced. With these models the draft agrees about 85 to 100% of the time, so each big-model run yields several tokens. Raise γ and watch tokens per run climb, then level off as long drafts start getting rejected part-way.

Reading it: this runs the rule from the equation 10,000 times on the worked example. For each word, the first bar is the target model's probability and the second is how often the rule actually produced that word. They match to within the random wobble of 10,000 draws, even though every sample started as a guess from the wrong distribution q. That is the paper's guarantee, made visible.

Why it matters today

This rule is what separates speculative sampling from simply “accept the draft if the big model's top choice agrees”, which only works for greedy decoding. Because the distribution is exactly preserved, the speed-up is free of any quality trade-off, and serving systems can switch it on without re-running evaluations.

3.1 and 3.2 Tokens per call, and the acceptance rate α · original

Everyday picture

How good is the assistant? Measure how much the two models' probability lists overlap. If they agree perfectly, every draft is kept; if they never overlap, none is. That overlap is the acceptance rate.

In words: “the chance a draft token survives is the total overlap of the two probability lists; averaged over the text it is α; and a round with γ drafts then produces 1 + α + α² + … + α^γ tokens on average.”

With the numbers: for the worked example, β = min(0.5, 0.6) + min(0.3, 0.2) + min(0.2, 0.2) = 0.5 + 0.2 + 0.2 = 0.9. With α = 0.8 and γ = 5: (1 − 0.8⁶) / (1 − 0.8) = (1 − 0.262) / 0.2 = 3.69 tokens per big-model run.

In Python:

p, q = [0.5, 0.3, 0.2], [0.6, 0.2, 0.2]
# β = Σ_x min(p(x), q(x))
beta = sum(min(px, qx) for px, qx in zip(p, q))
round(beta, 1)  # → 0.9
alpha, gamma = 0.8, 5
round(alpha ** (gamma + 1), 3)  # → 0.262
# E(#tokens)
tokens = (1 - alpha ** (gamma + 1)) / (1 - alpha)
round(tokens, 2)  # → 3.69

3.3 to 3.5 Speed, extra work, and choosing γ · original

Everyday picture

The assistant isn't free: drafting γ tokens takes γ small-model runs. And rejected drafts mean the big model did some checking for nothing. So the real questions are: how much faster in wall-clock time, and how much extra arithmetic?

In words: “the speed-up is the tokens per round divided by the cost of a round (one big run plus γ small runs); the extra arithmetic is the work of a round divided by the tokens it yields.”

With the numbers: with α = 0.8, γ = 5 and a draft that costs 5% of the big model (c = 0.05): 3.69 / (5 × 0.05 + 1) = 3.69 / 1.25 = 2.95× faster. With a free draft (c = 0), it is 3.69× faster at the price of 1.63× more arithmetic.

In Python:

alpha, gamma, c = 0.8, 5, 0.05
speedup = (1 - alpha ** (gamma + 1)) / ((1 - alpha) * (gamma * c + 1))
round(speedup, 2)  # → 2.95
# a free draft
c, c_hat = 0, 0
round((1 - alpha ** (gamma + 1)) / ((1 - alpha) * (gamma * c + 1)), 2)  # → 3.69
extra = (1 - alpha) * (gamma * c_hat + gamma + 1) / (1 - alpha ** (gamma + 1))
# times more arithmetic
round(extra, 2)  # → 1.63

Reading it: the x-axis is γ, the number of drafts per round; the curves show the predicted wall-clock speed-up and the extra arithmetic for the α and c chosen on the sliders. The speed-up curve rises, peaks and then slowly falls: past the peak, extra drafts are usually rejected anyway and just cost small-model time. The readout names the best γ. Try a poor draft (α = 0.4): the best γ is small and the gain modest. Try a great one (α = 0.9, c near 0): long drafts pay off handsomely, but the extra-arithmetic curve keeps climbing, which matters if the hardware has no idle compute to spare.

The formulas above reproduce every row. The paper also notes that memory traffic goes down, not up: the big model's weights and KV cache are read once per round instead of once per token, which is exactly why the trick works on memory-bound hardware.

3.6 Draft models · original

Everyday picture: any guesser works, and even a bad one helps a little. The paper's best drafts were existing small models from the same family, about two orders of magnitude smaller than the target. Remarkably, even a simple bigram model (predicting each word from the previous one alone) reached α = 0.2 on English-to-German translation, which with c ≈ 0 still gives a 1.25× speed-up. Draft models could also be trained on purpose, for example by distilling the big model.