# VideoAtlas: Navigating Long-Form Video in Logarithmic Compute

arXiv: https://arxiv.org/abs/2603.17948 · HTML: https://mlsanity.com/paper/2603.17948/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 25 references that are in the map.
- First posted on arXiv 18 Mar 2026.

## Builds on (most cited first, 19 of 19)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Qwen3-VL Technical Report](https://mlsanity.com/paper/2511.21631/) (2025)
- [InternVL: Scaling up Vision Foundation Models and Aligning for Generic Visual-Linguistic Tasks](https://mlsanity.com/paper/2312.14238/) (2023)
- [Video-MME: The First-Ever Comprehensive Evaluation Benchmark of Multi-modal LLMs in Video Analysis](https://mlsanity.com/paper/2405.21075/) (2024)
- [ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Tools](https://mlsanity.com/paper/2406.12793/) (2024)
- [OpenAI GPT-5 System Card](https://mlsanity.com/paper/2601.03267/) (2025)
- [LongVideoBench: A Benchmark for Long-context Interleaved Video-Language Understanding](https://mlsanity.com/paper/2407.15754/) (2024)
- [VideoAgent: Long-form Video Understanding with Large Language Model as Agent](https://mlsanity.com/paper/2403.10517/) (2024)
- [Visual Sketchpad: Sketching as a Visual Chain of Thought for Multimodal Language Models](https://mlsanity.com/paper/2406.09403/) (2024)
- [VideoTree: Adaptive Tree-based Video Representation for LLM Reasoning on Long Videos](https://mlsanity.com/paper/2405.19209/) (2024)
- [A Simple LLM Framework for Long-Range Video Question-Answering](https://mlsanity.com/paper/2312.17235/) (2023)
- [Recursive Language Models](https://mlsanity.com/paper/2512.24601/) (2025)
- [Deep Video Discovery: Agentic Search with Tool Use for Long-form Video Understanding](https://mlsanity.com/paper/2505.18079/) (2025)
- [An Image Grid Can Be Worth a Video: Zero-shot Video Question Answering Using a VLM](https://mlsanity.com/paper/2403.18406/) (2024)
- [WorldMM: Dynamic Multimodal Memory Agent for Long Video Reasoning](https://mlsanity.com/paper/2512.02425/) (2025)
- [VideoARM: Agentic Reasoning over Hierarchical Memory for Long-Form Video Understanding](https://mlsanity.com/paper/2512.12360/) (2025)
- [Vote-in-Context: Turning VLMs into Zero-Shot Rank Fusers](https://mlsanity.com/paper/2511.01617/) (2025)

## Built on by (most cited first, 1 of 1)

- [GridProbe: Posterior-Probing for Adaptive Test-Time Compute in Long-Video VLMs](https://mlsanity.com/paper/2605.10762/) (2026)

## Abstract (arXiv)

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.