# Structured-Sparse Attention for Entity Tracking with Subquadratic Sequence Complexity

arXiv: https://arxiv.org/abs/2605.22476 · HTML: https://mlsanity.com/paper/2605.22476/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 32 references that are in the map.
- First posted on arXiv 21 May 2026.

## Builds on (most cited first, 28 of 28)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [DynamicViT: Efficient Vision Transformers with Dynamic Token Sparsification](https://mlsanity.com/paper/2106.02034/) (2021)
- [MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling](https://mlsanity.com/paper/1810.00278/) (2018)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [End-to-end Neural Coreference Resolution](https://mlsanity.com/paper/1707.07045/) (2017)
- [SCROLLS: Standardized CompaRison Over Long Language Sequences](https://mlsanity.com/paper/2201.03533/) (2022)
- [Fine-Tuning Enhances Existing Mechanisms: A Case Study on Entity Tracking](https://mlsanity.com/paper/2402.14811/) (2024)
- [Not All Tokens Are Equal: Human-centric Visual Analysis via Token Clustering Transformer](https://mlsanity.com/paper/2204.08680/) (2022)
- [Quoref: A Reading Comprehension Dataset with Questions Requiring Coreferential Reasoning](https://mlsanity.com/paper/1908.05803/) (2019)
- [Structured Attention Networks](https://mlsanity.com/paper/1702.00887/) (2017)
- [What Matters in Transformers? Not All Attention is Needed](https://mlsanity.com/paper/2406.15786/) (2024)
- [Length-Adaptive Transformer: Train Once with Length Drop, Use Anytime with Search](https://mlsanity.com/paper/2010.07003/) (2020)
- [Efficient Transformers with Dynamic Token Pooling](https://mlsanity.com/paper/2211.09761/) (2022)
- [Tracking State Changes in Procedural Text: A Challenge Dataset and Models for Process Paragraph Comprehension](https://mlsanity.com/paper/1805.06975/) (2018)
- [Tracking the World State with Recurrent Entity Networks](https://mlsanity.com/paper/1612.03969/) (2016)
- [Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs](https://mlsanity.com/paper/2404.10308/) (2024)
- [Entity-aware Transformers for Entity Search](https://mlsanity.com/paper/2205.00820/) (2022)
- [Chain and Causal Attention for Efficient Entity Tracking](https://mlsanity.com/paper/2410.05565/) (2024)

## Built on by (most cited first, 1 of 1)

- [Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing](https://mlsanity.com/paper/2605.31367/) (2026)

## Abstract (arXiv)

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(n4/3d) (and O(n7/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.