Formal Language Theory and Transformers

Speaker: Michaël Cadilhac
Post thumbnail

At the heart of the recent boom in AI lies a mathematical model known as transformers. They consist of many large matrices and nonlinear transformations, arranged in a fixed way, whose internal values and parameters are tweaked during the learning process. This leads to tantalizing natural questions: if I have a target formal language in mind, can these parameters be tweaked in any way in order to recognize this language? Is there a correlation between the number of parameters and the expressive power of the transformer? Does alternating more or less between linear and nonlinear transformations change the expressiveness?

In this talk, I’ll survey a few results pertaining to the expressive power of transformers, through the lense of formal language theory. I will focus on distilling the complex-looking cocktail of mathematical symbols of the definition of transformers into more familiar objects: circuit classes and temporal logics. From there, I will reword the aforementioned tantalizing questions into formal language questions, and provide crisp answers. As is common in AI research, and to circle back to the muddy reality of the practical world, I will, time allowing, present experiments confirming these results.

Main sources:

  • Knee-Deep in C-RASP: A Transformer Depth Hierarchy. Andy Yang, Michaël Cadilhac, David Chiang, 2025, NeurIPS.
  • Transformers are Inherently Succinct. Pascal Bergsträßer, Ryan Cotterell, Anthony Widjaja Lin, 2026, ICLR.
  • Algebraic Decomposition Theory for Transformer Length Generalization. Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs, Charles Paperman, Howard Straubing, Michael Hahn, 2026, COLM.