Rethinking Attention with Performers

By Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter G. Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser and 3 more. 2020

2,365 citations recorded by the source corpus.

We introduce Performers, Transformer architectures which can estimate regular (softmax) full-rank-attention Transformers with provable accuracy, but using only linear (as opposed to quadratic) space and time complexity, without relying on any priors such as sparsity or low-rankness. To approximate softmax attention-kernels, Performers use a novel Fast Attention Via positive Orthogonal Random features approach (FAVOR+), which may be of independent interest for scalable kernel methods. FAVOR+ can be also used to efficiently model kernelizable attention mechanisms beyond softmax. This representational power is crucial to accurately compare softmax with other kernels for the first time on large-scale tasks, beyond the reach of regular Transformers, and investigate optimal attention-kernels. Performers are linear architectures fully compatible with regular Transformers and with strong theoretical guarantees: unbiased or nearly-unbiased estimation of the attention matrix, uniform convergence and low estimation variance. We tested Performers on a rich set of tasks stretching from pixel-prediction through text models to protein sequence modeling. We demonstrate competitive results with other examined efficient sparse and dense attention methods, showcasing effectiveness of the novel attention-learning paradigm leveraged by Performers.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

RoFormer: Enhanced Transformer with Rotary Position Embedding (2021, methodology): “4 Performer with RoPE Performer Choromanski et al. [2020] introduces an alternative attention mechanism, linear attention, which is designed to avoid quadratic computation cost that scales with input sequence length.”
FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “There are numerous approaches to overcome this bottleneck, including approximation with hashing (i.e., sparse) such as Reformer [53] and Smyrf [20] and with low-rank approximation such as Performer [13, 56].”
Landmark Attention: Random-Access Infinite Context Length for Transformers (2023, methodology): “Linformer [37] uses a low-rank approximation of the attention matrix while Performer [7] uses a non-softmax kernel to obtain a more efficient implementation.”
HTLM: Hyper-Text Pre-Training and Prompting of Language Models (2021, neutral): “Coupling this with the challenges of training transformers on very long sequence lengths (Choromanski et al., 2020; Wang et al., 2020; Beltagy et al., 2020), it was important to automatically convert web pages to a simpliﬁed form, which we call M inimal-HTML (MHTML), as deﬁned below.”
Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language (2022, methodology): “In the scenario of strict mem- ory requirements, we propose to leverage recently introduced techniques on linear attention (Choromanski et al. 2021b) combined with modern continuous associative memory (MCAM) models (Ramsauer et al. 2021).”
Swin Transformer: Hierarchical Vision Transformer using Shifted Windows (2021, methodology): “Compared to Performer [14], which is one of the fastest Transformer architectures (see [55]), the proposed shifted window based self-attention computation and the overall Swin Transformer architectures are slightly faster (see Table 5), while achieving +2.3% top-1 accuracy compared to Performer on I”
Sparse is Enough in Scaling Transformers (2021, neutral): “Sparse attention-based approaches have made the attention layer more efﬁcient, especially for long sequences, by incorporating additional combinatorial mechanisms, as in [40], or selecting a subset of tokens this layer attends to [31, 5, 19, 37, 15, 4] or other approaches [12].”
Generating Images with Sparse Representations (2021, background): “While memory-efﬁcient Transformer variants (Child et al., 2019; Kitaev et al., 2020; Choromanski et al., 2021; Dhari-wal et al., 2020; Zaheer et al., 2021; Roy et al., 2020) make long-sequence training more practical, care is still required to optimize model hyperparameters against available memory…”
Long Range Arena: A Benchmark for Efficient Transformers (2020, methodology): “Similar to speed, Performers and Linear Transformers are also relatively compact and are almost as compact as Linformers.”
Efficient Transformers: A Survey (2020, methodology): “…et al., 2020) O ( n ( k + m )) FP+M ETC (Ainslie et al., 2020) O ( N 2 g + NN g ) FP+M Synthesizer (Tay et al., 2020a) O ( N 2 ) LR+LP Performer (Choromanski et al., 2020a) O ( N ) KR Funnel Transformer (Dai et al., 2020) O ( N 2 ) FP+DS Linformer (Wang et al., 2020c) O ( N ) LR Linear…”
Pre-Trained Models: Past, Present and Future (2021, background): “Some works (Peng et al., 2021; Choromanski et al., 2021; Wang et al., 2020c; Katharopoulos et al., 2020) design low-rank kernels to theoretically approximate the original attention weights and result in linear complexity.”
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”