StateKV: Linear-Time Video Understanding Through Recurrent State Compression

Paper: 2605.31598 Authors: Cristobal Eyzaguirre, Jiajun Wu, Juan Carlos Niebles Categories: cs.CV

The Gap

Video vision-language models process long videos using spatiotemporal self-attention, which scales quadratically with frame count. Existing efficiency methods—aggressive frame dropping, sliding windows, or coarse attention approximations—trade accuracy for speed. The field has reached a point where models can handle long videos, but deployment in streaming or real-time settings remains impractical due to compute and latency constraints. Prior work either accepts the quadratic cost or sacrifices too much accuracy when approximating full attention.

Problem: Quadratic scaling in video VLMs
   |
   v
Existing solutions: Frame dropping / Sliding windows / Attention approximation
   |
   +---> Trade accuracy for efficiency
   |
   v
Gap: Can we achieve linear scaling WITHOUT losing accuracy?
   |
   v
Assumption: Cross-frame context can be compressed into fixed-size state
   |
   v
Method: StateKV (importance-based recurrent state + per-frame cache)
   |
   v
Evidence: Matches full attention, beats baselines across 3 benchmarks, 7 models
   |
   v
Conclusion: Linear-time video prefill is practical without fine-tuning

The Increment

One sentence: Before this paper, long-video VLMs chose between quadratic compute or accuracy loss; after, they can process videos in linear time while preserving full-attention accuracy through inference-time state compression.

Core Mechanism

StateKV operates during the video prefill phase—when the model first processes all video frames before generating text. It maintains two separate caches: a fixed-capacity recurrent state that carries compressed cross-frame context forward, and a full per-frame cache used during text generation.

The recurrent state works by selecting the most important key-value pairs from each frame based on attention scores, evicting less important entries when capacity is reached. As each new frame arrives, the model attends to both the recurrent state (containing compressed history) and the current frame’s full tokens. Important tokens from the current frame are then merged into the recurrent state for future frames. This creates a rolling window of compressed context that grows linearly with video length rather than quadratically.

During text decoding, the model switches to using the full per-frame cache, ensuring no information loss when generating responses. The recurrent state is only used for video-to-video attention during prefill, not for text generation.

Video Frames:  [F1] --> [F2] --> [F3] --> ... --> [Fn]
                 |        |        |               |
                 v        v        v               v
              +-----+  +-----+  +-----+         +-----+
Prefill:      | Attn|  | Attn|  | Attn|   ...   | Attn|
              +-----+  +-----+  +-----+         +-----+
                 |        |        |               |
                 v        v        v               v
            [Recurrent State: Fixed Capacity]
            [Select top-K KV pairs by importance]
            [Evict low-importance entries]
                 |
                 +---> Compressed cross-frame context
                 |
                 v
            [Per-frame Cache: Full KV for decoding]
                 |
                 v
              Decode text tokens using full cache

Think of StateKV like a news editor covering a multi-day event. The recurrent state is the editor’s running summary—each day, they read new developments (current frame), update their mental model by keeping the most important facts (importance-based selection), and discard minor details to avoid cognitive overload (fixed capacity). The per-frame cache is the full archive of daily reports. When writing the final article (text generation), the editor consults the complete archive, not just the summary. The summary’s job is to help the editor understand each new day’s events in context, not to replace the archive.

Key Concepts

• Recurrent State with Importance-Based Eviction: Traditional attention keeps all past tokens, causing quadratic growth. StateKV maintains a fixed-size buffer of key-value pairs, selecting which to keep based on attention scores from the current frame. When a new frame arrives and the buffer is full, the least-attended tokens are evicted. This is like a cache replacement policy, but for semantic importance rather than recency. Concretely: if the buffer holds 1000 KV pairs and frame 50 generates 200 new important tokens, the 200 least-important existing tokens are dropped. The buffer size stays constant, so compute scales linearly.

• Dual-Cache Architecture: StateKV uses two separate caches with different purposes. The recurrent state (small, compressed) is used only during video prefill to propagate cross-frame context. The per-frame cache (large, complete) stores all tokens from all frames and is used during text decoding. This separation allows linear-time video processing without sacrificing generation quality. The recurrent state answers “what context do I need to understand the next frame?” while the per-frame cache answers “what information do I need to generate accurate text?”

• Inference-Time Adaptation: StateKV requires no fine-tuning or architectural changes. It’s a drop-in replacement for the attention mechanism during inference. The pretrained model’s weights remain frozen; only the KV cache management strategy changes. This is powerful because it means any existing video VLM can be adapted immediately. The model never “knows” it’s using compressed context—from its perspective, it’s still doing standard attention, just with a different set of cached tokens.

Framework Shift

Before (Full Self-Attention):        After (StateKV):

Video frames:                        Video frames:
[F1][F2][F3]...[Fn]                 [F1][F2][F3]...[Fn]
  |   |   |      |                    |   |   |      |
  +---+---+------+                    v   v   v      v
  |                                 [Recurrent State]
  v                                 [Fixed capacity]
[All-to-all attention]              [Importance-based]
[Quadratic: O(n^2)]                      |
  |                                      v
  v                                [Selective attention]
[Full KV cache]                    [Linear: O(n)]
[Memory: O(n^2)]                        |
  |                                     v
  v                                [Per-frame cache]
[Decode]                           [Full KV for decode]
                                        |
                                        v
                                   [Decode]

From exhaustive cross-frame attention to selective context propagation, the core shift is replacing quadratic all-to-all dependencies with linear importance-filtered recurrence.

Expert Assessment

Problem choice: This is a real deployment bottleneck, not a manufactured gap. Video VLMs are moving toward streaming and long-horizon applications (robotics, surveillance, video QA), where quadratic scaling is a showstopper. The problem sits at the intersection of model efficiency and practical deployment—a high-value target. The framing is honest: they acknowledge existing efficiency methods and clearly state the accuracy-efficiency tradeoff they’re trying to break.

Method maturity: The core insight—importance-based state compression—is elegant but not groundbreaking. It’s essentially applying cache eviction policies from systems research to attention mechanisms. The dual-cache design is clever: it sidesteps the “lossy compression hurts generation” problem by only compressing during prefill. However, the method is somewhat brute-force in its reliance on attention scores as the sole importance metric. More sophisticated importance measures (gradient-based, uncertainty-based) might yield better compression. The lack of architectural changes is both a strength (easy adoption) and a limitation (can’t co-design the model for this compression scheme).

Experimental integrity: The evaluation is thorough—three benchmarks, seven models, three model families. Baselines are fair: they compare against sliding windows and recency-based methods, which are the dominant streaming approximations. The FLOPs analysis is a nice touch, showing that StateKV enables running larger models at the same compute budget. One red flag: no ablation on state capacity. How sensitive is accuracy to buffer size? The paper doesn’t explore the accuracy-memory tradeoff curve in depth. Also, all experiments are on long-video benchmarks; short-video performance (where full attention is feasible) isn’t reported, so we don’t know if there’s a regression.

Writing quality: The abstract and introduction are crisp. The method section is clear but could use more intuition-building before diving into implementation details. The related work section is thorough but reads like a checklist—it would benefit from a narrative arc showing how prior work led to this approach. The results section is dense with numbers but light on analysis: why does StateKV outperform sliding windows by different margins across models? What patterns emerge? The conclusion is generic and could be cut entirely.

Verdict: weak accept — Solid engineering contribution with clear practical value, but limited conceptual novelty and incomplete exploration of the method’s design space.

Takeaways

Importance-based eviction for attention caches: The idea of using attention scores to decide which KV pairs to keep is transferable beyond video. Any domain with long sequences (audio, genomics, time-series) could apply this. The key insight: not all tokens are equally useful for future context, and you can measure usefulness via attention weights.

Dual-cache pattern for lossy prefill + lossless decode: Compress aggressively during the “understanding” phase, but preserve full information during the “generation” phase. This pattern applies to any encoder-decoder or prefill-decode architecture where generation quality is more critical than encoding speed.

Inference-time adaptation as a deployment strategy: StateKV shows that you can adapt pretrained models to new efficiency constraints without retraining. This is a practical template: identify the bottleneck (quadratic attention), design a drop-in replacement (recurrent state), validate that accuracy holds. The “no fine-tuning required” property is underrated—it means faster iteration and lower deployment friction.

FLOPs-accuracy tradeoff reframing: Instead of “how do we make this model faster?”, ask “what larger model can we run at the same cost?” StateKV’s FLOPs savings enable running bigger models, which often yields better accuracy than running a smaller model faster. This reframing applies broadly: efficiency gains should be evaluated not just as speedups, but as budget reallocation opportunities.