Elamur Research⌕
☰
home / papers / 2026 / ParaCook: On Time-Efficient Planning for Multi-Agent Systems

ParaCook: On Time-Efficient Planning for Multi-Agent Systems

Paper · 2026 · Shiqi Zhang, Xinbei Ma, Yunqing Xu et al.

Summary

Most LLM agent benchmarks check whether a task gets done, not how quickly. They ignore idle time, blocking and contention for shared resources when work runs in parallel or asynchronously. ParaCook fills this gap with a benchmark for time-efficient planning in multi-agent systems. It is inspired by Overcooked and set in a 2D grid-world kitchen. Tasks are modeled as subtask DAGs with durations and waiting delays, so good plans need two kinds of parallelism: one agent overlapping its own work (e.g., chopping while something boils) and several agents working at once. The action space is kept small (MoveTo, Interact, Process, Wait, Finish), and complexity can be tuned via the number of agents and orders. The authors also add abstract scheduling tasks that remove low-level execution. On embodied tasks, frontier LLMs such as GPT-5 lag well behind humans in both success and completion time. On abstract tasks, the same models come close to optimal. This suggests the gap lies in grounding schedules in execution rather than in high-level reasoning.

Key points

  • Embodied results: GPT-5 performed best, with about 65% average success rate under plain IO prompting and about 73% with CoT. Humans succeeded on every task. Models also needed more time and more movements than humans.
  • Other models: Gemini-2.5-Pro, DeepSeek-V3.2-Exp, Claude-Opus-4.1 and Qwen3-Max-Preview were also tested, under IO and CoT prompting. Success dropped sharply on hard tasks. CoT gains depended on the model, and graph-augmented and interactive prompting showed no consistent winner either.
  • Abstract tasks: Plans were compared with optimal schedules from a constraint programming solver (cp_sat). GPT-5, Gemini-2.5-Pro and Claude-Opus-4.1 reached 100% success, with nOCT of 1.0241, 1.0220 and 1.0902 respectively. Qwen3-Max-Preview reached 78% success with nOCT 1.1315.
  • Implication: The authors argue for hierarchical frameworks that separate scheduling from action execution.
  • Availability: Code and data are at github.com/zsq259/ParaCook. The study covers only centralized IO/CoT planning and proposes no new solving method.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of California, MercedMerced · United States12 works · 425 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 works

Cite

Cite as Shiqi Zhang, Xinbei Ma, Yunqing Xu, Zouying Cao, Pengrui Lu, Haobo Yuan, Tiancheng Shen, Zhuosheng Zhang, Hai Zhao and Ming-Hsuan Yang. 2026. ParaCook: On Time-Efficient Planning for Multi-Agent Systems. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1378

@inproceedings{zhang2026paracook,
  title = {{ParaCook: On Time-Efficient Planning for Multi-Agent Systems}},
  author = {Shiqi Zhang, Xinbei Ma, Yunqing Xu, Zouying Cao, Pengrui Lu, Haobo Yuan, Tiancheng Shen, Zhuosheng Zhang, Hai Zhao and Ming-Hsuan Yang},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1378},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1378}
}

References

29 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Muzhen Cai, Xiubo Chen, Yining An, Jiaxin Zhang, Xuesong Wang, Wang Xu, Weinan Zhang, and Ting Liu. 2025. Cookbench: A long-horizon embodied planning benchmark for complex cooking scenarios. arXiv preprint arXiv:2508.03232. — [arXiv:2508.03232](https://arxiv.org/abs/2508.03232) find
  2. Zouying Cao, Runze Wang, Yifei Yang, Xinbei Ma, Xiaoyong Zhu, Bo Zheng, and Hai Zhao. 2025. PGPO: Enhancing agent reasoning via pseudocode-style planning guided preference optimization. In Findings of the Association for Computational Linguistics: ACL 2025, pages 14966–14985, Vienna, Austria. Associ… find
  3. Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. 2019. On the utility of learning about humans for human-ai coordination. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc. find
  4. Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. 2023. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research. find
  5. Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, Luke Marris, Sam Petulla, Colin Gaffney, Asaf Aharoni, Nathan Lintz, Tiago Cardal Pais, Henrik Jacobsson, Idan Szpektor, Nan-Jiang Jiang, and 3290 other…
  6. DeepSeek-AI. 2025. Deepseek-v3.2-exp: Boosting long-context efficiency with deepseek sparse attention. find
  7. Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Pal: Program-aided language models. In International Conference on Machine Learning, pages 10764–10799. PMLR. find
  8. Gonzalo Gonzalez-Pumariega, Leong Su Yean, Neha Sunkara, and Sanjiban Choudhury. 2025. Robotouille: An asynchronous planning benchmark for LLM agents. In The Thirteenth International Conference on Learning Representations. find
  9. Sirui Hong, Mingchen Zhuge, Jonathan Chen, Xiawu Zheng, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, Lingfeng Xiao, Chenglin Wu, and Jürgen Schmidhuber. 2024. MetaGPT: Meta programming for a multi-agent collaborative framework. In The T…
  10. Ao Li, Yuexiang Xie, Songze Li, Fugee Tsung, Bolin Ding, and Yaliang Li. 2025. Agent-oriented planning in multi-agent systems. In The Thirteenth International Conference on Learning Representations. find
  11. Fangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang, Anthony G Cohn, and Janet B Pierrehumbert. 2024a. Graph-enhanced large language models in asynchronous plan reasoning. In Forty-first International Conference on Machine Learning. find
  12. Fangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang, Anthony Cohn, and Janet B. Pierrehumbert. 2024b. Graph-enhanced large language models in asynchronous plan reasoning. Preprint, arXiv:2402.02805. — [arXiv:2402.02805](https://arxiv.org/abs/2402.02805) find
  13. Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. 2023. Llm+ p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv:2304.11477.
  14. Jiayi Pan, Xiuyu Li, Long Lian, Charlie Snell, Yifei Zhou, Adam Yala, Trevor Darrell, Kurt Keutzer, and Alane Suhr. 2025. Learning adaptive parallel reasoning with language models. arXiv preprint arXiv: 2504.15466. find
  15. Shuofei Qiao, Runnan Fang, Zhisong Qiu, Xiaobin Wang, Ningyu Zhang, Yong Jiang, Pengjun Xie, Fei Huang, and Huajun Chen. 2024. Benchmarking agentic workflow generation. arXiv preprint arXiv:2410.07869. — [arXiv:2410.07869](https://arxiv.org/abs/2410.07869) find
  16. Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. 2023. Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface. In Advances in Neural Information Processing Systems. find
  17. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36:8634–8652.
  18. Haochen Sun, Shuwen Zhang, Lujie Niu, Lei Ren, Hao Xu, Hao Fu, Fangkun Zhao, Caixia Yuan, and Xiaojie Wang. 2025. Collab-overcooked: Benchmarking and evaluating large language models as collaborative agents. Preprint, arXiv:2502.20073. find
  19. Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. 2023. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. arXiv preprint arXiv:2305.04091. find
  20. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  21. Shaokun Zhang, Jieyu Zhang, Dujian Ding, Jiale Liu, Mirian Del Carmen Hipolito Garcia, Ankur Mallick, Daniel Madrigal, Menglin Xia, Victor Rühle, Qingyun Wu, and Chi Wang. 2025a. Ecoact: Economic agent determines when to register what action. In Workshop on Reasoning and Planning for Large Language… find
  22. Shiqi Zhang, Xinbei Ma, Zouying Cao, Zhuosheng Zhang, and Hai Zhao. 2025b. Plan-over-graph: Towards parallelable llm agent schedule. arXiv preprint arXiv:2502.14563. — [arXiv:2502.14563](https://arxiv.org/abs/2502.14563) find
  23. Wentao Zhang, Liang Zeng, Yuzhen Xiao, Yongcong Li, Ce Cui, Yilei Zhao, Rui Hu, Yang Liu, Yahui Zhou, and Bo An. 2025c. Agentorchestra: A hierarchical multi-agent framework for general-purpose task solving. arXiv preprint arXiv:2506.12508. — [arXiv:2506.12508](https://arxiv.org/abs/2506.12508) find
  24. Yikai Zhang, Siyu Yuan, Caiyu Hu, Kyle Richardson, Yanghua Xiao, and Jiangjie Chen. 2024b. TimeArena: Shaping efficient multitasking language agents in a time-aware simulation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3… find
  25. Dongsheng Zhu, Weixian Shi, Zhengliang Shi, Zhaochun Ren, Shuaiqiang Wang, Lingyong Yan, and Dawei Yin. 2025. Divide-then-aggregate: An efficient tool learning method via parallel tool invocation. arXiv preprint arXiv:2501.12432. find
  26. Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Beibin Li, Erkang Zhu, Li Jiang, Xiaoyun Zhang, Shaokun Zhang, Jiale Liu, Ahmed Hassan Awadallah, Ryen W White, Doug Burger, and Chi Wang. 2023. Autogen: Enabling next-gen llm applications via multi-agent conversation. Preprint, arXiv:2308.08155.
  27. Dongjie Yang, Chengqiang Lu, Qimeng Wang, Xinbei Ma, Yan Gao, Yao Hu, and Hai Zhao. 2025. Plan your travel and travel with your plan: Wide-horizon planning and evaluation via llm. arXiv preprint arXiv:2506.12421. — [arXiv:2506.12421](https://arxiv.org/abs/2506.12421) find
  28. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2023. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR).
  29. Bin Zhang, Hangyu Mao, Lijuan Li, Zhiwei Xu, Dapeng Li, Rui Zhao, and Guoliang Fan. 2024a. Sequential asynchronous action coordination in multi-agent systems: A stackelberg decision transformer approach. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedin… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-paracook-time-efficient-planning-multi/