Source-linked AI summary
VideoDetective: Clue Hunting via both Extrinsic Query and Intrinsic Relevance for Long Video Understanding
Ruoliu Yang, Chu Wu, Caifeng Shan, Ran He, Chaoyou Fu
TL;DR
Long-video MLLM understanding is challenged by limited context windows and methods that localize clues primarily from queries while overlooking intrinsic video structure. VideoDetective combines query relevance with visual-temporal graph affinity in a Hypothesis-Verification-Refinement loop to propagate sparse observations across videos, consistently improving mainstream MLLMs by up to 7.5% on VideoMME-long. Its results support sparse, graph-guided clue localization, while its reliance on VLM self-reflection remains a robustness limitation.
Problem
Long-video MLLMs must identify sparse relevant segments under limited context windows, while existing methods largely overlook intrinsic inter-segment correlations.
Method
VideoDetective builds a visual-temporal affinity graph and iteratively verifies observed segments before propagating their relevance scores to unseen segments.
Results
VideoDetective consistently improves diverse MLLM backbones across representative benchmarks, with accuracy improvements of up to 7.5% on VideoMME-long.
Takeaways & Limitations
The framework localizes critical clues through sparse observations while maintaining computational efficiency through sparse sampling.
Takeaways & Limitations
The method relies on VLM self-reflection feedback signals, motivating more sophisticated relevance assessment mechanisms for robustness.
Abstract
from arXiv · showhide
Long video understanding remains challenging for multimodal large language models (MLLMs) due to limited context windows, which necessitate identifying sparse query-relevant video segments. However, existing methods predominantly localize clues based solely on the query, overlooking the video's intrinsic structure and varying relevance across segments. To address this, we propose VideoDetective, a framework that integrates query-to-segment relevance and inter-segment affinity for effective clue hunting in long-video question answering. Specifically, we divide a video into various segments and represent them as a visual-temporal affinity graph built from visual similarity and temporal proximity. We then perform a Hypothesis-Verification-Refinement loop to estimate relevance scores of observed segments to the query and propagate them to unseen segments, yielding a global relevance distribution that guides the localization of the most critical segments for final answering with sparse observation. Experiments show our method consistently achieves substantial gains across a wide range of mainstream MLLMs on representative benchmarks, with accuracy improvements of up to 7.5% on VideoMME-long. Our code is available at https://videodetective.github.io/
1. Introduction
VideoDetective addresses sparse clue localization in long videos by combining query relevance with intrinsic inter-segment correlations. Its iterative graph-based framework improves diverse MLLM backbones, with gains up to 7.5% on VideoMME-long.
- Limited context windows make it difficult to reliably localize query-relevant clues, especially for questions requiring complex reasoning.
- Existing keyframe, retrieval-based, and agent methods largely rely on query-to-content matching while overlooking intrinsic video correlations.
- VideoDetective models videos as Spatio-Temporal Affinity Graphs that encode visual semantics and temporal continuity.
- Its Hypothesis-Verification-Refinement loop selects informative anchors, verifies local relevance using multimodal information, and propagates scores through graph diffusion.
- 7.5% accuracy improvement is achieved on VideoMME-long across diverse MLLM backbones.
2. Related Work
Long-video understanding remains constrained by temporal length, context budgets, and the trade-offs of existing training-free approaches. Prior methods risk missing clues, require costly preprocessing, lose multimodal information, or lack robustness.
- Most MLLMs struggle with long-form content because of attention complexity and limited context windows.
- Key-frame sampling and token compression fit context windows but risk missing critical clues.
- Retrieval-augmented methods require full-video preprocessing and face information gaps when converting multimodal content to text.
- Agent-based methods use multi-step LLM planning and tools but lack robustness to diverse conditions.
3. Methodology
VideoDetective formulates long-video question answering as relevance estimation over a visual-temporal affinity graph. Its Hypothesis-Verification-Refinement loop sparsely observes anchor segments, propagates relevance, and selects top-ranked segments for final answering.
- Graph Construction: VideoDetective represents video segments as graph nodes, with edges combining visual similarity and temporal continuity.Segments are formed from frame-level visual features, while graph affinities encode both semantic similarity and temporal proximity.
- State Representation: The framework maintains sparse verified observations in an injection vector and a dense belief field estimating relevance for observed and unobserved segments.The belief field is inferred by propagating injection signals across the affinity graph.
- Answer Generation: The final answer is generated by feeding top-ranked segments from the refined belief field into the downstream multimodal language model.Algorithm 1 applies graph-based selection before final MLLM answer generation.
- Iterative Inference: The Hypothesis-Verification-Refinement loop selects anchors, verifies multimodal evidence, updates relevance scores, and diffuses them across the graph.Verification can combine visual captions, OCR, and ASR, while refinement progressively recovers the video’s global semantic structure.
- Anchor Selection: Query decomposition separates semantic facets into keyword and description components for facet-specific clue localization.Facet-guided initialization chooses the first anchor, while later iterations explore informative neighbors or fill global gaps.
- Belief Propagation: Graph diffusion enforces consistency with sparse observations and smoothness across high-affinity neighbors, allowing relevance to spread along visual-temporal paths.The graph is sparsified and symmetrized to support bidirectional information flow and efficient diffusion.
4. Experiments
Experiments evaluate VideoDetective across benchmarks, backbones, baseline paradigms, ablations, modality scales, and token budgets. The results show broad performance gains, component importance, visual-model bottlenecks, and improved accuracy-efficiency trade-offs.
- Experiments cover four representative long-video benchmarks, including VideoMME-long and LVBench without auxiliary transcripts, LongVideoBench validation, and MLVU test splits.
- Generalization across different backbones: 7.5% improvement is achieved on InternVL-2.5 (8B), while Oryx-1.5 (7B) improves by 7.0%, with robust gains across 8B–32B backbones.
- Controlled comparison with representative methods: VideoDetective consistently outperforms four representative long-video frameworks under matched Qwen3VL-8B and SeedVL-1.5 backbones with 32 answer frames.
- Comparison with state-of-the-art models: 67.9% accuracy on LongVideoBench (Val) with SeedVL-1.5 (20B) surpasses LLaVA-Video-72B at 63.9% and Gemini-2.5-pro at 66.8%.
- Component analysis: Removing graph propagation reduces performance by 4.2%, while removing facet decomposition lowers accuracy to 47.8%, below the baseline.
- Component analysis: A single-round variant drops 4.6%, and visual-only and uniformly combined visual-text settings reach 49.9% and 50.7%, respectively.
- Modality scaling analysis: Upgrading the VLM from 8B to SeedVL-1.5 raises accuracy from 55.6% to 65.1% (∆+9.5%), whereas upgrading the LLM from 8B to 30B changes it from 55.6% to 55.8%.
- Efficiency analysis: VideoDetective reaches 65.6% accuracy at approximately 38k tokens per video, while similar-budget VideoRAG and DVD are exceeded by over 13% absolute accuracy.
5. Conclusion
VideoDetective combines query relevance with intrinsic video correlations through a visual-temporal affinity graph and iterative inference. Across four challenging benchmarks, it locates critical clues with sparse sampling while maintaining computational efficiency.
- VideoDetective propagates query-relevance signals from sparse local observations across a visual-temporal affinity graph to locate critical clues.
- Across four challenging benchmarks, the framework competitively performs against strong MLLMs and consistently outperforms existing baselines with sparse sampling.
6. Limitation
VideoDetective relies on VLM self-reflection to generate feedback signals such as “missing keywords.” The authors identify more sophisticated relevance assessment as future work to improve robustness.
- The framework relies on VLM self-reflection to provide relevance feedback signals.An example is the “missing keywords” signal.
- Future work may explore more sophisticated relevance assessment mechanisms.The stated goal is improved robustness.
- The limitation concerns the mechanism used to assess relevance during clue hunting.
A. Belief Propagation: Theoretical Analysis
The analysis characterizes graph diffusion through its closed-form limit, convergence behavior, and sparse iterative computation. The broader pipeline selects and packages evidence for downstream answer generation.
- A.1. Closed-form Solution: The diffusion process converges to the closed-form belief field F⋆ = (1 −β) (I −β Wnorm)−1 Y after infinite iterations.The solution follows by setting successive belief fields equal and solving for F⋆.
- A.2. Convergence Analysis: The normalized affinity matrix has spectral radius at most 1, supporting exponentially fast convergence when βλmax < 1.The normalization is stated to guarantee stability of the iterative process.
- A.3. Computational Efficiency: O(K^3) direct inversion contrasts with O(TKk) sparse iteration, while new observations can update the current state without restarting computation.Here T and k are both much smaller than K in the stated setting.
- Evidence Selection: Graph-NMS suppresses neighbors of selected nodes to avoid redundant spatially and temporally adjacent evidence.The suppression factor η controls how aggressively neighboring nodes are suppressed.
- Evidence Packaging: Selected evidence packages include timestamps, uniformly sampled visual frames, and the highest-relevance textual evidence before downstream answer generation.The packages are temporally ordered and concatenated into a structured prompt.
D. Implementation Details and Hyperparameters
The implementation section states that the experiments use a complete set of hyperparameter settings. Parameters are consistent across benchmarks unless otherwise specified.
- The section provides the complete hyperparameter settings used in the experiments.
- The listed parameters are consistent across all benchmarks unless otherwise specified.
- The implementation details establish a common experimental configuration across benchmarks.
D.1. Backbone Comparison Experimental Configuration
Backbone comparisons use model-dependent frame counts and planner sizes. These configurations are intended to respect each model’s input capacity while maintaining fair comparisons.
- Frame Sampling: VideoXL2 and Oryx-1.5 use 16 frames, whereas all other models use 32 frames.
- LLM Planner: GLM, SeedVL, and Qwen3-VL 30B/32B variants use Qwen3-30B as the LLM planner.
- LLM Planner: All other models use Qwen3-8B as the LLM planner.
- Configuration Rationale: The varying frame sampling reflects different input capacities, while planner scale is matched to the visual backbone for computational efficiency.
- Configuration Rationale: The configurations are designed to test each model under optimal or commonly used settings while maintaining fairness.
D.2. Main Results Table Configuration
The main experiments evaluate VideoDetective under lightweight and larger parameter settings, while holding graph, propagation, inference, and final-answer frame budgets consistent for comparison.
- Main configurations: VideoDetective is evaluated in lightweight (<30B) and larger parameter configurations to test effectiveness across model scales.The configurations use Qwen3-VL-8B-Instruct with Qwen3-8B-Instruct, and SeedVL-1.5 with Qwen3-30B-Instruct, respectively.
- Controlled settings: Both configurations use 32 frames for final answer generation.The fixed frame budget supports fair comparison with baseline models.
- Controlled settings: Both configurations share graph construction, belief propagation, and active inference hyperparameters.This keeps the principal framework settings aligned across the two parameter scales.
D.3. Token Efficiency Data Collection
The token-efficiency analysis measures average per-video token consumption on VideoMME-long, combining real-run measurements for some methods with conservative lower-bound estimates for model baselines.
- Measurement setup: Average token consumption per video is reported on VideoMME-long for the token-efficiency analysis.The analysis focuses on input-token usage across videos in the benchmark.
- Measurement setup: VideoAgent, DVD, LVNet, and VideoDetective use token counts directly obtained from API response data during real inference runs.These values represent actual token consumption rather than estimates.
- Measurement setup: Gemini-1.5-Pro, GPT-4o, and LLaVA-Video-72B use estimated lower bounds based on official sampling rates, per-frame token counts, and standard video resolutions.The estimates are constructed from documented frame and token specifications.
- Measurement caveat: The model-baseline estimates include only image tokens and exclude prompts, system instructions, and other textual overhead.Consequently, the reported values are conservative and actual consumption would be higher in practice.
- Evidence scoring: Sparse lexical matching and dense semantic matching provide complementary retrieval signals.Dense matching handles synonymy and semantic equivalence but can drift toward false positives, whereas lexical matching preserves exact-token precision but misses paraphrases.
- Evidence scoring: Source-aware fusion combines lexical and semantic scores so exact mentions and implicit or varied references can both contribute.OCR favors lexical matching, while captions favor semantic matching through different source weights.
- Event descriptions: Event descriptions are generated from uniformly sampled frames, assigned to temporal nodes, and used as a semantic complement to keyword matching.The VLM produces a coarse time-stamped event timeline, whose descriptions are matched to node intervals.
- Evidence generation: Observed nodes provide VLM captions, OCR text, and ASR transcripts, which are scored independently through lexical-semantic matching.These sources supply complementary evidence for node-level relevance estimation.