Compositional Monte Carlo Tree Diffusion for Extendable Planning
This addresses the problem of extendable planning in AI for applications requiring long-horizon reasoning, representing an incremental improvement over MCTD.
The paper tackles the limitation of Monte Carlo Tree Diffusion (MCTD) in planning due to training trajectory lengths and lack of global context, proposing Compositional Monte Carlo Tree Diffusion (C-MCTD) to enable reasoning over complete plan compositions, which improves planning efficiency and scalability.
Monte Carlo Tree Diffusion (MCTD) integrates diffusion models with structured tree search to enable effective trajectory exploration through stepwise reasoning. However, MCTD remains fundamentally limited by training trajectory lengths. While periodic replanning allows plan concatenation for longer plan generation, the planning process remains locally confined, as MCTD searches within individual trajectories without access to global context. We propose Compositional Monte Carlo Tree Diffusion (C-MCTD), a framework that elevates planning from individual trajectory optimization to reasoning over complete plan compositions. C-MCTD introduces three complementary components: (1) Online Composer, which performs globally-aware planning by searching across entire plan compositions; (2) Distributed Composer, which reduces search complexity through parallel exploration from multiple starting points; and (3) Preplan Composer, which accelerates inference by leveraging cached plan graphs.