A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
Authors: William Merrill
Ashish Sabharwal
Venue: NeurIPS 2025 poster ()
Keywords: looped transformers
expressivity
state tracking
graph connectivity
circuit complexity
Primary area: theory
TL;DR: We show that slightly increasing transformers' depth with the input length increases their expressive power under standard complexity conjectures.

Abstract: Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational *depth* is bounded. However, prior work treats the depth as a constant, leaving it unclear to what degree bounded depth may suffice for solving problems over short inputs, or how increasing the transformer's depth affects its expressive power. We address these questions by analyzing  transformers whose depth can grow minimally with context length $n$. We show even highly uniform transformers with depth $\Theta(\log n)$ can express two important problems: *recognizing regular languages*, which captures state tracking abilities and was known to be expressible only by an unconventional, non-uniform model of transformers, and *graph connectivity*, which underlies multi-step reasoning. Notably, both of these problems cannot be expressed by fixed-depth transformers under standard complexity conjectures, demonstrating the expressivity benefit of growing depth. Moreover, our theory quantitatively predicts how depth must grow with input length to express these problems, showing that depth scaling is more efficient than scaling width or chain-of-thought steps. Empirically, our detailed experiments designed to bridge the expressivity vs. learnability gap reveal that our theoretical depth requirements for regular language recognition closely match the practical depth requirements for successfully training transformers. Thus, our results clarify how depth affects a transformer's reasoning capabilities, and provide practical guidance for effective depth selection for sequential reasoning.

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
William Merrill" Allen Institute for Al wil willm@allenai. org
Ashish Sabharwal Allen Institute for Al ashishs@allenai.cmm org
Abstract
Recent theoretical results show transformers cannot express sequential reasoning problems over long inputs, intuitively because their computational depth is bounded. However, prior work treats the depth as constant, leaving it unclear to what degree bounded depth may suffice for solving problems over short inputs, or how increasing the transformer's 's depth affects its expressive power. We address these questions by analyzing transformers whose depth can grow minimally with context length We show even highly uniform transformers with depth O(log n.) can express two important problems: recognizing regular languages, which captures state tracking abilities and was known to be expressible only by unconventional, non- non-uniform model of transformers, and graph connectivity, which underlies multi- step reasoning. Notably, both of these problems cannot be expressed by fixed-depth transformers under standard complexity conjectures, demonstrating the expressivity benefit of growing depth. Moreover, our theory quantitatively predicts how depth must grow with input length to express these problems, showing that depth scaling is more efficient than scaling width chain-of- chain-of-thought steps. Empirically, detailed experiments designed to bridge the expressivity vs. learnability gap reveal that our theoretical depth requirements for regular language recognition closely match the practical depth requirements for successfully training transformers. Thus, our results clarify how depth affects transformer's 's reasoning capabilities, and provide practical guidance for effective depth selection for sequential reasoning.
Introduction
line of recent work analyzing the intrinsic computational power of transformers, the neural architecture behind today's ' immensely successful large language models (LLMs), has established that, with fixed depth, transformers cannot express many simple problems outside the complexity class TC", including recognizing regular languages and resolving connectivity of nodes in graph (Merrill and Sabharwal, 2023a; Chiang et al., 2023). These problems conceivably underlie many natural forms of sequential reasoning, such as state tracking (Liu al., 2023; Merrill et al., 2024) and resolving logical inferences across long chains (Wei et al., 2022). Thus, these results suggest inherent limitations on the types of reasoning transformer classifiers can perform. Yet, these findings come with an important caveat: even if transformers cannot solve such problems exactly for inputs of arbitrary lengths, they may still be able solve them over inputs up to some bounded length. This perspective, coupled with the fact that treating depth as fixed is crucial to prior analyses placing transformers in TC motivates two related questions about depth as an important resource for transformer, in relation to the context length over which it reasons:
1. Bounded Context: If fixed-depti transformers cannot theoretically express certain problems over unbounded context lengths, can they still express them over bounded but still practically
"Work partially conducted as PhD student at New York University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

"large enough" contexts? Can we quantitatively characterize the context length up to which transformers are effectiive for different problems as a function of their depth?
2. Dynamic Depth:
Can minimally scaling the depth of transformer allow it to solve such problems for arbitrarily long inputs? How does this compare in efficiency to scaling width (i.e., model dimension) or scaling inference-time compute via chain-of-thougle steps?
We address these questions by analyzing the expressive power of "universal" transformers (also called "looped" transformers) where a fixed model is given dynamic depth by repeating a block of middle layers variable number of times (Dehghani et al., 2019; Yang et al., 2024; Geiping al., 2025). We capture the regime where depth grows minimally with context length, with the middle layers repeated (log n) times on contexts of length We prove that even such highly uniform transformers, when allowed log-depth, can recognize regular languages and solve graph connectivity, two important reasoning problems known to be beyond fixed-depth transformers (Merrill and Sabharwal, 2023a). Our core technical contribution enabling this is Lemma 1, that fully uniform transformers can compute division and remainder of small integers. This not only obviates the need for non-uniformity and special positional encodings relied upon in prior work, it is also an interesting finding on its own.
Our result has two interesting interpretations. First, it directly shows that, by dynamically in- creasing their depth as (llo n) on inputs of length n, one can construct transformers to solve regular language recognition (Theorem 1) and graph connectivity (Theorem 2) for arbitrary context length. In contrast, chain-of-thouge (CoT) steps, used for additional test-time com- pute by newest LLMs such as OpenAI ol (OpenAI, 2024) and DeepSeek-RI (DeepSeek AI, 2025), must be scaled superlogarithmicaly (Theorem 4) to solve these problems, and width must be scaled superpolynomially (Theorem 3), as shown in Figure 1. Thus scaling depth more efficiently allows solving these reasoning prob- lems compared to scaling width or using CO'.
Depth, width, and CoT efficiency for regular language recagrition
requited respurce
300
resource
width
CoT steps
200
1000
200
500
context longth
Figure I: To recognize a regular language over inputs of length n, the depth of a universal trans- former can grow (log n) by Theorem 1. On the other hand, width must grow superpolynomially (Theorem 3), and the number of chain- thougut steps must be superlogaritmmic (Theorem 4). The precise depth and width coefficients plotted here were obtained experimentally in Section 7.
Second, a universal transformer unrolled fixed (independent of input size) depth d is special case of a standard d-depth transformer, namely one with a highly uniform structure (pa- rameters shared across layers). Thus, our result shows that standard transformers with a fixed depth d can recognize regular languages (Corollary 1.2) and solve graph connectivity problems (Corollary 2.1) as long as one cares only about bounded inputs of size 20(d), This allows us to quantify how many layers are necessary for a desired input size. For instance, Corollaries 2.1 and 1.2 imply that with a depth of only 32, such as in LLaMA 3.1 7B (Meta AI, 2024) and OLMo 7B (Ai2, 2024), transformers can recognize regular languages up to strings of length 107 and solve connectivity for graphs with up to 128 vertices. A depth of 80 (such as in LLaMA 3.1 70B) makes these input size limits practically unbounded: strings of length up to 440K and graphs with up to 2.1B vertices. Empirically, our experiments supplementing our theoretical findings demonstrate that scaling depth as Ollog n.) is necessary and sufficient for learning to recognize hard regular languages." 3
We hope these findings serve as actionable guidance for practitioners choose effective model depths for reasoning over long contexts, and motivate further exploration of dynamic depth as an inference-time compute strategy for transformer based LLMs.
'While Liu et al. (2023) provided a similar result, their construction relied heavily on an unconventional, non-uniform transformer architecture, requiring a different set of model weights for each input length. In contrast, our result holds in a stronger setting of highly uniform transformers where model weights are not only tixed (independent of input length) as in practice but even shared across blocks of layers, enabling effective inference scaling. Our formal model incorporates standard architectural choices like residual connection and layer norm. We supplement our stronger theoretical findings with matching empirical lcarnability results. Code: https:/ //s:::///e thub. wtwc jopt/t//ott//dd peadddproollm/eeeee /eee/willll hwtp//wwlll/oo////////e haamm//oooo/oo hopthhlog--a depth.

---

2 Preliminaries: Universal Transformers
We consider (s, unnivessll transformers, which are defined to have a fixed initial layers at the start, a sequence of layers that is repeated some number of times based on the input length, and a sequence of fixed final/terminal layers. Thus, an (s,r,,))-uiverss transformer unrolled d(n) times for input length n has a total of s rd(n) + layers. Geiping et al. (2025) empirically explored such transformers for scaling test-time computation for reasoning problems. A standard d-layer transformer is (d, 0, -uniiversal (equivalently, (0, O, d))universal), while a standard universal transformer (Dehghani et al., 2019; Yang et al., 2024) is (0, 1, O)-uiivrrsl.
Definition 1. A decoder-only (s, r, -nniverrlll transformer with heads, d layers, model dimension m (divisible by h), and feedforward width w is specified by:
1. An embedding projection matrix E : Σ QTH and positional encoding function π N Q"", which we assume separates from other indices (Merrill and Sabharwal, 2024);
2. A list of s "initial" transformer layers (defined under "Transformer Sublayers" below);
3. A list of r "repeated" transformer layers;
4. A list of f. "final" transformer layers;
5. An unembedding projection matrix that maps vectors in QT logits in Q!2
We next define how the transformer maps a sequence W1 ... Wn Σn an output value y E Σ; to do so, we will always specify that the transformer is unrolled to a specific depth function d(n), which we will consider be d(n)) [log n The computation
inductively defined by the residual stream h;: a cumulative sum of all layer outputs at each token i. In the base case, the residual stream h; is initialized to hς E( w:) ) + (i)). We then iteratively compute + rd(n) + t more layers,
deciding which layer to use at each step as follows:
s-layer E
illess
L =
r-layer ((e- - 8 1) mod +1 if < L $ rd(n)
t-layer f-s rd((n)
otherwise.
We then compute hf..... hy = L'(hh--
"t.lf=",...,h, ......,,,!! by first computing the logits h U. where e" = 8 + rd(n) + 1, and then selecting the token with maximum score. We can identify special token in E with "accept" and say that transformer recognizes language L if, for every w E Σ", it outputs "accept" and only if u E L.
The transformer output is a token determined
An (s, r, -)ttanssfrrerr unrolled to some fixed depth can be viewed as a "uniform" special case of fixed-depth transformer. Thus, constructions of dynamic-depth transformers (depth d((n) for inputs of length r)) imply that, given any bounded context length N. there also exists a fixed-depth transformer with depth d(N) for the task at hand. The fact that this can be done with a looped transformer with dynamic depth is, in fact, a stronger condition that shows the construction is uniform. which is formally important as non-uniform models of computation can have very strong and unrealistic power (cf. Merrill et al., 2022). In this way, our results about looped transformers will provide insights about standard, non-looped transformers with bounded context lengths.
Transformer Sublayers. To make Definition 1 well-defined, we will next describe the structure of the self-ateentoon and feedforward sublayers that make up the structure of each transformer layer. Our definition of the transformer will have two minor differences from practice:
1. Averaging- attention (a.k.a,, saturated attention): attention weight is split uniformly across the tokens with maximum attention scores.
2. Masked pre-norm: We assume standard pre-norm (Xiong et al., 2020) but add learned mask vector m E 1T that can select specific dimensions of the residual stream per sublayer.
Under masked pre-norm, the sublayer input will be read as sequence of normalized residual stream values 2; = fotrr__ormmr___ m O h;), where @ is elementwise product and layer-norm can be standard layer-norm (Ba et al., 2016) RMS norm (Zhang and Sennrich, 2019). The sublayer then maps Zi,...,,, 2, to a sequence 6,...., 5n, and updates the residual stream as h = h; + +,,
Definition 2 (Self-attention sublayer). The self-attention sublayer is parameterized by mask m E QTh, output projection matrix W 0mm -> Q and, for < k S h, query, key, and value matrices Q K* V*, each of which is projection from Q" to /m//h/
FFollowing computer science conventions, we let log A log, n.
3

---

Given input z, the self-attention sublayer computes queries q: Q'z,. keys k; = K*z, 2, and values
V; Zzz, Next, these values are used compute the attention head outputs:
lim exp(1/T kg,kk),))
a
where Zi
Σ exp (1/T k.kk,,))
Zi,k
and c = for causal attention and с = for unmasked attention. The - 0 limit implements averaging- attention: all probability mass is concentrated on the indices j for which the attention score is maximized. This idealization is similar to assuming the temperature of the attention is large relative to the sequence length n. Finally, the attention heads are aggregated to create an output the residual stream d; W concat (at.)... ag.h).
Definition 3 (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 ReLLU(W..)
Positional Encodings. We will assume no positional encodings (Kazemnejad et al., 2023), but that there is beginning of sequence (BoS) symbol at the start. As described by Merrill and Sabharwal (2024), our constructions will generalize to any positional encoding as long as either BoS is provided or the first token's 's positional encoding is linearly separable from all other positional encodings.
2.1 Memory Management Universal Transformers
A technical challenge when working with universal transformers that add values the residual stream is that if one is not careful, outputs from the previous iteration of a layer may interfere with its computation at later iteration. This necessitates "memory management" of individual cells in which the transformer stores values. In particular, any intermediate values stored by a layer must be "reset" and any desired output values must be correctly updated after use in subsequent layers.
Appendix A discusses detail how (, 1} values can be stored directly in the residual stream, while a general scalar can be stored either as xf(2) = (z, 1,, 1) in its unnormalized form or as in its normalized form ("layer-norm hash"; ef. Merrill and Sabharwal, 2024). Importantly, however 2 is stored, when it read using masked pre-norm, we obtain o(2). In Appendix A, we show how numerical values represented using & or 6 can be easily written (Lemma 4), read (Lemma 2), and deleted (Lemmas and 6) from the residual stream. We will leverage these operations heavily in our theoretical constructions.
the unit vector ((2) 1/v2 v22//V22
2.2 Numerical Datatype and Precision
Our constructions will involve working with scalars used as pointers to token positions, which will be stored in and retrieved from the residual stream (as discussed in Section 2.1). We thus need ((logn) bits of precision. We now formalize the underlying datatype use for our constructions.
We assume scalars are encoded as strings in (0, 1},, with p = c clog for some fixed > Note that model parameters in our fully uniform setting cannot depend on but activations can. We assume there is some datatype D, that assigns numerical semantics for each string in {0, 13P, For x E R. let [æ]r, be rounded into μ. i.e., the bitstring whose numerical value in D. is closest to (breaking ties in favor of the higher value).
Our constructions will be agnostic to the underlying details of Dy. Instead, we will minimally assume that, for some fixed c, all arithmetic operations in the transformer computation graph (addition, multiplication, division, exp, and layer-norm) are p-precise for porps 2 c log in the following sense:
Definition 4 (p-Precise Operations). Let f : R - R be an operation with p- p-precision realization m + Dr- We say I is p-precise if, for any #1, Fh E IR exactly representable in ID,,,
[f( xx)]n, f(m=l,,,..,,__ll))))
To apply this definition, we view the summation attention heads as an n-ary operation. We also view layer-norm single operation from p. - m

---

Definition 4 is naturally satisfied by the nog-precision transformer model formalized by Merrill et al. (2024, Section 2.2 and Appendix A) and used in earlier work (Merrill and Sabharwal. 2023a.b), as long as sufficient precision is used internally to compute attention and layer-norm precisely. It is an open question how much precision is required by the internal primitive operations of summation and layer-norm to guarantee their output is (c log -precise. We intentionally abstract away these low-level details here, especially because, in practice, additional precision is typically allocated in any case for attention and layer-norm computation (Micikevicius et al., 201 8; Ai2, 2024).
Finally, we briefly note how Definition relates to other datatype models. Chiang et al. (2023) propose a peapmomial-prriiiiii rational datatype, which satisfies Definition 4 because the first clog bits (and potentially more) are correct. In contrast, finite- precceeoeeiioonn transformers do not satisfy Definition 4 because only ((1) bits are correct. In particular, while the mixed- -rexciiie model of Yang et al. (2025) can precisely represent attention, cannot store (c n--biit values the residual stream or as the output of layer-norm. It therefore does not satisfy Definition 4 or suffice for our constructions.
3 Fixed Depth Transformers Can Divide Small Integers
A useful primitive for coordinating information routing in a dep-h transformer will be dividing integers and computing remainders. We therefore start by proving that transformers can perform integer division for small numbers, which will be useful tool for our main results. Specifically, we show that given a non-negative integer a; no larger than the current position i, one can compute and store the (normalized) quotient and remainder when a; is divided by integer m. This effectively means transformers can perform arithmetic modulo m for small integers.
Lemma 1 (Division). Let ai, by, C, m.m.& E Z2 be such that a, = b.m + e, where a S. and q < m. Suppose (i)), (m)) and o(a.) (or v(as)) are present in the residual stream of a transformer each token i. Then, there exists a block of 7 transformer layers with causally masked attention and masked pre-norm that, on any input sequence, adds (bb.) and ((c;) to the residual stream at each token i.
The overall idea is as follows. In the first layer, each position i outputs an indicator of whether it's multiple of m. It also adds Φ(j) to the residual stream such that is the quotient i/m if is a multiple of m. In the second layer, each position attends to the nearest position j < that is a multiple of m and retrieves the (normalized) quotient stored there, which is j/m [i/m]. J. It adds this (normalized) quotient in its own residual stream. We then use Lemma 7 ($A.3) to construct a third layer that adds a(i 1) and s(i 2) to the residual stream. A fourth layer checks in parallel whether the quotient stored at matches the quotients stored at i - and i 2, respectively. In the fifth layer, position i counts the number of positions storing the same quotient as i, excluding the first such position. Finally. in the sixth layer, position attends to position ag to compute and add to the residual stream @( [a. /mm] (which is o)b;)) and d(a, - m mla/ [a.mm]] (which is ((c;)). We next describe a detailed implementation of the construction, followed by an argument of its correctness.
Proof.
Construction. The first layer uses the following attention head. The query position i is % = o(i, m) = ő(i/m) computed via Lemma 3 ($A.1) leveraging the assumption that (1) and (m) are present in the residual stream. The key and value at position j are kj Uy = Φ(j) Let h = +()) denote the head's 's output. The feedforward sublayer computes e; [lhh (ii/m)) using Lemma 8 (scalar equality check, $A.4) on the first coordinate of h and d(i/m) By Lemma 9 ($B). e, = 1 and only if is multiple of m and, if e, 1, then h ((//m), i.., it represents the quotient i/m. We store h:] = <(i/m) and to the residual stream.
The second layer uses a head that attends with query qi = (1, 1). key k, = (ey, [d())oo). and value ,U h/: both ej and h can be read from the residual stream using masked pre-norn This head attends to all positions j < that are multiples of m (where e, 1). with (p()]o, the first component of ((j). serving as a breakin term for breaking ties in favor of the nearest multiple of m. Lemma 10 (SB) shows this head outputs h? p( (([(1//// mm)] I), which store in the residual stream.
The third layer uses Lemma 7 ($A.3) to add Φ(i - 1) and d(i - 2) to the residual stream at position i.
$ As described in $8, a component will be added to the second layer to reset intermediate memory cells used in the first layer to 0 (this will happen analogously in later layers, but we will omit mentioning it).
5

---

In parallel for k E {1,2}. the fourth layer attends with query q: = o(i - k), key k -[i), and
value ; {iimmm) to retrieve the quotient stored at position k. It uses Lemma 8 (SA.4) on the first coordinate to store in the residual stream a boolean Dy = ([((li/m)] = @(l(i k)) ()),
indicating whether the quotient stored at i matches the quotient stored at - k.
In the fifth layer, position i attends with query qi (o(Li/m]), key k (ø(li/m) bJ), and value 8j <(h)) = oi mod m) as proved in Lemma 11 ($B).
b3g When the output h of this layer is read through layer norm, it produces
The sixth layer attends with query y <(a,), key K5 o().. and value Uy = (Li//L], Φ(j mod m)) (from layers two and five) to compute (<b( [/ss/m]), <b mod m)), which equals (o(b;), d(c.)).
The seventh and final layer cleans up any remaining intermediate values stored in the residual stream, setting them back as per Lemma 8. This is possible because all values are of the form o(x) or boolean, which means adding (t( to the residual stream will reset the corresponding cell to 0. C
Our division construction is somewhat similar to the modular counting construction from Strobl et al. (2024), though the tools and underlying assumptions are different. Specifically, their approach relies on nonstandard position embeddings whereas ours uses masked pre-norm.
4 Log Depth Enables Recognizing Regular Languages
Constant-depth transformers cannot recognize regular languages, a natural task closely related to state tracking (Liu et al., 2023; Merrill et al., 2024). Liu et al. (2023, Theorem 1)e show that variant of log-depth transformers can recognize regular languages using an associative prefix-sum construction (ef. Hillis and Steele Jr, 1986; Blelloch, 1990). However, it is, prima facie, unclear whether the fully uniform model of transformers we study where the parameters cannot change at all with n n-can can implement their construction for key reasons:
To handle information routing, Liu et al. (2023, Page 44) require parameters that are not fully uniform, meaning they depend on the input length and depth. This leaves it unclear whether a single transformer (with a fixed set parameters) could solve the task across all input lengths. In other words, their work leaves it unclear whether single transformer could implement the approach in a way that generalizes to inputs of any length. 2. Liu et al. (2023) also make several simplifications to the transformer architecture: they add ntn-standard positional embeddings and remove residual connections and layer-norm. While one could adapt their construction to handle residual connections, is not clear how to do this while also making their construction uniform, which requires proper memory management of cells in the residual stream (Section 2.1).
1.
Our result, using Lemma 1, addresses both of these weaknesses. It shows, for the first time, that a single transformer with fixed parameters (w.r.t input length n) can recognize strings of any length; moreover this transformer does not require specific positional encodings, allows for layer-norm (in fact leverages it), and allows for residual connections while remaining fully uniform.
Theorem (Regular Language Recognition). Let L be regular language over Σ recognized by (non- dettermdttiiiiiiccc finite automaton with states Q. Let $ & E. Then there exists a causally masked (0, 8, 9) -univerrllll transformer with
model dimension TINFA 2) or MIDFA = O(IQ) log Q1) if deterministic; feedforward width WNFA = 0 or WDFA = 0(2 Ql log (ol) if deterministic;
that, on any string w8, recognizes whether L when unrolled to [ogg [w] depth.
Proof in Appendix C. Theorem reveals that rumning transformer to O n) depth inputs of length n unlocks new power compared to fixed-depth transformer, assuming TC of NC!. If we do not care that the construction uniform across layers, we can simplify 8-layer block that determines activeness to 1 layer: we simply hardcode the layer index l and use single transformer layer to compute i mod f. Thus, the non-uniform construction results in a shallower transformer family:
"Saunshi et al. (2025, Theorem 5.1) also give log-depth transformer construction for the regular language recognition problem. It however, not fully uniform as positions encoded with vectors of length O(log rt).

---

Corollary 1.1 (Regular Language Recognition, Non-Uniform). Let L be regular language over Σ and $ & E. There exists a family of causally masked transformers {TaI== where T, has 4 4[log2 n| + 5 layers such that, on any string w$ of length n, Tn recognizes whether w E L.
These results can be extended beyond regular languages: if a b-layer transformer can perform some binary associative operation @ : X x X - X, then one can construct an (bblog layer transformer that computes the iterated version on values, I1 @ I2 ... @ 2n X. One example is iterated matrix multiplication. For matrices from a fixed set (e.g.. l x k boolean matrices), Theorem 1 already shows that this task can be performed. However, if the matrices are not from fixed set (e.g.. matrices over Z or Q or whose shape depends on n), then it is unclear whether log-depth transformers can solve the binary multiplication problem, and thus whether they can solve the iterated version.
Fixed Depth and Bounded Length Inputs. Interestingly, while Theorem and Corollary 1.1 are about log-depth transformers, they can be turned around to infer bounds on the input length up to which fixe depth transformers (i.c., depth fixed w.r.t. input length) can recognize regular languages. Specifically, given any regular language L and fixed d, Corollary 1.1 implies that there exists depth d transformer that can recognize strings w E L as long as 4 [[ogg//w]] + I d, which is satisfied if (1 + logyluc) /wl) + 5 S d, i.c., [w| S 2
Corollary 1.2 (Depth Scaling for Regular Language). Let T. be regular language over E and $ & Σ. For any d N, there exists a causally masked d-layer transformer that, on any string w$ of length at most 2 9) + 1, recognizes whether
L.
An analogous result holds for universal (i.e., shared parameter) transformers from Theorem 1.
5 Log Depth Enables Graph Connectivity
In the graph connectivity problem (also referred as STCON or the reachability problem), the input is a graph G. along with a source vertex and target vertex t. The task is to determine if G has a path from & to l. This a core problem at the heart of many computational questions in areas as diverse network security, routing and navigation, chip design, and-perhaps most commonly for language pondels-mutiissee logspace Turing machines (Reingold, 2008; Immerman, 1998), which means that, under common complexity conjectures. it cannot be solved accurately by fixed-depth transformers, which can only solve problems in the smaller class TCº. However, graph connectivity can be expressed by log-depth threshold circuits (TC', Barrington and Maciel, 2000), which opens up a natural question: Can log-depth transformers, which are in TC solve graph connectiviry?
reasoning. This problem is known to be complete for the class of
Sanford et al. (2024) provide results showing that non-uniform log-depth transformer with arbitrarily powerful feedforward nets can solve variants of graph connectivity. We prove that even a fully uniform deg-depth transformer can solve graph connectivity (proof sketch below, full proof in Appendix D):
Theorem 2 (Graph Connectivity). There exists (17,2, 1) -uniierrrall transformer T with both causal and unmasked heads, fixed model dimension m, and fixed feedforward width w that, when unrolled (directed undirected) graphs over vertices: given the
[logg n)] times, solves connectivity n x n adjacency matrix of a graph G, n² padding tokens, and s,t E {1....n} in unary, T checks whether G has a path from vertex to vertext. t.
Proof Sketch. We will prove this for the more general case of a directed graph G over n vertices. Let A E {0, 1 be G's adjacency matrix. The idea is to use the first n² tokens of the transformer to construct binary predicates Be(i, j) for E {0, I,..., Ilo...,,oonn n capturing whether has a path of length at most 2 from i to j. To this end, the transformer will use the n² padding tokens to also construct intermediate ternary predicates Cr k) for & E (1, (1...., [log n]] capturing whether G has paths of length at most 2 from i to k and from k to j. These two series of predicates are computed from each other iteratively, as in standard algorithms for graph connectivity:
Bo(i.j) + A(i,j) v vi=j Cet1 k: > B,(i, B.(k.) (i+i( > 3k s.t. Czi k)
(1)
(2)
"The inequality holds since Corollary 1.1 generalizes to show I' recognizes all strings of length
7

---

The crucial part is to construct a transformer that correctly operationalizes the computation of predicates Bg and Cr. The input to the transformer is the adjacency matrix A represented using n² tokens from {0, 1. followed by n² padding tokens D, and finally the source and target nodes 8, E {1, ,....., n) represented in unary notation using special tokens a and b:
A1, 1 12,1...
A2,
An.1
Ann
72
Let N = n² + + + + t, the length of the input to the transformer. The first n² token positions will be used to compute predicates Bj, while the next n² token positions will be used for predicates Ce.
Initial Layers. The transformer starts off by using layer to store 1 1/N, n, n², 8, and & in the residual stream at every position. It then uses the next 15 layers to compute and store in the residual stream the semantic "coordinates" of each of the first n² + n2 token position, namely, (i. j) for each of the first n positions p in j and (i, j, for each of the next n² positions p = n + (in? + kn j)- Finally, layer 17 of the transformer computes the predicate B) at the first n² token positions.
Repeated Layers. The repeated layers alternate between computing the C₁ and the Be predicates for É E {I..... [log ].]. The idea is compute Ce k) in the n padding tokens by attending to positions (i. k) and () and retrieving BB- (i, k) and B (k. Similarly, Be(ū,j) is computed the n² input positions via uniform attention over padding positions (i, K', j)) that store Celi, K, :))-
Final Layers. Finally, in layer foo n + 18, the final token uses a head that attends with query (Ø(s), ((()) corresponding to the source and target nodes and / mentioned in the input, attending solely to the position with coordinates (s, t), and retrieving the final value Bloog n1 (s, t).
Thus, while NC¹ circuits (which have log depth) cannot solve graph connectivity unless NC² = NL, log-depth transformers can.
Fixed Depth and Bounded Length Inputs. As for regular languages, this result also provides a concrete input length bound up to which fixed-depth transformer can solve this problem, namely when 18+ + 2 2[log, n < d. which is satisfied if 18 + 2 (1 + log2 n) I d, i.c., n S 2d2-20)/2
Corollary 2.1 (Depth Scaling for Graph Connectivity). For any E N, there exists a d-layer transformer with both causal and unmasked heads that, on any graph with most 2 vertices. solves the connectivity problem.
6 Comparing Scaling Depth to Scaling Width or Chain of Thought
Our results show that looping layers enables transformers to solve problems likely (conditionally under the conjecture that TC" F NC¹) outside TC We now consider how looping compares in expressive power to other ways to add computation to transformers. Rather than increasing depth by repeating layers, one can increase transformer's width via a larger model dimension (Definition 1) or padding tokens (Pfau et al., 2024). Whereas slightly increasing depth likely expands expressive power beyond TC we show that achieving expressivity beyond TC via width likely requires superpolynomial width, which is intractable. In contrast repeating layers, another way to extend inference-time computation is using chain-of-thought (CoT) steps. We thus compare the expressive power achieved repeated layers with CoT steps.
Wide Transformers with Fixed Depth Remain in TC Our Corollaries 2.1 and 1.2 show that minimally growing a transformer's depth allows it to express key problems that are likely outside TC In contrast, Theorem (which extends Merrill and Sabharwal (2023a); for completeness, Appendix gives a sketch) shows that, if depth remains fixed, width must increase drastically with sequence length to enable expressive power outside TC
Theorem (Width Scaling). Let T be a fixed-depht transformer whose width (model dimension or padding tokens; Pfau et al., 2024) grows at most polynomial in and whose weights on input length (to accommodate growing width) are computable in L. Then T can be simulated in L-uniform TC
Thus, to solve reasoning problems outside TC over a context length n, growing depth is much more efficient than growing width. Of course, there may be other types of problems (c.g., those that are
8

---

context (cg SC3NO)
contoxt langt
24
depth
width Dog scale]
Figure 2: Strong linear fits imply theory/experiment match for modeling the impact of depth (left, d = 4.8 log, n 15.8 with ,2 0.93) and width (right, 7.2 log2 w 41.7 with r 0.98) on effective context length for the As state tracking task, canonical hard regular language recognition problem. As predicted by Theorems and 3, recognize strings of length n, depth only needs to increase minimally oc log n while width must increase drastically as exp(O(n))
knowledge intensive or very parallelizable) where growing width might be more important than growing depth. Petty al. (2024) provide an interesting empirical investigation of this choice on language modeling, semantic parsing, and other tasks.
Transformers with Logarithmic Shain-of-Thoughe Steps Remain in TC Merrill and Sabhar- wal (2024, Theorem 4) analyze the power of transformers with Olog CoT steps, showing is at most L. However, we have shown that transformers with Ollog depth solve directed graph connectivity, which is NL-complete: this suggests growing depth has some power beyond growing CoT unless NL. In fact, the Ollog n) CoT steps result can be strengthened (Li et al., 2024, Figure 10; for completeness, Appendix gives sketch) an upper bound of TC
Theorem (CoT Scaling). Transformers with O(log n) thain-offthought steps can only recognize languages in L-uniform TC²
Thus, while giving a model O(log n) CoT steps does not increase its expressive power beyond TC our Theorems 1 and allow O(log n) to solve key problems that are (likely) outside TC". This demonstrates an advantage of dynamic depth over CoT as form of inference-timg compute for reasoning problems including regular language recognition and graph connectivity. It would be interesting to explore this comparison more generally for other problems.
7 Experiments: Learning to Recognize Regular Languages
Our theory characterizes the depth and width required to express regular language recognition and graph connectivity. Specifically, Theorem predicts that recognizing regular languages over strings of length is empirically possible with depth proportional to log On the other hand, Theorem predicts that the width would need to scale superpolynomially. Here, we aim to empirically measure how much depth and width transformers require in practice when trained to recognize regular languages. We will find that expressibility and learnability are highly aligned here: transformers with log depth learn to recognize regular languages, whereas width must increase superpolynomially with n. Moreover, we can empirically quantify the constant factors these relationships.
We report
extensive set of experiments to address these questions, training models of different depths and widths on the AG state tracking task (Merrill et al., 2024), which is a canonical testbed for hard regular language recognition (Theorem 1). The input to the task is sequence of elements in As (the group of even permutations over 5 elements), and the label at each token is the cumulative product of previous permutations up to and including that token (which is itself an element of As).
We train several (non-universal) transformers with the same architecture used by Merrill et al. (2024) on 100 million A5 sequences of varying lengths up to 1024. To understand the impact of depth and width in controlled way, we train two series transformers: the first with width fixed to $12 and depth varying in {6, 9, 12, 15, 18, 21, 24), and the second with depth fixed to 6 and width varying

---

in {128, 256, 512, 1024). See Appendix F for further details about our training procedure. After each model is trained, we measure accuracy at each token index from 1 to 1024 and define n as the maximum token index at which the model achieved at least 95% validation accuracy. As we trained several seeds with the same depth and width, we aggregate these results across all models with the same depth and width by taking the best- best-performing (max n²) model. We then plot n", which represents the effective context length up to which a model can solve the Ar, problem, as a function of either depth or width, holding the other variable fixed. We then evaluate if the predicted theoretical relationships between depth, width, and context length hold via an r² statistic.
When varying depth (left plot), there is very strong positive correlation (r²² = 0.93) between model depth (x-axis) and log n* (y-axis. log scale). the effective (log) context length till which it can solve problems with high accuracy. When varying width (right plot) there an even stronger positive correlation (r² 0.98) between log width (x-axis, log scale) and n² (y-axis). These results provide strong empirical support for our theoretical predictions that, to recognize regular languages over strings of length n, increasing depth logarithmically in n will suffice (Theorem I), but width must increase exponentially in n (Theorem 3). Figure 2 also gives us a strongly predictive functional form to quantify the impact of scaling depth or width on the effective context length for regular language recognition. The empirical slope for the depth relationship is is 4.8 layers per log tokens. This is less than the slope of 8 derived for universal transformers in Theorem 1, but slightly greater than the theoretical coefficient of 4 for transformers whose depth grows non- uniforrllly with context length. Thus, our transformers have learned a construction whose depth coefficient is comparable to what we showed was possible in theory, though perhaps slightly more wasteful than it needs to be. Overall, these empirical results show that, in practice, the impact of depth and width on effective context length for regular language recognition aligns with our theoretical predictions, and we are able to empirically fit the quantitative coefficients in the relationships.
The results are shown in Figure 2.
8 Conclusion
We have shown that recognizing regular languages and graph connectivity, two key problems inex- pressible by fixed-depth transformers, become expressible if the depth of the transformer can grow very slightly (logarithmically) with the context length by repeating layers. This implies transformers with fixed depth d can solve these problems up to bounded context lengths of 20(4), Further, we showed that scaling depth to solve these problems is more efficient than scaling width (which re- quires superpolynomial increase) or scaling increase). As dynamic test-time compute methods have become popular for building more powerful reasoning models such as OpenAl ol (OpenAI, 2024) and DeepSeek-R (DeepSeek AI, 2025), would be interesting to explore whether universal transformers can realize this theoretical efficiency to provide more efficient long-context reasoning than chain-of-thought steps in practice.
of-thought steps (which requires superlogarithmic
While growing depth enables transformers solve some key problems outside TCº, there are limita- tions on the types of problems log depth should enable solving. Unless NC = P. log-depth (or even polylog-depth) transformers cannot express P-complete problems including solving linear equalities, in-context context-free language recognition, circuit evaluation, and determining the satisfiability of Horn clauses (Greenlaw et al.. 1991). In future work, it would interesting study the depth required for transformers to solve other interesting problems in NC including context-free recognition (generalizing regular languages; Theorem 1), which is in AC (Ruzzo, 1981; Venkateswaran, 1991) and boolean formula evaluation, which is NC! -complete (Buss, 1987). This would help us better understand the degree to which repeating layers can be used as form of interence-time compute.
Limitations
We have given constructions whereby looped transformers can express NC'- -hadd problems, though we have not considered looped transformers' inductive biases and learning dynamics, which are also important in practice beyond expressivity. Saunshi et al. (2025) empirically study the inductive biases of looped transformers, suggesting looped transformers may generalize ways favorable for reasoning tasks. Our experiments in Section 7 were conducted with non-looped transformers. It would be interesting in future work to evaluate how the depth requirements change if we enforce that the transformer must re-use the same weights across layers.
10

---

References
Ai2. OLMo: Accelerating the science of language models. ACI, 2024.
L. Ba, R. Kiros, and Hinton. Layer normalization, 2016. URL httpss////aaxxi abs/1607. .6450..
D. A. M. Barrington and D. Thérien. Finite monoids and the fine structure of NC1. J. ACM, 35(4):
941 1412, oct 1988. ISSN 0004-5411. doi: 10.1 0.1114/48014.631355
D. M. Barrington and A. Maciel. Lecture 5: The landscape of complexity classes, 2000. Lecture
notes.
G. E. Bleiloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, Nov. 1990.
S. R. Buss. The Boolean formula value problem is in ALOGTIME. In STOC, page 123-131, 1987. doi: 10.1145/28395.2844
D. Chiang, P. Cholak, and A. Pillay. Tighter bounds on the expressivity of transformer encoders. In ICML, 2023.
DeepSeek AI. DeepSeck-RI: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv, abs/2501. 12948, 2025.
M. Dehghani, Gouws, O. Vinyals, J. Uszkoreit, and L., Kaiser. Universal transformers. In ICLR, 2019.
J. Geiping, S. McLeish, N. Jain, J. Kirchenbauer, S. Singh, B. R. Bartoldson, B. Kailkhura, A. Bhatele, and T. Goldstein. Scaling up test-time compute with latent reasoning: recurrent depth approach. ArXiv, abs/2502.05171, 2025.
R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. A compendium of problems complete for P. Technical Report TR91-11, University of Alberta, 1991. URL https://doi..rgg 7939 (0939//39990F73
W. Hillis and Steele Jr. Data parallel algorithms. Communications of the ACM, 29(12): 1170-1183, 1986.
N. Immerman. Descriptive complexity. Springer Science & Business Media, 1998.
A. Kazemnejad, I. Padhi, K. Natesan, Das, and S. Reddy. The impact of positional encoding on length generalization in transformers. In NeurlPS, 2023.
Z. Li, H. Liu, D. Zhou, and T. Ma. Chain of thought empowers transformers to solve inherently serial problems. In ICLR, 2024.
Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and Zhang. Transformers learn shortcuts to automata. In ICLR, 2023.
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of nog-precision transformers. TACL, 11, 2023a.
W. Merrill and Sabharwal. logic for expressing log-precision transformers. NeurIPS, 2023b.
W. Merrill and Sabharwal. The expressive power of transformers with chain of thought. In ICLR, 2024.
W. Merrill, A. Sabharwal, and N. A. Smith. Saturated transformers are constant-depth threshold circuits. TACL, 10:843-856 2022.
W. Merrill J. Petty, and A. Sabharwal. The illusion of state in state-space models. In ICML, 2024.
Meta AI. The Llama 3 herd of models. arXiv, abs/2407.21783, 2024.
P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston,
O. Kuchaiev, G. Venkatesh, and Wu. Mixed precision training. In ICLR, 2018. URL https: //openeeviww www//eeen///eee netd/forumm/dddr1ggg.......

---

J. Myhill. Finite automata and the representation of events. WADD Technical Report, 57:112-137, 1957.
OpenAl. Openai ol system card. arXiv, abs/2412.16720, 2024.
J. Petty, S. Steenkiste, I. Dasgupta, Sha, D. Garrette, and T. Linzen. The impact of depth on compositional generalization in transformer language models. In NAACI, 2024.
J. Pfau, W. Merrill, and S. R. Bowman, Let's think dot by dot: Hidden computation in transformer language models. In COLM, 2024. URL peattp:://ppenevviee net/forumm net//forun?ld-Viikbrrttt
O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4), Sept. 2008. ISSN 0004-5411. doi: 10.1 10.1145/139129/ 1391291.
W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22(3): 365-383, 1981. ISSN 0022-0000. doi: accieecc//ariille/ai///////222// attps://www. wwtp://.cieeneiiee..... wwwpiieretttctteeeeeeeeeeeeeeeee wttp:/ccccccccc.eeeeeee.eeeecaee
1900888- URL
C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halcrow, B. Perozzi, and V. Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In NeurlPS, 2024.
N. Saunshi, N. Dikkala, Z. Li, S. Kumar, and S. J. Reddi. Reasoning with latent thoughts: On the power of looped transformers, In ICLR, 2025.
L. Strobl, D. Angluin, D. Chiang, J. Rawski, and A. Sabharwal. Transformers as transducers. arXiv, abs/2404.02044 02040, 2024.
D. Thérien. Classification of finite monoids: the language approach. Theoretical Computer Science, 14(2):195-208, 1981. ISSN 0304-3975, doi: http:///o..ng//oo.00000004444440
URL
H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43(2):380-404, 1991. ISSN 0022-0000. doi: http:://bb..ogg///.0006002222000
URL
http://wwww.cciicedreeeeee. wttpiiirretttcctteeeeeeeeeeeeeee cww/scienceseecoccccccccccccccce wttp://ccciieeerrrcc.ca/////////
J. 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 large language models. In NeurIPS, 2022.
R. Xiong, Yang, D. He, Zheng, S. Zheng, Zhang, Y. Lan, L.. Wang, and T.-Y. Liu. On layer normalization in the transformer architecture, 2020. URL https://opearrviee..no id-Bix8anVEPr.
A. Yang, M. Cadilhac, and D. Chiang. Knee-deep C-RASP: A transformer depth hierarchy, 2025. URL atttp://arxivv org/ abs/2006.. 16055.
L. Yang, K. Lee, D. Nowak, and D. Papailiopoulos. Looped transformers better learning learning algorithms. In ICLR, 2024.
B. Zhang and R. Sennrich. Root mean square layer normalization. In NeurIPS, 2019.
12

---

A Building Blocks
A.1 Residual Stream Storage Interface
Our masked pre-norm transformer architecture always normalizes values when reading them from the residual stream. This means that it's not always the case that what's added to the residual stream by one layer is accessible as-is in future layers, which can be problematic if there a need "erase" that value. We discuss how values are stored and, if needed, erased from the stream.
For any general scalar storing in the residual stream results in sgm(2) being retrieved when masked pre-nont mre-normmn is applied to this cell. This will be useful when we want to collapse multiple values perform equality threshold checks. As special case, when {-1, 0, 1), the retrieved value after masked pre-norm precisely 2. Thus scalars in {-1,0,1) 1) can be stored and retrieved without any information loss.
order to retrieve a value z with masked pre-norm (rather than just its sign), we can instead represent as a 4-dimensional vector (2)) (z, -2, -1). Then, pre-norm masked to only this vector will return (22) = 1/v2-- (2)/ 1. Scalars 2 stored (2) or ((z) in the residual stream can be trivially retrieved as 6(2) by masked pre-norm:
Lemma 2. There exists a masked pre-norm v such that, if 6(2) or (z) is stored in h, v(h) = 6(2).
Furthermore, a single masked pre-norm can even be used to retrieve multiple scalars stored in the residual stream. Since (fz) is unit-norm vector, this is consequence of the following lemma:
Lemma 3. There exists masked pre-norm v such that, if h stores unit-norm vectors $1...., Ok. then vhh) (k1....ák)
Proof. We apply the mask to focus on the positions where 01 o1,..., are stored. Then, the masked pre-norm outputs
V2k (0) Øk).
We can hardcode the scalar multiplier of layer-norm to remove the scalar factor, or, equivalently, bake it into the next linear transformation. Either way, we are able to retrieve the concatenation of #1 Ob as input to the layer.
The following establishes that we can compute numerical values z with attention heads and make them accessible as 6(2) in later layers:
Lemma 4. Let be scalar computable by attention head from residual stream h. There exist two layers producing residual streams hn' h" such that
1. ((2) can be read via masked pre-norm from h' or h".
2. ((2) is stored in h" (formerly blank) indices I.
Proof. The first layer computes and stores (x2) blank indices in the residual stream, producing h'. Thus, the second layer can read ((2) with masked pre-norm via Lemma 2 and can also recompute from h, which is subspace of h', At this point, it outputs -1b(z) Φ(z) indices 7, which leads to h" storing ((z) at T.
A.2 Clearing Stored Values
In the repeated layers of a universal transformer, we will need to overwrite the values stored at particular indices in the residual stream. That is, if [h], x, it will be useful to produce h such that [h'], = y instead. The following lemmas will help implement constructions of this form.
Lemma 5. If a unit-norm vector & is stored in h as I, there exists a feedforward sub-layer that removes d, iee, produces ht such that [h]] =
Proof. The layer reads o via masked pre-norm and writes - to h L, setting [h], o- δ Ō.
13

---

Combining Lemma 5 with a parallel layer that stores some new value at Z, we see that we can effectively overwrite values at / rather than just deleting them.
is also possible to remove information that is not a unit-norm vector, although the construction is less direct.
Lemma 6. Let ô be the oulput of transformer layer on h, targeted to indices T at which h is blank. Then there exists another transformer layer that resets the residual stream h' h + 5 h.
Proof. The second layer is copy of the initial layer that considers the subvector h of h' as its input and where all signs are flipped. Thus, outputs -ō, which guarantees that the final residual stream is h" h + 8 8 h.
A.3 Computing Position Offsets
will be useful to show how transformer can compute the position index of the previous token.
Lemma 7. For fixed value k assume that each position i, transformer stores 1 0] and 1 < k] in the residual stream. Then, there exists a layer that adds øli - k) to the residual stream at token indices k.
Proof. We construct two attention heads. The first head is uniform with value j as [ 0). Thus, the head computes h1 = 1/i. The second head is uniform with value j as L[i 2 k).. and thus computes h2 = (i k)/ We then use a feedforward layer to compute:
(bh, (2) = 00 i "
k ( sii - k).
The resulting value is then written the residual stream.
The precondition that we can identify the initial token (cf. Merrill and Sabharwal, 2024) is easy to meet with any natural representation of position, including 1/i Φ(i), as we can simply compare the position representation against some constant.
We assume that the positional encodings used by the model allow detecting the initial token (Merrill and Sabharwal, 2024). One way to enable this would simply be to add a beginning soriiinn-o--sqqueee of-sequence token, although most position embeddings should also enable it directly.
A.4 Equality Checks
We show how to perform an equality check between two scalars and store the output as a boolean. Lemma 8. Given two scalars x, y computable by attention heads or stored in the residual stream, we can use a single transformer layer to write 1 [x y] in the residual stream. Furthermore, a second layer can be used to clear all intermediate values.
Proof. After computing x, in self-attention layer, we write x - y to temporary cell in the residual stream. The feedforward sublayer reads σ sgn(x y), computes ReLU(-o;) and writes to the residual stream.
ReLU(a,)
The next transformer layer then recomputes y and adds it to the intermediate memory cell, which sets it back to O. Thus, the output is correct and intermediate memory is cleared.
B Correctness of Division Construction Attention Heads
The proof of Lemma I presents the full construction to implement division in a transformer. For space, we omitted a full proofs of correctness for attention heads in the construction, which we now present. We expect some of these techniques could be reused, though we have not stated them as generally as the gadgets in Appendix A.
Lemma (First Layer of Lemma 1). Let h be an attention head computed with query q, = -(i/m)
and keys/values k, = Uy Φ()). Let e; I(h! o(i/m)). Then e; if and only if is multiple of m. Furthermore, if e; = 1, then h d(i/m).
14

---

Proof. Suppose first that is multiple of m. In this case, there exists a position 5 < i such that i == mj", which means the query q: = o(i/m) = <(j") exactly matches the key ky. The head will thus return V/z- = )(j") = ((i/m), representing precisely the quotient i/m. Further, the equality check will pass, making e = 1. The layer thus behaves as intended when is multiple of m.
On the other hand, when i is not a multiple of m, no such j exists. The head will instead attend to some j for which A mj and therefore 6(i/m) + Φ(j), making the subsequent equality check fail and setting = 0, as intended.
Lemma 10 (Second Layer of Lemma 1). Let hē be an attention head computed with qi (1, 1), key kj = (ej, [o()),), and value V/ = n1.. Then h = (((/mm))
Proof. By construction, q: k; e; - where [o(i)]o /222 2 is the first coordinate of (()). Note that ( E [0, 1) for positions j S and that it is monotonically increasing in j.
It follows that the dot product is maximized the largest j و i such that e, = 1, i.e. at the largest j S i that is a multiple of m. This has the property that [i/m] = j/mm Thus, the head at this layer attends solely to this j. Recall that the value Uj at this position hi = ó(i/m) @(Li/m]).
O
Lemma 11 (Fifth Layer of Lemma 1), Let hy be an attention head computed with query qi (o(Li/m]), 1), key k- = (((mi/m)) bb), and value vy =1 - 87. Then h2 = <(i mod m).
Proof. The query-key product achieves its upper bound of 2 exactly when two conditions hold: [i/m]= = | [j/m] and bj = 1. Thus, the head attends from to all j S that store the same quotient as i and also have b/ = 1. To make this clearer, let's write i as i = D'm + c' for some c' < m. The query- key dot product is then maximized precisely at the e positions j in (b'm+1,
1, 1,1'mmm + ....... b' + c
.....
for all of which [j/m] = Li/m] = b/: note that 0 i'm not included in this list as 1/3 = when j = 6'm. Of these positions, only t'm + 1 has the property that the quotient there is not the same as the quotient two position earlier, captured by the value vj = 1 by. Thus, the value Uj is I among these positions only at j b'm + 1, and 0 elsewhere.
Assuming m does not divide i, c' and the head attends uniformly at c' positions, returning L/c as the head output. By construction, c' = i - D' m = i mod m. The layer adds the vector (1, 1/c') defined as (1, 1/c², 11, -1/c²) to the residual stream position This, when read in the next layer using masked pre-norm, will yield 1/c)) = o(c') = ø(i mod m).
On the other hand, if m does divide i (which can be checked with a separate, parallel head), we write (0) to the residual stream, which, when read by the next layer, will yield ((0) = d(i mod m). O
C Regular Language Recognition Proof
Theorem (Regular Language Recognition). Let L be a regular language over Σ recognized by (non- Jdeterministic finite automaton with states Q. Let $ of E. Then there exists a causally masked
(0, 8, 9) -universal transformer with
model dimension mNFa 0((Q1), or MDDA O(IQ) log Q)) if deterministic; feedforward width WNFA 02 or WDFA 0(2 (01) if deterministic;
that, on any string w8, recognizes whether L when unrolled to [log|w|]] depth.
Proof. Regular language recognition can be framed as multiplying a sequence of elements in the automaton's 's transition monoid (Myhill, 1957; Thérien, 1981). It thus suffices to show how elements in a finite monoid can be multiplied with (llo n2) depth. We show how a log-depth universal transformer can implement the standard binary tree construction (Barrington and Thérien, 1988; Liu et al., 2023; Merrill et al., 2024) where each level multiplies two items, meaning the overall depth is (log] wl). We will represent a tree over the input tokens within the transformer. Each level of the tree will take transformer layers. We define a notion of active tokens: at level 0, all tokens are active, and, at level f, tokens at 1. 2 - 1 for any / will remain active, and all other tokens will be marked as inactive. As an invariant, active token i = -L-2 2 11 level E will store a unit-norm vector of that represents the cumulative product of tokens from i 2 1 to i.
15

---

We now proceed by induction over é, defining the behavior of non-S tokens at layers that make up level L. The current group element of stored active token i is, by inductive assumption, the cumulative product from 2 + i. Let of denote that token is active. By Lemma 7 we use a layer to store i - 1 at token i. The next layer attends with query ø(i - 1), key Φ(i), and value 5j to retrieve 6 the group element stored at the previous token. Finally, another layer attends with query I, key (o(i),, af), and value 0 retrieve the group element 83. stored at the previous active token, which represents the cumulative product from i 1 2-22 2 + 1 to - 2 Next, we will use two layers to update 5f + 5,+1 and o3 < O. which achieved as follows. First, we assert there exists a single feedforward layer that uses a table lookup to compute 63., - d such that d/Ild|| = 84. 8 = 5 Next, we invoke Lemma 6 to construct a layer that adds to an empty cell of the residual stream and then another layer that deletes it. This second layer can now read both 5f, 85. and 55+1 (from d) as input, and we modify it to add 56+1 - 5f to 8f, changing its value to 50t1. Similarly, we modify it to add -85. to 85. to set to O. A feedforward network then subtracts of from the residual stream and adds 8f -5. This requires at most 4 layers.
To determine activeness in layer + 1, each token i attends to its left to compute c//i, where &, is the prefix count of active tokens, inclusive of the current token. We then compute o(c//i, //c//i,1// 1/i) ((c.) and store & it temporarily in the residual stream. At this point, we use Lemma to construct 7 layers that compute e mod 2 with storage overhead. The current token is marked active in layer & + 1 iff c; = 0 mod 2, which is equivalent to checking whether = = 2 1 for some t. In addition to updating the new activeness a. a1 we also persist store the previous activeness of in a separate cell of the residual stream and clear e.. This requires most layers.
Finally, we describe how to aggregate the cumulative product at the $ token, which happens in parallel to the behavior at other tokens. Let of be monoid element stored at $ that is initialized to the identity and will be updated at each layer. Using the previously stored value - 1, we can use a layer to compute and store -i_1 and a at each i. A head then attends with query I, key (o(j),, 10 a.-1)- and value ((1 =) --1 This retrieves a value from the previous active token j at level that is 65 if j will become inactive at f+ 1 and Ô otherwise. Iff 85 is retrieved, a feedforward network subtracts og from the residual stream and adds dz og. This guarantees that whenever a tree deactivated, its cumulative product is incorporated into o5. Thus, after [logg/w|]] + levels, o6 will be the transition monoid element for w. We can use one additional layer to check whether this monoid element maps the initial state to an accepting state using finite lookup table. Overall, this can be expressed with 8 layers repeated [logz| [|]] times and 9 final layers (to implement the additional step beyond [log n1).
Finally, we justify the model size m and feedforward width w. To represent a nondeterministic monoid element Q - Q, which is defined by matrix in {0, 1) we must store SNFA IQ| bits. For deterministic monoid element, we can reduce this to SDFA IQ log by storing the index of the unique 1 in each row of the matrix. The model size is then m O(s). which gives:
MNFA = 0(
MDDAA = 0(1Q) logl Q1).
The feedforward network stores lookup table enumerating all possible values of 5² bits, returning bits in each case. This can be represented as long as O(s) and w O(2²), which gives:
0(2
( log" 101"
WNFA
mDFFA
This finishes the proof.
D Graph Connectivity Proof
Theorem 2 (Graph Connectivity). There exists (17,2, 1) -n-uiereraal transformer T with both causal and unmasked heads, fixed model dimension m, and fixed feedforward width w that, when unrolled [logg n.) times, solves connectivity on (directed undirected) graphs over vertices: given the n x n adjacency matrix of a graph G, n² padding tokens, and 8, E [1....n] in unary, T checks whether G has a path from vertex to vertex t.
16

---

Proof. We will prove this for directed graphs, as an undirected edge between two vertices can be equivalently represented as two directed edges between those vertices. Let G be directed graph over vertices. Let A E {0, 1 snan be G's adjacency matrix: for i, E (1,...,n) n), Ai, is 1 if G has an edge from i to j. and O otherwise.
The idea is to use the first n² tokens of the transformer to construct binary predicates (e(i, for l E {0, I.... [log n capturing whether G has path of length at most 2 from to j. To this end, the transformer will use the n² padding tokens to also construct intermediate temnary predicates Cz(i, for l E {1...., [log n1} capturing whether G has paths of length at most 2 from to k and from & to j. These two series of predicates are computed from each other iteratively, in standard algorithms for graph connectivity:
Boli,)) = A(i,)) V vi=j Ce+i(i,hi,)) = be(i,k) A (e Be41(1.)) = 3s s.t. CE+1 k,
(5)
We first argue that B Dlg " (i, if and only if G has path from to j. Clearly, there is such a path if and only if there is a "simple path" of length at most n from to j. To this end, we argue 1 if an only if G has a path of length most 2 from i to j. For the base case of = 0, by construction, ( = if and only if either = (which we treat as a path of length 0) or A., = 1 (i.e., there is a direct edge from to j). Thus, Be(i. = 1 if and only if there is a path of length at most 2 = from i to j. Now suppose the claim holds for J). By construction, C j) = 1 if and only if By k) = By(k: = 1, which by induction means there are paths of length at most 2 from i and from & to j. which in turn implies that there is a path of length at most 2- 2 = 2 from i to j (through k). Furthermore, note conversely that if there is path of length at most 2 from i to j. then there must exist a "mid-point" l: in this path such that there are paths of length at most 2 from i to k and from & to j. i.e., Ce+1 (1, j) = 1 for some k. This is precisely what the definition of Be+1 (i, j) captures: it is if and only if there exists a k such that Cc+1 (7, k) = 1, which, as argued above, holds if and only if there is a path of length at most 2 from i to j. This completes the inductive step.
by induction over E that j)
The crucial part is to construct transformer that correctly operationalizes the computation of predicates B, and Cj. The input to the transformer is the adjacency matrix A represented using n² tokens from {0, 1), followed by n² padding tokens D. and finally the source and target nodes 8, E (1......n) represented in unary notation using special tokens a and b:
A AI,1...AAp AL, 1 .2.,...AA, Ag,a
An. Anm
Let N = n² + n + s t, the length of the input to the transformer. The first n² token positions will be used to compute predicates Br, while the next n. token positions will be used for predicates Ce.
Initial Layers. The transformer starts off by using layer to store 1/N, n, n², ss and t in the residual stream at every position, as follows. The layer uses one head with uniform attention and with value 1 only at the first token (recall that the position embedding is assumed separate from other positions). This head computes 1 1/N and the layer adds 3)(1 (1/N) /N) to the residual stream. Note that the input tokens in the first set of n² positions, namely 0 and 1, are distinct from tokens in the rest of the input. The layer, at every position, uses a second head with uniform attention, and with value 1 at tokens in {0, 1} and value 0 at all other tokens. This head computes n² //N. The layer now adds (nn /N, 1/N), where (a, b) is defined as the (unnormalized) vector (a, 6, -a, -b). When these coordinates are later read from the residual stream via masked pre-norm, they will get normalized and one would obtain (n2 /N, 1/N)= = "(n²). Thus, future layers will have access to @(n²) through the residual stream. The layer similarly uses three additional heads to compute n C/N s/N, and t/N. From the latter two values, it computes (s//N, 1/N) and vit/N, 1/N) and adds them to the residual stream; as discussed above, these can be read in future layers as o(s/ x// /N, 1/N) = ((s) and ott/N, 1/N) = Φ(t). Finally, the layer computes (n3 /N, n² /N) and adds it to the residual stream. Again, this will be available to future layers as p(n" /N, n /N) = p(n).
The transformer uses the next 15 layers to compute and store in the residual stream the semantic "coordinates" of each of the first n² + n token position as follows. For each of the first n² positions
17

---

p in j with 1 S p S n², it uses Lemma 1 (7 layers) with a; set to p and m set n in order to add o(1) and d(j) to the residual stream at position p. In parallel, for each of the next n positions p n² + (in? + kn + j) with n² +1 S p S n² + n², it uses Lemma with a, set to p and m set n in order to add (((i+1) + k) and ())) to the residual stream, It then uses the lemma again (7 more layers), this time with 0, set to (i + 1) )n + k and m again set to n, to add Φ(i + 1) and Φ(k) to the residual stream. Lastly, it uses Lemma 7 applied to ø(i + 1) to add Φ(i) to the residual stream.
Layer 17 of the transformer computes the predicate (i) at the first n²² token positions as follows. At position p in + j. it uses Lemma 8 to compute [(({(A(i.)) = o(1) and I(((i)) = o())); note that @ (A(i, j)), ((i,, and (bj) are available in the residual stream at position p. It then uses a feedforward layer to output if both of these are 1, and output O otherwise. This is precisely the intended value of (i. The sublayer then adds (o j) to the residual stream. The layer also adds to the residual stream the value 1, which will be used to initialize the boolean that controls layer alternation in the repeated layers as discussed next.
Repeating Layers. The next set of layers alternates between computing the Ce and the By predicates for & E {I...., [log To implement this, each position i at layer updates in the residual stream the value of a single boolcan r computed as follows. r is initially set to I at layer 8. Each repeating layer retrieves from the residual stream and adds 1 - the same coordinate in the residual stream. The net effect is that the value of r alternates between and O at the repeating layers. The transformer uses this alternate between the computation of the Ct and the B, predicates.
For E E {I,..., [log }. layer (2 - 1) + 8 of the transformer computes the predicate Ci(i, j) at the set of n² (padding) positions = n² + in² + kn +j. as follows. It uses two heads, one with query (ő(i), (R:)) and the other with query (ő(k) +()). The keys in the first n² positions q = i'n + j' are set to (o(t"), ((j)), and the values are set to 1 j')). The two heads thus attend solely to positions with coordinates (i, k) and j), respectively, and retrieve boolean values B B (k. j). respectively, stored there in the previous layer. The layer then uses Lemma 8 to compute I(B k) = 1) and ([ (k: = 1). and uses a feedforward layer to output 1 if both of these checks pass, and output 0 otherwise. This is precisely the intended value of C. j). If E >> 1, the layer replaces the value Ce-1(i, j) stored previously in the residual stream with the new boolcan value Ce(i, j) by adding Ce(i, k, j) - Ci- k, to the same coordinates of the residual stream. If l = 1, it simply adds Ce j) to the residual stream.
(i. k) and
For l E {1,..., Nog n. 1, layer 28 + 8 computes the predicate Be( at the first n² positions p in + j. as follows. It uses head with query (d(1), d(j))- The keys in the second set of n positions = n² + i'n2 + k'n + +J are set to (o((") o(j")) (recall that do(²)) and o(j') are available in the residual stream at () and the corresponding values set to the boolean Cx K', J'), stored previously in the residual stream. The head thus attends uniformly to the n padding positions that have coordinates (i, K, for various choices of k', computes the average of their values, which equals h = - Cr J) as well as 1/(2n) using an additional head. We observe that h 2 1/n if there exists a K such that Ce(i, K = 1, and h = 0 otherwise. These conditions correspond precisely to (r( j) being 1 and O respectively. We compute h 1/(2n) and store it in the residual stream. Similar to the proof of Lemma 8, the feedforward layer reads a sgg (h - 1 1/(2)),, computes the residual stream. The value z is precisely the desired (i, as σ is 1 when h 2 1/n and when h = O. As in Lemma 8, the intermediate value (1-1/(2)) written the residual stream can be recomputed and reset in the next layer. As before, the transformer replaces the value B₁ (i.i stored previously in the residual stream with the newly computed value Bi(i,j) by adding (BB(iij) - (i,) to the stream at the same coordinates.
(1 + ReLU(r)) /2, and writes
Final Layers. Finally, in layer 2 llg ni] + 18, the final token uses a head that attends with query (o(s), (t))) corresponding to the source and target nodes s and mentioned in the input; recall that Ø(s) and ((t) are available in the residual stream. The keys in the first n² positions p in + are, as before, set to (o(i), (())) and the values are set to Blog xi) (i. retrieved from the residual stream. The head thus attends solely to the position with coordinates (s, 1), and retrieves and outputs the value Bllog x) (s, t). This value, argued earlier, is 1 if and only if G has path from to t. L
18

---

E Proofs for Width Scaling and Chain of Thought Claims
Theorem (Width Scaling), Let I' be a fixed-depth transformer whose width (model dimension or padding tokens; Pfau et al., 2024) grows at most polynomial in and whose weights on input length n (to accommodate growing width) are computable in L. Then T can be simulated in L-uniform TC
Proof. By assumption, we can construct an L-uniform TC² circuit family in which the transformer weights for sequence length are hardcoded as constants. Next, we can apply standard arguments (Merrill et al., 2022; Merrill and Sabharwal, 2023a,b) to show that the self-attention and feedforward sublayers can both be simulated by constant-depth threshold circuits, and the size remains polynomial (though a larger polynomial). Thus, any function computable by a constant-deple depth, polynomial-we transformer is in L-uniform TC².
Theorem (CoT Scaling). Transformers with O(log n) thain-of-thouuht steps can only recognize languages L-uniform TC
Proof. The high-level idea is that polynomial-size circuit can enumerate all possible O[log n)- length chains thought. Then, in parallel for each chain of thought, we construct a threshold circuit that simulates transformer (Merrill and Sabharwal, 2023a) on the input concatenated with the chain of thought, outputting the transformer's next token. We then select the chain of thought in which all simulated outputs match the correct next token and output its final answer. The overall circuit has constant depth, polynomial size, and can be shown to be L-uniform. Thus, any function computable by a transformer with Oloog n) chain of thought TCº.
F Experimental Details
Curriculum Training. In early experiments, we found that learning from long As sequences directly was infeasible for our transformer models. We hypothesize this was because, unless earlier tokens are predicted correctly, later tokens contribute significant noise the gradient. In order to make the learning problem feasible, we follow a curriculum training process, first training on Aş sequences of length 2, then length 4, and continuing up some fixed maximum power 2', We can then measure the maximum n < 2' such that the model achieves strong validation accuracy, as mentioned in Section
Depth Experiments. All depth experiments used a fixed width of 512. For historical reasons, we have slightly different numbers of runs for different experimental conditions, and some of the runs use different batch sizes (64 and 128). We originally ran single sweep of depths and widths with 5 runs for depths 6, 12, 18, and 24, each using a batch size of 64 and maximum depth of 2' 128. Seeking to clarify the trend between these original data points, we launched 3 additional runs at depths 9, 15, 18, and 21 using a batch size of 128, which anecdotally sped up training without harming final performance. We also observed that the original depth 24 runs were at the ceiling n* = 128, so we launched additional depth-24 runs with a batch size of 128 and 2 512 (we also used this larger sequence length for all other runs in the second set). In total, this made:
5 runs at depths 6, 12, and 8;
3 runs at depths 9, 15, 18, and 21;
8 runs at depth 24.
Width Experiments. All width experiments used fixed depth of 6. We launched 5 runs at widths 128, 258, 512, 1024 with the same hyperparameters, each using batch size of 64 and 2 128.
Compute. Each training run was launched on a single GPU. We estimate that, together, these experiments took about 1000 GPU hours.
License. The codebase of Merrill et al. (2024), which we used for data generation, has MIT license.
19

---

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: Sections 4 to 7 provide theoretical and empirical support for all claims.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as 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: Simplifying assumptions are discussed 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 not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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]
20

---

All proofs are included either right next to the formal statements or in the appendix.
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 proof' 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: [Yes]
Justification: Section 7 and Appendix F provide all key details of the experiments.
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 the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is 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?
21

---

Answer: [Yes]
Justification: As promised, we have updated the camera-ready version to point to the repository with code and data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. ec/
oo icyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. cc/
Seriidde/CooSSubne ssisssosiccyy for more details.
The authors should provide instructions data access and preparation, including how to 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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: [Yes]
Justification: Section and Appendix F provide all key details of the 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 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, 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:
[Yes]
Justification:
We include ? as a measure of linear fit.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
22

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables 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 execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Provided in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 the paper conform, in every respect, with the NeurlPS Code of Ethics https httpee:///ee/ieeeee htt///nuurripppe ctt.ippp...pp.ppoaee http:///ccc.cccettcccccccceeeeaa
Answer: [Yes]
Justification:
No special circumstances.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The contribution of this work is foundational understanding of the computa- tional power of transformers.
Guidelines:
The answer NA means that there 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.
23

---

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: [Yes]
Justification: Cited and acknowledged license for synthetic data codebase in Appendix F.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
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.

---

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: The paper did not introduce any new assets.
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:
Did not involve research with 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:
Did not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not 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.
25


Reviews:
[{"review_id": "6hCUNXTvsH", "reviewer": "Reviewer_vLZt", "summary": "The given paper analyzes _universal_ transformers, which include a block of layers that can be repeated based on the input size, and how increasing their depth increases their expressive power. The main theoretical results show that logarithmic depth in the input size is sufficient for universal transformers to recognize _regular languages_ and _graph connectivity_. These results are then compared to increasing the width of fixed-depth transformers as well as transformers with logarithmic chain-of-thought steps, both of which remain in the circuit complexity class $TC^0$. This is followed by an experimental evaluation on a dataset that contains one regular language, where the theoretically proposed scaling laws are empirically verified.", "questions": "1. More details on the required size of the transformer: For Theorem 1 and following corollaries, are there any assumptions on the required width for transformers, or is this completely independent on, e.g., the size of the alphabet, the number of states in the finite automaton that captures the language, etc.? On a similar note, what about the width of the feedforward layers, is this also problem independent? And in Lemma 1, are there any assumptions on how many attention heads are needed?\n2. Definition of universal transformer: If we consider a (2,1,1)-transformer where $r$ is repeated only one time, then, given definition of $L^{\\ell}$, $L^1$ and $L^2$ are $s$-layers 1 and 2, but $L^3$ is $r$-layer $(3 - 2) \\mod 1 = 0$; shouldn't the indexing of layers start at 1 as well? \n3. Comparison to Liu et al. [1]: The main difference to the transformer architecture used in Liu et al. seems to be the universal part, i.e., sharing weights in a dedicated block. However, in Section 4 it is said that Liu et al. strongly simplify their transformer architecture by assuming (i) \"specific, nonstandard\" positional encodings, and (ii) removing residual connections. In [1], the authors state that they use \"fairly standard positional encodings\" and use residual connections (both in p. 4, second paragraph). Could you further address these discrepancies?\n4. Depths vs. width scaling: Width can be more easily parallelized in comparison to depth; have you considered the practical implications of depth vs. width scaling and if yes, could you please elaborate why scaling depth is preferable despite not being able to parallelize increased depth?\n5. Comparison to Sanford et al. [2]: Could you please put Theorem 2 in context with the results for parallelizable tasks in [2], i.e., Theorem 11 and Theorem 18, which also state that log depth is required for transformers that are able to solve st-connectivity.\n6. Experiments: Could you please elaborate on your experimental setup, especially lines 358-362 on how $n^*$ is chosen and why only the best-performing models are presented? And, have you considered experiments on st-connectivity (and perhaps any preliminary results)?\n\n[1] Liu, B., Ash, J.T., Goel, S., Krishnamurthy, A. and Zhang, C., 2023. Transformers Learn Shortcuts to Automata. In The Eleventh International Conference on Learning Representations.\n\n[2] Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B. and Mirrokni, V., 2024. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37.", "limitations": "Please refer to the *Weaknesses* section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**: The precise characterization of the expressive power of log-depth transformers is an interesting and significant topic, with potential implications for the understanding and application of, e.g., LLMs. The technical content is presented in a clear and concise manner and the paper is well-written overall. The contributions are, for the most part, put well into context with related work. The setting of _universal_ transformers is particularly interesting, as it imposes a fixed parameter budget while maintaining uniformity (up to unrolling the transformer to a certain depth). Moreover, the theoretical results establish a lower bound on the number of layers needed for a certain context length in real-world models, which can be useful for practitioners. \n\n**Weaknesses**:\n\n*Theory*: While the paper presents interesting theoretical contributions, several aspects remain unclear. Most notably, I have open questions about assumptions underlying the logarithmic depth bounds. It is unclear to me whether the width (i.e., embedding dimension, padding tokens, width of feedforward layers) in, e.g., Theorem 1, is truly independent of the input size. For instance, results in [1] and [2] offer more precise bounds on, e.g., embedding dimension or number of attention heads. This also applies to Theorem 2 in the submission, which requires padding tokens polynomial in the input size. \n\n*Experiments*: The empirical evaluation seems underdeveloped. It appears rushed (e.g., differing numbers of runs and different batch sizes due to \"historical reasons\") and includes only a single task on regular language recognition. Including another task on, e.g., graph connectivity could substantially strengthen the substitution. Moreover, reporting only the best-performing runs is concerning, and further clarification for this choice would be appreciated. In my opinion, the paper could stand alone as a theoretical work, but if experiments are included, they should be more extensive and systematic to support the theoretical findings robustly (see Question 6 for setup concerns). \n\n*Clarity*: The clarity and mathematical rigor could be improved. The informal writing style makes the paper easy to read but at times imprecise; e.g., vague qualifiers like \"likely\" (lines 310-312) or ambiguous language in proofs (e.g., what exactly is meant by \"baking\" a scalar multiplier into a linear transformation in the proof of Lemma 3?). The proof sketch for Lemma 1 is difficult to follow without frequent back-and-forth with the Appendix; it would also be helpful to refer to the Appendix if a proof builds upon results which are not yet introduced (e.g., Lemma 7 in proof of Lemma 1). Furthermore, the repeated use of \"it\" makes the proof difficult to parse at times. It is also unclear whether the transformer architecture in Lemma 1 refers to a (7,0,0), (0,0,7) or (0,7,0) transformer, and whether repeating layers with shared weights is a fundamental part of the proof, or not. Please find some further minor remarks as follows: Variable $\\mathbf{m}$ is not introduced yet in line 128; \"The repeated layers alternates\" -> \"The repeated layers alternate\" in line 290, \"Superpolynomial in width\" -> \"Superpolynomial width\" in line 311; line 347: \"depth must increase exponentially\" -> I believe \"width\" is meant instead of \"depth\"; and in the proof of Lemma 7, it is unclear what the variable $j$ denotes. It would also be helpful to provide more context on how various circuit complexity classes relate to each other, especially for Section 6. \n\nMy current score reflects my concerns about the experimental evaluation and open questions about the theoretical contributions. If the authors are able to address these concerns, I would be willing to increase my score.\n\n[1] Liu, B., Ash, J.T., Goel, S., Krishnamurthy, A. and Zhang, C., 2023. Transformers Learn Shortcuts to Automata. In The Eleventh International Conference on Learning Representations.\n\n\n[2] Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B. and Mirrokni, V., 2024. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37.", "was_revised": true, "final_justification": "**Reason for not higher score**: I still think the experimental results are a bit underdeveloped.\n\n**Reason for not lower score**: I think the theoretical contributions of the paper are sufficient to justify its acceptance.", "rebuttal": "Thanks for your review!\n\n> width … is truly independent of the input size\n\nYes! In fact all parameters (their shape and values) in our construction are fully uniform, meaning they have no dependence at all on the sequence length. Thus, the embedding dimension, feedforward dimension, and number of heads do not depend at all on $n$. We will update the theorem statements to indicate this. For Theorem 2, the number of padding tokens does depend on $n$, but, crucially, this is an inference-time dependence and does not result in different parameters for different values of $n$ (unlike prior constructions of Liu et al [1] and Sanford et al [2]; see below).\n\n> Experiments\n\nWe took the max over runs (i.e., the best trained model) because we wanted the results to more carefully target *expressivity* (e.g., ignoring learning difficulties, zooming on what is possible for a transformer to represent). We focused our experiments on the regular language task because it has the nice property that every prefix forms a valid subinstance of the problem: thus, to evaluate the maximum length $n^*$ up to which the model succeeds, we can simply find the first index where the prediction was wrong. This property was very handy in our experimental methodology, and is not satisfied with graph connectivity.\n\n> informal language\n\nThere are some points in the paper where we indeed use slightly informal language to make the paper more readable (e.g., “likely” to mean assuming $TC^0 \\neq NC^1$). We see your point that this sacrifices precision in certain cases and will address this – most crucially in the proofs. In particular, we will clarify Lemma 7 and the other specific points you brought up (thanks for reading carefully).\n\n> Depths vs. width scaling: Width can be more easily parallelized in comparison to depth; have you considered the practical implications of depth vs. width scaling…\n\nIndeed, scaling width is easier than scaling depth. Our claim is in the context of inherently sequential problems such as regular language recognition and graph connectivity, which we focus on. Our theoretical results show that scaling width, even if easier, fundamentally cannot enable solving these problems (Theorem 3) whereas scaling depth logarithmically via looping layers can (Theorems 1 & 2).\n\nWe also note that depth scaling in a looped transformer is an inference-time method: the same trained transformer can be looped more, depending on $n$.  Width scaling, on the other hand, is a training-time method: one must *train a different transformer* for each desired width.\n\n> For Theorem 1 and following corollaries, are there any assumptions on the required width for transformers, or is this completely independent of, e.g., the size of the alphabet, the number of states in the finite automaton that captures the language, etc.? On a similar note, what about the width of the feedforward layers, is this also problem independent? And in Lemma 1, are there any assumptions on how many attention heads are needed?\n\nGood question. The embedding dimension, while independent of input length $n$, does need to be large enough to distinguish different tokens in $\\Sigma$ and to encode all the possible states. A conservative way to satisfy this would be to construct it as $\\max \\{ |\\Sigma|, |Q} \\}$. \n\nThe feedforward network is implementing a finite lookup table from $\\Sigma \\times Q \\to Q$. Thus, its width will have to grow with both the number of states of the minimal DFA and the size of the vocabulary. We have not closely analyzed how many attention heads are needed, but it is fixed independent of the language (i.e., there is some fixed number of heads that would work for *any* regular language, no matter the size of the minimal DFA).\n\nWe will clarify this.\n\n> If we consider a (2,1,1)-transformer where $r$ is repeated only one time, then, given definition of $L^\\ell$, $L^1$ and $L_2$ are $s$-layers 1 and 2, but $L^3$ is $r$-layer $(3 - 2) \\mod 1 = 0$; shouldn't the indexing of layers start at 1 as well?\n\nThanks for reading carefully and catching this. We’ll update the notation so that the three layer lists (s,r,t) are either all 0-indexed or all 1-indexed.\n\n> Comparison to Liu et al. [1]: The main difference to the transformer architecture used in Liu et al. seems to be the universal part, i.e., sharing weights in a dedicated block. However, in Section 4 it is said that Liu et al. strongly simplify their transformer architecture by assuming (i) \"specific, nonstandard\" positional encodings, and (ii) removing residual connections. In [1], the authors state that they use \"fairly standard positional encodings\" and use residual connections (both in p. 4, second paragraph). Could you further address these discrepancies?\n\n* Related to what you said, a major difference is that our construction is *fully parameter uniform* (the parameters are the same for any context length), whereas the Liu et al. construction requires the parameters to change with input length $n$.\n\n* As mentioned on page 44, the Liu et al. construction assumes each index $t$ gets two sinusoidal *position embeddings* $\\cos(\\pi * t / T) and \\sin(\\pi * t / T)$. While this somewhat resembles the absolute positional embeddings used in the original transformer, our construction is much more general, since it holds without any positional embeddings (as long as a beginning of sequence symbol is used or the first token can be uniquely attended to). We will clarify this difference in revisions and remove the current vague language.\n\n* Another difference between our construction and theirs is the presence of $layer norm$, which is standard in all practical implementations. As they mention on page 25, Liu et al. omit layer norm from their construction, whereas our construction uses (and in fact highly leverages) layer norm.\n\n* Regarding *residual connections*, it’s straightforward to adapt the Liu et al. construction to work with residual connections in a *non-parameter-uniform* setting. However, with *full parameter uniformity* (like we assume), it becomes technically challenging because looped layer blocks need to reuse the same cells in the residual stream. Dealing with this appropriately (*residual stream management*) is a novel contribution of this paper. We will revise the comparison with Liu et al. to better clarify these points.\n\n> Comparison to Sanford et al. [2]: Could you please put Theorem 2 in context with the results for parallelizable tasks in [2], i.e., Theorem 11 and Theorem 18, which also state that log depth is required for transformers that are able to solve st-connectivity.\n\nA key difference between our construction and that of Sanford et al. is, again, *full parameter uniformity*. Whereas our construction uses fixed embedding dimension (and fixed parameters) for all $n$, Theorem 18 in Sanford et al. uses an embedding dimension that grows as a sublinear polynomial in $n$.\n\nInterestingly, their construction uses a similar amount of “padding” tokens ($n^3$ to $n^4$ tokens, depending on the embedding dimension) to ours ($n^3$), unless the embedding dimension is allowed to grow as at least $\\sqrt(n)$, in which case their construction can work without padding. We will add some discussion of this comparison, focusing on the central difference of full parameter uniformity for our construction."}, {"review_id": "jBJ5KBXU4b", "reviewer": "Reviewer_GaAn", "summary": "The paper discusses the representation power of a transformer with a depth that grows on the order of the logarithm of the context length, denoted as n, instead of a constant depth. The paper demonstrates that it is possible to construct a transformer with this logarithmic depth and essentially uniform layers that can solve two fundamental problems: recognizing regular languages and solving graph reachability problems of size n.\n\nThe key to this construction is a module that can calculate the result of a small fixed integer modulo operation for a sequence of elements. By computing the position of an element in a sequence using a fixed number of layers, the transformer can look up the corresponding feature at that position.\n\nOnce this building block is established, the paper shows that not only can we design a transformer with logarithmic depth to recognize regular languages, but we can also design a uniform transformer, which uses repeated layers with shared weights, to achieve the same task with a small constant factor. If we allow for non-uniform construction, this constant can be reduced even further.\n\nThe paper also notes that if we consider scaling the width of the transformer, it would need to be super-polynomial to achieve the same complexity class, a result that aligns with previous findings. Additionally, if we only allow a logarithmic number of chain-of-thought steps, the model cannot solve the problem, suggesting that increasing depth is more computationally efficient than increasing width or chain-of-thought steps for this particular problem.", "questions": "Please refer to the weakness section for the major questions.\n\n1. Given that it has been shown in some previous works that linear RNN models or some variants of Transformer models can solve some NC-1 problem with constant depth, will logarithmic depth of such modules potentially be in a larger computational class than softmax Transformer?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Overall, the reviewer believes that this is a strong paper and that the weaknesses are relatively minor.\n\n## Strengths:\n\n1. The paper tackles a theoretically important problem by exploring transformers with depth that grows logarithmically with the input size, moving beyond the common and less realistic assumption of constant depth.\n\n2. The construction of the small integer modular module is theoretically interesting and is clearly presented.\n\n3. The theoretical results align closely with empirical findings, even down to small constants, especially in the case of regular language recognition.\n\n## Weaknesses:\n\n1. The abstract might give the impression that scaling depth is universally more efficient than scaling width or chain-of-thought steps, even though the results are specific to the particular context of regular language recognition.\n\n2. The use of the term \"uniform\" is not fully clarified. In circuit complexity, \"uniform\" means that there's a systematic way to generate the circuit parameters for any input size. In this paper, \"uniform\" seems to refer to having fixed parameters across input lengths / layers, and the reviewer is unsure if this matches the computational theory definition. This could create some confusion about whether previous constructions of [1] are truly non-uniform in the traditional sense. It is also unclear to the reviewer that why the authors believe Transformer can't learn a context length dependent weight as the training is performed on a fixed context length.\n\n3.  The reviewer believes that the paper should discuss its relationship with the closely related or possibly concurrent work [2] which shows that a looped transformer can generate latent thoughts and simulate multiple steps of chain-of-thought reasoning using loops. This related work also presents a parameter-uniform construction, and the reviewer would appreciate a discussion on how the two works relate and potentially differ.\n\n[1] Transformers Learn Shortcuts to Automata\n\n[2] Reasoning with Latent Thoughts on the Power of Looped Transformers", "was_revised": true, "final_justification": "This paper is of high theoretical importance in understanding the representation power of Transformer and I don't see any significant issues.", "rebuttal": "Thank you for your review!\n\n> The *abstract might give the impression that scaling depth is universally more efficient than scaling width or chain-of-thought steps, even though the results are specific to the particular context of regular language recognition.\n\nWe are unsure which part of the abstract you found to be potentially misleading. We tried to scope any depth vs. width vs. CoT comparisons to the two reasoning problems we consider here. In any case, we are happy to change any specific phrases to address this concern.\n\n> The use of the term *uniform* is not fully clarified. In circuit complexity, \"uniform\" means that there's a systematic way to generate the circuit parameters for any input size. In this paper, \"uniform\" seems to refer to having fixed parameters across input lengths / layers, and the reviewer is unsure if this matches the computational theory definition. This could create some confusion about whether previous constructions of [1] are truly non-uniform in the traditional sense. It is also unclear to the reviewer that why the authors believe Transformer can't learn a context length dependent weight as the training is performed on a fixed context length.\n\nThank you for raising this point - indeed, the sense of uniformity that we mean is stronger than standard uniformity, and we will clarify it appropriately. In circuit complexity, uniform indeed means there is a systematic way to generate the circuit for a certain size. Applying this to transformers, we can say that the parameters are $C$-uniform if the function mapping $n$ to the parameters for a network that processes strings of length $n$ is computable in the class $C$. The sense that we mean with **fully uniform** for a transformer is very strong– that $C$ is the class of *constant functions*, i.e., the parameters of the network do not depend on $n$ at all. We will make sure to clarify this appropriately.\n\n>  relationship with the closely related or possibly concurrent work [2] (reasoning with latent thoughts)\n\nThank you for bringing the concurrent Saunshi et al. paper on looped transformers to our attention -- we will make sure to cite them and add some comparison. Their Theorem 5.1 addresses the regular language recognition problem, but it is not fully parameter-uniform because the parameters (indeed the embedding dimension) can depend on $n$. Related to this, they also use nonstandard position embeddings in the proof, where each position is represented by its binary encoding, which has $O(\\log n)$ length. In contrast, our construction is fully parameter uniform and does not use any nonstandard positional embeddings.\n\n> Given that it has been shown in some previous works that linear RNN models or some variants of Transformer models can solve some $NC^1$ problem with constant depth, will logarithmic depth of such modules potentially be in a larger computational class than softmax Transformer?\n\nGood question! The short answer is that our constructions don’t straightforwardly generalize to linear RNNs because they require using attention to retrieve tokens from arbitrarily far back in the context. It’s unclear whether there is some way that linear RNNs could somehow take advantage of logarithmic depth to gain expressivity via a different construction."}, {"review_id": "iFdE0I1r2w", "reviewer": "Reviewer_8iy4", "summary": "This paper studies the expressivity of universal Transformer (aka. weight-tied / looped).\n\nTheoretically, the paper provides expressivity results: Let $n$ denote the input length. The paper shows that (log-precision, poly-width) Transformers with $\\Theta(\\log n)$ layers can 1) recognize all regular languages (Thm 1) which is NC$^1$-complete, and 2) solve graph connectivity (Thm 2) which is widely conjectured to be outside NC$^1$.\n- Both constructions are uniform with respect to $n$.\n- As corollaries, these results also show that the context size processable by a fixed-depth Transformer scales exponentially in the Transformer depth.\n- These results indicate that on certain problems, depth-recurrence is more efficient than the two alternatives of increasing expressivity:\n  - Using a larger width requires a superpolynomial growth in the width (Thm 3).\n  - Using chain of thought requires a superlogarithmic number of steps (Thm 4).\n\nEmpirically, the paper provides experiments on non-universal Transformers learning $A_5$. The results suggest that depth-scaling is more efficient than width-scaling: the allowed context size grows exponentially in the depth, but only logarithmically in width.", "questions": "- One challenge in using depth-recurrence models in practice is that training can be unstable, and unlike CoT, it's hard to collect intermediate supervision for depth-recurrence models. Do you have insights/suggestions on this?\n- The experiments are performed with non-weight-tied models. Do you have comments on the difference in inductive biases these non-weight-tied models have compared to the weight-tied models?", "limitations": "There is no direct societal impact.\n\nA limitation, as with any expressivity result, is that the increased expressivity does not necessarily translated to better learnability and hence practical performance. On the plus side, the paper has partially addressed this by providing empirical results consistent with the theory, using non-weight-tied Transformers.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The theoretical claims are valid and novel, and answers a timely question of comparing different axes of scaling: scaling the depth (depth recurrence) is provably more efficient than scaling width or using longer CoTs.\n- Further, the comparison is empirically verified.\n- The constructions provided in Thm 1 & 2 are both uniform, which is more practically relevant than non-uniform constructions.\n\nWeaknesses: I have no major complaints about the paper.", "was_revised": true, "final_justification": "I think the paper answers a timely question of comparing different axes of scaling: scaling the depth (depth recurrence) is provably more efficient than scaling width or using longer CoTs. The theoretical results are also corroborated with empirical findings.\nI think is a good paper and recommend acceptance.", "rebuttal": "Thank you for your review!\n\n> depth-recurrence models in practice … training can be unstable, and … it's hard to collect intermediate supervision\n\nWe agree that both of these details (stability and supervision in practice) going beyond expressivity are definitely important. Since we focused on the theoretical expressivity side here, we don’t have much to say about this, besides noting that there is some empirical evidence that looped transformers can be effective on algorithmic tasks. See for example [1]. We will add some discussion highlighting the learning aspects of looping as a potential limitation of this work.\n\n> The experiments are performed with non-weight-tied models. Do you have comments on the difference in inductive biases these non-weight-tied models have compared to the weight-tied models?\n\nWe don’t have any novel insights on this. However, [1] makes several interesting claims about this, suggesting weight tying might imbue an inductive bias towards “reasoning”:\n\n> Claim 2: For language modeling, looped models have an inductive bias towards good reasoning despite having worse perplexity and memorization to an iso-flop non-looped model\n\n> Claim 4: Looping-inspired regularization can leverage this inductive bias towards better reasoning\n\n[1] https://arxiv.org/abs/2502.17416"}, {"review_id": "eQyEjzNO5M", "reviewer": "Reviewer_i3BG", "summary": "This paper provides a lower bound on the expressivity of universal transformers, that is, transformers whose intermediate layers can be unrolled to arbitrary depth during inference. The authors provide explicit constructions showing that universal transformers of logarithmic depth are capable of recognising regular languages and solving graph connectivity, two fundamental algorithmic building blocks that are beyond the reach of log-precision fixed-depth transformers (at least when the input length is super-exponential in the depth). This result fundamentally advances our understanding of universal transformers, which have recently found success in medium-scale applications (Geiping et al. 2025).", "questions": "- When $z$ is stored as $\\psi(z)=<z,1,-z,-1>$, is it then not the case that the value retrieved through layernorm is $\\psi(z)/\\|\\psi(z)\\|_2=\\psi(z)/\\sqrt{(2(z^2+1))}$? Is the $\\sqrt2$  factor at all relevant? I assume not.\n\n- Do you believe it is feasible to extend your study such that the $\\tau \\rightarrow 0$ assumption in the attention softmax is not necessary? Can you comment on what kind of a framework would you need in this case?\n\n- The graph connectivity construction requires a cubic amount of padding tokens. Do you think that it might be possible to reduce this amount of tokens? It is not such a crucial question as we are still dealing with sub-exponential padding, I was just wondering.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\n- Providing explicit constructions for regular language recognition and graph connectivity in the context of **universal** transformers is indeed, as pointed out by the authors, a significant development compared to previously known length-specific constructions used in non-universal transformers. Such constructions are inherently length-generalisable, and I suspect that we might see a surge of experimental analyses of the generalisation of universal transformers following this theoretical finding.\n- The level of technical rigour deserves to be commended. While our intuition might tell us that the expressivity of a transformer respects an exponential relationship with the depth, formalising this concept is not a trivial task. It seems that the analysis can even be extended to other settings, i.e., if we know that a transformer can implement some binary associative operator, we can now rigorously show that unrolling the transformer can implement an iterated version of it. \n\n\n**Weaknesses**\n\n- In my eyes, a glaring weakness of the paper lies in the following fact. The construction using universal transformers was motivated by the limitations of Bingbin Liu's 2023 work, in which each sequence length gets its own transformer parametrization, yet the authors never experimentally test the effectiveness of a universal transformer trained on a short sequence, unrolled to a deeper network on a longer sequence. The paper already does a lot, I do not expect it to provide extensive experimental evidence as it is not the purpose of this work, but I do believe that this experiment could have strengthened the paper, given that a lot of it was motivated through the above mentioned limitations of Liu et al. 2023.\n- It is not entirely clear to me how realistic the setting of average-hard attention is. I believe that ideally, the results would also hold in the setup of standard softmax attention. But of course, I acknowledge that every theoretical study needs its assumptions, and these are the assumptions that we are dealing with here. Hard-attention seems more suitable for circuit-based analysis, whereas the softmax case might ultimately be a signal to noise ratio analysis.", "was_revised": true, "final_justification": "The theoretical analysis presented in this paper is thorough, creative, and addresses a very important open problem, that of formalising the expressivity of universal transformers. There has been ample evidence of improved out-of-domain generalisation of such models, making a rigorous, formal understanding their properties a valuable contribution.", "rebuttal": "Thanks for your review! We take your point that experiments with looped transformers would have been interesting to explore, but we have already invested a significant computational budget (about 1000 GPU hours) into the current regular language recognition experiments and are not in a position to rerun them.\n\n> It is not entirely clear to me how realistic the setting of average-hard attention is.\n\nRegarding the motivation and realism of the *average-hard attention* assumption (i.e., $\\tau \\to 0$), a central motivation of studying the AHAT model is that, without AHAT, it is unclear whether soft-attention transformers could even implement hard-attention retrieval over long contexts. Over any max context length bound, however, soft-attention transformers can arbitrarily approximate AHAT by multiplying all the weights in a head by a specific $\\tau$ (which shrinks as context length bound increases).\n\nSome versions of soft-attention transformers (e.g., if the weights can change with $n$) could thus directly simulate AHAT, but if the weights are fixed wrt $n$, it’s unclear if this simulation is possible (and seems intuitively unlikely). Thus, a central motivation in the AHAT model is to abstract away difficulties transformers might have in implementing hard attention. There is definitely opportunity for future work clarifying the relationship of the AHAT model to practice.\n\n> When $z$ is stored as $\\psi(z) = \\langle z, 1, -z, -1 \\rangle$, …\n\nYou are right that there is an additional $\\sqrt{2}$ factor with layer-norm – we will be sure to double-check that we have not omitted this anywhere. However, the constant factor is not significant, since it can be hardcoded into the weights and thus essentially ignored.\n\n> The graph connectivity construction requires a cubic amount of padding tokens. Do you think that it might be possible to reduce this amount of tokens?\n\nWe don’t quite see how to do this, but that doesn’t mean it’s not possible!"}]

Author rebuttal:

Meta-review: The paper studies the expressivity of weight-tied Transformers of depth scaling logarithmically with the context length $n$. They show that log-precision transformers operating over rationals with $\log n$ depth can recognize all regular languages and solve graph connectivity. They additionally show that depth recurrence is more beneficial than width or CoT where both need super polynomial size to compare. 

While we knew from prior work, that logarithmic depth Transformers can solve these tasks, the key contribution of the construction is uniformity, that the weights are not dependent on the context length, which was not true for prior work. Additionally, assumptions on the position encodings are much simpler, since the paper uses causal attention and average max-attention to avoid needing length-dependent encodings. This makes the construction a bit more realistic. 

I agree with the reviewers that the paper is a nice addition to the line of work on expressivity of Transformers. However there are some technical concerns with Theorem 4 and 5. As stated, the target class is a log-precision transformer, but the rounding semantics for the forward pass aren’t fully specified (there is no discussion other than a footnote). In particular, with masked pre-LayerNorm (involving a square-root) and averaging-hard attention (summing over an arg-max set), it isn’t clear (1) where rounding happens, (2) how ties are broken after rounding in the attention scores, and (3) how the averaging step is implemented (do we round during the multi-operand sum, or sum exactly then round once?). It is important to clarify this, to make sure your claims actually hold. 

Since this issue was only realized during the AC-SAC discussion, we have decided to go for a conditional-accept. We ask the authors to fix this concern and if they are unable to, then withdraw the paper. Additionally, we encourage the authors to improve clarity of exposition, point out the limitations of the lack of weight tying in the experiments, and add comparison to existing work on expressivity of looped Transformers. It would also be beneficial for the readers to (1) add a discussion about the dependence of the width and other parameters on the complexity of the regular language (perhaps in terms of the states of the minimal DFA needed to express it), and (2) more clearly explain the position encoding used, since it right now reads as 'there exists some positional encoding that works' but perhaps your result is stronger (correct me if I am wrong) that 'for any positional encoding function where the first position is distinguished', you can get a valid construction.
Decision: Accept (poster)