Chain and Causal Attention for Efficient Entity Tracking

Erwan Fagnou, Paul Caillon, Blaise Delattre, Alexandre Allauzen

Introduction: The Entity Tracking Bottleneck

Large Language Models (LLMs) are remarkably good at generating text, but they often stumble on "entity tracking"—the ability to maintain and update the state of an object over a long sequence of operations (e.g., "The apple is in the red box. Move the apple to the blue box. Where is the apple?").

Standard Transformers are theoretically limited in their ability to track these entities. In a standard architecture, information can only "hop" one step per layer. To follow a chain of $n$ dependencies, the model effectively builds a binary tree of connections, meaning it requires at least $\log_2(n+1)$ layers to resolve the final state. As sequences get longer and more complex, this "depth tax" makes models computationally expensive and prone to errors in causal reasoning.

Mapping textual entity tracking to a computational graph.

Methods: Chain and Causal Attention Layer (ChaCAL)

This paper introduces ChaCAL, a modified attention mechanism that shifts the perspective of the attention matrix $A$ from a simple similarity score to an adjacency matrix in a computational graph.

In graph theory, if $A$ represents direct connections, then $A^2$ represents paths of length two, $A^3$ paths of length three, and so on. To capture a chain of any length, one needs the sum of all these powers: $A + A^2 + A^3 + \dots$. Rather than calculating infinite powers, the authors utilize the geometric series for matrices: $A(I - A)^{-1}$.

The ChaCAL formula introduces a hyperparameter $\gamma$ to control the "reach" of the attention: $$Y = (1 - \gamma) \cdot A(I - \gamma A)^{-1} V$$

When $\gamma = 0$, the mechanism reverts to standard attention. When $\gamma \approx 1$, it allows a single layer to "look back" through an entire chain of dependencies. Because these are causal (decoder-only) models, the matrix $A$ is lower-triangular. This allows the equation to be solved as a triangular system ($BY = C$), which is highly optimized on modern GPUs and maintains the standard $O(n^2)$ complexity of attention.

Key Results and Performance

The researchers validated ChaCAL across synthetic tasks and natural language datasets, including a "Boxes" dataset where items are moved between containers.

Accuracy vs. training epochs for standard Transformers vs. the 1-layer ChaCAL model.
  • Theoretical Validation: On a toy task with a chain length of 15, standard Transformers failed until they reached 4 layers (matching the $\log_2(16) = 4$ prediction). ChaCAL solved it perfectly with just 1 layer.
  • Superior Tracking: On the "Advanced Boxes" dataset, a 2-layer ChaCAL model achieved 99.1% accuracy, while a standard 5-layer Transformer (with more parameters) only reached 97.0%.
  • Efficiency: ChaCAL reached peak performance significantly faster than standard models. In the boxes experiment, it was roughly 1.75x faster to train than the 5-layer baseline while using fewer resources.
  • Generalization: When fine-tuned on OpenWebText, the ChaCAL-enhanced GPT-2 maintained a perplexity (21.46) very close to the standard fine-tuned baseline (20.15), proving it remains a capable general-purpose language model.

Conclusion

Instead of making models larger to solve reasoning tasks, ChaCAL makes the internal mechanisms smarter. By treating attention as connectivity, the model can perform "multi-hop" reasoning within a single layer, effectively flattening the required depth of the network and providing a significant efficiency upgrade for entity tracking tasks.

Summary updated

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.
BibTeX
@inproceedings{fagnou2024chain,
  author = {Erwan Fagnou and Paul Caillon and Blaise Delattre and Alexandre Allauzen},
  title = {{Chain and Causal Attention for Efficient Entity Tracking}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  doi = {10.18653/v1/2024.emnlp-main.731},
}
Figure