PaperlayerView exact revision on arXiv

Source-linked AI summary

VideoAtlas: Navigating Long-Form Video in Logarithmic Compute

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

arXiv:2603.17948v1cs.CVcs.AI

TL;DR

Long-form video understanding lacks a lossless, scalable way to represent and recursively inspect visual context, since existing methods rely on sampling or text-based compression. VideoAtlas provides a navigable hierarchical grid and Video-RLM uses it for parallel recursive exploration, yielding logarithmic compute growth and robust performance as videos scale from 1 to 10 hours.

  • Problem

    Existing long-video methods use lossy visual approximations or convert video into text, limiting lossless visual access during long-context reasoning.

  • Method

    VideoAtlas represents video and agent evidence as a lossless hierarchical image grid, while Video-RLM applies parallel Master-Worker recursive exploration within this environment.

  • Results

    Video-RLM remains the most duration-robust method from 1-hour to 10-hour benchmarks, while hierarchical compute grows logarithmically and achieves 30-60% multimodal cache hit rates.

  • Takeaways & Limitations

    Structured visual navigation provides a scalable paradigm for video understanding with depth-controlled budgeting and adaptive compute allocation.

  • Takeaways & Limitations

    Performance remains constrained by the backbone VLM, with failures including perception errors, premature sufficiency, and text latching; anchor-free queries can also require extra exploration rounds.

Abstract

from arXiv · show

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 \textbf{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 \textbf{VideoAtlas} provides. \textbf{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.

1. Introduction

Long-form video understanding must find sparse evidence across massive temporal spaces without sacrificing visual fidelity. VideoAtlas addresses this with a lossless, navigable hierarchical grid and Video-RLM, enabling logarithmic access and cache-efficient recursive reasoning.

  • Motivation: An hour of video contains 90,000 frames at 25 fps, while query answers may occupy only a few seconds.Efficient understanding therefore requires locating task-relevant regions before examining them closely.
  • Motivation: Existing methods trade temporal coverage, frame fidelity, or recoverability of visual details when relying on sampling, grids, captions, or text-based agent memory.Uniform sampling can miss short events, while text conversion prevents later reasoning from recovering overlooked visual information.
  • VideoAtlas: VideoAtlas is designed to be lossless, navigable, scalable, caption-free, and preprocessing-free, avoiding the coverage-versus-fidelity tradeoff of uniform sampling.Each grid image remains full resolution, and the agent zooms only into regions requiring further inspection.
  • VideoAtlas: VideoAtlas represents video as a navigable K×K hierarchical image grid whose EXPAND action reaches sub-second temporal precision in O(log T) steps.The same grid representation stores the video, intermediate investigations, and the agent’s lossless multimodal evidence memory.
  • VideoAtlas: Structural reuse of root grids and overlapping sub-grids produces 30-60% multimodal cache hit rates, reducing effective GPU compute.The cache benefit arises because exploration rounds naturally reuse hierarchical grid regions.
  • Video-RLM: Video-RLM extends Recursive Language Models to video through parallel Master-Worker exploration within VideoAtlas.The Master coordinates global exploration while Workers recursively investigate assigned regions and accumulate lossless visual evidence.

2. Related Work

Prior long-video methods address frame limits, temporal coverage, or adaptive search separately, but their intermediate representations remain lossy or text-based. VideoAtlas fills the missing role of a lossless, visually navigable environment with structurally controlled temporal resolution.

  • Long-Form Video Understanding: Uniform sampling misses short events because practical frame budgets create very large temporal strides and can force lower per-frame resolution.At 64 frames in an hour, the stride is approximately 56 seconds per frame.
  • Long-Form Video Understanding: Composite grids improve token efficiency but remain fixed, lossy snapshots that do not resolve coverage gaps between sampled frames.Grids alleviate context packing without providing arbitrary-moment access by construction.
  • Caption-Based Approaches: Caption-based systems scale reasoning through text summaries, but visual observations are converted into text before planning and subsequent reasoning cannot recover omitted details.This makes captions the primary intermediate reasoning medium rather than raw visual evidence.
  • Agentic, Hierarchical, and Memory Approaches: Agentic systems provide hierarchical search tools and multimodal memories, yet store intermediate evidence as captions, summaries, or compressed embeddings rather than raw frames.Consequently, they do not provide lossless, navigable access to arbitrary video moments by construction.
  • Long Context as the Core Challenge: Recursive Language Models offer lossless recursive access for long text, but visual recursion requires an environment that agents can navigate directly.Existing video environments are primarily clip databases and text-based retrieval systems; VideoAtlas is proposed to fill this gap.
  • Environment Budgeting vs. Prior Compute Adaptation: Prior adaptive methods control sampling quantity, whereas VideoAtlas controls temporal resolution through depth, providing precision calibrated to video length and query granularity.Bounding depth supplies a distinct compute-accuracy budget because each level geometrically subdivides time.

3. Methodology

VideoAtlas represents video as a recursively navigable hierarchical grid, while Video-RLM uses a parallel Master-Worker process to explore regions and accumulate visual evidence. The environment preserves visual evidence throughout navigation and memory, with logarithmic access depth and task-defined stopping.

  • VideoAtlas: VideoAtlas renders any video as a task-agnostic, navigable K×K hierarchical grid whose root provides a full-video overview.EXPAND recursively generates finer-resolution sub-grids for selected temporal regions.
  • VideoAtlas: At depth d, temporal resolution is Δt_d = T/K2(d+1), and any frame is reachable in at most ⌈logK2(T · fps)⌉ navigation steps.Sub-grids are generated on the fly without offline preprocessing, and agents interact with raw frames at every level.
  • VideoAtlas: The environment exposes navigation, perception, and commit actions, including EXPAND, ZOOM, temporal INVESTIGATE, and scratchpad updates.State-dependent action masking removes invalid actions such as EXPAND below the temporal threshold or BACKTRACK at the root.
  • Memory: Positive memory stores lossless multimodal evidence as labeled visual grids, while negative memory marks irrelevant intervals as visually masked dead zones.The shared visual representation covers the video, intermediate investigations, and the agent’s evidence scratchpad.
  • Video-RLM: VideoAtlas is formalized as a Markov Decision Process with task-defined rewards and independently explorable subtrees that support parallel search.The final answer is synthesized from collected visual evidence rather than text summaries.
  • Video-RLM: Video-RLM runs recursive exploration in rounds: a Master assigns promising cells, Workers navigate their regions in parallel, and memory is updated before sufficiency-based stopping.Workers support DFS for local detail and BFS for evidence distributed across the video; traversal is selected from query characteristics.

4. Experiments

Experiments evaluate Video-RLM on standard and constructed 10-hour long-video benchmarks against proprietary, open-source, sampling, caption-based, and agentic baselines. Video-RLM remains comparatively robust as duration increases, while depth, question granularity, and worker parallelism shape compute and efficiency.

  • Experimental Setup: Experiments use LongVideoBench and Video-MME, plus 10-hour concatenated variants that place each queried source video among distractors.Video-MME evaluations omit subtitles to test visual exploration under a stricter setting.
  • Standard Benchmarks: Video-RLM achieves competitive standard-duration accuracy with 3B active parameters and zero-shot visual navigation, without intermediate captioning or text representations.With Gemini, Video-RLM reaches 72.0% on LVB versus 74.5% for Gemini-3-Flash direct performance.
  • Extended Duration: Video-RLM remains duration-robust on 10-hour videos: Gemini reaches 70.1% on LVB-10hr with near-zero degradation of -1.9%.On VMME-10hr, Qwen drops only 0.7%, compared with 13.2% for uniform sampling and 28.2% for captions.
  • Error Analysis: Failure analysis identifies perception errors, premature sufficiency, and text latching as model-dependent error modes.Accuracy improves substantially when switching from Qwen to Gemini without changing VideoAtlas.
  • Extended Duration: At 10 hours, Video-RLM uses 148K effective tokens versus over 1.4M for caption-based processing while maintaining comparable accuracy.Hierarchical depth grows logarithmically, and sufficiency-based stopping avoids captioning every clip.
  • Environment Budgeting: Accuracy rises from 30% at root-only depth to 43.3% at d=2, after which deeper exploration plateaus; maximum depth therefore controls compute-accuracy tradeoffs.The first sub-second layer is used in practice, adapting with video duration from d=1 for 1-minute videos to d=2 for 10-hour videos.
  • Adaptive Compute and Scaling: Scattered-answer questions consume 40% more tokens than localized questions, using 322K versus 230K tokens through emergent adaptive allocation.Increasing workers from 1 to 7 reduces wall-clock time from 588s to 257s, a 2.25× speedup, while accuracy remains 40-47%.

5. Limitations

The paper identifies backbone-dependent perception and reasoning failures, exploration overhead without obvious anchors, limited evaluation scope, and zero-shot-only operation as principal limitations.

  • Evaluation and agent scope: Figure 4 frames maximum exploration depth as a compute-accuracy control and shows adaptive token allocation based on evidence spread.The plotted quantities are accuracy and tokens versus depth, and average tokens versus evidence spread.
  • Backbone and exploration limitations: Backbone-dependent failures include perception errors, premature sufficiency, and text latching.These errors are described as environment-independent and improve substantially with a stronger VLM.
  • Backbone and exploration limitations: Without a visually obvious root-grid anchor, the agent may need additional exploration rounds to locate relevant regions.The Master progressively mitigates this as newly collected evidence improves later cell assignments.
  • Evaluation and agent scope: The evaluation validates VideoAtlas on multiple-choice question answering, while temporal grounding, summarization, and anomaly detection remain empirically un demonstrated.The MDP supports these tasks by changing the reward signal, but the paper does not evaluate them.
  • Evaluation and agent scope: The MDP is solved entirely through zero-shot VLM reasoning, leaving reinforcement-learning-based exploration for future work.The discrete finite action space is presented as directly compatible with methods such as PPO and DQN.

6. Conclusion

VideoAtlas reframes video understanding as navigation in a hierarchical environment, while Video-RLM uses parallel exploration to gather visual evidence. The conclusion highlights logarithmic compute growth, depth-based budgeting, and adaptive allocation as the formulation’s main properties.

  • 6. Conclusion: VideoAtlas reframes video understanding as navigation within a formally defined hierarchical environment, and Video-RLM operates there as a parallel Master-Worker agent.The conclusion presents both as the paper’s central formulations.
  • 6. Conclusion: The formulation yields logarithmic compute growth with video duration, principled budgeting through depth control, and emergent adaptive compute allocation.These are identified as three structural properties emerging from the formulation.
  • 6. Conclusion: A 25-minute FIFA World Cup Final highlight reel containing 90,117 frames is used for an end-to-end Video-RLM trace.Figures 6–8 show the pipeline stages for answering a yellow-card-count question.
  • 6. Conclusion: The initial 8×8 root grid covers the full 25-minute video at roughly 23 seconds per cell, while 8 exploration rounds black out 24 of 64 cells.The explored regions account for 4.7% of total frames.
  • 6. Conclusion: After 8 exploration rounds, the lossless visual scratchpad contains 51 timestamped frames paired with natural-language descriptions.Its entries include yellow-card events and contextual match evidence.

A. Detailed Error Analysis

A backbone-disagreement analysis separates environment failures from backbone limitations and finds that the stronger backbone is usually correct.

  • A. Detailed Error Analysis: Across LongVideoBench-Long and VideoMME-Long, the two backbones disagree on 522 cases, with the stronger backbone correct in 423 cases.The 423 cases represent 81% of the disagreements.

A.1. VLM Perception Errors

The detailed analysis describes perception and reasoning failures involving fine-grained visual attributes, inconsistent descriptions, surface-text matching, and premature commitment. These failures are largely backbone-dependent and improve with a stronger VLM.

  • A.1. VLM Perception Errors: The agent can reach the correct temporal region but misperceive its visual content.The analysis identifies attribute confusion and cross-frame inconsistency as two sub-patterns.
  • A.1. VLM Perception Errors: Attribute confusion causes errors in fine-grained colors, materials, spatial relationships, or on-screen text despite correct scene and entity identification.Such errors are especially common when one distinguishing visual feature determines the answer.
  • A.1. VLM Perception Errors: Cross-frame inconsistency produces contradictory descriptions of the same scene, after which the backbone may select one arbitrarily.The example descriptions vary between purple/pink, white against blue, and blue.
  • A.2. Surface-Text Latching: Surface-text latching anchors reasoning to a phrase that matches a candidate answer without contextual verification.This is particularly problematic when documentary or educational narration uses candidate-answer keywords rhetorically.
  • A.3. Early Evidence Anchoring: Early evidence anchoring commits the agent to the first plausible item and can prevent integration of later contradictory or refining evidence.The Master’s sufficiency mechanism may declare evidence sufficient after a single supporting item.
  • A.4. Impact of Backbone Quality: Switching to a stronger VLM resolves most of these errors without architectural changes, with a 4:1 to 5:1 win ratio across both benchmarks.The result supports a direct relationship between performance and backbone capability.

B. Per-Category Accuracy Breakdown

Video-RLM performance varies by question type, reasoning level, and topic on the reported LongVideoBench splits. Sequence questions are the hardest, and extending videos to 10 hours disproportionately reduces perception accuracy compared with relation reasoning.

  • Evaluation Axes: Tables 4–6 report accuracy breakdowns by question type, reasoning level, and topic for LVB-Long and LVB-10hr.The supplied passages identify the evaluation axes but do not provide the remaining table entries.
  • Question Type: Sequence-type questions are hardest, with SSS accuracy at 21.4% and SAA accuracy at 33.3%.These questions require ordering multiple events across the full video, combining broad coverage with temporal precision.
  • Reasoning Level: At 10 hours, L1-Perception accuracy drops 9.6 points from 59.4% to 49.8%.The reported decline is larger than for L2-Relation reasoning.
  • Reasoning Level: At 10 hours, L2-Relation accuracy drops 2.7 points from 47.6% to 44.9%.This smaller decline contrasts with the reported perception degradation.

C. Compute Breakdown

Video-RLM concentrates computation in parallel Worker exploration while keeping Master coordination comparatively lightweight. As duration increases, Worker effort grows substantially but remains far below linear scaling, with repeated visual prefixes also benefiting from multimodal caching.

  • Architecture: Workers perform the bulk of visual exploration tokens, while the Master uses a small fraction for probing, uncertainty analysis, and final decisions.This division reflects the parallel Master–Worker architecture, with the Master coordinating and Workers exploring assigned regions.
  • Duration Scaling: At 10 hours, Worker tokens increase 80% from 121K to 219K, while Master tokens increase 10% from 27.5K to 30.4K.The additional Worker cost corresponds to deeper exploration, increasing from 2.0 to 2.3 rounds.
  • Duration Scaling: The 10× duration increase produces a sub-linear compute increase, while evidence items rise modestly from 6.2 to 7.2.The passage attributes the additional Worker cost to deeper exploration needed to locate evidence in longer videos.
  • Caching: Repeated grid views during DFS exploration create multimodal prefix reuse that vLLM serves through automatic KV-cache hits.The caching mechanism operates without code changes, and Table 8 reports hit rates across video durations.
  • Prompted Control: The pipeline includes zero-shot prompt templates reused unchanged across benchmarks and video durations.The supplied implementation passages also describe text-only query conversion, Master cell ranking, Worker actions, and final evidence evaluation.

D.3. Master: Uncertainty Analysis

The Master analyzes exploration progress after each round to determine whether evidence is sufficient and how exploration should continue. Its uncertainty analysis evaluates each answer choice and can trigger targeted exploration or noise removal before finalization.

  • Uncertainty Analysis: After each evidence-gathering round, the Master performs a sufficiency check, proposes exploration, and erases unrelated noise.It suggests unexplored grid cells or custom time ranges and preserves partial evidence when relevance is uncertain.
  • Uncertainty Analysis: For each answer choice, the Master checks whether the collected evidence is sufficient before choosing FINAL_DECISION or CONTINUE.The decision output includes reasoning, with continued exploration specifying regions and optional evidence to erase.
Loading 2603.17948v1…