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 will situate transformers within the landscape of automata, boolean circuits, and formal logics. We will discuss what is currently known about transformers' capabilities and limitations, address the practical implications of these results for natural language processing, and identify some directions for future work. Participants will gain a comprehensive understanding of transformers' expressive power in terms of the problems they fundamentally can and cannot solve.
Organizers
David Chiang
University of Notre Dame
dchaing[æt]nd.edu
Jon Rawski
MIT/San Jose State University
jon.rawski[æt]sjsu.edu
Lena Strobl
Umeå University
lena.strobl[æt]umu.se
Andy Yang
University of Notre Dame
ayang4[æt]nd.edu
Course Schedule
Monday, July 29 - Friday, August 2 5.00pm - 6.30pm
Location: Aula Jean Monnet (i.e. the big auditorium)