Theoretical Foundations of Deep Selective State-Space Models

Authors: nicola muca cirone
antonio  orvieto
benjamin  walker
cristopher  salvi
terry  lyons
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:39:35

Abstract: Structured state-space models (SSMs) are gaining popularity as effective foundational architectures for sequential data, demonstrating outstanding performance across a diverse set of domains alongside desirable scalability properties. Recent developments show that if the linear recurrence powering SSMs allows for a selectivity mechanism leveraging multiplicative interactions between inputs and hidden states (e.g. Mamba, GLA, Hawk/Griffin, HGRN2), then the resulting architecture can surpass attention-powered foundation models trained on text in both accuracy and efficiency, at scales of billion parameters. In this paper, we give theoretical grounding to the selectivity mechanism, often linked to in-context learning, using tools from Rough Path Theory. We provide a framework for the theoretical analysis of generalized selective SSMs, fully characterizing their expressive power and identifying the gating mechanism as the crucial architectural choice. Our analysis provides a closed-form description of the expressive powers of modern SSMs, such as Mamba, quantifying theoretically the drastic improvement in performance from the previous generation of models, such as S4. Our theory not only motivates the success of modern selective state-space models, but also provides a solid framework to understand the expressive power of future SSM variants. In particular, it suggests cross-channel interactions could play a vital role in future improvements.

Main paper: 
 introduction: 
 Sequence-to-sequence blocks are fundamental components of modern deep learning models for language, images, video, audio, time series, and genomics. For the last five years,attention [Vaswani et al., 2017 , Dosovitskiy et al., 2020] has been the dominant mechanism powering these architectures. However, competitive results have recently been achieved without attention, by using state-space models (SSMs): GPU-efficient linear recurrent sequence-to-sequence blocks stemming from S4 [Gu et al., 2021] . SSMs achieve state-of-the-art results on long-range-reasoning benchmarks [Tay et al., 2020] and show outstanding performance in various domain including vision [Nguyen et al., 2022] , audio [Goel et al., 2022] , biological signals [Gu et al., 2021] , reinforcement learning [Lu et al., 2023] and online learning [Zucchet et al., 2023] . SSMs recently have gained significant interest in the community since their computational complexity scales linearly in sequence length, while attention scales quadratically; moreover, unlike other recurrent mechanisms such as LSTMs [Hochreiter and Schmidhuber, 1997] and GRUs [Cho et al., 2014] , they can be efficiently parallelized on GPUs during training using parallel scans [Martin and Cundy, 2017, Smith et al., 2023] .While standard SSMs were shown to be particularly powerful on signal processing tasks, their computation power is limited: the core sequential mechanism of S4 is equivalent to a convolution (filtering) [Li et al., 2022a] . This represents a drawback in challenging domains such as text and genetics, where the ability to select data efficiently in an input-dependent manner -i.e., perform content-based reasoning -is crucial (see [Wang et al., 2022 , Fu et al., 2022 , Arora et al., 2023] ). Towards reaching this goal with recurrent models, various adaptations of S4 have been proposed in the last few months. Notably, Mamba [Gu and Dao, 2023] implements simple and efficient gating mechanisms on the S4 recurrence, unlocking input selectivity in the memory update. Mamba achieved state-of-the-art performance in various language modeling tasks while greatly improving the inference throughput. Similar ideas can be found in recent developments inspired by attention, such as RWKV [Peng et al., 2023] , RetNet [Sun et al., 2023] , Gateloop [Katsch, 2023] , Gated Linear Attention (GLA) [Yang et al., 2023] , and HGRN2 [Qin et al., 2024] . Very recently, De et al. [2024] surpassed the performance of Mamba with a gated RNN architecture -Griffin -based on an improved version of the LRU [Orvieto et al., 2023a] , and [Feng et al., 2024] introduced minimal versions of GRU and LSTM as gated SSMs.Contributions At the core of the models discussed above is a time-varying dynamical system, where reasoning is performed through an efficient and parallelizable update linear in the hidden state. In this paper, we generalize the structure of such models, drawing a direct link to controlled differential equations (CDEs) [Young, 1936 , Lyons, 1994 , Kidger et al., 2020 , Morrill et al., 2021 , Fermanian et al., 2021 , Salvi et al., 2022 , Hoglund et al., 2023 , Walker et al., 2024] and use tools from rough path theory [Lyons et al., 2007] to study expressivity.SSM basics and S4. Most 1 SSMs [Gu et al., 2021 [Gu et al., , 2022] ] operate independently on input channels. Each time series x i ∈ R L is seen as the result of sampling a latent continuous-time signal X i : [0, 1] → R at multiples of a channel-dependent stepsize ∆ i > 0: X i ∆iℓ := X i (∆ i ℓ) = x i ℓ . In S4, each path X i produces a complex-valued hidden state signal Z i : [0, 1] → C Ni asEQUATIONwhere A i = diag(a i,1 , a i,2 , . . . a i,N ) is channel-specific diagonal N i × N i complex valued matrix and B ∈ C Ni is an input projection shared across input components i ∈ [d] . SSMs are based on a stable discretization of the continuous system above: each input sequence channel x i ∈ R L produces a sequence of hidden states z i = [z i;1 |z i;2 | . . . |z i;L ] ∈ C Ni×L as follows:EQUATIONwhere Āi and Bi are determined by the discretization technique and the channel-dependent stepsize ∆ i . Under the commonly used Zero-Order Hold discretization 2 ,EQUATIONNote from (2) that SSMs at inference time are equivalent to linear recurrent neural networks (RNNs). Yet, learning with gradient descent is performed on the continuous-time variables, unlocking stable signal propagation and alleviating vanishing gradients [Orvieto et al., 2023a, Zucchet and Orvieto, 2024] . Finally, at each channel i, the sequence of hidden states is mapped back to real numbers, and linear projections C i : C Ni → R are performed to produce an output a sequence of tokens y ∈ R d×L with the same dimensions as x: y i ℓ := C i • z i;ℓ To conclude, we point out that the transition matrices A i are often structured, i.e. initialized deterministically through HiPPO theory [Gu et al., 2020] in diagonal form. Common choices [Gu et al., 2022] are a •,n = -1 2 + iπn (S4D-Lin 3 ) and a •,n = -1 2 (S4D-Real). Mamba. As done in practice, let us consider all channels' hidden dimensions N i equal to N . The Selective SSM (S6) powering the Mamba architecture [Gu and Dao, 2023] augments S4 with input-controlled matrices:EQUATIONwhere the most crucial component (see in-context learning argument by Gu and Dao [2023] ) is the dependency of the diagonal matrix Āi (x ℓ ) ∈ R N ×N at timestamp ℓ on all input channels at timestamp ℓ. This makes the operation Āi (x ℓ ) • z i;ℓ-1 effectively a gate. The dependency of Āi : R d → R N ×N on the input is achieved efficiently by letting ∆ i in (3) be computed, at step ℓ, as ∆ i (x ℓ ) where∆ i : R d → R, ∆ i (x) = softplus(α i • x + β i ) ∈ Rwhere • is the scalar product and 4 α i ∈ R d , β i ∈ R. Further, Bi : R d → R N is computed via a, shared between channels, linear map B ∈ R N ×d via Bi (x l ) = (B • x ℓ ) ∆ i (x ℓ ) ∈ R N . Finally, each z i;ℓ ∈ R N is projected to y i ℓ ∈ R via a matrix C i . This step can also be done by means of output gating (C i function of the input), but we avoid this complication here as it can be seen as an architectural component outside the recurrence. Remark 2.1. While each channel evolves separately, the laws of evolution are pointwise determined by all input features: A i and B i can be functions of x ℓ , and not just of x i ℓ . We will discuss this in Sec. 4.3 after presenting our general results.The RG-LRU [De et al., 2024] works similarly, yet processing all input channels at once with a diagonal recurrence. Gateloop [Katsch, 2023] , GLA [Yang et al., 2023] , and HGRN2 [Qin et al., 2024] leverage similar ideas, though they differ in parametrization and gating strategies. 1 The LRU and S5 instead build a single recurrence operating on multidimensional (# channels) inputs. 2 This corresponds to: (i) considering the continuous underlying signal Xt to be piecewise constant, (ii) solving exactly ODE (1) and finally (iii) sampling Zt at the sample times of Xt. Refer to Appendix F.3 i denotes the imaginary unit √ -1, not to be confused with the index i. 4 In practice, Gu and Dao [2023] use a low-rank projection to construct the ∆is. In other words, the matrix [α ⊤ i , α ⊤ 2 , . . . , α ⊤ d ] is low rank. Another distinction that Mamba has compared to S4, is that the Ai matrices controlling the recurrence on channels i = 1, 2, . . . d, is now shared and can be thus referred to as A. 
known properties of (non-linear) recurrences: 
 The expressiveness of standard nonlinear RNNs of the form z ℓ = Aσ(z ℓ-1 ) + Bx ℓ , where σ is a nonlinearity, has been extensively studied since the seminal work of Siegelmann and Sontag [1992] , with recent contributions such as Korsky and Berwick [2019] and Hanson and Raginsky [2020] . In particular, Hanson and Raginsky [2020] proved that wide enough non-linear RNNs can approximate up to vanishing precision non-linear time-homogeneous systems of differential equations driven by input paths. The argument used here is based on the celebrated Barron's theorem [Barron, 1993] for approximation of continuous functions with neural networks with one hidden layer. Indeed, note that non-linear RNNs are recurrent perceptrons with one hidden layer, acting both on the state and the input [Tallec and Ollivier, 2018] . Instead, (selective) SSMs such as S4 and Mamba have transition map which is linear in the state -unlocking parallelization [Smith et al., 2023, Gu and Dao, 2023] . In the context of linear RNNs and non-selective SSMs, many results (classic and new) exist that characterize expressivity. Li et al. [2022b] showed that linear RNNs (i.e. S4-like recurrences) can approximate arbitrary convolution filters in the width limit. Further, Hanson and Raginsky [2019] proved that stacking exponentially (in the sequence length) many temporal convolution filters, chained together with ReLU activations, leads to approximation of arbitrary non-linear filters. Recent works [Orvieto et al., 2023b, Wang and Xue, 2023] prove the universality of linear recurrences (one layer) when equipped with a fixed (timestamp independent) point-wise MLP acting across the recurrence output, with intriguing connections to Volterra series [Boyd and Chua, 1985] . Mamba (alongside with gated linear attention variants e.g. Yang et al. [2023] ) falls neither in the linear RNN nor the nonlinear RNN setting: its recurrence is linear on the hidden state (can be parallelized) but unlike S4, it is not linear time-invariant as the input controls the recurrence eigenvalues. In this paper, we are interested in this hybrid setting. It is worth noting that some work exploring Mamba's expressiveness has already been performed to study some interesting toy tasks [Jelassi et al., 2024] and to understand its limitation using the framework of formal language theory [Merrill et al., 2024] . Compared to these works, which outline interesting failure cases, this paper studies a more general class of models, allowing to identify how architectural choices impact expressivity. 
ssms as linear cdes: 
 The crucial component that unlocks in-context learning and selectivity in modern SSMs is the inputdependent state-to-state transition matrix [Gu and Dao, 2023] , gating the hidden state and thus allowing the system to filter out unnecessary context and remember relevant information indefinitely.At the core of most modern SSMs is a a recurrence which is linear in the hidden state, but potentially non-linear in the input. This class includes many recent SSM-based or inspired models. Crucially, it does not contain classical RNNs, LSTMs, and GRUs -for which results are known and rely on the non-linear dependence of the hidden state in the update rule (Sec. 2.2). As we will shortly see, structure and features of (selective) SSMs can be studied within a unified, convenient, continuous-time framework (Linear Controlled Differential Equations) . This allows to answer the following question: "What is the most one can achieve using a recurrence which is linear in the hidden state and potentially non-linear in the input?"According to their continuous-time formulation, SSMs process input data sampled from a continuous path X : [0, 1] → R d , where d is the number of channels. By X i t we denote the input channel i, evaluated at time t ∈ [0, 1]. More formally, we consider input trajectories in the separable Banach spaceX = C 1,0 ([0, 1]; R d ) of absolutely continuous R d dimensional paths. In this space, one can write X = t 0 Ẋs ds since X ∈ L 1 ([0, 1]; R d ); and the norm is ∥X∥ 1;[0,1] := 1 0 | Ẋs | ds.To model gates (see Mamba in (4)), we introduce two maps transforming the path X, which output trajectories ω X , ξ X living in potentially higher dimensions:d ω and d ξ ω : X → C 1,0 ([0, 1]; R dω ), ξ : X → C 1,0 ([0, 1]; R d ξ )where we used the shorthand notation ω X := ω(X), ξ X = ξ(X). Akin the notation for the i-the channel of X (i.e. X i ), we denote by ω X,i the i-th channel in ω X . The role of the ξ, ω functions -which we denote gating functions -will be clear very soon. Definition 3.1 (Linear CDE). Fix N ∈ N (hidden-state dimension), matrices A 1 , ..., A dω ∈ R N ×N and B ∈ R N ×d ξ . The hidden state Z X := Z(X) is computed by the Linear CDE through a linear (in the hidden state) differential equation driven by ω, ξ -functions of the input path:dZ X t = dω i=1 A i Z X t dω X,i t + Bdξ X t , Z X 0 = Z 0 ∈ R N (5)We show that both S4 and Mamba can be written in continuous-time as systems of parallel Linear CDEs. The key ingredient setting the two models apart is the choice of drivers ω and ξ. As in the preceding section, we will use the bold tensor notation to stress the parallel nature of these CDEs.• S4 is a Linear CDE: It is sufficient to consider the setting d = 1, N = N i . The S4 model [Gu et al., 2021] in this case isdZ t = A • Z t dt + B (X t dt), where A ∈ R N ×N is diagonal.This can be written as a Linear CDE withEQUATIONsince dω X t = dt and dξ X t = X t dt. As the reader can promptly notice, here ω X is not a function of X -this will have a crucial role in expressivity (see Sec. 4.2).• Mamba is a Linear CDE: Recall from (4) that the recurrence inside Mamba (i.e. S6), can be written asz i;ℓ = Āi (x ℓ ) • z i;ℓ-1 + Bi (x ℓ )x i ℓ where for generic timestamp features x ∈ R d , we have Āi (x) = exp(∆ i (x)A i ), Bi (x) ≈ (B•x)∆ i (x) and ∆ i (x) = softplus(α i •x+β i ).Let us introduce a parameter δ > 0, and consider αi = α i /δ, βi = β i /δ. Let us further approximate the softplus function with a ReLU (σ(x) = ReLU(x) ≃ log(1 + e x )) to obtain ∆ i (x) = σ(δ αi • x + δ βi ) = σ( αi • x + βi )δ. Therefore, as δ → 0, one has Āi (x) = exp(∆ i (x)A i ) = exp(σ(α i • x + βi )δA i ) δ→0 → 1 + σ(α i • x + βi )δA i , leading to the recurrence z i;ℓ = z i;ℓ-1 + A i • z i;ℓ-1 σ(α i • x ℓ + βi )δ + (B • x ℓ ) x i ℓ σ(α i • x ℓ + βi )δ.As we show formally in Appendix F, δ plays the role of the differential dt. The equation above is the Euler discretization of the differential equationR N ∋ dZ X i;t = A i • Z X i;t σ(α i • X t + βi )dt + (B • X t ) X i t σ(α i • X t + βi )dtwhere for each i, Z X i : [0, 1] → R N . These are Linear CDEs with carefully chosen ω and ξ:ω X i;t = t 0 σ(α i • X s + βi )ds ∈ R, ξ X i;t = t 0 X s X i s σ( αi • X s + βi )ds ∈ R d .Note that here the ξ i depend on higher powers of X's dimensions, an intriguing feature connected to input gating [Hochreiter and Schmidhuber, 1997, Cho et al., 2014] . Remark 3.2 (Are hidden state components recurrently mixed?). In the Linear CDE defined bydZ X t = [ dω j=1 A j dω X,j t ] • Z X t + B • dξ Xt channels of the transformed input path ω X are mixed in a linear way in the recurrent step and stored in a shared hidden state Z X . This allows our framework to be more general compared to S4 and Mamba, where each channel of the input is processed individually, and hidden states are later combined. We know already from Merrill et al. [2024] that this distinction between hidden state mixing strategies is crucial for expressivity. Our discussion in Sec. 4.3 provides an in-depth look at the effects of separate channel processing, achieved in our framework by choosing the A i s to be diagonal and non-zero only around a channel-specific portion.dZ X t = dω i=1 A i Z X t dω X,i t + Bdξ X t Z X 0 = CX 0 ∈ R N (29)is given, using the notation A Ij := A j A I , byZ X t = d0 i=1 I∈W dω A I C i X i 0 Sig(ω X ) I 0,t + d ξ j=1 I∈W dω A I B j t 0 Sig(ω X ) I s,t dξ X,j s ∈ R N (30) Notice here A I C i , A I B j ∈ R N and X i 0 Sig(ω X ) I 0,t , t 0 Sig(ω X ) I s,t dξ X,j s ∈ R.Proof. Just apply Theorems (E.2) and (E.6) of Appendix E.Remark B.5. A property highlighted by the previous result is the interpretability of these models.After training the CDEs one can compute the matrix multiplications and observe which entries of the signature the model chooses to take into consideration, to attend. 
expressivity of linear cdes: 
 Having established the connection between SSMs and Linear CDEs, we now provide an explicit characterization of the uniform closure of Linear CDEs, i.e. a description of all the functions from compact subsets of X to R that can be uniformly approximated at an arbitrary precision by a Linear CDE of the form given in (5).The proof of the main theorem we present here (Thm. 4.1) is involved and requires tools from Rough Path theory; we provide a full derivation in Appendix B with tools reviewed in the self contained Appendix E, as well as an introduction to the Signature approach in Section 4.5 and Appendix A. While familiarity with these concepts is not necessary to grasp the main results as stated, it is essential for a thorough comprehension.In this subsection, Linear CDEs are analyzed in full generality -i.e., in the dense setting. While for efficiency reasons non-diagonal recurrences are rarely used in SSMs, our results allow to precisely characterize the Linear CDE hypothesis class (i.e. the closure), thus to the answer the question "What is the most we can achieve from recurrences which are linear in the hidden state?". We show that Linear CDEs can model, at fixed time t, arbitrary continuous functions of the whole seen inputs. Of course, understanding the diagonal setting with separate channel processing is of utmost importance in the current research landscape. The tools and results in this subsection allow us to directly discuss this case and compare it to the dense setting -this is presented in Sec. 4.3.In this section, for any path γ ∈ C 1,0 ([0, 1], R dγ ) and any sub-interval [s, t] ⊂ [0, 1], we denote byγ [s,t] ∈ C 1,0 ([0, 1], R dγ ) the path γ [s,t] (u) = γ t∧u -γ s∧u , where a ∧ b = min(a, b). Theorem 4.1. Let X ⊂ C 1,0 ([0, 1], R d) be compact and choose continuous gating functions ω, ξ such that 5 ω X,1 t = t and ω X,2 t = t 2 . Consider the Linear CDE model (5). Let Ψ, Φ be generic continuous functions from paths to real vectors:Ψ : C 1,0 ([0, 1], R dω ) → R, Φ : C 1,0 ([0, 1], R dω ) → R d ξ .There exist dense matrices A 1 , ..., A dω , B such that, after a fixed final linear projectionEQUATION)where • is the scalar product. Moreover Y X t = CZ X t is itself of form (7).In Theorem 4.1, the A i are dense matrices constructed ad hoc for the proof. We show next that, with high probability, random Glorot-initialized matrices [LeCun et al., 2012] provide enough expressivity -one only has to choose the appropriate matrix C. This is a similar mechanism to the paradigm advocated in reservoir computing [Lukoveviius and Jaeger, 2009 , Cuchiero et al., 2021a , Compagnoni et al., 2023] . The next result, however, is novel and of independent interest in Rough Path Theory.Theorem 4.2. Under the hypothesis of Theorem 4.1, pick[A j ] n,n ′ iid ∼ N (0, 1 N ) and [Z 0 ] n , [B] n,jiid ∼ N (0, 1). For any functional F : X × [0, 1] → R of the form (7) and ϵ > 0 it holds that limN →∞ P ∃C ∈ R 1×N such that sup (X,t)∈X×[0,1] |F (X, t) -CZ X t | ≤ ϵ = 1.Roughly speaking, our result shows that dense Linear CDEs have drastically superior expressive power compared to dense linear RNNs. This contrast is to be attributed completely to the gate ω.Warmup -Linear RNNs. Thm 4.1 can be seen as a generalization of the Universal Approximation for Linear RNNs presented by Li et al. [2022b][Thm. 7] for generic gates ω, ξ. In fact, their setting is restricted to ω X t = t and ξ X t = t 0 X s ds. This is also the case for S4, S5 and the LRU -which are linear RNNs at test time. Then the only information contained in ω [s,t] is the increment t -s so that family (7) reduces to (X, t) → ψ(t) + t 0 ϕ(t -s) • X s ds . This is, fundamentally, the set of linear filters on the input. As shown in Gu and Dao [2023] , such processing is unable to adapt information flow in-context. 5 These assumptions are of technical nature and can be relaxed at the cost of talking about tree-like equivalence of paths cf. Hambly and Lyons [2010] . Intuitively ω X,1 t = t ensures general X-uniformity while ω X,2 t = t 2 ensures [0, 1]-uniformity.How does a Linear CDE process inputs? Take without loss in generality6 ω X t = X t . The first term in the function class {Ψ(X[0,t] ) + t 0 Φ(X [s,t] ) • dξ Xs } is already enough to establish that the output CZ X t is a nonlinear function of all previously seen inputs X [0,t] -ξ could be set to zero. The term Ψ(X [0,t] ) is however non-trivial only in the Z 0 ̸ = 0 case (cf. Appendix B): picking ξ X t = 0 ∈ R N for all t indeed leads to dZ X t = dω i=1 A i dω X,i t Z X t , which is evolving only if Z 0 ̸ = 0. While this setting is interesting and suggests a clear direction for future research, a case more similar to Mamba (see Sec. 4.3) is Z 0 = 0 and ξ X t = t 0 X s ds. Here, we can approximate arbitrarily well outputs of the form(X, t) → t 0 Φ(X [s,t] ) • X s ds (8)where Φ is any continuous function of the input path, restricted to the portion [s, t] . This clearly shows that dense Linear CDEs are capable of context-dependent filtering: the output is again a linear combination of previously seen inputs, but weights are not predetermined as in Linear RNNs (S4)they are a function of the context. A similar yet less powerful processing is happening in the diagonal setting, which we explore next.The choice of diagonal weights considerably restricts the family of learnable functionals. Intuitively the diagonal choice corresponds to running N independent 1-dimensional systems, this absence of mixing between the different hidden dimensions is the main culprit for the loss of expressivity. The full power can however be recovered by chaining the diagonal schemes (cf. Prop. 4.5). Theorem 4.3 (Diagonal Case). If the matrices A 1 , ..., A dω are constrained to be diagonal, the requirements ω X,1 t = t, ω X,2 t = t 2 can be dropped and the closure reduces to(X, t) → ψ(ω X t ) + t 0 ϕ(ω X t -ω X s ) • dξ X s (9)for continuous ψ : R dω → R and ϕ : R dω → R d ξ .Compared to the dense setting, the effect of diagonality is pretty clear. Let us again assume ω X t = X t and ξ X t = t 0 X s ds for simplicity. While t 0 Φ(X [s,t] ) • X s ds unlocks filtering based on the entire trajectory X [s,t] , the diagonal case term t 0 ϕ(X t -X s ) • X s ds indicates that filtering coefficients can only be chosen by comparing two elements of the (potentially transformed through ω) input sequence. While this precise and tight result reveals a pitfall of diagonal recurrence, it also brings about an interesting connection to attention [Vaswani et al., 2017] , where only a finite number of tokens are compared at each layer. While a smart choice of gating functions ω, ξ can improve on the learned nonlinear filtering strategy (e.g. based on filtered input versions as in Mamba), our theory reveals the fundamental processing discrepancy compared to the dense setting, a property which was also explored in recent literature [Merrill et al., 2024] using different tools.As already noted, on top of diagonality, recent SSMs also mix inputs as linear combinations of independently run channel-dependent systems. This slightly modifies the function class as: Corollary 4.4 (Mamba Case). In the Mamba setting, the closure reduces to(X, t) → dω i=1 ψ i (ω X,i t ) + dω i=1 t 0 ϕ i (ω X,i t -ω X,i s ) dξ X,i s (10)for continuous ψ i : R → R and ϕ i : R → R.Fortunately it is possible to re-gain expressivity without sacrificing the computational advantages of diagonal schemes through chaining. This means driving a new Linear CDE by the solution of a previous Linear CDE, and repeating this procedure K times (cf. Appendix C).Proposition 4.5. Assume a compact X ⊂ C 1,0 ([0, 1]; R d ). For any functional F : X × [0, 1] → R of the form (7) and ϵ > 0 there exists a sequence of linear mapsW k ∈ R M k ×N k , diagonal weights A (k) iand B (k) for the following family of chained diagonal Linear CDEsEQUATIONsuch that eventually, as k → ∞, there existsC k ∈ R 1×N k with sup (X,t)∈X×[0,1] |F (X, t) -C k Z k,X t | ≤ ϵ.Intuitively, with chaining one recovers the mixing between the input dimensions which was so important for the expressiveness of dense Linear CDEs. This does not happen immediately but crucially depends on the length of the chain, the result in fact tells us that the recovery holds for long enough chains (and big enough hidden states). In Appendix C.2.1 we argue that the same conclusions hold also in the Mamba setting with non-linear gates.In this section, we introduce the primary tools, objects, and techniques from Rough Path theory used in our proofs. Given their technical nature, we have chosen to present the main results of this paper without explicit reference to them, allowing readers to understand the work without needing specialized knowledge. For those interested in the finer details, here we provide a brief overview and refer to Appendix A for additional details and references.To study the expressivity of Linear CDEs it is convenient to introduce the so-called signature transform [Lyons et al., 2007 , Kidger et al., 2019 , Fermanian et al., 2023] , a classical path-transform from stochastic analysis. The main reason for doing so is that, as a simple consequence of the Stone-Weirestrass theorem, linear functionals on the signature provide the essential building blocks (analogous to monomials on Euclidean spaces) to approximate continuous functions on path space.Consider a path γ ∈ C 1,0 ([0, 1]; R dγ ) and define as W dγ the set of words (i.e. ordered sequences) in {1, . . . , d γ }7 . The signature transform is the following infinite collection of scalar iterated integrals Sig(γ) s,t := Sig(γ)(I) s,t I∈W dγ , Sig(γ) (I) s,t := s<u1<...<un<t γ(i1) u1 ... γ(in) un du 1 ...du n .A classical result from rough path theory states that a Linear CDE can be expanded explicitly as an (infinite) linear combination of terms in the signature of the driving path. Proposition 4.6. For any choice of matrices A 1 , ..., A dω and B, the unique solution Linear CDE (5) is, using the notation A I := A in ...A i1 , given byEQUATION)Notice that the previous result does not rely on any assumptions on the nature of Z 0 , A i , and B; for any such choice the result is a time-independent linear map on a feature vector T (X) 0,t := (Sig(ω X )(I) 0,t , t 0 Sig(ω X ) (I) s,t dξ X,i s ) (I,i), where the index (I, i) runs over W dω × {1, ..., d ξ }. The main takeaway is that any linear projection Y X t := CZ X t is written as an (infinite) linear combination of the terms in T (X) 0,t . This means that the expressive power of such schemes is almost completely determined by the gate ω, which is the only path of which high order information is taken into consideration through its full signature. It is evident then that the classical choice of input-independent ω (i.e. ω X t = t) then precludes the use of higher order statistics of X. 
path-to-path learning: 
 In Section 4, we showed that Linear CDEs (and chained Mamba) can model, at fixed time t, arbitrary continuous functions of the whole seen inputs. Assume wanting to learn a functional of type(X, t) → Ψ t (ω X [0,t]) where the map Ψ t is changing with time as well, this is an example of a general continuous path-to-path model. Note in particular how this is a more general family than the one of Theorem 4.1, where the maps Ψ and Φ are fixed once and for all. Here, we discuss how passing the hidden state through a multi-layer perceptron (MLP), instead of just a linear readout (matrix C), allows us to efficiently approximate this richer class, interpolating between the Ψ t s.As shown in Orvieto et al. [2023b] , classical SSMs followed by an MLP are universal on sequences. Given their nature of input-independent convolutions, their construction defers all reasoning to the MLP acting on the output: in S4, the SSM is simply providing an input compression -with no added reasoning. In our setting, we instead characterized the processing power of input-controlled (dense or diagonal) SSMs precisely, showing how it greatly surpasses linear filtering. For this reason, the computational burden for an MLP action on a general Linear CDE would be greatly diminished and its actual function reduced to an interpolation of the maps Ψ t . We defer the proof to Appendix D. Proposition 5.1. Fix a compact set K ⊆ X and continuous ω, ξ with ω X,1 t ≡ t. Then for all ϵ > 0 and all causal8 continuous mappingEQUATION)Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The code to generate the data used and to run the experiments are included in the supplementary material alongside a README explaining how to run the experiments.Guidelines:• The answer NA means that paper does not include experiments requiring code. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 6. Experimental Setting/Details Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: Details can be found in the section titled empirical validation, with additional details for reproducing the results included in the supplementary material.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
empirical validation: 
 Code to reproduce all of our experiments can be found at:https://github.com/Benjamin-Walker/selective-ssms-and-linear-cdesDatasets. The first task is based on a dataset from Walker et al. [2024] where the aim is to predict terms in the anti-symmetric part of the input path's signature. The dataset's objective aligns with the proofs of Theorem 4.1 and 4.2, which characterise the closure using the path's signature. We created two datasets with dimensions 2 and 3 respectively. The increment in each channel at each step is an integer-rounded sample from a standard Normal distribution. The 2D dataset's target is an area integral1 0 v 0 dX 1 u dX 2 v, and the 3D dataset's target is a volume integral1 0 w 0 v 0 dX 1 u dX 2 v dX 3 w .The second task is the A 5 benchmark from Merrill et al. [2024] . It tests models on state-tracking, a crucial ability for tasks involving permutation composition, such as chess. The dataset comprises sequences from the group of even permutations on five elements, A 5 , where the target is the cumulative composition of all preceding permutations. Datasets vary by sequence length, ranging from 3 to 20.Models. On the anti-symmetric signature task, we considered seven models: (i-ii) S4 or Mamba recurrence with linear readout, (iii-iv) two stacked S4 or Mamba recurrences with a linear mixing layer in-between and a linear readout, (v-vi) two stacked S4 or Mamba recurrences with a linear mixing layer + ReLU in-between, and a linear readout, (vii) a linear CDE with gates ω X t = ξ X t = (t, X t ) and a linear readout. All state space models have trainable matrices in their recurrences, whereas the linear CDE is using fixed matrices. All models use a hidden dimension of 256, with the state space models using a state dimension of 256. The state space models are trained using gradient descent with a batch size of 32 and Adam with a learning rate of 10 -4 . The output from the linear CDE's recurrence is obtained using the Tsit5 adaptive ODE solver, with an absolute and relative tolerance of 10 -2 . The linear CDEs linear readout is optimised via ordinary least squares.On the A 5 benchmark, we consider five models: a linear CDE, a RNN, a transformer, and S4 and Mamba recurrences. All models use an embedding layer followed by a series of blocks that combine the sequence-to-sequence model, linear mixing with a non-linear activation function, layer normalization, and a residual connection. Furthermore, all models have trainable matrices in their recurrences and are trained using batch gradient descent with a batch size of 32 and AdamW with a weight decay of 0.01. The RNN, transformer, S4, and Mamba use a hidden dimension of 1024, with the state space models using a state dimension of 64 and the transformer using 64 heads. Due to memory constraints, the linear CDE uses a hidden dimension of 256. Note that the IDS4 recurrence introduced by Merrill et al. [2024] corresponds directly to a linear CDE with dense transition matrices, hence we did not include the model as a baseline. Results. Results on the anti-symmetric signature prediction task (Fig. 1 ) empirically demonstrate a number of the theoretical results presented in this paper. Firstly, as discussed in Sec. 4.2, recurrences which are linear in the input, such as S4, require a non-linearity inbetween the layers to perform well. Furthermore, as stated in Thm. 4.3 and Prop. 4.5, even if the recurrence is non-linear in the input, such as Mamba, the expressivity of models with diagonal matrices is improved by stacking. Additionally, the inclusion of the non-linearity inbetween the Mamba layers does not improve performance, as the recurrences themselves are expressive enough. Finally, as stated in Thm. 4.2, dense matrices can achieve strong expressivity with random initialization, no stacking, and only a trainable linear readout. The figure shows that the number of blocks S4, Mamba, and the transformer require to achieve greater than 90% validation accuracy grows with the sequence length. In fact, given our model architecture, none of these models could achieve greater than 90% validation accuracy for sequences of length twenty9 . On the other hand, the RNN and Linear CDE are able to achieve greater than 90% validation accuracy for all lengths considered using only one block. These empirical results further validate Thm. 4.3 and Prop. 4.5: there exists a gap in expressivity between diagonal and dense transition matrices, and stacking is required to recover the expressivity. Furthermore, they provide empirical evidence that even for simple state-tracking problems, the number of blocks required can grow quickly with sequence length. 
conclusions: 
 This paper explores Linear CDEs, a model family that extends both classical and modern SSM architectures, including recent gated RNNs. Using Rough Paths theory, we have characterized their uniform closure, generalizing the results of Li et al. [2022b] for linear RNNs. We precisely identified the advantages of input-controlled transition dynamics, which allow you to capture highorder statistics of the input as opposed to just the linear ones extracted by convolutions. While dense models reach full expressiveness, imposing diagonality (e.g. Mamba) weakens the model capabilities. This is in direct contrast to S4, where dense and diagonal settings share the same closure. Our analysis lays the theoretical foundation for analyzing the expressive power of future SSM variants and hints at non-diagonality as a potential source of improvements. We believe that light and efficient channel mixing in the recurrent block might already unlock the modeling of higher-order statistics.Limitations. The current framework examines expressivity from a continuous-time perspective with real-valued inputs. The RNN literature suggests that finite precision often plays a significant role in practice, making it an interesting direction for future exploration. Additionally, although dense transition matrices are shown to be theoretically and empirically more expressive than diagonal ones, their increased computational cost makes them impractical for large-scale models.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [Yes] Justification: Details included in the empirical validation section. Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: This is a theoretical work. We provide information sufficient for the reproduction of empirical results.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This is a theoretical work.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Answer: [NA] Justification: This is a theoretical work, not involving crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: This initial section of the Appendix is devoted to a brief introduction to the topic of Signature Transform. For a more in-depth account we refer the interested reader to Cass and Salvi [2024] .In the simplest setting of smooth paths a CDE is a differential equation of formdZ t dt = F dX t dt , Z t , Z 0 ∈ R nwhere X : [0, 1] → R d is a known smooth path to which we refer as control, Z 0 the known initial condition and Z : [0, 1] → R n the unknown solution.The natural generalization is the following: assume to have two spacesR dx and R dz , X ∈ C 1 ([0, 1]; R dx ), Z ∈ C 1 ([0, 1]; R dz ), F : R dz → L(R dx , R dz ) and Z 0 ∈ R dz .We say that (Z, X, F, Z 0 ) satisfy the CDEdZ t = F (Z t )dX t , Z 0 ∈ R dz whenever Z t = Z 0 + t 0 F (Z s )dX sThe theory of Rough Paths has its origins in the study of such types of differential equations and provides a theoretical framework to define and work in rough settings i.e. when X is not kust BV but even α-Hölder for α ∈ (0, 1) cf. Friz and Victoir [2010] .Assume thus to have the CDEdZ t = dx i=1 V i (Z t )dX i t , Z 0 ∈ R dzfor sufficiently regular vector fields V i and X ∈ C 1 ([0, 1]; R dx ). Given a smooth f : R n → R, by the change of variable formula (i.e. fundamental theorem of calculus) we havef (Z t ) = f (Z 0 ) + dx i=1 t 0 V i f (Z s )dX i s where V i f (z) := df y [V i (z)].Iterating this procedure on the V i f s, i.e. substituting in the previous equation the analogously obtained equalityV i f (Z s ) = V i f (Z 0 ) + dx j=1 s 0 V j (V i f )(Z u )dX j u ,we getf (Z t ) = f (Z 0 ) + d i=1 V i f (Z 0 ) t 0 dX i s + d i,j=1 t 0 s 0 V j V i f (Z u )dX j u dX i sKeeping with this procedure for N steps we getf (Z t ) = f (Z 0 ) + N k=1 |I|=k V I f (Z 0 ) • • • s<u1<•••<u k <t dX i1 u1 • • • dX i k u k + R N (t)where I = (i 1 , . . . , i k ) runs through the multi-indices,V I f := V i1 V i2 . . . V i k f and R N (t) := |J|=k+1 • • • s<u1<•••<u k+1 <t V J f (Z u1 )dX j1 u1 • • • dX j k+1 u k+1As one can imagine, under reasonable regularity assumptions, the remainder goes to 0 as N → ∞ and at the limitf (Z t ) = f (Z 0 ) + ∞ k=1 |I|=k V I f (Z 0 ) • • • s<u1<•••<u k <t dX i1 u1 • • • dX i k u kThis is a remarkable result: to know the solution Z t to the original CDE it suffices to know the quantities V I f for all multi-indices and f in the coordinate maps, together with the iterated integralsSig(X) I s,t := • • • s<u1<•••<u k <t dX i1 u1 • • • dX i k u k .This observation is at the core of Rough Path Analysis, the theory can in a sense be considered an extreme development of it. The collection of iterated integrals, the Signature, will be the main for our analysis.In Appendix E we expand and make rigorous the arguments of this section in the case of affine vector fields.Denote by(R d ) ⊗n := R d ⊗ • • • ⊗ R d the tensor product of n copies R d , set (R d ) ⊗0 := R. Let T (R d ) := ∞ k=0 (R d) ⊗k be the tensor algebra equipped with sum and tensor product. Definition A.1. Let {e 1 , . . . , e d } be the canonical basis of R d , then{e i1 ⊗ • • • ⊗ e i k : (i 1 , . . . , i k ) ∈ [d] k } is a basis of (R d ) ⊗k . We equip (R d ) ⊗k with the inner product ⟨•, •⟩ (R d ) ⊗k defined on basis elements as ⟨e i1 ⊗ • • • ⊗ e i k , e j1 ⊗ • • • ⊗ e j k ⟩ (R d ) ⊗k = δ (j1,...,j k ) (i1,...,i k )We extend this product to T (R d ) by⟨A, B⟩ T (R d ) := ∞ k=0 ⟨a k , b k ⟩ (R d ) ⊗kwhere A = (a 0 , a 1 , . . . ) and B = (b 0 , b 1 , . . . )A, B ∈ T (R d ) we have ⟨A ⊗ e i , B ⊗ e j ⟩ T (R d ) = ⟨A, B⟩ T (R d ) ⟨e i , e j ⟩ R d ,we refer to this as to the coproduct property. Definition A.2 (Infinite Tensor Algebra). The infinite tensor algebra is defined as the spaceT ((R d )) := ∞ k=0 (R d) ⊗k equipped with the operations + and ⊗ which act in the natural algebraic way; its elements are called tensor series.It is easily seen that (T ((R d )), +, ⊗) is an algebra with unit 1 = (1, 0, 0, • • • ) and we can endow it with a natural product which inherits the coproduct property.Another point of view could be taken on the definitions of these spaces, one that we will prefer later on. If we define W d to be the set of words in d letters thenT ((R d )) ∼ R W d , T (R d )is the subset of such functions with finite support and⟨A, B⟩ T (R d ) = I∈W d A I B I = ∞ k=0 |I|=k A I B Iwhere |I| is the length of the word I. The empty word, the only one with length 0, is denoted by () and corresponds to the basis element of (R d ) ⊗0 . In this view the tensor product coincides with concatenation of words accordingly distributed and the closure of T (R d ) with respect to its product is just the l 2 space l 2 (W d ).Definition A.3 (Signature). Given γ ∈ C 1,0 ([0, 1]; R d ) and s, t ∈ [0, 1] s.t. s ≤ t, the signature Sig(γ) s,t ∈ T ((R d )) of the path γ over [s, t] is defined as Sig(γ) s,t := (1, s<u1<t dγ u1 , • • • , • • • s<u1<•••<u k <t dγ u1 ⊗ • • • ⊗ dγ u k , • • • ) 10 (14)Equivalently Sig(γ) s,t is that element of l 2 (W d ) defined recursively on words as Sig(γ) ()EQUATIONHere we present some notable results of which we will make use through the paper. We omit the proofs if they can be easily found in the suggested references.The first result is about bounding the norm of Signature entries:EQUATIONThe most important fact about Signature is that it acts as the basis for a Taylor expansion in path space. In fact just as finite linear combinations of monomials are dense in the continuous functions with a compact input set, finite linear combinations of Signature entries are dense in continuous functions from compact path-spaces: Theorem A.5 (Universal Approximation Fermanian [2020] ). Fix K ⊂ C 1,0 ([0, 1]; R d+1 ) compact such that for any γ ∈ K it holds γ 1 t = t. For any F ∈ C 0 (K; R) and ϵ > 0 there is an integerEQUATION)for some finite sequence (α I ) |I|≤N of real numbers. Remark A.6. There is no magic in this result, it is just an application of Stone-Weiestrass enabled by the rich algebraic structure of iterated integrals, studied originally in Chen [1958] .We will need to restrict some paths to sub-intervals of [0, 1] in such a way to still be able to consider them meaningfully as elements of C 1,0 ([0, 1]; R d ), this is done in the following way:Definition A.7. Given any path γ ∈ C 1,0 ([0, 1]; R d ) we define its restriction on a sub-interval [s, t] ⊆ [0, 1] as the path γ [s,t] ∈ C 1,0 ([0, 1]; R d ) with values γ [s,t] (r) :=    0 if r < s γ r -γ s if s ≤ r ≤ t γ t -γ s if r > t (18)This definition is such that the following important equation holdsEQUATIONWith the right augmentation of the paths one can see that the Signature distinguishes between different sections of paths, this will be crucial for some of the original results presented in this work.EQUATION)Proof. The if part is follows from Sig(γ) s,t = Sig(γ [s,t] ) 0,1 . For the only if part, If s = s ′ and t = t ′ the statement holds; this is because if the signatures over the time interval [s, t] of two time-augmented paths are equal, then the two paths must be equal on [s, t] . We now show that augmenting the path with t 2 and imposing equality of signatures, implies s = s ′ and t = t ′ , which will in turn allow us to conclude the proof by the previous remark. Assume Sig(ω) s,t = Sig(γ) s ′ ,t ′ , in particular we must haveEQUATIONwhich reduces to the systemt 2 -s 2 = (t ′ ) 2 -(s ′ ) 2 t -s = t ′ -s ′ t + s = t ′ + s ′ t -s = t ′ -s ′ 2t = 2t ′ 2s = 2s ′Hence it must be true that t = t ′ and s = s ′ .In the body of the paper we have presented the main results with the simplified assumption of Z X 0 = 0 or at best Z X 0 = Z 0 i.e. with an initial value independent from the input. In this appendix we will carry on the proofs in a more general setting in which Z X 0 is allowed to be input-dependent, as previously discussed the choice of initial value is, in contrast to the classical setting, meaningful inasmuch it allows to approximate linear maps on the signature of ω X [0,1] . In order to do so we have to introduce a new gate, the initial value gate, in the form of a mapEQUATION)Despite the notation, there is no reason why (X) 0 should be the initial value of the path X, one should think of this map as the one summarizing the data which still matters for the task but which does not have a time-series nature.To recapitulate, the general setting of our models is the following: a topological input space space X,(•) 0 : X → R d0 , ((•) 0 -gate) ω : X → C 1,0 ([0, 1]; R dω ), (ω-gate) ξ : X → C 1,0 ([0, 1]; R d ξ ). (ξ-gate)where all the gates are continuous functions on X. The space X does not have to be a space of paths, a topological structure suffices, as long as the gates (•) 0 , ω, ξ are well defined and continuous. Remark B.1. Typical examples for the choice of gates are X space of paths and(X) 0 = 0 ω X t = t ξ X t = t 0 X s ds (S4) (X) 0 = 0 ω X t = t 0 sof tplus(αX s + β)ds ξ X t = t 0 sof tplus(αX s + β)X s ds (Mamba)Then the main object of study, "gated" Linear CDEs, are defined as: Definition B.2. Fix gates (•) 0 , ω, ξ as above, N ∈ N, matrices {A i } i=1,...,dω(A i ∈ R N ×N ), B ∈ R N ×d ξ , C ∈ R N ×d0 .The corresponding Linear CDE is the functionalEQUATIONHere we present the unified expressivity result in its most general form:Theorem B.3. For any compact set K ⊆ X and continuous gates (•) 0 , ω, ξ with ω X,1 t ≡ t and ω X,2 t ≡ t 2 . For any ϵ > 0 and anyEQUATION)whereEQUATIONMoreover generic parameters suffice with high probability in the sense that under LeCun initialization[A i ] n,j iid ∼ N (0, 1 N ) C n,j , B n,j iid ∼ N (0, 1)the following holds:lim N →∞ P ∃v ∈ R N : (27) holds = 1If the A i s are constrained to be diagonal, as often is the case in practice, the requirements ω X,1 t ≡ t, ω X,2 t ≡ t 2 can be dropped and the existence result only holds withEQUATION)for ψ ∈ C 0 (R dω ; R d0 ) and ϕ ∈ C 0 (R dω ; R d ξ ).Moreover in both the dense and diagonal cases the "reverse" also holds in the sense that, given any choice of matrices A i , B, C there is an ϵ-close map F in the corresponding family.As one can see the theorem is composed of different sub-results, which we believe are better understood separately from each other. The proof will thus be split in the following steps:1. Using the theory developed in Appendix E we see how linear functions on the Z t s can be seen as linear functions on certain terms of the Signature Transform. 2. Such terms define a feature map T (X) 0,t which generates a Reproducing Kernel Hilbert Space H (•)0,ω,η t. This abstract space acts as an upper bound on expressivity: linear functions on Z t always belong to its closure (in uniform norm), independently of dimension and weights chosen, hence they cannot reach what functions in H (•)0,ω,η t can't approximate. The expression in ( 30) is a linear map on a feature vector given, at time t, byEQUATIONThis feature vector can be understood as a tensor in the following way:Definition B.6. Let W d0,dω,d ξ be the set of words in the alphabet A d0,dω,d ξ := {e i } i=1,...,d0 ∪ {ϵ ξ j } j=1,...,d ξ ∪ {ϵ ω k } k=1,...,dω Fixed the gates (•) 0 , ω, ξ we define T (X) : [0, 1] → l 2 (W d0,dω,d ξ ) ⊆ T ((A d0,dω,d ξ )) as the unique solution to:T (X) 0,t = d i=1 X i 0 e i + d ξ j=1 ξ X,j t ϵ ξ j + dω k=1 t 0 T (X) 0,s dω X,k s ⊗ ϵ ω k (32)In fact one readily sees that the only non-zero terms of T (X) 0,t defined as above are⟨T (X) 0,t , e i ⟩ = X i 0 ⟨T (X) 0,t , e i ⊗ ϵ ω Ik ⟩ = t 0 ⟨T (X) 0,s , e i ⊗ ϵ ω I ⟩dω X,k s = X i 0 Sig(ω X ) Ik 0,t ⟨T (X) 0,t , ϵ ξ j ⟩ = ξ X,j t = t 0 dξ X,j s ⟨T (X) 0,t , ϵ ξ j ⊗ ϵ ω Ik ⟩ = t 0 ⟨T (X) 0,s , ϵ ξ j ⊗ ϵ ω I ⟩dω X,k s = t s=0 s r=0 Sig(ω X ) I r,s dξ X,j r dω X,k s = t r=0 t s=r Sig(ω X ) I r,s dω X,k s dξ X,j r = t 0 Sig(ω X ) I r,t dξ X,jr This is similar to the tensor-valued CDE defining the signature as a tensor i.e. Salvi et al. [2021a] Sig(ω) 0,t = () + t 0 Sig(ω) 0,s ⊗ dω s with the addition of two terms to track X 0 and ξ X . One could also understand T (X) s,t as a sub-tensor of X 0 ⊗ Sig((ω X , ξ X )) s,t but in doing this one would have to explicitly ignore most of the terms of this vector; the CDE (32) does exactly this, but implicitly. In any case the subtensor view shows that T : X×[0, 1] 2 → l 2 (W d0,dω,d ξ ) is well defined and continuous.To the feature map T (•) 0,t with values in the Hilbert space l 2 (W d0,dω,d ξ ) is then associated a Reproducing Kernel Hilbert Space Berlinet and Thomas-Agnan [2011] , where the Kernel is the one induced by the l 2 product, which we denote byEQUATIONClassical RKHS theory tells us that we can characterize its elements as:Proposition B.7. A map F (•) t : X → R is an element of H (•)0,ω,η tif and only if it is of the formEQUATION)for α i , β j ∈ l 2 (W dω ). Moreover ∥F (•) t ∥ 2 H (•) 0 ,ω,η t is equal to the minimal value of d0 i=1 ∥α i ∥ 2 l 2 (W dω ) + d ξ j=1 ∥β j ∥ 2 l 2 (W dω )taken over those γ, β for which the above equality holds. Just as signature kernels, the kernel associated to T (X) 0,t can be explicitly written as the solution of a two-parameter CDE:Lemma B.8. Let K X,Y (s, t) := ⟨T (X) 0,s , T (Y ) 0,t ⟩ l 2 then K X,Y (s, t) = ⟨X 0 , Y 0 ⟩ + ⟨ξ X s , ξ Y t ⟩ + s η=0 t τ =0 K X,Y (η, τ )⟨dω X η , dω Y τ ⟩ (35)or, directly in terms of Signature, alsoEQUATIONProof. The first expression follows immediately from (32) the second one by summing the products of T (X) 0,s 's and T (Y ) 0,t 's entries given above.Definition B.9. Define the space HEQUATIONfor α i , β j ∈ l 2 (W dω ). Thus for all t ∈ [0, 1] and F ∈ H(•)0,ω,η [0,1] it holds F (•, t) ∈ H (•)0,ω,η t . B.3.3 Linear maps on Z X t are close to the RKHS The following proposition will show how linear maps on Z X t cannot be more expressive than elements of the RKHS H(•)0,ω,η [0,1] since their closure is in the closure of H (•)0,ω,η [0,1]. In this precise sense these spaces act like upper bounds to expressiveness. Proposition B.10. Assume X compact. Consider fixed the gates andEQUATIONwhere F ∈ H(•)0,ω,η [0,1]. In other words, linear maps on the Z X t are in the uniform closure of H(•)0,ω,η [0,1].Proof. Using (30) we see that ⟨v, Z X t ⟩ is a linear map on T (X) 0,t with coefficients v ⊤ A I B j v ⊤ A I C i using Cauchy-Schwartz it's moreover easy to see the existence of a constant λ ≥ 0 such that for all I, i, j one has var,[s,t] we have that, given an integer M ≥ 0, the bound|v ⊤ A I B j | ≤ λ |I| |v ⊤ A I C i | ≤ λ |I| . Since |Sig(ω) I s,t | ≤ 1 |I|! ∥ω∥ |I| 1-R M (t) := d0 i=1 |I|≥M v ⊤ A I C i X i 0 Sig(ω X ) I 0,t + d ξ j=1 |I|≥M v ⊤ A I B j t 0 Sig(ω X ) I s,t dξ X,j s ≤ (∥X 0 ∥ 1 + ∥ξ X t ∥ 1 ) ∞ m=M λ m d m ω ∥ω X ∥ m 1-var,[0,t] m! ≤ (∥X 0 ∥ 1 + ∥ξ X t ∥ 1 ) ∞ m=M λ m d m ω ∥ω X ∥ m 1-var,[0,1] m! ≤ K ∞ m=M (λd ω K) m m!where K ≥ 0 is a constant which must exist by compactness of X and continuity of the gates. SinceK ∞ m=M (λdωK) m m!is just the tail of the taylor expansion of Ke λdωK there must be an M such that sup t∈[0,1] R M (t) ≤ ϵ. But then the choice we proceed to characterize which maps (X, t) → R can be uniformly approximated through them.EQUATIONProposition B.11. Fix a compact input set X and continuous gates (•) 0 , ω, ξ with ω X,1 t ≡ t and ω X,2 t ≡ t 2 . For any ϵ > 0 and anyEQUATION)whereΨ ∈ C 0 (C 1,0 ; R d0 ) and Φ ∈ C 0 (C 1,0 ; R d ξ ), there exist a G ∈ H (•)0,ω,η [0,1] such that sup (X,t)∈X×[0,1] |F (X, t) -G(X, t)| ≤ ϵ (40)Proof. Note first that the mapX × [0, 1] × [0, 1] → C 1,0 ([0, 1]; R dω ) (X, s, t) → ω X [s,t]is a continuous map from a compact space, thus the image must be compact too. Moreover by Prop.A.8 the Signature separates the points in this image. Since any G as above has formG(X, t) = d0 i=1 X i 0 ⟨α i , Sig(ω X ) 0,t ⟩ + d ξ j=1 t 0 ⟨β j , Sig(ω X ) s,t ⟩dξ X,j s = d0 i=1 X i 0 ⟨α i , Sig(ω X [0,t] ) 0,1 ⟩ + d ξ j=1 t 0 ⟨β j , Sig(ω X [s,t] ) 0,1 ⟩dξ X,js the proof follows from the uniform density on compact sets of linear functionals on the (truncated) Signature (Thm. A.5), by also uniformly bounding thanks to compactness and continuity the norms of X 0 and ξ X 1 . Remark B.12. The specific restriction of ω to subsets of [0, 1] is a crucial part of the result. The family of approximable maps does not include all path-to-path causal11 functions t → Y X t but a subset of them, of type t → Y X t := Ψ(ω X [0,t] ), satisfying the specific time-homogeneity specified by the form of the restriction, akin to that in Li et al. [2022b] .We have seen how linear maps on Z X t are in the uniform closure of H(•)0,ω,η [0,1], and we have explicitly characterized this closure. It is then natural to ask "how much" of this closure the Z X t are able to "explore". The present section not only shows that the Z X t "explore" all the closure, but also that a generic choice of weights is enough to eventually do this with high probability.The fact that these maps are "universal" in the above sense is not surprising, since it is well known that Linear CDEs are universal for path-to-point tasks cf. Kidger [2022] , what is surprising is that this universality can be achieved probabilistically with one of the standard parametrizations used in ML practice (LeCun)12 . Theorem B.13. Fix X compact and ϵ > 0. For all F ∈ H(•)0,ω,η [0,1] there exist a choice of hidden dimension N ≥ 1 and parameters v ∈ R N , A i ∈ R N ×N , B ∈ R N ×d ξ , C ∈ R N ×d0 such that sup (X,t)∈X×[0,1] |F (X, t) -⟨v, Z X t ⟩| ≤ ϵ (41)Moreover generic weight choices suffice with high probability, in the sense that under LeCun initialization[A j ] n,n ′ iid ∼ N (0, 1 N ) [C] n,i , [B] n,j iid ∼ N (0, 1)the following holds limN →∞ P ∃v ∈ R N : (41) holds = 1We propose two proofs, the first one of a deterministic character concerns the first claim in the theorem, the second one is probabilistic and concerns the whole result. The deterministic proof follows the same arguments employed by Kidger [2022] and is included to highlight the main idea of the probabilistic result, which reduces to a "spin" on the central argument of this proof.Deterministic Proof. Any F ∈ H (•)0,ω,η [0,1] has form F (X, t) = d0 i=1 X i 0 ⟨α i , Sig(ω X ) 0,t ⟩ + d ξ j=1 t 0 ⟨β j , Sig(ω X ) s,t ⟩dξ X,j s (42) for fixed α i , β j ∈ l 2 (W dω ). Consider an integer M ≥ 0 such that sup (x,t)∈X×[0,1] |F (X, t) - d0 i=1 X i 0 ⟨π M α i , Sig(ω X ) 0,t ⟩ - d ξ j=1 t 0 ⟨π M β j , Sig(ω X ) s,t ⟩dξ X,j s | ≤ ϵ (43)where π M is the truncation at length M .Fix d = d 0 + d ω + d ξ . Consider µ(M, d) ∈ N such that R µ(M,d) ≃ T M (R d ).We are going to write ,d) to mean the image of e I ∈ T M (R d ) through this identification. Note that (•) ,d) . Write ε ξ j := e d0+j for j = 1, . . . , d ξ and ε ω k := e d0+d ξ +k for k = 1, . . . , d ω . Then the solution to ,d) corresponding to the truncated tensor π M (T (X) 0,t ).e I ∈ R µ(M⊗ M e k : T M (R d ) → T M (R d ) is a linear map, it does then correspond to a matrix Λ k ∈ R µ(M,d)×µ(MR µ(M,d) ∋ Zt = d0 i=1 X i 0 e i + d ξ j=1 ξ X,j t ε B j + dω k=1 t 0 Λ d0+d ξ +k Zs dω X,k s (44) is the object in R µ(MThis Zt is of the formZ X t with N = µ(M, d), A k = Λ d0+d ξ +k , B = ε ξ 1 | • • • |ε ξ d ξ and C = [e 1 | • • • |e d0 ].In particular note how these matrices are such thatEQUATIONsince it holds thatEQUATIONand for all |I| > M one has necessarily A I = 0.Our strategy is that of using these equaities to create a vector v ∈ R N corresponding to the π M α i and π M β j . Define the vectorv := d0 i=1 |I|≤M α I i e i ⊗ ε ω I + dω j=1 |I|≤M β I j ε ξ j ⊗ ε ω I ∈ R µ(M,d) (47)Then expanding Z X t as in (30) and using the equalities above one has⟨v, Z X t ⟩ = d0 i=1 I v ⊤ A I C i X i 0 Sig(ω X ) 0,t + dω j=1 I v ⊤ A I B j t 0 Sig(ω X ) s,t dξ X,j s = d0 i=1 |I|≤M α I i X i 0 Sig(ω X ) 0,t + d ξ j=1 |I|≤M β I j t 0 Sig(ω X ) s,t dξ X,j s = d0 i=1 X i 0 ⟨π M α i , Sig(ω X ) 0,t ⟩ + d ξ j=1 t 0 ⟨π M β j , Sig(ω X ) s,t ⟩dξ X,j sproving that for such v and Z X it holds sup(x,t)∈X×[0,1] |F (X, t) -⟨v, Z X t ⟩| ≤ ϵ (48)The crucial ingredient for the success of this proof is the possibility to recreate the space T M (R d0+dω+d ξ ) as an euclidean space. To do this one needs µ(M, d 0 +d ω +d ξ ) ∼ (d 0 +d ω +d ξ ) M orthogonal vectors and a way to express them using the matrices A i , B and C, the essential equations which capture this are given by ( 45).The core idea of the following probabilistic proof of this same result is that of allowing for some error in ( 45), so the idea is that of exhibiting only approximately orthogonal vectors. At the cost of losing exactness, one can leverage results of the Johnson-Lindenstrauss Dasgupta and Gupta [2003] type to find on the order of ∼ e ε 2 N vectors in R N orthogonal up to an ε error, using random projections. This idea in the context of Signature goes back to Cuchiero et al. [2021b] , and allows for much smaller hidden dimensions.Proof.EQUATIONfor fixed α i , β j ∈ l 2 (W dω ). Consider an integer M ≥ 0 such that sup(x,t)∈X×[0,1] |F (X, t) - d0 i=1 X i 0 ⟨π M α i , Sig(ω X ) 0,t ⟩ - d ξ j=1 t 0 ⟨π M β j , Sig(ω X ) s,t ⟩dξ X,j s | ≤ ϵ (50)where π M is the truncation at length M .From Cirone et al. [2023] [Appendix C] we know that1 N C ⊤ i A ⊤ I A J C j -δ jJ iI L 2 = O( 1 √ N )2 |I|+|J| 2 (|I| + |J|)!! (51) 1 N C ⊤ i A ⊤ I A J B j L 2 = O( 1 √ N )2 |I|+|J| 2 (|I| + |J|)!! (52) 1 N B ⊤ i A ⊤ I A J B j -δ jJ iI L 2 = O( 1 √ N )2 |I|+|J| 2 (|I| + |J|)!! (53)Our strategy is that of using these bounds to create a vector v ∈ R N "acting" like the π M α i and π M β j . Define, noting that the A i , C i , B j depend on N , the vectorv N := 1 N   d0 i=1 |I|≤M α I i A I C i + dω j=1 |I|≤M β I j A I B j   (54)Then expanding Z X t as in ( 30)R M := sup (X,t)∈X×[0,1] ⟨v N , Z X t ⟩ - d0 i=1 X i 0 ⟨π M α i , Sig(ω X ) 0,t ⟩ - d ξ j=1 t 0 ⟨π M β j , Sig(ω X ) s,t ⟩dξ X,j s L 2 ≤ d0 i=1 |I|≤M (v N ) ⊤ A I C i -α I i L 2 sup (X,t)∈X×[0,1] |X i 0 Sig(ω X ) I 0,t | + + d0 i=1 |I|>M (v N ) ⊤ A I C i L 2 sup (X,t)∈X×[0,1] |X i 0 Sig(ω X ) I 0,t | + dω j=1 |I|≤M (v N ) ⊤ A I B j -β I j L 2 sup (X,t)∈X×[0,1] | t 0 Sig(ω X ) I s,t dξ X,j s | + + dω j=1 |I|>M (v N ) ⊤ A I B j L 2 sup (X,t)∈X×[0,1] | t 0 Sig(ω X ) I s,t dξ X,j s | Note how for |I| ≤ M one has (v N ) ⊤ A I C i -α I i L 2 ≤ O M ( 1 √ N )and that similarly for |I| > M(v N ) ⊤ A I C i L 2 ≤ O M ( 1 √ N )2 |I| 2 (M + |I|)!!Which leads, thanks to the same bounds of Cirone et al. [2023] [Appendix C], toEQUATIONBut then by Markov's inequality it holds thatP   sup (X,t)∈X×[0,1] ⟨v N , Z X t ⟩ - d0 i=1 X i 0 ⟨π M α i , Sig(ω X ) 0,t ⟩ - d ξ j=1 t 0 ⟨π M β j , Sig(ω X ) s,t ⟩dξ X,j s ≤ ϵ   → 1 (56)and thus there must be a choice of N, {A i }, B, C such that the inequality holds, and we thus obtain using ( 50) sup(X,t)∈X×[0,1] |F (X, t) -⟨v N , Z X t ⟩| ≤ 2ϵand we conclude by arbitrariness of ϵ.Here we study the particular, but empirically important, case where the matrices A i are taken to be diagonal 13 .What we'll discover is that the Z X t cannot differentiate between Sig(ω X ) I s,t and other Sig(ω X ) σ(I) s,t for any permutation σ of the letters in the word I.X t Proposition B.14. For any choice of V ∈ R N ×dω , B ∈ R N ×d ξ and C ∈ R N ×d0 , writing A i := diag(V i ), the unique solution to dZ X t = dω i=1 A i Z X t dω X,i t + Bdξ X t Z X 0 = CX 0 ∈ R N (57)is given byEQUATION)which can be expanded asEQUATIONProof. By Theorem E.1 and Theorem E.6 we know that the solution ofZ X t = Z X 0 + dω i=1 t 0 A i Z X t dω X,i t + t 0 Bdξ X t (61)is explicitly given byEQUATION)where W s,t is the unique solution toEQUATIONIn case the A i s are commuting matrices one can explicitly write the solution asEQUATIONsince for fixed s one has, using commutativity, thatdW X s,t = W X s,t dω i=1 A i dω X,i t = dω i=1 A i W X s,t dω X,i tOn the other hand we know, Theorem E.2, thatEQUATIONThe two views are reconciled by noticing that the symmetric group S k acts on W k dω , the space of words of lenth k, by permuting the letters and, by commutativity,∀σ ∈ S k .∀I ∈ W k dω . A I = A σ(I)Then we haveI∈W k dω A I Sig(ω X ) I s,t = I∈W k dω 1 k! σ∈S k A σ(I) Sig(ω X ) σ(I) s,t = I∈W k dω A I k! σ∈S k Sig(ω X ) σ(I) s,t recalling then how e I1 ¡ • • • ¡ e I k = σ∈S k e σ(I) we get to I∈W k dω A I Sig(ω X ) I s,t = I∈W k dω A I k! σ∈S k Sig(ω X ) σ(I) s,t = I∈W k dω A I k! k i=1 Sig(ω X ) Ii s,t = I∈W k dω 1 k! k i=1 A Ii Sig(ω X ) Ii s,t = 1 k! dω i=1 A i Sig(ω X ) i s,t k = 1 k! dω i=1 t s A i dω X,i r kIn particular we see how in the commuting caseEQUATIONwhereA sym I := 1 |I|! σ∈S k A σ(I) = A I Sig(ω X ) sym,I s,t := 1 |I|! σ∈S k Sig(ω X ) σ(I) s,t .Theorem B.15. Fix a compact input set X and continuous gates (•) 0 , ω, ξ. For any ϵ > 0 and anyEQUATIONMoreover the "reverse" also holds i.e. given any choice of matrices A i , B, C there is an ϵ-close map F in the family.Proof. This is just a repetition of the arguments used for the dense case with little more care to get the uniformity in time.One defines the subset Sym(H(•)0,ω,η [0,1] ) ⊂ H (•)0,ω,η [0,1]of those F of type (37) defined by α i , β j ∈ l 2 (W dω ) such that for any word I and any permutation σ(I) of itEQUATIONThe same argument of Proposition B.10 shows that the uniform closure of the space of linear maps on the Z X t is contained in the uniform closure of Sym(H(•)0,ω,η [0,1]), and the same bounds show that this latter closure is the same as that of its subset composed of those F ∈ Sym(H(•)0,ω,η [0,1]) having entries eventually equal to 0.Sig(ω X ) sym,I s,t := 1 |I|! σ∈S k Sig(ω X ) σ(I) s,t = 1 |I|! |I| i=1 (ω X,Ii t -ω X,Ii s ),such maps can be expressed exactly in the formP (ω X t ) • X 0 + t 0 Q(ω X t -ω X s ) • dξ X sfor polynomial maps P, Q fixed in time. The usual compactness and continuity argument, together with an application of Stone-Weiestrass, thus proves that the uniform closure of Sym(H(•)0,ω,η [0,1]) has the form needed.The final ingredient is the density of the space of linear maps on the Z X t in Sym(H(•)0,ω,η [0,1]); this is another consequence of Stone-Weiestrass as seen from Proposition B.18.Remark B.16. Notice how here there is no need to augment the paths in creative ways in order to ensure separability of the points. The map (ω, s, t) → ω [s,t] ∈ C 1,0 ([0, 1]; R dω ) is replaced by (ω, s, t) → ω t -ω s ∈ R dω and the space of polynomials always separates points in R dω .Remark B.17. It is not necessary to pass through Sym(H(•)0,ω,η [0,1]) to prove the previous result, since it directly follows from Proposition B.18. This choice of presentation has been motivated by the conviction of the usefulness of drawing parallels and comparisons. Proposition B.18. Fix a compact set K ⊂ R d and a d-dimensional convex cone C containing the origin. The spaceE := Span K ∋ x → e ⟨α,x⟩ R d ∈ R : α ∈ C is uniformly dense in C 0 (K; R).Proof. This is an application of Stone-Weiestrass: E is a sub-algebra since Remark B.19. The usefulness of stating the previous result in such a general setting is the following: with this formalism we can, for example, restrict to α ≤ 0, in this way we would have a method to control the stability (cf. Appendix C.1) of the Linear CDEs by choosing the gate with a.s. ωX ≥ 0. Corollary B.20 (Mamba Case). In the Mamba setting, the closure reduces toEQUATIONfor continuous ψ i : R → R and ϕ i : R → R.Proof. In this setting one runs in parallel d ω diagonal systems and then takes a linear combination of the stacked hidden state. The maps in the closure of the whole system are then just the sums of maps in the closure of the subsystems.For this section consider, unless otherwise stated, a fixed N ≥ 0, compact X and gates (•) 0 , ω, ξ.We will study the stability and chaining of diagonal systems defined by the choice of a matrixV ∈ R N ×dω such that A i := diag(V i ), where V = [V 1 | • • • |V dω ].Note that the present discussion holds even for non-diagonal but commuting matrices, since these can be simultaneously diagonalized (at the cost of considering the complex plane).Here we explore the stability of the dynamical system Z X , thus we need to study the eigenvalues of the W X s,t . Recall how in this settingEQUATIONNote that because ω X is continuous and of bounded variation, it can be reparameterised to be Lipschitz continuous, hence absolutely continuous. Thus we can assume that ω X is almost everywhere differentiable and its derivative ω ∈ L 1 .The stability of the dynamical system then depends on the alignment between ω X t -ω X s and the singular vectors of V . If V ωX t ≤ 0 for all times, where the inequality is coordinate-wise, then W X s,t has eigenvalues all in [0, 1] thus the system is stable making training easier Orvieto et al. [2023a] .Consider the singular value decomposition (SVD) of the matrixEQUATIONThen, a sufficient condition for stability is that for any k = 1, ..., KEQUATIONIn the case of Mamba Gu and Dao [2023] the matrices are diagonal and dω X t = sof tplus(W x t + λ)dt, dξ X t = x t ⊙ dω X t , moreover the proposed choices of V are all of type V = -v ⊗ 1 dω for some choice of 0 ≤ v ∈ R N . Note that sof tmax is just a smooth approximation of ReLU and that Im(ReLU ) ⊆ {w ∈ R dω : ⟨1 dω , w⟩ ≥ 0} hence mamba is implicitly ensuring that the dynamical system is approximately always well-conditioned.The diagonal case differs from the general one not only in the fact that the class of approximable functions is much weaker but also in the necessity for the presence of ξ X in order to obtain any path-dependence. The termt 0 ϕ(ω X t -ω X s ) • dξ X sbecomes then a crucial component. At first sight one might think that such a term allows to recover at least level two components of the Signature of (ω X , ξ X ), unfortunately things are not as easy as they may seem. Notice how inside of the integral time is "going backwards" from the perspective of ω X , thus we can in general approximate terms of typet 0 t s dω X,i r dξ X,j s = 1 1-t r 1-t d ← - ω X,i r d ← - ξ X,j s = Sig(( ← - ω X , ← - ξ X )) iωj ξ 1-t,1which are indeed terms of the Signature, but of the reverse paths ←ω X r = ω X 1-r and← - ξ s = ξ X 1-s !Proposition C.1. Fix a compact input set X, continuous gates (•) 0 , ω, ξ and X 1 0 = 1. If the components of ξ X are linear combinations of those of ω X , with time-independent weights, then linear functionals on Z X t can, uniformly in X × [0, 1], approximate arbitrarily well the following level 2 terms of Sig((ω X , ξ X )) 0,t :t 0 s 0 dω X,i r dξ X,j s = Sig((ω X , ξ X )) iωj ξ 0,tProof. Under these hypotheses we know that linear functionals on Z X t are uniformly dense, for continuous ψ, ϕ, in(X, t) → ψ(ω X t ) • X 0 + t 0 ϕ(ω X t -ω X s ) • dξ X s .Assume ξ X,j s = ⟨α j , ω X t ⟩ and consider the choicesEQUATIONEQUATIONTo conclude note thatω X,i t ξ t = t s=0 t r=0 dω X,i r dξ X,j s = t s=0 s r=0 dω X,i r dξ X,j s + t s=0 t r=s dω X,i r dξ X,j s = t 0 s 0 dω X,i r dξ X,j s + t s=0 (ω X,i t -ω X,i s )dξ X,j s hence t 0 s 0 dω X,i r dξ X,j s = ω X,i t ξ X,j t - t s=0 (ω X,i t -ω X,i s )dξ X,j s = ψ(ω X t ) • X 0 + t 0 ϕ(ω X t -ω X s ) • dξ X s If X ∈ C 1,0 ([0, 1]; R d )we can use the previous result to compute its Signature entries by chaining diagonal Linear CDEs. Theorem C.2. Assume a compact input set X ⊂ C 1,0 ([0, 1]; R d ). For any I ∈ W d with |I| ≥ 2 and ϵ > 0 there is a sequence of linear maps W k ∈ R N k ×1 and weights for the following family of chained Linear CDEsEQUATIONEQUATIONEQUATIONProof. For |I| = 2 we can apply Prop. C.1. Assume the theorem holds for |I| ≤ k and letM := sup X∈X ∥X∥ 1-var . Fix |Ij| = k + 1 and W k-1 ∈ R N k-1 ×1 such that sup (X,t)∈X×[0,1] |Sig(X) I 0,t -W k-1 Z k-1,X t | ≤ ϵ M .Again by Prop. C.1 there are aN k and v ∈ R N k such that sup (X,t)∈X×[0,1] | t 0 W k-1 Z k-1,X s dX j s -⟨v, Z k,X t ⟩| ≤ ϵ. Then |Sig(X) Ij 0,t -⟨v, Z k,X t ⟩| ≤| t 0 Sig(X) I 0,s dX j s - t 0 W k-1 Z k-1,X s dX j s | + | t 0 W k-1 Z k-1,X s dX j s -⟨v, Z k,X t ⟩| ≤ t 0 |Sig(X) I 0,s -W k-1 Z k-1,X s ||dX j s | + ϵ ≤ t 0 ϵ M |dX j s | + ϵ ≤ 2ϵthus concluding the proof.Then Proposition 4.5 follows as a corollary by running in parallel the systems above to recover simultaneously multiple Signature entries.Models like Mamba do not only use diagonal matrices but also consider controls of a specific kind:ω X t = t 0 ReLU (W X s + b)dsThe choice of ReLU enforces ωt ≥ 0 for all times as seen above, but could, a priori, destroy information about X which allows for the recovery, after chaining, of its Signature.Does this choice keep some expressivity? Fortunately almost all of it: sinceReLU (x) -ReLU (-x) = xone can choose a linear map W which allows to linearly recoverωX t = t 0 X s dsfrom ω X t . By correspondingly modifying the form of ψ and ϕ in (74) such thatEQUATION)one is able, through a similar chaining procedure, to recover arbitrarily deep entries of the Signature of ωXt = t 0 X s ds. D Path-to-Path Definition D.1. A map G ∈ C 0 (C 1,0 ([0, 1]; R d ) × [0, 1]; R) is causal iff for all t ∈ [0, 1] and paths ω, ω ∈ C 1,0 ([0, 1]; R d ) one has ω| [0,t] = ω| [0,t] =⇒ G(ω, t) = G(ω, t)i.e. G is causal if it does not look in the future. Proposition D.2. Assume a compact input set X, continuous (•) 0 , ω, ξ, X 1 0 ≡ 1 and ω X,1 t ≡ t. Then for all ϵ > 0 and all causal G ∈ C 0 (C 1,0 ([0, 1]; R dω ) × [0, 1]; R) there exist an integer N ≥ 0, some Feed Forward neural network F : R N → R, and parametersEQUATIONProof. Fix ϵ > 0. By B.7 the space H(•)0,ω,η [0,1]contains all functionals of form (X, t) → ⟨α, Sig(ω X ) 0,t ⟩ thus, by the properties of the signature and by compactness of X, for any fixed s 0 ∈ [0, 1] there is some f ∈ HEQUATIONfor i = 0, . . . , M -1. Notice then how for all X ∈ X and s ∈ [s i-1 , s i+1 ]|f i (X, s) -G(ω X , s)| ≤ |f i (X, s) -f i (X, s i )| + |f i (X, s i ) -G(ω X , s i )| + |G(ω X , s i ) -G(ω X , s)| ≤ 3ϵIt follows that the map F ∈ C 0 ([0, 1] × X; R) linearly interpolating the f i in time satisfiessup X∈X sup t∈[0,1] |F (X) t -G(ω X , t)| < 6ϵTo conclude note that X being compact, the f i take values in a common compact set K ⊆ R. There exist then a neural networkΨ : [0, 1] × K M → R such that sup i∈0,...,M -1 sup s∈[si,si+1] |Ψ(t, z) - s i+1 -s s i+1 -s i z i + s -s i s i+1 -s i z i+1 | < ϵ which means that sup X∈X sup t∈[0,1] |Ψ(t, f 0 (X, t), . . . , f M (X, t)) -F (X, t)| < ϵ Recalling that ω X,1 t = t we get that X → {t → t} ∈ H (•)0,ω,η [0,1]so that, given density of linear maps on Z X in the space, Ψ(t, f 0 (X, t), . . . , f M (X, t)) can be uniformly approximated. Triangular inequality gives finally supX∈X sup t∈[0,1] |Ψ(t, f 0 (X, t), . . . , f M (X, t)) -G(ω X , t)| < 7ϵwhich, by arbitrariness of ϵ, gives the thesis.The non-linearity is crucial for the path-to-path result. A map of type (ω, t) → ⟨tα, Sig(ω) 0,t ⟩ cannot be approximated arbitrarily well by (ω, t) → ⟨β, Sig(ω) 0,t ⟩.In any case, note that in the proof the role of the neural network is only that of interpolating the RKHS elements in the right order and at the right time. All the non-linear complexity of learning the particular G is offloaded and taken care of by the RKHS elements. Remark D.3. In the proof we have only considered the part of T (X) concerning ω X , but T (X) t depends linearly on X 0 and ξ X suggesting that neural networks on H(•)0,ω,η [0,1]have stronger generalization properties. In fact one can prove that it is possible to approximate all continuous G(X 0 , ω X , ξ X , t), this is done by reconstructing X 0 and ξ X [0,1] as in the classical SSM case cf. Orvieto et al. [2023b] .In this section we obtain a unified theory studying the solutions to general Linear CDEs. The results presented here are not new and can be found in different terms in the literature Friz and Victoir [2010] , despite this we have decided to reproduce them from scratch for completeness, notational reasons and to present a self-contained theory. Theorem E.1. For any choice {A 1 , . . . ,A d } ⊆ C 0 ([0, 1]; R N ×N ) and ω ∈ C 1 ([0, 1]; R d ) there exist a unique map W ∈ C 0 ([0, 1] × [0, 1]; R N ×N ) solving the following CDE W s,t = Id N + d i=1 t τ =s A i τ W s,τ dω i τ (84)Proof. We will use Banach fixed point theorem leveraging the completeness of the spaceΩ := C 0 ([0, 1] × [0, 1]; R N ×N ) with the uniform norm ∥X∥ ∞ := sup s,t∈[0,1] ∥X s,t ∥ op Define the map Γ : Ω → Ω as Γ(X) s,t = Id N + d i=1 t τ =s A i τ X s,τ dω i τ One has, for X, Y ∈ Ω and k ∈ N setting Γ 0 = Id Ω , that Γ k+1 (X) s,t -Γ k+1 (Y ) s,t = d i=1 t τ =s A i τ Γ k (X) s,τ -Γ k (Y ) s,τ dω i τ which iterated gives Γ k+1 (X) s,t -Γ k+1 (Y ) s,t = I∈W d |I|=k+1 t τ k+1 =s • • • τ2 τ1=s   1 j=k+1 A Ij τj   (X s,τ1 -Z s,τ1 ) k+1 j=1 dω Ij τj = I∈W d |I|=k+1 τ ∈∆ k+1 [s,t] A I τ (X s,τ1 -Z s,τ1 ) dω I τwhere W d is the set of words in the alphabet {1, . . . , d} andEQUATIONthus definitely (in k) the map Γ k is a contraction. By Banach fixed point there exist a unique fixed point W ∈ Ω.Theorem E.2. Under the assumptions of the previous theorem one can write W s,t explicitly asEQUATION)moreover if for all i the matrix-valued maps are constant on all [0, 1] i.e.EQUATIONwhere Sig(ω) I s,t is the Signature of the path ω.Proof. The second assertion follows from the first by definition of the Signature of a path.Regarding the first notice how the series is absolutely convergent in R N ×N , uniformly in s, t since var,[s,t] ≤ e dM ∥ω∥ 1-var, [0,1] thus for any s, t ∈ [0, 1] the series defines an element of Ws,t ∈ R N ×N .I∈W d τ ∈∆ |I| [s,t] A I τ dω I τ op ≤ ∞ k=0 d k M k ∥ω∥ k 1-var,[s,t] k! =e dM ∥ω∥ 1-Using the uniformity of this bound and the fact that for all I ∈ W d one hasW I s,t := τ ∈∆ |I| [s,t] A I τ dω I τ ∈ Ωas a function of (s, t), which moreover is uniformly continuousW I s1,t1 -W I s2,t2 op = τ ∈∆ |I| [s 1 ∧s 2 ,t 1 ∨t 2 ] (δ τ ∈∆ |I| [s 1 ,t 1 ] -δ τ ∈∆ |I| [s 2 ,t 2 ] )A I τ dω I τ op ≤M |I| τ ∈∆ |I| [s 1 ∧s 2 ,t 1 ∨t 2 ] δ τ ∈∆ |I| [s 1 ,t 1 ] -δ τ ∈∆ |I| [s 2 ,t 2 ] |dω I τ | ≤M |I| ∥ω∥ |I| [s1∧s2,s1∨s2]∪[t1∧t2,t1∨t2] , one concludes that Ws,t ∈ Ω. Finally notice that Ws,t is a fixed point of Γ Γ( Ws,t ) =Id N + d i=1 t τ =s A i τ I∈W d τ ∈∆ |I| [0,1] A I τ dω I τ dω i τ =Id N + I∈W d |I|≥1 τ ∈∆ |I| [0,1] A I τ dω I τ dω i τ = I∈W d τ ∈∆ |I| [0,1] A I τ dω I τ = Ws,tand conclude by uniqueness.Proposition E.3. Under the previous conditions, the unique solution of the N -dimensional CDEdX t = X 0 + d i=1 t τ =0 A i τ X τ dω i τ (88)is given byEQUATIONProof. The solutions are unique by standard results Friz and Victoir [2010][Thm. 3.7] , moreoverW 0,t X 0 = Id N + d i=1 t τ =0 A i τ W 0,τ dω i τ X 0 = X 0 + d i=1 t τ =0 A i τ (W 0,τ X 0 )dω i τProposition E.4. The Wronskian matrix has the following properties:1. ∀r, s, t ∈ [0, 1]. W r,t = W s,t W r,s 2. ∀s, t ∈ [0, 1]. W -1 s,t = W t,s 3. ∀s, t ∈ [0, 1]. W s,t = Id N + d i=1 t σ=s W σ,t A i σ dω i σ Proof.Regarding the first statement notice that for all X 0 ∈ R N one hasXt :=W s,t W r,s X 0 = Id N + d i=1 t τ =s A i τ W s,τ dω i τ W r,s X 0 =W r,s X 0 + d i=1 t τ =s A i τ (W s,τ W r,s X 0 )dω i τ =W r,s X 0 + d i=1 t τ =s A i τ Xτ dω i τand by the previous proposition alsoX t := W r,t X 0 = W r,t X 0 + d i=1 t τ =r A i τ X τ dω i τthus X t and Xt solve the same CDE and coincide at time t = s. This means, by uniqueness, that X t and Xt coincide for all times; hence W s,t W r,s and W r,t coincide for all times too since for any choice of X 0 one has W s,t W r,s X 0 = W r,t X 0 .The second statement follows from the previous one setting first r = t and subsequently exchanging s and t.To prove the third equality note that0 = d s (W s,t W t,s ) = (d s W s,t )W t,s + W s,t (d s W t,s ) hence d s W s,t = -W s,t (d s W t,s )W -1 t,s = -W s,t ( d i=1 A i s W t,s dω i s )W -1 t,s = - d i=1 W s,t A i s dω i sProposition E.5 (Liouville's Formula). Under the assumptions of the previous theorems,EQUATIONProof. This just follows from the classical case since we can writed i=1 t τ =s A i τ W s,τ dω i τ = t τ =s d i=1 A i τ ωi τ W s,τ dτWe can now state the main result of the section: Theorem E.6. Under the assumptions of the previous theorems, given continuous functions {B 1 , . . . , B t } ∈ (R d ) [0,1] the unique solution of the N -dimensional CDEX t = X 0 + d i=1 t τ =0 A i τ X τ + B i τ dω i τ (91) is given explicitly by X t = W 0,t X 0 + d i=1 t 0 W s,t B i s dω i s (92) where W s,t ∈ C 0 ([0, 1] × [0, 1]; R N ×N ) is the Wronskian matrix defined by W s,t = I∈W d τ ∈∆ |I| [s,t] A I τ dω I τ (93)Proof. Given the unique solution X t one hasd s (W s,t X s ) =d s (W s,t )X s + W s,t d s (X s ) = d i=1 -W s,t A i s X s + W s,t A i s X s + W s,t B i s dω i s = d i=1 W s,t B i s dω i s hence X t -W 0,t X 0 = W t,t X t -W 0,t X 0 = d i=1 t s=0 W s,t B i s dω i sConsider a Linear CDE as the one of ( 25)dZ t = dω i=1 A i Z t dω i t + Bdξ tand recall how the solution can be explicitly written, for times s < t, asZ t = W s,t Z s + t s W r,t Bdξ rAssume moreover that in the interval [s, t] both drivers have constant derivative i.e.EQUATIONBut the integral can be explicitly solved asEQUATIONleaving us withEQUATIONwhich, setting ∆ = t -s, can be rewritten asEQUATIONi.e. exactly the ZOH scheme.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.38th Conference on Neural Information Processing Systems (NeurIPS 2024).Let us ignore the terms t, t 2 at this stage; their role is purely technical due to possible path equivalences.So when we write I ∈ W dγ we mean I = i1i2 • • • iM for some integer M ≥ 0 and letters im ∈ {1, . . . , dγ}, then Ii will be the word i1i2 • • • iM i for i ∈ {1, . . . , dγ}.A causal map is one which does not "look in the future" cf. Appendix D.Merrill et al. [2024] show that with tailored architectures, S4, Mamba, and a Transformer can achieve over 90% validation accuracy on length-20 sequences using 4 blocks. However, in our experiments we wished to keep the architecture consistent between models, only changing the sequence-to-sequence model.Here the integral is intended in the Riemann-Stjeltes sense.A causal map is one which does not "look in the future" cf. Appendix D.It can be proved, using the results ofDubach and Peled [2021], that the sampling measure does not have to be Gaussian if it satisfies certain moment requirements.It is equivalent to ask for them to be commuting. 


Decision: The paper presents a detailed study on the expressive power of State Space Models (SSMs) through the lens of Rough Path Theory, with a particular focus on the importance of the gating mechanism. The paper is well-structured and clearly written, making it accessible to readers who are familiar with the core concepts. The results are robust and provide valuable insights into the design choices made in past implementations of SSMs. These findings have the potential to guide the development of future variants of SSMs, contributing positively to the field.

However, there is some room for improvement. While the authors have made a commendable effort to include preliminary materials in the appendix, the paper may still be challenging for readers who are not well-versed in the required background. This could limit its accessibility to a broader audience. A more thorough explanation or simplification of these complex concepts within the main text would greatly enhance the paper's readability. Despite this, the overall quality of the work and its potential impact on future research in SSMs warrant its acceptance.

Reviews: review: paper_summary: paper_summary: This work analyses the modeling capability of different SSMs (S4-S6 and others) using Rough Path Theory by viewing SSMs as (input-) controlled differential equations (CDE). To this end, the authors show that SSMs with with dense transition matrices (A) are able to approximate arbitrarily close any continuous functions of the inputs. In contrast, SSMs with diagonal transition matrices lack this property. However, when stacking/chaining multiple diagonal CDEs (as is the case for the deep architectures), full expressivity is gained again as the depth approaches infinity. The work is mostly theoretical, and, hence, there is only a single toy experiment showing RMSE for Mamba and S5 models with depth 1 and 2, showing that the more limited models are not able to solve the toy task, as they cannot approximate the corresponding function.
strength_weakness: strength_weakness: Despite the well-described theoretical contributions and insights, it is still not very clear to me what to take away practically.
In particular, it is not clear how useful the result regarding chaining diagonal CDEs is in practice: while it is important to have a proof that an infinite number of chains of diagonal CDE with mixing can recover the full expressiveness of the dense CDEs, the infinite case is not practically important. Instead, it would be important for practical considerations (computational efficiency vs model expressiveness) to know whether one should use dense CDEs or diagonal CDEs with mixing to achieve a certain level of expressivity.  However, as far as I understand, there is no result that quantifies e.g. how many diagonal plus mixing layers have a similar expressiveness as a certain number of dense CDEs. The authors speculate in the summary that architectures with non-diagonality might improve performance, but I do not see how this actually follows from this work, since there is no comparison between diagonal+mixing and dense in the regime of finite number of parameters. 

The experimental section is very weak. While this work is mostly theoretical, this work would nevertheless be improved a lot by a greater experimental section that validates the claims. Showing error curves with a single random seed is not that interesting. I would be better to have a table of final performance that includes error bars. Furthermore, it would be great to explore a few different tasks and several ablations such as number of layers. This would make it at least empirically possible to compare dense and diagonal + mixing and random dense + learned C (or MLP) in the finite parameter setting, where its not clear what to take away from the theorems.
questions: questions: - what is NCDE? This was not introduced.
- does random linear CDE perform best for Area computation and is also a strong baseline for Volume?  I understand that with high probability we can just take a random initialized A matrix and train only the C matrix (Theorem 4.2) to achieve full expressivity. However, that model should still not be better than a dense CDE where everything is trained such as in case of S5. Or did you choose S5 with diagonal transition?
limitations: limitations: Just a single limitation is mentioned in the conclusion. I am sure, the authors can think of many more limitations, such as my main concern raised above regarding the comparison of different mixed diagonal + mixing vs dense architectures. Or the limited experimental evidence.
paper_summary: paper_summary: This paper proposes a framework of using Rough Path Theory to understand the expressivity of SSMs and Mamba. The paper establishes connections to linear CDEs and then uses tools from Rough Path Theory to explain why gates are so powerful in SSM models.
strength_weakness: strength_weakness: Not much weaknesses in the work itself. The ultimate test of theory is its predictive power - the paper would be stronger if the theory could "close the loop" and propose a modification to SSM layers that would enable further performance. However, this is a high bar to clear, and I think the work stands on its own as a solid contribution even without a methodological contribution.
questions: questions: Can you think of any improvements to SSM layers/models that the RPT theory would suggest?
limitations: limitations: N/A
paper_summary: paper_summary: This paper proposes a framework for better understanding key features that allow the success of SSMs. To be specific, the authors first show that recent SSM-based models are linear controlled differential equations (CDEs). Then, the expressive power of linear CDEs are explored, depending on whether the matrices $A_i$ are diagonal.
strength_weakness: strength_weakness: * It would be better to provide preliminaries on rough path theory for readers who are not familiar with that.
* Although the mathematical results are interesting, I am not sure about the implications of the theoretical results in practice. It would be better if the empirical results are designed to provide the messages that are useful in practice.
questions: questions: * How can we derive Eq.3? Why suddenly exponential term appears? Any reference for the zero-order hold discretization? (Actually, I searched for such terminology, but could not make a connection between it and Eq.3)
limitations: limitations: * Check the weakness part & questions part
paper_summary: paper_summary: This work establishes density results of input-controlled differential equations, which formulate different types of state-space models such as S4 and Mamba in the continuous-time idealization. Under this framework, different closures of these models are derived, indicating their distinct inductive biases in the (universal) approximation sense, particularly implying the advantage of data-dependent modeling.
strength_weakness: strength_weakness: 1. In theory, only the density type of results is provided. That is, although models can rates certain targets universally when models' parameters go to infinity, the convergence *rates* are not characterized. This is much more important since the convergence can  be rather slow in certain situations (e.g. curse of dimension), leading to possibly vacuous bounds. The theoretical part would be strengthened and more convincing if authors can discuss more on the approximation rates of SSMs, especially the improvements (in parameter efficiency) of data-dependent modeling. 
2. In experiments, the simulations are conducted on low-dimensional (2 & 3) and synthetic datasets. Is it due to the ability of path signature? Can the path signature be powerful and efficient when handling high-dimensional (and real-world) input data?
questions: questions: 1. Please provide more details of questions raised in the weaknesses section above. 
2. In formulation, the mentioned "gating" mechanism in this work seems to have a different meaning as usual. Here, gating refers to the transformation of inputs (i.e. data pre-processing). However, in practice, gating often means the (multiplicative) interaction between the hidden states and readout layers (i.e., to get outputs). Can authors explain more about this?
3. Minor issues: What is the definition of (linear) NCDE (see line 311, 312, 315, 317 and 643).
limitations: limitations: As is stated by authors, this work applies a continuous-time idealization in the formulation. The role of concrete discretization schemes is also worthy of explorations, particularly under the case of data-dependent discretization.

Comments: title: Response
Response to rebuttal
comment: Thank you for the rebuttal. I will be keeping my high score.
We thank the reviewer for the message and the additional questions.

We agree that including insights on the effects of width is interesting; see next paragraph. However, note that width alone is insufficient to capture all the high-order  terms of the signature in the diagonal (Mamba-like) case. Our objective in this paper, besides completely characterizing the density, is to highlight a fundamental limitation of diagonal models that is independent of width (this is not an upper bound - our result is tight). Our insights can guide further analysis, such as the potential design of minimal epsilon-sparse recurrences that still capture the full effects of the signature without severely affecting speed or parameter count. 

Regarding your question: It is possible to derive width-dependent bounds, yet these are unlikely to be tight, similar to what is observed in standard MLPs.  

We will develop on this in a new subsection in our revision. Techniques and results going in this direction are actively researched by the Rough paths in ML community. As a primal example we would like to refer you to the paper titled "Generalization Bounds for Neural Controlled Differential Equations" (https://arxiv.org/abs/2305.16791). This work provides a generalization bound for a broader class of learners, specifically Neural Controlled Differential Equations (NCDEs), which, as explained in our previous response, are closely related to Linear CDEs, offering a detailed analysis of both generalization bounds and approximation biases. In order to do this the data streams and models are studied from a rough path perspective, dynamical bounds are produced by considering Lipschitz properties of the vector fields and the regularity of the input streams via their 1-variation. These are the natural tools to employ with CDEs like the ones we specify in this work. 

What we just described is an example of how our work establishes a solid theoretical connection between State Space Models (SSMs) and Rough Paths, setting the stage for further studies, and allowing researchers to leverage the rich literature of existing results.
We appreciate your continued feedback and your recognition of the theoretical contributions of our work. We understand your concerns regarding the practical implications of our results and the empirical validation to support our theoretical findings.

**Regarding your point about the practical impact of our work**:

We agree that understanding the implications of chaining diagonal matrices and the expressivity of models like Mamba in practical scenarios with multiple layers is important. While our work does not offer a direct blueprint for designing new architectures, we believe it lays the groundwork for future research in this area by identifying key components that could influence expressivity. In particular the fact that diagonal systems capture only the symmetric part of the signature could be leveraged to extend the chaining results to the non-linear case: approximating the result with a linear functional on the symmetric part of the signature, then leveraging the algebra structure of the shuffle product. This procedure would show how even $n$ chained diagonal (Mamba-like) layers, interleaved with non-linearities, would capture the non-symmetric part of the signature fundamentally only up to level $n$. Note that width alone cannot capture the higher terms of the signature; what we point out is a fundamental and *width-independent* drawback of diagonal models, a limitation which can serve as a guide for further avenues of analysis. We also note that it can be possible to derive width-dependent bounds, however those would likely not be tight (as in the standard MLP case).

**Regarding the empirical validation**:

We understand the importance of supporting theoretical claims with empirical evidence. As mentioned in our initial response, we have indeed conducted new experiments, including a novel analysis using the A5 benchmark of Merril et al. 2024 (“Illusion of state” paper). These experiments were designed to provide additional insights into the practical performance of different architectures, particularly focusing on the depth required for models like Mamba to achieve high performance on state tracking (a task that cannot be easily solved by attention). We included these results in the supplementary material and in the general response pdf.

Given your feedback, it seems that these new experiments may not have been fully considered. We are sorry if we perhaps did not emphasize them. If this is the case, we encourage you to review the supplementary material pdf and general response where these additional results are discussed in detail. 

We value your constructive feedback and would be open to any further suggestions on how we could better present or highlight these results in the final version of our paper.
Thanks for the reply. I still feel that the convergence rate characterization is much more important than the density analysis. Certainly, eq. (55) derives the dependence on hidden dimensions, but for sequence modeling problems, the approximation rate regarding the *input dimensions* and *dynamical properties* is more crucial, and the numerical verification here is performed only for low-dimensional tasks. Does the current analysis framework have the potential to solve this difficulty?
Thank you for your response. 

Note that I did not question the novelty of this work and also agree that the theoretical results are a great contribution, which is why I voted to accept the paper. However, I also remain of the opinion that the theoretical results do not offer a direct and very practical suggestion regarding design of new architectures. This is, because the proofs are indeed *not* independent of the width if you consider practical settings with multiple layers (chaining) and non-linearities in between. I do not want to suggest that such a proof should have been made, because it very likely is not possible. However, it remains not clear from this work, e.g. how much chaining would be sufficient with diagonal matrices and whether this would actually be a problem for Mamba, given that it a very deep model. 

I also understand that the contributions of this work are of theoretical nature and do not expect a very experimental section. However, I do still think that a bit more than Fig. 1 to support the theoretical findings would have been not only insightful, but important to underscore these findings.