Recursive rejection sampling achieves at least three quarters of the optimal acceptance in multi-draft speculative decoding with independent drafts

Speculative decoding speeds up a large language model: a small draft model proposes tokens, and the large model verifies them without changing its output distribution. With k independent drafts per position, SpecInfer's recursive rejection sampling (RRS) tests drafts one at a time, with no guarantee we know of beyond 1/k. We prove that RRS achieves at least a fraction rho_k = 1 - max_{0<=a<=1}(a^k - a^{2k-1}) of the optimal acceptance, and that this is tight: rho_2 = 23/27, and rho_k decreases to 3/4. The proof writes RRS as one scalar recursion and lumps the tokens into two groups by the sign of the final residual, which can only lower RRS's acceptance and only raise the optimum. We also give KEY, an exact optimal verifier: after one sort and an interval-placement step, each draft draws a random key, and the draft with the smallest key is verified. On two small model pairs (temperature 1, four drafts), the mean acceptance gap of RRS is only 0.033, yet RRS rejects 1.35 times as often as the optimal verifier (pooled). The record includes the paper, its LaTeX source, and the code and certificates that reproduce every computed result.