Fixed-Point RNNs: Interpolating from Diagonal to Dense
Authors: Sajad Movahedi
Felix Sarnthein
Nicola Muca Cirone
Antonio Orvieto
Venue: NeurIPS 2025 spotlight ()
Keywords: Deep Learning
Sequence Architecture
Recurrent Neural Network
State Space Model
Linear RNN
SSM
Mamba
Linear Attention
RWKV
DeltaNet
DeltaProduct
Looped Architecture
Recurrent Depth
Equilibrium Model
DEQ
Implicit Neural Network
Implicit Model
Neural ODE
Adaptive Computation Time
ACT
Test-Time Computation
Test-Time Compute
Reasoning
State-Tracking
A5
S5
Copying
CatbAbi
Primary area: deep_learning
TL;DR: We introduce the Fixed-Point RNN framework to solve state-tracking tasks by parameterizing the state transition matrix as implicitly dense.

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$ and $S_5$, while matching performance on copying and other tasks.

Fixed-Point RNNs: Interpolating from Diagonal to Dense
Sajad Movahedì 1.2, Felix Sarnthein" 1,2, Nicola Muça Cirone Antonio Orvieto 1.2 'LLLIS Institute Tuebingen, Maa Planck Institute for Intelligent Systems, DDeaarment of Mathematics, Imperial College London {sajad movahedi,
sarnthain www.eeeeeeeeee....eeeeeeerleellt ellis.eu
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 expressivity of RNNs because they rely on channel-wise (i.e.
the full diagonal) sequence mixing. In this paper, we investigate parameterizations of large class of dense linear RNNs as fixed-points of parallelizable diagonal linear RNNs. The resulting models fixed number of parameters and achieve state-of-the-at results on the state- prac-trackiig benchmarks A; and Ss. while matching performance on copying and other tasks.
naturally trade expressivity for efficiency
Introduction
State-space models (SSMs) and other new effi- cient recurrent token mixers are becoming pop- ular alternative softmax attention 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 mod- els can be expressed carefully parametrized linear recurrent neural networks (RNNs) with input-dependent, diagonal state transition:
Max lbrre Aua 3
16
1.0
LS
Test Test,Aoou Accuracy
FP Munie Ir=
0.2
PPStamtett ty-
Pt-ttamte-l tr- 4)
0.0
h diag(a; (a;) h.-1 + B,
(1)
Sequence Length
Figure 1: Sequence length generalization at train- ing length 16 (pink) for state-tracking on As, 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-poin iterations Emax' between 2 (green) and 16 (blue). Increasing the number of fixed- point iterations allows the linear RNN to interpo- late from diagonal to dense in few iterations.
Compared classical RNNs such LSTMs (Hochreiter & Schmidhuber, 1997), in Eq. (1) the relation between the previous hidden state h and the current h, is linear and its coeffi- cient a, does not depend on the hidden states. These choices allow SSMs such 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 al., 2018), At test time, they are faster than classical Transformers on long sequences due to their recurrent nature.
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Though modern linear RNNs have shown promise in practice, recent theoretical studies suggest that using dense, imputdeepnndent transition matrices (i.e. replacing diag(ar) with a dense A,) could present an opportunity to improve expressivity and unlock performance on challenging tasks. In particular, Cirone 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 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 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 h, A, + B,x, two fundamental concerns arise:
1. What should the parametric form for A., as a function of the input be? How can we guarantee this parametrization induces a stable recurrence, like in standard SSMs?
2. How does a parametrization balance between expressivity and parallelism? Which assumptions on the structure of A, 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 diagonaa 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 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-bare based mixing can be implemented efficiently on GPUs as
linear attention via WY-representations and the UT transform (Yang et al., 2024b).
While the works above offer exciting practi- cal strategies for boosting capabilities at rel- atively low additional computational cost, they fall short in exploring the sea of intriguing op- tions for dense transitions and hence, in thor- oughly answering questions (1) and (2) above.
(a) As
(b) Copying
FAMambest
Jest
0.75
Mamba
Mamba
0.50
LSTM
0.25
Unfortunately, this is not an easy task: although linear recurrences are theoretically paralleliz- able 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 viewpoint: instead of designing an algorithm which adds a model,
0.00
30
20
Num Params (M)
Num Params (M)
Figure 2: (a) State-tracking on As at sequence length 16, and (b) character accuracy of copying at 2x sequence length generalization, trained on lengths E 50). Our single layer FP-Mamba- H with mixer reflections r E 21, 21,2,4] is compared to baselines of increasing depth E {1, 2, 4, 6, 8). FP- Mamba-H is the only model capable of solving both the state-tracking and the copy task.
fraction of non-diagonal processing here, we look for a strategy to navigate the par- allelism tradeoff towards truly dense object.
Motivated by the idea of designing a paralleliz- able gencral-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 parametrizing the dense RNN layer as an explicit function h = (x), we build on the literature of equilibrium/implict models (Bai et al., 2019; Ghaoui et al., 2021) to parametrize it implicull as a solution h" to a fixed-point equation = fo(x, h) involving only a diagonal RNN. As described in Fig. 3a, we solve for h" using a fixed-point iteration of diagonal RNN evaluations fo-
"Standard SSMs are diagonal and operate in polar coordinates, parametrizing 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. vI -1-11 11/2 term in Griffin (De et al., 2024)).
2

---

A fundamental question some readers might rightfully ask, is the following: "what is the advantage of iterating single layer depth compared to Septh-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 priori choice on the network size.
Summary. In this work, we propose recipe design a general class of dense linear RNNs as fixed points of corresponding diagonal linear RNNs. Our contributions are:
1. We develop the framework of Fixed-Point RNNs to adaptively trade parallelism for expres- sivity using the number of fixed-point iterations (Fig. 1).
2. We achieve a stable parametrization of a dense RNN via a carefully designed diagonal RNN.
3. The framework allows for easy integration of both non-linear hidden state dependence and linear attention based matrix-valued formulations. This way, our FP-Mamba unites previously isolated capabilities of recurrent computation and memory (Fig. 2).
computatio
2 Background
Since their introduction (Rumelhart et al., 1986; Elman, 1990), RNNs have significantly contributed to the evolution of machine learning methods for sequential data (Hochreiter & Schmidhuber, 1997; Jaeger, 2001). But despite their theoretical promise of Turing- compleeenmseteeess (Siegelmann & Sontag, 1992), recurrent models fell out of fashion due to two significant challenges: they are inherently sequential, and notoriously difficult to train (Hochreiter et al., 2001; Pascanu et al., 2013). The recent advancements of linear RNNs (Gu & Dao, 2024) suggest a way forward combine the scalability of Transformers (Vaswani et al., 2017) with the expressivity of classical RNNs (Cirone et al., 2024b). The key challenge here is the stable and efficient parametrization of a linear RNN layer with a time-varying recurrent transition matrix. In this paper we are exploring first steps towards this goal.
Dense Selective RNN. Traditionally, RNNs are parametrized as either time-invariant, non-linear, or element-wise system. To the best of our knowledge, a time-variant, dense, and linear RNN parametrization has been of mild interest at best. To understand why, consider the general form
Fø x + h,
h = A,h;-1 + B,X:,
(2)
where A, E Rdxd corresponds to the varying state transition matrix, B, E RRdxd is the input transformation matrix, h, E Ed denotes the hidden state, and x, Rdd is the input for fort= < T steps. For a given sequence of Ar, the complexity of a forward pass is ((T)) in memory and O(T) sequential steps. Although such a linear RNN could also be computed in Ollg T) sequential steps using a parallel scan algorithm (Martin & Cundy, 2018), this would require materializing matrix- matrix multiplications at cost (dd)). An issue in both scenarios, however, is the parametrization of A, as time-varying varying, i.c. input- or even hidden deaeedde matrices. In general, this requires a map M : + d with potentially d x d² parameters, and O(T'd) time complexity. While structured dense matrix representations for A, could potentially present remedy, they come with additional challenges: (1) In order to guarantee expressivity, the A, cannot be co-diagonalizable such as for example Toeplitz matrices (Cirone et al., 2024b). (2) In order to guarantee stability of the dynamical system, the spectral radius p(At) needs to be less than, but still close to 1 for long-range interactions (Orvieto et al., 2023). (3) The matrix structure needs to be closed under multiplications to enable parallel scans without having to materialize dense representations at O d²) memory cost.
Related Works. Improving the trainability of classical non-linear RNNs has a long history. For
example, Arjovsky et al. (2016) and Helfrich al. (2018) investigate parameterizations stabilize their spectral radius with structured matrix representations, while Lim et al. (2024) and Gonzalez et al. (2024) propose iterative methods to parallelize their computation. In this work, however, we focus on stabilizing and parallelizing time-variant dense, linear RNN. Improving the limited expressivity of existing diagonal linear RNNs is the focus of few recent works, e.g. by Grazzi et al. (2024) and Siems et al. (2025). In contrast, we investigate wide class of structured parameterizations for dense RNNs where the additional cost adaptively chosen depending on the task. In concurrent work, Schöne et al. (2025) propose an iterative method similar to ours, but as opposed to our carefully designed implicit dense RNN layer, they focus on scaling implicit causal models of existing multi-layer architectures on language. For more extensive literature review, we refer the reader to App. A.
3

---

Draue SyA0
Thast Accurics
H mime A8M0
WC1
Diggoaal X3N (di.bl
Num Ntars
60-
Sequeace Mixerr Ae
04
NCH
23
K. Mike MCD
Channel Maxer Qu
Allel x-
Input
State
Serquence Length
10
Sequence Length
10
10
(a) Framework
(b) State Tracking on As
(c) Number of Iterations
Figure 3: (a) An overview of the proposed Fixed-Poini RNN framework in Sec. 3. A diagonal RNN fo consisting of sequence mixer Ar and channel mixer Q is iterated until convergence towards the hidden states of an implicitly dense RNN Fe. (b) FP-RNN variants with channel mixer introduced in Sec. 3.3 and 3.4 solve the state-tracking task As, up to various sequence lengths. (c) FP-RNNs adapt their computation time the difficulty of the task by varying the number of fixed--poit iterations l
Fixed-Points as an RNN Layer
In this section, we introduce implicit parameterization for family of dense RNNs Fx which describes its output by solution h" Txxx to the fixed-point equation h = fe (x, h) (Sec. 3.1). Then, we discuss how to find the solution h' using fixed-point iterations (Sec. 3.2) and the algorithmic implications (Sec. 3.4) of the FP-RNN framework in light of the challenges outlined in Sec. 2. Finally, we briefly touch on how to train an implicitly dense model (x( with gradient descent (Sec. 3.5).
3.1 From Explicit to Implicit Parameterization
We start by designing a diagonal RNN fe h) such that the solution h to its fixed-point equation (x, h) implicitly represents dense RNN h" (x)x.. Consider the factorized parametriza- tion of A, similar to the one introduced by Helfrich et al. (2018) for non-linear and time-invant invaiiiv RNN:
Fg : x
h = A + B,x.-
Separating A, into a diagonal matrix A, E Rdxd and a non-diagonal invertible mixing matrix Q Idddd allows to describe h" by only diagonal transition A, by reformulating Eq. 3 to
h A,h + Q,B,x, + (I Qi)hh
This means that the states h" = Fo (x) of the dense linear RNN can be implicitly described by the fixed-point h" [x( h²) of a corresponding diagonal linear RNN of the following form:
fo : (x, h) + h';
h = A,hL-1 1 + Q,B,x, + (I Q.,..
(5)
In other words, if we could find the fixed-point h" = fx h-) E Rxxx for the diagonal RNN defined in Eq. 5, then h" would describe the states of corresponding dense RNN h' Fo(x). Motivated by this insight, in Sec. 3.2 we carefully parametrize the diagonal RNN fe(x, h) and its channel mixer Q such that computable fixed-point exists.
3.2 The Fixed-Point Iteration
Solving fixed-point equations such as h = (x, h), is perhaps one of the most well-studied problems in mathematics (Granas et al., 2003). In the context of deep learning, the literature Neural ODEs (Chen et al., 2018) and Deep Equilibrium Models (Bai et al., 2019; Ghaoui et al., 2021) investigates fixed-point methods for implicit parametrizations of neural networks. A straightforward, yet effective method computes the forward pass by simply rolling out the fixed-point iteration. the context iteration in depth he fo(x, h Denoting as the current iteration depth (i.e., over the layer dimension), and as the current iteration in time (i.c., over the sequence dimension), the iteration starts at hς and proceeds with
of solving h" fo(x. x, h²), this corresponds to introducing
h A,h Q,B,x, + (I- hh
(6)
Intuitively, this iteration mixes information with interleaved channel mixing (with Qe) and sequence mixing (with A₂) until convergence towards the hidden states of an implicit dense RNN Fg (cf. 3a).

---

The difficulty with such an iteration in depth and time is that the recurrent dynamics could explode without proper stabilization. While the recurrence in time can be stabilized with RNN techniques (Zucchet & Orvieto, 2024) such as an input gate I - A,, the recurrence in depth, however, could still diverge if [x h) does not have an attracting fixed-point (Granas al., 2003). In order to design a diagonal linear RNN fe (x. h) which is guaranteed to have an attracting fixed-point, we make use of Banach (1922)'s s theorem, In our context, the theorem states that fx h) converges to a fixed-point from any initialization h if it has Lipschitz constant in h. For a fixed-point RNNs with input gate A, we present the following theorem:
Theorem 3.1. Let [x(x, h) be the diagonal linear RNN with input-independent A and Q
fo (x, h) + h',
h/ Ah1-1 (I A) (QB,x, + (I - QI- h.).
(7)
2 1 and |I 21 < 1, then fx h) has Lipschitz constant < in h. Proof in App. B.
Intuitively, Thm. 3.1 states two conditions for stable parametrization of an implicitly dense RNN Fo: (1) the recurrence in time needs to be coupled with input normalization and contractive (i.e.
||A||2< 1). (2) The recurrence in depth acting h, i.e. (I - Q:), needs to be contractive. Together, this guarantees that all sequences h up to h" throughout the fixed-point iteration do not explode without any explicit assumptions on the spectral radius on A (Arjovsky et al., 2016).
3.3 Parametrization of Q and A,
To satisfy the assumptions required for expressivity in (Cirone et al., 2024b), the implicit transition matrix A, and therefore A, and Q, need to be input-controlled (i.e. selective), which could be realized through linear mapping of the input, i.e. Q = _Mxx)) == reshape (WQx)). However, this presents two challenges: how can stability be guaranteed (c.f. Thm. 3.1) and excessive computational cost due to the (d²) parameters of W be avoided? A straight-forward solution lies in structured matrix representations for both the diagonal transition matrix A, and the channel mixer Q₁-
Inspired by Helfrich et al. (2018), we aim for Q to be approximately norm comm-preserving and Ae to control the eigenvalue scale using a parametrization akin to Mamba or Griffin (Gu & Dao, 2024; De et al., 2024) and normalization (I At). For the channel mixers Q,, we consider the structures:
Diagonal Plus Low Rank (DPLR): Q, = M(xx)) = (I En Qut U.. for rank r.
Householder Reflections (H): Q; = _M(x)) = IT (I - ast ū,) for r reflections.
Kronecker (K): Q: MMxx) = I I (K) @ K2?, where denotes the Kronecker product.
This allows to reduce the size of the input-dependent parameters Ost. ūa. and K; to O(d), and consequently reduce the size of the linear map Wq to O(dr) and (dd). In order to guarantee stability, the condition ||I Q|l2< 1 can be enforced by scaling ate ūg. and K; appropriately, For more details about the channel mixer variants, please refer to App. C. Fig. 3b, we compare different channel mixer variants and observe that the Kronecker structure seems be most appropriate the state-tracking task A5-
3.4 Algorithmic Implications
Recall from Sec. that an explicitly parametrized dense selective RNN can only parallelized under strict assumptions on its structure and runs otherwise in O(T) sequential steps. However, parallclizable structure is given by the element- wise, diagonal transition A, of a diagonal RNN (Martin & Cundy, 2018). Since such diagonal RNN is called t -t-ti subroutine of the fixed-poin iteration in Eq. 6, a sreed-point RNN runs in ( log T') sequential steps. This means that the implicit parametrization as opposed to explicit or non-linear parametrizations- allows to decouple the number of sequential steps ?" from the sequence length T itself, and trade parallelism for expressivity.
This insight suggests an opportunity to introduce a non-linear computation for every sequential step, like in classical RNNs. Concretely, we investigate channel mixers M(x; + h which are a function of both the input and the hidden state h from the previous iteration (in both time and depth) without degrading parallelizability In Fig. 3b, we compare channel mixers with and without hidden state dependence and observe that this indeed improves sequence length generalization.
5

---

Summarizing the results so far, we arrive at an updated recurrence with hidden state dependence:
o = X h + (1 - o (Q + (I-Q))h-))
where we use @ to highlight the parallelizability of the element-wise product. We would like to note that due to the normalization (I - A²), the corresponding dense RNN Fø is not explicitly representable anymore as discussed in App. B.2. Furthermore, for the time-varying parametrization in Eq. 8, the convergence guarantees may be weaker and solutions h* could be non-unique due to the hidden state dependence. In practice, we iterate until ||h llh-h"-n -hf < 0.1 and observe that the | oc
conditions of Thm. 3.1 are strong enough to reach convergence within a finite number of iterations e" as evidenced by Fig. 3c. Interestingly, the model navigates the parallelism tradeoff' (Merrill & Sabharwal, 2023) and adaptively increases its sequential computation for harder tasks.
3.5 Optimizing Fixed-Point RNNs
One advantage of converging to a fixed-point as opposed to general layer looping lies in model training. Since the gradient with respect to h is not needed, implicit differentiation can be used to avoid storing and backpropagating through the computational graph of the fixed-point iteration, as discussed by Liao et al. (2018), Bai et al. (2019), and App. B.3. In practice, truncated backpropagation of the last k iterations suffices to approximate the gradient through the full iteration J ~ Jx (h)..)).... Jxhh"). ). For Fixed-Poine RNNS we observe that computing the gradient only at the fixed-point (k- 0), is enough to stabilize training. This means that compared a single diagonal RNN layer, Fixed-Point RNNs incur memory overhead and only sequential overhead in the forward pass but not in the backward pass.
We hypothesize that this is possible because fe(x, h) is a mostly linear object as opposed to multi- layer implicit models such as (Schöne et al., 2025). Furthermore, we observe that hidden state dependence M(x, + hf=i) particularly helps with gradient-base based optimization. We credit this the symmetry between the gradients w.r.t. x and h, and formalize this in the following theorem:
Theorem 3.2. Let fe(x, h) have Lipschitz constant < and fixed-point h". If the Jacobians 050
850 (x, h) and Sh, (x, h) are equal, then the gradient Vo [xxx h), y) of the loss L(,,Y) for a Ux
target y at the fixed point h h² is descent direction of L1 ((Fo(x ((Fo(x),)) y) Proof in App. B.4.
4 Fixed-Point Mamba
(a) As PP-Mamba
(b) As Baselines
In the previous section we introduced the FP-RNN framework vector hidden state. Now, we extend it to
1.0
small RNN with
Tost Accuracy
0.5
0.6
modern matrix state RNNs in Sec. 4.1 and
0.1
parametrize a dense variant of Mamba (Gu & Dao, 2024) in Sec. 4.2. A detailed descrip- tion of the architecture is available in App. C.2. We compare the architecture Mamba (Gu & Dao, 2024), Mamba-2 (Dao & Gu, 2024), Gated DeltaNet (Yang al., 2025), and LTS (Hochreiter & Schmidhuber, 1997) on the copy task introduced by Jelassi et al. (2024) in Sec. 4.3 and state-tracking introduced by Merrill & Sabharwal (2023) in Sec. 4.4. In order to keep the number of layers at the same order of magnitude, we use two layers for the diagonal linear RNN baselines and one layer for FP- Pa-Ma and L.TM. Finally, we discuss the required number of fixed-point iterations in the context of state-tracking and language modeling in Sec. 4.5.
02
0.0
the baselines
(c) Ss - FP.Mamba
(d) S. Baselines
Tost. Accurnyy
a..
Mixer
0.5
R-742
0.4
DPUR-
Munbo
0.2
0.0
Sequence Length
Sequence Length
Figure 4: Length generalization on As (a, c) and Ss (b, d) beyond the train sequence length 16 (pink line). We compare a 1-layer FP-Mamba with mixer variants Q to baselines with 2 layers.

---

4.1 Introducing Matrix States
Memory capacity is an important consideration in RNNs. In preliminary experiments, we notice clear gap between the performance of a Fixed-Point RNNs and Mamba in terms of copying ability. We attribute this difference in performance to Mamba's 's state-expansion which endows it with matrix hidden states similar to linear attention, DeltaNet, or mL.TM (Katharopoulos et al., 2020; Schlag et al., 2021a; Beck et al., 2024). In simple terms, these models use an outer product of an input- dependent vector b, E Ruaee (i.e. the key) and the input vector x, BRdue (i.e. the value) as an input to matrix recurrence with hidden state and transition gate H,, X E R. X danee The hidden state is then contracted with another input-dependent vector C₁ E Rdam (i.e. the query) to get the output y; = c. H. E R rgd
H = A 2
(9)
This matrix- valued recurrence introduces some challenges to our fixed-poin framework. Specifically, in order to mix all the channels over the entirety of the state elements, the mixer has to be fourth-order tensor 2 E IR desm theee dhae X dueer in
H = A @ - + 2 b,x; + (I 2 H
(10)
where * denotes the tensor contraction einsum(klij, ij + kd) with fourth-order identity tensor I of the same shape as Qt. Certainly, computing the fixed-point introduced in Eq. 10 is very challenging both in terms of computation and memory. As we will confirm in Sec. 4.2, one solution is to pass the contracted output y between fixed-point iterations
H = A o H + b, (Qix.) + y
(11)
This implicitly factorizes the tensor mixer Q, into separately mixing along dimension diaee which is used for better expressivity, and dimension datate which is used for better memory capacity.
4.2 FP-Mamba Iteration
Let us apply the the fixed-point RNN framework to the Mamba parametrization. We represent the hidden state as H;, where is the token index (i.e., indexing over the sequence dimension), and / is the fixed-point iteration index (i.e., indexing over the depth dimension). The same notation is used for other variables emphasize when they depend on the input and hidden state of the current iteration.
We propose the following iteration to adapt Mamba with notation from App. C. to the fixed-point mechanism for matrix state RNNs in Eq. 11:
H = A O H
1-1 + D (A. x + (A. Q
(T- x.
y (c)) HH
(12)
L2- 122normalizing by and of allows to limit the Lipschitz constant according to Theorem 3.1. Further- more, we replace the normalization term (1 - (1)) with Mamba's normalization term A, Expanding
yi f-1 yields the recurrence on the matrix state
H X @ H + (A, + "
(13)
where the last term nicely illustrates the two components which mix the channels of the hidden states:
the low-rank matrix (ह -1) mixes over the dimension dstane. while (I - T mixes over the dimension dinns- This factorization significantly simplifies the fourth-order tensor mixer formulation
introduced in Eq. 10, remains expressive as discussed in App. F, and performs well in practice.
Finally, Eq. 12 can be computed as Mamba with an adjusted input x Qf (xr v(-1) y.
H X O H + by (A.x.)
(14)
In other words, one fixed-point step consists of channel mixing using Q., followed by a sequence mixing using Mamba. This separation of concerns allows to speed up the parallel recurrence in time using the Mamba implementation. To find fixed-point, the two phases are repeated until 1y'- < 0.1 is satisfied. After these lx iterations, required for the model to converge to fixed-point, H; and y present the hidden state and output of the dense matrix-valued RNN Fo- Similar to Mamba, we apply gated linear unit g: E Rudu to the output, which we observe to provide slight improvement in performance when present within the fixed-point loop: yf g: Oy!
7

---

Dependence on Yr-1
Test Accuracy
(a) FP FP-Mamia
(b) Baselines
X
Q
b.
Ce
0.11
0.00
/
0.53
0.02
Test Accursiy
Mixer
0.45
0.05
0.55
+ 0.05
Manata
Mambe
DRUR
0.88
0.81
0.01
0.01
DOLB
DR1R
L87N
0.86
0.02
0.94
+ 0.03
Sequence Longth
25
75
100
Sequence Length
75 100
Table Effect of shifted hidden state depen- dence Y on copying at x2 length general- ization. Each column determines which input- dependent component the recurrence Eq. 12 also depends on y Performance unlocked by including hidden dependence for by and et-
Figure Sequence length generalization on the copy task. A 1-layer FP-Mamba-F H matches a 2- layer GatedDeltaNet baseline. Note that the me- dian number of fixed-poine iterations l (gray vertical line) well below the longest training sequence length (pink line).
time
4.3 Shifted Hidden State Dependence y-=1
In preliminary experiments, we observe that even the Fixed-Point RNN with input-dependent pa- rameters and matrix state akin to Mamba-1 is outperformed by Mamba-2 DeltaNet (Dao & Gu, 2024; Yang et al., 2024b) on a copy task. Inspired by the short convolution in Mamba, we investigate the effect of augmenting the input-dependence of parameters X bf. cf. and Qf at iteration & with shifted hidden state dependence. In practice, this means that these are linear functions of x, well as the shifted previous iterate depth y!=1. We refer the reader to App. C.2 for the exact formulation of the dependency.
In Tab. 1, ablate the hidden state dependence for various combinations of X, by Ct, and Householder Q,- Observe that the dependence of b, and c, is crucial to enable the model to copy. In App. C.4, we discuss why this dependence of b, and C could be important for copying. If additionally f-1 A and Qu depend on y the copy task is essentially solvable at x length generalization. We therefore adopt the hidden state dependence for all components in FP-Mamba.
In Fig. 5, we evaluate length generalization on the copying task. While the best rest-performing baseline Gated DeltaNet is specifically designed for associative recall tasks (Yang et al., 2025), both Mamba and 2 struggle with x2 generalization. FP-Mamba closes this gap and proves the effectiveness of our proposed modifications for better memory. We would like to highlight that the number fixed-point iterations t (gray vertical line) in FP-Mamba is well below the maximum sequence length.
4.4 Stace-Tracking
Max Test Seq Lea (Aoc > 90%)
PF HFMambbell
FP FP-Maribe [...1
In Fig. 4, we evaluate the state mate-tracking capabili- ties of FP-Mamba with Kronecker, Householder, and DPLR channel mixers of r E {1, 2,4 4] re- flections ranks, respectively. In particular, compare our FP-Mamba to the baselines with regards their length generalization beyond the training sequence length 16. As expected, LSTM solves As and Sg. while Mamba and Mamba-2 are not able to learn it even at the training sequence length. Similar the Kronecker structure seems to be the most suitable for the task. But FP-Mamba based on Householders also improves in terms of se- quence length generalization presumably due to its improved memory. A comparison to the recent DeltaProduct (Siems et al., 2025) on train- ing sequence length 128 is available in App. E.2.
Manta
Munbel
GateiDDitaNett
30
At m4
20
200
300
400
500
600
700
800
900
Tratn Time
Fig. 3b,
Figure 6: Length generalization as a fanction of train- ing time on As. Wall clock time is plotted against the longest test sequence length with > 90% accuracy for every model. While baselines increasing depth can- not generalize beyond the training sequence length 16 (horizontal pink line), our proposed framework allows to achieve much higher generalization by scaling training time through the number fixed-ppn point iterations t.
8

---

4.5 Required Number of Iterations E'
Layer #1
Layer #2
Layer #3
A fixed-point iteration in the forward pass in- evitably introduces sequential overhead to the computation of model. While this might be acceptable for sequential generation at test time, reduced parallelism can be inhibiting at training time. In Fig. 1, we therefore eval- uate FP-Mamba-H on AG with limited num- ber of fixed-point iterations at training time lmax E {2. 4, 8, 16]. We observe that the per- formance decreases once mmux is lower than the training sequence length of 16. In Fig. 6, we con- firm that the resulting longer training times are indeed required for good length generalization. However, opposed to baselines of increas- ing depth E (1, 2. 4, 6, 8). fixed-point iterations gain from the additional training time. Further- more, there is room to improve efficiency, as suggested by simple randomization scheme (gray stars) where mmxx ~ [(4, )) is sampled from a Gamma distribution with mean 4 for every batch. But most importantly, the effective number of fixed-point iterations depends on the difficulty of the task. Indeed, Fig. 7 shows that the model automatically adapts to using less fixed-poin iterations on language pretraining at context length 2048. Similarly. on copying (Fig. 5) and and modular arithmetic (Fig. 10), we observe that the required number of fixed-poine iterations l is well below the sequence length T. This suggests that the model adapts to (TT) complexity on simpler tasks when the full state-tracking expressivity is not required.
20
Layer #4
Layer #5
Layer #6
40
20
Num Iters
Layer #7
Layer #8
Layer #9
60
20
Layer #10
Layer #11
Layer #12
40
Train Neration
Figure 7: The effective number of fixed-point iterations for each layer of a FP-Mamba-H throughout language pretraining
FineWeb (Penedo al., 2024) context length 2048. The corresponding validation perplexities are available in App. E.I.
Forward
Backward O(T)
5 Discussion
Mamba FP-Mamba
O(T)
O ((T + Cq.) min(E" bmxx)
O(T + Cq.)
A fixed-point mechanism, such the one introduced in this paper, endows parallelizable, diagonal linear RNN with the ability to dynamically increase the sequential computation and describe a dense linear RNN enable both strong state-tracking and memory
Table 2: Complexity of FP- Mamba in comparison to Mamba. The cost of channel mixing with structure Q: is denoted by Ca.-
in the limit. Our results show that such a paradigm capabilities with a constant number of parameters in a combined sequence and channel mixing layer (Fig. 2). In fact, the fixed-point iteration gradually transforms a diagonal (i.e., channel-wise) RNN into a dense (i.e., channel-mixing) RNN, thereby allowing to trade parallel computation for expressivity (Fig. 1) without incurring additional cost during backpropagation (cf. Tab. 2).
For Fixed-Point RNNs to become competitive in practice, it is important to further understand the trade-offss between parallel and sequential computation. In the worst case, shown in Tab. 2, FP- RNNs could behave like traditional, non-linear RNNs with quadratic runtime (T2) if the sequential overhead E" is linear in the sequence length T. This, however, is not necessarily disadvantage since FP-RNNs adapt& En to the difficulty of the task. In this paper, we focus on introducing the framework for FP-RNNs and leave the improvement of fixed-point convergence rates future work.
Fixed-Point RNNs present an interesting opportunity to be fused into a single GPU kernel with reduced memory I/O. This is an inherent advantage from performing repeated computation on the same operands. Several open problems need to be solved to achieve that: (1) different implementations such sequential, parallel, chunk- wise should converge to the same fixed-pointe (2) the memory footprint of the fixed -eoitt iteration should satisfy current hardware limitations, and (3) alternative sequence or channel mixer structures could unlock higher efficiency. Future progress on these problems could enable significant speed-ups in practical implementations of Fixed-Point RNNs.
Conclusion In this paper, we presented a framework to cast general class of dense linear RNNs as fixed-points of corresponding diagonal linear RNNs. Fixed- Printt RNNs provide mechanism to trade computation complexity for expressivity while uniting the expressivity of recurrent models with the improved memory of linear attention models. Following encouraging results on toy tasks specifically designed to assess these capabilities, we hope this paper enables more expressive sequence mixers.

---

Acknowledgments and Disclosure of Funding
We would like to thank Riccardo Grazzi and Julien Siems for the helpful discussions and comments. Antonio Orvieto, Felix Sarnthein and Sajad Movahedi acknowledge the financial support of the Hector Foundation. Felix Sarnthein would also like acknowledge the financial support from the Max Planck ETH Center for Learning Systems (CLS).
References
Ajroldi, N. plainlm: Language model pretraining in pytorch. Niccolo-Ape Miccolo-Ajroldi/pllaa. Ajroldd/ppainlM, 2024.
https://githum com/
Arjovsky. M., Shah, A., and Bengio, Y. Unitary evolution recurrent neural networks. In Proceedings of The 33rd International Conference on Machine Learning, pp. 1120-1128, 2016. URL https: // arxiv. org/ abs/1511. 06464.
Arora, S., Eyuboglu, S., Zhang, M., Timalsina, A., Alberti, S., Zou, J., Rudra, A., and Ré, C. Simple linear attention language models balance the hccall-trroghhuut tradeoff. In Forty-first International Conference on Machine Learning. ICML 2024, 2024. URL attps://arxiv. 18668.
abs/ 2402.
Bai, S., Kolter, J. Z., and Koltun, V. Deep equilibrium models. In Advances in Neural Information Processing Systems, pp. 688 699, 2019. URL https://axxix wwwpeiiiiiioooiooeeeeeeeeeoeeeee ////a///119900 01377.
Bai, S., Koltun, V., and Kolter, J. Stabilizing equilibrium models by jacobian regularization. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, pp. 554-565, 2021. URL https: / arxiv. org/ abs/2106 14342.
Banach, S. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta mathematicae, 3(1 3(1):133-181 1922.
Beck, M.. Pöppel, K., Spanring. M., Auer, A., Prudnikova, O., Kopp, M., Klambauer, G., Brandstetter, J., and Hochreiter, xlstm: Extended long short-term memory. In Advances in Neural Information Processing Systems 38, NeurIPS 2024, 2024. URL https:/ aarxiv. org/ /bs///b//// 2405. 04517.
Chen, R. T. Q., Rubanova, Y., Bettencourt, J., and Duvenaud, D. K. Neural ordinary differential equations. In Advances in Neural Information Processing Systems, 2018. URL /ttps:///rxiii org/abs/188 07366.
Chen, Y., Zeng, Q., Ji, H., and Yang, Y. Skyformer: Remodel self-attention with Gaussian kernel and Nystrom method. Advances in Neural Information Processing Systems, 2021. URL https: //arxiv.oorg abs/ 221.. 2111.00035..
Choromanski, K. M., Likhosherstov, V., Dohan, Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J. Q., Mohiuddin, A., Kaiser, I.., et al. Rethinking attention with performers. In International Conference on Learning Representations, 2020. URL pettts://arree
org/argg///.o.ooooo...o aaa///b///00 2009. 14794.
Cirone, N. M., Hamdan, J., and Salvi, C. Genus expansion for non non-linear random matrix ensembles with applications to neural networks, 2024a. URL https: / /twpiv.ivvv./////.//aaa//aaaavva wwwexii..rrr.oo..o ab////////2///////////////////// 20tp//477.0849. 08459.
Cirone, N. M., Orvieto, A., Walker, B., Salvi, C., and Lyons, T. Theoretical foundations of deep selective state-space models. In Advances in Neural Information Processing Systems, volume 37, pp. 127226-127272. 2024b. URL https: / arxiv org/ abs abss/240 2402. 19047.
Dao, T. and Gu, A. Transformers ssms: Generalized models and efficient algorithms through structured state space duality. Forty-first International Conference on Machine Learning. ICML 2024, 2024. URL https: // arxiv org/ abs/ 21060.
De. S., Smith, L., Fermando, A., Botev, A., Muraru, G., Gu, A., Haroun, R., Berrada, L., Chen, Y., Srinivasan, S., Desjardins, G., Doucet, A., Budden, D., Teh, Y. W., Pascanu, R., de Freitas, N., and Gulcehre, C. Griffin: Mixing gated linear recurrences with local attention for efficient language models, 2024. URL https:/ / arxiv org/abs/ /bsp///2.../4444
10

---

Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, L. Universal transformers. In 7th International Conference on Learning Representations, ICLR 2019, 2019. URL https: // //arxiv... org/ abs/1807.03819. 03819.
Elman, J. L. Finding structure in time. Cognirive science, 1990.
Geiping, J.. McLeish, S., Jain, N., Kirchenbauer, J., Singh, S., Bartoldson, B. R., Kailkhura, B., Bhatele, A., and Goldstein, Scaling up test-time compute with latent reasoning: recurrent depth approach. In ES-FoMo III: 3rd Workshop on Efficient Systems for Foundation Models, 2025.
URL https: //t:://aaxivv org/ wwwp/a/g///////ooooo//ooo/eeee// abs/2502 011771...........
Ghaoui, E., Gu, F., Travacca, B., Askari, A., and Tsai, Y. Implicit deep learning. SIAM Math.
Data Sci., 3:930-958, 2021. URL https: /arxivv.vvvvv//////////////v/v org/abs/ 1908. 06315.
Giannou, A., Rajput, S., Sohn, J., Lee, K., Lee, D., and Papailiopoulos, D. Looped transformers as programmable computers. International Conference on Machine Learning, ICMI. 2023, pp- 11398-1 1442, 2023. URL https: : //arxivv.vv///////// org/ abs/ /201..2311.... 13196.
Gonzalez, X., Warrington, A., Smith, J. T., and Linderman, S. Towards scalable and stable paral- lelization of nonlinear RNNs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. htlthttts//aaaee
org/ batg//bs//eee aaaaabb//200/ 19115.
Granas, A., Dugundji,, J., et al. Fixed point theory, volume 14. 2003.
Graves, A. Adaptive computation time for recurrent neural networks, 2016. URL https://arxiv.
org/ htg//bb//tt /103. 08983.
Grazzi, R., Siems, J., Franke, J. K., Zela, A., Hutter, F., and Pontil, M. Unlocking state-tracking in linear RNNs through negative eigenvalues. In NeurIPS 2024 Workshop on Mathematics of Modern Machine Learning, 2024. URL https: //appii///axvv...///// org/ abs/ 12537.
Gu, A. and Dao, Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling, 2024. URL https: awwpvv..ivvvvv http:://wwwwww.ooa/a/////saa 2312 00752.
Gu, A., Goel, K., and Ré, C. Efficiently modeling long sequences with structured state spaces. In The Tenth International Conference on Learning Representations, ICLR 2022, 2022. URL https: hatps://arrxxti org/ abs//a/// //t./......./.... 00396.
Hanson, J. and Raginsky, M. Universal simulation of stable dynamical systems by recurrent neural nets. In Learning for Dynamics and Control, 2020. URL http:: h/p.oeee///r mwm. press/ 1120/hanson20a.. html.
Helfrich, K., Willmott, D., and Ye, Q. Orthogonal recurrent neural networks with scaled Cayley transform. Proceedings the the 35th International Conference on Machine Learning, pp. 1969- 1978, 2018. URL https: / /rrxiv.. org/ wwg/abs/////eeeoeoeoogoooee abs/1707 .09520.
Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural computation, 1997.
Hochreiter, S., Bengio, Y., Frasconi, P., et al. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies. Field Guide to Dynamical Recurrent Neural Networks, 2001.
Hopfield, J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, (9(8))2554-2555 1982.
Jaeger, H. The "echo state" approach to analysing and training recurrent neural networks-with an erratum note. German National Research Center for Information Technology GMD Technical Report, 2001.
Jelassi, S., Brandfonbrener, D., Kakade, S. M., and Malach, F. Repeat after me: Transformers are better than state space models copying. In Forty-first International Conference on Machine Learning, ICML 2024, 2024. URL https: //aaaiv///////////aaaaaaeaaaaaaa org/a///// abs/2402. 01032.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are mas: Fast autoregressive transformers with linear attention. International Conference on Machine Learning, 2020. URI https: //arxv///ivv////a///aa org/ htsp/bbs/2000 16236.

---

Korsky, S. A. On the computational power of RNNs. PhD thesis, Massachusetts Institute of Technology. 2019. URL httpss////daa mit. wat.u//andl///eeaaaaaaaaeeeeeeee htt.aa/e/2...11111111/.. 1/12774
Liao, R., Xiong. Y., Fetaya, E., Zhang, L., Yoon, K., Pitkow, X., Urtasun, R., and Zemel, R. Reviving and improving recurrent back-pron paoo-propggttion. In Proceedings of the 35th International Conference on Machine Learning, pp. 3082-3091, 2018, URL https::tp//// /aattps///rxiv..../ wwtgg//////aaa /803. 06396.
Lim, Y. H., Zhu, Q., Selfridge, J., and Kasim, the sequence length. In The Twelfth International Conference Learning Representations, ICLR 2024, 2024. URL https: / /tt///axxvvv///////////////aaaa/ org/ hb///b///220 2309. 12252.
Parallelizing non-linear sequential models over
Liu, Y., Tian, Y., Zhao, Y., Yu, H., Xie, L.., Wang, Y., Ye, Q.. Jiao, J., and Liu, Vmamba: Visual state space model. In Advances in Neural Information Processing Systems 38, NeurlPS 2024, 2024. URL aattps://arxtae
org/ bogg/ba//2e0 abs/2440..0114
Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representationss 2017. URL https://arxiv arg/abs/ /1s//111... 05101.
Martin, E. and Cundy, C. Parallelizing linear recurrent neural nets over sequence length. In 6th International Conference on Leurning Representations, ICLR 2018, 2018. URL https: // //arxiv. org/ abs 04057.
Merrill, W. and Sabharwal, A. The parallelism tradeoff:: Limitations of logepreciiion transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023, URL https: //arxiv..o org/ 2207. .07229.
Merrill, W., Petty, J., and Sabharwal, A. The illusion of state in state-space models. In Forty-first International Conference on Machine Learning, 2024, 2024. URL htttttt////rxxt org/
Miyato, Löwe, S., Geiger, A., and Welling, M. Artificial kuramoto oscillatory neurons. In The Thirteenth International Conference on Learning Representations, 2025. URL httts://arxiv org/aba /a////b//24/// /2100.400000 13821.
Nguyen, E., Poli, M., Durrant, M. G., Kang, B.. Katrekar, D., Li, D. B., Bartie, L. J., Thomas, A. W., King, S. H., Brixi, G., et al. Sequence modeling and design from molecular to genome scale with Evo. Science, 2024. URL https: //wwww science orgeeee.rrr/deee org//oi/////oooooooo 126/s22ennnn ado9336.
Orvieto, A., Smith, S. L.,, Gu, A., Fernando, A., Gulcehre, C., Pascanu, R., and De, S. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, 2023. URL https: htt///aaxvvvv./////////////.aavv org/ abs 20...3333333
Pascanu, R., Mikolov, T., and Bengio, Y. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, 2013. URL https: //axxvv./////////a org/ hatg///////// htt//bb//111.. /211. 5063.
Penedo, G., Kydlíček, H., allal, L. B., Lozhkov, A., Mitchell, M., Raffel, C., Werra, L. V., and Wolf, T. The fineweb datasets: Decanting the web for the finest text data at scale. In The Thirty-eight Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2024. URL htttps///arxiyy .rg/ ab/////////0 17557.
Peng. B., Goldstein, D., Anthony, Q., Albalak, A., Alcaide, E., Biderman, S., Cheah, E., Du, X., Ferdinan, T., Hou, H., al. Eagle and Finch: RWKY with matrix-valued states and dynamic recurrence. In First Conference on Language Modeling, 2024. URL https: aattps://arxts http://axxvvvv.//e org/ /bs// 2404.05899
Peng, B., Zhang, R., Goldstein, D., Alcaide, E., Du, X., Hou, H., Lin, J., Liu, J., Lu, J.. Merrill, W. Song, G., Tan, K., Utpala, S., Wilce, N., Wind, J. S., Wu, T., Wuttke, D., and Zhou-Zheng, C. Rwky-7 "goose" with expressive dynamic state evolution. Second Conference on Language Modeling, 2025. URL htttps:/aaxxi: org/ wwg//tgg///////ooooo/o.ooe.aeeee abs//503...... 14456.
Qin, Z., Yang, S., Sun, W., Shen, X., Li, D., Sun, W., and Zhong, Y. HGRN2: Gated linear RNNs with state expansion. In First Conference on Language Modeling, 2024. URL. https: // arrxivv org/ 0et./2444.7999
12

---

Rumelhart, D. E., Smolensky, P., McClelland, J. L., and Hinton, G. Sequential thought processes in pdp models. Parallel Distributed Processing: Explorations in the Microstructures of Cognition. 1986.
Sarrof, Y., Veitsman, Y., and Hahn, M. The expressive capacity of state space models: A formal language perspective, In The Tiihty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: /aae://axxii /arxiv. org/ brg/abs/// abss/2405 10000..73990 17394.
Saunshi, N., Dikkala, N., Li, Z.,, Kumar, S., and Reddi, S. Reasoning with latent thoughts: On the power of looped transformers. In International Conference on Learning Representations (ICLR), 2025. URL https: htttps://aaxxv..oo org/ aba/ 17416.
Schlag, I., Irie, K., and Schmidhuber, J. Linear transformers are secretly fast weight programmers. In International Conference on Machine Learning, 2021a. URL aattps://arxxe 11174.
Schlag, I., Munkhdalai, T., and Schmidhuber, J. Learning associative inference using fast weight memory. International Conference on Learning Representations (ICLR), 2021b. URL https: //openreview
Schwarzschild, A., Borgnia, E., Gupta, A., Huang, F., Vishkin, U., Goldblum, M., and Goldstein, T. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. In Advances in Neural Information Processing Systems 34: NeurlPS 2021, pp. 6695-6706, 2021. URL https: arrxivvvvvv.....//vi//avaav/v..v org/ httg/bbs/2111 2206. 20211.6666......
Schöne, M., Rahmani, B., Kremer, H., Falck, F., Ballani, H., and Gladrow, J. Implicit language models
mns: Balancing parallelization and expressivity. In Forty-second International Conference Machine Learning, 2025. URL https: : /arxiv.vv....... httpa/awwww....aaaaaaaaae/a/aaaa /a0a 07827.
Siegelmann, H. T. and Sontag, E. D. On the computational power of neural nets. In Proceedings of the fifth Annual Workshop Computational Learning Theory, 1992.
Siems, J., Carstensen, T., Zela, A., Hutter, F., Pontil, M., and Grazzi, R. Deltaproduct: Increasing the expressivity of deltanet through products of householders. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https: arrxvv. org/ //s//bb//// 0abb/2500.100 10297.
Smith, J. T., Warrington, A., and Linderman, S. Simplified state space layers for sequence modeling. In International Conference on Learning Representations, 2023. URL pestts://arxxx org/ abs/ /2088. 04933.
Sun, Y., Dong, L., Huang, S., Ma. S., Xia, Y., Xue, J., Wang, J., and Wei, F. Retentive network: A successor to transformer for large language models, 2023. URL https::/t///aaa /ttppp/////xxi.o//////a// abs/ 2307 08621.
Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., and Metzler, D. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020. URL https: // arxiv. . org/ abs//bss////0 00001.10100.....1111111100110110
Terzic, A., Hersche, M., Camposampiero, G., Hofmann, T., Sebastian, A., and Rahimi, A. On the expressiveness and length generalization of selective state space models on regular languages. Proceedings of the AAAI Conference on Artificial Intelligence, pp. (1876-20884, 2025. URL fctps://arxiis org/ abs /bsp///..... /2122 19350.
Trockman, A., Harutyunyan, H., Kolter, J. Z., Kumar, S., and Bhojanapalli, S. Mimetic initialization helps state space models learn to recall. In Workshop on Neural Network Weights as a New Data Modality, 2024. URL https: //tp///axvvvv./a////i//////a.aaa org/ abs//410 11135.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, I.., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. Advances Neural Information Processing Systems, 2017. URL https: // //axiviivvaa orgo/og//aa ab///bb//// abss/700..o 03762.
Waleffe, R., Byeon, W., Riach, D., Norick, B., Korthikanti, V., Dao, T., Gu, A., Hatamizadeh, A., Singh, S., Narayanan, D., et al. An empirical study of Mamba-based language models, 2024. URI https:/ /ote:://arre /aaxxixivvv/////////ae///aaa wrw. 22//a/bb..///..///// 07887.
13

---

Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity, 2020. URL httph: //arxvv..ivvv//. org/ wwgg/abs/2006.. 04768.
Weston, J., Bordes, A., Chopra, S., Rush, A. M., van Merriënboer, B., Joulin, A., and Mikolov, Towards Al-complete question answering: A set of prerequisite toy tasks, 2015. URL https: //arxiv. org/ absaabas/22. 05698.
Yang. S., Wang, B., Shen, Y., Panda, R., and Kim, Gated linear attention transformers with hardware-efficient training. In Forty-first International Conference Machine Learning, ICML 2024, 2024a. URL https:/ / /ttp:///avvv.v//e org/ 2012. 06635.
Yang. S., Wang, B., Zhang, Y., Shen, Y., and Kim, Y. Parallelizing linear transformers with the delta rule over sequence length. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b. URL https /ttppi:///axiv.... org/ abs/ /206. 06484.
Yang, S., Kautz, J., and Hatamizadeh, A. Gated delta networks: Improving mamba2 with delta rule. In The Thirteenth International Conference on Learning Representations, 2025. URL atttp:///axxe wwt..bgg////.o...o..oo..o......a /bt. 06464.
Zucchet, N. and Orvicto, A. Recurrent neural networks: vanishing and exploding gradients not the end the story. Advances in Neural Information Processing Systems, pp. 139402-139443, 2024. URL https: // /arxiv.... org/ wtwp////555. 21064.
14

---

Appendices
Background and Literature Review (Sec.
16
Fixed-Points as an RNN Layer (Sec. 3)
17
B.1 Proof for Theorem 3.1 (Lipschitz constant of fx(x, h) is 1)
17
B.2 Effect of normalization factor (I 1--A, A,) on class of matrices A,
17
B.3 Implicit Differentiation for Optimizing Fixed-Point RNNs
18
B.4 Proof for Theorem 3.2 (Gradient of fo(x, h) is descent direction of Fo(x))
18
Fixed-Point Mamba (Sec. 4)
19
C.1 Mamba: Selective SSMs
19
C.2 FP-Mamba Parametrization.
19
C,3 Parameterizing the mixers
19
C,4 Dependence on H,-1 in theory
20
D Evaluation
21
D.1 Task Descriptions
D.2 Experimental Details
21
D.3 Heuristics to reduce the number of fixed-point iterations
22
Additional Experimental Results
23
E.1
Language Modeling
23
................................
E.2
Long-Range State-Trackin
23
................................
E.3
Reasoning on CatbAbl
24
E,4
Modular Arithmetic Task Results
25
E.5 Effect of max on test performance and number of iterations l
26
E.6
Sequential Parallel Fixed-Point Iteration
26
Low-Rank Expressiveness
27
15

---

A Background and Literature Review (Sec. 2)
Since their introduction (Rumelhart et al., 1986; Elman, 1990), RNNs have significantly contributed to the evolution of machine learning methods for sequential data, marked by key innovations such as the LSTM (Hochreiter & Schmidhuber, 1997) and Echo-State Networks (Jaeger, 2001). However, two significant challenges lead to the widespread adoption of the Transformer architecture ( (Vaswani et al., 2017); first, GPU hardware optimized for large-scale matrix multiplications. Second, recurrent models are notoriously difficult to train due to vanishing and exploding gradients (Hochreiter et al., 2001; Pascanu et al., 2013).
Beyond softmax attention. The quadratic runtime complexity of Transformers motivated research on the linearization of its attention mechanism (Wang et al., 2020; Chen et al., 2021; Choromanski al., 2020)- technique that inevitably brings the sequence mixing mechanism closer to RNN- like processing (Katharopoulos et al., 2020; Schlag et al., 2021a). Recently, improvements on the long-range-aremi benchmark (Tay et al., 2020) with state-space models (Gu et al., 2022; Smith et al., 2023) sparked renewed interest in recurrent models (Gu & Dao, 2024; Sun et al., 2023; De et al., 2024; Qin al., 2024; Peng et al., 2024; Yang al., 2024a). New efficient token mixing strategies such as Mamba (Gu & Dao, 2024) showcase impressive results in language modeling (Waleffe et al., 2024) while offering linear runtime complexity. These models are fundamentally diagonal linear RNNs, which enables parallel algorithms such as parallel scans (Martin & Cundy, 201 8) and fast linear attention based implementations (Yang et al., 2024b; Dao & Gu, 2024).
Expressivity of Diagonal vs. Dense RNNs. It was recently pointed out by Cirone al. (2024b) that the diagonality in the hidden-to-hidden state transition inevitably causes expressivity issues, showcas- ing a stark distinction with classic dense nonlinear RNNs, known to be Turing-complete (Siegelmann & Sontag, 1992; Korsky, 2019) and fully expressive in a dynamical systems sense (Hanson & Ragin- sky, 2020). Merrill et al. (2024) pointed at similar issue with diagonality using tools from circuit complexity: in contrast to e.g. LSTMs, diagonal linear RNNs can not express state-tracking algo- rithms. This issue sparked interest in designing fast non- non-diagonal recurrent mechanisms and, more generally. in providing architectures capable of solving state- trackeng problems. The first example of such an architecture DeltaNet ( (Yang et al., 2024b) employing a parallelizable Housholder reflection as a state transition matrix. Endowing this matrix with negative eigenvalues improves tracking in SSMs (Grazzi et al., 2024). In concurrent work, Siems et al. (2025) show that adding more reflections improves state-tracking.
Toy tasks. Several works propose toy tasks to identify specific shortcomings of modern archi- tectures. Specifically, Beck al. (2024) use the Chomsky hierarchy organize formal language tasks, of which a modular arithmetic task remains unsolved. With similar motivations, Merrill & Sabharwal (2023) introduce set of word-problems for assessing tracknng capabilities, among which the As and S₁ tasks remain unsolved by Transformers and SSMs. Motivated by Transformers outperforming RNNs in memory capabilities, Jelassi et al. (2024) introduce copying task as a fundamental benchmark for memory. We focus on these tasks to evaluate our Fixed-Point RNN framework.
Recurrence in Depth. Machine learning models that reduce intrinsic energy through iterations have been an object of interest for decades (Hopfield, 1982; Miyato et al., 2025). For example, recur- rence in depth can increase the expressivity of Transformers (Dehghani et al., 2019; Schwarzschild et al., 2021; Giannou et al., 2023; Geiping et al., 2025) and is sometimes also understood as adaptive compute time (Graves, 2016). Under certain assumptions, iterated blocks can converge to equilib- rium point where they implicitly describe an expressive function (Bai et al., 2019; Ghaoui et al., 2021), )). Recently, this technique has been used to approximate non-linear RNNs with fixed-point iteration of parallelizable linear RNNs (Lim et al., 2024; Gonzalez et al., 2024). In concurrent work to ours, Schöne al. (2025) apply iteration in depth to Mamba-2 and Llama blocks increase expressivity and show promising results of their implicit language models. In contrast, we derive an explicit fixed-point iteration towards a dense linear RNN with a theoretically motivated parameterization, and focus on theoretical toy tasks.
16

---

B Fixed-Points as an RNN Layer (Sec. 3)
B.1 Proof for Theorem 3.1 (Lipschitz constant of fo( h) is < <)
Theorem 3.1. Let fe(x, h) be the diagonal linear RNN with input-independen A and Q
So : (x, h) + h', ||| and ||I Q11 1, then fe (x, h) has a Lipschitz constant < h. Proof in App. B.
+ (I- A (QB,x, + (1-
(7)
We start the proof with the unrolled form of the linear RNN
fo h): - A
+ Q)
7=0
Note that in order prove the theorem, need to show that
[x, h), fo(x, h < 1|h-b'l
where h and ht' are two arbitrary hidden states. From the unrolled form, this is equivalent
1
Σ (1-) Q) (h, -h,) < <Ih h'll2-
(15)
T=
From the Cauchy-Schwand inequality, we can upper-hound the LHS of Eq. 15
(h, Σ T (I- - T=
S Σ A' |I
nt)
Ale | Q112 laa h'eell
where hę corresponds to the concatenation of the hidden states h, for S t. Now prove this product is | h'll2. consider the terms individually. Since h hlzell2 S h h' 2 the remaining terms need to be 1. Assuming A is contractive, we use the Neumann series
Ei=o A < A)-1 and get
r T
Σ r=0
A S 1.
Finally, it remains to show that
I- I-Qll 1.
This condition can be satisfied I Q is contractive. This completes our proof.
B.2 Effect of normalization factor ([A on class of matrices A,
For the sake of exposition, the introduction of the implicit parametrization in Sec. 3.1 did not consider input normalization (I A.). However, as discussed in Sec. 3.2 this crucial component to stabilize the recurrence in time. To derive the representable dense matrices A, in the presence of the normalization factor (I A,), let us start by assuming fixed-point was found according Thm. 3.2:
h = A,hi-1 + (I A.)(Q,Bix, + (I-Q, Q.)h;
A,hi-1 (I A.) + (I A:) Q.)hi.
Rearranging the terms allows to move h; to the other side
(I (I- AJ) Q.));; = A, (I A,
Moving (I- - (I AT (I- Q:)) back to other side yields
A, (I - (I A.) Q.))
(1- A, -1- Q:)))
-A-1- -I -

---

Following the standard assumptions that 0 < A., Q = I, the matrix (I (A, I)Q,) is full rank and = Therefore its inverse A, exists and is contractive. The expressivity of A, only limited if A, R I. This however would also be problematic for diagonal SSM and therefore the Mamba initialization bias towards A, < I. Thus, the normalization does not pose a significant problem for the expressivity of A, in practice.
B.3 Implicit Differentiation for Optimizing Fixed-Point RNNs
One advantage of converging fixed-point over general layer looping lies in model training. Since the gradient with respect to ho is not needed, implicit differentiation can be used to avoid storing and backpropagating through the computational graph of the fixed-point iteration, discussed by Liao et al. (2018), Bai et al. (2019), To see this, consider the Jacobian across & iterations J ASa 0x (x, h ".. Since h depends on as well, 0se (x, h) and Jn 0h J and the Jacobians of single iteration Jx (h) ãx
recursively express J in terms of 0fg (x. h) by applying
the chain rule
x (h + Jnc-1 1 J&-1
(16)
Instead of unrolling, we can implicitly differentiate h' [x h*) w.r.t x, which yields J Jx(h")++ + Jn. Jxx Given the conditions on the Lipschitz constant of fx(x, h) in h, we can assume Jn to be contractive and therefore (I IJJn;) ) to be positive definite and invertible. This allows to reformulate as
J
Jn-) -x
(17)
The case for J works analogously. This means that the gradient w.r.f. the input xr and parameters can be computed the fixed-point with the cost of solving (I Jn-)-1 Bai et al. (2021) and Schöne et al. (2025) approximate this inverse using the first terms of the Neumann series, which leads to a truncated backpropagation formulation or phantom gradients, incurring sequential overhead. For iteration with hidden state dependence, we can avoid this inversion altogether with Thm. 3.2:
Theorem 3.2. Let fo(x, h) have Lipschitz constant < and fixed-point h". If the Jacobians 05g
öie (x, h) and Sh (x, h) are equal, then the gradient V VoC(fe(x, y) of the loss L(:,y) for a target y at the fixed point
h² is a descent direction of ((Fo Proof in App. B.4.
In simple terms, Thm. 3.2 shows that parameterizing (x, h) such that Jx( Jn guarantees optimization progress even if the gradient computed only at the fixed-point. practice, we observe that adhering to this condition in the form of hidden state dependence speeds-up the convergence of the model during training.
B.4 Proof for Theorem 3.2 (Gradient of fo(x, h) is a descent direction of Fx(x))
We start the proof by setting 8 Oc and Jx Jx(h)). Then, we can write the backward of
propagation as ac (J2) 8. In order to prove that the gradient computed at the fixed-point is descent direction, we need to show that J 8 is in the direction of (J²) 8, or in other words, we have 8 J > O. This is equivalent to showing that the symmetric part of the matrix J.J is positive semi-defintt.
Now note that from Eq. 17 we have: J.J (I- J.JJ I From our assumption Jx Jn J, we need to show that the symmetric part of the matrix (I JJ -1 JJJ is positive semi-definite. Note that (I - J)-1 and J commute by application of the Neumann series
(I [I-J-- Σ J
-( 0=
1=1
Going back to the definition of positive semi- definiteness, we need to show that 8 J (I J) J 8 > 0 for all 8. Setting w = J this is equivalent having w (I (I-J) - w. Note that from our assumption for the Lipschitz constant of the function, we have ||J]|| < 1, which means (I - J) and (I J) have strictly positive eigenvalues. This completes our proof.
which yields (I- - JJ- JJJ = [[- J) J
18

---

C Fixed-Point Mamba (Sec. 4)
C.1 Mamba: Selective SSMs
Mamba a multi-layer network, with an embedding size of mmode-- A Mamba block is a matrix state diagonal linear RNN which first expands sequence of embeddings by factor of e to size dinner e X dmodel, and then computes an element-wise recurrence on the matrix hidden states H2 Rdam X dimer
H. b H4-1 by (Axx))
(18)
where Ae E I teo duee is an input- delendent state transition vector, b, E R an input transi- tion vector, X₁ E Rawa the input, and A E R4 xdue a diagonal matrix which acts an input normalization term. The matrices parameterized as:
A = c (r)
Auug = exp (w), b, WbX,,
A diag (softplus (W Axx + ba)),
with E RRd Xduser WA A Rduuex Wb Rduux and ba Rdume The output of Mamba block Yt E [Rce is a contraction of the matrix hidden state with C₁ E Rdd
yr c. H, C₂ W
for We E de x Xdueer Note that Mamba proposes skip connection of +D xx2, where D E Rd an input- inpteinndepnneent vector. Finally, the model output is usually scaled by a gated linear unit (GLU) y, ge yo, where g: SiLU (W gxx) is non-linear function of the input.
C.2 FP-Mamba Parametrization
In our design of FP-Mamba, we aim to minimize our interventions in the underlying architecture in order to showcase the adaptability of our proposed framework. Consequently, we do not modify careful parameterization of and the weight-tied normalization factor A, proposed in the original Mamba formulation, and instead rely on layer normalization to limit the Lipschitz constant of the Mamba function. Specifically, in the FP-Mamba model we redefine b, and c, as by W + W and C W f-1 W The remaining components, namely the state transition matrix X and the GLU component
parameterized identically to Mamba.
The normalization is applied to the output of the model yt after each iteration. While in theory projecting the output onto the unit sphere does not guarantee Lipschitz constant < 1, we observe that practice, this helps with stabilizing the forward and backward pass of the fixed-point RNN framework. We attribute this observation to the fact that achieving > Lipschitz constant requires the output the RNN to become its additive inverse after an iteration, which rarely happens in practice.
C.3 Parameterizing the mixers
We parameterize the channel mixer variants as follows:
Diagonal Plus Low Rank: we define uf, SiLU (Wa, xx WW, (=) and oir
σ ((wx)) T x; + (wx.)T/(=l + ba.). where SiLU(.) and (..) are the SiLU and the sig- moid functions, respectively.
Householder Reflections: we define similar to the diagonal plus low-rank variant.
Kronecker: define D.""" diag (a (WX T X, + W + bb=)) and K mat (SiLU (WX K..Xt + W + bk²)) for n = 2, where diag(.) is the operator transforming a vector into a diagonal matrix, and mat(.) the operator transforming a size d vector into a dd / matrix.
For the diagonal plus low rank and the Householder reflections mixers, we L2 normalize the vectors Un to achieve the unit vector formulation. Note that this does not guarantee contractive diagonal plus low rank structure, which is why the first variant of the channel mixers excluded form our
19

---

FP-RNN experiments. For the Kronecker variant, we define the matrices K; as symmetric and positive semi-defnite using the Cholesky decompositon structure. and normalize them by their largest eigenvalues. The largest eigenvalue is found using the power iterations method, which we found to be much more efficient for small-scale matrices compared to the functions the Py PyTorch framework provided for this purpose.
In all of these parameterization, computing a matrix vector product for each fixed-point iteration can be performed in subquadratic time. Specifically, for the DPLR and the Householder formulation, the computation can be performed in linear time in state-size, size, while in the kronecker product variant, can be performed in vd vd for d state-size.
C.4 Dependence H in theory
We hypothesize that the dependence of the matrices X, b,, C,, and Qr may provide a mechanism for the model retain and manipulate positional information and Trockman et al. (2024) show that position embeddings could play a crucial role in copy tasks by acting similar hashing keys in hashing table. We extend their mechanistic approach understand why two-layers of linear attention could need H generate appropriate position embeddings for the hashing mechanism.
the sequence. Jelassi et al. (2024)
Specifically consider v = c. H, with H, H,-1 + b,x!" assuming that linear RNN with matrix-state can express linear attention by setting X, = Vt. Upon receiving an input sequence [x1,X2... xx} of length 5 followed by a delimiter element Xg, the model is expected to copy the input sequence autoregressively, i.c. to start producing {x1,Xy, Xe...., Xs} at output positions position embeddings as
5 + 1 to 26. Following Arora et al. (2024), the second layer could hashing keys to detect and copy each token. More concretely, if the first layer receives a sequence (x1, (x1,X2,..., X8, Xx, X1, X2.-- (2-11 of size 25 and augments it with shifted position embeddings {p:) to produce the hidden sequence {x++PI P2. P2....
Ps, + X1+ -2......... -6-1-
}.). then a second layer can act as a linear transformer and produce the sequence {x1, X2,.... X.
at output positions 8 + 1 to 28. In the following, we focus the conditions for the first layer to produce the shifted position embeddings.
We start by assuming that the first layer has skip-connection y = ce H, + x In this case, the model can augment the inputs with positional embeddings {p: if it is able to produce shifted encodings P = Ps for < t using P. = =c, H, This condition can be unrolled as
Pi-s cT = o, H tc
Σ r=1-8+1 8+1
b, =
Vg <t
and is satisfied if the equations
1-1
c. - H
and
C
Σ b,x, - - b,X
T=2-8+1
hold. Such conditions could only be true if b, and c, are a function of the previous hidden state H because they need to be able to retain information about 1_-1 While not an explicit mechanism for copying, this derivation provides insight into why dependency H. could be helpful.
20

---

D Evaluation
D.1 Task Descriptions
In this section, we provide task descriptions for the tasks used in the main text.
State Tracking The task of tracking state in the alternating group on five elements (Aş) is one of the tasks introduced in (Merrill et al., 2024) to show that linear RNNs and SSMs cannot solve state-tracking problems. As is the simplest subset of Ss. the word problem involving tracking the permutation of five elements. In these tasks, a model is presented with an initial state and a sequence of permutations. As the output, the model is expected to predict the state that results from applying the permutations to the initial state. Solving these task with an RNN requires either a dense transition matrix or the presence of non-linearity in the recurrence. It is therefore a good proxy verify the state-trace tracking ability of FP-Mamba. In order to investigate the iiloof--iitribution generalization ability of the model, we train the model with smaller train sequence length and evaluate for larger (more than x3) sequence lengths.
Copying We use the copy task (Jelassi et al., 2024) in order to assess the memory capabilities of FP-Mamba. In this task, the model is presented with fixed-size sequence of elements, and expected to copy subsequence of it after receiving special token signaling the start of the copying process. In order to investigate the out-of-distribution generalization ability of the model, we train the models with sequence length < 50, and assess the x2 length generalization following Jelassi et al. (2024) and Trockman et al. (2024).
D.2 Experimental Details
In this section, we will provide our experiment setup for the state tracking, copying, and mod arithmetic tasks. The code is available at (attuub.coom/d--auuuuus/------//
State tracking. We train all models for 5 epochs, with a batch size of 512, 3 different random seeds, learning rate set to 0.0001, weight decay set to 0.01, gradient clipping 1.0, and the AdamW optimizer (Loshchilov & Hutter, 2017). For the train data, we sample 16M datapoints from all the possible permutations for a sequence length of 16, and split the data with a ratio of to 1 for train and validation samples. For the test data, we sample 500k sequences of length 50. We use the implementation and the hyperparameters provided by Merrill et al. (2024) both for data generation and train/test. We train the model for sequence length 16 on the train sample, and evaluate for sequence lengths 2 through 50 on the test sample. Consequently, each epoch of training consists of 25428 iterations, making the total number of iterations during training to be around 1.25M. Note that the likelihood of overlap between the train and test samples is negligible since exhaustive generation of samples in Sy and As at sequence length ie would amount to 60 and 30*, respectively.
Copying. We train all models for 10000 iterations, batch size 128, 3 different random seeds, learning rate 0.00001, weight decay 0.1, gradient clipping 1.0, the AdamW optimizer, and with linear learning rate decay after a 300 iterations warmup. The data is sampled randomly at the start of the training/evaluation.. We use vocab size of 29, context length of 256, and train the model for copy sequence length in the range 5 to 50, and evaluate for the range to 100. we use the implementation and the hyperparameters provided by Jelassi et al. (2024).
Mod arithmetic. Our models are trained for 100000 iterations, batch size 256, learning rate 0.001, weight decay 0.1, and no gradient clipping. The learning rate is decayed using cosine scheduling by a factor of 0.001 after 10000 iterations of warmup. The data randomly sampled at the start of training/evaluation. We use vocab size of 12, with context length 256, and train data sequence length in the range 3 to 40, and the test/evaluation data in the range 40 to 256. We use the implementation and the hy perparameterss provided by Beck et al. (2024) and Grazzi et al. (2024), which are the same hyperparameters used for training and evaluating the baselines.
Language Modeling. For the language modeling task, we use the implmentation provided by Ajroldi (2024). We use batchsize of 16 x 4 x = 256, training on 4 A100-80GB GPUs with 4 accumulation steps, which is the batchsize used in the 2.5B setting in (Gu & Dao, 2024). The
21

---

learning rate is optimized for the Mamba model (0.004) and train all models with this learning rate, with cosine warmup with 0.1 steps. We use the AdamW optimizer with weight decay set 0.1 and 81, 32 set to 0.9, 0.95.
Training Time on As. In order to compare the proposed model the baselines in terms of computation time, we train all of the baselines and our proposed model using the same hardware (A100-80GB gpus) on the As task. We present
results in Fig. 6. Our Fixed-Point Mamba trained at different maximum number of fixed-point iterations: between 2 (green) and 16 (blue), or sampled from the Gamma distribution (4,, 1) with mean (gray).
catbAbI In this experiment, we use the setting provided by Schlag et al. (2021b). We optimize the learning rates on Mamba, and use the same learning rate to train FP-Mamba, which we found to be 5 x 10-1. We use a batch size of 256, along with short convolutions, and 1, 2, or layers. We set the maximum number of iterations max to 100.
D.3 Heuristics reduce the number of fixed-point iterations
Given the importance of scalability in current machine learning research, an implicit network needs be as efficiently designed and implemented as possible. While our theoretical framework improves upon the memory and computational requirements on the backward pass, the forward, and especially finding the fixed-point through fixed-point iterations needs further consideration. In our preliminary experiments, we discover two heuristics that can help with improving this aspect significantly.
The first heuristic relaxing our definition of convergence to the fixed-point during training. We observe that the number of iterations required to find the fixed-point for the sequences in the model usually has power-law distribution, with certain outliers each batch elongating the convergence time. In our experiments, we notice very little difference in the performance of the converged model when we exclude these sequences from our stopping criterion. Consequently, during training, we continue the fixed-point iterations procedure until certain percentage of the datapoints in the batch (usually set to 75%) satisfy our criteria for convergence.
The second heuristic involves using a momentum-like update rule to accelerate the convergence of fixed-point iterations for certain sequences. Specifically, observe that by setting the fixed-point update rule to e++ = 5 fe h²) + (1 - 5) he for some 5 E [0, 1]. we can accelerate the convergence for certain sequences that are particularly slow converge. Since this update rule can result in a biased approximation of the fixed-poing we implement a autience-bassee system that starts with 8 1, and reduces the value of 8 exponentially when the residues fail to improve.
22

---

E
Additional Experimental Results
E.1
Language Modeling
50
Mamba
FP- Mamba-ll (r=
45
PP-Mamba-II (*=2)
FP-Mambe-K
Valid Perplexity
40
35
30
25
0
100
200
300
400
500
600
700
800
Train Iteration
Figure 8: The validation perplexity of the Mamba model vs. FP-Mamba-K and FP-Mamba-R H with E {1,2} reflections. Note that all of the hyperparameters of the models are identical for fair comparison.
In order to confirm the utility of the fixed-point framework in non-state-tracking settings, we per- formed experiment language modeling. Specifically, compare the performance of Mamba with an FP-Mamba, with the same hidden size (768) and number of layers (12). The settings are selected according to the 2.5B setup introduced Gu & Dao (2024). We use train subsample of the Fine Web dataset (Penedo et al., 2024) with 2B tokens, and a validation subsample with 200K tokens. We use context length of 2048 for our experiment. For the FP-Mamba model, we use the Householder mixer with and 2 reflections. We report the validation perplexity in Fig. 8.
As observe, the fixed-point framework does introduce significant improvement to the performance of the model on perplexity. However, we note that this improvement cannot be only attributed to the multi-layer hypothesis of implicit models (Giannou al., 2023), as increasing the number of Householder reflections does seem to be improving the perplexity further. Furthermore, we point out the practicality of the setup, as we can observe in Fig. that the absence of statk-tracking problem, the number of fixed-poin iterations seems to be independent of the sequence length, and instead hover the 10 range. Finally, fixed-point iterations are not required in the backward bass and therefore only increase training time moderately.
E.2 Long-Range State- Slate-Tracking
In this section, we investigate the ability of our proposed method in doing state tracking on longer sequences. Specifically, we will use the A5 and Sş datasets and train on sequence length 128, while evaluating for sequence lengths the range [2, 512]. We also implement the proposed Fixed-Point framework on Mamba2 (Dao & Gu, 2024), and compared al., 2025). In Fig. 9, we plot the test accuracy for these one-layer models.
method to DeltaProduct (Siems
Comparing our results to DeltaProduct, we can see that the non- lineaiiyy introduced by the Fixed- Point dynamics allow for slight improvement in the performance of the Householder products as the mixer components. Furthermore, we observe that the best performing mixer variant is still the Kroneckers model, which can successfully learn the state-tracking problem all runs. Moreover, FP- PP-Mamba2 model demonsterates a better length generalization ability compared to FP-Mambal, which we attribute the improved underlying architecture used in the model. As shown in (Dao Gu, 2024). Mamba2 has better recall capabilities, which can help with length generalization.
23

---

1.0
1.0
2.0
Test Accurmcy
Test Accurayy
0.8
0.4
203
420
200
400
Soquen.co Length
Sequeace Length
(a) State Tracking on As FP-Mamba
(b) State Tracking on Ss FP-Mamba
1.0
1.0
Toss, Arcurayy
Test Accuray
0.7
0.6
203
420
200
400
Sequen.ce Length
Sequence Length
(c) State Tracking on As FP-Mamha2
(d) State Tracking on Ss PP-Mamba2
1.0
1.0
Test. Ancuraccy
Test Accuracy
2.0
0.4
0.4
0.2
3.2
0.0
283
410
200
100
Sequen Length
Sequeace Langth
(c) State Tracking on As DeltaProduct
(f) State Tracking on S, DeltaProduct
Figure 9: The state-tracking experiment for train sequence length 128 and evaluation sequence length [2, 512). We omit the results of DPLR mixer due to poor performance. The figure presents (a, b) the results for FP-Manba with Householder (H) and Kronecker (K) mixer, (c, d) the results for FP-Mamba2 with Householder (H) and Kronecker (K) mixer, and (e, f) the DeltuProduce method (Siems et al., 2025) for Householder mixers.
E.3 Reasoning on CatbAbI
In order to investigate the state-trach taate-tracking ability of the fixed-point framework in a natural language setting, we perform experiments on the catbAbl dataset (Schlag et al., 2021b). catbAbl (concatenated- bAbl) is a reprocessing of the bAbl QA benchmark (Weston et al., 2015), where individual bAbl stories are stitched into one long, continuous sequence, models must keep track of state across story boundaries. The task tries to stress-test the long-range state tracking and associative inference capabilities of sequence models beyond short, isolated contexts. Each sample in this dataset is short story. At the end of each story, the model needs to choose a single word that is the answer to the question corresponding to the story. The responses include yes/no responses and the names of characters or locations in the story. We present the results Table 3.
In order to observe and compare the effect of more complex mixers with the number of layers, we use 2, and layers along with the Kronecker and Householder mixer with r E 2,,2,3) 3) reflections. Our investigation shows that increasing the number of layers seems to be reaching the point of diminishing returns very fast, while the fixed-point framework improves the performance. This observation seems to be in line with the findings of Saunshi et al. (2025), where the looped architecture seems to be providing a very helpful inductive bias for solving reasoning tasks. Comparing the performance of mixers, observe that the Kronecker mixer under-performs compared to the Houscholder
24

---

Layers
Mamba
FP-Mamba-K
FP-Mamba-H
FP-Mamba-Hl
FP-Mamba-II
(r L)
(r 2)
(r = 3)
Layer
78.28%
79.93%
81.32% 89.08%
81.60%
80.79%
Layers
87.08%
84.16%
87.47%
89.55%
Layers 86.51%
Table 3: Test accuracy of the Mamba model vs. the FP-Mamba model for the Kronecker (K) and the Householder (II) channel mixers with E (1,2,3, 3) on the catbAbl dataset. We increase the number of layers to show the effect of having more layers all models. The task benefits from the fixed-point dynamic, but increasing the number of layers seems be suffering from diminishing returns.
mixer, which we believe is in line with our observation in App. E.I, where the Kronecker mixer underperforms on tasks involving natural languages.
E.4 Modular Arithmetic Task Results
Following Grazzi et al. (2024), we also evaluate FP-Mamba on the remaining unsolved task of the Chomsky Hierarchy of language problems introduced by Beck et al. (2024), Specifically, on the mod arithmetic task with brackets. Following the setup of Grazzi et al. (2024), we train on sequence lengths 40 and report scaled accuracies test sequences of lengths 40 to 256. For FP-Mamba, we use a 2-layer model with r = reflections, i.e. the best performing model in the As experiment.
focus
In Tab. 4, we observe that a 2-layer FP-Mamba-H outperforms the baselines reported in (Grazzi et al., 2024) with comparable number of parameters. In Fig. 10, we plot the validation accuracy as a function of the number of fixed-point iterations. We observe that the accuracy plateaus at 20 iterations, which is significantly less than the shortest and longest sequence in the validation set. Therefore, the number of iterations required by FP-Mamba-H reach its fixed point clearly does not scale with the sequence length in this task.
Model
Accuracy
2L Transformer
0,025
Validation Accumeyy
2:30
2L mLSTM
0.034
2L sLSTM
0.173
21. Mamba
0.136
4.24
2L DeltaNet
0.200
2L GatedDeltaProduct
0.342
3.22
2L FP-Mamba (r 4)
0.384
Nerations
Table The accuracy of various models on modu- lar arithmetic with brackets. We adopt the reported numbers in (Grazzi et al., 2024) evaluating base- lines the extended [- -1, eigenvalue range. Scores are commonly used scaled accuracies between and 0.0 (random guessing). Highlighted is the best performance in each category.
Figure 10: Number of fixed-point iterations on the modular arithmetic task at test time. We report the validation accuracy after convergence for the number fixed-point iserations caped various values ranging from to 512. The pink dashed line denotes the maximum sequence length during validation.
25

---

E.5
Effect of max on test performance and number of iterations l
Max Btere
10
12
14
16
Max Sters
10
12
14
16
Accuracy
2-4
5.0
20
50
10
20
5n
Length
Seguence Length
(a) Effect of leux
(b) Number Iterations E
Figure 11: The effect Emai the performance of the model ((a)), and the number of iterations E" ((b)) on the As task. The vertical line denotes the train sequence length. All the experiments are performed on FP-Mambal with a Householder mixer with r reflections. Results are averaged across runs.
In Fig. 11 present the effect of the maximum number of iterations fmax during training the accuracy and the number of iterations & during inference. As we observe, the general trend that increasing max improves the performance of the model. We attribute this observation to how well the model learns the task, as following Thm. 3.2, a condition for the gradients being a descent direction for them be computed or close the fixed-point. Consequently, we can that when trained with a smaller number of iterations (small (mxx), the model fails to fully utilize the fixed-point by adapting e* to the difficulty of the task.
E.6 Sequential vs Parallel Fixed-Poine Iteration
An important detail about the fixed-point framework proposed in this paper is that it is not convex. Therefore, the fixed-point is not necessarily unique, which be problematic in autoregressive applications because there are no guarantee that the parallel fixed-point during training will be the same as the sequential eked-point used during inference (Schöne et al., 2025). In order to investigate this issue, we trained an FP-Mamba-H model on the As task and compared the fixed-point computed sequentially and in parallel. We report the results in Fig. 12. We observe that the fixed-points extremely similar, providing the possiblity of computing the fixed-point sequentially during inference.
0.10
0.08
0.06
Test
[b:
Train
0.04
FP Thr.
0.02
0.00
10
20
30
40
Sequence Length
The difference between the fixed-point computed sequentially (i.e., computing the fixed-point for each token separotely) and the fixed-point computed in parallel (t.e, computed through E4. 12) on the As task trained on sequence length 16 to convergence. The x-axis denotes the test sequence length, and the y-axis the normalized difference. The dashed gray line denotes the threshold for stopping the fixed fixed-point iterations.
Figure 12:
26

---

F Low-Rank Expressiveness
In this section, we prove that SSMs with low-rank structure can be maximally expressive under weak assumptions on the growth of the rank with hidden dimension. To do this we first place ourselves in the general setting of (Cirone al., 2024b), accordingly we consider models given by controlled differential equations of type":
du
dY, = Σ A'Y,dw',
Yo E Rdy
(19)
Following the notation and methodology of Cirone al. (2024b)(B.4)) ) this can be written in terms of the Signature as
Y ((A"),, W). := = Σ
(A'Y) St (W))
(20)
JEW
where Wa, is the set of words the alphabet [[d]]] == (l,...,dd d (i.e. Wa Unzol[d=[]* and
for given word I = i ....fe in with St (w)(o.1) we refer to the Ith component of the signature tensor (w)) ie.
('() =
dw ... dw.
111 KE C.n [1E
It follows directly from Eq. 20 that any linear readout of can be represented series in signature terms. As result, these systems are fundamentally restricted to learning functions that closely approximate these convergent series.
Maximal expressivity is attained when any finite linear combination of signature terms can be approximated linear readout Y, via suitable configurations of the matrices A
Definition F.1. Fix set of paths X' C Cl 1]; 1d). We say that sequence (AA, VN N where VN C IR N and AN C N achieves maximal expressivity for whenever for any positive T(R") there exist a choice of parameters v, (A*), Yo in some IRN, AN, YN in the sequence such that v Y((*),, Yo, Yo, is uniformly close to (a,S(w) (w)) up to an error e i.e.
tolerance 0 and any finite linear combination coefficients
Vc 0, Va T(RR), EN 0. [(c, (A)), E x A x VN
sup (a, ((w) v Yo,))) (u.1)ex'xx [0.1]
we are given a sequence of probabilities NN on A x Vvv such that Ve > 0, Va T(Rd) it holds that
lim PN Eu E R-- s.t. sup (x
Na, S(w) v Fo
(21)
N-000
then we say that (AN VN. PNN)NE achieves maximal probabilistic expressivity for X.
As discussed in the main body of this work in (Cirone al., 2024b) the authors prove that N R NN),, where P. is a Gaussian measure corresponding to the classical Glorot initializa- tion scheme in deep learning, achieves maximal probabilistic expressivity for compact sets.
Albeit expressiveness is thus maximally attained the resulting matrices A, are almost-surely dense, hence the models are not efficiently implementable. As the next result suggests, possible alternative given by low-rank matrices:
Proposition F.2. The sequence of triplets NxN R PN) where Py is such that
For simplicity we have omitted the df term, as the results and proof change minimally in form but not in spirit.
27

---

the initial value has independent standard Gaussian entries (Yola sid N( 1).
the weight matrices are distributed as A idd
WM with W and M independent
VNTK
x UN matrices having entries [W]a,9, [M]
sid
(N,,1).
the rank parameter nN satisfies TN - 00
achieves maximal probabilistic expressivity for compact sets.
Proof. Following (Cirone et al., [B.35)(B.3.5] we only need to prove bound of type
1 N
(A, A,Yo)aN
81
S (x(II+)1)))!! o(1)
(22)
13(BN)
as in the full-rank Gaussian case.
We will place ourselves in the graphical setting of (Cirone al., 2024a) and leverage the fact that (c.f. (Cirone et al., 20.11)[7.1]) their results and techniques naturally hold for rectangular matrices.
In setting + (Ay Yo, Ao))) corresponds to product graph GI,J corresponding to ladder having || edges as shown in Fig. 13. We can then use (Cirone et al., 202op)[Prop. 2] to compute the square of the L norm in equation Eq. 22, the only difference from the dense case is that half of the vertices (excluding the "middle" one) correspond to a space of dimension IN while the rest to the standard N.
1++ the admissible pairings of Gr.J of order (11) are only the leading ones. These correspond to product graphs with |M++ r--dimensionnl 2
Since TN + and given the scaling ~~
vertices and ||+ + N-dimensional vertices. By the same reasoning as the full-rank case, these are found to be just the identity pairings.
Moreover, all pairings of Gr,J L. Gr.J that do not result in identity pairing in least of the two copies are O NArx) iinttead of O( ). This follows in the full-rank case.
Since the total number of admissible pairings of Gr,J L Gr,r is (4(14))1))) conclude that equation 22 holds with 4 and o(1) == O VNArN
N (AYo, A,oo) = N (N+1)
Figure 13:
The product graph GI,J for I i122ts and J j1-
Remark F.3. Following (Cirone et al., 2024a)[6.1] 1] it's possible to prove that the W and M can be taken having iid entries from centred, symmetric but heavy tailed distribution given finiteness of even moments. This distributional choice comes useful in controlling the eigenvalues of = W T Remark F.4. While the proof crucially uses the assumption I'N + as N + at the same time we have not provided an argument against I'y not diverging. In Fig. 14 we present counterexample, showing that if IN does not diverge then the asymptotics differ from the dense ones, in particular some symmetries are "lost", impossible to recover due unavoidable noise.
28

---

Figure 14: Admissible pairing different from the "identity" paring, but still leading maximal
asymptotic scaling in the bounded rN case. Here, / = 12 1112 = J, and we have highlighted in blue the vertices corresponding correspond to the matrix (matrix of ones), and that two edges corresponding to matrices A and B which share direction and terminal vertices can be merged into the edge A @ B.
the bounded dimension rv. Recall that edges without arrows
29

---

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: In the paper make claims about the proposed method increasing the expressivity of the model, for which we provide experimental and theoretical justification.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, discuss the limitations in the discussion section of the paper.
Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
Yes, we provide the set of assumptions in the description of the theories, and the correct proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, we provide the experimental setups in the paper. full experimental setup description can be found in the appendix.
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary 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 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 appropriate to the research performed.
While NeurlPS 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
31

---

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: [Yes]
Justification: All of the datasets used in our paper open access. We intend to provide the code for our paper after publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips...
(oglic/guides/Coeeeee wwwpibiiissioooooioiiioooo onPolicy icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /náps. wwtppccccc/a/ccccccccccccccccllt weaiic/ggue//eeeee /aleeee/oooSmmmi cemmiissionPPP ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended 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: Yes, all of the details are available in the appendix, and the corresponding papers are cited.
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: [Yes]
Justification: All of the experiments either provide error bars, or the setting is specifically mentioned in the text and justified using cited material.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we provide the details of the hardware used in the experiments in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics attps://mne /tttu:://neurips... cc Spppblic/Ethissuuiiii
Answer:
[Yes]
Justification:
We believe work conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As our paper is mostly concerned with expressivity of RNNs and theoretical and empirical justifications for believe this issue does not apply to our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
33

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: As our paper is mostly concerned with expressivity of RNNs and theoretical and empirical justifications for believe this issue does not apply our work.
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.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, we cite the papers providing or proposing the datasets and models used in our experiments in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
34

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdattasess 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowd sourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to 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
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Our paper does not involve crow sourcing or working with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

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:
We do not use LLMMs this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: pettpa//neeuee httpe:///neuuuueeeeeeeeeeee ccCConneeeeeeeeee/222225 for what should or should not be described.
36


Reviews:
[{"review_id": "xqZ4ePp8un", "reviewer": "Reviewer_TEck", "summary": "The paper introduces Fixed-Point RNNs (FP-RNNs), a novel framework that models dense linear recurrent neural networks as the fixed points of diagonal RNNs. This approach enables a continuous trade-off between computational efficiency and expressivity by varying the number of fixed-point iterations, effectively interpolating from parallelizable diagonal structures to expressive dense ones. The method ensures stability through careful parameterization and uses structured mixers (e.g., Kronecker products, Householder reflections) to enable efficient and scalable computation.\n\nThe authors instantiate this framework in FP-Mamba, an extension of the Mamba selective state-space model, demonstrating state-of-the-art performance on tasks that require memory and state-tracking, such as the copy task and sequence length generalization benchmarks (A5/S5). Notably, FP-Mamba adapts the depth of computation dynamically based on task complexity and outperforms traditional RNNs and SSMs in expressivity, while maintaining better parallelism than classical RNNs. The work opens a path toward more expressive and efficient sequence models that unify the strengths of recurrent and state-space architectures.", "questions": "1. In practice, are there times or examples where convergence of the FP-RNN would be very slow? Any intuition about when or why?\n2. How should one select one of the mixer structures in practice?\n3. Could you provide concrete cost measurements (FLOPs, memory) comparing FP-RNNs to existing models?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well written and easy to follow. The intro and background were especially clear.\n- The fixed-point RNN framework is an elegant way to flexibly interpolate between diagonal and dense RNNs, enabling adaptive computation.\n- The paper carefully parameterizes the RNN in order to ensure stable dynamics.\n\nWeaknesses:\n- Limited empirical scope: the experiments focus on synthetic benchmarks, with little evaluation on real-world tasks.\n- A quantitative comparison table of compute time, memory usage, and iteration cost vs baselines would make the trade-offs more transparent.\n- The paper lacks practical intuition or heuristics for choosing the number of fixed point iterations", "was_revised": true, "final_justification": "The authors addressed my main concerns, showing performance on additional tasks and discussing compute time trade-offs in the main text. I have updated my score accordingly.", "rebuttal": "We thank the reviewer for their valuable feedback and we appreciate their assessment of our paper as **well written** and **easy to follow**, describing a **novel, elegant method** that **opens a path** towards improved sequence models. We address their suggestions as follows:\n\n**1. Make compute trade-offs more transparent.**\n\nWe agree that the main submission provided insufficient guidance on the compute trade-offs of our FP-RNN approach  when restricting the number of iterations. Therefore, we had already included plot to relate compute time to generalisation on the state-tracking task $A\\_5$ in Appendix E.4, Figure 11 and now provide an analysis here:\n\n*”Wall clock time is plotted against the longest test sequence length with > 90% accuracy for every model. While baselines of increasing depth $\\\\in \\\\{1, 2, 4, 6, 8\\\\}$ cannot generalize beyond the training sequence length 16 (horizontal pink line), our proposed framework allows to **achieve much higher generalization by scaling training time** through the number of fixed-point iterations $\\\\ell\\_\\\\text{max} \\\\in \\\\{2, 4, 8, 16\\\\}$. There is **further room to improve efficiency**, as suggested by a simple randomization scheme (gray stars) where $\\\\ell\\_{\\\\text{max}} \\\\sim\\\\Gamma(4,1)$ is sampled from a Gamma distribution with mean $4$ for every batch.”*\n\nWe will include the above analysis in Sec 4.5 and move Figure 11 to the main text (replacing Figure 7). Thank you for this excellent suggestion which makes the paper stronger! \n\n\n**2. More evaluations on real-world benchmarks.** \n\nThank you for sharing this perspective! It’s true that the main goal of the paper is to introduce a framework which solves the theoretically motivated state-tracking task and we therefore focus on this aspect in the evaluation. Nevertheless, we evaluate a small ~160M FP-Mamba language model trained on 2B tokens of Fine-Web (Penedo et al, 2024) in Appendix E.1. In addition, we now provide **new results of FP-Mamba on the reasoning benchmark CatbAbi**  (Schlag et al, 2021):\n\n| Accuracy | Mamba | FP-Mamba (K) | FP-Mamba (H1) | FP-Mamba (H2) | FP-Mamba (H3) |\n| --------      | -------     | -------   | -------   | -------   | -------   |  \n| 1 Layer    | 78.28 %  | 79.93 % | 81.32 % | 81.60 % | 80.79 % |\n| 2 Layers  | 87.08 %  | 84.16 % | 89.08 % | 87.47 % | 89.55 % |\n| 4 Layers  | 86.51 %  | - | - | - | - |\n\nIn this experiment, we report the test accuracy, using the settings of (Schlag et al, 2021). We optimize the learning rates on Mamba, and use the same learning rate to train FP-Mamba. The vanilla Mamba model hits the diminishing returns point with more layers, while our proposed dense variant further improves the accuracy with more dense layers. Furthermore, we can see that in this case, the Householder mixer performs better than the Kronecker mixer, indicating that the Householder mixer is more suitable for text data. We observed a similar pattern in language modeling, where FPMamba achieves a perplexity of 26.00 with the Kronecker mixer on the test set, while with a single Householder component it achieves the perplexity of 25.24. The vanilla Mamba achieves a perplexity of 27.01 in this case. \n\nWe agree with the reviewer that these initial results on real-world tasks are indeed an important signal to the community and we will thus place them more prominently in the paper. We believe that **our old language and new reasoning results point into a promising direction** and we would like to include more benchmarks in the camera-ready version if the reviewer has some concrete suggestions. However, we believe that a thorough, large-scale study to investigate which application domains benefit from our verified state-tracking capabilities is beyond the scope of this work.\n\n**3. Provide intuition/heuristics for choosing the number of fixed-point iterations.** \n\nAs described in L222 and L298, the fixed-iteration stops once the relative distance between iterates falls below a threshold of 0.1, so **the number of fixed-point iterations is chosen by the model itself and not the user**. In order to avoid excessive computation on outlier samples during training, we usually set the maximum number of iterations $\\\\ell\\_{max}$ to the sequence length $T$ and apply other heuristics as described in Appendix B.4.\n\n\n**Questions:**\n\n1. *Are there examples where the convergence of the FP-RNN is very slow?* We observe different convergence speeds depending on the application. For example state-tracking tasks are very hard to solve, whereas language modelling is easier and converges usually in a few iterations as depicted in Figure 6.\n\n2. *How should the mixer structure be selected in practice?* We suggest empirically evaluating the best performing mixer structure depending on the specific application. In the meantime, we have ablated the mixers on all tasks and conclude that the Kronecker structure seems to be a good default for state tracking, and the Householder structure more suitable for language and copying. However, we encourage the community to investigate more channel mixer structures under the FP-RNN framework.\n\n3. *Could you provide concrete cost measurements comparing FP-RNNs to existing models?* As discussed before, we compare the runtime of FP-RNN to existing models in Appendix E.4, Figure 11 and will move this discussion into the main text.\n\nWe hope that our response addresses the reviewer’s concerns and would be interested to hear if they are considering raising their score to help increase the visibility of our work during the conference. In case there are any remaining questions, we are of course happy to resolve them during the discussion period.\n\n\n\n---\n\nPenedo et al. (2024), *\"The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale\"*, https://arxiv.org/abs/2406.17557\n\nSchlag et al. (2021), *\"Learning associative inference using fast weight memory.\"*, https://arxiv.org/abs/2011.07831"}, {"review_id": "t9t2RgJ2Pr", "reviewer": "Reviewer_DU4S", "summary": "The authors propose a new parameterization for (implicit) dense linear RNNs as fixed-points of diagonal linear RNNs. The resulting sequence mixer shows superior expressivity which is shown both theoretically and empirically on state tracking tasks. The authors clearly explain how their proposed model allows for a tunable trade-off between expressivity and efficiency (i.e., parallelizablity) by varying the number of iterations. Their experiments show interesting results on adaptive computation that are well-aligned with their theory. Their model performs well on synthetic toy tasks as well as a small language modeling experiment.", "questions": "Could you elaborate on how, once the recurrence depends on the hidden state (as in Section 3.4), the theoretical guarantee of a unique fixed point from Theorem 3.1 remains? Since this state-dependence breaks the uniform contraction assumption of Theorem 3.1 and can admit multiple solutions $h^*$, under what additional conditions (if any) could you still prove convergence—-or at least uniqueness—-of the fixed-point iteration in this richer setting? My current understanding is that the empirical iteration condition is not guaranteed to hold and the system may iterate forever. It would be interesting to know under what conditions this might happen, so I would be curious if you have any results or ideas on this. \n\nCan you explain why the language modeling experiments in Appendix E.1 use the Householder mixer, while the experiments in the main paper showed the Kronecker to be most performant? Is there any guidance on which structure performs best on different tasks?", "limitations": "See comment about the authors' claims of state-of-the-art result.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- theoretically grounded, novel, and clean method for smoothly interpolating between diagonal linear RNNs and dense RNNs. Their approach cleanly separates time-recurrence (diagonal gate) from channel mixing, simplifying analysis and gradient flow. Shows how a single RNN step can be \"deepened\" via fixed-point iteration without stacking layers.\n- Demonstrates competitive or improved accuracy on synthetic copying tasks, and shows some results on language modeling as well. \n- very well-written paper with didactic explanations, it was a pleasure to read.\n- clearly points to new research directions in the field and opens new opportunities.\n\n**Weaknesses**\n- Time complexity might be $O(T^2)$ which would be worse than nonlinear RNNs, and the analysis in the paper is not convincing that this is *not* the case. Indeed, Figure 3c leads me to believe that the number of iterations indeed does scale with sequence length, leading to quadratic complexity.\n- Not clear how well the interpolation works when restricting the number of fixed point iterations - Figure 1 is the only result shown in the paper but I would be curious about the comparison to other linear sequence mixers. Does the proposed FP-RNN with maximum one iteration perform as well as Mamba? Little guidance on these trade-offs is offered in the paper.\n- Limited ablations: there is no detailed study of how iteration count, tolerance, or mixer depth affect performance.\n- Limited results on real-world benchmarks like language modeling (only compared to Mamba-1, not other models). It seems that their proposed FP-RNN outperforms Mamba-1 on language modeling but scalability to real world problems is not demonstrated very convincingly.\n- The claim of state-of-the-art performance in the abstract is not clearly backed up in the main text. It is advisable for the authors to clarify their exact new state-of-the-art results in the results section in more detail, and to qualify their claim in the abstract.\n\nMinor:\n- repeated sentence lines 42-43 and 44-45\n- footnote 1 grammar: \"allows to increasing\" \n- first introduction of the name FPMamba is a bit unexpected, might be better for the reader if it's introduced directly in the abstract and introduction as a contribution of the paper\n- reference needs brackets in line 134\n- broken sentence in line 140-141, 156\n- the task descriptions is not referenced in the main text (appendix D)\n- figure 7 is not referenced in the text", "was_revised": true, "final_justification": "The authors addressed all my concerns and incorporated all suggestions.", "rebuttal": "We thank the reviewer for their positive and detailed feedback and we’re glad that they found our paper **a pleasure to read**, describing a **theoretically grounded, novel, and clean method** that **clearly points to new research directions**. We address their suggestions as follows:\n\n**1. Make compute trade-offs more transparent.**\n\nWe agree that the main submission provided insufficient guidance on the compute trade-offs of our FP-RNN approach when restricting the number of iterations. Therefore, we had already included plot to relate compute time to generalisation on the state-tracking task $A\\_5$ in Appendix E.4, Figure 11 and now provide an analysis here:\n\n*”Wall clock time is plotted against the longest test sequence length with > 90% accuracy for every model. While baselines of increasing depth $\\\\in \\\\{1, 2, 4, 6, 8\\\\}$ cannot generalize beyond the training sequence length 16 (horizontal pink line), our proposed framework allows to **achieve much higher generalization by scaling training time** through the number of fixed-point iterations $\\\\ell\\_\\\\text{max} \\\\in \\\\{2, 4, 8, 16\\\\}$. There is **further room to improve efficiency**, as suggested by a simple randomization scheme (gray stars) where $\\\\ell\\_{\\\\text{max}} \\\\sim\\\\Gamma(4,1)$ is sampled from a Gamma distribution with mean $4$ for every batch.”*\n\nWe will include the above analysis in Sec 4.5 and move Figure 11 to the main text (replacing Figure 7). Thank you for this excellent suggestion which makes the paper stronger! \n\n\n**2. More evaluations on real-world benchmarks.** \n\nThank you for sharing this perspective! It’s true that the main goal of the paper is to introduce a framework which solves the theoretically motivated state-tracking task and we therefore focus on this aspect in the evaluation. Nevertheless, we evaluate a small ~160M FP-Mamba language model trained on 2B tokens of Fine-Web (Penedo et al, 2024) in Appendix E.1. In addition, we now provide **new results of FP-Mamba on the reasoning benchmark CatbAbi** (Schlag et al, 2021):\n\n| Accuracy | Mamba | FP-Mamba (K) | FP-Mamba (H1) | FP-Mamba (H2) | FP-Mamba (H3) |\n| --------      | -------     | -------   | -------   | -------   | -------   |  \n| 1 Layer    | 78.28 %  | 79.93 % | 81.32 % | 81.60 % | 80.79 % |\n| 2 Layers  | 87.08 %  | 84.16 % | 89.08 % | 87.47 % | 89.55 % |\n| 4 Layers  | 86.51 %  | - % | - % | - % | - % |\n\nIn this experiment, we report the test accuracy, using the settings of (Schlag et al, 2021). We optimize the learning rates on Mamba, and use the same learning rate to train FP-Mamba. The vanilla Mamba model hits at the diminishing returns point with more layers, while our proposed dense variant further improves the accuracy with more dense layers. Furthermore, we can see that in this case, the Householder mixer performs better than the Kronecker mixer, indicating that the Householder mixer is more suitable for text data. We observed a similar pattern in language modeling, where FPMamba achieves a perplexity of 26.00 with the Kronecker mixer on the test set, while with a single Householder component it achieves the perplexity of 25.24. The vanilla Mamba achieves a perplexity of 27.01 in this case. \n\nWe agree with the reviewer that these initial results on real-world tasks are indeed an important signal to the community and we will thus place them more prominently in the paper. We believe that **our old language and new reasoning results point into a promising direction** and we would like to include more benchmarks in the camera-ready version if the reviewer has some concrete suggestions. However, we believe that a thorough, large-scale study to investigate which application domains benefit from our verified state-tracking capabilities is beyond the scope of this work.\n\n**3. Further discuss required number of iterations.**\n\nYes, we do observe a complexity of $O(T^2)$ on state-tracking in Figure 3c. However, as we discuss in L365-365, we believe that *“this is not necessarily a disadvantage if the model is capable of adapting its sequential steps to the difficulty of the task, with negligible cost for the least demanding tasks*”. Indeed, on copying (Figure 5b), language modelling (Figure 6), and modular arithmetic (Figure 10) we observe the required number of fixed-point iterations $\\ell^*$ is well below the sequence length $T$ suggesting that **the model adapts to $O(T)$ complexity on simpler tasks**. Finally, a new theoretical study suggests that logarithmic depth might be both necessary and sufficient to achieve state tracking from an expressivity perspective (Merrill et al 2025). In future work, we will investigate how the number of fixed-point iterations could be reduced to this theoretical lower bound in practice. We will make sure to discuss this better in Sec. 4.5 of the paper, thank you for raising this concern!\n\n\n**4. Ablate iteration count, tolerance, and mixer depth.**\nThank you for the suggestion. We first note that the iteration count is not controllable by us, since it is the model that determines when it reaches the fixed-point. So we assume you are referring to the maximum number of fixed-point iterations. We agree these ablation studies are valuable, and **the results in Figure 1 provide a preliminary analysis of these parameters**. Our work ultimately focuses on ablating core architectural components, such as the choice of mixer, as we view iteration count and tolerance as solver-specific hyperparameters. But we are happy to expand on these initial findings with a more detailed study for the camera-ready version if needed.\n\nRegarding the mixer-depth choice, we would like to kindly ask you to further elaborate on what you are exactly interested in. In case your question is with regards to the number of Householder (H) components, **we have investigate the effect of more Householder components in the paper (up to 4)**.\n\n**5. Highlight state-of-the-art results in the paper.**\nThank you for your attention to detail. **Our claim on state-of-the-art results in the paper specifically refer to the A5/S5 task**, for which we believe our reported result for figure 5-a and 5-b - achieving near perfect $>\\\\times 3$ length generalization - is the best performance reported for these tasks for training in sequence length 16. Furthermore, using the setting proposed for the DeltaProduct method (Siems et al, 2025) for training in sequence length 128, we achieve better $\\\\times 4$ length generalization than their proposed method on both the $A\\_5$ and $S\\_5$ tasks (average of 3 separate runs), the result of which are available in the following table:\n| Accuracy | GatedDeltaProduct (H4) | FP-Mamba1 (K) | FP-Mamba1 (H4) | FP-Mamba2 (K) | FP-Mamba2 (H) |\n| --------      | -------     | -------   | -------   | -------  | -------   |  \n| A5    | 23.90 %  | 99.55 % | 87.68 % | 98.21 % | 88.19 % |\n| S5  | 45.42 %  | 90.75 % | 86.37 % | 92.82 % | 92.20 % |\n\nWe will make the distinction in the abstract of the paper about this point. \n\n**Questions:**\n\n1. *What are theoretical guarantees once the recurrence depends on the hidden state?* While we did not establish a formal proof, we’re happy to share some ideas on how to prove convergence in this richer setting. To start, we agree that a state-dependent iteration can admit multiple solutions. However, note that in the time dimension, sequence mixing occurs only uni-directionally. This allows for an inductive argument in both dimensions: Since $Q\\_0^{\\\\ell}$ is contractive, depends only on the input and no (varying) hidden state, the iteration in depth on the first time step $h\\_0^{\\\\ell}$ converges (similar to Thm 3.1). Once $h\\_0^{\\\\ell}$ converged and does not change anymore, $Q\\_1^{\\\\ell}$ will not change anymore and allow for $h\\_1^{\\\\ell}$ to converge. This way, the iterations $h\\_t^{\\\\ell}$ converge sequentially in time and the system cannot iterate forever. \n\n2. *Is there any guidance on which structure performs best on different tasks?* Since the submission, we have ablated the mixers on all tasks and conclude that the Kronecker structure seems to be a good default. The language experiment, however, is the only one where Householder mixers perform slightly better than Kronecker mixers. We will add these new results to the camera-ready version of the paper.\n\n\nWe thank the reviewer for the list of minor issues which we will fix in the camera ready version. We hope that our response addresses the reviewer’s concerns and would be interested to hear if they are considering raising their score to help increase the visibility of our work during the conference. In case there are any remaining questions, we are of course happy to resolve them during the discussion period.\n\n\n\n\n---\n\nPenedo et al. (2024), *\"The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scale\"*, https://arxiv.org/abs/2406.17557\n\nSchlag et al. (2021), *\"Learning associative inference using fast weight memory.\"*, https://arxiv.org/abs/2011.07831\n\nMerrill et al. (2025), \"A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers.\", https://arxiv.org/abs/2503.03961\n\nSiems et al. (2025), \"Deltaproduct: Improving state-tracking in linear rnns via Householder products.\" https://arxiv.org/abs/2502.10297"}, {"review_id": "KtsvYyb7Vr", "reviewer": "Reviewer_i3G4", "summary": "The paper aims to bridge the gap between matrix-diagonal and matrix-dense linear RNNs by striking a balance between expressivity (which favors denser matrices) and parallelizability (a strength of diagonal RNNs that process sequences in sublinear time wrt sequence length). This is acheived by rewriting the output of dense RNN recurrance as the solution to a fix point problem, which mirrors a digagonal RNN recurrence. \n\nTherefore, to compute the output of a dense layer under this approach, the hidden states are guessed (set to zero I believe) at first iteration, and then unrolled under the diagonal recurrence to get the next iteration (iter wrt fix point problem solver). This happens $ l^* $ times, which leaves us with time complexity of $\\mathcal{O}(l^* \\log(T))$, where $T$ is the sequence length. \n\nNote that $l^* << T$, meaning that their approach is still much faster than vanilla RNNs. In the experiments, the authors empirically show superior performance, mainly in tasks where RNNs/LSTMs would excel over more modern models such as Mamba and Transformers.", "questions": "* Did the authors see any sort of instability during training? \n\n* Is there a potential trade-off between the number of parameters and the required number of fixed-point iterations, i.e. $l^*$? The paper would be a lot more impactful if you show that smaller models can also trade memory, i.e. parameters, for FLOPs. \n\n* Is there a way to reduce the numebr of fix-point interations? For example by warmstarting from the hidden states of the previous layer?", "limitations": "yes, see above as well", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strenghts: \n\n* The idea to generate dense RNN unrolls as fix point iterations of diagonal RNNs is novel to best of my knowledge and an idea that would benefit the research community. \n* Their method is applicable to already existing SSMs and would unlock a plethora of models.\n* The unrolls are very efficient. Training is also remains unaffacted of the fix point finding problem, i.e. no need to backpropagate through fix point iterations. \n* The method is applied to Mamba in particular which makes the study more relavant. FP-Mamba consitently outperforms Mamab. Moreover, the authors report improved perplexity in a languge modeling task. \n* They show harder tasks require more fix point iterations which proves the effectiveness of their method. \n* The writing, theorems and equations are easy to follow, even though the method is somewhat complex. \n\nWeaknesses: \n\n* I would have appreciated a discussion regarding the effect of hidden state size in Mamba and State-Space Models (SSMs) and its relationship to expressivity. According to Koopman theory, SSMs can perfectly capture arbitrarily complex state-to-state transitions, \"dynamical systems\", as the state size ($d$) approaches infinity. What, then, justifies the necessity of this new approach over simply increasing $d$? Furthermore, would a larger standard Mamba model, operating under the same FLOPs, be able to outperform FP-Mamba?\n\n* The paper would generally benefit from a more thorough benchmarking analysis of FLOPs, particularly as task complexity increases. Specifically, I would be interested in seeing how $l^∗$ scales when dealing with progressively more challenging tasks.\n\n* The method's inability to fully capture dense RNNs, attributed to the introduction of the normalization factor $(I - \\Lambda)$, warrants further discussion. Specifically, I would have liked an explanation of the precise effect this normalization has on the class of dense matrices that remain representable.\n\n* A few minor writing errors that I was able to catch: \n> - Figure 3 caption say (6) and (6). \n> - I believe $h_t$ in Equation (5) should be revised to simply $h$. \n> - App. C.2 under subsection 4.3 needs to be revised to C.4? \n> - \"DLPR\" at the top of page 9, whould be revised to \"DPLR.\"", "was_revised": true, "final_justification": "The contributions of the paper are novel and useful for the community, from both academic and industrial stand points. I maintained my initial rating of 5 after the discussion period.", "rebuttal": "We thank the reviewer for their positive and detailed feedback and we’re glad that they found our paper **easy to follow**, describing a **novel idea that would benefit the research community** and could **unlock a plethora of models**. We address their suggestions as follows:\n\n\n**1. Reconcile results with Koopman theory.**\n\nThank you for asking for clarification on this important point! Indeed, according to Koopman theory any nonlinear dynamical system can be approximated by an SSM with a large enough hidden state $d$ — as long as it is followed by an MLP tasked with computing eigenfunctions. It is important to note, however, that the form of the Koopman operator depends on the nature of the dynamical system. In the case of a scalar-valued dynamical system the state-to-state transition acts as an element-wise linear operator (like Mamba). But **the Koopman operator of a vector-valued dynamical system is generally a dense object**.  It can be diagonalized into an element-wise operator only if there exists an eigenbasis which decouples the vector-valued dynamical system. This is where the expressivity results due to Merrill et al (2024) and Cirone et al (2024) come in: **certain problems such as state-tracking cannot be expressed by a decoupled dynamical system**. In the case of state-tracking, it is easy to see that the time-varying permutation matrices which represent the linear operator cannot be co-diagonalized. We will try to make this clearer in the introduction section, and point to the Discussion in Cirone et al (2024), who directly addressed this issue mathematically in their section 4.3.\n\nSince Mamba can express progressively more coupled dynamical systems with depth, we empirically investigated scaling it’s the depth (instead of width $d$) to operate under the same runtime as FP-Mamba. We hope that answer we gave to the other reviewers addresses your question:\n\n**2. Make compute trade-offs more transparent.**\n\nWe agree that the main submission provided insufficient guidance on the compute trade-offs of our FP-RNN approach when restricting the number of iterations. Therefore, we had already included plot to relate compute time to generalisation on the state-tracking task $A\\_5$ in Appendix E.4, Figure 11 and now provide an analysis here:\n\n*”Wall clock time is plotted against the longest test sequence length with > 90% accuracy for every model. While baselines of increasing depth $\\\\in \\\\{1, 2, 4, 6, 8\\\\}$ cannot generalize beyond the training sequence length 16 (horizontal pink line), our proposed framework allows to **achieve much higher generalization by scaling training time** through the number of fixed-point iterations $\\\\ell\\_\\\\text{max} \\\\in \\\\{2, 4, 8, 16\\\\}$. There is **further room to improve efficiency**, as suggested by a simple randomization scheme (gray stars) where $\\\\ell\\_{\\\\text{max}} \\\\sim\\\\Gamma(4,1)$ is sampled from a Gamma distribution with mean $4$ for every batch.”*\n\nWe will include the above analysis in Sec 4.5 and move Figure 11 to the main text (replacing Figure 7).\n\n**3. Scaling of $\\\\ell^*$ with progressively more challenging tasks**\n\nWe would love to provide benchmarking analysis, but unfortunately the NeurIPS rebuttal format does not allow for rich media. Therefore, we will resort to explaining the theoretical cost of executing a single layer of our method vs. the underlying sequence mixer used (Mamba) instead. Denoting the sequence length by $T$, the state size by $N$, and the number of iterations to convergence by $\\\\ell^*$, the FLOPS are:\n\n| Model | Sequence Mixing Cost | Channel Mixing Cost |\n| --------      | -------     | -------   |\n| Mamba | $\\\\mathcal{O}(TN)$ (forward), $\\\\mathcal{O}(TN)$ (backward) |$0$ |\n| FPMamba (H, DPLR) | $\\\\mathcal{O}(TN \\\\ell^*)$ (forward), $\\\\mathcal{O}(TN)$ (backward) | $\\\\mathcal{O}(T N\\\\ell^*)$ (forward), $\\\\mathcal{O}(TN)$ (backward) |\n| FPMamba (K) | $\\mathcal{O}(TN \\\\ell^*)$ (forward), $\\\\mathcal{O}(TN)$ (backward) | $\\\\mathcal{O}(T N \\\\sqrt{N} \\\\ell^{*})$ (forward), $\\\\mathcal{O}(TN\\\\sqrt{N})$ (backward)|\n\n\nNote that the overall cost of FP-Mamba is *$\\\\ell^\\*$ times the cost of channel+sequence mixing* for the forward pass while **no additional cost for the iteration occurs for the backward pass**. While the sequence mixing cost is inherited from Mamba, the **channel mixing incurs an additional cost that is sub-quadratic in state size and linear in sequence length** in all three variants of the mixers investigated in this paper. \n\nFigure 3c depicts the value of $\\\\ell^\\*$ in a progressively more challenging task. In this state tracking task $A\\_5$, the difficulty corresponds to the number of state transitions, which is equal to the sequence length $T$. From the figure, we observe a linear relationship between $\\\\ell^\\*$ and $T$, indicating that, at least in the state tracking problem, $\\\\ell^\\*$ scales linearly with the difficulty of the task. Note, however, that on simpler tasks (Figures 5b, 7, 10) the required number of fixed-point iterations $\\\\ell^\\*$ remains well below the sequence length $T$. Finally, the **overall FLOPs are scaled by the task-specific** $\\\\ell^\\*$ according to the cost in the table above. We will update the paper with this analysis.\n\n\n\n\n**4. Effect of normalization factor $\\\\mathbf{(I-\\\\Lambda\\_t)}$ on class of matrices $A\\_t$.**\n\nThank you for pointing out the missing description of the representable dense matrices $\\\\mathbf{A}\\_t$ in the presence of the normalization factor $(\\\\mathbf{I}-\\\\mathbf{\\\\Lambda}\\_t)$. To drive $\\\\mathbf{A}\\_t$, let us start by assuming a fixed-point was found according to Thm 3.1:\n\n$$h\\_t^* = \\\\mathbf{\\\\Lambda}\\_t h\\_{t-1}^* + (\\\\mathbf{I}-\\\\mathbf{\\\\Lambda}\\_t) (\\\\mathbf{Q}\\_t\\\\mathbf{B}\\_t x\\_t + (\\\\mathbf{I} -\\\\mathbf{Q}\\_t)h\\_t^*)$$\n\nRearranging the terms allows to move $h\\_t^*$ to the other side:\n\n$$(\\\\mathbf{I} - (\\\\mathbf{I} - \\\\mathbf{\\\\Lambda}\\_t)(\\\\mathbf{I} - \\\\mathbf{Q}\\_t))h\\_t^* = \\\\mathbf{\\\\Lambda}\\_t h\\_{t-1}^* + (\\\\mathbf{I}-\\\\mathbf{\\\\Lambda}\\_t) \\\\mathbf{Q}\\_t\\\\mathbf{B}\\_t x\\_t$$\n\nTherefore, $\\\\mathbf{A}\\_t = (\\\\mathbf{I} - (\\\\mathbf{I} - \\\\mathbf{\\\\Lambda}\\_t)(\\\\mathbf{I} - \\\\mathbf{Q}\\_t))^{-1}  \\\\mathbf{\\\\Lambda}\\_t = (\\\\mathbf{\\\\Lambda}\\_t^{-1}(\\\\mathbf{I} - (\\\\mathbf{I} - \\\\mathbf{\\\\Lambda}\\_t)(\\\\mathbf{I} - \\\\mathbf{Q}\\_t)))^{-1} = (\\\\mathbf{\\\\Lambda}\\_t^{-1} - (\\\\mathbf{\\\\Lambda}\\_t^{-1} - \\\\mathbf{I})(\\\\mathbf{I} - \\\\mathbf{Q}\\_t))^{-1} =(\\\\mathbf{I} + (\\\\mathbf{\\\\Lambda}\\_t^{-1} - \\\\mathbf{I})\\\\mathbf{Q}\\_t)^{-1}$\n\nFollowing the standard assumptions that $0\\\\preceq \\\\mathbf{\\\\Lambda}\\_t, \\\\mathbf{Q}\\_t\\\\preceq \\\\mathbf{I}$, the matrix $\\\\left(\\\\mathbf{I}+\\\\left(\\\\mathbf{\\\\Lambda}\\_t^{-1} - \\\\mathbf{I}\\\\right)\\\\mathbf{Q}\\_t\\\\right)$ is full rank and $\\\\succeq \\mathbf{I}$. **Therefore its inverse $\\\\mathbf{A}\\_t$ exists and is contractive.** The expressivity of $\\\\mathbf{A}\\_t$ is only limited if  $\\\\mathbf{\\\\Lambda}\\_t\\\\approx \\\\mathbf{I}$. This however, would also be problematic for a diagonal SSM and therefore the Mamba initialization is biased towards $\\\\mathbf{\\\\Lambda}\\_t \\\\prec \\\\mathbf{I}$. Thus, we argue that in practice, these modifications do not pose a significant problem. We will make sure to refer to this analysis when we introduce normalization in Sec. 3.1.\n\n\n\n**Questions:**\n\n1. *Are FP-RNNs unstable during training?* Although a large portion of our theoretical contributions focus on this issue, we notice that under certain conditions we can still face instability in training. Specifically, we notice that for long sequences in the state tracking tasks ($A\\_5$, $S\\_5$), where the difficulty of the task scales linearly with the sequence length, training can become unstable. In this case, we notice that incorporating off-the-shelf stability techniques, such as weight normalization, can significantly help with this issue (Gent et al, 2023).\n2. *Are there trade-offs between the number of parameters and the required number of fixed-point iterations?* In our experiments, we indeed observe a relationship between the parameter numbers and the required number of fixed-point iterations for finding the fixed point. However, this only happens when the model is modified in depth, and not in width. Specifically, we observe that when increasing the depth of the model for more challenging tasks, the number of iterations indeed reduces. \n3. *Is there a way to reduce the number of fixed-point iterations?* We have several potential solutions to reducing the number of fixed-point iterations. Firstly, we observe that off-the-shelf optimization techniques do not perform as well as fixed-point iterations near the initial point of the hidden state, but are much faster to find the exact solution once the hidden state is in the vicinity of the fixed-point. Consequently, we believe a hybrid approach would be possible to significantly convergence. We also introduce some techniques in Appendix B.4 for this purpose. Finally, as we noted in our response in the previous question, we observe that for deeper networks, the fixed-point becomes much easier to find. This may indicate the existence of a structure in the mixer (e.g. positive semi-definiteness) that can significantly improve the cost of finding the fixed-point.\n\n\nWe thank the reviewer for the list of minor issues which we will fix in the camera ready version. We hope that our response addresses the reviewer’s concerns and would be interested to hear if they are considering raising their score to help increase the visibility of our work during the conference. In case there are any remaining questions, we are of course happy to resolve them during the discussion period.\n\n\n---\n\n\nMerrill et al (2024), *”The Illusion of State in State-Space Models”*, https://arxiv.org/abs/2404.08819\n\nCirone et al. (2024), *”Theoretical Foundations of Deep Selective State-Space Models”*, https://arxiv.org/abs/2402.19047\n\nGeng et al. (2023). *\"Torchdeq: A library for deep equilibrium models.\"* https://arxiv.org/abs/2310.18605"}]

Author rebuttal:

Meta-review: The paper investigates a paramterizations of dense linear RNNs as fixed points of diagonal linear RNNs which enables a tunable trade-off between expressivity and efficiency. The reviewers praise the clarity of the presentation and that it is easy to follow. They also point out that  fixed-point RNNs are an elegant way to interpolate between diagonal and dense RNNs, enabling adaptive computation. During the discussion period, the authors clarified several important questions. Overall, the feedback for this paper is very positive and I recommend acceptance.
Decision: Accept (spotlight)