Abstract
Recent studies of the computational power of recurrent neural networks (RNNs) reveal a hierarchy of RNN architectures, given real-time and finite-precision assumptions. Here we study auto-regressive Transformers with linearised attention, a.k.a. linear Transformers (LTs) or Fast Weight Programmers (FWPs). LTs are special in the sense that they are equivalent to RNN-like sequence processors with a fixed-size state, while they can also be expressed as the now-popular self-attention networks. We show that many well-known results for the standard Transformer directly transfer to LTs/FWPs. Our formal language recognition experiments demonstrate how recently proposed FWP extensions such as recurrent FWPs and self-referential weight matrices successfully overcome certain limitations of the LT, e.g., allowing for generalisation on the parity problem. Our code is public.
Introduction
Standard Transformers face a "quadratic bottleneck" where computational costs grow with the square of the sequence length. Linear Transformers (LTs), also known as Fast Weight Programmers (FWPs), address this by using linearized attention, allowing them to operate with constant-size memory during inference, similar to an RNN. However, theoretical work has shown that standard Transformers struggle with "non-star-free" regular languages, most notably the parity problem (determining if a string has an even or odd number of ones). This study investigates whether LTs inherit these practical limitations and if specific architectural extensions can bridge the gap.
Methods
The authors evaluate four primary architectural variations:
- Linear Transformers (LT): The base model utilizing linearized attention.
- DeltaNet: Replaces simple additive updates with a delta rule (an error-correction mechanism), allowing the model to effectively "overwrite" or "forget" information.
- Recurrent Delta: Adds a proper recurrent connection by feeding the model's previous output back into the next step.
- Self-Referential Weight Matrix (SRWM): An extension where the weight matrix computes its own updates, enabling the model to modify its own "program" dynamically.
These models were tested on a suite of formal language recognition tasks, including Regular Languages (Parity, $(aa)^*$, $(abab)^*$), Counter Languages ($a^n b^n$, $a^n b^n c^n$), and Dyck Languages (Dyck-1, Reset Dyck-1). Models were trained on shorter sequences (Bin0) and tested on longer, unseen sequences (Bin1) to measure true generalization.
Key Results and Insights
The experimental results demonstrate a clear hierarchy of computational power among the models. Standard LTs and Transformers failed on all regular language tasks, often scoring near 0% on generalization (Bin1). In contrast, the Recurrent Delta and SRWM models achieved 100% accuracy across almost all tasks, including the challenging parity problem and context-sensitive languages.
The Importance of the "Forget" Mechanism
The "delta rule" proved essential for tasks like Reset Dyck-1. Without it, the model's memory accumulates values indefinitely, making it impossible to "reset" the internal state upon specific triggers. While DeltaNet improved performance on these tasks, it still struggled with Parity, which required the addition of recurrence or self-reference to solve.
Summary of Findings
- Inherited Weakness: Theoretical limitations of standard Transformers transfer directly to basic Linear Transformers.
- Recurrence is Key: Adding recurrence or self-reference allows models to solve the parity problem with 100% accuracy.
- State Complexity: Single-layer LTs maintain a state complexity of $O(\log n)$, aligning them with LSTMs and standard self-attention.
Conclusion
This research highlights that while basic Linear Transformers share the computational blind spots of their standard counterparts, architectural extensions like recurrence and self-referential weight updates significantly expand their capabilities. These models can successfully solve complex formal languages that standard Transformers cannot. Future work may involve applying these architectures to natural language tasks and exploring the extraction of symbolic rules from self-modifying neural networks.
Summary updated