REVIEW 4 major objections 7 minor 45 references
ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
T0 review · 4 major / 7 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read ELSAA approximates the attention operator itself with a sparse branch, a low-rank branch, and a denominator-aware fusion multiplier, keeping training tractable at 64K tokens where dense attention stalls.
desk verdict A plausible denominator-aware fusion mechanism, but the 'exact attention fails at 64K' headline is undercut by the paper's own causal exact-attention results, and the empirical case needs stronger baselines, seeds, and a working code link. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the denominator-aware fusion formula m_sparse = d_sparse / (d_sparse + λ d_lr + ε), which rescales the sparse branch output proportionally to its estimated attention mass before adding the low-rank branch output. The sparse branch is instantiated with sorted LSH exact attention over fixed-size blocks, and the low-rank branch uses RACE soft hash-bucket summaries; both branches return denominator proxies as well as outputs. A gate network learns per-token mixing weights, and λ may be fixed, learned, or input-dependent. This fusion is what distinguishes ELSAA from a naive addition of sparse and low-rank attention.
What would settle it
Run a dense FlashAttention baseline on the Text Retrieval @ 64K task with a sweep of learning rates, warmup schedules, and random seeds, tracking train loss curves. If any reasonable configuration achieves substantially better than approximately 50% train accuracy, the claim that exact attention fails entirely is contradicted or at least unsupported.
Extended reading notes
Core claim
ELSAA shows that long-context attention can be treated as a sparse-plus-low-rank operator constructed after the dense projections produce Q, K, and V, rather than by decomposing the query/key/value projection matrices. The sparse branch uses sorted LSH to select high-similarity query-key pairs and computes exact attention on those blocks; the low-rank branch uses RACE-style hash-bucket summaries to supply global context. Since the two branches have very different denominator masses, a denominator-aware multiplier m_sparse = d_sparse / (d_sparse + λ d_lr + ε) rescales the sparse branch's contribution, and two learned gates blend the outputs token-wise. The paper also gives a rank-theoretic an
Load-bearing premise
The central empirical advantage—that exact attention fails entirely at 64K tokens—rests on a single Exactflash run, and if that run was under-tuned or poorly implemented, the headline comparison loses its main evidence.
Editorial extensions
If this is right
- Attention interaction cost drops from Θ(N²) to Θ(N(s + Ls·2^γ)), enabling 32K-64K training on a single 48GB GPU.
- The denominator-aware multiplier yields a consistent average improvement of about 1.33 percentage points over the same architecture without it, isolating the rescaling term's contribution.
- On NIAH, ELSAA reaches 100% accuracy up to 16K tokens and remains strong at 32K-64K, while the pure low-rank branch collapses and exact attention runs out of memory.
- At 64K-token text retrieval, exact dense attention reportedly fails to optimize (near-random performance), whereas ELSAA and the low-rank baseline reach meaningful accuracy, suggesting an implicit structural prior.
- The causal version of ELSAA matches or exceeds causal exact attention on long-context classification, including 64K-token ArXiv, supporting use in autoregressive models.
Reading between the lines
- If the reported 64K exact-attention failure is genuine and not a tuning artifact, it implies long-context training may require implicit structural regularization or optimization stabilization, not just faster exact kernels; this is testable by running exact FlashAttention at 64K with multiple learning-rate schedules and monitoring training loss.
- The denominator-aware fusion principle could extend beyond sparse-plus-low-rank hybrids: any combination of normalized attention estimators with different supports—such as mixed local-global attention or KV-cache eviction schemes—may benefit from explicit rescaling by relative denominator mass.
- The rank analysis suggests that 'sparse matching size + low-rank dimension ≥ n' is a sufficient condition for full-rank hybrid attention; this could serve as a design rule for future linear-attention variants aiming to avoid rank collapse.
- Learnable gates and input-dependent λ may allow the model to adapt branch contributions per depth, head, and position, potentially enabling scheduling of sparse versus global computation during pretraining.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes ELSAA, a training-time attention approximation that operates on Q,K,V rather than on learned weight matrices. It combines an exact sparse branch (sorted-LSH block attention) with a low-rank RACE branch, and fuses the two separately normalized outputs using token-wise gates and a denominator-aware multiplier m_sparse = d_sparse/(d_sparse + λ d_lr + ε). The authors provide non-causal and causal algorithms, a linear-complexity analysis, and a probabilistic rank theorem for the idealized unnormalized operator S_Ω + BA. Experiments cover long-document and image classification, binary text retrieval at 64K, a needle-in-a-haystack probe across lengths, and causal classification; the central empirical claims are that exact attention 'fails entirely' at 64K while ELSAA/RACE train, and that m_sparse gives a consistent +1.33 pp average improvement over no-rescale fusion.
Significance. If the empirical claims held up, ELSAA would be a useful hybrid: the denominator-aware rescaling addresses a real scale-mismatch problem, and the causal extensions are substantial implementation work. The paper has genuine strengths: a clean single-term ablation (ELSAA vs. Sort Lsh RACE), an internally coherent rank proof under explicit assumptions, linear-complexity accounting with concrete interaction counts, and claimed code availability. The main obstacles are empirical: the headline 'exact attention fails' is supported by an apparently untuned exact run and contradicted by the paper's own causal exact result, and all tables are single-seed. The rank theory, while coherent, is not connected to the normalized fused estimator. These issues are fixable but require additional experiments and reframing.
major comments (4)
- [§7, Tables 1–2, 4–5] The central claim that exact attention 'fails entirely' at 64K rests on one Exactflash run (Table 2: ≈50% train/test) with no loss curves, gradient statistics, learning-rate sweeps, or seeds. This is contradicted by the same paper's causal Exactflash at the same length: Table 5 reports 99.83% train / 87.44% test on ArXiv @64K, showing dense attention can optimize at 64K. The retrieval failure therefore looks task/recipe-specific. The exact-baseline problem is broader: in Table 1, Exactflash at ArXiv @32K reaches only 81.77% train while RACE reaches 100.00% train under the stated shared protocol, and Table 4 reports Exactflash OOM at 32K while Tables 2/5 run exact attention at 64K. A properly tuned dense baseline with learning curves and multiple seeds is required before the 'exact fails' narrative can be accepted.
- [§7, Table 1; Appendix D] The only ablation isolating the main novelty—ELSAA versus Sort Lsh RACE—is a single-seed comparison. The +1.33 pp average (46.81% vs 45.48%) is not accompanied by error bars, seed counts, or significance tests; on tasks where the differences are a few points, seed variance can plausibly reverse the ranking. Appendix D states 'fix the random seed to 42,' confirming a single seed. Multi-seed results and variance should be reported for Tables 1–5, especially for the m_sparse ablation.
- [§4, Assumption 4.3, Eq. (6); §8] The rank theory is not connected to the ELSAA output actually trained. Proposition 4.5 and Theorem 4.6 analyze rank(S_Ω + BA), an unnormalized, ungated matrix whose sparse support is drawn from independent Bernoulli angular collisions. Algorithm 1 uses deterministic sortLSH block selection, normalized softmax denominators, learned gates, and m_sparse; full rank of S_Ω + BA does not imply a statement about the approximation error or optimization behavior of the fused output in Eq. (6). Section 8 explicitly concedes that the paper 'does not directly analyze the bias and variance' of the fused estimator, and Remark C.7 disclaims the independence model. The theory should be reframed as motivation or extended to the actual fused estimator.
- [§6, Algorithm 5] The linear-complexity claim is only analyzed for the non-causal case. Causal sortLSH (Algorithm 5) recursively calls CAUSALSPARSE on both halves and applies non-causal SORTLSH to each future–past block; the recurrence is at least T(n) = 2T(n/2) + Θ(ns), yielding Θ(ns log n) interactions, with further sorting overhead. Yet the conclusion states the method 'is linear in sequence length.' Since causal ELSAA is evaluated at 64K, the paper should either prove a linear bound for the causal sparse branch or report the correct subquadratic (log-linear) complexity.
minor comments (7)
- [§4] Proposition 4.5 says 'Under Theorem 4.4' and Theorem 4.6 says 'suppose Theorems 4.3 and 4.4 hold'; these should refer to Assumptions 4.3 and 4.4.
- [References] Han et al., 2024b is cited as 'arXiv:2401.XXXX' (placeholder), and the code link says 'available here' without a URL in the text. Both need completion.
- [§7, first paragraph] 'Tables 5–4 compare ELSAA...' should be 'Tables 1–4 compare...' or another correct range.
- [Eqs. (3)–(5)] Notation is inconsistent: the text uses 'osparse' in Eq. (3), and 'λ id_lr,i' in Eq. (5) vs 'λ_i d_lr,i' in Eq. (4). Make multiplication and subscripts uniform.
- [§2 and §5] Scatterbrain is discussed at length as the closest sparse-plus-low-rank method, but no Scatterbrain baseline appears in any experiment. A comparison or an explicit justification for its omission is needed.
- [Table 7, Algorithms 2–3] Table 7 lists 'RACE ensembles M' per setting, but Algorithms 2 and 3 do not define or use an ensemble dimension; clarify the relationship.
- [Table 5] The causal experiments omit Sort Lsh RACE, so the m_sparse ablation is not validated in the causal setting; this should be noted in the limitations or addressed with an additional ablation.
Circularity Check
No circular derivation: ELSAA's fusion rule is an explicit construction, no fitted parameter is disguised as a prediction, and the rank theorem is conditional on stated idealized assumptions.
full rationale
Walking the derivation chain, ELSAA's components are all defined rather than assumed into existence. The sparse branch returns exact block attention with a denominator d_sparse; the low-rank branch returns a RACE-style output with a denominator proxy d_lr; the fusion multiplier m_sparse,i = d_sparse,i / (d_sparse,i + λ_i d_lr,i + eps) is introduced as a construction (Eqs. 4-6), not derived from a claim that then reduces to itself. The ablation vs. Sort Lsh RACE is an honest empirical test of a fixed architectural variant, not a prediction of a fitted value. The rank analysis (Theorem 4.6 and Corollaries) is explicitly conditional on Assumptions 4.3-4.4 (independent Bernoulli edges, generic sparse values, generic low-rank factors), so it is an expressivity statement about an idealized operator rather than a restatement of the experimental results; the paper itself notes in Section 8 that the rank analysis 'does not directly analyze the bias and variance of ELSAA's normalized branch outputs under the denominator-aware fusion rule.' No load-bearing self-citation appears: the RACE and sortLSH building blocks are cited to external groups, and no uniqueness theorem from the present authors is invoked. The main weaknesses are empirical and derivational, not circular: the 'exact attention fails entirely' claim at 64K rests on a single Exactflash run without loss curves or LR ablations and sits in tension with the paper's own causal Exactflash result at the same length (Table 5: 99.83% train / 87.44% test), and the fusion formula lacks a bias-variance justification. These are evidence-quality gaps, not reductions of the output to the input by construction.
Assumptions & free parameters
free parameters (7)
- sortLSH block size s (b) =
32–256 depending on dataset
- RACE hash bits γ =
2–4 depending on dataset
- RACE number of tables L_s =
2–5 depending on dataset
- RACE soft-hash temperature β =
not reported
- fusion coefficient λ =
scalar λ: init 1.0, learned; input-dependent λ: c init 0.3, w init std 1e-3, bias init avg 0.8
- gate network Gθ =
hidden dim 64–128
- numerical floor ε =
1e-6
assumptions (5)
- domain assumption Assumption 4.3: independent angular edge model Ω_ij ~ Bernoulli(q_ij) independently
- domain assumption Assumption 4.4: nonzero sparse entries and low-rank factors are generic/absolutely continuous
- domain assumption Attention score matrices can be represented as sparse + low-rank
- domain assumption Exact dense attention's 64K failure is an optimization property, not a hyperparameter artifact
- standard math Standard rank facts: rank subadditivity, Hall's theorem, nonzero determinant polynomial a.s., Hoeffding inequality
Cite this review
Pith. "Pith review of ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers." pith.science (2026). https://pith.science/paper/I2K3SFEC
@misc{pith2026260720214,
author = {Pith},
title = {Pith review of: ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers},
year = {2026},
howpublished = {\url{https://pith.science/paper/I2K3SFEC}},
note = {Machine review of arXiv:2607.20214}
}
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.
Reference graph
Works this paper leans on
-
[1]
Advances in Neural Information Processing Systems , year=
Attention Is All You Need , author=. Advances in Neural Information Processing Systems , year=
-
[2]
Devlin, Jacob and Chang, Ming-Wei and Lee, Kenton and Toutanova, Kristina , booktitle=
-
[3]
Advances in Neural Information Processing Systems , year=
Language Models are Few-Shot Learners , author=. Advances in Neural Information Processing Systems , year=
-
[4]
International Conference on Learning Representations , year=
An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale , author=. International Conference on Learning Representations , year=
-
[5]
arXiv preprint arXiv:2302.13971 , year=
LLaMA: Open and Efficient Foundation Language Models , author=. arXiv preprint arXiv:2302.13971 , year=
-
[6]
and Ermon, Stefano and Rudra, Atri and R
Dao, Tri and Fu, Daniel Y. and Ermon, Stefano and Rudra, Atri and R. FlashAttention: Fast and Memory-Efficient Exact Attention with. Advances in Neural Information Processing Systems , year=
-
[7]
arXiv preprint arXiv:2307.08691 , year=
FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning , author=. arXiv preprint arXiv:2307.08691 , year=
-
[8]
arXiv preprint arXiv:1904.10509 , year=
Generating Long Sequences with Sparse Transformers , author=. arXiv preprint arXiv:1904.10509 , year=
arXiv 1904
Show all 45 references
-
[9]
arXiv preprint arXiv:2004.05150 , year=
Longformer: The Long-Document Transformer , author=. arXiv preprint arXiv:2004.05150 , year=
2004 arXiv
-
[10]
Advances in Neural Information Processing Systems , year=
Big Bird: Transformers for Longer Sequences , author=. Advances in Neural Information Processing Systems , year=
-
[11]
International Conference on Learning Representations , year=
Reformer: The Efficient Transformer , author=. International Conference on Learning Representations , year=
-
[12]
Transactions of the Association for Computational Linguistics , volume=
Efficient Content-Based Sparse Attention with Routing Transformers , author=. Transactions of the Association for Computational Linguistics , volume=
-
[13]
, journal=
Daras, Giannis and Kitaev, Nikita and Odena, Augustus and Dimakis, Alexandros G. , journal=
-
[14]
arXiv preprint arXiv:2006.04768 , year=
Linformer: Self-Attention with Linear Complexity , author=. arXiv preprint arXiv:2006.04768 , year=
2006 arXiv
-
[15]
Transformers are
Katharopoulos, Angelos and Vyas, Apoorv and Pappas, Nikolaos and Fleuret, Fran. Transformers are. International Conference on Machine Learning , year=
-
[16]
International Conference on Learning Representations , year=
Rethinking Attention with Performers , author=. International Conference on Learning Representations , year=
-
[17]
International Conference on Learning Representations , year=
Random Feature Attention , author=. International Conference on Learning Representations , year=
-
[18]
Xiong, Yunyang and Zeng, Zhanpeng and Chakraborty, Rudrasis and Tan, Mingxing and Fung, Glenn and Li, Yin and Singh, Vikas , booktitle=. Nystr
-
[19]
2026 , url=
Joshi, Sahil and Chowdhury, Agniva and Kanakamedala, Amar and Singh, Ekam and Tu, Evan and Shrivastava, Anshumali , booktitle=. 2026 , url=
2026
-
[20]
arXiv preprint arXiv:2011.04006 , year=
Long Range Arena: A Benchmark for Efficient Transformers , author=. arXiv preprint arXiv:2011.04006 , year=
2011 arXiv
-
[21]
ACM Computing Surveys , volume=
Efficient Transformers: A Survey , author=. ACM Computing Surveys , volume=
-
[22]
Advances in Neural Information Processing Systems , year=
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation , author=. Advances in Neural Information Processing Systems , year=
-
[23]
Journal of the ACM , volume=
Robust Principal Component Analysis? , author=. Journal of the ACM , volume=
-
[24]
SIAM Journal on Optimization , volume=
Rank-Sparsity Incoherence for Matrix Decomposition , author=. SIAM Journal on Optimization , volume=
-
[25]
and Shen, Yelong and Wallis, Phillip and Allen-Zhu, Zeyuan and Li, Yuanzhi and Wang, Shean and Wang, Lu and Chen, Weizhu , booktitle=
Hu, Edward J. and Shen, Yelong and Wallis, Phillip and Allen-Zhu, Zeyuan and Li, Yuanzhi and Wang, Shean and Wang, Lu and Chen, Weizhu , booktitle=
-
[26]
arXiv preprint arXiv:2209.13569 , year=
Exploring Low Rank Training of Deep Neural Networks , author=. arXiv preprint arXiv:2209.13569 , year=
-
[27]
Lialin, Vladislav and Muckatira, Sherin and Shivagunde, Namrata and Rumshisky, Anna , booktitle=
-
[28]
Zhao, Jiawei and Zhang, Zhenyu and Chen, Beidi and Wang, Zhangyang and Anandkumar, Anima and Tian, Yuandong , booktitle=
-
[29]
Han, Andi and Li, Jiaxiang and Huang, Wei and Hong, Mingyi and Takeda, Akiko and Jawanpuria, Pratik and Mishra, Bamdev , booktitle=
-
[30]
Advances in Neural Information Processing Systems , year =
Zhang, Zhenyu and Sheng, Ying and Zhou, Tianyi and Chen, Tianlong and Zheng, Lianmin and Cai, Ruisi and Song, Zhao and Tian, Yuandong and R. Advances in Neural Information Processing Systems , year =
-
[31]
2024 , eprint =
Efficient Streaming Language Models with Attention Sinks , author =. 2024 , eprint =
2024
-
[32]
2024 , publisher =
Tang, Jiaming and Zhao, Yilong and Zhu, Kan and Xiao, Guangxuan and Kasikci, Baris and Han, Song , booktitle =. 2024 , publisher =
2024
-
[33]
and Li, Dongsheng and Lin, Chin-Yew and Yang, Yuqing and Qiu, Lili , booktitle =
Jiang, Huiqiang and Li, Yucheng and Zhang, Chengruidong and Wu, Qianhui and Luo, Xufang and Ahn, Surin and Han, Zhenhua and Abdi, Amir H. and Li, Dongsheng and Lin, Chin-Yew and Yang, Yuqing and Qiu, Lili , booktitle =
-
[34]
2023 , publisher =
Li, Yixiao and Yu, Yifan and Zhang, Qingru and Liang, Chen and He, Pengcheng and Chen, Weizhu and Zhao, Tuo , booktitle =. 2023 , publisher =
2023
-
[35]
2405.16325 , archivePrefix =
Mozaffari, Mohammad and Yazdanbakhsh, Amir and Zhang, Zhao and Mehri Dehnavi, Maryam , year =. 2405.16325 , archivePrefix =
-
[36]
Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics , pages=
Learning Word Vectors for Sentiment Analysis , author=. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics , pages=
-
[37]
European Conference on Computer Vision (ECCV) , pages=
Food-101 -- Mining Discriminative Components with Random Forests , author=. European Conference on Computer Vision (ECCV) , pages=
-
[38]
arXiv preprint arXiv:1708.07747 , year=
Fashion-MNIST: A Novel Image Dataset for Benchmarking Machine Learning Algorithms , author=. arXiv preprint arXiv:1708.07747 , year=
-
[39]
Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing , year=
Automated Flower Classification over a Large Number of Classes , author=. Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing , year=
-
[40]
IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages=
Cats and Dogs , author=. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , pages=
-
[41]
arXiv preprint arXiv:2401.XXXX , year=
HyperAttention: Long-context Attention in Near-Linear Time , author=. arXiv preprint arXiv:2401.XXXX , year=
-
[42]
2023 , publisher=
Zandieh, Amir and Han, Insu and Daliri, Majid and Karbasi, Amin , booktitle=. 2023 , publisher=
2023
-
[43]
Dettmers, Tim and Pagnoni, Artidoro and Holtzman, Ari and Zettlemoyer, Luke , booktitle =
-
[44]
Liu, Shih-Yang and Wang, Chien-Yi and Yin, Hongxu and Molchanov, Pavlo and Wang, Yu-Chiang Frank and Cheng, Kwang-Ting and Chen, Min-Hung , booktitle =
-
[45]
2023 , eprint =
Sparse Low-rank Adaptation of Pre-trained Language Models , author =. 2023 , eprint =
2023
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.