Speculative DecodingOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Speculative Decoding

Each decode step of a large model reads every weight from HBM to produce one token, and most tokens ("the", "of", closing brackets, boilerplate) don't need 70B parameters to predict. Speculative decoding lets a small draft model propose several tokens cheaply, then has the large target model verify all of them in a single forward pass. Accepted tokens cost one target step for many tokens; rejected ones fall back to normal decoding. The remarkable part: with the right acceptance rule, the output distribution is mathematically identical to sampling from the target model alone.

The algorithm

One cycle of speculative decoding with draft model qq, target model pp, and lookahead kk:

  1. Draft: run the small model autoregressively for kk steps, sampling proposals x1,…,xkx_1, \ldots, x_k with probabilities q(xi∣prefix,x<i)q(x_i \mid \text{prefix}, x_{<i}).
  2. Verify: run the target model once on the prefix plus all kk proposals. Because a transformer scores every position in parallel, this single pass yields p(xi∣prefix,x<i)p(x_i \mid \text{prefix}, x_{<i}) for all ii — plus the distribution for position k+1k+1.
  3. Accept/reject left to right. For each proposal xix_i:
    • accept with probability min⁡ ⁣(1,p(xi)q(xi))\min\!\left(1, \dfrac{p(x_i)}{q(x_i)}\right);
    • on the first rejection, discard xix_i and everything after it, and sample the replacement token from the residual distribution   p′(x)=max⁡(0, p(x)−q(x))∑x′max⁡(0, p(x′)−q(x′))\;p'(x) = \dfrac{\max(0,\, p(x) - q(x))}{\sum_{x'} \max(0,\, p(x') - q(x'))}.
  4. Bonus token: if all kk proposals are accepted, sample token k+1k+1 directly from the target's already-computed distribution — free.

Each cycle therefore emits between 11 (immediate rejection, resample) and k+1k+1 (all accepted + bonus) tokens for one target forward pass.

Why the output distribution is exactly pp

The accept/resample rule is a form of rejection sampling. For any token xx, the probability it is emitted at a given position is

q(x)min⁡ ⁣(1,p(x)q(x))⏟proposed and accepted  +  (∑x′q(x′)[1−min⁡ ⁣(1,p(x′)q(x′))])⋅p′(x)⏟some proposal rejected, then x resampled\underbrace{q(x)\min\!\left(1, \frac{p(x)}{q(x)}\right)}_{\text{proposed and accepted}} \;+\; \underbrace{\left(\textstyle\sum_{x'} q(x')\left[1 - \min\!\left(1, \frac{p(x')}{q(x')}\right)\right]\right) \cdot p'(x)}_{\text{some proposal rejected, then } x \text{ resampled}}

The first term equals min⁡(q(x),p(x))\min(q(x), p(x)). The rejection mass sums to ∑x′max⁡(0,q(x′)−p(x′))=∑x′max⁡(0,p(x′)−q(x′))\sum_{x'} \max(0, q(x') - p(x')) = \sum_{x'} \max(0, p(x') - q(x')) (both equal half the total variation distance), which cancels the residual's normalizer, so the second term equals max⁡(0,p(x)−q(x))\max(0, p(x) - q(x)). Their sum is exactly p(x)p(x).

No approximation, no distribution shift — a worse draft model only makes speculative decoding slower, never wrong. This is why it's classed as a quality-neutral lever in the inference-optimization decision tree.

Worked trace

Vocabulary {the,cat,sat,mat}\{\text{the}, \text{cat}, \text{sat}, \text{mat}\}, lookahead k=3k = 3. The draft proposes the → cat → sat, and the target's verification pass returns:

PositionProposal xix_iq(xi)q(x_i)p(xi)p(x_i)min⁡(1,p/q)\min(1, p/q)Draw u∼U(0,1)u \sim U(0,1)Outcome
1the0.800.720.900.41✅ accept
2cat0.600.661.00—✅ accept
3sat0.700.140.200.55❌ reject

Position 3 rejects, so we resample from the residual there. Suppose at position 3: p=(0.10,0.06,0.14,0.70)p = (0.10, 0.06, 0.14, 0.70) and q=(0.05,0.15,0.70,0.10)q = (0.05, 0.15, 0.70, 0.10) over (the, cat, sat, mat). Then max⁡(0,p−q)=(0.05,0,0,0.60)\max(0, p - q) = (0.05, 0, 0, 0.60), which normalizes to p′=(0.077,0,0,0.923)p' = (0.077, 0, 0, 0.923) — the resample almost surely emits mat, the token the draft badly under-proposed. The cycle emits the, cat, mat: 3 tokens for one target pass instead of three.

Watch it run

The cycle above, decision by decision, and then the check that matters:

Speculative decoding — draft, verify, and the rule that keeps it exact

1/7

A 4-token vocabulary and lookahead k = 3. The small draft model proposes "the → cat → sat" for a few percent of the cost of one target step, and the target then scores all three positions in a **single** forward pass — a transformer computes every position in parallel, so verifying 3 tokens costs the same as generating 1.

python
1def cycle(prefix, draft, target, k):
2 xs = draft.sample(prefix, k) # k cheap steps
3 p = target(prefix, xs) # ONE big pass
4 out = []
5 for i, x in enumerate(xs):
6 if uniform() < min(1, p[i][x] / q[i][x]):
7 out.append(x) # accept
8 continue
9 # reject: resample the residual
10 resid = maximum(0, p[i] - q[i])
11 out.append(sample(resid / resid.sum()))
12 return out # discard the rest
13 # all accepted -> bonus token, free
14 out.append(sample(p[k]))
15 return out
state
draft proposals
theq=0.8
catq=0.6
satq=0.7

The bottleneck in decoding is memory bandwidth, not arithmetic: one target step reads every weight from HBM to produce one token. Producing several tokens per read is the entire idea.

One draft-and-verify cycle on the worked example above: two proposals accepted, one rejected, and a resample from the residual max(0, p − q) that lands on the token the draft under-proposed. The final step is the important one — 200 000 emissions under a well-matched draft and a deliberately terrible one, both reproducing the target distribution to four decimal places. A bad draft costs speed and nothing else.

What to notice as you step:

  • Under-proposing is free. At position 2 the target likes "cat" more than the draft did, so min⁡(1,p/q)=1\min(1, p/q) = 1 and no random number is even drawn. Only over-confidence by the draft can cause a rejection.
  • A rejection discards everything after it, because those proposals were conditioned on a token that will not be emitted. This is why acceptance rate compounds, and why lookahead kk has diminishing returns.
  • The residual is a correction, not a fallback. max⁡(0,p−q)\max(0, p - q) puts its mass exactly where the draft was under-confident, which is what makes the emitted distribution come out equal to pp rather than merely close to it.
  • The last step verifies that claim empirically: 200 000 emissions under a well-matched draft (94% acceptance) and a deliberately terrible one (26%), both reproducing pp to four decimal places. A worse draft costs throughput and nothing else.

Expected speedup

Let α\alpha be the average per-token acceptance probability (empirically α≈\alpha \approx 0.7–0.9 for a well-matched draft). The expected number of tokens emitted per cycle is the expectation of a truncated geometric plus the bonus token:

E[tokens/cycle]=1−αk+11−α\mathbb{E}[\text{tokens/cycle}] = \frac{1 - \alpha^{k+1}}{1 - \alpha}

If the draft costs a fraction c≪1c \ll 1 of a target step, the wall-clock speedup per emitted token is

speedup=1−αk+1(1−α) (1+ck)\text{speedup} = \frac{1 - \alpha^{k+1}}{(1 - \alpha)\,(1 + ck)}

At α=0.8\alpha = 0.8, k=4k = 4, c=0.05c = 0.05: E[tokens]≈3.36\mathbb{E}[\text{tokens}] \approx 3.36 per cycle and speedup ≈2.8×\approx 2.8\times. Diminishing returns in kk are steep — αk\alpha^{k} decays fast, so kk beyond ~4–8 mostly burns draft compute. Note the acceptance rate also depends on sampling temperature: at low temperature pp concentrates, agreement rises, and speculation wins more.

Variants

VariantDraft sourceTrade-off
Draft–target (classic)Separate small model (same tokenizer)Best acceptance; must host a second model
MedusaExtra decoding heads on the target itselfNo second model; heads need finetuning; tree-verifies multiple branches
EAGLELightweight head predicting from the target's hidden stateHigher acceptance than Medusa at similar cost; current default in vLLM/TRT-LLM
Prompt lookup / n-gramCopy matching spans from the promptFree; only wins on extractive/repetitive tasks (RAG quotes, code edits)
Self-speculativeTarget with layers skippedNo extra weights; modest acceptance

When it wins and loses

  • ✅ Templated, predictable text (support answers, code boilerplate, JSON) acceptance rates soar.
  • ✅ Low-batch, latency-sensitive serving — spare compute exists between bandwidth-bound decode steps; verification rides it free.
  • ❌ Large batches — the GPU is already compute-saturated, and verifying kk positions per sequence competes with other requests; the speedup shrinks toward zero.
  • ❌ High-entropy generation (creative writing at high temperature) — acceptance drops and cycles waste draft work.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Referenced by
Speculative DecodingInference Optimization & …Optimizing LLM InferenceDecoding & Sampling Strat…