ESSLLI 2024
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.
DatesJuly 29 – August 2, 2024
Time5:00–6:30 pm
LocationAula Jean Monnet, Leuven
Course overview
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.
Organizers
David ChiangUniversity of Notre Dame
Jon RawskiMIT / San José State University
Lena StroblUmeå University
Andy J YangUniversity of Notre Dame
Materials
Lecture notes & slides
Course materials from the five-day ESSLLI course.
Back to organizing