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

• URL: http://arxiv.org/abs/2607.20214v1
• Date: Wed, 22 Jul 2026 14:34:49 GMT
• Title: ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
• Abstract summary: We propose emphELSAA, an efficient low-rank and sparse approximation of attention.<n>A sparse branch captures selected high-similarity interactions, while a low-rank branch summarizes diffuse global interactions.<n>This gives a practical framework for constructing low-rank and sparse attention outputs without materializing the full quadratic score matrix.
• Score: 12.266057437036906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quadratic $N\times 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/kernel sketches, so that global interactions are compressed into a lower-dimensional representation. We propose \emph{ELSAA}, an efficient low-rank and sparse approximation of attention. Importantly, ELSAA does \emph{not} decompose the learned projection or output matrices of the Transformer into sparse and low-rank factors. Instead, after dense projections produce $Q,K,V$, 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. Since the two branches can be normalized over supports with very different denominator mass, ELSAA introduces a denominator-aware fusion term that scales the sparse branch according to its estimated attention mass relative to the low-rank branch. This gives a practical framework for constructing low-rank and sparse attention outputs without materializing the full quadratic score matrix, aiming to enable longer-context training while preserving both sharp token-level interactions and broad contextual mixing.

Related papers

• Scaling Attention via Feature Sparsity [50.64995497733461]
  Scaling Transformers to ultra-long contexts is bottlenecked by the $O(n2 d)$ cost of self-attention.<n>We propose Sparse Feature Attention, where queries and keys are represented as $k$-sparse codes that preserve high-dimensional expressivity.<n>Across GPT-2 and Qwen3 pretraining, SFA matches dense baselines while improving speed by up to $2.5times$ and reducing FLOPs and KV-cache by nearly 50%.
  arXiv  Detail & Related papers  (2026-03-17T08:41:50Z)
• Trainable Log-linear Sparse Attention for Efficient Diffusion Transformers [36.26426380985327]
  Diffusion Transformers (DiTs) set the state of the art in visual generation, yet their quadratic self-attention cost limits scaling to long token sequences.<n>Recent Top-K sparse attention approaches reduce the computation of DiTs by compressing tokens into block-wise representation.<n>We introduce Log-linear Sparse Attention (LLSA), a trainable sparse attention mechanism for extremely long token sequences.
  arXiv  Detail & Related papers  (2025-12-18T14:53:12Z)
• Sparse Attention Post-Training for Mechanistic Interpretability [55.030850996535776]
  We introduce a simple post-training method that makes transformer attention sparse without sacrificing performance.<n>Applying a flexible sparsity regularisation under a constrained-loss objective, we show on models up to 1B parameters that it is possible to retain the original pretraining loss while reducing attention connectivity to $approx 0.3 % of its edges.
  arXiv  Detail & Related papers  (2025-12-05T16:40:08Z)
• Nexus: Higher-Order Attention Mechanisms in Transformers [82.07756094886552]
  Transformers have achieved significant success across various domains, relying on self-attention to capture dependencies.<n>In this paper, we propose the Nexus, a novel architecture designed to enhance representational power through a recursion framework.<n>We provide theoretical analysis demonstrating that our method breaks the linear bottleneck of standard attention. Empirically, Nexus outperforms standard Transformers on multiple benchmarks.
  arXiv  Detail & Related papers  (2025-12-03T02:25:38Z)
• OmniSAT: Compact Action Token, Faster Auto Regression [70.70037017501357]
  We introduce an Omni Swift Action Tokenizer, which learns a compact, transferable action representation.<n>The resulting discrete tokenization shortens the training sequence by 6.8$times$, and lowers the target entropy.
  arXiv  Detail & Related papers  (2025-10-08T03:55:24Z)
• ToMA: Token Merge with Attention for Diffusion Models [8.079656935981193]
  Diffusion models excel in high-fidelity image generation but face scalability limits due to transformers' quadratic attention complexity.<n>We propose Token Merge with Attention (ToMA), an off-the-shelf method that negates token reduction for GPU-aligned efficiency.<n>ToMA reduces SDXL/Flux generation latency by 24%/23%, respectively (with DINO $Delta 0.07$), outperforming prior methods.
  arXiv  Detail & Related papers  (2025-09-13T17:35:00Z)
• SEA: Sparse Linear Attention with Estimated Attention Mask [51.22399593954608]
  Long seqeuences pose a problem due to the quadratic complexity of the attention operation. Previous research has aimed to lower the complexity by sparsifying or linearly approximating the attention matrix. We propose SEA: Sparse linear attention with an Estimated Attention mask.
  arXiv  Detail & Related papers  (2023-10-03T03:56:26Z)
• Diffuser: Efficient Transformers with Multi-hop Attention Diffusion for Long Sequences [16.066338004414092]
  textitDiffuser is a new efficient Transformer for sequence-to-sequence modeling. It incorporates all token interactions within one attention layer while maintaining low computation and memory costs. We show its ability to approximate full-attention by analyzing the graph expander property from the spectral perspective.
  arXiv  Detail & Related papers  (2022-10-21T08:13:34Z)
• CloudAttention: Efficient Multi-Scale Attention Scheme For 3D Point Cloud Learning [81.85951026033787]
  We set transformers in this work and incorporate them into a hierarchical framework for shape classification and part and scene segmentation. We also compute efficient and dynamic global cross attentions by leveraging sampling and grouping at each iteration. The proposed hierarchical model achieves state-of-the-art shape classification in mean accuracy and yields results on par with the previous segmentation methods.
  arXiv  Detail & Related papers  (2022-07-31T21:39:15Z)
• Combiner: Full Attention Transformer with Sparse Computation Cost [142.10203598824964]
  We propose Combiner, which provides full attention capability in each attention head while maintaining low computation complexity. We show that most sparse attention patterns used in existing sparse transformers are able to inspire the design of such factorization for full attention. An experimental evaluation on both autoregressive and bidirectional sequence tasks demonstrates the effectiveness of this approach.
  arXiv  Detail & Related papers  (2021-07-12T22:43:11Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  We show that sparse Transformers with only $O(n)$ connections per attention layer can approximate the same function class as the dense model with $n2$ connections. We also present experiments comparing different patterns/levels of sparsity on standard NLP tasks.
  arXiv  Detail & Related papers  (2020-06-08T18:30:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.