Title: A Theoretical Perspective for Speculative Decoding Algorithm Show Chinese title

Title: 一种推测解码算法的理论视角

Abstract: Transformer-based autoregressive sampling has been the major bottleneck for slowing down large language model inferences. One effective way to accelerate inference is \emph{Speculative Decoding}, which employs a small model to sample a sequence of draft tokens and a large model to validate. Given its empirical effectiveness, the theoretical understanding of Speculative Decoding is falling behind. This paper tackles this gap by conceptualizing the decoding problem via markov chain abstraction and studying the key properties, \emph{output quality and inference acceleration}, from a theoretical perspective. Our analysis covers the theoretical limits of speculative decoding, batch algorithms, and output quality-inference acceleration tradeoffs. Our results reveal the fundamental connections between different components of LLMs via total variation distances and show how they jointly affect the efficiency of decoding algorithms. Show Chinese abstract

Abstract: 基于Transformer的自回归采样是导致大型语言模型推理变慢的主要瓶颈。 一种有效加速推理的方法是\emph{推测解码}，它使用一个小模型来采样一系列草稿标记，然后使用一个大模型进行验证。 鉴于其经验上的有效性，对推测解码的理论理解却滞后了。 本文通过马尔可夫链抽象来概念化解码问题，并从理论角度研究关键属性，\emph{输出质量和推理加速}。 我们的分析涵盖了推测解码的理论极限、批处理算法以及输出质量与推理加速之间的权衡。 我们的结果揭示了通过总变异距离的不同组件之间的基本联系，并展示了它们如何共同影响解码算法的效率。