Lossless Acceleration of Large Language Model via Adaptive N-gram Parallel Decoding (2024)

Abstract: While Large Language Models (LLMs) have shown remarkable abilities, they are hindered by significant resource consumption and considerable latency due to autoregressive processing. In this study, we introduce Adaptive N-gram Parallel Decoding (ANPD), an innovative and lossless approach that accelerates inference by allowing the simultaneous generation of multiple tokens. ANPD incorporates a two-stage approach: it begins with a rapid drafting phase that employs an N-gram module, which adapts based on the current interactive context, followed by a verification phase, during which the original LLM assesses and confirms the proposed tokens. Consequently, ANPD preserves the integrity of the LLM’s original output while enhancing processing speed. We further leverage a multi-level architecture for the N-gram module to enhance the precision of the initial draft, consequently reducing inference latency. ANPD eliminates the need for retraining or extra GPU memory, making it an efficient and plug-and-play enhancement. In our experiments, models such as LLaMA and its fine-tuned variants have shown speed improvements up to 3.67x, validating the effectiveness of our proposed ANPD.

## introduction the advent of large language models (llms) such as @xcite , chatgpt @xcite , llama @xcite , and palm @xcite , has revolutionized the landscape of natural language processing. however, the majority of llms @xcite @xcite rely on the decoder-only transformers architecture @xcite , which is intrinsically autoregressive and consequently leads to increased generation time during inference. this characteristic has made the improvement of llm inference efficiency a sig- * corresponding author nificant research area within the natural language processing community. model compression techniques such as quantization @xcite , pruning @xcite , and distillation @xcite have been employed to alleviate the computational costs associated with llms. recently, innovative methods such as early exit strategies @xcite @xcite @xcite and speculative decoding @xcite @xcite @xcite have been proposed to speed up the inference process. while these methods are effective, they typically necessitate modifications to the model architecture and re-training, which can incur substantial costs. additionally, they may alter the model's output and require extra gpu memory needs. a method avoiding draft models using retrieval is presented in @xcite , but it requires a large database. for certain llms, such as llama, the tokenization process can dissect a single word into multiple tokens, thereby exacerbating inference latency. as illustrated in figure 1 , the token count exceeds the word count, resulting in an increased number of autoregressive generation steps. in such scenarios, given the constraints imposed by contextual information, the search space for predicting the next token that forms part of a word based on the current token is significantly narrowed. moreover, contextual information can often be leveraged to identify patterns and correlations between words. this is especially evident for simple phrases and paragraphs, where the context can provide clear indicators that reduce the dependency on llm decoding. based on the above motivation, this paper presents a novel approach, the adaptive n-gram parallel decoding (anpd), designed to enhance inference efficiency without necessitating retraining or the integration of an auxiliary small language model. anpd dynamically generates draft outputs via an adaptive n-gram module using real-time statistics, after which the drafts are verified by the llm. this characteristic is exactly the difference between anpd and the previous speculative decoding methods. the primary contributions of this work can be summarized as follows: inference systems. the development of specialized inference systems for large language models (llms), such as nvidia's tensorrt-llm (nvidia, 2023), orca @xcite , flex-gen @xcite , and deepspeed inference @xcite , represents a notable advancement in the field. despite progress, there is still a gap in the careful co-design of algorithms and systems, which is necessary to fully harness the potential of the hardware. compression. efficient llm inference is facilitated by techniques such as quantization @xcite @xcite , pruning @xcite @xcite , distillation @xcite , and exit early strategies @xcite @xcite @xcite suggest that some tokens can be accurately generated using only a fraction of the model layers. token prunings @xcite @xcite reduce memory and computational demand to accelerate the inference process by prioritizing crucial tokens. these methods enhance efficiency but may necessitate model alterations, re-training, and potentially reduce accuracy. speculative execution. speculative execution @xcite , adapted as speculative decoding in llms @xcite , has improved inference speeds by preempting computations. specinfer @xcite leverages existing distilled, quantized, and pruned variants of an llm, to build a small speculative model pool to guide speculation. however, these approaches require a high-quality draft model, and increase the memory footprint. @xcite also mentioned that unigram and bigram can be used as draft models, but they did not propose a method on how to build a bigram model for the actual running llms. @xcite presented a method of copying reference tokens to the decoder, though its utility is limited by a dependency on repeated text. these techniques increase resource use and compel specialized training, such as distillation, for the draft model to ensure compatibility with the primary model. ## method figure 2 illustrates the framework and workflow of proposed anpd. we explain the original autoregressive decoding in the appendix a.1. ## conclusion in this paper, we presented the anpd algorithm, a novel and lossless approach to accelerate the large language models (llms) inference. this algorithm implements an adaptive n-gram modeling strategy, reducing the necessity for large corpora and eliminating the requirement to build an additional deep-learning draft language model. the multi-level n-gram (mln) strategy not only enhances draft output accuracy but also further boosts efficiency. our empirical studies across various models and datasets validate the anpd algorithm's effectiveness, with a remarkable peak acceleration of up to 3.67× achieved. the anpd algorithm has demonstrated its potency as a powerful tool for enhancing the efficiency of llms. as a plugand-play module, it enables more extensive and pragmatic use of llms in various real-world contexts. future works. we believe that anpd can be further enhanced in two key aspects: by the large language model (llm) to commence a new draft iteration. if the entire content of the draft withstands verification, the final token predicted by the llm is then adopted to initiate the generation of a new draft sequence.