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

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Spatial and embodied reasoning, one of 17 directions in LLM reasoning.
- Builds on 35 of its 50 references that are in the map.
- First posted on arXiv 13 Oct 2025.

## Placed in

- LLM reasoning / [Spatial and embodied reasoning](https://mlsanity.com/lr/spatial-and-embodied-reasoning/)
- Multimodal LLMs / vision-language models / [Embodied and 3D vision-language models](https://mlsanity.com/mllm/embodied-and-3d-vision-language-models/)

## Builds on (most cited first, 30 of 35)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5-VL Technical Report](https://mlsanity.com/paper/2502.13923/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [MiniCPM-V: A GPT-4V Level MLLM on Your Phone](https://mlsanity.com/paper/2408.01800/) (2024)
- [VideoLLaMA 3: Frontier Multimodal Foundation Models for Image and Video Understanding](https://mlsanity.com/paper/2501.13106/) (2025)
- [Video-R1: Reinforcing Video Reasoning in MLLMs](https://mlsanity.com/paper/2503.21776/) (2025)
- [TempCompass: Do Video LLMs Really Understand Videos?](https://mlsanity.com/paper/2403.00476/) (2024)
- [VideoChat-R1: Enhancing Spatio-Temporal Perception via Reinforcement Fine-Tuning](https://mlsanity.com/paper/2504.06958/) (2025)
- [RL's Razor: Why Online Reinforcement Learning Forgets Less](https://mlsanity.com/paper/2509.04259/) (2025)
- [Scene-LLM: Extending Language Model for 3D Visual Understanding and Reasoning](https://mlsanity.com/paper/2403.11401/) (2024)
- [SpaceR: Reinforcing MLLMs in Video Spatial Reasoning](https://mlsanity.com/paper/2504.01805/) (2025)
- [SpatialBot: Precise Spatial Understanding with Vision Language Models](https://mlsanity.com/paper/2406.13642/) (2024)
- [Time-R1: Post-Training Large Vision Language Model for Temporal Video Grounding](https://mlsanity.com/paper/2503.13377/) (2025)
- [From Flatland to Space: Teaching Vision-Language Models to Perceive and Reason in 3D](https://mlsanity.com/paper/2503.22976/) (2025)
- [SPHINX-X: Scaling Data and Parameters for a Family of Multi-modal Large Language Models](https://mlsanity.com/paper/2402.05935/) (2024)
- [R1-Omni: Explainable Omni-Multimodal Emotion Recognition with Reinforcement Learning](https://mlsanity.com/paper/2503.05379/) (2025)
- [STI-Bench: Are MLLMs Ready for Precise Spatial-Temporal World Understanding?](https://mlsanity.com/paper/2503.23765/) (2025)
- [V-STaR: Benchmarking Video-LLMs on Video Spatio-Temporal Reasoning](https://mlsanity.com/paper/2503.11495/) (2025)
- [Multi-SpatialMLLM: Multi-Frame Spatial Understanding with Multi-Modal Large Language Models](https://mlsanity.com/paper/2505.17015/) (2025)
- [Perception-R1: Advancing Multimodal Reasoning Capabilities of MLLMs via Visual Perception Reward](https://mlsanity.com/paper/2506.07218/) (2025)
- [Depth-Breadth Synergy in RLVR: Unlocking LLM Reasoning Gains with Adaptive Exploration](https://mlsanity.com/paper/2508.13755/) (2025)
- [Agent-RLVR: Training Software Engineering Agents via Guidance and Environment Rewards](https://mlsanity.com/paper/2506.11425/) (2025)
- [Enhancing Video-LLM Reasoning via Agent-of-Thoughts Distillation](https://mlsanity.com/paper/2412.01694/) (2024)
- [SpaceVLLM: Endowing Multimodal Large Language Model with Spatio-Temporal Video Grounding Capability](https://mlsanity.com/paper/2503.13983/) (2025)

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

- [Thinking in Dynamics: How Multimodal Large Language Models Perceive, Track, and Reason Dynamics in Physical 4D World](https://mlsanity.com/paper/2603.12746/) (2026)
- [Watch, Remember, Reason: Human-View Video Understanding with MLLMs](https://mlsanity.com/paper/2606.07433/) (2026)
- [ViewFusion: Structured Spatial Thinking Chains for Multi-View Reasoning](https://mlsanity.com/paper/2603.06024/) (2026)
- [Beyond 3D VQAs: Injecting 3D Spatial Priors into Vision-Language Models for Enhanced Geometric Reasoning](https://mlsanity.com/paper/2605.30231/) (2026)
- [LenGuard-GPC: Length Guarding with Guided-Prompt Consistency for Spatial Reasoning Reinforce Learning](https://mlsanity.com/paper/2607.17243/) (2026)
- [Towards a Data-Centric Understanding of Spatial Reasoning in Multimodal Large Language Models](https://mlsanity.com/paper/2610.19108/) (2026)

## Abstract (arXiv)

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-based Group Relative Policy Optimization (GRPO) method 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.