# Plan-over-Graph: Towards Parallelable LLM Agent Schedule

arXiv: https://arxiv.org/abs/2502.14563 · HTML: https://mlsanity.com/paper/2502.14563/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 15 of its 52 references that are in the map.
- First posted on arXiv 20 Feb 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 15 of 15)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [CogAgent: A Visual Language Model for GUI Agents](https://mlsanity.com/paper/2312.08914/) (2023)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)
- [Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers](https://mlsanity.com/paper/2408.06195/) (2024)
- [AgentGym: Evolving Large Language Model-based Agents across Diverse Environments](https://mlsanity.com/paper/2406.04151/) (2024)
- [Igniting Language Intelligence: The Hitchhiker's Guide From Chain-of-Thought Reasoning to Language Agents](https://mlsanity.com/paper/2311.11797/) (2023)
- [DARG: Dynamic Evaluation of Large Language Models via Adaptive Reasoning Graph](https://mlsanity.com/paper/2406.17271/) (2024)

## Built on by (most cited first, 14 of 14)

- [Towards Scientific Intelligence: A Survey of LLM-based Scientific Agents](https://mlsanity.com/paper/2503.24047/) (2025)
- [Flash-Searcher: Fast and Effective Web Agents via DAG-Based Parallel Execution](https://mlsanity.com/paper/2509.25301/) (2025)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [Graph-Augmented Large Language Model Agents: Current Progress and Future Prospects](https://mlsanity.com/paper/2507.21407/) (2025)
- [GTool: Graph Enhanced Tool Planning with Large Language Model](https://mlsanity.com/paper/2508.12725/) (2025)
- [What Papers Don't Tell You: Recovering Tacit Knowledge for Automated Paper Reproduction](https://mlsanity.com/paper/2603.01801/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [RoboPARA: Dual-Arm Robot Planning with Parallel Allocation and Recomposition Across Tasks](https://mlsanity.com/paper/2506.06683/) (2025)
- [Atomic Task Graph: A Unified Framework for Agentic Planning and Execution](https://mlsanity.com/paper/2607.01942/) (2026)
- [HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agents](https://mlsanity.com/paper/2608.02650/) (2026)
- [A Two-Tier Perspective on Inference-Time Parallelism in Multi-Agent LLM Systems](https://mlsanity.com/paper/2608.05791/) (2026)
- [Robust Asynchronous Planning via Auto-Formalization](https://mlsanity.com/paper/2606.00981/) (2026)
- [Beyond Sequential Interaction: Benchmarking Parallel Execution and Coordination for GUI Agents](https://mlsanity.com/paper/2607.22689/) (2026)
- [Topology-Consistent Task Planning over Cellular Workflow Complexes for LLM-based Agents](https://mlsanity.com/paper/2610.07004/) (2026)

## Abstract (arXiv)

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.