Elamur Research⌕
☰
home / papers / 2022 / Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity

Paper · 2022 · Yiding Hao, Dana Angluin and Robert Frank

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 UniversityNew Haven · United States95 works · 12,765 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksComputational Theory and Mathematics · 252 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. DOI 10.1162/tacl_a_00490

@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}
}

References

6 references, 1 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
  2. Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the ability and limitations of transformers to recognize formal languages. 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
  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 ↗
  5. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. 2020. Are Transformers universal approximators of sequence-to-sequence functions? In ICLR 2020 Conference Track, Online. OpenReview. find
  6. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational find

Updated

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hao-2022-formal-language-recognition-hard-attention/