💻 computer science

CoRDS: Coreset-based Representative and Diverse Selection for Streaming Video Understanding

The paper proposes CoRDS, a coreset-based method for streaming video understanding that improves upon token-wise heuristic pruning by selecting a compact, diverse, and representative subset of the key-value cache through a bicriteria objective and orthogonality-driven diversity criterion, thereby enhancing performance across multiple vision-language models and benchmarks under fixed memory budgets.

Original authors: Ailar Mahdizadeh, Puria Azadi, Muchen Li, Xiangteng He, Leonid Sigal

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ailar Mahdizadeh, Puria Azadi, Muchen Li, Xiangteng He, Leonid Sigal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a very long movie, but you only have a tiny, sticky note to write down the most important parts so you can answer questions about it later. This is the challenge facing modern AI models (called Vision-Language Models) when they try to understand long videos in real-time. They can't remember everything, so they have to "compress" the video into a smaller memory.

The paper introduces a new method called CoRDS (Coreset-based Representative and Diverse Selection) to solve this. Here is how it works, using simple analogies:

The Problem: The "Recency" Trap

Currently, most AI models use a "sticky note" strategy that relies on simple rules, like:

"Keep the newest stuff": Only remember the last few seconds.
"Keep the loudest stuff": Only remember the parts that look the most obvious or bright.

The authors argue this is like trying to summarize a whole movie by only remembering the last scene or the scene with the biggest explosion. You might miss the quiet, crucial clues that happened 20 minutes ago, which are needed to solve a mystery later.

The Solution: The "Curator" Approach

CoRDS changes the game. Instead of picking tokens (tiny pieces of video data) one by one based on how loud or new they are, it acts like a museum curator trying to build a small exhibit that represents the entire collection.

Here are the three main tricks CoRDS uses:

1. The "Two-Handed" View (Joint KV Representation)
Imagine every piece of video data has two sides:

The "Key" (The Label): This tells the AI where to look in the past. (e.g., "This is the scene with the red car.")
The "Value" (The Content): This is the actual information. (e.g., "The red car crashed into a tree.")

Old methods often looked at just the label or just the content. CoRDS looks at both at the same time. It ensures that the AI can find the right memory and that the memory actually contains the right details. It's like making sure you have both the map (Key) and the photo (Value) of the location, not just one or the other.

2. The "Cover the Room" Strategy (Coreset Selection)
Instead of picking the "best" single item, CoRDS asks: "Which small group of items covers the most ground in the room?"
If you have a room full of furniture, you don't just pick the most expensive chair. You pick a chair, a table, a lamp, and a rug that, together, represent the whole room's style. CoRDS mathematically selects a small group of video frames that "covers" the geometry of the entire video history, ensuring no major visual style or scene type is left out.

3. The "New Angle" Rule (Orthogonal Diversity)
Sometimes, you might pick two items that are very similar (like two identical red chairs). This wastes space. CoRDS has a rule to prevent this: "Don't pick something that looks too much like what we already have."
It looks for items that offer a "new angle" or a new direction. If the AI already has a memory of a red car, it won't pick another red car unless it's the only way to cover that part of the video. It actively seeks out the unique, different moments to make the memory diverse.

The Results: Smarter Memory, Not Just More Memory

The paper tested this on four different AI models and five different video benchmarks (including long movies and live streams).

Better than the competition: CoRDS consistently beat existing methods (like InfiniPot-V and StreamMem) that use the "recency" or "loudness" rules.
Small is beautiful: Even when the AI was forced to use a very tiny memory (keeping only 1/16th of the video data), CoRDS performed better than models that had access to much larger memories using old methods.
Beating the "Full" model: In some cases, CoRDS performed better than the AI model trying to remember the entire uncompressed video. This suggests that by removing the "redundant" or "noisy" parts of the video, the AI actually focuses better on the important clues (solving the "needle in a haystack" problem).

Summary

Think of CoRDS as a smart editor for a video. Instead of just cutting out the boring parts or keeping only the latest clips, it carefully selects a diverse, representative handful of moments that capture the whole story. This allows the AI to answer questions about a 1-hour video just as well as if it had watched the whole thing, but using a fraction of the computer memory.

Technical Summary: CoRDS

Problem Statement

Streaming Video Understanding (SVU) with Large Vision-Language Models (VLMs) faces a critical bottleneck: the need to maintain a bounded memory footprint while processing unbounded video streams in real-time. Unlike offline video understanding, where the full context is available for frame sampling or query-dependent compression, SVU requires causal, query-agnostic processing where future frames are unknown.

Existing solutions primarily rely on Key-Value (KV) cache compression using local, token-wise heuristics (e.g., recency, temporal redundancy, or norm-based saliency). The paper argues that these methods suffer from a fundamental limitation: they do not explicitly optimize for the global representativeness of the retained memory. Consequently, cues that are individually weak but collectively important (such as static visual details or temporally distributed structures) are often discarded because they lack local salience at the moment of compression.

Methodology: CoRDS

The authors propose CoRDS (Coreset-based Representative and Diverse Selection), a training-free, query-agnostic framework that reframes KV-cache compression as a representative coreset selection problem. Instead of scoring tokens independently, CoRDS selects a small subset that geometrically covers the accumulated visual cache.

The method operates on three core principles:

1. Joint KV Representation and Bicriteria Coverage

The authors posit that effective selection must account for both Keys (which determine retrieval structure) and Values (which determine the information read out by attention).

Representation: Tokens are represented in a joint feature space $\phi^{(KV)}_i = [k_i; v_i]$ .
Objective: A bicriteria distance metric $d_\alpha(i, S)$ is defined to measure the distance from a candidate token $i$ to the selected set $S$ , balancing key-space and value-space approximation errors:
$d_\alpha(i, S) = \min_{j \in S} \left[ \alpha \|k_i - k_j\|^2 + (1-\alpha) \|v_i - v_j\|^2 \right]$
where $\alpha \in [0, 1]$ controls the trade-off. Empirical results suggest favoring values ( $\alpha < 0.5$ ) yields better performance.
Optimization: The subset is selected greedily using a D2-style farthest-first rule, which seeds cluster centers proportional to their squared distance from previously chosen centers. This provides an $O(\log k)$ approximation guarantee for the $k$ -means objective.

2. Orthogonal Diversity for Non-Redundancy

A pure coverage-based selection may yield a redundant coreset where multiple tokens lie in similar directions in feature space. To address this, CoRDS introduces an orthogonal anti-redundancy term.

Mechanism: For a candidate token, the method calculates the residual vector orthogonal to the span of the currently selected keys (and values).
Scoring: A novelty score based on the squared norm of this residual is added as a soft bonus to the coverage score. This is motivated by log-determinant subset selection, which guarantees a $(1 - e^{-1})$ approximation for monotone submodular maximization.
Final Score: The selection score combines the bicriteria distance and the orthogonal novelty:
$\text{score}(i | S_t) = e^{d_\alpha(i, S_t)} + \lambda \cdot \widehat{\text{Orth}}(i | S_t)$

3. Layer-Selective Compression and Cascade Reuse

To minimize computational overhead:

Layer Selection: The coreset selector is applied only to the bottom 25% of decoder layers, where visual redundancy is highest. Later layers, which encode task-conditioned features, are left uncompressed.
Cross-Layer Cascade: A small set of "anchor" layers performs the full selection. "Follower" layers reuse the selected token indices from their anchor layers without re-computing the selection, significantly reducing latency while preserving layer-specific representations.

Key Contributions

Coreset View of Streaming Compression: A shift from local token pruning to a query-agnostic, coverage-oriented formulation that selects a compact memory representing the accumulated video context.
Joint KV Representative Coverage: The introduction of a joint key-value representation and a bicriteria objective that explicitly balances retrieval structure (keys) and output content (values), demonstrating that selecting in only one space is suboptimal.
Orthogonal Diversity: An anti-redundancy mechanism grounded in log-determinant subset selection that favors candidates contributing new directions to the feature space, preventing the waste of token budgets on redundant information.

Experimental Results

The method was evaluated on four open-source VLMs (Qwen2-VL, Qwen2.5-VL, LLaVA-NeXT-Video) across five benchmarks (EgoSchema, MLVU, VideoMME, OVO-Bench, StreamingBench).

Performance: Under fixed cache budgets (3K and 6K tokens), CoRDS consistently outperforms heuristic baselines like InfiniPot-V and StreamMem.
- On MLVU, CoRDS improved performance by +4.2% over the best baseline at a 6K budget.
- At aggressive compression ratios (1/16), CoRDS often matches or exceeds the performance of the Full KV (uncompressed) baseline, suggesting that which tokens are kept is more critical than how many.
Streaming Efficiency: In streaming benchmarks (OVO-Bench, StreamingBench), CoRDS showed gains across backward, real-time, and forward tracks, particularly in tasks requiring evidence dispersed over long durations (e.g., Prospective Reasoning, Counting).
Coverage Analysis: Coverage Cumulative Distribution Function (CDF) analysis confirms that CoRDS retains a more representative subset of the full cache compared to baselines, with lower cosine distances to the original token set.
Efficiency: The cross-layer cascade strategy maintains a flat memory footprint and achieves prefill throughput comparable to or better than baselines, even for videos up to 1000 seconds long.

Significance and Claims

The paper claims that representative coreset selection offers a more effective principle than token-wise pruning for memory-constrained streaming video understanding. By explicitly optimizing for the geometric coverage of the accumulated history in a joint key-value space, CoRDS mitigates the "needle-in-a-haystack" problem inherent in long-context reasoning.

The authors emphasize that their approach is training-free and query-agnostic, making it immediately applicable to existing transformer-based VLMs without retraining. The results highlight that performance gains in streaming settings arise not merely from increasing cache size, but from retaining a less redundant and more informative subset of visual tokens. The paper concludes that this geometric grounding provides a principled alternative to heuristic-based compression for persistent perception agents.