Fast Monte Carlo Tree Diffusion: 100× Speedup via Parallel and Sparse Planning
Authors: Jaesik Yoon
Hyeonseo Cho
Yoshua Bengio
Sungjin Ahn
Venue: NeurIPS 2025 spotlight ()
Keywords: Diffusion
MCTS
Long-term Planning
Offline RL
Goal-conditioned RL
Efficient Planning
Reasoning
Inference-Time Scaling
Primary area: reinforcement_learning
TL;DR: Fast Monte Carlo Tree Diffusion (Fast-MCTD) achieves up to 100× speedup over MCTD through parallel rollouts and sparse trajectory planning, maintaining strong performance in complex long-horizon tasks while being computationally efficient.

Abstract: 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 100× 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.

Fast Monte Carlo Tree Diffusion: 100x Speedup via Parallel Sparse Planning
Jaesik Yoon"
Hyeonseo Cho"
KAIST & SAP
KAIST
jaesik yow.ik..ooookiis.... ac.
hyeonseo. cwwokaist.taeecccc ac.
Yoshua Bengio
Sungjin Ahn KAIST sungj sungjin.ahn@@ele ahn@kaist ac kr
Mila Quebec AI Institute
Université de Montréal
yoshua. bww.ionnnninni... quebee quebec
Abstract
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 promising solution by combining diffusion with tree-based search, achieving state-of of-the-art performance on complex planning problems. Despite its strengths, computational overhead due to the sequential nature tree search and the cost of iterative denoising. To address this, propose Fast-MCTI,, more efficient variant that preserves the strengths of MCTD while significantly improving its speed and scalability. Fast-MCTDD integrates techniques: Parallel MCTD, which selection;
analysis shows that MCTD incurs substantial
enables parallel rollouts via delayed tree updates and redundancy- 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. 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.
Introduction
Diffusion models have recently emerged as a powerful paradigm for trajectory planning, leveraging offline datasets generate complex, high-quality trajectories through iterative denoising [
36
Unlike autoregressive planners that generate trajectories sequentially via forward dynamics 3 10
diffusion-based approaches like Diffuser [12) generate trajectories holistically, mitigating issues such as long-term dependencies and cumulative error.
Despite these advantages, diffusion planners often struggle with complex reasoning test time, especially in ang-horizon tasks. They may produce plausible but suboptimal trajectories that fail to accomplish complex goals. To address this, inference-time scaling has emerged promising approach to enhance reasoning by adding computational procedures-suce as verification and
refinement-during inference [16 20
26 35 36
'Equal contribution. Correspondence to Jaesik Yoon and Sungjin Ahn <jaesik. kaist.ac.kr and sungjin.ahn @ kr.s..
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, designing diffusion- method that supports inference-time scaling remains challeng- ing. This primarily due to a fundamental mismatch: while reasoning often requires sequential or causal processing, diffusion models are inherently non-sequential and generate trajectories in non-causal manner by design. As a result, simple strategies such as increasing the denoising depth or employing best-of-N sampling have been shown to offer only limited improvements [3
To address this challenge, Yoon et al. [33] proposed Monte Carlo Tree Diffiusion (MCTD), which planning with sequential search through tree-based reasoning, akin to Monte Carlo Tree Search (MCTS) 7. MCTD adopts Diffusion Forcing [2] as the backbone and reinterprets its block-wise denoising as a causal tree rollout, introducing sequential structure while preserving the global generative strengths of diffusion models. By structuring trajectory generation as a tree search, MCTD enables systematic exploration and exploitation, helping the model escape local optima and discover higher-quality trajectories.
integrates diffusion-basse
While MCTD has demonstrated impressive performance in complex, long-horizon tasks that con- ventional methods fail to solve, further analysis reveals that it suffers from significant computational inefficiencies due to two key bottlenecks: the sequential nature of MCTS, which updates tree statistics after each iteration, and the iterative denoising process inherent diffusion models. Unfortunately, this inefficiency is most pronounced in the very long-horizon settings where MCTD's planning capa- bilities are most beneficial. Thus, improving the efficiency of MCTD is the most critical challenge for establishing it as broadly practical solution for diffusion- based inference- time scaling.
In this paper, we propose Fast Monte Carlo cantly reduces the computational overhead of tree search and iterative denoising while preserving the strong planning capabilities of MCTD. Fast-MCTD integrates two key optimization techniques: Par- allel MCTD (P-MCTD) and Sparse MCTD (S-MCTD). P-MCTD accelerates the tree search process by enabling parallel rollouts, deferring tree updates until multiple searches are completed, introducing aedundancy-awand selection, and parallelizing both expansion and simulation steps. S-MCTD further improves efficiency by planning over coarsened trajectories. using diffusion models trained these compressed representations. This not only reduces the cost of iterative denoising but also lowers overall search complexity by effectively shortening the planning horizon.
Tree Diffusion (Fast-MCTD), framework that signifi-
Experimental results show that Fast-MCTD achieves substantial speedups-up to 100x on some tasks compared standard MCTD, while maintaining comparable superior planning perfor- mance. Remarkably, Fast-MCTD also outperforms Diffuser in inference speed on some tasks, despite Diffuser's 's lack of search and its substantially inferior performance.
The main contributions this paper are twofold. First, we introduce Fast-MCTD, a framework that improves the efficiency of MCTD through parallelization and rollout sparsification. Second, we empir- ically show that Fast-MCTD achieves substantial speedups up to two orders of magnitude- while maintaining strong planning performance, demonstrating its practical effectiveness in challenging long-horizon tasks.
2 Preliminaries
2.1 Diffusion models for planning
Diffuser
12
formulates planning as a generative denoising process over full trajectories, defined as
X
81
ST
(I)
0g
a1
or
where T is the trajectory length and (st, oz) denotes the state and action at time f, respectively. During inference, trajectories are iteratively denoised from noisy samples, effectively reversing a forward diffusion process. Since the learned denoising model alone does not inherently optimize for returns or task objectives, Diffuser incorporates a guidance function Tx(x) inspired by classifier-guidde guided diffusion [8]. Specifically, the guidance function biases trajectory generation towards high-return outcomes by modifying the sampling distribution as:
po (x) (x) (x) exp (Jo
(2)
thus explicitly guiding the denoising process toward optimal trajectories at test time.

---

Diffusion Forcing [2] extends the Diffuser framework by introducing token-level denoising control within trajectories. Specifically, Diffusion Foreing tokenizes the trajectory x, enabling different tokens to be denoised at distinct noise levels. This selective, partial denoising allows the model to generate only the tokens exhibiting higher uncertainty, such as future plan tokens.
2.2 MCTD: Monte Carlo Tree Diffussio
MCTD unifies tree search and diffusion-based planning by integrating three key concepts.
(1) Denoising as tree rollout. Unlike traditional MCTS, which expands trees over individual states, MCTD partitions trajectory into fixed-length subplans xs. x = (x Xs).
each treated as high-level node. It applies remi-autoregressive denoising schedule using Diffusion Forcing, where earlier subplans are denoised faster, conditioning later ones on previous outputs, approximating:
S II ((xx (3b)
x 1(x(xxxx1=11
(3a)
p(x|g)
where 9s is guidance level (weight) for the classifier-guided sampling (Equation 2 This preserves the global coherence of diffusion models while enabling intermediate rollouts akin to MCTS, substantially reducing tree depth.
(2) Guidance levels meta-actions. To address exploration-exploittiii trade-off's in large or continuous action spaces, MCTD introduces meta-actions via guidance schedules. A guidance schedule g (. .9s) assigns discrete control modes-e.g. e.g.. GUIDE or NO LFO_GUIDE-L to each subplan, modulating whether it is sampled from an unconditional prior (Equation 3 or guided distribution (Equation Fp). This allows selective guidance within single diffusion process, enabling flexible trade-off control.
(3) Jumpy demoising as fast simulation. For efficient simulation, MCTD uses jumpy denoising (e.g.. Denoising Diffusion Implicit Models (DDIM) (28) to skip denoising steps and rapidly complete remaining trajectory segments. Given subplans X1:s; the rest &, ks+1 :. is coarsely denoised as: X ~ 1(x X1:s; g), yielding a full trajectory for evaluation.
The four steps of an MCTD round. These components are instantiated through the four canonical steps of MCTS adapted to operate over subplans within diffusion- based planning framework. See for a detailed pseudocode of the MCTD method.
1. Selection. MCTD traverses the from the root leaf using selection strategy like Upper Confidence Boundary of Tree (UCT) [14]. Each node corresponds to a temporally extended subplan, not single state, reducing tree depth and improving abstraction. The guidance schedule g is updated during traversal to balance exploration (NO_GUIDE) and exploitation (GUIDE).
2. Expansion.
Upon reaching leaf, a new subplan x, sampled using the diffusion forcing, conditioned the chosen meta-action dş Sampling may follow an exploratory prior p(x.|X1:e-1) or goal-directed distribution p(x, X1:s-1.92)
3. Simulation. Fast jumpy denoising (c.g., via DDIM) completes the remaining trajectory x after expansion. Although approximate, this is computationally efficient and sufficient for plan evaluation using a reward function rxx).
4. Backpropagation. The obtained reward is backpropagated through the tree to update value estimates and refine guidance strategies for future planning rounds. This enables adaptive,
control of exploration and exploitation.
The planning horizon dilemma
Despite its strong performance on long-horizon and complex planning tasks, MCTD suffers from fundamental computational inefficiency. This is because it requires repeated partial denoising
3

---

PointMaze Medium
PointMaze Giant
AntMaze Medium
AntMaze Giant
100
Success (%)
110x faster
85x faster
60
40
20
100
200
300
100
200
300
100
200
100
200
Planning Time (sec)
Planning Time (sec)
Planning (sec)
Planning Time (sec)
Diffuser
Difuser-Replan
Diffusion Forcing
MCTD
Fast-MCTD
Figure 1: Planning time vs. success rate. As maze size increases, most diffusion- based planners degrade in performance. MCTD maintains high success rates but with long planning times, reflecting the Planning Horizon Dilemma- performance requires longer planning time. Fast-MCTD breaks this trade-off, achieving strong performance with much faster planning.
operations to generate feasible subplans. Worse yet, as the planning horizon increases, the search space grows exponentially, resulting in significantly higher computational cost.
Ironically, the key strength of diffusion based planning- -its capacity for long-horizon reason- ing becomes ing-becomes principal bottleneck when integrated with the inherently sequential nature of Monte Carlo Tree Search. In effect, the very scenarios where MCTD's planning capabilities are most ad- vantageous are also those where it incurs the highest computational cost. We refer to this tension between the global trajectory reasoning of Diffuser and the step-by-step search process of MCTS as the Planning Horizon Dilemma.
More formally, consider diffusion foreing schedule that generates sequence of subplans. Let Nehild denote the branching factor at each tree node, corresponding to the cardinality of the meta-action space. Let Csub be the computational cost of performing partial denoising for single subplan x,. Lastly, let S S be the number of subplans required to reach the goal. Then, the total complexity of identifying a successful trajectory using MCTD is given by:
CMCTD = O child" Csub).
(4)
Although MCTD's exploration-exxllottaaio strategy reduces average-case complexity, its computa- tional cost still grows exponentially with the expected number of subplans 8.
This inefficiency of MCTD is clearly demonstrated in Figure which compares planning time and success rates across two maze environments (point mass and ant robot) and two map sizes (medium and giant). As maze size increases from medium to giant, other diffusion-based planners such as Diffuser [12 and Diffusion Forcing [2] exhibit substantial drops in performance, In contrast, MCTD maintains significant performance advantage due to its strong search capability. However, this ad- vantage comes at a steep computational cost: in medium sized mazes, MCTD requires roughly 8-10x more planning time than Diffuser, which further increases to 30-40x in giant- environments.
Fast Monte Carlo Tree Diffusion
The Planning Horizon Dilemma reveals two primary sources of inefficiency in MCTD: (1) Between- rollout inefficiency partial denoising operations across different rollouts are executed serially, limiting parallelism; and (2) Within-rollout inefficiency - each rollout requires the Diffusion to process long trajectories. leading to substantial computational overhead. To address these challenges, we propose Fast-MCTD, which incorporates two key improvements: Parallel Planning via P-MCTD, to improve concurrency, and Sparse Planning via S-MCTD, to reduce the effective planning horizon. The overall processes are illustrated in Figure
4.1 Parallel planning
Independently parallel MCTD via delayed tree update. We begin by parallelizing all four stages of MCTD through K concurrent rollouts. In this setting, each iteration generates a batch of tree rollouts, each proceeding independently within the shared search tree. To avoid synchronization overhead, adopt delayed tree update strategy: all rollouts operate on shared, fixed snapshot of

---

the tree, and updates to the tree (e.g., value estimates and visitation counts) are applied only after all rollouts in the batch are completed.
While this design allows for efficient parallel execution, it introduces a trade-off. As the batch size increases, the tree statistics used during search become increasingly stale, which can degrade planning performance by reducing the accuracy of selection and value propagation. To address this inefficiency, we propose a mitigation strategy in the following section. We further analyze this trade-off empirically in Section 6.4, identifying the optimal degree of parallelism that balances computational efficiency and search quality.
Redundancy-Awan Selection. While the delayed tree update enables parallel rollouts, it intro- duces critical inefficiency: redundant node selection. That is, multiple rollouts within batch independently select and thus may expand the same node, resulting in duplicated computation and limited exploration diversity. More specifically, this issue arises because the standard node selection is designed for sequential search
policy in SCCTD-Uppe Confidence Bound for Trees (UCT) 14 and does not account for concurrent expansions.
Table I:
Each step time of MCTD
To address this issue, we introduce the Redundancy--ware Selection (RAS) mechanism. Our key observation motivating this design is that the time spent on the Selection step, among the four stages of MCTD, is negligibly small: as shown in Table[] it constitutes only 0.05% time of the MCTD steps. This allows to remove the Selection (and the Backpropagation) step from the parallelization pipeline and instead implement as lightweight serial operation.
on PointMaze-Giaan
MCTD Step
Time (sec.)
Selection
3e-4 (0.05%)
Expansion
0.393 (70.9 %)
Simulation
0.161 (29.0 %)
Backpropagation
le-4 (0.02%)
Specifically, inspired by prior work on parallelized MCTS [7 19 25,, we implement Redundancy-
Aware Selection (RAS) by modifying the standard UCT based selection criterion. During each parallel search phase, we temporarily incorporate an auxiliary visitation count variable N,, which sequentially tracks selections made within the current batch. This variable is reset to zero after the delayed tree update is applied. The resulting selection policy is defined as follows:
log(N: [N; + N.
(i) arg max JEC(S)
Vs + 3
(5)
N₂+ N+NN.u
where (i) denotes the node selection policy from node i, C(i) is the set of child nodes of node i, and V1, .N represent the estimated value and visitation count of node i, respectively. The hyperparameter adjusts the
balance for parallel search: when standard MCTD selection, and higher values of w penalize nodes that have already been selected during the current batch, encouraging other rollouts to explore different parts of the tree.
0, the policy reduces to
Parallel denoising on expansion and simulation. Unlike conventional MCTS, where computa- tional costs primarily stem from simulations, MCTD incurs substantial overhead in both expansion and simulation due to the expensive denoising operations. To enhance computational efficiency, we propose a unified batching strategy, termed parallel denoising, that simultaneously processes multiple subplans chosen by RAS during the expansion and simulation phases. Specifically, we implement a common parallel harpllll_ssplllleeeeeeeeeeleelll subplan interface that batches denoising steps by scheduling noise levels and synchronizing DDIM (28 updates. To handle variable-length subplans and different guidance levels, subplans are zero-padded and packed into uniformly shaped tensors, enabling high-throughput parallel execution on GPUs
4.2 Sparse planning
Another key contributor to the Planning Horizon Dilemma is the within-rollout inefficiency, wherein the cost of denoising increases with length of the rollout trajectories. This inefficiency persists even with the parallelization improvements introduced by P-MCTD. To address this issue, we propose Sparse Monte Carlo Tree Diffussin (S-MCTD). The key idea is to incorporate trajectory coarsening-operete rollouts at a higher level of abstraction, as suggested in prior work [4 into the MCTD framework, thereby reducing the effective rollout length and overall computational cost.
Specifically, prior to training the diffusion model, we construct a dataset of coarse trajectories by subsampling every H steps from the original trajectories, yielding x' [I1, T2H
5

---

Plaasing Horieen
Dunoldng
3o
Xp
Denoliingg
Aia
Schedaleed Expurmiion
Schedaled Expansion)
X1.
X188
(1) Rodundsncy-swwrc Selection (2) Expansion
(3) Simulation
(4) Delayed Thes Update
(a) Parallel MCTD
(b) Sparse MCTD
Figure Two key components of Fast-MCTD. (a) Parallel MCTD accelerates planning by performing batched expansion and simulation on partial denoising tree, followed by delayed tree updates. (b) Sparse MCTD reduces denoising overhead by planning over abstract sub-trajectories. significantly decreasing the number of subplans.
These coarse trajectories are then modeled using a specialized sparse diffusion planner. Owing to the shorter trajectory lengths, the computational cost of denoising each coarse subplan-dence
as Ceaare -ic significantly lower than that of the original fine-grained subplans, Subb Furthermore, the overall search complexity is reduced, as plan- ning now involves approximately H times fewer subplans, i.c., x' = [x'n x'xx x'........x. x sr), where
Algorithm Fast-MCTD
1: Initialize tree T. selected node set S
2:
while not goal reached do
3: Reset N; for all node i in T
S' S/H given the original trajectory length S, as illustrated in Figure 2b In terms of computa-
4: for i = to K do
5:
Select node from T Equation Update S: S U.u.
tional complexity, S-MCTD offers a substantial reduction compared to MCTD (Equation (4)
6:
7: end for
8:
for == 1 S in parallel do
CS-MCTD = O ( (N-S/M Cccorse)
9:
Expand node via SparseExpand Simulate with SumpyiJJumyy end for
(6)
10:
11:
We observe that computational efficiency im-
12:
for i = to K do
proves exponentially with the interval size H.
13:
Backpropagate rewards through T end for end while
However, excessively large intervals may overly abstract the planning task, potentially leading to degraded performance. We empirically investi-
14:
16:
return best node from T
gate this trade-off in Section 6.4
Following prior work x", using heuristic controllers value-based policies and inverse dynamics models 33
12 33
we implement low-level control for executing each coarse subplan
4.3 Integrating Parallel and Sparse MCTD
Finally, we integrate the aforementioned Parallel MCTD (P-MCTD; Section 4.1 and Sparse MCTD (S-MCTD; Section 4.2) approaches into our final proposed method, termed Fast Monte Carlo Tree Diffusion (Fast-MCTD)) We illustrate the details of Fast-MCTD in Algorithm
5 Related work
Diffusion models (7 have demonstrated significant success in long-horizon trajectory planning, particularly pprrs-rewardd settings, by learning generate plan holistically rather than forward modeling [1] 2
12 18 36). Given the computational intensity of the denoising process, many approaches have focused on improving efficiency through methods like hierarchical planning [5] 9] To address the challenge of generating detailed, short-term actions, Chen et al. integrated value- learning policies (30] for low-level control. another direction, Chen et
introduces causal noise scheduling with semi-autoregressiv planning to improve performance in causality-sensinee tasks. More recently, research explored leveraging increased computational budgets inference time to enhance plan quality 33 35 Both Yoon et al.
33 and Zhang et al. 335 employ tree search methods within the denoising process. Yoon al. 33 combines auto-regressive denoising with guidance scale-based action control for complex long- hong-horizon planning, while Zhang al. [35]

---

Table 2: Maze results. Success rates and planning times (#:: std) across PointMaze and AntMaze environments on medium, large giant sized map navigate datasets. Best results are shown strong positive colors, compa- rable ones in mild positives. For planning time, slowest results use strong negatives, and marginally slower ones mild negatives.
Success Rate (%)
Planning Time (sec.)
Env.
Method
medium
large
giant
medium
large
giant
Diffuser
58 =
44 a
0 0
6.6 a 0.1
6.5 #:04 0.1
6.4 a: 0.1
Refuusc-RReplan
60 =
40 +
0 #:0
40.6 #:27
55.1 18
137.8 004
Diffusion Forcing
+
74 +
12.5 =.5
45.6 +
PointMaze
MCTD
100
98 1
100 1:0
59.2
174.6 272
264.2 35.
P-MCTD (Ours)
96
100
100
7.4
7.0
9.8
S-MCTD (Ours)
100
84 #
100
9.7
226.1 1144
18.9 2.
Fast-MCTD (Ours)
100
80 1:
100 1:0
3.6 J 0.6
4.1 0.04
2.4 0.1.1
Diffuser
36 i
14 16
0 0
6,2 1 0.1
6,5 1.0.1
6,5 1
Diffuser-Replan Replan
40 +
26 13
0 d:
60.3 #:42
73.7 = 1.9
193.0 2.04
Diffusion Forcing
90 1 10
57 1
24 12
14.0 1:38
24.1 a 1.8
67.0 3.44
AntMaze
MCTD
100 0
98 4:6
94 1:9
68.0 3.88
132.1 12.7
214.5 11.0
P-MCTD (Ours)
96 #
2,8 0.2
3.1 0.1.1
4.2 #
S-MCTD (Ours)
12.5 0.07
40.1
40.3
Fast-MCTD (Ours)
98
77
90 16
2.2 ::
2.2 8.01
2.5 0.0.1
develops tree search method with learnable energy functions for value estimation, applying it to reasoning tasks such as Sudoku. However, as inference-time scaling in diffusion denoising has only recently been explored, optimizing efficiency in this context remains relatively understudied. Our work addresses this gap by drawing inspiration from established principles for improving efficiency, namely sparse planning and the acceleration of Monte Carlo Tree Search (MCTS).
Monte Carlo Tree Search (MCTS) 7 has long history of success in Decision-makinn domains, particularly when integrated with learned policies or value networks 24 25 It has also been applied to Large Language Models (LLMs) to enhance reasoning required task performances [3] 32 34 To address MCTS's inherent inefficiency proposed, including parallel search methods [19], novel node selection policies [17]. and visited-node
sequential search, various enhancements have been
penalization in parallel searches [25]. Our work adapts these established principles of parallelization and efficient exploration to the unique computational structure of diffusion-basee planners.
Experiments
We evaluate Fast-MCTD using tasks from the Offline Goal-conditioned RL benchmark (OG- Bench) [22]. aligning with the setup in MCTD (33]. These include tasks such as point and ant maze navigation with long horizons, robot arm multi-cube manipulation, and visually and partially observable mazes. In all tasks, we use the same guidance function following MCTD, [(x) = = ||z, - g/|² where I; is the i-th state and is the target goal. This design encourages trajectories that reach the goal as quickly as possible. For consistency and fair comparison, we use this distance-basee based guidance function for all baselines. The weight of J. which serves the guidance level, corresponds to the meta-action of MCTD and MCst.MCTD. Metrics reported are mean success rate (%) and planning time (sec), averaged over 50 runs (5 tasks 10 seeds), including mean + standard deviation. Detailed configurations and control settings are available in Appendix A
Baselines. Besides MCTD, we include Diffuser [1], its replanning variant Diffuser- Replann and Diffusion Forcing (2), which uses the causal noise schedule like MCTD but without explicit search.
6.1 Long-horizon planning in maze
We evaluate our methods' efficiency in extensive horizon scenarios using PointMaze and AntMaze tasks from OGBench (22), requiring up to 1000-step trajectories in medium, large, and giant mazes. Following (33, PointMaze employs heuristic controller [12. and AntMaze uses a learned value- based policy (30 Results in highight that Diffuser and Diffusion Forcing exhibit performance
degradation maze sizes increase, while MCTD maintains effectiveness but at significantly increased
7

---

Table 3: Robot task results. Success rates and planning times (#: std) across increasing task difficulty.
Success Rate (%)
Planning Time i (sec.)
Method
Single
Double
Triple
Single
Double
Triple
Diffuser
23
6.3 1 0.1.1
+ 0.1
6.5 +:
Diffuser-Replan
92 13
12 # 13
4 4
21.4 2.44
71.2 5.1
130.9 i: 11.6
Diffusion Forcing
100
18 11
16 =
2.9 0.2.2
15.2 #.2
15.9 1.2
MCTD-Replan
100 0
78 1I
40 21
9.2 + 0.9
38.8 = 4.7
102.0 + 6.9
P-MCTD-Replan (Ours)
100 ::
80 2:9
50 1:21
2.9 1
6.5 2.3
11.4 288
S-MCTD-Replan (Ours)
100
75 3
42 1:
8.5 0.5
35.7 18.2
58.7 33.0
Fast-MCTD-Replan (Ours)
100
16
3.0
1.7
9.1
S-MCTD
MCTD
steps
start
200
300
goal
Figure 3: Planning visualization. Sparse planning (top row) allows for more effective long-horizon trajectories than the dense (bottom row).
computational costs, illustrating the planning horizon dilemma clearly. For instance, MCTD exceeds 4 minutes to solve PointMaze-Giant.
In contrast, Fast-MCTD demonstrates approximately 80-110x speedups relative to MCTD on giant maps with minimal performance loss. Surprisingly, Fast-MCTD is even faster than Diffuser, which employs straightforward denoising without search. Despite generally superior performance, Fast- MCTD encounters performance degradation on large maps due to sparse diffusion model limitations arising from insufficient start-positic positiosi training data when subsampled every H steps. Nevertheless, Sparse MCTD (S-MCTD) and Parallel MCTD (P-MCTD) achieve notable efficiency gains, in particular, P-MCTD reaches 50x speedup on AntMaze-Giaat Giant.
6.2 Robot arm manipulation
We evaluate efficiency of our methods in compositional planning tasks involving multiple cube manipulations from OGBench (22). Tasks require strategic manipulation sequences, such as stacking cubes in a specific order. High-level planning utilizes diffusion planners, and local actions executed via value-learning policies (30,, enhanced by object-wise guidance and replanning methods 33]
Fast-MCTD maintains or exceeds MCTD performance with significantly improved efficiency. Specif- ically, it shows better efficiency than Diffuser on single and double cube tasks. However, in triple cube tasks, Fast-MCTD is slower than Diffuser due to the increased task difficulty which demands more extensive search. Nevertheless, remains approximately 10x faster than MCTD, underscoring its significant computational advantages.
6.3 Visual planning
To assess efficiency in high-dimensional, partially observable contexts, we evaluate Fast-MCTD using visual maze environments where agents observe RGB image pairs depicting start and goal states 33 Observations are encoded with a pretrained VAE [13], actions derived via inverse dynamics models in latent space, and approximate positional hints provided by pretrained estimators.
As shown in Table 4 Fast-MCTD demonstrates substantial efficiency improvement (25-60x faster than MCTD), even outperforming it on larger mazes. This is because the abstract trajectory planning through Sparse MCTD (S-MCTD) reduces rollout horizon complexity and improves credit assignment in latent transitions MCTD and P-MCTD on larger maps. By integrating both sparse and parallel search, Fast-MCTD maximizes these efficiency gains. Replanning further enhances MCTD but at significant computa- tional cost, whereas Fast-MCTD achieves superior performance with relatively minimal overhead, comparable Diffuser-Replant Replan.
[18] shown in Figure 3 Consequently, S-MCTD surpasses both

---

Table 4: Visual maze results. Mean (%) and planning time (seconds) medium and large
Success Rate 1 (%)
Planning Time (sec.)
Method
Medium
Large
Medium
Large
Diffuser
+ 13
7.0 0.3
6.7 + 0.3
Diffuser-Replan
# 10
0 2:0
26.4
+ 1.0
26.0 = 0.4
Diffusion Forcing
66 d:
8
14.5 1.7
17.1 #.7
MCTD
76 + 20
2 6
98,8
+ 36.2
320.1 7.7.
P-MCTD (Ours)
86
0 0
6.8
7.6 4
S-MCTD (Ours)
16
40.1
4: 32.0
168.7 4: 46.2
Fast-MCTD (Ours)
: 18
32 +: 19
4.0 0.2
5.1 # 0.3
MCTD-Rephee
31 10
129.8
53.1
419.7
49.1
Fast-MCTDD-Reye Repllnn (Ours)
84 28
38 1:30
14.3
2.3
26.7 1: 3.7
Table 5: Planning times for Redundancy-Aie -warre vs. Unaware Selec- tion in PointMaze.
Planning time with different weight in PoiniMaze-Giami
Table 6:
Planning Time & (sec.)
Weight (w)
Planning Time (sec.)
Redundancy
Medium
Large
Giant
0.0
221.3 +: 1096
0.1
14.0 25
Aware
8.5 1.6
7.4 # 1.3 7.8 2.06
12.8 + 2.5
1.0
12.8 23
Unaware
6.6 + 1.0
18.4 0.09
5.0
12.5 2.1
6.4
Ablation studies
Redundancy-unavan selection. To assess the impact of Redundancy-Awerr Selection (RAS) on planning efficiency, we ablate the constraint that prevents multiple rollouts from expanding the same node simultancously. this redundancy-unavie counts but repeatedly expand the same node. Table [ableeseeesentt planning times of P-MCTD across different PointMaze sizes, measured under a generous computational budget with 100% success rates. By avoiding repeated expansion of the same node, RAS prevents excessive exploitation, which can dominate exploration when paths are harder to discover, especially in larger environments. In smaller environments, simple exploitation can still be effective, making the benefit of RAS less pronounced.
selection variant, rollouts still share visitation
Visitation count weight. We further investigate the impact RAS during the selection phase by ablating the visitation count weight from Equation (). which balances exploration and exploitation in parallel search. Vable(6]pesent the planning times in the PointMaze-Gaing for different to values. In the standard UCT setting (w 0), which lacks visitation count sharing, planning times exceed 220 seconds with high variance. In contrast, with RAS, planning times remain consistently low (12-14 seconds) across wide range of values, suggesting that redundancy awareness is more critical than fine-tuning this hyperparameter.
Parallelism degree and interval size. We also study key hyperparameters: the parallelism degree (number concurrent rollouts) and the subsampling interval size (steps skipped between coarsen states). Figure shows the performance of Fast-MCTD in different configurations. Increasing the parallelism degree initially reduces planning time through efficient parallelization, but high degrees (above 200) degrade success rates due delayed tree updates and selection redundancy, For interval size, larger interval sizes significantly boost efficiency but risk performance loss if the abstractions become coarse for accurate low-level control (33]
7 Limitations and discussion
While our Fast Monte Carlo Tree Diffusion framework significantly enhances performance, it in- troduces certain trade-offs. Optimal parallelization for P-MCTD benefits from nigh-performance computing, yet substantial efficiency gains are achievable even with modest parallel capabilities on standard hardware. Our approach also introduces new hyperparameters, namely the parallelism degree and interval size. However, ablation studies confirm the robustness of these parameters and

---

Parallelism Success Rate
Interval Success Rate
Parallolism Planning Time
Interval Planning Time
Success (%)
100
Planning Time (sec)
10"
60
10
100
200
300
10
20
30
40
50
100
200
300
0
10 20
30 40 50
Parallelism Degree
Interval Size
Parallelism Degree
Interval Size
PointMaze--Gant
AntMaze-Giant
Figure Ablation studies for parallelism degree and interval size. Success rates (%) and planning time (seconds) as the parallelism degree and interval size increase for maze giant tasks.
provide clear guidelines for their effective configuration. Furthermore, our sparse planning approach requires training dedicated diffusion model on coarsened trajectories, which represents additional upfront computational cost. The computational advantages of Fast-MCTD substantially outweigh the minor overhead of parameter tuning and additional training, enabling the practical deployment of Liffusion-based planning in time-sensitive applications where it was previously infeasible.
8
Conclusion
We introduced Fast Monte Carlo Tree Diffusion (Fast-MCTD), a framework that resolves the crit- ical efficiency bottleneck of Monte Carlo Tree Diffusion (MCTD), state-of-the-ar method for inference-time scalable planning- By synergizing parallelized tree search (P-MCTD) with sparse trajectory abstraction (S-MCTD), our method unlocks significant inference-time acceleration without compromising planning quality. Our experiments demonstrate that Fast-MCTD achieves up to a 100-fold speedup over prior work challenging long-horizon tasks, such as maze navigation and robotic manipulation, while maintaining or even improving performance. These gains are driven by algorithmic innovations like search-aware parallel rollouts and voarse-to-fine diffusion process over abstract plans. While Fast-MCTD alleviates key efficiency bottlenecks, future work could explore further improvements by integrating learned value function. Ultimately, findings demonstrate that test-time scalability and structured reasoning are not mutually exclusive, opening new avenues for developing fast, deliberative agents in nigh-dimensional domains.
Acknowledgments and Disclosure of Funding
We are grateful to Doojin Baek and Junyeong Park for their insightful discussions and valuable assistance with this project. This research was supported by GRDC (Global Research Development Center) Cooperative Hub Program of Korea (NRF) funded by the Ministry Science and ICT (MSIT) and Basic Research Laboratory through the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) and Institute of Information communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS- 2024-00509279, Global AI Frontier Lab). YB acknowledges the support from CIFAR, NSERC, the Future of Life Institute.
through the National Research Foundation
Program (No. RS-2024-00414822
References
[1] Anurag Ajay, Yilun Du, Abhi Gupta. Joshua B. Tenenbaum, Tommi S. Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision making? In International Conference Learning Representations, 2023.
[2] Boyuan Chen, Diego Martí Monsó, Yilun Du, Max Simchowitz, Russ Tedrake, and Vincent Sitzmann. Diffusson forcing: Next-token prediction meets full-sequence diffusion. Advances in Neural Information Processing Systems, 37:24081-24 -2415., 2024.
[3] Chang Chen, Yi-Fu Wu, Jaesik Yoon, and Sungjin Ahn. Transdreamer: Reinforcement learning with transformer world models, arXiv preprint arXiv:2202.0944 2022.
10

---

[4] Chang Chen, Junyeob Back, Fei Deng, Kenji Kawaguchi, Caglar Gulcehre, and Sungjin Ahn. PlanDQ: Hierarchical plan orchestration via d-conductor and q-performer. In International Conference Machine Learning. 2024.
[5] Chang Chen, Fei Deng, Kenji Kawaguchi, Caglar Gulcehre, and Sungjin Ahn. Simple hier- archical planning with diffusion. In International Conference on Learning Representations. 2024.
[6] Chang Chen, Hany Hamed, Doojin Back, Taegu Kang, Yoshua Bengio, and Sungjin Ahn. Extendable long-horizon planning via hierarchical multiscale diffusion. arXiv preprint urXiv:2503.20102, 2025.
[7] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In H. Jaap van den Herik, Paolo Ciancarini, and H. H. L. M. (Jeroen) Donkers, editors, Computers and Games, pages 72-83, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg. ISBN 978-3-540- 75538-8.
[8] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. Advances in neural information processing systems, 34:8780-8794, 2021.
(9] Zibin Dong, Jianye Hao, Yifu Yuan, Fei Ni, Yitian Wang, Pengyi Li, and Yan Zheng. Diffuserlite: Towards real-time diffusion planning. Advances in Neural Information Processing Systems, 37: 122556-122583, 2024.
[10] David Ha and Jürgen Schmidhuber. World models. arXiv preprint arXiv: 10122, 2018.
[11] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. arXiv preprint urXiv:1912.01660 1912.0160,, 2019.
[12] Michael Janner, Yilun Du, Joshua Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, 2022.
[13] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
[14] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European Conference on Machine Learning, 2006.
[15] Wenhao Li, Xiangfeng Wang, Bo Jin, and Hongyuan Zha. Hierarchical diffusion for offline decision making. In International Conference on Machine Learning, pages 20035-20064. PMLR, 2023.
[16] Xiner Li, Masatoshi Uehara, Xingyu Su, Gabriele Scalia, Tommaso Biancalani, Aviv Regev, Sergey Levine, and Shuiwang Ji. Dynamic search for inference-time alignment in diffusion models. arXiv preprint 2.X3:22503.000333 2025.
[17] Anji Liu, Jianshu Chen, Mingze Yu, Yu Zhai, Xuewen Zhou, and Ji Liu. Watch the unobserved: simple approach parallelizing monte carlo tree search. In International Conference on Learning Representations.
[18] Haofei Lu, Dongqi Han, Yifei Shen, and Dongsheng Li. What makes good diffusion planner for decision making? In The Thirteenth International Conference on Learning Representations, 2025.
[19] Guillaume M, J-B Chaslot, Mark H. M. Winands, and H Jaap Van Den Herik. Parallel monte- carlo tree search. In Computers and Games, 2008. https: httttpp:/aapp..smmnniccccchoeooe semanticsccoolarr org Org/CorpusID: 14562666
[20] Nanye Ma. Shangyuan Tong, Haolin Jia, Hexiang Hu, Yu-Chuar Su, Mingda Zhang. Xuan Yang. Yandong Li, Tommi Jaakkola, Xuhui Jia, et al. Inference-time scaling for diffusion models beyond scaling denoising steps. arXiv preprint arXiv:2501.085 009732, 2025.
[21] Yuta Oshima, Masahiro Suzuki, Yutaka Matsuo, and Hiroki Furuta. Inference-time timeenece--ieeeeee text-to-video alignment with diffusion latent beam search. CoRR, 2025.
11

---

[22] Seohong Park, Kevin Frans, Benjamin Eysenbach, and Sergey Levine. Ogbench: Benchmarking offline goal-conditioned In International Conference on Learning Representations, 2025.
[23]
Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. In International Conference on Learning Representations.
[24] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839)6604-66 609, 2020.
[25] David Silver. Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of go with deep neural networks and tree search. Nature, 529(7587):484-488 2016.
[26] Raghav Singhal, Zachary Horvitz, Ryan Teehan, Mengye Ren, Zhou Yu, Kathleen McKeown, and Rajesh Ranganath. general framework for inference-time scaling and steering of diffusion models. arXiv preprint arXiv:2501.0684 2025.
[27] Jascha Sohl-Dicksteins Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International Conference on machine learning, pages 2256 2265. pmlr, 2015.
[28] Jamming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
[29] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
[30] Zhendong Wang, Jonathan J Hunt, and Mingyuan Zhou. Diffusion policies expressive policy class for offline reinforcement learning. International Conference on Learning Representations, 2023.
[31] Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, et al. Towards system 2 reasoning in 1Ims: Learning how think with meta chain-of-though. arXiv preprint arXiv:2501.0444 04662,, 2025.
[32] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in Neural Information Processing Systems, 36, 2024.
[33] Jaesik Yoon, Hyeonseo Cho, Doojin Baek, Yoshua Bengio, and Sungjin Ahn. Monte carlo tree diffuuson for system planning. In Forty-second International Conference on Machine Learning, 2025.
[34] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. Rest-mets*: Llm self-training via process reward guided tree search. 2024.
[35] Tao Zhang, Jia-Shu Pan, Ruiqi Feng, and Tailin Wu. Test-time scalable mets-enhanced diffusion model. arXiv preprint arXiv:2502.01989, 2025.
[36] Guangyao Zhou, Sivaramakrishnan Swaminathan, Rajkumar Vasudeva Raju. Swaroop Guntu- palli, Wolfgang Lehrach, Joseph Ortiz, Antoine Dedieu, Miguel Greeilla,,, and Kevin Murphy. Diffusion model predictive control. arXiv preprint arXiv:2410.053644 2024.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable to "[No]" is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Our proposed method shows the efficiency gain while generally sustaining or sometimes exceeding the baseline performances, which corresponded to the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
13

---

Justification:
We discuss the limitation as separate section in the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each thcoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Ys]]
Justification: We provide the details of the implementation in the appendix including the hyperparameters and benchmark settings.
Guidelines:
14

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The source code is publicly httttpss//ggthuub.c//oobmmo////a
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
mublic//guide//CoeSuuumi www.ssabbsssioosoisoooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https ctt.ps.cc/public//uuu
Codeeuumiiiie wwwbbbbmsssionoooo ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting//etails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the detailed information for the experiments in our appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provide the standard deviation on performance and efficiency evalua-
tion.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All experiments were conducted on a nigh-performane computing server equipped with 8 NVIDIA RTX 4090 GPUs, 512GB system memory, and a 96-thread CPU. Model training required approximately 3-6 hours per model, while inference for each experimental evaluation took approximately up to minutes.
Guidelines:
16

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///war.....cooo/o.///aaalaa
Answer:
[Yes]
Justification:
We checked the NeurIPS Code of Ethics and followed them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:Thi paper presents foundational research in efficient algorithmic approaches for diffusion-based planning methods, which is primarily focused theoretical and com- putational efficiency improvements rather than specific applications with direct societal implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
17

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwpppswiithhaeooo thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
18

---

14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.M for what should or should not be described.
19

---

Initial Observation
Goal
(a) Maze Environment
(b) Robot Cube
(c) Visual Maze
Figure 5: Task Illustrations: (a) long-horizon maze navigation, (b) multi-object robotic manipulation requiring compositional planning, and (c) visual maze planning from raw RGB observations.
A Experiment details
A.1
Computation resources
The experiments conducted system memory, and a 96-thread CPU. Model training required approximately 3-6 hours per model, while inference for each evaluation took up 5 minutes.
equipped with 8 NVIDIA RTX 4090 GPUs, 512 GB of
A.2 Environment details
Following prior work [33. we evaluate our methods (P-MCTD, S-MCTD, and Fast-MCTD) on challenging scenarios from the OGBench [22] goal-conditioned benchmark. These include long- horizon maze navigation, robot arm manipulation, and visual maze navigation, as illustrated in Figure All evaluation tasks were unseen during training, requiring the models to generalize their planning capabilities to novel scenarios at inference time.
A.2.1 Long-horizon maze
To assess performance over long planning horizons, test methods point- mass and ant robot navigation in three increasingly complex environments: medium, large, and giant mazes. The models trained the navigate datasel, which contains long trajectories but lacks specific task information. At inference, the models must leverage their learned dynamics to solve these unseen maze configurations, thereby testing their generalization for complex, long- problems.
A.2.2 Robot arm manipulation
The robot manipulation tasks demand compositional planning to move multiple objects in a specific sequence. For instance, when tasked with stacking objects in predetermined order, the model must generate a coherent plan that adheres to these sequential constraints. As shown in prior work (33], holistic diffusion-based planners often struggle with such compositional tasks without explicit search or reward guidance. We evaluated Fast-MCTD in this domain, focusing improving efficiency within a replanning framework while preserving MCTD's strong compositional planning performance.
A.2.3 Visual maze
Following Yoon et al. [33]. we evaluate performance in high- sigh--imensional, partially observable settings using the Visual Antmaze task from OGBench [22]. In this task, the agent navigates from an initial observation to goal, where both are represented 64 64 RGB images. These images are encoded into an 8-dimensional latent space using a Variational Autoencoder (VAB) [3), providing a compact representation for efficient planning.
20

---

Table 7: Hyperparameter configurations for the Diffuser.
Hyperparameter
Value
Training configuration
Learning rate
2 10
EMA decay
0.995
Precision (training/inference)
32-bit (FP32)
Batch size
Max training steps
20,000
Diffusion & guidance
Beta schedule
Cosine
Diffusion objective
mo-prediction
Guidance scale
0.1
Planming configuration
Planning horizon
Task-dependent (see Sec A.7
Open loop horizon
50 (for replanning)
Model architecture (U-Net)
Depth
Kernel size
5
Channel dimensions
(32, 128, 256)
A.3 Baselines
We compared Fast-MCTD against several liffusion-based planning approaches:
Diffuser [12]
We implemented the standard Diffuser with classifier-guided generation baseline, ensuring comparable guidance mechanisms across all methods.
Diffuser-Replan To strengthen the Diffuser baseline, incorporated periodic replanning (details are in Appendix [A.4). This variant regenerates the entire plan at fixed intervals, allowing it to adapt to intermediate state observations.
Diffusion Forcing
This approach utilizes causal noise scheduling with tokenized trajectories but omits an explicit search mechanism. Its default implementation includes replanning, making it strong comparative baseline.
As our primary baseline, MCTD represents the state-of-the-ar inference- time scaling for diffusion planning. It integrates causal noise scheduling with tree-bases search. While effective, it exhibits significant computational inefficiencies complex planning scenarios.
MCTD X
MCTD-Replan:
This variant applies the replanning strategy (Appendix A.4) to MCTD, allowing it to adapt to intermediate state observations while maintaining high-quality plan- ning. However, this process incurs significant computational overhead compared other baselines, serving as a powerful but costly baseline.
A.4 Replanning strategy
The replanning strategy is applied to our replanning- baselines: Diffuser-Replan, Diffusion Forcing, and MCTD-Replas In this variant, the agent generates full-horizon plan (e.g., 500 steps in length) at each interval but executes only the first steps before replanning from the updated state. This process is repeated until the task is completed.
A.5 Model hy perrpaarrees
We maintain consistency with the hyperparameter configurations from prior work 33 and describe the detailed hyperparameters here enhance reproducibillit. We highlight the key parameters specific to our methods; complete implementation details will be made available.
21

---

Table 8: Hyperparameters for the value-learning policy,
Hyperparameter
Value
Optimizer settings
Learning rate
x 10
Gradient clipping norm
7.0
Learning eta
1.0
Training strategy
Training epochs
2,000
Target steps
10
Data sampling randomness (p)
Reward tuning
cql antmaae
Q-learning details
Max backup
False
Top-k
Table 9: Hyperparameters for the Diffusion Foreing,
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
5 x 10
Weight Decay
1 10-4
Warmup Steps
10,000
Batch Size
1024
Max Training Steps
200.005
Training Precision
16-bit Mixed
Inference Precision
32-bit (FP32)
Model Architecture (Transformer)
Hidden Size
128
Number of Layers
12
Attention Heads
Feedforward Dimension
512
Frame Stack Size
10
Causal Masking
Not Used
Diffusion & Sompling Sertings
Beta Schedule
Linear
Objective
preddcciitioon
Scheduling Matrix
Pyramid
DDIM Sampling 1
0.0
Planning Guidance Settings
Planning Horizon
Task dask-dependent (sec See A.7
Open-loop Horizon
Guidance Scale
3.0 (medium mazes), 2.0 (others)
Stabilization Level
10
A.6 Diffusion model training protocol
We follow the training protocol established by prior diffusion planners 12. Concretely, the model trained on offline trajectory datasets from OGBench [22]. The training objective standard denoising loss (e.g., 1.2 loss), where the model learns to predict the original trajectory xo from noised version. We employ Transformer-based architecture. All hyperparameters, including learning rates and batch sizes, are fully reported in Appendix A.5
22

---

Table 10: Hyperparameters for MCTD and its variants.
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
5 x 10
Weight Decay
1 10
Warmup Steps
10,000
Batch Size
1024
Max Training Steps
200,005
Training Precision
16-bit Mixed
Inference Precision
32-bit (FP32)
Model Architecture (Transformer)
Hidden Size
128
Number of Layers
Attention Heads
Feedforward Dimension
512
Frame Stack Size
10
Causal Masking
Not Used
Diffusion & Sampling Settings
Beta Schedule
Linear
Objective
Jo preddcciiion
Scheduling Matrix
Pyramid
Partial Denoising Steps
20
Jumpy Denoising Interval
10
DDIM Sampling y
0.0
Plamning & Search Setrings
Max Search Itcrations
500
Stabilization Level
10
Planning Horizon
Task-dependent (sec Sec A.7
Open-loop Horizon
(for replanning). otherwise full horizon Task-dependent (see Sec A.7
Guidance Set
Method-Specific Settings
Parallelism Degree
200 (P-MCTD, Fast-MCTD), (otherwise)
Parallel Search Weight (w)
1.0
Subsampling Interval (f))
(S-MCTD, Fast-MCTD), (otherwise)
A.7
Evaluation details
Our experimental setup. including all hyperparameters and environmental settings, is consistent with prior work 33 The specific configurations for each task are detailed below.
A.7.1 Maze navigation with point-mass mass and ant robots
Planning parameters. For the point-mass maze tasks, we use a guidance scale set of (0, 1,0.1.1.... 0.5, 1, 2). while for the antmaze evaluations, the set is (0, 1, 2, 3, 4, 5). The planning horizon set to 500 for medium and large mazes and is extended to 1000 for giant mazes.
Low-level controller. For the point-mass maze tasks, we employ the heuristic controller from Janner al. 12 For the antmaze tasks, we utilize the diffusion-basee value-learning policy from Chen et al. [. which functions as a low-level controller to navigate the agent toward given subgoal. A new subgoal assigned every steps, contingent upon successful arrival previous one.
Reward function for tree search-based planners. For maze navigation tasks, we adopt the reward function from Yoon et al. 33 This function assigns reward of zero to physically implausible trajectories, such as those with excessively large changes between consecutive states. For valid trajectory that reaches the goal timestep the reward is calculated as (H t)/H, where H
23

---

Table 11: Leaf parallelization ablation study results. Success rates and planning times (#: std) across PointMaze environment on medium, large giant sized maps.
Success Rate t (%)
Planning Time &. (sec.)
Env.
Method
medium
large
giant
medium
large
giant
No Leaf Par. (P-MCTD)
100 a
100 1:0
100 0
8.5 a
7.4 = 13
12.8 2:25
PointMaze
Leaf Pur.
6
100 1:0
1
7.4 1
6.7 = 0.
17.0 2.28
is the maximum horizon length. This reward structure incentivizes the discovery of shorter, more efficient paths.
A.7.2 Robot arm cube manipulation
Planning parameters and low-level controller. For each object, we utilize set of guidance scales 2,2,44.. As MCTD employs object-wise guidance [33], the total number of guidance combinations scales with the number of objects. The planning horizon is set to H 200 for single-cube tasks and H = 500 for all multi-cube manipulation tasks. We employ the same value-learning policy as in the antmaze tasks, following Wang et al. [30]
Redundant plans. Consistent with Yoon et al. 33 we implement redundant plans to resolve inconsistencies arising from object-wise planning. These plans are inserted between object-wise plan segments and exccute pre-defined actions, such as opening the gripper to release an object or returning to default position. This prevents infeasible actions, for instance, attempting to grasp new object while another is already held or moving to a distant, unrelated location.
Reward function for tree search- planners. We adopt the reward function from Yoon et al. [3 for the robot arm manipulation tasks. This function assigns a reward zero to physically implausible outcomes, including: (1) moving multiple cubes simultaneously;
(2) leaving cube suspended in mid-air; (3) causing collisions between cubes; or (4) grasping a cube that is obstructed by another. For trajectories that successfully complete the task at timestep t, a positive reward of r (H /) H is assigned, where is the maximum horizon length.
A.7.3 Visual point-mass maze
Framework for visual environment. For the visual maze tasks, we introduce a framework consist- ing of three pre-trained components. First, a Variational Autoencoder (VAE) [3] is pre-trained to encode visual observations into compact 8-dimensional latent representation, 2. This representation serves as the input for our planning and control models. Second, an MLP- inverse dynamics model, fuw, is pre-traine pre-trained to predict the action å required for transition. To infer velocity from static observations. the model is conditioned on three consecutive latent states: à, = fun (2t-1, 24, 24+1). This model functions as the low-level controller. Third, pre-train an MLP-based position estimator to predict the agent's coordinates from the latent state z. This estimator provides a positional signal for planning guidance without compromising the task's partial observability.
Planning parameters. We use a set of guidance seales {0, 0.1, 0.5, 1, 2}. Guidance is applied in the state space using the coordinates inferred by the pre-trained position estimator. This approach allows us to employ the same guidance function used in our other tasks (Section 6). A fixed planning horizon of H 500 is used for both the medium and large maze environments.
B
Additional experimental results
B.1
Leaf parallclization ablations
We conduct ablation study to compare method against leaf parallelization, common MCTS strategy that expands multiple children from a single node in parallel [99. The motivation for this approach is to reduce selection overhead by performing multiple expansions per selection operation.
As shown in Table TT] this strategy exhibits inconsistent performance across environment scales. While it offers marginal speedups in the medium (8.5s vs. 7.4s) and large (7.4s vs. 6.7s) mazes,
24

---

Generation from Student
Generstion from Teacher
Generation from Student
Generation from Teacher
Varying noise levels per subplan
(b) Uniform noise levels per subplan
Figure 6: Distillation challenges in MCTD. Trajectory quality from distilled diffusion models varies significantly based on the noise level distribution during training. (a) Using variable noise levels
(required for causal scheduling) leads to poor trajectory quality. (b) Using uniform noise levels
produces cleaner trajectories but is incompatible with MCTD's causal scheduling requirements.
significantly increases planning time in the giant maze (12.8s vs. 17.0s), degrading performance in the most computationally demanding setting.
We attribute this degradation disruption of the exploration-xxploiaaionn balance managed by
search-aware selection mechanism (Equation 5 By forcing the expansion of multiple children from the same node, leaf parallelization concentrates computational resources on potentially suboptimal branches, This effect is particularly detrimental in larger search spaces where strategic exploration is crucial. These findings validate our design choice to parallelize across disparate branches rather than within single node's 's children, especially for complex, long- aanghorizon planning tasks.
B.2 Distillation of diffusion planner ablations
We investigated diffusion model distillation, a prominent technique for accelerating the denoising process [23), as potential optimization for MCTD. We trained student model to predict the output of two teacher denoising steps, following the progressive distillation method.
However, this approach produced low-quality trajectories (Figure (6). We posit that this failure stems from a fundamental incompatibility; standard distillation methods assume uniform noise level across the entire data sample, whereas MCTD's causal scheduling applies heterogeneous, per-subplan noise levels. This transforms the distillation task into a more complex learning problem, as the student must learn mapping that is conditioned
non-uniform noise schedule.
Our findings suggest that successfully distilling MCTD is non-trivial task that requires novel distillation techniques capable of handling such heterogeneous noise distributions. We leave the development of these methods future work.
C Further discussion
C.1 On the choice fixed-interval subsampling
S-MCTD employs fixed-interval subsampling strategy for temporal abstraction. This approach contrasts with the semantic or hierarchical subgoal definitions typical the classical options frame- work 229] yet aligns with recent trends in diffusion-based planners, such Hierarchical Dif- fusers 5 and PlanDQ [4]. This design choice provides a simple yet general mechanism for abstracting trajectories.
Our empirical results corroborate the efficacy of this fixed-interval scheme. Notably, prior work [5] has shown that fxxd-interval subsampling can outperform adaptive subgoal selection methods like HDMI [5]. These findings suggest that a simple, uniform subsampling strategy can be more effective than complex, learned subgoal discovery techniques in certain domains.
C.2 Limitations and trade-offs of sparse planning
While sparse planning enhances the efficiency of Fast-MCTD, the level of abstraction, controlled by the hyperparameter H, introduces trade-off with performance. We empirically identified two primary failure modes:
25

---

1. Excessively coarse abstraction: As shown in Figure 4 the success rate degrades sig- nificantly when the abstraction interval H exceeds 20. This trend, observed across both PointMaze-Giant and AntMaze-Giant highlights the limitations of sparse guidance in scenarios requiring fine-grained control.
2. Tasks requiring high precision: rate in PointMaze-Mediin and Giant but drops sharply to 8% in PointMaze-Large, despite using an identical planning architecture. We hypothesize this discrepancy is due the task's geometric constraints, such as narrow corridors, which demand high- nigh-precision maneuvering. The coarse temporal abstraction may cause the planner to overlook critical intermediate states required to navigate these tight spaces successfully.
As reported in Table 2 S-MCTD achieves 100% success
C.3 Generalization
key feature of Fast-MCTD is its ability perform high-quality planning efficiently inference time. This design enables zero-shot adaptation to novel goals and initial states without requiring any retraining, However, consistent with other models trained on fixed data distribution (2] I2 [3], its performance may degrade when deployed in environments with significant dynamics shifts or out-o--distribution states.
C.4 Future work
promising avenue for future research is the integration of learned value functions or policy priors guide the search process. Such guidance could significantly enhance planning efficiency by pruning unpromising branches of the search tree, thereby reducing redundant rollouts. However, key challenge lies in integrating these components without compromising the simplicity and parallel scalability of Fast-MCTD's sparse planning framework.
Another compelling direction is extending Fast-MCTD to multi-agent planning domains. While the core framework is theoretically applicable, a naive extension would face challenges from the combinatorial explosion of the joint action and state spaces. Here, learned value functions or factored representations could be crucial for tractably managing the search complexity.
Finally, exploring more flexible temporal abstractions is promising direction. While S-MCTD uses a fixed-interval subsampling for its simplicity and parallelization benefits, adaptive interval selection could dynamically enhance efficiency and accuracy. This might mitigate over-abstraction issues in tasks requiring high precision. However, this must be balanced against added complexity and findings that simple fixed-interval schemes can outperform adaptive methods in some cases. Investigating this trade-off remains a valuable area for future research.
26

---

D Algorithms
Algorithm 2 Fast Monte Carlo Tree Diffusion
1: procedure FAST- FAST-MCTT (Crot iterations, jer.auleeiimmdeeeeeejjja..
2: for = 1 to iterations by puraalelism_degreee do
3:
nodes to tas__t___eppee expand <-
4: tempp_ citipp__istt_oouuttss _counts
Track parallel selections
for j
parallelism_ddgree
sarrch-wware P Search aware selection
6:
node t- root
7:
and not ISLEAF(Rode) do while SHARCH temp_ compp_vsittcommneee
8:
node 4
temp_nisitccontt [node] tewmp_/wss_coontsseeetooooo 0)
10:
end while APPEND(nodes to expand, node) end for exparssions []
11:
12:
13:
14:
for node nodes fedde_tt__eee to_expond in parallel
Parallel expansion phase
15:
(LEEE then
16:
9. + TELEECTMETAACTIONnndd APPEND(ezpaansions (node, 9.)) end if
17:
18:
19:
20:
new children + BACUDDDDoSSSuuurAuiiqqppsossusus
21:
for (node, child) E new children do ADDCHILD(node,.co child)
22:
23:
end for simulations + for (node, chald) E new new_children in parallel do
24:
25:
b Parallel simulation phase
26:
partial + GETTAARTAATTRAACCORRRRR
27:
APPENDDsiimulaations, (node, child, partial)) for rewards +- -ccel//ssSaassDaaooooommmmaaaaaa
28:
29:
30:
for (node, child, reward) rewerds do
D Delayed tree update
31:
current +- child
32:
while current * null
33:
current.visiiCoome 4- surrent.vissiCoont
34:
current. + Max(current. reward)
35:
UPPATTEMETAACTTINSCIEEDII current current.parent
reward)
36:
37:
end while end for
38:
39:
end for
40: return BESTCHILD(roOt)
41:
end procedure
27


Reviews:
[{"review_id": "s4jv963wZi", "reviewer": "Reviewer_hTDe", "summary": "This paper introduces Fast-MCTD, a framework designed to accelerate the performance of Monte Carlo Tree Diffusion (MCTD), a state-of-the-art diffusion-based planner. The authors identify two key bottlenecks in MCTD: the sequential nature of tree search and the high computational cost of iterative denoising over long trajectories. To address these, they propose two primary techniques: Parallel MCTD (P-MCTD), which parallelizes the search process using delayed tree updates and a redundancy-aware selection mechanism, and Sparse MCTD (S-MCTD), which reduces the effective planning horizon by operating on coarsened, subsampled trajectories. Experimental results across several challenging long-horizon tasks demonstrate that Fast-MCTD can achieve significant speedups over the original MCTD, while largely maintaining or sometimes even improving planning success rates.", "questions": "* Could you provide a more concrete example of the tree construction? Specifically, how is a trajectory partitioned into subplan nodes, and how are the meta-actions (guidance schedules) applied to these nodes during expansion? It'd be nice if the authors can expand on the details of each procedure of Fast-MCTD in the appendix.\n\n* The S-MCTD method creates abstract trajectories by uniformly subsampling states every H steps. How does this method of abstraction compare to more structured approaches, such as the options framework by Sutton et al. (1999), where temporally-extended actions are typically defined by sub-goals or semantic criteria? Does uniform subsampling risk creating abstract waypoints that are dynamically challenging for the low-level controller to achieve, and could you comment on whether this approach captures semantically meaningful sub-tasks versus serving primarily as an effective computational heuristic?\n\nReference:\n[1] Sutton et al. (1999): Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 2, "strengths_and_weaknesses": "__Strengths__\n\n* Practical impact: The work delivers a significant and practical contribution by drastically reducing the planning time of a state-of-the-art diffusion planner. The reported 80-110x speedups on challenging long-horizon tasks make the underlying MCTD method far more viable for practical use.\n\n* The authors present a well-designed approach, identifying two distinct inefficiencies (between-rollout and within-rollout) and proposing a specific, well-motivated solution for each (P-MCTD and S-MCTD, respectively).\n\n* Claims are backed by a comprehensive evaluation on diverse benchmark tasks. The ablation studies on key hyperparameters like parallelism degree and interval size are reasonable and provide convincing evidence for the method's effectiveness.\n\n__Weaknesses__\n\n* Lack of self-containedness: The paper relies heavily on prior work to explain core mechanics. Critical details on how the diffusion model is trained for this task, and how trajectories are partitioned into subplans to form the tree structure, are not sufficiently explained. This lack of clarity hinders a full understanding and reproducibility.", "was_revised": true, "final_justification": "This is a strong, high-impact paper, and the authors' rebuttal fully addressed all of my questions.\n\nMy initial concerns about the paper's clarity and the justification for its subsampling method have been resolved. The authors committed to adding implementation details to the appendix and provided a compelling, evidence-backed explanation for their design choice.\n\nI have no remaining issues and view this as a clear accept.", "rebuttal": "We thank reviewer hTDe for the thoughtful feedbacks and valuable suggestions.\n\n> Details on how the diffusion model is trained\n\nWe appreciate the reviewer’s interest in implementation details. The diffusion model in Fast-MCTD follows the same training protocol as MCTD, and we explicitly restate all relevant configurations in Appendix A.4 for clarity and completeness. We will further revise the appendix to ensure the training procedure is fully transparent and reproducible.\n\n**We follow the same training protocol as prior diffusion planners such as Diffuser and Diffusion Forcing.** Concretely, the model is trained on offline datasets of trajectories collected in OGBench. The training objective follows a standard $\\mathbf{x}_0$ prediction loss, where the model learns to recover the original trajectory $\\mathbf{x}_0$ from noisy inputs. We employ a Transformer architecture with stacked attention blocks, trained using cosine schedules. All hyperparameters, including learning rates, batch sizes, and sampling schedules, are fully reported in the appendix for reproducibility. \n\nAdditionally, we plan to release our full implementation shortly, which will further support reproducibility.\n\n\n> How is a trajectory partitioned into subplan nodes, and how are the meta-actions (guidance schedules) applied to these nodes during expansion? \n\nFor planning, we simply partition each trajectory into fixed-length segments of $S$ timesteps. Each segment, or subplan, is used as a high-level node in the search tree. Each node is denoised independently using a blockwise schedule, which allows early subplans to be generated first and later ones to be conditioned on them, creating an autoregressive structure within the diffusion framework.\n\nDuring tree expansion, meta-actions are defined as **guidance levels** selected from a predefined set (e.g., $\\{0, 1, 2, 4\\}$), controlling the strength of classifier guidance for each subplan. These levels modulate how strongly each node is biased toward goal achievement, enabling dynamic exploration–exploitation balancing across the tree.\n\nWe will expand these details in the appendix.\n\n> The S-MCTD method creates abstract trajectories by uniformly subsampling states every H steps. How does this method of abstraction compare to more structured approaches, such as the options framework by Sutton et al. (1999), where temporally-extended actions are typically defined by sub-goals or semantic criteria?\n\nWe thank the reviewer for this insightful question.\n\nS-MCTD adopts a fixed interval subsampling strategy (e.g., every $H$ steps)—rather than defining subgoals through semantic or hierarchical criteria, as done in classical options frameworks. This approach follows recent diffusion planners such as Hierarchical Diffuser [1,2] and PlanDQ [3], and offers a simple yet general abstraction mechanism.\n\nEmpirically, this strategy has proven highly competitive: Hierarchical Diffuser [1] reports that fixed-interval subsampling **outperforms adaptive subgoal selection** methods like HDMI [4], suggesting that even simple fixed-interval structures can outperform learned subgoal discovery methods.\n\n[1] Simple Hierarchical Planning with Diffusion., Chen et al., ICLR’24\n\n[2] DiffuserLite: Towards Real-time Diffusion Planning, Dong et al., NeurIPS’24\n\n[3] Hierarchical Plan Orchestration via D-Conductor and Q-Performer., Chen et al., ICML’24\n\n[4] Hierarchical diffusion for offline decision making, Li et al., ICML’23\n\n> Does uniform subsampling risk creating abstract waypoints that are dynamically challenging for the low-level controller to achieve?\n\nWe acknowledge that overly coarse waypoints can challenge low-level controllers. In S-MCTD, we address this by conducting an ablation over the interval size $H$, which reveals a clear trade-off: increasing $H$ improves efficiency, but can degrade success rates due to infeasible transitions. Based on this, we select $H$ to balance planning speed with controller compatibility.\n\n> Could you comment on whether this approach captures semantically meaningful sub-tasks versus serving primarily as an effective computational heuristic?\n\nWe thank the reviewer for this thoughtful question. **S-MCTD does not attempt to discover semantically meaningful subgoals.** This is a **deliberate design choice**, not a limitation. Semantic subgoal discovery often requires task-specific priors, auxiliary supervision, or added complexity—all of which reduce scalability and generality across domains.\n\nInstead, our method adopts a **simple, task-agnostic abstraction** based on fixed-interval subsampling. While it does not align with semantic task boundaries, it enables robust and tractable long-horizon planning without additional annotation or modeling overhead. Prior works, such as Hierarchical Diffuser [1, 2], have shown that this simple approach actually outperforms the adaptive subgoal method like HDMI [3].\n\nMoreover, this regular structure is especially well-suited for **parallel rollout planning**, as required in P-MCTD. Semantically chunked subgoals could introduce variability and irregularity that would hinder batching and GPU-efficient parallel denoising.\n\n[1] Simple Hierarchical Planning with Diffusion., Chen et al., ICLR’24\n\n[2] DiffuserLite: Towards Real-time Diffusion Planning, Dong et al., NeurIPS’24\n\n[3] Hierarchical Diffusion for Offline Decision Making., Li et al., ICML’23"}, {"review_id": "TPNZ0ZZsFs", "reviewer": "Reviewer_FWQE", "summary": "The authors propose Fast Monte Carlo Tree Diffusion (Fast-MCTD) to accelerate the planning time of conventional MCTD. They first introduce Parallel MCTD, which enables parallel computation in the expansion and simulation stages to speed up the MCTD process, and implement Redundancy-Aware Selection (RAS) as the selection strategy. Second, they present Sparse MCTD, which trains the diffusion model using sparse, coarse-grained trajectories. Experimental results demonstrate that Fast-MCTD achieves performance comparable to standard MCTD while significantly reducing planning time.", "questions": "1. How does Fast-MCTD compare to subgoal-based Diffuser variants that are designed for long-horizon planning, such as the hierarchical approaches in [1] and [2], in terms of both computational cost and performance?\n\n2. How is the Redundancy-Aware Selection (RAS) policy in Eq. (5) derived? Is it adapted from prior work on parallelized MCTS? Were there any challenges in formulating this policy?\n\n3. Are the sparse coarse trajectories used to train the diffusion model in addition to the original trajectories, or do they replace the original trajectories?\n\n[1] Chen, Chang, et al. Simple Hierarchical Planning with Diffusion. The Twelfth International Conference on Learning Representations (ICLR), 2024.\n\n[2] Li, Wenhao, et al. Hierarchical Diffusion for Offline Decision Making. International Conference on Machine Learning (ICML), 2023.", "limitations": "The authors claimed that they discussed the limitations of their work in a separate section, but such a section cannot be found in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The experimental results presented in the paper show a significant improvement in planning speed—up to 100× faster—compared to the standard MCTD method.\n\n2. The paper includes comprehensive experiments to evaluate the effectiveness of the proposed Fast-MCTD approach.\n\n3. Concrete implementation details and extensive experimental configurations are provided in the supplementary materials, enhancing reproducibility.\n\nWeaknesses:\n\n1. The work appears to be an incremental extension of the original MCTD method. The primary contribution lies in applying parallel computation to certain stages of MCTD, which limits the novelty of the paper.\n\n2. According to the original MCTD paper, the number of possible search trajectories is already bounded, meaning that the computational cost of standard MCTD does not grow exponentially without limit. Moreover, the proposed parallelization in Fast-MCTD does not reduce the exponential complexity in the worst case, but rather achieves a practical speedup by a factor of $K$.", "was_revised": true, "final_justification": "The authors have provided valuable responses in the rebuttal stage that have mostly addressed my concerns. While I believe the idea is not particularly novel and incorporates elements from prior works, the results are excellent and the paper is well written, warranting acceptance.", "rebuttal": "> The work appears to be an incremental extension of the original MCTD method. The primary contribution lies in applying parallel computation to certain stages of MCTD, which limits the novelty of the paper.\n\nWe sincerely thank the reviewer for their valuable feedback. We appreciate this opportunity to clarify the primary contributions of our work.\n\nFirst of all, we would like to emphasize that our main contribution lies in unleashing the full potential of the MCTD method as a practically adoptable solution by resolving its primary bottleneck—speed—rather than proposing a conceptually novel methodology. \n\nNevertheless, we respectfully wish to clarify that Fast-MCTD is also not merely a parallel extension of MCTD. Seemingly, it might look like an adoption of the MCTS parallelization. However, to make the adoption effective in the context of diffusion-based planning, we additionally propose **Redundancy-Aware Selection** and **Parallel Denoising**. These are non-trivial additions designed to efficiently navigate the vast search space inherent to diffusion models, a challenge that standard parallelization does not address. Furthermore, our contribution is not limited to parallel search. We also introduce **Sparse-MCTD**, a complementary approach that fundamentally enhances efficiency by enabling coarsen planning.\n\nTogether, **these techniques transform MCTD from a proof-of-concept into a practical tool for long-horizon or large-scale planning, achieving up to 100× speedup while retaining performance.** By addressing both diffusion- and search-specific inefficiencies, Fast-MCTD improves the practical usability of standard MCTD for long-horizon planning.\n\n> The number of possible search trajectories is already bounded, meaning that the computational cost of standard MCTD does not grow exponentially without limit.\n\nWhile it is true that the number of search trajectories in MCTD is theoretically bounded, we emphasize that **practical planning cost still grows exponentially** with the number of subplans $\\bar{s}$, which increases with the planning horizon. As detailed in Section 3, the search complexity scales as $O(N_{\\text{child}}^{\\bar{s}})$, making long-horizon tasks such as Giant PointMaze and visual mazes computationally expensive in practice. If the bound is set too high, computational overhead becomes significant; if set too low, exploration is insufficient and plan quality degrades. Also, in practice, many applications require not only bounded search time but also fast search.\n\n> The proposed parallelization in Fast-MCTD does not reduce the exponential complexity in the worst case, but rather achieves a practical speedup by a factor of $K$.\n\nAs you acknowledged, the main contribution of our work is to improve the practical speedup of MCTD. And, we agree that reducing the worst-case exponential complexity is not our main goal. However, the sparse MCTD allows to reduce $\\bar{s}$ by planning over temporally coarsened trajectories. This reduces the planning depth exponentially, fundamentally altering the computation complexity—not just the runtime.\n\n$\nC_{\\text{S-MCTD}} = \\mathcal{O}\\left(N_{\\text{child}}^{\\bar{s} / H} \\cdot C_{\\text{coarse}}\\right)\n$\n\nIn standard MCTD, the search complexity scales as:\n\n$\nC_{\\text{MCTD}} = \\mathcal{O}(N_{\\text{child}}^{\\bar{s}} \\cdot C_{\\text{sub}})\n$\n\n> How does Fast-MCTD compare to subgoal-based Diffuser variants that are designed for long-horizon planning, such as the hierarchical approaches, in terms of both computational cost and performance?\n\nWe thank the reviewer for this valuable question. While both Fast-MCTD and subgoal-based diffusion planners aim to address long-horizon planning through abstraction, they focus on fundamentally different aspects of the problem.\n\n- **Hierarchical Diffuser (HD)** [1] does **not perform explicit search**, but instead generates trajectories using subgoal conditioning. This approach results in much larger improvements in **training time** than in inference time (e.g., training time reduced from 132.7s to 8.7s, while planning time drops from 9.9s to 3.1s in Med-Maze).\n- In contrast, Fast-MCTD performs tree-based search at inference time. By coarsening trajectories and reducing the overhead on denoising process and the number of subplans from $\\bar{s}$ to $\\bar{s}/H$, Fast-MCTD achieves an exponential reduction in the search space, leading to significant speedups during planning.\n\nWe perform a fair comparison using guidance-based planning for both methods on PointMaze tasks. **The result shows that Fast-MCTD significantly outperforms HD with better efficiency.**\n\n|  |  | Planning Time |  |  | Success Rates |  |\n| --- | --- | --- | --- | --- | --- | --- |\n|  | medium | large | giant | medium | large | giant |\n| Diffuser | 6.6 ± 0.10 | 6.5 ± 0.10 | 6.4 ± 0.1 | 0.58 ± 0.06 | 0.44 ± 0.08 | 0 ± 0 |\n| Hierarchical Diffuser | 4.48 ± 0.14 | 4.57 ± 0.10 | 4.90 ± 0.31 | 0.62 ± 0.06  | 0.24 ± 0.08 | 0.00 ± 0.00 |\n| MCTD | 59.2 ± 27.1 | 174.6 ± 27.2 | 264.2 ± 33.8 | 1 ± 0 | 0.98 ± 0.06 | 1 ± 0 |\n| Fast-MCTD | 3.6 ± 0.6 | 4.1 ± 0.4 | 2.4 ± 0.1 | 1 ± 0 | 0.80 ± 0.00 | 1 ± 0 |\n\nParticularly, Fast-MCTD achieves over 100× inference-time speedup through exponential search space reduction with sparse planning, while Diffuser and Hierarchical Diffuser achieve only modest planning speedup under the same evaluation protocol.\n\n[1] Simple Hierarchical Planning with Diffusion., Chen et al., ICLR`24\n\n> How is the **Redundancy-Aware Selection (RAS) policy in Eq. (5) derived**? Is it adapted from prior work on parallelized MCTS? Were there any challenges in formulating this policy?\n\nWe thank the reviewer for the insightful question regarding our Redundancy-Aware Selection (RAS) policy. The reviewer is correct that the design of RAS is inspired by prior work on parallelized MCTS [1, 2], particularly the concept of virtual loss introduced in [2]. Furthermore, we apply a penalty only to the visit counts to encourage a more exploitative search.\n\nRegarding the challenges in formulating this policy, the key consideration was the sensitivity to the hyperparameter $w$. To address this, we conducted an extensive ablation study (presented in Table 6 for the PointMaze-Giant tasks). The results demonstrate that Fast-MCTD exhibits **robust performance across a wide range of w values**, indicating that precise tuning is not critical for achieving strong results.\n\n[1] Parallel monte-carlo tree search. Guillaume et al., In Computers and Games, 2008.\n\n[2] Mastering the game of go with deep neural networks and tree search. Silver et al., Nature 2016.\n\n> **Are the sparse coarse trajectories used to train the diffusion model in addition to the original trajectories, or do they replace the original trajectories?**\n\nWe thank the reviewer for the clarifying question. In S-MCTD, **coarsened trajectories replace the original ones** during model training. That is, we train a single diffusion model on uniformly subsampled sequences (e.g., every $H$ steps), instead of using the original fine-grained data.\n\n> The authors claimed that they discussed the limitations of their work in a separate section, but such a section cannot be found in the paper.\n\nWe thank the reviewer for their comment. While we discussed key limitations in Section 7 (e.g., reliance on parallelism and new hyperparameters), we acknowledge the absence of a dedicated “Limitations” section may have reduced clarity. We will restructure these points into a clearly marked section in the revision."}, {"review_id": "HY5tukQ2UY", "reviewer": "Reviewer_pbF8", "summary": "Recent work (MCTD) has used pretrained diffusion models to enable long-horizon planning using partially denoised plans along with Monte-Carlo tree search (MCTS). This work proposes to speed up MCTD using both parallel rollouts and a sparse trajectory-coarsening approach. Experiments with goal-conditioned RL tasks show that method achieves state-of-the-art results compared to other diffusion-based planning approaches. Both the parallel rollouts and the sparse trajectory coarsening approach maintains the good performance of MCTD while improving timing by up to two orders of magnitude.", "questions": "It seems like the experimental setup has been established in previous works such as MCTD and others. However, for the work to be self-contained, I would suggest explicitly defining $\\mathcal{J}_\\phi$ from Eq. 2 for each of the tasks. Is the \"guidance set\" weights of $\\mathcal{J}_\\phi$ that correspond to the actions of the MCTS? What are the number of timesteps in the pretraining trajectories and how do they compare to the number of timesteps in the found plans? More explanation of the \"replanning\" model variants would be helpful. Overall, I think the paper would be improved if details such as these were made more explicit in the main text.", "limitations": "Overall, yes, but see the last paragraph of \"Strengths and Weaknesses.\"", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Overall, the paper is written very clearly and the main contributions and experimental results are easy to read and understand. The two proposed modifications to MCTD are well-motivated and the ablation experiments are well done and give the reader a good sense of how the additional hyperparameters affect planning capacity (Tables 5, 6, Figure 4).\n\nThe performance of the model is very good and the problem of planning with pretrained diffusion models is an important research direction, especially given the recent uptick in interest in the flexible use of pretrained models with inference-time compute.\n\nThe paper is only moderately original, trajectory coarsening is not very novel in this context and parallel MCTS is a straightforward design improvement. I view this as a minor weakness of the paper.\n\nAnother weakness of the proposed approach is that the trajectory coarsening approach requires training a new diffusion model on coarsened trajectories, so the overall method is not strictly inference-time. This should be added to the discussion of limitations.", "was_revised": true, "final_justification": "After discussion with the authors, I remain convinced this is a strong paper. The original manuscript lacked clarity in some details, but the proposed clarification should fix this issue.", "rebuttal": "> The paper is only moderately original, *trajectory coarsening is not very novel* in this context *and parallel MCTS is a straightforward design improvement. I view this as a minor weakness of the paper.*\n\nWe thank reviewer pbF8 for the thoughtful feedback.\n\nThe main contribution of the paper is to propose a practical solution for improving the speed of MCTD, rather than introducing a conceptually novel approach. We acknowledge that, methodologically, the individual components may appear somewhat incremental. Nevertheless, we believe that their joint adaptation and integration specifically within the diffusion-based framework present a novel combination that effectively addresses key efficiency issues in MCTD.\n\nWe will revise the manuscript to better highlight this distinction and the unique innovations introduced.\n\n> Trajectory coarsening approach requires training a new diffusion model on ccoarsened trajectories, so the overall method is not strictly inference-time. This should be added to the discussion of limitations.\n\nThank you for the helpful comment. We agree that Fast-MCTD requires training a separate diffusion model on coarsened trajectories. While the planning process is entirely inference-time, the abstraction does require an additional training phase. We will clarify this point in the Limitations section.\n\n> It seems like the experimental setup has been established in previous works such as MCTD and others. However, for the work to be self-contained*,* I would suggest explicitly defining $\\mathcal{J}$ that correspond to the actions of the MCTS from Eq.2 for each of the tasks .\n\nWe thank the reviewer for highlighting the importance of clearly defining $\\mathcal{J}$.\n\nIn all tasks, we use the same guidance function following MCTD.\n\n$\n\\mathcal{J}(\\mathbf{x}) =\\sum_{i=1}^T ||x_i - g||^2\n$\n\nwhere $x_i$ is the $i$-th state and $g$ is the target goal. This design encourages trajectories that reach the goal as quickly as possible. For consistency and fair comparison, we use this distance-based guidance function for all baselines and all task domains.\n\nWe will make this definition explicit in the main text to improve clarity and self-containedness.\n\n> Is the \"guidance set\" weights of $*\\mathcal{J}$* that correspond to the actions of the MCTS?\n\nYes, in our framework, the “guidance set” refers to a set of discrete scalar weights applied to $\\mathcal{J}$ during each tree expansion. Each weight functions as a meta-action, directly influencing the degree of goal-directedness for the generated trajectory segment at that node.\n\nIn the MCTS process, selecting a specific weight from the guidance set at each branching point is analogous to choosing an action; this mechanism enables the planner to balance exploration and exploitation by adjusting the guidance strength.\n\nThe guidance sets used in our experiments are as follows:\n\n- **PointMaze (medium/large):** $[0, 0.1, 0.5, 1, 2]$\n- **PointMaze (giant):** $[0.5, 1, 2, 3, 4]$\n- **AntMaze:** $[0, 1, 2, 3, 4, 5]$\n\nEach value is treated as a meta-action, and the MCTS expands the tree across these discrete choices.\n\n> What are the number of timesteps in the pretraining trajectories and how do they compare to the number of timesteps in the found plans? More explanation of the \"replanning\" model variants would be helpful.\n\nThe pretrained diffusion model is trained on trajectory segments of 500 timesteps for medium and large mazes, and 1000 timesteps for giant mazes. At inference time, the planner generates full-horizon plans of the same lengths.\n\nIn robot manipulation and visual maze domains, we adopt the MCTD-Replanning variant introduced in the original MCTD paper, as the MCTD w/o replanning often struggles in these settings due to the complexity of multi-object interactions or the risk of trajectory collapse in long visual rollouts. In this variant, the agent generates a new full-horizon plan at each replanning step (e.g. 500) but executes only the first 50 steps before replanning from the updated state. This process is repeated until the task is completed.\n\nWe will clarify these implementation details, including all relevant planning horizons and replanning protocols, in the revised manuscript for completeness.\n\n> The paper would be improved if details such as these were made more explicit in the main text.\n\nWe agree with the reviewer’s recommendation to make these details explicit in the main text. In our revision, we will clearly present:\n\n- Definitions of the guidance function and the precise relationship to meta-actions.\n- Exact descriptions of training vs. inference-time trajectory lengths.\n- A clear explanation of replanning strategies, intervals, and their impact on computational efficiency.\n\nWe sincerely appreciate reviewer pbF8’s constructive feedback and believe that these revisions will significantly strengthen the quality and self-containedness of our work."}, {"review_id": "qMyMntIYR4", "reviewer": "Reviewer_EsS3", "summary": "Fast-MCTD combines two enhancements to the original MCTD: Parallel MCTD (P-MCTD), which introduces parallel rollouts with delayed tree updates and redundancy-aware selection to minimize duplicated computation; and Sparse MCTD (S-MCTD), which reduces planning complexity by operating on coarsened trajectory segments. The core innovation lies in integrating these methods to preserve MCTD’s planning strength while enabling high-throughput and low-latency execution, leveraging GPU acceleration and hierarchical abstraction.\n\nThe method is evaluated on OGBench tasks, including PointMaze, AntMaze, robot arm manipulation, and visual planning. Comparisons are made against Diffuser, Diffusion Forcing, and MCTD using metrics like success rate and planning time. Ablation studies isolate the impact of key design choices.", "questions": "1. How does Fast-MCTD scale with increasing action/state space complexity beyond current benchmarks? Would it remain computationally tractable in domains like multi-agent planning?\n2. What is the role of learned value functions or priors in further enhancing the efficiency of search within Fast-MCTD? Can these be integrated without negating the gains from sparse and parallel planning?\n3. Could adaptive interval selection in S-MCTD improve both efficiency and accuracy dynamically? This would potentially mitigate the issue of over-abstraction in long-horizon tasks.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- **Algorithmic Design:** The paper proposes Fast-MCTD, integrating two novel variants—Parallel MCTD and Sparse MCTD—which address key inefficiencies in Monte Carlo Tree Diffusion (MCTD).\n- **Significant Efficiency Gains:** Fast-MCTD achieves up to 100× speedup over MCTD and even outperforms purely denoising-based approaches like Diffuser in some inference scenarios.\n- **Thorough Empirical Validation:** The paper evaluates its approach across diverse domains (maze navigation, robotic manipulation, visual planning), and performs extensive ablation studies on key components (e.g., Redundancy-Aware Selection, parallelism degree). It benchmarks against relevant state-of-the-art models such as Diffuser, Diffusion Forcing, and MCTD, ensuring a meaningful performance context.\n- **Clear Theoretical Motivation:** The authors discuss the “Planning Horizon Dilemma” and analyze computational complexity, helping justify the need for both parallelization and trajectory coarsening.\n\n**Weaknesses**\n- **Limited Discussion on Generalization:** While efficiency and performance gains are clear in the tested domains, the paper could elaborate more on how well Fast-MCTD generalizes to unseen environments or out-of-distribution tasks.\n- **Sparse Planning Trade-offs:** The use of trajectory coarsening (S-MCTD) introduces approximation. While the authors do provide some mitigation strategies and ablations, a deeper analysis of where abstraction breaks down would be valuable.", "was_revised": true, "final_justification": "This paper deserves strong acceptance due to its rigorous method design and extensive evaluations. This could benefit many works using MCTS in goal-conditioned RL settings.", "rebuttal": "We thank reviewer EsS3 for insightful comments and constructive questions regarding potential directions for further improvement. Below, we address these points and outline how we will incorporate them into the revised manuscript.\n\n> Limited Discussion on Generalization: While efficiency and performance gains are clear in the tested domains, the paper could elaborate more on how well Fast-MCTD generalizes to unseen environments or out-of-distribution tasks.\n\nWe agree that explicitly discussing generalization is important. \n\nAlthough our current experiments follow the standard evaluation protocols in this line of research, we also agree that these protocols should be improved to better assess generalization to unseen environments. \n\nFast-MCTD is designed to efficiently perform tree-search-based planning entirely at inference time. **This enables adaptation to novel goals and initial states without retraining.** However, **like other diffusion-based planners**, Fast-MCTD may face **limitations when transferred to environments** with fundamentally different dynamics or state distributions. We will clarify these points in the revised manuscript.\n\n> Sparse Planning Trade-offs: The use of trajectory coarsening (S-MCTD) introduces approximation. While the authors do provide some mitigation strategies and ablations, a deeper analysis of where abstraction breaks down would be valuable.\n\nWe thank the reviewer for this important observation. We empirically identified two primary conditions under which abstraction begins to fail:\n\n1. **Overly large waypoint intervals**: As shown in Figure 4 , success rate degrades significantly when the abstraction interval increases beyond 20. This trend holds across both PointMaze-Giant and AntMaze-Giant, reflecting the limits of sparse guidance when dense, fine-grained control is needed.\n2. **Precision-sensitive tasks**: As shown in the main results table, S-MCTD achieves perfect success (100%) in PointMaze-medium and giant, but drops sharply to 84% in PointMaze-large, despite using the same planning architecture. We attribute this to the precision demands of PointMaze-large, where narrow corridors and sharp turns make the agent more sensitive to omitted intermediate states. The coarse abstraction in S-MCTD likely causes the planner to miss key maneuvering steps.\n\nIn our revision, we will provide a deeper analysis illustrating these boundaries more explicitly.\n\n> What is the role of learned value functions or priors in further enhancing the efficiency of search within Fast-MCTD? Can these be integrated without negating the gains from sparse and parallel planning?\n\n**We view this as a highly interesting avenue for future work.** Incorporating learned value functions or priors is indeed a promising direction for further improving the planning efficiency of Fast-MCTD. Value functions or learned priors can help bias the search toward more promising regions, reducing redundant rollouts and potentially increasing both sample efficiency and scalability. However, integrating these techniques with sparse and parallel planning in diffusion-based search is nontrivial, as it requires careful coordination to avoid undermining the scalability and simplicity that Fast-MCTD offers. We will mention it as a potential extension in the revised manuscript.\n\n> Would it remain computationally tractable in domains like multi-agent planning?\n\nWe acknowledge that **extending Fast-MCTD to multi-agent planning is an open challenge.** While the framework is applicable to multi-agent domains “in principle”, computational efficiency may deteriorate due to the combinatorial growth of joint action and state spaces. Incorporating learned value functions might help mitigate these challenges, and we will discuss such extensions as promising future directions.\n\n> How does Fast-MCTD scale with increasing action/state space complexity beyond current benchmarks?\n\nWe acknowledge that **applying Fast-MCTD to significantly larger action/state spaces remains to be thoroughly validated.** However, our current experiments already involve high-dimensional settings, such as visual mazes and giant PointMaze, and we expect Fast-MCTD to scale reasonably well. That said, further scaling may introduce new challenges, which we consider an important direction for future validation.\n\n> Could adaptive interval selection in S-MCTD improve both efficiency and accuracy dynamically? This would potentially mitigate the issue of over-abstraction in long-horizon tasks.\n\nWe thank the reviewer for this valuable suggestion. We agree that adaptive interval selection in S-MCTD could potentially improve both efficiency and accuracy by dynamically adjusting the abstraction level. \n\nHowever, prior works [1, 2] empirically showed that fixed-interval abstractions can outperform adaptive subgoal selection methods like HDMI [3]. This suggests that while adaptive methods offer flexibility, they may also introduce additional overhead or instability, especially in high-parallelism settings like Fast-MCTD.\n\nNonetheless, we believe that developing smart adaptive abstraction methods remains a promising direction, which can further enhance the performance of Fast-MCTD. We will include this as an exciting future direction in the revised manuscript.\n\n[1] Simple Hierarchical Planning with Diffusion., Chen et al., ICLR’24\n\n[2] DiffuserLite: Towards Real-time Diffusion Planning, Dong et al., NeurIPS’24\n\n[3] Hierarchical diffusion for offline decision making, Li et al., ICML’23"}]

Author rebuttal:

Meta-review: The paper builds on the recently proposed Monte Carlo Tree Diffusion (MCTD), proposing a new variant Fast-MCTD improving its speed and scalability including parallel rollouts via delayed tree updates - a usual feature for MCTS game programs. The length of rollouts are reduced by operating on sparse, coarse-grained trajectories. Empirical evaluation show that the proposed variant improves significantly on MCTD in terms of speed.

While the reviewers argued that the ideas behind the new variant are not novel for MCTS, the proposed variant seems strong enough based on the empirical evaluation presented.

The reviewers were satisfied by the author-reviewer discussions, and felt that the paper is worthy of publication. We advise the authors revise the paper according to the discussions.
Decision: Accept (spotlight)