Theoretical Foundations of Deep Selective State-Space Models

Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, Terry J. Lyons

Abstract

This paper establishes the first rigorous theoretical framework for understanding "selective" State-Space Models (SSMs), such as Mamba, by establishing a formal link to Rough Path Theory. We demonstrate that the input-dependent gating mechanism in these models allows them to transcend the limitations of simple linear filtering. By mapping discrete-time SSMs to continuous-time Linear Controlled Differential Equations (CDEs), we characterize the fundamental representational limits (the "closure") of both dense and diagonal SSM architectures, proving that stacking multiple diagonal layers is a theoretical necessity for achieving full expressive power.

Introduction

In the landscape of deep learning, a persistent trade-off has existed between the reasoning capabilities of Transformers and the computational efficiency of State-Space Models (SSMs). While Transformers offer unparalleled performance through content-based reasoning, their quadratic scaling ($O(L^2)$) limits their application to long sequences. Conversely, traditional SSMs like S4 scale linearly ($O(L)$) but often struggle with tasks requiring fine-grained, input-dependent attention.

Recently, "selective" SSMs, most notably Mamba, have bridged this performance gap. However, the mathematical justification for why this selectivity works—and what its ultimate limits are—has remained largely unexplored. This research addresses this gap by asking: What is the most a model can achieve if its recurrence is linear in the hidden state but non-linear in the input?

Theoretical Framework: SSMs as Linear CDEs

To analyze the expressivity of selective SSMs, we translate their discrete-time recurrences into a continuous-time framework known as Linear Controlled Differential Equations (CDEs). This translation allows us to leverage tools from Rough Path Theory, specifically the concept of a Path Signature.

A Path Signature is a mathematical object that captures the order and interaction of sequence elements. We show that the output of a generalized selective SSM can be represented as a linear combination of terms within the signature of the input path. This provides a closed-form description of the functions these models can approximate, which we term the "uniform closure."

The Power of the Gate

The "secret sauce" of Mamba lies in its selectivity mechanism (the $\omega$ gate). In non-selective models like S4, the gate is essentially a function of time, restricting the model to acting as a linear filter. In Mamba, the gate depends directly on the input. This allows the model to "re-parametrize" time, performing context-dependent filtering that can focus on specific parts of a sequence while ignoring others. This mechanism is what enables Mamba to capture higher-order interactions between channels that previous SSMs completely missed.

Architectural Trade-offs: Dense vs. Diagonal

A significant portion of our analysis focuses on the gap between dense and diagonal transition matrices.

  • Dense Matrices: We prove that a single layer with a dense transition matrix is a universal approximator for path-to-path maps. This links SSMs to the paradigm of reservoir computing, where even a randomly initialized dense recurrence followed by a trainable head can achieve full expressivity.
  • Diagonal Matrices: For hardware efficiency, models like Mamba utilize diagonal matrices. However, we prove a theoretical "gap" in expressivity for single layers. A single diagonal layer is strictly less powerful than a dense one.
  • Chaining: To overcome this limitation, we demonstrate that one must stack multiple diagonal layers (chaining) to recover the full expressive power of a dense system. This provides a formal theoretical justification for the deep architectures used in practice.

Empirical Validation

We validated these theoretical insights using two primary synthetic benchmarks designed to test specific representational properties:

  1. Anti-symmetric Signature Task: This regression task requires predicting the "area" or "volume" enclosed by an input path. It specifically tests the model's ability to capture cross-channel interactions. Our results show that Mamba’s gating allows it to solve this task, whereas non-selective models fail.
  2. $A_5$ Benchmark: This state-tracking task involves composing permutations from the group $A_5$. It tests the ability to maintain complex internal states over long sequences. We found that while S4 and Mamba require an increasing number of layers to solve the task as sequence length grows, a single-layer Dense Linear CDE solves it regardless of length, confirming the expressivity gap.

Conclusion and Future Directions

This work provides a rigorous foundation for the next generation of sequence models. By identifying the Path Signature as the underlying representation, we explain why selective gating is essential for content-based reasoning.

While diagonal architectures are necessary for current hardware efficiency, our findings suggest that the "holy grail" for future research lies in developing efficient channel-mixing strategies. Such strategies could provide the universal approximation benefits of dense matrices without the $O(N^2)$ state-dimension cost, potentially leading to even more powerful and efficient architectures than Mamba.

Summary updated

BibTeX
@inproceedings{cirone2024theoretical,
  author = {Nicola Muca Cirone and Antonio Orvieto and Benjamin Walker and Cristopher Salvi and Terry J. Lyons},
  title = {{Theoretical Foundations of Deep Selective State-Space Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=3SzrqwupUx},
}
Figure