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:
- 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.
- 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