The practical payoff of this theory is a fast algorithm, which can decide whether or not a transformer will length generalize on any given regular language. Evaluation on >100 randomly sampled regular languages demonstrates the theory accurately predicts length generalization!
Our second main contribution is to use this decomposition theory to derive a polynomial time decision procedure for regular language membership in C-RASP. This is formalized using the Derived Category Theorem (Tilson 1987) -- which explains how to "divide" one monoid by another.
Previous work (@huangxt233 2025) suggests transformers length generalize whenever the task is expressible in C-RASP. However, C-RASP sits orthogonally to classical measures of regular language complexity, so understanding the regular languages of C-RASP requires new ideas.
A fundamental question one can ask about a model of computation is, what finite-state languages can it recognize?
Kleene invented regular expressions in the 1950s to characterize McCulloch-Pitts nerve nets. 75 years later, we ask the analogous question for transformers.
Which state-tracking problems can transformers length generalize on?
Transformers' performance on different finite-state tasks varies drastically, even when the tasks are structurally similar. Now, for the first time, we can precisely predict when length generalization occurs.
How long do training strings need to be in order for transformers to generalize at test-time to inputs of arbitrary length?
We answer this question in two different numerical precision regimes, using connections with Diophantine equations and linear temporal logic!
📣 FLaNN 2026 at Yale 🍮
Invited talks+posters (non-archival): expressivity, computation, and learning in neural nets/LLMs
Speakers: Pablo Barceló, David Chiang, Will Merrill, Naomi Saphra, Gail Weiss
Abstracts due Feb 12, 2026
Details: flann.cs.yale.edu/
Announcing the first Workshop on Formal Languages and Neural Networks (FLaNN) 🍮!
We invite the submission of abstracts for posters that discuss the formal expressivity, computational properties, and learning behavior of neural network models, including large language models.
For those stumbling on my page, here's a research update.
Earlier, Michaël Cadilhac, @davidweichiang, and I proved a depth hierarchy in C-RASP which aligns with learnability in transformers of a given depth.
Now with new theory on positional encodings and new experiments :)
