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

• URL: http://arxiv.org/abs/2605.30523v1
• Date: Thu, 28 May 2026 19:58:43 GMT
• Title: Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
• Abstract summary: We find that padded $textL$ constantprecision transformers are surprisingly robust to expressivity.<n>$logd-looped constant-precision transformers reach $textFO-uniform TCd$, and growing-precision ones reach $textFO-uniform TCd$.
• Score: 78.36679389968772
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Fixed Universal Transformers [50.35639171254542]
  We introduce emphuniversal transformers: fixed transformers that can simulate any transformer in a given class via a suitable input embedding.<n>We provide explicit sparse constructions achieving universality when the embedding dimension is sufficiently large.<n>Our results suggest that much of a transformer's expressive power may reside in its input representation rather than its learned weights.
  arXiv  Detail & Related papers  (2026-05-29T15:22:06Z)
• Exact Expressive Power of Transformers with Padding [33.4994300801846]
  We show that padded transformers with $O(logd n)$ looping on inputs of length recognize exactly the class $mathsfFO$uniform $mathsfTCd$ moderately parallelizable problems.<n>Our results motivate further exploration of padding and looping as parallelizable alternatives to chain of thought for test-time compute.
  arXiv  Detail & Related papers  (2025-05-25T02:52:15Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  We study in-context learning for linear regression with diverse tasks. We show that multilayer Transformers are not robust to even distributional shifts as small as $O(e-L)$ in Wasserstein distance.
  arXiv  Detail & Related papers  (2024-10-29T03:27:56Z)
• Higher-Order Transformer Derivative Estimates for Explicit Pathwise Learning Guarantees [9.305677878388664]
  This paper fills a gap in the literature by precisely estimating all the higher-order derivatives of all orders for the transformer model.<n>We obtain fully-explicit estimates of all constants in terms of the number of attention heads, the depth and width of each transformer block, and the number of normalization layers.<n>We conclude that real-world transformers can learn from $N$ samples of a single Markov process's trajectory at a rate of $O(operatornamepolylog(N/sqrtN)$.
  arXiv  Detail & Related papers  (2024-05-26T13:19:32Z)
• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers [8.908747084128397]
  We introduce the temporal counting logic $textsfK_textt$[#] alongside the RASP variant $textsfC-RASP$.<n>We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size.
  arXiv  Detail & Related papers  (2024-04-05T20:36:30Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory.
  arXiv  Detail & Related papers  (2022-07-02T03:49:34Z)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  We show that saturated transformers transcend the limitations of hard-attention transformers. The jump from hard to saturated attention can be understood as increasing the transformer's effective circuit depth by a factor of $O(log n)$.
  arXiv  Detail & Related papers  (2021-06-30T17:09:47Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  We show that sparse Transformers with only $O(n)$ connections per attention layer can approximate the same function class as the dense model with $n2$ connections. We also present experiments comparing different patterns/levels of sparsity on standard NLP tasks.
  arXiv  Detail & Related papers  (2020-06-08T18:30:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.