Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers

Krzysztof Marcin Choromanski, Shanda Li, Valerii Likhosherstov, Kumar Avinava Dubey, Shengjie Luo, Di He, Yiming Yang, Tamás Sarlós, Thomas Weingarten, Adrian Weller

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

Abstract

We propose a new class of linear Transformers called FourierLearner-Transformers (FLTs), which incorporate a wide range of relative positional encoding mechanisms (RPEs). These include regular RPE techniques applied for nongeometric data, as well as novel RPEs operating on the sequences of tokens embedded in higher-dimensional Euclidean spaces (e.g. point clouds). FLTs construct the optimal RPE mechanism implicitly by learning its spectral representation. As opposed to other architectures combining efficient low-rank linear attention with RPEs, FLTs remain practical in terms of their memory usage and do not require additional assumptions about the structure of the RPE-mask. FLTs allow also for applying certain structural inductive bias techniques to specify masking strategies, e.g. they provide a way to learn the so-called local RPEs introduced in this paper and providing accuracy gains as compared with several other linear Transformers for language modeling. We also thoroughly tested FLTs on other data modalities and tasks, such as: image classification and 3D molecular modeling. For 3D-data FLTs are, to the best of our knowledge, the first Transformers architectures providing RPE-enhanced linear attention.
BibTeX
@inproceedings{choromanski2024learning,
  author = {Krzysztof Marcin Choromanski and Shanda Li and Valerii Likhosherstov and Kumar Avinava Dubey and Shengjie Luo and Di He and Yiming Yang and Tamás Sarlós and Thomas Weingarten and Adrian Weller},
  title = {{Learning a Fourier Transform for Linear Relative Positional Encodings in Transformers}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=1nLUYlYLr9},
}
Figure