Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding

Hanoona Rasheed; Haania Siddiqui; Ming-Hsuan Yang; Fahad Shahbaz Khan; Salman Khan

cs.CVAug 28, 2026

Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding

Authors: Hanoona Rasheed, Haania Siddiqui, Ming-Hsuan Yang, Fahad Shahbaz Khan, Salman Khan

Organizations: Mohamed bin Zayed University of Artificial Intelligence · University of California, Merced · Apertix

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.

Figures & tables

Figure 1: Autoregressive localization vs. Parallel Tube Decoding. Given a video and a referring expression, STVG predicts when the event occurs and the bounding box of the referred entity throughout that interval. We compare four decoding paradigms. Unquantized Token Decoding generates textual localization values autoregressively, while Quantized Token Decoding reduces representation overhead with discrete temporal and spatial tokens. Sequential Block Decoding further removes within-block dependencies but remains sequential across the tube. In contrast, our Parallel Tube Decoding (PTD) generates all time-conditioned spatial blocks in parallel after temporal localization, reducing the sequential decoding depth to $1+1$ . Compared with standard Unquantized Token Decoding, PTD achieves $79\times$ lower Tube Completion Latency and $92\times$ higher spatial decoding throughput, measured as Boxes Per Second (BPS), while simultaneously improving spatio-temporal grounding accuracy.

Figure 2: Qualitative comparison with prior STVG methods. We compare our model with competitive STVG methods on challenging grounding examples. Like many existing approaches, STVG-R1 [ Zhang et al., 2026 ] and DEViL [ Gao et al., 2025 ] use the MLLM for temporal localization but construct the spatial tube using external detection or tracking modules. In contrast, PTD directly generates both the temporal interval and complete spatial tube, producing more accurate temporal boundaries and spatial localization. The examples highlight fine-grained target identification among visually similar distractors, large changes in object scale as the target approaches the camera, and event-specific temporal localization rather than simply predicting the full period in which the target is visible. Bounding boxes show spatial predictions, while the horizontal lines indicate the predicted temporal intervals.

Figure 3: Illustration of Decoupled Block Attention in PTD. Each spatial block attends to the shared multimodal prefix and temporal block, uses bidirectional attention within the block, and remains isolated from other spatial blocks, enabling parallel tube generation.

	Declarative				Interrogative				Efficiency
Model Design	$m_{\mathrm{tIoU}}$	$\mathrm{vIoU}$			$m_{\mathrm{tIoU}}$	$\mathrm{vIoU}$			TCL (s)	BPS
		Mean	$@0.3$	$@0.5$		Mean	$@0.3$	$@0.5$	$\downarrow$	$\uparrow$
Unquantized Token Decoding	42.8	27.4	39.8	27.1	40.8	22.6	32.0	20.9	31.6	0.5
Quantized Token Decoding	43.3	28.7	40.6	27.3	42.0	23.0	32.2	21.2	9.1	1.5
Sequential Block Decoding	47.2	31.2	42.8	28.7	46.3	26.0	35.5	22.5	1.0	8.8
Parallel Tube Decoding (PTD)	47.5	32.9	46.0	30.5	46.7	27.2	37.8	23.3	0.4	45.9

Table 1: We report spatio-temporal grounding performance for declarative and interrogative queries, together with decoding efficiency measured by tube completion latency (TCL) and boxes per second (BPS). Quantization reduces decoding cost, sequential block prediction further improves efficiency, and the proposed Parallel Tube Decoding (PTD) achieves the strongest grounding performance while substantially reducing TCL and increasing BPS.

Figure 4: Analysis of decoding efficiency and trajectory-level dependency. (a) Tube completion latency as the number of grounded frames increases. PTD maintains nearly constant latency, while token-based and block decoding scale with tube length. (b) Attention distribution across tube decoding for Sequential Block Decoding (dotted) and PTD (solid). Sequential decoding progressively shifts attention from the video toward prior text. (c) History-correction analysis for Sequential Block Decoding. Replacing an erroneous box $B_{i}$ with its ground-truth box improves subsequent predictions, with the effect gradually decreasing as the decoding distance $j-i$ increases.

		Declarative Sentences				Interrogative Sentences
Model	Scale	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$
Backbone Baselines
Qwen2.5-VL-7B (ZS) [ Bai et al., 2025b ]	7B	16.8	10.9	14.3	5.4	13.8	8.5	11.3	4.4
Qwen2.5-VL-7B + SFT † [ Gu et al., 2025b ]	7B	41.6	20.3	26.1	15.4	40.9	17.1	17.6	13.9
Qwen3-VL-4B (ZS) [ Bai et al., 2025a ]	4B	36.2	13.1	16.6	7.0	36.1	8.9	10.2	3.8
Qwen3-VL-8B (ZS) [ Bai et al., 2025a ]	8B	37.0	13.4	16.5	7.1	35.0	9.3	11.0	3.9

Table 2: Comparison with prior work on VidSTG under declarative and interrogative settings. We report the model scale, mean temporal IoU (

m_{\mathrm{tIoU}}

), mean video IoU (

m_{\mathrm{vIoU}}

), and

\mathrm{vIoU}

at 0.3 and 0.5 thresholds. † denotes the Qwen2.5-VL SFT baseline reported in STVG-o1 [ Gu et al., 2025b ] , while ‡ denotes the Qwen3-VL SFT baseline reported in DEViL [ Gao et al., 2025 ] . Our results use Qwen3-VL-4B as the backbone. SFT (NTP) uses supervised fine-tuning with standard next-token autoregressive decoding, whereas SFT (PTD) uses the same supervised training objective with Parallel Tube Decoding at inference. GRPO (PTD) further optimizes the model with GRPO while retaining Parallel Tube Decoding.

		HC-STVG v1				HC-STVG v2
Model	Scale	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$
Backbone Baselines
Qwen2.5-VL-7B (ZS) [ Bai et al., 2025b ]	7B	25.6	19.1	20.2	12.6	22.9	13.0	15.6	6.4
Qwen2.5-VL-7B (SFT † ) [ Gu et al., 2025b ]	7B	53.5	28.6	45.2	21.9	55.3	26.5	38.6	20.2
Qwen3-VL-4B (ZS) [ Bai et al., 2025a ]	4B	44.6	19.5	25.4	4.9	45.2	19.4	24.7	5.5
Qwen3-VL-8B (ZS) [ Bai et al., 2025a ]	8B	47.6	21.5	30.3	6.5	53.1	21.9	30.0	6.6

Table 3: Comparison with prior work on HC-STVG v1 and HC-STVG v2 . We report the model scale, mean temporal IoU (

m_{\mathrm{tIoU}}

), mean video IoU (

m_{\mathrm{vIoU}}

), and

\mathrm{vIoU}

at thresholds 0.3 and 0.5. † denotes the Qwen2.5-VL SFT baseline reported in STVG-o1. Our models use Qwen3-VL-4B as the backbone. SFT (NTP) uses standard next-token prediction, while SFT (PTD) uses Parallel Tube Decoding. GRPO (PTD) further optimizes the PTD model with GRPO.

Table 8

Table 9

	Declarative Sentences				Interrogative Sentences
Reward	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$	$m_{\mathrm{tIoU}}$	$m_{\mathrm{vIoU}}$	$\mathrm{vIoU}@0.3$	$\mathrm{vIoU}@0.5$
SFT	50.0	34.9	48.5	33.3	48.2	28.7	40.2	25.6
Temporal	53.8	37.4	51.9	36.4	52.1	31.1	43.3	28.0
Spatial	51.8	37.2	51.6	35.9	49.9	31.3	43.2	29.2
Temporal + Spatial	53.7	38.3	53.0	37.5	52.2	32.4	44.9	30.3

Table 8: Ablation of the reward design for GRPO on VidSTG . We compare temporal-only, spatial-only, and the full temporal-spatial reward under declarative and interrogative settings. All variants use Qwen3-VL-4B with Parallel Tube Decoding.

Figure 5: Representative failure cases. Temporally subtle state changes can produce ambiguous event boundaries (top), while spatial localization becomes difficult for small, rapidly moving, or occluded targets (bottom). Green and blue denote the ground-truth and PTD predictions, respectively; the horizontal lines indicate their temporal intervals.

Temporal Video Grounding

Temporal video grounding locates the moments in a video that match a natural-language query, enabling precise search and evidence-based understanding.

See all 159 papers

Bridging Time and Space: Decoupled Spatio-Temporal Alignment for Video Grounding
Apr 9, 2026Xuezhen Tu, Jingyu Wu, Fangyu Kang +4Vision-Language Grounding Temporal Video Grounding
Shanghai Jiao Tong University China · ZTE Corporation China
Pocket-STVG: lightweight architecture for Spatio-Temporal Video Grounding
Sep 25, 2026Alberto Presta, Michal Byra, Grzegorz Stefański +3Temporal Video Grounding Vision-Language Grounding
Samsung AI Center, Warsaw, Poland · IFTR, Polish Academy of Sciences, Warsaw, Poland
GroundVTS: Visual Token Sampling in Multimodal Large Language Models for Video Temporal Grounding
Apr 2, 2026Rong Fan, Kaiyan Xiao, Minghao Zhu +3Temporal Video Grounding Video-Language Models
Newcapec AI Research · Fudan University · Tongji University

Apr 9, 2026J/K move · Enter open · S save

Bridging Time and Space: Decoupled Spatio-Temporal Alignment for Video Grounding

Xuezhen Tu, Jingyu Wu, Fangyu Kang, Qingpeng Nong+3

Shanghai Jiao Tong University China · ZTE Corporation China

Vision-Language Grounding Temporal Video Grounding Unified Multimodal Models

Open paper AskPDF arXiv

Spatio-Temporal Video Grounding requires jointly localizing target objects across both temporal and spatial dimensions based on natural language queries, posing fundamental challenges for existing Multimodal Large Language Models (MLLMs). We identify two core challenges: entangled spatio-temporal alignment, arising from coupling two heterogeneous sub-tasks within the same autoregressive output space, and dual-domain visual token redundancy, where target objects exhibit simultaneous temporal and spatial sparsity, rendering the overwhelming majority of visual tokens irrelevant to the grounding query. To address these, we propose Bridge-STG, an end-to-end framework that decouples temporal and spatial localization while maintaining semantic coherence. While decoupling is the natural solution to this entanglement, it risks creating a semantic gap between the temporal MLLM and the spatial decoder. Bridge-STG resolves this through two pivotal designs: the Spatio-Temporal Semantic Bridging (STSB) mechanism with Explicit Temporal Alignment (ETA) distills the MLLM's temporal reasoning context into enriched bridging queries as a robust semantic interface; and the Query-Guided Spatial Localization (QGSL) module leverages these queries to drive a purpose-built spatial decoder with multi-layer interactive queries and positive/negative frame sampling, jointly eliminating dual-domain visual token redundancy. Extensive experiments across multiple benchmarks demonstrate that Bridge-STG achieves state-of-the-art performance among MLLM-based methods. Bridge-STG improves average m_vIoU from

26.4

34.3

on VidSTG and demonstrates strong cross-task transfer across various fine-grained video understanding tasks under a unified multi-task training regime.

Abstract

Temporal Video Grounding

Explore similar work

Bridging Time and Space: Decoupled Spatio-Temporal Alignment for Video Grounding

Pocket-STVG: lightweight architecture for Spatio-Temporal Video Grounding

GroundVTS: Visual Token Sampling in Multimodal Large Language Models for Video Temporal Grounding