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

AI summary

Overview

Research area: Computer vision — specifically spatio-temporal video grounding (STVG) with multimodal large language models (MLLMs).

Technical level: Intermediate. Readers should be comfortable with autoregressive decoding, bounding-box IoU metrics, and standard MLLM training pipelines (supervised fine-tuning and policy optimization with GRPO).

Scope: The paper proposes Parallel Tube Decoding (PTD), a generative formulation that decodes an entire spatio-temporal grounding tube in two rounds (one temporal, one spatial) instead of one round per box, and reports its accuracy and inference-efficiency effects on VidSTG and HC-STVG.

What This Paper Is About

Spatio-temporal video grounding asks a model to identify when an event described by a natural-language query happens and where the referred entity is located throughout that interval as a sequence of bounding boxes (a "tube"). Existing MLLM approaches write this tube out one box at a time, so decoding latency grows with the number of boxes and an early localization error can propagate forward along the trajectory. The paper's goal is to remove both the token-level and trajectory-level dependencies so the whole tube can be generated in a fixed number of decoding rounds without sacrificing — and while improving — grounding accuracy.

Key Contributions

1. A new decoding formulation (Parallel Tube Decoding, PTD). The paper analyzes four decoding strategies for generative STVG and shows that PTD reduces tube generation from 4+7T rounds under Quantized Token Decoding and 1+T rounds under Sequential Block Decoding to just two rounds (1+1), independent of the number of boxes.
2. Decoupled Block Attention. An attention mechanism that lets each time-conditioned spatial block attend to the shared multimodal prefix (video, referring expression, and predicted temporal block) while blocking attention to other spatial blocks, which is what makes parallel spatial generation possible without cross-box dependencies.
3. Localization-aware policy optimization. Group Relative Policy Optimization (GRPO) with complementary rewards — a temporal IoU reward on the predicted interval and a spatial reward combining GIoU with an L1 coordinate penalty on boxes inside the temporal intersection — to directly improve event boundaries and box geometry.
4. Efficiency and generalization results. PTD cuts Tube Completion Latency by 79 times and raises spatial decoding throughput by 92 times over unquantized token decoding, using a compact 4B backbone (Qwen3-VL-4B), and the authors report it generalizes zero-shot to temporal grounding, grounded VideoQA, and referring video object tracking.

Main Findings

• Reducing dependencies improves both speed and accuracy. In the controlled comparison on VidSTG (Table 1), progressing from Unquantized Token Decoding to Quantized Token Decoding to Sequential Block Decoding to PTD steadily improves grounding metrics while lowering latency: mean tIoU on declarative queries rises 42.8 → 43.3 → 47.2 → 47.5, and TCL falls 31.6 s → 9.1 s → 1.0 s → 0.4 s. BPS rises 0.5 → 1.5 → 8.8 → 45.9.
• The headline efficiency numbers. Relative to the Qwen3-VL-4B baseline using Unquantized Token Decoding, PTD reduces Tube Completion Latency by 79 times and increases spatial decoding throughput (Boxes Per Second) by 92 times, while also improving spatio-temporal grounding.
• Latency becomes nearly independent of tube length. Varying the number of boxes from 8 to 64, PTD's latency grows only from 0.33 s to 0.40 s as tube length grows by 8 times, whereas Sequential Block Decoding rises from 0.72 s to 6.18 s over the same range.
• Cross-box error propagation is real and measurable. A history-correction intervention that replaces 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. Attention analysis shows Sequential Block Decoding progressively shifts attention from the video toward its own generated localization history, whereas PTD maintains video attention.
• PTD improves accuracy even under identical supervised training. Comparing SFT (NTP) against SFT (PTD) on VidSTG, the declarative mean tIoU rises from 46.3 to 50.0 and mean vIoU from 31.6 to 34.9; interrogative mean tIoU rises from 44.7 to 48.2 and mean vIoU from 26.3 to 28.7. GRPO (PTD) further raises these to 53.7 / 38.3 (declarative) and 52.2 / 32.4 (interrogative).
• Strong results with a small backbone. With a 4B model, GRPO (PTD) reaches declarative VidSTG m_tIoU 53.7, m_vIoU 38.3, vIoU@0.3 53.0, vIoU@0.5 37.5, and interrogative m_tIoU 52.2, m_vIoU 32.4, vIoU@0.3 44.9, vIoU@0.5 30.3 — exceeding several 7B prior methods such as LLaVA-ST, SpaceVLLM-7B, and DEViL on these measures.
• Results on HC-STVG. GRPO (PTD) reports HC-STVG v1 m_tIoU 59.4, m_vIoU 45.6, vIoU@0.3 73.8, vIoU@0.5 46.7, and HC-STVG v2 m_tIoU 63.1, m_vIoU 43.6, vIoU@0.3 71.0, vIoU@0.5 42.2. On HC-STVG v2 mean tIoU, prior Bridge-STG (Qwen3-VL-7B) reports 64.1 and STVG-o1 reports 63.8, so the 4B PTD model is competitive rather than ahead on that metric.
• Zero-shot generalization. The authors state the model generalizes zero-shot to temporal grounding, grounded VideoQA, and referring video object tracking; the specific numbers for those settings are not included in the provided paper content.

Methodology in Plain English

The model is built on a Qwen3-VL-4B backbone. The vocabulary is extended with 1,001 spatial tokens representing normalized coordinates in [0, 1000] and 100 temporal tokens representing discretized timestamps; the new localization tokens are initialized from semantically aligned Qwen3-VL vocabulary embeddings. Temporal tokens are interleaved with the video representation (temporal patch size 1), so each temporal patch carries an explicit anchor token.

Generation happens in two stages. First the model predicts the temporal block (start and end). Then, instead of decoding boxes one after another, the model instantiates all the anchor tokens for the localized interval at once and predicts every corresponding spatial block in parallel. Each spatial block takes the anchor token plus five mask tokens as input and jointly predicts the box, four coordinate tokens, and the closing tag.

To train this without breaking the model's ordinary autoregressive behavior, each training sample is supervised with two target sequences in a single forward pass: a next-token-prediction (NTP) sequence using standard causal attention, and a multi-token-prediction (MTP) sequence where blocks use bidirectional attention internally. Decoupled Block Attention governs the MTP side: each spatial block sees the shared prefix and temporal block but not other spatial blocks. The NTP sequence cannot attend to the MTP blocks, preventing information leakage.

Training is two-stage: supervised fine-tuning with the combined NTP/MTP loss, then GRPO with the temporal and spatial localization rewards, equally weighted. Both stages use LoRA with rank 32, optimizing the LoRA parameters together with the new token embeddings. Hyperparameters: SFT learning rate 2e-5, GRPO learning rate 5e-6, beta = 0.04, sampling temperature 0.9, videos sampled at 2 FPS with at most 64 frames. For the controlled decoding comparison, all four variants are trained for 1 SFT epoch; the main PTD model is trained for 2 epochs.

Training data combines the VidSTG and HC-STVG training splits (VidSTG has declarative and interrogative expressions; HC-STVG-v1 and v2 add human-centric samples), yielding approximately 90K SFT samples. For GRPO, the authors build a 16K subset chosen for within-group variation: the SFT model generates eight candidate responses per sample, scored by tIoU and vIoU, and samples with meaningful variation are preferentially retained.

Efficiency is measured with two metrics: Tube Completion Latency (TCL = T_full − T_TTFT, excluding prefill) and Boxes Per Second (BPS = T / TCL). All efficiency evaluations use batch size 1 and BF16 inference on a single 64-GB AMD Instinct MI210 GPU with PyTorch 2.7 and ROCm 6.3.

Why This Matters

Impact on research. The paper reframes STVG as a problem where sequential decoding depth is a design choice rather than a necessity. It shows that the trajectory-level dependency across boxes is not required by the task — the correct box at a time step depends on the query and the visual content at that step — and that removing it improves accuracy, not just speed. It also provides a controlled comparison of four decoding paradigms and a measurable error-propagation analysis, which gives future work a concrete baseline to build on.

Real-world applications:

• Long-video search, where users describe an event and need both the moment it occurs and the location of the subject throughout it.
• Evidence-grounded question answering, where answers must be tied to specific regions across time.
• Language-guided tracking of a described subject through a video.
• Embodied interaction and robotics, where a system must act on a referred entity located in space and time and cannot afford long generation delays.

Industry relevance. The work targets inference cost directly, which matters for deployment: a compact 4B backbone with near-constant tube latency is cheaper to serve than a 7B model producing long serialized coordinate sequences. The 92 times throughput gain and the fact that longer tubes only increase parallel decoding width — not sequential depth — map onto the batching and latency constraints of production video pipelines.

Future Directions

• Whether the two-round decomposition extends to other dense structured outputs that are currently serialized, such as multi-object tubes or longer temporal hierarchies.
• How PTD behaves at video lengths and tube counts beyond those tested; the latency scaling study covers 8 to 64 boxes and the model samples videos at 2 FPS with at most 64 frames.
• Whether the 16K GRPO subset selection criterion (retaining samples with within-group rollout variation) transfers to other grounding tasks and reward designs.
• How the approach compares against the decoupled architectures it outperforms on some metrics — for example, whether PTD can be combined with external detectors or trackers rather than replacing them.
• Extending the zero-shot generalization claims with detailed per-benchmark numbers for temporal grounding, grounded VideoQA, and referring video object tracking, which are referenced as Section 4.4 but not included in the provided content.

Target Audience

Researchers and engineers working on video-language models, video grounding, and efficient multimodal inference. It is most useful to those designing MLLM output representations and decoding schemes, and to practitioners who need accurate spatio-temporal localization at production latency. Readers without background in generative video grounding will need to consult the referenced prior work (VidSTG, HC-STVG, STVG-o1, DEViL, SpaceVLLM, Bridge-STG) to place the comparisons in context.

Authors’ 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.