PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Tree of Thought: Reasoning-Guided Visual Cue Search for Long-Video Understanding

Ziling Huang, Shin'ichi Satoh

arXiv:2608.27871v1cs.CV

TL;DR

Long-video MLLMs face context limits and may miss temporally organized evidence. T^3 addresses this with a reusable hierarchical temporal tree and adaptive answer–retrieve–explore reasoning, improving Qwen2.5-VL-7B across three benchmarks under the same frame budget.

  • Problem

    Long-video MLLMs are constrained by limited context length, while independent or uniform frame inspection can overlook temporally organized evidence.

  • Method

    T^3 constructs a question-agnostic hierarchical temporal tree of contiguous segments and adaptively explores relevant branches through an answer–retrieve–explore loop.

  • Results

    0.5%, 4.6%, and 4.4% accuracy gains over Qwen2.5-VL-7B were reported on VideoMME, LongVideoBench, and LVBench, respectively, under the same frame budget.

  • Takeaways & Limitations

    A reusable temporal tree combined with multi-round reasoning offers an effective direction for long-video understanding with MLLMs.

  • Takeaways & Limitations

    The temporal tree uses only visual features and a single visual representative frame per segment, potentially missing semantic transitions and motion cues.

Abstract

from arXiv · show

Long-video understanding remains challenging for Multimodal Large Language Models (MLLMs) due to limited context length. Uniform sampling may miss crucial moments, while agent-based frame video understanding methods often evaluate frames independently, overlooking the temporal organization of videos. Ideally, evidence selection should mimic how humans answer questions about long videos: first locating the relevant segment from the global context, then zooming into local objects and details. We propose Temporal Tree of Thought T^3, a training-free framework for adaptive coarse-to-fine long-video understanding. T^3 constructs a question-agnostic hierarchical temporal tree via recursive temporally constrained clustering, where each node represents a contiguous segment with an informative key frame. During inference, T^3 performs an answer-retrieve-explore loop: it reasons over coarse representative frames, generates a search statement when evidence is insufficient, and expands relevant branches for finer-grained evidence. This process adaptively shifts the search target from temporal regions to specific objects and visual details to help video understanding. Experiments on VideoMME, LongVideoBench, and LVBench show that T^3 improves Qwen2.5-VL-7B by 0.5%, 4.6%, and 4.4%, respectively, under the same frame budget, demonstrating the effectiveness of structured temporal reasoning.

1 Introduction

T^3 addresses long-video context limits by organizing videos into reusable temporal structure and progressively searching from relevant segments to fine-grained evidence. It is a training-free framework evaluated on three long-video QA benchmarks.

  • Motivation: Long videos can exceed current MLLM context budgets, making exhaustive frame encoding computationally prohibitive.A 30-minute video can produce over 400K visual tokens.
  • Motivation: Human-like evidence search first locates a relevant temporal segment, then focuses on objects and visual details before integrating evidence.The search target shifts from temporal regions at a coarse stage to specific visual evidence at a finer stage.
  • Contribution: T^3 introduces a training-free framework for long-video understanding.The framework organizes videos into a query-agnostic temporal tree and performs structured reasoning over it.
  • Results: 0.5%, 4.6%, and 4.4% accuracy gains over Qwen2.5-VL-7B were obtained on VideoMME, LongVideoBench, and LVBench, respectively.The evaluation used the same frame budget across the reported comparisons.
  • Contribution: Recursive temporally constrained clustering organizes videos into coarse-to-fine contiguous segments, creating a compact yet expandable representation.Each segment is represented by an informative frame, and relevant branches can be expanded during reasoning.
  • Contribution: T^3 uses an answer–retrieve–explore loop to reason over coarse frames, generate search statements when evidence is insufficient, and refine relevant branches.The process can continue for further refinement until sufficient evidence is collected or the round limit is reached.

2 Related Works

Prior work uses interactive agents, hierarchical video representations, and structured reasoning, but T^3 combines a reusable temporally constrained tree with evidence-driven search refinement.

  • Agent-based methods: Agent-based methods treat long-video understanding as interactive reasoning and may use retrieval, verification, or specialized roles across multiple rounds.VideoAgent retrieves captions or objects and verifies answers, while VideoMind uses planner, grounder, verifier, and answerer roles.
  • Tree-based methods: VideoTree builds a query-adaptive tree for each question, whereas T^3 builds a reusable question-agnostic tree with contiguous temporally constrained segments.T^3 preserves chronological structure in each node rather than clustering solely in relation to the query.
  • T^3 distinction: T^3 performs goal-directed search over a structured temporal tree instead of repeatedly querying the entire video with the original question.Its search statement updates with current evidence and tentative answers, shifting retrieval from temporal regions toward objects and visual details.
  • Structured reasoning: Chain-of-Thought and self-consistency support multi-step reasoning, while Tree-of-Thought structures search over intermediate states with look-ahead and backtracking.These methods provide broader reasoning precedents for structured multi-step inference.

3 Temporal Tree of Thought

T^3 first constructs a hierarchical temporal tree from cached visual features, then performs adaptive multi-round reasoning over representative frames. Low confidence triggers search-query generation and selective branch expansion.

  • Problem setup: T^3 studies training-free multiple-choice question answering on long videos with MLLMs.The video is represented as frames, with a question and candidate answer options.
  • Temporal tree construction: A frozen CLIP image encoder extracts visual features once and caches them for query-agnostic indexing and retrieval.The features represent densely sampled video frames and keep indexing training-free.
  • Temporal tree construction: Recursive temporal clustering partitions the timeline into contiguous segments, each represented by the frame closest to its cluster center.The resulting hierarchy provides coarse summaries at higher levels and finer access at deeper levels.
  • Initial reasoning: Inference begins with representative frames from the first layer, which provide global timeline coverage without directly scoring every frame.The active set is refined only when current evidence is insufficient.
  • Multi-round reasoning: The MLLM predicts an answer and confidence from the active representative frames, terminating early when confidence exceeds the threshold.Otherwise, the method proceeds to gather additional visual evidence.
  • Guided retrieval: When evidence is insufficient, the MLLM generates a search sentence, CLIP scores it against active frames, and similar representatives are selected for exploration.The selected parents are replaced by their children, allowing relevant regions to be examined at finer temporal resolution.
  • Selective exploration: If a cue is absent from current representatives, the ratio rule broadens expansion across multiple finer branches until evidence emerges or the round limit is reached.This supports adaptive widening when similarities are uniformly low.
  • Multi-round reasoning: Multi-round reasoning repeats prediction, retrieval, and selective expansion until confidence is sufficient or Tmax is reached while maintaining timeline coverage.The active set can drill into promising regions or explore other related story regions.

4 Experiments

Across three long-video QA benchmarks, T^3 is evaluated with different backbones, frame budgets, and ablations, showing consistent gains and benefits from structured, adaptive multi-round reasoning.

  • Experimental Setup: The evaluation covers VideoMME, LongVideoBench, and LVBench, including extremely long videos averaging approximately 4,101 seconds on LVBench.Experiments use Qwen2.5-VL-7B and LLaVA-Video-7B; prior methods retain their original reported settings.
  • Main Results: T^3-Q improves Qwen2.5-VL-7B by +0.5 on VideoMME, +4.6 on LongVideoBench, and +4.4 on LVBench.The reported gains are 65.4 versus 64.9, 60.6 versus 56.0, and 46.4 versus 42.0, respectively.
  • Main Results: On VideoMME’s 30–60 minute subset, T^3-Q improves from 53.9 to 55.3 (+1.4), exceeding its +0.5 overall gain.The paper attributes the smaller overall gain partly to shorter videos having denser coverage from uniform sampling and to questions requiring global understanding.
  • Main Results: On LongVideoBench, T^3 remains competitive despite using far fewer frames than densely sampled models such as Vamba with 1024 frames.LongVideoBench emphasizes temporally localized evidence, with relevant evidence described as sparse and dispersed across the timeline.
  • Ablation Studies: Structure-aware representation adds around +1.11 overall over uniform sampling, while adaptive expansion adds +1.29 over reasoning-guided retrieval and +3.51 over uniform sampling.The ablation incrementally evaluates structure-aware representation, question-guided retrieval, reasoning-guided retrieval, and ratio-based adaptive expansion.
  • Ablation Studies: Non-structured and non-temporally constrained variants underperform the full structure-aware setting, supporting contiguous temporal organization for hierarchical reasoning.The paper links the temporal constraint to avoiding confusion between visually similar but temporally distant events or contexts.
  • Ablation Studies: On LVBench, 87.8% of annotated questions proceed beyond one round, 46.3% of multi-round cases improve target coverage, and accuracy rises from 250 to 314 correct samples by Round 5.Late-hit cases account for 22.0% of multi-round cases, while the net accuracy gain is +4.2 points overall and +25.6% relative to Round 1.
  • Ablation Studies: A qualitative LVBench example shows retrieval shifting from an initial advanced-robotics hypothesis to an AI-and-societal-impact search, reaching hit count 93 in Round 3.The example illustrates retaining distributed active branches, revising the search cue, and recovering missing evidence across rounds.

5 Conclusion

T^3 organizes each video into a query-agnostic temporal tree and performs multi-round online reasoning that selectively explores relevant regions. Across three benchmarks, it consistently improves long-video question answering, with ablations supporting temporal representation and adaptive expansion.

  • 5 Conclusion: T^3 combines a reusable query-agnostic temporal tree with multi-round online reasoning over video evidence.The model starts from coarse representative frames, identifies missing evidence, and selectively explores relevant temporal regions.
  • 5 Conclusion: T^3 decouples temporal tree construction from question-specific reasoning, allowing the constructed tree to be reused across questions.
  • 5 Conclusion: T^3 consistently improves long-video question answering on VideoMME, LongVideoBench, and LVBench.
  • 5 Conclusion: Ablations support the contributions of temporal representation and adaptive expansion.

6 Limitations

T^3 remains limited by its visual-only temporal construction and single-frame segment representation. Its lightweight CLIP-based retrieval can also under-represent motion patterns and temporal relations.

  • 6 Limitations: The temporal tree uses only visual features and excludes subtitles, audio, and ASR transcripts.Multimodal cues could better align segment boundaries with semantic transitions, especially in dialogue-heavy or audio-centric videos.
  • 6 Limitations: Representing each temporal segment with one visual frame may miss motion cues within the segment.The paper suggests richer segment-level summaries, including compact textual descriptions, as an extension.
  • 6 Limitations: CLIP image-text similarity between generated search statements and representative frames may under-represent motion patterns and temporal relations.The retrieval design is lightweight and efficient but is constrained by single-frame evidence.

A.4 Task-Type Analysis

On VideoMME with LLaVA-Video-7B, T^3 improves most reasoning-intensive and temporally grounded task categories. It also preserves some global-context performance, while showing slight declines on several perception-oriented categories.

  • A.4 Task-Type Analysis: T^3 improves Counting Problem, Object Reasoning, Action Recognition, Temporal Reasoning, and Spatial Reasoning over the baseline.These categories require progressively localizing relevant evidence and refining focus toward fine-grained content.
  • A.4 Task-Type Analysis: T^3 also improves Information Synopsis and Spatial Perception, indicating that coarse-to-fine search can preserve global context while retrieving local evidence.
  • A.4 Task-Type Analysis: T^3 performs comparably on Temporal Perception but shows slight drops on Object Recognition, Attribute Perception, and OCR Problems.The paper relates these categories to whether the key visual cue is already visible in sampled frames.
  • A.4 Task-Type Analysis: Overall, T^3 is most beneficial for reasoning-heavy and temporally grounded questions.This pattern aligns with the framework’s use of structured temporal search for long-video understanding.

A.5 Runtime Analysis

T^3 adds one-time temporal-tree construction while keeping per-question online cost moderate, making reuse increasingly valuable across multiple questions. Early stopping and reusable structure limit repeated computation during inference.

  • A.5 Runtime Analysis: T^3-Q costs 11.4 sec/min-video offline and 4.34 sec/min-video online per question, versus 3.03 sec/min-video for the Qwen2.5-VL baseline.The offline tree construction is paid once per video.
  • A.5 Runtime Analysis: For M questions, T^3’s total runtime is TT^3-ours(M) = 11.4 + 4.34M.This expresses one-time offline preprocessing plus per-question online inference.
  • A.5 Runtime Analysis: T^3-Q adds 1.31 sec/min-video per question over the baseline, increasing online cost from 3.03 to 4.34 sec/min-video.The added time comes from extra evidence-retrieval rounds, while confident predictions can terminate early.
  • A.5 Runtime Analysis: Rebuilding temporal structure for each question raises online cost to 7.66 sec/min-video compared with 4.34 sec/min-video for T^3-Q.This comparison highlights repeated computation when temporal clustering is not reusable.

A.6 Video Length on Early Stopping.

T^3 requires more reasoning rounds as video length increases, reflecting the need to broaden temporal search and refine subtle visual evidence before answering.

  • 46% of short-video samples terminate after round 1, while 29% of medium-video samples stop after round 1.The remaining 54% of short-video samples enter later rounds for additional verification.
  • 72% of long-video samples require three rounds to reach a confident answer.Longer videos make early termination less frequent than in short and medium videos.
  • Additional rounds broaden and re-check temporal regions when decisive cues are brief or easy to miss.This addresses failures caused by insufficient coverage at a broad glance.
  • Further refinement is needed when a plausible region has been found but the answer depends on subtle visual details.The search zooms into the selected region before commitment.
  • Round 2 often consolidates evidence without reaching high confidence, causing some samples to proceed to round 3 for decisive evidence.New cues can weaken or revise an initially plausible answer from round 1.

A.7 Choice of the Early Stopping Threshold.

The stopping threshold is calibrated from confidence–accuracy curves and tested in an ablation, with τ = 0.9 selected as a conservative trigger for further exploration.

  • Accuracy increases monotonically as τ becomes stricter, with the strongest gains between 0.6 and 0.9.The analysis uses Qwen2.5-VL-7B with 128 uniformly sampled frames across three datasets.
  • τ = 0.9 is selected because it preserves most achievable accuracy while avoiding unnecessary expansions.The threshold is based on dataset-level confidence–accuracy analysis.
  • 65.4 accuracy is achieved at τ = 0.9 on VideoMME, compared with 63.2 at τ = 0.3 and 65.1 at τ = 0.6.The ablation uses Qwen2.5-VL-7B with T^3 on VideoMME.

A.8.1 Effect of First-Layer Segments K1.

First-layer granularity creates a coarse-to-fine trade-off: finer partitions improve early coverage, while coarser partitions require more rounds but can provide steadier later gains.

  • Effect of First-Layer Segments K1: K1 = 64 peaks at 65.93 in Round 2, providing the strongest early performance.The setting uses K>1 = 4 and ρ = 0.75.
  • Effect of First-Layer Segments K1: K1 = 32 peaks at 65.41 in Rounds 2–3, while K1 = 16 peaks at 64.67 in Round 5.Reducing first-layer granularity shifts the peak to later rounds and lowers it slightly.
  • Effect of First-Layer Segments K1: Larger K1 improves early coverage but can cause more subsampling and diminishing returns under a fixed per-round frame budget.Smaller K1 starts coarser and needs additional refinement to reach comparable evidence.
  • Effect of First-Layer Segments K1: A moderate deeper-layer branching factor K>1 = 4 performs best, peaking at Round 2 with K1 = 64 and Round 5 with K1 = 16.The later peak for K1 = 16 reflects the additional refinement needed after a coarser start.
  • Effect of First-Layer Segments K1: ρ ≈ 0.75 balances complementary-region coverage against over-expansion, though the best strictness depends on K1.With K1 = 64, ρ = 0.75 reaches 65.93 in Round 2; with K1 = 16, ρ = 0.70 peaks at 65.15 in Round 4.

B Failure Cases Analysis

The failure analysis identifies retrieval and reasoning errors on LVBench, while the supporting implementation materials describe temporal segmentation and option-probability extraction procedures.

  • Failure modes: Among 815 incorrect LVBench predictions, 465 (57.1%) are found_incorrect and 350 (42.9%) are notfound_incorrect.The former retrieves relevant segments but answers incorrectly; the latter never retrieves the required evidence.
  • Failure modes: found_incorrect cases often involve hallucinations or insufficiently discriminative evidence within the retrieved context.Retrieval alone does not guarantee a correct answer.
  • Failure modes: notfound_incorrect errors are strongly associated with sparse evidence in videos averaging 4,101 seconds, where decisive cues may occupy only a few frames.Extreme temporal sparsity can remain difficult even with multi-round reasoning.
  • Implementation: Temporal clustering divides a frame-feature sequence into K contiguous, non-overlapping segments satisfying a minimum length while minimizing total within-segment SSE.The algorithm then computes a mean feature vector for each subsegment as its cluster center.
  • Implementation: The option-probability procedure maps A–D to tokenizer IDs, gathers first-token logits, and applies softmax over valid options.It returns None when scores or corresponding token IDs are unavailable.
Loading 2608.27871v1…