Speculative Decoding Math: Algorithms & Speedup Limits › Speculative Decoding Math

In the previous chapter, we introduced speculative decoding as a technique for accelerating autoregressive generation by having a small draft model propose multiple tokens that a larger target model verifies in parallel. The key insight was that verification is faster than sequential generation because it allows parallel processing. However, a necessary question remains: how do we decide which draft tokens to accept?

The answer involves carefully designed acceptance criteria that guarantee mathematical correctness. We need a rejection sampling scheme that preserves the target model's output distribution exactly, not approximately. Speculative decoding is mathematically equivalent to standard sampling, creating outputs that are statistically indistinguishable from what you would have generated by running only the large model. This chapter develops the mathematical framework for speculative decoding, including the acceptance criterion, expected speedup analysis, draft quality effects, and optimal draft length selection.

To appreciate why the mathematics matters here, consider what would go wrong with naive approaches. One tempting shortcut is to accept draft tokens whenever both models agree and reject them otherwise. But this biases output toward the intersection of the two distributions, changing the character of the generated text in ways that depend on how similar the models are. Another approach might be to always accept draft tokens and only run the target model occasionally for "spot checking." This would be fast, but it fundamentally changes the output distribution to match the draft model rather than the target. Neither approach achieves the goal of preserving exact target model behavior while gaining speed.

Think of the speculative decoding problem as analogous to quality control in manufacturing. A fast but imperfect inspector (the draft model) checks items on a production line and marks some as passing. A slower, authoritative inspector (the target model) can then review a batch of flagged items simultaneously rather than examining each one independently. The key challenge is designing the fast inspector's acceptance rules so that the batch of passed items, after the authoritative review, has exactly the same quality distribution as if the authoritative inspector had checked each item individually. You want speed without sacrificing quality guarantees.

The mathematical framework we develop draws on classical statistics, specifically rejection sampling, and connects the performance of speculative decoding to the distributional similarity between draft and target models. We will derive precise formulas for expected speedup, understand how draft model quality affects performance, and see how to choose the optimal number of draft tokens for any hardware configuration. This analysis provides both theoretical understanding and practical guidance for deploying speculative decoding in real systems.