mlsanityData to 7 Oct 2026

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

arXiv 2102.03902 ↗First posted 7 Feb 2021cs.CL cs.LGcited by 468

Not on the map. Why?

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.

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

Builds on

34 of 65 references.

References · 34

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,266
  5. 2019BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehensioncited by 5,874
  6. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,854
  7. 2019DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lightercited by 4,243
  8. 2016SQuAD: 100,000+ Questions for Machine Comprehension of Textcited by 4,115
  9. 2020Longformer: The Long-Document Transformercited by 3,362
  10. 2019ALBERT: A Lite BERT for Self-supervised Learning of Language Representationscited by 2,772
  11. 2017A Broad-Coverage Challenge Corpus for Sentence Understanding through Inferencecited by 2,665
  12. 2018Deep contextualized word representationscited by 2,285
22 more
  1. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  2. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,830
  3. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  4. 2020Reformer: The Efficient Transformercited by 1,658
  5. 2020Rethinking Attention with Performerscited by 1,584
  6. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  7. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  8. 2015Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Bookscited by 1,041
  9. 2016Training Deep Nets with Sublinear Memory Costcited by 825
  10. 2019Are Sixteen Heads Really Better than One?cited by 803
  11. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  12. 2018Efficient Attention: Attention with Linear Complexitiescited by 366
  13. 2019Q8BERT: Quantized 8Bit BERTcited by 296
  14. 2018ListOps: A Diagnostic Dataset for Latent Tree Learningcited by 128
  15. 2020Fast Transformers with Clustered Attentioncited by 123
  16. 2019Large Memory Layers with Product Keyscited by 120
  17. 2018Learning long-range spatial dependencies with horizontal gated-recurrent unitscited by 98
  18. 2018Baseline Needs More Love: On Simple Word-Embedding-Based Models and Associated Pooling Mechanismscited by 53
  19. 2017Adaptive Sampled Softmax with Kernel Based Samplingcited by 38
  20. 2019Sampled Softmax with Random Fourier Featurescited by 33
  21. 2013Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Samplingcited by 21
  22. 2019Nystr"om landmark sampling and regularized Christoffel functionscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 48; 2022: 79; 2023: 87; 2024: 97; 2025: 80; 2026: 77.

468 papers.

Sort:

By area:

  1. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  2. 2022FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecastingcited by 1,200
  3. 2021Perceiver: General Perception with Iterative Attentioncited by 1,089
  4. 2022Simplified State Space Layers for Sequence Modelingcited by 776
  5. 2021Perceiver IO: A General Architecture for Structured Inputs & Outputscited by 616
  6. 2021TransMIL: Transformer based Correlated Multiple Instance Learning for Whole Slide Image Classificationcited by 549
  7. 2024FlashAttention-3: Fast and Accurate Attention with Asynchrony and Low-precisioncited by 507
  8. 2022XMem: Long-Term Video Object Segmentation with an Atkinson-Shiffrin Memory Modelcited by 436
  9. 2021A Survey of Transformerscited by 399
  10. 2021XCiT: Cross-Covariance Image Transformerscited by 335
  11. 2021Choose a Transformer: Fourier or Galerkincited by 333
  12. 2022ActionFormer: Localizing Moments of Actions with Transformerscited by 308
38 more
  1. 2025YOLOv12: Attention-Centric Real-Time Object Detectorscited by 300
  2. 2024Transolver: A Fast Transformer Solver for PDEs on General Geometriescited by 299
  3. 2022Transformers in Medical Imaging: A Surveycited by 245
  4. 2021Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformerscited by 237
  5. 2021Keeping Your Eye on the Ball: Trajectory Attention in Video Transformerscited by 224
  6. 2024MobileLLM: Optimizing Sub-billion Parameter Language Models for On-Device Use Casescited by 216
  7. 2022cosFormer: Rethinking Softmax in Attentioncited by 212
  8. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  9. 2023FLatten Transformer: Vision Transformer using Focused Linear Attentioncited by 170
  10. 2021TransGAN: Two Pure Transformers Can Make One Strong GAN, and That Can Scale Upcited by 162
  11. 2024Eagle and Finch: RWKV with Matrix-Valued States and Dynamic Recurrencecited by 155
  12. 2022FiLM: Frequency improved Legendre Memory Model for Long-term Time Series Forecastingcited by 147
  13. 2022On The Computational Complexity of Self-Attentioncited by 137
  14. 2022Liquid Structural State-Space Modelscited by 134
  15. 2021SOFT: Softmax-free Transformer with Linear Complexitycited by 128
  16. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  17. 2023Scalable Transformer for PDE Surrogate Modelingcited by 123
  18. 2024The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicrycited by 119
  19. 2022EdgeViTs: Competing Light-weight CNNs on Mobile Devices with Vision Transformerscited by 116
  20. 2022Cost Aggregation with 4D Convolutional Swin Transformer for Few-Shot Segmentationcited by 114
  21. 2023Retrieval meets Long Context Large Language Modelscited by 114
  22. 2023SoundStorm: Efficient Parallel Audio Generationcited by 111
  23. 2021LambdaNetworks: Modeling Long-Range Interactions Without Attentioncited by 107
  24. 2021Long-Short Transformer: Efficient Transformers for Language and Visioncited by 102
  25. 2024Demystify Mamba in Vision: A Linear Attention Perspectivecited by 101
  26. 2023Modeling Dense Multimodal Interactions Between Biological Pathways and Histology for Survival Predictioncited by 92
  27. 2023Agent Attention: On the Integration of Softmax and Linear Attentioncited by 90
  28. 2022Learning Operators with Coupled Attentioncited by 88
  29. 2022A graph-transformer for whole slide image classificationcited by 84
  30. 2022KERPLE: Kernelized Relative Positional Embedding for Length Extrapolationcited by 84
  31. 2021U-Net Transformer: Self and Cross Attention for Medical Image Segmentationcited by 81
  32. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 75
  33. 2021A Practical Survey on Faster and Lighter Transformerscited by 73
  34. 2023Cross-Modal Translation and Alignment for Survival Analysiscited by 70
  35. 2022Flowformer: Linearizing Transformers with Conservation Flowscited by 69
  36. 2024Feature Re-Embedding: Towards Foundation Model-Level Performance in Computational Pathologycited by 66
  37. 2021Closed-form Continuous-time Neural Modelscited by 65
  38. 2024Mamba-360: Survey of State Space Models as Transformer Alternative for Long Sequence Modelling: Methods, Applications, and Challengescited by 63

50 most cited of 468 All 468 (JSON)