acceptodds
Under review as a conference paper at ICLR 2027

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

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 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 and increases spatial decoding throughput by 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.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Spatio-Temporal Video Grounding, Video-Language Models, Parallel Decoding, Multimodal Large Language Models, Video Grounding, Structured Generation, Reinforcement Learning, Efficient Inference

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SgS9OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The paper proposes Parallel Tube Decoding (PTD) for MLLM-based spatio-temporal video grounding on Qwen3-VL-4B. After predicting the temporal interval as one block, it creates a frame anchor for every frame in that interval and fills all per-frame box blocks in a single forward pass. Decoupled Block Attention (DBA) lets each block see the video-query prefix but no other block. Training combines LocateAnything’s dual NTP/MTP formulation with GRPO using tIoU and GIoU − L1 rewards.

Critical strengths

S1. Decoding latency is independent of tube length, with no accuracy loss. From Fig. 2a, PTD stays at about 0.33–0.40 s from 8 to 64 frames, while Sequential Block Decoding (SBD) grows from about 0.7 s to 6.2 s. In Table 1, PTD exceeds SBD on all eight grounding metrics. This makes dense tube output practical inside a unified MLLM, and it is the paper’s most consequential result.

S2. SOTA-level results with a small, unified model. With a 4B backbone and no external detector or spatial decoder, the full model reaches VidSTG mvIoU of 38.3/32.4 (Bridge-STG: 37.2/31.3) and gains +1.5/+1.1 mvIoU on HC-STVG v1/v2. It also transfers zero-shot to temporal grounding, ReXTime, and referring VOS.

Critical weaknesses

W1. The new component is narrow, and the paper credits it with more than it does.

  • Most components are prior work:
    • quantized localization tokens (Pix2Seq, PaliGemma);
    • box-as-one-block decoding with dual NTP/MTP training (LocateAnything, arXiv:2605.27365);
    • BPS (reported by LocateAnything, uncredited in Sec. 2.3);
    • GRPO with localization rewards for STVG (STVG-o1, STVG-R1; acknowledged in Sec. 2.4).
  • Three of the four strategies in Contribution 1 are therefore not new. What is new is removing cross-block attention and creating frame anchors from the predicted interval. Predicting per-frame boxes in parallel is itself the standard non-MLLM STVG design, e.g., TubeDETR’s one time query per frame.
  • Single-round decoding does not require DBA, yet the paper credits it. Sec. 2.2 attributes one-round decoding to DBA replacing SBD’s “causal attention across blocks.” But one round follows from every block’s input (anchor plus <mask> tokens) being known in advance. Bidirectional or causal attention across blocks over the same inputs would also finish in 1 + 1 rounds. The paper’s own within-block design shows this: six tokens are predicted jointly in one round from an anchor and five masks. Full independence between blocks is a design choice, and it is never compared against cross-block attention.
  • Most of the 79× speedup comes from prior steps. It decomposes exactly from Table 1:
    • 31.6 → 9.1 s (3.5×, quantization);
    • 9.1 → 1.0 s (9.1×, block decoding);
    • 1.0 → 0.4 s (2.5×, PTD).
    • PTD’s own share is 2.5×, measured on decoding alone, since TCL excludes prefill (Sec. 2.3).
  • Why consequential: the abstract and Contributions 1–3 credit PTD with gains that come largely from LocateAnything and GRPO. The new delta has to stand on its own evidence, and W2 shows it does not yet.

W2. The claim that removing cross-box dependency improves accuracy is not isolated.

  • The only test of DBA changes two things at once. Table 1’s SBD vs. PTD comparison (1 SFT epoch, single run) shows +1.7/+1.2 mvIoU and +0.3/+0.4 mtIoU. Per App. D.3, SBD predicts <t_i> itself inside 7-token blocks, while PTD receives anchors for every frame of the predicted interval. SBD is therefore not “the natural ablation of Decoupled Block Attention” (Sec. 3.2). The variants also emit 14.2 vs. 17.7 boxes on average (Sec. 3.2) at nearly identical mtIoU (47.2 vs. 47.5). If SBD skips frames inside its own interval, part of the vIoU gap reflects box coverage, not box quality.
  • Fig. 2c shows dependence on history, not net harm. Correcting a mislocalized box improves later boxes (as we read it, by about 0.37 IoU at distance 1 and 0.27 at distance 12). That shows correct history helps. It never compares SBD with PTD on the same boxes.
  • SOTA depends on GRPO, which is applied only to PTD. Without GRPO, SFT(PTD) trails prior work on mvIoU on every benchmark:
    • VidSTG: 34.9/28.7 vs. Bridge-STG 37.2/31.3;
    • HC-STVG v1: 42.7 vs. STVG-o1 44.1;
    • HC-STVG v2: 39.2 vs. DEViL 42.5.
    • GRPO trains on the model’s own outputs, which is the standard remedy for exposure bias, so it may close the PTD–SBD gap. No GRPO run of SBD is reported.
  • Why consequential: the paper claims “faster and more accurate.” The speed is established; accuracy from decoupling is not.
Questions for authors

Experiments needed:

  • Please report SBD with anchors given (6-token blocks, attending to previously predicted boxes) and a cross-block bidirectional variant (still 1 + 1 rounds). Do PTD’s gains hold against both? Does SBD emit a box for every frame of its predicted interval?
  • Does PTD’s advantage survive when GRPO is also applied to SBD, even at reduced scale?

Clarifications:

  • Table 1’s BPS does not match BPS = T/TCL computed from the Sec. 3.2 means: SBD gives 14.2/1.0 = 14.2 (8.8 reported), and Unquantized gives 12.3/31.6 = 0.39 (0.5 reported). Is BPS averaged per sample? Please also report end-to-end latency including prefill.
  • HC-STVG-v2 test labels are not public. Is the 1,901-query split the validation set? Since v1 and v2 training data are combined and v2 extends v1, please confirm that no v1 test videos appear in v2 training.

Minor (no response needed):

  • NTP is never defined.
  • Sec. 3.2 says the variants differ only at inference, but App. D.3 shows different training formulations.
  • The App. F prompts request “object reference tokens,” which are absent from Eq. 1.
9 comments
AuthorsOpenReview ↗

Response to Reviewer SgS9 (1/4)

1. SBD with given frame anchors and box coverage

The only test of DBA changes two things at once. Table 1's SBD vs. PTD comparison (1 SFT epoch, single run) shows +1.7/+1.2 mvIoU and +0.3/+0.4 mtIoU. Per App. D.3, SBD predicts <t_i> itself inside 7-token blocks, while PTD receives anchors for every frame of the predicted interval. SBD is therefore not "the natural ablation of Decoupled Block Attention" (Sec. 3.2). The variants also emit 14.2 vs. 17.7 boxes on average (Sec. 3.2) at nearly identical mtIoU (47.2 vs. 47.5). If SBD skips frames inside its own interval, part of the vIoU gap reflects box coverage, not box quality.

Please report SBD with anchors given (6-token blocks, attending to previously predicted boxes) and a cross-block bidirectional variant (still 1 + 1 rounds). Do PTD's gains hold against both? Does SBD emit a box for every frame of its predicted interval?

(a) SBD with given anchors (6-token blocks, causal across boxes).

Through Table 1, our intention was to present a progressive study of four decoding strategies for generative STVG. Following the MTP formulation in images, we first formulate Sequential Block Decoding (SBD) as a direct extension to video, where each time-indexed box is predicted as a block. We then extend this formulation to PTD, where temporal anchors are constructed from the predicted interval to enable parallel spatial decoding (temporal anchoring is part of the proposed PTD design).

To address the concern and ablate the effect of temporal anchoring separately from Decoupled Block Attention (DBA), we additionally train an anchored SBD variant. Similar to PTD, it first predicts the temporal interval and uses it to construct the frame indices for each spatial block, while retaining sequential decoding. On VidSTG, PTD still achieves a 1.6–1.9 point improvement in mvIoU over anchored SBD, showing that temporal anchoring alone does not close the gap with PTD. The remaining improvement is not explained solely by box coverage, but instead reflects improved spatial localization quality.

Table R7. SBD with given anchors vs. PTD on VidSTG (all: 1 SFT epoch).

VariantDecl. mvIoUDecl. @0.3Decl. @0.5Decl. mtIoUInter. mvIoUInter. @0.3Inter. @0.5Inter. mtIoU
SBD31.242.828.747.226.035.522.546.3
SBD + given anchors31.343.729.047.825.335.022.046.4
PTD (DBA)32.946.030.547.527.237.823.346.7

(b) Does SBD emit a box for every frame of its predicted interval?

We analyze all VidSTG predictions and find that SBD covers every frame of its predicted interval in 98.4% of queries, while PTD ensures full coverage by design. The mean predicted interval lengths (14.2 vs. 17.7 frames) indicate that the difference in box counts primarily reflects temporal extent rather than skipped frames. Moreover, on frames where both methods predict boxes, PTD achieves higher spatial IoU (56.2 vs. 52.0) and retains a 1.6–1.9 point mvIoU advantage over anchored SBD under the same temporal anchoring procedure.


2. SOTA depends on GRPO, applied only to PTD

SOTA depends on GRPO, which is applied only to PTD. Without GRPO, SFT(PTD) trails prior work on mvIoU on every benchmark:

  • VidSTG: 34.9/28.7 vs. Bridge-STG 37.2/31.3;
  • HC-STVG v1: 42.7 vs. STVG-o1 44.1;
  • HC-STVG v2: 39.2 vs. DEViL 42.5.

GRPO trains on the model's own outputs, which is the standard remedy for exposure bias, so it may close the PTD–SBD gap. No GRPO run of SBD is reported.

Does PTD's advantage survive when GRPO is also applied to SBD, even at reduced scale?

To address this concern, we additionally apply GRPO to SBD using the same training setting as PTD (2-epoch SFT + GRPO). As shown in Table R8 below, PTD still outperforms SBD after GRPO, with mvIoU gains of 1.9 points on declarative and 2.2 points on interrogative queries. While our SOTA results benefit from localization-aware policy optimization, applying GRPO to SBD does not close the gap with PTD.

Table R8. GRPO applied to SBD vs. PTD on VidSTG.

VariantDecl. mvIoUDecl. @0.3Decl. @0.5Decl. mtIoUInter. mvIoUInter. @0.3Inter. @0.5Inter. mtIoU
SBD + GRPO36.450.836.352.630.241.129.551.2
PTD + GRPO38.353.037.553.732.444.930.352.2
AuthorsOpenReview ↗

Response to Reviewer SgS9 (2/4)

3. Single-round decoding and cross-block bidirectional attention

Single-round decoding does not require DBA, yet the paper credits it. Sec. 2.2 attributes one-round decoding to DBA replacing SBD's "causal attention across blocks." But one round follows from every block's input (anchor plus <mask> tokens) being known in advance. Bidirectional or causal attention across blocks over the same inputs would also finish in 1 + 1 rounds. The paper's own within-block design shows this: six tokens are predicted jointly in one round from an anchor and five masks. Full independence between blocks is a design choice, and it is never compared against cross-block attention.

To address this concern, we additionally train a variant with bidirectional attention across spatial blocks. Similar to PTD, it uses frame anchors from the predicted interval and six-token spatial blocks, but allows each block to attend to other spatial blocks. Both variants decode in 1+11+1 rounds, allowing us to examine the effect of DBA on grounding accuracy under the same decoding depth. Under the 2-epoch SFT setting, PTD improves mvIoU by +0.6/+0.7+0.6/+0.7 points over the bidirectional variant.

Table R9. Cross-block bidirectional attention vs. PTD on VidSTG (both: 2 SFT epochs).

VariantDecl. mvIoUDecl. @0.3Decl. @0.5Decl. mtIoUInter. mvIoUInter. @0.3Inter. @0.5Inter. mtIoU
Bidirectional blocks34.347.632.549.928.039.524.948.2
PTD (DBA)34.948.533.350.028.740.225.648.2

To further understand this difference, we analyze the attention distribution and the effect of neighboring box predictions on localization quality.

(i) Attention shifts away from video tokens. The bidirectional variant assigns 19.4% of its attention to other spatial blocks, while attending less to video tokens compared to PTD (12.9% vs. 16.7%). However, this additional cross-block attention does not improve grounding accuracy (Table R9), suggesting that attending to other spatial blocks provides little benefit over directly using the video evidence.

(ii) Localization accuracy conditioned on neighboring boxes. We further analyze predictions on the VidSTG test set, categorizing boxes as correctly localized (IoU≥0.5\mathrm{IoU}\geq 0.5) or incorrectly localized (IoU<0.3\mathrm{IoU}<0.3). We group frames by the correctness of neighboring predictions and compare both models on the same frames, averaging the IoU within each query and then across queries. When the preceding box is correct, the bidirectional variant performs similarly to PTD (75.0 vs. 75.3 IoU; 5,260 queries). We observe a similar trend when both adjacent boxes are correct (79.5 vs. 79.2 IoU; 4,087 queries). However, when the preceding box is incorrect, the bidirectional variant performs worse than PTD (29.1 vs. 31.6 IoU; 1,776 queries), and the gap further increases when both adjacent boxes are incorrect (21.3 vs. 26.1 IoU; 826 queries).

These results suggest that cross-block attention provides little additional benefit when neighboring boxes are correctly localized, while the bidirectional variant shows larger localization errors on frames with incorrect neighboring predictions. DBA removes these cross-block dependencies, keeping spatial predictions focused on the shared video evidence rather than other spatial blocks. Further, the independent spatial blocks can be decoded together or in smaller chunks when memory is limited.

AuthorsOpenReview ↗

Response to Reviewer SgS9 (3/4)

4. Novelty and attribution to prior work

Most components are prior work:

  • quantized localization tokens (Pix2Seq, PaliGemma);
  • box-as-one-block decoding with dual NTP/MTP training (LocateAnything, arXiv:2605.27365);
  • BPS (reported by LocateAnything, uncredited in Sec. 2.3);
  • GRPO with localization rewards for STVG (STVG-o1, STVG-R1; acknowledged in Sec. 2.4).

Three of the four strategies in Contribution 1 are therefore not new. What is new is removing cross-block attention and creating frame anchors from the predicted interval. Predicting per-frame boxes in parallel is itself the standard non-MLLM STVG design, e.g., TubeDETR's one time query per frame.

  • We agree that quantized localization tokens, block decoding, dual NTP/MTP training, and localization-aware GRPO build on prior work, as already acknowledged in the paper. Our approach is to systematically study four decoding strategies for generative STVG, progressing from standard autoregressive and quantized token decoding to sequential block decoding, and introducing PTD to remove tube-length-dependent sequential generation.
  • Our key contribution is predicting spatial boxes independently, conditioned on frame anchors constructed from the predicted temporal interval, such that decoding depth does not grow with tube length. In contrast, LocateAnything retains sequential dependencies across box blocks.
  • Importantly, our additional experiments demonstrate that this formulation improves accuracy beyond simply providing temporal anchors. PTD outperforms anchored SBD by +1.6/+1.9+1.6/+1.9 mvIoU on VidSTG, and retains gains of +1.9/+2.2+1.9/+2.2 mvIoU when GRPO is also applied to SBD.
  • While TubeDETR also predicts per-frame boxes in parallel, it relies on a dedicated detection decoder. In contrast, PTD enables parallel tube generation directly through the MLLM's language decoder, without additional prediction heads or external spatial decoders. Our contribution is therefore not parallel box prediction in general, but enabling efficient, accurate, and unified generative tube decoding within an MLLM. We have also credited LocateAnything for the BPS metric in the revised manuscript (§2.3).

5. Attribution of the 79× speedup

Most of the 79× speedup comes from prior steps. It decomposes exactly from Table 1:

  • 31.6 → 9.1 s (3.5×, quantization);
  • 9.1 → 1.0 s (9.1×, block decoding);
  • 1.0 → 0.4 s (2.5×, PTD).

PTD's own share is 2.5×, measured on decoding alone, since TCL excludes prefill (Sec. 2.3).

We agree that the 79× decoding speedup reflects the combined benefits of quantization, block decoding, and PTD. In checking the reviewer’s calculation, we identified an incorrectly reported SBD latency. The verified mean TCL is 1.6 s, giving a 4×4\times decoding speedup for PTD (1.6 s to 0.4 s). We also checked the separately computed per-query BPS and grounding results and confirmed their reported values.

End-to-end latency including video encoding and prefill: To establish the practical benefit, we additionally measured end-to-end latency, including video preprocessing, encoding, and prefill. PTD reduces total latency from 4.3 s to 3.1 s, a 1.4×1.4\times speedup over SBD, increasing to 1.9×1.9\times for longer tubes (33–64 ground-truth frames). The corresponding decoding speedup increases from 2.7×2.7\times (1–8 frames) to 9.1×9.1\times (33–64 frames), as SBD's decoding time grows from 0.99 to 5.11 s while PTD's remains below 0.6 s. We have corrected the SBD latency throughout the manuscript and now explicitly distinguish PTD’s incremental gain from the cumulative 79×79\times speedup.

Table R10. End-to-end inference latency on VidSTG.

DecoderInput processing (s)Decoding (s)End-to-end (s)PTD speedup (all)PTD speedup (33–64 GT frames)
Unquantized NTP2.7431.634.411.0×19.2× (94.4 vs. 4.9 s)
Quantized NTP2.759.111.93.8×7.7× (37.6 vs. 4.9 s)
SBD2.731.64.31.4×1.9× (9.5 vs. 4.9 s)
PTD (ours)2.740.43.1——

Note: Same setting as Table 1 (2 FPS, up to 64 frames, batch size 1, single MI210 GPU).

Reviewer_qebCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes Parallel Tube Decoding (PTD) for locating a described object over an event interval in a video. It predicts the interval first, then all time-conditioned boxes in parallel, using supervised fine-tuning followed by reinforcement learning. Experiments show faster tube decoding on VidSTG and competitive grounding accuracy on VidSTG and HC-STVG. Additional tests cover temporal grounding, grounded video question answering, and referring video segmentation with SAM2/SAM3.

Critical strengths
  1. Faster decoding with better accuracy. With one epoch of supervised training for both methods, PTD improves declarative mean vIoU and reduces tube completion latency (TCL) relative to Sequential Block Decoding. This is a useful improvement for video grounding without an external detector.

  2. Several experiments support the method. Results are competitive on VidSTG and HC-STVG-v1/v2 (Tables 2 and 3). The paper compares NTP and PTD inference using the same SFT checkpoint and tests temporal and spatial rewards separately. These experiments strengthen the evidence beyond decoding speed.

Critical weaknesses
  1. The attention change is not fully isolated. PTD supplies each box block with a frame index derived from its predicted interval; Sequential Block Decoding predicts that index itself (Appendix D.3). Thus, Table 1 varies both the attention mask and block inputs and targets. Figure 2 supports the error-propagation explanation, but a sequential variant with matched frame-index inputs would better establish how much accuracy gain comes from removing cross-box dependencies.

  2. End-to-end efficiency remains unclear. The 79-fold speedup is over Unquantized Token Decoding and measures TCL, explicitly excluding initial video and prompt processing (Section 2.3). The TCL speedup over Sequential Block Decoding is about 2.5-fold. End-to-end inference time and peak GPU memory are not reported, so the complete practical benefit remains uncertain.

Questions for authors
  1. Requested ablation: Does PTD retain its accuracy advantage over a sequential variant that also receives frame indices constructed from the predicted interval, while retaining attention to earlier boxes? This would help isolate the attention change.

  2. Runtime clarification: What is the total inference time for PTD and Sequential Block Decoding under identical video settings, including initial video and prompt processing?

  3. Memory clarification: What is the peak GPU memory for both methods, and how does it change with the number of predicted boxes? This would clarify any memory cost of parallel decoding.

6 comments
AuthorsOpenReview ↗

Response to Reviewer qebC (1/2)

1. Isolating attention from the frame-anchor input change

The attention change is not fully isolated. PTD supplies each box block with a frame index derived from its predicted interval; Sequential Block Decoding predicts that index itself (Appendix D.3). Thus, Table 1 varies both the attention mask and block inputs and targets. Figure 2 supports the error-propagation explanation, but a sequential variant with matched frame-index inputs would better establish how much accuracy gain comes from removing cross-box dependencies.

Requested ablation: Does PTD retain its accuracy advantage over a sequential variant that also receives frame indices constructed from the predicted interval, while retaining attention to earlier boxes? This would help isolate the attention change.

To address this concern, we additionally train an anchored SBD variant. Similar to PTD, it first predicts the temporal interval and uses it to construct frame indices for six-token spatial blocks. The boxes are still decoded sequentially, with attention to earlier predictions. With one SFT epoch for all variants, PTD improves over anchored SBD by 1.6 and 1.9 mvIoU points on declarative and interrogative queries, respectively (Table R5). Temporal anchoring alone therefore does not close the gap with PTD.

Table R5. SBD with given anchors vs. PTD on VidSTG (all: 1 SFT epoch).

VariantDecl. mvIoUDecl. @0.3Decl. @0.5Decl. mtIoUInter. mvIoUInter. @0.3Inter. @0.5Inter. mtIoU
SBD31.242.828.747.226.035.522.546.3
SBD + given anchors31.343.729.047.825.335.022.046.4
PTD (DBA)32.946.030.547.527.237.823.346.7
AuthorsOpenReview ↗

Response to Reviewer qebC (2/2)

2. End-to-end efficiency and memory cost of parallel decoding

End-to-end efficiency remains unclear. The 79-fold speedup is over Unquantized Token Decoding and measures TCL, explicitly excluding initial video and prompt processing (Section 2.3). The TCL speedup over Sequential Block Decoding is about 2.5-fold. End-to-end inference time and peak GPU memory are not reported, so the complete practical benefit remains uncertain.

(a) Runtime clarification: What is the total inference time for PTD and Sequential Block Decoding under identical video settings, including initial video and prompt processing?

(b) Memory clarification: What is the peak GPU memory for both methods, and how does it change with the number of predicted boxes? This would clarify any memory cost of parallel decoding.

(a) Decoding versus end-to-end speedup under matched settings: To address this concern and establish the practical benefit, we additionally measured end-to-end latency, including video preprocessing, encoding, and prefill. While verifying the SBD latency comparison, we identified an incorrectly reported SBD latency. The verified mean TCL is 1.6 s, giving a 4×4\times decoding speedup for PTD (1.6 s to 0.4 s). We also checked the separately computed per-query BPS and grounding results and confirmed their reported values. Importantly, PTD reduces total latency from 4.3 s to 3.1 s, a 1.4×1.4\times speedup over SBD, increasing to 1.9×1.9\times for longer tubes (33–64 ground-truth frames). The corresponding decoding speedup increases from 2.7×2.7\times (1–8 frames) to 9.1×9.1\times (33–64 frames), as SBD's decoding time grows from 0.99 to 5.11 s while PTD's remains below 0.6 s. We have corrected the SBD latency throughout the manuscript and now explicitly distinguish PTD’s incremental gain from the cumulative 79×79\times speedup.

Table R6. End-to-end inference latency on VidSTG.

DecoderInput processing (s)Decoding (s)End-to-end (s)PTD speedup (all)PTD speedup (33–64 GT frames)
Unquantized NTP2.7431.634.411.0×19.2× (94.4 vs. 4.9 s)
Quantized NTP2.759.111.93.8×7.7× (37.6 vs. 4.9 s)
SBD2.731.64.31.4×1.9× (9.5 vs. 4.9 s)
PTD (ours)2.740.43.1——

Note: Same setting as Table 1 (2 FPS, up to 64 frames, batch size 1, single MI210 GPU).

(b) Peak GPU memory and scaling with output length: We also observe comparable peak GPU memory usage across all four methods: over the VidSTG test set, the maximum peak is 20.6–20.7 GiB and the mean per-query peak is 11.0–11.1 GiB for every method. The peak is determined by video encoding and prefill, which depend on video length rather than the number of predicted boxes. In no query does decoding exceed the prefill peak, so parallel decoding adds no peak memory cost in this setting. Consistent with this observation, binning by tube length shows that the mean peak rises from 10.9 GiB (1–8 frames) to 12.6 GiB (33–64 frames) across all methods, as longer tubes generally correspond to longer videos. For 33–64 frame tubes, PTD has a mean peak of 12.6 GiB, compared with 12.8 GiB for SBD.

Dear Reviewer,

Thank you for your review. The authors have submitted their rebuttal. Could you please take a moment to review their responses?

Thank you for your time and contribution!

Best regards, Area Chair

Reviewer_nVq4OpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Parallel Tube Decoding (PTD) for efficient spatio-temporal video grounding. Instead of generating bounding boxes one by one, PTD first predicts the temporal interval and then generates all spatial boxes in parallel. The authors introduce Decoupled Block Attention and localization-aware GRPO to improve grounding performance. Experiments on VidSTG and HC-STVG show strong accuracy and significant decoding speedups. The method also shows promising zero-shot generalization to other video grounding tasks.

Critical strengths
  1. Simple and effective parallel decoding design. The idea of predicting all spatial boxes in parallel is intuitive and well-motivated. It removes the sequential decoding bottleneck and reduces error propagation between boxes. The results in Table 1 clearly show the benefits in both efficiency and accuracy.

  2. Strong experimental results. PTD achieves competitive or state-of-the-art results on VidSTG and HC-STVG with only a 4B backbone. The large decoding speedup is impressive. The additional zero-shot experiments also demonstrate good generalization across different tasks.

Critical weaknesses
  1. Limited technical novelty. The proposed PTD largely builds on existing block decoding methods, particularly LocateAnything. Its main contribution is extending parallel box decoding to video tubes by removing cross-box attention. While effective, this appears to be a relatively straightforward extension rather than a fundamentally new method. The paper could better justify the novelty of this design.

  2. Incomplete efficiency evaluation. The reported 79× speedup is impressive, but it only measures decoding latency and excludes video encoding and prefill. Moreover, PTD achieves a 2.5× speedup over the more closely related Sequential Block Decoding baseline. Without end-to-end latency and memory measurements, it is difficult to assess the practical efficiency gains of the proposed method.

Questions for authors

Q1. Could the authors report end-to-end inference latency, including video encoding and prefill? It would be helpful to see how much of the reported speedup remains in practice.

Q2. The overall decoding idea is clear, but the inference pipeline could be better explained. Could the authors provide an architecture diagram and more details on how parallel spatial decoding is implemented within Qwen3-VL?

Q3. Since PTD removes cross-box dependencies, how does it maintain temporal consistency under occlusion or fast motion? A quantitative comparison with Sequential Block Decoding on these challenging cases would be helpful.

Q4. It would be helpful to include a comparison with SARL-STG, which reports better temporal localization on HC-STVG v2 (64.2 vs. 63.1 mtIoU). Could the authors discuss this difference and whether the evaluation settings are comparable?

Q5. PTD seems closely related to LocateAnything, with the main difference being the removal of cross-box attention. Could the authors further clarify the technical novelty beyond this extension and explain how it differs from a straightforward adaptation of existing block decoding methods?

8 comments
AuthorsOpenReview ↗

Response to Reviewer nVq4 (1/3)

1. Technical novelty

Limited technical novelty. The proposed PTD largely builds on existing block decoding methods, particularly LocateAnything. Its main contribution is extending parallel box decoding to video tubes by removing cross-box attention. While effective, this appears to be a relatively straightforward extension rather than a fundamentally new method. The paper could better justify the novelty of this design.

PTD seems closely related to LocateAnything, with the main difference being the removal of cross-box attention. Could the authors further clarify the technical novelty beyond this extension and explain how it differs from a straightforward adaptation of existing block decoding methods?

We build on LocateAnything's block decoding formulation, as acknowledged in the paper. However, LocateAnything retains sequential dependencies across box blocks, whereas PTD predicts spatial boxes independently using frame anchors constructed from the predicted temporal interval, removing tube-length-dependent sequential generation.

Our additional experiments show that this formulation also improves localization accuracy. PTD outperforms anchored SBD by +1.6/+1.9+1.6/+1.9 mvIoU on VidSTG, with gains of +1.9/+2.2+1.9/+2.2 mvIoU retained when GRPO is also applied to SBD.

Unlike methods relying on dedicated spatial decoders, PTD enables parallel tube generation directly within the MLLM's language decoder, without additional prediction heads or external spatial modules. Our contribution therefore goes beyond adapting block decoding to videos, enabling efficient and accurate parallel generative tube decoding within a unified MLLM.


2. Practical efficiency beyond decode-only speedup

Incomplete efficiency evaluation. The reported 79× speedup is impressive, but it only measures decoding latency and excludes video encoding and prefill. Moreover, PTD achieves a 2.5× speedup over the more closely related Sequential Block Decoding baseline. Without end-to-end latency and memory measurements, it is difficult to assess the practical efficiency gains of the proposed method.

Could the authors report end-to-end inference latency, including video encoding and prefill? It would be helpful to see how much of the reported speedup remains in practice.

(a) End-to-end latency and its relationship to the decoding speedup: To address this concern and establish the practical benefit, we additionally measured end-to-end latency, including video preprocessing, encoding, and prefill. While verifying the SBD latency comparison, we identified an incorrectly reported SBD latency. The verified mean TCL is 1.6 s, giving a 4×4\times decoding speedup for PTD (1.6 s to 0.4 s). We also checked the separately computed per-query BPS and grounding results and confirmed their reported values. Importantly, PTD reduces total latency from 4.3 s to 3.1 s, a 1.4×1.4\times speedup over SBD, increasing to 1.9×1.9\times for longer tubes (33–64 ground-truth frames). The corresponding decoding speedup increases from 2.7×2.7\times (1–8 frames) to 9.1×9.1\times (33–64 frames), as SBD's decoding time grows from 0.99 to 5.11 s while PTD's remains below 0.6 s. We have corrected the SBD latency throughout the manuscript and now explicitly distinguish PTD’s incremental gain from the cumulative 79×79\times speedup.

Table R1. End-to-end inference latency on VidSTG.

DecoderInput processing (s)Decoding (s)End-to-end (s)PTD speedup (all)PTD speedup (33–64 GT frames)
Unquantized NTP2.7431.634.411.0×19.2× (94.4 vs. 4.9 s)
Quantized NTP2.759.111.93.8×7.7× (37.6 vs. 4.9 s)
SBD2.731.64.31.4×1.9× (9.5 vs. 4.9 s)
PTD (ours)2.740.43.1——

Note: Same setting as Table 1 (2 FPS, up to 64 frames, batch size 1, single MI210 GPU).

(b) Peak GPU memory: We also observe comparable peak GPU memory usage across all four methods: over the VidSTG test set, the maximum peak is 20.6–20.7 GiB and the mean per-query peak is 11.0–11.1 GiB for every method. The peak is determined by video encoding and prefill, which depend on video length rather than the number of predicted boxes. In no query does decoding exceed the prefill peak, so parallel decoding adds no peak memory cost in this setting. Consistent with this observation, binning by tube length shows that the mean peak rises from 10.9 GiB (1–8 frames) to 12.6 GiB (33–64 frames) across all methods, as longer tubes generally correspond to longer videos. For 33–64 frame tubes, PTD has a mean peak of 12.6 GiB, compared with 12.8 GiB for SBD.

AuthorsOpenReview ↗

Response to Reviewer nVq4 (2/3)

3. Inference pipeline and Qwen3-VL implementation

The overall decoding idea is clear, but the inference pipeline could be better explained. Could the authors provide an architecture diagram and more details on how parallel spatial decoding is implemented within Qwen3-VL?

We thank the reviewer for this suggestion. We have added a figure illustrating the complete inference pipeline of PTD within Qwen3-VL-4B, together with the implementation details below, to Appx. D.4 of the revised paper. PTD does not introduce any additional modules and uses the existing Qwen3-VL vision encoder, language model, and LM head, with an extended vocabulary for localization tokens. The inference pipeline consists of four steps:

(a) Video encoding and input representation. We sample the video at 2 FPS (up to 64 frames) and encode each frame using the Qwen3-VL vision encoder. Following Appx. D.2, we replace the original text timestamps with discrete temporal tokens <t_i>, representing the video as [<t_1> V_1], …, [<t_N> V_N], where ViV_i denotes the visual tokens of frame ii. We use a temporal patch size of 1 so that each sampled frame has its own temporal token. These visual tokens, together with the query, form the initial video-query context. After temporal localization, the predicted temporal block is included to form the shared multimodal prefix PP defined in Sec. 2.2. The temporal and coordinate tokens are added to the existing vocabulary, with embeddings initialized from the corresponding text representations (Appx. D.1).

(b) Round 1: Temporal localization. Given the initial video-query context, we construct a temporal block using its last token qPq_P, followed by five <mask> tokens. In a single forward pass, the language model predicts the temporal interval <time> <t_s> <t_e> </time>, with two <null> tokens used for padding.

(c) Temporal anchor construction. From the predicted interval [<t_s>, <t_e>], we directly construct the temporal anchors <t_s>, …, <t_e>, without any additional model call. Each anchor corresponds to a sampled frame in the video and is used to initialize its spatial block.

(d) Round 2: Parallel spatial localization. For each temporal anchor <t_i>, we construct a six-token spatial input [<t_i>, <mask> × 5]. All spatial blocks are processed together in a single forward pass through the Qwen3-VL language model. We apply Decoupled Block Attention (DBA), where each spatial block attends to the shared video-query prefix, the temporal block, and its own tokens, while attention to other spatial blocks is masked. The LM head jointly predicts the box delimiters and four coordinate tokens for each frame. The predicted coordinates are mapped back to the original frame dimensions, producing the complete spatial tube.

Thus, PTD generates the complete spatio-temporal tube in 1+11+1 decoding rounds, independent of the number of predicted boxes. The implementation requires no additional prediction heads or external spatial decoders, with parallel decoding enabled through temporal anchoring and the attention mask.


4. Temporal consistency under occlusion and fast motion

Since PTD removes cross-box dependencies, how does it maintain temporal consistency under occlusion or fast motion? A quantitative comparison with Sequential Block Decoding on these challenging cases would be helpful.

To address this concern, we additionally compare SBD and PTD on challenging subsets of VidSTG, including occlusion and fast motion. We define an occlusion proxy based on overlap with other annotated objects in at least 25% of frames, and fast motion as the top third of queries by box displacement per frame. As shown in Table R2, PTD consistently outperforms SBD on both subsets. We further evaluate frame-level temporal consistency and observe that PTD produces fewer incorrect boxes, recovers more often after localization errors, and has fewer whole-tube failures. These results suggest that PTD maintains temporal consistency through the shared video-query context and frame-specific temporal anchors, without relying on previously predicted boxes. In contrast, SBD's dependence on preceding boxes allows localization errors to propagate to subsequent frames.

Table R2. Challenging cases and temporal consistency on VidSTG (1 SFT epoch).

MetricSBDPTD (ours)
Challenging cases (mvIoU)
Occlusion proxy (6,937 queries) ↑29.031.2
Fast motion (3,180 queries) ↑21.222.2
Temporal consistency
Incorrect frames (IoU < 0.3, %) ↓26.421.2
Recovery after incorrect frame (%) ↑1.36.8
Incorrect after incorrect frame (%) ↓95.585.7
Whole-tube failures (%) ↓25.417.1
IoU on predicted GT frames ↑58.563.7
AuthorsOpenReview ↗

Response to Reviewer nVq4 (3/3)

5. Comparison with SARL-STG

It would be helpful to include a comparison with SARL-STG, which reports better temporal localization on HC-STVG v2 (64.2 vs. 63.1 mtIoU). Could the authors discuss this difference and whether the evaluation settings are comparable?

We thank the reviewer for pointing out this work. SARL-STG achieves 64.2 mtIoU on HC-STVG v2, compared to 63.1 for PTD. The evaluation settings are comparable. However, PTD achieves higher mvIoU (43.6 vs. 42.5) and comparable [email protected] (42.2 vs. 42.1). The two methods also differ in their training and model architectures. SARL-STG uses a Qwen2.5-VL-7B backbone with an external GroundingDINO detector, along with additional training data from STVG-Wild. In comparison, PTD uses a smaller but newer Qwen3-VL-4B backbone and directly generates both temporal boundaries and spatial boxes without an external detector.

Table R3. Comparison with SARL-STG on VidSTG.

MethodBackboneDecl. mvIoUDecl. @0.3Decl. @0.5Decl. mtIoUInter. mvIoUInter. @0.3Inter. @0.5Inter. mtIoU
STVG-o1Qwen2.5-VL-7B33.548.432.052.127.939.826.050.5
Bridge-STGQwen3-VL-7B37.252.437.452.631.343.831.250.1
SARL-STGQwen2.5-VL-7B + GDINO-B35.551.535.752.329.942.429.650.4
PTD (ours)Qwen3-VL-4B38.353.037.553.732.444.930.352.2

Table R4. Comparison with SARL-STG on HC-STVG v2.

MethodBackbonemvIoU@0.3@0.5mtIoU
STVG-o1Qwen2.5-VL-7B41.268.539.663.8
Bridge-STGQwen3-VL-7B41.567.538.664.1
SARL-STGQwen2.5-VL-7B + GDINO-B42.571.042.164.2
PTD (ours)Qwen3-VL-4B43.671.042.263.1

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to All Reviewers

We thank all reviewers for their constructive feedback. We have conducted several additional experiments and analyses to address the main concerns:

  • Anchored SBD: We provide SBD with the same temporal anchors as PTD while retaining sequential box decoding. PTD maintains +1.6/+1.9+1.6/+1.9 mvIoU, showing that temporal anchoring alone does not explain the accuracy gains.
  • GRPO on SBD: Under matched GRPO training, PTD retains +1.9/+2.2+1.9/+2.2 mvIoU, showing that GRPO does not close the accuracy gap.
  • Bidirectional attention: We allow spatial blocks to attend to each other while retaining 1+11+1 decoding rounds. PTD achieves +0.6/+0.7+0.6/+0.7 mvIoU, suggesting that additional cross-block attention does not provide a clear benefit for grounding accuracy.
  • End-to-end efficiency: We additionally measure inference latency including video encoding and prefill. PTD is 1.4×1.4\times faster than SBD overall (1.9×1.9\times on longer tubes), with comparable peak GPU memory.
  • Clarification of efficiency claims. We have revised the manuscript to clearly distinguish the cumulative 79×79\times decoding speedup over standard autoregressive decoding from PTD's incremental contribution. With the corrected SBD latency, PTD achieves 4×4\times faster decoding and 1.4×1.4\times faster end-to-end inference over SBD. We have also refined the novelty and attribution claims to better distinguish our contributions from prior work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.