Locate Anything in Videos: Rethinking Efficient Generative Spatio-Temporal Video Grounding
Hanoona Rasheed, Haania Siddiqui, Ming-Hsuan Yang, Fahad Shahbaz Khan, Salman Khan
cs.CV
2026-08-28
PTD times the event, then emits all boxes in parallel. VidSTG tube latency drops 79x and box throughput rises 92x vs AR decoding; a 4B model beats most 7B pipelines.
Spatio-temporal video grounding asks for two outputs at once: the time span of a referred event, and a box on the target at every step inside that span. If a multimodal LLM serializes the whole tube as text, decode depth grows with the number of boxes, and an early coordinate error travels forward in time. Strong systems often keep the LLM for semantics and timing, then hand spatial work to a detection head, an external detector, or a tracker. The unified token interface survives. The latency and the error cascade survive with it.
That cascade is not required by the task. The right box at a time step is fixed by the query and the pixels at that step, not by boxes already emitted. A history-correction test makes the dependency visible: swap one wrong sequential-block box for ground truth, and nearby future boxes improve immediately. The lift fades as decode distance grows.
Parallel Tube Decoding (PTD) splits generation into two fixed rounds. Round one emits a temporal block (start and end). Round two instantiates a time token for each step in that interval and decodes every spatial block together. Sequential depth is 1+1, independent of tube length. Longer tubes widen the parallel fan-out; they do not add rounds.
Four decoding rungs are compared. Unquantized text coordinates. Quantized discrete tokens at depth 4+7T. Sequential block decoding, one box per block, at depth 1+T. PTD then drops the remaining cross-box dependency.
Decoupled Block Attention makes the last step legal: each spatial block may read the shared video-query prefix and the temporal block, attends bidirectionally inside itself, and cannot see any other spatial block. Training keeps a next-token target and a multi-token target on the same sample so parallel decoding does not erase ordinary autoregression.
After SFT, GRPO uses two equal rewards. Temporal: tIoU of the predicted interval. Spatial: GIoU minus L1 on the temporal overlap, which penalizes shifted, loose, and drifting boxes. The backbone is Qwen3-VL-4B with 1,001 spatial tokens and 100 temporal tokens. SFT trains on about 90K VidSTG plus HC-STVG clips. GRPO keeps a 16K subset where rollouts disagree, so the relative signal is actually there.
Timing is decode-only on one MI210 at batch 1, after time-to-first-token.
| decoder | TCL (s) | BPS | declarative mtIoU / vIoU |
| unquantized AR | 31.6 | 0.5 | 42.8 / 27.4 |
| quantized tokens | 9.1 | 1.5 | 43.3 / 28.7 |
| sequential blocks | 1.0 | 8.8 | 47.2 / 31.2 |
| PTD | 0.4 | 45.9 | 47.5 / 32.9 |
Versus unquantized decoding, tube completion is about 79 times faster and box throughput about 92 times higher. Stretching the tube from 8 to 64 boxes moves PTD from 0.33s to 0.40s; sequential blocks move from 0.72s to 6.18s.
After full training, GRPO (PTD) reaches 53.7 mtIoU and 38.3 mvIoU on VidSTG declarative queries, above 7B Bridge-STG at 52.6 / 37.2. Interrogative mtIoU is 52.2 versus 50.1; [email protected] is 30.3 versus 31.2, so that cell is a loss. On HC-STVG v1, mvIoU is 45.6 versus STVG-o1 at 44.1, while temporal mtIoU trails 59.4 to 60.3. The paper's own count is seven of eight headline metrics.
Zero-shot transfer is the cleaner test of whether the habit generalizes. Charades-STA mIoU is 52.4 against DEViL at 47.7. ActivityNet is 44.6 against VideoChat-R1.5 at 35.5. On ReXTime, evidence mIoU is 47.8 against VideoTG-R1 at 32.2, while answer accuracy is 73.1 against 75.7. With SAM2, Ref-DAVIS J&F is 81.9, above finetuned Molmo2-4B at 73.5.
Dense video localization does not have to be a serial coordinate stream. A native generative interface can stay native. A 4B model with no extra spatial module sits in the 7B pipeline band. Latency barely moves as the tube grows, which is the regime that matters for long-video search and online grounding. The zero-shot jumps into temporal grounding, evidence VideoQA, and referring tracking say the model learned a transferable localization habit, not two dataset skins.
If the goal is to keep coordinates inside an MLLM, removing cross-box causal attention is a cheaper first move than bolting on another decoder.
The paper's own failure cases are occlusion-after-reappearance, small fast targets, and short visually ambiguous state changes that clip or over-extend the interval. Standard STVG labels one continuous span and one tube, so disjoint repeats, camera-driven disappearances, and multiple instances of the same phrase are out of scope. Dense tube data is still mostly VidSTG and HC-STVG. The 79 times figure is an MI210 number; it is not a CUDA constant. Tracking still needs SAM2 or SAM3 for masks. Interrogative [email protected] does not beat Bridge-STG, so tight spatial overlap still has a hole.