Overcoming the Quadratic Attention Bottleneck in Video Modeling

286 concepts247 papers1 proposal

When Transformers transitioned from natural language processing to computer vision, they brought along a fundamental mathematical constraint: the standard self-attention mechanism scales quadratically, $O(N^2)$, with the number of input tokens $N$. In text, a sequence length of a few thousand tokens represents a substantial document. In video, however, the sequence length explodes.

A video is a three-dimensional volume of data spanning height ($H$), width ($W$), and time ($T$). When a model processes a video by breaking frames into spatial patches across time, the total number of tokens scales as $O(H \times W \times T)$. Because standard self-attention requires every single token to compute a pairwise similarity score with every other token, the computational and memory costs scale as $O((HWT)^2)$.

As highlighted by Peiyuan Zhang et al. in Faster Video Diffusion with Trainable Sparse Attention, this "quadratic wall" makes processing high-resolution or long-duration videos prohibitively expensive. To build models capable of generating, understanding, or editing long-form video content, researchers must bypass this dense pairwise comparison. A vibrant domain of research has emerged to solve this scaling bottleneck through four primary strategies: factorization, token reduction, linear attention, and state space modeling.

Spatiotemporal Factorization and Localization

The core intuition behind factorization is that full global attention is highly redundant. A pixel representing a static background element in the first frame rarely needs to compute a unique attention weight for a random background pixel fifty frames later.

Instead of computing a massive, unified $HWT \times HWT$ attention matrix, models can break the operation into isolated dimensions. Arnab et al. pioneered this in ViViT: A Video Vision Transformer by factorizing spatial and temporal attention. By first computing self-attention only among patches within the same frame ($O(T \times (HW)^2)$) and subsequently computing attention across time for the same spatial locations ($O(HW \times T^2)$), the overall complexity drops significantly.

Another way to break down the dense matrix is through localization. Rather than allowing every token to look across the entire video volume, attention can be restricted to local neighborhoods or windows. Zhang et al. demonstrate in ActionFormer: Localizing Moments of Actions with Transformers that local self-attention combined with a multiscale feature pyramid is sufficient for temporal action localization, avoiding the global $O(N^2)$ penalty entirely while maintaining high precision.

Token Pruning, Merging, and Caching

If the quadratic cost is driven by the sequence length $N$, an intuitive solution is to make $N$ smaller by removing or merging redundant tokens. Video sequences exhibit massive temporal continuity; consecutive frames often contain nearly identical visual information.

This redundancy can be exploited dynamically during inference or training. For instance, Wenzhang Sun et al. introduce UniCP, a framework that accelerates video generation in Diffusion Transformers (DiTs) by combining error-aware caching and PCA-based pruning. By reusing previous computations when the change between steps is minimal and simplifying complex calculations on the fly, they mitigate the token explosion.

For vision-language understanding, where a video must be processed alongside a textual prompt, token compression can be applied hierarchically. Ziyang Fan proposes in FlashVID a training-free, tree-based spatiotemporal token merging strategy. By dynamically clustering and merging similar visual tokens, FlashVID reduces the token footprint by up to 90% without requiring model retraining. Similarly, Minghao Yang et al. develop VaporTok, an adaptive video tokenizer that uses reinforcement learning to drop redundant visual patches based on the complexity of the scene, ensuring that computational budgets are spent only on high-information regions.

Linear Attention and Latent Bottlenecks

Rather than reducing the number of tokens or restricting where they look, some approaches alter the mathematical formulation of attention itself to achieve linear $O(N)$ scaling.

Standard attention computes $\text{Softmax}(QK^T)V$. The matrix multiplication $QK^T$ results in an $N \times N$ matrix, which causes the quadratic bottleneck. Linear transformers change the order of operations by applying a kernel function to the Queries ($Q$) and Keys ($K$) first, computing $( \phi(Q) \phi(K)^T ) V$ as $\phi(Q) ( \phi(K)^T V )$. This shifts the computational complexity from $O(N^2)$ to $O(N)$. Dong Li et al. build on this in Linear Video Transformer with Feature Fixation, introducing a feature fixation module that reweights feature importance to help linear models retain focus, overcoming the representation degradation that often plagues standard linear attention.

Alternatively, the sequence can be funneled through a fixed-size bottleneck. Jing Tan et al. introduce the Temporal Perceiver, which uses a small, fixed set of learned latent queries to cross-attend to the massive video token sequence. Because the number of latent queries is independent of the video length, the attention mechanism scales linearly with the input sequence, allowing the model to ingest long-form videos without running out of memory.

Shifting to State Space Models

A more radical departure from the Transformer architecture involves replacing self-attention entirely with alternative sequence-modeling layers that scale linearly by design. State Space Models (SSMs), particularly the selective scan architecture known as Mamba, have emerged as a prominent alternative.

Instead of maintaining an explicit history of all past tokens and computing pairwise weights, an SSM processes inputs sequentially or through parallelizable convolutions, compressing historical context into a fixed-size hidden state. Kunchang Li 0002 et al. demonstrate the viability of this approach in VideoMamba, showing that it can achieve long-range temporal modeling while requiring drastically less GPU memory than traditional attention-based models.

Because video lacks a single inherent direction (unlike text, which flows left-to-right), video SSMs must adapt the scanning mechanism to capture spatial and temporal relationships effectively. For example, Qiang Zhu et al. propose TS-Mamba for online video super-resolution, utilizing a trajectory-aware token selection and a Hilbert scanning mechanism to maintain spatial awareness while preserving the linear computational efficiency of the underlying state space model.

Summary

The transition from short video clips to high-resolution, long-form video modeling hinges entirely on breaking the quadratic scaling of self-attention. Whether by factorizing the spatiotemporal matrix, pruning redundant tokens, rewriting attention to scale linearly, or adopting state space models, these diverse mechanisms share a singular goal: allowing deep learning architectures to process the vast token landscapes of video without succumbing to the memory and computational demands of the quadratic bottleneck.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_attention_complexity_quadratic_8a54c811,
  title = {quadratic attention complexity (quadratic attention scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-attention-complexity-quadratic-attention-scaling/rdr_8a54c811ba054e3692e27efb983148d1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_attention_complexity_quadratic_8a54c811_v1,
  title = {quadratic attention complexity (quadratic attention scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-attention-complexity-quadratic-attention-scaling/rdr_8a54c811ba054e3692e27efb983148d1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake