Research map / Large language models / Agents, code and math
Graph-enhanced Large Language Models in Asynchronous Plan Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the AsyncHow benchmark for asynchronous plan reasoning and PLaG, a graph-enhanced prompting method, showing LLMs including GPT-4 perform poorly and degrade with task complexity even with PLaG.
Problem
Whether LLMs can compute the optimal (shortest) time for asynchronous plans that mix sequential and parallel actions under ordering constraints, which requires time summation, time comparison, and constrained reasoning.
Approach
Plan Like a Graph (PLaG) adds graph representations (explicit adjacency-list-style graphs or graphs the model generates itself, BaG) to natural-language prompts, reframing the naturalistic planning question as a longest-path DAG problem; the benchmark is auto-generated from WikiHow and ProScript with deterministic gold answers via longest path.
Key results
- GPT-4 with PLaG (BaG) reaches 0.777 accuracy on AsyncHow versus 0.657 for the best no-graph setting (k-shot + CoT).
- PLaG improves all five tested models, e.g. GPT-3.5 rises from 0.248 (k-shot) to 0.355 with BaG.
- Accuracy drops sharply as task complexity |V|+|E| increases, and GPT-4 zero-shot is only 0.130 without illustrations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add PLaG with explicit graph instead of the strongest non-PLaG prompt | GPT-4 · AsyncHow | accuracy: 0.657 -> 0.730 | Helped |
| Add PLaG with BaG instead of the strongest non-PLaG prompt | GPT-4 · AsyncHow | accuracy: 0.657 -> 0.777 | Helped |
| Add PLaG with explicit graph instead of the strongest non-PLaG prompt | GPT-3.5 · AsyncHow | accuracy: 0.248 -> 0.290 | Helped |
| Add PLaG with BaG instead of the strongest non-PLaG prompt | GPT-3.5 · AsyncHow | accuracy: 0.248 -> 0.355 | Helped |
| Add PLaG with explicit graph instead of the strongest non-PLaG prompt | Command · AsyncHow | accuracy: 0.078 -> 0.100 | Helped |
| Use PLaG with BaG instead of the strongest non-PLaG prompt | Command · AsyncHow | accuracy: 0.078 -> 0.050 | Hurt |
| Add PLaG with explicit graph instead of the strongest non-PLaG prompt | LLaMA-2-70B-chat · AsyncHow | accuracy: 0.076 -> 0.101 | Helped |
| Use PLaG with BaG instead of the strongest non-PLaG prompt | LLaMA-2-70B-chat · AsyncHow | accuracy: 0.076 -> 0.069 | Hurt |
| Add PLaG with explicit graph instead of the strongest non-PLaG prompt | Mistral-7B-Instruct · AsyncHow | accuracy: 0.149 -> 0.161 | Helped |
| Use PLaG with BaG instead of the strongest non-PLaG prompt | Mistral-7B-Instruct · AsyncHow | accuracy: 0.149 -> 0.146 | No clear effect |
| Increase planning-task complexity | GPT-3.5 and GPT-4 · AsyncHow | accuracy | Hurt |
| Use more succinct and natural expressions for constraints | LLMs · AsyncHow | accuracy | Hurt |
Surprising findings
- GPT-3.5 outperforms GPT-4 in zero-shot, zero-shot+CoT and k-shot settings, with GPT-4 only dominating once k-shot+CoT illustrations are given.
- Self-generated graphs (BaG) outperform algorithmically generated explicit graphs for GPT models, attributed to graph position in the prompt.
Limitations
- Assumes infinite resources and only time cost as the optimization objective.
- Benchmark annotations rely partly on GPT-3.5/GPT-4 as annotators, and time durations lack unique gold answers.
- Open-source model results are low and some closed models were not fully explored (e.g., Command).
Experimental setup
Datasets: WikiHow ProScript
Benchmarks: AsyncHow
Metrics: accuracy McNemar's test with Holm-Bonferroni correction precision recall F1
Baselines: zero-shot zero-shot + CoT k-shot k-shot + CoT GPT-3.5 Cohere Command LLaMA-2-70B-chat Mistral-7B-Instruct
Builds on: chain-of-thought prompting few-shot prompting ProScript WikiHow
Closest papers by meaning
- LLMs Can Plan Only If We Tell Them (ICLR 2025 · similarity 0.91)
- On the self-verification limitations of large language models on reasoning and planning tasks (ICLR 2025 · similarity 0.90)
- Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs (NeurIPS 2024 · similarity 0.90)
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification (ICML 2025 · similarity 0.89)
- Embodied Task Planning via Graph-Informed Action Generation with Large Language Models (ICML 2026 · similarity 0.89)
- Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.