Temporal Backtracking Search for Test-time Generative Video Reasoning

Abstract

Why existing test-time scaling fails

Test-time scaling transformed reasoning in language models, but the recipes that work there do not transfer to generative video. The standard moves — searching over denoising steps, or sampling many full rollouts and keeping the best (Best-of-N) — both assume the model can explore alternatives at the point where it went wrong. For video reasoning, neither assumption holds. We trace this to two empirical bottlenecks.

Denoising-step search

The spatial trajectory is committed at the very first denoising step — S₁, S₅, and S₄₀ all produce the same plan. There is nothing left to search over.

✗ Wrong axis entirely

Root-level Best-of-N

72–78% of failures occur in the first 20% of a rollout. Every independent resample replays the same early bottleneck — discarding the verified-correct remainder each time.

✗ Wastes verified upstream progress

One-shot generation, long horizons

Correctness must hold at every frame simultaneously. On 2D Maze paths of 41+ steps, single-shot BoN-1 reaches only 1.9% — errors compound multiplicatively as the horizon grows.

✗ Collapses with horizon length

Bottleneck 1 — the trajectory is decided early, in the wrong search space. If we decode the same noisy latent at successive denoising steps, the high-level motion plan is already fixed within the first few steps and never changes afterward. So spending more compute on later denoising steps cannot redirect a plan that was wrong from the start — the denoising axis simply has nothing to explore.

(a) The same noisy latent at S₁, S₅, S₄₀: the motion plan is identical throughout — the trajectory is committed immediately. (b) Denoising-step search offers no trajectory exploration. (c) Temporal-step search does, by branching from verified prefixes.

Bottleneck 2 — failures cluster early, so blind resampling wastes the budget. Reasoning errors are not spread evenly along a rollout; they concentrate heavily in its opening frames. Because Best-of-N starts every candidate from scratch, it keeps re-failing in that same early region and throws away the correct frames it had already produced downstream. As the horizon lengthens, the probability that an independent rollout clears the bottleneck shrinks, and exact match collapses.

Temporal Backtracking Search

Cache the valid prefix. Branch from there. Repeat.

Both bottlenecks point the same way: stop searching the denoising axis, and stop throwing away verified frames. TBS reformulates video reasoning as inference-time search over the temporal axis. Instead of treating a rollout as one indivisible block, it isolates the first failure, keeps the verified frames before it, and spends compute extending that prefix — turning one long-horizon problem into a sequence of short, locally-easy continuations.

BoN (top): one error discards everything; restart from frame 1. TBS (bottom): localize the first failure, cache the verified prefix as a restart anchor in a priority frontier, regenerate only the invalid suffix. Full-prefix conditioning (variable-K) preserves the motion context that a single-frame state reset loses entirely.

Three components make the loop work:

Results

We evaluate across three regimes that span the realistic spectrum of process supervision — from exact symbolic rules to a learned noisy predictor to a closed-loop physics simulator. At matched compute budget, TBS Pareto-dominates Best-of-N in every regime.

Five rule-based grid-worlds where deterministic rules localize the first failure exactly. The gain tracks horizon length: tiny on already-saturated short tasks, large where rollouts are long. The clearest case is strict-OOD Keys-and-Doors, where every TBS solve comes from a restarted branch.

Where do the solves come from? Of every episode TBS-20 solves, how many were already solved by a root rollout (depth 0) versus only after a restarted branch (depth ≥ 1). The longer-horizon domains lean heavily on restarts — and strict-OOD Keys-and-Doors is decisive: not a single solve comes from a root sample; all 68 come from restarted branches.

Target-Bench tests whether the gains survive when the verifier is learned and noisy rather than an exact rule. TBS improves every one of the five trajectory metrics at both budgets, with the largest gains on miss rate and approach consistency — a noisy process signal is still enough to localize where a rollout drifts.

Generated videos are decoded to robot actions and replayed in a physics simulator. TBS helps when the base video model produces a repairable approach prefix — reusing the verified pre-grasp motion and regenerating only the failed contact window — but gains shrink under heavy visual randomization, where the base policy rarely reaches the target and there is little to repair.

Qualitative examples

Each clip shows BoN exhausting its budget and failing, followed by TBS backtracking to the failure point and succeeding from a restarted branch. Grouped by the same three regimes as the results above.

BibTeX

@article{jun2026temporal,
  title   = {Temporal Backtracking Search for Test-time Generative Video Reasoning},
  author  = {Jun, Sejoon and Ding, Zheng and Su, Chloe H. and Ye, Weirui and Du, Yilun},
  journal = {arXiv preprint arXiv:2606.13861},
  year    = {2026}
}