Scaling Real-Time Recurrent Learning

30 concepts27 papers

When training a Recurrent Neural Network (RNN) on sequential data, we typically rely on Backpropagation Through Time (BPTT). BPTT operates in reverse-mode: it processes an entire sequence forward, stores every intermediate hidden state in memory, and then propagates errors backward from the end of the sequence to the beginning.

While highly efficient per time step, BPTT introduces a severe memory bottleneck. Storing long histories becomes impractical for long sequences, violates the streaming nature of real-time applications, and lacks biological plausibility—the brain cannot pause reality to backpropagate errors through hours of stored memories (Barber (2002); Neftci (2021)).

The natural alternative is Real-Time Recurrent Learning (RTRL), a forward-mode differentiation approach (Toomarian et al. (1990)). Instead of keeping a history of states to compute gradients later, RTRL maintains a running history of gradients to update weights immediately at each time step. However, exact RTRL suffers from a devastating computational bottleneck: its computational complexity scales as $O(N^4)$ or $O(N^3)$ relative to the number of hidden units $N$.

A vibrant thread of research focuses on breaking this complexity barrier, transforming forward-mode learning from a theoretical curiosity into a scalable, practical framework for real-time deep learning.


Why Exact Forward Gradients Explode in Complexity

To understand why forward-mode learning scales so poorly, we must look at the tensor tracking the network's sensitivities.

Consider an RNN with a hidden state vector $h_t$ of size $N$ and a recurrent weight matrix $W$ of size $N \times N$ (containing $N^2$ parameters). The standard state update is:

$$h_t = \sigma(W h_{t-1} + x_t)$$

To update $W$ online without looking backward, we must know how a change in any weight affects the current hidden state. This requires us to maintain the Jacobian tensor, $J_t = \frac{\partial h_t}{\partial W}$. Because $h_t$ has $N$ elements and $W$ has $N^2$ elements, this tensor contains $N \times N^2 = N^3$ entries.

At each time step, we update this tensor using the chain rule:

$$ \frac{\partial h_t}{\partial W} = \frac{\partial h_t}{\partial h_{t-1}} \frac{\partial h_{t-1}}{\partial W} + \frac{\partial h_t}{\partial W_{\text{immediate}}} $$

The core bottleneck lies in the matrix-tensor multiplication $\frac{\partial h_t}{\partial h_{t-1}} \frac{\partial h_{t-1}}{\partial W}$. Here, we multiply the $N \times N$ state-to-state transition matrix by the $N \times N^2$ Jacobian tensor. For a fully connected, dense recurrent network, this operation requires $N \times N \times N^2 = N^4$ operations.

As noted by Zipser (1989) and Pineda (1989), this quartic scaling makes exact real-time updates impossible for networks of even moderate size. Even when exploiting structural redundancies to reduce the cost to $O(N^3)$ (Sun et al. (1991); Benzing et al. (2019)), the cubic scaling still severely outpaces the $O(N^2)$ cost of a standard forward inference pass, rendering exact online optimization impractical for modern high-dimensional architectures (Tallec et al. (2018); Nath et al. (2020); Silver et al. (2022)).

Exact RTRL Bottleneck:
[State Transition Matrix (N x N)] x [Jacobian Tensor (N x N^2)] = O(N^4) Operations

To scale online learning, researchers have developed three primary strategies: Sparsification, Factorization, and Architectural Constraints.


Strategy 1: Structural Sparsification

The earliest intuition for scaling RTRL was to avoid tracking how every weight affects every neuron. Zipser (1989) proposed a "subgrouping" strategy, dividing the network into smaller, isolated clusters of neurons and tracking sensitivities only within those boundaries.

Modern iterations of this concept apply explicit mathematical sparsification to the Jacobian tensor. In the SnAp (Sparse n-step Approximation) framework introduced by Menick et al. (2021), the Jacobian matrix is strategically pruned. By keeping only the entries where a neuron has a direct or near-step influence on another, the $N \times N^2$ tensor becomes highly sparse.

When we zero out the vast majority of the cross-talk terms in the sensitivity matrix, the $O(N^4)$ tensor multiplication collapses into a sequence of sparse operations, bringing the per-step complexity down closer to the ideal $O(N^2)$ baseline.


Strategy 2: Low-Rank and Kronecker Factorization

Instead of dropping entries entirely, can we compress the massive $N \times N^2$ Jacobian tensor into a more compact representation?

The Unbiased Online Recurrent Optimization (UORO) algorithm, derived by Tallec et al. (2018), achieves this by approximating the Jacobian with a rank-one stochastic matrix product:

$$\frac{\partial h_t}{\partial W} \approx \tilde{u}_t \tilde{v}_t^T$$

where $\tilde{u}_t$ is a vector of size $N$ and $\tilde{v}_t$ is a vector of size $N^2$. By tracking and updating these two vectors instead of the full tensor, UORO reduces the computational complexity per step to $O(N^2)$, matching the cost of standard inference.

To reduce the variance introduced by rank-one stochastic approximations, Mujika et al. (2018) introduced KF-RTRL, which decomposes the Jacobian using random Kronecker factors. Benzing et al. (2019) advanced this by proving an optimal Kronecker-sum approximation.

By representing the sensitivity tensor as a Kronecker product of smaller matrices, these methods capture structural correlations across weights and hidden states without explicitly constructing the full $N^3$ tensor, maintaining low variance while preserving a highly scalable computational profile.


Strategy 3: Architectural Constraints

The most radical and effective way to scale forward-mode learning is to redesign the RNN architecture so that the state-to-state transition matrix $\frac{\partial h_t}{\partial h_{t-1}}$ is naturally simple.

If we constrain the recurrent connections so that neurons do not cross-talk directly—meaning the recurrent weight matrix $W$ is diagonal—the state transition matrix becomes diagonal as well.

Standard RNN (Dense W):          Element-Wise RNN (Diagonal W):
   h1   h2   h3                     h1   h2   h3
   | \ / | \ / |                     |    |    |
   v  X  v  X  v                     v    v    v
   h1   h2   h3                     h1   h2   h3
(Cross-talk causes O(N^4))       (No cross-talk: O(N) or O(N^2))

As demonstrated by Zucchet et al. (2023), decoupling the hidden units into independent, linear recurrent modules simplifies the chain-rule update. Because each hidden unit's next state depends only on its own past state, the cross-derivatives vanish. The exact forward-mode gradient can then be tracked with only $O(N)$ or $O(N^2)$ complexity, matching or beating the computational overhead of truncated BPTT while completely eliminating truncation bias.

Irie et al. (2024) demonstrated the practical power of this approach by applying element-wise RNN architectures to complex 3D robotic and reinforcement learning environments. They proved that under these architectural constraints, exact RTRL becomes highly tractable, allowing agents to learn from infinite-length sequences and outperform standard offline baselines.


Biological Connections and Eligibility Traces

The quest to scale forward-mode gradients deeply intersects with computational neuroscience and reinforcement learning. In biological brains, synapses adjust their weights based on locally available information.

To approximate forward gradients locally, models often utilize eligibility traces—temporary, fading memories of past pre- and post-synaptic activity. Roth et al. (2019) developed KeRNL (Kernel RNN Learning), which factorizes the exact gradient tensor into a product of learned sensitivity weights and local eligibility traces, matching BPTT performance on long-term dependency tasks while operating entirely forward in time.

Similarly, in online reinforcement learning, algorithms like BP($\lambda$) leverage eligibility traces to estimate gradients without deep temporal unrolling (Costa et al. (2024)). In multi-layered or deep recurrent reinforcement learning architectures, tracking these traces through successive layers remains a challenge, often requiring structural simplifications or independent layer assumptions to prevent the gradient traces from compounding the computational overhead (Elelimy et al. (2024); Real-Time Recurrent Reinforcement Learning (2025)).


Broader Context: The Cost of History

The tension between forward-mode tracking and backward-mode re-evaluation appears across many deep learning domains:

  • Compositional Predictions: In Gradient Temporal Difference (GTD) networks, computing exact gradients for a web of interconnected predictions requires tracking how every individual prediction relies on the entire history, creating a scaling challenge similar to RTRL (Silver et al. (2012)).
  • Second-Order Adaptation: Algorithms like Recursive Least Squares (RLS) applied to Echo State Networks bypass gradient unrolling but introduce a quadratic computational cost relative to the reservoir size to track the running inverse correlation matrix (Jaeger (2002)).
  • Reversing Operations: Optimization algorithms that reverse the sequence of updates, such as backward-SGD, achieve unique stability properties but inherently suffer from quadratic time complexity because every new step requires re-evaluating the historical chain of operations (Dherin et al. (2025)).
  • Online Production Systems: In industrial applications like neural ranking models, performing full gradient updates on accumulated instances during live user interactions introduces latency bottlenecks, necessitating sublinear or localized approximation methods (Jia et al. (2022)).

Ultimately, scaling real-time recurrent learning is about choosing how to pay for the past. While exact tracking requires an unmanageable polynomial toll, the combination of structural sparsification, low-rank factorization, and element-wise architectures proves that we can achieve truly streaming, lifelong learning without the heavy burden of historical storage.

Key Foundational Work

Subgrouping Reduces Complexity and Speeds Up Learning in Recurrent Networks (1989) — contributed 2 concept elements to this direction.
Time Dependent Adaptive Neural Networks (1989) — contributed 1 concept elements to this direction.
Adjoint-Functions and Temporal Learning Algorithms in Neural Networks (1990) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_online_learning_scalability_0751c811,
  title = {online learning scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-scalability/rdr_0751c8112628426ebc90577fe4f2b83e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_online_learning_scalability_0751c811_v1,
  title = {online learning scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/online-learning-scalability/rdr_0751c8112628426ebc90577fe4f2b83e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake