Abstract
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_2 (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.
Introduction
Entity tracking—the ability to maintain and update the state of objects through a sequence of events—is a fundamental component of reasoning. For example, in a narrative where an object is moved from a drawer to a pocket, and then to a table, a model must track these transitions to correctly identify the object's final location. While Large Language Models (LLMs) show remarkable capabilities, their underlying Transformer architecture faces a theoretical bottleneck when resolving long dependency chains.
The Logarithmic Depth Constraint
Standard Transformers typically require a number of layers that grows logarithmically with the number of state changes ($n$). This is because each standard attention layer generally resolves only one step in a dependency chain per head. To resolve a chain of $n$ updates, the model must effectively build a binary tree of dependencies, necessitating at least $\log_2(n + 1)$ layers. For sequences involving numerous updates, this requirement forces models to be unnecessarily deep, increasing computational costs and memory overhead.
Methods: Chain and Causal Attention (ChaCAL)
We propose ChaCAL (Chain and Causal Attention Layer), a novel mechanism designed to overcome this depth constraint. The core innovation lies in reinterpreting the attention matrix $A$ as an adjacency matrix of a directed acyclic graph (DAG).
In graph theory, if $A$ represents direct dependencies, then $A^k$ represents paths of length $k$. To track an entity through an arbitrary number of steps in a single layer, we need to account for all possible path lengths. This is achieved through the sum of the power series $A + A^2 + A^3 + \dots$, which has a closed-form solution: $A(I - A)^{-1}$.
The ChaCAL Formula
To ensure numerical stability and allow for interpolation with standard attention, we introduce a damping factor $\gamma \in [0, 1)$: $$Y = (1 - \gamma) \cdot A(I - \gamma A)^{-1} V$$
Because the attention matrix $A$ is lower-triangular in causal models, we avoid explicit matrix inversion. Instead, we solve the triangular system $BY = C$ using efficient linear algebra solvers (e.g., solve_triangular) during training and forward substitution during inference. This allows a single layer to have an effectively infinite receptive field along a dependency chain.
Experimental Evaluation
We evaluated ChaCAL across three distinct benchmarks:
- Toy Dataset: A synthetic task requiring the model to follow a chain of shuffled indices. This task is designed to be difficult for standard attention mechanisms.
- Boxes Dataset: A natural language task where items are moved between containers. We utilized an "Advanced" version featuring implicit moves (e.g., "Move the contents of Box A to Box B"), which requires resolving complex nested dependencies.
- OpenWebText: To ensure general language modeling capabilities are preserved, we fine-tuned GPT-2 scale models on this standard English corpus.
Key Results
- Efficiency Gains: On the toy task, a standard Transformer required 5 layers to reach 100% accuracy. ChaCAL achieved 100% accuracy with a single layer within only 3 epochs.
- Superior Tracking: In the Advanced Boxes task, a 2-layer ChaCAL model achieved 99.1% accuracy, outperforming a 5-layer standard Transformer (97.0%) despite having significantly fewer parameters.
- General Language Performance: Replacing standard attention with ChaCAL in GPT-2 resulted in a perplexity of 21.46, compared to 20.15 for the standard model. This indicates that ChaCAL maintains competitive performance on general natural language tasks while providing specialized logic benefits.
Conclusion
ChaCAL addresses a fundamental theoretical limitation of the Transformer architecture by treating attention as a reachability problem in a graph. By enabling single-layer resolution of long dependency chains, ChaCAL allows for shallower, more efficient models that excel at complex entity tracking without sacrificing general language modeling performance. Future work will explore scaling this mechanism to multi-billion parameter models and learning the damping factor $\gamma$ dynamically.
Summary updated