acceptodds
Withdrawn from ICLR 2027

Going Beyond Scalar: Semantic Monte Carlo Tree Search for Planning with Large Language Model

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Real-world planning rarely admits a single fixed objective. User queries may combine hard constraints, priorities, soft preferences, and objectives such as cost, convenience, or comfort, making it difficult to encode user intent with a scalar reward. Conventional planning methods, including Monte Carlo Tree Search (MCTS), nevertheless evaluate states using scalar values and select actions through numerical exploration–exploitation criteria such as UCT, potentially discarding semantic information needed for flexible natural-language planning. To address this limitation, we propose Semantic Monte Carlo Tree Search (S-MCTS), which performs planning directly in a semantic value space. Instead of a scalar value, each state maintains a future situation—the best structured plan discovered through that state—and an LLM-generated summary evaluating it against the user's constraints, priorities, preferences, and objectives. In action selection, S-MCTS replaces UCT with LLM-based semantic exploration–exploitation, where candidate actions are annotated with summaries of their future situations and selected through query-conditioned reasoning. During backpropagation, parent and child summaries are compared, and the parent adopts the child's future situation when it is better. Thus, S-MCTS reformulates value representation, selection, and backup as semantic reasoning, enabling search under heterogeneous and difficult-to-scalarize requirements. Empirical results show that S-MCTS outperforms representative baselines on standard and flexible travel-planning benchmarks.

Primary area:
applications to robotics, autonomy, planning
Keywords:
planning, tree search, semantic representation, generalization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_C6owOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes S-MCTS for planning under natural-language constraints, priorities, and preferences. Each search node stores its best discovered complete plan and a semantic summary. An LLM uses these summaries to select branches and propagate better plans, replacing numerical selection and backup. Experiments on TravelPlanner, Natural Plan–Trip Planning, and generated flexible travel-planning queries show competitive performance across three backbone models. Additional experiments examine priority satisfaction, component ablations, and token consumption.

Critical strengths
  • Retaining complete candidate plans and explanations of which requirements they satisfy or violate is a meaningful direction for flexible planning. This information directly guides search decisions instead of only explaining the final output, potentially helping the planner handle conflicting requirements.

  • The evaluation is relatively comprehensive. Beyond overall success rates, the supplementary material reports satisfaction rates at different priority levels and separately examines semantic selection and backpropagation. These results provide useful evidence for the proposed components. The additional token consumption is also reported.

Critical weaknesses

The experiments do not sufficiently establish whether the gains come from semantic evaluation itself.

  • In Appendix E, the scalar baseline simply counts the fraction of satisfied constraints, ignoring their priorities. It can therefore prefer satisfying several low-priority requirements while violating a high-priority one. Outperforming this baseline does not demonstrate that semantic evaluation is better than numerical evaluation that appropriately represents the user’s priorities. The authors do not include scalar baselines that account for priorities, arguing that the appropriate weights are unknown. However, once the priorities are identified from the query, a baseline can compare higher-priority requirements first, without tuning weights for each task.

  • In addition, Appendix F shows that S-MCTS consumes more tokens, without comparing performance under equal token or LLM-call budgets. The results support the method’s effectiveness, but do not clearly separate the benefits of semantic information from those of a better-aligned evaluation objective and additional computation.

Questions for authors
  • Would S-MCTS retain its advantage over a numerical evaluator that respects the query’s priorities? For example, could the same LLM extract the priority levels, followed by fixed priority rules or lexicographic comparison? Why would such a baseline necessarily require unknown or tuned weights?

  • How much of the improvement remains under equal token or LLM-call budgets? Could the authors provide this comparison and specify the stopping parameter B and the budgets used for each method?

Reviewer_1zy6OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies LLM planning under multiple requirements that may conflict or have different priorities. The authors argue that a single score can hide which requirements are satisfied and why one plan is preferable. They propose S-MCTS, which stores complete plans and textual assessments in a search tree and uses LLM judgments for branch selection and backpropagation. Experiments on TravelPlanner, Natural Plan's Trip Planning task, and prioritized travel queries constructed following Flex-TravelPlanner report higher success rates across three backbone models; for example, TravelPlanner success with Gemini-2.5-Pro is 93.9%, compared with 86.1% for CoT.

Critical strengths
  1. The problem is practically relevant. Real planning requests can combine hard constraints, soft preferences, and conflicting priorities. Addressing these distinctions is more useful than simply counting satisfied requirements.

  2. The method is coherently organized and has preliminary empirical support. Complete plans and textual assessments are used in both selection and backpropagation. Table 1 reports higher overall success rates than the listed baselines across three backbone models and three travel-planning settings.

Critical weaknesses
  1. The methodological novelty is limited. S-MCTS mainly replaces numerical MCTS operations with prompted LLM judgments, without demonstrating a substantive advance over existing search and feedback-based revision methods.

  2. The experimental support is narrow and incomplete. Evaluation is restricted to travel planning, and the supplied version does not validate the accuracy or consistency of the LLM judgments guiding search.

  3. The added inference cost is not justified by the reported results. Repeated plan generation and evaluation increase computation, but the comparisons do not isolate this effect. The gains therefore cannot be clearly attributed to the search mechanism.

Questions for authors
  1. Which component provides the main benefit: retaining complete plans, textual assessment, semantic selection, or semantic backpropagation? Can controlled ablations and comparisons with priority-aware numerical evaluation establish this, and how reliable are the LLM plan comparisons?

  2. How does S-MCTS compare with stronger reasoning backbones and simpler workflows under comparable information access and inference budgets, considering success rate, end-to-end latency, and total token cost? Please provide the cited appendices and clarify the construction and scoring of the prioritized queries.

Reviewer_ZbPzOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Semantic Monte Carlo Tree Search (S-MCTS) for natural-language planning with hard constraints, priorities, and soft preferences. Each node stores the best complete plan found through that node and an LLM-generated summary describing how it satisfies the user’s requirements. Instead of using UCT, an LLM selects branches based on candidate actions, their summaries, and visit counts. During expansion, the method generates candidate actions and completes a rollout for each new child. Backpropagation compares parent and child summaries and passes the preferred plan toward the root.

Critical strengths
  • The research problem is clearly defined. Natural-language requests often combine hard constraints, priorities, and soft preferences. Explicitly retaining which constraints are satisfied or violated can help guide planning decisions under these requirements.

  • The results show higher success rates than the strongest listed baseline across three models and three travel-planning settings, including cases with conflicting requirements.

Critical weaknesses
  • S-MCTS changes value representation, action selection, and backpropagation simultaneously. In particular, it replaces conventional value aggregation with retention of the best plan found so far. The gains may therefore come from the backup rule or additional LLM computation. Ablation studies and LLM cost reporting are needed to determine whether the improvements reflect better search or simply more computation.

  • Providing visit counts and asking the LLM to balance exploration and exploitation does not establish that it will explore promising branches with poor initial results. An analysis of whether the method can recover from misleading initial rollouts would strengthen this claim.

  • Node selection and backpropagation rely on LLM-generated summaries and comparisons. These summaries may omit constraints, and the comparisons may produce inconsistent preferences, making performance dependent on the LLM’s reasoning ability. Incorrect comparisons can cause a better plan to be replaced by a worse one. The paper does not establish how consistently these judgments align with independently measured plan quality.

  • The evaluation scope is relatively limited. All three settings involve travel planning, and two are closely related. The results support effectiveness within this domain but provide insufficient evidence for broader claims about general natural-language planning.

Questions for authors

Section 3.1 defines the initial state as an empty action sequence, whereas Section 4.1 describes it as containing the problem and available information. Table 1 lists GPT-5.6-luna, GPT-5-mini, and Gemini-2.5-Pro, while Figure 3 includes GPT-5. These discrepancies need clarification.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.