기술적 요약: Preisach 어텐션: 순차적 기억을 위한 히스테리시스 모델

문제 제기

현재 지배적인 시퀀스 모델링 아키텍처, 특히 트랜스포머 (Transformer) 는 시간적 (거리가 멀어질수록 감쇠) 이거나 위치적 (토큰 위치에 인덱싱됨) 인 어텐션 메커니즘에 의존합니다. 이론적 분석은 하드 어텐션 (hard-attention) 트랜스포머의 튜링 완전성을 입증했지만, 이를 달성하려면 $O(\log n)$ 깊이가 필요하며, 표준 소프트맥스 어텐션은 1 차 논리의 제한된 부분집합에 해당합니다. 트랜스포머, 순환 신경망 (RNN), 상태 공간 모델 (SSM) 이 공유하는 치명적인 한계는 과거 입력의 빈도나 절대적 위치가 아닌 **중요성 (significance)**에 기반한 기억 메커니즘이 부재하다는 점입니다. 입력 히스토리의 국소 극값 (local extrema) 순서에 의존하여 시간 간격과 무관하게 출력이 결정되는 장기간의 에피소드 기억을 유지할 수 있는 아키텍처가 필요합니다.

방법론

본 논문은 수리물리학의 고전적인 Preisach 히스테리시스 연산자를 기반으로 한 새로운 시퀀스 모델링 아키텍처인 **Preisach 어텐션 레이어 (PAL)**를 소개합니다.

핵심 메커니즘: Preisach 연산자

Preisach 연산자는 활성화 임계값 $\alpha$와 비활성화 임계값 $\beta$로 특징지어지는 이진 릴레이 $\hat{\gamma}_{\alpha\beta}$들의 출력을 집계합니다. 시퀀스 모델링의 맥락에서:

1. 이진 릴레이: 입력 시퀀스 $u$에 대해, 릴레이 상태는 $u_n \geq \alpha$이면 1 로, $u_n \leq \beta$이면 0 으로 전환됩니다. 그 외의 경우 이전 상태를 유지합니다.
2. 극값 스택 (Extremum Stack): "지우기 성질 (wiping property)"의 근본적인 결과로, 연산자의 출력은 현재 극값 스택($\Pi_n$)에만 의존합니다. 이 스택은 교번하는 국소 최댓값과 최솟값을 저장합니다. 새로운 극값은 그보다 작은 크기의 모든 이전 극값을 지워, 자연스럽고 중요성 기반의 망각 메커니즘을 제공합니다.
3. 속도 무관성 (Rate-Independence): 출력은 토큰의 절대 시간이나 위치에 의존하지 않고 국소 극값의 순서에만 의존합니다.

아키텍처 정의

• PAL 레이어: 이 레이어는 임계값 평면 $(\alpha, \beta)$상의 이산화된 측도 $\mu$에 대해 이진 릴레이 출력들의 가중 합을 계산합니다.
• 멀티헤드 PAL (MPAL): 입력을 스칼라 신호로 투영하고 여러 헤드를 통해 처리한 후 다시 투영함으로써, 스칼라 PAL 을 벡터 값 시퀀스로 확장합니다.
• PAL-트랜스포머: 표준 어텐션 메커니즘이 MPAL 로 대체된 표준 트랜스포머 인코더 - 디코더 구조입니다. 이는 정현파 위치 인코딩 (PE) 과 MLP 레이어를 유지하지만, 핵심 기억 메커니즘은 히스테리시스적입니다.

주요 기여 및 결과

1. $O(1)$ 깊이에서의 튜링 완전성

본 논문은 단일 레이어 PAL-트랜스포머가 **튜링 완전 (Turing-complete)**임을 증명합니다.

• 메커니즘: 이 아키텍처는 튜링 머신과 동등한 임의의 2-스택 푸시다운 오토마타 (2-PDA) 를 시뮬레이션합니다.
• 인코딩: 알파벳 기호와 스택 깊이는 "칸토어 깊이 인코딩 (Cantor-depth encoding)"을 사용하여 극값 스택에 인코딩됩니다.
• 깊이 이점: 이 시뮬레이션은 $O(1)$ 깊이 (하나의 MPAL 레이어와 하나의 MLP 레이어) 로 달성됩니다. 이는 튜링 완전성을 달성하기 위해 $O(\log n)$ 깊이가 필요한 표준 하드 어텐션 트랜스포머 (Pérez 등, 2021) 와 대조됩니다.
• 벡터 PAL (vPAL): 2 차원 신호 투영을 사용하는 변형은 단일 헤드로 ($H=1$) 튜링 완전성을 달성하여, PAL 에서 신호 차원과 헤드의 수가 교환 가능한 자원임을 보여줍니다.

2. 표현력 분리

본 논문은 PAL 과 트랜스포머가 계산 가능한 함수 클래스가 **비교 불가능 (incomparable)**함을 확립합니다.

• PAL $\setminus$ 트랜스포머: PAL 은 $O(1)$ 레이어로 역사적 범위 통계 (예: $max(u) - min(u)$) 를 계산할 수 있습니다. 반면, 유한 깊이의 표준 트랜스포머는 회로 복잡도 하한 (MAX 는 $AC^0$에 속하지 않음) 으로 인해 이를 정확히 계산할 수 없습니다.
• 트랜스포머 $\setminus$ PAL: 트랜스포머는 정확한 랜덤 액세스 검색 (예: 위치 $p$의 토큰 검색) 을 수행할 수 있습니다. PAL 은 속도 무관성 속성으로 인해 국소 극값이 아닌 토큰의 값이 스택의 영향에서 "지워지므로", 보조 상태 없이는 위치 기반 검색이 불가능합니다.
• 분리 속성: 속도 무관성은 두 클래스를 구분하는 근본적인 속성으로 식별됩니다. PAL 출력은 입력 시퀀스의 시간 재확장에 불변인 반면, 표준 어텐션은 그렇지 않습니다.

3. 논리적 특성화

본 논문은 국소 극값 위치로만 양화 (quantification) 를 허용하고 극값 집계 연산자를 포함하는 1 차 논리의 확장인 **극값 1 차 논리 (Extremum First-Order Logic, EFO)**를 정의합니다.

• 정리: 유한 깊이의 PAL-트랜스포머가 계산 가능한 함수는 EFO 에서 정의 가능한 함수와 동치입니다.
• 함의: EFO 는 표준 트랜스포머에 해당하는 논리 (FO + 집계) 의 엄격한 부분집합이므로, PAL 은 임의의 위치 논리를 표현할 수는 없지만 극값 기반 집계에는 뛰어남을 확인합니다.

4. 물리학 및 복잡성과의 연결

• RFIM 동등성: 본 논문은 PAL 이 $T=0$에서의 **랜덤 필드 이징 모델 (RFIM)**의 학습된 순차적 비평형 일반화임을 보여줍니다. 극값 스택은 RFIM 히스토리의 최소 충분 통계량에 해당합니다.
• 복잡성: PAL 추론은 총 시간 복잡도가 $O(n \log n)$ (스택 업데이트 및 이진 검색으로 인해) 이고 메모리는 $O(kd)$인 반면, 표준 어텐션은$O(n^2)$입니다.
• 상전이: RFIM 이론에서 영감을 받아, PAL 레이어가 임계 무질서 강도 근처에서 작동할 때 "혼돈의 가장자리 (edge of chaos)" 행동을 보이며 입력 변화에 대한 민감도를 극대화하면서도 구조화된 기억을 유지할 수 있음을 시사합니다.

중요성 및 주장

본 논문은 PAL 이 빈도 기반 또는 위치 기반 기억에서 중요성 기반 기억으로 전환하는 시퀀스 모델링을 위한 근본적으로 다른 기억 메커니즘을 제공한다고 주장합니다.

• 이론적 발전: 기존 아키텍처와 비교 불가능한 시퀀스 모델 공간의 새로운 지점을 제공하며, $O(1)$ 깊이 튜링 완전성과 고유한 논리적 특성화 (EFO) 를 제공합니다.
• 효율성: 극값 스택에 의존함으로써 PAL 은 추론 복잡도를 2 차에서 준선형 ($O(n \log n)$) 으로 줄여, 장기간 에피소드 기억이 필요한 작업에 이론적으로 적합하게 만듭니다.
• 작업 적합성: 저자들은 PAL 이 속도 무관성이며 역사적 범위 통계에 의존하는 작업에서 표준 어텐션보다 우수한 성능을 발휘할 것으로 예측합니다. 예를 들어:
  • 긴 문서에 걸쳐 엔티티 상태 추적.
  • 역사적 범위에 기반한 시계열 이상 감지.
  • 위치 민감도 없이 순차적 사건에 대한 추론.
  • 의사결정 임계값이 행동을 주도하는 에너지 시장 배분.

본 논문은 PAL 이 랜덤 액세스를 수행할 수는 없지만, 모든 속도 무관 함수에 대해 입력 히스토리의 최소 충분 통계량을 유지할 수 있는 능력은 과거 사건의 중요성이 빈도나 절대적 위치보다 중요한 문제들에 자연스러운 아키텍처임을 결론짓습니다. 이 연구는 이론적이며, 경험적 검증과 학습 역학 (특히 임계성과 관련하여) 은 향후 연구의 열린 과제로 남아 있습니다.