When Is a Draft Accepted? A Theory of Acceptance in Speculative Decoding
2026-06-29 • Machine Learning
Machine LearningComputation and Language
AI summaryⓘ
The authors study a faster way to get text from language models by using a small, quick helper model to suggest words, then checking those suggestions with a bigger, slower model. Unlike past work that focused on exactly matching probabilities, they look at more practical methods that pick words by rules like picking the best option or using relaxed thresholds. They create math tools to understand when these methods work well and measure how close the results are to what the big model would pick exactly. They test their ideas on real models and show their approach can confidently accept more suggestions, especially when the big model is unsure between words.
speculative decodinglanguage model inferencegreedy decodingKL divergencerelaxed acceptancetop-m decodingtree decodingQwen3 modelsdistribution-preserving samplinginference acceleration
Authors
Aaryam Sharma
Abstract
Speculative decoding accelerates language model inference by using a fast drafter to propose candidate tokens that are then verified by a larger target model. Existing theory largely studies the stochastic, distribution-preserving setting, where the goal is to exactly sample from the target distribution. In contrast, many practical systems use greedy decoding, relaxed acceptance rules, or tree-based candidate sets, where success is governed by local ranking and threshold events rather than exact distributional equality. We develop a theory for these regimes. We identify that many common acceptance criteria have rejection regions that can be characterized as lower level sets of the target distribution. For these, we characterize the exact KL divergence required for rejection yielding exact certificates and sharp margin-based bounds for strict greedy decoding, additive and multiplicative relaxed acceptance, top-(m) relaxed criteria, and entropy-thresholded acceptance. We then extend the framework to greedy tree decoding, deriving exact and margin-only certificates for when the target greedy token remains covered by the drafter's top-(m) candidates. Finally, we evaluate the resulting certificates on Qwen3 models, showing that relaxed and tree-based criteria substantially enlarge the region of certified acceptance, especially on decoding steps with low target model distribution margin. These results complement existing distribution-preserving analyses of speculative decoding by characterizing the deterministic local acceptance events common in practical inference systems.