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.

Advertisement

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.

Advertisement

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-α).