PaperlayerView exact revision on arXiv

Source-linked AI summary

DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products

Julien Siems, Timur Carstensen, Arber Zela, Frank Hutter, Massimiliano Pontil, Riccardo Grazzi

arXiv:2502.10297v7cs.LGcs.CLcs.FL

TL;DR

Linear RNNs trade efficiency against expressivity because their transition matrices are structurally constrained. DeltaProduct addresses this by taking multiple gradient steps per token, forming Householder-product transitions whose tunable order improves state tracking and language-modeling behavior, especially length extrapolation.

  • Problem

    Linear RNNs face an efficiency–expressivity trade-off because transition-matrix structure limits what they can represent in finite precision.

  • Method

    DeltaProduct takes n_h gradient steps per token, producing state transitions formed from products of n_h generalized Householder transformations.

  • Results

    Experiments show superior state tracking and language modeling over DeltaNet, with sharply improved length extrapolation as the number of Householder factors increases.

  • Takeaways & Limitations

    Increasing n_h provides a tunable route to greater state-transition expressivity while preserving DeltaProduct’s norm-bounded recurrence structure.

  • Takeaways & Limitations

    The norm bound guarantees stable recurrence but restricts representation of some higher-spectral-norm transitions, and combining stability with universal regular-language recognition remains open.

Abstract

from arXiv · show

Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling, offering efficient training and linear-time inference. However, existing architectures face a fundamental trade-off between expressivity and efficiency, dictated by the structure of their state-transition matrices. Diagonal matrices, used in models such as Mamba, GLA, or mLSTM, yield fast runtime but have limited expressivity. To address this, recent architectures such as DeltaNet and RWKV-7 adopted a diagonal plus rank--1 structure, which allows simultaneous token and channel mixing, improving associative recall and, as recently shown, state-tracking when allowing state-transition matrices to have negative eigenvalues. Building on the interpretation of DeltaNet's recurrence as performing one step of online gradient descent per token on an associative recall loss, we introduce DeltaProduct, which instead takes multiple ($n_h$) steps per token. This naturally leads to diagonal plus rank--$n_h$ state-transition matrices, formed as products of $n_h$ generalized Householder transformations, providing a tunable mechanism to balance expressivity and efficiency. We provide a detailed theoretical characterization of the state-tracking capability of DeltaProduct in finite precision, showing how it improves by increasing $n_h$. Our extensive experiments demonstrate that DeltaProduct outperforms DeltaNet in both state-tracking and language modeling, while also showing significantly improved length extrapolation capabilities.

1 Introduction

Linear RNNs offer efficient sequence processing but face an expressivity–efficiency trade-off governed by their state-transition matrices. DeltaProduct addresses this gap by taking multiple gradient steps per token, yielding tunable Householder-product transitions with improved theoretical and empirical state-tracking performance.

  • Motivation: Linear RNNs provide efficient sequence processing, but transition-matrix structure creates a fundamental trade-off between training efficiency and expressivity.Diagonal transitions are efficient but severely limited in finite precision.
  • Approach: DeltaProduct performs multiple gradient-descent steps per token, producing products of generalized Householder matrices that tune recurrence expressivity through n_h.This extends DeltaNet’s single-step associative-recall interpretation.
  • Approach: DeltaProduct provides a controllable interpolation between efficient structured transitions and more expressive transitions by increasing the number of Householder factors.The method is designed to balance recurrence expressivity and efficiency.
  • Contributions: Theoretical results characterize improved finite-precision expressivity as n_h increases, while experiments report gains in state tracking and language modeling.The contribution includes both formal state-tracking results and empirical validation across domains.

2 Background

Linear RNNs update a hidden state through input-dependent transition and additive-update functions, enabling parallel sequence processing. DeltaNet uses generalized Householder transitions and can be interpreted as one online gradient-descent step on an associative-recall loss.

  • Linear RNNs: A linear RNN updates its hidden state with an input-dependent transition matrix and additive term, then decodes the resulting state and input.The recurrence is H_i = A(x_i)H_{i−1} + B(x_i).
  • Linear RNNs: Diagonal-transition models such as Mamba, GLA, and mLSTM support efficient parallel processing through chunkwise or scan-based computation.Their implementations differ primarily in the choices of A, B, and dec.
  • DeltaNet: DeltaNet uses generalized Householder transitions whose eigenvalues are 1 and 1−β_i, interpolating geometrically between identity and projection.The parameter β_i controls the transformation type.
  • DeltaNet: Each DeltaNet recurrence step is equivalent to one online gradient-descent update on a quadratic key-to-value loss.The step size is β_i.
  • State Tracking: State tracking can be formulated as a monoid word problem that maps each input sequence to its successive associative products.Finite-group word problems, including permutation-group problems, are difficult for Transformers and linear RNNs.

3 Related Work

Related work develops linear RNNs through state-space and causal-linear-attention perspectives, while structured matrix products provide a route to expressive, norm-preserving state updates. Extending eigenvalues to negative values improves state-tracking capabilities.

  • Linear RNN Perspectives: State-space models and causal linear attention form the two main perspectives underpinning modern linear RNN research.Examples include S4, H4, LRU, Mamba, and related gated models.
  • Structured Transitions: Structured matrix products have been used in recurrent state updates because orthogonal factors preserve norms and support long-term dependency learning.Prior work includes Givens rotations, Kronecker products, and Householder reflections.
  • State Tracking: Expanding linear RNN transition eigenvalues from [0, 1] to [−1, 1] enables DeltaNet to perform reflections and solve broader state-tracking tasks.This includes parity checking and more general group word problems.

4 DeltaProduct

DeltaProduct forms token-dependent state transitions from multiple generalized Householder transformations, increasing rank and expressivity as n_h grows while retaining a norm bound. Its theory establishes broad finite-precision state-tracking capability, alongside an expressivity–stability trade-off.

  • 4 DeltaProduct: DeltaProduct generates n_h keys, values, and step sizes per token and applies multiple gradient updates instead of DeltaNet’s single update.The resulting transition is a product of generalized Householder transformations.
  • 4 DeltaProduct: Expanding the Householder product yields an identity-plus-rank-at-most-n_h transition, allowing interpolation from generalized Householder matrices toward denser matrices.The gated variant additionally scales the transition with a forget gate.
  • 4 DeltaProduct: Householder products can represent any orthogonal matrix, whereas identical keys collapse to a single Householder transformation and orthogonal keys yield a symmetric low-rank update.Two reflections illustrate how products can produce rotations.
  • 4.1 State-Tracking Capabilities: For any n, DeltaProduct can solve the symmetric-group word problem with one layer at n_h=n−1, three layers when n_h>1, or four layers when n_h=1.The construction uses a lookup table in the penultimate layer for the multi-layer cases.
  • 4.1 State-Tracking Capabilities: Gated DeltaProduct recognizes any regular language with a finite number of layers, and increasing n_h improves expressivity relative to DeltaNet while reducing required depth or lookup-table size.The comparison places DeltaProduct ahead of DeltaNet and, up to three layers, ahead of RWKV-7.
  • 4.1 State-Tracking Capabilities: DeltaProduct transitions satisfy ||A(x_i)|| ≤ 1, guaranteeing stable recurrence but preventing representation of some higher-spectral-norm copy matrices.Relaxing this constraint can increase expressivity but may introduce instability.
  • 4.1 State-Tracking Capabilities: Whether a continuous transition parameterization can combine guaranteed stability with recognition of every regular language in finitely many fixed layers remains open.This is identified as an unresolved expressivity–stability trade-off.

5 Experiments

Experiments evaluate DeltaProduct on state tracking, throughput, length extrapolation, hidden-state dynamics, and language modeling. Increasing the number of Householder products improves expressivity and extrapolation, while increasing recurrence cost linearly with n_h.

  • Implementation: Training and prefill throughput decreases as n_h increases because the recurrence becomes n_h times longer.The MLP cost remains unchanged when the embedding dimension is fixed, and the recurrence cost scales linearly with n_h.
  • State-Tracking: Higher n_h improves state-tracking extrapolation: S3 requires n_h = 2 and S5 requires n_h = 4 for reliable performance beyond length 128 in one layer.S4 and A5 extrapolate robustly with n_h = 2, despite theoretical constructions suggesting more Householder transformations.
  • State-Tracking: DeltaProduct2 learns S4 transformations using two reflections, with both beta values near 2 and keys concentrated in a three-dimensional subspace.This matches the interpretation of cube rotations as compositions of reflections acting on the S4 permutation structure.
  • State-Tracking: Increasing depth with n_h = 1 is less effective than increasing n_h: fitting the training context requires 3 layers for S3, 6 for S4, 3 for A5, and more than 10 for S5.The multi-layer models also show degraded length extrapolation compared with increasing the number of Householder products.
  • Language Modeling: DeltaProduct’s length extrapolation improves sharply from one to two Householders, and performance degradation is minimal at n_h = 3.The authors hypothesize that multiple updates accelerate forgetting, although DeltaProduct2 still benefits from a forget gate.
  • Language Modeling: Beyond the training context, DeltaNet’s effective rank increases substantially, whereas gated models reduce or maintain low effective rank after question-answer boundaries.Some DeltaProduct heads update at beginning-of-sequence tokens and then decay over the remainder of the sequence.
  • Language Modeling: DeltaProduct scales better in training perplexity and retains an advantage on lm-eval tasks at the largest tested scale.Additional results report that DeltaProduct and Gated DeltaProduct generally outperform their corresponding DeltaNet baselines when n_h increases.

6 Conclusion and Future Work

DeltaProduct extends DeltaNet with products of Householder transformations, using n_h to trade expressivity against computation. Experiments report stronger state tracking, formal-language recognition, language modeling, and length extrapolation, while the main limitation is increased training cost.

  • Conclusion: DeltaProduct extends DeltaNet with products of Householder transformations as state-transition matrices.Each recurrence step is interpretable as multiple gradient-descent steps on an associative-recall loss.
  • Conclusion: The number of Householder transformations n_h provides a tunable balance between expressivity and computational efficiency.Increasing n_h improves the model’s attainable transformations while increasing training computation.
  • Conclusion: Experiments report superior performance over DeltaNet in state tracking, formal-language recognition, and language modeling, with particularly strong length extrapolation.The conclusion presents these results as evidence that DeltaProduct remains scalable while increasing sequence-modeling capability.
  • Future Work: The main limitation is increased computational cost that scales linearly with n_h during training.Future work includes adaptive numbers of Householder transformations per token to reduce computation.

Supplementary Material

The supplementary material develops the theoretical foundations, expressivity results, implementation details, and additional experiments for DeltaProduct. It also discusses related constructions and the expressivity–stability trade-off.

  • Theory: The supplementary material characterizes generalized Householder products, including special cases and the spectrum of products of two transformations.These results provide algebraic background for the model’s state-transition matrices.
  • Expressivity: It characterizes DeltaProduct expressivity, including group word problems, regular-language recognition, and products of RWKV-7 state-transition matrices.The supplementary sections also analyze a DeltaNet construction for dihedral groups.
  • Expressivity and Stability: The supplementary material discusses the trade-off between expressivity and stability in linear RNNs.This frames increased matrix expressivity as a property requiring separate stability consideration.
  • Experiments: Section C provides comprehensive experimental details and additional results.The supplementary material accompanies the main experiments with implementation and evaluation information.
  • Implementation: The authors provide code for the experiments at the DeltaProduct GitHub repository.The repository link is given as part of the supplementary material.

A Spectral Properties and Simplifications of Householder Product Matrices

Products of generalized Householder transformations have structured spectral behavior that depends on their direction vectors and β parameters. These products support increasingly expressive state-tracking constructions, including group-word and regular-language recognition.

  • Product simplifications: Identical direction vectors collapse the product to one effective generalized Householder transformation with a real spectrum.The resulting matrix is symmetric, so its eigenvalues are real.
  • Product simplifications: Orthogonal direction vectors make the factors commute, yielding a symmetric matrix with spectrum {1 −β1, . . . , 1 −βnh} ∪ {1}.The eigenvalue 1 has multiplicity n −nh; βj = 2 gives a block reflector.
  • Spectral behavior: Complex eigenvalues, and therefore rotations, arise if and only if both β1 > 1 and β2 > 1.If at least one βi ≤ 1, the corresponding transformations are restricted to scaling or reflection.
  • State-tracking expressivity: For any nh ≥ 1, DeltaProduct can solve symmetric-group word problems using one layer with nh = n−1, three layers with nh > 1, or four layers with nh = 1.Additional layers compensate when a single transition matrix cannot represent all permutations.
  • State-tracking expressivity: DeltaProduct also solves group word problems for groups embedded in orthogonal or special orthogonal groups when nh = n.The paper separately establishes modulo-counting and dihedral-group constructions, and relates these results to prior DeltaNet configurations.
  • State-tracking expressivity: Gated DeltaProduct recognizes any regular language in finitely many layers by simulating permutation-reset finite-state automata.Householder products represent permutations, while gating implements resets; the construction uses a cascade decomposition.

B.6 Stability vs. Expressivity of Linear RNNs

Linear RNN stability constrains expressivity: enforcing per-step spectral norms at most one excludes useful non-permutation matrices, while products of individually bounded matrices can still have spectral radius above one. DeltaProduct’s stability–expressivity analysis therefore examines when Householder-based transitions diverge or represent broader transformations.

  • Stability requires the spectral radius of every relevant transition product to remain at most one; otherwise the state norm diverges.
  • Enforcing ∥A_i∥≤1 guarantees stability through submultiplicativity but excludes boolean matrices whose spectral norm exceeds one.
  • The bounded-norm construction represents only permutations of up to n_h + 1 elements, limiting state-tracking expressivity.
  • RWKV-7 can represent copy matrices, but with practical c = 1, varying a_i makes its recurrence unstable for an infinite set of transition pairs.
  • A constructed product has spectral radius ρ(M) ≈1.23, so repeated application grows as ρ(M)^i and diverges.

C.2 Chomsky Hierarchy

The formal-language experiments test whether multiple Householder transformations improve length extrapolation across regular and context-free tasks. DeltaProduct with at least two Householder products achieves higher average accuracy than DeltaNet, especially on bracketed modular arithmetic.

  • The evaluation covers parity, modular arithmetic without brackets, and modular arithmetic with brackets across different Chomsky-hierarchy levels.
  • The bracketed modular-arithmetic task extends the unbracketed task with parentheses and nested expressions, using modulus m = 5.
  • DeltaProduct_nh with n_h ≥2 has better average accuracy than DeltaNet and other baselines on the formal-language tasks.
  • The improvement is strongest with eigenvalue range [−1, 1] and is most pronounced on modular arithmetic with brackets, the most challenging task.
  • Parameter-matched DeltaProduct training throughput is evaluated while reducing the SwiGLU inner dimension for n_h > 1.

C.3.3 Additional Benchmarks

Additional language-model benchmarks evaluate DeltaProduct against DeltaNet across standard lm-eval-harness tasks and multiple training setups. DeltaProduct achieves higher average accuracy in both reported setups.

  • DeltaProduct outperforms DeltaNet in average accuracy for both language-model training setups.
  • The benchmark includes language understanding, physical reasoning, situational understanding, commonsense reasoning, and reasoning categories.
  • The 4096-token comparison scales training from 19B to 55B tokens when parameter counts increase from 213M to 805M.
  • A separate comparison reports models trained with 2048-token context length, including DeltaProduct and Gated DeltaProduct.

C.3.4 Training behavior

DeltaProduct’s training remains stable as the number of Householder products increases. Higher n_h values also produce consistently lower training losses, despite relatively small absolute loss differences.

  • Training behavior remains stable as n_h increases across the reported DeltaProduct experiments.
  • Higher n_h values consistently yield lower training losses throughout training and convergence.
  • Small absolute loss differences between n_h values correspond to significant differences in length-extrapolation performance.

C.3.5 Additional results on Length Extrapolation

Additional experiments examine DeltaProduct's length-extrapolation behavior as n_h increases, both without changing other configuration parameters and under parameter-matched model scales. The plots cover loss, perplexity, and effective-rank behavior across long contexts.

  • Length extrapolation: Increasing n_h changes length-extrapolation behavior for (Gated) DeltaProduct without adjusting other model configuration parameters.Because increasing n_h also increases parameter count, the appendix separately evaluates parameter-matched models.
  • Parameter-matched scaling: Figures 17 and 18 compare per-token loss and perplexity for DeltaProduct models at three parameter-matched scales.Parameter equivalence follows the configurations listed in Table 6.
  • Length extrapolation: Figure 16 reports per-token loss and perplexity for (Gated) DeltaProduct models across context lengths up to 32,768.Per-token losses are smoothed with a window size of 300.
  • Effective-rank analysis: Effective-rank plots track four of eight heads across selected layers on CodeParrot sequences, marking new code sequences and the 4,096-token training context.Colored lines show effective rank per head over each sequence.

C.3.6 Additional Results on Scaling Behavior

Additional scaling experiments evaluate DeltaProduct under parameter-equivalent configurations formed by changing the number of heads. The results support DeltaProduct's superiority over DeltaNet, although larger n_h is not uniformly better under this alternative scaling strategy.

  • Scaling strategy: Alternative parameter-equivalent scaling still shows DeltaProduct outperforming DeltaNet on FineWeb perplexity.This setup reaches parameter equivalence by reducing the number of attention heads.
  • Scaling strategy: Higher n_h is not strictly better than fewer Householders when parameter equivalence is achieved by reducing the number of heads.This qualification applies to the alternative scaling analyzed in Figure 21.
  • Evaluation axes: Figure 21 reports final FineWeb perplexity and Lambada and lm-eval results across parameter-equivalent model scales.Models at each scale are trained with token counts reported in Table 4.
Loading 2502.10297v7…