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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Diffusion and flow policies for robotics, one of 14 directions in Diffusion models.
- Builds on 30 of its 42 references that are in the map.
- First posted on arXiv 16 May 2026.

## Placed in

- Diffusion models / [Diffusion and flow policies for robotics](https://mlsanity.com/diffusion/diffusion-and-flow-policies-for-robotics/)

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Is Conditional Generative Modeling all you need for Decision-Making?](https://mlsanity.com/paper/2211.15657/) (2022)
- [OGBench: Benchmarking Offline Goal-Conditioned RL](https://mlsanity.com/paper/2410.20092/) (2024)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Search on the Replay Buffer: Bridging Planning and Reinforcement Learning](https://mlsanity.com/paper/1906.05253/) (2019)
- [Motion Planning Diffusion: Learning and Planning of Robot Motions with Diffusion Models](https://mlsanity.com/paper/2308.01557/) (2023)
- [Foundation Policies with Hilbert Representations](https://mlsanity.com/paper/2402.15567/) (2024)
- [Generative Skill Chaining: Long-Horizon Skill Planning with Diffusion Models](https://mlsanity.com/paper/2401.03360/) (2023)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [Horizon Reduction Makes RL Scalable](https://mlsanity.com/paper/2506.04168/) (2025)
- [Inference-time Scaling of Diffusion Models through Classical Search](https://mlsanity.com/paper/2505.23614/) (2025)
- [Generative Trajectory Stitching through Diffusion Composition](https://mlsanity.com/paper/2503.05153/) (2025)
- [Multi-Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2410.03072/) (2024)
- [Hallucinative Topological Memory for Zero-Shot Visual Planning](https://mlsanity.com/paper/2002.12336/) (2020)
- [DiMSam: Diffusion Models as Samplers for Task and Motion Planning under Partial Observability](https://mlsanity.com/paper/2306.13196/) (2023)
- [A Comprehensive Review on Autonomous Navigation](https://mlsanity.com/paper/2212.12808/) (2022)
- [TUM autonomous motorsport: An autonomous racing software for the Indy Autonomous Challenge](https://mlsanity.com/paper/2205.15979/) (2022)
- [Graph-Assisted Stitching for Offline Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2506.07744/) (2025)
- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [Compositional Diffusion with Guided Search for Long-Horizon Planning](https://mlsanity.com/paper/2601.00126/) (2025)
- [Hybrid Diffusion for Simultaneous Symbolic and Continuous Planning](https://mlsanity.com/paper/2509.21983/) (2025)
- [Kinodynamic Motion Planning for a Team of Multirotors Transporting a Cable-Suspended Payload in Cluttered Environments](https://mlsanity.com/paper/2310.03394/) (2023)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Train-Once Plan-Anywhere Kinodynamic Motion Planning via Diffusion Trees](https://mlsanity.com/paper/2508.21001/) (2025)
- [Safe Interval Motion Planning for Quadrotors in Dynamic Environments](https://mlsanity.com/paper/2409.10647/) (2024)
- [Compositional Monte Carlo Tree Diffusion for Extendable Planning](https://mlsanity.com/paper/2510.21361/) (2025)
- [Effective Sampling for Robot Motion Planning Through the Lens of Lattices](https://mlsanity.com/paper/2502.04908/) (2025)
- [Scalable Inspection Planning via Flow-based Mixed Integer Linear Programming](https://mlsanity.com/paper/2603.16593/) (2026)

## Abstract (arXiv)

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. Project website: https://yanivhass.github.io/XDiffuser-site/