Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
By Zhiyuan Li, Hong Liu, Denny Zhou, Tengyu Ma. International Conference on Learning Representations, 2024
299 citations recorded by the source corpus.
Instructing the model to generate a sequence of intermediate steps, a.k.a., a chain of thought (CoT), is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. However, the mechanism behind CoT remains unclear. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness. Conceptually, CoT empowers the model with the ability to perform inherently serial computation, which is otherwise lacking in transformers, especially when depth is low. Given input length $n$, previous works have shown that constant-depth transformers with finite precision $\mathsf{poly}(n)$ embedding size can only solve problems in $\mathsf{TC}^0$ without CoT. We first show an even tighter expressiveness upper bound for constant-depth transformers with constant-bit precision, which can only solve problems in $\mathsf{AC}^0$, a proper subset of $ \mathsf{TC}^0$. However, with $T$ steps of CoT, constant-depth transformers using constant-bit precision and $O(\log n)$ embedding size can solve any problem solvable by boolean circuits of size $T$. Empirically, enabling CoT dramatically improves the accuracy for tasks that are hard for parallel computation, including the composition of permutation groups, iterated squaring, and circuit value problems, especially for low-depth transformers.
Subfields: Hardware and Architecture
View Paper: https://www.semanticscholar.org/paper/5a20aa49b81b4e14fdb36814e557b3da60259ce9
Citations in the corpus
- GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models (2024, unknown): “For example, parallels have been drawn between components such as attention and feed-forward modules and simple computational primitives (Weiss et al., 2021; Zhou et al., 2024).”
- Training Large Language Models to Reason in a Continuous Latent Space (2024, unknown): “Recent theoretical analyses have demonstrated the usefulness of CoT from the perspective of model expressivity (Feng et al., 2023; Merrill and Sabharwal, 2023; Li et al., 2024).”
- CRANE: Reasoning with constrained LLM generation (2025, unknown): “However, following existing works (Hahn, 2020; Merrill & Sabharwal, 2023; Li et al., 2024) and for simplicity in the theoretical setup in Section 3, we assume that the output of L on any input string xxx is deterministic in both constrained and unconstrained settings.”