PaperlayerView exact revision on arXiv

Source-linked AI summary

Temporal Backtracking Search for Test-time Generative Video Reasoning

Sejoon Jun, Zheng Ding, Huangyuan Su, Weirui Ye, Yilun Du

arXiv:2606.13861v1cs.CV

TL;DR

Generative video reasoning remains limited by single-shot rollouts, while existing video test-time scaling searches denoising steps or resamples whole videos. TBS searches over verified temporal prefixes through a generate–verify–restart loop. It Pareto-dominates matched-budget BoN across three domains and reaches 22.7% versus BoN’s 0.7% exact match in strict OOD evaluation.

  • Problem

    Video test-time scaling methods search denoising trajectories or partially denoised latents, while temporal BoN treats a whole rollout as an indivisible block.

    Source: §1 · p. 1

  • Method

    TBS uses variable-K conditioning, temporal process verification, and prefix-based search to restart generation from verified prefixes.

    Source: §1 · p. 2

  • Results

    Across three verification regimes TBS Pareto-dominates matched-budget BoN; on strict OOD, TBS reaches 22.7% versus BoN’s 0.7% exact match.

    Source: §1 · p. 2

  • Takeaways & Limitations

    TBS’s gains reflect video models’ local reasoning competence across symbolic, learned, and physics-based verification regimes.

    Source: §1 · p. 2

    TBS cannot supply competence the base model lacks; under heavy visual randomization, BoN-3 succeeds on 15% of episodes and TBS-3 on 16%.

    Source: §4.5 · p. 9

Abstract

from arXiv · show

While test-time scaling has revolutionized reasoning in large language models, generative video reasoning remains bottlenecked by a single-shot paradigm. We demonstrate that searching over denoising steps cannot rescue logically flawed rollouts because spatial trajectories commit early in the diffusion process. Root-level Best-of-N (BoN) sampling is similarly inefficient: reasoning errors cluster early in the temporal axis, and resampling blindly discards verified upstream progress. To unlock effective test-time scaling for video models, we introduce Temporal Backtracking Search (TBS), which shifts the search space to the temporal axis. TBS transforms video generation into an iterative generate-verify-restart loop via three core mechanisms: (1) variable-K conditioning to resume generation from arbitrary clean prefixes; (2) temporal process verification to localize failures and extract valid restart anchors; and (3) prefix-based search to reallocate compute toward extending correct trajectories rather than root resampling. Across algorithmic, navigation, and robotics domains, TBS Pareto-dominates matched-budget BoN. In a strict out-of-distribution setting where one-shot generation collapses (0.7% for BoN), TBS achieves 22.7%, with every solved episode stemming from a restarted branch. Ultimately, TBS reveals that the local reasoning competence of video models far exceeds what single-shot rollouts indicate, providing a scalable test-time framework to unlock it.

1 Introduction

TBS shifts video reasoning search from denoising steps and whole-rollout resampling to temporal prefixes that preserve verified progress. Across three evaluation domains, it Pareto-dominates matched-budget BoN, including a strict OOD setting where TBS reaches 22.7% versus BoN’s 0.7%.

1 Introduction

  • Video models commit to a spatial trajectory in the earliest denoising steps, while reasoning failures cluster early and root-level BoN discards valid upstream prefixes.Later denoising compute cannot redirect an already flawed trajectory.Source: §1 · p. 1, Figure 1 · p. 2
  • TBS turns single-shot generation into a generate–verify–restart loop using variable-K conditioning, temporal process verification, and prefix-based search.These mechanisms resume from clean prefixes, locate failures, and extend valid trajectories instead of resampling from the root.Source: §1 · p. 2
  • Across three verification regimes, TBS Pareto-dominates matched-budget BoN; on strict OOD, TBS reaches 22.7% versus BoN’s 0.7% exact match.Every solved strict-OOD episode came from a restarted child branch.Source: §1 · p. 2
  • The paper identifies early trajectory commitment and clustered early failures as two bottlenecks for video test-time scaling.It proposes temporal correction rather than monolithic single-shot sampling.Source: §1 · p. 2
  • The reported results indicate that temporal backtracking can stitch together video models’ local reasoning competence under symbolic, learned, and physics-based verification.The evaluation spans algorithmic, navigation, and robotics tasks.Source: §1 · p. 2

2 Related Work

Prior video test-time methods search denoising trajectories or partially denoised latents, while TBS searches verified temporal prefixes. Its verifier localizes failure, allowing causal repair while leaving verified past frames untouched.

Test-time scaling and process verification

  • TBS adapts process verification to video by locating where a trajectory deviates rather than only judging whether its terminal sequence is flawed.This shifts evaluation from monolithic rollouts to verified prefixes.Source: §2 · p. 2

Long-horizon video generation

  • Unlike generative stitching methods that use bidirectional harmonization or global resampling, TBS performs verifier-localized causal repair and leaves verified pasts untouched.Diffusion Forcing provides the clean-prefix continuation primitive for variable-K conditioning.Source: §2 · p. 2

Test-time scaling for video generation

  • TBS’s generate–verify–restart loop caches a valid prefix after locating a failure, then restarts from a prioritized anchor rather than discarding the whole rollout.A single error invalidates the remaining suffix in single-shot generation.Source: Figure 2 · p. 3
  • TBS differs from denoising-axis methods by searching temporal frames for trajectory correctness, with process supervision ranging from symbolic rules to simulator replay.The cited concurrent studies diagnose long-horizon limits but offer no constructive mitigation.Source: §2 · pp. 2–3

3 Method

The method formalizes trajectory validity and the conditional reuse gap, then searches over verified prefixes and trains the generator to continue from variable-length clean prefixes. This enables temporal branching while preserving prior motion context.

3.1 Problem Formulation and the Conditional Reuse Gap

  • A rollout is correct when every transition is valid and it reaches the goal; its first failure separates a valid prefix from an invalid suffix.The conditional reuse gap captures why extending a clean partial sequence is more tractable than generating the long-horizon rollout from scratch.Source: §3.1 · p. 3

3.2 Temporal Backtracking Search (TBS)

  • TBS maintains a priority frontier of verified prefix anchors, expands the highest-priority anchor with candidate suffixes, and returns a solved child when found.The verifier supplies the first failure frame, aligned restart anchor, and priority score.Source: §3.2 · p. 4

3.3 Variable-K Conditioning

  • Variable-K conditioning enables generation from a clean temporal prefix, and a progressive curriculum broadens training from K=1 to K=20.On 40 provably repairable long-horizon Maze trajectories, replacing the full prefix with a single-frame reset reduced repair success from 100% to 2.5%.Source: §3.3 · pp. 4–5
  • Evaluation spans rule-based grid-worlds, continuous navigation, and robotic manipulation, with Figure 3 depicting the task domains.The generator must preserve exact prefix conditioning to synthesize a suffix from a verified restart point.Source: §3.3 · p. 4, Figure 3 · p. 5

4 Experiments

The experiments evaluate TBS across symbolic grid-worlds, learned-predictor navigation, and simulator-based manipulation. TBS improves on matched-budget BoN, with gains tied to preserving verified prefixes and bounded by the base model’s ability to produce repairable trajectories.

4.1 Experimental Setup

  • Evaluation spans exact symbolic verification in grid-worlds, learned trajectory prediction in navigation, and simulator-replay verification in robotic manipulation.The shared baseline is matched-budget BoN; TBS and BoN use identical terminal evaluators and root candidate pools.Source: §4.1 · pp. 5–6

4.2 Main Results

  • 22.7% vs. 0.7% EM on Keys-and-Doors Strict-OOD: TBS-20 exceeds BoN-20, and all 68 TBS solves came from restarted branches.Across five rule-based domains, TBS matches or exceeds matched-budget BoN on every Overall score; the gap grows on harder and longer-horizon splits.Source: §4.2 · pp. 6–7, Table 1 · p. 6
  • TBS improves all five Target-Bench trajectory metrics at both budgets and adds +4% RoboTwin success in clean scenes at every budget.At budget 5, Target-Bench Miss Rate falls from 2.70% to 1.56% and Approach Consistency rises from 0.872 to 0.936; RoboTwin gains shrink to +1% under visual randomization.Source: Table 2 · p. 6, §4.2 · p. 7, Figure 4 · p. 7

4.3 Mechanism: Prefix Reuse Targets Early Failure Bottlenecks

  • In structured domains, 72.7% of failed BoN-20 Maze rollouts and 78.3% of Keys-and-Doors OOD failures begin in the first 0–20% of trajectories.Past 40 steps, Maze EM is 17.1% for BoN-20 versus 60.0% for TBS-20; prefix reuse preserves verified progress while spending compute on the remaining suffix.Source: §4.3 · pp. 7–8

4.4 Ablation Studies

  • Replacing a verified temporal prefix with a single-frame reset drops repair success from 100% to 2.5% on Maze and 5.0% on Sliding.The verified prefix carries motion information not redundant with the last frame’s visual content.Source: §4.4 · p. 8
  • At budget 20, Maze reaches 90.3% with narrow-deep search, while Sokoban reaches 82.7% with width 8 versus 76.5% with width 2.The best search shape varies by domain: depth suits suffix-localized failures, while width helps when prefixes may already be corrupted.Source: §4.4 · p. 8
  • At fixed search shape, richer verifier signals improve TBS by +4.2 to +10.2 pp on Sokoban and +2.2 to +4.3 pp on Sliding Puzzle.The signals identify dead states or undo moves, providing more useful restart guidance than prefix length alone.Source: §4.4 · p. 8

4.5 Operating Envelope: When Prefix Reuse Helps and When It Stops

  • TBS matches or exceeds BoN under increasing verifier noise, but its gains shrink when visual randomization leaves the base policy unable to reach the target.Under the strongest perturbation, scores converge at budget 3 (∆= +0.001 overall score); under heavy visual randomization, success is 15% for BoN-3 and 16% for TBS-3. Prefix reuse depends on a verifier that approximately localizes deviations and a base model that produces repairable prefixes.Source: §4.5 · pp. 8–9, Figure 7 · p. 9

5 Discussion

TBS uses verified-prefix reuse to repair localized errors across symbolic, learned, and physics-based environments. Its frontier search is not a full symbolic planner, and the generator must still synthesize each continuation.

5 Discussion

  • TBS caches verified partial progress and reallocates compute to repair localized errors across symbolic, learned, and physics-based environments.The discussion frames this as shifting test-time scaling from single-shot generation to the temporal axis.Source: §5 · p. 9

A Terminology and Claim Boundaries

  • Prefix-priority best-first search over verified prefixes is not UCT-style Monte Carlo tree search or a full symbolic planner.The paper claims improved long-horizon generative video reasoning through prefix reuse with frontier search.Source: A Terminology and Claim Boundaries · p. 12
  • Domain-specific process verifiers localize failures and provide restart anchors, but the generator—not the verifier—must synthesize the suffix.Structured-domain verifiers can localize the first checked failure frame in grid-world or grid-like rule-based problems.Source: A Terminology and Claim Boundaries · p. 12

B Structured Video Reasoning Details

  • The appendix collects structured-reasoning details, extended results, verifier-quality ablations, and search-policy ablations.Its topics include training settings, domain definitions, prompts, search budgets, failure clustering, and depth–width behavior.Source: B Structured Video Reasoning Details · p. 13

B.1 Prefix-Conditioning Ablation

The ablation tests whether full verified-prefix conditioning can repair parent prefixes better than a last-frame reset. The accompanying sections describe training, task domains, verification, and search-budget choices.

B.1 Prefix-Conditioning Ablation

  • 2.5% on Maze and 5.0% on Sliding are the recovery rates for last_frame_reset, versus 100% by construction for full_prefix.The subset contains only parent prefixes that full_prefix provably repairs, so this measures relative repair capability, not population-level success.Source: Table 3 · p. 13, §B.1 · p. 13

B.2 Training and Inference Details

  • Each domain uses a separate LoRA adapter on a frozen Wan2.2-TI2V-5B base model, with training on pre-encoded VAE latent caches.During training, the first K latent frames are clean context and the suffix frames receive a sampled timestep, teaching regeneration of the continuation.Source: §B.2 · p. 13, §B.2.3 · p. 14

B.3 Structured Video Reasoning Domains

  • The evaluation covers five deterministic rule-based domains with 600 samples each, plus 300 strict-OOD Keys-and-Doors samples with longer-than-training paths.The 600 samples per domain are split into 100 easy, 200 medium, and 300 hard examples.Source: §B.3 · pp. 14–15

B.4 Prompt Templates

  • Prompts share blocks for object identities and colors, movement constraints, scene invariance, and camera constraints; difficulty comes from the input image, not text.Prompt wording is uniform across difficulty levels within each domain.Source: §B.4 · p. 15

B.5 Verifier and Restart Details

  • The verifier returns a failure frame, restart frame, and prefix length, exposing a restartable prefix without supplying the correct continuation.For mazes, grid transitions are checked against geometry, walls, and task constraints; the restart frame is aligned to a latent-frame boundary.Source: §B.5 · p. 16, §B.5.1 · p. 17

B.5.2 Sokoban; B.5.3 Sliding Puzzle

  • Sokoban verification checks legal pushes and dead states, while Sliding Puzzle verification uses OCR and can roll back a move that creates a semantic dead-end.Sokoban priority also uses BFS state quality; Sliding Puzzle rollback returns to the prior stable board state.Source: §B.5.2 · p. 17, §B.5.3 · p. 17, §B.6 · p. 17

B.5.4 Keys-and-Doors

  • Keys-and-Doors verification checks key order and confirms that the door is reached after all keys are collected.Its OOD evaluation uses 161-frame videos with path lengths exceeding the training distribution.Source: §B.5.4 · p. 17

B.6 TBS Search Budgets and Priority

  • TBS budgets are parameterized by root width k1, samples per expanded non-root node s, and maximum expansions m; BoN uses B independent roots at matched budget.Sokoban prioritizes BFS state quality before prefix length, while Sliding Puzzle can roll back to a prior stable state.Source: §B.6 · p. 17

B.7.1 Confidence interval methodology

The appendix reports confidence-interval conventions and further evidence on failure clustering, horizon length, and restarted-branch solves. Failures concentrate early in some domains, while TBS continues finding solutions through deeper restarts.

B.7.1 Confidence interval methodology

  • Wilson 95% confidence intervals are used for EM because it is binomial, and unlike Wald intervals they do not collapse at 0% or 100%.Reported ± is the larger interval half, ensuring the full Wilson interval is contained even at saturation.Source: §B.7.1 · pp. 17–18

B.7.2 Maze rich-prompt path-length breakdown

  • At 41+ steps, BoN-20 reaches 17.1% EM while TBS-20 reaches 60.0%, a +42.9 pp gain.The path-length bins are posthoc analysis, not an online solution signal for TBS.Source: Table 8 · p. 18

B.7.3 Keys-and-Doors strict-OOD path-cell breakdown

  • On strict-OOD Keys-and-Doors, BoN-20 stays below 1.1% across path-cell bins, while TBS-20 reaches 15.7–27.5%.The table reports EM by path-cell-count bin.Source: Table 9 · p. 18

B.8 Failure Clustering Statistics

  • More than 70% of BoN failures cluster in the earliest 0–20% progress bin for Maze and Keys-and-Doors-OOD.The failure-to-recovery distribution compares failed BoN-20 root samples with TBS-20 episode outcomes.Source: Table 10 · p. 19

B.9 Root Solves vs. Restarted-Branch Solves

  • On Keys-and-Doors-OOD, every solved TBS-20 episode came from a restarted branch; on 2D Maze, TBS kept gaining across multiple restart depths.The depth-by-depth Maze results report solve rates above 25% through depth 3, showing reused prefixes remain useful after multiple continuations.Source: Table 12 · p. 19, §B.9 · p. 20, Table 14 · p. 20

B.10 Root-Width Sensitivity at Matched Budget

The preferred root width depends on the domain: Sokoban benefits from width, while Maze benefits from depth and some tasks are nearly width-insensitive. At matched budgets, TBS’s depth–width behavior varies by domain.

B.10 Root-Width Sensitivity at Matched Budget

  • At B=20, the per-domain comparison takes the best EM among configurations with each root width, while holding total generation count fixed.The range across root widths measures sensitivity to that choice.Source: §B.10 · p. 20
  • 82.7% EM at k1=8 versus 76.5% at k1=2 shows Sokoban benefits from wider roots; Maze and Maze3D vary by at most 1 pp across root widths.At strict-OOD, every k1 value reaches at least 18.9% EM versus BoN-20’s 0.7%.Source: Table 15 · p. 20, §B.10 · pp. 20–21

B.11 Depth–Width Search Shape

  • Across budgets, k1=2 dominates in 2D Maze, k1=8 in Sokoban, and 3D Maze and Keys-Doors ID curves remain within 2 pp.The figure reports each domain’s best TBS EM across swept root-width and budget combinations; strict-OOD is omitted because its scale is not meaningfully comparable to in-distribution results.Source: Figure 8 · p. 21, §B.11 · p. 21
  • The section contrasts depth-friendly Maze and width-friendly Sokoban with saturated domains where root-width differences are small.The narrow-and-deep Maze curve remains above wider variants at every budget, while wider roots dominate in Sokoban.Source: §B.11 · p. 21, Figure 8 · p. 21

B.12 Verifier-Quality Ablations: Sokoban BFS-Aware and Sliding Undo-Required

These ablations show that prefix reuse depends on restart-anchor quality: state-aware Sokoban verification and undo-required Sliding Puzzle semantics improve TBS by identifying more useful anchors.

Sokoban: state-aware verification is necessary

  • Sokoban’s visually legal prefixes can encode strategically dead box states, so prefix length alone may preserve an unusable restart anchor.The progress-aware ranking uses EM, non-dead BFS state, remaining moves, BFS progress, then prefix length as fallback.Source: §B.12 · pp. 22–23
  • Progress-aware Sokoban verification improves exact match by +4.2 to +10.2 pp across 9 matched configurations at budgets 8–20.It uses BFS dead-state, remaining-moves, and progress signals; dataset, generation model, prompt, and budget are held fixed.Source: Table 16 · p. 22

Sliding Puzzle: undo-required semantic rollback

  • Undo-required verification treats a move as failure when the only optimal next move is to undo it, rolling TBS back to the prior settled board.The cross-domain takeaway is that domain-specific verification is needed when prefix-length priority yields corrupted anchors.Source: §B.12 · p. 23
  • Undo-required semantics improve TBS by +2.2 to +4.3 pp across 9 matched configurations, while reducing BoN by −0.8 to −1.6 pp.The comparison supports a restart-anchor benefit rather than a more permissive terminal evaluator.Source: Figure 9 · p. 22, Table 17 · p. 23, §B.12 · p. 23

B.13 Search-Policy Ablation: Greedy, Beam-2, and Random Frontiers

The search-policy ablation tests whether prefix reuse alone suffices or whether frontier memory and priority matter. Full TBS is best or tied across the headline structured splits.

B.13 Search-Policy Ablation: Greedy, Beam-2, and Random Frontiers

  • At B=20, TBS is best or tied on every hard and strict-OOD structured split, with exact-match percentages reported over n=300 samples.Greedy, Beam-2, Random, and TBS share the per-domain TBS-20 shape; frontier memory and pop rule differ.Source: Table 18 · p. 24, §B.13 · p. 24
  • At B=20, full TBS exceeds Beam-2 by +2.7 pp on Maze, +2.4 pp on Sokoban, +1.4 pp on Sliding, +1.7 pp on Keys-ID, and +3.0 pp on strict-OOD Keys.Beam-2 recovers much of the gap by preserving one alternate restart anchor.Source: §B.13 · p. 24
  • Greedy prefix repair falls below TBS at B=20 on 2D Maze, Sliding, Sokoban, Keys-ID, and strict-OOD Keys.It retains only the best verified anchor, while Beam-2 retains two and Random uses an uncapped frontier with random popping.Source: §B.13 · p. 24
  • The ablation concludes that verified temporal prefix reuse is the dominant mechanism, but the full priority frontier is not redundant.Greedy over-commits to a single lineage; Beam-2 is a strong compact approximation, while full TBS is best or tied across all six structured splits.Source: §B.13 · p. 24

C.1 Official benchmark score and metric definitions

This section specifies the trajectory score and the verification pipelines used for navigation and robotic manipulation. It also describes how manipulation restarts preserve pre-grasp progress after a failed attempt.

C.1 Official benchmark score and metric definitions

  • Target-Bench combines five trajectory metrics into one score: ADE, FDE, miss rate, soft endpoint score, and approach-consistency corridor score.Trajectories are decoded from videos, anchored to the first-frame pose, calibrated to benchmark metric space, and reported as the selected video's official overall score.Source: §C.1 · p. 24

C.2 Predictor details

  • The Target-Bench verifier predicts a metric-space future path from the current frame and prompt, then compares decoded trajectories against nine predicted prefix points to find the first invalid point.The predictor uses V-JEPA2 image tokens and text embeddings; the tolerance schedule varies along the prefix.Source: §C.2 · pp. 24–25

D.1 Pipeline

  • The RoboTwin pipeline decodes generated videos into 14-D action sequences and replays them in simulation, where per-step state and task predicates inform verification.The search budget is counted at rollout/branch level; segments contain 61 frames, with an optional continuation when the first segment lacks a goal-attempt window.Source: §D.1 · p. 25

D.2 First-goal-attempt window

  • After a meaningful failed manipulation attempt, TBS restarts from the preceding gripper-opening boundary, preserving pre-grasp motion while focusing compute on repair.The first-attempt detector uses simulator state, decoded actions, gripper timing, and object–target distance to avoid counting repeated retries as separate solves.Source: §D.2 · p. 25

D.3 The 10-task progress-aware subset

The selected RoboTwin subset targets tasks with progress-aware manipulation and detectable partial progress. Results compare matched-budget TBS and BoN across clean and randomized scenes.

D.3 The 10-task progress-aware subset

  • The 10-task subset targets progress-aware manipulation with detectable first-goal-attempt windows and visible reach, grasp, move, place, stack, or release sub-goals.Source: §D.3 · p. 25, Table 19 · p. 26
  • Each task has 10 evaluation episodes in clean and randomized scenes, with matched-budget BoN and TBS comparisons in both regimes.Randomized scenes perturb visual background and object placement relative to generator-seen conditions.Source: §D.3 · p. 25
  • In clean scenes, TBS gains +4 successful episodes over matched-budget BoN at both budgets; in randomized scenes, performance is lower and the gain is smaller.The reported explanation is that fewer randomized-scene root rollouts produce repairable verified prefixes.Source: Table 20 · p. 26

E Limitations and Failure Cases

TBS’s gains are bounded by the quality and availability of reusable prefixes and process verification, while overhead depends on the verifier. The visual examples are presented in Figures 10 and 11.

E Limitations and Failure Cases

  • TBS cannot create base-model competence, and its gains shrink when rollouts fail before making meaningful progress.Examples include RoboTwin randomized, Sliding hard with semantic prefix corruption, and Maze3D 24-grid when the tracker loses the agent.Source: E Limitations and Failure Cases · p. 26
  • Verifier mislocalization can preserve corrupted prefixes and cause repeated failure; wider roots mitigate Sokoban tracking failures better than deeper search.Sliding undo-required also re-fails when the verifier misdetects the wrong-board state.Source: E Limitations and Failure Cases · p. 26
  • On Target-Bench, gains depend on learned process-signal quality and converge with BoN at the strongest tested noise, q=0.3 (~0.7 m mean ADE noise).Source: E Limitations and Failure Cases · p. 26
  • Where BoN-1 already solves many problems, including most Sokoban splits, TBS matches or slightly exceeds it but yields no large gains.These settings are treated as null controls for downside risk, not evidence for TBS.Source: E Limitations and Failure Cases · p. 26
  • TBS runs the verifier on every root and child rollout; overhead is negligible for symbolic verifiers and measurable but small for learned and simulator-replay verifiers.Source: E Limitations and Failure Cases · pp. 26–27

F Visual Examples

Related papers

Loading 2606.13861v1…