💻 computer science

Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA

The paper proposes VideoTreeSearch (VTS), a self-correcting agent framework that models grounded long-video QA as an iterative search over an adaptive temporal tree with explicit backtracking operations, significantly outperforming prior methods by enabling recovery from early mistakes and achieving state-of-the-art results across multiple benchmarks.

Original authors: Ce Zhang, Ziyang Wang, Yulu Pan, Oluwatumininu Oguntola, Pranav Wagh, Qiyu Wu, Hiromi Wakaki, Mohit Bansal, Gedas Bertasius

Published 2026-07-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ce Zhang, Ziyang Wang, Yulu Pan, Oluwatumininu Oguntola, Pranav Wagh, Qiyu Wu, Hiromi Wakaki, Mohit Bansal, Gedas Bertasius

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific, tiny moment in a movie that lasts for hours. Maybe you need to see exactly what a chef added to a bowl right before it went into the oven, but the video is a full-length cooking tutorial. If you just scan the whole movie quickly, you might miss that split-second action. But if you watch every single frame at normal speed, it would take you forever. This is the challenge of "Grounded Long-Video Question Answering." It's a task where a computer needs to not only answer a question about a long video but also point to the exact few seconds where the answer hides.

For a while, scientists tried to solve this by giving the computer a "scissors" tool. The computer would guess a time range, cut the video there, and look at the result. If it guessed wrong, it would try to cut again. But this approach was like trying to find a needle in a haystack by only being allowed to cut the haystack in half; if you cut the wrong half, you can't easily go back to the other side to try again. You just keep cutting the wrong piece smaller and smaller until you give up. This paper introduces a smarter way to search, turning the video into a map that the computer can explore, backtrack, and correct its mistakes on, much like a detective solving a mystery.

The Detective's Map: How VTS Solves the Video Mystery

Meet VideoTreeSearch (VTS), a new framework designed to help computers become expert video detectives. The researchers behind this paper realized that the old way of searching videos was too clumsy. Previous methods acted like a person who could only move forward, narrowing down a video clip by constantly cropping it. If they made a mistake early on—say, they thought the answer was in the first ten minutes when it was actually in the last ten—they were stuck. They had no way to say, "Wait, I went the wrong way," and go back to try a different path. They would just keep digging in the wrong hole.

The Tree Analogy
To fix this, the authors turned the video into a tree. Imagine the entire video is the trunk of a giant tree. The trunk splits into a few big branches, representing major scenes or chapters. Those branches split again into smaller twigs, and the twigs split into tiny leaves.

The Root: The whole video.
The Branches: Big chunks of the video where the scene changes (like moving from the kitchen to the dining room).
The Leaves: The tiny, specific moments where the answer might be hiding.

Crucially, this tree isn't built with equal-sized slices. Instead, the computer looks at the video and cuts the tree exactly where the visual story changes. If a scene lasts for five minutes, that branch is long; if a scene is just a quick flash, that branch is short. This means every part of the tree makes sense as a story unit, rather than just a random slice of time.

The Four Magic Moves
Once the video is a tree, the computer agent doesn't just "crop" anymore. It has four specific moves to navigate this map:

Zoom In: Go down a branch to see a smaller, more detailed part of the video.
Zoom Out: Go back up to the parent branch if you realize you went too deep in the wrong direction.
Shift: Move sideways to a different branch at the same level (like checking the next room instead of the current one).
Answer: Stop searching and give the final answer with the exact time stamp.

The most exciting part is Zoom Out and Shift. These are the "I made a mistake, let's try again" buttons. In the old methods, going back was impossible or very hard. In VTS, it's a standard, built-in move. The agent can dive into a wrong branch, realize it's a dead end, climb back up, and jump to a different branch to find the truth.

Training the Detective
You can't just give a computer a tree and expect it to know how to use it. The researchers had to teach the agent how to handle mistakes. They created a special training process where they deliberately sent the agent down the wrong path on purpose.

The Detour: The agent would be guided to pick a wrong branch.
The Recovery: Then, it had to figure out how to climb back up and find the right path.

By practicing these "detour-and-recovery" scenarios, the agent learned that making a mistake isn't the end of the game; it's just part of the search. It learned that if it gets stuck, it should use its Zoom Out and Shift tools to recover.

The Results
When they tested this new detective on three different video question-answering challenges, the results were impressive.

On the CG-Bench test, VTS improved the ability to find the right time interval by 12.5 points compared to the best previous method.
On the Haystack-Ego4D test (which uses very long videos), it improved by 7.4 points.
Even on general video questions where it didn't have to find the exact time, it still beat other methods by up to 7.1 points in accuracy.

The paper suggests that this "hierarchical search" (searching in layers) is the secret sauce. When they removed the ability to Zoom Out or Shift, the performance dropped significantly. This proves that the ability to backtrack is what makes the system so good.

Why It Matters
The authors found that VTS doesn't just guess; it explores. On average, it takes about 4.8 turns (steps) to solve a problem, whereas older methods usually gave up after just 1 or 2 turns. The new agent actively uses its backtracking tools in about 60% of its searches. It's not just a faster calculator; it's a smarter explorer that knows how to admit when it's wrong and try a different route.

In short, this paper shows that treating a long video like a structured map, rather than a flat list of frames, allows computers to solve complex questions with much higher accuracy. By giving them the tools to back up and change direction, we've taught them to be much better at finding the needle in the haystack.

Technical Summary: VideoTreeSearch (VTS) for Grounded Long Video QA

1. Problem Definition

The paper addresses Grounded Long Video Question Answering (Grounded LVQA), a task requiring a model to answer a question about a long video while simultaneously localizing the short temporal interval (evidence) that supports the answer.

Current agentic approaches typically frame this as a multi-turn exploration using a single continuous action: crop_video(start, end). The authors identify two critical structural shortcomings in these methods:

Asymmetric Action Space: While cropping naturally narrows the search (coarse-to-fine), it lacks a primitive for fine-to-coarse backtracking. Once an agent commits to a wrong region, it cannot easily recover, leading to premature convergence.
Flat Search Space: Continuous timestamp regression forces the agent to localize evidence from raw pixels without a hierarchical decomposition of the video. This leaves the search space unorganized and lacks semantic priors regarding where coherent segments lie.

Consequently, prior methods often fail to recover from early mistakes and struggle with precise localization in long videos where relevant evidence occupies a tiny fraction of the total duration.

2. Methodology: VideoTreeSearch (VTS)

The authors propose VideoTreeSearch (VTS), a framework that reframes Grounded LVQA as an iterative, self-correcting search over an adaptive temporal tree.

2.1 Adaptive Temporal Tree Construction

Instead of uniform frame sampling, VTS constructs a non-uniform tree where nodes correspond to semantically coherent video segments.

Boundary Detection: The tree is built by detecting visual scene changes using CLIP embeddings. For a given segment, frames are sampled at 1 fps, and cosine distances between consecutive embeddings are computed. Boundaries are placed where visual change exceeds an adaptive threshold.
Structure: The root represents the entire video. Intermediate nodes are coarse-grained segments, and leaves are fine-grained candidates. Children of a node form a non-overlapping partition of the parent's interval.
Lazy Materialization: The tree is constructed lazily during inference; only the root and children of visited nodes are materialized to keep the navigation space small.

2.2 Tree-Grounded Action Space

The agent navigates the tree using four discrete operations, explicitly separating exploration from self-correction:

zoom_in(c): Descends into the $c$ -th child segment (coarse-to-fine narrowing).
zoom_out(): Ascends to the parent node (fine-to-coarse backtracking).
shift(s): Moves laterally to the $s$ -th sibling under the same parent.
answer(ŷ, [ts, te]): Terminates the search with a final answer and the localized evidence interval.

This design turns backtracking from an implicit, difficult behavior into an explicit, learnable primitive.

2.3 Training Pipeline

Training requires supervision not only for correct paths but also for recovery from mistakes, which is absent in standard datasets. The authors introduce a trajectory synthesis pipeline:

Synthesis: A controller generates trajectories that include deliberate detours into incorrect branches followed by recovery (using zoom_out and shift).
Supervised Fine-Tuning (SFT): The agent is trained to imitate these trajectories. Crucially, the loss is applied selectively: the model observes the full "detour-and-recovery" sequence as context but is only supervised on the desirable moves (correct zoom-ins, recovery actions, and shifts). Intentional mistakes in the trajectory serve as context but are masked from the loss.
Reinforcement Learning (RL): Following SFT, the policy is refined using GRPO with rewards based on grounding accuracy (Temporal IoU) and answer correctness.

3. Key Contributions

Framework: Introduction of VTS, which casts Grounded LVQA as hierarchical search over a semantic tree rather than continuous regression.
Action Primitives: The proposal of discrete zoom_in, zoom_out, and shift actions that explicitly enable backtracking and self-correction, addressing the asymmetry of prior cropping methods.
Training Strategy: A novel trajectory synthesis pipeline that generates "detour-and-recovery" paths, enabling the agent to learn recovery patterns that are not present in ground-truth data.
Empirical Validation: Demonstration that explicit hierarchical search and backtracking are central mechanisms for improving performance on long-video tasks.

4. Experimental Results

VTS was evaluated on three Grounded LVQA benchmarks (CG-Bench, Haystack-LVBench, Haystack-Ego4D) and three general long-video QA benchmarks (Video-MME, MLVU, LVBench).

Grounded LVQA Performance

CG-Bench: VTS achieved 16.8 mIoU and 36.4% accuracy, outperforming the strongest prior agentic baseline (LongVT) by +12.5 mIoU and +19.0 accuracy.
Haystack-Ego4D: VTS achieved 18.4 T-F1 and 66.1% accuracy, surpassing the best baseline by +7.4 T-F1.
Efficiency: Despite superior performance, VTS processed fewer frames on average (328) compared to uniform sampling baselines (384) and captioner-LLM agents (450).

General Long-Video QA Transfer

The learned navigation policy transferred to general QA tasks without explicit grounding training:

VTS surpassed all prior agentic baselines on Video-MME, MLVU, and LVBench, with gains up to +7.1 accuracy points on LVBench.

Ablation Studies

Backtracking: Removing zoom_out and shift (no backtracking) degraded performance significantly across all metrics, confirming that self-correction is critical.
Tree vs. Flat: Replacing the hierarchical tree with a flat tree of uniform segments degraded QA accuracy, demonstrating the value of multi-scale search.
Trajectory Synthesis: Training on "detour-and-recovery" trajectories yielded significantly higher performance (+6.4 mIoU) than training on optimal-path-only trajectories.

5. Significance and Claims

The paper claims that structuring the search over a long video as an adaptive tree is a useful inductive bias for long-horizon video reasoning. The primary significance lies in shifting the paradigm from "continuous regression" to "discrete navigation," which:

Decouples Exploration and Correction: Makes backtracking an explicit, learnable behavior rather than an implicit, unstable capability.
Aligns with Semantics: By grounding the search in visual scene boundaries, the model reasons over semantically coherent units rather than arbitrary timestamps.
Enables Recovery: The ability to explicitly "undo" a wrong descent allows agents to handle the high cost of errors in long videos, where a single mistake can lead to irrecoverable loss of context.

The authors conclude that while VTS is trained primarily for evidence localization, the tree-grounded search policy generalizes effectively to broader long-video understanding tasks, suggesting that the mechanism of hierarchical, self-correcting search is broadly beneficial for video reasoning.