# How Sparse Attention Approximates Exact Attention? Your Attention is Naturally nC-Sparse

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2024.

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

- [Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond](https://mlsanity.com/paper/2405.03251/) (2024)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [SlimInfer: Accelerating Long-Context LLM Inference via Dynamic Token Pruning](https://mlsanity.com/paper/2508.06447/) (2025)
- [Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction](https://mlsanity.com/paper/2605.09649/) (2026)
- [Towards Infinite-Long Prefix in Transformer](https://mlsanity.com/paper/2406.14036/) (2024)
- [Vegas: Self-Speculative Decoding with Verification-Guided Sparse Attention](https://mlsanity.com/paper/2602.07223/) (2026)
- [AdaCluster: Adaptive Query-Key Clustering for Sparse Attention in Video Generation](https://mlsanity.com/paper/2604.18348/) (2026)
- [Unlocking the Theory Behind Scaling 1-Bit Neural Networks](https://mlsanity.com/paper/2411.01663/) (2024)
- [Unifying Learning Dynamics and Generalization in Transformers Scaling Law](https://mlsanity.com/paper/2512.22088/) (2025)
- [Gradient Flow Polarizes Softmax Outputs towards Low-Entropy Solutions](https://mlsanity.com/paper/2603.06248/) (2026)
- [NABLA: Neighborhood Adaptive Block-Level Attention](https://mlsanity.com/paper/2507.13546/) (2025)
- [Optimizing Native Sparse Attention with Latent Attention and Local Global Alternating Strategies](https://mlsanity.com/paper/2511.00819/) (2025)
- [Grokking as Structural Inference: Transformers Need Bayesian Lottery Tickets](https://mlsanity.com/paper/2605.15787/) (2026)
- [Language Models Can Control Their Own Attention](https://mlsanity.com/paper/2609.02737/) (2026)
- [HierEdit: Region-Aware Hierarchical Diffusion for Efficient High-Resolution Editing](https://mlsanity.com/paper/2605.17294/) (2026)
- [Beyond Sparse Weights: When Is Attention Compressible?](https://mlsanity.com/paper/2608.21541/) (2026)
- [What Pretraining and Midtraining Make Learnable from Rewards?](https://mlsanity.com/paper/2609.38446/) (2026)

## Abstract (arXiv)

Sparse Attention is a technique that approximates standard attention computation with sub-quadratic complexity. This is achieved by selectively ignoring smaller entries in the attention matrix during the softmax function computation. Variations of this technique, such as pruning KV cache, sparsity-based fast attention, and Sparse Transformer, have been extensively utilized for efficient Large Language Models (LLMs) deployment. Despite its widespread use, a theoretical understanding of the conditions under which sparse attention performs on par with traditional attention remains elusive. This work aims to bridge this gap by examining the inherent sparsity of standard attention processes. Our theoretical framework reveals several brand-new key insights: bullet Attention is nC-sparse, implying that considering only the largest Omega(nC) entries out of all n entries is sufficient for sparse attention to approximate the exact attention matrix with decreasing loss. Here, n represents the input length and C ∈ (0, 1) is a constant. bullet Stable o(log(n))-sparse attention, which approximates attention computation with log(n) or fewer entries, may not be feasible since the error will persist at a minimum of O(1). bullet An adaptive strategy (α · nC, α ∈ ℝ) for the window size of efficient attention methods rather than a fixed one is guaranteed to perform more accurately and efficiently in a task for inference on flexible context lengths.