Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs

Kan Zhu, Tian Tang, Qinyu Xu, Yile Gu, Zhichen Zeng, Rohan Kadekodi, Liangyu Zhao, Ang Li, Arvind Krishnamurthy, Baris Kasikci · 2025

Read Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs by Kan Zhu, Tian Tang, Qinyu Xu, Yile Gu, Zhichen Zeng, Rohan Kadekodi, Liangyu Zhao, Ang Li, Arvind Krishnamurthy, Baris Kasikci (2025) 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-2502-12216.txt.

Introduction

Kan Zhu and co-authors presented a sparse attention method in 2025 for long-context language models. Loading huge key-value caches during generation is slow, and earlier sparse methods fix a token budget for every head and layer. Attention importance, though, varies widely by place and context.

Their method, Tactic, picks tokens by cumulative attention score against a target share of the total, so selection adapts to how concentrated attention is. Clustering-based sorting and distribution fitting estimate importance cheaply. Tactic beat existing sparse methods on accuracy and sped the attention step of decoding up to about sevenfold, giving an overall generation speedup. It needs no calibration, aiding adoption in accuracy-sensitive uses.

Catalog record

CREATORKan Zhu, Tian Tang, Qinyu Xu, Yile Gu, Zhichen Zeng, Rohan Kadekodi, Liangyu Zhao, Ang Li, Arvind Krishnamurthy, Baris Kasikci
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12216

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tactic: Adaptive Sparse Attention with Clustering and Distribution Fitting for Long-Context LLMs Kan Zhu, Tian Tang, Qinyu Xu, Yile Gu, Zhichen Zeng, Rohan Kadekodi, Liangyu Zhao, Ang Li, Arvind Krishnamurthy, Baris Kasikci Abstract Long-context models are essential for many applications but face inefficiencies in loading large KV caches during decoding. Prior methods enforce fixed token budgets for sparse attention, assuming a set number of tokens can approximate full attention. However, these methods overlook variations in the importance of attention across heads, layers, and contexts. To address these limitations, we propose Tactic, a sparsity-adaptive and calibration-free sparse attention mechanism that dynamically selects tokens based on their cumulative attention scores rather than a fixed token budget. By setting a target fraction of total attention scores, Tactic ensures that token selection naturally adapts to variations in attention sparsity. To efficiently approximate this selection, Tactic leverages clustering-based sorting and distribution fitting, allowing it to accurately estimate token importance with minimal computational overhead. We show that Tactic outperforms existing sparse attention algorithms, achieving superior accuracy and up to 7.29 × 7.29\times decode attention speedup. This improvement translates to an overall 1.58 × 1.58\times end-to-end inference speedup, making Tactic a practical and effective solution for long-context LLM inference in accuracy-sensitive applications. † † affiliationnotice: Equal contribution 1 Introduction Large language models (LLMs) power a wide range of applications, from conversational assistants to document analysis systems and search engines. The demand for multi-turn interactions and long-document processing has driven an expansion of context length, growing from thousands to as many as one million tokens ( Liu et al., 2024b ) . However, supporting long contexts in LLM inference presents significant challenges, primarily due to the growing memory footprint of the Key-Value (KV) cache ( Tang et al., 2024 ) . The memory requirements of the KV cache scale proportionally with the context length, therefore, it can quickly become a bottleneck despite optimizations such as Grouped-Query Attention (GQA) ( Ainslie et al., 2023 ) . Furthermore, the need to repeatedly load the KV cache for every generated token becomes a bottleneck. For instance, loading the large KV cache can account for over 50% of the total latency during auto-regressive decoding, significantly impeding the efficiency of large-scale serving systems. ( Tang et al., 2024 ) To mitigate the high cost of KV-cache loading, recent methods approximate full attention by selecting a subset of stored Key and Value vectors, corresponding to a subset of tokens, within a fixed token budget ( Liu et al., 2024a ; Tang et al., 2024 ; Zhang et al., 2023 ; Xiao et al., 2023 ) . These approaches exploit the natural sparsity of attention, where only a small fraction of tokens significantly influence the output due to the softmax operation. By leveraging this sparsity, they aim to reduce the overhead of loading the KV-cache without sacrificing model accuracy. Figure 1 : Comparison between fixed-budget-based methods and Tactic. Fixed-budget-based methods may select excessive tokens or have a large difference from full attention score. In contrast, Tactic dynamically selects tokens to efficiently approximate full attention based on a cumulative attention score, considering variation of sparsity across different query tokens and contexts. Alas, existing fixed budget-based methods have several shortcomings. Some methods employ a global fixed token budget ( Tang et al., 2024 ; Xiao et al., 2023 ; Zhang et al., 2023 ) , not accounting for variations in attention sparsity across attention heads, and layers. In practice, some attention heads focus on significantly more tokens than others, and the level of sparsity fluctuates across layers. More adaptive methods ( Cai et al., 2024 ; Feng et al., 2024 ; Ge et al., 2024 ) attempt to distribute token budgets more effectively using calibration data or predefined rules, but they remain constrained by static allocation and cannot adapt to query tokens and contexts, often leading to suboptimal approximations in different cases. To address the limitations of fixed-budget-based methods, we propose Tactic, a sparsity-adaptive and calibration-free post-training sparse attention mechanism that improves both the accuracy and efficiency of long-context LLM inference. Fig. 1 shows a comparison between existing fixed budget-based methods and Tactic. Instead of enforcing a fixed budget, Tactic dynamically selects tokens starting from ones with the highest attention score to ensure that their cumulative attention scores (where attention score represents the softmax output of the Query-Key product) reach a target fraction of the full attention score. Dynamic and selective accumulation of attention scores offers two key advantages. First, it provides inherent flexibility—Tactic selects fewer tokens in high-sparsity cases and more in low-sparsity cases without requiring calibration. Second, since attention scores are multiplied by V vectors with similar norms, and the selected attention scores cumulatively reach at least a fraction of the total attention score, a cumulative attention score target guarantees, unlike token budgets in prior works, a bounded difference between sparse and full attention (see Sec. 3.2 and App. A ). However, efficiently selecting tokens to reach a certain fraction P of cumulative attention score is challenging. To minimize the number of tokens selected (i.e., loads from memory), the optimal way is to select tokens following a descending order of attention score until the cumulative attention score surpasses P . Thus, similar to prior works, efficiently sorting tokens by their contribution to the cumulative attention score is crucial for Tactic. However, unlike fixed budget-based methods that simply stop at a fixed token count, Tactic must track cumulative attention score in real time, requiring the exact attention score values for each token, making the selection process more complex. To approximate optimal token selection, Tactic introduces two key techniques: clustering and distribution fitting. First, to efficiently sort tokens, Tactic clusters similar tokens to reduce computational overhead. However, we observe that positional proximity, which is used for clustering tokens by prior work ( Tang et al., 2024 ) , does not necessarily guarantee similarity in Key vectors, which are fundamental to attention computation. Since attention operates on Query-Key interactions rather than token positions, Tactic groups tokens using K-means clustering based on Key-vector similarity (i.e., vector distance). During decoding, Tactic approximates the sorted list of tokens by sorting clusters based on the similarity between Query vectors and cluster centroids. After approximating token sorting, Tactic estimates the attention score for each token by leveraging the observation that attention scores follow a smooth distribution. Using distribution fitting, Tactic effectively keep track of attained cumulative attention score to determine the end of selection. By loading only the cluster centroids along with a small sampled subset of tokens ( \sim 2.5\% of the KV cache size in practice), Tactic efficiently selects the most critical tokens that reach the target cumulative attention score. To balance efficiency and accuracy, Tactic performs full attention on newly generated tokens and updates the clustering every fixed number of decoding steps (e.g., 2048). Our experiments show that Tactic achieves superior and consistent accuracy compared to existing algorithms including Quest ( Tang et al., 2024 ) , PyramidKV ( Cai et al., 2024 ) and Ada-KV ( Feng et al., 2024 ) , offering a more effective solution for long-context LLM inference in accuracy-sensitive applications. Tactic achieves up to 7.29\times decode attention speedup, which leads to 1.58\times end-to-end speedup. In

Read the complete text