Speculative decoding is a technique which uses a fast draft model to accelerate the inference of a slow target model. With the right verification procedure, speculative decoding can be lossless (i.e. it reproduces the quality of the target model). For token-by-token verification procedures, the criteria for lossless decoding can be written as a system of linear equations and inequalities. The acceptance rate, which directly controls model throughput, is also linear in the same variables. Thus, the optimal verification procedure is obtained by solving a linear program. This linear program is equivalent to an optimal transport problem from the draft distribution to the target distribution.
