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

• URL: http://arxiv.org/abs/2505.17761v1
• Date: Fri, 23 May 2025 11:34:21 GMT
• Title: Structured Linear CDEs: Maximally Expressive and Parallel-in-Time Sequence Models
• Authors: Benjamin Walker, Lingyi Yang, Nicola Muca Cirone, Cristopher Salvi, Terry Lyons,
• Abstract summary: We provide a unifying framework for sequence models with structured, input-dependent state-transition matrices.<n>We prove that, unlike the diagonal state-transition matrices of S4 and Mamba, SLiCEs employ block-diagonal, sparse, or Walsh--Hadamard matrices.<n> Empirically, SLiCEs solve the $A_5$ state-tracking benchmark with a single layer, achieve best-in-class length generalisation on regular language tasks among parallel-in-time models, and match the state-of-the-art performance of log neural controlled differential equations.
• Score: 6.389310720722303
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structured Linear Controlled Differential Equations (SLiCEs) provide a unifying framework for sequence models with structured, input-dependent state-transition matrices that retain the maximal expressivity of dense matrices whilst being cheaper to compute. The framework encompasses existing architectures, such as input-dependent block-diagonal linear recurrent neural networks and DeltaNet's diagonal-plus-low-rank structure, as well as two novel variants based on sparsity and the Walsh--Hadamard transform. We prove that, unlike the diagonal state-transition matrices of S4 and Mamba, SLiCEs employing block-diagonal, sparse, or Walsh--Hadamard matrices match the maximal expressivity of dense matrices. Empirically, SLiCEs solve the $A_5$ state-tracking benchmark with a single layer, achieve best-in-class length generalisation on regular language tasks among parallel-in-time models, and match the state-of-the-art performance of log neural controlled differential equations on six multivariate time-series classification datasets while cutting the average time per training step by a factor of twenty.

Related papers

• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• Fixed-Point RNNs: Interpolating from Diagonal to Dense [10.851383867834052]
  We investigate a class of dense linear RNNs as fixed-points of parallelizable diagonal RNNs.<n>The resulting models can naturally trade expressivity for efficiency at a fixed number of parameters.
  arXiv  Detail & Related papers  (2025-03-13T18:50:22Z)
• DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products [63.66021758150632]
  Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling.<n>Existing architectures face a fundamental trade-off between expressivity and efficiency, dictated by the structure of their state-transition matrices.<n>We introduce DeltaProduct, which takes multiple ($n_h$) steps per token and achieves superior state-tracking and language modeling capabilities.
  arXiv  Detail & Related papers  (2025-02-14T16:59:05Z)
• Classification of BCI-EEG based on augmented covariance matrix [0.0]
  We propose a new framework based on the augmented covariance extracted from an autoregressive model to improve motor imagery classification. We will test our approach on several datasets and several subjects using the MOABB framework.
  arXiv  Detail & Related papers  (2023-02-09T09:04:25Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences [16.59989033959959]
  We describe an efficient hierarchical method to compute attention in the Transformer architecture. Our method is superior to alternative sub-quadratic proposals by over +6 points on average on the Long Range Arena benchmark. It also sets a new SOTA test perplexity on One-Billion Word dataset with 5x fewer model parameters than that of the previous-best Transformer-based models.
  arXiv  Detail & Related papers  (2021-07-25T23:07:03Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.