mlsanityData to 7 Oct 2026

How Can Self-Attention Networks Recognize Dyck-n Languages?

arXiv 2010.04303 ↗First posted 9 Oct 2020cs.CL cs.FL cs.LGcited by 51

Not on the map. Why?

Abstract (arXiv)

We focus on the recognition of Dyck-n (Dn) languages with self-attention (SA) networks, which has been deemed to be a difficult task for these networks. We compare the performance of two variants of SA, one with a starting symbol (SA^+) and one without (SA^-). Our results show that SA^+ is able to generalize to longer sequences and deeper dependencies. For D2, we find that SA^- completely breaks down on long sequences whereas the accuracy of SA^+ is 58.82%. We find attention maps learned by SA^+ to be amenable to interpretation and compatible with a stack-based language recognizer. Surprisingly, the performance of SA networks is at par with LSTMs, which provides evidence on the ability of SA to learn hierarchies without recursion.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 18; 2024: 15; 2025: 9; 2026: 3.

51 papers.

Sort:

By area:

  1. 2022Transformers Learn Shortcuts to Automatacited by 260
  2. 2022Neural Networks and the Chomsky Hierarchycited by 214
  3. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  4. 2021Thinking Like Transformerscited by 182
  5. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  6. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  7. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  8. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  9. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  10. 2024SynCode: LLM Generation with Grammar Augmentationcited by 66
  11. 2024On Limitations of the Transformer Architecturecited by 63
  12. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
38 more
  1. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 47
  2. 2024Theoretical limitations of multi-layer Transformercited by 43
  3. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  4. 2024Differentiation and Specialization of Attention Heads via the Refined Local Learning Coefficientcited by 39
  5. 2025Type-Constrained Code Generation with Language Modelscited by 32
  6. 2024Mission: Impossible Language Modelscited by 31
  7. 2023Failures Pave the Way: Enhancing Large Language Models through Tuning-free Rule Accumulationcited by 30
  8. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  9. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  10. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  11. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  12. 2023Interpretability Illusions in the Generalization of Simplified Modelscited by 24
  13. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  14. 2025Can Language Models Learn Typologically Implausible Languages?cited by 23
  15. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  16. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  17. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  18. 2024Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursioncited by 14
  19. 2025Constrained Decoding of Diffusion LLMs with Context-Free Grammarscited by 13
  20. 2025On the Query Complexity of Verifier-Assisted Language Generationcited by 10
  21. 2023Feature Interactions Reveal Linguistic Structure in Language Modelscited by 8
  22. 2025Can Interpretation Predict Behavior on Unseen Data?cited by 8
  23. 2023MLRegTest: A Benchmark for the Machine Learning of Regular Languagescited by 7
  24. 2024ALTA: Compiler-Based Analysis of Transformerscited by 7
  25. 2024Simulating Weighted Automata over Sequences and Trees with Transformerscited by 4
  26. 2024Validating Mechanistic Interpretations: An Axiomatic Approachcited by 4
  27. 2023State space models can express n-gram languagescited by 3
  28. 2024Stability Analysis of Various Symbolic Rule Extraction Methods from Recurrent Neural Networkcited by 3
  29. 2026Context-Free Recognition with Transformerscited by 3
  30. 2022Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergencecited by 2
  31. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  32. 2024A Transformer with Stack Attentioncited by 2
  33. 2025Circuits, Features, and Heuristics in Molecular Transformerscited by 2
  34. 2023Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formulacited by 1
  35. 2025Learning Model Successorscited by 0
  36. 2025Tracr-Injection: Distilling Algorithms into Pre-trained Language Modelscited by 0
  37. 2025Hardness of Learning Regular Languages in the Next Symbol Prediction Settingcited by 0
  38. 2026Language Re-generation: An investigation into information locality effects on reconstructioncited by 0

50 most cited of 51 All 51 (JSON)