Paper deep dive
ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
Mahdi Heidari, Mohammad Mahdi Rahimi, Jaekyun Moon
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/23/2026, 3:14:10 AM
Summary
The paper introduces ELSAA (Efficient Low-Rank and Sparse Attention Approximation), a method to address the quadratic complexity of Transformer attention. ELSAA approximates the attention operator by combining a sparse branch (using LSH to capture high-similarity interactions) and a low-rank branch (using RACE attention for global context). It introduces a denominator-aware fusion term to balance the outputs of these two branches, which may have different normalization scales, allowing for efficient long-context training without materializing the full N×N attention matrix.
Entities (7)
Relation Signals (7)
ELSAA → addresses → Quadratic Complexity
confidence 95% · The quadratic N×N attention score matrix remains a central obstacle... ELSAA... aims to enable longer-context training while preserving both sharp token-level interactions and broad contextual mixing.
ELSAA → uses → Sparse Branch
confidence 95% · ELSAA approximates the induced attention score operator itself: a sparse branch captures selected high-similarity interactions
ELSAA → uses → Low-Rank Branch
confidence 95% · while a low-rank branch summarizes diffuse global interactions.
Low-Rank Branch → implementedby → RACE
confidence 90% · We use RACE attention as the low-rank global branch
Sparse Branch → implementedby → SortLSH
confidence 90% · The sparse branch is designed to preserve sharp token-level interactions... We use a sortLSH selector
ELSAA → introduces → Denominator-Aware Fusion
confidence 90% · ELSAA introduces a denominator-aware fusion term that scales the sparse branch according to its estimated attention mass relative to the low-rank branch.
FlashAttention → optimizes → IO Efficiency
confidence 85% · FlashAttention uses IO-aware tiling to avoid materializing the full attention matrix in high-bandwidth memory
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2607.20214v1
- Canonical: https://arxiv.org/abs/2607.20214v1
Trouble viewing inline? Open PDF directly →
Full Text
99,005 characters extracted from source content.
Expand or collapse full text
ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers Mahdi Heidari Mohammad Mahdi Rahimi Jaekyun Moon Abstract The quadratic N×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/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. Importantly, ELSAA does not decompose the learned projection or output matrices of the Transformer into sparse and low-rank factors. Instead, after dense projections produce Q,K,VQ,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. Efficient Attention, Sparse Attention, Low-Rank Attention, Transformers, Long-Context Modeling 1 Introduction Transformers have become the dominant architecture for language, vision, and multimodal modeling, largely because self-attention can adaptively mix information across all pairs of tokens (Vaswani et al., 2017; Devlin et al., 2019; Brown et al., 2020; Dosovitskiy et al., 2021; Touvron et al., 2023). However, this pairwise interaction is also the main barrier to extending models to longer input lengths. For a sequence of length N, standard attention forms the score matrix Z=QK⊤/dh,P=softmax(Z),Z=QK / d_h, P=softmax(Z), (1) where P∈ℝN×NP ^N× N is applied to the value matrix V. Equivalently, for a single query token i, dense attention computes di=∑j=1Nexp(zij),oi=1di∑j=1Nexp(zij)vj.d_i= _j=1^N (z_ij), o_i= 1d_i _j=1^N (z_ij)v_j. (2) Here did_i is the attention denominator, and it determines the scale on which the weighted value average is normalized. The memory and compute cost of this dense N×N× N operator grows quadratically with context length. Systems advances such as FlashAttention improve the IO efficiency and practical runtime of exact dense attention, but they do not change the fact that exact attention still represents all pairwise token interactions (Dao et al., 2022; Dao, 2023). Therefore, algorithmic approximations of the attention operator remain essential for training and serving models with substantially longer contexts. A large body of work reduces the cost of attention by exploiting either sparsity or low-rank structure. Sparse attention methods restrict each query to a subset of keys, using local windows, global tokens, random patterns, routing, clustering, hashing, or large-entry detection (Child et al., 2019; Beltagy et al., 2020; Zaheer et al., 2020; Kitaev et al., 2020; Roy et al., 2021; Daras et al., 2020; Han and others, 2024; Jiang et al., 2024). These methods are especially appealing when the attention distribution is low-entropy, peaked, or dominated by a small number of relevant keys. In such regimes, most of the denominator in Equation 2 may be contributed by only a small fraction of the full key set, and computing the corresponding high-mass interactions exactly can preserve the sharp token-level behavior of dense attention. In contrast, low-rank, kernel, and sketch-based methods approximate the dense attention operator through compressed features or landmarks, enabling global mixing without explicitly constructing the full matrix (Wang et al., 2020; Katharopoulos et al., 2020; Choromanski et al., 2021; Peng et al., 2021; Xiong et al., 2021). These methods are attractive when attention is high-entropy or diffuse, so that information is spread over many tokens and global context is better represented by a compressed dense summary. However, either assumption alone can be brittle: sparse methods may miss weak but globally important interactions, while low-rank methods may smooth out sharp, high-mass token-token dependencies. This complementarity suggests that attention should often be approximated as a combination of sparse and low-rank components. Prior work has provided strong evidence for this view, showing that the two approximation families can excel in different regimes of the attention matrix (Chen et al., 2021). Classical robust PCA also motivates the broader idea that many matrices can be represented as the sum of a low-rank term and a sparse residual (Candès et al., 2011; Chandrasekaran et al., 2011). Nevertheless, combining these structures inside attention is subtle. A naive addition of sparse attention and low-rank attention can double-count selected interactions, and Scatterbrain’s entrywise correction handles this issue at the level of an unnormalized attention estimator by correcting selected entries exactly (Chen et al., 2021). However, an entrywise correction alone does not answer how two separately normalized branches should be balanced during training. In particular, a sparse branch and a low-rank branch may have very different denominator masses, so their outputs can live on different scales even when both branches are useful. We propose ELSAA: Efficient Low-rank and Sparse Approximation of Attention. ELSAA is built around a simple principle: use a sparse branch for high-confidence interactions and a low-rank branch for global residual context. The sparse branch selects keys that are likely to be highly relevant to a given query and computes attention over the selected support. Different sparse key-finding mechanisms can instantiate this principle, including locality-sensitive hashing, routing or clustering, learned or dynamic sparse patterns, and approximate large-entry detection (Kitaev et al., 2020; Roy et al., 2021; Daras et al., 2020; Han and others, 2024; Jiang et al., 2024; Tang et al., 2024). The low-rank branch summarizes global key/value information in a compressed representation and produces a query-dependent global context vector without materializing all pairwise scores. For a given query token i, ELSAA forms a fused output Oi=gsparse,imsparse,iOsparse,i+glr,iOlr,i.O_i=g_sparse,i\,m_sparse,i\,O_sparse,i+g_lr,i\,O_lr,i. (3) where oisparseo^sparse_i is the sparse-branch output, oilowranko^lowrank_i is the low-rank-branch output, and gsparseg_sparse and glowrankg_lowrank are learned gates. Let disparsed^sparse_i denote the estimated denominator mass covered by the sparse branch, and let dilowrankd^lowrank_i denote the denominator estimate associated with the low-rank branch. We introduce the denominator-aware correction msparse,i=disparsedisparse+λdilowrank+ε,m_sparse,i= d^sparse_id^sparse_i+λ d^lowrank_i+ , (4) where λ can be fixed or learned. Several empirical studies of long-context attention and KV-cache compression observe that a small fraction of critical tokens or sparse attention patterns can dominate the attention outcome (Zhang et al., 2023; Xiao et al., 2024; Tang et al., 2024; Jiang et al., 2024). However, directly adding a sparse output to a low-rank output can distort the scale of the true attention computation, especially when the two branches are normalized by denominators of different magnitudes. The role of msparse,im_sparse,i is to rescale the sparse contribution according to its estimated denominator mass, so that the two outputs are fused on a more comparable scale. Thus, ELSAA does not merely add two attention approximations; it explicitly accounts for their relative normalization scales. We emphasize a distinction from sparse plus low-rank weight parameterizations. Recent work has shown that representing learned matrices using both low-rank and sparse components can improve parameter and memory efficiency for compression, fine-tuning, or pretraining (Li et al., 2023; Han et al., 2024; Mozaffari et al., 2024). ELSAA addresses a different object. We keep the learned Transformer projections dense and instead approximate the induced N×N× N attention operator after Q,K,VQ,K,V have been formed. This distinction is important for long-context modeling: the bottleneck we target is not the number of parameters in WQ,WK,WV,WOW_Q,W_K,W_V,W_O, but the quadratic attention matrix that appears for every input sequence. Combining these two orthogonal directions is also an interesting future research path: one may approximate the learned projection and output matrices in parameter space while simultaneously approximating the input-dependent attention matrix in sequence space. Our contributions are as follows. First, we formulate long-context attention as a low-rank and sparse operator construction rather than as a decomposition of learned projection matrices. Second, we combine an LSH-selected exact sparse branch with a RACE-style low-rank sketch branch, targeting both sharp local/similar-token interactions and diffuse global context. Third, we introduce denominator-aware fusion through mexactm_exact, with optional learnable λ, to address scale mismatch between sparse and sketch attention branches during training. 2 Related Work Efficient attention for long sequences. Efficient Transformers aim to overcome the quadratic cost of dense self-attention (Tay et al., 2020, 2022). One line of work keeps exact or nearly exact attention but improves practical execution. FlashAttention uses IO-aware tiling to avoid materializing the full attention matrix in high-bandwidth memory, providing major speed and memory improvements for exact attention (Dao et al., 2022; Dao, 2023). This is complementary to ELSAA: FlashAttention optimizes the computation of dense or block attention, while ELSAA changes the attention operator to avoid constructing all pairwise interactions. Another line of work imposes sparse attention patterns. Sparse Transformer uses structured sparse patterns (Child et al., 2019); Longformer and BigBird combine local, global, and random attention to support long documents (Beltagy et al., 2020; Zaheer et al., 2020); Reformer uses LSH to reduce attention cost (Kitaev et al., 2020); Routing Transformer and SMYRF use clustering or asymmetric hashing to identify relevant key blocks (Roy et al., 2021; Daras et al., 2020); and HyperAttention uses LSH-style detection of large entries to obtain near-linear long-context attention under appropriate structure (Han and others, 2024). More recent long-context inference methods also exploit dynamic sparse attention or query-aware critical-token selection, further supporting the view that only part of the full attention matrix may be necessary for many inputs (Zhang et al., 2023; Xiao et al., 2024; Tang et al., 2024; Jiang et al., 2024). These methods are effective when attention is sparse or structured, but sparse selection alone may not capture diffuse background interactions across the entire sequence. Low-rank, kernel, and sketch attention. A second family of efficient attention methods approximates the dense attention operator with low-dimensional features. Linformer projects the sequence dimension and assumes that attention matrices are approximately low-rank (Wang et al., 2020). Linear Transformer rewrites attention using kernel feature maps so that computation can be associated as ϕ(Q)(ϕ(K)⊤V)φ(Q)(φ(K) V) (Katharopoulos et al., 2020). Performer uses positive random features to approximate softmax attention with linear complexity (Choromanski et al., 2021), while Random Feature Attention studies related random-feature approximations for autoregressive modeling (Peng et al., 2021). Nyströmformer approximates attention using landmark-based Nyström methods (Xiong et al., 2021). RACE attention uses differentiable hash-sketch summaries, where keys are softly assigned to buckets, bucket statistics are accumulated, and queries read out from these summaries (Joshi et al., 2026). Such methods provide global context at subquadratic or linear cost, but they can struggle to represent sharp, high-confidence entries of the attention distribution. ELSAA uses the low-rank branch for global coverage while delegating high-mass interactions to a sparse branch. Sparse plus low-rank attention. The idea that attention may require both sparse and low-rank structure is closely related to sparse plus low-rank matrix decomposition. Robust PCA studies decompositions of a matrix into a low-rank component and a sparse component (Candès et al., 2011; Chandrasekaran et al., 2011). Scatterbrain applies this perspective to attention and shows that sparse and low-rank approximations can be complementary across attention entropy regimes (Chen et al., 2021). Its construction uses a low-rank random feature approximation together with a sparse LSH-selected correction so that selected entries match the unnormalized exponential attention exactly, while non-selected entries are approximated by the low-rank component. This provides an elegant entrywise estimator with unbiasedness and reduced variance. However, its analysis is primarily entrywise and does not directly provide a general output-level variance or scale analysis for combining attention branches that may be normalized by different denominators. ELSAA takes a related but distinct view: rather than correcting a single unnormalized matrix estimator, we study a training-time architecture with two separately normalized attention-like branches. In this setting, the main issue is not only entrywise unbiasedness, but also how to balance branch outputs whose denominator masses and scales can differ. The factor msparse,im_sparse,i in Equation 4 is designed for this branch-scale mismatch. Sparse plus low-rank parameterization of model weights. Sparse plus low-rank structure has also been used to parameterize, compress, or adapt the learned weights of neural networks. LoRA represents fine-tuning updates with low-rank factors (Hu et al., 2022), while subsequent work studies quantized low-rank adaptation, weight-decomposed low-rank adaptation, restarted low-rank training, and low-rank gradient projection (Dettmers et al., 2023; Liu et al., 2024; Lialin et al., 2024; Zhao et al., 2024). Other work explicitly combines sparsity with low-rank structure in parameter space: LoSparse compresses model weights using low-rank and sparse approximations (Li et al., 2023); SLoPe augments sparse LLM pretraining with low-rank adapters (Mozaffari et al., 2024); and SLTrain parameterizes weight matrices with a learned low-rank component together with a learned sparse component, improving parameter and memory efficiency during pretraining (Han et al., 2024). Sparse low-rank adaptation methods also study how sparsity can be incorporated into low-rank fine-tuning updates (Ding et al., 2023). This direction is orthogonal to ELSAA. We do not replace WQ,WK,WVW_Q,W_K,W_V, or WOW_O by sparse plus low-rank factors. Instead, our goal is to approximate the input-dependent attention operator induced by dense projections, thereby reducing the sequence-length bottleneck and enabling longer contexts. In short, SL-style methods decompose learned matrices in parameter space, whereas ELSAA constructs a sparse plus low-rank approximation in attention space. 3 Methodology Table 1: Comparison of attention methods across long-context classification tasks. ArXiv @ 32K Oxford-IIIT Pet @ 16K Flowers-102 @ 16K Food-101 @ 16K Average Method Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ ELSAA 99.97% 93.93% 91.55% 22.51% 97.84% 42.45% 76.43% 28.33% 91.45% 46.81% Sort_LSH 95.41% 84.94% 23.96% 12.65% 77.25% 37.25% 59.63% 19.03% 64.06% 38.47% RACE 100.00% 95.05% 59.89% 16.13% 91.66% 35.49% 67.57% 24.00% 79.78% 42.67% Sort_Lsh_RACE 99.95% 93.60% 76.76% 19.00% 95.98% 42.65% 76.05% 26.67% 87.19% 45.48% Exactflash 81.77% 70.11% 92.60% 24.66% 97.81% 48.13% 78.93% 29.96% 87.78% 43.22% Table 2: Text Retrieval @ 64K Method Train Acc. ↑ Test Acc. ↑ ELSAA 94.73% 65.34% RACE 94.95% 66.30% Sort_Lsh_RACE 94.28% 66.00% Exactflash ≈50≈ 50 ≈50≈ 50 Table 3: Comparison of attention methods on IMDB and Fashion-MNIST. IMDB @ 512 Fashion-MNIST @ 784 Average Method Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ ELSAA 90.68% 75.93% 87.79% 88.25% 89.24% 82.09% Sort_LSH 70.45% 66.14% 82.11% 83.15% 76.28% 74.65% RACE 89.93% 77.41% 89.79% 89.43% 89.86% 83.42% Sort_Lsh_RACE 90.20% 77.71% 85.43% 86.39% 87.82% 82.05% Exactflash 89.54% 78.67% 85.95% 85.81% 87.75% 82.24% Table 4: NIAH task test accuracy across input lengths. OOM indicates out-of-memory. Method 512 1024 2048 4096 8192 16384 32768 65536 Avg. Exact Flash 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% OOM OOM 100.0% ELSAA 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 98.8% 84.2% 97.88% Sparse_LSH 24.6% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 100.0% 90.58% RACE 11.0% 100.0% 100.0% 52.0% 13.4% 6.4% 4.8% 2.2% 36.23% Performer 19.2% 100.0% 88.2% 87.6% 88.2% 87.4% 83.2% 83.4% 79.65% Table 5: Comparison of causal attention methods across long-context classification tasks. ArXiv @ 32K ArXiv @ 64K Tiny ImageNet @ 1024 Average Method Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ Train ↑ Test ↑ ELSAA 100% 88.90% 100% 91.47% 94.44% 36.07% 98.15% 72.15% RACE 99.97% 87.84% 99.88% 91.46% 93.41% 36.39% 97.75% 71.90% Exactflash 99.97% 87.96% 99.83% 87.44% 96.59% 37.32% 98.80% 70.91% We instantiate ELSAA inside each attention layer by replacing dense attention with a sparse–low-rank hybrid operator that avoids constructing the full N×N× N score matrix. In this work, we use RACE attention as the low-rank global branch (Joshi et al., 2026), and use sorted Hamming LSH to identify highly correlated query-key pairs with high probability. This follows a line of efficient-attention methods that use hashing, kernel-density estimation, or large-entry detection to avoid materializing all pairwise attention scores, including KDEformer and HyperAttention (Zandieh et al., 2023; Han and others, 2024). The sparse branch captures high-similarity query-key interactions exactly, while the low-rank branch supplies global context through compressed bucket statistics. Future variants should also consider sliding-window, global-token, and learned top-k sparse selectors; these are natural alternatives but require careful implementation to preserve efficiency. We describe the method for one attention head. Multi-head ELSAA applies the same procedure independently per head and concatenates the outputs as in standard Transformers. Let Q,K,V∈ℝN×dhQ,K,V ^N× d_h be the query, key, and value matrices. Dense attention computes Oi=∑j=1Nexp(Qi⊤Kj/dh)Vj∑j=1Nexp(Qi⊤Kj/dh),O_i= _j=1^N (Q_i K_j/ d_h)V_j _j=1^N (Q_i K_j/ d_h), which requires all N2N^2 query-key scores. ELSAA instead computes two outputs, OlrO_lr and Osparse,O_sparse, together with denominator proxies dlr,dsparse,d_lr,d_sparse, and combines them through a denominator-aware fusion rule. 3.1 Low-rank branch: RACE attention RACE replaces the dense attention matrix with soft hash-bucket summaries. Each table softly assigns queries and keys to hypercube buckets, accumulates key/value statistics inside these buckets, and lets each query read from the resulting summaries. For a fixed number of tables, buckets, and head dimension, this gives a linear-time global branch in the sequence length N. We use the normalized ratio form because it directly provides both a low-rank output OlrO_lr and a denominator proxy dlrd_lr, which are both needed by the ELSAA fusion rule. For the causal setting, we extend RACE by partitioning the sequence into fixed-size chunks and decomposing the output into an inter-chunk contribution—bucket statistics accumulated from all strictly prior chunks via prefix sums—and a causally-masked intra-chunk contribution, preserving linear complexity. Full pseudocode for the non-causal and causal variants is given in Appendices A, 2 and 3. 3.2 Sparse branch: sortLSH exact attention The sparse branch is designed to preserve sharp token-level interactions that the low-rank branch may smooth. We use a sortLSH selector: queries and keys are hashed, sorted by their hash values, and grouped into equal-size blocks. After sorting, high-similarity query-key interactions are expected to concentrate near diagonal blocks of the permuted attention matrix. This lets us compute exact attention inside selected blocks using dense block matrix multiplications, without constructing the full N×N× N attention matrix. The branch returns a normalized sparse output OsparseO_sparse and its denominator dsparsed_sparse. For the causal setting, we adopt a recursive divide-and-conquer structure (Han and others, 2024): the sequence is split into past and future halves, the diagonal blocks are processed by recursive causal calls, and the future–past off-diagonal block is handled by standard non-causal sortLSH since all its keys precede all its queries; the two future contributions are merged via a log-sum-exp-aware combination that preserves exact softmax normalization. Full pseudocode for the non-causal and causal variants is given in Appendices A, 4 and 5. 3.3 Denominator-aware sparse–low-rank fusion The two branches are complementary but live on different normalization scales. The sparse branch computes selected high-confidence interactions exactly, but its support may cover only part of the row denominator. The low-rank branch provides global coverage, but may smooth sharp interactions. Therefore, directly adding the two outputs can over-amplify the sparse branch or double count overlapping mass. ELSAA introduces a denominator-aware sparse multiplier msparse,i=dsparse,idsparse,i+λidlr,i+ε,m_sparse,i= d_sparse,id_sparse,i+ _id_lr,i+ , (5) where λi>0 _i>0 can be fixed, a learnable scalar shared across tokens, or a query-dependent coefficient. The final ELSAA output uses two learned gates: (gsparse,i,glr,i)=σ(Gθ(qi))∈(0,1)2.(g_sparse,i,g_lr,i)=σ(G_θ(q_i))∈(0,1)^2. The fused output for token i is Oi=gsparse,imsparse,iOsparse,i+glr,iOlr,i.O_i=g_sparse,i\,m_sparse,i\,O_sparse,i+g_lr,i\,O_lr,i. (6) The factor msparse,im_sparse,i scales the sparse branch according to its estimated denominator mass relative to the low-rank branch, while the gates learn how much each branch should contribute to the final representation. Algorithm 1 ELSAA: Efficient Low-Rank and Sparse Approximation of Attention 1: Input: hidden states X∈ℝN×dX ^N× d, projections WQ,WK,WV,WOW_Q,W_K,W_V,W_O, RACE parameters Ls,γ,βL_s,γ,β, sortLSH block size b, gate network GθG_θ, coefficient rule λi>0 _i>0, numerical floor ε>0 >0 2: Output: hybrid attention output O∈ℝN×dO ^N× d 3: Project to one attention head Q←XWQ,K←XWK,V←XWV.Q← XW_Q, K← XW_K, V← XW_V. 4: Run the low-rank branch (Olr,dlr)←RACE(Q,K,V;Ls,γ,β,ε).(O_lr,d_lr) (Q,K,V;L_s,γ,β, ). 5: Run the sparse exact branch (Osparse,dsparse)←sortLSH(Q,K,V;b,ε).(O_sparse,d_sparse) (Q,K,V;b, ). 6: Compute denominator-aware sparse multiplier msparse,i←dsparse,idsparse,i+λidlr,i+ε,i=1,…,N.m_sparse,i← d_sparse,id_sparse,i+ _id_lr,i+ , i=1,…,N. 7: Compute token-wise gates (gsparse,glr)←σ(Gθ(Q)).(g_sparse,g_lr)←σ(G_θ(Q)). 8: Fuse branch outputs Ohead←gsparse⊙msparse⊙Osparse+glr⊙Olr.O_head← g_sparse m_sparse O_sparse+g_lr O_lr. 9: Return O←OheadWOO← O_headW_O Practical notes. The RACE branch can be implemented with different reduction modes using the same bucket statistics, while the sparse branch can be replaced by any efficient important-key selector that returns an exact sparse output and a denominator. In this work, we use sortLSH blocks because sorting makes the selected attention matrix block-diagonal after permutation, enabling efficient exact block attention without materializing the full N×N× N matrix. 4 A Rank View of Sparse + Low-Rank Attention We study hybrid sparse–low-rank attention operators of the form M^=SΩ+BA M=S_ +BA, where SΩ∈ℝn×nS_ ^n× n is sparse and BA∈ℝn×nBA ^n× n has rank at most r, with B∈ℝn×rB ^n× r, A∈ℝr×nA ^r× n. The sparse support Ω⊆[n]×[n] [n]×[n] is generated by angular collisions. Definition 4.1 (Angular collision probability). For nonzero Qi,Kj∈ℝdQ_i,K_j ^d, define ρij:=1−1πarccosQi⊤Kj‖Qi‖2‖Kj‖2∈[0,1]. _ij:=1- 1π Q_i K_j\|Q_i\|_2\|K_j\|_2∈[0,1]. For γ>0γ>0, the single-trial collision probability is πij:=ρijγ _ij:= _ij^γ. With LsL_s independent sparse hash trials, including (i,j)(i,j) after at least one collision gives qij:=1−(1−πij)Ls=1−(1−ρijγ)Ls.q_ij:=1-(1- _ij)^L_s=1-(1- _ij^γ)^L_s. Let M⋆∈ℝn×nM ^n× n denote the exact attention score/kernel matrix, e.g., Mij⋆=exp(Qi⊤Kj)M _ij= (Q_i K_j), and define SΩ:=Ω⊙M⋆S_ := M . Definition 4.2 (Sparse collision graph and matching deficiency). The support Ω defines the bipartite graph GΩ=([n]row,[n]col,Ω)G_ =([n]_ row,[n]_ col, ), where edge (i,j)∈Ω(i,j)∈ connects row i to column j. Let ν(Ω)ν( ) be its maximum matching size and define the matching deficiency d(Ω):=n−ν(Ω)d( ):=n-ν( ). Assumption 4.3 (Independent angular edge model). Conditioned on Q,KQ,K, we analyze the idealized model Ωij∼Bernoulli(qij) _ij Bernoulli(q_ij) independently over i,ji,j, preserving the marginal angular collision probabilities. Assumption 4.4 (Generic sparse values and generic low-rank factors). The nonzero entries of SΩS_ are in general position on their support, and B,AB,A are drawn independently from absolutely continuous distributions. Proposition 4.5 (Sparse matching deficiency plus low rank). Under 4.4, for fixed Ω , rank(SΩ+BA)=minn,ν(Ω)+ra.s.rank(S_ +BA)= \n,ν( )+r\ a.s. Hence, if ν(Ω)≥n−rν( )≥ n-r, then rank(SΩ+BA)=nrank(S_ +BA)=n almost surely. Thus, the sparse component contributes rank through the maximum matching of its support graph, while the rank-r branch fills up to r missing directions. Theorem 4.6 (Full rank from angular sparse collisions and rank-r low rank). Condition on Q,KQ,K, and suppose 4.3 and 4.4 hold. Let R:=r+1R:=r+1, and for I,U⊆[n]I,U [n] define Λ(I,U):=∑i∈I,j∈Uqij, (I,U):= _i∈ I,\ j∈ Uq_ij, Δr(Q,K):=∑I,U⊆[n]|I|≥R,|U|≥R,|I|+|U|≥n+Re−Λ(I,U). _r(Q,K):= _ subarraycI,U [n]\\ |I|≥ R,\ |U|≥ R,\ |I|+|U|≥ n+R subarraye^- (I,U). Then ℙ[rank(SΩ+BA)=n|Q,K]≥1−Δr(Q,K).P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1- _r(Q,K). The sets I,UI,U in Δr(Q,K) _r(Q,K) are Hall-deficiency cuts: failure occurs when a large query set has no sparse edges into a large key set. The quantity Λ(I,U) (I,U) is the expected number of sampled sparse entries in that rectangle, so full rank holds when every Hall-relevant rectangle has enough expected angular collision mass. We prove the theoretical claims from this section in Appendix B. In Appendix C, we further analyze settings that simplify Theorem 4.6 to ℙ[rank(SΩ+BA)=n|Q,K]≥1−n−c.P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1-n^-c. These results show that SΩ+BAS_ +BA can be full rank with high probability under natural sparse-coverage conditions, motivating further study of sparse–low-rank attention rank behavior. 5 Experimental Setup We evaluate ELSAA across classification and retrieval tasks to test whether the sparse–low-rank attention structure is useful beyond a single modality or dataset. Since our main motivation is efficient long-context modeling, we prioritize settings with relatively long input sequences or large tokenized inputs whenever possible. The benchmark suite includes long-document text classification, sentiment classification, fine-grained image classification, low-resolution image classification, and text retrieval. For all tasks, we compare attention variants under the same training and evaluation settings, and we report top-1 accuracy. Full task-specific hyperparameters, including learning rates, batch sizes, sequence lengths, model sizes, and training schedules, are reported in Appendix D. Datasets and tasks. We evaluate on text, image, and retrieval benchmarks: ArXiv for scientific text classification, IMDB for binary sentiment classification (Maas et al., 2011), Food-101 (Bossard et al., 2014), Fashion-MNIST (Xiao et al., 2017), Flowers-102 (Nilsback and Zisserman, 2008), and Oxford-IIIT Pet (Parkhi et al., 2012). For ArXiv classification, the model predicts the document subject class; for text retrieval, two ArXiv documents are paired into a 64K-token sequence and the model performs binary same-class prediction. We also evaluate on a synthetic Needle-in-a-Haystack (NIAH) benchmark, where a key-value needle is inserted at a random position in a long distractor context and the model must recall the value at sequence end. NIAH probes content-based retrieval across lengths 512,1024,2048,4096,8192,16384,32768,65536\512,1024,2048,4096,8192,16384,32768,65536\, with a separate model trained on length 1024. Finally, we evaluate the causal variants of Algorithm 6 on autoregressive long-context classification: packed ArXiv at N∈32,000,64,000N∈\32,000,64,000\, where the classification head reads the last valid token under strict left-to-right access, and Tiny ImageNet (200 classes, 64×6464× 64) using a causal ViT with patch size 2 (N=1024N=1024 tokens, raster-order causal mask, class token at position 0). Together these tasks span long text, tokenized vision, retrieval, and causal aggregation across a wide range of sequence lengths. Attention variants. We compare Exactflash as the full-attention baseline, RACE as the low-rank baseline, Sort_Lsh as the sparse baseline, and ELSAA as our proposed sparse–low-rank method. We also include Sort_Lsh_RACE as an ablation that combines both branches but sets msparse=1m_sparse=1, removing denominator-aware rescaling. For the causal experiments, Sort_Lsh and Sort_Lsh_RACE are omitted, as their sparse branch is replaced by the recursive causal sortLSH of Algorithm 5—which is precisely the sparse branch inside causal ELSAA—making them non-comparable baselines. In all result tables, we bold the highest accuracy among efficient attention variants, excluding Exactflash as it does not reduce the quadratic computation cost. Hardware and evaluation protocol. All experiments were run on an NVIDIA RTX PRO 6000 Blackwell GPU with 48 GB of memory. Within each task, all attention variants use the same model, training budget, optimizer, and evaluation protocol. Unless otherwise stated, we report top-1 accuracy. The source code is available here. 6 Complexity of ELSAA We analyze the attention-mixing cost for a non-causal sequence of length N, suppressing constants from batch size and number of heads. Exactflash attention computes all query–key interactions: Exactflash=Θ(N2),ℳExactflash=Θ(N2).C_Exactflash= (N^2), _Exactflash= (N^2). In Sort_Lsh, tokens are sorted by angular LSH and exact attention is computed only within fixed-size sorted blocks of size s. Therefore each query attends to at most s keys: Sort_Lsh=Θ(Ns),ℳSort_Lsh=Θ(Ns).C_Sort\_Lsh= (Ns), _Sort\_Lsh= (Ns). With r neighboring sorted blocks, this becomes Θ(N(2r+1)s) (N(2r+1)s). In our main setting r=0r=0, so the branch cost is Θ(Ns) (Ns). For Race, let LsL_s be the number of hash tables and γ be the number of hash bits per table. Each table has 2γ2^γ buckets, hence the total number of bucket features is SR=Ls2γ.S_R=L_s2^γ. Race does not materialize an N×N× N matrix; it builds global bucket summaries and each query reads from these SRS_R features: Race=Θ(NLs2γ),ℳRace=Θ(NLs2γ).C_Race= (NL_s2^γ), _Race= (NL_s2^γ). ELSAA combines Sort_Lsh and Race, with denominator-aware sparse rescaling: ELSAA=Θ(Ns+NLs2γ)=Θ(N(s+Ls2γ)),C_ELSAA= \! (Ns+NL_s2^γ )= \! (N(s+L_s2^γ) ), ℳELSAA=Θ(N(s+Ls2γ)).M_ELSAA= \! (N(s+L_s2^γ) ). The ablation Sort_Lsh_RACE has the same asymptotic cost as ELSAA, but removes the rescaling term by setting msparse=1m_sparse=1. For fixed s, LsL_s, and γ, Sort_Lsh, Race, Sort_Lsh_RACE, and ELSAA are linear in N, while Exactflash attention is quadratic. Complexity summary. ELSAA reduces the quadratic N2N^2 attention interaction cost by combining a sparse branch with O(Ns)O(Ns) selected query–key interactions and a low-rank RACE branch with O(NLs2γ)O(NL_s2^γ) bucket interactions, where s is the sparse block budget, LsL_s is the number of hash tables, and γ is the number of hash bits. Thus, ignoring lower-order hashing and sorting overhead, the attention-interaction cost scales as O(N(s+Ls2γ))O\! (N(s+L_s2^γ) ) instead of O(N2)O(N^2). We provide a concrete numerical example in Appendix E, showing that ELSAA reduces attention interactions by approximately 99%. 7 Results and Discussion Tables 5–4 compare ELSAA with sparse, low-rank, hybrid, and exact full-attention baselines across long-context vision, long-context text, retrieval, short-sequence, and length-extrapolation settings. We organize the discussion around four observations: (i) ELSAA improves on Sort_Lsh_RACE consistently, isolating the contribution of the denominator-aware correction; (i) the relative strength of the sparse and low-rank branches reflects a fundamental structural difference between vision and long-text tasks; (i) exact full attention is not merely expensive at very long contexts but can fail to optimize at all; and (iv) ELSAA is the only method that extrapolates reliably across all lengths on NIAH, including lengths shorter than training. Isolating the denominator-aware correction. One important ablation compares Sort_Lsh_RACE with ELSAA. These two methods share identical architecture, branches, gates, and hyperparameters; the only difference is that Sort_Lsh_RACE sets msparse=1m_sparse=1, while ELSAA computes the denominator-aware multiplier of Equation 5. Any performance gap is therefore attributable solely to this single term. On the long-context benchmarks of Table 5, ELSAA achieves an average test accuracy of 46.81%46.81\% versus 45.48%45.48\% for Sort_Lsh_RACE, a consistent +1.33+1.33p improvement obtained without changing parameter count, branch complexity, or optimization budget. The improvement is most visible on structured vision tasks (Oxford-IIIT Pet: 22.51%22.51\% vs. 19.00%19.00\%; Food-101: 28.33%28.33\% vs. 26.67%26.67\%), supporting our central claim: when two branches are normalized over supports of very different denominator mass, naive addition distorts the fused output, and msparsem_sparse corrects this with a principled rescaling rather than a learned heuristic. Vision is structured; long-text classification is diffuse. The most striking pattern in Table 5 is that the relative ranking of RACE, Sort_LSH, and ELSAA changes systematically between long text and long vision. On long vision tasks ELSAA dominates, improving over RACE by +6.4+6.4p on Oxford-IIIT Pet, +7.0+7.0p on Flowers-102, and +4.3+4.3p on Food-101. On ArXiv @ 32K, RACE alone (95.05%95.05\%) marginally outperforms ELSAA (93.93%93.93\%). This dichotomy is structural: vision attention is locally peaked, dominated by a small support of high-mass interactions that an unconditional low-rank approximation smooths away, whereas long-document topic classification requires aggregating diffuse weak evidence across the sequence, making a low-rank summary not only sufficient but preferable. ELSAA handles both regimes within a single architecture, consistent with the rank perspective of Section 4. Exact attention fails at very long context. The Text Retrieval @ 64K results in Table 2 are decisive. ExactFlash collapses to approximately 50%50\% on both train and test—random performance on a binary task—while ELSAA reaches 65.34%65.34\% and RACE 66.30%66.30\%. Dense attention at N=64,000N=64,000 spreads gradient signal across ≈4×109≈ 4× 10^9 pairwise interactions per layer, the vast majority uninformative. Approximate attention acts as an implicit structural prior that focuses the model on a tractable subset of interactions and stabilizes optimization, enabling a regime that exact attention cannot reach. The broad-aggregation nature of retrieval again favors the low-rank branch slightly, with RACE outperforming ELSAA by ≈1≈ 1p—consistent with the structural argument above. Short tasks do not require hybrid structure. Table 3 confirms the natural complement: at N=512N=512 and N=784N=784, ELSAA, RACE, and ExactFlash are all within 11–22p of each other. The relevant observation is not that ELSAA wins, but that it degrades gracefully rather than failing—an important property for a general-purpose attention layer deployed across heterogeneous workloads. NIAH: length extrapolation and the role of each branch. Table 4 reports NIAH accuracy when all models are trained at N=1024N=1024 and evaluated across lengths 512,…,65536\512,…,65536\, probing both shorter-than-training and longer-than-training generalization. Several findings stand out. First, RACE fails catastrophically beyond the training length: accuracy collapses from 100%100\% at 10241024 to 52%52\% at 40964096 and near-random (2.2%2.2\%) at 6553665536. This confirms that the low-rank bucket summaries, while globally expressive at seen lengths, cannot locate a specific needle token when the sequence length shifts the effective bucket density. Second, ExactFlash achieves perfect accuracy up to 1638416384 but runs out of memory at 3276832768 and beyond, highlighting the wall exact attention hits at extreme lengths. Third, Sparse_LSH extrapolates well at long lengths (100%100\% at 3276832768 and 6553665536) because content-based hashing is inherently position-independent, but it fails at N=512N=512—shorter than training—with only 24.6%24.6\% accuracy, suggesting that its block structure becomes degenerate when the sequence is too short to populate meaningful hash buckets. ELSAA, by contrast, achieves 100%100\% at N=512N=512, outperforming Sparse_LSH at this sub-training length: the low-rank RACE branch provides reliable global context when the sparse branch’s bucket structure is under-populated, and the denominator-aware gate learns to up-weight it accordingly. At the long end, ELSAA reaches 98.8%98.8\% at 3276832768 and 84.2%84.2\% at 6553665536—well above RACE and Performer, and within reach of Sparse_LSH—demonstrating that the hybrid structure preserves the content-based retrieval strength of the sparse branch while preventing the catastrophic failure of the low-rank branch alone. Causal ELSAA matches or exceeds baselines across lengths and modalities. Table 5 (causal) shows that causal ELSAA achieves the highest average test accuracy (72.15%72.15\%) across ArXiv @ 32K, ArXiv @ 64K, and Tiny ImageNet @ 1024, outperforming causal RACE (71.90%71.90\%) and causal ExactFlash (70.91%70.91\%). On the two long-text settings, all three methods are competitive, consistent with the diffuse-attention argument above. On Tiny ImageNet, causal ExactFlash leads slightly in test accuracy (37.32%37.32\% vs. 36.07%36.07\% for ELSAA and 36.39%36.39\% for RACE), suggesting that at N=1024N=1024 the quadratic baseline remains viable and the sparse branch’s advantage is modest. Crucially, at ArXiv @ 64K causal ExactFlash lags ELSAA by 44p (87.44%87.44\% vs. 91.47%91.47\%), confirming that the optimization difficulty of dense attention at very long contexts persists in the causal setting. 8 Future Work Scaling laws. Our experiments fix the model size and sweep over sequence length and modality, but a systematic study of how the relative contributions of the sparse and low-rank branches evolve with model scale, data scale, and context length would clarify when each branch dominates, and would inform the design of branch-specific schedules during pretraining. In particular, the dichotomy we observe between peaked (vision) and diffuse (long text) regimes suggests that the appropriate gate and λ schedules may also depend on depth and head index. Fused causal GPU kernels. A natural systems-level extension is a fused GPU kernel that combines, in one launch, the recursive sortLSH grouping of Algorithm 5, block-wise exact attention within sorted blocks, the chunked cumulative bucket aggregation of Algorithm 3, and the denominator-aware fusion of Equation 5. Implementations along the lines of FlashAttention show that such fusions are feasible and can recover most of the theoretical advantage in practice. A particularly promising aspect of ELSAA in this respect is that the sparse and low-rank branches are independent given Q,K,VQ,K,V, so they admit parallel scheduling on independent CUDA streams or within a single persistent kernel that shares the Q,K,VQ,K,V loads from high-bandwidth memory. Pretraining of decoder language models. Having validated the causal variant on long-context classification and on retrieval-style NIAH tasks at lengths up to 64K, the next milestone is autoregressive language-model pretraining with causal ELSAA. The empirical literature on long-context inference (Zhang et al., 2023; Xiao et al., 2024; Tang et al., 2024) consistently documents heavy-tailed attention access patterns dominated by attention sinks, recent context, and a small number of task-relevant pivots, which is precisely the structure that the sparse branch is designed to capture. The denominator-aware multiplier msparsem_sparse additionally provides a principled account of the mass discarded by KV-cache eviction methods, which currently address this scale problem with heuristics. Joint compression in parameter and attention space. ELSAA is orthogonal to weight-space compression methods such as LoRA (Hu et al., 2022), LoSparse (Li et al., 2023), and SLTrain (Han et al., 2024). Approximating the input-dependent attention operator and the learned projection matrices simultaneously is a natural composition: the former targets the sequence-length bottleneck, while the latter targets the parameter-count bottleneck. We see this composition as a promising route to long-context efficient pretraining of large language models. Theoretical analysis of branch fusion. The rank analysis of Section 4 establishes an expressivity guarantee for the hybrid sparse–low-rank operator but does not directly analyze the bias and variance of ELSAA’s normalized branch outputs under the denominator-aware fusion rule. A complementary output-level bias–variance analysis, in the spirit of Scatterbrain’s entrywise analysis but at the level of normalized attention outputs, would clarify when the denominator-aware multiplier provably reduces the mean-squared error of the fused estimator, and when learnable λ is preferable to a fixed schedule. 9 Conclusion We introduced ELSAA, a sparse–low-rank approximation of attention combining an exact sortLSH sparse branch with a low-rank RACE branch, fused via a denominator-aware multiplier msparsem_sparse that corrects the scale mismatch between separately-normalized branches. Our rank analysis shows the sparse component contributes rank through its support graph’s matching structure while the low-rank component fills the remaining deficiency. Empirically, ELSAA dominates efficient-attention baselines on long-context structured vision, remains competitive on diffuse long-text tasks, and succeeds where exact attention fails entirely (Text Retrieval @ 64K). On NIAH, ELSAA achieves perfect retrieval up to 16K and remains strong at 32K–64K where exact attention runs out of memory and RACE degrades sharply. We further extended both branches to the causal setting and validated causal ELSAA on autoregressive ArXiv classification up to 64K tokens and on Tiny ImageNet, matching or exceeding causal exact attention and causal RACE throughout. The method is linear in sequence length, adds negligible parameters, and degrades gracefully at short lengths, offering a principled path toward long-context attention that is tractable where exact attention is not. 10 Acknowledgments This work was supported by the National Research Foundation of Korea (NRF) grants funded by the Korea government (MSIT) (Nos. RS-2024-00340966 and RS-2024-00408003), and by the Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00444862). 11 Impact statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. References I. Beltagy, M. E. Peters, and A. Cohan (2020) Longformer: the long-document transformer. arXiv preprint arXiv:2004.05150. Cited by: §1, §2. L. Bossard, M. Guillaumin, and L. Van Gool (2014) Food-101 – mining discriminative components with random forests. In European Conference on Computer Vision (ECCV), p. 446–461. Cited by: §5. T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. (2020) Language models are few-shot learners. In Advances in Neural Information Processing Systems, Cited by: §1. E. J. Candès, X. Li, Y. Ma, and J. Wright (2011) Robust principal component analysis?. Journal of the ACM 58 (3), p. 1–37. Cited by: §1, §2. V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky (2011) Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization 21 (2), p. 572–596. Cited by: §1, §2. B. Chen, T. Dao, E. Winsor, Z. Song, A. Rudra, and C. Ré (2021) Scatterbrain: unifying sparse and low-rank attention approximation. In Advances in Neural Information Processing Systems, Cited by: §1, §2. R. Child, S. Gray, A. Radford, and I. Sutskever (2019) Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509. Cited by: §1, §2. K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser, et al. (2021) Rethinking attention with performers. In International Conference on Learning Representations, Cited by: §1, §2. T. Dao, D. Y. Fu, S. Ermon, A. Rudra, and C. Ré (2022) FlashAttention: fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Systems, Cited by: §1, §2. T. Dao (2023) FlashAttention-2: faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.08691. Cited by: §1, §2. G. Daras, N. Kitaev, A. Odena, and A. G. Dimakis (2020) SMYRF: efficient attention using asymmetric clustering. arXiv preprint arXiv:2010.05315. Cited by: §1, §1, §2. T. Dettmers, A. Pagnoni, A. Holtzman, and L. Zettlemoyer (2023) QLoRA: efficient finetuning of quantized LLMs. In Advances in Neural Information Processing Systems, Cited by: §2. J. Devlin, M. Chang, K. Lee, and K. Toutanova (2019) BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, Cited by: §1. N. Ding, X. Lv, Q. Wang, Y. Chen, B. Zhou, Z. Liu, and M. Sun (2023) Sparse low-rank adaptation of pre-trained language models. External Links: 2311.11696 Cited by: §2. A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, et al. (2021) An image is worth 16x16 words: transformers for image recognition at scale. In International Conference on Learning Representations, Cited by: §1. A. Han, J. Li, W. Huang, M. Hong, A. Takeda, P. Jawanpuria, and B. Mishra (2024) SLTrain: a sparse plus low-rank approach for parameter and memory efficient pretraining. In Advances in Neural Information Processing Systems, Cited by: §1, §2, §8. I. Han et al. (2024) HyperAttention: long-context attention in near-linear time. arXiv preprint arXiv:2401.X. Cited by: §1, §1, §2, §3.2, §3. E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen (2022) LoRA: low-rank adaptation of large language models. In International Conference on Learning Representations, Cited by: §2, §8. H. Jiang, Y. Li, C. Zhang, Q. Wu, X. Luo, S. Ahn, Z. Han, A. H. Abdi, D. Li, C. Lin, Y. Yang, and L. Qiu (2024) MInference 1.0: accelerating pre-filling for long-context LLMs via dynamic sparse attention. In Advances in Neural Information Processing Systems, Cited by: §1, §1, §1, §2. S. Joshi, A. Chowdhury, A. Kanakamedala, E. Singh, E. Tu, and A. Shrivastava (2026) RACE attention: a strictly linear-time attention layer for training on outrageously large contexts. In International Conference on Learning Representations, External Links: Link Cited by: §2, §3. A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret (2020) Transformers are RNNs: fast autoregressive transformers with linear attention. In International Conference on Machine Learning, Cited by: §1, §2. N. Kitaev, L. Kaiser, and A. Levskaya (2020) Reformer: the efficient transformer. In International Conference on Learning Representations, Cited by: §1, §1, §2. Y. Li, Y. Yu, Q. Zhang, C. Liang, P. He, W. Chen, and T. Zhao (2023) LoSparse: structured compression of large language models based on low-rank and sparse approximation. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 20336–20350. Cited by: §1, §2, §8. V. Lialin, S. Muckatira, N. Shivagunde, and A. Rumshisky (2024) ReLoRA: high-rank training through low-rank updates. In International Conference on Learning Representations, Cited by: §2. S. Liu, C. Wang, H. Yin, P. Molchanov, Y. F. Wang, K. Cheng, and M. Chen (2024) DoRA: weight-decomposed low-rank adaptation. In Proceedings of the 41st International Conference on Machine Learning, Cited by: §2. A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts (2011) Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, p. 142–150. Cited by: §5. M. Mozaffari, A. Yazdanbakhsh, Z. Zhang, and M. Mehri Dehnavi (2024) SLoPe: double-pruned sparse plus lazy low-rank adapter pretraining of LLMs. External Links: 2405.16325 Cited by: §1, §2. M. Nilsback and A. Zisserman (2008) Automated flower classification over a large number of classes. Proceedings of the Indian Conference on Computer Vision, Graphics and Image Processing. Cited by: §5. O. M. Parkhi, A. Vedaldi, A. Zisserman, and C. V. Jawahar (2012) Cats and dogs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), p. 3498–3505. Cited by: §5. H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. A. Smith, and L. Kong (2021) Random feature attention. In International Conference on Learning Representations, Cited by: §1, §2. A. Roy, M. Saffar, A. Vaswani, and D. Grangier (2021) Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics 9, p. 53–68. Cited by: §1, §1, §2. J. Tang, Y. Zhao, K. Zhu, G. Xiao, B. Kasikci, and S. Han (2024) QUEST: query-aware sparsity for efficient long-context LLM inference. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 47901–47911. Cited by: §1, §1, §2, §8. Y. Tay, M. Dehghani, S. Abnar, Y. Shen, D. Bahri, P. Pham, J. Rao, L. Yang, S. Ruder, and D. Metzler (2020) Long range arena: a benchmark for efficient transformers. arXiv preprint arXiv:2011.04006. Cited by: §2. Y. Tay, M. Dehghani, D. Bahri, and D. Metzler (2022) Efficient transformers: a survey. ACM Computing Surveys 55 (6), p. 1–28. Cited by: §2. H. Touvron, T. Lavril, G. Izacard, X. Martinet, M. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. (2023) LLaMA: open and efficient foundation language models. arXiv preprint arXiv:2302.13971. Cited by: §1. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin (2017) Attention is all you need. In Advances in Neural Information Processing Systems, Cited by: §1. S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma (2020) Linformer: self-attention with linear complexity. arXiv preprint arXiv:2006.04768. Cited by: §1, §2. G. Xiao, Y. Tian, B. Chen, S. Han, and M. Lewis (2024) Efficient streaming language models with attention sinks. External Links: 2309.17453 Cited by: §1, §2, §8. H. Xiao, K. Rasul, and R. Vollgraf (2017) Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747. Cited by: §5. Y. Xiong, Z. Zeng, R. Chakraborty, M. Tan, G. Fung, Y. Li, and V. Singh (2021) Nyströmformer: a nyström-based algorithm for approximating self-attention. In AAAI Conference on Artificial Intelligence, Cited by: §1, §2. M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang, et al. (2020) Big bird: transformers for longer sequences. In Advances in Neural Information Processing Systems, Cited by: §1, §2. A. Zandieh, I. Han, M. Daliri, and A. Karbasi (2023) KDEformer: accelerating transformers via kernel density estimation. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 40605–40623. Cited by: §3. Z. Zhang, Y. Sheng, T. Zhou, T. Chen, L. Zheng, R. Cai, Z. Song, Y. Tian, C. Ré, C. Barrett, Z. Wang, and B. Chen (2023) H2O: heavy-hitter oracle for efficient generative inference of large language models. In Advances in Neural Information Processing Systems, Cited by: §1, §2, §8. J. Zhao, Z. Zhang, B. Chen, Z. Wang, A. Anandkumar, and Y. Tian (2024) GaLore: memory-efficient LLM training by gradient low-rank projection. In International Conference on Machine Learning, Cited by: §2. Appendix A Branch Algorithms for ELSAA This appendix gives full pseudocode for all five branch-level procedures used by ELSAA: the non-causal RACE low-rank branch, its causal extension, the non-causal sortLSH sparse branch, its causal recursive extension, and the complete causal ELSAA fusion procedure. Algorithm 2 RACE Low-Rank Attention Branch 1: Input: Q,K,V∈ℝN×dhQ,K,V ^N× d_h, number of hash tables LsL_s, number of hyperplanes γ, temperature β>0β>0, numerical floor ε>0 >0 2: Output: low-rank output Olr∈ℝN×dhO_lr ^N× d_h, denominator proxy dlr∈ℝNd_lr ^N 3: Set R←2γR← 2^γ and ←±1γV←\± 1\^γ 4: for ℓ=1,…,Ls =1,…,L_s do 5: Draw W(ℓ)∈ℝγ×dhW^( ) ^γ× d_h with i.i.d. Gaussian rows 6: Build ΦQ(ℓ),ΦK(ℓ)∈ℝN×R _Q^( ), _K^( ) ^N× R with rows [ϕ(ℓ)(x)]r=expβtanh(W(ℓ)x)⊤vr∑r′=1Rexpβtanh(W(ℓ)x)⊤vr′,x∈Qi,Kj.[φ^( )(x)]_r= \β\, (W^( )x) v_r\ _r =1^R \β\, (W^( )x) v_r \, x∈\Q_i,K_j\. 7: Compute bucket mass and value summaries A(ℓ)←(ΦK(ℓ))⊤N∈ℝR,B(ℓ)←(ΦK(ℓ))⊤V∈ℝR×dh.A^( )←( _K^( )) 1_N ^R, B^( )←( _K^( )) V ^R× d_h. 8: end for 9: Compute table-averaged numerator and denominator Num←1Ls∑ℓ=1LsΦQ(ℓ)B(ℓ),Den←1Ls∑ℓ=1LsΦQ(ℓ)A(ℓ).Num← 1L_s _ =1^L_s _Q^( )B^( ), ← 1L_s _ =1^L_s _Q^( )A^( ). 10: Return Olr←diag(Den+ε)−1NumO_lr (Den+ )^-1Num, dlr←Dend_lr . Algorithm 3 Causal RACE Low-Rank Attention Branch 1: Input: Q,K,V∈ℝN×dhQ,K,V ^N× d_h, LsL_s, γ, β>0β>0, chunk size C, ε>0 >0 2: Output: causal low-rank output Olr∈ℝN×dhO_lr ^N× d_h, denominator proxy dlr∈ℝNd_lr ^N 3: Build soft hash features ΦQ(ℓ),ΦK(ℓ)∈ℝN×R _Q^( ), _K^( ) ^N× R for ℓ=1,…,Ls =1,…,L_s as in Algorithm 2 steps 3–7. 4: Pad sequence axis to N′=⌈N/C⌉⋅CN = N/C · C; reshape into nc=N′/Cn_c=N /C chunks of size C. Denote chunk-n slices ΦQ,n(ℓ),ΦK,n(ℓ)∈ℝC×R _Q,n^( ), _K,n^( ) ^C× R and Vn∈ℝC×dhV_n ^C× d_h. 5: for each table ℓ and chunk n do 6: An(ℓ)←(ΦK,n(ℓ))⊤C∈ℝRA_n^( )←( _K,n^( )) 1_C ^R, Bn(ℓ)←(ΦK,n(ℓ))⊤Vn∈ℝR×dhB_n^( )←( _K,n^( )) V_n ^R× d_h. 7: end for 8: Compute strict prefix states via cumulative sum and one-chunk right shift: sAn(ℓ)←∑m<nAm(ℓ)sA_n^( )← _m<nA_m^( ), sBn(ℓ)←∑m<nBm(ℓ)sB_n^( )← _m<nB_m^( ). 9: Inter-chunk (queries read from all prior chunks): inumn←1Ls∑ℓΦQ,n(ℓ)sBn(ℓ),idenn←1Ls∑ℓΦQ,n(ℓ)sAn(ℓ).inum_n← 1L_s _ _Q,n^( )sB_n^( ), _n← 1L_s _ _Q,n^( )sA_n^( ). 10: Intra-chunk (causally-masked soft attention within chunk): Mn←1Ls∑ℓΦQ,n(ℓ)(ΦK,n(ℓ))⊤⊙tril(C×C),M_n← 1L_s _ _Q,n^( )( _K,n^( )) (1_C× C), anumn←MnVnanum_n← M_nV_n, adenn←MnCaden_n← M_n1_C. 11: Combine: dlr,n←idenn+adennd_lr,n _n+aden_n, Olr,n←diag(dlr,n+ε)−1(inumn+anumn)O_lr,n (d_lr,n+ )^-1(inum_n+anum_n). 12: Concatenate chunks, remove padding, and return Olr,dlrO_lr,d_lr. Algorithm 4 sortLSH Sparse Exact Attention Branch 1: Input: Q,K,V∈ℝN×dhQ,K,V ^N× d_h, LSH map ℋ(⋅)H(·), block size b, ε>0 >0 2: Output: sparse output Osparse∈ℝN×dhO_sparse ^N× d_h, denominator dsparse∈ℝNd_sparse ^N 3: Hash: hiQ←ℋ(Qi)h^Q_i (Q_i), hjK←ℋ(Kj)h^K_j (K_j). 4: Sort: let PQ,PK∈Sym(N)P_Q,P_K (N) sort hQ,hKh^Q,h^K in non-decreasing order; form Qs,Ks,VsQ_s,K_s,V_s accordingly. 5: Partition sorted sequence into consecutive blocks Bt\B_t\ of size b. 6: for each block BtB_t do 7: Zt←Qs[Bt]Ks[Bt]⊤/dhZ_t← Q_s[B_t]K_s[B_t] / d_h, At←exp(Zt)A_t← (Z_t), ds[Bt]←Atd_s[B_t]← A_t1. 8: Os[Bt]←diag(ds[Bt]+ε)−1AtVs[Bt]O_s[B_t] (d_s[B_t]+ )^-1A_tV_s[B_t]. 9: end for 10: Undo query permutation: Osparse[PQ(t)]←Os[t]O_sparse[P_Q(t)]← O_s[t], dsparse[PQ(t)]←ds[t]d_sparse[P_Q(t)]← d_s[t]. 11: Return Osparse,dsparseO_sparse,d_sparse. Algorithm 5 Causal sortLSH Sparse Exact Attention Branch 1: Input: Q,K,V∈ℝN×dhQ,K,V ^N× d_h, LSH map ℋ(⋅)H(·), block size b, base length N0N_0, ε>0 >0 2: Output: causal sparse output Osparse∈ℝN×dhO_sparse ^N× d_h, logdsparse∈ℝN d_sparse ^N 3: Return CausalSparse(Q,K,V) CausalSparse(Q,K,V). 4: procedure CausalSparse(Q,K,V) CausalSparse(Q,K,V): 5: if n≤N0n≤ N_0 then return exact causal attention (O,logd)(O, d). 6: If n odd, pad by one zero token (n←n+1n← n+1); remove on return. 7: m←n/2m← n/2; split into past (Qp,Kp,Vp)←[⋅]1:m(Q_p,K_p,V_p)←[\,·\,]_1:m and future (Qf,Kf,Vf)←[⋅]m+1:n(Q_f,K_f,V_f)←[\,·\,]_m+1:n. 8: (Otop,logdtop)←CausalSparse(Qp,Kp,Vp)(O_top, d_top)← CausalSparse(Q_p,K_p,V_p) past–past causal 9: (Odiag,logddiag)←CausalSparse(Qf,Kf,Vf)(O_diag, d_diag)← CausalSparse(Q_f,K_f,V_f) future–future causal 10: (Ooff,logdoff)←SortLSH(Qf,Kp,Vp;b)(O_off, d_off)← SortLSH(Q_f,K_p,V_p;b) future–past, non-causal 11: (Obot,logdbot)←MergeLSE(Odiag,logddiag,Ooff,logdoff)(O_bot, d_bot)← MergeLSE(O_diag, d_diag,O_off, d_off) 12: Return concat(Otop,Obot)concat(O_top,O_bot), concat(logdtop,logdbot)concat( d_top, d_bot). 13: procedure SortLSH(Q,K,V;b) SortLSH(Q,K,V;b): apply Algorithm 4 and return (O,logdsparse)(O, d_sparse). 14: procedure MergeLSE(O1,logd1,O2,logd2) MergeLSE(O_1, d_1,O_2, d_2): 15: μ←max(logd1,logd2)μ← ( d_1, d_2); wk←exp(logdk−μ)w_k← ( d_k-μ); s←w1+w2s← w_1+w_2. 16: Return O←(w1O1+w2O2)/(s+ε)O←(w_1O_1+w_2O_2)/(s+ ), logd←μ+log(s+ε) d←μ+ (s+ ). Algorithm 6 Causal ELSAA: Efficient Low-Rank and Sparse Approximation of Attention 1: Input: hidden states X∈ℝN×dX ^N× d, shared projections WQ,WK,WV,WOW_Q,W_K,W_V,W_O, RACE parameters Ls,γ,β,CL_s,γ,β,C, sortLSH parameters b,N0b,N_0, gate network GθG_θ, coefficient λi>0 _i>0, ε>0 >0 2: Output: causal hybrid attention output O∈ℝN×dO ^N× d 3: Q←XWQ,K←XWK,V←XWVQ← XW_Q, K← XW_K, V← XW_V. 4: (Olr,dlr)←CausalRACE(Q,K,V;Ls,γ,β,C,ε)(O_lr,d_lr)← CausalRACE(Q,K,V;L_s,γ,β,C, ) Algorithm 3 5: (Osparse,logdsparse)←CausalSparse(Q,K,V;b,N0,ε)(O_sparse, d_sparse)← CausalSparse(Q,K,V;b,N_0, ) Algorithm 5 6: Compute msparse,im_sparse,i via numerically stable log-sum-exp: logDi←logsumexp(logdsparse,i,logλi+logdlr,i,logε), D_i \! ( d_sparse,i,\; _i+ d_lr,i,\; ), msparse,i←exp(logdsparse,i−logDi),i=1,…,N.m_sparse,i← ( d_sparse,i- D_i), i=1,…,N. 7: (gsparse,glr)←σ(Gθ(X))∈(0,1)N×2(g_sparse,g_lr)←σ(G_θ(X))∈(0,1)^N× 2. 8: Ohead←gsparse⊙msparse⊙Osparse+glr⊙OlrO_head← g_sparse m_sparse O_sparse+g_lr O_lr. 9: Return O←OheadWOO← O_headW_O. Appendix B Proofs and Additional Rank Corollaries We prove the rank statements from Section 4. The proof has four ingredients. First, we relate the angular collision probabilities qijq_ij to simpler lower and upper bounds. Second, a generic rank-r matrix can increase the rank of a fixed matrix by r, unless full rank is already reached. Third, the generic rank of a sparse matrix equals the maximum matching size of its support graph. Fourth, Hall’s theorem and concentration inequalities control the probability that the sparse collision graph has matching deficiency larger than r. B.1 Generic low-rank completion Lemma B.1 (Generic rank-r completion). Let S∈ℝn×nS ^n× n be fixed with rank(S)=k.rank(S)=k. Let B∈ℝn×rB ^n× r and A∈ℝr×nA ^r× n be drawn from an absolutely continuous distribution. Then rank(S+BA)=minn,k+ralmost surely.rank(S+BA)= \n,k+r\ almost surely. (7) In particular, if k≥n−rk≥ n-r, then rank(S+BA)=nalmost surely.rank(S+BA)=n almost surely. (8) Proof. Let m:=minn,k+r.m:= \n,k+r\. Since rank(S)=krank(S)=k, there exist invertible matrices P,Q∈ℝn×nP,Q ^n× n such that PSQ=(Ik000).PSQ= pmatrixI_k&0\\ 0&0 pmatrix. (9) Rank is invariant under multiplication by invertible matrices, hence rank(S+BA)=rank(PSQ+PBAQ).rank(S+BA)=rank(PSQ+PBAQ). (10) Define B~:=PB,A~:=AQ. B:=PB, A:=AQ. Because P and Q are invertible and A,BA,B are drawn from absolutely continuous distributions, A~,B~ A, B are also absolutely continuous. We show that some m×m× m minor of PSQ+B~A~PSQ+ B A is not the zero polynomial in the entries of A~,B~ A, B. Let t:=m−k.t:=m-k. Then 0≤t≤r0≤ t≤ r. Choose a deterministic value of B~,A~ B, A as follows: B~k+1,…,k+t,1,…,t=It,A~1,…,t,k+1,…,k+t=It, B_\k+1,…,k+t\,\1,…,t\=I_t, A_\1,…,t\,\k+1,…,k+t\=I_t, and set all other entries of B~,A~ B, A equal to zero. Then B~A~ B A places an identity block on coordinates k+1,…,k+tk+1,…,k+t. Therefore PSQ+B~A~PSQ+ B A contains an m×m× m identity block, and hence has rank at least m. Thus, at least one m×m× m determinant polynomial is not identically zero. Since the zero set of a nonzero polynomial has Lebesgue measure zero, the same minor is nonzero almost surely for absolutely continuous A~,B~ A, B. Hence rank(S+BA)≥malmost surely.rank(S+BA)≥ m almost surely. (11) On the other hand, by subadditivity of rank, rank(S+BA)≤rank(S)+rank(BA)≤k+r.rank(S+BA) (S)+rank(BA)≤ k+r. (12) Also rank(S+BA)≤nrank(S+BA)≤ n. Therefore rank(S+BA)≤minn,k+r=m.rank(S+BA)≤ \n,k+r\=m. (13) Combining Equations 11 and 13 gives rank(S+BA)=m=minn,k+rrank(S+BA)=m= \n,k+r\ almost surely. ∎ B.2 Structural rank and maximum matchings Definition B.2 (Structural rank). For a support pattern Ω⊆[n]×[n] [n]×[n], define the bipartite graph GΩ=([n]row,[n]col,Ω).G_ =([n]_row,[n]_col, ). The structural rank of Ω is the largest rank achievable by any matrix whose nonzero entries are restricted to the support Ω . Lemma B.3 (Structural rank equals maximum matching). Let XΩ∈ℝn×nX_ ^n× n be a sparse matrix supported on Ω . Assume that its nonzero entries are algebraically generic. Then rank(XΩ)=ν(Ω)almost surely.rank(X_ )=ν( ) almost surely. (14) Proof. Let m:=ν(Ω).m:=ν( ). Since the graph GΩG_ has a matching of size m, there exist row and column sets I,J⊆[n]I,J [n], with |I|=|J|=m|I|=|J|=m, such that the subgraph induced by I,JI,J contains a perfect matching. Consider the determinant of the submatrix XΩ,I,JX_ ,I,J. Expanding this determinant as a polynomial in the nonzero variables xij:(i,j)∈Ω,\x_ij:(i,j)∈ \, the perfect matching contributes a monomial of the form ∏(i,j)∈Mxij. _(i,j)∈ Mx_ij. (15) Different perfect matchings correspond to different monomials. Therefore this determinant polynomial is not identically zero. Since the entries are algebraically generic, the determinant is nonzero almost surely. Hence rank(XΩ)≥m.rank(X_ )≥ m. (16) Conversely, suppose that rank(XΩ)≥m+1rank(X_ )≥ m+1. Then there exists an (m+1)×(m+1)(m+1)×(m+1) minor that is not identically zero as a polynomial in the nonzero entries. In the determinant expansion of this minor, at least one permutation monomial must be present. Such a monomial corresponds to a matching of size m+1m+1 in GΩG_ , contradicting the maximality of ν(Ω)=mν( )=m. Therefore rank(XΩ)≤m.rank(X_ )≤ m. (17) Combining Equations 16 and 17 gives rank(XΩ)=ν(Ω)rank(X_ )=ν( ) almost surely. ∎ B.3 Hall deficiency and weighted Hall failure Definition B.4 (Neighborhood of a row set). For a set I⊆[n]I [n] of row vertices, define its neighborhood in the support graph GΩG_ by NΩ(I):=j∈[n]:∃i∈I such that (i,j)∈Ω.N_ (I):=\j∈[n]:∃ i∈ I such that (i,j)∈ \. (18) Lemma B.5 (Deficiency form of Hall’s theorem). For the bipartite graph GΩG_ , n−ν(Ω)=maxI⊆[n](|I|−|NΩ(I)|).n-ν( )= _I [n] (|I|-|N_ (I)| ). (19) Consequently, ν(Ω)<n−rν( )<n-r if and only if there exists I⊆[n]I [n] such that |NΩ(I)|≤|I|−r−1.|N_ (I)|≤|I|-r-1. (20) Proof. This is the standard deficiency form of Hall’s theorem. A matching of size at least n−rn-r exists if and only if every row set I⊆[n]I [n] has deficiency at most r, namely |I|−|NΩ(I)|≤r.|I|-|N_ (I)|≤ r. Equivalently, |NΩ(I)|≥|I|−rfor all I⊆[n].|N_ (I)|≥|I|-r for all I [n]. Thus, the condition fails if and only if there exists I⊆[n]I [n] such that |NΩ(I)|≤|I|−r−1.|N_ (I)|≤|I|-r-1. ∎ Lemma B.6 (Weighted Hall failure bound). Assume that the edge indicators Ωij _ij are independent Bernoulli random variables with probabilities qijq_ij. Let R:=r+1R:=r+1. For I,U⊆[n]I,U [n], define Λ(I,U):=∑i∈I,j∈Uqij. (I,U):= _i∈ I,\ j∈ Uq_ij. Then ℙ[ν(Ω)<n−r]≤∑I,U⊆[n]|I|≥R,|U|≥R,|I|+|U|≥n+Rexp(−Λ(I,U)).P[ν( )<n-r]≤ _ subarraycI,U [n]\\ |I|≥ R,\ |U|≥ R,\ |I|+|U|≥ n+R subarray (- (I,U)). (21) Proof. By Lemma B.5, the event ν(Ω)<n−rν( )<n-r occurs if and only if there exists I⊆[n]I [n] such that |NΩ(I)|≤|I|−r−1.|N_ (I)|≤|I|-r-1. Let J:=NΩ(I)J:=N_ (I) and U:=JcU:=J^c. Then no edges exist from I to U. Moreover, |U|=n−|J|≥n−|I|+r+1.|U|=n-|J|≥ n-|I|+r+1. Equivalently, |I|+|U|≥n+r+1=n+R.|I|+|U|≥ n+r+1=n+R. Also, such a violation can occur only when |I|≥R|I|≥ R, and the previous display implies |U|≥R|U|≥ R. Thus, Hall failure implies the existence of sets I,U⊆[n]I,U [n] satisfying |I|≥R,|U|≥R,|I|+|U|≥n+R,|I|≥ R, |U|≥ R, |I|+|U|≥ n+R, with no edges in the rectangle I×UI× U. For fixed I,UI,U, the probability that there are no edges in I×UI× U is ∏i∈I,j∈U(1−qij)≤exp(−∑i∈I,j∈Uqij)=exp(−Λ(I,U)). _i∈ I,\ j∈ U(1-q_ij)≤ (- _i∈ I,\ j∈ Uq_ij )= (- (I,U)). Taking a union bound over all admissible I,UI,U gives the result. ∎ B.4 Proof of the deterministic rank proposition Proof of Proposition 4.5. By Lemma B.3, the sparse matrix SΩS_ satisfies rank(SΩ)=ν(Ω)rank(S_ )=ν( ) almost surely under the generic-values assumption. Applying Lemma B.1 with S=SΩS=S_ , we get rank(SΩ+BA) (S_ +BA) =minn,rank(SΩ)+r = \n,rank(S_ )+r\ =minn,ν(Ω)+r = \n,ν( )+r\ (22) almost surely. In particular, if ν(Ω)≥n−r,ν( )≥ n-r, then rank(SΩ+BA)=nrank(S_ +BA)=n almost surely. ∎ B.5 Proof of the main full-rank theorem Proof of Theorem 4.6. Condition on Q,KQ,K. Then the angular collision probabilities qijq_ij are fixed numbers in [0,1][0,1]. By Lemma B.6, ℙ[ν(Ω)<n−r∣Q,K]≤Δr(Q,K).P[ν( )<n-r Q,K]≤ _r(Q,K). Therefore, with probability at least 1−Δr(Q,K)1- _r(Q,K), we have ν(Ω)≥n−r.ν( )≥ n-r. On this event, Proposition 4.5 implies rank(SΩ+BA)=nrank(S_ +BA)=n almost surely over the generic low-rank factors A,BA,B. Hence ℙ[rank(SΩ+BA)=n|Q,K]≥1−Δr(Q,K).P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1- _r(Q,K). ∎ Appendix C Interpretable High-Probability Corollaries The main theorem gives the full-rank probability through the quantity Δr(Q,K) _r(Q,K). In this section, we give several sufficient conditions under which Δr(Q,K)≤n−c _r(Q,K)≤ n^-c, so that ℙ[rank(SΩ+BA)=n|Q,K]≥1−n−c.P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1-n^-c. These corollaries are not meant to exhaust all possible conditions. Rather, they show different ways to interpret the rank guarantee: through uniform cut-density, through a conservative worst-case angular lower bound, and through an idealized isotropic mean model. C.1 A combinatorial rectangle bound Lemma C.1 (A binomial rectangle bound). Let R∈[n]R∈[n]. Suppose a,h∈R,…,na,h∈\R,…,n\ satisfy a+h≥n+R.a+h≥ n+R. Then log(na)+log(nh)≤8ahnlogenR. na+ nh≤ 8\, ahn enR. (23) Proof. We use the standard bound (nt)=(n−t)≤(enmint,n−t)mint,n−t, nt= nn-t≤ ( en \t,n-t\ ) \t,n-t\, with the convention that the corresponding term is zero when mint,n−t=0 \t,n-t\=0. First suppose a≤n/2a≤ n/2. Since a+h≥n+Ra+h≥ n+R, we have n−h≤a−R≤a.n-h≤ a-R≤ a. Therefore, log(na)+log(nh) na+ nh =log(na)+log(n−h) = na+ nn-h ≤alogena+(n−h)logen−h ≤ a ena+(n-h) enn-h ≤2alogena ≤ 2a ena ≤2alogenR. ≤ 2a enR. (24) Also h≥n/2h≥ n/2, so ah/n≥a/2ah/n≥ a/2. Hence log(na)+log(nh)≤4ahnlogenR. na+ nh≤ 4\, ahn enR. The case h≤n/2h≤ n/2 is symmetric. It remains to consider the case a>n/2a>n/2 and h>n/2h>n/2. Then (na)(nh)≤22n, na nh≤ 2^2n, so log(na)+log(nh)≤2nlog2. na+ nh≤ 2n 2. Since a>n/2a>n/2 and h>n/2h>n/2, we have ah/n>n/4ah/n>n/4. Also log(en/R)≥1 (en/R)≥ 1. Therefore 8ahnlogenR≥2n≥2nlog2.8\, ahn enR≥ 2n≥ 2n 2. Combining the cases proves the claim. ∎ C.2 Deficiency-aware collision density Corollary C.2 (Deficiency-aware collision density). Fix c>0c>0, and suppose 0≤r<n0≤ r<n. Let R:=r+1,R:=r+1, and define pr,c:=1n(8logenR+(c+2)lognR).p_r,c:= 1n (8 enR+ (c+2) nR ). (25) Suppose that for every pair of sets I,U⊆[n]I,U [n] satisfying |I|≥R,|U|≥R,|I|+|U|≥n+R,|I|≥ R, |U|≥ R, |I|+|U|≥ n+R, we have the cut-density lower bound Λ(I,U)=∑i∈I,j∈Uqij≥pr,c|I||U|. (I,U)= _i∈ I,\ j∈ Uq_ij≥ p_r,c|I||U|. (26) Then, under the assumptions of Theorem 4.6, ℙ[rank(SΩ+BA)=n|Q,K]≥1−n−c.P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1-n^-c. (27) Proof. Let R:=r+1.R:=r+1. Recall from Theorem 4.6 that the failure probability is bounded by Δr(Q,K)=∑I,U⊆[n]|I|≥R,|U|≥R,|I|+|U|≥n+Rexp(−Λ(I,U)). _r(Q,K)= _ subarraycI,U [n]\\ |I|≥ R,\ |U|≥ R,\ |I|+|U|≥ n+R subarray (- (I,U)). For fixed cardinalities a:=|I|,h:=|U|,a:=|I|, h:=|U|, the cut-density assumption gives Λ(I,U)≥pr,cah. (I,U)≥ p_r,cah. Therefore, Δr(Q,K) _r(Q,K) ≤∑a,h∈R,…,na+h≥n+R(na)(nh)exp(−pr,cah). ≤ _ subarrayca,h∈\R,…,n\\\ a+h≥ n+R subarray na nh (-p_r,cah). (28) By the definition of pr,cp_r,c, pr,cah=ahn(8logenR+(c+2)lognR).p_r,cah= ahn (8 enR+ (c+2) nR ). Using Lemma C.1, log(na)+log(nh)≤8ahnlogenR. na+ nh≤ 8\, ahn enR. Hence, for each admissible cardinality pair (a,h)(a,h), (na)(nh)exp(−pr,cah) na nh (-p_r,cah) ≤exp(−ahnR(c+2)logn). ≤ (- ahnR(c+2) n ). (29) Since a,h≥Ra,h≥ R and a+h≥n+Ra+h≥ n+R, the product ahah is minimized at (a,h)=(R,n)(a,h)=(R,n) or (n,R)(n,R). Thus ah≥nR.ah≥ nR. Therefore each admissible cardinality pair contributes at most n−(c+2).n^-(c+2). There are at most n2n^2 admissible pairs (a,h)(a,h). Consequently, Δr(Q,K)≤n2⋅n−(c+2)=n−c. _r(Q,K)≤ n^2· n^-(c+2)=n^-c. Applying Theorem 4.6 completes the proof. ∎ The threshold pr,cp_r,c is deficiency-aware. When r=0r=0, the sparse graph itself must contain a perfect matching, and the sufficient sparse density has the familiar O(logn/n)O( n/n) scaling. When r>0r>0, the sparse graph is allowed to have matching deficiency up to r, and the rank-r low-rank branch fills the missing directions. C.3 Conservative worst-case angular condition Corollary C.3 (Conservative worst-case angular condition). Fix c>0c>0, suppose 0≤r<n0≤ r<n, and let pr,cp_r,c be defined as in Equation 25. Let ρmin:=mini,jρij. _ := _i,j _ij. If 1−exp(−Lsρminγ)≥pr,c,1- (-L_s _ ^γ)≥ p_r,c, (30) then, under the assumptions of Theorem 4.6, ℙ[rank(SΩ+BA)=n|Q,K]≥1−n−c.P\! [rank(S_ +BA)=n\, |\,Q,K ]≥ 1-n^-c. (31) Equivalently, when pr,c<1p_r,c<1 and ρmin>0 _ >0, it is sufficient that Ls≥−log(1−pr,c)ρminγ.L_s≥ - (1-p_r,c) _ ^γ. (32) Proof. For every pair (i,j)(i,j), qij≥1−exp(−Lsρijγ).q_ij≥ 1- (-L_s _ij^γ). By definition of ρmin _ , ρij≥ρminfor all i,j. _ij≥ _ for all i,j. Therefore, qij≥1−exp(−Lsρminγ).q_ij≥ 1- (-L_s _ ^γ). If 1−exp(−Lsρminγ)≥pr,c,1- (-L_s _ ^γ)≥ p_r,c, then qij≥pr,cq_ij≥ p_r,c for all i,ji,j. Hence, for every admissible rectangle I×UI× U, Λ(I,U)=∑i∈I,j∈Uqij≥pr,c|I||U|. (I,U)= _i∈ I,\ j∈ Uq_ij≥ p_r,c|I||U|. Thus the cut-density condition in Corollary C.2 holds, and the desired high-probability full-rank conclusion follows. Finally, when pr,c<1p_r,c<1 and ρmin>0 _ >0, the inequality 1−exp(−Lsρminγ)≥pr,c1- (-L_s _ ^γ)≥ p_r,c is equivalent to exp(−Lsρminγ)≤1−pr,c, (-L_s _ ^γ)≤ 1-p_r,c, which holds whenever Ls≥−log(1−pr,c)ρminγ.L_s≥ - (1-p_r,c) _ ^γ. ∎ Remark C.4 (Worst-case angular conditions are pessimistic). Corollary C.3 uses the minimum angular similarity over all n2n^2 query-key pairs and is therefore conservative. In practice, full rank does not require every pair to have large collision probability; it only requires that no Hall-relevant rectangle has too little total collision mass. Thus, some individual pairs may have very small collision probability, as long as no large query set is separated from too many key vertices. C.4 Isotropic mean Hoeffding certificate Corollary C.5 (Isotropic mean Hoeffding certificate). Fix c>0c>0, δ∈(0,1)δ∈(0,1), and suppose 0≤r<n0≤ r<n. Let R:=r+1.R:=r+1. For a,h∈R,…,na,h∈\R,…,n\ satisfying a+h≥n+Ra+h≥ n+R, define τa,h,c:=log(na)+log(nh)+(c+2)lognah, _a,h,c:= na+ nh+(c+2) nah, (33) and βa,h,δ:=log(na)+log(nh)+log(n2/δ)2ah. _a,h,δ:= na+ nh+ (n^2/δ)2ah. (34) Let Θr,c,δ:=maxa,h∈R,…,na+h≥n+R(τa,h,c+βa,h,δ). _r,c,δ:= _ subarrayca,h∈\R,…,n\\\ a+h≥ n+R subarray ( _a,h,c+ _a,h,δ ). (35) Assume an idealized isotropic collision-probability model in which the entries qij∈[0,1]q_ij∈[0,1] are independent random variables with common mean μq _q. Moreover, assume that the isotropic angular estimate is a conservative lower approximation to this mean: μq≥q¯iso−εiso,q¯iso:=1−(1−2−γ)Ls, _q≥ q_iso- _iso, q_iso:=1- (1-2^-γ )^L_s, (36) where εiso≥0 _iso≥ 0 measures the approximation slack. In the sparse-collision regime Ls2−γ≪1L_s2^-γ 1, q¯iso=Ls2−γ+O(Ls22−2γ). q_iso=L_s2^-γ+O\! (L_s^22^-2γ ). If q¯iso−εiso≥Θr,c,δ, q_iso- _iso≥ _r,c,δ, (37) then, with probability at least 1−δ1-δ over the draw of the probability matrix (qij)(q_ij), all Hall-relevant rectangles satisfy 1|I||U|∑i∈I,j∈Uqij≥τ|I|,|U|,c. 1|I||U| _i∈ I,\ j∈ Uq_ij≥ _|I|,|U|,c. (38) Consequently, under 4.3 and 4.4, with probability at least 1−δ1-δ over the draw of (qij)(q_ij), ℙ[rank(SΩ+BA)=n|(qij)i,j]≥1−n−c.P\! [rank(S_ +BA)=n\, |\,(q_ij)_i,j ]≥ 1-n^-c. (39) Equivalently, over the joint randomness of the collision probabilities, the sparse support, and the low-rank factors, ℙ[rank(SΩ+BA)=n]≥1−δ−n−c.P\! [rank(S_ +BA)=n ]≥ 1-δ-n^-c. (40) Proof. Fix admissible cardinalities a,h∈R,…,na,h∈\R,…,n\ satisfying a+h≥n+R.a+h≥ n+R. For fixed sets I,U⊆[n]I,U [n] with |I|=a|I|=a and |U|=h|U|=h, define q¯(I,U):=1ah∑i∈I,j∈Uqij. q(I,U):= 1ah _i∈ I,\ j∈ Uq_ij. Under the idealized isotropic collision-probability model, the entries qij∈[0,1]q_ij∈[0,1] are independent with common mean μq _q. Hence Hoeffding’s inequality gives ℙ[q¯(I,U)<μq−βa,h,δ]≤exp(−2ahβa,h,δ2).P [ q(I,U)< _q- _a,h,δ ]≤ (-2ah _a,h,δ^2). By the definition of βa,h,δ _a,h,δ, exp(−2ahβa,h,δ2)=exp(−log(na)−log(nh)−log(n2/δ)). (-2ah _a,h,δ^2)= (- na- nh- (n^2/δ) ). Taking a union bound over all (na)(nh) na nh pairs of sets with these cardinalities, the probability that any such rectangle violates the bound is at most δn2. δn^2. Taking another union bound over at most n2n^2 admissible cardinality pairs (a,h)(a,h), we obtain that, with probability at least 1−δ1-δ, every Hall-relevant rectangle satisfies q¯(I,U)≥μq−β|I|,|U|,δ. q(I,U)≥ _q- _|I|,|U|,δ. By assumption, μq≥q¯iso−εiso≥Θr,c,δ. _q≥ q_iso- _iso≥ _r,c,δ. Since Θr,c,δ=maxa,h∈R,…,na+h≥n+R(τa,h,c+βa,h,δ), _r,c,δ= _ subarrayca,h∈\R,…,n\\\ a+h≥ n+R subarray ( _a,h,c+ _a,h,δ ), it follows that every Hall-relevant rectangle satisfies q¯(I,U)≥τ|I|,|U|,c. q(I,U)≥ _|I|,|U|,c. Equivalently, Λ(I,U)=∑i∈I,j∈Uqij≥|I||U|τ|I|,|U|,c. (I,U)= _i∈ I,\ j∈ Uq_ij≥|I||U| _|I|,|U|,c. By the definition of τa,h,c _a,h,c, Λ(I,U)≥log(n|I|)+log(n|U|)+(c+2)logn. (I,U)≥ n|I|+ n|U|+(c+2) n. Therefore, Δr _r =∑I,U⊆[n]|I|≥R,|U|≥R,|I|+|U|≥n+Rexp(−Λ(I,U)) = _ subarraycI,U [n]\\ |I|≥ R,\ |U|≥ R,\ |I|+|U|≥ n+R subarray (- (I,U)) ≤∑a,h∈R,…,na+h≥n+R(na)(nh)exp(−log(na)−log(nh)−(c+2)logn) ≤ _ subarrayca,h∈\R,…,n\\\ a+h≥ n+R subarray na nh (- na- nh-(c+2) n ) ≤n2⋅n−(c+2)=n−c. ≤ n^2· n^-(c+2)=n^-c. (41) Applying Theorem 4.6 conditionally on the realized probability matrix (qij)(q_ij) gives ℙ[rank(SΩ+BA)=n|(qij)i,j]≥1−n−cP\! [rank(S_ +BA)=n\, |\,(q_ij)_i,j ]≥ 1-n^-c with probability at least 1−δ1-δ over the draw of (qij)(q_ij). Finally, by the union bound over the two sources of failure, namely failure of the probability matrix to satisfy the rectangle-average condition and failure of the sampled sparse graph to have matching size at least n−rn-r, the joint success probability is at least 1−δ−n−c.1-δ-n^-c. ∎ The role of δ in Corollary C.5 is to control the probability that the random collision-probability matrix itself has a low-density Hall-relevant cut. The term n−cn^-c controls the subsequent failure probability of the sampled sparse graph, conditioned on that probability matrix. In the common sparse-collision regime, the practical design rule suggested by Equation 37 is Ls2−γ≳Θr,c,δ.L_s2^-γ _r,c,δ. Thus, increasing LsL_s increases sparse coverage, while increasing γ makes collisions more selective. C.5 Interpretation and technical remarks Remark C.6 (Interpretation). The rank guarantee is an expressivity statement. It shows that the hybrid sparse + low-rank construction avoids the rank collapse of purely low-rank attention. The sparse collision graph contributes rank through its maximum matching, while the low-rank branch supplies r additional dense directions. Thus, sparse matching size+low-rank dimension≥n sparse matching size+ low-rank dimension≥ n is sufficient for the hybrid attention matrix to be full rank. Remark C.7 (Scope of the probabilistic assumptions). The corollaries above should be read as interpretable regimes in which the error term in Theorem 4.6 becomes small. Some of these regimes make simplifying assumptions, such as independent edge sampling or an idealized isotropic model for the collision probabilities. These assumptions are not intended to fully model every practical hashing implementation. Rather, they expose the mechanism behind the algorithm: if angular sparse sampling produces enough coverage across Hall-relevant cuts, then the sparse component has matching deficiency at most r, and the rank-r low-rank component fills the remaining directions. Remark C.8 (Independence). Theorem 4.6 is stated under an independent angular edge model. Practical LSH collisions may be dependent because the same hash functions are reused across multiple query-key pairs. The deterministic implication in Proposition 4.5, however, does not require independence. It applies to any realized support Ω satisfying ν(Ω)≥n−rν( )≥ n-r. Independence is used only to control the probability that this matching condition fails. Remark C.9 (Deterministic version). The deterministic implication ν(Ω)≥n−r⟹rank(SΩ+BA)=nν( )≥ n-r (S_ +BA)=n holds under the generic sparse-values and generic low-rank assumptions, and does not require independence of the sparse support. Independence is used only to upper bound the probability that ν(Ω)<n−rν( )<n-r. Remark C.10 (When exact sparse values are not generic). If the sparse exact values SΩ=Ω⊙M⋆S_ = M are deterministic and not assumed to be generic, one can use the deterministic condition rank(SΩ)≥n−r.rank(S_ )≥ n-r. Then Lemma B.1 alone implies rank(SΩ+BA)=nrank(S_ +BA)=n almost surely over the low-rank factors A,BA,B. The matching condition ν(Ω)≥n−rν( )≥ n-r is a support-level sufficient condition for this rank condition under generic sparse values. Remark C.11 (Independent safety sparsifier). If one wants a literal independent-edge guarantee while preserving a practical LSH collision rule, one may augment the LSH support by an independent safety sparsifier: Ω=ΩLSH∪Ωsafe,Ωsafe,ij∼Bernoulli(pr,c). = _LSH∪ _safe, _safe,ij \! (p_r,c ). By Corollary C.2, the safety support alone is sufficient to guarantee rank(SΩ+BA)=nrank(S_ +BA)=n with probability at least 1−n−c1-n^-c, under the generic sparse-values and generic low-rank assumptions. Its expected number of additional edges is n2pr,c=n(8logenr+1+(c+2)lognr+1).n^2p_r,c=n (8 enr+1+ (c+2) nr+1 ). Appendix D Experiment Hyperparameters We evaluate all attention variants using encoder-style, non-causal Transformer architectures. Unless otherwise stated, we train with cross-entropy loss and the AdamW optimizer. We use dropout 0.10.1, set qkv_bias=False, and fix the random seed to 42. For the hybrid methods, the gate is a two-layer MLP with SiLU activation and two independent sigmoid outputs, one for the sparse branch and one for the RACE branch. We do not normalize the gates. Table 6: Main dataset-level hyperparameters. Here N denotes the input sequence length after tokenization or patchification. Dataset / Task N Layers Heads d MLP dim Batch Grad. accum. LR WD Epochs IMDB 512 1 2 128 512512 32 1 1×10−51× 10^-5 5×10−55× 10^-5 150 Fashion-MNIST 784 2 4 384 15361536 32 1–2 6×10−46× 10^-4 0.1 150 Oxford-IIIT Pet 16,384 2 4 384 15361536 32 1–2 6×10−46× 10^-4 0.1 150 Flowers-102 16,384 2 4 384 15361536 32 1–2 6×10−46× 10^-4 0.1 150 Food-101 16,384 8 8 512 20482048 8 4 3×10−43× 10^-4 0.001 100 ArXiv classification 32,000 4 4 256 1024 8 16 3×10−43× 10^-4 0.01 33 Text Retrieval 64,000 4 4 256 1024 4 16 3×10−43× 10^-4 0.01 50 For the image experiments, Fashion-MNIST uses 28×2828× 28 grayscale images with patch size 1, giving N=784N=784. Oxford-IIIT Pet and Flowers-102 use 512×512512× 512 RGB images with patch size 4, giving 128×128=16,384128× 128=16,384 image tokens. For Food-101, we use the long-image setting with 512×512512× 512 inputs, patch size 4, and N=16,384N=16,384. The vision models use a learnable class token and learnable positional embeddings. For ArXiv classification, we tokenize documents using a basic English tokenizer, keep documents with at least 1,000 raw tokens, and perform class-balanced streaming packing. Documents from the same class are concatenated until the target sequence length is reached. For the reported ArXiv classification setting, we use N=32,000N=32,000, a vocabulary limit of 50,000, and packed train/test examples produced from the class-balanced long-document subset. For Text Retrieval, we construct binary retrieval-pair examples from the packed ArXiv documents. Each input is formatted as [CLS]doca[SEP]docb,[CLS]\;doc_a\;[SEP]\;doc_b, with label 1 if the two documents come from the same ArXiv class and label 0 otherwise. We use 4,000 training pairs and 1,000 test pairs at N=64,000N=64,000. Table 7: Attention-specific hyperparameters. Component Text settings Vision settings RACE hash bits γ 4 for ArXiv/Retrieval, 3 for IMDB 2 RACE tables LsL_s 4 for ArXiv/Retrieval, 2 for IMDB 5 RACE ensembles M 1 for ArXiv/Retrieval, 2 for IMDB 1 Sort_LSH bits 5 4–5 Sort_LSH block size s 256 for ArXiv/Retrieval, 32 for IMDB 32 Sort_LSH min length 4096 for ArXiv/Retrieval, 256 for IMDB 256 Neighbor blocks 0 0 Gate hidden dim 64 128 Gate normalization False False ϵε for denominator correction 10−610^-6 10−610^-6 For ELSAA, the sparse branch is Sort_LSH and the low-rank branch is RACE. The output is computed as O=gsparsemsparseOsparse+graceOrace,O=g_sparse\,m_sparse\,O_sparse+g_race\,O_race, where gsparseg_sparse and graceg_race are token-wise sigmoid gates. In the denominator-aware version, we use msparse=dsparsedsparse+λdrace+ϵ.m_sparse= d_sparsed_sparse+λ d_race+ε. For the scalar-λ version, λ is parameterized as λ=exp(ℓλ),λ= ( _λ), initialized with λ=1.0λ=1.0, and learned during training. For the input-dependent version, we use λi=c+σ(w⊤qi+b), _i=c+σ(w q_i+b), where c is initialized to 0.3, is learnable, and is constrained to be nonnegative. The bias is initialized so that the initial average target is approximately 0.8. We detach qiq_i from the lambda path, use λmin=10−6 _ =10^-6, and initialize w with standard deviation 10−310^-3. For IMDB, we build a long-review subset at N=512N=512. Reviews with length between N and 2N2N are kept directly, longer reviews are split into overlapping windows with stride N/2N/2, and shorter reviews from the same class are concatenated until they reach the target length. During training, we apply light EDA augmentation using random deletion with probability 0.05 or random token swaps. For the vision datasets, we use standard data augmentation. Fashion-MNIST uses random horizontal flipping and random cropping with padding 4 during training. Oxford-IIIT Pet, Flowers-102, and Food-101 use random resized cropping and horizontal flipping for training, and resize followed by center crop for validation. RGB image datasets are normalized with ImageNet mean and standard deviation. Appendix E Numerical Complexity Example Attention interaction count. We give a concrete example to illustrate the scale of the savings from the sparse–low-rank construction. For N=32,000,s=256,Ls=4,γ=4,N=32,000, s=256, L_s=4, γ=4, full attention computes N2=1.024×109N^2=1.024× 10^9 query–key interactions per head. The sparse sortLSH branch computes Ns=32,000⋅256=8.192×106Ns=32,000· 256=8.192× 10^6 selected interactions, which is 0.8%0.8\% of full attention. The RACE branch uses NLs2γ=32,000⋅4⋅16=2.048×106NL_s2^γ=32,000· 4· 16=2.048× 10^6 bucket interactions, which is 0.2%0.2\% of full attention. Therefore, ELSAA uses N(s+Ls2γ)=32,000(256+64)=1.024×107N(s+L_s2^γ)=32,000(256+64)=1.024× 10^7 interactions, which is 1.0%1.0\% of full attention. This corresponds to roughly a 99.0%99.0\% reduction in attention interactions compared with exact dense attention. Hashing and sorting overhead. The hashing overhead is linear or near-linear in sequence length. The sortLSH branch requires angular hash projections and sorting, approximately O(Ndγsort)+O(NlogN),O(Nd\, _sort)+O(N N), where γsort _sort denotes the number of hash bits used by the sparse selector. The RACE branch requires soft-hash projections and bucket-feature construction, approximately O(NdLsγ)+O(NLsγ2γ).O(Nd\,L_sγ)+O(NL_sγ 2^γ). In our experiments, s, LsL_s, γ, and γsort _sort are fixed hyperparameters. Therefore, these terms scale linearly or near-linearly in N, whereas dense attention scales quadratically. For sufficiently long sequences, the hashing and sorting overhead is dominated by the saved N2N^2 query–key computation. Parameter overhead. The additional learnable parameters introduced by ELSAA are small compared with the base Transformer layer. The standard attention projections WQ,WK,WV,WO∈ℝd×dW_Q,W_K,W_V,W_O ^d× d already contribute O(d2)O(d^2) parameters. In contrast, the scalar-λ version of ELSAA adds only O(1)O(1) parameters, a query-dependent λ version adds O(d)O(d) parameters, and the gate MLP adds O(dg)O(dg) parameters for gate hidden width g≪dg d. Thus, the parameter overhead is negligible relative to the base attention projections, while the main savings come from reducing the input-dependent attention computation.