PaperlayerView exact revision on arXiv

Source-linked AI summary

VideoTree: Adaptive Tree-based Video Representation for LLM Reasoning on Long Videos

Ziyang Wang, Shoubin Yu, Elias Stengel-Eskin, Jaehong Yoon, Feng Cheng, Gedas Bertasius, Mohit Bansal

arXiv:2405.19209v3cs.CVcs.AIcs.CL

TL;DR

Long-form video reasoning faces redundancy, irrelevant content, and missing hierarchical structure. VideoTree builds a query-adaptive tree through iterative relevance-guided keyframe selection and coarse-to-fine expansion, then uses an LLM for reasoning. It reports improved accuracy and efficiency across long-video benchmarks, including better performance than GPT-4V on Video-MME’s long split.

  • Problem

    Redundant, query-irrelevant video content and unstructured caption lists hinder efficient and detailed LLM reasoning over long videos.

  • Method

    VideoTree is a training-free framework that iteratively selects query-relevant keyframes and organizes multi-granularity information in a hierarchical tree for LLM reasoning.

  • Results

    VideoTree improves accuracy and efficiency across EgoSchema, NExT-QA, and Video-MME, achieving better performance than GPT-4V on Video-MME’s long split.

  • Takeaways & Limitations

    The framework supports efficient LLM reasoning over long-form videos by allocating more detail to query-relevant regions and less to irrelevant ones.

  • Takeaways & Limitations

    Performance remains limited by the captioner’s ability to accurately capture sampled-frame contents.

Abstract

from arXiv · show

Long-form video understanding is complicated by the high redundancy of video data and the abundance of query-irrelevant information. To tackle these challenges, we propose VideoTree, a training-free framework which builds a query-adaptive and hierarchical video representation for LLM reasoning over long-form videos. First, VideoTree extracts query-relevant information from the input video through an iterative process, progressively refining the selection of keyframes based on their relevance to the query. Furthermore, VideoTree leverages the inherent hierarchical structure of long video data, which is often overlooked by existing LLM-based methods. Specifically, we incorporate multi-granularity information into a tree-based representation, allowing VideoTree to extract query-relevant details from long videos in a coarse-to-fine manner. This enables the model to effectively handle a wide range of video queries with varying levels of detail. Finally, VideoTree aggregates the hierarchical query-relevant information within the tree structure and feeds it into an LLM reasoning model to answer the query. Our experiments show that our method improves both reasoning accuracy and efficiency. Specifically, VideoTree outperforms existing training-free approaches on EgoSchema and NExT-QA with less inference time, achieving 61.1% and 75.6% accuracy on the test set without additional video-specific training. Moreover, on the long split of Video-MME (average 44 minutes), VideoTree achieves better performance than GPT-4V and many other MLLMs that were extensively trained on video data.

1. Introduction

Long-form video reasoning is hindered by redundant, query-irrelevant information and by representations that omit videos’ coarse-to-fine structure. VIDEOTREE addresses both issues with adaptive hierarchical keyframe selection and improves accuracy and efficiency across long-video benchmarks.

  • Redundant and irrelevant content can overwhelm LLMs, causing reasoning mistakes and reduced efficiency.
  • Unstructured caption lists overlook hierarchical video information, causing missed details in dense regions that require fine-grained temporal understanding.
  • VIDEOTREE adaptively extracts query-relevant keyframes in a coarse-to-fine manner and organizes them in a hierarchical tree.
  • Iterative clustering, captioning, and relevance scoring selects sparse keyframes, improving inference efficiency and reducing irrelevant information for reasoning.
  • 2.1% and 4.3% improvements were achieved on EgoSchema subset and NExT-QA validation, respectively, with less inference time or LLM calls.
  • VIDEOTREE performed better than GPT-4V on Video-MME’s long split and improved 4.8% against LangRepo with open-source LLMs.

2. Related Work

Prior work explores structured video representations and LLM-based video understanding, while VIDEOTREE combines adaptive coarse-to-fine extraction with agent-based reasoning and a human-readable tree.

  • Structured video-language methods represent frames across different temporal scales to support compact and efficient scene-context recognition.
  • LLM-based video understanding methods connect visual encoders to LLMs or use caption-centric information for video-related tasks.
  • VIDEOTREE adaptively extracts key information in a coarse-to-fine manner and improves interpretability through a human-readable tree of visual clues.

3. VIDEOTREE Method

VIDEOTREE constructs a query-adaptive tree by clustering and scoring video content, expanding relevant regions to finer levels, then temporally ordering captions for LLM reasoning.

  • VIDEOTREE uses adaptive breadth expansion, relevance-guided depth expansion, and LLM video reasoning to build a query-adaptive hierarchical representation.
  • Adaptive Breadth Expansion: Visual clustering groups semantically similar frames, reducing redundancy by summarizing n frames into k representative clusters and keyframes.
  • Adaptive Breadth Expansion: The K-Means operation maps frame features into k clusters and centroid vectors.
  • Adaptive Breadth Expansion: Cluster captioning converts representative keyframes or short clips into textual descriptions using a VLM-based captioner.
  • Adaptive Breadth Expansion: The LLM assigns each cluster a relevance score of 1, 2, or 3, and iteration stops when enough highly relevant clusters are found or max_breadth is reached.
  • LLM Video Reasoning: Selected tree nodes are captioned and sorted temporally into a textual video description for the LLM.
  • Relevance-guided Depth Expansion: High-relevance clusters are sub-clustered into deeper levels, allocating more granular information according to top-level relevance.

4. Experimental Setup

VIDEOTREE is evaluated on three long-form video question-answering benchmarks using multiple-choice accuracy, with GPT-4 as the main reasoning model and benchmark-specific video processing settings.

  • Tasks & Datasets: The evaluation covers EgoSchema, NExT-QA, and Video-MME, including Video-MME’s 30–60-minute long-video split.
  • Implementation Details: GPT-4 is used as the LLM, with EVA-CLIP-8B as visual encoder and CogAgent or LaViLa as benchmark-specific captioners.
  • Implementation Details: Videos are sampled at 1 FPS for EgoSchema and NExT-QA and 0.125 FPS for Video-MME; best average caption counts are 62.4, 12.6, and 128, respectively.
  • Evaluation Metrics: All datasets use multiple-choice question answering evaluated with standard accuracy metrics.

5. Results

VIDEOTREE consistently improves the efficiency-effectiveness trade-off over training-free and same-category baselines, while its hierarchical and adaptive components contribute to performance across settings.

  • VIDEOTREE outperforms existing training-free approaches on all evaluation metrics across EgoSchema and NExT-QA.
  • Efficiency-Effectiveness Analysis: 2.4% improvement on the EgoSchema subset is achieved by VIDEOTREE-fast using only 33% of LLoVi’s time cost.The best VIDEOTREE model achieves a 5.0% improvement with less overall inference time than the compared baseline.
  • Ablation Study: 6.5% and 2.0% average-accuracy gains over LLoVi and VideoAgent occur under similar frame-caption settings.The comparison uses settings with 7, 9, and 11 average frame captions.
  • Open-source LLM Reasoner: 2.2% and 4.8% better EgoSchema-subset performance are obtained with Mistral 7B and 12B while using substantially less inference time.VIDEOTREE uses only 20% of the frame captions, with approximately 72.5% and 69.0% less inference time than LangRepo on the two models.
  • VIDEOTREE Components: 1.8% and 3.2% performance decreases follow removal of depth expansion and adaptive breadth expansion, respectively.These ablations support contributions from both hierarchical and adaptive design choices.
  • Qualitative Analysis: Qualitative examples show VIDEOTREE selecting query-relevant key scenes and details where uniformly sampled frames fail.The comparison contrasts VIDEOTREE with LLoVi’s redundant and irrelevant frame sampling.

6. Conclusion

VIDEOTREE is an adaptive, hierarchical framework for LLM reasoning over long-form videos that extracts query-relevant keyframes in a coarse-to-fine manner. It shows strong performance across three datasets while reducing inference time and LLM calls.

  • VIDEOTREE organizes query-relevant keyframes into a hierarchical representation for handling complex long-video queries.
  • Strong performance is reported on EgoSchema, NExT-QA, and Video-MME together with reduced inference time and LLM calls.
  • Qualitative analysis shows key-scene extraction and finer-detail selection guided by the video query.

7. Limitations

VIDEOTREE depends on accurate frame captioning and includes hyperparameters, although reported ablations show it outperforms uniform sampling across tested max-depth and branch-width settings.

  • VIDEOTREE’s reasoning quality is limited by the captioner’s ability to accurately capture sampled-frame contents.
  • The framework’s modular design permits replacing captioners and LLM reasoning backbones as stronger models become available.
  • VIDEOTREE includes hyperparameters, but it outperforms uniform sampling across tested max-depth and branch-width choices.

8. Additional Quantitative Results

Additional evaluations show that VIDEOTREE generalizes beyond the main benchmarks, improving intent reasoning and performance across Video-MME splits and MLVU with different model settings.

  • IntentQA Results: 66.9% zero-shot accuracy on IntentQA surpasses LLoVi by 2.7% and approaches the finetuned Vamos method.IntentQA evaluates reasoning about people’s intent across varied video contexts.
  • Video-MME and MLVU Results: 67.8% and 59.9% accuracy on Video-MME short and medium splits improves over LLoVi and LongVA by more than 5.7% and 6.7%.
  • Video-MME and MLVU Results: VIDEOTREE gains 5.3% over LLoVi and 4.1% over LongVA on the MLVU validation set.

9. Additional Ablation Study

The ablations examine VIDEOTREE’s efficiency, representation structure, encoder and captioner choices, reasoning backbone, and tree hyperparameters. Results show that adaptive hierarchy and carefully limited information improve the efficiency–accuracy trade-off.

  • LLM Calls: VIDEOTREE needs only about 30% as many LLM calls as VideoAgent while achieving better results under similar caption counts.The authors attribute this to extracting more keyframes through adaptive hierarchical expansion rather than searching one frame at a time.
  • Visual Encoder: VIDEOTREE outperforms VideoAgent by an average of 6.9% across visual encoders, with only a 0.2% drop when reducing encoder size from 8B to 88M.DINOv2-base reaches 64.2% on EgoSchema subset, 1.8% below the same-size CLIP model.
  • Hyperparameter Analysis: A 4-branch tree gives the best performance, while excessive branch width overwhelms the LLM; even the worst setting outperforms the baseline.Reducing branch width improves efficiency while retaining performance relative to existing approaches.
  • Hyperparameter Analysis: A maximum breadth of 32 performs best, although smaller breadths retain good performance with fewer frames and excessive breadth worsens results.The findings support limiting the representation to avoid overwhelming LLM reasoning.
  • Hyperparameter Analysis: The best performance occurs at branch threshold 4, while reducing the threshold improves efficiency and retains strong performance.The threshold controls the iterative adaptive breadth expansion process.
  • VLM Captioner: Using a question-prompted LLaVA-1.6 captioner reaches 63.2% on EgoSchema subset, 3.0% below the direct-captioner variant.Captioner choice is comparable on NExT-QA but affects EgoSchema performance.
  • LLM Reasoner: A GPT-3.5 VIDEOTREE variant achieves 57.6% on EgoSchema subset, exceeding VideoAgent’s 48.8% and LLoVi’s 51.8% with the same LLM.The framework also improves with stronger LLMs, indicating performance can benefit from more advanced modules.
  • Tree structure: A temporal-order representation scores 66.2% on EgoSchema subset, compared with 64.8% for top-down left-right tree traversal.The tree structure remains important for keyframe selection, while temporal order benefits the reasoning model.

10. Detailed Algorithm

The algorithm builds VIDEOTREE through adaptive breadth expansion, relevance-guided depth expansion, and LLM reasoning. It iteratively clusters, captions, scores, expands, and aggregates video information before producing an answer.

  • Inputs: VIDEOTREE takes video frames, a query, clustering settings, visual encoder, captioner, LLM, and relevance controls as inputs.The algorithm maintains cluster information, relevance scores, and a tree-based video representation.
  • Adaptive breadth expansion: Adaptive breadth expansion doubles the cluster count until enough highly relevant clusters are found or the maximum breadth is reached.Each iteration performs visual clustering, cluster captioning, and relevance scoring against the query.
  • Relevance-guided depth expansion: Relevance-guided depth expansion refines each cluster using its relevance score and the selected branch width, adding finer-grained child nodes.The resulting expanded clusters are appended to the tree representation.
  • LLM reasoning: The framework retrieves captions from the video and tree, then applies LLM reasoning to the captions and query to return the predicted answer.Caption aggregation precedes the final reasoning step.

11. Additional Implementation Details

The implementation uses dataset-specific tree settings, shared captioning and reproduction procedures, detailed prompts, and modest compute resources. These details define the reported experimental configuration.

  • VIDEOTREE settings: EgoSchema and Video-MME use max_breadth 32, max_depth 3, branch_width 4, and threshold 4; NExT-QA uses 8, 3, 2, and 3.Initial cluster counts are 8 for EgoSchema and Video-MME and 4 for NExT-QA.
  • LifelongMemory reproduction: The reproduced LifelongMemory comparison uses VIDEOTREE’s captioner and 0.5FPS captions, but initially achieves only about 80% successful QA samples.Updating the output-format and processing code improves performance by about 10%, while results remain below the original paper’s report.
  • Prompt details: The authors provide separate prompts for relevance scoring and LLM reasoning on EgoSchema.These prompts are documented in Tables 16 and 17.
  • Compute resources: Experiments run on four or fewer NVIDIA-A6000 GPUs and Azure Cloud APIs, with a minimum GPU memory requirement of 24GB.OpenAI models are accessed through Azure Cloud APIs.

12. Additional Qualitative Analysis

Qualitative analyses show that VIDEOTREE allocates keyframes according to query detail and can localize activities efficiently, while a failure case exposes caption hallucination risks. Human evaluation also measures the accuracy of keyframe scoring.

  • Qualitative visualization: VIDEOTREE localizes embroidering a cloth and dynamically expands its constituent frames to answer correctly using a minimal number of frames.General queries produce sparser keyframes across distant video regions, whereas detailed action or object queries receive denser selections.
  • Qualitative visualization: The qualitative comparison marks cases answered wrongly with uniformly sampled frames in red and cases answered correctly by VIDEOTREE in green.The figure presents examples of VIDEOTREE keyframe and caption selection.
  • Failure case: A failure on repeated dish-washing actions occurs when fine-grained captions hallucinate and omit the higher-level keyword “dish.”The authors suggest stronger captioners could potentially resolve this failure.
  • Human study: GPT-4-based first-level keyframe scoring agrees with a human annotator on 90.7% of 345 keyframes from 20 EgoSchema videos.The study evaluates the relevance of selected keyframes to the query.
Loading 2405.19209v3…