Transformer가 Chain-of-Thought를 내재화하는 방식에 대한 이론적 증명

Chain-of-Thought (CoT) 프롬프팅은 Transformer의 샘플 효율성 (sample efficiency)을 실질적으로 개선하여, 패리티 학습 (parity learning)과 같은 작업의 복잡도를 입력 길이에 따라 지수 함수적 (exponential) 수준에서 다항식 (polynomial) 수준으로 감소시킵니다. 그러나 추론 (inference) 시 명시적인 추론 단계 (reasoning steps)를 생성하는 것은 계산 비용이 많이 듭니다. 암시적 Chain-of-Thought (Implicit Chain-of-Thought, ICoT)는 모델이 중간 단계들을 은닉 상태 (hidden states) 내에 내재화하도록 학습시키는 유망한 경험적 해결책으로 등장했으나, 그 이론적 토대는 여전히 잘 이해되지 않은 상태로 남아 있습니다. 본 논문에서는 ICoT에 대한 최초의 이론적 분석을 제공하며, 우리가 제안한 Log-ICoT 커리큘럼 (curriculum) 하에 학습된 $L$-레이어 (layer) Transformer가 $ ext{poly}(n)$개의 샘플과 $L = ext{log}_2 k$개의 학습 단계 (training stages)를 통해 $k$-패리티 (k-parity)를 학습함을 증명합니다. 이는 명시적 CoT의 샘플 효율성을 유지하면서도 추론 오버헤드 (inference overhead)를 제거하며, 기존의 단일 레이어 패리티 보장 (one-layer parity guarantees)을 다중 레이어 아키텍처 (multi-layer architectures)로 확장합니다. 사고 토큰 (thinking tokens)을 하나씩 제거하는 표준 ICoT와 비교하여, Log-ICoT는 이를 기하급수적인 덩어리 (geometric chunks) 단위로 제거함으로써 단계의 수를 $k$에 대한 선형 (linear) 관계에서 로그 (logarithmic) 관계로 줄입니다. 다중 레이어 Transformer에 대한 실험은 이론을 확인해주며, 추론 (reasoning)이 어떻게 점진적으로 더 깊은 레이어로 흡수되는지를 시각화하여 보여줍니다.