Speculative Decoding: The Algebra and the Proof

TL;DR: A draft proposes $\gamma$ tokens, the target checks all of them in one forward pass, and with per-token acceptance $\alpha$ the step emits $\frac{1-\alpha^{\gamma+1}}{1-\alpha}$ tokens: 2.53 at $\alpha = 0.7, \gamma = 3$, which is 1.95x faster when a draft step costs a tenth of a target step. The accept rule $\min(1, p/q)$ plus resampling from $(p-q)_+$ makes the output exactly the target's distribution, and the whole trick runs on compute that a bandwidth-bound decode step leaves idle, so it fades once the batch fills that compute.

The step, mechanically

Small-batch decode linear layers have arithmetic capacity to spare. On an H100 SXM in BF16 the dense ridge is 989 TFLOP/s / 3.35 TB/s = 295 FLOPs per byte, while batch-1 linear layers do roughly 1 FLOP per weight byte. Speculation feeds several candidate tokens through the target together, amortizing a weight read over the accepted prefix. Attention, proposal generation and verification still cost time; unused arithmetic alone does not guarantee a speedup.

Every step emits at least one token from the target, either the correction at the first rejection or the bonus token. That floor is why a terrible draft costs time but never correctness.

The algebra

Let $\alpha_j$ be the probability of accepting position $j$ conditional on accepting every earlier draft position. The general expectation is $1 + \sum_{i=1}^{\gamma}\prod_{j=1}^{i}\alpha_j$. If those conditional probabilities are all $\alpha$, this reduces to:

Normalize time by an ordinary target decode step. If each draft token costs $c$ and a verification pass costs $v$, the modeled speedup is $\mathbb{E}[N] / (\gamma c + v)$. The often-quoted denominator $\gamma c + 1$ assumes $v=1$. In practice $v$ depends on batch, context, draft length and implementation; measure it at the workload of interest.

alpha = 0.7, gamma = 3, c = 0.1
E[N]    = (1 - 0.7^4) / (1 - 0.7) = (1 - 0.2401) / 0.3 = 2.533 tokens per pass
cost    = 3 x 0.1 + 1 = 1.30 target steps
speedup = 2.533 / 1.30 = 1.95x
sanity: alpha -> 0 gives 1 / 1.30 = 0.77x (a slowdown)
        alpha -> 1 gives 4 / 1.30 = 3.08x (the gamma + 1 ceiling)

This table holds verification cost at $v=1$ and searches integer draft lengths; its costs are illustrative, not measurements of draft architectures. At $\alpha=0.8, \gamma=4, c=0.05$, expected output is $1+0.8+0.64+0.512+0.4096=3.3616$ tokens. With $v=1$, speedup is $3.3616/1.2=2.80$; with $v=3.5$, it is $3.3616/3.7=0.91$, a slowdown at identical acceptance. Vary both costs in the lab.

The proof

Let the draft sample $x \sim q$. Accept with probability $\min(1, p(x)/q(x))$; on rejection, sample from $r = (p-q)_+ / \lVert (p-q)_+ \rVert_1$. The acceptance mass is $\alpha = \sum_x \min(p(x), q(x))$, and because $\sum_x p = \sum_x q = 1$, the rejected mass equals the residual mass:

So the emitted token has probability $\min(p,q)(x) + (p-q)_+(x) = p(x)$ at every $x$. Acceptance is one minus the total-variation distance, which is the cleanest statement of why a better-aligned draft helps. The same argument applies position by position, because each position's $p$ is conditioned on the accepted prefix. The exact check below computes the emitted law directly rather than sampling it:

import numpy as np

def emitted_distribution(p, q):
    """Exact law of the token emitted at one draft position. p, q: [V]."""
    accept = np.minimum(p, q)               # q(x) * min(1, p(x)/q(x))
    alpha = accept.sum()                    # = 1 - TV(p, q)
    resid = np.maximum(p - q, 0.0)          # (p - q)+, total mass 1 - alpha
    if resid.sum() > 0:
        resid = resid / resid.sum()
    return accept + (1 - alpha) * resid, alpha

rng = np.random.default_rng(0)
worst = 0.0
for _ in range(10_000):
    V = rng.integers(2, 50)
    p, q = rng.dirichlet(np.ones(V)), rng.dirichlet(np.ones(V) * 0.3)
    out, alpha = emitted_distribution(p, q)
    tv = 0.5 * np.abs(p - q).sum()
    assert abs(alpha - (1 - tv)) < 1e-12
    worst = max(worst, np.abs(out - p).max())
print(f"max |out - p| over 10,000 random pairs: {worst:.1e}")   # 3.3e-16

out, alpha = emitted_distribution(np.array([1.0, 0.0]), np.array([1.0, 0.0]))
print("identical draft:", out, alpha)       # residual is empty, alpha = 1

The identical-draft case matters in review: when $p = q$ the residual has zero mass and a naive normalization divides by zero. The result preserves the target's probability law, not the token sequence obtained from a particular random seed. This is the exact sampler analyzed by Leviathan et al., ICML 2023.

Where it breaks

The batch fills the idle compute. Under the weight-dominated linear-layer approximation, verification intensity in BF16 is $B(\gamma+1)$. The H100 SXM ridge is near 295, so with $\gamma=3$ the linear phase crosses near $B=295/4\approx74$. This is a roofline crossover, not a measured speedup boundary. Native FP8 doubles both intensity and peak compute: $2B(\gamma+1)\approx591$ gives essentially the same batch threshold. Weight-only 8-bit storage with BF16 compute instead gives $2B(\gamma+1)\approx295$, halving that threshold. NVIDIA's dense peaks are half its sparsity-marked figures.

Acceptance varies by position and request. A single average acceptance rate does not determine the products of conditional probabilities. Estimate accepted prefix lengths on the real workload; later positions need not share the first position's acceptance.

Use the actual sampling distributions. Let $p$ be the requested target distribution after temperature and truncation, and $q$ the distribution that actually generated the proposal. They can use different settings; the ratio and residual must use the correctly normalized distributions over the same token vocabulary. Verifying against raw target logits silently changes the requested law. Tokens with $q=0, p>0$ enter through the residual; they cannot have been proposed by $q$.

State rollback. Rejected positions wrote KV entries and, for grammar-constrained requests, advanced a parser state. Both must roll back to the accepted prefix.

What interviewers listen for

• The bonus token, and the resulting $\gamma + 1$ ceiling rather than $\gamma$.
• Resampling from $(p-q)_+$, not from $p$. Resampling from $p$ over-weights the tokens where $q > p$.
• $\alpha = 1 - \mathrm{TV}(p, q)$ stated without prompting.
• The cost term $\gamma c$ in the denominator, and a speedup quoted with a batch size attached.
• Greedy decoding reduces the test to "does the draft match the target argmax", with the same expected-length algebra.

Say it in 30 seconds

"A draft proposes tokens and the target verifies them together. Expected output is one plus the sum of accepted-prefix probabilities. Divide that by drafting plus verification cost to decide whether it pays. Accepting with $\min(1,p/q)$ and correcting with $(p-q)_+$ preserves the target distribution. High acceptance helps, but expensive verification can still make speculation slower."