Linear Scaling Video VLMs for Long Video Understanding

StateKV: Achieving Linear-Time Scaling for Long-Video Understanding in VLMs

Current AI models get much slower and more expensive as videos get longer. They try to remember everything at once. Most video vision-language models (VLMs) rely on spatiotemporal self-attention. This means the computational effort grows quadratically with the number of frames. This makes real-time streaming or analyzing hour-long footage nearly impossible on standard hardware.

StateKV solves this by keeping a small, smart "summary" of important moments. This approach reduces computational complexity from quadratic $O(N^2)$ to linear $O(N)$ in the number of frames. It achieves this without retraining the model or changing its architecture. This provides a practical path for deploying long-context video intelligence.

The Problem

The status quo for video VLMs hits a massive scaling wall. As a video progresses, every new frame must attend to every previous frame. This quadratic growth in compute and latency is a major bottleneck. A car driving for an hour is fundamentally harder to query than one that just started. As shown in, unmodified full self-attention incurs an increasing per-frame cost.

This eventually makes long-horizon reasoning computationally prohibitive.

Existing attempts to fix this usually involve "shrinking" the input. Engineers often resort to subsampling frames or trimming visual tokens. Others compress the KV cache (the memory used to store key-value pairs for attention). However, the authors note these methods often lose critical information. Aggressive compression can degrade performance unless you retain a massive fraction of the original tokens. Other methods use a "sliding window" to look only at the most recent $R$ frames. This is a blunt instrument. Recency-based heuristics often miss "temporal sinks" (specific tokens that hold long-range importance). This leads to the instability and performance drops seen in models like ReKV .

How It Works

StateKV shifts the paradigm from "forgetting the past" to "summarizing the past." The core choice is a dual-cache system. It decouples the heavy lifting of video encoding from the precision required for text decoding. As illustrated in, the method maintains two distinct memory states for every transformer layer:

1. The Compressed State ($cstate$): A fixed-capacity, importance-based recurrent state. During the video prefill stage (the initial processing of video frames), this state acts as a limited "working memory." It carries essential cross-frame context forward. Its size does not grow with the video length.
2. The Detailed State ($dstate$): A full-length cache that stores every visual token from every frame. This is used exclusively during the final text generation stage. This ensures the model has high-fidelity visual details when answering a query.

The magic happens in how the $cstate$ is updated. StateKV uses importance-based selection rather than a naive sliding window. After processing a frame, the model calculates attention scores. These scores identify which tokens are most "salient" (relevant to the current context). It then selects the top-$B$ tokens. It combines the most important tokens from the previous $cstate$ with the new tokens from the current frame. This relies on the observation that long-video attention is highly structured. Most interaction mass concentrates on a small set of "temporal sinks" that evolve slowly over time .

Numbers

The most significant takeaway is the compute-accuracy frontier. StateKV does not just save FLOPs (floating-point operations). It changes the math of what is possible within a fixed budget. As shown in, StateKV provides a much stronger Pareto frontier than existing methods.

The FLOP savings are large enough to justify running much larger models. For example, the paper reports that an InternVL3-8B model using StateKV (with $B=4096$) achieves 62.5% accuracy on the VideoMME benchmark. Meanwhile, a much smaller InternVL3-1B model using full self-attention only hits 46.2%. Both operate at a similar compute cost. This means you can trade a smaller model's exact attention for a larger model's improved reasoning.

Furthermore, the scaling is truly linear. The authors measure the "marginal FLOPs" (the cost of adding one more frame). They show that while full self-attention costs continue to climb, StateKV's marginal cost remains approximately constant .

This enables predictable, linear-time scaling for streaming applications.

What's Missing

While the results are impressive, there are gaps a practitioner should consider:

• Architectural Generalization: The mechanistic validation of the "temporal sink" assumption was performed on existing models. Specifically, it was tested on the InternVL3 family. The authors admit this is not proven to be a universal property of all future VLM architectures.
• Kernel Optimization Maturity: Speedups in wall-time comparisons rely on a custom Triton kernel (a language for writing high-performance GPU code). This kernel handles score accumulation efficiently . Without this specialized implementation, the "eager" attention path could introduce overhead. This might offset the algorithmic gains.
• Hyperparameter Sensitivity: Performance is heavily dependent on the cache budget $B$. The paper shows a smooth scaling relationship .

However, finding the optimal $B$ for a specific deployment target remains a manual task. You must balance latency against accuracy.

Should You Prototype This

Yes, specifically if you are building streaming video applications. This includes handling long-horizon video QA.

StateKV is an inference-time method. It requires no fine-tuning or architectural changes. The barrier to entry is low. If your current bottleneck is the quadratic explosion of latency, this is the tool you need. The ability to swap a small model for a much larger model without increasing your FLOP budget is a massive win. Code is reportedly available; see the paper for the canonical link.