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

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.