Research map / Probabilistic and scientific modeling / Molecules and proteins
Fast Monte Carlo Tree Diffusion: 100× Speedup via Parallel and Sparse Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Fast-MCTD, which speeds up Monte Carlo Tree Diffusion via parallel rollouts with delayed tree updates and redundancy-aware selection plus sparse planning over temporally subsampled trajectories, reporting up to ~100x speedup over MCTD.
Problem
Monte Carlo Tree Diffusion (MCTD) achieves strong long-horizon planning but is computationally expensive because tree search is sequential and each rollout requires iterative diffusion denoising over long trajectories.
Approach
Combines parallel MCTD (batched rollouts on a shared tree snapshot with delayed updates and a visitation-count penalty within each batch to avoid redundant expansions) with sparse MCTD (planning over trajectories subsampled every H steps, shortening rollouts and reducing the number of subplans).
Key results
- Fast-MCTD achieves roughly 80-110x planning-time speedup over MCTD on giant PointMaze and AntMaze while keeping 100% success on PointMaze-Giant (3.6s vs 59.2s on medium; 2.4s vs 264.2s on giant).
- Fast-MCTD is faster than Diffuser on some maze tasks (e.g., 2.4s vs 6.4s on PointMaze-Giant), and roughly 10x faster than MCTD on triple-cube manipulation.
- On visual mazes Fast-MCTD is 25-60x faster than MCTD and achieves 32% success on large mazes vs 2% for MCTD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| combine parallel rollouts and sparse trajectory planning | MCTD · PointMaze giant | planning time (sec.): 264.2 ± 33.8 -> 2.4 ± 0.1 | Helped |
| combine parallel rollouts and sparse trajectory planning | MCTD · AntMaze giant | success rate (%): 94 ± 9 -> 90 ± 16 | Mixed |
| combine parallel rollouts and sparse trajectory planning | MCTD · Visual maze large | success rate (%): 2 ± 6 -> 32 ± 19 | Helped |
| combine parallel rollouts and sparse trajectory planning | MCTD-Replan · Robot manipulation triple | planning time (sec.): 102.0 ± 6.9 -> 9.1 ± 1.8 | Helped |
| add redundancy-aware selection to avoid repeated node expansion (ablation) | P-MCTD · PointMaze giant | planning time (sec.): 18.4 ± 0.9 -> 12.8 ± 2.5 | Helped |
| add redundancy-aware selection (ablation) | P-MCTD · PointMaze medium | planning time (sec.): 6.6 ± 1.0 -> 8.5 ± 1.6 | Hurt |
| add redundancy-aware selection (ablation) | P-MCTD · PointMaze large | planning time (sec.): 7.8 ± 0.6 -> 7.4 ± 1.3 | Hurt |
| set visitation-count weight to 0.0, removing within-batch count sharing (ablation) | P-MCTD · PointMaze giant | planning time (sec.): 12.8 ± 2.3 -> 221.3 ± 109.6 | Hurt |
| increase parallelism degree above 200 (ablation) | Fast-MCTD · maze giant tasks | success rate (%) | Hurt |
| increase trajectory subsampling interval (ablation) | Fast-MCTD · maze giant tasks | planning time | Mixed |
| use interval size H above 20 (ablation) | S-MCTD · PointMaze-Giant and AntMaze-Giant | success rate (%) | Hurt |
| use sparse trajectory abstraction (ablation) | S-MCTD · PointMaze-Large | success rate (%): 100% -> 8% | Hurt |
Surprising findings
- Fast-MCTD is faster than the search-free Diffuser baseline on several tasks despite using tree search.
- Leaf parallelization (expanding multiple children of one node) was worse than the proposed parallelization across tree branches in the giant maze.
Limitations
- Sparse planning degrades on large PointMaze (8% success for S-MCTD) and with coarse intervals H above 20.
- Requires training a separate diffusion model on coarsened trajectories, adding upfront cost.
- Introduces new hyperparameters (parallelism degree, interval size) and relies on high parallel hardware for best gains.
Experimental setup
Datasets: OGBench navigate dataset OGBench cube manipulation datasets OGBench visual antmaze
Benchmarks: OGBench PointMaze OGBench AntMaze OGBench cube manipulation OGBench visual maze
Metrics: success rate (%) planning time (sec)
Baselines: MCTD Diffuser Diffuser-Replan Diffusion Forcing MCTD-Replan
Builds on: Monte Carlo Tree Diffusion Diffuser Diffusion Forcing UCT DDIM
Closest papers by meaning
- Monte Carlo Tree Diffusion for System 2 Planning (ICML 2025 · similarity 0.94)
- Compositional Monte Carlo Tree Diffusion for Extendable Planning (NeurIPS 2025 · similarity 0.93)
- Resisting Stochastic Risks in Diffusion Planners with the Trajectory Aggregation Tree (ICML 2024 · similarity 0.88)
- Tree-Guided Diffusion Planner (NeurIPS 2025 · similarity 0.87)
- Diffusion Tree Sampling: Scalable inference‑time alignment of diffusion models (NeurIPS 2025 · similarity 0.87)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.