mlsanityData to 7 Oct 2026

Theoretical Limitations of Self-Attention in Neural Sequence Models

arXiv 1906.06755 ↗First posted 16 Jun 2019cs.CL cs.FL cs.LGcited by 286

Not on the map. Why?

Abstract (arXiv)

Transformers are emerging as the new workhorse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the computational capabilities of self-attention to process hierarchical structures are limited. In this work, we mathematically investigate the computational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limitations of the computational abilities of self-attention, finding that it cannot model periodic finite-state languages, nor hierarchical structure, unless the number of layers or heads increases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggesting that natural language can be approximated well with models that are too weak for the formal languages typically assumed in theoretical linguistics.

Key facts. Cited by 286 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 22; 2022: 22; 2023: 50; 2024: 57; 2025: 65; 2026: 70.

286 papers.

Sort:

By area:

  1. 2023A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questionscited by 1,582
  2. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  3. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  4. 2024Hallucination is Inevitable: An Innate Limitation of Large Language Modelscited by 329
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  6. 2022Transformers Learn Shortcuts to Automatacited by 260
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  8. 2022Neural Networks and the Chomsky Hierarchycited by 214
  9. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  11. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 184
  12. 2021Thinking Like Transformerscited by 182
38 more
  1. 2022A Review on Language Models as Knowledge Basescited by 156
  2. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  3. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  4. 2023Representational Strengths and Limitations of Transformerscited by 132
  5. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  6. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  7. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  8. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  9. 2024Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Taskscited by 104
  10. 2024Unlocking State-Tracking in Linear RNNs Through Negative Eigenvaluescited by 97
  11. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  12. 2023Language Model Behavior: A Comprehensive Surveycited by 92
  13. 2021Transformer Embeddings of Irregularly Spaced Events and Their Participantscited by 90
  14. 2025HalluLens: LLM Hallucination Benchmarkcited by 88
  15. 2024Transformers need glasses! Information over-squashing in language taskscited by 87
  16. 2021Going Beyond Linear Transformers with Recurrent Fast Weight Programmerscited by 84
  17. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 74
  18. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  19. 2023The Transient Nature of Emergent In-Context Learning in Transformerscited by 72
  20. 2025DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Productscited by 69
  21. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  22. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  23. 2023Transformers as Support Vector Machinescited by 67
  24. 2024SynCode: LLM Generation with Grammar Augmentationcited by 66
  25. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  26. 2024On Limitations of the Transformer Architecturecited by 63
  27. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  28. 2024RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrievalcited by 62
  29. 2023TransNeXt: Robust Foveal Visual Perception for Vision Transformerscited by 61
  30. 2023Grokking of Hierarchical Structure in Vanilla Transformerscited by 53
  31. 2021PnG BERT: Augmented BERT on Phonemes and Graphemes for Neural TTScited by 52
  32. 2025How Linguistics Learned to Stop Worrying and Love the Language Modelscited by 50
  33. 2021What Context Features Can Transformer Language Models Use?cited by 49
  34. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  35. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  36. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  37. 2022Autoregressive Structured Prediction with Language Modelscited by 43
  38. 2024Theoretical limitations of multi-layer Transformercited by 43

50 most cited of 286 All 286 (JSON)