PaperlayerView exact revision on arXiv

Source-linked AI summary

Video Models Reason Early: Exploiting Plan Commitment for Maze Solving

Kaleb Newman, Tyler Zhu, Olga Russakovsky

arXiv:2603.30043v1cs.CV

TL;DR

Video models can solve spatial reasoning tasks, but how their plans form and why long-horizon maze solving fails remain unclear. The paper studies these dynamics with controlled 2D mazes and introduces ChEaP, which selects promising early plans and chains generations. ChEaP raises long-horizon maze accuracy from 7% to 67% and improves hard-task accuracy by up to 2.5× across two datasets and two video models.

  • Problem

    The paper addresses limited understanding of how video models’ chain-of-frames reasoning emerges during generation and how reliably their latent capabilities can be elicited.

  • Method

    The paper analyzes intermediate denoising trajectories on controlled 2D mazes and introduces ChEaP, combining early plan selection with chaining across sequential generations.

  • Results

    7% to 67%: ChEaP boosts long-horizon maze accuracy, while evaluations span Frozen Lake and VR-Bench across Wan2.2-14B and HunyuanVideo-1.5.

  • Takeaways & Limitations

    Video models possess deeper maze-solving reasoning than standard evaluations reveal, and inference-time scaling can elicit it more reliably by exploring early plans and extending the effective horizon.

  • Takeaways & Limitations

    The verifier assumes privileged access to agent, goal, and obstacle locations in the 2D environment.

Abstract

from arXiv · show

Video diffusion models exhibit emergent reasoning capabilities like solving mazes and puzzles, yet little is understood about how they reason during generation. We take a first step towards understanding this and study the internal planning dynamics of video models using 2D maze solving as a controlled testbed. Our investigations reveal two findings. Our first finding is early plan commitment: video diffusion models commit to a high-level motion plan within the first few denoising steps, after which further denoising alters visual details but not the underlying trajectory. Our second finding is that path length, not obstacle density, is the dominant predictor of maze difficulty, with a sharp failure threshold at 12 steps. This means video models can only reason over long mazes by chaining together multiple sequential generations. To demonstrate the practical benefits of our findings, we introduce Chaining with Early Planning, or ChEaP, which only spends compute on seeds with promising early plans and chains them together to tackle complex mazes. This improves accuracy from 7% to 67% on long-horizon mazes and by 2.5x overall on hard tasks in Frozen Lake and VR-Bench across Wan2.2-14B and HunyuanVideo-1.5. Our analysis reveals that current video models possess deeper reasoning capabilities than previously recognized, which can be elicited more reliably with better inference-time scaling.

1 Introduction

Video models offer a promising but poorly understood form of spatial reasoning in pixel space. Using mazes as a controlled testbed, the paper identifies early plan commitment and develops ChEaP to exploit it and extend reasoning horizons.

  • Motivation: Video models simulate reasoning directly in pixel space, making them suited to spatial tasks such as maze solving and navigation.The paper frames this as chain-of-frames reasoning, where frames act as a visual scratchpad.
  • Early Plan Commitment: Video diffusion models commit to a high-level motion trajectory within the first few denoising steps, while later steps mainly refine visual details.Decoded intermediate predictions expose this early plan commitment.
  • Mazes as a Testbed: Mazes provide controlled, verifiable tests because their layouts are fixed, solutions can be checked by BFS, and difficulty varies systematically.Conditioning on an input frame separates trajectory reasoning failures from rendering failures.
  • ChEaP: Early Planning Beam Search scores partially denoised seeds with a lightweight verifier and fully denoises only the most promising candidates.This reallocates computation from polishing every seed toward exploring more candidate plans.
  • ChEaP: ChEaP combines early plan selection with chaining, reconditioning on successful traces to decompose long-horizon mazes into sequential sub-problems.The approach addresses the failure cliff for trajectories that are too long for one generation.
  • Results: 7% to 67%: ChEaP boosts long-horizon maze accuracy while matching best-of-N accuracy in 0.3× the diffusion steps and achieving up to 2.5× gains on hard tasks.These evaluations span Frozen Lake and VR-Bench with Wan2.2-14B and HunyuanVideo-1.5.

2 Related Work

Prior work establishes video models’ emergent visual reasoning and diffusion’s coarse-to-fine denoising structure, while recent inference-time methods search or refine diffusion outputs without explaining when maze plans form.

  • Visual Reasoning in Video Models: Video diffusion models have demonstrated zero-shot maze, puzzle, and physical reasoning capabilities, motivating process-aware evaluation beyond final-frame accuracy.Prior work also reports failures under strict long-horizon constraints.
  • Phase Transitions in Diffusion Models: Reverse diffusion follows a coarse-to-fine hierarchy in which global semantic structure crystallizes early and later steps refine low-level details.Cross-attention maps, activations, and stage-specialized denoisers provide empirical support for this structure.
  • Inference-Time Scaling for Diffusion Models: Training-free diffusion scaling methods exploit internal structure through seed search, verifier feedback, particle resampling, tree search, or noise-trajectory optimization.These approaches adapt test-time compute scaling ideas to diffusion models.

3 Mazes as a Controlled Testbed for Studying Reasoning

The paper uses Frozen Lake mazes as a controlled proxy for action planning, enabling precise analysis of when video models commit to solutions, which early signals predict success, and what task properties drive failure.

  • Controlled Testbed: Mazes fix the environment through input-frame conditioning, concentrating task-relevant structure in the agent’s motion trajectory.Trajectories can be extracted from intermediate denoising predictions and compared with exact solution structure.
  • Research Questions: The study asks when models decide their answers, whether early denoising signals predict success, and which structural properties drive failure.These questions target the internal dynamics and failure modes of maze-solving generation.
  • Controlled Testbed: Mazes support automatic verification through ground-truth solutions and expose limitations that output-only evaluations cannot explain.Prior sampling results describe final outputs but do not reveal when plans form or why brute-force sampling plateaus.
  • Experimental Setup: Frozen Lake evaluation varies grid size, obstacle density, and goal placement to control maze difficulty.Norm mazes place the goal at the far corner, while vary mazes use randomly placed goals that often permit shorter solutions.

4 Early Plan Commitment in Video Diffusion Models

Video diffusion models form maze trajectories early in denoising: intermediate clean-video predictions reveal a coarse route that later steps largely preserve while refining visual fidelity. Refinement from the same seed produces limited trajectory diversity, so inference-time compute is better spent screening more seeds.

  • 4.1 Flow matching: The clean-sample estimate x̂_0^(t) is recovered from the intermediate noisy state and velocity prediction, providing the model’s current best guess of the final video.At inference, the flow-matching process integrates the learned velocity field from noise toward a clean video.
  • 4.1 Flow matching: Early trajectory analysis decodes intermediate clean-video predictions to track the maze cells visited before final denoising.The trajectory is the task-relevant structure because the conditioned maze layout remains fixed while only the agent moves.
  • 4.3 Trajectories converge early during denoising: The convergence metric compares flattened spatial motion-energy maps using cosine similarity, where 1.0 means identical motion distribution and 0.0 means no agreement.The metric is scale-invariant and avoids binarization thresholds, making it less sensitive to brightness differences and small-grid cell-overlap noise.
  • 4.3 Trajectories converge early during denoising: 93% mean trajectory convergence is reached by step 5 on 4×4 Frozen Lake mazes for Wan2.2-14B.By step 10, convergence is nearly perfect, indicating that later denoising primarily improves visual fidelity rather than changing the route.
  • 4.4 Early trajectories are diverse across seeds, not refinement: EPBS partially denoises many seeds, scores their intermediate predictions, and fully denoises only the top-K candidates.Under a fixed function-evaluation budget, this reallocates computation from polishing every seed to exploring more candidate trajectories.
  • 4.4 Early trajectories are diverse across seeds, not refinement: Refinement branches from one seed reach at most 25% trajectory diversity, compared with 68% diversity between different seeds.Earlier refinement and larger mazes increase branch diversity, but not to the level produced by changing the initial seed.

5 Trajectory Screening for Efficient Sampling

EPBS exploits early trajectory commitment to screen many candidate plans cheaply, then fully denoises only promising seeds. It improves sampling efficiency and accuracy, while verifier rankings remain reliable across maze difficulty levels.

  • Early Planning Beam Search: EPBS screens trajectories from early denoising steps and fully decodes only the most promising seeds.Intermediate predictions are scored with a lightweight verifier before full decoding.
  • Early candidate exploration: 73 candidates are evaluated at B = 400 with EPBS, compared with 10 for best-of-N.Wan2.2-14B uses T = 40 and EPBS settings τ = 5, K = 1.
  • Efficiency and accuracy: EPBS matches best-of-N accuracy with 3.3× fewer NFEs and outperforms it by ∼10% on average across Wan2.2-14B maze sizes.The largest benefits occur on larger mazes, where broader candidate exploration avoids standard-sampling plateaus.
  • Verifier reliability: The verifier’s top-2 selections succeed 2.2× more often than random on easy mazes and 5.5× more often on hard mazes.Its confidence score has ROC AUC above 0.85 across all maze sizes.
  • Verifier reliability: Verifier top-2 accuracy is within 1.4% of the oracle on all sizes except size 6.When a solution exists in the candidate pool, the verifier almost always identifies it.
  • Ablations: The best probing step depends on maze size: τ = 5 works best for smaller mazes, while τ = 10, 15 is better for larger ones.K = 2 is preferred at low budgets, whereas K = 1 is sufficient at higher budgets.

6 Chaining generations for long-horizon reasoning

EPBS breaks down when a complete maze solution exceeds one generation’s horizon, because path length—not obstacle density—drives difficulty. Chaining shorter generations extends the horizon and substantially improves long-maze success.

  • 6 Chaining generations for long-horizon reasoning: An oracle cannot solve some large mazes because no single generation contains a complete solution.This identifies a structural horizon bottleneck rather than a seed-selection problem.
  • What makes a maze hard?: Path length dominates difficulty: EPBS success correlates with ground-truth path length at r = −0.81 on size 8 and r = −0.79 on size 10.Lake density has near-zero correlation with success, |r| < 0.05.
  • What makes a maze hard?: Success remains reliable through 9-step paths but drops below 10% at 13 steps and beyond.The sharp breakdown occurs around the 10–12-step generation horizon.
  • Chaining: Chaining decomposes long tasks into shorter sub-problems and feeds each generation’s final frame into the next.This extends the effective planning horizon across sequential generations.
  • Results: On Wan 2.2 long mazes with path lengths 10–13, ChEaP raises success from 7.3% with best-of-N and 16.4% with EPBS to 67.3%.On extra-long mazes of 14+ steps, chaining improves EPBS from 2.4% to 14.6%, with smaller gains from compounding chain errors.
  • Results: ChEaP achieves 88.5% pass@2 on Wan 2.2 size-6 mazes, a 33.4% improvement over EPBS and more than double best-of-N’s 43.6%.Across the full evaluation, Table 3 reports EPBS matching BoN at 3.3× fewer NFEs.

7 What Breaks When Video Models Fail?

Video-model failures fall into constraint violations, horizon-limited failures, and degenerate outputs, with different models exhibiting different dominant failure patterns. As trajectories lengthen, Wan2.2 increasingly sacrifices structural fidelity to complete the goal.

  • Failure taxonomy: The failure taxonomy distinguishes constraint violations, horizon-limited failures, and degenerate outputs.Horizon-limited failures follow a plausible route prefix but do not finish within one generation.
  • Model-specific failure patterns: HunyuanVideo is constraint-dominated at every size: 77.5% of size-4 failures are violations, compared with 32.5% for Wan.The pattern suggests that 8-step distillation degrades structural adherence independently of planning horizon.
  • Goal completion versus structure: When trajectories exceed the effective horizon, Wan2.2 may move the gift closer or spawn a second agent near the goal.These behaviors prioritize apparent goal completion over faithful maze traversal.
  • Goal completion versus structure: Controlled decoy mazes reveal a systematic bias toward direct goal completion over obstacle-constrained routes.The model struggles especially when the valid solution must go around a lake.
  • Roles of the methods: Trajectory screening helps when valid solutions are rare among candidates, whereas chaining helps when failures are horizon-limited.The two methods target distinct failure mechanisms.

8 Conclusion

The paper identifies early plan commitment and limited generation length as complementary bottlenecks in video-model reasoning. It argues that inference-time scaling should explore diverse candidates and extend effective horizons, while leaving broader generalization and training questions open.

  • 8 Conclusion: Plans crystallize in the first few denoising steps, favoring diverse candidate exploration over refining individual seeds.The conclusion links early commitment to inference-time scaling strategy.
  • 8 Conclusion: Local planning ability is limited by generation length, making longer context windows, learned pivoting, or improved chaining relevant for harder tasks.These are proposed ways to extend the effective horizon.
  • Open questions: The study focuses on mazes, leaving open whether early commitment and horizon limits extend to non-spatial reasoning modalities.It also leaves open whether training can improve planning reliability or horizon length.

A Implementation Details

The paper extracts cell-level trajectories from generated videos, verifies solutions using goal completion and constraint satisfaction, and ranks intermediate plans with a progress-and-obstacle score. Experiments use image-plus-text conditioning, model-specific schedulers, and maze prompts that enforce static layouts and obstacle avoidance.

  • Trajectory Extraction Pipeline: Trajectory extraction tracks the agent and goal with SAM2.1, then maps agent centroids to grid cells and records unique visited cells.The pipeline initializes tracking from the known start-cell region and checks goal drift during generation.
  • Verification: A video succeeds when its trajectory reaches the goal without entering holes or maze borders, accepting all valid solutions rather than only optimal paths.The criterion permits valid non-optimal routes and tolerates goal completion within grid tolerance.
  • Verifier: The verifier estimates intermediate trajectories with background-difference motion detection, combining final Manhattan distance with the fraction of frames spent on obstacles.Obstacle cells include lakes, traps, or walls depending on the environment.
  • Verifier: The confidence score penalizes obstacle occupancy with α = 0.5, ranks seeds continuously, and fully denoises only the top-K candidates.This score is intended to remain robust to minor tracking noise while rejecting clearly invalid trajectories.
  • Generation Settings: Both models use image-plus-text-to-video conditioning with padded 16:9 inputs and retain their default scheduler hyperparameters.Wan2.2-14B uses UniPC with shift 5.0, while HunyuanVideo-1.5 uses its native eight-step distilled Euler flow-matching schedule.
  • Text Prompts: Prompts specify the player, goal, traversable floor, and forbidden obstacles while requiring a static top-down camera and unchanged maze layout.Frozen Lake prompts emphasize avoiding icy lake cells; VR-Bench prompts distinguish walls or traps from the floor.

B.1 Ablation on Probe Step τ

The ablations show that probe-step choice and beam size govern the efficiency of early-plan screening, while matched-accuracy comparisons measure its practical speed advantage. Early trajectory information supports selective full denoising across maze sizes and models.

  • Probe Step τ: τ = 5 reaches peak accuracy at the lowest NFE for size 4, while larger mazes become less sensitive to probe-step choice.Very early probing at τ = 2 underperforms because its intermediate prediction contains insufficient trajectory information; τ = 10 is safer for sizes 6–10.
  • Beam Size: K=2 provides the best beam-size trade-off, reaching peak accuracy earlier than K=1 without the probe-count penalty of larger beams.At low budgets, larger beams overlap because limited compute leaves little room for additional full completions.
  • Compute Accounting: EPBS probes cost τ denoising steps plus VAE decoding and verifier scoring, while completions run the remaining T−τ steps before final decoding.For sizes 4–6, τ = 5 gives 1.2-minute probes and 6.9-minute completions; for sizes 8–10, τ = 15 gives 3.1-minute probes and 5.0-minute completions.
  • Efficiency: 1.1–3.2× wall-clock speedup is achieved by EPBS at matched accuracy, with the largest advantage on small mazes.At NFE = 120, EPBS accuracy matches baseline performance requiring NFE = 120–400, and timings include the full pipeline.
  • Cross-Model Commitment: Wan2.2-14B and HunyuanVideo-1.5 both show convergence rising sharply early in denoising and then plateauing.Convergence is measured by cosine similarity between intermediate and final motion-energy maps, which is more robust than discrete cell overlap on larger grids.

C.2 HunyuanVideo-1.5 Analysis

HunyuanVideo-1.5 exhibits early plan commitment and path-length-limited performance, while diagnostic mazes separate horizon failures from perception failures. Its verifier remains useful, but weaker early predictions reduce selection gains.

  • Path-Length Difficulty: r=−0.40, −0.77, and −0.77 correlations link success to path length for HunyuanVideo on sizes 4, 6, and 8, respectively.Path length is the primary difficulty axis in the HunyuanVideo analysis.
  • Planning Horizon: HunyuanVideo drops to near-zero success beyond 9 cells, earlier than Wan2.2, which retains 46% at path lengths 10–12.Wan2.2 falls to 9% at path lengths 13–15, while HunyuanVideo’s shorter horizon makes size-10 evaluation near-zero.
  • Verifier Reliability: 46.4% top-2 precision on size 4 gives the verifier a 1.8× gain over random selection, with gains declining to 1.7× and 1.3× on sizes 6 and 8.The weaker gains relative to Wan are consistent with noisier eight-step intermediate predictions carrying less discriminative trajectory information.
  • Decoy Mazes: 6% of decoy seeds succeed and EPBS solves 1 of 4 decoy mazes, because visually adjacent goals induce illegal lake shortcuts despite short valid paths.Decoy failure is characterized as perception-limited rather than horizon-limited.
  • Lake-Heavy Mazes: EPBS solves all 4 lake-heavy mazes with 69% per-seed success, showing that extreme obstacle density does not fundamentally break navigation.These mazes force a single narrow corridor through more than 75% lake tiles.
  • Detour Mazes: On size-4 detours, 29% of seeds succeed and EPBS solves both mazes, but no size-6 seed solves the 12-move detour.The verifier rejects shortcuts through the lake, whereas the 12-move case exceeds the model’s effective planning horizon.
  • Failure Regimes: The diagnostics distinguish horizon-limited detours from perception-limited decoys, while EPBS helps only when valid seeds exist in the candidate pool.This boundary limits what seed selection can recover from systematic generation failures.

D.1 Early Commitment Gallery

The gallery provides visual evidence that trajectories become stable early across maze sizes, models, textures, and chained generations. Later denoising primarily refines rendering, while chaining extends planning beyond a single generation.

  • Wan2.2 Early Commitment: τ=5 predictions already reveal stable routes across Wan2.2 mazes from size 4 through size 10.Later denoising sharpens visual details or cell-level precision without changing the overall planned trajectory.
  • HunyuanVideo Early Commitment: HunyuanVideo-1.5 commits to its trajectory by step 3 despite using an eight-step distilled schedule.This mirrors Wan2.2’s early commitment under a shorter inference schedule.
  • Cross-Domain Generalization: Early commitment persists on VR-Bench across brown/tan, blue/teal, and purple/blue maze textures.The harder maze_1 example retains its coarse τ=5 trajectory through final generation, while maze_2 is largely noise at τ=2.
  • Wan2.2 Chaining: Chained Wan2.2 generations stitch multiple segments to solve longer Frozen Lake, VR-Bench, and trapfield paths.High lake density and trap cells are handled across multiple segments rather than within one generation.
  • HunyuanVideo Chaining: Chaining extends HunyuanVideo’s effective planning horizon by stitching pivot and subsequent segments into complete solutions.Examples include size-4 and size-6 mazes with 65–80% lake density.
  • Failure Modes: Failure galleries include constraint violations, degenerate static motion, and horizon-limited trajectories that stop or exhaust frames before reaching the goal.Constraint failures span Frozen Lake and VR-Bench, while horizon failures can follow a legal prefix or a legal but suboptimal route.
Loading 2603.30043v1…