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

Alireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn · 2025

Read Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers by Alireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02393.txt.

Introduction

Chat models think out loud, step by step, and those steps add real power to what they can solve. Alireza Amiri, Xinting Huang, Mark Rofin, and Michael Hahn ask in 2025 how many steps a hard task truly needs. Their test bed is a strict form of the model where focus picks one spot at a time.

For a shelf of set tasks, the team proves floor counts on step length. The floors are tight, up to a small log slack. Some easy class tasks, such as parity, still need long chains in this strict form, which matches what users see. The work starts a firm scale for when step by step thought helps and when it can not.

Catalog record

CREATORAlireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE106 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-02393

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers Alireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn 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 T ​ C 0 TC^{0} to P ​ T ​ I ​ M ​ E PTIME , their required length remains poorly understood. Empirical evidence even suggests that transformers need scratchpads even for many problems in T ​ C 0 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 1 1 1 Code link: https://github.com/lacoco-lab/scratchpad_bounds . 1 Introduction Chain-of-Thought reasoning (CoT) has become a standard practice for solving hard problems with LLMs, enhancing 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 o1 ( Jaech et al., 2024 ) and DeepSeek-R1 ( Guo et al., 2025 ) . Models trained under this paradigm are optimized to generate a long CoT before answering any user’s request, which significantly elevates their reasoning abilities. However, the use of CoT may substantially 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 sequences without compromising quality became an important research direction ( Deng et al., 2024 ) . At the same time, there is so far little understanding of the minimal sufficient length of the CoT in a given case; thus the theoretical limits of CoT compression are unclear. Figure 1 : High-sensitivity problems such as Parity are difficult to learnably and generalizably represent for transformers. Such problems can be solved by CoTs decomposing them into a sequence of local steps. We study the length that such CoTs need to have, as a function of the input length. To gain understanding of those limits, we take up the problem of provably bounding the length of CoT sequences sufficient to solve various algorithmic problems with transformers. By providing the lower bounds on the length of the CoT, our paper complements an established line of research on the expressive power of transformers that has focused on the model size when the answer is provided without CoT ( Strobl et al., 2023 ; Bhattamishra et al., 2020a ; Sanford et al., 2024b ; Chen et al., 2024 , e.g.) . A simple example is the Parity function – deciding whether the number of 1’s in a bit string is even or odd. Transformers empirically struggle to learn it on longer inputs ( Bhattamishra et al., 2020a ; Delétang et al., 2023 ; Butoi et al., 2024 ; Hahn & Rofin, 2024 , e.g.) , and this difficulty is resolved by a CoT consisting of the parities of increasing prefixes, as in Figure 1 ( Anil et al., 2022 , e.g.) . Here, every decoding step depends only on a bounded number of tokens. However, for an input of length N , this CoT requires \Theta(N) extra decoding steps, a substantial computational burden. 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 CoTs . This 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 ) . 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 position where attention weights are maximized ( 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 , e.g.) . 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 ) . In this model, we rigorously prove that the CoT for Parity described above is optimal up to constant factors (Theorem 4.2 ). Besides Parity , we consider three other tasks ( Multiplication , Median , Reachability ) that are also empirically challenging for transformers to solve without 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 to logarithmic factors . Overall, these lower bounds place broad constraints on the inference-time compute needed to enable transformers to solve these problems. 2 Background 2.1 Sensitive Functions Require CoTs Prior work has often studied the abilities of transformers through the lens of circuit complexity ( Hao et al., 2022 ; Merrill & Sabharwal, 2023a ; Strobl, 2023 ; Feng et al., 2023 ; Li et al., 2024 ; Chiang, 2025 ; Merrill & Sabharwal, 2023b , e.g.) . Transformers express a subset of the circuit complexity class TC^{0} , which covers problems solvable by bounded-depth threshold circuits ( Merrill & Sabharwal, 2023b ; Strobl, 2023 ; Chiang, 2025 ) . By the unproven conjecture TC^{0}\neq NC^{1} , many problems, such as graph reachability, are thus not solvable by transformers without CoTs. Hence, the success of CoT has been linked to its ability to expand expressiveness beyond TC^{0} ( Feng et al., 2023 ; Merrill & Sabharwal, 2024a ; Li et al., 2024 ) . However, CoT is empirically beneficial even for tasks well in TC^{0} , such as Parity ( Anil et al., 2022 ) : Parity is expressible in TC^{0} 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 ( Bhattamishra et al., 2020a , e.g.) unless a CoT is provided ( Anil et al., 2022 , e.g.) . Hahn & Rofin (2024) show that this fact can be explained in terms of the loss landscape: Transformers require very sharp minima to represent 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 a CoT. In fact, the result of Hahn & Rofin (2024) extends beyond Parity , and is grounded in a foundational concept in the analysis of Boolean Functions, sensitivity . For a boolean function f:\{0,1\}^{*}\rightarrow\{0,1\} , the sensitivity counts how many Hamming neighbors have the opposite output: s(f,x)=\left|\{i=1,\dots,|x|\text{ such that }f(x)\neq f(x^{\oplus i})\}\right|

Read the complete text