Parallel Tube Decoding generates a video’s full spatio-temporal box trajectory in two decoding rounds instead of one-per-frame, by predicting every frame’s box in parallel once the time interval is fixed, cutting tube completion latency 79× on VidSTG.
You’re building a video assistant that answers “show me every frame where the person in the red jacket is handing off the package.” The model has to return both a time interval and a bounding box on each frame in that interval. Today’s Multimodal Large Language Model-based systems generate this frame by frame: box at t=1, then condition on that to predict t=2, and so on. Latency scales linearly with clip length, and one bad early box drags later boxes off-target. The dominant workaround, used by systems like DEViL and STVG-R1, is to give up on native generation entirely and bolt on an external detector or tracker. This paper keeps localization inside the language model but makes it parallel.
The key observation: once you know when the event happens, the correct box at each frame depends only on that frame’s pixels and the query, not on the box at the previous frame. So the cross-frame dependency that autoregressive decoding enforces is artificial. Parallel Tube Decoding exploits this in two stages. First, the model predicts one temporal block containing the start and end tokens of the event. Second, for every frame in that interval, it lays down a masked spatial block anchored to that frame’s time token, and decodes all of them in a single forward pass.
Making this work requires a custom attention pattern the authors call Decoupled Block Attention. Each spatial block can attend to the video, the query, and the temporal block, but cannot attend to any other spatial block. That’s the mechanism preventing frame-to-frame leakage during parallel decoding. Coordinates and timestamps are represented as single discrete tokens from a vocabulary of 1,001 spatial bins and 100 temporal bins, so each box is a fixed 7-token block.
Training runs two objectives in one pass: a standard next-token loss for autoregressive capability, and a multi-token block-prediction loss for Parallel Tube Decoding. After supervised fine-tuning, they run Group Relative Policy Optimization (GRPO) with two rewards: temporal IoU on the interval, and generalized IoU plus an L1 penalty on boxes inside the temporally-overlapping frames.
# Inference
prefix = encode(video, query)
temporal_block = decode_block(prefix) # round 1: <time><t_s><t_e></time>
t_s, t_e = parse(temporal_block)
# round 2: all frames in parallel, no cross-block attention
spatial_blocks = decode_parallel([
init_block(time_token=t_i, mask_len=5)
for t_i in range(t_s, t_e + 1)
], prefix + temporal_block, attn=decoupled_block_attention)
return (t_s, t_e), [parse_box(b) for b in spatial_blocks]
The prevailing assumption in Multimodal Large Language Model-based grounding is that a spatial trajectory is a sequence, so it must be decoded like one, with each box conditioned on the boxes before it. This paper shows the opposite: the trajectory’s sequential appearance is an artifact of the output format, not the task. Given the video and the time anchor for a frame, that frame’s box is independent of every other frame’s box, and forcing a dependency actively hurts by pulling attention away from the pixels. The evidence isn’t the headline benchmark score. It’s an intervention experiment where fixing one wrong box in a sequential decoder measurably improves the next few boxes, proving errors were propagating along a dependency that shouldn’t exist.
The load-bearing finding is the attention and error-propagation analysis. In sequential block decoding, as generation proceeds down the tube, attention shifts away from the video and toward the model’s own previously-emitted coordinate tokens. When the authors surgically replace one wrong box with its ground truth and re-decode the rest, downstream boxes improve, with the effect largest for nearby frames and decaying with distance. That decay curve is direct evidence of an error-propagation channel that Parallel Tube Decoding eliminates by construction.
The efficiency numbers follow from that design. On VidSTG, compared to unquantized text-based decoding, Parallel Tube Decoding takes tube completion latency from 31.6s to 0.4s and lifts throughput from 0.5 to 45.9 boxes per second, the paper’s headline 79× and 92× figures. Crucially, latency stays nearly flat as tube length grows from 8 to 64 boxes (0.33s → 0.40s), while sequential block decoding rises from 0.72s to 6.18s.
Accuracy improves alongside efficiency, not against it. On VidSTG with a 4B backbone, Parallel Tube Decoding matches or beats 7B systems that use external detectors or tracking pipelines, and Group Relative Policy Optimization (GRPO) adds another few points on top. Zero-shot transfer is strong: on Charades-STA temporal grounding, +4.7 mIoU over the best zero-shot baseline; on ReXTime grounded VideoQA, +15.6 mIoU zero-shot, beating even a fine-tuned baseline; on referring video object segmentation paired with SAM2, it beats a fine-tuned 4B competitor on Ref-DAVIS by 8.4 points.
Reach for this pattern when you’re building a video agent that has to return dense per-frame localizations, whether that’s a highlight extractor, a surveillance query system, or a data-labeling assistant that draws boxes on every frame of a clip. If your current pipeline serializes those boxes through the language decoder, the latency hit at longer clip lengths is what makes it unshippable. The reframe is: don’t predict frame N’s box conditioned on frame N-1’s box. Predict all of them from the shared video context and per-frame time anchors, with an attention mask that prevents cross-frame leakage. The Decoupled Block Attention pattern is the reusable idea, and the same recipe would apply to any per-timestep structured output.
Code and project page are released at GitHub. Backbone is Qwen3-VL-4B trained with LoRA rank 32. Training data is the ~90K combined training splits of VidSTG and HC-STVG, plus a 16K subset filtered for high within-group variance for the Group Relative Policy Optimization (GRPO) stage.
When your output looks like a sequence but the task doesn’t require one, kill the dependency and decode in parallel. The right question isn’t “how do I speed up autoregressive decoding of this trajectory,” it’s “does box N actually depend on box N-1, or am I just serializing it because that’s how my decoder works?” If the answer is the latter, you can often get both faster inference and better accuracy at once, because the sequential dependency was letting errors compound.
•
Parallel decoding of per-frame boxes assumes each frame carries enough visual evidence on its own to localize the target. For heavily occluded targets or identity re-acquisition after the target leaves and re-enters view, the failure cases the paper shows suggest a cross-frame consistency signal actually is useful, and Parallel Tube Decoding gives that up.
•
The formulation assumes exactly one continuous temporal interval and one spatial tube per query. Multi-segment events, multi-instance references (“every person wearing red”), and out-of-view gaps are out of scope; the authors call this out as future work.
•
The 79×/92× speedups are measured against unquantized text-token decoding on the same backbone, which is a weak baseline in absolute terms. Against the sequential block decoding variant, tube completion latency drops from 1.0s to 0.4s. Still a real win, but a 2.5× number is the honest apples-to-apples comparison, not 79×.