Speculative Decoding Math: Algorithms & Speedup Limits › Worked Example: Manual Token Verification

Before diving into expected speedup analysis, let's work through a complete numerical example of the acceptance criterion to build concrete intuition. We will use a tiny vocabulary of five tokens and trace through the entire verification process step by step.

Suppose our vocabulary is $\{A, B, C, D, E\}$ and the current token position has the following distributions from each model:

The draft model overestimates token B's probability (0.50 vs 0.30) and underestimates token A's probability (0.20 vs 0.40). All other tokens match exactly.

Scenario 1: Draft proposes token A. We compute $\alpha(A) = \min(1, 0.40/0.20) = \min(1, 2.0) = 1.0$. We draw $u \sim \text{Uniform}(0,1)$ and since $\alpha(A) = 1.0$, we always accept. Token A is used as the next token.

Scenario 2: Draft proposes token B. We compute $\alpha(B) = \min(1, 0.30/0.50) = \min(1, 0.60) = 0.60$. We draw $u \sim \text{Uniform}(0,1)$. Suppose $u = 0.72 > 0.60$, so we reject. Now we must sample from the residual distribution.

To compute the residual distribution, we calculate $\max(0, p(x) - q(x))$ for each token:

• $A$: $\max(0, 0.40 - 0.20) = 0.20$
• $B$: $\max(0, 0.30 - 0.50) = 0$
• $C$: $\max(0, 0.15 - 0.15) = 0$
• $D$: $\max(0, 0.10 - 0.10) = 0$
• $E$: $\max(0, 0.05 - 0.05) = 0$

The unnormalized residual concentrates all mass on token A with value 0.20. The normalizing constant is $Z = 0.20$, so $p_{\text{resid}}(A) = 0.20/0.20 = 1.0$. When the draft proposes B and we reject, we always sample A from the residual.

Verification that the combined procedure matches $p(x)$. Let's check token A's total probability:

The probability of creating A through acceptance: draft proposes A with probability $q(A) = 0.20$ and we always accept, contributing $0.20$.

The probability of creating A through rejection: draft proposes B with probability $q(B) = 0.50$ and we reject with probability $1 - 0.60 = 0.40$, then sample A from residual with probability 1.0, contributing $0.50 \times 0.40 \times 1.0 = 0.20$.

Total probability for A: $0.20 + 0.20 = 0.40 = p(A)$. Correct.

The probability of creating B: draft proposes B with probability $q(B) = 0.50$ and we accept with probability $0.60$, contributing $0.50 \times 0.60 = 0.30 = p(B)$. Correct.

Tokens C, D, E: the draft proposes each with the same probability as the target, so they are always accepted and match the target distribution exactly.

This worked example demonstrates concretely why the residual distribution is necessary. When we reject B (because the draft overproposed it), we do not simply resample from the draft. We sample from the corrected residual that redirects all the "saved" probability mass to tokens the draft underproposed. In this case, every rejection of B leads to an acceptance of A, which is exactly what we need to bring A's total probability from 0.20 (what the draft alone would give) up to 0.40 (what the target requires).