Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

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

T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that any chain-of-thought for PARITY, the middle digit of multiplication, MEDIAN, or DAG reachability in a hard-attention transformer must have at least linear length, with matching constructive upper bounds up to…

desk verdict A genuinely new generic CoT lower bound for UHAT, but the load-bearing depth-reduction lemma is asserted without proof and needs to be written out before the results can be trusted. read the letter →

arxiv 2502.02393 v3 pith:IQ7RFFOC submitted 2025-02-04 cs.LG cs.CC

Alireza Amiri , Xinting Huang , Mark Rofin , Michael Hahn This is my paper · ORCID
classification cs.LGcs.CC
keywords chain-of-thoughtuniquehardattentionlowerboundsrandomrestrictionsaveragesensitivityPARITYscratchpadstransformers
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that several basic algorithmic problems cannot be solved by hard-attention transformers with a short chain-of-thought: the number of intermediate reasoning tokens must grow at least linearly with the input size. The central theorem says that if a function has a sublinear-length chain-of-thought in the unique-hard-attention (UHAT) model, then fixing a constant fraction of the input positions already fixes the output; PARITY, the middle bit of multiplication, MEDIAN, and DAG reachability all stay unfixed under any such restriction, so they force linear (or larger) scratchpad length. The bounds are tight up to logarithmic factors, with explicit constructions: prefix parities, a Fourier-transform multiplication scratchpad of length $O(N \log N)$, enumeration of the lower half for MEDIAN, and a breadth-first-search scratchpad for reachability. These results put a provable limit on the inference-time compute that can be saved by compressing or jumping over chain-of-thought steps in transformers.

What carries the argument

The load-bearing object is the random restriction and its depth-reduction lemma (Lemma 3.4), a transformer analogue of the switching lemma for $\mathrm{AC}^0$ circuits: for any constant $C$, one restriction can fix a constant fraction of input positions so that every intermediate activation $y_i^{(l)}$ in a bounded-layer UHAT transformer depends on at most $c$ input positions. This strengthens the earlier depth-reduction lemma, which only preserved the final output, and the proof iterates it $L$ times to get a single restriction valid for all layers. Theorem 3.3 then appends the chain-of-thought to the restriction: because each autoregressive step's activation depends on the previously fixed CoT tokens and only $O(1)$ input positions, fixing $O(|g|)$ extra input bits pins down the whole CoT. When $|g| = o(N)$, the restriction still leaves a constant fraction of the input free while the output is fixed, and that is exactly the structure that high-sensitivity functions forbid.

What would settle it

A counterexample would be a UHAT transformer family with constant layers and heads together with a chain-of-thought of length $o(|x|)$ that computes PARITY on all inputs under the paper's Definition 2.2; finding one would refute Theorem 4.2. More directly, build a two-layer UHAT transformer and a constant $C$ such that every restriction leaving at least $CN$ positions free leaves some intermediate activation at layer 2 dependent on more than a bounded number of input positions—that would disprove Lemma 3.4, the strengthened depth-reduction lemma on which the main theorem rests.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 3.3: if $f$ has a UHAT-expressible chain-of-thought $g(x)$ of length $|g(x)| = o(|x|)$, then for every $C \in (0,1)$ there is a restriction $\rho$ leaving at least $CN$ positions free such that $f$ is constant on the remaining strings. The proof obtains a random restriction that makes every intermediate activation depend on a bounded number of input positions (Lemma 3.4), then fixes $O(|g(x)|)$ further positions to pin down all chain-of-thought tokens one by one; if $|g(x)| = o(N)$, a constant fraction of the input stays free while the answer is already decided. Since PARITY, the middle digit $M_N$ of $N$-bit multiplication, MEDIAN, and DAG reachability cannot be made constant by fixing any constant fraction of positions, their chain-of-thought length must be $\Omega(N)$ (and $\Omega(|E|\log|V|)$ for reachability). These lower bounds are tight up to logarithmic factors via explicit UHAT scratchpads, and a further theorem shows that 'dot-by-dot' pause-token scratchpads for PARITY require superpolynomial length $\omega(|x|^k)$ for every $k$, while an exponential-length one exists.

Load-bearing premise

The load-bearing premise is the strengthened depth-reduction lemma (Lemma B.3): a single random restriction can make every intermediate activation of a bounded-layer UHAT transformer depend on only a constant number of input positions, whereas the previously published version of the lemma only made this guarantee for the final output; the paper states the stronger claim follows from the earlier proof but does not reproduce that proof, so if the strengthening fails, the generic CoT bound and all four applications collapse.

Editorial extensions

If this is right

  • PARITY requires a UHAT chain-of-thought of length $\Omega(N)$, and the prefix-parity scratchpad attains $\Theta(N)$, making the bound tight up to constants.
  • The middle output bit of $N$-bit binary multiplication requires UHAT chain-of-thought length $\Omega(N)$, while a number-theoretic transform scratchpad computes the full product in $O(N\log N)$ steps.
  • MEDIAN on $N$ numbers requires UHAT scratchpad length $\Omega(N)$, attained by a chain-of-thought enumerating the lower $\lfloor N/2\rfloor$ sorted elements.
  • DAG reachability requires UHAT chain-of-thought length $\Omega(|E|\log|V|)$, attained by a breadth-first-search scratchpad, and this lower bound holds unconditionally without assuming $\mathrm{TC}^0 \neq \mathrm{NC}^1$.
  • Dot-by-dot scratchpads—sequences of pause tokens followed by the answer—cannot solve PARITY in polynomial length: their length must be $\omega(|x|^k)$ for every $k$, a superpolynomial separation from ordinary chain-of-thought.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An editorial extension of the restriction criterion: any Boolean function that cannot be made constant by fixing a constant fraction of its input bits automatically inherits a linear UHAT chain-of-thought lower bound, so the generic theorem is a reusable test for other high-sensitivity tasks such as counting modulo $m$ or evaluating a formula whose value depends on all variables.
  • The paper proves the UHAT lower bounds and notes that UHAT upper-bounds fixed-precision softmax transformers; I infer the practical lesson for LLMs is that attempts to distill or skip chain-of-thought steps on these tasks will hit an architectural floor, unless the model can use extra depth, tools, or a non-hard attention mechanism.
  • The dot-by-dot superpolynomial bound suggests a precise, testable difference between explicit and implicit reasoning: a pause-token-only model should fail to length-generalize on PARITY, whereas a model emitting explicit per-position parity tokens should succeed; the paper's LLM trace experiments are consistent with this, but the causal claim is an inference beyond its theorems.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies lower bounds on the length of chain-of-thought (CoT) sequences required by unique-hard-attention transformers (UHAT). The main technical result is Theorem 3.3, a generic CoT lower bound: if a function f has a UHAT-expressible CoT of length o(n), then for any C < 1 there is a restriction leaving at least Cn input positions free on which f is constant. From this the authors derive Omega(n) lower bounds for PARITY (Theorem 4.2), for the middle digit of N-bit multiplication (Theorem 4.5), for the last bit of MEDIAN (Theorem 4.8), and an Omega(|E| log |V|) bound for reachability in a specific DAG family (Theorem 4.10), with matching upper bounds up to logarithmic factors. The paper also shows that dot-by-dot CoTs for PARITY must have superpolynomial length and provides experimental evidence on trained transformers and LLMs. The central proof relies on Lemma B.3, a stated strengthening of a random-restriction depth reduction lemma from Hahn (2020), whose proof is not reproduced in the manuscript.

Significance. If Theorem 3.3 and its applications are correct, the paper makes a substantial contribution: it gives the first systematic, unconditional lower bounds on CoT length for a range of algorithmic problems in the UHAT model, and the bounds are tight up to polylogarithmic factors. The matching upper bounds, including the O(N log N) multiplication scratchpad via the number-theoretic transform and the BFS-based reachability scratchpad, are valuable and non-obvious. The experiments complement the theory by showing that the proposed scratchpads are learnable and that models without scratchpads fail on these tasks. However, the central claim currently rests on an unproven strengthening of a prior lemma, and several application proofs assert rather than demonstrate the required restriction-robustness of the target functions. For these reasons, the paper cannot be accepted in its present form, but the issues appear fixable by supplying the missing proof details.

major comments (4)
  1. [Appendix B.1, Lemma B.3] The strengthened depth reduction lemma is load-bearing for the entire paper, yet its proof is not given. The text asserts: 'by the way T' is obtained in that proof, the stronger statement for all activations follows.' This is not sufficient for a journal proof, especially because Lemma 3.4 is proved by iterating Lemma B.3 L times, and Theorem 3.3 relies on that iteration. If the strengthening fails, the single restriction needed to make every layer's activations depend on at most c input positions need not exist, and the generic CoT bound and all four application theorems collapse. The authors should include a complete, self-contained proof of Lemma B.3, or at least a detailed derivation of the strengthened statement from the construction in Hahn (2020), showing explicitly why simultaneous preservation of all intermediate activations holds.
  2. [Appendix C.2.1, Theorem 4.5] The proof of the multiplication lower bound is a single sentence: 'Now if one fixes CN input bits, for C small, the result cannot be fixed.' This is precisely the kind of claim that needs proof: one must show that for every restriction with a constant fraction of free positions, the middle digit M_N is not constant on the remaining strings. The intuitive argument based on high-degree parity is complicated by carries, and the one-sentence argument does not rule out the possibility that a cleverly chosen restriction fixes the digit. A rigorous argument is required, likely by exhibiting a pair of inputs consistent with the restriction with different M_N, or by a Fourier-analytic sensitivity argument.
  3. [Appendix C.3, Theorem 4.8] The MEDIAN proof similarly asserts: 'fixing, say, 1/10 N digits cannot fix the median.' This is not evident and in fact depends delicately on the relationship between the number of bits B and N, as the paper itself acknowledges in the regime discussion. A proof must show that for every restriction with a constant fraction of free positions, the last bit of the median is not constant on the restricted subcube. The current proof does not provide this, so the application of Theorem 3.3 is not justified as written.
  4. [Appendix C.4.1, Theorem 4.10] In the reachability proof, the statement 'fixing a small constant fraction of edges, while staying within G, cannot fix the reachability' is asserted without proof. Since the graph family G is designed to encode PARITY, a careful argument is needed to show that any restriction fixing fewer than a constant fraction of edges leaves at least one pair of vertices whose reachability remains variable. The current proof is too brief to be checked, and this step is necessary to apply Theorem 3.3 to the reachability lower bound.
minor comments (5)
  1. [Definition 3.2] There is a typo: 'a a family' should be 'a family'.
  2. [Section 4.2] The word 'precisioin' appears in the sentence 'not fixed-precisioin transformers'; it should be 'precision'.
  3. [Appendix B.2] The word 'superceeding' should be 'superseding'.
  4. [Theorem 4.6] The theorem states that there is a scratchpad of length O(N log N) for multiplication, but the construction in Appendix C.2.3 relies on an unbounded CoT alphabet and modular arithmetic encoded in the MLP; this is fine for the lower-bound model, but the text should clarify that the upper bound is in the same UHAT model with unbounded alphabets and not in a fixed-precision setting.
  5. [Figure 2] The caption says 'Left: CoTs consisting of prefix sum parities' but the figure appears to show two panels; the description of the right panel ('Dot-by-dot scratchpads help much less') would benefit from a clearer explanation of the axes and the dotted diagonal line.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower-bound chain is an implication from an external depth-reduction lemma; the asserted strengthening of Hahn (2020) is an unproved step but not a reduction to the paper's own inputs.

full rationale

The paper's derivation chain is: Lemma B.3, a depth-reduction lemma for UHAT transformers, is borrowed from Hahn (2020) and asserted in a strengthened form; Lemma 3.4 is obtained by iterating it L times; Theorem 3.3 is proved by applying Lemma 3.4 to the input and then inductively fixing o(N) additional input positions to pin down all CoT tokens; the application theorems then follow by showing that fixing a constant fraction of input bits cannot fix PARITY, middle-digit multiplication, MEDIAN, or DAG reachability. Each of these steps is an ordinary implication and none of the statements is defined in terms of the conclusion it is used to prove. The only potentially concerning step is the self-citation to Hahn (2020) for Lemma B.3, where the paper says 'This is a stronger statement of Lemma 4 of Hahn (2020)' and does not reproduce the proof of the strengthened claim. That is a load-bearing correctness risk: if the strengthening is false, Theorems 3.3, 4.2, 4.5, 4.8, and 4.10 would not follow. But it is not circularity: the cited lemma is an external, published result about hard-attention transformers, and the asserted strengthening is a claim about the internal construction of that proof, not an assumption of the lower bounds being derived. No parameters are fitted to data and later relabeled as predictions; the experiments illustrate the upper bounds and empirical behavior but do not feed fitted values into the theoretical derivation. Accordingly, no claimed prediction reduces by construction to its inputs, and the paper does not rename a known result as a new one. The correct finding is no significant circularity, with the omitted-proof concern recorded separately as a correctness risk.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theory is a pure math contribution: no free parameters are fitted. The main axioms are the UHAT model definition, the worst-case CoT length formalization, and the strengthened Hahn (2020) depth-reduction lemma (Lemma B.3), which is the main unproven dependency. Standard results used include Barrington et al. on regular languages in AC0, Boppana's average-sensitivity bound for AC0, and the inclusion of UHAT in AC0.

assumptions (5)
  • domain assumption UHAT model with causal masking, bounded layers/heads, arbitrary MLP and unbounded width (Definition 2.2).
    The entire lower-bound framework is defined relative to this model; the authors explicitly note (FAQ 8) that real softmax transformers differ, so this is a modeling assumption rather than an empirical fact.
  • ad hoc to paper Strengthened Depth Reduction Lemma B.3: a single restriction leaves at least C'N positions free and makes every activation y_i^{(l)} depend on at most c input positions (strengthening Hahn 2020, Lemma 4).
    This is the load-bearing unproven step; the paper says it follows from the proof in Hahn (2020) but does not reproduce that proof or verify the strengthening to all activations and to arbitrary finite alphabets/causal masking.
  • ad hoc to paper For each problem, fixing a constant fraction of input bits cannot fix the output (used for PARITY, multiplication digit M_N, MEDIAN last bit, reachability in the parity-encoding DAG family).
    These 'cannot be fixed' claims are asserted in Appendices C.1-C.4 without detailed combinatorial proof; PARITY is self-evident, but the multiplication, median, and reachability versions are less immediate.
  • standard math Barrington et al. (1992): a regular language is in AC0 iff its syntactic monoid is quasi-aperiodic.
    Used in Corollary 4.3 to classify regular languages and reduce mod-k counting to membership.
  • standard math Boppana (1997) / Linial-Mansour-Nisan: AC0 functions have polylogarithmic average sensitivity; UHAT is contained in AC0 (Hao et al. 2022).
    Used for the dot-by-dot CoT lower bound (Theorem 4.11) and for sensitivity arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers." pith.science (2026). https://pith.science/paper/IQ7RFFOC

@misc{pith2026250202393,
  author       = {Pith},
  title        = {Pith review of: Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQ7RFFOC}},
  note         = {Machine review of arXiv:2502.02393}
}
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 chain-of-thought 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.

Figures

Figures reproduced from arXiv: 2502.02393 by the authors.

Figure 1
Figure 1. 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 a sequence of local steps. We study the length that such CoTs need to have, as a function of the input length. quences without compromising quality became an important research direction (Deng et al., 2024). At the same time, there is so far lit… view at source ↗
Figure 2
Figure 2. Results for PARITY. Left: CoTs consisting of prefix sum parities, accuracy as a function of input and CoT lengths. CoTs of length Θ(N) succeed even on very long inputs. Right: Dot-by-dot scratchpads help much less, even when much longer then the input (Theorem 4.11). 4.2. Multiplication We next examine basic arithmetic operations. For N-digit numbers, both addition and multiplication are in T C0 , and both operation… view at source ↗
Figure 3
Figure 3. Accuracy of a transformer trained on autoregres [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Results for MEDIAN: CoTs consisting of the sorted first ⌊N/2⌋ numbers. Accuracy as a function of input and CoT lengths. lengths at which a transformer is learned successfully. 5. Discussion 5.1. Implications Across Sections 4.1–4.4, our lower bounds are tight up to pol…
Figure 4
Figure 4. Figure 4: Results for DAG reachability. Without a CoT, the [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 6
Figure 6. Figure 6: Length of reasoning traces of DeepSeek R1 ( [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: Arithmetic. Average sensitivity (Section [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: Accuracy of transformers trained on 12-digit multiplication (most significant digit at the left, zero-padded on [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. 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. = X i,j 2 i+j ξiηj = X k 2 k X i+j=k ξiηj Hence, the N-th digit of XY , MN , …
Figure 10
Figure 10. Figure 10: Average sensitivity of the last digit of [PITH_FULL_IMAGE:figures/full_fig_p028_10.png]
Figure 11
Figure 11. Figure 11: Multiplication: Comparing the number of tokens used in the [PITH_FULL_IMAGE:figures/full_fig_p032_11.png]
Figure 12
Figure 12. Figure 12: Arithmetic: Results on ADDITION and MULTIPLICATION of binary numbers, no CoT. Top row: 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 dig…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

    cs.LG 2025-11 conditional novelty 6.0 of 10

    Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.

Reference graph

Works this paper leans on

44 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [1]

    The situation is different for parallel computation as performed by transformers: Many problems do have direct parallel solutions

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

    work page

  2. [2]

    All lower bounds in this paper are essentially on the order of Ω(N ) or Ω(N log N ). Do any algorithmic problems require substantially 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 CoT...

    work page

  3. [3]

    Chen, L., Peng, B., and Wu, H

    URL https://openreview.net/forum? id=QBCxWpOt5w. Chen, L., Peng, B., and Wu, H. Theoretical lim- itations of multi-layer transformer. arXiv preprint arXiv:2412.02975, 2024. Chiang, D. Transformers in uniform TC $ˆ0$. Transac- tions on Machine Learning Research, 2025. ISSN 2835-

    arXiv 2024

  4. [4]

    Implementations of self-attention already have quadratic complexity. Why should one be concerned with a further linear number of CoT steps? It is true that generating N tokens, with KV-Cache, will have just O(N 2) complexity, asymptotically the same as directly providing an answer. However, it can still lead to substantial overhead, even if just by a cons...

    work page

  5. [5]

    Feng, G., Yang, K., Gu, Y ., Ai, X., Luo, S., Sun, J., He, D., Li, Z., and Wang, L

    URL https://openreview.net/forum? id=qHrADgAdYu. 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 llms. arXiv preprint arXiv:2410.13857, 2024. Furst, M., Saxe, J. B., and Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Mathematical s...

    arXiv

  6. [6]

    11 Lower Bounds for CoT Reasoning Kim, N

    URL https://openreview.net/forum? id=E7HwPhfX1B. 11 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. Kozachinskiy, A. Lower bounds on transformers with infi- nite precision. arX...

    arXiv 2023

  7. [7]

    Qiu, R., Xu, Z., Bao, W., and Tong, H

    URL https://openreview.net/forum? id=NikbrdtYvG. Qiu, R., Xu, Z., Bao, W., and Tong, H. Ask, and it shall be given: Turing completeness of prompting. arXiv preprint arXiv:2411.01992, 2024. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language Models are Unsupervised Multi- task Learners. OpenAI, 2019a. Radford, A., Wu, J., Child...

    arXiv 2024

  8. [8]

    URL https: //doi.org/10.48550/arXiv.2308.03212

    doi: 10.48550/ARXIV .2308.03212. URL https: //doi.org/10.48550/arXiv.2308.03212. Strobl, L., Merrill, W., Weiss, G., Chiang, D., and Angluin, D. Transformers as recognizers of formal languages: A survey on expressivity. CoRR, abs/2311.00208, 2023. doi: 10.48550/ARXIV .2311.00208. URL https:// doi.org/10.48550/arXiv.2311.00208. Svete, A. and Cotterell, R. ...

    arXiv doi:10.48550/arxiv.2308.03212

Show all 44 references
  1. [9]

    CoT lower bounds are proven for hard attention, while experiments are conducted with softmax attention. Isn’t there a mismatch between theory (hard attention) and experiments (softmax transformers)? It is true that we do not conduct experiments in the hard-attention setup, bec...

    2020

  2. [11]

    Transformers are already known to be Turing-complete. Why does this paper construct CoTs for the algorithmic problems – isn’t reducing to known Turing machine constructions enough? Compared to modern random-access models, single-tape Turing machines (as used in typical Turing ...

  3. [13]

    For instance, PARITY is a simple example of state tracking, a family of reasoning problems that have been of substantial interests and that still pose challenges for LLMs (e.g

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

    2024

  4. [14]

    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

    Definition 2.1 enforces a finite input alphabet, but allows an infinite CoT 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 no...

    2020

  5. [15]

    Isn’t this unrealistic? What about the role of length generalization? It is true that, in practice, one will expect transformers to perform the tasks across input lengths

    Definition 2.2 allows using different transformers T at every input length. Isn’t this unrealistic? What about the role of length generalization? It is true that, in practice, one will expect transformers to perform the tasks across input lengths. However, the theoretical lite...

    2023

  6. [16]

    In particular, UHAT is bounded by AC 0, whereas softmax transformers are bounded by T C0

    The results in this paper are proven for a hard-attention model, whereas real-world implementations use softmax attention, which can express functions that hard-attention transformers cannot. In particular, UHAT is bounded by AC 0, whereas softmax transformers are bounded by T...

    2024

  7. [18]

    |{i : ρ(i) = ∗}| ≥CN

  8. [19]

    By applying Lemma B.3 iteratively, L times

    within ρΣ∗, each y(l) i is determined by ≤ c 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 1 of Hahn (2020) independently to each layer of a Transforme...

    2020

  9. [20]

    Here, “ρ(3)” corresponds to the restriction ρ′ from the statement of the lemma

    |{i ≤ N : ρN (i) = ∗}| ≥Cn for sufficiently large N 5“We can thus remove layer 0, convert layer-1 activationsy(1) j into layer-0 activations y(0) j , and obtain a (c · (2ckH + 1))-transformer performing the same computation as before when ρ(3) is applied.” (quoted from Hahn, 2...

    2020

  10. [21]

    First, we obtain a restriction ρ(0), and integers c, k from Lemma 3.4, applying T only on the input x ∈ Σ∗ itself

    For each N ∈ N, f is constant on ΣN ∩ ρΣ∗ Proof. First, we obtain a restriction ρ(0), and integers c, k from Lemma 3.4, applying T only on the input x ∈ Σ∗ itself. For any N > k, we now consider the following. Let M := max|x|=N |g(x)|. Without loss of generality, we can pad th...

  11. [22]

    For each l ∈ [0, L], i ∈ [1, k− 1], the activation y(l) N +i is constant on all strings in ΣN ∩ ρ(k) N Σ∗

  12. [23]

    dot-by-dot CoT

    g1 . . . gk ∈ Ξk is constant on all strings in ΣN ∩ ρ(k) N Σ∗. We prove this by induction. Inductive Base (k = 1) We can fix y(1) N , . . . ,y(L) N by fixing at most ≤ c · L input positions, obtaining ρ(1) ≻ ρ, with {i : ρ(1)(i) = ∗} ≥ CN − c · L ≥ CN − 1 · c · H · L (9) Since...

    2024

  13. [24]

    a finite tape alphabet Σ

  14. [25]

    a finite state set Q

  15. [26]

    the action set A := {LEFT, RIGHT} ∪ {WRITE(σ) : σ ∈ Σ} (15)

  16. [27]

    a transition function δ, mapping Σ × Qto A × Q

  17. [28]

    a start state s0 ∈ Q

  18. [29]

    a terminating set T ⊂ Q with the following computation:

  19. [30]

    We consider a tape with positions 0, 1, 2,

  20. [31]

    All remaining tape positions hold a blank symbol BLANK ∈ Σ

    At the beginning, the machine starts at position 0 and in state s0; the tape holds a finite input word starting at 0, ending in a separator symbol. All remaining tape positions hold a blank symbol BLANK ∈ Σ

  21. [32]

    At each step, the next action and state are decided based on δ applied to the current state and the current tape symbol

  22. [33]

    The machine stops when a state from T is reached

  23. [34]

    We first encode the input word as a string over the input alphabet Σ, followed by a separator symbol

    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 a string over the input alphabet Σ, followed by a separator symbol. We then construct a CoT over the infinite alphabet Ξ := N × A ...

  24. [35]

    19 Lower Bounds for CoT Reasoning

    The input token ξ = (i, a, q) ∈ [0, N] × A × Qprovides the tape position i, the output a of δ, and the resulting state q. 19 Lower Bounds for CoT Reasoning

  25. [36]

    Turing programs

    An attention head attends to the last step at which the Turing machine head had been at tape position i while doing a WRITE operation. The key, given input token ξ′ = ( i′, a′, q′), is the one-hot vector indicating the tape position i′, an indicator for a′ ∈ {WRITE(σ) : σ}, an...

    2022

  26. [37]

    L ∈ AC 0 and f is expressible in UHAT without CoT

  27. [38]

    We show this using the characterization of regular languages in AC 0 by Barrington et al

    L is not decidable in AC 0, and any UHAT CoT for f has length Ω(N ) 20 Lower Bounds for CoT Reasoning Proof. We show this using the characterization of regular languages in AC 0 by Barrington et al. (1992) and the follow-up result on hard-attention transformers by Yang et al. ...

    1992

  28. [39]

    , M2N (and analogously for addition) in parallel

    Direct parallel decoding of each digit M1, . . . , M2N (and analogously for addition) in parallel. To avoid training separate transformers for each digit, we use a transformer encoder (i.e., transformer with bidirectional attention) reading in the two N-digt operands, and prov...

  29. [40]

    M2N (and analogously for addition)

    Autoregressive decoding of the result M1 . . . M2N (and analogously for addition). We expect that this setup is still difficult for MULTIPLICATION as discussed in Appendix C.2.2

  30. [41]

    We expect that this setup will make the task feasible for transformers

    Autoregressive decoding of the O(N log N )-length CoT. We expect that this setup will make the task feasible for transformers. Encoder-only Model for Direct Parallel Decoding: We employed a transformer encoder with 2 layers, 2 attention heads, a feed-forward network dimension ...

    2024

  31. [42]

    increment-by-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 ⪆ N 2 . This is illustrated in Figure 10. Hence, the task is challenging for transformers by the results rev...

    2024

  32. [43]

    Conjecture E.2 thus provides a more optimistic prediction here than our results

    (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

  33. [44]

    (2024) requires a linear-length CoT by Theorem 3.3, and can also be shown to not be representable at sub-linear average sensitivity under a reasonable input encoding

    (converging prediction) The Cycle task of Abb´e et al. (2024) requires a linear-length CoT by Theorem 3.3, and can also be shown to not be representable at sub-linear average sensitivity under a reasonable input encoding. Difficulty is predicted under both perspectives. Overal...

    2024

  34. [2023]

    Abb´e, E., Bengio, S., Lotfi, A., Sandon, C., and Saremi, O

    URL https://proceedings.mlr.press/ v202/abbe23a.html. Abb´e, 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 on Neural Information Processing Systems,

  35. [2024]

    Abbe, E., Cornacchia, E., Hazla, J., and Kougang-Yombi, D

    URL https://openreview.net/forum? id=FoGwiFXzuN. Abbe, E., Cornacchia, E., Hazla, J., and Kougang-Yombi, D. Learning high-degree parities: The crucial role of the initialization. arXiv preprint arXiv:2412.04910, 2024. Anil, C., Wu, Y ., Andreassen, A., Lewkowycz, A., Misra, V ...

    2024 arXiv

  36. [8856]

    Chiang, D

    URL https://openreview.net/forum? id=ZA7D4nQuQF. 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- tic...

    2022 arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.