트랜스포머를 통한 범용 추론의 장벽 (그리고 이를 극복하는 방법)

요약

본 논문은 트랜스포머 모델의 추론 능력 향상에 사용되는 Chain-of-Thought (CoT) 기법의 한계를 이론적으로 분석합니다. 표준적인 위치 인코딩과 유한 알파벳 하에서는 CoT를 통한 표현력 증가가 $TC^0$ 이상의 문제를 해결할 수 없음을 증명했습니다. 그러나 어휘 확장을 허용하고 '마커 토큰' 및 '값 변화 인코딩' 같은 새로운 메커니즘을 도입함으로써, 트랜스포머는 반복 복사나 마지막 위치 검색과 같은 길이 일반화의 핵심 장애물을 극복하고 튜링 머신의 길이 일반화 가능한 시뮬레이션을 달성할 수 있음을 제시합니다.

핵심 포인트

• CoT(Chain-of-Thought)가 트랜스포머의 성능을 높이지만, 표준적인 설정에서는 $TC^0$ 이상의 문제 해결에 한계가 있다.
• 표준 위치 인코딩과 유한 알파벳 하에서 CoT를 사용해도 '길이 일반화 가능한 학습 가능성'은 표현력 향상을 보장하지 않는다.
• 어휘 확장을 허용하고 '마커 토큰(signpost token)' 및 '값 변화 기록'을 도입하여 길이 일반화의 두 가지 핵심 장애물(반복 복사, 마지막 위치 검색)을 극복할 수 있다.
• 제안된 방법론은 트랜스포머가 튜링 머신의 길이 일반화 가능한 시뮬레이션을 달성할 수 있는 실질적인 지침을 제공한다.