Ltri-LLM: Streaming Long Context Inference for LLMs with Training-Free Dynamic Triangular Attention Pattern
Hongyin Tang, Di Xiu, Lanrui Wang, Xiurui Geng, Jingang Wang, Xunliang Cai · 2024
Read Ltri-LLM: Streaming Long Context Inference for LLMs with Training-Free Dynamic Triangular Attention Pattern by Hongyin Tang, Di Xiu, Lanrui Wang, Xiurui Geng, Jingang Wang, Xunliang Cai (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04757.txt.
Introduction
Hongyin Tang and co-authors wrote a 2024 paper on giving language models a longer reach. Standard attention grows in cost with text length, so very long inputs get too costly to run. Past fixes keep only part of the past text, but they often lose ground on tasks that need exact recall.
The authors found that attention heads show strong local links, as if the model chunks text on its own. Their system, Ltri-LLM, splits stored text into spans and keeps them in an index held off to the side. For each new query, it pulls back only the spans that matter. Tests on long text tasks came close to full attention scores while the system ran in a stream.
Catalog record
| CREATOR | Hongyin Tang, Di Xiu, Lanrui Wang, Xiurui Geng, Jingang Wang, Xunliang Cai |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-04757
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ltri-LLM: Streaming Long Context Inference for LLMs with Training-Free Dynamic Triangular Attention Pattern Hongyin Tang, Di Xiu, Lanrui Wang, Xiurui Geng, Jingang Wang, Xunliang Cai Abstract The quadratic computational complexity of the attention mechanism in current Large Language Models (LLMs) renders inference with long contexts prohibitively expensive. To address this challenge, various approaches aim to retain critical portions of the context to optimally approximate Full Attention (FA) through Key-Value (KV) compression or Sparse Attention (SA), enabling the processing of virtually unlimited text lengths in a streaming manner. However, these methods struggle to achieve performance levels comparable to FA, particularly in retrieval tasks. In this paper, our analysis of attention head patterns reveals that LLMs’ attention distributions show strong local correlations, naturally reflecting a chunking mechanism for input context. We propose Ltri-LLM framework, which divides KVs into spans, stores them in an offline index, and retrieves the relevant KVs into memory for various queries. Experimental results on popular long text benchmarks show that Ltri-LLM can achieve performance close to FA while maintaining efficient, streaming-based inference. † † affiliationnotice: Equal contribution 1 Introduction Recently, Large Language Models (LLMs) have made significant progress in extending context windows, as demonstrated by GPT-4 ( OpenAI et al., 2024 ) and LLaMA-3.1 ( Grattafiori et al., 2024 ) with a 128K window, GLM-4-9B ( GLM et al., 2024 ) with a 1M window, and Gemini-1.5-pro ( Google et al., 2024 ) with a 10M window. Despite these advancements, many open-source LLMs that support extended context lengths still face substantial computational challenges during inference. These challenges stem primarily from the excessive Key-Value (KV) cache storage requirements and the quadratic computational complexity ( Vaswani et al., 2017 ) of attention mechanisms. KV cache compression has emerged as a promising approach to alleviate computational and memory bottlenecks during inference, with studies demonstrating its potential to improve efficiency ( Zhang et al., 2023 ; Li et al., 2024 ; Lee et al., 2024 ; Liu et al., 2024a ; Ge et al., 2024 ; Adnan et al., 2024 ; Cai. et al., 2024 ) . While these methods typically rely on heuristic rules to compress or discard less critical KV elements, their effectiveness is often limited by accuracy trade-offs and constrained applicability in specific contexts. Recently, a novel approach called InfLLM has been proposed ( Xiao et al., 2024 ) , which introduces a block-based streaming mechanism, which can be likened to constructing a Full-Text Index while simultaneously performing Retrieval-Augmented Generation (RAG) ( Gao et al., 2024 ) . Although this design aligns closely with human intuition for managing large volumes of information—storing older information and retrieving it as needed, its effectiveness is heavily influenced by the quality of text index construction and retrieval processes, underscoring the importance of robust indexing and retrieval mechanisms in achieving optimal results. We evaluate InfLLM on the LLAMA3-8B-Instruct-262K 1 1 1 https://huggingface.co/gradientai/Llama-3-8B-Instruct-262k model on a set of Needle-In-A-Haystack(NIAH) tests consisting of eight questions. As depicted in Figure 1 , InfLLM struggles to provide correct answers. Our analysis revealed that the majority of InfLLM’s failed cases originate from overlooking of the crucial tokens with low attention scores. Figure 1: Average Needle-In-A-Haystack performance of InfLLM on a set of NIAH tests consisting of eight questions. More details can be found in Appendix A . In this paper, we address this issue by preserving independent semantic spans to the greatest extent possible. Our findings reveal that the attention distributions of LLMs exhibit strong local correlations, manifesting as multiple triangular regions in the attention map. These triangular patterns naturally correspond to the model’s interpretation of semantic segmentation. Building on this observation, we employ the Non-Maximum Suppression (NMS) technique to develop a simple yet effective algorithm for identifying the boundaries of these spans. Subsequently, we dynamically generate index vectors for each span by leveraging a “voting” mechanism among its neighboring spans. In summary, our contributions are as follows: • We investigate the reason why InfLLM struggles in NIAH test and identify that in the correct cases, the model’s recall is significantly higher than the wrong cases, and the recall varies considerably across different layers. Further, we attempt to analyze the effect of mandatory evidences injection, we found it can improve the accuracy, but it still largely depends on the model’s inherent capabilities. • Referring to the steps of InfLLM, we propose a novel method Ltri-LLM , which can efficiently and flexibly identifies semantic spans of the long context and store them in an offline cache, then retrieve them accurately when needed. • We employ LLAMA3-8B-Instruct-262K as the base model and conduct thorough evaluation on the long context benchmarks, including NIAH, \infty -Bench ( Zhang et al., 2024 ) and RULER ( Hsieh et al., 2024 ) . Experimental results show that Ltri-LLM can achieve promising performance while maintaining equally computation cost as InfLLM. 2 Preliminaries In this section, we firstly introduce the overall framework of InfLLM, including the KV offloading and retrieval process. Then, through the analysis of recall and success rate on NIAH test, we prove that the bottleneck of InfLLM lies in the performance of retrieval. Background. InfLLM splits the tokens into three parts in order, i.e., the Initial tokens \Lambda of length L_{init} , the Evicted tokens \mathcal{E} of length L_{ret} and the Local tokens \mathcal{L} of length L_{win} . \mathcal{L} are responsible for modeling local dependencies and the \Lambda (also known as Attention Sinks) maintain the numerical stability of the attention distribution. InfLLM processes the tokens in a streaming manner. At each step, it retrieves constant number of relevant blocks as \mathcal{E} from the context memory using the similarity score and apply attention to the concatenation of \Lambda,\mathcal{E},\mathcal{L} . When the length of the input tokens exceeds L_{win} , it stores tokens from the beginning of \mathcal{L} to context memory, picking tokens with high attention scores as the index vectors. Response Quality Hinges on Recall. We construct a group of NIAH tests with eight bilingual questions. More details are shown in Appendix A . We carefully record whether the needle is incorporated in the retrieved blocks or not at each decoding step. The model’s responses are scored by GPT-4 ( OpenAI et al., 2024 ) , only the responses with the highest score are considered as successful ones. We plot the average recall across different decoder layers and decoding steps. Figure 2 demonstrates the needle recall for both successful and failed instances. Obviously, there is a discernible trend shows that the successful cases have a much higher recall comparing to the failed cases. (a) Average on 11 successful samples with 26 decoding steps. (b) Average on 212 failed samples with 19 decoding steps. Figure 2: The average needle recall across layers and decoding steps of successful and failed NIAH cases. Mandatory Evidence Injection Transforms Unreasonable Responses. The observed relationship raises the question of whether increasing the recall could transform failed cases into successful ones. We validate this hypothesis by mandatorily injecting the blocks containing the needle into \mathcal{E} on the failed cases. The results of conversion are shown in Table 1 . After the mandatory injection, nearly all English NIAH cases are successfully converted, whereas the lower conversion rate of Chinese NIAH cases is probably