Depth in Recurrent Networks: Beyond the Composition of Nonlinearities

The conventional wisdom regarding depth in neural networks is firmly rooted in the feedforward setting. In multilayer perceptrons, depth enables complexity through the composition of nonlinear transformations; each layer applies a nonlinear activation to a linear projection, and stacking these layers allows the network to approximate intricate functions. Remove the nonlinearities, and a deep feedforward network collapses into a single linear map, rendering the additional layers structurally redundant. This intuition has long been assumed to extend, at least partially, to recurrent neural networks (RNNs). However, the paper On the Role of Depth in the Expressivity of RNNs by Lizaire, Rizvi-Martel, Dupuis, and Rabusseau demonstrates that this assumption obscures a more nuanced reality. In recurrent architectures, depth interacts with recurrence in subtle ways that can enhance expressivity even in the complete absence of nonlinear activation functions.

Memory Capacity Through Depth Alone

The first major insight of the paper concerns linear RNNs, architectures often dismissed as theoretically uninteresting precisely because linear transformations compose into further linear transformations. The authors prove, in Theorem 1, that deep linear RNNs are strictly more expressive than their shallow counterparts with respect to memory capacity. This result is initially counterintuitive. In feedforward networks, depth without nonlinearity provides no benefit; in RNNs, depth enables the network to retain and access information from farther back in the sequence history.

The mechanism underlying this phenomenon relates to how depth affects the effective order of the recurrence. A shallow linear RNN maintains a hidden state that evolves according to a first order linear dynamical system. When multiple such layers are stacked, the resulting computation effectively implements higher order recurrences across the depth of the network. This allows the model to maintain linearly independent memory modes that would require exponentially larger hidden dimensions in a shallow architecture. Theorem 2 formalizes this parameter efficiency: to achieve equivalent memory capacity, increasing depth requires fewer parameters than increasing the hidden size of a shallow network.

This finding carries immediate implications for the current generation of sequence models, particularly State Space Models (SSMs) such as S4. These architectures often employ deep stacks of linear recurrences to achieve competitive performance while maintaining hardware efficient parallel scans. The theoretical analysis suggests that the depth in these models is not merely an architectural convenience but a fundamental requirement for their ability to model long range dependencies. The memory capacity gains are not merely empirical observations but structural properties of deep linear recurrences.

Multiplicative Interactions and Polynomial Expressivity

The paper then turns to a more expressive class of models: second order recurrent neural networks (2RNNs), which incorporate multiplicative interactions between inputs and hidden states. Here, the authors uncover a distinct mechanism by which depth enhances expressivity. Unlike linear RNNs, which remain constrained to linear transformations of their inputs regardless of depth, linear 2RNNs compute polynomial transformations of their input sequences. Crucially, Theorem 3 establishes that the maximal degree of these polynomials grows precisely with the depth of the network.

This polynomial expressivity distinguishes multiplicative interactions from standard nonlinear activations. In a conventional RNN, applying a ReLU or tanh activation depthwise enables piecewise linear or smooth approximations, but the composition remains within the class of functions representable by feedforward networks applied sequentially. In contrast, the bilinear terms in 2RNNs create multiplicative couplings between time steps that generate genuine polynomial features of increasing degree as information propagates through deeper layers.

The analysis extends to CPRNNs, a practical variant where the bilinear tensor is factorized via CP decomposition to manage parameter counts. Theorem 4 reveals an orthogonality between depth and rank in these architectures: increasing the rank of the decomposition expands the space of representable polynomials in ways that depth cannot replicate, and vice versa. This suggests that practitioners should view these hyperparameters as complementary rather than substitutable resources.

Perhaps the most striking theoretical result is Theorem 5, which establishes a strict separation between multiplicative interactions and depthwise nonlinearities. The authors identify functions requiring state tracking, specifically the parity task, that can be computed by a single layer 2RNN but cannot be realized by any deep RNN employing only nonlinear activations between layers. This demonstrates that multiplicative interactions provide access to computational primitives that are fundamentally inaccessible through the composition of standard nonlinearities, regardless of network depth.

Architectural Implications and Trade-offs

These theoretical findings illuminate a tension in modern sequence modeling that is often underappreciated in empirical studies. The current trend toward linear RNNs and SSMs is driven by legitimate practical concerns: linear recurrences permit efficient parallel training via scan algorithms and avoid the vanishing gradient problems that plague deep nonlinear RNNs. However, the expressivity analysis suggests that this efficiency comes at a representational cost. The inability of deep linear RNNs to compute polynomials or perform state tracking without multiplicative interactions indicates that certain algorithmic tasks may remain out of reach for purely linear architectures, regardless of how deep they are made.

The empirical validation in the paper supports this concern. On synthetic memory and copying tasks, deep linear RNNs perform as predicted by the theory, successfully leveraging depth to improve retention. However, on the parity task, which requires state tracking rather than mere memory, architectures lacking multiplicative interactions fail regardless of depth, while 2RNNs succeed efficiently. On real world benchmarks including Tiny Shakespeare and the Long Range Arena, depth generally improves performance across architectures, but the parameter efficiency gains predicted for memory tasks do not uniformly transfer to all domains. This suggests that natural language and other sequential data may require a mixture of memory and polynomial computation that pure linear or pure multiplicative architectures cannot optimally provide.

Looking forward, these results raise important questions about how to reconcile the training stability and hardware efficiency of linear models with the expressive necessities of multiplicative interactions. One might explore architectures that introduce multiplicative terms selectively, perhaps through gating mechanisms that activate bilinear computations only when state tracking is required, while maintaining linear dynamics for memory intensive operations. Alternatively, the development of training techniques that can stabilize deep 2RNNs without requiring the full machinery of second order optimization remains an open challenge.

Conclusion

On the Role of Depth in the Expressivity of RNNs fundamentally reframes how we should conceptualize depth in recurrent architectures. Rather than viewing depth merely as a vehicle for composing nonlinearities, the paper demonstrates that in the recurrent setting, depth independently enhances memory capacity and, when combined with multiplicative interactions, enables polynomial computations of increasing degree. The separation between state tracking and memory as distinct computational requirements, and the corresponding architectural specializations needed to address each, suggests that the future of sequence modeling may lie in hybrid approaches. As the field continues to explore the space between fully linear SSMs and fully multiplicative architectures, the theoretical distinctions drawn in this work provide essential guidance for navigating the trade offs between computational efficiency and expressive completeness.