Plan First, Diffuse Later:
Extrinsic Graph Guidance for Long-Horizon Diffusion Planning

Yaniv Hassidof¹ Adir Morgan¹ Yilun Du² Kiril Solovey¹

¹Technion ²Harvard

Paper arXiv Code

By leveraging task-specific graph-search mechanisms, XDiffuser enables a pretrained goal-reaching compositional diffuser to solve complex unseen tasks. Left: Waypoints endow local segments with a coherent global structure, strengthening long-horizon goal reaching. The agent is marked by , waypoints by , and the goal by . Middle: Multi-agent goal-reaching AntMaze. Right: XDiffuser performs an inspection planning task when paired with an existing graph-based solver. Points of interest for inspection are marked in red, XDiffuser’s trajectory shown in blue.

Abstract

Compositional diffusion models offer a promising route to long-horizon planning by denoising multiple overlapping sub-trajectories while ensuring that together they constitute a global solution. However, enforcing local behavior over long chains is often insufficient for a coherent global structure to emerge. Recent works tackle this limitation through intrinsic search, which explores multiple paths during the denoising process. While intrinsic search improves global coherence, it comes at the cost of repeated evaluations of an already compute-heavy model.

In this work, we argue that extrinsic search, performed outside the denoising process, offers a more effective mode of exploration for long-horizon planning while naturally enabling the use of classical algorithms to solve unseen combinatorial tasks at test time. Our eXtrinsic search-guided Diffuser (XDiffuser) first computes a plan over a state-space graph—serving as a lightweight local connectivity oracle for the diffusion model. The plan is then used to guide denoising for a single trajectory, effectively offloading the burden of exploration. XDiffuser outperforms diffusion-based baselines on long-horizon tasks, with particularly large gains in the low-quality data regime and on unseen tasks beyond goal-reaching, including multi-agent coordination and TSP-style reasoning.

Key Contributions

Low-Quality Data Robustness

XDiffuser shows significant performance gains even when trained on suboptimal or low-quality datasets, where standard diffusion planners often fail.

Unseen Combinatorial Tasks

By offloading exploration to classical algorithms, XDiffuser naturally generalizes to unseen tasks at test time, such as TSP-style reasoning and multi-agent coordination.

Method: Extrinsic Search Guidance

Traditional diffusion planners use intrinsic search, which is computationally expensive. XDiffuser proposes extrinsic search:

Graph Plan: First, find a path in a lightweight state-space graph.
Guided Denoising: Use the graph path as an extrinsic guide for a single diffusion trajectory.
Efficiency: Avoids repeated model evaluations while ensuring global coherence.

Generalization to Complex Tasks

XDiffuser outperforms diffusion-based baselines on long-horizon tasks, including multi-agent coordination.

Multi-Agent Coordination: XDiffuser effectively manages agent interactions in dense environments.

Local Connectivity: The graph acts as a local connectivity oracle, simplifying the diffusion task.

BibTeX

@article{hassidof2024plan,
  title={Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning},
  author={Hassidof, Yaniv and Morgan, Adir and Du, Yilun and Solovey, Kiril},
  journal={arXiv preprint arXiv:2410.14660},
  year={2026}
}