# STEP: Enhancing Video-LLMs' Compositional Reasoning by Spatio-Temporal Graph-guided Self-Training

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Multimodal reasoning, one of 17 directions in LLM reasoning.
- Builds on 30 of its 64 references that are in the map.
- First posted on arXiv 29 Nov 2024.

## Placed in

- LLM reasoning / [Multimodal reasoning](https://mlsanity.com/lr/multimodal-reasoning/)
- Synthetic data and self-improvement for LLMs / [Self-improving MLLMs and synthetic data](https://mlsanity.com/synth/self-improving-mllms-and-synthetic-data/)

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Finetuned Language Models Are Zero-Shot Learners](https://mlsanity.com/paper/2109.01652/) (2021)
- [Video-LLaMA: An Instruction-tuned Audio-Visual Language Model for Video Understanding](https://mlsanity.com/paper/2306.02858/) (2023)
- [Video-LLaVA: Learning United Visual Representation by Alignment Before Projection](https://mlsanity.com/paper/2311.10122/) (2023)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Video-ChatGPT: Towards Detailed Video Understanding via Large Vision and Language Models](https://mlsanity.com/paper/2306.05424/) (2023)
- [mPLUG-Owl: Modularization Empowers Large Language Models with Multimodality](https://mlsanity.com/paper/2304.14178/) (2023)
- [VideoChat: Chat-Centric Video Understanding](https://mlsanity.com/paper/2305.06355/) (2023)
- [Large Language Models Can Self-Improve](https://mlsanity.com/paper/2210.11610/) (2022)
- [LLaMA-VID: An Image is Worth 2 Tokens in Large Language Models](https://mlsanity.com/paper/2311.17043/) (2023)
- [CLEVRER: CoLlision Events for Video REpresentation and Reasoning](https://mlsanity.com/paper/1910.01442/) (2019)
- [TVQA: Localized, Compositional Video Question Answering](https://mlsanity.com/paper/1809.01696/) (2018)
- [TempCompass: Do Video LLMs Really Understand Videos?](https://mlsanity.com/paper/2403.00476/) (2024)
- [MLVU: Benchmarking Multi-task Long Video Understanding](https://mlsanity.com/paper/2406.04264/) (2024)
- [STAR: A Benchmark for Situated Reasoning in Real-World Videos](https://mlsanity.com/paper/2405.09711/) (2024)
- [Orca 2: Teaching Small Language Models How to Reason](https://mlsanity.com/paper/2311.11045/) (2023)
- [ST-LLM: Large Language Models Are Effective Temporal Learners](https://mlsanity.com/paper/2404.00308/) (2024)
- [Momentor: Advancing Video Large Language Model with Fine-Grained Temporal Reasoning](https://mlsanity.com/paper/2402.11435/) (2024)
- [Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs](https://mlsanity.com/paper/2404.07103/) (2024)
- [MiniGPT4-Video: Advancing Multimodal LLMs for Video Understanding with Interleaved Visual-Textual Tokens](https://mlsanity.com/paper/2404.03413/) (2024)
- [Self-Training: A Survey](https://mlsanity.com/paper/2202.12040/) (2022)
- [V2Xum-LLM: Cross-Modal Video Summarization with Temporal Prompt Instruction Tuning](https://mlsanity.com/paper/2404.12353/) (2024)
- [Grounded Multi-Hop VideoQA in Long-Form Egocentric Videos](https://mlsanity.com/paper/2408.14469/) (2024)
- [VoCoT: Unleashing Visually Grounded Multi-Step Reasoning in Large Multi-Modal Models](https://mlsanity.com/paper/2405.16919/) (2024)
- [FreeVA: Offline MLLM as Training-Free Video Assistant](https://mlsanity.com/paper/2405.07798/) (2024)
- [Video-STaR: Self-Training Enables Video Instruction Tuning with Any Supervision](https://mlsanity.com/paper/2407.06189/) (2024)
- [VILA2: VILA Augmented VILA](https://mlsanity.com/paper/2407.17453/) (2024)
- [Stronger Models are NOT Stronger Teachers for Instruction Tuning](https://mlsanity.com/paper/2411.07133/) (2024)
- [Enhancing Logical Reasoning in Large Language Models through Graph-based Synthetic Data](https://mlsanity.com/paper/2409.12437/) (2024)
- [Fact :Teaching MLLMs with Faithful, Concise and Transferable Rationales](https://mlsanity.com/paper/2404.11129/) (2024)

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

- [VideoRFT: Incentivizing Video Reasoning Capability in MLLMs via Reinforced Fine-Tuning](https://mlsanity.com/paper/2505.12434/) (2025)
- [Video-MMLU: A Massive Multi-Discipline Lecture Understanding Benchmark](https://mlsanity.com/paper/2504.14693/) (2025)
- [Generative Multimodal Pretraining with Discrete Diffusion Timestep Tokens](https://mlsanity.com/paper/2504.14666/) (2025)
- [FocusDiff: Advancing Fine-Grained Text-Image Alignment for Autoregressive Visual Generation through RL](https://mlsanity.com/paper/2506.05501/) (2025)
- [Mastering Collaborative Multi-modal Data Selection: A Focus on Informativeness, Uniqueness, and Representativeness](https://mlsanity.com/paper/2412.06293/) (2024)
- [Benchmarking Multimodal CoT Reward Model Stepwise by Visual Program](https://mlsanity.com/paper/2504.06606/) (2025)
- [Janus-Pro-R1: Advancing Collaborative Visual Comprehension and Generation via Reinforcement Learning](https://mlsanity.com/paper/2506.01480/) (2025)
- [GraphThinker: Reinforcing Temporally Grounded Video Reasoning with Event Graph Thinking](https://mlsanity.com/paper/2602.17555/) (2026)
- [DyGEnc: Encoding a Sequence of Textual Scene Graphs to Reason and Answer Questions in Dynamic Scenes](https://mlsanity.com/paper/2505.03581/) (2025)
- [FocusGraph: Graph-Structured Frame Selection for Embodied Long Video Question Answering](https://mlsanity.com/paper/2603.04349/) (2026)
- [ViKey: Enhancing Temporal Understanding in Videos via Visual Prompting](https://mlsanity.com/paper/2603.23186/) (2026)
- [CurEvo: Curriculum-Guided Self-Evolution for Video Understanding](https://mlsanity.com/paper/2604.26707/) (2026)
- [Spatiotemporal Knowledge Graphs as Persistent Scene Memory for Embodied Question Answering](https://mlsanity.com/paper/2510.01483/) (2025)
- [EventFormer: A Node-graph Hierarchical Attention Transformer for Action-centric Video Event Prediction](https://mlsanity.com/paper/2510.21786/) (2025)
- [VTI-CoT: Visual-Textual Interleaved Chain of Thought for Video Reasoning](https://mlsanity.com/paper/2606.05736/) (2026)
- [Learning to Evolve Scenes: Reasoning about Human Activities with Scene Graphs](https://mlsanity.com/paper/2607.02425/) (2026)
- [MissionHD: Hyperdimensional Refinement of Distribution-Deficient Reasoning Graphs for Video Anomaly Detection](https://mlsanity.com/paper/2508.14746/) (2025)
- [Cross-modal Identity Mapping: Minimizing Information Loss in Modality Conversion via Reinforcement Learning](https://mlsanity.com/paper/2603.01696/) (2026)
- [Comparison Drives Preference: Reference-Aware Modeling for AI-Generated Video Quality Assessment](https://mlsanity.com/paper/2604.17074/) (2026)
- [Sink-Token-Aware Pruning for Fine-Grained Video Understanding in Efficient Video LLMs](https://mlsanity.com/paper/2604.20937/) (2026)
- [GRACE: Boosting Video MLLMs with Grounded Action-Centric Evidence for Viewer Sentiment Prediction](https://mlsanity.com/paper/2606.16198/) (2026)
- [STSG-VQA: Evidence-Grounded Temporal Question Answering from Surgical Spatio-Temporal Scene Graphs](https://mlsanity.com/paper/2609.08543/) (2026)

## Abstract (arXiv)

Video Large Language Models (Video-LLMs) have recently shown strong performance in basic video understanding tasks, such as captioning and coarse-grained question answering, but struggle with compositional reasoning that requires multi-step spatio-temporal inference across object relations, interactions, and events. The hurdles to enhancing this capability include extensive manual labor, the lack of spatio-temporal compositionality in existing data and the absence of explicit reasoning supervision. In this paper, we propose STEP, a novel graph-guided self-training method that enables Video-LLMs to generate reasoning-rich fine-tuning data from any raw videos to improve itself. Specifically, we first induce Spatio-Temporal Scene Graph (STSG) representation of diverse videos to capture fine-grained, multi-granular video semantics. Then, the STSGs guide the derivation of multi-step reasoning Question-Answer (QA) data with Chain-of-Thought (CoT) rationales. Both answers and rationales are integrated as training objective, aiming to enhance model's reasoning abilities by supervision over explicit reasoning steps. Experimental results demonstrate the effectiveness of STEP across models of varying scales, with a significant 21.3% improvement in tasks requiring three or more reasoning steps. Furthermore, it achieves superior performance with a minimal amount of self-generated rationale-enriched training samples in both compositional reasoning and comprehensive understanding benchmarks, highlighting the broad applicability and vast potential.