Technical Summary: Linear Scaling Video VLMs for Long Video Understanding (StateKV)

1. Problem Statement

Video Vision-Language Models (VLMs) are increasingly critical for long-horizon and streaming applications, such as autonomous driving and embodied robotics, which require integrating evidence over minutes or hours. However, a fundamental bottleneck exists: the computational cost of processing long videos in standard VLMs grows quatically ($O(N^2)$) with the number of frames ($N$). This occurs because dominant architectures rely on spatiotemporal self-attention, where each frame attends to all previous video tokens.

Existing efficiency strategies attempt to mitigate this by:

1. Subsampling frames or tokens: Reducing input size often degrades performance significantly unless a large fraction of tokens is retained (e.g., ~60%).
2. Compressing the KV cache: Aggressive compression can lose temporal and spatial cues necessary for reasoning.
3. Sliding-window/Recency-based heuristics: Methods like ReKV process frames sequentially using a fixed window of recent frames. While these reduce prefill complexity to linear ($O(N)$), they rely on ad-hoc assumptions that the most relevant information is always recent, often failing to capture long-range dependencies required for complex reasoning.

The challenge is to achieve linear-time video prefill (constant per-frame cost) without sacrificing the accuracy of full self-attention or requiring architectural changes and fine-tuning.

2. Methodology: StateKV

The authors introduce StateKV, an inference-time method that adapts frozen, pretrained long-video VLMs to linear-time video prefill. The core insight is that long-video attention in pretrained VLMs is highly structured: while most interactions are within-frame, long-range temporal interactions concentrate on a small set of "temporal sink" tokens that evolve slowly over time.

Core Assumptions

StateKV is built on two empirical assumptions regarding attention in pretrained VLMs:

1. Concentration of Inter-frame Attention: For any given frame, the majority of useful cross-frame attention mass is concentrated on a small set of historical tokens ($K \ll N$), regardless of the total video length.
2. Slow Evolution of Temporal State: The set of these "sink" tokens evolves slowly. The useful state for frame $n+1$ can be well-approximated by the state from frame $n$ combined with the tokens from frame $n+1$.

Architecture and Mechanism

StateKV operates via a two-cache structure per transformer layer, maintaining a frozen backbone:

1. Detailed State ($D_n$): A full-length cache that stores all visual tokens from every frame processed so far. This cache is never queried during the prefill stage but is preserved for the final text decoding stage to ensure no information is lost during generation.
2. Compressed State ($C_n$): A fixed-capacity, recurrent state (e.g., 1024 tokens) used only during the video prefill stage to approximate cross-frame interactions.

The Process:

• Streaming Prefill: As frames arrive, the model processes them incrementally. Frame $n$ attends to the concatenation of the current frame's tokens and the Compressed State from frame $n-1$.
• Importance-Based Selection: After processing frame $n$, the Compressed State is updated. The model calculates attention scores (video-only) for all candidate tokens (the previous compressed state + current frame tokens). It selects the top-$B$ tokens (where $B$ is the fixed budget) to form the new Compressed State $C_n$, evicting low-importance entries.
• Decoding: Once all frames are processed, standard autoregressive text generation begins. Crucially, decoding conditions on the Detailed State ($D_N$), which contains all original video tokens, ensuring the generation phase has access to the full context.

This design decouples the complexity of video encoding (linear, $O(N)$) from the fidelity of the final generation (full context).

3. Key Contributions

• Linear-Time Prefill without Fine-Tuning: StateKV enables frozen pretrained VLMs to process long videos with linear computational complexity ($O(N)$) and constant per-frame cost, without requiring architectural modifications or retraining.
• Principled Approximation of Full Attention: Unlike sliding-window methods that rely on recency, StateKV uses an importance-based mechanism to carry forward "temporal sinks." This provides a more principled approximation of full self-attention, capturing long-range dependencies that recency-based heuristics miss.
• Compute-Accuracy Tradeoff: By drastically reducing the FLOPs required for video prefill, StateKV allows practitioners to run larger models within the same compute budget. The paper demonstrates that a larger model with StateKV can outperform a smaller model using full self-attention at a similar or lower computational cost.
• Empirical Validation: The method is validated across three long-video benchmarks (VideoMME, MLVU, OVOBench) and seven models spanning three families (InternVL3, Qwen-VL, Eagle2.5) and multiple scales (1B to 8B parameters).

4. Results

• Accuracy vs. Full Self-Attention: Across all benchmarks and model scales, StateKV remains close to full self-attention (Full SA) performance. On average, it stays within roughly 1% of Full SA accuracy, significantly outperforming sliding-window baselines like ReKV (which often lag by ~10 points).
• Superiority over Recency-Based Methods: StateKV consistently outperforms ReKV (a dominant sliding-window method) across VideoMME, MLVU, and OVOBench. The authors attribute this to the fact that long-range attention patterns in VLMs are not purely recency-based; they often rely on persistent "anchors" from distant frames that sliding windows discard.
• Scaling Behavior: Performance improves monotonically as the compressed state capacity ($B$) increases. Larger models exhibit stronger scaling with cache size, often matching Full SA accuracy at high budgets.
• Compute Efficiency:
  • StateKV reduces video-prefill FLOPs dramatically.
  • Break-even Analysis: For sufficiently long videos, running a larger model (e.g., InternVL3-8B) with StateKV is computationally cheaper than running a smaller model (e.g., InternVL3-1B) with Full Self-Attention.
  • Example: StateKV-8B with a cache budget of 4096 achieves 62.5% accuracy on VideoMME at a compute cost similar to Full SA-1B (46.2% accuracy), effectively gaining ~16 points of accuracy for the same budget.

5. Significance and Claims

The paper positions StateKV as a practical step toward scalable long-video understanding. Its significance lies in:

• Enabling Real-Time Streaming: By achieving constant per-frame cost, StateKV removes the quadratic bottleneck that currently rules out real-time streaming applications for long videos (e.g., a car driving for an hour becomes harder to query than one just starting).
• Redefining the Compute Frontier: The method shifts the paradigm from "compressing to fit" to "compressing to approximate." It demonstrates that importance-based memory retention is a stronger approximation of full attention than strict recency, allowing for better accuracy at fixed compute budgets.
• Generalizability: The approach transfers consistently across different model families and parameter scales without requiring model-specific tuning, suggesting that the underlying attention structure (temporal sinks) is a robust property of current pretrained VLMs.

The authors acknowledge limitations, noting that the mechanistic validation is currently limited to existing models and tested inputs. They suggest that future work should explore whether these attention patterns hold across broader backbones and video regimes. However, within the tested scope, StateKV offers a robust, training-free solution to the long-video scaling problem.