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

Jie Ou, Yueming Chen, Wenhong Tian

TL;DR

This paper introduces Adaptive N-gram Parallel Decoding (ANPD), a novel, lossless method to speed up Large Language Model (LLM) inference. ANPD uses an adaptive N-gram module to draft multiple tokens in parallel, which are then verified by the LLM, achieving significant speedups without retraining or extra memory.

What Problem Does This Paper Address?

Large Language Models (LLMs) like GPT-4 and LLaMA are incredibly powerful but suffer from high latency and resource consumption during inference. This is largely due to their autoregressive nature, where tokens are generated one by one. This sequential process becomes a bottleneck, especially when tokenization splits words into multiple tokens, further increasing the number of generation steps. While existing methods like quantization, pruning, and speculative decoding offer improvements, they often require model retraining, architectural changes, or increased memory, making them less accessible. This paper aims to provide a plug-and-play solution that accelerates LLM inference without these drawbacks.

Methods

The core of ANPD is a two-stage decoding process:

  1. Drafting: An "Adaptive N-gram Module" generates a sequence of potential next tokens. This module is "adaptive" because it dynamically updates its probabilities based on the current context, rather than relying on large, static training corpora. It uses a probabilistic N-gram model that predicts the next token based on the preceding N-1 tokens. To improve accuracy, a "Multi-Level N-gram" (MLN) approach is employed, where the system queries N-gram models of decreasing order (from N down to 2) until a match is found. This drafting phase aims to propose multiple tokens simultaneously.
  2. Verification: The original LLM then takes these proposed draft tokens and verifies them in a single forward pass. If a draft token is accepted (i.e., it matches the LLM's prediction), it's added to the output. If it fails verification, it's discarded, and the LLM's own prediction is used, with drafting restarting from that point. This ensures that the output remains identical to what the LLM would have produced autoregressively, hence "lossless."

The ANPD approach is designed to be a plug-and-play module, meaning it doesn't require retraining the LLM or significant changes to its architecture.

Datasets

The paper evaluates ANPD on several standard datasets for text generation tasks:

  • Text Summarization: CNN/Daily Mail (CNN/DM) and Extreme Summarization (XSum).
  • Code Generation: HumanEval.

The authors mention using a sample size of 1000 for summarization tasks to ensure statistical significance.

Key Insights and Ideas

  • Leveraging N-grams for Speed: The paper demonstrates that even simple N-gram models, when adapted dynamically to the context, can effectively predict likely next tokens, bypassing some of the LLM's computational load.
  • Lossless Acceleration is Achievable: The core innovation is the "draft and verify" approach, which guarantees that the ANPD output is identical to the original LLM output, addressing a key limitation of many acceleration techniques.
  • Multi-Level N-gram for Precision: The MLN strategy is crucial for improving the accuracy of the drafted tokens, which directly impacts the "draft hit ratio" and thus the overall speedup.
  • Plug-and-Play Simplicity: The method's independence from LLM retraining or architectural modifications makes it highly practical for researchers and developers.

Key Results

ANPD demonstrated significant speedups across various LLMs and datasets:

  • LLaMA-7B: Achieved speedups over 2.0x.
  • LLaMA-2-13B: Showed a twofold increase in acceleration compared to a previous method (2.9088x vs. 1.3293x).
  • ChatGLM3-6B: Achieved speedups of 1.7046x and 1.6647x on CNN/DM and XSum, respectively, despite its larger vocabulary.
  • HumanEval (Code Generation): ANPD achieved a substantial speed-up of 3.6665x, significantly outperforming a previous method (1.6758x).
  • Overall: The paper reports peak acceleration of up to 3.67x on LLaMA and its fine-tuned variants.

The authors also found that increasing the N-gram order (N) generally improves accuracy, but gains plateau around N=5. Similarly, the number of parallel tokens drafted (K) shows diminishing returns beyond K=6-8.

Limitations and Future Work

  • Limitations: While ANPD is lossless, the speedup is dependent on the "draft hit ratio" – how often the N-gram module's predictions are correct. A lower hit ratio means more verification by the LLM, reducing the speedup. The paper notes that implementation issues can lead to theoretical speedups being slightly higher than actual achieved rates.
  • Future Work: The authors suggest two main directions:
  • LLM-Specific Adaptations: Tailoring ANPD's features to the specific characteristics of individual LLMs (like LLaMA or ChatGLM) to further boost inference performance.
  • Parallel Verification: Exploring the possibility of generating and verifying multiple tokens in parallel during the LLM's verification phase to achieve even greater acceleration.

Summary updated

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.
BibTeX
@inproceedings{ou2024lossless,
  author = {Jie Ou and Yueming Chen and Wenhong Tian},
  title = {{Lossless Acceleration of Large Language Model via Adaptive N-gram Parallel Decoding}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=Gg78BDdpsY},
}
Figure