acceptodds
Withdrawn from ICLR 2027

Sparse Attention Is Matrix Approximation, Not Choosing from a Bag of Values

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Large Language Models (LLMs) achieve strong performance across many domains, but their efficiency is limited by the quadratic cost of attention with respect to prompt length. Sparse attention reduces this cost by retaining only a small fraction of query-key interactions to approximate the full attention matrix. However, existing methods are trapped in a mathematically wrong view: they simply keep large scalar entries or high-mass regions of the attention matrix. This treats the attention matrix as a bag of values, ignoring that it is used as a structured matrix whose entries jointly determine the attention output through multiplication with value vectors. We argue that this is the core conceptual issue: **sparse attention should be formulated as matrix approximation, not as blindly choosing the largest values from a bag of entries.** Based on this view, we propose **M**atrix **A**pproximation **S**parse **A**ttention (**MASA**). MASA replaces raw attention-mass ranking with a closed-form score that measures how much each sparse unit reduces matrix-product approximation error. As a theory-grounded plug-in correction, MASA can be added to existing sparse attention frameworks without changing their sparse kernels or budgets. Extensive experiments across multiple sparse attention methods, benchmarks, and LLM backbones show consistent accuracy gains, supporting both MASA and the matrix-approximation view of sparse attention.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Transformer, attention, attention sparsity, LLM prefilling, LLM efficiency

Reviews

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

The paper proposes Matrix Approximation Sparse Attention (MASA), a scoring replacement for selecting structured sparse-attention units during prefill. Instead of ranking candidates by attention mass, MASA scores each candidate by its individual reduction in a squared matrix-product approximation error, using value-derived probes at the baseline's profiling resolution. It preserves the existing candidate families, sparse kernels, and budget rules. Experiments integrate MASA into MInference, SeerAttention, and FlexPrefill, reporting limited improvements across eight matched benchmark averages on Llama and Qwen family models, some additional latency, and lower executed attention-output error in four diagnostic comparisons.

Critical strengths
  1. MASA changes a selection score while reusing established sparse kernels and candidate structures. Integration into three different frameworks is meaningful evidence that the idea is implementable and not tied to one custom sparse pattern.
Critical weaknesses
  1. The eight reported average improvements range from approximately 0.17 to 1.41 points, without corresponding downstream confidence intervals or multi-seed results. More importantly, Appendix F states that the main results use the best tested probe configuration on each benchmark. This introduces selection bias into the reported gains. Appendix E provides useful uncertainty estimates for output error, but explicitly describes selected-setting comparisons rather than an independent held-out evaluation. Standardized evaluation with frozen configurations and five fixed seeds for RULER data construction would help establish that the gains persist across synthetic inputs and are not dependent on evaluation implementation or benchmark-specific configuration selection.

  2. Real attention can be highly concentrated, with many negligible entries; whether low-mass candidates have consequential value contributions under the actual execution precision is therefore an empirical question. The paper does not quantify this for the candidates whose selection changes. Moreover, the score models unnormalized retained contributions, whereas actual sparse kernels renormalize, and the implementation uses profiled and sometimes norm-controlled probes. Appendix E establishes an aggregate output-error improvement, but does not distinguish improved value-aware selection from increased retained attention mass, norm control, or numerical effects.

Questions for authors
  1. Could you evaluate Original and MASA through lm-eval-harness using five predeclared seeds that control RULER synthetic-data construction, with the same generated instances for both methods at each seed? Please freeze probe parameters using separate calibration data, preserve the intended long-context task settings, and release the harness task/backend configuration, data-generation seeds, and per-example scores. Report each seed's paired improvement, the mean and standard deviation. Greedy decoding does not remove the variability in synthetic-data construction. This would address both reproducibility of the evaluation pipeline and stability of the small gains.

  2. What are the dtypes and normalization/casting steps used for profiling, score computation, softmax intermediates, and the value multiplication? For blocks retained by MASA but omitted by the baseline, can you quantify their attention mass and effective value contribution under the actual kernel's numerical path, including how often relevant multiplication operands become zero? The important question is whether the proposed correction acts on meaningful contributions in trained models, rather than only on possibilities demonstrated by a constructed example.

  3. Could you provide a controlled, block-by-block experiment tracing where contributions are lost along the actual FlashAttention online loop, comparing Original and MASA with identical Q, K, V, candidate units, actual retention budget, and kernel settings? For each block, record its selection status, QK-derived attention mass, running row maximum and row sum, P before and after low-precision conversion, PV contribution, and the resulting change in the output accumulator. Report both the fraction of nonzero P entries rounded to zero and the weight they carry. Track subsequent accumulator rescaling and final normalization so that block contributions are compared on the final-output scale, and relate these losses to the complete output error against dense attention.

    Please use a common dense execution trace to characterize skipped blocks, together with each method's actual sparse execution trace to capture changes in online normalization. Focus on blocks retained only by Original or only by MASA: do MASA's replacement blocks preserve meaningful PV contributions after casting and accumulation, given the measured value-norm and variance distributions in the trained model? A small, budget-matched block-swap experiment on representative query tiles would help connect these selection differences to changes in final output error. This would distinguish the claimed value-aware preservation from alternatives such as retaining more effective attention mass or changing the normalization denominator, rather than relying solely on aggregate output-error improvements.

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

This paper observes that existing sparse attention methods typically select sparse units based on attention weight magnitudes or regional quality. However, Transformers actually consume the product of the attention matrix and the value matrix, AVAV; hence, larger attention weights do not necessarily make more important contributions to the final output. Based on this insight, the authors propose Matrix Approximation Sparse Attention (MASA), which formulates sparse selection as a matrix-product approximation problem. MASA retains the sparse units, budget, and execution kernels of the original methods and only replaces the ranking rule. The authors apply MASA to MInference, SeerAttention, and FlexPrefill and report consistent performance gains on RULER, InfiniteBench, and LongBench with Llama and Qwen models, while claiming negligible additional latency. The paper also measures the error between the outputs of practical sparse attention and full attention, showing that MASA reduces this error across four framework-model combinations.

Critical strengths
  1. The problem perspective is sound, and the method aligns better with the actual computational semantics of attention. The paper clearly distinguishes between “approximating large entries in the attention matrix” and “approximating the action of the attention matrix on values”. The scoring in MASA jointly accounts for attention weights, the direction and norm of the value/probe, and the alignment between candidate units and the full output AX. This perspective is more principled than relying solely on attention mass and provides a unified scoring framework for sparse units of different structures.

  2. The method exhibits good plug-and-play capability with reasonably comprehensive experimental coverage. MASA leaves candidate patterns, sparse budgets and underlying kernels unchanged, making it compatible with multiple existing systems. The authors conduct matched comparisons across three representative sparse attention frameworks, several long-context benchmarks and two model families, and supplement measurements of the actual attention-output error. These experiments at least suggest that the method is not effective only for a single implementation or a single task.

Critical weaknesses
  1. Ranking individual units does not truly optimize the global matrix-approximation objective proposed in the paper. For multiple candidate units, the true error reduction contains cross terms across units:

    Δ(S)=∑u∈Ss(u)−2∑u,v∈S<˘v⟨Cu,Cv⟩F.\Delta(S)=\sum_{u\in S}s(u)-2\sum_{\substack{u,v\in S\u<v}}\langle C_u,C_v\rangle_F.

    MASA selects the top-BB units based on each unit's standalone score relative to the empty set and ignores interactions between distinct units. While cross terms are preserved within a single block, interactions across different blocks, vertical lines, or slash lines are not handled. MASA is therefore more accurately characterized as a matrix-approximation heuristic or one-shot greedy proxy rather than a closed-form solution to Eq. (2)/(6). Phrases such as "correct selection objective" are significantly stronger than the theoretical results justify.

  2. There is an important mismatch between the theoretical objective and the sparsified softmax used in practice. The derivation assumes (MS⊙A)V(M_S\odot A)V, i.e., masking applied directly to the fully softmax-normalized attention matrix. Practical sparse kernels, however, typically renormalize over the retained positions and produce softmax⁡(masked logits)V\operatorname{softmax}(\text{masked logits})V. When the candidate set changes, the weights of all retained positions shift due to the renormalization factor. Consequently, the closed-form score in the paper is not an exact marginal reduction in output error for the actual sparse kernel. The empirical output-error results in the appendix are informative but do not close this theoretical gap.

  3. The main results rely on post-hoc hyperparameter tuning on the evaluation set. The appendix explicitly states that the main result for each framework/backbone/benchmark uses the probe configuration achieving the highest aggregate score on that benchmark. This means that the clipping percentile and norm-balancing parameters are chosen using final evaluation performance. Given that many reported average gains are only 0.1-0.5 points, this procedure may substantially inflate the reported improvements. For instance, raw MASA only improves LongBench from 54.20 to 54.24, whereas the test-set-tuned version reaches 54.37. Under top-conference standards, hyperparameters should be selected using a held-out validation set, chosen across datasets, or fixed uniformly in advance.

  4. Key baselines and scoring ablations that isolate the technical contributions are missing. Current comparisons are mostly between the original attention-mass ranking and full MASA, making it impossible to determine whether the gains stem from the matrix-product alignment term or merely from incorporating value norms or other value-side information. The paper should at minimum compare Aij∥Vj∥2A_{ij}\lVert V_j\rVert_2, Aij2∥Vj∥22A_{ij}^2\lVert V_j\rVert_2^2, an alignment-only variant, a variant without the quadratic penalty, and a practical leave-one-unit-out output-error oracle. Existing norm-control ablations only study probe construction and do not validate the necessity of each component in the full MASA scoring function.

  5. Evidence for statistical reliability and practical efficiency remains insufficient. Many downstream gains are small, with mixed task-level outcomes, yet confidence intervals or paired significance tests are not provided for the main benchmark results. For efficiency, only normalized kernel-level latency plots are shown; absolute latency, end-to-end prefill time, overhead from profiling, masking, and probe computation, peak memory usage, and results across different batch sizes are absent. Since MASA requires the additional computation of AXAX and (AX)X⊤(AX)X^\top, the available evidence does not support the general claim of "negligible overhead."

Questions for authors
  1. Could the authors provide theoretical conditions, error bounds, or approximation guarantees for neglecting cross-unit interaction terms? Have the authors compared an iterative greedy variant that recomputes marginal gains based on the current residual? If so, what are its accuracy and overhead?

  2. Can the derivation of MASA be extended to account for practical sparse-softmax renormalization? If not, would the authors explicitly frame the current objective as a surrogate and quantify the correlation between this surrogate score and the true reduction in output error?

  3. Why are the probe hyperparameters in the main table selected directly using the aggregate score on the corresponding benchmark? If a held-out validation set or a single unified configuration across all models and datasets is adopted, does MASA still outperform the baseline on all eight aggregate metrics?

  4. What are the gains of full MASA relative to simple value-aware baselines such as Aij∣Vj∣A_{ij}|V_j|, Aij2∣Vj∣2A_{ij}^2|V_j|^2, or the alignment-only variant? This is critical to verify that improvements arise from the matrix-approximation scoring rather than merely incorporating value-side information.

  5. Could the authors report end-to-end prefill latency, absolute runtime, and peak memory usage including profiling, scoring, mask construction, and the sparse kernel? Please provide results across different sequence lengths, batch sizes, sparsity ratios, and profiling resolutions.

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

The paper scores structured sparse-attention units using matrix-output approximation error while retaining existing frameworks, budgets, and kernels. It aims to make online ranking more closely reflect attention outputs rather than relying only on attention-weight coverage.

Critical strengths
  1. The derivation is clear and the integration practical, supporting multiple established sparse-attention frameworks without reconstructing the entire computation pipeline. The contribution is online scoring of structured sparse units, not the first use of value information; MInference's offline pattern search already incorporates relevant output information.

  2. Average results improve across different backbones and benchmarks. Real-kernel error experiments and paired bootstrap analyses support the score's effectiveness under the selected settings and deserve credit.

Critical weaknesses
  1. Test-set configuration selection weakens the independent evidence. Main results choose the probe configuration with the highest aggregate score on each test benchmark, which may introduce optimistic selection bias. The results do not adequately distinguish stable method gains from gains due to test-set selection. Existing interval analyses do not replace independent calibration followed by frozen-configuration testing.

  2. The connection between the theoretical score and actual kernels needs further validation. The masked matrix-product proxy is not renormalized, whereas actual sparse softmax is renormalized after masking. Ranking units independently also does not fully account for cross-unit interactions. This does not imply an algebraic error; it means the score is a reasonable surrogate rather than an exact optimization of actual output error.

The method offers a practical increment, and no algebraic error was identified. The main concern is that the evaluation does not yet provide sufficiently independent evidence for stable, general gains. The existence of prior value-aware methods does not itself imply that this paper lacks a contribution.

Questions for authors

Can you select the probe using independent calibration data and verify the gains after freezing the configuration? How do renormalization and cross-unit interactions affect ranking? Evaluation across sequence lengths and sparsity budgets would also help establish generality.

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

Related papers

Discussion (0)

Sign in to comment.