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

Yaniv Hassidof, Adir Morgan, Yilun Du, Kiril Solovey · 2026

Read Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning by Yaniv Hassidof, Adir Morgan, Yilun Du, Kiril Solovey (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16863.txt.

Introduction

Hassidof's team argues that outside search beats inside search for long diffusion planning. Layered diffusion models denoise paths toward an answer, but local conduct alone rarely yields global unity. Inside search explores paths mid-run, costing repeat checks of a heavy model. Their XDiffuser first plans over a state graph as a link oracle, then guides one path with it. It beats diffusion rivals on long tasks, on low-quality data and unseen tasks such as multi-agent teamwork and TSP-style logic.

Catalog record

CREATORYaniv Hassidof, Adir Morgan, Yilun Du, Kiril Solovey
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48204
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16863

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning Yaniv Hassidof, Adir Morgan, Yilun Du, Kiril Solovey 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. Website: https://yanivhass.github.io/XDiffuser-site/ Figure 1 : 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 \blacklozenge , waypoints by \bigstar , and the goal by \blacklozenge . 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. 1 Introduction Learning-based planning is pushing the frontiers of robotic decision-making, extracting effective behavior from static datasets collected by short-horizon, often suboptimal policies. However, scaling these methods to long-horizon tasks such as robotic assembly ( 18 ) , navigation ( 28 ) and infrastructure inspection ( 20 ) remains a central challenge ( 31 ) , as both learned dynamics models ( 26 ) and regressed value-based policies ( 39 ) suffer from compounding approximation errors. Diffusion-based planners ( 17 ) offer an appealing alternative by learning to directly sample a coherent trajectory from the data distribution, thereby casting planning as inference ( 4 ) . Yet, planning-as-inference faces its own limitations in the long-horizon regime. Real-world demonstrations required for training are often short, local, and incomplete due to the monetary, time, and safety constraints of data collection, thus placing long-horizon problems inherently outside the data distribution. To address this limitation, recent approaches leverage compositionality ( 25 ; 23 ) to assemble short-horizon trajectory segments that are mutually compatible into a coherent global long-horizon solution. However, as the horizon grows, compatibility must be maintained over an increasingly long chain of segments, each attempting to maximize its own local likelihood, making the inference process increasingly brittle: the model may generate locally plausible segments that are mutually incompatible, leading to failures in global consistency, task completion, or constraint satisfaction. Figure 2 : XDiffuser decomposes planning into extrinsic search followed by guided intrinsic generation. (1) At training time, a temporal distance representation is used to construct a connectivity graph over sampled dataset states. (2) A task-appropriate graph search is executed, producing a sequence of waypoints representing the graph solution. (3) A pretrained CompDiffuser denoises a smooth trajectory, guided by the waypoints set. We argue that this limitation is not merely a consequence of approximation error during inference, but a fundamental structural limitation of pure planning-as-inference approaches: when the target long-horizon distribution is never observed, local consistency alone is insufficient to guarantee globally-coherent behavior. Our key insight is that these requirements are naturally handled by extrinsic search (i.e., outside of denoising), while diffusion is best suited to synthesizing smooth, dynamically plausible trajectories between compatible states. Based on this view, we introduce the eXtrinsic search-guided Diffuser (XDiffuser), which is visualized in Figure 2 . Concretely, at training time, XDiffuser builds a graph over real trajectory data to produce a sparse, globally consistent scaffold. At test time, XDiffuser first searches this graph scaffold to produce a high-level plan that is then used for guiding a pretrained compositional diffusion planner to generate continuous trajectories that are smooth, likely under the data, and executable. In contrast to prior approaches that perform search inside the denoising process ( 43 ; 24 ; 41 ) , XDiffuser avoids repeatedly querying the model during iterative denoising, making planning substantially more efficient; we discuss this distinction in more detail in the related work. This decomposition between search and denoising yields a simple and modular framework for long-horizon planning. As the search layer operates over a structured graph it naturally supports adaptive horizon selection: the diffusion horizon is inferred from the temporal duration of the selected route, rather than fixed in advance by a heuristic rollout length as in prior methods. Furthermore, since the high-level objective lives in the search procedure, different planning algorithms can be incorporated at test time, enabling extensions beyond standard goal-reaching to settings such as multi-agent coordination or inspection planning (Figure 1 ). Our experimental results (Section 5 ) highlight XDiffuser’s test-time scalability. On the OGBench suite ( 30 ) , XDiffuser exhibits strong long-horizon planning, especially after training on low-quality data, by achieving 98.5% success rate on AntMaze Large Explore—over 70% higher than its base diffusion planner. We then demonstrate strong generalization across task structure while reusing the same pretrained diffuser in two tasks: (i) a multi-agent setting, where the single-agent diffuser is paired with priority-based graph planner to enable coordinated behavior, and (ii) inspection planning, leveraging a TSP-style graph planner. 2 Related Work Planning with Graphs. Planning over explicit graphs is one of the oldest, most widespread paradigms for long-horizon decision making. In robot motion planning, search is often carried out on a graph ( 6 ; 19 ; 29 ) , capturing the problem’s state-space connectivity, to generate efficient collision-free paths. Moreover, state-space graphs are leveraged in obtaining complex behaviors beyond standard goal reaching, such as multi-robot coordination ( 38 ) or inspection planning ( 27 ) . Graph search has been widely combined with reinforcement learning (RL) for long-horizon planning. Prior work plans over graphs of observations or learned landmarks, using image-space graphs ( 34 ; 22 ) , value-guided subgoal search ( 10 ) , or latent landmarks with multi-step edges ( 42 ) . More recently, Graph-Assisted Stitching (GAS) ( 2 ) performs search in a latent temporal-distance space. These approaches decompose long-horizon problems into locally feasible steps, but rely on strong value-based policies to track graph waypoints. However, this abstraction is inherently limited. Graph edges provide only local, approximate feasibility—indicating that transitions are possible or observed—without guaranteeing that sequences of edges form likely trajectories under the data distribution. As a result, individually valid transitions may compose into globally unnatural behaviors ( 42 ) , and shortest-path objectives can favor brittle plans that cut corners or traverse rarely co-occurring states. To address these shortcomings, our graph-guided diffusion approach takes inspiration from robot autonomy pipelines and hierarchical motion planning approaches wherein a high-level graph plan

Read the complete text