Plan-over-Graph: Towards Parallelable LLM Agent Schedule

• URL: http://arxiv.org/abs/2502.14563v1
• Date: Thu, 20 Feb 2025 13:47:51 GMT
• Title: Plan-over-Graph: Towards Parallelable LLM Agent Schedule
• Authors: Shiqi Zhang, Xinbei Ma, Zouying Cao, Zhuosheng Zhang, Hai Zhao,
• Abstract summary: Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning. 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.
• Score: 53.834646147919436
• License:
• Abstract: 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.

Related papers

• Interactive and Expressive Code-Augmented Planning with Large Language Models [62.799579304821826]
  Large Language Models (LLMs) demonstrate strong abilities in common-sense reasoning and interactive decision-making. Recent techniques have sought to structure LLM outputs using control flow and other code-adjacent techniques to improve planning performance. We propose REPL-Plan, an LLM planning approach that is fully code-expressive and dynamic.
  arXiv  Detail & Related papers  (2024-11-21T04:23:17Z)
• VeriGraph: Scene Graphs for Execution Verifiable Robot Planning [33.8868315479384]
  We propose VeriGraph, a framework that integrates vision-language models (VLMs) for robotic planning while verifying action feasibility. VeriGraph employs scene graphs as an intermediate representation, capturing key objects and spatial relationships to improve plan verification and refinement. Our approach significantly enhances task completion rates across diverse manipulation scenarios, outperforming baseline methods by 58% for language-based tasks and 30% for image-based tasks.
  arXiv  Detail & Related papers  (2024-11-15T18:59:51Z)
• Enhance Graph Alignment for Large Language Models [33.96082485852042]
  Graph-to-token approaches are popular in enabling Large Language Models to process graph information. Existing methods have a misalignment between self-supervised tasks and supervised downstream tasks. We propose Graph Alignment Large Language Models (GALLM) to benefit from aligned task templates.
  arXiv  Detail & Related papers  (2024-10-15T07:50:34Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• Graph-enhanced Large Language Models in Asynchronous Plan Reasoning [18.402877904882107]
  We find that large language models (LLMs) behave poorly when not supplied with illustrations about the task-solving process in our benchmark AsyncHow. We propose a novel technique called Plan Like a Graph (PLaG) that combines graphs with natural language prompts and achieves state-of-the-art results.
  arXiv  Detail & Related papers  (2024-02-05T08:26:33Z)
• Integrating Graphs with Large Language Models: Methods and Prospects [68.37584693537555]
  Large language models (LLMs) have emerged as frontrunners, showcasing unparalleled prowess in diverse applications. Merging the capabilities of LLMs with graph-structured data has been a topic of keen interest. This paper bifurcates such integrations into two predominant categories.
  arXiv  Detail & Related papers  (2023-10-09T07:59:34Z)
• Graph-ToolFormer: To Empower LLMs with Graph Reasoning Ability via Prompt Augmented by ChatGPT [10.879701971582502]
  We aim to develop a large language model (LLM) with the reasoning ability on complex graph data. Inspired by the latest ChatGPT and Toolformer models, we propose the Graph-ToolFormer framework to teach LLMs themselves with prompts augmented by ChatGPT to use external graph reasoning API tools.
  arXiv  Detail & Related papers  (2023-04-10T05:25:54Z)
• Sequential Manipulation Planning on Scene Graph [90.28117916077073]
  We devise a 3D scene graph representation, contact graph+ (cg+), for efficient sequential task planning. Goal configurations, naturally specified on contact graphs, can be produced by a genetic algorithm with an optimization method. A task plan is then succinct by computing the Graph Editing Distance (GED) between the initial contact graphs and the goal configurations, which generates graph edit operations corresponding to possible robot actions.
  arXiv  Detail & Related papers  (2022-07-10T02:01:33Z)
• Hallucinative Topological Memory for Zero-Shot Visual Planning [86.20780756832502]
  In visual planning (VP), an agent learns to plan goal-directed behavior from observations of a dynamical system obtained offline. Most previous works on VP approached the problem by planning in a learned latent space, resulting in low-quality visual plans. Here, we propose a simple VP method that plans directly in image space and displays competitive performance.
  arXiv  Detail & Related papers  (2020-02-27T18:54:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.