Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

Large language models (LLMs) have achieved state-of-the-art performance across a wide range of tasks, motivating two important aspects of deployment: inference efficiency and output provenance, which can be tackled by speculative sampling and watermarking, respectively. However, recent works have shown that combining these two goals is highly nontrivial and can be potentially impossible. In this work, we develop a novel multi-draft speculative sampling algorithm based on Poisson processes that improves the frontier of this fundamental trade-off. The proposed algorithm has strong sampling efficiency on its own and, more interestingly, is naturally watermarkable: we can embed an unbiased watermark without degrading speculative acceptance. Moreover, our algorithm is based on an exact list-coupling-without-communication scheme and satisfies certain level of drafter invariance that provides robustness to drafter substitution. Our multi-draft construction jointly provides exact target sampling, stable target-keyed watermark strength as the number of drafts increases, and strong empirical sampling efficiency.