# Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention

arXiv: https://arxiv.org/abs/2102.03902 · HTML: https://mlsanity.com/paper/2102.03902/

## Key facts

- Cited by 471 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 65 references that are in the map.
- First posted on arXiv 7 Feb 2021.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension](https://mlsanity.com/paper/1910.13461/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [Q8BERT: Quantized 8Bit BERT](https://mlsanity.com/paper/1910.06188/) (2019)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [Large Memory Layers with Product Keys](https://mlsanity.com/paper/1907.05242/) (2019)
- [Fast Transformers with Clustered Attention](https://mlsanity.com/paper/2007.04825/) (2020)
- [Learning long-range spatial dependencies with horizontal gated-recurrent units](https://mlsanity.com/paper/1805.08315/) (2018)
- [Baseline Needs More Love: On Simple Word-Embedding-Based Models and Associated Pooling Mechanisms](https://mlsanity.com/paper/1805.09843/) (2018)

## Built on by (most cited first, 30 of 471)

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting](https://mlsanity.com/paper/2201.12740/) (2022)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [TransMIL: Transformer based Correlated Multiple Instance Learning for Whole Slide Image Classification](https://mlsanity.com/paper/2106.00908/) (2021)
- [FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precision](https://mlsanity.com/paper/2407.08608/) (2024)
- [XMem: Long-Term Video Object Segmentation with an Atkinson-Shiffrin Memory Model](https://mlsanity.com/paper/2207.07115/) (2022)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Choose a Transformer: Fourier or Galerkin](https://mlsanity.com/paper/2105.14995/) (2021)
- [XCiT: Cross-Covariance Image Transformers](https://mlsanity.com/paper/2106.09681/) (2021)
- [Transolver: A Fast Transformer Solver for PDEs on General Geometries](https://mlsanity.com/paper/2402.02366/) (2024)
- [ActionFormer: Localizing Moments of Actions with Transformers](https://mlsanity.com/paper/2202.07925/) (2022)
- [YOLOv12: Attention-Centric Real-Time Object Detectors](https://mlsanity.com/paper/2502.12524/) (2025)
- [Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers](https://mlsanity.com/paper/2111.13587/) (2021)
- [Transformers in Medical Imaging: A Survey](https://mlsanity.com/paper/2201.09873/) (2022)
- [Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers](https://mlsanity.com/paper/2106.05392/) (2021)
- [MobileLLM: Optimizing Sub-billion Parameter Language Models for On-Device Use Cases](https://mlsanity.com/paper/2402.14905/) (2024)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [FLatten Transformer: Vision Transformer using Focused Linear Attention](https://mlsanity.com/paper/2308.00442/) (2023)
- [TransGAN: Two Pure Transformers Can Make One Strong GAN, and That Can Scale Up](https://mlsanity.com/paper/2102.07074/) (2021)
- [Eagle and Finch: RWKV with Matrix-Valued States and Dynamic Recurrence](https://mlsanity.com/paper/2404.05892/) (2024)
- [FiLM: Frequency improved Legendre Memory Model for Long-term Time Series Forecasting](https://mlsanity.com/paper/2205.08897/) (2022)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Liquid Structural State-Space Models](https://mlsanity.com/paper/2209.12951/) (2022)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [SOFT: Softmax-free Transformer with Linear Complexity](https://mlsanity.com/paper/2110.11945/) (2021)
- [Scalable Transformer for PDE Surrogate Modeling](https://mlsanity.com/paper/2305.17560/) (2023)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)

## Abstract (arXiv)

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"omformer -- a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nystr"om method to approximate standard self-attention with O(n) complexity. The scalability of Nystr"omformer 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"omformer 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"omformer performs favorably relative to other efficient self-attention methods. Our code is available at https://github.com/mlpen/Nystromformer.