구조화된 상태 공간으로 긴 시퀀스를 효율적으로 모델링하기: S4

Digest: S4(Structured State Space Sequence Model)는 수만 타임스텝에 걸친 장거리 의존성(Long-Range Dependencies)을 효율적으로 모델링하기 위한 새로운 시퀀스 모델 패러다임이다. 핵심 아이디어는 선형 상태 공간 모델(SSM)의 행렬 A를 HiPPO 이론에 기반해 초기화하고, 이를 Normal Plus Low-Rank(NPLR) 구조로 분해하여 수치 불안정성 없이 대각화하는 것이다. 이 분해를 통해 합성곱 커널 계산을 Cauchy 행렬 연산으로 환원함으로써, 기존 LSSL 대비 O(N²L)에서 **O(N+L)**로 연산 복잡도를 획기적으로 낮췄다. S4는 Long Range Arena 벤치마크 전 6개 태스크에서 기존 모든 모델을 압도했으며, 특히 길이 16,384의 Path-X 태스크에서 이전 모든 모델이 실패(~50% 랜덤 수준)한 것과 달리 **96.35%**를 달성하는 최초의 모델이 됐다. Sequential CIFAR-10에서 91.13%, 원시 음성 분류에서 98.32%를 기록하며, Transformer 대비 60배 빠른 생성 속도로 언어 모델링에서도 경쟁력 있는 성능을 보였다. S4는 이후 Mamba, Hyena, StripedHyena 등 선형 복잡도 시퀀스 모델 계열 전체의 이론적·구조적 토대가 된 landmark 연구이다.

섹션별 요약

Introduction

시퀀스 모델링의 핵심 과제는 수천~수만 타임스텝에 걸친 장거리 의존성을 포착하는 것
RNN은 기울기 소실, CNN은 수용 범위 한계, Transformer는 O(L²) 복잡도로 각각 LRD 모델링에 어려움
상태 공간 모델(SSM)은 이론적으로 LRD를 잘 포착할 수 있으나, 기존 LSSL은 O(N²L) 연산과 O(NL) 메모리로 실용 불가
S4는 SSM의 이론적 강점을 실용적 계산 효율과 결합

Methods

SSM 기초: 연속시간 방정식 x’(t) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t)을 bilinear 이산화하여 재귀·합성곱 이중 표현 도출
HiPPO 행렬: A를 직교 다항식 기저(르장드르 다항식)에 대한 최적 투영 연산자로 정의 → 모델이 과거 입력 히스토리 전체를 최적으로 기억
NPLR 분해 (핵심 기여): Theorem 1에 따라 모든 HiPPO 행렬은 A = VΛV* - PQ^T로 분해 가능. 수치적으로 안정된 대각화 달성
Cauchy 커널 계산: NPLR 구조 아래 합성곱 커널 계산을 Cauchy 행렬 문제로 환원 → FFT와 결합해 O(N+L) 달성
훈련/추론 이중 모드: 훈련 시 합성곱(FFT 병렬), 추론 시 재귀(O(1) 상태 업데이트)

Results

Long Range Arena: 전 6개 태스크 평균 86.09% (이전 SOTA Luna-256: 59.37%)
Path-X (16K 길이): 최초로 50% 이상 달성 (96.35%)
Sequential CIFAR-10: 91.13% (2D ResNet18과 동등 수준)
원시 음성 분류 (길이 16,000): 98.32%, MFCC 기존 모델(90.75%) 초과
WikiText-103: 20.95 ppl (Transformer 20.51 대비 미세 차이), 생성 속도 60배 빠름

Discussion

언어 모델링에서 Transformer에 근접하지만 미세하게 뒤처지는 것은 Attention의 강점이 여전히 존재함을 시사
HiPPO 초기화가 NPLR 구조 자체보다 훨씬 중요하다는 절제 실험 — 올바른 귀납적 편향의 중요성 강조
추론 시 스텝 크기 Δ만 조정하면 학습 없이 다양한 샘플링 레이트에 적응 가능

Insights

가장 중요한 아이디어: S4의 핵심은 새로운 아키텍처 발명이 아니라, HiPPO라는 고전적 함수 근사 이론과 Cauchy 행렬이라는 수치 해석 기법을 연결한 데 있다. “올바른 수학적 구조를 찾으면 계산 효율과 표현력을 동시에 얻을 수 있다”
연결 고리 — HiPPO: Gu et al. (2020)의 HiPPO가 “어떤 A 행렬이 장거리 기억에 좋은가”에 답했다면, S4는 “그 행렬을 어떻게 효율적으로 사용하는가”에 답한다
연결 고리 — Mamba, Hyena: S4는 이후 모든 선형 복잡도 시퀀스 모델의 이론적 토대. Mamba(2023)는 선택적 상태 공간을 도입, Hyena는 주의 없이 언어 모델 스케일로 확장
비판적 코멘트: 언어 모델링에서 Transformer 대비 0.44 ppl 높음 → Mamba가 입력 의존적 게이팅으로 이 격차를 해결. NPLR 분해의 구현 복잡도가 높아 후속 연구들이 S4D, DSS 등으로 단순화 시도

Discussion Points

SSM vs. Attention: S4는 모든 입력에 동일한 합성곱 커널 적용(content-agnostic) → Attention의 content-aware 가중치 조절과 근본적 차이. 이 한계가 Mamba의 선택적 SSM으로 이어짐
HiPPO 초기화의 범용성: 이산 텍스트 토큰에서 연속 신호 가정 기반의 HiPPO가 왜 잘 동작하는지 추가 이론화 필요
후속 연구: S4D(대각 단순화), Mamba(선택적 SSM), Hyena/StripedHyena(하이브리드 아키텍처)

메타데이터

항목	내용
제목	Efficiently Modeling Long Sequences with Structured State Spaces
저자	Albert Gu, Karan Goel, Christopher Ré
소속	Stanford University, Hazy Research Lab
연도	2021 (제출), 2022 (ICLR 출판)
학술대회	ICLR 2022 (Outstanding Paper Honorable Mention)
링크	arXiv, GitHub
키워드	State Space Model, HiPPO, NPLR, Long-Range Dependencies, Cauchy Kernel

BibTeX

@inproceedings{gu2022efficiently,
  title={Efficiently Modeling Long Sequences with Structured State Spaces},
  author={Gu, Albert and Goel, Karan and R{\'e}, Christopher},
  booktitle={International Conference on Learning Representations},
  year={2022},
  url={https://arxiv.org/abs/2111.00396}
}

왜 이 연구를 하는가?

핵심 질문

수만 타임스텝 이상의 장거리 의존성을 갖는 시퀀스를, 단일 범용 모델로 계산 효율적으로 처리할 수 있는가?

기존 접근법의 한계

한계	설명
RNN (LSTM, GRU)	기울기 소실/폭발로 수백 스텝 이상 LRD 포착 어려움, 병렬화 불가
CNN	수용 범위가 커널 크기에 제한, 깊은 팽창(dilated) 구조 필요
Transformer	O(L²) 시간·공간 복잡도, 길이 1,000 이상에서 비실용적
기존 SSM (LSSL)	이론적 최적이나 O(N²L) 연산·O(NL) 메모리로 실용 불가

핵심 통찰

HiPPO 행렬 A가 장거리 기억을 위한 최적 귀납적 편향 제공
NPLR 분해로 수치 불안정성을 해결하면서 Cauchy 커널이라는 효율적 계산 경로 확보
연속시간 SSM 기반이므로 Δ 조정만으로 다양한 샘플링 레이트 적응 가능

방법 (Method)

프레임워크 개요

graph TD
    A["입력 시퀀스 u(t)"] --> B["연속시간 SSM 정의\nx' = Ax + Bu\ny = Cx + Du"]
    B --> C["HiPPO 행렬 초기화\n르장드르 다항식 최적 투영"]
    C --> D["NPLR 분해\nA = V*Lambda*V* - PQ^T"]
    D --> E["Bilinear 이산화\nA-bar, B-bar 계산"]
    E --> F["Cauchy 커널 계산\nO(N + L) 복잡도"]
    F --> G1["훈련 모드\ny = K-bar 합성곱 u\nFFT 병렬 처리"]
    F --> G2["추론 모드\nx_k = A-bar*x_{k-1} + B-bar*u_k\nO(N) 재귀"]
    G1 --> H["S4 레이어 출력 y"]
    G2 --> H
    H --> I["비선형 활성화 + 선형 믹싱"]
    I --> J["스택된 S4 레이어들"]
    J --> K["최종 출력"]

핵심 구성요소

HiPPO 행렬: 과거 입력 시그널을 직교 다항식 기저(르장드르 다항식)에 최적 투영하는 이론. 모델이 임의 길이의 과거 입력 히스토리를 최적으로 압축·기억하게 한다.

NPLR 분해 (Theorem 1): 모든 HiPPO 행렬이 A = VΛV* - PQ^T (Normal + Low-Rank) 형태임을 증명. 직접 대각화는 ~2^(4N/3) 크기의 원소를 생성하여 불안정하지만, NPLR 분해는 유니터리 V(완벽한 조건수)로 안정적 대각화를 보장한다.

Cauchy 커널 환원: NPLR 구조 하에서 합성곱 커널 생성 함수를 단위원에서 평가하는 문제가 M_jk = 1/(ω_j - ζ_k) 형태의 Cauchy 행렬 연산으로 환원된다. O(N+L) 시간, O(N+L) 메모리로 계산 완성.

이중 모드 전환: 훈련 시 합성곱 표현(y = K̄ * u)으로 GPU 병렬 처리, 추론 시 재귀 표현(x_k = Āx_{k-1} + B̄u_k)으로 O(N) 상태만 유지하며 스트리밍 처리.

발견 (Findings)

주요 결과

벤치마크	S4	이전 SOTA	비고
LRA 평균 (6 태스크)	86.09%	59.37% (Luna-256)	+26.7pp
Path-X (16K 길이)	96.35%	~50% (모든 모델 실패)	최초 성공
Seq. CIFAR-10	91.13%	84.65% (LSSL)	2D ResNet18 수준
원시 음성 (16K)	98.32%	90.75% (MFCC 기반)	원시 파형으로 최고
WikiText-103	20.95 ppl	20.51 (Transformer)	0.44 차이, 60× 빠른 생성

핵심 발견

Path-X 완전 정복: 16,384 스텝 장거리 의존성을 실제로 포착하는 최초의 모델
원시 신호 처리의 강점: 연속시간 SSM 특성 덕분에 전처리 없는 원시 시계열에서 자연스러운 귀납적 편향
HiPPO 초기화의 결정적 역할: 절제 실험에서 HiPPO 없이 NPLR만 사용하면 ~76%(랜덤 수준)으로 저하

이론적 의의

NPLR 보편성 정리: 함수 해석학(HiPPO)과 수치 선형 대수(Cauchy 커널)를 연결하는 새로운 수학적 다리
계산 복잡도 이론: 재귀 스텝당 O(N), 전체 합성곱 Õ(N+L) 엄밀 증명. LSSL 대비 이론적 ~30배 속도, ~400배 메모리 절감
연속시간-이산시간 통일: Δ 파라미터 하나로 연속시간 신호 모델과 이산 시퀀스 모델을 통일
선형 복잡도 시퀀스 모델의 이론적 토대: Mamba, H3, S5, Hyena, RetNet, RWKV 등 후속 아키텍처의 공통 이론 언어 제공

핵심 용어 정리

용어	정의
SSM (State Space Model)	x’(t) = Ax(t) + Bu(t), y(t) = Cx(t) + Du(t) 형태의 선형 동역학계
HiPPO	과거 입력을 직교 다항식 기저에 최적 투영하는 이론. 장거리 기억을 가능하게 하는 A 행렬 구조 제공
NPLR (Normal Plus Low-Rank)	A = VΛV* - PQ^T 형태의 행렬 분해. 안정적 대각화를 가능하게 함
Cauchy 커널	M_jk = 1/(ω_j - ζ_k) 형태의 행렬. O(N+L) 시간에 계산 가능
Long-Range Dependencies	수백~수만 타임스텝 이상 떨어진 위치 간의 정보 의존 관계
Bilinear Discretization	연속시간 SSM을 이산시간으로 변환하는 Tustin 방법
합성곱 커널	SSM 재귀를 펼친 K̄ = (C̄B̄, C̄ĀB̄, …, C̄Ā^(L-1)B̄). y = K̄ * u
Long Range Arena (LRA)	효율적 시퀀스 모델 평가 벤치마크. 6개 태스크, 최대 16,384 길이
Path-X	LRA 최난이도. 16,384 픽셀 이미지에서 경로 연결 여부 판별

Juhyeon's Blog

탐색기

Efficiently Modeling Long Sequences with Structured State Spaces