# On the Trade-off Between Information Loss and Generalization in Sparse Attention

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 35 references that are in the map.
- First posted on arXiv 3 Oct 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Stabilizing Transformer Training by Preventing Attention Entropy Collapse](https://mlsanity.com/paper/2303.06296/) (2023)
- [O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformers](https://mlsanity.com/paper/2006.04862/) (2020)
- [On the Expressive Power of Self-Attention Matrices](https://mlsanity.com/paper/2106.03764/) (2021)
- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Sequence Length Independent Norm-Based Generalization Bounds for Transformers](https://mlsanity.com/paper/2310.13088/) (2023)
- [The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs](https://mlsanity.com/paper/2504.17768/) (2025)
- [Softmax is 1/2-Lipschitz: A tight bound across all ℓp norms](https://mlsanity.com/paper/2510.23012/) (2025)
- [HybridNorm: Towards Stable and Efficient Transformer Training via Hybrid Normalization](https://mlsanity.com/paper/2503.04598/) (2025)
- [Taming Transformer Without Using Learning Rate Warmup](https://mlsanity.com/paper/2505.21910/) (2025)
- [Graph-Aware Isomorphic Attention for Adaptive Dynamics in Transformers](https://mlsanity.com/paper/2501.02393/) (2025)
- [On the Benefits of Rank in Attention Layers](https://mlsanity.com/paper/2407.16153/) (2024)
- [Connecting Jensen-Shannon and Kullback-Leibler Divergences: A New Bound for Representation Learning](https://mlsanity.com/paper/2510.20644/) (2025)
- [Lil: Less is Less When Applying Post-Training Sparse-Attention Algorithms in Long-Decode Stage](https://mlsanity.com/paper/2601.03043/) (2026)
- [Generalization Bounds for Transformer Channel Decoders](https://mlsanity.com/paper/2601.06969/) (2026)
- [Rank-Aware Spectral Bounds on Attention Logits for Stable Low-Precision Training](https://mlsanity.com/paper/2602.18851/) (2026)

## Abstract (arXiv)

To mitigate the quadratic complexity bottleneck of the Transformer, sparse attention has emerged as a pivotal technology. Despite the extensive empirical success of sparse Transformers, the theoretical understanding of sparse attention remains fragmented. In particular, two fundamental questions remain unclear: (1) How does sparsification affect the information fidelity of attention mechanisms? (2) How does this information loss interact with the generalization behavior of the model? To bridge this gap, this paper proposes a systematic analysis of the Jensen-Shannon (JS) divergence and of the generalization gap of sparse attention mechanisms. Specifically, we first characterize the approximation error via the JS divergence. Through an order-statistics-based concentration analysis of the truncation mass alpha --- where the attention scores are assumed to be independent and identically distributed sub-Gaussian random variables with parameter sigma --- the JS divergence between the full attention distribution and the sparse attention distribution is shown to admit the closed form log 2 + ((1 - alpha)/2) log(1 - alpha) - ((2 - alpha)/2) log(2 - alpha). Subsequently, we derive a generalization bound through Rademacher complexity, quantified by O(gamma * sqrt(M/n) * (sqrt(log(3eL/M)) + sqrt(pi)/2)). Furthermore, building on a mutual-information-based generalization bound together with an entropy and covering-number analysis of the sparse hypothesis class, we obtain the sparsity-dependent generalization bound O(sqrt((M/(2n)) * (log(eL/M) + log(1 + 2/epsilon)))). Our analysis shows that sparsity reduces the complexity of the considered hypothesis class while introducing approximation error that can be quantified by the JS divergence. These findings provide a theoretical characterization of the trade-off between information fidelity and generalization in sparse Transformer architectures.