--- title: "Formal Language Recognition by Hard Attention Transformers:" description: "The authors compare three variants that differ in how ties are resolved. 6 references, cited by 35 papers here." authors: ["Yiding Hao", "Dana Angluin", "Robert Frank"] year: 2022 venue: "Transactions of the Association for Computational Linguistics" source: "https://aclanthology.org/2022.tacl-1.46/" doi: "10.1162/tacl_a_00490" licence: "CC BY 4.0 (ACL Anthology)" licence_url: "https://creativecommons.org/licenses/by/4.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/hao-2022-formal-language-recognition-hard-attention/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/hao-2022-formal-language-recognition-hard-attention/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2022](https://md.research.elamur.ai/free/en/papers/2022/page/5/) / Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity # Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity **Authors:** Yiding Hao, [Dana Angluin](https://md.research.elamur.ai/free/en/authors/dana-angluin/) and [Robert Frank](https://md.research.elamur.ai/free/en/authors/robert-frank/) · **Year:** 2022 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2022](https://md.research.elamur.ai/free/en/venues/tacl/2022/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/) **Links:** [Publisher's page](https://aclanthology.org/2022.tacl-1.46/) · [PDF](https://aclanthology.org/2022.tacl-1.46.pdf) · [DOI 10.1162/tacl\_a\_00490](https://doi.org/10.1162/tacl_a_00490) · [OpenAlex](https://openalex.org/W4224874866) **Citations:** 27 citations (OpenAlex, 2026-10-14) · [35](https://md.research.elamur.ai/free/en/papers/hao-2022-formal-language-recognition-hard-attention/cited-by/) in our library, of the 149,439 papers whose bibliographies we read ## Summary This theoretical paper asks which formal languages Transformer encoders can accept when self-attention is idealized as hard attention, where each head looks only at the highest-scoring position or positions. The authors compare three variants that differ in how ties are resolved. GUHAT (from Hahn, 2020) and its more concrete restriction UHAT (from Yao et al., 2021) select a single winning position. AHAT instead averages over all tied maxima. No datasets or experiments are involved. The method is proof-based: networks are translated into families of Boolean circuits. The central theorem shows that any language accepted by a GUHAT, and therefore by a UHAT, lies in AC0, the class of constant-depth, polynomial-size circuits. The authors further prove that an AHAT can reproduce the behavior of any UHAT. MAJORITY and DYCK-1 are outside AC0 but have known AHAT constructions, so averaging attention is strictly more expressive than unique attention. The result unifies earlier impossibility findings. It also suggests that circuit complexity, rather than the Chomsky hierarchy, may be the natural lens for studying Transformer expressivity. ## Key points - **Established relations:** UHAT ⊆ GUHAT ⊆ AC0, and UHAT ⊆ AHAT. Unlike the unique-attention models, AHAT can recognize languages outside AC0. Merrill et al. (2022) separately bound AHAT by TC0. - **Languages GUHAT cannot recognize:** Using Furst et al. (1984), GUHAT recognizes neither PARITY, MAJORITY, nor EQUALITY. This subsumes Hahn's (2020) negative results. - **DYCK-k outside AC0:** For every k ≥ 1, DYCK-k is not in AC0. The proof reduces from EQUALITY: a length-n input is padded with n opening brackets on the left and n closing brackets on the right, giving a string of length 3n. - **Positive results:** AHAT handles MAJORITY (Pérez et al., 2019) and DYCK-1 (Bhattamishra et al., 2020). PALINDROMES is shown to be in GUHAT. - **Open questions:** - closure properties of the three classes; - the effect of positional encoding choices; - whether soft attention is strictly stronger than averaging hard attention. Yao et al. give a soft-attention DYCK-k construction that relies on layer normalization. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [Yale University](https://md.research.elamur.ai/free/en/universities/yale-university/) — University, New Haven, United States · 101 works · 13,302 citations 📚 Shelves (3): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 321 works ## Cite Cite as: Yiding Hao, Dana Angluin and Robert Frank. 2022. Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity. Transactions of the Association for Computational Linguistics. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @article{hao2022formal, title = {{Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity}}, author = {Yiding Hao, Dana Angluin and Robert Frank}, journal = {Transactions of the Association for Computational Linguistics}, year = {2022}, doi = {10.1162/tacl\_a\_00490}, url = {https://doi.org/10.1162/tacl_a_00490} } ``` - [← previous It is AI's Turn to Ask Humans a Question: Question-Answer Pair Generation for Children's Story Books](https://md.research.elamur.ai/free/en/papers/yao-2022-it-is-ai-s-turn/) - [next → NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://md.research.elamur.ai/free/en/papers/welleck-2022-naturalprover-grounded-mathematical-proof-generation/) - [↑ back to papers of 2022](https://md.research.elamur.ai/free/en/papers/2022/page/5/) ## References 6 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Sanjeev Arora and Boaz Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, United Kingdom. https://doi.org/10 .1017/CBO9780511804090 [find](https://scholar.google.com/scholar?q=Sanjeev+Arora+and+Boaz+Barak%2E+2009%2E+Computational+Complexity%3A+A+Modern+Approach%2E+Cambridge+University+Press%2C+Cambridge%2C+United+Kingdom%2E+https%3A%2F%2Fdoi%2Eorg%2F10+%2E1017%2FCBO9780511804090) 2. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. [On the ability and limitations of transformers to recognize formal languages](https://md.research.elamur.ai/free/en/papers/bhattamishra-2020-ability-limitations-transformers-recognize-formal/). In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7096–7116, Online. Association for Computational Linguistics… 3. Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Langua… [find](https://scholar.google.com/scholar?q=Shunyu+Yao%2C+Binghui+Peng%2C+Christos+Papadimitriou%2C+and+Karthik+Narasimhan%2E+2021%2E+Self%2Dattention+networks+can+process+bounded+hierarchical+languages%2E+In+Proceedings+of+the+59th+Annual+Meeting+of+the+Ass) 4. Merrick Furst, James B. Saxe, and Michael Sipser. 1984. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27. https://doi.org/10.1007/BF01744431 [↗](https://doi.org/10.1007/BF01744431) 5. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. 2020. [Are Transformers universal approximators of sequence-to-sequence functions?](https://md.research.elamur.ai/free/en/papers/yun-2019-transformers-universal-approximators-sequence-sequence/) In ICLR 2020 Conference Track, Online. OpenReview. 6. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational [find](https://scholar.google.com/scholar?q=Michael+Hahn%2E+2020%2E+Theoretical+limitations+of+self%2Dattention+in+neural+sequence+models%2E+Transactions+of+the+Association+for+Computational) *Updated 2 November 2026*