Source-linked AI summary
T*: Re-thinking Temporal Search for Long-Form Video Understanding
Jinhui Ye, Zihan Wang, Haosen Sun, Keshigeyan Chandrasegaran, Zane Durante, Cristobal Eyzaguirre, Yonatan Bisk, Juan Carlos Niebles, Ehsan Adeli, Li Fei-Fei, Jiajun Wu, Manling Li
TL;DR
Long-form video understanding is constrained by the difficulty and cost of locating a few relevant frames among thousands. The paper introduces LV-HAYSTACK to evaluate temporal search and T* to perform it as adaptive spatial search, with reported downstream gains and improved efficiency. The approach is bounded by its few-keyframe and visual-only assumptions.
Problem
Long-form VLMs need an efficient way to locate a minimal set of relevant frames among tens of thousands while preserving the information needed for question answering.
Method
The paper introduces LV-HAYSTACK and T*, which transforms frame sequences into a large image and iteratively refines temporal and spatial regions using visual cues.
Results
T* improves GPT-4o from 47.1% to 51.9% on LongVideoBench XLong with 8 frames and LLaVA-OneVision-OV-72B from 56.5% to 62.4% with 32 frames.
Takeaways & Limitations
T* provides a more efficient temporal-search route for long-form video understanding by integrating spatial search with downstream VLM answering.
Takeaways & Limitations
The approach assumes that most problems can be answered with a few keyframes and focuses primarily on visual cues, excluding audio and subtitles.
Abstract
from arXiv · showhide
Efficiently understanding long-form videos remains a significant challenge in computer vision. In this work, we revisit temporal search paradigms for long-form video understanding and address a fundamental issue pertaining to all state-of-the-art (SOTA) long-context vision-language models (VLMs). Our contributions are twofold: First, we frame temporal search as a Long Video Haystack problem: finding a minimal set of relevant frames (e.g., one to five) from tens of thousands based on specific queries. Upon this formulation, we introduce LV-Haystack, the first dataset with 480 hours of videos, 15,092 human-annotated instances for both training and evaluation aiming to improve temporal search quality and efficiency. Results on LV-Haystack highlight a significant research gap in temporal search capabilities, with current SOTA search methods only achieving 2.1% temporal F1 score on the Longvideobench subset. Next, inspired by visual search in images, we propose a lightweight temporal search framework, T* that reframes costly temporal search as spatial search. T* leverages powerful visual localization techniques commonly used in images and introduces an adaptive zooming-in mechanism that operates across both temporal and spatial dimensions. Extensive experiments show that integrating T* with existing methods significantly improves SOTA long-form video understanding. Under an inference budget of 32 frames, T* improves GPT-4o's performance from 50.5% to 53.1% and LLaVA-OneVision-OV-72B's performance from 56.5% to 62.4% on the Longvideobench XL subset. Our code, benchmark, and models are provided in the Supplementary material.
1. Introduction
Long-form video understanding requires efficient temporal search because VLMs cannot feasibly process thousands of frames individually. The paper introduces LV-HAYSTACK to benchmark this problem and T* to recast temporal search as spatial search.
- Motivation: VLMs face computational challenges when processing thousands of long-video frames because each image requires many tokens.LLaVA and Tarsier, for example, use 576 tokens per image.
- Motivation: Temporal search selects a minimal set of relevant frames across an entire video rather than identifying one continuous temporal segment.The formulation treats long videos as haystacks containing a few essential frames.
- LV-HAYSTACK: LV-HAYSTACK contains 15,092 human-annotated instances from 988 Ego4D videos spanning 423 hours and 45.7 million frames.It combines Ego4D and LongVideoBench data and introduces temporal, visual, and frame-set similarity metrics.
- T*: T* reframes temporal search as spatial search by transforming frame sequences into one large image and iteratively refining temporal and spatial regions.The framework discards irrelevant frames, inserts frames around promising temporal regions, and zooms in for higher spatial resolution.
- Results: 3x FLOPs efficiency and comparable downstream performance with 4x fewer frames distinguish T* from frame-by-frame search.The reported efficiency and frame reduction are presented for T* applied to long-form video understanding tasks.
2. Temporal Search in Video Understanding
The paper defines temporal search as selecting a complete yet minimal keyframe set for answering questions in long videos. It constructs a benchmark and evaluates search utility through frame-level, set-level, and efficiency metrics.
- Task Formulation: Temporal search selects a minimal subset of video frames containing all critical information needed to answer a question.The selected set must satisfy both completeness and minimality.
- Benchmark: LV-HAYSTACK instances pair a video, question, human-selected keyframes, and answer, using egocentric and allocentric videos from Ego4D and LongVideoBench.Ego4D segments average 8.3 minutes and include activities such as object finding and shopping.
- Framework: T* searches keyframes through question grounding, iterative temporal search, and downstream question answering.The framework uses visual cues and progressively refines temporal and visual regions before passing K keyframes to a VLM.
- Search Utility: Frame-level utility compares predicted and annotated frames using temporal similarity and visual similarity based on SSIM.Temporal similarity uses a timestamp-difference threshold, while visual similarity measures structural details, luminance, and contrast.
- Search Utility: Set-level utility uses precision for alignment of selected frames with references and recall for representation of reference frames in the selection.Their harmonic mean is the F1 score, balancing relevance and coverage.
- Efficiency: Search efficiency is measured by frame cost, FLOPs, and latency.These metrics respectively capture processed-frame count, computational complexity, and total search time.
3. T*: Efficient Temporal Search
T* reformulates temporal search as spatial search by arranging sampled video frames into grids and iteratively refining attention toward promising temporal regions. Its pipeline grounds questions, searches adaptively, and returns top-scoring keyframes for downstream video understanding.
- Framework: T* comprises question grounding, iterative temporal search, and downstream task completion, forwarding selected keyframes to a VLM for answering.The first two phases identify keyframes; the final phase uses them for question answering.
- Question grounding: Question grounding uses a VLM to identify target objects and contextual cue objects from uniformly sampled frames conditioned on the question.Targets are directly relevant visual elements, while cues indicate potential regions of interest.
- Iterative temporal search: T* initializes a uniform frame distribution, assigns higher weight to target objects than cues, and samples frames to construct g × g grid images.The initial target and cue weights are 1.0 and 0.5, respectively, and the search budget decreases by g^2 per grid construction.
- Iterative temporal search: Each iteration detects objects in grid cells, scores sampled frames, updates the distribution through spline interpolation and local windows, and continues until targets are found or the budget is exhausted.High-confidence detections influence subsequent sampling, while visited frames are tracked during score updates.
- Search utility: Detector-based T* achieves the best 32-frame search performance across metrics, while attention-based T* performs well with 8 frames but requires larger foundation models.The comparison is reported on LV-HAYSTACK search utility results.
- Efficiency: T* achieves high performance with significantly less computation and lower latency than baselines in full LV-HAYSTACK efficiency evaluation.The evaluation includes both search efficiency and overall search-plus-downstream efficiency.
- Output: The final keyframes are selected by TopK from the score distribution, returning frames with timestamps for downstream tasks.The TopK operation is intended to preserve relevance and temporal coverage.
4. Experimental Setup
Experiments evaluate T* across search utility, efficiency, and downstream video-question-answering settings. The setup compares multiple search strategies, spatial-search implementations, VLMs, frame budgets, and video understanding datasets.
- Search models: The spatial search model H is implemented with attention-based, detector-based, and training-based variants.These variants use VLM attention matrices, object detectors such as YOLO-world, or custom-trained models.
- Metrics: Search performance is reported using metrics from Sections 2.3 and 2.4 with a 5-second temporal threshold.
- Baselines: Baselines include uniform sampling, temporal-search methods such as VideoAgent, and retrieval methods that score and rank all frames.The comparisons cover both sampling and search strategies.
- Downstream evaluation: Table 4 compares VLMs using QA accuracy on LongVideoBench and Video-MME without subtitles, alongside leaderboard models that typically use substantially more frames.Models are ranked by XLong video performance on LongVideoBench and total score on Video-MME, with frame counts reported.
- Datasets: Downstream QA is evaluated on LongVideoBench, VideoMME, EgoSchema, NExT-QA, and an Ego4D LongVideo QA extension.The tasks span temporal action reasoning, causal inference, and egocentric understanding across videos from 15 seconds to 60 minutes.
5. Experimental Results
T* improves temporal and downstream video understanding across datasets, frame budgets, and model types, while reducing search computation and latency relative to baselines.
- Attention-based T* achieves the best temporal metrics with higher precision, recall, and F1 scores at 8 frames.
- 169.6 TFLOPs, 10.4s latency, and 60.3% accuracy make training-based T* more efficient and accurate than VideoAgent at 690.7 TFLOPs, 34.9s, and 49.2%.
- The Ego4D Longvideo QA extension reports performance for both clip-level and full-video inputs using vision-language models.
- T* enhances VLM performance on LongVideoBench and VideoMME across frame budgets, video lengths, and VLMs.
- On NExT-QA and EgoSchema, T* outperforms other frame-selection methods while using the fewest frames.
- On the LongVideoBench XLong subset, T* boosts GPT-4o from 47.1% to 51.9% with 8 frames and LLaVA-OneVision-OV-72B from 56.5% to 62.4% with 32 frames.
6. Analysis
The analysis explains T*’s efficiency and search behavior: iterative visual-temporal refinement concentrates sampling on relevant regions while improving performance as more search frames are available.
- 6.1. Time and Cost Complexity of T*: T* operates as a quaternary search guided by an object-detector heuristic, with O(log L) complexity in stated best- and worst-case formulations.
- 6.1. Time and Cost Complexity of T*: T* offers better efficiency than methods that linearly process and examine all frames.
- 6.1. Time and Cost Complexity of T*: The computational overhead includes VLM reasoning and processing plus YOLO-world processing for each image grid.
- 6.2. Temporal Focus Dynamics: Sampling weights progressively align with ground-truth frames across iterations, including simultaneously distant keyframes around 50s and 100s.
- 6.3. Effect of Search Frames: T* consistently outperforms the baseline across search-frame counts and approaches human-selected-frame accuracy as the frame count increases.
7. Related Work
Related work addresses long-form video understanding, temporal localization, and needle-in-a-haystack evaluation, while this paper emphasizes temporal search in real-world long videos.
- Long-form Video Understanding: Existing long-video methods use compression or frame selection, and benchmarks mostly evaluate downstream QA rather than temporal search itself.
- Temporal Localization and Temporal Search: Temporal localization methods struggle with boundary detection, whereas this work targets the more challenging problem of searching longer videos.
- Needle in a Haystack: Prior needle-in-a-haystack approaches span text and multimodal domains but rely on synthetic data, unlike this work’s real-world natural video contexts.
8. Conclusion
The paper formulates temporal search as a Long Video Haystack problem, introduces LV-HAYSTACK for its evaluation, and proposes T* as a spatial-search reformulation for efficient long-form video understanding.
- Temporal search is formulated as finding a minimal set of relevant frames among tens of thousands in real-world long videos given specific queries.
- LV-HAYSTACK contains 15,092 human-annotated instances with fine-grained metrics for temporal search quality and computational efficiency.
- T* casts expensive temporal search as a spatial search problem and significantly improves SOTA performance when integrated with video understanding models.
Limitations
The work assumes most questions can be answered with a few keyframes, but this may not extend to tasks requiring broader context or dense reasoning. It also focuses primarily on visual cues rather than audio or subtitles.
- The few-keyframe assumption may not extend to complex tasks requiring broader context or dense reasoning.
- The approach primarily uses visual cues and does not leverage audio or subtitles.
A.1. Ablation on Question Grounding
Question Grounding remains effective with modest resource allocations: larger VLMs and more initial frames produce only marginal gains. Search performance also reflects trade-offs among grid size, return threshold, and evaluation metric choice.
- Question Grounding: Increasing VLM size and initial frames marginally improves search effectiveness and downstream performance.The reported downstream QA gain is below 1%.
- Question Grounding: Question Grounding can be achieved with modest resources while balancing search quality and computational usage.
- Grid Size Impact: Grid size changes the average number of search steps and LongVideoBench XL performance under an 8-frame LLaVA-72B setting.Figure 5 compares search iterations with downstream performance across image-grid configurations.
- Return Threshold: Lower return thresholds make searches faster but may reduce accuracy, whereas higher thresholds improve accuracy at greater search cost.
- Evaluation Metrics: Semantic-distance scores cluster from 87.9 to 89.2 and therefore discriminate less between methods than temporal and visual metrics.
- Evaluation Metrics: Temporal F1 has the highest Pearson correlation and Temporal Precision the highest Spearman correlation with downstream accuracy.
B. Complexity Analysis on T*
T* uses heuristic-guided multi-branch search over an image-grid representation, with efficiency depending on branch-selection accuracy and increasing search effort for longer videos. Its empirical behavior spans random-search degradation to direct b-ary search in the best case.
- Search Structure: T* retains up to 1/b of video-grid cells per iteration, forming a b-way search tree guided by heuristic scores.
- Complexity Cases: When scoring accuracy provides no effective guidance, T* degrades to linear search over the video frames.This is the stated worst-case behavior when P ≤ 1/b.
- Complexity Cases: When P = 1, T* approaches the target directly like a b-ary search, with branching factor b = n × n.
- Efficiency: Higher scoring-function accuracy reduces exploration of incorrect branches and improves efficiency.
- Empirical Complexity: The search-step average increases gradually with video length across videos from 100 to 3600 seconds.
- Empirical Complexity: For videos longer than 3000 seconds, T* requires 5 to 161 search steps, averaging 41.5 steps.
C. Detail Analysis on LongVideoBench
T* improves downstream QA across video lengths, especially for longer videos, while its trainable variant reduces computational cost. The framework uses question grounding, grid-based scoring, and reinforcement-learning-inspired frame selection, with annotation procedures designed to preserve logical correctness.
- LongVideoBench Results: GPT4o accuracy on XLong videos increases from 47.1 to 51.55 ± 0.35 with T*, while LLaVA-OneVision-72B rises from 53.7 to 55.25 ± 0.25.
- LongVideoBench Results: T* consistently improves QA accuracy across video lengths, with larger gains on longer videos and larger models.
- Trainable T*: The trainable scoring mechanism assigns each grid cell a relevance score and selects K frames for downstream question answering.
- Trainable T*: Its reward is the accuracy difference between frames selected from predicted relevance scores and uniformly sampled frames.
- HAYSTACK-EGO4D: Annotators watched entire videos before identifying keyframes, including multiple occurrences when questions required temporal ordering.
- Qualitative Analysis: T* sampling prioritizes semantically relevant frames and captures critical visual information such as the metal cylinder.