---
title: "Zubić et al. study expressive power of multi-layer SSMs at University of Zurich; Depth-precision bound; Ω(N/L^3)."
sdDatePublished: "2026-09-08T09:20:00Z"
source: "https://rpg.ifi.uzh.ch/docs/Zubic_TMLR_Expressive_2026.pdf"
topics:
  - name: "science and technology"
    identifier: "medtop:13000000"
locations:
  - "Zürich"
  - "Zhuzhou"
  - "Shenzhen"
---


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)