Chain of Thought Empowers Transformers to Solve Inherently Serial Problems

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.

한 줄 요약

CoT(Chain of Thought)를 통해 트랜스포머가 직렬 계산 문제를 해결할 수 있는 이론적 근거와 실증적 증거를 제시한다.

핵심 기여도

CoT가 트랜스포머의 표현력(Expressiveness)을 향상시켜 직렬 계산 문제를 해결할 수 있도록 한다는 이론적 분석.
상수 깊이 트랜스포머가 CoT 없이 $\mathsf{AC}^0$까지만 표현 가능하다는 새로운 상계(Theorem 3.1).
CoT 단계 수 $T$에 따라 트랜스포머가 최대 $\mathsf{P/poly}$까지 표현 가능하다는 증명(Theorem 3.3).
순열 그룹 합성, 반복 제곱, 회로 값 문제 등에서 CoT가 정확도를 크게 향상시킨다.

핵심 아이디어

기존 트랜스포머는 병렬 계산에 강하지만 직렬 계산 능력이 제한된다. CoT는 모델이 중간 단계를 생성하도록 유도하여 직렬 연산을 시뮬레이션할 수 있게 한다. 이는 트랜스포머가 $\mathsf{TC}^0$보다 낮은 $\mathsf{AC}^0$까지 표현 가능하다는 이론적 상계(Theorem 3.1)를 극복하는 핵심이다. CoT 단계 수 $T$가 증가함에 따라 트랜스포머는 $\mathsf{P/poly}$까지 표현 가능하다는 것이 증명된다(Theorem 3.3). 특히, $T$가 다항 크기일 때 트랜스포머는 다항 크기 회로를 표현할 수 있으며, 이는 기존 트랜스포머의 표현력 한계를 극복한다.

기술적 접근법

**모델**: 상수 깊이, 상수 비트 정밀도의 디코더-온리 트랜스포머.
**CoT 단계 수**: $T$개의 중간 토큰 생성 단계.
**임베딩 크기**: $O(\log n)$ 또는 $\mathsf{poly}(n)$.
**이론적 분석**: 회로 복잡도 이론을 활용한 표현력 분석.
**실험 대상 문제**: 순열 그룹 합성, 반복 제곱, 회로 값 문제, 모듈러 연산.
**결과 분석**: CoT 없이 해결 불가능한 문제에서 CoT가 정확도를 크게 향상시킴.

주요 결과

**순열 그룹 합성**: CoT 없이 해결 불가능하지만, CoT 단계가 추가되면 정확도가 크게 향상됨.
**반복 제곱**: CoT 없이 해결 불가능, CoT 단계 추가 시 정확도 73.2% 달성.
**회로 값 문제**: CoT 없이 해결 불가능, CoT 단계 추가 시 정확도 85.6% 달성.
**모듈러 연산**: CoT 없이도 해결 가능 (예: parity 문제, depth 1 트랜스포머로 98.7% 정확도).

의의 및 한계

**의의**: CoT가 트랜스포머의 직렬 계산 능력을 향상시키는 이론적 근거를 제공하며, 복잡한 추론 문제 해결에 기여.
**한계**: CoT 단계 수 $T$가 증가함에 따라 계산 비용이 증가하며, 실제 적용 시 효율성 문제가 발생할 수 있음. 또한, CoT 단계의 질에 따라 성능이 크게 달라질 수 있음.

실용적 활용

**수학 문제 풀이**: CoT를 통해 복잡한 수학 문제를 단계별로 해결하는 LLM 개발에 활용 가능.
**코드 생성**: 직렬적인 논리 흐름이 필요한 코드 생성 작업에서 CoT 기반 트랜스포머가 유용.
**복잡한 추론 시스템**: 회로 값 문제와 같은 복잡한 논리적 추론이 필요한 시스템에서 성능 향상에 기여.