The defining constraint of modern sequence modeling is the "quadratic bottleneck." In a standard Transformer, every token attends to every other token. This $O(L^2)$ complexity means that if you double the input length, the computational cost and memory requirements quadruple. While manageable for short sentences, this scaling law becomes a wall for high-resolution audio, multi-minute human motion, long-term time series, and extensive user histories.
To break this wall, researchers are moving away from dense global attention toward architectures that scale linearly or sub-quadratically with sequence length.
Compressing the Sequence via Token Aggregation
One of the most intuitive ways to bypass quadratic scaling is to simply make the sequence shorter before it reaches the attention mechanism. If we can represent the same information with fewer, more "meaningful" tokens, the $O(L^2)$ cost drops precipitously.
In the realm of recommendation systems, Jiayi Liao and colleagues introduced PatchRec, which aggregates individual user actions into "item patches" and "session patches." This hierarchical compression allows the model to process much longer histories—capturing long-term preferences that would otherwise be truncated—while actually reducing the computational load.
A similar intuition applies to signal processing. Tal Peer demonstrated that in speech enhancement, replacing 2ms "learned" frames with 32ms STFT (Short-Time Fourier Transform) magnitudes reduces the number of tokens by a factor of 16. Because of the quadratic nature of attention, this results in an 8x reduction in operations. Rather than learning everything from scratch, leveraging classical signal processing structures provides a "free" reduction in sequence length.
For more general text tasks, Piotr Nawrot and the team behind Dynamic-Pooling Transformer proposed grouping tokens into variable-length segments. By predicting boundaries for words or phrases and pooling them, the model achieves a better speed-accuracy trade-off than fixed-block methods.
Replacing Attention with Linear Primitives
While compression helps, it doesn't change the underlying $O(L^2)$ scaling. A more fundamental shift involves replacing the self-attention mechanism entirely with primitives that scale linearly ($O(L)$) or near-linearly ($O(L \log L)$).
State Space Models (SSMs), particularly the Mamba architecture, have emerged as a leading contender. Unlike Transformers, which keep the entire history in a KV cache, SSMs compress the history into a fixed-size hidden state. Li Wu and others utilized this in UmambaTSF for long-term time series forecasting, achieving state-of-the-art accuracy with linear-time efficiency. Similarly, Vincent Tao Hu introduced ZigMa, which uses a "zigzag" scanning strategy to apply Mamba to visual data, enabling high-resolution image and video generation that would be memory-prohibitive for standard Transformers.
Another approach is to rethink the matrix multiplications at the heart of the Transformer. Daniel Y. Fu and the Monarch Mixer team replaced both attention and MLPs with "Monarch matrices"—a class of structured matrices that are hardware-efficient and scale sub-quadratically. This allows the model to scale not just in sequence length, but also in model width, without the typical computational explosion.
Efficiency through the Frequency Domain
For data with periodic or seasonal patterns, such as time series or audio, the time domain (point-by-point) might be the most expensive place to operate. Kun Yi and co-authors argue in their survey that moving to the frequency domain via Fourier or Wavelet transforms allows models to capture global patterns more efficiently.
In TFDNet, Yuxiao Luo applies this by decomposing signals into trend and seasonal components using STFT. By processing these components in the frequency domain, the model avoids the need for the $O(L^2)$ comparisons required to find distant dependencies in the time domain. The frequency domain naturally "sees" the whole sequence at once, turning a long-range temporal problem into a local spectral one.
Recurrence and Persistent Memory
Finally, some researchers look back to the strengths of Recurrent Neural Networks (RNNs) to solve the Transformer's memory issues. The s-Transformer by Lei He introduces segment-level recurrence. Instead of processing a long paragraph as one massive block, it processes small chunks and passes a "cached memory" between them.
This "block-by-block" processing is also central to StreaMulT, which uses a persistent memory bank to handle arbitrarily long multimodal streams. By decoupling the "current" processing window from the "historical" memory, these models can maintain context over infinite horizons without the memory ever exceeding a fixed threshold.
Why It Works: The Information Bottleneck
The common thread across these diverse methods—from Mamba's state compression to PatchRec's token pooling—is the realization that not every token needs to attend to every other token with equal resolution.
Standard attention is "lazy" in its representation; it keeps everything just in case it's needed. Sub-quadratic architectures work by forcing the model to be more selective. Whether it's through frequency decomposition, state compression, or hierarchical patching, these models identify the underlying structure of the data (the "essence") and discard the redundant quadratic noise. This shift from $O(L^2)$ to sub-quadratic scaling isn't just an optimization; it's a prerequisite for AI that can reason over minutes of video, thousands of time-steps, or a lifetime of user interactions.