Comparison of different Unique hard attention transformer models by the formal languages they can recognize
Not on the map. Why?
Abstract (arXiv)
This note is a survey of various results on the capabilities of unique hard attention transformers encoders (UHATs) to recognize formal languages. We distinguish between masked vs. non-masked, finite vs. infinite image and general vs. bilinear attention score functions. We recall some relations between these models, as well as a lower bound in terms of first-order logic and an upper bound in terms of circuit complexity.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 7 of its 11 references that are in the map. First posted on arXiv 3 Jun 2025.
Builds on
7 of 11 references.
References · 7
- 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
- 2021Thinking Like Transformerscited by 184
- 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
- 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
- 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
- 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
- 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
Built on by
Not cited yet.