Parallel Recurrence through Decoupled Linear Transformations

This direction is merged into another direction: sequential processing bottleneck (sequential computation bottleneck). Its last version stays readable and citable here.

Version 1 of 161 papers80 conceptsfrozen 2026-10-04

The central challenge of Recurrent Neural Networks (RNNs) has always been their sequential nature. In a traditional LSTM or GRU, the hidden state $h_t$ is computed using a large matrix multiplication involving the previous state $h_{t-1}$. This creates a strict dependency chain: you cannot compute the state for the 100th word in a sentence until you have finished the 99th. While this allows RNNs to maintain a persistent memory, it prevents them from utilizing the massive parallel processing power of modern GPUs, which thrive on doing many independent calculations at once.

To overcome this, a broad research direction has emerged that seeks to "decouple" the heavy computational work from the sequential update. By isolating the time-dependent steps into minimalist, element-wise operations, these models achieve the training speed of Transformers while retaining the efficient, constant-time inference of RNNs.

Decoupling the Heavy Lifting

The primary bottleneck in a standard RNN is not the recurrence itself, but the fact that a large matrix-vector multiplication ($W \cdot h_{t-1}$) happens inside the loop. Researchers like James Bradbury and Tao Lei observed that much of this work can be moved outside the sequential chain.

In Quasi-Recurrent Neural Networks, James Bradbury proposed using masked convolutions to pre-compute "candidate states" and "gates" for every timestep in parallel. Once these are computed, a lightweight "pooling" layer handles the temporal dependency. Similarly, Biao Zhang demonstrated in the Lightweight Recurrent Network (LRN) that moving parameter-heavy operations outside the loop can make models up to 48% faster without losing accuracy.

By treating the input transformations as a parallelizable pre-processing step, the model only needs to perform a simple, element-wise update during the sequential pass.

From Matrix Multiplications to Element-wise Scans

If we remove the matrix multiplication from the state update, what is left? The answer is usually an element-wise (Hadamard) product. In Deep Independently Recurrent Neural Network (IndRNN), Shuai Li showed that if each neuron's hidden state only depends on its own previous value (and not the values of other neurons in the same layer), the gradient vanishing and exploding problems are largely solved.

This shift from $h_t = \sigma(W h_{t-1} + U x_t)$ to something like $h_t = f_t \odot h_{t-1} + i_t \odot \tilde{h}_t$ is transformative. Because the update is now linear and element-wise, the entire sequence of states can be calculated using a parallel associative scan.

As Antonio Orvieto explains in Resurrecting Recurrent Neural Networks for Long Sequences, a linear recurrence can be viewed as a prefix sum operation. Just as you can sum a list of numbers in $O(\log N)$ time on parallel hardware, you can compute the hidden states of a Linear Recurrent Unit (LRU) or a State-Space Model (SSM) in parallel. This bypasses the $O(N)$ sequential bottleneck entirely during training.

Hardware-Aware Recurrence

The final piece of the puzzle is making these mathematical shortcuts run efficiently on actual silicon. Even if an algorithm is theoretically parallelizable, memory access patterns (I/O) can still slow it down.

Korbinian Pöppel and Maximilian Beck addressed this in FlashRNN by using kernel fusion. By keeping the recurrent state in fast on-chip memory (SRAM) and avoiding repeated trips to the slower main memory (DRAM), they achieved up to 50x speedups for traditional RNNs.

This hardware-centric view is also central to the xLSTM architecture. By introducing exponential gating and a matrix-like memory structure that can be updated in parallel, Andreas Auer and colleagues have scaled the LSTM to the billion-parameter level, allowing it to compete with Transformers on tasks like vision (Vision-LSTM) and language modeling.

Why It Works: The Best of Both Worlds

The reason this research direction is so potent is that it resolves a fundamental trade-off in deep learning:

  1. Transformers are fast to train because they process all tokens at once, but they are slow to run (inference) because their memory grows with the sequence length.
  2. Traditional RNNs are fast to run because they have a fixed-size state, but they are slow to train because of the sequential bottleneck.

By decoupling the linear transformations from the recurrence and linearizing the state updates, models like SRU, LRU, and xLSTM achieve the best of both worlds. They use parallel scans to train at Transformer speeds and use their recurrent state to perform inference with constant memory overhead.

Papers in this version

Showing 60 of 61 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parallel_recurrence_through_decoupled_li_6aa98579,
  title = {Parallel Recurrence through Decoupled Linear Transformations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-recurrence-through-decoupled-linear-transformations/rdr_6aa985799f9349e0bd53ee1bbfb98124},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallel_recurrence_through_decoupled_li_6aa98579_v1,
  title = {Parallel Recurrence through Decoupled Linear Transformations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-recurrence-through-decoupled-linear-transformations/rdr_6aa985799f9349e0bd53ee1bbfb98124/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}