Ehrenfeucht-Haussler Rank and Chain of Thought
Authors: Pablo Barcelo
Alexander Kozachinskiy
Tomasz Steifer
Venue: ICML 2025 poster (2025)
Keywords: Transformers
chain of thought
decision tree rank
composition of functions
Primary area: theory->learning_theory
TL;DR: We show that the minimal number of chain-of-thought iterations (for 1-layer hardmax transformers), needed to compute a function, is equal to the rank of that function.

Abstract: The notion of _rank_ of a Boolean function has been a cornerstone in PAC learning, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function $f$ corresponds to the minimum number of _Chain of Thought_ (CoT) steps required by a single-layer Transformer with hard attention to compute $f$. Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that $\ell$-fold function composition necessitates exactly $\ell$ CoT steps. Furthermore, we analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.

Ehrenfeucht-Haussle Rank and Chain of Thought
Pablo Barceló * 123 Alexander Kozachinskiy
Tomasz Steifer
Abstract
Transformer architecture (Vaswani al., 2017), which has recently revolutionized the field of NLP and facilitated the development of LLMs. In essence, we show that the rank of function f corresponds to the minimum number of Chain of Thought (Co'T) steps required by a single-layer Trans- former to compute f. The Transformers used in our char- acterization are based on the hard attention mechanism theoretical abstraction of the soft attention mechanism em- ployed in practice. Hard attention has been widely used in theoretical studies (Hahn, 2020b; Hao et al., 2022b; Barceló et al., 2024; Yang et al., 2024) due to its amenability to formal analysis, while still effectively capturing the essence of practical models (Clark et al., 2019; Voita et al., 2019).
The notion of rank of a Boolean function has been comnersoone in PAC learning, enabling quasipolynomial-ting learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function corresponds to the minimum number of Chain of Thought (CoT) steps required by a single-layer Transformer with hard attention to compute f. Based this charac- terization we establish tight bounds on the number of CoT steps required for specific problems, show- ing that é-fold function composition necessitates exactly CoT steps. Furthermore, we analyze the problem of identifying the position of the k-thh occurrence of in Boolean sequence, proving that requires k CoT steps.
The Transformer architecture built upon attention layers and decoder. An attention layer performs attention on the input sequence, mapping sequence of input vectors to another sequence of vectors of the same length. Atten- tion layers are used to generate vector representations of sentences in natural language. However, a more common application of Transformers is sequence generation, where the input sequence is mapped an unbounded sequence of output vectors, generated iteratively, one at time. This task is carried out by the decoder. In the first iteration, the decoder processes the input sequence through the attention layers and outputs the vector in the last position. This output is then appended to the input sequence. During subsequent iterations, the decoder applics its attention layers to the ex- tended sequence, computes the next output, and appends to the sequence. These are the CoT steps mentioned earlier (Merrill & Sabharwal, 2024; Liu et al., 2024).
1. Introduction
Ehrenfeucht & Haussler introduced the notion of the rank of a Boolean function and showed that, for any constant r, the class of Boolean functions with rank at most r is properly PAC-learnable in polynomial time. As a corollary, they derived their renowned quasipolynomial-ime PAC-learning algorithm for polynomial-siee size decision trees. Pudlák & Impagliazzo further characterized the rank-not only for Boolean functions but also for Boolean relations through Prover-Delayer games. Since its introduction, this concept has played a significant role in proof complexity (Kullmann, 1999; Esteban & Torán, 2003).
Below we summarize our main results:
In this paper, we present new characterization of the notion of rank. Surprisingly, this characterization is grounded in the
We show that the rank of function f. denoted by rk(f), is the minimal number of iterations of single- layer decoder with one hard-attention head that com- putes f. We establish our result not only for Boolean functions, generalizing the notion of the rank to the non-Boolean case (as far we know, for the first time).
"qqual contribution 'Institute for Mathematical and Com- putational Engincering, Pontifical Catholic University Chile "Millennium Institute for Foundational Research on Data (IMFD Chile) "National Center for Artificial Intelligence (CENIA Chile) 'Intiittee of Fundamental Technological Research, Polish Academy of Sciences. Correspondence to: Alexander Kozachin- skiy
In practice, Transformers are equipped with multiple attention heads, which enhance their computational capabilities. We show that the ability of such Trans- formers to compute functions can also characterized using the notion of rank. Specifically, we define the
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Chrenfeucht-Haushhe Rank and Chain of Thought
H-head rank of function f. denoted as rk rk(4) for
based on hard attention with an unbounded number of it- erations are capable of computing any decidable language (with the parameters of the decoder not depending on the imput length). Afterwards, the computation power of de- coders with polynomially many iterations was addressed. Merrill & Sabharwal have shown that in the uniform-regime (when, as in (Pérez et al., 2021), parameters do not depend on the input length), such decoders with constant number of layers and softmax attention are capable of computing any polynomial-time language. Similarly, for the non-uniform regime, (Liuu et al., 2024) have shown that such decoders are capable of computing any language recognizable by a polynomial -ize family of Boolean circuits.
2 1. We prove that rk rk()) (f) equals the minimum number of iterations required by a single-layer decoder with H hard-attention heads to compute f.
We then explore methods for obtaining tight bounds the multi-head rank. We begin by observing that rk (f) is at most a factor of H smaller than rk())- While computing rk(f) is typically straightforward, it does not always provide an accurate bound for (f). To address this limitation, we propose a general communication complexity lower bound for (f). Using this technique, we derive a tight bound the H-head rank for the t-fold iterated com- position, a function whose complexity has been pre- viously studied for single-layer decoders with soft at- tention (Peng et al., 2024). The function t-Comp takes as input a sequence of n integers from (1..... n²), in- terpreted as the values of a function Φ: (1...., m > [1...., n). The output of t-Comp is the value of o. composed with itself I times, evaluated 1.
Our result is the first exact characterization of the expres- sive power of decoders with a given fixed number of itera- tions, although just for single layer and for hard attention. Recently, Peng et al. have shown that any single-layer de- coder with soft attention requires (2(t) iterations to compute (-Comp for / = /n/(dflp) where n is the input length, d is the dimension of vectors, H is the number of attention heads, and p is the number of bits of precision. We point out that our results instead do not require any assumptions the dimension and the number of bits of precision.
It is easy to see that rk(t-Comp) S t for any input length n. A decoder, establishing this upper bound works by computing (11) in the first iteration, then (()(1)) in the second iteration, and so on. We prove that this is optimal even if we increase the number of attention heads. Namely, for any H, we show that rk (H) (t-Comp = for all large enough input lengths.
Organization of the paper. An introduction decision trees and the notion of rank is found in Section 2, with basic concepts of Transformers being discussed in Section 3. The main results about single-head Transformers are presented in Section 4, with extensions to multi-head Transformers covered in Section 5, Final remarks are given in Scction 6. Missing proofs can be found in the arXiv version of this paper.
Finally, we study the k-thOne function. This function takes as input a Boolean sequence of length n, and it returns the position of the k-th one in it. is easy to see that rk(k-thOne) S k for any input length. In terms of decoders, in the first iteration we can compute the position of the first one, then of the second one in the second iteration, and so on. We prove that for any H and for large enough n, we have rk (f) (k-thOne) = k. showing that even increasing the number of attention heads we cannot improve upon the trivial solution for large enough input lengths. Interestingly, this result cannot be obtained via the communication complexity techniques used for iterated composition. Instead, our proof relies on purely combinatorial argument.
2. Decision Trees and Rank
Consider n + finite sets Ei...., E,,, O, for n >> 0. We are interested in decision trees that compute functions:
Σ₁ x
E, +
To do this, we consider decision trees over arbitrary families of queries, where a query is a function q whose domain is Σg x x... x En. We write Im(q) for the image of query Q. If F a set of queries, a decision tree over J is rooted tree T such that:
Related work. Numerous studies have sought to explore the expressive power of Transformers by treating them as a computational model and investigating what they can com- pute (Hahn, 2020a: Pérez et al., 2021; Hao et al., 2022a; Angluin et al., 2023; Chiang et al., 2023; Merrill & Sab- harwal, 2023; Barceló et al., 2024; Merrill & Sabharwal, 2024; Liu et al., 2024; Yang & Chiang, 2024; Peng et al., 2024). In particular, several works have investigated how the capability of decoders depends on the number of iter- ations. To start with, Pérez et al. showed that decoders
Every non-leaf node v is labeled by some query qu E FF and has exactly [Im(g.)) out-going edges, each one of them labeled by different element from Im(g.).
Every leaf & is labeled by some element of E O..
Given an input き = (aI..... on) E Σ₁ x... x En, the output of decision tree T on w computed by descending
2

---

Sarenfeucht-Hausshee Rank and Chain of Thought
from the root to one of the leaves. At each intermediate non- leaf node v, the tree computes the value qo (1) E Im(ge) and descends to the unique child of that is linked to v through an edge labeled g(w). In this way, we reach some leaf f, where 7 outputs the element Og as its result on w. We denote this output as T(w).
r(i) ()), for each j 1,.... |A|. Imagine that we do not know w, and we start asking person who knows v questions: "is the i1 letter of w equal to 0 o1?", 'is the i2-th letter of te equal to oz?", and so on. We stop once we receive the first YES answer. If this happens at the kth step, we return 9+ ( = (ūg,
The function Σ1 X ... En + +Oss computed by T. if T(w)= = f(w) for every input wi E E1 x... En.
We define the rank of an arbitrary function f Σn ... Mn + O in terms of the class of decision trees over assign- ment queries that compute f.
Boolean case. Decision trees are often defined for Boolean functions, i.c., functions of the form f: {0, 1)"h {0. 13. In our notation, this corresponds to the case Σ1 = = Σn = O = {0, 13. Boolean decision trees are deci- sion trees over a family (Pi,.... Pn) of queries, where for i = I,...,. n the function p.: {0, 13"h + {0, 13 is defined as follows on imput (b) (b1....,bb, b,) E {0, 13"::
Definition 2.1. Let f Σ1 x... En O. We define
rk(J) as the minimal depth of a decision tree over a-queries that computes f.
As we show below, the notion of rank we have just intro- duced for arbitrary functions aligns, in the case of Boolean functions, with the definition we previously provided for that class of functions.
bn)) bi-
Proposition 2.2. For any Boolean function f : [0,1)² + [0,1}; its rank, as defined by Ehrenfeucht and Haussler, equal to rk(f)-
That is, at every node, a Boolean decision tree queries the value of some coordinate of the input.
Ehrenfeucht & Haussler defined the rank of Boolean deci- sion tree T by inductively defining the rank of its nodes as follows:
An example: Iterated composition We consider the it- erated composition function. We use a notation [n] = n. for n E N. For positive integer numbers ł, n. we define:
the rank of leaf is 0, and
t-Comp, [n]" - [n], t-Comp,, (f(1)....., - f( f(((...f()) f()))
the rank of a non-leaf v, whose two children have ranks ro. rı, is maxfmin r + 1, max(ro.ri))
The rank of T is then the rank of its root, and the rank of a Boolean function f: {0, 13" + {0, 13 is the minimum rank of Boolean decision tree that computes f.
A clarification for the second line: an input to 1-Comp,, is an n-length word, where every letter is number from 1 to n. This input is interpreted as a function f: [n]] - [n)]. with (11) being the first letter of the word,
((2) being the second letter of the word, and so on. Sometimes, we also use the following notation:
Rank in the non-boolean case and a-queries. We extend the notion of rank to the non-Boolean case through decision trees over assignment queries. We start by introducing some terminology. Pairs of the form (i, a), where i E [n] and E Σ, are called assignments. We denote by
1 -fofo...of-
E times
A = [1} x E U U... un x E,,
In particular, we let f() be the identity function.
We claim that the rank of t-Comp, does not exceed t. Recall that the input is interpreted as word (f(1)...,,
the set of assignments. An assignment (i. .) is consistent with an input w- = (I....,,o)) E Σj x... En, if and only if o; = a. By a permutation of a finite set B we mean a bijection :: [1,...,[B] + B.
for some f: [r]] - [rx). and our task is to compute f (1). Consider a decision tree that first tries to guess the value of the first letter, that is, of /(1) by going "is f(1) = 1?", "is f(1) = 2?". and so on. Once the tree gets right, receiving the first YES-answer, it already knows f11, and now it starts guessing the f(1)st letter, that is, f()) (((()))) It costs the second YES-answer to get it right. Continuing in this way, the tree will find out (() (1) after t YES- -as-answers.
An assignment query (a-query from now on) is a function of the form 9:: Σ, x... x E,, A, where is permutation of the set of assignments A. For i E Σ) X ... X Σ., we let ka be the minimal element & E (1,..., ||]} such that T (kk) is consistent with w. We then define gr (w) = Tkk)).
It is sometimes convenient to view the computation of an a-query 4r on an input wt as follows. Assume that
By means of a combinatorial argument, it is possible to show that this the best one can do if large enough.
3

---

Satenfeucht-Hausskee Rank and Chain of Thought
Proposition 2.3. For any and for all >> 21, we have rk(t-Comp,)= tt.
was not yet fixed, because j already belonged the set of forbidden numbers F. But by definition of g that means that either g(t) y or g = js for some s >> m. The first case is not possible since y was chosen to be outside of F, and the second case gives us g(i) # j.
Proof. Assume for contradiction that we have a decision tree T of depth t over a-queries for t-Comp... for some 21. We start answering questions for T, descending to one of its leafs, in the following manner. We maintain a set F S [r]] of "forbidden numbers". Initially, F = {1}. When we receive an a-query with permutation r of assignments, we select the first assignment (i,j) such that j & F and f(i) is not fixed yet. We fix f(i) = j and continue along the tree as this was the first consistent assignment. After that, we put j into F. Note that after k values of f have been fixed this way, F consists of precisely k + 1 distinct elements. Indeed, every a-query we consider adds exactly one new element to F.
To finish the proof, we show that (1) = y. Consider a directed graph with vertex set { n2), where for every E {L....:7) n there is a directed edge from to g()). The image of the function 9 consists of Jı..... jt and y. In the graph, these are the only nodes with incoming edges. Observe that each of ji....,JK jk has exactly one incoming edge. Namely, for = -,...., k. the node ja has a unique incoming edge from ig. To compute gf (1), we start mov- ing from along the edges for & steps. We will be mov- ing over J1..... jk and y. Note that g(v) y because y & fir...., de). Hence, it is enough to show that y is reached from in at most L steps because then we stay at y forever. Now, if we do not reach y within the first t steps, then we travel over ..jk for / steps. Since k S ( 1, it means that we come into some of :.....:J. Ja two times, but this would mean that one of them has two distinct incoming edges, which is impossible.
Let denote the leaf of where we come in this way by answering a-queries. Suppose that Og E [r] is the value that T outputs in this leaf. We obtain a contradiction by showing that some function g: [n] + [n]] with (1) A of also gets to E.
Observe that, since T is of depth t 1, there are l S 1 a-queries on the path to l and the same number of values of f have been fixed:
An example: Position of the k-tth one. We define a func- tion k-thOne,, {0, 10" - [n + 1] such that:
f(i1) = -1. f(iz) = f((x) = jk.
(1)
k k-thOne, (0,,...,, on) min min (0n++nnUUU LiiE [n] :1 +... to, =0==k k}).
Note that i ,ig is are distinct because never fix the same value twice. Numbers ,.. -ek are distinct too, and
they define the evolution of the set F. Initially, F == (1) after the first a-query, F = {1, f1} } after the second a-query, F= (1,51, after the third one, and so on.
In other words, given v = On) E 10, 1)", the function k-thOne, returns the position of the k-th one in w (counting from the left). If there are fewer than k ones in W, we return n + 1. We can then show the following by means of a combinatorial argument:
Take any y E [n] \ {1, (1,ig...... J1.... ......... fk. σε} (it exists because n > 21 2 1(k+ Define function g: [n] + [n]
Proposition 2.4. For any n, k, we have rk(k-thOne,,) S k and for n 2 1.2 + k, we have rk(k-thhne,.) = k.
by
s(h) j1, g(x)- for E [m]] \. (ú,,.... .i...
j..... ......... g((s)) jN,
3. Attention Layers and Decoders
We first show that g arrives to é in T. For that, show that g is consistent with all answers to questions the path to f. All the assignments corresponding to our answers to a-queries on the path to l are as in (I), and g is consistent with all of them by definition. Next, take an assignment (i,j) and suppose it appears at the m-th a-query along the path to é, ordered before the assignment (bm:Jm (which we chose to be the first consistent one). Hence, in our descent along the tree we ignored this assignment and decided to fix the assignment jm instead. Hence, we need to observe that g is not consistent with it, that is, that g(i) # j. Indeed, we could have ignored (i, in two cases. Firstly, it could have happened that g() was already fixed to some value different to j. Secondly, we could have ignored it when g(i)
Attention layer. We consider layers with unique hard attention, and possibly multiple attention heads, where the output of the layer is computed in the last token. By unique hard attention we refer to the mechanism in which each position attends to the element with the highest attention score (breaking ties arbitrarily).
Formally, a unique hard-attention layer (or, simply, atten- tion layer) with H heads and embedding dimension d is a function L: (Rd)* + Rdd which is defined by
H query matrices Q(h) E R and H key matrices Kth) E gdxd, for h = I,..., H,
two matrices W1, W2 E Rddxd and

---

Ehrenfeucht- Haussler Rank and Chain of Thought
matrix Wo Rd
Inputs to f are interpreted words with n letters, with the i-th letter coming from the alphabet Ex, for i ,,...:7 : (alphabets are possibly different at different positions). We put this word as an input to decoder using n + 1 tokens, one per letter plus a special token at the end for the "end of line" symbol. Input tokens can use arbitrary encodings of letters by d-dimensional vectors, potentially different at different positions of the input word, utilizing this form positional information. We then run the decoder on the resulting input for some number i of iterations. The output of ʃ is computed by applying an output function to the decoder's ' output ye from the final iteration.
Consider an input sequence of vectors (I1,..... Lm) E mm The output of L on (II,.... 2m) is computed as follows. For every h = 1,..., , H, we compute the value of the h-th head on (III,..,, which is vector from Idd denoted by heads, E R.. Namely, we start by computing "attention scores"
(b) a iim = (K(M) Ts, )
(2)
defining, for every i = L..... m, the attention from the last token to the i-th token with respect to the h-th head. The vector k(h),,; is called the key of the i-th token, and the vector Q (())x,m xm called the query of the m-th token.
Definition 3.1 (Computation of functions by decoders). Let n be natural number and Σ1, ..... En, O be n + 1 finite sets, A function f: Σι ... x En, + O can be computed by iterations of a decoder with H heads, if there exist:
For every h = 1...., H, we let in fl....,m m) be the index maximizing (2). If there are multiple indices achieving the maximum, we let in be the leftmost one. We then set head,- = Ii,, for h = I,... H, and define:
d E N and an attention layer L of embedding dimen- sion with H heads,
a positional encoding p. i... a function p: Σi x { U ...U ...UE, x {u) U (EoL) - Rd, where Eol denotes a special "end-of-line" symbol, and
head1
multihead = Wo
E Rd
(3)
head
an output function a : RR + O,
Finally, we define:
such that for any v (01...., on)) E x En, the value f()) is determined by the following procedure:
L [( Lm))
= W22 RRLU
+ xm)) E Rdd
(4)
Define a sequence (#1, In. yo) of d-dimensional vectors by:
Recall that RcLU(z) = max z), for every x E R, and if i E IRd then (xx) is obtained by applying ReLU to each one of its components.
. p(o1, 1), ,.. Tn p(a,, n), yo p(EoL).
Place (#1, ., Fn yo) as an input to the the decoder defined by L, and let ye for 2 I denote the output of this decoder after t iterations.
Decoders. A decoder, defined by the d-dimensional atten- tion layer L, is a function that takes on input a sequence of vectors (#1...., E (I")) and in the output produces an infinite sequence of vectors {ye E Rd defined by:
3. Set f()) a(y)).
Next, we define the following important notion. Definition 3.2 (Decoder depth of a function). The decoder depth with H heads of f: Σn X ... x E,, + O, denoted (f), is the minimum t 2 0 such that f can be com- puted by iterations of decoder with H heads.
= L(I,,,..,, Xm),
Yt- = L( Im V1
1)-
t 22 2.
(H)
That is, the decoder works in iterations: first, it computes the output of I., adds it to the end of the input sequence, computes the output of L on the new sequence, adds this output to the end, and so on. We refer to y: as the output of the decoder after iterations (sometimes these iterations are called "chain of thought steps").
4. One-Head Decoder Depth vs Tree Rank
In this section, we show that the rank of a function is equiv- alent to its decoder depth in the single-head setting.
Theorem 4.1. For any function f: En ... Σn, + O, we have rk(f) = ddd))
Computation of functions by decoders. Fix n and n + finite sets ,,,... , En, O. We want to define how decoder computes functions of the form:
As a corollary to Theorem 4.1 and Proposition 2.3, we obtain that for suitable n the decoder depth with one head of the iterated composition function t-Comp,, is precisely
f: Eg x ... x Enn + O.
5

---

Sanenfeucht-Hausskee Rank and Chain of Thought
Corollary 4.2. For each and for all n 21, we have (t-Comppp t.
We now show the inequality dd (J) S rk(f). Assume that T is an r-depth decision tree over a-queries that computes f. We transform into a decoder with one head that computes f in iterations. We assume that T is a complete r-depth A -ary tree, where A is the set of assignments.
Also, as a corollary to Theorem 4.1 and Proposition 2.4, we obtain that for suitable n the decoder depth with one head of the ktth one function k-thOne, is precisely k:
The embedding dimension of our decoder will be:
Corollary 4.3. For each k. and every n 2 k2 + k, we have dd (k-thhnn,))= k
d d= + |A| + + |A|"
+ +1+ | +... + |A|"
We now prove our main theorem.
+ |A]
Proof of Theorem 4.1. We first show the inequality rk(f)= I ( Assume that f can be computed by decoder with one head in iterations, for some E N. We deduce that rk(f)= S r. For that, we show that at the cost of t a-queries one can compute the outputs of the decoder in the first t iterations on a given input. Hence, in r a-queries, we can compute the rth output of the decoder, which uniquely determines the value of f. implying that rk(f) S..
+1.
The coordinates will be split into 4 groups:
the first ++A++ + |A|l coordinates are called positional coordinates and are indexed by non-leaf nodes of T::
the second 1 |4| +.... + |A| coordinates are called oulpul coordinates and are indexed by nodes of Tü
Consider any input to (01, ,......,000 σn) Σn x ... En. Define then:
the third |A| coordinates are called assignment coordi- nates and are indexed by assignments;
F1 p(), Tn.,,nn = p(n, on); yo = ><(ol)))))))))))))))(()) E Rdd
where d is the dimension of our decoder and is its posi- tional encoding function. Let (yr. E ]= be the sequence of the outputs of our decoder on input (I) nn 3o). As- sume that we have already computed "ll,,..,,,, y/ for some t 2 0 (if 0. we just know you = p(EoL)). We explain how to compute yt+1 using one a-query. By definition,
the last coordinate will be called special.
Our goal is to construct decoder that "simulates" T in the following sense. On input w E Σ, x... Σ,, for any 2 0, we want the (-th output of the decoder, denoted by y/ E IR4, to be the one-hot encoding of the node where T comes on t at depth t. More specifically, this one-hot encoding will take place in output coordinates, the remaining coordinates of y will all be O.
yt+1 = L( En yo: ,i,...,,t).. yt).
where L is the attention layer defining our decoder. It is enough to compute s E (#I,..., Fnn: Vo. .I..... 3e with the maximal value of (Ks, Qyi) for the key and query ma- trices K,Q E Rdxd of our attention layer. If there are multiple vectors s E {xI,.... Tn,, .o. .B} with the max- imal value of this scalar product, we need to compute the
To achieve this, we start with defining Yo (EoL) E Rd as follows. In the restriction to the output coordinates it is the one-hot encoding of the root of T; all the other coordinates of yo are O. Next, we define the positional encoding p(a) E Rd for an assignment a = (i. A. In the restriction the assignment coordinates, it is the one-hot encoding of a. Now, for each non-leaf node e of T and its corresponding positional coordinate p(a).. we set p(a), = 1/T," (a), where To {1,...,/A1 |A] + A is the permutation defining the a-query asked at v. We let the special coordinate of p(a) to be 1. Finally, all output coordinates of p(a) are set to 0.
leftmost one among them. Since we already have com- puted yo, V1,-.. Vt, it suffices to find this maximal over {xi...., } [n, = {p(1, ()),,,,,........ p(,,,,,,,,,,,, o.)).
Consider the following linear order of the set A of assignments. Given two different assignments a = (i,o),a' = (i','), we say that a is larger than a' if ei- ther (Kp(a), Qy)) > (Kp(a'), (uy) or (Kp(a), Qui) (Kp(a') Qy.) and i < I' We arbitrarily order assign- ments with (Kp(a), Qui) V. Our task is to find the maximal assignment from (p(1, p(n, ]n)} in this order. For that, we ask the a-query 4, for permutation T, where the first assignment is the maximal in our linear order, the second one is the second maximal, and so on.
Having our positional encoding defined, we move to the con- struction of the attention layer and define the query matrix Q E Rdxd by the following linear transformation a + Qa for a E Red; for every non-leaf node v of T', the v-th posi- tional coordinate of Qa is equal the u-th output coordinate of a; the remaining coordinates of Qa are 0. The key matrix K E RRd is set to be the identity matrix.
(Kp(a'), Qu)) and
6

---

Sarreffuchtt-Husslle Rank and Chain of Thought
Assume that, as an input, for some / r, we give layer the following sequence of vectors:
is not an output coordinate for non-root node of T. Now, consider any non-root node T. It is enough show that the v-th output coordinate of - 8 is I for e = and is O or 1 for e # ty (applying ReLU to 0 and -1, we get 0).
Tns yo, M1, Vt E RR
where 2; = o() for ,,...,, n and for some w (a), (o),.... .nn) E 31 x... x Em, yo p p(Eo),, and for every i = I....,t the vector y; is the one-hot encoding, inside the output coordinates, of some depth-i node of T, and has 0 in the remaining coordinates. Let = qv, be the a-query asked at ltz and let r = Te, be the corresponding permutation of the set of assignments (the node v/ is a non- leaf node because t < r). We claim that the attention on this input will be maximized for the position with the assignment which is the output of q on t.
To calculate the e-th output coordinate of W1,3, as stated in (7-9), we calculate the parent(v) output coordinate of 3, the label(u)-th assignment coordinate of 3. and the special coordinate of 3. Recall that positional encodings of assignments have 0 in the output coordinates. Hence, the sum B = p(g((()) + 1/., in the restriction to the output coordinates, is the one-hot encoding of ug. In other words, the parent(u)-th output coordinate of / is the indicator [porent(v) = }.). Likewise, since yt has only 0 in the non-output coordinates, the sum / = =[(((w) + yts in the restriction to the assignment coordinates, is the one- hot encoding of the assignment ( Again, this means that the (v)-h assignment coordinate of 3 is equal to the indicator [llabe((v) = (())). Finally, the special coordinates of p()(ū)) and y/ are 1 and O, respectively, meaning that the special coordinate of 3 is 1. Plugging these equalities into (7-9) for a = B, we obtain that the v-th output coordinate of W13 equals:
Indeed, the vector yr has the unique I at the e,-th output co- ordinate, with the remaining coordinates of is being O. The matrix Q moves this 1 into the 1y-th positional coordinate, and the rest of the coordinates of Qy: are O. Thus, for any E Rd, the product (Ka, Qyt) equals the value of in the th positional coordinate. If p(i, o;) for i E [m]], this value is 1/r=\ii,;; The maximum of this value is attained for (i, E ((1,)))...
(n, on)) with the mini- mal value of r (i, o.). i.e, for (i) = q(σ). Now, for a E (yo. 31..................... ye ). the value of the 24-th positional co-
[parent(v)) v1 + [(labe(()) q( - 1.
ordinate, as well as any other positional coordinate, is O. Hence, the output of the head will be the vector p(q( ()).
This expression takes values in {-1, 0, 1) and it is equal to if and only if both indicators are 1. remains to note that
Ut+1 is the only node whose parent is v, and such that the label of the edge from v, to this node g(
The output of the layer is now computed as:
9t-1 = W2 ReLU (W1 1), B = p(g(())) + yt-
(5)
The r-th output of the decoder, yr. in restriction to the output coordinates, will be the one-hot encoding of the leaf to which we come while computing T on input w. Since this leaf uniquely determines f((), we are done.
(6)
We need to choose W1, W2 E Rdxd such that the resulting It+1 will encode the node 1r41 where the tree goes from e by following the
edge. More specifically, we
5. Multihead Rank
want De+1 to be the one-hot encoding of Ut+1 in the output coordinates, and we want all the other coordinates of Mt++1 to be O. We will set W2 to be the identity matrix. To define W1, we fix the following notation. For a non-root node v of T, let pv) denote the parent node of v, and let label(v) E denote the label of the edge from parenl(v) to We define Wi by the following linear transformation + Wia,a a Rd: for every non-root node of T, we define the v-th output coordinate of Wa as
In order generalize Theorem 4.1 decoders with many heads, we define the notion of H-head rank for a function ʃ Σi x... x Σn - O. For that we require a notion of the product of two functions with the same domain. Namely, by the product of f: A - B and g: A + C, we mean a function (ʃ 8 g): A + B x C, defined by:
(J @ (a) (J(a).
An H -degree a-query is product of H a-queries.
the parent(o)-tt -th output coordinate of a
(7)
(8) Definition 5.1. The H-head rank of function f Σ₁ x
+ the (r)-h assignment coordinate of a
x Σ, + O, denoted rk ()), is the minimal depth of (9) a decision tree over H H-degree a-queries that computes f.
the special coordinate of a.
We set all the other coordinates of a1a to O.
A simple generalization of the construction of Theorem 4.1 allows us to obtain the following result.
We have to show now that RcLU(W, -9), with 3 as in (5-6) has in the 1th output coordinate and 0 in all the other coordinates. Indeed, W1- /3 has 0 in any coordinate which
Theorem 5.2. For any H E N and any function f: Σ x
x Σn, - O. we have (1) (f) = dd (d()))
7

---

ChreeffeuchtHHuussee Rank and Chain of Thought
We observe that the H-head rank can be at most H times smaller than the normal rank. Specifically, each H-degree a-query can be computed by performing H. individual a- queries sequentially.
binary words my E {0, (0,1)41,-.. 1-.,,, my E {0, 13 by setting
my Mi(mi ... m1) for odd i E k),...,k. m. - Mi(mi.... 1,3) for even i E (I....,k)
Proposition 5.3. For f E1 x ... x Σn O and H 2 1, we have rk rk()) S H- rk (f).
Intuitively, mi = MI(E,)) is the first message of Al- ice that she sends to Bob in the protocol on input Upon receiving m., Bob replies with the second message m2 M2 v) that depends on his input and the first of Alice's messages. Then Alice sends the third message my = M3 (mim2, and so on. The output of the protocol is defined as out ... ...) ) E Z.
Proposition 5.3 allows us reduce, up a factor of H, lower bounds on rk (f) to lower bounds on rk(f). However, this proposition is sometimes unable to provide tight bounds on (f). This occurs, for instance, when rk rk(") is not smaller at all than rk(f). We present two examples of this phenomenon in this section.
By C*+,(() we mean the minimal communication complex- ity of k-round Alice-first protocol that computes f. By reversing the roles of Alice and Bob, we define k-round Bob- first protocols, and Ck. (f), the minimal communication complexity of a k-round Bob-first protocol for function f.
To establish precise lower bound on the decoder depth of a function with H heads, it suffices to derive a lower bound on its H -ead rank (Theorem 5.2). However, this task proves to be significantly more challenging than for the single-head rank. Specifically, for the iterated composition function, combinatorial arguments alone, employed in the proof of Proposition 2.3, are no longer sufficient. Instead, we must rely on techniques from communication complexity to ad- dress the problem. For the k-thOne, function, we develop a combinatorial argument that is notably more intricate than the one used in the proof of Proposition 2.4.
Assume we have a function f: Σ1 x... x Σ, + O and subset S C [n]] Suppose that positions of an input word w Σn ... Σn are split between Alice and Bob like this: Alice knows letters of w at positions i S, and Bob knows letter of i at positions i [n] \ S. Their goal is to find out f(w). This defines function:
5s: II E
II Σ -0,,, [Efn]),
5.1. Multihead decoder depth of iterated composition
WES
In this section, we show a method for lower bounding the multihead rank of a function based on communication com- plexity (Kushilevitz. & Nisan, 1996). Let X, V/2 2 be finite sets and f: X x y + Z be a function. Imagine that there are two players, Alice and Bob. Alice is given x E X' and Bob is given y E y. Their goal is to cooperatively compute (x, y)- For that, they can send each other messages that are binary words. They want to minimize the number of messages and their total length in bits.
where the two inputs correspond to the parts of w that Alice and Bob knows, respectively, and the output of is f(w).
Assuming that the Hthead rank of f is r, we construct low-communication (r + 1) -round Alice-first and Bob-first protocols for fs, for any S S [n]] This gives method for lower bounding the multihead rank of f: by showing that B either Cr+1,A() (f) and C is large enough, we conclude that the H-head rank of f is larger than r.
Formally, k-round Alice-first communication protocol II is given by:
Lemma 5.4. For every f: Σn X ... x En + {0, for every S S [n], and every H 2 1, denoting = rk' (H) (f) and A the number of assignments for J. we have:
k positive integer numbers E,,...,& (messages lengths);
Crt1, S 2HHr. -Ilog |All and Cr+1.B (f$) < 2Hr [log2 [A
a function M4: {0, 10.11 x X + {0, 13 for every odd i kk]:
Proof. We first notice that Alice and Bob can compute the value of any Hddegree a-query Qr, 8 8... @ 4TH by exchang- ing messages of length H [log2 a] In fact, for given input E Σn X ... En, there are exactly n assignments consistent with w. A part of them is known to Alice (for positions in S) and the other part to Bob (for positions in [n] ( For each h = 1,..., H, Alice and Bob have to calculate the first assignment in the permutation T which is consistent with w. Alice can see which ecconsistent assign- ment, known to her, goes first in The and the same for Bob.
function Mj: {0, 1) th x + f0, 13 for every even i {1, (1,...,A) k); and
the output function out: (0, 1) + + Z.
The communication complexity of ll is the sum E +.... Cu-
On input (z. v) E X x y, the output of II on (z, y) is
computed as follows. We inductively define a sequence of
8

---

Setteffucch-Hauusshe Rank and Chain of Thought
Among these assignments, the one that goes first is the answer to 4t,- Alice and Bob just have to exchange the indices of these assignments. For both Alice and Bob it is thus enough to send a H [log2 a] -bibit message with indices of H assignments.
5.2. Multihead decoder depth of ktth One
In this section, we establish tight lower bound on the multi-head rank of k-thOne.
Theorem 5.6. For any k, H E N. for all but finitely many n. E N, we have rk (H (k-thOne.)) =
We already see that an r-depth decision tree over Hdeegree a-queries can be simulated by a communication protocol with 2/r [log2 a| bits. We need explain how arrange this communication in r + 1 rounds. For that, Alice and Bob have to alternate the order in which they exchange their messages in computation of the H -ddggre a-queries. For example, for the Alice-first protocol, in the computation of the first query Alice has to send her message first and then Bob. Now, for the second query, Bob has to send his message first and then Alice. In this way, Bob's messages for the first and for the second query merge into single round of communication. Similarly, for the third query, Alice has to send first, and then Bob, and so on, getting overall r + rounds. The Bob-first protocol is constructed in an analogous fashion.
We observe that our communication complexity tool not applicable in this case, as for any partition of the input positions between Alice and Bob, there exists 2-round protocol with logarithmic communication that computes the position of the k-th one: Alice sends the positions of the first l ones in her part of the input, and Bob does the same.
Proposition 5.7. For any k, n and _ [n]]
Ca.A (k-thOne = (k-th(k))) = O log n).
If we wanted to use Lemma 5.4 to obtain lower on rk (k-thOnee) we would have needed (z.A(k-thOnee)) or (k=ttk--One to grow super-logarthmicall with for some I [n]. Instead, we use a self-reducibility tech- nique by means of partial fixations.
As a corollary, we obtain the following: Corollary 5.5. For every H and t, for all but finitely many n, we have (H) (t-Comp,.) =t
6. Final Remarks
Proof. We reduce from a communication problem called pointer chasing. In this problem, Alice is given fA: {1....,m: m} + (m....,m} and Bob is given fB: (1,...,,) m) + (1.....m). In the k-step pointer chase, denoted here by PCE, the goal of Alice and Bob is to compute:
We have shown that the expressive power of single-layer Transformers with hard attention is tightly connected to the notion of rank of functions. Extending this characterization to more layers or to soft attention is a challenging future direction. a contemporaneous manuscript, Chen et al. have proved unconditional lower bounds on the embedding dimension of multilayer decoder-only Transformers with soft attention that compute iterated function composition. However, their version of the problem differs significantly from the one considered here: they have several functions to compose, and each function is completely given in a single token. We plan to explore whether the techniques used in their work can be applied to strengthen our results.
(A(
& times
It is easy to see that CAAA(PC)) = Ok log (Alice starts by sending m, = f1), Bob replies by sending my = fo (m1), and so on). It is known that this task requires much longer communication for k-round Bob- first protocols. Namely, for any constant k, we have (PCC) ((m) (Duris et al., 1987).
A Akknowledgements
remains to notice that PCT is a special case of the problem 1-Comp for S = (1 (1.....n/)) .2/)), where Alice gets and Bob gets (ø(n/2 + 1)..... o(n)). for some function Φ: n - {1, (1.....ml, m.) and the task is to compute (1). Namely, we obtain PCP/22 as a special case when & maps the first half of the inputs into the second half, and the second half into the first half. Assuming that rk (t-Comp,,) < t, by Lemma 5.4 we obtain:
Kozachinskiy is supported by ANID Fondecyt Iniciación grant 11250060. Barceló and Kozachinskiy are funded by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID. Barceló is also funded by ANID Millennium Science Initiative Program Code ICN17002.
(é(1)....,
Impact Statement
Omega(n) B (PCpp// 5
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
< 2Ht flog2 n²?
For any fixed H, t this is true only for finitely many n.

---

Sarenfeucht-Hausslee Rank and Chain of Thought
References
Liu, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought powers transformers solve inherently serial problems. In ICLR, 2024.
Angluin, D.. Chiang, D., and Yang. A. Masked hard- attention transformers and boolean RASP recognize ex- actly the star-free languages. CoRR, abs/2310.13897, 2023.
Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. Trans. Assoc.
Comput. Linguistics, 11:531-545 2023.
Barceló, P., Kozachinskiy, A., Lin, A. W., and Podolskii, V. Logical languages accepted by transformer encoders with hard attention. In ICLR. OpenReview.nee, 2024.
Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. In ICLR, 2024.
Chen, I.,, Peng, B., and Wu, H. Theoretical limitations of multi-layer transformer. CoRR, abs/2412.02975, 2024.
Peng, B., Narayanan, S., and Papadimitriou, C. H. On limitations of the transformer architecture. CoRR, abs/2402.081 2024.
Chiang, D., Cholak, P., and Pillay, A. Tighter bounds on the expressivity transformer encoders. ICML, volume 202. pp. 5544-5562, 2023.
Pérez, J., Barceló, P., and Marinkovic, J. Attention is turing- complete. J. Mach. Learn, Res., 22:75:1-75:35, 2021.
Clark, K., Khandelwal, U., Levy, O., and Manning, C. D. What does BERT look at? analysis of bert's attention. In ACL Workshop BlackboxNLP, pp. 276-286, 2019.
Pudlák, and Impagliazzo, R. A lower bound for dll algo-
rithms for k-sat (preliminary version). In Proceedings of the eleventh anmual ACM-SIAM symposium Discrete algorithms, pp. 128-18 136, 2000.
Duris, P., Galil, Z., and Schnitger, G. Lower bounds on com- munication complexity. Information and Computation, 73(1):1-22, 1987.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In NeurIPS, pp.
2017.
Ehrenfeucht, A. and Haussler, D. Learning decision trees from random examples. Information and Computation, 82(3):231-246, 1989.
Voita, E., Talbot, D., Moiseev, F., Sennrich, R., and Titov, I. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In ACL, 2019,
Esteban, J. L. and Torán, J. combinatorial characteriza- tion of treelike resolution space. Information Processing Letters, 87(6):295-300, 2003.
Yang, A. and Chiang, D. Counting like transformers: Com- piling temporal counting logic into softmax transformers. CoRR, abs/2404.04399 2024.
Hahn, M. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8: 156-171, 2020a.
Yang, A., Chiang, D., and Angluin, D. Masked hard- attention transformers recognize exactly the star-free lan- guages. In NeurlPS, 2024.
Hahn, M. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020b.
Hao, Y., Angluin, D., and Frank, R. Formal language recog- nition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10:800-810, 2022a.
Hao, Y., Angluin, D., and Frank, R. Formal language recog- nition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810, 2022b.
Kullmann, O. Investigating general hierarchy of polyno- mially decidable classes of enf's based on short tree-like resolution proofs. Citeseer, 1999.
Kushilevitz, E. and Nisan, N. Communication Complexity. Cambridge University Press, 1996.
10


Reviews:
[{"review_id": "C4T74PDdQW", "reviewer": "Reviewer_QZRi", "summary": "The authors study the expressivity of single-layer transformers with hard attention by studying the question: How many chain of thought steps are required to compute particular functions that map strings of length n to some finite output set. The Ehrenfeucht-Haussler rank of a Boolean function measures the complexity of Boolean decision trees that compute the function. The authors introduce a generalisation of the Ehrenfeucht-Haussler rank for non-Boolean functions and obtain various results that relate the number of chain of thought steps required to compute a function to its rank. They first establish that the rank of a function is identical to the number of chain of thoughts required to compute the function. They also give a generalisation of this result to transformers with multiple attention heads by defining a corresponding H-head rank of a function. For particular examples, they establish that the ranks of an n-fold composition function and the function computing the position of the n:th 1 of an input is n.\n\nFinally they show that the H-head rank can be at most H times smaller than the 1-head rank, and that H-head ranks of the n-fold composition function and the function computing the position of the n:th 1 of an input is n. Hence, for these function adding the number of heads does not decrease the number of chain of thoughts required.\n\n## update after rebuttal\nI maintain my previous assessment.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review and for noticing some typos!", "claims_and_evidence": "The paper is well written and presented. The claims made in the paper are supported by clear intuitive explanations and formal proofs.", "methods_and_evaluation_criteria": "NA.", "theoretical_claims": "The proof ideas seem plausible. I did not identify any technical issues, but I did not check all the technical details.", "experimental_designs_or_analyses": "NA.", "relation_to_broader_scientific_literature": "The authors do a good job in setting the scene of the paper and in positioning their results with respect to literature.", "essential_references_not_discussed": "I am not aware of related works that should be cited.", "other_strengths_and_weaknesses": "This is a solid paper. The study of the expressivity of transformers is an important and timely topic, and this paper takes an interesting angle to this by relating to complexity of decisions trees needed to compute corresponding functions. The results are interesting and non-trivial.", "other_comments_or_suggestions": "Please in the future use two-column line numbering.\n\n-l.145, right. Typo: \"and out task\".\n-l.175. It is a bit out of place to define [n] here, since the notation has been used already many times before in the paper.\n-l.277. Typo: \"the t-the\"", "questions_for_authors": "No questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wy0LU2RjuU", "reviewer": "Reviewer_F5ay", "summary": "This paper characterizes the notion of rank for Boolean and non-boolean functions with a one-layer transformer. Specifically, they show that the rank of a function is equivalent to the minimum number of chain-of-though steps required by a single-layer Transformer with\nhard attention to compute the function. They also generalize the definition to the H-head attention. For some compositional tasks, they show $k$-fold function composition necessitates exactly $k$ CoT steps.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for all your valuable comments. Below we respond to some:\n\n1. *The specific tasks considered, t-Comp and k-thOne, are very simple. It would be great to consider some more practical tasks, e.g. the arithmetic tasks and Dynamic Programming in [1]. Or maybe give more examples of functions with different ranks so that the reader can have a better sense of the complexity of different task* \n\nThank you for the suggestions. We will study [1] to apply our technique for the tasks considered there. We can also add more simple examples. For instance, [Hahn, 2020] gives examples of functions (Parity, Majority, Dyck) that are not doable with a constant number of hardmax layers (without CoT).  We can show that these functions have rank, linear in the input length, meaning that they require a linear number of CoT steps for 1-layer hardmax decoders.\n\n[1] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. NeurIPS, 2023.\n\nLet us also point out that tasks considered also have practical motivation. Arguably, compositional/relational tasks are a very important part of human linguistic skills. Previous papers, like https://arxiv.org/abs/2311.13314, observed that LLMs struggle with prompts that can be viewed as composition of functions (e.g. ‘’When is Frederic Chopin’s father’s birthday?). Peng et al https://arxiv.org/abs/2402.08164 introduced t-Comp in this context exactly as a model of  compositional task, which could be used to explain why LLMs struggle with compositional tasks. We will elaborate on this in the revised version.\n\n*2. The fact that t-Comp and k-thOne need t or k CoT steps seems not very surprising since every step can only compute a single composition/iteration and the multi-head can only add different functions together but not compose functions.*\n\nWe agree with the reviewer that lower bounds on t-Comp and k-thOne are intuitive. However, we think that this is one of the strengths of our paper, that we provide a formal rigorous proof. With the proof, we can now with 100% certainty say CoT cannot do anything better than compute a single composition per iteration, even with a constant number of attention heads.\n\n*3. It would be great to discuss the relations with previous works. What is the relation between the rank and circuit complexity?\n\nGreat question. Ehrenfeucht and Hausler have shown that functions with constant rank have polynomial decision-tree size, which also implies they have polynomial circuit-size. By the result of Liu et al., that implies that problems with constant rank are solvable with polynomially many CoT steps. Our results clarify this by showing that only a constant number of steps suffices in this case. \nWe will also add a reference to the following recent paper [On (simple) decision tree rank, Dahiya, Mahajan] that has some connections of the rank with other complexity measures.\n\nRegarding some minor comments:\n\n*line 209 $u_{i_h}$ is not defined.*\n\nthis is a typo, it has to be x_{i_h}, thanks for noticing!\n\n*line 344 should be the product of $f$ and $g$?*\n\nsorry, the phrase ``Namely, by the product of g : A → B and h: A → C'' should be ''Namely, by the product of f : A → B and g: A → C''", "claims_and_evidence": "The theoretical claims are supported by proofs.", "methods_and_evaluation_criteria": "They evaluate the proposed rank for simple compositional task t-Comp and k-thOne.", "theoretical_claims": "I didn't check the proofs. But the theoretical results make sense to me.", "experimental_designs_or_analyses": "There is no experiments in the paper.", "relation_to_broader_scientific_literature": "The key contributions of the paper might help improve the understanding of the expressive power of transformers.", "essential_references_not_discussed": "The paper discussed several related works. But I think it would be good to discuss the relation with these works. For example, what is the relation between the rank and the different circuit complexity? What is the complexity of the t-Comp and k-thOne?", "other_strengths_and_weaknesses": "### Strengths\n- I think the connection between the rank of a function and the steps of CoT is quite interesting. It might help us to have a better understanding of the steps of CoT required for different problems.\n-  The proposed connection between rank and decoder depth allows us to have a finer analysis of the task complexity at hand. \n\n### Weaknesses\n- The specific tasks considered, t-Comp and k-thOne, are very simple. It would be great to consider some more practical tasks, e.g. the arithmetic tasks and Dynamic Programming in [1]. Or maybe give more examples of functions with different ranks so that the reader can have a better sense of the complexity of different tasks.\n- The fact that t-Comp and k-thOne need t or k CoT steps seems not very surprising since every step can only compute a single composition/iteration and the multi-head can only add different functions together but not compose functions.\n- It would be great to discuss the relations with previous works. What is the relation between the rank and circuit complexity?\n\n\n[1] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. NeurIPS, 2023.", "other_comments_or_suggestions": "- line 209 $u_{i_h}$ is not defined.\n- line 344 should be the product of $f$ and $g$?", "questions_for_authors": "See questions above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yw0neN2yr0", "reviewer": "Reviewer_MAzv", "summary": "The paper shows that the minimal number of CoT steps a single-layer hard-attention Transformer needs to compute a function exactly corresponds to the function's EH rank. In essence, it proves that the EH rank equals the minimum depth of decision trees (over assignment queries) that simulate the Transformer's computation process. Two directions are established: one where Transformer iterations mimic decision tree steps to resolve attention choices, and another where a Transformer decoder is constructed to replicate a decision tree of a given rank.\n\nKey canonical functions are analyzed. For iterated composition, it’s shown that the EH rank equals the number of compositions, while for the kth-one identification problem, the rank exactly equals k when the input size is sufficiently large. These results are supported by communication complexity and combinatorial arguments.\n\nAdditionally, the paper extends these findings to multi-head attention by defining an H-head rank, proving that even with parallel a-queries, the sequential steps required for tasks like composition or counting remain unchanged. Overall, the work bridges classical complexity (EH rank) with modern Transformer architectures, highlighting both their computational power and the limitations of parallelism in structured tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you kindly for all your comments and inspiring questions! \n\n*The claim that “multi-head attention cannot circumvent inherent sequential steps” applies only to t-Comp/k-thOne—not general tasks.*\n\nA following function with H-head rank 1 and 1-head rank H establishes tightness of proposition 5.3. [Dahiya, Mahajan, On (Simple) Decision Tree Rank] gives the function OR_H \\comp AND_m, defined as the disjunction of H conjunction, where each conjunction is taken on m disjoint variables. The aforementioned paper shows that its normal rank is H. On the other hand, its H-head rank is 1 because each head can compute one conjunction.\n\n*All the theoretical claims looks to be correct, just one doubt on Theorem 5.2 -> Multi-Head Rank Equivalence (...) This is valid if matrix dimensions align with the expanded coordinate system?*\n\nYes, this is still valid. In particular, by expanding the number of coordinates, we create $H$ independent blocks to encode assignments. This allows us to one-hot encode the assignments $a_1, .., a_H$, results of $H$ a-queries of the current, each within one of the blocks. In the matrix $W_1$, in each row (corresponding to a potential node $v_{t+1}$, there will be precisely one 1 per assignment block, indicating the unique tuple of answers $a_1, .., a_H$ that lead to the node $v_{t+1}$ from $v_t$.\n\nThere is a small typo here, we must have $-H$ before the special coordinate instead of $-(H-1)$. This is because we want the expression $ReLU(b_0 + b_1 + … + b_H - H)$ to be $1$ if and only if $b_0 = b_1 = … = b_H = 1$ if and only if $b_0 + b_1 + … + b_H = H +1$. We will fix this in the revised version. \n\nRe: *the paper does not validate if $t\\text{-Comp}$’s structure fully aligns with PC’s assumptions (e.g., cyclic dependencies).*\n\nLet us clarify that for this lower bound, we consider phi’s that map numbers from the first half to the second half, and numbers from the second half to the first half. Such mappings are decomposable into two independent function $g:{1, .., n/2} \\rightarrow {n/2+1, … n}$ and $h:{n/2+1, … n}\\rightarrow {1, .., n/2}$, which fully aligns the assumptions of the pointer chasing problem. Functions that are not decomposable in this way are not needed.\n\n*Q1:*\n\nThe exact relation between hard and soft attention constitutes a major open problem in the area. Recently, there has been some progress with regard to simulating hard attention with softmax, see e.g. Yang et al 2024 [Simulating Hard Attention Using Soft Attention] . Then there are examples of tasks, like PARITY, which can be done with softmax but not with hard attention. At the same time, in experiments softmax transformers struggle to learn PARITY. So lower bounds for hard attention do seem to predict well what a softmax transformer can do in practice, even if these lower bounds do not always generalize in theory.\n\n*Q2:*\n\nGreat question! By Yao’s principle, this is equivalent to asking whether there is a randomized transformer that, on any input, solves the task with probability of error at most 1%. We do not immediately see how to extend our lower bound to work against randomized transformers, but we hope that some argument exists. Indeed, this question is relevant from a practical point of view, as real language models generate tokens by sampling. \n\n*Q3:*\n\nWe hope that some ``recursive’’ version of EH rank can capture multi-layer hard attention decoders. For instance, we can think of level-2 decision trees as low-rank decision trees that in their leaves, instead of just 0,1, can compute a low-rank decision tree. For instance, the palindrome function can be computed as a disjunction of conjunctions, which is a level-2 decision tree of rank 1, as disjunctions and conjunctions are normal rank-1 functions.  We find it plausible that some variation of this notion will capture 2,3,4…-layer decoders, but of course, this is a future-work direction.\n\n*Q4:*\n\nThe matrix W_2 is set to be the identity matrix, as stated on Page 6 line 285. As for W_1, to increase the readability of the proof, we have defined it as a matrix of a linear transformation, defined in (6-8). We believe it is easy to deduce the explicit description of W_1 from the description of the corresponding linear transformation. Namely (W_1)_{ij} is equal to the value of the i-th coordinate of the image of our linear transformation on the vector that has 1 in the j-th coordinate and 0s elsewhere.\n\n*Q5*\n\nWe actually cite this paper, but we have to fix the citation, thank you for pointing us out to this issue. By the results of Li et al., to solve P-complete problems, transformers need polynomially many iterations of CoT. In turn, EH rank allows to precisely characterize what functions are computable in any given fixed number of iterations (1, 2, 3, and so on). Results are thus formally incomparable and complement each other in different regimes of the number of CoT steps.", "claims_and_evidence": "The claims are supported by clear theoretical evidence within the paper’s scope (single-layer hard-attention Transformers). The proofs for equivalence and lower bounds are systematic, leveraging combinatorial fixation, communication complexity, and inductive self-reducibility. However, the reliance on hard attention and idealized input fixation limits practical applicability. No evident gaps or errors are present in the core arguments.\n\n1. Equivalence of EH Rank and Decoder Depth: $\\mathrm{rk}(f) = \\mathrm{dd}^{(1)}(f)$ for any function $f$.  \n       1. Rank ≤ Decoder Depth: Simulates Transformer steps via decision trees over a-queries. Each CoT step corresponds to resolving one a-query (Appx. A.1).  \n       2. Decoder Depth ≤ Rank: Builds a Transformer decoder emulating rank-$r$ decision trees (Sec. 4). Positional encodings track decision paths, ensuring equivalence. The bidirectional reduction is explicit, with detailed embeddings and attention mechanisms (Sec. 4.1).  \n\n2. Tight Bounds for Canonical Functions $\\rightarrow$ for t-Comp $\\mathrm{rk}(t\\text{-Comp}_n) = t$ for $n > 2t$.  \nAuthors show combinatorial argument via input fixation (Prop. 2.3). Fixing $t-1$ values forces at least $t$ a-queries (Appx. A.2).  \n\n3. Authors also show Multi-Head Generalization claiming $\\mathrm{rk}^{(H)}(f) = \\mathrm{dd}^{(H)}(f)$, for $t$-Comp, reduces to pointer chasing (PC) with $\\Omega(t)$ rounds (Cor. 5.5) and for $k$-thOne, uses induction and unfixed intervals (Thm. 5.6).  \n\n---\nFew limitations that I found:\n\n1. Results apply to idealized hard attention, not softmax-based models. The paper acknowledges this but does not explore extensions (Sec. 6). \n2. Arguments for $k$-thOne (Appx. A.3) rely on intricate partial fixations. While valid, the self-reducibility step assumes $f(n)$ grows sufficiently without explicit bounds.  \n3. The reduction from PC assumes Bob-first protocols require $\\Omega(n)$ communication, but the paper does not re-prove this result, relying on Duris et al. (1987).", "methods_and_evaluation_criteria": "1. The equivalence between EH rank and decoder depth is established via explicit bidirectional reductions (decision trees ↔ Transformers). This provides a formal foundation for analyzing CoT steps.  Constructive embeddings (Sec. 4) ensure equivalence, while combinatorial fixation (Prop. 2.3) and communication complexity (Cor. 5.5) enforce tight bounds.\n\n2. Reduction to pointer chasing (PC) with Ω(t) communication rounds (Duris et al., 1987) is valid and aligns with established complexity theory.Partial fixation arguments (Appx. A.3) enforce sequential resolution of 1s, leveraging inductive self-reducibility\n\nLimitations:\n1. The analysis is restricted to single-layer decoders. Modern Transformers use multiple layers, which may reduce CoT steps via hierarchical processing—unaddressed in the paper.\n2. The decoder depth equivalence assumes custom positional encodings (Sec. 4.1). It is unclear if results hold for standard embeddings (e.g., sinusoidal, learned).\n3. While the paper proves multi-head rank equivalences (Thm. 5.2), it does not identify functions where additional heads reduce steps. The claim that “multi-head attention cannot circumvent inherent sequential steps” applies only to t-Comp/k-thOne—not general tasks.\n4. One thing which I was hoping to find in this paper: its applicability to real-world Transformers remains unproven. Future work should address soft attention and multi-layer models while incorporating standard NLP benchmarks.", "theoretical_claims": "All the theoretical claims looks to be correct, just one doubt on Theorem 5.2 -> Multi-Head Rank Equivalence claims $ \\mathrm{rk}^{(H)}(f) = \\mathrm{dd}^{(H)}(f) $, each head’s a-query is parallelized via $ H $-degree queries. Positional encodings and matrices generalize the single-head case. $W_O$ concatenates head outputs, and $ W_1, W_2 $ ensure state transitions. Assumes ReLU correctly prunes invalid paths. This is valid if matrix dimensions align with the expanded coordinate system?", "experimental_designs_or_analyses": "The paper is purely theoretical, focusing on proving equivalences and lower bounds via combinatorial/communication complexity arguments. Since it contains no empirical experiments, there are no traditional \"experimental designs\" or statistical analyses to critique.   \n\n1. All results assume idealized hard attention (argmax over tokens). While acknowledged, this limits practical relevance to real-world softmax-based Transformers.  \n2. Lower bounds rely on adversarial input constructions (worst-case analysis). No consideration of average-case or probabilistic inputs.  \n3. In Thm 4.1, matrices $W_1, W_2$ are described via logic (e.g., “ReLU correctly prunes invalid paths”) but lack explicit parameterization. While the logic holds, explicit matrices would strengthen rigor.  \n4. The $t\\text{-Comp}$ lower bound (Cor 5.5) depends on Duris et al.’s $ \\Omega(n) $ bound for PC. While this is a standard reference, the paper does not validate if $t\\text{-Comp}$’s structure fully aligns with PC’s assumptions (e.g., cyclic dependencies).", "relation_to_broader_scientific_literature": "The paper advances three major threads:\n\n1. Bridging Complexity Theory and Transformers: Connects EH rank (PAC learning) to CoT steps (Transformer theory).\n2. Multi-Head Limitations: Shows parallelism cannot circumvent sequential rank bounds, contrasting with softmax-based analyses.\n3. Combinatorial Proof Techniques: Introduces novel fixation/self-reducibility arguments for positional tasks, complementing communication complexity methods.\n\nThese results refine the understanding of Transformer’s inherent limitations, providing theoretical grounding for empirical observations about CoT’s necessity in complex reasoning.", "essential_references_not_discussed": "The paper does not cite several recent works that provide critical context for its contributions. Below are key omissions:\n## 1. \n1.1 Li et al. (ICLR 2024): [\"Chain of Thought Empowers Transformers to Solve Inherently Serial Problems\"](https://openreview.net/forum?id=3EWTEy9MTM) proves that transformers with CoT can simulate polynomial-size circuits, resolving whether CoT fundamentally increases expressivity. This work establishes that CoT allows transformers to overcome parallel computation limits (e.g., processing **TC⁰** vs **AC⁰**), which directly contextualizes the current paper’s focus on sequential steps and rank equivalence.  \n1.2 The current paper’s claim that CoT steps correspond to EH rank aligns with Li et al.’s conclusion but lacks a broader complexity-theoretic framing.\n\n## 2. \nFeng et al. (2023): [\"Transformers as Neural Solomoff Inducers\"](https://arxiv.org/abs/2310.10691)* connects CoT to circuit complexity, showing transformers with CoT can solve problems outside NC (parallelizable classes).  The current paper’s combinatorial proofs for k-thOne and t-Comp could be strengthened by contrasting with Feng et al.’s circuit-depth arguments.\n\n\n## 3. \nHu et al. (2024): [\"Stepwise Self-Consistent Training for Language Agents\"](https://arxiv.org/abs/2402.03286) demonstrates empirically that CoT steps reduce estimation error in multi-step reasoning, even with noisy intermediate tokens. The current paper’s theoretical analysis of hard attention could benefit from engaging with Hu et al.’s findings on robustness.\n\n## 4. \nChen et al. (2024): [\"Theoretical Limitations of Multi-Layer Transformer\"](https://arxiv.org/abs/2412.02975) proves dimensional lower bounds for soft attention in deep transformers. While cited briefly in Sec. 6, this work is critical for understanding why the current paper’s single-layer, hard-attention analysis cannot trivially extend to multi-layer models.  The paper does not contrast its rank-based bounds with Chen et al.’s dimension-dependent constraints.\n\n## 5. \nBhattamishra et al. (2024): [\"Transformers Learn Higher-Order Programs\"](https://arxiv.org/abs/2403.00732) shows transformers with CoT can learn program induction in-context.  The current paper’s focus on decision trees could be enriched by discussing how program induction aligns with EH rank’s sequential resolution.", "other_strengths_and_weaknesses": "The paper is a theoretically rigorous contribution that advances our understanding of Transformers’ computational limits. While its scope is narrow, its originality and formal insights lay groundwork for future research on CoT and neural architectures.", "other_comments_or_suggestions": "No other questions or comments for the authors.", "questions_for_authors": "**Question 1: Hard Attention vs. Practical Softmax Models**  \nThe paper establishes equivalences under hard attention, but real-world Transformers use softmax attention. **How do the authors anticipate their results generalizing to soft attention?**  \n\n---\n\n**Question 2: Combinatorial Fixation Assumptions**  \nThe lower bound for $k$-thOne relies on adversarial input fixation (Lemma A.2). **Do these bounds hold for inputs with probabilistic structure (e.g., i.i.d. 1s) or only worst-case inputs?**  \n\n---\n\n**Question 3: Multi-Layer Architectures**  \nThe paper focuses on single-layer decoders. **Can the EH rank framework extend to multi-layer architectures, given Chen et al.’s (2024) dimensional lower bounds for multi-layer soft-attention models?**  \n\n---\n\n**Question 4: Explicit Matrix Definitions**  \nTheorem 4.1’s Transformer construction lacks explicit parameterization of $W_1, W_2$. **Can the authors provide a full specification of these matrices (e.g., via block-diagonal structures or sparse encodings)?**  \n\n---\n\n**Question 5: Relation to CoT’s Circuit-Theoretic Power**  \nThe paper does not cite Li et al. (ICLR 2024), which shows CoT enables Transformers to solve **P**-complete problems. **How does EH rank align with CoT’s role in overcoming parallel computation limits (e.g., TC⁰ vs. AC⁰ separations)?**", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7KuCGFVkGV", "reviewer": "Reviewer_R7ST", "summary": "The paper studies the expressivity of one-layer Transformers with hard attention (in particular for Boolean functions), where it's shown that the Ehrenfeucht-Haussler rank of a Boolean function is equal to the number of (continuous) chain-of-thought (CoT) tokens that a single-head model has to produce to express the target label. The paper further extends this finding to multi-head single-layer Transformers and more general alphabets by defining appropriate ranks.\n\n## update after rebuttal\n\nI maintain my positive assessment for the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you a lot for your comments and questions. We respond to all three below.\n\n*Q1: What is the central message of the paper for the ML community?*\n\nThe ability of Transformers to perform function composition has garnered increasing attention in recent years, as understanding this capability sheds light on the computational resources they require to infer implicit knowledge from a given set of facts. Peng et al. demonstrated that single-layer, soft-attention Transformers without Chain-of-Thought (CoT) reasoning are fundamentally incapable of function composition. However, when CoT is introduced, they can achieve iterated composition—albeit at the cost of requiring a growing number of steps, which depends on both vector dimensionality and feature precision. Our work precisely quantifies the number of steps needed for t-th iterated composition and establishes that, under the idealized assumption of hard-attention, the number of required CoT steps is exactly t. This finding underscores a key insight: while CoT enables function composition, it does so incrementally—one step at a time. We believe this to be the central message for the ML community.\n\n*Q2: Can the arguments work with a decoder model that predicts discrete tokens belonging to a constant-size alphabet? (See 'Claims and Evidence' part)*\n\nOur argument works with discrete chain-of-thought tokens as well. Indeed, in our construction, CoT tokens essentially are used to maintain the one-hot encoding of the current node of the decision tree. In place of one-hot encoding, we can store these nodes directly in discrete tokens. \nWe do not know how to obtain our results with discrete tokens, belonging to the constant-size alphabet.  Note that in our setting, even input tokens do not necessarily belong to a constant-size alphabet (for example, in t-comp, input tokens come from the alphabet {1, …, n}).\n\n*Q3: In line 209 what is $u_{i_h}$?*\n\nThis should be $x_{i_h}$. Thank you for noticing this typo.", "claims_and_evidence": "The claims are supported by theoretical arguments and proofs. However, I have some concerns about the mathematical modeling of decoder-only Transformers in this paper. In particular, this paper assumes that CoT tokens are continuous arbitrary vectors and not predefined tokens. So I wonder if the results hold if we somehow limit the Transformer to a constant size (e.g., {0,1, EoL}) alphabet.", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "Yes, the theoretical arguments seem valid to me. See above for remarks on modeling.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "This paper studies the relation between CoT complexity and rank of Boolean functions for a specific class of Transformer functions. The paper does not provide any broad insight into the working mechanism of Transformers or large language models and is pretty shallow on the machine learning side. So I think the paper would be mainly of interest of a niche community of ML theory people.", "essential_references_not_discussed": "I think the original chain of thought and scratchpad papers should be cited.", "other_strengths_and_weaknesses": "The paper uses different notions and techniques from theoretical computer science. This makes the paper interesting but also hard to read. Nevertheless the writing is quite clear.", "other_comments_or_suggestions": "- When discussing the related work, some results depend on the size and depth of the models. It would be nice to discuss them in more detail. \n- Elaborating on the questions below could be helpful.", "questions_for_authors": "- What is the central message of the paper for the ML community?\n- Can the arguments work with a decoder model that predicts discrete tokens belonging to a constant-size alphabet? (See 'Claims and Evidence' part)\n- I think the decision trees could be defined and explained better. Do trees always have exactly $n$ queries? Is it always the same query at a particular depth? What is the meaning of the equation on line 121?\n- In line 209 what is $u_{i_h}$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This is a theoretical work providing theorems and insights on simple transformers. The high-level message is that there is a close connection between the minimal number of chain-of-thought steps a single-layer hard-attention Transformer needs and the function's rank (a well-studied complexity measure, mainly in the context of learning decision trees). Extensions to multi-head attention are also provided. 
Overall, the reviewers were positive about this work and uniformly supported the paper's acceptance.
Decision: Accept (poster)