Think in Sets for Streaming Video Token Compression
NovaCov uses set-wise selection with a recency-weighted reference bank, retaining 99.6% accuracy and reducing latency by 46% in streaming video token compression.
Key Findings
Methodology
This work formulates streaming video token compression as a set selection problem, introducing NovaCov. It maintains a capacity-limited, recency-weighted historical reference bank and employs a dual-branch submodular coverage objective. One branch preserves current frame content, the other emphasizes coverage of information not yet represented by history. Greedy algorithms optimize token selection, ensuring theoretical (1-1/e) approximation guarantees. The approach is training-free and suitable for real-time streaming, balancing content fidelity and efficiency.
Key Results
- Across streaming and offline benchmarks, NovaCov outperforms existing training-free methods, retaining 99.6% of ReKV accuracy while reducing LLM prefill latency by 46%. In OVO-Bench and StreamingBench, it achieves superior accuracy at compression ratios around 25%. Ablation studies confirm the importance of reference bank capacity and dual-branch weights. The method demonstrates robustness across diverse tasks, including question answering, spatial understanding, and event detection.
- Quantitative results show that at maximum compression (75%), NovaCov maintains high task accuracy, with minimal performance drop compared to uncompressed data. It significantly reduces redundant token selection, leading to faster inference. Compared to token-wise scoring methods like Yao or VisionZip, the set-wise approach effectively minimizes redundancy, improving information coverage and task performance.
- Parameter sensitivity analysis indicates that the reference bank capacity and decay parameters critically influence performance. The method remains stable across different settings, confirming its practical viability for real-time applications.
Significance
This research advances streaming video understanding by introducing a set-wise, training-free compression framework that effectively balances information preservation and computational efficiency. It addresses the core challenge of cross-frame redundancy and real-time decision-making, enabling faster, more accurate multimodal video analysis. The approach has broad implications for deploying large-scale VideoLLMs in latency-sensitive environments like autonomous driving, surveillance, and interactive AI systems, paving the way for scalable, efficient multimodal AI.
Technical Contribution
The key technical innovation lies in modeling token compression as a submodular set selection problem with a bounded, recency-weighted reference bank. The dual-branch coverage objective guarantees near-optimality via greedy algorithms, with theoretical (1-1/e) bounds. The design of the reference bank, combining prototype updates, recency decay, and capacity constraints, ensures dynamic, efficient representation of historical content. This framework extends offline set optimization techniques to streaming scenarios, providing rigorous performance guarantees and practical efficiency.
Novelty
This work is the first to adapt set-wise submodular optimization for streaming video token compression without training. Unlike prior offline methods that assume full visibility, NovaCov explicitly models causal, frame-by-frame decision-making with a bounded historical reference. Its innovative combination of a recency-weighted reference bank and dual-branch coverage objective distinguishes it from existing token ranking or offline set selection approaches, filling a critical gap in real-time multimodal understanding.
Limitations
- The method relies on fixed parameters for reference bank capacity and decay, which may require tuning for different scenarios. Extreme scene changes or very high compression ratios could degrade performance.
- Computational overhead of prototype updates and greedy selection, although optimized, may still pose challenges for ultra-low latency edge devices.
- Current design assumes static thresholds and weights, limiting adaptability to highly dynamic environments. Future work could incorporate learning-based parameter tuning.
Future Work
Future directions include developing adaptive parameter mechanisms for dynamic scene complexity, integrating multi-modal cues for richer content representation, and exploring learned reference update strategies. Extending the framework to multi-task and multi-modal settings, as well as hardware-aware optimizations, will further enhance its deployment in real-world applications like autonomous systems and large-scale video analytics.
AI Executive Summary
The rapid growth of video content presents significant challenges for real-time understanding, especially in resource-constrained environments. Traditional approaches rely heavily on offline processing or training-intensive models, which are often impractical for streaming scenarios demanding low latency and high efficiency. Addressing this gap, this paper introduces NovaCov, a novel, training-free method for streaming video token compression based on set-wise selection principles. Unlike conventional token ranking strategies that evaluate tokens independently, NovaCov models the problem as a subset selection task, leveraging a capacity-limited, recency-weighted historical reference bank. This bank dynamically summarizes previously conveyed content, enabling the system to prioritize tokens that add new, complementary information rather than redundant data.
The core technical innovation lies in the dual-branch submodular coverage objective, which simultaneously preserves the current frame's spatial content and emphasizes coverage of information not yet represented by history. Both branches are formulated as facility-location functions, ensuring the greedy selection process achieves a (1-1/e) approximation guarantee. This approach effectively balances the need for real-time responsiveness with the requirement for comprehensive content representation. Extensive experiments on benchmarks such as OVO-Bench and StreamingBench demonstrate that NovaCov outperforms existing training-free compression methods, retaining nearly all the accuracy of uncompressed data while halving the prefill latency.
This work significantly advances the field of streaming multimodal understanding, providing a scalable, theoretically grounded solution that adapts to the dynamic nature of continuous video streams. Its training-free, plug-and-play design facilitates deployment across diverse applications, from autonomous driving to surveillance. Looking ahead, integrating adaptive parameter tuning and multi-modal cues promises further improvements, making NovaCov a foundational component for future real-time video AI systems.
Deep Dive
Plain Language Accessible to non-experts
想象你在看一场电影，但你只能记住有限的内容，比如只记住最近发生的事情和一些最重要的细节。每当新场景出现时，你会快速决定哪些内容值得记住，哪些可以忘掉，以确保你不会被信息淹没。传统的方法就像随意记笔记，可能会重复记录一些无关紧要的细节。而新方法像个聪明的笔记本，记住哪些内容已经被提及，优先记那些新鲜或重要的部分。它还会根据内容的频繁出现和新颖程度，动态调整记忆的内容，确保你既能快速反应，又不会遗漏关键细节。这就像在不断筛选和整理信息，帮助你在有限的记忆空间里，快速理解和应对不断变化的场景。
ELI14 Explained like you're 14
想象你在学校的图书馆借书，但每次只能带几本。你会挑选最喜欢、最重要的书，而不是带所有的书。每次借完书后，你会记住哪些书你已经借过，下次就不会再带一样的书。这个过程就像视频中的令牌压缩，系统要决定每一帧带哪些内容。以前的方法就像随机挑书，可能带了很多重复的内容，浪费空间。而新方法像个聪明的朋友，记住哪些内容已经带过，优先带新鲜或重要的内容。它还会记住哪些内容经常出现，避免重复带相似的东西。这样既节省空间，又能保证理解完整。这就像你在不断学习和整理信息，既快又准，帮你更好地理解视频内容。
Abstract
Streaming VideoLLMs process frames causally while visual tokens grow continuously, making compression essential for controlling prefilling latency and memory. Existing training-free methods independently rank tokens, ignoring marginal-gain interactions among retained tokens. We argue that streaming video token compression should instead be formulated as set selection, where each candidate is valued by what it adds beyond the tokens already retained. Unlike existing set-wise methods designed for offline tasks, streaming makes causal, frame-by-frame pruning decisions, so modeling cross-frame interactions requires an explicit historical reference. This creates a reference-set dilemma: the reference must adequately represent previously conveyed content while remaining bounded for real-time inference. We introduce NovaCov, to our knowledge the first training-free, plug-and-play set-wise token compressor designed for streaming video. NovaCov maintains a capacity-bounded, recency-weighted Historical Reference Bank and optimizes a dual-branch submodular coverage objective that preserves representative current-frame content while prioritizing information insufficiently covered by history. Both branches are facility-location functions, so greedy selection retains the classical (1-1/e) approximation guarantee. Across streaming and offline benchmarks, NovaCov outperforms existing training-free compression methods, retaining 99.6% of ReKV accuracy while reducing LLM prefilling latency by 46%.