On the Role of Depth in the Expressivity of RNNs

Maude Lizaire; Michael Rizvi-Martel; Éric Dupuis; Guillaume Rabusseau

cs.LGApr 2, 2026

On the Role of Depth in the Expressivity of RNNs

Authors: Maude Lizaire, Michael Rizvi-Martel, Éric Dupuis, Guillaume Rabusseau

Organizations: Mila & DIRO, Université de Montréal · Independent · Mila & DIRO, CIFAR AI Chair, Université de Montréal

Abstract

The benefits of depth in feedforward neural networks are well known: composing multiple layers of linear transformations with nonlinear activations enables complex computations. While similar effects are expected in recurrent neural networks (RNNs), it remains unclear how depth interacts with recurrence to shape expressive power. Here, we formally show that depth increases RNNs' memory capacity efficiently with respect to the number of parameters, thus enhancing expressivity both by enabling more complex input transformations and improving the retention of past information. We broaden our analysis to 2RNNs, a generalization of RNNs with multiplicative interactions between inputs and hidden states. Unlike RNNs, which remain linear without nonlinear activations, 2RNNs perform polynomial transformations whose maximal degree grows with depth. We further show that multiplicative interactions cannot, in general, be replaced by layerwise nonlinearities. Finally, we validate these insights empirically on synthetic and real-world tasks.

Figures & tables

Figure 1: Theoretical insights overview of the effects of architectural choices on the expressivity of RNNs.

Figure 2: Unrolled deep recurrent architecture. Linear RNNs compute linear mappings of the inputs, while linear 2RNNs produce polynomial ones.

Figure 3: Information flow of RNN’s computation of $f_{p}$ for $n=2$ and $L=p$ .

Figure 4: Summary of theoretical results on linear RNNs: Adding layers increases memory capacity (Thm. 1 ), a single layer (for fixed number of units) offers more flexibility (Prop. 1 ), but raising depth rather than width (

n

) can be more parameter-efficient (Thm. 2 ).

Figure 5: State-tracking information flow. In 2RNNs, multiplicative interactions are performed by bilinear products, while in RNNs they need nonlinear activations

\sigma

, thus moving up a layer if applied only in depth.

Figure 6: Mean squared error (MSE) on test set for the copy task (lag 8) of linear RNNs with respect to hidden size (left), number of hidden units (center) and number of parameters (right) for varying depth.

Figure 7: Test mean squared error (MSE) for sinus (top) and copy-sinus (lag 4, bottom) of

tanh

activated RNNs in depth as a function of hidden size (left), number of units (center) and parameters (right) for varying depth.

Figure 8: Test MSE for the parity task versus hidden size

n

on RNNs with

tanh

activations in depth (left) or recurrence (center) for varying depth. Right panel compares activations by number of parameters.

Figure 9: Test bits-per-character (BPC) of RNNs (first), CPRNNs (second) versus hidden size

n

and S4 (third) versus features

H

across depths on tiny Shakespeare, fourth panel compares models by parameter count.

L	Retrieval	Images	ListOps	Pathfinder
2	0.9139	0.8581	0.5806	0.8534
3	0.9170	0.8765	0.6154	0.9328
6	0.9099	0.8980	0.6159	0.9619
8	0.9118	0.8913	0.6154	0.9673

Table 1: Test accuracies on Long Range Arena of S4 for varied depth with fixed parameter budget.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 10: Schematic representation of RNN’s computation of $f_{p}$ for $n=2$ and $L=p$ .

Figure 11: Left panel: Information flow through

\mathbf{h}^{(l)}_{t}

. Center panel: Schematization of computation

f_{p}

. Right panel: The information capacity needed for all the hidden states across the layers at some time

t

is obtained by considering the sum of information flows that enter the nodes.

$L$	Parameter	Retrieval	Images	ListOps	Pathfinder
6	$H$	256	512	256	256
6	$\#\mathrm{params}$	808k	3.6M	808k	1.3M
2	$H$	446	922	446	484
2	$\#\mathrm{params}$	808k	3.6M	808k	1.3M
3	$H$	364	745	364	385
3	$\#\mathrm{params}$	810k	3.6M	810k	1.3M

Appendix

Table 2: S4 parameters for Long Range Arena experiments: depth

L

, number of features

H

, and the resulting number of parameters. State dimension

N

is fixed (4 for Retrieval and ListOps, 64 for Images and Pathfinder). Rows corresponding to

L=6

reflect configurations from Gu et al. [2021] .

Recurrent Neural Networks

Recurrent neural networks process sequences by updating a persistent hidden state, enabling temporal modeling, memory, and streaming computation.

See all 303 papers

MinMax Recurrent Neural Cascades
May 7, 2026Alessandro RoncaRecurrent Neural Networks Neural Network Training Dynamics
IRIS-AI
Random Recursive Models
Sep 30, 2026Jama Hussein Mohamud, Mirco RavanelliEfficient Neural Network Inference LLM Reasoning
Mila – Quebec AI Institute · Université de Montréal · Concordia University
Why Are Linear RNNs More Parallelizable?
Mar 4, 2026William Merrill, Hongjian Jiang, Yanhong Li +2Circuit Complexity Recurrent Neural Networks
Allen Institute for AI · Rheinland-Pfälzische Technische Universität · Max-Planck Institute for Software Systems

May 7, 2026J/K move · Enter open · S save

MinMax Recurrent Neural Cascades

Alessandro Ronca

IRIS-AI

Recurrent Neural Networks Neural Network Training Dynamics Recurrent Language Models

Open paper AskPDF arXiv

We introduce MinMax Recurrent Neural Cascades (MinMax RNCs), a class of recurrent neural networks built from a novel form of recurrence over the MinMax algebra. We show that MinMax RNCs enjoy key properties that are difficult to obtain simultaneously: strong formal expressivity, efficient evaluation, stable dynamics, and non-vanishing state gradients. First, their formal expressivity corresponds to the regular languages, arguably the maximal expressivity for finite-memory systems. Second, in addition to evaluation in recurrent form, they also admit parallel-scan evaluation with logarithmic depth and linear work in the input length. Third, their states and activations are uniformly bounded for all sequence lengths. Fourth, their loss gradients exist almost everywhere and are uniformly bounded for all sequence lengths. Fifth, they do not exhibit vanishing state gradients: the gradient of a state with respect to a past state can retain norm one independently of the temporal distance between the states. Empirically, we find that these theoretical properties translate into strong practical performance. MinMax RNCs solve the considered synthetic tasks perfectly, generalise to long sequences, and outperform the recurrent baselines considered in our experiments. We also train a 112M-parameter MinMax RNC for next-token prediction, obtaining competitive performance for its size and providing initial evidence that MinMax recurrence can scale to real-world sequence-modelling tasks.

Abstract

Recurrent Neural Networks

Explore similar work

MinMax Recurrent Neural Cascades

Random Recursive Models

Why Are Linear RNNs More Parallelizable?