# Expressive power of recurrent neural networks

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2017.

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

- [Model Complexity of Deep Learning: A Survey](https://mlsanity.com/paper/2103.05127/) (2021)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Tensor-Train Density Estimation](https://mlsanity.com/paper/2108.00089/) (2021)
- [Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11729/) (2022)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Generative Learning of Continuous Data by Tensor Networks](https://mlsanity.com/paper/2310.20498/) (2023)
- [Towards Extremely Compact RNNs for Video Recognition with Fully Decomposed Hierarchical Tucker Structure](https://mlsanity.com/paper/2104.05758/) (2021)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Rank-R FNN: A Tensor-Based Learning Model for High-Order Data Classification](https://mlsanity.com/paper/2104.05048/) (2021)
- [Tensor-Train Recurrent Neural Networks for Interpretable Multi-Way Financial Forecasting](https://mlsanity.com/paper/2105.04983/) (2021)
- [Quantized Fourier and Polynomial Features for more Expressive Tensor Network Models](https://mlsanity.com/paper/2309.05436/) (2023)
- [On the Memory Mechanism of Tensor-Power Recurrent Models](https://mlsanity.com/paper/2103.01521/) (2021)
- [Language Modeling Using Tensor Trains](https://mlsanity.com/paper/2405.04590/) (2024)
- [What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement](https://mlsanity.com/paper/2303.11249/) (2023)
- [MetaTT: A Global Tensor-Train Adapter for Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2506.09105/) (2025)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Approximation Theory of Tree Tensor Networks: Tensorized Multivariate Functions](https://mlsanity.com/paper/2101.11932/) (2021)
- [A Tensor Decomposition Perspective on Second-order RNNs](https://mlsanity.com/paper/2406.05045/) (2024)
- [Low-Rank Tensor Decompositions for the Theory of Neural Networks](https://mlsanity.com/paper/2508.18408/) (2025)
- [Lower and Upper Bounds on the VC-Dimension of Tensor Network Models](https://mlsanity.com/paper/2106.11827/) (2021)
- [Group-invariant tensor train networks for supervised learning](https://mlsanity.com/paper/2206.15051/) (2022)
- [Error Analysis of Tensor-Train Cross Approximation](https://mlsanity.com/paper/2207.04327/) (2022)
- [conv_einsum: A Framework for Representation and Fast Evaluation of Multilinear Operations in Convolutional Tensorial Neural Networks](https://mlsanity.com/paper/2401.03384/) (2024)
- [Lecture Notes on Linear Neural Networks: A Tale of Optimization and Generalization in Deep Learning](https://mlsanity.com/paper/2408.13767/) (2024)
- [Reassessing Muon for Matrix Factorization](https://mlsanity.com/paper/2607.13246/) (2026)
- [The impact of allocation strategies in subset learning on the expressive power of neural networks](https://mlsanity.com/paper/2502.06300/) (2025)
- [On the Role of Depth in the Expressivity of RNNs](https://mlsanity.com/paper/2604.02201/) (2026)

## Abstract (arXiv)

Deep neural networks are surprisingly efficient at solving practical tasks, but the theory behind this phenomenon is only starting to catch up with the practice. Numerous works show that depth is the key to this efficiency. A certain class of deep convolutional networks -- namely those that correspond to the Hierarchical Tucker (HT) tensor decomposition -- has been proven to have exponentially higher expressive power than shallow networks. I.e. a shallow network of exponential width is required to realize the same score function as computed by the deep architecture. In this paper, we prove the expressive power theorem (an exponential lower bound on the width of the equivalent shallow network) for a class of recurrent neural networks -- ones that correspond to the Tensor Train (TT) decomposition. This means that even processing an image patch by patch with an RNN can be exponentially more efficient than a (shallow) convolutional network with one hidden layer. Using theoretical results on the relation between the tensor decompositions we compare expressive powers of the HT- and TT-Networks. We also implement the recurrent TT-Networks and provide numerical evidence of their expressivity.