FOCUS: Efficient Keyframe Selection for Long Video Understanding

## Abstract

Abstract Multimodal large language models (MLLMs) represent images and video frames as visual tokens. Scaling from single images to hour-long videos, however, inflates the token budget far beyond practical limits. Popular pipelines therefore either uniformly subsample or apply keyframe selection with retrieval-style scoring using smaller vision-language models. However, these keyframe selection methods still rely on pre-filtering before selection to reduce the inference cost and can miss the most informative moments. We propose Focus , Frame-Optimistic Confidence Upper-bound Selection , a training-free, model-agnostic keyframe selection module that selects query-relevant frames under a strict token budget. Focus formulates keyframe selection as a combinatorial pure-exploration (CPE) problem in multi-armed bandits: it treats short temporal clips as arms, and uses empirical means and Bernstein confidence radius to identify informative regions while preserving exploration of uncertain areas. The resulting two-stage exploration-exploitation procedure reduces from a sequential policy with theoretical guarantees, first identifying high-value temporal regions, then selecting top-scoring frames within each region
On two long-video question-answering benchmarks, Focus delivers substantial accuracy improvements while processing less than 2% of video frames. For videos longer than 20 minutes, it achieves an 11.9% gain in accuracy on LongVideoBench, demonstrating its effectiveness as a keyframe selection method and providing a simple and general solution for scalable long-video understanding with MLLMs. Code is available at https://github.com/NUS-HPC-AI-Lab/FOCUS .

## 1 Introduction

> *“The art of being wise is the art of knowing what to overlook.”* — William James

Recent advances in large language models (LLMs) and multimodal LLMs (MLLMs) have significantly improved visual understanding and reasoning. In current frameworks, images are encoded into visual tokens aligned with text and jointly processed by the LLM.
Extending this paradigm to videos—especially long, untrimmed ones—introduces a key challenge: the sheer number of frames leads to an overwhelming number of visual tokens, making inference computationally prohibitive.

A common solution is aggressive downsampling (Wang et al., 2022b; Lin et al., 2023; Maaz et al., 2024; Zhang et al., 2025c), but uniformly sampling a handful of frames (e.g., 64 from a one-hour video) often misses critical content (Tang et al., 2025; Zhang et al., 2025b). Increasing the frame rate, on the other hand, causes token explosion (Wang et al., 2024c). This trade-off motivates the need for keyframe selection: choosing a small set of informative frames that preserve semantics while staying within token limits.

Recent methods address this by scoring frame relevance with pre-trained vision-language encoders (e.g., CLIP (Radford et al., 2021) or BLIP (Li et al., 2022)) and then pick the highest-relevance frames (Tang et al., 2025; Zhang et al., 2025b). These text–image matching approaches are typically training-free and plug in easily before the visual encoder in MLLM stacks, retrieving frames with higher relevance other than uniform sampling.
Despite their success, current keyframe selection methods still face scalability and efficiency limitations. For a one-hour video at 30 fps (over $10^{5}$ frames), exhaustively scoring all frames entails on the order of $10^{11}$-$10^{12}$ FLOPs with a vision-language encoder like BLIP (Li et al., 2022). This scaling pressure forces existing methods to uniformly sample the video to lower frame rate before the scoring process. This pre-filtering process before keyframe selection undermines the goal of identifying most informative keyframes from all frames (Zhang et al., 2025b; Tang et al., 2025).

Figure: Figure 1: Temporal autocorrelation (ACF) of per-frame query relevance on LongVideoBench and Video-MME. We compute frame-level relevance per video and take the ACF over time lags (seconds); solid lines show the median across videos and shaded bands the interquartile range. The dashed line marks the correlation half-life level ($\rho(\delta)=0.5$).
Refer to caption: x1.png

In this work, we propose Focus, *Frame-Optimal Confidence Upper-Bound Selection*, a training-free, plug-and-play keyframe selection method designed to process extremely long videos with minimal computational overhead. Focus is easy to implement in practice while offering an elegant theoretical foundation.

The key insight behind Focus is grounded in the observation that natural videos exhibit strong temporal locality: adjacent frames are highly correlated in appearance and motion (Wiegand et al., 2003; Wang et al., 2016; 2022b). This local smoothness naturally extends to frame–query relevance scores. As illustrated in Figure [1](https://arxiv.org/html/2510.27280v1#S1.F1), we compute the autocorrelation function (ACF) of relevance scores $r_{t}$ on LongVideoBench and VideoMME. The results show a strong local correlation structure, with a half-life of approximately 5 seconds.
This observation implies that exhaustive scoring of all frames is unnecessary.
Instead, we can formulate keyframe selection as a bandit problem to adaptively allocate computation: quickly filtering out irrelevant temporal regions, concentrating scoring on promising segments, and ultimately prioritizing the most informative keyframes.

Focus first partitions the video into short temporal clips, each treated as an arm in a multi-armed bandit. The clip selection is then framed as a Combinatorial Pure-Exploration (CPE) problem: the goal is to identify a subset of arms that maximizes expected cumulative relevance under a strict token budget.
Each arm maintains an empirical mean relevance and a Bernstein-style confidence radius. Computation is adaptively allocated to clips that are either promising (high mean) or uncertain (large confidence radius), following an optimism-in-the-face-of-uncertainty principle. This iterative process enjoys theoretical convergence guarantees.
To leverage parallel computation without sacrificing optimism, we reduce the iterative strategy to a coarse-to-fine schedule: optimistic means guide exploration, while unbiased empirical means inform final arm selection. Within each selected arm, we extract the top-relevance frames to construct the final keyframe set.

We validate the effectiveness of our approach on two video understanding benchmarks, including LongVideoBench (Wu et al., 2024) and Video-MME (Fu et al., 2025). The proposed Focus is tested as an off-the-shelf module on with four popular MLLMs.
Focus improves answer accuracy over state-of-the-art keyframe selection baselines across benchmarks while maintaining lower inference cost. The gains are especially pronounced on long-form videos: for videos longer than 20 minutes on LongVideoBench, Focus delivers a 1.9% accuracy improvement while still cutting inference cost.

In summary, our main contributions are three-fold: (1) We formulate query-aware keyframe selection as a budgeted *combinatorial pure-exploration* (CPE) problem in a multi-armed bandit setting; (2) We introduce Focus, a training-free, model-agnostic keyframe selection module that selects query-relevant frames under a strict token budget; (3) We validate the effectiveness of Focus on two long-video understanding benchmarks, achieving consistent gains across four popular MLLMs.

## 2 Method

Figure: Figure 2: Overview of Focus. Focus partitions videos into fixed-length clips as bandit arms, applies optimistic confidence upper-bound arm selection and selects final keyframes within each promising arms.
Refer to caption: x2.png

### 2.1 Problem Formulation

##### Keyframe Selection Setup.

Let a video be $V=({\bm{x}}_{1},\ldots,{\bm{x}}_{T})$ and denote the corresponding text query as $q$. Let the frame index set be ${\mathbb{T}}=\{1,\ldots,T\}$. A downstream multimodal LLM $\Phi$ consumes a subset of frames indexed by ${\mathbb{K}}\subseteq{\mathbb{T}}$ with $|{\mathbb{K}}|=k$ and produces an answer $\hat{a}=\Phi\big(q,\{{\bm{x}}_{t}\}_{t\in{\mathbb{K}}}\big)$. Let $R_{\Phi}({\mathbb{K}}\mid V,q)$ denote the task-level utility of the selected frames (e.g., quality of generated answer, relevance to query, or other performance metrics).

##### Oracle and Surrogate Objective.

The oracle objective chooses ${\mathbb{K}}$ to maximize expected utility:

$$ ${\mathbb{K}}^{\mathrm{oracle}}(V,q)=\operatorname*{arg\,max}_{{\mathbb{K}}\subseteq{\mathbb{T}},\,|{\mathbb{K}}|=k}\;\mathbb{E}\big[R_{\Phi}({\mathbb{K}}\mid V,q)\big],$ (1) $$

Direct optimization to equation [1](https://arxiv.org/html/2510.27280v1#S2.E1) is infeasible due to the combinatorial search space and the high cost of black-box evaluations of $\Phi$.
We further expand the task-level utility $R_{\Phi}({\mathbb{K}}\mid V,q)$ to a summation of frame-level utility $y_{t}\in[0,1]$:

$$ ${\mathbb{K}}^{\star}=\operatorname*{arg\,max}_{{\mathbb{K}}\subseteq{\mathbb{T}},\,|{\mathbb{K}}|=k}\;\mathbb{E}\big[\sum_{t\in{\mathbb{K}}}y_{t}\big].$ (2) $$

However, estimating the contribution of each frame $t$ to the task-level utility is also intractable. We therefore posit that $y_{t}$ is indirectly observable via a vision-language encoder $\psi$ that outputs a relevance score $r_{t}=\psi({\bm{x}}_{t},q;{\bm{\theta}})=y_{t}+\epsilon_{\psi}$, where $\epsilon_{\psi}$ denotes encoder-induced noise. We assume $\epsilon_{\psi}$ follows some distribution that are supported on $[0,1]$ and with zero mean and $\sigma_{\psi}^{2}$ variance. Under this assumption, the relevance score $r_{t}$ is a unbiased estimator of $y_{t}$ which is also commonly used in many works (Tang et al., 2025; Yu et al., 2024) implicitly.

Exhaustively scoring all $T$ frames to get $\{r_{t}\}$ is computationally prohibitive, especially for hourly long videos which contains over $10^{5}$ frames.
This computational constraint motivates us to model keyframe selection under budget constraints, where we strategically allocate a limited sampling budget to identify the most promising temporal segments before producing the final set of $k$ keyframes.
Instead of directly optimizing equation [2](https://arxiv.org/html/2510.27280v1#S2.E2) at the frame level, we will approximate it through a combinatorial pure-exploration multi-armed bandit formulation at the clip level, which significantly reduces exploration cost.

### 2.2 Clip-Level Selection as Multi-Armed Bandit

For a video $V=({\bm{x}}_{1},\ldots,{\bm{x}}_{T})$, we partition the timeline into $M$ non-overlapping fixed-length clips $\mathcal{A}=\{A_{a}\}_{a=1}^{M}$, where each clip $A_{a}\subseteq{\mathbb{T}}$ spans frames $[s_{a},e_{a}]$ and is treated as a bandit arm.
We assume that frame-level utility within the same arm share the same distribution: $y_{t}\sim\mathcal{\nu}_{a}$ for all $t\in[s_{a},e_{a}]$, where $\mathcal{\nu}_{a}$ has mean $\mu_{a}$ and variance $\sigma_{a}^{2}$.
We define pulling the arm $a$ as randomly sampling one frame from that clip and observing its query relevance score $r_{t}$ as a reward.

Intuitively, our goal is to focus on the most promising clips which means we have to identify the optimal subset $S^{\star}\subseteq\mathcal{A}$. Formally, we define the *decision class* ${\mathbb{S}}\in 2^{\mathcal{A}}$ as a subset of the power set of $\mathcal{A}$. The optimal member $S^{\star}$ of decision class ${\mathbb{S}}$ is defined as

$$ $S^{\star}=\operatorname*{arg\,max}_{S\in{\mathbb{S}}}\;\sum_{a\in S}\mu_{a}.$ (3) $$

Under the classic CPE framework, the learner’s objective is to identify $S^{\star}$ after interacting with the arms over a sequence of rounds.
In the keyframe selection setting, our final goal is to further select $k$ keyframes from the selected arms. Denote $\{k_{a}\}_{a=1}^{|S^{\star}|}$ as the number of keyframes allocated to the $a$-th selected arm. We further define the frame-level optimal keyframe subset ${\mathbb{K}}_{a}^{\star}$ as

$$ ${\mathbb{K}}_{a}^{\star}=\operatorname*{arg\,max}_{{\mathbb{K}}_{a}\subseteq A_{a},\,|{\mathbb{K}}_{a}|=k_{a}}\;\sum_{t\in{\mathbb{K}}_{a}}y_{t}.$ (4) $$

The final keyframe subset ${\mathbb{K}}^{\star}$ is then defined as ${\mathbb{K}}^{\star}=\bigcup_{a\in S^{\star}}{\mathbb{K}}_{a}^{\star}$.
Empirically, we assume the decision class ${\mathbb{S}}$ is all size-$m$ subsets of $\mathcal{A}$ and keyframes are equally distributed across the promising arms. This setting gives us an elegant theoretical guarantee of regret bound as shown in section [C](https://arxiv.org/html/2510.27280v1#A3) and is also proved to be effective in our experiments.

### 2.3 Optimistic Confidence Upper-bound Arm Selection

Figure: Algorithm 1 Iterative Optimistic Confidence Upper-bound Arm Selection

Figure: Algorithm 2 Optimistic Confidence Upper-bound Arm Selection

#### 2.3.1 Optimal Arm Selection.

Generally, we play a exploration game by pulling an arm $a$ and observing the reward $r_{t}$ at each round $n$.
We maintain two core empirical statistics for each arm $a$ during this process: an empirical mean $\hat{\mu}_{a}$ and an empirical Bernstein confidence radius (variance-adaptive) $\beta_{a}$, following the UCV-V style bound (Audibert et al., 2009):

$$ $\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))}.$ (5) $$

Here $N_{a}(n)$ is the number of pulls for arm $a$ at round $n$ and $n=\sum_{a\in\mathcal{A}}N_{a}(n)$ is the total number of pulls. The confidence radius ensures that the empirical mean is within the confidence radius of the true mean with high probability, *i.e.,*

$$ $\mathcal{P}\left[\left|\hat{\mu}_{a}-\mu_{a}\right|\leq\beta_{a}(n)\right]\geq 1-\frac{6}{n}.$ (6) $$

Please refer to Appendix [B](https://arxiv.org/html/2510.27280v1#A2) for the detailed proof.

As shown in Algorithm [1](https://arxiv.org/html/2510.27280v1#alg1), the optimistic confidence upper-bound arm selection starts with an initialization phase where we pull each arm for $q$ times and observe the relevance scores as rewards. We then update the empirical means $\hat{\mu}_{a}$ and compute the confidence radius $\beta_{a}(n)$ for each arm $a$. Note the relevance score $r_{t}$ is an unbiased estimator of $y_{t}$ so we have $\mathbb{E}[\hat{\mu}_{a}]=\mu_{a}$.
Then we choose the best $m$ arms using the empirical means $\hat{\mu}_{a}$, *i.e., *${\mathbb{A}}_{n}=\mathrm{TopM}(\hat{{\bm{\mu}}},m)$, where $\hat{{\bm{\mu}}}$ is the vector of all arms’ empirical means and $\mathrm{TopM}(\cdot,m)$ returns a set of the $m$ arms with the largest empirical means.

We further refine the arm selection by evaluating the "potential" of each arm. To be specific, for arm $a\in{\mathbb{A}}_{n}$, we compute the lower confidence bound of the empirical mean, *i.e., *$\mathrm{LCB}_{a}(n)=\hat{\mu}_{a}-\beta_{a}(n)$; for arm $a\notin{\mathbb{A}}_{n}$, we compute the upper confidence bound of the empirical mean, *i.e., *$\mathrm{UCB}_{a}(n)=\hat{\mu}_{a}+\beta_{a}(n)$. If

$$ $\max_{a\notin{\mathbb{A}}_{n}}\mathrm{UCB}_{a}(n)\geq\min_{a\in{\mathbb{A}}_{n}}\mathrm{LCB}_{a}(n),$ (7) $$

this indicates that some arms outside the current top-$m$ set are still potential to be included in the top-$m$ set. Thus, we choose the arm $a$ that we are most uncertain about, *i.e.,*

$$ $a=\operatorname*{arg\,max}\limits_{a\in(\tilde{{\mathbb{A}}}_{n}\setminus{\mathbb{A}}_{n})\,\cup\,({\mathbb{A}}_{n}\setminus\tilde{{\mathbb{A}}}_{n})}\beta_{a}(n).$ (8) $$

We then pull this arm $a$ for $q$ times and repeat the process until the top-$m$ set is unchanged, *i.e., *${\mathbb{A}}_{n+1}={\mathbb{A}}_{n}$.
We then return the top-$m$ set ${\mathbb{A}}_{n}$.

It is easy to see Algorithm [1](https://arxiv.org/html/2510.27280v1#alg1) is guaranteed to return the optimal top-$m$ set ${\mathbb{A}}_{n}$ with high probability (see Section [C](https://arxiv.org/html/2510.27280v1#A3) for the detailed proof). However, the iterative process is empirically inefficient (or intractable) as the sequential arm-pulls and updating can not be parallelizable. We have to pull the arms one-by-one which means forward the vision-language model with batch size 1 sequentially. This costs significant waste of GPU utilization.

#### 2.3.2 Two-stage Arm Selection.

To make the procedure practical and easy to parallelize, we specialize Algorithm [1](https://arxiv.org/html/2510.27280v1#alg1) into the two-stage, batch variant in Algorithm [2](https://arxiv.org/html/2510.27280v1#alg2). The overall framework is shown in Figure [2](https://arxiv.org/html/2510.27280v1#S2.F2).

##### Stage I: Coarse initialization.

We pull each arm $q$ times in parallel and update the empirical means $\hat{\mu}_{a}$ and confidence radii $\beta_{a}(n)$ for all $a\in\mathcal{A}$. This stage coincides with the initialization phase of Algorithm [1](https://arxiv.org/html/2510.27280v1#alg1) and serves as a coarse exploration pass that produces reliable per-arm statistics at low coordination cost.

##### Stage II: Fine-grained exploration (batched).

Using the optimistic scores $\tilde{\mu}a=\hat{\mu}a+\beta_{a}(n)$, we select the top $\alpha m$ arms,
$\mathcal{A}_{\text{coarse}}=\mathrm{TopM}(\tilde{{\bm{\mu}}},,\alpha m)$,
and allocate an additional $z$ pulls to each $a\in\mathcal{A}_{\text{coarse}}$ (performed in a single batch). Here, $\alpha$ is a hyperparameter that controls the ratio of the coarse exploration budget to the fine-grained exploration budget. This stage is a batched counterpart of the iterative loop in Algorithm [1](https://arxiv.org/html/2510.27280v1#alg1): it implements the “optimism in the face of uncertainty” principle by concentrating samples on arms with the largest UCB values, while avoiding per-step scheduling overhead.

##### Final Arm Selection.

After the fine exploitation, we form the final set by selecting the best $m$ arms according to the unbiased empirical means,
${\mathbb{A}}_{\text{fine}}=\mathrm{TopM}(\hat{{\bm{\mu}}},m)$.
This choice mirrors $\delta$-PAC identification routines, where optimistic scores guide exploration but the recommendation itself is based on $\hat{\mu}_{a}$ rather than $\tilde{\mu}_{a}$.

### 2.4 Frame Selection within Selected Arms

Given the selected arm set ${\mathbb{A}}_{\text{fine}}$ and a total budget of $K$ frames, we sample $k_{a}$ frames per arm $a\in{\mathbb{A}}_{\text{fine}}$ with equal allocation (i.e., $k_{a}=\mathrm{round}(k/|{\mathbb{A}}_{\text{fine}}|)$, adjusted to sum to $K$).
For each arm $a$ with index set ${\mathbb{T}}_{a}$ and observed rewards $\{r_{a,s}\}_{s\in S_{a}}$ at sampled indices $T_{a}\subseteq{\mathbb{T}}_{a}$, we simply interpolate all rewards $\hat{r}_{a,t}$ within the arm using the nearest-neighbor assignment. We then form a per-arm sampling distribution according to the interpolated rewards and draw $k_{a}$ frames *without replacement* from $p_{a}$. The final keyframe set is $\mathcal{K}=\bigcup_{a\in\mathcal{A}_{\text{fine}}}\mathcal{K}_{a}$.

## 3 Experiments

### 3.1 Experimental Setup

##### Benchmarks

We follow the LMMs-Eval framework Zhang et al. (2024a) and adopt the open-source evaluation protocol from AKS for benchmarks, prompts, and scoring. Our experiments focus on two long-video multiple-choice QA benchmarks: LongVideoBench Wu et al. (2024) and VideoMME Fu et al. (2025). These datasets feature videos lasting up to an hour, where effective keyframe selection becomes crucial for performance. To ensure fair comparison (Tang et al., 2025), we disable subtitles, perform zero-shot evaluation, and keep model parameters frozen—varying only the frame selection strategy (our method versus uniform sampling).

##### Implementation Details

We test both open-source video MLLMs (Qwen2VL (Wang et al., 2024a), LLaVA-OV (Li et al., 2025), LLaVA-Video (Zhang et al., 2025c) and Qwen2-7B (Yang et al., 2024) language model) and the commercial GPT-4o (0513).
For frame relevance scoring, we use BLIP ITM (Li et al., 2022) to compute $r_{t}=\psi({\bm{x}}_{t},q;{\bm{\theta}})$, where $r_{t}$ estimates the latent frame-level utility as described in Section [2.1](https://arxiv.org/html/2510.27280v1#S2.SS1), which is justified as a promising choice by Tang et al. (2025).

### 3.2 Performance Analysis

**Table 1: Video-question answering accuracy (%) of various MLLMs on LongVideoBench and Video-MME. Focus is integrated into GPT-4o, Qwen2-VL, LLaVA-OV, and LLaVA-Video. The suffix “w/ Ours” denotes models using keyframes selected by our method; otherwise, frames are uniformly sampled. #Frame indicates the number of frames provided to the MLLM, and LLM denotes the language model size. We also include performance of additional popular MLLMs for reference.**
| Model | #Frame | LLM | LongVideoBench | Video-MME |
| --- | --- | --- | --- | --- |
| GPT-4V | 256 | – | 61.3 | 59.9 |
| Gemini-1.5-Flash | 256 | – | 61.6 | 70.3 |
| Gemini-1.5-Pro | 256 | – | 64.0 | 75.0 |
| VideoLLaVA | 8 | 7B | 39.1 | 39.9 |
| MiniCPM-V 2.6 | 64 | 8B | 54.9 | 60.9 |
| InternVL2-40B | 16 | 40B | 59.7 | 61.2 |
| LLaVA-Video-72B | 64 | 72B | 63.9 | 70.6 |
| GPT-4o | 32 | – | 51.6 | 61.8 |
| GPT-4o w/ Ours | 32 | – | 54.8 $\uparrow 3.2$ | 62.5 $\uparrow 0.7$ |
| Qwen2-VL-7B | 32 | 7B | 55.6 | 57.6 |
| Qwen2-VL-7B w/ Ours | 32 | 7B | 62.3 $\uparrow 6.7$ | 59.7 $\uparrow 2.1$ |
| LLaVA-OV-7B | 32 | 7B | 54.8 | 56.5 |
| LLaVA-OV-7B w/ Ours | 32 | 7B | 60.7 $\uparrow 5.9$ | 58.3 $\uparrow 1.8$ |
| LLaVA-Video-7B | 64 | 7B | 58.9 | 64.4 |
| LLaVA-Video-7B w/ Ours | 64 | 7B | 63.5 $\uparrow 4.6$ | 65.4 $\uparrow 1.0$ |

We evaluate Focus by using it to select keyframes as the visual input for the four aforementioned MLLMs, and compare it against the commonly used uniform sampling strategy. The results on LongVideoBench and Video-MME are summarized in Table [1](https://arxiv.org/html/2510.27280v1#S3.T1).

##### Improved Performance via Frame Selection.

As shown in Table [1](https://arxiv.org/html/2510.27280v1#S3.T1), Focus consistently outperforms uniform sampling across both open-source and closed-source MLLMs on both LongVideoBench and Video-MME.

Specifically, on LongVideoBench, Focus improves accuracy by 3.2% on GPT-4o, 6.7% on Qwen2-VL-7B, 5.9% on LLaVA-OV-7B, and 4.6% on LLaVA-Video-7B. On Video-MME, the gains are 0.7%, 2.1%, 1.8%, and 1.0% on the same models, respectively.

We observe a clear trend that larger MLLMs with more frame inputs tend to achieve better performance. However, Focus significantly narrows this gap by identifying the most informative frames, thereby boosting the performance of smaller MLLMs. For instance, Qwen2-VL-7B with Focus outperforms Gemini-1.5-Flash on LongVideoBench, despite using 8$\times$ fewer input frames. This highlights the effectiveness of Focus as a plug-and-play keyframe selection module for a wide range of MLLMs.

##### Interpretability through Visualizations.

We visualize the frames selected by Focus alongside uniformly sampled frames for two examples from LongVideoBench and Video-MME in Figure [3](https://arxiv.org/html/2510.27280v1#S3.F3).

Note that LongVideoBench and Video-MME differ substantially in how their video-question pairs are constructed. In general, LongVideoBench features more detailed and specific questions, while Video-MME focuses on concise, high-level queries. Moreover, LongVideoBench tends to ask about specific scenes or events, whereas Video-MME emphasizes global understanding of the video content.

To highlight this distinction, we manually mark the most informative frames relative to the query using yellow stars. These frames are more temporally concentrated in LongVideoBench (around specific events) and more uniformly distributed across the timeline in Video-MME.

This difference helps explain why Focus achieves greater performance gains on LongVideoBench: our method assumes that frame-level relevance scores are i.i.d., a common setting in multi-armed bandit formulations. This assumption neglects temporal dependencies between video segments. Consequently, retrieval-based methods for keyframe selection typically require regularization (Tang et al., 2025; Yu et al., 2024) to promote diversity and ensure coverage.

If temporal dependencies between segments (arms) are taken into account, the problem setting shifts toward Lipschitz or metric bandits (Kleinberg et al., 2008; Bubeck et al., 2011), and contextual bandits (Chu et al., 2011; Agarwal et al., 2014). We leave such extensions to future work.

Figure: Figure 3: Comparison between uniformly sampled frames and those selected by Focus. The left column shows two examples from LongVideoBench; the right column shows two from Video-MME. Yellow stars indicate manually annotated frames that are most informative to the query, many of which are successfully captured by Focus.
Refer to caption: x3.png

### 3.3 Comparison with State-of-the-Art

**Table 2: Comparison between our method and state-of-the-art keyframe selection baselines under matched keyframe count. Results are reported by video length buckets: Short, Medium, and Long. For Video-MME, we adopt its original categorization: Short (<2 min), Medium (4-15 min), and Long (30-60 min). For LongVideoBench, we define Short as videos shorter than 3 minutes, Medium as 3-20 minutes, and Long as over 20 minutes to ensure a balanced distribution.**
| Method | LongVideoBench |  | Video-MME |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Short | Medium | Long | Overall |  | Short | Medium | Long | Overall |  |
| Uniform | 67.5 | 57.4 | 51.8 | 58.9 |  | 76.4 | 62.6 | 54.3 | 64.4 |
| Top-$K$ | 72.3 | 58.0 | 60.5 | 62.3 |  | 75.4 | 60.4 | 53.0 | 62.9 |
| AKS | 72.3 | 59.2 | 56.1 | 62.1 |  | 76.3 | 62.8 | 54.7 | 64.6 |
| Focus (ours) | 72.3 | 59.0 | 63.7 | 63.5 |  | 76.5 | 63.5 | 56.1 | 65.4 |

To further validate the effectiveness of Focus, we compare it against state-of-the-art training-free keyframe selection methods on both LongVideoBench and Video-MME. Specifically, we consider recent approaches based on vision-language similarity:

- •
Top-$K$: Computes relevance scores between each frame and the query, then selects the top-$K$ scoring frames. Due to computational constraints, we apply a pre-filtering step by downsampling videos to 1 frame per second.
- •
AKS (Tang et al., 2025): A recent method that adaptively balances frame relevance and temporal coverage. It is considered the current state-of-the-art and also incorporates pre-filtering via downsampling to 1 frame per second (Tang et al., 2025).

Fair comparison protocol. We ensure a fair comparison by:
(i) evaluating all methods using LLaVA-Video-7B, the best-performing MLLM in our setup;
(ii) fixing the number of selected keyframes to $k=64$;
(iii) using the same vision-language encoder (e.g., BLIP) for frame scoring whenever possible.
Results are summarized in Table [2](https://arxiv.org/html/2510.27280v1#S3.T2).

##### Consistency across different lengths.

Focus achieves consistent performance gains across all video length categories, with particularly strong improvements on long videos. On LongVideoBench, Focus outperforms uniform sampling by 11.9% and Top-$K$ by 7.6% on videos longer than 20 minutes. On Video-MME, the respective improvements are 1.8% and 1.4%.

We also observe that on short videos, all keyframe selection methods perform similarly and consistently outperform uniform sampling. We attribute this to a possible saturation in the reasoning capabilities of the underlying MLLM (LLaVA-Video-7B), where input selection plays a less critical role.

##### Efficiency comparison.

We report the efficiency of each method in Table [3](https://arxiv.org/html/2510.27280v1#S3.T3), measuring both the number of frames “seen” (i.e., scored by a vision-language model) and the total GPU hours required to perform keyframe selection. All GPU hours are measured using a single NVIDIA H100 (80GB) GPU on the LongVideoBench dataset.

As shown, AKS without pre-filtering is computationally infeasible in practice, as it requires scoring all video frames—amounting to over 255 GPU hours by the optimistic estimation. With pre-filtering, the cost drops significantly to 9.3 GPU hours. In contrast, Focus is the most efficient: it requires only 1.6% of the BLIP forward passes and just 5.5 GPU hours, while simultaneously achieving the best overall performance.

**Table 3: Efficiency comparison of keyframe selection methods on LongVideoBench. "Pre-filtering" refers to downsampling videos to 1 fps prior to selection. Note that the official AKS pipeline includes this pre-filtering step by default. “Frames Seen (%)” counts the proportion of frame-level BLIP forward passes relative to scoring all frames; GPU hours are measured on a single H100 (80GB).**
| Method | Filtering-free | Frames Seen (%) | GPU hours |
| --- | --- | --- | --- |
| AKS w/o pre-filtering |  | 100 | 255 |
| AKS w/ pre-filtering |  | 3.7 | 9.3 |
| Focus (Ours) |  | 1.6 | 5.5 |

### 3.4 Efficiency-Accuracy Trade-off

Focus exposes a natural trade-off between accuracy and computational cost through a single hyperparameter $\alpha$, which controls the fraction of arms selected for fine-grained exploration. We report accuracy and efficiency under different $\alpha$ settings in Table [4](https://arxiv.org/html/2510.27280v1#S3.T4).

**Table 4: Effect of $\alpha$ on the performance and efficiency of Focus. “Frames Seen (%)” counts the proportion of frame-level BLIP forward passes relative to scoring all frames; GPU hours are measured on a single H100 (80GB).**
|  | Accuracy (%) | Frames Seen (%) | GPU hours |
| --- | --- | --- | --- |
| $\alpha=0.1$ | 62.9 | 1.1 | 3.5 |
| $\alpha=0.25$ | 63.5 | 1.6 | 5.5 |
| $\alpha=0.5$ | 63.6 | 2.5 | 9.2 |

We observe that choice of $\alpha$ has a significant impact on the efficiency while remain stable on the performance. When $\alpha=0.1$, Focus requires around 1.1% of the frames BLIP forward passes while only 3.5 GPU hours. When $\alpha=0.5$, Focus requires around 2.5% of the frames BLIP forward passes while only 9.2 GPU hours.
Exhaustively exploiting all arms would require 9.3 GPU hours, while the performance gain compared to $\alpha=0.25$ is negligible.

## 4 Conclusion

We addressed the core bottleneck of long-video understanding in MLLMs—the explosion of visual tokens—by introducing Focus, a training-free, plug-and-play keyframe selection method that allocates computation under a strict budget. Focus first partitions the video into temporal clips, treats each as an arm in a bandit problem, and then identifies query-relevant regions via a combinatorial pure-exploration strategy using empirical means and Bernstein confidence bounds. To improve efficiency, we reduce the iterative bandit process to a coarse-to-fine two-stage procedure that preserves optimism while enabling parallel inference.

Experiments on two challenging long-video QA benchmarks demonstrate that Focus consistently improves accuracy across four MLLMs while processing fewer than 2% of video frames. Our results show that lightweight, training-free keyframe selection—when guided by statistical principles—can significantly enhance the scalability and practicality of MLLMs for long-video understanding.

## 5 Reproducibility Statement

We provide a comprehensive theoretical analysis of our method in Appendix [B](https://arxiv.org/html/2510.27280v1#A2) and Appendix [C](https://arxiv.org/html/2510.27280v1#A3). The source code for this work is publicly available at [https://github.com/NUS-HPC-AI-Lab/FOCUS](https://github.com/NUS-HPC-AI-Lab/FOCUS). All models and datasets used in our study are publicly accessible.

## References

- Agarwal et al. (2014)
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire.
Taming the monster: A fast and simple algorithm for contextual bandits.
In Eric P. Xing and Tony Jebara (eds.), *Proceedings of the 31st International Conference on Machine Learning*, volume 32 of *Proceedings of Machine Learning Research*, pp. 1638–1646, Bejing, China, 22–24 Jun 2014. PMLR.
URL [https://proceedings.mlr.press/v32/agarwalb14.html](https://proceedings.mlr.press/v32/agarwalb14.html).
- Agrawal & Goyal (2012)
Shipra Agrawal and Navin Goyal.
Analysis of thompson sampling for the multi-armed bandit problem.
In *Conference on learning theory*, pp. 39–1. JMLR Workshop and Conference Proceedings, 2012.
- Alayrac et al. (2022)
Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katherine Millican, Malcolm Reynolds, et al.
Flamingo: a visual language model for few-shot learning.
*Advances in neural information processing systems*, 35:23716–23736, 2022.
- Audibert & Bubeck (2010)
Jean-Yves Audibert and Sébastien Bubeck.
Best arm identification in multi-armed bandits.
In *COLT-23th Conference on learning theory-2010*, pp. 13–p, 2010.
- Audibert et al. (2009)
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári.
Exploration–exploitation tradeoff using variance estimates in multi-armed bandits.
*Theoretical Computer Science*, 410(19):1876–1902, 2009.
- Auer et al. (2002)
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
*Machine learning*, 47(2):235–256, 2002.
- Bubeck et al. (2009)
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz.
Pure exploration in multi-armed bandits problems.
In *International conference on Algorithmic learning theory*, pp. 23–37. Springer, 2009.
- Bubeck et al. (2011)
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári.
<i>x</i>-armed bandits.
*Journal of Machine Learning Research*, 12(46):1655–1695, 2011.
URL [http://jmlr.org/papers/v12/bubeck11a.html](http://jmlr.org/papers/v12/bubeck11a.html).
- Cao et al. (2015)
Wei Cao, Jian Li, Yufei Tao, and Zhize Li.
On top-k selection in multi-armed bandits and hidden bipartite graphs.
*Advances in Neural Information Processing Systems*, 28, 2015.
- Chen et al. (2024a)
Lin Chen, Xilin Wei, Jinsong Li, Xiaoyi Dong, Pan Zhang, Yuhang Zang, Zehui Chen, Haodong Duan, Zhenyu Tang, Li Yuan, et al.
Sharegpt4video: Improving video understanding and generation with better captions.
*Advances in Neural Information Processing Systems*, 37:19472–19495, 2024a.
- Chen et al. (2016)
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang.
Combinatorial multi-armed bandit and its extension to probabilistically triggered arms.
*Journal of Machine Learning Research*, 17(50):1–33, 2016.
- Chen et al. (2023)
Xi Chen, Xiao Wang, Soravit Changpinyo, AJ Piergiovanni, Piotr Padlewski, Daniel Salz, Sebastian Goodman, Adam Grycner, Basil Mustafa, Lucas Beyer, Alexander Kolesnikov, Joan Puigcerver, Nan Ding, Keran Rong, Hassan Akbari, Gaurav Mishra, Linting Xue, Ashish V Thapliyal, James Bradbury, Weicheng Kuo, Mojtaba Seyedhosseini, Chao Jia, Burcu Karagol Ayan, Carlos Riquelme Ruiz, Andreas Peter Steiner, Anelia Angelova, Xiaohua Zhai, Neil Houlsby, and Radu Soricut.
PaLI: A jointly-scaled multilingual language-image model.
In *The Eleventh International Conference on Learning Representations*, 2023.
URL [https://openreview.net/forum?id=mWVoBz4W0u](https://openreview.net/forum?id=mWVoBz4W0u).
- Chen et al. (2020)
Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.
Uniter: Universal image-text representation learning.
In *European conference on computer vision*, pp. 104–120. Springer, 2020.
- Chen et al. (2024b)
Yukang Chen, Fuzhao Xue, Dacheng Li, Qinghao Hu, Ligeng Zhu, Xiuyu Li, Yunhao Fang, Haotian Tang, Shang Yang, Zhijian Liu, Yihui He, Hongxu Yin, Pavlo Molchanov, Jan Kautz, Linxi Fan, Yuke Zhu, Yao Lu, and Song Han.
Longvila: Scaling long-context visual language models for long videos.
2024b.
- Chen et al. (2024c)
Zhe Chen, Weiyun Wang, Yue Cao, Yangzhou Liu, Zhangwei Gao, Erfei Cui, Jinguo Zhu, Shenglong Ye, Hao Tian, Zhaoyang Liu, et al.
Expanding performance boundaries of open-source multimodal models with model, data, and test-time scaling.
*arXiv preprint arXiv:2412.05271*, 2024c.
- Chen et al. (2024d)
Zhe Chen, Weiyun Wang, Hao Tian, Shenglong Ye, Zhangwei Gao, Erfei Cui, Wenwen Tong, Kongzhi Hu, Jiapeng Luo, Zheng Ma, et al.
How far are we to gpt-4v? closing the gap to commercial multimodal models with open-source suites.
*Science China Information Sciences*, 67(12):220101, 2024d.
- Chen et al. (2024e)
Zhe Chen, Jiannan Wu, Wenhai Wang, Weijie Su, Guo Chen, Sen Xing, Muyan Zhong, Qinglong Zhang, Xizhou Zhu, Lewei Lu, et al.
Internvl: Scaling up vision foundation models and aligning for generic visual-linguistic tasks.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 24185–24198, 2024e.
- Cheng et al. (2025)
Chuanqi Cheng, Jian Guan, Wei Wu, and Rui Yan.
Scaling video-language models to 10k frames via hierarchical differential distillation.
*arXiv preprint arXiv:2504.02438*, 2025.
- Chu et al. (2011)
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.
Contextual bandits with linear payoff functions.
In *Proceedings of the fourteenth international conference on artificial intelligence and statistics*, pp. 208–214. JMLR Workshop and Conference Proceedings, 2011.
- Driess et al. (2023)
Danny Driess, Fei Xia, Mehdi S. M. Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, Wenlong Huang, Yevgen Chebotar, Pierre Sermanet, Daniel Duckworth, Sergey Levine, Vincent Vanhoucke, Karol Hausman, Marc Toussaint, Klaus Greff, Andy Zeng, Igor Mordatch, and Pete Florence.
Palm-e: An embodied multimodal language model.
In *arXiv preprint arXiv:2303.03378*, 2023.
- Even-Dar et al. (2002)
Eyal Even-Dar, Shie Mannor, and Yishay Mansour.
Pac bounds for multi-armed bandit and markov decision processes.
In *International Conference on Computational Learning Theory*, pp. 255–270. Springer, 2002.
- Even-Dar et al. (2006)
Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan.
Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.
*Journal of machine learning research*, 7(6), 2006.
- Fu et al. (2025)
Chaoyou Fu, Yuhan Dai, Yongdong Luo, Lei Li, Shuhuai Ren, Renrui Zhang, Zihan Wang, Chenyu Zhou, Yunhang Shen, Mengdan Zhang, et al.
Video-mme: The first-ever comprehensive evaluation benchmark of multi-modal llms in video analysis.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 24108–24118, 2025.
- Gao et al. (2019)
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou.
Batched multi-armed bandits problem.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Guo et al. (2025)
Weiyu Guo, Ziyang Chen, Shaoguang Wang, Jianxiang He, Yijie Xu, Jinhui Ye, Ying Sun, and Hui Xiong.
Logic-in-frames: Dynamic keyframe search via visual semantic-logical verification for long video understanding.
*arXiv preprint arXiv:2503.13139*, 2025.
- Hu et al. (2025)
Kai Hu, Feng Gao, Xiaohan Nie, Peng Zhou, Son Tran, Tal Neiman, Lingyun Wang, Mubarak Shah, Raffay Hamid, Bing Yin, et al.
M-llm based video frame selection for efficient video understanding.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 13702–13712, 2025.
- Jamieson et al. (2014)
Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck.
lil’ucb: An optimal exploration algorithm for multi-armed bandits.
In *Conference on Learning Theory*, pp. 423–439. PMLR, 2014.
- Jia et al. (2021)
Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, Yun-Hsuan Sung, Zhen Li, and Tom Duerig.
Scaling up visual and vision-language representation learning with noisy text supervision.
In *International conference on machine learning*, pp. 4904–4916. PMLR, 2021.
- Jin et al. (2024)
Tianyuan Jin, Yu Yang, Jing Tang, Xiaokui Xiao, and Pan Xu.
Optimal batched best arm identification.
*Advances in Neural Information Processing Systems*, 37:134947–134980, 2024.
- Jun et al. (2016)
Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu.
Top arm identification in multi-armed bandits with batch arm pulls.
In *Artificial Intelligence and Statistics*, pp. 139–148. PMLR, 2016.
- Kalyanakrishnan & Stone (2010)
Shivaram Kalyanakrishnan and Peter Stone.
Efficient selection of multiple bandit arms: Theory and practice.
In *ICML*, volume 10, pp. 511–518, 2010.
- Kalyanakrishnan et al. (2012)
Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone.
Pac subset selection in stochastic multi-armed bandits.
In *ICML*, volume 12, pp. 655–662, 2012.
- Karnin et al. (2013)
Zohar Karnin, Tomer Koren, and Oren Somekh.
Almost optimal exploration in multi-armed bandits.
In *International conference on machine learning*, pp. 1238–1246. PMLR, 2013.
- Kaufmann et al. (2016)
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.
On the complexity of best-arm identification in multi-armed bandit models.
*The Journal of Machine Learning Research*, 17(1):1–42, 2016.
- Kleinberg et al. (2008)
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.
Multi-armed bandits in metric spaces.
In *Proceedings of the fortieth annual ACM symposium on Theory of computing*, pp. 681–690, 2008.
- Lai & Robbins (1985)
Tze Leung Lai and Herbert Robbins.
Asymptotically efficient adaptive allocation rules.
*Advances in applied mathematics*, 6(1):4–22, 1985.
- Lattimore & Szepesvári (2020)
Tor Lattimore and Csaba Szepesvári.
*Bandit algorithms*.
Cambridge University Press, 2020.
- Lei et al. (2021)
Jie Lei, Linjie Li, Luowei Zhou, Zhe Gan, Tamara L Berg, Mohit Bansal, and Jingjing Liu.
Less is more: Clipbert for video-and-language learning via sparse sampling.
In *Proceedings of the IEEE/CVF conference on computer vision and pattern recognition*, pp. 7331–7341, 2021.
- Li et al. (2025)
Bo Li, Yuanhan Zhang, Dong Guo, Renrui Zhang, Feng Li, Hao Zhang, Kaichen Zhang, Peiyuan Zhang, Yanwei Li, Ziwei Liu, and Chunyuan Li.
LLaVA-onevision: Easy visual task transfer.
*Transactions on Machine Learning Research*, 2025.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=zKv8qULV6n](https://openreview.net/forum?id=zKv8qULV6n).
- Li et al. (2024a)
Dongxu Li, Yudong Liu, Haoning Wu, Yue Wang, Zhiqi Shen, Bowen Qu, Xinyao Niu, Fan Zhou, Chengen Huang, Yanpeng Li, et al.
Aria: An open multimodal native mixture-of-experts model.
*arXiv preprint arXiv:2410.05993*, 2024a.
- Li et al. (2021)
Junnan Li, Ramprasaath Selvaraju, Akhilesh Gotmare, Shafiq Joty, Caiming Xiong, and Steven Chu Hong Hoi.
Align before fuse: Vision and language representation learning with momentum distillation.
*Advances in neural information processing systems*, 34:9694–9705, 2021.
- Li et al. (2022)
Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.
Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.
In *International conference on machine learning*, pp. 12888–12900. PMLR, 2022.
- Li et al. (2023)
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.
Blip-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.
In *International conference on machine learning*, pp. 19730–19742. PMLR, 2023.
- Li et al. (2024b)
KunChang Li, Yinan He, Yi Wang, Yizhuo Li, Wenhai Wang, Ping Luo, Yali Wang, Limin Wang, and Yu Qiao.
Videochat: Chat-centric video understanding, 2024b.
URL [https://arxiv.org/abs/2305.06355](https://arxiv.org/abs/2305.06355).
- Li et al. (2020)
Linjie Li, Yen-Chun Chen, Yu Cheng, Zhe Gan, Licheng Yu, and Jingjing Liu.
HERO: Hierarchical encoder for Video+Language omni-representation pre-training.
In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu (eds.), *Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)*, pp. 2046–2065, Online, November 2020. Association for Computational Linguistics.
doi: 10.18653/v1/2020.emnlp-main.161.
URL [https://aclanthology.org/2020.emnlp-main.161/](https://aclanthology.org/2020.emnlp-main.161/).
- Li et al. (2019)
Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang.
Visualbert: A simple and performant baseline for vision and language.
*arXiv preprint arXiv:1908.03557*, 2019.
- Li et al. (2024c)
Yanwei Li, Chengyao Wang, and Jiaya Jia.
Llama-vid: An image is worth 2 tokens in large language models.
In *European Conference on Computer Vision*, pp. 323–340. Springer, 2024c.
- Liang et al. (2024)
Hao Liang, Jiapeng Li, Tianyi Bai, Xijie Huang, Linzhuang Sun, Zhengren Wang, Conghui He, Bin Cui, Chong Chen, and Wentao Zhang.
Keyvideollm: Towards large-scale video keyframe selection.
*CoRR*, 2024.
- Lin et al. (2023)
Bin Lin, Yang Ye, Bin Zhu, Jiaxi Cui, Munan Ning, Peng Jin, and Li Yuan.
Video-llava: Learning united visual representation by alignment before projection.
*arXiv preprint arXiv:2311.10122*, 2023.
- Liu et al. (2023)
Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee.
Visual instruction tuning, 2023.
URL [https://arxiv.org/abs/2304.08485](https://arxiv.org/abs/2304.08485).
- Liu et al. (2024a)
Haotian Liu, Chunyuan Li, Yuheng Li, Bo Li, Yuanhan Zhang, Sheng Shen, and Yong Jae Lee.
Llava-next: Improved reasoning, ocr, and world knowledge, January 2024a.
URL [https://llava-vl.github.io/blog/2024-01-30-llava-next/](https://llava-vl.github.io/blog/2024-01-30-llava-next/).
- Liu et al. (2024b)
Jiajun Liu, Yibing Wang, Hanghang Ma, Xiaoping Wu, Xiaoqi Ma, Xiaoming Wei, Jianbin Jiao, Enhua Wu, and Jie Hu.
Kangaroo: A powerful video-language model supporting long-context video input, 2024b.
URL [https://arxiv.org/abs/2408.15542](https://arxiv.org/abs/2408.15542).
- Liu et al. (2025)
Shuming Liu, Chen Zhao, Tianqi Xu, and Bernard Ghanem.
Bolt: Boost large vision-language model without training for long-form video understanding.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 3318–3327, 2025.
- Lu et al. (2019)
Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.
Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.
*Advances in neural information processing systems*, 32, 2019.
- Luo et al. (2022)
Huaishao Luo, Lei Ji, Ming Zhong, Yang Chen, Wen Lei, Nan Duan, and Tianrui Li.
Clip4clip: An empirical study of clip for end to end video clip retrieval and captioning.
*Neurocomputing*, 508:293–304, 2022.
- Maaz et al. (2024)
Muhammad Maaz, Hanoona Rasheed, Salman Khan, and Fahad Shahbaz Khan.
Video-chatgpt: Towards detailed video understanding via large vision and language models.
In *Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL 2024)*, 2024.
- Mahasseni et al. (2017)
Behrooz Mahasseni, Michael Lam, and Sinisa Todorovic.
Unsupervised video summarization with adversarial lstm networks.
In *Proceedings of the IEEE conference on Computer Vision and Pattern Recognition*, pp. 202–211, 2017.
- Perchet et al. (2016)
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.
Batched bandit problems.
2016.
- Qian et al. (2024)
Rui Qian, Xiaoyi Dong, Pan Zhang, Yuhang Zang, Shuangrui Ding, Dahua Lin, and Jiaqi Wang.
Streaming long video understanding with large language models.
*Advances in Neural Information Processing Systems*, 37:119336–119360, 2024.
- Qin et al. (2025)
Minghao Qin, Xiangrui Liu, Zhengyang Liang, Yan Shu, Huaying Yuan, Juenjie Zhou, Shitao Xiao, Bo Zhao, and Zheng Liu.
Video-xl-2: Towards very long-video understanding through task-aware kv sparsification.
*arXiv preprint arXiv:2506.19225*, 2025.
- Radford et al. (2021)
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.
Learning transferable visual models from natural language supervision.
In *International conference on machine learning*, pp. 8748–8763. PmLR, 2021.
- Shen et al. (2024)
Xiaoqian Shen, Yunyang Xiong, Changsheng Zhao, Lemeng Wu, Jun Chen, Chenchen Zhu, Zechun Liu, Fanyi Xiao, Balakrishnan Varadarajan, Florian Bordes, et al.
Longvu: Spatiotemporal adaptive compression for long video-language understanding.
*arXiv preprint arXiv:2410.17434*, 2024.
- Shen et al. (2025)
Yunhang Shen, Chaoyou Fu, Shaoqi Dong, Xiong Wang, Yi-Fan Zhang, Peixian Chen, Mengdan Zhang, Haoyu Cao, Ke Li, Xiawu Zheng, et al.
Long-vita: Scaling large multi-modal models to 1 million tokens with leading short-context accuracy.
*arXiv preprint arXiv:2502.05177*, 2025.
- Song et al. (2024)
Enxin Song, Wenhao Chai, Guanhong Wang, Yucheng Zhang, Haoyang Zhou, Feiyang Wu, Haozhe Chi, Xun Guo, Tian Ye, Yanting Zhang, et al.
Moviechat: From dense token to sparse memory for long video understanding.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 18221–18232, 2024.
- Su et al. (2020)
Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai.
Vl-bert: Pre-training of generic visual-linguistic representations.
In *International Conference on Learning Representations*, 2020.
URL [https://openreview.net/forum?id=SygXPaEYvH](https://openreview.net/forum?id=SygXPaEYvH).
- Sun et al. (2019)
Chen Sun, Austin Myers, Carl Vondrick, Kevin Murphy, and Cordelia Schmid.
Videobert: A joint model for video and language representation learning.
In *Proceedings of the IEEE/CVF international conference on computer vision*, pp. 7464–7473, 2019.
- Tan & Bansal (2019)
Hao Tan and Mohit Bansal.
Lxmert: Learning cross-modality encoder representations from transformers.
In *Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing*, 2019.
- Tang et al. (2025)
Xi Tang, Jihao Qiu, Lingxi Xie, Yunjie Tian, Jianbin Jiao, and Qixiang Ye.
Adaptive keyframe sampling for long video understanding.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 29118–29128, 2025.
- Tuynman & Degenne (2025)
Adrienne Tuynman and Rémy Degenne.
The batch complexity of bandit pure exploration.
*arXiv preprint arXiv:2502.01425*, 2025.
- Wang et al. (2016)
Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool.
Temporal segment networks: Towards good practices for deep action recognition.
In *European conference on computer vision*, pp. 20–36. Springer, 2016.
- Wang et al. (2022a)
Peng Wang, An Yang, Rui Men, Junyang Lin, Shuai Bai, Zhikang Li, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang.
Ofa: Unifying architectures, tasks, and modalities through a simple sequence-to-sequence learning framework.
In *International conference on machine learning*, pp. 23318–23340. PMLR, 2022a.
- Wang et al. (2024a)
Peng Wang, Shuai Bai, Sinan Tan, Shijie Wang, Zhihao Fan, Jinze Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, et al.
Qwen2-vl: Enhancing vision-language model’s perception of the world at any resolution.
*arXiv preprint arXiv:2409.12191*, 2024a.
- Wang et al. (2024b)
Xiaohan Wang, Yuhui Zhang, Orr Zohar, and Serena Yeung-Levy.
Videoagent: Long-form video understanding with large language model as agent.
In *European Conference on Computer Vision*, pp. 58–76. Springer, 2024b.
- Wang et al. (2022b)
Yi Wang, Kunchang Li, Yizhuo Li, Yinan He, Bingkun Huang, Zhiyu Zhao, Hongjie Zhang, Jilan Xu, Yi Liu, Zun Wang, et al.
Internvideo: General video foundation models via generative and discriminative learning.
*arXiv preprint arXiv:2212.03191*, 2022b.
- Wang et al. (2024c)
Yi Wang, Kunchang Li, Xinhao Li, Jiashuo Yu, Yinan He, Guo Chen, Baoqi Pei, Rongkun Zheng, Zun Wang, Yansong Shi, et al.
Internvideo2: Scaling foundation models for multimodal video understanding.
In *European Conference on Computer Vision*, pp. 396–416. Springer, 2024c.
- Wang et al. (2025)
Ziyang Wang, Shoubin Yu, Elias Stengel-Eskin, Jaehong Yoon, Feng Cheng, Gedas Bertasius, and Mohit Bansal.
Videotree: Adaptive tree-based video representation for llm reasoning on long videos.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 3272–3283, 2025.
- Weng et al. (2024)
Yuetian Weng, Mingfei Han, Haoyu He, Xiaojun Chang, and Bohan Zhuang.
Longvlm: Efficient long video understanding via large language models.
In *European Conference on Computer Vision*, pp. 453–470. Springer, 2024.
- Wiegand et al. (2003)
Thomas Wiegand, Gary J Sullivan, Gisle Bjontegaard, and Ajay Luthra.
Overview of the h. 264/avc video coding standard.
*IEEE Transactions on circuits and systems for video technology*, 13(7):560–576, 2003.
- Wu et al. (2024)
Haoning Wu, Dongxu Li, Bei Chen, and Junnan Li.
Longvideobench: A benchmark for long-context interleaved video-language understanding.
*Advances in Neural Information Processing Systems*, 37:28828–28857, 2024.
- Xu et al. (2024)
Lin Xu, Yilin Zhao, Daquan Zhou, Zhijie Lin, See Kiong Ng, and Jiashi Feng.
Pllava : Parameter-free llava extension from images to videos for video dense captioning, 2024.
- Yang et al. (2024)
An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, et al.
Qwen2 technical report, 2024.
*URL https://arxiv. org/abs/2407.10671*, 7:8, 2024.
- Yang et al. (2022)
Antoine Yang, Antoine Miech, Josef Sivic, Ivan Laptev, and Cordelia Schmid.
Zero-shot video question answering via frozen bidirectional language models.
*Advances in Neural Information Processing Systems*, 35:124–141, 2022.
- Yao et al. (2022)
Lewei Yao, Runhui Huang, Lu Hou, Guansong Lu, Minzhe Niu, Hang Xu, Xiaodan Liang, Zhenguo Li, Xin Jiang, and Chunjing Xu.
FILIP: Fine-grained interactive language-image pre-training.
In *International Conference on Learning Representations*, 2022.
URL [https://openreview.net/forum?id=cpDhcsEDC2](https://openreview.net/forum?id=cpDhcsEDC2).
- Yao et al. (2024)
Yuan Yao, Tianyu Yu, Ao Zhang, Chongyi Wang, Junbo Cui, Hongji Zhu, Tianchi Cai, Haoyu Li, Weilin Zhao, Zhihui He, et al.
Minicpm-v: A gpt-4v level mllm on your phone.
*arXiv preprint arXiv:2408.01800*, 2024.
- Yu et al. (2022)
Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu.
Coca: Contrastive captioners are image-text foundation models.
*Transactions on Machine Learning Research*, 2022.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=Ee277P3AYC](https://openreview.net/forum?id=Ee277P3AYC).
- Yu et al. (2024)
Sicheng Yu, Chengkai Jin, Huanyu Wang, Zhenghao Chen, Sheng Jin, Zhongrong Zuo, Xiaolei Xu, Zhenbang Sun, Bingni Zhang, Jiawei Wu, et al.
Frame-voyager: Learning to query frames for video large language models.
*arXiv preprint arXiv:2410.03226*, 2024.
- Zhang et al. (2025a)
Boqiang Zhang, Kehan Li, Zesen Cheng, Zhiqiang Hu, Yuqian Yuan, Guanzheng Chen, Sicong Leng, Yuming Jiang, Hang Zhang, Xin Li, et al.
Videollama 3: Frontier multimodal foundation models for image and video understanding.
*arXiv preprint arXiv:2501.13106*, 2025a.
- Zhang et al. (2018)
Chaoying Zhang, Yaping Dai, Yanyan Cheng, Zhiyang Jia, and Kaoru Hirota.
Recurrent attention lstm model for image chinese caption generation.
In *2018 Joint 10th International Conference on Soft Computing and Intelligent Systems (SCIS) and 19th International Symposium on Advanced Intelligent Systems (ISIS)*, pp. 808–813. IEEE, 2018.
- Zhang et al. (2023)
Hang Zhang, Xin Li, and Lidong Bing.
Video-llama: An instruction-tuned audio-visual language model for video understanding.
*arXiv preprint arXiv:2306.02858*, 2023.
- Zhang et al. (2024a)
Kaichen Zhang, Bo Li, Peiyuan Zhang, Fanyi Pu, Joshua Adrian Cahyono, Kairui Hu, Shuai Liu, Yuanhan Zhang, Jingkang Yang, Chunyuan Li, et al.
Lmms-eval: Reality check on the evaluation of large multimodal models.
*arXiv preprint arXiv:2407.12772*, 2024a.
- Zhang et al. (2016)
Ke Zhang, Wei-Lun Chao, Fei Sha, and Kristen Grauman.
Video summarization with long short-term memory.
In *European conference on computer vision*, pp. 766–782. Springer, 2016.
- Zhang et al. (2024b)
Peiyuan Zhang, Kaichen Zhang, Bo Li, Guangtao Zeng, Jingkang Yang, Yuanhan Zhang, Ziyue Wang, Haoran Tan, Chunyuan Li, and Ziwei Liu.
Long context transfer from language to vision.
*arXiv preprint arXiv:2406.16852*, 2024b.
URL [https://arxiv.org/abs/2406.16852](https://arxiv.org/abs/2406.16852).
- Zhang et al. (2025b)
Shaojie Zhang, Jiahui Yang, Jianqin Yin, Zhenbo Luo, and Jian Luan.
Q-frame: Query-aware frame selection and multi-resolution adaptation for video-llms.
*arXiv preprint arXiv:2506.22139*, 2025b.
- Zhang et al. (2024c)
Yuanhan Zhang, Bo Li, haotian Liu, Yong jae Lee, Liangke Gui, Di Fu, Jiashi Feng, Ziwei Liu, and Chunyuan Li.
Llava-next: A strong zero-shot video understanding model, April 2024c.
URL [https://llava-vl.github.io/blog/2024-04-30-llava-next-video/](https://llava-vl.github.io/blog/2024-04-30-llava-next-video/).
- Zhang et al. (2025c)
Yuanhan Zhang, Jinming Wu, Wei Li, Bo Li, Zejun Ma, Ziwei Liu, and Chunyuan Li.
Video instruction tuning with synthetic data.
*Transactions on Machine Learning Research*, 2025c.
- Zhao et al. (2017)
Bin Zhao, Xuelong Li, and Xiaoqiang Lu.
Hierarchical recurrent neural network for video summarization.
In *Proceedings of the 25th ACM international conference on Multimedia*, pp. 863–871, 2017.
- Zhou et al. (2018)
Kaiyang Zhou, Yu Qiao, and Tao Xiang.
Deep reinforcement learning for unsupervised video summarization with diversity-representativeness reward.
In *Proceedings of the AAAI conference on artificial intelligence*, volume 32, 2018.
- Zhu et al. (2024)
Bin Zhu, Bin Lin, Munan Ning, Yang Yan, Jiaxi Cui, WANG HongFa, Yatian Pang, Wenhao Jiang, Junwu Zhang, Zongwei Li, Cai Wan Zhang, Zhifeng Li, Wei Liu, and Li Yuan.
Languagebind: Extending video-language pretraining to n-modality by language-based semantic alignment.
In *The Twelfth International Conference on Learning Representations*, 2024.
URL [https://openreview.net/forum?id=QmZKc7UZCy](https://openreview.net/forum?id=QmZKc7UZCy).

## Appendix A Appendix

### A.1 Related Work

#### A.1.1 Multimodal Large Language Models (MLLMs) for Video Understanding

Recent MLLMs extend large language models with visual encoders, encoding images or frames into visual tokens that are fused with text to support open-ended video understanding. Most follow an encode-project-fuse pipeline with instruction tuning, as exemplified by the LLaVA family, Video-LLaVA/Video-LLaMA/Video-ChatGPT, and LLaMA-Vid/VideoChat (Liu et al., 2023; Lin et al., 2023; Zhang et al., 2023; Maaz et al., 2024; Li et al., 2024c; b). Progress has largely come from scaling data/backbones and strengthening cross-modal alignment (MiniCPM-V, InternVL/InternVL2, Qwen2-VL; data-centric and modality-binding advances via ShareGPT4Video and LanguageBind) (Yao et al., 2024; Chen et al., 2024e; d; c; Wang et al., 2024a; Chen et al., 2024a; Zhu et al., 2024), together with architectural refinements that unify multi-granularity visual inputs and tighten temporal adapters, and that improve projector efficiency or curricula (LLaVA-OneVision, LLaVA-NeXT/LLaVA-NeXT-Video, Aria, PLLaVA, Kangaroo) (Li et al., 2025; Liu et al., 2024a; Zhang et al., 2024c; Li et al., 2024a; Xu et al., 2024; Liu et al., 2024b). Finally, several models explicitly target extended context and hierarchical summarization for long-form understanding (LongVILA, LongVA, LongVLM, LongVU) (Chen et al., 2024b; Zhang et al., 2024b; Weng et al., 2024; Shen et al., 2024).

However, this tokenization-first paradigm encounters *token explosion* on long videos, where dense sampling yields prohibitive sequences. Recent efforts reduce the budget by compressing or restructuring tokens: MovieChat (Song et al., 2024) compacts frames into sparse memory, Video-XL-2 (Qin et al., 2025) synthesizes condensed tokens, and VideoStreaming (Qian et al., 2024) processes streams incrementally to cap tokens. Planning/tool-augmented agents (e.g., VideoAgent (Wang et al., 2024b)) curb perception via selective analysis, while hierarchical controllers (VideoTree (Wang et al., 2025)) and scaling recipes (VideoLLaMA 3 (Zhang et al., 2025a)) aid long-horizon reasoning. Beyond compression, ViLAMP (Cheng et al., 2025) uses mixed-precision tokenization to emphasize differential frames/patches and allocate capacity adaptively; long-context instruction-tuning such as Long-VITA (Shen et al., 2025) complements these strategies for long videos.

#### A.1.2 Vision-Language Pretrained Models

Cross-modal vision-language pretraining spans two-stream fusion, single-stream fusion, dual-encoder contrastive learning, and encoder-decoder hybrids. Two-stream models such as ViLBERT (Lu et al., 2019) and LXMERT (Tan & Bansal, 2019) encode vision and text separately and fuse via cross-attention, while single-stream counterparts—VisualBERT (Li et al., 2019), VL-BERT (Su et al., 2020), UNITER (Chen et al., 2020)—concatenate region features with text in a unified Transformer using MLM and alignment losses. Large-scale dual encoders like CLIP (Radford et al., 2021) and ALIGN (Jia et al., 2021) learn contrastive embeddings for zero-shot transfer, with FILIP (Yao et al., 2022) improving fine-grained patch-token alignment. Hybrid objectives combine contrastive and generative training (Li et al., 2021; Yu et al., 2022; Wang et al., 2022a; Chen et al., 2023) unify captioning and VQA. The BLIP family integrates vision encoders with language modeling—BLIP (Li et al., 2022) and BLIP-2 (Li et al., 2023) (via a lightweight Q-Former)—while Flamingo (Alayrac et al., 2022) and PaLM-E (Driess et al., 2023) inject visual inputs into large LMs for few-shot multimodal reasoning.

Extending to video, early pretraining models learned joint spatio-temporal-language representations with lightweight fusion and sparse sampling. VideoBERT (Sun et al., 2019) pairs frame sequences with transcripts in a BERT-style objective for retrieval and script generation, while HERO (Li et al., 2020) and ClipBERT (Lei et al., 2021) improve efficiency via hierarchical encoding and key-frame sampling for video-text retrieval and QA. Building directly on large image-text models, Clip4Clip (Luo et al., 2022) reuses CLIP encoders and matches videos to text via contrastive similarity, and FrozenBiLM (Yang et al., 2022) freezes a bi-directional LM while aligning a video encoder for zero-shot VQA.

#### A.1.3 Keyframe Selection

In video representation learning, keyframe selection spans two major paradigms.

##### Training-free keyframe selection.

Recent *training-free* methods leverage pretrained vision-language models and lightweight heuristics to pick informative, query-relevant frames. Adaptive Keyframe Sampling (AKS) maximizes prompt-frame similarity while enforcing temporal coverage via a split-and-judge policy (Tang et al., 2025); Q-Frame ranks frames by query-conditioned importance and preserves a few at higher resolution for detail (Zhang et al., 2025b). Text-frame alignment with frozen models further enables plug-and-play selectors (KeyVideoLLM, BOLT) that boost Video-LLM performance without fine-tuning (Liang et al., 2024; Liu et al., 2025). To avoid redundancy and preserve structure under a token budget, Logic-in-Frames performs dynamic, logic-verified search (Guo et al., 2025), while VideoTree builds a hierarchical, query-adaptive frame pyramid that expands salient scenes (Wang et al., 2025).

##### Instruction-aligned and learned selectors.

Instruction-guided approaches train selectors with LLM/MLLM feedback: Frame-Voyager learns to query frame combinations by ranking sets with a pretrained Video-LLM (Yu et al., 2024), and Hu et al. (2025) supervise a lightweight selector using MLLM-derived single-frame relevance and multi-frame complementarity. Classical summarization remains relevant: supervised LSTM-based models (vsLSTM, dppLSTM; hierarchical RNNs) learn importance/diversity from human summaries (Zhang et al., 2016; 2018; Zhao et al., 2017), while unsupervised RL/adversarial methods (DR-DSN, SUM-GAN) optimize diversity-representativeness or realism without labels (Zhou et al., 2018; Mahasseni et al., 2017); however, these are typically task-agnostic and may miss frames critical for query-driven VQA.

#### A.1.4 Multi-Armed Bandits and Batched Exploration

Multi-armed bandits (MAB) encompass both regret minimization and pure exploration. Regret-oriented methods such as UCB variants and Thompson Sampling establish logarithmic-regret foundations for sequential decision-making (Auer et al., 2002; Lai & Robbins, 1985; Agrawal & Goyal, 2012). Pure exploration instead targets high-confidence identification with minimal samples, formalized as best-arm (and top-$k$) identification (Even-Dar et al., 2006; Bubeck et al., 2009; Kalyanakrishnan & Stone, 2010; Cao et al., 2015). Early elimination schemes (Successive/Median Elimination) provide PAC guarantees (Even-Dar et al., 2006; 2002), while confidence-bound and racing families—LUCB, UCB-E, and near-optimal lil’UCB—sharpen sample complexity and approach known lower bounds (Kalyanakrishnan et al., 2012; Audibert & Bubeck, 2010; Karnin et al., 2013; Jamieson et al., 2014; Kaufmann et al., 2016). Beyond single arms, combinatorial pure exploration (CPE) seeks an optimal subset under structural constraints, combining bandit confidence bounds with combinatorial oracles to search exponentially large spaces efficiently (Chen et al., 2016; Lattimore & Szepesvári, 2020).

Fully sequential adaptivity can be impractical when decisions must be made in few rounds or in parallel. Batched (parallel) bandits address this by operating over a small number of adaptivity rounds, yet retain near-sequential sample efficiency for pure exploration in theory and practice (Perchet et al., 2016; Jun et al., 2016; Gao et al., 2019). Batch-elimination/LUCB-style procedures match sequential complexity up to constants with only a handful of updates (Jun et al., 2016), and lower-bound trade-offs between batches and samples are well understood with matching algorithms (Perchet et al., 2016; Kaufmann et al., 2016; Tuynman & Degenne, 2025). Recent designs such as Tri-BBAI attain asymptotically optimal fixed-confidence BAI with just three batches, underscoring the feasibility of resource-constrained exploration (Jin et al., 2024).

## Appendix B Bernstein Confidence Radius

###### Theorem B.1 .

Let $N_{a}(n)$ be the number of pulls for arm $a$ at round $n$ and $n=\sum_{a\in\mathcal{A}}N_{a}(n)$ is the total number of pulls. Let $\hat{\mu}_{a}(n)$ be the empirical mean of arm $a$ at round $n$ and $\hat{\sigma}_{a}^{2}(n)$ be the empirical variance of arm $a$ at round $n$. We define the empirical Bernstein Confidence Radius $\beta_{a}(n)$ as

$$ $\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))}.$ $$

Then we have the following bound holds with probability at least $1-\frac{6}{n}$:

$$ $\left|\hat{\mu}_{a}-\mu_{a}\right|\leq\beta_{a}(n)$ $$

###### Proof.

Under the setting of frame-query relevance setting, the reward $r_{t}$ and latent frame reward $y_{t}$ is naturally bounded in $[0,1]$. Therefore, according to Bernstein inequality, for any $\delta\in(0,1)$, we have

$$ $\mathcal{P}\left[\mu_{a}\leq\hat{\mu}_{a}(n)+\sqrt{\frac{2\hat{\sigma}_{a}^{2}\ln\frac{3}{\delta}}{N_{a}(n)}}+\frac{3\ln\frac{3}{\delta}}{N_{a}(n)}\right]\geq 1-\delta.$ $$

And symmetrically, we have

$$ $\mathcal{P}\left[\mu_{a}\geq\hat{\mu}_{a}(n)-\sqrt{\frac{2\hat{\sigma}_{a}^{2}\ln\frac{3}{\delta}}{N_{a}(n)}}-\frac{3\ln\frac{3}{\delta}}{N_{a}(n)}\right]\geq 1-\delta.$ $$

Therefore, we have

$$ $\mathcal{P}\left[\left|\hat{\mu}_{a}-\mu_{a}\right|\leq\sqrt{\frac{2\hat{\sigma}_{a}^{2}\ln\frac{3}{\delta}}{N_{a}(n)}}+\frac{3\ln\frac{3}{\delta}}{N_{a}(n)}\right]\geq 1-2\delta.$ $$

Choose $\delta=\frac{3}{n}$, then we have

$$ $\left|\mu_{a}-\hat{\mu}_{a}(n)\right|\leq\sqrt{\frac{2\hat{\sigma}_{a}^{2}\ln\frac{3}{\delta}}{N_{a}(n)}}+\frac{3\ln\frac{3}{\delta}}{N_{a}(n)}.$ $$

holds with probability at least $1-\frac{6}{n}$.

When $N_{a}(n)=0$, the statement is trivially true. Thus, we have the following bound holds with probability at least $1-\frac{6}{n}$:

$$ $\left|\mu_{a}-\hat{\mu}_{a}(n)\right|\leq\beta_{a}(n).$ $$

∎

###### Theorem B.1 .

###### Proof.

## Appendix C Regret Bound

##### Arm-level Regret Bound

###### Theorem C.1 .

Algorithm [2](https://arxiv.org/html/2510.27280v1#alg2) returns the oracle top-$s$ set $S^{\star}$ with probability at least $1-\frac{6M}{n}$ when terminated.

###### Proof.

When Algorithm [2](https://arxiv.org/html/2510.27280v1#alg2) terminates, the following condition holds:

$$ $\max_{a\notin\hat{S}}\hat{\mu}_{n}(a)+\beta_{a}(n)\leq\min_{a\in\hat{S}}\hat{\mu}_{n}(a)-\beta_{a}(n).$ $$

According to Theorem [B.1](https://arxiv.org/html/2510.27280v1#A2.Thmtheorem1), with probability at least $1-\frac{6}{n}$, we have $\left|\mu_{a}-\hat{\mu}_{a}(n)\right|\leq\beta_{a}(n)$ for all arms $a$. Therefore, for any $a\notin\hat{S}$,

$$ $\mathcal{P}\left[a\in S^{\star}\right]\leq 1-\frac{6}{n}.$ $$

Thus, the probability that there does not exist such an arm $a$ is at least $1-\frac{6(M-m)}{n}$, where $m$ is size of the $\hat{S}$ set.
And this completes the proof.
∎

###### Theorem C.1 .

###### Proof.

##### Frame-level Regret Bound

We define the frame-level regret as the difference between the optimal frame-level reward and the reward of the selected frames.

$$ $r_{N}^{\mathrm{frame}}=\sum_{t\in{\mathbb{K}}^{\star}}y_{t}-\sum_{t\in\widehat{{\mathbb{K}}}_{n}}y_{t}.$ $$

As long as we obtain the oracle top-$s$ set $S^{\star}$, the frame-level regret is also guaranteed to be small. As Frame-level sampling is actually finite so we can always find the top-$k$ frames with the highest rewards.

$$ $\mathbb{E}r_{N}^{\mathrm{frame}}=\mathbb{E}\sum_{t\in{\mathbb{K}}^{\star}}y_{t}-\sum_{t\in\widehat{{\mathbb{K}}}_{n}}y_{t}\\ =\mathbb{E}\sum_{a\in S^{\star}}\sum_{t\in{\mathbb{K}}_{a}^{\star}}2\epsilon_{\psi}=0.$ $$

For tighter bound, we leave this to future work.

## Appendix D Limitations

In this work, we assume the frame-query relevance scores are i.i.d. and the temporal dependencies between frames are not considered.
However, in practice, the frame-query relevance scores are dependent on the temporal dependencies between frames. As different parts may have strong correlations, this assumption may not hold.
In this setting, we can use the Lipschitz/metric bandit problem (Kleinberg et al., 2008; Bubeck et al., 2011) or contextual bandit problem (Chu et al., 2011; Agarwal et al., 2014) to model the problem. We leave this as future work.

## Appendix E The Use of Large Language Models (LLMs)

We used GPT-5 and Claude 4 solely for proofreading and light copy-editing (typos, grammar, and minor phrasing). All technical content, scientific claims, mathematical proofs, algorithms, experiment design and execution, dataset handling, figures, and evaluations were authored and verified by the human authors. LLMs were not used to generate ideas, code, data, results, or reviews; they did not contribute content at the level of a co-author. All suggested edits were manually inspected and accepted or rejected by the authors.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: As mentioned in the Weaknesses section, I believe additional ablation studies would greatly help clarify the method’s behavior and limitations. In particular, it would be valuable to see how different choices of M (number of clips) or other hyperparameters affect both performance and efficiency.
Additionally, it would be interesting to explore how the proposed method performs on spatially focused video understanding tasks, where temporal redundancy is less dominant. Such experiments could provide insights into the generality and potential boundaries of the FOCUS framework.
soundness: 3
strengths: 1. The paper is original in formulating keyframe selection for long-video understanding as a combinatorial pure-exploration multi-armed bandit problem. This is a novel and reasonable perspective that provides new theoretical and algorithmic insights for researchers working on efficient video representation and token budgeting.
2. The proposed two-stage coarse-to-fine procedure effectively addresses the non-parallelizable nature of sequential arm-pulling and updating, providing a practical solution that improves efficiency with minimal performance loss. This design is both elegant and empirically effective.
3. The paper also shows strong theoretical grounding and empirical validation. The theoretical analysis is clear and complete, and the experiments are comprehensive, covering multiple benchmarks and models. The results align well with the theoretical claims, reinforcing the soundness and significance of the contribution.
summary: The paper presents FOCUS (Frame-Optimistic Confidence Upper-bound Selection), a training-free and model-agnostic keyframe selection approach designed to improve long-video understanding in multimodal large language models (MLLMs). The authors formulate keyframe selection as a combinatorial pure-exploration problem within a multi-armed bandit framework, leveraging empirical means and Bernstein-style confidence bounds to balance exploration and exploitation. A two-stage coarse-to-fine procedure is further proposed to enable efficient and parallel computation. Experiments on LongVideoBench and Video-MME demonstrate consistent accuracy gains across multiple MLLMs. Overall, the paper provides an efficient and theoretically grounded solution to long-video understanding under tight token budget constraints.
weaknesses: 1. In Section 2.2, the paper assumes that “frame-level utility within the same arm share the same distribution.” It is unclear how this assumption is ensured in practice, especially regarding how the M non-overlapping fixed-length clips are partitioned. For instance, when the video contains shot changes or scene transitions, it is not clear how these are handled or whether the authors explored alternative segmentation strategies.
2. The experiments are limited to LongVideoBench and Video-MME, both of which focus on long-form video QA. Evaluating the method on datasets with different characteristics—such as spatial reasoning benchmarks (e.g., VSI-Bench) or shorter video datasets—would provide a better understanding of the method’s generalizability and potential limitations.
3. I am curious about how the number of clips (M) affects performance and efficiency. Since the method’s core formulation relies on partitioning videos into M fixed-length clips, an ablation study on M (and possibly related hyperparameters) would make the analysis more complete.
4. There are a few minor typos (e.g., a missing period around line 025). The authors are encouraged to carefully proofread the paper to minimize such small errors.

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 2
questions: Can you clarify the BLIP usage in your method? If that's the case, why BLIP and not another text/vision encoder such as Siglip? Do you have any ablations?
soundness: 2
strengths: - The method seems quiet effective in selecting the frames.
- Seem to work well across different MLLMs
- Better accuracy over the AKS method while improving efficiency.
summary: This paper introduces a novel, training-free, and ""model-agnostic"" algorithm for efficient video processing by sampling the most relevant frames. Addressing the limitations of long videos and the short context windows of many Multimodal Large Language Models (MLLMs), the method leverages principles from Bandits research to select frames without relying on external models, unlike approaches such as AKS. The algorithm employs a coarse-to-fine-grained exploitation strategy, demonstrating improved performance over uniform sampling, top-k selection, and the model-based AKS method across various models (Llava, Qwen, GPT-4o) and benchmarks (Video-MME, LongVideoBench). A key advantage is its significantly higher efficiency and reduced GPU hours, as it avoids additional model inference. The method also includes an adjustable hyper-parameter, alpha, to manage the trade-off between accuracy and computational cost (number of frames processed).
weaknesses: - The authors present the method as model-agnostic; however, they appear to leverage BLIP for frame relevance scoring to compute their latent frame-level utility. Even if only 1% of the frames are processed through BLIP, it still relies on a model, making the claim of model-agnosticism questionable. This point should have been better explained in the paper. 
- Lack of comparison with training-based method.
- Could have added more benchmarks such as MLVU, NextQA. MVBench
- Typos, abstract "within each region On two long-video"

---

confidence: 4
contribution: 3
initial_rating: 4
presentation: 3
questions: - Include ablation studies disentangling the effect of each module (coarse/fine, α, confidence radius).
- Compare against stronger or more diverse baselines (Q-Frame, Frame-Voyager, Logic-in-Frames, VSLS, $T^{*}$, Nar-KFC, TimeSearch).
- Evaluate robustness on longer and more diverse benchmarks, such as MLVU and LVBench (general), Ego4D/ EgoSchema (egocentric reasoning), and OVO-Bench / HLV-1K (reasoning).
- Analyze failure cases and provide qualitative insights on when FOCUS fails (e.g., multi-event reasoning).
- Consider extending the method with lightweight learnable scoring or adaptive thresholding to move beyond static heuristics.
soundness: 3
strengths: - **Conceptually elegant and efficient.** The formulation connects keyframe selection with variance-adaptive exploration in MABs, offering a lightweight theoretical lens for efficient inference. The two-stage batched procedure is practical and easily parallelizable, reducing GPU cost by 40–60% compared to AKS.

- **Training-free and modular.** The pipeline is plug-and-play, requires no fine-tuning, and integrates smoothly into existing LVLM inference workflows.

- **Empirically consistent.** Evaluations span multiple datasets, video lengths, and MLLM architectures, with consistent accuracy and efficiency trade-offs (Table 1–4).

- **Clear presentation.** The paper is well-written with informative figures and pseudocode; Algorithm 2 is easy to follow.
summary: This paper introduces FOCUS, a training-free and model-agnostic keyframe selection method for long-video understanding with multimodal large language models (MLLMs). FOCUS frames keyframe selection as a Combinatorial Pure Exploration (CPE) problem under a multi-armed bandit (MAB) formulation, treating short temporal clips as “arms.” By applying a Bernstein-style upper confidence bound (UCB-V) and a two-stage coarse-to-fine exploration scheme, the method efficiently identifies query-relevant temporal regions before selecting keyframes within each. Experiments on LongVideoBench and Video-MME, across four MLLMs (GPT-4o, Qwen2-VL, LLaVA-OV, and LLaVA-Video), show that FOCUS achieves 3–6% accuracy improvements over uniform sampling and comparable or slightly higher performance than recent training-free methods (AKS, Top-K), while processing only ~2% of frames.
weaknesses: - **Incremental novelty.** The “combinatorial pure-exploration bandit” framing is conceptually sound but reuses standard UCB-V principles with minimal adaptation to video reasoning. Similar adaptive sampling ideas have appeared in AKS, Q-Frame, T* and Frame-Voyager.

- **Weak theoretical substance & Limited methodological depth.** The regret bound assumes i.i.d. frame rewards and bounded noise, which do not hold in temporally correlated videos. The theoretical claim does not extend to frame-level optimality, limiting its practical significance. Despite the theoretical motivation, the final algorithm reduces to a fixed two-stage heuristic controlled by α and lacks adaptive or learnable exploration scheduling.

- **Missing core ablations.** The paper does not isolate contributions from key components—coarse vs. fine stages, confidence bounds vs. mean-based selection—so the source of improvement remains unclear.

- **Incomplete experimental comparison.** Evaluation omits recent reasoning-driven or event-centric baselines (e.g., Q-Frame, Logic-in-Frames ...), providing only partial evidence of superiority.

- **Lack of robustness and qualitative analysis.** No systematic study of failure cases, sensitivity to α or clip length, or behavior on complex multi-event queries is provided, leaving generalization uncertain.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: - FOCUS first partition the timeline into $M$ non-overlapping fixed-length clips. Does this destroy the spatiotemporal consistency of the video? Which makes it difficult to capture continuous segments with high information density?

- As discussed in the Limitation section, FOCUS assumes that each frame of the video is independent, which is completely contrary to the nature of the video. Does this limit FOCUS’s applicability to short videos?

- Table 1 lacks the experimental results of other frame selection methods, such as AKS and Q-Frame, based on the same baseline.

- The paper provides a visualization of FOCUS's superiority over uniform sampling in Figure 3. It is meaningful to include the negative aspects of FOCUS, which helps readers better understand its limitations.
soundness: 2
strengths: The paper introduces FOCUS, a training-free keyframe selection method that formulates the task as a combinatorial pure-exploration bandit problem. It partitions the video into clips (arms), uses optimistic confidence upper bounds to identify informative regions with minimal sampling, and then selects top frames within those clips. This two-stage exploration-exploitation strategy enables MLLMs to achieve strong performance on long-video QA benchmarks while processing fewer than 2% of frames. It significantly outperforms uniform sampling and existing retrieval-based methods, especially on videos over 20 minutes.
summary: The paper proposes FOCUS (Frame-Optimistic Confidence Upper-bound Selection), a training-free, model-agnostic keyframe selection method for long video understanding with multimodal LLMs (MLLMs). To address the prohibitive token cost of processing all frames, FOCUS formulates keyframe selection as a combinatorial pure-exploration (CPE) problem in a multi-armed bandit setting, where short temporal clips are treated as arms. It employs a two-stage exploration–exploitation strategy: first using optimistic confidence upper bounds (UCB) to identify promising clips, then selecting top-scoring frames within them. Evaluated on LongVideoBench and Video-MME, FOCUS processes <2% of frames yet achieves consistent gains over uniform sampling and SOTA retrieval-based methods, e.g., +11.9% accuracy on videos >20 minutes. The method is simple, theoretically grounded, and plug-and-play compatible with existing MLLMs
weaknesses: - The concept of ACF and the calculation of $r_t$ in Figure 1 require further explanation, which will help readers better understand the motivation of the paper. 

- This pre-filtering process before keyframe selection undermines the goal of identifying the most informative keyframes from all frames. The findings are interesting, but it is not certain whether the two-stage ARM selection proposed in the article will fall into the same limitations.

- Lack of experimental results on MLVU, a commonly used long video understanding benchmark.

- Minor Weaknesses
  - Line 36: multimodal LLMs (MLLMs) -> multimodal large language models (MLLMs)
  - Line 107: multimodal LLMs -> MLLMs

[1] Zhou J, Shu Y, Zhao B, et al. Mlvu: A comprehensive benchmark for multi-task long video understanding[J]. arXiv e-prints, 2024: arXiv: 2406.04264.


Decision: Accept (Poster)