mlsanityData to 7 Oct 2026

Self-Attention Networks Can Process Bounded Hierarchical Languages

arXiv 2105.11115 ↗First posted 24 May 2021cs.CL cs.AI cs.FLcited by 105

Not on the map. Why?

Abstract (arXiv)

Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as mathsfDyckk, the language consisting of well-nested parentheses of k types. This suggested that natural language can be approximated well with models that are too weak for formal languages, or that the role of hierarchy and recursion in natural language might be limited. We qualify this implication by proving that self-attention networks can process mathsfDyckk, D, the subset of mathsfDyckk with depth bounded by D, which arguably better captures the bounded hierarchical structure of natural language. Specifically, we construct a hard-attention network with D+1 layers and O(log k) memory size (per token per layer) that recognizes mathsfDyckk, D, and a soft-attention network with two layers and O(log k) memory size that generates mathsfDyckk, D. Experiments show that self-attention networks trained on mathsfDyckk, D generalize to longer inputs with near-perfect accuracy, and also verify the theoretical memory advantage of self-attention networks over recurrent networks.

Key facts. Cited by 105 papers in the map (data through 7 Oct 2026). Builds on 30 of its 57 references that are in the map. First posted on arXiv 24 May 2021.

Builds on

30 of 57 references.

References · 30

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2016Layer Normalizationcited by 5,579
  4. 2016Pointer Sentinel Mixture Modelscited by 2,992
  5. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,201
  6. 2018Self-Attention with Relative Position Representationscited by 1,112
  7. 2019BERT Rediscovers the Classical NLP Pipelinecited by 1,046
  8. 2018Universal Transformerscited by 613
  9. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  10. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  11. 2020Rethinking Positional Encoding in Language Pre-trainingcited by 197
  12. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
18 more
  1. 2019Open Sesame: Getting Inside BERT's Linguistic Knowledgecited by 119
  2. 2018The Best of Both Worlds: Combining Recent Advances in Neural Machine Translationcited by 101
  3. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  4. 2017DiSAN: Directional Self-Attention Network for RNN/CNN-Free Language Understandingcited by 71
  5. 2020A Formal Hierarchy of RNN Architecturescited by 61
  6. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  7. 2019Encoding word order in complex embeddingscited by 53
  8. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  9. 2020Fast and Accurate Neural CRF Constituency Parsingcited by 50
  10. 2018The Importance of Being Recurrent for Modeling Hierarchical Structurecited by 42
  11. 2019On the Computational Power of RNNscited by 35
  12. 2019Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languagescited by 31
  13. 2019Modeling Recurrence for Transformercited by 26
  14. 2019Establishing Strong Baselines for the New Decade: Sequence Tagging, Syntactic and Semantic Parsing with BERTcited by 19
  15. 2018Evaluating the Ability of LSTMs to Learn Context-Free Grammarscited by 16
  16. 2020On the Ability and Limitations of Transformers to Recognize Formal Languagescited by 12
  17. 2019Assessing the Ability of Self-Attention Networks to Learn Word Ordercited by 9
  18. 2018Unsupervised Grammar Induction with Depth-bounded PCFGcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 30; 2024: 31; 2025: 21; 2026: 15.

105 papers.

Sort:

By area:

  1. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  2. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  3. 2022Transformers Learn Shortcuts to Automatacited by 260
  4. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  5. 2021Thinking Like Transformerscited by 182
  6. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  7. 2023Representational Strengths and Limitations of Transformerscited by 132
  8. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  9. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  10. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  11. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  12. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
38 more
  1. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  2. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 74
  3. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  4. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  5. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  6. 2024On Limitations of the Transformer Architecturecited by 63
  7. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  8. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  9. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  10. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  11. 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 46
  12. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  13. 2024Theoretical limitations of multi-layer Transformercited by 43
  14. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  15. 2023Modeling rapid language learning by distilling Bayesian priors into artificial neural networkscited by 40
  16. 2023Learning Transformer Programscited by 40
  17. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  18. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  19. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 37
  20. 2024Transformers Can Represent n-gram Language Modelscited by 31
  21. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  22. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  23. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  24. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  25. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  26. 2023Interpretability Illusions in the Generalization of Simplified Modelscited by 24
  27. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  28. 2024Learned feature representations are biased by complexity, learning order, position, and morecited by 22
  29. 2024Provably learning a multi-head attention layercited by 21
  30. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
  31. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  32. 2024Do Efficient Transformers Really Save Computation?cited by 20
  33. 2023Pushdown Layers: Encoding Recursive Structure in Transformer Language Modelscited by 18
  34. 2023Can Transformers Learn to Solve Problems Recursively?cited by 17
  35. 2023Trainable Transformer in Transformercited by 17
  36. 2023Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patternscited by 17
  37. 2024Algorithmic Capabilities of Random Transformerscited by 17
  38. 2024Can Transformers Reason Logically? A Study in SAT Solvingcited by 16

50 most cited of 105 All 105 (JSON)