Imagen de Portada

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Li, Zhiyuan, Liu, Hong, Zhou, Denny, Ma, Tengyu
Formato:	Preprint
Publicado:	2024
Materias:	Machine Learning Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
por: Amiri, Alireza, et al.
Publicado: (2025)

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

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

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

Inference Scaling vs Reasoning: An Empirical Analysis of Compute-Optimal LLM Problem-Solving
por: AbdElhameed, Marwan, et al.
Publicado: (2024)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
por: Li, Chenyang, et al.
Publicado: (2025)

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

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

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

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

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

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

Efficient Turing Machine Simulation with Transformers
por: Li, Qian, et al.
Publicado: (2025)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
por: Hu, Jerry Yao-Chieh, et al.
Publicado: (2024)

Certifiable Boolean Reasoning Is Universal
por: Li, Wenhao, et al.
Publicado: (2026)

Provably Overwhelming Transformer Models with Designed Inputs
por: Stambler, Lev, et al.
Publicado: (2025)

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
por: Thornton, Mitchell A.
Publicado: (2026)

Polyhedral Instability Governs Regret in Online Learning
por: Li, Yuetai, et al.
Publicado: (2026)

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

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

Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
por: Liu, Yuxi
Publicado: (2025)

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

Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
por: Chen, Yifang, et al.
Publicado: (2025)

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

Learning Tree Pattern Transformations
por: Neider, Daniel, et al.
Publicado: (2024)

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

Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances
por: Wang, Jie, et al.
Publicado: (2024)

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
por: Chandrasekaran, Gautam, et al.
Publicado: (2024)

Ask, and it shall be given: On the Turing completeness of prompting
por: Qiu, Ruizhong, et al.
Publicado: (2024)

Large Language Models on Small Resource-Constrained Systems: Performance Characterization, Analysis and Trade-offs
por: Seymour, Liam, et al.
Publicado: (2024)

Data Debugging is NP-hard for Classifiers Trained with SGD
por: Guo, Zizheng, et al.
Publicado: (2024)

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

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

Spiky Rank and Its Applications to Rigidity and Circuits
por: Hambardzumyan, Lianna, et al.
Publicado: (2026)

Low-Rank Matrix Approximation for Neural Network Compression
por: Cherukuri, Kalyan, et al.
Publicado: (2025)

Proximity to Losslessly Compressible Parameters
por: Farrugia-Roberts, Matthew
Publicado: (2023)

Decision Tree Learning on Product Spaces
por: Moakahr, Arshia Soltani, et al.
Publicado: (2026)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
por: Cao, Yang, et al.
Publicado: (2025)

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
por: Jacobs, Peter Matthew, et al.
Publicado: (2026)