ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers

Mahdi Heidari, Mohammad Mahdi Rahimi, Jaekyun Moon

arXiv:2607.20214 [cs.LG] · 2026 · DOI: 10.48550/arXiv.2607.20214

Abstract

The quadratic N × N attention score matrix remains a central obstacle to extending Transformers to longer input lengths. Existing efficient attention methods usually reduce this bottleneck by either imposing sparsity, so that each query attends to only a small subset of keys, or by using low-rank or kernel sketches, so that global interactions are compressed into a lower-dimensional representation. We propose ELSAA, an efficient low-rank and sparse approximation of attention. ELSAA approximates the induced attention score operator itself: a sparse branch captures selected high-similarity interactions, while a low-rank branch summarizes diffuse global interactions. A denominator-aware fusion term scales the sparse branch according to its estimated attention mass relative to the low-rank branch. This provides a practical framework for constructing low-rank and sparse attention outputs without materializing the full quadratic score matrix.

Canonical citation

Heidari, M., Rahimi, M. M., & Moon, J. (2026). ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers. arXiv:2607.20214.

@misc{heidari2026elsaa,
  title = {ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers},
  author = {Heidari, Mahdi and Rahimi, Mohammad Mahdi and Moon, Jaekyun},
  year = {2026},
  eprint = {2607.20214},
  archivePrefix = {arXiv},
  primaryClass = {cs.LG},
  doi = {10.48550/arXiv.2607.20214}
}

Archive note: this author-hosted PDF preserves the visible pages of the official version. Only embedded document metadata was normalized so title and author fields match the title page.