Towards Scalable and Stable Parallelization of Nonlinear RNNs

Xavier Gonzalez, Andrew Warrington, Jimmy T. H. Smith, Scott W. Linderman

TL;DR

This paper introduces Quasi-DEER and ELK, two novel methods to parallelize the evaluation and training of nonlinear Recurrent Neural Networks (RNNs). By combining diagonal Jacobian approximations with a clever link between optimization theory and parallel Kalman smoothing, the authors achieve up to a 20x speedup over sequential evaluation and significant memory savings, all while maintaining numerical stability in regimes where previous methods failed.

What Problem Does This Paper Address?

Modern deep learning thrives on parallel hardware like GPUs. Architectures like Transformers and Linear State Space Models (SSMs) are popular because they can process entire sequences at once. However, classic nonlinear RNNs (like GRUs and LSTMs)—which remain vital in fields like computational neuroscience—are inherently sequential. To find the state at time $t$, you must first calculate the state at $t-1$. This creates a massive computational bottleneck.

A recent method called DEER attempted to break this bottleneck by treating RNN evaluation as a "fixed-point problem" solved via Newton’s method. While DEER allowed for parallelization, it had two major flaws:

  1. Scalability: It required cubic work relative to the state size ($O(D^3)$), making it memory-intensive for large models.
  2. Instability: Newton’s method is notorious for diverging if the initialization isn't perfect, leading to numerical "explosions" or slow convergence.

Methods

The authors propose three main innovations to fix DEER:

  • Quasi-DEER: Instead of using the full, dense Jacobian matrix (which is expensive to compute and store), they use a diagonal approximation. They provide a novel proof showing that even with this approximation, the algorithm is guaranteed to converge globally to the correct solution. This reduces memory and computational work from $O(D^2)$ and $O(D^3)$ down to $O(D)$.
  • ELK (Evaluating Levenberg-Marquardt via Kalman): To solve the stability problem, the authors move from raw Newton steps to the Levenberg-Marquardt algorithm, which uses a "trust region" to limit step sizes. The "aha!" moment here is the mathematical proof that solving this specific optimization step is equivalent to performing Kalman smoothing. Since Kalman smoothing can be implemented as a parallel associative scan, ELK remains fast ($O(\log T)$ time) while becoming much more robust.
  • Quasi-ELK: This hybrid approach combines the diagonal approximations of Quasi-DEER with the stability of ELK, offering a fast, memory-efficient, and stable parallel solver.

Datasets

The authors evaluated their methods across several benchmarks:

  • Untrained GRUs: Used for raw speed and memory benchmarking across various sequence lengths ($T$) and hidden state sizes ($D$).
  • C. elegans Phenotypes: A real-world time-series classification task involving the body posture of worms, used to test training performance.
  • Autoregressive (AR) GRU: A task involving generating noisy sine waves, specifically designed to test numerical stability in feedback-heavy models.
  • Lorenz96 System: A classic chaotic dynamical system used to evaluate how the algorithms handle highly unstable, nonlinear trajectories.

Key Insights and Ideas

  • The "Diagonal" Surprise: One of the most important takeaways is that you don't need the full Jacobian to reach the right answer. The authors prove that as long as you maintain the identity on the main diagonal, you can put anything in the sub-diagonal and still converge. This justifies the massive speedups of Quasi-DEER.
  • Optimization as Signal Processing: Linking the Levenberg-Marquardt algorithm to Kalman smoothing is a beautiful bridge between two fields. It allows researchers to use highly optimized parallel Kalman filters (originally meant for state estimation) to solve deep learning optimization problems.
  • Parallelism isn't Free: The paper notes that while these methods are theoretically faster, they are subject to "GPU saturation." For very small models, the overhead of parallel scans might not beat sequential code, but as sequence length grows, the parallel advantage becomes dominant.

Key Results

  • Speed: Both DEER and Quasi-DEER are up to 20x faster than sequential evaluation on modern GPUs.
  • Memory Efficiency: Quasi-DEER uses an order of magnitude less memory than the original DEER, allowing it to scale to much larger hidden state dimensions ($D=64$ and beyond) where DEER would crash due to Out-Of-Memory (OOM) errors.
  • Training Gains: In the C. elegans task, Quasi-DEER training steps were 2.5x faster than DEER, despite requiring slightly more iterations to converge.
  • Stability: In the Autoregressive GRU task, standard DEER was highly unstable and required slow "resetting" heuristics. ELK and Quasi-ELK converged rapidly and smoothly without any manual intervention.

Limitations and Future Work

  • Hyperparameter Tuning: ELK introduces a new hyperparameter ($\lambda$ for the trust region) that requires tuning. The authors suggest a grid search, but an adaptive method would be more user-friendly.
  • Chaotic Dynamics: While ELK is more stable, the authors admit that for extremely chaotic systems, sequential evaluation might still be the most reliable (and sometimes faster) option.
  • Hardware Specifics: The current implementation relies on JAX's associative_scan. Performance may vary significantly on different hardware or if implemented in other frameworks like PyTorch.
  • Future Direction: The authors suggest exploring more sophisticated "structured" Jacobian approximations that sit between "diagonal" and "full" to find an even better sweet spot for accuracy and speed.

Summary updated

Abstract

Conventional nonlinear RNNs are not naturally parallelizable across the sequence length, whereas transformers and linear RNNs are. Lim et al. [2024] therefore tackle parallelized evaluation of nonlinear RNNs by posing it as a fixed point problem, solved with Newton's method. By deriving and applying a parallelized form of Newton's method, they achieve huge speedups over sequential evaluation. However, their approach inherits cubic computational complexity and numerical instability. We tackle these weaknesses. To reduce the computational complexity, we apply quasi-Newton approximations and show they converge comparably to full-Newton, use less memory, and are faster. To stabilize Newton's method, we leverage a connection between Newton's method damped with trust regions and Kalman smoothing. This connection allows us to stabilize Newtons method, per the trust region, while using efficient parallelized Kalman algorithms to retain performance. We compare these methods empirically, and highlight the use cases where each algorithm excels.
BibTeX
@inproceedings{gonzalez2024towards,
  author = {Xavier Gonzalez and Andrew Warrington and Jimmy T. H. Smith and Scott W. Linderman},
  title = {{Towards Scalable and Stable Parallelization of Nonlinear RNNs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=hBCxxVQDBw},
}
Figure