LazyLLM: Dynamic Token Pruning for Efficient Long Context LLM Inference

• URL: http://arxiv.org/abs/2407.14057v1
• Date: Fri, 19 Jul 2024 06:34:45 GMT
• Title: LazyLLM: Dynamic Token Pruning for Efficient Long Context LLM Inference
• Authors: Qichen Fu, Minsik Cho, Thomas Merth, Sachin Mehta, Mohammad Rastegari, Mahyar Najibi,
• Abstract summary: LazyLLM is a method that selectively computes the KV for tokens important for the next token prediction. We show that LazyLLM accelerates the prefilling stage of the LLama 2 7B model by 2.34x while maintaining accuracy.
• Score: 30.722379261991563
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The inference of transformer-based large language models consists of two sequential stages: 1) a prefilling stage to compute the KV cache of prompts and generate the first token, and 2) a decoding stage to generate subsequent tokens. For long prompts, the KV cache must be computed for all tokens during the prefilling stage, which can significantly increase the time needed to generate the first token. Consequently, the prefilling stage may become a bottleneck in the generation process. An open question remains whether all prompt tokens are essential for generating the first token. To answer this, we introduce a novel method, LazyLLM, that selectively computes the KV for tokens important for the next token prediction in both the prefilling and decoding stages. Contrary to static pruning approaches that prune the prompt at once, LazyLLM allows language models to dynamically select different subsets of tokens from the context in different generation steps, even though they might be pruned in previous steps. Extensive experiments on standard datasets across various tasks demonstrate that LazyLLM is a generic method that can be seamlessly integrated with existing language models to significantly accelerate the generation without fine-tuning. For instance, in the multi-document question-answering task, LazyLLM accelerates the prefilling stage of the LLama 2 7B model by 2.34x while maintaining accuracy.

Related papers

• FIRP: Faster LLM inference via future intermediate representation prediction [54.897493351694195]
  FIRP generates multiple tokens instead of one at each decoding step. We conduct extensive experiments, showing a speedup ratio of 1.9x-3x in several models and datasets.
  arXiv  Detail & Related papers  (2024-10-27T15:53:49Z)
• Tokenization as Finite-State Transduction [24.19959327497118]
  We introduce a finite-state framework which can efficiently encode all possible tokenizations of a regular language. We show that Byte-Pair. Match (BPE) and MaxPiece (WordPiece) fit within this framework. An application of this is to guided generation, where the outputs of a language model are constrained to match some pattern.
  arXiv  Detail & Related papers  (2024-10-21T07:10:07Z)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [53.58854856174773]
  Speculative decoding is an approach to accelerate inference through a guess-and-verify paradigm. Token Recycling stores candidate tokens in an adjacency matrix and employs a breadth-first search algorithm. It significantly outperforms existing train-free methods by 30% and even a training method by 25%.
  arXiv  Detail & Related papers  (2024-08-16T12:20:56Z)
• Empowering Character-level Text Infilling by Eliminating Sub-Tokens [34.37743927032878]
  FIM-SE stands for Fill-In-the-Middle with both Starting and Ending character constraints. We introduce FIM-SE, which stands for Fill-In-the-Middle with both Starting and Ending character constraints.
  arXiv  Detail & Related papers  (2024-05-27T12:21:48Z)
• Parallel Decoding via Hidden Transfer for Lossless Large Language Model Acceleration [54.897493351694195]
  We propose a novel parallel decoding approach, namely textithidden transfer, which decodes multiple successive tokens simultaneously in a single forward pass. In terms of acceleration metrics, we outperform all the single-model acceleration techniques, including Medusa and Self-Speculative decoding.
  arXiv  Detail & Related papers  (2024-04-18T09:17:06Z)
• Prepacking: A Simple Method for Fast Prefilling and Increased Throughput in Large Language Models [48.592730159983276]
  Prefilling is the computation of the key-value cache for input tokens in the prompt prior to autoregressive generation. For longer input prompt lengths, prefilling incurs a significant overhead on decoding time. We propose Prepacking, a simple yet effective method to optimize prefilling computation.
  arXiv  Detail & Related papers  (2024-04-15T07:49:10Z)
• PaSS: Parallel Speculative Sampling [29.23180061749074]
  Scaling the size of language models to tens of billions of parameters has led to impressive performance on a wide range of tasks. At generation, these models are used auto-regressively, requiring a forward pass for each generated token, and thus reading the full set of parameters from memory. We show promising performance (up to $30%$ speed-up) while requiring only as few as $O(d_emb)$ additional parameters.
  arXiv  Detail & Related papers  (2023-11-22T18:37:27Z)
• Efficient Streaming Language Models with Attention Sinks [72.20260088848987]
  StreamingLLM is an efficient framework that enables Large Language Models to generalize to infinite sequence lengths without any fine-tuning. We show that StreamingLLM can enable Llama-2, MPT, Falcon, and Pythia to perform stable and efficient language modeling with up to 4 million tokens and more.
  arXiv  Detail & Related papers  (2023-09-29T17:59:56Z)
• RetroMAE v2: Duplex Masked Auto-Encoder For Pre-Training Retrieval-Oriented Language Models [3.4523793651427113]
  We propose duplex masked auto-encoder, a.k.a. DupMAE, which targets on improving the semantic representation capacity for contextualized embeddings of both [] and ordinary tokens. DupMAE is simple but empirically competitive: with a small decoding cost, it substantially contributes to the model's representation capability and transferability.
  arXiv  Detail & Related papers  (2022-11-16T08:57:55Z)
• COCO-LM: Correcting and Contrasting Text Sequences for Language Model Pretraining [59.169836983883656]
  COCO-LM is a new self-supervised learning framework that pretrains Language Models by COrrecting challenging errors and COntrasting text sequences. COCO-LM employs an auxiliary language model to mask-and-predict tokens in original text sequences. Our analyses reveal that COCO-LM's advantages come from its challenging training signals, more contextualized token representations, and regularized sequence representations.
  arXiv  Detail & Related papers  (2021-02-16T22:24:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.