Skip to content

VISA: Video Skeleton-Aware Efficient Frame Selection for Long Video Understanding

Conference: EMNLP 2026
Paper: https://aclanthology.org/2026.emnlp-main.1142/
Area: Video Understanding
Keywords: Frame Selection, Long Video Understanding, Multimodal Large Language Models, I-frame Anchors, Cross-GOP Refinement

TL;DR

VISA utilizes sparse native I-frames from video Group-of-Pictures (GOP) structures to build a query-agnostic temporal skeleton, aggregates hierarchical query relevance, allocates frame budgets via dynamic programming, and refines candidates across neighboring GOPs, reducing end-to-end latency by 32.9%โ€“53.6% while outperforming prior selection baselines.

Background & Motivation

Multimodal Large Language Models (MLLMs) have demonstrated substantial capabilities in short video understanding, open-ended question answering, and complex temporal instruction following. However, scaling these models to long videos lasting tens of minutes or hours encounters severe computational and architectural bottlenecks. A typical long video contains tens of thousands of frames; densely encoding all frames into visual tokens explodes memory footprint, drastically increases inference latency, and rapidly exceeds the context window capacity of modern MLLMs. Frame selection has therefore emerged as an essential preprocessing technique that aims to select a compact subset of keyframes (e.g., a budget of 32 frames) to represent the entire video before feeding visual tokens to the MLLM.

Existing frame selection approaches suffer from two fundamental deficiencies in efficiency and semantic integrity. First, in the sampling stage, current methods commonly adopt uniform frame sampling across the raw video. Because modern video codecs (such as H.264 and HEVC) compress videos into sequential Groups of Pictures (GOPs) where the vast majority of frames are inter-coded P-frames and B-frames that cannot be decoded independently, decoding uniformly sampled candidate frames requires sequentially reconstructing all preceding dependent frames back to the nearest intra-coded I-frame. This inadvertently triggers the decoding of almost the entire video stream, incurring severe I/O and CPU/GPU decoding latency. Second, in the selection stage, prevalent pipelines (such as AKS and FOCUS) score frames primarily by query relevance via cross-modal matching. This greedy ranking often clusters selected frames around repetitive, visually prominent shots (such as close-up object views) while discarding global temporal context, action continuity, and subtle transition cues, which leads the downstream language model to make hallucinated predictions due to missing contextual evidence.

Long video understanding intrinsically demands both localized query-relevant evidence and global contextual temporal coherence, and this balance must be attained without prohibitive decoding costs. Recognizing that I-frames in standard video bitstreams are independently decodable and naturally summarize key objects, background shifts, and scene boundaries, this paper builds on a key physical property of video containers. Core idea: exploit sparse, independently decodable native I-frame anchors to build a query-agnostic temporal skeleton with lightweight scene segmentation, aggregate query relevance hierarchically over the skeleton, allocate the frame budget across scenes via dynamic programming, and refine candidates across neighboring GOPs using boundary-aware scoring.

Method

Overall Architecture

VISA follows a coarse-to-fine hierarchical framework organized into three stages: Video Skeleton Construction, Skeleton-Aware Anchor Selection, and Cross-GOP Frame Refinement. In the first stage, the algorithm extracts sparse, independently decodable I-frames directly from native GOP structures as temporal anchors and groups them into query-agnostic scene segments using lightweight luma-map cosine distance, while hierarchical log-sum-exp pooling aggregates anchor-level CLIP query relevance to scene and skeleton levels. In the second stage, VISA models frame selection as a skeleton-aware allocation problem solved via dynamic programming, penalizing temporal redundancy while ensuring diminishing marginal returns across scenes. In the third stage, for each selected anchor, VISA expands a search window across adjacent GOPs and selects the optimal refined frame using a four-factor boundary-aware scoring metric that suppresses cross-scene drift and rewards local visual saliency.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}}%%
flowchart TD
    IN["Long Video V and Query Q<br/>Frame Budget B"] --> S1["Video Skeleton Construction<br/>Extract native I-frame anchors and segment scenes"]
    S1 --> S2["Query-aware Evidence Aggregation<br/>Temperature-scaled log-sum-exp pooling over skeleton"]
    S2 --> S3["Skeleton-Aware Anchor Selection<br/>Local redundancy discount and DP budget allocation"]
    S3 --> S4["Cross-GOP Frame Refinement<br/>Adjacent GOP expansion and 4-factor boundary scoring"]
    S4 --> OUT["Final Selected Frames X* (|X*| <= B)<br/>Fed into MLLM for efficient inference"]

Key Designs

1. Video Skeleton Construction: Bypassing Dense Decoding via Native I-Frames and Scene Segmentation

Standard uniform sampling incurs heavy decoding overhead because arbitrary frames are typically P- or B-frames requiring sequential reference decoding. VISA completely bypasses dense candidate decoding by extracting the native intra-coded I-frame from each Group of Pictures (GOP), producing a sparse temporal anchor set \(\mathcal{A} = \{a_1, a_2, \dots, a_M\}\). To partition anchors into coherent scenes without running heavy vision models, VISA extracts the grayscale luma map \(Y_i = 0.299R_i + 0.587G_i + 0.114B_i\) for each I-frame, resizes it to an ultra-compact \(32 \times 32\) thumbnail, and vectorizes/normalizes it to \(g_i\). The visual difference between consecutive anchors is measured by cosine distance: $\(\delta_i = 1 - g_i^\top g_{i+1}\)$ To eliminate spurious noise from minor camera shakes or localized lighting shifts, the sequence of distances is filtered by a three-point moving average, and candidate peaks are thresholded via an adaptive Otsu segmentation algorithm to establish prominent scene boundaries. This produces query-agnostic scene segments \(\mathcal{S} = \{S_1, S_2, \dots, S_K\}\) that capture the native temporal skeleton of the video with minimal CPU computation.

2. Query-aware Evidence Aggregation: Hierarchical Evidence Pooling Across the Skeleton

Relying solely on flat frame-level similarity risks picking isolated frames detached from scene context. VISA embeds the textual query \(q\) and all anchor frames using a lightweight, frozen CLIP ViT-B/32 encoder to compute raw similarities \(s_i = e_i^\top e_q\), which are calibrated via intra-video min-max normalization into anchor relevance scores \(p_i\). To quantify whether an entire scene or the overall video contains strong task-relevant clues, VISA performs bottom-up evidence aggregation using two-stage temperature-controlled log-sum-exp pooling: $\(E_k = \tau \log \left( \frac{1}{|S_k|} \sum_{i \in S_k} \exp(p_i / \tau) \right), \quad E_v = \tau \log \left( \frac{1}{K} \sum_{k=1}^K \exp(E_k / \tau) \right)\)$ where \(\tau = 0.1\). This smooth approximation of the maximum operator allows scenes with localized strong evidence to stand out without being skewed by noisy single-frame spikes, providing anchor-level relevance \(p_i\), scene-level evidence \(E_k\), and skeleton-level baseline evidence \(E_v\).

3. Skeleton-Aware Anchor Selection: Diminishing Returns and Dynamic Programming Allocation

Directly selecting the top-\(B\) anchors globally tends to collapse the budget into a single repetitive shot. VISA formulates anchor selection as an allocation problem over the structured skeleton. It defines scene surplus \(\Delta_{scene}^k = [E_k - E_v]^+\) and anchor surplus \(\Delta_i = [p_i - E_k]^+\), where \([x]^+ = \max(x, 0)\). To prevent picking visually near-duplicate anchors within a local temporal neighborhood of radius \(r=2\), it discounts anchor surplus by a local redundancy metric \(\rho_i^{(r)}\): $\(e_i^\Delta = \Delta_i \cdot \left(1 - \rho_i^{(r)}\right), \quad \rho_i^{(r)} = \frac{1}{|N_r(i)|} \sum_{j \in N_r(i)} \frac{e_i^\top e_j + 1}{2}\)$ When assigning \(m\) anchors to scene \(S_k\), the scene utility is modeled as \(U_k(m) = \Delta_{scene}^k \log(1+m) + \sum_{j=1}^m w_j e_{k,(j)}^\Delta\), where \(w_j = \log(1+j) - \log(j)\) enforces diminishing marginal returns. The global budget allocation is efficiently solved using dynamic programming: $\(dp[k, b] = \max_{0 \le t \le \min(b, |S_k|)} \left[ dp[k-1, b-t] + U_k(t) \right]\)$ Backtracking the DP state table yields an optimal anchor set \(\mathcal{A}^\star\) that balances cross-scene coverage and intra-scene distinctiveness.

4. Cross-GOP Frame Refinement: Four-Factor Boundary-Aware Saliency Scoring

While I-frame anchors indicate coarse temporal evidence locations, the exact critical action or object interaction often occurs at a nearby P/B frame or near the edge of a neighboring GOP. For each selected anchor \(a_i \in \mathcal{A}^\star\), VISA expands a local refinement window covering the preceding, current, and succeeding GOPs: \(\mathcal{W}_i = \text{GOP}(i-1) \cup \text{GOP}(i) \cup \text{GOP}(i+1)\). To prevent candidate selection from drifting across scene cuts into irrelevant visual content, VISA evaluates each candidate frame \(x \in \mathcal{W}_i\) with a comprehensive four-component score: $\(r_i(x) = u_i(x) \cdot q_i(x) \cdot b_i(x) \cdot \omega_i(x)\)$ Here, \(u_i(x) = \frac{1}{1 + \exp(-(s(x)-\mu_i)/\sigma_i)}\) is a robust standardized query similarity score using the local median \(\mu_i\) and median absolute deviation \(\sigma_i\); \(q_i(x) = \frac{e_x^\top e_{a_i} + 1}{2}\) ensures semantic consistency with the chosen anchor; \(b_i(x) = \eta_b + (1-\eta_b)\chi_i(x)\) is a scene boundary gate applying a floor penalty \(\eta_b = 0.70\) if a candidate crosses into a scene lacking evidence support; and \(\omega_i(x) = \exp(-\lambda_{dist} d_i(x) c_i(x))\) imposes an exponential temporal distance decay (\(\lambda_{dist}=0.70\)) on cross-scene frames. The candidate maximizing \(r_i(x)\) (with tie-breaking by raw similarity and temporal proximity) is collected as the final refined frame \(x_i^\star \in X^\star\).

Benchmark & Evaluation Protocol

All experiments are conducted using the lmms-eval framework on 6 NVIDIA A100 GPUs using PyTorch 2.5.1 and Transformers 4.49.0. Evaluation spans three challenging benchmarks: VideoMME (multi-domain long-video QA split into Short, Medium, and Long subsets), MLVU (multi-task understanding up to 2-hour duration), and LongVideoBench (LVB, fine-grained referring reasoning). Three representative open-source MLLMs are evaluated in zero-shot inference: Qwen2.5-VL-7B-Instruct, InternVL3-8B, and LLaVA-OneVision-Qwen2-7B-OV. Baselines include default uniform 32-frame sampling (Base) and state-of-the-art frame selection algorithms: AKS (CVPR 2025), WFS-SB (CVPR 2026), and FOCUS (ICLR 2026).

Key Experimental Results

Main Results

The table below reports answer accuracy (%) across VideoMME, MLVU, and LongVideoBench under a 32-frame visual budget across three MLLM backbones:

Backbone Model Method VideoMME Short VideoMME Medium VideoMME Long VideoMME Overall MLVU LongVideoBench Relative Gain \(\Delta\)
LLaVA-OV-7B Base (Uniform-32) 70.7 56.3 49.0 58.7 62.9 55.7 +0.0%
AKS [CVPR'25] 72.0 57.9 51.2 60.4 65.8 58.7 +4.3%
WFS-SB [CVPR'26] 73.0 63.1 50.0 62.0 67.9 55.8 +4.6%
FOCUS [ICLR'26] 67.3 57.2 50.7 58.4 67.9 59.8 +5.0%
VISA 70.6 59.2 50.0 59.9 66.5 58.6 +4.4%
InternVL3-8B Base (Uniform-32) 74.1 63.2 54.2 63.9 68.6 59.2 +0.0%
AKS [CVPR'25] 76.3 65.4 54.1 65.3 74.3 61.0 +4.5%
WFS-SB [CVPR'26] 75.7 66.4 54.3 65.5 73.6 58.3 +2.8%
FOCUS [ICLR'26] 70.9 63.9 56.0 63.6 71.8 61.3 +2.6%
VISA 76.0 65.4 55.6 65.7 73.5 62.3 +5.1%
Qwen2.5-VL-7B Base (Uniform-32) 72.8 61.8 49.7 61.4 59.3 58.6 +0.0%
AKS [CVPR'25] 72.8 62.4 53.6 62.9 65.4 61.6 +5.9%
WFS-SB [CVPR'26] 74.4 64.4 54.2 64.4 70.3 58.8 +7.8%
FOCUS [ICLR'26] 70.2 60.9 53.4 61.5 67.9 62.3 +7.0%
VISA 75.0 62.3 54.4 63.9 67.2 63.8 +8.8%

Ablation Study and End-to-End Latency

Table A analyzes the contribution of each architectural component of VISA on Qwen2.5-VL-7B; Table B compares end-to-end efficiency on LongVideoBench where videos average 20,033.7 frames:

Table A: Ablation Study of VISA Components (Qwen2.5-VL-7B, 32-Frame Budget)

Model Variant VideoMME Acc (%) Drop (\(\downarrow\)) LongVideoBench Acc (%) Drop (\(\downarrow\))
Full VISA 63.9 - 63.8 -
Module 2: Skeleton-Aware Anchor Selection
w/o skeleton-aware allocation (global ranking) 62.8 \(\downarrow 1.1\) 61.0 \(\downarrow 2.8\)
w/o redundancy penalty (\(1 - \rho_i^{(r)}\)) 62.8 \(\downarrow 1.1\) 62.5 \(\downarrow 1.3\)
w/o scene-anchor hierarchy 62.7 \(\downarrow 1.2\) 62.3 \(\downarrow 1.5\)
Module 3: Cross-GOP Frame Refinement
w/o cross-GOP refinement (raw anchors only) 62.2 \(\downarrow 1.7\) 62.8 \(\downarrow 1.0\)
w/o boundary-aware scoring (\(b_i, \omega_i\)) 63.1 \(\downarrow 0.8\) 63.5 \(\downarrow 0.3\)
single-GOP refinement (no neighbor expansion) 63.4 \(\downarrow 0.5\) 63.0 \(\downarrow 0.8\)

Table B: Efficiency Comparison on LongVideoBench (Qwen2.5-VL-7B)

Method Decoded Frames Decoding Time (s) End-to-End Latency (s) Relative Latency vs VISA
AKS [CVPR'25] 736.4 35.93 83.19 +113.3% (2.13x)
WFS-SB [CVPR'26] 750.9 35.74 84.03 +115.5% (2.15x)
FOCUS [ICLR'26] 348.1 36.08 58.09 +48.9% (1.49x)
VISA (Ours) 408.2 22.40 39.00 Baseline (Fastest)

Key Findings

  • Skeleton-Aware Allocation Prevents Temporal Collapse: Replacing the skeleton-aware DP allocation with flat global ranking leads to the sharpest performance drop (a 2.8-point loss on LongVideoBench), confirming that flat ranking over-concentrates budget into local query-matching bursts, missing essential structural context elsewhere in the video.
  • Decoding Efficiency Substantially Improves Despite Similar Frame Counts: While VISA decodes 408.2 frames on average compared to FOCUS's 348.1 frames, VISA's decoding time drops from 36.08s to 22.40s. Because VISA's primary anchors are independently decodable I-frames, it avoids the recursive reference chains required to unpack arbitrary P/B frames, slashing end-to-end latency by 32.9% to 53.6%.
  • Robust Scaling with Frame Budgets: When evaluating budgets of 8, 16, 32, and 64 frames, VISA consistently outperforms Base and FOCUS on LongVideoBench. At a large budget of 64 frames, Base gains saturate and FOCUS drops below Base on VideoMME (62.1% vs 63.1%), whereas VISA continues to scale up cleanly to 65.2%, demonstrating high robustness against redundancy.

Highlights & Insights

  • Hardware-Aware Algorithmic Co-Design: Rather than treating video as an abstract sequence of uncompressed RGB arrays, VISA harnesses native GOP structures and independent I-frame decoding, eliminating massive sequential decoding chains. This hardware-friendly perspective is directly transferable to streaming video systems and edge-device MLLM inference.
  • Logarithmic Diminishing-Return Budget Allocation: Formulating scene allocation with concave log utilities and dynamic programming provides an elegant, parameter-light mechanism to distribute frame budgets across multi-scene narratives without relying on brittle heuristic clustering thresholds.
  • Robust Boundary Gate with Temporal Decay: Expanding the search across neighboring GOPs while curbing cross-scene semantic drift via local MAD normalization, boundary evidence gates, and exponential distance decay ensures that localized actions at GOP edges are captured without sacrificing shot consistency.

Limitations & Future Work

  • Evaluation Limited to 7Bโ€“8B Backbones: Due to computational resource constraints, the empirical evaluation focuses on 7Bโ€“8B open-source MLLMs; validating scaling ceilings on 70B+ models or proprietary frontier APIs (e.g., GPT-4o, Gemini 1.5 Pro) remains for future work.
  • Sensitivity to Irregular GOP Encodings: The density and distribution of native I-frames depend on external video encoding parameters. In videos encoded with open GOPs, non-standard keyframe intervals, or scene-adaptive encoding with erratic I-frame spacing, the initial skeleton resolution may exhibit non-uniform variance.
  • Fixed Budget Allocation: The framework currently operates under a predefined static frame budget \(B\) rather than dynamically determining the requisite frame budget based on video complexity and question difficulty.
  • vs AKS (Tang et al., CVPR 2025): AKS relies on low-rate uniform candidate decoding across the full video, resulting in high decoding latency (83.19s). VISA cuts latency by more than half (39.00s) and improves LongVideoBench accuracy on Qwen2.5-VL from 61.6% to 63.8% by anchoring on native I-frames.
  • vs FOCUS (Zhu et al., ICLR 2026): FOCUS filters temporal clips before frame selection but lacks an explicit global skeleton, making it susceptible to temporal fragmentation. VISA achieves higher accuracy across all frame budgets on LongVideoBench and cuts latency by 32.9%.
  • vs WFS-SB (Chen et al., CVPR 2026): WFS-SB detects semantic boundaries using wavelet transforms over decoded candidate streams, incurring substantial signal computation and decoding overhead (84.03s). VISA derives scenes from luma-map transitions on sparse I-frames, achieving higher speed and superior long-video reasoning.

Rating

  • Novelty: โญโญโญโญ Innovative exploitation of codec-level I-frames for video skeleton modeling in MLLM frame selection.
  • Experimental Thoroughness: โญโญโญโญโญ Rigorous evaluation across 3 MLLMs, 3 long-video benchmarks, comprehensive ablations, and explicit breakdown of decoding vs. inference latencies.
  • Writing Quality: โญโญโญโญโญ Well-structured, mathematically rigorous, and crystal clear in defining motivations and mechanisms.
  • Value: โญโญโญโญโญ Highly practical and impactful for reducing the operational cost of long-video MLLM deployment.