Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA
summary
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.
In short
VideoTreeSearch (VTS) frames grounded long-video question answering as searching a temporal tree built from visual scene boundaries. The agent uses discrete actions like zoom_in, zoom_out, and shift to navigate this tree. By training on trajectories that include deliberate detours and recovery, VTS learns explicit backtracking, leading to superior performance across long-video QA benchmarks.
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 used across episodes
This episode discusses
- Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA · Paper Radio
- Qwen3-VL Technical Report
- VideoMiner: Iteratively Grounding Key Frames of Hour-Long Videos via Tree-based Group Relative Policy Optimization
- LongVILA: Scaling Long-Context Visual Language Models for Long Videos
- VideoZoomer: Reinforcement-Learned Temporal Focusing for Long Video Reasoning
- Video-R1: Reinforcing Video Reasoning in MLLMs
- VideoChat-R1: Enhancing Spatio-Temporal Perception via Reinforcement Fine-Tuning
- TimeSearch-R: Adaptive Temporal Search for Long-Form Video Understanding via Self-Verification Reinforcement Learning
- Too Many Frames, Not All Useful: Efficient Strategies for Long-Form Video QA
- xGen-MM-Vid (BLIP-3-Video): You Only Need 32 Tokens to Represent a Video Even in VLMs
- LongVU: Spatiotemporal Adaptive Compression for Long Video-Language Understanding
- VideoITG: Multimodal Video Understanding with Instructed Temporal Grounding
- LVBench: An Extreme Long Video Understanding Benchmark
- AdaReTaKe: Adaptive Redundancy Reduction to Perceive Longer for Video-language Understanding
- Time-R1: Post-Training Large Vision Language Model for Temporal Video Grounding
- Active Video Perception: Iterative Evidence Seeking for Agentic Long Video Understanding
- LongVT: Incentivizing "Thinking with Long Videos" via Native Tool Calling
- Generative Frame Sampler for Long Video Understanding
- T*: Re-thinking Temporal Search for Long-Form Video Understanding
- MomentSeeker: A Task-Oriented Benchmark For Long-Video Moment Retrieval
- Video-o3: Native Interleaved Clue Seeking for Long Video Multi-Hop Reasoning
The paper
Searching Videos as Trees: Self-Correcting Agents for Grounded Long Video QA · Read on arXiv
Ce Zhang, Ziyang Wang, Yulu Pan, Oluwatumininu Oguntola, Pranav Wagh, Qiyu Wu, Hiromi Wakaki, Mohit Bansal
University of North Carolina at Chapel Hill · Sony
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.
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.
More episodes
- 2603.28113-The multiplicative Lipschitz bound as an inductive bias
- 2603.28595-Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes
- 2603.29765-Training-Free Dynamic Upcycling of Expert Language Models
- 2605.00778-Observable Performance Does Not Fully Reflect Adaptive System Organization: A Multi-Level Analysis of Gait Dynamics Under Occlusal Constraint
- 2605.06906-TraXion: Rethinking Pre-training Frameworks for Mobility and Beyond
- 2605.09165-Sparse Layers are Critical to Scaling Looped Language Models
- 2605.09439-Inverse Design for Conditional Distribution Matching
- 2605.10313-Signature Approach for Contextual Bandits with Nonlinear and Path-dependent Rewards: Regret Bound and Statistical Inference
- 2605.10878-Minimum Neural Weight Norm = Kolmogorov Complexity
- 2605.11617-MIST: Reliable Streaming Decision Trees for Online Class-Incremental Learning via McDiarmid Bound