TL;DR
This paper explores the computational capabilities of Linear Transformers (LTs), a variant of the popular Transformer architecture. The authors demonstrate that LTs, when extended with recurrence or self-reference, can overcome limitations of standard Transformers and achieve powerful language recognition capabilities, rivaling those of more complex RNNs. This work bridges the gap between the theoretical power of RNNs and the practical advantages of Transformers.
What Problem Does This Paper Address?
The field of neural sequence processing is dominated by two major architectural families: Recurrent Neural Networks (RNNs) and Transformers. While RNNs are theoretically Turing-complete and possess a fixed-size state, making them well-suited for sequential tasks, they often struggle with long-range dependencies and parallelization. Transformers, on the other hand, excel at capturing long-range dependencies and are highly parallelizable, but their computational power in certain formal language recognition tasks has been shown to be limited.
This paper investigates a specific type of Transformer called Linear Transformers (LTs), which are known to be equivalent to RNN-like sequence processors with a fixed-size state. The core problem addressed is understanding the practical computational power of these LTs, particularly in formal language recognition, and whether they can overcome the limitations of standard Transformers. The authors also explore extensions to LTs that imbue them with recurrent or self-referential capabilities, aiming to enhance their expressive power.
Methods
The paper focuses on Linear Transformers (LTs), also known as Fast Weight Programmers (FWPs). LTs are presented as an auto-regressive Transformer with linearized attention. A key aspect is their equivalence to RNN-like sequence processors with a fixed-size state, bridging the gap between RNNs and Transformers.
The authors build upon existing theoretical results for standard Transformers and show that many of these transfer directly to LTs. They then investigate two specific extensions to LTs:
- Recurrence: This extension involves feeding back the output from the previous time step as an input to the current step, similar to traditional recurrent connections.
- Self-Reference: This extension, inspired by recursive self-improvement, allows the network to modify its own weight-generating mechanism.
These extensions are implemented and evaluated on formal language recognition tasks.
Datasets
The paper uses established datasets for formal language recognition tasks. These include:
- Non-Star-Free Regular Languages: Parity, (aa)*, and (abab)*.
- Counter Languages: aⁿbⁿ, aⁿbⁿcⁿ, Shuffle-2, and reset Dyck-1.
The datasets are split into "Bin0" (sequences with lengths seen during training) and "Bin1" (longer sequences) to evaluate generalization. The authors note that they use the official (pre-generated) dataset from Bhattamishra et al. (2020a) for most tasks, except for reset Dyck-1, which they generate using their official public code.
Key Insights and Ideas
- LTs Inherit Transformer Limitations: Standard LTs, like Transformers, struggle with certain non-star-free regular languages, such as the parity task. This highlights that the "linearization" of attention doesn't automatically grant them the full power of Turing-complete RNNs.
- Recurrence and Self-Reference Unlock Power: The paper's most significant finding is that adding recurrent or self-referential mechanisms to LTs dramatically enhances their computational power. These extensions allow LTs to successfully learn and generalize on tasks where standard LTs and even Transformers fail.
- Bridging the Gap: LTs, especially with their extensions, offer a compelling middle ground. They retain the parallelizability and efficiency benefits of Transformers while gaining the expressive power traditionally associated with RNNs.
- Delta-Rule's Role: While the delta-rule alone doesn't solve parity-like tasks for LTs, it is shown to be crucial for recognizing languages like "reset Dyck-1," demonstrating its importance in specific contexts.
Key Results
The experimental results, summarized in Table 1 and Table 2, are striking:
- Parity and (aa)*: Standard LTs and Transformers fail on these tasks (e.g., Transformer accuracy of 47.1% on Parity Bin0). However, Recurrent Delta and SRWM (self-referential) extensions achieve 100% accuracy on both training (Bin0) and generalization (Bin1) sets.
- Counter Languages: All LT variants, including the base Linear Transformer, can learn representative counter languages that standard Transformers can learn.
- Reset Dyck-1: The delta-rule, when applied to LTs, enables them to recognize the "reset Dyck-1" language, which is challenging for standard self-attention networks due to a lack of memory rewriting mechanisms.
Limitations and Future Work
The authors acknowledge several limitations:
- Exhaustiveness: The study is not an exhaustive comparison of LT expressivity to standard Transformers, focusing on specific formal language tasks.
- Self-Reference Power: While recurrence's benefit is clear, the full power of self-reference requires further investigation.
- Comparison to Memory-Augmented RNNs: A comparison with memory-augmented RNNs (like Neural Turing Machines) is left for future work.
- Task Scope: The experiments are based on eight tasks from a previous study; future work should extend to more diverse tasks.
Future work directions include:
- Deeper theoretical analysis of self-reference.
- Connecting LTs and Self-Modifying Automata (SMAs).
- Extending experimental results to a wider range of tasks.
- Comparing LTs with memory-augmented RNNs.
Summary updated