mlsanityData to 14 Oct 2026

Fast attention mechanisms: a tale of parallelism

arXiv 2509.09001 ↗First posted 10 Sep 2025cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits their scalability. We introduce an efficient attention mechanism called Approximate Nearest Neighbor Attention (ANNA) with sub-quadratic time complexity. We prove that ANNA-transformers (1) retain the expressive power previously established for standard attention in terms of matching the capabilities of MPC algorithms, and (2) can solve key reasoning tasks such as Match2 and k-hop with near-optimal depth. Using the MPC framework, we further prove that constant-depth ANNA-transformers can simulate constant-depth low-rank transformers, thereby providing a unified way to reason about a broad class of efficient attention approximations.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 45 of its 71 references that are in the map. First posted on arXiv 10 Sep 2025.

Builds on

45 of 71 references.

References · 45

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Language Models are Few-Shot Learnerscited by 32,419
  3. 2023GPT-4 Technical Reportcited by 18,396
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  5. 2020Reformer: The Efficient Transformercited by 1,668
  6. 2020Rethinking Attention with Performerscited by 1,601
  7. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  8. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 471
  9. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  10. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  11. 2022Transformers Learn Shortcuts to Automatacited by 268
  12. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
33 more
  1. 2023Looped Transformers as Programmable Computerscited by 237
  2. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 216
  3. 2024Simple linear attention language models balance the recall-throughput tradeoffcited by 208
  4. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  5. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  6. 2024The Illusion of State in State-Space Modelscited by 187
  7. 2023Birth of a Transformer: A Memory Viewpointcited by 161
  8. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  9. 2022On The Computational Complexity of Self-Attentioncited by 139
  10. 2023Representational Strengths and Limitations of Transformerscited by 133
  11. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  12. 2015Practical and Optimal LSH for Angular Distancecited by 106
  13. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  14. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  15. 2023Fast Attention Requires Bounded Entriescited by 102
  16. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  17. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  18. 2024Transformers, parallel computation, and logarithmic depthcited by 79
  19. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 67
  20. 2018Stable Recurrent Modelscited by 66
  21. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 64
  22. 2024On Limitations of the Transformer Architecturecited by 63
  23. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  24. 2024Theoretical limitations of multi-layer Transformercited by 45
  25. 2023PolySketchFormer: Fast Transformers via Sketching Polynomial Kernelscited by 36
  26. 2024One-layer transformers fail to solve the induction heads taskcited by 32
  27. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  28. 2024Do Efficient Transformers Really Save Computation?cited by 20
  29. 2013Communication Steps for Parallel Query Processingcited by 11
  30. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9
  31. 2013Parallel Algorithms for Geometric Graph Problemscited by 5
  32. 2024Lower bounds on transformers with infinite precisioncited by 3
  33. 2019MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyondcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026On the Computational Hardness of Transformerscited by 0
  2. 2026Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensionscited by 0
  3. 2026Latest Exact Match Attentioncited by 0