# Robotouille: An Asynchronous Planning Benchmark for LLM Agents

arXiv: https://arxiv.org/abs/2502.05227 · HTML: https://mlsanity.com/paper/2502.05227/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 43 of its 45 references that are in the map.
- First posted on arXiv 6 Feb 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 43)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents](https://mlsanity.com/paper/2207.01206/) (2022)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language](https://mlsanity.com/paper/2204.00598/) (2022)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models](https://mlsanity.com/paper/2212.04088/) (2022)
- [Ring Attention with Blockwise Transformers for Near-Infinite Context](https://mlsanity.com/paper/2310.01889/) (2023)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [MLAgentBench: Evaluating Language Agents on Machine Learning Experimentation](https://mlsanity.com/paper/2310.03302/) (2023)
- [On the Utility of Learning about Humans for Human-AI Coordination](https://mlsanity.com/paper/1910.05789/) (2019)
- [AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agents](https://mlsanity.com/paper/2401.13178/) (2024)
- [Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration](https://mlsanity.com/paper/1802.08802/) (2018)
- [FireAct: Toward Language Agent Fine-tuning](https://mlsanity.com/paper/2310.05915/) (2023)
- [Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents](https://mlsanity.com/paper/2408.07199/) (2024)
- [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023)

## Built on by (most cited first, 30 of 32)

- [From LLM Reasoning to Autonomous AI Agents: A Comprehensive Review](https://mlsanity.com/paper/2504.19678/) (2025)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directions](https://mlsanity.com/paper/2509.18970/) (2025)
- [The Long-Horizon Task Mirage? Diagnosing Where and Why Agentic Systems Break](https://mlsanity.com/paper/2604.11978/) (2026)
- [Symbiotic Cooperation for Web Agents: Harnessing Complementary Strengths of Large and Small LLMs](https://mlsanity.com/paper/2502.07942/) (2025)
- [COMPASS: Enhancing Agent Long-Horizon Reasoning with Evolving Context](https://mlsanity.com/paper/2510.08790/) (2025)
- [A Survey on Large Language Models for Automated Planning](https://mlsanity.com/paper/2502.12435/) (2025)
- [Agentic Artificial Intelligence (AI): Architectures, Taxonomies, and Evaluation of Large Language Model Agents](https://mlsanity.com/paper/2601.12560/) (2026)
- [PLANET: A Collection of Benchmarks for Evaluating LLMs' Planning Capabilities](https://mlsanity.com/paper/2504.14773/) (2025)
- [PM-Bench: Evaluating Prospective Memory in LLM Agents](https://mlsanity.com/paper/2607.12385/) (2026)
- [TextAtari: 100K Frames Game Playing with Language Agents](https://mlsanity.com/paper/2506.04098/) (2025)
- [HeroBench: A Benchmark for Long-Horizon Planning and Structured Reasoning in Virtual Worlds](https://mlsanity.com/paper/2508.12782/) (2025)
- [Multi-level Value Alignment in Agentic AI Systems: Survey and Perspectives](https://mlsanity.com/paper/2506.09656/) (2025)
- [AsyncTool: Evaluating the Asynchronous Function Calling Capability under Multi-Task Scenarios](https://mlsanity.com/paper/2605.27995/) (2026)
- [Reflex First, Reflect Later: Latency-Aware Embodied LLM Agents for Dynamic Response](https://mlsanity.com/paper/2506.07223/) (2025)
- [Skill-Aligned Fairness in Multi-Agent Learning for Collaboration in Healthcare](https://mlsanity.com/paper/2508.18708/) (2025)
- [ATTS: Asynchronous Test-Time Scaling via Conformal Prediction](https://mlsanity.com/paper/2509.15148/) (2025)
- [ParaCook: On Time-Efficient Planning for Multi-Agent Systems](https://mlsanity.com/paper/2510.11608/) (2025)
- [Embodied Task Planning via Graph-Informed Action Generation with Large Language Models](https://mlsanity.com/paper/2601.21841/) (2026)
- [TabAgent: A Framework for Replacing Agentic Generative Components with Tabular-Textual Classifiers](https://mlsanity.com/paper/2602.16429/) (2026)
- [Engagement Process: Rethinking the Temporal Interface of Action and Observation](https://mlsanity.com/paper/2605.11484/) (2026)
- [The Hunger Game Debate: On the Emergence of Over-Competition in Multi-Agent Systems](https://mlsanity.com/paper/2509.26126/) (2025)
- [PACE: Adaptive Budget Allocation for Time-Efficient Embodied Planning](https://mlsanity.com/paper/2608.03034/) (2026)
- [AdaFair-MARL: Enforcing Adaptive Fairness Constraints in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2511.14135/) (2025)
- [Latent Action Reparameterization for Efficient Agent Inference](https://mlsanity.com/paper/2605.18597/) (2026)
- [Robust Asynchronous Planning via Auto-Formalization](https://mlsanity.com/paper/2606.00981/) (2026)
- [Searching for Synergy in Shared Workspace Human-AI Collaboration](https://mlsanity.com/paper/2606.18413/) (2026)
- [Beyond Sequential Interaction: Benchmarking Parallel Execution and Coordination for GUI Agents](https://mlsanity.com/paper/2607.22689/) (2026)
- [HaReCAP: Habitual-action Grounding for Recursive Large Language Model Agents](https://mlsanity.com/paper/2608.16447/) (2026)
- [LLMs are General Asynchronous Agents](https://mlsanity.com/paper/2609.35427/) (2026)

## Abstract (arXiv)

Effective asynchronous planning, or the ability to efficiently reason and plan over states and actions that must happen in parallel or sequentially, is essential for agents that must account for time delays, reason over diverse long-horizon tasks, and collaborate with other agents. While large language model (LLM) agents show promise in high-level task planning, current benchmarks focus primarily on short-horizon tasks and do not evaluate such asynchronous planning capabilities. We introduce Robotouille, a challenging benchmark environment designed to test LLM agents' ability to handle long-horizon asynchronous scenarios. Our synchronous and asynchronous datasets capture increasingly complex planning challenges that go beyond existing benchmarks, requiring agents to manage overlapping tasks and interruptions. Our results show that ReAct (gpt4-o) achieves 47% on synchronous tasks but only 11% on asynchronous tasks, highlighting significant room for improvement. We further analyze failure modes, demonstrating the need for LLM agents to better incorporate long-horizon feedback and self-audit their reasoning during task execution. Code is available at https://github.com/portal-cornell/robotouille.