Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

We thank the reviewer for the positive assessment of our paper. We particularly appreciate the reviewer's point that complexity lower bounds, as shown in this paper, tend to be harder to prove than upper bounds.

If possible, we'd like to kindly ask the reviewer to provide more justification supporting their score. We are concerned that, as the review is rather brief, it might be disregarded by the AC and other reviewers.

We thank the reviewer for acknowledging that our claims are supported by clear and convincing evidence. We now address all the concerns mentioned in the review:

1. On the restrictiveness of our approach due to the use of hard attention and binary input/output format:

   We agree that hard attention is a simplifying assumption, though it is amply supported by interpretability studies as we cited in Appendix E.1.

   Perhaps even more importantly, recent results also show that hard attention has the same expressiveness as the real-world transformer setting -- that is, UHAT can simulate the output of finite-precision soft attention transformers with causal masking [3]. Hence, real-world transformers cannot have asymptotically shorter CoTs than UHAT transformers. Thus, our results provably transfer to the real-world setup. We will highlight this in the final version.

   Regarding 0-1 digit operations, this is not a substantive restriction. The random restrictions technique has typically been applied to binary input strings in the past, which we follow for simplificity. However, the technique equivalently applies to strings over other alphabets, and, trivially, any finite alphabet can be encoded in binary. We will add explicit discussion, and a formal statement of the equivalence, in the final version of our paper.

2. On neglecting the logical progression in CoT reasoning:

   Our bounds hold irrespectively of the contents of the CoTs, including their logical structure. If the concern of the reviewer is that some of the tokens in the CoT may be less important than others, then it is not a problem for our proofs, since we treat all tokens as important.

3. On arbitrary assumptions, specifically $|{i ≤ N : ρ_N (i) = ∗}| ≥ CN$:

   We would like to point out that this is not an assumption; this is a property of a specific class of functions in Theorem 3.3. It formalizes the idea that a function stays constant on a set of strings "ignoring" many positions in those strings. Informally, if $|{i ≤ N : ρ_N (i) = ∗}| ≥ CN$ then with probability at least $C$ changing one bit in the input of $f$ won't affect the output; in other words, $f$ is insensitive. We will expand our informal explanation of the rationale behind the statement of the theorem. We will also be happy to add intuition on the meaning behind other assumptions if the reviewer clarifies which of them seem arbitrary.

4. On unexplained symbols:

   Note that the * in Definition 3.2 is just a plain symbol in the output space of restrictions: $\rho_N : [1,N] \rightarrow \Sigma \cup \{*\}$, also used in the condition $\rho_{|x|}(i) \neq *$. Other symbols are also either defined or standard notation, but we will take care to make the notation more accessible for a broader audience in the final version.

5. On experiments not supporting the statement that $O(n)$ is the lower bound of the complexity:

   We assume that by the sentence "O(n) is the lower bound of the complexity" the reviewer references the group of our statements imposing the $\Omega(N)$ bounds on the length of CoT required to solve specific tasks. Generally, our experiments supporting this group of statements show that all successful CoT strategies for the tasks we consider require at least $\Theta(N)$ steps. We agree that it does not prove that no other successful sublinear CoT strategy exists; however, proving such statement experimentally is challenging since it isn't feasible to test all possible CoTs. We are happy to extend our experimental design if the reviewer has any suggestions.

6. On relation to [1] (Feng et al. 2023) and [2] (Chen et al. 2024):

   The key difference to prior work on the theory of CoT is that our results provide provable lower bounds on the lengths of CoTs. This is the key advance compared to [1], which instead focused on showing that certain tasks require CoTs, but didn't study how many steps are minimally needed.

   [2] shows the relationship between the type of the CoT and the maximum difficulty of the task that an LLM can solve with that CoT. While these results are important, they leave the concept of difficulty undefined, and they also do not provide the bounds on the required length of the CoT. Therefore, while the results of [2] are generally applicable to more tasks, our work offers much more precise and rigorous results for specific tasks.

7. On discussing interpretability of the CoT:

   In the camera-ready version of the paper, we will include a discussion of the work on interpretability of CoT and cite the papers mentioned by the reviewer.

8. On excessively strong assumptions:

   We ask the reviewer to clarify which assumptions are referenced in this concern and which of them are stronger than those in [1]. It is hard for us to give an answer to this question without knowing details.

[3] Jerad et al. "Unique Hard Attention: A Tale of Two Sides." arXiv preprint arXiv:2503.14615 (2025).

We thank the reviewer for the positive assessment of our experiments and theorems and pointing out the strengths of our paper. We now address the concerns raised in the review.

1. In Appendix A, we explain in detail why our results for hard attention are relevant for real-world transformers, especially concerning CoT. We briefly reiterate the arguments below.

   First of all, many existing CoT constructions for soft attention in the literature (e.g., [1]) can be expressed in UHAT. Hence, even if lower bounds for soft attention don't directly follow from the lower bounds for UHAT, our impossibility results show that any sublinear solutions for considered tasks would likely to be hard to find.

   Second, prior work [2] established a correspondence between the unlearnability of certain classes of tasks for soft attention and their impossibility for hard attention. Thus, our lower bounds for UHAT expressivity shed light on lower bounds for learnability in soft attention (and those are directly supported by our experiments).

2. In addition to our arguments in Appendix A, there is new substantial evidence proving a correspondence between hard and soft attention that has not yet been mentioned in our paper. Recent work, published after we had submitted our paper to ICML, rigorously establishes that some versions of UHAT are functionally equivalent to real-world Transformer setup (finite-precision causal soft attention) [3]. That result expands prior work that had already established that finite-precision soft attention is contained in $AC^0$ [4]. This directly establishes the relevance of our results for the real-world LLMs, as they directly imply corresponding lower bounds for finite-precision soft-attention transformers. We will make this implication explicit in the final version.

3. Regarding the scalability of our experiments, we agree that scaling our experiments would further illustrate our conclusions. Initially, we limited our multiplication experiments to 16 bits due to computational resource limitations. We will scale up our experiments, and include the results in the camera-ready version of the paper.

4. The reviewer has also mentioned that our template is wrong. We are not aware of any mismatch between our template and the official ICML template recommendations. We ask the reviewer to clarify what exactly is wrong with the template, and we can fix those issues in the final version of the paper.

Finally, we kindly ask the reviewer to reconsider the score given to our paper. We would like to point out that the reviewer agrees that the paper is clear, experiments and theoretical results are thorough, and the claims are supported by convincing evidence. The only weaknesses mentioned are the UHAT assumption and the recommended scaling of the experiments, and we address those weaknesses above. Thus, we believe that the negative score assigned by the reviewer is unjustified given this list of strengths and weaknesses.

[1] Abbe et al. "How far can transformers reason? the globality barrier and inductive scratchpad." NeurIPS 2024.

[2] Hahn and Rofin. "Why are Sensitive Functions Hard for Transformers?" ACL 2024.

[3] Jerad et al. "Unique Hard Attention: A Tale of Two Sides." arXiv preprint arXiv:2503.14615 (2025).

[4] Li et al. "Chain of thought empowers transformers to solve inherently serial problems" ICLR 2024