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

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.

Modern AI systems such as chatbots are built with a model called the \emph{transformer}, and researchers want to know exactly which problems such a model can and cannot solve. This is important to understand when we can trust their outputs. Researchers often study this by comparing transformers to \emph{circuits}---a mathematical abstraction of computers whose abilities we understand well. The trouble is that these comparisons are fragile: small bookkeeping choices, like how many digits the model uses to perform arithmetic, can substantially change the verdict, making it hard to tell which conclusions actually apply to the models in use. To amend this, we study transformers that are given extra blank ``filler'' characters as scratch space---room to carry out intermediate work before producing an answer. Mapping out how these padded models behave across many design choices, we find a surprisingly tidy picture: Padding makes them \emph{robust}, so most fiddly choices stop mattering. Only the precision of the arithmetic and the depth of reasoning (how many sequential steps the model makes before giving the answer) genuinely change what the model can compute. In particular, unlike unpadded variants, padded transformers map cleanly to well-known classes of circuits. We also look at \emph{looping}---letting the model run the same set of layers over and over, analogous to re-reading a problem to think it through in stages---which gives the model the sequential, step-by-step reasoning that pure parallel scratch space cannot; we show that the number of loops controls expressivity in exactly the way the depth of a circuit does, so more loops let the model solve strictly harder problems in a clean and predictable way. This means theorists can pick whichever version is easiest to analyze, and practitioners get concrete guidance: spend your memory budget on precision and depth, not width, and use looping when the task calls for sequential reasoning rather than just more parallel work.