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

Chain-of-Thought (CoT) 는 경험적으로 트랜스포머의 성능을 향상시키고, 이론적으로는 튜링 완전성까지 표현력을 높인다는 것이 입증되었습니다. 그러나 트랜스포머가 학습 중에는 보지 못한 더 긴 CoT 트레이스를 일반화하여 학습할 수 있는지에 대해서는 연구가 부족합니다. 우리는 최근의 트랜스포머 길이 일반화를 위한 이론적 프레임워크를 활용하여, 표준적인 위치 인코딩 (positional encodings) 과 유한 알파벳 (finite alphabet) 하에서는 CoT 를 사용하는 트랜스포머가 $TC^0$ 을 넘어선 문제를 해결할 수 없음을 발견했습니다. 즉, 더 엄격한 요구 사항인 '길이 일반화 가능한 학습 가능성 (length-generalizable learnability)' 하에서는 표현력 향상의 이점이 성립하지 않습니다. 반면, 어휘 (vocabulary) 를 문제 크기에 따라 확장하도록 허용하면, CoT 트레이스 길이가 시뮬레이션된 실행 시간 상수배에 선형적으로 비례하는 튜링 머신의 길이 일반화 가능한 시뮬레이션을 달성할 수 있습니다. 우리의 구성은 신뢰할 수 있는 길이 일반화의 두 가지 핵심 장애물인 반복 복사 (repeated copying) 와 마지막 발생 위치 검색 (last-occurrence retrieval) 을 극복합니다. 우리는 테이프의 각 위치마다 고유한 마커 토큰 (signpost token) 을 할당하고, 값의 변화만 기록함으로써 카운트를 통해 현재 테이프 심볼을 복원하여 두 장벽을 우회합니다. 또한, 우리는 이러한 마커 퀅과 값 변화 인코딩이 어려운 문제에서 길이 일반화를 개선하는 데 실행 가능한 지침을 제공함을 경험적으로 보여줍니다.