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
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(logT) ), requiring up to 9.7 × 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
∞ 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. “ ∞ 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 S0,S1,…,SD , where S0 is the root grid covering the entire video of duration T . Each grid has K2 cells. Deeper levels d provide finer temporal resolution Δtd=T/K2(d+1) . (Top Right) The discrete action space A is divided into navigation (e.g., Expand to St+1 ), perception, and commit actions. (Bottom Right) The visual scratchpad memory 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 S0 (with dead zones masked) and the scratchpad M+ , then assigns promising cells to Workers. Each Worker autonomously explores its assigned region via navigation, perception, and commit actions. After all Workers return, M+ and M− are updated. The Master performs an uncertainty analysis: if evidence is sufficient, the final answer is produced. Otherwise, a new round begins.
Method
Active
LVB
VMME
Proprietary Models
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).
Method
Acc.
Δ
Avg. Tokens
LVB-10hr
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. Δ : 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.
Figure 6: Navigation grid before and after exploration. (a) The Master’s initial 8 × 8 root grid provides a temporal overview of the full 25-minute video; each cell covers ∼ 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 –.
LVB-Long
LVB-10hr
Level
n
Acc
n
Acc
L1 – Perception
234
59.4
207
49.8
L2 – Relation
330
47.6
147
44.9
Table 5: Accuracy (%) by reasoning level.
LVB-Long
LVB-10hr
Topic
n
Acc
n
Acc
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.
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.
Avg. Tokens
Suff.
Expl.
Evid.
Benchmark
Master
Worker
Total
Checks
Rounds
Items
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).
Duration
Avg. Hit Rate (%)
Std. (%)
LongVideoBench
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.
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
Jihao Qiu, Lingxi Xie, Xinyue Huo +2
University of Chinese Academy of Sciences · Huawei Consumer Business Group
Long-video understanding remains challenging for Multimodal Large Language Models (MLLMs) due to limited context length. Uniform sampling may miss crucial moments, while agent-based frame video understanding methods often evaluate frames independently, overlooking the temporal organization of videos. Ideally, evidence selection should mimic how humans answer questions about long videos: first locating the relevant segment from the global context, then zooming into local objects and details. We propose Temporal Tree of Thought T^3, a training-free framework for adaptive coarse-to-fine long-video understanding. T^3 constructs a question-agnostic hierarchical temporal tree via recursive temporally constrained clustering, where each node represents a contiguous segment with an informative key frame. During inference, T^3 performs an answer-retrieve-explore loop: it reasons over coarse representative frames, generates a search statement when evidence is insufficient, and expands relevant branches for finer-grained evidence. This process adaptively shifts the search target from temporal regions to specific objects and visual details to help video understanding. Experiments on VideoMME, LongVideoBench, and LVBench show that T^3 improves Qwen2.5-VL-7B by 0.5%, 4.6%, and 4.4%, respectively, under the same frame budget, demonstrating the effectiveness of structured temporal reasoning.
Adapting Multimodal Large Language Models (MLLMs) for hour-long videos is bottlenecked by context limits. Dense visual streams saturate token budgets and exacerbate the lost-in-the-middle phenomenon. Existing heuristics, like sparse sampling or uniform pooling, blindly sacrifice fidelity by discarding decisive moments and wasting bandwidth on irrelevant backgrounds. We propose Tempo, an efficient query-aware framework compressing long videos for downstream understanding. Tempo leverages a Small Vision-Language Model (SVLM) as a local temporal compressor, casting token reduction as an early cross-modal distillation process to generate compact, intent-aligned representations in a single forward pass. To enforce strict budgets without breaking causality, we introduce Adaptive Token Allocation (ATA). Exploiting the SVLM's zero-shot relevance prior and semantic front-loading, ATA acts as a training-free O(1) dynamic router. It allocates dense bandwidth to query-critical segments while compressing redundancies into minimal temporal anchors to maintain the global storyline. Extensive experiments show our 6B architecture achieves state-of-the-art performance with aggressive dynamic compression (0.5-16 tokens/frame). On the extreme-long LVBench (4101s), Tempo scores 52.3 under a strict 8K visual budget, outperforming GPT-4o and Gemini 1.5 Pro. Scaling to 2048 frames reaches 53.7. Crucially, Tempo compresses hour-long videos substantially below theoretical limits, proving true long-form video understanding relies on intent-driven efficiency rather than greedily padded context windows.
Junjie Fei, Jun Chen, Zechun Liu +13
Meta AI · King Abdullah University of Science and Technology (KAUST)