ESSLLI 2024 course, Leuven
Expressivity of Transformers: Logic, Circuits, and Formal Languages
A five-day course on what transformer architectures can compute, what they cannot compute under different assumptions, and how formal tools help us prove it.
- Dates
- July 29 to August 2, 2024
- Time
- 5:00 to 6:30 pm
- Location
- Aula Jean Monnet, Leuven
- Organizers
- David Chiang (University of Notre Dame), Jon Rawski (MIT and San José State University), Lena Strobl (Umeå University), and Andy J Yang (University of Notre Dame)
Why formal expressivity?
Transformers are central to modern language modeling. But what problems can they solve, what problems can they not solve, and how can we prove it? This course examines transformer expressivity through the lens of computability and complexity theory. We situate transformers within the landscape of automata, Boolean circuits, and formal logics; survey known capabilities and limitations; connect theory to practical questions in NLP; and identify open directions for future work.
Lecture notes and slides
Course materials from the five-day ESSLLI course.