VideoAtlas: Navigating Long-Form Video in Logarithmic Compute

Mohamed Eltahir; Ali Habibullah; Yazan Alshoibi; Lama Ayash; Tanveer Hussain; Naeemullah Khan

cs.CVMar 18, 2026

VideoAtlas: Navigating Long-Form Video in Logarithmic Compute

Authors: Mohamed Eltahir, Ali Habibullah, Yazan Alshoibi, Lama Ayash, Tanveer Hussain, Naeemullah Khan

Organizations: King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia · Department of Computer Science, King Khalid University (KKU), Abha, Saudi Arabia · Department of Computer Science, Edge Hill University, Ormskirk, England

Abstract

Extending language models to video introduces two challenges: representation, where existing methods rely on lossy approximations, and long-context, where caption- or agent-based pipelines collapse video into text and lose visual fidelity. To overcome this, we introduce VideoAtlas, a task-agnostic environment to represent video as a hierarchical grid that is simultaneously lossless, navigable, scalable, caption- and preprocessing-free. An overview of the video is available at a glance, and any region can be recursively zoomed into, with the same visual representation used uniformly for the video, intermediate investigations, and the agent's memory, eliminating lossy text conversion end-to-end. This hierarchical structure ensures access depth grows only logarithmically with video length. For long-context, Recursive Language Models (RLMs) recently offered a powerful solution for long text, but extending them to visual domain requires a structured environment to recurse into, which VideoAtlas provides. VideoAtlas as a Markov Decision Process unlocks Video-RLM: a parallel Master-Worker architecture where a Master coordinates global exploration while Workers concurrently drill into assigned regions to accumulate lossless visual evidence. We demonstrate three key findings: (1)~logarithmic compute growth with video duration, further amplified by a 30-60% multimodal cache hit rate arising from the grid's structural reuse. (2)~environment budgeting, where bounding the maximum exploration depth provides a principled compute-accuracy hyperparameter. (3)~emergent adaptive compute allocation that scales with question granularity. When scaling from 1-hour to 10-hour benchmarks, Video-RLM remains the most duration-robust method with minimal accuracy degradation, demonstrating that structured environment navigation is a viable and scalable paradigm for video understanding.

Figures & tables

Figure 1: Logarithmic compute scaling with video duration. Video-RLM’s hierarchical grid grows sub-linearly (

O(\log T)

), requiring up to 9.7

\times

fewer tokens than linear-scaling baselines. A uniform VLM maxes out its 256K context trading off sampled frame count with resolution.

Method	Caption-Free	Lossless	$\infty$ Context	Parallel
VLM (Uniform)	✓	✗	✗	✗
LLoVi [ 24 ]	✗	✗	✗	✗
MR.Video [ 12 ]	✗	✗	✗	✓
VideoARM [ 22 ]	✗	✗	✗	✗
DVD [ 25 ]	✗	✗	✗	✗
Ours	✓	✓	✓	✓

Table 1: Comparison of long-video QA methods. “Caption-Free” = no text captions used as intermediate representation. “Lossless” = no information lost between input and reasoning. “

\infty

Context” = can handle arbitrarily long videos without context overflow. “Parallel” = workers explore concurrently.

Figure 2: The VideoAtlas Environment . (Left) The state space is a hierarchical grid stack $S_{0},S_{1},\ldots,S_{D}$ , where $S_{0}$ is the root grid covering the entire video of duration $T$ . Each grid has $K^{2}$ cells. Deeper levels $d$ provide finer temporal resolution $\Delta t_{d}=T/K^{2(d+1)}$ . (Top Right) The discrete action space $\mathcal{A}$ is divided into navigation (e.g., Expand to $S_{t+1}$ ), perception, and commit actions. (Bottom Right) The visual scratchpad memory $\mathcal{M}^{+}$ accumulates multimodal evidence (images, timestamps, QA pairs) across exploration rounds.

Figure 3: Video-RLM overview. The query is converted into a search task. In each round $r$ , the Master examines the root grid $S_{0}$ (with dead zones masked) and the scratchpad $\mathcal{M}^{+}$ , then assigns promising cells to Workers. Each Worker autonomously explores its assigned region via navigation, perception, and commit actions. After all Workers return, $\mathcal{M}^{+}$ and $\mathcal{M}^{-}$ are updated. The Master performs an uncertainty analysis: if evidence is sufficient, the final answer is produced. Otherwise, a new round begins.

Proprietary Models
Method	Active	LVB	VMME
GPT-4o [ 9 ]	Prop.	66.7	65.3
GPT-5 [ 14 ]	Prop.	72.6	81.8
Gemini-3-Flash [ 16 ]	Prop.	74.5	—
Claude-Opus-4.5 [ 1 ]	Prop.	67.2	77.6
Open-Source VLMs

Table 2: Video QA accuracy (%) on the standard (Long) subsets. LVB: LongVideoBench. VMME: Video-MME (no subs).

LVB-10hr
Method	Acc.	$\Delta$	Avg. Tokens
Qwen3.5 (uniform)	49.2	-12.3	212K
LLM over Captions ∗	62.1	-0.3	207K ‡
Video-RLM (Qwen)	47.7	-4.8	146K †
Video-RLM (Gemini)	70.1	-1.9	307K
VMME-10hr (no subs)

Table 3: 10-hour variant: accuracy (%) and average tokens per question.

\Delta

: accuracy drop from standard benchmarks ( Tab. 2 ).

Figure 4: (a) Environment budgeting: accuracy and tokens vs. max depth on subset of LVB-10hr (temporal span annotated). Green: optimal depth (first sub-second layer). (b) Adaptive compute: average tokens scale with evidence spread without ground-truth supervision.

Figure 5: Wall-clock time (normalized to equal workload) vs. number of workers 30 questions sampled from LVB-10hr. Accuracy (annotated) remains stable across all configurations.

Panel of Figure 6 — Figure 6: Navigation grid before and after exploration. (a) The Master’s initial 8 $\times$ 8 root grid provides a temporal overview of the full 25-minute video; each cell covers $\sim$ 23 s. (b) After 8 DFS rounds, explored regions are blacked out (24 of 64 cells), visually showing the coverage pattern. The system explored 4.7% of total frames.

Figure 7: Final evidence scratchpad. The system’s lossless visual memory after 8 rounds of exploration: 51 collected frames with burned-in labels [A]-[AY], each paired with a timestamp and natural-language description. Representative entries include “[D] @86.3 s: Referee shows yellow card to Marcus Thuram (Minute 18),” “[O] @371.1 s: Referee gives yellow card to Enzo Fernández (39 ′ ),” Not all items are yellow-card events: the scratchpad also captures contextual evidence such as match score overlays, player close-ups, and celebration scenes, enabling the Master to cross-reference events against the full match timeline. This grid image is passed directly to the Master for the final decision.

Figure 8: Exploration trace. Condensed log of the 8-round DFS exploration. The Master probes the root grid and dispatches 3 parallel Workers (W) per round to the highest-scored Cells (C). Workers use Zoom , Investigate , Expand , and Backtrack to drill into their assigned regions and collect evidence via Add_to_Scratchpad . After each round, the Master runs an uncertainty analysis to decide whether to continue or declare sufficiency. Evidence grows from 0 to 51 items across 8 rounds (97 VLM calls, 449K tokens), with the Master declaring Final_Decision after identifying 8 distinct yellow card events, which is the correct answer.

	LVB-Long		LVB-10hr
Question Type	$n$	Acc	$n$	Acc
S2A	30	66.7	27	63.0
T2E	33	63.6	33	60.6
S2E	42	61.9	42	50.0
S2O	33	60.6	33	42.4
O3O	30	60.0	–	–

Table 4: Accuracy (%) by question type. Categories present only in one split are marked with –.

Level	$n$	Acc	$n$	Acc
	LVB-Long		LVB-10hr
L1 – Perception	234	59.4	207	49.8
L2 – Relation	330	47.6	147	44.9

Table 5: Accuracy (%) by reasoning level.

Topic	$n$	Acc	$n$	Acc
	LVB-Long		LVB-10hr
Cooking-Recipes	42	64.3	30	56.7
Knowledge-Geography	54	63.0	45	46.7
Travel-Guides	54	61.1	30	53.3
Knowledge-STEM	75	54.7	48	52.1
Knowledge-History	69	53.6	42	54.8

Table 6: Accuracy (%) by topic category.

Panel of Figure 9 — Figure 9: Representative backbone failure cases. Top: Perception error: the lightweight backbone cannot perceive a clearly visible host wearing red and concludes the entity does not exist; the stronger backbone identifies both hosts and reasons about their spatial relationship. Bottom: Surface-text latching: the lightweight backbone matches a rhetorical narrator phrase to a candidate answer with high confidence; the stronger backbone synthesizes broader evidence to identify the underlying scientific explanation. Both runs use identical VideoAtlas configurations.

Benchmark	Master	Worker	Total	Checks	Rounds	Items
	Avg. Tokens			Suff.	Expl.	Evid.
LVB-Long	28K	121K	149K	1.8	2.0	6.2
LVB-10hr	30K	219K	250K	1.9	2.3	7.2

Table 7: Average per-question compute breakdown for Video-RLM (Qwen3.5, 3B active).

LongVideoBench
Duration	Avg. Hit Rate (%)	Std. (%)
1 min	60.9	7.0
10 min	48.2	7.1
1 hr	42.7	7.5
3 hr	50.7	12.4
5 hr	48.9	11.2

Table 8: vLLM multimodal prefix cache hit rates for Qwen3.5 across video durations.

Explore similar work

LongVideo-R1: Smart Navigation for Low-cost Long Video Understanding
Feb 24, 2026Jihao Qiu, Lingxi Xie, Xinyue Huo +2Long-Video Understanding Long-Video QA
University of Chinese Academy of Sciences · Huawei Consumer Business Group
Temporal Tree of Thought: Reasoning-Guided Visual Cue Search for Long-Video Understanding
Aug 28, 2026Ziling Huang, Shin'ichi SatohLong-Video Understanding Long-Video QA
National Institute of Informatics
Small Vision-Language Models are Smart Compressors for Long Video Understanding
Apr 9, 2026Junjie Fei, Jun Chen, Zechun Liu +13Long-Video Understanding Video Token Compression
Meta AI · King Abdullah University of Science and Technology (KAUST)

Feb 24, 2026J/K move · Enter open · S save

LongVideo-R1: Smart Navigation for Low-cost Long Video Understanding

Jihao Qiu, Lingxi Xie, Xinyue Huo, Qi Tian+1

University of Chinese Academy of Sciences · Huawei Consumer Business Group

Long-Video Understanding Long-Video QA VLM Reasoning Query-Aware Video Frame Selection

Open paper AskPDF arXiv

This paper addresses the critical and underexplored challenge of long video understanding with low computational budgets. We propose LongVideo-R1, an active, reasoning-equipped multimodal large language model (MLLM) agent designed for efficient video context navigation, avoiding the redundancy of exhaustive search. At the core of LongVideo-R1 lies a reasoning module that leverages high-level visual cues to infer the most informative video clip for subsequent processing. During inference, the agent initiates traversal from top-level visual summaries and iteratively refines its focus, immediately halting the exploration process upon acquiring sufficient knowledge to answer the query. To facilitate training, we first extract hierarchical video captions from CGBench, a video corpus with grounding annotations, and guide GPT-5 to generate 33K high-quality chain-of-thought-with-tool trajectories. The LongVideo-R1 agent is fine-tuned upon the Qwen-3-8B model through a two-stage paradigm: supervised fine-tuning (SFT) followed by reinforcement learning (RL), where RL employs a specifically designed reward function to maximize selective and efficient clip navigation. Experiments on multiple long video benchmarks validate the effectiveness of name, which enjoys superior tradeoff between QA accuracy and efficiency. All curated data and source code are provided in the supplementary material and will be made publicly available. Code and data are available at: https://github.com/qiujihao19/LongVideo-R1

Abstract

Explore similar work

LongVideo-R1: Smart Navigation for Low-cost Long Video Understanding

Temporal Tree of Thought: Reasoning-Guided Visual Cue Search for Long-Video Understanding

Small Vision-Language Models are Smart Compressors for Long Video Understanding