Revisiting Bi-Linear State Transitions in Recurrent Neural Networks
M.Reza Ebrahimi, Roland Memisevic · 2025
Read Revisiting Bi-Linear State Transitions in Recurrent Neural Networks by M.Reza Ebrahimi, Roland Memisevic (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21749.txt.
Introduction
Ebrahimi and Roland Memisevic revisit a richer way for recurrent networks to update their state, in work from 2025. Hidden units are often cast as passive memory stores, with gates to guard what they hold. The pair casts them as active parts of the math. Their update multiplies hidden state with input codes, a step called bilinear.
Proofs and tests show that step fits state-tracking tasks in a natural way. Such tasks are the simplest ones where hidden units must truly compute. The steps form a ladder of rising task depth. Known lean models, Mamba among them, sit at the ladder's low rung.
Catalog record
| CREATOR | M.Reza Ebrahimi, Roland Memisevic |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21749
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Revisiting Bi-Linear State Transitions in Recurrent Neural Networks Thanks: Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc. M.Reza Ebrahimi, Roland Memisevic 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. 1 Introduction State tracking is a fundamental requirement for performing sequential decision-making tasks, in which future actions depend on the consequences of past actions. The consequences of past actions are usually not directly observable, making state tracking a 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 a 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 to treat it as the task of correctly representing the arbitrary-length sequence of states that a state machine takes on in response to observing a 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 to learn, many models are surprisingly bad at learning it from data. The reason for its simplicity is that the task admits a simple inductive decomposition: For each input in the sequence, it suffices to update an internal representation of the state inferred from all inputs seen previously. As a result, it is possible, in principle, to learn state tracking for sequences of arbitrary length by simply learning the appropriate state transitions for every (input, state)-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 et al., 2023 ; Anil et al., 2022 ; Abbe et al., 2024 ) on sequences longer than the training data. This includes very large, pre-trained Transformer-based language models, and it is the case even when trained to use chain-of-thought reasoning (“inference-time compute”) (e.g., Ebrahimi et 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 hidden-to-hidden transition matrix satisfies two conditions: (i) it is a function of the input (and thus not time-invariant), and (ii) not all of its eigenvalues are positive ( Sarrof et al., 2024 ; Grazzi et al., 2025 ) . However, the tasks that can be learned under these conditions are highly restricted as we shall show. A benefit of linear models, besides being amenable to analysis, is that they can be trained efficiently on 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 a 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 (e.g., Sutskever et al. (2011) ; Downey et al. (2017) ; Wu et al. (2016) ), but they have not caught on as widely used models. This is in part due to instabilities and optimization difficulties owed to their inherent three-way multiplicative interactions. Figure 1: Taxonomy of bilinear RNNs studied in this paper, along with example regular language tasks they can learn (in blue). We show that bilinear RNNs are highly effective at learning state tracking tasks if one leverages a 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 a true bilinear not an 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-inefficient models to highly constrained and parameter-efficient models. The different model classes within the hierarchy correspond to increasingly narrow subclasses of regular language modeling tasks that can be learned from data (see Fig. 1 ). Several existing linear RNNs, such as Mamba ( Gu and Dao, 2024 ) , are at the center of the hierarchy, with no state tracking capability at all. A 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 a binary bit string. We show that a notable special case of learning bilinear state transitions without additive terms is that it can learn the parity task with a frozen (untrained) recurrence and only training final readout layer on as few as two training examples. Figure 1 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-valued diagonal transition matrix). Further constraining the transition matrix to positive diagonal impedes a model’s ability to perform state tracking (see, e.g., Grazzi et al. (2025) ; Sarrof et 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 a very large number of parameters. • We show that it is always sufficient (and in some cases necessary) for the hidden state to be a pure linear not affine function of the hidden state at 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 a trained linear readout layer