Random Feature Attention

By Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A. Smith, Lingpeng Kong. 2021

447 citations recorded by the source corpus.

Transformers are state-of-the-art models for a variety of sequence modeling tasks. At their core is an attention function which models pairwise interactions between the inputs at every timestep. While attention is powerful, it does not scale efficiently to long sequences due to its quadratic time and space complexity in the sequence length. We propose RFA, a linear time and space attention that uses random feature methods to approximate the softmax function, and explore its application in transformers. RFA can be used as a drop-in replacement for conventional softmax attention and offers a straightforward way of learning with recency bias through an optional gating mechanism. Experiments on language modeling and machine translation demonstrate that RFA achieves similar or better performance compared to strong transformer baselines. In the machine translation experiment, RFA decodes twice as fast as a vanilla transformer. Compared to existing efficient transformer variants, RFA is competitive in terms of both accuracy and efficiency on three long text classification datasets. Our analysis shows that RFA's efficiency gains are especially notable on long sequences, suggesting that RFA will be particularly useful in tasks that require working with large inputs, fast decoding speed, or low memory footprints.

Subfields: Artificial Intelligence, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Model Architectures

Citations in the corpus

SCROLLS: Standardized CompaRison Over Long Language Sequences (2022, methodology): “The language modeling community typically uses perplexity to measure how well models predict the next token, a practice that has been adopted by several works on efﬁcient transformer architectures (Roy et al., 2021; Choromanski et al., 2020; Tay et al., 2020a; Peng et al., 2021).”
Perceiver: General Perception with Iterative Attention (2021, background): “A number of scalable self-attention variants have also been proposed (Katharopoulos et al., 2020; Peng et al., 2021; Child et al., 2019; Tay et al., 2021; 2020; Bello, 2021), but they may be insufficient by themselves to achieve good performance on high-dimensional perceptual tasks (Tay et al.”
Efficient Transformers: A Survey (2020, background): “…Compressive Transformer (Rae et al., 2018) Routing Transformer (Roy et al., 2020) Funnel Transformer (Dai et al., 2020) Random Feature Attention (Peng et al., 2021) Long Short Transformer (Zhu et al., 2021) Poolingformer (Zhang et al., 2021) Nystromformer (Xionget al., 2019) Adaptive Sparse…”
Transformers in Vision: A Survey (2021, methodology): “Numerous methods have been proposed that make special design choices to perform self-attention more ‘eiciently’, for instance employing pooling/downsampling in self-attention [61, 209, 221], local window-based attention [138, 201], axial-attention [55, 83], low-rank projection attention [192, 208, 2”
FNet: Mixing Tokens with Fourier Transforms (2021, methodology): “…et al., 2020; Ainslie et al., 2020; Zaheer et al., 2020; Wang et al., 2020; Tay et al., 2020b,a; Kitaev et al., 2020; Roy et al., 2021; Vyas et al., 2020; Liu et al., 2018) or via linearization of the attention matrix (Katharopoulos et al., 2020; Choromanski et al., 2021; Peng et al., 2021).”
Luna: Linear Unified Nested Attention (2021, methodology): “One drawback of Luna causal attention, similar to the causal attention in Random Feature Attention (RFA) (Peng et al., 2021) and Linear Transformer (Katharopoulos et al.”
General-purpose, long-context autoregressive modeling with Perceiver AR (2022, methodology): “…and Combiner (Ren et al., 2021) – or by approximating this computation at lower cost – e.g. as in Linear Transformer (Katharopoulos et al., 2020), Lin-former (Wang et al., 2020), Reformer (Kitaev et al., 2020), Random-Feature Attention (Peng et al., 2021), and Per-former (Choromanski et al.).”
Long-Short Transformer: Efficient Transformers for Language and Vision (2021, methodology): “By comparison, Random Feature Attention [30] is slow at training due to the requirement for recurrence.”
Spike-driven Transformer (2023, methodology): “Removing the softmax in self-attention and re-arranging the computation order of Query, Key, and Value is the main way to achieve linear attention [59, 62, 23, 63, 64, 61, 65].”
Gated Delta Networks: Improving Mamba2 with Delta Rule (2024, unknown): “This recurrence structure appears in several other architectures including Gated RFA (Peng et al., 2021), xLSTM (Beck et al., 2024), and Gated RetNet (Sun et al., 2024b).”
Parallelizing Linear Transformers with the Delta Rule over Sequence Length (2024, unknown): “Many models make use of a kernel φ (e.g., [98, 79]) but we subsume them into the key/value vectors to reduce notational clutter. as Mamba [30] and gated linear attention Transformers [105, 116, 89, 77, 9] thus make use of cheap element-wise recurrence updates, in particular the Hadamard product,…”
Towards Incremental Transformers: An Empirical Analysis of Transformer Models for Incremental NLU (2021, background): “Second, we suspect that the chosen feature map in LTs to approximate the softmax attention is sub-optimal, and a further gating mechanism could yield a better performance (Peng et al., 2021).”
Visual Attention Methods in Deep Learning: An In-Depth Survey (2022, methodology): “RFA can be integrated into backbones easily to replace the normal softmax without increasing the number of parameters, only 0 .”
LongT5: Efficient Text-To-Text Transformer for Long Sequences (2021, unknown): “Another type of approaches is leveraging the low-rank approximation of the attention matrix, such as Lin-former (Wang et al., 2020), Performer (Choroman-ski et al., 2021), Random Feature Attention (Peng et al., 2021), and LUNA (Ma et al., 2021).”
VeRA: Vector-based Random Matrix Adaptation (2023, background): “In parallel to this, recent research has shown the surprising effectiveness of models utilizing random weights and projections (Peng et al., 2021; Ramanujan et al., 2020; Lu et al., 2022; Schrimpf et al., 2021; Frankle et al., 2021).”
On The Computational Complexity of Self-Attention (2022, methodology): “More recent works such as the Performer [11], Slim [30], or RFA [31] approximate the attention computation using random projections.”
cosFormer: Rethinking Softmax in Attention (2022, methodology): “…as the sparse attention matrix (Za-heer et al., 2020; Beltagy et al., 2020; Tay et al., 2020a; Kitaev et al., 2019; Child et al., 2019),low-rank representations (Wang et al., 2020) or kernel-based methods (Peng et al., 2020; Choromanski et al., 2020; Katharopoulos et al., 2020), among many others.”
Choose a Transformer: Fourier or Galerkin (2021, background): “The current prevailing approach to linearize the attention leverages the assumption of the existence of a feature map to approximate the softmax kernel [50, 19, 70].”