Understanding the computational limits of Transformers often involves mapping them to boolean circuit complexity classes (like $AC^0$ or $TC^0$). Historically, these theoretical mappings have been brittle—slight architectural tweaks, such as switching from softmax to hard attention or altering numeric precision, could drastically alter the conclusions about a model's expressivity.
This paper resolves these inconsistencies by analyzing padded transformers, revealing that many architectural choices matter far less than previously thought, provided the model has access to a computational "scratchpad."
The Power of Padding
Padded transformers append a polynomial number of dummy symbols (e.g., "...") to the input sequence. This padding acts as a workspace, providing the model with polynomial space for adaptive parallel computation. With this extra room available, the researchers ask: which architectural parameters actually drive the model's expressivity, and which are redundant?
The True Drivers: Precision and Looping
The authors demonstrate that the computational power of a padded transformer is primarily dictated by two factors: numeric precision and looping depth.
- The AC/TC Divide: Numeric precision determines whether a model can count. Constant-precision transformers are restricted to the $AC$ circuit class (logic without counting). In contrast, growing-precision transformers reach the $TC$ class (logic with counting capabilities).
- Looping for Depth: Applying a fixed block of layers repeatedly (looping) allows the model to scale its expressivity to match deeper circuit classes ($AC^d$ and $TC^d$) without increasing the parameter count. "Thinking longer" through looping is a highly parameter-efficient way to boost computational power.
Architectural Robustness
Surprisingly, once a transformer is padded, it becomes remarkably robust to other design choices that typically complicate theoretical analysis:
- Precision Compensates for Width: The authors define a model's "Volume" $V(N)$ as the product of its width ($D$) and numeric precision ($b$). As long as the volume meets a sufficient threshold ($\Omega(\log N)$) to distinguish input positions, a narrow model with high precision is just as powerful as a wide model with low precision. Growing width or precision beyond logarithmic bounds yields no additional expressivity.
- Attention Type Independence: Unlike unpadded models, padded transformers are indifferent to the specific attention mechanism. The paper proves that Softmax Attention (SMAT) can exactly simulate Average Hard Attention (AHAT) under logarithmic precision.
Key Theoretical Results
By evaluating transformers against formal language and circuit complexity classes, the authors establish several exact equivalences:
- Constant-Depth Equivalence: Padded L-uniform constant-precision transformers are exactly equivalent to $AC^0$. With growing precision, they match $TC^0$.
- Looped Models: Log-looped constant-precision transformers reach $FO\text{-uniform } AC^d$, while growing-precision variants reach $FO\text{-uniform } TC^d$. As looping depth increases, both approach the complexity class $NC$ (problems solvable in polylogarithmic time on parallel computers).
- Uniformity Collapse: For looped models, being "L-uniform" (parameters generated by a logspace Turing machine) offers no more power than being "FO-uniform" (a much more restrictive constraint).
Limitations and Open Questions
While this framework unifies much of transformer expressivity theory, several frontiers remain:
- Insufficient Volume: Models with very low volume ($V(N) = o(\log N)$) remain difficult to classify. They are too weak for standard circuit classes and likely require granular sub-$AC^0$ frameworks.
- Unpadded Transformers: The authors conjecture that unpadded transformers are fundamentally less powerful due to size hierarchy constraints in circuit complexity, though a formal proof for the general case remains open.
- Learnability vs. Expressivity: This paper maps what a transformer can compute (its capacity), not what it will learn via gradient descent. Bridging the gap between theoretical expressivity and practical learnability is a crucial next step.
- Arithmetic Realism: The proofs rely on fixed-point arithmetic. The authors acknowledge that results might differ for the floating-point implementations commonly used in actual hardware.
Summary updated