SMat-Attention: structured causal masks that trade off routing complexity and efficiency
This arXiv preprint introduces Structured Matrix Attention (SMat-Attention), a family of causal attention masks whose row supports have VC-dimension d, letting d=1 recover the standard causal mask and larger d enable richer subset-routing. The paper gives chunkwise forward/backward algorithms for hardware efficiency, proves subquadratic prefill work O(T^{2-3/d}+T) for a prescribed family and constant-time per-token decoding after a distant prefix with O(T^{1-1/d}) cached states in fixed-horizon streaming, and reports experiments and learned-routing extensions to Mamba-2 and Gated DeltaNet showing improved recall and comparable small-scale LM performance.