PaperlayerView exact revision on arXiv

Source-linked AI summary

Plan-over-Graph: Towards Parallelable LLM Agent Schedule

Shiqi Zhang, Xinbei Ma, Zouying Cao, Zhuosheng Zhang, Hai Zhao

arXiv:2502.14563v1cs.AI

TL;DR

LLM agent planning has under-explored parallel schedules, while graph understanding becomes harder as graph complexity grows. Plan-over-graph extracts task dependencies into graphs, trains models to plan over them, and reports significant improvements with parallel execution and global efficiency. The authors note remaining issues in graph extraction by open-source models and in adapting plans dynamically through environmental interaction.

  • Problem

    Parallelism remains under-explored in agent planning, and graph understanding degrades as graph scale and complexity increase.

  • Method

    Plan-over-graph extracts textual tasks into directed acyclic graphs, generates synthetic graph data, and uses a two-stage training scheme for graph-based planning.

  • Results

    The method significantly improves planning across API-based and open-source LLMs while supporting parallel execution and global efficiency.

  • Takeaways & Limitations

    Normalizing complex tasks as graphs provides a framework for parallel agentic systems across diverse models and graph topologies.

  • Takeaways & Limitations

    Open-source models still show extraction flaws, and real-world plans may need dynamic refinement through environmental perception.

Abstract

from arXiv · show

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.

1 Introduction

Existing agent planning usually executes subtasks sequentially, leaving parallelism under-explored. Plan-over-graph extracts task dependencies into graphs, plans under global constraints, and uses synthetic graph data plus two-stage training to improve scalable parallel planning.

  • Motivation: Sequential agent pipelines execute subtasks one after another even when dependencies do not require blocking, leaving available parallelism underused.Prior graph-structured reasoning expands the reasoning structure but still takes subtask actions sequentially.
  • Core contribution: Plan-over-graph extracts task rules into a graph and plans parallel execution under global consumption constraints.The graph-based formulation represents complex tasks with parallel subtasks and supports optimization over criteria such as time.
  • Dataset: The authors construct a dataset of connected directed acyclic task graphs with source and target nodes, feasible solutions, and optimal solutions contextualized by natural-language scenarios.The dataset generation pipeline prompts an LLM to turn abstract graphs into realistic task descriptions.
  • Training: A two-stage training strategy teaches models to extract graphs from textual queries and plan over graphs as graph scale increases.The method uses abstract graph training and evaluates success rate, optimal accuracy, feasible accuracy, and efficiency.
  • Results: The approach improves planning across LLMs and maintains planning efficiency and robustness across diverse models and graph topologies.The contribution claims significant improvement across both API-based and trainable open-source LLMs.

2 Related Work

Prior work studies agent planning, graph-based reasoning, and asynchronous execution, but graph understanding degrades as graph complexity grows. This paper defines a more formal, scalable planning-over-graph framework and reports improvements from training models on these graphs.

  • Agent planning: Existing planning research develops action sequences, searches for feasible or optimal trajectories, and uses reflection when environmental feedback updates task knowledge.The cited work spans sequence planning, search strategies, and feedback-driven refinement.
  • Graph-based reasoning: Graph-of-Thought and related approaches transform reasoning or contextual information into graphs for subtask generation, aggregation, refinement, inference, or transparency.These approaches establish graph-based reasoning, but do not provide the paper’s formal scalable planning-task definition.
  • LLM graph reasoning: Graph reasoning and understanding decline as graph size and complexity increase, producing a documented “comprehension collapse” and performance decrease.These findings motivate addressing structural reasoning on complex graphs rather than relying only on explicit graph representations.
  • Positioning: The proposed planning-over-graph framework is task-independent, formally captures task dependencies and complexity, and improves performance when models are trained on its graphs.The framework differs from existing work by combining a formal scalable graph structure with graph-based training.

3 Preliminary: Problem Statement

The paper formulates planning as selecting a feasible task-graph subplan that achieves a goal while optimizing global criteria such as time or cost. It identifies graph understanding and scale as bottlenecks, with performance falling sharply on larger graphs.

  • 3.1 Formulation of Planning: Planning maps a high-level task description to executable subtasks, schedules them under dependencies, optimizes global criteria, and achieves the task goal.The formal input is a task description represented by a complex task G and global criteria Ω.
  • 3.1 Formulation of Planning: A task graph is a DAG whose vertices are subtasks and whose edges encode precedence, while a feasible plan is a subgraph satisfying those dependencies.The formulation represents the task as G = (T, E), with precedence relations such as t_i ≺ t_j.
  • 3.1 Formulation of Planning: The optimal plan minimizes the global function Ω while achieving the task, with evaluation covering optimal rate, success rate, and the values of the global criteria.The metrics distinguish plans that achieve the goal from plans that are optimal under the specified criteria.
  • 3.2 Challenges of Planning: Graph understanding remains a bottleneck because complex topologies are difficult even with explicit graph representations, while existing benchmarks cover relatively small graphs.The cited scale examples mostly involve graphs with roughly 2–10 steps or total complexity between 10 and 20.
  • 3.2 Challenges of Planning: The pilot study evaluates random graphs with 10, 30, and 50 nodes and finds sharply declining feasible and optimal-path accuracy as node count increases.The optimal rate for 50-node graphs is only 6%, supporting the conclusion that complex graph topology under constraints is the core bottleneck.

4 Methodology: Plan-over-Graph

Plan-over-graph converts textual tasks into structured graphs, then plans over their dependencies to support parallel execution under global criteria. The method combines controllable synthetic graph generation with two-stage training to improve graph-based planning.

  • Plan-over-Graph Paradigm: Plan-over-graph first builds a task graph from a textual query, then generates a plan over that graph for parallel execution.The framework separates graph extraction from graph-aware planning and combines both steps at inference.
  • Abstract Task Formulation: Independent subtasks can execute in parallel, while each subplan waits only for its dependencies; time consumption is the primary optimization criterion.The formulation also defines global cost as the sum of subtask costs and evaluates time and cost efficiency.
  • Data Simulation: The automated data pipeline generates connected DAGs, assigns dependency rules and time values, selects source and target nodes, and labels optimal solutions with dynamic programming.It uses both random and tree-based DAG structures, with tree-based graphs adding ancestral and cross edges to enrich dependencies.
  • Data Simulation: Generated graphs are converted into textual real-life task descriptions, then self-corrected against the original graph to improve consistency.Each query preserves the graph’s task structure while expressing it as an executable scenario.
  • Training Scheme: Training uses supervised fine-tuning followed by direct preference optimization, distinguishing optimal solutions from feasible alternatives with efficient LoRA adaptation.DPO treats second-best solutions as rejected outputs and optimal solutions as chosen outputs.

5 Experiment

Experiments evaluate synthetic task graphs and real-life textual queries across API-based and open-source LLMs, testing training effects, graph-scale robustness, and textual-query planning. Plan-over-graph and its training scheme improve planning performance, with the trained model achieving strong optimality and efficiency results.

  • Experimental Setup: The graph-generation setup controls input complexity through linear edge scaling and, for random graphs, uniform sampling across the available edge range.The reported metrics include success rate, optimal accuracy, feasible accuracy, and efficiency.
  • Training Results: Two-stage training produces the strongest graph-planning result, reaching a 71.6% optimal rate while maintaining an 83.6% success rate.Training only on optimal solutions improves Llama to 75.7% success and 61.4% optimal rates; mixing feasible solutions raises these to 86.1% and 67.5%.
  • Graph-Scale Results: As graph size increases, performance generally declines, but the trained model and Claude show less sensitive drops than other models, while trained Llama leads optimal rate across node counts.Larger graphs also increase Llama's cost ratio, reflecting a tendency to select more subtasks.
  • Graph-Scale Results: For 30-node graphs, increasing edge count makes optimal-solution discovery harder and raises average time ratios for Claude and trained Llama.Average cost ratios rise less because denser graphs provide more feasible solutions, allowing completion with fewer, though not necessarily optimal, subtasks.
  • Textual Query Results: The trained model achieves a 72.5% optimal rate and 83% success rate on real-life textual queries, outperforming Claude on optimality.With plan-over-graph, Claude's optimal rate reaches 41.5%, while Llama's success rate rises to 38% and both models reduce time ratios.

6 Analysis

The analysis shows that node count affects planning performance more strongly than edge count, while parallel execution can reduce time relative to sequential execution. Remaining errors chiefly involve invalid subtasks, although source-dependency errors are largely resolved after training.

  • Impact of Node and Edge Counts: Node count has a stronger effect on planning metrics than edge count, with node-count correlations generally between 0.8 and 1.0.For 10-node graphs, edge changes produce correlations below 0.5, whereas 30-node graphs show stronger edge sensitivity, especially for Claude.
  • Parallel Efficiency: Parallel execution reduces completion time relative to sequential execution, with the efficiency benefit becoming more significant as graph scale increases.The evaluated plans are compared using parallel-to-sequential time ratios; model plans can still incur high cost ratios from redundant subtasks.
  • Wrong Case Study: After training, unavailable-source errors are nearly resolved, but hallucinated invalid subtasks remain the main performance bottleneck.The two error categories are invalid subtasks and unavailable sources.
  • Wrong Case Study: Essential-rule extraction errors can reduce overall performance, although subsequent planning may still complete a task correctly when incorrect rules are not used.The trained model’s optimal rate exceeds Claude’s despite a slightly lower success rate, and only 15% of cases exactly matched the original graph.

7 Conclusion

Plan-over-graph extracts task dependencies into structured graphs and uses graph-aware reasoning to improve parallel planning. The framework combines synthetic DAG data with two-stage training and shows improvements while revealing graph-scale effects on performance and time savings.

  • Conclusion: Plan-over-graph enhances parallelism in LLM-based agentic planning by extracting task dependencies as structured graphs and optimizing graph-aware reasoning.The framework is intended to bridge abstract graph planning and real-world applications.
  • Conclusion: The approach develops a synthetic DAG dataset and a two-stage training scheme for parallel planning.
  • Conclusion: Graph structure inversely affects model performance, while parallelism provides greater time reduction as graph scale increases.

Limitations

The paper identifies extraction weaknesses in open-source models and limits its current planning formulation to static plans. Future work targets improved extraction and environment-interactive plan refinement.

  • Limitations: Open-source models still exhibit flaws in extracting task structure, although the authors consider graph planning ability more important than extraction.
  • Limitations: The current formulation does not model plans as dynamic processes that interact with the environment and refine earlier decisions through perception.
  • Limitations: Future work will focus on improving extraction and enabling environment-interactive plan refinement.

B Textual Query Statistics

The synthetic query statistics summarize both token-length distribution and topic composition. Figure 4 presents these statistics using separate bar-chart and pie-chart views.

  • Query Statistics: Figure 4 summarizes the token distribution of the synthetic queries with a bar chart.
  • Query Statistics: Figure 4 summarizes the topic distribution of the synthetic queries with a pie chart.
  • Query Statistics: The synthetic-query statistics cover both token characteristics and topic composition.

C Trainning Setups

The training setup specifies the data formats for supervised and preference optimization objectives, while supplementary materials document implementation settings and evaluation context.

  • C Trainning Setups: Training is performed with the LLaMa Factory framework, and detailed hyperparameters are provided in Table 6.The supplied passages identify the framework and table but do not report individual hyperparameter values.
  • C Trainning Setups: SFT data pairs each graph G with an optimal plan, while mixup additionally includes a second plan; DPO uses optimal and second plans to form preferred and rejected outputs.The DPO input is (G, p_opt, p_second), with p_opt chosen and p_second rejected.
  • C Trainning Setups: The SFT and DPO training objectives are each defined by separate loss functions in the training setup.The passages introduce the SFT loss and identify the DPO loss as equation (12), without supplying their formulas.
  • C Trainning Setups: Figure 5 compares Claude and the trained Llama across edge-count intervals using counts of fail, feasible, and optimal states.The vertical axis represents the number of cases in each state, while the horizontal axis represents segmented edge counts.
  • C Trainning Setups: A real-life scenario is illustrated through a query and its corresponding plan.

F Supplementary of the Experiments

The supplementary experiments normalize several metrics, quantify their relationships with graph size using correlations and regression slopes, and define a parallel-to-sequential time ratio.

  • F Supplementary of the Experiments: The experiments report correlation coefficients and slopes for normalized metrics as node and edge counts change.Tables 7 and 8 summarize these relationships for node counts and edge variations with node counts.
  • F Supplementary of the Experiments: Metrics are min-max normalized to the [0,1] range before analysis.The raw quantities include node and edge counts, success and optimal counts, and average time and cost ratios.
  • F Supplementary of the Experiments: Pearson correlation coefficients quantify relationships between node or edge counts X and metrics Y.
  • F Supplementary of the Experiments: The slope m of each best-fit relationship is computed using linear regression.The supplied equation passage is incomplete, but it identifies the regression-based slope calculation.
  • F Supplementary of the Experiments: All reported results are rounded to two decimal places.
  • F Supplementary of the Experiments: The parallel-to-sequential time ratio is defined for a plan P composed of subplans p.The supplied passage introduces the calculation but does not provide its displayed formula.
Loading 2502.14563v1…