Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits

Understand

We consider multi-draft speculative sampling, where the proposal sequences are sampled independently from different draft models.

• At each step, a token-level draft selection scheme takes a list of valid tokens as input and produces an output token whose distribution matches that of the target model.
• Previous works have demonstrated that the optimal scheme (which maximizes the probability of accepting one of the input tokens) can be cast as a solution to a linear program.
• In this work we show that the optimal scheme can be decomposed into a two-step solution: in the first step an importance sampling (IS) type scheme is used to select one intermediate token; in the second step (single-draft) speculative sampling is applied to generate the output token.