# Graph-enhanced Large Language Models in Asynchronous Plan Reasoning

**Authors:** Fangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang, Anthony Cohn, Janet B. Pierrehumbert  
**arXiv:** [2402.02805](https://arxiv.org/abs/2402.02805)  
**Date:** 2024-02-05  
**Summary page:** https://www.summarizepaper.com/en/paper/2402.02805v1/

## Key points

- Comprehensive study on large language models (LLMs) and asynchronous plans
- Introduction of benchmark AsyncHow for evaluating LLMs like GPT-4 and LLaMA-2
- Poor performance of models without detailed task-solving process illustrations
- Proposal of Plan Like a Graph (PLaG) technique to improve model performance
- Struggles of LLMs with increased task complexity despite PLaG advancements
- Limitations of current LLMs in handling complex asynchronous planning tasks effectively
- Societal impact on downstream tasks like job scheduling discussed
- Ethical considerations regarding data generation from sources like WikiHow addressed
- Funding support from various organizations acknowledged
- Significance of the study in understanding capabilities and limitations of LLMs in autonomous agent scenarios

## Summary

In this paper, the authors conduct a comprehensive study on the ability of large language models (LLMs) to reason about asynchronous plans. These plans involve both sequential and parallel planning to optimize time costs. The study introduces a benchmark called AsyncHow and evaluates various LLMs, including GPT-4 and LLaMA-2, on this task. The results show that these models perform poorly without detailed illustrations of the task-solving process. To address this issue, the authors propose a novel technique called Plan Like a Graph (PLaG), which combines graphs with natural language prompts and significantly improves model performance across different levels of task complexity. Despite the advancements made by PLaG, the study reveals that LLMs still struggle when faced with increased task complexity. This raises concerns about their suitability for simulating digital devices or acting as intelligent agents. The paper emphasizes the limitations of current state-of-the-art LLMs in handling complex asynchronous planning tasks effectively. Furthermore, the authors discuss the potential societal impact of their work, highlighting how it can influence downstream tasks such as job scheduling and other applications of similar technologies. They also address ethical considerations related to data generation from sources like WikiHow, ensuring that content is safe and appropriate for use in research. The study acknowledges funding support from various organizations and expresses gratitude for feedback received during the research process. Overall, this work represents a significant step towards understanding the capabilities and limitations of LLMs in asynchronous plan reasoning and sheds light on future directions for utilizing these models effectively in autonomous agent scenarios.