🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

이 논문은 시계열 논리(temporal logics)를 사용하여 상태 공간 모델(SSM)의 표현력을 분석하며, 게이팅 메커니즘과 산술 정밀도에 따라 이들의 능력이 정규 언어에서 비정규 언어까지 범위가 달라짐을 밝히고, 이러한 발견을 트랜스포머 아키텍처와 체계적으로 비교한다.

원저자: Eric Alsmann, Lowejatan Noori, Martin Lange

게시일 2026-01-28

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Eric Alsmann, Lowejatan Noori, Martin Lange

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 로봇에게 이야기를 읽고 사건의 순서를 이해하는 법을 가르치려 한다고 상상해 보세요. 인공지능의 세계에는 이 일을 맡기기 위해 경쟁 중인 두 가지 주요 유형의 "독자"(아키텍처)가 있습니다. 바로 유명한 트랜스포머(Transformers)(현재 챗봇들을 움직이는 기술)와 떠오르는 신성인 **상태 공간 모델(State Space Models, SSMs)**입니다.

이 논문은 SSM의 "두뇌 능력"에 대한 이론적 조사입니다. 저자들은 이 모델들이 특정 테스트에서 얼마나 잘 수행하는지를 묻는 것이 아니라, **"얼마나 많이 훈련시키더라도 이 모델들이 이해할 수 있는 절대적인 한계는 어디까지인가?"**를 묻고 있습니다.

이 질문에 답하기 위해, 그들은 특별한 "논리 언어"(시제 논리, Temporal Logic)를 측정 기준으로 사용합니다. 다음은 간단한 비유를 사용한 연구 결과의 요약입니다.

1. SSM의 두 가지 주요 유형

논문은 정보를 처리하는 방식에 따라 SSM을 두 가지 맛으로 나눕니다.

대각 게이트 SSM (Diagonal-Gated SSMs - "엄격한 회계사"): 이 모델들은 현재 읽고 있는 단어에 따라 내부 "게이트"(정보 흐름을 제어하는 스위치)를 변경할 수 있지만, 반드시 "대각선" 형태를 유지해야 한다는 규칙이 있습니다. 이것은 숫자를 더할 때 숫자는 바꿀 수 있지만, 열(column)끼리 서로 섞을 수는 없는 계산기와 같습니다.
시변 불변 SSM (Time-Invariant SSMs - "일정한 시계"): 이 모델들은 어떤 단어를 읽든 상관없이 변하지 않는 게이트를 가지고 있습니다. 이들은 메트로놈이나 시계와 같습니다. 이야기의 내용과 상관없이 일정한 속도로 똑딱거립니다.

2. 정밀도의 문제: 자 vs 줄자

저자들은 또한 이 모델들 내부의 수학적 "정밀도"를 살펴보았습니다.

고정 정밀도 (Fixed-Precision): 눈금이 10개뿐인 자를 사용하는 것을 상상해 보세요. 이야기가 아무리 길어져도, 그 눈금보다 작은 것은 측정할 수 없습니다. 이것은 표준적인 컴퓨터 연산(부동 소수점)과 같습니다.
로그 정밀도 (Log-Precision): 이야기가 길어짐에 따라 자동으로 더 길어지고 더 세밀해지는 줄자를 사용하는 것을 상상해 보세요. 이야기가 100단어라면 자에 100개의 눈금이 있고, 1,000단어라면 1,000개의 눈금이 있습니다. 이를 통해 훨씬 더 미세한 측정이 가능합니다.

3. 이들은 실제로 무엇을 이해할 수 있는가?

"엄격한 회계사" (대각 SSM)

단순한 자를 사용할 때 (고정 정밀도): 이들은 사건의 순서를 이해하는 데 능숙합니다. "A가 B보다 먼저 일어났다"거나 "A가 일어났고, 그다음 B가 일민, 그다음 C가 일어났다"는 것을 말할 수 있습니다. 하지만 결정적인 약점이 있습니다: 순환(cycle)을 셀 수 없습니다.
- 비유: 만약 이들에게 "짝수 개의 'a'가 나타나는 패턴"(예: aa, aaaa, aaaaaa)을 인식하라고 요구하면 실패합니다. 그들의 수학은 단조 증가(monotonic)하기 때문에(계속 올라가거나 유지됨), 결국 "막혀버려서" 2개의 'a'와 4개의 'a'를 구분하지 못하게 됩니다.
성장하는 줄자를 사용할 때 (로그 정밀도): 만약 이들에게 정밀하게 셀 수 있는 능력을 부여한다면, 이들은 훨씬 더 똑똑해집니다. 이제 과거에 어떤 일이 정확히 몇 번 일어났는지 셀 수 있습니다. 이들은 "a의 개수가 b의 개수와 c의 개수와 같다"와 같은 복잡한 패턴도 이해할 수 있습니다.

"일정한 시계" (시변 불변 SSM)

단순한 자를 사용할 때: 이 모델들은 복잡한 "그 이후(since)" 관계(예: "마지막으로 'b'가 나타난 이후로 'a'가 나타났는가?")를 추적하는 데 서툽니다. 하지만 초능력이 있습니다: 원형으로 셀 수 있습니다.
- 비유: 내부 메커니즘이 일정한 순환 구조이기 때문에, 이들은 "지금이 2번째, 4번째, 혹은 6번째 단어인가?"를 아는 데 탁월합니다. 이들은 엄격한 회계사가 실패했던 "짝수 개의 'a's" 패턴을 쉽게 인식할 수 있습니다.
성장하는 줄자를 사용할 때: 이들은 원형으로 세는 것과 전체 숫자를 세는 것 둘 다 할 수 있습니다.

"하이브리드" (혼합 SSM)

두 유형의 레이어(엄격한 회계사와 일정한 시계)를 결 모두 결합하면, 두 세계의 장점을 모두 얻게 됩니다. 이들은 순서, 순환, 그리고 숫자를 세는 법을 모두 이해할 수 있습니다. 논문은 이러한 하이브리드 모델이 특정 복잡도 한계 내에서 생각할 수 있는 거의 모든 "정규(regular)" 패턴을 인식할 수 있음을 보여줍니다.

4. 트랜스포머와 어떻게 비교되는가?

저자들은 자신들의 발견을 우리가 이미 알고 있는 트랜스포머와 비교했습니다.

**대각 SSM (고정 정밀도)**은 대략 위치 정보가 없는 트랜스포머(단어의 순서는 알지만 정확한 위치는 모르는 모델)와 유사합니다.
시변 불변 SSM은 위치 인코딩(Positional Encodings)이 있는 트랜스포머와 유사합니다.
결정적인 차이점: "전역 주의(global attention)"를 가진 트랜스포머(Average Hard-Attention 유형 등)는 이야기 전체를 한꺼번에 훑어보며 앞뒤로 숫자를 셀 수 있습니다. 반면, SSM은 본질적으로 과거(이미 읽은 것)만을 바라봅니다. 따라서 SSM은 무언가가 나중에 일어날 것을 세는 능력에 있어서 가장 발전된 트랜스포머보다 엄격하게 열등합니다.

5. "불가능한" 과업들

가장 중요한 핵심은 이 모델들이 아무리 많이 훈련하더라도 할 수 없는 일들의 목록입니다.

고정 정밀도 대각 SSM은 반복되는 항목의 짝수와 홀수를 구별하는 법(예: aa와 aaa)을 절대로 배울 수 없습니다. 이것은 훈련의 실패가 아니라, 아키텍처 자체의 근본적인 한계입니다.
이 한계를 깨려면, 반드시 아키텍처를 변경하거나(시변 불변 레이어 추가), 수학적 정밀도를 높여야 합니다(성장하는 줄자 사용).

요약

이 모델들을 서로 다른 유형의 사서라고 생각해 보세요:

대각 (고정형): 책을 순서대로 읽는 데는 능숙하지만, 특정 패턴을 세라고 하면 혼란에 빠집니다.
시변 불변: 페이지 수(짝수/홀수)를 세는 데는 능숙하지만, "그 이후"의 복잡한 이야기에는 서툽니다.
하이브리드: 두 가지를 모두 할 수 있는 궁극의 사서이지만, 여전히 다음 장을 미리 엿보고 뒤에서 일어날 일을 세는 것은 불가능합니다.

이 논문은 이러한 한계가 아키텍처의 DNA에 새겨져 있음을 증명합니다. "고정 정밀도 대각" 사서에게 "숫자 세기" 전문 사서가 되도록 훈련시킬 수는 없습니다. 그 능력을 갖추려면 더 좋은 도구(로그 정밀도)를 주거나 다른 뇌 구조(혼합 레이어)를 제공해야만 합니다.

기술 요약: 시계열 논리를 통한 상태 공간 모델(SSM)의 표현력에 관하여

문제 정의

상태 공간 모델(SSM)은 시퀀스 모델링, 특히 대규모 언어 모델에서 트랜스포머(Transformer) 아키텍처의 강력한 대안으로 부상했습니다. 그러나 급격한 경험적 발전에도 불구하고, SSM의 **표현력(expressive power)**에 관한 이론적 토대는 트랜스포머에 비해 여전히 미개척 영역으로 남아 있습니다. 본 논문이 다루는 핵심 문제는, 훈련 역학(training dynamics)과는 독립적으로 서로 다른 SSM 변체들이 이론적으로 어떤 클래스의 언어와 패턴을 표현할 수 있는지를 결정하는 것입니다. 구체적으로, 본 논문은 두 가지 핵심적인 아키텍처 차원이 표현력에 어떻게 영향을 미치는지 조사합니다:

게이팅 메커니즘(Gating Mechanisms): 시간 불변(time-invariant) 게이트(상수 행렬, 예: S4), 대각 게이트(diagonal-gated) 메커니즘(입력 의존적 대각 행렬, 예: S6), 그리고 임의의(arbitrary) 게이트 간의 구분.
산술 정밀도(Arithmetic Precision): 고정 폭 산술(fixed-width arithmetic, 상수 비트, 예: 표준 부동 소수점)과 로그 정밀도 산술(log-precision arithmetic, 입력 길이에 따라 로그 단위로 스케일링되는 정밀도)의 구분.

저자들은 이러한 변체들을 형식 논리 파편(formal logic fragments) 및 복잡도 클래스(complexity classes)에 매핑하여 엄격한 하한선(lower bounds)을 설정하고 근본적인 아키텍처 병목 현상을 식별하고자 합니다.

방법론

저자들은 트랜스포머의 최근 기초 연구(예: Strobl et al., 2024; Yang et al., 2024a)를 모방하여, SSM의 표현력을 분석하기 위해 논리적 및 복잡도 이론적 프레임워크를 채택합니다.

형식 모델: SSM은 입력 시퀀스를 선형 재귀( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ )를 통해 변환한 후 비선형 출력 함수(ReLU 활성화 피드포워드 신경망으로 모델링됨)를 통과하는 층으로 공식화됩니다.
논리 프레임워크: 분석에는 유한 궤적 위의 선형 시계열 논리(LTLf), 특히 **순수 과거 파편(pure-past fragment, PLTLf)**을 사용합니다. 이 논리는 카운팅(counting) 없이 이벤트 순서에 기반한 속성을 포착합니다.
- 확장: 이 논리는 주기적 위치를 추적하기 위한 **모듈러 술어(modular predicates)**와 카운팅 능력을 분석하기 위한 **역방향 카운팅 연산자( $\overleftarrow{\#}$ )**를 포함하도록 확장됩니다.
구성적 증명(Constructive Proofs): 저자들은 특정 시계열 연산자(예: Yesterday, Previously, Since)와 카운팅 메커니즘이 특정 게이트 구조와 산술 설정을 통해 어떻게 구현될 수 있는지 보여주는 구성적 증명을 제공합니다.
불가능성 증명(Impossibility Proofs): 반대로, 고정 정밀도 대각 SSM에서의 **단조성(monotonicity)**과 같은 속성을 사용하여 특정 비-스타 프리(non-star-free) 언어(예: $(aa)^*$ )를 인식할 수 없음을 입증함으로써 비표현성 결과를 확립합니다.

주요 기여

1. SSM 변체의 표현력 계층 구조

본 논문은 게이팅과 정밀도에 따른 SSM 능력의 상세한 계층 구조를 확립합니다:

대각 게이트 SSM (고정 정밀도):
- 능력: PLTLf로 정의 가능한 모든 언어를 인식합니다 (이는 스타 프리 언어 및 **순서가 있는 일차 논리($FO[<]$)**와 동일함).
- 한계: 반복되는 동일 입력이 상태를 안정화시키는 단조성 특성 때문에 $(aa)^*$ 와 같은 비-스타 프리 언어를 인식할 수 없습니다.
대각 게이트 SSM (로그 정밀도):
- 능력: **PLTLf[ $\overleftarrow{\#}$ ]**에 속하는 언어를 인식하며, 역방향 카운팅을 통해 비-정규(non-regular) 및 심지어 비-문맥 자유(non-context-free) 언어(예: $\{a^n b^n c^n\}$ )까지 표현력을 확장합니다.
시간 불변 SSM (고정 정밀도):
- 능력: 모듈러 술어를 사용하는 **UN-PLTLf[MOD]**의 언어를 인식합니다. 순환 치환 행렬을 사용하여 주기적 위치(예: 짝수/홀수 인덱스 구분)를 추적할 수 있어 $(aa)^*$ 를 인식할 수 있습니다.
- 한계: 현재 정보와 과거 정보를 동적으로 결합할 입력 의존적 게이트가 부족하기 때문에, Since 연산자(예: $L(a \mathcal{S} b)$ )를 요구하는 언어를 인식하지 못한다고 추정됩니다.
혼합(Mixed) SSM (대각 + 시간 불변):
- 능력: 대각 및 시간 불변 능력을 효과적으로 결합한 **PLTLf[MOD]**를 인식합니다. 이는 $AC^0$ 내의 정규 언어 클래스에 해당합니다.
- 로그 정밀도 확장: 로그 정밀도를 갖추면 **PLTLf[ $\overleftarrow{\#}$ , MOD]**를 인식합니다.

2. 결정적 요소로서의 산술 정밀도

본 논문은 로그 정밀도가 비-정규 카운팅 언어를 인식하는 데 엄격히 필요함을 입증합니다. 고정 폭 산술은 SSM을 정규(또는 스타 프리) 언어로 제한하는 반면, 로그 정밀도는 $a^n b^n c^n$ 과 같은 언어에 필요한 카운트 축적을 가능하게 합니다.

3. 트랜스포머와의 체계적 비교

저자들은 SSM 변체를 알려진 트랜스포머 표현력 결과와 직접 매핑합니다:

대각 SSM (고정 정밀도) $\approx$ 위치 인코딩이 없는 고유 하드 어텐션 트랜스포머(UHAT) (둘 다 $FO[<]$를 포착함).
시간 불변 SSM $\approx$ 위치 인코딩이 있는 UHAT (UHAT+PE) (둘 다 $FO[<, MOD]$를 포착함).
혼합 SSM (로그 정밀도) $\approx$ 평균 하드 어텐션 트랜스포머(AHAT) (둘 다 카운팅 능력을 포착하지만, SSM은 역방향 카운팅으로 제한됨).
임의의 게이트: 임의의 게이트를 가진 SSM은 모든 정규 언어를 인식할 수 있으며, 이는 더 복합한 트랜스포머 변체의 상한선과 일치합니다.

주요 결과

정리 1: 고정 정밀도를 가진 대각 SSM은 PLTLf의 모든 언어를 인식한다.
정리 3: 고정 정밀도를 가진 대각 SSM은 $(aa)^*$ 를 인식할 수 없으며, 이는 시간 불변 SSM과의 엄격한 분리를 증명한다.
정리 4: 로그 정밀도를 가진 대각 SSM은 PLTLf[ $\overleftarrow{\#}$ ]의 모든 언어를 인식한다.
정리 7: 고정 정밀도를 가진 시간 불변 SSM은 UN-PLTLf[MOD]의 모든 언어를 인식한다.
따름정리 8: 고정 정밀도를 가진 혼합 SSM은 $AC^0$ 내의 모든 정규 언어를 인식한다.
불가능성: 본 논문은 특정 아키텍처 선택(예: 대각 고정 정밀도)이 아무리 많은 훈련 데이터나 최적화를 투입하더라도 극복할 수 없는 근본적인 병목 현상을 생성함을 보여주는 불가능성 증명을 제공한다.

의의 및 주장

본 논문은 SSM의 표현력과 형식 논리 사이의 첫 번째 연결 고리를 제공하며, 특정 SSM 변체가 이론적으로 학습 가능하거나 확실히 불가능한 패턴에 대한 구조적 보증을 제시한다고 주장합니다.

기초적 통찰: "불가능한" 작업(예: 고정 정밀도 대각 모델의 비-단조 패턴)을 명시함으로써, 본 연구는 훈련 역학과는 독립적인 아키텍처의 한계를 식별하여 경험적 벤치마크를 보완합니다.
아키텍처의 명확성: 결과는 SSM과 트랜스포머의 관계를 명확히 합니다. 즉, SSM은 재귀를 통해 위치 정보를 본질적으로 인코딩하지만(트랜스포머의 위치 인코딩과 유사), 카운팅 메커니즘(전역 어텐션 대비 역방향 카운팅)에서는 차이가 있음을 보여줍니다.
복잡도 일치: 연구 결과는 제한된 SSM(대각/시간 불변 고정 정밀도)이 아마도 $AC^0$ 내에서 작동할 것임을 시사하며, 이는 Merrill et al. (2024)이 확립한 $TC^0$ 상한선의 진부분집합입니다. 이는 이러한 아키텍처가 특정 수정 없이는 패리티(parity)나 $AC^0$ 외부의 다른 언어를 인식할 수 없음을 의미합니다.

저자들은 본 연구가 엄격한 이론적 기준을 확립하였으며, 게이팅 메커니즘과 산술 정밀도의 선택이 특정 훈련 절차와 무관하게 SSM이 모델링할 수 있는 언어 클래스를 근본적으로 결정한다는 점을 밝혀냈다고 결론짓습니다.