Video-STR: Reinforcing MLLMs in Video Spatio-Temporal Reasoning with Relation Graph

Wentao Wang, Heqing Zou, Tianze Luo, Guiyang Xie, Rui Huang, Yutian Zhao, Zhuochen Wang, Hansheng Zhang, Chengwei Qin, Yan Wang, Lin Zhao, Zhang huaijianSubmission to ICLR 2026 · Rejected

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:

  1. Pixel localization is bound to the 2D image plane and fails to capture 3D physical arrangements.
  2. 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

Abstract

Recent progress in Multimodal Large Language Models (MLLMs) has demonstrated strong semantic understanding capabilities, but struggles to perform precise spatio-temporal understanding. Existing spatio-temporal methods primarily focus on the video itself, while overlooking the physical information within the video, such as multi-object layouts and motion. Such limitations restrict the use of MLLMs in downstream applications that demand high precision, including embodied intelligence and VR. To address this issue, we present Video-STR, a novel graph-based reinforcement method for precise Video Spatio-Temporal Reasoning. Building upon the capacity of Reinforcement Learning with Verifiable Reward (RLVR) to improve model abilities, we introduce a reasoning mechanism using graph representation based on Group Relative Policy Optimization (GRPO) to guide the model in inferring the underlying spatio-temporal topology of scenarios during the thinking process.To resolve the lack of spatio-temporal training data, we construct the STV-205k dataset with 205k question-answering pairs, covering dynamic multi-object scenes in both indoor and outdoor environments, to support the model training. Experiments show that Video-STR achieves state-of-the-art results on various benchmarks, outperforming the base model by 13% on STI-Bench, and demonstrating the effectiveness of our approach and dataset. Code, model, and data will be released.
BibTeX
@misc{wang2025video,
  author = {Wentao Wang and Heqing Zou and Tianze Luo and Guiyang Xie and Rui Huang and Yutian Zhao and Zhuochen Wang and Hansheng Zhang and Chengwei Qin and Yan Wang and Lin Zhao and Zhang huaijian},
  title = {{Video-STR: Reinforcing MLLMs in Video Spatio-Temporal Reasoning with Relation Graph}},
  year = {2025},
  eprint = {2510.10976},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.10976},
}
Figure