Formal Foundations of Language Models: Expressive Power, Limitations, and Extensions

20 Nov 2026 10.00 AM - 11.00 AM S3.1-B1-03 (Executive Seminar Room 3) Jiaoda Li Postdoctoral Researcher, ETH Zurich Current Students, Industry/Academic Partners

Abstract

Transformers are the predominant architecture behind large language models, yet their capabilities and limitations remain only partially understood. This raises fundamental questions about their interpretability, reliability, and trustworthiness. In this talk, I will show how formal methods, particularly formal logic and formal language theory, can be used to characterize the expressive power of transformers. These characterizations allow us to reason precisely about which classes of tasks transformers can and cannot compute, and to identify settings in which we should expect them to succeed or fail. I will then discuss how this perspective can support faithful interpretation of trained language models, the construction of transformers that provably implement desired computations, and architectural modifications that overcome some of the limitations of standard transformers.

About the Speaker

Jiaoda Li is currently a postdoctoral researcher at ETH Zurich, working with Ryan Cotterell. He received both his PhD and master's degree from ETH Zurich, and his bachelor's degree from City University of Hong Kong. His research lies at the intersection of natural language processing and machine learning, with a focus on developing formal foundations for modern language models. In particular, he uses formal methods to analyse and interpret modern deep learning models, and to guide the development of new architectures and algorithms inspired by these formal perspectives.