MemStream: Scaling Token Budgets for Enhanced Video Stream Understanding with Dynamic KV-Cache

Paper: 2602.18434 Authors: Vatsal Agarwal, Saksham Suri, Matthew Gwilliam, Pulkit Kumar, Abhinav Shrivastava Categories: cs.CV

Abstract

Streaming video understanding presents unique challenges in encoding, storing, and retrieving information from continuous video streams for accurate video question answering (VQA). This paper introduces MemStream, a method that addresses the limitations of current key-value caching approaches which use restricted token budgets per frame, resulting in loss of fine-grained visual details. The authors identify a critical issue: existing methods exhibit temporal bias where query-frame similarity scores increase over time, favoring later frames during retrieval. MemStream proposes scaling token budgets combined with an adaptive selection strategy to reduce redundancy while maintaining local spatiotemporal information. Additionally, a training-free retrieval mixture-of-experts mechanism leverages external models for improved frame identification. The method demonstrates substantial improvements: +8.0% on CG-Bench, +8.5% on LVBench, and +2.4% on VideoMME (Long) compared to ReKV using Qwen2.5-VL-7B.

Key Contributions

• Token Budget Scaling: Proposes increasing the number of tokens per frame to capture more granular spatiotemporal information, addressing the information loss inherent in limited-token approaches
• Adaptive Selection Strategy: Introduces a mechanism to reduce token redundancy while preserving critical local spatiotemporal details, mitigating the temporal bias problem in feature encoding
• Training-Free Retrieval MoE: Develops a mixture-of-experts approach that incorporates external models to enhance frame retrieval accuracy without requiring additional training
• Comprehensive Evaluation: Demonstrates significant performance gains across multiple benchmarks (CG-Bench, LVBench, VideoMME) with consistent improvements over state-of-the-art methods

Technical Methodology

The core innovation of MemStream lies in its multi-faceted approach to handling dense video streams. Traditional methods like ReKV allocate a fixed, limited number of tokens per frame (typically 64-256 tokens), which forces aggressive compression of visual information. This compression leads to two critical problems: (1) loss of fine-grained details necessary for complex reasoning tasks, and (2) temporal bias in similarity computations.

MemStream addresses these issues through three key mechanisms:

1. Scaled Token Representation: By increasing the token budget per frame, the method maintains richer visual representations. However, naive scaling leads to computational challenges and redundancy. The authors carefully balance token count with information density.

2. Adaptive Token Selection: Rather than uniformly distributing tokens across all spatial regions, MemStream employs an adaptive strategy that identifies and preserves tokens corresponding to salient regions while reducing redundancy in homogeneous areas. This approach maintains $O(n)$ complexity while improving information retention.

3. Retrieval Mixture-of-Experts: The retrieval mechanism combines multiple scoring functions from different models to identify relevant frames. Given a query $q$ and frame representations $\{f_1, f_2, ..., f_T\}$, the system computes:

$s_i = \sum_{j=1}^{M} w_j \cdot \text{sim}_j(q, f_i)$

where $\text{sim}_j$ represents the similarity function from expert $j$, and $w_j$ are learned or heuristic weights. This ensemble approach reduces the temporal bias observed in single-model retrieval.

Experimental Results and Analysis

MemStream’s performance across three major benchmarks demonstrates its effectiveness:

CG-Bench Performance: The method achieves an 8.0% improvement over ReKV, indicating superior capability in handling compositional generalization tasks. This benchmark tests the model’s ability to understand complex spatiotemporal relationships and compositional queries.

LVBench Results: With an 8.5% gain, MemStream shows particular strength in long-video understanding scenarios. The adaptive selection strategy proves crucial here, as longer videos amplify the temporal bias problem that MemStream explicitly addresses.

VideoMME (Long): The 2.4% improvement on this challenging benchmark, while more modest, demonstrates robustness across diverse video understanding tasks. The training-free nature of the approach is particularly valuable, as it enables deployment without task-specific fine-tuning.

The ablation studies reveal that each component contributes meaningfully: token scaling alone provides baseline improvements, adaptive selection adds efficiency, and the retrieval MoE further enhances accuracy. The temporal bias mitigation is quantitatively demonstrated through analysis of similarity score distributions across frame positions.

Implications and Future Directions

MemStream represents a significant step toward practical streaming video understanding systems. The training-free nature of the retrieval component makes it particularly attractive for real-world deployment where computational resources and training data may be limited.

Several implications emerge from this work:

Scalability Considerations: While increasing token budgets improves performance, the relationship between token count and accuracy is not linear. Future work should investigate optimal token allocation strategies that adapt to video content complexity.

Generalization: The method’s success across multiple benchmarks suggests that the identified temporal bias problem is fundamental to KV-cache-based approaches, not dataset-specific. This insight could inform the design of future video understanding architectures.

Efficiency Trade-offs: The adaptive selection strategy demonstrates that intelligent token management can achieve better performance than naive uniform allocation. This principle could extend to other domains requiring efficient information compression.

Multi-Modal Integration: The mixture-of-experts retrieval approach opens possibilities for incorporating diverse signal types (audio, text, metadata) to enhance frame selection, potentially leading to more robust multi-modal video understanding systems.

Takeaways

1. Current streaming video understanding methods suffer from temporal bias in KV-cache retrieval, systematically favoring later frames due to feature encoding characteristics
2. Scaling token budgets per frame enables richer spatiotemporal representations, but requires adaptive selection strategies to manage redundancy and computational costs
3. Training-free retrieval mixture-of-experts can effectively leverage external models to improve frame identification without additional training overhead
4. MemStream achieves substantial improvements across multiple benchmarks (8.0% on CG-Bench, 8.5% on LVBench, 2.4% on VideoMME-Long), demonstrating broad applicability
5. The adaptive token selection strategy successfully balances information preservation with computational efficiency, maintaining linear complexity while improving performance
6. Addressing temporal bias in similarity computations is crucial for accurate long-video understanding and compositional reasoning tasks