Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
Authors: MohammadReza Ebrahimi
Roland Memisevic
Venue: NeurIPS 2025 poster ()
Keywords: recurrent neural networks
bi-linear models
state tracking
length generalization
Primary area: deep_learning
TL;DR: We show that multiplicative (bi-linear) hidden state transitions are a natural choice for representing state tracking behavior in linear recurrent networks.

Abstract: The role of hidden units in recurrent neural networks is typically seen as modeling memory, with research focusing on enhancing information retention through gating mechanisms. A less explored perspective views hidden units as active participants in the computation performed by the network, rather than passive memory stores. In this work, we revisit bilinear operations, which involve multiplicative interactions between hidden units and input embeddings. We demonstrate theoretically and empirically that they constitute a natural inductive bias for representing the evolution of hidden states in state tracking tasks. These are the simplest type of tasks that require hidden units to actively contribute to the behavior of the network. We also show that bilinear state updates form a natural hierarchy corresponding to state tracking tasks of increasing complexity, with popular linear recurrent networks such as Mamba residing at the lowest-complexity center of that hierarchy.

Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
M.Reza Ebrahimi Qualcomm AI Research ebrahimi eqti qual comm, com
Roland Memisevic Qualcomm AI Research rmemi seemisev@tt... qualcomm. com
Abstract
The role of hidden units in recurrent neural networks is typically seen as modeling memory, with research focusing enhancing information retention through gating mechanisms. A less explored perspective views hidden units as active participants in the computation performed by the network, rather than passive memory stores. In this work, we revisit bilinear operations, which involve multiplicative interac- tions between hidden units and input embeddings. We demonstrate theoretically and empirically that they constitute a natural inductive bias for representing the evolution of hidden states in state tracking tasks. These are the simplest type of tasks that require hidden units to actively contribute to the behavior of the network. We also show that bilinear state updates form natural hierarchy corresponding state tracking tasks of increasing complexity, with popular linear recurrent networks such as Mamba residing at the cowest-complexity center of that hierarchy.
Introduction
State tracking is fundamental requirement for performing sequential decision-making tasks, in which future actions depend on the consequences of past actions. The consequences of past actions usually not directly observable, making state tracking key ingredient in virtually every real- world multi-step interaction between an agent and its environment. This includes multi-hop dialogue, end-to-end learned robot control, and recent "agentic LLM" use-cases, in which language model is trained to interact with an API.
While state tracking is an ill-defined concept in general, a common way to define it formally, which shall suffice for the purpose of this work, is treat it as the task of correctly representing the arbitrary-length sequence of states that state machine takes on in response to observing given sequence of inputs. This is equivalent to modeling Finite Automata (FA), or regular languages, in the Chomsky hierarchy of formal languages (Chomsky, 1956; Hopcroft et al., 2006).
Although state tracking is a seemingly simple task for neural networks learn, many models are surprisingly bad at learning it from data. The reason for its simplicity is that the task admits simple inductive decomposition: For each input in the sequence, it suffices update an internal representation of the state inferred from all inputs seen previously. As a result, it is possible, in principle, learn state tracking for sequences of arbitrary length by simply learning the appropriate state transitions for every (input, spaie)-pair from the training data.
However, in practice, this requires an inductive bias towards the input-by-input state update, which is not present in many models. For example, many popular sequence models, such as the Transformer cannot learn to perform state tracking (Dziri al., 2023; Anil et al., 2022; Abbe al., 2024) sequences longer than the training data. This includes very large, pre-trained Transformer-bast
"Qualcomm Al Research is an initiative of Qualcomm Technologies, Inc
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Bi-linear
few two Factored/Block Diag. Bi-linear
Complex Diagonal
Arbitrary State Machines
Real Diagonal
Modular Addition
Positive Diagonal
Parity
Abelian Groups
(eg. Mambal
Figure 1: Taxonomy of bilinear RNNs studied in this paper, along with example regular language tasks they can learn (in blue).
language models, and it is the case even when trained to use chain-of-thought reasoning ("inference- time compute") (e.g., Ebrahimi al. (2024)).
Similarly, as shown by Merrill et al. (2024), many linear recurrent networks fail to learn arbitrary- length state tracking tasks, which include large RNN-based pre-trained language models, such as Mamba (Gu and Dao, 2024), or the mLSTM (Beck et al., 2024). Recent work has shown that certain linear RNNs can learn some state tracking tasks, if the
sidennttt-idder transition matrix satisfies two conditions: (i) it is a function the input (and thus not time-invariaan invviiiiiann,...... and (ii) not all of its eigenvalues positive (Sarrof al., 2024; Grazzi et al., 2025). However, the tasks that can be learned under these conditions are highly restricted as we shall show. benefit of linear models, besides being amenable analysis, is that they be trained efficiently parallel hardware (e.g.. Martin and Cundy (2018)). This is in contrast to standard (non-linear) recurrent networks (RNNs), due to the linear dependence between hidden states across time-steps.
In this work, we revisit recurrent networks with bilinear hidden-to-hidden transitions. The transition matrix in these models is simple bilinear function of inputs and hidden activations of the previous time-step. Various types of bilinear recurrent models have been investigated in the past (c.g.. Sutskever et al. (2011); Downey et al. (2017); Wu et al. (2016)), but they have not caught models. This is in part due to instabilities and optimization difficulties owed to their inherent three-way way multiplicative interactions.
widely used
We show that bilinear RNNs are highly effective at learning state tracking tasks if one leverages few simple tricks to avoid instabilities during training and inference. This includes removing any additive components ("bias terms" and other additive contributions to the hidden state), such that the hidden state is true bilinear not affine function of the previous time-step hidden state and input. We also show that bilinear models form a natural hierarchy of decreasing complexity, ranging from fully unconstrained but parameter-inefffcieett models to highly constrained and parameter-efffiient models. The different model classes within the hierarchy correspond to increasingly narrow subclasses of regular language modeling tasks that be learned from data (see Fig. 1). Several existing linear RNNs, such as Mamba (Gu and Dao, 2024), are at the center the hierarchy, with no state tracking capability at all.
task that has received significant attention as a testbed for learning state tracking behavior with sequence models in the past is the task of computing the parity of binary bit string, We show that notable special case of learning bilinear state transitions without additive terms is that can learn parity task with frozen (untrained) recurrence and only training final readout layer training examples.
Figure shows an overview of bilinear models along with task classes we study in this work, ranging from simulating arbitrary state machines (the broadest class learnable by unconstrained bilinear models) to parity (the most narrow class, which can be learned even by models with real-valuee diagonal transition matrix). Further constraining the transition matrix to positive diagonal impedes model's 's ability to perform state tracking (see, e.g., Grazzi et al. (2025); Sarrof al. (2024)). We summarize our contributions as follows:
We revisit bilinear state transitions in RNNs and present an extensive study, showing that they can learn state tracking tasks, unlike many existing linear recurrent models, albeit with the caveat that they can have very large number of parameters.

---

We show that it is always sufficient (and in some cases necessary) for the hidden state to be pure linear not affine function of the hidden state the previous time-step. The absence of any additive terms makes hidden states scale-invariant, which in turn allows us to normalize hidden states during training and/or inference without sacrificing the linear recurrence.
We show that a pure linear (not affine) RNN with frozen random weights and trained linear readout layer can learn parity with perfect accuracy from only two training examples.
We show that linear RNNs with diagonal transition matrices are a special case limited to learning state tracking tasks with commutative structure. This restriction is true even for complex-value diagonal transition matrices. Hence, linear RNNs with block-diagonal transition matrices of size 2 are not able to learn general state machines (negative result).
Bilinear models have been studied extensively for unsupervised learning of trans- formations and relationships from data (Tenenbaum and Freeman, 1996; Olshausen et al., 2007; Memisevic and Hinton, 2010). Bilinear state transitions have also been discussed in the context of recurrent networks by Sutskever et al. (2011); Downey al. (2017); Wu al. (2016); Michalski et al. (2014). Besides the analysis. a key novelty in our practical results is the importance of using pure bilinear, not affine, state transitions. As special case of bilinear state transitions, we study the use of two-dimensional subspaces in which hidden units are transformed through rotations only. This is similar to existing, but non-linear, networks with complex-valleee vvaued or unitary transition matrices (e.g.. Arjovsky et al. (2016); Wolter and Yao (2018)).
Related work:
Recent work has shown that dependence of hidden state transitions on the inputs is necessary for a recurrent network to learn any state tracking behavior (Grazzi et al. (2025); Sarrof et al. (2024); Fan al. (2024)), although the connection to bilinear models is absent that work, and transition matrices are defined as neural network layers and include input-dependent additive terms (which we show to be detrimental learning). Terzić et al. (2025) propose a variant of state-space models where the transition matrix is constructed from an input-dependent linear combination of learned (but fixed) dense matrices, enabling some degree of length generalization on a set of regular language tasks. Bilinear models learn to encode hidden-to-hidden transitions as linear functions of the input, making them reminiscent of observable operator models and predictive state representations (Jaeger, 2000; Littman and Sutton, 2001).
2 Modeling hidden state dynamics using bilinear state transitions
A linear recurrent neural network represents sequence of observations x' E Rº via the temporal cvolution of vector of hidden variables (the "hidden state") h² E RH The most common form for modeling the temporal evolution is:
= = + Bx. + +b,
where A E HR is a hidden-to-hidden matrix, B E R is an input-to-hidden matrix modeling input-dependent additive terms, and & E I is a vector of additive input-independent biases.
Recently, it has been remarked that for recurrent network of the form Eq. (1) to be able to learn state tracking tasks, the hidden-to-hidde transformation A needs to depend on the input (Gu and Dao, 2024; Sarrof et al., 2024; Fan et al., 2024; Grazzi et al., 2025). The necessity for input-dependence has been motivated by showing, both theoretically and empirically, that models fail to learn state tracking tasks in the absence of the input-dependence. The exact form of the dependence of AA on x has been left open. Instead, it has been suggested to parameterize A(z) neural network.
We argue that a natural alternative for this dependence, while keeping the recurrence linear, is to make it multiplicative, such that hidden unit hy at time is function of the products h;- x of the components of the hidden state at the previous time-step and the inputs at the current time-step. The reason is that this makes explicit the input-dependent transformations between hidden states across time-steps, and thereby makes it natural to simulate a state machine, as we shall discuss below.
2.1 Simulating finite-state machines and group structures
finite-state machine (FSM), or finite automaton (FA), can be formally defined as a tuple (Q, Σ, 8, go), where Q is a finite set of states, Σ is a finite input alphabet, and é Q x Σ Q is
3

---

the state transition function. The machine starts in an initial state qo E Q. Given an input sequence {01, 12 02....,.Tr.. JT the FSM undergoes a sequence of state transitions {q) 191.92..... .r where each state qt is determined by q: = 5 ot). We shall define state tracking formally as the task of simulating state machine. A model said to simulate state machine S if, after observing the
complete input sequence it can produce the final state dr (see Deletang et al. (2023); Liu et al. (2023)).
As special case, we can consider state machines representing group structure. In this context, a group (G..). -), where denotes the group operation, can be modeled as an FSM where the set of states and the input alphabet are identical to the set of group elements, i.e., Σ = Q = G. The transition function is defined by the group operation itself: ([9 92) 91 92 for all 91 92 E G, representing the associative group operator with corresponding inverse and identity group elements.
Another important special case is that of abelian group, where the group operator is commutative. We consider integer groups under addition modulo m. denoted as Zm. In this case, the state set and input alphabet are Q Σ Zm {0, I...., m 1}. The transition function ō : Zm x Zm + Zm is defined by addition modulo m: 8(a, b) = (a + b) (mod m). for all a, b E Zm. Specifically, simulating the group 2n is equivalent to computing the parity of a binary input sequence. It is important to note that the operation of integer addition modulo m is the canonical commutative operation to consider, as all finite abelian groups are structurally similar (isomorphic) direct products of subgroups of Zm.
2.2 Bilinear RNNs can learn arbitrary state machines
Formally. we consider the hidden state h' to be bilinear function of the previous hidden state ht-1 and the current input x². As such, we model state transitions as:
h = ( W3 x²
Σ jk
Wisuath
where Was are the components of three-way way parameter tensor W E R with matrix W, E Id fx D denoting the i-th slice of the tensor. Note that Eq. (2) is equivalent to using an input-dependent transition matrix A.r such that:
ht = A,,''
with (Az);; = Σx Wa In other words, the state transition matrix A is fully parameterized through a linear transformation of the input æ. RNNs with bilinear state transitions (albeit typically in affine, not pure multiplicative form) have been studied previously (e.g., Sutskever et al. (2011) 1); Downey et al. (2017); Wu et al. (2016)).
We note that the multiplicative dependence, in particular in the absence of any additive contributions from the input, allows the inputs "route" the information flow in the hidden states, conversely represent transformations acting on them. The ability for layers in network to elicit transformations acting on other layers has been common motivation for studying trainable bilinear models in the past (c.g.,Ols Olshausen et al. (2007)). In the context of (2), it allows inputs to determine the temporal evolution of the hidden state (or elicit "computations" to be performed by the hidden layer), which is different from the somewhat more common view of the role of RNN hidden units as memorizing information. In the following we shall now make this perspective more concrete by showing that a bilinear RNN can simulate any state machine.
Proposition 1. The bilinear state transition model defined in Equation (2) is capable of simulating any finite state machine S = (Q, E, 5, go).
We refer to Appendix A. for the proof. Besides allowing inputs to encode transformations on hidden units, the absence of any additive terms in Eq. (2) makes the hidden units ccale-invarians In other words, (up to floating point accuracy) one can multiply a hidden state vector by a constant at any time-step and divide by the same constant a later time-step without any effect the final result. In Section 3 we shall show that the scale-invariance allows us to keep hidden activations stable during training and inference.
2.2.1 Factorized state transition tensor
The bilinear state update Eq. (2) utilizes a three-way parameter tensor W. whose H2 parameters often necessitate low-rank factorization for a more parsimonious model. One of the most common

---

factorization methods proposed in the literature is the Canonical Polyadic (CP) decomposition, also known as Parallel Factor Analysis (PARAFAC) (Hitchoock, 1927), which was used, for example, in the bilinear RNNs discussed in Sutskever et al. (201 I); Downey et al. (2017). The CP decomposition approximates the tensor as sum of R rank-1 tensors W Σ (h1)
(hta) w. which in whth) @ WT
terms of individual components, is expressed as: Wyyk Σ ( (o(h)) moler) Here, & denotes jr
the outer product, and vectors w, [kx)) (12)) and (x) are the component vectors for the r-th rank-1 term. These component vectors are collected as columns in the factor matrices ()(h)) E " w(kk) E T and W(x) E Px respectively. As a result, the total number of parameters reduced to R(2H D). The input-dependent state transition matrix Ag can then be expressed compactly as:
A = Wilh)ddag ((W()))Tz) (PV(Ha))T,
where input vector x E RRP and diag(.) constructs a diagonal matrix from a vector. As shown in Appendix C.3, an increasing number of factors (R), enables simulating state machines with larger states, as factored models with a larger provide a better approximation of a full bilinear model.
2.2.2 Block-diagonal state transition tensor
An alternative method for controlling the parameter count in the bilinear model involves imposing block structures on the effective state transition matrix Ag- This achieved by utilizing B distinct three-way parameter tensors, denoted as W H' xH' D one for each block {l,..., B.....,,. B}. Here, H'' H B represents the dimensionality of each block's corresponding state subspace, assuming H is an integer multiple of B.
Consequently, the overall state transition matrix A₂ adopts a dooko-diagnnal structure, where each diagonal block,
A!
(b) IH' xH' is generated from its respective tensor W)(6) via the relation
(Ae)) N3- = Ei with W As a result, the total number of parameters is reduced by a factor B. This block-diagonal parameterization can be conceptualized as employing B independent "heads", each processing distinct subspace of the hidden state vector using its own dense transition dynamics. It is reminiscent of block-diae diagonal transition matrices studied by Fan et al. (2024), albeit defining them as bilinear, non-additive function of the inputs.
2.3 Complex diagonal bilinear RNNs
In Section 2.2, we established that the bilinear state-transition form defines an input-dependent state-transition matrix Ar. whose entries are linear functions of the input parameterized by third-order tensor W. In this section, we discuss how diagonalizing the state-transition matrix, common simplification in many linear RNN variants, reduces a model's expressive capability to commutative operations.
First, consistent with common practice in the linear RNN literature (e.g., Orvieto et al. (2023)), we consider state- transitranntion matrices that are diagonalizable over the complex numbers. This focus is justified because the set of non-diagonalizable matrices has measure zero (Axler, 2024): consequently. any matrix A IR X can be made diagonalizable over C through an arbitrarily small perturbation of its entries (Zhinan, 2002). This implies that, based on the real Jordan Normal Form, the state- transition matrix A, can be expressed as:
A = P.D.P-11
(5)
where Pa E H is an invertible matrix and Dz E HR is a real block-diagonal matrix with (for complex conjugate pairs of eigenvalues + ib). Both Pa and D. are generally parameterized by the input x.
blocks of size 1x 1 (for real eigenvalues) or x of the form = a
particularly important special case is when the state-transition matrix A, is orthogonal. This is highly desirable for linear RNNs, as it ensures stability by guaranteeing that all eigenvalues of Az have unit norm, preventing exploding or vanishing states during recurrent updates. this scenario, the diagonal matrix Dz will be entirely composed of 2-dimensional rotation matrices, which we
[cos 0 sin 0
denote as R2 = sin 0 cos 0
5

---

A common simplification is to assume that the transformation matrix Pa is independent of the input (i.e.. P,= = P). This fixed matrix P can then be canceled out the recurrence steps and absorbed into the input and output transformations of the recurrent layer. The state dynamics are thus governed by A₂ = Da., which remains input-dependent and retains its block-diagonal structure, often simplified to purely diagonal with real, or even non-negative entries, e.g., in Mamba (Gu and Dao, 2024). 2
important to recognize that fixing P while Dr varies with the input implies that the overall state-transition matrices A₂ = PD,P-1 and A, = PD,,P- for different inputs I and will commute if and only if their corresponding block- dooao-na components Da and Dy commute. Thus this architectural choice inherently restricts the model to commutative transition dynamics (Terzić et al., 2025). In fact, model whose transition matrix Ar is directly parameterized as such a block- diagonal matrix A, = Dr (i.e., effectively P = I) can naturally represent operations from any abelian group, as we show the following proposition:
Proposition 2. A linear RNN of the form in Eq. (3) with orthogonal state-transition matrices Ar. that share a common, input-independent eigenbasis (i.e,, As = =PD, p-1 with fixed P) can simulate any abelian group (commutative operation).
We refer to Appendix A.2 for the proof. In Section 3.5, we also present a visualization of the invariant subspaces and rotation angles learned by the model.
2.4 Real diagonal bilinear RNNs
Finally, the block-diagonal transition matrix, Da., is often further simplified to be purely diagonal with real values; e.g., the RG-LRU cell utilized in the Hawk architecture (De et al., 2024). However, as noted by Grazzi et al. (2025), such models are incapable of learning modular addition.
Contrary to this limitation, we will show that learning parity is not only straightforward, but that it is in fact trivial for a linear RNN with real-valued diagonal state transitions which depend multiplicatively not additively æ. Length- generalization capabilities of sequence models (e.g., Anil et al. (2022); Grazzi et al. (2025)).
the parity task is widely used to test the state tracking
Proposition 3. A random network with frozen real-diagonal transition matrix (without additive terms) and learnable linear readout layer learns parity with probability 1 - 2-H, H for arbitrary sequence length from only? 2 training examples of odd and even parity.
Freezing the recurrent weights turns the network effectively into a bilinear variant of an echo state network (Jaeger, 2007; Maass et al., 2002). Our result shows that an echo state network with state transitions depending only mulriplicarively on the input learn parity. We shall show experimental results confirming this result in practice in Section 3.4. This is in contrast to models like Mamba (Gu and Dao, 2024), in which state transitions diagonal and positive, and which can therefore not learn parity even when adapting recurrent parameters during learning (Grazzi et al., 2025).
3 Experiments
Tasks: To evaluate the state- saatetraackig capabilities of the bilinear RNN model variants introduced previously, we use the following three tasks: modular addition, random state machine, and modular arithmetic. In the modular addition task, the model processes sequence of integers, each randomly drawn from the set 2,m = {0. ... m 1}. and is required to predict their sum modulo m. For the random state machine task, the model must simulate a randomly generated finite-state machine where both the input alphabet Σ and the set of states Q are identical to 2m, and for each E Q, the transition function is set to 8(g. o) = n., (o), where Ty is a random permutation of Σ. Finally, the modular arithmetic task involves processing sequence alternating between integers from Z,,, and arithmetic operators (from the set {+, x, )); the model must compute and output the result of these operations, applied sequentially, with all calculations performed modulo m. For all tasks, multi-digit integers are tokenized into single tokens. We refer the reader to Appendix B.1 for examples and additional details on each task.
Models: We compare full, factored, and block-diagonal bilinear models against several baseline architectures: non-lineat RNNs including LSTM (Hochreiter and Schmidhuber, 1997) and Elman
Note, however, that this restriction may not be as problematic when additive terms present.

---

RNN (Elman, 1990), Mamba, and Transformer models. All RNN- based models (including the bilinear, and non-linear ones) have a single recurrent layer followed by linear classification head over the hidden states. For the Mamba and Transformer baselines, we evaluate configurations with 2, and layers. A consistent hidden and input dimensionality of 256 used across all models. Further details of the experimental setup are provided in Appendix B.
Recurrence stability: The absence of additive terms in recurrent formulation of Eq. makes the introduced bilinear hidden states scale-invariant as discussed above. For inference, we can therefore normalize hidden states during the recurrence, while not doing so during training, without introducing any inconsistency between training and inference.
3.1 Main results
We trained the models described above on the three tasks, instances of lengths 2-10, and evaluated on instances of length 500. The training is done for 100,000 steps, where at each step 64 samples (of length 2-10) generated for the task. Each model is trained using three different learning rates and picked the best-performing model. Table summarizes the main results. In all tables, we scale accuracy values such that 0 represents random chance, and is perfect accuracy.
We observe that bilinear models generally perform best across all tasks. Bilinear block-diagonal variants exhibit improved performance as the block size increases. Notably, the real-diagonal model (a bilinear block-diagonal model with block size 1) can only learn parity (i.e., modular addition with m 2); however, increasing the block size to two enables the learning of modular addition for larger values of m, as demonstrated in Proposition 2. Also, the R₂ block-diagon model explicitly parametrizes the state transition matrix as rotation blocks of the form R2, with angles parameterized by inputs. In contrast, a dlock-diagonal bilinear with block size of parametrizes 2D-blocks freely from the input.
Non-linear recurrent models, such as LSTM and simple RNN, also perform well on these state- tracking tasks. It can be speculated that multiplicative interactions between hidden states and inputs arise from the gating mechanisms and non-linear activation functions within their recurrent structures. While Mamba can learn the tasks in-distribution for small state sizes m. it largely fails to generalize to longer sequences. Also, the failure of transformers observation in the literature.
magtt-genneralization is a well-known
Note that in Table we used a consistent hidden dimension of 256 across all models. Appendix C.I. we report the performance of models matched in parameter count by adjusting their hidden dimensions. In addition, Appendix C.2 presents results for simulating dihedral groups with various models.
3.2 Data Efficiency
We showed in the previous section that bilinear models are effective at learning state tracking tasks. However, since the number of parameters grows the product of the input embedding and hidden dimension, their parameter counts can be extraordinarily large. While this may prove to be unproblematic in large-scale multi-task and language modeling tasks, data efficiency is a concern.
To gain insights on the data efficiency of bilinear models, we train and evaluate the models on the tasks discussed in the previous section, using fixed training set sizes. We also compare to LSTM. All models were trained on an imput sequence length of 10, using the optimal Icarning rate found in the previous experiment. The results are shown in Figure 2. They show that despite the large number of parameters, the models are not less data efficient than the LSTM. This is true even of the full bilinear model (denoted "Bilinear" in the figure).
3.3 Multiplicative versus additive interactions
Our results on bilinear models are based solely on pure bilinear transformations, such that hidden units do not have any additive bias terms or any other additive dependencies on the inputs. Our results imply that such pure bilinear transformations are sufficient for learning state tracking tasks. In the following experiment, we study the performance of models with and without additive terms, and we show empirically that for some models, the absence of additive terms also necessary (performance degrades in the presence of additive terms).
7

---

Table 1: In-distribution and length-generaan generalization performance (normalized such that 0 indicates random chance) of various models on three state tracking tasks: modular addition, simulating random state machines, and modular arithmetic. Bilinear models outperform others, with block-diagonal variants improving as block size increases. Non-linear recurrent models (LSTM, RNN) also perform well, whereas Mamba and Transformer struggle with long-sequence generalization.
Validation Accuracy (Length 2-10)
OOD Accuracy (Length 500)
Modulus/ / State Size
2
10
25
50
2
10
25
50
Modular Addition
Bilineur
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Factored Billincar
1.00
1,00
1.00
1.00
1.00
1.00
1.00
1,00
1.00
1.00
1.00
0.95
1
1.00
0.96
0.88
0.85
0.45
0.32
1.00
0.00
0.00
0.10
0.00
0.02
Block Diag.
2
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
(block
8
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
R2 Block Diag.
1.00
1.00
1.00
1.00
1.00
1.00
0.66
0.00
LSTM
1.00
1.00
1.00
1.00
1.00
0.99
1.00
1.00
0.98
1.00
0.00
0.02
RNN
1.00
1,00
1.00
1.00
1.00
1.00
1.00
1,00
1.00
0.98
0.37
0.07
0.99
0.92
0.96
0.85
0.74
0.61
0.00
0.01
0.01
0.00
0.00
0.00
Mamba
2
1.00
1.00
1.00
1.00
1.00
1.00
0.00
0.02
0.01
0.00
0.00
0.00
(layers)
1.00
1.00
1.00
1.00
1.00
0.47
0.01
0.01
0.00
0.01
0.00
0.00
1.00
1.00
0.47
0.19
0.03
0.01
0.01
0.00
0.00
Transformer
1.00
0.00
0.00
0.00
(layers)
4
1.00
1.00
1.00
0.99
0.02
0.04
0.00
0.00
0.01
0.00
State Machine
Billnear
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Factored Billnear
1.00
1.00
1.00
1.00
1.00
0.19
1.00
1.00
1.00
1.00
1.00
0.01
1.00
0.28
0.20
0.14
0.09
0.07
1.00
0.03
0.00
0.00
0.00
0.00
Block Diag.
0.15
0.02
(block size)
1.00
1.00
1.00
1.00
0.48
0.21
1.00
1.00
1.00
0.41
0.13
0.04
64
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Rs Block Diag.
1.00
0.29
0.19
0.11
0.07
0.02
1.00
0.00
0.00
0.00
0.00
0.01
LSTM
1.00
1.00
1.00
1.00
1.00
0.30
1.00
1.00
1.00
1.00
0.64
0.09
RNN
1.00
1.00
1.00
1.00
0.41
0.188
1.00
1.00
1.00
0.99
0.19
0.07
1.00
1.00
0.96
0.55
0.34
0.19
0.00
0.99
0.87
0.31
0.16
0.07
Mamba
1.00
0.09
(ayers)
1.00
1.00
0.99
0.41
0.03
0.97
0.17
0.10
1.00
0.94
0.83
0.46
0.27
0.18
0.03
0.01
0.02
0.01
0.00
0.00
Transformer
2
1.00
1.00
0.97
0.61
0.39
0.17
0.01
0.01
0.01
0.01
0.00
0.00
(layers)
4
1.00
1.00
1.00
0.84
0.49
0.17
0.00
0.02
0.01
0.00
0.00
0.00
Modular Arithmetic
Bilinear
1.00
1.00
1.00
1.00
1.00
0.99
Factored Bilincar
1.00
0.34
0.90
0.09
0.03
0.03
1.00
0.24
0.37
0.06
0.04
0.03
0.60
0.30
0.24
0.27
0.16
0.14
0.19
0.15
0.09
0.11
0.04
0.03
Block Diag.
2
0.99
0.77
0.53
0.52
0.27
0.21
0.37
0.00
0.08
0.12
0.03
0.05
size)
8
1.00
1.00
1.00
1.00
0.54
0.47
1.00
1.00
0.41
0.24
0.06
0.08
64
1.00
1.00
1.00
1.00
1.00
0.66
1.00
1.00
1.00
1.00
0.40
0.21
R. Block Diag.
0.61
0.34
0.21
0.23
0.03
0.04
0.02
0.00
0.04
0.01
0.02
0.03
LSTM
1.00
1.00
0.90
1.00
1.00
1.00
0.64
RNN
1.00
0.22
1.00
0.16
0.99
0.83
0.56
0.59
0.24
0.14
0.74
0.55
0.29
0.32
0.08
0.08
Mamba
2
1.00
0.99
0.80
0.93
0.35
0.33
0.85
0.38
0.41
0.29
0.11
0.07
(aayers)
4
1.00
1.00
0.99
0.99
0.55
0.29
0.92
0.75
0.48
0.51
0.17
0.09
0.88
0.63
0.46
0.32
0.10
0.08
0.19
0.02
0.04
0.01
0.03
0.01
Transfommrr
2
1.00
0.97
0.81
0.32
0.11
0.08
0.19
0.15
0.05
0.04
0.02
0.01
(aayers)
1.00
0.75
0.32
0.08
0.19
0.12
0.03
0.03
0.02
0.03

---

Mod. Addition
State Machine
Mod. Arithmotic
Toin Sumples
Trii Samples
Sumples
Madalos
Bilinear
8 5
Factored Bilinear
Masnlos
256 Becwrs
-200
8
0.8
Block Ding. Bilinear
Mobhin
32 blocks slse
-00K
5
0.5
Block Diag. Bilinear
Mohius
5
-IM
Malnnax
LSTM
500K
on 8 E
0.0
RNN -135K
Miainls
13 3
Data efficiency comparison between bilinear models and LSTM/RNN state tracking tasks. All models were trained on sequences of length 10 and evaluated on length 500, with varying training set sizes. Despite their large parameter counts, bilinear models including the full variant, exhibit better data efficiency compared LSTM.
Figure 2:
Figure 3 (left) shows the OOD performance of real diagonal, 2D block-diagonal, and full bilinear models on the modular addition tasks discussed previously. As observed, and in line with the proposed hierarchy, the diagonal model is only capable of learning the parity task (only when the additive terms are excluded), and the 2D block-diagon diigonia model can learn modular addition (again only without the additive terms). In contrast, additive contributions do not affect performance for the bilinear model. For a more comprehensive set of experiments and additional discussion on the effect additive terms, refer Appendix C.4.
3.4 Learning parity with random network
Figure (right) shows the OOD performance (testing length 400, best across seeds and 2 learning rates) of this type of model, after training sequences of lengths 10 - 50. It shows, in line with the theoretical result, that the pure bilinear model can solve the task, even though recurrent parameters frozen during training (only the readout layer is trained). It also shows the detrimental effect of additive terms for comparison.
Figure 3: (Left) Effect of (input-dependent) additive terms in the hidden state update rule on the OOD accuracy of modular addition task. (Right) Length generalization performance on parity with random multiplicative RNN with and without additive terms.
Effect of Additive Terms in Recurrence
Performance of Frozon Random Network Parity
Datasct
Parity
Modular Addition
Training Examples
2
100
Modulus
10
25
Training Length
10
20
50
10
50
Model
Additive Terms
Additive Terms
Real Diag.
No
1.00
0.01
0.00
0.00
0.00
Input Dependent
0.05
0.07
0.05
0.03
0.05
0.01
2D Block Ding
0.00
Input Dep. Constant
0.06
0.03
0.06
No
1.00
1.00
1.00
1.00
0.98
Constant
0.01
0.06
0.05
0.87
0.71
0.01
1.00
Bilinear
No
1.00
1.00
1.00
1.00
1.00

---

3.5 Representing commutative tasks by rotating phase angles
Figure 4 illustrates the rotation angles learned by the R2 block-diagonal model for the modular addition task with m = 10. The figure displays these angles for each input integer (0, 1..... 9) across several 2-dimensional hidden state subspaces (12 out of 128). These subspaces are ordered based the magnitude of the weights associated with these in the linear readout layer. The harmonic value, reported for each subspace, is calculated 02 /mm, where 0 is the learned rotation angle for the input integer 1 (rotation angles for other integers are multiples of 0, in the representations learned by the model). This harmonic value indicates how closely 0, aligns with an integer multiple of the fundamental angle 2 m required for ideal cyclic group representation.
125
42
1200
62*
135P
112*
45*
[1] Hanzooi
[21 Huttoano
[3l Hortasoo
[el Hesmona'2
5
200
300P
310"
200"
6
(6] Homoooi
Hormooo
Hermorio
Hermonnc
100 3.57
B66:2.0
jerr
Soe
0
325
2250
2257
312
225
117
201
D0'
105*
15'
1207
45*
132
47*
132*
(i) Hummonic 5
[:0] Hacmsric
[:3] Harmenic
(12) Harmatic
180
9.9
1004
2000
2000
270-
Figure 4: Visualization of the rotation angles learned by the R2 block-diagonal model for each input integer in the m 10 modular addition task. Each subplot corresponds to a distinct 2-dimensional hidden state subspace. These subspaces are ordered based on the magnitude of the classifier weights. The "harmonic" is 9, where 0 is the learned rotation angle for the integer 1. 24/m:
4 Discussion
Our work shows that models in which hidden states depend bilinearly on previous hidden states and inputs can learn state tracking tasks. This is contrast to many linear RNNs, such as Mamba (Gu and Dao, 2024), LRU (Orvieto et al., 2023), and others. It can also be viewed as extending upon the studies by Grazzi et al. (2025); Sarrof et al. (2024); Fan et al. (2024) to improve state tracking behavior beyond that work. However, it is important to note that bilinear models come at the cost of the number of hidden states. Whether there are
parameter count that grows roughly cubically ways to reduce the number of parameters while retaining strong performance across wide range of state tracking tasks an important question for future research. A closely related question whether such a reduction may be counterproductive (or conversely the large number of parameters even be beneficial) in massive multi-task scenarios such as language modeling, which possible with linear models due to the possibility for efficient, parallel training.
10

---

References
E. Abbe, Bengio, Lotfi C. Sandon, and Saremi. How far can transformers reason? the globality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, pages 27850-27899 2024.
C. Anil, Y. Wu, Andreassen, A. Lewkowycz, V. Misra, Ramasesh, A. Slone, G. Gur-Ari, E. Dyer, and B. Neyshabur. Exploring length generalization in large language models. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 38546-38556, 2022.
M. Arjovsky, A. Shah, and Y. Bengio. Unitary evolution recurrent neural networks. Proceedings of The 33rd International Conference on Machine Learning (ICML), volume 48 of Proceedings of Machine Learning Research, pages 1 1120-1128. PMLR, 2016.
Axler. Linear Algebra Done Right. Springer Nature, 4th edition, 2024.
M. Beck. Pöppel, M. Spanring, Auer. O. Prudnikova, M. Kopp, Klambauer, Brandstetter, and S. Hochreiter. xLSTM: Extended long short-term memory. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024.
N. Chomsky. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113-124, 1956.
S. De. S. L. Smith, A. Fernando, A. Botev, G. Cristian-Muraru, A. Gu, R. Haroun, L. Berrada, Y. Chen, S. Srinivasan, al. Griffin: Mixing gated linear recurrences with local attention for efficient language models. arXiv preprint arXiv:2402.. 19427, 2024.
G. Deletang, A. Ruoss, J. Grau-Moya, T. Genewein, I.. K. Wenliang, E. Catt, C. Cundy, M. Hutter, S. Legg, J. Veness, and P. A. Ortega. Neural networks and the chomsky hierarchy. In Interna- tional Conference on Learning Representations (ICLR), 2023. URL attpss//opeereviit net/ dorum/idd=WbHAAzkeeee
C. Downey, A. Hefny, B. Boots, J. Gordon, and B. Li. Predictive state recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
N. Dziri, X. Lu, M. Sclar, X. Li, L. Jiang, B. Y. Lin, S. Welleck, West, C. Bhagavatula, R. Le Bras, J. Hwang, S. Sanyal, X. Ren, A. Ettinger, Z. Harchaoui, and Y. Choi. Faith and fate: Limits of transformers on compositionality. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pages 70293-70332, 2023.
M. Ebrahimi, S. Panchal, and R. Memisevic. Your context is not array: Unveiling random access limitations in transformers. In First Conference on Language Modeling (COLM), 2024. URL https://openreviiee
J. L. Elman. Finding structure in time. Cognitive Science, 14(2):179-211 1990.
T.-H. Fan, T.-.. Chi, and A. I. Rudnicky. Advancing regular language reasoning in linear recurrent neural networks. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 45-53, 2024. URL https://
aclanthology org/2024.
R. Grazzi, Siems, J. K. Franke, A. Zela, F. Hutter, and M. Pontil. Unlocking state-tracking in linear RNNs through negative eigenvalues. In Proceedings of the Thirteenth International Confer- ence on Learning Representations (ICLR), 2025. URL /ttp:////////./ee//////// wwt.:/rumtffei.c.....m.e UVTo3tVBk2.
A. Gu and T. Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling (COLM), 2024. URL https:// www.ranrrrwiiiieeeoorn.o... net/forum? id=tEYskw1VV2.
F. L. Hitcheock. The expression of a tensor or polyadic as sum of products. Journal of Mathematics and Physics, 6( 1644419644-189, 1927.
Hochreiter and Schmidhuber. Long short-term memory. Neural Computation, 9(8): 1997.

---

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison- Addison-Wesley, 3rd edition, 2006.
H. Jaeger. Observable operator models for discrete stochastic time series. Neural Computation, 12 (6):1371-1398, 2000, doi: 10.1 10.1162009976603001541.
H. Jaeger. Echo state network. Scholarpedia, 2(9):2330, 2007. doi: 10.42499scholaappcdia. 2330.
H. Kurzweil and B. Stellmacher. The Theory Finite Groups: An Introduction. Springer, 2004.
M. Littman and S. Sutton. Predictive representations of state. In Advances Neural Information Processing Systems (NIPS), volume 14, pages 1001-1008, 2001.
B. Liu, J. T. Ash, S. Goel, A. Krishnamurthy, and C. Zhang. Transformers learn shortcuts to automata. In International Conference on Learning Representations (ICLR), 2023. URL https: //openreview wwwpteruum dtt.ooommmddddddgiiiiiii.
W. Maass, T. Natschläger, and H. Markram. Real-time computing without stable states: A new framework for neural computation based on perturbations. Neural Computation, 14(11):2531-256) 2002.
E. Martin and C. Cundy. Parallelizing linear recurrent neural nets over sequence length. In Inter- national Conference on Learning Representations (ICLR), 2018. URL https://openrevvir. net/f htt.fooruunddd-HUuuuul.....
R. Memisevic and G. E. Hinton. Learning to represent spatial transformations with factored higher- order Boltzmann machines. Neural Computation, (2(6):1433-142. 2010. doi: 10.1162/neco. 2010.01-09-953.
W. Merrill, J. Petty, and A. Sabharwal. The illusion of state in state-space models. In Proceedings of the 41st International Conference on Machine Learning (ICMI., pages 35492-35506. PMLR, 2024.
V. Michalski, R. Memisevic, and K. Konda, Modeling deep temporal dependencies with recurrent grammar cells. In Advances in Neural Information Processing Systems (NIPS), volume 27, pages 1925-1933. Curran Associates, Inc., 2014.
B. A. Olshausen, C. Cadieu, J. Culpepper, and D. K. Warland. Bilinear models of natural images. In B. E. Rogowitz, N. Pappas, and S. J. Daly, editors, Human Vision and Electronic Imaging XII, volume 6492, page 649206. International Society for Optics and Photonics, SPIE, 2007.
A. Orvieto, S. L. Smith, A. Gu, A. Fernando, C. Gulcehre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 26670-26698. PMLR, 2023.
A. Radford, J. Wu, R. Child, D. Luan, Amodei, and I. Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAl, 2019. URL https://openal com/ com/research/ better-language models.
Y. Sarrof, Y. Veitsman, and M. Hahn. The expressive capacity of state space models: formal lan- guage perspective. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024. URL https: http::///peeeeieeeeeeeee net/forum? net/fooummPdd=eV5yrrraa id=
I. Sutskever, J. Martens, and G. Hinton. Generating text with recurrent neural networks. In Pro- ceedings of the 28th International Conference on Machine Learning (ICML), pages 1017-1024, 2011.
J. Tenenbaum and W. Freeman. Separating style and content. In Advances in Neural Information Processing Systems (NIPS), volume pages 713-719, 1996.
A. Terzić, M. Hersche, G. Camposampiero, T. Hofmann, A. Sebastian, and A. Rahimi. On the expressiveness and length generalization of selective state-space models regular languages. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 20876-20884, 2025.
12

---

M. Wolter and A. Yao. Complex gated recurrent neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, pages 10162-10173, 2018.
Y. Wu, S. Zhang, Y. Zhang, Bengio, and R. R. Salakhutdinov. On multiplicative integration with recurrent neural networks. In Advances in Neural Information Processing Systems (NIPS), volume 29, pages 1334-1342 2016.
Z. Zhinan. The jordan canonical form of rational random matrix. Science Direct Working Paper, (41574-0358):44,2)) 2002.
13

---

A Proofs
A.1 Proof of Proposition
Proposition 1. The bilinear state transition model defined in Equation (2) is capable of simulating any finite state machine S = (Q, Σ, (.))
Proof. Given any state machine S (Q, 6,,,00)) qo): and for all inputs E Σ, we define the state transition matrix A, E (0,1)(0)x12)) with the (i. (i.j)-th element given by:
(An).s {
if 8( q;.
(6)
otherwise.
This means that if the state machine is in state gÿ and and receives input a, the one-hot representation of the next state is precisely the j-th column of Ag. Consequently, if E Q is the state at time and he E {0, 13141 is its one-hot encoded representation. the state dynamics can be expressed as:
gr 5(4
Am.
To demonstrate that the bilinear statc-transition form from Eq. (2) can represent any state machine, it suffices to show that the third-order tensor W can be constructed such that its resulting state transition matrix Ar equals A, for every a E Σ, where x is the embedding corresponding to a.
Without loss of generality, let the input alphabet be Σ {1, [EI).
We define the input embedding (0, 1 as the one-hot vector for the current input symbol Σ (thus, the input dimension is effectively [E). The third-order tensor W is then constructed such that for each Σ, the slice W... is equal to the state machine's ' transition matrix A.. From Eq. (3), will have:
(Ar) = - = Wigo (Da)
(8)
This because x is the one-hot vector for input symbol a (meaning 2y if and Te = 0 otherwise). Therefore, this construction yields Ar A.. Consequently, the state-transition dynamics of the bilinear model, h² = A become equivalent to those of the state machine, h An.h" --
A.2 Proof of Proposition 2
Proposition 2. A linear RNN of the form in Eq. (3) with orthogonal state-transition matrices A that share a common, enput-independent eigenbasis (i.e., Ag = PDDPP1 witt fixed P) can simulate any abelian group (commutative operation).
Proof. We show by construction that bilinear model with state transition matrix that is block- diagonal with R2 rotation blocks can represent modular addition, and hence any cyclic group. Based on the fundamental theorem of finite abelian groups, every finite abelian group be expressed as the direct sum of cyclic groups (typically of prime-power order) (Kurzweil and Stellmacher, 2004). Therefore, any model capable of simulating modular addition can, in principle, simulate any finite abelian group.
First, let's clarify how orthogonal transition matrix simplifies to a block-diagonal form composed of 2-dimensional rotation blocks. (Further details are available in Section 2.3). Based on the Real Jordan Normal Form, orthogonal matrix A, is similar real block-diagonal matrix D, (Axler, 2024). This means:
A =
where Pa "Il the invertible transformation matrix, and D. E " is real block-diagonn matrix composed entirely of 2-dimensional rotation matrices (assuming H is even), which we denote
R2( = cos 0 sin
(10)
sin 0
cos 0
14

---

Now, if the transformation matrix Pa is independent of the input (i.e., P= P), the fixed matrix P can be canceled out in the recurrence steps and absorbed into the input and output transformations of the recurrent layer. Therefore, for an orthogonal transition matrix with such input-independent transformations, we can effectively model Ar as being niak-aiagona,, with its blocks being dimensional rotation matrices R2 (f(z)), where the rotation angles ((z) are parameterized by the input æ.
Next, we present a simple construction with // = 2 (i.e., A. = R2(0(z)) that simulates modular addition. Let To be the embedding corresponding
an input integer E 2m {0. 1...., 1}.
We define the rotation angle for input a as ((xa) = 2 Consequently, after observing sequence of inputs a², _0?, .."......" o", the hidden state vector R2² (with initial state ho) evolves as follows:
ht = AArh" = A, Agr
(11)
= RR (0 (xx)
R2 (0 (x())) ...
... (0 (x7)) 10
(12)
R₂
θ (x')
h
(13)
2 2
R2
ho
(14)
m
T
2
R2 (6) = R2 (6 mod 2T))
= R2
mod 2
4t
(15)
m
T
2x
(2tr ( mod 2xr = (o mod m) ())
R₂
mod m
ho
(16)
Let y = 1E o²) mod m be the target sum modulo m. This means h.T is h rotated by 2m
m y:
2
T
= R2
R0
(17)
Finally, since this rotation is unique for every possible value of E 2m. a linear readout layer (i.e.. an m-class linear classifier) can perfectly extract y from h":
= argmax w hT
(18)
KEZ
with
2T
wk R2
ho
Wk 2m.
(19)
m
A.3 Proof of Proposition 3
Proposition 3. A random network with frozen real-diagonal transition matrix (without additive terms) and learnable linear readout layer learns parity with probability 2- for arbitrary sequence length from only? 2 training examples of odd and even pariry.
Proof. For the parity task, the model observes an input sequence a! 02 ...., JT, with each of {0, 1). The objective is to output the parity of this sequence, which is ET= 0²) mod? 2.
Let A and A be the diagonal state- tiiestrranition matrices corresponding inputs 0 and 1, with em and emba(1) denoting the diagonal elements:
1 diag(a ()), A diag(a!"))
(20)
The hidden state evolves according to h² = =A e e-1 For the i-th component of the hidden state, this evolution is:
hT = a |o T1 h
(21)
15

---

where ( denotes the i-th diagonal element of A(o) (i.e., the i-th element of al))).
Crucially, the sign of the product II aj can encode parity. If, for a given component we have [0] > 0 and ! < O, then sgn II 1= (o')) will be positive for an even number of is (even parity) and negative for odd number of is (odd parity). This is because the number of negative terms (a, ) in the product matches the count of Is in the input sequence. Conversely, if a [1] O, the sign of the product becomes (-1)7 (-1)T-countod of of 1s which also encodes parity, albeit and ag
in manner dependent the sequence length T. Since sgn [1==1a,-] ) sgn(hh"h if hy is
initialized with a fixed sign (e.g., positive), then in either case where 0 and a; have opposite signs (i.e.. a; 00] [1] < O), the sign of hf contains sufficient information to determine the parity of the input sequence. The model then only needs to update its read-out layer (e.g., with one example of even and one of odd parity) to decode parity from hf:; all other recurrent parameters could remain fixed.
Assuming that the elements of (9) and (2) are i..d. and symmetrically distributed around 0 at initialization, we analyze the probability of finding such suitable component i. The probability that an arbitrary component has at and a!" with opposite signs is 0.5. Therefore, given the independence across the H components, the probability that there exists at least one component for [0) which a; a. 0 (1 0.5) =1-2
Remark: For the model to learn parity for arbitrary sequence lengths using a simple sign-based readout from single component i, the ideal condition is a!" < 0 and a, > 0. Under the same i..dd symmetric initialization assumptions, this specific configuration for a component i occurs with probability 1/4. Therefore, the probability that least one such ideally suited component i exists is
(1-11/14 = 1- - (3/4)".
16

---

B Implementation details
B.1
Tasks
For all tasks, to generate training sample, we first randomly select the number of inputs ~ N),, where N is the maximum training sequence length. We then select n input symbols from {0, l..... m m-11 } uniformly at random with replacement. For the modular arithmetic task specifically, we also sample interleaved with the input symbols.
operators uniformly with replacement from the set f+.-, } which are then
Each sample structured with special tokens: it begins with [BOS] (beginning of sequence) token and the input portion concludes with an [EOI] (end of input) token, immediately followed by the TARGET, shown:
[BOS] INPUT, INPUT2 INPUT;
INPUT, [EOI] TARGET
Each input symbols (including multi-digit integers and potentially operators), and special tokens [BOS] and [BOI] are tokenized as single tokens. During training and inference, all model outputs are disregarded except for the output corresponding to the [EOI] token; this output is taken as the model's is prediction for TARGET. Consequently, during training, the loss is calculated only on this final target prediction.
We evaluate the models on the following three tasks:
Modular addition: The target is the sum of input integers modulo For example, with 5 and m 20:
[BOS] 0 12 18 5 [EOI]
Modular arithmetic: This task involves processing a sequence alternating between integers from {0, I,.., m7 1} and n arithmetic operators from {+, x, -). The target is the result of these operations applied sequentially from left to right, with all calculations performed modulo m. For example, with and m 20:
[BOS] 3 *
9
17 + 6 + 12 [EOI]
The target calculated as:
x3x 9) mod 20- 7
(7-17 17) mod 20 = 10
(10+ 6) mod 20 16
(16 + 12) mod 20 8
Simulating state machines: The objective is simulate a randomly generated finite state machine (FSM). Both the input alphabet Σ and the set of states Q are identical to {0, 1...,..., m 1}. For each state q Q, the transition function 8(g. or) defined as Ty (o),, where ng is random permutation of E. This transition function 5 is generated once per FSM definition and remains fixed for all samples related to that FSM. The first input symbol in the sequence, INPUT, determines the initial state the FSM. Subsequent symbols INPUT,, ... INPUT, are processed as inputs to the FSM, and the target is the FSM's s final state. For example, consider m and the following randomly generated transition function:
17

---

Input Symbol (a)
3
5
0
3
0
4
5
2
Current State (g
1
3
5
4
2
0
1
3
4
3
5
0
2
4
3
0
4
5
5
5
4
0
3
2
An example sequence for this FSM would be:
[BOS] 4 2 5 [EOI] 2
The initial state is the first input (4 in this example), and upon observing each input, the state transitions occur based on the transition table:
State: 4, Input: 5(4,1)=0
New State: 0
State: 0, Input: 2 A(0.2) New State: 4
State: Input: A(4.5) New State: 5
State: 5, Input: 5 6(5.5)=2 New State: 2
(Target)
B.2 Experiment Setup
For the experiments discussed in Section 3.1 and reported in Table 1, all models trained using the ADAM optimizer with three learning rates (10 10.100+2000 1,10 10- and the configuration yielding the best performance without learning rate scheduling, weight decay, or dropout. In addition, the parameters of bilinear models (and variants) were initialized from uniform distribution W4-0000 0.01). Training was conducted for 100,000 steps with a batch size of 64. An early stopping criterion was applied if the validation loss fell below 10-5 For these experiments, training examples were randomly sampled each training step with input sequence lengths ranging from 2 to 10, while models were evaluated on inputs of length 500.
selected for reporting. All models were trained from random initializations,
For the data efficiency experiments detailed Section 3.2 (results in Figure 2), we used the optimal learning rate identified for each model and task from the previous experiment. We constructed fixed training sets of specified sizes and trained models for 1000 epochs over each set. Other settings were kept consistent with those in the previous experiment.
Regarding the baseline models in Table the Transformer baseline based on the GPT-2 architecture (Radford et al., 2019) with configurations of 1, 2, and layers, and model (embedding/hiddenn) dimension of 256, consistent with other models. Other parameters, such as an MLP inner expansion factor of 4, followed default GPT-2 (small) settings. We also used Mamba-1 (Gu and Dao, 2024) with 1, 2, and 4 layers, setting its model and hidden dimensions to 256. For other configurations, we adopted default values of Mamba- Mamba-130M. including an intermediate expansion size of 512, state space dimension of 16, and a convolution kernel size of 4.
All experiments were conducted on cluster of A100 GPU nodes. A single training and evaluation run for given model configuration, task, and setting typically completed on single GPU within an hour in most cases, or up to few hours in the worst case.
18

---

C Additional experiments
C.1 Parameter-matched models
The large parameter counts for some of our models (c.g., the full bilinear variant) are direct result of matching hidden dimension (256) rather than parameters in experiments presented in Section To address the concern about parameter efficiency, we conducted another set of experiments, similar to those in Table I, in which models were matched in parameter count by adjusting their hidden dimension. In Table 2 we report the validation and OOD test accuracy on sequences of length 500, with training performed on sequences up to length 10. These new results still show superior state- tracking performance of bilinear models in most tasks (a slight degradation for modular arithmetic).
Table 2: Validation and OOD test accuracy for models matched by parameter count via adjusted hidden dimensions. Bilinear models maintain superior ftae-tracking performance across most tasks.
Model
Spec.
Hidden Dim.
Layers
Parameters
Bilineur
513,207
Factored Bilinear
Rank 700
256
541,447
Block Ding. Billnear
4 Block of Size 32
128
526,215
Block Ding. Bilinear
32 Blocks of Size
256
528,135
L.TTM
256
529,927
532,487
Mamba
549,376
Transformer
4 Heads
96
546,528
Validation Accuracy (Length 2-10)
OOD Accuracy (Length 500)
Modulus
25
Modular
Addition
Bilinear
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
(200 factes))
1.00
1.00
1.00
1.00
Block Diag, (Blook Size t)
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Black Diag. (Block Size 12)
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
LSTM
1.00
1.00
1.00
1.00
1.00
0.99
1.00
1.00
0.98
1.00
0.00
0.02
RNN
1.00
1.00
1.00
1.00
Mamha
1.00
1.00
1.00
1.00
1.00
0.98
0.01
0.00
0.01
0.01
0.00
0.00
Transformer
1.00
1.00
1.00
0.97
0.63
0.01
0.03
0.04
0.00
0.00
0.00
0.00
Machine
Bilinear
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Factored Bil.
1.00
1.00
1.00
1.00
1.00
0.98
1.00
1.00
1.00
1.00
1.00
0.18
Diag, (Block Stee R)
1.00
0.60
1.00
1.00
0.39
0.02
Black Diag. (Blick Size 32)
1.00
1.00
1.00
1.00
1.00
0.73
1.00
1.00
1.00
1.00
1.00
0.11
1.TTM
1.00
1.00
1.00
1.00
1.00
0.30
1.00
1.00
1.00
1.00
0.66
0.09
RNN
1.00
1.00
1.00
1.00
0.67
0.22
1.00
1.00
1.00
1.00
0.25
0.08
Manha
1.00
0.00
0.96
0.08
Transformer
1.00
1.00
0.99
0.74
0.38
0.17
0.00
0.02
0.02
0.01
0.01
0.00
Modular Arithmetic
Bilinear
1.00
1.00
1.00
1.00
1.00
0.70
1.00
1.00
1.00
1.00
0.35
0.19
Factored Bil. (700 facke)
1.00
1.00
1.00
1.00
1.00
0.28
1.00
1.00
1.00
1.00
0.33
0.29
Block (Block
1.00
1.00
1.00
1.00
0.66
0.60
1.00
1.00
0.12
0.20
0.03
0.07
Black Diag. Size 32)
1.00
0.13
LSTM
1.00
1.00
1.00
1.00
1.00
0.90
1.00
1.00
1.00
1.00
0.94
0.64
RNN
1.00
1.00
1.00
1.00
1.00
0.35
1.00
1.00
1.00
1.00
0.98
0.29
Mamba
1.00
1.00
0.97
0.99
0.38
0.23
0.95
0.78
0.36
0.37
0.18
0.07
Transformer
0.58
0.26
0.07
0.119
0.01
0.02
0.01
0.01
19

---

C.2
Simulating dihedral groups
Consider a finite state-machine with Q {0. (0.....m. 1} f-1.+11 and input alphabet fadvance, reverse). The state consists of a "value" and binary "direction". Upon receiving imput advance, the value will be incremented or decremented by (modulo m) depending on the current direction. The input reverse flips the direction while leaving the value unchanged. Formally, the transition function is defined as follows:
8((s, d), advance) = ((s + d) mod m, d)
6((s, d), reverse) (s. -d)
See Example 6 in Liu et al. (2023) for more details on dihedral groups. Table 3 reports the in- distribution and teggthhgeneraiizttoon performance of various models when simulating dihedral groups with different moduli. As before, all models were trained on sequences of length 10 and evaluated on sequences of length 500.
Table 3: In-distribution and mangt-genneaaizatton performance various models on simulating dihedral groups with different moduli.
Validation Accuracy (Length 2-10)
OOD Accuracy (Length 500)
Modulus
2
3
5
10
25
50
2
5
10
25
50
Bilinear
Factored Bil. 1256 faccos)
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.99
Block Diag. (blck sise
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Ra Block Ding.
0.78
0.32
0.35
0.42
0.40
0.41
0.02
0.03
0.00
0.07
0.01
0.01
RNN
1.STM
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.21
0.24
Mumba
1.00
1.00
1.00
1.00
1.00
1.00
0.15
0.01
0.00
0.00
0.00
0.00
Transformer
1.00
1.00
1.00
1.00
1.00
1.00
0.23
0.02
0.01
0.00
0.01
0.01
C.3
Effect of number of factors
Similar to the results presented in Section 3.1, Table presents the validation and cittof-ddistiibttio accuracy of factored bilinear models on the state machine simulation task, considering an increasing number of factors (R) across various state space sizes (m). As these results indicate, increasing the number of factors enables the simulation of larger state machines, as a factored model with a higher R more closely approximates full bilinear model.
Table 4:
In-distribution and gength-generalization (normalized) accuracy of factored bilinear models with different number of factors, the state machine simulation task.
Validation Accuracy (Length 2-10)
OOD Accuracy (Length 500)
50
Model
Factors
0.00
0.02
0.00
0.02
0.01
0.00
0.03
0.00
0.00
0.00
0.01
0.00
2
0.00
0.03
0.00
0.01
0.00
0.00
0.00
0.01
0.00
0.00
0.00
0.01
4
1.00
1.00
0.65
0.02
0.01
0.00
1.00
0.97
0.29
0.01
0.00
0.00
8
1.00
1.00
0.92
0.17
0.01
0.01
1.00
1.00
0.58
0.04
0.00
0.00
16
1.00
1.00
1.00
0.44
0.06
0.01
0.95
1.00
1.00
0.26
0.01
0.01
Factored
Bilineur
64
1.00
1.00
1.00
1.00
0.26
0.04
1.00
1.00
1.00
1.00
0.08
0.00
1.00
256
1.00
1.00
1.00
1.00
0.19
1.00
1.00
1.00
1.00
1.00
0.01
512
1.00
1.00
1.00
1.00
1.00
0.45
1.00
1.00
1.00
1.00
1.00
0.10
1024
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.78
2048
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Bilinear
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
20

---

C.4 Multiplicative vs. additive recurrence
In a model with bi-linear state transitions, the role the inputs represent transformations on the hidden state, effectively acting as computations performed by hidden units. This contrasts with the conventional role of hidden units in an RNN, which primarily involves information retention. Therefore, for fully bilinear models, multiplicative interactions without additive contributions are sufficient for learning state transitions. In fact, for rotational and (block- (oockkkaaaagnall models, the inclusion of additive terms can even be detrimental.
We trained models under four configurations: with and without input-dependent additive contributions, with and without bias, and without any additive terms. Table 5 reports the OOD (sequence length 500) accuracy for the diagonal, 2D block-diagonal, and full bilinear models on parity, modular addition, and state machine simulation tasks.
As observed, and in line with the proposed hierarchy, the diagonal model is only capable of learning the parity task (only when the additive terms are excluded), the 2D block-diagonal model can learn modular addition (again only without the additive terms). In contrast, the full bilinear model is able learn both modular addition and the non-commutative task, regardless of whether the additive terms included.
Interestingly, line with prior work by Terzić et al. (2025), we find that additive terms sometimes improve performance on tasks outside model's hierarchy (e.g., the 2D block-diagonal model on non-commutative tasks), although overall accuracy remains low such cases.
Table 5: Out-of-distribution (sequence length 500 for training sequence length of 10) accuracy of real diagonal, 2D Block-diagone and full bilinear models on parity, modular addition, and state machine simulation tasks with and without additive terms in the recurrence.
Dataset
Parity
Medular Addition
State Machine
Modolas/State Size
2
3
5
10
25
3
5
10
25
Model
Additive Terms
Const.
0.00
0.02
0.00
0.00
0.00
0.13
1.00
0.57
0.19
0.11
Input Dependent
0.00
0.01
0.00
0.00
0.00
0.03
1.00
0.75
0.24
0.11
Real Diag.
Inpul Dep. + Const.
0.00
0.00
0.01
0.00
0.00
0.00
1.00
0.74
0.24
0.11
None
1.00
0.01
0.00
0.00
0.00
0.01
0.00
0.00
Const.
0.00
0.00
0.66
0.77
0.73
0.00
1.00
0.84
0.28
0.13
Inpul Dependent
0.00
0.00
0.12
2D Block Diag.
Input Dep. Const.
0.00
0.30
0.00
0.00
0.00
0.00
1.00
0.96
0.31
0.11
None
1.00
1.00
1.00
1.00
0.98
1.00
0.34
0.16
0.08
0.05
Const.
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Input Dependent
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Billnear
Input Dep.
Const.
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
None
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
Our observation is consistent with work of Terzić et al. (2025), where it is shown that complex diagonal model can generalize longer sequences on commutative automaton, but only when the additive term is removed and a linear readout is used. However, they also show the same model fails to learn non-commutative automaton. In that case, the best performance achieved when additive terms are included and a non-lineas readout layer is used. Even then, generalization remains limited, although the additive terms offer a slight improvement.
21

---

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: The abstract correctly summarizes content of the paper, including contributions and scope.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long 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: Limitations (such data efficiency and model sizes) are discussed throughout where applicable.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

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

---

Question: 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?
Answer: [No]
Justification: While code release not currently planned, all models, training algorithms and data generation are described in great detail in the supplemental material for easy reproducibility. All experiments involve very simple existing models on auto-generated standard datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips) cc/
ott.uuiiiisiooooccorooooooooc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https:
httpsscccppbccccccceceeeccccccce aeliii/guidee guidee/ /eee:e/eeeeemieeeeeeeeeeeeeee iwt.uummissiooPoo... ssionPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All relevant details to make sense of the results are described in the paper, with additional details in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Results are very extensive. Performance that varies smoothly across model variants, training set size and sequence length, are therefore shown in lieu of error bars, such that any irregularities are visible in the data.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
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?
Question:
Answer: [Yes]
Justification: Details on compute resources are provided in the supplemental materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:: /tttr::i//nuurps... httppss.cccpbblb (etpblic//thissuddeeel.....
Answer: [Yes]
Justification: All guidelines in the NeurlPS Code of Ethics are followed. The research does not involve any human subjects; all datasets are automatically generated; the research is confined to basic research on the capabilities of neural networks; model, datasets, training algorithms and evaluation methods are disclosed for transparency and reproducibility. Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper discusses fundamental limitations and potential improvements of specific type of neural network. There are no specific harms or potential for misuse beyond those that neural networks pose overall.
25

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to 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 deseribe 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: The paper describes fundamental research specific type of neural net- work and illustrates the findings by training comparably small networks on automatically generated data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards 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
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use any existing assets, and relevant prior work is cited.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
26

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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 is an important, original, or non-standard component of the core 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: The research in this work does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components. wwl.///////oeceeeeeeee hct////onfeeeecccc/2////LLL Please refer to our LLM policy (https: http://eeeeeaecccoooeeerree/e/// for what should or should not be described.
28


Reviews:
[{"review_id": "3LQMmaSlXm", "reviewer": "Reviewer_LWAc", "summary": "This paper investigates the expressivity of bi-linear recurrent models theoretically and empirically by studying their performance on three formal language tasks: modular addition, random state machine, and modular arithmetic.\nThe paper investigates different factorizations and parameterizations of the state transition tensor.\nIn the experiments bi-linear recurrent neural networks perform best on the state tracking tasks (with LSTM being close).", "questions": "- What are the exact parameter counts of the models? Since it is mentioned in the discussion section that the parameter count is larger due to the cubic scaling with embedding dim, it would make this point more clear if the parameter counts are added to Table 1, too.\n- L 271: Why do you need to normalize during inference and not during training?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Very well written, clear and easy to understand\n- Table 1: Good performance of Bilinear models (even though LSTM is close) \n\nWeaknesses:\n- The paper mentions that the stability problems of bi-linear recurrent models were the main reason for them not being used, and seems to solve this issue by dropping any additive terms in the state update. However, further (details on) experiments on this issue are missing.\n- There are no „real world“ experiments, e.g. on language or vision. It could be at least explained if these models are applicable to a more large scale training setup?", "was_revised": true, "final_justification": "The authors clarified my questions and concerns regarding the parameter counts and the real world experiments during the rebuttal. \nWhile the authors agree that applications to language pretraining would be a crucial next step, the paper focuses on theoretical justification and synthetic experiments, which seems reasonable. \nTherefore, I will maintain my score.", "rebuttal": "> The paper mentions that the stability problems of bi-linear recurrent models were the main reason for them not being used, and seems to solve this issue by dropping any additive terms in the state update. However, further (details on) experiments on this issue are missing.\n\nYes, one benefit of removing additive terms from the recurrence is that the model becomes scale-invariant, which allows for normalization of the hidden states to ensure stability. The evidence for this stability is our strong length generalization result: models trained on sequences up to length 10 performed successfully on sequences of length 500, which is made possible by performing iterative normalization during inference. We thank the reviewer for raising this point; we will clarify the link between scale-invariance, normalization, and our OOD results in the updated version of the paper.\n\n---\n\n> There are no „real world“ experiments, e.g. on language or vision. It could be at least explained if these models are applicable to a more large scale training setup?\n\nThe primary focus of our work is to analyze the state-tracking capabilities of bilinear recurrent networks and identify the architectural principles that govern them. For this reason, we concentrated on synthetic tasks that allow for controlled and precise evaluation. That said, we agree that scaling these models for natural language pretraining is a crucial next step. This would be possible in principle, because unlike non-linear RNNs (but like linear RNNs/SSMs) all relevant computations could be parallelized for bilinear RNNs. We believe that robust state-tracking is a significant advantage for complex reasoning, but scaling up introduces challenges, including improving recall and managing gradient flow during parallelizable training on long context. These challenges can be effectively addressed by integrating gating mechanisms, specialized convolutions or memory layers. We'll add a discussion on these future directions to the revised manuscript.\n\n---\n\n> What are the exact parameter counts of the models? Since it is mentioned in the discussion section that the parameter count is larger due to the cubic scaling with embedding dim, it would make this point more clear if the parameter counts are added to Table 1, too.\n\nThank you for this helpful suggestion. While this information is already provided for a subset of models in Figure 2, we will add the parameter counts additionally for all models to Table 1 for added clarity:\n\n- Full Bilinear: ~16.7M\n- Block Diagonal, block size 1: ~69K, block size 2: ~135K, block size 8: ~528K, block size 64: ~ 4.2M\n- Factored Bilinear rank 1: ~4K, rank 2: ~5K, rank 4: ~7K, rank 8: ~10K, rank 16: ~16K, rank 64: ~53K, rank 128: ~102K, rank 256: ~200K, rank 512: ~397K, rank 1024: ~790K, rank 2048: ~1.5M\n- 2D Rotation: ~38K\n- LSTM: 531K\n- RNN: 135K\n- Transformer 1-layer: ~1M, 2-layer: ~1.8M, 4-layer: ~3.4M\n- Mamba 1-layer: 473K, 2-layer: 943K, 4-layer: 1.8M\n\nHowever, we also want to clarify a key point regarding these numbers: the large parameter counts for some of our models (e.g., the full bilinear variant) are a direct result of matching hidden dimension (256) rather than parameters in these experiments. To address the valid concern about parameter efficiency, we conducted a new set of experiments where models are matched in parameter count by adjusting their hidden dimension:\n\n| Model             |   Hidden Dim. |   Layers |   Parameters |\n|:------------------|-------------:|-------------:|-------------:|\n| Bilinear          |           80 |            1 |       513,207 |\n| Block Diag.  (Block Size = 32)   |          128 |            1 |       526,215 |\n| Factored Bil. (Rank = 700) |          256 |            1 |       541447 |\n| LSTM              |          256 |            1 |       529,927 |\n| RNN               |          512 |            1 |       532,487 |\n| Mamba             |          128 |            4 |       549,376 |\n| Transformer       |           96 |            4 |       546,528 |\n\nWe report the OOD test accuracy on sequences of length 500, with training performed on sequences up to length 10. These new results still show superior state-tracking performance of bilinear models in most tasks (a slight degradation for modular arithmetic). We will add them to the updated version of the paper.\n\n\n| Model        |Mod. Add.|    2 |    3 |    5 |   10 |   25 |   50 |State Machine|  2   |  3   |  5   |  10  |  25  | 50   |Mod. Arith.|  2   |  3   |  5   | 10   | 25   | 50   |\n|:-------------|---------|:----:|------| -----|------|------|------|-------------|------|------|------|------| -----| ---- |-----------|------|------|------|------|------|------|\n| Bilinear     |         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.35 | 0.19 |\n| Block Diag.  |         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.11 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.09 | 0.13 |\n| Factored Bil.|         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.18 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.33 | 0.29 |\n| RNN          |         | 1.00 | 1.00 | 1.00 | 1.00 | 0.36 | 0.11 |             | 1.00 | 1.00 | 1.00 | 1.00 | 0.25 | 0.08 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.98 | 0.29 |\n| LSTM         |         | 1.00 | 1.00 | 0.98 | 1.00 | 0.00 | 0.02 |             | 1.00 | 1.00 | 1.00 | 1.00 | 0.66 | 0.09 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.94 | 0.64 |\n| Mamba        |         | 0.01 | 0.00 | 0.01 | 0.01 | 0.00 | 0.00 |             | 0.00 | 1.00 | 0.96 | 0.48 | 0.24 | 0.08 |           | 0.95 | 0.78 | 0.36 | 0.37 | 0.18 | 0.07 |\n| Transformer  |         | 0.03 | 0.04 | 0.00 | 0.00 | 0.00 | 0.00 |             | 0.00 | 0.02 | 0.02 | 0.01 | 0.01 | 0.00 |           | 0.19 | 0.04 | 0.01 | 0.02 | 0.01 | 0.01 |\n\n---\n\n> L 271: Why do you need to normalize during inference and not during training?\n\nWe did not apply normalization during training simply because the input sequences were short enough. It is entirely possible to apply hidden state normalization during both training and inference, and we will clarify in the revised text that its omission during our training runs was for simplicity, not a requirement of the model."}, {"review_id": "n0GpW05jZN", "reviewer": "Reviewer_RHHC", "summary": "This paper focuses on bi-linear RNNs where the transition matrix is a bi-linear function (a multiplicative interaction) of current input and hidden activations of the previous time-step. The paper showed that bi-linear RNNs are highly effective at learning state tracking tasks by mainly removing any additive components, s.t. the hidden state is a true bi-linear (not affine function) of the previous time-step hidden state and input. This leads to a scale-invariance which allows for keeping hidden activations stable during training and inference.", "questions": "Q1) The empirical evaluations in Table 1 are limited to only three synthetic tasks. How about the non-commutative automata with solvable transformation semigroups, such as the dihedral group? A pointer for these tasks: B. Liu, et al. \"Transformers Learn Shortcuts to Automata\", ICLR 2023.\n\nQ2) In Table 1, what is the reason for the drop in the OOD accuracy of RNNs as the Module increases? RNNs have sufficient expressiveness to learn any regular language.\n\nQ3) The best-performing model is reported (out of three using different learning rates). It is also good to report the min-max, or average-max, performance across models.\n\nQ4) Table 2 (right) shows the detrimental effect of additive terms on the parity automata, which is consistent with the prior art. How about benchmarking when learning a non-commutative automaton (e.g., D_30)? Could the model provide better length generalization once the B matrix is introduced? See Table 4 of the prior art.\n  \nQ5) Is there any sample efficiency comparison with RNNs in Figure 2?\n\nQ6) What are the potential limitations and implications of applying this method towards making LLMs on real-world datasets?", "limitations": "What are the potential limitations and implications of applying this method towards making LLMs on real-world datasets?", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- Bi-linear RNNs showed OOD generalization on synthetic state-tracking tasks \n- The models show similar sample efficiency to LSTM\n\nWeaknesses:\n\nSeveral theoretical, conceptual, and experimental similarities with prior art (A. Terzic, et al., \"On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages\", AAAI 2025) have not been mentioned in the paper. These should be clarified and elaborated:\n\n> We show that linear RNNs with diagonal transition matrices are a special case limited to learning state tracking tasks with commutative structure. This restriction is true even for complex-valued diagonal transition matrices. Hence, linear RNNs with block-diagonal transition matrices of size 2 × 2 are not able to learn general state machines (negative result).\n\nTheoretically, it has also been shown in the prior art that under a described mapping of FSA to a single-layer selective (i.e., input-dependent) state-space model (SSM) whose transition matrices are simultaneously diagonalizable, the selective SSM can only emulate commutative automata.\n\nMoreover, the prior art had already noted that models that do not utilize the B matrix (i.e., additive interactions) tend to learn solutions that exhibit better length generalization than their counterparts (which include the B matrix).\n\nConceptually, the proposed state transition matrix A is fully parametrized through a linear transformation of the input x. In the prior art, the A matrix is a convex combination of a set of transition matrices based on the current input.\n\nExperimentally, a single recurrent cell is followed by a linear classification head over the hidden states. This is also similar to what has been used in the prior art, with further ablation that shows the inefficiency of non-linear readouts.", "was_revised": true, "final_justification": "After carefully considering the authors' responses as well as the discussion among the other reviewers, I have decided to maintain my score of 3. My reasoning is as follows:\n\n1) The work shares substantial theoretical, conceptual, and empirical similarities with prior art (SD-SSM). Both approaches investigate the state-tracking abilities of linear RNNs, advocate for unstructured dense transition matrices, and highlight the limitations of complex diagonal matrices in modeling non-commutative operations. In effect, SD-SSM is a parameter-efficient case of the bilinear model proposed in this work, so it remains unclear whether the proposed bilinear model could have any practical edge over SD-SSM in the studied state-tracking.  \n\n1.1) It seems that the bilinear model (that does not inherently include additive terms) is an unstable system without input accumulation, whereas SD-SSM was stable (if p<1) with input accumulation.\n\n2) As also noted by other reviewers, it is not yet evident how the improvements in state-tracking translate to downstream performance on real-world datasets. This is in contrast with other structured alternatives like block-diagonal linear RNNs, which showed competitive OOD generalization on the state-tracking as well as achieving superior results in real-world classification tasks e.g., on multivariate time-series: https://arxiv.org/pdf/2505.17761", "rebuttal": "> Several theoretical, conceptual, and experimental similarities with prior art...\n\nThank you for pointing us to the work by Terzic et al. (2025). It is a well-written paper with interesting connections to our work. We will add a detailed discussion in the related work section and highlight similarities and differences in other relevant subsections. \nWe acknowledge the similarities: both papers analyze the state-tracking capabilities of linear RNNs, advocate for dense transitions to improve state-tracking, and show that complex diagonal transition matrices can only learn commutative operations. However, our work also differs in several key aspects.\nThe model in Terzic et al. constructs its transition matrix as a convex combination of a fixed set of learnable dense matrices. This can be viewed as a specific, parameter-efficient approximation of a more general bilinear model, where the transition matrix is fully parameterized by the input. Our approach to stability also differs: while they use additive terms in the recurrence and normalize the columns of the transition matrix, our bilinear recurrence formulation does not inherently include additive terms. This enables scale-invariance and allows for direct normalization of the hidden states at arbitrary points in time.\nFurthermore, our work contributes a more detailed hierarchy of state-tracking by showing, both theoretically and experimentally, that a real-diagonal model can only learn parity, but with extreme data efficiency. Finally, we introduce and study two parameter-efficient variants: the factorized and block-diagonal bilinear models.\n\n---\n\n> Q1) The empirical evaluations in Table 1 are limited to only three synthetic tasks. How about the non-commutative automata with solvable transformation semigroups, such as the dihedral group? A pointer for these tasks: B. Liu, et al.\n\nWe thank the reviewer for this suggestion and the pointer. Following the suggestion, we benchmarked all models on the dihedral group simulation task in the same setup as discussed in the paper (training length 10, testing length 500, best of 3 learning rates). As the results below demonstrate, bilinear RNN models successfully learn a length-generalizable solution to this task:\n\n| Model  |Valid.|2|3|5|10|25|50|Test|2|3|5|10|25|50|\n|:--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|\n|Bilinear  ||1.00|1.00|1.00|1.00|1.00|1.00||1.00|1.00|1.00|1.00|1.00|1.00|\n|Block Diag.  ||1.00|1.00|1.00|1.00|1.00|1.00||1.00|1.00|1.00|1.00|1.00|1.00|\n|Factored Bil.||1.00|1.00|1.00|1.00|1.00|1.00||1.00|1.00|1.00|1.00|1.00|0.99|\n|2D Rotation  ||0.78|0.32|0.35|0.42|0.40|0.41||0.02|0.03|0.00|0.07|0.01|0.01|\n|LSTM||1.00|1.00|1.00|1.00|1.00|1.00||1.00|1.00|1.00|1.00|0.21|0.24|\n|RNN ||1.00|1.00|1.00|1.00|1.00|1.00||1.00|1.00|1.00|1.00|1.00|0.07|\n|Mamba  ||1.00|1.00|1.00|1.00|1.00|1.00||0.15|0.01|0.00|0.00|0.00|0.00|\n|Transformer  ||1.00|1.00|1.00|1.00|1.00|1.00||0.23|0.02|0.01|0.00|0.01|0.01|\n\n---\n\n> Q2) In Table 1, what is the reason for the drop in the OOD accuracy of RNNs as the Module increases? RNNs have sufficient expressiveness to learn any regular language.\n\nWe hypothesize that the observed drop in accuracy could be due to the learning problem becoming harder as the modulus (m) grows. A larger modulus means a larger state space and a more complex transition function for the model to learn. This could make the optimization more difficult and amplify the well-known challenges of propagating gradients through time in standard RNNs. Therefore, while the required solution is representable within the RNN's capacity, the model may struggle to converge to it as the task complexity increases.\n\n---\n\n> Q3) The best-performing model is reported (out of three using different learning rates). It is also good to report the min-max, or average-max, performance across models.\n\nWe thank the reviewer for this suggestion. We will add a table to the appendix showing the minimum and maximum accuracy for each model across the learning rates, complementing the best-performing results presented in the main text.\n\n---\n\n> Q4) Table 2 (right) shows the detrimental effect of additive terms on the parity automata, which is consistent with the prior art. How about benchmarking when learning a non-commutative automaton (e.g., D_30)? Could the model provide better length generalization once the B matrix is introduced? See Table 4 of the prior art.\n\nThe mentioned work shows that the complex diagonal model can generalize to longer sequences on a commutative automaton, but only when the additive term is removed and a linear readout is used. However, the same model fails to learn a non-commutative automaton. In that case, the best performance is achieved when additive terms are included and a non-linear readout layer is used. Even then, generalization remains limited, though the additive terms offer a slight improvement.\n\nWe performed an ablation study on the non-commutative state machine simulation task. We report results for the diagonal, 2D block-diagonal, and full bilinear models on parity, modular addition, and state machine simulation task (as a reminder, please note that accuracy numbers are scaled so that 0.0 represents random chance performance):\n\n**Validation Accuracy (Length 2-10)**\n\nModel|AdditiveTerms|Parity | Mod. Add. |5|10|25| State Machine |5|10|25|\n---|:--:|:--:|:--:|:---:|:---:|:---:|:--:|:---:|:---:|:--:|\nRealDiagonal|Yes|1.00||0.54|0.03|0.01||0.83|0.36|0.11|\nRealDiagonal|No|1.00||0.88|0.85|0.40||0.22|0.15|0.09|\n2D-BlockDiagonal|Yes|1.00||1.00|1.00|0.01||1.00|0.52|0.12|\n2D-BlockDiagonal|No|1.00||1.00|1.00|1.00||0.83|0.49|0.23|\nBilinear|Yes|1.00||1.00|1.00|1.00||1.00|1.00|1.00|\nBilinear|No|1.00||1.00|1.00|1.00||1.00|1.00|1.00|\n\n**Test Accuracy (Length 500)**\n\nModel|AdditiveTerms|Parity|Mod. Add. |5|10|25| State Machine |5|10|25|\n--|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|\nRealDiagonal|Yes|0.00||0.01|0.00|0.00||0.74|0.24|0.11|\nRealDiagonal|No|1.00||0.00|0.00|0.00||0.00|0.00|0.00|\n2D-BlockDiagonal|Yes|0.00||0.00|0.00|0.00||0.96|0.31|0.11|\n2D-BlockDiagonal|No|1.00||1.00|1.00|0.98||0.16|0.08|0.05|\nBilinear|Yes|1.00||1.00|1.00|1.00||1.00|1.00|1.00|\nBilinear|No|1.00||1.00|1.00|1.00||1.00|1.00|1.00|\n\nAs observed, and in line with the proposed hierarchy, the diagonal model is only capable of learning the parity task (only when the additive terms are excluded), the 2D block-diagonal model can learn modular addition (again only without the additive terms). In contrast, the full bilinear model is able to learn both modular addition and the non-commutative task, regardless of whether the additive terms are included. Consistent with prior work, we find that additive terms improve the models' performance on the non-commutative task, although the overall performance remains low in both cases. We will include this discussion in the revised version of the paper, along with citations to the relevant work.\n\n---\n\n> Q5) Is there any sample efficiency comparison with RNNs in Figure 2?\n\nBased on your question, we also performed the data-efficiency experiments for the RNN using the same setup described in Section 3.2, and we report the results below:\n\n**Modular Addition**\n\nModulo|10|50|100|500|1000|5000|10000|50000|\n--|---:|---:|---:|---:|--:|--:|--:|--:|\n2|0.03|0.01|0.00|1.00|1.00|1.00|1.00|1.00|\n5|0.00|0.01|0.01|0.00|0.00|1.00|1.00|1.00|\n10|0.01|0.01|0.00|0.00|0.00|0.00|0.19|0.95|\n25|0.00|0.00|0.00|0.00|0.00|0.01|0.00|0.00|\n\n**State Machine**\n\nStates|10|50|100|500|1000|5000|10000|50000|\n--|--:|---:|---:|--:|--:|--:|--:|--:|\n2|0.02|0.02|0.04|1.00|1.00|1.00|1.00|1.00|\n5|0.11|0.31|0.39|0.98|1.00|1.00|1.00|1.00|\n10|0.01|0.04|0.08|0.11|0.16|0.27|1.00|0.96|\n25|0.01|0.03|0.04|0.05|0.04|0.05|0.06|0.09|\n\n**Modular Arithmetic**\n\nModulo|10|50.|100|500|1000|5000|10000|50000|\n--|--:|--:|---:|--:|--:|--:|--:|--:|\n2|0.14|0.32|0.61|1.00|1.00|1.00|1.00|1.00|\n5|0.08|0.03|0.06|0.11|0.20|1.00|1.00|1.00|\n10|0.05|0.08|0.07|0.13|0.19|0.30|1.00|1.00|\n25|0.01|0.01|0.01|0.01|0.02|0.05|0.06|0.28|\n\nCompared to the LSTM, we found that the simple RNN shows slightly lower data efficiency on the modular addition and state-machine tasks, but slightly better efficiency on the modular arithmetic task when using larger moduli. We will include this in Figure 2.\n \n---\n\n> Q6) What are the potential limitations and implications of applying this method towards making LLMs on real-world datasets?\n\nThe benefits of improved state-tracking are particularly evident in math and code benchmarks. There is supporting evidence in the literature, for example, Grazzi et al. (2025) (figure 10), which shows that enabling even the weakest form of state-tracking in models like Mamba and DeltaNet leads to improved perplexity in math and code. Therefore, we believe that models with stronger state-tracking capabilities will have a significant advantage in reasoning more generally.\n\nCurrently, almost all large-scale pretrained language models have limited internal state-tracking capabilities. Although they rely on chain of thought to make the state observable in the token space, this becomes impractical when the state is large or continuous. \n\nAlthough bilinear models demonstrate strong state-tracking, we identify two potential limitations for scaling them to large-scale pretraining on natural language. First is their recall performance, which is crucial in the natural language domain. A second potential challenge is managing gradient flow over very long sequences while maintaining parallelizable training. Similar to recent developments in SSMs, limitations like these could be overcome by utilizing additional gating mechanisms, skip connections, 1D convolutions, or even hybrid layers that incorporate memory modules. While this is out of scope for this work, we do consider it important future work. \n\n_Grazzi, Riccardo, et al. \"Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues.\" The Thirteenth International Conference on Learning Representations._"}, {"review_id": "zoOtYWUxb8", "reviewer": "Reviewer_Cy8L", "summary": "In this paper, the authors study the properties of bilinear RNNs, where state transitions are governed by a tensor that is contracted against both the current state and the current input. They prove limitations on the state-tracking capabilities of several variants of standard SSMs and linear RNNs on state tracking tasks, and further prove that bilinear RNNs can simulate any finite state machine. Finally, they conduct a series of experiments on parity, modular arithmetic, and simulating random state machines to demonstrate that bilinear RNNs with more practical parameterizations (in terms of parameter efficiency) perform well on state tracking tasks when compared to other architectures.", "questions": "- Can the authors comment further on why including biases degrades performance of bilinear RNNs? Why can't the model learn to simply ignore the biases, and why does this lead to instabilities?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written, and to the best of my knowledge, clarifies important limits on the expressivity of various parameterizations of linear RNNs on state-tracking tasks. The analysis appears mathematically tight, and covers a wide range of interesting subproblems in state tracking (commutative vs noncommutative tasks, parity, automata). \n\nWeaknesses:\n\nWhile the authors do address the parameter-inefficient nature of bilinear RNNs by considering low-rank or factorized parameterizations, their experiments do not compare different model classes in a parameter-matched way; instead, hidden dimension is held fixed, giving a potentially massive parameter count advantage to the bilinear RNNs. A more complete set of experiments comparing bilinear RNNs and their factorized variants to other architectures with conserved parameter count would be needed to understand whether bilinear RNNs are actually practically useful on state-tracking tasks, and would be a useful addition to round out the paper regardless of what the results end up showing. I am open to bumping up my score to \"Accept\" if this can be done.", "was_revised": true, "final_justification": "The additional experiments clarified concerns I had over fairly comparing different model classes in a parameter-matched way.", "rebuttal": "> While the authors do address the parameter-inefficient nature of bilinear RNNs by considering low-rank or factorized parameterizations, their experiments do not compare different model classes in a parameter-matched way; instead, hidden dimension is held fixed, giving a potentially massive parameter count advantage to the bilinear RNNs. A more complete set of experiments comparing bilinear RNNs and their factorized variants to other architectures with conserved parameter count would be needed to understand whether bilinear RNNs are actually practically useful on state-tracking tasks, and would be a useful addition to round out the paper regardless of what the results end up showing. I am open to bumping up my score to \"Accept\" if this can be done.\n\nWe thank the reviewer for their constructive suggestion. First, we would like to emphasize that we chose to use a consistent hidden dimension size of 256 for all models in Table 1 which resulted in very large parameter counts for some of the models.\nAs suggested, we performed a new experiment to compare models in a parameter-matched setting instead, by adjusting the hidden state size of the models to approximately match parameter counts:\n\n| Model             |   Hidden Dim. |   Layers |   Parameters |\n|:------------------|-------------:|-------------:|-------------:|\n| Bilinear          |           80 |            1 |       513,207 |\n| Block Diag.  (Block Size = 32)   |          128 |            1 |       526,215 |\n| Factored Bil. (Rank = 700) |          256 |            1 |       541447 |\n| LSTM              |          256 |            1 |       529,927 |\n| RNN               |          512 |            1 |       532,487 |\n| Mamba             |          128 |            4 |       549,376 |\n| Transformer       |           96 |            4 |       546,528 |\n\nWe report the OOD test accuracy on sequences of length 500, with training performed on sequences up to length 10. The results show the superior performance of bilinear models in most state-tracking tasks (but a mild degradation for modular arithmetic), even with matched parameter counts:\n\n| Model        |Mod. Add.|    2 |    3 |    5 |   10 |   25 |   50 |State Machine|  2   |  3   |  5   |  10  |  25  | 50   |Mod. Arith.|  2   |  3   |  5   | 10   | 25   | 50   |\n|:-------------|---------|:----:|------| -----|------|------|------|-------------|------|------|------|------| -----| ---- |-----------|------|------|------|------|------|------|\n| Bilinear     |         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.35 | 0.19 |\n| Block Diag.  |         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.11 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.09 | 0.13 |\n| Factored Bil.|         | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |             | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.18 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.33 | 0.29 |\n| RNN          |         | 1.00 | 1.00 | 1.00 | 1.00 | 0.36 | 0.11 |             | 1.00 | 1.00 | 1.00 | 1.00 | 0.25 | 0.08 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.98 | 0.29 |\n| LSTM         |         | 1.00 | 1.00 | 0.98 | 1.00 | 0.00 | 0.02 |             | 1.00 | 1.00 | 1.00 | 1.00 | 0.66 | 0.09 |           | 1.00 | 1.00 | 1.00 | 1.00 | 0.94 | 0.64 |\n| Mamba        |         | 0.01 | 0.00 | 0.01 | 0.01 | 0.00 | 0.00 |             | 0.00 | 1.00 | 0.96 | 0.48 | 0.24 | 0.08 |           | 0.95 | 0.78 | 0.36 | 0.37 | 0.18 | 0.07 |\n| Transformer  |         | 0.03 | 0.04 | 0.00 | 0.00 | 0.00 | 0.00 |             | 0.00 | 0.02 | 0.02 | 0.01 | 0.01 | 0.00 |           | 0.19 | 0.04 | 0.01 | 0.02 | 0.01 | 0.01 |\n\nThank you again for the suggestion. We will add these results to the revised version of the paper.\n\n---\n\n>  Can the authors comment further on why including biases degrades performance of bilinear RNNs? Why can't the model learn to simply ignore the biases, and why does this lead to instabilities?\n\nOur hypothesis is that the presence of additive terms may alter the loss landscape such that, while a zero-bias solution exists, it may not be stable or easily reachable via gradient descent. This is similar to how different initialization schemes can lead optimization toward different local minima, even when the networks can represent better solutions. We would also like to highlight an additional benefit of removing bias terms from the recurrence: the model becomes scale-invariant, which enables normalization of the hidden states to maintain stability over long sequences. This is demonstrated in our length generalization setup with sequences of length 500."}, {"review_id": "iPV9tn3rjD", "reviewer": "Reviewer_9AkV", "summary": "This paper analyzes bi-linear operations in RNNs (where hidden states and inputs interact multiplicatively) in the context of state tracking tasks. By parameterizing the hidden state matrices of SSMs in bilinear form, this theoretically show how to solve the state tracking task. The paper also introduces a hierarchy of task complexity, with simple linear RNNs (like Mamba) at the base.", "questions": "1. How do bi-linear RNNs compare to the other RNNs in Figure 1 on \"real\" sequential processing tasks? E.g., sequential MNIST? \n2. Is there any connection to associative memory models, which also have multiplicative connections (albeit between hidden units, and not between inputs). For example, see Figure 1 [here](https://arxiv.org/pdf/2008.06996). There is also a (very) recent [paper](https://www.science.org/doi/epdf/10.1126/sciadv.adu6991) which contains multiplicative interactions between hidden states and external inputs. It would be interesting to know if there is some theoretical connection between bi-linear RNNs and associative memory.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The paper is very well-written, and the motivation is clear. I learned a lot reading this work! \n\nOne weakness is the lack of experiments on \"real\" benchmark sequential processing tasks, like those found in the [Long Range Arena](https://arxiv.org/abs/2011.04006).", "was_revised": true, "final_justification": "The authors addressed all my (minor) comments. I maintain my recommendation to accept.", "rebuttal": "> 1. How do bi-linear RNNs compare to the other RNNs in Figure 1 on \"real\" sequential processing tasks? E.g., sequential MNIST/Long Range Arena?\n\nThe primary focus of our work is to analyze the state-tracking capabilities of bilinear recurrent networks and identify the architectural principles that govern them. For this reason, we concentrated on synthetic tasks that allow for controlled and precise evaluation. That said, we agree that scaling these models for natural language pretraining is a crucial next step. We believe that robust state-tracking is a significant advantage for complex reasoning, but scaling up introduces challenges, including improving recall and managing gradient flow during parallelizable training on long context. These challenges could potentially be addressed by integrating gating mechanisms, specialized convolutions or memory layers, as done also for SSMs in the past. We'll add a discussion on this to the revised manuscript.\n\n---\n\n> 2. Is there any connection to associative memory models, which also have multiplicative connections (albeit between hidden units, and not between inputs). For example, see Figure 1 here. There is also a (very) recent paper which contains multiplicative interactions between hidden states and external inputs. It would be interesting to know if there is some theoretical connection between bi-linear RNNs and associative memory.\n\nWe thank the reviewer for this insightful question and for the pointers to the related work (which we will include in the paper). There is indeed a fundamental theoretical connection between the bilinear formulation of recurrence and associative memory networks, particularly with modern dense associative memory models (modern Hopfield networks). The foundational link is the principle of multiplicative interactions modulated by an external signal. While classic associative memories focused on hidden-to-hidden connections, modern Hopfield networks (variants with continuous state, or the IDP Hopfield model as pointed out by the reviewer) have an update rule reminiscent of attention mechanisms, where an input query dynamically weights the stored memory patterns. This is conceptually similar to the bilinear recurrence formulation, where the input modulates the hidden-state transition dynamics of the system in a multiplicative manner. We acknowledge that deeper understanding and study of this connection could lead to interesting future directions and appreciate the point raised by the reviewer."}]

Author rebuttal:

Meta-review: Strengths
- Proposed models show sample efficiency on synthetic state-tracking

- Reviewers note the paper is very-well written and easy to understand.

- The proposed bilinear models have good performance (though LSTM is close), and demonstrating OOD performance.

- Theoretically sound and justified, e.g. "tight mathematical analysis, covering a wide range of interesting subproblems in state tracking" (Reviewer Cy8L)

Weaknesses
- Substantial technical overlap with SD-SSM ([A. Terzic, et al., "On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages", AAAI 2025] noted by Reviewer RHHC), and initial version of the paper did not include reference or discussion of this; after rebuttal, authors have committed to include reference and detailed discussion of this method relative to their work.

- Lack of parameter-matched evaluations (Reviewer Cy8L); rebuttal resolved this by providing evaluation on this.

- Lack of experimentation on "real" benchmark sequential processing tasks e.g. Long Range Arena (Reviewer 9AkV, Reviewer LWAc). Authors note they use synthetic tasks to more easily analyze and control state-tracking task, which makes sense. Authors satisfied this reviewer's other minor comments in rebuttal.

Decision

Majority of reviewers feel positively about this paper. Most critical reviewer is concerned about too much overlap with the prior work SD-SSM, but I think authors justify that there are differences with this method, and authors promise to cite and discuss relation to this work in the final revision.
Decision: Accept (poster)