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.

Ce travail met en évidence une limitation théorique des transformers pour les tâches de suivi d’entités, montrant qu’ils nécessitent log2(n+ 1) couches pour gérer n changements d’état. Pour surmonter cette contrainte, nous proposons ChaCAL (Chain and Causal Attention Layer), une modification de l’attention standard qui l’interprète comme une matrice d’adjacence, permettant de capturer efficacement les dépendances longues avec une seule couche. Les expériences menées sur un jeu de données synthétique et un autre de suivi d’objets démontrent que ChaCAL surpasse les transformers classiques en réduisant la profondeur du modèle, tout en maintenant des performances compétitives sur une tâche de modélisation du langage. Cette approche optimise l’efficacité des modèles tout en réduisant leur coût computationnel.

This paper investigates the limitations of transformers for entity-tracking tasks in large language models. We identify a theoretical constraint, showing that transformers require at least log₂ (n+1) layers to handle entity tracking with n state changes. To address this issue, we propose an efficient and frugal enhancement to the standard attention mechanism, enabling it to manage long-term dependencies more efficiently. By considering attention as an adjacency matrix, our model can track entity states with a single layer.Empirical results demonstrate significant improvements in entity tracking datasets while keeping competitive performance on standard natural language modeling. Our modified attention allows us to achieve the same performance with drastically fewer layers. Additionally, our enhanced mechanism reveals structured internal representations of attention. Extensive experiments on both toy and complex datasets validate our approach. Our contributions include theoretical insights, an improved attention mechanism, and empirical validation.