Complex LLM Planning via Automated Heuristics Discovery

📄 arXiv: 2502.19295v1 📥 PDF

作者: Hongyi Ling, Shubham Parashar, Sambhav Khurana, Blake Olson, Anwesha Basu, Gaurangi Sinha, Zhengzhong Tu, James Caverlee, Shuiwang Ji

分类: cs.AI

发布日期: 2025-02-26

💡 一句话要点

提出AutoHD，通过自动启发式搜索提升LLM在复杂规划任务中的性能

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

关键词: 大型语言模型 复杂规划 启发式搜索 自动化 可解释性 推理 人工智能 任务规划

📋 核心要点

  1. 现有LLM规划方法依赖不可靠的自验证或昂贵的外部验证，缺乏效率和可解释性。
  2. AutoHD通过让LLM自动生成和进化启发式函数，指导推理搜索，提升规划的准确性和效率。
  3. 实验表明，AutoHD在多个基准测试中显著优于现有方法，在某些数据集上准确率近乎翻倍。

📝 摘要（中文）

本文旨在提升大型语言模型（LLMs）在复杂规划任务中的能力。现有方法依赖于不可靠的自我验证或外部验证器来评估中间步骤，这需要大量的数据和计算资源。为此，我们提出了一种新颖的方法：自动启发式发现（AutoHD），它使LLMs能够显式生成启发式函数，以指导推理时的搜索，从而准确评估中间状态。这些启发式函数通过启发式进化过程进一步完善，提高了其鲁棒性和有效性。我们提出的方法不需要额外的模型训练或微调，并且LLMs生成的启发式函数的显式定义提供了对推理过程的可解释性和洞察力。在各种基准测试中进行的大量实验表明，该方法优于多种基线，在某些数据集上的准确率几乎翻了一番，证明了我们的方法是复杂规划任务中一种可靠且可解释的解决方案。

🔬 方法详解

问题定义：论文旨在解决大型语言模型（LLMs）在复杂规划任务中面临的挑战。现有方法，如依赖自我验证或外部验证器，存在不可靠、计算成本高昂以及缺乏可解释性等问题。这些方法难以有效地评估规划过程中的中间状态，导致最终规划结果不理想。

核心思路：论文的核心思路是让LLMs自动生成启发式函数，并利用这些函数来指导推理时的搜索过程。通过显式地定义启发式函数，可以更准确地评估中间状态，从而提高规划的准确性和效率。此外，通过启发式进化过程，可以进一步完善这些启发式函数，提高其鲁棒性和有效性。

技术框架：AutoHD方法主要包含两个阶段：启发式函数生成和启发式函数进化。在启发式函数生成阶段，LLM被提示生成用于评估中间状态的启发式函数。在启发式函数进化阶段，通过迭代地评估和改进这些启发式函数，提高其性能。整个过程无需额外的模型训练或微调。

关键创新：AutoHD的关键创新在于它能够让LLMs自动生成和进化启发式函数，从而指导推理搜索。与现有方法相比，AutoHD不需要依赖外部验证器或进行昂贵的模型训练，并且生成的启发式函数具有可解释性。这种方法能够更有效地利用LLMs的知识和推理能力，从而提高复杂规划任务的性能。

关键设计：论文中，启发式函数的生成是通过提示LLM来完成的，提示词的设计至关重要，需要引导LLM生成有效的评估函数。启发式进化过程采用了一种迭代的优化方法，通过评估启发式函数在不同状态下的表现，并根据评估结果进行调整和改进。具体的参数设置和优化算法的选择可能因任务而异，需要在实验中进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，AutoHD在多个复杂规划基准测试中显著优于现有方法。例如，在某些数据集上，AutoHD的准确率几乎是基线的两倍。此外，实验还验证了启发式进化过程的有效性，证明了通过迭代优化可以显著提高启发式函数的性能。

🎯 应用场景

AutoHD方法具有广泛的应用前景，可应用于机器人导航、游戏AI、任务调度、供应链优化等领域。通过提升LLM在复杂规划任务中的能力，可以实现更智能、更高效的自动化解决方案。该研究还有助于提高AI系统的可解释性，促进人机协作。

📄 摘要（原文）

We consider enhancing large language models (LLMs) for complex planning tasks. While existing methods allow LLMs to explore intermediate steps to make plans, they either depend on unreliable self-verification or external verifiers to evaluate these steps, which demand significant data and computations. Here, we propose automated heuristics discovery (AutoHD), a novel approach that enables LLMs to explicitly generate heuristic functions to guide inference-time search, allowing accurate evaluation of intermediate states. These heuristic functions are further refined through a heuristic evolution process, improving their robustness and effectiveness. Our proposed method requires no additional model training or fine-tuning, and the explicit definition of heuristic functions generated by the LLMs provides interpretability and insights into the reasoning process. Extensive experiments across diverse benchmarks demonstrate significant gains over multiple baselines, including nearly twice the accuracy on some datasets, establishing our approach as a reliable and interpretable solution for complex planning tasks.