Scaling Spatiotemporal Attention Beyond Quadratic Complexity

658 concepts528 papers1 proposal

When Vision Transformers (ViTs) process a static 2D image, they slice it into a grid of patches. If an image has a resolution of $H \times W$ and each patch is $P \times P$, the model processes $N = \frac{HW}{P^2}$ tokens. The standard self-attention mechanism computes pairwise interactions between every single token, resulting in a computational and memory cost of $O(N^2)$. While manageable for static images, this quadratic scaling becomes a critical bottleneck when moving to the spatiotemporal domain—such as video processing, 3D scene understanding, or geographic forecasting.

The Spatiotemporal Token Explosion

In a video sequence with $T$ frames, the total number of tokens scales to $N_{\text{video}} = T \times N$. A naive application of global 3D self-attention requires computing an attention matrix of size $(T \times N) \times (T \times N)$. This means the computational complexity scales quadratically with both spatial resolution and temporal depth: $O(T^2 \cdot N^2)$.

As highlighted in a comprehensive survey on generative models by Hui Shen et al. in Efficient Diffusion Models: A Survey, this quadratic scaling severely restricts our ability to generate or analyze long-form, high-resolution video content.

Intuitively, full all-to-all attention across space and time is highly redundant. A patch showing a blade of grass in the top-left corner of the first frame rarely needs to compute its relationship with a bird flying in the bottom-right corner of the hundredth frame. Most pixels are either static or follow highly localized trajectories. To bypass this spatiotemporal token explosion, researchers have developed several core architectural paradigms that break the quadratic bottleneck.

Paradigm 1: Factorized Space-Time Attention

Instead of allowing every token to attend to every other token across all frames simultaneously, we can split the problem along its natural orthogonal axes. In a factorized (or divided) attention block, the operation is broken down into two sequential steps:

  1. Spatial Attention: Tokens only attend to other tokens within the same frame ($T$ independent attention operations of size $N \times N$).
  2. Temporal Attention: A token at a specific spatial coordinate only attends to tokens at that same coordinate across different frames ($N$ independent attention operations of size $T \times T$).

This factorization drops the complexity from $O(T^2 N^2)$ to $O(T N^2 + N T^2)$.

Naive 3D Attention:      [Space ✕ Time] ⟷ [Space ✕ Time]  (Quadratic Explosion)
Factorized Attention:    [Space ⟷ Space] ⟶ [Time ⟷ Time]   (Linear Additive Cost)

For example, Fengchuang Xing et al. leverage this divided space-time attention mechanism in StarVQA: Space-Time Attention for Video Quality Assessment to process high-resolution video without exceeding hardware memory limits. Similarly, in the context of snapshot compressive imaging, Ping Wang demonstrates in Hierarchical Separable Video Transformer for Snapshot Compressive Imaging that separating spatial and temporal operations avoids premature feature mixing and significantly optimizes reconstruction quality within strict memory budgets.

Paradigm 2: Sparse Windows and Coarse-to-Fine Guidance

Another strategy restricts the receptive field of attention to localized spatiotemporal windows, similar to how local neighborhoods are processed in 2D image models.

In Photorealistic Video Generation with Diffusion Models, Agrim Gupta et al. introduce a window-restricted transformer architecture (W.A.L.T) that confines self-attention to local spatiotemporal blocks. This bounds the quadratic cost to the size of the local window rather than the entire video volume.

However, purely local windows fail to capture long-range dependencies or fast-moving objects that quickly exit the window. To fix this, models can use a coarse-to-fine or drafting strategy. Xuan Shen et al. propose DraftAttention: Fast Video Diffusion via Low-Resolution Attention Guidance, which first computes a cheap, low-resolution "draft" attention map. This draft identifies which distant spatiotemporal regions are actually relevant, guiding a hardware-optimized sparse attention mechanism at full resolution and skipping irrelevant computations entirely.

Paradigm 3: Global Bottlenecks and Inter-Frame Communication

Rather than forcing frames to communicate by comparing all of their raw patches, we can introduce a small set of abstract "proxy" tokens that act as a shared memory bridge.

In Video Instance Segmentation using Inter-Frame Communication Transformers, Sukjun Hwang et al. introduce "inter-frame communication tokens." Instead of frame $A$ attending directly to frame $B$, each frame interacts only with a highly compressed set of global memory tokens.

Frame 1 Patches ───> [ Global Memory ] <─── Frame 2 Patches
                          │      │
                          ▼      ▼
                     Updated Frame Features

These memory tokens synthesize information across the entire sequence and broadcast it back out. This bypasses the quadratic explosion entirely, allowing the model to achieve state-of-the-art segmentation accuracy while running at real-time speeds (nearly 90 FPS).

Paradigm 4: Semantic Clustering and Permutation

Physical proximity in space and time does not always equal semantic relevance. A fast-moving object might jump across the screen, rendering local spatial windows ineffective, while static backgrounds remain identical but consume massive computational budgets.

To address this, Shuo Yang et al. develop Sparse VideoGen2: Accelerate Video Generation with Sparse Attention via Semantic-Aware Permutation. Instead of grouping tokens by their physical coordinates, they cluster and permute tokens based on their semantic meaning. By packing semantically related tokens into dense, contiguous blocks, they can apply standard, hardware-optimized dense attention operations on a much smaller subset of tokens, accelerating inference without degrading visual quality.

Paradigm 5: Linear State Space Models

A growing faction of research seeks to replace the attention mechanism altogether for temporal or spatiotemporal fusion, turning instead to State Space Models (SSMs) like Mamba. SSMs process sequential data recurrently by maintaining a running, fixed-size hidden state that compresses historical context, achieving a linear complexity of $O(N)$ relative to sequence length.

In 3D semantic occupancy prediction for autonomous driving, Ziming Zhu et al. introduce CSV-Occ: Fusing Multi-frame Alignment for Occupancy Prediction with Temporal Cross State Space Model and Central Voting Mechanism, replacing heavy voxel-matching attention with a linear-complexity Cross-SSM.

Similarly, for video super-resolution, Shijun Shi et al. propose Self-supervised ControlNet with Spatio-Temporal Mamba for Real-world Video Super-resolution, demonstrating that Spatio-Temporal Mamba blocks can maintain global temporal context across high-resolution frames without the prohibitive memory overhead of 3D attention.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

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

This exact version (version 2, frozen text):

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

These directions overlap with this one through shared papers.

See something wrong? Report a mistake