TL;DR
This paper introduces FourierLearner-Transformers (FLTs), a novel architecture that efficiently integrates relative positional encodings (RPEs) into linear attention mechanisms. FLTs learn the spectral representation of RPEs, enabling them to handle diverse data types, including complex geometric structures, while maintaining linear complexity and achieving state-of-the-art performance across various tasks.
What Problem Does This Paper Address?
Transformers, while revolutionary, suffer from a quadratic complexity in their self-attention mechanism, limiting their scalability to long sequences. Efficient Transformer variants, like Performer, address this by using linear attention. However, these efficient models often struggle to incorporate Relative Positional Encodings (RPEs), which are crucial for capturing positional information and improving performance, especially for data with non-trivial topological structures (like 3D molecules). Existing methods for combining RPEs with linear attention either sacrifice efficiency, require strong assumptions about the RPE mask structure, or are not generalizable to complex data. This paper aims to bridge this gap by proposing a flexible and efficient framework that seamlessly integrates a wide range of RPEs into linear attention.
Methods
The core innovation is the FourierLearner-Transformer (FLT). FLTs leverage the idea that many RPE mechanisms can be represented as the Fourier Transform of a function. Instead of directly computing the RPE mask (which can be computationally expensive), FLTs learn its spectral representation using random Fourier features. This allows them to approximate the RPE mask implicitly.
Key aspects of the FLT method:
- Spectral Representation Learning: FLTs learn the Fourier Transform ($g$) of the RPE function ($f$), rather than $f$ itself. This spectral representation allows for efficient computation and integration with linear attention.
- Random Fourier Features: The method utilizes random Fourier features to approximate the spectral representation, enabling a low-rank decomposition of the RPE mask.
- Performer-Friendly Integration: The learned RPE approximation is designed to be compatible with Performer-like architectures, allowing for efficient linear attention computation.
- Generalizability: FLTs are designed to handle a broad spectrum of RPEs, including those for sequential data (like text) and, importantly, for geometric data embedded in higher-dimensional Euclidean spaces (like 3D molecular structures).
- Novel RPE Variants: The paper introduces "local RPEs," which allow for localized attention patterns, mimicking some of the inductive biases of traditional convolutional networks.
Datasets
The paper evaluates FLTs on several standard benchmarks:
- Language Modeling: WikiText-103
- Image Classification: ImageNet, Places365, FashionMNIST
- Molecular Property Prediction: Open Catalyst 2020 (OC20) dataset (specifically the IS2RE task)
- Learnable Optimizers: ImageNet classification and Rastrigin-type functions.
No new datasets were introduced.
Key Insights and Ideas
- The Fourier Transform as a Bridge: The paper elegantly demonstrates that the Fourier Transform provides a powerful mathematical bridge to connect complex RPE mechanisms with efficient linear attention. By learning the spectral representation, FLTs bypass the computational bottlenecks of explicit RPE mask computation.
- Unifying RPEs for Diverse Data: FLTs offer a unified framework for RPEs, extending beyond simple sequential data to handle complex geometric structures like 3D molecules. This is a significant step towards more versatile Transformer architectures.
- Implicit RPEs for Efficiency: The core idea of learning an implicit representation of the RPE mask through its spectral properties is key to achieving both efficiency and expressiveness.
- Learnable Inductive Biases: The introduction of "local RPEs" shows how FLTs can be used to inject specific inductive biases (like locality) into the attention mechanism, leading to improved performance.
- Parameter Efficiency: The learned RPE components add a negligible number of parameters, making FLTs highly parameter-efficient.
Key Results
- Language Modeling: FLTs achieve state-of-the-art perplexity scores on WikiText-103, outperforming strong baselines like Performer and log-linear Performer, while also demonstrating superior efficiency (lower forward time and peak memory). For example, FLT with local RPE achieved a 1.0 point accuracy improvement over the regular Performer.
- Image Classification: FLTs show consistent accuracy gains across ImageNet, Places365, and FashionMNIST, outperforming regular Performer and CosFormer. For instance, FLT provided a 2.3% accuracy improvement over the regular Performer on ImageNet.
- Molecular Property Prediction: FLTs are the first Transformer architectures to provide RPE-enhanced linear attention for 3D molecular data. They achieve better performance (lower MAE and higher EwT) than the regular Performer on the OC20 IS2RE task, demonstrating their ability to handle complex, non-Toeplitz RPE masks.
- Learnable Optimizers: FLTs show significant improvements when used as memory units in learnable optimizers, effectively capturing long-range dependencies.
- Efficiency: FLTs exhibit significantly better time and space complexity compared to baselines, scaling much better with input sequence length.
Limitations and Future Work
- Distribution Choice for Random Features: FLTs require specifying a probability distribution for sampling random features. While Gaussian distributions are used and shown to be effective, the theoretical analysis suggests that choosing a distribution that minimizes $c = |||g(x)|/p(x)||_\infty$ (e.g., $p(x) \propto |g(x)|$) could lead to even better approximation.
- Logarithmic Factor in Sample Complexity: The theoretical analysis shows a logarithmic dependency on sequence length ($L$) in sample complexity. While this is negligible compared to polynomial dependencies, it's a technical aspect that could be further explored.
- Future Work: The authors suggest that the learned RPE mechanism can be further explored for other tasks and architectures. The ability to inject inductive biases through learnable RPEs also opens avenues for designing specialized attention mechanisms for various domains. The paper also hints at the potential for FLTs to be applied to other areas beyond those tested, such as learnable optimizers.
Summary updated