Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention

By Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Moo Fung, Yin Li, Vikas Singh. 2021

733 citations recorded by the source corpus.

Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences – a topic being actively studied in the community. To address this limitation, we propose Nyströmformer – a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with O(n) complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard self-attention. On longer sequence tasks in the Long Range Arena (LRA) benchmark, Nyströmformer performs favorably relative to other efficient self-attention methods. Our code is available at https://github.com/mlpen/Nystromformer.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Model Architectures, Efficiency & Compression

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 Electrical and Electronic Engineering

In Model Architectures

In Efficiency & Compression

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, background): “com/google-research/long-range-arena), and the Nyströmformer reproduction [87].”
Perceiver: General Perception with Iterative Attention (2021, methodology): “…or otherwise simplifying the matrix multiplications used in QKV attention (Choromanski et al., 2021; Peng et al., 2021; Ki-taev et al., 2020; Xiong et al., 2021; Katharopoulos et al., 2020; Tay et al., 2021a), or by introducing bottlenecks into each module’s computation (Lee et al., 2019;…”
Efficient Transformers: A Survey (2020, background): “…et al., 2021) O ( N ) KR Long Short Transformers (Zhu et al., 2021) O ( kN ) FP + LR Poolingformer (Zhang et al., 2021) O ( N ) FP+M Nystr¨omformer (Xiong et al., 2021b) O ( kN ) M+DS Perceiver (Jaegle et al., 2021) O ( kN ) M+DS Clusterformer (Wang et al., 2020b) O ( N log N ) LP Luna (Ma et al.,…”
Transformers in Vision: A Survey (2021, methodology): “axial-attention [55, 83], low-rank projection attention [191, 207, 224], kernelizable attention [41, 156], and similarity-clustering-based methods [104, 192].”
SoundStorm: Efficient Parallel Audio Generation (2023, neutral): “…by at least three orthogonal approaches, or a combination thereof: i) efﬁcient attention mechanisms (Kitaev et al., 2020; Choromanski et al., 2021; Xiong et al., 2021; Hawthorne et al., 2022), ii) non-autoregressive, parallel decoding schemes (Gu et al., 2017; Ghazvininejad et al., 2019; Chang et…”
LambdaNetworks: Modeling Long-Range Interactions Without Attention (2021, background): “They are recently enjoying a resurgence of popularity with many works modifying the popular Transformer architecture for sequential processing applications (Katharopoulos et al., 2020; Wang et al., 2020b; Choromanski et al., 2020; Xiong et al., 2021).”
XCiT: Cross-Covariance Image Transformers (2021, methodology): “Other methods provide an approximation of the self-attention matrix which can be achieved by a projection across the token dimension [69], or through a factorization of the softmax-attention kernel [15, 37, 56, 77], which avoids explicit computation of the attention matrix.”
Point Transformer (2020, methodology): “As future work, we want to focus on improving the efficiency of the Transformer architecture by implementing recent advances for self-attention, such as [44], [45].”
Geometric Transformers for Protein Interface Contact Prediction (2021, methodology): “One limitation of the Geometric Transformer’s current design is the high computational complexity associated with its dot product self-attention mechanism, which we hope to overcome using efﬁcient alternatives to self-attention like that of the Nystr¨omformer (Xiong et al. (2021)).”
Transolver: A Fast Transformer Solver for PDEs on General Geometries (2024, methodology): “…their official code provided in the OpenReview and rerun it under the same training and hyperparameter-search strategy as other baselines and also tried different linear attention designs (Katharopoulos et al., 2020a; Kitaev et al., 2020; Xiong et al., 2021; Cao, 2021; Choromanski et al., 2021a).”
A Survey of Transformers (2021, methodology): “Nyströmformer [151] uses the Moore-Penrose pseudoinverse of M instead of the inverse so that the approximation can be made for cases where M is singular.”
Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers (2021, methodology): “In Table 3a, we compare our Orthoformer algorithm to alternative strategies: Nyströmformer [85] and Performer [15].”
Transformers in Medical Imaging: A Survey (2022, background): “Recently, numerous efforts have been made to reduce complexity, including sparse attention [85], linearization attention [86], low-rank attention [87], memory compression based approaches [88], and improved MHSA [89].”
FLatten Transformer: Vision Transformer using Focused Linear Attention (2023, methodology): “On the other hand, carefully designed kernel functions [7] or matrix decomposition approaches [26, 50] may incur additional computation overhead.”
TransMIL: Transformer based Correlated Multiple Instance Learning for Whole Slide Image Classication (2021, methodology): “To deal with the long instances sequence problem in WSIs, the softmax in TPT adopts the Nystrom Method proposed in [22].”
ActionFormer: Localizing Moments of Actions with Transformers (2022, background): “There has been several recent work on efficient self-attention [68,4,62,15].”
A Practical Survey on Faster and Lighter Transformers (2021, methodology): “The Nyströmformer [136] relies on the Nyströmmethod to generate a low-rank approximation of the Softmax matrix.”
Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models (2021, methodology): “We follow the implementation and experimental setting in [Xiong et al., 2021].”