Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective
By Guhao Feng, Yuntian Gu, Bohang Zhang, Haotian Ye, Di He, Liwei Wang. Neural Information Processing Systems, 2023
451 citations recorded by the source corpus.
Recent studies have discovered that Chain-of-Thought prompting (CoT) can dramatically improve the performance of Large Language Models (LLMs), particularly when dealing with complex tasks involving mathematics or reasoning. Despite the enormous empirical success, the underlying mechanisms behind CoT and how it unlocks the potential of LLMs remain elusive. In this paper, we take a first step towards theoretically answering these questions. Specifically, we examine the expressivity of LLMs with CoT in solving fundamental mathematical and decision-making problems. We start by giving an impossibility result showing that bounded-depth Transformers are unable to directly produce correct answers for basic arithmetic/equation tasks unless the model size grows super-polynomially with respect to the input length. In contrast, we then prove by construction that autoregressive Transformers of constant size suffice to solve both tasks by generating CoT derivations using a commonly-used math language format. Moreover, we show LLMs with CoT are capable of solving a general class of decision-making problems known as Dynamic Programming, thus justifying its power in tackling complex real-world tasks. Finally, extensive experiments on four tasks show that, while Transformers always fail to predict the answers directly, they can consistently learn to generate correct solutions step-by-step given sufficient CoT demonstrations.
Subfields: Artificial Intelligence
View Paper: https://www.semanticscholar.org/paper/c2260403fd5cb2de73491323433e48b6ec36872c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Tengyu Ma
- Vaishnavh Nagarajan
- Zhiyuan Li
- Aditya Krishna Menon
- Denny Zhou
- Sanjiv Kumar
- Ankit Singh Rawat
- Hong Liu
Citations in the corpus
- Think before you speak: Training Language Models With Pause Tokens (2023, background): “Feng et al. (2023); Merrill & Sabharwal (2023) theoretically argue that CoT aids by increasing the computational expressivity of the Trans-former.”
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (2024, background): “The success of CoT has even been extended to multi-modal QA (Zhang et al., 2023; Yang et al., 2023) and code generation (Chen et al., 2022; Gao et al., 2022).”
- 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).”