기술 요약: 슬라이딩 윈도우 트랜스포머의 위치 인코딩 역할에 대한 재고

1. 문제 제기

위치 인코딩(Positional Encoding, PE)은 트랜스포머 아키텍처가 순서가 있는 시퀀스를 처리하기 위해 필수적인 구성 요소로 오랫동안 간주되어 왔습니다. 지배적인 직관은 명시적인 위치 정보가 없다면 셀프 어텐션 메커니즘이 순열 불변성(permutation-invariant)을 가지게 되어, 동일한 컨텍스트 토큰들의 서로 다른 순서를 구별할 수 없게 된다는 것입니다. 이러한 가정은 연쇄 사고(Chain-of-Thought, CoT) 추론을 통해 트랜스포머의 튜링 완전성(Turing completeness)을 입증한 기존의 이론적 결과들의 근간이 되었으며, 이들은 PE에 크게 의존하고 있습니다.

하지만 이러한 보편성 결과들은 대개 모델이 전체 이력을 참조한다는 것을 전제로 합니다. 실제의 긴 형태의 추론 시나리오에서 모델은 유한한 **슬라이딩 컨텍스트 윈도우(sliding context window)**를 가지고 작동합니다. 윈도우가 앞으로 슬라이딩함에 따라 토큰들이 들어오고 나가며, 이는 시간적 비대칭성을 도입합니다. 이 논문이 다루는 핵심 질문은 다음과 같습니다: 슬라이딩 윈도우 트랜스포머에서 보편적 계산을 달성하기 위해 위치 인코딩이 정말로 필요한가? 저자들은 슬라이딩 윈도우 메커니즘 자체가 명시적인 PE 없이도 보편적 계산을 달성하기에 충분한 순차적 구조를 제공하는지 조사합니다.

2. 방법론 및 프레임워크

HIST 모델

슬라이딩 윈도우로부터 파생되는 계산 능력을 격리하기 위해, 저자들은 HIST 모델이라는 추상적인 자기회귀(autoregressive) 모델을 도입합니다.

• 정의: HIST 머신은 유한한 제어 상태(control state)와 현재 윈도우의 토큰 카운트 히스토그램(알파벳에 의해 인덱싱된 토큰 빈도 벡터)만을 기반으로 다음 토큰을 생성합니다.
• 제약 사항: 이 모델은 윈도우 내 개별 토큰의 특정 위치에 접근할 수 없습니다. 즉, 모델의 전이 함수는 윈도우 내용에 대해 순열 불변적입니다.
• Parity-HIST 변형: 전이 함수가 히스토그램의 패리티(즉, 각 토큰 유형의 개수가 짝수인지 홀수인지 여부)에만 의존하는 제한된 버전입니다.

이론적 전략

튜링 완전성 증명은 두 가지 주요 단계로 진행됩니다:

1. 포스트 머신(Post Machines) 시뮬레이션: 저자들은 Parity-HIST 머신이 포스트 머신(큐 기반 자동기로, 튜링 완전한 것으로 알려짐)을 시사할 수 있음을 증명합니다.
   • 핵심 통찰: Parity-HIST 머신은 윈도우의 패리티만을 관찰하지만, 슬라이딩 윈도우의 FIFO(First-In-First-Out, 선입선출) 특성을 통해 윈도우에서 방금 빠져나간 토큰을 추론할 수 있습니다. 윈도우 업데이트 전후의 패리티 히스토그램을 비교함으로써(그리고 새로 들어온 토큰을 저장하기 위해 유한 제어 상태를 활용함으로써), 머신은 "드롭된" 앞쪽 토큰의 정체를 추론할 수 있습니다. 이는 명시적인 위치 주소 지정 없이도 큐의 디큐(dequeue) 연산을 효과적으로 시뮬레이션합니다.
2. 트랜스포머를 통한 Parity-HIST 시뮬레이션: 저자들은 PE가 없는 슬라이딩 윈도우 트랜스포머가 Parity-HIST 모델을 시뮬레이션할 수 있도록 구축합니다.
   • 메커니즘: 트랜스포머는 상수 크기의 토큰 알파벳과 적응형 업데이트 비트를 사용합니다. 어텐션 메커니즘으로부터 가공되지 않은 토큰 카운트(및 그 패리티)를 복구하기 위해, 이 구성은 특수한 **마커 심볼(#)**을 도입합니다.
   • 어텐션 역학: 균등 어텐션(Query와 Key 행렬을 0으로 설정하여 달성됨)을 사용하면 어텐션 가중치는 $1/m$ (여기서 $m$은 윈도우 크기)이 됩니다. 단일 마커의 존재를 통해 모델은 윈도우 크기 $m$을 추론하고 정규화된 어텐션 질량을 다시 가공되지 않은 정수 카운트로 변환할 수 있습니다.
   • 패리티 추출: 충분한 산술 정밀도(윈도우 크기에 대한 로그 스케일)를 갖추면, MLP 레이어는 토큰 카운트의 패리티를 계산하여 Parity-HIST 전이 함수를 효과적으로 복제합니다.

3. 주요 기여 및 결과

• 정리 1 (상위 수준): Parity-HIST 모델은 튜링 완전합니다. 저자들은 슬라이딩 윈도우의 시간적 진화가 순열 불변적 요약(히스토그램 패리티) 및 유한 상태와 결합될 때, 포스트 머신을 시뮬레이션하기에 충분하다는 것을 보여줍니다.
• 정리 2 (상위 수준): 모든 Parity-HIST 머신은 위치 인코딩이 없는 슬라이딩 윈도우 트랜스포머에 의해 시뮬레이션될 수 있습니다.
• 따름정리: 위치 인코딩이 없는 슬라이딩 윈도우 트랜스포머는 튜링 완전합니다.
• 구성 세부 사항:
  • 이 구성은 상수 크기의 어휘집과 상수 개의 학습 가능한 파라미터를 사용합니다.
  • 윈도우를 슬라이딩하거나(표준 방식), 가장 오래된 토큰을 유지하며 윈도우를 확장하는(확장 방식) 제어 비트를 토큰이 운반하는 적응형 윈도우 업데이트 메커즘을 채택하여, 최악의 경우의 윈도우 크기를 미리 지정할 필요가 없도록 합니다.
  • 시뮬레이션에는 패리티를 계산하기 위한 산술 연산으로서 로그 정밀도($O(\log S)$)가 필요하며, 여기서 $S$는 최대 윈도우 길이입니다.

4. 의의 및 주장

본 논문은 보편적 계산의 맥락에서 위치 인코딩과 순차적 구조의 개념을 근본적으로 분리한다고 주장합니다.

• PE는 필수적이지 않음: 이 결과는 트랜스포머가 보편적 계산을 수행하기 위해 명시적인 위치 인코딩이 반드시 전제 조건은 아님을 입증합니다. "FIFO와 유사한 움직임"인 슬라이딩 윈도우 자체가 순열 대칭성을 깨뜨리고 필요한 순차적 신호를 제공합니다.
• 보편성의 정교화: 이 연구는 보편적 계산을 위해 어떠한 형태의 순차적 구조는 필요하지만, 이 구조가 반드시 외부의 위치 주소 시스템에 의해 제공될 필요는 없다는 점을 명확히 합니다. 이는 생성 과정의 시간적 역학으로부터 자연스럽게 나타날 수 있습니다.
• 기존 연구와의 차별점: 회로 구조를 저장하거나 특정 토큰을 식별하기 위해 PE를 사용하는 이전의 보편성 증명들과 달리, 이 구성은 순열 불변적 윈도우 요약 모델을 통해 시뮬레이션을 수행합니다.
• 한계 및 범위:
  • 이 구성은 표현력에 관한 결과이지, 학습 가능성이나 실질적인 효율성에 대한 주장이 아닙니다. 이는 표준 트랜스포머가 이러한 알고리즘을 자연스럽게 학습할 것임을 의미하지 않습니다.
  • 이 모델은 윈도우 내의 정확한 토큰 위치를 복구하지 못하며, 단지 들어오고 나가는 토큰의 정체만을 추론합니다.
  • 이 구성은 패리티 계산을 위한 특정 패리티 프리미티브를 사용하며, 이는 환원(reduction)의 근본적인 아키텍처적 한계라기보다는 수치적 요구사항으로서 고립된 것입니다.

요약하자면, 본 논문은 슬라이딩 윈도우 메커니즘만으로도, 위치 인코딩이 없는 상황에서 토큰의 진입과 퇴출이라는 시간적 비대칭성을 활용하여 트랜스포머에게 보편적 계산 능력을 부여한다는 것을 입증합니다.