Barriers to Universal Reasoning With Transformers (And How to Overcome Them)

"Barriers to Universal Reasoning With Transformers (And How to Overcome Them)" 논문에 대한 상세한 기술적 요약은 다음과 같습니다.

1. 문제 제기

Chain-of-Thought (CoT) 프롬프팅은 경험적으로 Transformer 의 성능을 향상시켰으며, 이론적으로 그 표현력을 **튜링 완전성 (Turing Completeness)**까지 높일 수 있음이 입증되었으나, 중요한 격차가 여전히 존재합니다: Transformer 는 훈련 중에 본 것보다 더 긴 길이에 대해 CoT 추론을 일반화하여 학습할 수 있을까요?

기존의 경험적 증거는 CoT 추적 (trace) 길이가 증가함에 따라 알고리즘 및 논리 작업에서도 Transformer 의 정확도가 급격히 저하됨을 시사합니다. 본 논문은 **길이 일반화 가능한 학습 가능성 (length-generalizable learnability)**이라는 더 엄격한 요구 사항 하에서 튜링 완전성에 대한 이론적 주장이 유효한지 조사합니다. 구체적으로 다음과 같은 질문을 던집니다:

• 표준 CoT 형식은 Transformer 가 더 긴 시퀀스로 일반화할 때 $\text{TC}^0$(상수 깊이 임계 회로) 이상의 복잡도 클래스를 넘어선 문제를 해결할 수 있게 하는가?
• 이러한 일반화를 방해하는 구체적인 구조적 장벽은 무엇인가?
• 이러한 장벽을 특정 포맷팅 전략을 통해 극복할 수 있는가?

2. 방법론

저자들은 이론적 형식주의와 경험적 검증을 결합하여 접근합니다:

이론적 프레임워크

이 연구는 Transformer 길이 일반화에 대한 최근 이론적 프레임워크를 활용합니다:

• C-RASP: 유한 알파벳과 위치 인코딩을 가진 Transformer 에 대한 추론을 위한 형식주의. 소속 여부는 길이 일반화 보장을 의미합니다.
• C-RASP:* 무한 알파벳(구체적으로, 무제한의 지시 토큰)과 지역적 일치 술어를 허용하는 C-RASP 의 확장입니다.
• 학습 모델: 저자들은 증가하는 입력 길이에 대해 훈련된 Transformer 시퀀스가 단일 근본 알고리즘으로 수렴하는 이상화된 학습 모델을 채택합니다. 작업이 이러한 형식주의 내에서 표현될 수 있다면 일반화가 보장됩니다.

경험적 설정

• 작업: 세 가지 알고리즘적 추론 작업이 선정되었습니다:
  1. 패리티 (Parity): 이진 문자열에서 1 의 개수가 짝수인지 홀수인지 판별합니다.
  2. 부울 평가 (Boolean Evaluation): 중첩된 논리 공식의 진리값을 평가합니다.
  3. S5 순열 (S5 Permutation): 일련의 스왑 연산 후 5 개 객체의 상태를 추적합니다.
• 모델:
  • 처음부터 훈련 (From-Scratch): 특정 포맷팅 유무에 따라 CoT 추적에 대해 훈련된 GPT-2 모델 (25M 파라미터).
  • 미리 훈련된 LLM: Qwen2.5-7B, Mistral-Small-24B, Llama-3.3-70B 에 대한 제로샷 및 퓨샷 프롬프팅 실험.
• 포맷팅 변형:
  • Naive CoT: 표준 순차적 추론.
  • 지시 토큰 (Signpost Tokens): 임의의 주소 지정이 가능하도록 특정 위치나 연산에 고유 식별자 (예: <34>) 를 할당합니다.
  • 값 변경 인코딩 (Value-Change Encoding): 각 단계에서 전체 상태를 기록하는 대신, 모델은 값의 변화 (예: 1 -> 0) 만 기록하거나 값이 변경되지 않았음을 명시적으로 기록합니다.

3. 주요 기여 및 이론적 결과

기여 1: 유한 알파벳의 한계 (부정적 결과)

저자들은 표준 위치 인코딩과 유한 알파벳 하에서 CoT 를 사용하는 Transformer 가 $\text{TC}^0$ 밖의 문제를 해결하기 위해 길이 일반화를 할 수 없음을 증명합니다.

• 정리 3.4: 언어 $L$이 C-RASP(위치 원시 연산 포함) 로 표현 가능한 CoT 추적을 가진다면, $L$은 $\text{TC}^0$에서 정의 가능합니다.
• 함의: CoT 가 이론적으로 튜링 완전성을 허용하더라도, 어휘가 고정되어 있다면 그러한 시뮬레이션의 학습 가능성은 $\text{TC}^0$에 의해 제한됩니다. 표현력의 이점은 길이 일반화 가능한 학습 가능성으로 전환되지 않습니다.

기여 2: 무한 알파벳을 통한 장벽 극복 (긍정적 결과)

본 논문은 길이 일반화의 두 가지 핵심 장벽을 식별합니다:

1. 반복적 복사 (Repeated Copying): 임의의 문자열을 새로운 위치로 복사하는 어려움.
2. 최종 발생 검색 (Last-Occurrence Retrieval): 여러 번의 업데이트가 발생할 때 변수의 가장 최근 값을 검색하는 어려움 (비고유 검색).

이러한 장벽을 극복하기 위해 저자들은 C-RASP*를 사용한 구성을 제안합니다:

• 지시 토큰: 무한 알파벳에서 온 고유하고 무제한의 토큰을 테이프 위치나 연산 단계 각각에 할당합니다. 이는 절대적 정체성을 암기하지 않고 임의의 인덱싱을 허용함으로써 복사 장벽을 해결합니다.
• 값 변경 인코딩: 전체 상태를 기록하는 대신, CoT 는 *전이 (transitions)*만 기록합니다 (예: "값이 $x$에서 $y$로 변경됨"). 현재 상태는 초기 상태에 대한 순 변화량을 계산하여 복구됩니다. 이는 "최종" 발생을 검색하는 대신 현재 값을 개수의 함수로 만들어 검색 장벽을 해결합니다.
• 정리 3.8: CoT 를 사용하는 Transformer 가 지시 토큰의 무한 알파벳을 활용하고 값을 변경하여 계산을 인코딩한다면, 길이 일반화를 통해 임의의 튜링 머신을 시뮬레이션할 수 있습니다. CoT 추적 길이는 시뮬레이션 실행 시간에 선형적으로 유지됩니다.

4. 경험적 결과

처음부터 훈련 (From-Scratch Training)

• 패리티: 표준 CoT 는 훈련 길이 이상으로 일반화하지 못했습니다. 값 변경 인코딩은 훈련 길이의 $2$배까지 견고한 일반화를 가능하게 했습니다.
• 부울 평가 및 S5 순열: $\text{TC}^0$ 밖의 더 어려운 작업들은 Naive CoT 로는 실패했습니다. 지시 토큰을 추가하면 길이 일반화가 크게 개선되었으나, 모델이 활용할 수 있는 "단축키 (휴리스틱)"로 인해 S5 는 여전히 어려웠습니다.
• 이진 순열 (Binary Permutation): 높은 반복성을 가진 S5 의 변형. Naive 및 지시 토큰 전용 CoT 는 "비고유 검색" 오류로 인해 실패했습니다. 지시 토큰 + 값 변경을 결합한 것이 최상의 결과를 낳았으며, 이는 두 메커니즘의 이론적 필요성을 확인시켜 주었습니다.

미리 훈련된 LLM 프롬프팅

• 지시 토큰: 퓨샷 프롬프트에서 자연수를 지시 힌트로 사용하는 것은 모든 테스트된 LLM(7B~70B) 의 부울 및 S5 작업 성능을 향상시켰으며, 특히 더 긴 시퀀스 길이에서 두드러졌습니다.
• 값 변경: 코드 실행 작업 (변수 할당 추적) 에서, 중간 추론 단계 없이도 인라인 주석을 통해 값 변경을 명시적으로 기록 (예: # node a: 9 -> 0) 하는 것은 표준 코드 포맷팅보다 최종 답변의 정확도를 크게 향상시켰습니다.

5. 의의 및 결론

• CoT 성공의 재정의: 본 논문은 CoT 의 성공이 "사고" 과정 자체에 내재된 것이 아니라, 추적의 포맷팅에 크게 의존한다고 주장합니다. 표준 CoT 형식은 학습 가능성에 필요한 제약 (지역성 및 번역 불변성) 을 위반하기 때문에 종종 일반화에 실패합니다.
• 이론적 경계: Transformer 에 대한 튜링 완전성은 조건부임을 명확히 합니다. 이는 표현력(솔루션 하드 코딩) 에 대해서는 성립하지만, 특정 구조적 보조 (무한 알파벳/지시 토큰) 가 제공되지 않는 한 학습 가능성(일반화하도록 모델 훈련) 에 대해서는 성립하지 않습니다.
• 실무 지침: 이 연구 결과는 어려운 추론 작업에서 LLM 성능을 개선하기 위한 실행 가능한 원칙을 제시합니다:
  1. 인덱스 힌트 사용: 검색을 돕기 위해 위치나 단계를 고유 식별자로 명시적으로 표시합니다.
  2. 상태가 아닌 변경 사항 기록: 검색 모호성을 피하기 위해 전체 상태 덤프 대신 상태 전이를 강조하는 추론 추적 형식을 사용합니다.
• 향후 방향: 이 연구는 향후 사전 훈련 데이터와 CoT 방식이 이러한 이론적 제약을 고려하여 설계되어야 함을 시사하며, 이를 통해 장기적 추론 작업에서 Transformer 의 완전한 계산 잠재력을 해제할 수 있습니다.

요약하자면, 본 논문은 Transformer 가 이론적으로 보편적 추론이 가능함에도 불구하고, 이를 길이 일반화 가능한 방식으로 실현하려면 지시 토큰과 값 변경 인코딩을 사용하여 특정 아키텍처 및 포맷팅 장벽을 극복해야 함을 보여줍니다.