Zubić et al. study expressive power of multi-layer SSMs at University of Zurich; Depth-precision bound; Ω(N/L^3).
Zubić et al. study expressive power of multi-layer SSMs at University of Zurich; Depth-precision bound; Ω(N/L^3). Published in Transactions on Machine Learning Research (09/2026) On the Expressive Power and Limitations of Multi-Layer SSMs Nikola Zubić zubic@ifi.uzh.ch Robotics and Perception Group University of Zurich Qian Li liqian.ict@gmail.com Shenzhen International Center For Industrial And Applied Mathematics Shenzhen Research Institute of Big Data Yuyi Wang yuyiwang920@gmail.com Tengen Intelligence Institute CRRC Zhuzhou Institute Davide Scaramuzza sdavide@ifi.uzh.ch Robotics and Perception Group University of Zurich Reviewed on OpenReview: https: // openreview. net/ forum? id= NQ8IcsIti8 Abstract 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 propaga- tion, we prove that any L-layer SSM solving (L + 3)-function composition must satisfy d2p = Ω(N/L3), where d is the state dimension and p is the per-scalar precision. Con- versely, 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 prob- lem 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 circum- vent 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 interchange- able under exact step-preserving simulation in the base affine-state model, but become interchangeable through the streaming-memory characterization once input-interleaved rea- soning is allowed. 1 Introduction State-space models (SSMs) have emerged as a promising alternative to transformers for sequence modeling, offering linear-time inference and principled mechanisms for capturing long-range dependencies (Gu et al., 2022; Gu & Dao, 2024; Dao & Gu, 2024). Architectures such as S4 (Gu et al., 2022) and Mamba (Gu & Dao, 2024) process sequences through a recurrence that is linear in the hidden state yet input-dependent in its transition parameters, enabling efficient parallel training via associative scans while retaining the streaming efficiency of recurrent models. These models have achieved strong empirical performance across language, audio, and genomics, and their multi-layer variants are now deployed at scales comparable to transformer-based large language models. 1 ...