Linear Scaling Video VLMs for Long Video Understanding¶

Conference: ECCV 2026
Paper: ECCV 2026
Code: https://ceyzaguirre4.github.io/StateKV
Area: Multimodal VLM
Keywords: Long-Video Understanding, Video VLMs, KV Cache Compression, Linear Scaling, Streaming Prefill

TL;DR¶

To eliminate the quadratic compute and latency explosion in video VLM prefill, StateKV decouples streaming prefill from decoding on frozen backbones using a fixed-capacity, importance-based recurrent state that preserves temporal sinks, achieving strictly constant per-frame compute and global \(O(N)\) linear complexity.

Background & Motivation¶

Modern video vision-language models (VLMs) are increasingly deployed in long-horizon and streaming environments such as autonomous driving, embodied robotics, and continuous monitoring, where models must aggregate visual cues over minutes or hours. However, dominant video-LLM architectures rely on dense spatiotemporal self-attention across all visual tokens. As a video progresses, each newly arrived frame must attend to tokens from every preceding frame, causing the incremental per-frame computational cost to scale linearly with the number of processed frames and inflating the cumulative video prefill complexity to quadratic \(O(N^2)\). For real-time autonomous systems, this scaling creates a severe operational bottleneck: an autonomous vehicle that has driven for an hour experiences far higher latency to answer a visual query than one that has just departed.

Existing efficiency techniques for long videos typically compress input sequences through uniform frame subsampling, early visual token pruning, or fixed-budget KV cache reduction. However, multi-frame procedural reasoning and fine-grained visual search heavily depend on subtle spatiotemporal cues; aggressive token dropping (e.g., pruning over 40% of tokens) severely impairs long-horizon reasoning. Crucially, reducing sequence length merely shifts the constant factor without altering the quadratic scaling law. Another line of research investigates streaming prefill approaches, such as ReKV, which decouple video prefill from generation but rely heavily on rigid sliding-window heuristics. Enforcing a strict recency prior discards long-range global context and frequently leads to severe attention degradation and semantic discontinuity across extended sequences.

The key insight of this paper stems from an empirical analysis of attention structures in pretrained video VLMs: attention weights are dominated by intraframe spatial interactions, while cross-frame temporal interactions concentrate heavily on a compact set of "temporal sink" tokens that evolve gradually over time. Core idea: frame streaming video prefill as approximating full self-attention via a compact set of carried tokens, introducing a two-cache KV mechanism that maintains a fixed-capacity, attention-driven compressed state for \(O(1)\) cross-frame interaction during prefill alongside a detailed cache storing all per-frame tokens for decoding, achieving linear \(O(N)\) video understanding without any fine-tuning.

Method¶

Overall Architecture¶

StateKV operates on frozen pretrained video VLMs and bifurcates the inference workflow into two distinct phases: a frame-by-frame streaming video prefill stage and an autoregressive text decoding stage. During prefill, the model sequentially ingests \(N\) video frames (each comprising \(T\) visual tokens). Within each Transformer layer, StateKV maintains two separate KV caches: a detailed state (\(\mathcal{D}^\ell_n\)) that retains all processed tokens for final language generation, and a fixed-capacity compressed state (\(\mathcal{C}^\ell_n\)) capped at budget \(B\) that serves exclusively as the cross-frame context for subsequent frames.

When processing frame \(n\), the visual tokens attend only to the concatenation of the previous compressed state \(\mathcal{C}^\ell_{n-1}\) and the current frame's tokens. This restricts the marginal computation per frame to a constant \(O(T^2 + BT)\), reducing the total prefill complexity from \(O(N^2 T^2)\) to \(O(N(T^2 + BT))\). After completing the prefill pass across all \(N\) frames, the model executes standard autoregressive decoding conditioned on the full detailed state \(\mathcal{D}^\ell_N\), thereby preserving all high-resolution spatial and temporal evidence required for downstream generation.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input frame n visual features X_n"] --> B["Dual-State Decoupled Architecture<br/>Frame queries attend over [C_{n-1}; K_n]"]
    B --> C["Attention-Driven Dynamic Temporal Sink Update<br/>Score candidate pool and retain Top-B"]
    C --> D["Virtual Sequence Length & Consistent RoPE Scaling<br/>Derive positions from logical stream timestamps"]
    D --> E["Dual Cache Storage<br/>Pass updated C_n to frame n+1, append to D_n"]

Key Designs¶

1. Dual-State Decoupled Architecture: Separating Prefill Compute Bottlenecks from Decoding Detail

Conventional long-video inference couples prefill feature propagation with generation memory inside a single growing KV cache, progressively slowing down later frames. StateKV resolves this tension by decoupling the cross-frame context required during prefill from the visual detail required during generation. For each layer \(\ell\), the system maintains the detailed cache \(\mathcal{D}^\ell_n = \{ (K^\ell_{1:n}, V^\ell_{1:n}) \}\) and the compressed memory \(\mathcal{C}^\ell_n = \{ (\bar{K}^\ell_n, \bar{V}^\ell_n) \}\) with \(|\bar{K}^\ell_n| = B\). During the forward pass of frame \(n\), projected queries \(Q^\ell_n\) attend over the concatenated keys and values:

\[\text{Attn}\left(Q^\ell_n, [\bar{K}^\ell_{n-1}; K^\ell_n], [\bar{V}^\ell_{n-1}; V^\ell_n]\right) = \text{softmax}\left(\frac{Q^\ell_n [\bar{K}^\ell_{n-1}; K^\ell_n]^\top}{\sqrt{d_h}} + M_n\right) [\bar{V}^\ell_{n-1}; V^\ell_n]\]

Because historical detailed tokens in \(\mathcal{D}^\ell_{n-1}\) are never queried during prefill, quadratic compute growth across frames is eliminated. Meanwhile, retaining \(\mathcal{D}^\ell_N\) for text decoding ensures that fine-grained localized evidence remains intact when answering questions.

2. Attention-Driven Dynamic Temporal Sink Update: Top-K Working Memory via Gradual Evolution

Sliding-window heuristics abruptly truncate early video history, losing global anchor information. StateKV capitalizes on the observation that temporal attention sinks are sparse and evolve slowly across consecutive frames. At layer \(\ell\), after computing frame \(n\)'s self-attention, StateKV constructs a candidate pool \(U^\ell_n = \bar{S}^\ell_{n-1} \cup \{1, \dots, T\}\) combining the current compressed indices with all \(T\) tokens of frame \(n\). For any candidate key token \(j \in U^\ell_n\), its importance score is computed by averaging attention weights across all \(T\) queries in frame \(n\):

\[s^\ell_{n,j} = \frac{1}{T} \sum_{i=1}^T A^\ell_{n,i,j}\]

The top-\(B\) scoring candidates are selected to form the updated index set \(\bar{S}^\ell_n = \text{TopK}(\{s^\ell_{n,j} : j \in U^\ell_n\}, B)\), forming the updated cache \(\mathcal{C}^\ell_n\). This constant-time update dynamically evicts non-essential tokens while carrying forward durable temporal anchors and salient new features, bypassing the information loss inherent in rigid recency windows.

3. Virtual Sequence Length & Consistent RoPE Scaling: Enforcing Temporal Coordinate Coherence

Because the physical length of \(\mathcal{C}^\ell_n\) is capped at \(B\) while the logical stream advances by \(T\) tokens per frame, standard position indices would cause severe distortion in Rotary Position Embeddings (RoPE). Furthermore, modifying RoPE scaling factors mid-stream invalidates cached key representations. StateKV introduces a virtual sequence length \(L_n = nT\) that indexes tokens according to their true chronological positions in the stream, regardless of cache compaction. Prior to prefill, the maximum total sequence length (video frames plus user prompt plus max generation length) is calculated to configure a fixed RoPE scaling factor \(\alpha\) (e.g., via YaRN). This factor \(\alpha\) remains strictly invariant across both cache construction and language decoding, ensuring seamless mathematical alignment between the detailed cache \(\mathcal{D}^\ell_N\) and generated output tokens.

Key Experimental Results¶

Main Results¶

Evaluations were conducted at 1 FPS up to 512 frames across VideoMME (without subtitles), MLVU, and OVOBench (Real-Time Visual Perception subset). Baselines include exact Full Self-Attention (Full SA) and the sliding-window baseline ReKV (\(R=16\) frames, which is compute-matched to StateKV with \(B=4096\)).

Model	Method	VideoMME (%)	MLVU (%)	OVOBench (Real-Time, %)
InternVL3-1B	Full SA	46.19	47.05	55.79
InternVL3-1B	ReKV (R=16)	37.11	33.44	37.75
InternVL3-1B	StateKV (B=4096)	45.80	46.35	55.44
InternVL3-2B	Full SA	55.81	56.61	60.22
InternVL3-2B	ReKV (R=16)	31.78	5.49	33.33
InternVL3-2B	StateKV (B=4096)	54.15	57.31	61.05
Qwen3-VL-2B	Full SA	58.67	58.83	60.45
Qwen3-VL-2B	ReKV (R=16)	49.44	45.60	46.71
Qwen3-VL-2B	StateKV (B=4096)	58.00	57.72	60.93
Qwen3-VL-4B	Full SA	66.59	68.98	64.76
Qwen3-VL-4B	ReKV (R=16)	52.63	49.91	49.22
Qwen3-VL-4B	StateKV (B=4096)	65.89	67.80	64.87
InternVL3-8B	Full SA	64.19	61.14	71.45
InternVL3-8B	ReKV (R=16)	54.56	31.11	56.03
InternVL3-8B	StateKV (B=4096)	62.52	62.85	70.25
Eagle2.5-8B	Full SA	69.81	73.85	69.30
Eagle2.5-8B	ReKV (R=16)	58.70	55.01	55.44
Eagle2.5-8B	StateKV (B=4096)	67.96	70.52	68.70
Qwen3-VL-8B	Full SA	70.52	75.82	67.86
Qwen3-VL-8B	ReKV (R=16)	55.52	50.91	53.88
Qwen3-VL-8B	StateKV (B=4096)	68.11	71.38	64.99

Ablation Study¶

The ablation investigates the impact of the cache budget \(B\) on VideoMME accuracy and prefill FLOPs using InternVL3-8B at 512 frames, alongside comparisons to small Full SA baselines under equalized compute budgets.

Config / Cache Budget \(B\)	VideoMME (%)	Relative Prefill Compute (vs Full SA-8B)	Note
Full SA (8B)	64.19	1.00× (base)	Exact quadratic full self-attention
StateKV (\(B=16384\))	63.85	~0.65×	Near-lossless approximation of full attention
StateKV (\(B=4096\))	62.52	~0.33× (1/3rd)	Balanced setting: only 1.67% drop with 67% FLOPs reduction
StateKV (\(B=1024\))	59.80	~0.20×	Medium budget, substantially outperforming ReKV
StateKV (\(B=256\))	54.30	~0.12×	Low-memory edge configuration
ReKV (\(R=16\), compute-matched)	54.56	~0.33×	Sliding window drops 9.63% with severe variance
Full SA (1B)	46.19	~0.30×	Iso-compute 1B baseline under full attention

Key Findings¶

Closing the Full Self-Attention Gap: Across 7 models spanning 3 architectures and multiple parameter scales, StateKV consistently matches Full SA within ~1 percentage point while outperforming compute-matched ReKV by approximately 10 points on average.
Robustness Against Window Degradation: ReKV experiences catastrophic failures on specific models (e.g., falling from 56.61% to 5.49% on InternVL3-2B on MLVU), whereas StateKV maintains 57.31%, demonstrating that importance-driven sink preservation avoids the structural collapse caused by rigid recency biases.
Compute Reinvestment Dividends: StateKV's FLOPs reduction allows practitioners to deploy larger backbones within the same computational budget. Under equivalent prefill FLOPs, running an 8B model with StateKV (\(B=4096\), 62.52%) yields a massive +16.33 point gain over a 1B model with Full SA (46.19%).

Highlights & Insights¶

Operationalizing Temporal Attention Sinks: Adapts the static attention-sink phenomenon from language models into dynamic video understanding, using query-averaged attention scores to sustain global context over long streams with zero parameter updates.
Asymmetric Memory Decoupling: Recognizes that intermediate prefill representations require only a lightweight temporal summary, whereas question answering requires granular spatial-temporal detail, successfully overcoming the trade-off between \(O(N)\) computation and fine-grained localization.
Predictable Pareto Scaling: Traces a smooth log-linear relationship between context budget \(B\) and accuracy, providing a reliable knob for balancing latency, memory, and performance in streaming systems.

Limitations & Future Work¶

Reliance on Backbone Sink Emergence: The core mechanism presumes that the underlying model naturally concentrates long-range dependencies onto identifiable temporal sinks; architectures trained without causal anchoring or under localized windowing might exhibit weaker sink structures.
Linear Memory Footprint During Decoding: While video prefill compute scales strictly linearly with constant per-frame cost, storing the detailed cache \(\mathcal{D}_N\) for decoding still consumes memory proportional to the total number of frames. Integrating selective token eviction during the final decoding stage represents an important direction for scaling to unbounded durations.

vs ReKV: ReKV similarly decouples prefill from decoding but enforces a static sliding window that drops distant history. StateKV replaces the recency heuristic with an importance-based recurrent state, avoiding catastrophic degradation on long-horizon reasoning.
vs H2O / SnapKV: Language cache eviction techniques compress the generation-time KV cache. StateKV specifically targets the quadratic video prefill bottleneck and utilizes the structural disparity between intraframe spatial and interframe temporal attention.

Rating¶

Novelty: ⭐⭐⭐⭐☆ Principled formulation of streaming video prefill as attention approximation via dynamic temporal sinks.
Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive cross-family validation across 7 models, 3 long-video benchmarks, and rigorous compute-matched Pareto profiling.
Writing Quality: ⭐⭐⭐⭐⭐ Precise mathematical modeling, logical exposition, and detailed empirical ablations.
Value: ⭐⭐⭐⭐⭐ Delivers an immediately applicable, training-free solution to the quadratic scaling bottleneck in long-video VLM deployment.