Transformers have taken over the world of AI, but our mathematical understanding of why they work—and what they can’t do—is still catching up. Researchers have proposed various formal theories to describe Transformer capabilities, ranging from circuit complexity to formal logic. However, these theories often contradict each other.
In "Putting Transformer Theories to the Test," Altabaa et al. provide the first comprehensive "reality check" for these frameworks. By comparing theoretical predictions against the actual behavior of both small trained models and frontier LLMs, the authors identify which mathematical abstractions hold water and which ones fall short.
TL;DR
This paper benchmarks seven major formal theories of Transformer capabilities against empirical results across 19 diverse tasks. It finds that no single theory perfectly predicts performance, revealing that current models are often limited by learnability and inductive biases (like positional encodings) rather than just raw mathematical expressivity.
What Problem Does This Paper Address?
Theoretical researchers use different "lenses" to study Transformers. Some treat them as Boolean circuits ($\mathsf{AC}^0, \mathsf{TC}^0$), others as restricted programming languages (C-RASP), and others as communication protocols (MPC, BAPO).
Because these theories use different abstractions, they disagree on what is "easy" or "hard." For example, some theories predict that a Transformer cannot solve the "Majority" task (determining if more than half the bits in a string are 1s), while others say it can. This paper seeks to resolve these contradictions by asking: Which theory actually matches what we see in practice?
Methods
The authors mapped out seven prominent theories and translated their results into a unified prediction matrix for 19 computational tasks. They then conducted three types of empirical evaluations:
- In-distribution (ID) learning: Can a fixed-size Transformer learn the task as the input size $n$ grows?
- Length generalization (LG): Can a model trained on short sequences (e.g., length 32) succeed on much longer ones (up to length 256)?
- Pretrained LLMs: How do frontier models like GPT-4o and Gemini 1.5 Flash perform on these same tasks without specific training?
Datasets (Task Suite)
The authors used a suite of synthetic tasks designed to probe specific computational structures:
- Boolean Functions: All/Any, Majority, Parity.
- Retrieval: Indexing (finding a value at a specific position) and $k$-hop induction.
- Syntactic/Logic: Dyck languages (parenthesis matching) and Star-free languages.
- Arithmetic: Binary addition.
- Graphs: Edge existence and Reachability.
Key Insights and Ideas
- "Hard" is more certain than "Easy": Theories are much better at predicting when a Transformer will fail than when it will succeed. An "Easy" prediction usually means a handcrafted solution exists, but there is no guarantee that standard training (SGD) will ever find it.
- Soft Attention is a Superpower: Theories that assume "hard" attention (attending to only one token) predict that Transformers cannot solve Majority. In reality, Transformers use "soft" attention to aggregate information across the entire sequence, solving Majority with ease.
- The C-RASP Gap: C-RASP is a popular abstraction that models attention as uniform averaging. The authors proved (and empirically showed) that this fails to capture content-dependent retrieval. Tasks like $k$-hop induction are easy for real Transformers but exponentially hard for C-RASP-style models.
- Optimization vs. Expressivity: Transformers fail miserably at the "Parity" task. While some theories say this is because they aren't expressive enough, the authors argue it's actually an optimization barrier. The loss landscape for Parity is too "sharp" for SGD to navigate, a phenomenon better captured by Sensitivity theory.
Key Results
- C-RASP had the highest agreement with in-distribution learning (16/19 tasks), but its failure to model dynamic attention makes it a poor fit for retrieval-heavy tasks.
- Length Generalization is highly sensitive to positional encodings. No single encoding (RoPE, NoPE, Alibi, etc.) worked for all tasks. For instance, only "NoPE" (no positional encoding) allowed models to generalize on unbounded Dyck-1 tasks.
- LLMs vs. Small Models: Surprisingly, pretrained LLMs often performed worse than small, task-specific models on simple logic tasks like Majority as the input length increased, suggesting that massive scale and broad pretraining don't automatically confer robust algorithmic reasoning.
Limitations and Future Work
The study focused on single-pass performance, explicitly excluding "Chain-of-Thought" (CoT) or scratchpad reasoning, which are known to expand Transformer capabilities.
The authors conclude that a "Unified Theory of Transformers" must move beyond simple expressivity. Future theories need to account for:
- Soft, content-dependent attention (not just uniform averaging).
- Learnability: Why does SGD find some solutions but not others?
- Inductive Biases: How do architectural choices like positional encodings determine out-of-distribution success?
For a deeper dive into the specific assumptions of each theory, see the authors' breakdown below:
Summary updated