Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
Authors: Zhiyuan Li
Hong Liu
Denny Zhou
Tengyu Ma
Venue: ICLR 2024 poster (2024)
Keywords: Chain of thought
language modeling
circuit complexity
deep learning theory
Primary area: learning theory
TL;DR: We show both theoretically and empirically transformers with polynomial steps of CoT can simulate polysize circuits and thus are strictly more expressive than transformers without CoT.

Abstract: Generating a sequence of intermediate steps, \emph{a.k.a.}, a chain of thought (CoT), is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. However, the mechanism behind CoT remains unclear. 
This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness. Conceptually, CoT empowers the model with the ability to perform inherently serial computation, which is otherwise lacking in transformers, especially when depth is low. Given input length $n$, previous works have constant-depth transformers with finite precision $\mathsf{poly}(n)$ embedding size can only solve problems in $\mathsf{TC}^0$ without CoT. We first show an even tighter expressiveness upper bound for constant-depth transformers with constant-bit precision, which can only solve problems in $\mathsf{AC}^0$, a proper subset of $ \mathsf{TC}^0$. However, with $T$ steps of CoT, constant-depth transformers using constant-bit precision and $O(\log n)$ embedding size can solve any problem solvable by boolean circuits of size $T$. Empirically, enabling CoT dramatically improves the accuracy for tasks that are hard for parallel computation, including the composition of permutation groups, iterated squaring, and circuit value problems, especially for low-depth transformers.

Published as a conference paper at ICLR 2024
CHAIN OF THOUGHT EMPOWERS TRANSFORMERS TO SOLVE INHERENTLY SERIAL PROBLEMS
Zhiyuan Li
Hong Liu Stanford University h1iu998stanfordde
TTIC& & Stanford University zhi zhi yuanl fettiiiitticeeee edu
Denny Zhou
Tengyu Ma
Google DeepMind dernyzhou@gooqle.com com
Stanford University
tengyuma@@taaford.cce
ABSTRACT
Instructing the model to generate a sequence of intermediate steps, a.k.a., a chain of thought (CoT), highly effective method improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. However, the mechanism behind CoT remains unclear. This work provides theoretical un- derstanding of the power of CoT for decoder-only transformers through the lens expressiveness. Conceptually, CoT empowers the model with the ability perform inherently serial computation, which is otherwise lacking in transform- ers, especially when depth low. Given input length n, previous works have shown that constant-depth transformers with finite precision poly(n) embedding size can only solve problems in TC without COT. We first show an even tighter expressiveness upper bound for constant-deptie transformers with constant-bit bit pre- cision, which can only solve problems AC proper subset of TC However, with T steps of CoT, constant- deeth transformers using constant- bit precision and (logn) n) embedding size can solve any problem solvable by boolean circuits size T. Empirically, enabling CoT dramatically improves the accuracy for tasks that are hard for parallel computation, including the composition of permutation groups, iterated squaring, and circuit value problems, especially for low-depth transformers.
INTRODUCTION
Large Language Models (LLMs) exhibit exceptional capabilities in complex reasoning tasks such as mathematical problem-solving and code generation (Chowdhery et al., 2023; Anil et al., 2023; Achiam et al., 2023; Romera-Pee Paredes et al., 2023; Trinh et al., 2024), far surpassing standard su- pervised machine learning techniques. The key to unlocking these advanced reasoning abilities lies in enabling L.MS to generate intermediate steps, chain of thought (CoT), before finalizing the final answer. This can be achieved through various methods, including training or instruction tun- ing model with examples enriched with intermediate steps (Ling al., 2017: Cobbe et al., 2021; Nye et al., 2021; Chung et al., 2022), or through zero-shot or few-shot CoT prompting (Reynolds & McDonell, 2021; Nye al., 2021; ; Wei al., 2022; Kojima et al., 2022).
A natural explanation is that the intermediate steps provide extra information about the tasks and efficient approaches solving. that model can imitate. However, intriguingly. the efficacy of generating thought steps extends to zero-shot CoT prompting (Kojima et al., 2022), where L.MMs are only instructed with the prompt "let's think step by step",, and even using incorrect reasoning steps in the few-shot examples (Wang et al., 2022a; Madaan & Yazdanbakhsh, 2022). These observations suggest that the form of few-shot CoT prompting is as important as (if not more important than) its content, because merely instructing LLMs to generate the intermediate steps helps.
This paper aims to study why the form of CoT improves the reasoning capability of LLMs. Our hypothesis is that CoT allows for performing more serial computations that vanilla transformer cannot do without COT. We formulate and analyze this hypothesis through the lens expressive- ness with and without COT. We adopt the language of circuit complexity to discuss the capability

---

Published as a conference paper at ICLR 2024
of transformers. Previous works (Liu et al., 2022b; Merrill & Sabharwal, 2023b) have shown stan- dard decoder-only transformers (that output answers directly) are efficient parallel computers and can only express functions computable in an -pa)aplalle run-time with threshold circuits, TC computational model that allows the AND, OR, NOT and MAJORITY function with multiple inputs to be computed efficiently in parallel. We first show tighter upper bound (Theorem 3.1) for expressiveness of constant-per -rrccsssnnreiioon transformer it can only express a proper subset class of TC AC", where MAJORITY gates are not allowed. Our upper bound also more realistic because it handles the rounding issue or iterative addition of floating point numbers, while most previous results essentially only work for fixed-point number addition.
We then show that transformers equipped with CoT-allowing the transformer to auto-regressivell generate a sequence of intermediate tokens before answering the questions-can solve complex problems that inherently require serial computations (assuming well-known conjectures in com- plexity theory). Intuitively, without CoT. the number of serial computations conducted by the trans- former is bounded by the depth (which is considered T intermediate steps, the number of serial computations possible is boosted to T. Note that T can easily increase the sequence length increases where the depth is fixed number that depends on the architecture.
fixed constant for this work), whereas with
Concretely, we prove that constant-precision transformer with T intermediate steps and embedding dimension logarithmic in the sequence length can express any functions computable by a circuit of size T in Theorem 3.3. Taking T to be polynomial in the sequence length, the result suggests that transformers with polynomially many intermediate steps are capable of computing all circuits in with polynomial size, P/ /polyy, a superclass of P. Theorem 3.3 also implies that transformers with linearly many intermediate steps can compute all regular languages, including composition of non- solvable groups, like permutation group over five elements, Ss, which does not belong to AC" and is also widely conjectured to be out of TC As such, CoT makes transformers with bounded depth and precision strictly more powerful.
To corroborate our theoretical analysis, we empirically evaluate the capability of transformers in solving four core problems: modular addition, permutation composition, iterated squaring, and cir- cuit value problem. We train transformers to solve these tasks with large amount of synthetic data, with and without CoT, or with additional hint but not COT. The modular addition belongs to TC meaning it can be easily solved in parallel. Liu et al. (2022a) shows is solvable by constant-depth transformers with orgepriciionn and, indeed empirically depth I is sufficient for the parity problem (Modulo addition). The other three tasks are all conjectured require inherently serial computa- tions. As expected, the vanilla transformer either requires huge depth to solve these tasks (because the depth is the upper bound on the number of serial computation by transformers), or cannot solve the tasks at all. On the other hand, CoT can solve these tasks as long as the depth exceeds a small threshold. These experiments demonstrate CoT can provide more serial computations to solve com- plex reasoning tasks.
2 NOTATIONS AND PRELIMINARIES
Given a string I or set v, we use |z| to denote the size of For any n E N+, we define softmax : Rn + R" as (oofmax((x)), = exp(x;)/ Σi= exp(x;) for any x E IR" and i E [n]. We refer the readers to Appendix for all notations and preliminaries on eircuit complexity and transformers.
Given a vocabulary V a decoder-only transformer with parameter 0 and maximal input length Mmax maps sequence of input tokens (I1, ...,.,) E V to a probability distribution over V for all n S Amax denoted by Po(- Z..... 2n). We also define function (Fx by the token in V that maximizes (- (I,....Z,,) that is, (F*(2) arg max Po ..).
Next-token Generator: Given a vocabulary V, a next-token generator with parameter and max- imal input length Tamax is mapping from UNlmax>" to V. The main next-token generator we are interested in this work is decoder-only transformers, TF In)) where x; E V for all i E [n]. We also recursively define (F 2 TF (æI...., In, TFo for every positive integer and satisfying that TF )n)) A TFe zn). In other words, for all 0 I i S Amax n 1, the out- put with steps of CoT is Intitl TF (1)/1((11--. (#1,-.., Rn) TF (F - Taz Tntly -
S Rmmax 1 with the base case that
2

---

Published as a conference paper at ICLR 2024
Transformer Architecture Overview: The decoder-only transformer model we consider in this paper is very similar to GPT style architectures (Radford et al., 2019) and consists of four parts: a token embedding layer (TE), position encoding layer (PE), an output linear layer (OUTPUT), and a stack of I. identical layers serving as the "decoder" where I. is also called the depth of the model. Each decoder layer has two sub-layers: multi-head self-attention layer (ATTN) and a position-wis wise fully-connected feed-forward network (FF). Each layer mentioned above has its own trainable parameters and indexed by the layer name and the depth for attention and feedforward layers. That is we can split the model parameter 0 in the following way: 0 (OPE, TEE BOUTPUT: {0 gorithm 1). We defer the details of the standard transformer layers, including the token embedding layer TE, the positional encoding layer PE, the attention layer ATTN, the feedforward layer FF, and the output layer OUTPUT into Appendix B.2.
ATTN: 04 (-)), which are all trainable. (See formal definition in Al-
Algorithm Decoder-only Transformer, TFa and po
Input: Transformer parameter = (OPE, OTEEOOoUPUT 1O 0 ) and input tokens æ (Z1,...,,,, ) E V
Output: Output distribution po(- (1,....;..) for all i E [x]] and output token TF)(z).
1: h <- 10T00EEr0 [r;) + (iE(E), Vi E [n]]
2: for 0. 0..... L do
3:
(h)
"..,...,,) (+1)) + h3 (1+..5) + FF o0 (h, (140.))), Vi [n]
(L+.55
..... 11m (1+05)) - (h1) ...., (1) + ATTN (1
4: h
5: end for
6: p-(- ;i)..., + OUTPUTUUUTTTT (h, (
(11 V [r]
7: TFo arg max, (x "1.-..,Tn!
3 EXPRESSIVENESS THEORY FOR TRANSFORMERS WITH CHAIN OF THOTGHT(CoT)
3.1 FINITE PRECISION MODELING
In practice, training and inference of transformers are typically done with 16- or 32-bit floating point numbers. Thus in this paper, we mainly focus on the computation model of constant- constant-precision transformers, where the output of each arithmetic operation is rounded to the closest floating point number representable by a fixed number of digits following IEEE 754 standard (Definition B.2), thus avoiding the unrealistic infinite precision assumption made by prior works (Pérez et al., 2019; Dehghani et al., 2018).
Below we give an informal definition of Enite-precision transformers and defer the formal definition to Appendix B.3. We use Fe,s to denote the set of floating point numbers that can be expressed by I sign bit, exponent bit, and 2s precision bits. We further use rounde. (x) to denote the closest number to x in Fe,s, which is also denoted by [-le, for convenience. We break the tie by picking the
one with a smaller absolute value. We extend the definition of round to vector inputs by rounding coordinate -oieli.
Next, we define unite-precision summation over more two numbers by decomposing it as a chain of rounded binary addition in fixed order."
Definition 3.1 (Summation with Iterative Rounding). For any 8, n E N+ and vector x E R.,, we de-
fine summation with iterative rounding to 2s-bit precision as sum UnEN (Fe,.)" F. Fe, where for any
[[ee + 22le,a + 233 e,
N+ and E T ( A
Fn-1
+ Fr
0,5
c.8
We ignore the LayenNorm (Ba et al., 2016) in the usual transformer architecture for simplicity. Our pressiveness analysis can extend the transformers with LayerNorm with careful treatment. See Ap- pendix G. for discussion.
PTechnically speaking, instead of chain, the summation could also proceed like tree. This is more complicated case and leave for future work.
3

---

Published as a conference paper at ICLR 2024
We further define the following operations:
Finite-precision inner product: (x, vie.o sume,a ④ y);
Finite-precision matrix product: (A Xe,s B)es - ((At:) Bug e
Finite-precisten softmax: softmax.,. & [ixp(=))e,, /sum ((exp())))))
Finally, fiitte-precision transformer can be defined by replacing all the infinite- preciisooo operations by their frnite-precision counterparts listed above. (See details in Algorithm 4). We postpone the details of the finite-pren snite-precisio version of individual transformer layers into Appendix C.
3.2 CoT: COMPLEXITY CLASS FOR CONSTANT-DEPTH TRANSFORMERS WITH CoT
In this subsection, we define the complexity class consisting of all the problems that can be solved by some decoder-only transformers with CoT with finite precision.
Definition 3.2 (CoT), Given finite vocabulary V and four functions T(n), d(nn,, s(n), e(n), in- formally, (T))))), d(n), s(n), e(n)) is the family of problems solvable by a transformer with a constant depth, s(n) bits of precision, e(n) bits of exponent, embedding size d(n) and T(n) steps of COT. Formally, we say a problem L U Unex+ y - {0.1) 13 is in CT d(n), s(n), iff there is integer L and three functions T'
O(T(n)), (n) O(d(n)), s (n) (ss()), e'(n) = (e(n)), such that for every positive integer n. there is a L-layer decoder-only transformer, denoted by TFa., with embedding size d' (n), 2s (n) bits of precision, and e' c'(n) bits of exponent, that can output ((x) given any input x in V", using T" (n) steps of chain of thought. Mathematically,
means
TF TF (=) (x) ((x), Va E V".
(1)
We also extend the definition of CoT a class of function instead of single function. For example, (TT) poly(n), s(n), e(n)) & ULEN+ CoT(T'(n), n² e(n)).
Definition 3.3 (T). We define T[d(n), sn)) & CoT[O, d(n),, as the problems that a constant- depth, constant-precision decoder-only transformer can solve with (s((n) bits of precision, O(d(n) embedding size and without CoT (or with only 0 step of CoT)..
By definition, (T), d(n), s(n), is monotone in all T(n).d(n) s(n), e(n), egg. CTT d(n),,nn,, s(n), e()) S [oT(T((m,, d(n), s(n), if T')) T(n) for all n N. In particular, we have T(d(n), s(n) a CoT d(n), s(n)) S (o d(n), s(n)).
Note the above-defined complexity class CoT is non-unifone non-uniform, that is, it allows a different program for every input size. This is in contrast to previous works (Pérez al., 2019; 2021: Yao et al., 2021; Weiss et al., 2021: Chiang et al., 2023; Hao et al., 2022; Merrill & Sabharwal, 2023a; Merrill et al., 2022) which focus on the uniform transformer classes. Please refer to Appendix H for discussion.
3.3 TIGHTER UPPER BOUNDS ON TRANSFORMER EXPRESSIVENESS
Existing works (Merrill & Sabharwal, 2023b; Liu et al., 2022a) have shown that constant depth, polynomial width, and log precision transformers using TC" circuits. These results are built on the fact that multiplication and division of n-bits binary numbers (Hesse, 2001), as well as the iterated addition over n different n-bit binary integers are in TC
be simulated in small parallel time, i.e,
However, such TC² expressiveness upper bounds may be unrealistic for transformers operating with floating point numbers. (Merrill & Sabharwal, 2023b; Liu et al., 2022a) implicitly assumes when adding more than one Coating-point numbers, the algorithm first compute the exact answer without rounding using arbitrarily more precision and only perform rounding in the end. How- ever, in practice rounding happens after each addition between two numbers and it is open if such TC upper bounds still holds. Immediate rounding makes iterated addition over floating point numbers no longer associative (Goldberg, 1991), for example, round(a + round(b + c)) * round + b) + c)). The associativity of integer addition plays crucial role in the fact that the iterated addition over different n-bit binary integers are in TC".
In this section, we present two novel expressiveness upper bounds for transformers which rounds the immediate result after step of arithmetic operation. First, we show strictly tighter upper bound
4

---

Published as a conference paper at ICLR 2024
Hint
Label:
2
5
1
4
2
CoT
Label:
2
Input:
Input:
S5, Hint, accuracy %
55, CoT, accuracy %
12
100
20
20
12
100 100
100
16
20
20
100
100
20
20
20
19
20
20
19
100
100 100 100
100
Depth
100
100
21
20
21
19
20
20
20
20
Depth
5
100
100
100
100
100
100
100
100
100
100 100
100
100
20
20
21
20
20
20
20
20
20
20
20
100
100 100
100
100
100 100
100
100
100 100 100
m -000
20
20
19
19
20
20
21
20
21
21
21
m
100
100 100
100
100
100 100
100
100
100 100
100
100
20
20
20
20
21
19
20
20
20
20
20
N
-0100
100 100
100
100
100
100
100
100
100
100
100
56
21
19
19
20
19
20
20
20
19
20
21
100
100
100
100
100 100 100
84
84
84
54
46
3
6
9
12
15
21 Length
18
24
27
30
33
36
6
9
12
15
21 Length
18
24 27 30 33
36
Figure 1: Permutation Composition (Ss). The label is the composition of all the permutations, where given two permutation σ = (oi..... ds), ग ...,.... Ws), we define a o π - (Tm, Oxs). The chain thoughts and hints are the partial compositions. Only CoT can solve this task well, as predicted by our Theorem 3.5. Note for the most time the accuracy without CoT is 20%, which is better than randomly guessing number between and 5.
than TC which AC for constant-depth transformers with both constant bits of precision and exponents. (Theorem 3.1) This suggests when input length is sufficiently long, constant-precisten transformers cannot count eventually, even in the sense of modular. For example, it is well known that no AC circuits can decide the parity of binary string.
Theorem 3.1. (n), 1, S poly(),, 1, AC".
Our second result, Theorem 3.2, shows that when the number of bits for exponent is 0 (i.e. fixed- point numbers), TC upper bounds for expressiveness of constant- depth, log prgeprcciioon transformers still holds, even with the correct rounding defined in Definition B.2.
Theorem 3.2. (n), log(n)) 0] CoT(1, (nly log(n), 0] TC
The main technical difficulties in above two results are showing sum (Fe,s)" + Fe,s has AC" (resp. TC²) circuits when e, are both constants (resp. e 0, (llo(n)))) We view iterated addition with rounding over F being Re,s- The first result are due to a novel application of classical Krhon-Rhodes decomposition theorem for automata (Theorem D.2), where we use the property of rounded addition that for all [ + yle,e 2 [a' + yle.s. We formalize this property in Definition E.2 as ordered automata and show all ordered automata are counter-free free Theorem E.3 and thus can be simulated by AC circuits (McNaughton & Papert, 1971).
automaton with both state space and vocabulary
I, x, E Fe,s, E Fe,er I 2
The proof technique for Theorem 3.1 does not generalize to Theorem 3.2 because the depth of AC circuits constructed before depends on the number of the states of the automaton and thus is not constant. Our proof for Theorem 3.2 is motivated by Algorithm 1 in Liu et al. (2022a) for the automaton named 'GridWorld'.
However, it remains open whether constant-depth. log preericcioon transformers with log bits for expo- nents [[poly(n), log(n), log(n)) ] or even constant bits for exponents [[poly(z),,oo(()) 1] have TC circuits.
3.4 COT MAKES TRANSFORMERS MORE EXPRESSIVE
Now we are ready to present our main theoretical results (Theorem 3.3) which characterize the expressiveness of constant-depth, constant-precision transformers with CoT and O(log(n)) embed- ding size. log(n) embedding sizes is necessary to ensure that the position embeddings for in- puts are different. All the lower bounds for transformer expressiveness (with or without CoT) are proved for fixed-point numbers, i.e., without using any exponent bits. Allowing exponent bits will only make transformers more expressive. For convenience, define CoT(T(n) (()))(()) e [TT()(m), d(n), sn)), 0). The omitted proofs in this section can be found in Appendix F.
5

---

Published as a conference paper at ICLR 2024
Theorem 3.3. For any polynomial function T N+ - SIZE((()) S (n), n, 1]. In
particular, P/poly- = [oT[poly(n)) log 1].
Compared to Theorems 3.1 and 3.2, Theorem 3.3 shows that allowing polynomial steps of CoT strictly makes constant-depth. depth, constant-precisiin decoder-only transformer more expressive and log-precision transformers more expressive under a standard hardness assumption that TC S P/poly.'
Proof sketch of Theorem 3.3. The high-level proof idea is that we use each step in CoT to simulate one gate operation in the target circuit and write the gate output next input. To do that, we use one position encoding to store the information for each gate, which contains four parts: the current gate type (AND, OR, NOT, TRUE, FALSEJ, the two input gates id and the current gate id. Since there are total (n) gates, d(n) e (log n) embedding size suffices to store the above information. And the CoT here is constructed be the values of each gate in the increasing order of id. Therefore, in each step, we can use attention to pull the value (either computed already or it is input) of the two input gates and use feedforward network to compute the value of the current gate.
As we can see from proof sketch, a crucial step for CoT simulate any depth circuit is write the output token back to the next input position. This action resets the "depth" of the intermediate output in the circuit to 0. Our theory explains the ablation experiment in Wei et al. (2022) that when the model is prompted to output a only sequence of dots (...) equal to the number of tokens needed to solve the problem, the performance is no better than directly outputting the answer.
Because every regular languages can be recognized by finite state automaton (Definition D.1) and finite state automata can clearly be simulated by linear size circuits. The following holds as direct corollary of Theorem 3.3
Corollary 3.4. Every regular language belongs to [n, n, 1].
Below we give a concrete regular language that constant-depth. poly-embedding-sitn size transformers solve only with COT, the wording problem of permutation group over 5 elements, Sg in Theo- rem 3.5, under a standard hardness assumption that TC Ş NC² (Yao, 1989).
Definition 3.4 (Wording problem of group G). Given elements from G. (gi..... In), we use LG to denote the decision problem of whether 91 o 92 o o In is equal to the identity of G.
For convenience, in this paper extend the domain of LG to the sequence of groups encoded by binary strings. The proof of Theorem 3.5 is a direct consequence of Theorems 3.2, 3.3 and 3.6.
Theorem 3.5. Assuming TC² Ş NC1, the wording problem of Ss Ls, is in CoT [n, log n, 1] but not (n), n).
Theorem 3.6 (Barrington (1986)). The wording problem of S3 is NC' -complete under AC re- ductions. That is, for any decision problem L in NC², there a family of AC" circuits [Cn 1o0 (constant depth, poly(n) fan-outs), such that for any E N+ and {0, 1)" L(x) Ls, (C.(z))
Proof of Theorem 3.5. First Cs, is a regular language, thus belonging to CoT [n, log 1] by Corol- lary 3.4. Since Ls,, is NC² NC' complete by Theorem 3.6, assuming TC ç NC², Ls, does not belong to T This proof is completed by applying Theorem 3.2, which says (p)))y(n). log(n)) C TCº. O
Results for poly(n) embedding size: So far we have been focusing on the expressiveness of trans- former with Olognn embedding size, it is natural to ask can whether transformers can also benefit from having à larger embedding size, say poly(n)? Our Theorem 3.7 answers this question positively by showing that log-precision (resp. constant-precision) constant-depth poly-embedding- size decoder-only transformers with T(n) steps of CoT can simulate any T(n)-size circuit with some TC (resp. AC oracle gates with poly(n) input.
Formally, given a decision problem L: U (0, 13" + 10, we use C, to denote the restriction of L on {0, 1}". which can also be viewed as an single gate with n fan-ins. We define problems that can be solved by circuits with certain size of gates (including oracle gates) by Definition 3.5."
IIndeed such separation can be shown for any polynomial steps of CoT by padding polynomially many tokens to input.
'Our definition of complexity class solvable by circuits with oracle is slightly different from that in literature (Wilson, 1985), where the size of the oracle circuits refers to the number of wires, whereas ours refers to the number of gates.

---

Published as a conference paper at ICLR 2024
Label:
1
Label: Input:
Hint
CoT
Input:
3 5
6
2
3
C7. Hint, accuracy %
C7, CoT, accuracy %
100
Depth
Depth
N-
100
93
7
15
31 Length
63
127
15
31 Length
63
127
Figure Modular Addition(C+). The label the of the inputs modulo positive integer, which 7 in this case. The chain thoughts and hints are the partial modular sum. Low-depth transformers with hint can solve this task well for reasonable input sequence length, but with cot the performance is much better, especially with a long input sequence, as predicted by our Theorem 3.3. See experiments for C2 in Figure 5.
Definition 3.5 (SIZE For any decision problem and T(n) S (npoly(n)), we define (T(m) as the set of decision problems L' such that there exists p(n) E poly(n) and circuits j where Cn contains at most ((T(n)) AND, OR, NOT, and Lp(n) gates. For complexity class C, we define SIZE (T(n)) & (T(EIIIEE(((())
Theorem 3.7. For any T(n) E poly(n), it holds that SIZE + T(n)] (T)) poly(n), log Specifically, for T(n) O, we have TC SIZE TC [o poly(n), log n]] = [[ log
[1]
Theorem 3.8. For any ['n) poly(n). it holds that SIZE [1 T())] (n), (n), 1]. Specifically, for [nn) O, we have AC = SIZE [1] poly . 1| = (p), 1].
Theorem 3.8 shows that for T(n) poly(n) steps of CoT, using poly(n) embedding size does not improve expressiveness over using log(n) embedding size (Theorem 3.3). because SIZET< [poly(n)] = SIZE [poly(n)] = SIZE(poly(n)). However, Theorem 3.9 shows that for any specific polynomial (n)) n² steps of CoT, increasing embedding width from O(log(n)) to poly(n) make transformers strictly more powerful.
Theorem 3.9. For any s(n) = O(log m), Tllo n, s(n)) ç T[poly(m), 8(r)] and for E N. [n log mi s(n)) Ç ,
COT EMPIRICALLY IMPROVES EXPRESSIVENESS OF LOW-DEPTH TRANSFORMERS ON INHERENTLY SERIAL PROBLEMS
This section is empirical study of the expressiveness of decoder-only transformers with CoT on four different arithmetic problems: modular addition, permutation composition (Ss), iterated squar- ing, and circuit value problem. The first problem is parallelizable and can be solved by constant- depth transformers with log precision while the latter three are inherently serial under some standard hardness assumptions in computational complexity cryptography. As prediction of our theory, we expect to see a huge improvement in accuracy when CoT' turned on.
General Setup. To examine the expressiveness of decode-only transformers with and without CoT on these four types of problems, we train the transformer using Adam (Kingma & Ba, 2014) from random initialization in the online supervised setting for each problem and each different sequence length n. At each step, we sample a batch of training data from a distribution Pa (I) where æ = (I1, ... ... zn,) is training data and y f ("11.... ,,,,,, the label. We always set xn be "=', We consider three different settings, base, cot, and hint:
base: The optimization objective is simply Enasa (0) 2 Erep leo (2)(2), f()))
cot: We manually design chain of thought for each instance x, which string in v and we denote by c(z). We ensure the last token of c(z) is always equal to the answer, (x)... With j e c(:)), the concatenation of and c(x), and m be the length of c(x), the optimization objective is (f) & ma Ezzzp Σn+m In pe (#141 (ū.....,;)). hint: Even if the transformer has better performance in cot setting than base setting, may argue that besides the difference expressiveness, cot setting also has statisti-

---

Published as a conference paper at ICLR 2024
Hint
Label:
16
256
731
731
CoT
Label:
4
16
256
731
Input:
997
Input:
997
12
256
731
IS1000, Hint, accuracy %
IS1000, CoT, accuracy %
12
72
9 12
9
94
85
74
65
57
100
100
100
100
100
Depth
6
56
49
Depth
100
100
100
3
57
47
40
34
3
100
100
100
100
100
2
45
38
33
30
100
100
100
100
100
14
30
62
126
6
14
30
62
126
Length
Length
Figure 3: Iterated Squaring(IS). The vocabulary V - 10.1,.... 1,=, with ' 1000. We randomly generate input of format (r,p, 2,,,,........
2, .,....,2,. with 1 < r.P S T 1, p being prime and random number of '2 tokens (at most m.) The label is (n.(n) = (r²*) mod p. CoT and hints are (i) Though our construction does not exactly satisfy the technical conditions of the hardness assumption, this problem is difficult for transformers without CoT to learn, but be perfectly expressed with CoT even if depth is only
cal advantage over base, as cot provides more labels and thus more information about the groundtruth f to the model. This motivates to design the following loss which provides the chain of thought c(x) as the labels. Here for simplicity, we assume the length of c(x) is equal to n. Formally we define Enint
Eacp E - In po ,i,...,,;;) x:)).
Performance Evaluation. Since train transformers using fresh sampled synthetic data each step, the training accuracy/loss is just the same as validation accuracy/loss. For base and hint setting, evaluate the accuracy of the final answer directly. For cot setting, directly evaluating the final answer is too easy because it only measures the ability of the transformer to correctly compute the last step since CoT given as inputs. Ideally, should measure the answer output by transformers after suto-reerresivelly generating |c(x)] tokens. But for computational efficiency, we measure the probability that transformers can predict all tokens the given CoT correctly. Note this probability is a lower bound of the ideal metric because there is a small possibility that transformers can answer correctly with a wrong COT. Nevertheless, even with this slightly more difficult evaluation metric, transformers in cot setting still optimize much faster than without COT.
Due to space limit, we defer the details of the training and each setting to Appendix A. Our experi- mental results are presented in Figures to 4.
Unsurprisingly, the accuracy in hint setting is always higher than base setting. Due to the space limit, we postpone all results for base settings into Appendix A. For the problems hard for parallel computation, i.e., permutation composition, iterated squaring, and circuit value problem, find that cot is always better than hintand base, and the improvement is huge especially when depth is small. Our experiments suggest that turning on CoT drastically improves the expressiveness of low-depth transformers on problems which are hard to be parallel computed, i.e., those inherently serial problems.
Our Findings:
5 RELATED WORKS
Despite the numerous empirical achievements, unanswered questions concerning the inner workings of neural networks capable of algorithmic reasoning. The ability self-attention to create low- complexity circuits has been recognized (Edelman et al., 2022: Hahn, 2020; Merrill et al., 2021), as well as its capacity to form declarative programs (Weiss et al., 2021), and Turing machines (De- hghani et al., 2018: Giannou al., 2023; Pérez et al., 2021). Moreover, has been demonstrated that interpretable symbolic computations can be drawn from trained models (Clark et al., 2019; Temney al., 2019; Vig, 2019; Wang et al., 2022b).
Liu et al. (2022a) is a closely related work to ours, which studies the expressiveness of low-depth transformers for semi-automata. Their setting corresponds to using only 1 step of CoT and our contribution is to show that allowing more steps of CoT enables the transformers to solve more
$ NNoe such alignment is in general impossible because the CoT c(x) can be even longer than x itself. However, in our four settings, there exist meaningful ways to CoT c(T) as hints for earlier tokens in .r.
8

---

Published as a conference paper at ICLR 2024
Hint
Label:
NA
NA
NA
NA
2
AND
NOT
NA
Input:
T
NA
NA
1
F
NA
NA
AND
1
2
3
NOT
3
NA 4
CoT
NA
NA
NA
NA
NA
NA
NA
NA
NA
CVP, Hint, accuracy %
CVP, CoT, accuracy
12
100
100
100
100
12
100
100
100
100
9
100
100
98
100
100
100
100
100
Depth
6
10U
100
100
Depth
6
100
100
190
m
100
100
86
72
3
100
100
100
100
2
100
80
2
100
100
100
98
67
62
100
100
100
100
7
15
31
63
7
15
63
Length
Length
Figure 4: Circuit Value Problem(CVP), Given randomly generated circuit with mn gates (sorted by topological order). the vocabulary V [m]] u (TRUE, FALSE, AND, OR, NOT, NA, =}. Each gate represented by four consecutive tokens, which are gate type, two input gate ids, and the current gate id. The output is the value of the last gate m. CoT and hints also contain 4 tokens for each gate, which are gate type, two input gate values, and the current gate value.
difficult problems than semi-automata. especially those inherently serial problems, like the circuit value problem, which is P-complete.
Constant precision versus logarithmic precision: We note that most previous literature on the expressiveness of transformers focuses on the setting of logarithmic precision, including (Merrill & Sabharwal, 2023b; Merrill et al., 2022; 2021; Liu et al., 2022a), etc. One main reason as argued by Merrill & Sabharwal (2023a) is that log precision allows the transformer to use uniform attention over the rest tokens. However, recent advancements in LLMs showed that uniform attention might not be necessary towards good performance, at least for natural language tasks. For example, one of the most successful open-sourced LLM, LLAMA 2 (Touvron et al., 2023) takes the input of sequence of 4096 tokens and uses BF16 precision, which has sign bit, 8 exponent bits and mantissa bits (plus one extra leading bit). As consequence, for example, BF16 cannot express any floating-poine point number between 2 256 and 2 2 258, which makes LLAMA impossible to compute uniform attention over 257 elements.
concurrent work Feng et al. (2023) also studies the benefit of CoT via the perspective of expres- siveness, where they show with COT, transformers can solve some specific P-complete problem. Our result is stronger in the sense that we give a simple and clean construction for each problem in P/ ppply.. We also note the slight difference in the settings, while we mainly focus on constant- precision transformers with Ollogn) n.) embedding size, they focus on O(log(n) precision transform- ers with bounded embedding size.
CONCLUSION
We study the capability of CoT for decoder-only transformers through the lens of expres- siveness. We adopt the language of circuit complexity and define new complexity class CoT(I(()), ((n), s()), e(n)] which corresponds to a problem class solvable by constant-depth, constant-precisioon decoder-only transformers with ((](n)) steps of CoT, O(d(n)) embedding size and floating-pott numbers with O(e(n)) bits of exponents and (ss(n) bits of significand. Our theory suggests that increasing the length of CoT can drastically make transformers more expres- sive. We also empirically verify our theory in four arithmetic problems. We find that for those three inherently serial problems, transformers can only express the groundtruth function by using COT.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
We thank Wei Zhan and Lijie Chen for providing references on circuit complexity and various inspiring discussions. We thank Cyril Zhang and Bingbin Liu for helpful discussion on Khron- Rhodes Decomposition Theorem. We thank Kaifeng Lyu for his helpful feedbacks.
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt. Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. Palm 2 technical report. arXiv preprint arXiv:2305. 2023.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
David A. Barrington. Bounded- wiith polynomial-size branching programs recognize exactly those languages nc. pp. 1-5, 1986.
Ashok K Chandra, Steven Fortune, and Richard Lipton. Unbounded fan-in eircuits and associative functions. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp- 52 60, 1983.
David Chiang. Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. arXiv preprint arXiv:2301.10743 2023.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi. Sasha Tsyyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov. Katherine Lee, Zongwei Zhou, Xuezhi Wang, Bren- nan Sacta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Helisr-Hlll,tem,, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240): 1-13,, 2023.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction finetunne lan- guage models. arXiv preprint arXiv:2210. 1416, 2022.
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does bert look at? an analysis of bert's attention. arXiv preprint 1rXiv:1906.0434// 2019.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2 10. 10.1111..1110 14168, 2021.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint 1rXivv1807.038/1 2018
Benjamin L Edelman, Surbhi Goel, Sham Kakade. and Cyril Zhang. Inductive biases and variable creation self-attention mechanisms. In International Conference on Machine Learning, pp. 5793-5831. PMLR, 2022.
10

---

Published as a conference paper at ICLR 2024
Guhao Feng, Yuntian Gu, Bohang Zhang, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. arXiv preprint arXiv:2305. S.tv:2335.15003 15408, 2023.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dim- itris Papailiopoulos. Looped transformers as programmable computers. arXiv preprint MrXiv:2301.13196 2023.
David Goldberg. What every computer scientist should know about floating-pon point arithmetic. ACM computing surveys (CSUR), 23(1):5-48, 1991.
Michael Hahn. Theoretical limitations of aelf-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention trans- formers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-811 -1000-810, 2022.
William Hesse. Division is in uniform tcO. In International Colloquium Automata, Languages, and Programming, pp. 104-114. Springer, 2001.
IEEE. Ieee standard for floating-poin arithmetic. IEEE Std 754-2008, pp. 1-70, 2008. doi: 10. 1109/EEESTD. 26115..
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models zero-shot reasoners. Advances in Neural Information Processing Systems, 2022.
Kenneth Krohn and John Rhodes. Algebraic theory machines. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, 116: 450-464 1965.
Wang Ling, Dani Yogatama, Chris Dyer. and Phil Blunsom. Program induction by rationale gener- ation: Learning to solve and explain algebraic word problems. arXiv preprint arXiv: 170.v:1705.04166, 2017.
Bingbin Liu, Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts automata. arXiv preprini arXiv:2210. 10749, 2022a.
Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, and Yang You. Towards efficient and scalable sharpness- aware minimization. In Proceedings of the IEEEICVF Conference on Computer Vision and Pattern Recognition, pp. 12360-12370 2022b.
Alex Lombardi and Vinod Vaikuntanathan. Fiat-shamir for repeated squaring with applications to ppad- and vdfs. In Advances in CryptolgyyCRYPPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceed- ings, Part III, pp. 632-651. Springer, 2020.
Aman Madaan and Amir Yazdanbakhsh. Text and patterns: For effective chain of thought, it takes two tango. arXiv preprint arXiv:2209.07686 2022.
Oded Maler. On the krohn-rhodes cascaded decomposition theorem. In Time for Verification: Essays in Memory of Amir Pnueli, pp. 260-278. Springer, 2010.
Robert McNaughton and Seymour A Papert. Counter- Free Automata (MIT research monograph no. 65). The MIT Press, 1971.
William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers. In Thirty- seventh Conference on Neural Information Processing Systems, 2023a.
William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of preciiiciiion trans-
formers. Transactions of the Association for Computational Linguistics, 11:531-545 2023b.
11

---

Published as a conference paper at ICLR 2024
William Merrill, Yoav Goldberg, and Noah A Smith. On the power of saturated transformers: A view from circuit complexity. arXiv preprint 10X1:33106.1611,,, 2021.
William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Compulational Linguistics, 10:843-856, 2022.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114. 2021.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprini arXiv: 1xXi::9011003299 2019.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing complete. The Journal of Machine Learning Research, 22(1):3463 -3403,3377222 2021.
Nicholas Pippenger and Michael Fischer. Relations among complexity measures. Journal of the ACM (JACM), 26(2):361-38) 1979.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 1(8), 2019.
Laria Reynolds and Kyle McDonell. Prompt programming for large language models: Beyond the few-shot paradigm. In Extended Abstracts of the 2021 CHI Conference Human Factors in Computing Systems, pp. 1-7, 2021.
Ronald L Rivest, Adi Shamir, and David A Wagner. Time-lock puzzles and timed-release crypto. 1996.
Bernardino Romera-Paredess Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 2023. doi: 10. 10.1038/s41586
lan Tenney, Dipanjan Das, and Ellie Pavlick. Bert rediscovers the classical nlp pipeline. arXiv preprint arxiv: /905. 09t.: 05550, 2019.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.09288. 2023.
Trieu H Trinh, Yuhuai Wu, Quoc V Lc, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(7995):476 482, 2024.
Jesse Vig. Visualizing attention in transformer-hased language representation models. arXiv preprint 1rXiv:1904.02060 02679, 2019.
Boshi Wang, Sewon Min, Xiang Deng, Jiaming Shen, You Wu, Luke Zettlemoyer, and Huan Sun. Towards understanding chain-of- offthhtthtt prompting: An empirical study of what matters. arXiv preprint arXiv:2212.10000, 2022a.
Kevin Wang, Alexandre Variengien, Arthur Commy, Buck Shlegeris, and Jacob Steinhardt. Inter- pretability in the wild: a circuit for indirect object identification in gpt-2 small. arXiv preprint wwXiv:2211.00555 2022b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoe Le, and Denny Zhou. Chain of thought prompting clicits reasoning in large language models. Advances in Neural Information Processing Systems. 2022.
Gail Weiss, Yoay Goldberg, and Eran Yahav. Thinking like transformers. In International Confer- on Machine Learning, pp. 11080- 1090. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
Christopher B Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31(2):199-11,, 1985.
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pp. 10524-10533. PMLR, 2020.
Andrew Chi-Chih Yao. Circuits and local computation. pp. 186-196, 1989.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention net- works can process bounded hicrarchical languages. arXiv preprint arXiv:2105,11115, 2021.
13

---

Published as a conference paper at ICLR 2024
CONTENTS
1 Introduction
2 Notations and Preliminaries
3 Expressiveness Theory for Transformers with Chain of Thought(CoT)
3.1 Finite Precision Modeling
3.2 CoT: Complexity Class for Constant-depth Transformers with CoT
3.3 Tighter Upper Bounds on Transformer Expressiveness
3.4
CoT Makes Transformers More Expressive...
4 CoT Empirically Improves Expressiveness of Low-Depth Transformers on Inherently Serial Problems
5
Related Works
Conclusion
Additional Experimental Results
16
Additional Notations and Preliminaries
17
B.1
Circuit Complexity
18
B.2
Transformer Layers
18
B.3
Floating Phoating-point Numbers
19
Details on Finite-Precision Layers
20
Preliminary of Automata and Krohn-Rhodes Decomposition Theorem
20
D.I
The Krohn-Rhodes Decomposition Theorem
21
D.2 Counter-free Automata
22
E Proofs for Expressiveness Upper Bounds (Section 3.3)
23
E.1 Proofs for Theorem E.
23
E.2 Proofs for Theorem E.2
24
F Proofs for Expressiveness Lower Bounds (Section 3.4)
25
F.1 Proof of Theorem 3.3
................................
25
F.2 Proof of Theorems 3.7 and 3.8
27
F3 Proof of Theorem 3.9
................................
30
F.4 Auxiliary Lemmas
31
Discussion on Variants in Transformer Architecture
32
G.1 Extension Transformers with LayerNorm
32
14

---

Published as a conference paper at ICLR 2024
G.2 Extension to Transformers with Multihead Attention
32
Discussion on Non-uniformity
32
15

---

Published as a conference paper at ICLR 2024
A ADDITIONAL EXPERIMENTAL RESULTS
In this section present the experimental results for base setting which is omitted in the main paper and the details of training and each task. We use the nanogpt codebase for language modeling.
Adam with 10-5 learning rate, 0 weight decay, 83 0.9, 82 = 0.95, and gradient clipping with threshold equal to 1.0. The total training budget is 10 steps and we use linear warmup in the first 2000 steps starting from 10-6, For each step, we use fresh sampled batch of size 64 from population distribution. We turn off dropout and use float16. We vary the depth of the transformer for different settings while the embedding size and the number of attention heads are fixed to be 512 and 8 respectively.
Training Details. For all settings
Below we present the setting and the experimental results of each problem respectively.
Modular Addition (Cp). Given any positive integer the vocabulary of modular addition problem
,, in the following way: for each i In 11, we independently sample 2; from 1P 1} and set I, = '='. The label is f*) = E I4 mod p and CoT c(xx) is (Et= 2y mod p) Unsurprisingly, this task is easy task for transformers because attention can easily express the average function across different positions, and is the sum function. Then the feedforward layers can compute the modulus of the sum and m. We note that the high training accuracy here is not contradictory with our Theorem 3.1, because our sequence length is not long enough and float16 is like oog-precision. This intuitive argument elegantly extended to all solvable groups by leveraging Khron-Rhodes decomposition theorem by Liu et al. (2022a).
{0, (o.......7 P - =, We generate I
Permutation Composition (Sp). Given any E N+, the vocabulary of permutation composition problem is (1. (,), =}. We pick n = (p + 2)m and generate x = ..1,.... .n.) in the 'C, T(p+2); ")" and independently (x(++2)(i-1)) ())(())))))--. 1)+2.....
following way: for each E [m]. we set 2(p+2)(i-1++1
())+))((=)+++++1 We set I, to be '='. Different from other settings which only have the label at one position, we have p labels for
sample random permutation over [p),
this setting, which is the composition of 0 o.. The CoT c(x) is the partial composition from σj to on.
As mentioned in Section 3, unless TC = NC², composition of Sp cannot be computed by TC for any p 2 5, since composition of Sp implies the wording problem of Sp. which is NC -comceeee under AC reductions. Since all constant-depth noly-embedding-size transformers can be simulated by TC circuits (Theorem 3.2), shallow transformers not able solve the composition problem of Sp for 2 5. Our experimental results in Figure matches this theoretic prediction very well.
Iterated Squaring (IS). Iterated squaring refers to the following problem: given integers r, n. P. define the iterated squaring function (n) & ,22 mod p. It is often used as hardness assump- tions in cryptography (Rivest et al., 1996; Lombardi & Vaikuntanathan, 2020) that iterated squaring cannot be solved in n o(n) time even with polynomial parallel processors under certain technical conditions (e.g., is the product of two primes of a certain magnitude and there is some requirement on the order of as element of the multiplicative group of integers modulo p). In other words, people conjecture there is no faster parallel algorithm than doing squaring for n times.
Circuit Value Problem (CVP). Circuit value problem is the computational problem of computing the output of given Boolean circuit on given input. It is complete for P under -eddrecucs.. This means if one can solve CVP with constant-depth transformers (or any TC circuits), then any problem in P becomes solvable by TC which is widely believed to be impossible.
16

---

Published as a conference paper at ICLR 2024
Label:
Label:
0
0
Hint
Input:
Input:
1
0
C2, Hint, accuracy %
C2. CoT, accuracy
100
100
100
100
100
100
Depth
Depth
N.
100
100
100
100
N-
100
100
100
100
100
100
100
99
100
100
100
100
100
15
31 Length
63
127
7
15
31 Length
63
127
Figure 5: Results of Modular Addition C2.
Corracy
accuracy
Base, accuracy
25
51
22
26
13
11
100
95
54
73
Depp
25
Depth
22
20
22
24
11
12
100
27
72
64
Length
Longth
Longth
Figure Results base on Permutation Composition, Iterated Squaring, and Circuit Value Problem.
C2, Base, accuracy
Base, accuracy %
Depth
Depth
127
127
Length
Length
Figure 7: Results of Modular Addition base C2 and Cr.
We can observe that the accuracy of base setting is also lower than that of hint setting.
B ADDITIONAL NOTATIONS AND PRELIMINARIES
We use and to denote the set of natural numbers and real numbers respectively, For any n E N+, We define relu(z:) 2 max(x,, 0). For vector x, we use Ladd to denote the vector containing coordinates of from position to position b. For matrix M,
we define [n] 2, ........,,, nz.
define Mardh to denote the submatrix by selecting rows from a₃ to b1, columns from 02 to by. We also a1 to denote the subset of indices from aN to the end, bı denote the subset of indices from the beginning (1) to by and to denote all indices. Given two non-nege non-negative functions f.g. we say (n) O(g(n)) (resp. f(n) R(g(n))) iff there exists C 0. such that for all 2 0.
17

---

Published as a conference paper at ICLR 2024
fn) I Cg(n) (resp. f(n) 2 Cg(n)). We use poly(n) & {T: : N + N 3k 0,T(m) = On to denote the set of functions with at most polynomial growth rate.
Given a string I or set 2, we use |x| to denote the size of z. We use o(x) = - |o| - denote the value of binary number represented by binary string I. We use (in denote the usual binary encoding of natural number using & binary bits in the sense that 6 (bbin((r)) = x and sbing (2) to denote the signed binary encoding, which ( (l....,1) 1). For any n E N define softmax _ - I" as (softmax(z)), exp(z))/ E exp(z;) for any R" and i E [n]. We use O to denote the element-wise product of two vectors. We use allo or (a, b) to denote the concatenation of two vectors and b.
xx to
B. CIRCUIT COMPLEXITY
Problem. In this paper we consider the following notion of problems: given sequence of input tokens, output a token the answer. Mathematically, given vocabulary V, we call mapping L: UkUNN y* + V a problem. If the correct answer is always 0 or 1, we call L a decision problem. In circuit complexity, such C is also called a language.
Though the standard definition of circuit complexity only deals with binary strings, given any finite vocabulary V. we can always replace each token in V by its binary representation, and the length of the input only blows up by a constant factor. Therefore we can extend existing complexity classes listed arbitrary finite vocabulary naturally.
P. The class P contains all problems solvable by deterministic Turing machine in polynomial time.
Boolean Circuit. A Boolean circuit over n variables directed acyclic graph where nodes are AND, OR, or NOT gates. The gates with in-degree 0 are the inputs, which are assigned one of the boolean variables. Given the inputs, the circuit computes the value of each non-input gate based on the value of the incoming gates and outputs a number at the output gate.
(m)) Given any function T, (IZE(T(m) denotes the class of problems that can solved by boolean circuits with ((T()) gates when the input length is n. Formally, a problem & is in SiZE(T(()) if and only if there exists a sequence of circuits {Cn} such that each circuit Cn has n inputs and output, the size of each circuit On is at most (T))), and for all strings is in L if and only (z) =
P/poly. We define the class P/poly as the set of problems that can be solved by a family of polynomial-size circuits, that is, P/poly e UkeN+ SIZE|n Since any Turing Machine with time bound Tnz) can be simulated by a circuit of size T(n) T(n) (Pippenger & Fischer, 1979), we know that P C P/poly.
AC, and TC. The class NC contains all problems that can be solved in small parallel runtime-polylogee polylogarithmic in input length- and with a polynomial number of processors. For- mally, for a positive integer k, a problem L is in NC* and only if there exists a polynomial p(n) and a family of circuits {C,) such that each circuit C, has inputs and 1 output, the fan- in of the gates is at most 2, the size each circuit C, is at most p(n). the depth of each circuit define NC = NC* The class AC is defined almost the same as NC for each E N+, except the AND and OR gates in AC allow unbounded fan-in. The class TC allows a more powerful type of gate, MAJORITY, compared to AC# MAJORITY gate can have unbounded fan-in and is defined (E x1)-1/11//2
On is O((lg n) ))) and for all strings x, is in if and only if (1) 1. Finally
as MAJORITY (II,..., (..) 1
holds that NC¹ S AC TC C NC for all natural number Therefore NC AC TC, which all stands for the problem class that can be solved in polylogarithmic time with polynomial parallel processors.
B.2 TRANSFORMER LAYERS
Throughout this paper, use d to denote the embedding size of transformer.
18

---

Published as a conference paper at ICLR 2024
Self-Attention Mechanism: Given attention parameter θATTN (Wq. WK. Wv. (o) E R x Rdxd x Id x [ddd define the Attention layer with mask for decoder-only transformer in Algorithm 3. Note allowing multi-head attention will not change the class of problems solvable by constant layer decoder-only transformers as can simulate I multi-head attention layer with any constantly many heads with multiple single-head attention layers. Thus for simplicity of presenta- tion, we do not include multi-head attention in the definition below.
Algorithm 2 Causal
ATTN
: Input: Parameter AATNN = (WQ. WK. Wv, Wo). Input embedding h = (hi...., ha) E Rnd
Output: Output embedding h' = (b1,...,hi k2) & ATTNA (hin..,,,....
I: 9: Wohg, K ê Wxh,, v, å Wyh,, vi [n]
2: 8 softmax( (g:, k1) ..... (.......,,...................... (O) ................................ .).
3: M A Wo (8))8))
Feed-Forward Network: Given the parameter of fully-connected feedforward network layer OFF (W1, b1. W2, b2) Rdxd x Id x Raxd x IRd, we define the fully-connected feedforward layer FFo :IRd + Rd as FF (h) A Wyrelu(Wi, bb) + b2-
Token Embedding:
Given the parameter of token embedding layer ÔTE Rd we define the token embedding layer by viewing ÔTE as a mapping from V to Rd that is, for all V, the token embedding is (I)(
Given the parameter of position encoding layer OPE E R.dxmmax, we define the token embedding layer by viewing OPE as a mapping from [Mmax] to IRd that is, for all n E [Mmax), the position embedding is as (n.(
Position Encoding:
Output Layer: Given the parameter of output layer OOUTPUT E Rlvddd we define the output layer OUTPUT OUTPUTOcUTPUT OOUTPUT Rd > V as OUTPUT BOUTPUr (h) a softmax(fouTTuU) for all h e Rdd
B.3
FLOATING-POIN NUMBERS
Below we give a formal definition the Shating-point number and rounding operation. Recall we Σ/= 2k-'a; a, to denote the value of binary number represented by 13 for any
use (ba)
E N
Definition B.1 (Floating-point Representation). Let e be the number of bits for exponents and 8 be the number of bits for significand. (e 2s + 1)-bit binary string a (a1, 022-.... 0c+2s+1) E {0, (0,1)e-2<+1 a floating-pon ppini binary representation of number (e,=(a) (a) 2 sign(a) (ogg(aa)2exppaeee 2exponent(a))
significand(a) with e-bit exponent and 2s-precision, where the sign is sign(a) _ 2a1 - 1, the signif- icand is significand(a) - 2- 3=*6(22-2++1) and the exponent is exponent(a) (a) - @(02++
2max(0,e-1), We further use Fe,s to denote all the floating numbers representable using e-bit ex- ponent and 2s-bit precision (significand), that is, IF,,, A {S 2 -226 +1 < S < 22 -2maxx(00)-11 E 1 -20xm0,e-me01 E, NJ. We define Ba,s A max F c,5.
We also use We.s : Fr.s + {0, 1e to denote the inverse of Φe.s. We note that when the number of exponent bits is larger than 0, there are multiple ways to represent number in Fe,s by binary string and we assign ( as the string a E {0. 1)++04++ with the smallest (exponent(a)). which is unique for all non-zero numbers. For 0 we additionally set sign(We.. =
Definition B.2 (Correct Rounding). For any E R and any closed subset of R containing 0, F, we define correct rounding ro, TF' as the closest number to x in F. We break the tie by picking the one with smaller absolute value.
In particular, we denote the rounding operation with e-bit exponent, 2s-bit precision by round - round(,, FF.,d which also denoted by [le,, for convenience. We extend the defini- tion of round and rounda,, to vector inputs by rounding coordinate-wisely,
Our notion of floating-poit number simplifies the IEEE 754 Standard for Floating Bloating-point Arith- metic (IEEF, 2008) by removing oc and -cc. When overflow happens, we always round the out-
19

---

Published as a conference paper at ICLR 2024
put to the (negative) largest representable number in E...- For unary functions like exp(-) and binary functions including addition, subtraction, multiplication, and division, we simply define their rounded version by rounding their outputs. Whenever division by 0 happens, treat it as the model outputs the wrong result.
C DETAILS ON FINITE-PRECISIE LAYERS
In this section, we give the definition of the finite- ceate-precision version of different transformer layers. Recall that given N the numbers representable using 2s- bit significand and e-bit exponent is Fe,s A 2 - 2 +1 < S < 2 1, -2max(0,e-1) I E S 2 1-22mxx00,e-) E,S S N)-
Self-Attentinn Mechanism: Given attention parameter 0ATTN (Wq. WK, Wv, Wo) E R x Fdxd Fdxd Fexd we define the self-attention layer with causal mask for decoder-only trans- former in Algorithm 3.
Algorithm 3 Finite-Precision Causal Self-Attentin,, ATTN
Input: Integer N+ e E N, Parameter BATTN (WQ. WK. Wv, Wo), Input embedding h (hi...., Frd.
Output: Output embedding h' = (h/,..., h%,) - AT ATTN (hz,..., hn)- 1: d: WQ Xe,s 1,, Kis WK Xx,s hi, vs Wv Xx,s hi, Vi [m)
2: 8; softmaxe, (igt, ki)e,e.......................k. ..... (gt, kl) (O.....,
i's 0: Mask for Causal
Attention;
3: M4 2 Wo Xe,e sume, ((V1,.... Un] Xe,s 8:).
Feed-Forward Network: Given E No, N, and the parameter of fully- conleceddde feedforward network layer OFF = (W1, b,, W2, b2) E Rdxd x Fdd x Wddxd x FF. we define the fully-connected
feedforward layer FFo, e,e
IR FFo (h)
W2 xe,s relu([W1 Xe,s h bile.s) + l2 a.s
Token Embedding: Given s E N+, e E N, and the parameter of token embedding layer ÔTE Edx[V] we define the token embedding layer by viewing ÔTE as mapping from V to Rd, that is, for all V. the token embedding is θTE(#))
Position Encoding: Given E N+ E N. and the parameter of position encoding layer θPE Fdxamaxx we define the token embedding layer by viewing fPE as a mapping from [Amax]] to Id that is, for all [Tmaax], the position embedding is as (pe(n).
Output Layer: Given E N+, E N. and the parameter of output layer POUTPUT E xlvlxd (POUTPuT Xe,e h) for all Idd
define the output layer OUTPUT BOUTPUT Fdd
V OUTPUT P (h) A
Finally, we define finite-precision decoder-only transformers below.
D PRELIMINARY OF AUTOMATA AND KROHN-RHODES DECOMPOSITION THEOREM
In this section we recap the basic notations and definitions for automata theory and Krohn-Rhodes Decomposition Theorem (Krohn & Rhodes, 1965), following the notation and presentation of Maler (2010).
Definition D.1 (Automaton). deterministic automaton triple = (E, Q, where a finite set of symbols called the input alphabet. Q is finite set of states and 8 + x Q is the transition function.
The transition function can be lifted naturally to input sequences, by letting 8(g. wo) A 5(0(g, w), a) for all w E E" recursively.
20

---

Published as a conference paper at ICLR 2024
Algorithm 4 Finite-precision Decoder-only Transformer, TFa and ps
Input: Integer E N E N. Transformer parameter 0 = (OpE, OOUTPUT 10 ATTN FF FF) 1 with 2s-bit precision and e-bit exponent. Input tokens x: = (Z1...., Fn,) E V"
Output: Output distribution Pu(- :.)) for all i [ni] and output token TF (z)
1: 1/4 A (T) + (E(()) c,a Vi E [n]
2: for = 0, 0..... L do
(b1 (b((+0.55)
...., (140055)
[11 ,...,,, h19) + ATTN (h2,... ....,, 119
3:
ATTN
e,a
4: h3
(1+1) A
(1+0.5)
+ FF
to (
((
Vi E [n]
5: end for
6: po(- | [11...,, rz)
[OUTPUT BOUTPUT (h
vi E [n]
7: (x) A arg max, (2 x1 Fn)
An automaton can be made an acceptor by choosing an initial state go E Q and set of accepting states F C Q. As such it accepts/recognizes a set of sequences, also known as a language, defined as C(A. qo. F) = fw Σ' : 8(0, w) E F}. Kleene's Theorem states that the class of languages recognizable by finite automata coincides with the regular languages.
Definition D.2 (Automaton Homomorphism), A surjection Φ : Q + Qo is an automaton homo- morphism from A = (2,, Q, 5) to Ao = (2,, Qu. do) if for every q E Q E >, (00(g, σ)) 5u(0(g), g). In such a case we say that Ao is homomorphic to and denote by Ao So A. When é is a bijection, A and Ao are said to be isomorphic.
The conceptual significance of Automaton Homomorphism is that, if we can simulate any A and Ao So A. we can 'almost' simulate Ao as well, in the sense of following lemma:
Lemma D.I. For any two automata A (E, Ao = Qo, 6o) satisfying that Ao So A for some function o, for any Fo [ Q. go E Q o(q) = go. it holds that [(Ao, go. Fo) = C(A. 1.A..g.0-10 (Fo)..
Proof of Lemma D.I. We claim for any w E E", it holds that o(8(g, w)) = 5(((g). w). This claim holds by definition of automaton homomorphism for all |w| S 1. suppose the claim already holds for all w no longer than n for some n, for any w' = wo with |w| = n and E E, it holds that
0(8(g, w') w²)) = @(8(((q, w) o)) = 8(0(ō(g, w)), = o(ō(q,w)) E Po = d(q,w) o (FF(.. Thus we conclude that C(Au, 9o. Fu) = {w E' 8(90. w) E Fo} = {w E E" 8(g. w) E (Fa)) L(A. q, o (Fo)).
w))) = 8(0(g). w'). Therefore
do(go, w) E Fo > do(o(g) w) E Fo
Definition D.3 (Semigroups, Monoids and Groups). A Semigroup is a pair (S.-) where S is a set
and is binary associative operation ("multiplication") from S x S to S. A Monoid (S, 1) is semigroup admitting an identity element 1 such that 8 1 = 1 ... = 8 for every E S. A group is monoid such that for every & E S there exists an element s -1 E S (an inverse) such that s. s-
Definition D.4 (Semigroup Homomorphisms). A surjective function @ S + So is a semigroup homomorphism from (S, ) to (So, *) if for every 81, 82 E S, 51 82) = ((s) * ((x2). In such a case we say that So is homomorphic to S and denote it by So So S. Two mumully homomorphic semigroups are said to be isomorphic.
Definition D.5 (Transformation Semigroup). The transformation semigroup of an automata A = (E., Q 5) is the semigroup generated by (ō(;,a): : Q - Q E).
D.1 THE KROHN-RHODES DECOMPOSITION THEOREM
Below we give the definition of the cascade product of two automata, which is a central concept used Rhodes Decomposition Theorem for automata.
Definition D.6 (Cascade Product). Let B1 = (E, Q1 &1) and B2 = (Q1 x Σ, 82) be two automata. The cascade product B, B2 is the automaton C = (E,Q1 x Q2, 5) where
5((1); A (f1(11, .), 52(92, (1), o)))
21

---

Published as a conference paper at ICLR 2024
The cascade product of more than two automata is defined B1 B2 0...0 (... B2) B3 ......) k-
Automata). A automaton A = (2,, Q. is a permutation-reset automaton if for every letter E Σ, is either permutation or reset. the only permutations are identities, we call it a reset automaton.
Definition D.7 (Permutation-Rese
Theorem D.2 (Krohn-Rhodes; cf. Maler (2010)). For every automaton A there exists cascade By such that:
Bi o B2 o
1. Each B, is a permutation-rese automaton;
2. There is a homomorphism ø from to A;
3. Any permutation group in some B; homomorphic to a subgroup of the transformation semigroup of A.
The pair (C, is called a cascaded decomposition of A.
D.2 COUNTER-FREE AUTOMATA
Next we introduce a key concept used in the proof of Theorem E. (and thus Theorem 3.1) -Cuutte- free Automaton.
Definition D.8 (Counter-free Automaton, (McNaughton & Papert, 1971)). An automaton is counter- free if no word Σ" induces permutation other than identity any subset of Q.
subelass of the regular languages is the class of star-free sets defined as:
Definition D.9 (Star-Free regular languages). The class of star-free regular languages over the smallest class containing E' and the sets of the form {a} where E a U {t), which is closed under finitely many applications of concatenation and Boolean operations including union, intersection, and complementation.
is well-known that languages recognized by counter-free automata have the following equivalent characterizations.
Theorem D.3 (McNaughton & Papert (1971)). Suppose L is regular language not containing the empty string. Then the following are equivalent:
1. L is star-free;
2. L is accepted by a counter-free automata.
3. L is non-counting, i.e., there is an n E N so that for all x, y. and and all m 2 n, ry""
my E L.
Counter-free property of an automaton can also be characterized via its transformation semigroup by Lemma D.4, whose proof is straightforward and skipped.
Lemma D.4. An automaton is counter-free if and only if the transformation semigroup of the au- tomaton is group-free, i.e., it has no non-trivial subgroups. A semigroup (S, is group-free if and only if it is aperiodic, i.e., for all S, there exists & N, s g
Thus Theorem D.5 holds corollary of Theorem D.2.
Theorem D.5 (Corollary of Theorem D.2). For every counter-free automaton there exists cas- cade C B1 B2 ...o B3 such that each B, is reset automaton and there is homomorphism from A.
Using Theorem D.5 the following theorem connects the counter-free automata to constant-depth poly-size circuits with unbounded fan-in. The high-level proof idea that any reset automaton can be simulated using constantly many depth and any counter-free automaton can be decomposed into the cascade product of a finite number of reset automaton.
Theorem D.6. [Theorem 2.6, Chandra et al. (1983)] Suppose AA (E, @) is an counter-free automaton. Then there is circuit of size ( with unbounded fan-in and constant depth that simulates 5(g. w) for any q E Q and w E D" satisfying |w] = n, where O(-) hides constants depending the automaton.
22

---

Published as a conference paper at ICLR 2024
E PROOFS FOR EXPRESSIVENESS UPPER BOUNDS (SECTION 3.3)
The main technical theorems we will prove in this section are Theorems E.1 and E.2. Their proofs be found in Appendices E.1 and E.2 respectively.
Recall Ve.s Fe.. > {0, 1] is the binary representation of floating point with e-bit exponent and 2s-bit precision.
Theorem E.1. For any fixed E N, E N+. sum (Fe,s)" - Ie', has AC circuits.
In detail, there is family of AC circuits {C,} such that for all 21. In Fe,er it holds that Cn(Pee, (21) )ll (zr))
zn))
Theorem E.2. For s(n) = ((poly (n)), sumo,a(x) : (F)))()))* + IF (o))(n) has TC circuits.
In detail, there is family of TC circuits {C,) such that for all 2 ,I....,dy E (o,(())) it holds that (V (x1) ... (l) (Ix,) ()),((n) (sum (#1,
With Theorems E. and E.2 ready, Theorems 3.1 and 3.2 standard (e.g., see proof of Theorem in Liu et al. (2022a)) and thus are omitted.
E. PROOFS FOR THEOREM E.
Definition E.1 (Total Order). total order < on some set X is binary relationship satisfying that for all a, b,c E X:
1. a < a (reflexive)
2. a < bbbsc = a S (transitive)
3. a a.asbbbb = a b (antisymmetric)
4. a b a. (total)
Definition F.2 (Ordered Automaton). We say an automaton A = (E,, 0) is ordered if and only if there exists a total order S on Q and for all a E Σ, 8(.,)) preserves the order, that is,
4q. E Q,
q z d' = 8(g. 2 o).
Theorem E.3. All ordered automata are counter-free. Languages recognizable by any ordered automata belong to AC
Proof of Theorem E.3. To show ordered automaton = (E, 8) is counter-free. it suffices to its transformation semigroup is group-free, or aperiodic. We first recall the definition of aperiodic semigroups Lemma D.4. Let Tw Q - Q, (w) 5(q. w) be the transformation induced by word E Σ.. Transformation semigroup of A is aperiodic iff for any Σ", there exists & N, such that (T,)) ) )+T,)
Now We claim for any 9 E Q there is k N, such that ( (mw) Since Q is finite, this implies that there exists & E N, such that (Tw))* = (I 3+1 and thus the transformation semigroup of A is aperiodic. First, note that A is ordered,
know To is order-preserving for all E Σ. Let w Wi ... W., where |wl = n, we have Tw Tw,, ... Tw., is also order-preserving and thus for all
E Q, The (4) (.) Then we proceed by three cases for each g Q:
1. noe (4) = In this case, suffices to take k: = 0:
2. Tuo TT) > Since The is order-preserving, we know for any k E N, (TTr) 2
(Tw)) (g). Since Q is finite, there must exist some & E N such that ( (Trw)
3. ne (q) < q. Same as the case of T. (g) 2 q.
Since > is total order, at least one of the three cases happens. This concludes the proof.
The second claim follows directly from Theorem D.3.
23

---

Published as a conference paper at ICLR 2024
For any s E N. iterated addition floating point numbers with e-bit exponent and s-bit signifi- cand Fe,a can be viewed Ae,s = Fe,,
Theorem E.4. Automaton Ac.s (FF Fe,s, 8+) is ordered, where 6+ y) - [ac + yle, for any 2 F e.
Proof of Theorem E.4. The total order we use for Fe.. as the state space of automaton A co- incides with the usual order I on E. Recall the rounding operation is defined as [x]e, arg een (o (n-alp which means rounding operation is order preserving, that is, for any x x' E Re,ss [p]e 2 [a')e,s- Thus for any x, ", y Fe,, with x S x', holds that & (2,, v) [x + vle.s 2 [x' + vle,a = ( y). Thus A is ordered.
The following theorem Theorem E, a direct consequence of Theorem E.4.
E.2 PROOFS FOR THEOREM E.2
We first claim that the following algorithm Algorithm 5 correctly computes sumo,s(n) over n num- bers in (o.)(n). Lemma E.S. Algorithm 5 outputs sumo,s(m) (21, (21, ,.,,,,,,,,,)) Fnn) for all n E N+ and 21.... In Fo,s(n)
sign(x1) - Bu(n) and [sign(æ1) BB(r)) (m)) + yi si)o,s(m) Ii, thus we conclude sumo,a(w) (=1, Fnn) sumo.s(m) (y ( 1-11 1. 1/, 91, ......... Un Without loss of generality, we can assume that 4i > 0. Therefore S_2 = 0,5 = Ba)- and
Proof of Lemma E.5. Note that y-2 0, +y
So 2B)))) which further implies that L_2 < 0 and U_2 2Bx(n)- This ensures 8 always well-defined. For convenience we use H; denote (u)) (V-2 1- Yo, U,,..., . Ui-1) in the rest of this proof.
Now claim either S.- Li- or S,- Up.. By definition of i*, if neither of these two equalities
happen, we have that i" < - 1, U.- = +1, and Li- = Li+ which contradicts with the maximality of i" since U+++1 Li++1
U-- Li- 2 2B) Without loss of generality, we assume S,- = Li- and the analysis for the other case is almost the same. Now we claim that for all i i*, no negative overflow happens at position i, that is, H, + y 2 -B((n)-
We will prove this claim for two cases respectively depending on whether there exists some i < j < i such that sum), (y-2, 1- 1. you ...... ......... Uj)
Ba(n)- The first case is such j does not exist. Then neither positive or negative overflow happens through i" to i, and thus
H + y: = HG. + (S. - S..) ) 2 H 2 - BB(n)-
44)
If such j exists, we let j* to be the maximum of such j. Then neither positive or negative overflow happens through jr to i. Due to the optimality of i", we know that for all i,j 2 i*, |S, - -S,l < 2B.(m) <. Thus
Hi-1 + 4/1 H5- + (S: Sy.) 2 BB(x) - 2BB(.)) 2 - -B(())-
(5)
Now we claim Hy- BB(N)- Because there is no negative overflow between i* and k", we have
that Ha- HHs > Sg- S.- > (B)()) and the fist inequality is only strict when positive overflow
happens at some i' < k* If there is no such j. then Ba(r) 2 Hy- 2 H₃- + 2B.(n) Z Ba(r) and thus Hç. Ba(n)- Otherwise such exists and j" be the maximum of such j. Then Hç. 2
Hy- (S - S,-) 2 Ba(n) (S -S-..-SS-)) S,-) > Ba(n). where the last inequality is due to the optimality of ktt Thus both cases we conclude that H Ba(n)-
Finally we will show there is neither negative or positive overflow from k* 1 to n and thus H, = Hy + S, Sy,, which would justify the correctness of the algorithm. We have already shown there is no negative overflow. Suppose there is a positive overflow at some j > k= in the sense that Hy-1 + yj 2 Ba(n) and we let j* be the first positive overflow after k=" By definition of jr, there is neither positive and negative overflow between k' + 1 and j" and thus Hy--1 + Vi- Hy- + (Sy- SS-)) ) < H3- = Ba(n), which is contradictory to the assumption that there is a positive overflow at j". This concludes the proof.
24

---

Published as a conference paper at ICLR 2024
Algorithm AC algorithm for iterative addition for poly-precision floating point numbers
Input: Integer N+, s(n) = (n))) Floating numbers .1,..., E Fa,s(m)-
Output: ans = sumo,=(n) . ) E Fo.((n)-
I: y-2 - 0, 1, 90 - sz)) Be(n)- + x1 - -iin((1) Be(n). yi + Is, Vi E (2....,n]]
2: S Σj=o وio vi (-
3: U, t maxisjen Sy. 14 t min Sj. ViE (-2,....,,
4: i" < max v i n U Ln 2B (n));
5: if S. Up then
6:
k* t ii < < Ss = Li J:
7:
0 - Ba(n))
8: else
9:
k* -- max(i
k < n St = U:
10:
0 Ba(n):
11: end if
ans f 0 Sn S Sk
Proof of Theorem 3.2. It suffices to show that Algorithm can be implemented by family of AC circuits since Lemma E.5 guarantees the correctness of Algorithm 5. We can treat all the fixed-point floating numbers in the Algorithm 5 as integers with suitable rescaling, which is 2*(m), Since both sorting and adding binary integers with polynomial bits have AC circuits, each line in Algorithm can be implemented by an AC circuits (for all indexes simultaneously if there is any).
F PROOFS FOR EXPRESSIVENESS LOWER BOUNDS (SECTION 3.4)
We first introduce some notations. Since in the construction of the lower bounds we are only using fixed-point numbers, we will use the shorthand F, A Fo.. = {c k 2 c [-1,1],0 < k < 22 - 1, E N} and rounding operation [.], Hoo..- We use 1, to denote all-one vectors of length 8. Similarly we define +), x: and softmax,. We recall that for any N+ and integer
0 < 2" 1, use bin,(r) {0, 1 to denote the usual binary encoding of integer using binary bits in the sense that æ
E.= 2 (bbin, (x)), and sbin,(x) {-1, to denote the signed (I.
binary encoding, which is 2bin,
Recall B, max F. = 2 -
Lemma F.1. For any E N+, it holds that [exp(- - -B.).. 0.
Proof of Lemma F.I. By the definition of rounding operation for 2s-bit precision (Definition B.2), it suffices to show that exp( B3) < 2- that is, B, 2 2n (s
+ 1). Note that 2 2 8 8 for all 2- 22 > 3/ 2 In 2.
s 2 we have Ba/(6 (s + 1) 2 B.2 2
Using the same argument above, we also have Lemma F.2. Lemma F2. For any N+, it holds that [exp(B.)]. B..
F.1 PROOF OF THEOREM 3.3
Given two vectors y of the same length 8, we use xy y to denote their interleaving, that is, (0T))i-11 = Zi, (r- y)2; = yi for E [e].
Lemma F.3. For any s E N let qi = (b) and i = B, (1) for all
i E (2 1]. holds that [exp( (q., kg) = 1li = jl for i,j E [2 - 1].
Proof of Lemma F.3. suffices to prove that (q: ky), = B, if + j and (g., k2), = - = j. The rest is done by Lemma F.1.
25

---

Published as a conference paper at ICLR 2024
Given any i.j E [2 11. by definition of finite mnite-precision inner product, know that for any E [2s 11, it holds that a [AL-1 + (())) where op _ 0 and ar - ((%)), (ky)a), for E [2s]]
For all E [e]. we have that (())))()))l, = -B, Ba and ((q 12 = B, - [(sbin,, (1)) = (s)in,(j))1)- If j. it is straightforward that az-1
B. and 022 0 for all 1 [e]. If i * j. then there exists E [s - 1| such that (sbin(i))) & (sbin(j))) Thus [(g, 21-)))2113))) (k))2t111, = (2))):(k;)))
-B,, which implies az -Bs regardless of the value of 0212- Again use
induction we can conclude that dgr BB for all 1 S. <
Proof of Theorem 3.3. For any L E (n)), by definition there a family of boolean circuit {Cr} which compute L for all inputs of length n using O(T(n)) many NOT and AND gates. Without loss of generality, let us assume the number of non-input gates in C₂ be T(n). We will show that for each there is a 2-layer decoder-only transformer TF that computes C₁ (2) using
T(n) steps of CoT for all x E (0, 13". More precisely, we will construct a transformer that simulates one boolean gate in C.,, following the topological order of the circuit, in each step of its chain of thought.
We first index the gates (including input gates) from 1 to n T(n) according the topological order. For each gate E [n + 1,n + T(n]], we use a(i) and b(i) to denote its two input gates. Since NOT only has one input, we set a(1) as its input and b(i) as O. We let c(i)
0 if ith gate is NOT and e(i) = 1 if ith gate is AND. For any input gate 1 S i S. n, a(i), b(i), and the gate type are not meaningful and their choice will not affect the output and thus can be set arbitrarily. For convenience, we will set a(i)
b(i) c(i) O. We use (z(z) to denote the output of
non-input gate (n + 1 S i S n + T(m) on the circuit input E {0, 10,,)", which equal to (1 (1-c())) - =a(a) + c(i) (relu((r)))))
=M(e) 1)):
Now we describe the construction of the vocabulary V. the token embedding ÔTE, and position encoding 0pg. We set precision s as any positive integer larger than 1, {0. 1). - k((n) =
[loga (T) + n)] Ologn) since (nn) is a polynomial, d'(n) = 3k + 6, (TE( = 0 0-
(TE(1) el, and
(OpE)T 00,0,0000 0, (i). (b)n, sbin sbing
(b()siinnn)nn.)l) (6(1). 1], V2 Si S n T(n).
(6)
We use h.. h0.5 h1. h and h² to denote the intermediate embeddings at position i and different depths. Here, depth 0.3 and 1.5 refer to the output of the Attention layer inside each transformer layer.
1. For the first attention layer, denoting embedding at the ith position hy by h, we set the query as qi - (h646:2445) (hax-6 : 1g), the key as K - (Bahax+s) -haa446 1,), and the value as
0/ - "e2"
2. For the first fully-comnected layer, we skip it by setting its weights to be 0.
3. For the second attention layer, denoting embedding at the ith position h! by h, we set the query as qi (h2x+6:34+5) (hat+e 1,), the key as k; A (B.haa-s) (-h33++6 1,), and the value
as U/ A h1
.e3. he..
4. For the second fully conneceo layer, define F(a,b, b, c) e relu(1
relu(a+b+c- 2).
Denote the embedding at position i, Mi. by h. The output of the second fully-connected layer is defined as F F(h2, ht, ha) 64. Note this expression is valid because it can be expressed by two-layer ReLU nets with constant bits of precision and a constant number of neurons.
5. The final output at position i is (h²)
Below we first describe the value of the internal variables of the transformer and then show there exist parameters making such computation realizable. Let (T) be the input tokens, we
'Note here the dimension of k; and gi are the same but less than d', which does not strictly satisfy our definition of transformer in Algorithm 3. This is for notational convenience and is without loss of generality hecause we can pad extra zeros.
26

---

Published as a conference paper at ICLR 2024
define En+i A TF (I1 , kn), v1 1 T(n). We claim there exists transformers parameter
On such that TF2, (m) constructions will ensure the following inductively for all n + 1 i n T(n).
8n (#1.....,T,, Fn) (x) (i.e. (x)). More specifically, we claim that our
1. 46-1 [r 0, 0, c (sbin (i)) (sbin,, ((ssiin((()))))
(sbin :]":
2. 404 [.t-1
(sbin (sbin: (a (sbin, (b(0))T.1]
3. ML1 [ [--11, Ro (sbi))
sbin , (a (a()))) (sbin) (bb) (b(1)) ,1]":
4. 120 ||43a//e0eeaaooa//////o//0///0/0
5.
(1)) T (1)
(sbin, (sbin (sbin) (b(1))) 1]";
6. 32 A TFe, (I), (.1,,... -n. (x)
Now we explain why the above conditions hold for any position i using induction, í.e., assuming true for all n 1 E 1f < í. We first notice that by our construction, for all 1 < 1' S - 1, it holds that (h$) 1 = Ty and (hy 0o:k+5 for all & E {0, (0,0.5, 1, 1.5, Note these are the only information that will be used in the later attention layers.
1. This is simply by the construction of ÔTE and fpE.
2. In the first attention layer, the jth position, we have qj - sbinn(a(j)) 1, as the query,
ky B, (t) as the key and v, - Iy as the value for all j E [n + T(n]]- Note here reduce the sizes of hidden embeddings for simplicity of demonstration. This is valid because we can fill the extra coordinates by O. This is valid because we can al- ways set the extra coordinates to be O. By Lemma F.3, we know that [exp((n,,)) k)))))] for all
1 (a(i) s; _ softmax( (q, k1), ..... (q:, k2) ()l,,, 0), we know that s; Ca(i).
[m + T(n)J. Recall that the attention scores are defined as .....
3. We set the parameters in the first fully connecc feedforward layer to be all 0 and let the skip connection pass the intermediate values.
4. The second attention layer attains Tb(a)) and places in the third coordinate in the same way as step 2.
5. In the fully-connected feedforward layer we compute F( (b()) c(i)) relu(1 Ta(i) - c(i)) relu(Ia(() zb(1) + c(i) 2) for all za(i), Para). c(i) E 1). We can verify that (1)(()) To(e), e(t) (1 c(i)) =a(o) + (relu(z())) + Tb(3) - 1)) (xx),, which is the desirrd output of the gate i. This is because when c(i) = 0, the output is
1 1-a(i)= = NOTa(i) and when c(i) = output is relu(a(i)+b(() 1)) a(i)ANDb(
6. The output layer uses the fourth coordinate of 43, which is gx(x) according to induction, as the output.
This completes the proof of Theorem 3.3.
F.2 PROOF OF THEOREMS 3.7 AND 3.8
In this subsection, prove Theorems 3.7 and 3.8. We first prove a useful lemma that gives an equivalent characterization of AIZ and TC".
Lemma F.4. For any T(n) E poly(n) satisfying T(n) 2 1, Vn E N+ decision problem L UseNt (0. 13 {0, belongs to (T (resp. TC (T(n)) if and only if there exist a polynomial S(n), a function (') = ((T(n)), and a depth L E N+ such that for every n E N+ T')).. there exist sequence of Sizes-S(n), depth-L. eircuits, (CA) 1=1 with unlimited-fanin AND, OR
27

---

Published as a conference paper at ICLR 2024
and NOT gates (with additionally MAJORITY gates for SIZE and that for all E {0.1)"
(x))= = (n))
where
Un+i - C (T), (n1t..,, e (T))]
Proof of Lemma F.4. We will prove for SIZE only and the proof for SIZE is almost the same.
The direction is straightforward. By definition of SIZE TC" [T())] (Definition 3.5), for any C E SIZE TC" [T])], there a function p(n) E poly(n) and family of TC circuits {C]);s such that for every E IN and x E 10, Lu (x1,..... ................................ Inn) can be computed by size-O(T threshold circuits with oracle gate Cpin)- Now we sort all the nodes in the circuits with oracle gates along the topological order as 21,..., (n) where 21...., In are the inputs and T ['m)) = O(T(n) the
number of the gates, then clearly Un+i function of Zi..... In+i-1 for all E [T)( and this function can be implemented by different threshold circuit of constant depth and poly(n) size for each i. This completes the proof - direction.
Now we prove the other direction "s". We first show that given (") sizes-S(n). depth-I. cir-
cuits, (C% (") there is depth- + 1), size ((T(()))(m) circuit C,, such that
C₁ (Z 1.01,..110 "
= (n+j-)) v E [T"()),, (0,1)a47(0-), (8)
where 1, E (0, (0,1) is the one-hot vector with its jth coordinate being 1. Indeed, it suffices to set
91...... (r)()) v (m) (y) (a
Once we have such oracle gate C given input 21 we can recursively define
Enti C² (T1, F (n:
(10)
Thus can compute L(x) (n) using (n) oracle gate C₁ We get constant gate and by using œ1 A 11 and 21 V 11. respectively. This completes the proof.
Now are ready to prove Theorems 3.7 and 3.8. We will prove Theorem 3.7 first and the proof of Theorem 3.8 is very similar to Theorem 3.7.
Proof of Theorem 3.7. We first show that SIZE (T(m) + 1] CoT(T(m), poly(n), (oll())) log n). For
the case that the vocabulary of transformer V f0. 1). by Theorem 3.2, we know for any On. TFe,, (Zi,...,,2) 22) can be expressed by TC circuit whose depth is uniformly upper bounded by some constant for all n S i S n + ((T(n)). This completes the proof when V = {0, 13. When V + {0, 1}. we can use the binary encoding of elements in V as the inputs those TC gates constructed for the later layers of the transformer.
Now we turn to the proof for the other direction: SIZE [T(n) + +1] 1] CoT(T(n), poly(())))))())) log In level speaking, the proof contains two steps:
1. We show that TC C (poly((n), log n] C CoT[1. poly log The first step has two key constructions: (a). using attention to copy all the weights to the same position: (b). we can use polysize two-layer FC net with ReLU activation to simulate MAJORITY, AND, OR gate with unbounded fan-in (Lemma F.5);
2. We can do the first step for all positions = n + 1,..., O + simultaneously.
By Lemma F.4, we know that for any problem L SIZE TC polynomial S(m), and T'(n) = ( + 1), such that for every n E N+ there exist a sequence of threshold circuits, {C bounded by L. and that for all x E 13"
[T(n) + 1]. there exist constant L.
(m) whose sizes are uniformly bounded by S(n) and depth are uniformly
L(x) In)
where Enti P Inti-l), Vi (n)).
(1I)
28

---

Published as a conference paper at ICLR 2024
To simplify the notation of the proof, without loss of generality, assume for each i [T)], circuit C has the exactly same size S(n) and depth L.
Now present the construction of the constant-depth, constant-precision decoder-only transformer, TFo, which computes problem L when input length is n. Without loss of generality we only consider the case where (n) T(n) 1. We set vocabulary V {0. 1}, embedding width d(n) = 1 + 3(T(n) + n) + (5(n)T(n) = ((poly(n)). depth equal to L + 2, CoT length T(n) and precision s(n) [log2 S(n)] the precision is high enough for simulating all the poly(n) size MAJORITY gates used in C. (Lemmaa F.5). We set (OTE)O 0 eI, (OTE) = 1 e1, and (ÉPE); = e++1 for all i E [n + [n)]. where we use E {0, 1] d(xx) to denote the one-hot vector whose ith coordinate is for E [d(n)] and E; E {0, 10,1)))+(())) to denote one-hot vector whose ith coordinate is for E [n Tn))].
Below we first describe the value the internal variables of the transformer and then show there exist parameters making such computation realizable. To make our claims more interpretable, we only write the non-zero part of the embedding and omit the remaining O's. the Let (#1,..., Zn) be the input tokens and A & 3n + (n) 1, our constructions will ensure that
1. Unti = TF2, 8y (II,,...,tn)) , In), E [T(n)]-
2. Ny -2,61 + Cit1 =r; 83) Vi [n m++77 T(m)]:
3. 4.S = 2,61 + ei41 = (Ii, E,,, Vi E [n T(m)]:
4. 4 z,e1 eit1 + 2iCn+T(a)+it
[,, vi [n + T(n));
5. 41.5 = (Ii, Ei T2 T1, 2.), Vi E I
6. (h (h ) ((
E 10,1) S(n) stores the intermediate result of circuit C₁ (x1, I 1n) at layer I, vi E (m)) and I E [L];
7. (h ) (
is the intermediate result of circuit (T1....... In+i-1) layer 1 Vi E [T())]. but represented using = (1=tt-)4+o--sstm 111, That is, Mean-
while, (h (N
(I =0, Vi E [T(n)). #i
8. (POUTPUTh L+2 1 (CI, (n-i++))) for all i E [m)].
0, ((OUTPUTh
(h2+2 (h (hatt-1) Σje
Now we explain the purpose of each layer and how to set the parameters such that the requirements above are met.
1. Inti = TF. 0. (Z Vi [T(n)] is the goal of the construction;
2. This is by our construction of OpE and ÔTE:
3. The first attention layer does nothing by setting all weights to 0;
4. By Lemma F.5, AND can be simulated by 2-layer ReLU networks using 2 hidden neu- rons. Thus use the first feedforward-layer to compute the function (1:) ++) (hQ-5)14 (b(-²) for all i, E In + [[)) with totally 2(n T()) hidden neurons. Therefore if # i, then (hQ-5) 11+j = 0, which implies (1))=4(())++43 0; if = i, then (hQ-)) 1++ 1, thus (h) (1))4(()++1 (10.5
Zz-
5. This step exactly requires (ATTN g (1
(o)) = Ej Eatj It suffices to set the attention score the second layer at ith position 8; = (l.... 1,. 1,0. 1,.....0) 0) =
(1,, (n)T())))) for all [n + T(n) 1]. This be done by setting 9.5
Wohk. (Ba())) (n4T())-1);ttt h45 Wx (1, (.)))-)))-1). By Lemma F.2,
29

---

Published as a conference paper at ICLR 2024
have [exp([(4,, ky) )sst)) (asp(Bann))latt Bu(n)- Since rounded sum of any number of Ba(n) is still Ba(r) and (n) Ba(m))e(s) = 1, we know that
8; = softmax, (Bx(m) (.) ................................ 0) (1, . 1,0. ... 0) (1,, (n)T(()-)))
for all i E In + T(m) 1]. Note in this step we use our specific rounding rule to copy all the previous 24 with sum of attention score larger than 1. We can just also use ap- proximately uniform attention scores with an additional coefficient before x; since we have log n precision. Finally we set o/- - hy Ea+1T; and Wo Id(n).
6. The second attention layer is the only attention layer which has non-zert weights. Using the feedforward ReLU networks from layer 2 to L + 1, in parallel for all E [T(m] by Lemma F.5. In detail, Lemma F.5 ensures that we can use a two-layer fully-connected ReLU network with weights to simulate a layer of the TC circuits C Moreover, there is enough space in the embedding to reserve S(n)'s needed by Lemma F.5. And we always append the value of intermediate gates after the gate values which have already been computed each layer using the indices A + (i - ())(() + A + S(n) for h" - for each E [T))]. Note for each i, only the computation in the range A + (i 1))(m) +1: A ((n) is meaningful and the computation for other indices
simulate the circuits O,
will not be used later.
7. This is similar to step 3. (hat2 (h=-i1))+te ())+())))(()+++
We skip the attention layer and simply set (h (mnti-1n-- ( A (h (4 for all & [S(x)] using the feedforward fully-connected network.
8. This step holds directly due to the property guaranteed in step 8. We note that with the property claimed in step 9, we have that ( 24--11
L+2 1) (BoUTPUTh 242 1)o
then (0oUTpUrha4s--l) (fouTPUTh,** p- 1) = 1, which implies ( In+s-1) = 1, otherwise C₁ (1
( 6+2
1. Thus if (aI,,..-... -.,
L+2
".01,...,T...--...... = 0. In both cases, we have that Fo00....,,ntttt In-1 = 0, then TF (f1,..., Inti-1)
(2 ( -n TFo, (21 (21,..., (ntii-l)
(12)
So far we have finished the proof for the general (n). Specifically, when T(n) = T(n)= proof shows that the constant-depth transformer can still simulate any constant-depth circuit, which means TCº S [[)) S CoT poly(n)) SIZETC (1) TC Thus all the inclusions equivalence, that is TC = [n)] = [o poly(n) = TI (1).
(n) 0, our
Proof of Theorem 3.8. We first show that AIZ (T(n) + 1] 2 Co poly(n), 1]. For the case that the vocabulary of transformer V = {0, 1}. by Theorem 3.1, we know for any On TFo, (#1,..., .T) can be expressed by TC circuit whose depth is uniformly upper bounded by some constant for all n S S + ((T(n)). This completes the proof when = {0. 13. When # {0, 1}. we can use the binary encoding of elements in V the inputs of those TC gates constructed for the later layers of the transformer.
The other direction almost the same as that of Theorem 3.7, except that we now only need constant bits of precision because we do not need to simulate MAJORITY gates (Lemma F.5).
F.3 PROOF OF THEOREM 3.9
Proof of Theorem 3.9. By Lemma F7, holds that for all l E N. AC ç SIZE[n*). By The- orem 3.7, we know that AC C CoT poly(n), S CoT[n*, poly(n), 1] for any k E N. p)ly(n), ( ç SIZE[n*] for all k k' E N. Also, note that the attention layer
Thus CoT and fully-connected layer can be computed using poly-size circuits. Thus for any E N, CoT log(n)] C SIZE[n*)] for some integer > k. Combining these we conclude that for [.,g(]] any l N. CoT log(n)) Ç CoT pol((n)).
30

---

Published as a conference paper at ICLR 2024
F.4 AUXILIARY LEMMAS
In this subsection, we prove a few auxiliary lemmas that are used in the proofs in Section 3.4. Lemma F.5. Unlimited-fanin AND, OR (resp. MAJORITY) {0, 1 + {0, 1} can be simulated by some 2-layer feedforward ReLU network with constant (resp. log bits of precision constant hidden dimension and additional constant inputs of value 1.
Mathematically, let FF[s(n)] be the set of functions C {0, + {0, 1 which can be two- layer feedforward ReLU network with most s(n) bits of precision and constant hidden dimension FFo {0, 1) 1)2n - {0. 1), FF)()') = W2 x, relu([1 x, x' + bil,), where 0 = (W2, W1,b) such that for any x E {0, 1)",
FF 1, T2, I,..., Ix, 1) = -(x). We have unlimited-fanin AND, OR E FF[I] and MAJORITY E FF]
(13)
The proof of Lemma F.5 is based the following straightforward lemma (Lemma F.6).
Lemma F6. For any E N+ and E F... relu((a),) - relu((a 1l,) = 1[a >> 0J. In particular, for any a E Σ, relu(a) relu 1) 1aa 0j.
Proof of Lemma F.5. Recall that x"y denotes (x1, 21, ,2, ./.............................. Ln. yn) for any 2, y 10,1)%.
We have that (a (-1,,) I 0 for all e 2 and E {0, 13". Moreover, sum, (x (- -nn) =
O vi E in], = 1. Similarly, we have that (z) 0 and su) = [n]. 2, = 0. other words, we have
Vi
(zD(x)= [sum, (x (-1,)] 0) 1Kx Lm, (-1m)) + >><00 0j:
OR(z) = 11 [summ
0] = 1 1n 1n (0.)), > 0].
1 ( 1m
Therefore for AND, we can set ANDD & (WAND, WAND, (AND) with WAND و
1 ( 1
b1
[
W [1, 1], and we have that
FF FFBAND (x- 1n)) = [rrelu((e In, 1n (-1n)) + 1) - relu( Ins (nn
(n
-1((2 1n, 1n (-1,)) + +1> 0]
(by Lemma F.6)
=AND(x)
1n _p 1 0n
Similarly for OR, we can set OOR (WOR, WOR BOR) with WOR
.b
[ WOR [1, -1], and we have that
0
FFOOR (x (I)) = [relu( (a Ins In 0x),) a) - relu((x Ins In -0)). - -1]]
[I I, In (n,))) > 0)
(by Lemma F.6)
=OR(x)
The proofs for AND and OR are thus completed.
Next we deal with MAJORITY. Note that for s(n) 2 log2 n + 1, we have that 1i=(22;; - 1)
(x" 1n2 2,, (-1n)), for all {0,1)*
n
MAJORITY(2)) =1 (2x, - 1) 11<1((2"))) 1, 2. (--m)); =0
|relu( (x -1o-
Ln. 2n 2n (-11m)) relu(( (e 1n, 2 - 1)]
#F
1n), 1
(14)
2n, - - 1
where (MAJORITY& A MAMORITITY W:MAJORITY
BANAAUORRRTY,MAORRTTTYRR MMAJORITY) with M-MOORRITY
4
.b
2, 1
[
W.MAOORIYY = -1.-
31

---

Published as a conference paper at ICLR 2024
Lemma E.7. For all & N, AC _ SIZE[n
Proof of Lemma F.7. We first define (n]] as the problems solvable by circuits with T(1) standard AND, OR, NOT gates exactly. Thus SIZE nn = UCENI SIZE(Cn*). Now we claim that for each E N, there is a N E N such that for all n 2 N, holds that there is conjunction normal form (CNF) with at most n²* clauses over {.1,.... Fn that cannot be expressed by any circuit of size On This claim holds because of a simple counting argument. There are at least 2* different such CNFs. On the other hand, it is well known that one can represent a T (12) (niee circuit only allowing standard AND, NOT, OR gates with 37(n) T(nn bits (we need log (()) bits to encode the id of gate). Thus the total number of different circuits of size at most C' is at most 23Cn (k Co) which is smaller than 2***1 for sufficiently large We denote such for each C' by Nc. Now we define the following language LCNF: if the input length of is No for some C, use the -clauee CNF's output which cannot be expressed by size-On* circuits as the output; otherwise rejects (output 0). Then clearly LENF & SIZE(Cn*)) for all C, thus LENF $ UCEN- (ieen--IZECCn)) SI By construction, LCNF E AC This completes the proof.
G DISCUSSION ON VARIANTS IN TRANSFORMER ARCHITECTURE
G.1 EXTENSION TO TRANSFORMERS WITH LAYERNORM
Allowing LayerNorm changes the function class that transformer express and the position of the layer norm also matters (Xiong et al., 2020). However, the expressiveness results mentioned in this work still hold for the two most popular transformer architecture variants with LayerNorm Post LayerNorm and Pre LayerNorm. The upper bounds on transformer expressiveness The- orems 3.1 and 3.2 clearly don't get affected by adding LayerNorm, which can be computed in polynomial time for each token.
Below we focus the upper bound of the expressiveness of decoder-only transformers with or without COT. In detail, we will explain why Theorems 3.3 and 3.7 still holds even with LayerNorm. Here the key observation is that, if each coordinate of h E Ed ranges from {-1, 1} and -1, appear in pairs, then LayerNorm(1) (h) h. Thus it suffices to show that we can slightly twist the construc- tion of transformers in Theorems 3.3 and 3.7 that for all i [n T(n)]. E {0. 0.5, 1.... L). h! is composed of -1 and and they appear in pairs so the sum is always 0. Note that in the current construction, each hy only contains 0, 1, 1. It suffices to replace each dimension with four dimen- sions, in the sense 0 - 1, -1), - 1,, -1) and -1 (-1, 1, 1). This can be done by changing the weights of the token embedding, position encoding, and the weights of the second layer of each fully-connected layer. For the outgoing layer, we just use the average of the new representation, which is exactly the same as the original value in all three cases.
G.2 EXTENSION TO TRANSFORMERS WITH MULTIHEAD ATTENTION
In this paper, for simplicity, we only focus on the case where there is only one attention head each layer. The main results in this paper still apply if we allow constantly many attention heads, because we can simulate an attention layer with & heads with & attention layers with one head. Allowing an arbitrary number of attention heads while fixing total embedding size might make the constant-depth transformers strictly more expressive in certain settings and we leave it for future works.
H DISCUSSION ON NON-UNIFORMITY
Non-uniform computation models allow a different program for each different input length, like boolean circuits. However, the complexity class defined by circuits can also be uniform, if we add additional assumption the correlation between circuits of different input lengths, e.g., can require the circuits for input length n can be generated by a Turing Machine taken n as input in using a certain amount of time and space.
The complexity class CoT introduced in this paper can also be made uniform by enforcing an ad- ditional assumption, that the parameters of the transformer can be generalized by some Turing Ma-
32

---

Published as a conference paper at ICLR 2024
chine given the imput sequence length It is well-known that can simulate the execution of the Turing Machine for any T steps by a family of uniform boolean circuits of size O Thus enforce the parameters of transformers in CoT to be uniform, that constant-depth transformers with uniform parameters and polynomially many steps of chain of thoughts solve all problems in P. Also note that the inference of transformers can also be done in polynomial time, we conclude it is exactly equal to P.
main theorem would imply
One natural question about non-uniformity is that whether having a different transformer for each inpul sequence length is practical, given that significant portion of previous theoretical works on transformer expressiveness focuses on the uniform setting. This problem kind of ill-defined because we haven't t been able to scale up the input length to arbitrary length in practice, and thus it is not clear it necessary to keep scaling up the size of L.MSs for longer input sequence length. But at least for the LLMs that have been seen in practice, it seems quite common to scale up the model size when dealing with longer input sequence length. Also taking the GPT architecture (Radford et al., 2019) that we focus on in this paper, having more trainable parameters is necessary for longer input sequence length, due to the trainable absolute position encoding.
Still, one needs to note that there is a difference between natural language tasks and complexity class, where the former has a lot of memorization and does not require a strong ability to solve math problems of any sequence length. In contrast, to learn this complexity class like the composition of permutation of any length, transformers need to have the ability of length generalization, which does seem impossible for certain non-uniform models, e-g-, like GPT architectures with trainable absolute position encoding, because there is no way to learn the position encoding at an unseen position in the training dataset. Of course, length generalization would still be possible GPT architecture learned the ground truth without using the trainable position encoding at all.
33


Reviews:
[{"review_id": "GbA6LcPI3e", "reviewer": "Reviewer_qiA8", "summary": "- The purpose of this study is to demonstrate that CoTs can enhance the reasoning ability of LLMs. To prove this, they utilize the language of complex circuits to compare the expressive power of Transformer models with and without CoTs.\n\n- First, they hypothesize that CoTs enable more efficient serial computations, which vanilla Transformers cannot achieve. they subsequently establish that, when dealing with sufficiently long inputs, the precision of a Transformer model is limited to solving problems within $AC^0$. Furthermore, they demonstrate that CoTs, with T steps, utilizing a constant-depth transformer, constant localization accuracy, and O(log n) embedding size, can solve problems that exceed the capabilities of Boolean circuits of size T. Finally, they find that increasing the embedding size to poly(n) does not improve expressiveness beyond using a log(n) embedding size.\n\n- In conclusion, their theoretical analysis suggests that models with CoTs exhibit enhanced expressive abilities when compared to Decoder-only Transformers without CoTs. they have designed experiments to validate their theoretical findings.", "questions": "- I would like the author to supplement and polish the article based on the weaknesses.\n- In the demonstration experiment shown in Figure 2, it is observed that when the depth is set to 1, the CoT performs less effectively compared to the decoder-only Transformer without CoT. This difference is particularly noticeable when the label represents the sum of the inputs modulo 2 and exceeds a threshold of 20%. This observation appears to contradict the result presented in Theorem 3.2. Is related to the fact that CoT simulates any depth circuit by writing the output token back to the next input position? Further clarification from the author regarding this matter would be greatly appreciated.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Analyzing the effect of the presence or absence of CoT on model expressivity from a theoretical perspective.\n- Proposing a tighter upper bound for constant depth transformers' expressive power.\n- The motivation of this paper is clear.", "weaknesses": "- Symbols are not clearly described. The authors  don't make clear instructions when using symbols like NC^1, AC^0, etc. It is recommended that these symbols be explained when they are first mentioned.\n\n- The conclusions of Theorem 3.8 and Theorem 3.9 presented in the paper seem to be contradictory. Theorem 3.8 indicates that enlarging the embedding size to poly(n) doesn't improve the model's expressiveness of T(n) = poly(n) step CoT. On the other hand, Theorem 3.9 demonstrates that broadening the embedding width strengthens the model's power for any particular polynomial T(n) = n^k step CoT. The conclusions of these two theorems are confusing and require further clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jTocaS1d05", "reviewer": "Reviewer_wS3v", "summary": "The paper studies (mostly theoretically) the experessiveness of transformer architectures. The authors show that transformers with chain of thought can compute boolean circuits with a number of steps that is not bounded by the depth of the transformer.", "questions": "See (1) above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(+) Important result regarding the expressiveness of transformers. The finding seems very obvious intuitively, but the novelty seems to be in a rigorous proof.\n\n(+) Realistic modeling of finite precision computations\n\n(+) The theoretical finding is matched with empirical results on four tasks in arithmetic.", "weaknesses": "(1) I'm not sure I grasp the significance of the finding. It seems obvious that any model can perform serial computations if it is allowed to store intermediate results somewhere (in this case, in the output sequence, which can be written to and subsequently access with self-attention). Therefore, producing such intermediate output seems as expressive as a chain of multiple instances of the model (this does not even specific to transformers).\n\nIs this intuition misguided? Perhaps the important finding is rather that a transformer *without* CoT could not solve serial problems? (but this was covered in previous work).\n\nNote that this topic is not exactly my area of expertise (I was called as an emergency reviewer), but this should be addressed since it is likely something that other readers will wonder about.\n\n---------------------\n\n(2) Presentation could be improved. These are details though that are easy to fix.\n\nThe abstract could be clearer about what form of CoT is studied in the paper (whether it's about the training data, the test phase, the prompting, ...). The very first sentence seemed clear in retrospect to me, not on the first read. So it's probably good to be even more explicit and specify that it's just about instructing the model to generate intermediate steps.\n\nThere are some informal shortcuts in the technical language that should be fixed. Examples:\n\"transformers with polynomial intermediate steps\" -> \"with a number of intermediate steps polynomial in ...\"\n\"transformers with linear intermediate steps\"\n\"poly width and log precision\"\netc.\n\nTypos: poewrful, circuit valuation, \"because every regular languages\" (should be singular)\n\nSec. 4\"we find that cotis always\" (missing space, also in multiple other places in this section)\n\nWeird grammar in the abstract: \"previous works have ...\"\nI suppose you mean \"previous works show that ...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dCCNzcot8V", "reviewer": "Reviewer_pRpF", "summary": "This paper looks at the expressive power of transformer models, specifically looking at the expressive power on sequential reasoning tasks rather than parallel tasks. The main results are theoretical and It introduces several new classes of problems that are tightly focused", "questions": "What is the assumed background of a reader of this paper - as someone quite familiar with both machine learning, complexity theory, and the combinatorial problem classes being addressed, I found this paper confusing - for who I imagine the typical reader to be, I think lots of the content of this paper can be assumed knowledge - for example, I don't think a definition for a finite state automaton (Definition D.1) is a productive use of space in this paper - this is something you can cite directly (e.g. text above corollary 3.4 on p.6). \n\nIn all the figures, I did not find the presented examples particularly illuminating. For instance, with Figure 1, with the non CoT example,  the given label does not appear to be a composition of the permutations given in the input - and it doesn't even appear to have the form of the right answer.\n\n\n\nSuggestions\n- This paper spends a lot of time on the setup and has an extensive collection of supporting material. I like t", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "To my mind, there were three main strengths to the paper.\n\n1. Its theoretical approach: I greatly appreciated the theoretical bend to the paper. Phrasing things in terms of problem classes that a particular model can solve is the kind of I'd like to see more of. \n\n2. Interesting examples: The problem classes they used were interesting, novel, and nicely targeted to the theoretical results\n\n3. A detailed and rigorous approach to a intuitive idea. The supporting information section that includes very detailed proofs and ample details for the interested reader. \n\nIn terms of the primary dimensions, this paper was quite strong in two of them: Originality and Significance\n\nOriginality: As previously noted, phrasing the CoT problem in terms of specific problem classes for particular families of models is a fantastic idea, something we don't see nearly enough of in the field. I also thought the experiments performed were quite original - finding problems in particular problem classes takes a great deal of effort and creativity, the problems they used were not brand new, but were new to the area of CoT and transformer models\n\nQuality: The experiments performed were well chosen and did a good job supporting the theory\n\nSignificance: This paper does make a significant claim and provides good evidence to back it up. Understanding the power of transformer models, where they face challenges, and what problem classes they excel at, is a very significant result and exactly the kind of result that should be featured at an ICLR tier conference.", "weaknesses": "For all the strengths of this paper, there were a number of weaknesses as well. \n\nThe performance evaluation - data was trained and evaluated using \"freshly sampled synthetic data\". I think this is problematic at several levels. First, without a carefully though out test/train split, the model is at risk of overfitting. I think that is fine here - because overfitting is still telling you information about the expressive power of your model class, however this goes against the grain of standard model training practice, and at least deserves comment. Second, the problems used were all discrete problems. Discrete problems are great test beds for theoretical arguments - but in most of these examples, the problem space is finite for a fixed size, and randomly sampling from a discrete space gives the artificial impressing of having more data than is actually available. Finally, how you sample from these discrete spaces seems like it would make a big difference on the model performance\n\nThe model discussion was also significantly lacking. At the very least, a discussion of what the class of transformer models looks like and how you are bounding it belong in the main body of the text, not banished to appendix G on the final page of the supporting information. The details that were present, were in the form of Algorithm 1, defining an implementation, but not the class itsself. That made it difficult to tell what was the result of the model class and what was the result of the training process.\n\nFinally, this paper would be stronger if the presentation was as crisp and focused as the data classes and results. In particular, there was an odd mix of too much detail, too little detail, and superfluous detail. For example, Definitions 3.1 and 3.2 were primarily used in appendix C so their presentation on page 3 distracted from the main arguments of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BHBs4nGhdi", "reviewer": "Reviewer_Aro9", "summary": "This paper investigates whether chain of thought(COT) increases the power of transformers. COT provides additional power to transformer decoders in the form of a hidden \"scratch pad\" where a transformer can perform serial computations. Without COT, a transformer is limited to being a fixed depth circuit, and as such is known to have very limited power in the complexity sense. The paper studies the maximum ability of a transformer given the ability to run COT. COT is able to significantly expand the ability of transformers as without COT transformers are in AC0 and with COT transformers can solve problems from a significantly larger class, all problems with solvable by Boolean circuits of size T (T= time steps given to COT). The key technical contribution is a formalisation of COT and its placement in the circuit complexity heirarchy.", "questions": "--", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall i felt it was a quite well written paper and the case was made well. The paper formalizes the problem precisely, which is not only critical for answering the question considered in the paper, but is also of independent interest. I think the parameterisation of CoT  in terms of embedding size and depth, is novel and interesting. There are several well chosen examples that made comprehension easier.", "weaknesses": "The empirical evaluation is fairly convincing but it does not really reveal anything new insights not already covered by the proofs. \n\nMinor  errors:\nSection 1: poewrful -> powerful", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2WoJs9OwlX", "reviewer": "Reviewer_zX88", "summary": "This paper formally studies the representation power of transformers when used with chain-of-thought (CoT). The authors prove that transformers, under a certain formal model (but see weakness below of the model), with $T(n)$ CoT steps (where $T(n)$ is polynomial in $n$) on input of size $n$ can simulate the computation of any circuit of size $T(n)$. As a result, they derive a lower bound of P/poly. Along the way, they also derive new bounds on finite-precision and fixed-point log-precision transformers when rounding in iterated addition is done iteratively, rounding the sum of two numbers at a time.", "questions": "1. Please see my main concern above regarding non-uniformity. I don't really have any specific question around it, though I wonder what you think about the non-uniformity issue above and how, if you choose to, would you incorporate it in a revised version of the paper.\n\n2. After Theorem 3.2, you mention that an analog of this theorem remains open for log-precision transformers even with a constant number of bits for the exponent. Could you elaborate why one can't just absorb the constant bits of the exponent into additional constant bits of the significand? Perhaps you can illustrate it with what goes wrong if one has $1$ bit for the exponent?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The main strengths of this paper are:\n\n1. its rigorousness in making clear, concise statements of its findings (except for one important \"detail\" discuss under weaknesses);\n\n2. a formal characterization of the power of transformers with CoT, for which results have come out only very, very recently (after the ICLR submission deadline);\n\n3. carefully crafted arguments and proofs around rounding of numbers when performing addition of $n$ numbers, a key step used in multiple prior papers unless less realistic assumptions; and\n\n4. empirical evaluation to support the theory, which is often missing in similar theoretical characterizations of transformer variants in the past.\n\nI have not read the proofs in detail (esp. the material in the appendix), but the results and approach intuitively appear plausible.", "weaknesses": "I really have only one, albeit big, concern about the paper, namely **the formal model of transformers being studied is different not only from all prior theoretical works but also from practical use of transformers**. This is made worse by the lack of a discussion of this difference. Consequently, while the results appear to tighten prior upper bounds and provide novel lower bounds, they really are applicable to a different model.\n\nSpecifically, the authors assume a model of transformers that is **non-uniform** (in the sense it is used in circuit complexity), namely, for each $n$, there is a **different** transformer. As they state in Defn 3.4, \"for every ... $n$, there is a $L$-layer ... transformer\". This means that one needs a *family* of transformers, one for each input size $n$, to solve a given problem, and the weights of the transformer for input length $n$ may have nothing to do with that of the transformer for input lengths $n+1$. To specify such a family, one thus needs to specify an infinite family of unrelated weights, which obviously is unrealistic.\n\nIn contrast, in practice, one trains a transformer on inputs of certain lengths, freezes those weights, and then uses the same frozen-weights transformers for inputs (and chains-of-thought) of arbitrary lengths. In fact, inspired by this, the theoretical research on the representation power of transformers in the past 2-3 years has gone in the opposite direction---from non-uniform upper bounds, to tighter and tigher uniform bounds (e.g., log-space uniform, log-time uniform, FO-uniform, etc.).  Importantly, all along, the model of transformers used was uniform.\n\nThe *non-uniformity* of the model assumed here has other, well-known undesirable consequences also seen in non-uniform circuits---it allows transformers to **trivially solve certain undecidable problems**, namely any undecidable unary problem, over the alphabet $\\{1\\}$. E.g., it can solve the halting problem expressed in unary, just like all non-uniform circuit classes (including P/poly) can.\n\nBesides being unrealistic, this raises a question about the meaningfulness of the technique used to prove the main result (Theorem 3.3). In order to simulate a circuit of size $T(n)$, one must somehow *embed* the circuit into the transformer as the transformer needs to know what circuit to compute. As seen from the proof of it in the appendix, the authors have a creative solution: they put the description of the circuit in the *positional embedding* of the transformer.\n\nWhile interesting and unique, this has two undesirable implications:\n\n1. The positional embedding for inputs of length $n$ is allowed to be arbitrarily different from the positional embeding for inputs of length, say, $n+1$ (because there is no uniformity constraint between the circuits for the two respective sizes, $n$ and $n+1$), which departs heavily from practice.\n\n2. It means that the proposed construction must include some **uncomputable / undecidable positional embeddings**! To see this, consider any undecidable unary problem $P$ in P/poly. The typical polysize circuit construction for $P$ is to have, for each $n$, a trivial circuit $C_n$ that outputs a $1$ if and only if $1^n$ is in that undecidable language (e.g., $1^n$ is the unary encoding of the $n$-th Halting problem). Thus, by the authors' construction, there is a trivial transformer that decides the same language---and its embedding of the first position computes membership in that undecidable language! In other words, the embedding itself in not computable by any reasonable model of computation.\n\nTo summarize this, while the construction is correct to my understanding, it is for a formal model that departs from practice and assumes a lot of power (e.g., that of having access to potentially uncomputable embeddings).\n\nAt the very least, these limitations and their implications should be clearly discussed in the paper.\n\n**Minor points**\n\n* In the abstract, the statement \"with $T$ steps of CoT, constant-depth transformers ... can solve ...\" should be qualified with T being at most a polynomial in $n$.\n\n* In the 2nd last line of page one, I think you mean \"encoder-only\" rather than \"decoder-only\"; or single-step decoder.\n\n* In line 3 of section 2, do you mean $\\phi(bin_k(x)) = x$ rather than $\\ldots = 0$?\n\n* In the 2nd paragraph of section 2, where is the input length limited to $n_\\max$?\n\n* page 3, two lines before defn 3: \"over more two\" => \"over more than two\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ofubcIbvxL", "reviewer": "Reviewer_woBt", "summary": "The paper makes several contributions to the theory of the expressive power of transformers via circuit complexity:\n\n1. Constant precision transformers are in $\\mathsf{AC}^0$\n2. The authors show the existing $\\mathsf{TC}^0$ upper bound for log-precision transformers can be extended to iterated addition with intermediate rounding (at least in the case where the exponent has 0 bits).\n3. Constant-precision transformers with T steps of CoT and nonuniform $O(\\log n)$ embeddings can simulate T-sized circuits and thus express $\\mathsf P/\\mathsf{poly}$\n4. Empirically, transformers get \n\nThe first two results relate to understanding the expressive power of encoder-only transformers, and the third shows one sense in which CoT/decoding steps add power to transformers.", "questions": "Your circuit simulation result feels quite related to Lemma 3 from [Merrill & Sabharwal (2023)](https://arxiv.org/pdf/2207.00729.pdf), except that yours uses CoT to avoid the linear depth that they incurred. It could be worth discussing a bit about the similarities and differences between the two constructions.\n\nIn Theorems 3.1 and 3.2, you write $\\mathsf T[\\mathrm{poly}(n), 1, 1] \\subseteq \\mathsf{CoT}[1, \\mathrm{poly}(n), 1, 1]$, where the first class corresponds to $\\mathsf{CoT}(0, \\ldots)$. Is it possible to say that these classes are actually equal, i.e., a single step of CoT does not add power?\n\nDo you have any examples or thoughts about how transformers might systematically use rounding to gain expressive power (with nonzero exponent)?\n\nG.1: \"ranges from {-1, 1}\" -> \"[-1, 1]\"\n\nnit: Wording Problem -> Word Problem?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The first contribution (power of hard attention) may not be the most realistic model of practical transformers (see Weaknesses), but it is still potentially valuable for filling out the theory of transformers of different types.\n2. The second contribution showing log-precision transformers with rounding are still in TC0 is quite interesting and solves an technical problem unresolved in prior work. Even though the result is not fully general (requires zero exponent), the progress here is quite exciting and perhaps could be extended in future work.\n3. I would like some of the assumptions for the P/poly result to be better discussed (see Weaknesses), but it is a valid and potentially useful result for formalizing the power of CoT.\n4. The paper is generally well-written and organized, and I appreciate the inclusion of a neat empirical study.", "weaknesses": "## Limitations of Constant Precision\n\nConstant precision is not necessarily a realistic setting, since it means transformers cannot attend based on positional encodings or compute uniform attention (which require $\\log n$ bits). In the practical regime, transformers have enough precision to express uniform attention over their input length and can use uniform attention to recognize majority ([Merrill et al., 2021](https://aclanthology.org/2022.tacl-1.49/)), which is outside your upper bound of AC0. Presumably, if we wanted to apply transformers on very long input lengths, we would scale up the precision of attention logarithmically so that uniform attention and positional embeddings would remain expressible. For this reason, [Merrill & Sabharwal (2023)](https://neurips.cc/virtual/2023/poster/70153) propose studying the log-precision model instead of the constant precision one.\n\nTo put it another way, let's say you ran the same experimental setup as Figure 3 but with Majority instead of Iterated Squaring. If transformers are in AC0, we'd expect a similar qualitative pattern where models without CoT struggle without sufficient depth but models with CoT can succeed. But I think that's not what you would find: instead, even models of one layer could do well using a single uniform attention head.\n\nTo be clear, even though I think log-precision is more realistic, I think it is still potentially interesting to analyze the constant-precision case to fill out the overall theory and understand the value of log precision. However, the authors should discuss the differences between constant-precision and log-precision and specifically mention or respond to the argument for log-precision from [Merrill & Sabharwal (2023)](https://neurips.cc/virtual/2023/poster/70153). It could also be helpful to run the experiment I described above with Majority and potentially include the results in the appendix.\n\n## Nonuniform Embeddings\n\nThe paper characterizes transformers with T steps as P/poly. There is something weird about this result, in that it characterizes transformers by a nonuniform complexity class that contains undecidable problems (e.g., the unary encoding of the halting problem)! In contrast, we know that transformers cannot compute undecidable problems since they can be implemented on standard computers. This disconnect comes from the fact that the embeddings are assumed to be **nonuniform**: i.e., they can be any sequence of $O(\\log n)$ bits on inputs of size $n$. This enables the embeddings to be able to encode advice for solving undecidable problems, which standard positional transformers cannot do because they are computable.\n\nThis assumption of nonuniform embeddings should be better highlighted in Section 3.4: right now it's not even visible in the theorem statement. It would also be good to add some discussion of the assumption in the introduction or other high-level parts of the paper so readers don't miss it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)