DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products
Authors: Julien Siems
Timur Carstensen
Arber Zela
Frank Hutter
Massimiliano Pontil
Riccardo Grazzi
Venue: NeurIPS 2025 poster ()
Keywords: linear rnn
linear attention
state-space models
state-tracking
negative eigenvalues
householder
formal languages
regular languages
stability
finite-state automata
Primary area: deep_learning
TL;DR: We extend DeltaNet by using products of householders as state-transition matrices allowing us to trade-off expressivity and computational complexity.

Abstract: Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling, offering efficient training and linear-time inference. However, existing architectures face a fundamental trade-off between expressivity and efficiency, dictated by the structure of their state-transition matrices. Diagonal matrices, used in models such as Mamba, GLA, or mLSTM, yield fast runtime but have limited expressivity. To address this, recent architectures such as DeltaNet and RWKV-7 adopted a diagonal plus rank-1 structure, which allows simultaneous token and channel mixing, 
improving associative recall and, as recently shown, state-tracking when
allowing negative eigenvalues in the state-transition matrices.
Building on the interpretation of DeltaNet's recurrence as performing one step of online gradient descent per token on an associative recall loss, we introduce DeltaProduct, which instead takes multiple ($n_h$) steps per token. This naturally leads to diagonal plus rank-$n_h$ state-transition matrices, formed as products of $n_h$ generalized Householder transformations, providing a tunable mechanism to balance expressivity and efficiency. 
We provide a detailed theoretical characterization of the state-tracking capability of DeltaProduct in finite precision and how it improves by increasing $n_h$.
Our extensive experiments demonstrate that DeltaProduct outperforms DeltaNet in both state-tracking and language modeling, while also showing significantly improved length extrapolation capabilities.

DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products
Julien Siems* Timur Carstensen 94 Arber Zela Frank Hutter Massimiliano Pontil 9 Riccardo Grazzi
Equal contribution", University of Freiburg ELLIS Institute Tübingen* Microsoft Research Prior Labs CSML, Istituto Italiano di Tecnologia ? Al Centre, University College London
jullensieess@mail.cco
timurcarstensen@gaall. com #iccardograzzi148gaall. com
Abstract
Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling, offering efficient training and linear-time inference. However, existing architectures face fundamental trade- off between expressivity and efficiency, dictated by the structure of their state- transition matrices. Diagonal matrices, used models such as Mamba, GLA, or mLSTM, yield fast runtime but have limited expressivity. To address this, recent architectures such as DeltaNet and RWKV-7 adopted a diagonal plus rank- 1 struc- ture, which allows simultancous token and channel mixing, improving associative recall and, as recently shown, state-tracking when allowing state-transition ma- trices to have negative eigenvalues. Building the interpretation of DeltaNet's recurrence as performing one step online gradient descent per token on an asso- ciative recall loss, introduce DeltaProduct, which instead takes multiple (n₂) steps per token. This naturally leads to diagonal plus rank-nı, state-transition ma- trices, formed products of 7. generalized Householder transformations, pro- viding a tunable mechanism to balance expressivity and efficiency. We provide a detailed theoretical characterization of the state-tracking capability DeltaProd- uct in finite precision, showing how it improves by increasing Our extensive experiments demonstrate that DeltaProduct outperforms DeltaNet in both state- tracking and language modeling, while also showing significantly improved length extrapolation capabilities.
Introduction
The Transformer architecture [ has revolutionized natural language processing through its self- attention mechanism, enabling both parallel computation across the sequence length and effee- tive context retrieval. Consequently, Transformers have largely replaced recurrent models like LSTMs (2), which exhibit slower training and poorer retrieval performance. However, the quadratic computational complexity of Transformers with sequence length presents challenges when deal- ing with longer sequences. Linear RNNs have emerged a promising solution that combines parallel training across the sequence length with linear inference-time complexity. At the core of these models the state-transition matrices governing the recurrence, which fundamentally de- termine the expressivity of linear RNN B Early linear RNNs like S4 [4] and LRU [5] used token-ine indeepnnden sute-transition matrices. For superior expressivity, current linear RNNs now ex- clusively use token- dependent matrices. Among these Mamba (6, 77). GLA (8), and mLSTM [9] use diagonal trrnsstrrniiionn matrices for efficient sequence processing. Newer architectures have incorporated non non-diagonal structures, often diagonal plus rank- 1,, enabling simultaneous mixing of
Work started while at Istituto Italiano di Tecnologia.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Group Sg
CodeParrot
Figure 1: (Left) DeltaProduct, learns higher-order permutation groups like Ss in one layer, while DeltaNet (n,=1) is limited to S2 (parity). (Right Length extrap- olation of DeltaProduct improves significantly with higher n/-
1.0
3.6
DettaNie
Taken Loss
DellaPrdducty
Accuricy
3.1
DellaProducts:
0.5
3.2
3.0
0.0
0
200
400
1U96
16381
Sequence L Length
Sequence Length
information across both tokens and channels of the hidden state. This innovation has led to more ex- pressive models such as (Gated) DeltaNet [10 [1]. TTT-Linear [12), RWKV-7 [3]. and Titans (14), which demonstrate superior language modeling and in-context retrieval performance, often with only reasonable decrease in training efficiency.
Recent work has revealed a fundamental trade-off between training efficiency and expressivity of linear RNNs, dictated by the structure of their state-transition matrices [3] [3. [6]. Models with diagonal statettransition matrices, such as Mamba and GLA, are highly efficient train but face severe expressivity limitations for instance, they cannot perform addition modulo on sequences of arbitrary length in finite precision [66 Theorem 2]. Transformers also face similar limitations 17 18], since they can be seen special linear RNNs with state-transition matrix equal to the identity, albeit with an infinite dimensional state 19 DeltaNet partially overcomes these limitations through generalized Householder matrices, achieving greater expressivity. though it still requires multiple layers for some tasks, At the other extreme, linear RNNs with full state-transition matrices offer maximal expressivity 220, capable of recognizing any regular language with a single layer (3), but are prohibitively expensive to train.
To bridge this gap, we propose DeltaProduct. a method that balances expressivity and efficiency of the recurrence computation. While DeltaNet's recurrence performs single gradient descent step per token on the squared loss of a linear key-to-value mapping [TO] 211. DeltaProduct takes gradient steps using additional keys and values, yielding state-transition matrices that are products of n/, generalized Householder matrices. This connection between the number of optimization steps and the matrix structure provides an elegant way to interpolate between diagonal and dense matrices: increasing the number of gradient steps automatically increases the number of Householder matrices in the product, providing tunable mechanism to control the recurrence's s expressivity. DeltaProduct enables precise control over the norm of state transition matrices, ensuring it remains < to maintain stability during training on long sequences. We contribute DeltaProduct to the flsh--lieerr-ttenttie library (22). our experiment code is provided here
Concretely, we make the following contributions:
We propose (Gated) DeltaProduct, which generalizes (Gated) DeltaNet by using products of generalized Houscholder transformations as state- transition matrices (Section pp..
We provide detailed theoretical characterization of the expressivity of DeltaProduct in finite precision and how it improves by increasing n,, (Section 4.1. Notably, we prove that for any
nu > 1, DeltaProduct with at most 4 layers (3 if nı, 2) can solve any group word problem, and Gated DeltaProduct with a finite number of layers can recognize any regular language.
We empirically validate DeltaProduct's superior performance across multiple domains: solv- ing complex state-tracking tasks beyond DeltaNet's capabilities (see Figure I and improving language modeling performance with significantly enhanced length extrapolation (Section which we study through analysis of the hidden state's 's effective rank.
2 Background
Linear RNNs. Linear RNNs consist of stacked layers, each processing an input sequence of vectors
BIy..., y 3e R' (output of the previous layer) to produce an output sequence ÚI.... G. write the forward pass of each layer placing emphasis on the linear recurrence (as in [16]
IRP We
H. = A(x, H + B(x;),
ÿ. dec(H, xx))
where i E I,...,6
(1)
Ho E Raxd the initial hidden state, : TR. - RR maps the input to state-transition matrix, B R Baxd controls the information added to the new hidden state, and dee Rexd x
2

---

R' + I" determines the output of the recurrecce The functions A, B, and dec are learnable, with dec typically containing feedforward neural network. Different linear RNN variants are distinguished by their specific implementations of these functions. For example, Mamba G 7 GLA R and mL.STM [9] use variations of diagonal ttate-transition matrix Axx)) The linearity of the recurrence allows it to be parallelized along the sequence length, either via chunkwise parallel form 8 23 24] or using a parallel scan [6. 25H28)
For a comparison of different linear
RNN architectures see Yang et al. [10 Table 4].
DeltaNet. We base our work on the DeltaNet architecture 29 30
which has recently seen renewed
interest through the work of Yang et al. [0] III who demonstrate how to parallelize DeltaNet across the sequence length on GPUs The DeltaNet recurrence is parameterized as
Axx;) = I - 3.k,,'" B(x;)= = B,k,v," dec H,, x;) = v H q:)
(2)
where 8; E [0, 1], q;, k; E RR (with | ll = ||:l|| = 1), 0i IRd are outputs of learnable func- tions of x;. A(x;) is a generalized Householder transformation [1. which is symmetric and has eigenvalues (multiplicity n 1) and 1 - B, (multiplicity 1). From a geometric perspective, 3; determines the transformation type, interpolating between identity (3: = and projection (3, = 1). DeltaNet also has a natural interpretation from an online learning perspective [10). as each step of its recurrence is one step of online gradient descent on a quadratic loss with step size 3e:
(H = 1/2| k; - -2:12: H: = H - B, (H,, = H - 3g (kg H U,
DeltaNet: H, (I B,kkkk ) H,
+ B
State-Tracking and Word Problems. State-tracking is the ability of a model to keep track of the state of system while only observing the updates that are applied to it. can be modeled as a monoid word problem, which consists in mapping sequences .I...., Tt. with z; being an element of a monoid G, into sequences .1..... y/+, where y; = x; T;-1 ........ Iy and is the associative operation of the monoid. Recognizing a regular language can be accomplished by solving the word problem of a finite monoid associated to the language and will be the focus of this work. Problems where G is also group (group word problems) with finite elements, Transformers and linear RNNs. Group word problems for the symmetric or permutation groups subgroup of symmetric group. For
notoriously hard to solve for both
particularly important, since any group is isomorphic instance, if we denote with S, the group of permutations of n elements, parity corresponds to the S2 word problem, which cannot be solved in finite precision by Transformers [17] and diagonal Linear RNNs [15 with positive values, while the S5 word problem cannot be solved by these models even when the precision can grow logarithmically with the sequence length, since both Transformers and Linear RNNs belong to the TC" circuit complexity class while S₁ is in NC² E 18 32). In contrast, with unconstrained, full state-transition matrices any regular language can be recognized in one layer (see e.g. 3. Theorem 5.2]). However, training using full unstructured matrices is very inefficient and also unstable without any control on the norm.
3 Related Work
Linear RNNs have recently been studied from two main perspectives: state-space models and causal linear attention. State-space models, originating from continuous dynamical systems, inspired vari- ants such as S4
4 H4 (33], and LRU [5] (see Tiezzi et al. [34] for a comprehensive survey). Models
like Mamba 6 7 further enhance these by incorporating input-dependent gating mechanisms, sig- nificantly improving language modeling performance. In parallel, Katharopoulos et al. [9 showed that causal linear attention Transformers can be reformulated RNNs with linear sequence-length scaling. Following this, Gated Linear Attention (GLA) 8 introduced gating mechanisms similar to Mamba. Recent studies explored more expressive recurrences via non-diagonal transition ma- trices, such as DeltaNet [10] 29 355, TTT-Linear (12), RWKV-7 [33, B MOJO [36). and Titans 14] Additionally, Beck al. [9] introduced xLSTM, combining linear and nonlinear RNN archi- tectures inspired by LSTM (2). Another line of work explores recurrences in depth, which have been shown to increase the expressivity and reasoning capabilities [37 38 For instance, concurrent work explores how fixed-point iterations of diagonal linear RNN can increase its expressivity turning non-linear at the fixed-point [39 40 Unlike our approach, which enhances the expressivity by increasing the complexity of the linear recurrence, their approach works by applying the same recur- rence multiple times, effectively increasing the depth of the model without increasing the parameter count. This approach is orthogonal to ours and the two can be potentially combined.
3

---

Products of structured matrices [41] have previously been used in the state-update of non-linear RNNs- including (Givens) rotation matrices 44, Kronecker products 44). Householder reflec- tions 46 chosen for their orthogonal, norm-preserving properties that encourage long-term de- pendency learning 47 48). Recently, Biegun et al. [49] applied rotation matrices as traestran matrices in non-selective state-space models. In contrast, DeltaProduct uses a linear recurrence with state-transition matrices adaptive to the current token, expressed as products of generalized House- holder matrices.
State-Tracking. Recent work by Grazzi et al. demonstrates that expanding the eigenvalue range of linear RNNs' state transition matrices from [0, 1] to [-1,1] significantly enhances their expressivity. They show how DeltaNet's eigenvalue range can be extended from [o. 1] to [-1, 11,
simply by multiplying 3. by 2, allowing DeltaNet to perform reflections when & = 2. which enables to handle state-tracking tasks such as parity checking and, more generally, any group word problem where each element of the input sequence corresponds to permutation of at most two elements, while for other tasks, DeltaNet requires multiple layers [T6] Theorem 2 and 6]. Their theoretical results also cover the products of Householders used as state-transition matrices of DeltaProduct, showing that they allow to solve any group word problem in one layer (Theorem 3) and recognize any regular language (Theorem 4), when Tiy, is large enough and with finite number of layers. Here, we extend that work by providing experimental evidence of the benefit of larger n, and, leveraging the expressivity. e.g. with greatly improved dependency on 72,, The recent RWKV-7 [13] uses a state transition matrix of the form diag( w,) ck,, (k, @ a,) with ||,]| 1, a, w, [0, 1]" and e {1, which provides a potentially asymmetric rank-1 update in contrast to DeltaNet's symmetric update, allowing it to recognize any regular language with only 4 layers. However, the increased expressivity comes the cost of losing the guarantee on the stability of the recurrence. In contrast, (Gated) DeltaProduct has stable recurrence since the spectral norm of every state-transition matrix always S 1.
the analysis by Peng al. [13,, more refined theoretical results
DeltaProduct
While DeltaNet's recurrence can be seen as performing one step of online gradient descent per token, DeltaProduct builds upon DeltaNet by further refining the hidden state by taking multiple steps per token. This naturally leads to a more expressive trae-trrnnition matrix formed as a product of generalized Householder matrices, where each additional step expands the range of achievable linear transformations. Formally, for each input token 2; to the layer we generate n2 keys as kij
ab( W (W,,z)) n4 values as V.j5 Vjæ,, and n, betas as Bi,j ((U,æz;) where W,. Vj. Uj. are learnable weight matrices specific to the j-th gradient step, vb is a nonlinearity (we pick SiLU as in DeltaNet), while é is either the sigmoid or 2x the sigmoid increase the expressivity. Then, we compute nı gradient descent steps using the losses Li,(H) vi. ///2, i..., for j = 1. .1..
| k..
H Hij-1 V..,(HH.-)) Be H -1 + Beg
where Hio H and Hi,, H; Unrolling, we get H; A(m:) H:- + B(x;)) with
7hh
Rh.
A(x,) = II
I Be,s ki kT.) B(x,) = Σ
II
(I - k..kk,)) Bes key (3)
mm
An 3+1
Diagonal:
Rank 1 UUdate::
Rank ni Update:
Token Mix:
Channel Mix: x
Expressivity:
Parity Mamba, GLA
Reflections
Reflections, Rotations DeltaProduct
Examples:
DeltaNet, TTT, RWKV-7
Figure 2: Overview of state-transition matrices A(x;) in linear RNNs.

---

Hence, by taking multiple gradient descent steps per token, DeltaProduct's is state- transtrrnnstion matrices are products of generalized Householder transformations. and by expanding such a product, A (z;) takes the form of identity plus a matrix of rank at most n,, shown in Figure As DeltaNet extends [T], DeltaProduct can similarly be extended to
to Gated DeltaNet by incorporating a forget gate
Gated Delta Pedtutr by letting A (ax) = 9: II Th. (I- Big k.,) where the scalar gate 9. E [0, 1]
is adopted from Mamba 2 77 and B (xx;) remains unchanged. This formulation enables DeltaProduct to interpolate between generalized Householder (ny, = 1 as in DeltaNet) and dense matrices (of
norm < 1), since increasing nh can increase the rank of (2r;).
Expressivity of Householder products. While any state transition ma- trix of DeltaNet can model single Householder reflection (with 8, = 2), DeltaProduct's can model any orthogonal matrix. This is a consequence of the Cartan-Dieudonte theorem, which establishes that any X n or- thogonal matrix can be expressed as a product of at most n reflections (as illustrated in Figure for n = 2). The Householder product exhibits inter- esting properties in special cases. When all Householder keys are identical, the product simplifies to a single Householder with a scaled beta parameter, offering no additional expressivity (Prop. 1 Conversely, when the keys mutually orthogonal, the Householder product simplifies to identity plus a symmetric rank nA matrix (Prop. 2 Only when the keys are non- trivially linearly dependent can we obtain non-symmetric matrices, poten- tially yielding complex cigenvalues (Prop. 33). An important consequence of using Householder products that it allows us effectively bound the norm of A(x;). This is because the norm of the product is upper bounded by the product of the norms (each I 1), which ensures the stability of the recurrence [16, Prop. 1.1]. This bound would not be possible with the more direct parametrization Azx,) = - プラ= = Br ki which also restricts
H1
Ho
ko
x
k
20
x
Figure 3: Two reflec- tions produce a 2D rotation: Reflecting across planes Ho and H1 (with normals ko and kj) yields rota- tion by 20, where is the angle between the planes.
the matrix be symmetric.
4.1 State- Track-T Capabilities of (Gated) DeltaProduct
We present two theorems that characterize the state-tracking capabilities of DeltaProduct. Compared to Grazzi et al. [16] Theorem 3 and 4], we focus on results that hold for any n4 2 1. We defer proofs, and more details to Appendix [ where we also include results on dihedral groups (Theorem and on finite subgroups of the orthogonal and special orthogonal groups (Theorem
Theorem 1. For any n. N there exists DeltaProduct model with one of the following configu-
rations that can solve the word problem of the symmetric group Sn.' (i) one layer with ni, = nn-1
16 Theorem 3] (ä) 3 layers with n4>1 (iäi) 4 layers with na 1. The construction for (ii) and
(ii) requires that the MLP at the second last layer computes a lookup-table of size 2m x (n!)2m, function of the last 2m input tokens and the position modulo 2m with m =[n--)//ma
Theorem 2. For any nn 2 1 and any regular language, there exists Gated DeltaProduct model with a finite number of layers (dependent on the language) that recognizes it.
The proof for Theorem I uses the same idea as the construction for the theoretical results of Peng et al. [13 for RWKV-7. Each element of S, can be mapped to permutation matrix, but DeltaProd- uct's ' state transition matrices can only model permutations of up to n4 + 1 elements. Therefore,
7l + 1 < n, early layers decompose each product of m [n 1)/ra. consecutive permutations into m simpler permutations, which are applied in the recurrence of the last layer but in a delayed fashion. To get such a decomposition and account for the delay, the MIP at the second-last layer computes a potentially large lookup table, function of the past 2m tokens and the position modulo 2m. To prove Theorem 2 we use the Krohn Rhodes decomposition (50), similarly to Grazzi et al. [16 Theorem 4], where each automaton is decomposed into multiple permutation-resst automata, and model each using the same technique of Theorem I exploiting gates for the resets.
Comparison to other non-diagonal Linear RNNs. Table provides a comparison of the expres- sivity of different non-diagonal linear RNNs. (Gated) DeltaProduct with nA > 1 has improved expressivity compared to DeltaNet, and, up to 3 layers, even compared to RWKV-7 Moreover, increasing n4 has clear benefits: reducing the number of layers or the size of the lookup table. Since DeltaProduct can solve the S₃ word problem, it is outside of the TC" complexity class, just as RWKV-7. One might expect DeltaProduct to be able to model any useful state-transition matrix
5

---

Table 1: Expressivity of non-diagonal Linear RNNs shown through the formal language problems they can solve in finite precision. S.,. Z,, D,. are the symmetric, cyclic and dihedral groups of order n, while (nn) are the orthogonal and special orthogonal group of order n. For S., "only k-permutations" means that input sequences can contain only permutations of up to k elements. LS the size of the lookup table computed the second-last layer's ML.. |
and [Q] are the sizes of the alphabet and set of states of finite state automaton recognizing the regular language. Gated variants' state updates can also model constant (reset) transitions.
Layers (Gated) DeltaNet
RWKV-7
(Gated) DeltaProduct
Sn only 2-permutations.
Sn only 2-permutations
S, only (ma + 1)-permutt" Finite subgroups of O(mx),
SO(n, + 1) if na is even."
",D,D.' D'."
En. D..
S, with LS 2m (12))
where m = [(m m)/ma]
S, with LS 2(n - 1) x (n!)2(n-1)_
S, with LS as DeltaNet. Reg.
lang. with LS 2| (
f((Q)
Gated: Regular languages'
Gated: Regular languages'
16 Thm. 3]
16. Thm. 6]
TTmm.
Thm.
Thm. 3]
TThm. # TTh.
since it can model updates of arbitrarily high rank when nı, is equal to the number of rows of the hid- den state. This is because DeltaProduct's 's state-transition matrices A Axx;)) satisfy the spectral norm condition [|A())))] II ||X] (2;))Bll S 1, ensuring stable recurrence. RWKV-7 relaxes this constraint and can represent matrices with higher spectral norms. In particular, copy matrices identity matrices where one column is replaced by another with |I((xx;) = v2 (when e 2), allowing RWKV-7 to recognize any regular language in just four layers. However, this may lead to instability in the recurrence (see Appendix [. We could enhance expressivity the cost of stabil- ity by replacing the Householder matrices in DeltaProduct with RWKV-7's, state transition matrices. This modification enables us to prove a result analogous to Theorem D but for regular languages rather than group word problems- see Appendix [B.4 for details. Specifically, this approach allows the resulting linear RNN to recognize any regular language within a single layer, provided nip is sufficiently large.
Remark 1. For any regular language recognized by a sinite-state automaton (FSA) having n states there exists one layer linear RNN using ni = n products of RWKV-7 matrices state-transition matrices that can recognize it. This is because a linear RNN with unconstrained state-transition matrices can recognize any regular language in single layer 33 Theorem 5.2] by modeling FSA evaluation through matrix- vector products [57V. Peng et al. [13 Lemma 3] further showed that any transition matrix of an FSA with n states can be expressed as products of n matrices, each of which is either a swap, copy, or the identity matrix, all of which are representable by an RWKV-7 matrix.
The above discussion oulines a trade-off between the expressivity of RWKV-7 matrices and the guar- anteed stability of generalized Householders used DeltaProduct. It is an open question whether there exists continuous parameterization of state-transition matrices which yields stable recur- rences and still allows to recognize any regular language in a finite and fixed number of layers.
5 Experiments
We evaluate DeltaProduct on state-tracking and standard language modeling assess its expres- sivity and efficiency. Throughout the experiments we use either the suftix [-1, or [0, 1] after each method, to denote the eigenvalue ranges of its state transition matrices. We present additional
experiments on languages of different levels of the Chomsky hierarchy [52] in Appendix C.2
5.1 Implementation
We use the same macro architecture used by Gated DeltaNet. Since each step of (Gated) DeltaProd- uct follows the same recurrence structure as (Gated) DeltaNet, we can reuse its implementation written in Triton (53), available through the TTAASH-LINEAR-ATTEAN the chunk-wise parallel form for the recurrence.
library 22 which uses

---

Group Sg
Group S4
Group Ag
Group Ss
1.0
11
Accuracy
0.5
0.0
1.0
Accuncy
0.5
0.0
200
400
200
400
200
400
200
400
Sequence Length
Sequence Length
Sequence Length
Sequenoe Length
Figure 5: Accuracy state-tracking tasks for permutation groups S3. S4. As. and S5. plot- ted against sequence length (x-axis). (Top row) Varying the number of Householder products (Boltom row) Varying the number of layers I of DeltaProduct 1-1, L 1|/DeltaNet 1] (single Householder). Dashed vertical line at training con- text length 128. Higher ny improves extrapolation to longer sequences of permutations, e.g., S3 can be learned with nA = 2 with a single layer while three layers are required when keeping nt 1.
7% for single layer DeltaProduct,,, [- -Bottom
However, DeltaProduct differs by using nı, keys, values and be- tas per token, resulting in recurrence n, times longer than DeltaNet's. Therefore, we arrange keys (and similarly val- ues and betas) as [kr, ,i,,,, .2.1...., ... while for gating we construct the expanded sequence of gates as: [91, 1,..,,,.,,,, 1,99, 1,...,,,, .....] where each gate yi followed by - (m,-1) ones to match the number of keys and values, that we
n4
40K
Tokens per second (Ktis)
20K
use only one gate for each token. Once the recurrence is evalu-
40K
ated, we keep only every n4-th element of the output, so that the output sequence retains the same length as the input sequence.
20K
Throughput. The training (and prefill time) required for the
recurrence increases linearly with пy. since we use the same chunk size for the chunkwise parallel form. In contrast, since we keep the embedding dimension fixed, the cost for the MLP following the recurrence does not vary with nas To remedy the parameter-overhead introduced by the additional key and value projections due to increased 74. demonstrate the throughput when matching parameters in Figure 4 Matching parameters simply by scaling the head dimension is unfavorable (bottom subplot, nn 2) since head dimensions that are not a power of 2 will get padded the next power thereof, effectively giving up the remaining dimensions no reduction in runtime. See Appendix CC3.2 for additional results on smaller models. Note that if ri 1, could parallelize the recurrence have faster runtime also during autoregressive generation. Note that the throughput results are obtained using an optimized Triton kernel imple- mentation (developed by Songlin Yang and Yu Zhang, available in the Tash-linear-attention library) that achieves a 20% faster forward pass than DeltaNet's kernel.
16Kx1 8K*2 4Kx4 28x8 Training length Batch size Figure 4: Training throughput parameter matched 1.3B DeltaProduct on H100. Matched via: (Top) scaling the number of heads, (Bottom) scaling the head dimension.
5.2
State-Tracker
Setup. We evaluate DeltaProduct's ability to capture complex state dynamics using group word problems of increasing difficulty, specifically on the permutation groups S3. Sa, As, and Ss, as implemented by Merrill et al. [3]. These tasks consist in tracking how sequence of permutations rearranges elements. An intuitive parallel the shell game, where one needs to track the position of a hidden object after each shuffle. We train on sequences of 128 permutations and measure extrapo- lation up to 512. Throughout, we use the extended eigenvalue range, allowing eigenvalues [-1, 1]. We find that DeltaProduct models fail to learn even the training context-length when restricted to
7

---

the standard eigenvalue range [0. 1I, regardless of the number of Householder transformations n4, as shown in Figure [2] See Appendix for details on the experiments.
Single layer, varying nu. Figure 5 (top row) demonstrates the benefits of increasing the number of Householders R& per token for single layer DeltaProduct. Grazzi al. [16] Theorem 3] presents a construction for permutations of elements requiring n 1 Householders and keys of size n. In agreement, we find that for S3 achieving reliable performance beyond sequence lengths of 128 requires n 2, while Sţ needs n = 4. Unexpectedly, S4 and As can extrapolate robustly using only n4 = 2 despite the theorem suggesting and 4, respectively. This efficiency arises from their isomorphism to subgroups of S0(3, R), i.e. the group of 3D rotations, [54] Ch. 1, Sec. 2.4] which only require n,, = 2 and keys of size (see Theorem 4.. Specifically, S₃ is isomorphic to the rotation group of the cube (illustrated in Figure and A5 to the rotation group of the dodecahedron.
See Appendix C.T for details on the isomorphisms.
To empirically validate whether DeltaProducty(11 1, exploits the isomorphism S₃ to the rotation group of the cube, we verified two hypotheses: whether both Householders act as reflections (3,, -B,1
2) composing to form rotations (see Figure 3 and whether the keys are in a three- dimenssoaa subspace. By recording 3r,0 and B1 values (representing the first and second Householder in the product) across all 24 permutations of S4. we find that single head has indeed learned use both Householder transfor- mations as reflections where $1.0 3,1 = 2, ef-
90
2
4
3
Figure 6: Rotating cube permutes its di- agonals according the S4 group. This ex- ample shows how 90 rotation of the cube leads the 4-cycle
2 + 4 1).
fectively creating rotation matrices as shown Ap- pendix C.I This pattern is evident in Figure 7 (left), where this head predicts both 8i,0 and 1 approximately at 2. confirming that the model successfully learns to approximate rotations by com- bining two reflections. Note that the eigenvalues of the Houscholder product become complex in this case allowing it to perform rotations (Prop 3].. To further verify whether the keys are in a three-dimensional subspace, we apply Principal Component Analysis (55) to the key vectors of this head. The results in Figure 7 (right) demonstrate that three principal components account for over 95% of the variance in the key space. This finding strongly supports our theoretical understanding, as it indicates that the model primarily operates in a three-dimensional subspace, which aligns with the structure of SO(3, R..
Multiple layers, 7h = 1. The bottom row of Figure 5 explores the expressivity of multi-layered DeltaNer 11 (i.e. nn = 1). While increasing improves performance, it is
2.0
Cam, Explainal aaia Variance
1.8
0.75
layers with n4 less effective than increasing n,, and degrades length- extrapolation performance. Specifically, to fit the training context length, S3 required layers, S4 needed layers, and Aş required 3. For Ss. even 10 layers proved insufficient. This suggests that simply adding depth is less effective in practice than increas- ing ni. despite theoretical constructions showing that Sa can be solved with just layers (Theorem 7 and any group word problem can be solved with 4 Tayers (with a very wide MLP).
2.0
20
Pormutation Index
Num. Components
Figure 7: (Left) Estimated B values for DeltaProduetyl-L.1 on all permutations of Sg, clustering near 2 (reflection). (Right) PCA of key vectors shows that the first three components explain most of the vari- ance.
5.3 Language Modeling
Setup. We trained two model variants: DeltaProduct,,, [-1,, and Gated DeltaProduct,,, |- using the Web dataset [57]. We provide details about the training pipeline and hyperparameters in Appendix C.3.I To assess length extrapolation, we measured the cross-entropy loss beyond the training context length of 4096 tokens on CodeParrot [58] for coding, OpenThoughts 14k- Math (59 for math, and TriviaQA (60) for knowledge retrieval.
evaluated the models using language understanding, reasoning, and retrieval benchmarks from an-eval-harnes, [61), with task specifics Appendix C.3.3 C.333
Throughout our experiments we find that the training process remained
stable even as we increased 7ip (see Appendix C.3.4)
8

---

CodeParrot
Trivia QA
Open't I honghts 114K Math
2.50
Token Loes
3.1
2.75
3.0
2.70
3.0
2.9
2.9
2000
10000
15000
5000 10000
150m
2000
10000
15000
Sequence Length
Sequeence
Length
Sequenre Length
Deltaßes
DeltaProdurtz
DettaProdosts
Figure 8: Lenghh extrapolation results. Solid and dashed lines represent models with 8 and 12 heads respectively. Note that DeltaProducty|- 1] with 8 heads (392M parameters) matches the parameter count of DeltaNet (nA, = 1) with 12 heads (dotted line), while achieving significantly better length extrapolation. For each index of the sequence, we report the moving average over 501 tokens as suggested by Lin et al. [56]
DelteProduct,
DottaNet-11. 111]
GatedDelaaProdet,
GatedDeltaNef 1.]]
Effecctive Rank
-50
50
60
.00
40
20
20
30
30
10000
10000
10000
10000
Sequence Length
Sequence Length
Sequence Length
Sequence Length
Figure 9: Effective rank of H; for 4 of 8 heads in layer 20/24 on trivia-qa sequences. Solid vertical lines mark new question-answer pairs; dashed vertical line indicates 4096-token training context length; colored lines show effective rank per head over the sequence.
Length extrapolation results. Remarkably, as shown in Figure g DeltaProduct's length extrapola- tion performance increases sharply when going from one to two Householders, and at nt = 3, the performance degradation is minimal across the sequence length. We hypothesize that DeltaProduct achieves better length extrapolation by enhancing DeltaNet's 's forgetting mechanism. While DeltaNet requires n rank-l updates to reset its state to zero, DeltaProduct can accelerate this forgetting process by factor of nu. However, our experiments show that DeltaProductz [-1, 1] still performs better with a forget gate, as demonstrated by its improved results when compared to the non-gated version (see Appendix C.3.5).
Analyzing state dynamics through effective rank. To test our hypoth- esis towards a better forgetting mechanism, we compare how the infor- mation density of the hidden state H, changes over time for (Gated) DeltaProductsl-1) 1] and (Gated) DeltaNet[ 1]. We propose to mea- sure the information density of H, using its effective rank [62] defined as erank( H.) exp(- Σx & Pk: Px), where Pk ok/ Σ, aT and σ; is the i-th singular value of H, which satisfies S crank(H, I rank H.). Note that Parnichkun et al. [63] also used the effective rank in the context of linear RNNs, but measured on a different quantity: a linear operator associ- ated to the recurrence. Similarly, Peng et al. 13 conducted an interpretabil- ity study on the hidden state of RWKV-7 using the average stable rank (64] we present the effective rank of DeltaProducts,
16:
Delaoee
Perplexity
12:
200M 400M
800M
Parameters
across layers. In Figure 9 Gated DeltaProduct3. Gated DeltaNet, and DeltaNet across a sequence of tokens from the TriviaQA dataset, which consists of dnestion-answer pairs that test common knowledge. We observe that some heads of DeltaProduct learn to update their state with new information at the beginning of sequence (BOS) tokens and then decay over the rest of the sequence. In comparison, a few heads of Gated DeltaNet and Gated DeltaProduct learn reduce the effective rank of the hidden state close to zero after each BOS token, while the other heads maintain a very low effective rank throughout the sequence, In contrast, DeltaNet's effective rank increases substantially beyond the training context. We attribute DeltaNet's inability to extrapolate to longer sequences to this issue, as the training and extrapolation regimes differ, resulting in a distribution shift. We present additional results for other layers and the CodeParrot dataset in Appendix C.3.5
Figure 10: Scaling analysis w.r.t. (top) final perplexity on Fine Web, (bottom) Lambada and Im-eval tasks.

---

Scaling Analysis. We test whether it is favorable to increase model size through Householder prod- ucts as opposed to increasing model capacity through e.g., the head dimension. We adjust either the head dimension in DeltaNet, or the number of Householder products (nr)) in DeltaProduct to reach a given size. Figure TO (top) shows that DeltaProduct scales better in terms of training perplexity. The results on im-eval-harness tasks, in Figure [0] (bottom), reinforce our findings as DeltaProduct maintains its performance advantage at the largest scale. In total, we test two methods to reach pa- rameter equivalence at each model scale: scaling the number of heads or the head dimension. We find that the latter shows more consistent scaling. Results for scaling the number of heads can be found in Appendix C.3.6 In Appendix C.3.3 report additional results, including gated variants, where we find that both DeltaProduct and Gated DeltaProduct on average outperform their baseline counterparts (DeltaNett-11/ 1] and Gated DeltaNet|- 1]) across the considered language model- ing benchmarks from Im-eval harness when we increase T4- Interestingly. DeltaProducts(-1, achieves comparable performance Gated DeltaNet(-1 1), despite lacking a forget gate.
Conclusion and Future Work
We present DeltaProduct, an extension of DeltaNet that uses products of Householder transfor- mations as state-transition matrices. Our approach bridges the gap between structured and dense matrices, with each recurrence step interpretable as multiple steps of gradient descent on an as- sociative recall loss (compared to DeltaNet's single step). The number of Householder matrices (n₂) serves as a tunable parameter balancing expressivity and computational efficiency. Our ex- periments demonstrate DeltaProduct's 's superior performance over DeltaNet in state tracking, formal language recognition, and language modeling, with particularly strong length extrapolation results. DeltaProduct represents a promising step towards developing sequence models that are more capa- ble while still remaining scalable. Limitation. The main limitation of DeltaProduct is its increased computational cost, which scales linearly with n, during training. Future Work. Future research could explore more expressive and possibly stable matrix parameterizations or an adaptive version of DeltaProduct determining the number of Householders per token similar to Graves (65) in der to reduce computation. The additional parameters introduced with higher TA,, could be reduced through LoRA MLPs done in RWKV-7 [13.. In addition, one could combine DeltaProduct with fixed point RNNs [39, 40). Our DeltaProduct implementation could be further optimized through custom kernels as suggested in the recent works by Cirone and Salvi (66) or Beck al. [67]. We also identify promising applications for DeltaProduct in reasoning tasks, where the higher token counts align well with the strength of linear RNNs. Given that state-tracking benefits reasoning tasks (39].
future work should examine how increasing 7i, affects reasoning.
A Acknowledgements
We would like to thank Songlin Yang, Eddie Bergman, Arjun Krishnakumar, Alma Lindborg, and Julie Naegelen for constructive discussions and feedback. We acknowledge the support and as- sistance of the Data Science and Computation Facility and its Support Team, in particular Mat- tia Pini, in using the IIT High-Performance Computing Infrastructure, on which we run part of our experiments. This research was partially supported by the following sources: PNRR MUR Project PE000013 CUP J53C22003010000 "Future Artificial Intelligence Research (FAIR)", funded by the European Union NextGeneration and EU Project ELSA under grant agreement No. 101070617. TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215; the Deutsche Forschungsgemeinschaie (DFG. German Research Foundation) under grant number 417962828; the European Research Council (ERC) Consolidator Grant 'Deep Learning 2.0' (grant no. no. 10). This research was partially funded by the Deutsche Forschungsgemein- schaft (DFG, German Research Foundation) under grant number 539134284, through EFRE (FEIH 2698644) and the state of the Hector Foundation. The authors acknowledge support from ELLIS and ELIZA. Funded by the European Union The authors gratefully acknowledge the computing time made available to them on the pirh-ppeffrmmacc computers and at the NHR Centers at TU Dresden and KIT. These centers are jointly supported by the Federal Ministry of Research, Technology and Space of Germany and the state governments participating in the NHR. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the ERC. Neither the European Union nor the ERC can be held responsible for them.
Frank Hutter acknowledges financial support by
Baden-V/urteembrg
Co-funded by European Unior
10

---

References
[1] A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L. Jones, A. Gomez, L. Kaiser, and Polo- sukhin. Attention is all you need. In I. Guyon, U. von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Proceedings of the 31st International Conference Advances in Neural Information Processing Systems (NeurIPS 17). Curran As- sociates, Inc., 2017.
[2] Sepp Hochreiter and Jürgen Schmidhuber. Long Short-Term Memory. Neural Computation, 9 (8):1735-1780, 1997.
[3] W. Merrill, Petty, and A. Sabharwal. The Illusion of State State-Space Models. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning (ICML volume 251 of Proceedings of Machine Learning Research. PMLR, 2024.
[4] A. Gu, K. Goel, and C. Re. Efficiently Modeling Long Sequences with Structured State Spaces. In The Tenth International Conference on Learning Representations (ICLR'22). ICLR, 2022.
[5] A. Orvieto, S. L. Smith, A. Gu, A. Fernando, C. Gulcehre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In A. Krause, Brunskill, K. Cho, B. Engel- hardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning (ICMI. 23), volume 202 of Proceedings of Machine Learning Research. PMLR, 2023.
[6] Albert Gu and Tri Dao. Mamba: Linear- Time Sequence Modeling with Selective State Spaces. In First Conference on Language Modeling, 2024.
[7] T. Dao and A. Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Con- ference on Machine Learning ([CML'24) volume 251 of Proceedings of Machine Learning Research. PMLR, 2024.
[8] S. Yang, B. Wang. Y. Shen, R. Panda, and Y. Kim. Gated Linear Attention Transformers with Efficiar-EEffcieett Training. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41 International Conference on Machine Learning (ICMI. 224), volume 251 of Proceedings of Machine Learning Research. PMLR, 2024.
[9] M. Beck. K. Pöppel, M. Spanring. A. Auer, O. Prudnikova, M. Kopp, G. Klambauer, J. Brand- stetter, and S. Hochreiter. XLSTM: Extended Long Short-Term Memory. In A. Globerson, I. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Proceedings of the 37th International Conference on Advances in Neural Information Processing Systems (NeurIPS'2 24), 2024.
[10] S. Yang. Wang. Y. Zhang, Y. Shen, and Y. Kim. Parallelizing Linear Transformers with the Delta Rule over Sequence Length. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Pa- quet, Tomezak, and C. Zhang, editors, Proceedings of the 37th International Conference on Advances in Neural Information Processing Systems (NeurIPS 244), 2024.
[11] S. Yang, J. Kautz, and A. Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. In The Thirteenth International Conference on Learning Representations (ICLR'25) ICLR, 2025.
[12] Y. Sun, X. Li, K. Dalal, J. Xu, A. Vikram, G. Zhang, Y. Dubois, X. Chen, X. Wang, S. Koyejo, T. Hashimoto, and C. Guestrin. Learning to (lear at test time): RNNs with expressive hidden states. arXiv:2407 00000000000 [cs. 2024.
[13] Bo Peng, Ruichong Zhang, Daniel Goldstein, Eric Alcaide, Haowen Hou, Janna Lu, William Merrill, Guangyu Song, Kaifeng Tan, Saiteja Utpala, Nathan Wilce, Johan S. Wind, Tianyi Wu, Daniel Wuttke, and Christian Zhou-Zheng. RWKV-7 "Goose" with Expressive Dynamic State Evolution, 2025.

---

[14] Ali Behrouz, Peilin Zhong, and Vahab Mirrokni. Titans: Learning to memorize at test time. arXiv preprint arXiv:2501.0066. 2024.
[15] Y. Sarrof, Y. Veitsman, and M. Hahn. The Expressive Capacity of State Space Models: A Formal Language Perspective. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang, editors, Proceedings of the 37th International Conference on Ad- vances in Neural Information Processing Systems (NeurIPS 24), 2024.
[16] R. Grazzi, Siems, A. Zela, J. Franke, F. Hutter, and M. Pontil, Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. In The Thirteenth International Conference Learning Representations (ICLR 25). ICLR, 2025.
[17] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transac- tions of the Association for Computational Linguistics, 8:156-171, 2020.
[18] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
[19] A. Katharopoulos, Vyas, N. Pappas. and F. Fleuret. Transformers are RNNs: Fast Autore- gressive Transformers with Linear Attention. In H. Daume III and A. Singh, editors, Pro- ceedings of the 37th International Conference on Machine Learning (ICMI. 20), volume 98. Proceedings of Machine Learning Research, 2020.
[20] N. M. Cirone, A. Orvieto, B. Walker, C. Salvi, and T. Lyons. Theoretical Foundations of Deep Selective State-Space Models. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Pa- quet, J. Tomezak, and C. Zhang, editors, Proceedings of the 37th International Conference on Advances in Neural Information Processing Systems (NeurIPS'24) 244) 2024.
[21] Ke Alexander Wang, Jiaxin Shi, and Emily B Fox. Test-time regression: A unifying framework for designing sequence models with associative memory. arXiv preprint 12X:v 2025.
[22] Songlin Yang and Yu Zhang. FLA: A Triton-Basee Library for Hardware-Efficient Imple- mentations of Linear Attention Mechanism, January 2024. URL ltttps///github. com/ sustcsonglin/ flash- meiss-linearrs cemearr-atentioo
[23] W. Hua, Z. Dai, H. Liu, and Q. Le. Transformer quality in linear time. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning (ICMI/22), volume 162 of Proceedings of Machine Learning Research. PMLR, 2022.
[24] Yutao Sun, Li Dong, Shaohan Huang. Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang, and Furu Wei. Retentive network: A successor to transformer for large language models. arXiv preprint 20Xiv:2307.08621, 2023.
[25] Guy E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, 1990.
[26] E. Martin and C. Cundy. Parallelizing Linear Recurrent Neural Nets Over Sequence Length. In The Sixth International Conference on Learning Representations (ICLR' 18). ICLR, 2018.
[27] Smith, A. Warrington, and S. Linderman. Simplitied State Space Layers for Sequence Modeling. In The Eleventh International Conference on Learning Representations ([CLR'23) ICLR, 2023.
[28] Ting- Han Fan, Ta-Chung Chi, and Alexander Rudnicky. Advancing Regular Language Rea- soning in Linear Recurrent Neural Networks. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), pages 45-53, 2024.
[29] I. Schlag, K. Irie, and Schmidhuber. Linear transformers are secretly fast weight program- mers. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning (ICMI.21), volume 139 of Proceedings of Machine Learning Research. PMLR, 2021.
12

---

[30] I. Schlag, T. Munkhdalai, and J. Schmidhuber. Learning Associative Inference Using Fast Weight Memory. The Ninth International Conference on Learning Representations (ICLR ICLR, 2021.
[31] Alston S Householder. Unitary triangularization of a nonsymmetric matrix. Journal of the ACM (JACM), 5(4):339-342, 1958.
[32] B. Liu, J. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers Learn Shortcuts to Automata. In The Eleventh International Conference on Learning Representations (ICLR'23) ICLR, 2023.
[33] D. Fu, T. Dao, K. Saab, A. 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' 23)). ICLR, 2023.
[34] Matteo Tiezzi, Michele Casoni, Alessandro Betti, Tommaso Guidi, Marco Gori, and Stefano Melacci. Back to recurrent processing at the crossroad of transformers and state-space models. Nature Machine Intelligence, may 2025. ISSN 2522-5839. doi: 10. 10.00888/42256--25500044--
[35] Kazuki Irie, Róbert Csordás, and Jürgen Schmidhuber. Practical computational power of linear transformers and their recurrent and self-referential extensions. In The 2023 Conference Empirical Methods in Natural Language Processing, 2023.
[36] L. Zancato, A. Seshadri, Y. Dukler, A. Golatkar, Y. Shen, B. Bowman, M. Trager, A. Achille, and S. Soatto. B B'MOJO: Hybrid State Space Realizations of Foundation Models with Eidetic and Fading Memory. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tom- czak, and C. Zhang, editors, Proceedings of the 37th International Conference Advances in Neural Information Processing Systems (NeurlPS' 24), 2024.
[37] D. Mostafa, G. Stephan, V. Oriol, J. Uszkoreit, and L. Kaiser. Universal Transformers. In The Seventh International Conference on Learning Representations (ICLR' 19). ICLR, 2019.
[38] Jonas Geiping, Sean McLeish, Neel Jain, John Kirchenbauer, Siddharth Singh, Brian R Bar- toldson, Bhavya Kailkhura, Abhinav Bhatele, and Tom Goldstein. Scaling up test-time com- pute with latent reasoning: A recurrent depth approach. arXiv preprint arXiv:2502.05171, 2025.
[39] Mark Schöne, Babak Rahmani, Heiner Kremer, Fabian Falck, Hitesh Ballani, and Jannes Gladrow. Implicit Language Models are RNNs: Balancing Parallelization and Expressivity. arXiv preprint arXiv:2502.07822 2025.
[40] Sajad Movahedi, Felix Sarnthein, Nicola Muca Cirone, and Antonio Orvieto. Fixed-point RNNs: From diagonal to dense in a few iterations. In First Workshop on Scalable Optimization for Efficient and Adaptive Foundation Models, 2025.
[41] Matthias Kissel and Klaus Diepold. Structured matrices and their application in neural net- works: A survey. New Generation Computing, 41(3):697-722. 2023.
[42] Victor D. Dorobantu, Per Andre Stromhaug, and Jess Renteria. DizzyRNN: Reparame- terizing Recurrent Neural Networks for Norm-Preservee Backpropagation. arXiv preprint arXiv:1612.04000 04035, 2016.
[43] L. Jing, Y. Shen. T. Dubcek, J. Peurifoy, S. Skirlo, Y. LeCun, M. Tegmark, and M. Soljacic. Tunable Efficient Unitary Neural Networks (EUNN) and their application to RNNs. In D. Pre- cup and Y. Teh, editors, Proceedings of the 34th International Conference on Machine Learn- ing (ICML' 17), volume 70. Proceedings of Machine Learning Research, 2017.
[44] Rumen Dangovski, Li Jing, Preslav Nakov, Mićo Tatalović, and Marin Soljačić. Rotational unit of memory: novel representation unit for mns with scalable applications. Transactions of the Association for Computational Linguistics, 7:121-138, 2019.
[45] C. Jose, M. Cisse, and F. Fleuret. Kronecker recurrent units. In J. Dy and A. Krause, edi- tors, Proceedings of the 35th International Conference on Machine Learning (ICML. 18), vol- ume 80. Proceedings of Machine Learning Research, 2018
13

---

[46] Z. Mhammedi, A. Hellicar, A. Rahman, and J. Bailey. Efficient orthogonal parametrisation of
recurrent neural networks using householder reflections. In D. Precup and Y. Teh, editors, Pro- ceedings of the 34th International Conference on Machine Learning (ICMI. 17), volume 70. Proceedings of Machine Learning Research, 2017.
[47] Sepp Hochreiter. Untersuchungen zu dynamischen neuronalen netzen. Diploma, Technische Universität München, 91(1):31, 1991.
[48] Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
[49] Kai Biegun, Rares Dolga, Jake Cunningham, and David Barber. RoIRNN: Modelling Long Sequences with Rotations. arXiv preprint arXiv:2407.0722:: 2024.
[50] Kenneth Krohn and John Rhodes. Algebraic theory of machines. i. prime decomposition theo- rem for finite semigroups and machines. Transactions of the American Mathematical Society, 11::450-464, 1965.
[51] Anil Nerode. Linear automaton transformations. Proceedings of the American Mathematical Society, 9(4):541-544 1958.
[52] 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 Hi- erarchy. In The Eleventh International Conference on Learning Representations (ICLR'23).
ICLR, 2023.
[53] Philippe Tillet, Hsiang-Tsung Kung, and David Cox. Triton: An intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pages 10-19, 2019.
[54] Yvette Kosmann Schwarzbach. Groups and symmetries from finite groups to lie groups, 2010.
[55] Karl Pearson. LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2(11):559-577 1901.
[56] Zhixuan Lin, Evgenii Nikishin, Xu Owen He, and Aaron Courville. Forgetting transformer: Softmax attention with forget gate. arXiv preprint arXiv:2503.02133 2025.
[57] Guilherme Penedo, Hynek Kydlíček, Loubna Ben allal, Anton Lozhkov, Margaret Mitchell, Colin Raffel, Leandro Von Werra, and Thomas Wolf. The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale, 2024.
[58] Lewis Tunstall, Leandro Von Werra, and Thomas Wolf. Natural Language Processing with Transformers. O'Reilly Media, Inc., 2022.
[59]
OpenThoughts Team. Open Thoughts. https:/open January 2025.
[60] Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1601-1611, 2017.
[61] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding. Jeffrey Hsu, Alain Le Noac"h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf, Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang. Kevin Wang, and Andy Zou. A frame- work for fhw-shot language model evaluation, 07 2024.
[62] Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In 2007 15th European signal processing conference, pages 606-610. IEEE, 2007.
[63] Rom N Parnichkun, Neehal Tumma, Armin W Thomas, Alessandro Moro, Qi An, Taiji Suzuki, Atsushi Yamashita, Michael Poli, and Stefano Massaroli. Quantifying Memory Utilization with Effective State-Size. arXiv preprint arXiv:2504 19561, 2025.
14

---

[64] Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric functional analysis. Journal of the ACM (JACM), 54(4):21-es, 2007.
[65] Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.0899, 2016.
[66]
Nicola Muca Cirone and Cristopher Salvi. ParallelFlow: Parallelizing Linear Transformers via Flow Discretization. arXiv preprint #XXv:2504.00492 2025.
[67] Maximilian Beck, Korbinian Pöppel, Phillip Lippe. and Sepp Hochreiter. Tiled Flash Linear Attention: More Efficient Linear RNN and xLSTM Kernels. ICLR 2025 Workshop on Foundation Models in the Wild, 2025.
[68] Robert Schreiber and Beresford Parlett. Block reflectors: Theory and computation. SIAM Journal on Numerical Analysis, 25(1): 205, 1988.
[69] Joseph Gallian. Contemporary abstract algebra. Chapman and Hall/CRC, 2021.
[70] Lorraine L Foster. On the symmetry group of the dodecahedron. Mathematics Magazine, 63 12):066-177, 1990.
[71] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In The Seventh Interna- lional Conference on Learning Representations (ICLR'19) 19). ICLR, 2019.
[72] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Yang, Z. Vetito, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, L. Fang. J. Bai, and S. Chintala. Pytorch: An imperative style. performere deep learning library. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alche Buc, E. Fox, and R. Gamett, editors, Proceedings of the 32nd International Confer- ence on Advances Neural Information Processing Systems (NeurIPS 19). 2019.
[73] I. Loshchilov and F. Hutter. SGDR: Stochastic gradient descent with warm restarts. In The Fifth International Conference on Learning Representations (ICLR' 17). ICLR, 2017.
[74] J. Proto-Kaaufman, A. R. Loftus, E. Todd, J. Brinkmann, K. Pal, D. Troitskii. M. Ripa, A. Belfki, C. Rager, C. Juang, A. Mueller, Marks. A. Sen Sharma, Lucchetti, N. Prakash, C. BBoodley A. Guha, J. Bell, B. C. Wallace, and D. Bau. Nnsight and ndif: Democratizing access to foundation model internals. The Twelfth International Conference on Learning Representations (ICLR'244 ICLR, 2024.
[75] Fabian Pedregosa, Gaøl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning Python. the Journal of machine Learning research, 12:2825 28300, 2011.
[76] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. Zero: Memory opti- mizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-16. IEEE, 2020.
[77] Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc-Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The LAM-
BADA dataset: Word prediction requiring broad discourse context. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pa- pers), pages 1525-1534, 2016.
[78] Yonatan Bisk, Rowan Zellers, Ronan Le bras, Jianfeng Gao, and Yejin Choi. PIQA: Reasoning about physical commonsense in natural language. Proceedings of the AAAI Conference Artificial Intelligence, 34(05):7432-743, Apr. 2020.
[79] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. HellaSwag: Can a Machine Really Finish Your Sentence? Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4791-4800, 2019.
15

---

[80] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
[81] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? Try are, the ai2 reasoning challenge. arXiv preprint arXiv:1803.0544 2018.
16

---

Supplementary Material
The supplementary material is structured as follows:
Appendix A presents a proposition that provides special cases of the generalized Householder prod- for specific choices of keys and betas and characterizes the spectrum of the product of two generalized Householders.
Appendix B characterizes the expressivity of DeltaProduct.
B. demonstrates how DeltaProduct can solve any group word problem in single layer when nı, is sufficiently high, or alternatively using up to 4 layers when n, is limited.
B.3 shows how DeltaProduct can recognize any regular language in finite number of layers using the Krohn-Rhodes decomposition.
B.4 details the expressivity of a linear RNN with products of RWKV-7 state-transition matrices.
B.5 demonstrates how DeltaNet can solve any dihedral group in 2 layers using a specific construction.
B.6 discusses the tradeoff between expressivity and stability linear RNNs.
Appendix C provides comprehensive details experiments and additional results.
We provide the code for our experiments at http:////ggaauu...oo/ttttt//////
Notation, Mathematical objects are typically styled as follows. Matrices: uppercase letters (e.g.. A, H, M). Vectors: lowercase letters (e-g., k. v. at). Standard sets: R for reals, C for complexes, N for naturals. Common symbols and operations are denoted as follows. I: Identity matrix. T: Transpose operator (e.g., ke )).. ||/||| or ||v||2: Euclidean norm of vector |A]l: the operator norm for a matrix A. |: Absolute value for real scalars, or modulus for complex numbers. o: Element-wise (Hadamard) product. (A), p)A): Spectrum (set of eigenvalues) and spectral radius of matrix A. tr( A), det (A): Trace and determinant of matrix A. dzy: Kronecker delta (1 if j. otherwise). e; E {0, 1]"h is the i-th element of the canonical basis of R
A Spectral Properties and Simplifications of Householder Product Matrices
The following proposition characterizes conditions under which the product structure simplifies and the spectrum is real, contrasting with the general case which allows for complex spectra. It provides illustrative special cases for the more general Proposition
Grazzi et al. [16].
Proposition Let A E Raxx be matrix defined as the product of nz 2 generalized House-
holder transformations: A 1 nh.. H, where each H, = I- Byk,k], with kj E IR" being unit vector (1ik,l22 and B5 [0. Let ((A) C. C denote the spectrum (set of eigenvalues) of A. Then, all eigenvalues E (A) satisfy [A| S 1 and the following hold.
1. (Identical Direction Vector) Let l R" be nonzero and k; k// [[k]] all 1.m. Then IT -1 kk -- kk" for some real scalar 3 depending on {3) The product collapses to a single effective transformation of the same form. Consequently, if A is formed using only a single direction vector k1, it is symmetric and its spectrum is real.
2. (Orthogonal Vectors) If the direction vectors [k3} form an orthonormal set (i.e., kjj ki 8 this requires nú, Σ n), then the factors H2 commute, and the product simplifies to A
- -, k This matrix A is symmetric, and its spectrum is purely real: o(A) =
{1 - 1 3m, U (1 (multiplicity n - -mn)), When 35- = 2 for all j E {l,... T then
A known as a block reflector (68).
3. (Complex Spectrum via Non-orthogonal Directions) For n4, 2, has complex eigenvalues
if two consecutive direction vectors, e.g. k1, K2 satisfy 0 < [k k2 < 1 and their coefficients 31 32 exceed threshold (0) dependent on the angle between them. Conversely, if 5 31 < 1 or 0 S B2 < 1, these eigenvalues from the 2D span are guaranteed to be real.
Proof. Identical Direction Vector If m 1, then the statement is trivially satisfied with /8- B1- B3 kk I ((mm kk." .Multiplynng by
Suppose the statement is true for 2 1, i.e., II"
17

---

6:000'
6HTS'
88150
6-22.5
00:30
88337.5
00:5.00
0852.5
0=:00"
0R:67.5
0::75.0
8::90.0
2
0
20
B1
Figure 11: Visualization of complex eigenvalues of 1- (I- -1-kkkk))))))) with cos = ki K2- Complex region in red, real in white.
(I-8m+1 kk produces (I- kk (I-))(Immett kk 1-
- +8m+1-
Sm++1 kk
Hence, by induction, the product of any number of such factors remains of the form I kk Since the resulting matrix A I - 3 kk (where ks = ki) is symmetric, its eigenvalues are real.
Orthogonal Vectors Assume { is orthonormal set (kj Kj 651. ni I n). Let Pj
for j + 1. The product simplifies via induction to A = در= 33 P,. This matrix is symmetrie. Its cigenvalues are (1 3:) for / = I,..., r& (eigenvector k.) and with multiplicity π TRA (subspace orthogonal all k,). The spectrum is real.
kyk Then P,P. = 6, The factors H, I 3, P3 commute because P,P.
Complex Spectrum via Non-orthogonal Directions and Real Subcase Let k1, k2 span 2D sub- space S C IR" with cos & k lo2 such that 0 < cos 0 1. The product A = H2 acts as the identity on S (preserving
eigenvalues at 1) and non-trivially on S. The restriction As of A to S has trace tr (As) = 2 - 31 - B2 + 313, cos? 0 and determinant det (As) = 31) B2). The discriminant of its characteristic equation is D [tr( det As). Complex eigenvalues arise < O.
To find the explicit bounds, we expand the inequality D < 0:
(2 B1 - + 81 cos² 0)² - 4(1 - 81)(1 (2) <0
Rearranging this expression as quadratic in r = cos² 0 yields:
(3) + 2(2 31 --233,35 + (31 B3)= 0
This inequality holds if and only if æ = cos² 0 lies strictly between the two roots of the correspond- ing equation. Solving for the roots gives the explicit bounds for complex eigenvalues:
(VB)
32
(VB) V B3
< cos²
3132
3182
This inequality is only satisfiable when 31, E (1,2). For the special case two standard reflec- cos² f 1, confirming that the product of
tions where B1 32 2, the condition simplifies any two distinct reflections is a rotation.
Conversely, show that if at least one coefficient B; E [0, 1]. the eigenvalues are real as D > 0. We analyze this by cases:
Case 1: One coefficient is in [0, 1), the other in (1,2). Without loss of generality, let B1 E [0.
and 32 E (1, This implies (1 - B1)) 2 and (1- (B)) < 0, so their product det(As, < 0. The term det((AA) is therefore neg-negative. Since [tr(As)]² 0, their sum must be non-negative.
Case 2: Both coefficients are in [0,1]. By the AM-GM inequality on the non neg-negative terms
(1 (1) and (1 82), we have (1 11-$8 3:) + (1 (2) 2 2/(1 31)(1 32) 2 (As). Since tr(As) includes an additional non nen-negative term 3,3, cos? 6. also holds that tr(As) Z
(3))
2 / (ess). Squaring both sides gives [ir(A [s] > 4 dAs) ensuring 2 0.
This analysis confirms that complex eigenvalues, which enable rotations, can only arise and only if both 81 > and B2 > 1. When at least one 8g < 1, real eigenvalues restrict the transformations that subspace to scaling or reflection. This clear distinction behavior, dictated by the values and 0, is illustrated in Figure II
18

---

B Expressivity of DeltaProduct
In this section, we characterize the expressivity of (Gated) DeltaProduct in solving group word problems and recognizing regular languages. in support of Section 4.1 The results hold in finite precision (since our constructions require a finite number of values), and take inspiration from Peng et al. [13] Appendix D] and [6]. We begin by stating and discussing our key assumptions in Ap- pendix B.1] We then present our main results for group word problems in Appendix [.2] followed by our findings for regular languages in Appendix [.3 In Appendix B.5 we examine a result specific to dihedral groups. Finally, we explore the fundamental tradeoff between expressivity and stability of the recurrence in Appendix B.6
B.1 Assumptions
We consider a (Gated) DeltaProduct model where each layer is structured as
where i E I...., H,- ( + B(ar)), D. dec( H4, 224)
Th
A(x.) 9: II - Bi, kegkii, kig B(x,)
Σ
πI (I k=j+1
(1, 3i, ki Big kag
where 9i is only present in the gated variant and there only one head per layer. If H heads are considered, head will run the recurrence H:- = A' (H; + B (a:)). (with different learnable parameters from all other heads) and all the states will be passed to the decoder to get the output as D, = dec(( (H) ...., H a:).
Each layer receives the outputs of all previous layers. We assume that the output of all layers is passed as input all following layers: this can be achieved by using the residual connections (which would be inside dec) and by placing the output of different layers onto separate subspaces.
Task-dependent initial state. We assume that the initial state Ho be set appropriately depend- ing on the task and is of rank at most 722-
Arbitrary decoder and state transition functions. We also assume that for every i, 9i E [0, 1]. || = 1 and UHj E Rd are arbitrary continuous functions of x;, The
3i, E [0, 2]. k,jj E Rd || function dec can also be arbitrary (continuous). Since in all our setups the possible values of æ; and H; are finite, this implies that the functions dec, A. B can model an arbitrary function of their discrete domain of interest, with the only restriction coming from the structural assumption of the output spaces of A (product of ny, Householders) and B (rank n4). This assumption can always be fulfilled in practice dec is a sufficiently wide MLP (see the next section for practical concerns) and, in the case of A, B, which generally do not contain MLPs, by setting the dimension of sufficiently large, which can be achieved by adjusting the embedding layer or the dimensionality of the output of dec. Note that the width of the MLP will grow with the complexity of the function to be approximated, which in our case depends on the complexity of the problem.
B.1.1 Practical Considerations
Beginning of sequence token. Alternatively, the assumption on Ho (task-dependent with rank at most ny can be replaced by using a beginning of sequence token 11 = S and setting H, = 0, as done in practice, that Hi B($) is learnable matrix of rank most n4, which acts as the Ho in our constructions.
Decoder implementation. In our implementation, dee is the same in Gated DeltaNet:
d ... H.") ), x.) MLP(RMSnorm(z;; +.)),
H
O: WoRMSHorM (HH) g()) df <(W/::)/ll
where W W are two learned matrices, e = SiLU, RMSnorm(rr (x) = a 3 x e -' x, corresponds (when e = 0) to projection onto an axis aligned ellipse where a E Rdd learnable and determines the lengths of the axis and 0 is small value set avoid numerical errors.
19

---

Meanwhile, MLP is a two layer MLP. This structure can be limiting. For instance, when Hi E R then be (H q: R and if by >> then [RMSNorm(bb) R 1, which means that after RMSNorm we are left with effectively only 2 possible values, while our constructions might require more: as many the number of possible states. Indeed, for all our constructions to work in practice, we would need a sufficiently large e, so that the output of RMSnorm can retain some magnitude information. Since in our constructions the number of states is finite, with >> 0 and appropriate value for qf' we are guaranteed that the map Hi¹ RMSnorm( (H)) q²), and consequently (by appropriately setting ) the map from states and inputs Tt, to the input of the MLP, is injective,
which we show in the next lemma. Hence, thanks the MLP, the decoder can approximate any continuous function of H 0y) even after the bottlenecks caused by the scalar product with of and the RMSnorm.
Lemma 1. Let S C R be a finite set of values. Define 8min minn.yeS, 12 y and 8max max jrr y)- Let b- (b, b2 y...., B and q = b/ ||b||- If satisfies b Sumx + 1, then the mapping f St + I given by s(H) = RMSnormí H q) is injective.
Proof. The mapping f is composition 93 9 92 9 91, where the component functions are:
91 (H) Σ h,6 92(2)
ga(z) RMSnorm(z),
[6|
where H = (h (.1,...,, ha) The overall mapping is injective if each component is injective.
1. Injectivity of 91: Intuitively, Φ1 encodes the vector H as a scalar as a number in base b, where each h, acts as a "digit" drawn from the finite set S. By choosing b sufficiently large relative to the spread of S (captured by m mmii)) we ensure that different vectors produce distinct scalars. To prove this formally, we show that for any non-zero difference vector A (Ai,..., A.)
H1 H2, the difference 91 (H1) - 91 (H2) = Σi= A,b' is also non-zero. This is true since b is by definition greater than Cauchy polynomial upper bound for the roots of the polynomial P(b) = ビ A,b'. For an elementary proof, let = max(i A, highest-order term is lower-bounded by:
+ 0}. The magnitude of the
A - |A 2 O
The magnitude of the sum of lower-order terms is upper-bounded as
k-1
k-1
b (b-1) (b-11
6 bb)
Σ
S Σ
mmax = &max
S 8min (b+ - b),
Y=1
where we used the triangle inequality and the assumption on which implies Smax I Smin (b 1). Comparing the bounds, we see that
Aaba 2 bm > 8min (b* -
Σ
A
Since the magnitude of the highest-order term strictly greater than that of the sum of all other terms, their sum cannot be zero. Thus, 91 is injective.
2. Injectivity of 92 and g3: The function d2 is linear scaling by the non-zero constant 1/||b|| and is therefore injective. For ga(x) RMSnorm(zr) its derivative is strictly positive for 0, meaning ys is strictly monotonic and also injective.
Since 91, 92, and g3 are all injective, their composition f is also injective.
When the state is one-hot, i.e. Hi = e; E 10, with 1 S i S d (i-th element of the canonical basis), an alternative to the above construction is to replicate the recurrence onto d heads, where the j-th head has Wi qf ej. so that, assuming that in the RMSnorm e c= O, we get 0g = He = e;- This is the strategy used in Peng et al. 13, Appendix DJ. However, for some problems using the one-hot encoding states e,, Cn is not very efficient. For instance, to solve the S, word problem one would need nil-imensional one-hot vectors as states, while in our Theorem we use n-dimensional vectors. Moreover, learning multiple identical heads is redundant and indeed we observe that in our synthetic experiments, the model is learning to use only one head to solve the tasks (see Section 5.2
(Vd, ... Va)* and
20

---

B.2 Group Word Problems
The next theorem establishes that DeltaProduct can solve the word problem for the symmetric group Sn, which implies that it can also solve any group word problem, since for every group G there exists n such that G is isomorphic to a subgroup of Sn-
Theorem 3 (Restatement of Theorem []. For any n E IN there exists a DeltaProduct model with one of the following configurations that can solve the word problem of the symmetric group S, (i) one layer with nh n-1 16 Theorem 3] (ü) 3 layers with n4>>1 (ūi) 4 layers with n,=11 The construction for (ii) and (iti) requires that the MLP the second last layer computes lookup- tuble of size 2m x (unction function of the last 2m input tokens and the position modulo 2m with
m = mmn=1)/mm
Proof: One way to solve the group word problem for the symmetric group S, is to map each element of the group g E Sn to the corresponding permutation matrix Pg E {0, 1)"H and then for each input sequence z1, ..,..... It with z; E S, compute each element of the output sequence y/....., Ut
Vi = I2 Ti-1 ...-. I1 = p(Pa, ... Paj uo):
Uo (I,...,n)),
where ø is a surjective map from vectors in {I..... n the n! elements of S,, which we consider integers for simplicity, i.c. Iı, E [[....,,!]
(i). Since a permutation of elements is series of at most n swaps of 2 elements, if n4 = n-1n then we can solve the problem with a 1-layer DeltaProduct by setting H, = ug doe (H, = (Va.j 0), A(x,) Pa.. The latter is achieved by setting for the j-th element in the product 1 (I , k either BL, 2 and Ki (ex - ep)/ /2 with e, being the i-th element of the canonical basis of IR" (swap element at index k with the one at index p), or Bi, 0 (identity).
o H)), (x;))
(ii) and (iii). If n4, < <- then the state transition matrix is not sufficiently expressive to represent all permutations of n elements. However, we can use additional layers to overcome this issue as follows. We divide the input sequence into blocks of elements: we factorize the position i e (.. into i Im + i where > 0 is the index of the previous block and i E {I,..., m} is the position within the current block (index ( + 1). First, consider the case when / 2 1. Let P. = -P Pau--1mm= Pacc-1m+1 be the product of the permutations of the previous block. Since P. is a permutation matrix of elements, we can factor it into P.- = Gt.m G1,1 where we recall that m = [n 11)/mm and each of Gi, Gi. is a product of vı, generalized Householder matrices and thus can be state-transition matrix of our model. We fix one factorization for each possible permutation matrix and set P. Go,m Go,1, with Go T to handle the case when 7 0.
Now let x; be the input of the last layer. if æ; contains enough information about previous tokens (as we specify later), we can set the recurrence and decoder of the last layer as
H: H dec( H;) = @ Pa: ...
... Rbon 11 Gt.m ... Glit1 H:)
current black
previous block
where Ho = ug. B(xx)) = 0, A(x;) = Gr, using the construction at point (i) since Gj,3 is a product of at most n, Householers. Note that H, contains the product of the input permutations only up to token T(m-))m and a partial computation of previous block of permutations P. Hence, the decoder completes the computation by applying two additional components: (1) the remaining transformations G through Gl,m needed to complete Pt, and (2) the actual permutations from the current partial block P Patm+1 through Pz.. The delay in the recurrence is necessary, since to compute even the first matrix of the factorization for a block of m elements of the input sequence, all the elements in such a block need to be processed.
We can check that this ends up computing the correct output y by substituting the expression for H; and unrolling the recurrence as follows.
doo H,, 22)) = Φ(F Pammii Prim+n Gi.m GI, G.-II Go.m ... Hu).
ol Pa Pammti P PrIm+: P.P. ... Powo)
= o( (a ... Paimt1 P Pau-ijmmm
P Pau-11m41
Prm ... P,, Pouo) ..m
= ((Pa, ... Pay uo) = yi:
21

---

Note that to compute A(z;) G1 and (H,, æ, should contain i = i mod m and the last m + i (in general the last 2m) tokens, corresponding to the current and previous blocks. Hence, the layers before the last one are dedicated to compute at each time-step i a lookup table for the possible values of (i mod 2m, Wis..... 22 -2:m++111 whose output will be included in the input of the last layer a,, The first layers (two layers if vt,, 1, one if nt >> 1) can provide i mod 2m by using Lemma 2 with d = 2m. Finally, the second to last layer can output any function of the last 2m tokens and the position modulo 2m through Lemma 3 with d 2m and a Zt. by using i mod 2m from the first layer(s).
Lemma 2. The following DeltaProduct configurations can count modulo d N. (i) 2 layers each with one head and n4 = (76 Theorem 6]. (ii) I layer with one head and nu 2 2.
Proof. For (i), we can use the same construction in [16 Theorem 6]. where the first layer does counting modulo and the second layer computes addition modulo d. In this case, since we just want to count modulo d we can ignore input tokens and add modulo d at each time-step. For (ii), note that if n4 > 2, we can set, for any time-step t, (xx,) = 0 and the state transition matrix A (xxe equal to a 2D rotation with an angle of 2nT /d by appropriately setting two keys, say kt,1, ke,2, setting 3r,1, 3r = 2 (while for the other Householders we set 3rg = 0). Then, we can count modulo by setting Hn in the span of kt,1, 2 and dec appropriately to map the d values that H, can take to the correspondent element in {1, {1....,}} dJ.
Lemma 3. A DeltaProduct layer with n,, receiving in its input at time-step the tuple (t mod d, a.) (t2 1) where a, E D c R with D being discrete set of values, can implement any function of (t mod d, a-d-l........ .............. az), where for simplicity we set a, = & D for i {2 d, 03.
Proof. Let i = t mod d [+1 1 Set Ho 0 E _ and the recurrence update as
H, = (T - e H 0,00;
where e; is the i-th element of the canonical basis of Rd. This can be implemented by setting Br,1 1, kt.1 = ez. 1t,1 = a, and Be.j, Vt. = O. With this choice, H, contains dt-d+1,-.- .4. The result follows since dec can be arbitrary continuous function of both H, and Φ, and the latter contains t mod d.
Vt.j
Finally, the next results concern finite subgroups of the orthogonal and special orthogonal groups.
Theorem 4. Let G be a group isomorphic either to subgroup of O(n), to subgroup of SO(n+ 1) in is even, then if ny = n, there exists a DeltaProduce model that solves the group word problem for G.
Proof. From the assumption we can map each element g E to an orthogonal matrix G,,. For the word problem for G, each element of the input sequence belongs to G: x; G for every i.
If Gg E On)), then, since nı and every orthogonal
matrix can be written the product of at most Houscholder matrices, we can set Ho = I E RR and A(zz) = G.:, B(x,) = 0 and dec(H,, x;)) o(H)) with Φ O(n) - G bijective (which exists due the isomorphism). The Houscholder product structure enables A(x;) to represent general orthogonal matrices Ga,, including rotations.
If instead G3 E SO(n + 1). since n is even in this case then we can still write Gg as a product of an even number (at most since This is because the determinant of G. is +1, which is only possible if it is a product of an even number of Householder matrices, each having determinant -1. Thus, we can set A A
is odd) of Householder matrices of dimension + 1 x n + 1.
G..
Ra+ixx+1 B (x:) = O. Now if we let G = Gz, Gz.11 ... GG, and set H, = diag(1 1, 11..(11.......000 ((a+1)((++1) (we are only allowed rank matrix), then H; GHo will have all the first columns equal to G and the last set to zero. However, the last column can be found as a function of the others since it must be the unique unit vector orthogonal to all other columns of G and for which GGt(G) = +1. Therefore, there exists a bijective functon from states to elements of the group, which can be implemented in dec.
22

---

B.3 Regular Languages
This section details how Gated PeltaProduct networks can recognize any regular language in a finite number of layers. The core idea is to show that Gated DeltaProduct can simulate any Finite State Automaton (FSA), since FSAs are the computational models that define regular languages. The proof proceeds in two main steps: First, we leverage the Atoohn-Rhode theorem, fundamental result in automata theory, which states that any FSA can be decomposed into a cascade of simpler FSAs known as permutation-rese automata. These simpler automata only perform two types of operations: permuting their states or resetting all states to a single state. Second, we demonstrate in Lemma 4 that Gated DeltaProduct is well-equipped to simulate these permutation-rese automata. The Produuct mechanism, using products of Householder transformations, naturally handles permutations, while the "Gated" aspect allows for the reset operations by nullifying the previous state's 's influence and setting a new one. By simulating these building blocks and cascading them, Gated DeltaProduct can thus simulate any FSA and, consequently, recognize any regular language.
Definition 1 (Finite state automaton (FSA)), A finite state automaton (FSA) is a tuple (E, Q, 4o: 5, F), where is a finite set culled alphabet, Q is the finite set of states, go E Q is the initial state, for every w E Σ, 8m Q - Q is a stute transition function and F C Q is the set of accepting states.
Definition 2 (Permutation-reset automaton). An FSA is permulation--rese if for every w E E, 8n is either bijective or constant.
Definition 3 (Regular language). A regular language is a set of sequences L such that there exists an FSA that accepts it, i.e. such that L C Σ", where E* is the set of sequences with elements in E, and that for every word w = W1W2- ... Wi Ex
Sw (go) == 6w. 8w.-1
6w, (go) F = E L.
(4)
Notably, the computation of any FSA can be also done using only matrix and vector multiplications. Indeed, if we let Q = (l.....1] (for simplicity). then we can map each state q to the one hot vector ey (element of the canonical basis of R") and each transition 6w the matrix Ma E {0. 1 with
element at row and column q' being if and only if ō(q') q. This way, by setting E {0, 13 such that r. g E F and rg = 0 Otheewwis,, we have that for every word w = w/ w2........
... Wn E X*
r MM, Mw.Mu.. ... M.w..p..MM..ppppp = + w E L.
(5)
We observe that if s. is bijective and changes i states, then the corresponding M is permutation matrix that can be written as a product of - Householder matrices, each corresponding to a swap of two elements. Moreover, if 6w is reset (constant), i.c. if (g) for every 9 Q then Mn = eg. As we will see, constant transitions can be modeled by setting the gate to zero. We now ready to state main result.
Theorem 5 (Restatement of Theorem For any regular language L and any n. E N, there exists a Gated DeltaProduct model with a finite number of layers that recognizes the language, i.e., for every word w E E' outputs 1 if w E L and O otherwise.
Proof. Using the landmark theorem by Krohn and Rhodes 50 we can decompose the FSA corre- sponding to the regular language I. into cascade of permutation-reset FSA. We can use a group of at most 4 consecutive layers to represent each automaton the cascade via Lemma Then, we can combine the different FSA in the cascade in a feedforward manner using the same construction as the one in the proof of [16] Theorem 3), where the input of each FSA is the output concatenated with the input of the previous FSA in the cascade.
Lemma 4. For any permutation-reset FSA with IQ = n and [_|= = where each bijective state- transition function 8. changes at most l states, there exists a Gated DeltaProduct model with the following configuration that can implement it, i.e., for any word w = Wi...., We E Σ in input, it can output the corresponding sequence of states .1.....%: It of the FSA. (i) one layer with nn = 1. (ii) 3 layers with
1. (Íi) 4 layers with n., = 1. The construction for (ü) and (iū) requires that the MLP at the second last layer computes a lookup-table size 2m 52m, ffncctinn of the last 2m input tokens and the position modulo 2m with m [[k 1)/mal
Proof. We use the matrix vector multiply construction to implement the FSA. For every time-step i set F; wi as the input to the model. The proof follows path similar to the one of Theorem
23

---

(where more details are provided), where in addition to modeling permutations, the state-transition matrix uses the gate to model constant transitions.
(i). Set Ho = ego When 6n, is bijective, by assumption it changes at most & states. Thus, by setting n4 k we can represent the corresponding Mw; matrix using A(w:) with gate gi (product of k- - generalized Householder matrices), and thus we set (ww;) = 0. If instead 6w, is constant, i.e. (g) q and ey = Bq for every q E Q. then we can set the gate gi 0 so that A(w;) 0 and B(u;, (.)) k; Eq. Finally, we dec H;, correct state at step (for simplicity Q (I,....,.)).
H (I,...,)) n) to retrieve the
(ii) and (iii). If n4 k- - 1, then the state tramsition matrix is not sufficiently expressive represent all permutations of elements. However, we can use additional layers to overcome this issue.
We factorize the position i E {1....6) 6 into i Im + i for integers 2 0 and i {I.... m). First, consider the case when / - 1. The product M, M
13m+1 M Meag-tmtt is either a permutation matrix of k elements or, if for some ow, is constant, then there exists q such that Mie,- q for every q E Q. Therefore, we factor Mi into Mi Gt. .G.,1 where each of G......,, Gt.m is either a product of ny generalized Householder matrices or Gr,ee = eq for every q E Q. which can be modeled setting the gate zero as in point (i). We fix one factorization for each possible permutation matrix. In the last layer and with enough information in its input s;; about past tokens, we can thus set Ho eo and
H: Gi. H dec( H, ...) = (M (m+ ... Mi Gl.m ... G1.+1 H.) (I......)T
The case when 0 is handled by setting M,- Go.m Go.1 with Go I. Note that both M2 and dec(H,, 2t) are functions of ă mod m and the last m + (in general the last 2m) tokens. Hence, the layers before the last are dedicated output at each time-step for the possible values of (i mod 2m, W...... W;-2mm+1) The first layers (2 if ny = 1, if n& > 1) can provide i mod 2m by using Lemma 2 with d 2m. Finally, the second last layer can output any function of the last 2m tokens and the position modulo 2m through Lemma with = 2m and a W/ by using mod 2m from the first layer(s).
lookup table
B.4 Regular language recognition through products of RWKV-7 matrices
To enhance the expressivity at the cost of stability, we can replace the product of Householder matrices of DeltaProduct with a product of RWKV-7 matrices, i.e. for each layer set
A(x,) =
II (diag( (wx,) - ck.s (ki. C an.))),
(6)
where W..s. ai.j. kij are computed from x; such that aij. way E [0. 1]" ||ki = and e (1,2). Even without using gates, the resulting model will be capable of recognizing regu- lar languages effectively as the following theorem shows.
Theorem 6. For any regular language recognized by a finite-state automaton (FSA) with n E N states, there exists a linear RNN using products of RWKV-7 matrices as state-transition matrices (as in (6) with e = 2) with one of the following configurations that can recognize it: (i) one layer with na n (ti) 3 layers with n. >> 1 (iii) 4 layers with nas = 1 [3 Theorem 31. The construction for (ii) and (iii) requires that the MLP at the second last layer computes a lookup- of size 2m x (n!)²m. function of the last 2m input tokens and the position modulo 2m with m [n/np]]
Proof. The computation of an FSA with n states can be done using matrix-vectur multiplications as shown in (4). where the n x n state transition matrices Ma. have elements in {0, 1} and a single one in each column. Peng et al. [13] Lemma 3] prove that any of those matrices can be expressed as products of n matrices, each of which is either a swap (identity with two columns swapped), copy (identity with one row copied onto another), or the identity matrix and can be modeled by single RWKV-7 matrix. The proof for (ii) and (iii) follows similarly to Theorem [ but now tackling all state transition matrices, while Theorem I could handle only permutations since a generalized Houscholders matrix cannot be a copy matrix.
24

---

B.5 Dihedral Groups
In Grazzi et al. []6] Theorem 6] is shown that with 2 layers and the extended eigenvalue range, DeltaNet can compute addition modulo m, which corresponds to solving the group word problem for the cyclic group Zm. for any m E N. We extend this result and prove that, under identical as- sumptions, DeltaNet (DeltaProduct with n,, 1) can solve the group word problem for the dihedral group Dm. for any m E N. The dihedral group Dm represents the symmetries (both rotations and reflections) of a regular m-sided polygon. As notable example, D3 is isomorphic to the symmetric group S3.
The linear RNN construction used in this result can be implemented using 2-layer DeltaNet Model with two heads in the first layer. In the first layer, the linear RNN will compute parity for rotations and reflections separately, i.e. it will record if the number of past rotations (reflections) is even or odd. The recurrent state of the second layer will have 2m possible values (same as the order of Dm) and each will be decoded differently based on the parity of reflections. The parity of rotations, combined with the group element, determines which reflection matrix to use as the state transition matrix of the second layer.
Theorem 7 (Dihedral group word problems with reflections). For any m E N, consider the group word problem of the dihedral group D.m There exist DeltaProduct models with the following con- figurations that can solve it. (ii) Two layers with nA = and at least two heads in the first layer and one in the second layer. (ūi One layer with nn 2
Proof. The elements of the dihedral group Dm can be divided into m rotations R = fro...... mm-11
and m reflections = {:o..... 3. The identity is ro. To be able to solve the corresponding word problem, we would like to map sequences of group elements 21,-... with xi; E R. U S into
sequences y,,...,34 Dt with yi = 34 14-1 ... 21 and the group operation, that for dihedral groups is defined as
T3 13.T7 Tj = Ti+j mod ma T4 8;+5 mod ma T5 82-1 mod m.
8, 83 Ti-s mod m- (7)
Note that product of two rotations is commutative, while the product of two reflections or reflec- tion with a rotation is not. Indeed for m 2 3 Dm. is not an abelian group.
(i) The constructions of the two layers of DeltaProduct with nı = builds upon the one for the cyclic group 7m outlined in [6. Theorem 6]. The first layer functions as a pre-processor, calculating auxiliary information from the input sequence. Specifically, for each time step t, it determines two parities: the parity of the total number of reflections and the parity of the total number of rotations in the sequence .1,..., It. This information is then passed to the second layer.
The second layer is responsible for computing the cumulative group product. It uses a 2D hidden state to geometrically model the group elements and their compositions. The core challenge lies in modeling the group operations, i.c. rotations and reflections, using only a reflection as state- transition matrices (rotation matrices cannot be represented with n., = 1). To address this, the state representation in the second layer must encode more than just the previous group product. is designed to also incorporate the rotation parity computed by the first layer. This is achieved by maintaining two distinct sets of m state vectors each and two distinct sets of 2m reflection matrices each to represent the group elements. The choice of which set to use is determined by the rotation parity. Moreover, the reflection parity is also used but only in the decoder. This design allows a single, unified update mechanism, based solely on geometric reflections, to correctly implement all four of the distinct multiplication rules defined
We define rotation by and reflection matrices as
cos(() - -sin(a) sin(() cos(a)
cos ()) sin((:)
sin(a)
)
Rotation: R(a)= =
Reflection:
H(a) =
- -cos(a))
(8)
where R(a:) a rotation by an angle of a, while (aa) is a reflection by a line having an angle of a/2 with the line passing from the origin and the point (1,0). 0). Note that both R and H are periodic with period 2v. Moreover, let a, 7 E IR, the following are standard identities of products of matrix representations of 2D rotations and reflections.
R()) R(a + 7); R(a)H( H (n)
H()) = R(a - 7), R(a) H (7 - ())
(9)
25

---

For the first layer we use the following diagonal recurrence which indicates in the first (second) coordinate whether the number of rotations (reflections) is even (0) or odd (1).
(2) =0, 0,
1 11 a(xz)
3 - + b(æ)),
y (1)
dee (1) (he; nz))
(Et, Ne,1, 1e,
-1 2; E R
{-1 if r; E S
a(x:); =
a(zi)2 {1
(1
if ES
r; E R
if 24 E R
[1 if ot E
b(x))) 0 if if
b(zi)2 - 0 z1 R
This recurrence can be implemented also by DeltaProduct with nA = using 2 heads each with scalar hidden states: one for the rotations and the other for the reflections. For the second layer, we have instead the following constructions, which selects the appropriate reflection based on the parity of the rotations and uses the parity of the reflections for dec.
ho = (1,0),
h (2) A yy: (1) 1n yi = (2) (h(
(2)
(2), Ut ())
A (y) H (0(11, 82)),
dec (h, (h,
ri-
if y/s
8 arg max max(c, h d. h) m=()....m-1)
Sm-
y/3
where y = (v1, V/. 73)T angle of the reflection and is defined for all i E {0, .............................. 1) as
E RUSS {0. 1} x {0. 1} and 0: TRUSX x {0,1} + determines the
O(r,, 1) = (1 (1-20) 2T)
((r,,)) = (1+ 2
24 0(s, 0)
(2 24)
((s,, 1)
m
m
m
m
Moreover, C {co..... Cm- 1) and D {do .... dm-1) are two sets of states and are defined as
dg ho (2) (1,0) co H (z/m))dn
d = R((2 (1)it/m)ddo C; = R( 221--in mm)cc for all i E (O...., m 1}.
From choice of do (1 and co and from - for any a E IR we have
R(a)do- (a) and
R(a)co = ( = R(T/m)) = R(a a/m + w/m - r/m)ddo Ha + 2n /m/ H //m)dd H(a (a + 2TT 2t/m)co.
Moreover, from our choice of 0, d, and c, using the identities above and the the fact that is a periodic function with period 2 we have that
d R(2im/ (iir/mmdd = R(2ix/m)H (T/m)co (f(r,, 0))c,
C = R( -in m) Cc- = Ri-iii// m) H ((THH)/mm/m// ((Br,,, d, - R( 2i m) do H (-2nm m m) (0((s,, 1))
Cn-i = R( (+ 2it cm = ((2 + / H(((s, 0))co
for every i E {0,... m - 1}. Therefore, we can write
H(O(r,, 1) R(0(r,, 1) -(r,,,
2(i + f = Ci+s mod m.
(O((r, 0))c; R(O(r,, 0) - -O(r, 1))do = R(2( j))m+mj)mmmm = di+s mod (((ss,, 1))d, R(O(s), 1) 0(sm-i, 1) R = d mod ma
(10)
(0((s, 0))c, R(O(s,, 0) - 0s 0))co = R(2(i + +)=m = c_i-j mod mod
for every i,j E (O...., . m-11) 1}. We proceed to verify that the output of the second layer is computed correctly: satisfying the product rule for the dihedral group 7 i.e., we want to verify that
if (2)
Vitj mod
ri, Vt = rj
3/
(2)
Sitj mod m
if y/
(2)
Tt, 8
(11)
8i-j mod m
if Vt-1
-t = rj
Ti-j mod
if y
(2)
S, = 8j
26

---

Where we set Vo
(2) ro- First note that when Di (2)
(1) S, then 11, = 1 and when vi()) E R. then
(1) 0. We consider two cases.
V1,3
Case 1. If yf = Ti and hence Dt Vt- = O, then using 10) we obtain
H(( 1))d; = Ci+f mod m
if Dt = rj 2r =
H(O(r,, 0)]c; = di+s mod
if It = r Vt.2
(1)
1 = (2) (y)))
((( 1))d, -d-i-j mod (0(ss, 0))c; -c--j mod m
if zt = 8,, V1 2 1
if x - Sj Mt.
(1) 0
This, together with the definition of doe implies that
yt (2)
dec (1)
Di (1)
T++j mod
if Ø1 = rj. Vr.3
(1)
(12)
8i41 mod m
if 2t = 8) Vi.3
Case 2. If instead
Vi-1 8i and hence (1)
V/- 1, then using 10
obtain
HO(rr, ()) dmm = Cj-i mod
if Dt Ty. V1
(1)
h (y
(0(r,, 0)) dj -i mod m
if Tj. 11.22
(1) 0
H(Oss,, 1))dm-; di-j mod
os = 8), 31.
(0(s,, Cm-i = ci-s mod
if oz 8), Vr. 0
This, together with the definition of (2e implies that
V1
(2)
dec (2)
(he (2)
(1)
8 j mod m
if Vi. = or Vi,3
(13)
ri-j mod
Note that [22 and 13 imply Setting the output of the linear RNN equal to the output of the second layer concludes the proof.
(ii) follows from Theorem 4 since Dm is finite subgroup of 0(2), the group of 2D orthogonal transformations: rotations and reflections.
B.6 Stability vs. Expressivity of Linear RNNs
In this section, we discuss the tradeoff between expressivity and stability of linear RNN recurrence
H, = A, + B,, where A, A(x;), B, = (xx,). We say that such recurrence is stable if
3M E [0, oo) such that
II A
< M ViEN,
(14)
where ||-|| is the spectral norm. This property is true if and only if p(II;=1 A₁) S 1 where p(M) is the spectral radius of M, i.c. the maximum modulus of its eigenvalues. When this property is not satisfied, the norm of the state will diverge. An effective way to satisfy (14) with M 1 is to enforce ||A < for every since the norm of the product is less than equal to the product of the norms (due to the submultiplicativity property). However, this restriction excludes some boolean matrices which useful for recognizing regular languages. Indeed, in the construction shown in (4), all matrices involved are n x n with entries taking values in (0, 1} and having only a single one in each column. This class of matrices B satisfies (14 with M V because it is closed under matrix multiplication. i.c VB, B' E B, we have BB E B, and max [|] vn. which is achieved by matrices with ones only in one row. In particular, all matrices B that are not permutations have spectral norm greater than one and therefore cannot be expressed if we enforce || < 1.
The (Gated) DeltuProduct state transition matrix A, I[ gr kr satisfies ||A S since gi E [0, 1]. 81 E [0, 2), and || 1. Thus, from the matrices in B, it can represent only permutations of up to ni. + elements. Instead, the state-transition matrix of RWKV-7, A, diag(w,) ck, (k, @ a.) with 2, can represent not only the identity and permutations of two
27

---

elements, but also any copy matrix, which is obtained by copying one column of the identity onto another and has spectral norm equal to v2. However, as we show in the next theorem, even with the less expressive c
setup that used in practice, the RWKV-7 recurrence is not stable unless a; is the same for every i, which is the case studied in Peng et al. [33 Theorem 1]. Having different a, values is key to modeling the copy matrix, since this requires a value different from that of a permutation matrix.
Theorem 8. Consider the RWKV-7 state transition matrix A, = diag(w;; (k; C a.) with c = 1 (as set in practice), we = (1.....,) 1)T E R", a, E [0, 1]" ky E R" with ||k]|| = 1, and
A') E M, we have > 2. There exists an infinite M of matrix pairs such that for every AA)
p (AAA' > 1.2, where denotes the spectral radius. Thus, if we set
A A'
if mod 2 =
A
which implies
lim
II A
lim = c0.
i mod 1
We demonstrate this by construction for = 2; the generalization to n 2 2 is straightfor- ward.
Proof.
Let 0 = T/3, a = (0.1) a' = (1,0) k = (cos 0, sin 0)T = [1/2, v3/2.T. k'
(sin 0, cos 0) = (V3/2.1/2) Note that ||k||| = ||l'| = 1. We construct A and A' as
v3/2)
1/2] (
-V3/4 3/4
A = 1 - ((k o T= =
[0
1/2
1/2
3/4
0
= W o a') =
[1/2
0]
v3/2
33/4
1
Now, consider the product matrix
M = AA' (
--////
3/4 3/4 (-v3/4 9)
15/16
-v3/4
-3/3/16
3/4
To find the spectral radius p(M). we examine its eigenvalues. The characteristic equation is X² ( + det( (M) = 0, with Tr(M) = 27/16 and det(M) = 9/16. Hence, the characteristic equation is 16A 27A + 9 = 0. Thus, the eigenvalues the spectral radius is p(M) = ma |A2l] = a s 1.23. Also, since the spectral radius is continuous function of the matrix entries, which are continuous function of 6, then this means that there is an infinite set of matrices, namely M, obtained by varying @ around T/3 whose product has spectral radius greater than 1.2.
A 27+ v153 and X 27 2753/13 and 32
32
From construction of A,, we have I A, M By the definition of the spectral norm and ||||=||| = |a| p(M), where x is the eigenvector associated with the dominant eigenvalue \₁. The result follows since lim P(M)² = co.
spectral radius, || 2
C Experiments
C.1 State-Tracking
Clarification on the isomorphisms of Sz, St, As, and Ss
S3: The group consisting of all isometries that map an equilateral triangle onto itself, including both orientation orientation-preservingg rotations and orientation--eversing reflections, is isomorphic to Sz.
Sy: The rotation group of cube is isomorphic to the symmetric group S4. This correspondence arises because the cube has exactly four space diagonals, and every proper intation-tha is, every orientation- preeeervn-- isometry of the cube about an axis through its center-permutes these diago- nals in all possible ways (see Figure o an example). In particular, these proper rotations include, for example, the 90º, 180", and 270" rotations about axes passing through the centers of opposite faces, the 180 rotations about axes through the midpoints of opposite edges, and the 120% /2400
28

---

Group S3
Group S4
Group As
Group Sg
11/
f16
Accuracy
0.5
2
0.0
Accuracy
0.5
0.0
0
200
400
0
200
400
0
200
400
200
400
Sequence Length
Soquence Length
Soquence Length
Soquence Length
Figure 12: Results for permutation groups S3. Sq. As. and S3 when limiting the eigenvalue range of the state-transition matrix to [0, 1]. (Top row) Varying the number of Householder prod- ucts n4 for a single layer DeltaProduct,,, [0, 1]. (Bottom row) Varying the number of layers I of DeltaProduct, [0, 1//DeltaNet(,, 1] (single Householder). Dashed vertical line at training context length 128. Higher n, improves extrapolation to longer sequences of permutations, e.g., S3 can be learned with n = 2 with single layer while three layers are required when keeping = 1.
rotations about through opposite vertices. Hence, the proper rotational symmetries of the cube correspond precisely to the permutations of its four space diagonals [69].
A;: Similarly, a regular dodecahedron contains exactly five special cubes symmetrically arranged within it. Each proper rotation of the dodecaaedron--thal is, every orientation- orientation-presevving rigid motion mapping the dodecahedron onto itself-reanin rearranges these inscribed cubes by an even permu- tation. This property makes the rotation group of the dodecahedron isomorphic to the alternating group As. the group of all even permutations of five elements [70].
S5: When both proper rotations and reflections porientation-reversinn symmetries) are considered, the full symmetry group of the dodecahedron corresponds exactly to the symmetric group Ss, since reflections allow both even and odd permutations of the five hidden cubes 77).
Experimental Details. We used the experimental setup from Merrill et al. 3 and sampled 2,000,000 training datapoints at sequence length 128 and 500,000 test datapoints at sequence length 512. We did not use curriculum over sequence length during training. The models were trained us- ing Adam optimizer 771 with parameters 81 0.9, 8g 0.999, and
10 in PyTorch [72]. We used a learning rate of 10 with cosine annealing [73] and trained for 100 epochs with a batch size of 1024, except for the S3 models which required a batch size of 2048 for more reliable results. All models used a single-layer DeltaProduct architecture featuring 12 heads (more heads made the results more reliable) and head dimension of 32. We applied a weight decay coefficient of 10-6
The 3 values were extracted from the forward pass of the trained models using NNsight (74). We use the PCA implementation scikit-learn 75
C.2 Chomsky Hierarchy
Setup. We conducted experiments on selected formal language tasks originally introduced by Delétang et al. [52). Our goal was to demonstrate the improvements in length extrapolation that can be achieved using multiple Householder matrices in the state-transition matrix compared to DeltaNet. Following Grazzi et al. [16], we focus on three tasks: parity, modular arithmetic without brackets (both regular languages), and modular arithmetic with brackets context-free language). We trained DeltaProduct,,, with E {2, 3, 4} on sequences of length 3 to 40 and tested on se- quences ranging from 40 256 to evaluate generalization to longer inputs. We compare our results against the results obtained by Grazzi et al. [16] for Transformer, SL.TM and SL from Beck al. [9, Mamba (6. and DeltaNet [10]. For both Mamba and DeltaNet, we experiment with an eigenvalue range restricted to (0, 1] and extended to [1,
29

---

Head
Head
Head
Head
Head 4
Head 5
Head
Head
Head 8
Head 9
Head 10
Head
Bo
Figure 13: 3o and 31 values across all 24 permutations S₃ in DeltaProductyl- only head 6 (shown in Figure 7 learns to use both Householders as reflections (5u = 2, 31 = 2) allowing learn the rotations solve S4.
-11 1]. We find that
Experimental Details. All DeltaProduct and DeltaNet models contain 3 layers with head each and heads' dimensions set to 128, except for modular arithmetic with brackets, where we use 12 heads and set the heads' dimensions to 32. Both models use a causal depthwise ID convolution with a kernel size of 4 after the query/key/value projection. For modular arithmetic, we also use a gradient clipping norm of 1.0. We train each model using Adam [71] using learning rate of 5e-4, batch size 1024, 0.1 weight decay, and cosine annealing learning rate schedule [73] (minimum learning rate: 1e-6) after 10% warm-up steps. We train the modular arithmetic and parity tasks for 100k and 20k steps in total, respectively. At each training step, we make sure to generate a valid random sample from the task at hand (see below). We repeat the runs 3 times with different seeds each, and later pick the best to report in Table
Considered Tasks. We empirically evaluated three masks-parity, modular arithmetic without brack- ets, and modular arithmetic with brackets spanning different levels of the Chomsky Hierarchy. Be- low, provide details for each task, where [ denotes the vocabulary size and Accrand represents the accuracy of random guessing:
Parity (Σ) = AcCrand 0.5). Given a binary sequence æ = 21 ...... Dt E (0, 1)', the parity label E [0, is I if the total number of ones in the sequence is odd, and 0 otherwise. This task is equivalent computing the of all previous values modulo 2, i.e., y1 (E/= 2:4) mod?
Modular Arithmetic without Brackets (Σ) = 10, AcCrand 1/5). Given a set of special tokens Σ, {+, - 9, =, [PAD]] and modulus m 1, we define Σ Σ, U {O..... The label Ve corresponds to the result of evaluating the arithmetic operations in the sequence I 2 ........ Fy, computed modulo m. In our experiments, we set An example is:
1}.
2 + 1 - 2
[PAD]
Modular Arithmetic with Brackets (|>) = 12, Accrand = 1/5). This task follows the same definition modular arithmetic without brackets but includes an extended set of special tokens, 3, = (,,-,,,=)), [PAD]], allowing for nested expressions. Again, we set m 5. An example
sequence is:
(1-((2)) + ((4) + 3)) = 0 [PAD]
Results. As shown in Table 2 DeltaProduct,, with n; has better average accuracy compared to DeltaNet and other baselines. This performance improvement particularly pronounced when using the extended eigenvalue range [-1, 1), which aligns with the findings of Grazzi et al. [16]. Notably, we observe the most significant improvement the modular arithmetic with brackets task, which is also the most challenging.
30

---

1]. Performance of DeltaProductn, [-1, ni E {2, 4). formal language tasks. We report the best of runs. Scores are scaled accuracy, with 1.0 indicating perfect performance and 0.0 random guessing. The results for the other models were taken directly from Grazzi et al. [16].
Table 2:
Mod. Arithm. Mod. Arithm.
Model
Parity
(w/o brackels)
brackets)
Transformer
0.022
0.031
0.067
0.040
ml STM
0.087
0.040
0.1
0.080
sLSTM
1,000
0.787
0.178
0.655
Mamba [0,
0.000
0.0M5
0.123
0.073
Momba [-1,1]
1.000
0.241
0.116
0.452
DeltaNet [0.
0.233
0.302
0.253
0.263
DellaProductt
0.349
0.305
DelluProducts 00 1
0.285
0.402
0,288
0.325
Dellaroduuct, I
0.369
DeltaNet 1-
0,982
0.915
0.281
0.726
DeltaProductt 1, 0.896
0.887
0,329
0.704
DeltaProduct,
0.932
0.736
0.330
0.666
DellaProduct,
1,1
0.982
0.893
0.342
0.739
C.3 Language Modeling
C.3.1 Experimental setup
We follow the same basic training setup in [16]. We use the training pipeline flame from the mish-linear-atteation [22) repository. All our models are trained on NVIDIA L40s, NVIDIA A100 40GB NVIDIA H100 94GB GPUs. We used 16 to 32 GPUs at time to train model, in 2 to 8 node setup, depending on resource availability. We used DeepSpeed with ZeRO-2 [76] for distributed training. All models were trained with effective batch size of 524 288 tokens, and a learning rate of 3e-4. We optimized the models with Adam W (71] (0.01 weight decay) and used cosine annealing (73 for the learning rate schedule with linear warm up for 512 steps. We used total of 10 500 GPU hours to train all our models.
C.3.2 Throughput
Tokens per second (Ktis)
40K
20K
16K x
8K X
4K
4
2K
Training length Batch size
Figure 14:
Training throughput of a parameter matched DeltaProduct 1.3B. Parameter matching is achieved by decreasing the inner dimension in the SwiGLU MLP for n4. 1.
C.3.3 Additional Benchmarks
In Table we report evaluations for the models Figure 10 on tasks from Im-eval-harness 61.. In
addition, we also train and evaluate models with 2048 context length at the 340M parameter scale and report the results in aad compare them with the results [10] which are trained under comparable setup. We observe that DeltaProduct outperforms DeltaNet in terms of average accuracy for both training setups.
Tasks Details. We use the im-eval-harnes, benchmark 66 to assess model performance. Following Yang et al. [0], the evaluation encompasses multiple task categories: Language Understanding Tasks. The evaluation includes LAMBADA (LMB) 77 for testing text comprehension, PIQA 78 for physical reasoning assessment, HellaSwag (Hella.) 79] for situational understanding, and Winogrande (Wino.) [80] for commonsense reasoning evaluation. Reasoning. The ARC dataset provides two distinct testing sets: ARC-easy (ARC-e) and ARC-challenge (ARC-c) 81] measuring varying levels of scientific knowledge comprehension.
31

---

Table 3: Performance comparison of models shown Figure Parameter equivalence was
achieved by scaling the head dimension. To account for the increased parameter count we scaled the training token budget from 19B (213M parameters) to 55B (805M parameters) on FineWeb [57].
Models were trained 4096 token context length.
Wiki.
LMB.
LMB.
PIQA
Hella.
Wino.
ARC-e acc
ARC-c
Avg. 1
Model
ppl 4
ppl 4
acc
acc
acc_n 1
acc f
acc_n 1
p0n 2133
DeltaNet[-1,
32.39
107.41
20.4
65.3
35.1
52
44.1
24.5
40.25
DeltaProducty -1
31,46
78.98
23,9
64.6
36.2
52.6
45
23
40.88
DeltaProduct, 1
30.94
70.5
24.6
66.3
36.8
49.1
46
23.7
41.01
350 392M
DeltaNet(-11
25.5
40.32
30.2
68.5
41
51.9
47.3
23.3
43.7
DeltaProducts
1,
24.82
34.31
33.3
68.9
43.4
50.7
49.2
25
45.08
DeltaProducta 1,
24.81
37.13
31.1
68.5
43.3
50
48.2
23.7
44.1
550 MCM
DeltaNet[-111
20.81
20.57
48.9
55.6
25.6
48.55
DeltaProducts
1
20.54
19.56
50.7
55.2
52.1
26.7
49
DeltaProducts
11.1
20.01
15.56
51.4
49.95
Parameter equivalence was achieved by scaling the number of heads in the attention. To account for the increased parameter count we scaled the training token budget from 19B (213M parameters) to 55B (805M parameters)
Table 4: Performance comparison of models shown in Figure 21
on Web [57]. Models were trained 4096 token context length.
Wiki.
LMB.
LMB.
PIQA
Hella. acc_n
Wino. acc 1
ARC-e
ARC-c
Avg.
Model
ppl 4
ppl 4
acc
acc
aec
acc.n 1
190/ 2M1M
PoltaNet[-1,3
31.96
85.36
22.5
65.2
35.4
50.8
44.7
22.4
40.17
DeltaProducts 1
30.87
89.23
23.1
65.4
36.5
51.2
43.5
22.4
40.35
DeltaProducts 1
30.85
71.52
24.1
66.3
36.1
51.6
44.1
23.9
41.02
5507 RRM 350 3924
DeltaNet 1]
24.86
30.8
41.4
50.5
24.4
43.83
DeltaProducty -1
24.97
35.68
31.9
69.6
42.5
52.6
47.4
25.9
44.98
DeltaProducts) 1]
25.2
40.96
30.5
69.1
42.3
51.4
47.7
23.9
44.15
(oltaNer[-1,1
20.6
21.18
38.7
71.5
48.7
52.8
51.9
25.7
48.22
DeltaProducta
1.1]
20.26
17.41
40.7
72.6
50.3
53.9
52.4
24.9
49.13
DeltaProducts
-1,1]
19.97
17.78
40.79
72.3
50.9
52.1
53.9
26.4
49.4
Table 5: Performance comparison of models trained with 2048 context length. (SlimPajama (SPJ) reproduced from Yang et al. [10], Fine-Wad (FW) ours). Results are shown for DeltaProduct and Gated DeltaProduct. We use 8 heads for each layer, unless otherwise specified.
Wiki. ppl
LMB.
LMB.
PIQA
Hella. acv_n
Wino. acc ?
ARC-e acc
ARC-e acc_n 1
Avg. 1
Model
ppl
acc
acc
150 oaleosss SP3
340M parrams
Transfommer++
28.39
42.69
31.0
63.3
34.0
50.4
44.5
24.2
41.2
Mamba 1]
28.39
39,66
30.6
35.4
50.1
46.3
23.6
41.8
GLA [0.
29.47
45.53
31.3
65.1
33.8
51.6
44.4
24.6
41.8
DeltuNet (0.
28.24
37.37
32.1
64.8
34.3
52,2
45.8
23.5
42.1
DeltaNet 1| 340M
26.92
43.07
29.8
69.0
41.0
50.9
46.6
24.5
43.6
DeltaNet 1
26.57
36.76
50.9
47.2
24.4
530 FN
DeltaProduct,
392M
26.43
30.66
34.0
68.9
42.4
$3.1
48.9
25.9
45.5
DeltaProducts 11 443M
25.94
29.91
34.2
69.9
43.2
51,9
48.2
24.1
45.2
Gated DeltaNetf 1, 340M
25.97
33.57
33.1
69.5
44.1
51.1
50.9
26.7
45.9
DeltaProducte -,
25.12
30.03
55.3
25.3
46.4
32

---

C.3.4 Training behavior
The training behavior of DeltaProduct,, is stable as shown in Figure 15 considered model sizes in Figures 10 and 21 and Appendix C.3.5
This is also true for all
Training Loss vs Steps
Last 15k Staps
LO05
5
2.50
Stpe
Staps
-10"
Number Houscholders (ng)
The curves demonstrate stable training behavior as nı increases, with higher values of nı, consistently yielding lower losses throughout training and convergence. While the absolute differences in loss between different n, values are relatively small, they correspond significant differences in length extrapolation performance.
Figure 15: Training loss curves of DeltaProductm,(11111
C.3.5 Additional results on Length Extrapolation
In this section we show additional plots on length extrapolation. In Figure 16 we show the length extrapolation behavior of (Gated) DeltaProduct,,, scaling up n4 without adjusting any of the other increases the param- eter count of the model. Hence, Figures 17 and T8 show the per-token loss and perplexity of DeltaProduct,,, at three different scales where the parameter counts are matched at the respective scales following the configuration parameters shown Table Note that these the same models
model configuration parameters. As discussed in Section [3.3] increasing
as shown in Figure 21
CodeParrot
Thoughts 114K Math
Trivia QA
SlimPajaamt-
3.3
3.2
2.80
Token Loss
3.2
2.8
3.1
2.75
3.1
2,70
3.0
3.0
2.65
2.9
2.9
www.
2.60
16384
16384
16384
4096
16384
24
16.0
15.5
Perplexity
22
15.5
15.0
15.0
20
20
14.5
14.5
18
18
14.0
4096
16384
4096
16384
4096
16384
4096
16384
Sequence Position
Sequence Position
Sequence Position
Sequence Position
Model sype
Non-guted
Gatad
Figure 16: Per token loss and perplexity on context lengths up to 32.768 for (Gated) DeltaProduct,,.. (Top) per token loss. (Bottom) Perplexity. Per token losses smoothed with a window-size of 300.
33

---

CodePParoo
Open' OpenThoughts 114K Math
Trivia QA
Slim SlimPajjaa
4.0
3.6
3.00
3.00
Token Loss
3.8
3.5
2.95
2.95
3.6
3.4
3.4
2.90
3.3
2.85
3.2
2.85
2.80
4096
16384
4096
16384
4096
16384
4096
16384
3.6
2.80
Token Loss
3.2
3.4
2.75
3.0
2.70
4006
16384
4096
16384
4096
16384
4096
16384
3.6
2.65
Token Loss
3.2
3.4
2.60
3.2
3.0
2.55
3.0
2.8
2.8
2.50
4096
16384
4096
16384
4096
16384
4096
16384
Sequence Position
Sequence Position
Sequence Position
Sequence Position
Per token loss of DeltaProduct,,, contexts up 32.768 different model sizes. Models are parameter equivalent at each scale. Parameter equivalence achieved by scaling the number of heads. Exact model configurations be found in Table 6 (Top) 213M parameters. (Middle) 392M parameters. (Bottom) 805M parameters.
Figure 17:
34

---

CodeParrot
Open'T Thenghtth 114K Math
Trivio QA
SlimPajama
19.0
30
18.50
Perplexity
18.5
18.25
28
18.00
18.0
26
25
17.75
17.5
17.50
4096
16384
4096
16384
4096
16384
4096
16384
23
15.6
15.75
Perplexity
15.50
22
15.25
15.0
20
14.8
15.00
4096
16384
4096
16384
4096
16384
4096
16384
25.0
20
Perplexity
22.5
13.0
20.0
12.5
17.5
13.0
16
15.0
12.0
4096
16384
4096
16384
4096
16384
4096
16384
Sequence Position
Sequence Position
Sequence Position
Sequence Position
Figure 18: Perplexity analogue of Figure 17
Table Model configuration parameters for models shown Figures 17 and
18
All other config-
uration parameters are the same in [66..
Model Scale
Householders
Hidden size
Heads
768
8
213M
2
736
6
768
4
1024
12
392M
1024
8
1024
6
1536
16
805M
1468
3
1536
8
35

---

DellaProduct_[-
DelraNet[-1.
CatedDDelsarrodatty (-1
GaredDelaNe((LL.
Layer 22
60
60
30
Effective
40
20
20
10
60
Layer 19
60
Effeedive
-40
40
20
75
30
Layer 16
Effective Rank
60
50
20
40
Layer 13
40
Edtective
20
Layer 10
40
40
40
Edicetivo
20
Layer 7
40
Effcctive
40
20
20
20
20
Edfeedive Rank
30
20
Layer
20
20
20
10
Effective Rank
30
.00
7.5
Layer
20
5.0
20
20
2.5
0
0.0
100000
10000
0
10000
10000
Sequence Length
Sequence Longth
Sequenee Length
Sequence Length
Figure 19: Effective rank of H. for of heads for selection of the layers on CodeParrot se- quences. Solid vertical lines mark new code sequences; dashed vertical line indicates 4096-token training context length; colored lines show effective rank per head over the sequence.
C.3.6 Additional Results Scaling Behavior
In Figure 10 parameter equivalence is achieved each scale mainly by decreasing the the head dimension for models with nı, > 1. In Figure 21 we show perplexity of FineWeb for another set of scaling results where parameter equivalence reached by reducing the the number of heads in the attention. The result for this alternative type of scaling still shows the superiority of DeltaProduct compared DeltaNet. However, in this case, models with higher ny are not strictly better than those with fewer Houscholders.
36

---

DeluProouctt-LL.
DeltNetf-1,1
GatedDelaProduck,
GutedDelaNe(-L..
Layer 22
Rank
60
60
20
400
660
60
Layer 19
40
40
Effective
20
200
20
40
Layer 16
8
60
Effective
40
20
200
Effective Rank
60
Layer 13
40
40
20
400
Layer 10
Edicetive Rank
20
20
40
40
Layer 7
-00
Ediceiive
20
20
Layer 4
40
30
20
20
Effcetive
20
10
30
Effective Rank
7.5
Layer
20
5.0
20
10
2.5
0.0
10000
Sequence
Length
Sequence Length
Sequence Length
Sequence Length
Figure 20: Effective rank H. for heads for a selection of the layers on TriviaQA sequences. Solid vertical lines mark question-answer pairs; dashed vertical line indicates 4096-token train- ing context length; colored lines show effective rank per head over the sequence.
37

---

DeltaNet DeltaProducly
16
DeltaProduct,
15
Perplexity
12
200M
400M
800M
Parameters
Lambada
Avg. accurncy In-eval
pradhodua
0.45
Perplxity
10 80
0.45
0.44
200M
800M
20055400
RITM
Paramoters
Parumeters
Figure 21: Scaling analysis w.r.t. (top) final perplexity on FineWeb, (bottom) Lambada and Im-eval tasks. Parameter equivalence is achieved by scaling the number of heads. Models trained at each scale with number of tokens as reported Table
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All of our claims are substantiated in the experiments or the theory.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we discuss limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
39

---

Justification:
Yes, we state all assumptions for the theory in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all experimental details required for reproducibility for each ex- periment. The details for the state-tracking experiments are in Appendix C.I for the Chom- sky Hierarchy in Appendix C.2 and for the NLP experiments in Appendix C.3
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) 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 way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
40

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes, we provide the implementation of DeltaProduct and the experimental setup for state-tracking which can be executed quickly and cheaply verify our results during the reviewing period. The code is provided here https: /tte::///ghhbb..g thub. com com/automm/ DeltaProduct] We used synthetic data for the state-tracking and chomsky hierarchy ex- periments. For the language modelling we trained on the publicly available fineweb dataset.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
httppssccppullicguudddeeeee http://gguudee/eeeeuuuubt... htte///ooeeeeeeeeeeeeeeee ceiiiinnoolcyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments 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 permitted.
6. Experimental setting/details
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?
Question:
Answer: [Yes]
Justification: The state-tracking and chomsky hierarchy experiments carried out synthetic data for which we provide the number samples which we used for training and testing in Appendices C. and C.2 For language modelling, describe all experimental
details Appendix C.3.I
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The state-tracking and chomsky hierarchy tasks are learnability problems for which we provide the best observed performance over 3 seeds for every setting we consider. For the language modelling, we carry out a single training per configuration as the experiments are costly.
41

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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 (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables fig- ures symmetric error bars that would yield results that are out of range (c.g.. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: Yes, see Appendix
Appendix
C.2 and Appendix C.3.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
42

---

Justification: Our work has neither immediate positive or negative societal impact, because it is foundational and theoretical in nature. Our language modelling experiments are only carried out on small scale leading to models which would not be usable in practice.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses 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 re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Yes, we build on three experimental setups of two other works and one li- brary. For state-tracking, we build on the experimental code used for (3] For the chomsky hierarchy experiments, we build on the code base of xl STM [9. We integrated our method into local copy of the flash-linear-attention library the code they provided.
22 All three works are credited for
43

---

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 the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: Our code is well documented and provides instructions how to reproduce the experiments. We provide checkpoints for the models we trained for language modeling.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and sereenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
44

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equíva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
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 LLM policy httrpe//ceauurieecc///ooeeeeeeee for what should or should not be described.
45


Reviews:
[{"review_id": "PcyBxAHeJP", "reviewer": "Reviewer_HNXg", "summary": "This paper introduces DeltaProduct, a novel linear Recurrent Neural Network (RNN) architecture that improves upon existing models like DeltaNet by enhancing state-tracking and expressivity. While DeltaNet's recurrence is interpreted as a single online gradient descent step per token, DeltaProduct performs multiple (nh) steps, resulting in a more expressive state-transition matrix formed by the product of nh generalized Householder transformations. This creates a diagonal plus rank-nh matrix structure, providing a tunable mechanism to balance expressivity with computational efficiency. The authors provide theoretical analysis showing that increasing nh improves the model's capacity for complex state-tracking, such as solving group word problems. Through extensive experiments, they demonstrate that DeltaProduct outperforms DeltaNet in both state-tracking and language modeling tasks, and exhibits significantly improved length extrapolation capabilities.", "questions": "None.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths :-\n\n- The paper constructs complex, non-symmetric state-transition matrices by composing products of simple, symmetric Householder reflections. This allows the model to learn rotational and oscillatory dynamics, crucial for advanced state-tracking, while mathematically guaranteeing stability since the operator norm remains bounded. \n- The paper demonstrates nice scientific rigor by not just showing that the model solves a task (S4 permutations), but by verifying how it solves it. Through model introspection, it provides strong evidence that the network learns the underlying geometric structure of the problem (the isomorphism to a cube's rotation group) exactly as predicted by theory.\n\nWeaknesses :-\n\n- The model's core design using Householder products enforces a strict norm ||A(xi)|| <= 1 on its state-transition matrix. While this guarantees stability, it is also a fundamental expressive bottleneck that prevents the model from performing norm-increasing operations, which are crucial for amplifying signals and are a key reason why competing models like RWKV-7 achieve stronger theoretical guarantees.\n\n- Increasing the model's expressivity via the hyperparameter nh (the number of Householder products) is inefficient. It leads to a linear growth in both model parameters and, more critically, the sequential computation time of the recurrence, making it nh times slower per token. This architectural choice limits the practical scalability of using a large nh to achieve higher performance.\n\n- The number of operations, nh, is a fixed, global hyperparameter. The model applies the same amount of costly computation to every token, regardless of its importance. This is wasteful for simple tokens (e.g., punctuation) and may be insufficient for complex ones (e.g., resolving a long-range dependency), representing a missed opportunity for adaptive computation that could allocate resources more efficiently.", "was_revised": true, "final_justification": "The authors' rebuttal, particularly the new experiments and the generalization of their framework, has addressed my initial concerns. The planned revisions will substantially improve the paper's quality and significance. Therefore, I have updated my recommendation.", "rebuttal": "We thank the reviewer for the feedback and address each point below.\n\n> The model's core design using Householder products enforces a strict norm ||A(xi)|| <= 1 on its state-transition matrix. While this guarantees stability, it is also a fundamental expressive bottleneck that prevents the model from performing norm-increasing operations, which are crucial for amplifying signals and are a key reason why competing models like RWKV-7 achieve stronger theoretical guarantees.\n\nWe agree this is a crucial trade-off. We intentionally designed DeltaProduct with Householder products to prioritize guaranteed stability ($\\Vert A(x_i)\\Vert \\leq 1$), a criterion for stable training on long sequences. This design choice directly contrasts with the potential instability of models like RWKV-7. As we demonstrate in Appendix B.6, the RWKV-7 recurrence becomes unstable in the very cases that grant it higher expressivity (i.e., when vectors $a_i$ vary per token); we show that the product of just two such matrices can have a spectral radius > 1.2.\n\nHowever, the core product-of-matrices mechanism we propose is flexible. It can incorporate other matrix families, including the norm-increasing ones from RWKV-7  Indeed, a minor extension of our theory, building on Merrill et al. (2024) (Theorem 5.2) and Peng et al. (2025) (Lemma 3), shows that this generalized framework has stronger theoretical guarantees. For instance, a single-layer model using $n_h = n$ RWKV-7 matrix products can recognize any regular language accepted by a finite state automaton with $n$ states, while if $n_h \\geq 2$, a three-layer model can recognize any regular language. We will add these results to the revised paper.\n\nTo validate this, we ran new experiments with products of RWKV-7 type state-transition matrices. We used $(\\mathbf{I} - 2 * \\mathbf{k} (\\mathbf{k} \\odot \\mathbf{a})^T)$ as state-transition matrix where $\\mathbf{k}$ is unit norm and $\\mathbf{a}\\in [0, 1]$ by transforming through a sigmoid. We find that a single layer using products of 2 RKWV-7 matrices obtains comparable results to DeltaProduct$_2$ on $S_3$. We will add new experiments for the other permutation groups using products of RWKV-7 state-transition matrices to a revised version of our manuscript.\n\n> Increasing the model's expressivity via the hyperparameter $n_h$ (the number of Householder products) is inefficient. It leads to a linear growth in both model parameters and, more critically, the sequential computation time of the recurrence, making it nh times slower per token. This architectural choice limits the practical scalability of using a large nh to achieve higher performance.\n\nWe see the linear increase in sequential computation with $n_h​$ as a tunable trade-off rather than a fixed limitation. Our experiments in Figure 8 show that a small increase in $n_h$​ (e.g., to 2 or 3) yields substantial gains in length extrapolation, making it a highly effective trade-off for many applications. Despite the theoretical linear increase in computational complexity, we find that in practice the training time increases sub-linearly with $n_h$ as shown in Figure 13 in Appendix C.4. The scaling-rate is also dependent on training sequence length and batch size and could be further improved by a custom triton kernel. After submission, we benchmarked the training throughput of the parameter-matched 805M parameter DeltaNet and DeltaProduct$_3$ on an improved implementation of our model with fused projections and causal 1d-convolutions (see also the response to reviewer RGKp). We find that DeltaProduct$_3$ achieves 86% (compared to our previous 75% without fusing projections and causal 1d-convolutions)  of the training throughput of DeltaNet at 4096 token sequence length and a per-device batch size of 12.\n\n> The number of operations, nh, is a fixed, global hyperparameter. The model applies the same amount of costly computation to every token, regardless of its importance. This is wasteful for simple tokens (e.g., punctuation) and may be insufficient for complex ones (e.g., resolving a long-range dependency), representing a missed opportunity for adaptive computation that could allocate resources more efficiently.\n\nThank you for the suggestion. Adaptive computation is a promising direction that could greatly enhance the model's efficiency by allocating computation dynamically. While this falls outside the scope of our current work, which focuses on establishing the fundamental properties of the Householder product structure, we agree it is a valuable avenue for future research. We will add a discussion of adaptive computation, such as using a Mixture-of-Experts (MoE) approach to select $n_h$ per token, to our future work section.\n\n\n### References:\nMerrill, W., Petty, J., & Sabharwal, A. (2024, July). The Illusion of State in State-Space Models. In International Conference on Machine Learning (pp. 35492-35506). PMLR.\n\nPeng, B., Zhang, R., Goldstein, D., Alcaide, E., Du, X., Hou, H., ... & Zhou-Zheng, C. (2025). Rwkv-7\" goose\" with expressive dynamic state evolution. arXiv preprint arXiv:2503.14456."}, {"review_id": "ATsSnbWw2j", "reviewer": "Reviewer_RGKp", "summary": "DeltaProduct extends DeltaNet by performing rank-n updates instead of rank-1, yielding state-transition matrices as products of generalized Householder transformations. This creates a principled mechanism to interpolate between diagonal matrices (efficient) and more expressive transformations while maintaining stability through an operator norm less than 1. The authors prove that DeltaProduct can solve symmetric group word problems with improved trade-offs and that Gated DeltaProduct recognizes any regular language with finite layers. \n\nExperimentally, DeltaProduct demonstrates superior performance on state-tracking tasks involving permutation groups and achieves dramatically improved length extrapolation in language modeling compared to DeltaNet, with minimal performance degradation on sequences beyond training context. The effective rank analysis reveals that multiple Householder products enable more efficient state forgetting mechanisms. The work provides both theoretical insights and practical improvements in synthetic reasoning and real-world language modeling tasks.", "questions": "I'm curious about a FLOPs comparison in the scaling analysis in Figure 10. To match parameters, the number of heads was reduced, but how do these variants compare w.r.t. FLOPs?\n\nDid DeltaProduct display any training instabilities? \n\nIn Figure 5 bottom 2nd and 4th plots, an increased number of layers seems to hurt performance on the state tracking tasks. You addressed it, but isn't this unexpected? Is there an explanation? Also, the number of layers is not consistent in that row, which reduces the readability of the figure as a whole.\n\nIn Figure 9, the Gated DeltaNet effective ranks are extremely jagged. Why is this?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper demonstrates exceptional scientific rigor with a clear, meaningful contribution that advances linear RNN research. The theoretical foundation is mathematically sound yet accessible through intuitive geometric explanations. The experimental validation is comprehensive, effectively combining synthetic state-tracking tasks with realistic language modeling benchmarks at an appropriate scale. The work exemplifies proper incremental research, extending DeltaNet in a principled direction that yields genuine improvements. The related work section is particularly thorough and well-organized, while the authors' commitment to reproducibility strengthens the work's impact. I consider the presentation quality to be outstanding throughout.", "was_revised": true, "final_justification": "The work is convincing, and after seeing the other review,s I'm even more certain about it. This work should be accepted.", "rebuttal": "We thank the reviewer for the positive feedback.\n\n> I'm curious about a FLOPs comparison in the scaling analysis in Figure 10. To match parameters, the number of heads was reduced, but how do these variants compare w.r.t. FLOPs?\n\nThis is a great question. The FLOPs of the recurrence scale linearly in $n_h$ such that the complexity is $O(n_h \\times (LCd + Ld^2))$ (Yang et al., 2024), where $L$ is the sequence length, $C$ is the chunk size and $d$ is the dimension of keys and values. The recurrence computation also requires $n_h \\times L/C$ sequential steps. However, in our setup the total FLOPs of the model are dominated by the large matrix multiplications in the input/output projections and the MLP, rather than the recurrence itself, and so, the contribution of the recurrence to total model FLOPs is minor. \n\nIn our parameter-matched scaling experiments (Figure 10 and Table 4), we adjusted the number of heads to equalize parameters. For instance, at the ~800M scale, we compare DeltaNet (16 heads) with DeltaProduct$_2$ (12 heads). The increase in FLOPs from the additional key/value projections and the doubled recurrence in DeltaProduct$_2$ is largely offset by the reduction in FLOPs from having smaller query, key, and value projections due to the fewer number of heads. Our results in Figure 13 in Appendix C.4 also support this. There we can see that for non-parameter matched models, the training throughput scales sub-linearly in $n_h$. We conducted additional throughput experiments with an improved model implementation that fuses the projection layers and causal 1d-convolutions. Here we find that DeltaProduct$_3$ with 805M parameters achieves 86% (compared to 75% without fusing projections and causal 1d-convolutions) of the training throughput of DeltaNet with 805M parameters at 4096 sequence length and a per-device batch size of 12 (on a NVIDIA H100-94GB). Moreover, we expect this to further improve with an optimized custom triton kernel (we are using DeltaNet’s). \n\n> Did DeltaProduct display any training instabilities?\n\nNo, we did not encounter any training instabilities with (Gated) DeltaProduct. We attribute this to the inherent stability of the recurrence, as the operator norm of the transition matrix is bounded by 1, which keeps the gradients well-behaved. The training loss curves for $n_h=1,2,3$ in Figure 14 of the supplementary material demonstrate this stability empirically.\n\n> In Figure 5 bottom 2nd and 4th plots, an increased number of layers seems to hurt performance on the state tracking tasks. You addressed it, but isn't this unexpected? Is there an explanation? Also, the number of layers is not consistent in that row, which reduces the readability of the figure as a whole.\n\nIndeed, increasing layers from 8 to 10 reduces performance for the $S_4$ and $S_5$ groups.  However, we see that these experiments are quite challenging and require multiple seeds to find a run that could fit the training context length of 128 permutations and show extrapolation to 512 permutations: we use 5 seeds per configuration yet sometimes still couldn't fit the context length. This observation reinforces our claim: increasing expressivity horizontally via $n_h$ offers a more parameter efficient and stable optimization path for these state-tracking tasks than increasing it vertically via depth. We thank you for pointing out the inconsistent legend labels in the colormap; we will fix the colormap in the revised figure to improve readability.\n\n> In Figure 9, the Gated DeltaNet effective ranks are extremely jagged. Why is this?\n\nBoth Gated DeltaNet and Gated DeltaProduct produce very jagged effective ranks. We found that both models learned to set the forget gate close to zero at the beginning of sequence tokens, effectively erasing the memory for the new sequence. Since the forget gate is a scalar for each hidden state per head the reset is very drastic.\n\n> line 42 should be an em-dash (https://en.wikipedia.org/wiki/Dash)\n\nThank you for pointing this out, we have fixed it in our manuscript.\n\nThank you again for helping us improve the paper.\n\n### References\nS. Yang, B. Wang, Y. Zhang, Y. Shen, and Y. Kim. Parallelizing Linear Transformers with the\nDelta Rule over Sequence Length. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Pa-\nquet, J. Tomczak, and C. Zhang, editors, Proceedings of the 37th International Conference on\nAdvances in Neural Information Processing Systems (NeurIPS’24), 2024"}, {"review_id": "uur6Z8DqbD", "reviewer": "Reviewer_bkha", "summary": "This paper addresses the fundamental trade-off between expressiveness and computational efficiency in State Space Models (SSMs). While diagonal SSM blocks are computationally tractable but limited in expressive power, and unstructured transition matrices offer full expressiveness at prohibitive computational costs, the authors propose a novel middle-ground approach. Their solution involves taking several rank-one steps for each token, effectively using low-rank transition matrices with rank equal to the number of steps.\n\nThe paper provides theoretical results proving the well-posedness and expressive power of the new SSM on state tracking tasks, supported by extensive experiments comparing against state-of-the-art competing architectures.", "questions": "### Notation and Consistency Issues\n\n- **Line 97**: The definition \"yi = x1 · x2 · · · xi\" is inconsistent with parts of the appendix where \"yi = xi ... x1\". For non-abelian products, this distinction is crucial. Please maintain consistency or clearly indicate when different conventions are used.\n\n### Direct Parametrization Questions\n\n- **Lines 184-188**: You have a couple of lines on direct parametrization of the low-rank structure. It is true that in the presented case (line 188) the matrix is restricted to be symmetric, but is there something blocking you from choosing the second ki to be different from the first? In that case there would not be any imposed symmetry. Is there some reason why you did not consider this?\n\n## Appendix Issues\n\n### Proposition 1\n\n- **Line 1034 (CRITICAL)**: In computing D explicitly, you appear to have omitted the term -4det(A). Fortunately, since (2-b1-b2)² - 4(1-b1)(1-b2) = (b1-b2)², the conclusion still holds. With this correction, you could derive explicit bounds on cos(θ).\n\n### Unclear Statements and Missing Information\n\n- **Line 1064 (Pedantic)**: Can this really model ANY product of Householders, or do restrictions on operator norm apply? This may be inconsistent with later comments.\n- **Line 1069**: \"The assumption on H0\" - which specific assumption are you referring to?\n- **Line 1073**: In the RMS formula, the xi terms need to be squared.\n- **Lines 1078-1082**: Please clarify this section as it's currently difficult to follow.\n- **Line 1084**: \"H_t^j = ei\" - the indices i and j are not quantified. Are they related? Can they be any possible tuple?\n\n### Theorem 3 Issues\n\n- **Lines 1117-1119**: Please expand for clarity. This is where the definition of m is crucially used as $m \\cdot n_h \\geq n - 1$.\n    \n- **Lines 1120-1127 (CRITICAL)**: This section requires substantial clarification as it's a crucial part of the proof but appears hastily written:\n    \n    - Line 1120: What do you mean by \"with enough information in xi about previous tokens\"?\n    - Lines 1121-1122: Please place this within your established framework (A, B, k, v, etc.). Why is x bold now? What are the matrices \"P_{lm+i}\" - these haven't been defined. Aren't the \"G_{l,m}...G_{l,i+1}\" functions on tokens coming after the current one? How is this information encoded in the tuple (Hi,xi)?\n- **Line 1128**: The 'a' should not be bold here.\n### Lemma 2 Concerns\n\n- **Line 1141**: Use clearer set notation: write \"2-d ≤ i ≤ 0\" instead of \"i ∈ {2-d, ..., 0}\".\n- **Line 1142**: Where does the bold 'a' come from? Is this the tuple (t mod d, a_{t-d+1}, ..., at)?\n- **Line 1145**: There is no j>1 since nh = 1.\n- **Line 1146 (Important)**: While claiming that the system can learn any function on the specified domain is technically correct, it seems somewhat disingenuous. What you actually prove is that your recurrence can memorize input up to a certain time, while learning is performed by a universal approximator in the decoder (e.g., MLP). Do you believe this occurs in practice, or can your system perform meaningful computation independently of decoder universality? This deserves discussion.\n\n### Theorem 4 Issues\n\n- **Line 1152**: Which specific isomorphism are you referring to?\n- **Line 1153**: \"that\" appears to be a typo.\n- **Lines 1159-1161**: Please cite this result - it's unlikely the intended audience is familiar with it.\n- **Lines 1162-1164**: Why recover y only at the last step? Shouldn't it be recovered at all steps according to your state tracking problem definition?\n\n### Lemma 3\n\n- **Line 1198**: \"exist\" should be \"exists\".\n- **Lines 1215-1229**: Same critical issues as found in Theorem 3.\n\n### Theorem 6\n\n- **Lines 1247-1248**: There are two (ii) labels and no (i); line 1256 should be (i).\n- **Line 1252**: Consistency issue with \"yi = x1 · x2 · · · xi\" as discussed above.\n- **Line 1265**: Is the angle clockwise or counterclockwise? To be pedantic the line passes from the origin to the POINT (1,0), this line in some sense is the vector (1,0) itself.\n- **Lines 1268-1269**: Mismatch between j and i indices in the last two θ expressions.\n- **Line 1270 (Important)**: When referencing \"standard identities of products of 2D rotations and reflections,\" clarify that these are matrix representations of the group as given in equation (5). You should consider placing this paragraph (1270-1275) at the beginning for clarity, then introduce the system. In general I believe this theorem lacks a paragraph giving intuition, explaining what d_0 and c_0 are supposed to represent, etc.\n- **Lines 1271-1272**: First line - d0 is not bold. Second line - need to prove \"H(π/m)d0 = R(π/m)d0\"; avoid ambiguous ± notation.\n- **Lines 1273-1274**: \"d0 = H(π/m)c0\" appears true but unproven. \"R(-2iπ/m)d0 = H(-2iπ/m)d0\" is not proven.\n- **Lines 1274-1275 (Critical Error)**: There appears to be an error in the last line. θ(sj, 0) - θ(s{m-i}, 0) = (-2m + 2(i+j))π/m since (2+2j)-(2+2(m-i)) = 2j - 2m + 2i = -2m + 2(i+j). The expression in R should be (-2m + 2(i+j))π/m instead of (2 + 2(i+j))π/m.\n\n### Additional Issues\n\n- **Line 1292 (Pedantic)**: \"When this property is not satisfied, the norm of the state will diverge exponentially fast to infinity.\" Does this not depend on how fast the norms diverge?\n- **Lines 1375-1377 and 1407-1411**: Using identical hyperparameters for different models without justification raises fairness concerns. How do you ensure fair comparison?\n\n\n## Recommendation\n\nThis paper tackles an important problem with substantial theoretical and empirical evidence supporting it. The approach is well-motivated and the experimental work is comprehensive. However, the seeming mistakes in the main proofs (particularly in Proposition 1, where it is not a typo) and unclear arguments in Theorem 3 and Lemma 3 prevent acceptance of the paper in its current form.\n\n**Path to Acceptance**: Please correct the identified errors in the proofs (or prove me wrong) and clarify the murky arguments in Theorems 3 and Lemma 3. With these corrections, I would raise my recommendation to at least a 5, as the underlying contribution is valuable and the work is otherwise very well-executed.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n1. **Thorough Theoretical Foundation**: The paper provides comprehensive theoretical backing for the proposed approach, with formal proofs of well-posedness and expressive power.\n    \n2. **Extensive Experimental Validation**: The experimental section offers comprehensive comparisons with state-of-the-art architectures.\n    \n3. **Clear Problem Motivation**: The paper tackles an important and well-defined problem in the SSM literature with a principled approach.\n    \n4. **Transparency**: The authors are transparent about both the limitations and strengths of their approach.\n    \n\n## Major Weaknesses\n\n1. **Errors in Main Proofs**: There are errors in key theoretical results that need correction, though these appear to be fixable without changing the main conclusions.\n    \n2. **Inconsistent Proof Quality**: Some proofs are hastily written and inconsistent with the rest of the paper, making them very difficult to follow and verify.\n    \n3. **Experimental Fairness Concerns**: The use of identical hyperparameters and training setups across different models without justification raises questions about fair comparison.", "was_revised": true, "final_justification": "This paper tackles an important problem with substantial theoretical and empirical evidence supporting it. The approach is well-motivated and the experimental work is comprehensive. Mistakes pointed out before rebuttal have been addressed and corrected.\n\n As the contribution is valuable I raise my score and recommend acceptance.", "rebuttal": "We greatly thank the reviewer for the thoughtful and thorough response and apologize for the lack of clarity, typos and small mistakes in the theoretical sections. We modified our draft incorporating the reviewer feedback, which greatly improved the clarity of the paper. After careful checking and as the reviewer points out, none of our theoretical results will change. Due to space constraints, we have to be concise in our response, but will be happy to provide any clarification during the discussion period. \n\n## Direct Parametrization Questions\nLines 184-188: The issue discussed in that paragraph concerns bounding the norm of the recurrence. If we choose the second key to be different from the first we cannot in general guarantee the recurrence stability even when $n_h = 1$, as explained in Appendix B.5 for RWKV-7 which also has two different keys. Please also see our first response to Reviewer HNXg, where we expand on the expressivity of RWKV-7 products.\n## Appendix Issues\n### Proposition 1\nThank you for identifying this error in Proposition 1. \nOur corrected proof shows that real eigenvalues are guaranteed if at least one $\\beta_i$ is in $[0,1]$ by proving the discriminant $D = [\\text{tr}(\\mathbf{A}_S)]^2 - 4\\det(\\mathbf{A}_S) \\ge 0$ where $\\mathbf{A} = \\mathbf{H}_2\\mathbf{H}_1$ and $\\mathbf{A}_S$ is the subspace spanned by the vectors $\\mathbf{k}_1$, $\\mathbf{k_2}$. \n- If one $\\beta_i \\in [0,1]$ and the other is in $(1,2]$, then $\\det(\\mathbf{A}_S) \\le 0$, which ensures $D \\ge 0$.\n- If both $\\beta_1, \\beta_2 \\in [0,1]$, the AM-GM inequality shows $\\text{tr}(\\mathbf{A}_S) \\ge 2\\sqrt{\\det(\\mathbf{A}_S)}$, which implies $[\\text{tr}(\\mathbf{A}_S)]^2 \\ge 4\\det(\\mathbf{A}_S)$ and thus $D \\ge 0$.\nHence complex eigenvalues only arise when both $\\beta_1, \\beta_2 > 1$.\n\nFollowing your suggestion, we computed explicit bounds on $\\cos(\\theta)$ for which complex eigenvalues occur: \n$$\n\\frac{(\\sqrt{\\beta_1-1} - \\sqrt{\\beta_2-1})^2}{\\beta_1\\beta_2} < \\cos^2\\theta < \\frac{(\\sqrt{\\beta_1-1} + \\sqrt{\\beta_2-1})^2}{\\beta_1\\beta_2}\n$$\nFor the special case of two reflections ($\\beta_1 =\\beta_2 =2$), this simplifies to $0 < \\cos^2\\theta < 1$, which holds whenever the keys are linearly independent but not orthogonal. \n\n### Unclear Statements and Missing Information\nLine 1078-1082: We agree that that section was difficult to follow. The general idea is that for the decoder to support our theoretical constructions, we need the map from all possible states of the RNN and the inputs to the decoder to be injective so that these can be distinguished by the MLP. There are two challenges to make this happen. The first is the dimensionality reduction via the scalar product with the query vector: the vector-valued state that we generally use would be compressed to a scalar after this operation. The second is the RMSNorm operation, which, in the case of a scalar input and $\\epsilon = 0$ (in practice also if too small) gives a binary output, so no matter how many states our RNN has, we only have two different inputs to the MLP input. Since for our construction the number of states that we use is always finite, by setting the query as $\\\\textbf{b}/||\\\\textbf{b}||$ and $\\epsilon > 0$ (In practice not too small) we can still guarantee injectivity despite these drawbacks. We’ll include a proof of this fact in the revised paper and we’ll be happy to clarify this further during the discussion period if needed.\nWe also noticed a small mistake: $\\\\textbf{b}$ should be defined as $\\\\textbf{b} = (b, b^2, \\\\dots, b^d)^\\\\top$ with $b \\geq \\\\delta_{\\\\max}/\\\\delta_{\\\\max} + 1$, $\\\\delta_{\\\\max} = \\\\max_{x,y \\\\in \\\\mathcal{S}} |x - y|$, $\\\\delta_{\\\\min} = \\\\min_{x,y \\\\in \\\\mathcal{S}, x \\\\neq y} |x - y| $ and $\\\\mathcal{S} \\\\subset \\\\mathbb{R}$ is the finite set of values of each element of the RNN state matrix. \n\nLine 1064: You are correct. The restriction on operator norm applies here. We’ll rephrase this in the updated version.\n\nLine 1069:  We will explicitly state which assumption: “Alternatively, the assumption on $ \\\\textbf{H}\\_0 $ (task-dependent with rank at most $n\\_h$)”.\n\nLine 1084: j is the index of the head, which is not related to the content of the hidden state which is $e_i$. We will write that $1 \\\\leq i \\\\leq d$ to make this clearer.\n\nLine 1073, Line 1128: Thank you, we corrected it.\n### Theorem 3\nWe agree with the reviewer that this section was not clear. We’ll expand and clarify it in the revised version. The main idea of the proof is to divide the tokens into blocks of $m$ matrices. The recurrence of the last layer computes the decomposition for the tokens in the previous blocks, while the current block is computed via the last layer decoder. We’ll be happy to provide further clarification and possibly the complete proof during the discussion period if needed.\n\nLine 1117-1119: We’ll rewrite as “We divide the input sequence into blocks of $m$ elements: we factorize the position $i \\in \\\\{1,\\dots t\\\\}$ into $ i = lm + \\\\tilde i$ where $l \\\\geq 0$ is the index of the previous block and $\\\\tilde{i} \\in \\\\{1,\\\\dots, m\\\\}$ is the position within the current  block (index $l+1$).”\n\nLine 1120: We explain what we mean by “with enough information in xi about previous tokens” later in the text (we’ll clarify this): each token of the last layer should contain the position modulo 2m and the last 2$m$ elements of the input sequence: including both the (partial) current and previous blocks. $x$ is now bold because it is the input of the last layer, which can be a vector, as opposed to the input to the model. It should be $P_{x_{lm+i}}$, not $P_{lm+i}$, we’ll fix it. The matrices $G_{l,m}...G_{l,i+1}$ are not functions of the tokens coming after the current ones because they are part of the “previous block” of tokens. The current block of permutations is computed entirely in the decoder via lookup-table.\n## Notation and Consistency Issues\nLine 97: Thanks for pointing this out, we will make the main paper consistent with the appendix by reverting the order, i.e. using $y_i = x_i \\\\cdot x_{i-1} \\cdots x_1$.\n### Lemma 2\nLine 1146: You are right to highlight the role of the decoder. Our theoretical constructions (as RWKV-7’s) rely on the universality of the MLP, whose required size grows with the complexity of the task (e.g., the group size). We’ll clarify this. The MLP complexity for complex groups with small values of $n_h$ is quite high since to learn $S_n$, the lookup table that it has to learn grows exponentially with $m=(n-1)/n_h$. Indeed, in our experiments (Figure 5 bottom row) the $S_5$ world problem cannot be learned when $n_h=1$ even with 10 layers. However it might be possible to learn the construction if $n_h$ is closer in value to $n$.\n\nLine 1141, 1142, 1145, 1153, 1198, 1247-1248, 1252, 1268-1269:  Thank you, we agree and we fixed the typos in our manuscript.\n\nLine 1265: The direction of the angle does not matter for the proof. We will change “vector” for “point” as suggested.\n### Theorem 4\nLine 1152: We will change the word isomorphism to the word assumption. From the context, it will be clear that we are talking about the assumption of the group being isomorphic to the orthogonal or rotation groups.\n\nLine 1159-1161: The fact that we only need products of $n_h$ Householder matrices to represent all elements in $SO(n_h + 1)$ when $n_h$ is even, is a consequence of the Cartan-Dieudonné theorem, which we already mention since it explains DeltaProduct’s expressivity, and the fact that now we are focusing on orthogonal transformations with determinant +1. The determinant of the product of matrices equals the product of the determinants and each Householder has determinant -1. Hence, an even number of Householders cannot be in $SO(n_h + 1)$. We’ll add this clarification.\n\nLines 1162-1164: The same reasoning can be applied at any step (not only the last one), we will change the index from t to i to highlight this.\n### Lemma 3\nLine 1215-1229: The proof for this will follow the same structure as our clarified proof for Theorem 3, and we will refer to it to maintain conciseness.\n### Theorem 6\nLine 1270: We have added an introductory part to the proof explaining the geometric intuition and defining the matrix representations of reflections and rotations upfront.\n\nLine 1271-1272: We’ll ensure that $d_0$ is always bold. The unproven equation can be directly derived from the definition $d_0 = (1,0)^T$ and the definitions of rotation and reflection matrices, given that the first column of a rotation matrix is identical to that of a reflection matrix (based on our notation).\n\nLines 1273-1274: We do not use that equality but just use the definition $c_0 =\\textbf{H}(\\\\pi/m)d_0$ here. See the above point for the proof of the second equation.\n\nLines 1274-1275 (Critical Error): You’re right, that was a typo, your expression is correct. The $-2m$ term can be removed due to the periodicity of the rotation matrix, yielding the desired result $\\textbf{R}(2(i+j))\\pi/m)$. We’ll fix this in the revised version. \n\n## Additional Issues\nLine 1292: Correct. We will revise to remove \"exponentially fast\".\n\nLines 1375-1377 (Chomsky Hierarchy): In our experiments, we compared against the results by Grazzi et al. 2025 for DeltaNet, Mamba and mLSTM / sLSTM. Our hyperparameters were chosen based on the ones found to produce the best results on the state-tracking experiments.\n\nLines 1407-1411 (Language Modeling): Due to compute budget constraints, we decided to use the hyperparameters used by Yang et al. 2024 for similar experiments.\n\n\n## References:\nGrazzi, R., Siems, J., Zela, A., Franke, J. K., Hutter, F., & Pontil, M. Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. ICLR. 2025\n\nYang, S., Wang, B., Zhang, Y., Shen, Y., & Kim, Y. (2024). Parallelizing linear transformers with the delta rule over sequence length. Advances in neural information processing systems, 37, 115491-115522."}]

Author rebuttal:

Meta-review: ***Summary:***

Linear recurrent neural networks are an area of active study for language models because they avoid the quadratic complexity of dense softmax attention in transformers.  Earlier models such as Mamba or GLA use a diagonal transition matrix, which limits their expressivity.  More recent models such as DeltaNet and RWKV-7 improve on certain tasks by using a diagonal plus rank-1 transition matrix.  In this paper the authors introduce a new LRNN, DeltaProduct, which extends DeltaNet by taking multiple steps per token.  The state-transition matrix thus becomes rank-N rather than rank 1, and is formed as a product of N generalized Householder transformations. 

The paper provides both mathematical proofs, and experimental results which demonstrate that the technique works. 

***Meta-review.***

The reviewers were unanimously in favor of accepting this paper, and I see no reason to disagree.  The content of the paper lies outside my area of expertise, but it seems to be well-written.  The reviews also seem to be careful and thorough.  

Reviewer HNXg thought that "the paper demonstrates nice scientific rigor", but was concerned that the use of householder products was a "fundamental expressive bottleneck."  However, the authors provided new throughput benchmarks, and a detailed explanation of the "stability vs. expressivity tradeoff" in their rebuttal, which addressed the reviewer's concerns.  

Reviewer RGKp had nothing but praise:  
* "This paper demonstrates exceptional scientific rigor with a clear, meaningful contribution that advances linear RNN research."
*  "The related work section is particularly thorough and well-organized."

Reviewer bkha did an exceptionally detailed review (thank you!), went through the paper and the proofs line-by-line, and found some errors in key theoretical results. However, the authors provided updated proofs during the rebuttal period.  In their final justification, reviewer bkha writes: "Mistakes pointed out before rebuttal have been addressed and corrected."

Given the attention to detail with which bkha reviewed this paper, I feel confident that the paper was fairly reviewed, and should be accepted.  However, given that none of the reviewer scores were above 5, it probably does not qualify for a spotlight or oral.
Decision: Accept (poster)