# Fast Monte Carlo Tree Diffusion: 100x Speedup via Parallel Sparse Planning

arXiv: https://arxiv.org/abs/2506.09498 · HTML: https://mlsanity.com/paper/2506.09498/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion and flow policies for robotics, one of 14 directions in Diffusion models.
- Builds on 26 of its 37 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Placed in

- Diffusion models / [Diffusion and flow policies for robotics](https://mlsanity.com/diffusion/diffusion-and-flow-policies-for-robotics/)

## Builds on (most cited first, 26 of 26)

- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Diffusion Models Beat GANs on Image Synthesis](https://mlsanity.com/paper/2105.05233/) (2021)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [Diffusion Forcing: Next-token Prediction Meets Full-Sequence Diffusion](https://mlsanity.com/paper/2407.01392/) (2024)
- [Diffusion Policies as an Expressive Policy Class for Offline Reinforcement Learning](https://mlsanity.com/paper/2208.06193/) (2022)
- [Is Conditional Generative Modeling all you need for Decision-Making?](https://mlsanity.com/paper/2211.15657/) (2022)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [OGBench: Benchmarking Offline Goal-Conditioned RL](https://mlsanity.com/paper/2410.20092/) (2024)
- [Inference-Time Scaling for Diffusion Models beyond Scaling Denoising Steps](https://mlsanity.com/paper/2501.09732/) (2025)
- [A General Framework for Inference-time Scaling and Steering of Diffusion Models](https://mlsanity.com/paper/2501.06848/) (2025)
- [TransDreamer: Reinforcement Learning with Transformer World Models](https://mlsanity.com/paper/2202.09481/) (2022)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [Simple Hierarchical Planning with Diffusion](https://mlsanity.com/paper/2401.02644/) (2024)
- [DiffuserLite: Towards Real-time Diffusion Planning](https://mlsanity.com/paper/2401.15443/) (2024)
- [Inference-Time Text-to-Video Alignment with Diffusion Latent Beam Search](https://mlsanity.com/paper/2501.19252/) (2025)
- [What Makes a Good Diffusion Planner for Decision Making?](https://mlsanity.com/paper/2503.00535/) (2025)
- [Dynamic Search for Inference-Time Alignment in Diffusion Models](https://mlsanity.com/paper/2503.02039/) (2025)
- [Diffusion Model Predictive Control](https://mlsanity.com/paper/2410.05364/) (2024)
- [Monte Carlo Tree Diffusion for System 2 Planning](https://mlsanity.com/paper/2502.07202/) (2025)
- [Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search](https://mlsanity.com/paper/1810.11755/) (2018)
- [PlanDQ: Hierarchical Plan Orchestration via D-Conductor and Q-Performer](https://mlsanity.com/paper/2406.06793/) (2024)

## Built on by (most cited first, 6 of 6)

- [Scale Where It Matters: Training-Free Localized Scaling for Diffusion Models](https://mlsanity.com/paper/2511.19917/) (2025)
- [Diffusion Large Language Models for Black-Box Optimization](https://mlsanity.com/paper/2601.14446/) (2026)
- [Refining Compositional Diffusion for Reliable Long-Horizon Planning](https://mlsanity.com/paper/2605.03075/) (2026)
- [Inference-Time Scaling in Diffusion Models through Iterative Partial Refinement](https://mlsanity.com/paper/2605.19317/) (2026)
- [Can I Have Your Order? Monte-Carlo Tree Search for Slot Filling Ordering in Diffusion Language Models](https://mlsanity.com/paper/2602.12586/) (2026)
- [From Independent to Correlated Diffusion: Generalized Generative Modeling with Probabilistic Computers](https://mlsanity.com/paper/2603.27996/) (2026)

## Abstract (arXiv)

Diffusion models have recently emerged as a powerful approach for trajectory planning. However, their inherently non-sequential nature limits their effectiveness in long-horizon reasoning tasks at test time. The recently proposed Monte Carlo Tree Diffusion (MCTD) offers a promising solution by combining diffusion with tree-based search, achieving state-of-the-art performance on complex planning problems. Despite its strengths, our analysis shows that MCTD incurs substantial computational overhead due to the sequential nature of tree search and the cost of iterative denoising. To address this, we propose Fast-MCTD, a more efficient variant that preserves the strengths of MCTD while significantly improving its speed and scalability. Fast-MCTD integrates two techniques: Parallel MCTD, which enables parallel rollouts via delayed tree updates and redundancy-aware selection; and Sparse MCTD, which reduces rollout length through trajectory coarsening. Experiments show that Fast-MCTD achieves up to 100x speedup over standard MCTD while maintaining or improving planning performance. Remarkably, it even outperforms Diffuser in inference speed on some tasks, despite Diffuser requiring no search and yielding weaker solutions. These results position Fast-MCTD as a practical and scalable solution for diffusion-based inference-time reasoning.