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

arXiv:2607.16189 · cs.CV · Submitted 2026-07-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Searching Videos as Trees".

Jane: Here's the gist of the paper. 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.

Tom: Pruning redundant reasoning tokens The paper proposes VideoTreeSearch (VTS), a framework that casts grounded LVQA as iterative self-correcting search over an adaptive temporal tree.

Jane: VTS constructs a non-uniform tree from visual scene boundaries so that each node corresponds to a semantically coherent segment.

Tom: The agent navigates this tree through four discrete operations: zoom in, zoom out, shift, and answer.

Title and authors: Tom: So we're looking at this paper now called "Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA". It sounds like they’re trying to fix a problem where AI agents look at long videos and try to find the right piece of evidence, but they usually just keep cropping and fail if they make a mistake.

Jane: Right, so the main idea is that instead of just one continuous crop action, which is what those earlier methods used, this paper structures the video into a tree of segments and gives the agent specific moves to navigate it.

Lu: Exactly. They propose VideoTreeSearch or VTS, where they build this non-uniform tree based on visual scene boundaries so that each node represents a semantically coherent segment. This means instead of just looking at one part of the video, the agent is exploring different parts in a structured way.

Meng: So what’s the core mechanism? It sounds like they are teaching an agent to move through this tree using four specific actions: zoom in, zoom out, shift, and answer. I need to know if these actions are just fancy ways of saying cropping or something more specific.

Tom: They're not just fancy ways of saying cropping; they’ve made the backtracking part explicit. They call it a discrete tree-grounded action space where zoom out and shift are learnable primitives that let the agent recover from a wrong branch, which is a big deal for self-correction.

Jane: That sounds like it solves the problem of those agents just converging too early and not being able to recover when they hit an error. They use a trajectory synthesis pipeline to train the agent on deliberate detours into incorrect branches and then recovery moves, which helps instill those navigation patterns through supervised fine-tuning.

Lu: And what’s really interesting from the training setup is how they design that loss function so backpropagation only happens through turns whose actions are actually desirable—like a correct zoom in or a shift from a wrong node to the right sibling. It makes the learning process more guided than just standard reinforcement learning.

Meng: From an engineering standpoint, training on these synthesized trajectories sounds smart for robustness, but how does this affect deployment? If we deploy this, are we talking about complex tree navigation every single time a user asks a question about a long video?

Title and authors: Tom: It’s not meant to be that complex for the end user; it’s meant to be the agent's internal search policy. The point is that VTS substantially outperforms prior agentic methods across all three Grounded LVQA benchmarks, and the biggest gains are seen on HaystackEgo4D, which is their longest-video benchmark.

Jane: That result suggests that structuring the search over a long video is a useful bias even when you’re not just trying to localize evidence in a very specific spot. They also found that this tree-grounded action space outperforms continuous cropping by about one point three to four points on temporal grounding metrics and up to nearly ten points on QA accuracy.

Lu: And they’ve shown that removing those explicit backtracking primitives, the zoom out and shift actions from the tree-grounded action space, actually degrades performance on every single benchmark and metric they tested. That strongly implies the structure itself is providing a real benefit beyond just temporal localization.

Meng: So if we look at how this transfers to general long video understanding—not just grounding evidence—the paper says the learned policy also transfers well to tasks like Video-MME and MLVU, surpassing prior agents by up to seven point one accuracy points. That's a significant jump for a general understanding task.

Tom: It suggests that the structure of tree search isn't just for finding evidence; it’s a useful inductive bias for long horizon reasoning in general video QA, which is something we need to keep in mind when designing future agents.

Jane: Before we wrap up, they did flag a few limitations. For instance, the current action space only produces a single evidence interval per question and doesn't handle questions where the evidence is spread across multiple separate temporal regions.

Lu: They also mentioned that their adaptive segmentation relies on CLIP-based scene boundary detection, which they found can be less reliable when looking at videos that are visually very homogeneous. And finally, the trajectory synthesis depends on external vision-language and language models for captioning and reasoning.

Meng: So in short, it’s a powerful framework where structure helps recovery, but it has its own hurdles regarding video diversity and training dependency. It’s not a magic fix for every long video scenario yet.

Tom: Exactly. But the overall message is that organizing the search as a tree of segments and giving the agent explicit ways to backtrack makes precise localization and recovery learnable behaviors rather than implicit ones, which is a key step forward.

Title and authors: Jane: So if you’re driving or cooking and you ask an AI about something in a long video, this paper suggests the AI won't just keep trying one big crop; it will explore the video like a map of connected scenes and know how to backtrack when it gets lost.

Lu: That structural organization is what allows for that self-correction, turning mistakes into navigation steps on the tree. It’s about making exploration deliberate instead of accidental.

Meng: For deployment, we’d want to see if we can make those scene boundaries more robust so it doesn't fail on visually simple stuff like a plain wall or a long stretch of sky. That would be where the real production risk is for me.

Tom: So we’re looking at how this VTS framework organizes the video as a tree and uses zoom out and shift to recover from errors, and it shows that this approach beats prior multi-turn cropping agents on three different Grounded LVQA benchmarks.

Jane: And it extends to general understanding tasks like Video-MME, showing that even if you aren't strictly grounding evidence, the tree search structure helps the AI reason better over long videos.

Lu: It’s a strong indication that hierarchical search is a valuable inductive bias for handling long horizon video reasoning. It suggests that how we structure the search itself matters as much as the base model we use.

Meng: We need to keep watching these results on real traffic, because while the numbers are great, they're still based on curated data and those external models used for training are a dependency.

Tom: So that’s what they found: VTS outperforms prior agents by using tree search and explicit recovery actions, showing that structure is key to self-correcting in long video QA. We’ll keep an eye on how this scales.

Jane: That’s the big picture for now. We're looking at how organizing a video into a semantic tree and teaching an agent specific moves helps it localize evidence and recover from mistakes, with strong results across several benchmarks.

Lu: It really highlights that moving from continuous cropping to discrete, learnable navigation actions is what unlocks this level of performance gain.

Meng: I think the next step for us is figuring out how to make those scene boundaries more reliable so we can move this from research papers into something that actually runs smoothly in production.

Tom: Right, so it’s about making the search explicit and structured rather than implicit, which is what this paper on Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA shows us.

The paper's summary: Tom: So, to recap, this paper is about taking long videos and turning them into a tree structure so an AI agent can search through them more intelligently instead of just blindly cropping everything in one go.

Jane: Exactly. They introduce VideoTreeSearch or VTS, which builds this non-uniform tree based on where the visual scenes change, making each node a meaningful segment of the video.

Tom: And the core idea is that instead of just one big search path, the agent navigates this tree using four specific moves: zoom in, zoom out, shift and answer. These aren't just random movements; they are discrete actions that are explicitly learnable.

Jane: That’s what makes it different from before. They’ve trained the AI on these moves by creating trajectories where the agent deliberately takes wrong turns and then learns how to recover by using zoom out or shift back to a correct path.

Tom: The training setup is pretty clever too. they use this trajectory synthesis pipeline to teach the agent recovery patterns through supervised fine-tuning, and they even guide the learning with a loss function that only cares about actions that are actually good, like zooming in correctly or shifting from a wrong spot to the right neighbor.

Jane: That makes sense. It’s forcing the AI to learn how to self-correct by making those recovery moves explicit steps it has to master, instead of hoping it figures out how to backtrack on its own.

Tom: The results are pretty strong across three different tests, especially on HaystackEgo4D, their longest video benchmark. They’ve shown that this tree search approach beats continuous cropping by a noticeable amount in both localization accuracy and overall answer accuracy.

Jane: And they found that even when you take away those explicit backtracking moves—the zoom out and shift actions—the performance drops on every single benchmark they tested. That really proves the structure itself is giving them an advantage, not just the base model.

Tom: It suggests that for long video reasoning, structuring the search over time into a hierarchy of segments is a useful way to give an AI better reasoning capabilities than just looking at one continuous frame at a time.

Jane: And it’s not just about finding evidence; they showed that this learned policy actually transfers well to general long video understanding tasks, like Video-MME and MLVU, where the AI has to understand the whole context.

Tom: The implication here is that we might be looking at a new inductive bias for any long-horizon reasoning task in video stuff, which means we should probably start thinking about structuring our search space before we even think about what the base model can do.

Jane: But they did mention some things that limit this right now. For example, this setup only gives one evidence interval per question, and it doesn't handle questions where the important evidence is spread out across several different parts of the video.

Tom: And another thing is that their segmentation method relies on CLIP-based scene boundary detection, which they found can be less accurate if a video looks very similar everywhere. Also, they rely on external vision-language models for training trajectories, which means the whole system’s quality depends on those other models.

Jane: So while the framework is powerful for structured search and recovery, it’s not a magic fix yet because of those limitations regarding visual diversity and reliance on other AI systems for training.

Tom: Right, so VTS is a solid step forward because it makes self-correction learnable through explicit moves, but the next challenge is making that structure more robust to messy or boring video footage.

The paper's improvements: Tom: So, we’re looking at how they suggest improving this video tree search idea to make it even better than what they just built.

Jane: Right, so the paper points out that right now the system can only find one piece of evidence per question and it can't handle cases where the evidence is scattered across multiple separate moments in the video.

Tom: That’s a real limitation, and they are working on fixing that by making sure the search space isn't too rigid.

Jane: They also point out that their way of finding scene boundaries uses this CLIP thing, which they found can be less reliable when looking at videos that are visually very uniform, like a long stretch of sky or a plain wall.

Tom: And they’re dealing with the training setup too; right now the whole process depends on those external vision-language models for making captions and reasoning, which adds another layer of dependency.

Jane: So what do they suggest? They’re focused on making that tree structure more flexible so it can handle more complex evidence distributions, even when the video itself isn't super diverse.

Tom: Yeah, and they’re trying to get rid of those external dependencies by making the training pipeline more self-contained, which would be a huge win for production deployment if we want something stable.

Jane: It seems like they are pushing toward a system that can handle questions that require looking at several disconnected parts of the video, not just one single segment.

Tom: And what about the visual uniformity issue? They’re exploring ways to make those scene boundaries more resilient so it doesn't fail when things look really similar on screen.

Jane: It sounds like they are trying to build a more robust way for the AI to map out the video, so it can navigate those visually tricky parts without getting lost.

Tom: The big implication here is that if you want this kind of search agent to work in the real world, it needs to be able to handle a wider variety of video content than just the clean examples they used for training.

Jane: It means the future direction is about making that tree-grounded search structure more general and less dependent on perfectly distinct visual cues.

Tom: So we’re moving from just getting good results on specific benchmarks to building a system that can actually handle the messy, real-world videos we'll see out there.

Conclusion: Tom: So, to wrap things up, we’re talking about "Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA." The main point is that organizing a long video into a tree structure and giving the AI explicit moves like zoom out and shift makes it much better at finding evidence.

Jane: Exactly. It turns what used to be an implicit ability—just cropping—into something the AI can learn how to do intentionally, which helps it recover when it gets on the wrong path during its search.

Tom: And we saw that this approach beats prior agents and continuous cropping methods across all their tests, especially on the longest video benchmark by a big margin. The gains come from that tree structure itself, not just the base model.

Jane: It really shows how structuring the search over time can be a useful way to get better results for long horizon reasoning in video stuff.

Tom: Yeah, and it’s not just about finding evidence; they showed this framework helps with general video understanding too, beating other agents on tasks like Video-MME.

Jane: So what we’re seeing is that making the search explicit and structured gives the AI a real advantage in reasoning over long videos.

Lu: I think the core idea here is that hierarchical search provides a valuable inductive bias for handling long horizon video reasoning, which means we should probably start thinking about structuring our search space before we even think about what the base model can do.

Meng: From my side, it’s interesting that this framework outperforms multi-turn cropping agents and captioner models on those Grounded LVQA benchmarks by using the structure, not just a bigger brain. But I still have to wonder how much training data you need to get that segmentation right reliably.

Lalam: I’m confident in my assessment because the results are consistent across different tests, and this method clearly gives the AI a better way to explore information within a long video context.

Tom: True, but we have to remember they flagged some limitations, like how it handles evidence spread across multiple separate parts of the video or its reliance on external models for training trajectories.

Jane: So yeah, it’s powerful because it teaches the AI self-correction through these explicit moves in "Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA," but we need to keep working on making that structure more flexible and less dependent on other AI systems.

Lu: Exactly, the next challenge is moving from curated data to a system that can handle the messy, real-world videos we’ll see out there without needing perfect scene boundaries every time.

Meng: For us in production, it means we need to figure out how to make those scene boundaries more reliable so that when I deploy this, it doesn't just fail because the video is visually a little different from what it saw in training.

Lalam: I’m sure the research team will keep pushing on those generalization issues because that’s where the real performance gains are going to be if they can solve those problems.

Ce Zhang, Ziyang Wang, Yulu Pan, Oluwatumininu Oguntola, Pranav Wagh, Qiyu Wu, Hiromi Wakaki, Mohit Bansal

University of North Carolina at Chapel Hill · Sony

cs.CV

Submitted: 2026-07-17

Updated: 2026-11-06

Comments: Accepted to NeurIPS 2026

Code: https://github.com/CeeZh/VTS

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: 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.

Key concepts

VideoTreeSearch (VTS)
A framework that structures a long video into a hierarchy of semantically coherent segments called a tree. The agent navigates this tree using four discrete actions: zoom_in, zoom_out, shift, and answer. This organizes the search process.
Trajectory Synthesis
A training pipeline that generates multi-step paths through the video tree. It intentionally creates paths with deliberate detours into incorrect branches followed by recovery steps. This teaches the agent how to navigate mistakes explicitly.
Discrete Navigation Primitives
The specific, learnable actions (zoom_in, zoom_out, shift) used by the agent to move through the video tree. Unlike continuous methods, these are explicit behaviors that allow for clear backtracking and recovery from errors.
Adaptive Segmentation
The method used to build the temporal tree by detecting scene boundaries using CLIP-based techniques. This segmentation is adaptive, meaning it adjusts based on visual content, though it can be less reliable in visually uniform videos.

Terminology

Summary

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. p. 0

Where the paper says it

Wakaki}@sony. com 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.

Pruning redundant reasoning tokens

The paper proposes 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. p. 0

Where the paper says it

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.

The agent navigates this tree through four discrete operations: zoom in, zoom out, shift, and answer. p. 1
Where the paper says it

Concretely, VTS first constructs a non-uniform tree whose boundaries are derived from visual scene change points using CLIP [20] embeddings, so that each tree node corresponds to a semantically coherent segment. The agent then navigates this tree through four discrete operations: zoom_in to descend into a child segment, zoom_out to ascend to the parent, shift to move laterally to a sibling, and answer to commit.

These operations expose backtracking and recovery as explicit, learnable primitives rather than implicit behaviors. p. 0
Where the paper says it

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.

How the training signal is built

To train the agent to use these primitives effectively, a trajectory synthesis pipeline is introduced that produces multi-step paths through the tree. This pipeline produces trajectories that include deliberate detours into incorrect branches followed by recovery. p. 0

Where the paper says it

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.

These synthesized trajectories are used for supervised fine-tuning, followed by reinforcement learning with grounding and answer-accuracy rewards. p. 2
Where the paper says it

path trajectories and trajectories that deliberately enter incorrect branches before recovering through ascending and lateral moves. We use these synthesized trajectories for supervised fine-tuning to instill navigation and recovery patterns, followed by reinforcement learning with outcome-based rewards on grounding and answer accuracy.

The training involves a loss function where backpropagation is applied only through turns whose actions are themselves desirable as supervision — correct zoom in, zoom out from a wrong node, and shift from a wrong node to the correct sibling. p. 4
Where the paper says it

We optimize the standard token-level negative log-likelihood: LSFT = − X (Ot−1, Mt, Rt, At) ∈ DSFT log pθ(Rt, At | Ot−1, Mt, Q). (1) Crucially, we apply the loss selectively: although every trajectory is generated as an end-to-end sequence (including the deliberate wrong-branch detours that set up subsequent recovery turns), we backpropagate only through turns whose actions are themselves desirable as supervision — correct zoom_in, zoom_out from a wrong node, and shift from a wrong node to the correct sibling.

Where the gains come from

VTS substantially outperforms prior agentic methods across all three Grounded LVQA benchmarks. The largest gains are seen on the longest-video benchmark HaystackEgo4D. p. 2

Where the paper says it

We evaluate VTS on three Grounded LVQA benchmarks (CG-Bench [4], Haystack-LVBench [36], Haystack-Ego4D [36]) and three general long-video understanding benchmarks (Video-MME [9], MLVU [43], and LVBench [28]). VTS substantially outperforms prior agentic methods across all three Grounded LVQA benchmarks, with the largest gains on the longest-video benchmark HaystackEgo4D.

The performance gain is attributed to two components: hierarchical search across multiple temporal scales, and discrete navigation actions that make recovery from wrong branches explicit. p. 6
Where the paper says it

Despite this, VTS attains the best temporal grounding and QA accuracy among these methods. 2 Performance Gains Analysis We attribute VTS’s gains to two components: hierarchical search across multiple temporal scales, and discrete navigation actions that make recovery from wrong branches explicit.

Tree-grounded actions outperform continuous cropping by 1. p. 6
Where the paper says it

Table 3 reports three controlled experiments that isolate these ingredients. Tree-grounded actions outperform continuous cropping.

3–4.2 points on temporal grounding metrics and by up to 9. p. 6
Where the paper says it

Replacing the tree-grounded actions with a continuous crop_video action under the same data and recipe degrades performance by 1. 2 points on temporal grounding metrics and by up to 9.

8 points on QA accuracy. p. 0
Where the paper says it

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. p. 0

Where the paper says it

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.

Removing the backtracking primitives zoom out and shift from the tree-grounded action space degrades performance on every benchmark and metric. p. 6
Where the paper says it

Self-correction is critical. Removing the backtracking primitives zoom_out and shift from the tree-grounded action space degrades performance on every benchmark and metric.

General long-video understanding

VTS's 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. This suggests that tree-grounded search is a useful inductive bias beyond temporal grounding alone. p. 2

Where the paper says it

VTS surpasses the strongest prior agentic methods on Video-MME, MLVU, and LVBench by up to +7. 1 accuracy points, indicating that tree-grounded search is a useful inductive bias beyond temporal grounding alone.

VTS outperforms every multi-turn agentic baseline on all three general long-video QA benchmarks. p. 8
Where the paper says it

Accuracy (%) on Video-MME, MLVU, and LVBench, with frame counts for VTS averaged across the three. VTS outperforms every multi-turn agentic baseline on all three benchmarks.

Limitations and Future Work

VTS has several limitations, including the current action space produces a single evidence interval per question and cannot address questions whose evidence is distributed across multiple disjoint temporal regions. The adaptive segmentation relies on CLIP-based scene boundary detection and is less reliable on visually homogeneous video. p. 3

Where the paper says it

Turn ① zoom_in Turn ② zoom_in Turn ③ zoom_out Turn ④ shift Turn ⑤ zoom_in Turn ⑥ answer 00:00-35:46 00:00-12:48 12:48-17:31 00:00-04:42 04:42-12:48 12:48-16:00 16:00-17:31 00:00-03:31 03:31-04:42 17:31-35:46 Horse 16:32-16:40 Split boundary Non-leaf node Leaf node Figure 2: Overview of VideoTreeSearch (VTS). Left: Given a long video, VTS recursively partitions it into a non-uniform tree using CLIP-based scene boundaries, so each node corresponds to a semantically coherent segment.

Finally, trajectory synthesis depends on external vision-language and language models for captioning and reasoning. p. 2
Where the paper says it

We focus on Grounded LVQA [4, 36, 37], a more demanding setting in which the model must produce both an answer and the evidence interval that supports it. The grounding requirement makes predictions verifiable and prevents models from relying on language priors to answer correctly without attending to the relevant evidence.

Data Construction

The LongClueQA dataset is constructed from unlabeled long YouTube videos to serve as a training resource for evidence-seeking behavior required by VTS. The QA generation pipeline uses Qwen3-Next-80B-A3B-Thinking as the question generation model. p. 4

Where the paper says it

We focus on examples with a single ground-truth clue spanning at most 20% of the video duration. Full filtering and trajectory generation details are in the Appendix.

Qualitative Analysis

Figure 8 illustrates a deeper nine-turn trajectory that uses both backtracking primitives. This shows how zoom out and shift work together to recover from incorrect exploration. p. 4

Where the paper says it

A single zoom_in action descends one level rather than committing to a specific timestamp range, so reaching a fine-grained evidence interval naturally takes multiple turns of progressive narrowing. Exploration and self-correction are decoupled: zoom_in advances the search downward, while zoom_out and shift are dedicated mechanisms for abandoning an incorrect branch.

The agent first follows several zoom in steps into an incorrect branch that shows the man but no turkeys (turns 1–6). p. 3
Where the paper says it

Right: The agent navigates the tree through four discrete actions— zoom_in to descend into a child, zoom_out to ascend to the parent, shift to move laterally to a sibling, and answer to terminate with a final answer and evidence interval. In this example, the agent first descends into a wrong branch (red, turns 1–2), recovers via zoom_out and shift (turns 3–4), then zooms into the correct branch (turn 5) and answers with the localized clue at 16:32–16:40 (turn 6).

It then recovers by using zoom out to return to the parent node, followed by shift to move laterally to an unvisited sibling. p. 1
Where the paper says it

Concretely, VTS first constructs a non-uniform tree whose boundaries are derived from visual scene change points using CLIP [20] embeddings, so that each tree node corresponds to a semantically coherent segment. The agent then navigates this tree through four discrete operations: zoom_in to descend into a child segment, zoom_out to ascend to the parent, shift to move laterally to a sibling, and answer to commit.

The example shows zoom out as an explicit recovery action after the agent commits to a wrong branch. p. 9
Where the paper says it

It detects the error, issues zoom_out to return to the parent (turn 4), and explores a different child to reach the correct clue (turns 5–6). The example shows zoom_out as an explicit recovery action after the agent commits to a wrong branch.

Conclusion

VTS organizes the video as a tree of semantically coherent segments and navigates it with discrete actions, which turns precise localization and backtracking from implicit capabilities into explicitly learnable behaviors. More broadly, our results suggest that structuring the search over a long video is a useful inductive bias for long-horizon video reasoning. p. 9

Where the paper says it

On three grounded long-video QA benchmarks, VTS substantially outperforms prior multi-turn cropping agents and captioner-LLM baselines, and it transfers to three general longvideo understanding benchmarks while being more efficient. More broadly, our results suggest that structuring the search over a long video is a useful inductive bias for long-horizon video reasoning.

The framework shows that VTS outperforms prior multi-turn cropping agents and captioner-LLM baselines on Grounded LVQA benchmarks. p. 9
Where the paper says it

VTS organizes the video as a tree of semantically coherent segments and navigates it with discrete actions, which turns precise localization and backtracking from implicit capabilities into explicitly learnable behaviors. On three grounded long-video QA benchmarks, VTS substantially outperforms prior multi-turn cropping agents and captioner-LLM baselines, and it transfers to three general longvideo understanding benchmarks while being more efficient.

The gains stem from the framework rather than the base model, and a stronger backbone adds further gains. p. 8
Where the paper says it

8 accuracy on Haystack-Ego4D. The gains therefore stem from the framework rather than the base model, and a stronger backbone adds further gains.

p. 8
Where the paper says it

8 accuracy on Haystack-Ego4D. The gains therefore stem from the framework rather than the base model, and a stronger backbone adds further gains.

p. 8
Where the paper says it

8 accuracy on Haystack-Ego4D. The gains therefore stem from the framework rather than the base model, and a stronger backbone adds further gains.

Ablation Studies

Adaptive splitting outperforms uniform splitting by 1.2 mIoU at 4 children. p. 7

Where the paper says it

Highlighted rows denote the default VTS. Variant mIoU Acc Tree construction Uniform splitting, 4 children 15.

Training on trajectories with deliberate detours and recovery outperforms training on optimal-path-only trajectories by +6. p. 7
Where the paper says it

Trajectory synthesis. Table 4 shows that training on trajectories with deliberate detours and recovery outperforms training on optimal-path-only trajectories by +6.

4 mIoU and +5. p. 0
Where the paper says it

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.

1 accuracy. p. 0
Where the paper says it

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.

The hierarchical tree supports a wide range of clue durations. p. 7
Where the paper says it

5 Hierarchical search supports a wide range of clue durations. Replacing the hierarchical tree with a flat tree of uniform short segments degrades QA accuracy by 1.

Replacing the hierarchical tree with a flat tree of uniform short segments degrades QA accuracy by 1. p. 7
Where the paper says it

5 Hierarchical search supports a wide range of clue durations. Replacing the hierarchical tree with a flat tree of uniform short segments degrades QA accuracy by 1.

9-5.1 points on all datasets. p. 6
Where the paper says it

Specifically, temporal grounding drops by 2. 9 points on all datasets while QA accuracy drops by 1.

The gains stem from the framework rather than the base model, and a stronger backbone adds further gains.

Backbone generalization

VTS outperforms prior multi-turn cropping agents on every benchmark when using the same Qwen2.5-VL-7B backbone. p. 6

Where the paper says it

7 mIoU and +4. 6 accuracy on CG-Bench while using a smaller open-source backbone.

Under this matched-backbone setting, VTS improves over the strongest Qwen2. p. 8
Where the paper says it

5-VL-7B, the backbone used by prior multi-turn cropping agents. Under this matched-backbone setting (Table 6), VTS improves over the strongest Qwen2.

5-VL-7B cropping baseline by +10. p. 6
Where the paper says it

1 Main Results on Grounded Long-Video Question Answering Table 1 reports results on the three Grounded LVQA benchmarks. VTS substantially outperforms every multi-turn cropping baseline.

2 mIoU and +13. p. 0
Where the paper says it

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.

3 accuracy on CG-Bench. p. 0
Where the paper says it

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.

The gains therefore stem from the framework rather than the base model, and a stronger backbone adds further gains. p. 8
Where the paper says it

8 accuracy on Haystack-Ego4D. The gains therefore stem from the framework rather than the base model, and a stronger backbone adds further gains.

Evaluation Benchmarks

The evaluation includes three Grounded LVQA benchmarks: CG-Bench [4], Haystack-LVBench [36], and Haystack-Ego4D [36].

The LongClueQA dataset is constructed from unlabeled long YouTube videos to serve as a training resource for evidence-seeking behavior required by VTS. The data collection involves filtering videos based on visual diversity scores derived from CLIP embeddings. p. 1

Where the paper says it

Our key insight is that organizing the video as a tree of semantically coherent segments, and letting the agent navigate that tree through discrete actions, turns precise localization and backtracking from implicit capabilities into explicitly learnable behaviors. Concretely, VTS first constructs a non-uniform tree whose boundaries are derived from visual scene change points using CLIP [20] embeddings, so that each tree node corresponds to a semantically coherent segment.

VTS substantially outperforms every multi-turn cropping baseline. It is suggested that structuring the search over a long video is a useful inductive bias for long-horizon video reasoning. p. 9

Where the paper says it

On three grounded long-video QA benchmarks, VTS substantially outperforms prior multi-turn cropping agents and captioner-LLM baselines, and it transfers to three general longvideo understanding benchmarks while being more efficient. More broadly, our results suggest that structuring the search over a long video is a useful inductive bias for long-horizon video reasoning.

VTS substantially outperforms prior multi-turn cropping agents and captioner-LLM baselines on Grounded LVQA benchmarks. p. 9
Where the paper says it

VTS organizes the video as a tree of semantically coherent segments and navigates it with discrete actions, which turns precise localization and backtracking from implicit capabilities into explicitly learnable behaviors. On three grounded long-video QA benchmarks, VTS substantially outperforms prior multi-turn cropping agents and captioner-LLM baselines, and it transfers to three general longvideo understanding benchmarks while being more efficient.

The framework shows that VTS outperforms every multi-turn agentic baseline on all three general long-video QA benchmarks. p. 8
Where the paper says it

Accuracy (%) on Video-MME, MLVU, and LVBench, with frame counts for VTS averaged across the three. VTS outperforms every multi-turn agentic baseline on all three benchmarks.

The gains stem from the framework rather than the base model, and a stronger backbone adds further gains.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

1

Improved AI system can perform grounded long-video question answering by organizing video as a tree of semantically coherent segments and navigating it with discrete actions (zoom in, zoom out, shift, answer). This turns precise localization and backtracking from implicit capabilities into explicitly learnable behaviors.

2

The system can utilize trajectory synthesis to train agents on deliberate detours into incorrect branches followed by recovery, instilling navigation and recovery patterns through supervised fine-tuning. This allows the agent to learn how to recover from mistakes by applying the inverse of the action sequence that led into a wrong branch.

3

The agent can exhibit self-correction by using zoom out and shift as dedicated mechanisms for fine-to-coarse backtracking and moving laterally, which is explicitly learned rather than implicit. This results in VTS selfcorrecting in roughly 60% of trajectories on all three benchmarks compared to only 7-15% for the continuous-cropping baseline.

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 through adaptive temporal segmentation 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 multi-turn cropping agents 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 multi-turn cropping agents 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: removing either adaptive descent or explicit backtracking substantially degrades performance.

Sources

Related papers