# MDP3: A Training-free Approach for List-wise Frame Selection in Video-LLMs

arXiv: https://arxiv.org/abs/2501.02885 · HTML: https://mlsanity.com/paper/2501.02885/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 74 references that are in the map.
- First posted on arXiv 6 Jan 2025.

## Builds on (most cited first, 30 of 43)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [Flamingo: a Visual Language Model for Few-Shot Learning](https://mlsanity.com/paper/2204.14198/) (2022)
- [BLIP: Bootstrapping Language-Image Pre-training for Unified Vision-Language Understanding and Generation](https://mlsanity.com/paper/2201.12086/) (2022)
- [Qwen2-VL: Enhancing Vision-Language Model's Perception of the World at Any Resolution](https://mlsanity.com/paper/2409.12191/) (2024)
- [Sigmoid Loss for Language Image Pre-Training](https://mlsanity.com/paper/2303.15343/) (2023)
- [LLaVA-OneVision: Easy Visual Task Transfer](https://mlsanity.com/paper/2408.03326/) (2024)
- [InternVL: Scaling up Vision Foundation Models and Aligning for Generic Visual-Linguistic Tasks](https://mlsanity.com/paper/2312.14238/) (2023)
- [Video-MME: The First-Ever Comprehensive Evaluation Benchmark of Multi-modal LLMs in Video Analysis](https://mlsanity.com/paper/2405.21075/) (2024)
- [Video-LLaVA: Learning United Visual Representation by Alignment Before Projection](https://mlsanity.com/paper/2311.10122/) (2023)
- [Learning Transferable Features with Deep Adaptation Networks](https://mlsanity.com/paper/1502.02791/) (2015)
- [MVBench: A Comprehensive Multi-modal Video Understanding Benchmark](https://mlsanity.com/paper/2311.17005/) (2023)
- [MiniCPM-V: A GPT-4V Level MLLM on Your Phone](https://mlsanity.com/paper/2408.01800/) (2024)
- [How Far Are We to GPT-4V? Closing the Gap to Commercial Multimodal Models with Open-Source Suites](https://mlsanity.com/paper/2404.16821/) (2024)
- [VideoChat: Chat-Centric Video Understanding](https://mlsanity.com/paper/2305.06355/) (2023)
- [VideoLLaMA 2: Advancing Spatial-Temporal Modeling and Audio Understanding in Video-LLMs](https://mlsanity.com/paper/2406.07476/) (2024)
- [VILA: On Pre-training for Visual Language Models](https://mlsanity.com/paper/2312.07533/) (2023)
- [LongVideoBench: A Benchmark for Long-context Interleaved Video-Language Understanding](https://mlsanity.com/paper/2407.15754/) (2024)
- [MovieChat: From Dense Token to Sparse Memory for Long Video Understanding](https://mlsanity.com/paper/2307.16449/) (2023)
- [Long Context Transfer from Language to Vision](https://mlsanity.com/paper/2406.16852/) (2024)
- [VLMEvalKit: An Open-Source Toolkit for Evaluating Large Multi-Modality Models](https://mlsanity.com/paper/2407.11691/) (2024)
- [Chat-UniVi: Unified Visual Representation Empowers Large Language Models with Image and Video Understanding](https://mlsanity.com/paper/2311.08046/) (2023)
- [VideoAgent: Long-form Video Understanding with Large Language Model as Agent](https://mlsanity.com/paper/2403.10517/) (2024)
- [LongVILA: Scaling Long-Context Visual Language Models for Long Videos](https://mlsanity.com/paper/2408.10188/) (2024)
- [Effective Long-Context Scaling of Foundation Models](https://mlsanity.com/paper/2309.16039/) (2023)
- [VideoTree: Adaptive Tree-based Video Representation for LLM Reasoning on Long Videos](https://mlsanity.com/paper/2405.19209/) (2024)
- [Video-XL: Extra-Long Vision Language Model for Hour-Scale Video Understanding](https://mlsanity.com/paper/2409.14485/) (2024)
- [Self-Chained Image-Language Model for Video Localization and Question Answering](https://mlsanity.com/paper/2305.06988/) (2023)

## Built on by (most cited first, 30 of 43)

- [Beyond Attention or Similarity: Maximizing Conditional Diversity for Token Pruning in MLLMs](https://mlsanity.com/paper/2506.10967/) (2025)
- [Video Compression Commander: Plug-and-Play Inference Acceleration for Video Large Language Models](https://mlsanity.com/paper/2505.14454/) (2025)
- [Generative Frame Sampler for Long Video Understanding](https://mlsanity.com/paper/2503.09146/) (2025)
- [TimeSearch-R: Adaptive Temporal Search for Long-Form Video Understanding via Self-Verification Reinforcement Learning](https://mlsanity.com/paper/2511.05489/) (2025)
- [ReFoCUS: Reinforcement-guided Frame Optimization for Contextual Understanding](https://mlsanity.com/paper/2506.01274/) (2025)
- [Divide, then Ground: Adapting Frame Selection to Query Types for Long-Form Video Understanding](https://mlsanity.com/paper/2512.04000/) (2025)
- [Threading Keyframe with Narratives: MLLMs as Strong Long Video Comprehenders](https://mlsanity.com/paper/2505.24158/) (2025)
- [Video-EM: Event-Centric Episodic Memory for Long-Form Video Understanding](https://mlsanity.com/paper/2508.09486/) (2025)
- [From Frames to Clips: Training-free Adaptive Key Clip Selection for Long-Form Video Understanding](https://mlsanity.com/paper/2510.02262/) (2025)
- [GIFT: Global Irreplaceability Frame Targeting for Efficient Video Understanding](https://mlsanity.com/paper/2603.25072/) (2026)
- [FrameOracle: Learning What to See and How Much to See in Videos](https://mlsanity.com/paper/2510.03584/) (2025)
- [Event-Anchored Frame Selection for Effective Long-Video Understanding](https://mlsanity.com/paper/2603.00983/) (2026)
- [AdaCodec: A Predictive Visual Code for Video MLLMs](https://mlsanity.com/paper/2606.02569/) (2026)
- [SeViCES: Unifying Semantic-Visual Evidence Consensus for Long Video Understanding](https://mlsanity.com/paper/2510.20622/) (2025)
- [HiMu: Hierarchical Multimodal Frame Selection for Long Video Question Answering](https://mlsanity.com/paper/2603.18558/) (2026)
- [Post-Incorporating Code Structural Knowledge into Pretrained Models via ICL for Code Translation](https://mlsanity.com/paper/2503.22776/) (2025)
- [TempCore: Are Video QA Benchmarks Temporally Grounded?](https://mlsanity.com/paper/2509.01167/) (2025)
- [A.I.R.: Enabling Adaptive, Iterative, and Reasoning-based Frame Selection For Video Question Answering](https://mlsanity.com/paper/2510.04428/) (2025)
- [ViSIL: Unified Evaluation of Information Loss in Multimodal Video Captioning](https://mlsanity.com/paper/2601.09851/) (2026)
- [LDDR: Linear-DPP-Based Dynamic-Resolution Frame Sampling for Video MLLMs](https://mlsanity.com/paper/2605.11477/) (2026)
- [Swift Sampling: Selecting Temporal Surprises via Taylor Series](https://mlsanity.com/paper/2605.22678/) (2026)
- [ReQuest: Rethinking-based Question-Aware Frame Selection for Long-Form Video QA](https://mlsanity.com/paper/2607.01737/) (2026)
- [HFS: Holistic Query-Aware Frame Selection for Efficient Video Understanding](https://mlsanity.com/paper/2512.11534/) (2025)
- [Decomposing Queries into Tool Calls for Long-Video Keyframe Retrieval](https://mlsanity.com/paper/2605.23826/) (2026)
- [Coverage-Driven Adaptive Keyframe Selection for Video Understanding](https://mlsanity.com/paper/2608.00714/) (2026)
- [When and Where to Look: Adaptive Visual Evidence Scheduling for Efficient Long Video Understanding](https://mlsanity.com/paper/2608.03918/) (2026)
- [One Ranking, Any Budget: Matryoshka Evidence-to-Context Frame Selection for Long-Video Understanding](https://mlsanity.com/paper/2608.05707/) (2026)
- [Select, Compress, Reinvest: A Controlled Study of Visual-Token Allocation in Long-Video MLLMs](https://mlsanity.com/paper/2609.03820/) (2026)
- [One Skill Does Not Fit All: Automatic Discovery and Taxonomy-Guided Routing of Frame-Selection Skills for Long-Video Question Answering](https://mlsanity.com/paper/2609.12517/) (2026)
- [Design-Specification Tiling for ICL-based CAD Code Generation](https://mlsanity.com/paper/2603.12712/) (2026)

## Abstract (arXiv)

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 query-frame matching, do not capture all of these principles. Thus, we propose Markov decision determinantal point process with dynamic programming (MDP3) for frame selection, a training-free and model-agnostic method that can be seamlessly integrated into existing Video-LLMs. 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, MDP3 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, MDP3 significantly outperforms existing methods, verifying its effectiveness and robustness.