Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding
Abstract Overview
This paper studies spatio-temporal video grounding (STVG) in multimodal large language models, targeting the inefficiency of autoregressively generating dense bounding-box trajectories across time. The authors propose Parallel Tube Decoding (PTD), which first predicts the temporal interval of the queried event and then decodes all time-conditioned spatial boxes simultaneously in parallel, reducing the sequential decoding depth to two rounds regardless of tube length. To support parallel box prediction without cross-box autoregressive interference, they introduce Decoupled Block Attention alongside localization-aware policy optimization using temporal and spatial rewards. Evaluations on VidSTG and HC-STVG show substantial improvements in both generation speed and grounding accuracy, with the learned localization transferring zero-shot to temporal grounding, grounded VideoQA, and referring video object tracking.
Novelty
The primary novelty is Parallel Tube Decoding, a generative STVG decoding paradigm that eliminates both token-level and trajectory-level autoregressive dependencies by decomposing generation into a temporal block followed by parallel time-conditioned spatial blocks. The method also introduces Decoupled Block Attention to isolate spatial box blocks from each other while maintaining shared multimodal context, supported by a localization-aware policy optimization objective.
Results
On VidSTG, PTD reduces Tube Completion Latency by 79× and raises spatial decoding throughput by 92× compared to standard unquantized autoregressive decoding while maintaining nearly constant latency as tube length scales. Built on a 4B backbone without external spatial decoders or tracking modules, the model achieves state-of-the-art or competitive grounding accuracy on VidSTG and HC-STVG. It also generalizes zero-shot to temporal grounding on Charades-STA and ActivityNet, grounded VideoQA on ReXTime, and video object tracking across Ref-DAVIS, Ref-YT-VOS, and ReasonVOS.
Key Points
- Parallel Tube Decoding reformulates STVG generation into temporal localization followed by parallel decoding of all spatial boxes, fixing the sequential decoding depth to two rounds independent of trajectory length.
- Decoupled Block Attention eliminates inter-box dependencies and prevents error propagation along the trajectory while preserving shared multimodal context for each temporal anchor.
- The 4B model substantially accelerates inference throughput and improves grounding accuracy over sequential baselines, demonstrating strong zero-shot transfer to temporal grounding, grounded VideoQA, and video object tracking.