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

## Abstract

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 S patio- T emporal R easoning.
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.

## 1 Introduction

Multi-modal Large Language Models (MLLMs) have made significant progress in multi-modal understanding and reasoning (Zhao et al., 2025a; Huang et al., 2023; Ye et al., 2024; Liu et al., 2024a; Xu et al., 2025; Zou et al., 2025; Chen et al., 2024b), but still struggle with precise spatio-temporal reasoning in videos (Li et al., 2025c; Cheng et al., 2025; Zheng et al., 2025).
Spatio-temporal reasoning entails the inference of spatial and temporal relationships, where the former mainly captures positional topology, and the latter reflects dynamic changes. This requires the model not only to understand the objects’ layouts, but also to model their motion.
Some works have explored spatio-temporal understanding of videos (Yuan et al., 2025; Wang et al., 2025a; Li et al., 2025a; Liu et al., 2024a), but they mainly focus on changes within the image, overlooking the physical information behind the videos, the exact spatial positions of objects, their trajectories, and the interactions between multiple entities over time, etc.

Reinforcement Learning with Verifiable Reward (RLVR) has been demonstrated as a promising solution to unlock LLM reasoning gains through task-specific reward design (Guo et al., 2025; Yang et al., 2025b; Chen et al., 2025). Several works extend it on MLLMs to adapt for video spatio-temporal reasoning (Feng et al., 2025; Li et al., 2025b), which primarily employ two types of reward schemes: video pixel-level localization (Cheng et al., 2025; Wang et al., 2025a; Shi et al., 2024) and 2D cognitive map (Ouyang et al., 2025; Yang et al., 2025a).
As shown in Fig. [1](https://arxiv.org/html/2510.10976v1#S1.F1) (a), pixel localization is limited to identifying positions in the image plane, without the ability to infer object layouts or distributions in the physical space  (Li et al., 2025c).
2D cognitive map depicts the scene with a planar grid map, changes in camera viewpoints and non-rotation-invariant object coordinates can lead to errors in estimating object distributions. To overcome these limitations, we design a graph-based representation for multiple objects, in which nodes correspond to objects and edges characterize the relationships between them.
This brings two benefits: (1) beyond localizing individual objects, it further effectively characterizes inter-object relationships; (2) unlike object–camera relationships that are affected by dynamic ego viewpoint, inter-object relationships are insensitive to such dynamics, making the graph structure rotation-invariant and robust to video spatio-temporal reasoning.

Figure: Figure 1: Overview of Video-STR and previous methods. (a) Previous methods localized using images and 2D cognitive maps with spatial cues. (b) Our method, Video-STR, uses graph-based reasoning and RL to infer spatio-temporal relations and object states in videos.
Refer to caption: motivation.png

In this work, we present Video-STR, a novel RLVR framework to improve the spatio-temporal reasoning capabilities of MLLMs.
Specifically, we extend the Group Relative Policy Optimization (GRPO) (Shao et al., 2024) with a graph reasoning mechanism that enables the model to understand the spatial topology using the inter-object relation graph, where the graph is constructed based on the objects’ attributes.
To support training, we introduce the STV-205k, a dataset comprising question-answering (QA) pairs derived from the TAO (Dave et al., 2020), KITTI (Geiger et al., 2013) and ScanNet (Dai et al., 2017) datasets. The constructed dataset covers spatial reasoning tasks (e.g., relative distance, object sizes) and temporal reasoning tasks (e.g., appearance order and displacement). Meanwhile, diverse verifiable rewards $R_{ans}$ is introduced to adapt to various QA types in training.

Experiments on STI-Bench (Li et al., 2025c), V-STaR (Cheng et al., 2025), VSI-Bench (Yang et al., 2025a), SPAR-Bench (Zhang et al., 2025b), Video-MME (Fu et al., 2025), and TempCompass (Liu et al., 2024b) demonstrate that our method achieves strong performance in spatial, temporal, and spatio-temporal reasoning. In summary, our main contributions include:

- •
We construct the STV-205k dataset from TAO, KITTI, and ScanNet, providing 205k diverse QA pairs covering both static spatial and dynamic temporal reasoning, addressing the lack of video spatio-temporal datasets.
- •
We first employ an inter-object relation graph to provide a more comprehensive characterization of multi-object scenes. Based on this relation graph, we extend the GRPO with a graph reasoning mechanism that explicitly supervises the intrinsic topology among multiple objects to reinforce video spatio-temporal reasoning.
- •
Extensive experiments are conducted across diverse relevant benchmarks, indicating that Video-STR achieves the state-of-the-art performance, validating the effectiveness of the STV-205k dataset and our proposed method.

## 2 Related Works

Spatio-Temporal Understanding of MLLMs.
Video MLLMs have made significant advancements on semantics understanding (Hariharan, 2025; Fu et al., 2024), while spatio-temporal understanding remains a significant challenge and has inspired recent contributions (Cai et al., 2024; Li et al., 2024; Chen et al., 2024a).
Existing works mainly focus on the pixel-level spatial reasoning in 2D images. For example, VideoRefer (Yuan et al., 2025) adopts a versatile spatial-temporal object encoder to capture precise regional and sequential representations.
VideoExpert (Zhao et al., 2025b) decouples spatial and temporal reasoning, employing two dedicated modules to capture fine-grained spatial details and model dynamic temporal patterns, respectively.
In contrast to these approaches, our work emphasizes the physical information embedded in videos, thereby enabling more precise spatio-temporal understanding.

Reinforcement Learning with Verifiable Reward
Recent works, such as OpenAI-o1 (Jaech et al., 2024) and DeepSeek-R1 (Guo et al., 2025), have demonstrated that large models can significantly enhance their reasoning ability through reinforcement learning (RL).
Compared with supervised fine-tuning (SFT), it has the advantage of not overfitting (Huang et al., 2025; Da et al., 2025; Shenfeld et al., 2025).
In particular, Deepseek-R1 presents the GRPO algorithm, which can bring emergent and robust reasoning with chain-of-thoughts (CoT) in text-based domains.
Building on this, Kimi-k1.5 (Team et al., 2025) adopted rule-based RL strategies to improve reasoning across both text and vision modalities.
Motivated by this success, several recent efforts have explored extending RL training to MLLMs (Wang et al., 2025b; Zhao et al., 2025c; Xiao et al., 2025; Chen et al., 2025).
However, applying RL to video understanding remains limited due to challenges in designing temporally sensitive rewards and modeling spatio-temporal consistency. Only a few works, such as SpaceR (Ouyang et al., 2025), have explored this direction, leaving significant space for further research on reward formulation and training efficiency in the video domain.

Figure: Figure 2: The overview of the constructed dataset.
Refer to caption: x1.png

## 3 Dataset Design and Construction

### 3.1 Data Collection

To overcome the scarcity of training data for video spatio-temporal understanding, we develop the STV-205k, a large dataset including 205k QA pairs.
To ensure the richness of data sources for a broad spectrum of real-world environments, we collect raw images and videos from three publicly available datasets: TAO (Dave et al., 2020) for motion tracking, ScanNet (Dai et al., 2017) for indoor scene understanding, and KITTI (Geiger et al., 2013) for outdoor scene understanding.
The image data primarily supports the model’s static context comprehension, encompassing aspects such as spatial reasoning and semantic knowledge.
In contrast, video data serves to enhance the model’s temporal understanding, including the extraction of sequential dependencies and the inference of motion from visual dynamics.
Leveraging the provided frame-by-frame annotations, we transform the sampled data into a standardized format that incorporates object-relevant attributes, such as categories, sizes, and center points, which serve as the ground-truth information for QA tasks.

### 3.2 QA Generation

Figure: Figure 3: Data statistics of our constructed STV-205k dataset.
Refer to caption: starfinal.png

Utilizing the parsed ground truth information of the selected datasets, we automatically generate the QA pairs for spatial-temporal reasoning tasks, which are categorized into multi-choice QA (e.g., relative distance, relative direction, and appearance order) and numerical QA (e.g., object size, absolute distance, and object counting). The QA examples are illustrated in Fig. [2](https://arxiv.org/html/2510.10976v1#S2.F2).

- •
Object Counting (Image, video).
Given the ground truth labels, we can obtain the number of each type of object in the videos of images.
- •
Relative Direction (Image, video).
Based on the centre points of two objects, we can infer the spatial relation of them (e.g., left-up and right-down).
- •
Relative Distance (Image, video).
We randomly select a pair of distinct objects from the video or image and embed them into a question template. The Euclidean distance between the centre points of the two objects is then calculated and used as the corresponding answer.
- •
Appearance Order (Video).
For the video data, we record the frame index where an object first appears and randomly select a subset of them to generate questions and answers.
- •
Object Size (Image, Video).
The size information of objects is obtained from the bounding box annotations in the dataset (e.g., length, width, and height). Besides, for indoor scenes, we also record the area of the indoor space, which is measured in square meters.
- •
Motion Tracking (Video).
We use the sequence of bounding boxes to model the motion tracking of the objects in the video, including both 2D and 3D data.
- •
Object Localization (Image, video).
The centre point of the object is used as the answer.
- •
Displacement (Video).
For the video, we obtain the displacement using the travel distance of specific objects between time stamps.

To ensure the quality of QA pairs and prevent the model from naively memorizing the answers, we rigorously filter the sampled data.
For multiple-choice QA, the positions of correct answers are randomly shuffled to balance the answer distribution and mitigate positional bias.
Then, we perform synonym substitution on the questions to enhance the model’s comprehension ability.
Finally, we obtain 205k QA pairs covering diverse tasks.

Dataset Statistics.
The dataset statistics of STV-205k are illustrated in Fig. [3](https://arxiv.org/html/2510.10976v1#S3.F3).
According to the task type, a total of 205k samples are divided into two categories: spatial reasoning and temporal reasoning.
STV-205k dataset comprises both images and videos and encompasses various verifiable QA types: multi-choice, numerical, and IoU questions.
More details for data collection and generation are provided in the Appendix [D](https://arxiv.org/html/2510.10976v1#A4).

## 4 ST-Specific RLVR

To enhance video spatial-temporal reasoning in MLLMs, we introduce Video-STR, a reinforcement learning framework that extends GRPO by incorporating a series of verifiable specific reward functions to adapt to the constructed QA pairs.
Besides, a novel graph-based reasoning mechanism is introduced into the process of MLLM thinking to guide spatio-temporal reasoning.

### 4.1 Verifiable Reward Functions

To effectively supervise model outputs across diverse QA types, including multiple-choice, numerical, and IoU, we design a set of verifiable reward functions that evaluate responses $\hat{y}$ based on task-specific criteria, assessing either the correctness or the format of the answer.

Format Reward.
To regulate the responses $\hat{y}$ of the model to conform to a predefined structure, a format reward $R_{format}$ is defined based on whether the model wraps the reasoning process and answer into
<think> $\cdot\cdot\cdot$ </think> and <answer> $\cdot\cdot\cdot$ </answer> tags:

$$ $R_{format}(\hat{y})=\begin{cases}1,&\text{if }\hat{y}\text{ matches format},\\ 0,&\text{otherwise}.\end{cases}$ (1) $$

Multi-choice Reward. For multi-choice QA, the reward $R_{mc}$ is binary, depending on whether it matches the ground truth $y$:

$$ $R_{mc}(\hat{y},y)=\begin{cases}1,&\text{if }\hat{y}=y,\\ 0,&\text{otherwise}.\end{cases}$ (2) $$

Numerical Reward.
For the numerical QA, we compute the relative accuracy of the predicted results, which is formulated as:

$$ $R_{num}(\hat{y},y)=\max(0,1-|\hat{y}-y|/y)$ (3) $$

IoU Reward. For the spatio-temporal perception such as object tracking, it requires the MLLM to output the predicted bounding boxes in the video that is associated with the content of a given textual query. Evidently, we can use the Intersection over Union (IoU) between the predicted area by the model $\mathcal{I}_{\hat{y}}$ and the ground-truth area $\mathcal{I}_{y}$ as the reward function. This reward function effectively characterizes the accuracy of the interval predicted by the model.

$$ $R_{IoU}(\mathcal{I}_{\hat{y}},\mathcal{I}_{y})=|\mathcal{I}_{\hat{y}}\cap\mathcal{I}_{y}|/|\mathcal{I}_{\hat{y}}\cup\mathcal{I}_{y}|$ (4) $$

### 4.2 Graph-based Spatio-Temporal Reasoning

The base reward functions lack explicit reward signals to ensure a genuine understanding of spatio-temporal information, and they may merely lead the model to memorize the answers.
We introduce a graph-based reasoning mechanism that serves to facilitate spatio-temporal reasoning within the thinking process.
As shown in Fig. [2](https://arxiv.org/html/2510.10976v1#S2.F2), we adopt the graph-based representation to formulate the topology of multiple objects and their relationships such as object locations, sizes, and the spatial structure of object distribution.

A graph $\mathcal{G}$ is characterized by $(\mathcal{V},\mathcal{E},\mathcal{A})$, where $\mathcal{V}$, $\mathcal{E}$ and $\mathcal{A}$ are the set of nodes, edges and attributions.
Each edge $e_{ij}$ that connects node $v_{i}$ and $v_{j}$ is assigned an attribute $a_{ij}=(d_{ij},\theta_{ij})$, and node attributes are denoted as $a_{ii}=(x_{i})$ for node $v_{i}$, where $x_{i}$ is the location, $d_{ij}$ is the Euclidean distance and $\theta_{ij}$ is the angle of relative direction.
The model is prompted to generate such a graph to image the distribution of multiple objects within the scene, thereby enhancing the spatial understanding. To assess the quality of the generated graphs, we design a specific reward function to explicitly supervise the accuracy of the model inference.
First, we calculate the relative accuracy between the predicted object and the ground truth object by their relative distance:

$$ $R_{n}=\sum_{i=1}^{k}(\frac{n_{i}}{\sum_{j}^{k}n_{j}}\times({exp(-||x_{i}-x_{i^{\prime}}||_{2})}))$ (5) $$

where $k$ is the number of object categories. $n_{i}$, $n_{j}$ is the number of $i$-th and $j$-th object.
$x_{i}$ is the predicted center point coordinates of the object, while $x_{i^{\prime}}$ denotes the ground truth.
Besides, for the edges, the reward is formulated as:

$$ $R_{e}=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}({exp(-|d_{ij}-d_{i^{\prime}j^{\prime}}|)}+{exp(-|\theta_{ij}-\theta_{i^{\prime}j^{\prime}}|)})$ (6) $$

where $d_{ij}$ denotes the predicted Euclidean distance between $i$-th object and $j$-th object and $d_{i^{\prime}j^{\prime}}$ is the corresponding ground truth. $\theta_{ij}\in[0,\pi]$ denotes the angle between $d_{ij}$ and $d_{i^{\prime}j^{\prime}}$, serving as a measure of the degree of consistency in objects’ relative spatial relationship.
Then the graph-based reasoning mechanism of an image is defined as the sum of $R_{e}$ and $R_{n}$. For the video, we calculate the mean reward of the selected $k$ frames from the video

$$ $R_{graph}=\frac{1}{k}\sum_{i}^{k}R_{n}^{(k)}+R_{e}^{(k)}$ (7) $$

To illustrate the reasonableness of the reward function design, we state two theorems, and the proofs are provided in the Appendix [A](https://arxiv.org/html/2510.10976v1#A1).

Theorem 1. Graph-based multi-object topological representations exhibit rotation invariance.

$$ $R_{e}(\mathcal{R}X,C)=R_{e}(X,C)$ (8) $$

where $\mathcal{R}$ is the rotation, $C$ is the object category, and $\Phi$ is the representation method.

Theorem 2. Rewards based on graph similarity effectively promote the model’s comprehension of topological structures.

To further enhance the quality of reasoning, we introduce a length-based reward to regulate the length of the model’s output, thereby striking a balance between promoting deeper reasoning and preventing overthinking. Specifically, the model will receive an additional reward $R_{l}=\omega$ if the output answer is correct and the response length falls within a predefined interval $[l_{min},l_{max}]$.
The total reward can be formulated as:

$$ $R_{total}=\begin{cases}R_{format}+R_{ans}+R_{graph}+R_{l},&\text{if }R_{ans}>0.8,\\ R_{format}+R_{ans}+R_{graph},&\text{otherwise}.\end{cases}$ (9) $$

where $R_{ans}$ denotes the reward for the answer ($R_{mc}$, $R_{num}$ or $R_{IoU}$).

### 4.3 GRPO Training

GRPO is an extension of Proximal Policy Optimization (PPO)  (Schulman et al., 2017) that introduces the group of candidates responses, thereby eliminating dependency on the critic model.

Given an input question $q$, GRPO generates candidate responses $o=\{o_{1},...,o_{G}\}$ through policy sampling, $G$ is the number of output responses. The corresponding reward scores are $\{r_{1},...,r_{G}\}$. Then GRPO computes their mean and standard deviation for normalization and defines the quality:

$$ $A_{i}=(r_{i}-\text{mean}(\{r_{i}\}^{G}_{i=1}))\,/\,\text{std}(\{r_{i}\})$ (10) $$

where $A_{i}$ denotes the relative quality of the $i$-th answer.
The final training objective considers preventing the optimized policy $\pi_{\theta}$ from deviating far from the original MLLM parameters $\pi_{\text{ref}}$ by adding a KL-divergence term $\mathcal{D}_{KL}(\cdot||\cdot)$, which is formulated as:

$$ $J(\theta)=E_{q,\{o_{i}\}}[\frac{1}{G}\sum_{i=1}^{G}(\text{min}(\frac{\pi_{\theta}(o_{i}|q)}{\pi_{\theta_{\text{old}}}(o_{i}|q)}A_{i},\text{clip}(\frac{\pi_{\theta}(o_{i}|q)}{\pi_{\theta_{\text{old}}}(o_{i}|q)},1-\epsilon,1+\epsilon)A_{i}))-\beta\mathcal{D}_{KL}(\pi_{\theta}||\pi_{\text{ref}})]$ (11) $$

where $\beta$ is a regularization coefficient, preventing excessive deviation from the reference policy
during optimization and $\epsilon$ is a positive coefficient that limits the policy updating degree.

## 5 Experiments

### 5.1 Experimental Setup

**Table 1: Results of Video-STR and baselines on various video benchmarks including spatio-temporal benchmarks (V-STaR, STI-Bench), spatial reasoning benchmarks (VSI-Bench, SPAR-Bench) and temporal reasoning benchmarks (Video-MME, TempCompass).**
| Model | Params | Spa.-Temp. Reasoning | Spa. Reasoning | Temp. Reasoning |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| STI | V-STaR | VSI | SPAR | Video-MME | TC |  |  |
| Mainstream Commercial Models |  |  |  |  |  |  |  |
| \rowcolorgray!10<br>GPT-4o (Hurst et al., 2024) | - | 34.8 | 39.5 | 34.0 | 36.4 | 71.9 | 73.8 |
| \rowcolorgray!10<br>Gemini-2.0-Flash (Team et al., 2024) | - | 38.7 | – | 45.4 | – | – | – |
| \rowcolorgray!10<br>Claude-3.7-Sonnet (Anthropic, 2025) | - | 40.5 | – | – | 21.8 | – | – |
| Open-Source Models |  |  |  |  |  |  |  |
| Qwen2.5-VL-7B-Instruct (Bai et al., 2025) | 7B | 34.7 | 35.2 | 33.0 | 33.1 | 56.3 | 71.1 |
| MiniCPM-V-2.6 (Yao et al., 2024) | 8B | 26.9 | – | – | – | – | 54.9 |
| VideoLLaMA3-7B (Zhang et al., 2025a) | 7B | 26.9 | 27.0 | – | – | 66.2 | 68.1 |
| Video-R1 (Feng et al., 2025) | 7B | 33.3 | 35.4 | 35.8 | – | 59.3 | 73.2 |
| VideoChat-R1 (Li et al., 2025b) | 7B | 34.3 | 36.5 | 38.0 | – | 58.8 | – |
| SpaceR (Ouyang et al., 2025) | 7B | 35.2 | 34.5 | 45.7 | 37.6 | 57.9 | 71.4 |
| \rowcolorgreen!8<br>Ours (SFT) | 7B | 35.3 | 34.9 | 41.8 | 33.0 | 57.2 | 69.8 |
| \rowcolorgreen!8<br>Ours | 7B | 39.3 | 37.8 | 46.5 | 37.9 | 58.1 | 72.1 |

Figure: Figure 4: (a) Performance on sub-tasks. (b) Performance on static and dynamic tasks. (c) Performance in different scenarios.
Refer to caption: sub-sti.png

Implementation Details.
In the training process, we employ Qwen2.5-VL-7B-Instruct (Bai et al., 2025) as the base model.
We use Adam optimizer with a learning rate of 1e-6 to train our model.
For each sample, 8 responses are generated to compute the group-based advantage of GRPO.
The hyperparameter $\beta$ in the KL-divergence term is set to 0.04.
Training is performed with a batch size of 1 on 8 NVIDIA H100 80GB GPUs.
To ensure training stability, we apply a weight decay rate of 0.01 and clip the maximum gradient norm to 5.
The maximum completion length is set as 1024 tokens. The preferred length range of response is set to $[320,512]$ and the reward value is 0.2.
For efficiency considerations, we limit the maximum number of video frames to 16 during training, where each frame is processed at a resolution of $128\times 28\times 28$.
During inference, the number of video frames is standardized to 32 and each frame is incresead to $448\times 28\times 28$ for better accuracy.

Benchmarks.
We evaluate our model using multiple benchmarks: STI-Bench (Li et al., 2025c) and V-STaR (Cheng et al., 2025) for spatio-temporal reasoning, VSI-Bench (Yang et al., 2025a) and SPAR-Bench for spatial reasoning, and Video-MME (Fu et al., 2025) and TempCompass (Liu et al., 2024b) for temporal reasoning. Various mainstream closed-source and open-source MLLM baselines are used. Details are provided in Appendix [C](https://arxiv.org/html/2510.10976v1#A3).

### 5.2 Main Results

Overall Performance.
Table. [1](https://arxiv.org/html/2510.10976v1#S5.T1) shows the evaluation results on five relevant benchmarks.
We can see that our model outperforms the base model Qwen2.5-VL-7B-Instruct across all benchmarks.
Our model surpasses GPT-4o in spatio-temporal reasoning benchmarks, highlighting the capability of spatio-temporal reasoning.
In addition, our model also shows improvements in video temporal understanding, indicating that the enhanced spatial understanding did not lead to
overfitting, and the model maintained its generalization ability in video comprehension.

Comparison with SFT.
We also compare the effectiveness of our proposed method with SFT. As shown in Table. [1](https://arxiv.org/html/2510.10976v1#S5.T1), While SFT achieves localized improvements on benchmarks including STI-Bench and VSI-Bench, it simultaneously incurs performance degradation on other tasks, reflecting its limited generalizability due to overfitting. In contrast, our method consistently enhances performance across both spatial reasoning and video understanding benchmarks, underscoring its superior generalization capability. These findings substantiate the claim that “RLVR generalizes, whereas SFT memorizes,” indicating RLVR as a more effective training paradigm for advancing spatial reasoning in MLLMs.

Performance on sub-tasks.
Fig. [4](https://arxiv.org/html/2510.10976v1#S5.F4) shows the results of our proposed model on the sub-tasks of STI-Bench. It can be seen that the model achieves improvements over the base model across all sub-tasks, with particularly notable gains in tasks involving temporal and spatial coupling.

**Table 2: Ablation study on different components.**
| Method | Frames | Spatio-Temporal | Spatial Reasoning | Temporal Reasoning |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| STI-Bench | V-STaR | VSI-Bench | SPAR-Bench | Video-MME | Temp-Compass |  |  |
| w/o-spatial subset | 32 | 35.7 | 36.0 | 36.3 | 33.7 | 57.0 | 71.2 |
| w/o-temporal subset | 32 | 36.3 | 34.9 | 44.9 | 35.4 | 56.4 | 71.0 |
| w/o-graph-based reasoning | 32 | 36.9 | 37.1 | 45.8 | 37.4 | 56.7 | 71.4 |
| \rowcolorgreen!8<br>Video-STR | 32 | 39.3 | 37.8 | 46.5 | 37.9 | 58.1 | 72.1 |

### 5.3 Ablation Study

Effectiveness of Different Components. To demonstrate the contributions of each component of our proposed framework, we incrementally incorporate individual components of the

**Table 3: Accuracy of numerical predictions.**
| Model | STI | VSI |
| --- | --- | --- |
| Qwen2.5-VL-7B-Instruct | 38.1 | 33.9 |
| SpaceR (Ouyang et al., 2025) | 36.5 | 47.5 |
| \rowcolorgreen!8<br>Video-STR | 40.2 | 48.4 |

framework and obtain three variants of the model:
1) w/o-graph-based reasoning mechanism, which eliminates the graph-based reasoning mechanism in the training and inference stage;
2) w/o-spatial subset, which removes the spatial understanding subset of the STV-205k in the training process;
3) w/o-temporal subset, which excludes the temporal understanding subset of the STV-205k in the training process.
The evaluation results are illustrated in Table. [2](https://arxiv.org/html/2510.10976v1#S5.T2), confirming the effectiveness of the graph-based reasoning mechanism.
Secondly, removing spatial data leads to a notable degradation in spatial reasoning, while w/o-temporal data results in a clear decline in temporal understanding. These findings emphasize the particular effectiveness of our constructed dataset.

### 5.4 Quantitative Analysis

Figure: Figure 5: SFT using different datasets.
Refer to caption: x2.png

Accuracy of numerical QA pairs.
Considering that most of the benchmarks consist of multiple-choice questions, the model can achieve a certain level of accuracy even through random guessing, making it difficult to determine whether the model relies on memorization or true understanding. To more accurately assess the model’s spatial understanding, we converted some of the multiple-choice QA in the benchmarks into numerical QA and evaluated the accuracy. As shown in the Table  [3](https://arxiv.org/html/2510.10976v1#S5.T3), our model demonstrates a substantial improvement in accuracy, indicating a genuine enhancement in spatio-temporal understanding.

Comparison with Other Datasets.
To further evaluate the dataset we designed, we compared the performance of the SFT using different datasets.
Specifically, we respectively sample training data from Video-260k, SR-91k and STR-205k using uniform sampling. The results are shown in Fig. [5](https://arxiv.org/html/2510.10976v1#S5.F5).

### 5.5 Qualitative Analysis

We present two cases from STI-Bench in Fig. [6](https://arxiv.org/html/2510.10976v1#S5.F6) to show the process of the thinking of our model in spatio-temporal reasoning.
From the Fig. [6](https://arxiv.org/html/2510.10976v1#S5.F6) (a), we can see that our model demonstrates a clear qualitative superiority over the base model on topology reasoning, explicit spatial distribution, and accurate results.
Our model leverages imagined graphs to understand the surrounding environment, explicitly reasoning about the distribution of multiple objects and inferring the spatial relationship between “red car” and “white van”.
In contrast, the base model Qwen2.5-VL-7B-Instruct directly outputs an answer, but due to the lack of spatial reasoning, it produces an incorrect result.
We additionally present the results of another task in Fig. [6](https://arxiv.org/html/2510.10976v1#S5.F6) (b).
By reasoning across multiple frames of the video, our model precisely infers object motion trends through the spatio-temporal reasoning mechanism in the thinking process. By contrast, the base model misjudges the motion information of objects, leading to an erroneous prediction.

Figure: Figure 6: Two samples from the STI-Bench. (a) Comparison on object spatial relation; (b) Comparison on appearance order.
Refer to caption: qualita.png

## 6 Conclusion

In this work, we present Video-STR, a novel reinforcement learning framework specifically designed to advance video spatio-temporal reasoning in MLLMs. Video-STR integrates graph reasoning directly into the model’s thinking process, while employing GRPO with verifiable rewards to train the model. This mechanism enables the model to effectively capture complex multi-object distributions and layouts, which are often neglected by existing approaches. To facilitate both training and comprehensive evaluation, we introduce the STR-205k dataset, a large-scale dataset of diverse spatio-temporal QA pairs covering different scenarios. Extensive experiments demonstrate that Video-STR consistently outperforms previous spatio-enhanced and time-series modeling approaches, achieving a substantial improvement over GPT-4o on STI-Bench. These results highlight the effectiveness of integrating graph reasoning with RLVR for comprehensive video spatio-temporal reasoning. Looking forward, we aim to extend Video-STR to more complex, real-world scenarios, explore its applicability across richer modalities, and expand the dataset to encompass increasingly diverse tasks, paving the way for broader and deeper spatio-temporal reasoning in MLLMs.

## References

- Anthropic (2025)
Claude Anthropic.
3.7 sonnet and claude code, 2025.
- Bai et al. (2025)
Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, et al.
Qwen2. 5-vl technical report.
*arXiv preprint arXiv:2502.13923*, 2025.
- Cai et al. (2024)
Wenxiao Cai, Iaroslav Ponomarenko, Jianhao Yuan, Xiaoqi Li, Wankou Yang, Hao Dong, and Bo Zhao.
Spatialbot: Precise spatial understanding with vision language models.
*arXiv preprint arXiv:2406.13642*, 2024.
- Chen et al. (2024a)
Boyuan Chen, Zhuo Xu, Sean Kirmani, Brain Ichter, Dorsa Sadigh, Leonidas Guibas, and Fei Xia.
Spatialvlm: Endowing vision-language models with spatial reasoning capabilities.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 14455–14465, 2024a.
- Chen et al. (2025)
Ruizhe Chen, Tianze Luo, Zhiting Fan, Heqing Zou, Zhaopeng Feng, Guiyang Xie, Hansheng Zhang, Zhuochen Wang, Zuozhu Liu, and Huaijian Zhang.
Datasets and recipes for video temporal grounding via reinforcement learning.
In *Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: Industry Track*, 2025.
- Chen et al. (2024b)
Yuan Chen, Zi-han Ding, Ziqin Wang, Yan Wang, Lijun Zhang, and Si Liu.
Asynchronous large language model enhanced planner for autonomous driving.
In *European Conference on Computer Vision*, pp. 22–38. Springer, 2024b.
- Cheng et al. (2025)
Zixu Cheng, Jian Hu, Ziquan Liu, Chenyang Si, Wei Li, and Shaogang Gong.
V-star: Benchmarking video-llms on video spatio-temporal reasoning.
*arXiv preprint arXiv:2503.11495*, 2025.
- Comanici et al. (2025)
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al.
Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities.
*arXiv preprint arXiv:2507.06261*, 2025.
- Da et al. (2025)
Jeff Da, Clinton Wang, Xiang Deng, Yuntao Ma, Nikhil Barhate, and Sean Hendryx.
Agent-rlvr: Training software engineering agents via guidance and environment rewards.
*arXiv preprint arXiv:2506.11425*, 2025.
- Dai et al. (2017)
Angela Dai, Angel X Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.
Scannet: Richly-annotated 3d reconstructions of indoor scenes.
In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 5828–5839, 2017.
- Dave et al. (2020)
Achal Dave, Tarasha Khurana, Pavel Tokmakov, Cordelia Schmid, and Deva Ramanan.
Tao: A large-scale benchmark for tracking any object.
In *European conference on computer vision*, pp. 436–454. Springer, 2020.
- Feng et al. (2025)
Kaituo Feng, Kaixiong Gong, Bohao Li, Zonghao Guo, Yibing Wang, Tianshuo Peng, Junfei Wu, Xiaoying Zhang, Benyou Wang, and Xiangyu Yue.
Video-r1: Reinforcing video reasoning in mllms.
*arXiv preprint arXiv:2503.21776*, 2025.
- Fu et al. (2025)
Chaoyou Fu, Yuhan Dai, Yongdong Luo, Lei Li, Shuhuai Ren, Renrui Zhang, Zihan Wang, Chenyu Zhou, Yunhang Shen, Mengdan Zhang, et al.
Video-mme: The first-ever comprehensive evaluation benchmark of multi-modal llms in video analysis.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 24108–24118, 2025.
- Fu et al. (2024)
Rao Fu, Jingyu Liu, Xilun Chen, Yixin Nie, and Wenhan Xiong.
Scene-llm: Extending language model for 3d visual understanding and reasoning.
*arXiv preprint arXiv:2403.11401*, 2024.
- Geiger et al. (2013)
Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun.
Vision meets robotics: The kitti dataset.
*The international journal of robotics research*, 32(11):1231–1237, 2013.
- Guo et al. (2025)
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al.
Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning.
*arXiv preprint arXiv:2501.12948*, 2025.
- Hariharan (2025)
Mohanakrishnan Hariharan.
Semantic mastery: Enhancing llms with advanced natural language understanding.
*arXiv preprint arXiv:2504.00409*, 2025.
- Huang et al. (2023)
Hanyao Huang, Ou Zheng, Dongdong Wang, Jiayi Yin, Zijin Wang, Shengxuan Ding, Heng Yin, Chuan Xu, Renjie Yang, Qian Zheng, et al.
Chatgpt for shaping the future of dentistry: the potential of multi-modal large language model.
*International Journal of Oral Science*, 15(1):29, 2023.
- Huang et al. (2025)
Xiaoke Huang, Juncheng Wu, Hui Liu, Xianfeng Tang, and Yuyin Zhou.
Medvlthinker: Simple baselines for multimodal medical reasoning.
*arXiv preprint arXiv:2508.02669*, 2025.
- Hurst et al. (2024)
Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, et al.
Gpt-4o system card.
*arXiv preprint arXiv:2410.21276*, 2024.
- Jaech et al. (2024)
Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al.
Openai o1 system card.
*arXiv preprint arXiv:2412.16720*, 2024.
- Li et al. (2025a)
Hongyu Li, Jinyu Chen, Ziyu Wei, Shaofei Huang, Tianrui Hui, Jialin Gao, Xiaoming Wei, and Si Liu.
Llava-st: A multimodal large language model for fine-grained spatial-temporal understanding.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 8592–8603, 2025a.
- Li et al. (2025b)
Xinhao Li, Ziang Yan, Desen Meng, Lu Dong, Xiangyu Zeng, Yinan He, Yali Wang, Yu Qiao, Yi Wang, and Limin Wang.
Videochat-r1: Enhancing spatio-temporal perception via reinforcement fine-tuning.
*arXiv preprint arXiv:2504.06958*, 2025b.
- Li et al. (2025c)
Yun Li, Yiming Zhang, Tao Lin, XiangRui Liu, Wenxiao Cai, Zheng Liu, and Bo Zhao.
Sti-bench: Are mllms ready for precise spatial-temporal world understanding?
*arXiv preprint arXiv:2503.23765*, 2025c.
- Li et al. (2024)
Zhonghang Li, Lianghao Xia, Jiabin Tang, Yong Xu, Lei Shi, Long Xia, Dawei Yin, and Chao Huang.
Urbangpt: Spatio-temporal large language models.
In *Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, pp. 5351–5362, 2024.
- Liu et al. (2024a)
Dongyang Liu, Renrui Zhang, Longtian Qiu, Siyuan Huang, Weifeng Lin, Shitian Zhao, Shijie Geng, Ziyi Lin, Peng Jin, Kaipeng Zhang, et al.
Sphinx-x: Scaling data and parameters for a family of multi-modal large language models.
*arXiv preprint arXiv:2402.05935*, 2024a.
- Liu et al. (2024b)
Yuanxin Liu, Shicheng Li, Yi Liu, Yuxiang Wang, Shuhuai Ren, Lei Li, Sishuo Chen, Xu Sun, and Lu Hou.
Tempcompass: Do video llms really understand videos?
*arXiv preprint arXiv:2403.00476*, 2024b.
- Ouyang et al. (2025)
Kun Ouyang, Yuanxin Liu, Haoning Wu, Yi Liu, Hao Zhou, Jie Zhou, Fandong Meng, and Xu Sun.
Spacer: Reinforcing mllms in video spatial reasoning.
*arXiv preprint arXiv:2504.01805*, 2025.
- Schulman et al. (2017)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
*arXiv preprint arXiv:1707.06347*, 2017.
- Shao et al. (2024)
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al.
Deepseekmath: Pushing the limits of mathematical reasoning in open language models.
*arXiv preprint arXiv:2402.03300*, 2024.
- Shenfeld et al. (2025)
Idan Shenfeld, Jyothish Pari, and Pulkit Agrawal.
Rl’s razor: Why online reinforcement learning forgets less.
*arXiv preprint arXiv:2509.04259*, 2025.
- Shi et al. (2024)
Yudi Shi, Shangzhe Di, Qirui Chen, and Weidi Xie.
Enhancing video-llm reasoning via agent-of-thoughts distillation.
*arXiv preprint arXiv:2412.01694*, 2024.
- Team et al. (2024)
Gemini Team, Petko Georgiev, Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, et al.
Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context.
*arXiv preprint arXiv:2403.05530*, 2024.
- Team et al. (2025)
Kimi Team, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al.
Kimi k1. 5: Scaling reinforcement learning with llms.
*arXiv preprint arXiv:2501.12599*, 2025.
- Wang et al. (2025a)
Jiankang Wang, Zhihan Zhang, Zhihang Liu, Yang Li, Jiannan Ge, Hongtao Xie, and Yongdong Zhang.
Spacevllm: Endowing multimodal large language model with spatio-temporal video grounding capability.
*arXiv preprint arXiv:2503.13983*, 2025a.
- Wang et al. (2025b)
Ye Wang, Ziheng Wang, Boshen Xu, Yang Du, Kejun Lin, Zihan Xiao, Zihao Yue, Jianzhong Ju, Liang Zhang, Dingyi Yang, et al.
Time-r1: Post-training large vision language model for temporal video grounding.
*arXiv preprint arXiv:2503.13377*, 2025b.
- Xiao et al. (2025)
Tong Xiao, Xin Xu, Zhenya Huang, Hongyu Gao, Quan Liu, Qi Liu, and Enhong Chen.
Advancing multimodal reasoning capabilities of multimodal large language models via visual perception reward.
*arXiv preprint arXiv:2506.07218*, 2025.
- Xu et al. (2025)
Runsen Xu, Weiyao Wang, Hao Tang, Xingyu Chen, Xiaodong Wang, Fu-Jen Chu, Dahua Lin, Matt Feiszli, and Kevin J Liang.
Multi-spatialmllm: Multi-frame spatial understanding with multi-modal large language models.
*arXiv preprint arXiv:2505.17015*, 2025.
- Yang et al. (2025a)
Jihan Yang, Shusheng Yang, Anjali W Gupta, Rilyn Han, Li Fei-Fei, and Saining Xie.
Thinking in space: How multimodal large language models see, remember, and recall spaces.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 10632–10643, 2025a.
- Yang et al. (2025b)
Zhicheng Yang, Zhijiang Guo, Yinya Huang, Yongxin Wang, Dongchun Xie, Yiwei Wang, Xiaodan Liang, and Jing Tang.
Depth-breadth synergy in rlvr: Unlocking llm reasoning gains with adaptive exploration.
*arXiv preprint arXiv:2508.13755*, 2025b.
- Yao et al. (2024)
Yuan Yao, Tianyu Yu, Ao Zhang, Chongyi Wang, Junbo Cui, Hongji Zhu, Tianchi Cai, Haoyu Li, Weilin Zhao, Zhihui He, et al.
Minicpm-v: A gpt-4v level mllm on your phone.
*arXiv preprint arXiv:2408.01800*, 2024.
- Ye et al. (2024)
Qinghao Ye, Haiyang Xu, Jiabo Ye, Ming Yan, Anwen Hu, Haowei Liu, Qi Qian, Ji Zhang, and Fei Huang.
mplug-owl2: Revolutionizing multi-modal large language model with modality collaboration.
In *Proceedings of the ieee/cvf conference on computer vision and pattern recognition*, pp. 13040–13051, 2024.
- Yuan et al. (2025)
Yuqian Yuan, Hang Zhang, Wentong Li, Zesen Cheng, Boqiang Zhang, Long Li, Xin Li, Deli Zhao, Wenqiao Zhang, Yueting Zhuang, et al.
Videorefer suite: Advancing spatial-temporal object understanding with video llm.
In *Proceedings of the Computer Vision and Pattern Recognition Conference*, pp. 18970–18980, 2025.
- Zhang et al. (2025a)
Boqiang Zhang, Kehan Li, Zesen Cheng, Zhiqiang Hu, Yuqian Yuan, Guanzheng Chen, Sicong Leng, Yuming Jiang, Hang Zhang, Xin Li, et al.
Videollama 3: Frontier multimodal foundation models for image and video understanding.
*arXiv preprint arXiv:2501.13106*, 2025a.
- Zhang et al. (2025b)
Jiahui Zhang, Yurui Chen, Yanpeng Zhou, Yueming Xu, Ze Huang, Jilin Mei, Junhui Chen, Yu-Jie Yuan, Xinyue Cai, Guowei Huang, et al.
From flatland to space: Teaching vision-language models to perceive and reason in 3d.
*arXiv preprint arXiv:2503.22976*, 2025b.
- Zhao et al. (2025a)
Han Zhao, Min Zhang, Wei Zhao, Pengxiang Ding, Siteng Huang, and Donglin Wang.
Cobra: Extending mamba to multi-modal large language model for efficient inference.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 39, pp. 10421–10429, 2025a.
- Zhao et al. (2025b)
Henghao Zhao, Ge-Peng Ji, Rui Yan, Huan Xiong, and Zechao Li.
Videoexpert: Augmented llm for temporal-sensitive video understanding.
*arXiv preprint arXiv:2504.07519*, 2025b.
- Zhao et al. (2025c)
Jiaxing Zhao, Xihan Wei, and Liefeng Bo.
R1-omni: Explainable omni-multimodal emotion recognition with reinforcement learning.
*arXiv preprint arXiv:2503.05379*, 2025c.
- Zheng et al. (2025)
Haozhen Zheng, Beitong Tian, Mingyuan Wu, Zhenggang Tang, Klara Nahrstedt, and Alex Schwing.
Spatio-temporal llm: Reasoning about environments and actions.
*arXiv preprint arXiv:2507.05258*, 2025.
- Zou et al. (2025)
Heqing Zou, Tianze Luo, Guiyang Xie, Victor Xiao Jie Zhang, Fengmao Lv, Guangcong Wang, Junyang Chen, Zhuochen Wang, Hansheng Zhang, and Huaijian Zhang.
Hlv-1k: A large-scale hour-long video benchmark for time-specific long video understanding.
*arXiv preprint arXiv:2501.01645*, 2025.

## Appendix A Proof of Proposed Theorem

The center positions of the $n$ objects is represented as $\bm{x}_{1},\cdots,\bm{x}_{n}$, and their categories are $c_{1},\cdots c_{n}$.
Then we can define a weighted complete graph (or any chosen edge subset) by

- •
Vertex Set: $V=\{v_{1},\cdots,v_{n}\}$
- •
Label: $l(i)=c_{i}$
- •
Edge value: $d_{ij}=||x_{i}-x_{j}||$

Statement: Denote this structure as $\Phi(X,C)$, where $X=(x_{1},\cdots,x_{n})$ and $C=(c_{1},\cdots,c_{n})$. Then for the rotation matrix $\mathcal{R}\in SO(3)$ (i.e., $\mathcal{R}^{\top}\mathcal{R}=I$ and $\det\mathcal{R}=1$),

$$ $\Phi(\mathcal{R}X,C)=\Phi(X,C),$ $$

i.e., the graph (its labels and all edge weights) is invariant under rotations.

###### Proof.

For any $i,j$, we have

$$ $\|\mathcal{R}x_{i}-\mathcal{R}x_{j}\|=\|\mathcal{R}(x_{i}-x_{j})\|.$ $$

Since $\mathcal{R}^{\top}\mathcal{R}=I$, it follows that

$$ $\|\mathcal{R}(x_{i}-x_{j})\|=(x_{i}-x_{j})^{\top}\mathcal{R}^{\top}\mathcal{R}(x_{i}-x_{j})=\|x_{i}-x_{j}\|.$ $$

Taking the square root yields $\|\mathcal{R}x_{i}-\mathcal{R}x_{j}\|=\|x_{i}-x_{j}\|$.
Hence, all edge weights are preserved under rotations.
Hence each edge weight is preserved under rotation: $w^{\prime}_{ij}=w_{ij}$.
Moreover, the vertex labels $\ell(i)=c_{i}$ are unaffected by rotation (the category of an object does not change). Therefore $\Phi(\mathcal{R}X,C)$ and $\Phi(X,C)$ have identical vertices, labels, edge sets, and edge weights, and thus

$$ $\Phi(\mathcal{R}X,C)=\Phi(X,C).$ $$

Let $\Phi=R_{e}$, The equation still holds.

∎

Statement: Let a center point be represented by its absolute coordinate $x_{i}\in\mathbb{R}^{2}$. For any nontrivial rotation $\mathcal{R}\in SO(3)$ with angle $\theta\neq 0\ (\mathrm{mod}\ 2\pi)$, the absolute-coordinate representation is not rotation-invariant in general.

###### Proof.

For a nontrivial planar rotation $\mathcal{R}$, the only fixed point is the origin.
Indeed, suppose $\mathcal{R}x_{i}=x_{i}$. Then

$$ $(\mathcal{R}-I)x_{i}=\textbf{0}.$ $$

Since $\mathcal{R}-I$ is invertible when $\theta\neq 0$, it follows that $x_{i}=\textbf{0}$. Therefore, for any $x_{i}\neq\textbf{0}$, we have $\mathcal{R}x_{i}\neq x_{i}$. Let $f$ be any feature that depends on the absolute coordinate (for example, $f(x_{i})=x_{i}$).

Thus, for any $x_{i}\neq\textbf{0}$, we have $\mathcal{R}x_{i}\neq x_{i}$. Moreover,

$$ $f(x_{i})=x_{i},\quad f(\mathcal{R}x_{i})=\mathcal{R}x_{i}.$ $$

Combining these, it follows that

$$ $f(\mathcal{R}x_{i})\neq f(x_{i}).$ $$

Hence, $f$ is not invariant under rotations.

∎

Statement. The proposed graph similarity reward function can reflect the model’s level of scene understanding.

Proof. By directly substituting the results into the reward function, we find that the reward attains a value of 1 when the nodes are in complete agreement.

###### Proof.

###### Proof.

## Appendix B Benchmarks

- •
STI-Bench (Li et al., 2025c) investigates spatial-temporal based on real-world video data recorded in desktop, indoor, and outdoor environments. It proposes eight distinct tasks with over 2,000 QA pairs grouped into eight categories (including dimensional measurement, displacement and path length, ego-centric orientation, spatial relations, speed and acceleration, and trajectory description).
- •
V-STaR (Cheng et al., 2025) is a benchmark specifically designed to comprehensively assess the spatio-temporal reasoning capabilities of Video-LLMs. Constructed from 2094 videos covering 9 diverse domains—including Entertainment, Daily Life, Sports, Tutorials, and more—it provides coarse-to-fine Chain-of-Thought question chains and over 16,793 object bounding box annotations.
- •
VSI-Bench (Yang et al., 2025a) offers a large-scale resource for examining the visual–spatial reasoning skills of MLLMs. Built from 288 authentic indoor videos across a variety of locations—ranging from households to offices and factories—it contributes more than 5,000 question–answer pairs that directly test a model’s capacity for spatial reasoning.
- •
SPAR (Zhang et al., 2025b) is a benchmark for multi-view spatial understanding. Encompassing more than 7,000 QA pairs, it spans tasks that range from simple perceptual recognition to highly complex spatial reasoning. The dataset is structured into single-view and multi-view scenarios, thereby enabling evaluation under different spatial perspectives.
- •
Video-MME (Fu et al., 2025) is a comprehensive benchmark for general video understanding rather than focusing exclusively on spatial aspects. It features 900 video samples and 2,700 carefully designed multiple-choice questions (three per video), spanning a broad selection of domains and activities. To ensure fairness, textual subtitles are not included in the evaluation process.
- •
TempCompass (Liu et al., 2024b) mainly focus on temporal reasoning. Comprising 410 videos and 7,540 questions, it is intended to measure how well MLLMs can track, interpret, and reason about temporal dynamics in the videos.

## Appendix C Baselines

- •
GPT-4o (Hurst et al., 2024): GPT-4o is a multimodal model that processes text, audio, image, and video with near real-time responses. It matches GPT-4 Turbo in English, performs better in non-English, and provides stronger vision and audio while being faster and cheaper.
- •
Gemini-2.0-Flash (Team et al., 2024): Gemini 2.0 Flash is a lightweight, compute-efficient multimodal model built for speed and scalability with minimal quality loss. It handles millions of tokens across text, audio, and video, achieving near-perfect long-context retrieval, strong performance in long-document and long-video QA, and efficiency for real-world applications.
- •
Claude-3.7-Sonnet (Anthropic, 2025): Claude 3.7 Sonnet is Anthropic’s hybrid reasoning model that combines fast response with extended step-by-step thinking. It is optimized for coding, reasoning, and agentic workflows, supports long-context inputs of up to 200,000 tokens, and is available through Anthropic’s API, Amazon Bedrock, and Google Cloud Vertex AI.
- •
Gemini-2.5-pro (Comanici et al., 2025):Gemini 2.5 Pro is the most advanced model in the Gemini 2.X family, delivering state-of-the-art performance on coding and reasoning benchmarks. It integrates long-context processing, multimodal understanding, and extended reasoning, with the ability to handle up to three hours of video content. This combination enables complex agentic workflows that require both deep reasoning and multimodal input.
- •
Qwen2.5-VL-7B-Instruct (Bai et al., 2025):Qwen2.5-VL-7B-Instruct is a lightweight model optimized for efficiency in resource-constrained environments. It retains key multimodal abilities such as document parsing, chart understanding, and video analysis, providing strong vision-language reasoning at lower cost.
- •
MiniCPM-V-2.6 (Yao et al., 2024):MiniCPM-V 2.6 is an efficient multimodal model designed for end-device deployment. It delivers strong OCR, high-resolution image perception, multilingual support, and low hallucination, while achieving performance comparable to larger cloud-based models at much lower cost.
- •
VideoLLaMA3-7B (Zhang et al., 2025a): VideoLLaMA3-7B is a vision-centric multimodal model for image and video understanding. Trained primarily on large-scale image-text data and refined through multi-stage alignment and fine-tuning, it supports variable-resolution inputs and compact video representations, achieving strong performance across image and video benchmarks.
- •
Video-R1 (Feng et al., 2025):Video-R1 is a multimodal model designed for video reasoning, extending the R1 reinforcement learning paradigm with temporal modeling and curated image–video datasets. Using the T-GRPO algorithm and large-scale reasoning data, it achieves notable gains on benchmarks such as VideoMMMU, MVBench, TempCompass, and surpasses GPT-4o on VSI-Bench.
- •
VideoChat-R1 (Li et al., 2025b):VideoChat-R1 is a video multimodal model enhanced through reinforcement fine-tuning with GRPO, targeting spatio-temporal perception while preserving general chat ability. It achieves state-of-the-art results on temporal grounding and object tracking, and shows consistent improvements on video QA benchmarks such as VideoMME, MVBench, and Perception Test.
- •
SpaceR (Ouyang et al., 2025):VideoChat-R1 adopts the SpaceR framework to enhance video spatial reasoning through Spatially-Guided RLVR and a new 151k dataset. It achieves state-of-the-art results on spatial reasoning benchmarks such as VSI-Bench, STI-Bench, and SPAR-Bench, surpassing GPT-4o and matching Gemini-2.0-Flash, while maintaining strong general video understanding.

## Appendix D Dataset Construction

Figure: Figure 7: Question templates of STR-205k.
Refer to caption: QAca.png

QA Generation. As illustrated in Fig. [7](https://arxiv.org/html/2510.10976v1#A4.F7), we incorporate the corresponding objects, timestamps into the question templates.

## Appendix E Additional Implementation Details

Data Sampling.
We perform uniform sampling of QAs across various task types, resulting in 12,000 QA pairs.
Furthermore, to prevent the model from degrading in general video understanding during training, we incorporate a subset with 3k QA of data from Video-R1-260k (Feng et al., 2025) to preserve its generalization capability in video understanding.

## Appendix F Additional Discussion.

Why not use SFT?
Instead of using SFT, we adopt RLVR because RLVR directly optimizes for task-specific objectives and desired behaviors, allowing the model to learn from feedback signals rather than just mimicking labeled data. This approach better aligns the model with complex reward functions, improves its adaptability, and enhances performance on tasks where simple supervised learning may not capture nuanced preferences or long-term outcomes (Ouyang et al., 2025; Feng et al., 2025).

Figure: Figure 8: Prompt Template for Training and Inference.
Refer to caption: question_late.png

Figure: Figure 9: Prompt Template for Graph Reasoning.
Refer to caption: graph_late.png

## Appendix G Prompt Template

Fig. [8](https://arxiv.org/html/2510.10976v1#A6.F8) shows the prompt template for training and inference.
Fig. [9](https://arxiv.org/html/2510.10976v1#A6.F9) illustrates the prompt template for the graph reasoning mechanism.

## Appendix H Training curves

Fig. [10](https://arxiv.org/html/2510.10976v1#A8.F10) shows the training curves of our proposed framework. It is evident that the accuracy reward shows a generally increasing trend, indicating that the model steadily improves its ability to generate correct answers under reinforcement learning.
The performance changes of our model on STI-Bench are also illustrated. An upward trend can be observed, which validates the effectiveness of the verifiable reward we designed.

Figure: Figure 10: Training curves.
Refer to caption: curves.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: Please refer to the weakness.
soundness: 3
strengths: 1. The paper is well-written and has a good organization.
2. The proposed Video-STR is reasonable and can truly process complicated video scenarios.
3. The STV-205K is carefully constructed and well aligned with the proposed framework.
4. The experiments are comprehensive, and the ablations are solid.
summary: The authors propose Video-STR, a graph-based RL framework to model the fine-grained interactions in video, enabling advanced reasoning in scenarios with heavy physical information. To facilitate the model training, they collect a large-scale training dataset, STV-205K. The experimental results demonstrate the effectiveness of the training data, training strategy (graph-based GRPO). Video-STR outperforms existing video reasoning models on most benchmarks.
weaknesses: This paper is of good quality, and I just have a question about the setting of the dataset. It looks like there are still mostly recognition-type data in the dataset, not real reasoning data. From line 173-190. However, the design of the graph can be further explored, for example, some data like the intention of a motion.

---

confidence: 4
contribution: 3
initial_rating: 4
presentation: 3
questions: Please answer the questions in the weaknesses section
soundness: 3
strengths: - The graph representation for multi-object scenes makes sense and has nice rotation-invariance properties
- The benchmarking across 6 different datasets shows the approach generalizes reasonably well
summary: The paper introduces Video-STR, using graph-based reasoning and reinforcement learning to improve spatio-temporal understanding in video MLLMs. The authors build a 205k QA dataset and extend GRPO with graph rewards. Results are promising (13% gain on STI-Bench), but the work has several technical gaps and unclear design choices that weaken the contribution.
weaknesses: - Missing critical implementation details. For example: How do you actually detect and track objects to build these graphs?; During inference, does the model predict object locations itself, or do you use an external detector?
- 205k automatically generated QA pairs with no human verification is risky. Template-based generation could introduce systematic biases
- The paper says the model is "prompted to generate such a graph" but doesn't show how. Is it predicting coordinates in structured format? 
- Which reward components actually matter? No ablation on R_format, R_n, R_e, Rl_individually
- GRPO generates 8 responses per sample - what's the actual training time and memory cost?

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: Please see weaknesses above.
soundness: 2
strengths: The motivation and problem definition are valid. 

The graph based reasoning approach is interesting and seems novel, although I am not aware of all the research in the area of video reasoning. Nevertheless, a graph-based approach appears to be a viable direction for video reasoning. 

The idea of generating a QA dataset (STV-205K) from existing datasets is innovative and useful. 

Reported experimental results are promising.
summary: This paper presents a graph-based reinforcement learning method for Video Spatio-Temporal Reasoning which models inter-object relationships using relation graphs. It introduces a graph-based reasoning mechanism in the Group Relative Policy Optimization (GRPO) [Shao et al. 2024] for inferring the underlying spatio-temporal topology of scenarios during the thinking process. The paper proposes STV-205k dataset with 205k question-answering pairs for model training and reports SOTA performance on various benchmarks including STIBench.
weaknesses: My biggest concerns include limited contribution, lack of clarity and the possible unfair comparison in experiments. Details below. 

Graph-based spatio-temporal reasoning is not a new approach and has been done previously. This work appears to be a combination of existing techniques with limited methodological novelty.  

The very first sentence of the abstract is grammatically incorrect. Overall, the writing and presentation of the paper can certainly be improved as I find it quite confusing. Which “model” is being referred to at each place? And how distances are calculated in images? How do you get Euclidean distances from images/videos? Are they in pixels and if so, how meaningful are pixel based distances in a graph?  

What is X in Eqn.(8)? It should be defined after the equation and not only in the Appendix. Going to the proof in the Appendix, X seems to be the object locations and not distances and locations should not be rotation invariant. On the other hand, graph edge weights being Euclidean distances will remain rotation invariant. Also, images/video frames are 2D images, why is the rotation R \in SO(3)? 

Also, I did not notice the proof of Theorem 2 in the Appendix (maybe I overlooked but there were no numbers with Theorem proof in the Appendix). I am also not sure if these two theorems are worth mentioning at all. 

At this point, I should also highlight the ambiguity in the proposed dataset description. It is not explicitly mentioned which data modality and labels are obtained from the three datasets (TAO, ScanNet and KITTI) e.g. ScanNet and KITTI also have depth images/point clouds. There is no mention of 3D, depth or point cloud in the paper so I assume the paper is about conventional video reasoning but then “Euclidean distance” is mentioned at many places which is confusing. Yes, the Euclidean distances can be in pixel units but that would be meaningless in a scene graph e.g. the chair is two pixels to the right of the table. 

Referring to “The model is prompted to generate a graph” on page 5, which model is prompted? The following sentence is also confusing where “model” is used twice. Are they both the same model or two different models? 

On page 2 it is mentioned that “we extend the Group Relative Policy Optimization (GPRO)” but in Section 4.3, it is not clearly mentioned how GPRO is extended in this paper. 

The results in Table 1 look very good but I am wondering if the improvement is mainly due to the additional training data from newly proposed STV-205k dataset. Since the other methods did not use this additional dataset, the comparison is unfair. 

Page 7: “SFT achieves localized improvements”. What does “localized improvement” mean? 

In Fig.4(b), the improvement on “Static” sub-task is quite substantial compared to “Temporal”. This makes me wonder how the graph encodes temporal information. 

In Sec. 5.3, “Video-260k”, “SR-91k” are mentioned, but no reference or any further information is given about these datasets. 

Overall, the proposed method may have merit but that is obscured by unclear presentation. Moreover, unfair comparison with existing works also undermines its credability.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: After fine-tuning the model on graph-based spatio-temporal reasoning, how is it applied to the downstream benchmark tasks? Is there additional fine-tuning involved? Any task-specific (few-shot?) prompting?  

The work is reminiscent of older works on graph-based grounding, such as “Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations”, Krishna et al 2016, and many related and follow-up papers). It would be good to see a discussion on how it is related to this line of research. 

(small comment:) The frames in the figures (for example, Figure 1, Figure 2) are impossible to see properly or understand in a print-out version of the paper.
soundness: 3
strengths: The paper is quite easy to follow. It describes an (automatically generated) dataset, a training method and a model (based on fine-tuning Qwen2.5-VL-7B), all of which will be publicly released. The model yields fairly good performance on some video understanding benchmarks, specifically those that test for an understanding of object positions and their relations.
summary: The paper describes a dataset consisting of Question-Answer pairs about object-based tasks (such as counting, discances, movements, etc.) that were automatically generated from existing video dataset (TAO, ScanNet and KITTI). It also describes a reward design for RL-based training, based on the positions of objects as well as their positions relative to one another. It then shows that together, these two ingredients make it possible to fine-tune Qwen2.5-VL-7B to achieve relatively high recognition performance on several video understanding benchmarks (STI-bench, V-STaR, etc.). Ablations furthermore show that all the ingredients contribute positively to performance improvements on these benchmarks.
weaknesses: I have the concern that the object-centric data and reward designs are benefitting specifically tasks that measure the ability to understand object positions and relations, without enhancing the model’s visual understanding overall. The results suggest that this is indeed the case, as model performance on tasks like STI-bench and V-STaR is comparably high, while this is not nearly as much the case for tasks like Video-MME (where the model is in fact significantly behind the state of the art). 

Overall, this paper describes an engineering effort, based on automatically generated data and RL-training with object-centric rewards, to mildly improve performance on video-understanding benchmarks (and most significantly on object-centric benchmarks). I am not quite sure how this advances our understanding of visual capabilities, models and model limitations overall. I am also missing a view of the limitations of the object-centric design. For example, are there any tasks where performance degrades rather than benefits from this design?


Decision: Reject