기술적 요약: 사고의 연쇄 (Chain of Thought) 와 잠재적 사고 (Latent Thought) 간의 형식적 비교

문제 제기

대규모 언어 모델 (LLM) 은 명시적으로 중간 토큰을 생성하여 추론을 유도하는 **사고의 연쇄 (Chain of Thought, CoT)**를 통해 향상된 추론 능력을 입증해 왔습니다. 반면, 잠재적 사고 (Latent Thought) 패러다임 (연속적 사고의 연쇄/Coconut 및 루프형 Transformer 등) 은 이산적 언어 토큰을 생성하지 않고 연속적인 은닉 상태 공간에서 직접 작동하며 반복적으로 계산합니다. 두 접근법 모두 표현력을 향상시키기 위해 반복 계산을 활용하지만, 그 능력 간의 근본적인 이론적 분리는 아직 충분히 탐구되지 않았습니다. 구체적으로, 잠재적 사고가 CoT 보다 보편적으로 더 높은 표현력을 갖는지, 아니면 특정 계산 영역에서 한 패러다임이 다른 패러다임보다 엄격하게 우월한 경우가 존재하는지는 명확하지 않습니다.

방법론

저자들은 CoT 와 잠재적 사고의 표현력을 비교하기 위해 형식적 복잡도 이론 분석을 수행합니다. 방법론은 다음과 같습니다:

1. 형식적 정의: 논문은 CoT, Coconut, 루프형 Transformer 를 Transformer 블록의 반복적 적용으로 정의합니다. CoT 는 자동회귀적으로 토큰을 생성하는 반면, 잠재적 사고 모델 (Coconut 및 루프형 TF) 은 은닉 상태를 임베딩으로 피드백하여 (Coconut) 또는 전체 시퀀스를 재계산하여 (루프형 TF) 은닉 상태를 반복적으로 업데이트합니다.
2. 계산 모델링:
   • 결정 문제: 추론은 부울 회로를 나타내는 방향성 비순환 그래프 (DAG) 의 평가로 형식화됩니다. 저자들은 이러한 문제를 해결하기 위해 추론 단계 수 (CoT 의 경우) 또는 반복 횟수 (잠재적 사고의 경우) 가 입력 크기 $n$에 따라 어떻게 확장되는지 분석합니다.
   • 복잡도 클래스: 이 연구는 이러한 모델을 표준 복잡도 클래스, 특히 다항 로그 깊이의 임계 회로 ($TC_k$) 및 근사 계수와 관련된 클래스 ($FPRAS$대$FPTAS$) 에 매핑합니다.
   • 확률적 설정: 분석은 CoT 가 중간 토큰을 샘플링하기 위해 확률적 디코딩을 사용하는 반면, 잠재적 사고는 잠재 공간에서의 결정론적 변환 하에 분석되는 확률적 모델로 확장됩니다.
3. 이론적 증명: 저자들은 각 패러다임에 대한 상한과 하한을 증명하는 논증을 구성합니다. 부울 회로로의 환원과 자기-환원 가능 관계의 속성을 활용하여 분리를 확립합니다.
4. 실증적 검증: 이론적 주장은 기본 알고리즘적 추론 작업 (단어 문제, 그래프 연결성, 산술 평가, 편집 거리) 및 근사 계수/샘플링 작업 (DNF 계수, 그래프 채색) 에서 검증됩니다.

주요 기여

1. 잠재적 사고는 효율적인 병렬 추론을 가능하게 함

논문은 병렬 계산이 필요한 문제에서 잠재적 사고가 CoT 보다 엄격하게 효율적임을 입증합니다.

• 병렬성: 잠재적 사고 모델은 DAG 의 평가를 층별로 시뮬레이션할 수 있습니다. 계산 그래프의 깊이가 $d$라면, 잠재적 사고 모델은 $O(d)$번의 반복으로 이를 해결할 수 있습니다.
• CoT 의 순차적 한계: 반면, CoT 는 자동회귀적 특성으로 인해 DAG 를 노드별로 시뮬레이션해야 하므로 $O(\text{size}(G))$ 단계가 필요합니다.
• 형식적 분리: 다항 로그 반복 ($O(\log^k n)$) 하에서 잠재적 사고 (Coconut 및 루프형 TF) 는 복잡도 클래스 $TC_k$의 능력을 정확히 포착합니다. 그러나 동일한 단계 수를 가진 CoT 는 엄격하게 $TC_{k-1}$ 내에서 제한됩니다. 이는 잠재적 사고가 본질적으로 순차적인 CoT 보다 더 효율적인 병렬 계산을 허용함을 증명합니다.

2. CoT 는 확률성을 통해 근사 계수를 가능하게 함

논문은 CoT 가 잠재적 사고보다 엄격하게 우월한 영역을 규명합니다: 근사 계수 및 샘플링.

• 확률적 디코딩: CoT 는 명시적으로 중간 추론 토큰을 샘플링합니다. 이러한 확률성은 CoT 가 완전히 다항 시간 확률적 근사 알고리즘 (FPRAS) 을 포함한 무작위 알고리즘을 모방할 수 있게 합니다.
• 결정론적 한계: 토큰 수준의 샘플링 없이 연속 공간에서 결정론적으로 작동하는 잠재적 사고는 결정론적 근사 알고리즘 (FPTAS) 으로 제한됩니다.
• 형식적 분리: 자기-환원 가능 관계에 대해 $FPTAS \subsetneq FPRAS$라고 가정할 때 (표준 복잡도 가정), 저자들은 CoT 가 잠재적 사고가 할 수 없는 계수 문제를 근사하고 목표 분포에서 샘플링할 수 있음을 증명합니다. 구체적으로, CoT 는 잠재적 사고가 근사하지 못하는 분포를 생성할 수 있어, CoT 를 지지하는 최초의 형식적 분리를 제공합니다.

3. 실증적 검증

실험은 이론적 분리를 확인합니다:

• 병렬 작업: 그래프 연결성 및 산술 평가와 같은 작업에서 루프형 Transformer 는 문제 크기에 비례하는 단계가 필요한 CoT 와 비교하여 입력 크기의 로그에 비례하는 훨씬 적은 반복으로 높은 정확도를 달성합니다.
• 계수/샘플링 작업: DNF 계수 및 그래프 채색 샘플링에서 CoT 는 루프형 Transformer 보다 균일한 목표 분포에 더 가까운 분포를 생성하는 능력 (더 낮은 총변동 거리) 을 보여주어, 확률적 근사에서의 우월한 능력을 검증합니다.

결과

• 표현력 분리: 표현력에는 엄격한 분리가 존재합니다. 잠재적 사고는 다항 로그 영역의 깊이 주도 병렬화 가능 문제 (예: 그래프 알고리즘, 산술 평가) 에 우수하며, CoT 는 확률적 근사 및 계수가 필요한 문제에 우수합니다.
• 반복 효율성: 잠재적 사고는 병렬 작업에서 $O(\log n)$번의 반복으로 CoT 와 비교 가능한 성능을 달성하는 반면, CoT 는 $O(n)$ 또는 $O(\text{size}(G))$ 단계가 필요합니다.
• 샘플링 능력: CoT 는 자기-환원 가능 계수 문제의 맥락에서 결정론적 잠재적 사고 모델이 접근할 수 없는 분포를 근사할 수 있습니다.

의의

이 논문은 작업의 성격에 따라 추론 패러다임을 선택하기 위한 엄격한 이론적 프레임워크를 제공합니다:

• 잠재적 추론은 병렬 계산을 통해 효율적으로 해결할 수 있는 문제 (예: 그래프 알고리즘, 산술 평가) 에 더 적합하며, 반복 효율성에서 상당한 이점을 제공합니다.
• **사고의 연쇄 (Chain of Thought)**는 토큰 생성의 확률성이 계산적 자산이 되는 무작위 근사, 계수, 또는 샘플링이 필요한 복잡한 문제에 여전히 더 효과적입니다.

저자들은 어느 패러다임도 보편적으로 우세하지 않으며, 오히려 그 강점은 병렬화 가능성과 확률성 간의 절충에 의해 결정되는 상호 보완적이라고 결론지었습니다. 이 작업은 모델 설계 및 작업 선택에 대한 실용적인 지침을 제공하며, 향후 아키텍처는 하이브리드 접근법이나 작업별 추론 메커니즘 선택의 이점을 얻을 수 있음을 시사합니다.