Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding (2024)

Abstract: To mitigate the high inference latency stemming from autoregressive decoding in Large Language Models (LLMs), Speculative Decoding has emerged as a novel decoding paradigm for LLM inference. In each decoding step, this method first drafts several future tokens efficiently and then verifies them in parallel. Unlike autoregressive decoding, Speculative Decoding facilitates the simultaneous decoding of multiple tokens per step, thereby accelerating inference. This paper presents a comprehensive overview and analysis of this promising decoding paradigm. We begin by providing a formal definition and formulation of Speculative Decoding. Then, we organize in-depth discussions on its key facets, such as drafter selection and verification strategies. Furthermore, we present a comparative analysis of leading methods under third-party testing environments. We aim for this work to serve as a catalyst for further research on Speculative Decoding, ultimately contributing to more efficient LLM inference.

## introduction large language models (llms) have achieved remarkable proficiency in a range of downstream tasks @xcite @xcite . they are progressively evolving as the cornerstone of comprehensive api interfaces (e.g., chatgpt foot_1 ), offering human life services and guidance through real-time human-machine interactions. however, the inference latency of these sizable models has emerged as a substantial obstacle restricting their broader applications. this latency primarily arises from the token-by-token generation necessitated by autoregressive decoding, resulting in an escalation of the inference latency with both the length of the generated sequence and the model's scale. ## overview this paper offers a comprehensive survey of speculative decoding. we commence by introducing the early stages of speculative decoding research ( §3), illustrated by a timeline of its evolution (as shown in figure 2 ). this is followed by a formal definition and formulation of speculative decoding ( §4). then, we delve into a detailed discussion of leading techniques, including the selection of draft models ( §5), verification strategies ( §6), and alignment between the drafter and the target llm ( §7). moreover, we introduce spec-bench, an extensive evaluation benchmark designed for assessing the acceleration effect of speculative decoding ( §8). ## evolution of speculative decoding this section discusses the motivation behind speculative decoding ( §3.1) and then provides a detailed introduction to early attempts in this field ( §3.2). ## formulation and definition in this section, we first provide a concise overview of standard autoregressive decoding ( §4.1). then, we offer an in-depth exposition of speculative decoding ( §4.2), which encompasses a formal definition, a comprehensive description of the methodology, and a detailed elaboration of the algorithm. ## drafting as a vital component of speculative decoding, the drafting process has a crucial impact on the speedup of the paradigm. the impact is determined by two key factors: the speculation accuracy of the drafter m p , measured by the average number of accepted tokens per step, and the drafting latency @xcite . how to trade off high speculation accuracy and low drafting latency presents a major challenge in this process. in this section, we classify various drafting strategies into two categories: independent drafting ( §5.1) and self-drafting ( §5.2), and summarize their formulations draft (@xmath0, m p ) in ## verification in each decoding step, the drafted tokens are verified in parallel to ensure the outputs align with the target llm. this process also determines the number of tokens accepted per step, a vital factor impacting the speedup. this section summarizes various verification criteria verify ( x i , p i , q i ) (as shown in ## alignment as illustrated in section 5, the speedup of speculative decoding primarily depends on the speculation accuracy, which in turn is influenced by the behavior similarity between the drafter and the target llm. to enhance this, existing research has explored various knowledge distillation (kd) strategies to align the drafter's outputs with those of the target llm @xcite @xcite @xcite . particularly, blockwise decoding adopted sequence-level knowledge distillation (seq-kd) @xcite for alignment, which trained the drafter on the sentences generated by the target llm. @xcite proposed a collective boost-tuning (col-bt) strategy, applying seq-kd to finetune multiple small lms on the training data and utilizing their aggregated output as drafts to improve the speculation accuracy. although seq-kd is effective, it ignores the probability distributions of the target llm, leading to performance degradation with sampling methods. to rectify this, recent studies have explored other kd strategies for speculative decoding @xcite . notably, distill-spec @xcite conducted a comprehensive comparison of different kd strategies on speculative decoding across various downstream tasks. @xcite proposed an online kd strategy that dynamically aligns the drafter with the target llm on the fly using the query data. we summarize the main features of existing speculative decoding methods in ## spec-bench with the rapid research progress in speculative decoding, there is an increasing demand for comparative analysis of leading methods. however, existing approaches are tested using disparate benchmarks, devices, and environments, making fair comparisons impractical. to address this gap, we introduce spec-bench -a comprehensive benchmark for speculative decoding covering diverse application scenarios. based on spec-bench, we present a systematic comparison of open-source approaches under third-party testing conditions. experiments were executed on the same device and testing environment to ensure a fair comparison. ## challenges and future directions how to trade off speculation accuracy and drafting efficiency? as discussed in sections 5, scaling up the drafter can effectively enhance speculation accuracy, yet it largely reduces the drafting efficiency and even the overall speedup. therefore, it is essential to strike a balance between speculation accuracy and drafting latency. among existing strategies, behavior alignment is a promising approach to address this issue, as it improves speculation accuracy without increasing latency. however, despite recent advancements @xcite @xcite , there is still considerable room for improvement to align the drafter with the target llm. for example, given that the drafted tokens after the bifurcation position are all discarded, one potential direction could involve encouraging the drafter to prioritize the generation quality of early-position tokens. beyond alignment, other factors such as the quality of drafting @xcite and the determination of speculation length @xcite also influence speculation accuracy and merit further exploration. how to apply speculative decoding in batched inference scenarios? currently, only a few speculative decoding implementations have supported batched inference, such as eagle foot_4 and sps foot_5 . however, batched inference is a crucial technique for efficiently managing user inputs in llm realtime services. the primary challenges in batched speculative decoding lie in two aspects: (1) each decoded sentence in speculative decoding varies in decoding steps due to different speculation accuracy. thus, the inference latency of a batch depends on the slowest sample in the batch; (2) the extra computational complexity introduced by speculative decoding, especially in sampling settings, increases with larger batch sizes. how to maintain a promising speedup of speculative decoding in batched inference, and combine it with advanced techniques such as continuous batching @xcite , warrants further investigation. how to integrate speculative decoding with other leading techniques? as a general decoding paradigm, speculative decoding has already demonstrated its potential in conjunction with other advanced techniques @xcite @xcite . for instance, @xcite combined speculative decoding with contrastive decoding @xcite , which not only speeds up the inference but also substantially improves the generation quality. in addition to the acceleration of text-only llms, applying speculative decoding in multimodal inference, such as image synthesis, text-to-speech synthesis, and video generation, is also an intriguing and valuable direction for future research. another promising research direction is to integrate speculative decoding with other efficient methods such as vllm @xcite , non-auregressive generation @xcite and flash-attention @xcite , further boosting the inference efficiency of llm services. ## conclusion this paper presents a comprehensive survey of speculative decoding, including the evolution of this promising paradigm, its formal definition and formulation, a systematic categorization of existing methods, and an in-depth review of leading techniques. moreover, we introduce spec-bench, an extensive evaluation benchmark for speculative decoding methods, and present a comparative evaluation of prominent methods. to our knowledge, this is the first survey dedicated to speculative decoding. our aim for this paper is to clarify the current research landscape and provide insights into future research directions.