Video Models Reason Early: Exploiting Plan Commitment for Maze Solving

1. Problem Statement

Video diffusion models have demonstrated emergent reasoning capabilities, such as solving mazes and puzzles, by simulating motion directly in pixel space (a "chain-of-frames" approach). However, the internal mechanics of how these models reason during the generation process remain poorly understood. Specifically:

• It is unclear when and how a model commits to a high-level plan during the denoising process.
• Standard inference strategies (like Best-of-N sampling) treat the diffusion process as a black box, wasting computational resources by fully denoising every candidate seed, even those with poor initial plans.
• Current models struggle with long-horizon tasks (complex mazes), often failing due to structural limitations rather than a lack of reasoning ability.

The authors aim to uncover the internal planning dynamics of video models and develop inference-time strategies to elicit deeper reasoning capabilities without retraining.

2. Methodology

A. Controlled Testbed: Maze Solving

The authors use 2D maze solving (specifically Frozen Lake and VR-Bench) as a controlled environment.

• Setup: An agent (e.g., an elf) must navigate from a start point to a goal while avoiding obstacles (lakes/traps).
• Advantage: The maze layout is fixed via conditioning, isolating the model's reasoning (trajectory planning) from rendering failures. Success is verifiable via ground-truth BFS solutions.

B. Core Discovery: Early Plan Commitment

Through analyzing intermediate denoising steps ($\hat{x}_0$ predictions), the authors identified a phenomenon called Early Plan Commitment:

• Observation: Video diffusion models commit to a high-level motion trajectory within the first few denoising steps (e.g., step 5 out of 40).
• Evidence: Trajectory convergence metrics show that by step 5, the motion energy map (agent path) is already 93% similar to the final output. Subsequent steps primarily refine visual fidelity (texture, sharpness) rather than altering the path.
• Implication: The "decision" of the route is made early; refining a single seed further yields diminishing returns for reasoning diversity.

C. Proposed Framework: ChEaP (Chaining with Early Planning)

To leverage this discovery, the authors propose a two-part inference strategy:

1. Early Planning Beam Search (EPBS):

   • Instead of fully denoising $N$ seeds, the model partially denoises a large pool of seeds (e.g., $\tau=5$ steps).
   • A lightweight verifier scores these intermediate $\hat{x}_0$ predictions based on goal progress and obstacle avoidance.
   • Only the top-$K$ promising seeds are fully denoised to completion.
   • Benefit: Explores a much wider search space of candidate plans within the same compute budget.

2. Chaining for Long-Horizon Reasoning:

   • The authors found a "sharp failure threshold" at ~12 steps; models cannot solve paths longer than this in a single generation due to horizon limitations.
   • Chaining: Decomposes long mazes into shorter sub-problems. The final frame of a successful short segment becomes the conditioning image for the next segment.
   • This extends the effective planning horizon beyond the native generation window.

3. Key Contributions

1. Mechanistic Insight: Demonstrated that video diffusion models exhibit early plan commitment, where the semantic motion plan is fixed in the first 10–15% of denoising steps, while later steps only refine visual details.
2. Failure Analysis: Identified that path length, not obstacle density, is the primary predictor of difficulty. Models fail on long mazes not because they cannot plan, but because the generation horizon is too short to express the full solution.
3. Inference-Time Algorithm (ChEaP): Introduced a training-free method that combines EPBS (efficient seed selection) and Chaining (horizon extension).
4. Verifier Design: Developed a lightweight trajectory verifier that can reliably predict final success based on early, blurry intermediate frames.

4. Results

The method was evaluated on Wan2.2-14B and HunyuanVideo-1.5 across Frozen Lake and VR-Bench (480+ mazes).

• Efficiency: EPBS achieves accuracy comparable to standard Best-of-N (BoN) sampling with 3.3× fewer function evaluations (NFEs).
• Accuracy Gains:
  • Long-Horizon Mazes: ChEaP improved success rates on long mazes (path length >10) from 7% to 67%.
  • Hard Tasks: Achieved up to 2.5× accuracy gains on difficult tasks in VR-Bench.
  • Overall: Improved accuracy from 7% to 67% on long-horizon mazes and by 2.5× on hard tasks overall.
• Failure Modes:
  • Wan2.2: Primarily fails due to "horizon limits" (running out of frames) on easy/medium mazes, shifting to "constraint violations" (cheating by moving the goal) only on very hard mazes.
  • HunyuanVideo: More prone to constraint violations (structural adherence issues) across all sizes, likely due to step-distillation.

5. Significance

• Redefining Video Model Capabilities: The paper argues that current video models possess deeper reasoning capabilities than previously recognized. Their failure on complex tasks is often a bottleneck of inference strategy (how we sample) and generation horizon, not a lack of inherent reasoning.
• Efficient Inference: It challenges the "brute-force" approach to diffusion sampling. By recognizing that reasoning happens early, compute can be reallocated to explore more candidates rather than refining fewer ones.
• Generalizability: While tested on mazes, the principles of early plan commitment and horizon extension via chaining are applicable to broader spatial reasoning, robotics navigation, and long-horizon video generation tasks.
• No Retraining Required: The proposed ChEaP framework is a "plug-and-play" inference-time scaling method, offering immediate performance boosts for existing off-the-shelf video models.