{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,26]],"date-time":"2026-07-26T03:13:56Z","timestamp":1785035636236,"version":"3.55.0"},"reference-count":58,"publisher":"MIT Press - Journals","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Transactions of the Association for Computational Linguistics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> Transformers are emerging as the new workhorse of NLP, showing great success across tasks. Unlike LSTMs, transformers process input sequences entirely through self-attention. Previous work has suggested that the computational capabilities of self-attention to process hierarchical structures are limited. In this work, we mathematically investigate the computational power of self-attention to model formal languages. Across both soft and hard attention, we show strong theoretical limitations of the computational abilities of self-attention, finding that it cannot model periodic finite-state languages, nor hierarchical structure, unless the number of layers or heads increases with input length. These limitations seem surprising given the practical success of self-attention and the prominent role assigned to hierarchical structure in linguistics, suggesting that natural language can be approximated well with models that are too weak for the formal languages typically assumed in theoretical linguistics. <\/jats:p>","DOI":"10.1162\/tacl_a_00306","type":"journal-article","created":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T14:54:52Z","timestamp":1585666492000},"page":"156-171","source":"Crossref","is-referenced-by-count":96,"title":["Theoretical Limitations of Self-Attention in Neural Sequence Models"],"prefix":"10.1162","volume":"8","author":[{"given":"Michael","family":"Hahn","sequence":"first","affiliation":[{"name":"Stanford University."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"issue":"3","key":"bib1","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/0022-0000(92)90014-A","volume":"44","author":"Barrington David A. Mix","year":"1992","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"bib2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1109\/72.279181","volume":"5","author":"Bengio Yoshua","year":"1994","journal-title":"IEEE Transactions on Neural Networks"},{"issue":"1","key":"bib3","volume":"16","author":"Bernardy Jean-Philippe","year":"2018","journal-title":"LiLT (Linguistic Issues in Language Technology)"},{"issue":"5","key":"bib4","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"Boppana Ravi B.","year":"1997","journal-title":"Information Processing Letters"},{"issue":"7","key":"bib5","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1016\/j.neucom.2007.05.006","volume":"71","author":"Bo Cartling","year":"2008","journal-title":"Neurocomputing"},{"key":"bib6","doi-asserted-by":"crossref","first-page":"76","DOI":"10.18653\/v1\/P18-1008","volume-title":"Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Chen Mia Xu","year":"2018"},{"key":"bib7","doi-asserted-by":"crossref","first-page":"551","DOI":"10.18653\/v1\/D16-1053","volume-title":"Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing","author":"Cheng Jianpeng","year":"2016"},{"key":"bib8","author":"Child Rewon","year":"2019","journal-title":"arXiv preprint arXiv: 1904.10509v1"},{"key":"bib9","doi-asserted-by":"crossref","DOI":"10.1515\/9783112316009","volume-title":"Syntactic Structures","author":"Chomsky Noam","year":"1957"},{"key":"bib10","first-page":"118","volume-title":"Studies in Logic and the Foundations of Mathematics","volume":"35","author":"Chomsky Noam","year":"1963"},{"key":"bib11","volume-title":"Proceedings of BlackboxNLP 2019","author":"Clark Kevin","year":"2019"},{"key":"bib12","first-page":"2978","volume-title":"Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-August 2, 2019, Volume 1: Long Papers","author":"Dai Zihang","year":"2019"},{"key":"bib13","author":"Palma Giacomo De","year":"2018","journal-title":"arXiv preprint arXiv:1812.10156v2"},{"key":"bib14","volume-title":"International Conference on Learning Representations","author":"Dehghani Mostafa","year":"2019"},{"key":"bib15","first-page":"4171","volume-title":"Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)","author":"Devlin Jacob","year":"2019"},{"issue":"12","key":"bib16","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1016\/j.tics.2015.09.008","volume":"19","author":"Everaert Martin B. H.","year":"2015","journal-title":"Trends in Cognitive Sciences"},{"issue":"1","key":"bib17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"Furst Merrick","year":"1984","journal-title":"Mathematical Systems Theory"},{"issue":"6","key":"bib18","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1109\/72.963769","volume":"12","author":"Gers Felix A.","year":"2001","journal-title":"IEEE Transactions on Neural Networks"},{"issue":"3","key":"bib19","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1080\/016909699386293","volume":"14","author":"Gibson Edward","year":"1999","journal-title":"Language and Cognitive Processes"},{"key":"bib20","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/2840728.2840738","volume-title":"Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science","author":"Gopalan Parikshit","year":"2016"},{"issue":"1","key":"bib21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1080\/09540090500317291","volume":"18","author":"Gr\u00fcning Andr\u00e9","year":"2006","journal-title":"Connection Science"},{"key":"bib22","first-page":"1195","volume-title":"Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)","author":"Gulordava Kristina","year":"2018"},{"key":"bib23","first-page":"1198","volume-title":"Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)","author":"Hao Jie","year":"2019"},{"issue":"2","key":"bib24","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1006\/inco.1994.1008","volume":"108","author":"Hastad Johan","year":"1994","journal-title":"Information and Computation"},{"key":"bib25","doi-asserted-by":"crossref","first-page":"1520","DOI":"10.18653\/v1\/P19-1147","volume-title":"Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics","author":"Hsieh Yu-Lun","year":"2019"},{"key":"bib26","first-page":"179","volume-title":"Australian Joint Conference on Artificial Intelligence","author":"Kalinke Yvonne","year":"1998"},{"issue":"1","key":"bib27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/09540091.2011.641939","volume":"24","author":"Kirov Christo","year":"2012","journal-title":"Connection Science"},{"key":"bib28","author":"Korsky Samuel A.","year":"2019","journal-title":"arXiv preprint arXiv:1906.06349v2"},{"key":"bib29","doi-asserted-by":"crossref","first-page":"1426","DOI":"10.18653\/v1\/P18-1132","volume-title":"Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)","author":"Kuncoro Adhiguna","year":"2018"},{"issue":"3","key":"bib30","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1207\/s15516709cog0000_25","volume":"29","author":"Lewis Richard L.","year":"2005","journal-title":"Cognitive Science"},{"key":"bib31","first-page":"241","volume-title":"Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP","author":"Lin Yongjie","year":"2019"},{"key":"bib32","volume-title":"International Conference on Learning Representations","author":"Lin Zhouhan","year":"2017"},{"key":"bib33","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00115"},{"key":"bib34","doi-asserted-by":"crossref","first-page":"1192","DOI":"10.18653\/v1\/D18-1151","volume-title":"Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing","author":"Marvin Rebecca","year":"2018"},{"key":"bib35","author":"Thomas McCoy R.","year":"2019","journal-title":"arXiv preprint arXiv:1911.02969v1"},{"key":"bib36","volume-title":"Counter-Free Automata (MIT Research Monograph No. 65)","author":"McNaughton Robert","year":"1971"},{"key":"bib37","first-page":"1","volume-title":"Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges","author":"Merrill William","year":"2019"},{"key":"bib38","first-page":"419","volume-title":"Handbook of Mathematical Psychology","author":"Miller George A.","year":"1963"},{"key":"bib39","volume-title":"International Conference on Learning Representations","author":"Miller John","year":"2019"},{"key":"bib40","volume-title":"Probability and Computing","author":"Mitzenmacher Michael","year":"2017","edition":"2"},{"key":"bib41","doi-asserted-by":"crossref","first-page":"2249","DOI":"10.18653\/v1\/D16-1244","volume-title":"Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing","author":"Parikh Ankur","year":"2016"},{"key":"bib42","first-page":"121","author":"Parker Dan","year":"2017","journal-title":"Language Processing and Disorders"},{"key":"bib43","volume-title":"International Conference on Learning Representations","author":"Paulus Romain","year":"2018"},{"key":"bib44","volume-title":"International Conference on Learning Representations","author":"P\u00e9rez Jorge","year":"2019"},{"key":"bib45","doi-asserted-by":"crossref","first-page":"115","DOI":"10.18653\/v1\/W18-5414","volume-title":"Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP","author":"Sennhauser Luzi","year":"2018"},{"key":"bib46","volume-title":"Thirty-Second AAAI Conference on Artificial Intelligence","author":"Shen Tao","year":"2018"},{"key":"bib47","first-page":"4345","volume-title":"IJCAI\u201918 Proceedings of the 27th International Joint Conference on Artificial Intelligence","author":"Shen Tao","year":"2018"},{"key":"bib48","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/978-94-009-2727-8_4","volume-title":"Philosophy, Language, and Artificial Intelligence","author":"Shieber Stuart M.","year":"1985"},{"key":"bib49","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jcss.1995.1013","volume":"50","author":"Siegelman Hava","year":"1995","journal-title":"Journal of Computer and System Sciences"},{"key":"bib50","doi-asserted-by":"crossref","first-page":"232","DOI":"10.18653\/v1\/W18-5425","volume-title":"Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP","author":"Skachkova Natalia","year":"2018"},{"key":"bib51","first-page":"277","author":"Suzgun Mirac","year":"2019","journal-title":"Proceedings of the Society for Computation in Linguistics (SCiL)"},{"issue":"1","key":"bib52","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1111\/1468-0394.00126","volume":"17","author":"Tabor Whitney","year":"2000","journal-title":"Expert Systems"},{"key":"bib53","first-page":"4593","volume-title":"Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-August 2, 2019, Volume 1: Long Papers","author":"Tenney Ian","year":"2019"},{"key":"bib54","doi-asserted-by":"crossref","first-page":"4731","DOI":"10.18653\/v1\/D18-1503","volume-title":"Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing","author":"Ke Tran","year":"2018"},{"key":"bib55","first-page":"5998","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani Ashish","year":"2017"},{"key":"bib56","first-page":"5797","volume-title":"Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-August 2, 2019, Volume 1: Long Papers","author":"Voita Elena","year":"2019"},{"key":"bib57","doi-asserted-by":"crossref","first-page":"740","DOI":"10.18653\/v1\/P18-2117","volume-title":"Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)","author":"Weiss Gail","year":"2018"},{"key":"bib58","first-page":"3635","volume-title":"Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-August 2, 2019, Volume 1: Long Papers","author":"Yang Baosong","year":"2019"}],"container-title":["Transactions of the Association for Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/tacl_a_00306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:39:34Z","timestamp":1615585174000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/tacl\/article\/43545"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":58,"alternative-id":["10.1162\/tacl_a_00306"],"URL":"https:\/\/doi.org\/10.1162\/tacl_a_00306","relation":{},"ISSN":["2307-387X"],"issn-type":[{"value":"2307-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}