# A Tensor Decomposition Perspective on Second-order RNNs

arXiv: https://arxiv.org/abs/2406.05045 · HTML: https://mlsanity.com/paper/2406.05045/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 63 references that are in the map.
- First posted on arXiv 7 Jun 2024.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [HiPPO: Recurrent Memory with Optimal Polynomial Projections](https://mlsanity.com/paper/2008.07669/) (2020)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [On the Expressive Power of Deep Learning: A Tensor Analysis](https://mlsanity.com/paper/1509.05009/) (2015)
- [On the Expressive Power of Deep Polynomial Neural Networks](https://mlsanity.com/paper/1905.12207/) (2019)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Tensor-Train Recurrent Neural Networks for Video Classification](https://mlsanity.com/paper/1707.01786/) (2017)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [Inductive Bias of Deep Convolutional Networks through Pooling Geometry](https://mlsanity.com/paper/1605.06743/) (2016)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Learning Compact Recurrent Neural Networks with Block-Term Tensor Decomposition](https://mlsanity.com/paper/1712.05134/) (2017)
- [Convolutional Rectifier Networks as Generalized Tensor Decompositions](https://mlsanity.com/paper/1603.00162/) (2016)
- [Expressive power of recurrent neural networks](https://mlsanity.com/paper/1711.00811/) (2017)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Multiplicative LSTM for sequence modelling](https://mlsanity.com/paper/1609.07959/) (2016)
- [Scalable Interpretability via Polynomials](https://mlsanity.com/paper/2205.14108/) (2022)
- [On Multiplicative Integration with Recurrent Neural Networks](https://mlsanity.com/paper/1606.06630/) (2016)
- [On the Long-Term Memory of Deep Recurrent Networks](https://mlsanity.com/paper/1710.09431/) (2017)
- [Kronecker CP Decomposition with Fast Multiplication for Compressing RNNs](https://mlsanity.com/paper/2008.09342/) (2020)
- [Finite Sample Identification of Bilinear Dynamical Systems](https://mlsanity.com/paper/2208.13915/) (2022)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Multilinear Operator Networks](https://mlsanity.com/paper/2401.17992/) (2024)
- [Tensor Decomposition for Compressing Recurrent Neural Network](https://mlsanity.com/paper/1802.10410/) (2018)
- [Generalized Tensor Models for Recurrent Neural Networks](https://mlsanity.com/paper/1901.10801/) (2019)
- [Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning](https://mlsanity.com/paper/2010.10029/) (2020)
- [Language Modeling Using Tensor Trains](https://mlsanity.com/paper/2405.04590/) (2024)

## Built on by (most cited first, 3 of 3)

- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Low-Rank Tensor Decompositions for the Theory of Neural Networks](https://mlsanity.com/paper/2508.18408/) (2025)
- [On the Role of Depth in the Expressivity of RNNs](https://mlsanity.com/paper/2604.02201/) (2026)

## Abstract (arXiv)

Second-order Recurrent Neural Networks (2RNNs) extend RNNs by leveraging second-order interactions for sequence modelling. These models are provably more expressive than their first-order counterparts and have connections to well-studied models from formal language theory. However, their large parameter tensor makes computations intractable. To circumvent this issue, one approach known as MIRNN consists in limiting the type of interactions used by the model. Another is to leverage tensor decomposition to diminish the parameter count. In this work, we study the model resulting from parameterizing 2RNNs using the CP decomposition, which we call CPRNN. Intuitively, the rank of the decomposition should reduce expressivity. We analyze how rank and hidden size affect model capacity and show the relationships between RNNs, 2RNNs, MIRNNs, and CPRNNs based on these parameters. We support these results empirically with experiments on the Penn Treebank dataset which demonstrate that, with a fixed parameter budget, CPRNNs outperforms RNNs, 2RNNs, and MIRNNs with the right choice of rank and hidden size.