The Illusion of State in State-Space Models

State-space models (SSMs) have emerged as a potential alternative architecture for building large language models (LLMs) compared to the previously ubiquitous transformer architecture. One theoretical weakness of transformers is that they cannot express certain kinds of sequential computation and state tracking (Merrill&Sabharwal, 2023), which SSMs are explicitly designed to address via their close architectural similarity to recurrent neural networks (RNNs). But do SSMs truly have an advantage (over transformers) in expressive power for state tracking? Surprisingly, the answer is no. Our analysis reveals that the expressive power of SSMs is limited very similarly to transformers: SSMs cannot express computation outside the complexity class $\mathsf{TC}^0$. In particular, this means they cannot solve simple state-tracking problems like permutation composition. It follows that SSMs are provably unable to accurately track chess moves with certain notation, evaluate code, or track entities in a long narrative. To supplement our formal analysis, we report experiments showing that Mamba-style SSMs indeed struggle with state tracking. Thus, despite its recurrent formulation, the"state"in an SSM is an illusion: SSMs have similar expressiveness limitations to non-recurrent models like transformers, which may fundamentally limit their ability to solve real-world state-tracking problems.

한 줄 요약

S4, Mamba 등 주요 SSM은 순차적 상태 추적 문제를 해결하지 못하며, 이는 Transformer와 유사한 표현력 한계를 가진다.

핵심 기여도

S4, Mamba, S6와 같은 주요 SSM이 순차적 문제 해결 능력이 제한되어 있으며, 이는 $\mathsf{TC}^0$ 복잡도 클래스 내에 속함.
순열 합성 문제(S₅ word problem)는 SSM이 해결하지 못하지만, RNN은 단 1층으로 해결 가능함.
실험적으로 S4와 Mamba가 순열 합성 문제를 학습하지 못함을 보여줌.
입력 종속적 전이 행렬을 도입한 SSM 확장이 상태 추적 문제를 해결할 수 있음을 제시.

핵심 아이디어

S4, Mamba 등 SSM은 순환 신경망(RNN)과 유사한 구조를 가지며, 순차적 계산과 상태 추적 문제를 해결할 수 있다고 여겨졌다. 그러나 본 연구는 이들이 사실상 Transformer와 동일한 표현력 한계를 가지고 있음을 이론적으로 증명한다. 특히, S₅ word problem과 같은 순열 합성 문제는 $\mathsf{NC}^1$-hard로 분류되며, SSM이 이를 해결할 수 없다는 점에서 그 한계가 드러난다. 이는 SSM의 "상태"가 순환 구조를 가졌음에도 불구하고, 실제 상태 추적 능력이 부족함을 의미한다. 연구는 또한 입력 종속적 전이 행렬을 도입한 SSM 확장이 상태 추적 문제를 해결할 수 있음을 보여주며, 새로운 SSM 아키텍처 개발을 제안한다.

기술적 접근법

**S₅ word problem**: 순열 합성 문제로, $\mathsf{NC}^1$-complete이며, 상태 추적의 핵심 문제로 사용됨.
**복잡도 분석**: S4, Mamba, S6 등 SSM이 $\mathsf{TC}^0$ 복잡도 클래스에 속함을 증명.
**실험 설정**: S4, Mamba, Transformer가 순열 합성 문제를 학습하지 못함을 실험적으로 검증.
**확장 모델**: 입력 종속적 전이 행렬을 도입한 SSM 확장(예: Liquid S4)이 S₅ 문제를 해결함을 보여줌.
**하이퍼파라미터**: 실험은 고정된 레이어 수(예: 1층)에서 수행됨.

주요 결과

S₄, Mamba, S₆ SSM은 순열 합성 문제(S₅ word problem)를 해결하지 못함.
RNN은 단 1층으로 순열 합성 문제를 학습하지만, SSM과 Transformer는 학습 실패.
S₄와 Mamba는 $\mathsf{NC}^1$-hard 문제를 해결할 수 없으며, 이는 $\mathsf{TC}^0$ 표현력 한계에 기인함.
입력 종속적 전이 행렬을 도입한 SSM 확장은 S₅ 문제를 해결함.

의의 및 한계

본 연구는 SSM이 순차적 상태 추적 문제를 해결하는 데 있어 Transformer와 동일한 한계를 가지고 있음을 이론적으로 입증함으로써, SSM의 설계 철학에 대한 재평가를 촉구한다. 특히, S₅ word problem은 실제 세계 문제(예: 체스 상태 추적, 코드 평가, 장편 서사에서의 인물 추적)와 밀접한 관련이 있어, SSM의 실용적 한계를 드러낸다. 그러나 연구는 입력 종속적 전이 행렬을 도입한 SSM 확장이 상태 추적 문제를 해결할 수 있음을 제시하며, 새로운 연구 방향을 제시한다. 한계로는 확장된 SSM이 대규모 언어 모델링에 실제로 적용 가능한지 여부는 여전히 미지수이다.

실용적 활용

본 연구는 SSM이 체스 게임 상태 추적, 코드 평가, 장편 서사에서의 인물 추적과 같은 순차적 상태 추적 문제를 해결하지 못함을 보여주며, 이러한 문제를 해결하기 위한 새로운 SSM 아키텍처 개발을 촉구한다. 특히, 입력 종속적 전이 행렬을 도입한 SSM 확장은 이러한 문제 해결에 실용적 잠재력을 보인다.