Chain-of-Thought (CoT) 추론은 대규모 언어 모델(LLMs)을 크게 향상시키지만, 그 분포 외(Out-of-Distribution, OOD) 일반화 메커니즘은 여전히 이론적으로 충분히 탐구되지 않은 영역입니다. 우리는 CoT를 구성적(compositional) OOD 일반화로 연구합니다: 목표 작업이 완전한 추론 궤적이나 직접적인 입력-출력 쌍을 갖지 못하는 반면, 학습 데이터는 오직 분포 내(In-distribution, ID)의 원자적 단계 데이터만을 제공합니다. 우리는 CoT가 공유된 단일 단계 예측기(shared single-step predictor)를 반복적으로 적용하여 재사용 가능한 ID 전이(transition)들을 구성함으로써 일반화됨을 보여줍니다.
이론적으로, $T$를 목표 작업의 추론 단계 수, $n$을 하위 작업당 학습 샘플 수, 그리고 $k$를 단계당 출력 토큰 수라고 할 때; OOD 작업 위험은 ID 하위 작업 위험의 합에 의해 제어되며, 이 합산된 위험 자체가 $T$에 따라 증가할 수 있음에도 불구하고 $ ext{O}(k)$ 차수의 계수로 스케일링됩니다. 이 계수는 $T$와 무관합니다. 또한 Rademacher-complexity 분석은 예측기 공유가 공유 클래스에 대한 균일한 용량 제어(uniform capacity control) 하에서 이루어지므로, 추정 항(estimation term)이 $T$에 대해 선형적이지 않고 $ ext{O}(\sqrt{T/n})$ 차수임을 추가로 보여줍니다. 자기회귀적 다음 토큰 예측(autoregressive Next-Token Prediction)의 경우, 최종 작업 위험은 동일한 $ ext{O}(k)$ 차수의 계수로 스케일링된 최고 성능 단계별 위험에 더하여 $\widetilde{\text{O}}\big(k\sqrt{T/n}\big)$ 차수의 추정 항으로 경계 지어집니다. 또한, 패리티 결합 구성(parity-coupled construction)은 하위 작업 경험적 위험 최소화기(sub-task empirical risk minimizer)의 경우, $T \le n$일 때 기대 최종 작업 위험이 최고 성능 위험보다 적어도 $\Omega(\sqrt{T/n})$ 이상임을 보여줍니다.
Atom-Task 및 GSM8K에 대한 실험은 이 이론을 뒷받침합니다: CoT는 단기에서 장기로의 일반화와 구성적 일반화를 가능하게 하며, 명시적인 상태 추적(explicit state tracking)이 필수적입니다. 우리의 코드는 https://github.com/maxliang114514/CoT-OOD 에서 이용 가능합니다.