The Underlying Logic of Language Models: The Underlying Logic of Language Models: Transformers and Formal Logics

Jiaoda Li, Ryan Cotterell, Franz Nowak, Anej Svete

International Conference on Machine Learning 2025 · Tutorial

This talk, presented at ICML 2025 by Jiaoda Li and collaborators, delves into the fundamental expressive power of **Transformer** architectures by establishing formal equivalences with fragments of mathematical logic. The presenters aim to bridge the gap between classical theoretical computer science concepts—such as formal languages and logic—and modern neural network architectures, specifically focusing on how Transformers process and represent information. This tutorial is particularly geared towards making complex theoretical results more accessible to the wider ML community, hoping to foster further growth in this interdisciplinary area.

AI review

This is a rigorous and technically serious contribution to the expressivity literature on Transformers, establishing a precise formal equivalence between decoder-only Transformers (constant precision, future masking, no positional encodings) and PFO2/LTL Past. The result is clean, the two-directional simulation is carefully argued, and the experimental validation in the length generalization regime is well-designed and honest about what the theory actually predicts. The work sits in a line descending from Hahn, Pérez, and the circuit complexity characterizations of Weiss et al., and it makes…