Resurrecting Recurrent Neural Networks for Long Sequences

Antonio OrvietoSamuel L. SmithAlbert GuAnushan FernandoÇaglar GülçehreRazvan PascanuSoham De

article2023ICML466 citations

Introduces the Linear Recurrent Unit to demonstrate that recurrent neural networks, when designed with linear diagonal recurrences and proper signal propagation, can match both the training speed and long-range modeling accuracy of deep state-space models.

Listen

Modern sequence modeling increasingly demands architectures that can process very long contexts efficiently. While standard Recurrent Neural Networks (RNNs) offer fast, linear-time inference, they historically suffer from vanishing and exploding gradients and slow, sequential training. Attention-based Transformers resolve optimization bottlenecks but incur quadratic computational and memory costs, making them expensive on long sequences. Recent state-space models (SSMs) such as S4 overcome these challenges through continuous-time differential equations, specialized mathematical initializations, and discretization frameworks. The article investigates whether standard deep RNNs can match the high performance and computational efficiency of deep SSMs on long-sequence reasoning without relying on complex continuous-time theory.

The article evaluates a systematic redesign of vanilla deep RNNs, demonstrating that standard signal propagation, parameterization, and normalization techniques can recover SSM-level capability. The authors conducted rigorous empirical experiments across all six benchmarks of the Long Range Arena (LRA), which test long-range sequence understanding across tasks such as sequential image classification, mathematical list operations, text processing, document retrieval, and visual reasoning up to 16,000 steps. They also supported their empirical ablations with theoretical spectral analysis, random matrix theory, and dynamical systems theory, tracking both accuracy and wall-clock training speed.

The key findings reveal several insights for model design. First, eliminating nonlinearities from the recurrent state update (linear recurrences) significantly improves test accuracy over standard hyperbolic tangent and rectified linear activations, while non-recurrent feed-forward layers sufficiently preserve expressivity. Second, diagonalizing the recurrence with complex values enables associative parallel scans, delivering training speeds up to 29 times faster than standard RNNs and matching state-of-the-art SSM speeds. Third, using a stable exponential parameterization allows eigenvalues to be safely initialized close to the unit circle boundary, mitigating vanishing gradients and boosting accuracy on difficult tasks like Pathfinder to above 93%. Fourth, introducing a dedicated input-scaling normalization factor prevents forward-pass activation blow-up when eigenvalues approach magnitude one; combining this normalization with a restricted eigenvalue phase at initialization enables the model to reach 94.2% accuracy on PathX, the hardest LRA task.

These findings imply that the breakthrough performance of recent deep state-space models does not stem fundamentally from differential equation discretization or structured polynomial initializations. Instead, their success arises from linear recurrences, complex diagonal parameterizations, eigenvalue stability, and forward-pass normalization. By implementing these principles directly, the authors introduce the Linear Recurrent Unit (LRU), a simpler recurrent block that achieves equivalent accuracy and efficiency without the theoretical overhead or parameter sharing of continuous-time SSMs.

For future architectural development, engineering teams should consider adopting Linear Recurrent Units as streamlined, drop-in alternatives to attention mechanisms and SSMs for long-sequence tasks. Practitioners should leverage parallel associative scans for accelerated training and enforce stable exponential parameterization with normalization when long-range context is required. Although empirical confidence is high across the evaluated Long Range Arena benchmarks, future work should validate the scalability and generalization of LRUs on broader real-world applications, such as large-scale natural language generation, audio modeling, and production-scale time-series forecasting.

ETH Zurich Google computational efficiency inference parameterization Recurrent Neural Networks Deep Linear Recurrent Unit linear RNNs

arXiv: 2303.06349

Paper: Efficiently Modeling Long Sequences with Structured State Spaces, Albert Gu et al. (2022). Introduces the structured state-space model (S4) and sets the benchmark performance on the Long Range Arena that the source directly analyzes and seeks to match using simplified linear RNNs.
Paper: On the difficulty of training recurrent neural networks, Razvan Pascanu et al. (2012). Provides the foundational dynamical systems analysis of vanishing and exploding gradients in recurrent neural networks that motivates the source's signal propagation and initialization techniques.
Paper: A Simple Way to Initialize Recurrent Networks of Rectified Linear Units, Quoc V. Le et al. (2015). Demonstrates how recurrent weight initialization to the identity matrix allows linear and rectified activations to retain long-range memory, a core principle refined by the source's Linear Recurrent Unit.
Paper: Layer Normalization, Jimmy Lei Ba et al. (2016). Establishes normalization techniques across hidden features in recurrent networks, providing the basis for the forward-pass normalization strategies used in the source.
Paper: Long Short-Term Memory, Sepp Hochreiter et al. (1997). Presents the foundational gating and constant error carousel mechanism designed to overcome the long-sequence gradient failure modes discussed throughout the source.

Paper: Mamba: Linear-Time Sequence Modeling with Selective State Spaces, Albert Gu et al. (2023). Extends linear time-invariant state-space and recurrent formulations by introducing input-dependent selective state updates with hardware-efficient parallel scans.
Paper: Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality, Tri Dao et al. (2024). Unifies linear recurrent state-space models and attention through structured state space duality to achieve hardware-efficient training at scale.
Paper: Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling, Liliang Ren et al. (2025). Combines selective linear recurrent state-space layers with sliding window attention to enable infinite-context sequence modeling.
Paper: Test-time regression: a unifying framework for designing sequence models with associative memory, Ke Alexander Wang et al. (2025). Provides a unifying theoretical framework showing how linear state-space models and attention variants perform test-time regression for associative memory.
Paper: Dynamic Linear Attention, Xin Wang et al. (2026). Builds upon efficient linear recurrence and state-space architectures by implementing dynamic, information-aware memory state merging.

Cover for Resurrecting Recurrent Neural Networks for Long Sequences

Abstract

Recurrent Neural Networks (RNNs) offer fast inference on long sequences but are hard to optimize and slow to train. Deep state-space models (SSMs) have recently been shown to perform remarkably well on long sequence modeling tasks, and have the added benefits of fast parallelizable training and RNN-like fast inference. However, while SSMs are superficially similar to RNNs, there are important differences that make it unclear where their performance boost over RNNs comes from. In this paper, we show that careful design of deep RNNs using standard signal propagation arguments can recover the impressive performance of deep SSMs on long-range reasoning tasks, while also matching their training speed. To achieve this, we analyze and ablate a series of changes to standard RNNs including linearizing and diagonalizing the recurrence, using better parameterizations and initializations, and ensuring proper normalization of the forward pass. Our results provide new insights on the origins of the impressive performance of deep SSMs, while also introducing an RNN block called the Linear Recurrent Unit that matches both their performance on the Long Range Arena benchmark and their computational efficiency.

Topics

computational efficiency inference parameterization reasoning state space state space model recurrent networks

Keywords

Recurrent Neural Networks Deep Linear Recurrent Unit linear RNNs long-range dependencies sequence modelling deep SSMs LRA benchmark long-range reasoning tasks nonlinear RNNs

1 Introduction
2 Preliminaries
2.1 Recap of recurrent block structures
2.2 Experimental setup
3 Designing Performant Deep RNNs
3.1 Linear RNN layers are performant
3.2 Using complex diagonal recurrent matrices is efficient
3.2.1 Linear RNN eigendecomposition
3.2.2 Learning in the diagonalized space
3.3 Benefits of stable exponential parameterization
3.4 Additional considerations for long-range reasoning tasks
4 Insights on S4 and Variants
5 Conclusion
References
A Simplified Implementation of the Linear Recurrent Unit
B Related works
C Additional experimental results
C.1 Training speedups
C.2 Effect of stability and normalization
C.3 Expanded tables
D Detailed experimental setup
D.1 Architecture
D.2 General experimental details
D.3 Hyperparameters
D.4 Tasks
E Theoretical insights
E.1 Expressivity of linear RNN stacks
E.1.1 Spectral perspective
E.1.2 Insights from Koopman operator theory
E.2 Optimization of recurrent blocks
E.3 On alternatives to using complex numbers
F Proofs
F.1 Proof of Lemma
F.2 Proof of Proposition

Knowls

Knowl 1 — Linear Recurrent Unit Formulation
model/method
The Linear Recurrent Unit (LRU) is a recurrent neural network layer designed to process a sequence of $H$ -dimensional input vectors $(u_0, u_1, \dots, u_{L-1}) \in \mathbb{R}^{L \times H}$ into $H$ -dimensional output vectors $(y_0, y_1, \dots, y_{L-1}) \in \mathbb{R}^{L \times H}$ via an $N$ -dimensional complex hidden state $(x_0, x_1, \dots, x_{L-1}) \in \mathbb{C}^{L \times N}$ .

The recurrence is defined as:

$x_k = \Lambda x_{k-1} + \exp(\gamma^{\log}) \odot (B u_k)$

$y_k = \text{Re}(C x_k) + D u_k$

with initial hidden state $x_{-1} = 0 \in \mathbb{C}^N$ , where:
- $\Lambda = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_N) \in \mathbb{C}^{N \times N}$ is a complex diagonal transition matrix parameterized in polar/exponential coordinates to guarantee stability ( $|\lambda_j| < 1$ ):
$\lambda_j = \exp(-\exp(\nu_j^{\log}) + i \exp(\theta_j^{\log}))$

with learnable real parameters $\nu^{\log} \in \mathbb{R}^N$ and $\theta^{\log} \in \mathbb{R}^N$ .
- $B \in \mathbb{C}^{N \times H}$ is a complex input projection matrix.
- $\gamma^{\log} \in \mathbb{R}^N$ is a learnable real normalization parameter initialized element-wise as $\gamma_j^{\log} = \log\sqrt{1 - |\lambda_j|^2}$ to prevent forward-pass activation blow-up.
- $C \in \mathbb{C}^{H \times N}$ is a complex output projection matrix.
- $D \in \mathbb{R}^H$ is a real skip-connection weight vector that acts element-wise on $u_k$ .
- $\odot$ denotes the element-wise (Hadamard) product, and $\text{Re}(\cdot)$ takes the real part of a complex vector.
Knowl 2 — Forward-Pass Activation Variance and Normalization Factor in Linear Recurrent Systems
theoretical result
Let a linear recurrent system have a diagonal transition matrix $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_N) \in \mathbb{C}^{N \times N}$ with eigenvalues sampled uniformly on a ring in $\mathbb{C}$ between radii $0 \le r_{\min} < r_{\max} < 1$ . Under Glorot-initialized input projection matrix $B$ and constant or white-noise input sequence $(u_k)$ , the expected squared Euclidean norm of the hidden state $x_k = \sum_{j=0}^k \Lambda^j B u_{k-j}$ converges as $k \to \infty$ to:

$\mathbb{E}[\|x_\infty\|_2^2] = \frac{1}{r_{\max}^2 - r_{\min}^2} \log\left( \frac{1 - r_{\min}^2}{1 - r_{\max}^2} \right) \mathbb{E}[\|B u\|_2^2]$

When eigenvalues are initialized on an infinitely thin ring of radius $r = r_{\min} = r_{\max}$ (letting $\epsilon = r_{\max}^2 - r_{\min}^2 \to 0$ and $\rho = 1 - r_{\max}^2$ ), the variance amplification factor reduces to:

$\lim_{\epsilon \to 0} \frac{\mathbb{E}[\|x_\infty\|_2^2]}{\mathbb{E}[\|B u\|_2^2]} = \frac{1}{1 - r^2}$

For a single complex coordinate with eigenvalue $\lambda \in \mathbb{C}$ , the asymptotic gain under independent zero-mean input is $\mathbb{E}[|x_\infty|^2] / \mathbb{E}[|B u|^2] = \sum_{j=0}^\infty |\lambda|^{2j} = \frac{1}{1 - |\lambda|^2}$ . Initializing eigenvalues close to the unit disk ( $|\lambda| \approx 1$ ) causes hidden activations to blow up by a factor of $O((1 - |\lambda|^2)^{-1})$ , motivating the coordinate-wise normalization scaling factor $\gamma_j = \sqrt{1 - |\lambda_j|^2}$ on the input projection.
Knowl 3 — Uniform Annulus Initialization for Complex Diagonal Recurrent Matrices
theoretical result
To initialize a complex diagonal recurrent matrix $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_N) \in \mathbb{C}^{N \times N}$ uniformly on a ring in $\mathbb{C}$ bounded by inner radius $r_{\min}$ and outer radius $r_{\max}$ ( $0 \le r_{\min} \le r_{\max} \le 1$ ) with maximum phase angle $\theta_{\max} \in (0, 2\pi]$ , let $u_1, u_2 \sim \text{Uniform}(0, 1)$ be independent random variables. Define the parameters:

$\nu = -\frac{1}{2} \log\left( u_1 (r_{\max}^2 - r_{\min}^2) + r_{\min}^2 \right)$

$\theta = \theta_{\max} u_2$

Then the complex number $\lambda = \exp(-\nu + i\theta) = e^{-\nu}(\cos\theta + i\sin\theta)$ is uniformly distributed over the complex annulus segment with radii in $[r_{\min}, r_{\max}]$ and phase in $[0, \theta_{\max}]$ .

By Ginibre's Strong Circular Law, the empirical spectral measure of a real $N \times N$ matrix with i.i.d. Gaussian entries of mean 0 and variance $1/N$ (standard Glorot initialization) converges weakly almost surely as $N \to \infty$ to the uniform probability measure on the unit disk $\{z \in \mathbb{C} : |z| \le 1\}$ . Setting $r_{\min} = 0$ , $r_{\max} = 1$ , and $\theta_{\max} = 2\pi$ in this sampling procedure exactly matches the asymptotic eigenvalue spectrum of a Glorot-initialized dense linear RNN.

Knowl 4 — Long Range Arena Benchmark Performance of LRU and Deep SSMs

data/table

The table compares test classification accuracy (mean and standard error over 3 random seeds) across the six tasks of the Long Range Arena (LRA) benchmark for the Linear Recurrent Unit (LRU) against leading deep State-Space Models (S4, S4D, S5). All models use 6 residual layers.

Model	sCIFAR	ListOps	Text	Retrieval	Pathfinder	PathX
LRU	89.0 (0.1)	60.2 (0.8)	89.4 (0.1)	89.9 (0.1)	95.1 (0.1)	94.2 (0.4)
S4D (reproduced)	91.5 (0.2)	60.2 (0.3)	86.4 (0.0)	89.5 (0.0)	94.2 (0.3)	97.5 (0.0)
S5 (reproduced)	88.8 (0.1)	58.5 (0.3)	86.2 (0.1)	88.9 (0.0)	95.7 (0.1)	96.0 (0.1)
S4 (original)	91.1	59.6	86.8	90.9	94.2	96.4
S4D-LegS (original)	89.9	60.5	86.2	89.5	93.1	91.9
S5 (original)	90.1	62.2	89.3	91.4	95.3	98.6

The LRU matches the performance of deep continuous-time SSMs across all six tasks, including the 16k-length PathX task (which fails under standard RNN formulations), demonstrating that ODE discretization and structured HiPPO matrices are not required to achieve state-of-the-art long-sequence modeling.

Knowl 5 — Linear Recurrent Unit Layer Parallel Scan and Initialization Algorithm
algorithm
The algorithm below specifies the initialization and parallel associative scan execution for a Linear Recurrent Unit (LRU) layer with state dimension $N$ , model feature dimension $H$ , and sequence length $L$ .
Input: Input sequence matrix $U \in \mathbb{R}^{L \times H}$ , state dimension $N$ , feature dimension $H$ , annulus radii $r_{\min}, r_{\max} \in [0, 1]$ , maximum phase $\theta_{\max} \in (0, 2\pi]$
Output: Output sequence matrix $Y \in \mathbb{R}^{L \times H}$
function InitializeParameters( $N$ , $H$ , $r_{\min}$ , $r_{\max}$ , $\theta_{\max}$ )
    Sample $u_1, u_2 \sim \text{Uniform}(0, 1)^N$
     $\nu^{\log} \leftarrow \log\left( -0.5 \cdot \log(u_1 \cdot (r_{\max}^2 - r_{\min}^2) + r_{\min}^2) \right)$
     $\theta^{\log} \leftarrow \log(\theta_{\max} \cdot u_2)$

    Sample $B_{\text{re}}, B_{\text{im}} \sim \mathcal{N}(0, 1/(2H))^{N \times H}$
    Sample $C_{\text{re}}, C_{\text{im}} \sim \mathcal{N}(0, 1/N)^{H \times N}$
    Sample $D \sim \mathcal{N}(0, 1)^H$

     $\lambda \leftarrow \exp(-\exp(\nu^{\log}) + i \exp(\theta^{\log}))$
     $\gamma^{\log} \leftarrow \log\left( \sqrt{1 - |\lambda|^2} \right)$
    return $\nu^{\log}, \theta^{\log}, B_{\text{re}}, B_{\text{im}}, C_{\text{re}}, C_{\text{im}}, D, \gamma^{\log}$
end function
function AssociativeBinaryOp( $(a_i, b_i), (a_j, b_j)$ )
    return $(a_j \odot a_i, a_j \odot b_i + b_j)$
end function
function ForwardPass( $U$ , parameters)
     $\lambda \leftarrow \exp(-\exp(\nu^{\log}) + i \exp(\theta^{\log})) \in \mathbb{C}^N$
     $B_{\text{norm}} \leftarrow (B_{\text{re}} + i B_{\text{im}}) \odot \exp(\gamma^{\log}) \in \mathbb{C}^{N \times H}$
     $C \leftarrow C_{\text{re}} + i C_{\text{im}} \in \mathbb{C}^{H \times N}$

    for $k = 0$ to $L-1$ in parallel do
         $\Lambda_k \leftarrow \lambda$
         $v_k \leftarrow B_{\text{norm}} u_k \in \mathbb{C}^N$
    end for

     $(A_{\text{scan}}, X) \leftarrow \text{ParallelAssociativeScan}(\text{AssociativeBinaryOp}, ((\Lambda_0, v_0), \dots, (\Lambda_{L-1}, v_{L-1})))$

    for $k = 0$ to $L-1$ in parallel do
         $y_k \leftarrow \text{Re}(C x_k) + D \odot u_k \in \mathbb{R}^H$
    end for
    return $Y = [y_0, y_1, \dots, y_{L-1}]^T$
end function

Knowl 6 — Ablation of Parameterization and Normalization Components from Vanilla RNN to LRU

data/table

The table traces the progressive performance impact on Long Range Arena tasks when transitioning from a standard dense recurrent unit to the Linear Recurrent Unit (LRU). Test accuracy (mean and standard error across 3 seeds) is reported.

Recurrent Configuration	sCIFAR	ListOps	Retrieval	Pathfinder	PathX
Dense RNN-Tanh	69.9 (0.3)	43.9 (0.1)	88.9 (0.2)	Failed	Failed
Dense Linear RNN	72.2 (0.2)	50.4 (0.2)	89.1 (0.1)	Failed	Failed
Complex Diagonal ( $[\text{Re}, \text{Im}]$ )	86.5 (0.1)	58.8 (0.3)	87.8 (0.5)	Failed	Failed
Complex Diagonal (Exp Param)	85.4 (0.7)	60.5 (0.3)	89.4 (0.1)	65.4 (9.0)	Failed
Stable Exp Param	87.2 (0.4)	59.4 (0.3)	89.1 (0.2)	93.5 (0.5)	Failed
Stable Exp + Ring Init	88.1 (0.0)	59.4 (0.3)	90.1 (0.1)	94.4 (0.3)	Failed
LRU (+ $\gamma$ Normalization)	89.0 (0.1)	60.2 (0.8)	89.9 (0.1)	95.1 (0.1)	94.2 (0.4)

Key takeaways:

Removing the recurrent nonlinearity in dense RNNs improves performance across all solvable tasks.
Diagonalization in $\mathbb{C}$ drastically improves accuracy on sCIFAR and ListOps while maintaining linear equivalence at initialization.
Polar/exponential parameterization decouples magnitude and phase gradients, allowing Adam to optimize Pathfinder above chance.
Stable parameterization ( $\|\lambda\| < 1$ enforcement) and ring initialization ( $r_{\min} \approx 0.9$ ) prevent vanishing gradients over long horizons.
Forward activation $\gamma$ -normalization, paired with restricted initial phase, resolves the 16k-token PathX task.

Knowl 7 — Deep LRU Network Architecture
model/method
The deep architecture incorporating the Linear Recurrent Unit (LRU) consists of:
1. Input Linear Encoder: Maps input tokens or values into model dimension $H$ .
2. Residual Stack: A sequence of 6 residual blocks. Each block follows a Pre-Batch Normalization design with an identity skip connection:
  - Residual branch: $\text{Input} \to \text{Batch Normalization} \to \text{LRU Recurrence Core} \to \text{Position-wise Feedforward Mixing Layer} \to \text{Dropout}$ .
  - The mixing layer uses a Gated Linear Unit (GLU) activation: $\text{GLU}(z) = (z W_1 + b_1) \odot \sigma(z W_2 + b_2)$ .
  - Bidirectional recurrence is applied on 2D image sequence tasks (Pathfinder, PathX) by running forward and backward LRU layers and concatenating states; unidirectional recurrence is used on 1D sequence tasks.
3. Output Layer: Temporal pooling followed by a linear classification head mapping to the target classes.
Knowl 8 — Spectral Leakage of Pointwise Nonlinearities in Linear Recurrent Stacks
theoretical result
Let $u: \mathbb{R} \to \mathbb{R}$ be a continuous-time signal. Let $P_i = [p_i - L_i, p_i + L_i]$ denote the $i$ -th disjoint interval where $u(t) > 0$ . The Fourier transform of $\text{ReLU}(u(t))$ is given by the convolution in the frequency domain:

$\mathcal{F}_{\text{ReLU}(u)}(\omega) = \mathcal{F}_u(\omega) \star \left[ \sum_i 2 L_i e^{-i \omega p_i} \text{sinc}(\omega L_i) \right]$

where $\mathcal{F}_u$ is the Fourier transform of $u$ , $\star$ denotes continuous convolution, and $\text{sinc}(x) = \sin(x)/x$ .

While a linear RNN layer can only amplify, attenuate, or shift existing input frequencies (acting as a linear operator $Y(\omega) = H(\omega)U(\omega)$ ), applying a pointwise nonlinear activation like ReLU after the recurrent layer convolves the spectrum with a sum of sinc functions. This transfers signal energy to new, higher frequency components (spectral leakage), allowing deep stacks of linear RNN layers interleaved with position-wise nonlinear feedforward MLPs to approximate complex nonlinear dynamical sequence-to-sequence maps.

Knowl 9 — Training Throughput of LRU Compared to Tanh RNN and SSMs

data/table

The table reports training throughput in steps per second on an NVIDIA A100 GPU across tasks in the Long Range Arena benchmark, comparing the Linear Recurrent Unit (LRU) to a sequential dense Tanh RNN and diagonal SSM baselines (S4D, S5).

Model	sCIFAR	ListOps	Text	Retrieval	Pathfinder	PathX
Tanh RNN	2.0	1.1	0.5	0.5	2.1	0.14
LRU	15.9 (8.0x)	2.1 (1.9x)	14.7 (29.4x)	5.7 (11.4x)	15.5 (7.4x)	2.4 (17.1x)
S4D	13.5	2.2	10.6	3.0	24.5	2.6
S5	15.9	2.2	14.4	5.7	15.6	2.3

By diagonalizing the recurrence and computing the hidden states via parallel associative scan, the LRU eliminates the sequential step bottleneck of standard nonlinear RNNs, achieving 7.4x to 29.4x speedups over Tanh RNNs and matching the training speed of specialized State-Space Models.

Knowl 10 — Initial Phase Restriction for Ultra-Long Sequence Modeling
model/method
For ultra-long sequences such as PathX ( $L = 16\text{k}$ tokens), initializing the eigenvalue phase angles uniformly over $\theta \in [0, 2\pi]$ causes hidden state components to exhibit dense oscillations across the temporal history. This biases the network toward capturing spurious high-frequency local patterns from which first-order optimization fails to recover, leading to convergence at chance accuracy.

To solve this, the eigenvalue phase is restricted at initialization to a narrow interval around zero, $\theta \in [0, \pi/10]$ , while the magnitude parameters remain close to 1 ( $r_{\min} = 0.999, r_{\max} = 0.9999$ ). To facilitate gradient optimization over small positive angles, the phase is parameterized logarithmically as $\theta = \exp(\theta^{\log})$ with trainable real parameter $\theta^{\log} \in \mathbb{R}^N$ . Combining restricted phase initialization with $\gamma$ -normalization enables the LRU to achieve 94.2% test accuracy on PathX.

Coverage note — None was omitted; all key theoretical derivations, architectural components, initialization and normalization schemes, and empirical benchmark comparisons from the paper are covered.

References

1.M. Arjovsky, A. Shah, and Y. Bengio. Unitary evolution recurrent neural networks. In International conference on machine learning. PMLR, 2016.
2.S. Axler. Linear algebra done right. Springer Science & Business Media, 1997.
3.J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
4.S. Bai, J. Z. Kolter, and V. Koltun. An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271, 2018.
5.Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 1994.
6.N. Bordin, C. Dallago, M. Heinzinger, S. Kim, M. Littmann, C. Rauer, M. Steinegger, B. Rost, and C. Orengo. Novel machine learning approaches revolutionize protein knowledge. Trends in Biochemical Sciences, 2022.
7.J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, et al. JAX: composable transformations of python+ numpy programs, 2018.
8.T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, S. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005.14165, 2020.
9.K. Cho, B. Van Merriënboer, D. Bahdanau, and Y. Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409.1259, 2014a.
10.K. Cho, B. Van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078, 2014b.
11.S. Chung and H. Siegelmann. Turing completeness of bounded-precision recurrent neural networks. Advances in Neural Information Processing Systems, 2021.
12.T. Dao, D. Y. Fu, S. Ermon, A. Rudra, and C. Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. arXiv preprint arXiv:2205.14135, 2022a.
13.T. Dao, D. Y. Fu, K. K. Saab, A. W. Thomas, A. Rudra, and C. Ré. Hungry hungry hippos: Towards language modeling with state space models. arXiv preprint arXiv:2212.14052, 2022b.
14.Y. N. Dauphin, A. Fan, M. Auli, and D. Grangier. Language modeling with gated convolutional networks. In International conference on machine learning. PMLR, 2017.
15.S. De and S. Smith. Batch normalization biases residual blocks towards the identity function in deep networks. Advances in Neural Information Processing Systems, 2020.
16.A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, N. Houlsby, S. Gelly, X. Zhang, and J. Uszkoreit. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
17.J. L. Elman. Finding structure in time. Cognitive science, 1990.
18.N. B. Erichson, O. Azencot, A. Queiruga, L. Hodgkinson, and M. W. Mahoney. Lipschitz recurrent neural networks. In International Conference on Learning Representations, 2021.
19.J. Ginibre. Statistical ensembles of complex, quaternion, and real matrices. Journal of Mathematical Physics, 1965.
20.X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 2010.
21.K. Goel, A. Gu, C. Donahue, and C. Ré. It’s raw! audio generation with state-space models. arXiv preprint arXiv:2202.09729, 2022.
22.A. Gu, T. Dao, S. Ermon, A. Rudra, and C. Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances in Neural Information Processing Systems, 2020.
23.A. Gu, K. Goel, and C. Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2021a.
24.A. Gu, I. Johnson, K. Goel, K. Saab, T. Dao, A. Rudra, and C. Ré. Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances in neural information processing systems, 2021b.
25.A. Gu, A. Gupta, K. Goel, and C. Ré. On the parameterization and initialization of diagonal state space models. arXiv preprint arXiv:2206.11893, 2022a.
26.A. Gu, I. Johnson, A. Timalsina, A. Rudra, and C. Ré. How to train your hippo: State space models with generalized orthogonal basis projections. arXiv preprint arXiv:2206.12037, 2022b.
27.A. Gupta, A. Gu, and J. Berant. Diagonal state spaces are as effective as structured state spaces. In Advances in Neural Information Processing Systems, 2022a.
28.A. Gupta, H. Mehta, and J. Berant. Simplifying and understanding state space models with diagonal linear rnns. arXiv preprint arXiv:2212.00768, 2022b.
29.R. Hasani, M. Lechner, A. Amini, D. Rus, and R. Grosu. Liquid time-constant networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
30.R. Hasani, M. Lechner, T.-H. Wang, M. Chahine, A. Amini, and D. Rus. Liquid structural state-space models. arXiv preprint arXiv:2209.12951, 2022.
31.K. Helfrich, D. Willmott, and Q. Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning. PMLR, 2018.
32.T. Hennigan, T. Cai, T. Norman, and I. Babuschkin. Haiku: Sonnet for JAX, 2020. URL http://github.com/deepmind/dm-haiku.
33.S. Hochreiter. Untersuchungen zu dynamischen neuronales netzen. Diploma thesis, Institut f’’ur Informatik, Technische Universit’’at M’’unchen, 1991.
34.S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 1997.
35.J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 1982.
36.S. L. Hyland and G. Rätsch. Learning unitary operators with help from u (n). In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
37.S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, 2015.
38.M. M. Islam and G. Bertasius. Long movie clip classification with state-space video models. In ECCV 2022. Springer, 2022.
39.R. G. Jacquot. Modern digital control systems. Routledge, 2019.
40.H. Jeffreys. The theory of probability. OUP Oxford, 1998.
41.L. Jing, Y. Shen, T. Dubcek, J. Peurifoy, S. Skirlo, Y. LeCun, M. Tegmark, and M. Soljaćić. Tunable efficient unitary neural networks (eunn) and their application to rnns. In International Conference on Machine Learning. PMLR, 2017.
42.J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 2021.
43.E. Kaiser, J. N. Kutz, and S. L. Brunton. Data-driven discovery of koopman eigenfunctions for control. Machine Learning: Science and Technology, 2021.
44.N. Kalchbrenner, L. Espeholt, K. Simonyan, A. v. d. Oord, A. Graves, and K. Kavukcuoglu. Neural machine translation in linear time. arXiv preprint arXiv:1610.10099, 2016.
45.J. Kilian and H. T. Siegelmann. The dynamic universality of sigmoidal neural networks. Information and computation, 1996.
46.D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
47.B. O. Koopman and J. v. Neumann. Dynamical systems of continuous spectra. Proceedings of the National Academy of Sciences, 1932.
48.M. Korda and I. Mezić. On convergence of extended dynamic mode decomposition to the koopman operator. Journal of Nonlinear Science, 2018.
49.M. Korda and I. Mezić. Koopman model predictive control of nonlinear dynamical systems. In The Koopman Operator in Systems and Control. Springer, 2020.
50.V. R. Kostic, P. Novelli, A. Maurer, C. Ciliberto, L. Rosasco, and massimiliano pontil. Learning dynamical systems via koopman operator regression in reproducing kernel hilbert spaces. In Advances in Neural Information Processing Systems, 2022.
51.J. N. Kutz, S. L. Brunton, B. W. Brunton, and J. L. Proctor. Dynamic mode decomposition: data-driven modeling of complex systems. SIAM, 2016.
52.Q. V. Le, N. Jaitly, and G. E. Hinton. A simple way to initialize recurrent networks of rectified linear units. arXiv preprint arXiv:1504.00941, 2015.
53.J. Lee-Thorp, J. Ainslie, I. Eckstein, and S. Ontanon. Fnet: Mixing tokens with fourier transforms. arXiv preprint arXiv:2105.03824, 2021.
54.M. Lezcano-Casado and D. Martınez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference on Machine Learning. PMLR, 2019.
55.Y. Li, T. Cai, Y. Zhang, D. Chen, and D. Dey. What makes convolutional models great on long sequence modeling? arXiv preprint arXiv:2210.09298, 2022a.
56.Z. Li, J. Han, E. Weinan, and Q. Li. Approximation and optimization theory for linear continuous-time recurrent neural networks. J. Mach. Learn. Res., 2022b.
57.L. Liu, H. Wang, J. Lin, R. Socher, and C. Xiong. Mkd: a multi-task knowledge distillation approach for pretrained language models. arXiv preprint arXiv:1911.03588, 2019.
58.I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017.
59.X. Ma, C. Zhou, X. Kong, J. He, L. Gui, G. Neubig, J. May, and L. Zettlemoyer. Mega: moving average equipped gated attention. arXiv preprint arXiv:2209.10655, 2022.
60.E. Martin and C. Cundy. Parallelizing linear recurrent neural nets over sequence length. arXiv preprint arXiv:1709.04057, 2017.
61.A. Mauroy and I. Mezić. Global stability analysis using the eigenfunctions of the koopman operator. IEEE Transactions on Automatic Control, 2016.
62.A. Mauroy, Y. Susuki, and I. Mezić. Koopman operator in systems and control. Springer, 2020.
63.W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 1943.
64.H. Mehta, A. Gupta, A. Cutkosky, and B. Neyshabur. Long range language modeling via gated state spaces. arXiv preprint arXiv:2206.13947, 2022.
65.Z. Mhammedi, A. Hellicar, A. Rahman, and J. Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In International Conference on Machine Learning. PMLR, 2017.
66.T. Mikolov, M. Karafiát, L. Burget, J. Cernock`y, and S. Khudanpur. Recurrent neural network based language model. In Interspeech. Makuhari, 2010.
67.R. Nallapati, B. Zhou, C. Gulcehre, B. Xiang, et al. Abstractive text summarization using sequence-to-sequence rnns and beyond. arXiv preprint arXiv:1602.06023, 2016.
68.E. Nguyen, K. Goel, A. Gu, G. Downs, P. Shah, T. Dao, S. Baccus, and C. Ré. S4nd: Modeling images and videos as multidimensional signals with state spaces. In Advances in Neural Information Processing Systems, 2022.
69.A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, and K. Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499, 2016.
70.R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning. PMLR, 2013.
71.J. L. Proctor, S. L. Brunton, and J. N. Kutz. Generalizing koopman theory to allow for inputs and control. SIAM Journal on Applied Dynamical Systems, 2018.
72.D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. Technical report, California Univ San Diego La Jolla Inst for Cognitive Science, 1985.
73.P. J. Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of fluid mechanics, 2010.
74.H. T. Siegelmann. Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 2012.
75.J. T. Smith, A. Warrington, and S. W. Linderman. Simplified state space layers for sequence modeling. arXiv preprint arXiv:2208.04933, 2022.
76.J. J. Steil. Backpropagation-decorrelation: online recurrent learning with o (n) complexity. In 2004 IEEE international joint conference on neural networks. IEEE, 2004.
77.A. Surana. Koopman operator based observer synthesis for control-affine nonlinear systems. In 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016.
78.Y. Tay, M. Dehghani, S. Abnar, Y. Shen, D. Bahri, P. Pham, J. Rao, L. Yang, S. Ruder, and D. Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020.
79.A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 2017.
80.A. Voelker, I. Kajić, and C. Eliasmith. Legendre memory units: Continuous-time representation in recurrent neural networks. Advances in neural information processing systems, 2019.
81.C. R. Vogel. Computational methods for inverse problems. SIAM, 2002.
82.S. Wang, Z. Li, and Q. Li. The effects of nonlinearity on approximation capacity of recurrent neural networks, 2022.
83.S. H. Weintraub. Jordan canonical form: theory and practice. Synthesis Lectures on Mathematics and Statistics, 2009.
84.M. O. Williams, I. G. Kevrekidis, and C. W. Rowley. A data–driven approximation of the koopman operator: Extending dynamic mode decomposition. Journal of Nonlinear Science, 2015.
85.S. Wisdom, T. Powers, J. Hershey, J. Le Roux, and L. Atlas. Full-capacity unitary recurrent neural networks. Advances in neural information processing systems, 2016.
86.Z. Zhinan. The jordan canonical form of a rational random matrix. Science Direct Working Paper, 2002.
87.T. Zhou, Z. Ma, Q. Wen, L. Sun, T. Yao, R. Jin, et al. Film: Frequency improved legendre memory model for long-term time series forecasting. arXiv preprint arXiv:2205.08897, 2022.

Citation

MLA

Orvieto, A., et al. “Resurrecting Recurrent Neural Networks for Long Sequences”. arXiv, 2023, http://arxiv.org/abs/2303.06349v1.

APA

Orvieto, A., Smith, S. L., Gu, A., Fernando, A., Gulcehre, C., Pascanu, R., & De, S. (2023). Resurrecting Recurrent Neural Networks for Long Sequences. arXiv. http://arxiv.org/abs/2303.06349v1

Chicago

Orvieto, A., S. L. Smith, A. Gu, et al. 2023. “Resurrecting Recurrent Neural Networks for Long Sequences”. arXiv. http://arxiv.org/abs/2303.06349v1.

Harvard

Orvieto, A. et al. (2023) “Resurrecting Recurrent Neural Networks for Long Sequences”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2303.06349v1.

Vancouver

1. Orvieto A, Smith SL, Gu A, Fernando A, Gulcehre C, Pascanu R, De S (2023) Resurrecting Recurrent Neural Networks for Long Sequences. arXiv

BibTeX

@article{orvieto2023resurrecting,
  title = {Resurrecting Recurrent Neural Networks for Long Sequences},
  author = {Orvieto, Antonio and Smith, Samuel L and Gu, Albert and Fernando, Anushan and Gulcehre, Caglar and Pascanu, Razvan and De, Soham},
  year = {2023},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2303.06349v1},
  eprint = {2303.06349}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Resurrecting Recurrent Neural Networks for Long Sequences

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Linear Recurrent Unit Formulation

Knowl 2 — Forward-Pass Activation Variance and Normalization Factor in Linear Recurrent Systems

Knowl 3 — Uniform Annulus Initialization for Complex Diagonal Recurrent Matrices

Knowl 4 — Long Range Arena Benchmark Performance of LRU and Deep SSMs

Knowl 5 — Linear Recurrent Unit Layer Parallel Scan and Initialization Algorithm

Knowl 6 — Ablation of Parameterization and Normalization Components from Vanilla RNN to LRU

Knowl 7 — Deep LRU Network Architecture

Knowl 8 — Spectral Leakage of Pointwise Nonlinearities in Linear Recurrent Stacks

Knowl 9 — Training Throughput of LRU Compared to Tanh RNN and SSMs

Knowl 10 — Initial Phase Restriction for Ultra-Long Sequence Modeling

References

Citation

BibTeX

Access the Paper