acceptodds
Under review as a conference paper at ICLR 2027

MASaLA: Mass-Aware Fusion of Sparse and Low-rank Attention

Abstract

The quadratic computational cost of dense attention remains a central obstacle to training Transformers on long inputs. Efficient approximations typically restrict each query to a subset of keys or compress global interactions through low-rank and kernel-based representations. Sparse methods preserve sharp, localized interactions but may miss diffuse global structure, whereas low-rank methods capture broad mixing but can blur concentrated interactions. We propose MASaLA, a mass-aware fusion of sparse and low-rank attention operators that retains dense query, key, value, and output projections. A block-sparse branch computes exact attention over selected key blocks, while a low-rank branch summarizes diffuse global interactions. To account for the branches' different normalization masses, MASaLA uses mass-aware fusion that rescales the sparse contribution according to its estimated relative attention mass. The framework computes attention at subquadratic cost without materializing the full attention matrix. We further show that including each query's own block in the sparse support gives the hybrid operator the capacity to attain full rank regardless of the low-rank budget, overcoming the rank restriction of a purely low-rank approximation. We evaluate MASaLA on long-context classification benchmarks spanning 16K–64K tokens.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Linear Attention, Hybrid Attention, Sparse plus Low-rank Attention

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_P4wxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

MASaLA approximates attention with two branches computed from dense Q, K, and V. A block-sparse branch partitions the sequence into contiguous blocks, scores every key block for each query block, keeps the top-k blocks together with the query's own block, and computes exact softmax attention over that support. A low-rank branch uses RACE, a linear-attention form whose feature map is a vector of soft-LSH bucket probabilities. The two outputs are combined with sigmoid gates, and the sparse branch is additionally rescaled by its estimated share of the attention mass. The experiments train small models (1–8 layers, d = 128–512; Table 6) on classification tasks of 512 to 64K tokens. Appendix B describes a fused Triton kernel. On a single RTX PRO 6000 Blackwell (48 GB), the paper reports forward speedups over FlashAttention of about 3.5× at 32K and 13× at 128K and backward speedups of 3× and 11× for a single attention operator, and peak training memory 1.08× that of FlashAttention for a 4-layer model.

Critical strengths

S1. The fused-kernel design in Appendix B is careful and is the paper's main new technical content. Because RACE is associative, its key/value sums can be computed once and contracted per query inside the epilogue of the block-sparse kernel, so neither branch output is written to HBM. The backward pass recomputes both branches and keeps activation memory linear in N, with measured peak memory 1.08× that of FlashAttention, and the paper notes that its comparisons pad the head dimension of both kernels from 96 to 128. The explanation of why fp16 silently prevents the low-rank projections from training is useful to anyone fusing soft-hash features.

Critical weaknesses

W1. Results in three of the four main tables cannot be attributed to the described method, and the closest prior work is not cited. ELSAA (arXiv:2607.20214) proposes sparse-plus-low-rank attention with a RACE low-rank branch, the same mass-based scaling of the sparse branch, and the same gates, but uses a sortLSH sparse branch. More importantly, rows of Tables 1, 3, and 4 match that paper's reported results cell by cell under different method names (see Q1).

W2. Independently of W1, the evidence does not support the claims about long-context attention. There is no language-model evaluation: every task is classification or synthetic retrieval, and the reported models have 1–8 layers. On ArXiv (Table 2), all methods reach 99.9–100% training accuracy, MASaLA's test accuracy rises from 80.65% at 8K to 99.08% at 64K, and full attention (84.85% on average) trails RACE and every hybrid; the authors note that class-balanced packing may inflate long-length accuracy and that they did not run the per-document control. On vision, MASaLA's test accuracy is 22.51% on 37 classes and 28.33% on 101 classes, with train-test gaps of 69 and 48 points. The experiments therefore offer limited support for the paper's conclusions.

Questions for authors

Q1. Which sparse branch produced the rows labelled MASaLA, Block-Sparse, and BS+RACE? In Tables 3 and 4, these rows match, cell by cell, the rows labelled ELSAA, Sort LSH, and Sort Lsh RACE in the ELSAA paper (arXiv:2607.20214), whose sparse branch is sortLSH; in Table 1, the MASaLA and Block-Sparse rows match its ELSAA and Sparse LSH rows. Please also cite that paper and state the differences explicitly.

Q2. What top-k does the block-sparse branch use? It is not reported anywhere in the paper, including Table 7.

Q3. Do the reported speedups include block scoring, whose cost Appendix B.2 gives as quadratic in N? Please report them with and without it.

Q4. Could you add a language-modeling result, even a small one?

7 comments
AuthorsOpenReview ↗

Response to Reviewer P4wx (1/3)

We thank Reviewer P4wx for the careful review, recognizing the fused kernel as "the paper's main new technical content", and finding the fp16 analysis useful. The ELSAA, provenance, and evaluation concerns prompted substantive corrections, marked in blue. Ethics-related authorship information is addressed separately to the AC and Program Chairs to preserve double-blind anonymity.


W1 and Q1: Which sparse branch produced the results? What distinguishes MASaLA from ELSAA (arXiv:2607.20214)?

Response to W1 and Q1 (revised Secs. 2–3.2, Table 7, App. F):

We agree that the submission did not adequately distinguish MASaLA from ELSAA and inconsistently identified implementations. Some results using ELSAA's sortLSH branch appeared under Sec. 3.2's block-sparse description; ELSAA was also omitted from the references. Both were errors. The revision corrects attribution and identifies confirmed configurations.

1. Experimental provenance.

ResultsSparse branchEvidence
Table 1, MASaLA and BS+RACEsortLSHRevised Sec. 3.2
Table 2, MASaLA and BS+RACEsortLSHRevised Sec. 3.2, Table 7
Imagenette (new App. F.6)Block-sparseRevised protocol
Causal language modeling (new App. F.5)Block-sparseExplicit causal block selection
Kernel timing and memoryBlock-sparseFused implementation, App. F.1

Table 7 lists the vision settings as block-sparse. As the reviewer notes, however, Table 3 and the IMDB columns of Table 4 coincide with ELSAA tables. We are therefore rechecking the run configurations for those rows in CIFAR-10 in Table 4 and for the Block-Sparse and Scatterbrain rows in Tables 1–2, and will post the row-by-row mapping in this thread. Until then, we do not count these rows as evidence for the block-sparse implementation.

2. What the results establish.

The sortLSH results characterize the previously developed fusion formulation with ELSAA's branch, not independent validation of MASaLA's block-sparse kernel. Direct evidence for the new implementation comes from kernel benchmarks, Imagenette, and causal language modeling, each with explicit block selection. We separate these from prior fusion results.

3. Does the sparse branch matter?

App. F.7 compares branches under the same fusion formulation:

DatasetsortLSHBlock-sparse
Flowers-10240.7%42.4%
Oxford-IIIT Pet19.1%18.9–19.3%

Accuracy is comparable in these configurations: block-sparse has a modest Flowers-102 advantage and overlapping Pet performance. However, these are separate runs with incompletely logged seeds, not evidence of general interchangeability or unchanged method rankings across datasets. No directly corresponding block-sparse ArXiv run exists, so we do not extrapolate its sortLSH results.

4. What MASaLA adds beyond ELSAA.

The fusion rule

gSmOS+gRORg_SmO_S+g_RO_R

already appears in ELSAA and is not a MASaLA contribution. The revision cites ELSAA; introductory wording will be corrected wherever it still implies otherwise. MASaLA's distinct contributions are:

(a) A fused Triton implementation. One kernel computes both branches and fusion, with a recomputation-based backward pass. Peak training memory is 1.08× FlashAttention up to 262K tokens. Including selection, forward speedups are 3.6×, 6.9×, and 13.3× at 32K, 64K, and 128K. This is the implementation contribution highlighted by the reviewer.

(b) Block-sparse architecture and rank analysis. Unlike ELSAA's sortLSH branch, MASaLA selects contiguous key blocks and always includes the query's own and first blocks, enabling regular tiled computation and a fixed sparse budget. Lemma 1 establishes full rank for the ungated hybrid; new Proposition 1 extends it to the implemented gated operator for almost every parameter value. Full rank is not claimed as unique to MASaLA: the analysis establishes its preservation under low-rank fusion and gating.

(c) Fusion characterization. We measure complete selection-inclusive complexity, compare mm with exact support mass, test gate-only fusion, analyze query/key-norm and temperature sensitivity, and compare fusion rules on matched sparse support. These correct two interpretations: mm does not estimate exact sparse-support attention mass, and gate-only matches MASaLA's clean Imagenette accuracy.

These contributions distinguish MASaLA's architecture, implementation, and analysis without claiming the prior fusion rule as new.

AuthorsOpenReview ↗

Response to Reviewer P4wx (2/3)

Q2: What top-k does the block-sparse branch use?

Response to Q2 (revised Sec. 3.2, Table 7, App. F.5):

For the block-sparse vision experiments, Imagenette, and timing benchmarks, we use block size 64 and top-k=4k=4 selected blocks, together with the query's own and first blocks, giving 384 keys per query.

For causal language modeling, we use top-8 past blocks plus the query's own block, without forcing the first block.

The sortLSH-based runs do not use block-sparse top-kk selection. The ArXiv configurations use block size 256 (512 at 64K), as specified in Table 7.

These details are now stated explicitly to distinguish the implementations.


Q3: Do the reported speedups include block scoring? Report results with and without scoring.

Response to Q3 (Fig. 2, revised Sec. 6, App. F.1):

Yes. The reported end-to-end speedups include block scoring and top-kk selection. We additionally measured a selection-free positional-block baseline to quantify this overhead.

Sequence lengthWith scoringWithout scorer
32K3.6×3.8×
64K6.9×7.3×
128K13.3×14.2×

The selection-free configuration is a timing reference and was not trained.

At 128K, the forward takes 15.9 ms including selection versus 14.9 ms without it. Scoring and top-kk contribute approximately 7%, 6%, and 6% of forward time at 32K, 64K, and 128K, respectively. The backward pass has no selection overhead and achieves a 10.9× speedup at 128K.

We also corrected the scorer description. The original App. B.2 described a raw-key scorer that was never used in the experiments. Its forward speedups would be 2.8× / 4.7× / 7.2×, substantially below the implemented mean-pooled scorer.

The complete complexity is now stated as

Θ(N(s+Ls2γ)+(N/B)2dh),\Theta\big(N(s+L_s2^\gamma)+(N/B)^2d_h\big),

which is quadratic in NN for fixed BB. We removed unsupported linear and subquadratic claims for the complete method.

Fig. 2 uses shared projections between the branches. With separate projections, the 128K speedups are 11.8× forward and 10.0× backward. The timing configuration (Ls=4L_s=4, γ=4\gamma=4, gate width 64) differs from that used for the trained vision models (Ls=5L_s=5, γ=2\gamma=2, gate width 128).

Thus, although block scoring introduces a quadratic term, the measured end-to-end efficiency advantage remains substantial with that cost included.

AuthorsOpenReview ↗

Response to Reviewer P4wx (3/3)

W2 and Q4: No language-model evaluation; small models; packed ArXiv inputs; low vision accuracy and large train–test gaps.

Response to W2 and Q4 (revised Secs. 5, 7–8, new App. F.4–F.6):

We agree that the submission insufficiently addressed these limitations. We added pretrained causal language modeling, a single-document ArXiv control, and a vision benchmark with multiple MASaLA seeds and smaller train–test gaps.

1. Pretrained causal language modeling (new App. F.5).

We replaced every attention layer of Qwen2.5-0.5B and adapted it with rank-8 LoRA for 300 steps at T=16,384T=16{,}384 on WikiText-103, using strictly causal block selection and one seed per method.

Perplexity, lower is better:

Method4K16K
Full attention10.9510.38
Block-Sparse11.9411.74
Scatterbrain12.3412.04
MASaLA (gated)12.1212.09
BS+RACE (ungated, m=1m=1)13.8513.16

MASaLA operates in a pretrained causal model at 16K, within approximately 1.2–1.7 perplexity points of full attention. Gating improves on ungated BS+RACE by 1.73 points at 4K and 1.07 at 16K. MASaLA is comparable to Scatterbrain, outperforming it at 4K but not 16K.

However, Block-Sparse alone outperforms both hybrids: the low-rank branch provides no predictive benefit in this short-adaptation setting. App. F.5 and Sec. 8 explicitly state this limitation rather than generalizing the vision results to causal language modeling.

This establishes causal compatibility and predictive performance, not causal speedup: runtime benchmarks remain non-causal.

2. Single-document ArXiv control (new App. F.4).

As the reviewer observed, the original long ArXiv inputs packed shorter same-class documents because few individual documents reach 34K tokens. The 32K–64K experiments therefore largely evaluated classification from multiple documents, not one long document.

We added one 4,096-token document per 32,768-token input, using the packed experiments' training budget.

Validation accuracy, one seed each:

MethodAccuracy
MASaLA41.0%
Scatterbrain40.2%

The 0.8-point difference does not establish superiority with one seed per method. Both results are far below packed-document accuracies (above 90%), supporting the concern that the original benchmark largely measures aggregation of same-class evidence.

Sec. 7 now states this limitation, and we give Imagenette greater weight in the accuracy comparison than packed ArXiv.

3. Vision performance and overfitting (new App. F.6).

Pet and Flowers-102 have approximately 3.7K and 1K training images. Low accuracy and overfitting from scratch at 16K tokens made those results difficult to interpret; even full attention achieved only 24.66% test accuracy on Pet.

We therefore added Imagenette: approximately 9.5K training images, 10 classes, and 16K-token inputs.

MethodTrain accuracyTest accuracy
Full attention80.6378.12
MASaLA75.90 ± 0.0474.42 ± 0.27
Scatterbrain (RACE)72.4173.86
Block-Sparse71.2371.85
RACE68.9371.92

MASaLA uses three seeds (mean ± standard deviation); other methods use one each. It exceeds the reported Scatterbrain run by 0.56 points and either individual branch by approximately 2.5 points. Its three test accuracies are 74.73%, 74.22%, and 74.32%. All exceed the reported baseline runs, but additional baseline seeds are needed to establish statistical significance.

Train–test gaps are much smaller than in the original small-data benchmarks: 1.48 points for MASaLA and 2.51 for full attention. Imagenette thus provides more interpretable evidence for the tested architecture. Models remain relatively small; we do not extrapolate beyond the evaluated sizes to larger pretrained systems.


We thank the reviewer for identifying these issues. The revision clarifies the relationship to ELSAA, corrects implementation and complexity descriptions, reports selection-inclusive efficiency, and adds causal language-modeling, single-document, and multi-seed vision experiments.

The fusion rule predates MASaLA, and some original rows still require fuller provenance documentation. We distinguish these limitations from the independently evaluated block-sparse implementation and fused Triton kernel, our principal technical contribution.

We hope the corrected attribution, clearer contribution boundaries, and new evidence address the concerns. We would be grateful if the reviewer would reconsider the evaluation and welcome further questions.

Reviewer_xBJJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes to tackle the quadratic computational bottleneck of dense attention by combining block-sparse attention and low rank approximation techniques. The authors point out that naively merging these two ideas can distort the attentional scale, and propose MASaLS which enables scale-aware fusion. They propose to rescale the sparse contribution relative to the low-rank mask guided by learnable gates. MASaLA is able to achieve linear instead of quadratic computation, showing wall-clock speedups compared to other methods such as Flash Attention.

Critical strengths
  • The work provides theoretical grounds (lemma 1) of their method showing that the query's own block guarantees a matching that removes the rank ceiling other imposed by low-rank estimators.
  • The work provides experimental validation based on a fused triton kernel implementation matching the asymptotic memory scaling of Flash attention.
Critical weaknesses
  • The proposed method's precision constraints (bf16) seems rather rigid and limits the method's scalability to mixed precision training pipelines which is a lot of the cases.
  • The experiment resuts show that the optimal configuration for the method to work is highly task dependent, and it seems hard to know how practitioners can set the right configs when deploying the model on unseen data.
  • The evals seem to be limited to non-causal and classification retrieval tasks. As the authors explicitly mention that the application to autoregressive lm pretraining is limited, I think this is a big weakness,
Questions for authors

Please address the weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer xBJJ (1/2)

We thank Reviewer xBJJ for recognizing the "theoretical grounds (Lemma 1)" and the "fused Triton kernel implementation matching the asymptotic memory scaling of FlashAttention". We appreciate the reviewer's constructive concerns regarding mixed-precision compatibility, task-dependent configuration, and evaluation beyond non-causal tasks. All three have been addressed through corrections, additional analysis, and new experiments in the revised paper (changes in blue).


W1: The bf16 precision constraint seems rigid and limits mixed-precision training.

Response to W1 (revised App. B.5):

We agree that the original wording ("requirement", "constraint") incorrectly suggested that bf16 restricts the training pipeline. bf16 is the default kernel precision, not a requirement for mixed-precision training.

MASaLA supports the standard bf16 autocast setting: model weights, residual streams, gradients, and optimizer states remain in fp32, while kernel inputs (queries, keys, values, and RACE features) are cast to bf16. Inside the kernel, sums, both denominators, and fusion are accumulated in fp32; outputs are returned in fp32. Thus, MASaLA integrates into an existing torch.autocast bf16 pipeline without changes or loss scaling, using the same general mixed-precision strategy as FlashAttention.

The kernel also accepts fp32 inputs, at a higher memory cost. We use bf16 by default because its fp32-equivalent exponent range avoids the underflow observed with small RACE feature gradients in fp16. fp16 with loss scaling has not been tested, and the revised App. B.5 explicitly states this limitation.


W2: The optimal configuration is task dependent; how should practitioners choose it?

Response to W2 (revised Secs. 7–8, Fig. 2, Tables 1–4, new App. F.3 and F.6):

We agree that the best configuration depends on the task and that the original paper did not provide sufficiently clear guidance. Rather than proposing a universal configuration, we now distinguish the regimes supported by our measurements.

1. Practical configuration guide.

SettingRecommended choiceSupporting evidence
Short inputs (below approximately 10K tokens)Exact attentionFlashAttention is faster below the measured crossover (N≈10,600N\approx10{,}600, Fig. 2) and is at least as accurate on IMDB (Table 4)
Long non-causal inputs (16K and above)Gated MASaLA as an efficient candidateImagenette: 74.42 ± 0.27% vs. 73.86% Scatterbrain and approximately 71.9% for each single branch; 3.6×–13.3× measured forward speedups at 32K–128K
Exact retrieval well beyond training lengthBlock-Sparse aloneNIAH trained at 1K: Block-Sparse maintains 100% accuracy through 64K; MASaLA achieves 100% through 16K, 98.8% at 32K, and 84.2% at 64K
Pretrained causal language modelingBlock-Sparse alone among the evaluated efficient methodsQwen2.5-0.5B: 11.74 vs. 12.09 perplexity for MASaLA at 16K (new App. F.5)

These results provide a more actionable distinction than sequence length alone: gated fusion is promising for long non-causal inputs, whereas tasks dominated by exact retrieval or short adaptation of pretrained softmax models can favor the sparse branch alone. The guidance reflects the tested settings rather than a universal performance guarantee.

2. Choosing the fusion coefficient and temperature.

The new gate-only control (m≡1m\equiv1) reaches 74.34% on Imagenette, compared with 74.42 ± 0.27% for MASaLA. Thus, the scale correction mm does not establish an improvement in clean accuracy, and we no longer recommend it on that basis. The gated combination remains the relevant empirical mechanism.

In the perturbation experiments (App. F.3), MASaLA showed smaller degradation than gate-only across all nine measured settings, including key-norm noise σ=1\sigma=1 (−6.7 vs. −23.7 points). However, these comparisons use one checkpoint per model, so we do not claim that mm causes the robustness difference.

The trained MASaLA model is relatively insensitive to moderate changes of two fusion-related settings: multiplying λ\lambda by 0.1–10 changes Imagenette accuracy by at most 0.25 points, and changing attention temperature by ×0.5–×4 changes it by at most 0.6 points. These measurements suggest limited tuning sensitivity within the tested ranges, not across all configurations.

3. Scope of the configuration evidence.

All reported 16K vision experiments use block size 64, top-4 selected blocks plus the query's own and first blocks (384 keys per query). We have not systematically swept block size, number of selected blocks, or RACE settings, and therefore make no claim that these choices are universally optimal.

We have clarified this task dependence in Secs. 7–8. The table above summarizes the resulting practical guidance and can be incorporated into the final manuscript.

AuthorsOpenReview ↗

Response to Reviewer xBJJ (2/2)

W3: Evaluations are limited to non-causal classification and retrieval; no autoregressive language modeling.

Response to W3 (new App. F.5, revised Sec. 8):

We agree that evaluation only on non-causal classification and synthetic retrieval was an important limitation. To address this, we added a causal language-modeling experiment on Qwen2.5-0.5B, replacing every attention layer and adapting the model with LoRA (rank 8) for 300 steps at sequence length T=16,384T=16{,}384 on WikiText-103.

The experiment uses strictly causal block selection (block size 64, top-8 past blocks plus the query's own block), with one seed per method. We evaluate perplexity at 4K and 16K tokens, with lower values indicating better performance.

MethodT=4096T=4096T=16384T=16384
Full attention10.9510.38
Block-Sparse11.9411.74
Scatterbrain12.3412.04
MASaLA (gated)12.1212.09
BS+RACE (ungated, m=1m=1)13.8513.16

These results establish three points.

1. The causal extension is functional. MASaLA can replace all attention layers in a pretrained causal language model and be adapted with LoRA. It achieves perplexity within approximately 1.2–1.7 points of full attention at both evaluated context lengths. This extends the evaluation beyond the non-causal settings of the original submission.

2. Gating improves substantially over ungated fusion. MASaLA achieves 12.12 / 12.09 perplexity versus 13.85 / 13.16 for the ungated BS+RACE combination, improvements of 1.73 and 1.07 perplexity points at 4K and 16K, respectively. Its performance is also comparable to Scatterbrain (12.34 / 12.04). Thus, the gated combination improves over naive addition of the branches in this causal experiment, although it does not consistently outperform Scatterbrain.

3. The low-rank branch does not improve over Block-Sparse alone in this setting. Block-Sparse achieves the best perplexity among the evaluated efficient methods (11.94 / 11.74), outperforming both hybrid approaches. We explicitly acknowledge this limitation rather than claiming that fusion is universally beneficial.

One possible explanation is a mismatch between the pretrained model's original softmax attention and the inserted low-rank approximation. The low-rank branch does not provide an unbiased estimate of softmax attention, and 300 steps of LoRA adaptation may be insufficient to accommodate the resulting change in attention outputs. This explanation remains a hypothesis, not an experimentally established cause.

The results motivate further study of low-rank kernel selection, gate initialization, and longer adaptation for pretrained causal models. We have added these limitations and directions to App. F.5 and Sec. 8.

We again thank the reviewer for identifying these gaps. The revision clarifies that MASaLA supports standard mixed-precision training, provides configuration guidance based on measured task-dependent behavior, and extends evaluation to pretrained causal language modeling with explicit negative as well as positive results.

Together, these changes clarify where MASaLA is useful, where simpler alternatives remain preferable, and which extensions require further investigation. We believe they substantially address W1–W3 and strengthen the technical assessment of the paper. We would be grateful if the reviewer would reconsider their evaluation in light of the new evidence, and we welcome any remaining questions.

Reviewer_Er2bOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MASaLA, a hybrid attention mechanism that combines exact block-sparse attention with a low-rank RACE attention branch. The method introduces a mass-aware fusion coefficient to balance the contributions of the two branches based on their estimated attention denominators. The authors also establish a full-rank capacity result for the ungated hybrid operator and present experiments on long-context text classification, image classification, and synthetic retrieval tasks. The reported results suggest improvements over several efficient attention baselines, particularly in long-context settings.

Critical strengths
  1. Combining sparse attention for precise token-level interactions with low-rank attention for global context is a reasonable and well-motivated direction.
  2. The paper provides detailed implementation discussions, theoretical analysis, and ablation studies. The comparison against BS+RACE helps isolate the empirical contribution of the proposed fusion coefficient.
Critical weaknesses
  1. The complexity analysis overlooks the cost of block selection.

Equation (10) claims linear complexity, but Appendix B.2 states that the block scorer requires Theta(N² d_h / B) computation, plus top-k selection. With a fixed block size, the overall complexity remains quadratic. Excluding this cost makes the main efficiency claim misleading.

  1. The mass-aware fusion lacks theoretical justification.

The sparse branch uses exponential softmax scores, while RACE uses an approximate angular similarity kernel. Their denominators are therefore not directly comparable. It is unclear why their ratio should reflect the actual attention mass rather than simply act as a heuristic scaling factor.

  1. The full-rank result offers limited novelty.

As acknowledged in Section 4, Block-Sparse attention already has full-rank capacity because each query attends to its own block. The proposed fusion does not add this property. Moreover, the proof only covers the ungated variant, not the gated version used in the main experiments.

Questions for authors
  1. How do the authors reconcile the claimed linear complexity in Equation (10) with the quadratic block-scoring cost acknowledged in Appendix B.2? Can the authors provide a complete end-to-end complexity analysis, including block selection and top-k operations, together with their measured runtime contributions?

  2. Given that the sparse and RACE denominators are computed using different kernels, what theoretical or empirical evidence supports treating their ratio as a meaningful estimate of relative attention mass? How sensitive is the method to changes in query/key norms or attention temperature?

  3. Since Block-Sparse attention already has full-rank capacity, what additional theoretical property does MASaLA establish beyond preserving this existing property? Can the full-rank guarantee be extended to the gated operator used in the main experiments?

  4. Can the authors provide long-document classification experiments without same-class document packing, results across multiple random seeds, and a comparison against the original Scatterbrain implementation?

2 comments
AuthorsOpenReview ↗

Response to Reviewer Er2b (1/2)

We thank Reviewer Er2b for calling the direction "reasonable and well-motivated" and for noting the "detailed implementation discussions, theoretical analysis, and ablation studies". Each of the reviewer's four questions led to a change in the paper (in blue).

Status. Q1: complete complexity stated and runtime measured end to end. Q2: the ratio is tested against the exact mass and the sensitivity study is added; the reviewer's "heuristic scaling factor" reading is correct and the text now says so. Q3: the full-rank guarantee is extended to the gated operator. Q4: a no-packing control, three seeds on a new benchmark, and a comparison with Scatterbrain's fusion rule under its own low-rank kernel.


W1 and Q1: Reconcile Eq. (10) with the quadratic block-scoring cost; complete complexity and measured runtime contributions.

Response to W1 and Q1 (Sec. 3.2, Sec. 6 with new Eq. 11, App. B.2, App. E, Fig. 2, new App. F.1):

1. Complete cost. Eq. (10) is the cost given the selected blocks. Including selection: Θ(N(s+Ls2γ)+(N/B)2dh)\Theta\big(N(s+L_s2^{\gamma}) + (N/B)^2 d_h\big), quadratic in NN for fixed BB. We removed "linear" and "subquadratic" where they referred to the complete method.

2. Scorer. App. B.2 described a raw-key scorer (Θ(N2dh/B)\Theta(N^2d_h/B)); all experiments used a mean-pooled scorer (block means of queries and keys, top-kk plus own and first block), costing Θ(Ndh+(N/B)2dh)\Theta(Nd_h + (N/B)^2d_h). The description was wrong and is corrected.

3. Measured (selection included; forward speedup over FlashAttention; share of forward spent on scoring and top-kk):

NNpooled (used)raw-keyno scorer
32K3.6× (7%)2.8× (27%)3.8× (<2%)
64K6.9× (6%)4.7× (36%)7.3× (<2%)
128K13.3× (6%)7.2× (49%)14.2× (<2%)

So the reported speedups include selection, and the quadratic term costs 6–7% of the forward in this range. At 128K (15.9 ms): scorer 0.45, top-kk 0.44, sparse kernel 1.22, RACE kernel 0.43 ms; the rest is projections, RACE signatures and gates. Backward is unaffected by selection (10.9–11.5×). The no-scorer variant is a timing reference; it was not trained.


W2 and Q2: Why is the denominator ratio a meaningful estimate of attention mass? How sensitive is the method to query/key norms and temperature?

Response to W2 and Q2 (new App. F.2, F.3):

1. The ratio is not a mass estimate. We agree with the reviewer: it is a heuristic scaling factor. The submission described mm as an estimate of relative attention mass; that overclaimed, and we removed it. Against the exact support mass on trained Imagenette models, mean mm is 0.97 / 0.74 (layers 0 / 1) while the true mass is 0.05, with Spearman 0.01 / 0.06. A gate-only model (m≡1m\equiv1, one seed) reaches 74.3% vs. 74.4 ± 0.3% for MASaLA, so mm does not contribute to accuracy and we no longer claim that it does; the gain comes from the gated combination of the two branches (details: Response to Reviewer 6dbu, Q2).

2. Sensitivity. Trained Imagenette models perturbed at inference (3,925 images, same images for all settings, one checkpoint per model; the first row is the unperturbed accuracy of these checkpoints). "QK-norm" is MASaLA trained with L2-normalised q,kq,k (logits τcos⁡(q,k)\tau\cos(q,k)):

perturbationMASaLAgate-onlyQK-norm
none73.574.277.4
logit scale ×0.5 / ×2 / ×472.9 / 73.3 / 73.072.7 / 73.7 / 73.472.0 / 67.9 / 57.3
key-norm noise, log-normal σ = 0.3 / 0.6 / 1.071.6 / 69.6 / 66.867.5 / 58.6 / 50.677.4 (all)
1% of tokens with key norm ×3 / ×1070.3 / 68.961.3 / 54.977.4 (all)
  • Temperature: MASaLA is within 0.6 points over a factor-8 change (×0.5 to ×4).
  • Norms: heterogeneous key norms hurt through the exponential scores of the exact sparse branch, as in any softmax attention; perturbing only the RACE branch changes nothing.
  • Role of mm: in every setting above MASaLA degrades less than the gate-only model (σ = 1: −6.7 vs. −23.7 points). With one seed per model we do not attribute this to mm (App. F.3); it is an observation that more seeds would have to confirm.
  • QK-norm removes the norm sensitivity by construction and reaches 77.4% in this run, against 78.12% for full attention (App. F.6), at the price of more sensitivity to a global temperature change. We report it as an optional variant.
AuthorsOpenReview ↗

Response to Reviewer Er2b (2/2)

W3 and Q3: What does MASaLA add beyond the full rank of Block-Sparse? Can the guarantee be extended to the gated operator?

Response to W3 and Q3: Yes, the guarantee now covers the gated operator (new Proposition 1 in Sec. 4, proof in App. C). The gated matrix is Aθ=diag(gS⊙m)PS+diag(gR)PRA_\theta=\mathrm{diag}(g_S\odot m)P_S+\mathrm{diag}(g_R)P_R. For a fixed input and a fixed support pattern, det⁡Aθ\det A_\theta is real-analytic in the parameters θ\theta. Setting the last gate layer's weights to zero and its two biases equal gives gS=gR=cg_S=g_R=c for every token, so AθA_\theta becomes cc times the ungated operator; given a parameter value at which the ungated operator is non-singular, which is what Lemma 1 establishes with probability 1, det⁡Aθ≢0\det A_\theta\not\equiv0. A non-zero real-analytic function vanishes only on a set of Lebesgue measure zero, and there are finitely many support patterns, so the gated operator is full rank for almost every θ\theta. The result concerns exact rank, not conditioning.

What Lemma 1 adds. The reviewer is right that Block-Sparse with a forced own block is already full rank, and Sec. 4 says so. What is not automatic is that the property survives the fusion: adding a low-rank matrix to a full-rank one can make it singular, and here the sparse term is also rescaled row by row by mm and the gates. Lemma 1 and Proposition 1 show that neither step costs rank, so the hybrid gains global coverage and keeps the expressivity that a low-rank branch alone (rank at most Ls2γL_s2^{\gamma}) cannot have. We present it as a guarantee, not as a new source of rank.


Q4: Same-class packing in long-document classification; multiple seeds; comparison with the original Scatterbrain.

Response to Q4: 1. Without packing (new App. F.4). One 4,096-token document in each 32,768-token input, same budget as the packed runs. Validation accuracy, one seed each: MASaLA 41.0%, Scatterbrain 40.2%. MASaLA is nominally ahead, as App. F.4 notes, but a 0.8-point gap at one seed is not a difference we rely on. Both are far below the packed runs (above 90%), so the packed ArXiv numbers largely reflect the aggregation of same-class evidence; Sec. 7 carries this caveat together with the control, and we rest the accuracy claim mainly on Imagenette.

2. Seeds and an additional benchmark. Imagenette (10 classes, 16K tokens; train / test accuracy, new App. F.6):

FullMASaLAScatterbrain (RACE)Block-SparseRACE
train80.6375.90 ± 0.0472.4171.2368.93
test78.1274.42 ± 0.2773.8671.8571.92

MASaLA over 3 seeds (74.73, 74.22, 74.32) has the highest test accuracy among the efficient methods; every seed is above every efficient baseline. Its gap to Block-Sparse and RACE (2.5 points) is nine times its seed spread. Its gap to Scatterbrain is 0.56 points, about two standard deviations, with one Scatterbrain seed, so we do not claim significance for that gap alone. Tables 1–4 remain single-seed.

3. Scatterbrain's fusion rule, with its own low-rank kernel. We did not run the original implementation, whose sparse branch is LSH; we isolate what differs: the fusion rule. In the form of Eq. (9), O=m′ OS+(1−m′) ORsubO=m'\,O_S+(1-m')\,O_R^{\mathrm{sub}} with m′=dS/(dS+dRsub)m'=d_S/(d_S+d_R^{\mathrm{sub}}), we ran Scatterbrain's rule and ours on the same block-sparse support with both low-rank kernels (test accuracy, single runs): RACE, 74.73 vs. 73.86; Performer, the kernel of the original Scatterbrain, 73.12 vs. 70.62 (fp32 reference implementation). MASaLA's fusion leads in both, by 2.5 points over Scatterbrain's own kernel.


We thank the reviewer again. The complexity is complete and measured, the fusion coefficient is described as the heuristic the reviewer assumed, the rank guarantee covers the implemented model, and the new benchmark includes seeds. We would be grateful if the reviewer would reconsider the score.

Reviewer_6dbuOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MASaLA, a hybrid attention mechanism that combines block-sparse attention with a low-rank RACE-based attention branch. The sparse branch computes exact attention over selected key blocks, while the low-rank branch is intended to capture global interactions through compressed feature representations.

The main idea is a mass-aware fusion mechanism that adjusts the contribution of the sparse branch based on the relative denominator estimates from the two branches. The authors also require each query to attend to its own block and provide a theoretical analysis showing that the ungated hybrid attention operator is generically full rank under certain assumptions.

The method is evaluated on long-context text classification, vision classification, short-sequence tasks, and synthetic long-range retrieval benchmarks. The results are encouraging, particularly for long-context classification and Needle-in-a-Haystack (NIAH) retrieval. The paper also presents a fused Triton implementation and reports attention-operator-level speedups over exact FlashAttention at long sequence lengths.

Critical strengths

Strength 1: A reasonable approach to combining complementary attention mechanisms.

The paper addresses a relevant limitation of efficient attention methods. Sparse attention can preserve strong local or selected token-level interactions, but it may miss information distributed across many positions. Low-rank attention can represent broader interactions more efficiently, although it may struggle with sharp dependencies that require precise token selection.

Combining the two approaches is a sensible design choice. I also find the mass-aware fusion mechanism interesting as an attempt to adjust their relative contributions based on the attention computations themselves.

The experiments comparing MASaLA with simpler sparse-plus-low-rank combinations provide useful evidence that the fusion strategy can improve retrieval performance. This makes the architectural direction worth exploring further.

Strength 2: Encouraging long-context results and detailed implementation analysis.

The paper includes experiments across several tasks and attention configurations. The long-range retrieval results are particularly encouraging. MASaLA achieves an average NIAH accuracy of 97.9%, compared with 62.5% for the BS+RACE ablation. This is a substantial improvement and suggests that the proposed fusion mechanism can help preserve information needed for precise retrieval.

The results on long-context vision classification are also promising, with improvements over several efficient-attention baselines.

I appreciate the implementation details provided in the paper. The discussion of fused Triton kernels, backward recomputation, numerical precision, and GPU memory usage makes the engineering contribution more concrete. The operator-level benchmarks are useful for understanding the potential efficiency of the attention computation once the sparse support has been determined.

Critical weaknesses

Weakness 1: The claimed linear-complexity advantage does not account for the default block-selection procedure.

My main concern is the computational complexity of the complete MASaLA algorithm.

The paper states that the attention computation has complexity O(N(s+SR))O(N(s+S_R)), but this expression explicitly excludes the cost of block scoring. As acknowledged in Appendix B.2, the default scorer operates in the raw key space and requires

Θ(N2dh/B)\Theta(N^2d_h/B)

computation, in addition to the overhead of selecting the key blocks.

For a fixed block size (B), this term is still quadratic in sequence length. It therefore becomes the dominant asymptotic cost compared with the linear-complexity attention branches.

As a result, the complete default method does not appear to achieve the linear-time complexity emphasized in the efficiency discussion. I think this distinction is important because computational efficiency is one of the main motivations for developing the hybrid attention mechanism.

I also have questions about the reported runtime improvements. The paper describes the GPU speedups as attention-operator-level measurements, while block selection is performed before the fused attention kernel. It is unclear whether the quoted speedups include the time required for scoring candidate blocks and performing top-k selection.

If those operations are excluded, the reported results may overestimate the end-to-end speedup of the complete method.

I would like to see runtime measurements that include the entire attention pipeline, with a breakdown of the cost of block scoring, selection, sparse attention, low-rank aggregation, and fusion.

Alternatively, demonstrating that a more efficient block-selection method can retain the reported accuracy would help address this concern.

Weakness 2: The relationship between the mass-aware fusion weights and actual attention mass is not sufficiently justified.

My second concern is the interpretation of the proposed mass-aware correction.

The fusion mechanism uses a factor of the form

mS=dSdS+λdR+ε,m_S=\frac{d_S}{d_S+\lambda d_R+\varepsilon},

where (d_S) is calculated from exponentiated dot-product scores over the selected sparse support, while (d_R) comes from the RACE branch, which uses a different bounded similarity kernel.

Because these denominators are computed using different attention kernels, their magnitudes are not necessarily directly comparable. In particular, I do not see why their ratio should reliably estimate the proportion of the original softmax attention mass captured by the sparse branch.

For example, increasing the scale of the query-key dot products can cause the sparse denominator (d_S) to grow exponentially. The normalized RACE similarities, however, remain bounded. In this setting, the fusion factor could approach one even if a substantial fraction of the actual softmax attention mass lies outside the selected sparse support.

This suggests that the proposed weighting rule may be sensitive to the relative scales of the two kernels rather than accurately reflecting the attention mass represented by each branch.

The learned coefficient and additional gates may compensate for this mismatch during training, and the empirical results suggest that the resulting mechanism can be effective. However, I think the paper needs stronger evidence to support the specific interpretation of the weighting rule as a mass-aware correction.

A useful experiment would be to compare the learned fusion factors with the actual fraction of softmax attention mass covered by the selected sparse blocks, using sequence lengths where exact attention can be computed.

I would also like to see a comparison against a similarly parameterized learned fusion gate that does not use the denominator ratio. This would help determine whether the proposed mass-aware formulation provides a meaningful advantage over simpler adaptive weighting.

Questions for authors

Q1. End-to-end computational complexity and runtime

Could the authors provide the complete computational complexity of MASaLA, including block scoring and top-k selection?

Since the default raw-key-space scorer has a quadratic cost, I would like to understand how this affects the overall runtime as sequence length increases. It would be particularly helpful to report end-to-end latency measurements that include block selection, sparse attention, low-rank aggregation, and fusion.

What fraction of the total runtime is spent on block scoring and selection at different sequence lengths? Is there a practical configuration that achieves subquadratic end-to-end complexity while preserving the reported accuracy?

Q2. Interpretation and calibration of the mass-aware fusion mechanism

Could the authors explain why the ratio of the sparse and RACE denominators should provide a meaningful estimate of relative attention mass, given that the two branches use different similarity kernels?

I would be interested in an experiment comparing the fusion weights with the actual sparse-support mass fractions obtained from exact softmax attention on manageable sequence lengths.

A comparison against a gate-only fusion mechanism with a similar parameter budget would also be useful. This could help clarify whether the denominator-based correction contributes independently to the reported improvements.

Q3. Generalization of the experimental results and scope of the theoretical analysis

The ArXiv classification task concatenates documents belonging to the same class. This setup may make classification easier as sequence length increases, since longer inputs contain more information associated with the same label.

Could the authors provide a per-document control experiment or evaluate the method on another long-context task that does not rely on this packing strategy? This would help assess how well the reported improvements generalize to more natural long-context settings.

I also have a question about the theoretical result. The full-rank guarantee is established for the ungated hybrid operator, whereas the main experiments use gated fusion. Could the authors clarify which parts of the theoretical analysis still apply to the implemented model?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 6dbu (1/2)

We thank Reviewer 6dbu for describing MASaLA as "a reasonable approach to combining complementary attention mechanisms" and appreciating its "detailed implementation analysis". The revision directly addresses the reviewer's concerns by correcting complexity claims, adding end-to-end runtime measurements, providing the requested fusion controls, and presenting new theoretical and experimental results. All changes are marked in blue.


W1 and Q1: Complete complexity including block scoring and top-k; end-to-end runtime with a breakdown; a subquadratic configuration.

Response to W1 and Q1 (Sec. 3.2, Sec. 6 with new Eq. 11, App. B.2, App. E, Fig. 2, new App. F.1):

1. Complete complexity. The reviewer correctly identified that Eq. (10), Θ(N(s+Ls2γ))\Theta(N(s+L_s2^{\gamma})), accounts only for attention computation given the selected blocks. Including block selection, the complete complexity is

Θ(N(s+Ls2γ)+(N/B)2dh),\Theta\big(N(s+L_s2^{\gamma})+(N/B)^2d_h\big),

which is quadratic in NN for fixed block size BB. We corrected the complexity analysis and removed "linear" and "subquadratic" wherever these terms referred to the complete method.

2. Block scorer used in the experiments. The original description in Sec. 3.2 and App. B.2 specified a raw-key scorer with complexity Θ(N2dh/B)\Theta(N^2d_h/B). However, all experiments and timings used a mean-pooled scorer: queries and keys are averaged within each block, each query block scores all key blocks through dot products of their pooled representations (summed across heads), and selects the top-kk blocks together with its own and the first block.

The implemented scorer costs Θ(Ndh+(N/B)2dh)\Theta(Nd_h+(N/B)^2d_h). At B=64B=64, the quadratic term evaluates B2=4096B^2=4096 times fewer block pairs than token pairs. We corrected the method description to match the implementation.

3. End-to-end runtime. We now report forward speedups over FlashAttention with block scoring and top-kk selection included, alongside the originally described scorer and a selection-free control (batch 1, bf16, non-causal, 384 keys per query). Parentheses show the percentage of forward runtime spent on scoring and top-kk.

NNPooled scorer (used)Raw-key scorer (described)No scorer (neighbour blocks)
32K3.6× (7%)2.8× (27%)3.8× (<2%)
64K6.9× (6%)4.7× (36%)7.3× (<2%)
128K13.3× (6%)7.2× (49%)14.2× (<2%)

The reported end-to-end speedups remain substantial after including selection, which accounts for only 6–7% of forward runtime over the measured lengths. At 128K, the pooled forward takes 15.9 ms, including 0.45 ms for scoring, 0.44 ms for top-kk, 1.22 ms for the sparse kernel, and 0.43 ms for the RACE kernel; the remaining 13.4 ms comprises projections, RACE signatures, and gates.

Selection's measured share does not increase between 32K and 128K. Under an extrapolation assuming quadratic selection and linear scaling of all other costs beyond 128K, selection would reach 50% of forward runtime only near 2M tokens. This is an extrapolation, not a measured result.

Backward speedups are 10.9–11.5×, without selection overhead. Fig. 2 uses one shared projection set for both branches (Algorithm 1); separate projections achieve 11.8× forward and 10.0× backward speedups at 128K. Timing uses Ls=4L_s=4, γ=4\gamma=4, and gate width 64; the trained vision models use Ls=5L_s=5, γ=2\gamma=2, and gate width 128.

4. Subquadratic alternatives. We identify two configurations addressing the reviewer's request:

  • Neighbour-block selection: Eliminates content-based block scoring, giving linear end-to-end complexity and a measured 14.2× forward speedup at 128K.
  • Growing block size: Setting B=Θ(N)B=\Theta(\sqrt N) reduces the selection term to Θ(Ndh)\Theta(Nd_h) and gives overall Θ(N1.5)\Theta(N^{1.5}) complexity for fixed numbers of selected blocks and fixed feature dimensions.

Neither configuration has been trained, so we make no accuracy claims for them. All reported accuracy results use the mean-pooled scorer with B=64B=64. The growing-block analysis will be added to App. E and is not yet part of the revised PDF.


W2 and Q2: Why should the denominator ratio estimate relative attention mass? Compare with the exact sparse-support mass; compare with gate-only fusion.

Response to W2 and Q2 (Sec. 3.3, Sec. 7, new App. F.2):

1. Interpretation of mm. We agree with the reviewer's concern. The original manuscript described mm as rescaling the sparse branch "according to its estimated relative attention mass". This interpretation was not justified and has been removed.

The sparse denominator dSd_S uses an exponential kernel over the selected support, whereas dRd_R uses a bounded RACE kernel over all keys. Their ratio therefore does not estimate the exact sparse-support attention mass.

We now describe mm as a learned per-token scale correction between two separately normalized attention branches, rather than an estimator of attention mass.

AuthorsOpenReview ↗

Response to Reviewer 6dbu (2/2)

W2 and Q2 (continued): Exact support mass; gate-only fusion.

2. Comparison with exact attention mass. We evaluated trained Imagenette models (N=16,385N=16{,}385, 384 keys per query, 100 images, all heads). For each query, the exact support mass is

mi⋆=∑j∈Siesij∑jesij,m_i^\star=\frac{\sum_{j\in S_i}e^{s_{ij}}}{\sum_j e^{s_{ij}}},

using exact softmax with the same queries, keys, and selected support.

Model, layer 0 / 1Mean mmMean m⋆m^\starSpearman(m,m⋆m,m^\star)
MASaLA0.97 / 0.740.047 / 0.0480.01 / 0.06
MASaLA + QK-norm0.31 / 0.500.029 / 0.0290.42 / 0.26

As the reviewer suspected, mm substantially exceeds the true support mass and, without QK normalization, provides essentially no ranking information. Even before training, on Qwen2.5-0.5B at T=4096T=4096, true mass is 0.71, whereas the ratio gives 0.52 with RACE and 0.99 with Performer, showing its dependence on the low-rank kernel.

Accordingly, we no longer claim that mm estimates relative attention mass.

3. Gate-only control. We trained the same architecture and gates with m≡1m\equiv1, removing the denominator-ratio correction while retaining gated fusion.

Imagenette test accuracy at 16K tokens (MASaLA: three seeds, mean ± std; others: one seed):

FullMASaLAGate-onlyScatterbrainBlock-SparseRACE
78.1274.42 ± 0.2774.3473.8671.8571.92

Gate-only achieves similar accuracy to MASaLA; the scale correction therefore shows no accuracy advantage here. We removed the corresponding attribution to mm from Sec. 7.

Gated fusion itself remains effective: MASaLA exceeds either individual branch by approximately 2.5 points and outperforms Scatterbrain on matched sparse support with both kernels (RACE: 74.73 vs. 73.86; Performer: 73.12 vs. 70.62). This supports gated sparse-plus-low-rank fusion, rather than the original attention-mass interpretation.

4. Robustness under perturbations. Despite similar clean accuracy, MASaLA shows smaller degradation than gate-only in all nine jointly evaluated perturbation settings (App. F.3). Examples:

PerturbationMASaLAGate-only
Key-norm noise, σ=1\sigma=1−6.7 points−23.7 points
1% of keys with norm ×10−4.6 points−19.3 points
Logit scale ×0.25−2.5 points−10.2 points

These results suggest a possible robustness difference, but each model uses one seed, so they do not establish that mm causes it. Appendix F.3 explicitly states this limitation.


Q3: (a) A per-document control for ArXiv. (b) Which theory applies to the gated model?

Response to Q3:

(a) Single-document ArXiv control (new App. F.4).

We agree that packing same-class documents can inflate accuracy by aggregating independent class evidence. We originally used this construction because ArXiv contains few documents of 34K tokens or more.

We therefore trained a control with one 4,096-token document per 32,768-token input, using the packed experiments' training budget.

Validation accuracy, one seed each:

MethodSingle-document ArXiv
MASaLA41.0%
Scatterbrain40.2%

MASaLA's nominal 0.8-point lead is inconclusive with one seed. Both methods perform far below their packed-document results (above 90%), supporting the concern that the original benchmark primarily measures aggregation of same-class evidence rather than modeling a single long document.

Sec. 7 now states this limitation, and our main accuracy claim rests on Imagenette rather than packed ArXiv.

(b) Full-rank theory for the gated operator (Sec. 4, new Proposition 1, App. C).

Lemma 1 originally established full rank for the ungated hybrid operator. We extended the analysis to the implemented operator:

Pgated=diag⁡(gS⊙m)PS+diag⁡(gR)PR.P_{\mathrm{gated}}=\operatorname{diag}(g_S\odot m)P_S+\operatorname{diag}(g_R)P_R.

New Proposition 1 establishes that, for a fixed input, if the ungated operator is nonsingular at some parameter value for every admissible support pattern, as established almost surely by Lemma 1, then the gated operator is nonsingular outside a set of Lebesgue measure zero in parameter space.

The full-rank guarantee thus extends to the gated architecture. It concerns exact rank, not conditioning.


We thank the reviewer for these constructive questions. The revision retains the substantial efficiency gains with selection included, while separating the empirical value of fusion from the unsupported attention-mass interpretation.

We would be grateful if the reviewer would reconsider their evaluation in light of this evidence. We welcome any remaining questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank the reviewers for their careful and constructive reviews. Every experiment requested is now in the paper (new Appendix F; changes in blue). Several of them changed what we claim, and we state the contributions first as the revised paper supports them.

Contributions, as supported by the revised paper

  1. A fused kernel for sparse-plus-low-rank attention (the part Reviewer P4wx calls the main new technical content). Peak training memory is 1.08× FlashAttention up to 262K tokens. The forward is 3.6× / 6.9× / 13.3× faster at 32K / 64K / 128K with block selection included, and the backward 10.9–11.5×. Selection costs 6–7% of the forward.
  2. A gated fusion of an exact block-sparse branch and a low-rank branch. On Imagenette at 16K tokens, MASaLA reaches 74.42 ± 0.27% over three seeds, 2.5 points above either branch alone, and its fusion rule is ahead of Scatterbrain's on the same support with both low-rank kernels (RACE 74.73 vs. 73.86; Performer 73.12 vs. 70.62). Baselines have one seed; the 0.56-point gap to Scatterbrain's main run is about two standard deviations.
  3. A rank guarantee that reaches the implemented model: full rank for the ungated operator (Lemma 1) and now for the gated one for almost every parameter value (Proposition 1).

What the revision corrects

  • The complete method is quadratic in the number of blocks, not linear (all four reviewers).
  • mm is a learned scale correction, not a mass estimate, and a gate-only model matches MASaLA in accuracy (6dbu, Er2b). In our perturbation tests, the model with mm degraded less; with one seed per model, we do not attribute this to mm.
  • The packed ArXiv results carry a same-class packing caveat; in a single-document control, MASaLA and Scatterbrain are 0.8 points apart at one seed (6dbu, Er2b, P4wx).
  • In a pretrained causal language model, MASaLA is on par with Scatterbrain but behind Block-Sparse alone (xBJJ, P4wx).
  • Rows of Tables 1, 3 and 4 come from the configuration reported in ELSAA (arXiv:2607.20214), with its sortLSH branch; ELSAA is now cited. The row-by-row provenance is in our reply to Reviewer P4wx, and the revised captions name the sparse branch in every table (P4wx).
  • bf16 is a default, not a requirement (xBJJ).
Requested byWhat was addedMain result
allComplete complexity; end-to-end runtime with a breakdown (F.1)Θ(N(s+Ls2γ)+(N/B)2dh)\Theta(N(s+L_s2^{\gamma})+(N/B)^2d_h). Forward speedup at 32K / 64K / 128K: 3.6× / 6.9× / 13.3× with scoring, 3.8× / 7.3× / 14.2× without
6dbu, Er2bmm vs. the exact support mass; gate-only control (F.2)Spearman 0.01 / 0.06. Gate-only 74.34% (one seed) vs. MASaLA 74.42 ± 0.27%
Er2b, xBJJSensitivity to temperature, q/k norms and λ\lambda; QK-norm variant (F.3)Within 0.6 points for temperature ×0.5 to ×4, 0.25 for λ\lambda ×0.1 to ×10. QK-norm variant: 77.4% (one run; full attention 78.12%)
6dbu, Er2b, P4wxSingle-document ArXiv control (F.4)MASaLA 41.0% vs. Scatterbrain 40.2% (one seed each); far below the packed runs
xBJJ, P4wxCausal language modeling, Qwen2.5-0.5B, LoRA (F.5)Perplexity at 4K / 16K: Block-Sparse 11.94 / 11.74, MASaLA 12.12 / 12.09, Scatterbrain 12.34 / 12.04, ungated sum 13.85 / 13.16
Er2b, P4wx, xBJJImagenette, 16K tokens, 3 seeds; fusion × kernel grid (F.6)Full 78.12, MASaLA 74.42 ± 0.27, Scatterbrain 73.86, RACE 71.92, Block-Sparse 71.85
6dbu, Er2bGated operator (Proposition 1, Sec. 4, App. C)Full rank for almost every parameter value

Protocol: Imagenette at 16,385 tokens, 60 epochs; MASaLA 3 seeds (mean ± std), other methods one seed. Timings: batch 1, bf16, non-causal, 384 keys per query, Ls=4L_s=4, γ=4\gamma=4, gate width 64.

Text edits: Sec. 3.2, Sec. 6 (Eq. 11), App. B.2, App. E (scorer actually used; complete complexity); abstract, Sec. 1, 3.3, 7, 8 (mm as a learned scale correction); Sec. 2 and 3.2 (ELSAA cited; rows produced with its sparse branch); Sec. 5 and 7 (packing and the control); App. B.5 (bf16); Fig. 2, App. B.7 (selection included); Table 7.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.