Compositional Monte Carlo Tree Diffusion for Extendable Planning
Jaesik Yoon, Hyeonseo Cho, Sungjin Ahn
Monte Carlo Tree Diffusion (MCTD) has emerged as a powerful framework for long-horizon planning, combining the structured exploration of tree search with the generative flexibility of diffusion models. However, MCTD remains limited by the trajectory lengths observed during training, restricting its effectiveness on tasks requiring extended reasoning. To address this, we propose Compositional Monte Carlo Tree Diffusion (C-MCTD), a novel inference-time scaling framework that includes three approaches: Online Composer, Distributed Composer and Preplan Composer. Online Composer extends the MCTD's tree search to stitch the generated plan, and Distributed Composer and Preplan Composer improves Online Composer's scalability through parallel computation and prebuilt plan graphs. Experiments demonstrate that C-MCTD methods significantly outperforms standard MCTD strategies on tasks requiring plans much longer than those seen in training, highlighting the potential of compositional inference-time scaling. Source code will be released upon publication at: \url{https://anonymous.4open.science/r/C-MCTD-CF7F}.