SMat-Attention introduces a family of causal attention masks where the complexity of long-range access is controlled by a single parameter: the VC dimension d. This structure bridges the gap between softmax attention (flexible but quadratic) and (efficient but limited to a fixed-size state). For sequences of length T, the hard-routing version achieves subquadratic prefill computation (O(T^{2-3/d}+T) work) and constant-time decoding per token after processing a distant prefix, using O(T^{1-1/d}) cached states.
The approach is extended to modern recurrent architectures like Mamba-2 and Gated DeltaNet by adding a learned content-hashing and four-read selector, which preserves subquadratic complexity. Controlled experiments on subset-routing and multi-key retrieval tasks show that SMat variants improve mean recall accuracy over the native backbones in several settings, while remaining competitive on small-scale language modeling.
This work is interesting because it makes the tradeoff between expressivity and efficiency explicit and tunable. Rather than committing to either full token-level interactions or full compression into a fixed state, practitioners can select the VC dimension to match their desired balance of computational cost and access flexibility.