Skip to content

FOCUS: Efficient Keyframe Selection for Long Video Understanding

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

ICLR 2026; FOCUS efficient keyframe selection for hour-long video MLLMs

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

FOCUS is a training-free, model-agnostic keyframe selection module that reformulates query-aware frame selection as a Combinatorial Pure-Exploration (CPE) multi-armed bandit problem. It exploits strong temporal autocorrelation in video relevance scores to adaptively concentrate BLIP scoring on promising clips, achieving +11.9% accuracy on long-video QA while examining less than 2% of frames.

Problem

Existing long-video MLLM pipelines either uniformly subsample frames (missing critical content) or apply retrieval-style keyframe scoring with CLIP/BLIP (which requires a pre-filtering downsampling step to ~1 fps before scoring, itself undermining the goal of finding the globally most informative frames). For a one-hour 30-fps video, exhaustive frame scoring costs \(O(10^{11}\)–\(10^{12})\) FLOPs, making any filter-free dense scoring infeasible under practical compute budgets.

Method

FOCUS partitions a video \(V=(x_1,\ldots,x_T)\) into \(M\) fixed-length non-overlapping clips (bandit arms \(\{A_a\}_{a=1}^M\)). Pulling arm \(a\) means uniformly sampling a frame \(t\in A_a\) and computing its BLIP image-text matching score \(r_t = \psi(x_t, q;\theta)\) as reward—an unbiased estimate of the latent per-frame utility \(y_t\).

The two-stage batched algorithm (Algorithm 2): 1. Stage I — Coarse exploration: Pull each arm \(q\) times in parallel; compute empirical means \(\hat\mu_a\) and Bernstein confidence radii \(\beta_a(n) = \sqrt{\frac{2\hat\sigma_a^2 \ln n}{\max(1,N_a(n))}} + \frac{3\ln n}{\max(1,N_a(n))}\); select the top-\(\alpha m\) arms by optimistic UCB scores \(\tilde\mu_a = \hat\mu_a + \beta_a\). 2. Stage II — Fine exploitation: Pull each coarse-selected arm \(z\) additional times in a single batch; re-rank by unbiased empirical means \(\hat\mu_a\) to obtain the final \(m\) arms \(A_\text{fine}\).

Within each selected arm, per-frame scores are interpolated via nearest-neighbor assignment to the unscored frames, and \(k_a = \lfloor k/|A_\text{fine}|\rfloor\) keyframes are sampled proportionally to the resulting score distribution. The theoretical convergence (high-probability optimality of the returned arm set) reduces from the iterative CPE Algorithm 1 via the PAC-identification argument.

Key Contributions

  • Formulates query-aware keyframe selection as a budgeted CPE multi-armed bandit problem, with a formal regret-bound guarantee.
  • Introduces the two-stage batched FOCUS algorithm that replaces the theoretically motivated but GPU-inefficient sequential policy with parallelizable coarse-exploration + fine-exploitation passes.
  • Demonstrates filter-free operation: FOCUS scores only 1.6% of frames (vs. AKS's 3.7% after pre-filtering, or 100% without), cutting total GPU hours from 9.3 (AKS w/ pre-filter) to 5.5 on LongVideoBench (H100).
  • Achieves consistent plug-and-play gains across four MLLMs (GPT-4o, Qwen2-VL-7B, LLaVA-OV-7B, LLaVA-Video-7B) and four benchmarks without any fine-tuning.

Results

  • LongVideoBench overall: +3.2% (GPT-4o), +6.7% (Qwen2-VL-7B), +5.9% (LLaVA-OV-7B), +4.6% (LLaVA-Video-7B) over uniform sampling at matched frame budgets.
  • LongVideoBench — long videos (>20 min): +11.9% over uniform sampling and +7.6% over Top-K (LLaVA-Video-7B, 64 frames).
  • Video-MME overall: +0.7% (GPT-4o), +2.3% (Qwen2-VL-7B), +1.8% (LLaVA-OV-7B), +1.0% (LLaVA-Video-7B) over uniform sampling.
  • vs. AKS (state-of-the-art): FOCUS scores 63.5% vs. AKS 62.1% on LongVideoBench overall; 65.4% vs. 64.6% on Video-MME (LLaVA-Video-7B, 64 frames).
  • Efficiency: FOCUS sees 1.6% of frames and requires 5.5 GPU hours vs. AKS w/ pre-filter at 3.7% frames / 9.3 GPU hours; AKS without pre-filtering is infeasible at 255 GPU hours.
  • Qwen2-VL-7B + FOCUS (32 frames) outperforms Gemini-1.5-Flash (256 frames) on LongVideoBench using 8× fewer input frames.

Limitations

  • The bandit formulation assumes per-frame rewards are i.i.d. within arms, ignoring temporal dependencies between clips; this limits gains on videos where informative content is globally distributed (e.g., Video-MME "global understanding" queries).
  • Extension to Lipschitz/metric bandits or contextual bandits to model cross-arm temporal correlations is left as future work.
  • Frame relevance scoring relies on BLIP ITM; the choice of the vision-language encoder is fixed and its alignment quality directly caps FOCUS's ceiling.
  • Equal keyframe allocation across selected arms is a simplification; arm-proportional or query-adaptive allocation could improve fine-grained exploitation.
  • Evaluation focuses on multiple-choice QA; generalization to open-ended generation or dense temporal grounding tasks is not shown.

Relevance to Vision-Language Models

FOCUS directly addresses one of the core scalability bottlenecks for VLMs applied to video: the quadratic token explosion as video length grows. By treating frame scoring as a bandit exploration problem rather than exhaustive retrieval, it offers a principled, theoretically grounded alternative to the uniform-subsample-then-score pipeline that the field currently defaults to. The result — a training-free module that plugs in before any MLLM's visual encoder and consistently improves accuracy across commercial (GPT-4o) and open-source (Qwen2-VL, LLaVA) models — makes it immediately applicable to the standard long-video VLM evaluation stack (LongVideoBench, Video-MME, MLVU). For researchers tracking VLMs, this work also surfaces the underexplored connection between temporal autocorrelation structure in videos and adaptive computation allocation, which is relevant to any architecture that must process variable-length visual sequences under a fixed token budget.