Speculative Decoding — Acceptance Rate and Optimal Draft Length

Why one target pass can check γ+1 tokens

Autoregressive decoding produces one token per forward pass, and at batch size one that pass is memory-bound, not compute-bound. To emit a single token the hardware must stream every weight of the model from memory into the arithmetic units: roughly 2N bytes for an N-parameter model in fp16, in order to perform roughly 2N FLOPs. That is an arithmetic intensity of about one FLOP per byte — far below what any modern CPU or GPU needs to saturate its multipliers, so the multipliers idle while the memory bus works.

Now feed the model γ+1 positions at once. The FLOPs multiply by γ+1; the bytes moved do not, because the weights are read once regardless. In the memory-bound regime the wall-clock cost is therefore almost unchanged. This is the justification for the 1 in the cost model below: one target pass over γ+1 positions costs about what one position costs. Speculation exists to spend those idle FLOPs.

The scheme: draft, then a modified rejection rule

Fix a position. The target model defines a next-token distribution p(x) over the vocabulary; the draft model defines q(x). Both are the final distributions you intend to sample from — after temperature, top-k and top-p have been applied. The rule is:

1. draw  x ~ q(x)
2. draw  u ~ Uniform(0, 1)
3. if u ≤ min(1, p(x)/q(x)):   accept x
4. else: draw x from the residual
     p′(x) = max(0, p(x) - q(x)) / Σ_y max(0, p(y) - q(y))

Read step 3 as: trust the draft exactly as far as it does not overclaim. If the target likes the proposed token at least as much as the draft did (p(x) ≥ q(x)), the ratio is at least 1 and the token is accepted outright. If the draft was over-confident, the token survives with probability p(x)/q(x) — the fraction of the draft’s enthusiasm the target actually endorses. Step 4 repairs the deficit, and it turns out to repair it exactly.

Correctness: the emitted token is distributed as p

Let x_0 be any token. It can arrive by two disjoint routes, so add their probabilities.

accept route:
  P(draw x_0, accept) = q(x_0) · min(1, p(x_0)/q(x_0))
                      = min(q(x_0), p(x_0))

β = P(accept) = Σ_x min(p(x), q(x))
1 - β         = Σ_x max(0, q(x) - p(x))
                = Σ_x max(0, p(x) - q(x))    [since Σp = Σq = 1]

reject route:
  P(reject, emit x_0) = (1 - β) · max(0, p(x_0)-q(x_0)) / (1 - β)
                      = max(0, p(x_0) - q(x_0))

total: min(p, q) + max(0, p - q) = p(x_0)

That last line is a two-case identity: if p(x_0) ≥ q(x_0) it reads q + (p - q) = p; otherwise p + 0 = p. The pivot is that the residual’s normalizer is exactly the rejection probability — true because both distributions sum to 1, forcing the mass the target holds in excess of the draft to equal the mass the draft holds in excess of the target. So the emitted token follows p identically, not approximately: speculative decoding is a lossless speedup.

The acceptance rate is one minus a divergence

The β that fell out of the proof is the per-token acceptance probability, conventionally written α, and it has a clean identity:

α = Σ_x min(p(x), q(x))
  = Σ_x [ p(x) + q(x) - |p(x) - q(x)| ] / 2
  = (1 + 1 - 2·TV(p, q)) / 2
  = 1 - TV(p, q),      TV(p, q) = ½ Σ_x |p(x) - q(x)|

So α is one minus the total variation distance between draft and target. A draft that matches the target exactly has TV = 0 and α = 1; a draft on disjoint support has TV = 1 and α = 0. Every gain in this technique is bought with distributional agreement, and TV is the exact currency. Note what α is not: not accuracy, not perplexity, not KL. A draft with mediocre perplexity can still yield a high α if it errs on exactly the positions the target also finds ambiguous.

Expected accepted tokens per verification step

Idealize α as constant and independent across the γ drafted positions. A step keeps a prefix — it stops at the first rejection — so it accepts k < γ tokens with probability α^k(1-α), and all γ with probability α^γ.

Every step also emits one bonus token. On rejection, the residual sample at that position is a real token. On full acceptance, the same target forward pass already produced p at position γ+1, so that token is free. Both branches yield exactly one extra, which collapses the expectation to a geometric sum:

E[tokens] = Σ_{k=0}^{γ} α^k = (1 - α^(γ+1)) / (1 - α)

Sanity checks: as α → 1 it tends to γ+1, the most a step can produce; at α = 0 it is 1, plain decoding. As γ → ∞ it saturates at 1/(1-α). Real acceptances are correlated — one rejection usually marks a genuinely hard position — so treat α as an empirical average.

From tokens per step to wall-clock speedup

Measure time in target forward passes. Let c be the cost of one draft pass as a fraction of one target pass — the cost ratio, typically 0.02 to 0.15. One speculative iteration runs the draft γ times sequentially plus the target once, costing γc + 1. Baseline decoding yields one token per unit cost, so the speedup is simply the ratio:

speedup(γ) = E[tokens] / (γc + 1)
             = (1 - α^(γ+1)) / [ (1 - α)(γc + 1) ]

Two forces pull against each other. The numerator grows with γ but with sharply diminishing returns, because an extra drafted token only pays off when all of its predecessors were accepted — a factor of α^γ. The denominator grows linearly. Linear cost eventually beats geometrically decaying benefit, so the speedup has an interior maximum rather than rising forever. And even at c = 0 nothing beats the ceiling 1/(1-α).

Solving for the optimal draft length

Treat γ as continuous and set the derivative to zero. Write a = α and L = -ln a > 0, so that d/dγ [1 - a^(γ+1)] = L·a^(γ+1). The quotient rule gives:

L·a^(γ+1)(cγ + 1) - (1 - a^(γ+1))·c = 0
⇒   a^(γ+1) · [ L(cγ + 1) + c ] = c

This is transcendental — no elementary closed form — but that barely matters, since γ must be a positive integer anyway and evaluating the speedup at γ = 1..12 settles it. The equation is still worth having, because it shows the direction of both derivatives: γ* rises with α (a more agreeable draft is worth trusting further) and falls as c rises (an expensive draft must pay for itself sooner). Those are the only two knobs the theory offers.

A worked example

Take a draft with α = 0.8 and c = 0.1, and tabulate:

The optimum is γ* = 6 at 2.47×; the stationarity condition puts the continuous optimum at γ ≈ 5.6, consistent. The striking feature is how flat the peak is — anything from 4 to 8 lands within 3% of the best, so precision tuning of γ is not where wins live. Now weaken the draft to α = 0.6 at the same c: the optimum moves to γ* = 3 and the speedup collapses to 1.67×. At α = 0.4 it is 1.30×. The ceiling 1/(1-α) says where the headroom is: 5× at 0.8, but only 2.5× at 0.6. Raising α dominates tuning γ.

What moves α: temperature and truncation

α = 1 - TV(p, q) is not a fixed property of a model pair. It moves with every sampling parameter, because temperature and truncation reshape p and q themselves before the rule ever sees them.

Temperature. At T = 0 both distributions are point masses and the rule degenerates: α is exactly the probability that the two models share an argmax, and acceptance is all-or-nothing per token. Raising T across the practical range lowers α, because it shifts mass off the shared top choice onto the tail — precisely where a small model and a large one disagree most. A toy two-token case with target logits (2, 0) and draft logits (1.5, 0) gives α = 1.00 at T = 0, 0.97 at 0.5, and 0.94 at 1.0. (Formally α → 1 again as T → ∞, since both tend to uniform, but over a 100k-token vocabulary that limit sits far outside any usable temperature.)

Truncation. Top-k and top-p are applied before the rule sees the pair, and the proof holds for whatever pair you hand it — output is exact with respect to the truncated target. The hazard is mismatched support: if the draft proposes a token the target’s nucleus excludes, then p(x) = 0, the accept probability is min(1, 0/q(x)) = 0, and the token is rejected with certainty however confident the draft was.