Speculative Decoding Math: Algorithms & Speedup Limits › Summary

This chapter developed the mathematical foundations of speculative decoding. This provides tools to understand and optimize this important inference acceleration technique.

The acceptance criterion uses rejection sampling with a residual distribution to guarantee that speculative decoding produces outputs identical in distribution to standard autoregressive sampling. The acceptance probability $\alpha(x) = \min(1, p(x)/q(x))$ ensures we accept tokens where the draft model underestimates the target probability while probabilistically rejecting overestimated tokens. The residual distribution on rejection corrects for the missing probability mass, completing the guarantee through the algebraic identity $\min(p,q) + \max(0, p-q) = p$.

The connection to total variation distance, $\alpha = 1 - TV(p, q)$, provides a basic measure of draft model quality rooted in classical statistics. This tells us that acceptance rates are not arbitrary metrics but reflect the most basic notion of how distinguishable two probability distributions are.

Expected speedup depends on the acceptance probability $\alpha$, draft length $k$, and cost ratio $c$. The formula $S = \frac{(1 - \alpha^{k+1})/(1-\alpha)}{1 + k/c}$ captures the tradeoff between generating more draft tokens and the diminishing probability of accepting them all. The geometric series structure of $\mathbb{E}[N]$ is responsible for the diminishing returns that create an interior optimum for draft length.

Optimal draft length balances these factors. Higher acceptance rates support longer drafts, with practical optima typically ranging from 4 to 10 tokens depending on model quality and hardware configuration. The first-order condition for optimality equates the marginal benefit of extending the draft with the marginal cost, and this balance shifts predictably with changes in $\alpha$ and $c$.

Draft model quality directly impacts speedup through the acceptance probability $\alpha = \sum_x \min(p(x), q(x))$. Smaller models within the same family often provide the best balance of speed and distribution similarity, and the optimal draft model is not necessarily the one with the highest acceptance rate but the one that maximizes the speedup formula when both quality and speed are accounted for.