Literature
Display
← All papers

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

· CVPR 2025 ↗

Computer vision15 min text · CondensedOriginal paper ↗
Contents

Overview

The overview compares long-video QA accuracy with the number of frames passed to the answering model. Its frame budget excludes the additional frames and model calls used during search.

Original PDF illustration S0.F1
Figure 1: Long-form video understanding performance comparison on LongVideoBench [72] XL subset (900-3600s). Open-sourced model size is indicated by marker size. Our lightweight temporal search algorithm T* (§3) improve SOTA models significantly: GPT-4o (50.5% →\rightarrow~53.1% and LLaVA-OneVision-OV-72B (56.5% →\rightarrow 62.4%), both with 32 frames.

At a glance

T* selects informative frames from long videos by arranging sampled frames into an image grid and applying spatial object-search models to that grid. It alternates sampling, scoring and temporal/spatial refinement before passing a small selection to a video question-answering model. LV-Haystack provides human keyframes and answers for evaluating search separately from final QA. On LongVideoBench’s longest subset, the main table reports GPT-4o improving from 50.5% to 53.1% and LLaVA-OneVision-72B from 56.5% to 62.4% with 32 output frames. Search has additional computational cost, and neither complete answer evidence nor logarithmic worst-case search is guaranteed.

1 Introduction

Long videos contain far more frames than a VLM can economically process at full detail. The proposed task selects a small, potentially discontinuous set of answer-supporting frames, unlike temporal localization of one continuous interval. LV-Haystack uses natural videos from Ego4D [18] and LongVideoBench [72] rather than inserting artificial needles. Its contribution is explicit search-quality and search-cost evaluation alongside downstream answers.

Inspired by spatial visual search such as V* [73], T* packs video frames into one image, identifies useful cells, and reallocates temporal and spatial resolution to promising regions. The method combines a VLM for question grounding, a cheaper spatial scorer for repeated search, and a separate answering model. Claims of fourfold frame savings refer to selected downstream inputs; claims of computational savings require the full grounding, search and answer costs, which are reported separately.

Original PDF illustration S1.F2
Figure 2: The T* framework that employs efficient temporal search for long-form video understanding. T* employs an iterative temporal search approach to search keyframes essential to answer questions. Left: Question Grounding, where a visual language model identifies visual cues (target and cue object) from the textual question. Center: Iterative Temporal Search, formulated as Spatial Search where a spatial search model iteratively detects visual cues and upsamples relevant temporal/visual regions. Right: Downstream Task, where the visual language model answer questions using KK keyframes sampled from the final temporal search distribution as visual input.

2 Temporal Search in Video Understanding

Temporal search aims to retain the visual evidence needed to answer a question using few frames. The paper separates this selection problem from the answering model.

2.1 Task Formulation

The desired set is complete if it preserves the answer obtainable from the full video, and minimal if removing any essential evidence would compromise that answer. These are task objectives, not properties established by object detection or by the proposed overlap metrics. Different frame sets may legitimately support the same answer.

2.2 The LV-Haystack Benchmark

Haystack-Ego4D has 15,092 QA pairs from 988 original videos, with 28,300 annotated keyframes. Annotation operates on 1,324 context clips averaging 8.3 minutes; Table 1 describes the originals as 423 hours, about 25.7 minutes each. Haystack-LVBench has 114 videos, 342 questions and 496 reference keyframes, with 26.7 hours listed. The abstract’s 480-hour total is not reconciled with these table totals (449.7 hours).

The main section describes Ego4D NLQ validation data and verification/refinement of LongVideoBench timestamps. Section 5.3 instead names Ego4D’s test set, and Appendix E describes directly reusing LongVideoBench reference positions. These protocol differences are retained as unresolved source ambiguities, rather than asserting a uniquely specified split or fresh annotation of every reference.

Subset Haystack-Ego4D Haystack-LVBench
Video Type Egocentric Allocentric
# video 988 114
# length 423 h 26.7 h
- 25.7 min per video - 14.1 min per video
# frame 45,700,000 2,200,000
- 46,300 per video - 19,100 per video
# QA pair 15,092 342
- 15.3 per video - 3.0 per video
# keyframe 28,300 496
- 1.9 per question - 1.5 per question

Table 1: Data Statistics of LV-Haystack.

2.3 Evaluation Metrics for Search Utility

Search utility compares selected frames with annotated evidence using both timestamp and image similarity, while allowing each frame to match its best counterpart.

Algorithm 1 Efficient Temporal Search with Dynamic Sampling
Input : Video VV, target/cue objects {T,C}\{T,C\}, keyframe count KK, search budget BB, threshold θ\theta
Output : Keyframes FF with timestamps τ\tau
1 Initialize: S,N←𝟎L,𝟏LS,N\leftarrow\mathbf{0}^{L},\mathbf{1}^{L}, P←1L​𝟏LP\leftarrow\frac{1}{L}\mathbf{1}^{L}, R←TR\leftarrow T, F,τ←∅F,\tau\leftarrow\emptyset ; // L=|V|L=|V|
2 while R≠∅R\neq\emptyset and B>0B>0 do
     3 I←Sample​(P⊙N,g2)I\leftarrow\text{Sample}(P\odot N,g^{2}), G←Grid​(V​[I])G\leftarrow\text{Grid}(V[I]), B←B−g2B\leftarrow B-g^{2} ; // Sample and grid
     4 (C,O)←Detect​(G)(C,O)\leftarrow\text{Detect}(G) ; // Get confidence maps and objects
     5 for i∈[1..|I|]i\in[1..|I|] where Oi∩R≠∅O_{i}\cap R\neq\emptyset do
         6 S⁡[Ii],N⁡[Ii]←Ci,0S[I_{i}],N[I_{i}]\leftarrow C_{i},0 ; // Update scores and mark visited
         7 if Verify​(V​[Ii])>θ\text{Verify}(V[I_{i}])>\theta then
             8 F,τ←F∪{V⁡[Ii]},τ∪{Ii/f​p​s}F,\tau\leftarrow F\cup\{V[I_{i}]\},\tau\cup\{I_{i}/fps\}, R←R∖(Oi∩R)R\leftarrow R\setminus(O_{i}\cap R)
     9 P←Normalize​(Spline​(S,N))P\leftarrow\text{Normalize}(\text{Spline}(S,N)) ; // Update distribution
10 return Sample​(V,S,K)\text{Sample}(V,S,K)

Frame-to-Frame Metrics.

Temporal similarity is a binary timestamp match within a threshold; experiments use five seconds. Visual similarity uses SSIM [5], which compares structure, luminance and contrast. Neither a nearby timestamp nor a similar-looking frame establishes that the answer-relevant event or relation is visible.

Set-to-Set Metrics.

Precision averages each predicted frame’s best similarity to any reference; recall reverses those roles. Their harmonic mean gives F1. This accommodates several valid-looking matches, but still depends on the annotated set and may penalize valid unannotated evidence. Duplicate or semantically irrelevant but visually similar frames can also complicate interpretation. The original equations and complete search algorithm are retained.

Equations 1–2
Precision​(Fpt,Fgt)=1|Fpt|​∑fpti∈Fptsim​(fpti,Fgt),\text{Precision}(F_{\text{pt}},F_{\text{gt}})=\frac{1}{|F_{\text{pt}}|}\sum_{f_{\text{pt}}^{i}\in F_{\text{pt}}}\text{sim}(f_{\text{pt}}^{i},F_{\text{gt}}), (1)
Recall​(Fpt,Fgt)=1|Fgt|​∑fgtj∈Fgtsim​(fgtj,Fpt),\text{Recall}(F_{\text{pt}},F_{\text{gt}})=\frac{1}{|F_{\text{gt}}|}\sum_{f_{\text{gt}}^{j}\in F_{\text{gt}}}\text{sim}(f_{\text{gt}}^{j},F_{\text{pt}}), (2)

2.4 Evaluation Metrics for Search Efficiency

Efficiency is measured by total processed frames, FLOPs and latency. Final output-frame count should be distinguished from all frames examined during grounding and iterative search.

3 T* : Efficient Temporal Search

Question grounding extracts visual targets and context cues; iterative search concentrates samples around promising temporal regions; the answering VLM receives the selected frames. The framework supports attention, detector and learned scoring variants.

Method Frames↓\downarrow Haystack-Ego4D Haystack-LVBench
Temporal Visual Temporal Visual
Precision ↑\uparrow Recall ↑\uparrow F1F_{1} ↑\uparrow Precision ↑\uparrow Recall ↑\uparrow F1F_{1}↑\uparrow Precision ↑\uparrow Recall ↑\uparrow F1F_{1} ↑\uparrow Precision ↑\uparrow Recall ↑\uparrow F1F_{1}↑\uparrow
Baselines: Static Frame Sampling
Uniform [72] 8 1.0 3.4 1.6 58.0 63.0 60.2 1.4 6.3 2.2 56.0 72.0 62.7
Uniform [72] 32 1.1 14.8 2.0 58.5 65.6 61.5 1.4 24.9 2.7 58.7 81.6 67.3
Baselines: Adaptive Temporal Search
VideoAgent [68] 10.1 1.7 5.8 2.7 58.0 62.4 59.9 1.2 8.5 2.1 58.8 73.2 64.7
Retrieval-based 8 1.2 4.2 1.9 58.5 61.7 59.9 1.5 6.3 2.3 63.1 65.5 64.1
Retrieval-based 32 1.0 13.8 1.9 58.5 65.4 61.4 1.3 21.8 2.4 59.9 80.8 67.8
Ours: T∗T^{*} for Zooming In Temporal Search
Attention-based 8 2.2 7.5 3.3 58.4 62.5 60.2 1.5 6.6 2.4 63.6 68.6 65.7
Training-based 8 1.4 4.9 2.1 58.0 61.5 59.6 1.5 6.6 2.3 59.8 71.1 64.5
Detector-based 8 1.7 5.8 2.7 63.8 70.1 66.8 1.6 7.1 2.5 58.4 72.7 64.3
Detector-based 32 1.8 26.3 3.4 62.9 76.2 68.9 1.7 28.2 3.1 58.3 83.2 67.8

Table 2: Search utility results on LV-Haystack. 8-frame setting bests are underlined, 32-frame setting bests are in bold. We show that more searched frames consistently improves recall but reduces precision in retrieval methods. Detector-based T* achieves best performance in 32-frame setting across metrics, demonstrating the effectiveness of visual grounding and iterative temporal search. Attention-based T* performs well in 8-frame setting but requires larger foundation models, thereby reducing efficiency.

Method Search Efficiency Overall Task Efficiency
Grounding Matching TFLOPs ↓\downarrow Latency (sec) ↓\downarrow TFLOPs ↓\downarrow Latency (sec) ↓\downarrow Acc ↑\uparrow
Baselines: Static Frame Sampling
Uniform-8 [72] N/A N/A N/A 0.2 139.3 3.8 45.9
Baselines: Adaptive Temporal Search
VideoAgent [68] GPT4×\times4 CLIP-1B×\times840 536.5† 30.2 690.7† 34.9 49.2
Retrieval-based N/A YOLO-world-110M×\times840 216.1 28.6 355.4 32.2 50.3
Ours: T∗T^{*} for Efficient Temporal Search
Attention-based LLaVA-72B×\times3 N/A 88.9 13.7 228.2 17.3 49.6
Detector-based LLaVA-7B×\times1 YOLO-world-110M×\times49 33.3 7.5 172.6 11.1 50.8
Training-based LLaVA-7B×\times1 YOLO-world-110M×\times38 30.3 6.8 169.6 10.4 51.0

Table 3: Efficiency results on the full LV-Haystack, including search efficiency and overall (search+downstream) efficiency. We report the search models used and their avg. call frequency (e.g., VideoAgent calls GPT-4 four times for grounding). T* achieves high performance with significantly less computation and lower latency. VideoAgent’s FLOPs (†) exclude GPT-4 costs due to its closed-source nature. All training and inference operations are carried out on a cluster of 8*H800 Nvidia GPUs.

LongVideoBench Video-MME
Model and Size #Frame Video Length Model and Size #Frame Video Length
XLong Long Medium Short Long Medium Short Total
15-60min 2-10min 15-60s 8-15s 41min 9min 1.3min 17min
GPT4o 8 47.1 49.4 67.3 69.7 GPT4o 8 51.4 54.3 55.7 53.8
GPT4o + T* 8 51.9 52.4 72.7 70.0 GPT4o + T* 8 55.9 57.3 56.4 56.5
LLaVA-OneVision-72B 8 53.7 57.4 74.1 73.0 LLaVA-OneVision-72B 8 52.6 55.5 59.6 55.9
LLaVA-OneVision-72B + T* 8 55.5 63.7 76.3 73.5 LLaVA-OneVision-72B + T* 8 57.7 57.5 61.7 59.0
GPT4o 32 50.5 57.3 73.5 71.4 GPT4o 32 56.3 60.7 68.3 61.8
GPT4o + T* 32 53.1 59.4 74.3 71.4 GPT4o + T* 32 59.3 63.5 69.5 64.1
LLaVA-OneVision-72B 32 56.5 61.6 77.4 74.3 LLaVA-OneVision-72B 32 60.0 62.2 76.7 66.3
LLaVA-OneVision-72B + T* 32 62.4 64.1 79.3 74.6 LLaVA-OneVision-72B + T* 32 61.0 66.6 77.5 68.3
GPT-4o (0513) 256 61.6 66.7 76.8 71.6 Gemini-1.5-Pro (0615) 1/0.5 fps1∗ 67.4 74.3 81.7 75.0
Aria-8x3.5B 256 60.1 64.6 76.6 69.4 Qwen2-VL-72B 7683∗ 62.2 71.3 80.1 71.2
LLaVA-Video-72B-Qwen2 128 59.3 63.9 77.4 72.4 GPT-4o (0615) 3842∗ 65.3 70.3 80.0 71.9
Gemini-1.5-Pro (0514) 256 59.1 65.0 75.3 70.2 LLaVA-Video-72B 64 61.5 68.9 81.4 70.6
Qwen2-VL-7B 256 52.5 56.7 67.6 60.1 Aria-8x3.5B 256 58.8 67.0 76.9 67.6

Table 4: Downstream task evaluation results show T* effectiveness as a temporal search module for VLMs on LongVideoBench and Video-MME (without subtitles for fair comparison). Using QA accuracy (%) as the metric, we compare with top leaderboard models (shown in gray), noting these typically use substantially more frames, making direct comparisons challenging. Models are ranked by XLong video performance on LongVideoBench and total score on Video-MME, with frame counts indicated. All baseline figures are directly cited from their original publications. Standard deviations and more detailed analysis are available in Appendix C.

3.1 Question Grounding

A VLM views uniformly sampled frames with the question and names target objects directly relevant to the answer plus contextual cue objects likely to occur nearby. The default uses LLaVA-OneVision-7B [28] with eight frames. For a dustbin question, the bin is a target and surrounding room objects supply cues. Errors or omissions in this object-centric grounding propagate into search.

Equation 3
{T,C}=VLM​(VN¯,Q).\{T,C\}=\texttt{VLM}(\overline{V_{N}},Q).\vskip-6.0pt (3)

3.2 Iterative Temporal Search

The iterative procedure maintains scores, sampling probabilities, visited flags and a set of not-yet-found targets.

Initialization

Sampling probabilities start uniform; scores start at zero and all frames are unvisited. Target objects receive weight 1.0 and context cues 0.5. The remaining-target set initially contains every requested target.

Frame Sampling and Grid Construction

Each iteration samples g² frames from the probability distribution masked by unvisited flags, arranges them into a g × g image, and subtracts g² from the search budget. Grid cells trade image detail against temporal coverage; the default grid is 8 × 8.

Equation 4
I=Sample​(P⊙Nv,g2)I=\text{Sample}(P\odot N_{v},g^{2})\vskip-6.0pt (4)

Object Detection and Scoring

A spatial model scores each cell by the maximum detected-object confidence multiplied by its target/cue weight. Confidently verified targets are recorded and removed from the remaining-target set. Finding an object alone does not ensure that its action, event order or relation answers the question.

Equation 5
Ci,j=maxo∈𝒟i,j⁡(co⋅wo)C_{i,j}=\max_{o\in\mathcal{D}_{i,j}}(c_{o}\cdot w_{o})\vskip-6.0pt (5)

Distribution Update

Observed scores mark frames as visited; a local temporal window propagates high scores with distance decay. Spline interpolation and normalization update the sampling distribution. Search stops when all targets are found or the budget is exhausted. The text describes returning top-K scored frames, while Algorithm 1 writes Sample(V,S,K); this top-K-versus-sampling distinction is not resolved in the pseudocode.

Equations 6–7
Sf=Cf,Nv,f=0S_{f}=C_{f},\quad N_{v,f}=0\vskip-6.0pt (6)
Sf±δ=max⁡(Sf±δ,Sf|δ|+1),δ∈[−w,w]S_{f\pm\delta}=\max(S_{f\pm\delta},\frac{S_{f}}{|\delta|+1}),\quad\delta\in[-w,w]\vskip-6.0pt (7)

3.3 Downstream Task Completion

Selected frames and timestamps become input to the downstream VLM. Temporal coverage is an intended effect of iterative sampling rather than a formal guarantee of the final selection rule.

4 Experimental Setup

Experiments evaluate both selected-frame quality and final question answering, using matched downstream frame budgets where possible.

4.1 Evaluations on Search Utility and Efficiency

LV-Haystack measures search directly, and the efficiency comparison passes eight selected frames to a common answering model.

Datasets and models.

The common answering model is LLaVA-OneVision-72B. Spatial scoring uses either VLM attention, the 110M-parameter YOLO-World detector [8], or a trained replacement scoring head. Grounding and search model sizes vary across variants.

Evaluation Metrics.

Temporal matching uses a five-second threshold; visual matching uses SSIM. Frame counts, FLOPs and latency accompany downstream QA accuracy.

Baselines.

Baselines include uniform sampling, VideoAgent [68] and exhaustive retrieval that scores/ranks frames. These differ in search work even when their final output counts match. The implemented VideoAgent is adapted for this benchmark rather than an unchanged reproduction.

4.2 Evaluations on Downstream Tasks: Video QA

Downstream evaluation spans long videos and short action clips, including egocentric questions and temporal or causal reasoning.

Datasets.

Benchmarks are LongVideoBench, Video-MME [15], EgoSchema [43], NExT-QA [77] and an Ego4D LongVideo QA extension. Video-MME excludes subtitles for the reported comparison.

Evaluation Metrics.

Downstream success is multiple-choice QA accuracy, which measures the entire selection-plus-answering pipeline rather than search alone.

Baselines.

The main comparisons add T* to GPT-4o or LLaVA with eight or 32 final frames. Other leaderboard entries use different models and often many more frames, so those rows are context rather than controlled algorithm comparisons.

5 Experimental Results

The results distinguish low absolute temporal evidence overlap from improvements in downstream QA.

5.1 Results on LV-Haystack Search Performance

With eight outputs, attention-based search has the best temporal F1 among the reported variants, but uses a costly 72B model. Detector-based T* with 32 frames reaches temporal F1 3.4 on Haystack-Ego4D and 3.1 on Haystack-LVBench; evidence localization remains weak in absolute terms. More output frames generally raise recall, while precision can fall. Table 2’s caption overstates across-metric dominance: on LVBench, retrieval has higher visual precision (59.9 versus 58.3).

Table 3 reports trained T* at 169.6 TFLOPs and 10.4 s overall, versus VideoAgent’s 690.7 TFLOPs and 34.9 s; VideoAgent’s closed GPT-4 cost is omitted. The table gives trained T* QA accuracy as 51.0%, whereas the section’s prose claims 60.3%. These conflicting values are preserved and flagged. Grounding and matching costs make the final eight-frame count an incomplete description of total work.

Model Frames NExT-QA EgoSchema
0.7min 3min
Baselines using Static Uniform Sampling
InternVideo [69] 90 49.1 32.1
MVU [52] 16 55.2 60.3
LLoVi [86] 90 67.7 57.6
LangRepo [23] 180 60.9 66.2
LLaVA-OneVision-7B [28] 32 79.4 65.4
Baselines using Adaptive Frame Selecting
SeViLA [83] 32 63.6 25.7
VideoAgent [67] 8.4 71.3 60.2
LVNet [49] 12 72.9 66.0
VideoTree [70] 63.2 73.5 66.2
VidF4 [37] 8 74.1 -
Ours: Plug in T∗T^{*} for Efficient Temporal Search
LLaVA-OneVision-7B [28] 8 76.4 63.6
+ T* 8 80.4 66.6

Table 5: Downstream task evaluation results by plugging in T* as an additional temporal search method for VLMs on NExT-QA and EgoSchema. The video length is shorter than Table 4. Baseline results are directly cited from respective publications.

Model Frames Tiny Test
Clip Video Clip Video
Baselines using Static Uniform Sampling
GPT4o 8 45.5 41.5 45.9 45.3
GPT4o + T* 8 49.5 45.0 49.4 46.7
GPT4o 32 49.0 45.5 52.3 51.0
GPT4o + T* 32 51.0 46.5 54.9 52.5
QWen2.5VL 7B 8 37.0 32.0 40.0 38.8
QWen2.5VL 7B + T* 8 38.5 37.0 42.7 40.3
QWen2.5VL 7B 16 37.5 35.0 40.9 38.8
QWen2.5VL 7B + T* 16 39.5 38.5 43.8 42.8
QWen2.5VL 72B 8 45.0 45.0 51.0 50.1
QWen2.5VL 72B + T* 8 45.5 46.0 53.5 52.8
QWen2.5VL 72B 16 49.0 49.5 53.6 50.6
QWen2.5VL 72B + T* 16 50.0 50.0 55.1 52.8

Table 6: Downstream evaluation results on the Ego4D Longvideo QA dataset. We extend the Ego4D NLQ task by including answer options and responses, and report performance for both clip-level and full video inputs using vision-language models.

5.2 Results on Downstream Tasks: Long Video QA

On LongVideoBench XLong with eight frames, GPT-4o rises from 47.1 to 51.9%; with 32 frames it rises from 50.5 to 53.1%, and LLaVA-72B from 56.5 to 62.4%. Video-MME’s overall 32-frame scores rise from 61.8 to 64.1 and from 66.3 to 68.3, respectively. Effects vary by duration and model; the full table preserves each setting.

For shorter videos, eight-frame LLaVA-7B improves from 76.4 to 80.4 on NExT-QA and from 63.6 to 66.6 on EgoSchema. Cross-paper baselines often use different models and frame budgets. The frame-saving and accuracy claims therefore apply to these tested pipelines, not arbitrary VLMs or tasks.

5.3 Results on Ego4D LongVideo QA

Seven annotators add answers and distractors to Ego4D queries; the resulting QA dataset has tiny, dev and test subsets. Table 6 reports tiny/test performance for both context clips and full videos, with GPT-4o and Qwen2.5-VL [2]. For example, GPT-4o with 32 frames improves full-video test accuracy from 51.0 to 52.5, while Qwen2.5-VL-72B with 16 frames rises from 50.6 to 52.8. Full-video and clip inputs answer different context-budget questions and should not be combined into one metric.

6 Analysis

The analysis examines heuristic complexity, temporal score refinement and the final-frame budget.

6.1 Time and Cost Complexity of T*

The main text incorrectly states logarithmic worst-case complexity. Appendix B instead gives linear O(L) worst-case search, logarithmic best case, and a heuristic average scaling with inverse branch-selection probability. The cost equation separately counts grounding VLM calls and grid-detector calls. Thus logarithmic efficiency depends on a useful heuristic and simplifying assumptions, rather than holding for every video.

Equation 8
C=NVLM⋅CVLM⏟Grounding Overhead+NYOLO-world⋅CYOLO-world⏟Matching Overhead,C=\underbrace{N_{\text{VLM}}\cdot C_{\text{VLM}}}_{\text{Grounding Overhead}}+\underbrace{N_{\text{YOLO-world}}\cdot C_{\text{YOLO-world}}}_{\text{Matching Overhead}}, (8)

6.2 Sampling Iteration Dynamics

Figure 3 shows three examples whose sampling scores increasingly emphasize annotated times, including separated events in one video. These qualitative trajectories illustrate the mechanism; they do not establish convergence or complete event recovery.

Original PDF illustration S6.F3
Figure 3: Sampling weight dynamics over iterations for example videos. Ground truth frames are marked in red. Sampling weights progressively focus on ground truth frames across iterations (1, 11, and 21), indicating improved model alignment with keyframes over time. Notably, due to the efficient sampling in temporal search, our model can simultaneously zoom in and focus on distantly located key frames (e.g., around 50s and 100s in the top plot).

6.3 Effect of Search Frame Count on Accuracy

Figure 4 compares uniform sampling, T* and human-selected oracle frames across output budgets. T* approaches the oracle around 64 frames in this plot, but all curves deteriorate at the largest shown count. More frames do not monotonically improve the answering model, and oracle parity on this comparison is not equivalent to human-level video understanding.

Original PDF illustration S6.F4
Figure 4: Performance improvement with increasing search frames. T* consistently enhances accuracy and reaches near-human oracle performance at 64 frames.

7 Related Work

T* joins work on efficient long-context video models and frame selection, with direct supervision/evaluation of the search stage.

Long-form Video Understanding.

Video attention, compression and token/frame selection reduce long-context costs. T* complements these model-level approaches by selecting inputs and evaluating their correspondence with human evidence frames.

Temporal Localization and Temporal Search.

Temporal localization predicts segment boundaries, while the present task can select separated frames. Caption-based retrieval and keyframe methods supply relevant alternatives, including VideoAgent and moment-retrieval methods [7].

Needle in a Haystack.

Needle-in-a-haystack tests often insert synthetic target content. LV-Haystack instead uses natural scenes and real questions, though its reference frames remain a finite annotation of potentially multiple valid evidence sets.

8 Conclusion

The central result is that object-guided spatial search over video-frame grids can improve fixed-budget QA while reducing search cost relative to the tested expensive search baseline. LV-Haystack exposes a substantial remaining gap in temporal evidence overlap. The method’s practical value is supported by these experiments, while the complexity and reporting inconsistencies limit stronger claims.

Limitations

Sparse frames are unsuitable when answering requires dense motion, broad global context or many events. The method ignores audio and subtitles, depends on visual object grounding, and can miss evidence outside the detected target vocabulary. Annotation/split ambiguities, incomplete closed-model cost accounting and only two repeat runs for one experiment constrain reproducibility and uncertainty estimates.

Appendix

The appendix preserves sensitivity studies, complexity assumptions, repeated results, training details, annotation procedures and all three original prompts.

Appendix A Ablation Study

Ablations test grounding resources, grid and threshold choices, alternative similarity metrics and correlations with final QA.

A.1 Ablation on Question Grounding

Increasing the grounding model from 7B to 72B raises reported grounding compute from 26.9 to 148.5 TFLOPs but QA only from 59.8 to 59.9. Increasing the 7B grounding input from eight to 32 frames costs 108.2 TFLOPs and reaches 60.3. These small gains motivate the cheaper eight-frame 7B default; they should not be confused with Table 3’s differently reported overall accuracy.

Grounding VLM Frames TFLOPs Visual F1 QA Acc
LLaVA-OneVision-7B 8 26.9 59.9 59.8
LLaVA-OneVision-72B 8 148.5 60.6 59.9
LLaVA-OneVision-7B 32 108.2 60.7 60.3

Table 7: Impact of VLM size and initial frame count on question grounding and search effectiveness on LV-Haystack. Experimental settings are aligned with the baseline setup reported in Section 4 (main paper). Our results indicate that increasing the resources for question grounding results in marginal improvements in search effectiveness (<1<1% gain in QA Acc.).

A.2 Ablation on Searching Algorithm

Grid size trades cell detail and iterations: Figure 5 shows the lowest step count around size eight, while larger grids lose accuracy and can increase steps. Raising the return threshold generally improves QA but sharply increases search work at high values. The default is an 8 × 8 grid with threshold 0.6; neither choice is an optimum established across all datasets.

Original PDF illustration A1.F5
Figure 5: Grid Size Impact on Search Performance. The red line represents the average number of search iterations for different image grid configurations, while the blue line shows the performance on the LongVideoBench [72] XL subset using 8 frames and the LLaVA-72B as the downstream QA model.
Original PDF illustration A1.F6
Figure 6: Impact of Return Threshold θ\theta. The graph clearly illustrates the trade-off between threshold settings and search performance: lower thresholds result in quicker searches but may reduce accuracy, while higher thresholds enhance accuracy at the expense of increased search steps and computational cost.

A.3 Ablation on Searching Utility Metrics

CLIP [51] feature similarity is tested as a semantic evidence metric. Its F1 values cluster around 87.9–89.2 across methods, offering little separation, so temporal and SSIM measures remain primary. Semantic or visual closeness alone should not be read as proof that a selected frame contains the answer.

Method Frames↓\downarrow Haystack-Ego4D
Temporal Visual Semantic
Precision ↑\uparrow Recall ↑\uparrow F1F_{1} ↑\uparrow Precision ↑\uparrow Recall ↑\uparrow F1F_{1} ↑\uparrow Precision ↑\uparrow Recall ↑\uparrow F1F_{1} ↑\uparrow
Baselines: Static Frame Sampling
Uniform [72] 8 1.0 3.4 1.6 58.0 63.0 60.2 87.2 89.3 88.2
Uniform [72] 32 1.1 14.8 2.0 58.5 65.6 61.5 87.3 90.4 88.8
Baselines: Adaptive Frame Selection
VideoAgent [68] 10.1 1.7 5.8 2.7 58.0 62.4 59.9 87.0 88.9 87.9
Retrieval-based 8 1.2 4.2 1.9 58.5 61.7 59.9 87.3 88.7 88.0
Retrieval-based 32 1.0 13.8 1.9 58.5 65.4 61.4 87.3 90.5 88.9
Ours: T∗T^{*} for Zooming In Temporal Search
Attention-based 8 2.2 7.5 3.3 58.4 62.5 60.2 87.3 89.1 88.1
Training-based 8 1.4 4.9 2.1 58.0 61.5 59.6 87.2 89.0 88.0
Detector-based 8 1.7 5.8 2.7 63.8 70.1 66.8 87.2 88.9 87.9
Detector-based 32 1.8 26.3 3.4 62.9 76.2 68.9 87.2 91.4 89.2

Table 8: Results of searching utility on LV-Haystack. Best results for the 8-frame setting are underlined, and best results for the 32-frame setting are in bold. We include semantic metric (detailed in Appendix A.3) for ablation. Scores range closely from 87.9 to 89.2, showing limited differentiation across methods compared to temporal and visual metrics.

A.4 Correlation between Search Utility and Video Understanding

Temporal F1 has Pearson correlation 0.901 with QA (p = 0.037); temporal precision has Spearman correlation 0.975 (p = 0.005). The remaining coefficients and p-values are preserved. These small comparative correlations are associations, not causal evidence or a validated general-purpose predictor of downstream success.

Metric Pearson
Correlation
Pearson
p-value
Spearman
Correlation
Spearman
p-value
Temporal F1F_{1} 0.901 0.037 0.700 0.188
Temporal Precision 0.828 0.084 0.975 0.005
Visual F1F_{1} 0.829 0.083 0.600 0.285
Temporal Recall 0.655 0.231 0.700 0.188
Visual Recall 0.568 0.317 0.500 0.391
Visual Precision 0.327 0.591 0.100 0.873
Table 9: Pearson and Spearman correlations (with p-values) between search utility metrics and downstream task accuracy. The highest correlations are highlighted in bold for Temporal F1F_{1} and Temporal Precision, suggesting they are strong predictors of effective video understanding performance.

Appendix B Complexity Analysis on T*

The simplified tree analysis assumes one target frame, an n × n grid with branching factor b, and a branch scorer selecting the correct branch with probability P. For uninformative scoring, worst-case work is O(L); perfect scoring gives O(log_b L). With independent successful attempts costing 1/P per level, the claimed average is O(log_b L/P). These assumptions abstract away multiple targets, grounding mistakes, image resolution, verification, interpolation and model-call cost.

The four video-length groups show substantial empirical variation. For videos longer than 3,000 seconds, search ranges from five to 161 iterations, averaging 41.5. The illustrated b-ary traversal and complete distributions are retained; they do not establish a universal logarithmic bound. This appendix’s linear worst case contradicts the main analysis.

Original PDF illustration A2.F7
Figure 7: Illustration of the T* search process on a bb-ary tree. The video duration is 3.6k seconds, and the target white trash appears between 1532 and 1539 seconds. Numbers in the figure indicate the visited intervals of nodes, while the lines indicate the visited nodes and the search trajectory.
Equations 9–13
Tworst=𝒪⁡(L),T_{\text{worst}}=\mathcal{O}(L), (9)
Tbest=𝒪⁡(logb⁡L),T_{\text{best}}=\mathcal{O}(\log_{b}L), (10)
m=logb⁡L,m=\log_{b}L, (11)
E⁡[N]=m×1P,E[N]=m\times\frac{1}{P}, (12)
Tavg=𝒪⁡(logb⁡LP),T_{\text{avg}}=\mathcal{O}\left(\frac{\log_{b}L}{P}\right), (13)
Original PDF illustration A2.F8
Figure 8: Empirical results on search complexity of T*. We show the number of iterations of T∗T^{*} on the LongVideoBench dataset, dividing videos with lengths between 0 and 4000 seconds into four groups. The figure shows the generally required intensity of iterative search as the length of videos vary.

Appendix C Detail Analysis on LongVideoBench

Table 10 repeats T* twice and gives means with standard deviations. At eight frames on XLong, GPT-4o is 51.6 ± 1.4 and LLaVA-72B is 55.3 ± 1.3; the surrounding appendix prose instead says 51.55 ± 0.35 and 55.25 ± 0.25. The discrepancy is unresolved. With 32 frames, the table reports 53.3 ± 1.2 and 62.6 ± 1.2, differing slightly from the main table’s single values. Two runs provide limited uncertainty information, and no paired significance analysis is given. GPT-4o’s undisclosed parameter count does not support the prose’s model-size comparison with 72B LLaVA.

   LongVideoBench   
   Model and Size       #Frame       Video Length   
   XLong       Long       Medium       Short   
   15-60min       2-10min       15-60s       8-15s   
   GPT4o       8       47.1       49.4       67.3       69.7   
   GPT4o + T*       8       51.6 ±\pm 1.4       51.7 ±\pm 1.7       72.9 ±\pm 1.2       70.2 ±\pm 0.2   
   LLaVA-OneVision-72B       8       53.7       57.4       74.1       73.0   
   LLaVA-OneVision-72B + T*       8       55.3 ±\pm 1.3       63.5 ±\pm 1.2       76.6 ±\pm 1.3       73.7 ±\pm 0.2   
   GPT4o       32       50.5       57.3       73.5       71.4   
   GPT4o + T*       32       53.3 ±\pm 1.2       59.2 ±\pm 1.2       74.3 ±\pm 0.0       71.4 ±\pm 0.0   
   LLaVA-OneVision-72B       32       56.5       61.6       77.4       74.3   
   LLaVA-OneVision-72B + T*       32       62.6 ±\pm 1.2       63.9 ±\pm 1.2       79.3 ±\pm 0.0       74.6 ±\pm 0.0   

Table 10: Detailed downstream task evaluation results for T∗T^{*} as an additional frame selection module for VLMs on LongVideoBench. The metric is QA accuracy (%). We run T* two times and report the average accuracy and standard deviation ( ±\pm ).

Appendix D Implementation Details

Implementation details specify grounding, the three search variants, the adapted baseline and the answering setup.

D.1 Implementation of Training-free T*

The default training-free path grounds objects once, then uses iterative detection or attention to guide search.

Question Grounding:

LLaVA-OneVision-7B receives eight uniformly spaced frames and the question-grounding prompt preserved in Figure 12.

Iterative Temporal Search:

The grid is 8 × 8 and the verification threshold is 0.6. Attention scoring sums last-layer attention to target objects in a 72B model; smaller models or shallower layers reportedly underperformed the baseline. This expensive variant stops after three iterations.

Downstream Question Answering:

The main downstream experiments use the official GPT-4o API and LLaVA-OneVision-72B implementation. Figure 13 retains the exact answer-letter prompt.

D.2 Implementation of Trainable T ∗

Trainable T* replaces YOLO’s detection head with a single-layer MLP that scores grid cells. It samples K frames from those scores, obtains QA feedback, and defines reward as selected-frame accuracy minus uniform-frame accuracy. Equation 16 sums reward-weighted cross-entropy between predicted scores and binary cell-selection labels across Monte Carlo samples; it is an RL-inspired scoring objective, not a squared-error loss. Positive rewards favor sampled selections and negative rewards discourage them.

The prose describes averaging accuracy across samples while the equation weights each sample by its own reward; the exact estimator and Monte Carlo sample count are not fully specified here. Training uses short NExT-QA videos and evaluation includes unseen longer videos. At inference the learned scores guide search without online QA reward. Training and experiments use a cluster of eight H800 GPUs; this is not a claim of single-device latency.

Equations 14–16
𝒞,ℬ←ScoreFunction​(G,𝒯)=MLP(YOLO​(G,𝒯)​).\mathcal{C},\mathcal{B}\leftarrow\text{ScoreFunction}(G,\mathcal{T})=\text{MLP(YOLO}(G,\mathcal{T})\text{)}. (14)
reward=VLM​(Kselected,Q)−VLM​(Kuniform,Q),\text{reward}=\text{VLM}(K_{\text{selected}},Q)-\text{VLM}(K_{\text{uniform}},Q), (15)
loss=∑i=1M(rewardi×CrossEntropy​(𝒞,𝒞i)),\text{loss}=\sum_{i=1}^{M}\left(\text{reward}_{i}\times\text{CrossEntropy}(\mathcal{C},\mathcal{C}_{\text{i}})\right), (16)

D.3 Implementation of the baseline VideoAgent

The baseline adapts VideoAgent’s caption/retrieval pipeline to long-video haystacks. The appendix says BLIP-Large [30] is replaced with “CLIP-1B,” yet lists both clip-vit-large-patch14 and blip-image-captioning-large as used components. This ambiguous description and the omitted closed GPT-4 FLOPs should be considered when interpreting relative efficiency.

D.4 Video QA Implementation

LLaVA-OneVision-72B is the common answering model for the search comparison. The broader downstream tables also include GPT-4o and Qwen, so the appendix’s statement of uniform LLaVA use does not describe every reported experiment.

Original PDF illustration A4.F9
Figure 9: Annotation Interface for Videos. This interface allows annotators to answer questions based on video clips by keyframe annotations. Annotators can navigate to specific videos and questions using the provided controls (Video / Question ID). The current question is displayed with the recommended time range identified by the Ego4D dataset. Annotators can select key video frames and delete or modify annotations. A text box is available for entering answers based on observed video content.

D.5 Implementation of Different Search Strategies

Retrieval exhaustively scores frames with YOLO and returns the top eight. Zooming starts with a coarse grid and increases temporal/spatial detail in promising regions. Trainable search learns grid scores on NExT-QA and iterates three times by default, again returning eight frames. The complete qualitative selection example is retained; its favorable outcome is illustrative rather than a measured guarantee of diversity.

Original PDF illustration A4.F10
Figure 10: The visualization of frame selection results demonstrates the effectiveness of our approach compared to baseline methods. Our method consistently identifies more relevant and temporally diverse keyframes, capturing important frames that directly address the question. In contrast to baseline approaches which may select redundant or less informative frames, our strategy achieves better coverage of key events while maintaining temporal coherence across the video sequence.

Appendix E Data Annotation Details

The two subsets reuse established datasets to evaluate natural egocentric and allocentric video search. The annotation process differs substantially between them.

E.1 Haystack-LVBench

Haystack-LVBench reuses validation-set frame positions and answers from LongVideoBench, excludes subtitle-dependent questions, and selects what the appendix calls the 3,600-second duration group. Its 114 videos and 342 questions match Table 1, but that table lists an average 14.1-minute duration. The duration-group interpretation and the main section’s claim of timestamp refinement are not clarified here.

E.2 Haystack-Ego4D

For Ego4D, annotators watch context clips, choose evidence frames and answer questions. Recommended time windows help navigation, but annotators are instructed to watch the full clip to capture event order or repeated events. They can flag unanswerable questions and give reasons. Questions/interface are translated into Chinese using googletrans, and answers translated back to English.

A random audit of 100 QA pairs found two obvious errors. This small audit does not measure inter-annotator agreement, translation error, evidence minimality or all possible valid frame sets. The 1,324 clips are derived from 988 originals, so clip counts and original-video counts should remain separate.

Appendix F Data Annotation Interface

The interface supports video/question navigation, recommended time ranges, frame selection/deletion and free-text answers. Figure 9 preserves the full interface. Figure 11 preserves the complete question, choices, timeline and both eight-frame selections for the metal-cylinder example.

Original PDF illustration A6.F11
Figure 11: Comparison of uniform sampling and T* sampling for long-format video understanding. In this example, the task involves identifying a “metal cylinder” in an hour-long video. Uniform sampling fails to include relevant frames, as it randomly selects 8 frames across the video. In contrast, T* sampling dynamically selects frames containing the metal cylinder, providing the necessary visual context for effective understanding.

Appendix G Qualitative Analysis

In the illustrated hour-long video, uniform selection misses the metal cylinder while T* concentrates on relevant moments and supplies useful visual evidence. The source loosely calls uniform sampling random; the baseline elsewhere is specified as uniform sampling. The example supports the intended mechanism without quantifying failure frequency.

Appendix H Prompt Design

All three prompts are retained as PDF-faithful images with the original text available below them.

H.1 Prompt for Question Grounding

Grounding requests two comma-separated lists: key objects needed for the answer and nearby contextual cue objects. It includes the question and options alongside video frames.

Original PDF illustration A8.F12
Figure 12: The template of a question grounding prompt T*. <system prompt> is the default system instruction from  LLaVA and the <image> are PIL.Image objects for each frame and other text elements are strings.
Original prompt text
<system prompt>
Here is a video:
<image>
<image>
<image>
...
Here is a question about the video:
Question: <Question>
Options: <Options>

When answering this question about the video:
1. What key objects to locate the answer?
 - List potential key objects (short sentences, separated by commas).
2. What cue objects might be near the key objects and might appear in the scenes?
 - List potential cue objects (short sentences, separated by commas).

Please provide your answer in two lines, directly listing the key and cue objects, separated by commas.

H.2 Prompt for Question Answering

Answering requests only the option letter for a multiple-choice question, given the selected video frames and choices.

Original PDF illustration A8.F13
Figure 13: The template of a question answering prompt.
Original prompt text
<system prompt>
Select the best answer to the following multiple-choice question based on the video.
<image>
<image>
<image>
...
Question: <Question>
Options: <Options>

Answer with the option letter from the given choices directly.

H.3 Prompt for Distractor Generation

The distractor template supplies the question and correct answer and requests four plausible but incorrect alternatives with related context, category or characteristics. This prompt appears without a figure number in the PDF and was missing from the extracted section prose; it is restored in full.

Original PDF illustration A8.prompt-distractors
Original unnumbered distractor-generation prompt from Appendix H.3.
Original prompt text
<system prompt>
You are an expert in creating challenging multiple-choice questions.
For the question: <question> with the correct answer <answer> generate 4 plausible but incorrect distractors that are closely related to the correct answer in context, category, or characteristics, making the question more challenging.
Ensure that the distractors could reasonably seem correct to someone who is unsure of the answer.
The output format should be:
"1. \"<Distractor 1>\"",
"2. \"<Distractor 2>\"",
"3. \"<Distractor 3>\"",
"4. \"<Distractor 4>\"".

Broad Impact

Suggested applications include video indexing, summarization, training and surveillance, with keyframe supervision potentially supporting broader video models. Lower FLOPs suggest a route to reduced compute use, but no energy or emissions measurements establish sustainability gains. Compatibility with any model or task, real-time use, and reliable deployment in high-stakes applications are proposed possibilities rather than demonstrated results.

Concept demonstration

Open image ↗