It's Not “Accept If They Match”: The min(1, p/q) Rule That Makes Speculative Decoding Provably Lossless

Speculative decoding has a reputation problem: it sounds like a quality tradeoff. A small model guesses tokens, a big model spot-checks them — surely something is lost? Nothing is. The original paper proves the output distribution is exactly the target model's, for any draft model, even a bigram table. The interesting part is the three-line rejection rule that makes this true, and the equally interesting part is the regime where the whole trick quietly stops paying.

The idle compute that makes drafting free

Autoregressive decode generates one token per forward pass, and each forward pass streams the model's weights through memory. At small batch sizes the accelerator is memory-bandwidth-bound: the arithmetic units sit mostly idle while weights are read. That idleness is the budget speculative decoding spends.

The scheme, introduced by Leviathan, Kalman, and Matias ("Fast Inference from Transformers via Speculative Decoding", ICML 2023) and concurrently by Chen et al. at DeepMind, works like this:

1. A cheap draft model q autoregressively proposes γ tokens (γ is small — 3 to 5 in practice).
2. The target model p runs once on all γ positions in parallel — costing roughly the same wall time as generating a single token, because the weight reads dominate.
3. Draft tokens are accepted left to right until the first rejection; the rejection position gets a corrected token for free.

So each target-model pass yields between 1 and γ+1 tokens instead of exactly one. The open question is step 3: what does "accept" mean, such that the result is indistinguishable from just sampling the target model?

The rule: accept with probability min(1, p/q)

Here is the entire mechanism. The draft samples token x from its distribution q(x). Then:

• If q(x) ≤ p(x), accept the token unconditionally.
• If q(x) > p(x), accept with probability p(x)/q(x) — i.e., reject with probability 1 − p(x)/q(x).
• On rejection, resample the token from the residual distribution:

p'(x) = norm(max(0, p(x) − q(x)))

The intuition: wherever the draft is overconfident (q > p), you thin out its samples by exactly the overconfidence ratio. Wherever the draft is underconfident (q < p), its samples are all kept — but they arrive too rarely, and the residual distribution max(0, p − q) is precisely the probability mass the draft under-delivers. Rejections are routed there. Sum the two paths and every token comes out with probability exactly p(x). The paper proves this as a theorem: tokens produced by speculative sampling are distributed identically to tokens sampled from p alone, regardless of what q is.

Two corollaries worth internalizing:

• A rejection is not a wasted step. The resample from p' produces a valid token from the target distribution, so every iteration emits at least one token. The worst case degenerates to (slightly slower than) ordinary decoding, never to garbage.
• At temperature 0 the rule collapses to exact match. With greedy decoding p is one-hot, so p(x)/q(x) is either ≥1 (draft picked the argmax → accept) or 0 (reject, and the residual norm(max(0, p−q)) is just the argmax). The "check if the tokens match" description you often hear is the greedy special case, not the algorithm.

The algebra that decides whether you win

Define α = E[min(p, q)] — the expected acceptance rate, which is 1 minus a divergence between draft and target. The number of tokens per iteration is a capped geometric variable:

E[#tokens per target pass] = (1 − α^(γ+1)) / (1 − α)

With c the ratio of draft-model to target-model runtime, the expected wall-time improvement is:

speedup = (1 − α^(γ+1)) / ((1 − α)(γc + 1))

and the paper shows that whenever α > c there is some γ that yields an improvement of at least (1+α)/(1+c). That inequality is the whole business case: the draft must agree with the target more often than it costs, proportionally, to run.

Measured α values from the paper (English→German translation, T5-XXL as target) show how forgiving this is:

Note the temperature column: sampling at temperature 1 costs T5-small 13 points of acceptance versus greedy. Flatter target distributions are harder to guess, so your production speedup depends on your sampling settings, not just your model pair. End to end, the paper reports 2–3× acceleration on T5-XXL over the standard T5X implementation, with no retraining and no architecture changes.

What it looks like at 70B scale

The DeepMind paper ("Accelerating Large Language Model Decoding with Speculative Sampling") ran this on Chinchilla 70B serving on 16 TPU v4s, with a purpose-built 4B draft model — same tokenizer, but 8 layers instead of Chinchilla's 80, chosen for sampling latency: 1.8 ms/token for the draft versus 14.1 ms/token for the target.

With K=4 speculated tokens:

• XSum (summarization): 7.52 ms/token with nucleus sampling (1.92×), 7.00 ms/token greedy (2.01×).
• HumanEval (code): 5.73 ms/token with nucleus sampling — 2.46×, which the paper notes exceeds what the memory-bandwidth ceiling alone would predict, since multiple real tokens now come out of each pass.

The domain gap is the lesson: acceptance rate depends on the application and the decoding method. Code is locally predictable — brackets, indentation, boilerplate — so drafts survive longer. Free-form prose rejects more. The same deployment gets different speedups per workload, and even the optimal K shifts (XSum's latency minimum was at K=3, not 4).

Where the free lunch ends

The speedup is bought with extra arithmetic — the draft's γ passes plus the target's parallel verification of tokens that may be thrown away. The paper gives the expected increase in total operations as (1−α)(γĉ+γ+1)/(1−α^(γ+1)) and is explicit that the method "is not helpful for configurations where additional computation resources are not available."

That is exactly the high-batch serving regime. Continuous batching fills the idle arithmetic units with other users' requests; once the accelerator is compute-bound, speculative decoding's verification passes compete with real work instead of using slack. vLLM's current documentation encodes this directly in its method-selection guidance: model-based speculators (EAGLE, MTP, draft models, PARD, MLP speculators) are rated high gain at low-QPS, latency-focused serving, dropping to medium at high QPS, while the model-free options (n-gram, suffix decoding) offer low-to-medium gains but cost almost nothing to try:

vllm serve <target-model> \
  --speculative-config '{
    "method": "draft_model",
    "model": "<draft-model>",
    "num_speculative_tokens": 5
  }'

One last honesty note, straight from vLLM's docs: the sampling is theoretically lossless, and vLLM validates its rejection sampler against the target distribution — but floating-point error can cause slight output variations, and changing batch size already perturbs logprobs in ordinary batched inference. Speculative decoding preserves the distribution; it does not make a nondeterministic serving stack deterministic.

The mental model to keep: speculative decoding is an arbitrage on the gap between memory bandwidth and compute. The rejection rule guarantees you never pay in quality; α, γ, and your batch size decide whether you get paid at all.

References

• Leviathan, Kalman & Matias — Fast Inference from Transformers via Speculative Decoding (ICML 2023)
• Chen et al. (DeepMind) — Accelerating Large Language Model Decoding with Speculative Sampling
• vLLM Documentation — Speculative Decoding

speculative-decodingllm-inferencerejection-samplingvllmgpu