mlsanityData to 7 Oct 2026

Overcoming a Theoretical Limitation of Self-Attention

arXiv 2202.12172 ↗First posted 24 Feb 2022cs.LG cs.CLcited by 110

Not on the map. Why?

Abstract (arXiv)

Although transformers are remarkably effective for many tasks, there are some surprisingly easy-looking regular languages that they struggle with. Hahn shows that for languages where acceptance depends on a single input symbol, a transformer's classification decisions become less and less confident (that is, with cross-entropy approaching 1 bit per string) as input strings get longer and longer. We examine this limitation using two languages: PARITY, the language of bit strings with an odd number of 1s, and FIRST, the language of bit strings starting with a 1. We demonstrate three ways of overcoming the limitation suggested by Hahn's lemma. First, we settle an open question by constructing a transformer that recognizes PARITY with perfect accuracy, and similarly for FIRST. Second, we use layer normalization to bring the cross-entropy of both models arbitrarily close to zero. Third, when transformers need to focus on a single position, as for FIRST, we find that they can fail to generalize to longer strings; we offer a simple remedy to this problem that also improves length generalization in machine translation.

Key facts. Cited by 110 papers in the map (data through 7 Oct 2026). Builds on 14 of its 21 references that are in the map. First posted on arXiv 24 Feb 2022.

Builds on

14 of 21 references.

References · 14

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  4. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  5. 2016Layer Normalizationcited by 5,579
  6. 2017Convolutional Sequence to Sequence Learningcited by 550
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  8. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  9. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  10. 2021Thinking Like Transformerscited by 182
  11. 2019Transformers without Tears: Improving the Normalization of Self-Attentioncited by 153
  12. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
2 more
  1. 2020Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descentcited by 40
  2. 2019Learning Internal Representations (COLT 1995)cited by 25

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 23; 2024: 33; 2025: 31; 2026: 20.

110 papers.

Sort:

By area:

  1. 2023Qwen Technical Reportcited by 3,273
  2. 2023A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questionscited by 1,582
  3. 2024Hallucination is Inevitable: An Innate Limitation of Large Language Modelscited by 329
  4. 2022Neural Networks and the Chomsky Hierarchycited by 214
  5. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  6. 2023Scaling Laws of RoPE-based Extrapolationcited by 124
  7. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  8. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  9. 2022State-of-the-art generalisation research in NLP: A taxonomy and reviewcited by 97
  10. 2025HalluLens: LLM Hallucination Benchmarkcited by 88
  11. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 74
  12. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
38 more
  1. 2023The Transient Nature of Emergent In-Context Learning in Transformerscited by 72
  2. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  3. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  4. 2025Test-time regression: a unifying framework for designing sequence models with associative memorycited by 63
  5. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  6. 2023TransNeXt: Robust Foveal Visual Perception for Vision Transformerscited by 61
  7. 2024MemFlow: Optical Flow Estimation and Prediction with Memorycited by 55
  8. 2024Knowledge Mechanisms in Large Language Models: A Survey and Perspectivecited by 50
  9. 2024MVSFormer++: Revealing the Devil in Transformer's Details for Multi-View Stereocited by 49
  10. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  11. 2024LongEmbed: Extending Embedding Models for Long Context Retrievalcited by 47
  12. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  13. 2024Length Generalization of Causal Transformers without Position Encodingcited by 46
  14. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  15. 2024Theoretical limitations of multi-layer Transformercited by 43
  16. 2024Softmax is not Enough (for Sharp Size Generalisation)cited by 42
  17. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 37
  18. 2024Transformers Can Represent n-gram Language Modelscited by 31
  19. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 29
  20. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  21. 2024ALR2: A Retrieve-then-Reason Framework for Long-context Question Answeringcited by 25
  22. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  23. 2024When Can Transformers Count to n?cited by 22
  24. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  25. 2024Extending LLMs' Context Window with 100 Samplescited by 20
  26. 2025AttentionRAG: Attention-Guided Context Pruning in Retrieval-Augmented Generationcited by 19
  27. 2023Pushdown Layers: Encoding Recursive Structure in Transformer Language Modelscited by 18
  28. 2024Superiority of Multi-Head Attention in In-Context Linear Regressioncited by 17
  29. 2024Selective Prompt Anchoring for Code Generationcited by 16
  30. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  31. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  32. 2023Transformer Working Memory Enables Regular Language Reasoning and Natural Language Length Extrapolationcited by 13
  33. 2023From Interpolation to Extrapolation: Complete Length Generalization for Arithmetic Transformerscited by 10
  34. 2025Unique Hard Attention: A Tale of Two Sidescited by 10
  35. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 10
  36. 2024LeMeViT: Efficient Vision Transformer with Learnable Meta Tokens for Remote Sensing Image Interpretationcited by 9
  37. 2024Rethinking Transformers in Solving POMDPscited by 9
  38. 2024Fundamental Limitations on Subquadratic Alternatives to Transformerscited by 9

50 most cited of 110 All 110 (JSON)