FocusGraph: Graph-Structured Frame Selection for Embodied Long Video Question Answering

Tatiana Zemskova; Solomon Andryushenko; Ilya Obrubov; Viktoriia Khoruzhaia; Ekaterina Eroshenko; Ekaterina Derevyanka; Dmitry Yudin

cs.CVMar 4, 2026

FocusGraph: Graph-Structured Frame Selection for Embodied Long Video Question Answering

Authors: Tatiana Zemskova, Solomon Andryushenko, Ilya Obrubov, Viktoriia Khoruzhaia, Ekaterina Eroshenko, Ekaterina Derevyanka, Dmitry Yudin

Organizations: AXXX · MIRAI · Yandex · FusionBrain Lab

Abstract

Understanding long videos is crucial for embodied intelligent agents, as their performance depends on effectively accumulating and using long-horizon perceptual memories. Multimodal large language models (MLLMs) are increasingly used for long-video understanding, but their performance degrades and inference time increases as more frames are provided. Therefore, selecting informative keyframes is essential for efficient question answering over long videos. In this work, we develop FocusGraph, a framework for keyframe selection in egocentric long-video question answering. It includes a lightweight Scene-Graph LLM Selector that identifies query-relevant clips from compact graph-based captions, avoiding the need to process raw frame sequences at question time. From these clips, we extract keyframes using Patch-wise Sparse-Flow Retention (PSFR), an offline program-evolved method with no learned parameters at inference time, before passing them to an MLLM for answer generation. FocusGraph achieves state-of-the-art performance on FindingDory and HourVideo while reducing question-time inference cost compared with existing approaches.

Figures & tables

Fig. 1: FocusGraph retrieves relevant intervals from a reusable scene-graph memory and uses PSFR to select non-redundant original frames for answer generation.

Fig. 2: FocusGraph overview. FocusGraph partitions an egocentric video into temporal clips represented by object-centric scene graphs generated with the SG-Ego pipeline [ 33 ] . The graph triplets are encoded into a compact chronological memory and processed jointly with the question by Scene-Graph LLM Selector, which generates a temporally grounded answer and identifies relevant video intervals. PSFR then selects up to $K$ informative, non-redundant frames for final answer generation by a downstream MLLM.

Frame Selection Method	Scene Representation	QA MLLM	Frame Number	All tasks		Single-Goal Spatial Tasks		Single-Goal Temporal Tasks		Multi-Goal Tasks
Frame Selection Method	Scene Representation	QA MLLM	Frame Number	full val.	dev.	full val.	dev.	full val.	dev.	full val.	dev.
Uniform Sampling	image	Gemini-3-Flash [ 46 ]	8	-	26.42	-	31.82	-	30.60	-	2.1
Uniform Sampling	image	Qwen-2.5-VL-7B [ 47 ]	8	12.6	18.4	16.4	22.6	11.8	19.4	2.0	3.2
Uniform Sampling	image	GPT-5-Mini [ 48 ]	8	15.49	24.25	20.37	29.27	14.04	27.38	2.71	2.78
Uniform Sampling	image	Qwen3.8-27B [ 49 ]	8	18.12	28.97	23.38	34.57	17.08	34.08	3.11	2.55
MaxInfo [ 13 ]	image	Qwen-2.5-VL-7B [ 47 ]	16	13.7	17.2	17.5	19.5	13.4	22.2	1.9	2.1

TABLE I: Performance comparison across frame sampling methods and LLM settings on FindingDory [ 6 ] .

Frame Selection Method	Frame No.	Overall	Nav.	Perc.	Reason.	Summ.
Uniform Sampling	8	29.86	10.0	33.7	27.9	37.8
Uniform Sampling	16	31.22	15.0	36.8	27.5	43.9
MaxInfo [ 13 ]	16	29.61	17.5	33.9	26.6	40.2
ReMEmbR [ 2 ]	8 1 1 1 For ReMEmbR, frame number is the average number of documents retrieved from the database per query.	24.28	17.5	24.54	27.47	0.0
VideoTree [ 51 ]	8	31.4	22.5	32.4	30.4	39.0
LVNet [ 52 ]	8	24.79	27.50	22.72	23.93	40.24

TABLE II: Results on HourVideo [ 4 ] . All methods use Qwen-2.5-VL-7B [ 47 ] except ReMEmbR [ 2 ] , which uses Llama3.1-8B [ 50 ] .

Method / stage	Scope	Tok./fr.	Time, ms
Reusable window processing
Frame-level relation extraction	Window	–	$59180\pm 14430$
Object grounding and frame-graph construction	Window	–	$10440\pm 6200$
Temporal tracking and graph consolidation	Window	–	$16230\pm 9890$
MaxInfo [ 13 ]	Window	–	3420
PSFR visual feature extraction (ours)	Window	–	$4530\pm 2440$

TABLE III: Inference latency on HourVideo [ 4 ] .

Fig. 3: Comparison of frame sampling methods. Left: FindingDory [ 6 ] . Green-bordered frames are present in the ground truth; red-bordered frames are not. Right: HourVideo [ 4 ] . Correct answers are highlighted in green, incorrect ones in red.

Method	$\mathrm{mIoP}$	$\mathrm{mIoG}$	$\mathrm{IoU@0.3}$	$\mathrm{mIoU}$	Sent. Sim.	Score
GPT-4o [ 54 ] (60 frames, z.s.)	18.9	24.4	12.0	12.2	73.7	5.4
InternVL2-8B [ 55 ] (30 frames, z.s.)	11.8	24.0	6.3	6.6	71.9	4.5
LLaVA-NeXT-Video-7B [ 56 ] (32 frames, z.s.)	–	–	–	–	62.1	4.2
TimeChat-7B [ 57 ] (96 frames, z.s.)	10.2	5.6	3.0	3.6	58.9	3.3
VTimeLLM-7B [ 58 ] (100 frames, z.s.)	12.4	28.2	8.8	9.2	70.5	4.3
LLaVA-NeXT-7B [ 56 ] $\rightarrow$ Llama-3.1-8B [ 50 ] (180 frames, z.s.)	21.4	22.3	10.1	9.7	63.6	3.5

TABLE IV: Comparison with published baselines and graph tokenization variants on the MultiHop-EgoQA [ 34 ] validation split.

Clip selection	Frame sampling	Frame number	All tasks	Single-goal spatial	Single-goal temporal	Multi-goal tasks
Uniform image baseline	Uniform	8	12.60	16.40	11.80	2.00
Scene-Graph LLM Selector	Uniform	8	15.76	21.72	12.65	3.15
Scene-Graph LLM Selector	PSFR	8	17.25	23.47	14.50	3.00

TABLE V: Downstream frame-sampling ablation on the FindingDory [ 6 ] full validation split.

		FindingDory (FD)			GenS		Time (s)
Keyframe selector	Opt.	Inter.	Incl.	$F_{\sqrt{2}}$	w-Inter	Incl	$\mu\pm\sigma$
Uniform	-	0.111	0.715	0.0136	0.470	0.890	–
Hand-Crafted	FD	0.075	0.380	0.008	0.501	0.840	$0.016\pm 0.002$
Grid-Search	FD	0.132	0.714	0.016	0.488	0.832	$0.017\pm 0.002$
Evolved on Inter.	FD	0.212	0.645	0.0289	0.449	0.803	$1.324\pm 0.933$
Evolved on $F_{\sqrt{2}}$	FD	0.181	0.834	0.0250	0.426	0.770	$0.007\pm 0.009$

TABLE VI: Ablation of keyframe selectors under a fixed budget of

K{=}16

frames. GenS denotes GenS-Videos-150K.

	Short		Medium		Long
Questions	46		52		65
Method	Score	EM	Score	EM	Score	EM
Uniform	2.000	10.9	1.865	15.4	2.308	12.3
FocusGraph	3.717	45.7	2.673	28.8	2.508	10.8

TABLE VII: Demo Outdoor Video QA Benchmark results. Score is the mean judge score (1–5), and EM is exact match (%).

Explore similar work

FORTE: Adaptive Scoring and Exact Keyframe Selection for Long-Video Question Answering
Sep 30, 2026Haifeng Huang, Biyin Xu, Chunsheng Xin +1Keyframe Selection Long Video Question Answering
Iowa State University.
QCA: Query- and Content-Aware Keyframe Selection for Long Video Understanding
Jul 1, 2026Jun Peng, Baiyang Song, Jie Li +4Video Understanding Keyframe Selection
Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, P.R. China · Peng Cheng Laboratory, Shenzhen, P.R. China · School of Electronic and Computer Engineering, Peking University, P.R. China
ReQuest: Rethinking-based Question-Aware Frame Selection for Long-Form Video QA
Jul 2, 2026Minkuk Kim, Suyong Yun, Young Tae Kim +3Long Video Question Answering Keyframe Selection
Kyung Hee University, Republic of Korea · Electronics and Telecommunications Research Institute (ETRI), Republic of Korea

Sep 30, 2026, cs.CVJ/K move · Enter open · S save

FORTE: Adaptive Scoring and Exact Keyframe Selection for Long-Video Question Answering

Haifeng Huang, Biyin Xu, Chunsheng Xin, Yang Li

Iowa State University.

Keyframe Selection Long Video Question Answering Long Videos Multimodal Large Language Models Question Gaussian Process

Open paper AskPDF arXiv

Query-aware keyframe selection enables multimodal large language models (MLLMs) to process long videos using only a small set of question-relevant frames. Existing score-based methods, however, typically search within a fixed, uniformly sampled candidate pool, preventing evidence outside this pool from ever being selected. Given a limited relevance-scoring budget, the key challenge is to allocate evaluations adaptively to promising frames while continuing to explore underrepresented temporal regions. We introduce FORTE, a training-free framework that addresses this challenge through two stages: adaptive relevance scoring and global keyframe optimization. Starting from sparse, uniformly distributed observations, our efficient Gaussian-process relevance predictor estimates relevance for unscored frames, exploiting temporal locality and the approximately banded kernel structure to reduce the core computation from cubic to linear time in the number of frames for fixed bandwidth. The scoring stage then selects which frames to score next by balancing predicted relevance with temporal coverage, prioritizing promising regions while also exploring less-represented parts of the video. The optimization stage selects the final keyframes by maximizing an objective that jointly captures measured relevance and temporal coverage. We derive an exact algorithm that leverages the logarithmic coverage structure to identify the optimal subset of the scored candidate pool in time linear in the pool size, for a fixed final-frame budget. Experiments on four long-video question-answering benchmarks show that FORTE achieves the highest observed mean accuracy among the compared selectors under every tested scoring budget. Further evaluations demonstrate its consistent effectiveness across different relevance scorers and downstream MLLMs.

Abstract

Explore similar work

FORTE: Adaptive Scoring and Exact Keyframe Selection for Long-Video Question Answering

QCA: Query- and Content-Aware Keyframe Selection for Long Video Understanding

ReQuest: Rethinking-based Question-Aware Frame Selection for Long-Form Video QA