Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models

Thank you very much for your comprehensive review.

Weaknesses

1. We have expanded our experiments on the UEA benchmark, which consists of real-world time series datasets, to include all of the SLiCE structures. Furthermore, we have performed empirical runtime and GPU memory experiments on EigenWorms, the longest dataset considered in this paper, to provide additional guidance when applying these models in practice. For more details, please see the section of our response to reviewer 7XXo titled "Questions 1, 3, and 4". We hope these additions partly address your concerns, although we acknowledge that there remains open work on understanding the behaviour of these models at finite hidden dimension and how to choose their hyperparameters.
2. On the A5 benchmark, all of the SLiCE architectures were chosen to have $1024$ non-zero parameters per state-transition matrix (Lines 241, 802). We were computationally limited to a hidden dimension of $128$ for dense matrices, and so chose a hidden dimension of $128$ and a sparsity factor of $3/7$ for S-LNCDE, giving $1024$ non-zero parameters. We have amended the paper to make this decision clearer. We have also added an additional experiment on the A5 benchmark to investigate the impact of sparsity. We trained the S-LNCDE on the length $20$ A5 dataset and varied the sparsity factor $\epsilon$. We find that as $\epsilon$ decreases, the number of training steps taken to converge increases, but the model still converges to $100\\%$ validation accuracy with only $1\\%$ of the parameters being non-zero. Thank you for bringing these two sparse papers to our attention, we will incorporate them into our discussion.
3. We haved moved part of the discussion on the impact of block size and rank to the main body of the text.
4. We note that many existing sequence-model architectures that use matrix-valued hidden states, including Gated Linear Attention, RetNet, RWKV6, mLSTM, and Mamba, do not have a method for column interaction in the recurrence. Furthermore, if desired, column mixing can be achieved by right-multiplying by an input-dependent $n \times n$ matrix, as is done in DeltaNet, without requiring a full $d_h n \times d_h n$ coupling. We have expanded Appendix C to broaden the comparison with existing matrix-valued hidden-state models.

Minor

1. We have modified Lines 56–60 to the following (citations removed for brevity): “Utilising structured matrices to reduce the computational burden of neural networks extends beyond sequence models. The lottery-ticket hypothesis argues that dense networks contain sparse sub-networks that, when trained in isolation, can match the accuracy of the full model. Such sub-networks have been uncovered by pruning before, during, and after training. SLiCEs differ from pruning by imposing structured sparsity at initialisation and training the resulting sparse model directly. Other structured-matrix approaches include sparse Transformers, 2:4 sparsity in linear layers, and Monarch layers, which factorise weight matrices into two block-diagonal components.”

2. We have amended the caption to “shaded region”.

3. Yes, Appendix B is referenced on Line 218.

4. We have added the following line to Table 1:

   Model	Parameters	Recurrent Cost	Parallel Cost
   Log-X-LNCDE	$\mathcal{O}(P_X)$	$\mathcal{O}\left(\tfrac{R_X}{s}d_h^{N-1}\right)$	$\mathcal{O}\left(\log\tfrac{n}{s},C_X d_h^{N-1}\right)$

   Log-X-LNCDE corresponds to applying the Log-ODE method with intervals containing $s$ samples and a truncation depth of $N$, where X corresponds to a specific SLiCE structure (DE, D, DPLR, S, WH, or BD), $P_X$ is the order of parameters for X, $R_X$ is the order of the recurrent cost for X, and $C_X$ is the order of the cost per composition for X.

   We have also expanded the discussion in Section 5.3 to contrast the theoretical computational cost of the Log-ODE method with the reduction in I/O costs. Empirically, we show that the Log-ODE method leads to practical speed-ups for the BD-LNCDE on the longest dataset we consider, the EigenWorms dataset, which has almost $18{,}000$ observations per sequence. See the table below for details.

   Metric	Log-ODE Interval	Recurrent	Parallel steps 128
   Time / 1 k steps [s]	1	227.26	52.58
   	12	24.66	13.40
   GPU Memory [GB]	1	3.48	7.59
   	12	3.48	3.49

Questions

1. Yes, although we did not find that first-order approximation compromised training stability in practice. We have expanded the discussion to mention that this is done as a computational cost-saving measure, and we did not find training stability impacted by this choice.
2. The fast Walsh–Hadamard transform, although supported, would likely benefit from improved software and dedicated hardware. For example, the fastest inference method we are aware of (PyTorch’s Hadacore) does not support back-propagation.
3. Inspired by the $\mathrm{Lip}(\gamma)$ regularisation introduced in [1], all SLiCEs use weight regularisation on their state-transition matrices. The paper does not make this explicit and we apologise for this oversight. The main body and Appendix now discuss this. The Walsh–Hadamard LNCDE’s training was still sometimes unstable. Therefore, we constrained the range of the diagonal weights to \[-1,1]\, which means that the eigenvalues of the state-transition matrix have modulus $\leq 1$. This was briefly discussed in Appendix D, but we have now included an expanded discussion in Section 4.5.

[1] 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 on Machine Learning, 2024.

Thank you very much for your thoughtful follow-up and for raising your score. We are glad our response addressed your concerns.

We agree that including the results for varying levels of sparsity and clarifying that S-LNCDE used a sparsity of $\epsilon=3/7$ in the Table presented to reviewer 7XXo will strengthen the paper. We will incorporate these into the final version.

Thank you very much for your thorough review.

Clarity

We have redrafted the paper to improve the clarity. Changes to the abstract and introduction are detailed in our response to reviewer 7XXo, and details about a new introductory chapter in the Appendix are given in our response to reviewer g3ZB. Here, we focus on the changes we have made to improve the clarity of our model architecture and how it compares to existing models in the literature. We have added the following paragraph as Section 4.7 in the paper.

Comparison to Existing Architectures

SLiCEs are closely related to S6, the recurrent component of Mamba. In particular, if you remove the bias term (i.e. $B = 0$), then the continuous form of S6 is given by a LNCDE,

where

and the trainable parameters are $\alpha \in \mathbb{R}^d$, $\beta \in \mathbb{R}$, and diagonal $D \in \mathbb{R}^{d_h \times d_h}$ [1]. It is possible to include the bias term in the Linear NCDE formulation, as shown in [1], but S6’s expressivity still remains limited. Furthermore, the block-diagonal, DPLR, Walsh–Hadamard, and Sparse SLiCEs are maximally expressive without a bias term, so it is not included in the SLiCE architecture. The other key difference with the S6 architecture is considering more general forms for the driving term $\omega^{X}_t$. In particular, all the experiments in this paper use

In contrast to models such as Mamba, which combines the S6 recurrence with a convolution and gated MLP, each SLiCE recurrence is combined with only:

• a linear layer to mix the channels,
• a tanh activation function,
• layer normalisation, and
• a skip connection.

In addition to the above section, we have also included an algorithm outlining how to implement a structured linear CDE in practice.

Algorithm — Structured Linear CDE: The algorithm is presented for a dense state-transition matrix $A_{\theta}$. Comments indicate where the structure of $A_{\theta}$ can be used to reduce memory footprint and speed-up computation.

Input: $\boldsymbol{\omega}$ : $(B, L, d_\omega)$
Output: $\mathbf{h}$ : $(B, L, d_h)$

1. $\mathbf{h_0}$ : $(B, d_h)$ $\leftarrow$ $\xi_\phi(\boldsymbol{\omega_0})$

2. $\boldsymbol{\omega}^{\text{inc}}$ : $(B, L−1, d_\omega) \leftarrow \text{diff}(\boldsymbol{\omega})$

3. $A_{\theta}$ : $(d_\omega, d_h, d_h) \leftarrow$ Parameter  $\qquad\qquad\qquad\qquad\qquad\qquad\qquad$ # Exploit structure of $A_\theta$

4. $I$ : $(d_h, d_h) \leftarrow d_h\times d_h$ identity matrix

5. if mode = parallel then

6. $\quad F$ : $(B, L−1, d_h, d_h) \leftarrow I + \text{einsum}(bli, ijk \rightarrow bljk, \boldsymbol{\omega}^{\text{inc}}, A_\theta)$  # Broadcast $I$, exploit structure of $A_\theta$

7. $\quad F^{\text{comp}}$ : $(B, L−1, d_h, d_h) \leftarrow \text{pscan}(F)$ $\qquad\qquad\qquad\qquad\quad\ \$ # Parallel associative scan, exploit structure of $F$

8. $\quad \mathbf{h_{1:L-1}}$ : $(B, L-1, d_h) \leftarrow \text{einsum}(bljk, bk → blj, F^{\text{comp}}, \mathbf{h_0})$

9. $\quad \mathbf{h}$ : $(B, L, d_h) \leftarrow [\mathbf{h_0}, \mathbf{h_{1:L-1}}]$

10. else  $\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \$ # Recurrent pass

11. $\quad$for $t = 0$ to $L−2$:

12. $\quad \quad F_t$ : $(B, d_h, d_h) \leftarrow I + \text{einsum}(bi, ijk \rightarrow bjk, \boldsymbol{\omega_t}^{\text{inc}}, A_\theta)$  $\qquad$ # Exploit structure of $A_\theta$

13. $\quad \quad \mathbf{h_{t+1}}$ : $(B, d_h) \leftarrow \text{einsum}(bjk, bk \rightarrow bj, F_t, \mathbf{h_t})$ $\qquad\qquad\quad\ \$ # Exploit structure of $F$

14. $\quad$end for

15. $\quad \mathbf{h}$ : $(B, L, d_h) \leftarrow [\mathbf{h_0}, …, \mathbf{h_{L−1}}]$ $\qquad\qquad\qquad\qquad\qquad\qquad\ \ \$ # Stack along length axis

16. end if

17. return $\mathbf{h}$

Weaknesses

1. We believe that the comment regarding missing implementation details stem from a misunderstanding of the simplicity of our proposed models. In particular, there are no multiplicative gates, head dimensions, or sharing structure to provide details on. We hope that our proposed additional section clarifies this, and that you now feel the implementation details for our models are sufficiently provided in Appendix D.
2. We hope that the proposed additional section has also clarified several of your questions here. The speed difference between the diagonal LNCDE and Mamba is partly due to the additional structure surrounding the S6 recurrence, but also due to different hyper-parameter choices, which were selected via a grid search. We have also expanded the results on the UEA dataset to include all of the SLiCE architectures, as detailed in our response to reviewer 7XXo under the heading "Questions 1, 3, and 4".

Thank you for highlighting the distinction between S4 and S4D. We have updated our paper accordingly. Additionally, we have added a dedicated Limitations section to consolidate our discussion of constraints in one place.

[1] Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Terry Lyons. Theoretical foundations of deep selective state-space models. Advances in Neural Information Processing Systems, 2024.

Thank you very much for your detailed review.

Clarity

We have redrafted the paper to improve the clarity. In particular, we have included the following two new lines in the introduction:

1. After Line 19: "Linear Neural Controlled Differential Equations (LNCDEs) are a continuous-in-time sequence model where the state-transition matrix, or vector field, depends linearly on the current input. This allows for the multiplicative interactions between the input and hidden state necessary for gating."
2. After Line 28: "SLiCEs replace the dense state-transition matrix of an LNCDE with an efficient structured variant, such as block-diagonal, sparse, Walsh–Hadamard, or DPLR, which maintain the maximal expressivity of dense matrices whilst significantly reducing both the parameter count and computational cost."

Additionally, we have introduced a new chapter in the Appendix, which serves as a broad introduction to neural controlled differential equations. Topics covered include:

• Paths, including bounded variation and discretisation/interpolation,
• Solving controlled differential equations, including an expanded discussion on the discretised solve used in equation (2) (Lines 67-68),
• The signature and log-signature of a path, which are crucial tools in the proofs of Theorems 4.1, 4.2, and 4.3 and the Log-ODE method.

Furthermore, we have expanded our comparison to S6 and Mamba, by adding the following paragraph as Section 4.7 in the paper.

Comparison to Existing Architectures

SLiCEs are closely related to S6, the recurrent component of Mamba. In particular, if you remove the bias term (i.e. $B = 0$), then the continuous form of S6 is given by a LNCDE,

where

and the trainable parameters are $\alpha \in \mathbb{R}^d$, $\beta \in \mathbb{R}$, and diagonal $D \in \mathbb{R}^{d_h \times d_h}$ [1]. It is possible to include the bias term in the Linear NCDE formulation, as shown in [1], but S6’s expressivity still remains limited. Furthermore, the block-diagonal, DPLR, Walsh–Hadamard, and Sparse SLiCEs are maximally expressive without a bias term, so it is not included in the SLiCE architecture. The other key difference with the S6 architecture is considering more general forms for the driving term $\omega^{X}_t$. In particular, all the experiments in this paper use

In contrast to models such as Mamba, which combines the S6 recurrence with a convolution and gated MLP, each SLiCE recurrence is combined with only:

• a linear layer to mix the channels,
• a tanh activation function,
• layer normalisation, and
• a skip connection.

Toy Example

We appreciate your recommendation for a toy example, and believe this will significantly benefit the approachability of the paper. Therefore, we have added the following motivating example as a demonstration of the difference in expressivity between models which do not mix their hidden-state channels (i.e. models with diagonal state-transition matrices) and models which do mix their hidden-state channels.

Given a stream of bits

we want to predict the parity label defined by

where

Whenever a new bit is $1$ the label flips; if the bit is $0$ the label stays the same. If we consider a diagonal LNCDE with a hidden dimension of $2$ and $\omega^x_{k+1}-\omega^x_k = x_{k+1}$, then

and

With a linear read-out $r=(r_1,r_2)^\top$ followed by a monotone activation $\phi$ (such as $\tanh$, ReLU, sigmoid):

Since $f(S)$ has at most one turning point and $\phi$ is monotone, $\hat{p}_n$ can cross any chosen threshold at most twice. However, the true label $p_n$ flips every time $S_n \mapsto S_n + 1$. Hence, no diagonal $2 \times 2$ LNCDE can realise parity on arbitrarily long input.

However, if you replace $A$ with

then

Thus

Taking $r=(1,0)^\top$, $h_0^{(1)}=1$, and $\phi(s)=\bigl(1-\operatorname{sign}(s)\bigr)/2$,

Hence, a dense $2 \times 2$ LNCDE can solve parity exactly with a hidden dimension of 2.

Questions

1. Both the DPLR and diagonal-dense LNCDE use exclusively non-power-of-two dimensions for their hidden state on the regular-language tasks, and we do not see a major degradation in performance. In particular, the diagonal-dense LNCDE with a hidden dimension of $272$ achieves the highest average validation accuracy on the formal-language benchmark. For the UEA benchmarks, we specifically chose to match the hidden dimensions selected via the hyper-parameter grid search in [1] in order to isolate the impact of the SLiCE structure from alternative hyper-parameter choices.

2. Results for S6, Log-NCDE, and BD-LNCDE on a synthetically irregularly subsampled version of EigenWorms (70 % of the samples dropped):

   Model	EigenWorms (original)	EigenWorms (70 % dropped)
   S6	$85.0 \pm 16.1$	$76.3 \pm 11.8$
   Log-NCDE	$85.6 \pm 5.1$	$68.9 \pm 6.4$
   BD-LNCDE	$86.7 \pm 4.1$	$85.0 \pm 2.8$

   Table 1: Comparison of S6, Log-NCDE, and BD-LNCDE on irregularly subsampled EigenWorms.

   In addition to these results, we have significantly expanded our analysis of SLiCEs on the UEA datasets, including runtime comparisons. See our response to reviewer 7XXo for more details.

3. We have added the toy example outlined in the previous section.

Limitations

We have added a dedicated Limitations section to bring together our discussion of the constraints of this work in one place.

[1] 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 on Machine Learning, 2024.

Thank you very much for your thoughtful review.

Clarity

We have redrafted the abstract and introduction to improve the clarity. Key edits include:

1. Line 1: "This work introduces Structured Linear Controlled Differential Equations (SLiCEs), a unifying framework"
2. After Line 19: "Linear Neural Controlled Differential Equations (LNCDEs) are a continuous-in-time sequence model where the state-transition matrix, or vector field, depends linearly on the current input. This allows for the multiplicative interactions between the input and hidden state necessary for gating."
3. After Line 28: "SLiCEs replace the dense state-transition matrix of an LNCDE with an efficient structured variant, such as block-diagonal, sparse, Walsh–Hadamard, or DPLR, which maintain the maximal expressivity of dense matrices whilst significantly reducing both the parameter count and computational cost."
4. Line 30: "We introduce Structured Linear Controlled Differential Equations (SLiCEs)"

Questions

Questions 1, 3, and 4

We now evaluate all SLiCEs on the UEA benchmark. The D-DE and DPLR structure use a dense block of dimension $16$ and a rank of $4$, respectively, as these were the best-performing choices on the formal-language benchmarks. BD-LNCDE is the best-performing, followed by Log-NCDE, DE-LNCDE, and WH-LNCDE. We find that D-DE, S, and DPLR LNCDEs underperform S5, S6, LRU, and a D-LNCDE. Together with the formal-language tasks, these findings indicate that BD provides practical benefits relative to the other SLiCE structures considered. In particular, we believe the connection with multi-head attention (Lines 169-170) is important, and have redrafted our paper to expand this discussion.

Additionally, we have run a number of experiments comparing the time per $1000$ training steps for the different SLiCE structures on EigenWorms ($\approx 18{,}000$ observations). When computing recurrently, going from DE to D, BD, or WH reduces the run-time. Note DPLR actually has a longer runtime than DE. This is likely due to our implementation incurring the computational overhead of three separate operations, which outweighs the benefit of the reduced number of FLOPS. For the D and BD LNCDE, applying the parallel associative scan strictly decreases run time, as expected. Although the same is theoretically true for DE-LNCDE, the I/O costs are magnified for DE matrices, making the associative scan slower than recurrent computation when using a small number of parallel steps. Since WH and DPLR are treated as DE when applying a parallel associative scan, they follow the same behaviour. We did not include S in the comparison as it is always treated as DE.

Training time per 1 k steps (s)

We also compare runtime and GPU memory on EigenWorms when using the Log-ODE method. See our response to reviewer EATe for a theoretical computational cost analysis. The additional memory for BD-LNCDE is negligible. However, for WH-LNCDE, where the matrices are treated as dense, the Log-ODE method incurs significant additional memory. For both models, the Log-ODE method leads to a significant decrease in runtime. A parallel associative scan leads to further runtime reductions for the BD-LNCDE. However, for the WH-LNCDE, the parallel associative scan incurs too high a GPU memory cost when not using the Log-ODE method, and is slower than recurrent calculation when using the Log-ODE method. This is due to the high I/O costs when using dense matrices.

BD-LNCDE

WH-LNCDE

Question 2

Non-linear NCDEs numerically solve a non-linear differential equation, which is costly and recurrent.

Question 5

All SLiCEs use weight regularisation on their state-transition matrices. The paper did not make this explicit and we apologise for this oversight; the main body and Appendix now discuss it. In addition, due to training-stability issues, we constrained the entries of the Walsh–Hadamard LNCDE’s diagonal matrix to be in the range $[-1,1]$ (Lines 808-809, 856-857), restricting the eigenvalues of the state-transition matrix to modulus $\leq 1$. A broader investigation of regularisation techniques is important future work but sits outside the scope of this paper.

Question 6

All SLiCEs were initially evaluated on the formal-language tasks using the same number of non-zero parameters ($512$) in their state-transition matrices (Line 264). This yields a wide range of total parameter counts, owing to linear layers between SLiCE layers and varying hidden dimension with varying block sizes/ranks. To mitigate hidden-dimension effects, the WH, D-LNCDE, and all baselines were also run with hidden dimension $128$, with the best choice selected for each dataset (Lines 259, 265, 835, 851). We have clarified this motivation. In practice, WH-LNCDE performed better on some tasks with hidden dimension $128$ (cycle navigation, even pairs) and others with $512$ (modular arithmetic without brackets, parity). Overall average validation accuracies were $44.9$ (dim 128) and $45.2$ (dim 512).

Question 7

We have added a detailed comparison between D-LNCDEs and Mamba. See our response to reviewer oajU under the heading "Clarity" for full details. In brief, Mamba combines the S6 recurrence, a convolution, and a gated MLP, whereas LNCDEs are a recurrence followed by a non-linear channel mixing. We added S6 as a baseline on the formal-language tasks; it fails to solve modular arithmetic without brackets, suggesting that Mamba’s additional components are what enable performance above random guessing.

Question 8

We are adding a length-generalisation experiment on the A5 benchmark. Models are trained on sequences of lengths 3–40, with early stopping on a validation set of sequences of lengths 40–128. Preliminary results show nearly 90 % token accuracy for sequences up to 16 × longer than those seen in training.