Fixed-Point RNNs: Interpolating from Diagonal to Dense
Sajad Movahedi, Felix Sarnthein, Nicola Muça Cirone, Antonio Orvieto · 2025
Read Fixed-Point RNNs: Interpolating from Diagonal to Dense by Sajad Movahedi, Felix Sarnthein, Nicola Muça Cirone, Antonio Orvieto (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-2503-10799.txt.
Introduction
Sajad Movahedi, Felix Sarnthein, Nicola Muca Cirone, and Antonio Orvieto widen what linear recurrent networks can track, without giving up their speed. Their 2025 paper notes that models like Mamba mix sequences channel by channel, a diagonal pattern that limits true state-tracking power. Full dense recurrence tracks more, but resists parallel training.
Their trick recasts a broad class of dense linear recurrences as fixed points of diagonal ones, which stay parallel-friendly. The dial between the two extremes turns at fixed parameter count, trading expressivity for efficiency as needed. On the standard A5 and S5 state-tracking tests the models set new marks, while matching rivals on copying tasks. The work narrows the gap between fast sequence layers and the old recurrent ideal.
Catalog record
| CREATOR | Sajad Movahedi, Felix Sarnthein, Nicola Muça Cirone, Antonio Orvieto |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-10799
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fixed-Point RNNs: Interpolating from Diagonal to Dense Sajad Movahedi, Felix Sarnthein, Nicola Muça Cirone, Antonio Orvieto Abstract Linear recurrent neural networks (RNNs) and state-space models (SSMs) such as Mamba have become promising alternatives to softmax-attention as sequence mixing layers in Transformer architectures. Current models, however, do not exhibit the full state-tracking expressivity of RNNs because they rely on channel-wise (i.e. diagonal) sequence mixing. In this paper, we investigate parameterizations of a large class of dense linear RNNs as fixed-points of parallelizable diagonal linear RNNs. The resulting models can naturally trade expressivity for efficiency at a fixed number of parameters and achieve state-of-the-art results on the state-tracking benchmarks A 5 A_{5} and S 5 S_{5} , while matching performance on copying and other tasks. Figure 1 : Sequence length generalization at training length 16 (pink) for state-tracking on A_{5} , with Transformer (brown) and LSTM (purple) as lower/upper bounds. Our Fixed-Point RNN (FP-Mamba-H) is trained at different maximum number of fixed-point iterations \ell_{\text{max}} : between 2 (green) and 16 (blue). Increasing the number of fixed-point iterations allows the linear RNN to interpolate from diagonal to dense in a few iterations. 1 Introduction State-space models (SSMs) and other new efficient recurrent token mixers are becoming a popular alternative to softmax attention in language modeling ( Gu & Dao, 2024 ) as well as in other applications such as vision ( Liu et al., 2024 ) and DNA processing ( Nguyen et al., 2024 ) . Inspired by linear input-controlled filtering, these models can be expressed as carefully parametrized linear recurrent neural networks (RNNs) with input-dependent, diagonal state transition: \displaystyle\mathbf{h}_{t}=\text{diag}(\mathbf{a}_{t})\mathbf{h}_{t-1}+\mathbf{B}_{t}\mathbf{x}_{t} (1) Compared to classical RNNs such as LSTMs ( Hochreiter & Schmidhuber, 1997 ) , in Eq. ( 1 ) the relation between the previous hidden state \mathbf{h}_{t-1} and the current \mathbf{h}_{t} is linear and its coefficient \mathbf{a}_{t} does not depend on the hidden states. These choices allow SSMs such as Mamba ( Gu & Dao, 2024 ) to be computed through efficient parallel methods during training. Furthermore, they are easier to optimize than classical RNNs, thanks to stable and efficient reparametrizations available for diagonal transitions ( Orvieto et al., 2023 ; Zucchet & Orvieto, 2024 ) – techniques that are significantly more difficult to apply effectively in the classical setting ( Arjovsky et al., 2016 ; Helfrich et al., 2018 ) . At test time, they are faster than classical Transformers on long sequences due to their recurrent nature. Though modern linear RNNs have shown promise in practice, recent theoretical studies suggest that using dense, input-dependent transition matrices (i.e. replacing \text{diag}(\mathbf{a}_{t}) with a dense \mathbf{A}_{t} ) could present an opportunity to improve expressivity and unlock performance on challenging tasks. In particular, Cirone et al. (2024b) prove that dense selective SSMs are endowed with the theoretical expressivity of classical non-linear RNNs such as LSTMs. As shown by Merrill et al. (2024) and Sarrof et al. (2024) , such gained expressivity proves to be particularly useful in state-tracking applications where models are expected to maintain and extrapolate a complex state of the world. Since state-tracking is naturally expressed by non-linear RNNs but provably unavailable to channel-wise sequence mixers such as SSMs or Transformers, Merrill & Sabharwal (2023) speculate on a fundamental tradeoff between parallelism and expressivity . This discussion sparked interest in non-diagonal recurrences and parallelizable architectures capable of state-tracking ( Grazzi et al., 2024 ; Terzic et al., 2025 ; Schöne et al., 2025 ; Peng et al., 2025 ; Siems et al., 2025 ) . When designing new architectures involving dense selective yet linear state transitions of the form \mathbf{h}_{t}=\mathbf{A}_{t}\mathbf{h}_{t-1}+\mathbf{B}_{t}\mathbf{x}_{t} , two fundamental concerns arise: 1. What should the parametric form for \mathbf{A}_{t} , as a function of the input be? How can we guarantee this parametrization induces a stable recurrence, like in standard 1 1 1 Standard SSMs are diagonal and operate in polar coordinates, parameterizing directly the gap between eigenvalues and the stability threshold ( Orvieto et al., 2023 ) . This technique allows to increasing granularity near the identity, and to effectively normalize the forward pass (cf. \sqrt{1-|\gamma|^{2}} term in Griffin ( De et al., 2024 ) ). SSMs? 2. How does a parametrization balance between expressivity and parallelism? Which assumptions on the structure of \mathbf{A}_{t} enable efficient computation, and how do they interact with expressivity? Perhaps the first approach tackling the above questions was DeltaNet ( Schlag et al., 2021a ; Yang et al., 2024b ) with a block-diagonal and orthogonal therefore, stable state transition structure, where each block is parametrized by a Householder matrix. The parallelizable algorithm, was then extended to include negative eigenvalues ( Grazzi et al., 2024 ) , gates ( Yang et al., 2025 ) , and most recently products of Householders ( Siems et al., 2025 ) . Such choices, leading to increased expressivity as exemplified by their state-tracking and length generalization capabilities, are motivated mainly by hardware considerations: Householder-based mixing can be implemented efficiently on GPUs as linear attention via WY-representations and the UT transform ( Yang et al., 2024b ) . Figure 2 : (a) State-tracking on A_{5} at sequence length 16 , and (b) character accuracy of copying at 2\times sequence length generalization, trained on lengths \in[5,50] . Our single layer FP-Mamba-H with mixer reflections r\in\{1,2,4\} is compared to baselines of increasing depth \in\{1,2,4,6,8\} . FP-Mamba-H is the only model capable of solving both the state-tracking and the copy task. While the works above offer exciting practical strategies for boosting capabilities at a relatively low additional computational cost, they fall short in exploring the sea of intriguing options for dense transitions and hence, in thoroughly answering questions (1) and (2) above. Unfortunately, this is not an easy task: although linear recurrences are theoretically parallelizable across sequence length ( Martin & Cundy, 2018 ) , parallelizing dense RNNs efficiently is not trivial due to increased memory I/O. These thoughts inspired us to change our viewpoint: instead of designing an algorithm which adds a fraction of non-diagonal processing to a model, here, we look for a strategy to navigate the parallelism tradeoff towards a truly dense object. Motivated by the idea of designing a parallelizable general-purpose method to implement new dense RNN variations, in this paper we devise a new adaptive computation strategy which allows to interpolate between fast recurrent diagonal RNNs and dense recurrences with arbitrary preselected structure. Instead of parameterizing the dense RNN layer as an explicit function \mathbf{h}=F_{\boldsymbol{\theta}}(\mathbf{x}) , we build on the literature of equilibrium/implicit models ( Bai et al., 2019 ; Ghaoui et al., 2021 ) to parametrize it implicitly as a solution \mathbf{h}^{*} to a fixed-point equation \mathbf{h}=f_{\boldsymbol{\theta}}(\mathbf{x},\mathbf{h}) involving only a diagonal RNN. As described in Fig. 3(a) , we solve for \mathbf{h}^{*} using a fixed-point iteration of diagonal RNN evaluations f_{\boldsymbol{\theta}} . A fundamental question some readers might rightfully ask, is the following: “ what is the advantage of iterating a single layer in depth compared to depth-stacking multiple SSM, e.g. Mamba layers? ” We claim one advantage comes from having access to the limiting dense object. As showcased by Fig. 2 , this allows to adaptively provide the required expressivity for a fixed set of parameters without any a priori choice on the network