Ehrenfeucht-Haussler Rank and Chain of Thought

Thank you kindly for all your comments and inspiring questions!

The claim that “multi-head attention cannot circumvent inherent sequential steps” applies only to t-Comp/k-thOne—not general tasks.

A 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.

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?

Yes, 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$.

There 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.

Re: the paper does not validate if $t\text{-Comp}$’s structure fully aligns with PC’s assumptions (e.g., cyclic dependencies).

Let 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.

Q1:

The 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.

Q2:

Great 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.

Q3:

We 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.

Q4:

The 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.

Q5

We 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.

Thank you a lot for your comments and questions. We respond to all three below.

Q1: What is the central message of the paper for the ML community?

The 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.

Q2: Can the arguments work with a decoder model that predicts discrete tokens belonging to a constant-size alphabet? (See 'Claims and Evidence' part)

Our 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. We 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}).

Q3: In line 209 what is $u_{i_h}$?

This should be $x_{i_h}$. Thank you for noticing this typo.

Thank you for all your valuable comments. Below we respond to some:

1. 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

Thank 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.

[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.

Let 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.

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.

We 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.

*3. It would be great to discuss the relations with previous works. What is the relation between the rank and circuit complexity?

Great 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. We 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.

Regarding some minor comments:

line 209 $u_{i_h}$ is not defined.

this is a typo, it has to be x_{i_h}, thanks for noticing!

line 344 should be the product of $f$ and $g$?

sorry, 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''

Thank you for the positive review and for noticing some typos!