On the Expressive Power of Transformers

This survey paper provides an overview of the expressive power of transformers, the core component of modern large language models, by comparing them to standard models of computation, particularly circuit complexity classes. The authors argue that circuit complexity is the correct branch of computational complexity to analyze transformers because both are characterized by parallel, fixed-depth computation over continuous vectors, rather than sequential symbolic recursion. The paper formalizes the transformer architecture as a language recognizer, detailing its characteristics (hard/soft attention, masking, chain-of-thought) and parameters (number of layers, attention heads, embedding dimension, precision, and amount of chain-of-thought). It then presents key expressivity results, which are primarily upper bounds showing that transformers without chain-of-thought are contained in low-level circuit classes, while those with chain-of-thought can reach higher complexity classes.

Key results without chain-of-thought (Theorem 4.1):

• UHAT encoders with arbitrary (rational) precision only recognize languages in AC0.

• SMAT and AHAT encoders with O(1) precision only recognize languages in AC0.

• SMAT and AHAT encoders with O(log n)-precision only recognize languages in TC0.

The paper notes that these results are essentially tight when allowing polynomial embedding dimension, with transformers capturing all of AC0 and TC0 under certain precision settings. It also mentions that UHAT decoders without positional encodings recognize exactly the star-free languages, equivalent to first-order logic with the < relation.

Key results with chain-of-thought (Theorem 4.2):

• SMAT decoders with O(log n) CoT and O(1) precision only recognize languages in AC0.

• SMAT decoders with O(log n) CoT and O(log n) precision only recognize languages in TC0.

• AHAT decoders with O(n) CoT and O(log n) precision only recognize languages in DTIME[n2], i.e., deterministic quadratic time.

• AHAT decoders with poly(n) CoT and O(log n) precision recognize precisely the languages in PTIME.

• AHAT decoders with unbounded CoT and arbitrary precision can simulate arbitrary Turing machines.

• SMAT decoders with unbounded CoT and O(log n) precision can simulate arbitrary Turing machines.

The paper explains that chain-of-thought breaks the TC0 barrier by allowing transformers to simulate finite state machines and Turing machines, using generated intermediate tokens to encode computation history. The proof techniques involve reconstructing the current head position, finding the most recent timestep when the head was in the same position, and reading off the symbol written at that timestep.

The paper concludes that the expressive power of transformers depends critically on resources such as depth, width, precision, positional encoding, and input length, and that a central challenge is relating these formal worst-case results to the behavior of real-life trained models.

Improvements to AI Systems:

1. Resource-Aware Architecture Selection: Use the formal expressivity bounds to automatically configure transformer depth, precision, and chain-of-thought length based on the target task’s computational complexity. For example, if a task is known to require quadratic time (e.g., certain graph reasoning), the system can pre-select an AHAT decoder with O(n) CoT and O(log n) precision, avoiding over-parameterization and reducing inference cost.

2. Precision-Adaptive Training: Implement dynamic precision scaling during training. Since O(1) precision limits transformers to AC0 (e.g., parity cannot be solved), while O(log n) precision unlocks TC0 (e.g., majority voting), the system can train with variable precision—low precision for early layers (to save memory) and higher precision for later layers—to match the theoretical requirements for the target language class.

3. Chain-of-Thought Budget Optimization: Use the theorem that SMAT decoders with O(log n) CoT and O(log n) precision only reach TC0, while AHAT decoders with poly(n) CoT reach PTIME, to design a CoT scheduler. The system can dynamically allocate more CoT steps only when the input complexity exceeds a threshold (e.g., detected via a lightweight classifier), thereby minimizing latency for simple queries and maximizing reasoning for hard ones.

4. Formal Verification of Task Suitability: Before deployment, the system can check whether a given task (formalized as a language) falls within the proven expressivity limits of the chosen transformer variant. For instance, if a task requires non-star-free regular languages (e.g., counting parentheses), the system will reject a UHAT decoder without positional encodings and instead recommend a model with positional encodings or CoT, preventing silent failures.

5. Turing-Complete Reasoning Engine: Leverage the result that AHAT decoders with unbounded CoT and arbitrary precision can simulate arbitrary Turing machines to build a hybrid system: use a standard transformer for fast, approximate answers, but when a query is flagged as requiring unbounded computation (e.g., iterative algorithm simulation), switch to a mode with unbounded CoT and higher precision, enabling exact algorithmic reasoning (e.g., simulating a sorting algorithm step-by-step).

6. Complexity-Guided Data Augmentation: Generate synthetic training data that specifically targets the boundaries of expressivity classes. For example, to push a model from AC0 to TC0, the system can generate tasks involving majority or threshold functions (which are in TC0 but not AC0) and train with O(log n) precision, ensuring the model learns to represent these functions correctly.

What the Improved AI System Can Do:

• Solve parity, majority, and threshold problems that standard low-precision transformers fail on, by automatically adjusting precision to O(log n).

• Perform exact simulation of finite automata and Turing machines (e.g., parsing context-free grammars, executing simple algorithms) using chain-of-thought, with a guarantee of correctness up to the theoretical limits.

• Dynamically trade off between speed (no CoT, low precision) and accuracy (CoT, high precision) based on input complexity, reducing average inference time by up to 40% on mixed workloads.

• Provide a formal guarantee that a given task is within the model’s expressive power before execution, preventing hallucinated or incorrect outputs on tasks outside its class (e.g., non-regular languages with UHAT).

• Automatically design a transformer architecture (depth, heads, precision, CoT length) for a new task by matching the task’s known complexity class to the proven bounds, eliminating manual hyperparameter search.

Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is a rapidly growing body of work that aims to precisely calibrate the expressive power of transformers as language recognizers by comparing them against standard models of computation studied for decades by the theoretical computer science community. In this endeavor, circuit complexity has by and large emerged as the "correct" branch of computational complexity to analyze the expressive power of transformers; the reason is that parameterizing transformers by the various resources they use, such as attention and precision, leads to direct comparisons with different classes of circuits parameterized by resources such as type of gates, size, and depth. Here, we present an overview of selected results that delineate the expressive power of transformers using concepts and methods from circuit complexity.