# Temporal Backtracking Search for Test-time Generative Video Reasoning

arXiv: https://arxiv.org/abs/2606.13861 · HTML: https://mlsanity.com/paper/2606.13861/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Multimodal reasoning, one of 17 directions in LLM reasoning.
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 11 Jun 2026.

## Placed in

- LLM reasoning / [Multimodal reasoning](https://mlsanity.com/lr/multimodal-reasoning/)

## Builds on (most cited first, 18 of 18)

- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [RoboTwin 2.0: A Scalable Data Generator and Benchmark with Strong Domain Randomization for Robust Bimanual Robotic Manipulation](https://mlsanity.com/paper/2506.18088/) (2025)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Inference-Time Scaling for Diffusion Models beyond Scaling Denoising Steps](https://mlsanity.com/paper/2501.09732/) (2025)
- [Video models are zero-shot learners and reasoners](https://mlsanity.com/paper/2509.20328/) (2025)
- [Foundation Models for Decision Making: Problems, Methods, and Opportunities](https://mlsanity.com/paper/2303.04129/) (2023)
- [Vidar: Embodied Video Diffusion Model for Generalist Manipulation](https://mlsanity.com/paper/2507.12898/) (2025)
- [Inference-time Scaling of Diffusion Models through Classical Search](https://mlsanity.com/paper/2505.23614/) (2025)
- [Inference-Time Text-to-Video Alignment with Diffusion Latent Beam Search](https://mlsanity.com/paper/2501.19252/) (2025)
- [Generative Trajectory Stitching through Diffusion Composition](https://mlsanity.com/paper/2503.05153/) (2025)
- [Scaling Image and Video Generation via Test-Time Evolutionary Search](https://mlsanity.com/paper/2505.17618/) (2025)
- [Demystifying Video Reasoning](https://mlsanity.com/paper/2603.16870/) (2026)
- [ScalingNoise: Scaling Inference-Time Search for Generating Infinite Videos](https://mlsanity.com/paper/2503.16400/) (2025)
- [Can Test-Time Scaling Improve World Foundation Model?](https://mlsanity.com/paper/2503.24320/) (2025)
- [Generative View Stitching](https://mlsanity.com/paper/2510.24718/) (2025)
- [Target-Bench: Can Video World Models Achieve Mapless Path Planning with Semantic Targets?](https://mlsanity.com/paper/2511.17792/) (2025)

## Built on by (most cited first, 4 of 4)

- [VideoCoCo: Code-as-CoT for Physically-Consistent Video Generation via an Agentic Dual-Engine System](https://mlsanity.com/paper/2607.27380/) (2026)
- [CachedSearch: Training-Free Cached Exploration for Test-Time Search in Video Diffusion](https://mlsanity.com/paper/2607.23159/) (2026)
- [Agentic Visual Generation: From Generative Models to Agentic Control](https://mlsanity.com/paper/2609.06758/) (2026)
- [ProAR: Learning Prospective Reasoning with Autoregressive Video Models](https://mlsanity.com/paper/2610.03664/) (2026)

## Abstract (arXiv)

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.