MDP 3 : A Training-free Approach for List-wise Frame Selection in Video-LLMs

Ming Li, Weihua Luo, Zhao Xu, Shiyin Lu, Qing-Guo Chen, Kaifu Zhang, Huanyu Wang, Hui Sun

arXiv · PDF · Open in the Atlas

Code that ran

We lifted 4 functions out of this paper's own repositories and ran 2 of them in a sandbox. "Ran" means the function executed on a synthesized input and returned a value. It is not a reproduction of the paper's results.

Repositories linked to this paper

• sunh-23/MDP3

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

Video large language models (Video-LLMs) have made significant progress in understanding videos. However, processing multiple frames leads to lengthy visual token sequences, presenting challenges such as the limited context length cannot accommodate the entire video, and the inclusion of irrelevant frames hinders visual perception. Hence, effective frame selection is crucial. This paper emphasizes that frame selection should follow three key principles: query relevance, list-wise diversity, and sequentiality. Existing methods, such as uniform frame sampling and queryframe matching, do not capture all of these principles. Thus, we propose Markov decision determinantal point process with dynamic programming (MDP 3 ) for frame selection, a training-free and model-agnostic method that can be seamlessly integrated into existing Video-LLMs at test time. Our method first estimates frame similarities conditioned on the query using a conditional Gaussian kernel within the reproducing kernel Hilbert space (RKHS). We then apply the determinantal point process (DPP) to the similarity matrix to capture both query relevance and list-wise diversity. To incorporate sequentiality, we segment the video and apply DPP within each segment, conditioned on the preceding segment selection, modeled as a Markov decision process (MDP) for allocating selection sizes across segments. Theoretically, MDP 3 provides a (1 -1/e)-approximate solution to the NP-hard list-wise frame selection problem with pseudo-polynomial time complexity, demonstrating its efficiency. Empirically, MDP 3 significantly outperforms existing methods, verifying its effectiveness and robustness.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2501.02885")
get_code_for_paper("2501.02885")
have("2501.02885")

Connect an agent — have() is free.