Compositional Monte Carlo Tree Diffusion for Extendable Planning
Authors: Jaesik Yoon
Hyeonseo Cho
Sungjin Ahn
Venue: NeurIPS 2025 spotlight ()
Keywords: Diffusion
MCTS
Long-term Planning
Offline RL
Goal-conditioned RL
Stitching sub-plans
Primary area: reinforcement_learning
TL;DR: C-MCTD enables diffusion planners to generate plans 10× longer than training examples by systematically stitching together shorter plans through tree search.

Abstract: Monte Carlo Tree Diffusion (MCTD) integrates diffusion models with structured tree search to enable effective trajectory exploration through stepwise reasoning. However, MCTD remains fundamentally limited by training trajectory lengths. While periodic replanning allows plan concatenation for longer plan generation, the planning process remains locally confined, as MCTD searches within individual trajectories without access to global context. We propose Compositional Monte Carlo Tree Diffusion (C-MCTD), a framework that elevates planning from individual trajectory optimization to reasoning over complete plan compositions. C-MCTD introduces three complementary components: (1) Online Composer, which performs globally-aware planning by searching across entire plan compositions; (2) Distributed Composer, which reduces search complexity through parallel exploration from multiple starting points; and (3) Preplan Composer, which accelerates inference by leveraging cached plan graphs.

Compositional Monte Carlo Tree Diffusion for Extendable Planning
Jaesik Yoon" KAIST & SAP
Hyeonseo Cho
KAIST
jaesik. www.lk..ooo@aaas..accooo
www.nnso.chokkaisee krr
Sungjin Ahn" KAIST & NYU
sungjin. sungjin.ahn@kaisee ahn@kaist.ac.kr
Abstract
Monte Carlo Tree Diffusion (MCTD) integrates diffusion models with structured search to enable effective trajectory exploration through stepwise reasoning. However, MCTD remains fundamentally limited by training trajectory lengths. While periodic replanning allows plan concatenation for longer plan generation, the planning process remains locally confined, as MCTD searches within indi- vidual trajectories without access to global context. We propose Compositional Monte Carlo Tree Diffusion (C-MCTD), framework that elevates planning from individual trajectory optimization to reasoning over complete plan compositions. C- MCTD introduces three complementary components: (1) Online Composer, which performs globally-aware planning by searching across entire plan compositions; (2) Distributed Composer, which reduces search complexity through parallel explo- ration from multiple starting points; and (3) Preplan Composer, which accelerates inference by leveraging cached plan graphs.
1 Introduction
Diffusion models have emerged as powerful framework for trajectory planning, particularly excelling in long-horizon tasks due to their ability to learn plans in a holistic manner 15 23). This stands in contrast to conventional autoregressive approaches [3] [T] which construct trajectories step-by- step. By generating trajectories as coherent wholes, diffusion planners can effectively address key challenges in long-term planning, such as sparse rewards and the accumulation of transition errors. However, these models often struggle to generate complex long-horizon plans rarely encountered in the training distribution.
To address this limitation, growing body work has explored inference-time scaling techniques, particularly by incorporating them into the diffusion denoising process (25
Among these approaches, Monte Carlo Tree Diffusion (MCTD) [32 represents a novel perspective by combining tree search with denoising. This integration enables MCTD to achieve state-of-the-arr performance across a wide range of planning tasks.
27
32 33
MCTD combines causally scheduled denoising with Monte Carlo Tree Search (MCTS) [7]. establish- ing a structured framework for deliberative planning that has shown strong performance across diverse planning domains. By decomposing trajectory generation into subplan-level tree process, which decomposes full plan into multiple subplans and systematically searches for the best combination of
*Correspondence to Jaesik Yoon and Sungjin Ahn Moussik,yoo@kkaiste and sungjin ahn @ kc.st.ac.kr>>
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

these subplans performing exploration and exploitation to escape local optima. It has demonstrated notable success in complex, long-horizor planning tasks [28] where conventional diffusion planners
often struggle, representing substantial advancement in generative planning methods.
Despite its strong performance, MCTD inherently struggles generate plans that exceed the trajectory lengths observed during training. While existing periodic replanning strategies appear to address this length limitation, they suffer from fundamental myopic decision-making problem that severely undermines their effectiveness [32]. Specifically, the replanning approaches make planning decisions based solely on local information within each limited planning horizon. It can lead to dead-end states or suboptimal paths due to the lack of consideration about the global path structure or long-term consequences. This fundamental limitation raises key research question: How can we enable MCTD to perform globally-avare planning that substantially exceeds training trajectory lengths while avoiding the myopic pitfalls of traditional replanning approaches?
To address this question, we propose Compositional Monte Carlo Tree Diffusion (C-MCTD), an inference-time scaling framework designed compose entire plans, enabling reasoning across plans rather than within subplans. The core instantiation of this framework, referred to as Online Composer, extends the tree search of MCTD the plan composition through three key components. First, stitching- batching-based tree extension connects individual diffusion-generated plans into a longer, coherent plan, enabling global reasoning beyond the limitations of isolated plan generation. Second, guidance sets as meta-actions provide configurable control parameters for the plan generation process. This mechanism enables the planner to generate targeted and adaptive high-quality plans, balancing exploration and exploitation according to its given guidance set. Third, fast replanning for simu- lation quickly approximates remaining trajectory segments using accelerated denoising methods, significantly reducing computational costs while preserving trajectory coherence during inference.
While Online Composer demonstrates strong performance across diverse environments, its sequential search procedure becomes inefficient in large state spaces due to the exponential growth in the number of candidate plan combinations. To address this challenge, Distributed Composer and Preplan Composer. Distributed Composer leverages parallel processing and plan sharing across multiple search trees to mitigate the combinatorial explosion of the search space. Preplan Composer, in contrast, preconstructs a plan graph offline, enabling more efficient inference-time planning by reducing online search overhead and improving overall performance.
introduce two specialized variants:
Experimental results demonstrate that the proposed C-MCTD methods significantly outperform standard replanning strategies based on MCTD across variety of task settings. Notably, Pre- plan Composer achieves perfect success on the challenging pointmaze-giant task, which requires generating plans approximately 10x longer than the trajectories seen during training.
The main contributions of this paper are as follows. (1) We propose Compositional Monte Carlo Tree Diffusion (C-MCTD), a novel inference-time scaling framework that fundamentally addresses the myopic planning limitations of existing approaches by enabling tree search to compose plans. (2) We provide comprehensive validation demonstrating that C-MCTD significantly outperforms existing MCTDD-ased and alternative long-horizon planning approaches across diverse planning domains.
2 Preliminaries
Terminology. This work involves multiple hierarchical concepts of trajectories that require clear distinction. A plan refers to single diffusion-generaa trajectory from the base planner. A subplan is a trajectory segment that corresponds to node in MCTD's 's tree structure. A stitched plan concatenates multiple individual plans end-to-end to extend beyond the original planning horizon. Finally, a fill plan represents a complete trajectory that successfully connects the start state to the goal state.
2.1 Diffusion models for planning
Diffusion models have been successfully applied to planning by reformulating it as a generative modeling problem 2 [5] 23 34], where trajectories are represented as sequential data comprising state-action pairs. Formally, a trajectory is denoted as x = [ dg 81; d1, 87; ar). where T is the planning horizon and (st: a,) represents the state-action pair at time step l. During inference, the trajectory is iteratively refined from an initial random noise through a sequence of denoising steps, progressively converging toward a coherent plan.

---

This approach differs fundamentally from traditional planning algorithms like Probabilistic Road Maps (PRM) [T6] and Kapidly-exploring Random Trees (RRT) [0]. Whereas traditional methods are online algorithms that actively explore the state space by querying an environment simulator or interacting with the physical world, diffusion planners operate in a fully offline setting. They learn to generate the trajectories from a static dataset of prior experiences, requiring no online environment access during the planning phase.
To ensure that generated trajectories align with specified task objectives, both classifier-free 14 and classifier-guided sampling [8] techniques have been explored in the context of diffusion planning [I] 15 In this work, we adopt the classifier-guide approach [[]], which incorporates a guidance function (x(xx to steer the generative process toward high-reware trajectories. The modified sampling distribution is defined as:
(x(x) (x) exp (Ta(x))
This guidance mechanism biases the diffusion model toward trajectories with higher expected returns, while retaining the flexibility of the original generative distribution.
Additionally, we adopt comi-autoregressive generation with causal noise schedule [2]. which selec- tively denoises uncertain tokens (typically future timesteps) while preserving causal dependencies. This approach maintains temporal consistency and significantly improves long-horizon plan quality compared to standard diffusion generation.
2.2 Monte Carlo Tree Diffusion
Monte Carlo Tree Diffusion (MCTD) 32 reformulates trajectory planning as a tree search problem, structured around three key components.
Denoising as tree rollout. Unlike conventional MCTS approaches that perform rollouts at the individual state level, MCTD operates at the level of subplans-partitionss segments of the full trajectory. trajectory is represented
= xx....., Xs), where denotes the complete trajectory and each x, is a constituent subplan. MCTD leverages a semi-autoregressivee generation strategy (2), resulting in the following factorization: p(x) = II._1 p(x, -1) This formulation preserves the global coherence characteristic of diffusion models while enabling intermediate evaluations akin to MCTS rollouts, effectively reducing the depth of the search tree.
Guidance levels as meta-actions. To balance exploration and exploitation during subplan-level expansion, MCTD introduces guidance levels as meta-actions. For example, subplan may be assigned a discrete control mode-such as GUIDE or NO _ LL_GUGDEEEVE which determines whether is sampled from the guided distribution (Equation D or the unconditional prior. This mechanism enables subplan-speciffi control over guidance, allowing for flexible and adaptive trade-offs between exploration and exploitation throughout the planning process.
Jumpy denoising as fast simulation. To enable efficient simulation, MCTD leverages fast denoising techniques such Denoising Diffusion Implicit Models (DDIM) (30 to complete the remaining noisy subplans using fewer denoising steps. Given partially generated trajectory X1:s, the remaining segments X,+1:8 are rapidly denoised as: X,+1:8 p(x,+1:5 X1:s, where g denotes the guidance level. This produces a complete trajectory & that can be used for evaluation, enabling fast and approximate rollout within the tree.
Four operation steps MCTD. MCTD adapts the four canonical steps Monte Carlo Tree Search (MCTS) to operate within the diffusion framework as follows:
(1) Selection. The tree traversed from the root using node selection policy such as UCT [1 Unlike standard MCTS, each node in MCTD corresponds to an extended subplan rather than a single state, reducing tree depth and promoting higher-level abstraction. (2) Expansion. When a leaf node is reached, meta-action- actiannttineeecaeeeeeeeeeee guidance level g is selected. A new subplan x, is then sampled conditioned on 9. (3) Simulation. After expansion. the remaining subplans are rapidly completed using accelerated denoising techniques such as DDIM [30]. Although approximate, this simulation step offers significant computational efficiency while retaining sufficient fidelity for reward-based evaluation using the reward function, r(x). (4) Backpropagation. The resulting statistics, including visitation counts and trajectory rewards, are propagated upward through the tree to update value estimates and guide future search.
3

---

Plan
Tree Connection
Prebuilt Plan Graph
(n) Replanning
(b) Online Composer
(c) Distributed Composer
Preplan Composer
Figure I: Comparison stitched planning approaches. (a) Replanning: Sequential plan generation
without exploring alternatives, leading myopic decisions. (b) Online Composer: Systematic tree search over plan combinations to avoid local optima.
(c) Distributed Composer: Parallel tree growth from multiple origins with strategic connections (red circles) for efficient exploration. (d) Preplan Leverages prebuilt plan graphs for rapid solution composition with minimal online search.
Composer:
Compositional Monte Carlo Tree Diffusion
While MCTD demonstrates strong performance complex planning tasks, it is inherently limited in the training trajectory lengths. Existing replanning strategies (Figure (a)) generate new plans when current plans end, but remain inherently myopic-making decisions based solely local information, often leading to dead-end states or suboptimal paths.
To overcome this fundamental limitation, we propose Compositional Monte Carlo Tree Diffusion (C-MCTD), a framework that constructs a globally coherent plan by composing shorter, high-quality plan segments within tree search, effectively reasoning over long-horizon dependencies. We develop three variants targeting different scalability challenges:
Online Composer (OC): Systematic tree search for composing plans with coherent reason-
ing across them.
Distributed Composer (DC): Parallel tree expansion across multiple origins to reduce search depth.
Preplan Composer (PC): Graph-based planning using precomputed waypoint connections for computational efficiency.
3.1 Online Composer
We introduce Online Composer (OC), the foundational variant of C-MCTD that addresses myopic planning through systematic plan-level tree search. OC integrates three key components: (1) stitching- based tree expansion that builds a search tree where each node represents an entire, generated plan, rather than partially denoised plan, (2) guidance
meta-actions for flexible inference-time scaling, and (3) fast replanning for efficient simulation. The approach is illustrated in Figure (b). with architecture details in Figure 2 and the core algorithm in Algorithm
Stitching-based free expansion. To implement plan-level tree search, OC performs stitching at each tree expansion by connecting the terminal state the parent node's plan the starting state of the newly generated plan. This enables each expansion to generate longer plans as the length of the plans generated from the diffusion planner 2 15 32 while systematically searching for global optima through tree exploration. The resulting trajectory is stitched sequence of plans x ix] ,x.,..,,x" xM], generated autoregressively:
A
(x 2 II Po |x x1mm-1),
(2)
m=1
where each " is complete plan from the diffusion planner.
Guidance sets as meta-actions. In MCTD 32 the guidance level-a parameter controlling the influence of guidance function generation is used as meta-action for branching the search

---

Guidancee of.
66
Algorithm Online Composer
Initialize tree T; Sstar
Salkered mods
2: while not goal reached do Select node from T
Stitching Expansion
Expasded sade
4: Expand node u via Stitching Simulate with FastRepland
Fast denoiing Value
Fast Replanaing
Eratenta (13)
6: Backpropagate rewards through T
Evalunte r(x)
end while
8: return goal meachee plan
Figure 2: Architecture of Online Composer
tree. Our approach generalizes this concept to the plan level by introducing guidance set as its meta-action. This set, comprising multiple guidance levels, enables inference-time planners (e.g.. Best-of-N or MCTD) to dynamically select the most appropriate level at each step. This mechanism empowers the planner to generate more effective and diverse local plans by adaptively modulating the guidance function's 's influence during the tree search. We empirically demonstrate the efficacy of using guidance sets in Appendix [B. By enabling more sophisticated plan generation at each compositional step, this approach significantly enhances the quality of the final stitched solutions.
Fast replanning for simulation. To accelerate planning, OC employs fast replanning inspired by jumpy denoising (30) from MCTD, Once tree expansion reaches the m-th plan, the remaining trajectory rapidly completed through a replanning process with the jumpy denoising that skips the denoising step every C' steps:
m-+MMM ~ po px (MMMM
x 1:m G),
producing complete trajectory x (xlim, s=++iM) for direct evaluation via reward function r(x). This approach reduces computational overhead while preserving long-horizon coherence. The effectiveness of this fast replanning is empirically analyzed in Appendix B.2
Scalability considerations. While OC effectively extends planning beyond training trajectory lengths, it faces scalability challenges in extremely large spaces due to exponential search growth inherent in sequential tree search 32]. These limitations are empirically demonstrated in our maze experiments (Section 5.2 To address these challenges, we introduce Distributed Composer and Preplan Composer in the following sections.
3.2 Distributed Composer
While Online Composer effectively explores plan combinations, the search space grows exponentially in long-horizon planning tasks, requiring prohibitively deep tree search. We address this challenge by introducing Distributed Composer (DC), which parallelizes tree stitching across multiple starting positions shown in Figure (c). These starting positions are identified cluster centroids from the training dataset, representing strategically significant states that are frequently traversed or serve as critical waypoints. Building on this framework, DC incorporates three key innovations: (I) guidance-orienten parallel tree search, (2) strategic tree connection, and (3) efficient path synthesis. The core algorithm of DC discussed in Algorithm 2
Guidance-oriented parallel tree search. key challenge in parallel plan-level tree search is efficiently guiding expansion from multiple starting positions. While directly connecting all position pairs enables plan stitching, this requires quadratic computational overhead for the parallelism degree. Instead, DC optimizes search efficiency by guiding each tree's expansion toward task-relevant objectives. For each tree starting position E S. the guided trajectory distribution is:
(x(sss:) (x)ss) (x)(
where Po (x{{:) is the base diffusion distribution from position 8;, and Tx(x is a task-specific guidance function biasing exploration toward planning-relevant regions. This enables each tree to prioritize expansions likely to contribute to the overall task, with connections established via strategic tree connection.
5

---

Algorithm 2 Distributed Composer
Algorithm Preplan Composer
1: Initialize trees T: on origins 8, E S
Offline: Build plan graph G on for 8; E S in parallel do
2: Initialize connectivity graph G (S,
3: while not synthesized plan found do
3:
Apply Online Composer (Alg. to find
4: for Tj on S in parallel do
local paths from Sytn 8;
5: Execute Four steps in Alg.
4:
Apply Online Composer (Alg. ! to find
6: end for
local paths from s; Sgoal
7: Update G via strategic connections
5: end for
8: Apply shortest-path synthesis
Update G with new connections
9: end while
7: Apply shortest-path synthesis on G
return synthesized plan
return synthesized plan
Distributed Composer grows multiple search trees in parallel, each from a different starting position. naive strategy would compare every node across all trees to identify connection opportunities, but this results in quadratic computational overhead. To avoid this, DC connects trees only when a plan from one tree reaches the starting position of another, narrowing the search key waypoints and enabling efficient composition without exhaustive comparison. Specifically, for trees Ti and Tj with starting positions s; and 8j, connection is attempted when:
Strategic tree connection.
[Tue, i To minpee. dist(p, 8j)
Connect (T,, TΙ)
False,
otherwise
where v.trajectory is the position sequence of node v's plan, and dist(p, 85) measures distance between position and starting position 8j. This strategically targets starting positions natural environment waypoints. When a connection is established, the connectivity graph G = =S, F) is updated:
E = E U {(5) sy, v.plan)),
(6)
where v.plan provides a feasible path from 8; to and is small distance threshold. This approach significantly reduces computational overhead by parallelizing search across multiple origins, avoiding exponential single-tree complexity. The distance threshold, is a key hyperparameter that can affect
DC's performance. We empirically analyze this effect in Appendix B.3
Efficient path synthesis. After parallel tree expansion and connection, DC constructs a connectivity graph G where nodes are the starting positions S and edges represent feasible plans between them. DC then applies classical shortest- -atte algorithms (Dijkstra [9] or A (13) to find optimal plan combinations. Search terminates when the synthesized plan satisfies task constraints (c.g., maximum episode length), ensuring computational efficiency by avoiding unnecessary exploration once a viable solution found.
Computational challenges. While DC reduces individual tree depth through parallelization, it still incurs substantial inference-time computation, particularly when exploring ultimately task-inrelevant positions. To address this inefficiency, introduce Preplan Composer in the next section, which leverages precomputed knowledge for enhanced planning efficiency.
3.3 Preplan Composer
To address DC's computational challenges, we propose Preplan Composer (PC), which amortizes planning costs through offline precomputation. As illustrated in Figure [ (d), PC pre-builds comprehensive plan graph offline, then leverages this graph during inference to guide tree search and dramatically reduce online computational overhead. The core algorithm is presented in Algorithm
Pre-building the plan graph. Unlike DC's dynamic graph construction. PC builds reusable graph by systematically exploring connections between selected starting positions. PC employs Online Composer to generate plans between waypoint pairs, guided by position-specie rather than task-specific guidance:
po(x(s;) (x((s):) exp( (disstdx,

---

where dist(x, sj) measures the minimum distance between any state in plan x and target position 83. This task-agnostic process generates reusable knowledge repository for multiple planning queries within the same environment. While this requires computationally intensive quadratic search between waypoints, the preprocessing phase allows substantial resource allocation to thoroughly sample the environment and establish reliable connections. This amortized computational overhead enables efficient online planning through the prebuilt graph, with each edge storing trajectory and cost information. A detailed analysis of this computational overhead is provided in Appendix B.5
Inference-time search. When presented with coal-conditioned planning task (Sstart, Sgoat). ). PC efficiently leverages the prebuilt plan graph for solution composition. The algorithm employs Online Composer to generate only short connecting plans: from Sstart to waypoints and from waypoints to Sgual- Since long-distn long-distance connections between waypoints are already planned in the preprocessing phase, OC focuses solely on these local connections. Using the augmented graph, PC applies shortest- path algorithms [9] [ to identify the optimal waypoint sequence forming complete solution. This approach dramatically reduces search complexity compared to DC's extensive online search, as most potential paths are pre-encoded in the graph.
4 Related work
Diffusion models for planning. Diffusion models 29 excel at long-horizon planning, particularly for sparse reward settings, by learning to generate plans holistically [
Research advances include hierarchical planning approaches for improved efficiency and long-term reasoning [5]
2
[5]
23
34
[T], hybrid planners integrating value learning policies and diffusion planning with causal noise schedule for generating causally consistent plans
Inference-time scaling diffusion planning. Recent works have explored inference-time scaling
to enhance diffusion planner reasoning capabilities [32 33). Yoon et al. [32) integrates semi- autoregressive denoising [2] with Monte Carlo Tree Search (MCTS) (7), while Zhang et al. [33
applies MCTS to diffusion models using learnable energy functions for value estimation.
Planning beyond training trajectory length. Several approaches extend planning capabilities beyond training trajectory lengths (6, [7 21 (2), primarily by modifying the training data or objectives. For instance, some methods create longer training sequences by stitching trajectories from the dataset before training the diffusion planner [6] 21]. Others introduce specialized training
objectives that encourage the model to learn compositional structures from sub-trajectories (24), or
employ dedicated value functions for long-term estimation while generating short-horizon plans (17).
Our work uniquely applies inference-ting -ieenneee-meeeeee scaling specifically for trajectory stitching, providing a training-fiee approach that extends planning capabilities without specialized training procedures or data augmentation.
Experiments
To demonstrate the effectiveness of C-MCTD in compositional long-horizon planning, we conduct comprehensive evaluation on tasks from the Offline Goal-conditioned RL benchmark (OGBench) (8]] following MCTD's experimental setup [32]. Our evaluation spans point and ant maze navigation with extended horizons, multi-cube robot arm manipulation, and partially observable visual maze tasks. All evaluated methods are diffusion planners, which, as discussed in Section 2.1 are trained on offline trajectory datasets and do not require environment interaction during training or planning. We report mean success rate (%) and planning time (seconds), averaged over 50 runs (5 tasks 10 seeds), with complete configuration details in Appendix
5.1 Baselines
We compare C-MCTD against diverse baselines spanning stitching methods and diffusion planners. For stitching approaches, we evaluate Replan (fixed-interval plan regeneration without lean- search) and DatasetStitch [6] 21 (training on concatenated trajectories). For diffusion planners, include Diffuser [15] (foundational diffusion planning), Diffusion Forcing 22] (causal noise
7

---

Table 1: Long-horizon maze navigation performance. Success rates (%) for pointmaze and antmaze environments across medium, large, and giant maze scales. The models are trained from stitch datasets. Results are presented as mean standard deviation across multiple runs.
Success Rate (%) on PointMaze 1
Success Rate (%) on AntMaze 1
Method
medium
large
giant
medium
large
giant
Diffuser-Repaan
384 6
40 0
0:::0
46
12
0::0
Diffuser-Daiin DatasetStitch
32 22
0:
0::0
12: 10
Diffusion Forcing (DF)
53 16
20
0::0
60 13
26 9
0 0
DF-DatasetStich
52 23
26 13
0::
24
6
0:::0
SSD
40 0
40 0
0
12 9
0= 0
0+: 0
CompDiffuser
100
100
68
96 2
86# 2
654
MCTD-Replat
90 14
20 0
0#:0
75
30 10
0 0
MCTD-DatasetSticch
12. 10
2 6
01
87 13
6.1.
0.1 0
Online Composer
934 9
82# 17
0#:0
98 6
94::
12: 16
Distributed Composer
100
100
26
98:
93+
21 14
Preplan Composer
100
100
100: 0
94
94:
75 18
Table 2:
Run time and plan quality comparison. The time (sec.) search and the generated plan quality (the required interaction steps to reach the goal) on the pointmaze environment with medium, large, and giant mazes when trained from the stitch datasets.
Run Time (sec.) |
Plan Length +
Method
medium
large
giant
medium
large
giant
Online Composer
83.6 318
91.2+ 35.7
269.8 51.0
595.7 56.1
743.5 53.6
1000.0: 0.0
Distributed Composer
26.7
39.1
530.7 108.8
493.3 98.2
608.5 75.1
971.7 24.6
Preplan Composer
11.1 0.2
21.5 0.4
36.9 0.3
143.8: 1.1
256.8 0.9
451.9 1.9
scheduling for long-horizon control), SSD 17 (stitching diffusion planner via learned value function
guidance). CompDiffuser (24) (stitching diffusion planner with sub-trajectory dependency modeling), and MCTD [32 (direct comparison for plan-level vs. in-plan search). Complete details are provided
in Appendix A.3
5.2 Long-horizon maze navigation: scaling beyond trained trajectory length
We evaluate the effectiveness of C-MCTD on long-horizon tasks using PointMaze and AntMaze environments from OGBench, which require planning trajectories up to 1000 steps despite training
on significantly shorter sequences (100 steps). Following prior work [15] (2], PointMaze uses
heuristic controller while AntMaze employs a learned value-based policy 31..
Baseline performance degrades with complexity. Table ] reveals that conventional stitching methods (Replan, DatasetStitch) exhibit severe performance drops as maze complexity increases, with most methods achieving 0% success on giant mazes. Notably, CompDiffuser achieves strong performance on smaller mazes but degrades sharply in giant environments (68% vs. 100% on medium/large), highlighting the critical need for flexible plan-level search escape the local optima in complex long-horizon scenarios.
C-MCTD demonstrates superior scalability. Our methods show strong robustness across all maze sizes. Preplan Composer achieves perfect 100% success on PointMaze- significantly outperforming the best bascline (CompDiffuser 68%). Online Composer excels medium and large mazes but struggles in giant environments due to exponential search space growth. Distributed Composer outperforms Online Composer medium and large mazes through parallel tree stitching. However, it faces challenges in giant mazes, as its synthesized plans often fail to meet the strict episode length constraint. When we relaxed the maximum episode length from 1000 to 2000 steps, DC's success rate improved to 86%. The qualitative result comparison between C-MCTD variants is shown in Figure
Efficiency analysis reveals computational trade-offs. Table demonstrates that Distributed and Preplan Composers achieve superior efficiency through parallelism and amortized graph structures
8

---

Table 3: Robot arm cube manipulation performance. Success rates (%) across increasing complex- ity manipulation tasks involving single, double, triple, and quadruple cube arrangements in OGBench, presented as mean + standard deviation.
Success Rate (%)
Method
single
double
triple
quadruple
Diffuser-Replan
924
12
44
01
Diffusion Forcing
100+
18:
16:
0
MCTD-Replan
100: 0
78 11
40 21
24 8
Online Composer with Plan Cache
100
100=0
75 12
82: II
respectively. Preplan Composer produces notably shorter, higher-quality plans through its pre-built graph approach, achieving the best computational efficiency while maintaining perfect success rates.
5.3 Multi-object manipulation: compositional planning with plan caching
We evaluate C-MCTD multi-cube manipulation tasks from OGBench 28 which require precise action sequencing for stacking cubes into predefined configurations. These tasks demand compo- sitional reasoning to determine optimal cube movement sequences, making them ideal for testing plan-level search capabilities. Our approach combines diffusion-based high-level planning with low-level value-guided control and object-wise guidance described in prior work 4 32
Method adaptation for manipulation tasks. For these specialized tasks, we exclude Distributed and Preplan Composers since parallel tree stitching from random positions proves inefficient for precise manipulation sequences. Instead, we implement a plan cache mechanism that stores and retrieves previously generated plans for identical scenarios, significantly enhancing search efficiency (detailed analysis in Appendix [B.4).
Baseline performance degrades with task complexity. Table shows that while MCTD-Replan
outperforms Diffuser-based approaches due to object-wise guidance capabilities [32), its effective- ness diminishes substantially complexity prreases-ddoppiine from 100% (single cube) to 24% (quadruple cube). This performance degradation highlights the limitations the baseline's search strategy in complex sequential manipulation tasks.
Online Composer excels through compositional search. In contrast, our Online Composer with Plan Cache demonstrates robust performance across all complexity levels. It achieves 100 % success rate on single and double cube tasks and maintains strong performance on more difficult scenarios, succeeding in 75% of triple-cube and 82% of quadruple-cube tasks. These results underscore the effectiveness of our compositional search approach, where the plan cache enables the efficient reuse of sub-solutions across related manipulation sequences.
5.4 High-dimensional visual navigation: POMDP planning challenges
We evaluate C-MCTD on Visual Maze tasks from prior work [32], which require navigation from start- ing observations to target goals within 64 x 64 RGB observation spaces-foree Observable Markov Decision Processes (POMDPs).
Table 4: Visual PointMaze results.
Success Rate (%)
Method
medium
large
challenging Partially
Diffuser
8 13
0=
Diffuser-Replan
8 10
0 0
Following established protocols (32]
employ Variational Autoencoders [8] for latent space plan- ning, inverse dynamics models for action generation, and positional estimators for POMDP guidance (de- tails in Appendix ).3.3).
Diffusion Forcing
66 32
8
MCTD
82
0=:
CCTD-Replan
90
20 21
Online Composer
100 000
54 18
Distributed Composer
94 1
26 9
Preplan Composer
96
48
Myopic planning fails in complex visual environ-
ments. Table shows that while MCTD-EB MCTD-Replan achieves strong performance medium mazes (90%), it suffers substantial degradation on large mazes (20%), demonstrating the limitations of myopic plan generation in high-dimensional partially observable settings.
Online Composer excels through plan-level reasoning. Online Composer significantly outper- forms all baselines, achieving perfect success medium mazes and maintaining strong performance

---

on large mazes (54% vs. 20% for ICTTD-Replan) This demonstrates the effectiveness of plan-level tree search for overeoming myopic limitations in visual navigation tasks.
High-dimensional challenges limit parallel variants. Interestingly, Distributed and Preplan Com- posers underperform compared Online Composer-contraanee 5.2..5.2). Our analysis reveals that clustering meaningful waypoints in high-dimensional latent spaces proves challenging, hindering efficient plan integration. This limitation highlights an important direction for future research in visual POMDP planning.
with maze experiments (Sec-
6 Discussion
In this work, we introduced Compositional Monte Carlo Tree Diffusion (C-MCTD), a novel frame- work that integrates plan-level search into diffusion-based planners. This approach enables compo- sitional reasoning. allowing for generalization to training data. While our experiments demonstrate significant performance gains, is important to discuss the inherent trade-offs of our method and the broader challenges that remain for diffusion planning models.
tasks far exceeding the scope of the
Limitations and trade-offs of C-MCTD variants. The primary challenge of C-MCTD is the computational cost associated with searching vast compositional plan space. We introduced Distributed Composer (DC) and Preplan Composer (PC) to mitigate this cost through parallelism and amortized graph search, respectively. However, these variants introduce their own trade-off'. PC requires a rre-ooputationn to build the graph. It is highly efficient and is suited for the environments where the graph can be reused across many queries. DC's parallel tree stitching is powerful for spatial navigation but can be less efficient for tasks requiring precise sequential dependencies, as seen in our manipulation experiments Section 5.3 These trade-offs highlight that the optimal C-MCTD variant is task-dependent, a key insight for future applications.
Future directions for diffusion planning models. Looking forward, key challenge for C-MCTD and other diffusion planners is achieving real-time inference speeds suitable for online robotics applications. Bridging this efficiency gap is critical avenue for future work. Furthermore, our work inherits two fundamental limitations of the current generative planning paradigm. First, generalization to entirely novel environments remains difficult, as planners can produce kinematically invalid plans when faced with out-of-diste d-dsttiibution states. Second, handling stochastic dynamics is an open problem, as standard diffusion models may generate an ineffective "averaged" plan rather than a robust, multi-modal policy.
Despite these open challenges, C-MCTD marks critical step toward creating more general, scalable, and compositional generative planners, paving the way for solving increasingly complex decision- making problems.
Conclusion
We introduced Compositional Monte Carlo Tree Diffusion (C-MCTD), novel framework that scales diffusion-based planners to generate complex, long-horizon plans by composing shorter trajectories at inference time. C-MCTD integrates three complementary approaches: the Online Composer for flcxible, on-the-fly plan generation; the Distributed Compaser for scaling through parallelism; and the Preplan Composer for maximum efficiency via pre-computed plan graphs. Our extensive evaluations show that this compositional framework significantly outperforms conventional replanning strategies. Notably, the Preplan Composer solves tasks requiring trajectories up 10x longer than those seen during training. These results demonstrate that compositional scaling at inference time can dramatically enhance the reasoning capabilities of diffusion planners. Crucially, this is achieved without any model retraining, offering practical and effective path toward more capable agents for challenging sequential decision-making problems.
Acknowledgments and Disclosure of Funding
We would like to extend our gratitude to Doojin Baek for his insightful discussions and assis- tance throughout this project. This research was supported by Brain Pool Plus Program (No.
10

---

2021HID3A2A051006655 through the National Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT (MSIT), Institute Information & communications Technology Plan- ning & Evaluation (ITTP) grant funded by the Korea government (MSIT) (No. RS-2024-00500929), Global Al Frontier Lab), and GRDC (Global Research Development Center) Cooperative Hub Pro- gram (RS-2024-004361
through the National Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT (MSIT).
References
[1] Anurag Ajay, Yilun Du, Abhi Gupta, Joshua Tenenbaum, Tommi S. Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision making? In International Conference on 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. In Advances on Neural Information Processing Systems, 2024.
[3] Chang Chen, Yi-Fu Wu, Jaesik Yoon, and Sungjin Ahn. Transdreamer: Reinforcement learning with transformer world models. arXiv preprint arXiv:2202.0948) 2022.
[4] Chang Chen, Junyeob Back, Fei Deng, Kenji Kawaguchi, Caglar Gulcehre, and Sungjin Ahn. PlanDQ: Hierarchical plan orchestration via d-conductor and q q-performer. In International Conference on Machine Learning, 2024.
[5] Chang Chen, Fei Deng, Kenji Kawaguchi, Caglar Gulcehre, and Sungjin Ahn. Simple hier- archical planning with diffusion. In International Conference Learning Representations, 2024.
[6] Chang Chen, Hany Hamed, Doojin Baek, Taegu Kang, Yoshua Bengio, and Sungjin Ahn. Extendable long-horizon planning via hierarchical multiscale diffusion. arXiv preprint arXiv: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 on image synthesis. In Advances in Neural Information Processing Systems, 2021.
[9] Edsger W Dijkstra. A note two problems in connexion with graphs. In Edsger Wybe Dijkstra: his life, work, and legacy, pages 287-290. 2022.
[10] Zibin Dong, Jianye Hao, Yifu Yuan, Fei Ni, Yitian Wang, Pengyi Li, and Yan Zheng. Diffuserlite: Towards real-time diffusion planning. In Advances in Neural Information Processing Systems, 2024.
[11] David Ha and Jürgen Schmidhuber. World models. In Advances in Neural Information Processing Systems, 2018
[12] Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning behaviors by latent imagination. In International Conference on Learning Representa- tions, 2020.
[13] Peter Hart, Nils Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
[14] Jonathan Ho and Tim Salimans. arXiv:2207. 1..007./2500 12598, 2022.
Classifier-free diffusion guidance.
arXiv preprint
[15] Michael Janner, Yilun Du, Joshua Tenenbaum, and Sergey Levine. Planning with diffusion for flexible behavior synthesis. In International Conference on Machine Learning, 2022.
11

---

[16] Lydia E Kavraki. Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in dige-diiensional configuration spaces. IEEE transactions on Robotics and Automation, 12(4):566-58) 1996.
[17] Sungyoon Kim, Yunseon Choi, Daiki E Matsunaga, and Kee-Eung Kim. Stitching sub- trajectories with conditional diffusion model for goal-conditioned offline rl. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[18] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International conference on Learning Representations, 2014.
[19] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, 2006.
[20] Steven La Rapidly-exploris random trees: A new tool for path planning, Research Report 9811, 1998.
[21] Guanghe Li, Yixiang Shan, Zhengbang Zhu, Ting Long, and Weinan Zhang. DiffStitch: Boost- ing offline reinforcement learning with diffusion-based trajectory stitching. In International Conference on Muchine Learning, 2024.
[22] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 1982.
[23] Haofei Lu, Dongqi Han, Yifei Shen, and Dongsheng Li. What makes good diffusion planner for decision making? In International Conference on Learning Representations, 2025.
[24] Yunhao Luo, Utkarsh A Mishra, Yilun Du, and Danfei Xu. Generative trajectory stitching through diffusion composition. arXiv preprint arXiv:2503.05153, 2025.
[25] Nanye Ma, Shangyuan Tong, Haolin Jia, Hexiang Hu, Yu-Chuan Su, Mingda Zhang. Xuan Yang, Yandong Li, Tommi Jaakkola, Xuhui Jía, al. Inference- time scaling for diffusion models beyond scaling denoising steps. arXiv preprint arXiv:2501.09732. 2025.
[26] James MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume I: Statistics, 1967.
[27] Yuta Oshima, Masahiro Suzuki, Yutaka Matsuo, and Hiroki Furuta. Inference-time text-to-video alignment with diffusion latent beam search. CORR, 2025.
[28] Seohong Park, Kevin Frans, Benjamin Eysenbach, and Sergey Levine. Ogbench: Benchmarking offline goal-conditioned rl. In International Conference on Learning Representations (ICLR), 2025.
[29] Jascha Sohl- Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International conference on machine learning, 2015.
[30] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021.
[31] Zhendong Wang, Jonathan J Hunt, and Mingyuan Zhou. Diffusion policies an expressive policy class for offline reinforcement learning. International Conference on Learning Representations, 2023.
[32] Jaesik Yoon, Hyeonseo Cho, Doojin Baek, Yoshua Bengio, and Sungjin Ahn. Monte carlo tree diffusion for system 2 planning. In International Conference on Machine Learning, 2025.
[33] Tao Zhang, Jia-Shu Pan, Ruiqi Feng and Tailin Wu. Test-time scalable mets-enhanced diffusion model. arXiv preprint 20Xiv:2502.01989 2025.
[34] Guangyao Zhou, Sivaramakrishnan Swaminathan, Rajkumar Vasudeva Raju, J Swaroop Guntu- palli, Wolfgang Lehrach, Joseph Ortiz, Antoine Dedieu, Miguel Lázaro-Gredilla, and Kevin Murphy. Diffusion model predictive control. arXiv preprint arXiv:2410.05580 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
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We proposed that our proposed method shows the effectiveness to extend the reasoning abilities beyond single plan length in abstract and introduction, which are the main contribution of this paper and well fitted in this paper contents.
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:
The limitation is discussed in the main paper as a separate section.
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 approxinations 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 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 are taken in low lighting. Or speech-to-text system might 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's
Question: For each theoretical 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: [Yes]
Justification: The details the implementation in the appendix including the hyperparame- ters and benchmark settings are discussed in our appendix.
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 a 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS 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 to 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 dataset 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 reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to 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 the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The source code will be prepared to be as release version after the reviewing process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
gablic//uides/Codeee /ttp///eesmisssssooooolooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //niss.ccpuulic//uuus http://////iiiee///deuuubiiiiiii
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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
15

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details about training and test are discussed in the main paper and appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The performance (success rate) and running time are reported with the standard deviation the multiple testing.
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, at 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 run 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 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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, the computer resources utilized in the training and test are discussed in the paper.
Guidelines:
16

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:h/pw..aaae....opoooooo/eeee
Answer:
[Yes]
Justification:
We checked the NeurIPS code of Ethics and followed them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances 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: This paper presents foundational research in the inference-time scaling diffusion model over the single generation range, which primarily focused on theoretical improvements rather than specific applications with direct societal implications.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 to point out 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML.)
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
17

---

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 for controlled use of the model, for example by requiring that users adhere 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
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 dataset.
The authors should state which version the asset used and, 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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
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 the dataset/codeemoodll as part 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 an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to 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 crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, 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
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/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 to 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 an 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 LLM policy for what should or should be described.
wwwpearrpps.c//oofeeeeeeeeeeeeee /
19

---

start
goal
L (a)
(b)
(c)
Figure 3: Illustrations of the environments. Our method is evaluated on three distinct tasks: (a) A long-horizon maze where the agent must navigate from a start to a goal state. (b) A robotic manipulation task requiring precise control of robotic arm. (c) A visual maze task where observations are provided as first-person view images.
A Experiment details
A.1 Computation resources
All experiments were conducted on high-performance hardware consisting of 8 NVIDIA RTX 4090 GPUs, 512GB system memory, and a 96-thread CPU. Training each model required about hours, while inference for comprehensive experimental evaluation took up hour in the most computationally intensive cases.
A.2 Environment details
To evaluate our C-MCTD, we adopt the benchmarks from Yoon et al. [32. While the robotic manipulation and visual maze tasks replicate the environmental settings of the prior work, we introduce more demanding evaluation for the long-horizon maze environments. Specifically, we employ the stitch datasets from Park et (28 rather than the navigate datasets. This choice creates a challenging scenario that requires generating plans significantly longer than the trajectories observed during training. For instance, training trajectories are limited to 200 steps, whereas successfully reaching goals in the test environments requires plans of up 1000 steps. This setting allows to rigorously assess the extendable planning capabilities of our approach. An overview each task provided in Figure
A.3 Baselines
To evaluate C-MCTD, we compare its performance against diverse baselines. These baselines combine different stitching methods with various diffusion planners to extend their effective planning horizons. We describe the core components below.
A.3.1 Stitching methods
Replan. This baseline addresses the fixed-horizon limitation of standard diffusion planners, which are constrained by the trajectory lengths in the training data. The Replan method operates by iteratively generating a new plan from the final state of the previous one. While this enables extendable planning, the myopic nature of each planning step often results in suboptimal long-horizon solutions.
DataStitch. 6 21l An alternative approach, which term DataStitch, extends the planning horizon by first elongating the trajectories within the training dataset itself. Because trajectories in the original dataset are not necessarily connectable, this method involves training auxiliary diffusion planners and inverse dynamics models to generate synthetic continuations, effectively stitching existing data points together. For instance, Chen al. ( iteratively applied this process to extend trajectories up to sevenfold. Following this methodology, we create an extended version of the stitch dataset by lengthening trajectories five times their original length and subsequently train our models on this augmented data.
20

---

A.3.2 Diffusion planners
As primary baseline, we include Diffuser, which pioneered training diffusion models on sequences of concatenated state-action pairs. We evaluate Diffuser with both the Replan and DataStitch extension methods by training it on the corresponding augmented datasets.
Diffuser. 15
Diffusion Forcing.
This Diffuser variant tokenizes data and applies varied noise levels enable causal denoising that prioritizes near-future states. We employ the Transformer-base implementation proposed by Chen al. (2). As the method is inherently designed for replanning, we evaluate it with the DataStitch extension but do not create separate "Replan" variant.
Sub-trajectory Stitching with Diffusion (SSD). 17 Kim et al. [17] introduced diffusion planner that achieves extendability via a learned value function, which guides the model to concatenate short trajectories into longer, task-relevant plan. While effective, empirically found that learning reliable value function is challenging with suboptimal data, whereas inference-time scaling offers more robust alternative. Because SSD is natively designed for extendable planning, we do not evaluate it using our Replan or DataStitch extensions.
24 Lao et al. 24 proposed an alternative approach to extendable planning where diffusion model is trained to generate sub-trajectories conditioned on nearby context. This framework allows the model to compose multiple sub-trajectories, gener- ating plans that are longer than any seen during training. Similar to SSD, CompDiffuser's native extendability makes evaluation with our proposed extensions unnecessary.
Compositional Diffuser (CompDiffuser))
introduced framework that imple- ments inference-time scaling by branching the denoising process into a Monte Carlo Tree Search, rather than merely increasing sequential denoising steps. Guided by a reward function, this approach explores alternative paths to find optimal solutions, demonstrating superior performance across diverse planning tasks. We evaluate MCTD with both the Replan and DataStitch extension methods.
Monte Carlo Tree Diffusion (MCTD).
Yoon et
A.4 Model hyperparameters
Our hyperparameter configuration largely adopted from Yoon et al.
32 For full reproducibility.
provide the detailed configurations for the baseline models in Tables 3 Hyperparameters introduced by our proposed C-MCTD are detailed in Section A.3 alongside their corresponding experimental setups. For the SSD baseline, we utilized the default configurations from its official public implementation
A.5 Evaluation details
This section outlines the configurations for each benchmark.
A.5.1
Long-horizon maze environments
Datasets and environment configuration. To evaluate extendable planning, all models were trained on the challenging stitch datasets. An exception was made for the value-learning policy [31]. which failed converge on this data; as this baseline not our focus, we trained it on the original navigate dataset. For all maze environments, we set the training trajectory length and the single-pass planning horizon 100, sampling sub-sequences from the full 200-step trajectories enhance data diversity. Following prior work [32), we remove random noise from the start and goal positions to isolate the planner's performance from environmental stochasticity. Furthermore, we employ a heuristic controller for PointMaze environments [15] and a value-based policy for AntMaze for which we set the subgoal interval
environments
Guidance mechanism. To steer the diffusion process, we apply a guidance function that minimizes the L2 distance between each planned state x; and the goal g [2] [2]. This function, defined as E; ||=; gll2. is used across all models. The strength of this guidance is controlled by a scale hyperparameter, which we configure for each baseline as follows:
21

---

Table 5: Hyperparameters for the Diffuser baseline. These settings are adopted from the original MCTD paper [32 to ensure a fair comparison. Task-specific parameters, such as the planning horizon, are detailed their respective sections.
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
2 x 10-1
Batch Size
32
Max Training Steps
20,000
EMA Decay
0.995
Floating-Poinn Point Precision
32-bit (FP32)
Diffusion & Guidance Settings
Beta Schedule
Cosine
Objective
un-prediction
Guidance Scale
0.1
Open-loop Horizon
50 (for Diffuser-Replan)
Model Architecture (U-Net)
Depth
4
Kernel Size
5
Channel Sequence
32,
128, 256
Diffusion Forcing: Following Chen et al. [2, we set the guidance scale to 3 for medium maps and 2 for large and giant maps.
MCTD:
The guidance sets are adopted from Yoon al. [32 (0, 0.1, 0.5, 1,2] for Point- Maze (Medium & Large), (0.5, 1,2,3, 4} for PointMaze (Giant), and 2, 5) for all AntMaze tasks.
Our proposed C-MCTD variants inherit these settings; during node expansion, each of the two child nodes is assigned the corresponding guidance set for the environment.
Reward function for tree search-based planners. Both MCTD and C-MCTD require a reward function to evaluate simulated trajectories. We adopt the function from Yoon al. [2), which incorporates two components. First, it penalizes physically implausible plans by assigning a reward of ( any trajectory with unrealistic position changes between consecutive states. Second, for valid trajectories that first reach the goal at timestep 1, the reward is calculated as r = (H t)/ H, where Il is the maximum horizon length. This encourages finding shorter, more efficient paths.
C-MCTD configurations.
Node expansion planner:
For node expansion in the maze environments, C-MCTD utilizes best-of-N search-base planner (34) built upon Diffusion Forcing (2). In this approach. N candidate trajectories are generated, and the one yielding the highest reward (as defined above) selected. We N 50 for all maze experiments.
DC and PC variants: Our Distributed Composer (DC) and Preplan Composer (PC) variants identify representative waypoints via k-means clustering (22 26 on the training data, with 10, 30, and 70 cluster centers for medium, large, and giant maps, respectively. For DC. the search is capped at 100 iterations. For PC, we limit the search to 20 iterations and plan concatenations (a tree depth of 2) for medium and large maps; these are reduced to 10 iterations and I concatenation for the giant map. These settings render our methods substantially more efficient than the Online Composer baseline, which requires up 500 search iterations and 10 concatenations.
22

---

Table Hyperparameters for the Diffusion Forcing baseline. Settings are based on the implementa-
tion in Yoon et al. [22 and adapted for our tasks. Parameters that vary across environments, such as the guidance scale, are specified in Section A.5
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
x 10-1
Weight Decay
10-4
Warmup Steps
10,000
Batch Size
1024
Max Training Steps
200,005
Training Precision
16-bit (Mixed)
Inference Precision
32-bit (FP32)
Diffiasion & Sampling Settings
Beta Schedule
Linear
Objective
prediction
Scheduling Matrix
Pyramid
Stabilization Level
10
DDIM Sampling
0.0
Frame Stack
10
Open-loop Horizon
50
Causal Mask
Not Used
Model Architecture (Transformer)
Embedding Dimension
128
Number of Layers
12
Number of Attention Heads
FFN Dimension
512
A.5.2 Robot arm manipulation environment
Environment and baseline configuration. We conduct these experiments using the play datasets. The planning horizon is set to 200 for single-cube tasks, corresponding to the maximum episode length, and extended 500 for more complex multi-cube tasks. Similar the AntMaze experiments, we employ a value-based policy 31 as a low-level controller, with a subgoal interval of 10.
Guidance mechanism. The goal-reaching guidance function is identical to that used in the maze environments (Section A.3.T). For the Diffusion Forcing baseline, the guidance scale is set to 2. For tree-search planners (MCTD and C-MCTD), we adopt the object-wise guidance strategy from Yoon et al. [32]. This approach guides the planner to manipulate single cube at time, preventing physically infeasible plans that attempt to move multiple objects concurrently. The guidance set for this strategy is {1, 2, 4], which our C-MCTD variants inherit for two child nodes during expansion.
Reward function. We adopt the reward function from Yoon et al. [32], which is designed to filter physically unrealistic trajectories. A plan receives reward of 0 if it violates any of the following conditions: (1) moving multiple objects simultaneously; (2) leaving an object in an unstable, mid-air position; (3) causing inter-object collisions; (4) attempting grasp object obstructed by another. Otherwise, a positive reward is assigned based on task success.
Macro-actions for planning efficiency. Following Yoon et al. we incorporate a of pre- defined macro-actions (scripted primitives) to improve the efficiency and robustness of obje planning. These routines handle common operations, such as automatically releasing an object at its target or pre-positioning the arm before manipulating the next object. This scripting approach prevents common planning failures, like generating trajectories beyond the arm's 's kinematie reach or attempting to grasp with an occupied gripper.
23

---

Table Hyperparameters for the Monte Carlo Tree Diffusion (MCTD) baseline. These settings are
based on the original implementation [2 Task-dependen parameters, such as the planning horizon and guidance set, are specified in Section A.5
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
x 10-4
Weight Decay
10-4
Warmup Steps
10,000
Batch Size
1024
Max Training Steps
200,005
Training Precision
16-bit (Mixed)
Inference Precision
32-bit (FP32)
Diffusion & Sampling Settings
Beta Schedule
Linear
Objective
Po-prrdiition
DDIM Sampling ?
0.0
Frame Stack
10
Open-loop Horizon (MCTD-Replan)
50
Causal Mask
Not Used
Scheduling Matrix
Pyramid
Stabilization Level
10
MCTD Search Setrings
Max Search Iterations
500
Partial Denoising Steps
20
Jumpy Denoising Interval
Model Architecture (Transformer)
Embedding Dimension
128
Number of Layers
12
Number of Attention Heads
4
FFN Dimension
512
C-MCTD configurations. strategies:
For the robot manipulation tasks, C-MCTD employs two specific
Node expansion planner: Unlike in the maze environments, node expansion utilizes the full MCTD planner instead of the simpler best-of-N search. This choice is necessitated by the significantly longer planning horizons in this domain (200-500 steps), which demand more powerful and systematic search capability.
Plan caching:
To improve computational efficiency, introduce plan caching strategy. Successfully generated plans are stored with their metadata (target object, start, and goal states). A cached plan reused for task if its target object is identical and its start/goal states fall within an L2 distance of from the cached ones.
A.5.3 Visual maze environment
Environment and data configuration. We follow the experimental setup from Yoon et al. B2 for the visual maze tasks. Using the data generation scripts from Park et (28), we create datasets of 1000-step trajectories for both medium and large maps. To ensure diverse training samples, our diffusion models are trained on sub-trajectories with a planning horizon of 500, sampled from these full-length trajectories.
24

---

Table Hyperparameters for the value-learning policy baseline. These settings are configured for training the policy on the navigate dataset.
Hyperparameter
Value
Training & Optimizer Settings
Learning Rate
10-1
Training Epochs
2,000
Gradient Clipping Norm
7.0
Aggorithm-Specifee Settings
Learning ?
1.0
Max Q Backup
False
Reward Tune
cqI cql_antmaze
Top-k
Target Update Steps
10
Data Sampling Randomness (p)
0.2
Vision-based modeling pipeline. To handle the high-ding sigh-dimensional visual inputs and partial observ- ability, we adopt the modeling pipeline from Yoon al. (32), which consists of three pre-trained components that operate on 64 x 64 x 3 RGB observations:
Variational Autoencoder (VAE); VAE is first pre-trained to encode each image observation into a compact 8-dimensional latent representation, This latent space serves as the basis for all subsequent planning and control models.
Inverse dynamies model: An MLP-based inverse dynamics model, finy. is trained predict the action å, required to transition between latent states. To infer velocity from static images, the model is conditioned on three consecutive latent states: à fin (2t-1 2t, 2++1). This learned model acts as a low-level controller.
Position estimator: A separate MLP is trained to predict the agent's approximate (x, y) coordinates from a given latent state žt. This provides a weak positional signal for planning guidance without compromising the task's 's partial observability.
Guidance Mechanism. Guidance is performed in the state space using the positional signal from the pre-trained position estimator. This allows us to apply the same 1.2 distance-based guidance function as described in Appendix [..5I] Following Yoon al. (32), we use a guidance set of {0, 0.1,0.1.... 1, 2 for all baselines. Our C-MCTD variants inherit this configuration, assigning this guidance set each child node during an expansion.
C-MCTD Configurations. For our Distributed Composer (DC) and Preplan Composer (PC) variants, we generate representative waypoints by applying k-means clustering to the coordinates predicted by the position estimator. We define 3 and 5 cluster centers for the medium and large maps, respectively.
25

---

Table 9: The guidance sets meta-action ablation study on PointMaze environments. Success
rate (%) comparison with the variant of Online Composer with fixed guidance level as a meta-action rather than guidance set, presented as mean standard deviation.
Success Rate (%) 1
Environment
Default
Fixed: 0.1
Fixed: 0.5
Fixed:
Fixed: 2
PointMaze Medium
93#9
80=0
90+
9
83# 8
PointMaze Large
82+ 17
77 14
52 13 27= 10
20 0
Table 10: The Fast replanning ablation study on PointMaze environments. Success rate (%)
comparison with the variant of Online Composer without fast replanning, presented as mean + standard deviation. The numbers in parentheses indicate the maximum search iterations allowed.
Success Rate (%)+ t
Enivornment W/ FR (200)
W/o FR (200)
W/ FR (100)
W/ FR (100)
W/FR (50)
W/o FR (50)
PointMaze Medium
9618
621
94
76
92_ 10
631
PointMaze Large
84 +
54= 13
82
49
82: 19
32= 11
B Additional experimental results
B.1 Ablation Study on Guidance Sets as Meta-actions
Our framework enables C-MCTD to provide the planner with a guidance set as a meta-action (e.g.. {0, 0.1, 1, 1,2)), rather than single value. To experimentally isolate the benefit of this design, compare our default approach against variants that use a single, fixed guidance level.
The results in reveal that the optimal guidance level is task-dependent. In PointMaze-Medine which requires moderately complex planning, higher guidance levels (e.g.. 0.5 and 1.0) yield strong performance. Conversely, the more challenging PointMaze-Laree environment necessitates a low guidance level (0.1) to achieve a competitive result.
Notably, our default method, which provides the planner with set of guidance options. achieves robustly high performance across both environments. This demonstrates that the guidance set is vital mechanism that empowers the planner to adaptively select the most suitable guidance strength for a given task. This adaptability key ensuring effective and versatile performance across varying levels of environmental complexity.
B.2 Ablation Study on Fast Replanning
Fast Replanning is a core component of C-MCTD. To validate its contribution, we conducted an ablation study comparing the performance of the Online Composer with and without this mechanism across various search budgets. The experiments were performed in the maze environments. We omit results from PointMaze Giant as the performance difference was negligible.
As presented in Table 10 the results demonstrate the critical role of Fast Replanning. In configura- tions, the version with Fast Replanning consistently outperforms its counterpart. This performance gap becomes more pronounced as the search budget decreases. For instance, in the PointMaze Large environment with search budget of 50 iterations, method with Fast Replanning maintains high success rate of 82%, whereas the variant without it experiences a substantial performance degradation, dropping to 32%.
This analysis confirms that Fast Replanning is not merely an incremental optimization but a crucial element for the robustness and sample efficiency of our tree search algorithm. It enables effective value propagation throughout the search tree, particularly under limited computational budgets.
B.3 Ablation Study on Stitching Threshold
We investigate the sensitivity of C-MCTD to the stitching threshold hyperparameter, e. our main experiments, set 1.0, adopting the value from the goal-achievement threshold in the original
26

---

Table 11: The stitching threshold ablation study on PointMaze environments. Success rate (%) comparison with the variant of Distributed Composer with diverse stitching threshold hyperparameter values, presented as mean
standard deviation.
Success Rate (%) 1
Environment
5.0
2.0
1.0
0.5
0.1
PointMaze Medium
100 0
100=
100
100= 0
94+
PointMaze Large
65 16
100
100
100 0
73
PointMaze Giant
40
26
26
10
0=
Table 12: The plan cache ablation study on robot arm cube manipulation tasks. Run time (sec.) comparison between the versions with and without plan cache, presented as mean standard deviation.
Run Time (sec.) 4
Method
single
double
triple
quadruple
OnlineComposer
19.4 0.3
50.5
308.4 4 33.5
1432.8
300.1
OnlineComposer with Plan Cache
19.4 0.2
4
166.9. L 27.1
242.8 1 16.1
To analyze the robustness of our method to this choice, we conducted an extensive ablation study with our Distributed Composer.
MCTD framework 32
Our analysis, presented in Table TT. reveals that the optimal stitching threshold e highly dependent on task complexity. In the PointMaze Medium environment, which represents simpler planning problem, our method exhibits strong robustness. Optimal performance is maintained across broad range of e values (0.5 to 5.0), with only minor degradation observed at the highly restrictive threshold of 0.1. For the more challenging PointMaze Large environment, a clear trade-off emerges. An overly permissive threshold (e.g., 5.0) results in spurious stitching, such as incorrectly connecting trajectories across physical barriers, thereby degrading performance. Conversely, an overly restrictive threshold (e.g.,
0.1) prevents valid connections, impairing the construction of long-horizon solutions. This highlights the existence of an optimal range for e in moderately complex tasks. Intriguingly, in the most complex PointMaze Giant environment, more lenient threshold (e 5.0) yields the best performance. The vast scale of this environment makes connecting distant states inherently difficult. A larger increases the likelihood of successful stitching, facilitating the formation of long-range plans. In this scenario, maximizing connectivity, even at the cost of some precision, is more effective than enforcing high-precision stitching that results in sparse failed connections.
B.4 Ablation Study on Plan Caching
To quantify the computational efficiency gained by plan caching method, conducted an ablation study on robotic manipulation tasks increasing complexity. The results, summarized in Table 12 measure the wall-clock time required to solve tasks involving one four cubes.
For tasks with one or two cubes, the runtime difference minimal, as the planning overhead is low. However, as the task complexity increases, the benefits of plan caching become exponential. This due to the combinatorial explosion of the planning space multi-object manipulation. For the four-cube task, our method with plan caching achieves approximately 6x runtime reduction in runtime compared to the baseline without caching (242.8s vs. 1432.8s). These results confirm that plan caching is effective strategy for mitigating the computational burden in complex tasks with large, structured planning spaces.
B.5 Analysis of Preplan Composer's Graph Construction Overhead
The Preplan Composer (PC) variant relies on a one-time, offline graph construction process. In this section, we quantify this computational overhead and contextualize by comparing the cost to the online planning times of our other methods. We emphasize that this is pre-inference step performed only once per environment. All timings were measured on the PointMaze environments using NVIDIA GeForce RTX 4090 GPUs.
27

---

Table 13: The comprehensive planning runtime comparison on PointMaze environments. Plan-
ning run time (sec.) and success rate (%) comparison across the methods except CompDiffuser.
Run Time (sec.) +
Success Rate (%)
Method
Medium
Large
Giant
Medium
Large
Giant
Diffuser-Replan
80.2
144.7
166.8
38
40
8.4
8.3
9.4
32
Diffusion Forcing
18.8
26.1
30.1
53
20
Diffusion Forcing-DatasetStiice
10.9
11.5
10.9
SSD
32.8
33.8
42.7
40
40
MCTD-Replan
166.5
503.7
630.1
90
20
MCTD-DatasetSütchh
50.2
77.2
53.8
12
Online Composer
83.6
91.2
269.8
93
82
Distributed Composer
26.7
39.1
530.7
100
100
26
Preplan Composer
11.1
21.5
36.9
100
100
100
(a) MCTD-Replan
(b) Online Composer
(c) Distributed Composer (d) Preplan Composer
Figure 4: Qualitative comparison of stitched planning approaches. (a) MCTD-Replan: Sequen-
tial replanning (trajectories shown from light to dark red) enables plan concatenation but results in myopic, short-sighted paths. (b) Online Composer: Plan-level search explores beyond the training data horizon. Gray lines denote discarded candidate plans during the search. (c) Distributed Com- poser: Search efficiency is improved by initiating searches from multiple starting positions (blue dots). Gray lines are unselected plans originating from the starting positions.
(d) Preplan Composer: pre-built graph is leveraged generate higher-quality plans with more optimized efficiency. Gray lines represent pre-computed but unused plans.
We measured the graph construction times for the medium, large, and giant PointMaze maps, which contain 10, 30, and 70 waypoint nodes, respectively. The corresponding construction times were 46.16 16, 83.18, and 72.69 seconds. Notably, building the graph for the giant environment is faster than for the large one. This counter-intuitive result occurs because the higher density of nodes (70 vs. 30) allows for shorter maximum search length between any pair of nodes, reducing the per-edge planning complexity.
This one one-time cost represents highly practical initial investment. To put this into perspective, the entire graph construction for the Large environment (83.18s) takes less time than a single planning query with our Online Composer (91.2s, see Table 2 Once this graph is built, it is reused for all subsequent planning tasks, including those with unseen start-goal pairs. Therefore, the initial computational cost is effectively amortized across numerous runs, leading to the significant inference- time efficiency gains Preplan Composer. This strategic trade-off-a modest offline computation for substantial and repeated online speedup-is key advantage of the proposed method.
B.6 Comprehensive planning runtime comparison
This section provides comprehensive comparison of the planning runtime for proposed meth- ods against all baselines, with detailed results presented in Table 13 We note that runtime for CompDiffuser not reported in the original paper and is therefore excluded from this analysis.
The results underscore that our C-MCTD framework achieves state-of oftthe-rrt trade-off between task success and computational efficiency. In the Medium environment, all C-MCTD variants achieve success rates exceeding 90%. In comparison to the strongest baseline, MCTD-Replan (90% success), methods are 2-15x faster. This advantage becomes pronounced in the Large environment,
28

---

where our Distributed and Preplan Composers achieve a 100% success rate, a stark contrast to the sub-50% rates of all baselines. Notably, this superior performance is achieved with planning times that are comparable to or faster than most baselines, with the exception of the DatasetStitch variants. In the most challenging Giant environment, the Preplan Composer the only method achieve 100% success rate (versus 0% for all other baselines), while also recording highly competitive runtime among non-DatasetStitch approaches.
C Algorithms
Algorithm 4 Online Composer
Require: Sstart' start state, Sgoat: goal state, D: diffusion planner, H: plan horizon, L: full-plan horizon, B: expansion budget, G: set of guidance sets
Ensure: A full trajectory Thall from Sttrtt to 8goal or failure
1: procedure ONLINE COMPOSER (Sstuts Syaals D, H, T., B,
2: Uroot f- Node(Ssart null)
D Create root node with start state D Initialize tree with root node
3: T T (V {Uraa) E = 0)
4: expandedNodes + 0
5:
while expandedNodes B and node close to Sgaal do
6:
> Based on UCT value
7:
G. t SelectGuudanceeet(
> Select guidance set
8:
+ D(v.plan, Sgeal: H, G+)
Generate guided plan
9:
Tchild + Concatenate(v,, (v.pla,, 7)
10:
reward + FestReplaninggimulltoooo/ Tehild Sguals D, H, L)
Vebili < Node Tehila, reward)
12:
T.V - T.V U (chilaa)
b Add child node to tree Add edge tree
T.E + T.E (vv, Vchila))
14:
Backpropagate((* reward)
Update ancestors' values
15:
expandedNodes +- expandedNodes
16:
end while
17: if node Egoal exists with dist(v Ugoal Ugoat-plan, $geal) I E then
18:
return Ugoal -paan
19: else
20:
return failure
21: end
22: end procedure
23: procedure FATTREPAANIIGGSSIILATTOOO Teurrent Spoal D, H, L)
24:
Tremaining 60 0
Initialize empty trajectory
25:
Scurrent f-
Teurren[-11
26:
while length Tremaining) do
27:
Thast +- D.FastDenoise
(SsooiisssSSersttt (Scurrent: Sgoal H
>> Fast denoising Append trajectory
28:
Tremaining Concatenate
(Tremaainttereaeinnnggg Tremmining: Tiast)
29:
Scurrent + Tiast [H]
> Update current state
if no progress iteration limit reached then
31:
break end if end while
33:
34:
return EvaluateReeward(Teeei.
Return estimated reward
35:
end procedure
29

---

Algorithm 5 Distributed Composer (DC)
Require: Sstar: start state, Sgoal: goal state, D: diffusion planner, H: plan horizon, L: full-plan horizon, B: expansion budget, N: number of origin positions
Ensure: A full trajectory
from Sstart to goal or failure procedure DISTRIBUTED COMPOSER(SS (Sttatt Sgoal, D, D,H.L,B.N)
2: S - Sstant U SamplePositions(N -)
> N origin positions
3: G (S. ()
Initialize connectivity graph
4: expandedTrrees t- 0
5:
while expandedTrees B do
6:
8i SelectOriginPosiiioon G)
Tree expansion can be implemented in parallel P Define guided distribution
7:
Po [x [2) x (x) exp( [x(()) T. + GrowTree 8c, Po, H,H,I, for each 8, ES {8t}
8:
Grow tree using Online Composer
9:
10:
for each node
Tj do minpev. plan dist(p, 8y) then
11:
12:
G.E + G.E G.E
{(s), 8/, v.plan))
Add connection to graph
13:
break
14:
end if end for end for
15:
17:
expandedTrees + expandedTrrees + if path exists from Ssart Sgoal in G then
18:
19:
path + ShortestPath(G: Sstart: Sgoal)
D. Dijkstra's or A
Tull StitchPath( path))
Stitch plans along path
21:
if length(TTuu) S L then
return Tial
23:
end if
end
25:
end while
26: return failure
27:
end procedure
28: procedure GROWTREF(SS, Po, H, L.)
29:
Vrot &- Node(s;, 0)
Create root node Initialize tree
30:
T f- (V (Uroot), 0)
31:
for to K do
K: tree expansion iterations
32:
x SellecNodeeToExaad(())
33:
< D(c.plan, po. H)
Sample from guided distribution
34:
Tenld + Concatenate(u.pple (.plan, 7)
35:
reward +- FuseRplaaminngSmmllatontttto 8gaal, D, H. L)
36:
Uabild + Node (Thhid reward)
37:
T.V T. (Chila)
38:
T.E. - T (1, Vchila)
end for
40: return T
end procedure
30

---

Algorithm 6 Preplan Composer (PC) Building Plan Graph
Require: E: environment, D: diffusion planner, H: plan horizon, N: number of waypoints
Ensure: Plan graph G encoding environment connectivity
1: procedure BUILDPLANGRAPHI D, N)
Pre-building phase
2: S Selec/Waypomms(E..N)
Identify N strategic waypoints
3: G < (8,
> Initialize plan graph
4:
for each pair (8s: 8,)
where i + j do Po [x(x))) x (x)ss; exp(-dist(x, 8,))
5:
Position- based guidance
6:
Túj < OC(si, 8j: D, Ho)))
Generate plan
7:
if Túj * 0 then
If connection successful
8:
G.E + G. ((8), 84)
Add plan graph
9:
end if end for
10:
11: return G
Return completed plan graph
12: end procedure
Algorithm 7 Preplan Composer Inference
Require: Sstati start state, Sgeal goal state, G: prebuilt plan graph, D: diffusion planner, H: plan horizon, L': local path horizon, L: full-plan horizon Ensure: A full trajectory Thall from 8start Syoal or failure 1: procedure PC-INFERENCF(SL.. Sgoal G, D, H, I., L.)
2: for each 8; E G do
4: Ta-si + OCCSS 8;, D,H.
3:
Ts-si + then
5: end
G.E + G.E U (Satart, 8,, Ts Ts
Add to plan graph
6:
7:
end for
8:
for each
8; E G do Ti-g OC(st, Sgoal D, H,H') Ti-g + 1 then
9:
10:
11:
G.E G.E U ((si, Sgual, Ti-tg)
Add to plan graph
12:
end
end for path <- ShortestPath(G, Sstart, $goal)
14:
if path , then
16:
Thall <- Stticchaat((path)
> Compose final solution
if leegthh (ru)) < L then
18:
return Tiall
end if
20:
end if
return failure
22:
end procedure
31


Reviews:
[{"review_id": "oXd9xreSr7", "reviewer": "Reviewer_ECBR", "summary": "Building upon MCTD, the authors propose the C-MCTD framework, which incorporates three complementary strategies—Online, Distributed, and Preplan Composer—to perform compositional search over multiple short-horizon plans during the inference stage. This enables the generation of long-horizon trajectories exceeding 10× the training horizon. Experiments across OGBench’s Point-/Ant-Maze, vision-based mazes, and robotic block manipulation tasks demonstrate significant performance improvements over baselines such as MCTD-Replan and CompDiffuser.", "questions": "- the paper only reports inference-time runtime (Table 2), how long does the offline graph construction take?\n- the author states that the Online Composer relies on mechanisms such as guidance sets and fast replanning, but their specific contributions to performance are not demonstrated.", "limitations": "yes (section 5.4)", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength:\nThe paper extends the MCTD to composable inference-time reasoning, allowing long-horizon plan generation without retraining. \n\nWeakness:\nThe paper lacks ablation studies on key design components of the Composers—for instance, the Fast Replanning and Plan-Cache modules in the Online Composer.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and effort in reviewing our manuscript.\n\n> [W1] The paper lacks ablation studies on key design components of the Composers—for instance, the Fast Replanning and Plan-Cache modules in the Online Composer.\n\nWe thank the reviewer for their constructive feedback. We appreciate the opportunity to clarify our analysis of the key components of the Online Composer and provide further validation.\n\n**1. Ablation Study on the Plan-Cache Module**\n\nWe would like to clarify that an ablation study for the Plan-Cache module is provided in **Appendix B.1**. These experiments were conducted on the Robot Arm Cube Manipulation tasks. As detailed in Table 5, our findings show that while the benefit of the Plan-Cache is modest for relatively simple tasks (e.g., single or double object manipulation), its utility increases exponentially with task complexity. Notably, in the most complex quadruple cubes manipulation task, the Plan-Cache **achieves a ~6x reduction in runtime** (from 1432.8s to 242.8s), demonstrating its critical role in scaling our method to challenging, long-horizon problems.\n\n**2. Ablation Study on the Fast Replanning Module**\n\nFollowing the reviewer's valuable suggestion, we have conducted a new ablation study on the Fast Replanning (FR) module. We evaluated the performance of the Online Composer with and without Fast Replanning across various search budgets in our maze environments. The numbers in parentheses indicate the maximum search iterations allowed. We did not report results on PointMaze Giant as the performance difference was negligible.\n\n| Environment | W/ FR (200) | W/o FR (200) | W/ FR (100) | W/o FR (100) | W/ FR (50) | W/o FR (50) |\n| --- | --- | --- | --- | --- | --- | --- |\n| PointMaze Medium | **96±8%** | 82±6% | **94±9%** | 76±12% | **92±10%** | 63±15% |\n| PointMaze Large | **84±15%** | 54±13% | **82±14%** | 49±10% | **82±19%** | 32±11% |\n\nThe results unequivocally demonstrate the importance of Fast Replanning.\n\n- **Consistent Improvement:** Across all settings, enabling Fast Replanning leads to a significant performance improvement.\n- **Efficiency under Constraint:** The performance gap widens dramatically as the search budget shrinks. For instance, in PointMaze Large with a budget of 50, our method with Fast Replanning maintains a high success rate of 82%, whereas the performance of the version without it collapses to 32%.\n\nThis analysis highlights that Fast Replanning is not just a minor optimization but a crucial component that makes our tree search algorithm robust and sample-efficient, by enabling effective value propagation throughout the search tree.\n\nWe will add this new ablation study to the appendix in the revised version. We thank the reviewer again for their insightful comments, which have helped us further strengthen our paper.\n\n> [Q1] the paper only reports inference-time runtime (Table 2), how long does the offline graph construction take?\n\nWe thank the reviewer for this insightful question regarding the offline graph construction time. We omitted this from the main paper as it is a one-time, pre-inference step, but we agree that providing this information adds valuable context. We will include these details in the final version of the paper.\n\nWe measured the runtime for building the plan graph for each PointMaze environment on a system with 8 NVIDIA GeForce RTX 4090 GPUs. The results are as follows:\n\n- **PointMaze Medium (10 nodes):** 46.16 seconds\n- **PointMaze Large (30 nodes):** 83.18 seconds\n- **PointMaze Giant (70 nodes):** 72.69 seconds\n\nNotably, the construction for the 'Giant' environment is faster than for 'Large'. This is because the higher density of nodes (70 vs. 30) allows us to set a shorter maximum length for the plans connecting each pair of nodes, which in turn reduces the per-pair search complexity.\n\nThe key takeaway is that this offline cost represents **a highly practical one-time investment**. For context, in the 'Large' environment, **the entire graph construction (83.18s) takes less time than a single planning instance with our Online Composer (91.2s, as reported in Table 2).**\n\nOnce this graph is constructed for a given environment, it is reused for all subsequent planning tasks, including any unseen start-goal pairs. **This one-time computational cost is therefore effectively amortized across numerous runs**, leading to the significant inference-time efficiency gains of our Preplan Composer. This strategic trade-off—a modest, one-time offline computation for a substantial and repeated online speedup while maintaining high performance—is a central achievement of our proposed method.\n\n> [Q2] the author states that the Online Composer relies on mechanisms such as guidance sets and fast replanning, but their specific contributions to performance are not demonstrated.\n\nWe thank the reviewer for their insightful comment. To clarify the distinct contributions of our proposed mechanisms, **we have already included an ablation study on Fast Replanning in the above comment for [W1]**, and we now present a new ablation study on the guidance set.\n\nIn our framework, C-MCTD provides the planner with a guidance set—e.g., [0, 0.1, 0.5, 1, 2] for the PointMaze tasks—as a meta-action. This allows for effective integration with inference-time scaling planners. To experimentally isolate the contribution of this component, we compared our default approach (providing the full set) against providing the planner with a single, fixed guidance level.\n\nThe results are summarized in the table below:\n\n| Environment | Default (Guidance Set) | Fixed: 0.1 | Fixed: 0.5 | Fixed: 1 | Fixed: 2 |\n| --- | --- | --- | --- | --- | --- |\n| PointMaze Medium | **93±9%** | 80±0% | 90±10% | **98±6%** | 83±8% |\n| PointMaze Large | **82±17%** | **77±14%** | 52±13% | 27±10% | 20±0% |\n\nThe results reveal a clear trade-off. For the `PointMaze-Medium` environment, which requires moderately complex planning, higher fixed guidance levels (0.5 or 1.0) yield strong performance, comparable to using the full set. In contrast, for the more challenging `PointMaze-Large` environment, a low fixed guidance level (0.1) is required to achieve a competitive score.\n\nCrucially, our default method of providing a guidance set achieves robustly high performance across both environments. This demonstrates that **the guidance set is a vital mechanism that empowers the planner to adaptively select the most suitable guidance strength for a given task.** It is this adaptability that ensures effective and versatile integration with inference-time planners across varying levels of environmental complexity.\n\nWe will incorporate this analysis and the table into the revised manuscript to make the contribution of the guidance set explicit."}, {"review_id": "mfRk1ZT2f8", "reviewer": "Reviewer_NuJi", "summary": "This paper proposes Compositional Monte Carlo Tree Diffusion (C-MCTD), a  framework that extend MCTD's planning capabilities beyond training trajectory lengths through three variants, online Composer, Distributed Composer, and Preplan Composer. \n\nThe key idea is to stitch multiple short-horizon plans together using tree search at the plan level rather than the subplan level. Online Composer performs sequential plan stitching with hierarchical tree search, Distributed Composer uses parallel trees with strategic connections, and Preplan Composer leverages prebuilt plan graphs. The authors evaluate on maze navigation, robot manipulation, and visual planning tasks, showing improvements over replanning baselines.", "questions": "Why not compare against recent methods that specifically address training length limitations, such as hierarchical planning approaches or other compositional methods? The current baselines seem weak.", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "1. The paper addresses a real limitation of MCTD - its inability to generate plans longer than training trajectories. The hierarchical approach of searching over plans rather than subplans is reasonable.\n\n2.The core contribution lacks novelty. Plan stitching is well-established, but,,,  the paper essentially applies existing tree search techniques at a higher level.\n3.The experimental evaluation has several issues. The baselines are mostly weak replanning methods rather than SoTA long-horizon planners. The comparison lacks recent methods that directly address training length limitations. Results are inconsistent across environments - Distributed Composer sometimes outperforms Online Composer, sometimes doesn't, with no clear explanation.", "was_revised": true, "final_justification": "Reviewer has addressed some of my concerns", "rebuttal": "We would like to thank the reviewer for their valuable feedback.\n\n> [W1] The core contribution lacks novelty. Plan stitching is well-established, but,,, the paper essentially applies existing tree search techniques at a higher level.\n\nWe sincerely thank the reviewer for their time and valuable feedback. We appreciate the opportunity to clarify the core contributions of our work, C-MCTD. We respectfully posit that our framework offers significant novelties beyond the high-level application of existing tree search techniques. Below, we detail the distinct innovations within each of our proposed composers.\n\n**1. The Online Composer: A Generalization of MCTD**\n\nWhile building on tree search principles, the Online Composer introduces a novel formulation. It employs a guidance set to define **meta-actions**, which allows each node within the search tree to function as an independent, recursively-scaled planner.\n\nThis design makes our Online Composer a **generalization of MCTD**. Specifically, MCTD can be viewed as a special case of our method where planning is constrained only to the root node. By enabling every node to be a planner, C-MCTD can tackle more complex, hierarchical problems.\n\nFurthermore, we introduced a practical innovation, the **Plan Cache**, for the Robot Arm Cube Manipulation task. As shown in the Appendix (Table 5), this mechanism enables highly efficient combinatorial search by reusing successful local-plans. This is a capability that standard high-level plan stitching does not support.\n\n**2. The Distributed Composer: Efficient Parallel Search**\n\nDistinct from conventional tree search, the Distributed Composer initiates **parallel searches from multiple, diverse root nodes** simultaneously by merging these parallel search trees, which is guided by a latent distance heuristic.\n\nThis approach effectively partitions the overall search space. By preventing the exponential growth of a single, excessively deep tree, it facilitates a far more efficient exploration for long-horizon tasks. This parallel, heuristic-guided merging is a new technique designed specifically to address the scaling limitations of diffusion planners.\n\n**3. The Preplan Composer: Amortized Inference via Reusable Plan Graphs**\n\nThe Preplan Composer introduces a novel mechanism for optimizing inference-time efficiency by pre-computing a **compositional plan graph**.\n\nCrucially, this graph is designed to be **reusable across various tasks** within the same environment. This feature allows the significant computational overhead of planning to be **effectively amortized**, a substantial advantage for practical applications. To the best of our knowledge, this form of compositional graph reuse during the inference phase is a previously unexplored concept in the diffusion-based planning literature.\n\n**Concluding Remarks**\n\nThese contributions, individually and collectively, represent a substantial advancement beyond applying existing techniques. We have developed a comprehensive framework that significantly enhances the applicability of diffusion planners to generalized inference-time scaling problems—particularly for tasks where the required plan length exceeds that seen during training. We are confident in the significance of this contribution and its potential to influence future work in long-horizon planning.\n\n> [W2]  The baselines are mostly weak replanning methods rather than SoTA long-horizon planners.\n\nWe sincerely thank the reviewer for their constructive feedback on our experimental evaluation. We would like to take this opportunity to clarify a potential misunderstanding regarding the baselines used for comparison in our work.\n\nFirst, to address the concern about \"weak replanning methods,\" **we went beyond simple replanning.** For established diffusion planners like Diffuser, Diffusion Forcing, and MCTD, we significantly strengthened them by integrating recent data-stitching techniques [1, 2]. These techniques are specifically designed to overcome the very training length limitations the reviewer highlighted. This ensures that our primary baselines are not naive implementations but are instead robust competitors that incorporate modern advancements.\n\nSecond, regarding the lack of \"SoTA long-horizon planners,\" our evaluation in **Table 1** explicitly includes comparisons against t**he most recent and relevant state-of-the-art methods.** We benchmarked C-MCTD against:\n\n- **Stitching Subtrajectory Diffuser (SSD):** A leading method that leverages a learned value function to address trajectory length limitations.\n- **Compositional Diffuser (CompDiffuser):** A SoTA planner that utilizes a specialized training paradigm for compositional planning.\nOur results, as detailed in Table 1, demonstrate that C-MCTD substantially outperforms *all* these methods—including the strengthened baselines and the current SoTA planners. For example, across all sizes (medium, large, giant) of the PointMaze and AntMaze environments, C-MCTD elevates performance dramatically, often turning success rates of 0-50% into 100%.\n\nThis superior performance underscores the core contribution of our work: **C-MCTD achieves state-of-the-art results through a novel inference-time scaling stitching mechanism based on tree search, without requiring complex, specialized training schemes or auxiliary components like value functions.**\n\n> [W3] Results are inconsistent across environments - Distributed Composer sometimes outperforms Online Composer, sometimes doesn't, with no clear explanation.\n\nWe thank the reviewer for their insightful comment. We would like to clarify the performance of our proposed methods.\n\nOur results demonstrate that the Distributed Composer **consistently outperforms** the Online Composer in the `pointmaze`and `antmaze` environments. This consistent improvement highlights its effectiveness in complex, sparse-reward settings.\n\nWe acknowledge that the Distributed Composer showed a different performance trend in the Visual PointMaze environment. **As we briefly discussed in the manuscript (Page 9, Lines 340-342)**, we attribute this to the challenges of latent state misalignment that arise when stitching trajectories generated from diverse tree origins.\n\n> [Q1] Why not compare against recent methods that specifically address training length limitations, such as hierarchical planning approaches or other compositional methods?\n\nWe thank the reviewer for their valuable feedback and the opportunity to clarify our comparisons with recent methods designed for long-horizon tasks with limited training data.\n\n**1. Comparison with Compositional Methods**\n\nWe would like to gently point the reviewer to **Table 1** of our submission, where we conduct a detailed empirical comparison against two highly relevant compositional methods: SSD, a value-learning-based approach, and CompDiffuser, a state-of-the-art compositional planning method.\n\n- **Against SSD:** Our C-MCTD methods (Online, Distributed, and Preplan Composers) consistently and significantly outperform SSD across all tested environments (PointMaze and AntMaze).\n- **Against CompDiffuser:** All C-MCTD variants demonstrate comparable or superior performance in medium and large environments. Notably, in the most challenging 'giant' environments, our Preplan Composer surpasses CompDiffuser by a significant margin.\n\nWe wish to emphasize a critical distinction that highlights the novelty of our work: CompDiffuser's performance relies on a diffusion planner trained with a highly specialized learning scheme. In contrast, a key contribution of C-MCTD is achieving these superior or comparable results using a **standard, pre-trained diffusion planner**. Our performance gains stem from our novel inference-time scaling and tree-search-based stitching framework, making C-MCTD a more general, modular, and practical approach.\n\n**2. Addressing Hierarchical Planning Methods**\n\nRegarding the comparison with hierarchical planning methods like the Hierarchical Multi-scale Diffuser (HMD) [2], a direct comparison was unfortunately not feasible as its source code has not been publicly released.\n\nHowever, to provide a principled and fair analysis, we isolated the core mechanism HMD employs to handle training length limitations: **dataset stitching**. We implemented this technique ourselves and applied it to strong diffusion planners (Diffuser, Diffusion Forcing, and MCTD) to create robust baselines. As shown in Table 1, our C-MCTD framework decisively outperforms these dataset-stitching-enhanced baselines. The performance gap is substantial, with C-MCTD achieving **over 50% higher success rates** in the challenging 'large' and 'giant' environments.\n\nThis result demonstrates that the simple stitching of datasets is insufficient and that our proposed inference-time composition via tree search is a significantly more effective strategy for long-horizon planning. We hope this clarification underscores the strength and significance of our contributions.\n\n[1] Guanghe Li, Yixiang Shan, Zhengbang Zhu, Ting Long, and Weinan Zhang. Diffstitch: Boosting offline reinforcement learning with diffusion-based trajectory stitching. arXiv preprint arXiv:2402.02439, 2024.\n\n[2] Chen, Chang, et al. \"Extendable long-horizon planning via hierarchical multiscale diffusion.\" arXiv preprint arXiv:2503.20102 (2025)."}, {"review_id": "aerFLgLqx0", "reviewer": "Reviewer_Q2ax", "summary": "This work presents an extension of the Monte Carlo Tree Diffusion (MCTD) approach for long-horizon planning, termed C-MCTD. The proposed method enables the construction of long-horizon plans by effectively \"stitching\" together relatively short plans generated by MCTD. The authors introduce three strategies to achieve this—online, distributed, and preplan—and apply them to long-horizon maze navigation and multi-cube robot arm manipulation tasks.", "questions": "- How is the guidance set defined and implemented in the proposed method? Despite frequent references to \"guidance\" in the main text and appendix, its precise formulation and implementation remain unclear.\n- What is the size of the subgoal set, and how are subgoals sampled during planning? Is randomly scattering subgoals a valid strategy for complex long-horizon tasks, or could this limit planning efficiency and interpretability?\n- Could the authors provide further details on the hyperparameters used in the experiments? For instance, how was the epsilon threshold for stitching trajectories determined, and was the method robust to smaller epsilon values during execution?\n- (minor) spacing in Table 3 : Online Composer", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths\n- Divide-and-conquer approach for long-horizon tasks: This work builds upon the idea of MCTD by proposing a method that enables planning over longer horizons than the trajectory lengths supported by MCTD. By introducing and comparing three different composition strategies in C-MCTD, the authors allow for flexible selection of an appropriate strategy depending on the task requirements.\n- Clear explanation of some key algorithmic components: The differences among the proposed composition strategies are well explained, particularly in terms of the components that distinguish each approach. The inclusion of algorithmic details in the appendix and the release of open-source code contribute to the reproducibility of the proposed method.\n\n### Weaknesses\n- Shallow analysis of candidate tree origin position proposal : While the proposed method extends MCTD by composing multiple sub-trajectories via tree search—similar to hierarchical RL—it lacks in-depth discussion on the generation and maintenance of subgoals, which are crucial in hierarchical planning. The method treats tree origin positions as subgoals but does not provide substantial analysis on how these subgoals should be selected or maintained. In particular, for the distributed and preplan composers, subgoals are either randomly sampled or derived from previous trajectories, without further discussion on their semantic significance or strategic role.\n- Lack of clarity regarding the use and definition of the guidance set: Despite the frequent use of the term \"guidance\" throughout the manuscript and appendix, there is a lack of concrete mathematical formulation or detailed explanation regarding how the guidance set is actually utilized. A more explicit clarification—either in the main text or at least in the appendix—is necessary.\n- Insufficient discussion of the preplan composer: The authors claim that the preplan composer achieves 100% accuracy, which is not necessarily an incorrect observation. However, the emphasis on this result raises questions about the true contribution of the preplan composer. Without deeper analysis on what kinds of preplans are effective for long-horizon or multi-stage tasks—and how these preplans contribute to improved efficiency or accuracy—the method risks being perceived as a simple concatenation of ground-truth trajectory fragments.\n- Limited empirical validation of the proposed method: The model is only evaluated on two tasks (maze navigation and cube arrangement). While the results on these tasks demonstrate some level of robustness, the general applicability of the method remains uncertain. Additional experiments across diverse environments would be necessary to demonstrate that the proposed method is not overly specialized to these specific scenarios.\n- Lack of visualization for experimental results: The only visual comparison presented is the conceptual illustration in Figure 1. To better understand the behavior and differences between the proposed composition strategies, it would be helpful to include visualizations of the actual trajectories generated in the experiments.", "was_revised": true, "final_justification": "Having considered both the initial submission and the authors’ rebuttal, I believe that the work has reached the standard expected for a NeurIPS conference paper. Accordingly, I have adjusted my evaluation from a borderline reject to a borderline accept.\n\nMy primary concerns were related to the lack of detailed explanations of the experiments and the justification of the reported results. The authors have addressed many of these concerns in their response. However, I expect the final version of the manuscript to include the detailed clarifications and result visualizations as outlined in the rebuttal.", "rebuttal": "We thank the reviewer for their constructive comments.\n\n> [W1] Shallow analysis of candidate tree origin position proposal\n\nWe thank the reviewer for their insightful feedback and for highlighting the need for a clearer exposition of our subgoal selection strategy. We respectfully wish to clarify that the selection of tree origin positions (subgoals) for our Distributed and Preplan Composers is a principled, data-driven process, not a random one.\n\n**As detailed in the Appendix (Lines 885-890)**, we identify these subgoals by performing k-means clustering on the trajectories from the training dataset. The centroids of these clusters represent strategically significant and diverse states—regions that are frequently traversed or serve as critical waypoints in the environment's state space. This data-driven approach ensures that our subgoals possess **semantic significance**, directly reflecting the structure of the underlying environment. **They are not arbitrarily chosen but are representative of key decision points.**\n\nWe acknowledge that this crucial detail was not sufficiently emphasized in the main body of the paper. To address this, we will revise the manuscript.\n\n> [W2] Lack of clarity regarding the use and definition of the guidance set\n\nWe thank the reviewer for their insightful comment and for highlighting the need for a more explicit definition of the \"guidance set.\" We acknowledge that the role of this component could be further clarified to better underscore its importance within our framework.\n\nThe term \"guidance\" in our work refers to the steering mechanism inherent in our classifier-guided approach, which is directed by the value function $\\mathcal{J}_\\phi(\\mathbf{x})$ as formulated in Equation (2).\n\nThe **guidance set** is a collection of hyperparameter weights that modulate the strength and nature of this guidance. Crucially, our inference-time scaling planner takes this set as an argument during the node expansion phase of C-MCTD. **This mechanism empowers the planner to generate effective and diverse local plans by dynamically adjusting the influence of the value function at each step of the tree search.** We studied the ablations for the guidance set in the rebuttal for the reviewer ECBR's review, `Ablation Study on the Efficacy of the Guidance Sets`.\n\nTo address the reviewer's valid point, we will incorporate these clarifications into the revised manuscript.\n\n> [W3] Insufficient discussion of the preplan composer\n\nWe thank the reviewer for their insightful comment, which highlights the need for a more detailed discussion of the Preplan Composer. We would like to clarify its mechanism and contribution, addressing the concern that it might be a \"simple concatenation of ground-truth trajectory fragments.\"\n\nThe Preplan Composer is a method designed to amortize the computational cost of planning, enabling highly efficient inference for long-horizon tasks. Its contribution is not merely achieving high accuracy but in structuring the planning problem to drastically reduce online computational overhead. The process unfolds in three distinct stages:\n\n1. **Offline Plan Graph Construction:** First, we construct a \"plan graph\" entirely offline. This involves generating plans between a set of diverse \"tree origin positions\" sampled from the training data distribution. This computationally intensive step is performed only once and the resulting graph can be reused across various tasks within the same environment.\n2. **Inference-Time Graph Connection:** At inference time, given a novel start-goal pair, our system generates only short \"bridging\" plans to connect the start and goal to their nearest nodes in the pre-computed plan graph. Since the graph is dense, these bridging plans are typically very short, requiring minimal online search.\n3. **Final Path Assembly:** Finally, we perform a rapid search (e.g., Dijkstra's algorithm) on the graph to find the shortest path of nodes connecting the start and goal. The final plan is an assembly of the pre-generated plans corresponding to the edges in this path.\n\nCrucially, each segment in this final path is a plan **generated by our learned diffusion planner**, not a ground-truth trajectory fragment. The Preplan Composer's novelty lies in its strategic pre-computation, which amortizes the planning effort. This allows our method to efficiently solve complex, long-horizon problems at inference time, a significant step beyond methods that perform the entire search online.\n\n> [W4] Limited empirical validation of the proposed method\n\n**Our primary objective was to directly address a critical and known limitation of prior work (MCTD)**: its performance degradation in settings constrained by short training trajectories. To create the most rigorous and fair comparison, **we intentionally selected the very environments where MCTD had previously demonstrated its effectiveness.**\n\nWhile we concur that evaluation on a broader set of tasks is a valuable direction for future work, our focused experiments provide the necessary and compelling evidence that our proposed method resolves a significant bottleneck in state-of-the-art inference-time scaling planning algorithms.\n\n> [W5] Lack of visualization for experimental results\n\nWe thank the reviewer for this valuable feedback. We concur that visualizing the experimental results will significantly improve the paper. We will update them in our revised version.\n\n> [Q1] How is the guidance set defined and implemented in the proposed method?\n\nWe thank the reviewer for the opportunity to clarify our method.\nThe term \"guidance\" denotes the steering of the generation via a value function (Eq. 2). The \"guidance set\" is the concrete implementation of this principle: a collection of predefined weights that control the strength of this steering.\nWe will ensure this definition is stated more explicitly in the final version of the paper.\n\n> [Q2] Clarification of Subgoal Set\n\nWe thank the reviewer for this insightful question, which allows us to clarify the role and selection of our tree origin positions. We infer that the \"subgoals\" mentioned in the comment refer to what our paper calls \"tree origin positions,\" which serve as starting points for Distributed and Preplan Composers in our C-MCTD framework.\n\nThe size of the origin position set is tailored to the complexity of the environment. For example, we use 10, 30, and 70 positions for the `medium`, `large`, and `giant` maps, respectively. Crucially, these positions are not randomly scattered. **We employ a principled selection strategy to ensure broad and meaningful coverage of the state space.** Specifically, we use k-means clustering on a large set of collected states to identify diverse and representative locations. This deliberate placement is vital for the agent's ability to solve a wide variety of unseen start-goal tasks. **They are not randomly sampled, therefore this does not limit the planning efficiency and interpretability.**\n\n> [Q3] how was the epsilon threshold for stitching trajectories determined, and was the method robust to smaller epsilon values during execution?\n\nWe sincerely thank the reviewer for their insightful comment regarding the sensitivity of our hyperparameters. In our experiments, the epsilon threshold for trajectory stitching in the PointMaze environment was initially set to $\\epsilon=1.0$. We adopted it directly from the goal-achievement threshold used in the reward function of the original MCTD framework, upon which our work builds.\n\nTo explicitly address the reviewer's question about robustness, especially concerning smaller epsilon values, we performed a thorough ablation study using our Distributed Composer. The results, showing the success rate (mean ± std) across different epsilon values, are summarized below:\n\n| Environment | 5.0 | 2.0 | 1.0 | 0.5 | 0.1 |\n| --- | --- | --- | --- | --- | --- |\n| PointMaze Medium | 100±0% | 100±0% | 100±0% | 100±0% | 94±9% |\n| PointMaze Large | 65±16% | 100±0% | 100±0% | 100±0% | 73±13% |\n| PointMaze Giant | 40±24% | 26±13% | 26±21% | 10±10% | 0±0% |\n\nOur analysis of this data reveals a clear relationship between task complexity and the optimal epsilon value:\n\n- **Robustness in Simpler Environments:** For the `PointMaze Medium` environment, which requires relatively straightforward planning, our method demonstrates high robustness. Performance remains optimal across a wide range of epsilon values (from 0.5 to 5.0), only degrading slightly at a very restrictive ϵ=0.1.\n- **A \"Sweet Spot\" in Complex Environments:** In the more challenging `PointMaze Large` environment, the results highlight a clear trade-off. An excessively large epsilon (e.g., 5.0) degrades performance by causing spurious stitching—for instance, incorrectly connecting trajectories across physical barriers. Conversely, an overly restrictive epsilon (e.g., 0.1) prevents valid stitching opportunities, thus hampering the agent's ability to form long, successful plans. This demonstrates that an appropriately tuned epsilon is beneficial for complex tasks.\n- **The Benefit of Lenient Stitching in Gaint Environments:** Intriguingly, for the `PointMaze Giant` environment, a larger epsilon threshold ($\\epsilon=5.0$) yields a noticeable performance improvement. The immense scale of this environment makes it difficult for the planner to connect distant states. A more lenient stitching condition (larger $\\epsilon$) facilitates the creation of long-range plans by increasing the frequency of stitching, even if some connections are imprecise. This proves more effective than sparse, high-precision stitching in such scenarios.\n\nWe are grateful to the reviewer for raising this important point. This detailed hyperparameter analysis and the accompanying discussion will be incorporated into the revised manuscript.\n\n> [Q4] (minor) spacing in Table 3\n\nWe sincerely thank the reviewer for catching the spacing issue in Table 3. We will fix it in our revision."}, {"review_id": "X6UfveS8eC", "reviewer": "Reviewer_rpAX", "summary": "This paper try to address the limited planning horizon issue of MCTD framework by adding hierarchical planning strategy that stitch the plans in various different ways. It achieved substantially better performance or efficiency in out-of-domain long-horizon maze navigation tasks compared with Diffuser and MCTD.", "questions": "* One of the most important question is what is the formulation of the problem that C-MCTD works the best among the Diffuser, MCTD, traditional A* or MCTS algorithms such as UCT, PUCT, GumbelMuzero, etc. Where could we apply this algorithm in practice? What is the supporting evidence? \n* If applicable, I am curious about the performance of A* search with manhattan distance heuristics in pointmaze problem, including the runtime and successrate. \n* Looks like the MCTD and C-MCTD assume there is no need to use transition function to simulate the actual state changes for action execution? Are the environments in the experiment deterministic in transition? Will there be any impact if the environment has a highly random transition function? \n* In POMDP tasks, are you conducting the search offline as well and replan online? Is the low-performance is caused by no transition function's simulation, so that the gap between actual execution and plan is big?", "limitations": "I think in Discussion section, the author compare the limitations of different variants of C-MCTD, but did not actually discuss the limitation of C-MCTD compared with MCTD, Diffuser, and traditonal search algorithms. This should be included with supporting evidence to better define the scope of the application of C-MCTD.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n1. The overall performance is substantially strong in long-horizon maze navigation tasks compared with MCTD and Diffuser. \n2. The overall framework seems to be general. The paper applied the idea in both the maze navigation and robot arm cube manipulation. \n\n**Weaknesses**\n\n1. The algorithm could become quite complex due to the inherent computational cost of MCTS. In the worst case, UCT has an exponential complexity of the form $\\Omega(\\exp(\\exp(\\exp(...\\exp(1)))))$ (depth -1 times of $\\exp$) [1], and the actual worst-case performance could be even more prohibitive in practice when composing multiple UCT instances and diffusion process.\n2. If understand correctly, the algorithm seems to tackle the offline planning problems. However, MCTS is a online planning algorithm because of its anytime property and effectivenness in online MDP/POMDP (POMCP or DESPOT for POMDP). Given the essential slow runtime of diffusion, the proposed method could be very limited in real-time or low-latency planning scenarios.\n3. The paper might need a more comprehensive discussion of practical application scenarios where the proposed C-MCTD method offers a distinct advantage. For example, determinisitic pointmaze navigation could be tackled effectively by A* search. As for POMDP, there are also mature algorithms such as POMCP and DESPOT. It would strengthen the paper to include a discussion on when and why C-MCTD should be preferred over these traditional approaches, and under what conditions it significantly outperforms them.\n\n[1] Qoquelin & Munos, Bandit Algorithms for Tree Search, UAI 2007", "was_revised": true, "final_justification": "I personally believe it is a good paper if the author could address the issues mentioned in the rebuttal during the revisions:\n\n1. The inherent limitations of traditional algorithms (PRM, MCTS, etc), coupled with a clear problem formulation in the preliminaries section, to highlight the distinct advantage of C-MCTD. Also, reflect the formulation on the experimental setup.\n2. Online planning or\b planning in a stochastic environment.\n3. Assumptions made in different variants of C-MCTD. \n\nMy main reason for acceptance is that \n1. It indeed has good reported performance in long-horizon planning tasks, and also \n2. provides reasonable solutions to the extensive run-time issues; \n3. The assumption is also reasonable, as we generally expect the training dataset to be fairly similar to the testing cases.\n\nThus, with clear assumptions and a discussion of the limitations, I believe this research is a meaningful attempt to address long-horizon planning problems.", "rebuttal": "We thank the reviewer for their constructive comments.\n\n> [W1] On Computational Complexity and Our Proposed Solutions\n\nWe thank the reviewer for their insightful comment regarding the computational complexity of MCTS. The reviewer is correct that the worst-case exponential complexity of MCTS is a critical consideration and it has been figured out in the previous work, MCTD. Indeed, addressing this inherent challenge was one of primary motivations for our work.\n\nOur proposed method, C-MCTD, is designed specifically to mitigate this complexity through two key innovations: the **Distributed Composer** and the **Preplan Composer**.\n\n1. **Distributed Composer:** This approach prevents the search space from exploding in deep trees by parallelizing the search from multiple origin points, effectively managing the search depth.\n2. **Preplan Composer:** This method further enhances efficiency by pre-generating and caching the plans between the tree origin positions into a graph, significantly reducing the online search burden at inference time.\n\nThe effectiveness of these solutions is empirically validated in our experiments. As shown in **Table 2**, compared to the Online Composer, our Distributed Composer achieves substantial speedups of ~3× and ~2× on Medium and Large maps, respectively. Furthermore, the Preplan Composer demonstrates even more significant gains, with speedups of ~7× and ~4×.\n\n> [W2] On the Practicality for Online Planning and the Role of the Preplan Composer\n\nWe thank the reviewer for their insightful comment. We agree that the inherent computational cost of diffusion models presents a significant challenge for their application in online planning. Addressing this very challenge is one of central motivations for our work.\n\nThe Preplan Composer variant is designed precisely to overcome the runtime limitations mentioned by the reviewer. By pre-generating a graph of potential plans in an offline phase, it shifts the computational burden away from the time-critical online execution. During the online phase, the agent primarily performs efficient lookups and minimal stitching, rather than expensive generative planning.\n\nAs empirically demonstrated in Table 2, this approach is highly effective. **The Preplan Composer achieves a 4-7x speedup in planning time compared to Online Composer and 2x speedup compared to Distributed Composer that generate plans entirely online**, showcasing its viability for scenarios where low latency is crucial. Therefore, our work provides a practical pathway to harness the power of diffusion models for complex online planning tasks.\n\n> [W3 & Q2] Clarification on the Task Complexity and the Advantage of C-MCTD\n\nWe thank the reviewer for their insightful suggestion to elaborate on the practical application scenarios for our proposed C-MCTD. We respectfully clarify that the environments evaluated in our work present significant challenges that render traditional search algorithms, such as A* or POMDP solvers, impractical.\n\nFor instance, the PointMaze navigation task features continuous state and action spaces. An optimal agent navigating the giant map requires a trajectory of at least 500 steps. Applying conventional search algorithms to such a long-horizon task in a continuous space would involve exploring a prohibitively large, if not intractable, search space. Our method, C-MCTD, is precisely designed to tackle these complexities by leveraging diffusion models for tree search-based stitching of short trajectories, a task for which methods like A* are not suited.\n\nWe acknowledge that a more explicit discussion of these task characteristics will strengthen our paper. In the revised version, we will dedicate a section to discuss the limitations of traditional approaches in our problem settings.\n\n> [Q1] Clarification on the Optimal Use Cases and Practical Applications of C-MCTD\n\nThank you for the insightful question, which clarifies where C-MCTD is most effective.\n\nC-MCTD is specifically designed to excel in scenarios where diffusion models are constrained by limited training data length and thus cannot generate sufficiently long, high-quality plans. Our method's core strength lies in its ability to effectively stitch together short trajectories through a tree-search mechanism at inference time, enabling long-horizon planning that surpasses the limitations of the training data.\n\nThe supporting evidence for this is presented in our experimental results.\n\n- **As shown in Table 1,** when the required planning horizon is longer than the training trajectories, C-MCTD outperforms all baseline methods—including Diffuser, Diffusion Forcing, and their variants using replanning or stitched datasets—**by a substantial margin of 10-100%.**\n- **Furthermore, Table 3 highlights** that C-MCTD's advantage is even more pronounced (achieving 10-100% better performance) in tasks that necessitate compositional planning, **directly validating the efficacy of our tree-search-based stitching.**\n\nRegarding traditional search algorithms, they are often not well-suited for the complex tasks we address, which involve continuous state-action spaces and demand very long-horizon planning.\n\n> [Q3] On the Role of the Transition Function and Environmental Stochasticity\n\nWe thank the reviewer for their insightful question regarding our model's assumptions and its applicability to stochastic environments.\n\n**1. Clarification on the Transition Function:** The reviewer is correct in observing that our methods, MCTD and C-MCTD, do not require an explicit transition function $T(s,a,s′)$. Our framework leverages a diffusion model trained on an offline dataset of short trajectories. By doing so, our model directly learns the underlying distribution of valid state sequences, implicitly capturing the dynamics demonstrated in the dataset. **This sequence-level modeling is a core design choice that allows our method to generate coherent long-horizon plans without the need for step-wise state transition modeling.**\n\n**2. On Environmental Stochasticity:** We confirm that the environments used in our current experiments are deterministic. This was a deliberate choice to first establish a strong foundation for diffusion-based planning and demonstrate the effectiveness of our core contribution: inference-time tree search and stitching.\n\nThe reviewer raises an excellent point about performance in highly stochastic environments. A direct application of our current model would likely result in learning an \"averaged\" plan from the varied outcomes in the dataset, which may degrade planning quality.\n\nExtending our framework to such settings is a promising direction for future work. We will explicitly clarify the deterministic scope of our experiments and **add this important discussion on stochasticity as a future work direction in the revised manuscript.**\n\n> [Q4] Clarification on the Primary Cause of Performance Degradation in POMDPs\n\nWe appreciate the reviewer's insightful question regarding performance in POMDP settings. While the gap between actual execution and planning due to the absence of transition function simulation could indeed contribute to performance degradation, our analysis reveals a more fundamental issue.\n\nAs documented in the MCTD paper (Appendix A7.7) and confirmed through our extensive experiments, the primary challenge stems from **trajectory collapse** during long-horizon generation in POMDP environments—specifically, later trajectories becoming stuck in suboptimal states. The MCTD paper attempted to address this through frequent online replanning at short intervals; however, this approach remains inherently **myopic** and constrains performance improvements.\n\nOur C-MCTD framework directly tackles this limitation through **inference-time stitching methods** that maintain global coherence while avoiding trajectory collapse. This approach demonstrates substantial performance gains, particularly in complex large-scale environments where traditional replanning strategies struggle.\n\n> [L] On the Limitations and Application Scope of C-MCTD\n\nWe thank the reviewer for the constructive suggestion to further elaborate on the limitations of our method. We will clarify this in the final version.\n\nOur discussion did not originally center on a direct comparison with standard MCTD or Diffuser because **C-MCTD is architected to address a fundamentally different challenge: composing long-horizon plans that exceed the trajectory lengths of the training data.** In contrast, methods like MCTD and Diffuser focus on optimizing planning *within* the horizon of the training data. C-MCTD is a solution for inference-time generalization to out-of-distribution plan lengths, a scope where direct application of standard diffusion planners is not feasible.\n\nWhen compared to traditional search algorithms, a key prerequisite for C-MCTD—and diffusion planners in general—is the requirement for an offline trajectory dataset and a corresponding offline model training phase. For our Preplan Composer variant, an additional preliminary step involves the construction of a plan graph.\n\nTherefore, the application scope of C-MCTD is specifically for domains where: 1) an offline dataset is available, and 2) the primary goal is to solve long-horizon tasks that surpass the lengths of the available demonstration trajectories.\n\nWithin this defined scope, C-MCTD demonstrates significant value.\n\n- It substantially outperforms relevant baselines, as evidenced in **Table 1**.\n- It proves effective in complex compositional tasks that inherently demand long-term planning, such as the multi-cube robotic manipulation task (**Table 3**) and the Visual PointMaze task, where generating long plans is notoriously difficult (**Table 4**).\n\nWe will add this detailed discussion to the paper to clearly define the application scope and limitations of C-MCTD."}, {"review_id": "yj3teiq2DP", "reviewer": "Reviewer_y79K", "summary": "This work tackles long-horizon planning tasks, applying methods trained on shorter planning datasets (e.g., upto 100 steps) to test environments that requires longer planning (e.g., 1000 steps). The authors proposed three \"stitching\" methods to extend planning ability of existing work (Monte Carlo Tree Diffusion). Specifically, the author introduces 1) Online-Composer which performs online MCTS over subplans to extend planning horizon; 2) Distributed Composer to speed up 1); and 3) Preplan Composer which utilizes offline plans to bootstrap online search performance. The authors evaluated their methods against other baselines in various environments in the OGBench, and showed improvements in long-horizon planning against other methods.", "questions": "Question:\n- Why are baselines different in different experiments? Table 1 included baselines such as CompDiffuser, but they are not included in Table 3 and Table 4?\n\nTypos:\n- In L106 the subscripts 1:s and s+1:S are not formatted correctly\n- in L205-206 \"ParTS-MCTD\" is a new method name?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n- This paper proposed novel inference-time stitching methods to enables long-horizon planning beyond the length seen during \"training\".\n- The authors experimented with multiple tasks in the OGBench and showed their methods improves generalization in long horizon environments.\n\nWeaknesses:\n1. Planning runtime is only compared between the three methods proposed in this work, but not against other prior work. These should be reported in Table 1 along with other methods to provide a more transparent comparison.\n2. The best method (Preplan composer) takes significant runtime (mentioned in 228-229) as it involves an additional offline planning phase. This limits generalization ability as 1) the test environment may not be always accessible a priori; and 2) it is unclear how much offline planning is \"enough\".\n3. Preplan composer shows strong performance on giant mazes in Table 1 by utilizing plans composed offline in the same environment. Wouldn't this make comparisons against other planners unfair, since I assume all other planners only had access to small mazes (up to 100steps) during training? Without preplan composer, Table 1 shows that CompDiffuser (a prior work) achieved the best performance compared to the proposed methods.", "was_revised": true, "final_justification": "the authors have provided a full runtime table, show clarifying that the proposed methods is both performant and computationally fast. Additionally, the response have clarified a few experimental setting about preplan composer (potentially accessing the test environment in advance). I believe my concerns are mostly addressed, and hence I raise my quality and overall score.", "rebuttal": "We would like to thank the reviewer for their valuable feedback.\n\n> [W1] Planning runtime is only compared between the three methods proposed in this work, but not against other prior work.\n\nThank you for highlighting the importance of comprehensive runtime comparisons. We provide planning runtime comparisons with all baseline methods below.\n\n**Comprehensive Planning Runtime Comparison**\n\nWe have conducted extensive runtime comparisons across all baseline methods. CompDiffuser's runtime was not reported in their paper and thus could not be included. \n\n**Key Performance-Efficiency Analysis**\n\nOur C-MCTD methods demonstrate superior performance while maintaining competitive planning runtimes:\n\n- **Medium environment**: All C-MCTD variants achieve >90% task success rate. Compared to the strongest baseline MCTD-Replan (90% success rate), our methods **run 2-15× faster.**\n- **Large environment**: Distributed and Preplan Composer achieve 100% task success rate (vs. <50% for baselines) while **maintaining planning times comparable to or better than most baselines**, excluding DatasetStitch variants.\n- **Giant environment**: Preplan Composer achieves 100% task success rate (vs. 0% for all baselines in the table) **with the most competitive runtime among non-DatasetStitch methods.**\n    \n    \n    | Method | Medium | Large | Giant |\n    | --- | --- | --- | --- |\n    | Diffuser-Replan | 80.2s | 144.7s | 166.8s |\n    | Diffuser-DatasetStitch | 8.4s | 8.3s | 9.4s |\n    | Diffusion Forcing | 18.8s | 26.1s | 30.1s |\n    | Diffusion Forcing-DatasetStitch | 10.9s | 11.5s | 10.9s |\n    | SSD | 32.8s | 33.8s | 42.7s |\n    | MCTD-Replan | 166.5s | 503.7s | 630.1s |\n    | MCTD-DatasetStitch | 50.2s | 77.2s | 53.8s |\n    | Online Composer | 83.6s | 91.2s | 269.8s |\n    | Distributed Composer | 26.7s | 39.1s | 530.7s |\n    | Preplan Composer | 11.1s | 21.5s | 36.9s |\n\n**Significance of Our Contribution**\n\n**C-MCTD introduces efficient inference-time stitching that achieves both effectiveness and efficiency across diverse environments.** The results demonstrate that our tree search-based stitching approach not only outperforms existing methods in task success but does so without prohibitive computational overhead.\n\nWe will incorporate this comprehensive runtime comparison into Table 1 of our revised manuscript to ensure transparent comparison across all metrics.\n\n> [W2] The best method (Preplan composer) takes significant runtime (mentioned in 228-229) as it involves an additional offline planning phase. This limits generalization ability as 1) the test environment may not be always accessible a priori; and 2) it is unclear how much offline planning is \"enough\".\n\nWe thank the reviewer for their insightful question regarding the Preplan Composer's offline planning phase and its potential impact on generalization. We would like to clarify two key aspects that address this concern.\n\nFirst, the offline planning phase does **not** require any prior access to the test environment. Our method, the Preplan Composer, constructs a \"plan graph\" by generating plans between various representative states. These states are identified by clustering positions solely from the *training dataset*. The diffusion planner then generates these plans between clustered states without any access to the test environment.\n\nSecond, we determine the sufficiency of the offline planning using **the same robust reward function employed in the original MCTD framework**. This reward function provides a quantitative measure to evaluate the quality and utility of the pre-generated plans.\n\nThis strategic pre-planning is precisely what enables the Preplan Composer to achieve significant efficiency gains at inference time without sacrificing performance or generalizability.\n\n> [W3] Preplan composer shows strong performance on giant mazes in Table 1 by utilizing plans composed offline in the same environment. Wouldn't this make comparisons against other planners unfair, since I assume all other planners only had access to small mazes (up to 100steps) during training? Without preplan composer, Table 1 shows that CompDiffuser (a prior work) achieved the best performance compared to the proposed methods.\n\nWe thank the reviewer for raising this important question about the fairness of our experimental setup. We would like to clarify that **all diffusion planners, including ours, were trained under identical conditions** (up to 100 steps on medium/large/giant mazes).\n\nThe key distinction of Preplan Composer lies not in its training advantage, but in its **novel inference-time methodology**. Between training and inference, Preplan Composer introduces an additional plan graph building phase that enables more efficient planning during actual deployment. This intermediate step represents a fundamental innovation in our approach—while other methods lack mechanisms to leverage such preprocessing for enhanced planning efficiency, our method demonstrates that inference-time scaling through strategic preprocessing can significantly improve performance.\n\nWe acknowledge the reviewer's observation that CompDiffuser achieves the best performance among baselines when excluding Preplan Composer. However, this comparison highlights a crucial distinction: **CompDiffuser requires specifically designed training for compositional planning, whereas C-MCTD achieves superior results through inference-time scaling alone**. This demonstrates that our approach offers a more flexible and generalizable solution that doesn't require retraining the underlying diffusion model.\n\nThe strong performance of Preplan Composer on giant mazes validates our core hypothesis that inference-time scaling through tree search-based stitching can overcome the limitations of models trained on shorter trajectories. Rather than being an unfair advantage, this represents the successful realization of our method's design goals.\n\n> [Q1] Why are baselines different in different experiments? Table 1 included baselines such as CompDiffuser, but they are not included in Table 3 and Table 4?\n\nWe thank the reviewer for this important question. We would like to clarify our rationale for the baseline selection.\n\nFor the benchmarks in **Table 1** (PointMaze, AntMaze), we used the numbers directly reported in the original CompDiffuser paper for a fair comparison.\n\nThe benchmarks in **Tables 3 and 4** (Robot Arm Cube Manipulation, Visual PointMaze) were **not evaluated in the CompDiffuser paper**. Implementing and validating their method on our distinct, more complex environments was not feasible during the short rebuttal period due to significant engineering requirements.\n\nWe are committed to adding this direct comparison to the revised version to further validate our method's superior performance.\n\n> [Q2] Response to Formatting and Naming Issues\n\nWe sincerely thank the reviewer for their meticulous feedback. We have corrected the subscript notation in L106 to ensure mathematical precision. Additionally, we have resolved the naming inconsistency in L205-206; \"ParTS-MCTD\" was an internal name for our Distributed Composer, and we have updated the manuscript to use this term consistently for clarity."}]

Author rebuttal:

Meta-review: This paper proposes Compositional Monte Carlo Tree Diffusion (C-MCTD), an extension of MCTD designed to overcome limited planning horizons by stitching together multiple short-horizon plans. The framework introduces three complementary strategies—Online Composer (sequential hierarchical stitching), Distributed Composer (parallel plan trees with connections), and Preplan Composer (prebuilt plan graphs)—to enable compositional search during inference. This allows the generation of trajectories more than 10× longer than the training horizon. Experiments on maze navigation, vision-based planning, and robotic manipulation tasks demonstrate that C-MCTD significantly outperforms replanning baselines such as MCTD-Replan and CompDiffuser in both performance and efficiency.

The main strength of the paper, which is acknowledge by the reviewers, is that an important limitation of MCTD, the limited planning horizon, is overcome. The concerns are mostly in terms of presentation and also some aspects in the evaluation.

There has been an extensive discussion with the reviewers, and mostly the opinion is that this is a paper worthy of being accepted. I will follow this recommendation. However, it seems that the paper could benefit from some more clarifications and discussions, which is why I am hesitating to recommend for an oral presentation. The authors should address the reviewers' concerns for the CR version and their presentation.
Decision: Accept (spotlight)