Speculative Sampling via Exponential Races

Speculative decoding accelerates large language model inference using a smaller draft model.In this paper, we establish a surprising connection between speculative sampling and the concept of channel simulation from information theory, which aims at simulating a noisy channel using as few bits as possible.This connection allows us to provide an informationtheoretic analysis of the speed up that can be achieved by speculative sampling.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 sampling method via exponential races called ERSS that matches state-of-the-art performance.