acceptodds
Under review as a conference paper at ICLR 2027

SMat-Attention: Structured Long-Context Sequence Modeling

Abstract

Long-context sequence models face a fundamental tradeoff: softmax attention uses flexible token-level interactions at quadratic cost, whereas linear attention obtains linear-time training and constant-time decoding by compressing history into a fixed-size state. In this work, we ask whether we can connect these regimes through a tunable notion of structure. To this end, we introduce Structured Matrix Attention (SMat-Attention) via a family of causal masks with structured long-range routing whose row supports have VC-dimension . In our construction, recovers the standard causal mask, and increasing permits richer subset-routing patterns. We give chunkwise forward and backward algorithms to enable hardware-efficiency. For sequences of length , the hard-routing construction takes work, despite the mask being dense, for our prescribed family. In fixed-horizon streaming, decoding after the distant prefix takes constant time per token using cached states. SMat-Attention therefore makes VC-dimension an explicit knob governing access-pattern complexity, prefill cost, and decoding memory. Empirically, subset-routing and rule-assisted multi-key retrieval experiments illustrate the masks’ routing expressiveness. Extensions to Mamba-2 and Gated DeltaNet using learned routing with top- query reads retain subquadratic prefill, improve recall accuracy over the backbones in several settings, and achieve comparable small-scale language-modeling performance.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Long Context, Efficient Attention, Structured Matrix, Causal masks, Decoding, ML Systems

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_mvcaOpenReview ↗
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 dk×dvd_k \times d_v summary states, with the number of states scaling as roughly T1−1/dT^{1-1/d}, 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 G=RCE⊤G = RCE^\top 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 O(1)O(1). In the learned four-read variant, each query must score B=Θ(T1−1/d)B = \Theta(T^{1-1/d}) 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 d=2d=2, d=3d=3, and d=4d=4 use approximately 99MB, 774MB, and 3439MB respectively, while the reported softmax baseline uses 4295MB. This means d=3d=3 is already around 18% of the full-MHA softmax KV cache, and d=4d=4 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 d=3d=3, and potentially close to SMat d=2d=2. 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 ≥340\geq 340M parameters.
  • No experiment at ≥10\geq 10B 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
  1. Which exact SDPA backend was used for the softmax timing: memory-efficient attention, FlashAttention-2, or math backend?

  2. 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?

  3. What is the actual end-to-end prefill and decode throughput of learned SMat at 16K, 32K, 128K, and 256K context?

  4. How does SMat compare against BF16 FlashAttention-2/3 with GQA or MLA-style KV compression?

  5. What are SM occupancy, achieved memory bandwidth, and batch-size scaling during decoding?

  6. Does SMat still have a favorable Pareto frontier when compared against modern GatedMLA or GQA softmax baselines?

  7. 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
AuthorsOpenReview ↗

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⊤G = RCE^\top 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 dd enable exact attention in O(T2−3/d+T)O(T^{2-3/d} + T) work, and O(rp)O(rp) decoding from O(T1−1/d)O(T^{1-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)\Theta(T^{2-1/d}) prefill scoring O(T1−1/d)O(T^{1-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)

Model16K32K128K256K
GDN + SMat (d=2)169235261263
GDN + SMat (d=3)154175204192
Mamba-2 + SMat (d=2)234267288285
Mamba-2 + SMat (d=3)160179193165
GDN (backbone)502706760771
Mamba-2 (backbone)859907932931
Softmax, MHA (cuDNN)49239514675

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,4d=1,2,3,4, respectively.

Decode throughput (tokens/s, batch 1, prompt filling the context)

Model16K32K128K256K
GDN + SMat (d=2)31.129.827.226.9
GDN + SMat (d=3)31.229.726.727.5
Mamba-2 + SMat (d=2)51.052.442.442.9
Mamba-2 + SMat (d=3)50.952.540.541.4
GDN (backbone)53.957.455.054.2
Mamba-2 (backbone)61.858.260.059.3
Softmax, MHA87.092.877.878.4

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.

AuthorsOpenReview ↗

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.

64K128K256K
Softmax MHA (6 KV heads)3,2216,44212,885
Softmax GQA (2 KV heads)1,0742,1474,295
Softmax MQA (1 KV head)5371,0742,147
SMat d=2, fp32 / bf161,215 / 6071,630 / 8152,322 / 1,161
SMat d=3, fp32 / bf168,859 / 4,42910,847 / 5,42318,019 / 9,010
  1. 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 Θ(T)\Theta(T) vs Θ(T1−1/d)\Theta(T^{1-1/d}).

  2. MLA compresses the width of each token's entry, not the number of entries, so its cache also stays Θ(T)\Theta(T)

  3. Each SMat slot is larger. A slot is an r×pr\times p matrix, against 2dv2d_v 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 d,g,rd,g,r, 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)

TSMat d=1SMat d=2SMat d=3SMat d=4Softmax, cuDNNSoftmax, FA2Paper's softmax line
16K0.681.631.529.320.671.111.11
32K1.081.702.6920.62.413.963.89
64K2.112.265.1974.49.7914.414.4
128K4.063.687.5576.538.856.956.5
256K7.927.0515.8322163237237
512K15.613.730.8328689977993

Decode, ms per step, NVIDIA H200 SXM (SMat / bf16 FlashAttention-2)

ContextBatch 1Batch 64Batch 256
64K0.23 / 0.180.25 / 0.260.25 / 0.87
256K0.24 / 0.200.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:

  1. Theorem 3.1 (VC-dimension = d) maps to the subset routing experiment showing degradation past k=dk=d (Table 9 and Fig 5)

  2. Hyperplane covering (k≤d−1k \leq d-1) maps to the multi-key retrieval tasks (Table 1,11,14)

  3. Theorem 3.2 (prefill of O(T2−3/d+T)O(T^{2-3/d} + T) maps to Figure 3 and Table 10 (hard routing),

  4. Theorem 3.3 (Lemma 5 and decoding) maps to the decoding in Table 10 and Tables 5-7, and

  5. 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

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

The paper introduces SMat-Attention, a structured memory mechanism that interpolates between a single recurrent summary and more flexible access to historical subsets. Distant tokens are pooled into profile states, which are combined into reusable summaries through finite-field point–hyperplane incidences. The construction uses mask VC dimension to characterize access-pattern complexity and establishes corresponding computation and cache bounds. The paper also develops learned-routing extensions for Mamba-2 and Gated DeltaNet and evaluates them on synthetic retrieval tasks and PG-19.

Critical strengths
  1. The paper connects the VC dimension of a structured mask family to computation and cache complexity, providing a principled characterization of long-range access patterns.
  2. The finite-field point–hyperplane formulation gives a concrete mechanism for organizing overlapping memory summaries and reusing aggregation across queries.
  3. The paper develops chunkwise forward and backward algorithms, together with a cached decoding procedure, and states their assumptions and asymptotic costs explicitly.
Critical weaknesses
  1. Evaluation relies primarily on synthetic retrieval tasks and PG-19 language modeling. The main learned variants lack downstream long-context evaluation, while their language-modeling results show small or negligible gains and use only one seed per configuration. Could the authors add more evaluations, including both general and long-context benchnmarks?
  2. These is a gap between theoretical guarantees and measured model performance. Linear-time prefill and constant-time decoding apply to hard routing. The learned top-4 selector introduces sequence-length-dependent computation, but the reported efficiency benchmarks do not establish the end-to-end quality–efficiency tradeoff of these learned variants.
Questions for authors

See weaknesses.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 3db5

Dear Reviewer 3db5,

We thank you for your detailed review, and for appreciating our principled characterization of long-range access patterns. Please find our response below which addresses each of your concerns:

W1: Evaluation beyond synthetic tasks and PG-19. The synthetic tasks we provided are really quite deliberate as they were to validate the predictions of our theoretical framework:

  1. Subset routing (Table 9). Accuracy holds up to k=dk=d and degrades beyond it, as our VC-dimension theory predicts,
  2. Multi-key retrieval (Tables 1, 14). We show that retrieval succeeds for k≤d−1k\leq d-1 targets, which is what the hyperplane geometry guarantees: d=2d=2 solves k=1,d=3k=1,d=3 solves k≤2k\leq 2 and d=4d=4 solves k≤3k\leq 3.

Importantly, we do not position SMat as a SOTA language model, and our language-modeling runs are only to check that the added structure preserves backbone quality. That said, we agree the evaluation should be broader, and we are adding multiple seeds for the PG-19 runs (Table 16), and a long-context retrieval benchmark at the scale we train on.

Two existing results already address long-context behavior. Table 5 evaluates MQAR at up to 8x the training length, and the quarter-length window variant improves with evaluation length (82.2% to 97.6%). Table 6 varies how far back the stored pairs are from the queries.

W2: Gap between the guarantees and the learned variant. We agree the paper should make this distinction explicit, and we have revised the text accordingly:

  1. The linear-time prefill and constant-time decoding guarantees (Theorems 3.2-3.3) apply to hard routing.
  2. The learned four-read selector adds Θ(T2−1/d)\Theta(T^{2-1/d}) scoring during prefill and O(T1−1/d)O(T^{1-1/d}) per decoded token. Contribution 3 and Section 3.4 state this, and it remains subquadratic for every fixed dd: each query scores B=Θ(T1−1/d)B=\Theta(T^{1-1/d}) type states instead of TT tokens, a factor of T1/dT^{1/d} fewer scores than all-pairs attention.

We had not measured the learned variant end to end, and we agree that is needed.

Now, we have 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)

Model16K32K128K256K
GDN + SMat (d=2)169235261263
GDN + SMat (d=3)154175204192
Mamba-2 + SMat (d=2)234267288285
Mamba-2 + SMat (d=3)160179193165
GDN (backbone)502706760771
Mamba-2 (backbone)859907932931
Softmax, MHA (cuDNN)49239514675

Decode throughput (tokens/s, batch 1, prompt filling the context)

Model16K32K128K256K
GDN + SMat (d=2)31.129.827.226.9
GDN + SMat (d=3)31.229.726.727.5
Mamba-2 + SMat (d=2)51.052.442.442.9
Mamba-2 + SMat (d=3)50.952.540.541.4
GDN (backbone)53.957.455.054.2
Mamba-2 (backbone)61.858.260.059.3
Softmax, MHA87.092.877.878.4

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 answered your concerns, we sincerely hope you would consider re-evaluating your assessment of our work.

Thank you,

Authors

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

This paper proposes SMat-Attention, which organizes historical memory using points and hyperplanes over finite fields. Historical tokens are mapped to profiles, and their KV associations are accumulated in the corresponding matrix states; queries retrieve information from pre-aggregated type states. The authors characterize subset access patterns through the VC dimension of the masks and provide chunkwise training and cached decoding algorithms for a specific hard-routing construction. The paper also extends this memory organization to Mamba-2 and Gated DeltaNet, using learnable write addresses and top-4 reads. These extensions improve performance on synthetic retrieval tasks while maintaining small-scale language modeling performance close to that of the base models.

Critical strengths
  1. The multi-state memory organization is worth exploring. Compared with aggregating the entire history into a single recurrent state, this design provides more distinct memory states and overlapping subset access patterns. In my view, its potential lies in further developing it into a high-capacity memory with low-cost sparse addressing and updates, so that storage capacity can grow without a proportional increase in per-token computation.

  2. The geometric construction provides a well-defined object of analysis. Describing which historical information a query can access through subset structures over finite fields makes the memory organization more than an empirical routing design. The connections among the VC dimension analysis, shared aggregation, and chunkwise algorithms are among the more interesting aspects of this paper.

  3. The improvements on synthetic tasks are substantial. For example, in Table 1, when k = 3 SMat with d=4 achieves an average exact-support accuracy of 98.99%, compared with 66.46% for softmax. The appendix also includes learned-routing experiments, rather than only rule-assisted results. These experiments support the effectiveness of the structure in certain multi-target retrieval settings.

Critical weaknesses
  1. The current implementation has not yet fully realized the potential of high-capacity sparse memory. Although writes and final reads are sparse, each profile still stores a finite-dimensional dense association matrix, and the type table must cache multiple pre-aggregated states. The learned selector scores all B types, so expanding the memory still increases routing costs. Although the total cache grows with context length, historical associations remain compressed into a sublinear number of finite-capacity states, leaving room for within-slot collisions and associative interference. The paper does not sufficiently establish whether this design continues to improve retrieval with larger memory budgets and longer contexts, or whether the gains justify the additional storage and routing costs. A joint analysis of memory size, context length, and retrieval accuracy would be more convincing.

  2. The gains in Table 1 cannot yet be clearly attributed to the geometric structure, nor can they be directly interpreted as evidence of superior retrieval capabilities over softmax. The SMat model in this table uses a rule-based hyperplane selector to cover the requested target profiles, whereas the baselines have no corresponding rule-based module. Moreover, for k=3, softmax achieves approximately 99.9%, 0%, and 99.5% across the three seeds; its lower mean primarily reflects a training failure in one seed rather than a consistent gap in representational capacity. Increasing d also changes geometric coverage, the numbers of profiles and types, and the memory budget simultaneously. It is therefore necessary to disentangle the contributions of geometric dimension, rule-based assistance, and optimization stability under matched storage, candidate counts, and read budgets. The existing matched MoM comparisons are helpful, but they do not fully isolate these factors.

  3. There remains an evidence gap between success on specific subset tasks and general improvements in retrieval. The task in Table 1 is closely aligned with the ability of hyperplanes to cover multiple targets, so it may primarily validate the suitability of this geometric inductive bias for that particular task. The other learned-routing retrieval experiments provide additional evidence, but they are not sufficient to establish that the advantage generalizes reliably across different numbers of targets, distractor distributions, repeated keys, and longer contexts. The PG-19 results mainly support approximate performance parity, and Table 16 uses a single training seed, so it cannot substantiate broader modeling advantages. I would like to see more retrieval tasks that are less closely tied to the geometric construction, with per-task results reported under different memory loads.

Questions for authors

see weaknesses

1 comment
AuthorsOpenReview ↗

Response to Reviewer Rjyi

Dear Reviewer Rjyi,

We thank you for your thoughtful review and for seeing the multi-state memory organization as a path toward high-capacity memory with sparse addressing. We respond to each of your concerns below:

W1: Capacity, collisions, and scaling with memory budget. We agree that each profile is a finite r×pr\times p association matrix, so tokens that share a profile can interfere. The construction intentionally sits between one fixed-size state and an uncompressed KV cache: the number of states grows as Θ(T1−1/d)\Theta(T^{1-1/d}), so each profile receives about T1/dT^{1/d} tokens. We clarify the following, however:

  1. In the hard-routing construction (the object of Theorems 3.2-3.3), routing costs O(1)O(1) per query. Each query reads the single state of its own type, so the size of the type table affects the cache but not routing cost. Only the learned selector scores all BB types; Section 3.4 states this cost explicitly, and we now measure it.
  2. As requested, we are adding a joint sweep of memory size (qq, hence BB) x context length x memory load on MQAR, reporting accuracy, cache size, and routing cost together.

W2: Attributing Table 1 to the geometry. This is a fair point, and we take its parts in turn.

  1. Rule-assisted selector. We agree, and the paper says so explicitly (Appendix G.2). The rule isolates what the mask can express, separately from what routing can learn. In fact, with a linear head that predicts the direction from the query (seed 0), SMat reaches 60.1% and 44.6% at d = 3, and 74.2% and 59.2% at d=4, for k=2,3k = 2, 3. Every baseline gets 0%. Also, fully learned Mamba-2–SMat (Table 14) reaches 99.90 ±\pm 0.14% at k = 3 with d=4, while Mamba-2 gets 0%.

We will move both results into the main text next to Table 1.

  1. Softmax seed variance. We agree that the softmax mean reflects one run that never left the constant-prior plateau (Table 11: 99.9 / 0.0 / 99.5 at k=3), not a gap in capacity. Table 12 shows the other schedules we tried. We will certainly report the per-seed results in the main paper.

  2. Separating geometry from memory budget. We incorporated two controls to address this. (a) Memory-matched linear attention (Table 11) scores 0% at every k k. LSH bucketing with 121 and 125 buckets uses the same number of cells as SMat's profile tables at d=3 (q=11,q2=121q=11, q^2 = 121) and d=4d=4 (q=5,q3=125q = 5, q^3 = 125). LSH reads one cell, while SMat reads a hyperplane's union of cells. Both reach 100% at k=1k=1, but LSH falls to 0.3-2.1% at k=2k=2 while SMat d=3d=3 stays at 99.8%. With the number of cells held fixed, this isolates the union-of-cells geometry.

We will also add the controlled ablation you suggest of having the same storage, candidate count, and read budget, with dd varied and the rule removed.

W3: Generalization beyond tasks aligned with the geometry. We already have two results that address this: MQAR (Table 2) and joint context-key recall (Table 3) are not built around hyperplanes. JCKR in particular has keys repeated across contexts, so a key alone cannot identify the record. Tables 5-6 vary evaluation length up to 8x the training length, and the distance between stored pairs and queries.

We will add per-load breakdowns for MQAR and JCKR, with multi-key variants with more distractors and more targets. In particular, we agree that the PG-19 runs (single seed) show only parity. We have reworded them as a check that SMat preserves backbone quality, and we are adding seeds as well.

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 answered your concerns, we sincerely hope you would consider re-evaluating your assessment of our work.

Thank you,

Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to Reviewers

We thank the reviewers for their careful reading. The reviewers found the construction "mathematically elegant" (mvca), a "principled characterization of long-range access patterns" (3db5), and "a well-defined object of analysis" (Rjyi). We think several of the reviewers’ concerns come from considering our work as a long-context LLM paper, which we do not really claim anywhere. We address that first, then list the revisions and new experiments.

What we claim in the paper

The paper's contribution is structural and algorithmic: it identifies a property of the attention mask that controls both expressivity and computational cost, and makes that property tunable.

  1. A family of dense causal masks whose VC dimension is exactly dd (Theorem 3.1). The family is built from point–hyperplane incidences over Fqd−1\mathbb F_q^{d-1}. Here, d=1d=1 recovers the causal mask, and the masks have Θ(T2)\Theta(T^2) nonzeros for every dd.

  2. Exact finite-feature attention under these masks in O(T2−3/d+T)O(T^{2-3/d}+T) work (Theorem 3.2) with a matching backward pass. This is linear for d≤3d\leq 3. For comparison, enumerating the long-range edges costs Θ(T2−1/d)\Theta(T^{2-1/d}) and the best known general result for VC-dimension dd matrices is O(T2−1/d)O(T^{2-1/d}) per product after O(T2)O(T^2) preprocessing (Anand et. al., NeurIPS 2025).

The incidence structure we exploit in our construction saves a further T2/dT^{2/d} by factoring the mask as G=RCE⊤G=RCE^\top, which lets keys be pooled once and query aggregates be shared.

  1. Moreover, O(rp)O(rp)-time decoding per token from O(T1−1/d)O(T^{1-1/d}) cached states (Theorem 3.3). Lemma 5 extends this to horizon-free decoding.

Together these make VC dimension an explicit knob that trades routing expressivity against prefill cost and cache size, and we do not claim a new SOTA language model. The point of our experiments are really only to test whether the theory's predictions hold. For instance, our recurrent extensions check that the structure is compatible with modern backbones, and they are not meant as competitive LLMs.

Furthermore, we would like to correct some of our wording. Every member of the family is finite-feature (kernel) attention. What interpolates is the expressivity of the mask, from VC dimension 1 (linear attention) up to Θ(log⁡T)\Theta(\log T). Softmax is covered only through kernel approximation (Sec. 2). We will replace "interpolates between softmax and linear attention" with this more precise statement throughout.

The experiments test the theory's predictions

  1. Subset routing (Table 9, Fig. 5). VC dimension dd predicts that all subset patterns over dd landmarks are realizable, but not over d+1d+1. Accuracy degrades right after k=dk=d as predicted: d=2d=2: 99.5% at k=2k=2, then 82.5% at k=3k=3. At d=3d = 3: 98.2% at k=3k=3, then 89.5% at k=4k = 4. At d=4d = 4: 98.0% at k=4k=4, then 93.7% at k=5k=5.

Baselines with VC dimension 1 (Mamba-2, DeltaNet, GDN, Log-Linear) behave like SMat with d=1d= 1.

  1. Multi-key retrieval (Table 1, Table 14). Any d−1d-1 profiles lie on a common hyperplane, so retrieving k≤d−1k\leq d-1 targets should work. With learned routing in Mamba-2, d=4d=4 reaches 99.9% at k=3k=3, while the backbone gets 0%. Memory-matched linear attention (Table 11) and MoM variants matched on profile count and on storage (Table 15) rule out "just a larger state" as the explanation. Cost (Fig. 3, Table 10). Measured scaling follows the bounds: linear for d≤3d\leq 3 and the T2−3/dT^{2-3/d} term dominates at d=4d=4.

Revisions

  1. Table 1 (Reviewer Rjyi). Per-seed results (already in Table 11) now appear in the main text. We note that softmax solves the task whenever it escapes the constant-prior plateau (Table 12), so we make no claim of superiority over softmax.

  2. Learned-routing efficiency (Reviewers mvca, 3db5). Sec. 3.4 already states the Θ(T2−1/d)\Theta(T^{2-1/d}) cost of the learned selector. We now measure the full prefill, decode, and memory cost of the learned, gated variant at 16K-256K.

  3. Baselines (Reviewers mvca). We add a bf16 FlashAttention-2 baseline with GQA, include GQA rows in the cache comparison, and add a batch-size sweep for decoding.

We hope this clarifies the scope of our work, and we would be glad to discuss further.

Thank you,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.