AI3 Seminar

Monday, August 31, 2026
12:30 PM
New Computer Science Bldg 120

What Transformers Can and Can’t Do

David Chiang

Associate Professor, Computer Science and Engineering, University of Notre Dame

Abstract: Neural networks are advancing the state of the art in many areas of artificial intelligence, but in many respects remain poorly understood. At a time when new abilities as well as new limitations of neural networks are continually coming to light, a clear understanding of what they can and cannot do is more needed than ever. The theoretical study of transformers, the dominant neural network for sequences, is just beginning, and we have helped to make this into a fruitful and fast-growing area of research.
Our approach is to relate transformers to mathematical formalisms for describing formal languages, like automata, circuits, and especially logics. The picture that is emerging is that the expressivity of transformers is highly dependent on one’s assumptions, but in any case they do not fit neatly into the well-known Chomsky hierarchy. The complexity classes that are more suitable for transformers come from the subregular hierarchy, circuit complexity, and descriptive complexity.
I will give a survey of this new subfield, focusing on recent results and some open questions. It will include joint work with my student Andy Yang and other collaborators.

Short bio: David Chiang (PhD, University of Pennsylvania, 2004) is an associate professor in the Department of Computer Science and Engineering at the University of Notre Dame. His research is on computational models for learning human languages, particularly on connections between formal language theory and natural language, and on speech and language processing for low-resource, endangered, and historical languages. He is the recipient of best paper awards at ACL 2005 and NAACL HLT 2009, and a social impact award and outstanding paper award at ACL 2024. He has received research grants from DARPA, NSF, Google, and Amazon, has served on the executive board of NAACL and the editorial board of Computational Linguistics and JAIR, and is currently on the editorial board of Transactions of the ACL. For more information about him, please visit: https://academicweb.nd.edu/~dchiang/