TL;DR
Video-STR enhances multimodal large language models (MLLMs) in fine-grained video spatio-temporal reasoning by teaching them to infer explicit inter-object relation graphs during their internal chain-of-thought. Trained via Group Relative Policy Optimization (GRPO) with verifiable geometric rewards on a new 205k-sample dataset (STV-205k), Video-STR achieves a 13% relative boost over its base model on STI-Bench and outperforms commercial baselines like GPT-4o on spatio-temporal benchmarks without degrading general video understanding.
What Problem Does This Paper Address?
While MLLMs excel at high-level video semantics (e.g., summarizing an action or identifying scene categories), they frequently fail at fine-grained spatial and temporal reasoning. Downstream applications like robotics, embodied AI, and virtual reality require precise awareness of 3D object layouts, motion trajectories, and relative spatial configurations across time.
Recent attempts to train reasoning MLLMs using Reinforcement Learning with Verifiable Rewards (RLVR) typically reward models using either 2D pixel bounding boxes or 2D planar grid maps. Both have major drawbacks:
- Pixel localization is bound to the 2D image plane and fails to capture 3D physical arrangements.
- 2D grid maps rely on camera-centric coordinates that are sensitive to ego-motion and camera viewpoint shifts.
Methods
Video-STR addresses these issues by framing spatio-temporal reasoning around rotation-invariant, inter-object relation graphs:
- Graph-Guided Thinking Process: During generation, the model is prompted to build an explicit scene graph inside its
<think>tags before answering. Vertices represent objects (with estimated coordinates and classes), while edges capture pairwise Euclidean distances ($d_{ij}$) and relative angles ($\theta_{ij}$). Because edges model inter-object relationships rather than camera-to-object vectors, the topological representation is robust against viewpoint changes. - Verifiable Reward Suite:
- Graph Similarity Reward ($R_{graph}$): Evaluates predicted nodes ($R_n$) and edges ($R_e$) against ground-truth multi-object 3D layouts across video frames.
- Task-Specific Correctness ($R_{ans}$): Employs exact match for multi-choice ($R_{mc}$), relative numerical accuracy ($R_{num}$), and Intersection-over-Union ($R_{IoU}$) for spatial intervals.
- Format and Length Penalties ($R_{format}, R_l$): Enforces correct tag formatting and penalizes both underthinking and excessive verbosity.
- RLVR Training via GRPO: Built upon Qwen2.5-VL-7B-Instruct, Video-STR optimizes policy parameters using Group Relative Policy Optimization (GRPO), eliminating the need for a separate critic network.
Input Video + Query
──> Model Thinking: Generate Relation Graph (Nodes: Objects, Edges: Relative Distances/Angles)
──> Verifiable Rewards: R_graph + R_ans + R_format + R_l
──> GRPO Policy Update
Datasets
- STV-205k (Introduced): A newly built dataset of 205,000 question-answer pairs derived from three foundational vision datasets:
- TAO: Dynamic multi-object tracking.
- KITTI: Autonomous driving / outdoor 3D spatial scenes.
-
ScanNet: Richly annotated indoor 3D scenes. Covers 8 core tasks spanning static spatial reasoning (object counting, relative direction/distance, 3D localization, object sizes) and dynamic temporal reasoning (appearance order, displacement, motion tracking).
-
Evaluation Benchmarks: Evaluated across spatio-temporal suites (STI-Bench, V-STaR), spatial suites (VSI-Bench, SPAR-Bench), temporal suites (Video-MME, TempCompass), and general video understanding (LongVideoBench).
Key Insights and Ideas
- Inter-object topology beats ego-centric mapping: Pairwise relationships between objects remain consistent regardless of camera translation and rotation, offering a mathematically invariant supervision target for spatial reasoning.
- RLVR generalizes where SFT memorizes: Supervised fine-tuning (SFT) showed minor localized gains but degraded general video benchmarks. In contrast, RLVR boosted spatial and temporal reasoning while preserving general video understanding (improving slightly from 54.0% to 54.3% on LongVideoBench).
- Edge supervision matters most: In ablation experiments, removing the edge reward ($R_e$) caused the sharpest drop in benchmark accuracy, proving that learning relative relational geometry—rather than isolated object localization—is key to spatial reasoning.
Key Results
- Spatio-Temporal Benchmarks: On STI-Bench, Video-STR reached 39.3%, outpacing the Qwen2.5-VL-7B base model (34.7%) by ~13% relative and surpassing GPT-4o (34.8%). On V-STaR, it achieved 37.8% (vs. base 35.2%).
- Spatial Benchmarks: Achieved 46.5% on VSI-Bench (up from 33.0% base) and 37.9% on SPAR-Bench (up from 33.1% base).
- Numerical Robustness: When multiple-choice tasks were converted into raw numerical queries to eliminate guessing, Video-STR achieved 40.2% on STI and 48.4% on VSI, consistently beating SpaceR and the base model.
Limitations and Future Work
- Frame and Resolution Constraints: Due to compute overhead during RL rollouts, training was restricted to 16 sampled frames at low resolution ($128 \times 28 \times 28$), before scaling to 32 frames at $448 \times 28 \times 28$ during inference.
- Scenario Diversity: While STV-205k covers common indoor and autonomous driving environments, extending the framework to more intricate real-world interactions, long-horizon manipulation, and additional sensor modalities remains open for future research.
Summary updated