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

Sep 20, 2026cs.CV

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

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.

Siru Zhong, Qiongyan Wang, Xiaohui Lv +5

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

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

Ask PDF

Jul 3, 2026cs.CV

Incentivizing Vision Language Models to Search for Long Video Question Answering

We introduce VSeek, an agentic framework that transforms long-video question answering (LVQA) from a passive, single-pass perception task into a multi-turn retrieval process. VSeek utilizes a natural language-driven search to identify relevant context within long videos and is post-trained with reinforcement learning (RL) to jointly formulate targeted search queries and reason over retrieved clips for LVQA. While RL post-training has revolutionized reasoning in symbolic domains such as mathematics and code, its application to long-video understanding remains hindered by a lack of verified rewards. To ensure that the retrieved context is relevant, we propose a novel neuro-symbolic approach that bridges open-ended natural language with discrete visual verification. Specifically, complex user queries are compiled into formal temporal logic specifications for systematically decomposing natural language questions into a definitive checklist of required atomic visual primitives, such as key objects and activities, along with their temporal ordering. These systematically derived grounding events provide the critical feedback signal for RL post-training, enabling dense, verifiable rewards based on the successful retrieval of these specific visual elements rather than relying entirely on outcome-only answer accuracy. By explicitly optimizing for this verifiable evidence-seeking behavior, VSeek improves Pass@1 scores by up to 8% and Pass@4 scores by 15% on long-video understanding benchmarks compared to base models. We open-source our code at https://utaustin-swarmlab.github.io/VSeek.

Harsh Goel, S P Sharan, Sahil Shah +4

The University of Texas at Austin, Austin, TX, USA

Long Video Question Answering Video Understanding Question

Ask PDF

Sep 14, 2026cs.CV

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

Multimodal Large Language Models (MLLMs) have achieved remarkable progress on short video understanding yet remain limited on long videos due to the limited visual context window. Prevailing approaches rely on uniform frame sampling or recent coarse-to-fine agentic zooming, both of which struggle to localize sparse, decisive evidence in sufficiently long videos. We formulate long video understanding as a \textbf{Sequential Evidence Acquisition (SEA)} problem, in which an agent reads the video turn by turn along the temporal axis, deciding at each turn how fast to watch, what evidence to retain, when to revisit uncertain segments, and when to stop and answer. Inspired by this view, we propose \textbf{VideoScout}, a multi-turn reasoning agent that instantiates the SEA paradigm through adaptive reasoning pacing. Specifically, by dynamically controlling the viewing pace, VideoScout enables efficient traversal of long videos within a bounded visual context window, allowing the agent to access more video content while balancing content analysis depth with reading efficiency. To train VideoScout, we construct VideoScout-66K, a set of over 66K high-quality exploration turns from 10K answer-verified trajectories, and adopt a two-stage pipeline: cold-start supervised fine-tuning teaches the agent per-turn output format, while the Decoupled Clip and Dynamic sAmpling Policy Optimization (DAPO) algorithm performs trajectory-level reinforcement learning with a composite reward that jointly considers answer accuracy, output format compliance, and the temporal alignment between the agent's viewing progress and the teacher's answer timing measured by intersection-over-union (IoU). Extensive experiments on long video understanding and reasoning benchmarks demonstrate that our 7B model achieves strong performance compared with existing trained 7B agentic models.

Weixin Xu, Zhenyu Yang, Bing Wang +2

Video Understanding Multimodal Large Language Models Agentic Discovery

Ask PDF