The Role of Logic and Automata in Understanding Transformers
Not on the map. Why?
Abstract (arXiv)
The advent of transformers has in recent years led to powerful and revolutionary Large Language Models (LLMs). Despite this, our understanding on the capability of transformers is still meager. In this invited contribution, we recount the rapid progress in the last few years to the question of what transformers can do. In particular, we will see the integral role of logic and automata (also with some help from circuit complexity) in answering this question. We also mention several open problems at the intersection of logic, automata, verification and transformers.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 12 of its 24 references that are in the map. First posted on arXiv 28 Sep 2025.
Builds on
12 of 24 references.
References · 12
- 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
- 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
- 2023What Formal Languages Can Transformers Express? A Surveycited by 124
- 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
- 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
- 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
- 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
- 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
- 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
- 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
- 2024Simulating Hard Attention Using Soft Attentioncited by 15
- 2025The Counting Power of Transformerscited by 9
Built on by
Citing papers per year: 2026: 1.
1 paper.