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

arXiv: https://arxiv.org/abs/2502.12216 · HTML: https://mlsanity.com/paper/2502.12216/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 20 of its 26 references that are in the map.
- First posted on arXiv 17 Feb 2025.

## Placed in

- Efficient LLM inference and serving / [KV cache optimization](https://mlsanity.com/inference/kv-cache-optimization/)

## Builds on (most cited first, 20 of 20)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints](https://mlsanity.com/paper/2305.13245/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers](https://mlsanity.com/paper/2105.03011/) (2021)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [Scaling Laws of RoPE-based Extrapolation](https://mlsanity.com/paper/2310.05209/) (2023)
- [NanoFlow: Towards Optimal Large Language Model Serving Throughput](https://mlsanity.com/paper/2408.12757/) (2024)
- [ClusterKV: Manipulating LLM KV Cache in Semantic Space for Recallable Compression](https://mlsanity.com/paper/2412.03213/) (2024)

## Built on by (most cited first, 24 of 24)

- [Sparse VideoGen2: Accelerate Video Generation with Sparse Attention via Semantic-Aware Permutation](https://mlsanity.com/paper/2505.18875/) (2025)
- [The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs](https://mlsanity.com/paper/2504.17768/) (2025)
- [SLA2: Sparse-Linear Attention with Learnable Routing and QAT](https://mlsanity.com/paper/2602.12675/) (2026)
- [SpargeAttention2: Trainable Sparse Attention via Hybrid Top-k+Top-p Masking and Distillation Fine-Tuning](https://mlsanity.com/paper/2602.13515/) (2026)
- [Multipole Attention for Efficient Long Context Reasoning](https://mlsanity.com/paper/2506.13059/) (2025)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [Accelerating Large-Scale Reasoning Model Inference with Sparse Self-Speculative Decoding](https://mlsanity.com/paper/2512.01278/) (2025)
- [vAttention: Verified Sparse Attention](https://mlsanity.com/paper/2510.05688/) (2025)
- [Double-P: Hierarchical Top-P Sparse Attention for Long-Context LLMs](https://mlsanity.com/paper/2602.05191/) (2026)
- [SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers](https://mlsanity.com/paper/2606.22874/) (2026)
- [SPLA: Block Sparse Plus Linear Attention for Long Context Modeling](https://mlsanity.com/paper/2601.22379/) (2026)
- [SOCKET: SOft Collision Kernel EsTimator for Sparse Attention](https://mlsanity.com/paper/2602.06283/) (2026)
- [MAGE: All-[MASK] Block Already Knows Where to Look in Block Diffusion LLM](https://mlsanity.com/paper/2602.14209/) (2026)
- [FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM Serving](https://mlsanity.com/paper/2608.19758/) (2026)
- [Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining](https://mlsanity.com/paper/2509.10406/) (2025)
- [S3-Attention:Attention-Aligned Endogenous Retrieval for Memory-Bounded Long-Context Inference](https://mlsanity.com/paper/2601.17702/) (2026)
- [Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache](https://mlsanity.com/paper/2605.06763/) (2026)
- [LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding](https://mlsanity.com/paper/2607.24555/) (2026)
- [EntmaxKV: Support-Aware Decoding for Entmax Attention](https://mlsanity.com/paper/2605.21649/) (2026)
- [GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization](https://mlsanity.com/paper/2609.36074/) (2026)
- [HHR: Hierarchical Hash Retrieval for Efficient LLM Generation](https://mlsanity.com/paper/2610.01230/) (2026)
- [MOIRA: Mass-Oriented Indexing with Ragged Attention for Long-Context Decoding](https://mlsanity.com/paper/2610.04313/) (2026)
- [Attention via Black-Box Vector Search](https://mlsanity.com/paper/2610.10135/) (2026)
- [Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values](https://mlsanity.com/paper/2610.10871/) (2026)

## Abstract (arXiv)

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.29x decode attention speedup. This improvement translates to an overall 1.58x end-to-end inference speedup, making Tactic a practical and effective solution for long-context LLM inference in accuracy-sensitive applications.