Transformers as Recognizers of Formal Languages: A Survey on Expressivity

Lena Strobl, William Merrill, Gail Weiss, David Chiang, Dana Angluin

Transformers as Recognizers of Formal Languages: A Survey on Expressivity

Abstract

While Transformers have achieved unprecedented empirical success, their fundamental computational limits remain a subject of intense theoretical study. This paper provides a comprehensive map of Transformer expressivity through the lens of formal language theory. By categorizing models based on attention mechanisms, precision, and the use of intermediate computation steps, the authors establish a rigorous taxonomy that links Transformer architectures to well-known complexity classes like AC⁰, TC⁰, and NC¹.

Introduction: The Expressivity Gap

Despite their dominance in NLP, the "IQ" of a Transformer—what it can represent in principle—is often misunderstood. Can a standard encoder solve basic tasks like counting or checking for balanced parentheses? This survey addresses the "expressivity gap" by treating computational problems as formal languages (sets of strings following specific rules). This approach allows for a precise categorization of Transformers within established hierarchies of computation, similar to how we classify regular expressions or Turing machines.

Theoretical Framework: Architectural Levers

The authors establish a unified framework to compare disparate theoretical results. They identify several critical "levers" that determine a model's power:

  • Attention Type: The distinction between "Hard" attention (selecting a single token) and "Softmax" attention (averaging over tokens).
  • Precision: The impact of using infinite-precision reals versus more realistic $O(\log n)$ or fixed $O(1)$ bit representations.
  • Position Embeddings (PE): How the model perceives token order (e.g., sinusoidal vs. $1/n$ weights).
  • Computation Flow: The difference between single-pass encoders and decoders utilizing "Chain-of-Thought" (CoT) or scratchpads.

Formal Language Benchmarks

To evaluate these models, the survey utilizes formal language "litmus tests" that serve as indicators of computational power:

  • PARITY: Determining if a bitstring contains an even number of 1s (tests counting ability).
  • DYCK-k: Checking for well-nested parentheses (tests hierarchical structure processing).
  • MAJORITY: Determining if more than half the bits are 1s.
  • W(S₅): A complex regular language that serves as a boundary case for certain architectures.

The Hierarchy of Transformer Power

The survey's primary achievement is the unification of these results into a coherent map of computational power. By mapping architectural variants to complexity classes, the authors provide a rigorous taxonomy.

A map of formal language classes and their relationship to circuit complexity classes like AC⁰ and TC⁰.

As illustrated in the figure, standard Transformer encoders are generally contained within TC⁰ (constant-depth circuits with threshold gates). This means they can handle tasks like MAJORITY but are fundamentally limited in solving problems requiring deep sequential recursion in a single forward pass. More complex languages, such as those in the context-free or context-sensitive categories, often require architectural enhancements like scratchpads or higher precision.

Key Insights: Softmax, Precision, and Scratchpads

Several landmark findings emerge from this synthesis:

  1. The "Scratchpad" Superpower: A Transformer decoder's power increases dramatically when allowed to generate intermediate tokens. With sufficient time and precision, they can simulate any Turing machine, providing a theoretical foundation for the effectiveness of "Chain-of-Thought" prompting.
  2. Softmax vs. Hard Attention: There is a sharp divide in capability. Hard attention limits models to AC⁰, preventing them from solving even the PARITY problem. Softmax attention allows for summation and averaging, elevating the model to TC⁰.
  3. The Precision Trap: Many proofs of "infinite power" rely on unrealistic infinite-precision real numbers. Restricting models to $O(\log n)$ precision significantly lowers their theoretical upper bounds.
  4. Logic as a Language: Transformers can be characterized by specific types of logic, such as First-Order Logic with counting quantifiers, suggesting that their computation is akin to evaluating complex logical formulas in parallel.

Conclusion and Future Directions

While this survey clarifies the theoretical limits of Transformers, several questions remain. The gap between expressivity (what a model can do) and trainability (what it learns via gradient descent) is still wide. Furthermore, the exact role of Layer Normalization and the search for a tight logical characterization of softmax attention remain active areas for future research.

Summary updated

BibTeX
@article{strobl2024transformers,
  author = {Lena Strobl and William Merrill and Gail Weiss and David Chiang and Dana Angluin},
  title = {{Transformers as Recognizers of Formal Languages: A Survey on Expressivity}},
  journal = {Trans. Assoc. Comput. Linguistics},
  year = {2024},
  doi = {10.1162/tacl\_a\_00663},
}
Figure