Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding
Computer Vision and Pattern Recognition
Summary
The authors study how to find and track objects in videos based on a description of events happening over time. They point out that existing methods decode the object's location step-by-step, which slows down the process and causes errors to build up. They propose a new approach called Parallel Tube Decoding that breaks the problem into a time part and many space parts, which it solves all at once, making the decoding much faster and more accurate. Their method uses special attention mechanisms to keep important video and query information available while avoiding dependencies between object locations. Tests show their approach is faster and works well on different video grounding tasks.
Authors
Hanoona Rasheed, Haania Siddiqui, Ming-Hsuan Yang, Fahad Shahbaz Khan, Salman Khan
Abstract
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.