When Is a Draft Accepted? A Theory of Acceptance in Speculative Decoding

I've been wondering about when a draft is considered accepted in speculative decoding scenarios. A lot of research was done on the stochastic distributed setting, typically called speculative sampling or rejection sampling, where the acceptance probability is 1 - TV(p, q).
For greedy acceptance, the draft is accepted if it is the highest probability token under the target model. But I realized this is not trivial, as this is a deterministic process. There was also no literature on this and I wanted to study it further.
I analyzed the conditions under which a draft can possibly be rejected from the perspective of target and draft KL divergence. I also extended this to relaxed acceptance, medusa sampling, and tree based acceptance.

• Read on arXiv

I hope you enjoyed reading the paper!!

Any feedback is greatly appreciated!