# Graph-enhanced Large Language Models in Asynchronous Plan Reasoning

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 34 of its 79 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 30 of 34)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [ChatGPT Outperforms Crowd-Workers for Text-Annotation Tasks](https://mlsanity.com/paper/2303.15056/) (2023)
- [Textbooks Are All You Need](https://mlsanity.com/paper/2306.11644/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Text2Motion: From Natural Language Instructions to Feasible Plans](https://mlsanity.com/paper/2303.12153/) (2023)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [WikiHow: A Large Scale Text Summarization Dataset](https://mlsanity.com/paper/1810.09305/) (2018)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [AnnoLLM: Making Large Language Models to Be Better Crowdsourced Annotators](https://mlsanity.com/paper/2303.16854/) (2023)
- [Is ChatGPT better than Human Annotators? Potential and Limitations of ChatGPT in Explaining Implicit Hate Speech](https://mlsanity.com/paper/2302.07736/) (2023)
- [Language Models of Code are Few-Shot Commonsense Learners](https://mlsanity.com/paper/2210.07128/) (2022)
- [Translating Natural Language to Planning Goals with Large-Language Models](https://mlsanity.com/paper/2302.05128/) (2023)
- [Dynamic Planning with a LLM](https://mlsanity.com/paper/2308.06391/) (2023)
- [Structured, flexible, and robust: benchmarking and improving large language models towards more human-like behavior in out-of-distribution reasoning tasks](https://mlsanity.com/paper/2205.05718/) (2022)
- [TRAM: Benchmarking Temporal Reasoning for Large Language Models](https://mlsanity.com/paper/2310.00835/) (2023)
- [Skills-in-Context Prompting: Unlocking Compositionality in Large Language Models](https://mlsanity.com/paper/2308.00304/) (2023)
- ["I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and Constraint Programming](https://mlsanity.com/paper/2312.06908/) (2023)
- [Code Simulation Challenges for Large Language Models](https://mlsanity.com/paper/2401.09074/) (2024)

## Built on by (most cited first, 30 of 37)

- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [The Landscape of Emerging AI Agent Architectures for Reasoning, Planning, and Tool Calling: A Survey](https://mlsanity.com/paper/2404.11584/) (2024)
- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [RAG vs. GraphRAG: A Systematic Evaluation and Key Insights](https://mlsanity.com/paper/2502.11371/) (2025)
- [A Scalable Communication Protocol for Networks of Large Language Models](https://mlsanity.com/paper/2410.11905/) (2024)
- [Can Graph Learning Improve Planning in LLM-based Agents?](https://mlsanity.com/paper/2405.19119/) (2024)
- [CRAB: Cross-environment Agent Benchmark for Multimodal Language Model Agents](https://mlsanity.com/paper/2407.01511/) (2024)
- [Robotouille: An Asynchronous Planning Benchmark for LLM Agents](https://mlsanity.com/paper/2502.05227/) (2025)
- [Advancing Agentic Systems: Dynamic Task Decomposition, Tool Integration and Evaluation using Novel Metrics and Dataset](https://mlsanity.com/paper/2410.22457/) (2024)
- [Assessing Dialect Fairness and Robustness of Large Language Models in Reasoning Tasks](https://mlsanity.com/paper/2410.11005/) (2024)
- [Toward Efficient Agents: Memory, Tool learning, and Planning](https://mlsanity.com/paper/2601.14192/) (2026)
- [The Evolution of Tool Use in LLM Agents: From Single-Tool Call to Multi-Tool Orchestration](https://mlsanity.com/paper/2603.22862/) (2026)
- [Revisiting Compositional Generalization Capability of Large Language Models Considering Instruction Following Ability](https://mlsanity.com/paper/2506.15629/) (2025)
- [YOLO-MARL: You Only LLM Once for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.03997/) (2024)
- [TCP: a Benchmark for Temporal Constraint-Based Planning](https://mlsanity.com/paper/2505.19927/) (2025)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [Forecasting Credit Ratings: A Case Study where Traditional Methods Outperform Generative LLMs](https://mlsanity.com/paper/2407.17624/) (2024)
- [AsyncTool: Evaluating the Asynchronous Function Calling Capability under Multi-Task Scenarios](https://mlsanity.com/paper/2605.27995/) (2026)
- [When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Coding](https://mlsanity.com/paper/2606.00953/) (2026)
- [Language Models Are Implicitly Continuous](https://mlsanity.com/paper/2504.03933/) (2025)
- [Probing Large Language Models for Scalar Adjective Lexical Semantics and Scalar Diversity Pragmatics](https://mlsanity.com/paper/2404.03301/) (2024)
- [Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment](https://mlsanity.com/paper/2506.00845/) (2025)
- [ParaCook: On Time-Efficient Planning for Multi-Agent Systems](https://mlsanity.com/paper/2510.11608/) (2025)
- [Iterative Graph Alignment](https://mlsanity.com/paper/2408.16667/) (2024)
- [When Dimensionality Hurts: The Role of LLM Embedding Compression for Noisy Regression Tasks](https://mlsanity.com/paper/2502.02199/) (2025)
- [Out-of-Context Reasoning in Large Language Models](https://mlsanity.com/paper/2503.10408/) (2025)
- [KGLAMP: Knowledge Graph-guided Language model for Adaptive Multi-robot Planning and Replanning](https://mlsanity.com/paper/2602.04129/) (2026)
- [Efficient Graph Understanding with LLMs via Structured Context Injection](https://mlsanity.com/paper/2509.00740/) (2025)
- [Can Large Language Models Generalize Procedures Across Representations?](https://mlsanity.com/paper/2602.03542/) (2026)

## Abstract (arXiv)

Planning is a fundamental property of human intelligence. Reasoning about asynchronous plans is challenging since it requires sequential and parallel planning to optimize time costs. Can large language models (LLMs) succeed at this task? Here, we present the first large-scale study investigating this question. We find that a representative set of closed and open-source LLMs, including GPT-4 and LLaMA-2, 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. We show that although PLaG can boost model performance, LLMs still suffer from drastic degradation when task complexity increases, highlighting the limits of utilizing LLMs for simulating digital devices. We see our study as an exciting step towards using LLMs as efficient autonomous agents. Our code and data are available at https://github.com/fangru-lin/graph-llm-asynchow-plan.