这篇论文搞明白了推测解码里那些花式接受规则到底行不行，给出了数学保证，还在Qwen3上验证了，搞推理加速的值得一看。
推测解码利用快速起草器生成候选 token，再由大模型验证以加速推理。现有理论主要针对随机采样，而实用系统多用贪婪解码和松弛接受规则。本文提出一类具有拒绝区域的接受准则，并给出其精确 KL 散度下界，覆盖严格贪婪、加性和乘性松弛、top-(m) 以及熵阈值等情形。对于树形解码，推导出目标贪婪 token 仍被起草器 top-(m) 覆盖的充分条件。在 Qwen3 模型上的实验表明，松弛和树形准则显著扩大了可保证接受的区域。
When Is a Draft Accepted? A Theory of Acceptance in Speculative Decoding
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.