Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity

2026/05/21 by Hangyue Zhao, Paul Caillon, Erwan Fagnou +1 · 1 voice · 1 citation
Computer Science · #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2605.22476

Abstract

Entity tracking requires maintaining and updating latent states for entities and attributes over long sequences. Recent task-specific attention operators can compress deep Transformer stacks into a few layers by performing multi-hop state propagation within a single layer, but their dense evaluation remains expensive. We show that in this setting, learned attention is strongly structured: most mass concentrates in local block-diagonal neighborhoods with a light cross-block residue. Exploiting this, we derive a blockwise evaluation of a resolvent-style operator that keeps within-block interactions exact and routes cross-block interactions through a reduced system. The resulting evaluation is subquadratic in sequence length O(n^4/3d) (and O(n^7/3) when d≈ n). On controlled tracking benchmarks, our method matches the dense operator's accuracy while reducing wall-clock time by 12-29% under a standardized measurement protocol, and is up to 2.4 × faster than a compact dense Transformer at comparable exact-match accuracy. We further provide ablations over block size and model capacity, and identify a limitation: performance collapses when the number of simultaneously evolving properties exceeds the number of attention heads.

Citations

• What Matters in Transformers? Not All Attention is Needed
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs
• Fine-Tuning Enhances Existing Mechanisms: A Case Study on Entity Tracking
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
• Not All Tokens Are Equal: Human-centric Visual Analysis via Token Clustering Transformer
• SCROLLS: Standardized CompaRison Over Long Language Sequences
• DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification
• Long Range Arena: A Benchmark for Efficient Transformers
• Length-Adaptive Transformer: Train Once with Length Drop, Use Anytime with Search
• Rethinking Attention with Performers
• Big Bird: Transformers for Longer Sequences
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
• Linformer: Self-Attention with Linear Complexity
• Longformer: The Long-Document Transformer
• Reformer: The Efficient Transformer
• BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension
• What Does BERT Look At? An Analysis of BERT's Attention
• What Does BERT Look at? An Analysis of BERT’s Attention
• Generating Long Sequences with Sparse Transformers
• MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling
• Tracking State Changes in Procedural Text: A Challenge Dataset and Models for Process Paragraph Comprehension
• End-to-end Neural Coreference Resolution
• Attention Is All You Need
• Structured Attention Networks
• Tracking the World State with Recurrent Entity Networks
• Modeling Local Coherence: An Entity-Based Approach
• Quoref: A Reading Comprehension Dataset with Questions Requiring Coreferential Reasoning

Cited by

• Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing

Discussions

• 📖 New LAMSADE preprint: Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity. (arXiv) https://doi.org/10.48550/arXiv.2605.22476 [bsky, 0 points, 0 comments]

Related

• Combiner: Full Attention Transformer with Sparse Computation Cost
• Representational Strengths and Limitations of Transformers
• Intrinsically Interpretable Attention via Sparse Post-Training
• The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers