기술 요약: 언제 도구 사용이 유한 정밀도 순환 모델의 표현력을 증가시키는가?

문제 정의

현대적인 시퀀스 모델들은 토큰 생성과 외부 도구 호출(예: 계산기, 코드 인터프리터, 검색 시스템)을 교차하며 수행하는 에이전트로 점점 더 많이 배치되고 있습니다. 경험적인 성공은 분명하지만, 근본적인 이론적 질문은 여전히 해결되지 않은 상태로 남아 있습니다: 어떤 특정 도구가 고정된 유한 정밀도 순환 모델의 계산 표현력을 증가시키며, 얼마나 많이 증가시키고, 그에 따른 내부 메모리 비용은 얼마인가?

기존 문헌은 고정된 유한 정밀도 순환 모델(상태 공간 모델(SSM) 포함)이 유한 상태 기계(FSM)와 동등하며 정규 언어(regular languages)만을 인식한다는 점을 확립했습니다. 생각의 사슬(Chain-of-thought) 디코딩은 생성되는 단계 수에 의해 제한되는 제한적인 이득만을 제공합니다. 본 논문은 외부 도구 접근이 이러한 계산 지형을 어떻게 변화시키는지에 대해, 단순히 유한한 메모리를 추가하는 도구와 계산 능력을 근본적으로 확장하는 도구를 구분하여, 아키텍처 수준의 정확한 특성을 규명하고자 합니다.

방법론

저자들은 시퀀스 모델을 오라클(oracle)과 유한한 명령/관측 인터페이스를 통해 상호작용하는 **결정적 유한 상태 컨트롤러(deterministic finite-state controller)**로 추상화합니다.

• 컨트롤러 모델: $B$ 비트의 내부 상태를 가진 컨트롤러는 최대 $2^B$개의 구성(configurations)을 가진 FSM으로 모델링됩니다. 이는 입력을 읽은 후, 토큰을 방출하거나, 도구 명령을 발행하거나, 관측값을 받거나, 혹은 종료하는 생성 단계를 거칩니다.
• 도구 인터페이스: 논문은 두 가지 뚜렷한 클래스의 도구를 분석합니다:
  1. 유한 상태 유한 인터페이스 오라클: 유한한 메모리 집합과 유한한 명령/관측 알파벳을 가진 도구.
  2. 무한 테이프 오라클: 무한한 테이프 상에서 국소적 읽기/쓰기/이동 작업을 지원하는 최소한의 무한 상태 도구(튜링 머신의 테이프와 유사).
• 실현(Realization): 이론적 구성은 **유한 정밀도 선택적 아핀 SSM(selective affine SSMs)**으로 매핑됩니다. 저자들은 모든 관측 기반 유한 상태 컨트롤러가 이진 원-핫(one-hot) 숨겨진 상태, $\{0, 1\}$ 전이 행렬, 그리고 제로 바이어스를 가진 1층 SSM에 의해 정확하게 실현될 수 있음을 증명합니다. 단, 이때 전이 행렬은 선택적(현재 관측 토큰에 의존적)이어야 합니다.

주요 기여 및 결과

1. 유한 상태 도구는 (거의) 아무것도 더하지 못한다

논문은 "곱집합 상태 시뮬레이션(product-state simulation)" 정리를 확립합니다. 만약 도구가 그 자체로 메모리 집합 $M$과 유한한 인터페이스를 가진 유한 상태 기계라면, 컨트롤러는 도구의 상태를 내부화할 수 있습니다.

• 결과: 증강된 시스템은 여전히 유한 상태 기계입니다. 내부 메모리 비용은 오직 $\log_2 |M| + O(1)$ 비트만큼만 증가합니다.
• 시사점: 유한 상태 도구는 정규 언어 이상의 언어 클래스를 인식하는 능력을 높이지 못합니다. 인터페이스의 유한한 성격이 필수적인데, 그렇지 않으면 임의의 초기화나 명령-관측 맵이 비정규 동작을 인코딩할 수 있기 때문입니다.

2. 하나의 최소 무한 도구가 튜링 완전성을 제공한다

저자들은 국소적 읽기/쓰기/이동 명령만을 지원하는 "테이프 오라클"을 정의합니다.

• 결과: 컨트롤러가 튜링 머신의 상태 집합 $Q$와 테이프 알파벳 $\Gamma$에 대해 $O(\log |Q| + \log |\Gamma|)$ 비트의 내부 메모리를 가지면, 이 테이프 오라클과 상호작용할 때 단일 테이프 튜링 머신을 시뮬레이션할 수 있습니다.
• 튜링 완전성: 시스템은 튜링 완전해집니다. 컨트롤러는 테이프를 저장할 필요가 없습니다. 단지 시뮬레이션되는 머신의 현재 상태와 동작 모드만을 저장하면 됩니다.
• 구체적 분리: 논문은 등가성 문제 $EQ_n$($n$비트 문자열 두 개가 같은지 확인하는 문제)을 사용하여 구체적인 지수적 하한선을 제공합니다.
  • 도구가 없을 때: $EQ_n$을 해결하려면 최소 $2^n$개의 상태를 가진 컨트롤러가 필요합니다.
  • 테이프 접근이 있을 때: 단 하나의 상수 크기 컨트롤러(n에 독립적)가 모든 $n$에 대해 $EQ_n$을 해결할 수 있습니다.

3. 선택적 SSM에 의한 정확한 실현

논문은 위에서 설명한 이론적 유한 상태 컨트롤러가 단순한 추상적 구조가 아니라, 특정 신경망 아키텍처에 의해 정확하게 실현 가능함을 증명합니다.

• 아키텍처: 다음을 갖춘 1층 유한 정밀 선택적 아핀 SSM:
  • 이진 원-핫 숨겨진 상태.
  • $\{0, 1\}$의 원소를 갖는 전이 행렬.
  • 제로 바이어스.
  • 선택성(Selectivity): 전이 행렬 $A_\omega$는 현재 관측 토큰 $\omega$에 의존합니다.
• 선택성의 중요성: 저자들은 선택성이 핵심적인 아키텍처 요소임을 강조합니다. 고정된 선형 시불변(LTI) 순환 구조(비선택적)는 이 설정에서 임의의 유한 제어를 구현할 수 없습니다.
• 차원: 필요한 숨겨진 차원은 원-핫 인코딩을 사용할 때 $d = O(|Q| \cdot |\Gamma|)$입니다.

4. 정확한 자원 계량 (부록 결과)

부록 자료는 자원 경계치를 정교화합니다:

• 로그 시뮬레이션: 고정된 리드아웃(readout)에 머신 설명을 하드코딩하고 테이프를 외부 메모리로 사용함으로써, $O(\log B)$ 비트의 순환 비트만으로 임의의 $B$-상태 튜링 머신을 시뮬레이션할 수 있습니다. 이는 차원을 $O(|Q|)$에서 $O(\log |Q|)$로 개선합니다.
• 직접 실현의 불가능성: 외부 메모리 없이 임의의 $B$-상태 전이 맵을 단일 아핀 순환 업데이트로 정확히 실현하려면 정확히 $B-1$의 총 순환 차원이 필요합니다. 이는 로그 이득이 상태를 외부 테이프로 오프로딩하는 것에 엄격하게 의존함을 확인시켜 줍니다.

의의 및 주장

본 논문은 도구로 증강된 순환 계산의 정확한 자원 계량적 모습을 제공한다고 주장합니다. 주요 의의는 다음과 같은 **날카로운 이분법(sharp dichotomy)**을 확립한 데 있습니다:

1. 유한 상태 도구는 표현력 클래스 측면에서는 계산적으로 "공짜"이지만(정규 언어로 남음), 작은 선형 메모리 비용을 발생시킵니다.
2. 무한 테이프 도구는 컨트롤러 아키텍처가 선택성을 지원한다는 전제하에, 최소한의 로그 내부 메모리 비용으로 튜링 완전성이라는 거대한 표현력의 도약을 제공합니다.

이 연구는 도구 사용이 언제 힘을 발휘하는지에 대한 질문을 해결합니다: 그것은 컨트롤러 자체가 아니라, 도구의 상태 공간과 인터페이스에 의해 결정됩니다. 결과는 근사, 확률적 논증, 또는 훈련에 의존하지 않는 정확한 구성 및 무조건적 하한선을 제공합니다. 결론적으로, 현대적 SSM의 "선택적" 특성(전이가 입력에 의존하는 특성)이 이러한 모델들이 외부 메모리와 결합하여 정확한 유한 컨트롤러로서 작동할 수 있게 하는 구체적인 메커니즘이며, 이를 통해 유한 정밀도 모델과 튜링 완전한 계산 사이의 간극을 메운다는 점을 밝히고 있습니다.