2403.11322

# StateFlow: Enhancing LLM Task-Solving through State-Driven Workflows **Authors**: - Yiran Wu (Pennsylvania State University) - &Tianwei Yue - \ANDShaokun Zhang (Pennsylvania State University) - &Chi Wang (Microsoft Research Redmond) - &Qingyun Wu (Pennsylvania State University) Abstract It is a notable trend to use Large Language Models (LLMs) to tackle complex tasks, e.g., tasks that require a sequence of actions and dynamic interaction with tools and external environments. In this paper, we propose StateFlow, a novel LLM-based task-solving paradigm that conceptualizes complex task-solving processes as state machines. In StateFlow, we distinguish between “process grounding” (via state and state transitions) and “sub-task solving” (through actions within a state), enhancing control and interpretability of the task-solving procedure. A state represents the status of a running process. The transitions between states are controlled by heuristic rules or decisions made by the LLM, allowing for a dynamic and adaptive progression. Upon entering a state, a series of actions is executed, involving not only calling LLMs guided by different prompts, but also the utilization of external tools as needed. Our results show that StateFlow significantly enhances LLMs’ efficiency. For instance, StateFlow achieves 13% and 28% higher success rates compared to ReAct in InterCode SQL and ALFWorld benchmark, with 5 $×$ and 3 $×$ less cost respectively. We also show that StateFlow can be combined with iterative refining methods like Reflexion to further improve performance. 1 Introduction LLMs have increasingly been employed to solve complex, multi-step tasks. Specifically, they have been applied to tasks that require interactions with environments (Yang et al., 2023a; Yao et al., 2022a; Shridhar et al., 2020; Zelikman et al., 2022) and those tasks that can benefit from utilizing tools such as web search and code execution (Mialon et al., 2023; Wu et al., 2023b; Wang et al., 2023c). In approaching these tasks, there is typically a desired workflow, or plan of actions based on heuristics that could improve the efficiency of task solving (Kim et al., 2023; Wu et al., 2023a). A common practice in the context of LLMs, such as ReAct (Yao et al., 2022b) and the vast customization of GPTs, is to write a single prompt that instructs the models to follow a desired procedure to solve the task (Dohan et al., 2022). The LLM is called iteratively with the same instruction, along with previous actions and feedback from tools/environments. This relies on LLMs’ innate capability to determine the current task-solving status and perform subsequent actions autonomously. Despite the impressive abilities of LLMs, it is still unrealistic to expect LLMs to always judge the status of current progress correctly. It is also almost impossible to reliably track these judgments and their decisions of subsequent action trajectory. Given these considerations, we pose the research question: How can we exert more precise control and guidance over LLMs? In this paper, we propose StateFlow, a new framework that models LLM workflows as state machines. Finite State Machines (FSMs) (Mealy, 1955; Moore et al., 1956) are used as control systems to monitor practical applications, such as traffic light control (Wagner et al., 2006). A defined state machine is a model of behavior that decides what to do based on current status. A state represents one situation that the FSM might be in. Drawing from this concept, we want to use FSMs to model the task-solving process of LLMs. When using LLMs to solve a task with multiple steps, each step of the task-solving process can be mapped to a state. For example, to solve the InterCode (Yang et al., 2023a) SQL task, a desired procedure is to first gather information about the tables and columns in the database, then construct a query to retrieve required information, and finally verify the task is solved and end the process. We can convert this workflow to a set of states (See upper left of Figure 1). Within each state, we define a sequence of output functions, which will be called upon entering the state. The output functions would take in the context history and output a new context to be appended to the history, which can be a tool, an LLM with a specific instruction, or a prompter. Based on the current state and context history, the StateFlow model would determine the next state to transit to. The task-solving process progresses by transitioning through different states and calls to corresponding output functions, and ends until a final state is reached. Thus, StateFlow enhances control over the task-solving process and seamlessly integrates external tools and environments. <details> <summary>2403.11322v5/x1.png Details</summary>  ### Visual Description # Technical Document Extraction: Flowchart Analysis ## Legend - **Location**: Bottom-left quadrant - **Labels**: - `P`: Prompter (Gray) - `E`: Execution (Green) - `M_i`: LM with instruction `T_i` (Pink) ## SQL Task Flowchart ### Components 1. **Nodes**: - `Init` (Gray) - `Observe` (Green) - `Select` (Green) - `Verify` (Green) - `Submit` (Green) - `End` (Gray) - `Error` (Pink) 2. **Arrows**: - `Observe → Select` (Green) - `Select → Verify` (Green) - `Verify → Submit` (Green) - `Submit → End` (Green) - `Error → Select` (Pink, labeled `DESC`) - `Error → Verify` (Pink, labeled `SELECT`) 3. **Flow**: - `Init` → `Observe` → `Select` → `Verify` → `Submit` → `End` - Error handling: `Error` loops back to `Select` (via `DESC`) and `Verify` (via `SELECT`). ## Bash Task Flowchart ### Components 1. **Nodes**: - `Init` (Gray) - `Solve` (Green) - `Verify` (Green) - `Submit` (Green) - `End` (Gray) - `Error` (Pink) 2. **Arrows**: - `Init → Solve` (Green) - `Solve → Verify` (Green) - `Verify → Submit` (Green) - `Submit → End` (Green) - `Error → Solve` (Pink, loop) 3. **Flow**: - `Init` → `Solve` → `Verify` → `Submit` → `End` - Error handling: `Error` loops back to `Solve`. ## Diagonal Divider - A black diagonal line separates the SQL Task (top-left) and Bash Task (bottom-right) flowcharts. ## Spatial Grounding - **Legend Position**: Bottom-left quadrant (coordinates: [x=0, y=0] relative to diagram origin). - **Color Consistency**: - Gray nodes: `Init`, `End` (matches `P` in legend). - Green nodes: `Observe`, `Select`, `Verify`, `Submit`, `Solve` (matches `E` in legend). - Pink nodes: `Error` (matches `M_i` in legend). ## Key Trends - **SQL Task**: - Linear progression from `Init` to `End` with error recovery loops. - `Error` node introduces branching to `Select` and `Verify`. - **Bash Task**: - Simplified linear flow with a single error recovery loop to `Solve`. ## Notes - No numerical data or heatmap present; purely procedural flowchart. - All text is in English; no additional languages detected. </details> Figure 1: The StateFlow models for the SQL and Bash task. Init and End state are basic components of state machines, and states like Observe, Solve, Verify, Error can be adaptable across various tasks. When reaching a state, a sequence of output functions defined is executed (e.g., $\text{M}_{i}→\text{E}$ means to first call the model and then call the SQL/Bash execution). Execution outcomes are indicated by red arrows for failures and green for successes. Transition to different states is based on specific rules. For example, at a success ‘Submit’ command, the model transits to End state. We evaluate StateFlow on the SQL task and Bash task from the InterCode (Yang et al., 2023a) benchmark and the ALFWorld Benchmark (Shridhar et al., 2020). The results demonstrate the advantages of StateFlow over existing methods in terms of both effectiveness and efficiency. With GPT-3.5, StateFlow outperforms ReAct by 13% on InterCode SQL task and 28% on ALFWorld, with 5 $×$ and 3 $×$ less LLM inference cost respectively. StateFlow is orthogonal to methods that iteratively improve future attempts using feedback based on previous trials (Shinn et al., 2023; Madaan et al., 2024; Prasad et al., 2023). Notably, we show that StateFlow can be combined with Reflexion (Shinn et al., 2023), improving the success rate on ALFWorld from 84.3% to 94.8% after 6 iterations. Our main contributions are the following: (1) We introduce StateFlow, a paradigm that models LLM workflows as state machines, allowing better control and efficiency in LLM-driven task solving. We provide guidelines on how to build with the StateFlow framework and illustrate the building process through a case study. (2) We use three different tasks to illustrate the effectiveness and efficiency of StateFlow, with improvement in performance and a 3-5 $×$ cost reduction. We also perform an ablation study to provide deeper insights into how different states contribute to the performance of StateFlow. (3) We show that StateFlow can be combined with iterative refining methods to further improve performance. 2 Background Finite-state Machines We first introduce state machines, which we will use to formulate our framework. A finite state machine (automaton) is a mathematical model of a machine that accepts a set of words or string over an input alphabet $\Sigma$ (Hopcroft et al., 2001; Carroll & Long, 1989), where read of symbols would lead to state transitions. The automaton would determine whether the input is accepted or rejected. A basic Deterministic Finite-state Machine (DFSM) is a Deterministic Finite-state acceptor, usually used as a language recognizer that determines whether an input ends in an accept state. An acceptor is not suitable in our modeling of LLM generations, where we want to determine actions to be performed and produce outputs in between states. Instead, we base our model on a transducer finite-state machine, which is a sextuple $\langle\Sigma,\Gamma,\mathrm{S},\mathrm{s}_{0},\delta,\omega\rangle$ (Rich et al., 2008), where $\Sigma$ abd $\Gamma$ are the input and output alphabet (finite non-empty set of symbols), $S$ is a finite non-empty set of states, $\omega$ is the output function, $\mathrm{s}_{0}$ is the initial state, $\delta$ is the state transition function ( $\delta:S×\Sigma→ S$ ), and $F$ is the set of final states. 3 Methodology In this section, we first define the StateFlow model. We then provide a general guideline for constructing StateFlow model and illustrate with a detailed case study. 3.1 StateFlow In a finite state machine, a state carries information about the machine’s history, tracking how the state machine has reached the present situation (Wagner et al., 2006). It is feasible to conceptualize the task-solving process with LLMs as a state machine. Different from traditional FSMs, StateFlow doesn’t have the concept of input tape but solely depends on the context history, which is a cumulative record of all past interactions. StateFlow employs a set of instructions $T={T_{1},T_{2},..T_{i}}$ to guide the language model generation at different states. This is equivalent to constructing a set of LLM agents $p_{\theta}^{T_{i}}$ with a specific instruction $T_{i}$ . This dynamic prompting approach ensures that the language model receives the most relevant guidance at each state, improving its ability to focus on a specific step. Following the definition of finite state machines, we formulate a StateFlow model to be a sextuple $\langle\mathrm{S},\mathrm{s}_{0},\mathrm{F},\delta,\Gamma,\Omega\rangle$ and explain each of the components under the LLM scenario: States $\mathrm{S}$ A state encapsulates the current status of a running process, essentially an abstraction of the context history. Upon entering a state, a predefined set of actions is executed. For example, entering an error state implies the process encounters an issue, triggering the execution of predetermined error-handling actions. Initial state $\mathrm{s}_{0}$ The process begins at the initial state when receiving the input task/question. Final States $\mathrm{F}$ A set of final states when the process is terminated, which is a subset of $\mathrm{S}$ . Output $\Gamma$ We define $\Gamma$ to be an infinite set of messages (unit of text) consisting of prompts $P$ , language model responses $C$ , and feedback from tool/environment $O$ : $\Gamma=\{P,C,O\}$ , which represents all possible messages that can be generated within StateFlow. We further define context history to be $\Gamma^{*}$ , which is a list of messages that have been generated. $S×\Gamma^{*}$ could be view as a snapshot of a running StateFlow (Rich et al., 2008). Here we distinguish static prompts $P$ that will added to the context directly from instructions $T$ that are used upon calling an LM. Algorithm 1 StateFlow 0: task Q, max transitions M, model $\langle\mathrm{S},\mathrm{s}_{0},\mathrm{F},\delta,\Gamma,\Omega\rangle$ , we define $s.outputs$ to be list of functions $[\omega_{1},...,\omega_{i}]$ , $\omega_{i}∈\Omega$ for each $s∈ S$ 1: $\Gamma^{*}← Q$ 2: Counter $←$ 0 3: $s← s_{0}$ 4: while $s\not∈ F$ do 5: for $\omega$ in s.outputs do 6: do $\Gamma^{*}←\Gamma^{*}+\omega(\Gamma^{*})$ 7: end for 8: $s←\delta(s,\Gamma^{*})$ 9: return $s,\Gamma^{*}$ if Counter $≥$ M 10: end while 11: return $s,\Gamma^{*}$ State transition $\delta$ Based on the current state and context history, the transition function would determine which state to go to ( $\delta:S×\Gamma^{*}→ S$ ). This could mean string matching of the last input, for example, checking if ‘Error’ is in the message from code execution. We can also explicitly employ an LLM to check for conditions and determine what is the next state. Output Functions $\Omega$ Here we define $\Omega$ to be a set of output functions, where a function $\omega$ takes the whole context history and generates an output ( $\omega:\Gamma^{*}→\Gamma$ ). The output function can be an LLM, a tool call, or a prompter function that returns a static prompt (e.g., P, E and $\text{M}_{i}$ in Figure 1). The generated response will then be added to the context history. The process starts at $s_{0}$ when task $Q$ is appended to the context history $\Gamma^{*}$ and ends when reaching one of the final states (See Algorithm 1). We also use a counter that defines maximum turns of transitions to prevent infinite loops. The process returns the exit state and the whole context history in the end. 3.2 Deployment Guideline In this section, we provide guidelines for deploying StateFlow models, with reference to the case study discussed in Section 3.3. In general, StateFlow is designed for tasks that require a designated process to solve. Essentially, creating a state machine involves transforming abstract control flow or human reasoning into a formalized logical model, grounded in a comprehensive understanding of the task at hand. Defining States To define the states, we start with identifying an ideal workflow of a given task. A state should represent a distinct phase or step in the process, defined with enough granularity to capture key milestones and decision points. With the basic workflow in mind, we need to think about possible situations during the process. Specifically, handling failures is an important part of the state machine, where a Error state is commonly used to handle failures. A set of fine-grained states might lead to better control over a problem-solving process. For example, it is possible to identify different types of errors and use different ways to handle them, but this adds complexity in defining the model as a trade-off. Defining output functions Within each state, we need to define a set of outputs. In practice, we need to identify the set of tools we will use, and what instructions we should send to the LLM. For example, in the Solve state defined for the bash task, we first send an instruction that asks for a bash command, call the model, and then execute the bash command. This is a typical sequence of sending instructions to LLMs and then utilizing tools. Defining Transitions We identify two possible state transitions: 1. A static string matching with the LLM responses or tool executions. For example, the tool execution might return a specific string like ”execution failed”, which can be used to determine the transition. Also, it is common to instruct LLMs to follow a certain template to generate outputs, so we can extract strings from the response. 2. Use LLM for an explicit checking of the current status when previous context is too random to be used for string matching. For example, we can send the context history to a model to ask whether a given problem is solved. 3.3 A Case Study of StateFlow Design on SQL We use the SQL task from the InterCode (Yang et al., 2023a) benchmark to illustrate how to identify a workflow and convert it to a StateFlow model. The benchmark is evaluated with ReAct (Yao et al., 2022b), a few-shot prompting that requires annotations of example trajectories of actions, thoughts, and observations. These trajectories are human-crafted, and they reflect how one thinks is a good process to solve the problem. <details> <summary>2403.11322v5/x2.png Details</summary>  ### Visual Description # Technical Document Extraction: SQL Query Process ## Question **What are the names and grades for each high schooler?** --- ### Step-by-Step Analysis #### **Thought 1** - **Text**: "I should write a SQL command that selects the name and grade fields from a table about high schoolers." - **Action**: `execute[SELECT name, grade FROM high_schoolers]` - **Observation**: `Error: Table 'network_1.high_schoolers' doesn't exist` #### **Thought 2** - **Text**: "The high_schoolers table doesn't exist. I need to check what tables are available to use." - **Action**: `execute[SHOW TABLES]` - **Observation**: `[('friend',), ('highschooler',), ('likes',)]` #### **Thought 3** - **Text**: "There is a table called `highschooler`. I should check what information this table contains." - **Action**: `execute[DESC highschooler]` - **Observation**: `[('ID', ...), ('name', ...), ('grade', ...)]` #### **Thought 4** - **Text**: "I can now write a SQL command that answers the question." - **Action**: `execute[SELECT name, grade FROM highschooler]` - **Observation**: `[('John', 12), ('Haley', 10), ...]` #### **Thought 5** - **Text**: "The output contains the name and grade, answering the question. I can submit this as the answer." - **Action**: `submit` --- ### Key Observations 1. **Table Name Correction**: The initial query used `high_schoolers` (with underscore), but the correct table name is `highschooler` (without underscore). 2. **Column Structure**: The `highschooler` table contains columns: `ID`, `name`, and `grade`. 3. **Sample Data**: The final query returned names and grades, e.g., `('John', 12)`, `('Haley', 10)`. --- ### Conclusion The process involved debugging table existence, verifying schema, and executing a corrected SQL query to retrieve the required data. The final output successfully answers the question. </details> Figure 2: A ReAct few-shot example for the SQL task. From the example, we can abstract a general workflow to solve the problem. See Figure 2 for one ReAct trajectory for the SQL task: (1) the process starts with a ‘SELECT’ query and results in an error. (2) At an error, the next thought is to explore the tables, so the SHOW TABLES command is executed to retrieve all tables. (3) After getting the tables, the next step is to explore the ‘highschoolers’ table with the ‘DESC’ command. (4) With knowing what the table contains, the next thought is to use the select query to solve the question. (5) Finally, it confirms the output contains relevant info, and submits. The trajectory demonstrates what to do based on previous history, which is similar to state transitions in StateFlow. While the trajectory starts with a ‘SELECT’ query but results in an error, we believe a better workflow would be to first explore the tables and use the ‘SELECT’ command. Based on this, we construct the states to be: Init -> Observe -> Solve -> Verify -> End (See Figure 1). In each state, the model is instructed to perform a specific action. For example, we ask the model to submit if the task is verified in state Verify and explore tables at an error in state error. 4 Experiments 4.1 InterCode Benchmark We first experiment with 2 tasks from the InterCode benchmark (Yang et al., 2023a): (1) SQL: The InterCode-SQL adapts the Spider dataset for MySQL, containing 1034 task instances. For each task, a MySQL interpreter is set up with all relevant tables within a docker container. (2) Bash: The InterCode-Bash dataset has 200 task instances curated from the NL2Bash dataset. We use the same hyperparameters Zhang et al. (2023a; b; 2024b); Zheng et al. (2023) for both two benchmarks. Specifically, we allow a max of 10 rounds of interaction with the environment. We evaluate with OpenAI GPT-3.5-Turbo and GPT-4-Turbo (both with the 1106 version) and the temperature is set to 0. Baselines. We compare StateFlow with two prompting strategies used in the InterCode benchmark. (1) Plan & Solve (Wang et al., 2023b): A two-step prompting strategy to first ask the model to propose a plan and then execute it. (2) ReAct (Yao et al., 2022b): a few-shot prompting method that prompts the model to generate thoughts and actions. Additionally, since we observed an ideal workflow for the SQL task in Section 3.3, we edit the ReAct prompt used in the benchmark accordingly to see if it already improves performance, named ReAct_Refined, and evaluate it on the SQL task (See Table 19 and 20 for details). Metrics. We present metrics provided by the benchmark and we also report the LLM usage of each method. Success Rate (SR): a task is considered a success only if the reward is 1. Error Rate: percentage of commands that fails. Turns: number of interactions with the environment. Cost: the cost of calling an LLM API in US dollars. <details> <summary>2403.11322v5/x3.png Details</summary>  ### Visual Description # Technical Document Extraction: SQL Query Process Flowchart ## Diagram Overview The image depicts a **state transition diagram** for a SQL query execution process with error handling. The flowchart outlines steps from initialization to error resolution, including table observation, query formulation, verification, and termination. --- ### Key Components & Flow #### 1. **Init (Initialization)** - **Prompt**: "What is the money rank of the tallest poker player?" - **Action**: `execute[SHOW TABLES]` - **Execution Output**: Tables `('people', 'poker_player')` identified. - **State Transition**: `ALWAYS → Observe` #### 2. **Observe** - **Model Instruction (T1)**: Use `DESCRIBE [table_name]` or `DESC [table_name]` to understand table structure. - **Thought**: "I need to understand the structure of the 'poker_player' table." - **Action**: `execute[DESC poker_player]` - **Execution Output**: Columns `('Poker_Player_ID', 'People_ID', ...)`. - **State Transition**: `Last action is DESC → Solve` #### 3. **Solve** - **Model Instruction (T2)**: Formulate a SQL query to answer the problem. - **Thought**: "I should write a SQL command that selects the money rank of the tallest poker player." - **Action**: `execute[SELECT Money_Rank FROM poker_player ORDER BY Earnings DESC LIMIT 1]` - **Execution Output**: `(58.0,)` (Money Rank). - **State Transition**: `Last action is SELECT → Verify` #### 4. **Verify** - **Model Instruction (T3)**: Validate if the output answers the question. - **Thought**: "The output does not specifically address the tallest poker player... I need to modify..." - **Action**: `execute[SELECT Money_Rank FROM poker_player ORDER BY Earnings DESC, Height DESC LIMIT 1]` - **SQL Error**: `Unknown column 'Height' in 'order clause'`. - **State Transition**: `Last action is submit → End` #### 5. **Error Handling** - **Error Trigger**: Execution failure due to invalid column reference (`"Height"`). - **Model Instruction (T4)**: Read error message to diagnose issues. - **Thought**: "The error message indicates that the 'Height' column is not..." - **Action**: `execute[DESC people]` - **Execution Output**: Columns `('People_ID', 'Nationality', ...)`. - **State Transition**: `Last action is DESC → Solve` (retry cycle). #### 6. **End** - **Termination**: Process concludes after successful verification or error resolution. --- ### Diagram Flowchart ```mermaid graph TD Init --> Observe Observe --> Solve Solve --> Verify Verify --> End Error --> Observe Error --> Solve Error --> Verify ``` --- ### Textual Transcription #### Left Panel (Primary Flow) ``` Question: What is the money rank of the tallest poker player? Init Prompt: Thought: I should find out what tables are available. Action: execute[SHOW TABLES] Execution: [('people', 'poker_player')] State transition: ALWAYS → Observe Observe Model: Instruction (T1): Use DESCRIBE [table_name] or DESC [table_name] command... Thought: I need to understand the structure of the "poker_player" table... Action: execute[DESC poker_player] Execution: [('Poker_Player_ID', ...), ('People_ID', ...)] State transition: Last action is DESC → Solve Solve Model: Instruction (T2): Based on the understanding of the tables... Thought: I should write a SQL command that selects the money rank of the... Action: execute[SELECT Money_Rank FROM poker_player ORDER BY Earnings DESC LIMIT 1] Execution: [(58.0,)] State transition: Last action is SELECT → Verify Verify Model: Instruction (T3): Carefully check if the output answers the question... Thought: The output does not specifically address the tallest poker player... Action: execute[SELECT Money_Rank FROM poker_player ORDER BY Earnings DESC, Height DESC LIMIT 1] SQL: Observation: Error executing query: Unknown column 'Height' in 'order clause' State transition: Last action is submit → End ``` #### Right Panel (Error Handling) ``` Error Model: Instruction (T4): Please carefully read the error message... Thought: The error message indicates that the "Height" column is not... Action: execute[DESC people] SQL: Observation: [('People_ID', 'int', ...), ('Nationality', ...)] State transition: Last action is DESC → Solve State transition: 4 Last Execution Fails → Error State transition: 5 Last action is DESC → Solve State transition: 6 Last action is SELECT → Verify State transition: 7 Last action is submit → End ``` --- ### Notes - **Language**: All text is in English. - **Critical Data Points**: - SQL column names: `Poker_Player_ID`, `People_ID`, `Money_Rank`, `Earnings`, `Height`. - Error: `Unknown column 'Height' in 'order clause'`. - State transitions numbered 1–7 for process steps and error handling. - **Flow Logic**: The process iterates between `Observe`, `Solve`, and `Verify` until the query succeeds or errors are resolved. </details> Figure 3: An example of the StateFlow execution for the SQL task. In this example, StateFlow runs through all states to reach a final answer. StateFlow Setup. For both tasks, we prompt the model to generate thought and action at each turn. Each prompt consists of 3 components: (1) instruction: details of what the LLM should perform at the current state; (2) examples: partial thought or action steps from the ReAct examples as demonstrations; (3) response format: explain the thought-action template. These prompts are put in the system message of each LLM agent and are not visible to other agents. SQL: We construct 6 states for the SQL task (See Figure 1 and Section 3.3 for a case study). In Init, we always execute the ‘SHOW TABLES’ command. In state Observe, Solve, Verify, Error, when the execution output is an error string, we will transit to state Error. In any of states Solve, Verify, Error, a successful ‘DESC’ will transit to Solve; a successful ‘SELECT’ will transit to Verify. In Verify, we use LLM to self-evaluate, which is proven useful by Weng et al. (2022); Xie et al. (2023). Bash: For the bash task, we define a StateFlow model consists of 5 states Init, Solve, Verify, End, Error. The states are similar to SQL, and the transition only depends on whether the execution is successful or not (Figure 1). See details in Appendix A.1 | Plan & Solve ReAct ReAct_Refine | 47.68 50.68 57.74 | 4.31 5.58 5.47 | 12.5 16.3 3.82 | 2.38 17.7 18.1 | 56.19 60.16 57.93 | 5.39 5.26 5.01 | 1.79 3.87 2.49 | 44.7 147 141 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | StateFlow | 63.73 | 5.67 | 6.82 | 3.82 | 69.34 | 5.11 | 1.89 | 36.0 | Table 1: Evaluation of the Intercode SQL dataset with GPT-3.5 and GPT-4. Best metrics of each model is in Bold. Second-best is Underlined. Result and analysis on SQL On GPT-3.5, our refined ReAct version increases the success rate by 7% over the original ReAct prompt. But StateFlow can further improve over the refined version by 6%, with 5 $×$ less cost. We note that the big difference in cost mainly comes from the prompt token use. The ReAct prompt has 2043 tokens with 4 example trajectories, while the longest instruction from StateFlow has only 400 tokens. The LLM is called iteratively with the whole prompt, thus the difference in cost accumulates. Compared to Plan & Solve, StateFlow uses 1.6 $×$ more cost but improves the SR by 17%. ReAct_Refined and our methods follow a similar workflow and have low error rates. On GPT-4-Turbo, StateFlow can improve over ReAct by 10% in SR but has 3 $×$ less cost. We further look into results from different levels of difficulties and found that the success rate drops significantly for harder tasks (Details in Appendix A.2). StateFlow also shows a greater improvement over ReAct on hard and extra hard tasks, which often require complex joins across multiple tables. We found that state Error in StateFlow is crucial, as it is encountered in 20% of extra hard tasks compared to only 9% in easy tasks, highlighting its role in improving performance on challenging queries. Result and analysis on Bash. On the bash task, StateFlow outperforms other methods while efficiently interacting with the environment. Switching to GPT-4-Turbo has little effect on the methods, where the two baselines even suffer from a decrement in accuracy. While the success rate is low, the average reward is high as 0.8 (See Table 6 in Appendix). Our investigation shows that 58.5% of the bash tasks have a positive reward greater than 0.5, while only 0.5% of the failed tasks have a positive reward greater than 0 in the SQL task. This is because a bash task sometimes consists of two requests (retrieve information or configure a file), making it harder to completely solve a task. Please see more details and results in Appendix A.2 and A.3. | Plan & Solve ReAct StateFlow | 23.5 32.5 36.0 | 4.98 5.52 3.90 | 25.8 13.2 8.74 | 0.74 3.28 0.63 | 20.5 31.5 39.0 | 5.15 3.86 2.95 | 21.0 9.90 7.85 | 9.59 20.40 5.02 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | Table 2: Evaluation of the InterCode Bash dataset with GPT-3.5 and GPT-4. Best metrics of each model is in Bold. Second-best is Underlined. | StateFlow No_Verify No_Error | 63.73 62.28 58.80 | 5.67 5.18 5.72 | 6.82 5.96 11.6 | 3.82 3.68 4.05 | | --- | --- | --- | --- | --- | | No_Obsrve | 57.83 | 6.00 | 17.0 | 4.64 | Figure 4: Ablation of states on the InterCode SQL dataset with GPT-3.5-Turbo. Best metrics in Bold. Second-best is Underlined. Ablation of States. To understand how different states contribute to the accuracy in StateFlow, we perform additional ablations and analysis with the SQL task (See Table 4). (1) We remove the Observe state. Note that in the original prompt for state Solve, we also instruct the model to call ‘DESC’ if necessary, so the model can still explore tables, but not with an explicit state and instruction to perform this action. (2) We remove the error state and rely on the verify state to correct mistakes. (3) We remove the verify state and add a sentence in Solve to prompt the model to submit when finished. The table shows that removing any of the states results in a drop in performance. When Verify state is removed, StateFlow has the lowest cost and error rate, matching the idea that more corrections to the results will be performed with an explicit Verify state. Removal of the Error state leads to a drop of 5% in SR, and an increase in turns, error rate, and cost, showing that the Error state plays an important role in the workflow. Removal of the Observe results in the lowest SR and highest cost, showing that ‘Observe‘ is the most important state. 4.2 ALFWorld ALFWorld (Shridhar et al., 2020) is a synthetic text-based game implemented in the TextWorld environments (Côté et al., 2019). It contains 134 tasks across 6 distinct task types: move one or two objects (e.g., put one/two cellphone in sofa), clean/cool/heat an object (e.g., clean/cool/heat some apple and put it in sidetable) and examine an object with lamp (e.g., look at bowl under the desklamp). The agent is required to navigate around a household setting and manipulate objects through text actions (e.g., go to desk 1, take soapbar from toilet 1), and the environment will give textual feedback after each action. We experiment with GPT-3.5-Turbo (1106). For all experiments, we follow AutoGen (Wu et al., 2023a) to use the BLEU metric to map output to the valid action with the highest similarity. Our implementation is also based on AutoGen We use AutoGen v0.2.17.. More details are in Appendix B.1. <details> <summary>2403.11322v5/x4.png Details</summary>  ### Visual Description # Technical Document Extraction: Flowchart Analysis ## Diagram Overview The image depicts a state transition diagram for a task execution system with environmental interaction. The flowchart includes decision nodes, action nodes, error handling, and state transitions. All text is in English. --- ## Key Components and Flow ### 1. Initialization - **Node**: `Init` (Gray circle) - **Transition**: `Init → Plan` (Gray arrow) - **Purpose**: System startup ### 2. Planning Phase - **Node**: `Plan` (Light green circle) - **Transition**: `Plan → Pick` (Gray arrow) - **Instruction**: `M_i → E` (LM with instruction `T_i` to Environment) ### 3. Object Acquisition - **Node**: `Pick` (Light green circle) - **Self-loop**: `Pick → Pick` (Gray arrow) labeled `"Look"` - **Transition to Process**: `Pick → Process` (Green arrow) labeled `"Heat/Cool/Clean"` - **Transition to FindLamp**: `Pick → FindLamp` (Green arrow) labeled `"Look"` ### 4. Error Handling - **Node**: `Error` (Red circle) - **Transition**: `Pick → Error` (Red arrow) labeled `"Wrong Pick"` - **Transition**: `Error → Pick` (Gray arrow) ### 5. Processing Phase - **Node**: `Process` (Light green circle) - **Self-loop**: `Process → Process` (Gray arrow) - **Transition to Put**: `Process → Put` (Green arrow) labeled `"Processed"` ### 6. Object Utilization - **Node**: `FindLamp` (Light green circle) - **Transition**: `FindLamp → UseLamp` (Green arrow) labeled `"Found"` - **Self-loop**: `UseLamp → UseLamp` (Gray arrow) ### 7. Completion Phase - **Node**: `Put` (Light green circle) - **Transition**: `Put → End` (Green arrow) labeled `"Done"` - **Self-loop**: `Put → Put` (Gray arrow) ### 8. Termination - **Node**: `End` (Gray circle) - **Transition**: `End → Exit` (Gray arrow) --- ## Legend and Notation - **E**: Environment - **M_i**: LM with instruction `T_i` - **Transition Syntax**: `Source → Target` (Arrow color indicates transition type) - Gray: System flow - Green: Successful action - Red: Error condition --- ## Spatial Grounding - **Legend Position**: Bottom-left quadrant - **Node Colors**: - Gray: System states (`Init`, `End`) - Light Green: Operational states (`Plan`, `Pick`, `Process`, `Put`, `FindLamp`, `UseLamp`) - Red: Error state --- ## Flowchart Logic 1. **Normal Execution Path**: `Init → Plan → Pick → Process → Put → End` 2. **Alternative Paths**: - **Search Loop**: `Pick → FindLamp → UseLamp → Put` - **Error Recovery**: `Pick → Error → Pick` 3. **Conditional Transitions**: - `"Pick 2"` (Double object acquisition) - `"Heat/Cool/Clean"` (Environmental processing) --- ## Critical Observations 1. **State Persistence**: All operational nodes (`Plan`, `Pick`, etc.) maintain self-loops for iterative processing. 2. **Error Handling**: Explicit error state with dedicated transition from `Pick` node. 3. **Environmental Interaction**: All actions (`Pick`, `Process`, `UseLamp`) involve `M_i → E` transitions. 4. **Completion Criteria**: `"Done"` transition from `Put` node triggers system exit. --- ## Diagram Structure </details> Figure 5: The StateFlow model for ALFWorld. For Plan, we call the LLM directly. For other states (except Init and End), we first call LLM with an instruction and then call the environment to get feedback. In state Pick, when the correct object is picked, we transit to different states based on task type. For states Pick, Process, FindLamp, UseLamp, Put, we stay in the current state if the corresponding task is not completed, represented by gray semi-circle arrows. Baselines. We evaluate with: 1. ReAct (Yao et al., 2022b): We use the two-shot prompt from the ReAct. Note there is a specific prompt for each type of task. 2. ALFChat (2 agents) (Wu et al., 2023a): A two-agent system setting from AutoGen consisting of an assistant agent and an executor agent. ALFChat is based on ReAct, which modifies the ReAct prompt to follow a conversational manner. 3. ALFChat (3 agents): Based on the 2-agent system, it introduces a grounding agent to provide commonsense facts whenever the assistant outputs the same action three times in a row. | ReAct | 83.3 | 36.6 | 53.6 | 58.7 | 63 | 41.2 | 55.5 | 6.6 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | ALFChat (2 agents) | 87.5 | 60.2 | 44.9 | 65.1 | 38.9 | 43.1 | 58.2 | 6.9 | | ALFChat (3 agents) | 84.7 | 60.2 | 69.6 | 77.8 | 68.5 | 41.2 | 67.7 | 6.1 | | StateFlow | 91.7 | 83.9 | 85.5 | 79.4 | 92.6 | 62.7 | 83.3 | 2.6 | Table 3: Performance and cost of StateFlow and other methods on ALFWorld benchmark with GPT-3.5-Turbo. We report average success rate of 3 attempts. StateFlow Setup. The StateFlow model is shown in Figure 5. The process starts at Plan, where a plan to solve the task is generated. We note a similar planning is also used in the ReAct prompting. Then, we transit to Pick to instruct the model to search for the target object and take it. We stay in Pick until the target object is picked. We identify the target object by calling an LLM at the beginning and use it as ground truth. If a wrong object is picked, we go to the Pick_Error state, where the wrong object is put down. If the correct object is picked, we transit to the next state (Process, Put or FindLamp) based on the task type. We follow the ReAct template to prompt the model to generate thought and action each time. Also, we use task-specific planning examples and instructions in Plan and Process. See details in Appendix B.1. <details> <summary>2403.11322v5/x5.png Details</summary>  ### Visual Description # Technical Analysis of Dual-Line Charts ## Overview The image contains two line charts comparing performance metrics across iterations for two methodologies: **StateFlow + Reflexion** (red) and **ReAct + Reflexion** (blue). Both charts share the same x-axis (Iterations) but differ in y-axis metrics. --- ## Top Chart: Success Rate vs. Iterations ### Axes - **X-axis**: Iterations (0 to 6, integer increments) - **Y-axis**: Success Rate (0.5 to 1.0, decimal increments) ### Legend - **Location**: Top-right corner - **Labels**: - Red: StateFlow + Reflexion - Blue: ReAct + Reflexion ### Data Points | Iteration | StateFlow + Reflexion | ReAct + Reflexion | |-----------|-----------------------|-------------------| | 0 | 0.85 | 0.55 | | 1 | 0.89 | 0.63 | | 2 | 0.90 | 0.67 | | 3 | 0.92 | 0.68 | | 4 | 0.93 | 0.73 | | 5 | 0.95 | 0.75 | | 6 | 0.95 | 0.75 | ### Trends - **StateFlow + Reflexion**: Steady upward trend, plateauing at 0.95 by iteration 5. - **ReAct + Reflexion**: Gradual increase, reaching 0.75 by iteration 5 and stabilizing. --- ## Bottom Chart: Cumulative Cost vs. Iterations ### Axes - **X-axis**: Iterations (0 to 6, integer increments) - **Y-axis**: Cumulative Cost ($, 0 to 30, integer increments) ### Legend - **Location**: Bottom-right corner - **Labels**: - Red: StateFlow + Reflexion - Blue: ReAct + Reflexion ### Data Points | Iteration | StateFlow + Reflexion | ReAct + Reflexion | |-----------|-----------------------|-------------------| | 0 | $3 | $7 | | 1 | $4 | $11 | | 2 | $5 | $15 | | 3 | $6 | $19 | | 4 | $7 | $22 | | 5 | $8 | $25 | | 6 | $8.5 | $28 | ### Trends - **StateFlow + Reflexion**: Linear growth, ending at $8.5 by iteration 6. - **ReAct + Reflexion**: Steeper exponential growth, reaching $28 by iteration 6. --- ## Spatial Grounding & Validation 1. **Legend Accuracy**: - Red lines in both charts correspond to **StateFlow + Reflexion**. - Blue lines correspond to **ReAct + Reflexion**. 2. **Data Consistency**: - Top chart success rates align with legend labels. - Bottom chart costs match legend labels and trend descriptions. --- ## Key Observations 1. **Success Rate**: StateFlow + Reflexion consistently outperforms ReAct + Reflexion across all iterations. 2. **Cost Efficiency**: ReAct + Reflexion incurs significantly higher cumulative costs despite similar success rates in later iterations. 3. **Divergence**: By iteration 6, ReAct + Reflexion costs are **3.5x higher** than StateFlow + Reflexion ($28 vs. $8.5). --- ## Language Notes - **Primary Language**: English (all labels, axis titles, and legends are in English). - **No Additional Languages Detected**. </details> Figure 6: StateFlow and ReAct integrated with Reflexion. StateFlow can further be improved with Reflexion, with much less cost incurred than ReAct. Results and analysis. Table 3 shows the results for the ALFWorld benchmark. We record the accuracy for each type of task and also the cost for LLM inference. We can see that StateFlow achieves the best performance on all 6 tasks, and significantly outperforms all baseline methods on the whole dataset. It improves over ReAct by 28% and ALFChat (3 agents) by 15%. At the same time, StateFlow uses 2.5x less cost. With StateFlow, we decompose a long prompt into shorter but more concise prompts to be used when entering a state. Thus, we reduce the prompt tokens used while making the model focus on a sub-task for better responses. To understand the failure reasons of StateFlow, we analyzed all 23 failed tasks and classified them based on the ending state. The analysis revealed that 15 out of 21 tasks ended in the Pick state, indicating that finding the correct object is the most challenging part. The failures in the Pick state were due to three main reasons: the LLM hallucinating about the object’s location, picking the wrong object, and getting stuck in loops between locations. We refer to Appendix B.2 for more analysis of the results. In Appendix B.3, we show that further decomposition of the states in StateFlow can increase the success rate to 88.8%, with 15% less cost. Integration with Reflexion. We incorporate StateFlow with Reflexion (Shinn et al., 2023), showing that StateFlow can be combined with iterative refining methods to improve its performance. Reflexion reflects from previous unsuccessful trials and stores the feedback in memory for subsequent trials. We can either use ReAct or StateFlow as the basic executor. We run StateFlow +Reflexion and ReAct+Reflexion for 6 iterations, until both ReAct and StateFlow stop performance improvement. In Figure 6, StateFlow +Reflexion further improves from 84% to 94.8%, with the total cost increased from $2.9 to $8.6. While ReAct+Reflexion improves from 55.2% to 74.6%, the total cost for it increased from $7.1 to $27.9. 5 Related work Different prompting frameworks have been proposed to enhance LLM reasoning processes (Zhang et al., 2023d; Wu et al., 2022; Sel et al., 2023; Ning et al., 2023; Zhou et al., 2022; Zhang et al., 2023c; Zelikman et al., 2023). Tree of thoughts (ToTs) (Yao et al., 2023) models the reasoning process as a tree and employs DFS or BFS search to explore sequential thoughts. Tree-of-Thought by (Long, 2023) models the thoughts as trees but relies on a rule-based verifier to determine if a thought is valid and performs refining or backtracking based on a controller. Graph of Thoughts (Besta et al., 2023) models the process as a directed graph and defines 3 types of transformations at a node in the graph: aggregation, refining, and generation. These frameworks have better control over LLM’s intermediate steps, but they are not well-designed to consider LLM workflows with external tools and environments. StateFlow considers external feedback and also allows the design of complex patterns for more difficult tasks, where any state can be connected with the definition of state transitions. The step-wise search from ToTs (Yao et al., 2023) can easily be applied to StateFlow. When we call LLM in a state, we can generate several responses and employ an evaluator to select the best one. LLMs have been used to interact with environments (Deng et al., 2023; Yao et al., 2022a; Shridhar et al., 2020) and tools (Paranjape et al., 2023; Gou et al., 2023; Schick et al., 2023; Gao et al., 2023; Yang et al., 2023b; Zhang et al., 2024a; Zou et al., 2024). ReAct (Yao et al., 2022b) uses a few-shot prompting strategy that generates the next action based on past actions, and observations, which have been proven effective. Follow-up works employ iterative refining to improve from previous trials (Sun et al., 2024; Prasad et al., 2023). Reflexion (Shinn et al., 2023) and Self-Refine (Madaan et al., 2023) generate reflections from the past to improve future trials. In parallel to our work, Liu & Shuai (2023) adapts a state machine to record and learn from past trajectories. Extending from ToTs and RAP (Hao et al., 2023), (Zhou et al., 2023) proposes an LLM-based tree search incorporating reflection and feedback from the environment. These methods incur additional costs from the interactions or searching processes. StateFlow is orthogonal to these methods, and some of them can be used on top of StateFlow to further improve performance. LLMs are becoming a promising foundation for developing autonomous agents (Xi et al., 2023; Wang et al., 2023a; Wu et al., 2023a; Li et al., 2023; Hong et al., 2023; Sumers et al., 2023). AutoGen (Wu et al., 2023a) offers an open-source platform for developing LLM-based agents. MetaGPT (Hong et al., 2023) proposes a multi-agent framework for software development and CAMEL (Li et al., 2023) proposes a framework for autonomous agent cooperation. In StateFlow, specialized agents with different instructions are used in different states. 6 Conclusion In this paper, we propose StateFlow, a novel problem-solving framework to use LLMs for complex, multi-step tasks with enhanced efficiency and control. StateFlow grounds the progress of task-solving with states and transitions, ensuring clear tracking and management of LLMs’ responses and external feedback. We can define a sequence of actions within each state to solve a sub-task. StateFlow requires humans to have a good understanding of a given task and build the model and prompts. An intriguing avenue for further research lies in the automation of StateFlow model construction and prompting writing, leveraging LLMs to dynamically generate and refine workflows. Further, the idea of employing active learning strategies to iteratively adjust or ”train” a StateFlow, adding or removing states automatically based on task performance, presents a promising path toward maximizing efficiency and adaptability in complex task solving. Acknowledgements We would like to thank Hanjun Dai and Eric Zelikman for their reviews and helpful feedback. We also thank Yu Tong (Tiffany) Ling from MathGPTPro for her help in creating demonstration figures. References - Besta et al. (2023) Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint arXiv:2308.09687, 2023. - Carroll & Long (1989) John Carroll and Darrell Long. Theory of finite automata with an introduction to formal languages. 1989. - Côté et al. (2019) Marc-Alexandre Côté, Akos Kádár, Xingdi Yuan, Ben Kybartas, Tavian Barnes, Emery Fine, James Moore, Matthew Hausknecht, Layla El Asri, Mahmoud Adada, et al. Textworld: A learning environment for text-based games. In Computer Games: 7th Workshop, CGW 2018, Held in Conjunction with the 27th International Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, July 13, 2018, Revised Selected Papers 7, pp. 41–75. Springer, 2019. - Deng et al. (2023) Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens, Boshi Wang, Huan Sun, and Yu Su. Mind2web: Towards a generalist agent for the web. arXiv preprint arXiv:2306.06070, 2023. - Dohan et al. (2022) David Dohan, Winnie Xu, Aitor Lewkowycz, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski, Rif A Saurous, Jascha Sohl-Dickstein, et al. Language model cascades. arXiv preprint arXiv:2207.10342, 2022. - Gao et al. (2023) Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval-augmented generation for large language models: A survey. arXiv preprint arXiv:2312.10997, 2023. - Gou et al. (2023) Zhibin Gou, Zhihong Shao, Yeyun Gong, Yelong Shen, Yujiu Yang, Nan Duan, and Weizhu Chen. Critic: Large language models can self-correct with tool-interactive critiquing. arXiv preprint arXiv:2305.11738, 2023. - Hao et al. (2023) Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14992, 2023. - Hong et al. (2023) Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Jinlin Wang, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, et al. Metagpt: Meta programming for multi-agent collaborative framework. arXiv preprint arXiv:2308.00352, 2023. - Hopcroft et al. (2001) John E Hopcroft, Rajeev Motwani, and Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(1):60–65, 2001. - Kim et al. (2023) Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks. arXiv preprint arXiv:2303.17491, 2023. - Li et al. (2023) Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Communicative agents for ”mind” exploration of large scale language model society, 2023. - Liu & Shuai (2023) Jia Liu and Jie Shuai. Smot: Think in state machine. arXiv preprint arXiv:2312.17445, 2023. - Long (2023) Jieyi Long. Large language model guided tree-of-thought. arXiv preprint arXiv:2305.08291, 2023. - Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651, 2023. - Madaan et al. (2024) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems, 36, 2024. - Mealy (1955) George H Mealy. A method for synthesizing sequential circuits. The Bell System Technical Journal, 34(5):1045–1079, 1955. - Mialon et al. (2023) Grégoire Mialon, Roberto Dessì, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi-Yu, Asli Celikyilmaz, et al. Augmented language models: a survey. arXiv preprint arXiv:2302.07842, 2023. - Moore et al. (1956) Edward F Moore et al. Gedanken-experiments on sequential machines. Automata studies, 34:129–153, 1956. - Ning et al. (2023) Xuefei Ning, Zinan Lin, Zixuan Zhou, Huazhong Yang, and Yu Wang. Skeleton-of-thought: Large language models can do parallel decoding. arXiv preprint arXiv:2307.15337, 2023. - Paranjape et al. (2023) Bhargavi Paranjape, Scott Lundberg, Sameer Singh, Hannaneh Hajishirzi, Luke Zettlemoyer, and Marco Tulio Ribeiro. Art: Automatic multi-step reasoning and tool-use for large language models. arXiv preprint arXiv:2303.09014, 2023. - Prasad et al. (2023) Archiki Prasad, Alexander Koller, Mareike Hartmann, Peter Clark, Ashish Sabharwal, Mohit Bansal, and Tushar Khot. Adapt: As-needed decomposition and planning with language models. arXiv preprint arXiv:2311.05772, 2023. - Rich et al. (2008) Elaine Rich et al. Automata, computability and complexity: theory and applications. Pearson Prentice Hall Upper Saddle River, 2008. - Schick et al. (2023) Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.04761, 2023. - Sel et al. (2023) Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Lu Wang, Ruoxi Jia, and Ming Jin. Algorithm of thoughts: Enhancing exploration of ideas in large language models. arXiv preprint arXiv:2308.10379, 2023. - Shinn et al. (2023) Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303.11366, 2023. - Shridhar et al. (2020) Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint arXiv:2010.03768, 2020. - Sumers et al. (2023) Theodore R Sumers, Shunyu Yao, Karthik Narasimhan, and Thomas L Griffiths. Cognitive architectures for language agents. arXiv preprint arXiv:2309.02427, 2023. - Sun et al. (2024) Haotian Sun, Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models. Advances in Neural Information Processing Systems, 36, 2024. - Wagner et al. (2006) Ferdinand Wagner, Ruedi Schmuki, Thomas Wagner, and Peter Wolstenholme. Modeling software with finite state machines: a practical approach. CRC Press, 2006. - Wang et al. (2023a) Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al. A survey on large language model based autonomous agents. arXiv preprint arXiv:2308.11432, 2023a. - Wang et al. (2023b) Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. arXiv preprint arXiv:2305.04091, 2023b. - Wang et al. (2023c) Xingyao Wang, Zihan Wang, Jiateng Liu, Yangyi Chen, Lifan Yuan, Hao Peng, and Heng Ji. Mint: Evaluating llms in multi-turn interaction with tools and language feedback. arXiv preprint arXiv:2309.10691, 2023c. - Weng et al. (2022) Yixuan Weng, Minjun Zhu, Shizhu He, Kang Liu, and Jun Zhao. Large language models are reasoners with self-verification. arXiv preprint arXiv:2212.09561, 2022. - Wu et al. (2023a) Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen llm applications via multi-agent conversation framework. arXiv preprint arXiv:2308.08155, 2023a. - Wu et al. (2022) Tongshuang Wu, Ellen Jiang, Aaron Donsbach, Jeff Gray, Alejandra Molina, Michael Terry, and Carrie J Cai. Promptchainer: Chaining large language model prompts through visual programming. In CHI Conference on Human Factors in Computing Systems Extended Abstracts, pp. 1–10, 2022. - Wu et al. (2023b) Yiran Wu, Feiran Jia, Shaokun Zhang, Qingyun Wu, Hangyu Li, Erkang Zhu, Yue Wang, Yin Tat Lee, Richard Peng, and Chi Wang. An empirical study on challenging math problem solving with gpt-4. arXiv preprint arXiv:2306.01337, 2023b. - Xi et al. (2023) Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07864, 2023. - Xie et al. (2023) Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, and Qizhe Xie. Self-evaluation guided beam search for reasoning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. - Yang et al. (2023a) John Yang, Akshara Prabhakar, Karthik Narasimhan, and Shunyu Yao. Intercode: Standardizing and benchmarking interactive coding with execution feedback. arXiv preprint arXiv:2306.14898, 2023a. - Yang et al. (2023b) Kaiyu Yang, Aidan M Swope, Alex Gu, Rahul Chalamala, Peiyang Song, Shixing Yu, Saad Godil, Ryan Prenger, and Anima Anandkumar. Leandojo: Theorem proving with retrieval-augmented language models. arXiv preprint arXiv:2306.15626, 2023b. - Yao et al. (2022a) Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. Advances in Neural Information Processing Systems, 35:20744–20757, 2022a. - Yao et al. (2022b) 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, 2022b. - Yao et al. (2023) 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. arXiv preprint arXiv:2305.10601, 2023. - Zelikman et al. (2022) Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476–15488, 2022. - Zelikman et al. (2023) Eric Zelikman, Eliana Lorch, Lester Mackey, and Adam Tauman Kalai. Self-taught optimizer (stop): Recursively self-improving code generation. arXiv preprint arXiv:2310.02304, 2023. - Zhang et al. (2023a) Shaokun Zhang, Feiran Jia, Chi Wang, and Qingyun Wu. Targeted hyperparameter optimization with lexicographic preferences over multiple objectives. In The Eleventh international conference on learning representations, 2023a. - Zhang et al. (2023b) Shaokun Zhang, Yiran Wu, Zhonghua Zheng, Qingyun Wu, and Chi Wang. Hypertime: Hyperparameter optimization for combating temporal distribution shifts. arXiv preprint arXiv:2305.18421, 2023b. - Zhang et al. (2023c) Shaokun Zhang, Xiaobo Xia, Zhaoqing Wang, Ling-Hao Chen, Jiale Liu, Qingyun Wu, and Tongliang Liu. Ideal: Influence-driven selective annotations empower in-context learners in large language models. arXiv preprint arXiv:2310.10873, 2023c. - Zhang et al. (2024a) Shaokun Zhang, Jieyu Zhang, Jiale Liu, Linxin Song, Chi Wang, Ranjay Krishna, and Qingyun Wu. Training language model agents without modifying language models. arXiv preprint arXiv:2402.11359, 2024a. - Zhang et al. (2024b) Shaokun Zhang, Xiawu Zheng, Guilin Li, Chenyi Yang, Yuchao Li, Yan Wang, Fei Chao, Mengdi Wang, Shen Li, and Rongrong Ji. You only compress once: Towards effective and elastic bert compression via exploit-explore stochastic nature gradient. Neurocomputing, pp. 128140, 2024b. - Zhang et al. (2023d) Yifan Zhang, Jingqin Yang, Yang Yuan, and Andrew Chi-Chih Yao. Cumulative reasoning with large language models. arXiv preprint arXiv:2308.04371, 2023d. - Zheng et al. (2023) Xiawu Zheng, Chenyi Yang, Shaokun Zhang, Yan Wang, Baochang Zhang, Yongjian Wu, Yunsheng Wu, Ling Shao, and Rongrong Ji. Ddpnas: Efficient neural architecture search via dynamic distribution pruning. International Journal of Computer Vision, 131(5):1234–1249, 2023. - Zhou et al. (2023) Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406, 2023. - Zhou et al. (2022) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Olivier Bousquet, Quoc Le, and Ed Chi. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625, 2022. - Zou et al. (2024) Wei Zou, Runpeng Geng, Binghui Wang, and Jinyuan Jia. Poisonedrag: Knowledge poisoning attacks to retrieval-augmented generation of large language models. arXiv preprint arXiv:2402.07867, 2024. Appendix A InterCode A.1 Experiment Details For ReAct and Plan & Solve, we use the code from InterCode repository https://github.com/princeton-nlp/intercode. The StateFlow models for the ablation study on the InterCode SQL task are in Figure 9 and the full metrics for the ablation study are shown in Table 7. See Figure 10 for a bash example with StateFlow. We include also two examples of ReAct and ReAct_Refined in Table 19 and 20 for comparison. For the InterCode benchmark, we recorded different metrics provided by the benchmark and we also recorded the LLM usage of each method. Additional metrics: (1) Reward: For SQL, the reward is calculated by Intersection over Union (IoU) of the latest execution output generated against the gold output. For Bash, a customized function is used to evaluate the performance against file system modifications and the latest execution output. (2) Token Count: We also recorded the prompt tokens (input), and completion tokens (output) used by each method. See Table 5 and Table 6 for detailed comparisons. See Table 15 and 16 for the instructions used for SQL StateFlow model and Table 17 and 18 for instructions used for Bash. A uniform prompt that introduces the overall environment is put in the system message, and a specific prompt is put in the head of the user message. Code is available at https://github.com/yiranwu0/StateFlow. A.2 Additional Analysis The additional analysis below is based on results with the GPT-3.5-Turbo model. SQL. The SQL dataset consists of different levels of difficulties (See Table 4). The success rate drops with harder tasks, and the difference in SR between easy and extra hard tasks is as great as 50% with StateFlow. Harder queries usually pose several constraints on the data and require looking across tables and joining information from them (Extra hard example: “Which distinctive models are produced by maker with the full name General Motors or weighing more than 3500?”. Easy example: “Give the city and country of the Alton airport.”). However, StateFlow greatly improves over other baselines on hard and extra tasks, leading to 20% improvement compared to ReAct. Since harder tasks require information across tables, they are more likely to result in errors. We collected the states traversed for tasks that are solved successfully, and found that only 9% of the easy tasks go over state Error, while 20% of the extra hard tasks have state Error visited. This indicates that the state Error in StateFlow plays an important role in the performance gain in hard tasks. | Plan & Solve ReAct ReAct_Refined | 80.6 72.2 77.0 | 49.1 57.6 66.1 | 29.1 35.6 44.8 | 13.2 15.7 19.9 | 47.7 50.7 57.7 | | --- | --- | --- | --- | --- | --- | | StateFlow | 87.9 | 62.9 | 59.8 | 36.7 | 63.7 | Table 4: Success Rate of different level of difficulties on InterCode SQL with GPT-3.5-Turbo. Bash A Bash task consists of one or both of the following two requests: 1. retrieving information that can be acquired through output (e.g, “find files in /workspace directory which are modified 30 days ago”) and 2. changing configuration of a file/folder (e.g., “change permissions for all PHP files under the /testbed directory tree to 755”) (Yang et al., 2023a). To complete a Bash task, all required commands need to be correct, making it difficult to achieve a reward of 1. We collect the rewards from the failed bash tasks of StateFlow and find that 58.5% of the bash tasks have a positive reward greater than 0.5. For SQL, only 0.5% of the failed tasks have a positive reward greater than 0. This shows that many of the tasks are partly solved. In Section A.3, the results of “Try Again” show that signals from the environment are very useful and help the model understand how much process it has made to solve the task. Currently, our StateFlow model designed for bash follows a simple workflow of solve $→$ verify. However, since the bash task consists of two distinct requests as mentioned, we believe it is possible to improve the performance with a more complex StateFlow model, with different states constructed for each request. A.3 Additional Results SF_Chat We present the results of SF_Chat, an alternative version of StateFlow, in Table 5 and 6. Instead of creating individual LLM agents with specific instructions, we directly append that instruction to context history, imitating a user’s reply in a conversation. For this alternative, we construct the context history in a conversational manner. The observations and instructions are appended as user messages, and replies from models are appended as assistant messages. We can see that SF_Chat has a similar performance to StateFlow. By directly appending the instructions, SF_Chat takes fewer turns to finish the task and has a lower error rate than StateFlow. In trade-off, the cost of SF_Chat is higher. We note that SF_Chat might not be suitable for tasks that require many turns of interactions (e.g., ALFWorld), because the cost would be high with the instruction prompts accumulated in the context history. | | | SR | Reward | Turns | Error | Cost | Average | Average | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | % $\uparrow$ | $\uparrow$ | $\downarrow$ | % $\downarrow$ | $ $\downarrow$ | p-token $\downarrow$ | c-token $\downarrow$ | | | | GPT-3.5 | Plan & Solve | 47.68 | 0.4893 | 4.31 | 12.46 | 2.38 | 1998 | 154 | | ReAct | 50.68 | 0.5257 | 5.58 | 16.33 | 17.73 | 16456 | 348 | | | ReAct_Refined | 57.74 | 0.5928 | 5.47 | 3.82 | 18.05 | 16782 | 340 | | | Try Again ∗ | 56.38 | 0.5762 | 7.62 | 34.73 | 6.61 | 6098 | 145 | | | StateFlow | 63.73 | 0.6637 | 5.67 | 6.82 | 3.82 | 3128 | 281 | | | SF_Chat | 60.83 | 0.6356 | 5.38 | 5.01 | 5.59 | 4965 | 220 | | | GPT-4 | Plan & Solve | 56.19 | 0.5793 | 5.39 | 1.79 | 44.7 | 3065 | 416 | | ReAct | 60.16 | 0.6277 | 5.26 | 3.87 | 147 | 12951 | 419 | | | ReAct_Refined | 57.93 | 0.6104 | 5.01 | 2.49 | 141 | 12377 | 421 | | | StateFlow | 69.34 | 0.7223 | 5.11 | 1.89 | 36.0 | 2700 | 261 | | | SF_Chat | 70.41 | 0.7329 | 4.84 | 1.20 | 49.2 | 3907 | 283 | | Table 5: Results of the Intercode SQL with GPT-3.5 and GPT-4 with all metrics. We also include SF_Chat, an alternative of StateFlow, and another baseline Try Again with an oracle setting(∗). Best metrics of each model is in Bold. Second-best is Underlined. | | | SR | Reward | Turns | Error | Cost | Average | Average | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | % $\uparrow$ | $\uparrow$ | $\downarrow$ | % $\downarrow$ | $ $\downarrow$ | p-token $\downarrow$ | c-token $\downarrow$ | | | | GPT-3.5 | ReAct | 32.5 | 0.7674 | 5.52 | 13.23 | 3.28 | 15529 | 442 | | Plan & Solve | 23.5 | 0.7472 | 4.98 | 25.78 | 0.74 | 3232 | 225 | | | Try Again ∗ | 49.5 | 0.8453 | 6.88 | 19.54 | 0.83 | 3833 | 159 | | | StateFlow | 36.0 | 0.8033 | 3.90 | 8.74 | 0.63 | 2667 | 232 | | | SF_Chat | 37.0 | 0.8011 | 3.04 | 9.95 | 0.79 | 3658 | 148 | | | GPT-4 | ReAct | 31.5 | 0.7724 | 3.86 | 9.90 | 20.40 | 9027 | 392 | | Plan & Solve | 20.5 | 0.7280 | 5.15 | 21.03 | 9.59 | 3460 | 444 | | | StateFlow | 39.0 | 0.8059 | 2.95 | 7.85 | 5.02 | 1835 | 225 | | | SF_Chat | 37.5 | 0.8015 | 2.86 | 7.27 | 7.04 | 3113 | 135 | | Table 6: Results of the Intercode Bash with GPT-3.5 and GPT-4 with all metrics. We also include SF_Chat, an alternative of StateFlow, and another baseline Try Again with an oracle setting(∗). Try Again We also include results of another baseline “Try Again” from InterCode Benchmark with GPT-3.5-Turbo. Try Again is an iterative feedback setup from InterCode to mimic human software development (Yang et al., 2023a). In this setup, the model can receive a ground-truth reward from the environment at each execution of the command and stops when the task is solved correctly or reaches max turns. Then the max reward from all the executions is retrieved. We note that this is an oracle setting not used in StateFlow and other baselines. In our setting, we use the model to determine when to stop and submit the answer, and only the result before submission is evaluated. From Table 5, we can see that Try Again doesn’t work well in the SQL task, and that the performance is slightly worse than our refined version of ReAct. It also has a high error rate of 34.73%. However, with the bash task, Try Again significantly outperforms other methods. This discrepancy indicates the difference in the nature of the two tasks. In the SQL task, the reward is mostly 0 or 1. The observation commands such as ”DESC” and a wrong ”SELECT” command receive 0, and there are only a few cases where the ”SELECT” command is partially correct to receive a partial reward. In this case, the reward signal is not very useful. However, the bash tasks from InterCode are explicitly selected with utilities $≥$ 4 (require several commands), and each correct command can receive a partial reward. Thus, the reward signal can help the model understand how much progress it has made and provide guidance, leading to a significant improvement in performance. | StateFlow | 63.73 | 0.6637 | 5.67 | 6.82 | 3.82 | 3128 | 281 | | --- | --- | --- | --- | --- | --- | --- | --- | | No_Verify | 62.28 | 0.6473 | 5.18 | 5.96 | 3.68 | 3070 | 244 | | No_Error | 58.80 | 0.6091 | 5.72 | 11.58 | 4.05 | 3280 | 318 | | No_Observe | 57.83 | 0.6041 | 6.00 | 16.95 | 4.64 | 3816 | 337 | Table 7: Ablation of states on the SQL dataset with GPT3.5-Turbo with all metrics. Best metrics in Bold. Second-best is Underlined. Appendix B ALFWorld B.1 Experiment Details For ALFWorld, we use ReAct from Reflexion https://github.com/noahshinn/reflexion, which has the same implementation as the original ReAct repository. For ALFChat, we used the code from AutoGen Evaluation https://github.com/qingyun-wu/autogen-eval. We allow a maximum of 50 rounds of interactions with the environment. For ReAct and StateFlow, we follow a text completion manner to use the chat-based model GPT-3.5-Turbo. In this experiment, we follow Reflexion to put all instructions and interaction history in one user message when querying the model. The ALFChat is essentially a chat version of ReAct, where the examples are converted into a history conversation between the ‘user’ and ‘assistant’. Details on StateFlow Setup We refer to Table 12, 13, 14 for the prompts we used. The type of input task, as a prior knowledge, is used in all methods. ReAct and ALFChat use different few-shot examples for different types of tasks. Similarly, we have different planning examples for different tasks, as shown in Table 12. In Process, we also have three different prompts corresponding to heat, cool, and clean. In Figure 8, we illustrate activated states for different tasks. As discussed in the main paper, we identify the object of interest by calling the same LLM at the beginning of the task. In Pick, only when we detect a string match of “You pick up A” (A is the object needed), we would transit the next state. Similarly, in FindLamp, we transit to UseLamp only if a string “desklamp” is matched. In Process, we match the pattern “You heat/cool/clean” to proceed. Note that this feedback is from the environment. Finally at state Put and UseLamp, we transit to End only if the task succeeds or fails. A task is considered success if we receive “Done=True” from environment, and considered fail if the same response is generated by the LLM for three consecutive rounds (following AutoGen). In this experiment, the environment feedback “Done” is available to all methods to terminate the process upon success. Please see Figure 11 for an example. B.2 Additional Analysis To understand the failure reasons of StateFlow, we manually went through the 23 failed tasks of one attempt and classified them based on the ending state (See Table 8). Ending in different states can show how much progress has been made on a task. For example, a task ending in Cool implies that the correct object is being picked, but not cooled correctly. From the table, we can see that 15/21 tasks end in Pick. This suggests that the most difficult part is to go around the household to find the correct object. For the failed tasks that ended in Pick, we summarize three failure reasons: 1. The LLM hallucinates about taking the target object from locations where it does not exist. 2. The LLM takes the wrong object. 3. The LLM gets stuck in loops between two locations. | StateFlow (7-state) | 15 | 2 | 2 | 1 | 1 | 0 | 21 | | --- | --- | --- | --- | --- | --- | --- | --- | | StateFlow (10-state) | 8 | 3 | 0 | 0 | 0 | 2 | 13 | Table 8: Count of failed ALFWorld tasks that end in different states. We also include the StateFlow model with 10 states for comparison. B.3 Additional Experiments Adding more states to StateFlow In the states defined for ALFWorld, we allow different types of actions to be performed. For example, in Pick, the model is instructed to either go around the household with the ‘go to {recept}’ command, open receptacles with ‘open’, and take an object with ‘take {obj} from {recept}’ command (the format annotation is adopted from Prasad et al. (2023)). We further divide these actions and add 3 more states and test its performance (See Figure 7). In Figure 9, we show the results of StateFlow, and StateFlow with 3 more states. The overall performance increases from 83.3% to 88.8%, with 15% less cost. Table 8 indicates that the primary contribution to performance improvement comes from dividing the Pick action into Find and Take. | StateFlow (7-state) | 91.7 | 83.9 | 85.5 | 79.4 | 92.6 | 62.7 | 83.3 | 2.6 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | StateFlow (10-state) | 100 | 92.5 | 94.2 | 87.3 | 90.7 | 58.8 | 88.8 | 2.2 | Table 9: Performance and cost of StateFlow and StateFlow with 3 more states. We report an average success rate of 3 attempts. More states and division of tasks can further improve performance at even a lower cost. Additional results with GPT-3.5-Instruct. In our experiments, we use the latest chat models (e.g., GPT-3.5-Turbo) because they are more powerful and have been studied extensively lately. Original ReAct was tested on completion model text-davicin-002, which has been depreciated. The recommended replacement is GPT-3.5-instruct https://platform.openai.com/docs/deprecations. We also tested ReAct and StateFlow on GPT-3.5-turbo-instruct, and find that the performance drops for both methods (see Figure 11). Compared to results on GPT-3.5-Turbo, ReAct has a drop of 4% and StateFlow has a drop of 9%. Addition results with open-source models We further test StateFlow and ALFChat with 3 agents on 3 open-source models: Mistral-7b, Llama-8b and Llama3-70b. We observe that StateFlow outperforms 3-agent ALFChat with 3 agents across the open-source models. It is worth noting that Mistral-7b struggles to complete the task using both methods, suggesting the model itself is not equipped to handle tasks within ALFWorld. However, Llama3-70b with StateFlow can hit a 94% accuracy, surpassing the performance of GPT-3.5 Turbo. | Mistral-7b Llama3-8b Llama3-70b | 1.5 50.7 83.6 | 0.708 0.52 2.53 | 6 62.7 94 | 2.03 0.38 1.83 | | --- | --- | --- | --- | --- | Table 10: Accuracy and cost comparison on ALFWorld with different open-source models. For this experiment, we compare with the strongest baseline and run the test one time. | ReAct | 62.5 | 41.9 | 78.3 | 57.1 | 38.9 | 23.5 | 51.5 | 10 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | StateFlow | 87.5 | 66.7 | 87 | 57.1 | 77.8 | 64.7 | 73.9 | 5.0 | Table 11: Performance and cost on ALFWorld with GPT-3.5-instruct. Here we report success rate of only one attempt. The performances of both methods drop compared to result with GPT-3.5-Turbo, on which ReAct achieves 55.5% and StateFlow achieves 83.3% in overall success rate. <details> <summary>2403.11322v5/x6.png Details</summary>  ### Visual Description # Technical Document Extraction: Flowchart Analysis ## Diagram Overview The image depicts a state machine or workflow diagram with **12 nodes** and **15 transitions**. Nodes are color-coded (gray, green, blue, red) and labeled with actions/states. Transitions include conditional logic and action descriptors. --- ## Node Definitions ### Gray Nodes (Start/End States) 1. **Init** - Start of workflow - Transition: `→ Plan` (no label) 2. **End** - Final state - Incoming transitions: - `→ Done` (from `Put`) - `→ Done` (from `UseLamp`) ### Green Nodes (Process States) 3. **Plan** - Transition: `← Init` (no label) - Transition: `→ Find` (no label) 4. **Find** - Self-loop: `↔` (no label) - Transition: `→ Take` (labeled `Found`) - Error path: `→ Error` (labeled `Wrong Pick`) 5. **Process** - Incoming: `→ Process` (from `GoBeforeAct`) - Outgoing: `→ GoTo` (labeled `Processed`) 6. **FindLamp** - Self-loop: `↔` (no label) - Transition: `→ UseLamp` (labeled `Found`) 7. **UseLamp** - Self-loop: `↔` (no label) - Transition: `→ End` (labeled `Done`) ### Blue Nodes (Action States) 8. **Take** - Central decision node - Outgoing transitions: - `→ FindLamp` (labeled `“Look”`) - `→ Process` (labeled `“Heat/Cool/Clean”`) - `→ Put` (labeled `“Pick/Pick 2”`) 9. **GoBeforeAct** - Incoming: `← Take` (labeled `“Heat/Cool/Clean”`) - Outgoing: `→ Process` (no label) 10. **GoTo** - Incoming: `→ GoTo` (from `Process`) - Outgoing: `→ Put` (labeled `“Pick 2”`) 11. **Put** - Incoming: - `→ Put` (from `GoTo`) - `→ Put` (from `Take`) - Outgoing: `→ End` (labeled `Done`) ### Red Node (Error State) 12. **Error** - Incoming: `→ Error` (from `Find`) - No outgoing transitions --- ## Key Trends and Logic Flow 1. **Primary Workflow** `Init → Plan → Find → Take → [FindLamp → UseLamp → End]` - `Find` loops until `Found` condition met - `UseLamp` loops until `Done` condition met 2. **Alternative Paths** - **Heat/Cool/Clean Path**: `Take → GoBeforeAct → Process → GoTo → Put → End` - **Pick/Pick 2 Path**: `Take → Put → End` 3. **Error Handling** - `Find` node triggers `Error` on `Wrong Pick` condition --- ## Spatial Grounding and Color Mapping - **Legend**: - Gray: `Init`, `End` - Green: `Plan`, `Find`, `Process`, `Put`, `FindLamp`, `UseLamp` - Blue: `Take`, `GoBeforeAct`, `GoTo` - Red: `Error` - **Transition Labels**: - `Found`, `Processed`, `Done` (success states) - `“Look”`, `“Heat/Cool/Clean”`, `“Pick/Pick 2”` (action conditions) - `Wrong Pick` (error condition) --- ## Component Isolation ### Header - No explicit header; workflow begins at `Init`. ### Main Chart - Central node: `Take` (blue) with three decision branches. - Critical loops: - `Find` ↔ `Find` (green) - `UseLamp` ↔ `UseLamp` (green) ### Footer - `End` node aggregates all successful paths. --- ## Data Extraction Summary | Node | Type | Connections | |---------------|------------|-----------------------------------------------------------------------------| | Init | Start | → Plan | | Plan | Process | ← Init, → Find | | Find | Process | ← Take, → Take (Found), → Error (Wrong Pick), ↔ Find | | Take | Action | ← Find (Found), → FindLamp (“Look”), → Process (“Heat/Cool/Clean”), → Put (“Pick/Pick 2”) | | GoBeforeAct | Action | ← Take (“Heat/Cool/Clean”), → Process | | Process | Process | ← GoBeforeAct, → GoTo (Processed) | | GoTo | Action | ← Process, → Put (“Pick 2”) | | Put | Process | ← GoTo, → Take (“Pick 2”), → End (Done) | | FindLamp | Process | ← Take (“Look”), → UseLamp (Found), ↔ FindLamp | | UseLamp | Process | ← FindLamp (Found), → End (Done), ↔ UseLamp | | End | End | ← Put (Done), ← UseLamp (Done) | | Error | Error | ← Find (Wrong Pick) | --- ## Notes - No numerical data or charts present; purely logical flow diagram. - All transitions are labeled with conditions or actions. - Self-loops indicate retry logic for `Find` and `UseLamp`. - Error state is terminal with no recovery path. </details> Figure 7: StateFlow model for ALFWorld with 3 addition states. The additional states are marked blue. In states Pick, Process and Put of the original model, there are actually two actions to be performed: 1. go to some receptacle. 2. take/process/put an object. Here, we further split it, using one state for one action. <details> <summary>2403.11322v5/x7.png Details</summary>  ### Visual Description # Technical Document Extraction: Flowchart Analysis ## Overview The image depicts a **flowchart** divided into three distinct sections, each representing a different task flow with error handling. The diagram uses **nodes** (circles) and **arrows** (directed edges) to represent states, actions, and transitions. Colors and labels are used to differentiate error states, task types, and process outcomes. --- ## Section 1: Task is Heat, Cool or Clean ### Nodes and Connections 1. **Init** (Gray) → **Plan** (Light Green) - Label: None 2. **Plan** → **Pick** (Light Green) - Label: None 3. **Pick** → **Process** (Light Green) - Label: None 4. **Process** → **Put** (Light Green) - Label: `Processed` 5. **Put** → **End** (Gray) - Label: `Done` 6. **Pick** → **Error** (Pink) - Label: `Wrong Pick` ### Key Observations - The primary flow progresses from `Init` → `Plan` → `Pick` → `Process` → `Put` → `End`. - An error state (`Error`) is triggered if the wrong item is picked during the `Pick` step. --- ## Section 2: Task is Pick or Pick 2 ### Nodes and Connections 1. **Init** (Gray) → **Plan** (Light Green) - Label: None 2. **Plan** → **Pick** (Light Green) - Label: None 3. **Pick** → **Put** (Light Green) - Label: `"Pick 2"` 4. **Put** → **End** (Gray) - Label: `Done` 5. **Pick** → **Error** (Pink) - Label: `Wrong Pick` ### Key Observations - The flow skips the `Process` step compared to Section 1. - The `Pick` step directly transitions to `Put` with a label indicating a secondary pick action (`"Pick 2"`). - Error handling remains consistent with Section 1. --- ## Section 3: Task is Look ### Nodes and Connections 1. **Init** (Gray) → **Plan** (Light Green) - Label: None 2. **Plan** → **Pick** (Light Green) - Label: None 3. **Pick** → **FindLamp** (Light Green) - Label: `Found` 4. **FindLamp** → **UseLamp** (Light Green) - Label: None 5. **UseLamp** → **End** (Gray) - Label: `Done` 6. **Pick** → **Error** (Pink) - Label: `Wrong Pick` ### Key Observations - Introduces new nodes (`FindLamp`, `UseLamp`) for a task requiring sequential actions. - The `Found` label indicates successful identification of an object (e.g., a lamp). - Error handling remains consistent across all sections. --- ## Common Elements Across All Sections 1. **Error Handling** - All sections include an `Error` node connected to `Pick` with the label `Wrong Pick`. - Error state is represented by a **pink circle**. 2. **Terminal State** - All flows terminate at `End` (Gray node) with the label `Done`. 3. **Initialization** - All sections start with `Init` (Gray node) → `Plan` (Light Green node). --- ## Diagram Structure - **Color Coding**: - **Gray**: Start/End nodes (`Init`, `End`). - **Light Green**: Process nodes (`Plan`, `Pick`, `Process`, `Put`, `FindLamp`, `UseLamp`). - **Pink**: Error node (`Error`). - **Arrows**: - Directed edges represent transitions between states. - Labels on arrows describe the action or outcome of the transition. --- ## Summary The flowchart illustrates three task flows with shared error handling but distinct workflows: 1. **Heat/Clean**: Involves processing after picking. 2. **Pick/Pick 2**: Skips processing, includes a secondary pick action. 3. **Look**: Requires finding and using an object. All flows emphasize error detection at the `Pick` step and conclude with a `Done` status upon successful completion. </details> Figure 8: Active states for different type of tasks in ALFWorld. Only 4-6 states are active for a single task. States Plan, Pick, Error and Put are sharable across tasks. <details> <summary>2403.11322v5/x8.png Details</summary>  ### Visual Description # Technical Document Analysis: State Transition Diagram ## Overview The image presents a state transition diagram divided into three distinct sections, each representing a different operational state: **No Error State**, **No Observe State**, and **No Verify State**. The diagram uses colored nodes (gray, green, pink) and labeled arrows to depict transitions between states. --- ## Section 1: No Error State ### Diagram Structure 1. **States**: - **Init** (Gray Circle): Starting point. - **Observe** (Green Circle): Always transitioned to from Init. - **Solve** (Green Circle): Transitioned to from Observe via `DESC`. - **Verify** (Green Circle): Transitioned to from Solve via `SELECT` or `DESC`. - **End** (Gray Circle): Final state, reached from Verify via `Submit`. 2. **Transitions**: - **Init → Observe**: Labeled `Always`. - **Observe → Solve**: Labeled `DESC`. - **Solve → Verify**: Bidirectional arrows labeled `SELECT` (top) and `DESC` (bottom). - **Verify → End**: Labeled `Submit`. - **Verify Self-Loop**: Arrows labeled `SELECT` (looping back to Verify). ### Key Observations - The `DESC` label appears on multiple transitions, suggesting a conditional or iterative process. - The `SELECT` label is used for both forward and backward transitions between Solve and Verify. --- ## Section 2: No Observe State ### Diagram Structure 1. **States**: - **Init** (Gray Circle): Starting point. - **Solve** (Green Circle): Transitioned to from Init via `Always`. - **Verify** (Green Circle): Transitioned to from Solve via `SELECT` or `DESC`. - **End** (Gray Circle): Final state, reached from Verify via `Submit`. - **Error** (Pink Circle): Error state, transitioned to from Solve or Verify via `Error`. 2. **Transitions**: - **Init → Solve**: Labeled `Always`. - **Solve → Verify**: Bidirectional arrows labeled `SELECT` (top) and `DESC` (bottom). - **Verify → End**: Labeled `Submit`. - **Verify Self-Loop**: Arrows labeled `SELECT` (looping back to Verify). - **Error Self-Loop**: Arrows labeled `Error` (looping back to Error). - **Solve → Error**: Labeled `Error`. - **Verify → Error**: Labeled `Error`. ### Key Observations - The `Error` state is reachable from both Solve and Verify, indicating failure conditions. - The `DESC` label is reused here, potentially indicating a shared error-handling mechanism. --- ## Section 3: No Verify State ### Diagram Structure 1. **States**: - **Init** (Gray Circle): Starting point. - **Observe** (Green Circle): Transitioned to from Init via `Always`. - **Solve** (Green Circle): Transitioned to from Observe via `DESC`. - **End** (Gray Circle): Final state, reached from Solve via `Submit`. - **Error** (Pink Circle): Error state, transitioned to from Solve via `Error`. 2. **Transitions**: - **Init → Observe**: Labeled `Always`. - **Observe → Solve**: Labeled `DESC`. - **Solve → End**: Labeled `Submit`. - **Solve → Error**: Labeled `Error`. - **Error Self-Loop**: Arrows labeled `Error` (looping back to Error). ### Key Observations - The `SUCCESS` label appears on the transition from Solve to End, indicating successful completion. - The `Error` state is only reachable from Solve, suggesting a simplified error pathway. --- ## Cross-Section Analysis - **Color Coding**: - **Gray**: Start/End states (`Init`, `End`). - **Green**: Active states (`Observe`, `Solve`, `Verify`). - **Pink**: Error states (`Error`). - **Arrow Labels**: - `Always`: Unconditional transitions. - `DESC`, `SELECT`, `Submit`: Conditional or action-based transitions. - `Error`: Failure states. - `SUCCESS`: Successful completion (only in No Verify State). --- ## Summary The diagram illustrates three operational workflows with varying error-handling mechanisms: 1. **No Error State**: A linear flow with error recovery via `DESC`/`SELECT`. 2. **No Observe State**: Skips observation, introduces error states earlier. 3. **No Verify State**: Simplifies verification, uses `SUCCESS` for completion. All transitions are explicitly labeled, with colors and labels consistently applied across sections. </details> Figure 9: StateFlow model for the ablation study with InterCode SQL task. <details> <summary>2403.11322v5/x9.png Details</summary>  ### Visual Description # Technical Document Extraction: State Transition Workflow ## Diagram Overview The image depicts a state transition workflow for converting the first 16 characters of a text file (`/testbed/textfile7.txt`) to a hexadecimal value. The process involves error handling and verification steps. --- ### **State Transitions and Actions** #### **1. Init → Solve** - **Question**: Convert the first 16 characters in `/testbed/textfile7.txt` to a single hexadecimal value. - **State Transition**: Always → Solve #### **2. Solve** - **Model Instruction**: Provide a BASH command to solve the task. - **Action Attempted**: ```bash execute[head -c 16 /testbed/textfile7.txt | xxd -p -c 16] ``` - **Thought**: Use `head` to extract the first 16 characters and `xxd` to convert to hexadecimal. - **SQL Observation**: ```sql /bin/bash: line 1: xxd: command not found ``` - **State Transition**: Execution Error → Error #### **3. Error** - **Model Instruction**: Check the last command output to diagnose the error. - **Thought**: The `xxd` command is unavailable. Use `od` (octal dump) instead. - **Action**: ```bash execute[od -t x1 -N 16 /testbed/textfile7.txt | awk '{$1=$1;print}' | tr -d ' '] ``` - **SQL Observation**: ```sql 546578742066696c6520203720776869746520697320 ``` - **State Transition**: Execution Success → Verify #### **4. Verify** - **Model Instruction**: Confirm the task completion. - **Thought**: The first 16 characters have been converted to hexadecimal. - **Action**: Submit - **SQL Observation**: ```sql 546578742066696c6520203720776869746520697320 ``` - **State Transition**: Last action is submit → End #### **5. End** - **Final Output**: Hexadecimal value of the first 16 characters: ```sql 546578742066696c6520203720776869746520697320 ``` --- ### **Flowchart Diagram** ``` Init (1) → Solve (2) → Error (3) → Verify (4) → End ``` --- ### **Key Trends and Data Points** 1. **Command Execution Flow**: - Initial attempt used `xxd`, which failed due to missing command. - Corrected with `od` (octal dump) and `awk`/`tr` for formatting. - Final hexadecimal value extracted successfully. 2. **Error Handling**: - Error state identified missing `xxd` command. - Workaround used `od` with post-processing to achieve hexadecimal conversion. 3. **Verification**: - Confirmed successful conversion via SQL observation. --- ### **Component Isolation** - **Header**: Diagram title and initial question. - **Main Chart**: State transitions with numbered arrows. - **Footer**: Final hexadecimal value and SQL observations. --- ### **Legend and Spatial Grounding** - **Legend**: Not explicitly present; colors inferred from state labels. - **Spatial Grounding**: - `Init` at top-left. - `Solve`, `Error`, `Verify` in sequential order. - `End` at bottom-right. --- ### **Textual Transcription** - **Error Message**: ```bash /bin/bash: line 1: xxd: command not found ``` - **Final Hexadecimal Value**: ```sql 546578742066696c6520203720776869746520697320 ``` --- ### **Conclusion** The workflow successfully converted the first 16 characters of `/testbed/textfile7.txt` to a hexadecimal value despite an initial command error. The corrected command used `od` for octal dumping and post-processing to achieve the desired output. </details> Figure 10: Example of StateFlow on Bash task. <details> <summary>2403.11322v5/x10.png Details</summary>  ### Visual Description # Technical Document Extraction: Household Task Flowchart ## Overview The image depicts a **text-based flowchart** outlining a household task workflow for heating an apple and disposing of it in a garbage can. The flowchart is divided into two columns: - **Left Column**: Initialization (`Init`), Planning (`Plan`), and iterative object search attempts (`Pick`). - **Right Column**: Execution steps (`Pick`, `Heat`, `Put`, `End`) with state transitions and observations. --- ## Left Column: Initialization & Planning ### `Init` - **Household Setting**: - Cabinets: 6, 5, 4, 3, 2, 1 - Countertops: 3, 2, 1 - Drawers: 3, 2, 1 - Shelves: 3, 2, 1 - Appliances: Coffeemaker 1, Microwave 1, Stoveburner 4, Stoveburner 3, Stoveburner 2, Stoveburner 1, Toaster 1 - Garbagecan 1, Sinkbasin 1, Fridge 1 - **Task**: Heat an apple and place it in Garbagecan 1. ### `Plan` - **Model Instruction**: "You are given a household setting and a task to accomplish. Please make a plan to complete the task." - **Plan Steps**: 1. Search for an apple (likely in Fridge 1, Countertop 1-3, Drawers 1-3, Cabinets 1-6). 2. Heat the apple in Microwave 1. 3. Dispose of the apple in Garbagecan 1. ### Iterative `Pick` Attempts #### State Transition 1: `Always → Pick` - **Model Instruction**: Search receptacles for the apple. - **Action**: Go to Fridge 1. - **ALFWorld Observation**: "The fridge 1 is closed." - **State Transition**: `2 No Pick → Pick` #### State Transition 2: `No Pick → Pick` - **Model Instruction**: Continue searching. - **Action**: Open Fridge 1. - **ALFWorld Observation**: "The fridge 1 is open. Contains: Bowl 1, Pan 1, Plate 1, Tomato 1." - **State Transition**: `3 No Pick → Pick` #### State Transition 3: `No Pick → Pick` - **Model Instruction**: Check next location. - **Action**: Go to Countertop 1. - **ALFWorld Observation**: "Countertop 1 contains: Apple 1, Egg 1, Mug 2, Soapbottle 2, Spoon 3, Vase 2." - **State Transition**: `4 No Pick → Pick` --- ## Right Column: Execution Workflow ### `Pick` - **Model Instruction**: Follow the plan to locate the apple. - **Action**: Take Apple 1 from Countertop 1. - **ALFWorld Observation**: "Apple 1 picked from Countertop 1." - **State Transition**: `5 Correct object picked → Heat` ### `Heat` - **Model Instruction**: Heat the apple in the microwave. - **Action**: Go to Microwave 1. - **ALFWorld Observation**: "Microwave 1 is closed." - **State Transition**: `6 Object Not heated → Heat` - **Action**: Open Microwave 1. - **ALFWorld Observation**: "Microwave 1 is open. Empty." - **State Transition**: `7 Object Not heated → Heat` - **Action**: Heat Apple 1 in Microwave 1. - **ALFWorld Observation**: "Apple 1 heated using Microwave 1." - **State Transition**: `8 Object heated → Put` ### `Put` - **Model Instruction**: Dispose of the heated apple. - **Action**: Place Apple 1 in Garbagecan 1. - **ALFWorld Observation**: "Garbagecan 1 contains: Papertowel 1, Potato 1." - **State Transition**: `9 Task not done → Put` - **Action**: Confirm disposal. - **ALFWorld Observation**: "Task success." - **State Transition**: `10 Task success → End` ### `End` - **Exit**: Workflow completed. --- ## Key Observations 1. **State Transitions**: - Numbered steps (1-10) track progress, with labels like "Correct object picked" (5) and "Task success" (10). - Failed attempts (e.g., closed fridge, empty microwave) trigger retries. 2. **Flow Logic**: - The apple is found on Countertop 1 after failed fridge searches. - Heating requires opening the microwave twice before successful heating. - Final disposal in Garbagecan 1 completes the task. 3. **No Numerical Data**: - The flowchart focuses on procedural steps rather than quantitative metrics. --- ## Diagram Structure | Section | Subsections | Flow Direction | |-----------|--------------------------------------|----------------| | Init | Household inventory, task description| Left-to-right | | Plan | Search, heat, dispose steps | Top-to-bottom | | Pick | Fridge, countertop searches | Iterative loops| | Heat | Microwave interactions | Sequential | | Put | Garbagecan disposal | Final step | | End | Task completion | Terminal | --- ## Conclusion The flowchart systematically outlines a household task with iterative object search, heating, and disposal steps. State transitions and ALFWorld observations validate each action's outcome, ensuring task completion. No non-English text or numerical data is present. </details> Figure 11: Example of StateFlow on ALFWorld. Table 12: Few-shot examples for State Plan in ALFWorld. Same as ReAct and other baselines, we use one prompts for each type of task. Table 13: Instructions of StateFlow for ALFWorld. Table 14: Instructions of StateFlow for ALFWorld. (Continued) | Observe ## Instructions Use the DESCRIBE [table_name] or DESC [table_name] command to understand the structure of the relevant tables. Only give one DESC command in action. ## Examples Action: execute[DESC highschooler] Action: execute[DESC friends] ## RESPONSE FORMAT For action, put your SQL command in the execute[] block. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response): Thought: $<$ your thought on which table(s) is/are relevant in one short sentence $>$ Action: execute[ $<$ your command $>$ ] | | --- | | Error ## Instructions Please carefully read the error message to understand what went wrong. If you don’t have enough information to solve the question, you can use the DESC [table_name] command to explore another table. You may want to review other tables to see if they have the information you need. ## Examples Thought: A ‘transcripts‘ table exists, but it doesn’t have the ‘release_date‘ column I came up with. I should find out what columns are available. Thought: The ‘friends‘ table has two ids. I should check if the ‘highschooler‘ table has a name associated with an ID. Thought: The ‘contestants‘ is a table, it is not a column in ‘people‘. I need to check the ‘contestants‘ table to see how to get the contestant names. Thought: I get a single number that is the number of likes that the high schooler Kyle has. This should be the answer. ## RESPONSE FORMAT For action, put your SQL command in the execute[] block. You should only give one command to execute per turn. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response): Thought: $<$ your thought on why this query is error and whether you should gather more information or fix the error in one sentence $>$ Action: execute[ $<$ your command $>$ ] | | Verify ## Instructions Carefully check if the output answers the question exactly. Make sure the output only display fields that the problem asks for. - If the output contains any extra fields, please revise and modify your query (column alias is fine, no need to round numbers). - If the output doesn’t answer the question, please revise and modify your query. You may use DESC/DESCRIBE to learn more about the tables. - If the output answers the question exactly, please submit the query with this ”Action: submit” command. ## Examples Thought: The output displays the contestant names and also contestant count. Although the count is used for sorting, it should not be displayed in output. I should modify my query to only select the contestant names. Thought: The question asks for the total population for North America. However, the output also has the continent id. I should modify my query to only select the total population. ## RESPONSE FORMAT For action, put your SQL command in the execute[] block. If the problem is solved, your action should be ”Action: submit”. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response, ” $|$ ” is the ”or” operation): Thought: $<$ your thought on whether the output and command answers the problem $>$ Action: execute[ $<$ your new command $>$ ] $|$ submit | Table 15: Instructions of StateFlow for SQL task (part 1). | Col1 | | --- | | Solve ## Instructions Based on the understanding of the tables and the problem, formulate a SQL query with SELECT that answers the question EXACTLY. Use specific clauses like WHERE, JOIN, GROUP BY, HAVING, etc if necessary. If you need more information of another table, use DESC to explore the table. Notes: You should construct your command that the output answers the question exactly. For example, If the question asks for count, your command should output a single number. Only select the field the question asks for. Do not include relevant but unnecessary fields such as ids or counts, unless the question specifically asks for it. No need to CAST or ROUND numbers unless the question asks for it. ## Examples: Thought: I should write a SQL command that selects the names from a table about high schoolers in ascending order of their grades. Grade should not be selected. Action: execute[SELECT name, grade FROM high_schoolers ORDER BY high_schoolers.grades ASC] Thought: I can use the SUM and AVG functions to get the total population and average area values for North America. Action: execute[execute[SELECT SUM(population) AS total_population, AVG(area) AS avg_area FROM countries WHERE continent = ’North America’ AND area $>$ 3000]] Thought: I should write a SQL query that gets the name field from contestants and exclude the name of ’Jessie Alloway’ Action: execute[SELECT contestant_name FROM contestants WHERE contestant_name != ’Jessie Alloway’] Follow the RESPONSE FORMAT to give your thought and action. ## RESPONSE FORMAT For action, put your SQL command in the execute[] block. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response): Thought: $<$ your thought on constructing command to answer the query exactly $>$ Action: execute[ $<$ your command $>$ ] | Table 16: Instructions of StateFlow for SQL task (part 2). | System message Interact with a Bourne Shell system using BASH queries to answer a question. Follow the user’s instructions to solve the problem. | | --- | | Solve ## Instructions Given the question, please give a self.language command to solve it. ## Examples Thought: I can try to use ‘od‘ (octal dump) command to get a hexadecimal dump and stitch together the values into one continuous string. Action: execute[od -A n -t x1 -N 16 /testbed/textfile7.txt — awk ’ $1=$ 1;print’ — tr -d ’ ’] Thought: I should find the paths to all java files in the testbed directory, then apply the word count command to each path. Action: execute[find /testbed -name ”*.java” -type f -exec md5sum + — sort — uniq -D -w 32 — awk ’print $1’] Thought: I should find the paths to all php files in the testbed directory, then apply the word count command to each path. Action: execute[find /testbed -name ”*.php” -type f -exec cat + — wc -l] Thought: The ‘du‘ command is useful for printing out disk usage of a specific directory. I can use the -h option to print in human readable format and the -s option to only print the total disk usage. Action: execute[du -sh /workspace] Follow the RESPONSE FORMAT to give your thought and action. ## RESPONSE FORMAT For action, put your BASH command in the execute[] block. Only give one command per turn. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response): Thought: $<$ your thought in one sentence $>$ Action: execute[ $<$ your command $>$ ] | Table 17: Instructions of StateFlow for Bash task (part 1). | Col1 | | --- | | Error ## Instruction Please carefully check your last command and output to understand what went wrong. Revise and modify your command accordingly or try another command. ## Examples Observation: /bin/bash: line 1: xxd: command not found Thought: Seems like xxd is not available. I can try to use ‘od‘ (octal dump) command to get a hexadecimal dump. Action: execute[od -A n -t x1 -N 16 /testbed/textfile7.txt] Follow the RESPONSE FORMAT to give your thought and action. ## RESPONSE FORMAT Reply with the following template ( $<$ … $>$ is the field description): Thought: $<$ your thought in one sentence $>$ Action: execute[ $<$ your command $>$ ] | | Verify ## Instructions Carefully check if the question is answered. - Please check if the desired tasks have been performed. - If the question also asks for output, please check your last command and output, and make sure the output is in the desired format, and doesn’t contain any extra fields. - If the desired tasks have been performed, please submit the query with this ”Action: submit” command. ## Examples Thought: This gives me storage information for every folder under the workspace directory, but I only need the storage for just the ‘workspace/‘ directory. The ‘-s‘ option should help with this. Action: execute[du -sh /workspace] Thought: This shows the output hashes and they have the same values, indicating that these files are duplicates. However, the file names are also shown, which are not needed. Action: execute[find /testbed -name ”*.java” -type f -exec md5sum + — sort — uniq -D -w 32 — awk ’print $1’] Thought: This shows me too much information, I only need the total number of lines. I should add up the lines together and output a single number. Action: execute[find /testbed -name ”*.php” -type f -exec cat + — wc -l] Thought: The hello.txt file has been created successfully in the testbed/ directory, and it contains the Hello World text. I can submit. Action: submit Please follow this RESPONSE FORMAT to give your thought and action. ## RESPONSE FORMAT For action, put your {self.language} command in the execute[] block. Only give one command per turn. If the question is solved, your action should be ”Action: submit”. Reply with the following template ( $<$ … $>$ is the field description, replace it with your own response, ” $|$ ” is the ”or” operation): Thought: $<$ your thought on whether the question is answered in one sentence $>$ Action: execute[ $<$ your new command $>$ ] — submit | Table 18: Instructions of StateFlow for Bash task (part 2). | Col1 | | --- | | ReAct Prompt Example 1 Question: What are the names and grades for each high schooler? Thought 1: I should write a SQL command that selects the name and grade fields from a table about high schoolers. Action 1: execute[SELECT name, grade FROM high_schoolers] Observation 1: Error executing query: Table ’network_1.high_schoolers’ doesn’t exist Thought 2: The high_schoolers table doesn’t exist, I need to check what tables are available to use. Action 2: execute[SHOW TABLES] Observation 2: [(’friend’,), (’highschooler’,), (’likes’,)] Thought 3: There is a table called ‘highschoolers‘. I should check what information this table contains. Action 3: execute[DESC highschooler] Observation 3: [(’ID’, ’int’, ’NO’, ’PRI’, None, ’auto_increment’), (’name’, ’text’, ’YES’, ”, None, ”), …] Thought 4: The highschooler table contains the name and grade columns. I can now write a SQL command that answers the question Action 4: execute[SELECT name, grade FROM highschooler] Observation 4: [(’John’, 12), (’Haley’, 10), (’Alexis’, 11), (’Jordan’, 12), (’Austin’, 11), (’Tiffany’, 9), (’Kris’, 10), (’Jessica’, 11), (’Jordan’, 9), (’Brittany’, 10), (’Logan’, 12), (’Gabriel’, 9), (’Cassandra’, 9), (’Andrew’, 10), (’Gabriel’, 11), (’Kyle’, 12)] Thought 5: The output contains the name and grade for each high schooler, answering the question. I can submit this as the answer. Action 5: submit | | ReAct_Refined Prompt Example 1 Question: What are the names and grades for each high schooler? Thought 1: I should first find out what tables are available in this MySQL database that can help me answer this question. Action 1: execute[SHOW TABLES] Observation 1: [(’friend’,), (’highschooler’,), (’likes’,)] Thought 2: There is a table called ‘highschoolers‘. I should check what information this table contains. Action 2: execute[DESC highschooler] Observation 2: [(’ID’, ’int’, ’NO’, ’PRI’, None, ’auto_increment’), (’name’, ’text’, ’YES’, ”, None, ”), …] Thought 3: The highschooler table contains the name and grade. I can now write a SQL command that answers the question. Action 3: execute[SELECT name, grade FROM highschooler] …(Same as original example) | Table 19: (Example 1) Comparison of example trajectories from ReAct and refined version of ReAct for the SQL task. For the new version, we always start with the ”SHOW TABLES” command. In the original ReAct prompt, it always starts with a select query but results in error. Table 20: Example 2) Comparison of example trajectories from ReAct and refined version of ReAct for the SQL task.