PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Compositional Spatio-Temporal Video Grounding with Synthetic Curriculum

Xingjian Wang, Shijian Wang, Yibo Wang, Zihao Yu, Runhao Fu, Xuelian Cheng, Zongyuan Ge

arXiv:2608.30584v1cs.CV

TL;DR

Existing STVG data and evaluations underrepresent compositional queries that require jointly reasoning over essential attributes and relations. The paper introduces CompSTVG, a scene-graph-based difficulty-controlled synthesis engine, STVG-CompBench, and CurrSTVG. Across 11 grounders, performance drops sharply with difficulty, while CurrSTVG produces its largest gains on the hardest queries.

  • Problem

    Existing STVG corpora and benchmarks largely use simplistic queries, leaving compositional grounding with jointly required attribute and relational cues insufficiently addressed.

  • Method

    The paper constructs CompSTVG and STVG-CompBench with scene-graph-based difficulty measurement and constraint-programmed query synthesis, then trains CurrSTVG with curriculum reinforcement learning.

  • Results

    Across 11 representative grounders, performance degrades sharply as difficulty increases, while CurrSTVG achieves its largest gains on the hardest compositional queries.

  • Takeaways & Limitations

    The framework makes compositionality measurable, controllable, and actionable by tying one difficulty axis to both benchmark construction and training.

  • Takeaways & Limitations

    Out-of-domain transfer remains imperfect, very short target tracks yield unstable spatial-reward gradients, and IoU rewards can encourage over-long outputs.

Abstract

from arXiv · show

Despite the impressive progress of recent MLLMs on spatio-temporal video grounding (STVG), existing evaluations and training data focus primarily on simple queries. They largely overlook the compositional queries prevalent in real-world scenarios, where a target must be disambiguated by jointly reasoning about its attributes and relations to other entities. To bridge this gap, we propose Compositional Spatio-Temporal Video Grounding (CompSTVG), a task that requires models to process complex textual queries where every intertwined attribute and relational cue is essential for disambiguation. To facilitate this task at scale, we build a synthetic data engine that leverages a spatio-temporal scene graph as a difficulty measure and casts difficulty-controlled query synthesis as a constraint programming problem, producing difficulty-graded data for both evaluation and training. Built on this engine, we introduce STVG-CompBench, a benchmark stratified by explicit difficulty levels that jointly capture temporal complexity and spatial interference. Evaluating 11 representative STVG models on STVG-CompBench reveals that current models perform poorly on compositional queries, exhibiting a sharp performance drop that is typically obscured by overall dataset-level averages. We further construct synthetic training data and propose CurrSTVG, a curriculum reinforcement learning framework that delivers consistent gains, with the largest improvements observed on the most challenging compositional queries.

1 Introduction

The paper identifies a gap in STVG: existing data emphasize simplistic queries, whereas real-world grounding requires jointly using essential attribute and relational cues. It introduces CompSTVG, a difficulty-controlled synthetic engine, STVG-CompBench, and CuRRSTVG to measure and improve compositional grounding.

  • Existing STVG benchmarks and training corpora are dominated by simplistic queries resolvable through superficial or singular cues.
  • Compositional STVG requires appearance, action, temporal, spatial, and relational cues to jointly disambiguate targets from distractors.
  • CompSTVG generates non-redundant queries by combining spatio-temporal scene graphs, difficulty-controlled distractors, and binary integer programming.
  • STVG-CompBench stratifies compositional grounding examples into explicit difficulty tiers for evaluation.
  • Evaluations of 11 representative grounders reveal severe performance degradation as compositional query complexity increases across transformer and MLLM paradigms.
  • CuRRSTVG uses curriculum reinforcement learning to schedule difficulty-labeled samples from easy to hard and achieves its largest gains on the hardest queries.

2 Related Work

Prior work studies compositionality in language, action-object recognition, and structured video reasoning, but does not directly address arbitrary natural-language tube grounding with multidimensional cues and distractors.

  • Early STVG methods use detector proposals and matching networks, while one-stage transformers regress tubes end-to-end but degrade on long, multiclause queries.
  • Recent STVG work extends grounding to multimodal large language models, including LLaVA-ST and SpaceVLLM.
  • Compositional temporal grounding tests novel lexical combinations, whereas compositional action localization tests novel action-object combinations.
  • Unlike these settings, CompSTVG grounds arbitrary natural-language descriptions to tubes while controlling multidimensional attribute composition against same-category distractors and look-alike intervals.

3 Task Formulation

CompSTVG generalizes STVG by requiring non-redundant compositions of target attributes and inter-entity relations, with explicit difficulty labels based on temporal and spatial competitors.

  • CompSTVG constrains queries to combine target attributes and relations without allowing any single dominant cue to resolve disambiguation.
  • A CompSTVG input is an untrimmed video and natural-language query, and the output is a spatio-temporal tube uniquely localizing one or more targets.
  • The non-redundancy constraint requires every query cue because no proper subset may uniquely identify the target tube.
  • Attribute cues include category, appearance, action, and temporal pattern, while relation cues include spatial layout and interactions with other entities.
  • Each query receives a three-level difficulty label measuring disambiguation against temporal competitors and spatial competitors.

4 Synthesizing Difficulty-Controlled Compositional STVG Data

The paper constructs a synthetic, STSG-based engine that measures query difficulty through temporal and spatial competitors, then samples minimal cue compositions under explicit constraints. Globally optimized queries are verbalized into difficulty-graded data for evaluation and training.

  • STSG construction: The engine represents each video with an STSG containing temporal intervals, object tubes, object attributes, action nodes, and spatial or non-spatial relation edges.Object tubes include categories, appearances, environment phrases, and frame-indexed tracks; action nodes attach labels, target arguments, and durations.
  • Difficulty measurement: Query difficulty measures compositional confusion against temporal competitors and same-arity spatial competitors rather than graph complexity alone.Temporal competitors are other intervals of the target object, while spatial competitors are rival candidates with different identities.
  • Difficulty measurement: Temporal difficulty reflects the complement of attribute-based exclusion, while spatial difficulty uses similarity and overlap with rivals before the combined score is binned into three levels.The spatial score uses Jaccard–tIoU similarity, an exponent β to amplify highly confusable rivals, and a soft count bounded in [0, 1].
  • Difficulty-controlled sampling: Cue selection solves a 0–1 integer program that minimizes the smallest attribute subset excluding every competitor within a template’s stylistic budget.Constraints cover competitor exclusion, target-tuple coverage, cue-type ranges, query length, temporal-chain complexity, and sequentially qualified cues.
  • Difficulty-controlled sampling: CompSolveR returns a globally optimal feasible cue subset, skips infeasible candidate-template pairs, and has no heuristic fallback before LLM verbalization.Fourteen templates span single- and multi-target query arities.
  • Dataset construction: Each accepted sample stores the video, verbalized query, target tube, and difficulty bin, forming separate held-out benchmark and training splits.The target tube is read from the selected object tuple and interval, and iterating over videos and difficulty bins produces the graded corpus.

5 STVG-CompBench: Diagnosing the Compositional Gap

STVG-CompBench evaluates 11 representative grounders across explicit difficulty buckets to test whether compositional degradation is visible beyond dataset-level averages. Results show a performance cliff as difficulty increases, while CuRRSTVG yields its largest gains on the hardest queries.

  • Experiment Setup: STVG-CompBench contains 2,000 balanced samples organized across Easy, Medium, and Hard difficulty buckets.The benchmark is drawn from 2,000 long, multi-shot source videos and balanced across difficulty bins and attribute–relation cue combinations.
  • Experiment Setup: The study evaluates eleven representative grounders spanning transformer-based and MLLM-based paradigms under a unified 1 FPS scoring protocol.Models use officially released checkpoints, with predictions at other rates linearly interpolated to 1 FPS before scoring.
  • Main Results: Most grounders degrade sharply as difficulty increases, revealing a performance cliff that dataset-level averages hide.TA-STVG loses 14.2 m_vIoU from Easy to Hard, while TubeDETR drops from 18.01 to 7.00.
  • Main Results: The high-IoU regime collapses on Hard queries, with vIoU@0.5 falling from 10–16 on Easy to essentially zero.Residual m_vIoU on Hard therefore reflects loose predictions rather than correct tubes.
  • Main Results: CuRRSTVG improves m_tIoU over the strongest baseline LLaVA-ST by 13.3, 28.0, and 28.2 points on Easy, Medium, and Hard, respectively.The largest absolute gain occurs on Hard queries, the regime that current STVG benchmarks under-represent.

6 CurrSTVG: Curriculum RL on Synthetic Difficulty

CuRRSTVG turns synthetic difficulty labels into an easy-to-hard curriculum reinforcement-learning schedule for compositional STVG. It combines format, temporal, and spatial rewards, improves generalization to established benchmarks, and benefits most from curriculum training on hard queries.

  • Training strategy: CuRRSTVG trains Qwen3-VL-8B with a short SFT stage followed by GRPO, introducing harder difficulty buckets only after rewards plateau.The curriculum uses the same difficulty labels that organize the synthetic data.
  • Reward design: The composite reward combines format correctness, predicted-interval tIoU, and temporally rescaled per-frame box IoU.The spatial reward averages IoU over temporally overlapping frames and rescales it by temporal overlap.
  • Generalization: CuRRSTVG transfers to standard STVG benchmarks despite never seeing their training data.Evaluation covers HC-STVG-v2 and VidSTG under out-of-domain settings.
  • Generalization: 46.7 m_tIoU is achieved on HC-STVG-v2, while vIoU@0.3 increases from 6.2 to 12.3 and vIoU@0.5 from 0.2 to 2.32 over the Qwen3-VL backbone.On VidSTG, performance remains competitive on most metrics, with interrogative sentences generally trailing declarative ones on m_vIoU and vIoU.
  • Curriculum ablation: The curriculum variant clearly outperforms shuffled training on STVG-CompBench, with the gap concentrated in the hardest bucket.Shuffled training encounters hard queries before format and temporal rewards stabilize, producing noisy spatial-reward gradients.
  • Data verification: 94.7% trajectory, 91.7% attribute, and 93.6% relation accuracy support the reliability of the STSG construction pipeline.Unique reference and temporal range are lower at 85.4% and 80.3%, respectively; 3.1% of all judged items are fabricated or mismatched.
  • Solver ablation: CompSolveR matches the generic ILP backend on every quality metric while running roughly three times faster.The generic ILP backend has 81.2 ms mean and 327.1 ms tail latency, whereas random and greedy heuristics introduce feasibility and optimality problems.

7 Conclusion

The paper introduces compositional STVG, a difficulty-graded synthetic data engine, STVG-CompBench, and CuRRSTVG. By sharing one difficulty axis across benchmark construction and training, the framework makes compositionality measurable and actionable while identifying remaining transfer and temporal-reasoning limitations.

  • Task and framework: Compositional STVG requires non-redundant attribute and relation cues, graded by an explicit difficulty label.The task prevents disambiguation from relying on a single dominant cue.
  • Task and framework: The STSG-based constraint-programming engine builds STVG-CompBench and supplies difficulty-controlled training data for CuRRSTVG.The same difficulty axis connects dataset construction, evaluation, and curriculum reinforcement learning.
  • Findings and outlook: CuRRSTVG delivers its largest gains where the compositional cliff is steepest, while transfer and short-track limitations motivate broader data coverage and more robust temporal reasoning.These limitations are identified as directions for future work.

Limitations

CuRRSTVG has three reported scope boundaries: imperfect out-of-domain transfer, instability on very short target tracks, and a reward shape that can favor over-long outputs.

  • Scope boundaries: Out-of-domain transfer remains imperfect: CuRRSTVG trails the strongest specialist baselines on HC-STVG-v2 and VidSTG.The model transfers without seeing those benchmarks’ training data.
  • Scope boundaries: Performance degrades on very short target tracks because the temporally-rescaled spatial reward concentrates on too few frames for a stable gradient.
  • Scope boundaries: The IoU-based reward can incentivize over-long outputs because widening predicted intervals and padding JSON references are not penalized by format checks.Rollout-length penalties partially mitigate this issue.

A Evaluated Models

The evaluation covers general-purpose vision-language models and specialist STVG grounders under a unified protocol, while blank evaluation cells are excluded from quantitative claims.

  • Model families: The benchmark evaluates general-purpose vision-language models alongside specialist STVG models.Specialist models range from transformer-based one-stage grounders to MLLM-based grounders.
  • Model families: Vanilla MLLMs receive prompts for per-frame boxes and a temporal interval, which are post-processed into tubes without additional training.
  • Model families: Qwen3-VL-8B serves both as a baseline and as the backbone of CuRRSTVG.
  • Model families: Specialist baselines include TubeDETR, CG-STVG, TA-STVG, LLaVA-ST, and VideoChat-R1.
  • Evaluation protocol: Blank evaluation cells for several models indicate evaluations in progress and are excluded from quantitative claims.

B Evaluation Metrics

Evaluation follows the standard STVG protocol with one temporal and three spatio-temporal metrics, reported both overall and by difficulty bucket.

  • Metric suite: The evaluation reports four metrics: one temporal metric and three spatio-temporal metrics.
  • Metric suite: m_tIoU is mean temporal Intersection-over-Union averaged over all queries.
  • Metric suite: m_vIoU combines temporal alignment with per-frame box overlap using only temporally overlapping frames and temporal-union rescaling.
  • Metric suite: vIoU@τ measures the fraction of queries whose video IoU exceeds threshold τ, with τ ∈{0.3, 0.5}.vIoU@0.5 represents the high-precision regime relevant to downstream tube consumption.
  • Difficulty-stratified reporting: All four metrics are reported overall and within each difficulty bucket to expose compositional weaknesses hidden by dataset-level averages.

C Benchmark Details

The benchmark uses scene-graph-driven queries over long videos, disjoint balanced splits, and a unified 1 FPS inference protocol with structured relation and attribute extraction.

  • Dataset construction: The dataset is built from 2,000 long, multi-shot videos, evenly sampled from MOSE and the Perception Test.Queries are sampled on spatio-temporal scene graphs using an ILP-based procedure.
  • Dataset construction: The corpus contains 7,785 queries split into 2,000 evaluation and 5,785 training queries with disjoint videos.Both splits are balanced across three difficulty levels, with no shared video, scene graph, or query.
  • Evaluation protocol: All models process frames at 1 FPS, with predictions interpolated to 1 FPS when necessary and the same temporal resolution used for CuRRSTVG training.
  • Scene-graph annotation: The data engine extracts per-object attributes, pairwise spatial relations, non-spatial temporal relations, and cross-shot identity matches for tube unification.
  • Scene-graph annotation: Prompts constrain spatial extraction to visually supported geometric relations and temporal extraction to continuous intervals where both marked objects are present.The structured outputs use object IDs, predicates, and frame-indexed time spans.
Loading 2608.30584v1…