MarKey: Marginal Utility Guided Greedy Keyframe Selection for Long Video Understanding

• URL: http://arxiv.org/abs/2609.15408v1
• Date: Mon, 14 Sep 2026 11:39:20 GMT
• Title: MarKey: Marginal Utility Guided Greedy Keyframe Selection for Long Video Understanding
• Abstract summary: Long-video understanding remains challenging for large language models.<n>Recent training-free selection methods have enabled more efficient inference.<n>We propose MarKey, a framework that formulates multimodal selection as subset-aware greedy optimization.
• Score: 17.82627304498428
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Long-video understanding remains challenging for multimodal large language models (MLLMs) because densely encoding long frame sequences is computationally expensive, while uniform sampling under a limited visual budget can miss sparse yet decisive evidence. Recent training-free keyframe selection methods have enabled more efficient inference and yielded promising performance gains. However, many existing methods score frames largely in isolation without explicitly considering how each candidate complements the currently selected subset, potentially resulting in redundant selections and incomplete evidence coverage. To address this limitation, we propose MarKey, a training-free framework that formulates keyframe selection as subset-aware greedy optimization. At each iteration, MarKey scores each candidate using a tractable surrogate that jointly accounts for query relevance, marginal coverage gain, and context-dependent redundancy, and selects the frame with the highest utility. To make this iterative subset-aware evaluation efficient, MarKey uses a compact set of representative anchors to approximate full-video coverage and a bounded window of previously selected frames to limit context-dependent comparisons. Experiments on six benchmarks spanning holistic video understanding, human-centric video understanding, and open-ended video understanding demonstrate that MarKey consistently outperforms existing methods. Further analyses show robust gains across different MLLM backbones, model scales, and frame budgets.

Related papers

• Coverage-Driven Adaptive Keyframe Selection for Video Understanding [12.078063042214573]
  We propose CSES, a training-free semantic selector that adaptively determines the numbers of frames to score and select.<n> CSES estimates the prominence of the frame-query to guide active acquisition and adapt the temporal coverage of each input.<n>It then formulates selection relevance as a coverage problem that jointly accounts for semantic relevance, temporal redundancy, and visual redundancy.
  arXiv  Detail & Related papers  (2026-08-01T15:24:06Z)
• Efficient Frame Selection for Long Videos at Test Time with Attention-Based MLLM Selectors [69.75895255395702]
  Cross-modal attention at validation-selected extraction layers in MLLMs already provides query-relevant frame evidence without requiring autoregressive generation.<n>A lightweight MLLM selector, even with only 2B parameters, can extract frame-level evidence by converting selected-layer attention into relevance scores through query-conditioned aggregation.<n>Under a 32-frame budget, our selector improves over uniform sampling by up to 6.4 points on Video-MME and outperforms prior training-based selectors under matched frame budgets.
  arXiv  Detail & Related papers  (2026-07-17T07:04:31Z)
• Gaussian Mixture Modeling for Event-Aware Visual Allocation in Long Video Understanding [55.04091863981529]
  Large Vision-Language Models (LVLMs) face significant challenges in long video understanding due to the excessive computational cost and information loss associated with uniform sampling.<n>We propose GMM-EVA, which leverages Gaussian Mixture Models to model event-level structure from discrete frame-wise.<n>A differentiated allocation strategy is then applied to preserve one primary high-resolution per event for high-fidelity detail, while utilizing lower-resolution secondary observations to maintain temporal context and optimize token budgets.
  arXiv  Detail & Related papers  (2026-07-14T09:27:25Z)
• Where to Focus: Query-Modulated Multimodal Keyframe Selection for Long Video Understanding [48.14432643308697]
  Long video understanding is a formidable challenge for Multimodal Large Language Models.<n>Q-Gate is a plug-and-play framework that treats selection as a dynamic modality routing problem.
  arXiv  Detail & Related papers  (2026-04-19T13:04:18Z)
• Query-Conditioned Evidential Keyframe Sampling for MLLM-Based Long-Form Video Understanding [21.306038832082553]
  Multimodal Large Language Models (MLLMs) have shown strong performance on video question answering.<n>Their application to long-form videos is constrained by limited context length and computational cost.<n>We propose an evidence-driven sampling framework grounded in information theory.
  arXiv  Detail & Related papers  (2026-04-01T15:02:50Z)
• FOCUS: Efficient Keyframe Selection for Long Video Understanding [26.44459739499484]
  Multimodal large language models (LMLMs) represent images and video frames as visual tokens.<n> FOCUS, Frame-Optimistic Confidence Upperbound Selection, is a model-agnostic selection module that selects frames under a strict token budget.<n>For videos longer than 20 minutes, it achieves an 11.9% gain in accuracy on LongVideoBenching benchmarks.
  arXiv  Detail & Related papers  (2025-10-31T08:41:13Z)
• AdaRD-key: Adaptive Relevance-Diversity Keyframe Sampling for Long-form Video understanding [31.685368980481968]
  We propose AdaRD-Key, a training-free sampling module for query-driven long-form video understanding.<n>To handle broad queries with weak alignment to the video, AdaRD-Key employs a lightweight relevance-aware gating mechanism.<n>Our pipeline is training-free, computationally efficient (running in real time on a single GPU), and compatible with existing vision-language models.
  arXiv  Detail & Related papers  (2025-10-03T07:19:34Z)
• Threading Keyframe with Narratives: MLLMs as Strong Long Video Comprehenders [62.58375366359421]
  Multimodal Large Language Models (MLLMs) for long video understanding remains a challenging problem.<n>Traditional uniform sampling leads to selection of irrelevant content.<n>Post-training MLLMs on thousands of frames imposes a substantial computational burden.<n>We propose threadings with narratives (Nar-KFC) to facilitate effective and efficient long video perception.
  arXiv  Detail & Related papers  (2025-05-30T03:04:28Z)
• BOLT: Boost Large Vision-Language Model Without Training for Long-form Video Understanding [51.49345400300556]
  Large video-language models (VLMs) have demonstrated promising progress in various video understanding tasks.<n>Traditional approaches, such as uniform frame sampling, often inevitably allocate resources to irrelevant content.<n>We introduce BOLT, a method to BOost Large VLMs without additional Training through a comprehensive study of frame selection strategies.
  arXiv  Detail & Related papers  (2025-03-27T13:18:40Z)
• Adaptive Keyframe Sampling for Long Video Understanding [75.7837692594814]
  This paper presents a simple yet effective algorithm named Adaptive Keyframe Sampling (AKS)<n>It inserts a plug-and-play module known as Adaptive Keyframe Sampling (AKS) which aims to maximize the useful information with a fixed number of video tokens.<n>Experiments on two long video understanding benchmarks validate that AKS improves video QA accuracy upon selecting informative encounters.
  arXiv  Detail & Related papers  (2025-02-28T17:46:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.