AgentRVOS: Reasoning over Object Tracks for Zero-Shot Referring Video Object Segmentation

1. Problem Definition

Referring Video Object Segmentation (RVOS) is the task of generating dense segmentation mask tracks for a specific target object throughout a video, based on a natural language query.

• Challenges: Unlike static image segmentation, RVOS requires handling complex temporal dynamics, including object motion, state changes, and inter-object relationships. Queries often go beyond simple appearance descriptions (e.g., "the person who stands up after sitting" or "the car that turns left").
• Limitations of Existing Training-Free Methods: Current zero-shot approaches typically rely on Multimodal Large Language Models (MLLMs) to select keyframes and ground objects, followed by a video segmentation model (like SAM2) to propagate masks.
  • Temporal Blindness: MLLMs often process only sparsely sampled frames due to token limits, causing them to miss objects that appear briefly or intermittently.
  • Reasoning vs. Perception Trade-off: MLLMs excel at reasoning but struggle with precise spatio-temporal perception. Conversely, segmentation models excel at perception but lack the semantic reasoning to interpret complex queries.
  • Pipeline Flaw: Existing methods force the MLLM to make temporal decisions before reliable object-level evidence is available, leading to poor reasoning quality and incomplete coverage.

2. Methodology: AgentRVOS

AgentRVOS is a training-free agentic pipeline that synergistically combines SAM3 (a video segmentation model) and an MLLM. It operates on the principle of "Complementary Strengths": SAM3 provides dense, frame-level perception, while the MLLM performs query-grounded reasoning over the resulting object tracks.

The pipeline consists of two main phases:

Phase 1: Candidate Mask Track Generation

Instead of asking the MLLM to select frames, the system uses the MLLM to extract concepts from the query, which are then fed to SAM3 to generate mask tracks for the entire video.

• Concept Extraction: The MLLM analyzes the query to determine if it is a Referring Query (target identifiable by text alone, e.g., "the cat") or a Reasoning Query (target requires visual context, e.g., "the one moving fastest").
  • It extracts Core Concepts (specific nouns) and Broader Concepts (general categories) to ensure high recall.
  • Iterative Retry: If SAM3 fails to detect objects with the initial concepts, the MLLM iteratively refines or broadens the concepts (e.g., changing "silver car" to "vehicle") until candidates are generated.
• SAM3 Processing: SAM3 processes all frames of the video using the extracted concepts, generating temporally consistent mask tracks. This ensures that even small, occluded, or briefly appearing objects are captured, providing a comprehensive pool of candidates ($M$).

Phase 2: Iterative Spatio-temporal Pruning

The MLLM reasons over the candidate pool to identify the target, but unlike previous methods, it does so iteratively to manage complexity.

• Iterative Classification: In each iteration, the MLLM examines the current candidate tracks (visualized with masks overlaid) and classifies each as:
  • Accepted: Confidently matches the query.
  • Rejected: Confidently does not match.
  • Uncertain: Requires more evidence.
• Spatio-temporal Pruning:
  • Candidate Pruning: Accepted tracks are saved; Rejected tracks are discarded. Only Uncertain tracks proceed to the next iteration.
  • Temporal Scope Pruning: The system dynamically narrows the temporal window. It restricts the next iteration's analysis only to the frames where the remaining Uncertain candidates exist.
• Convergence: The process repeats, progressively reducing the candidate set and the temporal scope, until no uncertain candidates remain. This allows the MLLM to focus its reasoning power on the most ambiguous cases with high-density visual evidence.

Auxiliary Component (Appearance Tool): To handle queries relying on color or texture (which might be obscured by mask overlays), an optional "Appearance Tool" extracts detailed visual descriptions of candidates before pruning begins.

3. Key Contributions

1. AgentRVOS Pipeline: A novel training-free framework that delegates object detection and temporal localization to SAM3, allowing the MLLM to focus exclusively on complex reasoning over structured object-level evidence.
2. Iterative Spatio-temporal Pruning: A strategy that decomposes the complex selection problem into simpler steps. By progressively narrowing the candidate set and the temporal scope based on SAM3's existence information, the MLLM avoids the "sparse frame" limitation and focuses on high-ambiguity cases.
3. State-of-the-Art Performance: The method achieves superior results across multiple benchmarks without requiring any task-specific fine-tuning.

4. Experimental Results

The authors evaluated AgentRVOS on three major benchmarks: MeViS (motion-centric), ReVOS (reasoning-centric), and ReasonVOS (world knowledge).

• Performance: AgentRVOS significantly outperforms existing training-free methods (e.g., CoT-RVS, AL-Ref-SAM2) and even surpasses many training-based methods.
  • On MeViS, it achieved a $\mathcal{J}\&\mathcal{F}$ score of 73.1 (using GPT-5), a massive improvement over the previous best training-free method (CoT-RVS with GPT-4o at 52.2).
  • On ReVOS and ReasonVOS, it similarly achieved top-tier results, demonstrating robustness in reasoning and temporal understanding.
• Ablation Studies:
  • Concept Extraction Retry: Crucial for preventing failure when initial concepts miss objects.
  • Iterative Pruning: Removing the iterative process causes a significant drop in performance, confirming the need to focus reasoning on uncertain candidates.
  • Temporal Scope Pruning: Restricting the temporal window to uncertain candidates improves reasoning density and accuracy.
• Generalizability: The pipeline works consistently with various MLLM backbones (Qwen3-VL, GPT-5), showing that the architecture itself, rather than just the model size, drives performance.

5. Significance

• Paradigm Shift: AgentRVOS challenges the standard "MLLM selects frames $\to$ Segmentation" pipeline. It proves that offloading the heavy lifting of spatio-temporal perception to a dedicated vision model (SAM3) allows MLLMs to function more effectively as reasoning engines.
• Zero-Shot Efficiency: It achieves state-of-the-art results without the computational cost and data requirements of training-based models, making it highly scalable and adaptable to new MLLMs.
• Robustness to Temporal Complexity: By leveraging SAM3's ability to process the entire video, AgentRVOS solves the critical issue of missing short-duration objects that plague frame-sampling-based MLLM approaches.

In summary, AgentRVOS effectively bridges the gap between precise video perception and high-level semantic reasoning, setting a new benchmark for zero-shot video object segmentation.