Skip to content

LRU

Introduced in Resurrecting Recurrent Neural Networks for Long Sequences (Orvieto et al., 2023).

The Linear Recurrent Unit (LRU) shows that the long-range performance of deep SSMs like S4 can be matched by a carefully designed linear RNN, without deriving the recurrence from a discretized continuous-time ODE. It isolates which ingredients of SSMs actually matter.

From RNN to LRU

Starting from a vanilla RNN, the authors apply a sequence of changes:

  1. Linear recurrence: remove the nonlinearity inside the recurrence (nonlinearities are kept between layers, in the MLP blocks).
  2. Complex diagonalization: diagonalize the recurrent matrix over \(\mathbb{C}\), so the recurrence is elementwise and can be computed with a parallel scan.
  3. Stable exponential parameterization: parameterize the eigenvalues directly in polar form so they always lie inside the unit disk.
  4. Normalization: scale the input so that the hidden state does not blow up for eigenvalues close to the unit circle.

The resulting layer is

\[ \begin{align} x_{t} &= \Lambda x_{t-1}+\gamma\odot Bu_{t}\\ y_{t} &= \mathrm{Re}(Cx_{t})+Du_{t} \end{align} \]

with \(\Lambda=\mathrm{diag}(\lambda_{1},\ldots,\lambda_{N})\) and

\[ \lambda_{j}=r_{j}e^{i\theta_{j}},\qquad r_{j}=\exp(-\exp(\nu_{j})),\qquad \theta_{j}=\exp(\varphi_{j}),\qquad \gamma_{j}=\sqrt{1-|\lambda_{j}|^{2}} \]

The double exponential guarantees \(0<r_{j}<1\) for any learned \(\nu_{j}\).

Initialization

The eigenvalues are initialized uniformly on a ring (annulus) in the complex plane, with \(r\in[r_{\min},r_{\max}]\) close to \(1\) and phase \(\theta\in[0,\theta_{\max}]\). Eigenvalue magnitudes close to \(1\) give long memory, and a small \(\theta_{\max}\) restricts the rotation frequencies for tasks with very long dependencies. The initialization results in Results - July 26 arrive at the same annulus scheme.

Selective LRU

The LRU is time-invariant. Making \(\lambda_{j}\) input-dependent gives a selective complex SSM, similar to GateLoop and the complex state of Mamba 3. Such a Selective LRU is used as a baseline in the oscillatory SSM project (see Results).