Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
Authors: Aleksandar Terzic
Nicolas Menet
Michael Hersche
Thomas Hofmann
Abbas Rahimi
Venue: NeurIPS 2025 spotlight ()
Keywords: State-Space Models
Expressiveness
Efficiency
Matrix Parametrisation
State-Tracking
Finite-State Automata
Primary area: deep_learning
TL;DR: We propose a parametrisation of SSM transition matrices that enables SSMs to track states of arbitrary finite-state automata while keeping the cost of the parallel scan comparable to that of diagonal SSMs.

Abstract: Modern state-space models (SSMs) often utilize structured transition matrices
which enable efficient computation but pose restrictions on the model’s expressivity,
as measured in terms of the ability to emulate finite-state automata (FSA). While
unstructured transition matrices are optimal in terms of expressivity, they come
at a prohibitively high compute and memory cost, even for moderate state sizes.
We propose a structured sparse parametrization of transition matrices in SSMs
that enables FSA state tracking with provably optimal state size and depth, while
keeping the computational cost of the recurrence comparable to that of diagonal
SSMs. Our method, \emph{PD-SSM}, parametrizes the transition matrix as the product
of a column one-hot matrix ($P$) and a complex-valued diagonal matrix ($D$). As
a result, the computational cost of parallel scans scales linearly with the state
size. Theoretically, the model is BIBO-stable and can emulate any $N$-state FSA
with one layer of dimension $N$ and a linear readout of size $N ×N$, significantly
improving on all current structured SSM guarantees. Experimentally, the model
significantly outperforms a wide collection of modern SSM variants on various FSA
state tracking tasks. On multivariate time-series classification, it outperforms neural
controlled differential equations, a paradigm explicitly built for time-series analysis.
Finally, we integrate PD-SSM into a hybrid Transformer-SSM architecture and
demonstrate that the model can effectively track the states of a complex FSA in
which transitions are encoded into sets of variable-length English sentences. The
code is available at https://github.com/IBM/expressive-sparse-state-space-model.

Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models
Aleksandar Terzić
Nicolas Menet nicolas www.mtiie.nc.mmmmmmmmm
aleksandar wwrziciiiiia com
Michael Hersche
Thomas Hofmann thomas. hofmannčinf. ethz. ch
Abbas Rahimi' abrezurich. ibm com
mi sichael. www.eerrheeee cerrscheibmm com
IBM Research- Zurich, 'Department Computer Science, ETH Zürich
Abstract
Modern state-space models (SSMs) often utilize structured transition matrices which enable efficient computation but pose restrictions on the model's expressivity, as measured in terms the ability to emulate finite-state automata (FSA). While unstructured transition matrices optimal in terms of expressivity, they come at a prohibitively high compute and memory cost, even for moderate state sizes. We propose structured sparse parametrization of transition matrices in SSMs that enables FSA state tracking with provably optimal state size and depth, while keeping the computational cost of the recurrence comparable that of diagonal SSMs. Our method, PD-SSM, parametrizes the transition matrix as the product of column one-hot matrix (P) and a complex-valuee diagonal matrix (D). As a result, the computational cost of parallel scans scales linearly with the state size. Theoretically, the model is BIBO-stable and can emulate any --state FSA with one layer of dimension N and linear readout of size N x N, significantly improving on all current structured SSM guarantees. Experimentally, the model significantly outperforms a wide collection of modern SSM variants on various FSA state tracking tasks. multivariate time-series classification, outperforms neural controlled differential equations, paradigm explicitly built for time-series analysis. Finally, we integrate PD-SSM into hybrid Transformer-Sot demonstrate that the model can effectively track the states of complex FSA in which transitions are encoded into sets of variable-length English sentences. The code is available at https//ghhhbbbooo////////ssssi// stwpsus--stttt--p--emooooo
architecture and
Introduction
The Transformer /Vaswani al. 2017) marked paradigm shift in machine learning, providing unified yet versatile architecture with strong scalability. However, experimental and theoretical results indicate that Transformers struggle in algorithmic state tracking tasks such finite-state automaton (FSA) emulation (Hahn 2020 Bhattamishra et al. 2020 Merrill and Sabharwal 2023 Delétang et al. the attention
2023 Liu al. 2023 Strobl et al. 2024p. Moreover, the inherent quadratic mechanism hinders the training on very long sequences, and its linearly growing key/value cache can lead to memory issues during inference.
In contrast, state-space models (SSMs) (Gu et al. 2022b; Gupta et al. 2022 Fu et al. 2023 Smith
al. 2023 Orvieto et al. 2023 Gu and Dao 2023) offer scalable alternative Transtormers
"Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

with complementary properties: they generalize better to longer sequences, the number of total operations scales linearly with the sequence length, and memory is constant during inference. Modern large language models (LLMs) are increasingly adopting hybrid architecture that integrates both Transformer and SSM layers Yang et al. 2024 RRen et al. 2025 De et al. 2024 Waleffe et al. 2024 Lenz et al. 2025| Wu et al. 2025). To achieve computational efficiency competitive with that of Transformers, modern SSMs often utilize diagonal transition matrices. Empirically. in time-invarian SSMs, this strategy has proven effective in range of applications (Gupta et al. 20022] Gu et al. [022aa Orvieto et al. 2023), while time-varying diagonal SSMs can achieve language modeling performance comparable that of the Transformer (Gu and Dao 2023).
Despite their promising performance in language modeling, diagonal SSMs are restricted in the type of FSA they can emulate (Merrill et al. (2224). This stands in stark contrast with the nonlinear RNN, which can quickly learn such algorithmic abstractions (Delétang et al. (023). To enable FSA state tracking, previous approaches propose using transition matrices of various structures such as fully unstructured (i.e., dense) (Terzić et al. 2005), or (emii)structtree matrices such as block-diagonal (Fan et al. 2024), diagonal plus low-rank (DPLR) (Schlag et al. 202 la Yang et al. 2024; Walker et al. 2025| Peng et al. 2025) or products of DPLR matrices Siems et al. (2025). While any N -staate FSA can be represented by unstructured SSM with single layer, state dimensionality N, and a readout size N x N, unstructured SSMs scale unfavorably and thus prohibit large-scale training. Current
approaches more efficient, but do not allow for such compact encodings. With this in mind, the goal of this work can be summarized as follows:
We aim to enable single-layer time-varying SSMs with state size N and readout size N x N to represent any FSA with N states while keeping the cost comparable to that of diagonal SSMs.
To this end, we propose a novel structured sparse matrix parametrization of SSM transition matrices, denoted as PD) parametrization, defined as product of binary column-one-hnn matrix (P) and a complex-valuee diagonal matrix (D). A PD parametrization of transition matrices is preserved under multiplication, meaning that the product of PD matrices is still PD matrix. As such, chained product of PD matrices can be computed using parallel scans (Blelloch) I 1990; Martin and Cundy 2018 Smith et al. 2023) in ((LN) concurrent operations and (LL)) memory, matching the complexity and concurrency of a chain of diagonal matrix products. In terms of expressivity, the PD matrices encompass the commonly used diagonal transition matrices, but can also represent transition functions of arbitrary Ststate automata. Our contributions are as follows:
We propose PD-SSM, time-varying SSM that can emulate any N-state FSA with single layer, state dimension N, and linear readout of size N N. Theoretically, we prove that PD-SSM is stable and that it achieves universal FSA emulation with (almost) the least possible state size.
Empirically, we demonstrate that PD-SSM learns track the states of complex automata by exhibiting state-of-the the-aat length generalization. We furthermore test our model on long-range multivariate time-series classification tasks and observe that it exhibits high performance, comparable to that of neural controlled differential equations.
We provide a novel benchmark in which each FSA transition is redundantly encoded by meaningful English sentences. Adopting hybrid Transformer-Se SaMM architecture, we show that integrating PD-SSM enables the model to emulate the underlying FSA and to generalize to longer sequences, in contrast diagonal SSMs which fail in-domain sequences.
Background
2.1 State-Space Models
By state-space models (SSMs), we denote neural networks that utilize the recurrence equations
It A(u) B(u)u
yt = C(u)) + D(u)u
Ot (vv)
with Uy IR the input to the system, 2e E C its (hidden) state, y1 C the complex- valued output, and or IR_ the real-valued output. A(u) E NNN is the state transition matrix, B(u,) CDx N
2

---

Matrix Structure
Examplc Models
Solvable
Non-Solvable
Cost
R Diagonal
Mamba, S6, S7, GLA, mLSTM
X
x
((LN)
Diagonal
PD-SSM with 1ly (Ours)
*
((LN)
DPLR
(Gated) DeltaNet, DeltaProduct, RWKV-7
d*
v*
O(L
R Dense
SD-SSM
((L)2)
Structured Sparse
PD-SSM (Ours)
@(LN)
Table 1:
The structure of the transition matrix A(ux) in time-varying SSMs determines the class of FSA they can emulate. We consider two classes of automata, partitioned based on the solvability of their transformation group. v indicates that the structure enables the emulation of any N-state FSA from the partition using one layer, state dimension N and a linear readout of dimension indicates that the matrix structure can emulate any automaton from the partition, but potentially high dimension or depth, and in case of RWK exponentially large linear layers Siems et al. (2025).
x N. V*
The cost only considers the complexity of the parallel computation of (T. Modern DPLR methods trade off FLOPs for increased parallelism and better memory management. The recurrent complexity ((LN2), but modern methods utilize algorithms that scale quadratically in L Yang et al. 2024).
and C(u,)= E DxN map from embeddings to states and vice versa, and D(u,) E DD is a memoryless skip connection. Finally, 30 CP + IR" extracts a real-valued embedding from complex-valued embedding, often implemented as ('())) Re(y. (Gu et al. 2022a Gupta et al. 2022, Orvicto et al. 2023). The time-variance of the system stems from the time dependence of the A(ux) matrix, this being the crucial differentiator between time-varying and time-invariany SSMs (Gu and Dao 2023 Merrill al. 2024). We thus fix B ((4) B, C(,) = C, D(u)) = D.
A (ue) B(ue), C(uu), ) ((,)). In this work we only consider time dependence
If the system is time-invariant, i.e., A(u,) A, then its dynamics can be equivalently represented by diagonal transition matrix up an arbitrarily small perturbation of the entries of A (Orvieto et al. 2023 Axler 2024 Indeed, writing A WAW-1 results, upon change of basis ã, := W- I2, in an equivalent state evolution ã. = AĀ; + W-1 Bu, but with a diagonal state transition matrix A.
In contrast, if A(we) is function of time, then the system admits diagonal representation if and only if all A A(wx) are diagonalizable under the same change of basis. That is, there must exist a single WA, This is a much more restrictive condition. can in fact only be fulfilled if the matrix product commutes for all state transition matrices occurring (Axler 2024). This fact hints at the restrictiveness of diagonal transition matrices, which is expanded upon in an alternative framework in Section 2.3
W E CNNN such that for all I, A(we)
over time, i.e., Vi + j, A(v,) A(,,) =
2.2 Modeling Finite-State Automata with SSMs
In this work, we measure the expressivity of an SSM by considering the type of deterministic finite- state automaton (FSA) can emulate. deterministic FSA is an abstract model of computation defined as 5-tuple (Q, Σ, 5, finit. F) where Q is a finite set of states, Σ is finite input alphabet, 8 Q x Σ - Q is the state transition function, Zun E Q a fixed initial state, and C Q is the set of accepting states.
Any (deterministic) FSA can be mapped time-variant SSM follows. Encode each g E Q using enc: Q + 9 such that the encodings of different states are orthogonal. Note that orthogonality a sufficient but not necessary condition for mapping an FSA to a selective SSM, as certain automata such as modular counters allow alternative, more compact, mappings to SSMs. Given such an orthogonal encoding of states, we can map the state transition function 8 : Q x Σ + Q to the state transition matrices A(ue) via A(a) = ΣgEQ enc(ō(g, a)) enc(g)", set B = 0, C = I, D = 0, and x = id. Upon identification of with enc(q) and Pini with Do. the SSM matches the FSA exactly.
Ay > 0,4 D.A.RN NXN 3A. NXN
s.t. A. WAW-1 with diagonal A E NNN and JA Aelle
3

---

2.3 Limitations of Vareintriant SSMs for FSA State Tracking
To demonstrate the limitations of various SSMs structures for state tracking in automata, it suffices to consider automata with group structure in their state transitions. The transformation group (Straubing) 1994) of such an automaton is then the algebraic group of invertible state-to-state mappings with function composition as binary operation For conciseness, we equate such automata with their transformation group, thus saying, for instance, solvable automaton.
Through a circuit complexity argument, Merrill et al. (024) showed that non-solvable automata cannot be emulated using bounded-depth logarithmic precision diagonal fime-variant SSMs, providing an upper bound on their expressivity. Through an explicit construction Sarrof et al.l (2024) demonstrate that all solvable automata can be emulated using finite-precision complex-valued diagonal time-variant SSMs, although the depth of the SSM stack exhibits a non-trivial dependence on the complexity of the FSA. Concretely, the SSM stack depth is proportional
the Krohn-Rhodes complexity of the transformation group Margolis et al. (2024). A more recent family of time-variant SSM models utilizes diagonal plus low-rank (DPLR) transition matrices Grazzi et al. (2024): Peng et al. (2025);
Siems ct al. (2025). While such matrices enable the emulation of any FSA, the necessary model depth either a function of the automaton's is structure, or the model requires exponentially large linear layers Siems et al. (2025). In contrast, unstructured SSMs Terzić et al.] (2025); Walker et (2025) enable the emulation of any N-state FSA using a single layer, a state size of N and a readout size N x N. However, they scale poorly with the state size. For an overview of the results, see Table
2.4 Associative Scan for Fully Parallelizable Recurrence SSMs
We use parallel scans to concurrently compute the states of an SSM (Belloch 1990 Martin and Cundy|2011 2018 Smith et al. 2023). Suppose a binary associative operator i.c., (a and a sequence of elements (a1, 022 a2,..., "a......,r... ar.]- The scan operation (sometimes referred to as all- prefix-sum) then returns the sequence (a1, (01 02)).... . (01 02 of the linear recurrence of a (lie-variiat) SSM x, = A, + b, takes precisely the form of a parallel sean (Ar4 b (Ac, b,) (Ac+1 Ar, Ac+ + be+1) with prefix elements dr = (Ar, be). According to Blelloch 19900. Section 1.4), associative scans can be computed in θ L) total operations (i.e., in work-efficient manner) with Olog L) sequential steps, where To represents the cost of matrix-matrix multiplication. For dense matrices A, E NNN To O(N3) and thus the associative scan quickly becomes prohibitively expensive in deep learning settings. In contrast, if A, are diagonal matrices, To = O(N). terms of memory, parallel scans with dense matrices use ((N2L) memory, whereas diagonal matrices lead to a ((NL) memory consumption.
c).
az)] Note that composition
3 PD Parametrization for Efficient and Expressive Transition Matrices
Prior research indicates that the expressiveness of time- varying SSMs can be significantly enhanced by relaxing the structural constraints of the transition matrix A (1) to allow for non-diagonal structures. (Merrill et al. 2024 Cirone et al. 2024 Terzić et al. 2025). ) As noted by Terzić et al. (2025), relaxation to arbitrary matrices prohibitively increases the compute cost of paralel scans from ((T.N) to (I.N3). To circumvent these limitations, we propose to parameterize the transition matrices as the product A(u)) = P(u.) (((u,)((u) ((+),, where P(w4) is a binary matrix in which each column has single non-zero element, and D(u,) is complex-valued diagonal matrix.
Figure presents our architecture for generating transition matrices with PD parametrization. The diagonal matrices are generated by two nonlinear feed-forward neural networks, each with a single hidden layer employing the GeLU nonlinearity Tellu and a saturating nonlinearity in the form of the sigmoid a. The two networks define a magnitude generator D(4)) and phase generator of ((())))
D(u)) = o OW.M (o (W," un + BM) + 6 E (0,
((((w)) = (w: (a
(a (W,P un + b,)) + b()) E 2m)
Concerning the column one-hot matrix P. the input in generates the weights s(u)), which are used to soft-select among a set of trainable transition matrices, written as the dictionary {M, E RNNN with K being hyperparameter. Sparsity of P is achieved by applying column-wise hardmax after
[ ]igjk]
A more complete background algebra and results SSM expressivity is provided in Appendix A

---

Column one-hot matrix generator
(M E R R.XNY B.
Linear
Softmax
a(te) & A R-
E sa(u)) BNAN
Column Sparsification
P(u) E 10,1)
Complex diagonal matrix generator
Magnitude
[D(w)] 1)
v:
MLP
Diu) eA
A(m) P(u)D(())
Phase MLPP
explio(D(ww))) fx O:la - 17"
Figure 1: The PD parametrization can be integrated into any selective SSM by adopting the shown
architecture for generation of structured sparse state transition matrices A(we) - P(ur).
soft-selection of the state transition. More formally:
s(u+) = softmax (Su:) E A-1
M(u)) Σ Sx(w))M RNNNN R=1 (u)(ue) hardmax(M.,,(ut)) E {0, 13 where hardmax(x); := òi, max, at
The parametrization is motivated by Terzić et al. 2025), which has shown that models utilizing normalized Fan et al. (2024) convex combinations of dense transition matrices can achieve perfect length generalization FSA emulation tasks and are parameter-effiee
compared alternative proposals such e.g. (Hasani et al. 2023 Fan et al. 2024 Merrill et al. 2024).
The P and D factors of our parametrization have complementary strengths for encoding automata into time-varying SSMs. The matrix enables emulating any FSA, but the required dimension scales linearly with the number of states. For cyclic automata, which form central building block of all solvable automata (Krohn and Rhodes] 1965) Sarrof et al. (024). complex diagonal matrices provide more compact encoding compared to column one-hot matrices. Visual intuition is provided in Figure 2 Additionally, as proven in the following section, the diagonal matrices provide guarantee for the system's 's BIBO stability as the magnitude of each entry lies in (0, 1).
1
A(0) expli
1
A(1) exp(- -
00
00
A(0)
100
A(1) =
0
(a) non-cyclic FSA and its corresponding column one-hot transition matrices.
(b) A cyclic FSA whose behavior be ulated with single complex number.
Figure 2: Any -tstate FSA can be encoded using sparse binary N N transition matrices (a), but modular counters admit more compact representation based on diagonal transition matrices (b).

---

3.1 Surrogate Gradients
aP(M) is generalized function- it vanishes almost everywhere, except at isolated Strictly speaking, ]M[u] points where exhibits Dirac delta-like singularities. To smooth these singularities over sets of non-zero measure, we approximate the hardmax with softmax during the backward pass.
ap
Thardmax(M1
@softmax
0M
FM
This is reminiscent of the slope-annealed straight-throug estimator (Bengio et al. 2013: Paulus al. (222). yet we use stochasticity neither in the forward nor in the backward pass (ablations with stochastic categorical sampling in P' are reported in Appendix EB. Note that during the forward pass we do not relax the hardmax, since doing so would break the sparsity essential for efficient parallel scan. With tempered softmax in the low-temperature limit, the above expression becomes exact.
3.2 Algebraic Structure of the PD Parametrization
In this section, we formalize the set of transition matrices H XN that are decomposable into a binary one-hot column matrix and a complex diagonal matrix D. Note that our PD matrices exhibit such column one-hot structure. Hence, all of the subsequent statements made for the set HI immediately also hold for our matrix parametrization. All proofs are Appendix C
Definition 1 (One-hot Column Matrices). Let MI := {A C
|
= 1} where
||œ|| denotes the e- "norm" " counting the number of non-zero entries in x.
Under matrix multiplication as binary operation, X
X forms monoid.
Property (Algebraic Structure of One-hot Column Matrices). NxN a monoid under matrix multiplication, i.e., it is closed under associative matrix multiplication and contains the identity.
Closure under multiplication is essential for efficient chained matrix multiplication via parallel scans, because matrix multiplication in NxN can be implemented in ((N) instead of the usual (NN3). as formalized by Property and visualized in Figure
Property 2 (Computational Efficiency of Matrix Multiplication in HNN), Let A, E NNN Then C = AB E HH N can be computed in ((N) arithmetic operations.
0
0
07
0
0
72
8
0
2]
0
0
0
0
0
=
act
oy
0
[
0
0
0
0
0
7
t
1
2
0
2
2]
[1
2
[1
0]
[a
B 7
[xx:
ory
72)
fox
ay
72)
Figure 3: Left: The sparse matrices in N can be efficiently represented by separately storing the indices of the active elements and their values. Center: The indices of the matrix product are computed with gather-scatter operation. Right: The nonzero entries of the matrix product computed using gather- scatter followed by clement-wise multiplication.
3.3 Stability and Expressivity of the PD Parametrization
If the PD parametrization is adopted for state transition matrices and if one ensures matrix entries inside the complex unit circle, then the state space model becomes provably bounded-input, bounded- output (BIBO) stable. Note that parametrization of [(4)) with sigmoid-based MI.P ensures all conditions for BIBO stability are met.
Proposition 1 (System Stability under PD- Parametriizziion) Let E (0, 1] and consider the state transition Ia A + b, with A, E HNNN ||Allo I E. Let further ||ool|2 S B and |bbll2 < B for B R.. Then it holds that
||x||22 I VNB/s Vt.
(2)

---

As direct consequence of the FSA to SSM mapping described in Section 2.2 Proposition 2 (Expressivity of PD Parametrization). Any FSA with N states can be exactly repre- sented by a single-layer PD-SSM with a state size N and linear readout of size N x N.
Proposition hoolds
Not only can PD-SSMs represent any FSA, they do so with the (almost) smallest state size possible, L... PD-SSMs are maximally expressive for regular languages.
Proposition 3 (Optimality of PD Parametrization) For any N there exists a finite-stan state automaton with N states that cannot be emulated by any single-layer SSM with state size less than N - under unique state encodings.
The assumption of unique state encodings, meaning that each state is represented by a single, unique vector, is practical necessity for readout. Indeed, without unique state encodings (and with arbitrary precision). even a single-layer real SSM with state size can represent any FSA, albeit in a format that requires exponentially large lookup tables to read out. Proposition 3 makes this statement exact. Proposition 4 (Arbitrary Precision and Readout). Consider I++1 It be where by ue k2 with Uy E Q input encodings and k2 = /Pi E R R2Q time encodings, where pt is the t-th prime. Then, any FSA can be encoded into this scalar-valued SSM under an appropriate lookup table readout.
4 Results
4.1 Runtime Measurements
We first measure how the runtime of a single-layer SSM scales as a function of the transition matrix structure as well as the hidden dimension on an NVIDIA A100-80GB GPU. We compare PD-SSM with the unstructured (dense) relled SD-
Dense SD-SSM
SSM Terzic et al. 2025), as well as a diagonal vari- ant of PD-SSM that sets A(u,) = D(ue) C... To equalize the effective state size, the state dimen- sionality N, of the real-valued dense SSM is twice that of the complex- valued models No. The embed- ding size is scaled D N, = 2. Figure we see that PD-SSM scales significantly better than the dense SSM, with a 71 x speed-up at D 5632. At this dimension, the diagonal SSM is 7x faster than PD-SSM. The PD model's higher runtime mainly stems from the additional operations in the generation of matrices. For more details and results under different settings, see Appendix D
Sparse PD-55M
Diagunal SSM
Time [ms]
10
10a
10
256
2048
4096 5632
Hidden Dimention
Figure 4: Runtimes of single-layer SSMs with varying dimension and sequence length 64.
4.2 FSA Emulation
We first evaluate our model on a set of automaton state tracking tasks, originally introduced in Delé tang et al. (2023). The four tasks correspond to four finite-state automata of various complexities. The benchmark is centered at evaluating the length generalization of the models, which serves as a proxy of the model having learned the correct algorithmic abstraction, avoiding fixed-length shortcut solutions Liu et al. (2023). Concretely, the models are trained for 100,000 steps on randomly sampled sequences of inputs of length 3 to 40, and are evaluated on sequences of length 40-256. We extend the set of results from Walker et al. (2025) which evaluates each model under a single varying hyperparameter choice, state dimensionality of 128 512. We instead fix the dimensionality to 128, finding that it is sufficient for high performance. Table 2 reports the mean and standard deviation of the best validation accuracy of five randomly initialized models. The set of evaluated models consists of recurrent and parallelizable models, where we bold and underline the best and second-best parallclizable model, respectively. Excluding the Transformer, the parallelizable models can be interpreted as SSMs with various transition matrix structures, namely diagonal (Gu and Dao (2023): Walker et al. (2025) and our C diagonal model defined by setting P(u+) to identity). diagonal plus low-rank (Schlag et al. (2021a) Yang et al. (2024); Grazzi et al. (2024), product of diagonal plus low-rank (Walker et al. 2025 Peng et al. 2025 Siems et al. 2025), as well as alternative variants including block-diagonal,
Walsh-Hadamane matrix modulated by an input-dependent diagonal matrix, and mixture of diagonal and dense matrices Walker et al. (2025). As we can read from the table, our model performs best, with significant margin over the second-ber method.
7

---

Model
Cycle Nav.
Even Pairs
Mod Arith.
Parity
Average
Recurrent
LSTM
100.0 = 0.0
100.0 0.0
99.9
100.0 = 0.0
100.0 = 0.0
sLSTM
32.5 # 0.4
100.0 0.0
0..6
100.0 = 0.0
65.1 + 0.2
XLSTM[1:1]
53.5 5.6
99.0 1.9
29.3 # 1.6
100.0 + 0.0
70.5 + 1.5
Parallel
Transformer
24.4 0.5
90.4 10.4
23.6 0.7
5.42
2.6
Mamba
2.2
1.0
3.6
54.2#2.1
58.9 1.8
D-SLiCE
6.3
1.0
2.1
1.0.0
72.6
C Diag.
9..4
8.84
29.9
61.8
73.6
DeltaNet
4.7
1.0
4..2
57.8
1.7
DeltaNNetf-L.1]
4.17
1.0
6.8
97.7
2.7
Gated DeltaNet
8.8
1
4.2
1.95
6.0
Gated DeltaProductt-1.1]
6.6
1.0
10.9
98.0
8.27
RWKV-7
5.0
8 14.2
6.1
51.1
5..1
DPLR-SLiCE,, -
81.1 16.6
100.0 0.0
69.3
91.0
+
WH-SLiCE
6.8
93.1
2.1
71.4
64.5 5.2
BD-SLiCE,,
99.8 0.2
81.3
54.0 12.5
9.9
83.8 + 4.3
D-DE-SLiCEd, =272,b=16
73.3 29.4
84.8
98.4
83.8
85. 8.2
PD-SSM
99.5 2 0.7
99.7
96.2
99.9
98.8 + 0.9
Random
20.0
50.0
20.0
50.0
35.0
Table 2: Average and standard deviation of validation accuracy across seeds for range of models on FSA emulation tasks. The baseline results are taken from (Walker et al. 2025).
We further analyse the method on two non-solvable groups, As and S3. For both groups, consisting of 60 and 120 permutations respectively, all of the group elements can be generated using only two permutations corresponding to two transition matrices per the mapping in Secion 2.2 To increase the connectivity of the resulting automaton's s states, we introduce additional randomly selected permutations. We compare PD-SSM with K = 32 against two layers of the complex diagonal model with A Aww) D(u)). and one two layers of DPLR model, Gated DeltaProduct [-1,1] with n, 4 (Siems et al. (025). with state dimension 128. We perform learning rate grid search and train the models for 100,000 steps with batch size 256. We train the models on sequences of length up to 40 and report the best validation accuracy on sequences of length up to 40-256 in Table
Model
Depth
(Ag, 2)
(As, 6)
(As, 8)
(As, 12)
(Ss, 4)
(Ss, 8)
(S,, 32)
C Diagonal
2
15.5
Gated DP [-1,1] Gated DP [-1.1]
97.9
92.5
91.8
60.5
88.7
57.4
1.23
68.4
84.7
62.2
PD-SSM
100.0
100.0
100.0
100.0
100.0
100.0
1.07
Table 3: Best validation accuracy (%) on longer sequences across 3 random seeds. Each task is defined in terms of non-solvable algebraic group (A, Ss) generated with redundant set of permutations, the cardinality which the number n each tuple (As or S,
As predicted by the theory, the complex diagonal model fails on the simplest task, (Ag, 2). Gated DeltaProduct with nı, = 4 exhibits degrading accuracy with a higher number permutations, which cannot be recovered by stacking two layers of the model. PD-SSM maintains full accuracy for all automata with a single layer, excepting S₁ with 32 generating permutations.
4.3 Multivariate Time-Series Classification
We next provide an evaluation on multivariate time-series classification. We evaluate our model on a subset the University of East Anglia (UEA) Multivariate Time-Series Classification Archive (UEA-MTSCA) (Dau et al. 2019), extending on the results from Walker et al. (0024); Rusch and Rus 2025). We consider six tasks from the archive previously selected due to their long sequence lengths, which range from around 400 over 17,000. Conforming to the evaluation methodology

---

and data splits defined in Rusch and Rus (2025); Walker et al. (2024), we report the average and standard deviation of the test accuracy across five random initializations, with the hyperparameter grid conforming to that of (Rusch and Rus 2025) with the exception of the state size, which in our case selected from (16, 64, ]28} as opposed {16, 64, 256] of the baselines. The set of evaluated models includes neural controlled differential equations (Walker et al. 2024). LTT SSMs (Smith et al. 2023; Orvieto et al. 2023), time-varying SSMs (Gu and Dao 2023). as well as an SSM paradigm based on system of forced harmonic oscillators (Rusch and Rus 2025). The results are reported in As we can see, our model maintains very high accuracy on this set tasks, achieving an estimated mean accuracy that is within standard error of the sate-of-the of-the art SSM.
Table 4
Model
Worms
SCP1
SCP2
Ethanol
Heartbeat
Motor
Average
NRDE
83,9 7.3
53.7 2.5
6.9
25.3 1.8
72.9 4.8
5.7
60.6 2.15
NCDE
75.0 5.1
53.0 5.6
6.5
2.6
4.8
60.2 1.76
Log-NCDE
83.
4.17
3,44
4.6
5.33
64.3 + 1.99
LRU
878
82.6
51.2
21.5
6.7
5.0
61.7 + 1.72
S5
8..1
4.6
2.6
24.1
47.7 7.5
61.8 + 1.83
S6
85.0
8.78
4..9
2.44
8.3
51.3 4.7
62.0 +
Mamba
15.9
8.47
48.2
2..9
3.82
47.7
58.6 + 2.99
LinOSS-IMEX
2.70
4.0
8.1
2..
4.3
57.9 5.3
65.0 + 1.95
LinOSS-IM
9..0
2.6
6.9
0.6
3.7
60.0 7.5
67.8 + 2.00
PD-SSM
5.70
80,9 # 2.0
56.1 8.6
3..7
80.0 + 2.6
60.0 + 3.7
67.0 2.02
Table 4: Mean and standard deviation of test accuracies across 5 seeds selected long-sequence UEA time-series classification datasets as per (Rusch and Rus 2025)
4.4 Long-Range Arena
The long-range arena (Tay et al. 2021) dataset (LRA) covers mathematical expressions, freeform text, and images, all represented in sequences up length 16k. We evaluate model subset of LRA, with sequences up to length 4k. The baseline results are taken from Soydan et al. (2024). We consistently use 4 layers with embedding dimension 128 and state dimension 128 for all tasks except Retrieval, which used state dimension 64.
For all tasks, the transition matrix dictio- nary size is set K 6. Time-invarinn invariant SSMs perform significantly better on av- erage than the shown collection of time- variant ones. Among the variantriant SSMs (Mamba, S7, and PD-SSM), ours performs best average on this set of tasks. Together with the time-series re- sults, this serves as evidence that the PD parametrization can be effective on realis- tic leng-eequence tasks.
Time-Invarian
Time-Variant
Dataset
S4
LRU
Mamba
S7
PD FD-SSM
ListOps
59.6
60.2
38.0
63.8
61.0
Text
86.8
89.4
83.0
87.2
88.1
Image
88.6
89.0
69.8
70.4
Retrieval
90.9
89.9
72.1
91.8
90.0
Pathfinder
94.2
95.1
69.3
65.5
62.6
Average
84.0
84.7
66.4
73.9
74.4
Table 5: LRA results, average over 3 seeds.
4.5 State Tracking in Natural Language
Finally, we introduce a novel task which we call state tracking in natural language, more complex version of the FSA state tracking task with the crucial difference that the inputs encoded in natural language. As result, state transition is only triggered after a length- varying sequence of tokens. A real-world instance of such state tracking in natural language is geographic location tracking given text information, where the model has to work with descriptions such as I took the bus. I walked, and went for a run. In this benehmark, we assume that an agent transitions through a fixed state space according sequence of meaningful English sentences. Each transition in the underlying automaton is redundantly encoded through multiple sentences of different lengths. For instance, Aş is understood as enc-
I walked. went for run.
jogged.
took the plane, Twnt by train. drove.
Figure 5: Cayley diagram of the As group (Carter 2009). We encode state transitions into sets of English sentences.

---

oding a transportation network where an agent can either move along ring of motorized trans- portation (via bus. plane, train, car) move (i.e., walk, run, jog, hike) between such rings. Red transitions correspond to movement using motorized transport, whereas blue transitions are taken without motorized transport, see Figure 5 Figure shows the performance diagonal SSMs as well as PD-SSM for state tracking in natural language. To benefit from large-scale pretraining and to demonstrate the modularity of our approach, we freeze a pretrained Qwen 2.5-1.5B model and replace its final layer with single trainable SSM layer. This analysis centers around the applicability of the sparse parametrization in larger-scale setting, and also serves as a test of the utility the PD parametrization opposed to purely diagonal models. Concretely, we vary the matrix structure such that it is either real-valued diagonal (A(u) = (u,)), complex- or structured sparse (A(u,) = P(u,) ((u,). We train the model for 100,000 steps with batches of size 256. Each batch consists of sequences English sentences, with the number of sentences randomly sampled up 25, each sentence triggering state transition in the underlying automaton. The automata are Parity and A5 with two generators as Figure [ In Figure 6 we report the best validation performance out of 3 random seeds of each model with equivalent hyperparameter grid search. Even though complex diagonal SSMs can represent parity (Sarrof et al. (024), the models did not learn to do in the experiments. On this task, PD-SSM converges within 10,000 steps.
diagonal ( (A(u)) = D (u,)),
1.00
1.0
0.75
0.6
0.50
Real Diagonal SSM
Diegonal
0.25
Complex Disgonal SSM
Complex Diagonal SSM
PD-SSM
PD-SSM
0.00
00
10
15
20
25
35
Length
Length
(a) Accuracy the natural language version of Parity
(b) Accuracy the natural language version of As
Figure 6: Applying one layer of our PD-SSM at the output of a frozen Qwen-2.5 1.5B allows the model learn to follow the state transitions of automata when the inputs are redundantly encoded in English sentences. The vertical dashed line indicates the maximum training sequence length.
Conclusion
We introduced an expressive and efficient structured sparse parametrization of transition matrices for time-varying SSMs manifesting in the PD-SSM architecture. Theoretically, PD-SSM can emulate arbitrary finite-state automata while reaching the lower bound on the network depth and state size required to do so in the worst case. It is significantly more efficient than unstructured SSMs and reaches new state-of- oftth---- in synthetic state-tracking tasks. Among the investigated time-varying SSMs, PD-SSM on average performs best tasks from the LRA benchmark requiring the processing of long sequences (up to 4k), and additionally exhibits high performance on multivariate time-series classification with long sequences (up to 17k), demonstrating performance within standard error of the saate-of-th-aae SSM. Finally, we verified its effectiveness in a hybrid Attention-SSS architecture on novel state-tracking in natural language task, showing that it can track non-solvable automaton states even when the inputs are redundantly encoded in variable-length English sentences.
Limitations and Future Work Although we significantly improve upon the scalability of SD-SSM while retaining its favorable expressivity, PD-SSM still incurs overhead when generating the P(u)) matrices. Our future work will investigate how our method can benefit from more efficient one-hot column matrix generation strategies, and how it can be utilized in large-scale pretraining.
6 Broader Impact
The paper introduces a novel neural network architecture with increased expressivity while retaining efficiency. More expressive and efficient models can potentially have unpredictable societal impacts in the future, but do not foresee any immediate and direct negative impact of this work.
10

---

Acknowledgement
This work is supported by the Swiss National Science foundation (SNF), grant 10002666.
References
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. S. Axler. Linear Algebra Done Right. International Publishing, Cham, 2024.
Undergraduate Texts in Mathematics. Springer URL Dtttps://likk.pprtee springer. com/10. 1007/
978-3- 001-0331-1120000
D. A. Barrington. woutded-width polynomial-size branching programs recognize exactly those lan- guages in NC1. Journal of Computer and System Sciences, 3801):150-16,,, 1989. ISSN 0022-0000.
URI. wwwp://wieeeeiieee......o. com http///eteeeeerrrre/////////////
Y. Bengio, N. Léonard, and A. Courville. Estimating or propagating gradients through stochastic
neurons for conditional computation. arXiv preprint arXiv: 1308.333, 2013. URL https
//arxiv.org wwwp///0.... 3432
Bhattamishra, K. Ahuja, and N. Goyal. On the Ability and Limitations of Transformers to Recognize Formal Languages. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 7096-7116 16. Association for Computational Linguistics, 2020. doi:
URL
https: http:::/wwwww.lll
org/
anthology/2020. emnlp main. 576)
C. H. Bischof and C. Van Loan. The WY Representation for Products of Householder Matrices. SIAM Journal on Scientific and Statistical Computing, 8(1):s2-s13, 1987. doi: 10.1137/0908009
G. E. Blelloch. Prefix Sums and Their Applications, 1990.
N. C. Carter. Visual group theory. Classroom resource materials. Mathematical Association of
America, Washington, D.C., 2009.
N. M. Cirone, A. Orvieto, B. Walker, C. Salvi, and T. Lyons. Theoretical foundations of deep selective
state-space models. In Advances in Neural Information Processing Systems (NeurIPS), 2024. URL
https://openreviice wwt./eee/fooooee ? 1dd332zxx qwupux
T. Dao. 2lashAttcnniion-2:: Faster attention with better parallelism and work partitioning. In Interna- tional Conference on Learning Representationns (ICLR), 2024.
H. A. Dau, A. Bagnall, K. Kamgar, C.-C. M. Yeh, Y. Zhu, Gharghabi, C. A. Ratanamahatana, and E. Keogh. The ucr time series archive. JEEE/CAA Journal of Automatica Sinica, 6()):1293.1305.
2019. doi: 10. 109/1A...09........ 191117777
S. De. S. L. Smith, A. Fernando, A. Botev, G. Cristian-Muraru, A. Gu, R. Haroun, L. Berrada, Y. Chen, S. Srinivasan, G. Desjardins, A. Doucet, D. Budden, Y. W. Teh, R. Pascanu, N. De Freitas, and C. Gulcehre. Griffin: Mixing gated linear recurrences with local attention for efficient language http:/awwxvv.../raaea////
models. arXiv preprint arXiv:2402. 19427, Feb. 2024. URL 19427
org 2402
G. Delétang, A. Ruoss, J. Grau-Moya, T. Genewein, L. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg. J. Veness, and P. A. Ortega. Neural networks and the Chomsky hierarchy. In The Eleventh International Conference on Learning Representations (ICLR), 2023. URL https 7/openreview. .ne// htte:/oormmmmddxxxiiaaa
T. H. Fan, T.-C. Chi, and A. I. Rudnicky. Advancing regular language reasoning in linear recur- rent neural networks. In Proceedings of the 2024 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies (Vol- ume 2: Short Pupers), pages 45-53. Association for Computational Linguistics, 2024. URL org/2024.
ssttss:/aclanttolll
D. Y. Fu, T. Dao, K. K. Saab, A. W. Thomas, A. Rudra. and C. Re. Hungry hungry hippos:
Towards language modeling with state space models. In The Eleventh International Conference on Learning Representations (ICLR), 2023. URL https: hattps///penr:: //tp////pp/ee..e///////e/e.eeeee www//eeeu////n/ie ddDDDDDDWWGGGG
R. Grazzi, J. Siems, J. K. Franke, A. Zela, F. Hutter, and M. Pontil. Unlocking state-tracking in
linear RNNs through negative eigenvalues. In NeurlPS 2024 Workshop on Mathematics of Modern
Machine Learning, 2024. URL https:
wew. frrmm? id E.G.oxxGGGKKKKX
A. Gu and T. Dao. Mamba: Linear-Time Sequence Modeling with Selective State Spaces. arXiv preprint arXiv:2312.0075:
2023. h httt::/tt//iiii http://aaaxiv..o/ab///////a 2312200772222222
A. Gu, T. Dao, S. Ermon, A. Rudra, and C. Ré. HiPPO: Recurrent Memory with Optimal Poly- nomial Projections. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors,
11

---

Advances in Neural Information Processingg Systems, volume 33, pages 1474-1487. Curran As- sociates, Inc., 2020. URU/attps://proeeciige www.iiinnnn.n........r..mrrri nwwripe f F1le/ 2al.aa/000088000000777799--0-0 Paper. pdf
A. Gu, I. Johnson, K. Goel, K. Saab, T. Dao, A. Rudra, and C. Ré. Combining Recurrent, Convo- lutional, and Continuous-time Models with Linear State-Space Layers. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 572-585, 2021.
A. Gu, K. Goel, A. Gupta, and C. Ré. On the parameterization and initialization of diagonal state space models. In Advances in Neural Information Processing Systems (NewrIPS), volume 35, pages 2022a. URL https:://proceeedinggg neurips http:/ppprfffeeeeeeeeepp p 2022/file/ e932ff a cat. Conference. påf
35971-35998
A. Gu, K. Goel, and C. Ré. Efficiently modeling long sequences with structured state spaces. In Inter- national Conference on Learning Representations (ICIR), 2022b. URL httl.hhtps:/// bhttpps://openeviiie
net/forrmmidduu/PPer
A. Gupta, A. Gu, and J. Berant. Diagonal state spaces are as effective as structured state spaces. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 22982- 22994, 2022. URL https: http://///ooceee..eeeeee neurips. wwwpuaiii..ccppppppeeeeeoep (tt.://fffaaaa11187c44446eee
pdf
M. Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguisties. 8:156-1711 01 2020. ISSN 2307-387X. doi:
10.1162/tacl_ a 00306. URL httpp://dooi.
R. Hasani, M. Lechner. T.-H. Wang. M. Chahine, A. Amini, and D. Rus. Liquid structural state-space models. In The Eleventh International Conference on Learning Representations (ICLR), 2023.
URL httL:htts::///t /ttb:::://peerreeev... wtw.i//www.e//ooummmmmmm oot.roorummmnnggTTTKKTTTTTTT
S. Hochreiter and J. Schmidhuber. Long short- memory. Neural Computation, 9(8) 17800
Nov. 1997. jttps://///// mit. wdw/neco/ ctt.c//////////111/1 E. Jaffe. Linearly independent integer roots over the scalar field q. The University of Chicago, 2007.
E. Jang, S. Gu, and B. Poole. Categorical reparameterization with gumbel-softmax. In 5th
International Conference on Learning Representations ICLR. OpenReview.net, 2017. URL http:/oorummmiddrt333eee
K. Krohn and J. Rhodes. Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines. Transactions of the American Mathematical Sociery, 116:450-464, 1965. ISSN 00029947, 10886850. doi: 10.2307/1994127. URL /ttt:://wwww jstor org/ Publisher: American Mathematical Society.
Stable/1994125
B. Benzz, O. Lieber, A. Arazi, A. Bergman, A. Manevich, B. Peleg, B. Aviram, C. Almagor, C. Fridman, D. Padnos, D. Gissin, D. Jannai, D. Muhlgay, D. Zimberg, E. M. Gerber, E. Dolev, E. Krakovsky, E. Safahi, E. Schwartz, G. Cohen, G. Shachaf, H. Rozenblum, H. Bata, I. Blass, I. Magar, I. Dalmedigos, J. Osin, J. Fadlon, M. Rozman, M. Danos, M. Gokhman, M. Zusman, N. Gidron, N. Ratner, N. Gat, N. Rozen, O. Fried, O. Leshno, O. Antverg, O. Abend, O. Dagan, O. Co- havi, R. Alon, R. Belson, R. Cohen, R. Gilad, R. Glozman, S. Lev, S. Shalev-Shwartz, S. H. Meirom. T. Delbari. T. Ness, Asida. T. B. Gal, T. Braude, U. Pumerantz, J. Cohen, Y. Belinkow, Y. Globerson, Y. P. Levy, and Y. Shoham. Jamba: Hybrid transformer-mant mamba language models. In The Thirteenth International Conference on Learning Representations (ICLR), 2025. URL -id B. Liu, T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference Learning Representations (ICLR), 2023. URL https: //oprrr///erreie f orum? ? (immmidddDDeejuueee
X. Ma, Chou, X. Kong, J. He, L. Gui, G. Neubig, J. May, and L. Zettlemoyer. MEGA: mov- ing average equipped gated attention. In The Eleventh International Conference on Learning Representations (ICLR), 2023. URL http::////peeeviiee
S. Margolis, J. Rhodes, and A. Schilling. Decidability of Krohn- Rhodes complexity for all finite semigroups and automata, 2024. BtLLhttps:// //arxi/ org/ att////s//222 18477
E. Martin and C. Cundy. Parallelizing Linear Recurrent Neural Nets Over Sequence Length. In Inter- national Conference on Learning Representations (ICLR), 2018. URL httpp:://operreee het/forummic Hii-iddHHHHUulc--C--
W. Merrill and A. Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 1 11:311555,, 2023.
W. Merrill, J. Petty, and A. Sabharwal. The illusion of state in state-space models. In International Conference on Machine Learning (ICML), 2024. URL httpp:://pperreview net/ www.:eneeffotfimmmm for QZgo9JZpLQ
12

---

D. A. Mix Barrington, K. Compton, H. Straubing, and D. Thérien. Regular languages in NCI. Journal of Computer and System Sciences, 44(3):478 499, 1992. ISSN 0022-0000. doi: https:// doi.org/ 00. 101 00000000000000000000000000000000 #tticcleppi/0002200002222
httpp:/w::// sciencedi com/ science/
A. Orvieto, S. L. Smith, A. Gu, A. Fernando, C. Gulcehre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning
(ICML). PMLR, 2023,
M. B. Paulus, C. J. Maddison, and A. Krause. Rao-Blackwellizing the straight-through gumbel- softmax gradient estimator. In International Conference Learning Representations (ICLR), May
2021. URL hwtp///ppeevvveeeeeeeee eviee..eeee....... net/ f forum? www.rrriduuieeee. M
B. Peng, R. Zhang, D. Goldstein, E. Alcaide, X. Du, Hou, J. Lin, J. Liu, J. Lu, W. Merrill, G. Song, K. Tan, S. Utpala, N. Wilce, J. S. Wind, T. Wu, D. Wuttke, and C. Zhou-Zheng. RWKV-7 "Goose" with Expressive Dynamic State Evolution. In Second Conference on I Language Modeling, 2025. L. Ren, Y. Liu, Y. Lu, C. Liang, W. Chen, et al. Samba: Simple hybrid state space models for efficient unlimited context language modeling. In The Thirteenth International Conference on Learning Representations (ICLR), 2025.
T. K. Rusch and D. Rus. Oscillatory state-space models. In The Thirteenth International Confer- wwwss//foommiiii
ence on Learning Representations (ICLR), 2025. URL http::: GRMfXcAAFh
Y. Sarrof, Y. Veitsman, and M. Hahn. The expressive capacity of state space models: A formal language perspective. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems (NeurIPS), 2024. URL URI.tttps:/ htt.t:ttt////eeemeete openrevieeeeeeeeeeeeeeeee net. ft
I. Schlag, K. Irie, and Schmidhuber. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning (ICML., pages 9355-9366. PMLR, 2021a.
I. Schlag, T. Munkhdalai, and J. Schmidhuber. Learning associative inference using fast weight memory. In International Conference h//ppenreveww.ne////eeeeeeeeeeee www.eeeneeeffoormreoo ? d=TuK6agbdt:27
Learning Representations (ICLR), 2021b. URL https
J. Schmidhuber. Learning to control fast-weight memories; An alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139 1992. doi: (166//ecoo.19224411.
J. Siems, T. Carstensen, A. Zela, F. Hutter, M. Pontil, and R. Grazzi. Deltaproduct: Improving state- sate--tacckig in linear RNNs via Householder products. In ICLR 2025 Workshop on Foundation Models in the Wild, 2025.
Smith and Zipser. Encoding sequential structure:
experience with the real-time recurrent learning algorithm. In International 1989 Joint Conference Neural Networks, pages 645-644 648 v. 1989. doi: 10. I 109//JCNN. 1989.1 18646.
J. T. H. Smith, A. Warrington, and S. W. Linderman. Simplified state space layers for sequence modeling. In The Eleventh International Conference on Learning Representations (ICLR), 2023. htttss:///// /tsttps://opppe //tp://vpeeeeieeeeeem
T. Soydan, N. Zubić, N. Messikommer, S. Mishra, and D. Scaramuzza. S7: Selective and simplified state space layers for sequence modeling. arXiv preprint arXiv:2410.0344 2024.
H. Straubing. Finite automata, formal logic, and circuit complexity. Birkhauser Verlag, CHE, 1994.
L. Strobl, W. Merrill, G. Weiss, Chiang, and Angluin. What formal languages can transformers express? survey. Transactions of the Association for Computational Linguisties, 12:543-561, 05 2024. ISSN 2307-387X. doi: 10. 162/tacl a 00663. URL httpsstss:///oo
10. 111.///a1..1//.c1111
a_ 00663
Y. Tay, M. Dehghani, S. Abnar, Y. Shen, D. Bahri, Pham, J. Rao, L. Yang. S. Ruder, and D. Metzler. Long range arena A benchmark for efficient transformers. In International Conference on Learn- ing Representations (ICLR), 2021. URL htttps:::: /
www./eeeooounnne wiw=iyeeewgweeeeee CrCk A. Terzić, M. Hersche, G. Camposampiero, T. Hofmann, A. Sebastian, and A. Rahimi. On the expressiveness and length generalization of selective state-space models on regular languages. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 20876-20884 2025.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention Is All You Need. In Advances in Neural Information Processing Systems (NewrIPS), volume 30, 2017. URL httph::ttt/ttttt p/ttteee//proeeedingg weepeeddiinnnnnuunnneeee www.riiiiii. ips. cc. htt wwwppppeeeeeepaappppppppeeeeeeee Paper. .ddf
R. Waleffe, W. Byeon, D. Riach, B. Norick, V. Korthikanti, T. Dao, A. Gu, A. Hatamizadeh, S. Singh, D. Narayanan, et al. An empirical study of mamba-based language models. arXiv preprint 27Xiv:2406.07887, 2024.
13

---

B. Walker, A. D. McLeod, T. Qin, Y. Cheng, H. Li, and T. Lyons. Log neural controlled differential equations: The lie brackets make a difference. International Conference on Machine Learning (ICML), 2024.
B. Walker, I.. Yang. N. M. Cirone, Salvi, and Lyons. Structured linear CDEs: Maximally expressive and parallel-in-time sequence models. arXiv preprint arXiv:2.005. 17761, 2025.
B. Wu, J. Shi, Y. Wu, N. Tang, and Y. Luo. Transxssm: A hybrid transformer state space model with unified rotary position embedding. arXiv preprint Stti:::506.09555
2025.
R. Xiong, Y. Yang. D. He, K. Zheng, S. Zheng, C. Xing, H. Zhang, Lan, L. Wang, and T.-Y. Liu. On layer normalization in the transformer architecture. In Proceedings of the 37th International Conference on Machine Learning (ICML), (CML'20. JMLR.org, 2020.
S. Yang. B. Wang. Y. Zhang, Y. Shen, and Y. Kim. Parallelizing linear transformers with the delta rule over sequence length. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024. URL http::s///peervveeet net/forunnIddyy@on4/tn
14

---

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) justificatinn right after your answer (even for NA).
The checklist answers an integral part of your paper submission. They are visible 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 While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd a proper justification is given (e.g., "error bars expensive" or 'ee were unable to find the license for the dataset we used"). In general, answering binary way, we
the checklist one of the factors in their evaluation.
reported because it would be too computationally
"[No] " or "[NA] is not grounds for rejection. While the questions are phrased eeknowledge that the true answer often more nuanced, so please just use your best, judgment and write justification 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: The paper experimentally and theoretically validates all claims made in the abstract and the introduction.
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 in 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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
15

---

Justification: The paper clearly states that the proposed method is a trade-off between efficiency and expressiveness. We also clearly show that the method does match the accuracy of I.TI systems in image processing. Furthermore, the runtime is discussed in detail under various settings in Appendix F.
Guidelines:
The answer NA means that the paper has 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 approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of 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 fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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: The paper does provide several theoretical results, the assumptions and full proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does 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 be properly referenced.
4. Experimental result reproducibility
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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
16

---

Justification: All of the hyperparameters for reproducing our results are reported in the appendix or the provided codebase. Moreover, we provide the code for reproducing the main experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) 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 describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., 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]
Justification: We provide github repository with summary of the paper and instructions on reproducing the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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 for more details.
/nips.cc/ppull http:cccpppbcccctcttect.c ottpa/ddee/odeeabaaasssoooooooo
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.
17

---

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.
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: The paper provides the code and data needed to reproduce all of our results, from which the required details are evident. Details on the experimental setup, data splits and hyperparameters are also provided in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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: We repeated all benchmarks with multiple seeds and have reported mean and standard deviation for most results. certain experiments we only report the best- performing seed following standard practice on similar studies.
Guidelines:
The answer NA means that the paper does 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 to 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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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?
18

---

Answer: [Yes]
We report the main specification of the system used to train the models as well as the approximate compute time needed to reproduce representative experiments in Appendix D.2.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The research conducted fully conforms to the NeurlPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., .., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper introduces new neural network model and analyses its behavior on datasets with no immediate societal impacts. Certainly, more expressive and efficient models can have significant societal impacts down the line, we do not see any direct and immediate negative impacts of this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
19

---

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 MI.).
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 (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses immediate risk of misuse.
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 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.
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.
Licenses for existing assets
Question: Are the creators or 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?
Answer: [Yes]
Justification: For each existing asset, the original source is cited and the license terms respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if 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 (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com datasets 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 s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper releases new assets which are described in detail the paper as well the associated code.
Guidelines:
20

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 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 as details about compensation (if any)?
Answer: [NA]
Justification:
The research did not involve crowdsourcing nor human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or 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: The research did not involve crowdsourcing nor 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used in any important, original or non non-standard way during the research.
Guidelines:
21

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non-standard components.
Please refer to our LLM policy (https://neurips /ttp://pp//cc//offfeeeee//////// for what should or should not be described.
22

---

A Background
The goal of this section is to provide knowledge of abstract algebra and circuit complexity theory at level sufficient to understand the motivation behind our paper. While the presentation is fully precise, we do omit certain details for clarity, and we often focus on providing an intuitive understanding by considering visual and textual explanations and examples for important concepts. This approach is highly inspired by Carter (2009). As the core of our work is the design and analysis of novel neural network architecture, one does not need to have deep understanding of these topics to understand our paper. As such, the entire Appendix A can be skipped without significantly affecting the understanding of our PD method. For a deeper treatment of the topics, one may consult the following resources: (Straubing] 1994] Carter 2009; Arora and Barak 2009).
We start by motivating the connection between abstract algebra and FSAs in A.I We then explain the central algebraic concepts in A.2 starting with the definition of a group and finishing with step-by- step reasoning about why certain group is solvable. A. introduce the main relevant concepts and classes from circuit complexity theory. We finish in A.4 by examining the most important results on the expressivity of SSMs that combine the two presented frameworks.
A.1 Algebra and Finite-State Automata
Algebra is, broadly speaking, the study of sets and binary operations on elements of sets. The set elements can be of various nature. An intuitive example of an algebraic structure is the set of integers under addition, often denoted as Z+ In more generality, one may consider sets of functions with the binary operation being function composition. This is in fact highly related to the study of finite- state functioonn automata (FSAs), where we consider sets of transition functions corresponding to the input elements,
and we study the effect of composing transition functions. This described set is defined for any automaton A = (Q, Σ, 8) as
T(A) (8(--11....7) T N, Vi [T) E }}}
where 5(,, ()....)) Q + Q is the transition function obtained by composing the transition functions of each input in the sequence, namely, 01....... 5(6(....8( o1)........ or..),
This set contains all of the transition functions that can expressed by the given automaton. The limitations of SSMs on FSA emulation stem from the discrepancy between T (AA) and the transition functions that SSMs with different transition matrix structures can express. motivating illustrative example is given in Figure [SI] in which we consider the As automaton and time-variant SSM with diagonal transition matrices and Vt b(u)) = O. Please note that this figure only serves to illuminate the connection between FSAs with algebraic structure and SSMs, with precise bounds being presented later.
Z1
A
0
0
0
0
0
0
0
0
ZI
0
0
0
0
0
1
0 0 0
A E
Wi 2 CJ
1
0
0
0
1 0
0
0
AN_
Figure S1: Left: A visualization of the As automaton Center: The two transitions of A5 equivalently represented in matrix form. T(A) is isomorphic to the set of all possible unique iterated products of the two matrices, of which there are total of 60. Right: A simplified diagonal SSM that omits the B(u)) term. As the transition matrices are restricted to be diagonal, and since the transition matrices represented in the center are not simultaneously diagonalizable, there seems to exist a discrepancy between ((A)) and the SSM.
used it in experiments (Carter 2009).
The reasoning in the figure above is only valid for a single SSM layer with no B(u ),, term. In order reason about several layers of the full model, recent work Merrill al. (2024); Sarrof al. (0024) have utilized the frameworks of Abstract Algebra (A.2) and Circuil Complexity Theory (A.3).
A.2 Algebraic Groups and their Properties
We will now define algebraic objects that are of interest to us. We start with groups.
23

---

Definition 2 (Algebraic Group), An algebraic group is set G equipped with a binary operation that
-c= 1. Associative: (a-b)-c=a a (b. c) for all a, 1,, G.
2. Has neutral element G such that a ee.. for all E G,
3. And where every element has an inverse: for each E G, there exists a aa
1 E G such that
Algebraic groups can be graphically represented using Cayley diagrams. Starting from the neutral element, Cayley diagram visualizes the structure of the group by applying the group operation in conjunction with a group element the current element. This can be easily understood by considering the group of integers under addition modulo (2.4) in the figure on the right. We draw the Cayley diagram by first drawing the neutral element, O. Starting from 0, all other elements are generated by iteratively applying +1 on current element. For
+1
some groups, in order generate all elements of the set, we need consider more than one generating element. An example is the As group. While Figure ST refers to it as automaton, the figure is equivalently the Cayley diagram of A5 with the two selected generating permutations.
central property of groups is the commutativily of the binary operation. The binary operation of a group is commutative only if Va, 6 G b b.c....
Z2 x ZA
Da
Figure S2: Cayley diagrams of the group Zg x 44 and the dihedral group D4 (Carter 2009). Z2 x Z4 commutative group, while D4 is not. Both solvable, with solvability of Zn x Σ4 shown in Example
Solvability
Another central property groups is solvability. We will first present it informally and will then precisely define it. Loosely speaking, group is solvable if it can be constructed from co- mmutative groups The details of the construction are par- ticularly easy to understand on the example of the Ze x Z4 group, shown in Figure SS The Z2 Z. group is solvable, as it corresponds to the direct product of two commuta- tive groups. While the D4 group shown previously is not commutative, it is solvable as it can be constructed from commutative groups in a similar manner as Σ, Σ4- However, As cannot be constructed using commutative groups Carter (2009). To speak about solvability more definite terms, we need to define several concepts. The re- mainder of this subsection defines and explains solvability in concrete terms. It can be freely skipped without any effect on reading the rest of the appendix. Firstly, we will define subgroups, which are in essence closed subsets of group.
Ze x Z4
Z
Zz
=OOX
X
Figure S3: Composition of شの Zz.
Definition 3 (Subgroup). Let be a group. A subset C is called subgroup if H itself group under the operation inherited from G. That is, H is subgroup if:
1. H, where is the identity element of G,
2. For all a, b E H. the product a bis in H,
3. For all E H, the inverse -1 in H.
Of central interest are normal subgroups, which a particularly well-behaved category of subgroup. We will normal subgroups them to partition group into sequence of subgroups. The solvability of a group can be determined by examining the structure of sequence of normal subgroups.

---

Definition 4 (Normal Subgroup). A normal subgroup N of a group G. written N < G, is a subgroup invariant under conjugation by elements of G. i.e. for each n E N, holds that gng -1 n for all g E G.
In particular, the sequence of group partitions we want to examine is the group's normal series. Definition (Normal Series). normal series of a group is a finite sequence of subgroups
{e} Go a G1 a... 4 G, = =G,
such that each subgroup G3 is normal the next one, i.e,, G, 1 for all i, and the series terminates in the trivial group {e}-
Apart from subgroups, we need to define cosets, as they are a central concept when analyzing how groups decompose. A coset is subset of the group formed by subgroup, but in contrast subgroup, it is not necessarily closed under the group operation.
Definition 6 (Coset). Let G be a group and H a subgroup of G. For any element g E G, the left coset of H in G with respect to g is the set
gH = ( H).
Similarly, the right coset is
Hg = (bg: / h H}.
Cosets partition the group G into disjoint subsets of equal size.
Consider, for example, the partition of the integers into even and odd. As the following example shows, the even numbers are a normal subgroup, the odd numbers are a coset, and together they form all integers.
Example 1. The integers under addition form group which write as Zt. The even integers, written as 22.", form a subgroup of Z=,, as the sum of two even numbers is again even and the neutral element, is even. In particular, this is normal subgroup, an easily verifiable immediate consequence of the commutativity of addition.
The odd integers are coset of Zz constructed from 2z by adding I each even number. That is, the odd integers form the set 1 + 2z+ This is not a subgroup. as it does not contain the neutral element. The sets are disjoint, are of equal size by 1-to-l mapping of the elements, and together they form Z.
It is precisely the decomposition group by use of a normal subgroup that we are interested in. This procedure creates a new group structure called a factor group, which describes the relation between a group and its normal subgroup.
Definition (Factor Group). Let N be a normal subgroup of a group G. A factor group (or quotient group) G/N is the set of left cosets of N in G, concretely (G/N = [gN E G}. equipped with natural group operation.
Let us again consider the even and odd integers. We have seen that this is the full set of cosets of = we abstract away the individual numbers and only consider the concepts of even and odd, we can see that the two concepts form group structure.
Example 2. Consider the set (Even, Odd} with the binary operation defined as per Figure S4 figure is in fact the Cayley diagram of 2 /2.
This
A solvable group is one in which group being commutative. The sequence should also end with the trivial group containing only the neutral element.
create sequence of such factor groups with each factor
Definition 8 (Solvable Group). A finite group G is solvable if there exists a finite sequence of subgroups
( 4G1 4... GG.
such that each G3 is a normal subgroup of G441 and each eachfactor group Git1 /G commutative. Equivalently, G has normal series whose successive quotients are commutative groups.
25

---

odd
number
even
even number
Even
Odd
number
odd
number
Figure S4: The Even and Odd cosets of Z themselves form group under addition, in particular the factor group Z/2Z. The even numbers act the neutral element, addition associative, and the integers are closed under addition.
Figure S5: The Un x E4 group Cayley diagram.
We will understand these concepts better if we use them, for example, to argue about why Z₂ x 2, is a solvable group.
Example 3. Consider the group G B2 E4. We can understand the group by considering its Cayley diagram visualized Figure 55
We can identify the elements G Zn x Z, using two integers (a, b). We define the group operation as |a + mod 2, b + mod 4). If we choose the upper-most element to be the neutral element [0, 0], and generate the rest of the group using +[0, 1] and +[1, 0), we obtain the Cayley diagram shown below.
[a, b] + [c,
[0.0]
[1.0]
[0.3]
[1.3]
[1,11
[0.1]
[1.2]
[0.2]
Figure S6: The Zo x ZA group Cayley diagram, labeled by integer tuples.
We can first notice that the outer ring in the diagram forms subgroup. Adding any two elements on this ring produces an element on that same ring, and the neutral element [0, is part of it. This group is isomorphic to the integers under addition modulo 4, written Z4- The outer ring is in fact a normal subgroup of Zz x Z4. When the group operation is commutative, as it is in this case, conjugation is trivial operation and each subgroup is normal. Concretely, if we commutativity .g -1 'n = n trivially in the definition of a normal subgroup (Definition 4), we see that gng -g--
holds.
The outer ring forms a normal subgroup isomorphic Za, and we know that we can use a normal subgroup to construct factor group per Definition We have seen this in Example 2 when
26

---

we created a factor group dividing all integers using the even ones. In this case of partitioning
G Lg x Za using Σn we obtain the same factor group as we did in Example 2. To this end, we
will generate the coset [1,0] + [0, Fa), which contains all elements of the inner ring in Figure [S6] It not a subgroup, as does not contain the neutral element. We can easily verify that the two cosets of Zn x Big Sollow the behavior shown in Figure S7
switch ring
move ring
move on ring
ring
ring
switch ring
Figure S7: The factor group obtained by dividing Z, x Z, by the outer ring normal subgroup.
Abstracting away the details, this is conceptually the same figure as the one we have seen previously when dividing & by 2Z. The factor group is therefore 2/22.. We have now constructed the first part of the normal series, Z, 4 Zz Z1. and we know that the factor group Zn x Z, Z 2 is commutative because its group operation is isomorphic to integer addition modulo 2.
We can now perform similar exercise to derive that Z2 Zis and that Zis / is commutative group. However, we spare ourselves the effort by first noting that {e} a Z4 and that Za/ [e} is commutative. Firstly, the trivial group is a normal subgroup of any group. Secondly, Za/ Za/fe} is commutative because Zg is commutative and for each group G, G/(c) = =G. Both of these properties can be verified using the tools we introduced above. With this, we complete the chain of normal subgroups with commutative factor groups, showing the solvability of Ze x Z4 by
{e) 4 Z4 4Z2 Z4
The entire exercise could of course have been skipped by directly noting that Bg x EA is commutative. In this case, trivially stating {e} < 4222 En suffices.
We are now equipped with basic understanding of what a solvable group is. To better understand the implications of this concept for state state-tracking with SSMs, we need to introduce a different, yet perhaps surprisingly related framework (Straubing 1994). that of Boolean circuit complexity.
A.3 Circuit Complexity Theory
The theory of circuit complexity aims to provide an abstract understanding of highly parallel al- gorithms. One might imagine that there exist problems for which it is difficult, if not impossible, to design one efficient algorithm which operates on arbitrary-length inputs, yet in which all input lengths admit a bespoke, highly efficient and parallel algorithm" 3l Such considerations are especially important in cryptography, an efficient algorithm for the factorization of n-bit integers would be a significant development for any large n. Boolean circuit complexity is the study of such parallel algorithms,, or rather circuit families. Let first define Boolean circuit.
Definition 9 (Boolean Circuit). Boolean circuit is a directed acyclic graph where internal nodes logic gates (typically AND, OR, and NOT), leaves input variables or constants (0 or 1), and there is a single designated output node, The circuit computes a Boolean function by propagating values from the inputs through the gates to the output.
A Boolean circuit family is simply the collection of problem-specific Boolean circuits, with one circuit being defined per imput length.
Definition 10 (Boolean Circuit Family). A Boolean circuit family is sequence of Boolean circuits (Cn hnen, where each circuit C, has n input variables and produces a single output bit.
We will now present the two classes of circuits directly relevant to our work.
Definition 11 (TC Circuit Complexity Classes). The class TC consists of languages decidable by families of Boolean circuits of polynomial size (pooy((n)) and depth O(log' n),, with unbounded fan-in AND, OR, NOT, and mujority (threshold) gates.
As per (Arora and Barak 2009), introductory remark to Chapter 6, Karp and Lipton propose variant of this
idea in 1982.
27

---

TC" consists of shallow (constant-depp but arbitrary fan-in Boolean circuits of standard elements (AND, OR, NOT) augmented with a majority gate, Emulating solvable automata is proven to be within TO (aarrf et al. 2024).
Definition 12 (NC* Circuit Complexity Class), The class NC¹ consists of languages decidable by familles of Boolean circuits of polynomial size (ppoly(n)) and depth (llo n)), with AND, OR, and NOT gates of fan-in 2.
NC² allows for logarithmic depth, but restricts the fan-in of the gates to 2. Emulating solvable automata is proven to be an NNC comppleee problem Barrington (189)) meaning that all NC problems be reduced it.
Many relations between circuit complexity classes remain unknown. It is, for example, not known whether TC" * NC It is in fact not even known whether TC is equal to P. the class of problems decidable in polynomial time (Arora and Barak 2009). As a consequence, certain restrictions have been placed on the generation of Boolean circuits in order to allow for a more realistic and fine-grained study of their properties. The central restriction is that of uniform generation, or uniformity.
Definition 13 (Uniform Boolean Circuits). A family of Boolean circuits {C, } IEE is uniform there exists a deterministic Turing machine that, given 1", outputs a description of Cn in time bounded by some resource (e.g., logarithmic space or logarithmic time). Of particular interest us is log-space uniformity, in which the Turing machine operates using O(log n) space for inpul length n.
Turing machine generates length-spocific Boolean circuit
Input
Work
Output
A
Figure S8: A visualization of a uniformly generated circuit family, with the specific example being the XOR circuit for inputs of length 2. On the left signifying that the circuit should be generated for inputs of length 2. Either the size of the work tape or the number of computational steps is upper bounded tape contains the description of the circuit visualized on the right. This is in fact a log-space uniform circuit family, symbolized by the short work tape. The XOR circuit is highly related to the parity automaton, as it outputs 1 if and only if the number of ones in the input is odd.
Turing machine whose input is 11,
function of the input length. The output
A.4 SSM Expressivity Results
We finally arrive the results that this section was building up to, bounds on the expressivity of SSMs within the framework of algebraic groups and Boolean circuits. We do not prove any new theorems here nor restate the proofs, opting instead to refer to work which proves the claims. Let us start by restating classic result in the terminology that we introduced in our paper:
Theorem 1 (Barrington] (1989). Theorem 5). The word problem for any nonsolvable group is complete for NC under AC" reductions.
The word problem of a group is defined as follows Merrill et al. 2024y:
Definition 14 (Group Word Problem). Let (M,-) be a finite group. The word problem of M is defined as evaluating the product of arbitrary sequences of elements of M. That is, given a sequence mom1 "k solving the word problem involves returning m E M such that mo mm m. m.
The separation of word problems over solvable and non-solvable groups rests on the widely-held conjecture that TC * NC Arora and Barak 2009) combined with the result that word problems of solvable groups belong to TC";
Theorem Mix Barrington et al. 1992). ) Theorem 8). The word problem for any solvable group in TC.
28

---

A recent work analyses the expressivity of diagonal SSMs by demonstrating that the individual computations in the SSM can emulated by bogspace-uniform TC circuits, under the assumption that the numerical representation capacity is logarithmic in the sequence length. Concretely, it is O(logn) n).
Theorem 3 (Merrill et al. 2024), Theorem 4.4). Every fixed depth log-precision diagonal SSM can be emulated by logspace-unjoons TC circuit.
This is the main upper bound we refer to in the paper, and is what we mean when we say that non-solvable automata cannot be emulated by diagonal SSMs, which is implied by combining the strict inclusion logspace-unifomn TC C TC with the conjectured TC n NC _ * 0, and utilizing Theorem 3 This bound rests on an unproven conjecture, but it is supported by significant experimental
evidence Merrill et (002)) Cirone et (2024): Grazzi al. (2024); Sarrof et (2024): Terzić
al. 2025
B
Architectural Details
B.1 Full Architecture
This work mainly describes a new method for generating the SSM transition matrices. The method itself embedded into larger architecture, which mostly follows standard practice in neural network design as pioneered by the Transformer (Vaswani et al. 2017). That is, we embed the PD parametrization into neural network layers which consist of nonlinear feed-forward networks, vector normalization, and residual connections, calling the entire model PD-SSM. The connection pattern of PD-SSM closely follows that of pre- or post-norm Transformers, and can be seen in (Xiong et al.) 2020).
We show two sketches of the full PD-SSM model in Figure [S9
Readout The readout from the state, (0 different from standard practice, which typically implements it as vp(x;)) (x:) (Orvieto et al. 2023 Gu et al. [2022b] Gu and Dao 2023 Smith al. 2023). Instead of taking the real part of 24, we apply a transformation on the concatenation of the real and imaginary part of z,, denoted as Ref2, H (2x2), Depending on the benchmark, the readout is either a GELU-activated nonlinear network:
((x.)= Read, &Getu! (GGetaWWRee (WRodd,1 (Re [m [m()) + Read, Read,O
Or, if we refer to it as linear readout, we concretely mean the transformation:
(xx)) W Read (Re [mm)())) + &
For the long-range arena tasks, we employ the nonlinear readout and a deeper architecture. For the state tracking tasks, we apply the linear readout and single-layer architecture. See Appendix
B.2 Efficiently Computing the Parallel Scan Gradients
dL
The total derivative of loss L with respect to Zs. written dag
satisfies the equation below:
dL aL + 00s+1
dL
dxs+1
dr
Oa
Oxg
dL explains the total effect of æy on via all of the intermediate computations,
In our notation,
dxş
0L denotes the direct effect of øy on L, ignoring the influence of x& on the rest of the dzy
whereas
sequence.
The expression above is equivalent to:
dL
AL
dL
Ak+1
dx
drs
dr
*Using tools from rough path theory. (Cirone et al, 2024) prove the restrictiveness of diagonal time-variant SSMs compared dense without relying unproven circuit complexity conjectures.
29

---

PD-SSM Block
PD-SSM Block
$ x
LayerNorm
x
LayerNorm
Readout
GeLU MLP
LayerNorm
Concatenate imag. elements of the state
Readout
3, Re(az))) gay book
Re( De
LTV System
LTV System
Bu, C
A Bug C.
A..... NsN
Bug Bug & c
A @ HANN
Bug Bug C
Matrix Generator (Fig 1)
Linear
PD Matris Generator (Fig 1)
Linear
Wh.... R
MI..... R
(a) Full PD-SSM model with linear readout, as used in the state-tracking experiments.
(b) Full PD-SSM model with nonlinear readout, used in the LRA and time-series experiments.
Figure S9: Full PD-SSM models we used in our state-tracking and LRA experiments. In the time- series classification experiments, used model equivalent the shown in subfigure S9b with the exception that en Refxx R.N.
can see that computing the derivative of with respect to states Fy is a linear recurrence with sparse transition matrices Ak+1. Computing the gradient thus reduces to reverse parallel scan with matrix multiplication complexity of O(N). Within the framework the parallel scan introduced in Section 2.4, gradient computation then be parallelized using the following associative operation:
dL dr
A; + dL ) (A:Aiti, dr.
dL
dL dr
(Ai,
(Ait1, dx;
C Proofs
We first restate and prove the two properties of the space column one-hot hot matrices, NxN
Property 1 (Algebraic Structure of One-hot Column Matrices). NxN is monoid under matrix multiplication, ie., is closed under associative matrix multiplication and contains the identity.
Proof. It is easy to verify that NxN contains the identity, as is column one-hot matrix. It is also trivial verify that the product of two column one-hot matrices remains column one-hot. Given A, B E N the columns of B select and scale the columns of A. More precisely, the entry in row i, column j of the product matrix C AB given by:
C₁
A Bks
30

---

Since for each fixed j. the matrix B has exactly one non-zero entry in column j, say at row & = r, all other terms in the sum are zero. That is.
Bkj for all rr, and Brj 0
So the sum reduces to single term:
Cipy = Air Brj
Now, since matrix A also has exactly non-zero entry in each column, the r-th column of A has only one non-zero value, say at row 8. Therefore,
Air 0 for all + 8, and Asr +
This implies that for each column j of the product C, there is exactly one row such that Cij + 0. and all other entries in that column are zero.
Property 2 (Computational Efficiency of Matrix Multiplication in HNNN), Let A, B HNN Then C AB NNN can be computed in ((N) arithmetic operations.
Proof. As per the previous proof, in order to compute C = AB for A, B E HNN we only need compute element in each column of C. Figure 3 in the main text outlines the details of the computation.
The following proof is an application of a chain of inequalities that shows that under certain assump- tions, which are fulfilled by the PD-parametrization, the SSM is BIBO-stable.
Proposition 1 (System Stability under PD- (D-Parametrization) Let E E (0, 1] and consider the state
transition Iy- = AA + by with A₁ E NNN,, ||A S E. Let further |xoll2 S B and [ S for B < co. Then holds that
| VNB/E Vk.
(3)
Proof. Expanding the recursion of the state transition results
II j=
Aj) 2o +
A2)
t=1
j=k
where we define
II
Aj whenever i > k, with denoting the identity matrix.
j=k
We bound the norm of the state as follows:
++1 br
||0/||2 = |1 II
Az) 200 + _
(4)
j=k
f=
2+1
II( II[I A
zol2 + Σ
Ay)b, l12
(5)
j=k
j=
4+1 II
II f=b
Ag1l[|z0|12
Σ
(6)
f=k
< B(I II j=k
A +
Σ [=1
II 1D
where the first inequality is the result the triangle inequality, the second inequality results from the definition of the matrix spectral norm in both terms (specifically, denoting the spectral norm of square matrix as || it holds that for vector b, Ab|l| S ||A[[||||a and the triangle inequality
in the second term, and the final incquality is due to the assumptions on the norms of zo and 6,-
31

---

To bound the spectral norms of the two products of the form I[ Aj. we will use the fact that for
general complex-valuee matrices A. it holds that ||A||| _ ||||[ We will additionally leverage the
algebraic structure of PD matrices, i.e., the fact that [[}= Aj, k has column one-hot structure, which enables these results to derive the following upper bound:
the trivial bound IT j= Ajll= VN VNI IT
Ayl1oo We will combine
II j=k
A I II
All S SVNI
II Ayllo -)((-e)
j=b
We will prove this by induction, assuming that the follwing formula holds for a fixed and arbitrary k 2
Ayllo S 5 -1)-))-itt
(8)
The base case & holds as a direct consequence of the assumption's proposition:
I ==
A,llx |AAllo S (1 e)
Suppose now that Equation 8 holds for some k > i. Then, for + 1,
II A,1x || II A,llo 11 jmA++11
II Ayl jmn
jmb
where we decomposed A&+1 into the column one-hot matrix Pk+1 and the complex diagonal matrix DR=II By the proposition's assumption, [|Dx+1 S 1 6. By the induction's assumption,
IIIT Aglloo & (1 c) Since DR+1 is diagonal, [[ Iīi= Aslloo S (1 c)²-
Finally, Pk+1 only rearranges the entries of D4+1 IT Aj, so that, as desired,
11 II ANllo = | j=k+1
II
Ayllo = || Dx+1 II j=k
Ayllo S (1 ()+))(++1)-5+))
j-k
We obtain the final result by plugging these bounds into Equation
7 i.e., we have, with k 2 1:
1+1
|aull2 S B(I II A+ll
A,
j=k
j=k
1+1
< B(VN
A
N
t=1
j=k
< BVN
(1 c) Σ
(1
k-
1=1
BVN
(1 Σ
1 )r)
1=1
|
BVN (1 () -1
1 BVN
B
*
+
<
The following lemma will be of use for proving the optimality of PD parametrization.
32

---

Lemma 1. Any single-layer complex SSM with state size d can be reduced to single-layer real SSM with state size 2d.
Proof. Let Lt, by E Cd and A, E Cdxd with F++1 Λ + be. Write x; = =R(xz), x = I(xs).
by = =((b)), bj = I(b)). A = RR(a)) and A = I(A)). Then
1 + itt+1 = Zt+1 = ArT; + 6, = (A + (2) + ix() + by + ib;
=,,x - Aja + by + i + A5a + b))-
In block matrix form, the complex SSM can be represented as a real SSM through
4+1
Ap
++1
A
The following proposition states that for cach N E N, one can construct FSA which requires state dimensionality of at least N - 1 to emulate using an SSM, under the assumption that each automaton state has unique vector encoding. By combining this with Proposition 2, which states that all State automata can be emulated using a PD-SSM with one layer and state size N, the optimality of the PD decomposition for emulating FSAs is established.
Proposition 3 (Optimality of PD Parametrization). For any N there exists a sittt--saate automaton with N states that cannot be emulated by any single-layer SSM with state size less than N under unique state encodings.
Proof. Interpreting complex state size as 2d and real state size as d for x E Rd and x E Cd. respectively, we can invoke Lemma [ and stick real SSMs in the remainder of this proof. Let N E N. For N < 2 the statement is trivial, so suppose N 2 3. Consider the FSA A with states $1..... 8N and input vocabulary equal to the set of states mapping to state transitions
88+1 mod N
Sz + fa where fa(s;)
115
8;
+ x.
Now, assume by contradiction unique (one-to-one) encoding 8; _ 0j R with d S N - 2. Then there exist two states S2, Sy. w.l.o.g. set SN such that
N- Σ
N-2
= span span(ui,..... = span (11 uN 2 and UN-1 =
0,4 as well as uN Σ
3
1=1
Now, single-layer SSM that emulates A must satisfy
i ==
Ac + be
U141 mod N
An immediate consequence is that ii=1 # 1 EN' Br, since otherwise either
UN AN- bN- -'²
0z 1AN + bb + bN- (1 DI''2 o;)) = UN--
or
Ui ANUN + +b = D'' (A + bN) + bn - NN=22 Bi) UN +
violating the uniqueness assumption. But then
V ssan UN UN 2- UN
since EN= - = u uN N a.) * 0. We can now leverage this spanning
-
property by noting that AN - UN-1) (v. VN- Vi {I.... N - 2} and thus An lv dly. But if An acts as identity on 3 uN. then 11 = AN + by = i1 + by and hence bn = 0. But then reach the contradiction violating uniqueness of state encodings
01 = ANuN + by = ANlyen + +by LVuN + by = UN-
33

---

The following proposition is meant to highlight the importance of assuming restricted readout, such done in Proposition 3 with unique state encodings. Indeed, by using lookup tables that are exponentially large in the maximum sequence length, even scalar SSM can emulate any finite state automaton. In practice, however, such lookup tables are entirely impractical.
Proposition (Arbitrary Precision and Readout). Consider z(+1 It + where = u k2 with U E Q input encodings and k, = /Pt E R/ R/Q time encodings, where is the t-th prime. Then, any FSA can be encoded into this scalar-valued SSM under an appropriate lookup table as readout.
Proof. According to Jaffe 2007). h; is linearly independent over Q, i.e. for u, E Q holds that 0. Therefore, no two differing input sequences U1...., Un and Ui..... Um will result in the same state representation It = Zo + E: u,ki Now, simple identification of every FSA state with all the state representations Ie of associated input sequences that lead to said FSA state shows universal expressivity under arbitrary readout.
wiki + + hin =
u1
D Experimental Setup
D.1 Hyperparameter Selection
FSA Emulation On FSA emulation, Table 2 we did not perform hyperparameter grid search. We re-used the fixed hyperparameters which were used to evaluate all of the baseline methods, as per Walker et al. 2025). contrast to the baseline methods which were evaluated using various state sizes including 128, only evaluated our model using only state size 1 128. We used Adam with the default parameters (0.9, 0.999).
On experiments with non-solvable groups in Table 3 {le-4,5e 56-4, le -,-3, 5e-3, 1e-2], and report the best validation accuracy over any the 3 random seeds and hyperparameter configurations. The state size was 128. We used Adam with the default parameters (0.9, 0.999).
ran learning rate grid search in
Time-Series Classification We performed the following grid search, following Rusch and Rus (202);: Learning rate in {1e-5, le-4, 1e-3). number of layers in {2, 4, 6). state dimension in [16, 64, 128) and embedding dimension (16, 64, 128]. We used Adam with the default parameters (0.9, 0.999).
Long-Range Arena We performed grid search defined by combinations of the following values: Learning rate in (1e-5, 5c-5, 1e-4, 5e-4, 1e-3), weight decay in {0.001, 0.01, 0.1, 0.05]. and dropout in {0.0, 0.1, 0.33. On each task, we report the average accuracy over three random seeds. The embedding dimension and state size were both fixed to 128, with the exception of the Retrieval dataset which we reduced it to 64. We used Adam with the default parameters (0.9, 0.999). The hyperparameters of the models compare with were obtained via extensive Bayesian hyperparameter search, as outlined in Soydan et al. (2024).
Natural Language State Tracking The setup of this task is equivalent to symbolic state tracking, only we train for 100,000 steps or until convergence on a validation set with length 40. We only ran grid search over learning rates in {le 4, 5e le 3]. State size was fixed to 128, and the number of dictionary matrices (K) was 6.
D.2 Training Times
We report the training time for representative benchmarks using NVIDIA A100 40GB GPUS.
Natural Language State Tracking This benchmark uses an inefficient Torch implementation of the PD-SSM. resulting in extended training times. The experiment can be executed significantly more efficiently using the provided JAX implementation.
On the Parity automaton:
PD 7.2 hours
Complex diagonal: 70.3 hours
34

---

Real diagonal: 68.6 hours
On the As automaton:
PD 82.8 hours
Complex diagonal: 68.4 hours
Real diagonal: 63.6 hours
Long-Range Arena
CIFAR: 2.5 hours
ListOps: 9.3 hours
IMDB: 6.6 hours
AAN: 34 hours
UEA Time-Series All results can be obtained within several hours on the specified GPU.
E
Additional Results
E.1 Runtime Measurements
Measurement Details The runtime measurements were obtained using optimized and compiled JAX c We did not implement custom system-aware methods, which can certainly make difference in practice (Gu and Dao 2023 Dao 2024). We assume that our runtime measurement setup is reflective of most researchers' typical use cases, and should provide an equal testbed for all the methods. All of the runtime measurements were obtained on an NVIDIA A100 80GB GPU, The code is implemented in JAX, version 0.4.24. The parallel scan relies on the jax. lax associative iesoocaatvv__sst associative_scan primitive. The computation is parallelized across the batch dimension and sequence length using jax. vmap. and is finally just-in- time compiled. At the time of writing, the parallel scan primitive is work-in-progress PyTorch our experience, the JAX version was significantly more efficient.
State Representation Size Matched Comparison We extend the comparison of our PD model with two representative methods, Lime-varian SSM with unstructured but column-normalized transition matrices (SD-SSM) Terzić et al. (2025 and a time-variant SSM with diagonal transition matrices generated using our MLP generation A u D(u).. Below, extend the results from Figure 4 by considering sequence lengths 256 and 512. Concretely, the dimension of SD-SSM again set twice that of the other models account for the discrepancy between the real and complex-valued state representations. The results are shown in Figure ($10
From Figure 4 at sequence length 64 and embedding dimension 5632, the SD-SSM exhibits an around 71 x slowdown compared to PD-SSM. The PD-SSM in turn around slower than the diagonal model.
At hidden dimension D 2048, the relative speed-up of PD-SSM over SD-SSM is 18.8x for L = 64, 28.3x for L = 256, and 30.3x for L = 512, an increasing trend in L.
State Size Matched Comparison Previously. the unstructured SSM had double the state dimen- sionality of the other two models to account for the discrepancy between the real and complex-valued state representations. We now set the state dimensionalities all models to be equal and again evaluate the scaling function of embedding size under sequence lengths 64 and 256. The results are shown Figure STT
Columm normalization crucial step ensure system stability when using unstructured transition matrices. has been implemented by dividing matrix elements by L" (quasi- Jnorm corresponding column (Fan et al. 2024 Terzić et al, 2025). As a consequence of the Gershgorin disc theorem and basic inequalities, a matrix with L' normallzzed columns is guaranteed to have spectral radius less than whenever p < L.
35

---

10a
Sparse PD-SSM
Sparse PD 2D-S5M
Diagonal
Diagonal
Time (mss
101
Time
10P
10
10"
256
512
1024
2048 2816
256
512
1024
2048
Hidden Dimension
Hidden Dimension
(a) Sequence Length 256
(h) Sequence Length 512
Figure $10: Runtimes with state dimension of SD-SSM set to twice that of other models.
Dense SD-S3M
Derse SD-SSM
Sparse
10"
Sperse
10a
Diagonal SSM
Diagonal SSM
Time [ms)]
[mo]
101
10a
10a
10-1
10a
2048
4096
5632
(a) Sequence Length 64
(b) Sequence Length 256
Figure S11: Runtime measurements with equal state size.
At sequence length 64 and embedding dimension 5632, the SD-SSM exhibits 16.6x slowdown compared to PD-SSM. The PD-SSM is in turn 7.6x slower than the diagonal model, a similar ratio as in the state matched setup above but now with double the state size.
At hidden dimension D 2048, the relative speed-up of PD-SSM over SD-SSM 6.8x for 64, 8.8x for = 256, and 9.7x for L = 512 (not shown). Again, an increasing trend with L.
Parameter Matched Comparison Given state size N, embedding dimension D and K transition matrices in the dictionary where applicable, the models have the following total parameter cost: N(2D+ NNN N)++ K D for SD-SSM, ((66+22N KN KNN +4)+ K for PD-SSM, and N(6D+2N +4) for the diagonal SSM. Let us denote the state size of SD-SSM as N, and that of PD-SSM as N Suppose further that D N, and K = 6, as used in our measurements. To equalize the parameter cost of PD-SSM with SD-SSM, N₂ must be set as:
- (6N, + 4) + (GN, + 4)2 + 192N
N₂
12
With this, given for example N, = D 2048, the corresponding N, is 1552. The corresponding relationship for the state dimensionality of the diagonal model Na given = N, and K
- -6NN, + +4) V(N,, + 4)2 + 64N2 + 48N,
N₂
which for N, 2048 exactly N, 2048. This adapted scaling results in the Figure S12 At sequence length 64 and embedding dimension 5632, the SD-SSM exhibits 21.7x slowdown compared to PD-SSM. The PD-SSM is now around 6.0x slower than the diagonal model.
36

---

Sparse PD-SSM
10
Sparse PD 2D-SSM
10a
Diagonal
Diagonal
Time (ms)
10
Time
10P
10
10"1
256
512
1024
2048
4096
5632
256
512
1024 Hidden Dimension
2048
2816
Hidden Dimension
(a) Sequence Length 64
(b) Sequence Length 256
Figure $12: Runtime measurements in parameter-mateen setting.
PD-SSM PD-5SM With Precomputed Plan)
10X
Diagonal SSM
Time [ms)
Stewdown
PD-S5M
Precomputed Diagonal SSM (Raference)
10a
1x
512
1024
2048
7168
5121024
2048
3072
4096
5120
6144
7168
Hidden Dimension
Hidden Dimenssio
(a) Runtime comparison with length L
(b) Slowdown w.r.t. diagonal baseline, 64.
Figure S13: Measuring the overhead of generating P matrices.
At hidden dimension D 2048, the relative speed-up of PD-SSM over SD-SSM is 10.6x for L = 64, 13.9x for I. = 256, and 15.5x for I. = 512 (not shown). Once again, an increasing trend with
Effect of P Generation Under Equal State Size In this measurement, we compare the runtime of the PD-SSM and the diagonal SSM with version of PD-SSM that receives pre-computed random sparse P matrices input. In this scenario, we set the state size of all models be equal. The results are reported Figure As predicted Table [ the PD parallel scan incurs constant, even diminishing overhead compared to the diagonal scan. The overhead stems primarily from the generation of the P(u) matrices.
E.2
Varying Mamba Depth (A5,2) 2)
Mamba (Gu and Dao 2023) non-negative real-valued transition matrices, which are in theory highly restrictive even for emulating solvable automata (Grazzi et al. 2024 However, we can observe that several layers of the model can in fact learn emulate the non-solvable automaton on in-domain lengths, as shown in Figure SI4 The model however does not exhibit any substantial length generalization.
E.3 PD-SSM Ablations on Arithmetic
We ablate several design choices on the Arithmetic task from Delétang et al. 2023
'Such models must converge to steady state upon application of constant input. This goes contrary to FSA emulation. For example, Parity converges upon repeated application of a
37

---

1.00
Mamba, Layerr
0.75
Mamba, Layers
Accuracy
Mamba, Layers
0.50
0.25
0.00
20
40
60
80
100
Length
Figure S14: Mamba with varying number of layers trained emulate the non-solvable (As, 2)
automaton.
Stochastic P Generation and Inference With Dense P Matrices:
The first ablation centered
on the generation of P matrices, in particular the following deterministic equations:
P = hardmax(M (M) E {0, 13 where hardmax(x), = 1 i=arg maxy 2g
OP Ghardmax(M) (M) @softmax(M))
0M
0M
0M
The dependence on de as well as the indices are omitted for notational simplicity. Typically, straight- through gradient approximators, softmax, are used conjunction with categorical sampling schemes (Paulus et al. [021 [ang et al.) 2engiBongio et al. 2013). In particular, widely used stochastic scheme takes the following form, called Gumbel max:
example of which is our approximation of the hardmax via
P hardmax M G) (0,
OP Ohardmax ( + GG) @softmax (M + G)
0M
G Gumbel 1), [N]
Given the prominence of this scheme, we test its effectiveness on learning to emulate the Arithmetic automaton. Simultancously, we test the effectiveness of using dense P' matrices during inference. While the matrices must be sparse in order to ensure high efficiency during parallel training, at inference, the structure of the matrix can relaxed We test the effectiveness of employing the following matrix generation during inference, P.j softmax(MM.)) E IR This is optionally combined with stochasticity as shown above. The best obtained results with all four combinations of
determinissiicstochastii P generation and hardmax/softtax activation are shown in Figure S15
1.00
0.75
Deterministic Training, Hardmax Inference Deterministic Training, Softmax Inference Stochastic Training, Hardmax Inference Stochastic Training, Softmax Inference
Accuracy
0.50
0.25
0.00
75 Length
100
125
150
Figure S15: P parametrization ablations the Arithmeric FSA with layer of PD-SSM with linear readout. The dashed vertical line indicates the maximum training length.
We can that introducing stochasticity and relaxing sparsity both have detrimental effects accuracy.
"The memory footprint of dense N N matrices is @(N² during training but only @(N²) during inference.
38

---

Nonlinear Readout Experiments:
The second ablation is centered on the readout function (xx) As previously stated, for our tracking experiments, the readout function is defined
/ (z+) W Read (Re (eee==))l/m(xe)) + Reod
with || denoting vector concatenation. Typically, however, neural networks interleave sequence processing layers with nonlinearly activated feed-forward networks (Vaswani et al. 2017), as opposed the affine transformation that we applied. We test the effect of nonlinear readout, defined
(xx) = W Read, aGela ( (WReed,J (Re{z,) (mm(3) + BRead.)) + Read,
We repeat all of the experiments that we report in Figure SI5 but now with the nonlinear readout. We see Sigure[S16tii that the results are significantly worse than with linear readout. No method performs well even on in-domain lengths.
1.00
Accuracy
0.75
Deterministic Training, Hardmax Inference
Deterministic Training, Softmax Inference
0.50
Stochastic Training, Hardmax Inference
0.25
Stochastic Training, Softmax Inference
0.00
25
50
75 Length
100
125
150
Figure $16: P parametrization ablations on the Arithmetic FSA with layer of PD-SSM with nonlinear readout. The dashed vertical line indicates the maximum training length.
Related Work
General Overview of SSMs LTI SSMs have been proposed as more scalable alternative to
Transformers that is also more performant long sequences Gu et al. (020 2021 2022b a Gupta et al.] (2022); Smith et al. (203)); Orvieto er al. 2023). A subsequent analysis showed promising language modeling performance with hybrid architectures based gated SSMs and Attention Ma
ct al. (202)); Fu et al. (2023). Time-variant hybrid systems were then shown to perform significantly better on practical tasks with the Mamba SSM which utilizes diagonal transition matrices Gu and Dao (2023). Consequently, line of work has demonstrated that hybrid models utilizing diagonal time-variant SSMs and attention exhibit better generalization longer sequences, better general language modeling and reasoning performance (Ren et al. 2025 De et al. 2024
Lenz et al. 2025 Wu
al. 2025 Waleffe al. 2024).
Overview of Formal Results and SSM Matrix Structures Concurrently, formal analyses of time-varying SSMs have shown limitations of the diagonal transition matrix structure Merrill et al.) (2024); Cirone et al. (2024). spurring line of work investigating the utility of block-diagonal and unstructured matrices Fan al. (2024): : Terzić et al. (2025), as well as more expressive structured transition matrices, most notably diagonal plus low-rank Yang et al. (2024); Grazzi et al. (2024); Peng et al. (2025); Siems et al.) (2025). with the original inspiration stemming from at least far back as fast-weight programmers Schlag et al. (2021a b): [Schmidhuber (1922) whose computational structure contains products of generalized Householder matrices Yang al. (2024), which enables the adoption of early algorithmic optimizations of such procedures Bischof and Van Loan (987).
Details of Formal Results As a lower bound on diagonal SSMs, SSMSs, al. (2024) show that stack of complex diagonal SSM layers can emulate any solvable automaton, with the stack depth proportional to the Krohn-Rhoded (KR) complexity of the transformation semigroup Krohn and Rhodes (1965); Margolis et al. (2024). As an upper bound on diagonal SSMs, Merrill et al. (2024) derives bound on fixed-depth diagonal selective SSMs with logarithmic precision representation, placing them in the L-uniform TC circuit complexity class. This complexity class encompasses solvable automata. DPLR matrices can emulate any automaton with depth proportional to KR- complexity and width linear in depth and arbitrary readout Siems et al. (2025).
39

---

Experimental Expressivity Analyses Experimental analysis of sequential neural networks trained on formal language tasks goes back to at least (Smith and Zipser 1989; Hochreiter and Schmidhuber 1997). The exact experimental setup we build on is more recent one, with the set of tasks taken from Delétang et al. (2023), and the experimental setup borrowed from Walker et al. (2025). All of the non-solvable group word problems were generated using modified sample generation code
from Liu et al. (2023).
40


Reviews:
[{"review_id": "cEoOZvzX3N", "reviewer": "Reviewer_pBTL", "summary": "This paper proposes a novel parameterization of the transition matrices in selective state-space models (SSMs). Specifically, the authors replace diagonal transition matrices with a product of a column one-hot matrix (P) and a complex-valued diagonal matrix (D). Through both theoretical and empirical analysis, they argue that this new parameterization effectively models arbitrary finite-state automata (FSA). They also demonstrate improved efficiency by comparing the empirical runtime of their method against SD-SSM and Diagonal SSM baselines.", "questions": "How does the FSA-based analysis inform real-world applications? Do FSAs share structural or behavioral similarities with typical use cases of SSMs in NLP or vision tasks?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper is clearly written and easy to follow.\n2. It presents a strong theoretical foundation, supported by empirical improvements in both performance and efficiency.\n3. The work addresses an important problem in the expressivity and computational efficiency of SSMs.\n4. The proposed changes are simple to implement yet yield meaningful benefits.\n\n**Weaknesses**\n\nThe analysis is centered entirely around finite-state automata. While FSAs are a useful proxy, state-space models are increasingly applied in real-world tasks such as natural language processing and computer vision. It remains unclear whether the proposed parameterization would translate into practical benefits in these broader domains.", "was_revised": true, "final_justification": "Overall, I recommend the acceptance of the paper because:\n* The paper presents a strong theoretical foundation, supported by empirical improvements in both performance and efficiency.\n* The work addresses an important problem in the expressivity and computational efficiency of SSMs.\n* The proposed changes are simple to implement yet yield meaningful benefits.\n* Effectiveness in realistic scenarios were addressed in the rebuttals with time-series classification.", "rebuttal": "We thank the reviewer for their thoughtful feedback and are pleased they found the paper clear and appreciated our focus on the expressivity-efficiency trade-off in state-space models (SSMs), as well as the simplicity and theoretical depth of our proposed parameterization.\n\n---\n\n**On the FSA focus and practical relevance**\n\nWe agree that real-world applicability is critical and appreciate the concern about whether FSA-based analysis generalizes beyond synthetic settings. Our core contribution is a state-space model that **can exactly emulate arbitrary finite-state automata (FSA)** while maintaining the parallel scan efficiency of diagonal SSMs. This property significantly enhances the expressive power of parallel sequence models—an ability particularly relevant in domains requiring structured reasoning, such as code generation or formal language understanding.\n\nAlthough large-scale NLP and vision tasks were beyond the scope of this submission, we note growing evidence that **architectural expressivity grounded in formal structures like FSAs does translate into practical benefits**. For example, Grazzi et al. (ICLR 2025) demonstrate that making DeltaNet—a matrix-valued SSM—more expressive in terms of its ability to emulate finite-state automata directly translates to improved performance on tasks like code generation and mathematical problem solving. Hu et al. (ACL 2025) similarly show that pretraining on formal languages enhances downstream NLP task performance. These works reinforce our belief that FSA emulation capabilities can be a building block for success in broader domains.\n\n---\n\n**New real-world benchmarks**\n\nIn our work, we introduce the first state-space model capable of perfectly tracking the states of finite-state automata (FSA) while maintaining the parallel scan cost at the same asymptotic level as diagonal state-space models. Through experiments on the Long Range Arena (LRA), we already observed practical benefits on text and image classification.\n\nTo address the reviewer's helpful suggestion for more practical evaluations, we added experiments on six multiclass time-series classification datasets (table below), covering long sequences (up to 17,000 time steps). This benchmark is widely used in real-world settings like healthcare, and it can be evaluated within the rebuttal window. To obtain the results, we ran a grid search over learning rates in {1e-5, 1e-4, 1e-3} and number of layers in {1, 2}. The state dimensionality was fixed to 16, and the embedding dimensionality was fixed to 64. All other hyperparameters were re-used from the referenced paper (Walker et al. 2025). Notably, this hyperparameter grid is significantly less extensive than the one used to evaluate the baseline methods, see Walker et al. (2024), yet we still achieve state-of-the-art results among the evaluated methods. S6 is the previous best-performing evaluated non-CDE SSM, with a more extensive overview of SSM results including LRU, S5, and Mamba provided in Walker et al. (2024).\n\n| Dataset                | S6          | Log-NCDE    | D-LNCDE     | BD-LNCDE    | DE-LNCDE    |    PD-SSM   |\n|------------------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| EigenWorms            | 85.0 ±16.1  | 85.6 ±5.1   | 80.0 ±5.4   | 86.7 ±4.1   | **87.8 ±5.7**   | 87.2 ±5.1   |\n| EthanolConcentration  | 26.4 ±6.4   | 34.4 ±6.4   | 25.8 ±3.9   | 28.6 ±6.4   | 25.6 ±3.7   | **38.7 ±6.6**   |\n| Heartbeat             | 76.5 ±8.3   | 75.2 ±4.6   | 72.9 ±5.0   | 75.2 ±6.0   | 76.1 ±3.1   | **76.8 ±3.0**   |\n| MotorImagery          | 51.3 ±4.7   | 53.7 ±5.3   | 54.0 ±7.3   | **58.2 ±4.1**   | 54.0 ±5.3   | 55.4 ±5.0   |\n| SelfRegulationSCP1    | 82.8 ±2.7   | 83.1 ±2.8   | 83.5 ±2.1   | **84.9 ±1.9**   | 83.5 ±6.6   | 82.8 ±3.2   |\n| SelfRegulationSCP2    | 49.9 ±9.5   | 53.7 ±4.1   | 53.0 ±5.8   | 53.3 ±7.5   | 46.3 ±3.6   | **54.0 ±2.8**   |\n| Average               | 62.0        | 64.3        | 61.5        | 64.5        | 62.2        | **65.8**        |\n\nPD-SSMs achieve a new state-of-the-art among the evaluated state space models on this dataset (taken from Walker et al. 2025), notably even without building on controlled differential equation (CDE) architectures.\n\nThese findings highlight a growing consensus around the practical benefits of expressive architectures, and they motivate our ongoing work. While the LRA benchmark offers valuable insight, we acknowledge its somewhat synthetic nature. Our newly added time-series experiments help address this by demonstrating real-world relevance. A comprehensive evaluation of our model on large-scale NLP tasks remains an exciting direction for future work.\n\n---\n\n**Extended automaton emulation results**\n\nWe also significantly expanded our comparison on FSA emulation tasks. We now include over 10 recent baselines across four automaton challenges—two more than in the original submission. Concretely, we extended the Table from Walker et al. (2025), by evaluating our proposed model on the full set of state tracking tasks from Deletang et al. (2023). We fully conform to their experimental setup which adopts a two-layer architecture and uses a single, fixed set of hyperparameters on all tasks. While the authors used the best results obtained with state size 128 or 512, we fixed the state size to 128. A summary of central results is reported in the table below. Notably, our model sets the state-of-the-art performance with no hyperparameter tuning.\n\n| Model                    | Cycle Nav.     | Even Pairs     | Mod Arith.. | Parity          | Average |\n|-------------------------|----------------|----------------|-----------------------|------------------|---------|\n| sLSTM                   | 39.2 ±4.3      | 100.0 ±0.0     | 34.8 ±1.5             | 100.0 ±0.0       | 68.5    |\n| xLSTM[1:1]              | 56.6 ±3.6      | 100.0 ±0.0     | 34.4 ±1.4             | 100.0 ±0.0       | 72.8    |\n| DeltaNet                | 49.0 ±5.4      | 100.0 ±0.0     | 44.2 ±8.0             | 58.4 ±1.1        | 62.9    |\n| DeltaNet[−1, 1]         | 47.3 ±6.0      | 100.0 ±0.0     | 63.9 ±7.2             | 97.2 ±1.7        | 77.1    |\n| Gated DeltaNet          | 55.9 ±7.8      | 100.0 ±0.0     | 49.9 ±7.5             | 56.6 ±0.7        | 65.6    |\n| Gated DeltaProduct[-1,1]| 61.4 ±12.0     | 99.6 ±0.6      | 58.0 ±20.0            | 98.8 ±1.5        | 79.5    |\n| RWKV-7                  | 37.8 ±5.0      | 88.1 ±14.2     | 41.6 ±13.8            | 51.0 ±0.3        | 54.6    |\n| mLSTM                   | 87.4 ±4.5      | 100.0 ±0.0     | 29.0 ±5.1             | 50.9 ±0.3        | 66.8    |\n| Transformer             | 24.4 ±0.5      | 90.4 ±10.4     | 23.6 ±0.7             | 52.2 ±0.4        | 47.7    |\n| Mamba                   | 50.7 ±7.8      | 100.0 ±0.0     | 38.1 ±6.0             | 54.5 ±1.5        | 60.8    |\n| D–LNCDE                 | 73.5 ±4.7      | 100.0 ±0.0     | 20.8 ±0.3             | 91.9 ±14.5       | 71.6    |\n| WH–LNCDE                | 66.7 ±7.9      | 87.5 ±17.2     | 23.9 ±1.3             | 62.1 ±2.2        | 60.1    |\n| BD4–LNCDE               | 100.0 ±0.0     | 91.3 ±12.2     | 45.6 ±7.8             | 88.4 ±13.9       | 81.3    |\n| D–DE16–LNCDE            | 77.3 ±21.3     | 81.4 ±9.9      | 94.5 ±5.2             | 81.0 ±18.1       | 83.6    |\n| DPLR4–LNCDE             | 83.9 ±20.1     | 97.7 ±5.2      | 26.0 ±0.7             | 79.6 ±20.3       | 71.8    |\n|**PD-SSM**                  | 97.7 ±0.02    | 96.2 ±0.07    | 96.4 ±0.04            | 99.7 ±0.03       | **97.5**    |\n\n---\n\n**Conclusion**\n\nWhile our focus is on improving the theoretical expressiveness of SSMs via FSA emulation, we have taken concrete steps to show this expressiveness translates into real-world benefits on long-range, structured sequence tasks. A comprehensive evaluation on large-scale NLP or vision datasets remains an exciting direction for future work, and we appreciate the reviewer’s encouragement in that direction."}, {"review_id": "TAGnvKhgcc", "reviewer": "Reviewer_DCmS", "summary": "Building on prior work, this paper proposes a new parameterization of transition matrices for state-space models that achieve greater expressivity for state tracking/automata simulation with lower memory. Concretely:\n1. The paper proposes parameterizing transition matrices as column one-hot times diagonal (PD) form\n2. Theoretically, the paper shows this parameterization unlocks expressivity for state tracking with linear memory in the convolutional form, which is reduced compared to a dense parameterization\n3. Empirically, the authors show this parameterization attains better runtime, better performance on fully synthetic and natural-language state tracking, and strong Long Range Arena performance relative to other time-variant SSMs.", "questions": "“a finite-state automaton with N states that cannot be emulated by any single-layer SSM” What does emulation precisely mean? An SSM can classify the output state of the SSM using a linear layer?\n\nWhat about the other direction: Given a single layer of your PD SSMs, if we want to capture its output with a WFA, how many states would we need?\n\nRegarding your natural language state tracking task: what does a state correspond to? a physical location? Show a full example input.\n\nIn 4.4, why are time-invariant models better than time-invariant models? Is this expected/found elsewhere in the literature?", "limitations": "The major limitation I see the lack of larger scale language modeling experiments: if these were present and validated that the architecture could be scaled up (e.g., with an appropriate hardware kernel) and achieve good performance, I would consider raising my score. I would like to see the cross entropy attained by an SSM with this parameterization or even scaling laws or measures of compute efficiency relative to other architectures. However, I understand these experiments could require significant resources, and could reasonably be relegated to future work motivated by this paper.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n \n1. The paper is well motivated, clear, and rigorous\n2. The proposed PD parameterization is a compelling method to achieve greater expressivity while minimizing memory overhead.\n3. The empirical evaluation is fairly extensive, spanning synthetic state tracking evaluations and more natural tasks\n\n## Weaknesses\n\nIn addition to the existing empirical evaluations, the paper could benefit from reporting language modeling performance (e.g., cross entropy or bits/byte) on a standard dataset.\n\nThe following claim is made regarding other approaches for other methods that balance efficiency and expressivity with SSM transition matrix parameterizations:\n\n> However, these approaches either scale unfavorably and thus prohibit large-scale training, or are not expressive enough to encode arbitrary N-state FSA with a reasonably-sized model such as a single layer with state dimensionality N.\n\nThis claim is made without rigorous support: you have not shown in what sense other methods like RWKV-7 scale poorly. E.g., RWKV-7 also uses a constrained parameterization where each matrix has rank 1. The products of those matrices may have higher rank, which suggests that SCAN might take more memory, but you have not shown this rigorously, so this sentence comes off as too strong. You should either elaborate a bit about the other methods you are comparing against or hedge this sentence appropriately.\n\nRegarding scalability, some of these other methods (e.g., RWKV-7) have scaled up beyond the experiments in this paper. So while they might \"scale unfavorably\" compared to your approach in principle, they have indeed been scaled up.\n\n> Theoretically, time-invariant (fixed) diagonal transition matrices suffice to guarantee universal approximation to any regular causal sequence-to sequence map (Orvieto et al. 2024).\n\nI don't understand this sentence in the intro. Clarify this and explain how it is consistent with the reduced expressivity of diagonal transition matrices for state tracking.", "was_revised": true, "final_justification": "I appreciate the new empirical results and maintain my high score.", "rebuttal": "We are glad that the reviewer has a positive impression of our paper, highlighting its clear motivation, rigor, and strong empirical evaluation, as well as the premise of our PD parameterization in enhancing expressivity with minimal memory overhead.\n\n---\n\n**Extended evaluation, including standard datasets:**\n\n We share the reviewer's interest in how the increased expressiveness translates to other impactful tasks, such as e.g. language modeling, code generation, or mathematical problem solving, tasks typically executed by LLMs. Such an evaluation was unfortunately out of the scope of our paper, but it is a future work we are deeply interested in. Based on recent literature, increased SSM expressivity can translate to practical benefits in other real-world tasks. Grazzi et al. (ICLR 2025) demonstrate that increasing the expressivity of DeltaNet, which can be interpreted as a matrix-valued SSM, translates to significantly reduced perplexity on code generation and mathematical problem solving. Hu et al. (ACL 2025) consistently observe that models pre-trained on formal languages, specifically context-free and context-sensitive languages, exhibit increased performance on standard NLP tasks. A large-scale evaluation of the benefits of our concrete implementation is certainly something we plan to address in future work.\n  \nWhile we do not provide language modeling performance, we have extended the evaluation of our model to an extensive collection of baselines (+10 new models) on: 1) four tasks in FSA emulation (two new tasks compared to our submission); 2) a real-world dataset in long-range multi-class time-series classification.\n\nThe table below extends the experimental evaluation from Walker et al. (2025). We now evaluate +10 sequence models on four FSA emulation tasks. Notably, our model sets the state-of-the-art performance in this setup with no hyperparameter tuning.\n\n\n| Model                    | Cycle Nav.     | Even Pairs     | Mod Arith.  | Parity          | Average |\n|-------------------------|----------------|----------------|-----------------------|------------------|---------|\n| sLSTM                   | 39.2 ±4.3      | 100.0 ±0.0     | 34.8 ±1.5             | 100.0 ±0.0       | 68.5    |\n| xLSTM[1:1]              | 56.6 ±3.6      | 100.0 ±0.0     | 34.4 ±1.4             | 100.0 ±0.0       | 72.8    |\n| DeltaNet                | 49.0 ±5.4      | 100.0 ±0.0     | 44.2 ±8.0             | 58.4 ±1.1        | 62.9    |\n| DeltaNet[−1, 1]         | 47.3 ±6.0      | 100.0 ±0.0     | 63.9 ±7.2             | 97.2 ±1.7        | 77.1    |\n| Gated DeltaNet          | 55.9 ±7.8      | 100.0 ±0.0     | 49.9 ±7.5             | 56.6 ±0.7        | 65.6    |\n| Gated DeltaProduct[-1,1]| 61.4 ±12.0     | 99.6 ±0.6      | 58.0 ±20.0            | 98.8 ±1.5        | 79.5    |\n| RWKV-7                  | 37.8 ±5.0      | 88.1 ±14.2     | 41.6 ±13.8            | 51.0 ±0.3        | 54.6    |\n| Transformer             | 24.4 ±0.5      | 90.4 ±10.4     | 23.6 ±0.7             | 52.2 ±0.4        | 47.7    |\n| Mamba                   | 50.7 ±7.8      | 100.0 ±0.0     | 38.1 ±6.0             | 54.5 ±1.5        | 60.8    |\n| BD4–LNCDE               | 100.0 ±0.0     | 91.3 ±12.2     | 45.6 ±7.8             | 88.4 ±13.9       | 81.3    |\n| D–DE16–LNCDE            | 77.3 ±21.3     | 81.4 ±9.9      | 94.5 ±5.2             | 81.0 ±18.1       | 83.6    |\n|**PD-SSM**                  | 97.7 ±0.02    | 96.2 ±0.07    | 96.4 ±0.04            | 99.7 ±0.03       | **97.5**    |\n\nThe table below reports the performance of a variety of parallelizable sequence models on time-series classification with sequences of lengths up to over 17k. S6 is the previous best-performing evaluated SSM, with a more extensive overview of SSM results provided in Walker et al. (2024).\n\n| Dataset                | S6          | Log-NCDE    | D-LNCDE     | BD-LNCDE    | DE-LNCDE    |    PD-SSM   |\n|------------------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| EigenWorms            | 85.0 ±16.1  | 85.6 ±5.1   | 80.0 ±5.4   | 86.7 ±4.1   | **87.8 ±5.7**   | 87.2 ±5.1   |\n| EthanolConcentration  | 26.4 ±6.4   | 34.4 ±6.4   | 25.8 ±3.9   | 28.6 ±6.4   | 25.6 ±3.7   | **38.7 ±6.6**   |\n| Heartbeat             | 76.5 ±8.3   | 75.2 ±4.6   | 72.9 ±5.0   | 75.2 ±6.0   | 76.1 ±3.1   | **76.8 ±3.0**   |\n| MotorImagery          | 51.3 ±4.7   | 53.7 ±5.3   | 54.0 ±7.3   | **58.2 ±4.1**   | 54.0 ±5.3   | 55.4 ±5.0   |\n| SelfRegulationSCP1    | 82.8 ±2.7   | 83.1 ±2.8   | 83.5 ±2.1   | **84.9 ±1.9**   | 83.5 ±6.6   | 82.8 ±3.2   |\n| SelfRegulationSCP2    | 49.9 ±9.5   | 53.7 ±4.1   | 53.0 ±5.8   | 53.3 ±7.5   | 46.3 ±3.6   | **54.0 ±2.8**   |\n| Average               | 62.0        | 64.3        | 61.5        | 64.5        | 62.2        | **65.8**        |\n\nAs we can see, our method also achieves a new state-of-the-art among the evaluated SSMs on this dataset (taken from Walker et al. 2025), outperforming approaches that rely on controlled differential equation (CDE) architectures.\n\n---\n\n**Clarifying our statements on the scaling of related methods:**\n\nThe reviewer is correct to point out that RWKV-7 and related methods have indeed been scaled to larger experimental setups. Our statement on unfavorable scaling preventing large-scale training does not refer to the family of matrix-valued SSMs that adopt a diagonal plus low-rank (DPLR) transition matrix structure, such as RWKV-7. The comment rather refers to unstructured transition matrices from Terzic et al. (2025), which do enable the emulation of any N-state FSA using a single layer with state size N, yet are prohibitively expensive in a larger setting. We have made sure to explicitly state these facts in a revised version of the paper.\n\nWe additionally acknowledge that our submission did not provide sufficient theoretical detail on RWKV-7 and related DPLR methods. We have referred to previous work which provides bounds on the model size necessary to emulate FSAs using such approaches, yet we have not clearly stated what those bounds are and how they compare to ours.\n\nTo clarify what we mean by the statement that DPLR-based methods are not expressive enough to encode any N-state FSA with a reasonably-sized model, we turn to Theorem 4 from Grazzi, Siems et al. (2024), which exactly considers SSMs with diagonal plus low-rank transition matrices. We paraphrase the theorem to focus on the relevant aspects of it as follows:\n\n> SSMs with state transition matrices that are repeated products of Generalized Householder matrices, each with eigenvalues in the range [−1,1], can recognize any regular language. In particular, every FSA A=(Σ,Q,q0,δ) can be implemented by a finite precision SSM with s≤2^|Q|layers, where the state is of size n≤|Q| and the number of Generalized Householder factors in the transition matrix is p≤s.\n\nIn this construction, the number of layers is exponential in the number of states, as is the number of factors which build up the transition matrix. In contrast, our model allows the emulation of any N-state FSA using **one layer and a state size of N**, where the size of the readout is linear in the number of automaton states.\n\nIn a separate result, Peng, Zhang, Goldstein et al. (2025) show that the RWKV-7 model is able to emulate an arbitrary FSA using four layers. However, the provided construction relies on MLP layers which implement lookup tables whose sizes are exponential in the size of the state set, which becomes infeasible for even moderately large FSAs.\n\nWe have now added a paragraph to the paper that contextualizes our theoretical results through comparison with these previous theoretical results on model expressivity, and thank the reviewer for bringing this up.\n\n---\n\n**Clarifying the universal approximation property of diagonal SSMs**\n\nThe referenced result on universal function approximation assumes a mapping from a sufficiently regular fixed-length sequence to another fixed-length sequence. The setting of tokens living in a finite set, such as what we have, is drastically different and not discussed in their work. In addition, the cited work makes no assumption on the numerical precision used by the SSM, and the latent dimension of the SSM and the subsequent MLP scale with the length of the sequence. As such, the framework and the assumptions used by the authors are vastly different from the empirically validated circuit-complexity bounds presented in Merill et al. (2024), which form the background of our work.\n\n---\n\n**Questions:**\n\n1. We indeed refer to accurate linear classification of the SSM hidden states into the classes defined by the automaton states. In our tasks, the input to the SSM is a sequence of one-hot encoded entries from the FSA vocabulary, and the model, with a linear layer at the output, is trained to predict the automaton state given such a sequence of inputs.\n\n2. The number of possible values that the entries of the hidden state can assume is very large, essentially limited only by numerical representation capacity. An interesting approach towards answering this question may make use of methods for automatic extraction of FSAs from the model, such as e.g. the one proposed in Weiss et al. (2019).\n\n3. In this task, the states are fully defined by the underlying automaton. The difference between this task and the one we presented in Section 4.2 lies in the encoding of the inputs. Whereas the inputs in the \"synthetic state tracking\" task were one-hot encodings of a discrete set of inputs, the inputs we consider in \"natural-language state tracking\" are LLM-generated embeddings of meaningful English sentences.\n\n4. This result is indeed expected and is found elsewhere in literature, e.g., Soydan, Zubic et al. (2025).\n\n---\n\nWe thank the reviewer for their thoughtful review and hope that we were able to address all their questions and concerns."}, {"review_id": "31ePCFJW5S", "reviewer": "Reviewer_XSo7", "summary": "This paper addresses a fundamental limitation in State Space Models (SSMs): the trade-off between expressiveness and computational efficiency. While diagonal SSM blocks are computationally tractable, they suffer from limited expressive power. Conversely, unstructured transition matrices offer full expressiveness but at prohibitive computational costs. The authors propose a novel middle-ground approach using structured matrices with a PD parameterization, where P is a one-hot matrix computed via a complex procedure and D is diagonal. This parameterization maintains efficiency while forming a monoid under multiplication, enabling parallel scan algorithms.\n\nThe paper establishes theoretical foundations by measuring expressive power through the class of Finite State Automata that SSMs can emulate (without post-SSM nonlinearity). \nTo address the non-trivial computations required for P, which present differentiation challenges, the authors provide implementation strategies and circumvention methods.\nThe theoretical claims are empirically validated through testing on state tracking problems.", "questions": "## Minor Issues and Suggestions\n\n- **Lines 34-36**: The universal approximation claim is correct and actually supports your arguments even more strongly. Consider clarifying that in the cited result, the approximation is actually achieved by the neural network after the SSM, while the SSM itself primarily reconstructs the input. Since your approach focuses on the SSM without post-processing nonlinearity, making this distinction explicit would better highlight the significance of your theoretical contribution.\n- **Lines 79-82**: The invertibility of A, while implied by perturbation arguments, should be stated more explicitly.\n- **Lines 86-87**: (Pedantic comment) in addition to the stated condition the matrices need to be all diagonalizable by themselves as well.\n- **Lines 144-148**: The choice of P through post-processed mixture seems convoluted. Please elaborate on:\n    - Whether this was the original design choice\n    - Alternative approaches considered (e.g., input-dependent low-rank followed by hardmax)\n    - Comparative analysis of different parameterization strategies\n- **Line 165**: (Pedantic comment) Property 2 alone is insufficient to justify associative scan usage. A remark after line 157 demonstrating that matrices in H can be written as PD would improve rigor.\n- **Section 4.2**: Consider expanding the analysis with additional comparisons that would strengthen the paper's impact. I assume only SSM blocks are compared here - it would be valuable to explore whether including MLPs afterwards changes the relative performance. Additionally, reporting how many layers Mamba requires to reach 100% accuracy would provide an extremely compelling addition to demonstrate the efficiency gains of your approach.\n- **Lines 227-231**: The architecture description needs expansion, potentially in an appendix.\n\n\n### Appendix Issues \n\n- **Notation Consistency**: Inconsistent use of Z/nZ, Zn, and C_n for the same group throughout\n- **Lines 40-41**: T(A) notation unclear; specify the second element of delta in Q and define σ₁,...,T\n- **Lines 53-57**: Quantify all mathematical objects\n- **Lines 66-67**: Inconsistent switching between \"group\" and \"automaton\" terminology\n- **Line 141**: Verify if C₄/C₂ × C₄ should be (C₂ × C₄)/C₄; inconsistent Z₄ and C₄ usage\n- **Lines 144-146**: Notation {e}/C₄, {e}/Z₄, {e}/G should be reversed\n- **Line 173**: Reference Definition 12 when first using \"Uniform\" in Definition 10\n- **Line 181**: There appears to be an inconsistency regarding fan-in restrictions. The text states that \"NC1 allows for logarithmic depth, but restricts the fan-in of the gates to 2,\" while the definition only mentions that fan-in is bounded. Please clarify this discrepancy.\n- **Line 231**: Use standard notation instead of ∂⁺ for total derivative\n- **Line 267**: In the equation \"xₖ = Aₖ xₖ₋₁ + bₖ\", the subscript of A and b should be \"k-1\" for consistency with both the proof and the results presented below.\n- **Line 273**: Quantify P appropriately\n- **Equation below 269**: (Pedantic comment) Specify that α and β are not all zero in summation equalities\n\n\n\n## Recommendation\n\nThis paper addresses an important problem in the SSM literature with a theoretically sound and well-motivated approach. The core contribution—finding a middle ground between diagonal SSMs and unstructured matrices through the PD parameterization—is valuable and tackles a fundamental limitation in the field. However, the current submission has notable gaps that prevent clear acceptance at this stage.\n\nI would genuinely like to accept this paper as it shows strong theoretical promise and addresses a central problem in the SSM literature. However, it requires multiple small but targeted improvements: the appendix and proofs need polishing, the experiments need improvement, and experimental details must be included to ensure fair comparisons with competing models. With proper revision addressing these specific issues, this work would clearly merit acceptance.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n1. **Clear Problem Formulation**: The paper tackles one of the most important open problems in the SSM literature with a well-motivated theoretical framework.\n2. **Theoretical Rigor**: The proposed architecture is theoretically grounded and addresses fundamental expressiveness limitations of diagonal SSMs.\n3. **Practical Considerations**: The authors provide detailed analysis of training difficulties and propose concrete solutions for implementation challenges.\n4. **Novel Contribution**: The PD parameterization represents a principled approach to balancing expressiveness and computational efficiency.\n\n## Weaknesses\n\n1. **Insufficient Experimental Validation**: The experimental section has significant gaps that undermine the paper's contributions:\n    - **Missing experimental setup details**: Critical information about hyperparameter selection, training procedures, and experimental configurations is absent. Specifically: How were hyperparameters chosen? Were hyperparameter sweeps conducted? How was fair comparison between different models ensured? The learning rate appears constant across S2 and S3, and hyperparameter choices for Mamba are not visible.\n    - **Lack of comparison with recent models**: No benchmarking against important recent SSM variants including Mamba2, DeltaNet, GatedDnet, and RWKV-7, which are essential baselines for evaluating the proposed method\n    - **Limited scope of experiments**: While the focus on toy models and limited language modeling experiments may be acceptable for an initial architecture introduction (following similar literature precedents), the current experimental validation is insufficient to demonstrate the method's practical advantages\n2. **Presentation Issues**: Appendix A (Algebra and FSA) contains poorly organized algebraic content with numerous inconsistencies and unclear definitions that require substantial polishing for clarity. For example, Appendix A2 inconsistently switches between Z/nZ, Zn, and Cn to denote the same group. The mathematical exposition suffers from such notation inconsistencies, missing quantifications, and terminological confusion that hinder comprehension.", "was_revised": true, "final_justification": "I recommend acceptance. The authors have addressed all raised concerns, expanded the experimental evaluation, and clarified the theoretical framework. The work tackles a fundamental limitation of modern SSMs and represents a meaningful contribution that merits publication.", "rebuttal": "We thank the reviewer for their exceptionally careful reading of our paper. We are glad that they recognize the importance of the studied problem and the theoretical and methodological contributions of our work. We are pleased that the reviewer recognizes the empirical analysis and practical considerations addressed. It is very encouraging to hear that our work would merit acceptance given an appropriate revision, and we are especially thankful for the constructive and comprehensive list of suggestions for improvements. \n\n---\n\n**Insufficient Experimental Validation**\n\n***Experimental Setup Details***: The text we submitted indeed omits important information on the experimental setup, including the optimizer, loss functions, hyperparameter search procedures. The accidental omission of these details is unfortunate, and have made sure to include them in full detail in the final text. For example, the experimental details on LRA only listed the hyperparameters for each task. In contrast, the improved text now reads as follows:\n\n  >The optimal hyperparameters for our model on the long-range arena dataset were obtained va grid search defined by all combinations of the following values: Learning rate in {1e-5, 5e-5, 1e-4, 5e-4, 1e-3}, weight decay in {0.001, 0.01, 0.1, 0.05}, and dropout in {0.0, 0.1, 0.3}. On each task, we report the average accuracy over three random seeds. The embedding dimension and state size were both fixed to 128, with the exception of the Retrieval dataset in which we reduced it to 64. We used Adam with the default parameters (0.9, 0.999). The hyperparameters of the models we compare with were obtained via an extensive Bayesian hyperparameter search, as outlined in (Soydan, Zubic et al., 2025).\n\nWe agree that clearly stating such information is central to gauge the fairness of our comparison, and have added analogous descriptions to all of the tasks considered.\n\n***Comparison with Recent Models and Limited Experimental Scope***: We agree that a thorough comparison with the variety of modern SSMs is of central importance. While we did address the two extreme ends of the spectrum, diagonal and dense transition matrices, a more thorough comparison with a range of established models was missing. To address this, we now provide a significantly extended comparison with related methods.\n\nFirstly, we extended the Table from Walker et al. (2025), by evaluating our proposed model on the full set of state tracking tasks from Deletang et al., (2023). We fully conform to their experimental setup which adopts a two-layer architecture and uses a single, fixed set of hyperparameters on all tasks. While the authors used the best results obtained with state size 128 or 512, we fixed the state size to 128. A summary of central results is shown below. Notably, our model sets the state-of-the-art performance with no hyperparameter tuning.\n\n| Model                    | Cycle Nav.     | Even Pairs     | Mod Arith.   | Parity          | Average |\n|-------------------------|----------------|----------------|-----------------------|------------------|---------|\n| DeltaNet                | 49.0 ±5.4      | 100.0 ±0.0     | 44.2 ±8.0             | 58.4 ±1.1        | 62.9    |\n| DeltaNet[−1, 1]         | 47.3 ±6.0      | 100.0 ±0.0     | 63.9 ±7.2             | 97.2 ±1.7        | 77.1    |\n| Gated DeltaNet          | 55.9 ±7.8      | 100.0 ±0.0     | 49.9 ±7.5             | 56.6 ±0.7        | 65.6    |\n| Gated DeltaProduct[-1,1]| 61.4 ±12.0     | 99.6 ±0.6      | 58.0 ±20.0            | 98.8 ±1.5        | 79.5    |\n| RWKV-7                  | 37.8 ±5.0      | 88.1 ±14.2     | 41.6 ±13.8            | 51.0 ±0.3        | 54.6    |\n| Transformer             | 24.4 ±0.5      | 90.4 ±10.4     | 23.6 ±0.7             | 52.2 ±0.4        | 47.7    |\n| Mamba                   | 50.7 ±7.8      | 100.0 ±0.0     | 38.1 ±6.0             | 54.5 ±1.5        | 60.8    |\n| BD4–LNCDE               | 100.0 ±0.0     | 91.3 ±12.2     | 45.6 ±7.8             | 88.4 ±13.9       | 81.3    |\n| D–DE16–LNCDE            | 77.3 ±21.3     | 81.4 ±9.9      | 94.5 ±5.2             | 81.0 ±18.1       | 83.6    |\n|**PD-SSM**                  | 97.7 ±0.02    | 96.2 ±0.07    | 96.4 ±0.04            | 99.7 ±0.03       | **97.5**    |\n\nWhile the table above significantly extends the set of experiments and comparisons we already report on, it is still limited to FSA emulation. We extend the evaluation of our method to more real-world tasks by including additional experiments on time-series classification with long-range dependencies.\n\n| Dataset                | S6          | Log-NCDE    | D-LNCDE     | BD-LNCDE    | DE-LNCDE    |    PD-SSM   |\n|------------------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| EigenWorms            | 85.0 ±16.1  | 85.6 ±5.1   | 80.0 ±5.4   | 86.7 ±4.1   | **87.8 ±5.7**   | 87.2 ±5.1   |\n| EthanolConcentration  | 26.4 ±6.4   | 34.4 ±6.4   | 25.8 ±3.9   | 28.6 ±6.4   | 25.6 ±3.7   | **38.7 ±6.6**   |\n| Heartbeat             | 76.5 ±8.3   | 75.2 ±4.6   | 72.9 ±5.0   | 75.2 ±6.0   | 76.1 ±3.1   | **76.8 ±3.0**   |\n| MotorImagery          | 51.3 ±4.7   | 53.7 ±5.3   | 54.0 ±7.3   | **58.2 ±4.1**   | 54.0 ±5.3   | 55.4 ±5.0   |\n| SelfRegulationSCP1    | 82.8 ±2.7   | 83.1 ±2.8   | 83.5 ±2.1   | **84.9 ±1.9**   | 83.5 ±6.6   | 82.8 ±3.2   |\n| SelfRegulationSCP2    | 49.9 ±9.5   | 53.7 ±4.1   | 53.0 ±5.8   | 53.3 ±7.5   | 46.3 ±3.6   | **54.0 ±2.8**   |\n| Average               | 62.0        | 64.3        | 61.5        | 64.5        | 62.2        | **65.8**        |\n\nPD-SSMs achieve a new state-of-the-art among the evaluated state space models on this dataset (taken from Walker et al. 2025), notably even without building on controlled differential equation (CDE) architectures. S6 is the previous best-performing evaluated non-CDE SSM, with a more extensive overview of SSM results provided in Walker et al. (2024).\n\n---\n\n**Presentation Issues**\n\n We thank the reviewer for pointing out the notational and conceptual inconsistencies. We aimed to provide a self-contained tutorial on the relevant concepts and frameworks. We are thus particularly grateful for the detailed proofread provided by the reviewer. In addition to their suggestions, we have found several unfortunate inconsistencies that we have since corrected. For example, the initial submission's Theorem 3 states the following:\n\n  > Under the assumption that ${TC}^0 \\neq {NC}^1$, constant depth and width diagonal log-precision SSMs can be emulated by a logspace-uniform $TC^0$ circuit.\n\nThe assumption is, however, not required for the stated conclusion, and the implications of the conclusion are not clearly spelled out. The improved version of Theorem 3 is now summarized as:\n\n  > Under the assumption that ${TC}^0 \\neq {NC}^1$, log-precision diagonal SSMs cannot emulate automata with non-solvable transformation groups.\n\n---\n\n**Addressing the Suggestions:**\n\n **Lines 79-82:** The text now explicitly states: $\\forall \\varepsilon > 0, \\forall A \\in \\mathbb{R}^{N\\times N}, \\exists A_\\varepsilon \\in \\mathbb{R}^{N \\times N}$, invertible $W \\in \\mathbb{C}^{N \\times N}$ and diagonal $\\Lambda \\in \\mathbb{C}^{N \\times N}$ s.t. $ A_\\varepsilon=W\\Lambda W^{-1} $ and $\\||A - A_\\varepsilon\\||_F < \\varepsilon.$\n\n **Lines 79-82:** Assuming $A(u_t)$ are diagonalizable under the same change of basis already implies individual diagonalizability.\n\n **Lines 144-148:** The specific choice of the P parametrization does in fact provide certain practical benefits compared to alternatives such as a linear generator by reducing the number of parameters and operations. We now include a paragraph elaborating on those.\n\n **Section 4.2** We agree that the proposed experiments are interesting ones, and we did in fact report results with these two ablations. Due to the page constraint, the ablations are part of the appendix (E.2 and E.3). We deeply appreciate the suggestion for improvement; a more extensive version of the ablations can be of benefit in the main text too.\n    \n **Lines 227-231** The new version of the paper provides a full sketch of the architecture, highlighting architectural details such as positioning of the norms and the design of the residual connections.\n \n---\n\n**Addressing the Appendix Issues:**\n\n1. We now refer to the cyclic group using Zn.\n2. We now provide a definition of $\\delta(\\cdot, \\sigma_{1,\\dots,T}):Q \\rightarrow Q$ as the composition of the single-step $Q \\rightarrow Q$ functions $\\delta(\\cdot, \\sigma_1), ..., \\delta(\\cdot, \\sigma_T)$, with $\\sigma_i \\in \\Sigma$. \n3. We now denote the group set as G and denote the binary operation by \\cdot. We have appropriately quantified all objects in the sense that it is always clear that the elements listed in the different properties belong to the group set G.\n4. We now make no references to automata in this section.\n5. The factor group should indeed be written as (Z₂ × Z₄)/Z₄. We have corrected this error and ensured consistent notation throughout.\n6. See above.\n7. We have removed the mention of uniformity in this definition.\n8. The definition of $NC^1$ has been revised to correctly state that the gate fan-in is restricted to 2.\n9.  We have revised the text to better conform to standard notation, writing total derivatives using $d$ and partial derivatives using $\\partial$.\n10. We have corrected the typos in the proof and subsequent results to ensure consistency with the presented indexing.\n11. The text now makes it clear that P is an element of the monoid H.\n12. We have incorporated the helpful suggestion.\n\n---\n\nDue to space constraints, we could not address each individual suggestion in the rebuttal. Once again, we thank the reviewer for their thoughtful feedback, including their extensive list of comments and suggestions. Addressing their concerns and following their suggestions allowed us to substantially improve the paper, and by doing so, we hope to convince them to recommend acceptance."}, {"review_id": "vR5XPiAad8", "reviewer": "Reviewer_SXh7", "summary": "This paper proposes PD-SSM, a structured state-space model with a novel input-dependent structured state-transition matrix, $A(u_t)=P(u_t)D(u_t)$, where $P(u_t)$ is a binary matrix with one non-zero element per column and $D(u_t)$ is a complex diagonal matrix. This structure fits within a large family of existing structures, including the diagonal structure of Mamba, the dense structure of IDS4, Linear NCDEs, and SD-SSM, the block-diagonal structure of block-diagonal input dependent linear RNNs, and the diagonal-plus-low-rank structure of DeltaNet. \n\nThe paper shows that PD-SSM has the same asymptotic computational complexity as using diagonal transition matrices and can solve any finite state automata with a hidden dimension that scales linearly with the number of states. Additionally, PD-SSM empirically solves a number of state-tracking benchmarks and outperforms Mamba and S7 on a subset of the long range arena benchmark.", "questions": "## Questions\n\n- How were the hyperparameters chosen for each dataset?\n\n## Suggestions\n\n- As mentioned, a theoretical and empirical comparison to the already existing structures in the literature is critical for a paper proposing a new structure. This addition would significantly improve the paper. Given an appropriate demonstration of the benefits of the PD structure over BD and DPLR, I would raise my score.\n\n- A log scale on the y-axis of figure 4 would make the comparison with the diagonal structure easier. \n\n- After the submission deadline, [this paper](https://arxiv.org/abs/2505.17761) introduced two more possible structures for the transition matrix, and introduced a unifying framework for input-dependent structured state transition matrices. I mention it here as I believe including this paper in the discussion of alternative structures would be benficial. However, there is naturally no requirement to engage with it given that it appeared after submission.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The paper is well written.\n\n- The PD structure is well motivated, both from a theoretical cost stand point and the analysis showing that any FSA can be represented in an efficient manner.\n\n- The benchmark datasets are suitable, and the PD structure clearly demonstrates an increase in expressivity over diagonal matrices.\n\n- The natural language state-tracking benchmark provides a good indication that the results on the regular language benchmarks translate into real-world language modelling performance.\n\n## Weaknesses\n\n- The paper limits the theoretical and empirical results to only diagonal, dense, and PD structures. However, as noted by the authors on lines 43 and 44, both block-diagonal (BD) and diagonal-plus-low-rank (DPLR) structures exist in the literature. Table 1 and the empirical results neglect these additional structures, and no arguments are made as to why the PD structure should be favoured over BD and DPLR.\n\n- Both Table 2 and Table 3 are currently incomplete. Table 2 is missing cycle navigation and even pairs, both of which SD-SSM solves perfectly, and Table 3 is missing the pathfinder datasets (which the authors note is due to an issue with their compute cluste). The paper would be significantly improved by completing the missing datasets and expanding the empirical results to include BD and DPLR structured matrices.\n\n- Given that computational cost is a main motivating factor for the PD structure, the empirical runtime of the model is not sufficiently discussed in the main body of the text. As shown in the Appendix, despite having the same asymptotic computational cost, going from diagonal to a PD structure can lead to an order of magnitude longer training time per step. \n\n- The main body claims $C_2\\times C_{30}$ and $D_{30}$ are trained on sequences up to length $40$, but the Appendix claims they were trained on sequences up to length $90$.", "was_revised": true, "final_justification": "The authors have significantly improved the empirical evaluation of their proposed structure, expanding both the datasets and baselines. This, coupled with their existing theoretical results, represents a substantial contribution to the literature on state transition matrices. I am happy to recommend this paper for acceptance.", "rebuttal": "We thank the reviewer for their careful reading of our paper. We are glad that the reviewer finds the paper well written and that they appreciate the theoretical analysis and motivation. We are pleased that they find our benchmarks suitable and effective, even as indicators for real-world language modeling benefits.\n\n---\n\n**Weaknesses 1 and 2:** We agree that the paper would benefit from a more thorough comparison with the variety of modern SSMs, in particular those adopting BD and DPLR transition matrices. To address this, we provide significantly extended results to strengthen our contribution. \n\nFirstly, the table below extends the experimental evaluation from Walker et al. (2025). We now evaluate +10 recurrent and parallelizable sequence models on four FSA emulation tasks. We fully conform to their experimental setup which adopts a two-layer architecture and uses a single, fixed set of hyperparameters on all tasks. While the authors used the best results obtained with state size 128 or 512, we fixed the state size to 128. Notably, our model sets the state-of-the-art performance with no hyperparameter tuning.\n\n| Model                    | Cycle Nav.     | Even Pairs     | Mod Arith.  | Parity          | Average |\n|-------------------------|----------------|----------------|-----------------------|------------------|---------|\n| xLSTM[1:1]              | 56.6 ±3.6      | 100.0 ±0.0     | 34.4 ±1.4             | 100.0 ±0.0       | 72.8    |\n| DeltaNet                | 49.0 ±5.4      | 100.0 ±0.0     | 44.2 ±8.0             | 58.4 ±1.1        | 62.9    |\n| DeltaNet[−1, 1]         | 47.3 ±6.0      | 100.0 ±0.0     | 63.9 ±7.2             | 97.2 ±1.7        | 77.1    |\n| Gated DeltaNet          | 55.9 ±7.8      | 100.0 ±0.0     | 49.9 ±7.5             | 56.6 ±0.7        | 65.6    |\n| Gated DeltaProduct[-1,1]| 61.4 ±12.0     | 99.6 ±0.6      | 58.0 ±20.0            | 98.8 ±1.5        | 79.5    |\n| RWKV-7                  | 37.8 ±5.0      | 88.1 ±14.2     | 41.6 ±13.8            | 51.0 ±0.3        | 54.6    |\n| Transformer             | 24.4 ±0.5      | 90.4 ±10.4     | 23.6 ±0.7             | 52.2 ±0.4        | 47.7    |\n| Mamba                   | 50.7 ±7.8      | 100.0 ±0.0     | 38.1 ±6.0             | 54.5 ±1.5        | 60.8    |\n| BD4–LNCDE               | 100.0 ±0.0     | 91.3 ±12.2     | 45.6 ±7.8             | 88.4 ±13.9       | 81.3    |\n| D–DE16–LNCDE            | 77.3 ±21.3     | 81.4 ±9.9      | 94.5 ±5.2             | 81.0 ±18.1       | 83.6    |\n| DPLR4–LNCDE             | 83.9 ±20.1     | 97.7 ±5.2      | 26.0 ±0.7             | 79.6 ±20.3       | 71.8    |\n|**PD-SSM**                  | 97.7 ±0.02    | 96.2 ±0.07    | 96.4 ±0.04            | 99.7 ±0.03       | **97.5**    |\n\nOn the Pathfinder dataset, our model achieves 62.61% average accuracy. The average LRA accuracy of our method is now 74.43%, compared to the 66.44% achieved by Mamba and 73.89% achieved by S7.\n\nTo extend the evaluation of our method on more real-world datasets, we further add results on time-series classification with long-range dependencies, following Walker et al. (2025). To obtain the results, we ran a grid search over learning rates in {1e-5, 1e-4, 1e-3} and number of layers in {1, 2}. The state size is 16, and the embedding size is 64. Notably, this hyperparameter grid is significantly less extensive than the one used to evaluate the baseline methods. We happily report that PD-SSMs natively also achieve a new state-of-the art for SSMs on this dataset, notably without adopting a CDE structure.\n\n| Dataset                | S6          | Log-NCDE    | D-LNCDE     | BD-LNCDE    | DE-LNCDE    |    PD-SSM   |\n|------------------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| EigenWorms            | 85.0 ±16.1  | 85.6 ±5.1   | 80.0 ±5.4   | 86.7 ±4.1   | **87.8 ±5.7**   | 87.2 ±5.1   |\n| EthanolConcentration  | 26.4 ±6.4   | 34.4 ±6.4   | 25.8 ±3.9   | 28.6 ±6.4   | 25.6 ±3.7   | **38.7 ±6.6**   |\n| Heartbeat             | 76.5 ±8.3   | 75.2 ±4.6   | 72.9 ±5.0   | 75.2 ±6.0   | 76.1 ±3.1   | **76.8 ±3.0**   |\n| MotorImagery          | 51.3 ±4.7   | 53.7 ±5.3   | 54.0 ±7.3   | **58.2 ±4.1**   | 54.0 ±5.3   | 55.4 ±5.0   |\n| SelfRegulationSCP1    | 82.8 ±2.7   | 83.1 ±2.8   | 83.5 ±2.1   | **84.9 ±1.9**   | 83.5 ±6.6   | 82.8 ±3.2   |\n| SelfRegulationSCP2    | 49.9 ±9.5   | 53.7 ±4.1   | 53.0 ±5.8   | 53.3 ±7.5   | 46.3 ±3.6   | **54.0 ±2.8**   |\n| Average               | 62.0        | 64.3        | 61.5        | 64.5        | 62.2        | **65.8**        |\n\nIn addition to the experimental results, we want to highlight that we provided theoretical arguments in the paper on why PD is favourable over the BD and DPLR structures, although we agree with the reviewer that we did not explicitly spell them out:\n- We proved the existence of FSAs that cannot be emulated by an SSM with state size less than N-1. \n- We proved the fact that a single-layer PD-SSM can emulate any N-state FSA with state size N.\n\nTaken together, these results clearly speak against adopting block-diagonal (BD) transition matrices, since they are theoretically less expressive than PD-SSMs (they cannot mix between blocks), but more expensive (O(b^2 d L) vs our O(d L)). In addition, theoretical constructions for DPLR models to emulate FSAs rely either on an exponential number of layers and DPLR factors (Grazzi et al., 2024), or rely on MLPs with exponentially large hidden layers (Peng, Zhang, Goldstein et al, 2025), in stark contrast with the guarantees provided by our parametrization. We will expand on this analysis in a revision of our text.\n\n---\n\n**Weakness 3:** Due to the restricted number of pages in the initial submission, we were indeed unable to further open up this point in the main body. Still, as the reviewer points out, we provide a detailed break-down on the empirically observed computational cost in the Appendix, and further mention this in the limitations section. While our implementation is not optimized on the kernel level, Table S8 suggests that the generation of P matrices is responsible for most of the compute. Indeed, the table demonstrates that a parallel scan with PD transition matrices only has a 2x overhead compared to diagonal transition matrices. To address the reviewer's concern, we will switch to a log-log plot for Figure 4 in the main body of the text, move Table S8 from the Appendix to the main sections, and more thoroughly discuss the P matrix generation as a bottleneck. We suggest the following additional text:\n\n>As shown in Figure 4, PD-SSM scales significantly better than SD-SSM. PD-SSM’s higher runtime compared to diagonal SSM stems primarily from the additional operations in the generation of P: the simultaneous soft selection of transition matrices $M_i$ across the sequence during parallel execution incurs additional compute and memory. Table S8 confirms these findings and suggests potential improvements in future work.\n\n---\n\n**Weakness 4:** We appreciate the reviewer catching this inconsistency. The two tasks, C2xC30 and D30 were indeed trained on sequences of length up to 90.\n\n---\n\n**Question: Hyperparameters**\n\n- Long-Range Arena: We performed a grid search defined by all combinations of the following values: Learning rate in {1e-5, 5e-5, 1e-4, 5e-4, 1e-3}, weight decay in {0.001, 0.01, 0.1, 0.05}, and dropout in {0.0, 0.1, 0.3}. On each task, we report the average accuracy over three random seeds. The embedding dimension and state size were both fixed to 128, with the exception of the Retrieval dataset in which we reduced it to 64. We used Adam with the default parameters (0.9, 0.999). The hyperparameters of the models we compare with were obtained via an extensive Bayesian hyperparameter search, as outlined in (Soydan, Zubic et al., 2025).\n\n- FSA Results (Section 4.2): We ran a grid search over learning rates in {5e-5, 1e-4, 5e-4, 1e-3}, state sizes in {64, 128}, and the number of dictionary matrices (K) in {6, 8}. The reported baseline results are taken from Terzic et al. (2025), who ran similar hyperparameter grid searches for all baseline methods. \n\n- New FSA Results: We re-used the hyperparameters from the referenced paper (Walker et al., 2025) with no tuning and with the state size fixed to 128.\n\n- Time Series: We ran a grid search over learning rates in {1e-5, 1e-4, 1e-3} and number of layers in {1, 2}. The state dimensionality was fixed to 16, and the embedding dimensionality was fixed to 64. All other hyperparameters were re-used from the referenced paper (Walker et al. 2025). Notably, this hyperparameter grid is significantly less extensive than the one used to evaluate the baseline methods, see Walker et al. (2024).\n\n---\n\n**Suggestions:**\n\n1. **Comparison with BD and DPLR**: Addressed in the two tables above, as well as in our theoretical arguments.\n\n2. **Log-scale y axis for runtime**: Agreed, a logarithmic plot will provide more information than the current format.\n\n3. **Discussion of the Structured-LNCDE Paper**: We became aware of the paper shortly after submission and thank the reviewer for bringing it up. We agree that it is very relevant related work and we now thoroughly engage with it through both experimental and theoretical claims, and accordingly made a benchmarking comparison with it (see above tables). Interestingly, the referenced work theoretically analyses sparse SSMs. The authors note that unstructured sparse SSMs do not provide any efficiency benefits over unstructured dense SSMs, and note that they anticipate that ongoing work on sparse matrices will enable future gains in efficiency. Our work exactly presents a structured sparse SSM with significant efficiency gains compared to unstructured variants.\n\n---\n\nOnce again, we thank the reviewer for their thoughtful feedback, which enabled us to substantially improve the paper, and hope that by addressing all their concerns, we can convince them to improve their score."}]

Author rebuttal:

Meta-review: In this paper, the authors propose PD-SSM, a new parametrization of transition matrices for selective state-space models. Instead of diagonal matrices (efficient but limited) or unstructured matrices (expressive but costly), PD-SSM represents transitions as the product of a column one-hot matrix (P) and a complex diagonal matrix (D). This keeps efficiency comparable to diagonal SSMs while allowing exact emulation of finite-state automata (FSA). The authors perform theoretical analysis to show expressivity guarantees and performance improvements, and experiments covering synthetic FSA tracking, natural-language encoded FSAs, and Long Range Arena benchmarks.

Initial reviews were broadly positive. Reviewers agreed that the parametrization is simple and theoretically grounded, and that the experiments support improvements in efficiency and expressivity (R-pBTL, R-DCmS). While some reviewers appreciated that the evaluation was already extensive, it was generally pointed out that the scope was still limited: R-pBTL questioned whether the FSA focus translates to broader domains such as NLP or vision, while R-DCmS noted the absence of language modeling results and said that claims about other approaches (e.g., RWKV) scaling poorly may have been overstated.

In the rebuttal, the authors added experiments on six multiclass time-series classification datasets with sequences up to 17k steps, showing PD-SSM performing better than prior SSMs. They also cited related work suggesting that improved expressivity grounded in FSAs can transfer to NLP and code generation tasks. For the point raised regarding the RWKV comparison, they offered clarification on scaling claims by distinguishing unstructured SSMs from Diagonal plus Low rank methods such as RWKV, and added more context on how their theoretical results compare to prior work. Reviewers were satisfied with these clarifications and maintained positive recommendations.

Overall, the paper presents a parametrization that expands the expressivity of SSMs while keeping efficiency, with extensive experiments and theoretical analysis backing up the claims. I recommend the paper be accepted, with the expectation that the final version will include the extended baselines, time-series results, and revised comparisons offered in the rebuttal.
Decision: Accept (spotlight)