Speculative Decoding: The Accept-Reject Math of Faster Tokens

The uncomfortable truth about serving a large language model is that generating text is slow for a reason that has nothing to do with how much arithmetic the model does. Producing a token requires reading every weight of the model out of memory, and you must do it again for the next token, and the next, because each token depends on the one before it. The compute units sit mostly idle, starved for data. Speculative decoding is the observation that you do not have to guess the future one token at a time. If a smaller, cheaper model can propose several tokens at once, the large model can check all of them in a single pass, and a carefully constructed accept-reject rule lets you keep exactly the tokens the large model would have produced anyway. The speedup is real, it is lossless, and it is entirely governed by a handful of equations.

The tyranny of one token per pass

Fix notation first. A decoder-only transformer defines a next-token distribution p(x | context) over a vocabulary; sampling text means drawing a token, appending it, and repeating. Because token t+1 is conditioned on token t, the forward passes are strictly sequential: you cannot compute the distribution for position t+1 until you have committed the token at position t. Producing T tokens therefore costs T forward passes, and no amount of parallel hardware changes that dependency chain.

The second fact is what makes the first one painful. A single decoding forward pass is memory-bandwidth-bound, not compute-bound: to produce one token the accelerator must stream the entire weight matrix (and the key-value cache) from high-bandwidth memory through the arithmetic units, and the volume of data moved dwarfs the useful multiply-adds performed for a single position. The processor spends most of its time waiting on memory. Let the per-token target latency be t_p. Then naive generation of T tokens takes T * t_p, and that wall-clock time is dominated by memory traffic, not floating-point work.

This is the seam speculative decoding pries open. If the expensive weight read that a single target forward pass performs could be amortized over more than one token, latency would fall even though the total arithmetic rose. The question is how to get more than one correct token out of a single target pass without changing what the model would have said.

Draft, then verify

Introduce a second, much smaller model q that approximates the target p. Call p the target model and q the draft model. In one speculative iteration the draft model runs autoregressively and cheaply to propose a block of gamma candidate tokens x_1, ..., x_gamma, each sampled from q conditioned on the growing prefix. This costs gamma draft passes, but each is small.

Now the key move. Because the candidate tokens are already fixed, the target model can score all of them at once. A single target forward pass, batched over the gamma+1 positions, returns the target distribution p at every position: p(. | prefix), p(. | prefix, x_1), and so on up to p(. | prefix, x_1..x_gamma). In the memory-bound regime this parallel pass costs essentially the same as one ordinary single-token pass, because the weights are read from memory exactly once regardless of how many positions are scored. Verification is, to first order, free.

What remains is a rule that decides how many of the gamma proposed tokens to keep. If we keep them naively whenever the draft happened to agree with the target, we would bias the output distribution toward the draft model. The genius of the method is a rejection rule that keeps a random prefix of the proposals and yet leaves the final distribution provably identical to sampling from p directly.

The accept-reject rule

Walk the gamma proposals left to right. For candidate x_i, look up the draft probability q(x_i) and the target probability p(x_i), both conditioned on the same prefix. Accept x_i with probability min(1, p(x_i)/q(x_i)). Intuitively: if the target likes the token at least as much as the draft did (p >= q), accept it outright; if the target likes it less, accept it only in proportion to how much less.

On the first rejection at some position j, discard x_j and every proposal after it, and replace the rejected token by drawing a single token from the residual distribution, the normalized positive part of the gap between target and draft. If instead all gamma proposals are accepted, sample one bonus token directly from the target distribution at position gamma+1, which the same parallel pass already gave you for free. Either way every iteration commits at least one token and at most gamma+1.

This is a modified form of rejection sampling (Leviathan, Kalman & Matias, 2023): standard rejection sampling would discard and retry, wasting the target pass, whereas here the residual draw guarantees forward progress on every single iteration.

Why the output is exactly the target's

The claim that makes speculative decoding safe is that the token committed at each position is distributed exactly as p, the target distribution, no matter what the draft model q is. It is worth proving, because it is the entire reason you are allowed to use the technique in production without changing model behaviour.

Consider a single position and ask for the probability that the committed token equals some value x. There are two disjoint ways x can be committed: the draft proposed x and it was accepted, or the draft proposed something that was rejected and the residual resample landed on x. Sum the two.

The accept term is q(x) times min(1, p(x)/q(x)) = min(q(x), p(x)). The total rejection mass is the sum over all tokens x' of q(x') minus min(q(x'), p(x')), which equals the sum of max(0, q(x') - p(x')); by conservation of probability that quantity equals the residual normalizer, the sum of max(0, p(x') - q(x')). Multiplying the rejection mass by p_res(x) collapses the normalizer and leaves max(0, p(x) - q(x)). Adding the two contributions gives min(q(x), p(x)) + max(0, p(x) - q(x)) = p(x) in both cases p >= q and p < q. The draft model has vanished from the answer.

Two consequences follow. First, correctness does not depend on q being a good approximation of p; a terrible draft still yields exactly the target distribution. Second, the quality of q affects only speed, through how often its proposals are accepted. Speculative decoding trades no accuracy for its latency; the only thing at stake is how much you win.

The acceptance rate alpha and how many tokens you win

Define the acceptance rate alpha as the probability, averaged over the draft's own proposals, that a single drafted token is accepted. A short calculation shows alpha equals the sum over the vocabulary of min(p(x), q(x)), which in turn equals one minus the total variation distance between the two distributions. Total variation distance, TV(p, q), is half the sum of absolute differences of the probabilities; it is zero when the models agree everywhere and one when they are disjoint. So alpha = 1 - TV(p, q): the more the draft's distribution overlaps the target's, the higher the acceptance rate.

Treat the per-token acceptances as independent Bernoulli(alpha) trials, an approximation that is exact only if alpha is constant across positions. Let n be the number of accepted draft tokens before the first rejection, from 0 up to gamma. Then the probability of accepting at least k in a row is alpha^k, so the expected number of accepted draft tokens is the geometric sum of alpha^k for k from 1 to gamma. Every iteration also commits exactly one further token, the residual resample or the bonus draw, so the expected tokens produced per iteration is that sum plus one, which simplifies to a clean closed form.

Read the closed form as a saturating curve. As gamma grows, the numerator approaches one and the expected yield approaches 1/(1 - alpha), a ceiling set entirely by the acceptance rate. Doubling the block size past a point buys almost nothing because deep proposals are rarely all accepted.

The speedup equation and its optimum

Latency, not token count, is what you pay for. Let c be the cost ratio of one draft pass to one target pass, c = t_q / t_p, with c much less than one for a useful draft. One speculative iteration costs one target pass plus gamma draft passes, or t_p times (1 + gamma * c), and it yields the expected token count derived above. The baseline produces one token per t_p. Dividing yields the expected wall-clock improvement factor.

The equation exposes the whole trade-off in two competing terms. The numerator, the expected yield, rises with gamma but saturates at 1/(1 - alpha). The denominator, 1 + gamma * c, rises with gamma without bound. There is therefore an interior optimal block size gamma-star: increase gamma while the extra accepted tokens outpace the extra draft cost, and stop when they no longer do. The optimum grows as alpha approaches one (proposals go deeper before failing) and shrinks as c grows (each speculative token costs more).

This is why the two knobs that matter are the acceptance rate and the draft cost, and why they must be tuned together. A high-alpha draft that is expensive can lose to a slightly-lower-alpha draft that is far cheaper, because c multiplies gamma in the denominator.

Making the draft cheap

Because the draft cost c sits in the denominator of the speedup and is multiplied by gamma, shrinking it is often more valuable than nudging alpha. Two families of techniques do this. The first is architectural: use a genuinely small separate model, or a self-speculative scheme in which the target model's own early layers or a lightweight head produce the draft, so no second network is loaded.

The second is numerical, and it connects speculative decoding to weight quantization. Post-training quantization methods such as GPTQ (Frantar et al., 2022) and AWQ (Lin et al., 2023) compress a model's weights to low bit-width while controlling the error they introduce, which reduces the memory a forward pass must move and therefore its latency. Quantizing the draft model lowers t_q and hence c directly; because correctness is guaranteed regardless of the draft's fidelity, a quantized draft costs you only a little acceptance rate in exchange for a cheaper c. This is my own framing of the interaction, not a claim from those papers, but it follows from the speedup equation: the residual accept-reject rule makes the draft's approximation error free of correctness consequences, so aggressive draft compression is unusually safe.

The corresponding constraint is that the parallel verification pass must stay cheap, which holds only while decoding is memory-bandwidth-bound. Efficient serving systems that maximize memory utilization, such as the paged key-value cache of vLLM (Kwon et al., 2023), preserve that regime at the batch sizes where speculative decoding pays off.

When it breaks

The method is not free money, and the equations say exactly when it fails. First, low acceptance: if the draft approximates the target poorly, alpha is small, the expected yield collapses toward one token per iteration, and the speedup falls to 1/(1 + gamma * c), which is less than one. You have paid for gamma useless draft passes and gained nothing. A bad draft makes generation slower, not faster.

Second, an expensive draft: if c is not small, the gamma * c term dominates the denominator and the improvement evaporates even when acceptance is high. The draft must be a small fraction of the target's cost.

Third, and most subtly, the regime assumption. The entire argument that verification is free rests on decoding being memory-bandwidth-bound, so that scoring gamma+1 positions costs about the same as scoring one. At very large batch sizes decoding becomes compute-bound, the parallel verification pass costs roughly gamma times more, and the advantage disappears. Finally, alpha is not really constant: high-entropy positions accept less often, so the independent-Bernoulli estimate overstates the realized speedup, and you should always measure alpha on your own workload rather than trust the closed form.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

accepted, proposed = 0, 0
for prompt in eval_set:
    ctx = prompt
    while len(ctx) < max_len:
        draft = draft_model.sample_block(ctx, gamma)      # gamma cheap tokens
        p = target_model.score(ctx, draft)               # one parallel pass
        for i, x in enumerate(draft):
            proposed += 1
            if random() < min(1.0, p[i][x] / q_prob(draft, i, x)):
                accepted += 1
                ctx = ctx + [x]
            else:
                ctx = ctx + [sample_residual(p[i], q_at(draft, i))]
                break
        else:
            ctx = ctx + [sample(p[gamma])]               # bonus token
report('alpha_hat', accepted / proposed)

Glossary

Target model (p)

The large, accurate model whose output distribution the system must reproduce exactly.

Draft model (q)

A small, cheap model that proposes candidate tokens; its only job is to be accepted often.

Modified rejection sampling

An accept-reject rule that keeps a prefix of proposals and resamples the first rejection from the residual, guaranteeing progress and exact target-distributed output.

Residual distribution

The normalized positive part of p minus q, from which a rejected token is redrawn.

Acceptance rate (alpha)

The expected probability that a drafted token is accepted; equals one minus the total variation distance between draft and target.

Total variation distance

Half the sum of absolute differences between two probability distributions; zero when identical, one when disjoint.

Memory-bandwidth-bound

A regime in which latency is set by moving weights from memory, not by arithmetic, so scoring several positions in one pass costs about the same as scoring one.

References

1. Leviathan, Kalman & Matias (2023), Fast Inference from Transformers via Speculative Decoding (ICML)
2. Vaswani et al. (2017), Attention Is All You Need (NeurIPS)
3. Kwon et al. (2023), Efficient Memory Management for LLM Serving with PagedAttention (SOSP)
4. Frantar et al. (2022), GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers
5. Lin et al. (2023), AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration