Cost-Awareness in Tree-Search LLM Planning: A Systematic Study
Zihao Zhang1 Hui Wei2 Kenan Jiang1 Shijia Pan2 Kai Shu1 Fei Liu1 1Emory University 2University of California, Merced {zihao.zhang, kenan.jiang, kai.shu, {huiwei2,
Abstract
Planning under resource constraints is central to real-world decision making, yet most large language model (LLM) planners assume uniform action costs. We systematically analyze whether tree-search LLM planners are cost-aware and whether they efficiently generate budget-feasible plans. In contrast to black-box prompting, explicit search trees expose intermediate decisions, node evaluations, and failure modes, which allows for controlled ablations of planner behavior. We study depth-first search, breadth-first search, Monte Carlo Tree Search, and bidirectional search within a unified framework. Our experiments show that existing tree-based LLM planners often struggle to find cost-optimal plans, and that additional search computation does not reliably improve optimality. Among the methods evaluated, bidirectional search achieves the best overall efficiency and success rate. MCTS achieves the highest optimality on short-horizon tasks. Tree-search planners are especially valuable for studying LLM planning because their reasoning steps are explicit, in contrast to plain LLMs that internalize planning dynamics through post-training trajectories. Our findings suggest that improving LLM pl
中文速览
大多数大语言模型（LLM）规划器把每一步行动的代价视作相同，但现实中不同行动往往消耗截然不同的资源，这使得规划器很容易生成超出预算的方案。研究者以积木世界（BlocksWorld）为测试平台，在统一框架下系统评估了深度优先搜索、广度优先搜索、蒙特卡洛树搜索（MCTS）和双向搜索（Bidirectional Search）四种树搜索 LLM 规划方法在有预算约束场景下的表现。实验发现，现有树搜索规划器普遍难以找到代价最优的方案，而且单纯增加搜索计算量并不能稳定地改善最优性；其中双向搜索在搜索效率和长任务成功率上最为突出，MCTS 则在短任务上的最优性最高。这项研究揭示了当前 LLM 规划在资源约束场景下的核心瓶颈，表明仅靠扩大推理时算力远远不够，未来需要专门设计具备代价感知能力的新搜索算法。
原文 arXiv:2505.14656;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2505.14656v2