Attaining and Surpassing the IID Ceiling in Multi-Draft Speculative Decoding

Multi-draft speculative decoding has a computable acceptance ceiling under independent and identically distributed (IID) proposals, but turning this value into an exact, scalable sampler remains a constructive challenge. We resolve this problem with Optimal IID, which preserves the target distribution exactly and attains the IID ceiling for any candidate count without iterative optimization or an approximation tolerance. Its finite-score construction uses near-linear arithmetic preprocessing. To exceed this ceiling, Stratified changes proposal dependence through equal-mass stratification, preserving each slot's draft marginal and matching or exceeding IID coverage for every token subset. Its optimal acceptance is no lower than the IID ceiling for any target, with strict improvements on some inputs. A recursive exact verifier attains this new ceiling with near-linear arithmetic work and polylogarithmic arithmetic span. Across three model pairs from the Qwen3 and Gemma 2 families, Stratified recovers approximately 85–92% of the gap from optimal IID to a target-aware coupling oracle with the same proposal marginals. The evaluation uses four candidates, top-100 draft support, and temperature 1. In a feasibility study at this setting, a single-GH200 implementation for Qwen3-32B/1.7B averages 0.49 ms per output token for verification-plan construction and online sampling, including residual correction, and accelerates decoding by 1.58× over autoregressive sampling. Proposal dependence thus enables further acceptance gains after IID verification is optimal.