Metraipolis › archive › dc_61d4fc02aa53
On the Trade-off Between Information Loss and Generalization in Sparse Attention — arXiv:2610.04424
- Source
- arXiv
- Original
- https://arxiv.org/abs/2610.04424
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:30:33.816Z
- SHA-256 of the archived text
4ba98d63bd48553b8d96edb30183e045b28582e3af603fc6c45ebd2b72649de3- Stable URL of this page
https://metraipolis.com/documento/dc_61d4fc02aa53
How to cite
On the Trade-off Between Information Loss and Generalization in Sparse Attention — arXiv:2610.04424 — arXiv, https://arxiv.org/abs/2610.04424 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_61d4fc02aa53 (Metraipolis archive dc_61d4fc02aa53, sha256 4ba98d63bd48553b8d96edb30183e045b28582e3af603fc6c45ebd2b72649de3)
BibTeX
@misc{dc61d4fc02aa53,
title = {On the Trade-off Between Information Loss and Generalization in Sparse Attention — arXiv:2610.04424},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2610.04424},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_61d4fc02aa53; sha256 4ba98d63bd48553b8d96edb30183e045b28582e3af603fc6c45ebd2b72649de3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.04424. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno). Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML). Pagina del lavoro: https://arxiv.org/abs/2610.04424 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-06T05:27:05.680Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).