One-Step Limits of Randomized Speculative Decoding

Speculative decoding accelerates language-model inference by proposing candidate continuations and verifying them in parallel. This letter studies a deliberately restricted one-step abstraction: under a parallel verification budget \(P\) , a non-anticipating policy proposes up to \(P\) continuations, and the accepted length is the longest verifier-consistent prefix. We show that, for any verifier prefix law and any deterministic or randomized policy, the probability of accepting at least \(\ell\) tokens is bounded by the top- \(P\) mass \(M_{P}(\ell)\) of the verifier's length- \(\ell\) prefix distribution. Consequently, \(\mathbb{E}[L_{P}]\leq\sum_{\ell\geq 1}M_{P}(\ell)\) . The result identifies covered verifier-prefix mass as the depthwise bottleneck in this one-step model: randomization cannot improve on the best deterministic prefix cover at any fixed prefix length. Under independent-token specializations, Rényi and collision-entropy bounds yield logarithmic-in- \(P\) limits, while uniform and spread-out regimes give matching or near-matching deterministic constructions. Stylized simulations and inference-only logits experiments illustrate the predicted diminishing returns.