PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Scaling Video VLMs for Long Video Understanding

Cristobal Eyzaguirre, Jiajun Wu, Juan Carlos Niebles

arXiv:2605.31598v1cs.CV

TL;DR

Long-video VLMs face quadratic self-attention costs, and existing scalable approaches can lose information relative to full attention. StateKV uses a fixed-capacity importance-based recurrent state for linear-time video prefill while retaining a full per-frame cache for decoding, and it remains close to full attention across broad evaluations. The method also improves the compute-accuracy tradeoff, though its assumptions are validated only on tested models and inputs.

  • Problem

    Long-video VLMs need to integrate increasingly long frame sequences, but full self-attention makes video processing cost grow quadratically and existing reductions can lose information.

  • Method

    StateKV incrementally carries cross-frame context in a fixed-capacity importance-based temporal state while preserving all per-frame video tokens in a separate detailed cache for decoding.

  • Results

    Across multiple backbones, scales, and long-video benchmarks, StateKV remains close to full attention and consistently outperforms sliding-window or recency-based streaming approximations.

  • Takeaways & Limitations

    StateKV reduces video-prefill cost enough to support operating points where a larger StateKV model is cheaper and more accurate than a smaller full-attention baseline.

  • Takeaways & Limitations

    The mechanistic assumptions are validated only on existing models and tested inputs, so untested or future backbones may behave differently.

Abstract

from arXiv · show

Video vision-language models (VLMs) are increasingly used in long-horizon and streaming settings, yet most video encoders still rely on spatiotemporal self-attention, causing compute and latency to grow quadratically with the number of frames. Existing efficiency methods improve scalability but often lose accuracy relative to full self-attention, for example through aggressive frame/token dropping or coarse attention approximations. We introduce StateKV, an inference-time method that adapts pretrained long-video VLMs to linear-time video prefill by carrying cross-frame context in a fixed-capacity, importance-based recurrent state, paired with a second full per-frame cache used for decoding. Across three long-video benchmarks and seven models spanning three families and multiple scales, StateKV remains close to full self-attention and consistently outperforms dominant sliding-window / recency-based streaming approximations, without fine-tuning or architectural changes. StateKV also reduces video-prefill cost measured FLOPs, enabling stronger accuracy at a fixed compute budget by running larger models. These results suggest a practical step toward scalable long-video understanding.

1 Introduction

Long-video VLMs face quadratic video-processing costs, while existing efficiency methods often trade away information or rely on ad-hoc recency heuristics. StateKV instead carries important cross-frame context in a fixed-capacity state while retaining detailed per-frame tokens, yielding linear video encoding and results close to full attention.

  • Long-video VLM processing scales quadratically because each frame attends over all preceding video tokens.This creates a bottleneck for real-time, long-horizon applications.
  • Aggressive frame, token, or KV-cache compression can substantially degrade long-video performance unless much visual information is retained.
  • Streaming-prefill methods reduce video-prefill complexity from O(N^2) to O(N) while retaining all per-frame visual tokens for decoding.Their generation-stage cost remains O(N) in the number of frames.
  • StateKV approximates full self-attention by preserving a small set of slowly evolving temporal-sink tokens between frames.The approach is motivated by attention concentrating within frames and on a small set of long-range temporal tokens.
  • StateKV uses a fixed-capacity temporal state for cross-frame context and a detailed per-frame cache for decoding, producing O(N) video encoding.It adapts frozen pretrained VLMs without changing the final full-token decoding context.
  • Across three benchmarks and multiple model families and scales, StateKV stays close to full attention and outperforms sliding-window or recency-based streaming approximations.It requires no fine-tuning or architectural changes and improves the compute-accuracy tradeoff by enabling larger models at a fixed budget.

2 Related Work

Long-video efficiency work spans token reduction, architectural changes, fixed-budget compression, and streaming-prefill methods. StateKV occupies an intermediate position by compressing only the running prefill state while preserving full per-frame detail for decoding.

  • Vision language models and the long-video bottleneck: Video VLMs aggregate information across many frames, making video-side prefill a dominant cost as duration grows.
  • Token reduction without changing asymptotic order: Token-reduction methods reduce frames or visual tokens without changing the underlying sequence-processing order.Atemporal baselines show that some VideoQA benchmarks can perform strongly with single-frame selection.
  • Long-video and streaming video inference with changed complexity: Hybrid long-video architectures can achieve linear-time processing but require architectural changes and costly training.
  • Long-video and streaming video inference with changed complexity: Fixed-budget schemes compress or regulate the video KV cache to support longer videos or unbounded streams.
  • Long-video and streaming video inference with changed complexity: Streaming-prefill methods such as ReKV reduce video encoding with sliding windows while retaining accumulated per-frame tokens for decoding.Follow-up systems optimize generation through hierarchical memories, retrieval, compression, or streaming cache construction.
  • StateKV's position among related methods: StateKV differs from ReKV by carrying an importance-based fixed-capacity temporal cache rather than imposing a strict sliding-window view of the past.Its second cache preserves full per-frame visual detail for final generation.
  • KV-cache compression for long-context models: KV-cache research includes eviction, sparsification, compression, and adaptive budgeting, but long-video prefill has distinct frame-based attention structure.
  • StateKV's position among related methods: StateKV's transformer-layer design processes frames with a frozen backbone and separates compressed prefill context from the full decoding state.

3 Method

StateKV builds video KV caches frame by frame using a fixed-capacity, attention-selected temporal state for cross-frame context and a growing detailed state for decoding. Its design assumes concentrated, slowly evolving temporal sinks and applies consistent positional handling during cache construction and generation.

  • 3.1 Core Assumptions: StateKV assumes most inter-frame attention mass concentrates on K historical temporal sinks with K much smaller than the number of prior tokens.This motivates limiting cross-frame attention to a fixed-capacity temporal memory.
  • 3.1 Core Assumptions: The temporal sink set is assumed to evolve slowly, so the next state can be updated from the previous state and the current frame.The update evicts low-importance entries and admits newly salient current-frame tokens.
  • 3.1 Core Assumptions: Because all video tokens remain available for text decoding, temporal sinks only need to approximate video-only frame-to-frame interactions.StateKV therefore selects sinks from video-only attention without modeling text-query effects on sink identities.
  • 3.2 Method Overview: The method maintains a growing detailed state containing all per-frame tokens and a fixed-capacity compressed state used only during cache construction.The detailed state is for final decoding, while the compressed state is the only prior-frame context available to the next frame.
  • 3.3 Per-frame cache-builder forward pass: For each frame, the cache builder attends to the compressed memory and current-frame tokens, then appends the resulting per-layer keys and values to the detailed state.This restricts cross-frame interaction to the fixed-size compressed state while preserving all frame tokens for decoding.
  • 3.3 Per-frame cache-builder forward pass: Attention-driven selection refreshes the compressed state by retaining the top-B candidates from the prior memory and current frame.The resulting temporal cache is capacity-limited and updated incrementally rather than recomputed over the full prefix.
  • 3.3 Per-frame cache-builder forward pass: StateKV maintains virtual sequence positions for RoPE even when physical compressed-cache length is smaller than the number of processed tokens.
  • 3.3 Per-frame cache-builder forward pass: The same RoPE scaling parameters are used during cache building and generation so cached keys and values remain compatible with later queries.Changing the scaling after cache construction causes severe degradation.

4 Results

Across long-video benchmarks, StateKV preserves accuracy more effectively than sliding-window approximations while reducing video-prefill compute from quadratic to linear scaling. These savings support stronger compute-accuracy tradeoffs and larger models at comparable budgets.

  • Pareto frontier: StateKV traces a stronger compute-accuracy frontier than ReKV as cache budgets increase, despite the expected accuracy-compression tradeoff.Its operating points follow a smooth log-linear relationship between compute and accuracy.
  • Compute-accuracy tradeoff: 62.5% accuracy is achieved by StateKV-8B with B = 4096 at similar compute cost to Full SA-1B at 46.2%.The comparison illustrates how reduced prefill cost can be reinvested in model scale.
  • Cross-backbone results: StateKV stays close to Full SA while consistently outperforming ReKV across three benchmarks, model families, and parameter scales.ReKV with a 16-frame retrieval window and StateKV with B = 4096 are compute-matched.
  • Scaling behavior: StateKV remains closer to Full SA than ReKV at comparable compute across short, medium, and long videos.The trend holds across InternVL3-1B/2B/8B and increasing context budgets.
  • Baseline behavior: ReKV shows unstable behavior across settings and can remain substantially below Full SA even at its highest tested sliding-window budgets.The reported instability includes degradation for InternVL3-2B and on MLVU for InternVL3-8B.
  • Compute scaling: Full SA has quadratic video-prefill cost, whereas StateKV has linear cost in the number of frames.Marginal and cumulative break-even intersections identify horizons where larger StateKV models become cheaper than smaller Full SA baselines.

5 Conclusion

StateKV approximates long-video self-attention by carrying a small importance-based token state between frames while retaining detailed per-frame information for decoding. Across diverse models and benchmarks, it stays closer to Full SA than sliding-window baselines and improves the compute-accuracy tradeoff, although its mechanistic assumptions are validated only on tested models and inputs.

  • Method: StateKV uses a streaming cache-construction stage with importance-based carried tokens and final text decoding over retained detailed video state.The design replaces a strict sliding-window prior with an approximation to full self-attention.
  • Main result: Across multiple backbones, scales, and benchmarks, StateKV stays closer to Full SA than sliding-window baselines while reducing video-prefill complexity from quadratic to linear.The conclusion reports the same qualitative pattern across the evaluated settings.
  • Practical consequence: StateKV produces a better measured FLOPs-based compute-accuracy tradeoff by enabling larger backbones at comparable or lower cost than smaller Full-SA baselines.Its small accuracy loss under compression can be offset by increasing model scale.
  • Interpretation: The analyzed attention patterns are not well described by a pure sliding-window view, helping explain why strict recency approximations can be weak in this setting.The evidence supports a narrower interpretation tied to the analyzed cases.
  • Limitations: Mechanistic validation is limited to existing models and tested inputs, so untested backbones or future models may not exhibit the same behavior.The paper calls for broader analysis across backbones and video regimes.

A Empirical validation of the assumptions

The empirical analysis tests whether useful inter-frame attention is concentrated in a small historical token set and whether that state changes slowly enough for incremental recovery. It uses unmodified Full SA on sampled long videos, providing representative rather than universal evidence for these assumptions.

  • Assumptions: The analysis tests two assumptions: useful inter-frame attention is concentrated in a small historical token set, and the temporal state evolves slowly.These assumptions motivate recovering the next state from the previous state and current frame.
  • Scope: The validation is mechanistic rather than exhaustive and probes InternVL3-1B/2B/8B on 16 long videos from the VideoMME training split.Cache budgets include B ∈{1, 4, 16, 64, 256, 1024, 4096, 16384}.
  • Data: Each video contributes 128 frames sampled approximately uniformly over its full duration using the InternVL3 video loader.The subsection treats these cases as representative supporting evidence.
  • Protocol: The protocol runs unmodified Full SA frame by frame, aggregates video-only attention over current-frame queries, and forms the reported statistics.StateKV separately maintains and prunes sinks within each layer and KV head, while this analysis targets higher-level layerwise assumptions.

A.1 Assumption 1: concentration of inter-frame attention

StateKV’s first assumption is that most useful cross-frame attention concentrates on a small set of historical tokens. Measurements across model scales support this bounded-sink pattern, especially in middle layers.

  • Assumption: Assumption 1 posits that most useful cross-frame attention is concentrated on a relatively small set of historical tokens.This supports replacing unbounded cross-frame memory with a fixed-capacity temporal-sink state.
  • Measurement: The concentration analysis measures the fraction of historical attention mass captured by the top-B historical tokens from earlier frames.Attention is aggregated over heads and queries belonging to the current frame, while the key set includes all available tokens.
  • Measurement: The concentration curves should rise rapidly and saturate before B reaches the full historical context if the bounded-sink assumption holds.This is the stated empirical signature used to evaluate Assumption 1.
  • Evidence: At B = 256, the mean captured historical attention mass is 0.71/0.69/0.72 for 1B/2B/8B, increasing to 0.93/0.93/0.93 at B = 4096.These values come from 16-video, 128-frame runs and show that relatively small budgets capture most inter-frame attention mass.
  • Evidence: Historical attention concentration is high in most layers across all three scales, with the first few and last few layers as the main outliers.The bounded-sink behavior is therefore strongest in middle layers and somewhat weaker near the network ends.

A.2 Assumption 2: slow evolution of the temporal state

StateKV’s second assumption is that the useful temporal state evolves slowly enough to be recovered from the previous state and the current frame. Weighted recall supports this incremental-update premise, despite turnover among lower-importance tokens.

  • Assumption: Assumption 2 states that the next useful sink set can be approximated from the previous state together with the current frame.This is the empirical basis for incrementally updating the temporal state rather than recomputing it over the entire video prefix.
  • Methodology: The oracle state is the top-B state over all tokens seen through frame n, and the candidate pool combines the previous state with frame n+1.Candidate-pool recall measures how well this incremental pool covers the next oracle state.
  • Evidence: Weighted candidate-pool recall is 0.90/0.95/0.92 at B = 16 and 0.96/0.97/0.96 at B = 256 for the 1B/2B/8B runs.The weighted metric emphasizes preservation of the highest-mass oracle tokens even when exact set overlap is imperfect.
  • Evidence: Retention at B = 1 is 0.81/0.89/0.85 for 1B/2B/8B, indicating that the top-1 oracle token often persists between consecutive frames.At larger budgets, exact membership changes substantially while weighted recall remains high.
  • Interpretation: The temporal state contains a stable core of high-importance tokens alongside a broader band of medium-importance tokens that turns over more quickly.This structured turnover remains compatible with the incremental update rule, which requires recoverability rather than global static membership.

A.3 Supporting comparison: recency-based retention

The comparison tests whether attention-based historical-token selection captures more relevant context than pure recency retention during streaming video prefill. Across model scales and practical budgets, attention-based selection captures substantially more historical attention mass, while kernel-aware implementations improve StateKV latency.

  • Comparison with recency retention: Attention-based selection captures substantially more historical attention mass than recency retention at comparable practical budgets across InternVL3-1B/2B/8B.The gap is about 0.59/0.57/0.62 at 256 tokens versus 1 frame and 0.59/0.57/0.61 at 1024 tokens versus 4 frames.
  • Comparison with recency retention: The attention pattern is not pure recency: first and last available frames attract most historical attention mass for many heads.Sliding windows preserve near-past tokens but systematically discard the oldest-frame anchor.
  • Kernel considerations: StateKV cache building requires attention weights or sufficient statistics, which typical fused FlashAttention/SDPA kernels do not expose.The reported comparison therefore uses eager attention for StateKV cache building and FlashAttention-2 for full self-attention.
  • Kernel considerations: The wall-time measurements report per-frame forward-pass latency after warmup on one NVIDIA L40S with batch size 1, not end-to-end dataset throughput.Each point processes one additional frame given the preceding cache and reports repeated-measurement error bars.
  • Kernel considerations: Despite the kernel mismatch, StateKV’s fixed-budget per-frame cost eventually beats full self-attention’s linearly increasing per-frame cost across InternVL3-1B/2B/8B.A custom Triton kernel reduces StateKV wall time and moves the crossover to shorter sequences than eager attention.

C.1 Marginal compute frontier

This section compares the cost of processing one additional frame after the preceding cache has been built, complementing total prefill cost for fixed-length videos. The qualitative result remains that StateKV stays approximately constant at fixed cache budgets while full self-attention grows with context.

  • Interpretation of the marginal frontier: Marginal cost measures the expense of processing one additional frame after the preceding cache is built, rather than total 512-frame prefill compute.This view is especially relevant to streaming deployment, where video grows continuously.
  • Interpretation of the marginal frontier: At fixed cache budgets, StateKV’s marginal cost remains approximately constant while full self-attention’s per-frame cost grows with previously seen tokens.The marginal frontier compares these per-frame operating costs directly against VideoMME accuracy.

C.2 Long-horizon compute scaling

The long-horizon analysis extends compute-break-even comparisons to 3600 frames, or roughly one hour at 1 FPS, making StateKV’s linear-versus-full-attention scaling separation visible. At sufficiently long horizons, larger StateKV models can become compute-favorable relative to smaller full-attention models.

  • Long-horizon extension: The analysis extends compute-break-even comparisons to 3600 frames, corresponding to roughly one hour of video at 1 FPS.It examines both marginal and cumulative FLOPs on linear and log scales.
  • Scaling behavior: Full self-attention’s marginal and cumulative costs keep growing with context, whereas StateKV remains approximately constant per frame at fixed cache budgets.The cumulative curves therefore exhibit quadratic-versus-linear separation.
  • Scaling behavior: Around 1800 frames, InternVL3-8B with the largest tested StateKV cache budget becomes cheaper than InternVL3-1B Full SA.This crossover is approximately half an hour at 1 FPS and illustrates the strongest long-horizon scaling result.
  • Scaling behavior: The long-horizon plots show that substantially larger backbones can become compute-favorable once attention cost is linearized.Log-scale panels make these crossover intersections easier to inspect than linear-scale panels at long horizons.
Loading 2605.31598v1…