PlanU: Large Language Model Reasoning through Planning under Uncertainty

All tested backbones are in the 7–8B parameter range. Evaluating across more diverse model scales (e.g., smaller or larger LLMs) would improve the generality of the claims.

We further evaluated larger models in Blocksworld, including Qwen2.5-14B-Instruct, OpenAI GPT-4.1, and Google Gemini-2.5-Pro. These cover both larger-scale open-source and closed-source models. The results are summarized in the following table. PlanU performs well both on larger-scale open-source and closed-source models.

OpenAI/GPT-4.1

Google/Gemini-2.5-Pro

Qwen/Qwen2.5-14B-Instruct

The ablation study could be more fine-grained. For example, testing hybrid configurations such as quantile + standard UCT or mean value + UCC would better isolate the individual contributions of each module.

Thanks for your valuable advice. We have conducted such fine-grained ablation studies. Specifically, the hybrid configurations suggested are clearly presented in Appendix Figure 10:

1. For the mean value + UCC, it is depicted as 'PlanU w/o dist'.
2. The quantile + standard UCT is depicted as 'PlanU w/o UCC'.

Tomato lettuce salad

Entertainment

Ablation results show PlanU outperforms PlanU w/o dist and PlanU w/o UCC in both scenarios, with faster convergence and better optimal performance—confirming the critical role of both components.

To provide more information to the reviewer, we have conducted experiments to evaluate the impact of the text encoder used in UCC, and evaluate the impact of the number of quantiles.

For text encoders, the default PlanU performs better in medium-to-high iterations across both scenarios. While the two all-MiniLM variants show slightly lower overall performance, their gap with the default narrows in later iterations, indicating UCC's compatibility with different encoders.

The different sentence-transformer models in Tomato salad

The different sentence-transformer models in Tomato lettuce salad

The default setting of 51 quantiles (n=51) outperforms both n=41 and n=61 in most iterations, particularly in later stages. Performance differences across quantile choices are minor, indicating that the method is robust to changes in this parameter, with the default providing the best results in our experiments.

The different number of quantiles in Tomato salad

The different number of quantiles in Tomato lettuce salad

• line 212: a uncertainty-aware - an uncertainty-aware

Thanks for your help. We will check the writing of the paper carefully by using a grammar checker.

W1:The main technical contributions of this paper largely stem from prior works, such as MCTS, QRDQN...

Regarding the technical contribution and novelty, we hold a different opinion from the reviewer.

1. It is common to address a problem through the integration of existing approaches. DQN is an integration of Q-Learning with a deep neural network. Self-consistency is a combination of CoT with majority voting. ToT extends CoT with a tree structure. RAP combines MCTS with LLM. Rainbow combines double Q-learning, prioritized replay, dueling networks, multi-step learning, distributional RL, and noisy nets. These works make a significant contribution to research advancement.
2. Our contribution is threefold. We are the first to identify the common uncertainty pitfall when using vanilla MCTS for LLM planning. Second, we are the first to integrate the quantile distribution into MCTS-based LLM planning. Third, we are the first to integrate random network distillation into MCTS-based LLM planning.
3. Addressing the uncertainty pitfall when using MCTS for LLM planning is non-trivial, none of the existing LLM-based planning approaches addresses the environmental uncertainty and the LLM uncertainty together. We address the uncertainty pitfall through a novel integration of existing approaches. We had shown in Figure 3 that adding uncertainty consideration in CoT, DeLLMa, RAP, and Reflextion fail for stochastic environments.
4. We have conducted multiple experiments combining existing uncertainty-aware methods into LLM planning. RAP-D and RAP-E combine RAP with DMCTS and EMCTS, respectively. DMCTS and EMCTS are methods dealing with uncertainty. RAP-D-UCC replaces the UCT used in RAP-D with the UCC score. As it is shown in the following tables, simple integrations of existing methods that deal with uncertainty do not work effectively.

Tomato salad

Tomato lettuce salad

W2:...Most of the failure cases are manually injected..

We have evaluated PlanU on real-world tasks with more realistic failures. Please refer to our response to Reviewer c3qH and bLkk.

W3:...the expectation operator ( \mathbb{E} ) as the default ( \psi )...the necessity of learning the full distribution ( Z(s_t, a_t) )...

In distributional RL, learning an approximate distribution rather than a single expected value can preserve the multimodality in value distribution, which can lead to more stable learning. As shown in the following tables, PlanU w/o dist—a variant using mean value without learning quantile distribution—performs significantly worse than PlanU.

We also evaluated impacts of different operators: $\tau_ {0.5}$, $\mathbb{E}[Z(s_ t,a_ t)]$ +variance, and $\mathbb{E}[Z(s_ t,a_ t)]$+ $\tau_ {0.9} - \tau_ {0.1}$. $\mathbb{E}[Z(s_ t,a_ t)]$ is the mean operator, $\tau_ {0.5}$, $\tau_ {0.9}$ and $\tau_ {0.1}$ are the value for quantile 0.5, 0.9 and 0.1, respectively. The mean operator (below tables) can lead to first or the second performance.

Tomato lettuce salad

Entertainment

W5:...The LLM is only used for initializing probabilities... ReAct-style agents... based on environmental feedback.

1. As stated (Lines 29-32), PlanU leverages LLMs beyond simple initialization: it explicitly uses them as a world model to simulate outcomes for planning, similar to humans predicting consequences before execution.

2. PlanU does incorporate environmental feedback. As detailed in Figure 2 and Lines 199-206, our backpropagation mechanism dynamically updates action probabilities based on real-world outcomes.

3. In line with the reviewer's suggestion, we did compare our work with powerful agents in Figure 3 and Appendix C2.2: a ReAct-style MCTS agent (LATS, ICML 24) and an uncertainty-aware agent (DeLLMa, ICLR 25). LATS uses ReAct agent and reflection during MCTS planning. DeLLMa infers and predicts hidden factors to make decision. The results (below table) show that PlanU performs better than such powerful agents.

Q1:...wouldn’t simply re-executing the same action suffice? What is the intuitive benefit of introducing a reward distribution...

If an action is optimal, re-executing it suffices, but the agent must learn to know which action is the optimal. Thus, introducing a quantile distribution is necessary to better model potential multimodality in the value distribution. We have explored more realistic failure models. Please refer to our response to Reviewer c3qH and bLkk.

Q2:...removing any single component results in almost no return improvement for the baseline...the proposed method and the baseline do not seem to be clearly distinguishable...

Sorry for the misunderstanding.

1. There are not results for any baselines in Figures 5 (a) and (b). For comparison, we additionally show the results of RAP in below tables. The results show that each component of PlanU leads to performance improvement thanks to their ability to deal with uncertainty.

Tomato lettuce salad

Entertainment

2. For Figure 5c, we demonstrate that PlanU deals with LLM uncertainty well, even for ambiguous instructions. To augment Figure 5c, we evaluated RAP under prompt shuffling (randomly shuffling task/environment description sentences) and injection (adding task-irrelevant but environment-related text)—uncertainties common when prompts include LLM-generated content. Results (below table) show PlanU consistently outperforms RAP in handling LLM uncertainty.

Entertainment

W4:The proposed UCC score lacks theoretical justification...

UCT converges to optimal actions for the tabular case with finite states. However, it is not guaranteed that UCT will converge for neural networks. We leave the theoretical guarantees of UCC as future work.

Dear Reviewer QuAk,

Thanks for your effort in reviewing our work. We deeply appreciate your time and suggestions. NeurIPS is renowned for its rigorous review process. Throughout this process, reviewers provide valuable feedback on both the manuscript and author responses, which significantly fosters progress within the research community. To help us address your concerns most effectively, could you kindly specify any remaining points requiring further clarification?

We have addressed your concerns in the rebuttal. We summarize our response as follows:

1. We addressed your concerns regarding technical novelty and effectiveness (W1) through comparative experiments and ablations, including variants of RAP with uncertainty modeling, as well as comparisons with strong agent (ReAct-style) baselines such as LATS (ICML 24) and DeLLMa (ICLR 25). The results demonstrate that simple combinations of existing methods fail in uncertain settings, while PlanU performs robustly across tasks.
2. We addressed concerens about the experiments(W2) by adding two real-world benchmarks: TravelPlanner and Webshop.
3. We addressed concerns about the value of modeling reward distributions (W3, Q1) by showing that PlanU outperforms its mean-value variant (PlanU w/o dist), and that distributional modeling enables better handling of multimodal returns.
4. We have described the difference among UCT and UCC (W4).
5. We clarified that PlanU uses LLMs not only for initialization but also as world models and incorporates environmental feedback during MCTS updates (W5). PlanU thus enables more dynamic and informed planning than methods that treat LLMs statically.
6. We addressed concerns about component effectiveness and baseline distinguishability (Q2) by clarifying the results of Figures 5(a)(b) with baseline RAP and further evaluate them under prompt perturbations.

---

In summary, based on your feedback we added:

1. Evaluating PlanU and others on two new benchmarks: WebShop and TravelPlanner. In WebShop, the agent needs to buy products according to user instructions, with real internet latency injected to simulate uncertainty. In TravelPlanner, the agent must plan transportation, accommodation, and attractions according to the user's instructions. Real-world transportation delays are injected to simulate uncertainty.
2. Evaluating robustness to prompt perturbations, including shuffled or injected instructions.
3. Direct comparisons with ReAct-style and uncertainty-aware agents: LATS (ICML 24）and DeLLMa (ICLR 25).
4. Additional ablations to quantify the contribution of each PlanU component (e.g., distributional value estimates, UCC).

Do you have any remaining concerns? We are eager to discuss them with you.

Best Regards,
Authors

We show that the UCC score converges to the expectation of the quantile distribution under a tabular setting, if the expectation operator is used. Selecting the action according to the argmax operator on the UCC score can lead to maximizing expected returns. For this, we first prove Lemma regarding the convergence of the novelty score, and then prove the Theorem regarding the convergence of the UCC score.

Lemma 1 (Convergence of Novelty Score). Consider a finite state space $\mathcal{S}$, an encoder $e: \mathcal{S} \to \mathcal{Z}$, and a fixed target function $f: \mathcal{Z} \to \mathbb{R}^k$. Let $\hat{f}: \mathcal{Z} \to \mathbb{R}^k$ be a predictor implemented as a tabular function over the finite latent space $\mathcal{Z}' = e(\mathcal{S})$ (i.e., $\hat{f}(z)$ is an independent learnable vector for each $z \in \mathcal{Z}'$). The novelty reward is defined by the following:

$

r_i(s_t) = \|\hat{f}(e(s_t)) - f(e(s_t))\|_2^2.

$

Under the following assumptions:

1. Infinite visitation: Every state $s \in \mathcal{S}$ is visited infinitely often.

2. Robbins-Monro conditions: For each $z \in \mathcal{Z}'$, the learning rates $\{\alpha_n^{(z)}\}_ {n=1}^\infty$ for updates to $\hat{f}(z)$ satisfy:

$

\sum_ {n=1}^\infty \alpha_ n^{(z)} = \infty \quad \text{and} \quad w\sum_ {n=1}^\infty \left(\alpha_ n^{(z)}\right)^2 < \infty.

$

Thus, the novelty score almost surely converges to zero:

$

\lim_{t \to \infty} r_i(s_t) = 0 \quad \text{a.s.}

$

Proof of Lemma 1.

Since the $\mathcal{S}$ is finite, $\mathcal{Z}' = e(\mathcal{S})$ is also finite. Let $\mathcal{Z}' = \{z_1, \dots, z_M\}$ where $M \leq |\mathcal{S}|$. For any latent point $z \in \mathcal{Z}'$, let $\mathcal{S}_z = \{s \in \mathcal{S} : e(s) = z\}$. By assumption 1, every state $s \in \mathcal{S}_z$ is visited infinitely often. Consequently, each $z$ is updated infinitely often.

At the $n$-th update to $z$, let $\hat{f}^{(n)}(z)$ be the predictor's value and $e_n(z) = \hat{f}^{(n)}(z) - f(z)$. The SGD update minimizes $\mathcal{L}(z) = \|e_ n(z)\|_ 2^2$ and the rule is given by:

$

\hat{f}^{(n+1)}(z) = \hat{f}^{(n)}(z) - \alpha_n^{(z)} \cdot 2e_n(z),

$

This update rule implies the following recursive relationship for the error:

$

e_{n+1}(z) = \left(1 - 2\alpha_n^{(z)}\right) e_n(z).

$

As the update is identical for each dimension of $e_n(z) \in \mathbb{R}^k$, for the $j$-th component $e_n^{(j)}(z)$, the recursion is:

$

e_{n+1}^{(j)}(z) = \left(1 - 2\alpha_n^{(z)}\right) e_n^{(j)}(z).

$

By solving this recursion, we obtain an expression for the error at the $n$-th step:

$

e_n^{(j)}(z) = e_1^{(j)}(z) \prod_{m=1}^{n-1} \left(1 - 2\alpha_m^{(z)}\right).

$

The Robbins-Monro condition, $\sum_m^\infty (\alpha_m^{(z)})^2 < \infty$, implies that $\alpha_m^{(z)} \to 0$ as $m \to \infty$. Thus, $\exists M_z$ such that $0 < 2\alpha_m^{(z)} < 1$ for all $m \geq M_z$. The series $\sum_{m=1}^{\infty} \log\left(1 - 2\alpha_m^{(z)}\right)$ diverges to $-\infty$ because:

$

\log\left(1 - 2\alpha_m^{(z)}\right) \leq -2\alpha_m^{(z)} \quad \forall \alpha_m^{(z)} \in (0,1/2),

$

and the Robbins-Monro condition states that $\sum_{m=1}^{\infty} -2\alpha_m^{(z)} = -\infty$ by $\sum \alpha_m^{(z)} = \infty$. Thus, $\prod_{m=1}^{\infty} \left(1 - 2\alpha_m^{(z)}\right) = 0$.

Finally, we consider any state $s_t \in \mathcal{S}$ and its latent representation $z_t = e(s_t)$. As $t \to \infty$, the number of updates to $z_t \to \infty$. Therefore, the error $e_n(z_t)$ converges to zero. For the novelty score, the following equation holds:

$

\lim_{t \to \infty} r_i(s_t) = \lim_{n \to \infty} \|e_n(z_t)\|_2^2 = 0 \quad \text{a.s.}

$

The Lemma 1 is proven.

Theorem 1 (Convergence of UCC). Consider a finite MDP with state space $\mathcal{S}$, action space $\mathcal{A}$, and an encoder $e: \mathcal{S} \to \mathcal{Z}$. Let $f: \mathcal{Z} \to \mathbb{R}^k$ be a fixed target function and $\hat{f}: \mathcal{Z} \to \mathbb{R}^k$ be a predictor implemented as a tabular function over $\mathcal{Z}' = e(\mathcal{S})$. We define the novelty score as the prediction error $r_ i(s_ t) = \|\hat{f}(e(s_t)) - f(e(s_t))\|^2_2$. The UCC score is given by $\mathrm{UCC}(s_ t, a_ t) = \mathbb{E}[Z(s_ t, a_ t)] + c_1 \cdot \frac{r_ i(s_ t)}{N(s_ t, a_ t)}$, where $c_1 > 0$ and $N(s_t, a_t)$ is the visit count of $(s_ t, a_ t)$.

Under the following assumptions:

1. Every state $s \in \mathcal{S}$ is visited infinitely often.

2. For each $z \in \mathcal{Z}'$, the learning rates $\{\alpha_n^{(z)}\}$ satisfy the Robbins-Monro conditions:

$

\sum_{n=1}^\infty \alpha_n^{(z)} = \infty, \quad \sum_{n=1}^\infty (\alpha_n^{(z)})^2 < \infty.

$

Then, the UCC score almost surely converges to the expectation of the quantile distribution:

$

\lim_{t \to \infty} \mathrm{UCC}(s_t, a_t) = \mathbb{E}[Z(s_t, a_t)] \quad \text{a.s.}

$

Proof of Theorem 1

We first decompose the UCC score and obtain that:

$

\mathrm{UCC}(s_t, a_t) - \mathbb{E}[Z(s_t, a_t)] = c_1 \cdot \frac{r_i(s_t)}{N(s_t, a_t)}.

$

From Lemma 1, $r_i(s_t) \to 0$ a.s. Furthermore, since counts start at 1, $N(s_t, a_t) \geq 1$ for all $t$. Thus, the following inequality holds:

$

0 \leq \frac{r_i(s_t)}{N(s_t, a_t)} \leq r_i(s_t) \quad \forall t.

$

As $r_i(s_t) \to 0$ a.s., we can obtain the following result by the squeeze theorem:

$

\lim_{t \to \infty} \frac{r_i(s_t)}{N(s_t, a_t)} = 0 \quad \text{a.s.}

$

Consequently, we conclude that the difference between the UCC score and the expectation of the quantile distribution converges to zero almost surely:

$

\lim_{t \to \infty} \left( \mathrm{UCC}(s_t, a_t) - \mathbb{E}[Z(s_t, a_t)] \right) = 0 \quad \text{a.s.},

$

which implies $\mathrm{UCC}(s_t, a_t) \to \mathbb{E}[Z(s_t, a_t)]$ a.s.

The Theorem 1 is proven.

Therefore, we discovered a key insight. The term $\frac{r_i(s_t)}{N(s_t, a_t)}$ vanishes almost surely because:

1. $r_i(s_t) \to 0$ due to infinite state visitation and SGD convergence.
2. $N(s_t, a_t) \geq 1$ prevents divergence.

The result holds for any encoder $e$ since $\mathcal{Z}'$ remains finite.

Dear Reviewer QuAk,

Thank you for your effort in reviewing our work. The author-reviewer discussion phase will be closed in less than 4 hours. We hope our responses have fully addressed your concerns; if so, could you please reconsider your rating? Are there any remaining concerns?

Best regards,

Authors of PlanU

W1: Incorrect claims about MCTS: ...standard MCTS is unsuitable for stochastic environments...canonical UCT algorithm was explicitly designed for...stochastic settings.

Sorry for the misunderstanding about the motivation and positioning. We will make them clearer.

1. We agree with the reviewer that canonical UCT [1] guarantees convergence probability 100% for selecting optimal actions (i.e., action stochasticity $p(a|s)$), as established in the original UCT analysis. However, this action selection stochasticity ($p(a|s)$) is fundamentally distinct from environmental stochasticity ($p(s'|s,a)$) considered in this work. The former governs exploration/exploitation trade-offs during decision-making, while the latter characterizes transition uncertainty inherent to the environment itself.

2. The canonical UCT algorithm is unsuitable for stochastic environments, as discussed in [2]. We have shown in Figure 3 that UCT (written as LLM-MCTS) cannot model the true tree structure, which lead to wrong Q value estimation. Sparse UCT [2] addresses this drawback by allowing multiple child nodes per action (corresponding to different stochastic outcomes), while retaining the UCT action selection policy. Conceptually, Sparse UCT can be viewed as a simplified variant of our PlanU method, lacking its quantile distribution and UCC components. pUCT [3] improve planning through incorporating action priors (i.e., LLM priors). Our results (detailed below) demonstrate PlanU's superior performance compared to UCT, Sparse UCT, pUCT for LLM planning.

Tomato salad

Tomato lettuce salad

3. In line with the reviewer's suggestion, we had already compared our work with RAP (LLM+UCT), a method designed for LLM-based planning. Our evaluation shows that RAP's performance drops significantly in stochastic environments (Figure 1). Critically, and as detailed in Figures 3, 4, and Table 1, our method significantly outperforms RAP. This performance advantage also holds against the RAP variants incorporating uncertainty-dealing mechanisms, RAP-D and RAP-E (Figures 3, 4, Table 1).

W1: Mischaracterizing a design choice as a fundamental limitation: ...LLM-based MCTS baselines...not designed for stochastic outcomes...It is not...a fundamental limitation of the MCTS framework...

4. It is a limitation when applying vanilla MCTS for LLM even if the environment is deterministic. As we have stated in the introduction, LLM planning suffers from LLM generation uncertainty, when using LLM as the world model (as we do in this work), LLM may generate different text descriptions even for the same state. This may be interpreted as different stochastic states. Moreover, state aliasing (e.g., caused by partial observability) could effectively introduce environmental stochasticity for a deterministic environment.

5. We agree with the reviewer that the drawback of vanilla MCTS can be viewed as a "simplifying implementation choice". For example, Sparse UCT [2] can be viewed as a non-simplified version of UCT for stochastic environments. We will add such discussion into the main text and present the results of MCTS with modeling stochastic environment outcomes (Sparse UCT).

[1]Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 2006

[2]Lower bounding Klondike solitaire with Monte-Carlo planning, Conf. Autom. Plan. 2009

[3]Combining online and offline knowledge in UCT. ICML 2007

W2: Quality of evaluation: ...Introducing stochasticity by...having a random chance of an action failing...on problems with genuine, inherent uncertainty.

L1: Generalization and scope: The evaluation is confined to planning tasks with artificially injected, simplistic stochasticity... more complex and naturalistic uncertainty.

In this rebuttal, we evaluate PlanU on two real-world planning benchmarks: a travel planning benchmark and a web agent benchmark using more realistic failure models. Please refer them to our response to Reviewer c3qH.

W3: The rationale for initializing the value distribution Z during the expansion phase using the policy's sampling probability is not justified...

Q2: ...specific choice of initializing the value distribution Z based on the policy's action probability during expansion? An ablation study...

The proposed initialization serves as a warm start for the policy. We have studied different initialization strategies: random and uniform. The random choice initialize the distribution randomly, whereas the uniform choice assign a uniformly spaced set of points within the interval [0, 1] to the distribution. Their results, obtained from the Blockworld experiment where Mistral-7B was used as the underlying LLM, are listed as follows. It is shown that using the prior from LLM for initilization can significantly speed up learning.

Blockworld

For closed-source model the prior probability of LLM cannot be obtained, we choose initialize the distribution using the uniform strategy. As it is depicted in our response to Reviewer c3qH regarding GPT-4.1 and Gemini-2.5-Pro, PlanU performs better than RAP significantly.

Q1: ...canonical MCTS algorithms like UCT can handle stochastic environments...why they are insufficient for the problems...directly extend an UCT algorithm to LLMs and use it as a baseline?

We had compared our work with RAP, an algorithm that extend UCT algorithm to LLMs. It performs poorly in stochastic environments on 7-8B LLMs, as depicted in Figure 3, 4 and Table 1. We shows the results between PlanU and RAP on Blocksworld on large LLMs as follows.

Openai/GPT-4.1

Google/Gemini-2.5-pro

Qwen/Qwen2.5-14B-Instruct

L2:Failure modes: A discussion of potential failure modes would be valuable.

1. In the WebShop benchmark, we inject internet latency into web-related actions. An action is considered failed if the latency exceeds a predefined timeout period.

2. For the TravelPlanner benchmark, we simulate real-world uncertainty — a critical challenge in travel planning where transportation delays often disrupt itineraries — by injecting realistic delay probabilities into planes and trains. These probabilities are derived from two sources: empirical probability density function (PDF) modeling [4] and a National Transportation statistics. Specifically, the delay probabilities for flights are as follows:

For trains, the delay probability is set to 2% based on the average of the past 5 years from a National Transportation. Such delays can invalidate subsequent segments of generated travel plans, regarding as failure modes, mirroring how real-world disruptions (e.g., a delayed flight causing missed train connections) impact trip feasibility.

[4]Statistical characterization of airplane delays, Scientific Reports 2021

Dear Reviewer bLkk,

Thanks for your effort in reviewing our work. To help us address your concerns most effectively, could you kindly specify any remaining points requiring further clarification?

We have addressed your concerns in the rebuttal. We summarize our response as follows.

1. We addressed your concerns regarding the suitability of MCTS for stochastic environments (W1, Q1, Q2) by clarifying the difference between action stochasticity and environmental stochasticity. We further compared PlanU with canonical UCT, Sparse UCT, and pUCT in both synthetic and real-world environments, demonstrating PlanU's superior performance.

2. We addressed your concerns regarding the initialization of the value distribution Z (Q2, W3) by conducting an ablation study comparing different initialization strategies. Results show that using LLM priors leads to faster convergence and better performance.

3. We addressed your concerns regarding the realism of stochasticity (W2, L1, L2) by introducing two real-world planning environments: WebShop and TravelPlanner. These benchmarks include realistic failure modes, such as latency-based action failures and probabilistic transportation delays derived from empirical data and national statistics.

In summary, based on your feedback we added:

1. Ablation studies on value distribution initialization to validate the design choice。
2. Two new benchmarks (WebShop, TravelPlanner) with empirically grounded stochasticity and realistic failure modes.
3. Extended experiments using GPT-4.1, Gemini-2.5-Pro, and Qwen2.5-14B, showing that PlanU consistently outperforms RAP even in high-performance LLM settings.

During the rebuttal, we have also added:

1. A discussion of Sparse UCT and its conceptual relation to PlanU, and additional experimental results to support this comparison.
2. Compute cost and token/runtime experiments
3. Experiments on different operater and different setence-transformer models.
4. Abalations experiments of prompt perturbation between PlanU and RAP.

Do you have any remaining concerns? We are eager to discuss them with you.

Best Regards,
Authors

W1: The three datasets the paper use are toy, textual and simulated. There're no real-world, long-horizon tasks with rich observations or actuation. And the model sizes are small.

Q2: Can PlanU perform well on some real-world tasks? Q3: Can PlanU been adapted to Web agent?

In this rebuttal, we evaluate PlanU on two real-world planning benchmarks: a travel planning benchmark and a web agent benchmark using Qwen3-14B as the underlying LLM.

1. Travel Planning Benchmark (TravelPlanner [1]): This benchmark requires an agent to generate a comprehensive plan encompassing transportation, meals, and accommodation based on a user query. The agent can perform various search actions to gather necessary information before making decisions. To simulate real-world uncertainty, we inject delay probabilities for planes and trains. The injecting delay probabilities are derived from the empirical probability density function (PDF) modeling [2] and a National Transportation statistics. Consequently, delays can invalidate subsequent segments of the generated plan. We evaluated 45 tasks of easy/medium/hard difficulty with TravelPlanner. The evaluation metrics includes Task Completion Rate (covers core travel elements) and Constraint Satisfaction Rate (average of satisfying TravelPlanner’s commonsense + hard constraints, e.g., no repeated attractions, meeting budget). Results show PlanU outperforms others (table below).

2. Web Agent Benchmark (WebShop [3]): This benchmark evaluates agents tasked with purchasing products in an online shop with over one million items, meeting specific user requirements (e.g., brand, price, size). Agents interact via web clicks and searches, making decisions based on observed pages and interaction history. Crucially, to mimic real-world conditions, web actions incur network latency following a long-tail log-normal distribution [4] (mean 2s), with actions failing if latency exceeds 10 seconds. Performance is measured by reward (percentage of user-specified attributes satisfied) and success rate (frequency of fully meeting all requirements) across 10 shopping instructions. Experimental results (below) demonstrate that PlanU achieves superior performance compared to several baselines.

These evaluations on TravelPlanner and WebShop, incorporating realistic uncertainty like transportation delays and internet latency, highlight PlanU's effectiveness in complex, real-world planning scenarios.

[1]TravelPlanner: A Benchmark for Real-World Planning with Language Agents, ICML 2024

[2]Statistical characterization of airplane delays, Scientific Reports 2021

[3]WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents, NeurIPS 2022

[4]On the log-normal distribution of network traffic,Physica D: Nonlinear Phenomena

[5]Language agent tree search unifies reasoning, acting, and planning in language models, ICML 2024

Q5: Can PlanU been extended to closed-source models?

We evaluate in Blocksworld on OpenAI GPT-4.1 and Google Gemini-2.5-Pro. For closed-source models (e.g., GPT-4.1 and Gemini-2.5-Pro), as the token probability cannot be obtained, we initialized the quantiles using a uniform distribution instead of using the token probability. The results are summarized in the following table. The results show that PlanU perform well on closed-source models (GPT-4.1 and Gemini-2.5-Pro). Besides PlanU perform well on a 14B open source models (Qwen2.5-14B).

Openai/GPT-4.1

Google/Gemini-2.5-pro

Qwen/Qwen2.5-14B-Instruct

W2: Compute cost and token/runtime overhead haven't been discussed. Q1: Can you report wall-clock time, tokens for PlanU vs RAP/ToT?

We had placed a detailed analysis of the computational overhead in Appendix C.5. We study the token usages, query times, wall-clock time, and rewards for the Tomato Lettuce Salad task. The results are shown as follows.

As it is shown, PlanU is highly resource-efficient compared to other MCTS-based methods. It consumes nearly three times fewer tokens than RAP, demonstrating its superior ability to navigate the search space effectively. In general, MCTS-based methods performs better than CoT and ToT at the cost of most token consumption. The higher token requirement when compared to non-search methods like CoT and ToT is an expected trade-off, which allows PlanU to robustly handle complex planning problems under uncertainty, a domain where simpler methods like CoT and ToT frequently fail.

W3: The paper lacks enough details about experiment setup in the main text.

The details of our experimental setup had been described in Appendix C. This includes our general setup and computing resources in Appendix C.1. The setup for the Blocksworld, Overcooked, and VirtualHome environment are detailed in Appendix C.2, C.3, and C.4, respectively. Each of these sections covers the complete task description, observation/action spaces, environment dynamics, and reward structure, ensuring full reproducibility.

Q4: I think it'll be better if the authors include PlanU's performance into figure 1.

We have put the results of the new Figure 1 as follows. It shows that PlanU performs better than CoT, ToT, and RAP both in deterministic and stochastic environments.

Deterministic

Stochastic

Q6: Can you provide a deeper comparison between PlanU and RAP since they are all MCTS-based methods?

We can view PlanU and RAP from four different angles: visual comparison, algorithmic design, performance, and resource consumption.

1. In Section 5.2, Figure 3 visually describes the difference among the trees used by RAP (written as LLM-MCTS) and PlanU. RAP cannot model the Q value for even such a simple task due to the limitation of vanilla MCTS, whereas PlanU models environmental stochastic using quantile distribution. We have described the drawbacks of vanilla MCTS in Appendix A2 in detail.

2. Regarding algorithmic design, PlanU differs from RAP mainly in two aspects: (1) Environmental Uncertainty— RAP uses the vanilla MCTS with UCT. The vanilla MCT+UCT assumes deterministic state transitions, while PlanU does not assume such simplification. It considers environmental stochastic through modeling returns as quantile distributions, which better capture environmental uncertainty during planning; (2) LLM uncertainty — PlanU uses the UCC score, which considers LLM uncertainty, whereas RAP does not explicitly consider such uncertainty.

3. Regarding performance, as we have shown in the new Figure 1 in the previous response, *PlanU performs better than RAP both in deterministic and stochastic environments.

4. Regarding resource consumption on stochastic environments, PlanU consumes fewer tokens and wall clock times than RAP, as we have reported in previous responses. We further report the number of expanded nodes (lower indicates higher efficiency) on Overcooked tasks. PlanU consume a significantly lower cost than RAP, demonstrating both effectiveness and efficiency. Moreover, we show that each component of PlanU contributes its low number of expanded nodes.

Dear Reviewer c3qH,

Thanks for your effort in reviewing our work. We have addressed your concerns in the rebuttal and summarize our response as follows:

1. Real-world applicability (W1, Q2, Q3): We have conducted evaluations on two real-world tasks: TravelPlanner and WebShop, showing PlanU’s superior performance under realistic uncertainties (delays, latency).

2. Closed-source adaptation (Q5): We have evaluated PlanU and others on GPT-4.1 and Gemini-2.5-Pro and additionally on a 14B open-source model (Qwen2.5-14B); the results confirm PlanU's strong performance across all settings.

3. Computational overhead (W2, Q1): We have reported token usage, query counts, and wall-clock time; PlanU is about three times more efficient than RAP.

4. Experiment details (W3): We have clarified setups in Appendix C for full reproducibility.

5. Comparison with RAP (Q4, Q6): We have improved Figure 1 accordingly, and find that PlanU consistently outperforms RAP in both deterministic and stochastic settings.

Do you have any remaining concerns? We are eager to discuss them with you.

Best Regards,

Authors