Robotouille: An Asynchronous Planning Benchmark for LLM Agents
Authors: Gonzalo Gonzalez-Pumariega
Leong Su Yean
Neha Sunkara
Sanjiban Choudhury
Venue: ICLR 2025 Poster (2025)
Keywords: benchmark
llm
agents
planning
Primary area: datasets and benchmarks
TL;DR: Robotouille is an LLM agent benchmark for stress testing stress testing long-horizon synchronous and asynchronous planning capabilities.

Abstract: 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 over-
lapping tasks and interruptions Our results show that ReAct (gpt-4o) 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.

Published as a conference paper at ICLR 2025
ROBOTOUILLE: AN ASYNCHRONOUS PLANNING BENCHMARK FOR LLM AGENTS
Gonzalo Gonzalez-Pumariegr Leong Su Yean, Neha Sunkara, Sanjiban Choudhury Cornell University
ABSTRACT
Effective asynchronous planning, or the ability 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 fong-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 capabilitiess 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 over- lapping tasks and interruptions. Our results show that ReAct (gpt 4 4-o) achieves 47% synchronous tasks but only 11 % on asynchronous tasks, highlighting sig- nificant 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 here.
INTRODUCTION
Large language models (LLMs) have demonstrated impressive reasoning and task planning capabili- ties in short-horizon single-agent environments with clearly defined sequential tasks (Yao et al., 2022; 2023b; Shinn et al., 2023); however, decision-making in the real world introduces more intricate array of challenges. Consider an assistant that helps you with cooking a recipe. must be able to handle (1) time delays such boiling spaghetti, which takes time to complete. An efficient agent would move onto other steps instead of waiting for the spaghetti to fully cook. It should also handle (2) diverse long-horizon tasks that require the assistant to satisfy multiple objectives and reason about dependencies between different actions. Finally, the assistant should handle (3) multiple agents by coordinating with others or distributing tasks based each agent's 's capability. To tackle these challenges, an agent must be capable of asynchronous planning, or the ability to efficiently reason and plan over states and actions that must happen in parallel sequentially. With this capability, an agent can coordinate time delays, break down long horizon tasks into subtasks, and efficiently assign subtasks multiple agents.
To improve asynchronous planning capability, we are interested in a benchmark (Table 1) that stress tests LLM agents using time delays. AsyncHow Lin al. (2024) benchmarks asynchronous planning but does not use an interactive environment, lacking support for closed-loop planning agents. ALFWorld (Shridhar et al., 2021), WebShop (Yao et al., 2023a) and PlanBench (Valmeekam et al., 2023b) offer long-horizon diverse tasks (up to 50, 48 and 90 steps respectively) but evaluate with single agent and no time delays. VirtualHome (Puig et al., 2018) offers long-horizon (up to 96 steps) and multi-agent tasks with procedural generation for extra diversity but also lacks time delays.
To address these gaps, we introduce ROBOTOUILLE, a simulator for cooking diverse recipes designed to stress test LLM agents (Figure 1). ROBOTOUILLE tests asynchronous planning through tasks that take time like cooking meat for burgers or sandwiches or filling up pot with water to cook soup. Its fully customizable ISON backend allows for the addition of new states, actions, and goals simplifying the creation of diverse long-horizon tasks. Finally, ROBOTOUILLE supports surn-based and real-time multi-agent execution either locally or on the network.
"Corresponding author. Email: gg387 @comell.edu

---

Published as a conference paper at ICLR 2025
ROBOTOUILLE
Synchronous Benchmark
Asynchronous Benchmark
Syndronsus Planning
Syechroroua
Proddrr
Cooky leuce
X
Bocc eg. The gial K.
Action Move reborl frome tóde2 to stewel.
Lingng Action
veve vor Joti
Oioevation
sivel has paryl tip of
Inefficent
Elficeet
Steps: 25
Steps: 20
Figure 1: Overview of ROBOTOUILLE along with examples our synchronous and asynchronous benchmarks. ROBOTOUILLF takes domain and problem JSON to procedurally generate an envi- romment for an LLM agent to plan in. the synchronous benchmark, the order that the burger is assembled has minimal impact in the efficiency of the plan. In the asynchronous benchmark, ordering matters due to time delays; leaving the patty to cook before cutting the lettuce is more efficient than leaving the patty to cook after cutting the lett.
In addition, we provide 3 datasets to test LLM agents' synchronous, asynchronous, and multi-agent planning capabilities. We implement 3 baselines for benchmarking the synchronous and asynchronous datasets, leaving multi-agent for future work, and provide analyses on the failure modes to provide insights for future work. Our hope is for the research community engage with ROBOTOUILLE to create an ecosystem of environments and methods that increase the diversity of our testbed and the capabilities of LLM agents.
Our key contributions include the following
We present a new environment, ROBOTOUILLE, for stress testing LLM agents' ability to perform asynchronous planning to handle time delays, diverse long-horizon tasks, and multi-agent.
2. We curate 3 datasets for synchronous, asynchronous, and multi- settings, each contain- ing 10 unique tasks each with 10 procedurally generated instances.
3. We implement various LLM baselines, evaluate them on the synchronous and asynchronous datasets, and provide quantitative and qualitative analyses failure modes.
2 ROBOTOUILLE
We formalize ROBOTOUILLE tasks as an MDP with time-delayed effects, . =< S,A,T,R Each state s S is (&,, H²) where s, represents observable state elements like objects or predicates such as iscut (lettucel), or "lettucel is cut". and on (lettucel, table2), or "lettucel on table2", and H, set of timer variables E H, each created by actions with countdown function h(x:)= d (x= where d is delay constant and is the timer's activation step. Action E a grounded action such as move (robotl, tablel, table2), , "Move robot 1 from tablel table2" that may introduce new timers h. Actions have preconditions over state predicates which must be met to be valid. For a given state s and action a, the transition function T: S A S returns the next state s' ($141, He+1) if valid or the current state a is invalid. For a valid action step, 8 = 8, (predicates(h)) E H,,h(t) h(t) = 0} to removes expired timers and H (H₂ (h(h(()) 0}} U (hla adds delay) to update active timers. The
2

---

Published as a conference paper at ICLR 2025
reward function R: S + {0, 1} defines the goal of given task where for goal state 8g. r(sg) We provide complexity analysis between synchronous and asynchronous settings in Appendix A.9.
Benchmark
High-Level Actions
Multi-agent
Procedural
Time Delays
Number Tasks
Longest Plan Horizon
Lovel Generation
ALFWorld (Shridhar et al., 2021)
X
K
3827
50
CuisineWorld (Gong ct al., 2023)
/
X
33
11
MiniWoB++ ++ (Liu et al., 2018)
X
X
40
13
Overcooked-4 Al (Carroll et al., 2020)
X
1
100
PlanBench (Valmeekam et al., 2023b)
885
T-bench (Yao al., 2024)
/
X
X
165
30
WebArena (Zhou et ul., 2024)
X
V
X
812
30
WehShop (Yao et ul. 2023a)
X
X
12087
90
AgentBench (Liu al., 2023d)
V
X
8
35
ARA (Kinniment al., 2024)
12
AsyneHow (Lin al., 2024)
1600
MAgIC (Xu et al., 2023)
5
20
T-Eval (Chen et al., 2024)
X
23305
19
MI. AlggnnBBencch (Huang et al., 2024)
X
X
X
13
50
GAIA (Mialon el al., 2023)
3
466
45
VirtualHome (Puig et al., 2018)
2821
ROBOTOUILLE (Ours)
30
82
Table I: Comparison between ROBOTOUILLLFF and other benchmarks. See Appendix A. for more details.
Domain and Problem JSONs ROBOTOUILLE uses JSONs to fully describe task M using domain D =< OD, PD.AA >> and problems et al., 1998) and described in Figure (a-b). Domain D defines the possible states and actions of an environment with object types Op. predicate definition Pp and action definitions Ap. Problem P grounds the domain definitions with objects Op, initial state predicates Ip, and goal Gp. In addition, PD. Ap and Gp have language representations for an LLM agent.
Op, Ip, Gp >, inspired by PDDL (Acronautiques
Action Effects We adopt immediate effects from PDDL, where a(s,a)= = and s' results from predicates being added or removed due to a. To extend actions beyond immediate effects, we introduce special effects, which are custom code blocks that allow for complex interactions, such as delayed effects in cooking where predicates are added after a delay. Figure 2 (c) shows an example of special effect for the cook action. A conditional effeet applies the iscockii brookking ng predicate if an item i1 is on station sl and removes it otherwise. In addition, a delayed effect is nested that adds predicate i s cooked (il) after delay specified in the problem JSON (see Appendix A.2).
Language Goal Language goals are inherently ambiguous and many states may satisfy them. For example, in Figure (d), the goal Make lettuce cheese sandwic ch table lacks information about which ingredients or tables to use (in the case where there are multiple) and doesn't t specify whether the lettuce is above or below the cheese. We created a flexible goal specification system that captures combinatorial number of goal states that may satisfy a vague language goal. In this example, by specifying that (1) one bread slice must be directly the table, (2) another is somewhere at the table while being clear top and (3) lettuce and cheese must be somewhere at the table, we fully capture all possible outcomes that satisfy the language goal.
Procedural Generation ROBOTOUILLE provides procedural generation which works off an existing problem JSON. To ensure that goals can be satisfied, the problem JSON should contain the minimum number of objects that satisfy the goal. The procedural generator shuffles existing objects and adds new objects which allows for stress testing on diverse environments with varying language descriptions and optimal paths to the goal.
Multi-agent ROBOTOUILLE supports multi-agent environments by simply adding more players into the problem JSON, These environments can be either turn-baeed, where LLM agent controls single agent at time, or real-time, where an LLM agent controls all agents simultaneously. We additionally implement networked multi-agent allow data-collection of human- human play and evaluating agents against humans.

---

Published as a conference paper at ICLR 2025
peniicate_dets""
"aaz"" Taove",
*name": Nastable",
"precons") [[
"pacan_typea;: ["stasion"),
*predicate" *locf,
"language werpuueeeesrrrrreoeo _esorriptorat:
"params"; (fpt", *635),
*pt: *(0)
'ia_true's txue
11.1
"paran_types"; t*itent, "station"),
"predicate"t *0ot,
"Langagee wwwpppppddarppppppo pptorr
"params" (fp1%, *22t), "in_true"s true 1, "predicate"s *toof "parass": (*p1",
egt; *(0) ie directly top of 133%
*1"
KB3 has 10) directly on top of
(a) Predicate Definitions
*afx":
*Language, cespupeddecrippioon
*sda": [f
-. "Nove (pi) From [81) to (x2)*
"type": *conditional",
*pacant; *11*,
*canditiona":
Action Definitions
"predicato" *item_on",
danl_descriptien"
"in_true";
*Make lettuce cheese sandkich table",
*goal": II
"Ia"s [I
"predicate"; "ites_on",
"predicata": "Lacooking",
"arga": ["bread", "tabie"),
"parans": (M11%),
*ids"; [L, 21
-in_tsue":
"predicate"i *itewatt 1.
*ofxt:
(*lettuce", "table"), "ids":
"sypo": "delayedt.
*paran": "11",
b
*Ix": [I
"predicate"; *itemaat",
*predicate"; *secooed"',
"arge": (fcheese", *table"),
*parara"; (M21%).
*id"":
"in_true"
"predicate"; *sscooking", "pacana": (M11*),
*arge*: (*bread", "table"),
"ids":
"ix,trum" dales
b.
11,
"predicate": *eleact,
*etxts [l
targe*: ("bread"),
*ido":
Nested special effects for "cook" action
(d) Goal Description
Figure 2: ROBOTOUILLE uses domain and problem JSONs to define MDP and language descrip- tion of environment and tasks using (a) predicate definitions, (b) action definitions, (c) special action effects and (d) goal definitions. See Appendix A.2 for other JSONs used.
DATASET DETAILS
In this section we discuss the contents of the synchronous and asynchronous datasets and their differ- ences. We provide discussion of the in-context example tasks and multi-agent dataset in Appendix A.3. Each dataset contains 10 unique tasks and has 10 procedurally generated instances. Table 3 and Appendix A.6 include visual representations of the tasks and dependency graphs respectively.
Synchronous Dataset This dataset consists tasks involving assembling sandwiches and burgers with ingredients that may need to be cut. Any ingredients that can be cooked initialized as cooked. Tasks to 3 involve assembling sandwiches of increasing difficulty where Task 1 only involves assembling and Task and involve cutting ingredients. Tasks 4 to 7 involve assembling burgers which differ from sandwiches in that the burger buns have ordering constraints with distinct buns that go on the top and the bottom. Unlike other tasks, Task enforces strict ordering constraint on the placement of all ingredients. Finally, Tasks 8 to 10 involve the preparation of 2 recipes which increase in difficulty from identical sandwiches, identical burgers, and finally sandwich and burger with different ingredients.
Asynchros Dataset This dataset consists of tasks including sandwiches and burgers from before but also fried recipes and soup. Unlike the synchronous dataset, ingredients that can be cooked are initialized as uncooked; this allows for asynchronous planning. Tasks 1 to use the same ingredients as those in the synchronous setting except for an added ingredient which must be cooked or fried. We studied these tasks in Appendix A. 17 for a closer one-to-one comparison with synchronous tasks and found that asynchronous tasks are more difficult. Tasks 4 and 5 involve making burger and fried recipe; Task 4 includes french fries which requires cutting potato then frying while Task recipe, soup, which involves filling a pot with water from a sink, boiling the water, putting ingredients inside, and finally serving in bowl. Of these subtasks, filling pot with water and boiling the water
includes fried onions which is the same process with an onion. Tasks 6 to 7 introduce
4

---

Published as a conference paper at ICLR 2025
steps that can be done asynchronously with other tasks. Finally, Tasks to 10 involve making soup along with increasing numbers of sandwiches and burgers.
EXPERIMENTS
4.1 BASELINES
We evaluate LLMS ROROTOUILLE using the following baselines: T/C, I/O CoT, and ReAct. I/C takes as input the initial state, including valid actions and goal, and outputs an plan directly. I/O CoT (Wei al., 2023) also takes as input the initial state but outputs plan with chain of thought before each action that estimates the resulting state. Instead of outputting the entire plan, ReAct (Yao et al., 2022) outputs reasoning and the next action given the current state, and receives the next state before repeating. We use an ablated version of ReAct that only keeps the reasoning and action of the previous timestep in context (along with the base prompt and in-context examples); the improved performance and cost-effectiveness is detailed in Appendix A.7. Each baseline receives a single in-context example on a training example excluded from the testing set. We use temperature 0.7 for all models. All prompts and few-shot examples are located in our codebase here.
4.2 RESULTS AND ANALYSIS
4.2. I OVERALL TAKEAWAYS
Closed-loop agents are superior: The best baseline, 4-t ReAct, achieves 47% the synchronous dataset and 1 11% on the asynchronous dataset, surpassing open-loop approaches I/O and I/O COT (Finding 1, Sec 4.2.2).
Poor feedback incorporation leads to decreased asynchronous performance: Despite being closed-loop, gpt o ReAct failures often make little progress towards the goal (Finding Sec 4.2.2) due to poor failure recovery (Finding 5, Sec 4.2.3). We find that boosting priors improves performance (Finding 7, Sec 4.2.4) but discuss better feedback methods in Section 5.
Synchronous and asynchronous failures are closely related: failures are dominated by rule violations and goal misinterpretation (Finding Sec 4.2.3). We hypothesize that this is due to poor failure recovery (Finding 5, Sec 4.2.3) and agents that recover efficiently could boost performance in both settings.
Both synchronous and asynchronous
Task prioritization is critical in asynchronous planning: Proper prioritization of subtasks in asynchronous settings significantly boosts performance (Finding 6, Sec 4.2.4).
4.2.2 SUCCESS AND OPTIMALITY
Finding 1. Closed-loop baselines outperform open-loop baselines.
Table 2 shows the success rates of various LLMs baselines on the synchronous and asynchronous datasets. Table shows the task-specific success rates of baselines using 4pt4-o Success rate is determined by reaching the goal within 1.5 times the optimal number of steps for the given instance. Baselines exceeding this step limit are terminated.
Among all the LLM baselines, ReAct with the gpt 4 model performs the best on the synchronous and asynchronous datasets. I/O performs worst for most LLMs while I I/O CoT improves per- formance. We qualitatively observed gemini-1. 5- flassh failing with ReAct since it attempts to solve the few-shot example goal rather than the current environment goal. This is likely due to the long context examples, aligning with findings in Liu et al. (2023c) where LLMs struggle with simple tasks in long contexts. We investigate PLaG (BaG) Lin et al. (2024) and Reflexion Shinn et al. (2023) performance the asynchronous dataset in Appendix 1. and achieved small performance improvements. We present the performance state-of-the- the-art open source LLMs in Appendix 1.1
When considering task-specific success over 4-t4-o baselines, ReAct: generally achieves higher performance per task. While we list the horizon length as a crude difficulty metric, is evident that success rate is not solely dependent it. We investigate this further in Appendix A.8. We also investigate different agent failure modes in more depth in Section 4.2.3.
Finding 2. Asynchronous successes are less optimal than synchronous ones.
5

---

Published as a conference paper at ICLR 2025
Synchronous (%)
Asynchronous (%)
I/O
I/O CoT
ReAct
I/O
I/O CoT
ReAct
9pt4-o
4.00
14.0
47.0
1.00
1.00
11.0
gpt-4o-mini
4.00
10.0
11.0
0.00
1.00
0.00
Demini-1.5-flash
0.00
13.0
0.00
0.00
0.00
0.00
claude-3-haiku
1.00
2.00
2.00
0.00
0.00
0.00
Table 2: Success rates of state-of-the-art L.LMs the synchronous and asynchronous datasets.
I/O
I/O CoT
ReAct
Horizon Length
Synchronous (%)
20.0
40.0
70.0
10
0.00
20.0
80.0
14
10.0
30.0
80.0
0.00
40.0
0.00
0.00
6
10.0
20.0
20.0
23
0.00
0.00
50.0
36
0.00
30.0
0.00
10.0
20.0
63
110]
0.00
0.00
20.0
57
Total
4.00
14.0
47.0
Asynchronous (%)
10.0
0.00
20.0
21
0.00
0.00
30.0
27
0.00
0.00
40.0
37
0.00
0.00
10.0
5
0.00
10.0
0.00
46
0.00
0.00
10.0
19
0.00
0.00
0.00
42
0.00
0.00
0.00
46
0.00
0.00
0.00
68
10
0.00
0.00
0.00
82
Total
Table 3: got 4-o performance on the synchronous and asynchronous datasets.
Fig. 3 shows a histogram of the binned optimality rates on the successful runs 4-t ReAct on [[ the synchronous and asynchronous datasets. Optimality rate is [ where [| is the number of steps
taken by agent and ||>*|| is the optimal number of steps reach the goal from the initial state.

---

Published as a conference paper at ICLR 2025
For the synchronous dataset, 55.3% of successful attempts optimal compared the asynchronous dataset where only 9.1% of successful attempts are optimal. We expect this since the order that tasks done in the synchronous setting does not affectt optimality compared the asynchronous setting. We also see for the asynchronous dataset that 63.6% of successful attempts are suboptimal in the (1, 1.25) bucket. We qualitatively observe that while the LLM agent usually prioritizes asynchronous subtasks, suboptimal runs were due to inefficient actions, such as waiting while cooking. We further investigate the agent's subtask prioritization in Section 4.2.4.
Synchronous
Asynchrooous
Perconiago (86
Percniage (8%
$3.6%
53,37
27.0%
19.1%
9.31%
15]
(1.25,
(1,125)
(1.25,
Optimality
Optimality Ratio
Figure 3: Histogram of the optimality rate for gpt 4 ReAct successes the synchronous and asynchronous datasets. The bin includes attempts that were optimal. Attempts between (1, 1.5] are suboptimal but classified successful. Attempts greater than optimality rate of 1.5 classified as failures.
Finding 3. Asynchronous failures make little progress toward the goal.
Fig. 4 shows a histogram of the binned normalized steps to go on the failed rums of gpt ReAct on the synchronous and asynchronous datasets. Steps to go is In where [ are the optimal ]>'
number of steps left to reach the goal from the final state in failed run and normalization factor ||>*|| is the optimal number of steps to reach the goal from the initial state.
Synchoomous
Asynchronous
100
100
Percentage (%)
Perseslage (%)
58.655
41.5%
25.3%
20
10.5.100 Normalized Steps to Go
00.0.5
1.0]
1.5]
Normalized Steps to Go
Figure 4: Histogram of the normalized steps go for gpt 4-o ReAct failures on the synchronous and asynchronous datasets. The 0 to 0.5 bucket includes attempts that were making progress towards the goal while the 0.5 bucket includes attempts that made little to no progress towards the goal. Buckets greater than includes attempts that traversed further away from the goal.
For the asynchronous dataset, about 58.6% of the failures are in the (0.5, 1.0] bucket, which shows that most attempts made little to no progress towards the goal. We also see this in the synchronous dataset, with 41.5% of failures in the (0.5. 1.0] bucket. We show quantitative results of gpt 4 ReAct's 's ineffective failure recovery in Section 4.2.3 suggesting that failures on the asynchronous dataset mainly due to little progress being made. In contrast, see 45.3% failures in the
7

---

Published as a conference paper at ICLR 2025
synchronous dataset from (1.0, oo) which show that most attempts make progress away from the goal.
The asynchronous dataset only has 25.3% failures from (1.0, oo). We present qualitatively annotated failures in Section 4.2.3 that suggest failures on the synchronous dataset due to misunderstanding the goal.
4.2.3 FAILURE MODE ANALYSIS
Finding 4. Dominant failures in both settings stem from rule violations and goal misinterpretations.
Fig. 5 shows nested piechart that captures failure modes of gpt 4 ReAct on the synchronous and asynchronous datasets. We define our failure modes in terms of uncertainty over the MDP of the environment. The main failure categories include uncertainty in the state (S), actions (A), transition function (T) and the goal (G). For detailed description of the subcategories and dataset annotation, see Appendix A.
For synchronous failures, the uncertainty in the goal accounts for the majority at 64.1 1% followed by the uncertainty in the transition function at 32. 1 %. Goal failures could due (1) an incorrect understanding the start of the plan or (2) mistake during plan exccution, such using an ingredient without cutting it, which is incorrectly believed to satisfy the goal. We observe that case (1) occurs 28.3% of the time under Bad Start; the LLM agent restates goals incorrectly for complex tasks with strict ordering dependencies like Task 6 or tasks with many diverse ingredients like Task 10 which we show in Appendix 12. We observe that case (2) occurs 35.8% of the time under the remaining subcategories; although the LLM agent starts with a correct goal, misunderstands the goal during execution by choosing the wrong action. For transition failures, violating the 'one item at station' rule accounts for the majority of failures at 24.5%. We qualitatively observe that the agent attempts to use cutting stations for ingredient preparation while other items occupy the station; however, we also observe that once the agent has recovered from this failure it is unlikely to repeat it which we show in Appendix 141
Sprchoonous
Asynchronou
Failunos
[S] Misunderstands Predicates
13.00
[T] Violates 'Hold ore ibemn tule
14%
[T] Violates 'One station
2L.5
[T] Violates both
[c]
[G] Uneertainties
[G] Ingredient Liveeraintty
[G] Oldder Uncertainty
[A] Action
Figure 5: Nested pie chart of g-t4-o ReAct failure modes capturing uncertainties in the MDP. The main categories are on the outer circle representing the uncertainty the state space (S), action space (A), transition function (T), reward/goal (G). The subcategories the inner circle represent the dominant cause of failure and are described further in Appendix A.
For asynchronous failures, the inverse true with uncertainty in the transition function accounting for 56.8% of failures and uncertainty in the goal accounting for 34.1% 1% of failures. Similar to the synchronous failures, violating the 'one item at a station' rule dominates failures at 53.4%. This is due to the increased number of unique stations in the asynchronous setting compared to the synchronous setting which increases the potential number of recoveries necessary. the synchronous setting, which only uses the cutting board station, agent may need to recover once from violating the 'one item at a station" rule. In the asynchronous setting, which uses stoves, fryers, and sinks, an agent, in the worst case, may need to recover from violating rules on each station in task.
We point out that while we designed the synchronous and asynchronous datasets to test different capabilities of LLM agents, mainly observe similar transition failures in both settings. This demonstrates the need to improve LLM agents at following environment constraints to improve their decision-making ability. We investigate this further in Section 4.2.4.
8

---

Published as a conference paper at ICLR 2025
Finding 5. Asynchronous recovery is worse than synchronous recovery.
Fig. 6 shows a histogram of the repeated transitions gpt 4-0 ReAct rums on the synchronous and asynchronous datasets. We use repeated transitions as proxy for measuring ReAct's effectiveness at recovering from failure.
In both the synchronous and asynchronous datasets, we that the majority of successes have O repeated transitions; few successes have repeated transitions but successfully recover. For failures, the asynchronous dataset's 's lower and upper quartiles 103.1% and 55.8% larger than the synchronous dataset's quartiles. This means that failures on the asynchronous dataset are expected to have higher repeated transitions; this ineffectiveness recovery aligns with the transition failures being dominant for the asynchronous setting in Fig. 5. Similarly, since the synchronous dataset has lower quartiles than the asynchronous dataset, we expect to see less repeated transitions which suggests less transition failures. We do a further investigation in Appendix A.13 by introducing stochasticity and find that even in synchronous settings LLMs struggle recovery.
Synchromous
Asynchromous
Tellac
(etoro)
7.00
Misten-battrrsi
Quantlosifalam)
2.53
Kle
Trequency
15
15
15 Repested Transitions
Repeated
Transitions
Figure 6: Histogram of the repeated transitions of gpt 4-o ReAct runs the synchronous and asynchronous datasets. The median and quartiles of the asynchronous dataset are generally higher than those of the synchronous dataset, indicating higher repeated transitions.
4.2.4 FOLLOW-UE UP INVESTIGATION
From the previous experiments, we conclude that LLM agents struggle in the asynchronous dataset due to simple failures that arise in the synchronous dataset. In order to have a better understanding of how improve LLM agent capabilities on asynchronous planning, we look into asynchronous subtask prioritization and boosting performance.
Finding 6. Proper asynchronous prioritization boosts performance.
Efficient asynchronous planning requires prioritizing subtasks that can be performed asynchronously. We investigate how success rate changes with asynchronous task prioritization to understand the impact of asynchronous planning on the results. Our hypothesis is that prioritizing asynchronous subtasks leads to higher success rates because within the maximum step limit. We find that the success rate conditioned on prioritization is 16% compared to 6% without, supporting that prioritization achieves higher success rate. An agent should be capable of auditing its own reasoning and plan to ensure that its prioritization correctly targets asynchronous subtasks. We discuss methods for reliable velfiieriiication in Section
planned trajectory shorter and reaches the goal
Finding 7. Stronger priors improve asynchronous performance.
The dominant failures of gpt 4- 4 ReAct on the asynchronous dataset were transition failures. We investigate how We create an augmented method, ReAct Prior, that prompts ReAct with more details about the rules of ROBOTOUILLE.
improve performance by increasing the priors over the transition function.
Fig. 7 shows nested pie charts of the failure modes on Tasks to of the asynchronous dataset from the 4- ReAct experiments in Table and from 4-o ReAct
Prior.
We observe a statistically insignificant change in performance, where the success rate for gpt 4-o ReAct is 0.30 + 0.085 and gpt 4 4-o ReAct + Prior 0..00 0.050. We also observe failures

---

Published as a conference paper at ICLR 2025
relating to violating the 'one item station' rule decrease from 38.1% for gpt4-o ReAct (8 failures) to 22.2% for qpt4-o ReAct + Prior (4 failures) accounting for a 50% decrease in these transition failures. While this shows that increasing priors rules decreases transition failures as expected, overall performance did not improve due to other failures that arose. We note that state failures increase from 23.8% for gpt4 ReAct. (5 failures) to 38.9% for gpt4-o ReAct. + Prior (7 failures). These failures are due to misunderstandings with the state description provided; specifically, the agent assumes that meat on a stove always implies it is cooked. Augmenting ReAct + Prior over state priors would presumably improve performance but is impractical because requires excessive effort from a domain-expert and wouldn's generalize new domains. We discuss methods for incorporating state feedback in Section 5.
Asyne go
Aryiic apt-lo
Faalures
[A] Invalid Action
[i] Vidiates
Total 21
Total IS
Ari
Vinlatew, Chee item at shrion rale
[G] lngondiont Uncortiitt
Order Unvertentty
2225
[G] Both Unormaintics
Figure 7: Nested pie chart of failure modes capturing uncertainties in the MDP of gpt 4-o ReAct + Prior on Tasks to (30 problems) the asynchronous dataset using 9pt ReAct and gpt4-o ReAct Prior.
DISCUSSION
In this paper we propose new benchmark, ROBOTOUILLE, for stress testing LLM agents on synchronous, asynchronous, and multi-agent settings. We evaluate state-of-the-art LLMs and expose their dominant failure modes are similar across synchronous and asynchronous settings. We perform follow-up studies to bring up performance and uncover the need for improvements in LLM agents that we discuss below.
Feedback Incorporation general method to incorporate long-horizen planning feedback LLM agents is to include all interactions in the context history. This works well for models with large context windows or near- mear-infinite attention mechanisms (Liu et al., 2023b; Munkhdalai et al., 2024), but LLMs often struggle with long-contexts (Liu et al., 2023c). An alternative is RAG (Lewis et al., 2021), yet this shifts the complexity to retrieval. As explored in Section 4.2.4, a promising approach is for the agent to summarize interactions into facts reduce uncertainty and strengthen priors. It should also reason about future states to avoid myopic behaviors, as shown qualitatively in Appendix A.11. Another underexplored yet effective approach is finetuning LLM agents (Chen et al., 2023) with methods such as TD learning and value propagation (Putta et al., 2024; Gehring et al., 2024).
Self- Verification An LLM agent should be able to audit but LLMs are unreliable self-verification (Valmeekam et al., 2023a). Other approaches use LLMs to create representation for external planners (Liu al., 2023a; Guan al., 2023) or finetune on planning datasets (Pallagani et al., 2022; Lehnert et al., 2024) but these methods are difficult to debug and lack guarantees respectively. One approach to combine code-use with language (Wang et al., 2024); reasoning language and verifying understanding with code and APIs would allow us stronger guarantees that easier to debug.
Real- World Application To effectively deploy LLM agents on real-world agents, the cost and inference time of LLMs must be brought down to make them affordable and quick. This is especially problematic for long-ho horizon task planning since cost and inference time increases context grows. These system must also be evaluated with real humans; one future direction for Robotouille is serving online platform to test agents with humans through collaboration.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported in part by the National Science Foundation FRR (#2327973) and ONR Young Investigator Award. Sanjiban Choudhury supported in part by the Google Faculty Research Award and the OpenAl Superalignment Grant.
REFERENCES
Constructions Aeronautiques, Adele Howe, et al. Pddll the planning domain definition language. Technical Report, Tech. Rep., 1998.
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian lchter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. Do can, not as say: Grounding language robotic affordances. 2022. URL https: / arxiv. org/ abs 2204 01691.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving claborate problems with large language models. Proceedings of the AAAI Conference Artificial Intelligence, 38816)11662211766666 March 2024. ISSN 2159-5399. doi: 10. 1609/aaai.
htth:t::.. : dx doi. org/r0rg///// 609/ aaai waaai..vvi1...999
Micah Carroll, Rohin Shah, Mark Ho, Thomas L. Griffiths. Sanjit A. Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. 2020. URL
https: / //wpvva.avvvv///////a//e...a.avv org/ abs / 910. 05789.
Baian Chen, Chang Shu, Ehsan Shareghi, Nigel Collier, Karthik Narasimhan, and Shunyu Yao. Fireact: Toward language agent fine-tuning, 2023. URL https::t///attttt wrg.
/agg abs /2310 05915.
Zehui Chen, Weihua Du, Wenwei Zhang, Kuikun Liu, Jiangning Liu, Miao Zheng, Jingming Zhuo, Songyang Zhang, Dahua Lin, Kai Chen, and Feng Zhao. T-eval: Evaluating the tool utilization capability of large language models step by step. 2024. URL https: http://aaxvvvv.o/o/ org.g.iiioo....ooooooo...oo.oo.. abs/ 2312. 1403.
Jonas Gehring, Kunhao Zheng, Jade Copet, Vegard Mella, Taco Cohen, and Gabriel Synnaeve. Rlef: Grounding code 1ims in execution feedback with reinforcement learning, 2024. URL https: /tapps///xxxv.../////
org/ abs/2210 02089.
Ran Gong, Qiuyuan Huang, Xiaojian Ma, Hoi Vo, Zane Durante, Yusuke Noda, Zilong Zheng, Song-Chun Zhu, Demetri Terzopoulos, Fei-Fei, and Jianfeng Gao. Mindagent: Emergent gaming interaction. 2023. URL https: arwiv.iiiivv org/ abs 230..099777.
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre- trained large language models construct and utilize world models for model-based task planning, 2023. URL https: /ttpaaxiivv..oo//.a//aaa
wtw.iiioorrreeee www.oo/g/aaooo abs /2t...
Qian Huang, Jian Vora, Percy Liang, and Jure Leskovec. Mlagentbench: Evaluating language agents on machine learning experimentation. 2024. URL 03302.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter. Inner monologue: Embodied reasoning through planning with language models. 2022. URL https: aarxivi. www.viioorr....oooooooooo..oo... abs 2207. 05608.
11

---

Published as a conference paper at ICLR 2025
Megan Kinniment, Lucas Jun Koba Sato, Haoxing Du, Brian Goodrich, Max Hasin, Lawrence Chan, Luke Harold Miles, Tao R. Lin, Hjalmar Wijk, Joel Burget, Aaron Ho, Elizabeth Barnes, and Paul Christiano. Evaluating language-mon modell agents realistic autonomous tasks. 2024. URL
https: /apps///axxiii org/ alss 2231 1.2.. 12..2..2 11671.
Lucas Lehnert, Sainbayar Sukhbaatar, DiJia Su, Qinqing Zheng, Paul Mevay, Michael Rabbat, and Yuandong Tian. Beyond a#: Better planning with transformers via search dynamics bootstrapping, 2024. URL https: axxiv. worgii.rrrrgooooooooo
.rgg abs / 24002 14083.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmmented generation for grwwledge-intensiie nlp tasks, 2021. URL https: www.iv.org/bbbe.. 2005. 11401.
Jacky Liang. Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code policies: Language model programs for embodied control. 2023. URL
https:://rxxiii /ttp//aavvv///////e//eeee...ev.t org/ alss
Fangru Lin, Emanuele La Malfa, Valentin Hofmann, Elle Michelle Yang, Anthony Cohn, and Janet B. Pierrehumbert. Graph-enhanced large language models in asynchronous plan reasoning. 2024.
URL https: /ttp:v/aaiivvvviaa org/
02805.
Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang. Joydeep Biswas, and Peter Stone. Lim+p: Empowering large language models with optimal planning proficiency. 2023a. URL https: htt/aaixvvvrrg//.
2304.11477 11477.
Evan Zheran Liu, Kelvin Guu, Panupong Pasupat, Tianlin Shi, and Percy Liang. Reinforcement learning on web interfaces using workflow-guid guided exploration, 2018. URL WtRhhttss://axiii org/abs/ 1802. 08802.
Hao Liu, Matei Zaharia, and Pieter Abbeel. Ring attention with blockwise transformers for near- infinite context, 2023b. URL https: http//iivvoo///////////a orgg hatp/ab//22/ 23100. 01889.
Nelson F. Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts, 2023c. URL https: /tt::///axxvvi org/ abs/ 2307.03172.
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. Agentbench: Evaluating lims as agents. 2023d. URL https: https::/taaaaea http://://axxvvoora///////////// 03688.
Chang Ma. Junlei Zhang, Zhihao Zhu, Cheng Yang, Yujiu Yang, Yaohui Jin, Zhenzhong Lan, Lingpeng Kong, and Junxian He. Agentboard: An analytical evaluation board of multi-turn llm agents. 2024. URL https: //wrxiv..vv///////////.../.awwvl org/ abs /2011 13178.
Grégoire Mialon, Clémentine Fourrier, Craig Swift, Thomas Wolf, Yann LeCun, and Thomas Scialom. Gaia: benchmark for general ai assistants, 2023. URL https: /tt//aaxvvvvo.../.a abs abs/2311. 2211. 12983.
Tsendsuren Munkhdalai, Manaal Faruqui, and Siddharth Gopal. Leave no context behind: Efficient infinite context transformers with infini-attention, 2024. URL httph:tt/////. httx/aaxvvvoo. www.iii...gg/abbbo 2404. 07143.
Vishal Pallagani, Bharath Muppasani, Keerthiram Murugesan, Francesca Rossi, Lior Horesh, Biplav Srivastava, Francesco Fabiano, and Andrea Loreggia. Plansformer: Generating symbolic plans using transformers, 2022. URL https: // wawiiivvvoooo org/ abs/ 2212. 08681.
Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li. Tingwu Wang, Sanja Fidler, and Antonio Torralba. Virtualhome: Simulating household activities via programs. 2018. URL https: //arxiv. org/abs//8055 0.
12

---

Published as a conference paper at ICLR 2025
Pranav Putta, Edmund Mills, Naman Garg, Sumeet Motwani, Chelsea Finn, Divyansh Garg, and Rafael Rafailov. Agent q: Advanced reasoning and learning for autonomous ai agents, 2024. URL
aitps://aamee org/ als///////////////// 222244088 07199.
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023. URL
https: / htt///rxivvv http//awwv...g...e../..... alss//b///// 2303. 11366.
Mohit Shridhar, Xingdi Yuan, Marc-Alexandr Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. 2021. URL htttttss:///ttteeee
orgg abs 2010 0. 03768.
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. 2022. hol.ttts:://rxii..oo
wwwpwwwwwwoooorooooooooeooeoeoee org/ abs 2209 11302.
Chan Hee Song. Jiaman Wu, Clayton Washington, Brian M. Sadler, Wei-Lun Chao, and Yu Su. LIm-planner: Few-shot grounded planning for embodied agents with large language models. 2023.
httpst wtt//aivvvoooo orgg abs 2212. 04088.
Karthik Valmeckam, Matthew Marquez, and Subbarao Kambhampati. Can large language models really improve by self-critiquing their own plans?, 2023a. httpstts://aaxii org. abs/
2310.08118.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambham- pati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. 2023b. URL https: / arxiv. org/ abs /200222222222 10498.
Xingyao Wang, Yangyi Chen, Lifan Yuan, Yizhe Zhang, Yunzhu Li, Hao Peng, and Heng Ji. Executable code actions elicit better Ilm agents, 2024. URL https: org /bs/ 2402. 01030.
Yuqing Wang and Yun Zhao. Tram: Benchmarking temporal reasoning for large language models. 2024. URL https:://// http:://axxvvvvveeee.e abs/////////////////////////aa//
abs / 00835.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou, thain-of-thought prompting elicits reasoning in large language models, 2023. URL httpt::t///aaaa httttps:/aaxiv..rrt
abs/ wtw./////.... 2201.2011112 11903.
Xixi Wu, Yifei Shen, Caihua Shan, Kaitao Song, Siwei Wang, Bohang Zhang, Jiarui Feng, Hong Cheng, Wei Chen, Yun Xiong, and Dongsheng Li. Can graph learning improve task planning? 2024. URL https:/ ptttps://ariiv. org 1911..99999...9..... 19119.
Lin Xu, Zhiyuan Hu, Daquan Zhou, Hongyu Ren, Zhen Dong, Kurt Keutzer, See Kiong Ng, and Jiashi Feng. Magic: Investigation of large language model powered multi-agent in cognition, adaptability, rationality and collaboration. 2023. URL https: arxiv. org/ abs 221111111222 08562.
Zhun Yang, Adam Ishay, and Joohyung Lee. Coupling large language models with logic programming for robust and general reasoning from text. 2023. URL https: //tp/aaxivv///////////.a.///.avl wog.giiiirrr..oooooooo.oooo.ooe. abs 2207. 07696.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. 2023a. URL https://arxia
org/abs/222 2200 01206.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao. and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023b. URL https:://// /eatts::/aaee //axxi/v worg/org//ooo.o. abs/ 10601.
13

---

Published as a conference paper at ICLR 2025
Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan. r-bench: A benchmark for tool-agent-user interaction in real-world domains. 2024. URL https:///axxi org/
Andy Zeng, Maria Attarian, Brian Ichter, Krzysztof Choromanski, Adrian Wong. Stefan Welker, Fed- erico Tombari, Aveek Purohit, Michael Ryoo, Vikas Sindhwani, Johnny Lee, Vincent Vanhoucke, and Pete Florence. Socratic models: Composing zero-shot multimodal reasoning with language. 2022. URL https: / arxivv orq/ abs / 2204. 00598.
Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. Webarena: A realistic web environment for building autonomous agents. 2024. URL https: httppp:://aaae h/tp///aavvv.o/////eeeeaae.. org. /abs/ 2307.13854.
A APPENDIX
A.
RELATED WORKS
In this section we will focus on our desiderata for LLM assistants and how ROBOTOUILLE is different from other related works (Table 1).
Asynchronous Planning Many benchmarks evaluate the task planning abilities of LLM agents (Shridhar al., 2021; Gong al., 2023; Liu al., 2018; Valmeekam al., 2023b; Yao et al., 2024; Zhou et al., 2024; Yao et al., 2023a) but few test the ability to plan asynchronously. Existing work relevant asynchronous planning evaluate LLM capabilities on temporal logic (Wang & Zhao, 2024) or use graph-based techniques (Wu et al., 2024); (Besta et al., 2024)) but do not focus on it. (Lin al., 2024) proposes the Plan Like Graph technique and benchmark AsyncHow that focuses on asynchronous planning but makes a strong assumption that infinite agents exist. (Carroll et al., 2020) proposes a benchmark, Overcooked-A AI, that involves cooking onion soup which has time delays but has limited tasks and focuses on lower-level planning without I.I.M agents. ROBOTOUILLE has dataset focused on asynchronous planning that involves actions including cooking, frying, filling a pot with water, and boiling water.
Diverse Long-Horizan Task Planning There vast amount work that use LLMs to plan (Ahn et al., 2022; Huang et al., 2022; Zeng al., 2022: Liang et al., 2023; Singh et al., 2022; Song et al., 2023; Yang et al., 2023; Song et al., 2023) but they tend to evaluate on short-horizon tasks with limited diversity in tasks. We present the number of tasks, longest plan horizon, and procedural generation capability of various benchmarks in Table to capture these axes. Notable LLM agent benchmarks that capture these axes include PlanBench (Valmeekam et al., 2023b), WebShop (Yao et al., 2023a), and VirtualHome (Puig et al., 2018). ROBOTOUILLE provides a focused set of diverse long-horizon tasks that can be procedurally generated.
Multi-agent Planning LLM agent benchmarks like (Liu et al., 2023d; Xu et al., 2023; Ma et al., 2024; Gong et al., 2023) evaluate multi-agent interactions but do not involve time delays. OvercookedAl (Carroll et al., 2020), while not an LLM agent benchmark, incorporates time delays which brings the complexity of asynchronous planning to multi-agent settings. ROBOTOUILLE provides multi- agent dataset for 2-4 agents, a choice between turn-based or realtime planning, and incorporates asynchronous tasks for added complexity.
A.2 ADDITIONAL ROBOTOUILLE JSONS
To provide flexibility in task and environment creation, an environment JSON (Figure 8) is used to define the problem. The size of the grid used can be specified, and positions of objects in the item can be specified using coordinates. Predicates that are specific to item can also be specified. In conjunction with the flexible goal creation described in Section 2, objects in the environment can be given specific ids, if the goal must be satisfied for specific objects. Additionally, if the environment requires a different number of cuts to complete cutting, or a different cook time, these values can be configured in the JSON.
Adding objects to the environment is also simple. To add new object, the necessary predicates for that object can be added to the domain JSON, and its corresponding image be added to the
14

---

Published as a conference paper at ICLR 2025
"width"; 3,
"height";
"config":
"num_cuts":
lettucs*: 3,
"default;;
cook soook_time::
patty";
defauit":
11.
"stations"; [[
"name"; "board",
"x": 0,
"y":
"ic": "X"
]1,
"items":
"name": "lettuse",
"x":
"y": 1, "stack-level";
"predicates": ("iscattable"),
11, "players": II "name"; "robot", "x": D, "y": 9, "direction"; [0, 1]
11,
"goal_ dene__eeerrp,,nn. "Cut the lettuce on the board until it la out",
"goal"; "predicate"; "iscut",
"arga": ["letture"),
"ids*: ["a*]
]]
Figure Environment JSON for a lettuce cutting task.
rendering JSON (Figure 9). there are different images for the object depending on the predicates that are true in the environment, these can also be specified. The images can also be scaled or offset using the rendering JSON.
To specify what button to press for each action, requires mouse click, we can specify where the player needs to click to perform the action. the action requires key press, we specify which button press for which action, and where the player needs to be to perform the action.
input JSON (Figure 10). If the action
A.3 ADDITIONAL DATASET DETAILS
Multiagent Dataset This dataset consists of tasks designed the LLM agent's multiagent capabilities. Robotouille's multiagent capabilities test the agent's ability to collaborate, and is more difficult because it includes tasks where agents may potentially interfere with one another, and share resources with one another.
Tasks 1- 3: Burgers The first 3 tasks involve cooking and assembling burger with increasing levels of difficulty. In Task 1, the agents need to chop lettuce, and cook patty, before assembling the burger with the patty, lettuce, a bottom bun, and top bun. In Task 2, the complexity increased with an additional ingredient, a tomato, that needs be and stacked onto the burger. In Task lettuce needs to be cut, a chicken needs to be fried, and an onion needs to cut first before it is fried. This adds level of complexity because one of the ingredients, the onion, needs to be both cut and fried.
Tasks 4- 6: Sandwiches Tasks involve making sandwiches. Unlike the tasks which only involve single agent, sandwiches in multiagent environments more complex than burgers because there ambiguity in the stack ordering. In burgers, the bottom bun needs to be at the bottom, while in sandwiches, piece of bread can be used either the bottom bread or the top bread. This is complex
15

---

Published as a conference paper at ICLR 2025
"player": {
"robot":
"Eront"; "robot__freoo foooot__foottttto png"",
"back":
*loft": "robot_.lftt.png""
#right": "robot_ "robot_right right.ppg"
Fir
"floor": "floorkitchen.pee
ritem":
"constants":
"STATION IETETTEEMPPPR OFFSET" 0.25,
*X_SCALB : 0.125,
"LSSCAL 0.75
"entities": {
"chicken":
"assete": "default"; "chicken.png',
"cokeed": "asset"; "cockedchicken.png"
"pradicates"; ("iscocked")
"fried":
"asseL"; "Iriedchickennpnng "pradinates": ("isfried")
b
cconseenss" (
b 2
"station":
"constants"; (h. "entities":
Eryer":
assetss:
ddfault"; "fryer.png"
"constents" ()
Figure Rendering JSON
cattsueeeeoo__tttteee [[
"nam=": "muve", "1 "inpus_ instructions:
"button": "left",
click_on"; "s2"
1. actioos": *Reyboardecctonns*
I[
"name" : "cook*,
"inpor_ "npo=_insttre iosttttotooorss ora":
"eey" "e*,
*at"; *el*
Figure 10: Input JSON
because the agents need collaborate and share the resources, and they need to agree on which bread to use the top bread and the bottom bread. Task 4 involves cutting a lettuce and cooking chicken before assembling the sandwich. Task involves one more ingredient, a tomato, which also needs to be cut. Task 6 double stacked lettuce chicken sandwich. Unlike the previous tasks, Task 6 enforces a strict ordering on the placement of the ingredients, meaning that the agents need to collaborate and properly agree the order of the ingredients.
Task 7: Soup Task involves cooking soup. This involves filling a pot of water, boiling a water, adding three ingredients into the soup: cut onion, potato, and cut tomato, before serving the soup in a bowl. This task is complex because involves multiple complex actions, including cutting, filling the pot, and boiling the water.
16

---

Published as a conference paper at ICLR 2025
Tasks 8 10: Multiple Recipes Tasks 8 10 involve the agents making multiple recipes. Task involves different recipes, a tomato cheese patty burger, and a onion chicken sandwich. This task is difficult for multiple agents because the 2 recipes both require ingredient to be cut and an ingredient to be cooked. Task involves making 2 identical lettuce cheeseburgers, Having 2 identical recipes is more complex than having 2 different recipes because the agents need agree which ingredient should be used in which burger. Finally, Task 10 involves making 2 different soups, potato tomato chicken soup, and potato cheese onion soup. Soups are the most complex recipes because it involves multiple complex actions. Furthermore, once an ingredient has been added to soup, it cannot be removed. This forces the agents to properly plan for which ingredient should go into which soup.
A.4 RELATED WORKS TABLE DATA
For each benchmark in (Table 1), we explain how the number of tasks and longest horizon plans were calculated.
A.4.1
ALFWORLD
ALFWorld consists of 3827 different tasks consisting of 3,553 train tasks, 140 seen tasks, and 134 unseen tasks from the ALFRED dataset.
The longest horizon plan is 50 steps since is the max number of steps per episode in ALFWorld.
A.4.2 CUISINEWORLD
World consist of 33 unique dishes which represent the tasks.
The longest horizon plan is steps since Figure 2 of Cuisine World indicates the dish distribution over the number of steps.
A.4.3 MINIWOB++
MiniWoB++ consist of 40 tasks since 40 tasks are filtered out of 80 total tasks from the MiniWoB benchmark.
The longest horizon plan is 13 steps since Table 1 indicates that 13 the maximum number of steps needed for perfect policy to complete the task.
A.4.4 OVERCOOKED-Al
Overcooked-AI consists of task since onion soup is the only dish in the environment.
The longest horizon plan 100 steps since 100 the max number of timesteps that planning methods are evaluated on.
A.4.5 PLANBENCH
PlanBench consist of 885 tasks consisting 600 tasks from Blocksworld domain and 285 tasks from the Logistics domain.
The longest horizon plan 48 steps since Figure PlanBench indicates that 48 is the longest optimal plan length from both the Blocksworld and Logistics problem sets.
A.4.6 7-BENCH
T-bench consist of 165 tasks consisting of 115 tasks from the 7-retail benchmark and 50 tasks from the 7-airline benchmark.
The longest horizon plan is 30 steps since 30 is the max number of actions per task in benehc.
A.4.7 WEBARENA
WebArena consist of 812 long-horizon web-based tasks.
17

---

Published as a conference paper at ICLR 2025
The longest horizon plan is 30 steps since 30 is the max number of state transitions in WebArena.
A.4.8 WEBSH1OP
WebShop consist of 12087 crowd-sourced text instructions which represent tasks.
The longest horizon plan is 90 steps since 90 is the max number of state visited in Table 2 of WebShop.
A.4.9 AGENTBENCH
AgentBench consist of 8 environments which represent tasks.
The longest horizon plan 35 steps since 35 is the largest number of average turns according to table 3 in AgentBench.
A.4.10 ARA
ARA consists if real-world tasks.
The longest horizon plan is 4 steps after counting the number of steps in the description of each task Table ARA.
A.4.11 ASYNCHOW
AsyncHow consists of 1600 high-quality instances for real-life tasks.
The longest horizon plan is 9+ steps after checking Figure of AsyncHow.
A.5 MAGIC
MAgIC consists of games which represent tasks.
We will assume all games will have 3 players and the same number of rounds as indicated in Table 3 of magic (1 round for Chamelcon, 2 for Undercover, and for Cost Sharing, Prisoner's Dilemma, and Public Good).
Calculations of longest plan with regards to steps:
Chameleon: (3 clues given out to participants + accusations/votes from participants guess for the final word if the chameleon correctly identified) round = steps
Undercover: (3 people assigned groups clues are given from participants 3 votes from participants) * rounds 18 steps
Cost Sharing: parties get allocation of money + (1 negotiation phase + fairness check) 5 rounds 13 steps
Prisoner's Dilemma: 3 decisions from participants rounds 15 steps
Public Good: (3 decisions from participants redistribution of money) 5 rounds = steps
Therefore, Public Good has the longest horizon plan with 20 steps.
A.5.1 T-EvAL
T-Eval consists of 23305 tasks according to Table 2 in T-Eval. The longest horizon plan is 19 steps based on Figure 5b in T-Eval.
A.5.2
MLAGENTBENCH
MLAgentBench consists of 13 ML tasks from diverse domains ranging in difficulty and recency.
The longest horizon plan is 50 steps based on Figure 7 in MLAgentBench which describes the distribution of numbers of steps used by agents.
18

---

Published as a conference paper at ICLR 2025
A.5.3 GAIA
GAIA consists of 466 carefully crafted and human annotated questions.
The longest horizon plan is around 45 steps based on Figure in GAIA which describes the distribu- tion of numbers of steps taken and tools used answer the 466 questions.
A.5.4 VIRTUALHOME
VirtualHome consists of 2821 programs which represent tasks.
The longest horizon plan is 96 steps after examining all the activities in VirtualHome's Activity Knowledge base and finding the longest.
A.6 TASK DEPENDENCY GRAPHS
In general, the ordering of ingredients for task dependency graphs does not matter unless specified. For soups, though the task dependency graphs imply a certain order, vegetables can be added to the pot long the pot contains water. In addition, all items placed on the table.
A.6.1 SYNCHRONOUS GRAPHS
Figure 11: Task 1 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare a cheese sandwich on table." "
Figure 12: Task 2 for the synchronous dataset in Table 3. The language goal for this graph "Prepare lettuce sandwich table."
19

---

Published as a conference paper at ICLR 2025
Figure 13: Task 3 for the synchronous dataset in Table 3. The language goal for this graph "Prepare sandwich with lettuce and tomato on table."
Figure 14: Task 4 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare a hamburger on a table."
Figure 15: Task 5 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare
a cheeseburger on a table."
Figure 16: Task 6 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare a double cheeseburger on table which contains two patties and two cheese slices interleaved (starting with patty)." " This graph also contains the constraint that needs be in this exact order.
20

---

Published as a conference paper at ICLR 2025
Figure 17: Task 7 for the synchronous dataset in Table The language goal for this graph "Prepare lettuce tomato cheeseburger on table."
Figure 18: Task 8 for the synchronous dataset in Table 3. The language goal for this graph "Prepare two lettuce chicken sandwiches separate tables."
Figure 19: Task 9 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare two lettuce tomato burgers separate tables." "
Figure 20: Task 10 for the synchronous dataset in Table 3. The language goal for this graph is "Prepare burger with cheese and onions on one table and a chicken sandwich with lettuce and tomato another table."
21

---

Published as a conference paper at ICLR 2025
A.6.2 ASYNCHRONOUS GRAPHS
Figure 21: Task for the asynchronous dataset in Table 3. The language goal for this graph "Prepare cheese chicken sandwich table."
Figure 22: Task 2 for the asynchronous dataset in Table 3. The language goal for this graph is "Prepare a lettuce chicken sandwich on table."
Figure 23: Task 3 for the asynchronous dataset in Table 3. The language goal for this graph is "Prepare a fried chicken sandwich with lettuce and tomato on a table".
Figure 24: Task for the asynchronous dataset in Table 3. The language goal for this graph is "Prepare tomato burger and fries on separate tables."
22

---

Published as a conference paper at ICLR 2025
Figure 25: Task 5 for the asynchronous dataset in Table 3. The language goal for this graph is "Prepare an onion cheese burger and fried onion rings on separate tables."
Figure 26: Task 6 for the asynchronous dataset Table 3. The language goal for this graph is "Make potato soup with whole potato and serve into a bowl on table."
Figure 27: Task 7 for the asynchronous dataset in Table 3. The language goal for this graph is "Make onion soup with 3 cut onions and serve into a bowl on table."
Figure 28: Task 8 for the asynchronous dataset in Table 3. The language goal for this graph is "Make tomato soup with a whole tomato served into a bowl on a table and a lettuce chicken sandwich on another table."
23

---

Published as a conference paper at ICLR 2025
Figure 29; Task 9 for the asynchronous dataset in Table 3. The language goal for this graph is "Make soup with a cut tomato and cut onion served into a bowl on table and two chicken sandwiches on other tables."
Figure 30: Task for the asynchronous dataset in Table 3. The language goal for this graph is "Make soup with whole onion and potato served into bowl, burger with lettuce and fried onion rings, and an onion chicken sandwich all on separate tables."
A.6.3 MULTI-AGENT GRAPHS
Figure 31: Task for the multi-agent dataset. The language goal for this graph is "Prepare a lettuce burger table."
24

---

Published as a conference paper at ICLR 2025
Figure 32: Task for the multi-agent dataset. The language goal for this graph "Prepare a lettuce tomato burger on a table."
Figure 33: Task for the agent dataset. The language goal for this graph is "Prepare lettuce fried onion fried chicken burger on a table."
Figure 34: Task for the multi-agent dataset. The language goal for this graph is "Prepare lettuce chicken sandwich on a table."
Figure 35: Task for the multi-agent dataset. The language goal for this graph is "Prepare a lettuce tomato fried chicken sandwich table."
25

---

Published as a conference paper at ICLR 2025
Figure 36: Task for the aulti-agent dataset. The language goal for this graph "Prepare a double lettuce chicken sandwich table which contains two chicken patties and two lettuce leaves interleaved (starting with a patty). This graph also contains the constraint that needs be this exact order.
Figure 37: Task 7 for the multi-agent dataset. The language goal for this graph is "Prepare onion potato tomato soup table."
Figure 38: Task for multi-agent dataset. The language goal for this graph is "Prepare a tomato cheeseburger one table and onion chicken sandwich on another table."
Figure 39: Task for the multi-agent dataset. The language goal for this graph is "Prepare two lettuce cheeseburgers separate tables."
26

---

Published as a conference paper at ICLR 2025
Figure 40: Task for the multi-agent dataset. The language goal for this graph is "Prepare a soup with potato, tomato, and chicken on one table and soup with potato, cheese, and onion another table." "
A.7 REACT ABLATIONS
ReAct in its original form can grow very expensive in cost long horizon tasks due to the increasing context size. We sought to perform early ablations of ReAct to find cost-effective variant whose performance is relatively the same. We first ablated on the types of feedback from feedback at all ("no-history") to ablating away components of the feedback from the last time step (where represents the last timestep with all feedback, wast-reassning-accie represents the last timestep with only the reasoning and action, and "last-action" represents the last timestep with only the last action. Next, we tested two different types of reasoning; one where we simply prompt ReAct to reason about the given information and another where make it provide a plan its sequence before outputting a single action (which we'v ve termed "mpe" after Model Predictive Control). From these ablations cosstreasoning-actie action-mpe" was the best performing and inexpensive as shown Table 4.
masstobb-rcasonin--actioo
small subset of data, determined that
Experiment
Accuracy (Tasks Solved)
Average Steps
Cost ($)
no-history
1/9
29.11
2.11
no-history-mpe
1/9
28,66
2.70
last-action
1/9
29.55
2.35
last-action-mpe
2/9
26,66
2.92
last-reasoning-action
1/9
28.88
2.46
lastrressoning--uttion-npe
3/9
28.33
2.64
last-obs-reasooningaccioo last-obs-reasooing-aatiion----
2/9
26.77
3.02
3/9
23.88
2.93
Table 4: Performance comparison across different ablations of ReAct. The variant using "last-
reasoning- action" and "mpe" ties for best performance but outperforms others terms of cost.
A.8 DIFFERENCES IN HORIZON PERFORMANCE
In Table 3 we observe that horizon length does not necessarily correlate with success. The main confounding variable is the quality of few-shot examples. Each dataset provides a single optimal few-shot example from a training task excluded from the testing set. This example is insufficient when the LLM agent makes mistake because it has not seen examples of incorporating state feedback to recover from failure. The LLM agent, therefore, acts in an open-loop manner.
In the synchronous dataset, Task 5 is more complex than Task 4, yet it has higher success rate. This because Task more aligned to the few-shot example, sharing a common sub-trajectory (i.c. stacking cheese). This similarity allows ReAct to stay within the distribution of the example, leading to fewer mistakes. contrast, Task deviates more from the example, resulting in ReAct making mistakes it cannot recover from.
Similarly, in the asynchronous dataset, we also observe that Task < Task < Task 3 despite having increasing complexity. Task and 3 more aligned to the few-shot example, sharing common
27

---

Published as a conference paper at ICLR 2025
sub-trajeed uub-trajectories (i.e. cutting veggies) expect the two perform at least as well as Task 1. We also expect some variance since we run our models with a temperature of 0.7; Tasks and are within standard error (30.0 13.8 for Task 2 versus 40.0 = 14.8 for Task 3) they perform similarly.
A.9 WHY IS ASYNCHRONOUS HARDER THAN SYNCHRONOUS?
The complexity of search for synchronous and asynchronous given the MDP in Section is:
1. Synchronous Case (d 0): No delays, so the planner operates in O(S |A])
2. Asynchronous Case (d > 0): Each delay expands the effective state space, yielding O([S) x (d + 1)" + [A)) complexity, where n the number of timers
Hence the expanded state space requires both conventional planner LLM based planner to reason over a larger range of delayed effects.
A.10 FAILURE MODE TAXONOMY DETAILS
Markov Decision Process To categorise the failure modes, used the Markov Decision Process (MDP), where there are main failure modes:
1. State failures
2. Action failures
3. Transition Function failures
4. Goal failures
We chose learn and understand the MDP of new enviornments, such as Robotouille. In using the MDP as system categorise failures, are better able to how the LLM bridges its knowledge of the real world to its understanding of new environments.
the MDP because LLMs know the MDP of the real world very well, but struggle to
State Failures A failure is categorised as a state failure when the agent misunderstands predicates in the state, and fails as result of this misunderstanding. For example, when preparing chicken cheese sandwich, the LLM agent may mistake the chicken to be already cooked, when is not. Even though the predicates are true the state, the agent misinterprets the predicates, causing take the wrong action and preventing it from achieving the goal successfully.
Item chicken2:
chicken2 is a chicken breast chicken2 can be cooked on a stove chicken2 is at stove4 chickens is directly top of stove4 chicken2 has nothing above it
Reasoning: The goal is to make an onion chicken sandwich on table. I can cook chicken while doing other tasks. Thus, will stack the ingredients from bottom to top as follows: table -> bottom bun -> chicken -> cheese bread.
First, will leave chicken1 cooking. chicken1 already cooked and in the sandwich.
2. The first ingredient is the bottom bun. I see bottombun1 on table3 with chicken1 top of it. I will leave bottombuni in place since it is already in the correct position.
3. The second ingredient is chicken. see chickenl stacked bottombunl. Since chickeni is already stacked on bottombunl, will leave it in place.
28

---

Published as a conference paper at ICLR 2025
4. The third ingredient is cheese. see cheesel table3. Since cheesel is dizectly on top of chickenl, I will leave it in place.
5. The fourth ingredient is bread. see bread2 on table3 and breadl held by robot1. need to stack bread1 top of cheesel to complete the sandwich.
Action:
Stack breadl on top of cheesel using robot1
Listing 1: Example of State failure: c_cheese_chicken___ sandwich, 252
Action failures failure is categorised by an action failure when the agent exceeds the number of steps and fails to complete the environment because it repeatedly tries to take an invalid action. Even thought the valid actions are listed the agent at each step, the agent may ignore the prompt and try to take another invalid action repeatedly. For example, when making potato soup, the agent tries to "transfer" the soup in the pot into a bowl it currently holding, although the correct action in the environment is pick up the pot and "pour" the soup into the bowl.
Valid Actions:
Move robot1 from stovel to sink1
Move robot1 from stovel to tablel
Move robotl from stovel to table2
Move robotl from stovel to fryerl
Move robot1 from stovel to boardl
Move robotl from stovel to fryer2
Move robotl from stovel to stove2
Move robot1 from stovel to table3
Do nothing
Goal: Make potato soup with a whole potato and serve into a bowl table.
ACTION PROPOSAL RESPONSE
Reasoning:
The goal is to make potato soup with whole potato and serve into a bowl on table. The steps required achieve this goal are:
1. Fill potl with water (done).
2. Boil the water in pot1 (done).
3. Add potatol to the boiling water in pot1 (done)
4. Serve the soup into bowll on a table.
Currently, potatol has been added to boiling water in potl, holding bowll which is empty.
and pot1 is at stovel. The next step is to transfer the soup from potl to bowll. Since I am already at stovel, will transfer the soup from potl to bowll.
Action: Transfer waterl and potatol from potl to bowll using robot1
ACTION PROPOSAL PROMPT
Error Feedback: The action r TTranffer waterl and potatol from pot1 to bowll using robot1' is not valid. Please provide a valid action.
29

---

Published as a conference paper at ICLR 2025
Listing 2: Example of an Action failure: 5 potato_ soup_ 126
Transition Function failure failure is categorised as transition function failure when the agent violates rule, even though the rules are included in the prompt to the agent. When the agent tries to plan for and perform actions that break the rule, if it unable recover, it will repeat transitions, causing it exceed the number of steps and fail to complete the task in the environment. For example, one of the rules in the environment that "A Station must contain a single Item to perform an action on it". When trying prepare onion soup, the agent may try to cut multiple onions together single cutting board at the same time. While this is possible the real world, is not allowed in our environment. This misunderstanding of the transition failure causes the agent to run out of steps.
Reasoning: The goal is to make onion soup with cut onions
and serve it into a bowl on a table. The steps to achieve this goal
follows:
Gather and cut the onions.
2. Place the cut onions into a pot with water.
Boil the pot with the onions.
4. Serve the soup into bowl on table.
Currently, I am holding onionl and need to cut it. Since I am at boardl, will stack onionl on top of onion2 to cut it on the cutting board.
Action: Stack onion1 top of onion2 using robot1
Listing Example of an Transition Function failure: 6_ onion_ soup_ 126
Goal failure failure categorised as a goal failure when the agent fails due misunderstanding of the goal, even though the goal is specified the agent. This may mean that the agent stacks the ingredients the wrong order, fail to prepare the ingredients before assembling the recipe, or include ingredients not included in the recipe. For example, when preparing cheese chicken sandwich, the agent may fail to cook the chicken before assembling the sandwich.
Reasoning: The goal is to make a cheese chicken sandwich on table. The ingredients need to be stacked from bottom to top as follows: table -> bread -> chicken -> cheese -> bread.
Given the current state:
1. I am holding chickeni at table3.
The base of the sandwich includes bread2 and bottombunl and is already correctly stacked on table3.
The next step is to stack the chicken on top the existing bottom bun and bread combination.
4. After the chicken, will need to stack cheese, which is on stove3.
5. The final ingredient is the top bun, which is not explicitly mentioned but can be assumed to be the topmost bread slice.
Therefore, the immediate action will be to stack chickenl on top of bottombunl, which is already table3.
Listing 4: Example of Goal failure: 0_ cheese___chheee whicceeensaawwviiieeee 252
Prioritising Failure Modes Sometimes, the agent may fail due to multiple reasons. For example, may violate rules and also misunderstand the goal. In such cases, choose the failure
30

---

Published as a conference paper at ICLR 2025
Figure 41: 0_ cheese_ chicken sandwich__ 84: All stoves are occupied, and agent naively follows rules, causing it to repeat transitions
mode that ultimately contributes to the goal. If it ultimately tries to perform actions based on misunderstanding of the state, causing it to fail, classify it as state failure. If it repeats transitions due to a misunderstanding of the valid actions in the state, we classify as an action failure.
The dominant failure modes in the datasets are transition function failures and goal failures, and there multiple environments where the agent seemingly fails to understand both the transition function and the goal. In this case, we refer to the following tiebreaker. If the agent misunderstands the goal but also violates rules, find the reason why the agent failed. In the case it violates rule and is unable to recover, we classify it as a transition function failure because it was unable to ultimately make any progress towards the goal, whether it was accurate or not. the agent was able to recover but failed due to a misunderstanding of the goal, we classify it as goal failure.
Another situation that is unclear is when the agent fails to prepare the ingredients before assembling the recipe. This could either be due to misunderstanding of the state, or because misunderstanding of the goal. If the agent reasons that the ingredients is already prepared when it is not, it is classified as a state failure. However, the agent does not reason about preparing the ingredient at all, then is classified goal failure.
A.11 QUALITATIVE PLANNING FAILURE EXAMPLE
To gain more insight into why LLM agents are unable to efficiently complete asynchronous tasks successfully, we created new baseline by repeating the rules the agent before every action. However, this caused the agent to sometimes be even more inefficient, as it naively tries to follow rules without proper planning-
In this example, the agent needs cook chicken on a stove, but all the stoves are currently occupied. It first follows the rule "A Station must contain single Item to perform action on it" and picks up the item from the stove. Then, it follows Since it is currently holding the item it does not need, and it wants to cook the chicken, it places the item back onto the stove to free its hands. This causes the agent to repeatedly pick up the item from the stove and place it back onto the stove. (Fig. 41)
rule "A Player can only hold single Item
time".
Reasoning: The goal is to make cheese chicken sandwich table. The sandwich will be stacked in the following order: table bread -> chicken cheese bread.
31

---

Published as a conference paper at ICLR 2025
1. The first ingredient, breadl, is already on table2 and will serve the base for the sandwich. I will leave it in place.
2. The second ingredient is chicken. I see chicken1 on table3. must cook chickenl before stacking it on breadl. stoved currently has bread3 on it, which is not needed for the sandwich. will pick up bread3 from stove4 to make space for cooking chicken1.
Action:
Pick up bread3 from stove4 using robot1
Reasoning:
The goal is to prepare cheese chicken sandwich a table. To achieve this, I need to stack the ingredients from bottom top as follows: table bread -> chicken cheese -> bread.
1. The first ingredient, breadl, is already on table2 and will serve as the base for the sandwich. will leave it place.
2. The second ingredient is chicken. see chickenl table3. I must cook chickenl before stacking it on breadl. stove4 is currently empty, will place bread3 there to free up my hands.
Action: Place bread3 on stove4 using robot.1
Listing 5: Log for 0_ cheese chicken sandwich 84
A.12 QUALITATIVE BAD START FAILURES
5_ double_ cheeseburger: 42 In this task, the agent misunderstands the goal from its very first line of reasoning. The goal is to make double cheeseburger on table, with bottom bun, cooked patty, cheese, cooked patty, cheese, and a top bun, stacked in that order. However, the agent misunderstands the goal and does not include of the ingredients, causing fail to complete the task.
Reasoning:
The goal is to make double cheeseburger on a table with the following stack: table patty -> cheese -> patty -> cheese.
1. The first ingredient is patty. see pattyl boardl and patty2 on table2. Since boardl is a cutting board and not table, will use patty2 table2 the base for the burger. I will move robot1 to table2 to pick up patty2.
Action: Move robot1 from tablel to table2
Listing 6: 5_ double_ cheeseburger 42
9_ onion_ cheese_ burger_ and_ lettuce_ tomato_ chicken sandwich_ 168 In this task, the agent correctly understands the ingredients needed for the two recipes and the order in which they should be stacked, but misunderstands the preparation of the ingredients, and does not register that it needs to first cut the onion, lettuce, and tomato. Thus, it does not include these preparations in its reasoning, and ultimately fails complete the task.
32

---

Published as a conference paper at ICLR 2025
Reasoning; The goal has two parts: prepare a burger with cheese and onions one table, and chicken sandwich with lettuce and tomato on another table.
For the burger with cheese and onions:
Bottom bun: bottombunl on tablel.
2. Onion: onionl on table3.
Cheese: cheesel on table2.
4. Patty: pattyl on fryerl.
Top bun:
topbun1 on boardl.
For the chicken sandwich with lettuce and tomato:
1. Bread: breadl held by robotl and bread2 on table4.
2. Chicken: chickenl on table8.
3. Lettuce: lettucel table5 lettuce2 table6.
4. Tomato: tomatol on sinkl.
St.es:
Move breadl (held by robotl) table4 to combine with
bread2.
Stack breadl on top of bread2 complete the bread part
the chicken sandwich.
3. Move robotl to table8 to pick up chicken1.
4. Move robotl to table4 to stack chicken1 on the bread. Move robotl to table5 or table6 to pick up lettucel or lettuce2.
6. Move robotl to table4 to stack lettuce on the chicken.
7
Move roboti to sinkl to pick up tomatol.
8 Move robotl to table4 to stack tomatol on the lettuce.
For the burger:
Move robotl to table2 to pick up cheesel.
2 Move robotl to tablel to stack cheesel on bottombunl.
3. Move robotl to table3 to pick up onionl.
4.
Move robotl to table1 to stack onionl on cheesel.
5 Move robot1 to fryer1 to pick up pattyl.
6. Move robotl to tablel to stack pattyl on onionl.
7.
Move robotl to boardl to pick up topbunl.
8.
Move robotl to tablel to stack topbunl pattyl.
Action: Stack bread1 on top of bread2 using robot1
Listing 7: 9_ onion_ cheese_ burger_ and_ lettuce tomato_ chicken_ sandwich_ 168
A. STOCHASTIC FAILURES
In our experiments we note that most successes have low repeated transitions while failures have high repeated transitions for both the synchronous and asynchronous datasets (Finding 5, Sec 4.2.3). While this implies that LLM agents aren't 't effective at following environment constraints, it also reveals a more general issue that LLMs cannot effectively incorporate feedback while generating text. We showcase this by introducing stochasticity into Robotouille; with 33% chance, cut item will revert to begin uncut a single time per environment seed. Table shows the results on synchronous tasks that involve cutting for gpt 4-o ReAcz our original deterministic setting and the stochastic setting. There a large drop in performance and we have qualitatively found that successes occur when the stochastic change occur immediately, allowing the agent continue cutting.
33

---

Published as a conference paper at ICLR 2025
Deterministic
Stochastic
Synchronous (%)
80.0
10.0
80.0
20.0
50,0
0.00
30.0
10.0
20.0
10.0
[10]
20.0
0.00
Total
56.00
1.00
Table 5: 4-t ReAct performance on a subset synchronous tasks with stochasticity.
A.14 TRANSITION FAILURE RECOVERY ANALYSIS
In this section, annotated for the transition failures on the synchronous and asynchronous datasets whether (I) the LLM agent recovers from a failure and (2) whether it repeats its mistake after recovering.
mistake occurs when the agent violates a rule at certain station for specific action. When the agent makes mistake, there 4 cases:
1. The agent violates a rule and is unable recover
2. The agent violates a rule at station for a specific action, but is able to recover. After recovery, they do not make any more mistakes; they do not repeat the mistake after recovering.
3. The agent violates rule at station, recovers, but is later repeats the mistake by trying to perform same action at the same type station. In this case, they repeat the mistake after recovering.
4. The agent violates a rule at a station, recovers, and does not repeat the mistake by trying to violate the same rule for the same action the same type of action. However, they violate the same rule for a different action at different type of station. In this case, we say that they do repeat their mistake.
On the synchronous dataset, the transition failures account for 32.1% (17) of the total failures. Of these failures, 58.8% (10) recovered from the mistake. Of the failures that recovered from their mistake, 90% (9) did not repeat the same mistake.
On the asynchronous dataset, the transition failures account for 58.5% (52) of the total failures. Of these failures, 40.4% (21) recovered from the mistake. Of the failures that recovered from their mistake, 57.1% (12) did not repeat the same mistake.
In the case where agent able to recover from a mistake, the agent may still fail to complete the task because they recovery process took too long and exhausted the step limit. Then, this failure would be categorised as Transition Function failure.
A.15 ADDITIONAL BASELINES FOR ASYNCHRONOUS PLANNING
We attempted to increase performance on the asynchronous dataset by benchmarking 2 new baselines. We introduced PLaG (BaG) Lin et al. (2024), which creates explicit graph representation of the task with an adjacency list. We adapt this method to multi-turn settings by making ReAct construct the graph representation at each step. We also introduce Reflexion Shinn al. (2023) by allowing ReAct attempts at an environment, keeping a reflection of the first failed attempt in context. We present results in Table 6.
34

---

Published as a conference paper at ICLR 2025
ReAct
PLaG (BaG)
Reflexion
Asynchronous (%)
20.0
20.0
30.0
30.0
30.0
50.0
40.0
20.0
40.0
10.0
30.0
10.0
0.00
10.0
10.0
6
10.0
20.0
30.0
7
0.00
0.00
0.00
8
0.00
0.00
0.00
9
0.00
0.00
0.00
[10]
0.00
0.00
0.00
Total
11.0
13.0
17.0
Table 6: gpt4-o performance on the asynchronous dataset over various baselines.
We observe that PLaG (BaG) achieves 2% performance increase over ReAct and Reflexion achieves a 6% performance increase over ReAct. We expected PLaG (BaG) to perform relatively similar to our ReAct. baseline because our few-shot examples for ReAct construct language graph representation for the task. Reflexion has a larger performance increase but at the cost of retrying runs which very expensive for long horizon tasks. These results highlight that future work should investigate how LLM agents can optimally represent asychronous tasks and cost-effective methods for incorporating feedback to recover from errors.
A.16 ADDITIONAL RESULTS FROM OPEN-SOURCE MODELS
We perform experiments on synchronous and asynchronous settings for top-performing open-source LLMs on the HuggingFace leaderboard with the ReAct baseline. The following experiments were run on NVIDIA RTX 6000 Adas using FP8 quantization.
Synchronous (%)
Asynchronous (%)
Qwcn2-723-Instruet
7.00
2.00
Qwcn2-323-Instruct
6.00
1.00
2.00
0.00
1.00
0.00
gemma-2-27b-it
0.00
0.00
gemma-2-9b-it
0.00
0.00
Table 7: Success rates of state-of-the-a open- source LLMs on the synchronous and asynchronous
datasets.
A.17 SYNCHRONOUS VARIANTS OF ASYNCHRONOUS TASKS
perform closer analysis of difficulty between the synchronous and asynchronous datasets by adapting the first 3 tasks of the asynchronous dataset to synchronous variants. We do this by making cooking instant by setting the time delay to O. The results in Table demonstrate that ReAct gpt performs better in the synchronous variants compared to the asynchronous setting.
35

---

Published as a conference paper at ICLR 2025
Synchronous (%)
Asynchronous (%)
50.0
20.0
60.0
30.0
50.0
40.0
Table 8: ReAct gpt -o performance 3 synchronous variant tasks for comparison.
36


Reviews:
[{"review_id": "OF5vJiRnVq", "reviewer": "Reviewer_qY1d", "summary": "This paper proposes a benchmark to evaluate LLMs’ planning ability, focusing in particular on their asynchronous planning capabilities. Here asynchronous means that the optimal solution is not to complete sub-tasks in a sequential manner. Rather, while “waiting for” some subtasks to complete, the agent should directly focus on other tasks. The benchmark contains 30 tasks, where existing LLMs suffer to perform well even with techniques such as chain-of-thought.", "questions": "Which components of asynchronous planning make it much harder than synchronous planning?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper proposes a benchmark for asynchronous planning based on an environment similar to overcooked.\n- The paper demonstrates that many existing LLMs fail short at planning problems that requires to consider time delays of sub-tasks.", "weaknesses": "- While this paper proposes a new benchmark for certain types of LLM reasoning tasks, it does not include sufficient experimental evaluation and analysis to highlight its main challenges. Specifically, while there are many LLMs as well as LLM-based planning algorithms to tackle planning problems, the paper only experimented with one LLM and two planning algorithms (CoT and ReAct). More baselines are needed to better illustrate the challenges posed by the proposed benchmark.\n\n- It is unclear from the paper which components of asynchronous planning make it much harder than synchronous planning. In the failure mode analysis, it is unclear to me what does it mean to attribute failure in terms of uncertainty over the MDP. Additionally, this categorization seems to be irrelevant to the key ingredient of the benchmark: *asynchronous* planning. A detailed analysis of why “asynchronous” planning is harder is needed to understand in what ways do this benchmark challenges the methods.\n\n- While the paper highlights that the benchmark requires long-horizon planning, the horizon counted by the paper is the number of required “atomic steps”, while the agent is performing high-level actions such as move an object to a place. This size of the graphs (e.g., in Figure 11) seems to be a better measure of the “planning depth”. Given this, it seems unclear what are the additionally challenges in this benchmarks compared to for example the AsyncHow dataset mentioned in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oxvFHtLuMd", "reviewer": "Reviewer_ZuBC", "summary": "This paper introduces ROBOTOUILLE, a challenging benchmark environment designed to evaluate the capabilities of large language model (LLM) agents in handling asynchronous, long-horizon, and multi-agent scenarios. Specifically, ROBOTOUILLE serves as a simulator for cooking various recipes, aiming to stress-test LLM agents. It utilizes domain and problem JSONs to define the Markov Decision Process (MDP) and the language description of the environment and tasks. By testing models such as gpt-4-o in both synchronous and asynchronous datasets, the authors demonstrate that agents face greater challenges in completing assigned tasks under asynchronous conditions. Additionally, the paper provides a thorough analysis of failure modes towards the end.", "questions": "1. The paper states that ROBOTOUILLE supports multi-agent environments by simply adding more players to the problem JSON. However, I did not see any related attempts or studies mentioned. Is this intended as a future research direction?\n\n2. Some results in the experiments struck me as peculiar. For instance, in Table 2, the Gemini model performs significantly better than ReAct using the I/O CoT method. What accounts for this discrepancy?\n\n3. Furthermore, in Table 3, Task 5 under synchronous conditions is more complex than Task 4, yet ReAct has a higher success rate. A similar situation occurs in the asynchronous setting. The paper does not provide a clear explanation for this phenomenon. What might be the underlying reasons?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. There is a notable gap in benchmarks for planning and decision-making tasks that involve asynchronous, long-horizon scenarios. The authors effectively compare their work to relevant literature, underscoring the significance of ROBOTOUILLE. Moreover, the cooking aspect of the tasks makes them relatable and easy to understand.\n\n2. By conducting experiments across two different settings, the authors identify key reasons for failure modes in the asynchronous decision-making context, such as the ineffectiveness of failure recovery strategies. This provides valuable directions for future research in asynchronous planning.\n\n3. The models used in the experiments represent the latest advancements in the field, showcasing the highest capabilities of current LLMs. Despite this, the agents still struggle to consistently complete asynchronous tasks, highlighting the relevance of the research direction proposed in the paper.\n\n4. The authors supply essential code and detailed implementation explanations, demonstrating that the experimental results are reproducible and persuasive.", "weaknesses": "1. The paper lacks a discussion on prompt design. The performance differences between the synchronous and asynchronous datasets may stem from variations in prompts, which often determine the practical limits of an agent's capabilities.\n\n2. Additionally, the tasks in the synchronous and asynchronous datasets differ, making it inappropriate to directly compare results from both settings during the analysis.\n\n3. If possible, I suggest including experimental results from some open-source models in the model list. While these results may not surpass those of proprietary models, they could encourage the open-source community to pay more attention to this research area.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gZ3oeXeR46", "reviewer": "Reviewer_nvj3", "summary": "This paper introduces Robotouille, a benchmark designed to evaluate the planning capabilities of LLMs in asynchronous, long-horizon, and multi-agent environments. Authors highlight a significant performance gap for SOTA approaches (e.g., GPT-4o+ReAct), showing success rates of 47% in synchronous tasks and only 11% in asynchronous ones. The benchmark includes datasets with varying levels of complexity, along with a thorough failure analysis, offering key insights into where and why current approaches fall short.", "questions": "* Line 366: Could you clarify why (0.5, 1.0] implies minimal progress? Wouldn’t a score of 0.5 indicate the solution is halfway there?\n\n* Line 520: I was surprised not to see value propagation and temporal difference learning listed under Feedback Incorporation techniques.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "+ Well-written with clear illustrations of domain complexities.\n+ Rigorous experimental design, featuring carefully curated datasets across multiple complexity levels and a detailed failure analysis.", "weaknesses": "* The paper can be split into two main sections: 1) introducing and baselining the benchmark and 2) analyzing results. While the first part is strong, insights in the second part are somewhat obscured. For instance, in Q6, the majority of both successful (72.7%) and failed (52.8%) trajectories prioritized subtask completion. Does this indicate that subtask prioritization may not be a critical area for improvement in planning? I encourage authors to capitalize more on their analysis.\n\n* The absence of stochastic elements in the environment and experimentation is notable. One of the significant challenges for LLM architectures lie in adapting to stochastic domains [1].\n\n* Although the paper initially emphasizes the multi-agent aspect of the environment, this is not reflected in the empirical results.\n\n**Minor Suggestions**\n\n* Include GAIA benchmark in your related work section (https://arxiv.org/abs/2311.12983).\n* Use vectorized image formats to ensure quality remains high when zooming.\n* Line 443: Add context to the caption: \"The median separates failures into runs with lower and higher repeated transitions, with quartiles representing the mean of these two groups.\"\n\n[1] David Brandfonbrener, Alberto Bietti, Jacob Buckman, Romain Laroche, and Joan Bruna. \"When does return-conditioned supervised learning work for offline reinforcement learning?\" In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL: https://openreview.net/forum?id=XByg4kotW5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)