Elamur Research⌕
☰
home / papers / 2023 / Resurrecting Recurrent Neural Networks for Long Sequences

Resurrecting Recurrent Neural Networks for Long Sequences

Paper · 2023 · Antonio Orvieto, Samuel L Smith, Albert Gu et al.

Summary

Classic RNNs are cheap at inference on long inputs, but they train slowly and suffer from vanishing or exploding gradients. Deep state-space models such as S4 do very well on the Long Range Arena (LRA) benchmark and also train in parallel. The authors (ETH Zurich and DeepMind) ask which ingredients actually explain this advantage. They start from a deep tanh RNN placed inside a fixed Norm–Recurrence–GLU–Skip block. They then ablate a chain of changes: removing the recurrent nonlinearity, rewriting the dense linear recurrence in complex diagonal form so that parallel scans become possible, parameterizing eigenvalues through a stable exponential map with initialization on a ring of the unit disk, and rescaling inputs with a normalization factor γ. The resulting block, the Linear Recurrent Unit (LRU), matches S4, S4D and S5 in accuracy and training efficiency on every LRA task, including PathX. The finding shows that continuous-time discretization and HiPPO-structured initialization are not essential. Ordinary signal-propagation reasoning is enough, which points toward simpler sequence architectures.

Key points

  • Removing the nonlinearity from the recurrence sharply raises LRA accuracy. Stacked linear RNN layers interleaved with nonlinear MLP blocks still express complex sequence-to-sequence maps.
  • The LRU defines eigenvalues as λ = exp(−exp(ν) + i·exp(θ)). This keeps them inside the unit circle, so training stays stable, and a diagonal recurrence allows fast parallel-scan training.
  • The eigenvalue distribution at initialization matters more than any specific deterministic scheme. Sampling eigenvalues evenly across a restricted region of the unit disk (a diagonalized Glorot analogue), combined with γ = (1 − |λ|²)^½ normalization, solves PathX. The authors say they are the first to show this without HiPPO-inspired initialization.
  • Analysis of S4D-Lin with Δ = 1e-3 and N = 128 shows eigenvalue magnitudes of about 0.9995 and phases within [0, π/8]. In this setting, the Δ factor on B acts as normalization, and decoupling the shared Δ parameter does not reduce performance.
  • Results are averaged over 3 seeds on sCIFAR, ListOps, Text, Retrieval, PathFinder and PathX.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓ETH ZurichZurich · Switzerland84 works · 9,181 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 works

Cite

Cite as Antonio Orvieto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu and Soham De. 2023. Resurrecting Recurrent Neural Networks for Long Sequences. arXiv:2303.06349.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2303.06349 · arXiv 2303.06349

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

References

88 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Arjovsky, A. Shah, and Y. Bengio. Unitary evolution recurrent neural networks. In International conference on machine learning. PMLR, 2016. find
  2. S. Axler. Linear algebra done right. Springer Science & Business Media, 1997. find
  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. find
  5. Y. Bengio, P. Simard, and P. Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 1994. find
  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. find
  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. find
  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. find
  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. find
  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. find
  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. find
  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. find
  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. find
  19. J. Ginibre. Statistical ensembles of complex, quaternion, and real matrices. Journal of Mathematical Physics, 1965. find
  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. find
  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. — [arXiv:2202.09729](https://arxiv.org/abs/2202.09729) find
  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. find
  23. A. Gu, K. Goel, and C. Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2021a. find
  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. find
  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. — [arXiv:2206.11893](https://arxiv.org/abs/2206.11893) find
  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. — [arXiv:2206.12037](https://arxiv.org/abs/2206.12037) find
  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. find
  28. A. Gupta, H. Mehta, and J. Berant. Simplifying and understanding state space models with diagonal linear rnns. arXiv preprint arXiv:2212.00768, 2022b. — [arXiv:2212.00768](https://arxiv.org/abs/2212.00768) find
  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. find
  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. — [arXiv:2209.12951](https://arxiv.org/abs/2209.12951) find
  31. K. Helfrich, D. Willmott, and Q. Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning. PMLR, 2018. find
  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. find
  34. S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 1997. find
  35. J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 1982. find
  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. find
  37. S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, 2015. find
  38. M. M. Islam and G. Bertasius. Long movie clip classification with state-space video models. In ECCV 2022. find
  39. R. G. Jacquot. Modern digital control systems. Routledge, 2019. find
  40. H. Jeffreys. The theory of probability. OUP Oxford, 1998. find
  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. find
  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. find
  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. find
  45. J. Kilian and H. T. Siegelmann. The dynamic universality of sigmoidal neural networks. Information and computation, 1996. find
  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. find
  48. M. Korda and I. Mezić. On convergence of extended dynamic mode decomposition to the koopman operator. Journal of Nonlinear Science, 2018. find
  49. M. Korda and I. Mezić. Koopman model predictive control of nonlinear dynamical systems. In The Koopman Operator in Systems and Control. Springer, 2020. find
  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. find
  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. find
  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. find
  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. find
  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. — [arXiv:2210.09298](https://arxiv.org/abs/2210.09298) find
  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. find
  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. find
  58. I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017. find
  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. find
  60. E. Martin and C. Cundy. Parallelizing linear recurrent neural nets over sequence length. arXiv preprint arXiv:1709.04057, 2017. find
  61. A. Mauroy and I. Mezić. Global stability analysis using the eigenfunctions of the koopman operator. IEEE Transactions on Automatic Control, 2016. find
  62. A. Mauroy, Y. Susuki, and I. Mezić. Koopman operator in systems and control. Springer, 2020. find
  63. W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. The bulletin of mathematical biophysics, 1943. find
  64. H. Mehta, A. Gupta, A. Cutkosky, and B. Neyshabur. Long range language modeling via gated state spaces. arXiv preprint arXiv:2206.13947, 2022. — [arXiv:2206.13947](https://arxiv.org/abs/2206.13947) find
  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. find
  66. T. Mikolov, M. Karafiát, L. Burget, J. Cernockỳ, and S. Khudanpur. Recurrent neural network based language model. In Interspeech. Makuhari, 2010. find
  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. find
  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. find
  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. find
  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. find
  73. P. J. Schmid. Dynamic mode decomposition of numerical and experimental data. Journal of fluid mechanics, 2010. find
  74. H. T. Siegelmann. Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 2012. find
  75. J. T. Smith, A. Warrington, and S. W. Linderman. Simplified state space layers for sequence modeling. arXiv preprint arXiv:2208.04933, 2022. — [arXiv:2208.04933](https://arxiv.org/abs/2208.04933) find
  76. J. J. Steil. Backpropagation-decorrelation: online recurrent learning with o (n) complexity. In 2004 IEEE international joint conference on neural networks. find
  77. A. Surana. Koopman operator based observer synthesis for control-affine nonlinear systems. In 2016 IEEE 55th Conference on Decision and Control (CDC). find
  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. find
  81. C. R. Vogel. Computational methods for inverse problems. SIAM, 2002. find
  82. S. Wang, Z. Li, and Q. Li. The effects of nonlinearity on approximation capacity of recurrent neural networks, 2022. find
  83. S. H. Weintraub. Jordan canonical form: theory and practice. Synthesis Lectures on Mathematics and Statistics, 2009. find
  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. find
  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. find
  86. Z. Zhinan. The jordan canonical form of a rational random matrix. Science Direct Working Paper, 2002. find
  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. — [arXiv:2205.08897](https://arxiv.org/abs/2205.08897) find
  88. Resurrecting Recurrent Neural Networks for Long Sequences Resurrecting Recurrent Neural Networks for Long Sequences Supplementary Materials Supplementary Materials A. Simplified Implementation of the Linear Recurrent Unit A. Simplified Implementation of the Linear Recurrent Unit find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/orvieto-2023-resurrecting-recurrent-neural-networks-long/