Speculative Decoding: Fast LLM Inference Without Quality Loss › The Verification Procedure

The verification procedure is the mathematical heart of speculative decoding. It determines which draft tokens to accept and how to generate corrections when tokens are rejected. We can construct an acceptance criterion that exactly preserves the target model's output distribution while maximizing the number of accepted tokens. This is not an approximation or heuristic: it is a mathematically guaranteed property that makes speculative decoding a lossless acceleration technique.

The mathematical result that makes speculative decoding work is called the acceptance-rejection sampling theorem. In classical statistics, acceptance-rejection sampling is a technique for drawing samples from a target distribution $p$ when you can only sample easily from a proposal distribution $q$. You draw a sample from $q$, then accept it with probability proportional to $p/q$. The accepted samples are guaranteed to be distributed according to $p$. Speculative decoding applies this classical idea to language model token generation, with the draft model as the proposal distribution and the target model as the target distribution.

For each draft token, we compare the draft model's probability $q(x)$ with the target model's probability $p(x)$. We want to accept as many draft tokens as possible while ensuring the accepted tokens are distributed according to $p$, not $q$. The acceptance probability that achieves this is:

$$\alpha(x) = \min\left(1, \frac{p(x)}{q(x)}\right)$$

where:

• $\alpha(x)$: the probability of accepting candidate token $x$ as a valid sample from the target distribution
• $p(x)$: the probability assigned to token $x$ by the target model given the current context
• $q(x)$: the probability assigned to token $x$ by the draft model given the same context
• The minimum ensures the acceptance probability never exceeds 1, since probabilities must be at most certain

This formula has an elegant interpretation. When $p(x) \geq q(x)$ (the target model likes this token at least as much as the draft model), we always accept. This makes sense: the target model considers this token at least as likely as the draft model proposed, so accepting it only makes our output distribution more aligned with the target. When $p(x) < q(x)$ (the draft model overestimated this token's likelihood), we accept with probability equal to how much it overestimated. The more the draft model overestimated a token, the lower our acceptance probability, preventing us from biasing our output toward tokens the draft model unfairly favored.

The results show that we accept with certainty when the target model prefers a token more than the draft model does (probability 1.00), but only probabilistically when the draft model is overconfident. The "Draft overestimates" scenario, where the draft gives 20% probability but the target gives only 5%, yields a 25% acceptance probability. This means the draft model proposed this token 4x more often than the target would have wanted, so we discard it 75% of the time to prevent it from appearing 4x too frequently in our output.

When a draft token is rejected, we need to sample a correction token. Simply sampling from the target model's distribution at that position would bias the output: we would undersample tokens that were already accepted under the acceptance criterion and oversample tokens that were never drafted. The correction distribution must account precisely for the tokens that have already been "covered" by the acceptance procedure.

To understand why, think about what the acceptance step has already done. Imagine the target distribution assigns 30% probability to token A and 20% to token B. The draft distribution assigns 10% to A and 25% to B. In the acceptance step, token A (if drafted) would be accepted with probability 1.0 (since $p/q = 3.0 > 1$), and token B would be accepted with probability $0.20/0.25 = 0.80$. So token A is well-covered, but token B is slightly over-proposed. If we reject and then sample from $p$ directly, we would add another 30% chance of token A on top of the already-accepted A, distorting the distribution.

The correction distribution adjusts for the tokens that would have been accepted through drafting, sampling only the "residual" probability mass:

$$p_{\text{correction}}(x) = \frac{\max(0,\, p(x) - q(x))}{\sum_{x'} \max(0,\, p(x') - q(x'))}$$

where:

• $p_{\text{correction}}(x)$: the adjusted probability of sampling token $x$ as a correction after a rejection
• $p(x) - q(x)$: the difference between target and draft probabilities for token $x$
• $\max(0, \dots)$: selects only tokens where the target assigns more probability than the draft (the "under-sampled" tokens)
• $\sum_{x'} \max(0,\, p(x') - q(x'))$: the normalization constant ensuring the correction distribution sums to 1

This distribution has a clear interpretation. It samples only from tokens where the target model assigns more probability than the draft model proposed. These are precisely the tokens that the draft model under-represented. By sampling from this residual distribution, we fill in the probability mass that was missed by the draft model's proposal. This keeps the combined output of accepted drafts and corrections matches the target distribution exactly. The formal proof of this property shows that the marginal distribution of each generated token equals $p(x)$, even after the acceptance-rejection process.

Notice how the correction distribution emphasizes token 0 and token 2, where the target model assigns more probability than the draft. Token 1 and token 3 receive zero correction probability because the draft model already over-sampled them. By combining accepted draft tokens with correction samples, we ensure the overall distribution perfectly matches what the target model would have produced through standard autoregressive generation. This is not approximately right: it is mathematically exact.

During verification, we process draft tokens sequentially and stop at the first rejection. If draft token 3 is rejected, we do not verify tokens 4 and beyond. This is because the correction at position 3 changes the context, invalidating the draft model's predictions for subsequent positions. The draft model generated tokens 4 and beyond assuming token 3 would be accepted as-is. Once we substitute a correction token, those subsequent predictions become irrelevant because they were conditioned on a different context.

This sequential processing means the number of accepted tokens follows a geometric-like distribution. With acceptance rate $\gamma$ per token, the expected total number of tokens generated per round combines the always-present correction token with the expected accepted drafts:

$$\begin{aligned} \mathbb{E}[\text{tokens}] &= 1 + \sum_{k=1}^{K} \gamma^k && \text{(correction token + expected accepted drafts)} \\ &= \sum_{k=0}^{K} \gamma^k && \text{(combine into single series)} \\ &= \frac{1 - \gamma^{K+1}}{1 - \gamma} && \text{(geometric series closed form)} \end{aligned}$$

where:

• $\mathbb{E}[\text{tokens}]$: the expected number of tokens produced per round (drafts plus correction)
• $1$: the correction token, which is always generated regardless of how many drafts are accepted
• $\sum_{k=1}^{K} \gamma^k$: the expected number of accepted draft tokens, summed over each position
• $\gamma$: the probability of accepting a single draft token (the acceptance rate)
• $K$: the number of draft tokens attempted per round

This formula sums the always-present correction token with the geometric series of accepted drafts. The geometric series arises because each subsequent draft token can only be accepted if all previous draft tokens were also accepted. The probability of accepting the first two drafts is $\gamma^2$, the first three is $\gamma^3$, and so on. This cumulative structure explains why acceptance rate has such a dramatic effect on speedup: small improvements in $\gamma$ compound across multiple positions. Moving from $\gamma = 0.7$ to $\gamma = 0.8$ with $K = 5$ increases expected tokens from 3.08 to 3.93, a 28% improvement in throughput from a 14% improvement in acceptance rate.