For years, sequence modeling has been trapped in a fundamental trade-off between training efficiency and inference speed.
Recurrent Neural Networks (RNNs) process tokens sequentially. To compute the hidden state at time step $t$, an RNN must first compute the hidden state at time step $t-1$. This step-by-step dependency makes it impossible to parallelize training across the time dimension on modern hardware like GPUs, creating a severe sequential bottleneck. However, during inference, RNNs are incredibly efficient: they maintain a fixed-size memory footprint and generate each new token in constant time ($O(1)$).
Transformers and Convolutional Neural Networks (CNNs) took the opposite approach. By avoiding step-by-step temporal dependencies, they allow hardware to process all tokens in a sequence simultaneously during training. Yet, this parallel training efficiency comes at a steep cost during deployment. Transformers require storing a growing history of past keys and values (the KV cache), leading to quadratic memory and time complexity ($O(T)$ or $O(T^2)$) as sequences grow longer.
A rapidly growing body of research has resolved this dilemma through a concept known as sequential-parallel duality. By designing sequence models that can seamlessly switch between a parallel form for training and a recurrent form for inference, researchers have unlocked the best of both worlds: high-throughput, hardware-accelerated training alongside low-latency, constant-memory generation.
The Core Mechanism: Linearity as a Bridge
The secret to achieving this duality lies in isolating or removing the non-linear activation functions within the recurrent step. In a traditional RNN, the hidden state update is non-linear:
$$h_t = \sigma(W h_{t-1} + U x_t)$$
Because the activation function $\sigma$ (such as $\text{tanh}$ or $\text{ReLU}$) wraps the entire expression, you cannot expand this equation mathematically to solve for $h_t$ without evaluating every intermediate step.
As demonstrated by Chilkuri et al., separating the linear memory dynamics from the non-linear output transformations allows a model to break this bottleneck. If we make the state transition strictly linear, the recurrence relation simplifies to:
$$h_t = A h_{t-1} + B x_t$$
Because this equation is purely linear, we can mathematically unroll it. Assuming an initial state $h_0 = 0$, let's look at the first few steps:
$$h_1 = B x_1$$ $$h_2 = A(B x_1) + B x_2 = AB x_1 + B x_2$$ $$h_3 = A(AB x_1 + B x_2) + B x_3 = A^2B x_1 + AB x_2 + B x_3$$
Extrapolating this to any arbitrary time step $t$, the hidden state can be expressed as a direct sum of all prior inputs:
$$h_t = \sum_{i=1}^t A^{t-i} B x_i$$
This algebraic expansion changes everything. It reveals that the hidden state at any point in time can be computed directly from the input sequence, without needing to calculate the intermediate hidden states sequentially.
Training Mode: The Convolutional and Scan Formulations
Depending on whether the transition matrix $A$ is constant or changes over time, this unrolled linear equation can be executed in parallel using two primary mathematical formulations.
1. The Global Convolution View
If the transition matrix $A$ and input matrix $B$ are constant across all time steps (a Linear Time-Invariant system), the coefficients applied to the inputs depend entirely on the relative distance $(t-i)$. This structure matches the exact mathematical definition of a discrete 1D convolution.
We can construct a single, global convolution kernel $K$ that spans the maximum sequence length:
$$K = [B, AB, A^2B, \dots, A^{T-1}B]$$
To train the model, the entire sequence of hidden states $H$ can be computed at once by convolving the input sequence $X$ with this kernel:
$$H = K * X$$
As shown in foundational work on Structured State Space models (S4) by Gu et al., this global convolution can be computed incredibly fast on modern hardware using Fast Fourier Transforms (FFTs). By mapping the recurrence to an FFT-accelerated convolution, the system completely bypasses the sequential bottleneck during training, achieving sub-quadratic computational complexity relative to sequence length (Lu et al.).
2. The Parallel Prefix Scan View
If the parameters are time-varying (meaning $A_t$ and $B_t$ change at each step to condition on the input), the operation can no longer be framed as a simple convolution. However, because matrix multiplication is associative, the unrolled state updates can still be computed in parallel using a parallel prefix scan (or parallel scan) algorithm.
A parallel scan distributes the work across a binary tree structure on the GPU. Instead of computing steps $1, 2, 3, \dots, T$ in order, the hardware computes local combinations (e.g., combining step 1 with 2, and step 3 with 4) simultaneously, reducing the sequential time complexity from $O(T)$ to $O(\log T)$. Kortvelesy et al. and Yau et al. demonstrate that this prefix-scan formulation allows time-varying linear models to maintain full training parallelization while preserving deep temporal expressiveness.
Inference Mode: Constant-Time Recurrence
While the convolutional and prefix-scan views are ideal for processing a fully known sequence during training, they are highly inefficient for autoregressive generation (where we predict one token at a time, and each new token depends on the last). If we used the convolutional form during inference, we would have to re-run a growing convolution over the entire history for every single new token we generated.
This is where the duality pays off. Because the convolutional kernel and the prefix scan are mathematically equivalent to the original linear recurrence, we can discard the parallel formulations entirely when deploying the model.
During inference, the model reverts back to its recurrent state-space formulation:
$$h_t = A h_{t-1} + B x_t$$
Training Phase (Parallelized Global View):
Inputs (X): [ x_1 x_2 x_3 ... x_T ]
\ | / /
\ | / / <-- FFT Convolution or Parallel Scan
v v v v
Outputs (H): [ h_1 h_2 h_3 ... h_T ]
Inference Phase (Step-by-Step Recurrent View):
Input (x_t) ---> [ + ] ---> Output (h_t)
^
|
Matrix A (State Memory)
|
Hidden State (h_t-1)
To generate the next token, the model only needs to maintain the single vector $h_{t-1}$ in memory. It multiplies this vector by $A$, adds the new input contribution, and produces the next state. The memory footprint remains completely constant ($O(1)$), and the time required per step never increases, no matter how long the sequence becomes.
A Unified Paradigm Across Domains
This dual-mode capability has sparked a massive wave of innovation across diverse architectures and application domains, effectively unifying what were once considered entirely separate families of models.
- Large Language Models: Architectures like RetNet (Sun et al.) and RWKV (Peng et al.) replace standard softmax attention with dual-form linear representations. They achieve the high-throughput training matrix multiplications of Transformers alongside the low-latency, constant-memory deployment of RNNs. Similarly, frameworks like LION (Afzal et al.) extend this duality to bidirectional tasks by unifying attention, recurrent, and chunkwise representations.
- Audio Generation and Speech Processing: Generating raw audio requires modeling tens of thousands of samples per second. Models like SASHIMI (Goel et al.) and aTENNuate (Pei et al.) leverage the dual representation to train efficiently on long audio waveforms via parallel convolutions, while executing sample-by-sample, real-time processing on edge devices with ultra-low computational overhead.
- Reinforcement Learning and World Models: Simulating environments requires agents to imagine future trajectories quickly. By swapping out slow RNNs or memory-heavy Transformers for dual-form models, architectures like S4WM (Deng et al.) and the Retentive Environment Model (Cohen et al.) allow agents to train on environment data with high throughput and then simulate future states with minimal latency.
- Computer Vision: In fields like event-based vision, where cameras produce continuous streams of high-frequency temporal data, applying the dual-mode framework allows models to train rapidly via unrolled parallel computations while maintaining real-time, constant-memory inference on physical hardware (Zubic et al.).
Ultimately, sequential-parallel duality proves that training throughput and inference efficiency are not mutually exclusive. By anchoring sequence modeling in the clean mathematics of linear systems, the field has moved past the traditional trade-offs of recurrent and feedforward networks, establishing a highly efficient paradigm for long-context sequence processing.
Key Foundational Work
It's Raw! Audio Generation with State-Space Models (2022) — contributed 4 concept elements to this direction.
Parallelizing Legendre Memory Unit Training (2021) — contributed 2 concept elements to this direction.
Efficiently Modeling Long Sequences with Structured State Spaces (2022) — contributed 1 concept elements to this direction.