Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs

Chenxi Sun, Hongzhi Zhang, Zijia Lin, Jingyuan Zhang, Fuzheng Zhang, Zhongyuan Wang, Bin Chen, Chengru Song, Di Zhang, Kun Gai, Deyi Xiong

Abstract

Large language models have demonstrated exceptional capability in natural language understanding and generation. However, their generation speed is limited by the inherently sequential nature of their decoding process, posing challenges for real-time applications. This paper introduces Lexical Unit Decoding (LUD), a novel decoding methodology implemented in a data-driven manner, accelerating the decoding process without sacrificing output quality. The core of our approach is the observation that a pre-trained language model can confidently predict multiple contiguous tokens, forming the basis for a lexical unit, in which these contiguous tokens could be decoded in parallel. Extensive experiments validate that our method substantially reduces decoding time while maintaining generation quality, i.e., 33% speed up on natural language generation with no quality loss, and 30% speed up on code generation with a negligible quality loss of 3%. Distinctively, LUD requires no auxiliary models and does not require changes to existing architectures. It can also be integrated with other decoding acceleration methods, thus achieving an even more pronounced inference efficiency boost. We posit that the foundational principles of LUD could define a new decoding paradigm for future language models, enhancing their applicability for a broader spectrum of applications. Keywords: Parallel Decoding, Lexical Unit Decoding, Large Language Model

Introduction

The standard Transformer architecture generates text auto-regressively, producing one token at a time. This sequential bottleneck is the primary hurdle for real-time LLM applications. While techniques like speculative decoding attempt to mitigate this by using auxiliary "draft" models, they introduce additional complexity and memory overhead. Lexical Unit Decoding (LUD) offers a "middle path": a data-driven approach that enables parallel decoding within a single, standard model by identifying and exploiting "islands of certainty"—sequences of tokens the model can predict with high confidence.

Methodology: Lexical Unit Decoding

LUD operates on the principle that many token sequences are highly predictable in context. The method consists of three main phases:

1. Lexical Unit Identification

A "lexical unit" is defined as a span of consecutive tokens where the model’s prediction probability exceeds a high threshold ($\alpha$). These units represent common phrases, syntactic structures, or boilerplate code that the model can effectively "fast-forward" through.

Examples of identified lexical units in natural language (A), source code (B), and sub-word sequences (C).

2. Data-Centric Training

Rather than modifying the model architecture, LUD employs a data-centric training strategy. On a target dataset, identified lexical units are replaced with trainable [PAD] tokens. This teaches the model to predict the entire chunk in parallel while maintaining correct positional information, effectively fine-tuning the model to recognize and generate these units as single blocks.

3. Adaptive Inference

During generation, the model uses a "look-ahead" window (typically $k=10$) to attempt parallel prediction. To ensure quality, LUD employs an adaptive mechanism: it only accepts a sequence of tokens as long as their individual confidence scores stay above a threshold ($\beta$). If the model's confidence drops, it gracefully reverts to standard single-token decoding for that step.

The LUD adaptive inference process. The model predicts multiple tokens in parallel but only accepts those exceeding the confidence threshold $\beta$.

Experimental Evaluation

The researchers evaluated LUD using LLaMA-13B across two domains:

  • Natural Language: Using the Alpaca dataset (52,000 instructions) for training and a diverse set of 252 instructions for testing.
  • Code Generation: Using Code Alpaca (20,000 instructions) for training and the HumanEval benchmark (164 problems) for evaluation.

Key Results

  • Text Generation: LUD achieved a 33.68% wall-time acceleration with 100% quality retention (verified by GPT-4 evaluation).
  • Code Generation: LUD achieved a 29.77% wall-time acceleration with a minor 3% quality dip. The higher predictability of code structures led to more consistent speedups.
  • Efficiency: The Forward Compression Ratio (FCR) indicated that LUD reduces the number of forward passes required by approximately one-third.

Discussion and Insights

A key finding is the "linguistic rationality" of the parallelized units. As shown in Figure 6, the tokens decoded in parallel are not random; they form coherent linguistic or functional units (e.g., "specifically designed to" or "def max_element").

Furthermore, LUD avoids the need for auxiliary models, simplifying deployment and reducing memory overhead compared to speculative decoding. It also includes a "Token Repetition Mitigation" check to prevent "stuttering" errors common in parallel decoding schemes.

Conclusion and Future Work

LUD demonstrates that parallel decoding can be achieved within a single model through data-driven fine-tuning. While current implementation requires a fine-tuning step on target datasets, future work could involve integrating these principles directly into the initial pre-training phase. This would make LUD a more general-purpose "plug-and-play" solution, potentially defining a new paradigm for efficient LLM inference. All codes are publicly available at https://github.com/tjunlp-lab/Lexical-Unit-Decoding-LUD-.

Summary updated

Abstract

Large language models have demonstrated exceptional capability in natural language understanding and generation. However, their generation speed is limited by the inherently sequential nature of their decoding process, posing challenges for real-time applications. This paper introduces Lexical Unit Decoding (LUD), a novel decoding methodology implemented in a data-driven manner, accelerating the decoding process without sacrificing output quality. The core of our approach is the observation that a pre-trained language model can confidently predict multiple contiguous tokens, forming the basis for a \textit{lexical unit}, in which these contiguous tokens could be decoded in parallel. Extensive experiments validate that our method substantially reduces decoding time while maintaining generation quality, i.e., 33\% speed up on natural language generation with no quality loss, and 30\% speed up on code generation with a negligible quality loss of 3\%. Distinctively, LUD requires no auxiliary models and does not require changes to existing architectures. It can also be integrated with other decoding acceleration methods, thus achieving an even more pronounced inference efficiency boost. We posit that the foundational principles of LUD could define a new decoding paradigm for future language models, enhancing their applicability for a broader spectrum of applications. All codes are be publicly available at https://github.com/tjunlp-lab/Lexical-Unit-Decoding-LUD-. Keywords: Parallel Decoding, Lexical Unit Decoding, Large Language Model
BibTeX
@inproceedings{sun2024decoding,
  author = {Chenxi Sun and Hongzhi Zhang and Zijia Lin and Jingyuan Zhang and Fuzheng Zhang and Zhongyuan Wang and Bin Chen and Chengru Song and Di Zhang and Kun Gai and Deyi Xiong},
  title = {{Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=n9uLLy4GWD},
}
Figure