Parallelizable Recurrence for Efficient Sequence Modeling

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

Version 1 of 1641 papers694 conceptsfrozen 2026-10-04

For years, the deep learning community has faced a fundamental trade-off known as the "impossible triangle" of sequential modeling: the desire to combine high training efficiency, fast inference speed, and strong predictive performance.

Traditional Recurrent Neural Networks (RNNs), such as LSTMs and GRUs, offer $O(1)$ inference—they process one token at a time with a fixed-size memory. However, as noted in State-Space Modeling in Long Sequence Processing, they suffer from a "sequential tax." Because the hidden state $h_t$ is a non-linear function of the previous state $h_{t-1}$, every step must wait for the previous one to finish. This serial bottleneck prevents RNNs from exploiting the massive parallelism of modern GPUs, leading to the dominance of Transformers.

A new wave of research is breaking this bottleneck by redesigning recurrence to be mathematically parallelizable, effectively "rediscovering" RNNs for the modern hardware era.

The Associative Scan Breakthrough

The core intuition behind parallelizable recurrence is the associative property. In a standard RNN, the state update is often $h_t = \sigma(Wh_{t-1} + Ux_t)$. The non-linearity $\sigma$ and the way $h_{t-1}$ is buried inside it make the operation non-associative. You cannot compute $h_{100}$ without computing $h_1$ through $h_{99}$ first.

However, if the recurrence is linear—or can be simplified into a linear-like form—the operation becomes associative. As Zhenrui Yue, Julian McAuley, and others demonstrate in Linear Recurrent Units for Sequential Recommendation, linear recurrence allows the use of parallel scans (or prefix sums). This algorithm turns a sequential process of length $L$ into a parallel one with $O(\log L)$ depth, allowing the model to train as fast as a Transformer while retaining the $O(1)$ inference of an RNN.

Stripping the Gates: minLSTM and minGRU

One of the most surprising recent findings is that much of the complexity in traditional RNNs was actually hindering their scalability. In Were RNNs All We Needed?, Leo Feng, Yoshua Bengio, and their colleagues introduced minLSTM and minGRU.

They observed that the primary obstacle to parallelization in LSTMs is that the gates (input, forget, and output) depend on the previous hidden state $h_{t-1}$. By removing this dependency—making the gates depend only on the current input $x_t$—the recurrence becomes a simple element-wise weighted sum. This minimal architecture is fully parallelizable during training, uses significantly fewer parameters, and rivals the performance of modern State-Space Models (SSMs) like Mamba.

Hybridizing Recurrence and Attention

While pure recurrence is efficient, attention is still king at local feature extraction. This has led to hybrid architectures that use recurrence to handle long-range dependencies while using attention for local context.

Jonathan Pilault and Mahan Fathi proposed the Block-State Transformer (BST), which replaces the sequential passing of hidden states between blocks with parallelizable SSMs. Similarly, Xianming Li and colleagues developed Recurrent Attention Networks (RAN), which use a window-level recurrent mechanism to process documents of arbitrary length without the quadratic cost of standard self-attention.

Beyond Sequences: Graphs and Labeling

The drive toward parallelization is extending beyond simple text sequences into more complex structures:

  • Temporal Graphs: Yizhou Chen and others in Recurrent Temporal Revision Graph Networks address the bottleneck of node-wise hidden states, attempting to integrate complete historical data without the usual sequential overhead.
  • Sequence Labeling: Traditional models like CRFs rely on the sequential Viterbi algorithm. Caio Corro and Mathieu Lacroix introduced Bregman Conditional Random Fields, which replace recursive dynamic programming with parallelizable iterative projections.
  • Computer Vision: In MambaVT, Simiao Lai applies parallelizable state-space modeling to RGB-T tracking, achieving 50 FPS by replacing the standard Transformer backbone with a linear-complexity Mamba design.

The Future of Memory

The shift toward parallelizable recurrence suggests a future where "memory" is not a static cache (like the KV cache in Transformers) but a dynamic, compressed state that is updated via efficient, parallel operations. As explored in Lattice and TNT, the goal is to move toward "test-time memorization"—where the model's internal weights or states are updated on the fly as it reads, but in a way that modern hardware can actually execute at scale.

Papers in this version

Showing 60 of 641 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_parallelizable_recurrence_for_efficient__4af3340a,
  title = {Parallelizable Recurrence for Efficient Sequence Modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelizable-recurrence-for-efficient-sequence-modeling/rdr_4af3340a95ca419699d23d38ae23ea96},
  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_parallelizable_recurrence_for_efficient__4af3340a_v1,
  title = {Parallelizable Recurrence for Efficient Sequence Modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallelizable-recurrence-for-efficient-sequence-modeling/rdr_4af3340a95ca419699d23d38ae23ea96/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}