Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amiri, Alireza, Huang, Xinting, Rofin, Mark, Hahn, Michael
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Why are Sensitive Functions Hard for Transformers?
by: Hahn, Michael, et al.
Published: (2024)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
by: Brösamle, Moritz, et al.
Published: (2026)

On the Computational Hardness of Transformers
by: Saha, Barna, et al.
Published: (2026)

The Expressive Power of Transformers with Chain of Thought
by: Merrill, William, et al.
Published: (2023)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
by: Cao, Yang, et al.
Published: (2024)

Subquadratic Algorithms and Hardness for Attention with Any Temperature
by: Gupta, Shreya, et al.
Published: (2025)

A Theory of Learning with Autoregressive Chain of Thought
by: Joshi, Nirmit, et al.
Published: (2025)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

Understanding the Emergence of Seemingly Useless Features in Next-Token Predictors
by: Rofin, Mark, et al.
Published: (2026)

New Hardness Results for Low-Rank Matrix Completion
by: Chawin, Dror, et al.
Published: (2025)

Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
by: Amir, Guy, et al.
Published: (2024)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
by: Huang, Zekai, et al.
Published: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

Learnability of Parameter-Bounded Bayes Nets
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Unique Hard Attention: A Tale of Two Sides
by: Jerad, Selim, et al.
Published: (2025)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
by: Chen, Siyu, et al.
Published: (2025)

Certifiable Boolean Reasoning Is Universal
by: Li, Wenhao, et al.
Published: (2026)

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

Circuit Complexity Bounds for RoPE-based Transformer Architecture
by: Chen, Bo, et al.
Published: (2024)

Generalized and Unified Equivalences between Hardness and Pseudoentropy
by: Hu, Lunjia, et al.
Published: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

On the Hardness of Learning One Hidden Layer Neural Networks
by: Li, Shuchen, et al.
Published: (2024)

Constant Bit-size Transformers Are Turing Complete
by: Li, Qian, et al.
Published: (2025)

A Logic for Expressing Log-Precision Transformers
by: Merrill, William, et al.
Published: (2022)

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
by: Wang, Xiao
Published: (2026)

Hardness of Maximum Likelihood Learning of DPPs
by: Grigorescu, Elena, et al.
Published: (2022)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
by: Li, Xiaoyu, et al.
Published: (2024)

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
by: Merrill, William, et al.
Published: (2025)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
by: Nagda, Ansh, et al.
Published: (2025)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, et al.
Published: (2024)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
by: Sälzer, Marco, et al.
Published: (2024)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

Fundamental Limitations on Subquadratic Alternatives to Transformers
by: Alman, Josh, et al.
Published: (2024)

Distribution-Specific Agnostic Conditional Classification With Halfspaces
by: Huang, Jizhou, et al.
Published: (2025)