Theoretical Foundations of Deep Selective State-Space Models
Authors: Nicola Muca Cirone
Antonio Orvieto
Benjamin Walker
Cristopher Salvi
Terry Lyons
Venue: NeurIPS 2024 poster (2024)
Keywords: theory
deep learning theory
SSM
RNN
neural controlled differential equations
signatures
kernels
Primary area: deep_learning_architectures

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.

Theoretical Foundations of Deep Selective State-Space Models
Nicola Muca Cirone Department of Mathematics Imperial College London
Antonio Orvieto MPI for Intelligent Systems, Tübingen Al Center ELLIS Institute Tübingen
Benjamin Walker Mathematical Institute University of Oxford
Cristopher Salvi
Terry Lyons Mathematical Institute University of Oxford
Department of Mathematics Imperial College London
Abstract
Structured state-space models (SSMs) gaining popularity effective founda- tional architectures for sequential data, demonstrating outstanding performance across diverse set of domains alongside desirable scalability properties. Recent developments show that if the linear recurrence powering SSMs allows for selec- tivity mechanism leveraging multiplicative interactions between inputs and hidden states (e.g. Mamba, GLA, Hawk/Griffin, HGRN2), then the resulting architecture can surpass attention attention-powered foundation models trained on text in both accuracy and efficiency. at scales of billion parameters. In this paper, we give theoretical grounding the selectivity mechanism, often linked to in-context learning, using tools from Rough Path Theory. We provide 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 closed-form description of the expressive powers of modern SSMs, such Mamba, quantifying theoretically the drastic improvement in performance from the previous generation models, such as $4. Our theory not only motivates the success of modern selective state-space models, but also provides solid frame- work to understand the expressive power of future SSM variants. In particular, it suggests cross-channel interactions could play vital role in future improvements.
Introduction
Sequence-to-sequee blocks are fundamental components of modern deep learning models for language. images, video, audio. time series, and genomics. For the last five attestit [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- sequence-to-sequene to-sequence blocks stemming from S4 [Gu et al., 2021] I]. SSMs achieve state-of-the-art results on long-rangg-reassonnng benchmarks [Tay et al., 2020] and show outstanding performance in various domain including vision [Nguyen et al., 2022), audio [Goel 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 lincarly 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 al., 2023].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

While standard SSMs were shown to be particularly powerful on signal processing tasks, their computation power limited: the core sequential mechanism of S4 equivalent a convolution (fil- tering) [Li et al., 2022a]. This represents a drawback in challenging domains such as text and genetics, where the ability to select data efficiently 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-arr 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 et al., 2023a], and [Feng et al., 2024] introduced minimal versions of GRU and LSTM as gated SSMs.
improved version of the LRU [Orvieto
Contributions At the core of the models discussed above is a time-ngrying dynamical system, where reasoning is performed through 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 differeetial equations (CDEs) [Young, 1936, Lyons, 1994, Kidger et al., 2020, Morrill 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 al., 2007] study expressivity.
1. In Sec. 3.1 we provide a framework for the analysis of (input-controlled) linear (in the hidden state) recurrences such as S4 and Mamba. This framework allows the use of powerful tools and results in the Rough Path Theory literature by casting a large family of SSMs as Linear CDEs driven by the two possibly nonlinear embeddings X + x and X + xx_ defining gates. Appendices A and E provide a largely self-contained exposition of the key theoretical tools now available to us.
2. In Sec. 4 we fully characterize the closure (i.e. the class of functions which can be arbitrarily well approximated) of our generalized models. This provides generalization of the results by Li et al. [2022b], Orvieto et al. [2023b], Wang and Xue [2023], who only consider the case of $4. The Mamba setting is more rich, complex, and relevant given the rising interest in selective SSMs.
3. We show (Thm. 4.2) that full expressivity can be obtained by training only linear layer on Linear CDE with random parameters, providing a direct link to kernel methods and reservoirs.
4. We point out (Thm. 4.3) that the recurrence is diagonal, as the case for Mamba, the closure is strictly smaller than in the general dense case. Interestingly though, the closure is a peculiar set of filters that unlock some specific context-dependent processing. Full expressive power is recovered by stacking multiple SSMs without MLPs in between (Prop. 4.5).
Our framework not only provides SSM architectures, but we also envision it to be useful tool in analysing, and perhaps developing, future architectural advances.
significant theoretical insight regarding some recently proposed
2 State-space Models
We describe here the structure of the main SSMe-based strategies for processing length-L input sequences of d dimensional tokens: x E IRdxL We denote by x, the b-th column of a (the E-th token) and by x² the i-th row of (time series for the i-th channel). We will write A for matrix-vector multiplication when this enhances comprehension, and use bold letters for "tensors" of order greater than (such as z E X.R N.X. introduced below).
2.1 Review of Modern SSMs
We start with quick simplified recap of $4 [Gu et al., 2021], the first SSM proposed in the literature, and then describe recent improved variants such as Mamba (in particular, the S6 block) [Gu and Dao. 2023]. We restrict our focus to the recurrent mechanism and invite the reader to refer to the original papers for a description of the token-wise operations following and preceding each block.

---

SSM basics and S4. Most' SSMs [Gu et al.. 2021, 2022] operate independently on input channels. Each time series x' E R' seen as the result of sampling latent continuous- signal X [0, 1] I at multiples of a channel-dependent stepsize A; > 0: A,t (²(),)) = 2zg. In $4,
each path X produces complex-value valued hidden state signal Z; [0, 1] - C. as
dZz = A Zie dt + B Xidt,
where A, = diag 01,1 04,2.- ... d,,N) is channel -speciffc diagonal N; x N, complex valued matrix and B E: C. is input projection shared across imput components i [d]. SSMs are based stable discretization of the continuous system above: each input sequence channel x' E R produces
sequence of hidden states
[Z,1 |2:2| ... [Z:L]] E CN follows:
Z A, 2 + Baxy,
where A, and B, are determined by the discretization technique and the chamnel-dependent stepsize A,, Under the commonly used Sero-Order Hold discretization'.
A, = exp(
B, = (A.AA)
- 1)A, x A,B.
(3)
Note 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-ting 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 real numbers, and linear projections C₁ : C - IR are performed to produce an output a sequence of tokens y E RRdx with the same dimensions
y/= : C; Zzdl
To conclude, we point out that the transition matrices A, 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., - - + imn (S4D-Lin") and a, = - (S4D-Real).
Mamba. As done in practice, let consider all channels' hidden dimensions N, equal to N. The Selective SSM (S6) powering the Mamba architecture [Gu and Dao, 2023] augments S4 with input-controlled matrices:
Z43² A,(a))) Z:.-- + (x
(4)
where the most crucial component (see in-context learning argument by Gu and Dao [2023]) is the dependency of the diagonal matrix (xzz) E R at timestamp é all input channels at timestamp É. This makes the operation A,(x;) Zag-1 effectively a gate. The dependency of A, Rd + RNNNNN xN on the input is achieved efficiently by letting A, in (3) be computed, at step E, as (1( where
: H, Ai(x) = softplus(a; x + (:) E
where is the scalar product and a E Rd, Bg RR Further, B Rd - R. is computed via shared between channels, linear map B E Nxd via B,(2)) = (B xx) (x())) E R Finally, each Zizz E RV- is projected to y/ R via a matrix C.. This step can also be done by means of output gating (C; function of the input), but we avoid this complication here as it can be seen as an architectural component outside the recurrence.
Remark 1.1. While each channel evolves separately, the laws of evolution are pointwise determined by all input features: A; and B; can be functions of we, and not just of a/. 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 al., 2023], and HGRN2 [Qin et al., 2024] leverage similar ideas, though they differ in parametrization and gating strategies.
'The LRU and SS instead build single recurrence operating on multidimensional (# channels) inputs. "This corresponds to: (i) considering continuous underlying signal X, to be piecewise constant, (ii) solving exactly ODE (1) and finally (iii) sampling Z, at the sample times of X.. Refer to Appendix F.
i denotes the imaginary unit V-I, to be confused with the index i.
'In practice, Gu and Dao [2023Juse low-rank projection to construct the A,s. In other words, the matrix T ....... a is low rank. Another distinction that Mamba has compared to S4, is that the A, matrices controlling the recurrence channels i 1,2,.. d, is now shared and can be thus referred to A.
3

---

2.2 Known properties of (non-linear) recurrences
The expressiveness of standard nonlinear RNNs of the form 2e Az( + Bxg, where a 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 -omoggnnggnn systems of differential equations driven by input paths. The argument used here is based on the celebrated Barron's '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 inveriiaiinntt as the input controls the recurrence eigenvalues. In this paper, we are interested in this hybrid setting. It worth noting that some work exploring Mamba's 'ss 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.
3 SSMs as Linear CDEs
The crucial component that unlocks in-context learning and selectivity in modern SSMs is the input- dependent stte-to-ssttte 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 recurrence which is linear in the hidden state, but potentially non-linea in the input. This class includes many recent 3SM-basee 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 unified, convenient, continuous-time framework (Linear Controlled Differential Equations). This allows to answer the following question:
"What is the most one can achieve using recurrence which is linear in the hidden state and potentially non- non-linear in the input?"
3.1 Linear CDEs
According to their continuous-time formulation, SSMs process input data sampled from a continuous path X [0, 1] + Rd. where d the number of channels. By X we denote the input channel i, evaluated at time t = [o, 1]. More formally, we consider input trajectories in the separable Banach space X = ([0, 1]: Rd)) of absolutely continuous IRd dimensional paths. In this space, one can write X fo X, ds since X E [[, 1); Rd); and the norm is || == fo |x,| ds.
To model gates (see Mamba in (4)), we introduce two maps transforming the path X, which output trajectories xx ex living in potentially higher dimensions: du and de
w X ((0, 1]: R",) ) X + C1,0(10, 1):
where we used the shorthand notation wx xx), {(X). Akin the notation for the i-the channel of X (i.e. X'), we denote by x. the i-th channel in wx
The role of the &, w functions which we denote gating functions will be clear very soon.

---

Definition 3.1 (Linear CDE). Fix N e N (hidden-see dimension), matrices A1, Ad, E RVV and B E Nxd, The hidden state 2* == ((x) is computed by the Linear CDE through linear (in the hidden state) differential equation driven by w, functions of the input path:
dZp
A dwl + Bdg
Z = Zo E R
(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: is sufficient to consider the setting d = 1, N N₁. The S4 model [Gu et al., 2021] in this case is dZ,- A Ze dt + B (X,dt), where A R NxN is diagonal. This can be written as a Linear CDE with
<t #=f[ x, E R
w =EER,
(6)
since dwt dt and dež X,dt. As the reader can promptly notice, here w is not function of X this will have 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 as Z = (zz) Z + (xx ax) where for generic timestamp features x E R2, we have A,(x) = (A. (x) (z) ~ (B-x) A, (x) and (,(x) = softplus(a, x 3,). Let us introduce a parameter > 0, and consider a; = 0z/ó. B. = 3./5. Let us further approximate the softplus function with a ReLU (a(x)) = (zLU(z) ~ log(1 + =))) )) to obtain (x) = a(ōā; + 88,) = exp(o +
aaā x + 3,)5. Therefore, as 5 + 0, one has (x) ())))) 0 + (ā;; x + 3,)8A, leading to the recurrence
(
ZizZ - + A. z (ā Iz + B.)ō + (B xz) zāo(ā; It + 8.)8.
As we show formally in Appendix plays the role of the differential dt. The equation above is the Euler discretization of the differential equation
N dz A, 7 aāā; X1 B.)dt (B xx) Xjo(ā; Xt + 8,)dt
where for each i, Z [0, 1] + R.V. These are Linear CDEs with carefully chosen and &:
wht = ff cān X, + 8.)ds Ch [ X'o X, + 3:)ds E Tdd.
Note that here the &, 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 by dz,- = 1Σ 1 Z + B dEX channels of the transformed input path wx are mixed in linear way in the recurrent step and stored in shared hidden state 2 This allows our framework to be more general compared 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,S be diagonal and non-zero only around Channel-specifee portion.
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 IR that can be uniformly approximated an arbitrary precision by Linear CDE of the form given in (5).
5

---

4.1 Characterization of the closure
The proof of the main theorem we present here (Thm. 4.1) is involved and requires tools from Rough Path theory; we provide 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, 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 SSMs, our results allow to precisely characterize the Linear CDE hypothesis class (i.e. the closure), thus to the answer the question "What the most we can achieve from recurrences which are linear in the hidden state?". We show that Linear CDEs can model, at fixed time I, arbitrary continuous functions of the whole seen inputs. Of course, understanding the diagonal setting with separate channel processing is of utmost impor- tance 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 7 E C1, 1], Rd) and any sub-interval [s, t] C [0, 1], we denote by ]s..] E C1.0(10, 1), IR) the path Mo. (u) "Yw - Yssuus where A b = min(a.b)
Theorem 4.1. Let X C. CLo(( 12 be compact and choose continuous gating functions W.E such that 5 witt = t and wi = t². Consider the Linear CDE model (5). Let W o be generic continuous functions from paths to real vectors:
V : C1,0000 11, Id R. Φ (CI.0((0,),RR4) + RR4.
There exist dense matrices Aq,.., Ad,, B such that, after a fixed final linear projection C E R the output Y CZZ is arbitrarily close, uniformly on X x [0, 11, to
I (W ) + [: ((W dex
where is the scalar product. Moreover Y? C7A is äself of form (7).
In Theorem 4.1, the A, are dense matrices constructed ad hoc for the proof. We show next that, with high probability, random one only has to choose the appropriate matrix C. This is 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.
matrices [LeCun et al., 2012] provide enough expressivity
Theorem 4.2. Under the hypothesis of Theorem 4.1, pick [A,],, idd (0, +o) and [Zo].: [B],, did ((,0,), 1). For any functional F : X x 0) > IR of the form (7) and c >> 0 it holds that
lim P [[(30 RlxN such that
F(X,t) - CZ s sc]] =1.
sup (X.1)exx(o.1
N N
4.2 Intuition on the closure result: role of gates
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 w.
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 E. In fact, their setting is restricted to w and & = fe X, x,ds. This also the case for S4, S5 and the LRU which are linear RNNs at test time. Then the only information contained in W[s.a] is the increment t -
(() + fu d0 - s) X,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.
so that family (7) reduces to
{ {(x
"These assumptions of technical nature and can he relaxed the cost of talking about tree-like equivalence of paths of. Hambly and Lyons [2010]. Intuitively w X,1 t ensures general X X-uniformity while w. x.2 = t2 ensures [0, 1] unifformity

---

Take without loss in generality" wx = X,. The first term in the function class (V((().)) + Jo ((((a))) )
How does a Linear CDE process inputs?
is already enough establish that the output C'ZN is nonlinear function of all previously seen inputs X - - could be set to zero. The term V (())o.)) is however non-trivial only in the Zo # 0 case (cf. Appendix B): picking &x
R for
all t indeed leads to dzz EE A,du; Z which is evolving only Zo + O. While this setting is interesting and suggests a clear direction for future research, case more similar to Mamba (see Sec. 4.3) is Zo = 0 and e = Jo X.ds. Here, can approximate arbitrarily well outputs of the form
{(x00~
((00)()(())))) ((((s.)
X,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 linear combination of previously seen inputs, but weights are not predetermined as in Linear RNNs (S4) they a function of the context. A similar yet less powerful processing is happening in the diagonal setting, which we explore next.
4.3 The Diagonal Case
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 Ai..., Ad, are constrained to be diagonal, the requirements w. = t, w/ f can be dropped and the closure reduces to
(x,0) v(})) + 1/ Ólwg - w() dE
for continuous vb Rd_ - IR and Φb Rd= + Rdc.
Compared to the dense setting, the effect of diagonality pretty clear. Let us again assume w X,
and ex = So X, ds for simplicity, While f6 (X(ss)) X, ds unlocks filtering based on the entire trajectory [|s,) the diagonal case term fo o(x, Xx) X,, ds indicates that filtering coefficients can only be chosen by comparing two elements of the (potentially transformed through w) 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 finite number of tokens are compared at each layer. While a smart choice gating functions w, & can improve on the learned nonlinear filtering strategy (e.g. based filtered input versions 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
(xx,0) + Σ bi(W + Σ f bilwit - -wiit) dex.
(10)
for continuous vy : IR + R and Φ, : RR R.
4.4 Chaining Diagonal CDEs
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 previous Linear CDE, and repeating this procedure K times (ef. Appendix C).
Let ignore the terms t, t at this stage; their role is purely technical due to possible path equivalences.
7

---

Proposition 4.5, Assume compact X C C,, 1): For any functional F X |0,1] Rf of the form (7) and > O there exists a sequence of linear maps Ws E RM XNx, diagonal weights A !a and B(k) for the following family of chained diagonal Linear CDEs
d+Ms
W k. X
z = dZ
dzk+1x
Σ
A
d
+ BBk+1) dX, E N
(11)
such that eventually, as + oo, there exists Cg RIXNN with
F(X,t) -G S
sup (Xx))xx((o.]
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 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.
4.5 Proof Idea Signature expansion
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 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 al., 2007, Kidger et al., 2019, Fermanian et al., 2023], 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 path y E ((,, 1]; 12 and define Wa, a, the of words (i.e. ordered sequences) in {1.....d, d 7. The signature transform is the following infinite collection of scalar iterated integrals Sig(?)s, (Sig()) JEW
Sig(n))
((. (6))) du.,..duu... Fas
Jscors..euneet
A classical result from rough path theory states that 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 A1, Ad, and B, the unique solution Linear CDE (5) is, using the notation A Ai., Ai....Ai given by
dg
A,B, [ Sig(w M e R.
2 = Σ A,Zo Sig( 00
Σ
Σ JEWa
(12)
IEW
Notice that the previous result does not rely any assumptions the nature of Zo. A,. and B; for any such choice the result is a time-independent linear map on feature vector T(X) )).. =
(Sig(w>)02 Jo l Sig(w>) ),, dexx*) (I.)). where the index (T,i) over W, x (1. The main takeaway is that any linear projection Y.* CZ is written as an (infinite) linear combination of the terms in T(X)u,t- This means that the expressive power of such schemes is almost completely determined by the gate w, 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 indeeddndeenndentt (i.e. W t) then precludes the use of higher order statistics of X.
5 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 functional of type
"o when we write 1 E Wa, we mean = irdz 12.-.-m for some integer M 2 0 and letters i.. (I..., dr ). then li will be the word iid2 .ai for i E (L....,dy}, dr).
8

---

(X,t) + (.(W where the map V is changing with time as well, this is an example of 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 v/ 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 Vys.
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 vr, We defer the proof to Appendix D.
Proposition 5.1. Fix a compact set K. S X and continuous w. E with x.1 = t. Then for all > 0 and all causal 8 continuous mapping G : Ci,o ([0, 1]. IR ) x [0. 1] + E there exist an integer N 2 0, some MI. F : IR-N + IR, and parameters Zo E RV A, E N B E RRd such that
[F(2)) - G(w t) < e. (X.1)EXx(o.]
sup
(13)
6 Empirical Validation
Code to reproduce all of our experiments can be found at:
attps://githun comlii..ccom//aa com/Benj
ssm-eetttiiieeeeeeeeesesse and--ndd-ll and-linear-coe cdes
Datasets. The first task is based on 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 '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 's target is an area integral Ju Jo" dX.dx? v. and the 3D dataset's 's target is volume integral Jo J0" S" dx dx!dx3dx3
The second task is the AG benchmark from Merrill et al. [2024]. It tests models on state-tracking, crucial ability for tasks involving permutation composition, such as chess. The dataset comprises sequences from the group of even permutations on five elements, As, 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) $4 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 $4 or Mamba recurrences with linear mixing layer GeLU in-between, and a linear readout, (vii) a linear CDE with gates w/ & = X2) 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 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 s recurrence obtained using the Tsit5 adaptive ODE solver, with an absolute and relative tolerance of 10-2. The The linear CDEs linear readout is optimised via ordinary least squares.
On the Aş benchmark, consider five models: linear CDE, 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-seqqencc 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 hidden dimension of 256. Note that the IDS4 recurrence introduced by Merrill et al. [2024] corresponds directly a linear CDE with dense transition matrices. hence we did not include the model as a baseline.
A causal map is one which does not "look in the future" ef. Appendix D.
9

---

Mamba Depts
54 Dzpth
Prsiicing Zore Randum Unear
Mamba Depts
54 Dupth
Results. Results on the anti-symmetrin signa- ture prediction task (Fig. 1) empirically demon- strate number of the theoretical results pre- sented in this paper. Firstly, as discussed in Sec. 4.2, recurrences which are linear in the input, such as S4, require a non-linearity in-
Hamba Depen Nominna
S4 Depth Nonthear
Area (2D)
Volume (3D)
Validation RMSE
between the layers to perform well. Further- more, 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 di- agonal matrices is improved by stacking. Ad- ditionally, the inclusion the non-linearity in- between the Mamba layers does not improve per- formance, as the recurrences themselves are ex- pressive 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.
Training Steps
Training Steps
Figure Comparison of the Linear CDE, Mamba, and S5 on the anti- signature prediction tasks. For each model, we plotted the mean and range of the validation accuracy over 5 independent runs.
Minimum Blocks Required
Fig. 2 is plot of the results on the As benchmark. The figure shows that the number of blocks S4, Mamba, and the transformer require achieve greater than 90% validation accuracy grows with the sequence length. In fact, given model archi- tecture, none of these models could achieve greater than 90% validation accuracy for sequences of length twenty". On the other hand, the RNN and Linear CDE are able achieve greater than 90% validation accuracy for all lengths considered us- ing only one block. These empirical results further validate Thm. 4.3 and Prop. 4.5; there exists gap expressivity between diagonal and dense transi- tion matrices, and stacking is required to recover the expressivity. Furthermore, they provide empir- ical evidence that even for simple state-tras trate-tracking problems, the number of blocks required can grow quickly with sequence length.
Mamba
S4
Transformer
RNN
Linear CDE
18
20
Sequence Length
Figure 2: For each sequence length, the plot shows the minimum number of blocks required to achieve at least 90% validation accuracy, with each grey band corresponding a number of blocks. Missing points mean the model did not achieve least 90% valida- tion accuracy with 4 blocks or less.
7 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, 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 capture high- order 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 non-diagonality as potential source of improvements. We believe that light and efficient channel mixing the recurrent block might already unlock the modeling of higher-order statistics.
Limitations. The current framework examines expressivity from a continuous-ting time perspective with real-valued inputs. The RNN literature suggests that finite precision often plays significant role in practice, making an interesting direction for future exploration. Additionally, although dense transition matrices shown to be theoretically and empirically more expressive than diagonal ones, their increased computational cost makes them impractical for large-scale models.
"Merrill et al. [2024] show that with tailored architectures, $4, Mamba, and a Transformer can achieve over 90% validation accuracy on length-20 20 sequences using 4 blocks. However. in our experiments we wished to keep the architecture consistent between models, only changing the sequence-to-seen sequeencc model.
10

---

Acknowledgments
Antonio Orvieto acknowledges the financial support of the Hector Foundation. Terry Lyons was funded in part by the EPSRC (EP/S026347/11, in part by The Alan Turing Institute EEP/551012/11, in part by the Defence and Security Programme, in part by the Office for National Statistics, and in part by the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA), Benjamin Walker was funded by the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA). The authors would like acknowledge the use of the University of Oxford Advanced Research Computing (ARC) facility in carrying out this work. http://dx.doi.org/1.... 12te1:00022///oooo2255525555
References
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Neil Houlsby, Sylvain Gelly, Xiaohua Zhang, and Jakob Uszkoreit. An image worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
Albert Gu. Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2021.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. In International Conference Learning Representations, 2020.
Eric Nguyen, Karan Goel, Albert Gu, Gordon W. Downs, Preey Shah, Tri Dao, Stephen A. Baccus, and Christopher Ré. S4nd: Modeling images and videos as multidimensional signals using state spaces. Advances in Neural Information Processing Systems, 2022.
Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré. It's raw! audio generation with state-space models. International Conference on Machine Learning, 2022.
Chris Lu, Yannick Schroecker, Albert Gu, Emilio Parisotto, Jakob Foerster, Satinder Singh, and Feryal Behbahani. Structured state space models for in-context reinforcement learning. Advances in Neural Information Processing Systems, 2023.
Nicolas Zucchet, Robert Meier, Simon Schug, Asier Mujika, and João Sacramento. Online learning of long-range dependencies, 2023.
Sepp Hochreiter and Jurren Schmidhuber. Long short-term memory. Neural computation, 1997.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint urXiv:1406. 1078, 2014.
Eric Martin and Chris Cundy. Parallelizing linear recurrent neural nets over sequence length. arXiv preprint arXiv: net.: 2017.
Jimmy T. H. Smith, Andrew Warrington, and Scott W. Linderman. Simplified state space layers for sequence modeling, 2023.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convolutional models great on long sequence modeling? arXiv preprint arXiv:2210.092998 2022a.
Junxiong Wang. Jing Nathan Yan, Albert Gu, and Alexander M Rush. Pretraining without attention. arXiv preprint arXiv:22 10544 2022.
Daniel Y Fu, Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In The Eleventh International Conference Learning Representations, 2022.
11

---

Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language models. arXiv preprint arXiv:2312.049277 2023.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2023,
Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, Kranthi Kiran GV, et al. Rwkv: Reinventing rnns for the transformer era. arXiv preprini 2xXi::3355.30455 2023.
Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models, 2023.
Tobias Katsch. Gateloop: Fully data-controlled linear recurrence for sequence modeling, 2023.
Songlin Yang, Bailin Wang, Yikang Shen, Rameswar Panda, and Yoon Kim. Gated linear attention transformers with hardware-efffcient training. arXiv preprint arXiv:2312.06633, 2023.
Zhen Qin, Songlin Yang, Weixuan Sun, Xuyang Shen, Dong Li, Weigao Sun, and Yiran Zhong. Hgrn2: Gated linear mas with state expansion. arXiv preprint arXiv:2404.07904, 2024.
Soham De, Samuel L. Smith, Anushan Fernando, Aleksandar Botev, George
Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, Guillaume Desjardins, Arnaud Doucet, David Budden, Yee Whye Teh, Razvan Pascanu, Nando De Freitas, and Caglar Gulcehre. Griffin: Mixing gated linear recurrences with local attention for efficient language models, 2024.
Antonio Orvicto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXivv2303.06349 2023a.
Leo Feng, Frederick Tung, Mohamed Osama Ahmed, Yoshua Bengio, and Hossein Hajimirsadegh. Were rnns all needed?, 2024. URL htttt://s////iii www.aaawww...oooooooraaaeeooeerr org/abs/ abs/2410..00...///////////////// 012001.
Laurence C Young. An inequality of the hölder type, connected with stieltjes integration. 1936.
Terry Lyons. Differential equations driven by rough signals (i): An extension of an inequality of Ic young. Mathematical Research Letters, 1(4):451-466 1994.
Patrick Kidger, James Morrill, James Foster, and Terry Lyons. Neural controlled differential equations for irregular time series. Advances in Neural Information Processing Systems, 33:6696 6707, 2020.
James Morrill, Cristopher Salvi, Patrick Kidger, and James Foster. Neural rough differential equations for long time series, In International Conference on Machine Learning, pages 7829-7838. PMLR, 2021.
Adeline Fermanian, Pierre Marion, Jean-Philippe Vert, and Gérard Biau. Framing mnn as kernel method: A neural ode approach. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 3121-3134. Curran Associates, Inc., 2021. URL https: /ttppe://proeeeeinggg neurips. cc/p Paper. pdf.
aper
Cristopher Salvi, Maud Lemercier, and Andris Gerasimovics. Neural stochastic pdes: Resolution- invariant learning of continuous spatiotemporal dynamics. Advances in Neural Information Processing Systems, 15:1333-1344, 2022.
Melker Hoglund, Emilio Ferrucci, Camilo Hernandez, Aitor Muguruza Gonzalez, Cristopher Salvi, Leandro
and Yufei Zhang. neural rde approach for continuous-time non-markovian stochastic control problems. arXiv preprint arXiv:2306.1 14258, 2023.
Benjamin Walker, Andrew D. McLeod, Tiexin Qin, Yichuan Cheng, Haoliang Li, and Terry Lyons. Log neural controlled differential equations: The lie brackets make a difference. International Conference Machine Learning, 2024.
12

---

Terry J Lyons, Michael Caruana, and Thierry Lévy. Differential equations driven by rough paths. Springer, 2007.
Zhong Li, Jiequn Han, E Weinan, and Qianxiao Li. Approximation and optimization theory for linear continuous-time recurrent neural networks. J. Mach. Learn. Res., 23:42-1, 2022b.
Antonio Orvieto, Soham De, Caglar Gulcehre, Razvan Pascanu, and Samuel L Smith. On the univer- sality of linear recurrences followed by nonlinear projections. arXiv preprint arXiv:2307.11888. 2023b.
Shida Wang and Beichen Xue. State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory. arXiv preprint arXiv:2309. 13414, 2023.
Albert Gu, Ankit Gupta, Karan Goel, and Christopher Ré. On the parameterization and initialization of diagonal state space models. arXiv preprint arXiv:2206.1189, 2022.
Nicolas Zucchet and Antonio Orvieto. Recurrent neural networks: vanishing and exploding gradients are not the end of the story. arXiv preprint arXiiv:4055.21664 2024.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances in neural information processing systems, 33: 1474-1487, 2020.
Hava Siegelmann and Eduardo D Sontag. On the computational power of neural nets. In Proceedings of the fifth annual workshop on Computational learning theory, pages 440444,, 1992.
Samuel Korsky and Robert C Berwick. On the computational power of rnns. arXiv preprint arXiv: 06349, 2019.
Joshua Hanson and Maxim Raginsky. Universal simulation of stable dynamical systems by recurrent neural nets. In Learning for Dynamics and Control, pages 384-392. PMLR, 2020.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-9455 1993.
Corentin Tallec and Yann Ollivier. Can recurrent neural networks warp time?, 2018.
Joshua Hanson and Maxim Raginsky. Universal approximation of input-output maps by temporal convolutional nets. Advances in Neural Information Processing Systems, 32, 2019.
Stephen Boyd and Leon Chua. Fading memory and the problem of approximating nonlinear operators with volterra series. IEEE Transactions on circuits and systems, 32(11):1100-1161 1985.
Samy Jelassi, David Brandfoobrener, Sham M Kakade, and Eran Malach. Repeat after me: Trans- formers are better than state space models at copying. arXiv preprint arXiv:2402.01032 2024.
William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. arXiv preprint arXiv:2404.0885 00889 2024.
Ben Hambly and Terry Lyons. Uniqueness for the signature of path of bounded variation and the reduced path group. Annals of Mathematics, pages 109-167, 2010.
Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robet Müller. Efficient BackProp. pages 9-48. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 118-3-642-35289-8 doi: (0100799778--4--5557
3. URL attps:///o// htt:///oooooroo////// 09700079978-0 3- 2-642- 02122-3529--8 8_3.
Mantas Lukoveviius and Herbert Jaeger. Reservoir computing approaches to recurrent neural network training. Comput. Sci. Rev., 3: 3:127-149, 2009. URL https: //api. sww.ntccccoollarr wwwechollarrro/ooooooooooooo IpusID::54006.
Christa Cuchiero, Lukas Gonon, Lyudmila Grigoryeva, Juan-Pablo Ortega, and Josef Teichmann. Discrete-time signatures and randomness reservoir computing. IEEE Transuctions on Neural Networks and Learning Systems, Forthcoming, 04 202 doi:
13

---

Enea Monzio Compagnoni, Anna Scampicchio, Luca Biggio, Antonio Orvieto, Thomas Hofmann, and Josef Teichmann. On the effectiveness of randomized signatures as reservoir for learning rough dynamics. In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1-8.
IEFE, 2023.
Patrick Kidger, Patric Bonnier, Imanol Perez Arribas, Cristopher Salvi, and Terry Lyons. Deep signature transforms. Advances in Neural Information Processing Systems, 32, 2019.
Adeline Fermanian, Terry Lyons, James Morrill, and Cristopher Salvi. New directions in the applications of rough path theory. IEEE BITS the Information Theory Magazine, 2023.
Thomas Cass and Cristopher Salvi. Lecture notes on rough paths and applications to machine learning. arXiv preprinl arXiv:2404.0658, 2024.
Peter K. Friz and Nicolas B. Victoir. Multidimensional Stochastic Processes as Rough Paths: Theory and Applications. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2010. doi: 10.1017/CB09780511 1845079.
Adeline Fermanian. Embedding and learning with signatures, 2020.
Kuo-Tsai Chen. Integration of paths-a faithful representation of paths by noncommutative formal power series. Transactions of the American Mathematical Society, 39(2):995-407, 1958. ISSN 00029947. URL http: http:://ww.jstor org/ http:/saalee//ee 19931199.
Cristopher Salvi, Thomas Cass, James Foster, Terry Lyons, and Weixin Yang. The signature kernel is the solution of goursat pde. SIAM Journal on Mathematics of Data Science, ((3):873-89) 2021a. doi: 10.1 13794 URL https: //oi org/10. 1137 11377200136677999
A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer US, 2011. ISBN 9781441990969, URL https: //books google . co uk/books?ide bX3TB=ААQBAJ.
Maud Lemercier, Cristopher Salvi, Theodoros Damoulas, Edwin V. Bonilla, and Terry Lyons. Distribution regression for sequential data, 2021.
Cristopher Salvi, Maud Lemercier, Chong Liu, Blanka Horvath, Theodoros Damoulas, and Terry Lyons. Higher order kernel mean embeddings to capture filtrations of stochastic processes. Advances in Neural Information Processing Systems, 34: 16655-1676,,, 2021b.
Thomas Cochrane, Peter Foster, Varun Chhabra, Maud Lemercier, Terry Lyons, and Cristopher Salvi. Sk-tree: systematic malware detection algorithm on streaming trees via the signature kernel. In 2021 IEEE international conference on cyber security and resilience (CSR), pages 35-40. IEEE, 2021.
Cristopher Salvi, Maud Lemercier, Thomas Cass, Edwin V Bonilla, Theodoros Damoulas, and Terry J Lyons. Siggpde: Scaling sparse gaussian processes on sequential data. In International Conference on Machine Learning, pages 6233-6242. PMLR, 2021c.
Nicola Muca Cirone, Maud Lemercier, and Cristopher Salvi. Neural signature kernels as infinite- width-depth-limits of controlled resnets, 2023.
Zacharia Issa, Blanka Horvath, Maud Lemercier, and Cristopher Salvi. Non-adversarial training of neural sdes with signature kernel scores. Advances in Neural Information Processing Systems, 2023.
Alexandre Pannier and Cristopher Salvi. A path-dependent pde solver based on signature kernels. arXiv preprint arXiv:2403.11755 2024.
Georg Manten, Cecilia Casolo, Emilio Ferrucci, Spren Wengel Mogensen, Cristopher Salvi, and Niki Kilbertus. Signature kernel conditional independence tests in causal discovery for stochastic processes. arXiv preprint arXiv:2402. 18477, 2024.
Patrick Kidger. On neural differential equations, 2022.
14

---

Guillaume Dubach and Yuval Peled. On words of non nermitant random matrices, The Annals of Probability, 1984 1916, 2021. doi: 10.121420-AOP1496 URL https://doi.ooom http:///oooorr/////////// 10 .1214/20-AOP 10000000P1499
Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22, 2003. URL https: //ap:i//pppp. http://ppp...maaicccsooeooo semanticccholar wwwehhoorrrrrrooeoooeeoee org/Cory usID: 10327788
Christa Cuchiero, Lukas Gonon, Lyudmila Grigoryeva, Juan-Pablo Ortega, and Josef Teichmann. Expressive power of randomized signature. In The Symbiosis of Deep Learning and Differential Equations, 2021b.
15

---

A Introduction to Signatures
This initial section of the Appendix is devoted to a brief introduction the topic of Signature Transform. For more in-depth account we refer the interested reader to Cass and Salvi [2024].
A.1 Intuition Controlled Differential Equations
In the simplest setting of smooth paths a CDE a differential equation of form
dz,
dX, dt ( Z.). Z.). Zo E R
==
F
where X [0, 1] + _ is known smooth path to which we refer control, Zo the known initial condition and Z [0, 1] + R" the unknown solution.
The natural generalization is the following: assume have two spaces R&d and RRd, X Ci (10, 1]: [Rdx), ) Z E (i 1]; Rdd, ), F Rd: - L(TRR= IRd)) and Zo E IRd: We say that (Z, X, F, 70) satisfy the CDE
dz, = F(Z,)dX,, Zo Rd
whenever
Z, Zo / F(Z.)dX,
The theory of Rough Paths has its origins in the study of such types of differential equations and provides theoretical framework to define and work rough settings ie, when X kust BV but even a-Hölder for E (0, 1) of. Friz and Victoir [2010].
Assume thus to have the CDE
dz. Σ vi(Z)) Zo Rd.
for sufficiently regular vector fields V, and X E ((0, R².) Given a smooth f R R. by the change of variable formula (i.e. fundamental theorem of calculus) we have
f(2.) = f(Z)) + Σ ( V.f(Z.)
where Vif(z) = df)]V((=)). Iterating this procedure on the V,fs, i.e. substituting in the previous equation the analogously obtained equality
Σ [ (V((
V.f(Z.) V.f(Zo)
$=1
we get
= = + Σ Vi)(Z)) L' dx.
d
d 1'' [ (V,V/((2))x//xx +
Σ 1-21
Keeping with this procedure for N steps we get
N + Σ Σ Vif(Zu)
/.. dx axth + RN
= =
Jmn
12
where I (i1,... ix) runs through the multi-indices, Vif = V4, Vi, V.. and
f.../
Rx(1)= = Σ
Vi ... -
...d
[J| scup Cu
16

---

As one can imagine, under reasonable regularity assumptions, the remainder goes to 0 as N + 00 and at the limit
[(2))=((2)) + Σ Σ ViJ(Zo) 7
dx
dx ... uk
SKM <o
This is a remarkable result: to know the solution Z, to the original CDE it suffices to know the quantities f for all multi-indices and in the coordinate maps, together with the iterated integrals
Sig(X) =
dxu u1
dx
This observation is at the core of Rough Path Analysis, the theory can in 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 expand and make rigorous the arguments of this section the case of affine vector fields.
A.2 Basic Definitions
Denote by (Rdjon = Tdd 60 ... s TRdd the tensor product of n copies Rd. set (IR")@0 = TR. Let T(E Dx (R2) be the tensor algebra equipped with sum and tensor product.
Definition A.1. Let fei.....cdl cd} be the canonical basis of Rd then
{ei, @ ... @ eig (i i [d]*}
a basis of (RR)) We equip (Rd) with the inner product ( (RujO defined basis elements
as
(e,, @ ... & Ci en 2 @jL)(R = jr.....a))
(1.....)))
We extend this product to 7(Rdd) by
B)T(R)) =
Σ k=
(ax, (R)
where A = (ao, ......) and B = (bo, bI....)
Note how for any A, B E T(R4) we have (A B B ( (A, ()rron(ere))) we refer to this as to the coproduct property.
Definition A.2 (Infinite Tensor Algebra). The infinite tensor algebra is defined as the space T((R)) := II ( equipped with the operations and @ which act in the natural alge- braic way; its elements are called tensor series.
It is easily that (T((R))), +, ④) is algebra with unit 1 (1,0,0,...) and we endow it with natural product which inherits the coproduct property.
Another point of view could be taken the definitions of these spaces, one that we will prefer later on. If we define Wa be the set of words in d letters then T((R)) R., T(RRd) is the subset of such functions with finite support and
(A, B)(())
= Σ A,Br = Σ
Σ k=0 7|
A
JEW
where |/] is the length of the word 1. The empty word, the only one with length 0, is denoted by () and corresponds to the basis element of (Rd) this view the tensor product coincides with concatenation words accordingly distributed and the closure T(Rd)) with respect its product just the @ space 1 (WW.).
17

---

Definition A.3 (Signature), Given y (1, R+) and s, E [0, 1] s.t. S t, the signature Sig(7)sa E T(R))) of the path over [s, t] is defined as
S... 17 8 ... 2 drup ...)
Sig(7)s,r = (1,
(14)
8 SCM <oEEE
Equivalently Sig(r)s, is that element of (WW)) defined recursively on words as
Sig()))( =1, Sig(n) = Sig(?)),,
(15)
A.3 Notable Results
Here present some notable results of which will make use through the paper. We omit the proofs they can be easily found the suggested references.
The first result is about bounding the norm of Signature entries:
Proposition A.4 (Factorial Decay Rate). Given E CL,((O, 1]; R.). for all k 2 and s, E [0, s.t. $ S one has
/ ② .... d
(16)
k!
(Bot)ok
The most important fact about Signature is that it acts as the basis for a Taylor expansion path space. In fact just 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 C1,0(1,, 1): compact such that for any y E K it holds 7t = t. For any F E (K;R) and e > there is an integer N such that
sup [F E asSig( se 7eK
(17)
|A|SN
for some finite sequence (az))ir SN of real numbers.
Remark A.6. There no magic in this result, it 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-interee intervals of [0, 1] in such a way to still be able to consider them meaningfully as elements of ([0, 1]; IRd), this is done in the following way:
Definition A.7. Given any path E C1,o((O, 1]: Rdd) we define its restriction sub-interval [s, d] C [0, 1] as the path Ye.4] Ci, 1]; RR) with values
0
<f
(r) = Pr 7s
ifs St
(18)
1/t
%
ifr t
This definition is such that the following important equation holds
Sig(7)..r = Sig(M).4))o..
(19)
With 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.
Lemma A.8. Assume w, 7 E C1,0((0, 1]; Rd+2) with wt = 7 = and w/ = ?? = t2, Then
Sig(w)s,t Sig())<.e' = w|s.1| = 71.0000
(20)
Here the integral is intended in the Riemann Siemman--Sjeltes sense.
18

---

Proof. The if part is follows from Sig(r)..: - Sig(N)sa) Jo,1. For the only if part. = s' and = t' the statement holds; this is because if the signatures over the time interval [s, t| of two tume-augmented paths are equal. then the two paths must be equal on [s, f). We now show that augmenting the path with e and imposing equality of signatures, implies s = s' and = t', which will in turn allow us to conclude the proof by the previous remark. Assume Sig(w)s, Sig(7) s'e e in particular we must have
[ d(r?) = 12 - =2- == =(1)²² - -6))² = {" d(r²)
(21)
[ d(r) =t t'
d(r)
(22)
which reduces to the system
2 g² = (1 (s')²
t + 8
2t = 21'
8-8= 8
1- 8 =
28 2
Hence it must be true that / - l' and = 8.
19

---

1) B Expressivity
B.1 Model Recap
In the body of the paper we have presented the main results with the simplified assumption of 2 = at best 7 Zo Lee. with initial value independent from the input. In this appendix will carry on the proofs in a more general setting in which Zg is allowed to be input-dependent, as previously discussed the choice of initial value is, in contrast to the classical setting, meaningful inasmuch allows to approximate linear maps on the signature of w In order to do so we have to introduce a new gate, the initial value gate, in the form of map
(+)o X + IR
(23)
X + Xo
Despite the notation, there is no reason why (X), 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 time-series nature.
To recapitulate, the general setting of our models is the following: a topological input space space X,
(-) Rd
((-oo-gate) (w-gate)
w x + C,,, 1]; Rd)),
x + C1,0 1]; Id))
(f-gate)
where all the gates are continuous functions on X. The space X does not have to be space of paths, a topological structure suffices, as long as the gates (.),.w, w. are well defined and continuous. Remark B.1. Typical examples for the choice of gates are X space of paths and
(X), =0 w. =t 5² = L X,ds
(S4)
[' so softplus(aX, + f) <x = l softplus(aX, + X)
(X)o = wp -
(Mamba)
Then the main object of study, "gated" Linear CDEs, are defined as: Definition B.2. Fix gates w, & above, N E N. matrices {A du (A, E RNNN),
B E R.N. C Nxdo The corresponding Linear CDE is the functional
Z: + ( 1]: )
(24)
dw
2/ = CXo,
A, du + Bdg
(25)
B.2 Main Result Statement and Strategy
Here we present the unified expressivity result in its most general form:
Theorem B.3. For any compact set IK C X and continuous gates w.). with witl and x.2 =t? 2. For any e >> and any
Fe (x,t) ((())))>W(()()))) Xo S' (wff))) dex
(26)
where V C (C Rda) and & E (C ),te,, there exist a choice of hidden dimension N 2 1 and parameters E N A E NNN Xxde C IR Ndo such that
sup
F((X() (v, 2i Se
(27)
(X.0)EXx(o.) [0.1]
Moreover generic parameters suffice with high probability the sense that under LeCun initialization
[A üd N
N Cn.jr Br,; id N(
20

---

the following holds:
lim P[3u E CR (27) holds] N-000
the A,S constrained be diagonal, often is the case in practice, the requirements wi t, wi² =t can be dropped and the existence result only holds with
F (x. ((wF) No + S Ōlw?, wa) de
(28)
for v E (RL,, and & (R
Moreover in both the dense and diagonal cases the "reverse" also holds in the sense that, given any choice of matrices A., B, C. there is an c-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 seen as linear functions on certain terms of the Signature Transform.
how linear functions the 7,8 can be
2. Such terms define a feature map ((X)a Jo. which generates a Reproducing Kernel Hilbert Space H. (o.o.... This abstract space acts an upper bound expressivity: linear functions on Ze always belong to its closure (in uniform norm), independently dimension and weights chosen, hence they cannot reach what functions in H, (/())oww.) can't approximate.
3. The full expressive range of H. Po.0).007 is shown to be captured by generic Z,s.
4. Diagonal systems are shown be restricted to a subset of the H, ())o....) of which they capture the full expressive range.
B.3 Main Result Proofs
B.3.1 An expansion for Z
Proposition B.4. For any choice of A ERNNN B R and C Nxdo, the unique solution
to
du
dz Σ
d, + Bag
(29)
i=1
2 CXo E R.
is given, using the notation
Arj Aj by
do
ArB; I' (ig(w)) E EN
2
Σ A,C, XiSig(w") 16.t + Σ Σ
(30)
IEW
TEWaL
Notice here ArCi, ArBj N and XiSiggu No.. So Sig(w>) ya E RR
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.
B.3.2 The feature map T and its RKHS
The expression in (30) is linear map on a feature vector given, at time 1, by
T(X), := (/SSig(W>) Yo. /" Sig(w>),,de) : [dal. I W Wa,5 E [de]
(31)
This feature vector can be understood as tensor in the following way:
21

---

Definition B.6. Let W de be the set of words in the alphabet
dd = fe:)i=i,.... U ((e)) j= de U
Fixed the gates (-)o, wi we define T(X): [0, 12 (W ((AAdo the unique solution to:
d
de Σ
dus
o( = Σ Xie; +
+
T(X)o,a di @ E
(32)
j=1
In fact one readily that the only non-zero terms of T(X)o, defined as above
(T(X)o,s ei) = X
(T(X) e, 2 (7
(T(X),,s,
@ G7 = X Sig(w>)of
(T(X)a, e)) = ex,s_ = ( dÉ2
(T(X)a,s Ef 2 57h) [/ (T(X) )o,s @ dw) =f" f" Sig(w>) dep
- -f" Sig(w>) du du de S Sig(w Y/, dex
This is similar to the tensor-valued CDE defining the signature as a tensor ie.. Salvi et al. [2021a]
Sig(w)o. f Sig(w)o, @ dw,
with the addition of two terms to track Xo and gx. One could also understand T(X),,: as sub-tensor
of
Xo @ Sig((w>, )x
but in doing this one would have explicitly ignore most the terms of this vector; the CDE (32) does exactly this, but implicitly. In any case the subtensor view shows that 7" X x [0, 1]² + (WWa, de well defined and continuous.
To the feature map To))o. with values the Hilbert space (WW is then associated a Reproducing Kernel Hilbert Space Berlinet and Thomas-Agnan [201 1], where the Kernel is the one induced by the product, which we denote by
H, )o.w. CX;
(33)
Classical RKHS theory tells us that we can characterize its elements as: Proposition B.7. A map F())= K IR an element of H! ())oen and only it is of the form
F(x), = Σ (a Sig(w Do.e) + (,03, (..(ii()...)ddd"" d
do
de
(34)
$=1
for az a, E 12(1 (W..). Moreover [IF(-)) (0 mow is equal to the minimal value of
|a (arl)) || (88llP
taken over those B for which the above equality holds.
Signature kernels Salvi et al. [2021a] are a class universal kernels on sequential data which have received attention in recent years thanks to their efficiency in handling path-dependent problems Lemercier et al. [2021], 1], Salvi et al. [2021b], Cochrane et al. [2021], Salvi et al. [2021c], Cirone et al. [2023], Issa al. [2023), Pannier and Salvi [2024], Manten et al. [2024].
Just as signature kernels, the kernel associated to ((X) )o. can be explicitly written as the solution of two-parameter CDE:
22

---

Lemma B.8. Let (s,t) = u. ()))) then
(s, = (Xo, Yo) + (5x [ 1- [ 13 (ddwy dutt)
(35)
or, directly in terms of Signature, also
(s, = (Xo, Yo) (Sig(WS)ooo... Jo,,, Sig(w")os) + fr I (Sig(w") Sig(w) (r (de)) det)
(36)
Proof. The first expression follows immediately from (32) the second one by summing the products of (o)),,s 's and T(Y)o, i 's entries given above.
Definition B.9. Define the space ((.1))
_ CX x [0, []:1] as the space of functions of form
do
de
/ (3) Sig(w)),.)
(X,1) +
Sig(w
Σ 5=1
(37)
for ag 3g 12 (W....)). ). Thus for all [0, and F E Halunn it holds F(,t)) E H. Nown
B.3.3 Linear maps on Z, are close to the RKHS
The following proposition will show how linear maps on Z cannot be more expressive than elements of the RKHS [0.11 H/ since their closure is in the closure of H Jo.wo. In this precise sense these spaces act like upper bounds to expressiveness.
Proposition B.10. Assume compact. Consider fixed the gates and A, E RNN B Nx and C E R. Nxdo Consider a linear readout v E R.. For any e > O there exist choices of 0i,3, 3, E (W..). such that
sup (X,1)EXx(0.))
1(v, 2, F(X,0)S
(38)
Hooo.. In other words, linear maps on the Z% are in the uniform closure of H Jo.un where ((.00)
0.11
Proof. Using (30) we see that (v, 2 is a linear map on T(X)o, with coefficients
A, TT A,C;
using Cauchy-Schware Schwartz it's moreover easy to see the existence of constant 2 such that for all I, one has
T A, S X Io AACa & !
Since (,,g(w)/,1 S
1 7p || -oar[aas] we have that, given an integer M 2 0, the bound
da Σ
de
1 Sig(w>)), dec
(t =
TT AAC, XiSig(w>) 3o.-
Σ TT
AiB
1=1 M
1=1
Xmd || 1 1-var_(0..]
(11ooll2 115%111
m!!
m=M
Xm
T- [0.1] pm |
()d
(1lXoll + 112711)
K
m!
mn!
m=M
m=
where K 2 0 is a constant which must exist by compactness of X and continuity of the gates. Since K - (Ad_ R' is just the tail of the taylor expansion of K Ad there must be M such that supiejo.1] (t < e. But then the choice
ma
of = n A,C, T([T] < M) 8/:=0² TT=,,A,B A, 1(I < M)
suffices for the required bound.
23

---

B.3.4
Uniform closure of the RKHS
Now that we have established the theoretical interest of the [0.1]] (oaaa we proceed to characterize
which maps (X, + can be uniformly upproximated through them. Proposition B.11. Fix compaet input set X. and continuous gates (-),,w, & with wf and x.2 12, For any e > and any
Wi
FE { (x,t) ((wton)) Xo + L. (Wwl)a)) dex
(39)
where V (C Rdy) and 1 E CC Rdt), there exist a G E Hooajm such that
sup (Xx,)ex((U,j]
[F(X,t) - G(
(40)
Proof. Note first that the map
X x [0,
1]
1] (1,((1,1);
(X, w(x.t]
a continuous map from 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 form
do
de
G(X,t) = Σ
(a, Sig(w>)).)
+
Σ
(8,, Sig(("),,))de
j=1
do
/ Sigluf/(l (o.1 1=1
de
= Σ (as Sig(
Σ
+
the proof follows from the uniform density compact sets of linear functionals on the (truncated) Signature (Thm. A.5), by also uniformly bounding thanks to compactness and continuity the norms of X1 and ex-
Remark B.12. The specific restriction of w to subsets of [0, 1] is crucial part of the result. The family of approximable maps does not include all path-to-path causal" functions + Y but subset of them, of type + Y == (w satisfying the specific time-homogeneity specified by the form of the restriction, akin to that in Li et al. [2022b].
B.3.5 Generic Weights fully expressive
We have seen how linear maps on Z are in the uniform closure of H ())o.. and we have explicitly Ho.11
characterized this closure. It is then natural to ask "how much" this closure the Z are able to "explore". The present section not only shows that the Z "explore" all the closure, but also that generic choice of weights is enough to eventually 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 of Kidger [2022], what surprising 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 e > O. For all F E H(-Jwam there exist a choice of hidden xde, C N such that
dimension N and parameters v E TEN A, RNNN
sup (X.NEXx(0.1)
[F(x,t) (v,
(41)
Moreover generic weight choices suffice with high probability, in the sense that under LeCun initialization
[Ag],, idd NOO, + [C],,,, [B]n, (0,
causal map one which does not "look the future" ef. Appendix It can be proved, using the results of Dubach and Peled [2021], that the sampling measure does not have to be Gaussian if satisfies certain moment requirements.
24

---

the following holds
lim (P E TR (41) holds N-00
We propose proofs, the first one of 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 highlight the main idea of the probabilistic result, which reduces to a "spin" on the central argument of this proof.
Deterministic Proof. Any F E Hy waww has form
[0.1)
(as Sig(w + / (8, Sig(w>))
F(X,1) = Σ
(42)
i=1
for fixed at, Bg E 1 (WW.). Consider an integer M such that
de Σ j=l
sup (x.1)
IF(X,t)
Σ XglTma, (ig
Σ/
(igla) Sc (43)
where TM is the truncation at length M.
Fix do + du + dg. Consider μu( (M, E N such that RR(M,d) TM (TR.). We are going to write es E RM(M,d) to mean the image of e₁ E T (R") through this identification. Note that (-) @M eg TM (Id)) + TM (I2) is a linear map, it does then correspond to a matrix Aş E (x(M.d))p(MMM Write ef. = Edotj for j = I,..., de and E == Edo+de + for k = =1,.... I,..., dw. Then the solution to
do
du
(R(M,d) 3 Z.
Xle
xx. 5
(44)
the object in (M( corresponding to the truncated tensor TM (T (x)o.))
This Ze is of the form z with N p(M,d), A Ado B [eil... 153 and C
[ei] lel.l-
In particular note how these matrices are such that
eAC = I(e. = (
B, = I(es = 2 3f7)
(45)
since it holds that
A,C; = e, 2 =7, and for all |/| > M one has necessarily A =0
A, = ef 3 s7
(46)
Our strategy is that of using these equaities to create a vector & E R corresponding to the TMa; and B.. Define the vector
da
Σ a
Σ Σ
(M(
(47)
Then expanding Z as in (30) and using the equalities above one has
dp
AA 1' Sig(w>)
(v, z =
A,C,
SiSi(w Jo.s
+
iml
do
de
of XiSigg(X> )o.1
Σ
Σ
8/
F=1 I1EM
do
de
(a Sig(w>)o.))
Σ
(3 Sig(w>)) )x.)) b.e)dEs
j=1
25

---

proving that for such v and 2 it holds
sup (x.0)eXx(0.) (0.1]
( - (,,, e
(48)
The crucial ingredient for the success of this proof the possibility recreate the space TM (pd)+dw++))) as an cuclidean space. To do this one needs ftM,, dg +d +de) ~ dp orthogonal vectors and way to express them using the matrices A,, B and C, the essential equations which capture this are given by (45).
The idea of the following probabilistic proof of this same result is that of allowing for some in (45), so the idea is that of exhibiting only approximately orthogonal vectors. At the cost of losing exactness,
leverage results of the Johnson-Linddessrrass Dasgupta and Gupta [2003] type c==N vectors IR orthogonal up to an error, using random projections.
find on the order This idea in the context of Signature goes back to Cuchiero et al. [2021b], and allows for much smaller hidden dimensions.
Proof. (Probabilistic Proof) Any F E (-)oo.. has form [0.1]
Σ / (B,, Sig(w))
F(X,1)= = Σ Yas Sig(w
(49)
for fixed a;, 33 E (PWa..) Consider an integer M 2 such that
sup [F(Xtt) - do (x.1)
de
L (r )a,) Sc (50)
Σ Xolamas Sig(w*))o) )o.e)
Sighu
Σ 3=1
where TM is the truncation at length M.
From Cirone et al. [2023][Appendix CJ we know that
C ATA - 88/
0
2
(17) [Ji)!!
(51)
VN
CT
CTATAB
0
1
2
(1Z + !J]!!!
(52)
17
N
F++
N
O
(1 |
(53)
12
Our strategy is that of using these bounds to create vector R "acting" like the aMa and ा my. Define, noting that the As, C., B, depend on N, the vector
do N = N
a
A,C,+
+
Σ
Σ MM
3) A,B,
(54)
MISM
j=1
26

---

Then expanding Z as in (30)
do
de Xo(TMai Sig(w
==1 f (TM Sig(w*) )=
RM*
sup (Xx1)EXX(U_]]
Σ
Σ
1.2
do
||(0") A,C; - ab112>
[gSSig(u*))) 1
sup (x,
1= MISM
do
IiSiig(>)). %ooll
sup (xx1)
M M
1/ ) (xx1)EXx(0.)
(( A,B, - -3511
sup
M
Σ
Σ
(( B,
sup
(Xx])eX((xu1]
M
Note how for //| S M one has
||(0²) T ArC; - -bil s 500(
and that similarly for / > M
[( A,C; 12 1 5M
1
2 m
(M + !
Which leads, thanks to the same bounds of Cirone et al. [20e3][ CJ, to
RM
VN (1)
(55)
But then by Markov's inequality it holds that
do
I (TM Sig(w") )ig(w>),.))
sup [x.0)Xx[[_.]
(u,
(o(Tmas Sig(w Jo.))
Σ
Se +
1=1
1=1
(56)
and thus there must be a choice of N, {A,,,, C' such that the inequality holds, and we thus obtain using (50)
sup (X.1)xxx(o.)
FFX, t) (0., 2 S 2e
and we conclude by arbitrariness of e.
B.4 The Diagonal Case
Here we study the particular, but empirically important, case where the matrices A, are taken be d
What we'll Il discover is that the Z cannot differentiate between Sig(w>) and other Sig(w>) (l) for any permutation o of the letters in the word
)
It is equivalent ask for them be commuting.
27

---

B.4.1 Diagonal Expansion for 2
Proposition B.14. For any choice of V RNNd B RNxd, and C IR writing A; dV)g the unique solution to
du dz
du: + Bddt
(57)
Z = CXo E R
is given by
Z = ding(V ding(V= + S'" edingiViut -w"") Bde
(58)
which can be expanded
do
de
Aprm B3 (' Sig(w")at
2
AT C2 SiSig(W")
Xysym, 10.t
yoymi T E RN
1=1 IEWa.
1=1 NEW
(59)
where
A 4m
1
Σ 0ES
Aa(1) Ar Sig(w")an (amm)
Σ Sig(w>)).))
(60)
Proof. By Theorem E.1 and Theorem E.6 we know that the solution of
A. + f BUEX
4 = 2 +
(61)
1=1
is explicitly given by
2 = W 20 + J W W
(62)
where Wa is the unique solution
W
Id +
Σ/
A,Wx dup
(63)
i=1
In case the A&s commuting matrices one can explicitly write the solution
du
WX
exp
Σ
Ardwe
exx
exp (diag(V (WW w)
(64)
d=1
since for fixed one has, using commutativity, that
du
du
dwx - 8.t
Σ
Ardwyi
Σ
W.W.s.dur
On the other hand we know, Theorem E.2, that
Wx
Σ IEWA
A/Sig(w>)
Σ KEW
Σ
A)Sig(u>)),
(65)
The two views are reconeiled by noticing that the symmetric group S₁ acts on Wh the space of words of lenth k by permuting the letters and, by commutativity,
Vo E ST.VT E Wh. As- Ao(1)
Then we have
A
Σ LEWL
A/Sig(w*)
Σ
Σ
An(r) SiglW
Σ
Sig(w>))a1)
kl
h!
1EW
nES,
IEW
oES.
dw
28

---

recalling then how ei, W. ... WU UIe = Eoese Ca(1) we get to
Σ
ArSig(w")a
JEWS
A
# Sig(w>)el
Σ
Sig(w>)ol
Σ
II
k!
h
JEW
JES
Tew
1=1
1011 )
)
du
[ Ardezi
Σ
II
A Sig(w>)<i
Σ A,Sig(W>))
>
JEW
In particular we see how in the commuting case
W Σ
AT
Sig(w>)ss Myamm
(66)
1EW
where
AP
Σ
Aot = Ar
)ig(w*)..
)a,t
symm
Σ
Sig(w>)
)((
7
dESt
dES
B.4.2 Diagonal Expressiveness
Theorem B.15. Fix a compact input set X and continuous gates (:),w,,, &. For any e >> and any
FE { (x,1) v(wi) No + L, Ølwt wh)) de>
(67)
for th E (RL,; Rd) and o E C ; there exist choice of hidden dimension N 2 1 and
parameters v E ERN, BERNNA C Nxdo and diagonal A, E NNN such that
sup (x.))xx(0.]
FF( (v, 2 Se
(68)
Moreover the "reverse" also holds iee. given any choice of matrices A,, B,C' there an c-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 ( (o.0)) Heloo of those F of type (37) defined by as By [0.1]
12 (PWa), such that for any word and any permutation a(T) of it
of = a; (()
(69)
The same argument of Proposition 10 shows that the uniform closure of the space of linear maps on the 2 is contained in the uniform closure of ( and the same bounds show that 0.11
this latter closure is the same as that of its subset composed of those e Sym (H ( (1o..))) having entries eventually equal to O.
[o.1]
Since
sym. Sig(w>) (
1
Σ Sig(w>))(1)
TT!
[7
oESt
such maps can be expressed exactly the form
P(WN) Xo + S' Q(wē - w/)) dex
29

---

for polynomial maps P. Q fixed in time. The usual compactness and continuity argument, together with an application of Kione-Weiestrass thus proves that the uniform closure of Sym H (Ja,e has the form needed.
[0.1]
The final ingredient is the density of the space of linear maps on the Z in Sym (yym(Hoo.1 [0,1]]
(olaa this is
another consequence of Stone- weiestrasssss as seen from Proposition B.18.
Remark B.16. Notice how here there no need to augment the paths in creative ways in order ensure separability of the points. The map (w, 8, 4(a.d Ci,o((,, 1); Rd=) is replaced by (w, s,t) + Wy Wa R and the space polynomials always separates points in RR' Remark B.17.
not necessary to pass through Sym(H [o.1] Sym(H((o.mm)) to prove the previous result, since [o.1]
directly follows from Proposition B.18. This choice presentation has been motivated by the conviction of the usefulness of drawing parallels and comparisons.
Proposition B.18. Fix a compact set K C. Rd and a d-dimensional convex cone C containing the origin. The space
: Span K 9 +> cla.)) E R :R:
uniformly dense in C CK;
Proof. This is an application of Stone-Weiestee Weiestrass: & is sub-algebra since
(a.x) ( (B, (g)
and a, BEC a B E C' by convexity of the cone; & contains the constant function ((0,)) 1 and is clearly point separating since the cone, being d-dimensional, it contains a basis of the whole space.
Remark B. The usefulness of stating the previous result in such a general setting is the following: with this formalism we can, for example, restrict to a S 0, in this way we would have a method to control the stability (ef. Appendix C.I) of the Linear CDEs by choosing the gate with a.s. axx > 0.
Corollary B.20 (Mamba Case). In the Mamba setting, the closure reduces to
(X.10 - Σ
Vil +
1=1 /
du(w X. w dex.
(70)
for continuous ti IR + R and Φ; RR R.
Proof. this setting one runs in parallel d_, diagonal systems and then takes linear combination of the stacked hidden state. The maps in the closure of the whole system are then just the sums of maps the closure of the subsystems.
30

---

C Stability and Chaining of Diagonal Systems
For this section consider, unless otherwise stated, fixed N 2 0, compact X and gates (-)o; w.C. &.
We will study the stability and chaining of diagonal systems defined by the choice of a matrix V E I Nxd such that A, == dV)) where V = [V] ... [V_.)-
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).
C.1 Stability
Here we explore the stability of the dynamical system 2*, thus we need to study the eigenvalues of the WX 4,5- Recall how this setting
dw W = exp Σ Adduai))
=exp exp diag( f V exp (diag (V(w) - wa)))
(71)
Note that because w is continuous and of bounded variation, it can reparameterised to be Lipschitz continuous, hence absolutely continuous. Thus can assume that w is almost everywhere differentiable and derivative à L'.
The stability of the dynamical system then depends on the alignment between w/ - w and the singular vectors of V. If V S 0 for all times, where the inequality coordinate-wise then W has eigenvalues all [o, 1] thus the system stable making training easier Orvieto al. [2023a].
Consider the singular value decomposition (SVD) of the matrix
K
V
(72)
Then, sufficient condition for stability is that for any k 1,.,, K 0 > 0k R, 0 uk E RR,, and (ux, wx)) 2 0 for any t [0, T].
(73)
C.1.1 The case of Mamba
In the case Mamba Gu and Dao [2023] the matrices are diagonal and
dup = so ftppussWW W x4 + A)dt, det = O dw
moreover the proposed choices of V are of type
== & 1d
for some choice of v N Note that softmaz is just smooth approximation of ReLU and that Im(Relee (ReUU) C {w E Rd (Id,, w) 2 0} hence mamba is implicitly ensuring that the dynamical system approximately always well-conditioned.
C.2 Chaining
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 term
[ Ó(w) -6wx--wk w.) dex
becomes then a crucial component. first sight one might think that such a term allows to recover at least level two components of the Signature of (w* unfortunately things are not easy they may seem. Notice how inside of the integral time is "going backwards" from the perspective of wx thus can in general approximate terms of type
S. du. dex
I"
d = Sig(( xx)
t which are indeed terms of the Signature, but of the reverse paths w = wp_ and { EX_
31

---

Proposition C.1. Fix compact input set X. continuous gates W.,. and X = 1. If the components of td are linear combinations of those of w", with ind-iddeenddett weights, then linear functionals Z5 can, uniformly in X x [0, approximate arbitrarily well the following level 2 terms of Sig(( ( No,
S/ dwy do = Sig((w" 1 Swde
Proof. Under these hypotheses we know that linear functionals on Z are uniformly dense, for continuous v; o, in
((x1)= (w?)) Xo + L/ olwř w.) de.
Assume Ex. (aj, wi) and consider the choices
b(x)- = (x' (ays x)) O, ,0),, <(x) = -00,..,, ".........,,,.............
(74)
so that
m((z)) Xo = wi ex plw w²)) ded = -ww - -w wd(
(75)
To conclude note that
w 5x 1r ==
f dw dex.
1 dis dgx. + f fr dwj dexs
0= 0=
1' Io
dex + { (W/) wix )dE23
du
hence
1 l'¹ dw." dedd w. c.
1 (w)
wit )dE ((w))) Xo S' dlwe w²) de.
==0
If X (1,, 1]: R. we can the previous result compute its Signature entries by chaining diagonal Linear CDEs.
Theorem C.2. Assume a compact input set C C1.0((, 1]; 1);R"). For any T E Wa with [T] 2 and there a sequence of linear maps Wa E R.Nexl and weights for the following family of chained Linear CDEs
d ax; + B ZJ Zo-
dz. Σ
1 2.
(76)
d+1
dz
1,,+
A
(b+1)
1.x
+ B(++1) E ERM+,, z zitli z
(77)
X
i=1
such that for some E N one has
(i, - (v, -
sup (x,0)Xx(0.1)
Se S5
(78)
Proof. For [T] 2 we can apply Prop. C.I. Assume the theorem holds for [7] S A and let
M == supxex ex |X| po Fix Li] = k + and W IR N1 x1 such that
sup (x.1)exx(011
(5) W W
1x S
M
Again by Prop. C.I there are a N₁ and v E Nx such that
1." WA 16-1Zk-1Xdx - (c, 2 15 Se. (Xx))xx((0 [0.1]
sup
32

---

Then
(Sig(X)), (v, 2 E / (0(X), / Wh- Wh-1 2 1i--1z----000 dxx + S/ VV--12-1.- - (v, Z,,1
1 SiggX)). W 1 1 | +e
S/" M
|dx + S
thus concluding the proof.
Then Proposition 4.5 follows corollary by running in parallel the systems above to recover simultaneously multiple Signature entries.
C.2.1 ReLU activation choice
Models like Mamba do not only diagonal matrices but also consider controls of specific kind:
w = Re + b)ds
The choice of ReLU enforces We 2 0 for all times as above, but could, priori, destroy information about X which allows for the recovery, after chaining, its Signature.
Does this choice keep some expressivity? Fortunately almost all of it: since
ReLU(x) - ReLU(-x) = x
one can choose linear map W which allows to linearly recover
ax [. X,ds
from wp. By correspondingly modifying the form of vb and o in (74) such that
(ww,) Xo = W. ex
olwe
w de - (w,
(79)
one is able, through a similar chaining procedure, to recover arbitrarily deep entries of the Signature of Wن = So X.ds.
33

---

D Path-to-Path
Definition D.1. A map G E (" 11:112)) x [0, 1]: R) is causal iff for all E [0, 1] and paths w,we E (,,0 R)) one has
w| = 3|oo.1| = G(w,t) G(
Le. causal if it does not look the future.
Proposition D.2. Assume compact inpua set X, continuous (:),,w, &, X = and wi t. Then
for all 0 and all causal G' C"(CC,,(0) 11; [0, 11; IR) there exist integer N 0, some
Feed Forward neural network F RR + R, and parameters C' Nxdo A R N such that
B E I Nxde
sup sup [F(Z)) <( xeX1c(0.1]
(80)
Proof. Fix O. By B.7 the space H (o.w.. contains all functionals of form [0.1]
(X,t) (a, Sig(w))o.) )o.))
thus, by the properties of the signature and by compactness of X, for any fixed so E [0, 1] there is some f E Ho such that
[0,1]
sup X
f( so) - G(w"((((,, so)l <e
Using the fact that G E (10, 1]; (C (10, 1}; R4; R)) and compactness of [o, 1]. we find
finite set {0= & so S ... < SM $ 1] of points and . E Moo1
Dowsr such that
sup
IG(W G(w 8:)1 <E
(81)
sup
[f((X, ((("",,s)) <e
(82)
XeX
sup (X,,)xXx(s, 188211)
[f((X, - fi(X, s;) <E
(83)
for O,..., .M Notice then how for all X X and S1+11 [Ji(X, G(w", . < [Xi(X, 8) (((X,))) [A(X, s:) - G(w", |G(u>, 8:) - G(w*, S 3c
It follows that the map F' E (²I( 1] R) linearly interpolating the f; in time satisfies
sup sup [F(X): G(wx,, 1)) < xex:c(0.1]
To conclude note that X being compact, the fa take values in a common compact set K C R. There exist then neural network v [0, K + R such that
[V(1, z) - Si+1
9i
sup iE --1 se
Zi+1
<E
81+1 8i
81t1
which means that
sup sup [tt fo(X,t), re
<E
get that X + {t t} [o.o1] 2 the space, (t, fo(,, ...., (M(X t)) can be uniformly approximated. Triangular inequality gives finally
Recalling that w.
Haam so that, given density of linear maps on
sup sup (t, (...((())......xxxx)))) G(w < 7e xe
which, by arbitrariness of e, gives the thesis.
34

---

The non non-linearity is crucial for the path-to-pate result. A map of type (w,t) H (ta, Sig(w)o,.) cannot be approximated arbitrarily well by (w,t) (3, Sig(()..))
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 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 wx, but T(X), de- pends linearly on Xy and Ex suggesting that neural networks on ( have stronger generalization properties. In fact one can prove that it is possible to approximate all continuous G(Xo, wx <x .t,, this is done by reconstructing Xo and &x as in the classical SSM case of. Orvieto al. [2023b].
35

---

E Wronskian Matrix Theory
In this section obtain unified theory studying the solutions 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 seratch for completeness, notational reasons and to present a self-contained theory.
Theorem E.1. For any choice {A' ..... .....AA] C ( R and w ([[0,,]:R) 1]: there exist a unique map W E (Co, 1] [0, 1|: (XN) solving the following CDE
Wa, IdN + Σl" A. W,,
(84)
Proof. We will use Banach fixed point theorem leveraging the completeness of the space ([0, 1] x [0, I|:RNxx) with the uniform norm
|x = sup ||
+.1E(0.1]
Define the map : - Q as
r(X)a.= Idv + Σ
do,,,
i=1 r=s
One has, for X, E 12 and E N setting r Idg, that
d Σ
/ A (T*(
p* - ()),t
- dut
T=B
which iterated gives
Sree
k+1 dul
pht1 (X),) - (X),,eI"* ph+ (Y),,
Σ
II
A (Noin Zo.m
II ==1
IEWa
T441=s
j=
11/=41
= Σ
(Xa,r - )
TEAMT
JEW
|1+++1
where Wa is the set of words in the alphabet (1,...,a) d) and
A/..)) = {(T...... Tw) [0, 1] Vj I...., k 1. T3 S Tz+1}
A
II j=k+1
A dwf
dw!
By defining M = max A
:1 fl,...,d}} dd}} then one clearly has
(dM [|W|] )* |X- - Y
(x) - r Ic
(85)
thus definitely (in k) the map I is contraction. By Banach fixed point there exist unique fixed point W E Ω.
Theorem E.2. Under the assumptions of the previous theorem one can write Wa explicitly as
Watt Σ Σl
Addwu,
(86)
JeW, TEA b.t)
moreover for all the matrix-valued maps are constant on all [0, i.e. i.c. A₁ = A then
W Σ
A)Sig(W)
(87)
IeWa
where Sig(w),, is the Signature of the path
36

---

Proof. The second assertion follows from the first by definition of the Signature of path.
Regarding the first notice how the series is absolutely convergent in R-Nx,, uniformly in 8, since
Σ E Iewa TEA!!
|| (or.
dw
d M
k=
aM ||||||| IM
thus for any s, E [0, 1] the series defines an element of Wa, E RNNxN.
Using the uniformity of this bound and the fact that for all I Wa one has
W
Afdw, E
JEEA in (eid)
as function of (s, 1). which moreover is uniformly continuous
[ 2
W
02.
TrEA!!! 12)
(8 (STEA/1) 11 (1i
6 Tea
(22122)
1n
) du!
SMI'l
Jreafh
8 TEa!!!
8 SEa/!!1 (0gita)
du
<M
concludes that Wa, Ω. Finally notice that Wo, is fixed point of r
r(W.,)) =Idx +
Σ
A
Σ NEW' FEA 0.11
Afdue dut
=Idy +
Σ
A dw
TEAM!! M1
TEW,
10,11
1121
Σ
Addut W.,t
TEA!!!
lewa
and conclude by uniqueness.
Proposition E.3. Under the previous conditions, the unique solution of the N-dimensional CDE
dX, = =Xo+ + Σ
A;X
(88)
1=1 ==0
given by
X, = Wo,
(89)
Proof. The solutions are unique by standard results Friz and Victoir [2010][Thm. 3.7], moreover
Wo,cXo = (Idv Σ A do,
Xo No= Xo Σ f Aooo
Proposition E,4. The Wronskian matrix has the following properties:
Vr, 8, [0, 1).
Wr, W. W.W.W.
2. Vs,t E [0.1]. w- -W,
3. Vs,te [0.1].
Wa IdN Dt fot W dw,
37

---

is given explicitly by Proof. Regarding the first statement notice that for all Xo E IR one has
IdN + Σ l" A,W
X, := W Wo
WroXo
d
= -W,,s0 +
Σ
A-(W,,r (W,,WW,,eppp
1m
T==
= =W,,5 +
A
d
1=1
and by the previous proposition also
X₁ = WrcNo Wr, + Σ rmy
A, dw
thus X, and X2 solve the same CDE and coincide at time = s. This means, by uniqueness, that X, and X, coincide for all times; hence W.sWr, and Wr, coincide for times too since for any choice of Xo one has W W.&WW No Wo.
The second statement follows from the previous setting first and subsequently exchanging and t.
To prove the third equality note that
0 de W,,s) (d, Wd.,(dWW..)
hence
Wd,, = = W d.W., s.t
= Σ W.. W.,
Proposition E,5 (Liouville's Formula). Under the assumptions of the previous theorems, if w E C² 1]: (R)) then
del(Wa.)) = 1+ Σ [ (w(,))de((Ws;))dd = exp 1=1
Σ
d
tr( tr(A))
(90)
Proof. This just follows from the classical case since we can write
A W., dw,, = I Σ Af W
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' Bd) E (TRd).0.11 0.11 the unique solution of the N N-dimensional CDE
d
X, = X +
Σ i=1
(A,X, + BB) du
(91)
X; Wo. + Σ
W WarBldww
(92)
t=1
where W E ((0, x (0, 1}; NxN ) is the Wronskian matrix defined by
W Σ
A!dw!
(93)
TEA
TeW.
38

---

Proof. Given the unique solution X, one has
da (W,,....) =d, ,), + (X,))
W W., 1,X, + W.,AAX. + Ws, B., du
Wa Bidw
hence
X1 Wo,eo0 Wr, Wo, Σ Σ W d.,
39

---

ZOH and Exact Solutions
Consider Linear CDE as the one of (25)
de A:Zedws + Bdl..
dz
and recall how the solution can be explicitly written, for times s t, as
Z, = Wo + S. Wr,
Assume moreover that in the interval [s, both drivers have constant derivative i.e.
Wp Ws w( 5) E, E v(r s)
Then if Aw Ee=1 A,w0 we get that Wr (t thus
Z: = (b Zs [ ( Budr Aw Bu + (Se coull-m)ar) Bo
(94)
But the integral can be explicitly solved as
L Aulll- dr = (-
(nolt-))) -
= And (cdnalt-))11) -1
(95)
r=s
leaving us with
Zi (1-b) Zz + Aw (cu II) Bu
(96)
which, setting A = 1 can be rewritten as
Z A A Z + (A (chmm -I) (BA)u
-
(97)
i.e. exactly the ZOH scheme.
40

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the Introduction we list our contributions and refer, point by point, to the relevant sections of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
41

---

Justification:
We have discussed some limitations in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the proofs are found in the Appendices, the specific sections of interest are referred after the statements.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Code to reproduce experiments included in supplementary material.
Guidelines:
42

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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 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 good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code to generate the data used and to run the experiments are included in the supplementary material alongside README explaining how run the experiments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm blic/guie gwwggg//idddesiiie
ssionnoiccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / inips.cc/publin httpc//pbblc//guiessss.ebeeeeeee wtwp://gg//e//eeee/eeeceees.eeet http://iiiiiiiieeoo/////ttiiiiii www.eessummssiioPoooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
43

---

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) 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, hyper- parameters, 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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi- dence 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 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 a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
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 should state it. The authors should preferably report a 2-sigma error bar than state that they have 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 the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed 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.
44

---

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 compute required for each of the individual experimental runs well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neurrs
http:://narrppp.ccpbbiii httprrss....pppbpt//.cccccceeee ines?
Answer: [Yes]
Justification: This is theoretical work. We provide information sufficient for the reproduc- tion 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. 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 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 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 partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
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 (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
45

---

Justification:
This is theoretical work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, paperswithcode com /ataaasset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
46

---

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 crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is theoretical work, not involving crowdsoureing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
47


Reviews:
[{"review_id": "i8Jtuvq94A", "reviewer": "Reviewer_KnKG", "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.", "questions": "- what is NCDE? This was not introduced.\n- 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": "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well written and the authors managed to make the very involved theory and proofs more accessible by walking through the interpretation and takeaways on a more high level. \n- The theoretical results are important contributions for categorizing the expressivity of existing SSM models and may potentially inform about future architecture design of SSMs and related models.", "weaknesses": "Despite the well-described theoretical contributions and insights, it is still not very clear to me what to take away practically.\nIn 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. \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback on our theoretical work. We are pleased you found our expressivity results important and our proofs accessible. We spent a considerable amount of time making our manuscript easy to parse despite the high technicality of the content.\n\n## Weaknesses\n\nThe reviewer is right in saying that our work does not explore the finite-regime setting and does not compare architectural options in terms of model parameters needed to achieve a desired level of expressivity. This would be highly desirable but is not an easy task; in addition results can be confounded by issues such as optimization, inductive biases (OOD generalization), GPU bottlenecks (e.g. memory dependency on sequence length) etc. Indeed, current research did not yet unveil such clean comparisons even for Transformers vs SSMs : the attention mechanism has more parameters compared to the S6 block in Mamba, but how exactly expressivity compares at a fixed compute budget or model dimension is unclear. \n\nWhile touching on the issues above is for sure needed when proposing a new model, we like to point out that the purpose of our work is not suggesting a new mixing component (i.e. dense RNNs linear in the state), but instead exploring the source of limitations of modern sequence mixing components at generic widths. To do so, we study dense linear (in the state) recurrences, and then dive into the diagonal setting. As such, our dense linear CDE framework is not intended for direct implementation in a deep model, but provides an upper bound on the expressivity which is achievable with one RNN (SSM) linear in the state but nonlinear in the input.\n\nNote that\n- **What happens at finite width**. Our results prove that one linear CDE layer can approximate any nonlinear transformation, while diagonal CDEs (e.g. Mamba) cannot. This is however only a subset of our results. Leaving out chaining from the discussion here, our theorems identify the functional form for dense and diagonal settings in closed form – this holds at any width. Specifically, why the output in the dense setting can be written as $\\int_0^t \\Phi(\\omega^{X}_{[s,t]}) \\cdot d\\xi^{X}_s$ (eq 7), for width-dependent function $\\Phi$ determined by the model parameters. Instead, in the diagonal setting, the functional form for the output is restricted to $\\int_0^t \\phi(\\omega^{X}_t - \\omega^{X}_s) \\cdot d\\xi^{X}_s$. Note that width can only modify the complexity of the nonlinear functions $\\Phi$ and $\\phi$, but cannot modify the output structure.\n\n- **Experiments**. While we believe very much that experiments can provide valuable insights in some setting, our objective here is to provide a theoretical foundation, hence the title. We remark that our results are not bound - they provide a tight description of the fundamental elements interacting when outputs are constructed, with model dimension only controlling functions $\\Phi$ and $\\phi$ above. We also note that our results are novel - also in the realm of Rough Paths theory as an independent mathematical subject. We refer the reviewer to the supplementary PDF for augmented and new results, as discussed in the **general comment**.\n\n\n## Questions:\n\n- **NCDE**: NCDE stands for Neural CDE. In fact a linear NCDE is just a linear CDE, hence there was no need to mention the “Neural” part – we used this terminology since it is linked to some results on rough path theory applied to neural networks (e.g. https://arxiv.org/abs/2005.08926) but here this connection is not necessary. We thank the reviewer for pointing this out. We will revise the manuscript to use the term “CDE” instead of “NCDE” in the relevant sections to avoid any confusion.\n\n- **S5**. As you stated, we expect that a dense CDE with a trainable transition matrix would be the best performing model on this benchmark. However, the computational burden of training such a model is very high. In practice, S5 is parameterized using a diagonal transition matrix, as discussed in Section 3.2 of the S5 paper (https://arxiv.org/abs/2208.04933). Consequently, the same theoretical results on expressivity apply to both S4 and S5. In fact, any model where $d\\omega$ is $1$-dimensional (i.e. any model with only one transition matrix $A_1$) is equivalent over $\\mathbb{C}$ to a diagonal model, by virtue of $A_1$ being similar to a diagonal matrix. To obtain the full expressivity results more than one $A_i$ must be present, and these matrices must not be simultaneously diagonalizable. As demonstrated in the proof of Theorem 4.3, in the diagonal case, the relevant terms of the signature are those appearing in its symmetric part. The signature of a $1$-dimensional path being fully symmetric shows consistency of our findings. On reflection, given this equivalence, we believe introducing S5 in our experiments is redundant. To streamline our presentation and strengthen the connection between our theoretical and experimental results, we have chosen to replace S5 with S4 in our experiments. We hope this revision addresses your concerns.\n\n\n## Limitations:\n\nWe will augment the list of limitations in the camera ready version, using the additional available space.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nwUdbsecBj", "reviewer": "Reviewer_K8Nc", "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.", "questions": "Can you think of any improvements to SSM layers/models that the RPT theory would suggest?", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This is a really nice theory explaining SSMs. It gives a new way of looking at the expressivity/quality results that have been observed in prior work. Hopefully this theory can lead to new insights about how to design better SSMs in the future.\n\nReally solid work.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback on our paper. We appreciate the positive remarks on the theory's presentation and contribution. We would like to address the points raised regarding “closing the loop”.\n\nOur paper shows how non-diagonal transitions lead to a substantial increase in expressivity. However, this theoretical insight is currently impeded by the reality of computation with dense layers, which is practically infeasible due to the associated computational costs.\nAt the same time, recent literature (e.g. https://arxiv.org/pdf/2402.19427, section 4.2) has shed light on how the computation of linear diagonal RNNs is dominated by memory transfers. This indicates that there is leeway allowing for an increase in the complexity of the sequential mechanism, presenting itself as a very promising area of research.\n\nSuch a mechanism would have to be non-diagonal but efficiently computable. Recent works (e.g. https://arxiv.org/abs/2310.16597, https://arxiv.org/abs/2407.08459, https://arxiv.org/abs/2406.05045) suggest that low-rank or even highly sparse weights should lead to the same limiting behaviors found in the dense case. This is a promising avenue, which we have not studied in this work, as it would require substantial theoretical justification as well as thorough empirical evaluations at scale. As the purpose of this paper is to outline the hypothesis class and power of SSM variants, we decided to leave this avenue for future research.\n\nHowever, given the importance and interest of such observations, we will augment the concluding section with them in the camera ready version, using the additional available space.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wcYujJS7D9", "reviewer": "Reviewer_xt92", "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.", "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": "* Check the weakness part & questions part", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* This paper focuses on timely and important research problem. \n* I could not fully read the proof, but the results seem correct.", "weaknesses": "* It would be better to provide preliminaries on rough path theory for readers who are not familiar with that.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback on our paper. We appreciate the positive remarks regarding the timeliness and importance of the research problem we address. We would like to address the points raised concerning weaknesses and questions.\n\n\n## Weaknesses\n\n- **Preliminaries on Rough Path Theory**: We understand the importance of making our paper accessible to readers unfamiliar with Rough Path Theory. In Appendix A (referenced at line 268), we provide an introduction to the Signature Transform and reference several in-depth studies and presentations of Rough Path Theory in the context of machine learning. Additionally, in Appendix E, we provide a self-contained theory studying the solutions to general Linear CDEs. To enhance clarity and ease of access, we will ensure to reference both Appendix A and Appendix E more prominently in the main body of the paper.\n\n - **Implications in Practice**: Our results fit into an ever-growing theoretical literature on the implicit limitations deriving from architectural choices in the context of SSMs (see e.g. https://arxiv.org/pdf/2404.08819, https://arxiv.org/abs/2406.05045), which we enhance by providing explicit, analytical characterizations and by establishing a theoretical foundation, in terms of Rough Path theory, which we envision as a base for further study. The take-away from this literature is clear: devising a non-diagonal, input-dependent, and efficiently computable transition mechanism would allow you to overcome the expressive limitations of present SSMs without the need for an arbitrarily high number of layers. A promising avenue is using low-rank or even highly sparse weights, as suggested by recent works (e.g. https://arxiv.org/abs/2310.16597, https://arxiv.org/abs/2407.08459, https://arxiv.org/abs/2406.05045). \n\n- **Further experiments**: As a further example of the practical implications of our theoretical results, we have performed additional experiments focused on the A5  benchmark introduced by https://arxiv.org/pdf/2404.08819. This benchmark is designed to evaluate models on their state-tracking, a crucial ability for solving problems that involve permutation composition, such as tracking chess moves. A key result of their paper is that state-space models such as Mamba require stacking in order to perform well on this benchmark. Our experiments have shown that even on the longest sequence length in the benchmark, where Mamba requires 4 stacked layers to achieve >90% test accuracy, a linear CDE with a trainable transition matrix requires only one layer to achieve >90% test accuracy. We intend to include a full discussion of these results in the final version of our paper.\n\n\n## Questions\n\n- **Derivation of Eq.3 and the Appearance of the Exponential Term**: We appreciate the reviewer's attention to the details of our derivation. A self-contained explanation of Zero-Order Hold (ZOH) discretization is provided in Appendix F (referenced just before 164). To increase clarity, we will highlight the reference to this section in the main body of the paper. We also note that ZOH discretization is a conventional nomenclature for such a scheme in the SSM literature (see e.g. https://arxiv.org/abs/2303.06349).\n\nWe hope these clarifications address the reviewer's concerns and enhance the overall readability and impact of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lJS87Q48hJ", "reviewer": "Reviewer_1RLC", "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.", "questions": "1. Please provide more details of questions raised in the weaknesses section above. \n2. 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?\n3. Minor issues: What is the definition of (linear) NCDE (see line 311, 312, 315, 317 and 643).", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work provides fundamental theoretical justifications on the expressivity of different types of SSMs. \n2. The derived inductive biases clearly distinguish the recent new data-dependent modeling (e.g. Mamba) from the classic original data-independent modeling (e.g. S4) thorough a input-selective framework, which shows rigorously the superiority of the former architecture. \n3. Other theoretical results also lead to useful insights. For instance, diagonal recurrence weakens the approximation capability, but this can be alleviated via stacking. \n4. All these insights are basically verified by numerical experiments.", "weaknesses": "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. \n2. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback on our paper. We appreciate the positive assessment of our work's soundness, presentation, and contribution. Below, we address the raised points.\n\n## Weaknesses\n\n- **Rates of convergence**: While our current theoretical framework in general provides only density-type results, we agree that the characterization of convergence rates is a crucial question. We envisioned this paper as one establishing the language and theoretical groundwork for further analysis in such a direction.  \nWe want to point out that for Theorem 4.2, the bounds are explicit in $N$, as given in equation (55). \nNevertheless, a study of the rates in the general case, particularly for the stacked diagonal systems, would be more technically involved and is considered beyond the scope of the current work. However, we acknowledge its importance and will highlight it as a critical direction for future research.\n\n- **Experiments**: We would like to clarify a potential misunderstanding: our approach does not utilize the path signature as part of the method itself. Instead, we are simply using specific terms in the path signature as the labels for the synthetic datasets. \nWe opted for low-dimensional, synthetic datasets to provide empirical evidence for the theoretical results in our paper in a simple setting. These experiments were not intended to comment on the effectiveness of the path signature when handling high-dimensional data. There are a number of interesting works which apply variants of the signature to real-world data, with some recent examples being the signature kernel (https://arxiv.org/abs/2006.14794, https://arxiv.org/abs/2006.05805), the path development layer (https://arxiv.org/abs/2204.00740), the randomized signature (https://arxiv.org/abs/2201.00384), and log neural controlled differential equations (https://arxiv.org/abs/2402.18512). \n\n## Questions\n\n- See above\n- **Gating**: Our definition of gating is aligned to that of forget and input gate in the LSTM, GRU and SSM literature. In particular, what the reviewer refers to is known as output gate: what instead $\\omega$ and $\\xi$ modulate is how inputs are selected and forgotten. The multiplicative interaction crucial in this setting is $Z_t^X d\\omega_t^X$ - this can be thought of as a forget gate on the hidden state, with input-dependent gating function induced by $\\omega$. We note that the gate terminology was introduced in the LSTM paper, but is also used in recent SSMs paper such as in Mamba and Griffin.\n\n- **NCDE**: NCDE stands for Neural CDE. In fact a linear NCDE is just a linear CDE, hence there was no need to mention the “Neural” part – we used this terminology since it is linked to some results on rough path theory applied to neural networks (e.g. https://arxiv.org/abs/2005.08926) but here this connection is not necessary. We thank the reviewer for pointing this out. We will revise the manuscript to use the term “CDE” instead of “NCDE” in the relevant sections to avoid any confusion.\n\n## Limitations\n\nWe agree with the reviewer on this point. We believe that our casting of SSMs in the language of Rough Paths theory might open the way for such a study of discretizations, using the honed tools of the field.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to extend our gratitude to all reviewers for their insightful comments and valuable feedback. We appreciate the time and effort invested in evaluating our work. Below, we address the primary clarifications about relevance and practical implications.

- **Our Contribution**. Ours is a theoretical paper studying approximation of sequence to sequence maps with modern (gated) state-space models. Our results are to be inserted in the vast literature on expressivity and computational power of recurrent mechanisms, but with a fresh look at modern architectural components (e.g. the Mamba block). Our results are novel, and our tools draw a strong connection to powerful techniques in Rough Path Theory. We provide a closed-form analytical characterization of the class of learnable functions implemented by SSM variants, and discuss how this is affected by computationally critical choices such as the use of diagonal matrices. Our results on universality hold in the width limit, as common in much of the deep learning literature, but crucially the input mixing mechanics we identify provide valuable insights also at finite width, acting as upper limits to computational power.

While our paper is mainly intended for readers interested in deepening our theoretical understanding of new deep learning blocks, we are also concerned with practical implications and the road ahead for future research:

- **Relevance of the results**. Most importantly, the functional forms we identify using Rough Path Theory reveal how input tokens are processed in dense (idealized) versus diagonal (Mamba-like) models. In diagonal models only first order information about the input sequence is used when producing an output, whereas, in the dense setting the entire history contributes to the computation. This is a significant difference, independent of width. Recent investigations, such as those found in https://arxiv.org/abs/2209.11895, https://arxiv.org/pdf/2402.01032, https://arxiv.org/pdf/2404.08819, and https://arxiv.org/abs/2312.04927, have explored similar distinctions in token processing strategies. Compared to these works, our results also offer tight guarantees on expressive power and on the effects of chaining.

- **New Experiments**.  We have rerun the signature prediction experiment for each model with 5 different random seeds. We have augmented our plot of the validation RMSE to show the range of the validation RMSE over the 5 runs, and this can be found in the supplementary PDF file. We have also conducted additional experiments on the A5 benchmark introduced by https://arxiv.org/pdf/2404.08819. This benchmark is designed to evaluate models on their state-tracking ability, which is crucial for tasks involving permutation composition, such as tracking chess moves. A key finding from their paper is that state-space models like Mamba require stacking to perform well on this benchmark. Our experiments demonstrate that even for the longest sequence length in the benchmark, where Mamba needs 4 stacked layers to achieve over 90% test accuracy, a linear CDE with a trainable transition matrix achieves over 90% test accuracy with only one layer. We have included plots of these new results in the supplementary PDF file and we plan to include a broader discussion of these results in the final version of our paper. 

- **Practical Implications**. Our results outline some inherent limitations of diagonal recurrent computation. We are not making claims of the type "diagonal is less expressive, use dense”; even though dense recurrences are more expensive. However, implications and directions for future research are clear: recent studies, such as https://arxiv.org/pdf/2402.19427, indicate that linear diagonal RNNs are memory bound, with computation dominated by memory transfers. Increasing the complexity of the sequential mechanism is thus a promising research area. Our paper shows that advancements towards efficient (perhaps sparse) non-diagonal computation are supported by increased expressivity. Our analysis also highlights specific components to target for enhancing compute with direct impacts on expressivity. Note that https://arxiv.org/pdf/2404.08819 arrives at similar conclusions, with drastically different tools but without identifying completely the hypothesis classes, as we instead do here.

Meta-review: 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.
Decision: Accept (poster)