🤖 machine learning

Putting Transformer Theories to the Test

This paper evaluates seven formal theories of transformer capabilities by mapping their predictions against a suite of tasks and experimental results, finding that no single theory fully explains observed behaviors and highlighting the need for a new framework that incorporates soft attention, dynamic content-dependent retrieval, and learnability.

Original authors: Awni Altabaa, Tobias Schnabel, Kiran Tomlinson

Published 2026-10-26✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Awni Altabaa, Tobias Schnabel, Kiran Tomlinson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of artificial intelligence, a specific type of computer program called a transformer has become the engine behind the most advanced language systems, such as the technology used in AI chatbots like ChatGPT. These programs do not think like humans, but they are remarkably good at spotting patterns in text, predicting the next word in a sentence, and solving complex puzzles. Because they work so well in practice, scientists have spent years trying to build mathematical maps of exactly what these programs can and cannot do. These maps, or theories, are like different sets of blueprints. Some blueprints suggest the programs are limited to simple tasks, while others claim they can handle almost anything. The problem is that these blueprints often contradict each other. One might say a specific job is too hard for the machine, while another insists it is easy. Without a way to test these competing maps against reality, it is difficult to know which one is actually correct or how to build better machines in the future.

A team of researchers set out to settle this debate by treating these theories like scientific hypotheses that must be tested in the real world. They gathered seven of the most prominent theories currently used to describe transformer capabilities and put them to the test against a wide variety of specific tasks. These tasks ranged from simple counting problems and logical puzzles to tracking the structure of sentences and navigating through networks of connections. The researchers did not just look at the math on paper; they built small, custom-made versions of these programs and trained them from scratch to see if they could actually solve the problems. They also tested massive, pre-trained language models that are already in use today to see if the rules changed when the programs became much larger and more complex.

The results revealed a surprising truth: no single theory could explain the full picture. When the researchers compared the predictions of the seven theories against the actual performance of the programs, they found that the theories often disagreed with reality and with each other. For instance, several theories predicted that a program would struggle to count how many times a specific symbol appeared in a long list of text. In the lab, however, the programs learned this task easily and could even apply what they learned to lists much longer than the ones they were trained on. Conversely, other theories predicted that a program would be able to solve a complex arithmetic problem, but the programs consistently failed to learn it, even when given plenty of training data. This mismatch showed that the theories were missing key details about how the programs actually work.

The study identified two main reasons why the theories failed to match reality. First, many of the theories assumed the programs made decisions by focusing on just one piece of information at a time, like a spotlight picking a single word. In reality, the programs use a softer, more flexible method that allows them to blend information from many different parts of the text at once. This flexibility lets them solve tasks that the rigid theories said were impossible. Second, some theories assumed the programs could perform unlimited calculations at every step, which made them seem more powerful than they really are. These theories predicted the programs could solve difficult graph problems, but the experiments showed the programs got stuck, unable to learn the necessary steps. The researchers found that the ability of a program to learn a task often depended less on its raw power and more on how it was taught and how its internal memory was organized.

One of the most striking findings was that the size and training history of the program mattered immensely. The small programs built specifically for the experiments behaved very differently from the giant, pre-trained models used in everyday applications. Sometimes the small models learned a task that the large models failed to solve, and other times the large models succeeded where the small ones failed. This suggests that the capabilities of these systems are not just a result of their design, but also of the vast amounts of data they are fed and the specific methods used to train them. The theories that focused only on the architecture of the program, ignoring the data and the learning process, could not predict these outcomes.

Ultimately, the paper concludes that to truly understand these powerful tools, scientists need a new kind of theory. This new framework must account for the flexible way the programs blend information, the limits of their local calculations, and the crucial role of how they learn. It must also explain why some programs generalize well to new situations while others do not, a difference often driven by the specific way they are taught to remember the order of words. By showing that no single existing map covers the entire territory, the researchers have provided a clear path forward. They have created a new set of benchmarks and a clearer understanding of what is actually happening inside these machines, offering a solid foundation for building the next generation of artificial intelligence that is both powerful and predictable.

Technical Summary: Putting Transformer Theories to the Test

Problem Statement

Since the introduction of the transformer architecture, numerous formal theories have emerged to characterize its capabilities and limitations. These theories—including Star-free, AC0, TC0, C-RASP, MPC, BAPO, and Sensitivity—employ distinct abstractions regarding information flow, attention mechanisms, and computational bounds. Consequently, they often yield conflicting predictions about which tasks transformers can solve (e.g., predicting Majority or Parity as "Hard" or "Easy").

The central problem addressed in this work is the lack of a unified understanding of which theoretical framework best aligns with empirical reality. It remains unclear which abstractions are necessary to explain the successes and failures of transformers in practice, particularly regarding in-distribution learning, length generalization, and the performance of pretrained large language models (LLMs). This paper seeks to bridge the gap between transformer theory and practice by systematically comparing the predictions of seven major theoretical frameworks against controlled empirical experiments.

Methodology

The authors constructed a comprehensive evaluation framework consisting of three main components:

Task Suite: A diverse collection of tasks covering various computational structures was curated to target points of theoretical disagreement. The suite includes:
- Boolean Functions: All, Any, Majority, Parity.
- Retrieval Tasks: Index, Index-All/Any, Index-Parity, and k-Hop Induction (composing content-dependent lookups).
- Sparse Functions: Sparse-All/Any, Sparse-Parity.
- Arithmetic & Graphs: BinaryAdd, Edge Existence, Directed/Undirected Reachability.
- Syntactic Structures: Dyck languages (bounded and unbounded depth).
Theoretical Mapping: The authors mapped each task against the seven theories (Star-free, AC0, TC0, C-RASP, MPC, BAPO, Sensitivity). Where existing literature lacked a prediction for a specific theory-task pair, the authors derived new theoretical results or constructions to complete the prediction matrix. This involved proving lower bounds, impossibility results, or explicit constructions (e.g., proving C-RASP requires exponential size for certain retrieval tasks).
Empirical Evaluation: Three distinct experimental lines were conducted to test theoretical predictions:
- In-Distribution Learning: Training small, task-specific causal transformers (4 layers, width 256) on increasing input sizes ( $n$ ) to measure sample complexity and whether the model can learn the task.
- Length Generalization: Training models on small inputs ( $n \le 32$ ) and evaluating their ability to generalize to much larger inputs ( $n$ up to 256). This was tested across 27 architectural configurations (varying model sizes and positional encodings like RoPE, NoPE, and absolute/relative schemes).
- Pretrained LLM Performance: Evaluating five frontier pretrained models on the same tasks without task-specific fine-tuning, using natural language prompts with few-shot examples.

Key Contributions

1. Theoretical Analysis and New Results

The authors provided new theoretical results to fill gaps in the existing literature, specifically:

C-RASP Limitations: Proved that C-RASP (which models uniform averaging) requires exponential program size to solve query-key retrieval tasks that softmax attention transformers solve efficiently with linear width. This highlights the cost of lacking dynamic, content-dependent attention.
k-Hop Induction: Demonstrated that C-RASP cannot express k-Hop Induction (even for $k=1$ ), despite induction heads being central to in-context learning in practice.
BAPO Hardness: Established that unbounded Dyck languages and BinaryAdd are BAPO-hard.
Exponential Separation: Showed an exponential width separation between C-RASP and softmax attention transformers for retrieval tasks.

2. Empirical Validation Matrix

The study generated a comprehensive matrix comparing theoretical "Easy/Hard" predictions against empirical outcomes (In-Distribution, Length Generalization, and LLM performance). This matrix revealed that no single theory consistently predicts the observed behavior across all tasks.

3. Identification of Failure Modes

The experiments identified specific reasons why theoretical predictions fail:

Hard vs. Soft Attention: Theories assuming hard attention (Star-free, AC0, BAPO) incorrectly predict tasks requiring global aggregation (like Majority) to be hard. Empirically, transformers with soft attention solve these tasks robustly.
Content-Dependent Retrieval: Theories assuming uniform averaging (C-RASP) incorrectly predict retrieval tasks (like Index and k-Hop Induction) to be hard. Empirically, transformers with dynamic attention solve these.
Loose Upper Bounds: Theories providing loose upper bounds (TC0, MPC) often predict tasks to be easy that transformers fail to learn in practice (e.g., BinaryAdd, Parity). This suggests these theories overestimate practical learnability by ignoring optimization barriers or local computation constraints.
Learnability vs. Expressivity: The failure to learn tasks like Parity is attributed to optimization barriers (sharp loss landscapes) rather than expressivity limits, a nuance captured only by the Sensitivity theory.

Results

Disagreement Among Theories

The seven theories make conflicting predictions on the majority of tasks. For instance:

Majority: Predicted Hard by Star-free, AC0, and BAPO; Easy by TC0, C-RASP, MPC, and Sensitivity. Transformers successfully learn this, supporting the latter group.
Parity: Predicted Hard by Star-free, AC0, C-RASP, and Sensitivity; Easy by TC0, MPC, and BAPO. Transformers fail to learn this even in-distribution, supporting the former group.
k-Hop Induction: Predicted Hard only by C-RASP; Easy by others. Transformers learn 1-hop induction but struggle with 2-hop and 3-hop compositions.

Empirical Findings

No Single Theory Suffices: No theory explains the full pattern of successes and failures.
Hard Predictions are More Reliable: When a theory predicts a task is "Hard," it is more likely to be correct empirically than when it predicts a task is "Easy." "Easy" predictions often rely on handcrafted constructions that training algorithms may not discover.
Role of Positional Encoding: Length generalization is highly sensitive to positional encoding. No single encoding generalizes across all tasks (e.g., NoPE generalizes on unbounded Dyck-1, while RoPE succeeds on 1-Hop Induction).
LLMs vs. Small Transformers: Pretrained LLMs behave differently from small transformers trained from scratch. LLMs often fail on tasks like Majority and Index as input size grows, whereas small transformers succeed. Conversely, LLMs succeed on some tasks where small transformers fail, suggesting that data, tokenization, and training recipes significantly impact capabilities beyond architecture alone.

Significance and Claims

The paper claims that current theoretical practice has a weakness: "easy" predictions are often based on existence proofs (constructive upper bounds) that do not guarantee learnability, while "hard" predictions sometimes misidentify the root cause of failure (e.g., attributing Parity failure to expressivity rather than optimization).

The authors argue that a unified theory of transformers must capture several specific features currently omitted or oversimplified in existing frameworks:

Soft, Content-Dependent Attention: Models must account for dynamic retrieval, not just hard selection or uniform averaging.
Bounded Local Computation: Theories must constrain local computation to avoid overestimating capabilities (as seen in MPC/BAPO).
Learnability and Inductive Biases: Theories must explain why training finds certain solutions and not others, incorporating the effects of positional encodings and optimization landscapes.
Data and Training Dynamics: A theory of LLMs must account for the influence of pretraining data and training recipes, not just the static architecture.

Ultimately, the paper provides a testbed (the task suite and prediction matrix) to guide the development of more practical theories that can explain the complex interplay between expressivity, learnability, and inductive biases in transformer models.