Source-linked AI summary
MDP3: A Training-free Approach for List-wise Frame Selection in Video-LLMs
Hui Sun, Shiyin Lu, Huanyu Wang, Qing-Guo Chen, Zhao Xu, Weihua Luo, Kaifu Zhang, Ming Li
TL;DR
Long video-token sequences challenge Video-LLMs, and existing frame-selection approaches do not capture query relevance, list-wise diversity, and sequentiality together. MDP3 combines query-conditioned DPP with sequential segment selection and dynamic-programming allocation. The paper reports significant improvements on three long-video benchmarks and gives a pseudo-polynomial-time approximation guarantee.
Problem
Long videos create visual-token sequences that challenge context capacity, while existing frame-selection methods do not fully capture query relevance, list-wise diversity, and sequentiality.
Source: §1 · pp. 1–2Method
MDP3 is a training-free, model-agnostic method that combines query-conditioned frame similarity and DPP with sequential segment selection and dynamic-programming allocation.
Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5Results
MDP3 significantly improves performance over existing methods on three long-video benchmarks and provides a (1 − 1/e)-approximation for the NP-hard selection problem.
Source: §5 · p. 8Takeaways & Limitations
MDP3 can be integrated at test time with existing Video-LLMs as a plug-and-play frame-selection method.
Source: §1 · p. 2The stated complexity guarantee is pseudo-polynomial rather than polynomial time.
Source: C. Limitations of MDP3 and Future… · p. 20
Abstract
from arXiv · showhide
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.
1. Introduction
Video-LLMs face long visual-token sequences, while uniform and query-based frame selection fail to capture all the principles needed for effective selection. MDP3 combines query relevance, list-wise diversity, and sequentiality in a training-free, model-agnostic method, and the paper reports improvements over existing baselines.
1. Introduction
- Long videos can exceed Video-LLMs’ context capacity, while redundant or irrelevant frames can hinder perception and increase resource use and token costs.The introduction also notes that accuracy can decline when using 64 frames instead of 32, underscoring the need to select a limited set.Source: §1 · pp. 1–2
- Uniform sampling ignores the query, while query-based pointwise retrieval overlooks relationships among selected frames, including diversity and sequentiality.The paper identifies query relevance, list-wise diversity, and sequentiality as the three principles frame selection should address.Source: §1 · p. 2
- MDP3 is a training-free, model-agnostic method that extends DPP-based selection to account for query relevance, list-wise diversity, and sequentiality.It reuses pretrained VLMs to score frame subsets, avoiding supervised-dataset collection and training a scoring model from scratch.Source: §1 · p. 2
- MDP3 estimates query-conditioned frame similarities, applies DPP to capture relevance and list-wise diversity, and uses segment-wise DPP conditioned on preceding selections to model sequentiality.An MDP allocates the total selection size across segments.Source: §1 · p. 2
- MDP3 is evaluated as a test-time plug-and-play process with four Video-LLMs on Video-MME, MLVU, and LongVideoBench, with significant improvements over baselines reported.The paper also presents a (1 − 1/e)-approximation for the NP-hard selection problem and describes the method as efficient through pseudo-polynomial complexity.Source: §1 · p. 2
2. Realted Work
Prior frame-selection approaches address different parts of the problem: uniform sampling disregards queries, query retrieval can yield redundant selections, and existing sequential DPP methods leave segment-size allocation challenging.
2. Realted Work
- Extending LLM context length does not resolve the computational burden or the “lost-in-the-middle” issue associated with long video-token sequences.The passage describes videos as containing hundreds or thousands of frames, making direct input impractical.Source: §2 · p. 2
- Uniform sampling is common, but it may miss query-relevant frames and include irrelevant ones; query-based retrieval can select redundant frames without modeling list-wise diversity.Cluster-based approaches regularize pairwise diversity but do not capture list-wise combinatorial relationships; a supervised selector tailored to VILA requires data collection and end-to-end training.Source: §2 · p. 3
- Prior work on video summarization applies DPP within consecutive segments conditioned on preceding selections, but allocating the total selection size across segments remains challenging.Gong et al. allocate uniformly, while Zheng and Lu use relaxed integer-programming constraints; this paper instead models sequential DPP as an MDP and uses dynamic programming for optimal allocation.Source: §2 · p. 3
3. Method
The method formulates query-conditioned frame subset selection and combines RKHS similarity, DPP, and sequential segment selection to handle relevance, diversity, and temporal structure. Dynamic programming allocates a fixed selection budget across segments, with a stated approximation guarantee and practical efficiency strategies.
3. Method
- The method frames VidQA as selecting k frames from a video given a query, while seeking a score that balances relevance, diversity, and sequentiality.It also identifies practical-time solution of the NP-hard list-wise subset-selection problem as a challenge.Source: §3 · p. 3
3.1. High-dimensional Conditional Similarity
- CMGK estimates high-dimensional frame similarities conditioned on the query by combining frame-frame similarity with each frame’s query relevance.The method maps embeddings into an RKHS and uses a conditional kernel to reduce the importance of irrelevant frames.Source: §3.1 · p. 3
3.2. Determinantal Point Process (DPP)
- DPP applied to the conditional similarity matrix captures query relevance and list-wise diversity, with a weighting factor trading off the two.The subset objective is submodular and NP-hard to maximize; the described greedy MAP inference has a (1 − 1/e)-approximation guarantee and O(nk2) complexity.Source: §3.2 · p. 4
3.3. Markov Decision DPP
- Sequential DPP selects within consecutive segments conditioned on preceding selections, while an MDP and dynamic programming optimize allocation of the total k across segments.The method states a (1 − 1/e)-approximation with closely O(nk4) time complexity; lazy and parallel updates are described as reducing practical complexity to O(nk2).Source: §3.3 · pp. 4–6
4. Experiments
Experiments test MDP3 as a plug-and-play frame selector across Video-LLMs and long-video benchmarks, comparing it with existing methods, frame counts, durations, and ablations. Results highlight stronger performance with fewer selected frames and the importance of sequentiality, especially for longer videos.
4.1. Experiments Protocol
- In evaluation, MDP3 selects 8 frames from 128 uniformly sampled candidates as input to Video-LLMs; it is tested on three long-video benchmarks using LLaVA-OneVision-7B, MiniCPM-V2.6-7B, Ovis2-8B, and VILA-V1.5-7B.The benchmarks are Video-MME, MLVU, and LongVideoBench, using its validation set without subtitles.Source: §4 · p. 6, §4.1 · pp. 6–7
4.2.1. Comparison with SOTA Methods
- MDP3 substantially improves baseline performance across three benchmarks, consistently beats uniform sampling, and enables Ovis2 to achieve the highest overall performance across benchmarks.The paper also reports that LLaVA-OneVision with MDP3 selecting 8 frames outperforms its well-tuned-frame-count variant, and that MDP3 surpasses FRAME-VOYAGER.Source: §4.2.1 · p. 7
4.2.2. Results across Various Selection Sizes
- 8 selected frames outperform the best uniformly sampled 32-frame baseline, while 2 and 4 frames reach 90.8% and 96.3% of top performance, respectively.Performance with 64 frames is lower than with 32 frames, whether or not MDP3 is used; the authors suggest this may reflect training on 32 frames.Source: §4.2.2 · p. 7
4.2.3. Results across Various Video Durations
- MDP3 substantially improves baseline performance for most video durations, but gains are smaller at 8–15 seconds and MiniCPM-V2.6 shows a slight decline.The authors attribute the smaller effect to uniform sampling already providing about 1 fps in that duration range.Source: Table 2 · p. 7, §4.2.3 · p. 8
4.2.4. Ablation Study
- The complete MDP3 achieves the best ablation performance, and its RKHS similarity, DPP diversity, and MDP sequentiality components are each reported as effective and indispensable.MDP3 is slightly worse than standard DPP on short videos, while standard DPP deteriorates significantly on longer videos.Source: §4.2.4 · p. 8, Table 3 · p. 8
5. Conclusion
The conclusion presents MDP3 as a training-free, model-agnostic approach that combines query relevance, list-wise diversity, and sequentiality. Experiments report improved performance, while the method offers an approximate solution with practical runtime optimizations.
5. Conclusion
- Across three long-video benchmarks, integrating MDP3 with existing Video-LLMs significantly improves performance.The conclusion characterizes the method as effective and robust.Source: §5 · p. 8
- MDP3 combines query relevance, list-wise diversity, and sequentiality in a training-free, model-agnostic frame-selection method.The conclusion describes it as the first method to address all three principles together.Source: §5 · p. 8
- MDP3 provides a (1 − 1/e)-approximation for the NP-hard list-wise frame-selection and selection-size allocation problem, with practical time complexity O(nk^4), reducible to O(nk^2) through lazy and parallel updates.Source: §5 · p. 8
Supplementary Material
The supplement reviews submodular maximization and establishes the greedy approximation result used in the paper. It relates diminishing marginal utility to submodularity and describes iterative selection under a cardinality limit.
A.1. Preliminaries
- Submodularity can be expressed through a set inequality and corresponds to diminishing marginal utility as items are added.The supplement also gives an equivalent two-item inequality formulation.Source: §A.1 · p. 13
- For a submodular function, the marginal value function after fixing a set remains submodular.Source: §A.1 · pp. 13–14
A.2. Proof of (1 −1/e)-approximation
- The greedy algorithm starts from an empty set, repeatedly selects the item with greatest marginal gain, and stops at cardinality k, guaranteeing a (1 − 1/e)-approximation.The supplement applies this result to standard DPP when selecting 8 frames, giving an approximation ratio of at least 65.6%.Source: §A.2 · p. 14
A.3. Proof of Time Complexity
The supplement analyzes MDP3’s runtime, describes the evaluation resources and benchmarks, and records implementation choices for the visual encoder and kernel. It also reports the shared hyperparameters used across tasks and benchmarks.
A.3. Proof of Time Complexity
- With small segment size, Algorithm 1 is upper-bounded by O(nk^3) in most practical cases; lazy strategies and parallel updates can reduce runtime to O(nk^2).Without those strategies, practical complexity is described as closely O(nk^4); segment size m and selection size k are both much smaller than the total frame count n.Source: §A.3 · pp. 14–15
B.1. Experiments Compute Resoureces
- Experiments use NVIDIA A100 GPUs and 256 AMD EPYC CPUs under Ubuntu 20.04.6.Source: §B.1 · p. 15
B.2. Dataset Details
- The benchmarks cover video understanding: Video-MME [13] contains 900 videos and 2,700 question-answer pairs, MLVU [75] has 2,593 tasks, and subtitle-free LongVideoBench validation [61] has 1,337 question-answer pairs.MLVU’s average video duration and LongVideoBench validation’s average video length are both 12 minutes.Source: §B.2 · p. 15
B.3. Implementation Details
- SigLIP serves as the visual encoder and VLM; questions exceeding its 64-token text-encoder context are split into equal-length sequences and pooled into one embedding.Source: §B.3 · p. 16
- The implementation uses averaged Gaussian-kernel weights and sets λ = 0.2 and segment size m = 32 across tasks and benchmarks.The trade-off and segment-size values were determined through cross-validation on a subset of the LLaVA-OneVision-mid training set.Source: §B.3 · p. 16
B.4. Hyperparameter Sensitivity Analysis
MDP3’s accuracy remains robust across tested score-trade-off and segment-size settings. It also adds little inference overhead while reducing the frames processed by the language model.
B.4. Hyperparameter Sensitivity Analysis
- Accuracy stays at 51–53% across tested λ values, peaks at 53.3% for λ = 0.2, and exceeds the 49.2% baseline throughout.The sensitivity test varies λ logarithmically from 0.0125 to 12.8.Source: §B.4 · p. 16, Figure 4 · p. 16
- Segment sizes from 8 to 128 frames all exceed baseline; accuracy peaks at 53.3% for m = 32 and remains 51.8% at m = 128.Accuracy stays above 52% for m ≤ 64, indicating insensitivity to segment size.Source: §B.4 · p. 16, Figure 5 · p. 16
B.5. Additional Parameters Analysis
- The added text-encoder parameters are no more than 6% of the original MLLM scale and require no tuning for the specific MLLMs.MDP3 reuses pretrained VLMs and is training-free and model-agnostic.Source: §B.5 · p. 16
B.6. Latency Comparison
- 11.47s less MLLM inference time (90% of baseline) comes with 1.94s additional frame-selection time; parallel MDP3-P cuts that overhead to 1.30s.The comparison uses MiniCPM-V2.6 on Video-MME without subtitles, selecting 8 frames from 128 candidates.Source: §B.6 · p. 17
B.7. Additional Experiments about Ablation Study
Across three Video-LLMs and three benchmarks, MDP3 achieves peak scores, with the largest reported gains on MLVU. Ablations indicate that partial adherence to the selection principles and cosine-only similarity yield weaker results.
B.7. Additional Experiments about Ablation Study
- MDP3 reaches peak scores across configurations—53.3/58.6/50.8 for VILA-V1.5, 58.0/66.6/57.1 for MiniCPM-V2.6, and 59.6/69.8/59.0 for LLaVA-OneVision—with MLVU gains of +4.8 to +6.2 over baselines.The ablation study covers Video-MME, MLVU, and LVBval.Source: §B.7 · p. 17, Table 5 · p. 17
- Intermediate variants gain less when they omit query relevance, list-wise diversity, or sequentiality, while uniform sampling trails by 3.0 to 9.5 points across models.The authors attribute the limited gains to partial adherence to the proposed principles.Source: §B.7 · p. 17
- Cosine similarity beats uniform sampling by 2.1 to 4.8 points but still trails MDP3 by the same margin, supporting the multi-kernel RKHS similarity design.The passage attributes the difference to better capture of high-dimensional feature relationships.Source: §B.7 · p. 17
B.8. More Experiments with Various Selection Size
The benefit of adding frames depends on each Video-LLM’s training frame count: performance can decline when input exceeds that setting. More frames are therefore not uniformly better, and frame selection remains important across video durations.
B.8. More Experiments with Various Selection Size
- VILA-V1.5 improves with more frames through k ≤ 16 but suffers a catastrophic decline above 16; LLaVA-OneVision improves through k ≤ 32 and retains some generalization beyond 32.The authors attribute declines beyond training frame counts to out-of-distribution input.Source: §B.8 · p. 18
- The reported 8-frame comparison setting is not necessarily optimal across Video-LLMs, benchmarks, and durations.The authors selected 8 frames to match the state-of-the-art Frame-Voyage settings for a fair comparison.Source: §B.8 · p. 18
- More frames face training and inference constraints: exceeding a model’s training configuration can degrade performance, while edge resources and token-based charges make excess input costly.The paper also cites diminishing marginal gains, redundant or irrelevant frames, and increased latency as reasons not to increase frame counts indefinitely.Source: §B.8 · pp. 18–19
- The authors report that these considerations hold across short, medium, and long video-understanding scenarios.This statement scopes the preceding discussion across durations.Source: §B.8 · p. 19
B.9. Qualitative Analysis
The qualitative cases illustrate different weaknesses in baseline selection: query matching can over-focus on textual cues or duplicate frames, while uniform sampling can miss relevant items. MDP3’s diversity and sequentiality help represent broader video content and transitions.
B.9. Qualitative Analysis
- For counting items distributed across frames, uniform sampling can miss them and query matching can repeatedly select the same item; MDP3’s more diverse selections aid counting.The examples include counting bird species and animal faces.Source: §B.9 · p. 19
- For summarization and reverse questions with no specific matching text, query-frame matching struggles, while MDP3 provides a more comprehensive and diverse video representation.The examples ask for a video’s genre and which elements do not appear.Source: §B.9 · p. 19
- For counting repeated appearances, query matching can miss transitions and merge occurrences, whereas MDP3 captures sequentiality and transitions.The example concerns counting how many times an interviewed girl appears.Source: §B.9 · p. 19
C. Limitations of MDP3 and Future Directions
MDP3 relies on pretrained VLMs, which may struggle with complex instructions, and its fixed selection size can occasionally include useless frames. The paper identifies fine-tuning and adaptive selection size as directions for addressing these limitations.
C. Limitations of MDP3 and Future Directions
- Pretrained VLMs used by MDP3 may struggle with complex instructions, while fine-tuning them could improve frame selection.The paper notes that paired selection data and contrastive learning could support this fine-tuning.Source: C. Limitations of MDP3 and Future… · p. 20
- MDP3 fixes selection size k and may select useless frames; choosing the best smaller size remains unresolved.Adjusting the relevance–diversity trade-off is not feasible for each sample, although dynamic programming records the optimal selection for each size i < k.Source: C. Limitations of MDP3 and Future… · p. 20
- Case examples contrast duplicate-frame failures in item counting with MDP3’s use of diversity to support counting and comprehensive video representation.The examples include counting animal faces and people wearing ties, alongside a video-genre question where query-frame matching fails to represent the whole video.Source: C. Limitations of MDP3 and Future… · pp. 21, 23, 24