TL;DR
CoRDS introduces a training-free, query-agnostic approach to streaming video understanding by reframing key-value (KV) cache compression as a geometric coreset selection problem. By selecting a diverse, non-redundant subset of tokens that globally covers a joint key-value feature space, CoRDS dramatically reduces memory footprints while matching or even exceeding the performance of uncompressed models.
What Problem Does This Paper Address?
Deploying Large Vision-Language Models (VLMs) for real-time, "always-on" streaming video applications (like robotic perception or wearable assistants) is incredibly challenging. Because video streams are effectively infinite, the model's key-value (KV) cache—which stores past visual context—grows continuously, leading to memory exhaustion and high latency.
Existing streaming methods try to mitigate this by pruning tokens using local heuristics, such as keeping only the most recent frames or dropping tokens with low attention weights. However, these token-wise strategies suffer from a major flaw: they evaluate tokens independently. Consequently, they often discard weak or distributed visual cues that are collectively vital for understanding the long-term context of a video, failing to ensure that the compressed memory remains globally representative of the video's history.
Methods
CoRDS (Coreset-based Representative and Diverse Selection) shifts the paradigm from local token pruning to global geometric coverage.
The core method consists of three main components:
- Joint KV Representation: Instead of compressing keys or values in isolation, CoRDS measures coverage in a joint $K$-$V$ feature space. This ensures the model preserves both the retrieval structure (governed by keys) and the actual information read out by attention layers (governed by values).
- Bicriteria Coreset Selection: The authors define a distance metric that explicitly balances approximation errors in both key and value spaces using a weighting parameter $\alpha$. To minimize the total quantization error efficiently online, they use a deterministic, greedy $D^2$-style farthest-first traversal algorithm.
- Orthogonal Anti-Redundancy Regularizer: Pure coverage optimization can accidentally select multiple tokens pointing in the same direction, wasting memory budget. CoRDS introduces a lightweight diversity bonus inspired by log-determinant subset selection. It projects candidate tokens onto the orthogonal complement of the already selected subspace, favoring tokens that expand the memory into entirely new geometric directions.
To keep computational overhead minimal, CoRDS employs a layer-selective schedule and cross-layer cascade. Compression is restricted to the bottom 25% of decoder layers (where visual redundancy is highest), and a few "anchor" layers compute the coreset selections, which are then instantly reused by neighboring "follower" layers.
Datasets
The authors evaluated CoRDS across five challenging benchmarks using four open-source VLMs (Qwen2-VL-7B, Qwen2.5-VL-3B/7B, and LLaVA-NeXT-Video-7B):
- Offline Long-Video Benchmarks (Evaluated Causally): EgoSchema, MLVU, and VideoMME. Though traditionally offline, the video tokens were fed sequentially to simulate a streaming environment before answering queries.
- Streaming Video Benchmarks: OVO-Bench and StreamingBench, where queries arrive asynchronously at arbitrary timestamps throughout the video stream.
Key Insights and Ideas
- Values Matter More Than Keys: Empirically, favoring value-space approximation ($\alpha < 0.5$) yields better downstream accuracy. This aligns with attention theory: values directly dictate the magnitude of the model's output, whereas keys only modulate retrieval weights.
- Less Can Be More (Beating the Full Cache): In several long-video tasks, CoRDS actually outperformed the uncompressed Full KV cache baseline. This suggests that keeping a clean, representative coreset helps mitigate the "needle-in-a-haystack" confusion that VLMs experience when overwhelmed by massive, imbalanced contexts.
- Late Layers are Pruning-Sensitive: Compressing all transformer layers severely degrades performance. Early layers process redundant structural video data, making them ideal for coreset selection, whereas later layers develop highly specialized, task-conditioned semantic features that are easily disrupted by pruning.
Key Results
- Substantial Compression: At a cache budget of $|M|=6\text{K}$ tokens (representing an $\sim 8\times$ compression ratio), CoRDS matched or exceeded the uncompressed Full KV baseline across nearly all Qwen2(.5)-VL backbones.
- Superiority in Tight Budgets: At an aggressive $17\times$ compression ratio ($|M|=3\text{K}$ tokens), CoRDS consistently outperformed state-of-the-art streaming baselines like InfiniPot-V and StreamMem, even when those baselines were given twice the token budget.
- Hardware Efficiency: When processing long video clips (up to 1000 seconds), CoRDS maintained a completely flat memory footprint and high throughput, achieving up to a 44% reduction in energy consumption compared to non-cascaded configurations.
Limitations and Future Work
While CoRDS is highly effective, it is strictly query-agnostic by design; it compresses the video stream without knowing what question will be asked. While this is necessary for true streaming, incorporating a lightweight, late-stage query conditioning mechanism could help retrieve niche details that a geometric coreset might overlook. Additionally, the authors note that exploring adaptive, per-layer token budgets and extending the coreset framework to audio-visual or embodied AI agents are promising future directions.
Summary updated