💻 computer science

Compositional Diffusion with Guided Search for Long-Horizon Planning

This paper introduces Compositional Diffusion with Guided Search (CDGS), a method that integrates population-based search and likelihood filtering directly into the diffusion denoising process to resolve mode averaging in compositional generative models, thereby enabling coherent long-horizon planning across diverse domains like robot manipulation, panoramic image synthesis, and video generation.

Original authors: Utkarsh A Mishra, David He, Yongxin Chen, Danfei Xu

Published 2026-07-21

📖 8 min read🧠 Deep dive

CC0 1.0

Original authors: Utkarsh A Mishra, David He, Yongxin Chen, Danfei Xu

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to solve a giant puzzle, or asking a computer to paint a massive mural, or even directing a movie that lasts for hours. The problem is that these tasks are too big to learn all at once. It's like trying to memorize an entire encyclopedia in a single night; your brain (or the computer's) just can't hold it all. So, scientists have a clever trick: they break the big job into tiny, manageable chunks. They teach the robot how to pick up a single block, or how to paint one square of a wall, or how to film a five-second clip. These are the "local" experts.

But here is the tricky part: just because you know how to do each small piece perfectly doesn't mean you can stick them together to make a perfect whole. If you try to glue two puzzle pieces together without looking at the picture on the box, you might force them to fit in a way that looks okay up close but makes the whole picture look warped and broken. In the world of artificial intelligence, this is called "mode averaging." It's when a computer tries to be too safe and averages out all its options, resulting in a plan that is a messy, impossible compromise—like a robot arm that tries to grab a cup and a hammer at the same time, or a video where a cat suddenly turns into a dog in the middle of a sentence.

This is where a new paper from researchers at the Georgia Institute of Technology comes in. They are working in the field of generative AI, which is the technology behind computers that can create new images, videos, and plans. Specifically, they are tackling the headache of "long-horizon planning"—figuring out how to string together many small steps to achieve a big goal. They noticed that the old way of stitching these small AI models together often led to those messy, impossible compromises. So, they invented a new method called Compositional Diffusion with Guided Search (CDGS). Think of it as giving the computer a flashlight and a map while it tries to assemble the puzzle, allowing it to peek ahead, check if the pieces actually fit, and throw away the bad ideas before they ruin the picture.

The Problem: When "Average" is the Enemy

To understand what the authors fixed, we first need to understand the mess they found. Imagine you are trying to plan a road trip from New York to Los Angeles. You have a map app that is great at planning short drives, like "New York to Philadelphia" or "Chicago to Denver." If you just ask the app to average the routes for every possible stop, you might end up with a path that goes halfway to Chicago, then suddenly jumps to Denver, then back to Chicago. It's a "mathematical average" of all the paths, but it's a terrible, impossible road trip.

In the world of AI, this happens when the computer tries to combine many different "local" plans. The local plans are often "multimodal," which is a fancy way of saying there are many different valid ways to do a single step. For example, to move a block, a robot could push it, pull it, or lift it. If the computer just averages these options, it might try to do all three at once, resulting in a robot that vibrates uselessly. The old methods tried to fix this by simply averaging the scores of the different possibilities, but the authors found that this approach often produced plans that looked smooth on paper but were physically impossible or logically broken in reality.

The Solution: A Guided Search Through the Fog

The authors propose a new way to handle this, which they call Compositional Diffusion with Guided Search (CDGS). To understand how it works, imagine you are in a dark, foggy forest trying to find a specific clearing. You have a compass (the AI model) that tells you the general direction, but the fog is so thick you can't see the path ahead.

The old method was like taking a step, looking at the compass, and then taking another step, hoping you stay on track. But because the fog is thick, you might drift off into a swamp without realizing it until it's too late.

The CDGS method is different. Instead of just taking one path, it sends out a whole team of explorers (a "population" of candidate plans). At every step of the journey, these explorers do three things:

They Talk to Each Other (Iterative Resampling): The explorers at the front of the line whisper to the ones at the back, and vice versa. This helps the whole group stay aligned. If the front explorer realizes the path ahead is a dead end, they can tell the back explorer to turn around before the whole group gets lost. This ensures that the plan stays consistent from start to finish, rather than having the beginning and the end contradict each other.
They Check the Map (Pruning): The team has a special rule: if a path looks like it's going to lead to a cliff (an impossible transition), they cut it off immediately. They use a clever trick involving the AI's own "memory" of what a good path looks like to spot these dead ends early. They don't wait until the end of the trip to realize they are lost; they prune the bad branches as they grow.
They Pick the Best Path (Selection): After checking the paths, they keep only the best, most promising explorers and send them on to the next step. This is like a survival of the fittest for road trips.

By doing this, CDGS avoids the "mode averaging" trap. Instead of creating a mushy, impossible average, it finds a specific, coherent path that works from start to finish.

What They Found: Robots, Panoramas, and Movies

The authors tested their new method in three very different worlds, and the results were quite promising.

1. The Robot Playground
First, they tested CDGS on robots. They gave the robots tasks like moving a cube from one spot to another, but with a twist: the robot had to use a hook to pull the cube, or move other objects out of the way first. These are "long-horizon" tasks because they require a sequence of many steps.

The Result: In these tests, CDGS performed just as well as the best existing methods, and in some cases, even better. It managed to solve complex puzzles where the robot had to figure out the right order of moves without being explicitly told the steps. The paper suggests that CDGS can handle these tasks without needing massive amounts of new training data, which is a huge win because collecting robot data is slow and expensive.

2. The Panoramic Artist
Next, they tried using CDGS to create giant panoramic images. Imagine taking a photo of a mountain range, but you can only take small pictures of one peak at a time. You have to stitch them together to see the whole view.

The Result: When they used CDGS to stitch these images, the final panorama looked seamless. The mountains matched up perfectly, and the sky didn't have weird glitches. They compared it to other methods that just "averaged" the edges, and CDGS produced much more natural-looking results that kept the style consistent across the whole image.

3. The Movie Director
Finally, they tested it on video generation. They took short video clips (about 50 frames long) and tried to stitch them together to make a long video (up to 350 frames).

The Result: The challenge here is keeping the characters consistent. If a panda is playing a guitar in the first clip, it shouldn't turn into a bear in the second. CDGS managed to keep the subjects looking the same and the motion smooth throughout the long video. While the video quality was slightly lower than a short clip (a trade-off the authors note is common in long videos), it was far more consistent than other methods that let the characters morph and change.

The Bottom Line

The authors are careful to say that this isn't a magic wand that solves every problem instantly. They note that their method relies on having a clear goal (like "move the cube to the green spot") and that it works best when the "local" experts (the small AI models) are already pretty good at their specific jobs. They also admit that their method takes more computer power to run because it has to check many paths at once.

However, the paper strongly suggests that CDGS is a powerful new tool for making AI smarter about long-term planning. By embedding a "search" process directly into the way the AI generates plans, it avoids the messy compromises that have plagued previous methods. Whether it's a robot arm figuring out how to rearrange a messy desk, a camera panning across a vast landscape, or a movie director stitching together a long story, CDGS offers a way to make the whole greater than the sum of its parts, ensuring that the final result is not just a mathematical average, but a coherent, working reality.

Technical Summary: Compositional Diffusion with Guided Search for Long-Horizon Planning

Problem Statement

Generating coherent long-horizon sequences (e.g., robotic manipulation plans, panoramic images, long videos) is a critical challenge. While generative models like diffusion models have shown promise, monolithic models struggle to generalize beyond their training horizons and are data-expensive to train on full-sequence data. Compositional approaches, which stitch together short-horizon local distributions to form global plans, offer a data-efficient alternative. However, these methods face a fundamental limitation known as mode averaging.

When local plan distributions are highly multimodal (containing many feasible but distinct local behaviors), naive compositional sampling (e.g., score averaging) tends to average incompatible modes. This results in global plans that are neither locally feasible nor globally coherent, often manifesting as "hallucinated" transitions or infeasible state sequences that violate the underlying physics or logic of the task. Existing methods often sidestep this by relying on explicit task skeletons or constraint graphs, limiting their flexibility.

Methodology: Compositional Diffusion with Guided Search (CDGS)

The authors propose Compositional Diffusion with Guided Search (CDGS), a framework that embeds a guided search mechanism directly into the diffusion denoising process. Instead of naively averaging scores, CDGS treats the generation of a long-horizon plan as a search problem over the space of local mode sequences.

The method operates at every denoising timestep $t$ and consists of two primary components integrated into a population-based sampling loop:

Iterative Resampling for Global Consistency:
Standard compositional sampling often fails to propagate information across distant segments of a plan. CDGS addresses this by applying iterative resampling (inspired by belief propagation). At each timestep, the algorithm alternates between forward noising and denoising steps ( $U$ iterations). This allows the score network's predictions for a specific segment to incorporate information from distant neighbors via overlapping variables, effectively enforcing global consistency and reducing the likelihood of mode-averaging artifacts.
Likelihood-Based Pruning for Local Feasibility:
To filter out incoherent candidates, CDGS introduces a ranking metric $J(\cdot)$ based on local feasibility. Since exact likelihoods in diffusion models are intractable, the authors leverage DDIM inversion to approximate the likelihood of local plan segments.
- The method calculates a "smoothness" metric $g(y^{(0)})$ based on the curvature of the diffusion trajectory during inversion. High-likelihood samples follow smooth, low-curvature paths, while low-likelihood (infeasible) samples exhibit high curvature as the model struggles to bring them back to the data manifold.
- A global plan ranking metric $J(\tau^{(0)})$ aggregates these local smoothness scores. Plans with high $J$ values (indicating infeasible local transitions) are pruned.
- The algorithm maintains a batch of $B$ candidate global plans, ranks them using $J$ , and retains the top- $K$ "elite" plans to repopulate the batch for the next denoising step.

This process creates a plug-and-play sampler that navigates the exponentially large search space of multimodal distributions without requiring long-horizon training data or explicit symbolic supervision.

Key Contributions

Identification of Mode Averaging: The paper formally identifies and addresses the "mode-averaging" problem in compositional diffusion, where naive score averaging produces invalid global plans from multimodal local distributions.
Guided Search Integration: The authors introduce CDGS, which integrates iterative resampling and likelihood-based pruning directly into the diffusion denoising loop. This allows the model to explore diverse mode sequences while filtering out those that fail local feasibility checks.
Training-Free Scalability: CDGS operates as a training-free inference-time scaling strategy. It improves the performance of existing short-horizon models (e.g., Diffuser, Stable Diffusion, CogVideoX) to handle long-horizon tasks without retraining on long sequences.
Cross-Domain Applicability: The framework is demonstrated to be generalizable across three distinct domains: robotic task-and-motion planning (TAMP), panoramic image synthesis, and long-video generation.

Experimental Results

The paper evaluates CDGS across robotics, image, and video generation tasks:

Robotic Planning (OGBench & TAMP):
- On the OGBench Maze and Scene tasks, CDGS matches or outperforms inverse reinforcement learning baselines (e.g., GCBC, HIQL) and compositional generative baselines (e.g., GSC, CompDiffuser). Notably, it achieves this with significantly less training data requirements.
- In Task-and-Motion Planning (TAMP) benchmarks (Hook Reach, Rearrangement Push, Rearrangement Memory), CDGS substantially outperforms baselines that rely on LLM/VLM prompting or symbolic search (PDDL) when no oracle task plan is provided. It achieves success rates comparable to privileged methods that have access to ground-truth task skeletons.
- Scaling analysis shows that increasing the batch size ( $B$ ) and resampling steps ( $U$ ) improves success rates, confirming the method's ability to leverage additional compute for harder problems.
Panoramic Image Generation:
- Using Stable Diffusion 2.0, CDGS generates coherent 512x4608 panoramas. It matches the performance of Sync-Diffusion (which uses explicit perceptual guidance) in terms of style consistency and prompt alignment, while outperforming Multi-Diffusion (naive score averaging) in maintaining local consistency.
Long-Video Generation:
- Using CogVideoX-2B, CDGS extends video generation from ~50 frames to 350 frames at 720p. It significantly improves subject consistency and reduces temporal flickering compared to naive composition (Gen-L-Video), maintaining high prompt alignment while extending the temporal horizon.

Significance and Claims

The paper claims that CDGS provides a general pathway for extending the reach of generative models beyond their training horizons. By embedding search within the denoising process, CDGS effectively handles the combinatorial multi-modality inherent in long-horizon planning.

The authors emphasize that their approach:

Solves the Mode-Averaging Problem: It avoids the incoherent outputs of naive compositional sampling by explicitly reasoning about the compatibility of local modes.
Eliminates the Need for Long-Horizon Data: It enables the generation of coherent long sequences using only short-horizon training data, addressing the data scarcity issue in long-horizon domains.
Offers Adaptive Compute: The method scales with inference-time compute (batch size and resampling steps), allowing it to adapt to the difficulty of the planning problem.

The paper concludes that CDGS is a versatile framework applicable to robotics, vision, and video, offering a robust solution for generating globally coherent, locally feasible long-horizon sequences.