arXiv:2604.14501v2 cs.LG

다층 SSM의 표현력과 한계

On the Expressive Power and Limitations of Multi-Layer SSMs

Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

제출 2026-04-16

한국어 초록

깊이, 유한 정밀도, 상태 차원, 사고의 연쇄(CoT)가 다층 상태공간 모델(SSM)의 표현력에 미치는 영향을 연구한다. 순차적 정보 전파를 위한 표준 벤치마크인 명시적 테이블 $K$-함수 합성(explicit-table $K$-function-composition) 문제에 대해, $(L+3)$-함수 합성을 푸는 임의의 $L$-층 SSM은 $d^2p=Ω(N/L^3)$를 만족해야 함을 증명한다. 여기서 $d$는 상태 차원, $p$는 스칼라당 정밀도이다. 반대로 $K$-함수 합성은 $d=1$, $p=Θ(\log N)$인 $(K+1)$-층 일반화 SSM으로 정확히 풀 수 있다. 이는 해당 형식적 문제군에 대한 최악의 경우 깊이 계층(depth hierarchy)을 제공한다. 이어 입력 후 추론(post-input reasoning)—모든 사고 토큰이 입력 이후에 생성되는 경우—과 입력 교차 추론(input-interleaved reasoning)—입력 스트림을 읽는 동안 사고 토큰을 삽입할 수 있는 경우—을 구분한다. 입력 후 추론은 통신 기반 하한 파이프라인을 우회하지 못하는 반면, 입력 교차 추론은 지속 메모리(persistent memory) 수준에서 일반적 결정론적 일패스 스트리밍 알고리즘과의 양방향 시뮬레이션을 허용한다. 마지막으로 기본 affine-state 모델에서 정확한 단계 보존(step-preserving) 시뮬레이션 하에서는 너비(width)와 정밀도가 상호 대체 불가능하지만, 입력 교차 추론이 허용되면 스트리밍 메모리 특성화(streaming-memory characterization)를 통해 상호 대체 가능해진다.

원문 초록

We study how depth, finite precision, state dimension, and chain-of-thought (CoT) affect the expressive power of multi-layer state-space models (SSMs). For the explicit-table $K$-function-composition problem, a canonical benchmark for sequential information propagation, we prove that any $L$-layer SSM solving $(L+3)$-function composition must satisfy $d^2p=Ω(N/L^3)$, where $d$ is the state dimension and $p$ is the per-scalar precision. Conversely, $K$-function composition is solved exactly by a $(K+1)$-layer generalized SSM with $d=1$ and $p=Θ(\log N)$. This gives a worst-case depth hierarchy for this formal problem family. We then distinguish post-input reasoning, in which all thought tokens are generated after the input, from input-interleaved reasoning, in which thought tokens may be inserted while the input stream is being read. Post-input reasoning does not circumvent our communication-based lower-bound pipeline, whereas input-interleaved reasoning admits bidirectional simulations with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Finally, width and precision are not interchangeable under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved reasoning is allowed.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2604.14501v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.