Language Model Agents Suffer from Compositional Decision Making

We thank the reviewer for the thoughtful review and comments. Please let us know any remaining questions or concerns if you have.

> Questions 1

Thank you for your suggestion. We separated the details of finetuned language model agents, including data-rebalancing, as an independent section in the revised paper (Section 4.5).

> Questions 2

While tasks are visually simplified, we believe CombWoB reflects a broader spectrum of functionalities in real-world websites without sacrificing controllability. For example, the task in Figure 1 sketches the structure of a login form with agreement checkboxes and a pop-up window, like Internet banking. We also designed tasks with page transitions, such as from the login form to the email browser. Some of the recent works utilized unsupervised auto-curricula to adaptively design new tasks from a set of primitive base tasks using a teacher/student paradigm [1, 2]. While they can be useful for designing realistic websites, they still suffer from a limited set of base tasks and training instability in a multi-agent system.

> Questions 3

Real-world websites have dependencies between sub-tasks. For example, Gmail requires successful login to proceed to writing an email or reading social media posts of a specific user requires navigating to the personal page of that user. In CombWoB, we implemented these kinds of dependencies in the reward function using logical AND operations. For example, while we allowed agents to continue to “write an email” subtask without successful login, the agent would get zero rewards even if the “write an email” subtask is successful. We inform agents of these dependencies using connectors in instructions such as “solve Y after X” or “solve X then Y”. Our analysis in Section 6.4 also suggests that, in addition to task compositionality, long instructions and deep HTML sub-tree can lead to challenging tasks.

> Questions 4

The failure analysis in Table 3 has shown that language model agents fail to parse the instructions into the correct order. This can be because base-task demonstrations in the prompt just have "left-to-right" instructions from base MiniWoB tasks; strongly conditioning the LLM agents to process instructions in a linear order while compositionality could imply a non-linear processing of instructions. This mismatch between the prompt ("left-to-right") and inference tasks (mixing "left-to-right" and "right-to-left") could cause the performance drops.

> Questions 5

Following the recent work in deep reinforcement learning literature [3], we measured average performance as a proxy of oracle task solvability. If many kinds of agents perform poorly, such tasks are regarded as challenging. This can shed light on "task" or "environment", rather than "language model agents" or "prompting methods", while such an analysis has been overlooked so far. Additionally, we agree with the reviewer that a single statistic, such as average over the methods, might not reflect the nuances for each method. While the trend with average might be the same, distributional characteristics for each language model agent could be different. We extended our analysis by reporting the individual performances of each agent in Appendix J (Figure 8). Our results still indicate that while all the language model agents (HTML-T5++, RCI, AdaPlanner, Synapse) often show negative correlations between the success rate and instruction tokens or max subtree depth with statistical significance, the trends for other statistics may differ among the methods.

> Questions 6

We appreciate your pointing out the grammatical errors in our manuscript. We fixed these errors based on your suggestions in the revised paper.

[1] Gur et al., (2022) Environment Generation for Zero-Shot Compositional Reinforcement Learning (https://arxiv.org/abs/2201.08896)

[2] Sohn et al., (2022) Fast Inference and Transfer of Compositional Task Structures for Few-shot Task Generalization (https://arxiv.org/abs/2205.12648)

[3] Furuta et al., (2021) Policy Information Capacity: Information-Theoretic Measure for Task Complexity in Deep Reinforcement Learning (https://arxiv.org/abs/2103.12726).

We appreciate your careful reading and detailed discussion of our paper. We address your concerns below and please let us know if there are remaining questions or unclear points.

> Weaknesses 1 & Questions 1

We selected baseline LLM agents in our work based on their superior performance and novelty in using LLMs for web navigation problems. RCI [1] is the first to use prompting in a self-refinement loop, outperforming SL/RL agents on MiniWoB benchmark that requires millions of demonstrations to work. AdaPlanner [2] and Synapse [3] were the follow-up works outperforming RCI via code generation from environmental feedback or via well-designed decomposed prompts with retrieval.

Since we extensively studied these three reference models, we wanted to provide a detailed and to-the-point summary of these models so that it is easy to reason about their performance, shortcomings, and practicality. To improve readability, we shortened Section 4 by moving some of the content to the Appendix.

> Weaknesses 2 & Questions 2

MiniWoB has around 104 base tasks; all the two-way and three-way combinations of these tasks would give 185,460 compositional tasks. It is infeasible to manually curate all the two-way/three-way combinations. Unfortunately, it is also nontrivial to automate this process due to the locality of the environment implementations in MiniWoB. Each environment is mostly self-contained, making it nontrivial to modularize the whole benchmark/codebase so that every combination can be automatically generated. We decided to outline a set of design principles – solvability, feasibility, reality, etc. which we follow to manually curate 50 compositional tasks and 50 reverse-order instruction tasks that we believe cover a wide variety of difficulty, and compositionality. We believe these guiding principles would be applicable to other compositional generalization problems such as robotic navigation. We also believe that based on these design principles, our compositional benchmark can easily be extended in the future to study even more challenging and compositional web navigation problems.

We'd also like to highlight that, because previous works were tested around 50 - 60 MiniWoB tasks [1,2,3,4,5], 50 compositional tasks is a decent number of tasks to evaluate the agents. Our addition of 50 new compositional tasks doubles the number of tasks for the community to study.

> Weaknesses 3

Due to limited space, we had to carefully structure our paper. We wanted to make the main part to be as self-contained as possible while also giving more details in the appendix for clarification and reproducibility. We made some changes to include some of the details of data balancing and task difficulty estimation as a new section in the revised paper (Section 4.5). We explain how difficulty scores are estimated (Appendix D), or the ratio of tasks in the rebalanced dataset (Appendix E) in the appendix. Please let us know if you have any other concerns.

[1] Kim et al., (2023) Language Models can Solve Computer Tasks (https://arxiv.org/abs/2303.17491)

[2] Sun et al., (2023) AdaPlanner: Adaptive Planning from Feedback with Language Models (https://arxiv.org/abs/2305.16653) 

[3] Zheng et al., (2023) Synapse: Trajectory-as-Exemplar Prompting with Memory for Computer Control (https://arxiv.org/abs/2306.07863) 

[4] Gur et al., (2022) Understanding HTML with Large Language Models (https://arxiv.org/abs/2210.03945) 

[5] Furuta et al., (2023) Multimodal Web Navigation with Instruction-Finetuned Foundation Models (https://arxiv.org/abs/2305.11854) 

We appreciate the careful reading and thoughtful comments. We address your concerns below, and please let us know if there are remaining questions or unclear points.

> Weaknesses 1

We provided additional results with oracle demonstrations for compositional tasks in Appendix I (Figure 7). RCI with GPT-4 and oracle exemplars achieves 82.9% success rate averaged on 20 two-way tasks, which is the best among the methods (e.g. HTML-T5++: 73.9%, RCI with gpt-3.5-turbo: 46.9%, RCI with gpt-4: 71.5). This indicates that if a prompt includes how to perform on compositional tasks, the performance gets better. However, please keep in mind that providing exemplars for every compositional problem is infeasible given the huge space of problems and the cost of collecting examples for every one of them.

We thank the reviewer for the careful reading and constructive feedback. We address your concerns below and please let us know if you have further questions.

> Weaknesses 2

Thank you for your suggestions. We decided to change the title to Language Model Agents Suffer from Compositional Generalization in Web Automation in the final version. Since we intentionally distinguish the terminology of "language model agents" (prompting & pipeline) and "large language models" (model itself), we do not intend to argue "the model itself is harmed" in the title; in fact, we have compared different agent-prompting methods (RCI, AdaPlanner, Synapse) on the same LLMs (gpt-3.5-turbo/gpt-4). Please let us know if you have further concerns about the title.

> Weaknesses 1

We agree with the reviewer that many of the real-world tasks have inherent compositionality to some degree, including MiniWoB tasks. However, these tasks are not explicitly designed for compositionality, making it difficult to systematically investigate the generalization gap. For example, existing language model agents, that we also study in our paper, already achieve human-level performance on MiniWoB – more than 90% performance on almost all the tasks in MiniWoB. However, when these tasks are combined, their performance drops significantly – allowing us to analyze this gap using the difficulty of the base tasks themselves as well as the difficulty of the task compositions. Given that these agents already solve base tasks, we found it surprising that even the most capable GPT-4-based agents still struggle with task compositions while a fine-tuned T5-based model transfers better. We also added Parsel to related work (Section 2) in the revised paper.