Compositional Reasoning with Transformers, RNNs, and Chain of Thought
Authors: Gilad Yehudai
Noah Amsel
Joan Bruna
Venue: NeurIPS 2025 poster ()
Keywords: learning theory
expressiveness
transformers
Primary area: theory
TL;DR: We show that solving compositional reasoning problems requires transformers, RNNs, or CoT-augmented transformers to scale specific hyperparameters with input size, revealing distinct strengths and trade-offs across architectures.

Abstract: It is understood that different neural network architectures are suited to different tasks, but is there always a single best architecture for a given task? We compare the expressive power of transformers, RNNs, and transformers with chain of thought tokens on a simple and natural class of tasks we term Compositional Reasoning Questions (CRQ). This family captures multi-step problems with tree-like compositional structure, such as evaluating Boolean formulas. We prove that under standard hardness assumptions, *none* of these three architectures is capable of solving CRQs unless some hyperparameter (depth, embedding dimension, and number of chain of thought tokens, respectively) grows with the size of the input. We then provide constructions for solving CRQs with each architecture. For transformers, our construction uses depth that is logarithmic in the problem size. For RNNs, logarithmic embedding dimension is necessary and sufficient, so long as the inputs are provided in a certain order. For transformers with chain of thought, our construction uses $n$ CoT tokens. These results show that, while CRQs are inherently hard, there are several different ways for language models to overcome this hardness. Even for a single class of problems, each architecture has strengths and weaknesses, and none is strictly better than the others.

Compositional Reasoning with Transformers, RNNs, and Chain of Thought
Gilad Yehudai
Noah Amsel
Courant Institute of Mathematical Sciences
Courant Institute of Mathematical Sciences
New York University
New York University
gy2209@nyu.
noah. amsel @nyu. edu
Joan Bruna
Courant Institute of Mathematical Sciences, & Center for Data Science, New York University Center for Computational Mathematics, Flatiron Institute jb44960nyu.c edu
Abstract
It is well understood that different neural network architectures are suited to different tasks. but is there always single best architecture for given task? We compare the expressive power of transformers, RNNs, and transformers with chain of thought tokens on a simple and natural class of tasks we term Compositional Reasoning Questions (CRQ). This family captures multi-step problems with tree- like compositional structure, such as evaluating Boolean formulas. We prove that under standard hardness assumptions, none of these three architectures is capable solving CRQs unless some hyperparameter (depth, embedding dimension, and number of chain of thought tokens, respectively) grows with the size of the input. We then provide constructions for solving CRQs with each architecture. For transformers, construction uses depth that is logarithmic in the problem size. For RNNs, logarithmic embedding dimension is necessary and sufficient, so long the inputs provided in certain order. For transformers with chain of thought, our construction uses n CoT tokens for input size n. These results show that, while CRQs inherently hard, there overcome this hardness. Even for a single class problems, each architecture has strengths and weaknesses, and none is strictly better than the others.
several different ways for language models
Introduction
Large language models [Touvron et al. 2023 Anil et al. 2023 Achiam et al. 2023 are increasingly used to perform logical reasoning and other problems that require algorithmic thinking. To understand the power and limitations of these models, it is essential to determine what kinds of computational problems they are capable of solving. To this end. long line of theoretical work has studied the expressive power of various language modeling architectures using simple tasks like copying strings, recognizing formal languages, and determining if graph is connected [Jelassi et al.. 2024 Sanford al. 2024b Strobl al. 2024]. Such studies typically provide constructions prove impossibility results for a particular architecture or paradigm-ste as recurrent neural networks, transformers, and transformers with test-time scaling ("chain of fooughh""~-lllowiii the progress of the field
In this paper, consider transformers with and without chain of thought be distinct architectures. We also distinguish between "shallow" (constant number layers compared the input size) and "deep" transformers, While these are all types transformer, our results show that they are qualitatively very different.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Comparison between methods for solving CRQs on n nodes. Each architecture minimizes one kind of resource at the expense of the others. For ease of comparison, we assume the depth of the CRQ tree is log By parallel runtime, mean the runtime using an unlimited number of parallel processors.
Architecture
Num. Parameters
Runtime
Parallel Runtime
Deep transformer (eectinn 4
O(L log n) [O n), ((n) Ollog* n)
O logn)
O(L)
RNN (Section 5
((glogn) O(n2)]
(
Chain of Thought (Section 6
O(n" log" n)
(
In this paper, we take a broader view. We compare the abilities of several different language modeling architectures to solve class of problems that we call Compositional Reasoning Questions (CRQs). While it is intuitive that each architecture has strengths and weaknesses, rigorous understanding of this phenomenon is incomplete. Theoretical comparisons between architectures often use tasks that are selected to make one model look good. For instance, copying an arbitrarily long string is impossible for an RNN with fixed memory, but easy for transformer (Jelassi et al. 2024]. In this work, we prove that the relationships between model classes can be much subtler and more interesting. Our study of CRQs prove that there are unavoidable trade-offs between the architectures we consider, even for a single problem. None of these architectures can solve CRQs without a strong dependence the size of the input. However, each architecture allows to minimize the of some computational resource compared to the others (see Table I}. CRQs are simultaneously hard in different ways for different architectures, but not intractable for any one of them. Thus, the CRQ task provides a crisp and formal way to characterize the essential differences between these architectures.
Our motivation for defining and studying Compositional Reasoning Questions is follows. Many multi-step reasoning tasks share a common tree-like structure, meaning that they are hicrarchical compositions of smaller tasks. Consider the following examples:
What (6 + 2)- 5)?
5)?
Among all U.S. states, which one's highest mountain has the lowest elevation?
To answer these questions, we must first solve several sub-tasks, like "What is + 2?" and "What is
the elevation of the highest point in Hawai??" While some of these sub-tasks can be solved in parallel, the overall task cannot be solved without first gathering the answers to the sub-tasks. Furthermore, sub-tasks may be nested hierarchically to form more complex tree structures, as in 5--88(99:3 (2= Each sub-task corresponds to a non-leaf node of the tree, and the answer to the overall questions corresponds to the root node. See Figure I for an example tree. The paradigmatic example of compositional reasoning is Boolean formula evaluation, which is the problem of determining the truth-value of an expression like (T V) A (-(F A T)). This is problem of fundamental importance in basic logic and in complexity theory, where is one of the key NCC problems, but has been surprisingly understudied in prior work on LLM reasoning. Various other tasks studied in the literature also share this hierarchical structure [Sinha et al., 2019 Feng et al. 2024]. Compositional Reasoning Questions, which we define in Section 3.1] provide simple and unified framework for studying reasoning tasks that exhibit compositionality. In particular, we prove that the CRQ task captures Boolean formula evaluation. Therefore, we believe that CRQs are of fundamental importance as a yardstick for LLM reasoning.
We study the abilities of deep transformers, recurrent neural networks, and shallow transformers with chain of thought to solve these problems. Our main contributions are as follows:
1. In Section 3.1
we present Compositional Reasoning Questions, a simple, formal framework based on semantic similarity for studying LLM reasoning on arbitrary tree structures.
2. In SSecioon 4 we prove that transformers with constant depth cannot solve arbitrary CRQs (hhoormm 4.3) but transformers with depth L. can solve all CRQs of depth up to L Theo
rem 4.
3. In /Section 5, we prove that RNNs with constant hidden dimension cannot solve arbitrary CRQs (Theorem 5.5) but RNNs with Ollog n.) hidden dimension and constant depth can
DDeeending the ordering of the inputs, see more details in Section 5

---

solve all CRQs of size ( (Thoorem 5.4). This ability depends on the inputs being arranged in a particular order (Algorithm 1) if they are ordered adversarially, RNNs require ((n)
hidden dimension (Theorem 5.2).
4. In Section 6. we prove that transformers augmented with Olog n) CoT tokens cannot solve CRQs of size n, but transformers augmented with (n) CoT tokens can Theorem 6.1
Each of these results fills a gap in the literature; taken together, they demonstrate the fundamental trade-offs between different models (Tale T). While deep transformers are highly parallelizable, they require (loog n) depth in the worst case, so the model size must depend (albeit mildly) on the problem size. Likewise, RNNs use little compute but must grow to handle larger problems, although their success depends on the order of the inputs. Chain of thought allows single, logarithmic-size model to handle any CRQ, but it runs slowly and not parallelizable. Overall, our work reveals a rich complexity landscape for an important class of reasoning problems.
2 Related Work
Expressive power of transformers. Our work belongs to large body of research study- ing the representational capacity of transformers, chain of thought prompting and RNNs. Trans- formers with unbounded depth are known to be universal approximators (Yun al.) 2019), and can simulate Turing machines Wei et al. 2022a Merrill and Sabharwal [023b if their size can grow with the sequence length. Looped trans- formers, which repeat a fixed sequence of trans- former layers variable number of times depend- ing on the length of the input, can implement simple but universal programming language GGinnoou et al.) 2023]. Several works studied the expressive power of shallow transformers in solving certain representative tasks. [Sanford let al. (024c) study problems like sparse aver- aging and matching, Yehudai et al. (004) study counting, and Amsel et al. [2025] study nearest neighbor. A long line of work Hahn 2020 Hao
H
[1]
-
P
Figure I: Example of a compositional reason- ing question. Inside each node is the vector corresponding to this node. Red lines indi- cate the answer of each sub-question, given by arg max.ec(w)) Xx, where C(v) are the chil- dren of node v.
et al. 2022 Merrill et al. 2022 Strobl al.]
2024 has used circuit complexity classes to characterize the power and limitations of transformers. Merrill and Sabharwal [023c] show that constant-depth transformers can only compute functions that are computable by Boolean circuits in the complexity class TC We use this result to prove that they cannot solve CRQs either (Theo- rem 4.3). Finally, Chen et al. (2024) study decoder-only transformers, in which each token can attend only to the previous tokens in the sequence, and prove that L-layer decoders are strictly weaker than L ++ 1-layer decoders for the task of function composition.
Past work has also studied the expressive power of transformers with logarithmie-depth. [Sanford) ct al. 2024a|b] focus graph tasks, showing how the parallelism of transformers gives them an advantage over other architectures. [iu et al. 2022) show the ability of logarithmic-deple transformers to simulate finite automata, and Merrill and Sabharwal (2025) extend these results by weakening their assumptions. We note that as implied by Lemma 4.2 CRQs in general cannot be solved by finite-state automata.
Power of RNNs An older line of research studied the capacities of recurrent networks, usually by relating them to automata [Merril] 2019 Korsky and Berwick, 2019 Merrill et al.) 2020). However, they generally assume that the order of the inputs is fixed and that the size of the network is constant in the size of the input. We study models whose hyperparameters (size, number of CoT tokens) change with the problem size, and we study the effect of both benevolent and adversarial orderings of the inputs.
3

---

Chain of Thought prompting. Chain of thought (CoT) [Reynolds and McDonell 2021 Wei
al. 2022b Nye al. 2021] a method that enhances the ability transtormers to solve logical
reasoning tasks. Rather than producing the answer all at once, the model is allowed to autoregressively
generate a series of intermediate tokens to help carry out each step in the solution. [i et al. [2024) show that constant-depth transformers that generate 7' CoT tokens can simulate Boolean circuits of size T. Merrill and Sabharwal [2033) prove they can simulate (T)) steps of a Turing machine.
Most closely related to our work is that Feng et al.
2024] which studies the power of chain of
thought in solving arithmetic problems. Like CRQs, arithmetic expressions correspond to tree of subproblems and are solved by working up the tree. Unlike their work, in which the tree structure is indicated by parentheses in the sequence, we encode the tree structure into the positional encodings of the tokens. However, both problems are NC'-hard Like Feng et al. (2024), we prove that our task is solvable by a constant depth transformer using chain of thought, but not otherwise. However, there are several differences: (i) We provide an explicit construction for solving CRQs using logarithmic depth transformers without chain of thought. (ii) While their task is unsolvable by RNNs with a hidden dimension of o(n/ / log n),, we provide an explicit construction of an RNN that solves CRQs using only (log n.), but does not work for all orderings of the input. (iii) Our chain of thought solution generates n tokens, while theirs requires (nn²) tokens. Such different conclusions emphasize the importance of the input format; in particular our more favorable scalings hint at the importance of leveraging prior information about the hierarchical structure. In [Appendix we generalize our definition of CRQ to also capture arithmetic operations, as studied in Feng et al. 20244.
3 Problem Formulation and Preliminaries
Notation. We use bold letters for vectors, c.g. x, x, Let (x) E R-+++ denote entries i through of and (x)-1 its last entry. For N. [n] (1....,W) Let T (V, E) be rooted tree with root or E The depth of a node v E V is the length of the unique path from v E V to er- The V is the node connected to v on the path to the root and denoted by P(v). The children of v are the nodes whose parent is v, and are denoted by C(v). The degree of node is the number of its children. Thus, leaves have
depth of the tree is the largest depth of its nodes. The parent of a node
degree of O. We say that node is descendant of if there is such that p(t) (u) where p(t) is the parent function composed with itself i times. We also say in this case that v is an ancestor of u.
3.1 Compositional Reasoning Questions
We formally define the class of Compositional Reasoning Questions follows:
Definition 3.1. A Compositional Reasoning Question (CRQ) is rooted tree T= (V, E) with root Ur E V, where each node in the tree t E V is labeled by a vector X. E TTd Here T C I is some finite vocabulary of constant size and d E N.
The size of the CRQ is defined as [V]. The answer to the CRQ, denoted as A(e,), is defined recursively: For leaf u E V we define A(u) = Xy,. For non-leaf node v E V we define:
A(v) = arg max (A(u), x,,,uE((u)
We refer to every node v V which not a leaf as a sub-question.
In AnAAppendix A.2, we prove that Boolean formula evaluation is a special case of CRQ. Intuitively, the leaves represent Boolean literals (true and false), the sub-questions represent logical operations (and, or, etc.), the tree topology encodes the order of operations, and the answer is the truth value of the overall expression. Using vector representations is not only more general, but also makes for simple constructions using language modeling architectures like attention.
In the above definition we assume that the CRQs are defined over some finite vocabulary I'. We can for simplicity, although any other vocabulary is allowed too.
think of it as 1 = {0,
CRQs thus inherently hierarchical tasks, where the usual sequential structure is replaced by tree structure. Therefore, we will consider learning CRQs with models that can leverage this tree structure. Each node is embedded the vector (Xe, Zu, Zp()); ((v)), where x, is the label, is positional embedding, and ((v) is the depth of in the tree.

---

3.2 Transformers
We now provide a formal definition of the transformer architecture that will be used throughout the paper. The input sequence is :i. Xn, R We concatenate Positional Encodings (PE) ei...., Cn E R to the inputs. The positional encodings cannot depend on the values of the vectors X,, only on their positions (namely, on i). The input to the transformer is the sequence
x;
iRdte, The transformer backbone contains alternating layers of hardmax, single-head
self attenttention and feed forward networks with skip connections. For simplicity, do not use layer normalization or attention masking (though the lower bounds like[Theorem 4.3 generrlll hold against models that include them). Formally, let h (2) denote the hidden embedding output after & transformer blocks corresponding to the ith input. Define:
h (0)
8;
h (6+1/2) = h
(E)
VE
arg max NE(h 10 .... (h (
(2)
h ((+1) MLPo
(n
(111/2)
(3)
where Ve, Ke, Qe E (dd+e)x((++)) and 0, are weight matrices and a()) is the ReLU function. Ties
in the arg max are broken arbitrarily. Finally, an unembedding layer y; = Ia
h (L)
discards
entries corresponding the positional encoding. We consider yı be the output of the model. Following previous work [Merrill and Sabharwal c023a|c], we assume that the inputs, weights, and intermediate representations of the network can all be represented using Ollog n) bits of precision. We use hardmax attention for case of analysis, following previous works on the theory of transformers. However, all our constructions can be extended softmax. To do so, we would modify the statements Theorems 4.1 and 6. to say that our constructions approximate the target function up to arbitrary error c > that is independent of n, rather than exactly expressing the target. The proofs would then tune the temperature of the softmax function so that it is sufficiently close to hardmax to achieve approximation error c.
Depth in Transformers is Necessary and Sufficient
In this section we provide two complementary results about the power of transformers to solve CRQs. We first show that deep transformers can solve any CRQ so long as the depth of the transformer at least the depth of the CRQ tree. We then prove a conditional lower bound showing that constant depth transformers cannot solve all CRQs. Combining both results, we conclude that depth both necessary and sufficient for transformers to solve CRQs.
4.1 Deep transformers can solve CRQs
Theorem 4.1. For any L, E N there exists a transformer T with depth L - and embedding dimension O(d + log(n)) that solves all CRQs with at most n nodes and depth at most L.
The proof appears Appendix A.I
First, note that the depth of the transformer depends only on the depth of the tree of the CRQ. This is one of the main strengths of transformers: parallelism. Namely, the transformer is able to solve all the sub- sub-questions in the tree of the same depth with just one layer.
We also emphasize that is probably not possible to solve CRQs of size n with less than log(n) precision. The reason is that transformer without positional encoding is invariant to the order of the tokens. However, the CRQ has an inherent structure, a tree, which without it it cannot be solved. Thus, just to be able to provide even the simplest positional encoding which is numbering the nodes of the tree from 1 until n requires (log(n)) bits (cf. Merrill and Sabharwal (2023al). Our construction
more complex positional encoding that captures the structure while still using only (log(n)) bits.
We now give short intuition for our construction. We first define positional encoding vector for each node that has four parts. For each non-leaf node v, define an identifying vector z, { (=1g0(())())) (log(())
5

---

such that (Zu, Zu) < Zy|i for any nodes 24, V. For leaf nodes, we let Z, = (a)) This is the first part. The second part of node e's positional encoding vector the identifier of its parent, (P(())- The third part is the depth of u in the tree. The fourth is an indicator variable that is 1 when the depth is I. 1, where is the depth of the tree, and otherwise. These four parts are all concatenated to the value of the node x..
We construct each layer of the transformer be exactly the same. Using the positional encoding, we construct the following attention pattern:
Each non-leaf tokens that have depth smaller than L 1 attends only to itself.
Each non-leaf tokens that has depth L- attends only to its children. Specifically, it attends to the child child that answers its sub-question, one whose value vector has the largest correlation with the non-leaf token.
Leaf tokens can do they like, as they will not be attended to in succeeding levels.
By constructing this attention pattern, all the sub-questions in layer L are solved simultaneously. We then use the MLP to reorganize the tokens. We increase the counter of the depth of every token, and update the indicator for nodes of depth L- 1 are altered to resemble leaves, i.e. their 2, vector is set zero. For these nodes, we also set their value vector x; to be the answer to their sub-question, as computing in the previous attention layer. In the next attention layer, nodes previous in layer L will play the part of leaves and be attended to by their parents, which were previously in layer L - 2. Applying this construction L 1 times will compute the answer to the root, which is the answer to the CRQ.
1. Nodes that the previous iteration had depth
4.2 Constant depth transformers cannot solve CRQs
We will now show that solving CRQs using a constant size transformer cannot be done, conditional on the assumption that TC * NC Our main result this subsection is reduction from Binary Formula Evaluation Problem (BFEP), which known be NC -comleee (see Buss 1987) D. to solving CRQ.
Lemma 4.2. The CRQ problem over a finite alphabet is -hadd
For full proof, see Appendix A.2 The reduction is straightforward, and resembles the reduction in Feng et al. [2024] from BFEP
arithmetic problems. The main idea is to define the vectors
and t = tv ! which correspond to 0 and 1 in Boolean formulas. Now note
to = LA
that taking argmax of the dot product with t, corresponds to the A operation, and the argmax of the dot product with to corresponds to the V operation. The operation of - is slightly more intricate and defined in Figure 3 All the operations in the reduction can be done using TC circuits, which means that the CRQ problem is -hard.
It was shown in Merrill and Sabharwal [2023c] that transformers with constant depth, polynomial size and logarithmic bit- precision (all w.r.t n) are in TC Thus, the following theorem follows immediately from Lemma 4.2)
Theorem 4.3. Under the assumption that TC + NC*, any E and polynomial P(x), there exists N such that transformer with depth L, number of parameters that is smaller than P(n) and ((lg(()) bit bit-precision can solve all CRQs of size n.
Combining the two results of this section, see that transformers have the power to solve the CRQ problem for each layer efficiently, however the number of layers of the transformer depends on the size of the tree. This dependence is also mandatory under the assumption that TC * NC1. One concrete example, which will be relevant in the next section, is a balanced binary tree with nodes, and log(n) depth. There exists a transformer that can solve all CRQs of this shape with log(n) layers, but not with constant number of layers. In the next sections we will provide alternative approaches to solve this problem with different models using constant depth.
We note that arithmetic problems, presented in Feng et al. 2024 can also be embedded as certain generalized CRQs. This embedding is presented in Appendix F Thus, both Theorem 4.1 and Theorem 4.3 can be applied to arithmetic problems, if they are presented in tree structure. It

---

is in general possible to apply preprocessing procedure using depth (log(n)) transformer to turn an arithmetic problem presented in a sequential form, into a tree structure which captures the order of arithmetic operations. Note that the above theorem readily extends to transformers with layer normalization and attention masking, since relies on a result for Merrill and Sabharwal [2023c that includes both elements.
5 Solution Using Shallow RNNs
In this section we will show that under certain assumptions, RNNs can solve CRQs. The proofs for this section appear in inAppeddix CJ We first define RNNs in the following way:
Definition 5.1. An RNN is a cully--cnneeted neural network N TRd+m + IR. The inputs to the
(
h, where bo...., h,, R The h,'s 'ss are called the hidden states of the RNN. ho is defined as part of the architecture, and independent of the input data. The output of the RNN is h
RNN are , E IRd,, and the RNN operates as N
Xx
(n_-1)
Xi
Note that in contrast to transformers, RNNs are not invariant to changing the order of the inputs. The reason is that the order in which the vectors Xi...., Xn are fed to the model is part of the imput itself, and not part of the architecture like positional encodings for transformers. We will show that the way the nodes of the CRQs are ordered is crucial for having an efficient solution with RNNs.
5.1 The order of the nodes matters
Our next result shows that there are bad orderings which force RNNs to have large hidden dimension:
Theorem 5.2.
Let T = (V, E) be a balanced binary tree of size n. There exists an ordering of the nodes with the following property: Any RNN that reads the imputs in that order and solves all CRQs defined on T must have a hidden state of size ((n)) bits. That is, if the hidden state is in R. and each eniry is represented by p bits, then p m M(1).
The proof is given in Appendix C.I Note that Theorem 5.2 doesn't 't depend on the depth of the RNN. Note that it is easy construct RNN with hidden dimension of size (n) that solves all CRQs. The idea is just to encode all the nodes in the hidden state, which can be done if we have enough memory, and then use large enough neural network to solve the CRQ. Constructing such neural network is possible by the universal approximation property [Cybenko] [989]] Since the number of possible outputs is finite (because the alphabet is finite), we can approximate the solution up to small enough accuracy and then threshold over the output.
Leshno et al. 1993).
The proof of Theorem 5.2 uses communication complexity argument. Specifically, reduction from the set disjointness problem (see Claim C.I for a formal definition). We then construct communication protocol between two parties, where each one of them has knowledge of only half of the inputs. When using the bad ordering of the nodes, this communication protocol forces the first party to encode all of its inputs into the hidden state when passing it to the second party.
Feng et al. 2024 proved that a specific RNNs construction requires hidden state of size (()) to solve arithmetic problems. Our results are stronger in that: (1) Our lower bound applies to any possible construction, so long as the bad order is used, and (2) We next show that the Q(n) memory requirement can be alleviated by re-ordering the inputs.
5.2 Memory-rank sort
In this subsection, we restrict ourselves to CRQs with full binary trees for simplicity; that is, the degree of each node is O or 2. In Appendixx D) we extend the results from this section to non-binary trees, but note that every CRQ can be converted into an equivalent CRQ with a binary tree and at most twice as many notes (see Appendix D.I).
We will now introduce a sorting algorithm for trees that will allow to solve any CRQs using an RNN with a small hidden dimension. First, we to define the memory-rank of each node:
'It is often common to define two separate outputs of the RNN, the hidden state and the prediction. Here we combine them for simplicity.
7

---

Definition 5.3 (Memory Rank). Let = (V,E) be a rooted tree. The memory rank of a node v E V defined recursively as: mr(v) if is a leaf. and otherwise
mr ()) = max (Omax: Ominn + 1)
where amax max (mr(ci (V)), mr((c(()))
Quin = min (mr(ci(u)), mr(cz(1))) (m)((((t)),mm((((()))
and 01 (v) and (2) are the two children nodes of u. The memory rank of the tree mr(T) is defined as the memory rank of root.
Intuitively, the memory rank is the smallest possible stack size needed for a stack machine to solve the CRQ if we are allowed to pick the order of the nodes. A stack machine is an automaton augmented with stack that it can uses as memory. It processes the inputs sequentially, optionally pushing and popping finite number of elements from its stack at each step and performing computations with the resulting vectors. We should order the inputs according to post- orderind depth-first search of the CRQ, meaning that the position of a node in the ordering corresponds to when the depth first search last visits it. This ordering akin to reverse Polish notation, which notates an arithmetic expression like (2 + 3) * 6 as the following sequence: 23 + *. By ordering the inputs this way, we ensure that whenever the automaton reads non-leaf node, the top two elements on the stack are the solutions to the CRQs defined by that node's two children. It can simply pop them off, compute the solution to the current node, and push the result back onto the stack to save it for later.
Even using a depth-fire first search ordering, the size of the stack used by this machine could grow as large as n in the worst case. However, by ordering the children of each node carefully, we can reduce the stack depth to only log n. To compute the CRQ corresponding to a given node u. we (1) solve for one of its children, (2) save this result on the stack, then (3) solve for the second child. If we solve er (v) first, then the largest stack depth during the first stage is mr(ci (v)) and the largest stack depth during the second stage is (r)) + 1. The overall largest stack depth is the maximum of these two. Thus, to use as little memory as possible, we should always start with the child whose memory rank is larger. This sorting algorithm is defined formally in Algorrihh See Figure 2 for example of memory-rame sort of a tree. In Theorem 5.4 we will simulate this stack machine using a RNN with hidden dimension of size (T()).
5.3 Shallow RNNs can solve CRQs
We are now ready present the main theorem of this section:
Theorem 5.4. For any E N there exists RNN with 5 layers and hidden dimension Or (n)) that solves any CRQ with a binary tree, if the nodes are ordered by|Algorithm 1
The proof is given in Appendix C.2 The main idea is to simulate a stack machine with the RNN. The stack will contain the vectors x, that are needed for future calculations, and will have two possible operations: (1) pop out vectors, and (2) push vector. The stack will be transferred through the RNN in the hidden state. We include the depth of each node in its positional embedding, which will help us determine which of the two operations (push or pop) to use.
At each new input we check whether the last node in the stack has a larger depth by exactly If doesn't, then we insert into the stack and move to the next input. If it does, then we pop out the last two nodes from the stack, say in and u2, and calculate the inner products (x,,, Xwy) ; (X,, Xwg)- We insert back to the stack either Xx, or Xug. whichever has a higher inner product, but with the depth of the node v. All the above operations can be simulated using ReLU neural networks. The memory- rank sort does the rest of the work, since it makes sure that if is the current node to be processed, the last two nodes in the stack must either be its children, or nodes with a smaller depth. Doing this recursively over all the nodes will gradually solve the CRQ.
Note that in Theorem 4.1, we also needed the embedding dimension of the transformer to be ([log(n)), but for a very different reason. There, the transformer is invariant to re-ordering of the input tokens, and since the output does depend on the ordering (specifically, the structure of the tree) we would need ((og(n)) bits just to label the tokens from to For RNNs, the inputs are already ordered, and we even defined a specific ordering algorithm that aligns with our task. The reason that in Theorem 5.4 we need the size of the hidden dimension to be (1)) is because in order to
8

---

solve CRQs, we need to store some of the inner calculations (i.e. answers to the sub- sub-questions) while we solve others. We emphasize that this hardness is not captured by the fact that solving CRQs is hard There are other NC'-hard -hard problems that can be solved with a constant size RNN, such as the word problem on S5 (see Definition 3.1 and Theorem 5.1 in Merrill et al. 2024
Finally, note that the memory rank of any tree with n nodes is bounded by log(n) (see Lemma C.2). In fact, for given tree structure T. the hidden dimension of the RNN needed to solve all CRQs with this structure is bounded by Od mr(T)) using our construction. We next prove that the memory-rame -rank also provides a lower bound on the required size of the hidden dimension:
15
2
14
7
Theorem 5.5. Let E N. let T be a rooted tree of size n with some ordering of the nodes from 1 to n. Suppose there exists an RNN that solves all CRQs with a tree structure T T if the nodes are provided in the given ordering. Then, the hidden dimension of the RNN must have (T)) bits. In particular, an RNN that solves all CRQs all trees of size n. for a given ordering must have hidden dimension with ())lg(n) bits.
12
13
3
11
10
2
5
0
0
8
Figure 2: Memory-rank sorting of tree. Each node is labeled with its memory rank, which ranges from
The proof is given in Appendix C.3 Combin- ing Theorem 5.4] and Theorem 5.5] we see that the memory-rank gives complete characteriza- tion of the memory needed to solve CRQs using RNNs.
in this case. The number below each node is its ordering according to Algorithm Note that we first traverse the right branch of the tree, since the right child of the root has higher memory-rank than the left child.
6 Solution Using Shallow Transformers with Chain of Thought
In this section we show that adding the ability to produce chain of thought tokens also help solve CRQs using a constant depth transformers. We assume in this section that the nodes are ordered in reverse BFS ordering. Namely, for tree with nodes and depth L, the nodes are numbered from I until n starting from the nodes at depth L,, and going up until the root which is numbered n. Our main result in this section is the following:
Theorem 6.1. There exists 2-layer transformer that solves all the CRQs with trees containing n nodes. The embedding dimension is O log(n)), the bit-precision of the transformer is (log(n)), and the number of chain-of-thouge tokens generated is n.
The proof idea is to solve all the sub-questions of the CRQ from the bottom-up. Each generated CoT token will solution to one of the sub-questions represented by a non-leaf node. Each node token contains two sets of positional encoding. The first one represents the tree structure and is similar to the positional encoding from Theorem 4.1 The second one encodes the position in the reverse BFS ordering of the nodes. The role of this embedding is that at each operation of the transformer, the last token that was generated will attend to the next token in the reverse BFS order. This way, all the sub-question in the same layer solved one after the other, before moving on to the next layer. The construction of the transformer itself contains 2-layers of self-attention. The first layer is similar to single layer of the construction from Theorem 4.1 Its role is to solve single layer of sub-questions. The second layer make sure that the last generated token can only attend to the next token in the reverse BFS order, using the designated positional encodings.
Our work leaves open the question of whether a constant-depth transformer can solve CRQs by generating onn) CoT tokens. Li et al. [2024) it was shown that transformers with constant depth that generate O(log(n)) CoT tokens lie in TC (see also Theorem 4 of Merrill and Sabharwal 2025 ). By Lemma 4.2 we know that solving CRQs is NC! -hadd. Thus, under the assumption that TC * ? we know that transformers need more than logarithmically many CoT tokens solve

---

CRQs. However, the gap between (n)) and our solution with ((n) CoT tokens is still open. We also note that by Amiri et al. [2025). in the finite precision case, a lower bound of (2n)) CoT tokens for solving CRQs can be derived. Hence, in this case, our construction is asymptotically optimal. the log-precision case (which is the main setting of this paper), the question of whether our construction is optimal remains open.
We now compare our result with the CoT solution from Feng et al. [024 for arithmetic problems. Both solutions use a transformer with O(1) layers and (rlog(n))) bit precision. However, their solution generated (n 2 CoT tokens, while ours generates only O(n) tokens. This is significant improvement, since for large sequences, quadratic number of generated tokens can be infeasible to generate during inference time. The reason for this improvement that in our solution each generated token solves exactly one sub-question, thus the number of tokens can be bounded by the number of sub-questions. In the solution of Feng et al. [2024), each time one sub-problem is solved (e.g. adding two numbers) the entire expression is rewritten. Thus, the number of tokens needed is + (n - 1) + (n - 2) + ... Onn)). However, we use different input format that encodes the tree structure directly into the positional encodings, rather than processing the arithmetic expression from left to right.
7 Discussion and Future Work
In this paper, we introduce the framework of compositional reasoning questions. We describe the trade-offs inherent in solving CRQs with deep transformers, RNNs, and shallow transformers with COT. Our results indicate that although transformers are highly parallelizable, they must be deep to be able to solve CRQs; in particular, the depth must scale with the depth of the CRQ tree. In contrast, RNNs and CoT can solve CRQs with constant depth, but their operation not parallelizable Transformers require quadratic computational cost, but RNNs can solve CRQs in nearly linear time. Finally, transformers with CoT solve CRQs using a logarithmic number of parameters, while the other models require the number of parameters to be linear in n in the worst case.
Our results have a broader significance for the grand challenge of improving LLM reasoning. The three architectures we consider correspond to three schools of thought about how to make progress on this problem, each of which has received support from the theoretical literature:
1. Scale up transformers by, e.g., adding more layers, and greater capabilities will continue to emerge. Transformers with depth log(n) can do k-hop induction and graph algorithms [errill and Sabharwal 2025 Sanford et al. 2024b c).
2. Devise better architectures, such as state space RNNs or hybrid models, because attention is not all you need to learn and reason efficiently. RNNs can more easily do state tracking tasks like recognizing regular languages [Merrill et al. 2024].
3. Introduce test-time scaling via chain of thought, opening a new axis of the design space. This enables dynamic programming and simulating Turing machines (Feng et al. 2024 Merrill and Sabharwal 2023b].
In previous work, the school that looks most promising depends on which model problem they chose to study. CRQs are just as fundamental as any of the other problems studied in the literature. However, when using CRQs as a theoretical yardstick of reasoning. we find that none of the schools is a clear winner and none is clear loser. Thus, the theory of representational capacity does not give single answer to the question how to improve LLM reasoning. Perhaps some blend of the three schools or fourth school will emerge that dominates the others, but for now the answer is equivocal and contingent, even for a single task.
There are several open questions remaining. First, is our solution using constant depth transformers that generates n. CoT tokens optimal, or it possible to solve CRQs while generating fewer tokens? Second, our work only considers the expressiveness point of view, it would he interesting to understand the optimization process of transformers and other models when solving CRQs. Finally, it would be interesting to understand how general the solutions learned by transformers are. Do they generalize to other trees with different structures, sizes and different question regimes?
'In the arithmetic problems from Feng et al. 2024 we refer to as the number of symbols in the problems.
ie. numbers, parenthesis and arithmetic operations.
10

---

NA was supported by NSF award 2234660. We thank Will Merrill for helpful discussions related to this work and for drawing our attention to the Boolean formula evaluation problem.
Acknowledgments
References
Achiam, S. Adler, Agarwal, L. Ahmad, I. Akkaya, L. Aleman, D. Almeida, Altenschmidr, S. Altaan, S. Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.088774 2023.
A. Amiri, X. Huang, M. Rofin, and M. Hahn. Lower bounds for chain-of-thought reasoning in hard-attention transformers. arXiv preprint arXiv:2502.02393, 2025.
N. Amsel, G. Yehudai, and Bruna. Quality over quantity in attention layers: When adding more heads hurts. In The Thirteenth International Conference Learning Representations, 2025. URL
https://openreviee
R. Anil, S. Borgeaud, J.-B. Alayrac, J. Yu. R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al. Gemini: family of highly capable multimodal models. arXiv preprint a7Xiv:2312.11805. 2023.
S. R. Buss. The boolean formula value problem is in alogtime. In Proceedings of the nineleenth ammual ACM symposium on Theory of computing, pages 123-131, 1987.
L. Chen, B. Peng. and H. Wu. Theoretical limitations of multi-layer transformer, 2024. URL https://arxiv. org/
G. Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
A. Daniely. Depth separation for neural networks. In Conference Learning Theory, pages 690-696. PMLR, 2017.
G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and L. Wang. Towards revealing the mystery behind chain of thought: theoretical perspective. Advances Neural Information Processing Systems, 36, 2024.
A. Giannou, S. Rajput, J.-Y. Sohn, K. Lee, J. D. Lee, and D. Papailiopoulos. Looped transformers as programmable computers. In A. Krause, Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11398-11444 11442. PMLR, 23-29 Jul 2023. URL htttps://proceedinngg htt.:/gssw.rrrr.es.eee.eeeeese www.ppeesss0000 11202//iannou23a. html html
M. Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 8:156-171, 2020.
Y. Hao, D. Angluin, and R. Frank. Formal language recognition by hard attention transformers: Per- spectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-811 11800-100, 810, 2022.
S. Jelassi, D. Brandfonbrener, S. better than state space models at copying. arXiv preprint arXiv:2402.01032 2024.
M. Kakade, and E. Malach. Repeat after me: Transformers
S. A. Korsky and R. C. Berwick. On the computational power of mns. arXiv: 10Xiv:900.000 06349, 2019.
arXiv preprint
M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural networks, 666).861-867, 1993.
Li, H. Liu, Zhou, and Ma. Chain thought empowers transformers to solve inherently serial problems. arXiv preprint 12875 2024.

---

B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang, Transformers learn shortcuts to automata. arXiv preprint arXiv:2210. 2022.
W. Merrill. Sequential neural networks as automata. J. Eisner, M. Gallé. J. Heinz, A. Quattoni, and G. Rabusseau, editors, Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges, pages 1-13, Florence, Aug. 2019. Association for Computational Linguistics. doi: 10.18653/v1/W 19-3901. URL. htt.:itss//aaaaaattllloooooo wwwppgy....///1-/9/00000
W. Merrill and A. Sabharwal. A logic for expressing precissio transformers. In Shinty- Conference on Neural Information Processing Systems, 2023a. URI. ltttps://openrevieer
W. Merrill and A. Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023b.
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log prg--iiiiioon transformers. Transactions of the Association for Computational Linguistics, 1 11:531-540 2023c.
W. Merrill and A. Sabharwal. A little depth goes a long way: The expressive power of log-depth transformers, 2025. URL /ttttps://ariiii org/ abs/ /200..255.... 03961
W. Merrill, G. Weiss, Y. Goldberg, R. Schwartz, N. A. Smith, and E. Yahav. A formal hierarchy of RNN architectures. In D. Jurafsky, J. Chai, N. Schluter, and J. Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 443-459, Online, July 2020. Association for Computational Linguistics. doi: 10. 23665//v/2022.acl-mm/ main.43. URL https://cclanthology) org/ 2020. acl-main, 43/
circuits. Transactions of the Association for Computational Linguistics, 10:843-856 856, 2022. W. Merrill, A. Sabharwal, and N. A. Smith. Saturated transformers are constant-depth threshold
W. Merrill, J. Petty, and A. Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404.088/1 2024.
M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint 2rXiv:2112.0011 2021.
L. Reynolds and K. McDonell. Prompt programming for large language models: Beyond the few-shot paradigm. In Extended abstracts of the 2021 CHI conference on human factors in computing systems, pages 1-7, 2021.
C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halerow, B. Perozzi, and V. Mir- rokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint vrXiv:2405.18512 2024a.
C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024b.
C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024c.
K. Sinha, S. Sodhani, J. Dong, Pineau, and W. L. Hamilton. CLUTRR: diagnostic benchmark for inductive reasoning from text. In K. Inui, J. Jiang, V. Ng, and X. Wan, editors, Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International pages 4506 Hong
Joint Conference on Natural Language Processing (EMNLP-IJCNEL Kong, China, Nov. 2019. Association for Computational Linguistics. doi: 1..1 1/599 URL http:////aaaaathhllo/o www.oogggg-........o 1458/
L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin What Formal Languages Can Transformers Express? A Survey. Trunsactions of the Association for Computational Lin- guistics, 561, 05 2024. ISSN 2307-387X. doi: 10.1 (a26///alaa00066666 a URL https 1/doi. ww12/111c1//// a_00663
12

---

H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, al. Llama: Open and efficient foundation language models. arXiv preprint (tti:2300..3977/ 2023.
C. Wei, Y. Chen, and T. Ma. Statistically meaningful approximation: case study approximating turing machines with transformers. Advances in Neural Information Processing Systems, 35: 12071-12083, 2022a
J. Wei, X. Wang. D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. Le, D. Zhou, et al. Ohain-of-thoughe prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-248371 2022b.
A. C.-C. Yao. Some complexity questions related distributive computing (preliminary report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 209-213, 1979.
G. Yehudai, H. Kaplan, A. Ghandeharioun, M. Geva, and A. Globerson. When can transformers count to n? arXiv preprint 201.152007..1660, 2024.
C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar. Are transformers universal approximators sequence-to-sequueee functions? arXiv preprint drXw:1912.10077,, 2019.
13

---

A Proofs from Section 4
A.1 Proof Theorem 4.1
The following lemma is useful for defining the positional encodings:
Lemma A.I. For any k 2 2 there exist vi,...; E (=1} (=1] such that (Vi, V3) S 3 (lg())
for all +
Proof. We sample Vi...., Va E (=1]))og(k) uniformly at random. Note that for any i + we have that (((v vy)l 0. By Hoeffding's 's inequality we have that:
Pr (I(v,, vy)l 3 log())) S 2 2exp(-4
Applying union bound on the above for all pairs i + we get that:
2
Pr (Vi # j, 1(v,, v3)1 & 3 log(+)) 2 2exp(-4log(k)) 222
k
In particular, for k this probability is non-zero, meaning that there exists such vectors Vi Vk-
Theorem
For any CRQ with up to n nodes, there exist at most |Y| S possible queries. By Lemma A.1 there exist vectors Zi...., Zn E (=1 such that (2,, 2,) S log(n) for any
/
8 3
We will first describe how embed each node as imput token to the transformer, and then describe the construction of the transformer itself. For each node E that is not a leaf, we set one of the vectors 2, 's be corresponded with this node, and denote it as 2,, Recall that P(v)) is the parent of node v. Note that although each node may have several children, only has one parent.
Each node of the tree will be embedded as vector in R 2d45 1og(()++2 The input tokens corresponding to leaf node and non-leaf node are defined as:
Og
0g
(u)( O4 log(n)
tw =
to
(5)
(p)()) ((u)
(E(v) = I
where f(v) is the depth of node v (the length of the shortest path from vo to the root).
The crux of the construction lies mainly in the way choose the embedding: The embedding first contains the value of the leaves or query of the corresponding node. The embedding also contains a positional encoding (PE), where each leaf token contains its parent's 's PE, and each non-leaf token contains its own PE as well as its parent's, s. In addition, there is number representing the depth of each node and a flag whether node is in the second to last layer (i.e it is the deepest intermediate node connected to leaf).
We construct the weights of the transformer so it will work as follows: In the first layer, each token representing an intermediate node will attend either to itself, if its depth higher than L - 1, or to its children, if its depth is exactly T, - 1. This means that only the tokens of nodes in depth 7, will change while all other tokens of intermediate nodes will remain the same. Using the positional encodings, the tokens depth L 1 will attend only to their children, not to themselves, and after the self-attention layer (before applying the V matrix) will be equal to the token representing their child with the highest correlation to their query. We now the V matrix, residual connection and MLP so that the tokens with depth L - will have a similar embedding to the leaves tokens, and decrease the depth of all other intermediate tokens. We also make
that the flag after the first layer will be equal to for nodes depth 2. We now apply a similar layer exactly L times, so that in the final layer the output of the token representing the root will be equal to the solution to the CRQ.
We now turn to the formal construction of the transformer. The order of the input tokens is not important for the construction, except for the root token which will be the last token since its final
14

---

embedding will include the answer to the CRQ. Let 2 1 be some universal constant such that ||x| I for every x E rdd there exists such constant since I is finite. The matrices of all the layers of the transformer will be the same and equal to:
72d+8 log(m)
K
0
Ind
6CI4
Q =
cl1log(n)
6c log(n)
Oat
La
V
Ta
Oa
(2
Before defining the MLP, we will explain how the attention layer operates on the input tokens. Since the attention mechanism contains a hardmax head, the output of each token will depend only on the token to which it attends. We will first show the next two claims:
1. Each token non-leaf node with (t,)) = 0 will attend to itself.
2. Each token non-leaf's with (t,) = 1 will attend to t, with arg max ( (Xus X.).
For the first claim, let u be some node with (t,) 0. Then have that:
ty K Qt. ||xx + 6e ||z0111 e||zp(()) || Now, let u A o be some other node. If is a leaf then we have that:
28c log(n)
(6)
t KT Qt S (Xx: x.) + Ge/ (ZP(u)) zn) + cl (0. z
sc 24c lng 25clog(n)
is not leaf then we have that:
t K Qt. S (xx, x 6c| (zu, z,) + cl (Zp(n); zp(w))
S c + 18clog(n) (n) + 4c log(n)) 23c 23c log(n),
where we used that (zu: zu) 1 s log(n) for + u. This shows that to can only attend itself.
Next, let v be a node with (t,)-1 = 1. Let u be a node with u E C(v) and let w * u with w & C(v). We have that:
t, K Qt. (Xx: xx) 6c |
2 - 24clog(n) 2 23c 23clog(n) log(n)
t KT Qt $ (x x.) 6 (z' 2 + (w), zp(w))
S c + 18c log 4clog((1)
< 23c log(n)
K Qt, x, 2 6z |., 11 1 ( | 6c
- log(n)
< 24clog + (o 6c log < 23clog(n)
Here z' is some vector with z' + z. (n fact, z' z or z' (w)) depending on whether is leaf). This shows that t, can only attend to its children. It is also clear that t, will attend to its child that maximized (X,, x,). This finishes the two claims above.
After applying the matrix and the residual connection from the previous layer, the output of the self-attention layer on token t, equal t, + O., where (o.) = x, if (t,)-1 0 and 1. In words, the entries of each token in place d + until 2d after the self-attention layer is the solution to the sub-question for the deepest non-leaves nodes of the tree, and for other nodes it the queries themselves.
(o.)(d+1:20) arg maxx max(). (X,, if (t.)-1
We now define an MLP that will reorganize the tokens before applying the next layer of self-attention. The role of the MLP will be perform the following operations input token t.:
15

---

-2
2
iI
0
i
ta/t t
-2
()
P2
Figure Left: Construction for mp. Right: Construction for yo A 922 and yp V 422
1. If the entries in places 2d 4 log(n) + 1 to 2d + 8 log(n) zero, then t, 0.
2. If the last entry of t, is equal to 1, then replace the entries in places 2d +1 until 2d log(n) (n)
(which used to hold z.) with the entries in places 2d + 4 log(n) + until 2d + 8 log (which used to hold 2p())) Then, replace the entries in places 2d 4log(n)
until
2d + 8 log(n) with zeroes. This makes it a leaf embedding.
3. Replace between the entries in places until d and d + until 2d. Then replace the entries in places d + until 2d with zeroes.
4. Add 1 to the entry in place 2d + 8 log(n) 1. Then, if this entry is equal to I. 1, replace the last entry with 1, if this entry is equal to T. replace the last two entries with zeroes.
The first operation zero out any token that corresponded to leaf node, they won't otn't be necessary in later stages of the computation. The second operation turn tokens the second last layer to have the same embedding have a PE their own. The third operation update the value x,, this only changes for nodes that in the second to last layer. For any other non-leaf node, since it attended to itself both vectors are equal. The last operation updates the depth of each node. Now, each node that was in the second to last layer will be embedded similarly a leaf, while nodes in the third to last layer will have 1 in their last coordinate.
leaf nodes, namely that they only contain the PE of their parent, and don't 't
Each such operation can be implemented by 2-layer MLP with width bounded by O(d + log(n)). For example, implement the first operation we use the function:
f(z) a(2 1) a( 1/2) + a(1 - ( (1/2-
that can be implemented by the first layer of an ML.. We concatenate the output of this function on the 2d + log(n) + 1-th coordinate of the input, to the input itself. Then, we use the output layer to apply the function x - 0ş (8)+41 + & (1 (x) ())++)> 1) where X is the input concatenated with the additional coordinate of the output of f, and & = 2d log(n) + 2. use similar constructions to implement the rest of the operations.
After applying the MLP we have that each token is either equal to: (1) if it was previously leaf. (2) An embedding of leaf if it was previously in the second to last layer; or (3) An embedding of non-leaf node if it wasn't It leaf or in the second last layer. By applying the same construction L times, we get that each node except the root is equal to 0, while the first d coordinates of the
root contain the answer to the CRQ, which the final output of the transformer. This finishes the proof.
L
A.2 Proof of Lemma 4.2
Our proof relies on reduction to the Boolean Formula Evaluation Problem (BFEP). was shown in Buss 1987), that this problem is NC1 -cmmcopple thus reduction of BFEP to CRQ would finish the
16

---

proof. The BFEP is defined recursively over the alphabet: = (1,0, 7, 7,3 in the following way:
1. 0 and 1 are Boolean formula.
2. If yp is Boolean formula, then (-ip) is a Boolean formula.
3. If (P1, (P2 are Boolean formulas, then (191 (22) and (f1 A (22) are Boolean formulas.
The goal in BFEP, is given a Boolean formula to evaluate whether it is true or false (i.c. outputs 1 or 0). We will construct translation function from Boolean formulas CRQ. and specifically to tree structure where each node is given a specific value. We will use vectors in IR* while in fact all the possible values of the vectors in the CRQ will be in {0, =1, +2). We define the vectors
t )) and
The translation function is defined recursively follows:
1. For f()) and f(1) we construct a node in the tree whose corresponding value is equal to to and t1 respectively.
2. Given two Boolean formulas yP,, P2 define f((() (22) and [(((1 V vy2)) the tree in Figure 3 (right), where for A we use to for the root, and for V we use t₁.
3. Given Boolean formulas yp we define ((-p)) as the tree in Figure 3 (left).
We will first show that this construction can be done using TCº circuits, and then show its correctness. Given Boolean formula of length it is clear that the construction above creates tree with at most O[ss)) nodes, where the values of each nodes a 2-d vectors with entries in {0, +1, +2). Thus, the total number of bits requires for the construction is also bounded by O(ss)).
The translation works recursively over the logical operators A, V, and make the construction work we need to know in which order to translate them. Namely, the root should begin with the outmost logical operator, its children the second outmost operators etc., until reach either 0 or 1, which should be translated to leaves in the tree. We will show that this order can be determined using TC circuits. Given Boolean formula yp we define by ii its character in place i. We define:
rs = Σ [() j<i
= [-0]--1fe -1(p==1> 1'].
jei
It is easy to that r; can be calculated using TC² circuits. Now, the order in which the recursion works is in increasing order w.r. r; over the logical operators. Namely, begin with the logical operator place i where r, 0, continue with r; +2 an so forth.
For the correctness of the reduction, it is an easy calculation to see that given t, for i E (0, 1} the construction for -yo outputs f1-; with the definition of CRQ. Also, for A and the construction outputs correctly t; A t, and f; V ty for i, E 10. Therfore, this construction forms a reduction from the BFEP to CRQ, and thus CRQ is NC hard.
B Memory-rank sort
In this section we formally define the memory-rank sort. is presented in Algorithm I We next prove that performing memory rank sort and calculting the memory-rank of all the nodes in a tree can be done efficiently:
Lemma B.1. Let T (V, be rooted binary tree, then calculating the memory-rank of each node and performing the memory- -rank sort takes time O(VI).
Proof. Calculating the memory rank of each node can be done using reverse breadth-first search (BFS) of the tree, traversing from the leaves to the root. BFS can be done in time O(VV), and calculating the memory rank of each nodes requires only knowledge of the memory rank of its children. Thus, this can be done in linear time by going over each node only once.
The time that Algorithm I runs is the number of iterations in the "while" loop. Note that each leaf in the tree visited at most once, since if yeur is leaf, it is inserted the list and not visited again. For any non-leaf node, it is visited at most times during the loop. Once for each of its children, and
17

---

Algorithm 1: Memory-Rami Sort
Input: Tree 7 =V, F)) with root fr and memory rank calculated for each node.
S
Plur
V/
while
|S| + [V do
if Uour = 2 or C(Ueur) S then
x Vaur
Ucur ((vau))
Continue
Ucur
arg max mr(:)
oEC(va))ogS
Return: S
again when inserted into the list. total the running time of the sorting algorithm is bounded by 3.V.
L
C Proofs from Section 5
C.1 Proof Theorem 5.2
Proof. Our proof uses the following claim from communication complexity:
Claim C.1 (Lower bound for set disjointness (Yao 1979).. Suppose Alice and Bob are given inputs b E {0, 1)", respectively. Their goal is calculate max, a,b, by alternately sending 1-bit messages to one another over a sequence of communication rounds. Any deterministic protocol for computing max; a,d; requires at least rounds of communication.
For simplicity of the proof, we use trees with 4n - nodes instead of n, this will only affect the constant in the Ω notation. We construct the following CRQ: The tree T (V, E) is a balanced binary tree with 4n nodes in the second to last layer are all equal to 1, and the
nodes, thus has 2n leaves. All the values of the leaves are in {+1]. The
equal to 1. We number the leaves as V1...., 02n- Suppose we are given an instance of the set-disjointness problem, where Alice is given the leaves 1 1 and Bob the leaves U2i for i [n)]. By the definition of CRQ, the answer to the second to last layer nodes with leaves 02; and U2 is if U2--1 U2 = 1 and
non-leaf nodes
-1 otherwise. In addition the answer any other node will be if one of its children is and -1
otherwise. In total, the answer to the tree is if there exists some i E [n)] with U2--1 = U2 = 1 and otherwise.
The first n nodes are U2 for i E [n]. the next nodes U2 for i [m]. The root is the last node in this ordering, and the rest of the nodes are given in some arbitrary order. Suppose there an RNN known to both Alice and Bob that solves the CRQ problem above in the prescribed order of the nodes, and it has hidden state h E R where each coordinate is represented by p bits. We will define the following communication protocol to solve the set disjointness problem: Alice apply the RNN on her inputs. After each input v2:-1 for i E [n] she passes the hidden state h; to the next recurrence of the RNN. After n such recurrences of the RNN, the hidden state h, is passed to Bob, he inputs his inputs V2 for j [ni] in the prescribed order, each time passing a hidden state. He continue to run the RNN on the rest of the nodes, and output the answer the CRQ. The number of bits transferred between Alice and Bob m p. since the only communication between them is transferring h, and Alice finishes processing her inputs. By Claim C.I we have that mp 2(n). which finishes the proof.
Consider the following ordering of the nodes for the RNN:
C.2 Proof of Theorem 5.4
We first need the following lemmas:
Lemma C.2. For a binary tree T with n nodes, have that mr(T)) S log(n).
18

---

Proof. Let ry be the smallest number of descendants for node with memory-rank k. It is easy to see that r1 = 2, which happens when the node has only two children that are leaves. Let be node with mr(r)
k, and let w1, M2 be its children. It can be seen that 2 2rk-1- This is because, if mr(u1) * mr(u then one of them must be equal to k, assume w.l.o.g is u1- This means that either 41 one of its descendants have two children with memory-rank of k 1. In particular, the number of descendants of o is larger than 2r If mr(()) = mr(u)), then they are both equal to k - in which case the same conclusion follows. Applying the recurrence formula, we get that rk 2 2
Let k be the memory rank of a tree with n nodes. We have 2 < r S n. Thus, k I [log(n)]. Hence, for any tree with nodes, the largest possible memory-rame of the tree is bounded by log(n).
Lemma C.3. Let R, c > 0 and d E N. There exists a 2-layer neural network N: R2d - R with width
R such that mexx.yel-R.n (x (x, s.
Proof. We can use Lemma 6 from Daniely [2017] to find 2-layer network N RR2 - R with width O (t) such that max ye R,,r [2r,)) - yl S c. Summing such networks over the coordinates of and y, and replacing with = proves the lemma.
The main crux of the proof simulate a stack using a ReLU network with constant depth. The maximal size of the stack for tree T = (V, E) will be O(d - mr([)). The RNN will execute the following pseudo-code:
Theorem 5.4
1. Given an input node v, check the last node in the stack:
(a) If has the same depth or larger depth than v, then add to the stack. (b) If has depth that is lower by exactly than e, then pop out the last two nodes from the stack and w. If (u, v) 2 (w, v) then insert into the stack and raise its depth by Otherwise, inset w and raise its depth by 1.
2. The stack is the hidden state that is transferred to the next iteration of the RNN.
We now turn to the formal construction. Each node E V in the tree will be embedded as a vector {(V) E Rd+1, where ((v) is the depth of v. The hidden state of the RNN at the beginning will
be Od(log(n)+1)- The input to the RNN will be the current input vector, concatenated to the hidden state. Throughout the proof we refer to X the vector that is inputted to the RNN, namely the concatenation of the embedding of each node with the hidden state. We call the part of x that contains the hidden state h the stack, and each consecutive d coordinates in it as node that is was inputted to the stack. The reason is that this part of the input will simulate a stack where the RNN can only access its first and second nodes, namely the first 2d + 2 coordinates. The RNN will add at most 3 coordinates to x, which will simulate flags with values that are either 0 or 1. The RNN contains the following layers:
1. Layer 1: Check whether the depth of the input node is the same or larger than the depth of the last node in the stack. If so, turn on specific flag for this event.
2. Layer 2: the flag is turned on, insert v into the stack by moving all the elements log(n) entries forward and putting at the top of the stack.
3. Layer 3: If the flag is turned off, extract the last two nodes from the stack in and u2 and caleulate (Xuy xx) (Xuy. x,).
4. Layers 4 & 5: If the flag turned off, insert un or u2 to the stack, whichever has the higher inner product with v. Also, increase the depth of this node by 1.
Note that the input to the RNN is of dimension d(log(n) + 1) + d+ 1, which is concatenation the embedding of the current input node and the hidden state. We will also need to following parameters:
19

---

Let e > O be such that > |a| for every E T. namely, it is larger than all possible entries of the x, 'ss and that c > L, the depth of the tree. We have that (()) which is the largest possible depth of the tree. Also, let é > 0 such that mina, |a bj < We think about as a constant independent of and d, as only depends on the possible values in r. Each layer is constructed in the following way:
First layer:
We denote the input vector the RNN is x. The first layer add a coordinate to the input. All the input coordinates are copied, while the last coordinate is constructed as: ((())++1-((x)) (1)411)))224+++
1) - -=x(())++ d++ (x)2d+1) 1). Note that this added last coordinate equal to 1 (x)d41 - (x)2d+1 2 0. meaning that the current node has an equal or larger depth that the last node in the stack, and 0 if (x)d+1 (x) 2d+11 I -1. The copying of the input can be done by a ReLU network, since (22) - (-2) = a for every & E R. Thus, adding two identity matrices to the weights of the MLP with different signs, and adding their outputs together will copy the inputs.
Second layer: Let A = (1 la+i (I(llog()++))
be a d(log(n) 1) + d d+ 1 square matrix. The second
layer will perform the following operation:
x (Ix()--)) -cIx(-1) + cl) + (Ax(1=-2) 2cI(-x((1) +1 +1) +c)+ cl.
This operation can be implemented by a 2-layer network, where the constant vectors are added using the bias terms. This operation will apply the identity matrix to the inputs if the flag (defined in the previous layer) is and apply the matrix if is 1. The A matrix will copy the first d + 1 entries (the current input node), and will move also add it to the stack, while also moving all the other entries + coordinates further down in the stack. The added cl factor so that if there are negative values in the entries of the inputs, they will not be removed by the ReLU, this factor is removed at the end to keep the original value. We will later on prove that the stack will not get overflown, meaning that we don't 't delete the last d + 1 entries of it.
Third layer: This layer will be used approximate inner products. Assume that v is a non-leaf node and let ú1 and uy be its two children. If it is a leaf node, this layer will not effect its input, The layer will add two coordinates to its input vector, corresponding to an upproximation of (xx, x) and (Xus, x).
By Lemma C.3 there exists a 2-layer neural network N Rd2d + R with width O(d²) such that maxx,ye1 y) (x,y) y) S f. We will stack two such networks that approximate up to an error the inner products (Xuy: xx)) (Xmg xn). If X., A Xu2. then by the assumption on we have that (Xuy: Xx) - (Xua: xx) 2 By the construction of N, we also have that:
(xx,, Xo) (Xuu x.) S [Nxx,, x.) N( x.
2
This means that (x x.) - -N(xxss x,)1 5. We use similar construction to the previous layer to apply this calculation and add A' (Xu,) and MindN((x,) N x,) only if the flag in the last coordinate is turned off. Otherwise, if the flag is turned on, we just copy the inputs.
Fourth and Fifth layers: In the last layer, we add an additional flag on whether (Xuz; Xu) > (X Xx) and 0 otherwise. This can be calculated by using the following function:
2 (0((xx)2--xx) (x) - o(xx)2 -x))))(=-=(())---)
x
By the argument from the previous layer, this function will provide the additional flag. All the other coordinates are copied as is. We use another layer to pop out the first 2d + 2 coordinates from the stack, meaning that all the entries in the stack are moved upward by + 1 coordinates, and the first
d ++1 are changed to either
Xu:
Xuz - 1)
depending on whether the new flag is 1 or
(((z))))
-
((uz)
0. Again, we apply this operation only if the flag from the first layer is turned off, by using a similar construction to the second layer. The rest of the coordinates are copied, and the coordinates of the flags that were used throughout the computation are removed. The output will be the hidden state to the next recurrence with the dimension the hidden state that was inputted.
First, it clear from the construction that applying the RNN on a single input node will perform the poeudo-code described in the beginning of the proof. We will show the the construction outputs the correct answer to the CRQ When a node inputted to the RNN, according to the ordering of the memory-rank sort, there are three options:
Proof of correctness:
20

---

1. Its depth is equal to the the depth of the first node in the stack. This can only happen to leaf nodes, in which case, according to the memory-rank sorting, the node in the stack must be sibling of the inputted node.
2. Its depth is larger than the depth of the first node in the stack. In this case, the first node in the stack will be pushed down to the second place after applying the RNN.
3. Its depth is smaller by exactly than the last node in the stack. In which case, it must be its parent, and the second node in the stack is its sibling. After applying the RNN, both nodes are popped out, and the node that correctly answer the query corresponding to v is inputted back to the stack, but with an updated depth. In this case, all the descendants of the inputted node have already being processed by the RNN, and the next inputted node will necessarily be its parent or sibling.
By induction over the nodes of the tree, and using these three options we get that after applying the RNN to the root (which is the last inputted node), the only node left in the stack is the answer to the question given by the root, which is the answer to the CRQ.
We are left with showing that the stack does not overflow. We will show that the maximal number of nodes in the stack is bounded by mr(T) + 1. Since the number of coordinates in the representation of each node is d + 1, using Lemma C.2 finishes the proof. Let u be some node with mr(v) k. We will first show by induction on & that at any point in time, before processing v, the maximal number of nodes in the stacks that are also descendants of is bounded by k. If h 0 then is leaf doesn't have any children. For the induction step, assume k > 0, and let U1, U2 be the two children mr(u2). ug), then by the definition of memory rank, they are both equal to & 1. Assume w.l.o.g that in is processed before U2 Note that in this case, U2 is processed only after all the descendants of uj are processed. Then, by the induction step, the maximal number of nodes in the stacks that are also descendants of U2 is bounded by k - 1. Hence, the maximal number of nodes in the stack that are descendants of u is k. which includes d If mr (11) o mr(u2). assume w.l.o.g that mr(u)) > mr(u2). ). then i is processed before U2 (resp. u2 before w1). ). In this case, by the induction case, again the number of nodes in the stack the are descendants of v. are either descendants of un in which case no nodes that are descendants of u2 have being processed, or descendants of u2, in which case tn is in the stack, as well as at most
of v. If mr(u1)
descendants of u2- This finished the induction.
Now, we will show that the number of nodes that are not descendants of v and are in the stack is bounded by 1 + mr( - k. This will be by induction over p()) (v), namely the ancestors of v. We assume that mr mr(k) = v. If mr(P(v)) = k. then v is processed before its sibling, which by the induction we showed before, the number of nodes in the stack that are descendant of p(t) (v) is bounded by k. If mr(P(c) = le + 1, then the sibling of either have a memory- of k or larger than k. In both cases it can be processed before v (as well as all its descendants). hence the number of nodes in the stack that are descendants of P(u) is bounded by l + 1. Using the same induction argument before, applied for the sibling of (v) we get that the number of nodes the descendants of u that are in the stack is bounded by mr mr(p(+))()) + 1.
Combining the two inductive arguments above, we get that when v processed into the RNN, the number of nodes in the stack is bounded by mr (T) + 1. This finishes the correctness proof.
By induction on mr(v). If m 0. then is a leaf. By Algorrithh I since doesn't have children, the only node that is processed before it can be its sibling. When its sibling was processed necessarily all its children were already processed, hence there is at most 1 node in the stack. Assume that if mr(u) = k. then there are at most l + 1 nodes in the stack, and let e with mr(v) = k + 1. Denote by in and ua the children of v. and assume w.l.o.g that ar(u)) 2 (ug)).. If mr mr(u1) > mr(wz). then mr(v)- = mr(u2). ). This means that tn was processed before Ug Hence, U1 is in the stack, and U2 was processed right before v, which by induction shows that there are at most k + nodes in the stack. If mr(u)) mr(u2), the by the definition of memory-rank, it necessarily happen that they are both equal to k. Assume w.l.o.g that i is processed before U2 (the order of them being processed chosen arbitrarily in this case). Hence, when processing U2 there most k nodes.
21

---

C.3 Proof of Theorem 5.5
We begin with proving the theorem for balanced binary trees and then generalize to other trees. Let T be a rooted balanced binary tree of size with given ordering of the nodes denoted as: U1...... Un-
Let == lo + 1). We define the vectors to = -i) -i),tt t )))
We now define tnull = (0)
set of CRQs given by X E (to. t1, tmul2] } for all i [m]. We will show that given an RNN that solves all CRQs with this tree and this ordering of the nodes must have a hidden state containing (llog(()) (n)) bits.
As in Lemma 4.2) an intuitive way to look at these CRQs is as Boolean formulas. For leaf nodes to represents O and t represents 1. For non-leaf nodes, to represents A and t1 represents V. The vector tu11 is used by a hidden node to pass values up the tree without changing them, as described below.
Let u1 be the last leaf node in the prescribed ordering. Denote its ancestors ug...., Ug where uR is the root. Also, for each u; with i o denote its other child as w;-1 (i.e. the sibling of uq-1). 1). Suppose that the current input to the RNN is u1. We will show that the RNN needs at least & bits in its memory at this point in the calculation to solve the CRQ.
We consider the set of CRQs defined by the following rules:
1. Each of the nodes wi and u,,..., up equal to either to or ti.
2. For each node w2..... 1k-1 all its leaf descendants are identical to one another. Either they are all to, or they are all tj. Its non-leaf descendants, including itself, are all equal to tmlll
To solve the sub-question represented by u2, the RNN must use 1-bit of memory to remember wi, since by assumption, wi precedes #1 in the sequence. Similarly, to solve the sub-question represented by u2, the RNN must know the answer to w2- Because of rule 2, each subquestion in the subtree rooted at W2 results in a tie. Because all the leaves in this subtree are identical, the answer to the subquestion rooted at W2 equals any of its descendant leaves. These leaves all precede u1 in the sequence, so we must use 1-bit of memory to store their value. For each node ug.... Uks the RNN must store at least 1 bit of memory at the point when it processes u1. In total, this amounts to log(n) - 1 bits of memory that needs to be transferred through the hidden state of the RNN.
Now, let T be some rooted tree of size n, which is not necessarily a balanced binary tree. Denote by f := mr(T), and recall this means that the root has a memory-rank of f. We will find subset of T that forms balanced binary tree whose depth equals f. We will construct all the other nodes to simply copy their inputs up the tree, and appeal to the case of a balanced binary tree proved above.
We first show how to find such a subset. If the root has two children with memory rank of L - 1, denote the root by uj. Otherwise, exactly one of its children has memory-rane of e search recursively through its children until a node with two children of rank - 1 is found and label it u.. We now apply the above procedure recursively on the two children of u1- This yields two nodes, U2 and uty each of which has two children with a memory rank of f - 2. We apply this procedure recursively until we defined nodes U1 Ule, where each node either leaf or has two children with the same memory-rank as one another. By the definition of memory rank, this process will generate a subset that forms a (possibly non-consecutive) complete binary tree.
We now construct a family of CRQs on the original tree whose answer always equals that of the complete binary subset {ui,.. U2e J. Nodes in the subset are labeled with to, t1, tnull, as above, except we append an extra 1 to each of these vectors:
0 i
(
0
to
. ti
Emlll
0
(8)
Each node of the original tree that is not in the subset is labeled with one of the following two vectors:
6 0 or t. 0 Specifically, leaf nodes that are not the subset are labeled with t..
and non-leaf nodes are labeled with 4.. To see that the answer to this CRQ equals that of the CRQ corresponding to the balanced binary subset, it suffices to show that the vectors t4 and t_ are never
22

---

chosen over to and t at any subquestion. First, we show that t. is never chosen over to and t1. This can be seen be enumerating all the possible values that the parent (non-leaf) node can take on (to, L1, 1ull, (+) and seeing that each prefers to and t to t._. Second, f, is never even compared to to and t1, because no leaves are labeled with t...
We now define a CRQ over Ui...., U2e the same way as in the balanced binary tree case using to, t1, fmall. By construction, the depth of this synthetic tree is l mr(T), so the RNN needs memory of size mr(T).
Finally, if an RNN solves all CRQs trees of size it also solves them balanced binary trees of size n. Thus, the number of required bits in the hidden state of the RNN is (l)og())).
D Extension of the RNN solution to non-binary trees
D.1 Converting non-binary to binary trees
Suppose we have a CRQ over a tree T with n nodes and max degree k. We can transform it to an equivalent CRQ over a binary tree 7" with 2n nodes and max degree 2. By equivalent we mean that the answer to the two CRQs are the same.
The construction is as follows: Let v be some node with degree k and denote its leaves by ui....y Mg- Suppose that = 2 for some integer E. We create balanced binary tree with at most 2k nodes and depth E. The leaves will have vectors Xay..... Xu, and all the non-leaf nodes have vector equal to X,. It is easy to see that the answer to the sub-question of the root of this tree the same as the answer to the sub-question of the node from the original tree. The number of nodes is increased by a factor of at most 2. If k is not a power of 2, we can duplicate the last leaf node until the number of leaves is power of and use the same construction.
Doing this for every node increases the size of the tree by a factor of at most 2, and the resulting CRQ will have the same answer as the original CRQ.
D.2 Memory-rank for non-binary trees
In this sub-section we explain how to extend some of the results from Section 5)to non-binary trees. We first define memory-rank for general trees:
Definition D.1 (Memory Rank for non- non-binary trees). Let I = (V, E" be a rooted tree. The memory rank of a node u E V is defined recursively as: mr(v) = 0 if is a leaf. If is not a leaf, suppose it has k children denoted by uı...., Ug where mr(w1) ... mm(uk) then:
mr(v)= = max (mr(u)), + 1....,,r(un + 10-1] 1)
is straightforward to see that this definition generalizes Definition 3.3 Also, AlsorAAlooithm generalizes to Definition D.I since it has no dependence on the degree of each node.
I readily
Extending Theorem 5.4 to general trees with maximal degree of & can done in a straightforward way by having an RNN with hidden dimension of O(dk log(n)) and Olk) layers. The idea is to add for each node an additional coordinate representing its degree. Now, in the proof of Theorem 5.4 split this into k
when the last two nodes are extracted from the stack (layer 3 in the construction), layers. Each layer checks the degree of the parent node from 2 until & and for degree i extracts the last i nodes from the stack. This can be implemented by a ReLU network of depth Okk).. Finally, the node with the highest inner product to the parent is inserted back to the stack with an updated depth (similarly to layers 4 and 5 from the proof of Theorem 5.4).
We believe it is also possible to extend this construction to having depth O(1) and hidden dimension Odd log(n)) for general trees by changing the sorting algorithm. This can be done by splitting the argmax operation over inputs into k argmax operations, each over inputs, where these operations are nested. We leave this construction for future works.
23

---

E Proofs from Section
The main idea of the construction is iteratively use the self-attention layer constructed in The orem 4.1 while wrapping it with a construction that allows outputting CoT tokens in the right order.
(n) for any o J. We will use these vectors twice, and for two different use cases. The first is similar to the construction ohehrree 4.1] Namely, for each node E V that not a leaf, we set one of the vectors 2; to be corresponded with this node and denote it as Zy-
By Lemma A.1 there exist vectors 21...., Z, E [=1]41og()) such that (z,, zj) I 3 (og(n)
We also assume that the tree has a reverse BFS ordering. This means that we a standard BFS ordering of the tree, and order of node i in the reverse order is i 1. For node v, let / (t) be be its place in the reverse BFS ordering. We also correspond one of the vectors defined above to each place in this order we denote this vector Wi(e). For the root v, have [(v,)
and define w W((s)++ W1. We use a different notation for the BFS ordering to not confuse them with the other set of positional encoding, although this is the same set of vectors. It is also possible to find another set of vectors with the same property, although it won't 't matter for the construction. The embedding for leaf node u and non-leaf node defined as:
0g
0a
(P(
tu
O (og(n) WI(w)
t ==
ZP(2) Wi(e)
E R 224+0llog())+1
(9)
W
WI(s)+1
As in Theorem 4.1 all the coordinates of the positional encoding are in {+1), and the matrices that operate over these coordinates will have all their entries in {-1, 1-1,0, 0, 1}. We will first give an intuitive explanation of the embedding and how the transformer will work. The embedding first contains the vector x corresponding to the node. It also contains its own positional encoding &, if its non-leaf, and the positional encoding of its parent. Next, contains the vector representing its place in the reverse BFS ordering, as well as the subsequent vector in the order. The last coordinate is flag for whether node is leaf.
The transformer will contain 2 self-attention layers, and an MLP with 0(1) layers after each self- attention layer. The first self-attention layer and the MLP afterwards is similar the construction in Theorem 4.1 Their goal is to solve the sub-questions in the CRQ. This layer will use the z's positional encoding vectors. The second self-attention layer will make sure that the last CoT token that was created will attend to the next token corresponding to the node after it in the reverse BFS ordering. This way, each CoT token will provide answer one sub-question of the CRQ, and using the reverse BFS order we make sure that any subsequent questions will have the questions of their children already solved.
We the formal construction: Let be some constant such that ||x|| S for every d The matrices for the first self-attention layer equal to:
La
Odxd
K
Ve- T log(())
0 012 log(n) (x) log(n)
/3c/
La
0 Oaxd
Q
Vo- Ia Ilog(()
012 log(n) x12 log(n)
-ee
Odxd
la Odsed
V
la
0 0 016log(n) x 16 161ogg())+1

---

We will first show to which each token can attend to. Let v be some non-leaf node, and u child of which is leaf, and w some other node. We will show that v can only attend u:
cy K' Qt = -xx, Xa) + c ||z.|l 1| 2 4clog(n) -
t. K Qt,, = =|,,,11 + e1| - 3c - 4clog(n) 2c
t KJ Qt (X,,, x.) + (Zu,zu) zu) 3c 4clog(n) 2c
This shows that t, K Qt 2 t.K Qt, and K Qt,
: 2 t K Qtw. In particular, e will attend to its child with max (Xy, Xu), which the correct answer to the sub-question represented by e, After applying the V matrix and adding the residual connection, the to embedding of v is equal to:
Xy
Xu
Ze
(p(()
W(()
Wi
where x,, maximizes the inner product with x, over its children. The first layer of the MI.P doesn't change the input. This can be easily done with ReL.U network since a(z) a(-2) z for every z E I.
The second self-attention layer will have the following weights:
02dx20 2d
O log(()) x log(n)
I4 log(n) (og(n))11og(0)
K
O (x)()))x1)og())
22
La (og(
04 log(n) (n))
Q
Og (n) (og(n))
0 log(n) x (ng(
Oaxd
Ia Oaxed
Oaxd
V
04 Lox ( log(n)
I4 tog(n) O log(n) x4log(n)
O log(r)) (lg((n)
Ied (og(
The second MLP will again just copy the input, and we will not use the residual connection for the second layer 5
We now turn prove the correctness of the construction. The second self-attention layer forces each token v to attend to the token u with [(u) = I(x) + 1, namely the consecutive token in the reverse BFS order. The V matrix of the second self-attention layer transform the embedding of this token to be similar to that of an embedding of a node. Suppose we constructed A - CoT tokens already, and for node v. 7(v) k: By the ordering, this means that all the descendants of have being processed. Also, if have descendants that are non-leaves, then the first layer correctly solved the corresponding sub-question them, and they were outputted as CoT tokens with similar embedding to leaf node. Hence, in the current iteration, the token corresponding to e will necessarily attend the its child that solves the sub-question. In addition, the last token CoT token that was created will necessarily attend to the token corresponding to v by the construction of the second atff-attentonn layer. This means that the new CoT token will be the answer the sub-question corresponding to v, with and embedding similar to a leaf. This is true for any node v, hence the last CoT token will contain the answer to the root, which the answer to the CRQ.
token corresponding
'It is always possible to ignore the residual connection This can be done by adding zero coordinates, then use the V matrix to copy the original vector intro those added coordinates, and use another linear layer from the MLP to move back the vector to the first coordinates while removing what was added from the residual connection.
exists) by doubling the embedding dimension.
25

---

F General CRQs
In our definition of CRQs DDfinition 3.1) each sub-question is defined as the argmax over inner products. There are two main reasons for this choice: (1) The argmax function aligns well with the attention layers in transformers, allowing for simple constructions, and (2) The argmax function is flexible enough to capture many natural problems special cases, such as evaluating Boolean expressions. However, by allowing for other operations besides argmax, CRQs can be generalized to include many more tasks. We define the class of generalized CRQ problems formally below. For simplicity we only consider binary trees. (Given a CRQ over a non- con-binary tree, we can always convert it into equivalent CRQ over binary tree with at most twice many nodes; see Appendix D)
Definition F.1 A General Compositional Reasoning Question (GCRQ) is rooted binary tree T= (V, E) with root U, E V, and a set of operators fi....: ff. : RR - Rd. Each node v E V is labeled by a vector x, E Dd, and non-leaf nodes are also labeled by an operator's index bn [R:] Here I C IR is some finite vocabulary of constant size and d E N.
The answer the GCRQ defined as Alv,) where the function A is defined recursively: For a leaf u E V we define A(u) Xu. For a non-leaf node v E with children u1, u2 we define:
A(v)= = Si (x., A(un),
We refer to every node v E V which is not a leaf as a sub-question.
As concrete example, we can represent modular arithmetic problems special case of GCRQs. Let r = {0, 1, P 1} for some prime p. Let the dimension of the embedding vectors be = 1.
We define the operators: [+, f-, Sx: J+
f+ (X,, Xuz) Xu: + Xu2
f- (Xx; Xuy Xus)
Xxi Xua
fx = (x,, (X,,Xu;: Xuz) = Xu, x Xag
f= = (Xp; Xuy Xuy) = Xx, Xuz
(In this construction, the non-leaf labels x, are not used.) Clearly, any arithmetic expression can be converted into GCRQ whose tree structure matches the order of operations in the expression. Furthermore, each of the four arithmetic operators can be represented by a ReLU network. For instance. Feng et al. [024 Lemma C.5, Theorem D.1] implements them using lookup table, since the inputs come from a finite field.
All of our constructions can be adapted to work for GCRQs. Consider k operators fi..... f&. Rdd + Rdd where each operator can be implemented by a ReLU network. Note that the only place in the proofs Theorem and Theorem 6. we use the fact that the operator is argmax is where we use a single self-attention layer to calculate inner products. Instead, we can modify this attention layer so that each parent node attends to both its children, with the output being concatenation of their vectors. In more detail, assume that each two siblings ii and U2 in the tree are labeled
by vectors
Xui 0g
and
Xug Then using the positional embeddings, we can force their parent
0g
to attend to both of them with the same attention score just as in the proofs of Theorem 4. and Theorem 6.1 We also construct the MLP so that its input will include the index of the operator, én. The MLP will simulate an "if" statement over the i operators and apply the relevant one over the vectors x,, X Xuy- This "if" statement can be simulated by a k-layer ReLU network. We need to assume that i is independent of n. which is natural since the number of possible operators (e.g. 4 in arithmetic problems) is independent of the input length.
A similar construction will work for the proof of Theorem 5.4, where here the MLP will output the last two inputs from the stack and apply the operator i, Again, it will increase the depth of the MLP by k. We leave exact constructions for future work.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
26

---

Justification: Our abstract and introduction highlight the main results of each section: the definition of CRQs, the lower bounds (Theorem 4.3 Theorem 5.5), and the upper bounds Theorem 6.1).
(Theorem 4.1 Theorem 5.4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Each our theorems clearly states all assumptions. Section discusses the questions raised by our work that remain open.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Formal theorem statements include all assumptions. Proof' appear in Appen dices toto Cad
Guidelines:
The answer NA means that the paper does not include theoretical results.
27

---

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

---

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

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
No human subjects or data was used. No clear potential exists for harmful consequences.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper provides theoretical comparison of several widely-used LLM architectures. The goal is to achieve better scientific understanding of these methods. While LLMs have broad societal impacts, the results of this paper do not directly relate to this impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate
30

---

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

---

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

---

Answer: [NA]
Justification: LLMs were not used in any meaningful way.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non sta-standard components.
Please refer to our LLM policy /ttp::://neurrii cc cc//omfferences/2225/11 for what should or should not be described.
33


Reviews:
[{"review_id": "rafbpVVTkE", "reviewer": "Reviewer_71Pc", "summary": "This paper introduces a formal problem class called Compositional Reasoning Questions (CRQs) to analyze the expressive power of different neural architectures. CRQs are problems with a tree-like structure, such as Boolean formula evaluation, that require multi-step, compositional reasoning. The authors theoretically compare the capabilities of transformers, RNNs, and transformers with chain of thought (CoT) on this task. They prove a series of complementary results showing that no single architecture is strictly best. Instead, there are fundamental trade-offs: deep transformers can solve CRQs in parallel but require depth that scales with the CRQ's tree depth; RNNs can solve them with constant depth but require a specific input ordering and a hidden state size that scales logarithmically; and constant-depth transformers with CoT can also solve them, but require a number of thought tokens that is linear in the problem size.", "questions": "* The constructions presented are elegant proofs of expressiveness, but they rely on very specific, pre-designed components like the tree-aware positional encodings for the transformer and the memory-rank sorting for the RNN. Do you have any intuition on whether these mechanisms, or functionally equivalent ones, could be learned by these architectures from data, or do you view these results as primarily characterizing the limits of what a pre-programmed network can do?\n* Your analysis uses a hardmax attention function. How do you expect your positive results (the constructions) to change if using a standard softmax? Could a low-temperature softmax approximate the hardmax behavior, perhaps at the cost of requiring higher precision, or would it fundamentally break the constructions?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\n* The primary strength of this paper is its novel and insightful comparison of major neural architectures on a single, well-defined class of problems.\n* The introduction of Compositional Reasoning Questions (CRQs) provides a simple yet powerful framework for studying an essential capability of language models: multi-step, hierarchical reasoning. By proving that this problem is NC¹-hard, the paper grounds the analysis in established complexity theory, providing a solid foundation for its claims.\n* The theoretical analysis is rigorous and comprehensive. I appreciate that the authors provide both positive results (constructions showing how a model can solve the task) and negative results (conditional lower bounds showing what a model cannot do) for each architecture. This dual approach gives a much more complete picture of each model's capabilities and limitations. The summary of these trade-offs in Table 1 is particularly effective.\n* The paper is exceptionally well-written. The motivation is clear, the CRQ problem is defined precisely, and the main results are stated upfront and then elaborated on in dedicated sections. The comparison with related work, especially Feng et al. [2024], is sharp and clearly articulates this paper's distinct contributions.\n* While the proof techniques themselves (e.g., reductions from circuit complexity, communication complexity arguments) build on prior work, their application to the novel CRQ framework to draw a three-way comparison between transformers, RNNs, and CoT is highly original. The resulting insights into the architectural trade-offs feel new and important.\n\nWeakness:\n* The main weakness lies in the gap between expressiveness and practical learnability. The constructions for solving CRQs rely on highly engineered mechanisms, such as specific positional encodings that perfectly capture the tree structure or a presorted input sequence for the RNN. It is an open question whether these solutions can be learned via standard gradient-based optimization, a limitation the authors rightfully point out in their future work section.\n* The analysis uses a hardmax attention mechanism and assumes finite precision, which are standard in theoretical analyses but differ from the softmax attention used in practice. A brief discussion on how these results might translate to the standard setting would have been beneficial.\n\nOverall, the strengths far outweigh the weaknesses. This is a strong theoretical paper that makes a significant contribution to our understanding of the fundamental capabilities of different language model architectures.", "was_revised": true, "final_justification": "After reviewing the full discussion, I am maintaining my recommendation to Accept.\n\nResolved Issues: The authors gave solid answers to the technical questions, effectively clarifying the path from hardmax to softmax attention and the reasoning for their lower-bound assumptions.\n\nUnresolved Issues: The main unresolved point, shared by other reviewers, is the lack of experiments. The paper proves what architectures can express, but not what they can learn.\n\nJustification: For me, the paper's theoretical contributions are strong enough to stand on their own. The CRQ framework is a novel tool for analysis, and the rigorous comparison of architectures offers genuinely new insights into their fundamental trade-offs. In my view, the value of this foundational work is high enough to recommend acceptance.", "rebuttal": "We thank the reviewer for their thorough and positive review.\n\n**Weaknesses:**\n\n- We agree with the reviewer and acknowledge that our theoretical analysis assumes a specific, benevolent format for the input. We consider the tree-aware positional encodings (and, for the RNN result, the input order) to be constructed in a preprocessing phase that assembles the input. We conjecture that these structures can be learned using the early layers of a transformer, and it would be an interesting question for future work to confirm this experimentally. Different problems can encode tree structure in various ways that each requires different preprocessing steps; for instance, arithmetic formulas use parentheses, while natural language does not. Studying the general framework of CRQ problems allows us to abstract away the specific input format and focus on what we see as the more mathematically interesting part: the compositional structure itself.\n\n- We use hardmax attention for ease of analysis, following previous work like [1]. However, all our constructions can be extended to softmax. We would need to change the guarantees to say that we can approximate the target function up to an arbitrarily small error $\\epsilon > 0$ that is independent of $n$, rather than exactly expressing it. To give a concrete example of how this extension can be achieved, take Theorem 4.1. We use the hardmax assumption in lines 552-556 of the proof, which describes the token we want to attend to in each layer. By the definition of the softmax function, if we want 99.99% of the attention to go to the desired token, it should have an attention score that is greater by $\\Omega(\\log(n))$ than any of the other n tokens’ attention scores. As you can see in lines 558 - 559 this already holds for some layers, and by adjusting our constants, it can be made to hold for the other layers too (line 562). In fact, since error accumulates across layers, we need $(1 - \\epsilon/L)$ of the attention to go to the desired token to have final error epsilon, but since $L = \\log(n)$ and epsilon is constant with respect to n, this also already holds. Thus, even a low temperature softmax suffices. This is a good point and we will add this as a remark in the final version. We should also point out that, as in other theoretical studies of attention, we don’t assume finite precision but allow the precision to grow as $\\log(n)$ (see lines 174 and 188).\n\n**Questions:**\n\n- Although our theoretical analysis takes these mechanisms for granted, we believe they (or something similar) can be learned. This is supported by previous works on mechanistic interpretability, e.g. [2] where the model learns addition of natural numbers as multiplication of complex numbers, and [3] where the transformers with CoT solve arithmetic problems. These are not exactly the structures we look into, but this line of work provides evidence that transformers can learn to parse and process inputs with complex structures. Further empirical study is a very interesting future direction.\n\n- See the answer above.\n\n[1] Merrill, William and Ashish Sabharwal. “A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers,” 2025.\n\n[2] Nanda, Neel, et al. \"Progress measures for grokking via mechanistic interpretability,\" 2023.\n\n[3] Feng, Guhao, et al. \"Towards revealing the mystery behind chain of thought: a theoretical perspective,\" 2023."}, {"review_id": "7acwKIJvBJ", "reviewer": "Reviewer_GoH5", "summary": "The paper provides theoretical analysis of transformers and RNNs in solving a subset of reasoning tasks which the authors named as Compositional Reasoning Question. The analysis shows some interesting insights but the proof is only for the ideal case and without experimental support.", "questions": "None", "limitations": "None", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper is in general written clearly with easy to follow usage of math notations.\n2. The paper shares some insights on the theoretical grounding of transformer and RNN's ability to solve reasoning tasks that can be structured as binary trees. The paper illustrates why CoT can allow shallower transformer to generalize for the reasoning task.\nWeakness:\n1. Some statements are not substantiated. e.g. Line 168 \"(though the lower bounds generally hold against models that\ninclude them)\". The authors also didn't explain why they pick transformers with single attention head that uses hardmax rather than softmax (presumably to simplify the proof?). \n2. The proof seems to be only for the ideal case. For example, the authors \"use a different input format that encodes the tree structure directly into the positional encodings,\" but this in reality when the reasoning problem is natural language based and fuzzy, how well can the proof be extended to those cases?\n3. While this is more of a theoretical paper, I think some experimental evidence such as results on some reasoning datasets will strength the paper more.", "was_revised": true, "final_justification": "I will maintain my rating as I still think the proposed analysis only targets a narrow set of compositional reasoning problems and experimental results are not provided.", "rebuttal": "We thank the reviewer for the thorough review.\n\n**Weaknesses:**\n\n- The review mentions line 168: “For simplicity, we do not use layer normalization or attention masking [when defining transformers] though the lower bounds generally hold against models that include them.” The lower bound in question is Theorem 4.3, which is a consequence of the fact that constant-depth transformers cannot solve tasks that are $NC^1$ complete (e.g., in [1]). But in [1], this fact was proven even for transformers that do have layer normalization and attention masking. Thus, our proof of Theorem 4.3 holds even without our simplifying assumption. This is a good point, and we will clarify it and add it to the theorem. The other lower bounds in Section 5 are about RNNs and do not concern the transformer architecture. If there are other claims that the reviewer thinks could be justified better, we are happy to do so.\n\n   Regarding the question of softmax versus hardmax, we indeed used the hardmax function for ease of analysis, as in previous work (e.g., [2]). However, our construction can be extended to use softmax instead of hardmax. We would need to change the guarantees to say that we can approximate the target function up to an arbitrarily small error $\\epsilon > 0$ that is independent of n, rather than exactly expressing it. To give a concrete example of how this extension can be achieved, take Theorem 4.1. We use the hardmax assumption in lines 552-556 of the proof, which describes the token we want to attend to in each layer. By the definition of the softmax function, if we want 99.99% of the attention to go to the desired token, it should have an attention score that is greater by $\\Omega(\\log(n))$ than any of the other n tokens’ attention scores. As you can see in lines 558 - 559 this already holds for some layers, and by adjusting our constants it can be made to hold for the other layers too (line 562). In fact, since error accumulates across layers, we need $(1 - \\epsilon/L)$ of the attention to go to the desired token to have final error epsilon, but since $L = \\log(n)$ and epsilon is constant with respect to n, this also already holds. Thus, even a low temperature softmax suffices. This is a good point and we will add this as a remark in the final version. We should also point out that, as in other theoretical studies of attention, we don’t assume finite precision but allow the precision to grow as log n (see lines 174 and 188).\n\n\n- We acknowledge that, as in comparable theoretical work, we study an idealized task and make simplifying assumptions about components such as the input format. These simplifications only strengthen our lower bounds. **Even if** a benevolent input format is used, the models will still fail because their architectures are inherently limited. We consider the tree-aware positional encodings (and, for the RNN result, the input order) to be constructed in a preprocessing phase that assembles the input. We conjecture that these structures can be learned using the early layers of a transformer, and it would be an interesting question for future work to confirm this experimentally. Different problems can encode tree structure in various ways that each require different preprocessing steps; for instance, arithmetic formulas use parentheses, while natural language does not. Studying the general framework of CRQ problems allows us to abstract away the specific input format and focus on what we see as the more mathematically interesting part: the compositional structure itself.\n\n- As discussed in Section 7, we acknowledge that our upper bounds do not in themselves demonstrate what functions these architectures can learn, only what functions they can represent. Still, we believe that our upper bounds capture the actual abilities of these architectures to solve CRQs, especially given that findings from comparable theoretical studies like [1] and [3] do hold up in experiments. Moreover, we believe there is value in understanding the fundamental capabilities of these architectures, divorced from the training algorithm. Finally, while it would be valuable to compare the three architectures on downstream reasoning tasks or other benchmarks, we scope our paper only to CRQs. We believe CRQs provide a clean way to explain aspects of these architectures’ ability to reason at scale that are not captured in the literature.\n\n\n[1] W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. 2023\n\n[2] Merrill, William and Ashish Sabharwal. “A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers,” 2025.\n\n[3] Feng, Guhao, et al. \"Towards revealing the mystery behind chain of thought: a theoretical perspective,\" 2023."}, {"review_id": "DCa4WwmZRP", "reviewer": "Reviewer_ruzm", "summary": "This paper inspects RNNs, Deep Transformers, and shallow Transformers with CoT tokens in the context of Compositional Reasoning Questions (CRQ).\n\nCRQs are defined as a tree representation of a complex question with each sub question being a child node. Each node as a vectorial representation.\n\nThe authors show that transformers with depth $L$ can solve all CRQs of depth up to $L$; RNNs with O(log n) hidden dimension and constant depth can solve all CRQs of size $n$; and transformers with O(n) CoT tokens can solve all CRQs of size $n$.", "questions": "In Table 1, the caption says that “_Each architecture minimizes one kind of resource at the expense of the others_”, however, in the RNN row, the minimal resource is the number of parameters (with O(log n)), similar to the CoT row;  and not the runtime ( with O(n . log n)) like what is highlighted in green in the table.\nThe caption is somewhat confusing, it could maybe be rephrased to something like “_each ressource has an architecture that will minimize its usage_”?", "limitations": "No societal impact as this is theoretical work. The main limitation of this work is the lack of experiments and experimental analysis.", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 1, "strengths_and_weaknesses": "## Strengths\n\nThis paper provides theoretical analysis to better understand the representation capacity of Transformers, RNNs, and Transformers with CoT tokens.\n\nThis is an important research topic to better understand and interpret Transformer architectures.\n\n\n## Weaknesses\n\n1. The paper provides theorems, proofs, and intuitions, but no experiments to validate the work. Experiments with Transformers and RNNs of a given size must be run on problems of small to large sizes to validate all the theory presented in this work.\n\n2. CRQs are defined in the paper but no dataset is presented as examples. Presenting and releasing a dataset that follows the CRQ principles would greatly improve the quality of this work. As an example of an already existing reasoning Q&A dataset that follows a graph structure, the authors can have a look at CLUTRR by Sinha et. al, 2019 which evaluates RNNs and Transformers like this paper.\n\n3. The distinction between Transformers and Transformers with CoT tokens is not clearly motivated. These are the exact same model architecture. The only difference is the number of input / output tokens. Given that the paper is motivated by exploring the strengths and weaknesses of neural network **architectures** for a class of problems; I would encourage further discussion why this split is necessary.", "was_revised": true, "final_justification": "The paper does not provide any experimental validation of the theory proposed and authors did not express any interest in adding some during the rebutal.\nIn addition, when asked to clarify the problem this paper tackles by providing examples, the authors also declined to do so because it is a ``paradigmatic reasoning problem''. As such, it is personally hard for me to recommend this work.", "rebuttal": "We thank the reviewer for the thorough review.\n\n**Weaknesses**\n\n1) As discussed in Section 7, we acknowledge that our upper bounds do not in themselves demonstrate what functions these architectures can learn, only what functions they can represent. It would be valuable for experimentalists to validate that the scaling rules predicted by our upper bounds hold in practice. However, we think that our theoretical analysis is already a valuable contribution to the literature on transformers and RNN representational capacity. First, our lower bounds apply regardless of the training methodology used in practice. Second, proving results like ours for a particular, well-defined task guides experiments by providing clean, controlled, easily-testable hypotheses. Finally, we are interested in the capabilities not just of today’s frontier models, but of architectures and problem sizes that are too large to experiment with currently. For those settings, asymptotic analysis is essential. For these reasons, approximation theory has been an important subfield of machine learning for decades.\n\n2) The review asks us to identify a real-world example of a CRQ problem. As we prove, CRQ is a generalization of Boolean formula evaluation. All of our results — both our constructions (upper bounds) and impossibility results (lower bounds) apply even if we restrict ourselves to this task. We believe that Boolean formula evaluation is a paradigmatic reasoning problem. Just as related work has used problems like graph connectivity, recognizing regular languages, and arithmetic to examine the capabilities and limitations of reasoning models, we use Boolean formula evaluation. Moreover, the CRQ framework allows us to provide a unified analysis of other problems that share the compositional structure of Boolean formulas. Our focus is not on the outward form of the problems, which differentiates them from one another, but on the deeper properties that unite them. We see this as a strength of the paper. The CLUTRR task is a great example, and we will add a reference to it in the introduction; thank you for pointing it out to us. However, it is not a goal of this paper to devise new benchmarks with compositional structure; we believe that existing tasks like Boolean formula evaluation provide plenty of motivation for studying this kind of reasoning.\n\n3) The review asks why we differentiate between different types of transformers, particularly why we refer to them as being different “architectures”. The reviewer suggests that these are all examples of one architecture, just with different hyperparameters. However, our paper is part of a line of work showing that hyperparameters like the number of layers and number of chain of thought tokens can have a major, qualitative impact on the model’s power. Thus, when describing a neural network architecture, it does not suffice to say “we used a transformer” or even “let’s add chain of thought prompting to our transformer”. For the types of problems we study, it is essential to specify the number of layers in the transformer and the number of chain of thought tokens we allow, relative to the size of the inputs. Our paper considers four types of transformers: (1) constant depth transformers without chain of thought, (2) constant depth transformers with logarithmic chain of thought, (3) log depth transformers without chain of thought, and (4) constant depth transformers with linear chain of thought. We show that these models are qualitatively different in that (1) and (2) cannot solve CRQs, while (3) and (4) can. Furthermore, (3) and (4) use resources very differently, as shown in Table 1. Thus, while all four of them are transformers, it is fruitful to think of them as if they were distinct architectures. We acknowledge that this use of the term “architecture” may be counterintuitive, and we will add a clarification in the introduction.\n\n**Questions:**\n\n- The review is correct in its interpretation of the table. It shows that, for each resource, there is a particular architecture that minimizes its use, and furthermore, that no single architecture is best for more than one resource. Thus, when you select one of the architectures, you are effectively prioritizing one resource at the expense of the others. In the table, it means that each architecture (row) minimizes one resource (column). For example, RNNs minimize the runtime, which is quadratic for transformers with and without CoT, and almost linear for RNNs."}, {"review_id": "3t1FgZzcDz", "reviewer": "Reviewer_u4qx", "summary": "The paper investigates the expressive power of transformers, recurrent neural networks (RNNs) and transformers with chain of thought (CoT) for Compositional Reasoning Questions --- which they formally define as tree structured hierarchical problems. They investigate the trade-offs between the number of nodes and depth of a CRQ, and the architecture requirements (number of parameters, runtime and parallel-runtime) for Transformers, RNNs and CoT.  They provide the following results:\n\n1. The provide a sufficiency criterion on a Transformer's depth, embedding dimension for solving a CRQ (Theorem 4.1)\n\n2. Any constant‑depth transformer, no matter how wide, fails on some CRQs unless (TC^{0} \\neq NC^{1}).\n\n3. Role of ordering of the nodes of a CRQ on the size of RNNs hidden dimensions required to solve the task.\n\n4. They show that under correct ordering of nodes, shallow RNNs can solve CRQs\n\n5. They show that a 2-layer transformer (with CRQ size dependent embedding sizes and precision) with CoT can solve CRQs.", "questions": "Q1. Do you think that your results provide any meaningful guidance to practitioners for specific applications? If yes, then such applications should be highlighted.\n\nQ2. I am not a circuit complexity expert, but why is the result of Thm 4.3 conditional on TC$^{0} \\neq NC^{1}$, when you seem to have a clear counter example (line 239)?\n\nQ3. Are CRQs generalization/restriction of some other problems investigated in theoretical CS?", "limitations": "There is no discussion of limitations. And I think some discussion of the sort should be there, as at the moment I do not see why the results are relevant to any potential application or how are they connected to other natural problems investigated in Theoretical CS.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "S1[Originality]. A key strength of the paper is the formalization CRQs as a well-defined compositional task (although, I am slightly ambivalent on this, also check W3).\n\nS2[Clarity and Quality]. Quite intuitive and natural results that are presented in a well-structured format. The paper clearly outlines the necessary and sufficient conditions for Transformers and RNNs to express CRQs. I think fair amount of intuition is provided for the results. I did not check the proofs in the appendix. \n\nW3 [Significance]  Although I appreciate the CRQ formalization and the presented results. I am not sure that the paper's results actually motivate any guidance for practitioners, or explain any observed behavior in transformer design. Furthermore, the problem does not have a very natural motivation and the proof ideas (at least as discussed in the paper) do not seem to be of major impact on other areas.", "was_revised": true, "final_justification": "**Reasons for maintaining the score:**\nAfter seeing the reviews from other reviewers and the author's rebuttal. I still believe that the paper can be interesting for the community studying expressivity of transformers. Hence, I will maintain my score.\n\n**Reasons for not upgrading:**\nThe authors have attempted to address my questions and concerns regarding the naturalness and practical motivation of the investigated problem. However, even after reading their response, I remain unconvinced. I believe that the motivation behind the work is still not clear, and this concern appears to be shared by other reviewers as well.", "rebuttal": "We thank the reviewer for the thorough and positive review.\n\n\n**W3 + Q1:** Thank you for raising this point. We acknowledge that we could have better framed the larger stakes of this problem and the takeaways of our results for practitioners and others working outside the field of representational capacity. Let us explain a bit more about our broader motivation for studying this problem.\n\nTransformer LLMs have proved to be surprisingly good at reasoning, especially on small problems, but still have obvious limitations. Experimental and theoretical analysis agree that they struggle, especially as the problems become larger and computationally harder. There are several competing trends or schools of thought about how to overcome these limitations:\n1) Trust the scaling laws. Grow the size of the transformer by stacking more layers, and greater capacities will continue to emerge.\n\n2) Devise better architectures, such as state space or hybrid models, because attention is not all you need. Improving the architecture will make it easier to learn and perform certain kinds of computations efficiently. \n\n3) Introduce test-time scaling using chain of thought or related reasoning-style generation. Even after fixing the architecture, model size, dataset size, etc., we can squeeze out much better reasoning performance by opening up this whole new axis of the design space.\n\nNow each of these schools have received theoretical support to some extent. For instance, [1,2,3] support school #1 by showing the power of log-depth transformers. Work on state tracking tasks like recognizing regular languages and composing permutations [4] supports school #2. And recent work on the power of chain of thought [5,6] supports school #3. Each school has some claim on being the best way to improve reasoning, because they are using different theoretical rulers. For instance, if the kind of reasoning you care about most resembles state tracking, then RNNs are a natural choice and everything else will look wasteful. Whereas, if your paradigm of reasoning is dynamic programming or simulating Turing machines, then chain of thought clearly looks like the most promising path. On the third hand, for k-hop induction or graph-based reasoning problems, transformers win out.\n\nBut each of these theoretical measuring sticks is limited, and may not yield very general insights. For example, we believe compositional reasoning is fundamentally important, but it doesn’t fall neatly into any of these categories. It is not a state tracking task, because it requires logarithmic writable memory. It is computationally much easier than simulating a Turing machine or doing dynamic programming. It is not parallelizable enough to be solved in O(1) rounds, but is still computationally easy compared to even one layer of quadratic attention (the same may be true for certain graph problems).\n\nSo our conclusion is that none of these three schools is in the goldilocks zone. Using CRQ as a measuring stick, none is a clear winner and none is a clear loser. So we should not place all our hopes in any one of them. As table 1 shows, the best choice may depend on what resource you decide you want to optimize. Perhaps it is some blend of all three schools, or a fourth paradigm that hasn’t been developed yet. While these conclusions may not immediately change the best practices for downstream applications, we think they will help guide researchers as they address the grand challenge of improving reasoning. \n\n**Q2:** We apologize for the confusing phrasing. What we meant here is that under the assumption of $TC^0 \\neq NC^1$, no transformer with a constant depth (independent of $n$) can solve all CRQs. The example we give of a balanced binary tree is a particular type of CRQ for which an input of size $n$ corresponds to a tree of depth $\\log(n)$. Even limiting ourselves to these balanced binary CRQs, no transformer with constant depth can solve all CRQs of this type. (Of course, our log-depth construction from Theorem 4.1 solves *all* CRQs, including this type as a special case.)  Without the assumption that $TC^0 \\neq NC^1$, our proof would break and it would be unknown whether there is a constant size transformer that solves all CRQs (although the CS community mostly believes this assumption to be true, similar to the assumption that $P \\neq NP$).\n\n**Q3:** Yes, CRQs are both a restriction and a generalization of important classes of problems from theoretical CS. Most prominently, Boolean formula evaluation is a special case of CRQ, a fact that we prove in Appendix A.2 as part of the proof of Theorem 4.3. Boolean formula evaluation is fundamental in computer science and has received particular attention in circuit complexity A closely related and natural problem is evaluation of arithmetic expressions mod p. We explain the connection of this problem to CRQs in Appendix F. The advantage of studying CRQs is that it captures several problems with common mathematical structure in a single framework for a unified analysis. In addition, CRQs can be understood as lying in a special class of problems that are simultaneously $NC^1$-hard and require logarithmic space. Previous work has compared LLM architectures through the lenses of state tracking and parallelism. State tracking tasks are naturally solved by RNNs and are difficult for transformers (Merrill, Petty, Sabharwal) , while highly parallel tasks are the reverse (Stanford, Hsu, Telgarsky). CRQs occupy a theoretically interesting middle ground: they are not fully parallelizable, because they are $NC^1$-hard (Theorem 4.1), but they are also not state tracking tasks, because they require $\\log(n)$-size memory that finite state machines lack (Theorem 5.5). However, CRQs are *somewhat* parallelizable and *nearly* memoryless. Perhaps this can be summarized by saying that CRQs lie in a class of problems that are “inherently compositional”.\n\n**Limitations:**\nWe include a brief discussion of the limitations of our work in Section 7, but we would be happy to expand this discussion to better contextualize our results according to the advice of the reviewers.\n\n[1] Merrill and Sabharwal, “A Little Depth Goes a Long Way”, 2025\n\n[2] Stanford, Hsu, and Telgarsky, “Transformers, parallel computation, and logarithmic depth”, 2024\n\n[3] Stanford, Hsu, and Telgarsky, “Representational strengths and limitations of transformers”, 2023\n\n[4] Merrill, Petty, and Sabharwal, “The Illusion of State in State Space Models”, 2024\n\n[5] G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and L. Wang. “Towards revealing the mystery behind chain of thought: a theoretical perspective”, 2023\n\n[6] Merrill and Sabharwal, “The expressive power of transformers with chain of thought”, 2023"}]

Author rebuttal:

Meta-review: This paper analyses the expressive power of different neural architectures—Transformers, RNNs, and Transformers with Chain of Thought (CoT)—on a class of problems termed Compositional Reasoning Questions (CRQs). 
The reviewers are in consensus about several key strengths:

The introduction of the CRQ framework to compare the expressive powers of different architectures is an interesting approach, providing a formal basis for studying compositional reasoning. The theoretical analysis offers both upper and lower bounds for each architecture and grounding the work in established complexity theory. The comparison highlights fundamental trade-offs in resource usage (e.g., depth vs. sequence length vs. hidden state size).
The paper is overall well written with a well-defined problem, a clear description of the theoretical results, and a thorough discussion with related work.

Although the reviewers primarily concerned lack of experimental validation. The theoretical contributions are strong enough to stand on their own. The work is technically solid and provides insightful comparisons that contribute to our understanding of the fundamental capabilities of the models for compositional reasoning. Therefore, despite the lack of experiments, it can lead to future theoretical investigations into the compositional reasoning abilities of deep networks. Therefore, I recommend acceptance.
Decision: Accept (poster)