Temporal Backtracking Search boosts video reasoning from 0.7% to 22.7%

Sejoon Jun and colleagues from MIT present Temporal Backtracking Search (TBS), a novel test-time scaling framework for generative video reasoning. While large language models benefit from scaling compute at inference time, video generation has been stuck in a single-shot paradigm where errors early in the diffusion process propagate irreversibly. TBS shifts the search space from denoising steps to the temporal axis, enabling the model to backtrack and restart from verified correct prefixes. It consists of three core mechanisms: variable-K conditioning to resume from arbitrary clean frames, a temporal process verifier to pinpoint failure points and extract valid restart anchors, and a prefix-based search that reallocates compute toward extending correct trajectories rather than blind resampling.

In rigorous evaluations across algorithmic, navigation, and robotics domains, TBS Pareto-dominates matched-budget Best-of-N (BoN) sampling. Notably, in a strict out-of-distribution (OOD) setting where one-shot generation collapses to 0.7% for BoN, TBS achieves 22.7% accuracy—and every solved episode originates from a restarted branch. This highlights that the local reasoning competence of video models far exceeds what single-shot rollouts reveal. TBS provides a scalable, test-time framework to unlock that latent capability, potentially accelerating applications in autonomous driving, video editing, and physics simulation.