Speculative Sampling via Exponential Races
This work addresses the computational bottleneck in LLM inference for users needing faster generation, offering a theoretical foundation and a competitive method, though it is incremental as it builds on existing speculative decoding approaches.
The paper tackles the problem of accelerating large language model inference through speculative decoding, establishing a connection to channel simulation to provide an information-theoretic analysis and deriving an explicit relation for speed-up as an upper bound, while proposing a novel method (ERSD) that matches state-of-the-art performance.
Speculative decoding accelerates large language model inference using a smaller draft model. In this paper, we establish a surprising connection between speculative decoding and channel simulation, which aims at simulating a noisy channel using as few bits as possible. This connection allows us to provide an information-theoretic analysis of the speed up that can be achieved by speculative decoding. Leveraging this link, we derive an explicit relation between generation speed-up and the number of tokens $k$ generated by the draft model for large $k$, which serves as an upper bound for all $k$. We also propose a novel speculative decoding method via exponential race ERSD that matches state-of-the-art performance.