mlsanityData to 7 Oct 2026

Self-attention Does Not Need O(n2) Memory

arXiv 2112.05682 ↗First posted 10 Dec 2021cs.LGcited by 152

Not on the map. Why?

Abstract (arXiv)

We present a very simple algorithm for attention that requires O(1) memory with respect to sequence length and an extension to self-attention that requires O(log n) memory. This is in contrast with the frequently stated belief that self-attention requires O(n2) memory. While the time complexity is still O(n2), device memory rather than compute capability is often the limiting factor on modern accelerators. Thus, reducing the memory requirements of attention allows processing of longer sequences than might otherwise be feasible. We provide a practical implementation for accelerators that requires O(√n) memory, is numerically stable, and is within a few percent of the runtime of the standard implementation of attention. We also demonstrate how to differentiate the function while remaining memory-efficient. For sequence length 16384, the memory overhead of self-attention is reduced by 59X for inference and by 32X for differentiation.

Key facts. Cited by 152 papers in the map (data through 7 Oct 2026). Builds on 15 of its 22 references that are in the map. First posted on arXiv 10 Dec 2021.

Builds on

15 of 22 references.

References · 15

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  4. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  5. 2020Reformer: The Efficient Transformercited by 1,658
  6. 2020Rethinking Attention with Performerscited by 1,584
  7. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  8. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  9. 2016Training Deep Nets with Sublinear Memory Costcited by 825
  10. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  11. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 469
  12. 2018Efficient Attention: Attention with Linear Complexitiescited by 366
3 more
  1. 2019Blockwise Self-Attention for Long Document Understandingcited by 158
  2. 2021Luna: Linear Unified Nested Attentioncited by 96
  3. 2021Combiner: Full Attention Transformer with Sparse Computation Costcited by 64

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 41; 2024: 48; 2025: 33; 2026: 24.

152 papers.

Sort:

By area:

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  3. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  4. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  5. 2023RWKV: Reinventing RNNs for the Transformer Eracited by 814
  6. 2023Baichuan 2: Open Large-scale Language Modelscited by 664
  7. 2023A Comprehensive Overview of Large Language Modelscited by 639
  8. 2023LightGlue: Local Feature Matching at Light Speedcited by 583
  9. 2023The Falcon Series of Open Language Modelscited by 526
  10. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Servecited by 507
  11. 2022Hungry Hungry Hippos: Towards Language Modeling with State Space Modelscited by 495
  12. 2023Ring Attention with Blockwise Transformers for Near-Infinite Contextcited by 448
38 more
  1. 2024mGTE: Generalized Long-Context Text Representation and Reranking Models for Multilingual Text Retrievalcited by 233
  2. 2023Patch n' Pack: NaViT, a Vision Transformer for any Aspect Ratio and Resolutioncited by 226
  3. 2024World Model on Million-Length Video And Language With Blockwise RingAttentioncited by 196
  4. 2023SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefillscited by 187
  5. 2024Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendationscited by 184
  6. 2024Flex Attention: A Programming Model for Generating Optimized Attention Kernelscited by 180
  7. 2024From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Modelscited by 136
  8. 2023ONE-PEACE: Exploring One General Representation Model Toward Unlimited Modalitiescited by 117
  9. 2023Towards Efficient Generative Large Language Model Serving: A Survey from Algorithms to Systemscited by 101
  10. 2023Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Surveycited by 71
  11. 2024Hydragen: High-Throughput LLM Inference with Shared Prefixescited by 71
  12. 2024Tracking Meets LoRA: Faster Training, Larger Model, Stronger Performancecited by 70
  13. 2022General-purpose, long-context autoregressive modeling with Perceiver ARcited by 60
  14. 2023SiLK -- Simple Learned Keypointscited by 54
  15. 2023Striped Attention: Faster Ring Attention for Causal Transformerscited by 52
  16. 2023Geometric Algebra Transformercited by 46
  17. 2024Post-Training Sparse Attention with Double Sparsitycited by 45
  18. 2023Boosting Latent Diffusion with Flow Matchingcited by 44
  19. 2023Replacing softmax with ReLU in Vision Transformerscited by 43
  20. 2024CATS: Contextually-Aware Thresholding for Sparsity in Large Language Modelscited by 41
  21. 2024Cut Your Losses in Large-Vocabulary Language Modelscited by 35
  22. 2025Scaling Laws for Forgetting during Finetuning with Pretraining Data Injectioncited by 35
  23. 2023MosaicBERT: A Bidirectional Encoder Optimized for Fast Pretrainingcited by 33
  24. 2025PaTH Attention: Position Encoding via Accumulating Householder Transformationscited by 32
  25. 2022GACT: Activation Compressed Training for Generic Network Architecturescited by 31
  26. 2024BatchLLM: Optimizing Large Batched LLM Inference with Global Prefix Sharing and Throughput-oriented Token Batchingcited by 31
  27. 2025ConTextTab: A Semantics-Aware Tabular In-Context Learnercited by 31
  28. 2023Scalable, Detailed and Mask-Free Universal Photometric Stereocited by 30
  29. 2023DISTFLASHATTN: Distributed Memory-efficient Attention for Long-context LLMs Trainingcited by 28
  30. 2023On Efficient Training of Large-Scale Deep Learning Models: A Literature Reviewcited by 26
  31. 2023LORD: Low Rank Decomposition Of Monolingual Code LLMs For One-Shot Compressioncited by 26
  32. 2023Transformer-VQ: Linear-Time Transformers via Vector Quantizationcited by 26
  33. 2023Efficient Attention via Control Variatescited by 23
  34. 2023Unsupervised 3D out-of-distribution detection with latent diffusion modelscited by 22
  35. 2023FABRIC: Personalizing Diffusion Models with Iterative Feedbackcited by 19
  36. 2025HMAR: Efficient Hierarchical Masked Auto-Regressive Image Generationcited by 19
  37. 2024FlashMask: Efficient and Rich Mask Extension of FlashAttentioncited by 18
  38. 2024Token Cropr: Faster ViTs for Quite a Few Taskscited by 18

50 most cited of 152 All 152 (JSON)