The Effect of Depth on the Expressivity of Deep Linear State-Space Models

Zeyu Bao, Penghao Yu, Haotian Jiang, Qianxiao Li · 2025

Read The Effect of Depth on the Expressivity of Deep Linear State-Space Models by Zeyu Bao, Penghao Yu, Haotian Jiang, Qianxiao Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19296.txt.

Introduction

Zeyu Bao and co-authors published this study in 2025. It examines state-space models, a family of sequence models now popular beside transformers. The question is what depth adds: does stacking more layers let a linear model express more? The authors study deep linear versions, where the math stays tractable. First, with no limits on parameter size, depth and width turn out broadly equal at matched parameter counts.

Limits change the verdict. When parameter norms are capped, deep models gain an edge. The team shows a shallow model with large norms can be rebuilt as a deep one with small norms. They also bound the least depth needed for such a rebuild. Computer checks support the theory. The upshot: depth is a real resource when weights must stay modest.

Catalog record

CREATORZeyu Bao, Penghao Yu, Haotian Jiang, Qianxiao Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-19296

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Effect of Depth on the Expressivity of Deep Linear State-Space Models Zeyu Bao, Penghao Yu, Haotian Jiang, Qianxiao Li Abstract Deep state-space models (SSMs) have gained increasing popularity in sequence modelling. While there are numerous theoretical investigations of shallow SSMs, how the depth of the SSM affects its expressiveness remains a crucial problem. In this paper, we systematically investigate the role of depth and width in deep linear SSMs, aiming to characterize how they influence the expressive capacity of the architecture. First, we rigorously prove that in the absence of parameter constraints, increasing depth and increasing width are generally equivalent, provided that the parameter count remains within the same order of magnitude. However, under the assumption that the parameter norms are constrained, the effects of depth and width differ significantly. We show that a shallow linear SSM with large parameter norms can be represented by a deep linear SSM with smaller norms using a constructive method. In particular, this demonstrates that deep SSMs are more capable of representing targets with large norms than shallow SSMs under norm constraints. Finally, we derive upper bounds on the minimal depth required for a deep linear SSM to represent a given shallow linear SSM under constrained parameter norms. We also validate our theoretical results with numerical experiments. 1 Introduction Recent advances in state space model(SSM) have been successful in learning long sequence relationships via mitigating the computational inefficiency of explicitly modeling token interactions ( Gu & Dao 2023 ; Gu et al. 2021a ; Gu et al. 2020 ; Gu et al. 2021b ; Smith et al. 2022 ) . It achieves significantly better performance compared with attention-based transformers in the long range arena (LRA) dataset ( Tay et al. 2020 ) . The linear time-invariant structure of SSM allows for an asymptotic computational complexity of only O(T\log T) , which is significantly better than the O(T^{2}) complexity of traditional full-attention approaches exhibiting significant computational demands ( Vaswani et al. 2017 ) . Moreover, SSMs have proven effective in multiple domains dealing with continuous signal data, including audio and vision tasks ( Li et al. 2024 ; Goel et al. 2022 ; Nguyen et al. 2022 ) . Despite its success across various fields of practical application, many theoretical questions remain unanswered. One of the biggest problems is the expressivity of deep state-space models. Although modern SSMs ( Smith et al. 2022 ; Gu & Dao 2023 ) comprise dozens of layers and contain millions of parameters, it is still unclear what the real difference is between shallow SSMs and deep SSMs, and the reason why we need depth in state-space models. Another notable problem is what kind of sequence to sequence relationship can be handled better with a deep network than with a shallow network. A number of recent works have employed dynamical systems approaches to study token stability in deep SSMs ( Vo et al. 2024 ) . Geshkovski et al. 2023 uses a similar dynamics-based formulation to investigate feature clustering behaviors in transformers. Other studies focus on the training dynamics of deep linear networks from an optimization perspective ( Menon 2024 ) . However, relatively little work has been devoted to understanding how depth affects the expressivity of deep SSMs. In this paper, we adopt a simple formulation that allows us to characterize important differences between multi-layer SSM and one-layer SSM. Our main contributions are presented as follows: • In Theorem 4.1 , we prove that, in the absence of norm constraints, depth and width are equivalent in approximation in the sense that under a fixed parameter budget, models of arbitrary depth achieve the same expressive power. • In Theorem 4.2 , we demonstrate that a shallow SSM with large-norm weights can be exactly represented by a deep SSM with smaller-norm weights, under explicit norm constraints on the model parameters. • We establish upper bounds on the minimal depth required for a deep linear SSM to represent a given shallow linear SSM in the regime of constrained parameter norms in Theorem 4.3 and validate our theoretical results with numerical experiments. 2 Related works Expressivity of State-Space Models State-space models originate from the HIPPO matrix, which is optimal in the online function approximation sense ( Smith et al. 2022 ; Gu et al. 2020 ) . Wang & Xue 2023 also provides theoretical guarantees for the approximation of continuous sequence-to-sequence mappings using SSMs with layer-wise nonlinear activations. Furthermore, Muca Cirone et al. 2024 employed tools from Rough Path Theory to show that deep diagonal SSMs possess less expressive power than their non-diagonal counterparts. However, these works primarily focus on function approximation of deep SSMs, whereas the present work aims to present the simplest setting where one can study how depth influences the expressivity in deep SSMs. Dynamics in deep State-Space Models Several works focus on dynamics in deep SSMs. Vo et al. 2024 investigates the divergence behavior of tokens in a pre-trained Mamba model by characterizing continuous-time systems. Smekal et al. 2024 shows how the memory of a deep linear SSM varies with the depth and width, and how the learning dynamics of deep linear models vary with memory expressivity. Our work focuses on a different setting and complements existing analyses by providing a theoretical understanding of depth in deep linear SSMs. Deep linear networks Simple linear architectures often serve as effective tools for gaining theoretical insights into the behavior of deep neural networks. Arora et al. 2018 proves that the convergence of gradient descent achieves a linear rate for training a deep linear neural network over whitened data under certain conditions. Bah et al. 2022 also shows that optimizing a deep linear network is equivalent to Riemannian gradient flow on a manifold of low-rank matrices, with a suitable Riemannian metric. Gruber & Avron 2024 study the implicit bias arising from weight initialization in deep linear networks, offering the insight that weight norms are central to understanding the behavior of deep models. Following prior theoretical analysis of deep linear networks, our work focuses on understanding the expressivity of deep recurrent models, specifically deep state-space models. 3 Problem Formulation One particularly notable feature of currently popular sequential models such as S4 ( Smith et al. 2022 ) and Mamba ( Gu & Dao 2023 ) is the stacking of multiple layers, which leverages scaling laws to increase the number of parameters and achieve stronger performance. In this section, we aim to provide a theoretical perspective on the architecture of deep state-space models, to characterize more precisely how depth contributes to their success. 3.1 Deep Linear State-Space Models For a general l -layer deep state-space model, we express its recurrent form as follows, where each layer’s input comes from the previous layer’s output: \displaystyle y(t) \displaystyle=C^{T}\sigma(h_{l}(t)) (1) \displaystyle h_{l}(t+1) \displaystyle=A_{l}h_{l}(t)+B_{l}\sigma(h_{l-1}(t+1)) \displaystyle h_{2}(t+1) \displaystyle=A_{2}h_{2}(t)+B_{2}\sigma(h_{1}(t+1)) \displaystyle h_{1}(t+1) \displaystyle=A_{1}h_{1}(t)+B_{1}x(t+1) where h_{l}(t)\in\mathbb{R}^{m} is the hidden state of l -th layer at time step t . \sigma:\mathbb{R}^{m\times 1}\to\mathbb{R}^{m\times 1} is activation function on hidden state h_{l}(t) . A_{1},...,A_{l},B_{2},...,B_{l}\in\mathbb{C}^{m\times m} and C,B_{1}\in\mathbb{C}^{m\times 1} are hidden matrices. Also, A_{1},...,A_{l} are the state-space matrices, B_{1},...,B_{l} are the input matrices and C is the output matrix. For each scalar input x(t)\in\mathbb{R} , we obtain an output y(t)\in\mathbb{R} by passing it through this

Read the complete text