PaperlayerView exact revision on arXiv

Source-linked AI summary

Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues

Riccardo Grazzi, Julien Siems, Arber Zela, Jörg K. H. Franke, Frank Hutter, Massimiliano Pontil

arXiv:2411.12537v5cs.LGcs.CLcs.FL

TL;DR

Transformers and current LRNNs struggle with state-tracking, including parity, despite the relevance of maintaining internal state to tasks such as code evaluation. The paper proves limits tied to positive eigenvalues and matrix structure, and studies extending LRNN eigenvalues to include negatives. Modified LRNNs improve state-tracking, while large-scale versions retain competitive language-modeling performance.

  • Problem

    Transformers and current LRNNs struggle to learn state tracking from update sequences, including the simple parity task.

    Source: §1 · p. 2

  • Method

    The paper analyzes eigenvalue and matrix-structure limits and extends LRNN state-transition eigenvalues to [−1, 1], including products of generalized Householder matrices.

    Source: §1 · p. 2

  • Results

    Modified Mamba and DeltaNet improve state-tracking performance, and versions up to 1.3B parameters perform comparably to original models on generative language modeling.

    Source: §1 · p. 2

  • Takeaways & Limitations

    LRNNs with products of generalized Householder matrices whose eigenvalues lie in [−1, 1] can learn any regular language.

    Source: §1 · p. 2

    The modification is not directly compatible with log-space cumulative-product techniques used by some diagonal LRNNs, including Mamba2, GLA, and mLSTM.

    Source: §6 · p. 10

Abstract

from arXiv · show

Linear Recurrent Neural Networks (LRNNs) such as Mamba, RWKV, GLA, mLSTM, and DeltaNet have emerged as efficient alternatives to Transformers for long sequences. However, both Transformers and LRNNs struggle to perform state-tracking, which may impair performance in tasks such as code evaluation. In one forward pass, current architectures are unable to solve even parity, the simplest state-tracking task, which non-linear RNNs can handle effectively. Recently, Sarrof et al. (2024) demonstrated that the failure of LRNNs like Mamba to solve parity stems from restricting the value range of their diagonal state-transition matrices to $[0, 1]$ and that incorporating negative values can resolve this issue. We extend this result to non-diagonal LRNNs such as DeltaNet. We prove that finite precision LRNNs with state-transition matrices having only positive eigenvalues cannot solve parity, while non-triangular matrices are needed to count modulo $3$. Notably, we also prove that LRNNs can learn any regular language when their state-transition matrices are products of identity minus vector outer product matrices, each with eigenvalues in the range $[-1, 1]$. Our experiments confirm that extending the eigenvalue range of Mamba and DeltaNet to include negative values not only enables them to solve parity but consistently improves their performance on state-tracking tasks. We also show that state-tracking enabled LRNNs can be pretrained stably and efficiently at scale (1.3B parameters), achieving competitive performance on language modeling and showing promise on code and math tasks.

1 INTRODUCTION

LRNNs offer linear scaling for long sequences, but current architectures struggle with state-tracking, including parity. The paper extends eigenvalue-based results to non-diagonal LRNNs and shows that negative eigenvalues improve state-tracking while preserving efficiency and training stability.

1 INTRODUCTION

  • Transformers scale quadratically with sequence length, while LRNNs offer linear scaling and competitive performance for long sequences.LRNNs update states through matrix-vector products with structured, often input-dependent state-transition matrices.Source: §1 · p. 1
  • Transformers and current LRNNs struggle to track finite-state machines, including parity, while non-linear RNNs can track finite-state machines but are challenging to parallelize across sequence length.The paper notes potential relevance to entity tracking, nested code structures, and reasoning that benefits from maintaining state.Source: §1 · p. 2
  • Extending the eigenvalue range from [0, 1] to [−1, 1] significantly improves LRNN state-tracking without compromising efficiency or training stability.The authors report that Mamba and DeltaNet can use the extended range and demonstrate improved performance on parity, modular arithmetic, and permutation composition.Source: §1 · p. 2
  • Finite-precision LRNNs with only positive real state-transition eigenvalues cannot solve parity at arbitrary lengths, and non-triangular matrices are required for counting modulo 3.Products of generalized Householder matrices with eigenvalues in [−1, 1] can implement any regular language.Source: §1 · p. 2
  • Modified Mamba and DeltaNet models up to 1.3B parameters achieve performance comparable to their originals on generative language modeling, while DeltaNet improves code and math perplexity.Source: §1 · p. 2

2 RELATED WORK

Prior work characterizes expressivity limits for Transformers and recurrent models, while LRNN research spans state-space and linear-attention architectures. This paper builds on analyses of positive-eigenvalue diagonal LRNNs by studying non-diagonal models and testing negative eigenvalues in practice.

2 RELATED WORK

  • Mamba and GLA use gated state-space or linear-attention recurrences, while DeltaNet and TTT-Linear explore more expressive non-diagonal state-transition matrices.S4 and H4 are LRNN variants inspired by state-space models, and xLSTM combines non-linear and linear RNNs.Source: §2 · p. 2
  • Transformers can learn shortcut solutions for solvable finite-state automata, but these may not generalize to arbitrary sequence lengths; diagonal LRNNs also face limits under fixed depth, size, or precision assumptions.Prior results use differing assumptions, including log-precision arithmetic and depth scaling with sequence length.Source: §2 · p. 3
  • Sarrof et al. (2024) showed that finite-precision diagonal LRNNs with positive state-transition values cannot solve parity, but did not test negative eigenvalues empirically.Earlier empirical DeltaNet state-tracking modifications used a non-linear recurrence that is hard to parallelize; this work studies a minimal modification that maintains efficient large-scale training.Source: §2 · p. 3

3 BACKGROUND

The background defines LRNNs as recurrent state updates and connects their layers to finite-state automata. It frames state-tracking as computing products of updates, including group word problems such as parity and permutation tracking.

3.1 LINEAR RECURRENT NEURAL NETWORKS (LRNNS)

  • An LRNN layer maps each input vector to a state update and output through learnable functions A, B, and dec, with variants differing in their forms.The recurrence is H_i = A(x_i)H_{i−1} + B(x_i), followed by decoding the state and input.Source: §3.1 · p. 3
  • Common LRNN transition matrices are diagonal or generalized Householder, the identity minus a vector outer product, supporting efficient matrix-vector products and having eigenvalues in [0, 1].Table 1 gives instances of LRNN layers, including Mamba and other architectures.Source: §3.1 · p. 3, Table 1 · p. 3

3.2 FORMAL LANGUAGE THEORY

  • A finite-state automaton recognizes a language by transitioning among states as it reads words; regular languages are precisely those recognized by such automata.The set of transformations induced by all words forms a finite transition monoid under function composition.Source: §3.2 · p. 4
  • State-tracking can be expressed as computing the product of a sequence of updates in a monoid, with group word problems including addition modulo m and permutation composition.Parity is the S2 word problem; the passage identifies chess-move tracking and code evaluation as potentially harder than the S5 word problem.Source: §3.2 · p. 4
  • An LRNN layer implements an automaton when its hidden-state updates can be mapped onto the automaton’s state transitions, allowing a decoder to recognize the automaton’s language.The paper distinguishes this general capability from whether transition matrices fit the structures imposed by current LRNNs.Source: §3.2 · p. 4

4 THEORETICAL ANALYSIS

The theory establishes eigenvalue and matrix-structure limits on LRNN state tracking, then characterizes how products of generalized Householder matrices expand their expressivity. Negative eigenvalues are necessary for parity, while non-triangular transitions and GH products support broader counting and regular-language capabilities.

4.1 LIMITATIONS OF CURRENT LRNNS

  • Finite-precision LRNNs need at least one transition matrix with a non-real or negative eigenvalue to solve parity at arbitrary lengths.A scalar recurrence with a(1) = −1 alternates between the two parity states.Source: §4.1 · p. 5, Figure 2 · p. 5
  • Counting modulo m, when m is not a power of two, requires a product of transitions with a non-real eigenvalue.Real eigenvalues, including negative ones, are insufficient for modulo m > 2 in the one-layer case.Source: §4.1 · p. 5

4.2 ALLOWING NEGATIVE EIGENVALUES

  • Extending diagonal and GH transitions to eigenvalues in [−1, 1] permits negative values while keeping matrix norms at most one; triangular transitions still cannot count modulo 3.The modified GH transition has an eigenvalue 1 − 2ϕ(x); the paper notes the modulo-counting limitation even with negative eigenvalues.Source: §4.2 · p. 6

4.3 EXPRESSIVITY OF PRODUCTS OF GENERALIZED HOUSEHOLDER MATRICES

  • Products of GH matrices with eigenvalues in [−1, 1] represent every matrix with Euclidean norm at most one, and these products remain norm-bounded.The construction can represent any such matrix using at most 3n GH factors.Source: §4.3 · p. 6
  • A one-layer LRNN can implement any FSA whose transition monoid is a group, using permutation representations built from GH factors.For cyclic transition groups, the construction uses two-dimensional matrices; parity can use scalar transitions in {−1, 1}.Source: §4.3 · p. 7
  • Repeated products of GH transitions with eigenvalues in [−1, 1] let finite-precision LRNNs recognize any regular language, with at most 2|Q| layers in the stated construction.In the worst case, both layer count and width are exponential in the FSA's number of states; the authors conjecture a more refined decomposition could reduce the layer count to linear.Source: §4.3 · p. 7

5 EXPERIMENTS

The experiments test whether extending LRNN state-transition eigenvalues from [0, 1] to [−1, 1] improves state-tracking and language modeling. The extension enables parity and helps DeltaNet on coding and math, while results vary across architectures and tasks.

5 EXPERIMENTS

  • The experiments compare Mamba and DeltaNet with original and extended eigenvalue ranges on synthetic tasks and language modeling; the range extension increases expressivity without additional computational cost.The language-modeling setup uses 340M- and 1.3B-parameter DeltaNet models and 370M-parameter Mamba models trained on FineWeb-100B.Source: §5 · p. 8, Table 2 · p. 8, §5.3 · p. 9

5.1 CHOMSKY HIERARCHY

  • Extending the eigenvalue range enables every examined model to fully solve parity and substantially improves Mamba and especially DeltaNet on both modular arithmetic tasks.The authors note that DeltaNet’s non-diagonal transitions are better suited to these tasks.Source: §5.1 · p. 8, Table 3 · p. 8

5.2 STATE-TRACKING

  • With swap-only inputs, one-layer DeltaNet [−1, 1] fully learns S5, whereas five-layer DeltaNet [0, 1] generalizes only slightly beyond training length.Adding 3-element permutations reduces performance across models, though five-layer DeltaNet [−1, 1] still generalizes well; four tokens per group element also support extrapolation to around length 200.Source: §5.2 · p. 9, Figure 4 · p. 9

5.3 LANGUAGE MODELING

  • DeltaNet [−1, 1] achieves lower perplexity than [0, 1] on coding and math at both model sizes, while Mamba’s modifications degrade performance across these tasks.DeltaNet [−1, 1] is slightly worse on TriviaQA and slightly better on SlimPajama.Source: Figure 5 · p. 9, §5.3 · p. 10
  • At 340–370M parameters, extended-range Mamba gains +2.1% average accuracy on the second task subset, and DeltaNet gains +2% SWDE and +4.4% SQUAD; 1.3B DeltaNet results are mixed.The authors suggest training beyond 100B tokens may be needed to fully unlock the increased expressivity.Source: §5.3 · p. 10, Table 4 · p. 10

6 CONCLUSION

The paper concludes that extending LRNN eigenvalue ranges improves state-tracking expressivity without added training or inference overhead. It also identifies compatibility and theoretical-scope questions that remain open.

6 CONCLUSION

  • Extending state-transition eigenvalues from [0, 1] to [−1, 1] enhances LRNN state-tracking expressivity without adding training or inference overhead.Mamba solves parity, but its diagonal structure limits further gains; DeltaNet’s non-diagonal transitions support broader task performance through simultaneous token and channel mixing.Source: §6 · p. 10
  • The modification is not directly compatible with log-space cumulative-product techniques used by some diagonal LRNNs, including Mamba2, GLA, and mLSTM.The authors call for further study of large-scale training, potential expressivity trade-offs, and the multi-layer theoretical expressivity of DeltaNet [−1, 1].Source: §6 · p. 10

A.1 NOTATION

  • The notation section defines regular-expression conventions, including Kleene star for repetition and star-free languages as those expressible without it.It also specifies conventions for scalars, vectors, matrices, Hadamard products, norms, and canonical basis vectors.Source: §A.1 · p. 16

A.2 DETAILS OF TABLE 1

  • The appendix explains that Mamba’s recurrence is written row by row for simplicity, while an alternative full-matrix form uses an element-wise product instead of the matrix-matrix product in the general recurrence.The implementation follows the official Mamba code’s formulation of B(xt).Source: §A.2 · pp. 16–17

A.3 REGULAR LANGUAGES AND RECURRENT NEURAL NETWORKS

  • A single-layer LRNN can recognize any regular language by encoding finite-state-automaton states as one-hot vectors and letters as Boolean transition matrices.Those matrices can have norm greater than one, which the appendix notes can make language-model recurrences unstable.Source: §A.3 · p. 17

A.4 FINITE PRECISION

  • For the positive expressivity results, finite precision means computations use a finite datatype independent of input length; the negative results instead allow an arbitrary finite set and use a cast function.The appendix notes that practical floating-point datatypes may not capture every value in the constructions, while finite precision can include values such as 0, 1, and −1.Source: §A.4 · p. 17

A.4.1 INITIAL STATE, MATRIX-VALUED STATES, AND THE DECODER FUNCTION

  • The theoretical constructions can make the initial state learnable, though a beginning-of-sequence token can provide the same effect; they use vector-valued states, while matrix-valued states matter for associative recall.The decoder is abstracted from the recurrence; the positive results use either no decoder or a linear one, though more powerful decoders can reduce state size and may be hard to learn.Source: §A.4.1 · p. 18

B PARITY AND MODULAR COUNTING – PROOFS

The proof analyzes how casting sums of polynomial-exponential terms into finite precision eventually stabilizes or alternates, depending on whether negative eigenvalues are present. In particular, nonnegative eigenvalues yield a constant cast value for sufficiently large powers.

B PARITY AND MODULAR COUNTING – PROOFS

B.1 PROOF OF THEOREM 1

For a one-layer LRNN on repeated 1s, nonnegative eigenvalues make the finite-precision state eventually constant, while parity alternates. The proof uses this mismatch to rule out parity recognition, including for finitely many layers.

B.1 PROOF OF THEOREM 1

  • A one-layer LRNN whose A(1) has only nonnegative eigenvalues has an eventually constant finite-precision state on 1^k, so its output cannot match alternating parity.The argument extends inductively to finitely many layers because each later layer receives an eventually constant input.Source: §B.1 · p. 20
  • The proof derives eventual stabilization by expressing powers of A(1) through Jordan blocks and applying the finite-precision cast argument component-wise.It assumes products are evaluated in infinite precision before casting, simplifying the finite-precision analysis.Source: §B.1 · p. 20

B.2 PROOF OF THEOREM 2

The proofs bound what finite-precision LRNNs can recognize under real-eigenvalue constraints and show how products of generalized Householder matrices support modular counting. They also establish eigenvalue and factorization properties used in the constructions.

B.2 PROOF OF THEOREM 2

  • With L layers under the stated real-eigenvalue condition, the eventual output period divides 2^L, so unary modular languages are recognized only when the modulus is a power of two.The induction tracks periodic layer inputs and bounds the period at each layer.Source: §B.2 · p. 22

C.1 PRODUCTS OF TWO HOUSEHOLDERS AND MODULAR COUNTING

C.2 PROOF OF PROPOSITION 1

  • Every matrix with norm at most one can be expressed as a product of generalized Householder matrices.The proof factors its singular value decomposition components into such matrices.Source: §C.2 · p. 23
  • For a product of generalized Householder matrices, each eigenvalue is either 1 or has magnitude below 1.The proof bounds the product using the factors’ Euclidean norms.Source: §C.2 · p. 23
  • A product of two symmetric positive semidefinite matrices has real nonnegative eigenvalues, bounded in magnitude by the product matrix’s norm.The proof uses similarity to a symmetric positive semidefinite matrix and continuity when a factor is singular.Source: §C.2 · pp. 23–24

C.3 PROOF OF THEOREM 3

The proofs construct finite-precision LRNNs that implement finite-state automata, using permutation representations and cascade products. The Krohn–Rhodes decomposition supplies the cascade structure for the general construction.

C.3 PROOF OF THEOREM 3

  • An LRNN can implement an automaton using permutation-matrix transitions, with bounded integer entries enabling finite-precision implementation.For cyclic transition groups, the construction can use a scalar state for parity or two-dimensional rotations when the group order is at least three.Source: §C.3 · p. 24

C.4 KROHN-RHODES THEOREM

  • The Krohn–Rhodes theorem represents every finite-state automaton as a cascade product of at most 2|Q| permutation-reset automata.Each component transition is either a permutation or a constant map.Source: §C.4 · pp. 24–25

C.5 PROOF OF THEOREM 4

  • The LRNN construction implements the cascade by assigning each component automaton a layer, with finite-precision matrices and vectors.The construction uses entries in {0, 1} or finite sets of state-index integers.Source: §C.5 · p. 25

D LRNNS CAN DO MODULAR ADDITION USING ONLY REFLECTIONS

Two-layer LRNNs using only reflection state transitions can perform addition modulo any m. The construction alternates a modulo-2 state with parity-conditioned reflections that track the group element.

D LRNNS CAN DO MODULAR ADDITION USING ONLY REFLECTIONS

  • DeltaNet [−1, 1] can therefore solve the cyclic-group word problem with two layers.The construction computes the sum of input symbols modulo m for arbitrary sequence length.Source: D LRNNS CAN DO MODULAR ADDITION USING… · p. 26
  • With reflection-only transitions, two layers are needed because a group element cannot be represented directly as a rotation; the construction uses two reflections instead.A first layer tracks parity, and a second layer applies parity-dependent reflections to update the group element.Source: D LRNNS CAN DO MODULAR ADDITION USING… · p. 26
  • Two-layer LRNNs with reflection transitions can perform addition modulo any m, using 2 scalar states first and 2m vector states second.The first layer counts modulo 2; the second uses two reflection matrices per group element, conditioned on the first layer’s parity.Source: D LRNNS CAN DO MODULAR ADDITION USING… · p. 26

E.1.1 DETAILS ON THE EXPERIMENTAL SETUP

The experiments compare recurrent models and a Transformer on parity and modular arithmetic tasks, training on short sequences and evaluating length generalization. The appendix reports task definitions and the formal-language performance summary.

E.1.1 DETAILS ON THE EXPERIMENTAL SETUP

  • Models trained on sequence lengths 3–40 were evaluated on lengths 40–256; the study compared mLSTM, sLSTM, Mamba, DeltaNet, and a Transformer.Parity models used two blocks; modular arithmetic models used three layers, with task-specific settings and 100k training steps.Source: §E.1.1 · p. 27
  • Table 5 reports scaled accuracy for recurrent models on regular and context-free language tasks, with median ± median absolute deviation and best scores across three runs.A score of 1.0 denotes perfect accuracy and 0.0 random guessing; the table caption reports a positive impact from allowing eigenvalues in [−1, 1] across architectures.Source: Table 5 · p. 28

E.1.2 DETAILS ON THE EVALUATED TASKS

  • The evaluated tasks were parity and modular arithmetic with or without brackets, using modulus 5 for both arithmetic tasks.The arithmetic tasks use operation and special tokens; the bracketed version additionally includes opening and closing parentheses.Source: §E.1.2 · p. 28

E.2.1 DETAILS OF THE EXPERIMENTS

The experiments examine state-tracking and length generalization, including permutation-group tasks and cyclic-group addition. They also report run variability and the large-scale language-modeling evaluation setup.

E.2.1 DETAILS OF THE EXPERIMENTS

  • The S5 experiments include unrestricted permutations, swaps, permutations of up to three elements, and a four-token-per-transition encoding.Inputs are sampled from S5 or restricted permutation sets; the special-token encoding inserts three identity tokens between transitions.Source: §E.2.1 · p. 28
  • For formal-language length tests, models trained up to length 40 were evaluated on sampled sequences of lengths 40–256; the Transformer nearly fails to extrapolate while remaining near-perfect within training length.Figure 6 reports mean and 95% confidence intervals over 8,192 test sequences.Source: Figure 6 · p. 29
  • One DeltaNet [−1, 1] run with five layers performed poorly on S5 with four tokens per transition, despite efforts to reduce run variability.The experiments used three seeds and shared train and validation datasets across runs.Source: §E.2.1 · pp. 29–30

E.2.2 CYCLIC GROUPS

  • On Z60, extending the eigenvalue range seems to help with both input encodings, while Mamba [−1, 1] performs best but generalizes poorly to longer sequences.The two-token transition encoding helps only marginally; the plotted evaluations use one seed.Source: §E.2.2 · p. 31, Figure 8 · p. 31

E.3.1 DETAILS ON THE EXPERIMENTAL SETUP

  • The 1.3B DeltaNet language-model runs used 32 Nvidia A100s for 50,000 steps, while 340M DeltaNet and 370M Mamba runs used 16 A100s for 200,000 steps.All models used context length 2048 and learning rate 3e-4; evaluation covered language-modeling and recall-intensive benchmarks including LAMBADA, PIQA, HellaSwag, FDA, SWDE, and SQUAD.Source: §E.3.1 · p. 31, §E.3.2 · p. 31

E.4 IMPLEMENTATION

The implementation extends Mamba and DeltaNet state-transition eigenvalues from [0, 1] to [−1, 1]. The appendix describes the kernel changes and reports stable large-scale training alongside a length-extrapolation trade-off for coding and math.

E.4 IMPLEMENTATION

  • DeltaNet’s extended range required no Triton-kernel change, while Mamba needed forward and backward CUDA associative-scan modifications that did not add computational cost.The modified implementation was checked against a naive for-loop; DeltaNet’s change also multiplies B(xt) by 2.Source: §E.4 · p. 31
  • All reported models trained stably with the same hyperparameters; the 1.3B runs used 50,000 optimizer steps versus 200,000 for the 340M runs.The 1.3B runs used a four-times-larger batch size.Source: Figure 9 · p. 32
  • Mamba [−1, 1] has worse length-extrapolation perplexity on coding and math tasks than the [0, 1] baseline.The dashed vertical line marks the 2048-token training context length.Source: Figure 10 · p. 32
  • The change is not directly compatible with log-space products used by Mamba2, GLA, and mLSTM; early chunkwise GLA tests showed degraded performance.The authors also note that negative values may bring the normalization term of normalized-state methods such as mLSTM close to zero.Source: §E.4 · p. 32

Related papers

Loading 2411.12537v5…