Efficient Sequence Modeling with Linear State Space Models

1,410 concepts814 papers6 proposals

For years, the deep learning landscape has been dominated by a fundamental trade-off in sequence modeling. On one side stand Transformers, which capture long-range dependencies with unparalleled accuracy but suffer from a quadratic computational bottleneck: as the sequence length $N$ grows, the cost of computing self-attention scales at $O(N^2)$. On the other side sit Recurrent Neural Networks (RNNs), which process tokens sequentially with linear $O(N)$ complexity but struggle to retain historical context due to vanishing gradients and memory decay.

A rapidly growing body of research addresses this dilemma through Linear State Space Models (SSMs). By reimagining sequence modeling through the lens of continuous dynamical systems, these architectures achieve the best of both worlds: the parallelizable training of Transformers and the linear-scaling, constant-time inference of RNNs.

The Core Mechanism: Dual Representations

To understand why linear SSMs work, we must look at their foundational mathematical property: the ability to switch between a continuous differential equation, a discrete recurrence, and a global convolution.

At its heart, a state space model maps a 1D input signal $x(t)$ to an $N$-dimensional latent state $h(t)$ before projecting it to a 1D output $y(t)$ via a system of linear ordinary differential equations:

$$\dot{h}(t) = Ah(t) + Bx(t)$$ $$y(t) = Ch(t) + Dx(t)$$

To process discrete tokens or time-series steps, this continuous system is discretized using a step size $\Delta$, transforming the continuous matrices into discrete counterparts $(\bar{A}, \bar{B})$. This yields a standard recurrent formulation:

$$h_t = \bar{A}h_{t-1} + \bar{B}x_t$$ $$y_t = Ch_t + Dx_t$$

This recurrent view is incredibly efficient for inference. To predict the next step, the model only needs to maintain the current hidden state $h_{t-1}$ and ingest the new token $x_t$, requiring $O(1)$ time per step and $O(N)$ total complexity over a sequence.

However, sequential recurrence is notoriously slow to train on modern parallel hardware like GPUs. The breakthrough of Linear Time-Invariant (LTI) SSMs is that if the transition matrices $A, B,$ and $C$ remain constant across all time steps, the recurrence can be mathematically unrolled into a single, global convolution:

$$y_t = C\bar{A}^t h_0 + \sum_{i=0}^{t} C\bar{A}^{t-i}\bar{B}x_i$$

By defining a convolution kernel $K_t = C\bar{A}^t\bar{B}$, the entire output sequence can be computed simultaneously as $y = x * K$. Because convolutions can be computed efficiently in the frequency domain using Fast Fourier Transforms (FFTs), the model can be trained in parallel with sub-quadratic complexity.

To make this architecture practical, researchers focused on structuring the state matrix $A$. Ankit Gupta et al. demonstrated in Diagonal State Spaces are as Effective as Structured State Spaces that restricting $A$ to a purely diagonal parameterization matches the performance of more complex low-rank formulations while significantly simplifying implementation. Building on this efficiency, Yitian Zhang et al. introduced SKOLR: Structured Koopman Operator Linear RNN for Time-Series Forecasting, which splits signals into parallel frequency bands processed by linear RNNs, achieving state-of-the-art accuracy while utilizing less than 2% of the GPU memory required by traditional attention-based models.

From Static Convolutions to Dynamic Selection

While pure LTI SSMs excel at capturing long-range temporal structures, they possess a major flaw: because the convolution kernel is fixed across time, the model cannot alter its attention based on the content of the input. It processes a crucial piece of information and a random noise token with the exact same transition dynamics.

To solve this, modern architectures introduce Selective State Space Models (often referred to as the Mamba architecture). A selective SSM makes the discretization parameter $\Delta$ and the matrices $B$ and $C$ direct functions of the input token $x_t$.

This input-dependency breaks the time-invariance property, meaning the model can no longer be computed as a simple global convolution via FFTs. Instead, to maintain parallel training efficiency, selective SSMs rely on a hardware-aware parallel associative scan algorithm. This allows the model to compute the recurrent states in parallel across GPU threads while dynamically adjusting what information to compress, retain, or discard at each specific time step.

The power of this selection mechanism is explored across several foundational tasks. Harsh Mehta et al. demonstrated in Long Range Language Modeling via Gated State Spaces how combining gating units with simplified state spaces enables models to generalize zero-shot to sequences up to 16 times longer than those seen during training. Similarly, Aoran Wang et al. utilized this selective compression in Structural Inference of Dynamical Systems with Conjoined State Space Models to prioritize relevant temporal features, allowing the model to robustly infer hidden interactions even when data is sampled at highly irregular intervals.

Unlocking High-Dimensional and Real-Time Modalities

The transition from quadratic $O(N^2)$ attention to linear $O(N)$ state transitions has profound practical implications, particularly for domains where sequence lengths are naturally massive or where real-time constraints are strict.

High-Dimensional Video and Spatiotemporal Modeling

In video processing, sequence length scales rapidly with frame rate and spatial resolution, making Transformers computationally prohibitive. Jimmy T. H. Smith et al. addressed this in Convolutional State Space Models for Long-Range Spatiotemporal Modeling, showing that linear-scaling inference can generate long-horizon video samples hundreds of times faster than quadratic attention mechanisms.

This efficiency allows models to ingest extensive temporal context without encountering out-of-memory errors. For instance, Guozhen Zhang et al. developed VFIMamba: Video Frame Interpolation with State Space Models to achieve global context modeling across high-resolution 4K video frames. In generative tasks, Xiang Wang et al. showed in UniAnimate: Taming Unified Video Diffusion Models for Consistent Human Image Animation that replacing traditional attention layers with SSMs allows video generation frameworks to scale linearly to hundreds of frames on standard hardware. For tracking applications, Simiao Lai proposed MambaVT: Spatio-Temporal Contextual Modeling for robust RGB-T Tracking, leveraging linear complexity to process multiple historical templates simultaneously, helping the system adapt to target appearance changes over long durations.

Motion Forecasting and Trajectory Prediction

In autonomous driving and robotics, tracking agents requires long-term temporal consistency alongside low-latency execution. Chengyue Wang et al. developed DEMO: A Dynamics-Enhanced Learning Model for Multi-Horizon Trajectory Prediction in Autonomous Vehicles, utilizing selective SSMs to encode historical motion data within strict real-time latency constraints.

The structural advantages of SSMs over Transformers in this domain are highlighted by Bozhou Zhang et al. in DeMo: Decoupling Motion Forecasting into Directional Intentions and Dynamic States, noting that while Transformers excel at global spatial reasoning, linear-time sequence models are inherently more effective at maintaining long-term temporal consistency in predicted paths. This temporal grounding is further extended to complex 3D human motion: Haonan Han demonstrated in MambaTalk: Efficient Holistic Gesture Synthesis with Selective State Space Models that SSMs can synthesize synchronized gestures without quadratic computational costs, while Xinghan Wang introduced Text-controlled Motion Mamba: Text-Instructed Temporal Grounding of Human Motion to process long, untrimmed motion captures that would otherwise cause memory overflows in attention-based architectures.

High-Frequency Sensor Streams and Biosignals

For continuous physical sensors, data arrives at high frequencies, resulting in massive sequence lengths. In the domain of neuromorphic sensing, the authors of the Event-Based Eye Tracking. AIS 2024 Challenge Survey highlighted linear SSMs as a primary candidate for real-time edge applications due to their optimal trade-off between temporal context and computational cost. To maximize this efficiency, Jiaqi Chen et al. proposed SpikMamba: When SNN meets Mamba in Event-based Human Action Recognition, applying recurrent state space equations directly to binary spike sequences from event cameras to achieve linear complexity without heavy downsampling.

Transformer Self-Attention: O(N²) Complexity
[Token 1] <---> [Token 2] <---> [Token 3] <---> [Token 4]  (All-to-all comparison)

Linear State Space Model: O(N) Complexity
[Token 1] ---> [ Hidden State h_t ] ---> [Token 2] ---> [ Hidden State h_t+1 ]
                      |                                         |
               (Global FFT Convolution during training / Constant-time step during inference)

This paradigm is equally powerful for medical time-series analysis. Aditya Kommineni et al. utilized structured SSMs in Knowledge-guided EEG Representation Learning as a parameter-efficient alternative to Transformers, capturing complex neural dynamics over extended periods with 75x fewer parameters. For real-time denoising, Yu-Tung Liu et al. introduced MSEMG: Surface Electromyography Denoising with a Mamba-based Efficient Network, providing global temporal context with linear complexity to remove cardiac interference from muscle recordings. Finally, Avery Hee-Woon Ryoo addressed the clinical deployment bottleneck in Generalizable, real-time neural decoding with hybrid state-space models, demonstrating that SSMs maintain constant-time inference speed regardless of sequence length, satisfying the strict latency requirements of brain-computer interface hardware.

By elegantly bridging continuous-time physical modeling with discrete sequence processing, linear state space models offer a mathematically rigorous solution to the quadratic scaling problem, establishing a new foundation for efficient, long-context deep learning.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_complexity_sequence_modeling_c2e9db9b,
  title = {linear-complexity sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-sequence-modeling/rdr_c2e9db9be86248e5bb558f5abeeec37e},
  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_linear_complexity_sequence_modeling_c2e9db9b_v1,
  title = {linear-complexity sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-sequence-modeling/rdr_c2e9db9be86248e5bb558f5abeeec37e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake