mlsanityData to 7 Oct 2026

Graph-enhanced Large Language Models in Asynchronous Plan Reasoning

arXiv 2402.02805 ↗First posted 5 Feb 2024cs.AI cs.CL cs.LGcited by 37

On the map: LLM reasoning → Reasoning for agents, planning and code

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.

Key facts. Cited by 37 papers in the map (data through 7 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.

Builds on

34 of 79 references.

References · 34

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  3. 2023Lost in the Middle: How Language Models Use Long Contextscited by 3,383
  4. 2023Mistral 7Bcited by 3,065
  5. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,579
  6. 2022Do As I Can, Not As I Say: Grounding Language in Robotic Affordancescited by 2,302
  7. 2023Code Llama: Open Foundation Models for Codecited by 2,105
  8. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  9. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 873
  10. 2023ChatGPT Outperforms Crowd-Workers for Text-Annotation Taskscited by 849
  11. 2023Textbooks Are All You Needcited by 561
  12. 2023LLM+P: Empowering Large Language Models with Optimal Planning Proficiencycited by 496
22 more
  1. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  2. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  3. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 249
  4. 2023Text2Motion: From Natural Language Instructions to Feasible Planscited by 223
  5. 2023Language is All a Graph Needscited by 219
  6. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 209
  7. 2018WikiHow: A Large Scale Text Summarization Datasetcited by 203
  8. 2023Talk like a Graph: Encoding Graphs for Large Language Modelscited by 175
  9. 2023AnnoLLM: Making Large Language Models to Be Better Crowdsourced Annotatorscited by 171
  10. 2023Is ChatGPT better than Human Annotators? Potential and Limitations of ChatGPT in Explaining Implicit Hate Speechcited by 165
  11. 2022Language Models of Code are Few-Shot Commonsense Learnerscited by 160
  12. 2023Translating Natural Language to Planning Goals with Large-Language Modelscited by 132
  13. 2023Dynamic Planning with a LLMcited by 60
  14. 2022Structured, flexible, and robust: benchmarking and improving large language models towards more human-like behavior in out-of-distribution reasoning taskscited by 56
  15. 2023TRAM: Benchmarking Temporal Reasoning for Large Language Modelscited by 39
  16. 2023Skills-in-Context Prompting: Unlocking Compositionality in Large Language Modelscited by 33
  17. 2023"I Want It That Way": Enabling Interactive Decision Support Using Large Language Models and Constraint Programmingcited by 19
  18. 2024Code Simulation Challenges for Large Language Modelscited by 15
  19. 2021Two Contrasting Data Annotation Paradigms for Subjective NLP Taskscited by 12
  20. 2023Graph Elicitation for Guiding Multi-Step Reasoning in Large Language Modelscited by 10
  21. 2024Consolidating Trees of Robotic Plans Generated Using Large Language Models to Improve Reliabilitycited by 6
  22. 2023Do prompt positions really matter?cited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 11; 2025: 14; 2026: 12.

37 papers.

Sort:

By area:

  1. 2024Retrieval-Augmented Generation with Graphs (GraphRAG)cited by 170
  2. 2024The Landscape of Emerging AI Agent Architectures for Reasoning, Planning, and Tool Calling: A Surveycited by 164
  3. 2025Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systemscited by 125
  4. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 82
  5. 2025RAG vs. GraphRAG: A Systematic Evaluation and Key Insightscited by 51
  6. 2024A Scalable Communication Protocol for Networks of Large Language Modelscited by 43
  7. 2024Can Graph Learning Improve Planning in LLM-based Agents?cited by 42
  8. 2024CRAB: Cross-environment Agent Benchmark for Multimodal Language Model Agentscited by 38
  9. 2025Robotouille: An Asynchronous Planning Benchmark for LLM Agentscited by 31
  10. 2024Advancing Agentic Systems: Dynamic Task Decomposition, Tool Integration and Evaluation using Novel Metrics and Datasetcited by 24
  11. 2024Assessing Dialect Fairness and Robustness of Large Language Models in Reasoning Taskscited by 20
  12. 2026Toward Efficient Agents: Memory, Tool learning, and Planningcited by 11
25 more
  1. 2026The Evolution of Tool Use in LLM Agents: From Single-Tool Call to Multi-Tool Orchestrationcited by 11
  2. 2025Revisiting Compositional Generalization Capability of Large Language Models Considering Instruction Following Abilitycited by 10
  3. 2024YOLO-MARL: You Only LLM Once for Multi-Agent Reinforcement Learningcited by 9
  4. 2025TCP: a Benchmark for Temporal Constraint-Based Planningcited by 8
  5. 2024Forecasting Credit Ratings: A Case Study where Traditional Methods Outperform Generative LLMscited by 5
  6. 2025Language Models Are Implicitly Continuouscited by 4
  7. 2025Large Language Models in Operations Research: Methods, Applications, and Challengescited by 4
  8. 2026When Parallelism Pays Off: Cohesion-Aware Task Partitioning for Multi-Agent Codingcited by 4
  9. 2024Probing Large Language Models for Scalar Adjective Lexical Semantics and Scalar Diversity Pragmaticscited by 3
  10. 2025Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignmentcited by 3
  11. 2026AsyncTool: Evaluating the Asynchronous Function Calling Capability under Multi-Task Scenarioscited by 3
  12. 2024Iterative Graph Alignmentcited by 2
  13. 2025When Dimensionality Hurts: The Role of LLM Embedding Compression for Noisy Regression Taskscited by 2
  14. 2025Out-of-Context Reasoning in Large Language Modelscited by 2
  15. 2025ParaCook: On Time-Efficient Planning for Multi-Agent Systemscited by 2
  16. 2026KGLAMP: Knowledge Graph-guided Language model for Adaptive Multi-robot Planning and Replanningcited by 2
  17. 2025Efficient Graph Understanding with LLMs via Structured Context Injectioncited by 1
  18. 2026Can Large Language Models Generalize Procedures Across Representations?cited by 1
  19. 2025Do LLMs Dream of Discrete Algorithms?cited by 0
  20. 2026GRAFT: Graph-Tokenized LLMs for Tool Planningcited by 0
  21. 2026Robust Asynchronous Planning via Auto-Formalizationcited by 0
  22. 2026Searching for Synergy in Shared Workspace Human-AI Collaborationcited by 0
  23. 2026Beyond Sequential Interaction: Benchmarking Parallel Execution and Coordination for GUI Agentscited by 0
  24. 2026The Dialect Tax: Dialectal Biases Persist throughout the Language Modeling Pipelinecited by 0
  25. 2026SkillGym: Training Skill-Use Agents with Automatic Verifiable Environment Generationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Plan-over-Graph: Towards Parallelable LLM Agent Schedule
  2. 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change
  3. 2025LLMs Can Plan Only If We Tell Them
  4. 2023On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)
  5. 2024Asynchronous Large Language Model Enhanced Planner for Autonomous Driving
  6. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks
  7. 2026SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models
  8. 2025Can LLM-Reasoning Models Replace Classical Planning? A Benchmark Study