Exact Expressive Power of Transformers with Padding
Authors: William Merrill
Ashish Sabharwal
Venue: NeurIPS 2025 poster ()
Keywords: transformers
padding tokens
looped transformers
expressivity
circuit complexity
inference-time compute
Primary area: theory
TL;DR: We exactly characterize the expressive power of transformers with padding tokens as $\mathsf{TC}^0$, and we also characterize transformers with looping and padding.

Abstract: Chain of thought is a natural inference-time method for increasing the computational power of transformer-based large language models (LLMs), but comes at the cost of sequential decoding. Are there more efficient alternatives to expand a transformer's expressive power without adding parameters? We consider transformers with *padding* tokens as a form of parallelizable test-time compute. We show that averaging-hard-attention, masked-pre-norm transformers with polynomial padding recognize precisely the class $\mathsf{FO}$-uniform $\mathsf{TC}^0$ of extremely parallelizable problems. While the $\mathsf{TC}^0$ upper bound was known, proving a matching lower bound had been elusive. Further, our novel analysis reveals the precise expanded power of padded transformers when coupled with another form of inference-time compute, namely dynamically increasing depth via *looping*. Our core technical contribution is to show how padding helps bring the notions of *complete problems* and *reductions*, which have been a cornerstone of classical complexity theory, to the formal study of transformers. Armed with this new tool, we prove that padded transformers with $\mathrm{O}(\log^d n)$ looping on inputs of length $n$ recognize exactly the class $\mathsf{FO}$-uniform $\mathsf{TC}^d$ of moderately parallelizable problems. Thus, padding and looping together systematically expand transformers' expressive power: with polylogarithmic looping, polynomially padded transformers recognize precisely the class $\mathsf{FO}$-uniform $\mathsf{NC}$, the best that could be expected without losing parallelism (unless $\mathsf{NC} = \mathsf{P}$). Our results thus motivate further exploration of padding and looping as parallelizable alternatives to chain of thought for test-time compute.

Exact Expressive Power of Transformers with Padding
William Merrill Allen Institute for fillm@allenar org
Ashish Sabharwal Allen Institute for ashishs@allenai. org
Abstract
Chain of thought is a natural inference-tine method for increasing the computa- tional power of transformer-basee -assed large language models (LLMs), but comes the cost of sequential decoding. Are there more efficient alternatives to expand a transformer's expressive power without adding parameters? We consider transform- ers with padding tokens as form of parallelizable test-time compute. We show that averaging- hard--atarrrt-ioonn, masked-pre-norme transformers with polynomial padding recognize precisely the class FO-uniform TC" of extremely parallelizable problems. While the TC upper bound was known, proving matching lower bound had been elusive. Further, our novel analysis reveals the precise expanded power of padded transformers when coupled with another form of inference time compute, namely dynamically increasing depth via looping. Our core technical contribution is show how padding helps bring the notions of complete problems and reductions, which have been a cornerstone of classical complexity theory, to the formal study of transformers. Armed with this tool, prove that padded transformers with O(log" n) looping on inputs of length n recognize exactly the class FO-uniform TC moderately parallelizable problems. Thus, padding and looping together systematically expand transformers expressive power: with poly- logarithmic looping, polynomially padded transformers recognize precisely the class FO-uniform NC, the best that could be expected without losing parallelism (unless NC = P). Our results thus motivate further exploration of padding and looping as parallelizable alternatives to chain of thought for test-time compute.
Introduction
Due to the computational limitations of transformers (Merrill and Sabharwal, 2023a; Strobl et al., 2024; Chiang, 2025), solving complex reasoning problems requires extending their computational power at inference time, typically by allowing models to generate long chains of thought (CoT) before their outputs (Wei et al., 2022; Nye et al., 2022). Theoretical work has shown how CoT expands the expressive power of transformers sequential problems outside the class TC of highly parallelizable problems, but it also sacrifices parallelism (Merrill and Sabharwal, 2023b; Li et al., 2024), making inference slow. Are there alternative inference-time compute approaches that increase expressive power while preserving parallelism?
One method for parallelizable inference-tine compute with LLMs is using padding tokens rather than COT. Padding can be understood as restricted CoT where the tokens on the chain are restricted to some "blank" symbol rather than tokens generated by the LLM. Since all the input tokens are known in advance, padding is more parallelizable than COT. There have been some attempts to make padding practical with mixed results (Goyal al., 2024; Pfau al., 2024), but it is not fully understood. Specifically, while it is known that padded transformers remain in TC it has been open and elusive whether they can solve all problems in TC or even the smaller class AC (Pfau et al., 2024).
Work partially conducted as PhD student at New York University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Mix Barrington et al.
TC
Merril and Sabharwal
Lemma
TC .c,d2 11
FO _ AHAT:
Lemma 6
FO M
Theorem
Lemma
Theorem
LŞ AHAT!
Lemma
AHAT
Lemma 5
AHAT
Figure I: Summary of core results: exact characterizations of the expressive power of (llog" n)- depth looped AHAT' with padding, for d 2 0. Theorem shows that AHAT = FO-uniform TC Theorem 2 extends this to show that, for d 2 0, AHAT? = FO-uniform TC In the process of obtaining these results, we also found the novel circuit complexity result that, for any 2 1, FO-uniform TC = L-uniform TC Theorem 3. Thus, for d 1, AHAT, = L-uniform TC
Our first contribution is exactly characterizing the expressive power of transformers with polynomial padding FO-uniform TC", answering open question (Pfau al., 2024). The result emerges through a finer- grained analysis of transformers in terms of string logics (Merrill and Sabharwal, 2023c; Chiang al., 2023; Yang al., 2024; Yang and Chiang, 2024). Thinking in terms of logic, we show that n² padding tokens give transformers enough "storage space" to resolve any first- order majority logic formula over variables. This suffices to capture all of FO-uniform TC (Mix Barrington et al., 1990), giving exact characterization of the expressive power of such transformers.
This first result, however, does not clarify whether padded transformers can be minimally extended to gain expressivity beyond TC". To address this, we consider the combination of padding with looping, i.e., repeating block of layers dynamically as function of input length, also referred to as universal transformers (Dehghani et al., 2019; Giannou al., 2023). This can be understood as a form of inference-tin time compute where padding controls the computation width and looping controls the computation crpth--cucially, without adding any parameters. If the number of repetitions is minimal (e.g., sublinear) in sequence length, this transformer model remains highly parallelizable relative to CoT (Merrill and Sabharwal, 2025).
Extending this result, show that, for d 2 transformers with polynomial padding and O(log" n)) looping recognize exactly FO-uniform TC Thus log or polylog-looped transformers can solve many problems outside TC under standard complexity conjectures, including boolean formula evaluation, iterated matrix multiplication, graph connectivity, and context-free language recognition. It also follows that polylog-looped padded transformers converge in expressive power FO-uniform NC, the ceiling that could be expected while preserving parallelism under standard complexity conjectures.
Our first result about the expressive power of fixed-depth padded transformers provides crucial insight for our extended results about looped padded transformers (ef. Figure 1), by allowing, for the first time, the use of familiar tools of reductions and complete problems from classical complexity theory in the analysis of transformers. First, the ability to express TC implies that padded transformers can implement FO reductions. We then scaffold the ability to implement FO reductions to show that transformers can also implement L reductions, via known results about transformers' ability to implement graph connectivity, an NL-complete problem under FO reductions. We then use this to show that Ollog" n) looping recognizes exactly FO-uniform TC via the "wide" TC circuit evaluation problem, which prove to be complete for this class under L reductions.
Finally, we prove novel circuit complexity result that FO-uniform TC = L-uniform TC for any 2 This was obtained in our analysis of looped transformers with 2 Besides being potentially of independent interest circuit complexity, this allows us to see that, for 2 1, O(log" n) looping allows recognizing not just FO-uniform TC but also L-uniform TC (because they are the same).
Overall, our results provide an exact characterization of the expressive power of padded fixed- depth transformers as TC answering an open question (Pfau et al., 2024). Further, we exactly
OOu formal model. detailed in Section 2, assumes a fully uniform transformer with fixed parameters, fixed width, logarithmic or polynomial precision (showing their equivalence in this setting), masked pre-norm, and causal masking (Theorem I also applies unmasked transformers, showing their equivalence under padding).

---

characterize the expressive power of polylog-looped padded transformers, which reveals that padding and looping dramatically extend the expressive power of transformers under standard complexity conjectures. We take these results to motivate empirical investigation of padding and looping as forms of inference-time compute that are more parallelizable than standard CoT.
Preliminaries
2.1 Averaging-Harrd-Attennn Transformers
Following previous work, we analyze model of transformers that is slightly idealized compared to standard soft-attention transformers. Specifically, we analyze transformers with averaging hard attention (AHAT; also called "saturated"" by Merrill et al., 2022) and masked pre-norm (Merrill and Sabharwal, 2023b). AHAT attention heads only attend to the values that maximize the attention score; in the case of ties, the head returns uniform average of all values with tied scores. Masked pre-norm means that the transformer can apply linear projection before pre-norm at the beginning of each sublayer, which is useful for reading individual values from the residual stream without interference from other values. Overall, believe these idealizations minimal changes that make it easier to implement algorithmic constructions that generalize to any sequence length.
More formally, we define the transformer sublayers in this AHAT model following Merrill and Sabharwal (2025). Each sublayer uses masked pre-norm (Xiong et al., 2020; Merrill and Sabharwal, 2023b), reading input 2, matrix, and layer-norm can be standard layer-norm (Ba et al., 2016) or RMS norm (Zhang and Sennrich, 2019). The sublayer outputs 81,..., 8n and the residual stream is updated hJ h, + 8, Definition (Self-attention sublayer). The self-attention sublayer is parameterized by a mask m E Qmmn output projection matrix W Q + QTT and, for < k S h. query, key, and value matrices K V*, each of which is projection from Q" to @m/hh.
where h; is the previous sublayer output, M is some
Given input 2, the self-attention sublayer computes queries q: = Qzz, keys k; = K²z, and values V; Vzz, z, Next, these values used compute the attention head outputs:
exp(1/T
9 (.kk)
a.k
lim T-0
Vi
where Zi,
Σ exp (1/T g.ck,,))
Ze,
1=1
We can set c= i define causally masked attention and e= n for unmasked attention. Averaging hard attention is formalized by taking the low-temperature limit (7 0), which causes all probability mass to be concentrated on the tokens that maximize the attention score. In practice, transformers can approximate this by learning temperature close to zero; for fixed sequence length, this approximation will hold, but for longer strings it will break down. Finally, the output of the self- attention sublayer is computed by aggregating the head outputs via W concat (a;1,, a;,x)-
Definition 2 (Feedforward sublayer). The feedforward sublayer at layer i is parameterized by mask m Q" and projections W Q + Q and U Q" Qm
A feedforward layer computes a local update to the residual stream via 6, = U ReLU(Wz.)..
A transformer defines function Σ* -> or Σ' 10, if we add linear head the final layer and take its argmax as the output. We say that a transformer T Σ + {0. 1} recognizes a language L (with -owaninng-o-seuuunneee token $) if, for any Σ". T(Sw) = 1 if and only if w L.
Precision. In Appendix A, we formalize logarithmic (Merrill and Sabharwal, 2023a) and polynomial precision (Chiang. 2025) datatypes. All our constructions go through with either datatype, showing that logarithmic and Salynomial-precisionn looped padded transformer classes are, in fact, identical.
Layer-Norm Hash. Our constructions will use the layer-norm hash representation (Merrill and Sabharwal, 2023b, 2025) for query-key matching with positive integer values.
Definition 3. Given z E N, its layer-norm hash is the vector (z, 1, -2, +2
The layer-norm hash is computable within a transformer and satisfies that property that dbi)) T (bj) 1 if and only if i j. This makes it useful for retrieval based position matching using AHATs.
3

---

2.2 Padded and Looped AHATs
We assume looped transformer model as previously defined by Merrill and Sabharwal (2025):
Definition 4 (d(n))looped transformer). A looped transformer's 's layers are partitioned into blocks (A, C). On an input of length n, block / repeated depth-wise d(n) times.
Looped transformers provide a way of dynamically scaling width at test time by looping a block of layers. In addition, we also consider padding (Pfau et al., 2024) as simple way to increase width: Definition 5 tokens (0 E Σ) and then feed this full string through the transformer.
transformer). On an input length n, we first append w(n) "blank"
Looping and padding can also be combined, giving us the following language class for transformers:
Definition 6 (Padded and looped transformers). Let d, k Z20. AHAT is the class of languages recognizable by a causally masked looped transformer with masked pre-norm, a beginning-of. sequence token, no position embedding, O(log" n)) depth, and (nn)) padding tokens. Further, AHAT = U AHAT R. AHAT; = Uk-o AHAT R. and AHAT. = U AHAT.
g. uses causal masking with no positional encodings (but with a beginning-of of-seuuence (BoS) token 8; cf. Merrill and Sabharwal, 2023b). In contrast, some of our constructions will be for unmasked transformers, which must use position encodings to distinguish positions. We will write U for the language classes recognizable by unmasked transformers with 1/2 position encodings. We will occasionally consider mixed-masker transformers where some attention heads use causal masking and others do not. These transformers, which do not need position encodings since they can compute 1/i with causal heads and the BoS token, will be denoted mAHAT
With some abuse of notation, we will use AHAT & to denote both the class of languages as defined above as well as the corresponding class of transformer models. i.e., transformers with O(log" n) and (n*)) padding tokens. The distinction should be clear from the context.
2.3 Circuit Complexity
We define the eircuit complexity classes AC and TC in the standard way (Arora and Barak, 2009; Strobl et al., 2024). A circuit family is mapping C = {Cn from input lengths to circuits that take inputs. AC is the class of language that can be recognized by polynomial-size, fixed-depth circuit families with unbounded-arity AND/OR gates. TC is the same class but augmented with unbounded-arity MAJ gates that take a majority vote over their input bits.
It will often be useful to talk about uniform variants of these classes. A X-uniform circuit family obeys that constraint that circuit Cn for input size n can be "built" from the input string 1 using computation in X. We will consider two standard notions of uniformity: FO uniformity (which is equivalent to DLOGTIME uniformity: Mix Barrington et al., 1990) and the weaker uniformity (i.e., log-space uniformity). For a circuit class XC, we will write A-uniform XC to denote that class constrained to circuit families satisfying A uniformity. See Appendix for formal definitions of each type of uniformity and Strobl et al. (2024) for further context.
Finally, we will also use the notion of completeness for circuit classes. Informally, an X-complete problem is a problem in X to which any other problem in X can be mapped via some simple reduction R. Whether a problem complete depends on the notion of reduction used. See Definition 9 for a more formal definition of reductions, which makes completeness fully defined.
2.4 Logic
We define the standard notion first-order logic over strings (FO; ef. Merrill and Sabharwal, 2023c). FO formulas map strings to boolean values. Its formulas can check for token occurrences at specific string positions, and it allows quantification over positions in the input string. More formally: Definition FO contains two types: indices, representing positions in the input string, and formulas, which evaluate to true or false. For an index or formula æ, we write [>]]> ". for the evaluation of x on string w with variable assignments v (a map from names to values). Indices in FO are integers denoting positions in the input string:

---

1. The constant 1, representing the first token's position: [1]", 1.
2. The constant n, representing the last token's position: [n] w. |wm-
3. Symbols (e.g., i, j, k) representing variables ranging over positions to n: w.e mli).
Formulas in FO then constructed follows:
1. Let 2 be a finite alphabet. For each a E > and any index i, Qx) is a formula that is true
when the i-th input token is That is, (t)
1 iff Wm where = [ te
2. For two indices i, i = J. i S J, and 2 j are formulas with their conventional semantics.
3. For two indices i.j, bit(i,,) is a formula returning the j-th bit i.
4. For two formulas P. Q. P A Q and PV Q are formulas with their conventional semantics.
5. For any formula P (which may refer to i any over variable), the following are formulas:
(a) P..P means setting i to some value m E [1,n] makes P true (more formally,
[P] [P],:e/i=m = =))
(b) Vi.P means setting to any value E [1, make true.
An FO formula P with no free variables is called sentence and returns value in {0, 1] for each input string. The language defined by a sentence is the set of strings mapped to 1. The nesting depth of an FO formula is the depth of its syntactic tree constructed by the rules above. The number of distinct variables is the number of different variable names used in P. This can be minimized by allowing two independent quantifiers in parallel subformulas use the same variable name.
is known that the class of languages defined by FO is exactly the circuit complexity class DLOGTIME-uniform AC = FO-uniform AC (Mix Barrington et al., 1990). This class captures the languages recognized by unique hard-attention transformers (Hao et al., 2022: Yang al., 2024), but it is not large enough to capture soft-attention transformers (Merrill and Sabharwal, 2023a). To consider more expressive logic capable of modeling soft-attention transformers, we can extend FO with majority quantifiers (Merrill and Sabharwal, 2023c). Specifically, we will define FO + M2 as FO extended to include a paired majority quantifier:
Definition 8 (Mix Barrington et al., 1990). FO + M² is FO extended to include the M² quantifier. defined as follows: () is true if ji holds for majority of pairs of positions (i,5) E [n] in the string.
It is known that FO + M defines exactly FO-uniform TCº (Mix Barrington et al., 1990, Theorem 10.2, which uses paired majority). It is also possible to use majority quantifiers to define addition over indices, so without loss of generality, we can assume FO + M formulas have no addition (unlike FO formulas). Moreover, it possible to simulate bit terms of M so we can consider FO + M formulas not contain bit, in contrast to the more standard logic FO + M[bit] that also defines TCº. This makes FO + M a simpler target for our transformer constructions than FO + M M(bit).
3 Masked and Unmasked Transformers
Before presenting our main results, we briefly discuss a simple but important relationship between different kinds of masking that will come in handy. When using a transformer as a recognizer for formal languages, there is choice of whether a decoder (with causal attention masking) to encode the input string. Causally masked (decoder) models are more standard these days, well as theoretically more convenient (c.g., no need for position embedding, as position information can be derived from causal attention), so we take them default model. However, it is sometimes easier reason about how to solve problems with unmasked transformers. Fortunately, the following lemma shows we can simulate an unmasked transformer (encoder) with causally masked transformer (decoder), if we allow padding tokens proportional to the transformer depth. This will be useful going forward in several places where we convert unmasked and mixeed-makke constructions to causally masked constructions.
an encoder (with attention masking) or
Lemma 1 (Unmasked to Causally Masked). Let E be an unmasked (with position encoding 1/i) AHAT encoder with depth & > 1. Then there exists a causally masked AHAT decoder D (without any position encoding) with depth & and with in padding tokens on input length n that is equivalent to E in the following sense: the final outputs of D match the original n outputs of E.
Proof. We first observe that the causally masked decoder D can compute 1 (the position encoding used in the unmasked encoder E) by attending uniformly with value 1 only for the beginning-of
5

---

sequence symbol. To simulate unmasked attention with causally masked attention via padding, the idea for D to unroll a sequence of l "blocks" (one for each of the l layers of E) along the padding length dimension, each of width n. Each block will attend to the previous block in the previous layer and can thus see all tokens despite causal masking.
To implement the block construction, we first compute (n)). We then use this to compute ((b.), where 6; - [i/n] E [1, f), which represents the block that each token belongs to. We also compute ((b; - 1) E [0, 2 --1 using a head that ignores the
token S. Next, we modify each original head from U have an additional term in the query/key product. The query is Co(b; - 1) and the key is o(b,), where C' is large weight. We set C' to fixed large value (independent of n) such that this term dominates all other terms in the inner product computation at each token. As result, the head is constrained over keys in the context where b, = b, - i.e., the keys from the last block. Within these keys, it computes exactly the same AHAT output as the original unmasked head. In this way, we are able to simulate an unmasked (or mixed mask) transformer with a causally masked transformer.
Since causally masked heads of mixed maskedd transformer can be trivially simulated by causally masked transformer, Lemma I allows us to relate various masking variants (proof in Appendix C):
Proposition 1. Unmasked (with position encoding 1/i or i/n; cf. Lemma 10 in $C) and mixed- masked padded transformers (i.e., uAHAT' and mAHATs) can be simulated by causally masked transformers (AHATs). Specifically, for any d, k E N, the following holds for the corresponding problem classes:
1. & S M S AHAT
(kx(k.1)
2. uAHAT C mAHAT S AHATT mmmxx(k.1) for d 2 1
3. uAHAT, C mAHAT! C AHAT!
4 Fixed-Depth Padded Transformers Recognize Exactly FO-uniform TC
We are now ready to prove our first main result, namely that padding tokens allow transformers to simulate FO formulas- with more padding allowing more nesting of variables. Moreover, they can simulate formulas with the special paired majority quantifiers.
Lemma 2. An FO + M2 formula with k 2 1 distinct variables and nesting depth can be computed in & & (and hence in A with (fixed) depth f.
Proof. We will store all n² possible configurations of i variables of the formula using n² padding tokens, where each token corresponds to a specific configuration of all the variables, which we denote (cf. Definition 7). We will present an inductive transformer construction that uses single layer to compute the boolean variable of each formula and the integer value of each numerical expression in FO + M assuming the constituent formulas and values were already computed at the previous layer. Since each FO + M formula consists of fixed number of subformulas and values, we can accumulate all constituents in the residual stream in order to compute any larger formula.
In more detail, let [=r].:" be the value of formula or numerical value x on string w under assignment v. with k total variables. We will identify each variable assignment with an integer u [n*], so that, for every P. padding token v stores [P] in the residual stream with a scalar whose sign indicates a truth value. For numerical value i, token e will represent w. small vector ([..)...) where á is the layer-norm hash (Definition 3). We show how to evaluate each constituent of an FO + M formula. As mentioned after Definition 8, addition over indices and bit are subsumed by M so we do not need to simulate them.
1. Constants. To compute the constant 1 or n at each configuration v, we can attend from each v to the first and last input token and retrieve its position get @(1) or Φ(n), where n |wc]
2. Variables. At each token v, we will compute <[[i] representation of the value of variable i
under assignment v. We view the integer E [n*]] as tuple of & values v[1)..... u[k] E [r]]. We have that [i] w. = =-ii). To get this, we first compute Φ(v) and then take "projection" to retrieve @(v(i)) using quotient and remainder operations (Merrill and Sabharwal, 2025, Lemma 3.1). More

---

formally, we compute ((n) where n |uml divide - 1 times by and then take the remainder mod obtain:
o (Lv/n\ mod n) d(v((i))-
Thus, we conclude that we can compute d(eli) <[I]] ")))) each token v.
Given two numerical values i.j (either variables or constants) already stored at as <{{+) w.) [[[] ".), we can simply compare <[+])r))) $[[]] on some axis and apply layer-norm to obtain [ ", at token
Comparisons.
4. Token Predicates. Assume have <[[:]=))) previously stored at assignment We can hard- attend to retrieve token Wm where m = ".0. We then compute [Qo (i) w," by checking whether
Wm
5. Connectives. Assume we have [P] and [Q] ". previously stored each assignment token Then we can simply use a feedforward network to compute [-P] [PA PPQQuM QI".", or [P Q] independently each
Standard Quantifiers, Assume we have [P] u stored at each configuration v. Then, each m, where v/i = m denotes v with i overriden to have value m. We will count c, the number of m such that polimm holds. More formally, let Ji...., be the set of variables excluding Then e' with query (o(ji), ... (())))) key (o(j"),,... (( and value p to retrieve c/n. Finally, we threshold e/n against + (for 3) or 2n-1 2m
we want to resolve the quantifier Q over the set [[P]w.]iim)) ]= Jm=1,
attend from v
(for v) resolve [Qi.ø]w...
2n
Paired Majority Quantifiers, Assume we have [P] stored at each configuration v. We want to compute [M(i.j).P] for any two variables i.j already represented. The idea slightly generalizes the construction for sangle-variable quantifiers: we will use attention to count the number of assignments where [P]] imm.j. is true. Formally, let ji...., be the set of variables excluding i.j. Then we can attend from v over of with query (ØUi), o(jE-2)), key (OGT') )..,) o +(r-2)) and value [P] to retrieve c/n².. Finally, threshold c/n² against to resolve
In conclusion, we can compute any FO + M formula in uAHAT by inductively computing its constituent formulas and storing their values over & variables using n² padding tokens. The result extends to AHAT by applying Proposition 1.
Our construction for Lemma 2 somewhat resembles (though is distinct from) a result of Lange (2004, Corollary 6.8) that any problem in TC can be reduced to majority logic via a transformation that appends some extra tokens the input. However, their transformation is padding since appends some "non-blank" tokens, and their result also does not clearly apply to transformers.
Combined with previous results about transformers being FO-uniform TC Lemma 2 yields an exact characterization of constant-depth transformers with padding:
Theorem 1. uAHAT AHAT. FO-uniform TC i.e., FO[M, bit).
Proof. It is known that *HAT C FO-uniform TC" (Merrill and Sabharwal, 2023a,c; Chiang, 2025), and this generalizes to transformers with padding tokens (Pfau et al., 2024). We will show FO-uniform TC S uAHAT?. Mix Barrington et al. (1990, Proposition 10.3) proved that FO-uniform T is definable by FO formulas with M² quantifiers: notably, the bit predicate is not necessary when using M² quantifiers. Thus, Lemma establishes that FO-uniform TC S uAHAT". Finally, from Proposition 1, we have uAHAT. C AHAT?. Hence, uAHAT? AHAT!! FO-uniform TC
technical hurdle to obtaining this characterization in prior work was simulating the bit predicate in standard definitions of TC (Pfau et al., 2024). Our results circumvent this by instead relating transformers to FO + M which is equivalent to standard FO]M, bit] (Mix Barrington et al.. 1990).
7

---

It thus follows from Theorem that padded transformers can also simulate bit as well as all of FO, which will be useful in the following section for simulating FO reductions.
Lastly, we note that the arguments leading to Theorem work for both logarithmic and polynomial precision (ef. Appendix A) transformers. This shows that these two levels of precision lead to identical power for fixed-depth padded transformers.
5 Log" Padded Transformers Recognize Exactly FO-uniform TC
The notion of completeness of problem (or language) for a complexity class under certain types of reduction has played a key role in computational complexity. Just like it has been useful for reasoning about the expressivity of resource- bounded standard models of computation (Turing machines, eircuit models, etc.), we show it can also be used to reason about the expressivity of padded transformers.
We begin by formally defining the notion of reductions in terms of predicates languages (rather than string-to-string functions). This will make it easier to precisely implement reductions inside transformers, which produce contextual representations of prefixes of the input string in parallel, in contrast to the more standard definition of reductions as string-to-string functions.
Definition 9. Let b(i) be the binary encoding of E N some alphabet Σ (0.1). Let be a class of languages. We say a transduction f Ex + E* is an R reduction if [[()) is polynomial in |w] and the language R = {ww, b(1),) f(w); = o is in R.
Definition 9 recovers the standard notions of FO and L reductions. A transformer can be said to compute a reduction f if it recognizes the language of triples (w, i, defined above. Since |X] is finite and transformers can equally casily output 'token' in Σ instead of just 0/1, it is in fact more natural to require the transformer to compute a functional form of this language, namely compute ry(,, 2) defined fw=); Our constructions work under both views, though the latter is often more natural and efficient. Formally:
Definition 10. We say that a transformer computes an R reduction f if it either recognizes the language R₃- {(w, i, f(w); = o} in R or computes the function E x N + Σ defined as ry(w, i) = =f(w); where, either case, is encoded in binary.
Lemma 3. Ler C, be classes of languages. Let language be C-complete under R reductions. If AHAT transformers can recognize L and compute every R reduction, then C -AAAT
Proof Sketch. Consider any language L' E C. By the assumed completeness of L. there exists an R reduction f that maps inputs of T,' into inputs of I. such that w E T,' if and only if f(w) E T.. From the last precondition of the theorem, there exists a causally masked log--depti padded transformer Tr that recognizes the corresponding reduction language Ry or, equivalently, computes the reduction function ry (cf. Definition 10). We will assume the latter, i.e., that T7 computes ry. though the construction can also be made to work if Ty checks membership in Ry. Additionally, we also have from a precondition that there exists a causally masked log"-depth padded transformer T'p that recognizes L.
The idea is to "stack" Tz on top of T to obtain a log -epth padded transformer T that recognizes L'. Intuitively, given an input w, the first set of layers of T will compute f(w) tokenwise, by computing r(w. i) = f()); & for every i in parallel. To this end, we will essentially make [ copies of the padding tokens needed by T7 and perform the computation of T independently for each f(w); The second and final set of layers of T will then check whether the string [ww produced by the first set of layers is in L, which will hold if and only if I/. See full proof in Appendix C.
D
Combined with results in prior work, it follows from Lemma 3 (see proof below) that padded log-depth transformers can recognize any language in NL:
Lemma 4. NL C AHAT!
Proof. Let T. be the graph connectivity problem, class C be NL, and class R be FO. We will show that the preconditions of Lemma 3 are met, from which it will follow that NL C AHAT?. First, graph
Here f(w): denotes the i-th token of (ww) i < [[w),, and special symbol D & ل otherwise.
8

---

connectivity is known to be NL-complete under FO reductions (Immerman, 1998). Second, Merrill and Sabharwal (2025) recently showed that mixed-masked log-depth transformers with cubic padding can recognize the graph connectivity problem L, i.c., mAHAT" From Proposition it follows that L E AHAT: Finally, follows from Theorem that fixed-depth eausally masked transformers can recognize languages in FO[M. bit], and hence also languages in FO. Such transformers can therefore compute FO reductions f in the sense of Definition 10, i.e. compute the function ry (w. defined as f the i-th bit of f(w). Thus, Lemma 3 applies.
Since L reductions are in NL, we can bootstrap this result to obtain the following stronger result. For this, we will leverage the notion of reductions and the completeness of the problem of evaluating given "wide" log" depth circuit, formalized in Definition 15 (Appendix D).
Lemma 5. For d 2 0, FO-uniform TC C AHAT.
Proof. We will apply Lemma 3 with the wide circuit evaluation problem (Appendix D) L, FO-uniform TC class C, and L as class R. We next argue that the preconditions of Lemma 3 met, which will finish the proof. First, Corollary 13.1 (Appendix D.2) shows that log -dpth looped transformers (without padding) can solve the wide-TC" circuit evaluation problem, i.e., L E AHAT Second, Corollary 14.2 (Appendix D.3) shows that L is complete for FO-uniform TC under L reductions. Finally, Lemma 4 implies that log"-depth transformers for d 2 can recognize any language in L, and thus compute any L reduction in the sense of Definition 10. Applying Lemma 3, we conclude that FO-umiform TC S AHAT..
The proof heavily leverages the fact that TC circuit evaluation ccmmcleee,,, which show in Appendix D.1. To our knowledge, formalizing this TC -compeeeeete problem (or, in fact, any natural comppeee problem) is novel contribution. We next note the following extension of known result about fixed-depth transformers. See Appendix C for a proof, which leverages the fact that recurrent composition of poly-size FO-uniform circuit families remains FO-uniform (Lemma Appendix B.1):
Lemma 6. For d 2 L, AHAT FO- TC
Combining Lemmas 5 and 6, obtain exact characterization of AHAT! for d 2 1: Theorem 2. For any d 2 1, AHAT = FO FO-uniform TC
Taking the union over all d. we obtain Už_ AHAT as the class of languages recognized by polylogarrihhii-llopped padded transformers. Theorems and imply that this class is the same as Us_o FO-uniform TC", which in turn is the same as the class FO-uniform NC, where NC the class of all "parallelizable" languages- those recognized by polylogarithmic depth (and polynomial size) circuit families. We therefore have:
Corollary 2.1. Polylog-looped poly-padded transformers recognize exactly FO-uniform NC.
As before, we note that the arguments leading to Theorem 2 and Corollary 2.1 work for both logarithmic and polynomial precision (cf. Appendix A) transformers. This shows that these two levels of precision lead to identical power for pooye polynomially-padee transformers.
6 Uniformity Collapse for Circuit Classes
Our results on looped transformers involved substantial analysis of uniform polylogarihmii--epp cireuit classes. This analysis led to prove novel result about uniform circuit families, which both slightly strengthens our results about looped transfomers and may of independent interest.
The result concerns the strength of different uniformity conditions for circuit families, characterizing conditions under which variants of cireuit classes with different uniformity conditions collapse to express the same class of languages (Proposition 6 in Appendix E). Applying this general result to (wide) T circuits, we show that for d > 1, both NL-uniformity and L-uniformity collapse to the weaker notion of FO-uniformity for both ACd and TCd circuits:

---

Theorem 3 (Uniformity Collapse), For any d 2 1, the following equivalences hold:
FO FO-uniform AC = L-uniform AC = NL-uniform AC"
FO-uniform TC L-uniform TC NL-uniform TC*.
The key idea, formalized in Appendix E, is leverage the fact that NL and L themsslves are in FO-uniform AC for d 2 1, and therefore the NL or L machine that builds circuit family can itself be simulated in FO-uniform AC" as well. Thus all one needs to do is compose this "circuit building" circuit family with a "circuit evaluation" circuit family. To this end, we show that functions computed by FO-uniform circuit families are closed under fixed compositions (Proposition 3).
Theorem 3 implies that, for d 2 1, AHAT: recognizes not just FO-uniform TC but also L-uniform TC because these classes are the same.
7 Conclusion
Our results in this work give a precise theoretical understanding of how padding and looping- two ways to dynamically expand the computational resources of a transformer at inference time-increate the expressive power of transformers. Padding expands the circuit width of transformers, allowing them to resolve logical formulas over more variables. As consequence of this, polynomially padded transformers can recognize exactly TC", which was previously known only as an upper bound (Merrill and Sabharwal, 2023a; Pfau al., 2024). In contrast, looping increases the depth of transformers. Applying looping on top of padding, we extended our result to show that padded transformers recognize exactly TC This means that transformers with polynomial padding and polylogarithmic looping converge recognizing NC, the largest class of problems that can be solved with parallel computation. In contrast, transformers with CoT have greater expressive power under standard complexity conjectures (Merrill and Sabharwal, 2023b), but suffer from slow sequential decoding. Thus, while looping and padding are not powerful as CoT, our results suggest they are quite effective ways to expand transformers' expressive power while preserving parallelism.
Several interesting open questions remain from this work. On the theoretical side, it would be valuable to develop a more finegrained characterization of AHAT k. i.c., looped transformers where the padding is at most (nn*) ) for some fixed k. On the empirical side, while looped and padded transformers have both been explored already an extent, would be interesting to see whether these approaches could be successfully integrated to improve the performance of transformers on hard reasoning tasks. Further developing these approaches could ultimately lead inference-time compute methods based on padding and looping that increase transformers' expressive power without sacrificing parallelism, providing more efficient alternative to CoT for solving moderately parallclizable problems.
Limitations
Practical Concerns for Looped Transformers with Padding. In this paper, we showed looped transformers with padding are quite expressive. However, the degree to which transformers can learn to use looped layers is an important open question. In particular, practical details might be important here, such an appropriate parameterization where features can be learned in later layers (Dey et al., 2025). Another practical caveat is that, while padding is efficiently parallclizable, will extend the context length, incurring more memory overhead for the forward pass.
Transformer Model. Here we have assumed AHAT' here rather than softmax attention transformers (SMATs). For any fixed maximum context length, it is possible scale the temperature of SMAT heads to arbitrarily approximate AHAT heads, but for unbounded context lengths, SMAT's may not be able to simulate AHATs. We thus view the AHAT as mild simplification of the SMAT that abstracts away issues with soft attention for simulating hard attention over very long contexts. It would also be interesting to better understand the necessity of the masked pre-norm assumption.
10

---

Acknowledgments
We appreciate discussions with Selim Jerad, Andy Yang, Michael Cadhilac, and attendees of the Formal Languages and Neural Networks (FLaNN) seminar. This project was supported by the National Science Foundation (NSF) through award 1922658 and WM's NSF Graduate Research Fellowship. WM was also supported by a Two Sigma PhD Fellowship and the Allen Institute for AL.
References
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009. ISBN 0521424267.
J. L.. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization, 2016. URL httpstttss://arx...orr 0t///16070004555
D. Chiang.
Transformers uniform TC$10S. TMLR, 2025. ISSN 2835-8856. URL https:
D. Chiang, P. Cholak, and A. Pillay. Tighter bounds the expressivity of transformer encoders. In ICML, 2023.
M. Dehghani, S. Gouws, O. Vinyals, J. Uszkoreit, and L., Kaiser. Universal transformers. In ICLR, 2019. URL https::/ http:/iwwwwieeeee.eeeeeeeeeeeeee http:/oorumm.ddttydd.......
N. Dey, B. C. Zhang, L. Noci, M. Li, B. Bordelon, S. Bergsma, C. Pehlevan, B. Hanin, and Hestness. Don't be lazy: CompleteP enables compute-efficien deep transformers, 2025. URL https://arxiv. www. abt///bb//2200 01618.
A. Giannou, S. Rajput, J.-y. Sohn, K. Lee, J. D. Lee, and D. Papailiopoulos. Looped transformers as programmable computers. In ICML, 2023.
S. Goyal, Z. Ji, A. S. Rawat, A. K. Menon, S. Kumar, and V. Nagarajan. Think before you speak: Training language models with pause tokens. In ICLR, 2024. URL http:://////e net/ forum?1d=phO4cRkP.C.
Y. Hao, D. Angluin, and R. Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. TACL, 10:800-810. 2022. doi: 1 00490. URL
https://aclanns httph/olccllttoogyyyyoooo org/2022. tacl-1.46;
N. Immerman. Descriptive Complexity. Springer Verlag, 1998.
K.-J Lange. Some results on majority quantifiers over words. In Conference on Computational Complexity, page 123-129 129. IEEE Computer Society, 2004. ISBN 0769521207.
Z. Li, H. Liu, Zhou, and Ma. Chain thought empowers transformers solve inherently serial problems. In ICLR, 2024. URL https: //ppnreeieeeeeeiiew. wttp://etteeeeieeee/mm http://foouumdddd//////aaa
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of precision transformers. TACL, 11:531-545, 2023a. doi: 10.1162/ a 00562. URL https://aclanthol1 org/ 2023. tacl-
W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. In NeurlPS 2023 Workshop on Mathematics of Modern Machine Learning. 2023b. URL https:
W. Merrill and A. Sabharwal. A logic for expressing log-precision transformers. In NeurIPS, 2023c. URL https: / http///ppprreiiieeeee htt:/
W. Merrill and Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers. In NeurlPS, 2025. URL httphtttss///oprreiveee wtt.://eoorrmmmdd-pll.llllllll
W. Merrill, A. Sabharwal, and N. A. Smith. Saturated transformers are constant-depth threshold circuits. TACL, 10:843-856, 2022. doi: (1166//clll_00049990 URL https::/acllatth///
09.11922.tcc111..49) tac1-1.49/

---

D. A. Mix Barrington, N. Immerman, and H. Straubing. On uniformity within NCI. Journal of Computer and System Sciences, 41(3):274-306, 1990. ISSN 0022-0000. doi: https://doi.rrg// 10. rect. http:/sciecnaaarriiccca 1016/0002-0000099999902222... URL httpppp://w...ccieeeerreee.... p:1/00220009090002..
M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, C. Sutton, and A. Odena. Show your work: Scratch- pads for intermediate computation with language models, 2022. URL ffooooodoiiiidii Jm92o0a.
Pfau, W. Merrill, and S. Bowman. Let's think dot by dot: Hidden computation in transformer language models. In COLM, 2024. URL http:: http:://o/peeeeeeeeeee net
L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin. What formal languages can transformers express? A survey. TACL, 12:543-561 561,, 2024. doi: 10.1162/tacl a 00663. URL https:// aclanthology
hwapchhooog..rrg///// org/2024, tacl-1.30/
H. Vollmer. Introduction to circuit complexity: uniform approach. Springer Science & Business Media, 1999.
Wei, X. Wang. D. Schuurmans, M. Bosma, brian ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou. Chain of thought prompting elicits reasoning in large language models. In NeurIPS, 2022.
R. Xiong, Y. Yang, D. He, K. Zheng, Zheng, C. Xing, H. Zhang, Y. Lan, L. Wang, and T. Liu. On layer normalization in the transformer architecture. In ICMI, 2020. URL URL.httss://proceediin mlr wptpss//v1//xiiii//e///ee
html.
A. Yang and Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In COLM, 2024. URL httpttt://ppeereiieeeeeee/ http://rwweeeeeeeeeeeeeeeeeeeeee
A. Yang, D. Chiang, and D. Angluin. Masked hard-attention transformers recognize exactly the star- free languages. NeurlPS, 2024. URL /tttps://opeeretttt net/forum2id-FBKsaaaae
B. Zhang and R. Sennrich. Root mean square layer normalization. In NeurlPS, 2019.
12

---

A Datatype Assumptions
We adapt the p-precise datatype model from Merrill and Sabharwal (2025). We encode scalars as strings in {0, 1j", where can be function of n. If p depends parameters, can depend on n. A datatype D assigns numerical semantics for each string in {0, 1jP, For I. let [z]n, be rounded into p i.e., the bitstring whose numerical value in Dr is closest to x (breaking ties in favor of the higher value). We define our datatype Dp to satisfy the following:
activations, but not models
Definition 11 (p-Precise Operations). Let ʃ R - IR. be operation with y-precision realization f: D Dp. We say f is p-precise if, for any ........ IR exactly representable in D
[f(r1...... rx)),, 1,
To apply Definition 11, we view the summation in attention heads as an n-ary operation. We also view layer-norm as single operation from Th IR. Lastly, assume that these operations in the computation graph are defined in the standard way and are thus computable in TC² (Merrill and Sabharwal, 2023a.c).
We consider two natural instantiations of D, in the main text: log precision, with p = c clog (Merrill and Sabharwal, 2023a), and polynomial precision, with p = (Chiang, 2025), for some fixed > All our results go through with either datatype, showing their equivalence for polylogarithnically- looped cetoomiall-ppaddeer transformers.
B Uniformity of Circuit Classes
To make our arguments rigorous for highly uniform (i.e., FO-uniform) circuit families, will be necessary to work with detailed definition of uniformity. For this, we start with standard formal definition of the connection language describing the gates and wires of a circuit family, Here we allow each circuit to have more than one (numbered) output gates.
Definition 12 (Connection Language; cf. Vollmer, 1999). Define the connection language for 109 o as Le Lgaate Lwire where
circuit family {
Lngane ig gate of Cn is type g, is k-th input gate k 2 0, and is b-th output gate if 2 0} Lwire = ij C, has a wire i + j}
and i.j E Zza. g is a gate type, and k. l Z2-1- Here i, k, l are represented using exactly clog bits for some fixed e Zz1.
We will assume that gates in all circuits are numbered so that there is a block of input gates, followed by a block of intermediate gates, followed by a block of output gates. Thus, there exist specific gate thresholds that denote the boundaries for input and output gates.
Definition 13 (Generalized Uniformity). A family of circuits C = (Ca ) is A-uniform if Le E A.
When A = L, this generalized uniformity notion is equivalent to the standard definition of uniformity in terms of being able serialize C, function of 1":
Proposition 2. C { L-uniform if and only if + (Cn) is computable in log space.
Proof. To the connection language notion of uniformity to serialize the circuit with log space, simply maintain a counter of our current gate position and edge and call an oracle for the connection language to print each gate and wire. In the other direction, we modify the routine that serializes the circuit to only output gate i or edge j. and we use this to recognize Lc.
B.1 Uniformity Composition Closures
Our later results about uniform circuit families will rely on the property (formalized below) that for strong-enough classes A, any fixed composition of A-uniform circuit families is also A-uniform. Note that any fixed composition of functions can be decomposed into fixed number of serial and parallel compositions of two functions, defined as follows:
13

---

Definition 14 (Function Composition). For functions f.g E {0. - [0, their serial com- position is the function (g (w) g(((w) and their parallel composition is the function (f) = fw) g(w).
For L-umiform functions, serial and parallel composition clearly preserves L-uniformity, as we can maintain a counter to reroute inputs and outputs between subeircuits appropriately. The same applies to any class A containing L. For FO uniform circuit classes, closure under composition requires a bit more work justify, shown in the following two lemmas.
Lemma 7. If functions f and g have polynomial-size FO-uniform circuit families, then does their parallel composition (f.9)-
Proof. Let CJ = [C be an FO-uniform circuit family for f, with connection language L5 Le, E FO. Similarly, define CO C22 and Lg for g.
We will decide the connection language ((gg)) by querying Lg and Lg to build C% and C% in parallel. Without loss of generality, we assume all gate indices the input word for gate query fit into one of the following three cases: (1) at most the number of gates sy in the circuit C₁ (2) larger than sf but most 5 + $g where 5g is the number of gates in C% or (3) larger than 8y + 8g but at most 8/ + Sy + os. where oy is the number of output gates of C₁ If all gates are at most sj, we simply query Ly. If all gates are larger than sy but at most 8 + Sg. we subtract sy from each gate index and query Lg. Finally, if we are querying new gates from 5y + Sy < S $1 + Sy + os, we design the connection language to represent identity gates. Importantly, addition and inequality checks can be performed in FO, and the connection languages f and L.g can be queried in FO by construction.
The logic for edge queries in the connection language modifies gate indices according to the same logic as the gate queries with a few exceptions. First, for an edge (i, if is an input for C (and CH) and = -- 8,, return 1. This ensures that C₁ and C2 both receive the same input. Second, if i is an output for C/ and sy Sq < j S sy + Sy + Og, we also return 1. This copies over the outputs of C/2 so that they appear at the very end of the combined circuit.
Thus, this connection language constructs a circuit family that computes f and g parallel and returns their outputs (g(w), f(w)). Without loss of generality, their order can be casily permuted to obtain the output (f().. g())) of parallel composition. It is clear from the construction that the size of the resulting circuit family is linear in the sizes of Cf and C9, and thus polynomial in n. D
Lemma 8. If functions| f and g have polynomial-size FO-uniform circuit families, then so does their serial composition g f.
Proof. Let Cf = (C J be an FO-uniform circuit family for f. with connection language Ly = Le, E FO. Similarly, define C2, C22 and Lg for g.
We will decide the connection language / by querying T.y to construct C/,, then modifying the inputs to Lg to build C. on the output of f. which has size m. The cases are the same as for parallel composition, except for a few changes. First, we build C' instead of Cg. Second, when querying input gates for CR we add a condition that routes from the outputs of C rather than its inputs. Finally, we do not construct additional gates to copy over the outputs from C/2- Thus, this connection language builds circuit family that computes g on the output of f. Similar to the parallel composition case, it is clear from the construction that the size of the resulting circuit family is linear in the sizes of es and C9, and thus polynomial in n.
Combining Lemmas and 8 along with the fact that any fixed composition of functions can be decomposed into fixed number of serial parallel compositions of two functions time, obtain that fixed function composition preserves FO-uniformity of circuit families:
Proposition 3 (Composition Preserves FO-Uniformity). Any fixed composition of polynomial size FO-uniform circuit families is also polynomial-size and FO-uniform.
Lemma 9 (Recurrent Composition). Let m(n), d(n), and r(n) be functions at most polynomial in with m(n) and r(n.) definable variables in FO given a". Let f {0, 1)m(n) - {0, 1) have polynomial-siz size FO-uniform circuit family with depth d(n)). Then the function frin) (i.e., f
14

---

called recurrently on itself r()) times) has an FO-uniform circuit family of polynomial size and depth d(n) r(n).
Proof. Let CJ = 10 be a polynomial size FO FO-uniform circuit family for f. with connection language T.g. Without loss of generality, we assume the number of gates in C₁2 is 22(n) for some integer s(n) (this can always be achieved by padding C₁, if necessary, in a way that increases size by at most factor of 2). Since the circuit family is of polynomial size, s(n) O n) and can be computed in FO as the smallest j s.t. bit(sy..j 1, where 8y is the number of gates in C/2, We will construct an FO-uniform circuit family C {Cn J==o where Cn consists of f(n) iterations of CA By construction, C₂2 has size at most polynomial and depth d(n) r(n).
The remainder of the proof will justify that C is FO-uniform by defining its connection language Le in terms of Ly. starting with gate queries. Given a gate query w with index i, we first compute r(n), which is possible by construction. We then compute 5 = r(n) 2²(x) by left shifting r(n) by s(n). and, if i 2 S. we reject w. Otherwise, we compute '' = mod 20(n) = bit(i, ((n)), which can be computed in FO by reading the s(n)-th bit from the start of i in w. We then compute query where: is replaced by i'. We then query whether u E Ly. This ensures that Cn repeats all the gates in C₁, stacked in r(n) blocks.
new
Given an edge query w between (i, we first compute i' mod 2*(x) and j' j mod 2*(m) as above. Additionally, let qi = Li/2<(n) and qj = [j/22(()]. We compute qi and qj in FO by right-shifting by s(n). If q. = yj. we follow similar logic to the gate case, constructing u by replacing i with i' and j with j/. We then query whether u E T.y. This has the effect of constructing all edges within a block of C, analogously to those in C₁ Additionally, if q + j' S mnnn), we return
qj. 2 8 - m(n). and for this edge; recall that mnn) is the number of inputs well as the number of outputs of f. This has the effect of routing the output of each block as the input for the next block. Thus, C computes (r(m)) and FO-uniform.
C Omitted Proofs
Proposition 1. Unmasked (with position encoding 1/i or i/n; cf. Lemma 10 in $C) and mixed- masked padded transformers (i.e., uAHATs and mAHATSs can be simulated by causally masked transformers (AHATs). Specifically, for any d, k E N. the following holds for the corresponding problem classes:
1. D C mAHAT S AHATO
max(k.13
2. uAHATE C MAHAT C AHAT 1-max (k, for d 2 1
3. uAHAT? C mAHAT! C AHAT
Proof. As noted in the proof of Lemma 1, the 1/i position encoding used in our unmasked transform- ers can be computed by causally masked transformers, and hence also by mixed-masked transformers. Thus, unmasked padded looped transformers with position encoding 1/i constitute a special case of mixked padded looped transformers, and can thus be trivially simulated by the latter. We will next describe how to leverage Lemma I to convert an unmasked padded looped transformer to a masked one, on a per-head basis. The construction will leave the computation of masked heads unchanged, making the approach suitable for converting both unmasked and mixked padded transformers to masked ones.
Let E be an unmasked looped encoder in UAHATI- k- Then E has depth e = Ologg n)) and operates over n + Onr*) tokens (including original input and padding tokens). By Lemma 1, E can be simulated by a causally masked decoder D with depth l and with E (n + O(z²)) new padding tokens (after the original O(n²) ) padding tokens used by E). Thus, the total number of padding tokens D uses is p On*) + f. (n + O(n*)). Since = (log" n), this simplifies to p = Ollgg (n) n²) where = max (, 13. This is O(n*') when d = O, and +11) when d 2 1. This finishes the proof of the first two parts. For the third part, observe that by definition, uAHAT! = U uAHAT!
From the above, this in turn is contained in U AHAT #+1 1 S AHAT! as desired.
15

---

For the mixed maakkngg case, the construction in Lemma will preserve the original computation of causally masked heads if we add an additional term with large negative weight C' (fixed w.r.t. n) that is activated if the index within the block is greater than b;. We set C' large enough to dominate all other terms in the inner product computation at each token, As result, the head is constrained to only attend to previous tokens within the block. Applying this modified construction on a case-by-case basis per head, we can take this proposition to apply equally to transformers with masking... O
The above simulation of unmasked padded looped transformers (with position encoding 1/ with mixeddmask transformers can, in fact, be extended even to the case where the unmasked transformer uses i/n positional encoding:
Lemma 10. There exists a mixed-mask sublayer with one masked head and one unmasked head that computes ((i/n).
Proof. We use two attention heads, one causally masked and one unmasked, both of which attend uniformly with value only for the beginning-of-ssqueee symbol. The first head thus computes 1/2, while the second head computes 1/n. We can then combine these values to compute (11/n, 1/2) <(i/n).
Lemma 3. Lel C, be classes of languages. Let language L be C-complete under R reductions. If A transformers can recognize I. and compute every R reduction, then C C AHAT
Proof. Consider any language L' C. By the assumed completeness of L, there exists an R reduction f that maps inputs of L' into inputs of L such that w E L' if and only if f(w) E L. From the last precondition of the theorem, there exists causally masked -eeth padded transformer Ty that recognizes the corresponding reduction language R2 or, equivalently, computes the reduction function ry (ef. Definition 10). We will assume the latter, i.e., that T computes r,, though the construction can also be made to work if y checks membership in Ry. Additionally, we also have from a precondition that there exists a causally masked ldgt-depth padded transformer Th, that recognizes L.
The idea is to "stack" Tr, on top of T3 to obtain log--depth padded transformer T that recognizes L'. Intuitively, given an input w. the first set of layers of T will compute f'ww) tokenwise, by computing r(w, = f for every i in parallel. To this end, we will essentially make [w)] copies of the padding tokens needed by Ty and perform the computation of T independently for each f(w),. The second and final set of layers of T will then check whether the string f(w) produced by the first set of layers is in L, which will hold if and only if w E T.. We next make this idea more concrete.
Compute Reduction. Suppose Ty AHATE and let = -wwl. Then, on input (w, i), where i is represented in binary, Ty uses O(n²) padding tokens to compute f(w);, which we upper bound by h+1 for sufficiently large n (for small n, we assume T instead uses a fixed lookup table (and no padding). There is uniform TC circuit family that computes ji) from input (ii), Φ(j), so, by Theorem 1, there exists a transformer Tbit that computes bit with n² padding tokens, for some b and sufficiently large n (again, for smaller n. we assume Tbit uses fixed lookup table). Since [f(w) is bounded by some polynomial n", we know that any i S [fw) takes at most c logg n bits to specify, which we upper bound by d' = (since it's unclear how transformer would compute log n.)
We will construct ne blocks of padding tokens, each of size B B'n' + ++1, Block i will first compute the binary expansion of in its first c'n'' padding tokens using Thit, and then use the remaining n k++1 padding tokens to consume (w, i) using Ty and return r (w. i). At each token t compute integer division with
in block i, compute (i) as @(ttBB] B)) }), using the fact that a fixed block of transformer layers (Merrill and Sabharwal, 2025) and having computed B as a function of n in earlier layers (since it is in TC?). For t' < d, token t = t'm computes oot") via division similarly to d(i) and then bit(ī, t'). This recovers the binary representation of i stored across tokens t = t' t'n in block i, for 1 tt < c. Finally, we apply slightly modified TỤ over the block. Specifically, we add a new term to each attention head so that only attends over the input tokens and some tokens within the current block: those satisfying / = I'n for some 1 < l'' < é' or L. >> d'nh: since c' n, these predicates are simple to check. As a result, block i simulates Ty over w with n padding. Thus, the final token of block i computes y (w, i) = fw).
16

---

Solve Complete Problem. We will use additional layers to check whether f(w) E L'. We are given that there exists transformer 7 that, on input w', checks whether w' E I'. For each attention head in LT, we add new term to the attention score that is very negative if that token is not the final token in some attention block. Thus, each head in Tr, will only attend over tokens that are final in some block. We also modify Tr, so that uses ((i) in place of the position embedding for token t. Thus, TL computes whether (w) E L', which is equivalent to recognizing whether w E L.
Lemma 6. For d 2 L, AHAT FO-uniform TC
Proof. Let L be language in AHAT and let ' be a looped. padded AHAT transformer that, when unrolled e llgg n. times for large enough nt," recognizes whether w E for any input w with |we = n. Let (A, B, C) be the partition of layers of 'T where A is the set of initial layers, B is the block that's repeated llog" times on inputs of length n, and C is the set of final layers. Each of these itself a fixed-depth padded transformer; let's call these TA. TB, and Tc. By prior results (Merrill and Sabharwal, 2023a,e; Chiang, 2025), there are FO-uniform TC" circuit families {CAA) J== {C, ooe and [ J== that simulate transformers Ta, TB, and Tc, respectively. Let TR be TB iterated log times, and Let Ty be Ta iterated log" n times. We justify that r(n) [log n is definable variable in FO given a": compute the index of the last a and then find the greatest bit index that is 1. We now invoke Lemma 9 to show that T' has an FO-uniform TC circuit family; we can repeat this process d times to get an FO-uniform TC circuit family for Tÿ By Lemma 8, there is also an FO-unifom TC circuit family that computes the serial composition of TA,TR..... TR, and Tc. where accounts for a fixed repetition of TR to account for a constant e on the depth e [log n Thus, we conclude that L E FO-uniformTC".
n==
D Wide-TC Circuit Evaluation Problem
To formalize the circuit evaluation problem, we will use the following serialized format for repre- senting circuit. This format is a simplification of the one used by Merrill and Sabharwal (2023a), with two main differences: (a) instead of single threshold gate, we use AND, OR, NOT, and MAJ (the majority gate), which will simplify the description of the construction; and (b) we do not require the gates in the serialization to be sorted in any particular order, which makes easier (and perhaps even possible) to have a log-space reduction from any L-uniform TC" language to the cireuit evaluation problem this specific serialization format. The syntax of this circuit format is governed by the following grammar:
Circuit Gate
Gate + X Op Arg"
Op + AND
OR
NOT
MAJ
Arg &1"
Semantically, we take the k-th X gate to return the k-th input bit. Other gates retrieve the values of the gates referred by their argument pointers and apply the associated logical function. We take the final gate in the serialization to be the output gate of the circuit. Note that not all strings in this grammar represent a well-formed circuit, but any valid circuit can serialized in this format.
As an example, the threshold circuit Majority (I1, T2 VI3, -2:a) stating that at least two of T2.122V Vas. and - should be true, would be represented follows:
X XXXXX MAJ &1 &11111 &111111 OR &11 &111 NOT &111
impul
Majority gale
Or gate
Not gale
Note that the non-input gates need not be serialized in this particular order. The following is also an equally valid serialization of the same formula:
X X
OR &11 &111 NUT &111 MAJ &1 &1111 #11111
input
Or gate
Not gate
Majority gate
We now formalize the circuit evaluation problem, for any class of circuit families, such as the class TCd of -eeth circuit families:
As before, for small assume 2" uses lookup table.
17

---

Definition 15 (C Circuit Evaluation). Let C be class of (potentially non-uniform) circuit families. The C circuit evaluation problem defined as follows:
Input: (r, (C)) where E (0, 1) a string and (C)) is the serialization of a circuit such
that C' = C|1 for some circuit family {Cn C.
Output: The value C(z).
For example, the case where C poly yields the generic circuit value problem, which is known to be P-complete. We focus here to the case of C = TC i.e., the TC circuit evaluation problem. somewhat intuitive that this problem hard for the class A-uniform TC as long as A is strong enough to build circuits; we formalize this later in Lemma 11. However, the TC circuit evaluation problem is not necessarily in the class TC To see this, suppose to the contrary that there exists an A-uniform TC circuit family = {C 1op that solves the TC circuit evaluation problem. Then, for large enough n, each circuit C, E has depth upper bounded by e clog n for a fixed > 0. This c being fixed is problematic-if one were to try to evaluate on string æ a circuit C₁ from a TC circuit family that has depth c' log" n where d' > c (that is, invoke circuit evaluation for input (x, (C2))) the intuitive approach would require a circuit whose depth larger than that of C..
To address this, now formalize a constrained version of the TC circuit evaluation problem that is, in fact, within the class FO-uniform TC We achieve this via the wide-TC circuit evaluation problem, where the class TCd is defined as follows:
Definition 16 (Wide Circuits). Let wide C TC be the class of circuit families {Cn J such that there exists some e such that, for large n, the depth of C. is most log" and, crucially, the size is at least n..
That is, wide-TC" enforces that the size (and hence the width) of the circuit is large relative to its depth. particular, for every wide-TC" circuit family C, there a > 0 such that the circuit C, has serialization of size ((n"), and depth most e log" n. Thus the depth of C, is at most log" N where N = n + (nn)) is the overall size of the input (I, (Ca)) to the corresponding circuit evaluation problem. As we will show later, this allows the wide-TC" circuit evaluation problem to be solved by transformer (Corollary 13.1) well by an FO-uniform TC circuit family (Lemma 14) using precisely log" N iterations (manifested as loops of transformer FO-uniform TC" block, respectively). irrespective of the C-dependent value of c.
Since is a class of circuit families, wide- TC can be constrained by uniformity conditions in the natural way. With some abuse of notation, we will use wide-TC' to refer to both the class of circuit families and the complexity class of language classes the circuit families recognize. Interestingly, this minimum size constraint imposed by wide-TC" does not weaken it as language class compared to TCd:
Proposition 4. For any d 2 0, non-uniform wide- TCd non-umiform TCd.
Proof. Every wide TC cireuit family is, by definition, also a TC circuit family.
Conversely, suppose E TCd, Then there is circuit family [ recognizing L, where the depth of C, is most clog" for some and large enough n. Consider modified eircuit family (C,, JC where, for each n, C₁ is a copy of C, that, needed, padded with dummy gates so that it has size at least n This modified circuit family also recognizes L but belongs to wide-TCd completing the proof.
In fact, the above equality holds even for uniform variants of these classes: Proposition 5. For any d 2 and A 2 FO, A-uniform wide-TC" = A-uniform TC
Proof. The proof follows that of Proposition 4. Every A-uniform W circuit family is, by definition, also a A-uniform TCd circuit family. Conversely, suppose L A-uniform wid
18

---

Then, we have circuit family C = {Cn In=o recognizing L, where the depth of each Cn is at most clog" for some and large enough n. By A uniformity, we have the connection language Le e A. We define a circuit family C" that least n²" The connection language Le defaults to Le for gates that exist in C' and simply returns a dummy gate for other gate indices up to n This additional logic can be implemented FO, so Le E A 2 FO. Thus, the circuit family C" recognizes L and is A-uniform.
padded with dummy gates to make the number of gates at
D.1 Hardness of Wide-TC" Circuit Evaluation
Lemma 11. For d 0. TC circuit evaluation is hard for L-uniform TC under L-reductions.
Proof. Given any L-uniform TC there exists a log-space Turing machine Tr. that constructs a eireuit family {C,, __ that recognizes I.. We can construct an L-reduction from the TC circuit evaluation problem as follows. Given an imput z whose membership in L we would like to check, the reduction first copies x to the output. It then uses the log-space Turing machine Ti to build the circuit C1z] and output it in the above serialized format. We thus have a log-space reduction from x to (z, ()) We conclude that TC" circuit evaluation is hard for L-uniform TC under L-reductions.
O
Lemma 12. For d O, wide- TC" circuit evaluation is hard for L-uniform TC under L-reductions.
Proof. As in the proof of Lemma 11, we are given L such that there exists log-space Turing machine Tz that constructs { recognizing L. where the depth of each C, is most clog" for some c and large enough n. We can create a modified log-space Turing machine Tý, that builds [Cr] that still recognizes L in depth e clogg n but is padded, if needed, with dummy gates so that it has size least n": we do this by keeping a counter for the number of gates and wires produced and outputting dummy ones until n is exceeded. We then follow the rest of the proof of Lemma 11 with Ty, instead of TT.
j
D.2 Solving Wide-TC Circuit Evaluation with Transformers
mixed-masked masked looped transformer T that, on input (x, (C)) where x E {0, 1}* and (C') is the serialization of a depth l circuit with [x] inputs, computes C(x) when unrolled & times.
Lemma 13. There is a mixed
Proof. We adapt the proof of Merrill and Sabharwal (2023a, Theorem 3), which sketches how log-depth (unlooped) transformers can implement the TC circuit evaluation problem. We construct a looped transformer that will "attempt" to evaluate every gate: if its arguments have already been computed, the gate will return (0, 1}, and, if not, it will return undefined (.L..
Let be a token index. We say the token wi is gate token if it X, AND, OR, NOT, MAJ. We will use gate token i to store the value v, E {0, 1} for the gate it represents as a one-hot encoded vector. In the base case (embedding layer), we initialize v; 1 for every gate token. Using looped block of 2 layers, we will proceed in way that propagates the computation of Us at later layers in terms of previously computed values.
X Gates. In the setup layers at an X token i, we use causally masked uniform attention head with value 1[w = x]. Thus, this head computes r ri/i, where r; number of gates before and including i. We compute <r;//i, /i 1/i) (r::) and store it in the residual stream.
In the looped layers, we define attention head with query o(r:). key d(j), and value wy. This head thus retrieves input token Wry, We update the gate value to V +- Wr, (viewing both as vectors in the same space).
Other Gates. In the setup layers, each argument token attends with causally masked uniform attention with value 1 [wr = & to compute o,, the number of arguments to its left (including it). Each & token attends with query d(a;), key ((az), and value 1l [w, &J. which returns 1/(1 + 2:). where z; the number of 1's following & token i. We compute and store o(2; + 1) in the residual stream. We compute g, similarly to a, the number of gate tokens to left of token (also inclusive).
19

---

In the first looped layer, each & token i attends with query 0(2; + 1), key o(g;), and value vy. Thus, the argument token retrieves +1 the value at gate 2, In the second looped layer, gate token i attends with query ((g)). key ((3)), and value 12y+1- This, it returns the vector TA. ZjEA, 'j+ where A, is the set of gates that are arguments of gate From this vector, to recover T, the fraction of j E A, with ey = 1, as well as U, the fraction of j E A, with vj = L. set v by thresholding T against some threshold based on the gate type (7 2 1 for AND, T > O for OR, and T 2 1/2 for MAJ). In effect, this sets oy + G((;))e) where G' is the gate type.
can apply projections
If U > O, set V -. Otherwise,
Thus, the looped layers either keep v; as 1 or correctly update it to its true value. Furthermore, the number of looping steps until is updated is exactly the depth of node i. Thus, circuit C of depth & can be fully evaluated by looping the depth-2 block times.
Corollary 13.1. For d 2 0, wide-TC circuit evaluation is in mAHAT ir and hence in AHAT
Proof. We are given input (2r, (Ca)), where Cn comes from some wide- circuit family {Cn ) with depth at most clog" and size at least n², where c is constant specific the cireuit family. If unroll the transformer from Lemma 13 to depth log" problem for large enough n (w.lo.g. we can solve small-n examples via table lookup).
solve wide-TC" circuit evaluation
We next justify that mixed-masked mAHAT transformer will unroll at least clog" times for large enough n. This transformer will unroll exactly log" N times, where N = n + [(C,)] | the total input length for circuit evaluation instance. Since the size of C, is at least n², we have that N 2 nº. Thus, m transformer unrolls the following number of times:
log" N log" n == c² log" n 2 c log"
Thus, our transformer will umroll a sufficient number of times to solve the wide- TC circuit evaluation problem. It follows that this problem is in mAHAT
Finally, we conclude via Proposition that this mixed-masked transformer can be converted to a corresponding causally masked padded transformer, placing the problem also in AHAT
D.3 Solving Wide-TC Circuit Evaluation with FO-Uniform Circuits
It is immediate that the looped transformer in Corollary 13.1 can be simulated in L-uniform TC Moreover, since Lemma 6 shows looped padded transformers can be simulated by FO-uniform polylog-depth threshold circuit families, we obtain:
Lemma 14. For O, wide- TC circuit evaluation FO-uniform TCd.
Combined with Lemma 12, this implies the following completeness results for wide-TC" circuit evaluation:
Corollary 14.1. For d 2 0, wide- TC circuit evaluation is complete for L-uniform TC² under L reductions.
Corollary 14.2. For d 2 0, wide- T circuit evaluation is complete for FO-uniform TC under L reductions.
E Uniformity Collapse for Circuit Classes
In general, for classes A, B such that A B, B-uniformity often leads to larger classes of languages than A-uniformity, as we have more resources to construct a circuit. However, as the following lemma shows, this is not always the case:
Proposition 6 (Uniformity Collapse). Consider classes A, B of functions and a class XC of polyno- mial size circuit families such that:
1. C A-uniform XC:
2. XC circuit evaluation is in A-uniform XC;
20

---

3. A-uniform XC circuit families are closed under fixed compositions (cf. Appendix B.
Then B-uniformity does not strengthen A-uniformity, i.e, A-uniform XC = -B-uniform XC.
Proof. Since A S B, we trivially have A-uniform XC S B-uniform XC. The rest of the proof will focus the other direction, showing that any language L E B-uniform XC is also in A-uniform XC.
By the definition of B-uniform XC, there exists a function f E B that constructs an XC circuit family {C h=20 that recognizes L. Specifically, f(1")= = C where C₁2 is an XC circuit that checks membership in L over all strings of size n: for E 10" (f(w) = iff E L. The key insight is the following: while [C/ is not necessarily an A-uniform XC circuit family, we can build C on demand using a different, A-uniform XC circuit family (C20020 by leveraging the first preonndition of the lemma, specifically that B C A-uniform XC. We will then leverage the second precondition to construct another A-uniform XC circuit family {Ch, n, Jn.220 that evaluates the built circuit C on the input string We will then use the third precondition compose these two circuit families in order to obtain the final A-uniform XC circuit family { 1220 that recognizes L.
Building Cf2= Since f B, by the first precondition of the lemma, is also in A-uniform XC. We can thus simulate f using an A-uniform XC circuit family. More concretely, there exists a function g E A that, for any n 2 O, maps input 1" an XC circuit Cg that does what f does, i.e., Cg on input 1 constructs the circuit C₁2- Thus, we have g(1)) C% and (1 = C₁₁
Evaluating Cf on wt By the second precondition of the proposition, there exists function E A that, for any n, m 2 O, maps input (1",1") to an XC circuit C.., that evaluates any XC circuit Cn of size m over any input string w of size i.e., h 1 = Chh |w| n.
n,m and Ch n.m (On, w) (.ww) for
Composing builder and evaluator circuits: Now we are ready to construct an A-uniform XC circuit family [ that recognizes L. This circuit family, on input w of length n, computes the following composition of the circuit builder family {C%)n20 and the circuit evaluator family (Ch: nmm20
(w) Ch (C%(1"), w)
(1)
where n = |w| and m = |. We first observe that this composite circuit does, in fact, recognize L. That's because for any input string w of length
(w) = Ch (C%(1"),, w)
Cth n,m (C/, w)
which, by definition, is if and only if w E Thus, Cz recognizees L.
Lastly, by the third assumption this proposition, the circuit family {Ch In20. being a fixed composition of A-uniform circuit families {Ch,,.. In.2200 {Ch]n20. and the identify function (for constructing the second argument w of Chh is also A-uniform.
Proposition 6 may appear surprising on the surface level, but it has quite intuitive interpretation: weaker uniformity provably cannot increase a circuit class that is sufficiently expressive. This has an interesting implication for polylog-depth circuit classes: FO and L-uniform TCd collapse for d 2
Theorem (Uniformity Collapse). For any d 2 1, the following equivalences hold:
FO-uniform ACd = L-uniform ACd = NL-uniform AC
FO-uniform TC L-uniform TC NL-uniform TC*.
Proof. We state the proof for TCd, but everything generalizes for ACd as well. By construction, the following containments hold:
FO-uniform TC L-uniform TCd ç NL-uniform TC
21

---

We will show that NL-uniform TC S FO-uniform TC using Proposition 6, with A = FO, B NL, and XC = wide-TC With A FO, the third precondition of Proposition follows from Proposition 3. We next argue that its first two preconditions are also met:
1. Since d 2 1 and NL is known to be in FO-uniform AC which is contained in FO-uniform TC*. we have NL S FO-uniform TC FO-umiform wide-TC", where the final equality comes from Proposition 5. Thus, the first precondition is satisfied.
2. From Lemma 14, we also have that wide- TC evaluation in FO-uniform TC which by Proposition 5 equals FO-uniform wide-TC". Thus, the second precondition is also satisfied.
We conclude by Proposition 6 that
NL-uniform TC C FO-uniform wide- FO-uniform TC
Thus, for d 2 1, FO-uniform, L-uniform, and NL-uniform TC collapse to the same class of languages.
Notably, the proof of Theorem 3 does go through in the case of TC since it is not known (and not believed) that and NL are in TC
"This be proven analogously for ACd and wide-AC!
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main two results proved in Theorem 1 and Theorem 2.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Lack of empirical support is acknowledged and simplifications made to transformer architecture acknowledged in Section 2.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

All theorems are numbered, cross-referenced, and given full proofs. Relevant definitions are given in Section 2.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
oonooicy))))) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips.coo. wttpccccpppccceeeeececceccccccct /ttpi///ggiiiee/eeeeuubbiiiiii /Cooeeeooeiesseeeeeeeeeee cemmmissiinnn ssionnolll ceiiinnolccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:
Answer: [Yes]
Justification:
No exceptional circumstances.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is foundational. focusing on general theoretical understanding of the computational power of transformers.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No artifacts used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No artifacts released.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "75Z1pYhMmW", "reviewer": "Reviewer_YvVK", "summary": "This paper precisely characterizes the expressive power of transformers with a polynomial number of _padding_ tokens by providing a matching lower bound on their ability to solve $TC^0$ problems. Additionally, the authors show that $O(\\log^d n)$ _looping_ layers enable padded transformers to be precisely characterized by $TC^d$. Using padding effectively enlarges the width of the transformer, while looping effectively increases the depth of the transformer. While the expressive power of padded and looped transformers remains below the expressive power of chain-of-thought (COT) transformers, they are more easily parallelizable and thus offer computational advantages in comparison to COT.", "questions": "1) To my current understanding, Proposition 10.3 in Barrington et al. implies that we can express FO[M$^2$] by using formulas from FO[M, $\\texttt{bit}$], but not the other way around. Could you clarify what \"FO[M$^2$] ... is equivalent to standard FO[M, $\\texttt{bit}$]\" means in this context?\n2) In lines 352-357 in the proof of Lemma 3: Why do we check if $f(w) \\in L'$ instead of $L$?\n3) In Theorem 1 and Theorem 2, do we assume infinitely many padding tokens (given Definition 6), and thus infinite width?\n4) Could you explain what exactly is meant by the phrase \"converge to recognizing NC\" in the context of your theoretical results?\n5) How expensive is padding and looping in practice? How can padding be efficiently parallelized?\n\nBarrington, D. A. M., Immerman, N., & Straubing, H. (1990). On uniformity within NC1. Journal of Computer and System Sciences, 41(3), 274-306.", "limitations": "There is no explicit discussion of limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*: The submission provides novel bounds for transformers with padding as well as looping in terms of circuit complexity classes, which helps compare their expressive power to other transformer architectures. Additionally, Lemma 3 introduces the concept of _reductions_ for analyzing the expressive power of transformers, which might be useful on its own to derive further results.\n\n*Weaknesses*: There are several issues with clarity, which makes it generally difficult to assess the soundness of the submission. While the paper is easy to read, it would benefit from more rigorous definitions and careful proofreading. In several places, the presentation appears imprecise. For example, $\\phi$ is used inconsistently, sometimes as a formula (without being introduced as such), and elsewhere as a layer norm. Additionally, the use of colloquial language and frequent quotation marks around technical terms contributes to ambiguity. For instance, in line 310, why is 'token' in quotes; similarly, line 247 mentions a \"projection,\" and line 40 refers to \"storage space,\" both again in quotation marks; in the proof of Lemma 3 in line 354, the phrase \"very negative\" is vague. Overall, the proofs rely heavily on informal language, which hinders accessibility and undermines precision. Without more rigorous definitions and terminology, the arguments are difficult to follow for me. Lastly, the absence of a dedicated related work section makes it more difficult to situate the contributions within the broader context.\n\nPlease find more detailed remarks below:\n\n- The variable $\\phi$ appears many times in seemingly different contexts:\n    * $\\phi(i)$ in line 111\n    * $\\phi$ in Definition 7, 5(b)\n    * $\\phi(i,j)$ in Definition 8\n    * $\\phi(b_i - 1)$ in line 209\n    * $\\phi(i)$ in line 343\n- Line 123 in Definition 6: What does universal mean in this context, looped?\n- Line 142: \"for\" instead of \"For\"\n- Line 166: \"other\" instead of \"over\"\n- First sentence in Definition 7 should be outside of definition environment\n- Line 211: What is the $\\texttt{bos}$ token?\n- Line 216: What does \"masked unmasked head\" mean?\n- The proof of Lemma 2 is difficult to follow:\n    * Many terms seemingly refer to the same variable: $v$ is a token (lines 240,245), a variable assignment (line 240), an integer (line 246), and a configuration (line 250). \n    * Line 233: Should this be Definition 7 instead of Definition 8?\n    * Could you explain what \"Each token corresponds to a specific assignment of all the variables, which we denote $v$\" means?\n    * Lines 261 and 268: Why do we have $[[P]]^{w,v}$ in line 261 and $P^v$ in line 268?\n    * Lines 265 and 272: What is $v'$?", "was_revised": true, "final_justification": "I did not increase my score since, as also acknowledged by the authors, the paper has some issues with clarity, which makes it difficult for me to judge its overall soundness. However, given the confident review by reviewer FTuT which attests the paper to be \"technically flawless\", I assume that all the proofs were carefully checked and are correct (except for the discussed mistakes in notation). This, together with the novelty and significance of the theoretical contributions, makes me lean towards acceptance.", "rebuttal": "Thank you for your review!\n\nThanks for your careful reading and *feedback on clarity*. To respond to some of your points:\n\n* Regarding $\\phi$, we will standardize it to only refer to the layer-norm hash. We will change Definition 3 to explicitly mention this sense of $\\phi$ (we apologize that it seems to have gotten removed at the last minute) We will change the symbol for formulas in Definitions 5 and 8 to $P$ or $Q$. This will make both aspects of the paper clearer to read.\n\n* In Definition 6, “universal” indeed means “looped”. We will change this. By “bos” we mean a beginning-of-sequence symbol \\$ as defined on page 3. We will update the text to make this clear.\n\n* “Masked unmasked” is a typo and should just be “masked”\n\nRegarding Lemma 2, we will take into account your feedback on clarity, and briefly address here your following question:\n\n> Could you explain what \"Each token corresponds to a specific assignment of all the variables, which we denote $v$\" means?\n\nIf a formula has $k$ variables ranging from $1$ to $n$, there are $n^k$ possible assignments to that vector of variables. We can think about a single assignment $v$ as a tuple in $[n]^k$, or we can think about it as a number between $1$ and $n^k$. What we mean is that we identify each variable assignment with a specific number. Then, token $v$ will represent variable assignment $v$.\n\nWe will also incorporate all the other detailed feedback you mentioned regarding clarity and informal language - thanks for reading carefully! On the use of informal terms, we did that in certain places to make the argument more accessible to broader audience. However, we see that it can result in lack of precision and we will make sure to make the language more precise -- critically in all proofs.\n\n> To my current understanding, Proposition 10.3 in Barrington et al. implies that we can express $FO[M^2]$ by using formulas from $FO[M,Bit]$, but not the other way around… \n\nYour interpretation of Proposition 10.3 is correct, but what we use here is Theorem 10.2, which proves the other direction that $FO[M^2]$ can capture all of $TC^0$. We will update our reference to the Barrington et al. paper to include the relevant theorem.\n\n> In lines 352-357 in the proof of Lemma 3: Why do we check if $f(w) \\in L’$ instead of $L$?\n\nIndeed, have a minor issue with the notation in this paragraph where we flipped L and L’. We will correct it to say that we are checking whether $f(w) \\in L$, which is equivalent to checking $w \\in L’$. Thanks for finding this!\n\n> In Theorem 1 and Theorem 2, do we assume infinitely many padding tokens (given Definition 6), and thus infinite width?\n\nThe number of padding tokens needed in the simulations in Theorem 1, 2, and 3 is naturally a function of the complexity of the underlying $TC^0$, $NL$, and $TC^d$ circuits / algorithms. It’s not infinite, but rather *unbounded* a priori. E.g., if a $TC^0$ circuit being simulated is equivalent to a $FO[M^2]$ formula with $k$ distinct variables, then we need $n^k$ padding tokens (in Lemma 2 and Theorem 1). Since one can define arbitrarily large circuits, their transformer simulation also needs to support correspondingly more (but still polynomially many) padding tokens, i.e., a larger exponent $k$ in $n^k$. Crucially, for every problem, there is a fixed $k$ that works. The subscript $$ in our notation $AHAT^d_*$, representing the union over all $k$, captures this. We will clarify this, in particular that for simulating any *fixed* circuit family, we need only a fixed polynomial degree number of padding tokens.\n\n> Could you explain what exactly is meant by the phrase \"converge to recognizing NC\" in the context of your theoretical results?\n\n$NC$ can be defined as $\\bigcup_{k = 0}^\\infty TC^k$. With $O(\\log^k)$ depth, we showed padded transformers can recognize $TC^k$. So, as $k \\to \\infty$, $O(\\log^k)$ depth (i.e., polylog-depth) transformers can recognize any problem in $NC$. In other words, for any problem in $NC$, there is *some* choice of $k$ such that a $\\log^k$ depth padded transformer will recognize it. We will clarify the discussion around this to make it more precise.\n\n> How expensive is padding and looping in practice? How can padding be efficiently parallelized?\n\nPadding is efficiently parallelizable in practice: in can be thought of as just growing the input with blank symbols, and then making a single call for transformer inference (as opposed to CoT, which requires sequential inference calls to the transformer).\n\nThe practical bottleneck it would run into is the length of the context window, as running a transformer with a long context will run into memory limitations. Some problems like 3SUM considered by Pfau et al. are solvable with a small padding degree $k$, but if a problem requires a larger value of $k$, this could definitely become impractical (the same argument holds for CoT, in addition to the sequentiality of CoT). We will clarify this potential limitation in the text."}, {"review_id": "nKrezeuMIm", "reviewer": "Reviewer_FTuT", "summary": "This paper investigates the expressive power of Transformers when augmented with two parallelizable forms of inference-time compute: padding and looping. The authors provide a precise formal characterization of the class of problems solvable by these models. Their first main result is that fixed-depth, polynomially padded Transformers can recognize exactly the complexity class `TC^0`, a class of highly parallelizable problems. This result resolves an open question, as previous work had only established `TC^0` as an upper bound. The second main result extends this analysis to Transformers that dynamically repeat a block of layers. The paper shows that a Transformer with polynomial padding and `O(log^d n)` looping recognizes exactly the class `L-uniform TC^d`. This establishes a systematic relationship between the depth of looping and the computational power of the model, showing that these parallelizable mechanisms can expand a Transformer's capabilities to encompass the entire class `NC` (the class of efficiently parallelizable problems), a significant increase in power over un-augmented models.", "questions": "1.  **On the Practicality of Padding:** The constructions require `O(n^k)` padding to simulate `k` variables, which can become very large. Could you comment on the prospects for reducing this padding requirement? For instance, are there more compressed ways to represent the variable assignments, or could a model potentially learn to use a smaller scratchpad more efficiently? Is the `n^k` dependency a hard theoretical barrier for your proof technique, or do you see some approaches that can tighten this?\n\n2.  **Bridging the Gap to Soft Attention:** Could you elaborate on the key challenges in extending your results from the AHAT model to standard soft-attention Transformers? The core of your proof seems to rely on precise retrieval and counting via hard attention. What kind of new techniques or assumptions would be needed to show that soft attention can approximate these operations with sufficient fidelity, especially as sequence length `n` grows?\n\n3.  **The Role of Uniformity:** The paper proves equivalence with `L-uniform TC^d`. The appendix notes that this implies `L-uniform TC^d = NL-uniform TC^d`. This is an interesting complexity-theoretic side effect of the analysis. Could you elaborate slightly on why your Transformer construction naturally leads to `L` or `NL` uniformity rather than, for example, the stricter `FO`-uniformity seen in the `TC^0` case? Is it because solving the complete problem (e.g., Graph Connectivity) requires the power of `L`?\n\n4.  **Implications for Architecture Design:** Your results provide a compelling theoretical motivation for using padding and looping. Do you have any high-level thoughts on how these findings might inform future Transformer architecture design? For example, would it make sense to design models with dedicated \"scratchpad\" blocks or explicit looping mechanisms that are more suitable to learning the kinds of algorithms you describe?", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n\n1.  **Significant Impact:** The paper provides a definitive and exact characterization of the expressive power of padded and looped Transformers. This closes an important gap in the theoretical understanding of Transformers and provides a formal basis for exploring alternatives to sequential reasoning methods like Chain of Thought (CoT).\n\n2.  **Technical Quality and Rigor:** The paper is technically flawless. The proofs are carefully constructed, building from the base case of fixed-depth padded Transformers to the more general case of looped models. The authors clearly define their idealized model (AHAT) and leverage its properties to build a rigorous, step-by-step argument. The connection to string logics (`FO[M^2]`) to circumvent the `BIT` predicate issue is original and demonstrates a deep understanding of the relevant literature in both machine learning and complexity theory.\n\n3.  **Clarity of Presentation:** Despite the technical density of the material, the paper is exceptionally well-written. The introduction clearly motivates the problem and situates the work within the existing literature. The main results are stated cleanly, and the proof sketches provide excellent intuition for the formal constructions. Figure 1 is a nice summary of the paper's contributions and how they relate to known complexity classes.\n\n**Weaknesses:**\n\n1.  **Idealized Model:** The analysis is based on an Averaging-Hard-Attention Transformer (AHAT) with masked pre-norm and `O(log n)` precision. While this is a common and necessary simplification in theoretical work, it creates a gap between the theoretical model and the soft-attention, fixed-precision Transformers used in practice. The authors acknowledge this, but the practical implications of their findings hinge on the assumption that these results will translate, which is not guaranteed.\n\n2.  **Lack of Empirical Validation:** The paper is purely theoretical. While the goal is to establish formal limits of computation, the practical feasibility of the proposed constructions remains an open question. For instance, the polynomial padding required (`n^k` tokens) could be prohibitively large for even moderate `k`. The paper would be even stronger if it included a small-scale empirical demonstration or a more in-depth discussion of how these theoretical ideas might be approximated in practice.\n\n3.  **Learnability:** The paper focuses on expressive power (what is computable in principle), not on learnability (what can be learned from data via gradient descent). The constructions are intricate and algorithmic, and it is unclear if a standard training procedure could ever converge to the specific weight configurations required.", "was_revised": true, "final_justification": "Rating stays the same. Oral quality paper in my opinion.\n\nThe paper is of top quality, all the comments are addressed, and I keep my rating of Strong Accept.", "rebuttal": "Thanks for your review! We are happy to hear that you appreciate the technical quality and clarity of our paper as well as its potential for impact.\n\nWe agree that the *practical learnability* of AHAT constructions (with masked pre-norm) is an interesting open question. We will add some discussion either in the main paper or in a limitations section. The major gap between soft attention and AHAT is indeed the ability to implement hard-attention retrieval. For any fixed maximum context length, it is possible to scale the attention head parameters to arbitrarily approximate AHAT attention, but for unbounded context lengths, it seems difficult (and may likely be impossible) to simulate AHAT or hard attention. For this reason, we view AHAT as a mostly mild assumption (suitable for bounded context lenghts) that abstracts away issues with soft attention for simulating hard attention over very long contexts.\n\nRegarding the *practicality of padding*, $n^k$ is indeed a practical barrier if $k$ must be large for some tasks. Small values of $k$ will suffice for some natural tasks tasks: for example, in the 3-SUM task considered by Pfau et al. But, in general, there may be tasks in $TC^0$ that require a large value of $k$, which would lead to a large memory overhead to store a long context window (the same problem would plague transformers with long CoT or chain of thought). More work is needed to assess the tasks for which small values of $k$ would suffice or whether other techniques could be developed to reduce the memory overhead of padding -- we will acknowledge this as a limitation.\n\nRegarding your question about $L$ vs. $FO$ uniformity, we have a brief discussion of this in the appendix after the proof of Lemma 4 (that $\\log^d$ depth transformers are in $TC^d$).\n\nIndeed, for $d \\geq 1$, it can be shown that $\\log^d$-looped transformers would be in $FO$-uniform $TC^d$, similar to how you suggest. The idea is that looping an $FO$-uniform $TC^0$ circuit $O(\\log^d n)$ times can be implemented in $FO$-uniform $TC^d$.\n\nThis has the interesting consequence that $FO$-uniform $TC^d = L$-uniform $TC^d$ by our *uniformity ceiling lemma* (Proposition 2, Appendix C) , just like the $L$-uniform vs. $NL$-uniform collapse noted in the appendix.  In answering your question, we looked closely at the uniformity ceiling argument (Prop. 2) and we think it also goes through when $XC = wide-TC^d$ for $d \\geq 1$, class $B = L$, and class $A = FO$, showing that $L$-uniformity collapses to $FO$-uniformity for deeper $TC$ classes.\n\nNote that this doesn’t go through for $TC^0 (d=0)$ because $L$ is not known to be a subset of $FO$-uniform $TC^0$. Thus, the uniformity ceiling lemma cannot be applied.\n\nThank you for bringing this refinement to our attention! We will add a brief section highlighting these novel results about uniformity and also the novel complete problems we developed to obtain these uniformity collapse results, since these might be of independent interest."}, {"review_id": "TBHb9fdwVc", "reviewer": "Reviewer_KzvS", "summary": "This work investigates the impact of padding tokens on the expressive power of Transformers. Focusing on averaging-based hard attention and masked pre-norm log-precise Transformers, the authors demonstrate that polynomial padding enables the model to represent the class $\\mathsf{TC}^0$. Additionally, they show that combining padding with looping mechanisms further enhances expressivity: $O(\\log^d n)$ looping enables recognition of the class $\\mathsf{TC}^d$, while polylogarithmic looping extends this capability to the class $\\mathsf{NC}$.", "questions": "1. Could the authors provide further discussion on how padding and looping compare to CoT in terms of expressive power (e.g., the differences between the results of this work and those of [1])?\n\n2. Could the authors provide any insights or intuitions on the learnability of the proposed constructions?\n\n[1] Merrill, W. and Sabharwal, A., The Expressive Power of Transformers with Chain of Thought. ICLR 2024.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The work consider the practical techniques, i.e., padding and looping, from a theoretical perspective, offering valuable insights into why these methods can be effective.\n2. It establishes connections between the expressive power of padded Transformers and well-known complexity classes, providing a precise and hierarchical characterization of their representational capacity.\n\nWeaknesses:\n1. The analysis does not compare the benefits and limitations of padding and looping with other reasoning techniques, such as CoT.\n2. The theoretical results focus solely on expressivity and do not address the learnability of the proposed constructions.", "was_revised": true, "final_justification": "The authors have satisfactorily addressed my main concerns in their rebuttal. While the learnability limitation remains, this aspect falls outside the paper's core contributions. Given the overall quality of the work and the response, I maintain my positive score.", "rebuttal": "Thank you for your review! You raise a good point regarding the* comparison of padding and looping with chain of thought*. In the case of $\\log n$ looping vs. CoT, it is now known [1][2]] that transformers with logarithmic CoT steps remain in $TC^0$ whereas log-looped transformers can solve some $NC^1$-complete problems, suggesting an advantage of looping. More generally, the comparison between transformers with $t$ steps of looping vs. $t$ steps of CoT remains open. We will update the paper to discuss this comparison, what is known, as well as the open question.\n\nRegarding *learnability*, we agree this is very interesting, but is beyond the scope of the current work, which we can acknowledge as a limitation.\n\n[1] https://arxiv.org/abs/2503.03961\n[2] https://arxiv.org/abs/2210.10749"}, {"review_id": "7WF6qxeYnp", "reviewer": "Reviewer_KMSi", "summary": "It was observed previously that average-hard attention transformers with logarithmically many bits can only recognize language from TC^0 (which is almost obvious, they have constant number of layers and arithmetic operations that they employ are doable within TC^0). Moreover, if one uses some simple explicit positional encoding, one can show that such transformers belong to the dlogtime-uniform TC^0. \n\nDoes this inclusion hold in the other direction? Intuitively, there is a big obstacle -- transformers have linear size while TC^0 circuits can have arbitrary polynomial size. One of the results of the paper is -- if we are allowed to add polynomially many ``blank'' tokens initially, we obtain a transformer model, exactly equivalent to dlogtime-uniform TC^0.\n\nThe paper goes beyond that and asks -- what about NC, the class of polylog-depth circuits? Just adding polynomially many blank tokens does not seem enough since we still have constant number of layers. The paper suggests to allow a fixed constant block of layers to be repeated polylogarithmically many times. They claim that with this, transformers converge precisely to L-uniform NC.", "questions": "How precisely you define TC^d? If as O(log^d)-depth threshold circuit, then definition 11 in the supplementary material does not make sense to me, because any circuit belongs to some sequence of circuits from TC^d (by making  constant in O(log^d) big enough).\n\nI guess you should for any constant C, d, define the C,d-threshold circuit evaluation problem, where the input circuit has depth at most Clog^d n precisely.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Characterizing dlogtime-uniform TC^0 via polynomially padded transformers seems valid. This is a solid result but maybe not very surprising and not very exciting technically. \n\nAs for the L-uniform NC result, I think there are some technical inaccuracies, but I believe the result should held (at least maybe without precisely equivalence of the hierarchies, just that every language in L-uniform NC can be recognized by a polylog-looped transformer). One non-trivial idea is required here. A naive approach to simulate a polylog-depth circuit by a transformer is to compute each layer of a circuit in a transformer layer. However, in this way we might require to have polylog-many different layers in a transformer, and we just want a loop of a block of a fixed constant number of layers. Instead, the paper constructs a transformer that in a loop, tries to evaluate all gates of a circuit simultaneously, and the gate can be evaluated when all gates that are fed to it are already evaluated. This idea appears in Merrill and Sabharwal 2023a.\n\nSome minor remarks:\nDefinition 1, h is the number of attention heads, and k is their index?\n\nLine 126, in the positional encoding here, n is the initial length or padded one?\n\nLine 176, maybe clarify that ``unique hard-attention transformers''\n\nNames of Sections 4 and 5 are misleading because you forget to mention uniformity conditions there.", "was_revised": false, "final_justification": "", "rebuttal": "> How precisely you define $TC^d$? If as $O(\\log^d)$-depth threshold circuit, then definition 11 in the supplementary material does not make sense to me, because any circuit belongs to some sequence of circuits from $TC^d$ (by making constant in $O(\\log^d)$ big enough). I guess you should for any constant $C, d$, define the $C,d$-threshold circuit evaluation problem, where the input circuit has depth at most $C \\log^d n$ precisely.\n\nIndeed, you’re right that $TC^d$ circuit evaluation is the same as $TC$ circuit evaluation because the constant can be folded in. This is why we have taken the care to define wide-$TC^d$ class of circuits and the wide-$TC^d$ circuit evaluation problem in the appendix.\n\nwide-$TC^d$ is defined as the class of $TC$ circuit families where each family has a fixed $c$ such that depth is at most $c \\log n$ and, crucially, size is **at least** $n^c$. With this additional constraint, wide-$TC^d$ circuits express the same languages as $TC^d$, but the evaluation problem can be solved in $TC^d$ (unlike evaluation of $TC^d$, for the reasons you noted). To see why this constraint helps, note that if we increase $c$ to make a wide-$TC^d$ circuit deep, the length of the circuit serialization must increase, which effectively makes the circuit shallow w.r.t. the total input length for the circuit evaluation problem, upper bounding its effective depth by $c^* \\log^d n$ for some **fixed** constant $c*$ chosen a priori. This circuit then can be evaluated by a $(c^*  \\log^d n)$-depth circuit family (for a fixed $c^*$), which we build for the wide-$TC^d$ circuit evaluation problem.\n\nThank you for raising this important point. We will clarify this and also make the wide-$TC^d$ a numbered definition (after Definition 11) as it’s an important concept that addresses the issue you mentioned.\n\n> Some minor remarks: Definition 1, $h$ is the number of attention heads, and $k$ is their index?\n\nYes, we will note this.\n\n> Line 176, maybe clarify that ``unique hard-attention transformers''\n\nWill do.\n\n> Names of Sections 4 and 5 are misleading because you forget to mention uniformity conditions there.\n\nYou are right. We omitted the uniformity qualifier to prevent the section titles from becoming too long, but we agree it would be better to include it and will update in revisions.\n\n> Line 126, in the positional encoding here, $n$ is the initial length or padded one?\n\nIn discussing this question, we realized that $i/n$ can actually be simplified to $1/i$ embeddings, and all constructions will go through. This works because $1/n$ (where $n$ is the initial input length) can be computed first, and then $\\phi(i/n)$ can be computed as $\\phi(1/i, 1/n)$.\nThis simplifies the conversion from unmasked to masked transformers because $1/i$ encodings can be directly simulated by a uniform causally masked head.  We will update the setup in the paper to use the simpler $1/i$ embeddings and clarify these details. Thanks for your question, which led us to think about this!"}]

Author rebuttal:

Meta-review: **Scientific Claims and Findings**
This paper provides a precise characterization of the expressive power of Transformers augmented with padding and looping, two parallelizable inference-time computation mechanisms. The authors' central claim is that fixed-depth, hard-attention Transformers with a polynomial number of padding tokens can recognize exactly the complexity class $TC^0$. The paper further demonstrates that by incorporating $O(\log^d n)$ looping (dynamically repeating a block of layers), the expressive power is precisely extended to the class $TC^d$. Consequently, with polylogarithmic looping, these models can recognize the entire class $NC$, which represents the class of efficiently parallelizable problems.

**Strengths**
This paper definitively resolves an open question by providing an exact, rather than an upper-bound, characterization of padded Transformers' expressive power, which significantly deepens our understanding of expressiveness of transformer architecture. The reviewers also praise the clarity of the writing.

**Weaknesses**
1. The main weakness of the submission is that the finite precision number system and thus the main function class considered in the paper $AHAT^d_k$ are not defined in the paper. This does not directly hurt the validity of the main result of the paper, that the looped transformers with polynomially many padding can simulate $TC^k$ circuits. However, without a formal and rigorous definition of the function class $AHAT^d_k$, the other direction of equivalence, that circuits can simulate transformers, is ambiguous. The main issue comes from the imprecision about O(log n) precision number system. 

     First, it is clear that without any approximation, it is hard to simulate the embeddings of the transformer using TC circuits with perfect precision, because the \sqrt operation in layernorm ill-defined as rounding is necessary for \sqrt. The average hard attention also allows the transformer to take average of poly(n) numbers, which drastically increases the precision for exact simulation. So the natural fix here seems to define the forward pass of transformer as **first compute exactly and then round to finite precision** for every basic operation such as square root, multiplication and addition over poly(n) numbers. Though I think in principle a rigorous and relatively simple fix based on "exact computation and then round" exists, there are a few subtle issues that remains and I would like the authors to be aware:

     (1). details of the number system and rounding: how do you represent a rational number? is it in the form of p/q, where p,q are integers bounded by poly(n) (so O(log n) bits), or p/2^x, where p,x is integers with absolute values bounded by poly(n) (the latter one is more like floating point numbers)? do you always around to the closest representable number, or your round to any number that is sufficiently close? (but then to make the output a well-defined deterministic function class, you have to show that the potential non-determinism does not output the output token nondeterministic, in some sense, a margin-based analysis is required)

    (2). the (potential) increased complexity of the proof of the main direction -- transformer simulates circuits, due to the existence of rounding. Here a careful control of rounding error and its propagation is needed, especially in the polylog(n) depth case.

    (3). Depending on the representation system the authors choose, the actual needed precision of forward pass could be much higher than O(log n). For example, suppose rational numbers are stored in the form of p/q, where p,q are integers bounded by poly(n) (so O(log n) bits), then the sum of M such numbers could require $\Omega(M\cdot \log n)$ bits to represent. When M =poly(n), the proposed mathematical model of transformers $AHAT^d_k$ might need to work with a much higher precision than O(\log n), which is $\Omega(poly(n))$.

2. Other weaknesses identified by reviewers are including the reliance on an **idealized Transformer model** (Averaging-Hard-Attention Transformer, AHAT) as opposed to the more practical version (finite precision, softmax attantion) and the **lack of empirical validation or discussion of learnability**. The theoretical constructions, which require specific weight configurations and potentially a large number ($n^k$) of padding tokens, may not be achievable through standard gradient-based training or practical for real-world applications. 

**Reasons for Recommendation**
Overall, the work makes a significant contribution to the theoretical understanding of Transformers. By precisely linking the architecture of padded and looped Transformers to well-established complexity classes ($TC^0$, $TC^d$, and $NC$), it provides a theoretical foundation for exploring parallelizable alternatives to sequential reasoning methods like Chain of Thought. The paper's technical depth and the resolution of an open problem make it stand out as a significant advance in the field, if the above main weakness can be addressed.

The final recommendation for this paper is Accept(poster), conditioned on that the authors will give a formal and rigorous definition for the function class $AHAT^d_k$ and rigorous proofs for the both directions of the main results. This is the conclusion that SAC and AC have reached after a long discussion and is based on our impression that a rigorous and relatively simple fix based on "exact computation and then round" exists. It is of course up to the authors to choose their way to fix the current issues, and we expect the authors to withdraw the paper if they cannot make it precise and rigorous. In particular, I recommend that the authors write as explicit about the number system and forward pass of transformers as possible, and try to avoid use big O notations in the key definitions about the function class.
Decision: Accept (poster)