Cost-Awareness in Tree-Search LLM Planning: A Systematic Study

📄 arXiv: 2505.14656v2 📥 PDF

作者: Zihao Zhang, Hui Wei, Kenan Jiang, Shijia Pan, Shu Kai, Fei Liu

分类: cs.AI

发布日期: 2025-05-20 (更新: 2026-01-12)

💡 一句话要点

系统研究树搜索LLM规划器的成本意识，揭示其在资源约束下的规划能力不足

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: LLM规划 树搜索 成本意识 资源约束 双向搜索

📋 核心要点

  1. 现有LLM规划器在资源约束下，特别是动作成本不统一时，规划能力不足，难以找到成本最优方案。
  2. 本文采用显式树搜索方法，暴露中间决策过程，便于分析LLM规划器的成本意识和预算可行性。
  3. 实验对比了多种树搜索算法，发现双向搜索在效率和成功率上表现最佳，MCTS在短视距任务中具有优势。

📝 摘要（中文）

在资源约束下进行规划是现实世界决策的核心，但大多数大型语言模型(LLM)规划器假设动作成本是统一的。本文系统地分析了树搜索LLM规划器是否具有成本意识，以及它们是否能有效地生成预算可行的计划。与黑盒提示不同，显式搜索树暴露了中间决策、节点评估和失败模式，从而可以对规划器的行为进行受控消融研究。本文在一个统一的框架内研究了深度优先搜索、广度优先搜索、蒙特卡洛树搜索和双向搜索。实验表明，现有的基于树的LLM规划器通常难以找到成本最优的计划，并且额外的搜索计算并不能可靠地提高最优性。在评估的方法中，双向搜索实现了最佳的整体效率和成功率。MCTS在短视距任务上实现了最高的最优性。树搜索规划器对于研究LLM规划尤其有价值，因为它们的推理步骤是显式的，这与通过后训练轨迹内化规划动态的普通LLM不同。研究结果表明，改进资源约束下的LLM规划可能需要新的搜索算法，而不仅仅是扩展推理时计算。

🔬 方法详解

问题定义：论文旨在解决LLM规划器在资源约束下的规划问题，尤其关注动作成本不统一的情况。现有LLM规划器通常假设动作成本是统一的，这在现实世界中并不常见。因此，这些规划器难以找到成本最优的计划，也无法有效地生成预算可行的计划。现有方法主要依赖黑盒提示，难以深入理解LLM的规划过程和失败原因。

核心思路：论文的核心思路是利用显式树搜索来暴露LLM规划器的中间决策过程，从而更好地理解其成本意识和规划能力。通过构建搜索树，可以观察节点评估、中间决策和失败模式，并进行受控消融研究，分析不同搜索算法的优缺点。

技术框架：论文构建了一个统一的框架，用于评估不同的树搜索算法在LLM规划中的表现。该框架包括以下主要模块：1) LLM作为环境模型，用于评估动作的有效性和成本；2) 树搜索算法，包括深度优先搜索、广度优先搜索、蒙特卡洛树搜索和双向搜索；3) 评估指标，用于衡量规划的成本、成功率和效率。整体流程是：从初始状态开始，LLM根据当前状态生成可能的动作，树搜索算法选择一个动作进行扩展，LLM评估新状态，重复此过程直到达到目标状态或达到预算限制。

关键创新：论文最重要的技术创新点在于利用显式树搜索来研究LLM规划器的成本意识。与黑盒提示相比，树搜索可以暴露LLM的中间决策过程，从而更好地理解其规划能力和局限性。此外，论文还系统地比较了不同的树搜索算法在LLM规划中的表现，为未来的研究提供了指导。

关键设计：论文的关键设计包括：1) 使用LLM作为环境模型，评估动作的有效性和成本；2) 实现了多种树搜索算法，包括深度优先搜索、广度优先搜索、蒙特卡洛树搜索和双向搜索；3) 设计了评估指标，用于衡量规划的成本、成功率和效率。具体的参数设置和损失函数取决于所使用的LLM和树搜索算法。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，现有的基于树的LLM规划器通常难以找到成本最优的计划，并且额外的搜索计算并不能可靠地提高最优性。在评估的方法中，双向搜索实现了最佳的整体效率和成功率。MCTS在短视距任务上实现了最高的最优性。这些结果表明，改进资源约束下的LLM规划可能需要新的搜索算法，而不仅仅是扩展推理时计算。

🎯 应用场景

该研究成果可应用于机器人导航、任务调度、资源分配等领域，尤其是在资源受限的环境下。通过改进LLM规划器的成本意识，可以提高决策效率和质量，降低成本，并为未来的智能体设计提供指导。例如，在智能家居中，可以利用该技术优化能源使用，降低电费支出。

📄 摘要（原文）

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 planning under resource constraints will likely require new search algorithms, rather than solely scaling inference-time compute.