Skip to content

SMat-Attention: Structured Long-Context Sequence Modeling

Sep 2026 · arXiv.org · Vol abs/2609.36062 · 3 citations · 52 references
Computer Science

TL;DR

This work introduces Structured Matrix Attention via a family of causal masks with structured long-range routing whose row supports have VC-dimension, which makes VC-dimension an explicit knob governing access-pattern complexity, prefill cost, and decoding memory.

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 $d$. In our construction, $d=1$ recovers the standard causal mask, and increasing $d$ permits richer subset-routing patterns. We give chunkwise forward and backward algorithms to enable hardware-efficiency. For sequences of length $T$, the hard-routing construction takes $O(T^{2-3/d}+T)$ 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 $O(T^{1-1/d})$ 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-$k$ query reads retain subquadratic prefill, improve recall accuracy over the backbones in several settings, and achieve comparable small-scale language-modeling performance.

View source

Similar papers

Switching Linear Attention

Switching Linear Attention (SwiLA) is introduced, a novel sequence layer that bridges the gap to softmax attention by enhancing representational capacity while retaining the fixed-size recurrent state of linear attention.

Hyun Dong Lee, X. Gonzalez, Nicolas Zucchet et al. · 0 citations
Book Open access Sep 2026

CONGA: Continual Neural Gated Architecture for Long-History Sequential Recommendation

Existing sequential recommendation models rely on absolute positional encodings and fixed context windows, producing two structural failure modes: out-of-distribution degradation on histories longer than the training window, and hard context limits that discard long-range interactions. We present CONGA (COntinual Neura...

Hoang-Duong Le, Tuong Bach Hy Nguyen, Bac Le · 0 citations
#small language model Preprint Aug 2026

BF1: A Causal Dyadic Sparse-Attention Retrofit for Efficient Long-Context Transformers

The results establish BF1 as a reproducible sparse operator and selective retrofit primitive with real long-context systems value, and evaluates numerical correctness, selected-interaction scaling, kernel performance, partial-model inference, and matched next-token language modeling.

Hina Dixit · 0 citations
#natural language process... Preprint Oct 2026

HLA: Expressive Hybrid Linear Attention via Chunk-Wise Dynamic Mixing

Linear attention enables efficient long-context autoregressive decoding by compressing history into recurrent states, but this compression can make selective access to sparse and distant information difficult. Existing chunk-based extensions increase memory capacity, yet learned chunk-mixing coefficients may remain fix...

Zhuo-Kun Chen, Xi Lin, Xi-Yu Wu et al. · 0 citations

RunningTensor: Generalizing Linear Attention to Higher-Order Recurrent States

The RunningTensor is introduced, which generalizes this memory to an order-o tensor, updated by a rank-1 outer product and read by contracting against $o-1$ vector queries, and improves performance on language-understanding and non-synthetic retrieval tasks, suggesting that higher-order recurrent state can provide usef...

Luca Herranz-Celotti, Vincent Guigue · 1 citation

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.