VideoTreeSearch: Self-Correcting Tree Search Agents for Grounded Long Video QA

Forum topic · 小凯 · 2026-07-21

Summary

This paper introduces VideoTreeSearch (VTS), a framework that reformulates grounded long-video question answering as iterative self-correcting search over an adaptive temporal tree. Existing agentic approaches rely on a single coarse-to-fine crop_video action and lack an explicit backtracking primitive, causing premature convergence when early steps are wrong. VTS builds a non-uniform tree from visual scene boundaries, ensuring each node maps to a semantically coherent segment, and trains agents to navigate with four discrete operations: zoom_in, zoom_out, shift, and answer. A trajectory synthesis pipeline generates multi-step paths that include deliberate detours into wrong branches followed by recovery, enabling supervised fine-tuning followed by reinforcement learning with grounding and answer-accuracy rewards. VTS outperforms prior agentic methods on CG-Bench (+12.5 mIoU), Haystack-LVBench, and Haystack-Ego4D (+7.4 T-F1), and transfers to general long-video QA on Video-MME, MLVU, and LVBench with up to +7.1 accuracy gains.

Paper Overview

Research Area: cs.CV Authors: Ce Zhang, Ziyang Wang, Yulu Pan Release Date: 2026-07-21 arXiv: 2507.15489

Abstract

We propose VideoTreeSearch (VTS), a framework that casts grounded LVQA as iterative self-correcting search over an adaptive temporal tree. VTS constructs a non-uniform tree from visual scene boundaries so that each node corresponds to a semantically coherent segment, and trains an agent to navigate the tree through four discrete operations:

zoom_in
zoom_out
shift
answer

These operations expose backtracking and recovery as explicit, learnable primitives rather than implicit behaviors. To train this navigation, we introduce a trajectory synthesis pipeline that produces multi-step paths through the tree, including deliberate detours into incorrect branches followed by recovery. We use these trajectories for supervised fine-tuning, followed by reinforcement learning with grounding and answer-accuracy rewards.

Key Results

CG-Bench: +12.5 mIoU over the strongest prior agentic method.
Haystack-Ego4D: +7.4 T-F1 improvement.
Haystack-LVBench: Consistent gains over prior agentic baselines.
General Long-Video QA Transfer: The learned policy also transfers to general long-video QA, surpassing all prior agentic baselines on Video-MME, MLVU, and LVBench by up to +7.1 accuracy points.
Ablations: Confirm that self-correcting hierarchical search is the central mechanism behind these gains.

Original Abstract

Grounded long-video question answering (Grounded LVQA) requires answering a question about a long video while localizing the short evidence interval that supports the answer. Recent agentic methods frame this task as multi-turn exploration with a single crop_video(start, end) action, which supports coarse-to-fine narrowing but provides no primitive for fine-to-coarse backtracking. As a result, these agents typically converge prematurely and cannot recover from an early mistake. We propose VideoTreeSearch (VTS), a framework that casts grounded LVQA as iterative self-correcting search over an adaptive temporal tree. VTS constructs a non-uniform tree from visual scene boundaries so that each node corresponds to a semantically coherent segment, and trains an agent to navigate the tree through four discrete operations: zoom_in, zoom_out, shift, and answer. These operations expose backtracking and recovery as explicit, learnable primitives rather than implicit behaviors. To train this navigation, we introduce a trajectory synthesis pipeline that produces multi-step paths through the tree, including deliberate detours into incorrect branches followed by recovery. We use these trajectories for supervised fine-tuning, followed by reinforcement learning with grounding and answer-accuracy rewards. On three Grounded LVQA benchmarks (CG-Bench, Haystack-LVBench, Haystack-Ego4D), VTS outperforms the strongest prior agentic methods by +12.5 mIoU on CG-Bench and +7.4 T-F1 on Haystack-Ego4D. The learned policy also transfers to general long-video QA, surpassing all prior agentic baselines on Video-MME, MLVU, and LVBench by up to +7.1 accuracy points. Ablations confirm that self-correcting hierarchical search is the central mechanism behind these gains.