- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes SMat-Attention, a structured state-expansion mechanism for linear/kernel attention. The method maintains a sublinear number of summary states, with the number of states scaling as roughly , and uses finite-field point–hyperplane incidence structure to route queries to structured long-range summaries. The paper presents theoretical results for hard-routing SMat, including subquadratic prefill and constant-time fixed-horizon decoding, and evaluates the method on synthetic routing/retrieval tasks, MQAR/JCKR recall tasks, and small-scale PG-19 language modeling.
The core idea is interesting, and the VC-dimension framing gives a clean way to reason about structured access patterns. However, I do not think the experimental evidence supports the practical claims made in the paper. In particular, the efficiency evaluation is not aligned with the main learned variant, the softmax baselines are not representative of modern efficient attention systems, and the language-modeling experiments are far too small-scale to justify claims about long-context sequence modeling.
Critical strengths
- The paper proposes an interesting perspective: treating SMat as a structured expansion of linear-attention states.
- The hard-routing construction is mathematically elegant, and the factorization gives a clear algorithmic route to avoiding explicit sparse edge enumeration.
- The synthetic routing experiments are well aligned with the VC-dimension story and show that increasing $d $ increases subset-routing expressivity.
- The paper includes more implementation and timing details than many theoretical long-context papers.
Critical weaknesses
1. Efficiency evaluation is not convincing for modern LLM settings
The paper compares against PyTorch SDPA in fp32, which the appendix states uses the memory-efficient backend. This is not a naive attention implementation, but it is also not a convincing comparison against modern production-grade BF16/FP16 FlashAttention-2/3 attention stacks. The paper does not report whether the softmax baseline uses FA2, what backend is actually selected, or whether the comparison is against the best available modern attention implementation.
More importantly, the decoding benchmark does not report SM occupancy, achieved bandwidth, Tensor Core utilization, or batch-size sweeps. It is therefore unclear whether the reported decode numbers correspond to a saturated GPU regime or are dominated by small-kernel / launch overhead. The reported timing appears to be on small subset-routing-style models, not production-scale end-to-end LLM inference.
This makes it hard to interpret claims such as “constant-time decoding” or “faster than softmax” in a practical serving context.
2. Timing is for hard-routing SMat, not for the learned dynamic-routing variant used in main empirical results
The paper’s most favorable efficiency results appear to be measured on hard-routing / fixed-mask SMat. However, MQAR, JCKR, and PG-19 use the learned four-read routing variant.
This distinction is crucial. In hard routing, each token reads one distant state plus the local recurrent state, so selection is . In the learned four-read variant, each query must score candidate type states and select top-4. This introduces $ \Theta(T^{2-1/d}) $ prefill scoring cost and $ O(T^{1-1/d}) $ per-token routing cost during decoding, before even reading the selected states.
Thus the speed/memory numbers do not demonstrate that the learned variant achieving the reported task performance retains the advertised efficiency. The paper uses hard routing for efficiency claims and learned routing for performance claims, but does not provide a unified speed–quality evaluation for the same model.
3. Cache comparison against softmax is not fair relative to modern GQA/MLA-style baselines
The paper reports decode-cache sizes at 256K context, where SMat , , and use approximately 99MB, 774MB, and 3439MB respectively, while the reported softmax baseline uses 4295MB. This means is already around 18% of the full-MHA softmax KV cache, and is close to softmax.
However, the softmax baseline appears to be full multi-head attention, not GQA, MQA, MLA, or any modern KV-compressed attention variant. In realistic LLM settings, GQA and MLA-style latent KV caches can reduce KV memory dramatically. With sufficiently large KV grouping, MLA, or token-level KV compression, the cache cost of modern softmax attention could plausibly fall below SMat , and potentially close to SMat . For example, contemporary MLA/GatedMLA-style baselines can make the memory advantage of SMat much less clear.
Therefore the claimed memory advantage over softmax is overstated. The relevant comparison should be against modern memory-efficient softmax baselines, not full-MHA KV cache.
4. No fair softmax attention quality baseline
The paper does include a Transformer/softmax baseline in some language-modeling experiments, but the comparison is not sufficient. It is unclear whether the Transformer baseline uses comparable architecture, tuning, context handling, GQA/MLA, or modern training recipes.
Moreover, since SMat is not exact softmax attention but a finite-feature / recurrent structured-memory mechanism, the key question is whether its memory reduction justifies any loss in modeling quality. This requires a quality–memory–speed Pareto comparison against strong softmax baselines. The paper does not provide this.
In particular, if a modern GatedMLA or GQA+FlashAttention baseline achieves much lower KV cache than full MHA while preserving softmax-quality modeling, then the practical tradeoff of SMat becomes unclear.
5. Experiments are far too small-scale for long-context LM claims
The language-modeling experiments are very limited:
- PG-19 small models: around 27M–33M parameters, 300M training tokens.
- Larger setting: 16 layers, width 768, 750M training tokens.
- No experiment at M parameters.
- No experiment at B tokens.
- No Chinchilla-scale or even moderately scaled pretraining evaluation.
- No strong long-context downstream tasks such as long-context QA, code, book-level reasoning, multi-document retrieval, or needle-style evaluations against modern baselines.
The reported PG-19 improvements over Mamba-2/GDN are marginal, and in some larger settings SMat is essentially tied or slightly worse. Given the substantial cache expansion over ordinary recurrent/linear models, these small gains do not demonstrate a worthwhile performance-efficiency tradeoff.
6. Contribution and experiments are not well connected
The theoretical contribution is strongest for hard-routing finite-feature SMat with fixed-horizon decoding. The empirical results that look most relevant use learned routing, top-4 state selection, and Mamba-2/GDN extensions. These are materially different systems with different complexity and implementation costs.
Questions for authors
-
Which exact SDPA backend was used for the softmax timing: memory-efficient attention, FlashAttention-2, or math backend?
-
Why are the main speed numbers reported for hard-routing SMat, rather than the learned top-4 routing variant used in PG-19/MQAR/JCKR?
-
What is the actual end-to-end prefill and decode throughput of learned SMat at 16K, 32K, 128K, and 256K context?
-
How does SMat compare against BF16 FlashAttention-2/3 with GQA or MLA-style KV compression?
-
What are SM occupancy, achieved memory bandwidth, and batch-size scaling during decoding?
-
Does SMat still have a favorable Pareto frontier when compared against modern GatedMLA or GQA softmax baselines?
-
Can the method scale to at least hundreds of millions of parameters and tens of billions of tokens, where long-context architectural tradeoffs become meaningful?
3 comments
Response to Reviewer mvca (part 2)
Q5. SM occupancy, bandwidth, and batch scaling during decoding. Table 10 decodes at batch 64. We also report 0.22 ms/token at batch 1 (App G.2).
Q4 and W3. Flash Attention with GQA or MLA, and the cache comparison.
We agree the comparison should use full MHA only as a reference point, and we are adding GQA rows (several group ratios) to the cache table.
Decode cache per sequence (MB), learned PG-19 models (16 layers, 6 heads × 128), batch 1. SMat is shown in fp32 as trained, and in bf16 to match the KV cache.
| 64K | 128K | 256K | |
|---|---|---|---|
| Softmax MHA (6 KV heads) | 3,221 | 6,442 | 12,885 |
| Softmax GQA (2 KV heads) | 1,074 | 2,147 | 4,295 |
| Softmax MQA (1 KV head) | 537 | 1,074 | 2,147 |
| SMat d=2, fp32 / bf16 | 1,215 / 607 | 1,630 / 815 | 2,322 / 1,161 |
| SMat d=3, fp32 / bf16 | 8,859 / 4,429 | 10,847 / 5,423 | 18,019 / 9,010 |
-
GQA reduces the softmax cache by a constant factor g, but still grows linearly in T. SMat's states are per KV head, so the same grouping applies to SMat and shrinks its cache by the same factor. At a fixed ratio, the comparison is vs .
-
MLA compresses the width of each token's entry, not the number of entries, so its cache also stays
-
Each SMat slot is larger. A slot is an matrix, against numbers per softmax token. So at short lengths SMat's cache can be larger. In App G.2, we give these numbers (36 MB vs. 17 MB at 1K for d = 3).
The useful quantity is hence the crossover length as a function of , and we will say it explicitly rather than comparing it to 256K.
- Efficiency evaluation is not convincing for modern LLM settings. This is not a naive attention implementation, but it is also not a convincing comparison against modern production-grade BF16/FP16 FlashAttention-2/3 attention stacks. It does not report whether the softmax baseline uses FA2, what backend is actually selected, or whether the comparison is against the best available modern attention implementation.
We thank you for the question, and we would be happy to include the following table in our manuscript which includes this detail now, including an evaluation of Softmax attention with FA2, as well as Softmax attention with CuDNN on H200 GPUs.
Prefill, one hard-routing SMat layer, bf16, NVIDIA H200 SXM (ms)
| T | SMat d=1 | SMat d=2 | SMat d=3 | SMat d=4 | Softmax, cuDNN | Softmax, FA2 | Paper's softmax line |
|---|---|---|---|---|---|---|---|
| 16K | 0.68 | 1.63 | 1.52 | 9.32 | 0.67 | 1.11 | 1.11 |
| 32K | 1.08 | 1.70 | 2.69 | 20.6 | 2.41 | 3.96 | 3.89 |
| 64K | 2.11 | 2.26 | 5.19 | 74.4 | 9.79 | 14.4 | 14.4 |
| 128K | 4.06 | 3.68 | 7.55 | 76.5 | 38.8 | 56.9 | 56.5 |
| 256K | 7.92 | 7.05 | 15.8 | 322 | 163 | 237 | 237 |
| 512K | 15.6 | 13.7 | 30.8 | 328 | 689 | 977 | 993 |
Decode, ms per step, NVIDIA H200 SXM (SMat / bf16 FlashAttention-2)
| Context | Batch 1 | Batch 64 | Batch 256 |
|---|---|---|---|
| 64K | 0.23 / 0.18 | 0.25 / 0.26 | 0.25 / 0.87 |
| 256K | 0.24 / 0.20 | 0.27 / 0.54 | — |
For reference, the fp32 memory-efficient kernel used for Table 10 takes 11.9 / 12.9 / 17.3 ms at 256K (batch 1 / 64 / 256).
Q6 and W4. Quality-memory-speed Pareto against strong softmax baselines. We agree with the reviewer's framing: SMat is finite-feature attention, not exact softmax, and we do not claim softmax-level modeling quality. The natural comparison class is recurrent and linear-attention models, where SMat adds structured, sublinear memory and improves recall, and we have added these tables in our manuscript.
Q7 and W5. Scale. Training at hundreds of millions of parameters and tens of billions of tokens is beyond our academic compute budget (as we mention in our footnote in Table 16). It is also not needed for the paper's claims, which are about mask structure, exact algorithms, and their complexity. We have reworded every LM-related claim to “preserve backbone quality at small scale.”
To connect our contribution and the experiments, we would be happy to add a short table that maps each experiment to the result it tests:
-
Theorem 3.1 (VC-dimension = d) maps to the subset routing experiment showing degradation past (Table 9 and Fig 5)
-
Hyperplane covering () maps to the multi-key retrieval tasks (Table 1,11,14)
-
Theorem 3.2 (prefill of maps to Figure 3 and Table 10 (hard routing),
-
Theorem 3.3 (Lemma 5 and decoding) maps to the decoding in Table 10 and Tables 5-7, and
-
Section 3.4 (learned extensions) maps to our experiments on MQAR, JCKR, PG-19, and the new learned-variant timing.
We hope the revisions and new measurements address your concerns. Of course, we would be happy to answer any further questions you may have for us, and if you find that we have addressed your concerns, we sincerely hope you would consider re-evaluating your assessment of our work.
Thank you,
Authors
Thanks for the authors' response which have partially addressed my concerns. However, some issues remain unsolved which make it inappropriate to give a weak accept to this paper.
(1) Absence of language modeling experiments at scale makes the model's advantages limited.
I believe that language modeling with 340M params and 10B tokens (especially in hybrid architecture) is the minimal configuration to demonstrate the model's overall effectiveness in real-world language modeling scenarios, and a lot of previous papers in linear attention (even 3 years ago) has already achieved this [1] . From my hands on experiences, no more than 200 GPU hours for A100/A800/H20 is enough for such a standard run, and the cost for GPU rental is not unacceptable.
Even though the synthetic tasks widely used in this paper have demonstrated some advantages of SMat attention, I've already encountered a lot of cases in linear attention improvement where the model excels in synthetic tasks but demonstrates performance degradation in other real world tasks such as the QA sub-tasks in RULER. Therefore, based on the current evidences and the authors' resistance in running 340M language modeling comparisons, I could not confirm that SMat attention demonstrates consistent advantages beyond the scope of the synthetic tasks in this paper.
Besides, I'd like to remind the authors that the scaling property of linear attention mechanisms is less stable than other efficient attention mechanisms (such as sparse attention), and models excelling at small param scales are not guaranteed to keep the same advantages when scaled up. I believe 340M is a bottom line for demonstrating a linear attention mechanism's scaling property.
(2) From the profiling results in the authors' response message (part 2), SMat attention is already slower than MQA with 1 kv heads. Unless the proposed SMat attention outperforms MQA by a large extent in real-world scenarios, I could not believe SMat achieves an effective speed-performance tradeoff.
As a consequence, I stick to my initial rating.
References: [1] https://arxiv.org/abs/2312.06635
Response to Reviewer mvca (part 1)
Dear Reviewer mvca,
We thank you for your detailed review, and for calling the hard-routing construction and the G=RCE⊤ factorization mathematically elegant.
However, we would like to push back on some of your concerns by pointing out that the main contribution of our work is to provide a structural result. Dense masks with VC-dimension d enable exact attention in O(T2−3/d+T) work, and O(rp) decoding from O(T1−1/d) states. We provided Table 10 to check that measured costs follow from these bounds, and it is not to benchmark against production softmax stacks.
Please find our response to your questions below:
Q1. Which SDPA Backend?
Table 10 uses PyTorch SDPA in fp32, which dispatches to the memory-efficient kernel (Appendix G.2). Moreover, FlashAttention-2 does not support fp32, and Figure 3 compares in bf16 against FlashAttention-2 via SDPA.
Q2. Why time hard routing and not the learned top-4 variant? Theorems 3.2-3.3 concern hard routing, so Table 10 times the object that the theorems describe. We agree that this left the learned variant's cost unmeasured. However, section 3.4 states its selector cost (Θ(T2−1/d) prefill scoring O(T1−1/d) per decoded token).
Q3. What is the actual end-to-end prefill and decode throughput of learned SMat at 16K, 32K, 128K, and 256K context?
We timed the trained PG-19 models end to end (16 layers, 150-190M parameters, bf16, batch 1, NVIDIA H200; median of repeated runs). "Learned SMat" is the four-read variant with learned top-4 routing used in our PG-19/MQAR/JCKR experiments; the backbone and the fastest softmax kernel (cuDNN) are shown for reference.
Prefill throughput (thousand tokens/s)
We see that on 512K, our speedup over cuDNN soft-max attention on H200 GPUs are 44x, 50x, 22x, and 2.1x for d=1,2,3,4, respectively.
Decode throughput (tokens/s, batch 1, prompt filling the context)
In decoding, we see that by batch 256 at 64k, SMat is 3.5x faster than bf16 FA2.
In summary, in prefill, learned SMat keeps a roughly constant per-token rate as context grows, while softmax's falls about 2x per doubling. SMat d=2 is slower than softmax at 16K-32K (2-3x), and 1.8-2.0x faster at 128K and 3.5-3.8x faster at 256K. Its overhead over the backbone (about 3x) is the memory branch; with that branch disabled, the model runs at backbone speed. In decoding, at batch 1, learned SMat is slower than softmax at every length (27-52 vs 78-93 tokens/s). At this model size all decoders are bound by per-layer launch overhead rather than memory traffic, so softmax's growing KV reads do not yet cost it time. In our batch-32 measurement at 64K, Mamba-2 + SMat d=2 is faster than full-MHA softmax but not than MQA.