Compositional Diffusion with Guided Search for Long-Horizon Planning

AI summary

Overview

Research area: Robotics / generative-model-based planning (diffusion models, compositional generation, task-and-motion planning), with extensions to text-to-image and text-to-video generation.

Technical level: Advanced. The paper assumes familiarity with diffusion models, score functions, factor graphs, and reinforcement-learning benchmarks, though the central idea can be understood without the math.

One-sentence scope: The paper introduces CDGS, an inference-time search-and-pruning procedure layered on top of compositional diffusion, so that short-horizon generative models can be stitched into coherent long-horizon plans, panoramas, and videos without ever training on long-horizon data.

What This Paper Is About

Long-horizon tasks — multi-step robot manipulation, panoramic images, long videos — are expensive to learn directly because collecting full-length training data is costly or infeasible. A popular workaround is to learn many short-horizon generative models and compose them, but when each short model is multi-modal (many plausible local behaviors), naive composition averages incompatible modes, producing plans that are neither locally feasible nor globally coherent. The goal of this paper is to fix that "mode averaging" failure by searching over combinations of local modes during the diffusion denoising process itself.

Key Contributions

1. Diagnosis and formulation of mode averaging: The paper frames compositional generation as a factor-graph problem built with the Bethe approximation, and shows that when local distributions are highly multi-modal, score-averaging composition (as in prior methods) yields incoherent global plans.

2. CDGS: guided search inside denoising. A population-based search algorithm that operates at every diffusion timestep, drawing a batch of candidate global plans, ranking them, keeping the best, and repopulating — an approach the authors describe as resembling the cross-entropy method.

3. Iterative resampling for local-to-global message passing. Repeated alternation between forward noising and denoising steps lets information propagate across distant segments through their overlaps, described as belief propagation on a chain of factors, so that each local plan is informed by its neighbors.

4. Likelihood-based pruning via DDIM-inversion curvature. A ranking metric J(τ) that measures the curvature of the diffusion trajectory during inversion (Eq. 5); low-likelihood local segments exhibit high curvature and are pruned. The whole method is plug-and-play and applies across robotics planning, panoramic image generation, and long video generation.

Main Findings

• Matches oracle performance on seven robot manipulation tasks. As stated in the abstract, CDGS matches oracle performance on seven robot manipulation tasks and outperforms baselines that lack compositionality or that require long-horizon training data.

• Strong gains on the hardest maze scales (OGBench, Table 1). On PointMaze Giant, CDGS reaches 87 ± 3, versus CompDiffuser (CD) at 68 ± 3, GSC at 29 ± 2, and HIQL at 0 ± 0 — several inverse-RL baselines score 0 ± 0 across the board. On AntMaze Giant, CDGS scores 85 ± 3 versus CD 65 ± 3 and HIQL 21 ± 2. On HumanoidMaze Giant, CDGS scores 55 ± 3 versus CD 64 ± 4 and HIQL 12 ± 2. On HumanoidMaze Large, CDGS scores 74 ± 2 versus CD 72 ± 3 and HIQL 31 ± 3.

• The Scene (play data) result is a standout. On the OGBench Scene task, CDGS (ours) reaches 51 ± 2, versus GSC 8 ± 2, CD 13 ± 1, and CDGS without pruning 36 ± 6. GCBC scores 5 ± 1 and GCIVL 42 ± 4.

• Pruning contributes measurably. "Ours w/o PR" (CDGS without pruning) is reported alongside CDGS in all OGBench tables, and CDGS typically improves on it on the largest/hardest variants (e.g., PointMaze Giant 78 ± 2 to 87 ± 3; AntMaze Giant 82 ± 1 to 85 ± 3; HumanoidMaze Giant 47 ± 5 to 55 ± 3; Scene 36 ± 6 to 51 ± 2).

• High-dimensional state stitching works (Table 2, AntSoccer). In 17D state space, CDGS scores 69 ± 1 on Arena and 18 ± 2 on Medium, versus GSC (17D) at 65 ± 3 and 12 ± 2 respectively; in 4D, GSC scores 41 ± 4 and 5 ± 2 and CD scores 55 ± 6 and 13 ± 1.

• Hybrid task-and-motion planning without a symbolic planner or LLM. On the TAMP suite (Table 3, success over 50 trials), CDGS (ours) scores 0.64, 0.58, 0.84, 0.48, 0.42, 0.18 across Hook Reach Task 1/Task 2, Rearrangement Push Task 1/Task 2, and Rearrangement Memory Task 1/Task 2 (task lengths 4, 5, 4, 7, 4, 7). It substantially outperforms the same method without pruning (0.24, 0.12, 0.12, 0.00, 0.11, 0.00) and the naive compositional baseline GSC without a task plan (0.18, 0.04, 0.00, 0.00, 0.07, 0.00), and it beats the LLM-prompted planner (LLM-T2M with n = 11 in-context examples: 0.0, 0.48, 0.72, 0.06, 0.0, 0.0) on several tasks. It trails the privileged GSC (Original) with an oracle task plan (0.78, 0.80, 0.88, 0.64, 0.82, 0.48). Notably, CDGS is described as one of only two methods that do not rely on explicit symbolic search or LLM/VLM supervision.

• Performance scales with inference compute. On the most challenging TAMP tasks with planning horizon 7, increasing batch size B and resampling steps U increases task-planning and motion-planning success. Neither B nor U alone is sufficient for overall motion-planning success, which the authors cite as evidence that resampling and pruning are both essential.

• Coherent panoramas (Table 4). Using Stable Diffusion-2.0 to stitch 512 × 512 images into 512 × 4608 panoramas, CDGS achieves Intra-LPIPS 0.59 ± 0.04 (best reported, versus Sync-Diffusion 0.58 ± 0.06, GSC/Multi-Diffusion 0.72 ± 0.08, and CDGS w/o PR 0.61 ± 0.08) and Intra-Style-L of 1.38 ± 0.03 × 10⁻² (best reported, versus Sync-Diffusion 1.39 ± 0.12, CDGS w/o PR 1.97 ± 0.08, and GSC/Multi-Diffusion 2.96 ± 0.24), while also improving Mean-CLIP-S to 32.51 ± 2.66 (versus 31.77, 31.77, and 31.71 for the other three). CDGS matches Sync-Diffusion without any explicit perceptual loss.

• Qualitative failure modes are documented. Figure 5 illustrates mode-averaging artifacts in the hook/cube domain: infeasible transitions where the inhand(hook) precondition is never met for place(hook), and state hallucination where the cube moves under(rack) despite being geometrically infeasible for push(cube, hook).

• Long video generation is claimed but not quantified in the provided content. The abstract and Figure 2 state that CDGS stitches short clips into consistent longer videos, but the truncated content does not report text-to-video numeric results.

Methodology in Plain English

The researchers start from a simple decomposition: instead of learning one gigantic model of an entire long plan, learn a small model of short plan fragments and glue fragments together through their overlapping frames. Gluing is done inside a diffusion model by adding up the score (denoising direction) contributed by each fragment.

That gluing breaks when each fragment has several plausible behaviors — think of a robot that could pull, push, or grasp. Averaging those options produces a physically nonsensical middle ground. The fix is to search rather than just average:

1. Propose many plans at once. At each denoising timestep, generate a batch of B candidate global plans rather than one.
2. Let information travel. Repeatedly noise and denoise the candidates (U resampling steps), so each fragment gets informed by fragments far away in the sequence via the shared overlap variables — the authors compare this to belief propagation.
3. Score and prune. For each candidate, run each local fragment through DDIM inversion and measure how "curved" the denoising trajectory is. Fragments near a real mode of the local distribution produce a smooth, low-curvature path; fragments that fell into the averaged no-man's-land produce high curvature. Multiply the per-fragment scores into a single plan score J(τ), keep the best K candidates, and use them to repopulate the batch.
4. Repeat until the final denoising step, returning the surviving plan.

Because the procedure only wraps around an existing score function, no retraining is needed: the same algorithm is used with a Diffuser-trained local plan model (local plans up to 4 seconds at 20 Hz, composed at inference into up to 10 seconds of motion), a Stable Diffusion-2.0 model for panoramas, and video models.

Why This Matters

Impact on research. The paper reframes compositional generation as a search problem rather than a pure score-averaging problem, and shows a generic inference-time mechanism (resample + prune) that improves long-horizon coherence without long-horizon training data. It connects diffusion planning to classical search, belief propagation, and inference-time scaling, and demonstrates the same machinery across robotics, images, and video — suggesting a domain-agnostic recipe.

Real-world applications:

• Multi-step robot manipulation where a robot must sequence several skills (pulling with a hook, moving an obstacle, relocating a target object) without any task-specific sequence labels.
• Learning from unstructured "play" data or demonstration fragments, where a factory or lab already has short clips but not complete task trajectories.
• Panorama and wide-format image generation for content creation, where separate image patches must agree in style and content.
• Long video generation and stitching of short clips into temporally consistent sequences.

Industry relevance. Any pipeline built on short-horizon generative models — warehouse robotics trained on skill libraries, creative tools generating wide scenes or long clips — can apply CDGS as a plug-and-play inference-time wrapper. The adaptive-compute property (spend more batch size and resampling steps on harder problems) makes the accuracy/cost tradeoff tunable per deployment.

Future Directions

• Scaling behavior on very long horizons. The paper demonstrates planning horizon 7 for the scaling study; whether the method continues to improve, or saturates, at substantially longer horizons is not established in the provided content.
• Quantitative video results. Text-to-video is claimed and visualized but not numerically benchmarked in the available content; a rigorous video evaluation (temporal consistency metrics over hundreds of frames) is a natural next step.
• Compute cost of search. Batch size B, elite count K, and resampling steps U are all tunable, and both B and U are needed for motion-planning success; characterizing the wall-clock cost and finding cheaper approximations to the curvature-based ranking remains open.
• Closing the gap to privileged methods. On Hook Reach and Rearrangement Push, CDGS still trails GSC with an oracle task plan and STAP CEM with a hand-built PDDL domain; narrowing that gap without symbolic supervision is an obvious target.

Target Audience

Robotics and embodied-AI researchers working on long-horizon manipulation, task-and-motion planning, and diffusion-based policies; generative-model researchers interested in compositional generation, inference-time scaling, and long-content synthesis; and practitioners who have short-horizon models or fragmentary data and need coherent long sequences without collecting long-horizon training data. Readers without a diffusion-model background will find the high-level search-and-prune intuition accessible, but the formal sections (score composition, Bethe approximation, DDIM inversion) require prior familiarity.

Authors’ abstract

Generative models have emerged as powerful tools for planning, with compositional approaches offering particular promise for modeling long-horizon task distributions by composing together local, modular generative models. This compositional paradigm spans diverse domains, from multi-step manipulation planning to panoramic image synthesis to long video generation. However, compositional generative models face a critical challenge: when local distributions are multimodal, existing composition methods average incompatible modes, producing plans that are neither locally feasible nor globally coherent. We propose Compositional Diffusion with Guided Search (CDGS), which addresses this mode averaging problem by embedding search directly within the diffusion denoising process. Our method explores diverse combinations of local modes through population-based sampling, prunes infeasible candidates using likelihood-based filtering, and enforces global consistency through iterative resampling between overlapping segments. CDGS matches oracle performance on seven robot manipulation tasks, outperforming baselines that lack compositionality or require long-horizon training data. The approach generalizes across domains, enabling coherent text-guided panoramic images and long videos through effective local-to-global message passing. More details: https://cdgsearch.github.io/