Source-linked AI summary
Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding
Hanoona Rasheed, Haania Siddiqui, Ming-Hsuan Yang, Fahad Shahbaz Khan, Salman Khan
TL;DR
STVG requires temporal event localization and spatial tracking, but autoregressive dense trajectories incur length-dependent latency and error propagation. PTD predicts a temporal block followed by parallel time-conditioned spatial blocks, using decoupled attention and localization-aware optimization. It achieves large efficiency gains with improved grounding accuracy, favorable benchmark performance, and zero-shot transfer across related video tasks.
Problem
Existing MLLM-based STVG serializes dense localization trajectories autoregressively, making latency grow with tube length and allowing localization errors to propagate across time.
Method
PTD generates one temporal block followed by parallel time-conditioned spatial blocks, with Decoupled Block Attention removing cross-box dependencies and localization-aware policy optimization refining boundaries and box geometry.
Results
79× lower Tube Completion Latency and 92× higher spatial decoding throughput over standard autoregressive decoding accompany stronger grounding accuracy, favorable VidSTG and HC-STVG performance, and zero-shot transfer to three video tasks.
Takeaways & Limitations
Dense spatio-temporal localization can be generated efficiently without sequential trajectory decoding, including with a 4B backbone and no dedicated spatial localization module.
Takeaways & Limitations
The current formulation supports one interval and one spatial tube, leaving disjoint occurrences, temporary out-of-view periods, and multiple matching instances largely unexplored.
Abstract
from arXiv · showhide
Spatio-temporal video grounding (STVG) requires models to identify when a referred event occurs and localize the target entity throughout that interval. Existing multimodal large language models typically serialize dense localization trajectories autoregressively, causing decoding latency to grow with tube length and allowing localization errors to propagate across time. We introduce Parallel Tube Decoding (PTD), a generative formulation that decomposes grounding into a temporal block followed by time-conditioned spatial blocks decoded simultaneously. This removes both token-level and trajectory-level dependencies, reducing the sequential decoding depth to a fixed $1 + 1$ rounds, independent of tube length. To enable parallel spatial generation, we introduce Decoupled Block Attention, which preserves access to shared video-query context while eliminating cross-box dependencies, together with localization-aware policy optimization for temporal boundaries and spatial geometry. On VidSTG, PTD reduces Tube Completion Latency by 79x and increases spatial decoding throughput by 92x over standard autoregressive decoding, while also improving grounding accuracy. With a compact 4B backbone, our model performs favorably well on VidSTG and HC-STVG, and generalizes zero-shot to temporal grounding, grounded VideoQA, and referring video object tracking. Our results show parallel tube generation is an efficient and effective alternative to autoregressive localization in videos.
1 Introduction
STVG must identify an event’s temporal interval and localize its referred entity throughout that interval, but autoregressive tube decoding becomes slower with longer tubes and can propagate early errors. PTD addresses these dependencies by generating a temporal block first and time-conditioned spatial blocks in parallel, while adding decoupled attention and localization-aware optimization.
- STVG identifies when a queried event occurs and localizes the referred entity throughout that interval.
- Autoregressive coordinate sequences make decoding depth and latency grow with tube length, while generated-box history can propagate early errors across the trajectory.
- PTD decomposes tube generation into one temporal block followed by time-conditioned spatial blocks predicted in parallel across the interval.
- Two decoding rounds replace 4+7T rounds under Quantized Token Decoding and 1+T under Sequential Block Decoding, independent of the number of boxes.
- Decoupled Block Attention removes cross-box dependencies while preserving shared multimodal evidence for each box’s temporal position.
- 79× lower Tube Completion Latency and 92× higher spatial decoding throughput over unquantized token decoding accompany improved localization quality, competitive 4B-backbone performance, and zero-shot transfer.The transfer targets are temporal grounding, evidence-grounded VideoQA, and referring video object tracking.
2 Related Works
Related STVG methods use task-specific or multimodal architectures to infer temporal boundaries and spatial tubes, while newer efficient approaches either offload spatial localization or retain token-by-token tube generation. This motivates reducing sequential dependencies within unified generative localization.
- Early STVG approaches combine graph reasoning, crossmodal transformers, or DETR-style decoders to infer temporal boundaries and corresponding spatial tubes.
- Bridge-STG and DEViL reduce MLLM output length and decoding cost by offloading dense spatial localization to dedicated decoders or detectors.
- Discrete spatial and temporal tokens reduce representation overhead, but language-decoder methods still generate the complete tube token by token.
3 Method
PTD reformulates STVG as temporal localization followed by parallel, time-conditioned spatial localization, removing token-level and trajectory-level dependencies. Its attention and training design preserve multimodal grounding while enabling fixed-depth tube generation and localization-aware optimization.
- Task formulation: STVG predicts an event interval and a bounding-box tube for the referred entity across that interval.The formulation represents the output as temporal boundaries plus time-indexed spatial boxes.
- Decoding strategies: Quantized Token Decoding reduces each coordinate to one token but still requires 4+7T sequential decoding rounds for a tube with T boxes.The temporal interval uses four token predictions, while each spatial box uses seven.
- Decoding strategies: Sequential Block Decoding jointly predicts tokens within each localization block, reducing depth to 1+T while retaining sequential dependencies across spatial blocks.Each additional spatial prediction still adds another sequential round as tube length grows.
- Parallel Tube Decoding: PTD predicts one temporal block followed by all time-conditioned spatial blocks in parallel, reducing sequential depth to 1+1 independent of tube length.Longer tubes increase parallel width rather than sequential decoding rounds.
- Parallel Tube Decoding: Decoupled Block Attention gives each spatial block shared multimodal and temporal context while isolating it from other spatial blocks.This removes cross-box dependencies while retaining bidirectional attention within each block.
- Training and evaluation: The method combines dual-formulation training with Tube Completion Latency and Boxes Per Second metrics and localization-aware policy optimization.The optimization uses complementary temporal and spatial rewards, while the metrics quantify completion time and spatial decoding throughput.
4 Experiments
Experiments show that progressively reducing sequential dependencies improves decoding efficiency and grounding quality. PTD maintains near-constant latency, achieves strong in-domain performance with a compact backbone, and transfers zero-shot across related video-understanding tasks.
- Experimental Setup: PTD reduces tube generation to two decoding rounds and uses localization-aware policy optimization to improve temporal boundaries and spatial geometry.The model supports PTD with a Qwen3-VL-4B backbone and is trained with supervised fine-tuning followed by GRPO using temporal and spatial rewards.
- Decoding Efficiency: 79× lower Tube Completion Latency and 92× higher spatial decoding throughput are achieved over unquantized token decoding while improving localization quality.Across the decoding strategies, quantization reduces latency, block decoding further improves efficiency and localization, and PTD achieves the strongest grounding performance.
- Decoding Efficiency: 0.4s Tube Completion Latency and 8× longer tubes increase PTD latency only from 0.33s to 0.40s, while block decoding rises from 0.72s to 6.18s.Token-based and Sequential Block Decoding also scale substantially with tube length.
- Main STVG Results: PTD leads on seven of eight VidSTG metrics, improving previous-best mvIoU by +1.1 points for both declarative and interrogative queries.It also improves previous-best mtIoU by +1.1 and +1.7 points for declarative and interrogative queries, respectively.
- Main STVG Results: On HC-STVG, PTD improves previous-best mvIoU by +1.5 points on v1 and +1.1 points on v2, achieving the best vIoU@0.3 on both benchmarks.Temporal localization remains competitive, while gains are more pronounced for full spatio-temporal tube evaluation.
- Generalization: Zero-shot transfer is strong across temporal grounding, grounded VideoQA, and referring video object tracking, including a +15.6-point mIoU gain on ReXTime over the strongest zero-shot baseline.The model also performs strongly on Charades-STA, ActivityNet, and three referring video object tracking benchmarks without task-specific supervision.
5 Limitations
PTD’s remaining errors arise from ambiguous temporal boundaries, difficult target appearance conditions, and the limited scope of current STVG formulations and training resources.
- Short, visually ambiguous state transitions can make predicted temporal intervals extend beyond or end before the complete event.
- Small, rapidly moving, or occluded targets can make spatial localization imprecise, especially when target identity must be recovered after occlusion.
- Standard STVG benchmarks generally use one continuous temporal interval and one spatial tube, leaving richer multi-segment and multi-instance scenarios largely unexplored.
- Limited dense-tube training data constrains the current study, with VidSTG and HC-STVG-v1/v2 serving as the primary available datasets.
6 Conclusion
The paper introduces PTD to generate a temporal interval followed by spatial blocks in parallel, avoiding autoregressive dense trajectory decoding. Experiments report substantially higher efficiency alongside stronger grounding accuracy and zero-shot transfer across related video tasks.
- PTD removes autoregressive dense spatial trajectory decoding by predicting the temporal interval first and then generating time-conditioned spatial blocks in parallel.
- Two sequential decoding rounds replace tube-length-dependent generation, while Decoupled Block Attention removes cross-box dependencies and preserves shared multimodal evidence.
- On VidSTG, PTD reduces Tube Completion Latency by 79× and increases spatial decoding throughput by 92× relative to standard autoregressive decoding while achieving stronger grounding accuracy.
- With a 4B backbone, the model performs favorably on VidSTG and HC-STVG and transfers zero-shot to temporal grounding, grounded VideoQA, and referring video object tracking.