Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
Authors: Alireza Amiri Bavandpour
Xinting Huang
Mark Rofin
Michael Hahn
Venue: ICML 2025 poster (2025)
Keywords: theory
lower bounds
chain-of-thought
transformers
Primary area: theory
TL;DR: We prove lower bounds for the length of chain-of-thoughts on algorithmic problems.

Abstract: Chain-of-thought reasoning and scratchpads have emerged as critical tools for enhancing the computational capabilities of transformers. While theoretical results show that polynomial-length scratchpads can extend transformers' expressivity from $TC^0$ to $PTIME$, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in $TC^0$, such as Parity or Multiplication, challenging optimistic bounds derived from circuit complexity. In this work, we initiate the study of systematic lower bounds for the number of CoT steps across different algorithmic problems, in the hard-attention regime. We study a variety of algorithmic problems, and provide bounds that are tight up to logarithmic factors. Overall, these results contribute to emerging understanding of the power and limitations of chain-of-thought reasoning.

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
Alireza Amiri'
Xinting Huang?
Mark Rofin
Michael Hahn
Abstract
JT
J011
20m1
1
0
1
1
0
Chain-of-thought reasoning and scratchpads have emerged as critical tools for enhancing the com- putational capabilities of transformers. While theoretical results show that polynomial-length scratchpads can extend transformers' expressiv- ity from TC to PTIME E, their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in TC such as PAR- ITY or MULTIPLICATION, challenging optimistic bounds derived from circuit complexity. In this work, we initiate the study of systematic lower bounds for the number of CoT steps across dif- ferent algorithmic problems, in the hard-attention regime. We study a variety of algorithmic prob- lems, and provide bounds that are tight up to log- arithmic factors. Overall, these results contribute to emerging understanding of the power and limi- tations of chain-of-thouge reasoning'.
Trarer
0
1
SEP
1 J01
0 2011
1 ATTO
1 JYTI
Figure I: High-sensitivity problems such as PARITY are dif- ficult to learnably and generalizably represent for transform- ers. Such problems can be solved by CoTs decomposing them into sequence of local steps. We study the length that such CoTs need to have, function of the input length.
quences without compromising quality became an important research direction (Deng et al., 2024). At the same time, there is far little understanding of the minimal sufficient length of the CoT in a given case; thus the theoretical limits of CoT compression are unclear.
To gain understanding of those limits, we take up the prob- lem of provably bounding the length of CoT sequences sufficient to solve various algorithmic problems with trans- formers. By providing the lower bounds the length of the CoT, our paper complements established line of research on the expressive power of transformers that has focused on the model size when the answer is provided without CoT (e.g. Strobl et al., 2023; Bhattamishra et al., 2020a; Sanford et al., 2024b; Chen et al., 2024).
1. Introduction
Chain-of-Thoughe reasoning (CoT) has become standard practice for solving hard problems with LLMs, enhanc- ing the capabilities of Transformers (Nye et al., 2021; Wei et al., 2022b) and powering a new generation of state-of- the-art models, such as OpenAI ol (Jaech al., 2024) and DeepSeek-RI (Guo et al., 2025). Models trained under this paradigm are optimized to generate long CoT before answering any user's request, which significantly elevates their reasoning abilities. However, the use of CoT may sub- stantially increase the number of tokens produced by the model and raise the inference costs (Han et al., 2024), in some cases reaching millions of tokens for a single task (Chollet, 2025). Hence, shortening the generated CoT se-
A simple example is the PARITY function deciding whether the number of I's in bit string is even odd. Transformers empirically struggle to learn it on longer in- puts (e.g. Bhattamishra et al., 2020a; Delétang et al., 2023; Butoi et al., 2024; Hahn & Rofin, 2024), and this difficulty is resolved by a CoT consisting of the parities of increasing prefixes, as Figure/ (e.g. Anil al., 2022). Here, every decoding step depends only on a bounded number of tokens. However, for input of length N, this CoT requires (NN) extra decoding steps, substantial computational burden.
'Sharif University Technology. Work done in part while interning at Saarland University. 'Saarland University. Correspon- dence to: Michael Hahn <mhahn centtuni-saatt saarland.de>..
Proceedings of the 4rnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
An interesting and pertinent question is thus whether such a linear-length CoT is optimal, or whether a shorter CoT might exist. The goal of this paper is to develop explicit and unconditional bounds on the length of CoT's This
CCode link: https:/ http://ggtthubbh htt.hhhb..oomccccc waaam//accoo-i1 lab/ scratchpaddbecune

---

Lower Bounds for CoT Reasoning
question is analogous to the classical question of bounding the time complexity of Turing machines. We argue that it is of foundational interest in the context of LLM-based systems relying on CoT reasoning (Jaech et al.. 2024; Guo et al., 2025).
functions that, like PARITY, are simultaneously sensitive to every input bit, and hence do not practically learn them on long inputs; sharpness is starkly reduced in the presence of COT.. In fact, the result of Hahn & Rofin (2024) extends be- yond PARITY, and is grounded in a foundational concept in the analysis of Boolean Functions, sensitivity. For a boolean function f {0, 13" - {0, 1), the sensitivity counts how many Hamming neighbors have the opposite output:
We study this question in the unique-hard attention (UHAT) regime, a popular theoretical abstraction of self-attention, in which every attention head attends to the unique posi- tion where attention weights are maximized (e.g. Hahn, 2020; Hao et al., 2022; Barceló et al., 2024; Svete & Cot- terell, 2024; Bergsträfßer et al., 2024; Yang et al., 2024; Barceló et al., 2025). Importantly, bounds in this regime entail bounds on realistic softmax transformers operating at fixed precision, as their expressiveness is upper-bounded by UHAT (Jerad et al., 2025).
8 ( x) = |(i 1,..../a such that f(x) # (xx
|x|
(I)
where x 0 is obtained from x by flipping the i-th bit. The av- erage sensitivity is defined as the average over the Hamming
cube, at string length N (e.g. O' O'Donnell, 2014):
asx(f)
1 2N
Σ DE(1
s(f.z)
(2)
In this model, we rigorously prove that the CoT for PARITY described above is optimal up to constant factors (Theo- rem 4.2), Besides PARITY, we consider three other tasks (MULTIPLICATION, MEDIAN, REACHABILITY) that are also empirically challenging for transformers to solve with- out COT. Across tasks, we show that CoT lengths need to scale at least linearly in the size of the original problem. We further show that our bounds are optimal up loga- rithmic factors. Overall, these lower bounds place broad constraints on the inference- -eteennce-timeeeeeee compute needed to enable transformers to solve these problems.
In PARITY, flipping any bit flips the output, hence asN (PARITY)= N. Hahn & Rofin (2024) show that such linear growth of sensitivity with input length produces high sharpness in transformers' loss landscapes. This unifies a string of empirical results finding that transformers have an inductive bias towards low average sensitivity (Bhattamishra et al., 2023; Vasudeva et al., 2024; Abbe et al., 2023). Hahn & Rofin (2024) applied this result to the PARITY function; but, in this paper, we identify range of other tasks also fac- ing linear growth of sensitivity, including tasks within TC"0 (MULTIPLICATION and MEdIan), and task conjectured not to be in TC (REACHABILITY), We thus overall
2. Background
2.1. Sensitive Functions Require CoT's
focus on algorithmic tasks with as (f) = O(N).
Prior work has often studied the abilities of transformers through the lens of circuit complexity (e.g. Hao et al., 2022; Merrill & Sabharwal, 2023a; Strobl, 2023; Feng et al., 2023; Li et al., 2024; Chiang, 2025; Merrill & Sabhar- wal, 2023b). Transformers express a subset of the circuit complexity class TC", which covers problems solvable by bounded-deye depth threshold circuits (Merrill & Sabharwal, 2023b; Strobl, 2023; Chiang, 2025). By the unproven con- jecture TC * NC². many problems, such graph reach- ability, are thus not solvable by transformers without CoTs. Hence, the success of CoT has been linked to its ability to expand expressiveness beyond TC (Feng et al., 2023; Merrill & Sabharwal, 2024a; Li et al., 2024).
including both tasks within TC and tasks conjectured to be outside it.
2.2. Model of Transformers
The theoretical literature on transformers has developed var- ious formal abstractions of transformers. In this paper, we study the regime of unique hard attention (UHAT), a popu- lar theoretical model of self-attention, where every attention head attends to the unique position where attention scores are maximized (e.g. Hahn, 2020; Hao et al., 2022; Barceló et al., 2024; Svete & Cotterell, 2024; Bergsträßer et al., 2024; Yang et al., 2024; Barceló et al., 2025). UHAT is an appealing modeling choice, both because strong techniques for proving lower bounds are available (see Section 3), and because interpretability work shows that language models heavily rely on heads focusing their attention on few posi- tions (e.g. Cabannes et al., 2024; Olsson et al., 2022; Clark et al., 2019; Voita et al., 2019; Ebrahimi et al., 2020).
However, CoT is empirically beneficial even for tasks well in TC such as PARITY (Anil et al., 2022): PARITY is ex- pressible in TC and also by certain models of transformers (Chiang& & Cholak, 2022; Kozachinskiy, 2024), but practical transformers consistently struggle to learn it via SGD in long inputs (e.g. Bhattamishra et al., 2020a) unless a CoT is provided (e.g. Anil et al., 2022). Hahn & Rofin (2024) show that this fact can be explained in terms of the loss land- scape: Transformers require very sharp minima represent
We now introduce the relevant notions and notation. We assume a finite alphabet Σ, with token embeddings e(o) E Rd. There further are positional encodings
2

---

Lower Bounds for CoT Reasoning
P1. P2: Ps...... Pamuz RRd where maaz is the maximal context size of the transformer. We consider an input string E Σ", with length |a|| = N.. We define the activations y, E IRd at position i of the k-th layer (k- 1..... follows. The zero-th layer consists of token and positional encodings: y; (0) = e(x;)) + P: (i = ,.....,, N.. In each layer 1 = 1,..., L, we first compute attention scores for the h-th head (h- 1....,HH) H):
We write Ey to be the (finite) set of symbols appearing in at least one string zg(x:) for with |ac| N.
We note that E is not restricted to be fimite. Some theoretical work has allowed the CoT vocabulary to grow with the input length (Bhattamishra et al., 2020b; Abbé et al., 2024); our lower-bounds are robust to this.
, I.) as
We now formalize what it means for CoT to be expressible in UHAT. For maximal generality, we assume a relaxed definition: rather than requiring that a single transformer perform the task across all input lengths (which makes it hard to distinguish unboundedly many positions), we only ask that a family of transformers perform the task with a bounded number of layers and heads:
(k.M) (k- 1 K QUA.D (* (k-1) 0ij -
where K ("key"), QK ("query") are Rdxd In soft- are then obtained
max attention, the attention weights 2 via the softmax transform. In the UHAT model, these are idealized as one-hot weights:
Definition 2.2. We say that transformer T computes the CoT g(z) on input x E Σ" if all symbols in 2=(2)) appear in (3) the vocabulary of T and [arg(=)] is bounded by the maximal context window, and if, when T is run on xg(#), its output at position |x| + is a one-hot vector with "one" at the index corresponding to g(z)); E E, for fori-
exp(a..) (k.h))
(k.h)
[Softmax]
Ee=1 exp(a (k,h))
(k.
1
j j= aarggg max dis
(k.h)
[UHAT]
(4)
lg(.).
0
else
We say that the CoT g(x) is expressible in UHAT' across input lengths if, for each input length there is a UHAT transformer Tn computing g(z) for all [zg(()) = n, and the numbers of layers and heads are uniformly bounded.
The UHAT model can be viewed as the limit of the Softmax model when one attention score Og,, far exceeds the others. If more than one attains the maximal attention score, ties are broken according to some fixed rule (e.g.. choosing the left- or right-most match, Yang et al. (2024); Jerad et al. (2025)). The output of the attention block is computed by weighting according to attention weights (kk.)) (j s i)?, and applying a linear transformation V ("value")); these are then aggregated across heads and combined with a skip- connection:
While we bound layers and heads, we do not expect the width to necessarily stay bounded, which allows positional encodings to keep all unboundedly many positions distinct. This is a very weak requirement, a necessary precondition for the existence of single length-gencralizing transformer across input lengths, and much more relaxed than the degree of uniformity often assumed in lower bounds for transform- ers (e.g. Merrill & Sabharwal, 2023a; Huang et al., 2024). It is nonetheless sufficient for proving essentially matching lower and upper bounds.
H
y: = MIP
1k-1)
(k.h)) VENyY
1k-1)
y
(5)
where fMLP: Rd > Rd. For our purposes here, MMP may be arbitrary. Finally, next-token predictions are made by T = yn
3. Results: Generic CoT Bounds
(2) for some parameter O E RREE xd, where we are assuming some numbering of the alphabet E.
Our goal is to study the required length of the CoT [g(x)] as function of the input length |ær]. under the constraint that the CoT expressible in the sense of Def. 2.2. Following standard practice in computational complexity, we focus on the worst-case complexity, which - for given input length N, amounts to maX.|[a] N g(())-
2.3. Formalizing CoTs
Definition 2.1. Let E be finite alphabet. Given a function f: Ex + Σ and an alphabet E 3 Σ, shain-of-thougih (CoT) is map g: E' + E + ending in the suffix fz).
It is well-known that transformer CoT' are universal in the sense that they can simulate Turing machines (Pérez et al., 2019; Bhattamishra et al., 2020b: Hou et al., 2024; Merrill & Sabharwal, 2024a; Malach, 2024; Wei et al., 2022a: Qiu et al., 2024). Constructions use variety of assumptions about attention; we first note that this property holds in our setup:
"W assume causal masking in line with standard language model architectures, in order to allow autoregressive generation of the COT. Our techniques are also applicable to the setting where the input itself is processed with bidirectional attention assumed by Abbé et al. (2024) (Remark B.7).
'Transformers additionally implement layer norm (Ba et al., 2016). Our bounds are robust to such position-wise operations. For instance, layer norm following the MI. can be absorbed into JMLP for the purposes of our theorems.
Fact 3.1 (Universality of UHAT CoTs), Consider a Turing machine that terminates within S T(N) steps on all inputs
3

---

Lower Bounds for CoT Reasoning
of length < N. Then there is COT g(x) over a countable alphabet E computing the output of the Turing machine, with length [=(x)) (Ir())), expressible in UHAT.
Theorem 3.3 is shown via Lemma 3.4, an analogue of the classical Switching Lemma (Hastad et al., 1994) for AC circuits, which permits collapsing bounded-depth circuits into shallow circuits on pΣ Like that classical lemma, it is based on randomizing p and showing that the probability of satisfying the desired properties is nonzero; hence, a satisfying P exists.
The construction is discussed in Appendix B.3. As conse- quence, all PTIME problems have polynomial-lenglte CoTs and problems outside of PTIME cannot have polynomial- length CoTs (Merrill & Sabharwal, 2024a). More generally, CoT is upper-bounded by Turing machine time complexity. The converse does not hold: Many problems have efficient parallel algorithms that can be expressed by self-attention without any CoT. As a simple example, the Boolean AND function of N variables requires (2(N) steps with a Turing machine, simply because every input needs to be considered in the worst case, but it can be represented by a very simple transformer with just one attention head, and no CoT. Our main technical contribution in this paper is to show that a diverse set of algorithmic problems do require long CoTs, of length linear in the input.
Lemma 3.4. Given a UHAT transformer T operating over the finite alphabet E,, and & (0, 1), there is N, K E N (c and K each only depending on the number of layers and heads, and [E)), and a restriction p such that
1it S N: :NN(1) - CN
(1) (i E [1. I 2. On EN n OpE", each activation y.
[1, T.) depends only on at most e. input positions
The lemma is strengthening of Theorem of Hahn (2020), the proof is in Appendix B.1. Note that Lemma 3.4 applies to transformer computations without CoT, whereas Theo- rem 3.3 broadens the scope to functions computable with olN)-tengt Co'.. In order to deduce Theorem 3.3, we first apply Lemma 3.4 to obtain restriction on the input x itself (not the CoT tokens). We then show that it is possible to fix c H L [g(x)) further input symbols to fix every symbol appearing in the CoT, and hence the function output (z). If [9(x)) = o(Iz]), the resulting restriction still leaves a con- 9 stant fraction of input positions free (say, TO CNN positions). We provide the full argument in Appendix B.1.
Our key technical tool, and first central result, is a generic CoT lower bound (Theorem 3.3). In order to state and prove this bound, we use the method of random restrictions, a key technique for understanding bounded-depth circuits (e.g. Hastad al., 1994; Furst et al., 1984; Boppana, 1997) and transformers (Hahn, 2020).
Definition 3.2. Let N be an input length. A restriction p is a family of maps PN : [] + 1, .... We write pΣ* for the set of strings E* where I, (i) whenever (i) * *.
E [*),, for N
We show that the existence of sublinear-length CoT has strong implications for the function computed.
4. Results: Application to Algorithmic Problems
Theorem 3.3 (Generic CoT Bound). Assume that has UHAT-expressible CoT g(x) of length la(x)) = (zz)). Choose any C' E (0,1). Then there is restriction such that
We now proceed to proving explicit lower bounds for vari- ous algorithmic problems. For each problem, we first exam- ine sensitivity to establish difficulty for transformers based on the results reviewed in Section 2.1 (independent of un- proven conjectures about TC For high-sensitivity prob- lems, then use Theorem 3.3 to lower-bound CoT length, and construct explicit CoT that matches the bound up to logarithmic factors.
1. Mi (N() = = CN for sufficiently large N
2. For each N, f is constant on EN OpE
The first condition says that leaves large fraction of input positions open; the second condition says that it is nonetheless sufficient for fixing the output.
4.1. Lower Bounds for Regular Languages
Definition 4.1. PARITY takes an input x 1 and decides if the number of I's is even or odd.
A simple example of a UHAT-computable function is the AND function, where fixing single bit 0 fixes the output to 0; it is easily computed by UHAT transformer where single attention head attends to occurrence of 0 if any exists. Even though every bit can potentially matter to the output, this is casily computed in UHAT without COT. On the other hand, the PARITY function cannot be fixed by fixing any strict subset of the input bits; hence, Theorem 3.3 entails linear-length lower bound for CoT there.
PARITY is the archetype of seghly-sensitive function, with as,, (PARITY) = n, and it has long been documented empir- ically that transformers struggle with it (e.g. Bhattamishra et al., 2020a; Delétang et al., 2023; Anil et al., 2022; Butoi et al., 2024): We provide the following lower bound:
Theorem 4.2. Any UHAT CoT for PARITY has length Ω ((N)..
4

---

Lower Bounds for CoT Reasoning
The proof is a direct consequence of Theorem 3.3: as long as one does not fix all input symbols, one can never fix the output of PARITY. The UHAT bound is tight, and is attained by the straightforward CoT consisting of the parities of increasing prefixes of the input.
Full CoT
Dot-by-Dot CoT
500
500
Acc
Acc
Langhh
300
68
200
3.5
200
077
100
0.7
We note that Theorem 4.2 is substantively different from bounds based on learnability arguments applying to sub- set parities (e.g. Kim & Suzuki, 2024; Abbé et al., 2024; Abbe et al., 2023; Wies et al., 2022), distinct from the PAR- ITY function applying to the full input (see Section 5 for discussion).
100
0
100
220
300
400
50C
20
00
Imput Length
Inpul Length
Figure 2: Results for PARITY. Left: CoTs consisting of prefix sum parities, accuracy as a function of input and CoT lengths. CoT' of length (NN) succeed even very long inputs. Right: Dot-by-dot scratchpads help much less, even when much longer then the input (Theorem 4.11).
Why is Theorem 4.2 nontrivial? At first sight, one might wonder if Theorem 4.2 is trivial: Every bit matters for PAR- ITY, and hard attention head can only attend to a single position; hence, one might be tempted argue that lin- number of CoT steps is trivially needed to take every bit into consideration. However, importantly, the behavior of the attention heads itself is input-dependent and can in principle be influenced by every input bit. While each head in UHAT attends to only one position, the entire input glob- ally determines which position this is (e.g., for the boolean AND function of N bits, even though every bit can matter, single head is enough). Key to showing Theorem 4.2 is that it is sufficient to fix fraction of input bits to "distract" all attention heads and prevent them from considering the full input. More broadly, our results establish a dichotomy on simulating finite-state automata:
4.2. Multiplication
We next examine basic arithmetic operations. For N-digit numbers, both addition and multiplication are in TC', and both operations can in principle be expressed by soft- attention transformers (Feng et al., 2024), but empirical research has found transformers to succeed much better at addition than at multiplication, which remains hard for transformers (Yang et al., 2023). Addition has low sensi- tivity and can be represented in UHAT and fixed precision (Feng et al., 2024); multiplication is shown expressible by unbounded-preecision transformers but not fixed-rreisiioin transformers (Feng al., 2024). We examine the difficulty of computing each of the 2N output digits in multiplication.
Corollary 4.3. Let f be the membership problem of a finite- state language L. Then exactly one of the following holds:
Definition 4.4. Given two N- integers X, Y encoded in binary, let M& be the k-th bit of the binary representation of the product XY.
1. L. E AC and f is expressible in UHAT without Co'l'
Multiplication has high sensitivity; most importantly and interestingly, it turns out that digits in the middle of the result are particularly sensitive (Figure 7). For these: Theorem 4.5. A UHAT CoT for MN requires length ((N).
2. L & ACO, and any UHAT CoT for f has length (2N)
The proof is in Appendix C.I.I. Importantly, f is affected by the sensitivity- if and only T. & AC (Remark C.2). Overall, this result complements results on transformer shortcuts to automata (Liu et al., 2023) by establishing when a shorteut (i.e., a solution with CoT) can be represented well by transformers.
barrier discussed in Section 2.1
The proof is in Appendix C.2.1. Importantly, addition faces such hurdle, as any digit has at most polylogarithmic average sensitivity due to the existence of an AC (and UHAT) construction for adding -iiigit numbers without CoT (Feng et al., 2024); thus, transformers can output each digit in parallel better for addition than for multiplication (Figure 12).
Experiments We trained transformers on PARITY on lengths between and 500 (Figure and Appendix 1.2.2; results averaged across three runs). We considered the full CoT from Figure I (dots along diagonal line). We also con- sidered CoTs where only every k-th step of the CoT was provided, shortening the CoT by 1/k (dots below diagonal line). Across input lengths, the model is successful when k & 3. We also verified that two LLMs (DeepSeek-R1, Guo et al. (2025), and ol-mi Jacch et al. (2024)) produce CoTs of at least linear length (Figure 6).
Given our ((NN) lower bound (Theorem 4.5), what is the best upper bound? Existing work providing scratchpads for transformers performing multiplication (Hou et al., 2024) uses the naive grade-school algorithm, which has O(N2) complexity, much larger than the 2(N) lower bound. In fact, there is a UHAT scratchpad matching the ((NV lower bound up to a logarithmic factor:
Theorem 4.6. There is UHAT scratchpad for the full
5

---

Lower Bounds for CoT Reasoning
Correct Predictions per Digit Position
Definition 4.7. Consider the MEDIAN task, where the input consists of N numbers, each with B bits, and the target is the [N/2] -th number when the list is sorted.
1000
TC circuits solve this by selecting the number that is si- multancously smaller than and greater than [N/2] other numbers. However, the median, especially its last bit, is sensitive to alterations of the N integers (Appendix C.3). We obtain a CoT bound:
Correct Prodect
6002
4000
Theorem 4.8. For the MEDIAN task, UHAT scratchpad requires length ((N). This bound is attained.
14
Position
The proof is in Appendix C.3; the bound is attained by a CoT enumerating the lowest [N/2] numbers.
Figure 3: Accuracy of a transformer trained on autoregres- sive 12-digit multiplication (most significant digit at the left, zero-padded on the left), on a test set with 10K number pairs. High-sensitivity digits in the middle show substan- tially decreased accuracy even if digits at beginning and end are predicted exactly. See Figure& 8 for more.
Experiments We trained transformers on MEDIAN on input lengths between 6 and 398 (Figure 5 and Ap- pendix C.3.2), corresponding to to 99 decimal numbers (each with B digits). We considered the full CoT (upper most dots in each input length). Like PARITY, we also con- sidered CoTs where only every k-th step of the CoT was provided (starting from the smallest number), shortening the CoT by 1 (dots below the upper most dots in each input length). Across input lengths, the model is always successful when using the full CoT,, and there is a chance of failure when &s > 2 (accuracies are averaged over 3 runs).
product, M1... M2N. with length O(N log N).
The construction is based on the Fourier transform (Ap- pendix C.2.3).
Remarks Theorem 4.5 concerns direct decoding of an individual digit Mx; we comment on barriers on autore- gressive decoding of products in Appendix C.2.2. Recent work has found that custom positional encodings which match structurally corresponding digits to help with addition (Zhou et al., 2023; McLeish al., 2024; Cho et al., 2024a;b; Sabbaghi et al., 2024). Theorem 4.5 holds for arbitrary posi- tional encoding vectors, suggesting that, while beneficial in the case of ADDITION, specialized positional encodings are insufficient to overcome the difficulty of MUL.TIPLICATION.
4.4. Graph Reachability
Another foundational aspect of reasoning is graph reacha- bility.
Definition 4.9. Given a set of vertices V and set of di- rected edges E C V x V, the Reachability task is defined as follows. Input: Given some numbering of V, we assume a list of all edges E, cach coded as a pair of log V-digit binary numbers. We also assume a query pair of two vertices i, j, Output: A binary label, indicating if there a path from i to j.
Experiments We trained small transformers (2 layers, 2 heads) multiply binary numbers with up to 16 digits, either directly, with the O(N log N) CoT from Theo- rem 4.6. Multiplication failed to generalize when no CoT was given (Figure 12), with difficulty driven by the high- sensitivity middle digits (Figure 3). The CoT succeeded at all lengths up to 16 (Table 1).* See Appendix C.2.4 for de- tails. We also verified that two LLMs (DeepSeek-RI (Guo et al., 2025) and ol-mini (Jaech al., 2024)) produce CoTs of at least linear length (Figure 6).
The reachability problem in graphs, even in directed acyelic graphs (DAG), is NL-complete (Jones al., 1976); hence, by the unproven conjecture TC # NC is expected not to be solved by transformers without CoTs. We provide an unconditional lower bound, even for sub-family of graphs for which the reachability problem is solvable in TC', by observing that PARITY is reducible to DAG reachability:
Theorem 4.10. There is family & of DAGs inside which reachability is solvable in TC", but cannot be represented by a transformer at sublinear average sensitivity. A UHAT CoT needs length f2 ( log VV). This bound attained.
4.3. Order Statisties
We next consider another task in TC which concerns finding order statistics.
The proof proceeds by coding PARITY into DAGs with 2N vertices (lower bound), and coding breadh-fine search into CoT (upper bound), see Appendix C.4.
We focused extensive experiments to numbers of up this length due to resource constraints.
6

---

Lower Bounds for CoT Reasoning
Experiments We generate random DAGs with sizes rang- ing from 5 to 35 vertices and them train Transformers to solve a DAG reachability task in the general case with O(E) log |lee-hhntth scratchpad. The results, presented in Figure 4, show that a scratchpad of this length indeed suf- ficient to solve the task. contrast, a model trained without a scratchpad performs at chance level. See Appendix C.4.2 for details.
200
150
Acc
1.00
CoT Length
0.75
100
0.25
0.00
1.0
0
100
200
300
400
Input Length
Aocuracy
0.8
Scratchpad No scratchpad
Figure 5: Results for MEDIAN: CoTs consisting of the sorted first [N/2] numbers. Accuracy as a function of input and CoT lengths.
0.8
100
200
300
400
500
600
Input length
lengths at which transformer is learned successfully.
Figure 4: Results for DAG reachability. Without CoT, the model performs at chance level for all but very small graphs. An ( log [V] |Vengghgthh CoT leads to a perfect accuracy
5. Discussion
5.1. Implications
independent of the graph size.
Across Sections 4.1 our lower bounds are tight up to polylogarithmic factors. By showing that the UHAT CoT length must scale with the input length, they provide barri- ers on the possibility for self self-attention solve these tasks with small inference-time compute in generating additional tokens.
4.5. Limitations of Dot- CoTs
Recent work has observed benefit even for CoT's con- sisting just of repetition of single token ("pause token"), which might give transformer the opportunity to perform extra computations even without outputting any intermedi- ate steps (Goyal et al., 2024; Pfau et al., 2024). While the power such "dot-by-dot" CoTs remains in TC', provided their length is polynomially bounded, they may still enable additional computations (Pfau al., 2024), which raises the potential challenge of unauditable unobservable computa- tions in LLMs. Our methods result in additional barriers for such CoTs, suggesting that high-sensitivity computations require a substantial degree reliance on explicit CoT to- kens. Specifically, for PARITY, such COT cannot have polynomially bounded length:
An attractive approach for shortening CoT reasoning and re- ducing inference-time compute is by fine-tuning transform- ers to perform reasoning in fewer and fewer steps (Deng et al., 2024). Our results show that such a process is likely to run up against representational limitations of the archi- tecture. The findings demonstrate efficiency limitations to CoTT-baee reasoning that might be overcome via tool use or stronger architectures. Logarithmic growth of the depth may be one way to overcome these (Merrill & Sabharwal, 2024b); within fixed-depth architectures, certain SSM archi- tectures overcome at least the difficulty of PARITY (Grazzi et al., 2024). remains to be understood if this applies to the other problems from Sections 4. 1-4.4.
Theorem 4.11. Consider a UHAT-expressible CoT for PAR- ITY where g(x) has the form ..... # fxx). ("dot-by-dot CoT"). Then 19(x)] w(x f for any le E N.
5.2. Related Work
The proof is in Appendix B.2. Complementing this lower bound, exponentially-sizze UHAT CoT does exist in principle (Appendix B.2). Overall, we have thus a super- polynomial separation between the lengths required for full CoTs (O(N) and dot-by-dot CoTs (N))))((N)))
Theoretical Understanding of Seratchpads and CoT The first theoretical study of scratchpads for transformers is by Pérez al. (2019), who showed that transformers can autoregressively simulate the computations of Turing machine. More recently, work has shown that polynomial- length CoT can allow transformers to transcend the com- plexity class TC (Feng et al., 2023; Merrill Sabharwal, 2024a; Li et al., 2024), and express all problems PTIME,
Experiments Figure 2B shows that a by- variant of the CoT for PARITY is not successful expanding the

---

Lower Bounds for CoT Reasoning
PARITY
MULTIPLICATION
MEDIAN
Number of tokens the
5000
DespSonk-R1
01-mini
Number of tokems in the CoT
DeapSeak-R1
01-mini
Number of tokens in the CaT
10000
--- DeapSeck-R1
o1-mini
4000
8000
3000
4000
6000
2000
4000
2000
1030
2000
0
20
40
60
8
20
40
80
80
Length of the bitstring
Number of digits
Sequence length
Figure 6: Length of reasoning traces of DeepSeek RI (Guo et al., 2025) and o1-mini (Jaech et al., 2024) LLMs prompted to solve the tasks of parity (left), multiplication (center), and median (right). We only include traces leading to the correct answer. In both cases, the growth of CoT appears at least linear. Manual inspection of reasoning traces of DeepSeek R1 shows that the model perform the counting of all ones for PARITY, and the naive quadratic algorithm for MULTIPLICATION. The experimental details are provided in Appendix D.
which by widely believed but unproven conjectures far ceeds TC There are also lower bounds for scratchpads for single-layer transformers (Peng et al., 2024; Barceló et al., 2025), showing that a one-layer transformer (both the input itself and the CoT are processed by a single layer) requires a substantial number of steps to solve certain problems, such as iterated function composition. Chen et al. (2024) ex- tended this line of work to multi-layer transformers, proving benefit for CoT in iterated function composition.
2025), for autoregressive transformers (Chen et al., 2024), and for tength-generalizg transformers (Huang et al., 2024) relying on communication complexity or VC dimension.
Relation to Results on Subset Parities Our results con- cerning PARITY are distinet from results on Subset Parities. A long string of results has established difficulty of learning subset parities that is, parity functions restricted subsets U C {l..... Nj in various setups, and established bene- fits for providing intermediate steps (e.g. Wies et al., 2022; Abbe et al., 2023; Kim & Suzuki, 2024; Yang et al., 2025). Intuitively, the difficulty of learning subset parities emerges from the fact that one has to identify the set U from the exponentially- large power-set. In learning such functions, there is a provable benefit to providing intermediate steps in training (Wies et al., 2022; Abbe et al., 2023; Kim & Suzuki, 2024; Yang et al., 2025). However, this argument does not readily imply that causal transformers will find the PARITY function difficult to learn and that CoTs will help there, because the PARITY function applies to a very specific set (U {I,..., N)). Our results thus are distinct from results on subset parities due Wies al. (2022); Abbe et al. (2023); Kim & Suzuki (2024); Yang et al. (2025). Interestingly, Abbe et al. (2024) show that PARITY may be easy to learn for MLPs with Rademacher initialization; however, this requires a weight norm substantially growing with N, making transformer length generalization unlikely (Huang et al., 2024).
Another angle to understanding CoT's is via learnability ar- guments (Wies et al., 2022; Kim & Suzuki, 2024; Hahn & Goyal, 2023; Abbé et al., 2024). A particularly promising angle is the globality degree (Abbé et al., 2024), with poten- tially broad implications for scratchpads, though resulting lower-hounds remain largely conjectural beyond special cases (Appendix E.2). Interestingly, the globality degree is linked to our sensitivity- principle lead to stronger bounds; future full proof of the main conjecture of Abbé et al. (2024) would, in combina- tion with our unconditional results here, entail even further results (Appendix E.2).
techniques and could in
Lower bounds for transformers Lower bounds for UHAT transformers primarily rest on random restrictions, either directly (Hahn, 2020; Barceló et al., 2024) or via re- duction to known circuit bounds proven with those (Hao et al., 2022). A key technical step in our work to expand the reach of the random restriction technique to transform- ers including CoTs. Another approach obtaining lower bounds relies on circuit conjectures from computational complexity (Merrill& & Sabharwal, 2023b; Sanford et al., 2024a) and is thus conditional on these (widely believed) conjectures. There are further techniques for single-layer transformers (Kozachinskiy, 2024; Peng et al., 2024; San- ford et al., 2024b; Bhattamishra et al., 2024; Barceló al.,
Mechanistic Understanding of CoT Concurrent with the theoretical line of work, the mechanisms behind the CoT abilities in LLMs have been studied empirically. Wang et al. (2024) used path patching to identify attention heads critical for CoT and found that only a few attention heads are important for that. Dutta et al. (2024) showed that LLMSs
8

---

Lower Bounds for CoT Reasoning
employ multiple neural pathways that work in parallel to generate the final answer, all writing the residual stream. Kudo et al. (2024) demonstrated for arithmetic reasoning that single-step subproblems can be solved by LLMs even before the seratchpad hegins, while more complicated tasks are solved during CoT generation.
Author Contributions
MH coordinated the project. All authors contributed to the conceptual framework. Experiments were contributed by AA (Section 4.2), XH (Section 4.3), MR (Section 4.4), and MH (Sections 3, 4.1, and 4.5). MH contributed the bounds for UHAT transformers, with input from the other authors. AA and MH jointly developed theory in Section 4.2.
5.3. Limitations and Open Questions
One limitation of our bounds is that they apply in the worst- case setting. Providing average-case bounds is an interesting problem for future research. second limitation of our results is that they focus on the UHAT model, while there other formal models of transformers (e.g. log-precision transformers, Merrill & Sabharwal (2023a)). Our results pose the open question whether some other model might enable substantially shorter but still learnable CoTs:
Acknowledgments
Funded by the Deutsche Forschungsgecmeinschaat (DFG, German Research Foundation) Project-ID 232722074 SFB 1102. The authors thank Satwik Bhattamishra, Will Merrill, Sophie Hao, Anej Svete, Franz Novak, Ryan Cot- terell, Emmanuel Abbé, and Andy Yang for discussion, and Yash Sarrof and Entang Wang for feedback on the paper.
References
Open Problem 5.1. Are there sublinear-length Co'I' for any high-sensitiving problem from Sections 4.1-4.4 that are expressible by some formal model of transformers (other than UHAT; e.g., log-precision transformers), while being practically learnable?
Abbe, E., Bengio, S., Lotfi, A., and Rizk, K. Generaliza- tion on the unseen, logic reasoning and degree curricu- lum. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Con- ference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceed- ings of Machine Learning Research, pp. 31-60. PMLR, 2023. URI. punttts://prooeee ngs. ml r. press/
Solving this problem in the affirmative might have sub- stantial implications for real-world LLMs, and any such solution is likely to require further progress in understand- ing the learnability properties of transformers. On the other hand, a negative answer might suggest that tool use or ar- chitectural improvements are likely to be unavoidable for wansformer-basel LLMs even on many TC" problems, due to architectural limitations that make successful CoTs im- practically long.
v202 abbe23a. html.
Abbé, E., Bengio, S., Lotfi, A., Sandon, C., and Saremi, O. How far can transformers reason? the globality barrier and inductive scratchpad. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024. URL /tttttts:////peeeeeeeeee wwwpreeveeeeeeeeeeeeeeeeeeeeeeee net/ forum? 1 (d=FoGwiFXxin
Abbe, E., Cornacchia, E., Hazła, J., and Kougang-Yone Yombi, D. Learning high-degree parities: The crucial role of the initialization. arXiv preprint arXiv:2412.049100 2024.
6. Conclusion
The success of scratchpad and chain-of-thoupe techniques raises the need to understand their strengths and limitations. Here, we have provided lower bounds for the number of steps required for CoT reasoning in various fundamental algorithmic problems, in the UHAT model. These bounds are tight up to polylogarithiic factors, and are attained by realistically trainable models. Taken together, our results provide theoretical bounds on the ability of transformers to solve reasoning problems with COT.
Anil. C.. Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. Exploring length generalization in large language models. Advances in Neural Information Pro- cessing Systems, 35:38546-38556, 2022.
Ba, L. J., Kiros, J. R., and Hinton, G. E. Layer normalization. CoRR, abs/1607 06450, 2016. URL http://arxiv: org/ / abs / 1100 06450.
Impact Statement
Barceló, P., Kozachinskiy, A., Lin, A. W., and Podolskii, V. Logical languages accepted by transformer encoders with hard attention. In The Tweifth International Conference on Learning Representations, 2024. URL https: openreview net/ forum? i 1= 7mq.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be
specifically highlighted here.

---

Lower Bounds for CoT Reasoning
Barceló, P., Kozachinskiy, A., and Steifer, T. Ehrenfeucht- haussler rank and chain of thought. arXiv preprint WrXiv:2501.12997 2025.
Cabannes, V., Arnal, C., Bouaziz, W., Yang, X. A., Char- ton, F., and Kempe, J. Iteration head: A mechanistic study of chain-of-thought. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:://///...... http:tttsp//oppeeeeiiiiiiee /pppreeeeeeeeeeeeeeemee net/ forum? (dd=BCCxipOt
Barrington, D. A. M., Compton, K., Straubing, H., and Thérien, D. Regular languages in nc1. Journal of Com- puter and System Sciences, 44(3):478-499 499, 1992.
Chen, L., Peng, B., and Wu, H. Theoretical lim-
Bergsträßer, P., Köcher, C., Lin, A. W., and Zetzsche, G. The power of hard attention transformers on data sequences: A formal language theoretic perspective. The Thirty- eighth Annual Conference Neural Information Pro- cessing Systems, 2024. URL hwtph:t//tp/erreeeeeeee http://pppnreee..eemeee net/forune d=NBq] v4f
itations of multi-layer transformer. arXiv preprint
arXiv:2412.02975, 2024.
Chiang, D. Transformers in uniform TCS Transac- tions Machine Learning Research, 2025, ISSN 2835- 8856. URL https: http:::///ppeeeviiwww net forum? id- 2A 2A724DDuDF.
Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal lan- guages. In Webber, B., Cohn, T., He, Y., and Liu, Y. (eds.), Proceedings of the 2020 Conference on Empirical Meth- ods in Natural Language Processing, EMNLP 2020, On- line, November 16-20, 2020, pp. 7096-77 71167716.226 Association for Computational Linguistics, 2020a. doi: 10.18653/V// AD20.EMNLP-MAIN.500 URL https:ttpt..cm.. doii..... org/ 10. /v05553551l/// / emm.:p2eemmmmppmmm.p.m wwwee-elmm-.emm m76..
Chiang, D. and Cholak, P. Overcoming a theoretical lim- itation of self-attention. In Muresan, S., Nakov, P., and Villavicencio, A. (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguis- ties (Volume 1: Long Papers). ACL 2022, Dublin, Ire- land, May 22-27, 2022, pp. 7654-7664. Association for Computational Linguistics, 2022. doi: 10.18653/ V1/202.ACI-LONG.5527 /tt:ttps: /ttp://doiooooo org/ 10. 10.18653/v1/2022 acc.ll.....ccc.........oo acl- Long.ong2.
Bhattamishra, S., Patel, A., and Goyal, N. On the com- putational power of transformers and its implications in sequence modeling. arXiv preprint (xXi:20066009286. 2020b.
Cho, H., Cha, J., Awasthi, P., Bhojanapalli, S., Gupta, A., and Yun, C. Position coupling: Improving length gener- alization of arithmetic transformers using task structure. In The Thirty-eighth Annual Conference Neural In- formation Processing Systems, 2024a. URL https: www.eewwweeeeeeeeeeeeeeeeeeeeeee // opperreriiw...tefffooooooooooade
Bhattamishra, S., Patel, A., Kanade, V., and Blunsom, P. Simplicity bias in transformers and their ability learn sparse boolean functions. In Rogers, A., Boyd-Graber, J. L., and Okazaki, N. (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), ACL 2023, Toronto, Canada, July 9- 14, 2023, pp. 5767-5799 Association for Computational Linguistics, 2023. doi: 10.18653/ V1/2023 httpsts::httt http:/i..rrrg 10.18653/w1/20222 -on.://000.....111......... 317.
Cho, H., Cha, J., Bhojanapalli, S., and Yun, C. Arithmetic transformers can length-generalize both operand length and count. arXiv preprint (tX.::2410011787, 2024b.
Chollet, F. Openai o3 breakthrough high score on arc- agi-pub, December 2025. URL httptt///c//ppriia org /bllooooooooooooooooooooo buw-----bbb-bbbaaaaruuuhh. Ac- cessed: 2025-01-25.
Clark, K., Khandelwal, U., Levy, O., and Manning, C. D. What does BERT look at? An analysis of BERT's atten- tion. In Proceedings of BlackboxNLPP 2019, 2019.
Bhattamishra, S., Hahn, M., Blunsom, P., and Kanade, V. Separations in the representational capabilities of transformers and recurrent architectures. CoRR, 04022066093447 2024. doi: 10.4855//ARXIV24666. 09347. URL https://doi. org/ 48550/ arXiv. 2406. 09347.
Cooley, J. W. and Tukey, J. W. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90))297-3011 1965.
Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wen- liang, I. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Ve- ness, J., and Ortega, P. A. Neural networks and the chom- sky hierarchy. 2023. URL net / http:pofff...d-ixxxxeeeeeeee..
Boppana, R. B. The average sensitivity of bounded-depth circuits. Information processing letters, 63(5):257-261, 1997.
Butoi, A., Khalighinejad, G., Svete, A., Valvoda, J., Cot- terell, R., and DuSell, B. Training neural networks as recognizers of formal languages. arXiv preprint arXiv:2411.07107,00 2024.
Deng, Y., Choi, Y., and Shieber, S. From explicit CoT to implicit CoT: Learning to internalize CoT step by step. arXiv preprint arXiv:2405. 14838, 2024.
10

---

Lower Bounds for CoT Reasoning
Dutta, S., Singh, J., Chakrabarti, S., and Chakraborty, T. How to think step-by-step: A mechanistic understanding of chain-of-thought reasoning. Transactions Machine Learning Research, 2024.
Hahn, M. and Rofin, M. Why are sensitive functions hard for transformers? In Proceedings of the 2024 Annual Con- ference of the Association for Computational Linguistics (ACL 2024), 2024. arXiv Preprint 2402.09963.
Han, T., Fang, C., Zhao, S., Ma, S., Chen, Z., and Wang, Z. fokke-bbudgetaware Ilm reasoning. arXiv preprinl arXiv:2412.188 18547, 2024.
Ebrahimi, J.. Gelda, D., and Zhang. W. How can self- attention networks recognize dyck-n languages? In Find- ings of the Association for Computational Linguistics: EMNLP 2020, pp. 4301 3301-4306, 2020.
Hao, Y., Angluin, D., and Frank, R. Formal language recog- nition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. Towards revealing the mystery behind chain of thought: A theoretical perspective. In seieth- Conference on Neural Information Processing Systems, httpeeeeewwwneeeeeeeeeeeeeeeeeee net/forunt
Computational Linguistics. 10:800-814 810, 2022.
Harvey, D. and Van Der Hoeven, J. Integer multiplication in time O(n log n). Annals of Mathematics, 193(2):563-617, 2021.
2023. URL
id=cHrADgAdYu.
Hastad, J., Wegener, I., Wurm, N., and Yi. S.-Z. Optimal depth, very small size circuits for symmetrical functions in acO. Information and Computation, 2000212000-21, 1994.
Feng, G., Yang, K., Gu, Y., Ai, X., Luo, S., Sun, J., He, D., Li, Z., and Wang, L. How numerical precision af- fects mathematical reasoning capabilities of Ilms. arXiv preprint arXiv:2410.13857 2024.
Hou, K., Brandfonbrener, D., Kakade, S., Jelassi, S., and Malach, E. Universal length generalization with turing programs. arXiv preprint arXiv:2407.03340 2024.
Furst, M., Saxe, J. B., and Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17(1):13-27, 1984.
Hsich, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F., and Ginsburg, B. RULER: What's s the Real Context Size of Your
Goyal, S., Ji, Z., Rawat, A. S., Menon, K., Kumar, S., and Nagarajan, V. Think before you speak: Training language models with pause tokens. In The Twelfth International Conference on Learning Representations, 2024.
Language Models? In First Conference on Language Modeling, COLM, 2024. doi: 1044850/ARXIV.2444.0666
Grazzi, R., Siems, J., Franke, K., Zela, A., Hutter, F., and Pontil, M. Unlocking state-tracking in linear mns through negative eigenvalues. arXiv preprint ar arXiv:2411.1255: 2024.
Huang, X., Yang. A., Bhattamishra, S., Sarrof, Y., Krebs, A., Zhou, H., Nakkiran, P., and Hahn, M. A formal framework for understanding length generalization in transformers. arXiv preprint arXiv:2410.02140, 20244
Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Car- ney, A., et al. Openai ol system card. arXiv preprint arXiv:2412.16720,, 2024.
Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., Zhang, X., Yu, X., Wu, Y., Wu, Z. F., Gou, Z., Shao, Z., Li, Z., Gao, Z., Liu, A., Xue, B., Wang, B., Wu, B., Feng. B., Lu, C., Zhao, C., Deng, C., Zhang, C., Ruan, C., Dai, D., Chen, D., Ji, D., Li, E., Lin, F., Dai, F,, Luo, F,, Hao, G., Chen, G., Li, G., Zhang, H., Bao, H., Xu, H., Wang, H., Ding, H., Xin, H., Gao, H., et al. Deepseek-rl: Incentivizing reasoning capability in 1mm via reinforcement learning. 2025. URL fettps://arxee
Jerad, S., Svete, A., Li, J., and Cotterell, R. Unique hard attention: A tale of two sides. arXiv preprint arXiv:2503. 1.Vv::5503.1615. 2025.
Jones, N. D., Lien, Y. E., and Laaser, W. T. New problems complete for nondeterministic log space. Mathematical systems theory, 10:1-17, 1976.
org/ abs/ /200..2111..0 12948.
Hahn, M. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for
Jukna, S. Boolean Function Complexity: Advances and Frontiers. 2012.
Computational Linguisties, 8:156-171, 2020.
Kim, J. and Suzuki, T. Transformers provably solve par- ity efficiently with chain of thought. In NeurIPS 2024 Workshop on Mathematics of Modern Machine Learning. 2024. URL https: http::///ppeeeeieew net forum? (d=E7HWPh
Hahn, M. and Goyal, N. A theory of emergent in- context learning as implicit structure induction. arXiv Preprint, 2023. URL https:/ / //wxxi.vvoo... .rgg abs/ 2303. 07971.

---

Lower Bounds for CoT Reasoning
Kim, N. and Schuster, S. Entity tracking in language models. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), Annual Meeting of the Association for Computational Linguistics. ACL, July 2023.
Merrill, W. and Sabharwal, A. A little depth goes a long way: The expressive power of log-depth transformers. In NeurlPS 2024 Workshop Mathematics of Modern Machine Learning. 2024b.
Kozachinskiy, A. Lower bounds on transformers with infi- nite precision. arXiv preprint arXiv:2412.20195 2024.
Merrill, W., Petty, J., and Sabharwal, A. The Illusion of State in State-Space Models. In International Conference on Machine Learning. 2024.
Kudo, K. Aoki, Y., Kuribayashi, T., Sone, S., Taniguchi, M., Brassard, A., Sakaguchi, K., and Inui, K. Think-to-talk or talk-to-think? when ilms come up with an answer in multi-step reasoning. arXiv preprint arXiv22412.01113, 2024.
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D.,, Dohan, D., Lewkowyzz, A., Bosma, M., Luan, D., et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint 2rx.v:2112.00111444 2021.
Lehnert, L., Sukhbaatar, S., McVay, P., Rabbat, M., and
Tian, Y. Beyond a Better planning with transformers via
O' O'Donnell, R. Analysis of Boolean Functions. Cambridge University Press, 2014.
search dynamics bootstrapping. In ICLR 2024 Workshop on Large Language Model (LLM) Agents, 2024.
Li, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought em- powers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, 2024.
Olsson, C.,, Elhage, N., Nanda, N., Joseph, N., DasSarma,
N., Henighan, T. J., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., Drain, D., Ganguli, D., Hatfield-Doddss
Z.,, Hernandez, D., Johnston, S., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T. B., Clark, J., Kaplan, J., McCandlish, S., and Olah, C. In-context learning and induction heads. ArXiv, abs/2209.11895. 2022.
Linial, N., Mansour, Y., and Nisan, N. Constant depth circuits, fourier transform, and learnability. Journal of the ACM, 40(3):607-620, 1993.
Liu, B., Js J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Represen- tations, 2023. URL /ettps://opereeviii forum? Drrumm?ddDDe-PY3FPeee
Peng. B., Narayanan, S., and Papadimitriou, C. On lim- itations of the transformer architecture. arXiv preprint arXi::440.008164 2024.
Pérez, J., Marinković, J., and Barceló, P. On the turing completeness of modern neural network architectures. 2019.
Malach, E. Auto-regressive next-token predictors are universal learners. In Forty-first International Con- ference on Machine Learning, 2024. URL https: //openreview wewpiiewweee/oooee wworteeuureoeeeeeeeooooooo iidiiid-ii 1dd1566ppppE...
arXiv preprint
Pfau, J., Merrill, W., and Bowman, S. R. Let's think dot by dot: Hidden computation in transformer language models. In First Conference on Language Modeling, 2024. URL https:/ htapp:://ppeezee apwnreviewweeeeeeeeeeeeeeeeeeewe net/ net/forum? forum? id=Nikbrdt.vG.
McLeish,, S., Bansal, A., Stein, A., Jain, N., Kirchenbauer, J. Bartoldson, B. R., Kailkhura, B., Bhatele, A., Geip- ing. J., Schwarzschild, A., et al. Transformers can do arithmetic with the right embeddings. arXiv preprint vrXiv:240S.17399 2024.
Qiu, R., Xu, 7., Bao, W., and Tong, H. Ask, and it shall be given: Turing completeness of prompting. arXiv preprint urXin:2411.001992 2024.
Merrill, W. and Sabharwal, logic for expressing log- precision transformers. In Seirth- Conference on Neural Information Processing Systems, 2023a.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language Models are Unsupervised Multi- task Learners. OpenAl, 2019a.
Merrill, W. and Sabharwal, A. The parallelism tradcoff: Limitations of log- log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531- 545, 2023b.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, Language models are unsupervised multitask learners. OpenAl Blog, 1(8):9, 2019b.
Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024a. URL httpp::////// ststpps://penreviiece hww.//rrnnrrrt JdN Ph8wh.
Sabbaghi, M., Pappas, G., Hassani, H., and Goel, S. Ex- plicitly encoding structural symmetry is key to length generalization in arithmetic tasks. arXiv preprint arXiv:2406.0/885, 2024.
12

---

Lower Bounds for CoT Reasoning
Sanford, C., Hsu, D., and Telgarsky, M. Transformers, parallel computation, and logarithmic depth. In Forty-first International Conference Machine Learning, 2024a.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E. H., Le, Q., and Zhou, D. Chain of thought prompt- ing elicits reasoning in large language models. CoRR, abs/2201.119033 2022b. a abs 2201/2211.11 11933.
Sanford, C., Hsu, D. J., and Telgarsky, M. Representational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024b.
Wies, N., Levine, Y., and Shashua, A. Sub-task decom- position enables learning in sequence to sequence tasks. arXiv preprint arXiv:2204.02899 2022.
Schönhage, A. Asympiotically fast algorithms for the nu- merical muitiplication and division of polynomials with complex coefficients. In European Computer Algebra Conference, pp. 3-15. Springer, 1982.
Yang, A., Chiang, D., and Angluin, D. Masked hard- attention transformers recognize exactly the star-free lan- guages. In The Thirty-eighth Annual Conference Neu- ral Information Processing Systems, 2024.
Siegelman, H. and Sontag, E. D. On the computational power of neural nets. Journal of Computer and System Sciences, 50:132-150, 1995.
Yang. Ci, Z., and Wipf, ofain-offthhouhh provably enables learning the (otherwise) unlearnable. In The Thirteenth International Conference Learning Repre- sentations, 2025.
Strobl, L. Average-hard attention transformers are constant- depth uniform threshold circuits. CoRR, abs/2308.0322 032212, 2023. doi: 10.48550/ARRXIV2333.... 03321. URL https: //do/ //doii.org/000 40w.::....0001111.... 03222.
Yang. Z., Ding, M., Lv, Q.. Jiang, Z., He, Z., Guo, Y., Bai, J., and Tang, J. Gpt can solve mathematical problems without calculator. arXiv preprint arXhv:2309.0324/ 2023.
Strobl, L., Merrill, W., Weiss, G.. Chiang, D., and Angluin, D. Transformers recognizers of formal languages: A survey on expressivity. CoRR, abs/231 1. 1002088, 2023. doi: 10.48550/ARXIV22311 1.00008. URL https:// doi. org.10.011... 4 48550/ arxiv. 2311. 00208.
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, P. What algo- rithms transformers leam? study in length general- ization. arXiv preprint arXiv:2310. 2023.
Svete, A. and Cotterell, R. Transformers can represent n-gram language models. In Proceedings of the 2024 Conference of the North American Chapter of the Associ- ation for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 6841-6874 2024.
Vasudeva, B., Fu, D., Zhou, T. Kau, E., Huang, Y., and Sharan, V. Simplicity bias of transformers to learn low sensitivity functions. arXiv preprint arXiv:2403.0692. 2024.
Voita, E., Talbot, D., Moiseev, F., Sennrich, R., and Titov, Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Pro- ceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2. 2019, Volume 1: Long Papers, pp- 5797-5808, 2019.
Wang, Y., Hu, S., Zhang, Y., Tian, X., Liu, X., Chen, Y., Shen, X., and Ye, J. How large language models imple- ment chain-of-thought? OpenReview, 2024.
Wei, C., Chen, Y., and Ma. T. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances in Neural Infor- mation Processing Systems, 15:12077-12088 2022a.
13

---

Appendix Contents
A. FAQ
1. Isn't it obvious that one needs at least a linear number of steps to solve these algorithmic problems?
In general, serial computation models such as Turing machines need at least a linear number of steps in order to solve tasks that require knowing the full input. The situation is different for parallel computation as performed by transformers: Many problems do have direct parallel solutions. For instance, for all regular languages expressible in the cireuit complexity class ACO, transformers can express these in the UHAT model without CoT (Theorem 4.3), essentially via parallel 'shorteuts'. Our results are notable in that they establish that many algorithmic problems do require linear-length CoT's with barriers the possibility of substantial parallel shortcuts.
2. All lower bounds in this paper are essentially on the order of (N(N) or S (og No. Do any algorithmic problems require substuntially super-linear (e.g,, quadratic) CoTs?
This question is closely linked to deep unsolved questions at the heart of computational complexity. Due to the Turing completeness of transformer CoTs, proving such lower bounds on CoTs would entail superlinear (c.g., quadratic) lower bounds on multitape Turing machine time complexity, which has been extremely challenging, even for NP-complete problems.
3. Transformers are already known to be Turing-completc Why does this paper construct CoT's for the algorithmic problems isn't 't reducing to known Turing machine constructions enough?
Compared to modern random-access models, single-tape Turing machines (as used in typical Turing machine com- pleteness proofs for transformers) require substantial overhead to process data structures central to many algorithmic problems. For instance, a straightforward implementation of the queue used in breadth-firs search (Theorem 4.10) takes quadratic number of steps on a single-tape Turing machine, as the head needs to repeatedly move between start and end position of the queue. It is thus not immediate from Turing completeness that these problems can all be solved at (near-)linear CoT lengths. Multi-tape Turing machines (which can also be coded into Co may provide substantially better bounds, but CoTs derived from Turing machine constructions are still likely to have substantial overhead (even if just constant factors). In contrast, we show that explicit constructions on the four algorithmic problems studied can be practically learned, confirming that the upper bounds are meaningful.
4. Implementations of self-attention already have quadratic complexity. Why should one be concerned with further linear number of CoT steps?
It is true that generating N tokens, with KV-Cache, will have just (N2)) complexity, asymptotically the same as directly providing an answer. However, it can still lead to substantial overhead, even if just by a constant factor, if the number of CoT tokens grows appreciably with N (compare Figure 6). Thus, any potential sublinear CoTs would be of great interest in increasing efficiency; our results demonstrate barriers to such solutions.
5. What is the practical impact of the results? Do the results relate to any specific NLP tasks?
PARITY, MULTIPLICATION, MEDIAN, REACHABILITY are foundational problems, which instantiate simple models of reasoning problems that have been of broad interest. For instance, PARITY is a simple example of state tracking, family of reasoning problems that have been of substantial interests and that still pose challenges for LLMs (e.g. Merrill et al., 2024; Kim & Schuster, 2023; Hsieh et al., 2024). There also has been a large amount of interest in the ability of transformers and L.MSs to perform arithmetic such as MUT.TIPLICAATIN,, as it is a fundamental ingredient of mathematical reasoning. REACHABILITY is a simple case of search, which is foundational to many aspects of reasoning, and transformers' abilities to perform such problems have been an object of interest (e.g. Lehnert et al., 2024). On all these problems, our results entail barriers on the possibility of transformer algorithms avoiding substantial CoTs.
6. Definition 2. I enforces a fmite input alphabet, but allows an infinite Co'I' alphabet. Why?
The input alphabet needs to be finite for Theorem 3.3 to go through, because the proof of Lemma B.3 by Hahn (2020) involves a union bound over the alphabet. On the other hand, this is not needed for the CoT tokens. Some prior work (Bhattamishra et al., 2020b; Abbé et al., 2024) allows the CoT vocabulary to grow with the input length. Theorem 3.3 can accommodate this, and we indeed find this useful in our constructions.
14

---

Lower Bounds for CoT Reasoning
7. Definition 2.2 allows using different transformers T every input length. Isn't this unrealistic? What about the role of length generalization?
It is true that, in practice, one will expect transformers perform the tasks across input lengths. However, the theoretical literature on transformers has developed different approaches to formalize this. Notably, a single transformer at fixed width may have trouble solving single task across unboundedly many input lengths unless very specific positional encodings are used (e.g. Merrill & Sabharwal, 2024a), and work has thus often considered cases where the width may grow with the length (e.g. Liu et al., 2023; Huang et al., 2024; Bhattamishra et al., 2024). To accommodate such variability, we aim for the most general setup under which we can prove lower bounds. We hence expect only the depth and the number of heads to stay constant, but allow everything else to grow with the input length. This the most general setup under which our techniques allow to show Theorem 3.3.
8. The results in this paper are proven for attention, which can express functions that hard-attention transformers cannot. In particular, UHAT is bounded by AC whereas softmax transformers are bounded by TC Given this difference, what do the results entail about real-world LLMs?
model, whereas real-world implementations use softmax
It is true that softmax attention can express some functions that hard attention (and AC cannot, such as the MAJORITY function. On the other hand, TC is an overly optimistic upper bound on practical abilities of transformers, as many TC functions are not practically learned by transformers due to the sensitivity limitations discussed in Section 2.1. Hence, we focused on tasks for which existing results based on average sensitivity (Hahn & Rofin, 2024) entail that transformers will struggle across different formal models of self-attention, irrespective of differences in expressive capacity (Section 2.1), including problems within TC', Thus, for the tasks considered here, a CoT is practically needed irrespective of the specific formalization of self- attentinn: this is also confirmed by our experiments, where transformers consistently failed in the absence of CoTs We further note that existing CoT constructions from the literature can by and large be expressed well using hard-attention operations (Appendices E. and B.3). In LLM experiments, we observed algorithms in line with our theoretical constructions (Appendix D). Our results thus place strong constraints on any possibility of evading linear lower bounds. In principle, it is possible that other formal models of transformers allow substantially faster CoT's on some algorithmic problems while maintaining practical learnability (Problem 5. I); rigorously proving or refuting the existence of such solutions likely require substantial advances in understanding transformers' learnability properties.
9. CoT lower bounds are proven for hard attention, while experiments are conducted with softmax attention. Isn't 't there a mismatch between theory (hard attention) and experiments (softmax transformers)?
It is true that do not conduct experiments in the hard-attention setup, because there is no efficient training procedure for that setup. Our experiments, conducted in the practical softmax attention setting, complement the theoretical results in two ways:
(a) First, transformers consistently failed in the absence of CoT on the four algorithmic tasks. This supports the theoretical prediction that a CoT improves transformers' ability to solve these tasks.
(b) Second, by showing that CoTs implementing the thcoretical upper bounds can be practically learned, demon- strate the real-world meaningfulness of our theoretical bounds.
B. General Theoretical Results
B.1. Proof of Theorem 3.3: Generic CoT Bound (Main Result)
Here, we prove our main lower bound (Theorem 3.3), which provides generic condition under which sublinear CoTs can be possible. Our techniques build on lower-bounding methods for bounded-depth circuits (Furst et al., 1984; Hastad et al., 1994). Recall the definition of restrictions (Definition 3.2).
Definition B.1. We say p' > p if, whenever P'x = *, then pn (i) = (1 s N).
Definition B.2 (c- (c-rransfrrmer). A c-Transformer conforms to the definition of transformers from Section 2.2, except that is a function of < c cinput positions. That is, there are functions f. such that: each y! (0)
yi (0)
f((II..N)
(6)
and fa depends on at most e of its inputs.
15

---

for all sufficiently large N. Lower Bounds for CoT Reasoning
We build the following lemma shown by Hahn (2020), rephrased for self-containedness. It can be viewed transformers analogue of the Switching Lemma (Hastad al., 1994) for bounded-depth circuits:
Lemma B.3 (Depth Reduction Lemma). Given UHAT c-Transformer T with L layers, a constant (0, 1]. and
restrictions PN P1, ...... such that
Mi S N: PN(( =+]] + CN
Choose any C² E C). Then there are restrictions p1 > p1. > P2.... such that
Kis N: (1) = C'N
(8)
for all sufficiently large N, and such that there is a (E + 1)-tranffrmme T with L. layers, for some integer (depending on )²), such that, for each [1, N] and each / [1, L}.
(1) y1 in T
equals
(1-1) in T
whenever the input is in p'
(1)
Proof. This is stronger statement of Lemma of Hahn (2020). That lemma only stated that the final output y was preserved in 7". However, by the way T" is obtained in that proof the stronger statement for all activations follows. We also note that the original statement considered E {), but the proof transfers to arbitrary finite alphabets E without change, except that 7" is now a H -rransformer, rather than c (2% + -rtrrnsffrmer.
We note that Hahn (2020) did not assume causal masking, whereas we are assuming by default (Section 2.2). Causal masking be easily simulated in UHAT, by setting up positional encodings in such way that d whenever > i. Hence, the proof of the Depth Reduction Lemma continues to work in the presence of hard-coded causal masking.
(R.A) is extremely small
This lemma entails the following fact, strengthening of Theorem of Hahn (2020):
Lemma B.4 (Restated from Lemma 3.4). Let T be UHAT transformer operating over finite alphabet. Take any C' E (0, 1). Then there is c E N, l E N such that, for each N > k. there is p such that
1. Ii: p()) + CN
2. within pK each /n is determined by S. input positions
Proof. By applying Lemma B.3 iteratively, L times.
Remark B.5. A reader might wonder why, instead of introducing Lemma B.4, one cannot simply apply Theorem of Hahn (2020) independently each layer of Transformer. The reason that the latter approach would only ensure the existence of L independent restrictions one for each layer-wheere wweereas Lemma B.4 guarantees that a single restriction fixes each y!"
We now conclude the key result, Theorem 3.3:
Theorem B.6 (Restated from Theorem 3.3). Assume that f has a UHIAT-expressibbee CoT g(x) of length (9(x)) ((rl). Choose any C' (0, 1). Then there is restriction such that
1. Hii < (1) *}1 2 for sufficiently large N
S-We can thus remove layer 0, convert layer-1 activations 3² into layer-0 activations v and obtain a (c- (2% + 1)) transformeer performing the computation before when (3)) applied." (quoted from Hahn, 2020). Here, "p(3)" corresponds the restriction p from the statement the lemma.
16

---

(k) Lower Bounds for CoT Reasoning
2. For each N E N, is constant on EN p
Proof. First, we obtain a restriction p!)) and integers c, k from Lemma 3.4, applying T only on the input o E E* itself.
For any N k. we consider the following, Let M == max g(x))] Without loss of generality, we can pad the CoT's for all x with |2| = N to have length M.
Let g(x) = .1. gM E EMM
We now construct a sequence p(0) - p()) - p(2) + p(0) - ...p!h) while maintaining the following properties for
k 1...M M (f):
1. (i: (x) (1) *} 2 CN - -k--k-o c. H.
( 2. For each E [), i E [1, 11, the activation Uy++ is constant all strings in EN nPN E'.
5 E _ is constant on all strings in EN n PN E. 3. 91 gk
(k)
We prove this by induction.
Inductive Base (k= 1) We can fix yN ..... UN by fixing at most I c- L input positions, obtaining p()) P. with
(1) (L)
(i: 00 (1) *) CN c. 12 CN c. H
(L) Since I1 is determined by yN this also fixes 91-
Inductive Step (k > 1) Assume that the claim has been shown for all K' < & (Inductive Hypothesis). Note that Jk is determined by (L) +-- By the Inductive Hypothesis, Ik-1 is fixed by p( hence, (0) also is. We now perform the following construction for each layer / 1, ......., , L, and within each layer for each head h 1,...,Ih H. We iteratively expand p (1-1) by restricting more input tokens.
At a given layer 7 and head h, let أ > p(*-1) be the restriction obtained after treating layers I,..., and, within layer 1, (1-1) heads 1, I...., h 1. The activation 3 N is now already fixed by p. Our goal is now restrict few more input positions to fix the attention of this head to specific position, and thus fix its output. For this, determine the maximal value of any attention score over all inputs satisfying the restriction, and fix input tokens so that this value is achieved, forcing the attention head to attend to specific position. Formally, for each j E [1, N + k I]. we consider
A₃ = max (1.b)
> (N+1.
(10)
Now let j be the j that maximizes Aj (under the tie-breaking procedure, e.g. choosing the lefimost one, if more than one attain the same Ay). One possibility J [N + 1, ...... N + k 1]; then attention is guaranteed to fall onto this position because each relevant activation is constant across p E1" by Inductive Hypothesis. The more interesting possibility is
(1-1) depends only on I c input tokens in pΣ"; hence, we can expand the restriction p by when j E [1, N]. Note that y
fixing S c additional input symbols force (L-1) take on a value leading to that maximal attention score (1,b) y
"N+--13"
(8) Overall, performing this sequentially each layer and head, we ultimately fix all activations v and hence ga. with a restriction (k) that restricts at most S c. I.- further input tokens beyond p (K--1) 1),
This concludes the inductive proof of the claim (i). Overall, by taking p = (M) we have fixed an additional < c. H. L- [-(x) = o(N) input positions to fix all CoT tokens. As the output f(x) is part of the CoT, fz) must also be constant across all x E N E*
Remark B.7. We assume, by default, causally masked attention throughout the transformer (Section 2.2), for consistency with typical modern language models. Our results are also compatible with setups where attention is bidirectional on the input and causal masking at most applies during CoT generation, which is the setup assumed by Abbé et al. (2024). As explained in the proof of the Depth Reduction Lemma, it holds independently of whether causal masking is applied to the input or not.
17

---

Lower Bounds for CoT Reasoning
B.2. Proof of Theorem 4.11 (Barriers for Dot-by-Dot Scratchpads)
Theorem B.8 (Repeated from Theorem 4.11). Consider a UHATTexpressiblee CoT PARITY where g(x) has the form
#f(x)
("dot-by-dot CoT
(11)
This CoT has length ) all ls O.
Proof. In such a CoT, we can consider the suffix f(z) as the target of prediction given the input 2... of length = [x] [g(x)) - 2, with N = |a]]_ The function predicting f(x:) based prefix x... #
input of length
. + [gxx]] 2, where N = |zz, and has average sensitivity N. We note the following fact: Due to the inclusion of UHAT in AC (Hao al., 2022), and the known bound on the average sensitivity of AC circuits (Corollary 12.14 in Jukna (2012)); originally due to Linial et al. (1993); Boppana (1997)), we have asx(f) = Oppoly(oog(n)) Hence, N = Opooly(oog( + (l(()))))) hence [xx) cannot be bounded by a polynomial N.
Theorem B,9 (Exponentially-Sie Sized Dot-by- by- Scratchpad for PARITY). PARITY has UHAT dot- dot-by-dot CoT of length ((exp(N))
Proof. We lay out construction for dot-by-dot scratchpad of length 2 + 2, expressible in UHAT Transformer with two layers, one attention head, and d = 2N hidden dimensions. Each of the first 2 positions in scratchpad is assigned a unique bitstring g()) E (0, 1 (i E [1 that is, i-th token in scratchpad (or + i-th token overall) corresponds to a binary encoding of
The construction works as follows. In the first layer, each of the 2 scratchpad tokens assigned with g($) determines whether the input string is equal to g(9) In the second layer, the (2N + 1)-th scratchpad token gathers information from them and uses it to predict the hard-coded value of parity for the input string (which is the (2.N + 2)-th scratchpad token).
In the first layer, at the position corresponding to string g(,), an attention head sends out query looking for positions j where æÿ + 5/ For this, the query corresponding bit string (()), emanating from the i-th position in the CoT (overall, index N + i). has the form
(11
5 (1 --
(1 <
(12)
At this position, the key and value vectors are zero.
The key and value corresponding to the j-th bit in the input has the form Ky:
Cg CN+j
Zj 0
K₁
(13)
Zj = 1
where e... E 2NN
one-hot vectors.
Keys of all tokens in the scratchpad are constant vectors of -1.
Then, the attention score
2j * E)
ON+ij
2j E
(14)
<0 j > N
If one position j achieves 1, one of these will be selected by tie- tie-breaking; if none does, one of the N input bits will be selected. The MLP at the query position checks if the retrieved value vector indeed indicates a mismatch z5 * el using knowledge about ((t) forwarded via the residual connection. If no mismatch is found, the transformer can conclude that = {(), and use that in the second layer.
In the second layer, we are interested in the (2 + 1)-th scratchpad token, superceeding all positions corresponding to g(9) At this position, the second-layer attention head attends to the unique position at which the first layer found no mismatch, and retrieves the hard-coded answer computed from the positional embedding of that position.
18

---

Consider a Turing machine defined by Lower Bounds for CoT Reasoning
B.3. Proof of Fact 3.1 (Universality of UHAT CoTs)
A substantial number of constructions coding Turing machine computations into transformer CoTs have been presented in the literature (e.g. Pérez al., 2019; Wei et al., 2022a; Bhattamishra al., 2020b; Hou et al., 2024; Qiu al., 2024; Malach, 2024), but they all use different assumptions about the formal model of transformers. For self-containedness. here provide a simple construction. Our construction is largely equivalent to that of Wei et al. (2022a), but we present it in simplified and self-contained manner in the notation used in our paper. We also note that constructions from Bhattamishra et al. (2020b); Hou et al. (2024); Qiu et al. (2024); Malach (2024) can also be expressed straightforwardly in UHAT. We discuss existing constructions from the literature at the end this subsection.
Construction
1. finite tape alphabet >
2. finite state set Q
3. the action set
(LEFT, RIGHT) (WRITE(O) : E E)
(15)
4. transition function 8, mapping E x Ao A Q
5. start state so E Q
6. terminating set T CQ
with the following computation:
1. We consider tape with positions 0, 1,......
2. At the beginning, the machine starts position 0 and in state su: the tape holds finite input word starting at 0, ending in a separator symbol. All remaining tape positions hold a blank symbol BLANK E Σ.
3. At each step, the next action and state are decided based on 8 applied to the current state and the current tape symbol
4. The machine stops when a state from T' is reached
5. The final state indicates whether the input word was accepted or rejected
We encode the computations as follows. We first encode the input word as string over the input alphabet Σ, followed by a separator symbol. We then construct a CoT over the infinite alphabet
= N Ax Q
(16)
For each state transition, we record (i) the tape position after carrying out 8 (an element of N), (ii) the output of 5 (an element of A x Q)
We relate this construction to other constructions in Appendix E.
We now show that this is implemented by UHAT as defined in Section 2.3. We need define a set of UHATs Ty. operating on inputs with length & N, with uniformly bounded number of layers and heads. We define
Ex = [0,]
(17)
First, let N be bound on the input length. At cach position,
1. The input token g (i, a, g) E 00, NJ x Ax Q provides the tape position i, the output a of 8, and the resulting state q.
19

---

Lower Bounds for CoT Reasoning
2. An attention head attends to the last step which the Turing machine head had been tape position while doing WRITE operation.
The key, given input token ç' = d', .'), is the one-hot vector indicating the tape position i' an indicator for a' (WRITB(O) : J., and a scalar indicating the position
ey E RN 1
E R 1E R
(18)
The query, given input token & = (i, is
NNe; RN 2N R 1E IR
(19)
If the tape position has previously appeared, the attention score will be maximized by the most recent position at which write operation occurred; otherwise, it will fall somewhere else. We define the value, given input token e' = (i', a', "',''),
Ev
(20)
c/'
The MLP then checks if the value is in
E (WRITE(A)
: E
(21)
If not, the symbol at tape position must be what it was set to before the computation started. Else, the symbol the position must be as given by the action a' retrieved.
Simultaneously, a second head attends to position and check whether is part of the original input (i.e., precedes the separator); it is, that position provides the symbol; if it not, the tape position has not yet been written to.
Based the information gathered by these two heads, the MLP then computes the next action, and outputs the new tape position, the action, and the new state.
Comparison to other constructions Our construction closest to that of Wei et al. (2022a). is also similar to that of Qiu et al. (2024). The original Turing completeness proof for scratchpads (Pérez et al., 2019) recomputed the current tape position in every step, an idea used by Merrill & Sabharwal (2024a); our translation differs by keeping the tape position explicitly in the CoT, rather than recomputing it every step; we believe that this reduces some technical challenges in the construction (at the price of making the transformer's 's width and parameters dependent the input length). Bhattamishra et al. (2020b) noted that the classical RNN construction of Siegelman & Sontag (1995) can be straightforwardly replicated in transformer using hard attention and unbounded aobeunded-precisioo activations. This construction also is expressible in the UHAT model. A related translation, albeit in the special case where the Turing machine produces no repeated strings, is developed in Theorem 4.1 of Hou et al. (2024); hence our lower bounds also hold for the "Turing programs" scratchpad technique proposed by Hou et (2024). Another translation (applicable to, but not specific to transformers) is used by Malach (2024), uses even simpler computations in each step, but may suffer a polynomial slowdown compared Turing machines.
C. Applications to Algorithmic Tasks
C.1. PARITY and other Finite-State Languages
C. 1.1. PROOF OF COROLLARY 4.3: CHARACTERIZATION FOR SINITE-STATE LANGUAGES
Corollary C.1 (Restated from Corollary 4.3). Let f be the membership problem of a finite-state language L. Then f exactly one of the the following holds:
1. L AC and f expressible in UHAT without CoT
2. I is not decidable A and any UHAT CoT for f has length (2N)
20

---

Lower Bounds for CoT Reasoning
Proof. We show this using the characterization of regular languages in AC by Barrington al. (1992) and the follow-up result on hard-attention transformers by Yang et al. (2024).
First, if L E AC then it is definable in UHAT (without CoT) by Corollary 8 of Yang et al. (2024).
Conversely, if I. E ACO, then by Theorem 3 of Barrington et al. (1992), the syntactic morphism of I. is not quasi-aperiodic. That is, if M. is the syntactic morphism of L then there is & E N such that nı (>*) contains a nontrivial group G. As in the proof of Theorem 3 of Barrington et al. (1992), we now consider an element m E G of order k > 0, and define M' {m, m² such that Ti (u) m, 7L (v) m².
..... m² to be the subgroup defined by m; its identity element is m We can then find strings u, v E E
Namely, there are strings B E* such that either aruB E L, aruB & L, or the other opposite holds. By passing from L to its complement if needed, we may assume without loss of generality that aub E L, av3 of L. We now consider inputs of the form
(22)
Now assume that a UHAT CoT with length [=(=)) o[==)) exists for deciding, on such inputs, membership in L. By hard-coding the (fixed) strings a, B, we can convert this into a UHAT CoT performing the same problem with only the inner part, a word in (ulu)", given as input. As |u| |el, we can further convert this into UHAT CoT over new alphabet Σ' = {a, b). translating u E E' to a E E' and E Σº to b E E', cutting the string length by a constant factor of t t= -u|u = |u|. We now reach contradiction: On inputs of the chosen form, checking membership in L amounts to counting how often и (or, after changing the alphahet, a) appears modulo k. Fixing any constant fraction of symbols cannot fix the result. By Theorem 3.3, the UHAT CoT cannot have had length [g(x)] = o((=1) in the first place. Hence, any UHAT CoT for deciding membership in L has length (2N)..
Remark C.2. We also mentioned, below Theorem 4.3, that f is affected by the sensitivity- based barrier discussed in Section 2.1 if and only L & AC This is seen as follows. First, if L E AC", then by the result of Boppana (1997), a (f) Opolyy(og((N)) (lo(()))) o(N). Second, if L & AC then the deciding membership of strings from " as defined in the proof of Theorem 4.3 amounts to counting how often u appears modulo k. Any function Σ' - {0, 1} that exhibits this behavior on strings from a(ulv)", 3 must have a high sensitivity. Overall, this means that shortcuts to finite-state automata without linear-length CoT (Liu et al., 2023) are likely to be learned well on long inputs if and only the automaton can be simulated in AC
C.1.2. EXPERIMENT
We trained a 2-layer 2-head transformer using the GPT-2 architecture (Radford et al., 2019b), with d 256. Each model was trained at fixed input and CoT length. Each training and testing input generated randomly on the fly. Training was for 30K steps, at batch size of 64, with Adam (learning rate le-4).
C.2. Arithmetic
C.2.1. PROOF OF THEOREM 4.5 (LOWER BOUND FOR MULTIPLICATION)
Theorem C.3. A UHAT CoT for My requires length ((N)..
Proof. In order to understand the difficulty of different digits in multiplication, we first review the connection between multiplication and bit string convolution. The integers X, Y, XY can be written in terms of binary coefficients E., m)s E {0, 1}
as:
N
X
2'E;
i=0
N
Y 2'm
=
i=0
N
XY
Σ
2
Σ 2'n
refer to Barrington et al. (1992) for the relevant definition.
21

---

Lower Bounds for CoT Reasoning
ADDITION
MULTIPLICATION
Length
20.3
Sensitilty
10
10
20
Posilon
Position
Figure 7: Arithmetic. Average sensitivity (Section 2.1) of the results digits as a function of the length N of the operands (colored lines) and the position & (x-axis). The most significant digit position O. Left: ADDITION. Sensitivity grows sublinearly with n. Right: MULTIPLICATION, Sensitivity grows rapidly with the length of the multiplicands, and is highest in the middle, where sensitivity shows linear growth with 1.
Correct Predictions per Digit Position
Correct Pred ctions per Digit Position
10000
10020
Predictions
8000
6000
2000
2000
Digit
Figure 8: Accuracy of transformers trained on 12-digit multiplication (most significant digit at the left, zero-padded on the left), either autoregressively (left) or in parallel (right), on a test set with 10K number pairs. In both setups, the high-sensitivity digits the middle (compare Figure 7 Right) show substantially decreased accuracy even if digits at beginning and end are predicted exactly.
22

---

Lower Bounds for CoT Reasoning
Pspectation
Ceee Tranped
Dowceete vohes
091
Volv55
-0.0
Figure 9: Numerical Experiments for Conjecture C.5: 100 different combinations samples for each T. Blue dots indicate
values for (23) for 100 different sampled (A, B, C). Right: Zoomed in on T= 7,8,9.
2 Eimli
Σ
2
Em
C+ k
Hence, the N-th digit of XY, My, is determined by, the one hand, the high-order parity Di+j=k Emy XOR-red with carries obtained from terms at lower kss. Now if one fixes CN input bits, for C' small, the result cannot be fixed.
Remark C.4. Regarding MN(,,), ), we note that the innermost digits MN are, up the impact of carries, derived from high-degree parities as discussed in the proof of Theorem 4.5. In accordance with this, we find that as (Mx) is approximately
(in 2N - ks) and in particular peaks at & ss N (Figure 7). Empirically, the middle digits are the hardest for transformers (Figure 8).
C.2.2. REMARK: AUTOREGRESSIVE MULTIPLICATION
Theorem 4.5 shows that querying individual digits of product of N-digit numbers requires at least linear-length CoT. An interesting question is whether autoregressive decoding can help, i.e., the earlier digits in the result can serve as an effective Mfain-of-thought for later digits. Empirical results cast doubt on such possibility, because transformers struggle substantially more with multiplication than addition even in autoregressive generation (Figure 12).
Here, we outline path to rigorously showing this. The key idea is the following conjecture, which is of purely combinatorial nature:
Conjecture C.5. Given two binary encodings X, 10,1)* N-bit integers, let Mx(X, Y) be the i-th bit of the product
XY. We assume standard binary encoding with the most significant bit the left.
Then, there is constant D 0 such that for any T E [1, sets A, B C [1. C C [1, - 1). we have
MT(X,Y)
II X II 8 II Mx(X,Y)
22-DT
(23)
SEA
JEB
keC
where X, = 2X, =X,
[-1,1), and similar for Y, M.
This statement intuitively states that digits of the product are not substantively correlated with combinations of individual digits in the inputs or preceding digits in the result. We provide numerical evidence for this conjecture in Figure 9, Any proof of this conjecture would imply lower bounds on autoregregressive multiplication. Formally, we are interested in autoregressive predictors
Fr (0, (0,1)2N+T-1 - {0, 1}
(24)
23

---

Lower Bounds for CoT Reasoning
with the property that
Mr (x, X2, X2,..., XN, Y1, Y2, ...... YN, Mi....y Mr-1)
(25)
We then have bounds based on sensitivity (hence learnability by Section 2.1) and UHAT expressiveness: Lemma C.6. Assume Conjecture C.5. Then any Boolean function implementing Fy needs to satisfy'
as(Fx) (2(N)
(27)
A CoT directly outputting M....My without (1) further intermediate steps, cannot be implemented in UHAT.
Proof. it is sufficient to show the lower bound average sensitivity; the claim about UHAT follows from the inclusion of UHAT in A and Boppana's s upper bound on the average sensitivity of AC functions (Boppana, 1997). We refer to
O'Donnell (2014) to background on Fourier analysis of Boolean functions. We consider the Fourier transform of FN as
Boolean function:
N
E
AA,,CC'
II iEA
II Y, II Mr JEB
(28)
REC
for unique coefficients A.B.C E R given by
AAB.C = Ex.
Mr(X,Y) II & II II Mx(X))
(29)
iEA
jEB
REC
We have, by the conjecture,
{ E
1)
?
X A.C.C
MM((,
II
X; II Y, II
2 22DN
TEA
JEB
REC
Now, for any E (0, the number of tuples (A,B, C*) where Hence,
|A + B|+ S 17 3N is ~ 2%, for some Yn- > 0.
Σ
AA.BCC 2 2
By Parseval's Theorem:
1
Σ
AB
ABCLNIICCINNI
We choose 7 that % < 2D. Then, by the link between Fourier transforms and average sensitivity (O' (O'Donnell, 2014), find:
as(Fx) = Σ (I4) + [ B|++C[]) |AA,B.C
A,B,C
23
PA..
A.B.CAMIHH1HH110020000
N (1- (1-2(7,-20) -D2N)
=N(N)
This concludes the proof.
In fact, the stronger bound
as 92(T)
(26)
be concluded uniformly for T, independently of N. This is hecause Fr is only relatively weakly dependent digits at positions much larger than T, making products trivially close to zero Conjecture C.5 when B include indices substantially greater than T.
24

---

Lower Bounds for CoT Reasoning
C.2.3. CONSTRUCTION OF ON log N)-LENGTH COT FOR MULTIPLICATION
Whereas the traditional approach for multiplying two N-digit numbers requires ((N2) steps, modern algorithms are more efficient for large inputs, and achieve asymptotic runtime up to ( log N) (e.g. Schönhage, 1982: Harvey & Van Der Hoeven, 2021). We illustrate this by demonstrating scratchpad whose length, O log N), matches widely conjectured lower bound on the asymptotic time complexity of multiplication in the Turing machine model. It is based on the Schönhage-Strassen algorithm (Schönhage, 1982). 8
Background: Number Theoretic Transform (NTT) The Number Theoretic Transform is an analogue of the Discrete Fourier Transform (DFT) that operates over finite fields. While the DFT leverages the complex roots of unity, the NTT employs roots of unity in modular arithmetic setting. Formally, let Fg denote a finite field of size q, where = p for some prime p and integer k. Consider a prime p such that there exists a primitive n-th root of unity w E Fg. w (mod p) and for all n,, = # The NTT is then defined as a mapping of an input vector of length n., say a (ao, 01,... an 1). to output vector A = (Ap. A1...... ................................ Ax-1), where:
Σ 1=0
aawh
(mod p), for 0, O.l.,..,n-
This transformation can be seen as a modular version of the classical DFT. The inverse of the NTT (INTT) is similarly defined, allowing for the reconstruction of the original vector from its transformed version. The INTT expressed as:
n Agw - (mod p), for j = 0, 1, ,
aj
72
where 1 refers to the modular multiplicative inverse of n modulo which must exist for the INTT to be valid. In the context of multiplication, the use of NTT allows for a scratchpad with ONN log N) length, compared to the O(N2) length of the naive scratchpad.
CoT Construction and Analysis The Schönhage-Strasse algorithm provides a method to perform integer multiplication efficiently (Schönhage, 1982). To translate this into a scratchpad for use in a UHAT framework, the steps of the algorithm are defined here. We note that the required attention pattern is, for any input length N, input-independent,, which ensures that the CoT is expressible in UHAT. The number of CoT steps scales as O(N log N) because the NTT is computed using the divide-and-comne
Fast Fourier Transform strategy (Cooley-Tukey Algorithm, Cooley & Tukey, 1965).
We use "-1" as separator token.
Input encoding
We encode the input:
[-1] First Number
[-1]
Second Number
[-1]
Input Reversal and Padding Given two binary numbers, first reverse their bit sequences and pad them to the nearest power of two, 2", where is chosen such that 2n is greater than equal to the length of the input sequences. This ensures that the sequences are of length suitable for efficient NTT computation.
[-1] First Number Reversed and Padded] ]
[-1] Second Number Reversed and Padded
'The Schönhage- Strassen algorithm (Schönhage, 1982) requires O(N log N log log N) steps, slightly different from the O(N log N) COT length. This is because we use an unbounded CoT alphabet to encode and perform arithmetic on the entries of the NTT. Moving constant-size CoT alphahet would incur log log N factor in the standard Schönhage-Strasee Strassen algorithm. The algorithm of Harvey Van Der Hoeven (2021) attains O(N log N) complexity, but substantially more complex.
25

---

Lower Bounds for CoT Reasoning
NTT Transformation The padded sequences are then transformed using the NTT, which operates in finite field. The output is sequence Ao...., An-1 (0, PO.....P-1.
[-1] [NTT of First Number [-1] [NTT of Second Number
This part takes O(N log N) steps because the NTT is computed using the divide-and-conquee Fast Fourier Transform strategy (Cooley-Tukey Algorithm). Every step combines two fixed previously computed results; the attention pattern can be hard-coded into positional encodings and the modular arithmetic required can he hard-coded into the MIP map fMLP (Section 2.2).
In the NTT domain, the two transformed sequences multiplied pointwise, modulo our prime number. This convolution corresponds to multiplication in the original domain. We found that training was improved by first copying the NTTs with each digit marked with an index hint (Zhou et al., 2023) indicating its position, as a way of indicating which pairs of numbers to match in pointwise multiplication.
Convolution
[-1]
[onvolution| ] [-1]
This part takes just (N) steps.
Inverse NTT After the convolution, apply the inverse NTT to convert the sequence back the domain.
[-1] Result of Inverse NTT] [-1]
Again involving hivide-and-conquee FFT, this takes O(N log .) steps.
Finally, we recombine the elements of the transformed sequence to produce the final multiplication result. Starting from the leftmost element, we multiply by 2 the next by 2 and so on, summing these weighted values to get the desired output.
Recombination
Recombined Final Result] ]
[-1]
Example
Below is example of the full CoT for 2 digit binary multiplication (10 * 11) using prime p 5.
Input:
-110- 111-111-1
.Target:
-1
0 0100
-1
1100
-1
1 1243 4
First Number Reverse and Pad
Sccond Number Reverse and Pad
NTT of First Number
2 3
a c d 3
c
NTT of Second Number
NTT of First with Index Hints
NTT of Sccond with Index Hints
-1 2 b c 0 2
- 2 -1
0
0110 -1 0 0110 1
Comvolution with Index Hints
Convolution
INTT Convolution
Result (Recombined)
C.2.4. EXPERIMENTS
Setup All experiments were conducted on NVIDIA A100 GPUs (40GB memory each). We experimented with two different transformer architectures: a BART based decoder model (for autoregressive decoding of multiplication) and an encoder-only model (for parallel decoding).
26

---

Lower Bounds for CoT Reasoning
Model Configurations We experiment with three setups:
1. Direct parallel decoding of each digit Mı...., M2N (and analogously for addition) in parallel. To avoid training separate transformers for each digit, we use transformer encoder (i.e., transformer with bidirectional attention) reading in the two N-digt operands, and providing predictions for each of the 2N results digit at the top layer. Due to high sensitivity of the middle digits (Figure 7) and Theorem 4.5, we expect that this setup will be difficult for MULTIPPIICTTON, though not for ADDITION.
2. Autoregressive decoding of the result Mi... M2N (and analogously for addition). We expect that this setup is still difficult for MULTIPLICATION as discussed in Appendix C.2.2.
3. Autoregressive decoding of the ON log -lengtth COT. We expect that this setup will make the task feasible for transformers.
Encoder-only Model for Direct Parallel Decoding: We employed transformer encoder with layers, attention heads, feed-forward network dimension of 512, and a model dimension of 128. The vocabulary size was determined by the tokenizer used for encoding the digits and arithmetic symbols.
Encoder-Decooe Model for Autoregressive Decoding: In autoregressive decoding, we slightly deviated from the theoretical setup in Section 2.2 in allowing bidirectional attention on the input (though not on the CoT) as in Abbé et al. (2024), for consistency with the Direct Parallel Decoding setup, where we use bidirectional attention for efficiency, as described above. We built on the BART architecture, with a I-layer encoder and a 2-layer decoder. Both the encoder and decoder had attention heads, and the decoder's bord-forward network dimension was 512. The model dimension for both encoder and decoder was 128.
Note Bidirectional Attention: As the results in Hahn (2020) do not presuppose causal masking, our lower bounds are also applicable in the setup with bidirectiobnal attention (Remark B.7).
Datasets All experiments were conducted on binary numbers. We trained and evaluated both models without CoT on datasets consisting of 2-digit, 4-digit, and 6-digit arithmetic problems for both addition and multiplication. For the CoT, we used training dataset of 5 million samples and 10,000 test samples. The dataset sizes for 8-digit 12-digit multiplication were smaller due the limited number of possible combinations, with 50,000 samples for training and 10,000 for testing. In both cases, the test data is held-out, without overlap with the training data.
Training Configurations For the CoT multiplication experiments, we used the following training configuration: Number of training epochs: 20 Batch size (per device): 8 for both training and evaluation Gradient accumulation steps: 4 Learning rate: 0.0001
Multiplication Task
Training Set Size
Accuracy (%)
8-digit
50,000
99. 99.83
9-digit
50,000
99.87
10-digit
50,000
99.82
11-digit
50,000
99.85
12-digit
5,000,000
99.84
13-digit
5,000,000
99.82
14-digit
5,000,000
99,96 99,96
15-digit
5,000,000
99.91
16-digit
5,000,000
99.83
Table 1: Accuracy results of the ONN log -eengh CoT for MULTIPLICATION for different digit sizes. All accuracies computed on tests sets disjoint from the training set.
27

---

Lower Bounds for CoT Reasoning
Average Sensitivity as a Function N
300
250
Average Sensitiity
200
150
100
0
100
200
300
400
500
Figure 10: Average sensitivity the last digit of MEDIAN as a function of N when B ~ 1 1 [log N7. We estimate average sensitivity by sampling 200 input strings at each N, and 200 bit flips for each input. As predicted theoretically (Appendix C.3), average sensitivity grows linearly in this regime where exp(B) 2 N.
C.3. MEDIAN Task
C. THEORY
We first establish the claim that the last digit of MEDIAN is sensitive changes of the integers, in the regime where N << B). Changing the first digit in any of the numbers with order rank < 2 can get it to have rank > | I J. Under uniform sampling of the numbers, the chance that this will change the last digit is RJ 1. Changing other digits will additionally have some nonzero (though smaller) chance of flipping the last output digit. Hence, the average sensitivity of the last digit is z N. in Section 2.1.
2 This illustrated in Figure 10. Hence, the task challenging for transformers by the results reviewed
Now proceed showing the CoT bounds.
Theorem C.7 (Restated from Theorem 4.8). For the MEDIAN lask, UHAT scratchpad requires length S2(N). This bound is attained.
Proof. We note that the input length is BN, where B is the number of bits in each integer. To show the lower bound by applying Theorem 3.3, note that fixing, say, N BN digits cannot fix the median.
10B
Now we show that the bound is attained. Recall that the input consists of N unique numbers in binary encoding, each with B bits. Let a1,..., an be the integers in the input, and let di,,...,4 Di. be the same numbers ordered by magnitude. Now the CoT simply consists of
ai Og N/2)
(30)
To implement this in UHAT, first use B attention heads in order aggregate each a, the basis of the B bits entering its binary representations:
B 0; Σ
2 PBBB
(31)
1=
where À (0, BN is the input string consisting of N integers with B digits each. This number a; is stored, e.g. one-hot encoding, in the activation (2) at the last digit of its binary representation in the input. The CoT then orders the
'If N is the order of even larger than exp( ()), then uniform sampling of numbers (even with replacement) will have high chance producing the same number and sensitivity. hence focus on the regime where << exp(B).
28

---

Lower Bounds for CoT Reasoning
numbers by magnitude, stopping at the k-th index. Importantly, this is expressible with single attention head as follows: If the integer is represented as the one-hot vector 6i then c. KTQe,, produces the desired behavior when 10
-1 N N+ else
i
(K* Q)5
(32)
Stopping at [N/2] can be hard-coded via positional encodings.
C.3.2. EXPERIMENT
To simplify the setup, deviated from the theoretical construction by using decimal numbers instead of binary numbers, and also using decimal numbers instead of atomic encodings in the COT. We considered three-digit numbers (B = 3, but with decimal instead of binary encoding)."
We experiment with = {1,9, 19, 29, 39, 59,59, 69, 79, 89, 99). The resulting input length is between and 398 (including BOS and SEP token). The N numbers are randomly sampled from {0, 1, , ,9993 with replacement. We train separate models for each N, and test on the same length. Note that the size of the test set varies with N, concretely it is (N + +10) 20. Because when N 1, there only 1000 possible inputs. The test examples excluded from training set. The input format is as follows (for the case N 3), including full scratchpad:
BOS 3 4 3
9
2
SEP 0
1
9
4
3
EOS
We use ";" to separate each number. As mentioned, we experiment with the full scratchpad and without any scratchpad, as well as every keth element in the full scratchpad, where k = {2, 3, 4, 5, 6, 9, 12]. The models are trained with cross entropy loss on tokens after SEP (excluding itself). The input length figure refers to number of tokens before and including SEP, and CoT length refers to number of token after SEP and before the final answer (last digits). While models are trained predict both the scratchpad and the answer, we do consider scratchpad during testing. In other words, evaluate the models, we give them tokens up to SEP, and let them generate with greedy search, and take the last generated number before EOS as the prediction. The prediction is considered correct only when it matches all digits in the answer. We run each experiment (each N and each kind of scratchpad) with 3 random seeds, and report the average accuracy.
Regarding hyperparameters, we use the same model architecture for all experiments in this section, which has 3 layers, attention heads in each layer, and model dimensionality of 256. We use batch size of 64, train models for 50k steps, use learning rate starting from 10-4 and decreasing linearly. We use AdamW optimizer, with $1 0.9, 32 0.999 and weight decay of 0.01. All dropout rates are set zero. Note that observe that low accuracy is always accompanied with big training loss.
C.4. Graph Reachability
C.4.1. PROOF OF THEOREM 4.10
Theorem C.8 (Restated from Theorem 4.10). There is a family 6 of DAGs inside which reachability is solvable in TC but cannot be represented by transformer at sublinear average sensitivity. A UHAT CoT needs length Ω ([E) log [V]). This bound is altained.
Proof. For the lower bound, the proof proceeds by coding PARITY, n into DAGs with 2n vertices. For i = 1,..., NN we introduce two vertices oid and eveeen. Whenever = 1, we add edges Us,odd + 411evven and Us,odd + 14+1.even- When z; = 0, the edges instead connect Ujoodd > 1;+1,odd and Uieven -> Us+1.even- Then, x has even parity and only there is path from evve to UN+1, We define as the set of these graphs. TC" circuit is sufficient for deciding membership. As the graphs in & code PARITY, reachability cannot be represented by transformers at low sensitivity. Also, fixing a small constant fraction of edges, while staying within G cannot fix the reachability.
is guaranteed to be in G, then a
We note that definitions of autoregressive sorting by transformers are also given RASP-L (Zhou et al., 2023) and C-RASP (Huang al., 2024).
"In preliminary experiments, found that it is important to have diverse inputs (i.e., B not too small in relation to N) to avoid learning "increment-by algorithm (imagine when N = 100, sample 100 number from [0, 99] without replacement, which means the sorted list and median is always the same).
29

---

Lower Bounds for CoT Reasoning
To show that the 2 ([E) log [V]) bound is attainable, we note that a CoT of length ( log VI) can encode breadth-fing first search, generalization of the DFS/BES CoT for the cycle task in Abbé et al. (2024). The input consists of the edges and the query, such as:
BOS
06
08
04
01
04
05
01
03
08
00
01
05
QUBRYI 0.3
QUER 04
SEP
Whereas the imput codes each vertex [log |Vll-ength number (keeping the input alphabet finite), each vertex is coded as an atomic token inside the COT. At the beginning of the CoT, each edge is translated from binary representations to this atomic representation. This takes O(EE) log [V]) steps. 12
We then implement a standard first-n-ffist-out queue. As nothing can be deleted from the CoT sequence once has been generated, we maintain a pointer N that indicates the current head of the queue. The CoT then starts with the first query vertex. We copy into the CoT all the edges starting with the end of the edge. We then move the second edge in the CoT and write down all the edges starting with the end of that edge, and so on. If at any point encounter the target vertex, exit. Throughout, in every CoT step, we additionally maintain the pointer N indicating the current head of the queue. O
C.4.2. EXPERIMENT
We show that the CoT described in Theorem C.8 is sufficient for Transformers to solve the problem of DAG reachability in the general case, For that, we train Transformers to predict the reachability of two vertices in a random DAG, both with and without a COT.
Data generation. Each random DAG is generated by sampling a random lower triangular adjacency matrix and instantiating a DAG from it. We then compute the distances between all pairs of vertices in the graph. When sampling examples for training or evaluation, we select, with equal probability, either an unconnected pair labeled as or a connected pair labeled as 1. For connected pairs, we sample the pairs such that the distribution of possible distances is uniform.
For example, in chain graph A + B C, the unconnected pairs (C, B), A), and (B, A) are sampled with a probability of 1/6 each. The connected pairs (A, B) and (B, C)) are sampled with a probability of 1/8 each (distance 1), while the pair (A, ()) is sampled with a probability of 1/4 (distance = 2). This way, we avoid the bias toward shorter distances.
For each generated DAG, we compute the Ceisfeiler-Lehmand hash and ensure that the hashes of the training and test DAGs do not overlap. When provided to the model, the input data encoded as described in Theorem C.8.
Model and training. We use decoder-only Transformer based the GPT-2 architecture (Radford et al., 2019a). The model has 4 layers, 4 attention heads per layer, and 256 hidden dimensions. The model is trained for 50k steps using AdamW with batch size of 64 samples.
We train the models in two regimes: with and without a COT. In the CoT regime, we generate a BFS-based CoT as descrihed in Theorem C.8 and append it to the input data. To simplify and reduce computational cost, we represented all vertex indices as decimal numbers, eschewing conversion to atomic symbols. During training, we optimize the next-token prediction loss on the CoT and answer parts of the sequence, while ignoring the predictions for the input tokens. During evaluation, the model autoregressively generates the CoT and the final prediction. The no-CoT regime is similar, but the CoT is not appended to the input, requiring the model to generate the answer directly.
Evaluation accuracy is checked every 9k steps. If the evaluation accuracy exceeds 99.5%, training is terminated early.
Results. The model's accuracy for various input sizes, corresponding to DAGs with 5 to 35 vertices, is shown in Figure 4. All values are averaged over three runs.
For all graph sizes except one, Transformers with CoT achieve near-perfect accuracy, while Transformers without CoT perform chance level. The exception is for graphs with the smallest size (5 vertices), where both regimes achieve approximately 90% accuracy. This discrepancy may be due to the limited number of distinct DAGs of this size, leading to insufficient training signal for the model to learn the algorithm of CoT construction.
Formally, a Em. A,21, define ā Eln 2,2' The CoT then translates the binary representation of each vertex index a E [V] into the atomic representation by enumerating 0610 ... di [lgg/V 1
30

---

Lower Bounds for CoT Reasoning
D. Experiments with Pretrained LLMs
Approach. To test our predictions on the necessary CoT length, we run experiments with state-of-the-art LLMs trained to generate CoT reasoning before responding to a user's request: DeepSeck-RI (Guo et al., 2025) and ol ol-mini (Jaech et al., 2024). If, contrary to our predictions, sub-linear algorithm for any of the discussed problems exists, these models might discover it and solve the task with CoT of sub-lineat size. Verifying this serves as basic sanity check for theory.
We tested the models on three tasks: parity, multiplication, and median. For the parity task, we generated random bitstrings of various lengths, ranging from 10 to 70, and asked the models to calculate their parity, We then selected the CoTs that led to correct answers and calculated their average size for each input length. The prompt provided to both models was: You will receive a string. You have to manually calculate its parity. Finish your response with if the parity is odd, and if the parity is even.
The approach for the multiplication task was similar. We generated random pairs of numbers with lengths rang- ing from 3 to digits, prompted the models to multiply them, and computed the sizes of the correct CoTs. The prompt provided was: You will receive two numbers. You have to multiply them manually. Finish your response with the precise result of the multiplication.
For the median task, we generated sequences of odd length and prompted the models to find the median. The numbers were generated uniformly from 1 to 10 The prompt provided was: You will receive a sequence of numbers. You have to manually compute its median. Finish your response with the value of the median of this sequence.
The results of the experiment are shown in Figure 6. For all three tasks, the size of the CoTs grew at least linearly, supporting the theoretical prediction that no CoT exists to solve parity, multiplication, or median in a sub-linear number of steps.
Results.
A qualitative inspection of the reasoning traces of DeepSeek-RI revealed that, when computing the parity of a bit sequence, it copied every bit, counted the number of ones, and then determined the evenness of that count. For multiplication, it used a naive quadratic algorithm. However, the performance of DeepSeek-RI dropped significantly for numbers with 10 digits or more, suggesting that its multiplication algorithm is not truly length-generralizable.
E. Further Discussion on Related Work
E.1. CoT Constructions in the Literature
Besides CoTs emulating Turing machines (Appendix B.3), various other more specialized CoT constructions have been considered in the literature. Feng et al. (2023) provide a general construction of transformers for a very broad class of dynamic programming (DP) algorithms. This construction essentially only uses hard-attention operations, and can be expressed in UHAT as long as the aggregation function used in the DP algiorithm can be expressed. This includes, for instance, evaluating Boolean formulas. Cabannes et al. (2024) analyzed the algorithm learned by transformer trained on scratchpads for various algorithmic problems, identifying computes unique hard attention pattern iterating through the input, combining material from the input with the last CoT step. Relatedly, the Inductive Scratchpad Abbé et al. (2024) a construction where each step is a function specifically of the previous CoT step and the input.
"iteration head" attention pattern. This head effectively
E.2. Relation to Globality Degree
Here, we discuss the relation of our results to the work by Abbé et al. (2024) on the Globality Degree. We recall their definition, rephrased for self-containedness::
Definition E.1 (rephrased from Definition 2 of Abbé et al. (2024)). For an alphabet A of cardinality (p)oy(nn)) and distribution D on A x A, D has constant globality if and only if there is k E N such that, for each there exists S C [m]. |S| = k, such that
I (x[[), -0 -01)
(33)
where (X,Y) ~ D, and Px is the histogram of tokens in X.
31

---

Lower Bounds for CoT Reasoning
NTT Scratchpad
Scratchpad
of Tolems
500
400
Number of Bits Scretchpad
Figure 11: Multiplication: Comparing the number of tokens used in the log N) NTT CoT (Appendix C.2.3) CoT implementation of the naive ((N²) algorithm. The token count of the NTT CoT is piecewise constant because the length only depends on the prime p used in the construction; length is asymptotically OLN log N).
Here, we think of (X, E A as a pair of input and label; hence, Y will generally be a function of X.
If one assumes |AI (1) and puts aside the knowledge of the token histogram, then constant globality is equivalent the presence of nontrivial correlations with the circuit complexity class N (Lemma 6 in Abbé et al. (2024)), highly restricted class contained within AC and easily simulated by UHAT.
The key conjecture of Abbé et al. (2024) states:
Conjecture E.2 (Conjecture of Abbé et al. (2024)). A distribution Px.y with well-behaved Px is efficiently weakly learnable by a T-regular Transformer if and only if Px,y has constant globality.
For CoTs, the implied prediction is that (i) tasks with nonconstant globality require a CoT for efficient learning. (ii) CoT is learnable if and only if each its intermediate steps has constant globality. A version Conjecture E.2 shown formally for a cycle classification task, though the conjecture makes far-reaching predictions beyond that. The practical predictions made by this conjecture are related those of our theory, but not equivalent; for instance:
1. (diverging prediction) PARITY has low globality, because the conditioning on the histogram is not constrained. Conjecture E.2 thus provides a more optimistic prediction here than our results.
2. (converging prediction) The Cycle task of Abbé al. (2024) requires lincar-length CoT Theorem 3.3, and can also be shown to not be representable at sub-linear average sensitivity under reasonable input encoding. Difficulty is predicted under both perspectives.
Overall, there similarities and differences between the practical predictions made by Conjecture E.2 and unconditional lower bounds. On technical level, the theoretical arguments of Abbé et al. (2024) rely bidirectional attention at least on the original input (if not the scratchpad), different from the causally masked transformers generally used in LMs. Expanding those arguments to causally masked transformers is an interesting problem for further research.
This is defined in Definition in (Abhé et al., 2024). A simple example is the uniform distribution over {0. 13x 14 "Infrrmllyy, this is bidirectional transformer under standard initialization (Definition (Abbé al., 2024)).
32

---

Lower Bounds for CoT Reasoning
m Anhen
A8p
1000
(a) 4D In- Domain Autoregressive
(b) 6D In In-Domain Autoregressive
(c) 8D In-Domain Autoregressive
10g aeteema 2022
(d) 4D Held-OOt Autoregressive
(e) 6D Held-Out Autoregressive
(f) 8D Held-Out Autoregressive
wnteredi
antrrntt
WW
13.00
2000
10.0
4D Held-Out Direct
(h) 6D Held-Ou Direct
(i) 8D Held-Out Direct
Figure 12: Arithmetic: Results ADDITION and MULTIPLICATION of binary numbers, COT. Top row: In- in-Domain test data, Middle row: Held-Out test data (autoregressive decoding), bottom row: Held-Out test data (direct parallel decoding). Addition is learned well, even when the digits are directly decoded. contrast, multiplication does poorly.
33


Reviews:
[{"review_id": "Z4g9WE2ndb", "reviewer": "Reviewer_Does", "summary": "This paper establishes that hard-attention transformers require chain-of-thought (CoT) sequences of length linear in the input size to solve high-sensitivity algorithmic tasks like MEDIAN, and REACHABILITY in layered DAGs, with bounds tight up to logarithmic factors. By leveraging sensitivity analysis and a novel application of random restrictions, the authors prove that sublinear CoT steps would render these functions reducible to constants, which is impossible due to their inherent sensitivity, and further show that \"dot-by-dot\" CoTs require super-polynomial lengths. Empirical validation on synthetic tasks confirms sharp accuracy declines with sublinear CoT, while tests on real LLMs corroborate the necessity of sufficient intermediate steps.", "questions": "", "limitations": "", "rating": 2, "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": "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.\n\n1. 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.\n\n    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.\n\n    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).\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\nFinally, 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.\n\n---\n\n[1] Abbe et al. \"How far can transformers reason? the globality barrier and inductive scratchpad.\" NeurIPS 2024.\n\n[2] Hahn and Rofin. \"Why are Sensitive Functions Hard for Transformers?\" ACL 2024.\n\n[3] Jerad et al. \"Unique Hard Attention: A Tale of Two Sides.\" arXiv preprint arXiv:2503.14615 (2025).\n\n[4] Li et al. \"Chain of thought empowers transformers to solve inherently serial problems\" ICLR 2024", "claims_and_evidence": "All claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The experiments make sense.", "theoretical_claims": "The theorems in paper make sense, and I believe they are correct. However, I didn't check the proof line by line.", "experimental_designs_or_analyses": "The experimental designs are valid.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths**  \n1. **Theoretical Rigor**: The paper provides a foundational analysis using tools from circuit complexity (e.g., sensitivity, random restrictions) to derive lower bounds, rigorously extending prior work on transformer expressivity. \n2. **Empirical Alignment**: Synthetic experiments validate theoretical predictions, with clear accuracy drops when CoT lengths are sublinear. Tests on real LLMs strengthen practical relevance, bridging theory and practice.  \n3. **Clarity**: The exposition is well-structured, with intuitive explanations of sensitivity and UHAT transformers, making complex theoretical arguments accessible.  \n\n### **Weaknesses**  \n1. **UHAT Assumption**: The reliance on *unique hard attention* limits direct applicability to real-world transformers, which use soft attention. While the authors justify UHAT for theoretical tractability, the practical implications for standard transformers remain limited.  \n2. **Scalability of Experiments**: Synthetic tasks use small inputs (e.g., 16-bit integers), raising questions about generalization to larger scales. While pragmatic for controlled validation, broader empirical tests (e.g., 64-bit MULTIPLICATION) could strengthen claims.", "other_comments_or_suggestions": "The template seems to be wrong.", "questions_for_authors": "Please refer to the weakness.", "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": "fK8Bokl6nm", "reviewer": "Reviewer_PLKX", "summary": "This paper establishes lower bounds on the required chain-of-thought (CoT) length that unique hard-attention (UHAT) transformers need for solving certain classes of problems.\nIn particular, lower bounds are established for PARITY ($\\Omega(N)$), MULTIPLICATION ($\\Omega(N)$), MEDIAN ($\\Omega(N)$), and REACHABILITY ($\\Omega(\\lvert E \\rvert \\log \\lvert V \\rvert)$), where $N$ is the length of the input.\nEmpirical experiments on both synthetic setups and LLMs validate the paper's claims.", "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": "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.\n\nIf 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.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This improves our understanding of LLM expressivity.", "essential_references_not_discussed": "None that I'm aware of.", "other_strengths_and_weaknesses": "Strengths:\n* This paper is quite solid and improves our understanding of transformer expressivity.\n* Complexity lower bounds are appreciated, as they tend to be harder to prove than upper bounds.\n* The list of FAQs in Appendix A resolves many of the questions I initially had.\n* This is a good paper.\n\n\nWeaknesses:\n* I do not see clear weaknesses in this paper.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "1w5jzyPLSu", "reviewer": "Reviewer_M2re", "summary": "This paper explores the use of CoT reasoning and scratchpads in enhancing the computational capabilities of transformers. The authors propose new lower bounds for the number of CoT steps required for various algorithmic problems, challenging optimistic bounds from circuit complexity.", "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": "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:\n\n1. On the restrictiveness of our approach due to the use of hard attention and binary input/output format:\n\n    We agree that hard attention is a simplifying assumption, though it is amply supported by interpretability studies as we cited in Appendix E.1. \n    \n    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.\n\n\n    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.\n\n2. On neglecting the logical progression in CoT reasoning:\n\n    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.\n    \n3. On arbitrary assumptions, specifically $|{i ≤ N : ρ_N (i) = ∗}| ≥ CN$:\n\n   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.\n\n4. On unexplained symbols:\n\n    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 *$.\n    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.\n    \n5. On experiments not supporting the statement that $O(n)$ is the lower bound of the complexity:\n\n    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.\n    \n6. On relation to [1] (Feng et al. 2023) and [2] (Chen et al. 2024):\n    \n    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.\n\n    [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.\n    \n7. On discussing interpretability of the CoT:\n    \n    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.\n    \n8. On excessively strong assumptions:\n\n    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.\n\n---\n\n[3] Jerad et al. \"Unique Hard Attention: A Tale of Two Sides.\" arXiv preprint arXiv:2503.14615 (2025).", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "I believe the analysis method is overly restrictive, particularly with the use of hard transformers and 0-1 digit operations. It seems difficult to accurately represent real-world scenarios using these approaches.\n\nFurthermore, I think the model completely neglects the logical progression inherent in CoT reasoning. Treating all outputs as equivalent tokens seems problematic, especially for long dialogues where the summary might be treated in the same way. This approach doesn't appear to be reasonable.", "theoretical_claims": "I have examined the proof process. The proof contains numerous assumptions that are either arbitrary or difficult to relate to practical contexts. For example, the assumption |{i ≤ N : ρN (i) = ∗}| ≥ CN is completely unclear in terms of its rationale, and the corresponding proof seems to fail to justify this core inequality.\n\nAdditionally, there are many unexplained symbols, such as *, ρ|x|, and |{i ≤ N : ρN (i) = ∗}|.", "experimental_designs_or_analyses": "The conclusion of this experiment does not seem to indicate that O(n) is the lower bound of the complexity. At the same time, the conclusions of these experiments appear to be similar to those in [1, 2].\n\n[1] Towards revealing the mystery behind chain of thought: A theoretical perspective. NeurIPS 2023\n\n[2] Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought. NeurIPS 2024", "relation_to_broader_scientific_literature": "None.", "essential_references_not_discussed": "In fact, there has already been some detailed discussion on CoT Boundaries in previous work. Please analyze in detail the differences between the following works and your proposed boundary:\n1. Towards revealing the mystery behind chain of thought: A theoretical perspective. NeurIPS 2023\n2. Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought. NeurIPS 2024\n\nFurthermore, there is a lack of significant work focusing on the interpretability of CoT. Relevant works include:\n1. Wang et al. How Large Language Models Implement Chain-of-Thought? Arxiv 2023.\n2. Hanna et al. How does gpt-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language model. NeurIPS 2023.\n3. Dutta et al. How to think step-by-step: A mechanistic understanding of chain-of-thought reasoning. TMLR 2024.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "None.", "questions_for_authors": "- Could you please elaborate on the specific differences between this work and previous research mentioned above?\n-  The experimental results do not seem to conclusively demonstrate that O(n) is the lower bound of the complexity. It would be helpful to see a more rigorous argument or further evidence supporting this claim.\n- The assumptions made in this work appear to be quite strong, potentially even stronger than those in the original work by Feng et al. [1]. It might be useful to provide additional justification or relax some of these assumptions, to ensure the findings are robust and applicable in a wider range of scenarios.\n\n[1] Feng et al. Towards revealing the mystery behind chain of thought: A theoretical perspective. NeurIPS 2023", "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: The paper presents lower bounds on the chain-of-thought (CoT) length required by unique hard-attention (UHAT) transformers to solve high-sensitivity algorithmic tasks (like median or reachability). Proof uses sensitivity theory and random restrictions, and bounds are tight up to logarithmic factors. This is a nice theoretical contribution to the literature on the expressive power of transformers. The model is mostly in line with what is used in practice, except for the use of unique hard attention instead of the commonly used soft attention. This is a restrictive assumption, but it is justified, given the difficulty of proving theoretical lower bounds on soft-max transformers. Overall, this is a nice theoretical contribution and can be accepted to ICML.
Decision: Accept (poster)