Automating Thought of Search: A Journey Towards Soundness and Completeness

📄 arXiv: 2408.11326v2 📥 PDF

作者: Daniel Cao, Michael Katz, Harsha Kokel, Kavitha Srinivas, Shirin Sohrabi

分类: cs.AI

发布日期: 2024-08-21 (更新: 2025-05-28)

💡 一句话要点

AutoToS：自动化Thought of Search，实现规划问题求解的完备性和可靠性

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自动化规划 大型语言模型 代码生成 单元测试 搜索算法 可靠性 完备性

📋 核心要点

  1. 现有方法依赖LLM作为世界模型定义搜索空间，虽灵活但缺乏可靠性，易出错。
  2. AutoToS旨在自动化Thought of Search (ToS) 过程，无需人工干预，提升效率。
  3. AutoToS通过单元测试反馈迭代优化LLM生成的代码，在多个领域实现100%准确率。

📝 摘要（中文）

大型语言模型（LLMs）正被用于解决需要搜索的规划问题。现有文献大多将LLMs用作世界模型来定义搜索空间，为了灵活性而牺牲了可靠性。最近的一项工作，Thought of Search (ToS)，提出用代码定义搜索空间，并让LLMs生成该代码。ToS需要人工参与，协作生成可靠的后继函数和目标测试。然而，结果是值得的：所有测试的数据集都以100%的准确率解决。因此，自动化ToS过程具有巨大的潜力。我们朝着自动化ToS (AutoToS) 迈出了重要的第一步，将人从与语言模型的交互循环中移除。AutoToS通过来自通用和特定领域的单元测试的反馈，逐步引导语言模型生成可靠且完整的搜索组件。我们表明，AutoToS能够以少量的LLM调用在所有评估的领域中实现100%的准确率。

🔬 方法详解

问题定义：论文旨在解决规划问题中，利用大型语言模型（LLMs）进行搜索时，现有方法可靠性不足的问题。现有方法通常将LLMs作为世界模型，直接定义搜索空间，这种方式虽然灵活，但容易产生不符合实际情况的搜索路径，导致求解失败。人工参与的ToS方法虽然能保证可靠性，但效率较低，难以扩展。

核心思路：AutoToS的核心思路是通过自动化Thought of Search (ToS) 流程，利用LLMs生成用于定义搜索空间的可靠代码，并结合单元测试反馈机制，迭代优化LLM生成的代码，最终实现无需人工干预的、可靠且高效的规划问题求解。

技术框架：AutoToS的整体框架包含以下几个主要阶段：1) LLM代码生成：利用LLM生成定义搜索空间的初始代码，包括后继函数和目标测试；2) 单元测试：对生成的代码进行通用和特定领域的单元测试，检测代码的正确性和完备性；3) 反馈与优化：根据单元测试的结果，生成反馈信息，并将其输入LLM，指导LLM修改和优化代码；4) 迭代：重复上述过程，直到代码通过所有单元测试，达到预期的可靠性和完备性。

关键创新：AutoToS的关键创新在于自动化了ToS流程，无需人工参与即可生成可靠的搜索组件。它通过引入单元测试反馈机制，有效地指导LLM生成符合要求的代码，避免了人工干预带来的效率瓶颈。

关键设计：AutoToS的关键设计包括：1) 精心设计的单元测试用例，涵盖通用和特定领域，能够有效地检测代码的错误；2) 有效的反馈机制，能够将单元测试的结果转化为LLM可以理解和利用的信息，指导LLM进行代码优化；3) 迭代优化策略，能够逐步提高代码的可靠性和完备性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

AutoToS在多个评估领域实现了100%的准确率，证明了其有效性和可靠性。与需要人工参与的ToS方法相比，AutoToS无需人工干预，大大提高了效率。此外，AutoToS仅需少量LLM调用即可达到理想效果，降低了计算成本。

🎯 应用场景

AutoToS可应用于各种需要规划和搜索的领域，例如机器人导航、游戏AI、任务调度等。它能够降低开发成本，提高问题求解的效率和可靠性。未来，AutoToS有望成为一种通用的规划问题求解工具，推动人工智能技术在更多领域的应用。

📄 摘要（原文）

Large language models (LLMs) are being used to solve planning problems that require search. Most of the literature uses LLMs as world models to define the search space, forgoing soundness for the sake of flexibility. A recent work, Thought of Search (ToS), proposed defining the search space with code, having LLMs produce that code. ToS requires a human in the loop, collaboratively producing a sound successor function and goal test. The result, however, is worth the effort: all the tested datasets were solved with 100% accuracy. Consequently, there is great potential to automate the ToS process. We take a first major step towards automating ToS (AutoToS), taking the human out of the loop of interactions with the language model. AutoToS guides the language model step by step towards the generation of sound and complete search components, through feedback from both generic and domain specific unit tests. We show that AutoToS is able to achieve 100% accuracy on all the evaluated domains with a small number of LLM calls.