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

Published in Transactions on Machine Learning Research (09/2026) Despite this practical success, a rigorous understanding of the expressive power of multi-layer SSMs remains incomplete. A growing body of theoretical work has begun to map the computational landscape of these architectures. Merrill et al. (2024) showed that, under standard complexity-theoretic assumptions, common SSMs like S4 and Mamba cannot express computations outside TC0, placing them on a similar footing to transformers in terms of circuit complexity. Sarrof et al. (2024) studied SSM expressiveness through the lens of formal languages, identifying both strengths and weaknesses relative to transformers. Muca Cirone et al. (2024) provided a continuous-time analysis via rough path theory, characterizing the closure of linear controlled differential equations that underpin selective SSMs, while Zubic & Scaramuzza (2025b) studied regularity and stability properties of selective SSMs with discontinuous gating. Although these results offer important insights, they primarily address single-layer or time-invariant models, or operate in asymptotic regimes that do not directly capture the interplay between depth, finite precision, and state dimension in multi-layer architectures. In parallel, the role of chain-of-thought (CoT) reasoning has led to numerous theoretical works in the con- text of transformers. Merrill & Sabharwal (2024) showed that allowing a transformer decoder to generate intermediate tokens before answering can fundamentally expand its computational power: a linear number of CoT steps enables simulation of arbitrary finite automata, while polynomial steps yield the full power of P. Li et al. (2024) proved analogous results for constant-precision transformers, connecting CoT to circuit size. Chen et al. (2025) studied the computational power of Transformers without CoT and the function composition problem. These findings raise a natural question for SSMs: does CoT similarly amplify the power of SSMs, and if so, does the timing of CoT generation matter? This work. We provide a unified theoretical analysis of the expressive power and limitations of multi- layer SSMs, organized around three axes: compositional lower bounds, the role of CoT, and width–precision tradeoffs. Our results are summarized as follows: (i) Lower bound via communication complexity (Theorem 1). Under the canonical blockwise explicit-table encoding, we show that any L-layer SSM solving the (L+3)-function-composition problem must satisfy d2p = Ω(N/L3), where d is the state dimension, p is the per-scalar precision, and N is the problem size. The proof introduces a forward communication model (Definition 3) that captures the layer-by-layer information flow in multi-layer SSMs, and reduces to pointer chasing lower bounds (Nisan & Wigderson, 1993; Mao et al., 2025). This establishes a worst-case resource separation on a canonical sequential-composition benchmark. It is not a claim that every compositional task admits the same reduction or lower bound. (ii) Complementary upper bound and depth hierarchy. We complement the lower bound with a construction showing that K-fold function composition can be solved exactly by a (K+1)-layer SSM with d = 1 and p = Θ(log N), yielding dp = O(log N). Specializing to K = L + 3 gives a constant-gap depth hierarchy: the (L+3)-composition problem is easy for L+4 layers, hence for O(L) layers, but hard for L layers. (iii) Post-input reasoning does not remove the lower bound. Input-interleaved reasoning yields streaming equivalence (Proposition 1, Theorem 4). We distinguish post-input reasoning (of- fline CoT), in which all self-generated tokens appear after the complete exogenous input, from input- interleaved reasoning (online CoT), in which such tokens may be inserted between exogenous tokens. Post-input reasoning is local post-processing in our communication reduction and therefore leaves this lower-bound pipeline unchanged. This is not a claim that post-input computation is useless for ev- ery task. In contrast, within the deterministic generalized model, input-interleaved reasoning admits bidirectional simulation with general one-pass streaming algorithms at the granularity of persistent memory. Consequently, a single-layer generalized SSM solves arbitrary-length function composition with dp = O(log N) using one thought token per exogenous token (Corollary 2). (iv) Width and precision are not interchangeable in the base model (Theorems 5 and 6). We prove that in the base (no-CoT) model, the product dp is not a complete invariant of computational power: a width-w, precision-p machine cannot, in general, be simulated by a width-1, precision-pw machine, nor vice versa. The proofs are algebraic, exploiting a counting argument over affine transition 2

Published in Transactions on Machine Learning Research (09/2026) maps (Theorem 5) and the nonexistence of order-8 affine permutations over F3 2 (Theorem 6). However, once online CoT is allowed, the correct invariant becomes the total persistent memory Lwp, and width and precision become fully interchangeable (Proposition 2). Techniques. Our lower bound strategy connects SSMs to multi-party communication via a forward com- munication model in which K players, each holding one block of the input, communicate in L synchronous rounds. The key observation (Lemma 1) is that because each SSM layer performs an affine state update, the effect of an entire input block on the hidden state can be summarized by a (d2+d)-parameter affine map, which any downstream player can compose with its own summary. This reduction converts an L-layer SSM into an L-round protocol with message length O(d2p). An improved serialization of these synchronous rounds into L + 1 alternating two-party messages, combined with the pointer chasing lower bound of Mao et al. (2025), yields the desired Ω(N/L3) bound. For the CoT results, the decisive issue is when thought tokens are generated relative to the exogenous input stream. Post-input reasoning amounts to local post-processing by the final player and cannot alter the information exchanged during the communication rounds. Input-interleaved reasoning permits state- dependent feedback before the next exogenous token arrives, enabling a bidirectional simulation with general deterministic one-pass streaming algorithms at the granularity of persistent memory. Organization. Section 2 surveys related work. Section 3 introduces the generalized multi-layer SSM and the communication model. Section 4 presents the main lower bound and its proof strategy via the com- munication reduction. Section 5 gives the complementary upper bound via explicit construction. Section 6 formalizes post-input (offline) and input-interleaved (online) CoT and establishes their contrasting effects on expressiveness. Section 7 analyzes width–precision tradeoffs. Section 8 discusses implications and open problems. Full proofs are deferred to Appendices A–D. The main text retains theorem statements and proof roadmaps. 2 Related Work State-space models and efficient recurrences. The structured state-space model S4 (Gu et al., 2022) demonstrated that linear recurrences with carefully parameterized transition matrices capture long-range dependencies while admitting efficient parallel training. This paradigm has since expanded into a rich family of architectures: S5 (Smith et al., 2023) simplifies to a diagonal parameterization purely in the time domain while retaining parallelism, the Linear Recurrent Unit (Orvieto et al., 2023) further distills the design to its minimal components, Mamba (Gu & Dao, 2024) introduces input-dependent (selective) gating and achieves transformer-competitive language modeling, S7 (Soydan et al., 2024) makes S5 input-dependent, and Mamba-2 (Dao & Gu, 2024) reveals a formal duality between selective SSMs and structured attention. Additional efficient recurrent alternatives include RWKV (Peng et al., 2023), Griffin (De et al., 2024) and GG-SSMs (Zubic & Scaramuzza, 2025a). A common structural feature of many of these models, and the only such feature used by our communication reduction, is that the update is affine in the previous hidden state once the current layer input is fixed. These affine updates can be composed over a token block. Definition 1 isolates this property while deliberately abstracting away architecture-specific parameterizations, gating constraints, training dynamics, and hardware implementations. It is therefore a common upper-level model for lower-bound analysis. Expressiveness and limitations of recurrent and state-space models. The theoretical study of recurrent architectures has a long history. Siegelmann & Sontag (1995) established that recurrent neural networks with infinite-precision rational weights are Turing-complete, but this result relies crucially on unbounded precision. Under finite or saturated precision, the computational power contracts sharply: Weiss et al. (2018) showed empirically that finite-precision RNNs behave as finite automata, and Merrill et al. (2020) formalized this by proving that saturated RNNs recognize exactly the regular or counter languages depending on the gating architecture. For SSMs specifically, Merrill et al. (2024)