ESSLLI 2024

Expressivity of Transformers: Logic, Circuits, and Formal Languages

A major advancement in language modeling is the use of the transformer architecture. But what problems can transformers solve, what problems can they not solve, and how can we prove it? This course examines the expressivity of transformers through the lens of computability and complexity theory. We situate transformers within the landscape of automata, boolean circuits, and formal logics. We discuss what is currently known about transformers’ capabilities and limitations, address practical implications for NLP, and identify directions for future work. Participants gain a comprehensive understanding of transformers’ expressive power.