Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

Anej Svete, William Merrill, Ryan Cotterell, Ashish Sabharwal

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:

  1. Constant-Depth Equivalence: Padded L-uniform constant-precision transformers are exactly equivalent to $AC^0$. With growing precision, they match $TC^0$.
  2. 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).
  3. 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

Abstract

Recent work describes what transformers can and cannot compute through connections to boolean circuits, but existing results lack exact characterizations and are sensitive to modeling choices. Padded transformers---to whose input filler symbols such as ``...'' are appended---emerge as a useful gadget for establishing equivalences to circuit classes by providing polynomial space for adaptive parallel computation. However, only a limited set of padded transformer idealizations has been studied, leaving open how robustly these equivalences hold under changes to attention type, model width, and uniformity. We find that, under practical assumptions, padded transformers are surprisingly robust to all of these, and identify numeric precision and model depth as the main factors affecting expressivity. Concretely, we prove that polynomially padded $\text{L-uniform}$ constant-precision transformers are equivalent to $\text{L-uniform AC}^0$, while growing-precision ones achieve $\text{L-uniform TC}^0$ regardless of width. Furthermore, looping enables sequential processing analogous to circuits: $\log^d N$-looped constant-precision transformers reach $\text{FO-uniform AC}^d$, and growing-precision ones reach $\text{FO-uniform TC}^d$. Interestingly, growing width or precision beyond logarithmic does not increase expressivity, and all our results hold for both softmax and average hard attention transformers.
BibTeX
@inproceedings{svete2026revisiting,
  author = {Anej Svete and William Merrill and Ryan Cotterell and Ashish Sabharwal},
  title = {{Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=nBuL6HywFX},
}
Figure