Sub-Quadratic Sequence Modeling for Long Contexts

614 concepts568 papers8 proposals

The standard Transformer architecture owes its remarkable success to the self-attention mechanism. By allowing every token in a sequence to look at every other token, Transformers capture intricate, long-range dependencies across text, audio, and video. However, this global view comes at a steep price: quadratic computational and memory complexity ($O(n^2)$) relative to the sequence length $n$.

To understand why, imagine a sequence of length $n$. To compute attention, the model must calculate a pairwise similarity score between every single query and key, resulting in an $n \times n$ attention matrix. When $n$ scales from 1,000 to 100,000 tokens—common in long documents, high-frequency time series, or multi-minute video streams—the memory and compute requirements explode by a factor of 10,000. This quadratic bottleneck makes deploying standard Transformers on resource-constrained hardware or in real-time applications prohibitively expensive.

To break this scalability barrier, researchers are developing alternative architectures and routing mechanisms that achieve linear ($O(n)$) or sub-quadratic ($O(n \log n)$) scaling without sacrificing the expressive power of global context.

Compressing the Past: State Space Models and Linear Recurrence

One of the most prominent strategies for bypassing the $n \times n$ matrix bottleneck is replacing explicit pairwise attention with a continuous or recurrent hidden state. Instead of keeping the entire history of tokens in memory and computing interactions across all of them at every step, these models compress the historical context into a fixed-size internal state that updates incrementally.

State Space Models (SSMs) and modern linear recurrent units operate on this principle. Because the size of the hidden state remains constant regardless of the sequence length, the computational cost scales linearly ($O(n)$) with each new token.

A central question in this shift has been whether attention-free architectures can match the sophisticated capabilities of Transformers, such as learning new tasks on the fly from context. Lee et al. investigated this boundary, demonstrating that modern SSMs like Mamba can perform in-context learning just as effectively as Transformers, proving that an explicit $n \times n$ attention matrix is not strictly necessary for complex reasoning.

This linear scaling makes SSMs highly effective for modalities characterized by dense, high-resolution sequences:

  • Time-Series Diffusion: Traditional diffusion models rely on heavy Transformer backbones that struggle with long temporal windows. Gao et al. introduced SSD-TS, substituting these backbones with linear-time Mamba blocks to process long-range dependencies in high-resolution time series without encountering memory overflows.
  • Temporal Video and Motion Tracking: Processing continuous human movement requires maintaining long-term physical momentum. Zheng et al. leveraged Retentive Networks (NC-RetNet) to capture long-term historical context via cross-chunk states, achieving low-latency 3D human pose estimation without the quadratic penalty of standard attention.

Mixing in the Frequency Domain

Another intuitive way to bypass the quadratic cost of attention is to rethink what attention actually does. At its core, self-attention acts as a "sequence mixer"—a mechanism that allows information to flow and combine across the time or token dimension.

Instead of performing this mixing via pairwise token matching in the time domain, we can transform the sequence into the frequency domain using the Fast Fourier Transform (FFT). In the frequency domain, global interaction can be computed via element-wise multiplication, which takes linear time. Combined with the $O(n \log n)$ cost of the FFT itself, this approach reduces the overall sequence-level complexity to sub-quadratic scaling.

Time Domain:       [Token 1] <---> [Token 2] <---> [Token 3]  --> O(n²) Pairwise Attention
                         │               │               │
                       (FFT)           (FFT)           (FFT)
                         ▼               ▼               ▼
Frequency Domain:  [Freq 1]  *     [Freq 2]  *     [Freq 3]   --> O(n log n) Global Filter

Zhou et al. applied this insight to recommendation systems with FMLP-Rec. Production recommendation models must parse extensive user histories, where standard Transformers hit a scalability wall. By completely replacing self-attention with learnable frequency-domain filters, the authors maintained high accuracy while dropping the sequence complexity to $O(n \log n)$.

Taking this mathematical simplification further, Fu et al. proposed the Monarch Mixer (M2). This architecture replaces both the attention mechanism and the dense Multi-Layer Perceptrons (MLPs) with structured, hardware-efficient primitives called Monarch matrices. This dual optimization achieves sub-quadratic scaling in both the sequence length and the model dimension, drastically increasing throughput for long-context tasks.

Token Compression and Dynamic Routing

Rather than changing the underlying mathematical primitive, a third category of solutions focuses on reducing the effective sequence length $n$ that the attention mechanism has to process, or optimizing how tokens navigate through the network.

Hierarchical Patching

If raw data is too fine-grained, we can aggregate adjacent tokens into compressed blocks or "patches" before feeding them into the Transformer. Liao et al. designed PatchRec for large language model-based recommendations. By grouping individual textual tokens into "item patches" and further into "session patches," the framework compresses long user interaction histories by up to 13.6x. This allows the model to capture extended historical context that would otherwise be truncated due to strict context limits.

Dynamic Token Leaping

Not every token requires the same amount of computational depth. In a standard Transformer, every token passes through every single layer, regardless of its importance to the final output. Kim et al. introduced the Leap-of-Thought (LoT) framework to exploit this redundancy. Instead of permanently dropping tokens—which risks losing critical information—LoT allows tokens to dynamically "leap" over intermediate layers when their processing is deemed redundant. This dynamic routing preserves the full context across the model while accelerating inference speeds up to 25x.

Summary

The transition from quadratic $O(n^2)$ attention to sub-quadratic and linear alternatives represents a fundamental shift in sequence modeling. Whether by compressing history into fixed-size recurrent states (SSMs), shifting sequence mixing to the frequency domain (FFT), or dynamically compressing and routing tokens, these approaches break the scalability bottleneck. The result is an emerging generation of models capable of processing exceptionally long contexts efficiently across diverse real-world applications.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 505 papers
  2. Version 1 · 2026-10-04 · 407 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_transformer_quadratic_complexity_6e272d2a,
  title = {transformer quadratic complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transformer-quadratic-complexity/rdr_6e272d2a0a8d43d2a5241462791f55cc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_transformer_quadratic_complexity_6e272d2a_v2,
  title = {transformer quadratic complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transformer-quadratic-complexity/rdr_6e272d2a0a8d43d2a5241462791f55cc/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake