논문 요약: Attention 의 범용 시뮬레이터 존재성 (ON THE EXISTENCE OF UNIVERSAL SIMULATORS OF ATTENTION)

이 논문은 트랜스포머 (Transformer) 아키텍처가 학습 (Learnability) 을 통해 특정 알고리즘 패턴을 근사하는 능력을 넘어, 이론적으로 임의의 어텐션 (Attention) 메커니즘을 결정론적으로 시뮬레이션할 수 있는지를 탐구합니다. 저자들은 데이터에 의존하지 않는 알고리즘적 구성을 통해 단일 레이어 트랜스포머 인코더가 범용 시뮬레이터 (Universal Simulator, $U$) 로서 작동할 수 있음을 증명합니다.

1. 문제 제기 (Problem Statement)

• 배경: 기존 트랜스포머 연구는 주로 학습을 통한 특정 알고리즘 패턴의 근사 가능성 (확률적 보장) 에 집중했습니다. 반면, 표현력 (Expressivity) 연구는 이론적으로 계산 가능한 문제들을 다루며 트랜스포머의 튜링 완전성 등을 증명했습니다.
• 핵심 질문: 학습된 트랜스포머가 아닌, 트랜스포머 자체를 계산 모델로 볼 때, 임의의 어텐션 메커니즘 (특히 단일 레이어 멀티헤드 소프트맥스 어텐션, SMAT) 을 다른 트랜스포머 인코더들의 상호작용만으로 시뮬레이션할 수 있는가?
• 목표: 특정 작업 (Task) 에 맞춰 설계된 어텐션 (예: Match2, k-PARITY) 을 학습에 의존하지 않고, 범용 시뮬레이터 $U$를 통해 정확하게 (deterministically) 재현하는 알고리즘적 해법을 제시하는 것.

2. 방법론 (Methodology)

저자들은 RASP (Restricted Access Sequence Processing) 라는 형식적 프레임워크를 사용하여 트랜스포머의 계산을 모델링하고, 이를 기반으로 다음과 같은 구성을 제안합니다.

• 범용 시뮬레이터 $U$ 구성:
  • 입력으로 어텐션 메커니즘을 정의하는 행렬 $A$ (Query-Key 결합), $V$ (Value) 와 입력 시퀀스 $X$를 받습니다.
  • $U$는 트랜스포머 인코더 레이어들만으로 구성되어 $T(X)$와 동일한 출력을 생성합니다.
• 핵심 연산의 알고리즘적 구현 (RASP 기반):
  트랜스포머가 행렬 연산과 활성화 함수를 수행할 수 있음을 보이기 위해 다음과 같은 보조 정리 (Lemma) 들을 증명합니다.
  1. 행렬 전치 (Transpose): 행렬의 행과 열을 뒤집는 연산을 어텐션 점수 행렬의 치환을 통해 구현 (Lemma 3).
  2. 소프트맥스 (Softmax): 행렬의 각 행에 대해 소프트맥스 함수를 적용하는 연산을 구현 (Lemma 4).
  3. 행렬 곱셈 (Multiplication): 두 행렬의 곱을 계산하는 연산을 구현. 이는 $A$와 $B$의 특정 행/열을 선택하여 요소별 곱을 수행하고 집계하는 방식으로 이루어짐 (Lemma 5).
  4. 활성화 함수: ReLU, MaxMin, Softmax 등 다양한 활성화 함수를 트랜스포머로 정확히 표현 가능함을 보임 (Lemma 7 등).
• 구현 방식:
  • 평균 하드 어텐션 (Average Hard Attention, AHAT): 소프트맥스 기반의 부드러운 어텐션을, RASP 의 select 및 aggregate 연산을 통해 구현된 평균 하드 어텐션으로 정확히 모사합니다.
  • 입력 의존성: 시뮬레이터 $U$의 깊이 (Depth) 는 입력과 무관하게 일정하지만, 너비 (Width, 어텐션 헤드 수) 는 입력 시퀀스 길이 $n$에 비례하여 확장됩니다.

3. 주요 기여 (Key Contributions)

1. 범용 시뮬레이터 $U$의 존재 증명: 단일 레이어 트랜스포머 인코더 (멀티헤드 포함) 를 다른 트랜스포머 네트워크로 정확히 시뮬레이션할 수 있는 알고리즘적 구성을 최초로 제시했습니다.
2. 데이터 무관한 결정론적 해법: 기존 연구가 학습을 통한 확률적 근사에 의존했던 것과 달리, 이 연구는 수학적 구성을 통해 오차 없이 (deterministically) 어텐션 동작을 재현하는 방법을 제공합니다.
3. 행렬 연산 및 활성화 함수의 트랜스포머 내 구현: 전치, 곱셈, 역행렬 (3x3), 소프트맥스, MaxMin 등 선형 대수 및 비선형 연산을 트랜스포머의 기본 연산 (어텐션, FFN) 만으로 구성 가능함을 증명했습니다.
4. 표현력의 확장 (Lipschitz 연속 함수): MaxMin 연산의 구현을 통해 트랜스포머가 Lipschitz 연속 함수 및 Hölder-smooth 함수의 범용 근사기임을 새로운 방식으로 증명했습니다.
5. RASP 구현 코드 제공: 모든 알고리즘적 구성에 대한 RASP 코드를 공개하여 재현성을 보장했습니다.

4. 결과 (Results)

• 정확한 시뮬레이션: 제안된 네트워크 $U$는 입력 $\langle T, X \rangle$를 받아 원래 트랜스포머 $T$가 $X$에 대해 생성하는 출력 $T(X)$와 수치적으로 동일한 결과를 생성합니다 (NumPy 구현과의 비교 실험에서 오차가 거의 0 에 수렴함을 확인).
• 복잡한 언어 인식 가능: 기존에 단일 레이어 SMAT 로만 학습 가능한 것으로 알려진 문제들 (예: Match2, k-PARITY) 을 제안된 범용 시뮬레이터를 통해 정확히 해결할 수 있음을 보였습니다.
• 계층적 표현력: 입력 시퀀스 길이 $n$이 더 큰 시뮬레이터 $U(n)$은 더 작은 $n$을 가진 시뮬레이터 $U(m)$을 포함하는 계층적 구조를 가집니다. 즉, 충분히 큰 $N$에 대해 $U(N)$은 임의의 단일 레이어 어텐션을 시뮬레이션할 수 있는 범용 기계가 됩니다.
• 멀티헤드 확장: 단일 헤드 시뮬레이션 결과를 바탕으로 멀티헤드 어텐션 (Theorem 9) 및 전체 트랜스포머 인코더 (Corollary 9.1) 로의 확장을 증명했습니다.

5. 의의 및 중요성 (Significance)

• 학습과 표현력의 간극 해소: 트랜스포머의 표현력이 단순히 "학습을 통해 근사 가능하다"는 것을 넘어, "이론적으로 정확히 계산 가능하다"는 것을 보여줌으로써 학습 이론과 계산 이론 사이의 간극을 메웠습니다.
• 형식적 검증 (Formal Verification) 가능성: 근사 오차가 허용되지 않는 엄격한 환경 (예: 형식적 검증, 안전 임계 시스템) 에서 트랜스포머의 동작을 알고리즘적으로 보장할 수 있는 기반을 마련했습니다.
• 새로운 계산 모델로서의 트랜스포머: 트랜스포머가 단순한 패턴 인식기를 넘어, 임의의 계산 모델 (특히 어텐션 메커니즘 자체) 을 시뮬레이션할 수 있는 범용 계산 장치임을 이론적으로 입증했습니다.
• 실용적 함의: Tracr, ALTA 와 같은 RASP 컴파일러를 통해 제안된 가중치를 실제 트랜스포머 모델로 변환하고, 이를 학습 데이터 없이도 정확한 계산을 수행하는 모델로 활용하는 길을 열었습니다.

결론적으로, 이 논문은 트랜스포머 아키텍처가 학습에 의존하지 않고도 임의의 어텐션 메커니즘을 결정론적으로 시뮬레이션할 수 있는 범용 시뮬레이터의 존재를 수학적으로 증명하고 구체적인 구성 방법을 제시함으로써, 트랜스포머의 이론적 한계와 가능성을 재정의했습니다.