Bridging VideoQA and Video-Guided Agentic Tasks via Generalized Keyframe Extraction¶

Conference: ECCV 2026
arXiv: 2606.29445
Project: https://vg-gui-tasker.github.io/
Code: https://github.com/VG-GUI-TASKER/VG-GUI-TASKER
Area: Video Understanding
Keywords: Keyframe Extraction, Video Question Answering, GUI Agent, Graph Search, Multimodal Large Language Models

TL;DR¶

This paper proposes TASKER, a generalized algorithm that formulates keyframe extraction as a graph search problem. An MLLM simultaneously evaluates task relevance (what information is missing) and scene dynamics (where major shifts occur) to guide the search direction, paired with a dual-path confidence voting mechanism to decide when to terminate. TASKER outperforms the previous best baselines by 2.0% and 1.8% on EgoSchema and NExT-QA respectively using only about 15% of the total frames, and introduces the matching VG-GUI-Bench benchmark to evaluate the model's ability to learn step-by-step operational steps from video tutorials and transfer them to GUI agent tasks.

Background & Motivation¶

Multimodal Large Language Models (MLLMs) have achieved impressive performance on VideoQA leaderboards. However, existing benchmarks almost exclusively assess whether a model can perceive shallow visual cues (object recognition, short-term actions, attributes), barely touching upon a more fundamental question: can the model learn procedural operational knowledge from video tutorials and generalize it to long-horizon agent tasks? This ability can be viewed as video in-context learning, which is highly common in real-world scenarios—such as watching a tutorial on "how to change a Discord password" and then performing the steps in a GUI environment.

This work first categorizes video understanding into two progressive tiers: low-level VideoQA (extracting factual information from videos and performing conditional reasoning) and high-level video-guided agentic tasks (learning procedural knowledge from video demonstrations and transferring it to decision-making execution). Currently, the field suffers from two main pain points: first, the lack of benchmarks to evaluate high-level capabilities, and second, both tiers sharing the same bottleneck—how models locate task-relevant temporal content in long videos. Long videos are filled with redundant segments, whereas key operational evidence often appears only briefly. Naive uniform sampling either misses key moments or introduces excessive redundancy that degrades inference. For instance, in NExT-QA, under the same frame budget, GPT-4o with a frame filtering strategy improves accuracy by about 15% compared to uniform sampling.

To address this, this paper does two things: first, it releases VG-GUI-Bench, a benchmark pairing video tutorials with GUI interaction tasks (1,000 test cases, averaging 10.71 steps per episode); second, it proposes TASKER, a task-driven and scene-aware keyframe search algorithm that unifies temporal information selection in both VideoQA and video-guided agentic tasks from the perspective of classic graph search. Core Idea: Model keyframe extraction as a graph search problem, leveraging MLLMs as cost function evaluators and confidence judges. The search simultaneously considers "what information is still needed for the task" and "where the video has changed significantly" to support accurate inference with minimal frames.

Method¶

Overall Architecture¶

TASKER treats a long video as the root node and progressively approaches the video clips containing key information through continuous binary splitting and selective expansion. The entire process is an iterative tree search: in each round, visible frames (the first and last frames of each clip) are extracted from all currently split video segments. Based on the visible frames' information, the answer is predicted, and the current confidence is evaluated. If the confidence is insufficient, the most valuable node is chosen for binary expansion according to a cost function. After expansion, new frames are verified for redundancy, and the process proceeds to the next round.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Video + Question/Task"] --> B["Uniformly split into M segments<br/>Initialize Open List"]
    B --> C["Extract Visible Frames<br/>First/Last frame of each segment"]
    C --> D["Predict Answer/Action"]
    D --> E["Confidence Evaluation<br/>Self-evaluation + Temporal Summary Voting"]
    E -->|"c1≥C and c2≥C"| F["Output Answer + Keyframe Set"]
    E -->|"Insufficient Confidence"| G["Task-Driven & Scene-Aware<br/>Cost Function Evaluation"]
    G --> H["Select Beam Nodes<br/>Binary Expansion"]
    H --> I["Frame Verification & Frozen Set"]
    I --> C

The search starts by spliting the entire video uniformly into $M$ segments (set to $M=10$ in the paper), where each segment is a node, and all are placed into the open list $\mathcal{L}$. Each iteration uses only the visible frames $\mathcal{F}_v$—meaning the first and last frames of all segments (since adjacent segments share bounding frames, information can be concatenated)—to predict the answer. At this stage, the MLLM can only "see" these boundary frames, while the internal frames of the segments remain invisible. If the confidence meets the threshold, the search terminates, outputting the current answer and the visible frames as the keyframe set. Otherwise, the cost function is evaluated to select the $B$ highest-scoring nodes for binary expansion (splitting a segment in half at its midpoint). The newly exposed internal frames undergo deduplication and relevance verification before entering the next round. The maximum number of iterations is $T=6$. The entire process is a training-free zero-shot inference, relying solely on the evaluation and reasoning capabilities of the MLLM.

Key Designs¶

1. Graph Search Formulation: Translating Keyframe Extraction into a Node Expansion Problem

TASKER's core insight is that keyframe extraction naturally lends itself to graph search modeling. Video segments serve as nodes. Starting from a coarse-grained initial partition, the search progressively "unfolds" certain segments to approximate the temporal intervals containing key information—equivalent to performing heuristic search on a video tree. Traditional keyframe methods either rely on pre-computed feature clustering (such as VideoTree, which clusters features across all frames to construct a tree, resulting in high pre-processing costs independent of the query) or perform fixed-pattern recursive sampling (such as VideoAgent's uniform downsampling). In contrast, TASKER delegates the decision of "which segment to expand" to the online evaluation of the MLLM, allowing the search direction to dynamically adjust to the query and video content.

Specifically, the search manages all current video segments using an open list $\mathcal{L}$, from which nodes are selected for expansion in each round based on a cost function $f(n)$. The expansion is performed via binary splitting: the selected segment is split in half at its midpoint, and the new first and last frames become visible frames added to $\mathcal{F}_v$. Rather than using traditional "target node reached" criteria (since the sufficiency of information cannot be known beforehand in keyframe search), the search termination is governed by a confidence evaluation mechanism (see Design 3).

2. Dual Task-Driven and Scene-Aware Cost Functions: Three Search Strategies Cover Diverse Needs

This is the core design of TASKER. Inspired by classic graph search algorithms, the paper defines four cost function variants corresponding to different search preferences:

TASKER-GBFS (Task-driven): Employs a heuristic function $h(n)$, where the MLLM judges "what information is still missing from the current visible frames to answer the question," and then evaluates which two invisible frames the missing information is most likely located between. A smaller $h(n)$ means the current node is closer to "sufficient information." GBFS prioritizes expanding nodes with the simplest $h(n)$ . This strategy is purely driven by the task query, making it suitable for scenarios with clear questions and concentrated key information.
TASKER-Dijkstra (Scene-aware): Employs a transition cost function $g(n)$, where the MLLM evaluates the degree of scene change (scene cuts, character movements, activity transitions, etc.) between the boundary frames of each segment. Segments with larger changes are assumed to contain richer information and are prioritized for expansion. Notably, this strategy operates without reading the question—the MLLM makes selections solely based on the video's intrinsic structure, rendering it purely scene-aware and suitable for scenarios without a clear query but requiring a video summary.
TASKER-A* (Joint task + scene): The cost function is $f(n) = h(n) + g(n)$, which simultaneously accounts for task relevance and scene dynamics. Only segments that score highly on both aspects are prioritized for expansion. Experiments show that the A* variant achieves the best overall performance across tasks.
TASKER-BFS (Naive baseline): Skips cost evaluation and uniformly expands all nodes, advancing layer by layer like a wave. This is suitable for scenarios where MLLMs are unavailable or no information can be missed. The paper does not introduce a DFS variant, as depth-first search is prone to getting trapped in local optima.

3. Confidence-Driven Search Termination: Dual-Path Voting via Self-Evaluation and Temporal Summarization

When does the search stop? Traditional graph search terminates upon "reaching the target node," but keyframe search has no explicit target state—it is unknown whether sufficient information has been gathered. TASKER leverages the MLLM's self-evaluation capabilities to design a dual-path confidence voting mechanism:

Self-Evaluation and Self-Reflection: The question, visible frame information, the model's reasoning chain, and the predicted answer are fed back to the MLLM to evaluate the accuracy and reliability of its own answer, outputting a confidence score $c_1$. This exploits the MLLM's ability to reflect on its own reasoning flaws.
Temporal Summarization: Frame captions are discrete and lack temporal context. TASKER guides the MLLM using few-shot exemplars to synthesize captions of all visible frames into a coherent video summary, and then predicts the answer and outputs a confidence score $c_2$ based on this summary. This compensates for the limitations of analyzing isolated frames by judging information sufficiency within a complete temporal context.

The search terminates only when $c_1 \geq C$ and $c_2 \geq C$ (where $C$ is the confidence threshold). Ablation studies show that when the two paths are used independently, their accuracies are 67.4% and 67.3% respectively; combining them through joint voting boosts the accuracy to 68.0%, verifying the complementarity of the two perspectives.

4. Frame Verification and Frozen Set: Deduplication to Prevent Redundancy and Avoid Repeated Exploration

Each node expansion generates new visible frames, which may include redundant frames (highly visually similar to existing visible frames) or irrelevant frames (not containing information required for the task). TASKER executes a frame verification step after each expansion round: it first checks the visual redundancy of the new frames against existing ones, and then directs the MLLM to assess their task relevance. Redundant or irrelevant frames are discarded (with alternative frames searched nearby if possible). Segments that produce only redundant frames are added to a frozen set $\mathcal{S}_{\text{frozen}}$ and are excluded from subsequent iterations. This mechanism effectively controls the growth of visible frames, serving as a key guarantee of TASKER's high frame efficiency.

A Complete Example¶

Taking a 3-minute video from EgoSchema as an example: the key information for the answer appears only between seconds 126 and 130, accounting for only about 2% of the video. TASKER begins with 10 initial segments (approx. 18 seconds each). In the first round of evaluation, the A* cost function detects a significant scene switch between the first and last frames of a specific segment (high $g(n)$), and the MLLM determines that the missing answer clue is likely within this interval (low $h(n)$), thereby prioritizing this node for expansion. After binary splitting, the newly exposed middle frame narrows down the search range, and the next round continues the evaluation at a finer granularity. After about 3-4 iterations, TASKER precisely localizes the 125-130s interval, returning its frames as keyframes and successfully answering the question. Throughout the search tree, only nodes on the critical path are expanded (marked in yellow in the diagram), while others remain virtually unexplored, resulting in only about 28 visible frames being consumed (15% of the total frames).

Loss & Training¶

TASKER is a training-free method and utilizes no loss functions. The only adjustable hyperparameters are the initial segment count $M$ (default 10), maximum iterations $T$ (default 6), beam width $B$, and confidence threshold $C$. The backbone LLMs used are gpt-4-1106-preview and gpt-4o-2024-11-20. The captioners used are CogAgent for NExT-QA and LaViLa for EgoSchema (due to its self-supervised video pre-training tailored for egocentric scenarios).

Key Experimental Results¶

Main Results¶

VideoQA Results (Table 1): TASKER-A* consistently outperforms the previous best baselines on both the full EgoSchema and NExT-QA datasets.

Dataset	Metric	TASKER (GPT-4)	Prev. SOTA	Gain
EgoSchema	Full Acc.	63.1	61.1 (VideoTree)	+2.0
EgoSchema	Subset Acc.	68.0	66.2 (VideoTree)	+1.8
NExT-QA	Temporal (Tem.)	72.3	70.6 (VideoTree)	+1.7
NExT-QA	Causal (Cau.)	78.2	76.5 (VideoTree)	+1.7
NExT-QA	Descriptive (Des.)	85.4	83.9 (VideoTree)	+1.5
NExT-QA	Average	77.4	75.6 (VideoTree)	+1.8

Switching to GPT-4o further increases performance to 63.6 on EgoSchema and 78.1 on NExT-QA. Using the open-source Qwen3-VL-235B still yields an average improvement of 0.8% over VideoTree. Crucially, TASKER processes only about 15% of the total frames (e.g., ~28 frames for the full EgoSchema dataset vs. 180 total frames), whereas methods like LangRepo and LifelongMemory process all frames. In terms of frame efficiency, at the same 66% accuracy level, TASKER consumes only about 1/4 of the frames required by VideoTree.

VG-GUI-Bench Results (Table 3): Comparing various keyframe selection methods using Qwen3-VL-235B as the backbone.

Method	Acc. (%)	Type Acc. (%)	Comp. (%)	Eff. (Frames/Step)	PIR
No Video	25.32	65.85	69.03	0	-
All Keyframes	37.21	65.75	72.01	13.23	0.470
Uniform Sampling	39.82	66.34	70.64	10.88	0.573
Oracle Keyframes	44.32	73.31	76.32	1	0.750
VideoTree	40.79	67.52	71.93	10.00	0.611
VideoAgent	39.86	67.03	71.17	5.12	0.574
TASKER-A*	40.96	67.71	71.38	8.24	0.618

TASKER-A* achieves the best performance in both overall accuracy and PIR (video-guided learning gain), with TASKER-Dijkstra closely approaching the Oracle upper bound with a 74.39% completion rate (vs. 76.32%). On the VG-GUI-Bench leaderboard, Gemini-3.1-Pro leads with 61.68% (using 10-frame uniform sampling).

Ablation Study¶

Comparison of Search Algorithms (Table 4, EgoSchema Subset):

Algorithm	Acc. (%)	Visible Frames
TASKER-BFS	64.7	31.2
TASKER-GBFS	67.0	27.3
TASKER-Dijkstra	66.8	27.6
TASKER-A*	68.0	27.9

A* outperforms BFS by 3.3% while consuming fewer frames (27.9 vs. 31.2), indicating that targeted search is more efficient than uniform expansion. GBFS and Dijkstra outperform BFS by approximately 2.3% and 2.1% respectively, while A* combines their strengths for a further accuracy boost with only a minor compromise in frame efficiency.

Ablation of Termination Conditions (Table 5, EgoSchema Subset):

Method	Acc. (%)	Visible Frames
Self-Evaluation Only	67.4	27.4
Temporal Summary Only	67.3	28.2
Joint Voting	68.0	27.9

The performance is similar when each path is independent. However, joint voting improves accuracy by 0.6-0.7%, demonstrating that the two perspectives evaluate different dimensions of information sufficiency, and their combination yields higher reliability.

Key Findings¶

A* Is the Practically Optimal Choice: TASKER-A* exhibits the best overall performance in all tested scenarios, demonstrating that both task-driven and scene-aware aspects are indispensable. Purely task-driven methods (GBFS) can be misled when queries are ambiguous, while purely scene-aware methods (Dijkstra) might expand irrelevant segments that contain high visual changes.
Frame Efficiency Gain Stems from "On-Demand Expansion" Rather than "Full Pre-processing": VideoTree requires pre-computing feature clustering on all frames to build a static tree, whereas TASKER only processes visible frames and uses the frozen set mechanism to avoid repeatedly exploring invalid regions. At matching accuracy, TASKER consumes only 1/4 of the frames required by VideoTree.
Stronger Backbone LLMs Yield More Significant Search Gains: GPT-4o achieves higher absolute accuracy and better frame efficiency than GPT-4 (26.7 vs. 27.9 visible frames). However, reasoning models like o3-mini and DeepSeek-R1 perform slightly worse. The authors attribute this to the relatively "straightforward" visual reasoning required in this task, which does not fully leverage the deep thinking advantages of these reasoning models.
Video Guidance Effectively Enhances GUI Agent Capabilities: All models demonstrate accuracy gains on VG-GUI-Bench when utilizing 10-frame uniform sampling. Seed-2.0-Pro reaches a PIR of 0.107 (improving from 35.93% to 39.78%). However, the absolute PIR values remain low overall, indicating that extracting executable knowledge from videos remains an open challenge.

Highlights & Insights¶

Unifying Keyframe Extraction via Classic Graph Search Is an Elegant Abstraction: The four strategies (BFS/GBFS/Dijkstra/A*) correspond to different application preferences—BFS when MLLMs are unavailable, GBFS for pure question-driven scenarios, Dijkstra for pure video-structural analysis, and A* for the optimal joint configuration. The "pluggable" nature of this framework allows deployment under various resource constraints.
Pragmatic Confidence Voting Design: Captions of isolated frames lack temporal context, while viewing raw frames directly may lack a global perspective. The two paths complement each other, and their joint voting is more robust than a single hard decision. Although the ablation shows a modest improvement of 0.6-0.7%, the mechanism itself can be generalized to any iterative search task that relies on MLLM self-evaluation.
Valuable Metric Design in VG-GUI-Bench: Splitting action correctness into a action type score (0.3) and a parameter score (0.7) provides a finer grain than simple exact matching. The PIR (Performance Improvement Ratio) metric directly quantifies "how much the video actually helped," which can be reused in other video-guided benchmark evaluations.
The Frozen Set Is a Hidden Gem for Frame Efficiency: Many search methods repeatedly probe "dead zones." TASKER explicitly marks invalid segments using a frozen set, which, combined with frame deduplication, curbs the visible frame count to about 15%. This mechanism can easily be transferred to any iterative frame sampling method.

Limitations & Future Work¶

Heavy Reliance on MLLM's Evaluation Capability: Cost function evaluation, confidence estimation, and frame relevance determination all depend on the zero-shot evaluation quality of MLLMs. If the MLLM fails to judge accurately in a particular domain (e.g., being insensitive to scene changes in specific videos), the entire search direction can be derailed. The authors do not discuss fallback strategies when the MLLM's evaluations fail.
The Performance Gap on VG-GUI-Bench Remains Wide: Even with TASKER-A*, the accuracy reaches only 40.96% (while the Oracle is only 44.32%), suggesting that transferring knowledge from video tutorials to GUI operations remains fundamentally challenging. The paper lacks a detailed breakdown of failure cases (e.g., which types of actions are unlearnable? Is it a temporal alignment issue or an abstract generalization issue?).
Lack of Sensitivity Analysis for Hyperparameters $M$ and $T$: The initial segment count and the maximum number of iterations directly affect search outcomes. However, the paper only provides default values in the appendix, without presenting performance curves across various parameter sweeps, leaving practitioners with little guidance on tuning these parameters for different video lengths.
Unknown Applicability to Extremely Short Videos and Live Streams: TASKER assumes videos have a certain duration (more than 3 minutes in experiments). For very short videos (e.g., several seconds), a few binary splits will reach the frame level, nullifying the search advantage. For live streams, an online version would be required.
Directions for Improvement: Lightweight visual cues (such as CLIP similarity or optical flow magnitude) can be incorporated into the cost function to supplement the MLLM, reducing sole dependency on the MLLM's evaluation. Additionally, TASKER's search process can be combined with end-to-end Video-LLMs, where the extracted keyframes serve as inputs to enable more powerful two-stage inference.

vs. VideoTree: VideoTree precomputes feature clustering on all frames to build a static tree before performing LLM-guided search. In contrast, TASKER performs no pre-processing, extracts frame information on-demand during the search, and incorporates both task and scene dimensions into its cost function. The disadvantage of TASKER is that it queries the MLLM for cost evaluation in every round, which may incur high API costs when the number of iterations is large.
vs. VideoAgent: VideoAgent also performs multi-round frame sampling, but its frame selection strategy does not explicitly model internal scene transitions and video structure. TASKER's Dijkstra variant specifically addresses this via scene-change-driven search. Furthermore, TASKER's frozen set mechanism better avoids redundant exploration.
vs. TongUI / Watch-and-Learn: These works focus on translating videos into learnable trajectories at the action sequence level. TASKER operates at the frame selection level as a training-free module, meaning it can serve as a plug-and-play front-end component for these methods.
Insights: Combining traditional algorithms (graph search) with the strengths of MLLMs (evaluation, reflection, summarization)—where the MLLM acts as a component that typically requires human intuition (such as heuristic function design)—represents a promising paradigm. This can be extended to other tasks requiring "step-by-step target approximation," such as long-document retrieval in text or bug localization in codebases.

Rating¶

Novelty: Four Stars. Formulating keyframe extraction as a graph search and leveraging MLLMs to evaluate the cost function is a fresh approach. The dual-path cost function design is also clever, though the underlying components (MLLM self-evaluation, tree search) are not fundamentally brand new.
Experimental Thoroughness: Four Stars. The evaluation covers two VideoQA benchmarks and a self-constructed GUI agent benchmark, presenting ablations on search strategies, termination conditions, and backbone LLMs, as well as quantitative comparisons on frame efficiency. However, it lacks hyperparameter sensitivity analyses and failure case analyses.
Writing Quality: Five Stars. Well-structured and logical. The methodology section provides a clear mapping from classic graph search to TASKER. The pseudocode and diagrams are nicely aligned, and the appendix offers full prompt templates and implementation details.
Value: Four Stars. The work makes dual contributions by introducing both a benchmark (VG-GUI-Bench) and a method (TASKER). Its training-free nature allows plug-and-play integration into various video understanding pipelines. However, the absolute accuracy of video-guided agentic tasks is still low, leaving a gap for practical application.