ACL Findings2026
ParaCook: On Time-Efficient Planning for Multi-Agent Systems
Shiqi Zhang, Xinbei Ma, Yunqing Xu, Zouying Cao, Pengrui Lu, Haobo Yuan, Tiancheng Shen, Zhuosheng Zhang, Hai Zhao, Ming-Hsuan Yang
Abstract
Large Language Models (LLMs) exhibit strong reasoning abilities for planning long-horizon, real-world tasks, yet existing agent benchmarks focus on task completion while neglecting time efficiency in parallel and asynchronous operations. To address this, we present ParaCook, a benchmark for time-efficient collaborative planning. Inspired by the Overcooked game, Para-Cook provides an environment for various challenging interaction planning of multi-agent systems that are instantiated as cooking tasks, with a simplified action space to isolate the core challenge of strategic parallel planning. Through a comprehensive evaluation of state-of-the-art LLMs, we find that current approaches achieve suboptimal plans, which struggle with parallel actions or coordination. Our analysis also reveals LLMs' potential on abstract tasks where they can focus on high-level parallel optimization. ParaCook provides a scalable evaluation framework with adjustable complexity, establishing a foundation for developing and assessing time efficiency-aware multi-agent planning. The code and data are available at https://github.com/zsq259/ParaCook.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning cites Reflexion: language agents with verbal reinforcement learning
- Reflexion: language agents with verbal reinforcement learning cites HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face
- HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face cites PAL: Program-aided Language Models
Builds on14
- Reflexion: language agents with verbal reinforcement learningNoah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan et al.NeurIPS 2023 · 5,828 citations
- HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging FaceYongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li et al.NeurIPS 2023 · 1,778 citations
- PAL: Program-aided Language ModelsLuyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon et al.ICML 2023 · 700 citations
- Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language ModelsLei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu et al.ACL 2023 · 249 citations
- Graph-enhanced Large Language Models in Asynchronous Plan ReasoningFangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang et al.ICML 2024 · 33 citations
Related papers
- Collab-Overcooked: Benchmarking and Evaluating Large Language Models as Collaborative AgentsHaochen Sun, Shuwen Zhang, Lujie Niu, Lei Ren et al.EMNLP 2025
- Recipe2Plan: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between ActionsZirui Wu, Xiao Liu, Jiayi Li, Lingpeng Kong et al.EMNLP Findings 2025
- Robotouille: An Asynchronous Planning Benchmark for LLM AgentsGonzalo Gonzalez-Pumariega, Leong Su Yean, Neha Sunkara, Sanjiban ChoudhuryICLR 2025
- TimeArena: Shaping Efficient Multitasking Language Agents in a Time-Aware SimulationYikai Zhang, Siyu Yuan, Caiyu Hu, Kyle Richardson et al.ACL 2024
- ProAgent: Building Proactive Cooperative Agents with Large Language ModelsCeyao Zhang, Kaijie Yang, Siyi Hu, Zihao Wang et al.AAAI 2024 · 141 citations
