Paper deep dive
Coverage-Driven Adaptive Keyframe Selection for Video Understanding
Junyang Zhang, Puhan Luo, Chen Tang, Yuxi Shi, Xiang-Yang Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/4/2026, 4:54:36 AM
Summary
The paper introduces CSES, a training-free adaptive keyframe selection method for long-video understanding using Large Vision-Language Models (LVLMs). CSES addresses computational overhead by adaptively determining the number of frames to score and select based on frame-query relevance and redundancy. It utilizes a 'log peak prominence' metric to estimate relevance concentration, guiding an active acquisition strategy and a submodular coverage-based selection process that accounts for semantic, temporal, and visual redundancy. Experiments demonstrate that CSES reduces scoring by 4-13x and selects fewer keyframes while maintaining accuracy.
Entities (7)
Relation Signals (6)
CSES → formulatesas → coverage problem
confidence 93% · It then formulates keyframe selection as a coverage problem that jointly accounts for semantic relevance, temporal redundancy, and visual redundancy.
CSES → uses → log peak prominence
confidence 92% · CSES estimates the prominence of the frame-query relevance profile... We therefore define log peak prominence to quantify the concentration of each relevance profile.
CSES → evaluatedon → LongVideoBench
confidence 90% · Experiments with four LVLMs on two benchmarks show that our method preserves accuracy... We randomly sample 256 video–query pairs from LongVideoBench...
CSES → reduces → computational overhead
confidence 90% · processing the large number of frames in a video incurs substantial computational overhead... CSES... reduces LVLM inference costs
CSES → outperforms → AKS
confidence 85% · CSES further achieves a 3.1-5.4x speedup in frame selection over baselines... scoring 4-13x fewer frames... than existing baselines.
CSES → outperforms → Focus
confidence 85% · CSES further achieves a 3.1-5.4x speedup in frame selection over baselines... scoring 4-13x fewer frames... than existing baselines.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Recent advances in large vision-language models (LVLMs) have enabled long-video understanding and analysis. However, processing the large number of frames in a video incurs substantial computational overhead. Existing methods reduce LVLM inference costs by scoring frame-query relevance before inference and selecting keyframes accordingly. Nevertheless, the distribution of relevant frames varies across queries, and these methods often need to score hundreds or thousands of frames. To address this limitation, we propose CSES, a training-free semantic keyframe selector that adaptively determines the numbers of frames to score and keyframes to select. CSES estimates the prominence of the frame-query relevance profile to guide active acquisition and adapt the temporal coverage of each input. It then formulates keyframe selection as a coverage problem that jointly accounts for semantic relevance, temporal redundancy, and visual redundancy. Active acquisition and keyframe selection terminate based on coverage saturation. The selection objective is monotone and submodular, enabling greedy optimization with a standard approximation guarantee. Experiments with four LVLMs on two benchmarks show that our method preserves accuracy while scoring $4$-$13\times$ fewer frames and selecting $18.4\%$-$20.5\%$ fewer input keyframes than existing baselines. CSES further achieves a $3.1$-$5.4\times$ speedup in frame selection over baselines.
Tags
Links
- Source: https://arxiv.org/abs/2608.00714v1
- Canonical: https://arxiv.org/abs/2608.00714v1
Trouble viewing inline? Open PDF directly →
Full Text
57,335 characters extracted from source content.
Expand or collapse full text
Coverage-Driven Adaptive Keyframe Selection for Video Understanding Junyang Zhang, Puhan Luo, Chen Tang, Yuxi Shi, Xiang-Yang Li Abstract Recent advances in large vision-language models (LVLMs) have enabled long-video understanding and analysis. However, processing the large number of frames in a video incurs substantial computational overhead. Existing methods reduce LVLM inference costs by scoring frame–query relevance before inference and selecting keyframes accordingly. Nevertheless, the distribution of relevant frames varies across queries, and these methods often need to score hundreds or thousands of frames. To address this limitation, we propose CSES, a training-free semantic keyframe selector that adaptively determines the numbers of frames to score and keyframes to select. CSES estimates the prominence of the frame–query relevance profile to guide active acquisition and adapt the temporal coverage of each input. It then formulates keyframe selection as a coverage problem that jointly accounts for semantic relevance, temporal redundancy, and visual redundancy. Active acquisition and keyframe selection terminate based on coverage saturation. The selection objective is monotone and submodular, enabling greedy optimization with a standard approximation guarantee. Experiments with four LVLMs on two benchmarks show that our method preserves accuracy while scoring 44–13×13× fewer frames and selecting 18.4%18.4\%–20.5%20.5\% fewer input keyframes than existing baselines. CSES further achieves a 3.13.1–5.4×5.4× speedup in frame selection over baselines. 1 Introduction Large vision–language models (LVLMs) have enabled the understanding of videos lasting tens of minutes or longer, supporting question answering and reasoning about events, objects, and temporal relationships (Chandrasegaran et al. 2024; Song et al. 2024). This capability allows models to combine information from distant parts of a video. However, such videos may contain thousands of frames. Encoding all frames generates a large number of visual tokens, consumes substantial context-window capacity, and increases LVLM inference costs. In addition, irrelevant frames may distract the model from the evidence required to answer a query. Query-aware keyframe selection addresses this issue by reducing the visual input without modifying the LVLM. A pretrained image–text model first scores each candidate frame for its relevance to the query, after which a selector forwards a selected subset to the frozen LVLM. Training-free methods such as Adaptive Keyframe Sampling (AKS) (Tang et al. 2025) and FOCUS (Zhu et al. 2026) adaptively determine the temporal locations at which frames are scored or selected under fixed budgets. However, scoring hundreds or thousands of candidate frames can itself become a bottleneck. On the same hardware, FOCUS frame selection takes 24.4 seconds per LongVideoBench instance, versus 7.6 seconds for Qwen2-VL-7B inference on its 32 selected frames. An effective keyframe selection method should therefore adaptively determine the number of frames to score and the number of keyframes to select based on the evidence requirements of each video–query pair. The selection criterion should jointly account for query relevance and inter-frame redundancy to preserve relevant evidence while reducing redundant frames. Jointly adapting these two frame counts is challenging because evidence distributions vary across video–query pairs and must be inferred from sparse observations. Sampling densely around observed relevant frames may miss evidence needed for global queries, whereas uniform scoring may overlook short relevant segments and waste computation on irrelevant frames. Moreover, relevance scores are unavailable for unscored frames. The selector must therefore infer which frames are worth scoring and adaptively construct a relevant, nonredundant input for the LVLM. In this paper, we formulate keyframe selection as a relevance-weighted coverage problem that jointly considers temporal and visual redundancy. Redundant frames can be covered by representative frames, while relevance weighting favors frames related to the query. We observe that queries requiring localized evidence often yield concentrated relevance peaks, whereas those requiring global evidence produce more diffuse relevance distributions. We therefore introduce peak prominence to quantify relevance concentration and adapt the inter-frame temporal coverage range. A smaller range enables denser selection within highly relevant regions, whereas a larger range promotes broader temporal coverage. We further propose a coverage-driven active acquisition strategy to allocate the scoring budget efficiently. Coarse uniform sampling provides initial relevance observations and estimates relevance concentration. The method then prioritizes unscored frames near high-relevance or insufficiently covered regions based on their expected marginal coverage gains. This prevents scoring operations from being repeatedly concentrated within a small number of temporal segments. Both active acquisition and final keyframe selection are driven by the coverage principle and terminate based on coverage saturation, allowing the numbers of scored frames and selected keyframes to adapt to each video–query pair. Our contributions are as follows: • We analyze cross-query variations in frame–query relevance profiles and introduce peak prominence, a measure of relevance concentration that guides adaptive frame selection across video–query pairs. • We propose CSES, a training-free selector that uses peak prominence to guide active acquisition and relevance-weighted visual–temporal submodular coverage, thereby adapting both frame counts. • Across four LVLMs and two benchmarks, CSES attains comparable observed accuracy while the baselines score 4.14.1–13.0×13.0× as many frames and CSES selects 18.4%18.4\%–20.5%20.5\% fewer input keyframes. 2 Related Work Query-Aware Keyframe Selection. Many training-free query-aware selectors use CLIP or BLIP to score frame–query relevance and retain a compact input subset (Radford et al. 2021; Li et al. 2022). AKS recursively partitions the timeline to balance relevance and temporal coverage, whereas FOCUS distributes a prescribed scoring budget across temporal arms (Tang et al. 2025; Zhu et al. 2026). Q-Frame jointly allocates frames and resolution, Logic-in-Frames uses semantic-logical verification, and MDP3 models relevance, diversity, and temporal order under a fixed output budget (Zhang et al. 2025b; Guo et al. 2025; Sun et al. 2025). Learned selectors use pseudo-labels, downstream feedback, or rewards (Yu et al. 2023, 2025; Hu et al. 2025; Qin et al. 2026). Flexible Frame Selector can also predict a variable output size (Buch et al. 2025). Recent training-free methods adapt sampling to query type or temporal structure (Li et al. 2026; Zhang et al. 2026; Chen et al. 2026), while others use query-, content-, or model-derived signals for test-time selection (Peng et al. 2026; Eltahir et al. 2026; Wang et al. 2026). Agent-based systems retrieve evidence over multiple rounds and operate under a different computational setting (Wang et al. 2024b; Chu et al. 2025; Liu et al. 2026). Among pre-inference selectors, joint per-instance control of the realized frame-scoring count and LVLM input size remains underexplored. Coverage-Based Selection. Coverage objectives support representative, nonredundant subset selection. Submodular formulations are used in document and video summarization and admit standard greedy guarantees under cardinality constraints (Lin and Bilmes 2011; Gygli et al. 2015; Nemhauser et al. 1978). Classical formulations assume that candidate utilities are available before selection, whereas scorer-based query-aware methods must first decide which frames to score. CSES applies marginal coverage to acquisition under partial observation and final selection over scored frames, while keeping the objectives distinct. Coverage saturation adaptively stops both stages within their respective upper bounds. 3 Observation To enable adaptation across different video–query pairs, we first analyze variations in relevance distributions, then define a metric to characterize these variations. Figure 1: Representative frame–query relevance profiles. Relevance distributions vary across video–query pairs. Figure 1 shows BLIP relevance profiles computed from 128 uniformly sampled frames. Panels (a), (c), and (d) present examples from LongVideoBench. Figure 1(b) uses the same video as (a), but with a query requiring a global description. Queries requiring localized evidence tend to produce one or several prominent peaks, whereas queries requiring video-wide or multi-moment evidence produce more diffuse relevance profiles. These observations indicate that the relevance distribution is jointly determined by the video content and the query, motivating an instance-adaptive selection strategy. We therefore define log peak prominence to quantify the concentration of each relevance profile. Figure 2: Log peak prominence across question types. Figure 3: Stability across uniform probe sizes. Log peak prominence. The maximum relevance score alone does not reveal whether the peak is prominent relative to background variation. For a relevance profile r=(r1,…,rn)r=(r_1,…,r_n), we define peak prominence as P=max(r)−median(r)MAD(r)+δ,P= (r)-median(r)MAD(r)+δ, (1) where MAD(r)=median(|r−median(r)|)MAD(r)=median(|r-median(r)|) is the median absolute deviation and δ=10−6δ=10^-6 is a small constant to prevent division by zero. To compress the wide dynamic range of P, we use logP=log10(max(P,10−6)) P= _10( (P,10^-6)), referred to as log peak prominence. A high logP P indicates that the maximum relevance score stands out clearly from background variation, suggesting that query-relevant evidence is concentrated within localized temporal segments. Effectiveness and stability. We randomly sample 256 video–query pairs from LongVideoBench, covering seven categories in its official taxonomy: Scene-referred Object Tracking (SOS), Scene-referred Object Existence (S2O), Scene-referred Object Attribute (S2A), Object-referred Event (O2E), Event-referred Object (E2O), Scene-referred Object Attribute Change (SAA), and Sequence of Scenes (S). For analysis, we further group these categories according to their temporal information requirements implied by their task definitions. The first five typically target temporally localized visual information and form the localized-reference group. By contrast, SAA and S explicitly require comparison or ordering across multiple moments and form the global-reference group. For each video–query pair, we compute logP P from the relevance scores of 128 uniformly sampled frames. As shown in Figure 2, logP P is generally higher for the localized-reference group than for the global-reference group, indicating that it captures differences in relevance concentration across instances. Based on this observation, we use τ=2τ=2 as an empirical reference value to distinguish relatively concentrated from relatively diffuse relevance profiles. To evaluate stability, we recompute logP P for the same instances using 64, 128, and 256 uniformly sampled frames. Figure 3 shows that the between-group separation remains broadly consistent across probe sizes. This empirical stability is consistent with the non-additive construction of logP P. Thus, logP P provides an instance-level signal of relevance concentration, and serves as the basis for adapting the temporal extent of frame coverage in the subsequent method. 4 Method Design 4.1 Method Overview CSES (Coverage-driven Submodular kEyframe Selection) formulates final keyframe selection using a submodular visual–temporal coverage objective weighted by semantic relevance. It extends the same coverage principle to active acquisition, thereby adapting both the frame-scoring count and the LVLM input size to each video–query pair. As shown in Figure 4, CSES proceeds in three stages. First, a coarse probe scores a small set of uniformly sampled frames to estimate relevance concentration. Next, coverage-driven active acquisition prioritizes unscored temporal locations for additional scoring according to their estimated coverage value. Finally, the method uses the relevance scores and visual features of all scored frames to select the keyframe set. The latter two stages assess candidate value through marginal coverage and terminate based on coverage saturation. We next formalize the coverage objective underlying CSES before presenting the complete three-stage procedure. Figure 4: Overview of the three-stage CSES framework. 4.2 Relevance-Weighted Visual–Temporal Coverage We formulate final keyframe selection as a coverage problem: once relevant content has been represented, additional frames that are visually similar to and temporally close to the selected frames offer little marginal gain. Let O be the set of scored frames and S the set of selected keyframes. For each i∈i with timestamp tit_i, a frame scorer returns a frame–query relevance score ri∈[0,1]r_i∈[0,1] and an ℓ2 _2-normalized, query-independent visual feature eie_i in one forward pass. The visual feature is obtained from the same image encoding used for relevance scoring and therefore requires no additional image-encoder pass. We define visual and temporal affinities between a scored frame i and a selected frame j, and combine them into a joint coverage kernel ijK_ij: Φij=max(⟨ei,ej⟩,0),Aij=exp(−(ti−tj)22ℓ2), _ij= ( e_i,e_j ,0),\;\;A_ij= \! (- (t_i-t_j)^22 ^2 ), (2) ij=ΦijAij,ii=1, _ij= _ijA_ij,\;\;\;\;K_i=1, (3) where Φij _ij denotes the clipped cosine similarity and captures visual redundancy, whereas AijA_ij is a Gaussian temporal kernel and captures temporal redundancy. The parameter ℓ>0 >0 denotes the temporal bandwidth of AijA_ij, measured in seconds. Both terms are nonnegative, and ij∈[0,1]K_ij∈[0,1] takes a large value only when the two frames are both visually similar and temporally close. Consequently, visually similar but temporally distant frames and temporally adjacent but visually dissimilar frames are not treated as interchangeable. The temporal bandwidth ℓ determines the temporal range over which one frame can cover another and should adapt to the estimated evidence concentration of each video–query pair. A smaller bandwidth preserves fine-grained temporal distinctions around localized evidence, whereas a larger bandwidth suppresses redundant local selection and promotes broader temporal coverage. We therefore map the log peak prominence introduced above to a concentration coefficient u and then to ℓ : u=clip(logP/τ,0,1),ℓ=1+(1−u)(ℓmax−1),u=clip\! ( P/τ,0,1 ),\;\; =1+(1-u)( _ -1), (4) where ℓmax _ is the maximum temporal bandwidth, and τ=2τ=2 is the empirical reference value identified in Section 3. Clipping logP/τ P/τ to u∈[0,1]u∈[0,1] limits the influence of extreme values and keeps ℓ∈[1,ℓmax] ∈[1, _ ] seconds. A larger u indicates more concentrated relevant evidence and narrows the temporal kernel, enabling denser selection within localized high-relevance regions. Conversely, a smaller u widens the kernel, discouraging repeated local selection and promoting broader temporal coverage. The joint kernel captures inter-frame representativeness, but not whether the represented content is useful for the query. We therefore define the relevance-weighted coverage objective: F()=∑i∈(ri+κ)maxj∈ij,maxj∈∅ij:=0,F(S)= _i (r_i+κ) _j K_ij, _j∈ K_ij:=0, (5) where κ>0κ>0 is a small constant that ensures the objective is equivalent to unweighted coverage when relevance scores are zero. For each frame i, maxj∈ij _j K_ij is its coverage by S, weighted by relevance. The marginal gain therefore favors candidates that represent high-relevance content not yet covered, while visual and temporal redundancy discount repeated selection. Thus, F combines relevance and both forms of redundancy through marginal coverage. As a nonnegative weighted maximum-coverage function, F can be shown to be normalized, monotone, and submodular. Therefore, the standard greedy algorithm achieves a (1−1/e)(1-1/e) approximation guarantee (Nemhauser et al. 1978). CSES follows this greedy approach, and uses coverage saturation to control the stopping condition. Let KmaxK_ denote the maximum number of selected keyframes, and let ϵ∈(0,1)ε∈(0,1) be the saturation tolerance. Starting with =∅S= , the selector repeatedly adds the frame with the largest marginal gain in F. Since ii=1K_i=1, the maximum attainable coverage is F()=∑i∈(ri+κ)F(O)= _i (r_i+κ). The selector terminates when F()≥(1−ϵ)F()F(S)≥(1-ε)F(O) or ||=Kmax|S|=K_ . This rule adapts the number of selected keyframes to each video–query pair. Localized evidence may reach coverage saturation with a small representative set, whereas evidence distributed throughout the video may require more keyframes, subject to the upper bound KmaxK_ . The appendix provides the submodularity proof and detailed selection pseudocode. 4.3 Three-Stage Keyframe Selection The coverage objective requires the relevance score and visual feature of each candidate frame, but these quantities are unknown before scoring. CSES must therefore decide which frames to score. Let RmaxR_ and KmaxK_ cap the sizes of O and S, respectively. Sparse uniform scoring may miss relevant evidence, whereas dense scoring may negate the intended efficiency gains. As shown in Algorithm 1, the resulting pipeline comprises three stages: initial probing to obtain sparse observations, active acquisition to allocate the scoring budget, and final keyframe selection using relevance-weighted visual–temporal coverage. Stage 1: Coarse Probe. CSES uniformly samples n1n_1 frames to form the initial scored set O and obtain the relevance scores and visual features (ri,ei)i∈\(r_i,e_i)\_i . The method then computes logP P using Equation (1) and obtains the concentration coefficient u and temporal bandwidth ℓ from Equation (4). With a small number of scoring operations, the coarse probe provides the adaptive parameters and initial coverage information required for subsequent active acquisition and final keyframe selection. Input: Budgets KmaxK_ and RmaxR_ ; grid size G; probe size n1n_1; bandwidth limit ℓmax _ ; saturation threshold ϵε Output: Keyframe set S 1 Stage 1: Coarse Probe; 2 Uniformly sample and score n1n_1 frames, obtaining O, r(n1)r^(n_1), and ri,eii∈\r_i,e_i\_i ; 3 Compute logP P using Eq. (1), and obtain u, ℓ from Eq. (4); 4 Stage 2: Active Acquisition; 5 Construct G from G uniformly spaced unscored frames; compute A using Eq. (2); 6 Compute r^(c) r(c), vis(c)vis(c), and initial covv(c)cov_v(c) using Eqs. (6) and (7); set ←∅P← ; 7 while ||+||<Rmax|O|+|P|<R_ and ∖≠∅G ≠ do 8 σ(c)←(1−covv(c))vis(c)σ(c)←(1-cov_v(c))vis(c); set W(c)W(c) using Eq. (8); 9 if ∑c∈W(c)covv(c)≥(1−ϵ)∑c∈W(c) _c W(c)cov_v(c)≥(1-ε) _c W(c) then 10 break; 11 12 end if Δ(x)←∑c∈W(c)[Axc−covv(c)]+ (x)← _c W(c)[A_xc-cov_v(c)]_+ ; // define [⋅]+=max(⋅,0)[\,·\,]_+= (\,·\,,0) 13 x⋆←argmaxx∈∖Δ(x)x ← _x (x); 14 if Δ(x⋆)≤0 (x )≤ 0 then 15 break; 16 17 end if 18 ←∪x⋆P ∪\x \; covv(c)←max(covv(c),Ax⋆c)cov_v(c)← (cov_v(c),A_x c) for c∈c ; 19 20 end while 21Score the planned frames in P with batched inference; ←∪O ; 22 Stage 3: Coverage Selection; 23 Compute the recalibrated logP† P using Eq. (9); 24 Obtain ℓ† from Eq. (4); 25 Apply CoverageSelection with ℓ† to obtain S; 26 return sort()sort(S); Algorithm 1 CSES: three-stage adaptive selection. Stage 2: Active Acquisition. Stage 2 allocates the remaining scoring budget under partial observation. Because relevance scores and visual features are unavailable at unscored frames, the joint coverage objective cannot yet be evaluated. Instead, CSES estimates the potential value of unscored candidates from the coarse-probe observations and selects frames based on estimated temporal coverage. Moreover, CSES adaptively balances exploitation and exploration according to the concentration of the coarse-probe relevance profile. We select a set G of G uniformly spaced, unscored candidate frames along the video timeline. For each c∈c , let tct_c denote its timestamp. Using the bandwidth ℓ obtained in Stage 1, all temporal affinities A can be computed from timestamps without frame scoring. We first construct the exploitation signal to prioritize regions surrounding observed high-relevance frames. Temporal kernel regression then estimates the relevance of each candidate from the scored frames as the exploitation signal: r^(c)=∑j∈Acjrj∑j∈Acj. r(c)= _j A_cjr_j _j A_cj. (6) We next construct the exploration signal. A candidate is valuable for exploration when it is poorly covered by scored frames and lies in an interval that may contain unobserved information. We capture these two factors by defining the exploration signal σ(c)σ(c): covv(c) _v(c) =maxj∈Acj, = _j A_cj, (7) vis(c) (c) =1−max(⟨ejL(c),ejR(c)⟩,0), =1- ( e_j_L(c),e_j_R(c) ,0 ), σ(c) σ(c) =(1−covv(c))vis(c), =(1-cov_v(c))vis(c), where jL(c)j_L(c) and jR(c)j_R(c) denote the probe frames with the nearest timestamps before and after tct_c. (1−covv(c))(1-cov_v(c)) measures the temporal coverage deficit at c and is large in temporal gaps poorly represented by the scored frames. vis(c)vis(c) measures the visual difference between its neighboring probes and indicates whether the intervening interval may contain unobserved information. Consequently, σ(c)σ(c) is large when c is poorly covered and its neighboring probes differ visually. We combine these two signals using a concentration coefficient to determine the potential value of candidate frames: W(c)=u(r^(c)+κ)+(1−u)σ(c).W(c)=u ( r(c)+κ )+(1-u)σ(c). (8) A higher u value implies that evidence is relatively concentrated, causing active acquisition to focus on the neighborhood of high-relevance frames; a lower u shifts emphasis toward poorly covered intervals with visual change. To avoid repeatedly scoring redundant frames within local regions, CSES selects frames for scoring according to their marginal coverage gains. Because visual features are unavailable for unscored candidates, the method uses W(c)W(c) to weight temporal coverage and greedily selects candidates according to their current weighted marginal temporal-coverage gains (Algorithm 1, lines 7–18). Frame acquisition terminates once coverage reaches the prescribed saturation threshold. The resulting acquisition set P is then scored in batches and added to the scored set O. Table 1: Frame-scoring count, LVLM input size and accuracy. CSES reduces both counts while achieving similar mean accuracy. (a) Frame-scoring count and LVLM input size Number of scored frames Number of keyframes Selector R¯ R Reduction vs. AKS Reduction vs. FOCUS ||¯ |S| Reduction vs. FOCUS LVB VMME LVB VMME LVB VMME LVB VMME LVB VMME AKS 746.6 1039.6 – – – – 32 32 – – FOCUS 323.4 449.4 ↓2.3× 2.3× ↓2.3× 2.3× – – 32 32 – – CSES (our) 79.3 79.9 ↓9.4× 9.4× ↓13.0× 13.0× ↓4.1× 4.1× ↓5.6× 5.6× 25.4 26.1 ↓20.5% 20.5\% ↓18.4% 18.4\% (b) Accuracy (%) LVB VMME Mean accuracy LVLM AKS FOCUS CSES (our) AKS FOCUS CSES (our) AKS FOCUS CSES (our) LLaVA-OneVision-7B 58.19 59.84 59.61 60.63 58.63 60.26 59.41 59.23 59.93 Qwen2-VL-7B-Instruct 57.52 59.69 58.34 60.00 59.48 60.00 58.76 59.59 59.17 LLaVA-Video-7B 59.84 60.28 60.96 64.26 62.56 62.96 62.05 61.42 61.96 Qwen3-VL-8B-Instruct 58.79 60.51 59.54 66.33 65.30 64.93 62.56 62.90 62.23 Four-model mean 58.59 60.08 59.61 62.81 61.49 62.04 60.70 60.79 60.82 Figure 5: Component ablations with Qwen2-VL-7B-Instruct and two benchmarks. Stage 3: Coverage Selection. Stage 3 applies the final coverage objective to the expanded scored set. We refer to the greedy coverage procedure described in Section 4.2 as CoverageSelection. Active acquisition may find high-relevance frames missed by the coarse probe, causing the Stage 1 estimate of logP P to underestimate relevance concentration. However, active acquisition preferentially samples regions of high predicted relevance, so the expanded scored set is biased and may distort the background median and median absolute deviation when used to recompute logP P. We therefore use Stage 2 scores only to update the peak value while retaining background statistics from the uniform Stage 1 probe. Let r()r^(O) denote relevance scores over the expanded scored set after Stage 2 and r(n1)r^(n_1) those of the n1n_1 frames scored in Stage 1. We define the recalibrated P as P†=max(r())−median(r(n1))MAD(r(n1))+δ.P = (r^(O))-median(r^(n_1))MAD(r^(n_1))+δ. (9) We then obtain logP† P from P†P using the same transformation as in Section 3. This hybrid estimate incorporates a newly discovered peak without using the biased acquisition set to estimate the background. Substituting logP† P into Equation (4) gives u†u and ℓ† . We then construct the joint kernel over O using ℓ† and apply CoverageSelection. Coverage saturation determines the realized size of S, which is returned in temporal order (Algorithm 1, lines 21–24). Inference cost. Active acquisition and coverage selection follow the coverage principle to adapt two distinct costs to each video–query pair. Active acquisition determines the number of additional frames to score subject to RmaxR_ . The resulting frame-scoring count is R=||=n1+||R=|O|=n_1+|P|. Coverage selection determines the LVLM input size, producing |||S| keyframes subject to KmaxK_ . Figure 6: Local parameter sensitivity with Qwen2-VL-7B-Instruct and two benchmarks. 5 Experiments 5.1 Experimental Setup Benchmarks and models. We use the 1,337-question validation set of LongVideoBench (LVB) (Wu et al. 2024) and 2,700 Video-MME (VMME) questions (Fu et al. 2025). The downstream LVLMs are LLaVA-OneVision-7B (Li et al. 2025), Qwen2-VL-7B-Instruct (Wang et al. 2024a), LLaVA-Video-7B (Zhang et al. 2025c), and Qwen3-VL-8B-Instruct (Bai et al. 2025). Baselines. We compare with AKS (Tang et al. 2025), which balances relevance and temporal coverage, and FOCUS (Zhu et al. 2026), which allocates samples across temporal arms. All methods are evaluated with LMMs-Eval (Zhang et al. 2025a) in the same environment. They share the BLIP-large frame scorer, Kmax=32K_ =32, the prompts, and all downstream LVLM inference settings. Metrics and configuration. We report accuracy, the mean number of scored frames R¯ R, and the mean number of keyframes forwarded to the LVLM ||¯ |S|. In our protocol, selector outputs do not depend on the downstream LVLM, so both frame counts are shared across the four models. CSES uses Kmax=32K_ =32, Rmax=128R_ =128, G=512G=512, n1=64n_1=64, ℓ∈[1,38] ∈[1,38] seconds, κ=0.005κ=0.005 and ϵ=0.05ε=0.05. Unless otherwise specified in the ablation studies, we use this configuration for all models and benchmarks. 5.2 Overall Results As shown in Table 1, CSES uses substantially fewer scored and forwarded frames, while the three selectors have similar aggregate observed accuracy. The aggregate over the eight model–benchmark combinations is 60.82% for CSES, 60.79% for FOCUS, and 60.70% for AKS, and no selector has the highest accuracy in every setting. The efficiency gains are consistent across both benchmarks. Relative to CSES, AKS scores 9.49.4–13.0×13.0× as many frames and FOCUS scores 4.14.1–5.6×5.6× as many. CSES also forwards 18.4%18.4\%–20.5%20.5\% fewer keyframes than their fixed 32-frame outputs. Thus, CSES reaches a lower-cost operating point with close aggregate observed accuracy. 5.3 Method Analysis Component ablations. Figure 5(a) reports component-wise ablations of CSES. Every variant reduces mean accuracy, indicating that each component contributes to the complete method. The largest observed decrease occurs when active acquisition is removed and only the coarse probe is retained, reducing mean accuracy by 2.28 points. To further evaluate active acquisition, we replace it with uniform scoring of up to 128 frames. As shown in Figure 5(b), active acquisition yields 0.63 points higher mean accuracy while reducing R¯ R from 114.1 to 79.6. This result indicates that active acquisition allocates the scoring budget more effectively by prioritizing candidate frames with greater estimated value for final keyframe selection. Coverage selection. As shown in Figure 5(a), fixing ℓ at 19 seconds, near the midpoint of its adaptive range, or removing either visual or temporal coverage lowers mean accuracy. These results support the contributions of bandwidth adaptation and joint visual–temporal coverage. To evaluate final selection independently of active acquisition, we apply the Stage 3 coverage selector and AKS to the same 128 uniformly scored candidate frames. Table 2 shows that our selector forwards fewer keyframes and achieves a higher mean accuracy than AKS. Compared with the 32-frame uniform input, the Stage 3 coverage selector improves mean accuracy while forwarding fewer frames on both benchmarks, showing that a smaller LVLM input does not compromise accuracy. These results support the effectiveness of the proposed coverage selection method. FOCUS is excluded because its selection is coupled to its arm-search procedure. Table 2: Comparison of final-selection methods. Selector Frames LVB VMME Mean Uniform input 32 55.05 57.70 56.38 AKS from 128 32 55.12 59.41 57.26 CSES from 128 26.3/27.6 58.04 59.04 58.54 Parameter sensitivity. Figure 6 shows limited sensitivity around the default configuration. Across the tested one-at-a-time settings, mean accuracy varies by at most 0.95 points and R¯ R ranges from 77.1 to 83.2. The saturation tolerance ϵε produces the clearest accuracy–cost trade-off, consistent with its role in stopping both coverage stages, whereas κ and ℓmax _ have smaller local effects. Table 3: Frame-selection latency on LVB (s/instance). Method Decode Preproc. Inference Selection Total CSES (our) 5.052 0.428 2.298 0.088 7.866 AKS 17.086 4.005 21.648 0.097 42.838 FOCUS 13.156 1.746 9.372 0.138 24.411 5.4 Frame-Selection Latency We measure selector-side latency from video decoding through final selection on all 1,337 LVB validation instances. Experiments use an NVIDIA RTX 3090, an Intel Core i5-13600KF, and BLIP-large with a batch size of 8. The reported inference latency of CSES includes the additional cost of ℓ2 _2-normalizing the visual features produced by BLIP. Table 3 reports mean latency per instance for decoding, BLIP preprocessing and GPU transfer, BLIP inference, and the remaining selection overhead. From Table 3, CSES achieves a 5.45×5.45× frame-selection speedup over AKS and a 3.10×3.10× speedup over FOCUS. Most of the measured reduction occurs in video decoding, BLIP preprocessing, and BLIP inference, consistent with processing fewer frames. For context, on the same hardware, Qwen2-VL-7B-Instruct inference using the 32 keyframes selected by FOCUS averages 7.618 seconds per instance, whereas FOCUS requires 24.411 seconds for frame selection. Thus, scoring many candidate frames with BLIP can make frame selection more costly than downstream LVLM inference. CSES reduces this cost to 7.866 seconds, substantially alleviating the bottleneck. 6 Conclusion We presented CSES, a training-free keyframe selector that adapts both the frame-scoring count and the LVLM input size. CSES uses log peak prominence to characterize relevance concentration. CSES uses this signal to adapt temporal coverage and guide active acquisition. Final keyframes are then selected using relevance-weighted visual–temporal submodular coverage. Across four LVLMs on LongVideoBench and Video-MME, CSES achieves comparable observed accuracy while the baselines score 4.14.1–13.0×13.0× as many frames and CSES forwards 18.4%18.4\%–20.5%20.5\% fewer keyframes. References S. Bai, Y. Cai, R. Chen, K. Chen, X. Chen, Z. Cheng, L. Deng, W. Ding, C. Gao, C. Ge, W. Ge, Z. Guo, Q. Huang, J. Huang, F. Huang, B. Hui, S. Jiang, Z. Li, M. Li, M. Li, K. Li, Z. Lin, J. Lin, X. Liu, J. Liu, C. Liu, Y. Liu, D. Liu, S. Liu, D. Lu, R. Luo, C. Lv, R. Men, L. Meng, X. Ren, X. Ren, S. Song, Y. Sun, J. Tang, J. Tu, J. Wan, P. Wang, P. Wang, Q. Wang, Y. Wang, T. Xie, Y. Xu, H. Xu, J. Xu, Z. Yang, M. Yang, J. Yang, A. Yang, B. Yu, F. Zhang, H. Zhang, X. Zhang, B. Zheng, H. Zhong, J. Zhou, F. Zhou, J. Zhou, Y. Zhu, and K. Zhu (2025) Qwen3-VL technical report. CoRR abs/2511.21631. External Links: Link, Document, 2511.21631 Cited by: §5.1. S. Buch, A. Nagrani, A. Arnab, and C. Schmid (2025) Flexible frame selection for efficient video reasoning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 29071–29082. Cited by: §2. K. Chandrasegaran, A. Gupta, L. M. Hadzic, T. Kota, J. He, C. Eyzaguirre, Z. Durante, M. Li, J. Wu, and L. Fei-Fei (2024) HourVideo: 1-hour video-language understanding. In Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, External Links: Link Cited by: §1. W. Chen, Y. Zeng, Y. Luo, T. Xie, L. Lin, J. Ji, Y. Zhang, and X. Zheng (2026) Wavelet-based frame selection by detecting semantic boundary for long video understanding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 24052–24061. External Links: Link Cited by: §2. M. Chu, Y. Li, and T. Chua (2025) GraphVideoAgent: enhancing long-form video understanding with entity relation graphs. In Proceedings of the 33rd ACM International Conference on Multimedia, p. 4639–4648. External Links: Document, Link Cited by: §2. M. Eltahir, L. Ayash, A. Habibullah, T. Hussain, and N. Khan (2026) GridProbe: posterior-probing for adaptive test-time compute in long-video VLMs. CoRR abs/2605.10762. External Links: Document, Link, 2605.10762 Cited by: §2. C. Fu, Y. Dai, Y. Luo, L. Li, S. Ren, R. Zhang, Z. Wang, C. Zhou, Y. Shen, M. Zhang, P. Chen, Y. Li, S. Lin, S. Zhao, K. Li, T. Xu, X. Zheng, E. Chen, C. Shan, R. He, and X. Sun (2025) Video-MME: the first-ever comprehensive evaluation benchmark of multi-modal LLMs in video analysis. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 24108–24118. Cited by: §5.1. W. Guo, Z. Chen, S. Wang, J. He, Y. Xu, J. Ye, Y. Sun, and H. Xiong (2025) Logic-in-frames: dynamic keyframe search via visual semantic-logical verification for long video understanding. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2025, NeurIPS 2025, External Links: Link Cited by: §2. M. Gygli, H. Grabner, and L. Van Gool (2015) Video summarization by learning submodular mixtures of objectives. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 3090–3098. Cited by: §2. K. Hu, F. Gao, X. Nie, P. Zhou, S. Tran, T. Neiman, L. Wang, M. Shah, R. Hamid, B. Yin, and T. Chilimbi (2025) M-LLM based video frame selection for efficient video understanding. In Proceedings of the Computer Vision and Pattern Recognition Conference, p. 13702–13712. Cited by: §2. B. Li, Y. Zhang, D. Guo, R. Zhang, F. Li, H. Zhang, K. Zhang, P. Zhang, Y. Li, Z. Liu, and C. Li (2025) LLaVA-OneVision: easy visual task transfer. Trans. Mach. Learn. Res.. External Links: Link Cited by: §5.1. J. Li, B. Li, J. Li, and Y. Lu (2026) Divide, then ground: adapting frame selection to query types for long-form video understanding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 11369–11380. External Links: Link Cited by: §2. J. Li, D. Li, C. Xiong, and S. Hoi (2022) BLIP: bootstrapping language-image pre-training for unified vision-language understanding and generation. In International conference on machine learning, p. 12888–12900. Cited by: §2. H. Lin and J. Bilmes (2011) A class of submodular functions for document summarization. In Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies, p. 510–520. Cited by: §2. R. Liu, Z. Liu, J. Tang, Y. Ma, R. Pi, J. Zhang, and Q. Chen (2026) LongVideoAgent: multi-agent reasoning with long videos. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), San Diego, California, United States, p. 40404–40416. External Links: Document, Link Cited by: §2. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher (1978) An analysis of approximations for maximizing submodular set functions – I. Math. Program. 14 (1), p. 265–294. External Links: Link, Document Cited by: §2, §4.2. J. Peng, B. Song, J. Li, H. Li, Y. Zhou, R. Ji, and Y. Tian (2026) QCA: query- and content-aware keyframe selection for long video understanding. CoRR abs/2607.00983. External Links: Document, Link, 2607.00983 Cited by: §2. Y. Qin, H. Li, W. Mu, and Y. He (2026) Efficient frame selection for long video understanding via reinforcement learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 16944–16953. Cited by: §2. A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, G. Krueger, and I. Sutskever (2021) Learning transferable visual models from natural language supervision. In International conference on machine learning, p. 8748–8763. Cited by: §2. E. Song, W. Chai, G. Wang, Y. Zhang, H. Zhou, F. Wu, H. Chi, X. Guo, T. Ye, Y. Zhang, Y. Lu, J. Hwang, and G. Wang (2024) MovieChat: from dense token to sparse memory for long video understanding. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2024, p. 18221–18232. External Links: Link, Document Cited by: §1. H. Sun, S. Lu, H. Wang, Q. Chen, Z. Xu, W. Luo, K. Zhang, and M. Li (2025) MDP3: a training-free approach for list-wise frame selection in Video-LLMs. In IEEE/CVF International Conference on Computer Vision, ICCV 2025, p. 24090–24101. External Links: Link, Document Cited by: §2. X. Tang, J. Qiu, L. Xie, Y. Tian, J. Jiao, and Q. Ye (2025) Adaptive keyframe sampling for long video understanding. In Proceedings of the Computer Vision and Pattern Recognition Conference, p. 29118–29128. Cited by: §1, §2, §5.1. P. Wang, S. Bai, S. Tan, S. Wang, Z. Fan, J. Bai, K. Chen, X. Liu, J. Wang, W. Ge, Y. Fan, K. Dang, M. Du, X. Ren, R. Men, D. Liu, C. Zhou, J. Zhou, and J. Lin (2024a) Qwen2-VL: enhancing vision-language model’s perception of the world at any resolution. CoRR abs/2409.12191. External Links: Link, Document, 2409.12191 Cited by: §5.1. X. Wang, Y. Zhang, O. Zohar, and S. Yeung-Levy (2024b) VideoAgent: long-form video understanding with large language model as agent. In European Conference on Computer Vision, p. 58–76. Cited by: §2. Y. Wang, X. Zheng, D. Mao, L. Li, Z. Yang, P. Yu, R. Yan, Y. Yao, and A. J. Wang (2026) Efficient frame selection for long videos at test time with attention-based MLLM selectors. CoRR abs/2607.15689. External Links: Document, Link, 2607.15689 Cited by: §2. H. Wu, D. Li, B. Chen, and J. Li (2024) LongVideoBench: a benchmark for long-context interleaved video-language understanding. Advances in Neural Information Processing Systems 37, p. 28828–28857. External Links: Document, Link Cited by: §5.1. S. Yu, J. Cho, P. Yadav, and M. Bansal (2023) Self-chained image-language model for video localization and question answering. Advances in Neural Information Processing Systems 36, p. 76749–76771. Cited by: §2. S. Yu, C. Jin, H. Wang, Z. Chen, S. Jin, Z. Zuo, X. Xu, Z. Sun, B. Zhang, J. Wu, H. Zhang, and Q. Sun (2025) Frame-Voyager: learning to query frames for video large language models. In The Thirteenth International Conference on Learning Representations, ICLR 2025, External Links: Link Cited by: §2. K. Zhang, B. Li, P. Zhang, F. Pu, J. A. Cahyono, K. Hu, S. Liu, Y. Zhang, J. Yang, C. Li, and Z. Liu (2025a) LMMs-Eval: reality check on the evaluation of large multimodal models. In Findings of the Association for Computational Linguistics: NAACL 2025, Albuquerque, New Mexico, p. 881–916. External Links: Link, Document Cited by: §5.1. K. Zhang, C. Fang, T. Chen, B. Song, Y. Shen, Y. Zhou, and R. Ji (2026) Towards fast and effective long video understanding of multimodal large language models via adaptive quasi-gaussian sampling. CoRR abs/2606.24187. External Links: Document, Link, 2606.24187 Cited by: §2. S. Zhang, J. Yang, J. Yin, Z. Luo, and J. Luan (2025b) Q-frame: query-aware frame selection and multi-resolution adaptation for Video-LLMs. In Proceedings of the IEEE/CVF International Conference on Computer Vision, p. 22056–22065. Cited by: §2. Y. Zhang, J. Wu, W. Li, B. Li, Z. Ma, Z. Liu, and C. Li (2025c) LLaVA-Video: video instruction tuning with synthetic data. Trans. Mach. Learn. Res.. External Links: Link Cited by: §5.1. Z. Zhu, H. Xu, Y. Luo, Y. Liu, K. Sarkar, Z. Yang, and Y. You (2026) FOCUS: efficient keyframe selection for long video understanding. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §1, §2, §5.1. Appendix A Additional Details for the Observation The four profiles in Figure 1 are computed from 128 uniformly sampled frames. Panels (a), (c), and (d) correspond to LongVideoBench samples. Panel (b) uses the same video as panel (a) with an author-constructed video-description query, providing a controlled comparison of different information needs for the same video. The queries and corresponding log peak prominence values are listed below. (a) Object-referred Event, logP=5.22 P=5.22. Query: On a stage with lights, there are many people wearing colorful outfits. What are these people in the colorful outfits doing? (b) Video Description, logP=1.20 P=1.20. Query: What does this video cover? (c) Scene-referred Object Tracking, logP=5.05 P=5.05. Query: In an indoor basketball court with red walls and a yellow floor, there is a girl wearing a purple short-sleeve shirt with her hair tied up, holding a basketball. In which of the following places has the girl appeared? (d) Sequence of Scenes, logP=0.69 P=0.69. Query: Which of the following sequence of scenes is correct? Panels (a) and (c), which require temporally localized evidence, have substantially higher log peak prominence than panels (b) and (d), which require video-wide or multi-moment information. The controlled comparison between panels (a) and (b) further shows that the relevance profile depends jointly on the video and the query. Table 4: Frame-selection latency on LongVideoBench, grouped by video duration. Video duration Method Video decoding (s) BLIP preprocessing (s) BLIP inference (s) Selection overhead (s) Total (s) 0–5 min CSES 1.669 0.206 1.096 0.033 3.003 AKS 1.945 0.456 2.440 0.030 4.870 FOCUS 2.293 0.302 1.592 0.029 4.217 5–10 min CSES 6.903 0.541 2.902 0.105 10.452 AKS 11.517 2.586 13.802 0.106 28.012 FOCUS 8.719 1.132 5.989 0.094 15.934 10–20 min CSES 7.050 0.550 2.946 0.101 10.646 AKS 25.277 5.635 30.306 0.119 61.337 FOCUS 18.558 2.394 12.809 0.178 33.939 20–30 min CSES 7.216 0.574 3.116 0.127 11.033 AKS 33.367 7.645 41.757 0.153 82.922 FOCUS 24.633 3.228 17.553 0.288 45.701 30–60 min CSES 7.242 0.617 3.296 0.200 11.354 AKS 53.663 13.926 75.530 0.243 143.361 FOCUS 42.100 5.915 31.836 0.405 80.256 Appendix B Frame-Selection Latency Table 4 reports average per-instance latency for all 1,337 LongVideoBench validation instances, grouped by video duration into 498, 273, 290, 168, and 108 instances. All methods use BLIP-large on one NVIDIA GeForce RTX 3090 with a batch size of 8. The additional ℓ2 _2 normalization of visual features required by CSES is included in the reported latency. One-time model loading and warm-up are excluded. The table separates video decoding, BLIP preprocessing, BLIP inference, and residual frame-selection operations, including video metadata retrieval, BLIP output post-processing, and method-specific selection overhead. Beyond five minutes, the total latency of CSES remains between 10.452 and 11.354 seconds, whereas AKS and FOCUS reach 143.361 and 80.256 seconds for videos of 30–60 minutes. Because residual selection time is small for all methods, the advantage mainly comes from decoding and scoring fewer frames with BLIP as video duration increases. Appendix C Additional Experimental Details Complete configuration. The default configuration is Kmax=32K_ =32, Kmin=8K_ =8, Rmax=128R_ =128, G=512G=512, n1=64n_1=64, ℓ∈[1,38] ∈[1,38] seconds, κ=0.005κ=0.005, ϵ=0.05ε=0.05, τ=2τ=2, and δ=10−6δ=10^-6. Here, KminK_ specifies the minimum number of keyframes before the final coverage-saturation test is enabled; it does not change the greedy order. The same configuration and random seed 42 are used for both benchmarks and all downstream models. Each ablation changes one component at a time. Frame scoring and batching. The BLIP-large frame scorer reuses one image encoding to obtain the frame–query relevance score and the query-independent visual feature. The feature is ℓ2 _2-normalized before coverage computation. The coarse probe and the actively acquired frames are processed in two separate batched scoring phases. Active-acquisition planning invokes no frame scorer. Accordingly, R counts distinct scored frames rather than the number of minibatch forward passes. C.1 Parameter Sensitivity Table 5 provides the exact values shown in Figure 6. Each result uses Qwen2-VL-7B-Instruct and is averaged over LVB and VMME. Only the listed parameter is changed from the default configuration. Across these one-at-a-time sweeps, mean accuracy varies by at most 0.95 points, R¯ R ranges from 77.1 to 83.2, and ||¯ |S| ranges from 24.2 to 27.5. Increasing ϵε enables earlier saturation stopping and therefore reduces both frame counts. The effects of κ and ℓmax _ are smaller within the tested ranges. Table 5: Parameter sensitivity results. Asterisks mark the default values. Parameter Value Mean R¯ R ||¯ |S| ϵε 0.030.03 58.76 83.2 27.5 0.05∗0.05 59.17 79.6 25.8 0.070.07 58.22 77.1 24.2 κ 0.0010.001 58.76 77.6 24.6 0.005∗0.005 59.17 79.6 25.8 0.010.01 59.00 80.0 26.2 ℓmax _ 3434 58.70 81.0 25.9 38∗38 59.17 79.6 25.8 4242 58.74 78.5 25.6 C.2 Detailed Component Ablations Table 6 reports the exact Qwen2-VL-7B-Instruct results underlying Figure 5. Mean, R¯ R, and ||¯ |S| are unweighted averages over LVB and VMME, and Δ is the change in mean accuracy relative to full CSES. Table 6: Detailed component ablations. Variant LVB VMME Mean Δ R¯ R ||¯ |S| Full CSES 58.34 60.00 59.17 – 79.6 25.8 Remove exploration σ 58.19 59.67 58.93 −0.24-0.24 78.3 25.8 Uniform 128 instead of acquisition 58.04 59.04 58.54 −0.63-0.63 114.1 26.9 Remove predicted relevance r r 57.07 59.33 58.20 −0.97-0.97 83.4 25.9 Remove temporal coverage A 56.99 58.78 57.88 −1.29-1.29 79.6 16.2 Fix bandwidth ℓ=19 =19 s 55.65 59.52 57.58 −1.59-1.59 67.9 23.5 Remove visual coverage Φ 58.12 56.52 57.32 −1.85-1.85 79.6 22.4 Uniform 64 only (no acquisition) 54.45 59.33 56.89 −2.28-2.28 57.1 24.7 Appendix D Active-Acquisition Details Let O denote the uniformly scored probe set available at the start of Stage 2, G a set of up to G distinct uniformly spaced unscored candidates, and P the candidates planned for additional scoring. The implementation includes the temporal endpoints in O whenever n1≥2n_1≥ 2. Consequently, every candidate c∈c has scored probes with the nearest timestamp before and after tct_c, denoted by jL(c)j_L(c) and jR(c)j_R(c), respectively. For each c∈c , the relevance estimate r^(c) r(c) and visual-transition cue vis(c)vis(c) are computed from O using Equations (6) and (7). These two quantities remain fixed during batch planning. The method instead updates virtual temporal coverage as candidates are added to P: covv(c)=maxj∈∪Acj.cov_v(c)= _j A_cj. Initially, =∅P= , so coverage is determined only by scored probes. Adding a candidate to P updates coverage through its timestamp, without using its unknown relevance score or visual feature. At each planning step, the method recomputes σ(c) σ(c) =(1−covv(c))vis(c), =(1-cov_v(c))vis(c), W(c) W(c) =u(r^(c)+κ)+(1−u)σ(c). =u ( r(c)+κ )+(1-u)σ(c). For every eligible candidate x∈∖x , its weighted marginal temporal-coverage gain is Δ(x)=∑c∈W(c)[Axc−covv(c)]+. (x)= _c W(c)\,[A_xc-cov_v(c)]_+. Here, [z]+=max(z,0)[z]_+= (z,0). The maximum-gain candidate is added to P, after which coverage, σ, W, and all subsequent gains are updated. Thus, W(c)W(c) weights coverage demand over the timeline rather than serving as an independent ranking score. Planning stops at weighted coverage saturation, when the scoring budget or candidate pool is exhausted, or when no candidate provides a positive marginal gain. The planned set is then scored in one batched phase and added to O. Appendix E Submodularity of the Coverage Objective The following result concerns final coverage selection, where the scored set O, the relevance scores, and the joint kernel K are fixed. Since ri∈[0,1]r_i∈[0,1] and κ>0κ>0, the weight wi=ri+κw_i=r_i+κ is positive. Moreover, ij≥0K_ij≥ 0 by construction. Proposition 1. For any fixed O and K, the objective F()=∑i∈wimaxj∈ij,maxj∈∅ij:=0,F(S)= _i w_i _j K_ij, _j∈ K_ij:=0, is a normalized, monotone, and submodular set function defined on all subsets of O. Proof. For each i∈i , define gi()=maxj∈ij,gi(∅)=0.g_i(S)= _j K_ij, g_i( )=0. The empty-set convention gives F(∅)=0F( )=0. For any ⊆ℬ⊆A , taking a maximum over a larger set gives gi()≤gi(ℬ)g_i(A)≤ g_i(B), so gig_i is monotone. For any x∉ℬx , its marginal gain is gi(∪x)−gi() g_i(A∪\x\)-g_i(A) =[ix−gi()]+ =[K_ix-g_i(A)]_+ ≥[ix−gi(ℬ)]+ ≥[K_ix-g_i(B)]_+ =gi(ℬ∪x)−gi(ℬ), =g_i(B∪\x\)-g_i(B), where [z]+=max(z,0)[z]_+= (z,0). Thus, gig_i satisfies diminishing returns and is submodular. Finally, since F=∑i∈wigiF= _i w_ig_i and wi≥0w_i≥ 0, the marginal gain of F for any ⊆ℬ⊆A and x∉ℬx is a nonnegative weighted sum of the marginal gains of the functions gig_i: F(∪x)−F() F(A∪\x\)-F(A) =∑i∈wi[gi(∪x)−gi()] = _i w_i [g_i(A∪\x\)-g_i(A) ] ≥∑i∈wi[gi(ℬ∪x)−gi(ℬ)] ≥ _i w_i [g_i(B∪\x\)-g_i(B) ] =F(ℬ∪x)−F(ℬ)≥0. =F(B∪\x\)-F(B)≥ 0. The first inequality follows from the submodularity of each gig_i, and the final inequality follows from their monotonicity and the nonnegative weights. Therefore, F is normalized, monotone, and submodular. □ Appendix F Coverage Selection Pseudocode Algorithm 2 instantiates the relevance-weighted coverage objective in Equation (5). It maintains covi=maxs∈iscov_i= _s K_is, with covi=0cov_i=0 for =∅S= . Hence, g(j)=∑iwi[ij−covi]+g(j)= _iw_i[K_ij-cov_i]_+ is exactly the marginal gain F(∪j)−F()F(S∪\j\)-F(S). Because ij∈[0,1]K_ij∈[0,1] and ii=1K_i=1, selecting all scored frames yields the full-set reference coverage Ftot=F()=∑iwiF_tot=F(O)= _iw_i. After at least KminK_ frames have been selected, the algorithm stops when the accumulated coverage reaches (1−ϵ)Ftot(1-ε)F_tot. Otherwise, it continues until it reaches KmaxK_ , exhausts the scored set, or finds no positive marginal gain. Concentrated evidence may therefore reach saturation with a small representative set, whereas evidence distributed across the video may require more keyframes but remains bounded by KmaxK_ . Sorting the returned set by timestamp also leaves the coverage objective unchanged. Input: Scored set O with ti,ri,eii∈\t_i,r_i,e_i\_i ; bandwidth ℓ ; κ,Kmin,Kmax,ϵκ,K_ ,K_ ,ε Output: Selected keyframe set ⊆S 1 ij←max(⟨ei,ej⟩,0)exp(−(ti−tj)22ℓ2)K_ij← ( e_i,e_j ,0) \! (- (t_i-t_j)^22 ^2 ); ii←1K_i← 1; 2 wi←ri+κw_i← r_i+κ for every i∈i ; 3 Ftot←∑i∈wiF_tot← _i w_i; 4 ←∅S← ; covi←0cov_i← 0 for every i∈i ; 5 while ||<Kmax|S|<K_ do 6 if ∑iwicovi≥(1−ϵ)Ftot _iw_i\,cov_i≥(1-ε)\,F_tot and ||≥Kmin|S|≥ K_ then 7 break; 8 end if 9 g(j)←∑i∈wi[ij−covi]+g(j)← _i w_i\,[K_ij-cov_i]_+, ∀j∈∖\ ∀ j ; 10 j∗←argmaxjg(j)j ← _jg(j), break ties by minimizing maxs∈js _s K_js, thereby selecting the candidate farthest from S; 11 if g(j∗)≤0g(j )≤ 0 then break; 12 ←∪j∗S ∪\j \; covi←max(covi,ij∗),∀icov_i← (cov_i,K_ij ),\ ∀ i; 13 14 end while 15return S sorted by timestamp; Algorithm 2 Greedy relevance-weighted coverage selection.