Research map / Video / Video-language understanding
STEP: Enhancing Video-LLMs' Compositional Reasoning by Spatio-Temporal Graph-guided Self-Training
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STEP, a graph-guided self-training method where Video-LLMs induce spatio-temporal scene graphs from raw videos, sample multi-step reasoning paths to create QA pairs with CoT rationales, and train on answers plus rationales.
Problem
Video-LLMs struggle with compositional reasoning requiring multi-step spatio-temporal inference, and existing training data is costly to annotate, lacks spatio-temporal compositionality, and provides no explicit reasoning supervision.
Approach
Self-generate reasoning-rich QA pairs and step-by-step CoT rationales from spatio-temporal scene graphs induced by the Video-LLM itself, via symbolic structure induction (visual splitting, semantics parsing, dynamic merging, cross-clip bridging) and stepwise graph-driven path sampling, then train on both answers and rationales.
Key results
- On STAR questions requiring three or more reasoning steps, VideoChat2* STEP reaches 33.6 vs 27.7 for VideoChat2* baseline (21.3% relative improvement).
- VideoChat2* STEP improves average accuracy on AGQA from 36.5 to 39.2 and on STAR from 34.8 to 39.8.
- STEP outperforms the GPT-4V distillation control and the manually annotated Instruct model on compositional and standard QA benchmarks with both VideoChat2* and VILA backbones.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace scene-cut detection and clustered keyframes with uniform intervals and evenly sampled frames (ablation) | STEP with VideoChat2* · AGQA | accuracy: 38.9 -> 39.2 | Helped |
| replace scene-cut detection and clustered keyframes with uniform intervals and evenly sampled frames (ablation) | STEP with VideoChat2* · STAR | accuracy: 39.2 -> 39.8 | Helped |
| add incremental parsing of attributes, objects, and relations to the simplified scene-graph prompt (ablation) | STEP with VideoChat2* · AGQA | accuracy: 37.8 -> 39.2 | Helped |
| add incremental parsing of attributes, objects, and relations to the simplified scene-graph prompt (ablation) | STEP with VideoChat2* · STAR | accuracy: 36.5 -> 39.8 | Helped |
| merge redundant nodes and represent dynamic information (ablation) | STEP with VideoChat2* · AGQA | accuracy: 38.3 -> 39.2 | Helped |
| merge redundant nodes and represent dynamic information (ablation) | STEP with VideoChat2* · STAR | accuracy: 37.3 -> 39.8 | Helped |
| add cross-clip information (ablation) | STEP with VideoChat2* · AGQA | accuracy: 38.6 -> 39.2 | Helped |
| add cross-clip information (ablation) | STEP with VideoChat2* · STAR | accuracy: 38.3 -> 39.8 | Helped |
| set rationale-loss weight λ to 1 (ablation) | STEP with VideoChat2* · AGQA and STAR | accuracy | Helped |
| balance simple and complex reasoning-step samples rather than using only 1-step or only 3-step questions (ablation) | STEP with VideoChat2* · AGQA and STAR | accuracy | Helped |
| use STEP self-training instead of manually annotated instruction-tuning data | VideoChat2* · AGQA | accuracy: 37.4 -> 39.2 | Helped |
| use STEP self-training instead of GPT-4V-generated distillation data | VideoChat2* · STAR | accuracy: 37.6 -> 39.8 | Helped |
Surprising findings
- Self-training with the model's own generated data outperformed distillation from the stronger GPT-4V teacher, which the authors attribute to lower training loss (better alignment with the base model) and filtering of STSG accuracy.
Limitations
- Relies on the base model's instruction-following ability to construct STSGs, requiring an initial instruction-tuning stage.
- Evaluation of open-ended QA depends on GPT-3.5-turbo judging, and STAR reasoning-step counts were manually assigned per template.
- Dataset size and compute details are not clearly reported in the main text.
Experimental setup
Datasets: AGQA STAR existing instruction-tuning data (for initial instruction tuning) raw untrimmed videos
Benchmarks: AGQA STAR MSVD-QA MSRVTT-QA ActivityNet-QA MVBench TempCompass MovieChat-1K MLVU
Metrics: accuracy average score (0-5)
Baselines: VideoChat2* VideoChat2* Instruct VideoChat2* Distillation (GPT-4V) VILA Instruct VILA Distillation VideoChatGPT Video-LLaVA mPLUG-Owl-V
Builds on: VideoChat2 Video-of-Thought Video-STAR chain-of-thought
Closest papers by meaning
- VELOCITI: Benchmarking Video-Language Compositional Reasoning with Strict Entailment (CVPR 2025 · similarity 0.90)
- SF2T: Self-supervised Fragment Finetuning of Video-LLMs for Fine-Grained Understanding (CVPR 2025 · similarity 0.90)
- VideoEspresso: A Large-Scale Chain-of-Thought Dataset for Fine-Grained Video Reasoning via Core Frame Selection (CVPR 2025 · similarity 0.89)
- Look, Remember and Reason: Grounded Reasoning in Videos with Language Models (ICLR 2024 · similarity 0.89)
- Tool-Augmented Spatiotemporal Reasoning for Streamlining Video Question Answering Task (NeurIPS 2025 · similarity 0.89)
- Modularized Self-Reflected Video Reasoner for Multimodal LLM with Application to Video Question Answering (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.