Fast Inference from Transformers via Speculative Decoding

3.1 Number of Generated Tokens

1. What is the acceptance rate \(\beta\), and how does it relate to \(p\) and \(q\)?
   \(\beta\) is the probability that a guess \(x \sim q\) is accepted, given the prefix: \(\beta = \sum_x \min(p(x), q(x)) = 1 - D_{LK}(p, q)\), where \(D_{LK}\) is a symmetric divergence in \([0,1]\) (0 iff \(p = q\), 1 iff disjoint supports). \(\alpha = E(\beta)\) measures how well \(M_q\) approximates \(M_p\).
   • Leviathan et al., 2023, Fast Inference from Transformers via Speculative Decoding (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §3.1
2. What is the expected number of tokens per run of the algorithm?
   Assuming i.i.d. \(\beta\)s, it is a capped geometric variable: \(E(\#\text{tokens}) = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}\). For \(\alpha = 0.8\) and \(\gamma = 5\) this is about 3.7 tokens per run of \(M_p\).
   • Leviathan et al., 2023, Fast Inference from Transformers via Speculative Decoding (Proceedings of the 40th International Conference on Machine Learning (ICML 2023), PMLR 202), §3.1