Training Transformers as a Universal Computer

"Training Transformers as a Universal Computer" 논문에 대한 상세한 기술적 요약입니다.

1. 문제 제기

Chain-of-Thought(CoT) 가 보강된 Transformer 들이 계산적 보편성 (Turing 기계를 시뮬레이션할 수 있는 능력) 을 가진다는 이론적 연구가 있음에도 불구하고, 표현력 (이론적으로 무엇을 표현할 수 있는지) 과 학습 가능성 (경사 기반 최적화를 통해 실제로 무엇을 학습할 수 있는지) 사이에는 상당한 격차가 존재합니다.

현재의 주요 과제는 다음과 같습니다:

• 일반화 실패: 모델들은 길이 일반화 (예: 훈련 시 본 것보다 긴 숫자 더하기) 와 구성적 일반화 (기저 요소들의 새로운 조합 해결) 에서 어려움을 겪습니다.
• 컨텍스트 병목 현상: 표준 CoT 는 작업의 시간 복잡도 $T$에 비례하는 $O(T)$의 컨텍스트 길이를 요구합니다. 이로 인해 제한된 컨텍스트 윈도우 내에서 길고 복잡한 프로그램에 대한 훈련과 추론이 불가능해집니다.
• 보편적 학습의 부재: 이전의 신경 인터프리터 훈련 시도들은 종종 특정 사전 설계된 함수나 특수 아키텍처에 의존하여, 표준 Transformer 가 일반적이고 Turing 완전한 언어를 해석하도록 학습할 수 있음을 입증하지 못했습니다.

이 논문이 다루는 핵심 질문은 다음과 같습니다: 표준 Transformer 를 훈련시켜 보편적 컴퓨터로 작동하게 하고, 보지 못한 프로그램과 길이에 일반화시킬 수 있을까요?

2. 방법론

저자들은 새로운 프로그래밍 언어, 메모리 효율적인 실행 발판 (scaffold), 그리고 특정 훈련 체계를 결합한 프레임워크를 제안합니다.

A. MicroPy: 계산 가능한 보편적 언어

저자들은 간소화되었으나 Turing 완전한 객체 지향 프로그래밍 언어인 MicroPy를 설계했습니다.

• 의미론: 이는 검색 (retrieval) 과 재작성 (rewriting) 의 작은 유한 집합에 의존합니다.
  • 검색: 컨텍스트 (스택 프레임 또는 상태) 에서 함수 정의, 변수 바인딩, 또는 속성 값을 조회합니다.
  • 재작성: 현재 상태에 기반하여 (IF, SEQ, LookupAttr 와 같은) 원시 연산을 더 간단한 표현식으로 축소합니다.
• 구조: 프로그램은 절차 정의와 표현식으로 구성됩니다. 실행은 표현식의 단계별 축소, 가변 상태 (객체의 속성) 관리, 그리고 지역 변수를 위한 스택 프레임 관리를 포함합니다.
• 목표: 이러한 유한한 규칙을 학습함으로써, 모델은 어떤 MicroPy 프로그램이든 해석할 수 있게 되어, 사실상 보편적 인터프리터 역할을 수행합니다.

B. PENCIL 발판: 유한 컨텍스트 실행

컨텍스트 길이 병목 현상 ($O(T)$) 을 해결하기 위해, 저자들은 PENCIL(Yang et al., 2025) 을 활용합니다.

• 메커니즘: PENCIL 은 완료된 중간 계산을 회수하는 재작성 규칙을 도입합니다. 서브 계산 (스택 프레임) 이 완료되면, 중간 추론 단계는 지워지고 최종 결과만 유지됩니다.
• 복잡도: 이는 컨텍스트 길이를 시간 복잡도 $O(T)$ 대신 공간 복잡도 $O(S)$로 제한합니다.
• 유사성: 이는 프로그래밍 언어의 스택 규칙과 유사하게 작동합니다: 함수가 반환되면, 그 지역 스택 프레임이 팝되어 긴 실행 프로그램에서도 컨텍스트 윈도우 크기를 관리 가능하게 유지합니다.

C. 훈련 데이터 생성

모델은 무작위로 생성된 MicroPy 프로그램에서 생성된 실행 흔적 (traces) 으로 훈련됩니다.

• 두 가지 샘플러:
  1. 프로그램 수준 샘플러: 확률적 컨텍스트 자유 문법을 통해 다양한 구문 구조를 생성합니다.
  2. 계획 (Plan) 샘플러: 희귀한 런타임 구성 (특정 스택 뼈대와 검색 패턴) 을 커버하도록, 목표 "계획" (스택 구조) 을 샘플링하고 이를 실현하는 프로그램을 컴파일합니다.
• 지도 학습: 훈련 목표는 단계별 실행 흔적에 대한 다음 토큰 예측입니다. 모델은 현재 컨텍스트를 기반으로 다음 재작성 단계 (검색 또는 지역 축소) 를 예측합니다.
• 제약 조건: 훈련 프로그램은 모델에 과부하를 주지 않으면서 다양성을 보장하기 위해 128 줄의 흔적으로 제한되지만, 평가는 훨씬 더 긴 프로그램으로 수행됩니다.

D. 모델 아키텍처

• 아키텍처: RoPE(회전 위치 임베딩) 를 갖춘 디코더 전용 Transformer(5950 만 매개변수).
• 최적화: 임베딩에는 AdamW 를, 2D 행렬 매개변수에는 Muon 을 사용합니다.
• 입력: 절차 정의 + 평가할 표현식 + 현재 상태/스택.
• 출력: 실행 흔적의 다음 단계 (토큰 단위).

3. 주요 기여

1. MicroPy 언어 설계: 구성적 학습을 용이하게 하는 검색 및 재작성 규칙의 유한 집합에 기반한 의미론을 가진 Turing 완전 언어의 창조.
2. 보편적 학습의 경험적 증거: 보편적 언어의 무작위 흔적만으로 훈련된 표준 Transformer 가 보지 못한 복잡하고 인간이 작성한 프로그램을 실행할 수 있음을 최초로 입증.
3. PENCIL 통합: 고정된 컨텍스트 윈도우 내에서 훈련 시 본 것보다 60 배 더 긴 흔적 길이를 가진 프로그램을 실행할 수 있도록 PENCIL 발판을 성공적으로 적용.
4. 완벽한 일반화: 비트 조작, 산술, 논리 해결과 관련된 홀드아웃 (held-out) 작업에서 100% 정확도 달성으로 강력한 구성적 및 길이 일반화를 증명.

4. 실험 결과

모델은 훈련 데이터보다 훨씬 길고 의미적으로 풍부한 홀드아웃 인간 작성 MicroPy 프로그램으로 평가되었습니다.

• 평가된 작업:
  • 비트 조작: 연결 리스트에서 비트 복사 및 반전.
  • 산술: 비트 문자열 표현을 사용한 이진 덧셈 및 곱셈.
  • 논리: SAT 검증 및 SAT 해결 (백트래킹 검색 사용).
• 성능:
  • 정확도: 모델은 테스트된 컨텍스트 윈도우 내 모든 작업에서 100% 토큰 수준 정확도를 달성했습니다.
  • 길이 일반화: 모델은 128 줄로 제한된 프로그램으로 훈련되었음에도 불구하고, 7,552 줄까지의 흔적 길이를 가진 프로그램을 성공적으로 실행했습니다.
  • 분포 격차: 훈련 프로그램 분포와 테스트 스위트 간에 거의 겹침이 없어, 모델이 특정 프로그램을 암기하는 것이 아니라 실행 규칙을 학습했음을 확인했습니다.
• 연산 커버리지: 훈련 생성기는 테스트 스위트에서 사용된 모든 연산 유형 (예: If, LookupVar, TailApp) 을 커버하여, 모델이 훈련 중 모든 필요한 원시 연산을 보도록 보장했습니다.

5. 중요성 및 함의

• 보편적 계산의 학습 가능성: 이 논문은 계산적 보편성이 Transformer 의 이론적 속성일 뿐만 아니라, 적합한 언어에 대한 표준 다음 토큰 예측 훈련을 통해 획득할 수 있는 능력임을 강력하게 입증합니다.
• 구성성을 위한 귀납적 편향: 결과는 컨텍스트 관리 발판 (PENCIL 과 같은) 과 결합된 Transformer 가 구문 구조와 구성적 의미론에 잘 맞는 귀납적 편향을 가지고 있음을 시사합니다. 이는 프로그래밍 언어와 자연 언어의 구조 모두를 반영합니다.
• 격차 해소: 이 연구는 I/O 흔적을 학습하는 "신경 컴퓨터"와 형식 인터프리터 사이의 격차를 해소하여, 단일 모델이 형식적이고 Turing 완전한 언어를 실행하도록 학습할 수 있음을 보여줍니다.
• 향후 방향: 저자들은 프로그래밍 언어 인터프리터 학습을 가능하게 하는 동일한 메커니즘이 구성적 의미론에 의존한다는 점에서 Transformer 가 자연어 작업에서 매우 효과적인 이유를 설명할 수 있다고 제안합니다. 향후 연구는 명시적 실행 흔적 없이 더 풍부한 언어와 추론으로 확장될 수 있습니다.

요약하자면, 이 논문은 실행이 컨텍스트를 효율적으로 관리하도록 발판이 제공된다면, 표준 Transformer 를 훈련시켜 Turing 완전 언어의 임의 프로그램을 완벽하게 실행할 수 있는 보편적 컴퓨터로 기능하게 할 수 있음을 보여줍니다.