Plan-over-Graph: Towards Parallelable LLM Agent Schedule

📄 arXiv: 2502.14563v1 📥 PDF

作者: Shiqi Zhang, Xinbei Ma, Zouying Cao, Zhuosheng Zhang, Hai Zhao

分类: cs.AI

发布日期: 2025-02-20

🔗 代码/项目: GITHUB

💡 一句话要点

提出Plan-over-Graph方法，实现LLM Agent任务规划的并行化调度

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

关键词: LLM Agent 任务规划 并行调度 图神经网络 合成数据

📋 核心要点

  1. 现有LLM Agent在复杂任务规划中难以有效支持并行调度，限制了整体效率。
  2. Plan-over-Graph方法将任务分解为子任务图，并在此图上进行规划，天然支持并行执行。
  3. 通过合成图数据和两阶段训练，显著提升了LLM在复杂任务图上的规划性能。

📝 摘要（中文）

大型语言模型（LLMs）在任务规划方面展现了卓越的推理能力。然而，并行调度方面的挑战尚未得到充分探索。本文提出了一种新的范式，即plan-over-graph，其中模型首先将现实世界的文本任务分解为可执行的子任务，并构建一个抽象的任务图。然后，模型将该任务图作为输入，并生成一个用于并行执行的计划。为了增强复杂、可扩展图的规划能力，我们设计了一个自动且可控的流程来生成合成图，并提出了一个两阶段训练方案。实验结果表明，我们的plan-over-graph方法显著提高了基于API的LLM和可训练的开源LLM的任务性能。通过将复杂任务规范化为图，我们的方法自然地支持并行执行，从而展示了全局效率。代码和数据可在https://github.com/zsq259/Plan-over-Graph获取。

🔬 方法详解

问题定义：现有的大型语言模型在任务规划中表现出色，但对于如何有效地进行并行调度仍然面临挑战。传统的串行规划方法无法充分利用计算资源，导致处理复杂任务时效率低下。此外，如何让LLM理解任务之间的依赖关系并生成合理的并行执行计划也是一个难题。

核心思路：Plan-over-Graph的核心思想是将复杂的任务分解为一系列可执行的子任务，并将这些子任务之间的依赖关系表示为一个图结构。然后，利用LLM对这个图进行理解和推理，生成一个能够最大化并行执行效率的计划。这种方法将任务规划问题转化为图上的规划问题，从而能够更好地利用LLM的推理能力。

技术框架：Plan-over-Graph方法包含以下几个主要步骤：1) 任务分解：将输入的文本任务分解为一系列可执行的子任务。2) 图构建：根据子任务之间的依赖关系构建一个抽象的任务图。3) 图理解与规划：利用LLM对任务图进行理解和推理，生成一个并行执行计划。4) 计划执行：按照生成的计划执行子任务。为了提升LLM在复杂图上的规划能力，论文还设计了一个自动化的合成图生成流程和一个两阶段训练方案。

关键创新：Plan-over-Graph方法的关键创新在于将任务规划问题转化为图上的规划问题，从而能够更好地利用LLM的推理能力。与传统的串行规划方法相比，Plan-over-Graph方法能够自然地支持并行执行，从而提高任务处理效率。此外，通过合成图数据和两阶段训练，可以有效地提升LLM在复杂图上的规划性能。

关键设计：论文设计了一个自动化的合成图生成流程，用于生成大规模的训练数据。该流程可以控制图的规模、复杂度和依赖关系等属性。此外，论文还提出了一个两阶段训练方案，第一阶段使用合成数据进行预训练，第二阶段使用真实数据进行微调。这种训练方案可以有效地提升LLM在复杂图上的泛化能力。具体的损失函数和网络结构细节在论文中未详细说明，属于未知信息。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，Plan-over-Graph方法在API-based LLMs和可训练的开源LLMs上均取得了显著的性能提升。具体的数据提升幅度未在摘要中明确给出，属于未知信息。该方法通过将复杂任务规范化为图，实现了自然地并行执行，展示了全局效率。

🎯 应用场景

Plan-over-Graph方法可应用于各种需要复杂任务规划和并行执行的场景，例如智能助理、自动化流程管理、机器人控制等。通过将任务分解为子任务图，并利用LLM进行智能规划，可以显著提高任务处理效率和自动化程度。该方法有望在工业自动化、智能家居等领域发挥重要作用。

📄 摘要（原文）

Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning. However, challenges remain under-explored for parallel schedules. This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph. The model then understands this task graph as input and generates a plan for parallel execution. To enhance the planning capability of complex, scalable graphs, we design an automated and controllable pipeline to generate synthetic graphs and propose a two-stage training scheme. Experimental results show that our plan-over-graph method significantly improves task performance on both API-based LLMs and trainable open-sourced LLMs. By normalizing complex tasks as graphs, our method naturally supports parallel execution, demonstrating global efficiency. The code and data are available at https://github.com/zsq259/Plan-over-Graph.