LazySloth: Bounded LLM-based Lazy Tree Search for Fast Long Video Comprehension

Arka Mukherjee; Kaleen Shrestha; Larissa Zhu; Maja Matarić

cs.CVSep 29, 2026

LazySloth: Bounded LLM-based Lazy Tree Search for Fast Long Video Comprehension

Authors: Arka Mukherjee, Kaleen Shrestha, Larissa Zhu, Maja Matarić

Organizations: School of Computer Engineering, Kalinga Institute of Industrial Technology (KIIT) Bhubaneswar · Computer Science Department, Viterbi School of Engineering, University of Southern California

Abstract

Modern vision-language models (VLMs) have shown promising results in long-video understanding due to the rich semantic information they can capture. However, most methods focus on coarse captioning of extracted image frames that are computationally inefficient and require models with large context windows. While past work has explored efficient methods through multimodal retrieval-augmented generation (RAG), they rely on lossy embeddings that lose temporal context and fine-grained detail. Few works to date have investigated how VLM-based query-relevant information retrieval can be optimized. We introduce LazySloth, an efficient tree-based search method that speeds up video comprehension and retrieval tasks 2.9-8.3x (compared to existing agentic methods) through bounded captioning of portions of the video considered irrelevant by a VLM of the video. Compared to contemporary specialized video-understanding VLMs and RAG-based methods, LazySloth achieved similar or better final task accuracy across two recent open-source base VLMs--Gemma 4 31B and Qwen3.6 27B--across four benchmarks. LazySloth reduced the gap between the base open-source model and a closed-source model, GPT-4o. Ablations showed that replacing VLM scene understanding with CLIP-based retrieval cost 8.8-19.9% in accuracy, while lazy tree construction matches eager construction at a fraction of the captioning cost. With LazySloth, we demonstrate the possibility of faster long-video comprehension without substantial loss in performance.

Figures & tables

Figure 1: Overview of how LazySloth bounds captioning. Each level captures more fine-grained information, with the parent root representing all of the video. Grayed-out nodes are never visited, which reduces the total time to navigate through the hierarchical tree.

Figure 2: Overview of the LazySloth pipeline. (A) Corpus creation, which produced an ordered list of frames after applying optional uniform frame sampling to the input video. (B) Hierarchical frame bunching, which initialized the first few levels of the search tree. (C) Lazy generation of tree nodes by the captioner VLM $C$ . (D) Agentic Direct Corpus Interaction (DCI), where the search VLM $S$ explored the tree with backtracking to traverse alternative branches. (E) Final answer prediction by the reasoner VLM (R), conditioned on the textual evidence and representative frames collected during the search.

	Video- MME	LongVideo Bench	LV Bench	Ego Schema
Source	YouTube	Web	YouTube	Ego4D
Domain	6 domains	Multi-topic	Longform	Egocentric
# Videos	900	753	103	500
# Questions	2,700	1,337	1,549	500
# Options	4	4–5	4	5
Avg. length (min)	17.0	7.9	67.3	3.0

Table 1: Long-video comprehension benchmarks used in our evaluation: Video-MME ( Fu et al. 2025 ) , LongVideoBench ( Wu et al. 2024 ) , LVBench ( Wang et al. 2025a ) , and EgoSchema ( Mangalam, Akshkulakov, and Malik 2023 ) . All four are multiple-choice and scored by exact match. The suite spans web, film/television, and egocentric content, and in total, we evaluate almost 500 hours of video.

	Accuracy (%)
Method	Video-MME (w/o subs)	LongVideo Bench	LV Bench	Ego Schema
Random baseline	25.0	21.3	25.0	20.0
Direct inference (64 frames)
GPT-4o ‡	71.9	66.7	48.9	72.2
Qwen 3.6 27B	45.7	31.8	27.7	38.4
Gemma 4 31B	65.8	52.8	40.7	65.4

Table 2: Accuracy results on four long video-understanding benchmarks. Bold marks the best open-source result per benchmark; underline marks the second-best open-source result. † Numbers sourced from Yeo et al. (2026) . ‡ GPT-4o numbers are taken from the public leaderboards of the respective benchmarks; we do not report a newer GPT release, as none could be located on the maintained leaderboards.

Figure 3: Efficiency comparison of LazySloth, a brute-forced eager tree, VideoLucy, and WorldMM by median seconds per video (log y, broken above the working band) on LVBench, which was chosen as it has the longest videos in our test corpus. Bootstrapped 95% confidence intervals are plotted at each video length value. All methods shared the Qwen3.6-27B reasoner and Nemotron captioner.

Figure 4: WorldMM vs VideoLucy vs LazySloth median wall clock time per video on LVBench decomposition by captioning, reasoning, and other (I/O, etc.). VideoLucy spends a lot of time captioning; WorldMM spends a lot on reasoning. Our method optimizes both frontiers for the lowest total time.

Figure 5: Comparing the accuracy difference between LazySloth and direct inference across benchmarks and models with respect to search tree depth.

Figure 6: Accuracy with respect to the caption budget used by the tree search with Qwen3.6 27B, where

budget=1

root

+

4

seed branches

+

4

per successful DRILL

+

4

per EXPAND . Beyond a single descent into the tree, accuracy declined across all benchmarks.

Figure 7: Analysis of temporal localization on correctly answered LongVideoBench questions that were annotated with specific timestamps. Blue: the portion where LazySloth’s final window contained the referenced span. Gray: the rate expected from placing a window of the same width at random, averaged per question.

	Accuracy (%)
Configuration	Video-MME	LongVideoBench	LVBench	EgoSchema
LazySloth	61.4	53.2	39.1	73.9
Scene understanding (CLIPScore, greedy best-first)
lazy top-down tree	41.5	40.5	27.2	55.6
eager bottom-up tree	43.4	42.1	30.3	56.4

Table 3: Ablation study of LazySloth with Qwen3.6 27B. Group (a) varies the memory structure while keeping VLM-based scene understanding; group (b) replaces VLM captioning and search with a frozen CLIP encoder that scores each tree node by CLIPScore and navigates by greedy BFS.

Dataset	Searcher (%)	Reasoner (%)	$\Delta$ (Reasoner $-$ Searcher)
EgoSchema	76.6	76.9	+0.3
LongVideoBench	58.6	60.8	+2.2
LVBench	42.5	41.4	$-1.1$
Video-MME	62.3	62.6	+0.2
MCQ Micro-Avg	58.0	58.3	+0.3

Table 4: Agreement between the searcher’s selected answer and the reasoner’s final answer with Qwen 3.6 27B. We observe that using a separate reasoner results in a 0.3% accuracy gain over always trusting the search model’s answer.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Tier	Dataset	“All” (31 FPS)	24 FPS	12 FPS	1 FPS
Qwen 2.5 VL 7B (Unsloth bf16 GGUF)
DFEW	C: $26.7{\scriptscriptstyle\,\pm\,}22.7$ R: $12.3{\scriptscriptstyle\,\pm\,}6.7$	C: $27.4{\scriptscriptstyle\,\pm\,}22.4$ R: $14.7{\scriptscriptstyle\,\pm\,}7.4$	C: $32.2{\scriptscriptstyle\,\pm\,}24.0$ R: $26.2{\scriptscriptstyle\,\pm\,}13.7$	C: $32.5{\scriptscriptstyle\,\pm\,}22.7$ R: $30.9{\scriptscriptstyle\,\pm\,}21.8$	$14.05{\scriptscriptstyle\,\pm\,}2.51$
CCDb-IB	C: $23.5{\scriptscriptstyle\,\pm\,}10.1$ R: $18.0{\scriptscriptstyle\,\pm\,}8.4$	C: $28.2{\scriptscriptstyle\,\pm\,}8.4$ R: $21.7{\scriptscriptstyle\,\pm\,}7.9$	C: $22.6{\scriptscriptstyle\,\pm\,}8.2$ R: $22.2{\scriptscriptstyle\,\pm\,}7.0$	C: $27.2{\scriptscriptstyle\,\pm\,}8.0$ R: $14.8{\scriptscriptstyle\,\pm\,}6.7$	$12.63{\scriptscriptstyle\,\pm\,}2.39$
CCDb-HG	C: $16.7{\scriptscriptstyle\,\pm\,}22.5$ R: $7.4{\scriptscriptstyle\,\pm\,}10.0$	C: $16.2{\scriptscriptstyle\,\pm\,}21.5$ R: $10.1{\scriptscriptstyle\,\pm\,}13.5$	C: $16.8{\scriptscriptstyle\,\pm\,}20.4$ R: $13.9{\scriptscriptstyle\,\pm\,}12.9$	C: $20.1{\scriptscriptstyle\,\pm\,}23.8$ R: $17.8{\scriptscriptstyle\,\pm\,}13.7$	$16.73{\scriptscriptstyle\,\pm\,}2.74$
CCDb+	C: $54.4{\scriptscriptstyle\,\pm\,}20.7$ R: $20.1{\scriptscriptstyle\,\pm\,}12.1$	C: $59.8{\scriptscriptstyle\,\pm\,}25.5$ R: $22.7{\scriptscriptstyle\,\pm\,}12.1$	C: $60.7{\scriptscriptstyle\,\pm\,}25.1$ R: $30.2{\scriptscriptstyle\,\pm\,}12.2$	C: $56.7{\scriptscriptstyle\,\pm\,}19.9$ R: $57.5{\scriptscriptstyle\,\pm\,}10.5$	$49.87{\scriptscriptstyle\,\pm\,}3.35$
SEMPI	C: $32.7{\scriptscriptstyle\,\pm\,}15.4$ R: $1.2{\scriptscriptstyle\,\pm\,}2.6$	C: $44.8{\scriptscriptstyle\,\pm\,}18.3$ R: $3.4{\scriptscriptstyle\,\pm\,}3.9$	C: $43.2{\scriptscriptstyle\,\pm\,}17.7$ R: $35.4{\scriptscriptstyle\,\pm\,}11.3$	C: $54.0{\scriptscriptstyle\,\pm\,}19.5$ R: $56.3{\scriptscriptstyle\,\pm\,}15.4$	$50.07{\scriptscriptstyle\,\pm\,}3.62$

Appendix

Table 5: Per quantization

\times

sampling-strategy estimates of accuracy (%) for Qwen 2.5 VL 7B and Gemma 4 E4B. Each video cell reports Constrained (C) and Reasoning (R) settings as mean

\pm

std; image-based datasets are frame-independent and span all sampling columns.

Model	CLIP Score $\uparrow$	SigLIP Score $\uparrow$	Avg. length (words)	Latency (s) $\downarrow$
google/gemma-4-12b	0.2447	0.1367	32.6	1.27
qwen/qwen3.6-27b	0.2435	0.1403	31.4	2.29
google/gemma-4-31b	0.2417	0.1348	29.1	2.70
qwen/qwen3.5-9b	0.2417	0.1402	31.5	0.92
qwen2.5-vl-7b-instruct	0.2341	0.1292	27.7	0.98
nvidia/nemotron-3-nano-omni	0.2331	0.1340	25.1	0.59

Appendix

Table 6: Reference-free caption quality of the candidate frozen captioners

C

, pooled over all evaluated datasets. Captions were generated from the same sampled frames with the identical pipeline prompt, then scored by CLIPScore ( Hessel et al. 2021 ) and a SigLIP2 cross-check. Latency is wall-clock seconds per caption. The shaded row is the captioner used in all experiments reported in this paper.

Model	Ego Schema	LongVideo Bench	MMBench Video	Movie Chat	Video MME
google/gemma-4-31b	0.236	0.239	0.246	0.248	0.238
qwen/qwen3.6-27b	0.236	0.238	0.245	0.262	0.237
google/gemma-4-12b	0.227	0.239	0.248	0.264	0.245
qwen/qwen3.5-9b	0.236	0.229	0.244	0.259	0.240
qwen2.5-vl-7b-instruct	0.229	0.230	0.230	0.256	0.226
nvidia/nemotron-3-nano-omni	0.234	0.220	0.230	0.252	0.230

Appendix

Table 7: Per-dataset CLIPScore for each candidate captioner. Rows are ordered by the pooled CLIPScore of Table 6 .

Length	LazySloth	VideoLucy	WorldMM	Brute-forced Eager	DI
40 min	149 s	509 s (3.4 $\times$ )	735 s (4.9 $\times$ )	7.0 h (169 $\times$ )	57 s
60 min	176 s	553 s (3.1 $\times$ )	1109 s (6.3 $\times$ )	10.5 h (214 $\times$ )	57 s
90 min	251 s	727 s (2.9 $\times$ )	1560 s (6.2 $\times$ )	15.8 h (226 $\times$ )	57 s
120 min	287 s	1000 s (3.5 $\times$ )	2393 s (8.3 $\times$ )	21.0 h (263 $\times$ )	57 s
140 min	307 s	936 s (3.0 $\times$ )	2371 s (7.7 $\times$ )	24.5 h (287 $\times$ )	57 s

Appendix

Table 8: Median inference time comparison across different video lengths on LVBench. Speedup is shown relative to LazySloth.

Length	LazySloth	VideoLucy	WorldMM	Brute-forced Eager
40 min	35	27 (0.8 $\times$ )	97 (2.8 $\times$ )	3,600 (103 $\times$ )
60 min	35	35 (1.0 $\times$ )	149 (4.3 $\times$ )	5,401 (156 $\times$ )
90 min	38	46 (1.2 $\times$ )	220 (5.8 $\times$ )	8,102 (215 $\times$ )
120 min	34	54 (1.6 $\times$ )	291 (8.6 $\times$ )	10,801 (320 $\times$ )
140 min	45	42 (0.9 $\times$ )	330 (7.3 $\times$ )	12,603 (280 $\times$ )

Appendix

Table 9: Median caption calls across different video lengths on LVBench. Speedup is shown relative to LazySloth with Qwen3.6 27B.

Figure 8: WorldMM vs VideoLucy vs LazySloth median captions generated per-video on LVBench. While VideoLucy doesn’t caption significantly more than LazySloth, the difference in wall clock time arises from how the two methods utilize caching and optimize multi-frame inputs to VLMs.

Figure 9: Share of questions for which LazySloth (aggregated over Qwen3.6 27B and Gemma 4 31B) chose the first, second, third, or fourth quarter of the video at the first level of the search tree. LazySloth’s first descent was strongly biased toward the start of the video (roughly twice the rate of random branch selection). The dashed reference shows an empirically measured random baseline.

Figure 10: Tree depth searched by the two tested base VLMs, Gemma 4 31B and Qwen3.6 27B, across the four datasets with LazySloth and Direct Inference. Since Direct Inference does not create trees to search in, it is scored on exactly the questions that fall in each of LazySloth’s strata.

Benchmark	Question type	$N$	LazySloth	Direct inf.	$\Delta$	McNemar $\chi^{2}$
LongVideoBench	SSS	97	38.1	12.4	+25.8	18.6 ∗
LongVideoBench	E3E	94	52.1	28.7	+23.4	13.8 ∗
LongVideoBench	S2E	93	57.0	43.0	+14.0	4.4 ∗
LongVideoBench	S2A	88	64.8	62.5	+2.3	0.0
LongVideoBench	O2E	87	50.6	42.5	+8.0	1.9
LongVideoBench	TAA	82	46.3	26.8	+19.5	7.0 ∗

Appendix

Table 10: Search gain by question type using Qwen 3.6 27B as the base VLM. LVBench and EgoSchema are omitted as they do not contain segregated question types. ∗ marks

\chi^{2}>3.84

(

p<0.05

Symbol	Meaning
$V$	Input video clip.
$Q$	Query/task (MCQ question + options, open-ended question, or classification prompt).
$L$	Label set — MCQ letters / class labels; $\varnothing$ for open-ended QA (free-text answer).
$C$	Frozen captioner VLM; only ever produces captions (kept fixed so an experiment varies only the search VLM).
$S$	Search VLM + reasoner VLM — one model in two roles: text-only navigation, then multimodal final answer.
$\phi$	Frame sampling rate, measured in FPS, used to decode the clip.

Appendix

Table 11: Notation reference for formalization of the LazySloth framework in Section 3 and Algorithm 1 .

Explore similar work

PREM: Prefix-Steered Recurrent Memory for Long-Video Understanding
Sep 20, 2026Siru Zhong, Qiongyan Wang, Xiaohui Lv +5Frozen Vision-Language Models Long-Video Benchmarks
The Hong Kong University of Science and Technology (Guangzhou) · Beta Infinity · Tsinghua University
Incentivizing Vision Language Models to Search for Long Video Question Answering
Jul 3, 2026Harsh Goel, S P Sharan, Sahil Shah +4Long Video Question Answering Video Understanding
The University of Texas at Austin, Austin, TX, USA
VideoScout: Learning Agentic Active Exploration with Adaptive Reasoning Pacing for Long Video Understanding
Sep 14, 2026Weixin Xu, Zhenyu Yang, Bing Wang +2Video Understanding Multimodal Large Language Models

Sep 20, 2026, cs.CVJ/K move · Enter open · S save

PREM: Prefix-Steered Recurrent Memory for Long-Video Understanding

Siru Zhong, Qiongyan Wang, Xiaohui Lv, Yuzheng Zhuang+4

The Hong Kong University of Science and Technology (Guangzhou) · Beta Infinity · Tsinghua University

Frozen Vision-Language Models Long-Video Benchmarks Visual Evidence Recurrent Model

Open paper AskPDF arXiv

Long-video understanding must capture transient visual evidence under strict token budgets, yet existing methods compress frames, append memory tokens, or alter internal key-value (KV) caches. We introduce Prefix-Steered Recurrent Memory (PREM), a memory-token-free framework for frozen vision-language models (VLMs). PREM separates video ingestion from query answering: a recurrent writer distills visual streams into a compact 256 KiB multi-slot associative state, while a question-conditioned readout adds memory-derived key/value (K/V) steering modulations to existing non-visual prompt prefixes during prefill. This enables write-once, query-many inference without extra prompt tokens or decoding recurrence. Across six long-video benchmarks in offline and streaming end-of-stream settings, PREM consistently outperforms frozen baselines at every evaluated visual budget. Under a constrained budget of 16 frames, PREM improves macro-average accuracy by 3.06% on Qwen2.5-VL-3B, with gains of 11.0% on action antonym identification and 9.9% on localized needle retrieval. These gains require tuning 0.24% of backbone parameters at 0.03 GiB of peak GPU memory overhead.

Abstract

Explore similar work

PREM: Prefix-Steered Recurrent Memory for Long-Video Understanding

Incentivizing Vision Language Models to Search for Long Video Question Answering

VideoScout: Learning Agentic Active Exploration with Adaptive Reasoning Pacing for Long Video Understanding