StateFlow: Enhancing LLM Task-Solving through State-Driven Workflows

Authors: yiran  wu
tianwei  yue
shaokun  zhang
chi  wang
qingyun  wu
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-21 14:06:36

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$\times$ and 3$\times$ less cost respectively. 
We also show that StateFlow can be combined with iterative refining methods like Reflexion to further improve performance.

Main paper: 
 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? 1 Published as a conference paper at COLM 2024 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., M i → 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.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.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 LLMdriven 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. 
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 Σ (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 Finitestate 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 ⟨Σ, Γ, S, s 0 , δ, ω⟩ (Rich et al., 2008) , where Σ abd Γ are the input and output alphabet (finite non-empty set of symbols), S is a finite non-empty set of states, ω is the output function, s 0 is the initial state, δ is the state transition function (δ : S × Σ → S), and F is the set of final states. 
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.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 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 ⟨S, s 0 , F, δ, Γ, Ω⟩ and explain each of the components under the LLM scenario:States 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 s 0 The process begins at the initial state when receiving the input task/question. Final States F A set of final states when the process is terminated, which is a subset of S.Output Γ We define Γ to be an infinite set of messages (unit of text) consisting of prompts P, language model responses C, and feedback from tool/environment O: Γ = {P, C, O}, which represents all possible messages that can be generated within StateFlow. We further define context history to be Γ * , which is a list of messages that have been generated. S × Γ * 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.Based on the current state and context history, the transition function would determine which state to go to (δ : S × Γ * → 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.Require: task Q, max transitions M, model ⟨S, s 0 , F, δ, Γ, Ω⟩, we define s.outputs to be list of functions [ω 1 , . . . ,ω i ], ω i ∈ Ω for each s ∈ S 1: Γ * ← Q 2: Counter ← 0 3: s ← s 0 4: while s ̸ ∈ F do 5:for ω in s.outputs do6: do Γ * ← Γ * + ω(Γ * ) 7: end for 8: s ← δ(s, Γ * ) 9:return s, Γ * if Counter ≥ M 10: end while 11: return s, Γ * Output Functions Ω Here we define Ω to be a set of output functions, where a function ω takes the whole context history and generates an output (ω : Γ * → Γ). The output function can be an LLM, a tool call, or a prompter function that returns a static prompt (e.g., P, E and 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 Γ * 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.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.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.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.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.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. 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' 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. 
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 20 and 21 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. (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 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 7 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. with GPT-3.5-Turbo. We report average success rate of 3 attempts.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 AutoGen1 . More details are in Appendix B.1.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.StateFlow Setup. The StateFlow model is shown in Figure 4 . 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. 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 5 , 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. 
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 rulebased 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. 
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. 
 
 Appendix: For ReAct and Plan & Solve, we use the code from InterCode repository2 . The StateFlow models for the ablation study on the InterCode SQL task are in Figure 8 and the full metrics for the ablation study are shown in Table 8 . See Figure 9 for a bash example with StateFlow. We include also two examples of ReAct and ReAct Refined in Table 20 and 21 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 6 and Table 7 for detailed comparisons.See Table 16 and 17 for the instructions used for SQL StateFlow model and Table 18 and 19 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.The additional analysis below is based on results with the GPT-3.5-Turbo model.The SQL dataset consists of different levels of difficulties (See Table 5 ). 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 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 Table 7 : 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( * ).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.We present the results of SF Chat, an alternative version of StateFlow, in Table 6 and 7. 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. 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 6 , 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.For ALFWorld, we use ReAct from Reflexion3 , which has the same implementation as the original ReAct repository. For ALFChat, we used the code from AutoGen Evaluation4 . 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'.We refer to Table 13 , 14, 15 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 13 . In Process, we also have three different prompts corresponding to heat, cool, and clean. In Figure 7 , 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 10 for an example.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 9 ). 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 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. 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 6 ). In Figure 10 , 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 9 indicates that the primary contribution to performance improvement comes from dividing the Pick action into Find and Take. 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-instruct5 . We also tested ReAct and StateFlow on GPT-3.5-turbo-instruct, and find that the performance drops for both methods (see Figure 12 ). Compared to results on GPT-3.5-Turbo, ReAct has a drop of 4% and StateFlow has a drop of 9%. Figure 6 : 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.Household setting: You are in the middle of a room.quickly around you, you see cabinet 6, cabinet a cabinet 4, a cabinet a cabinet 2, a cabinet 1, a coffeemachine 1, a countertop 3, a countertop 2, a countertop 1, a drawer 3, a drawer 2, a drawer 1, a fridge 1, a garbagecan 1, a microwave 1, a shelf 3, a shelf 2, a shelf 1, a sinkbasin 1, a stoveburner 4, a stoveburner 3, a stoveburner 2, a stoveburner 1, and a toaster 1. Your task is to: heat some apple and put it in garbagecan. ## Examples -Use "go to {recept}" command to go to the receptacle: Action: go to cabinet 1 Action: go to fridge 1 Action: go to diningtable 1 -Take the object only if the place have the exact object you are looking for: Thought: Now I find the soapbar (1). Next, I need to take it. Action: take spraybottle 2 from cabinet 2 Thought: Now I find the apple (1). Next, I need to take it. Action: take apple 1 from diningtable 1 Error You just took the wrong object. Please put it down with the "put obj in/on place" command, where "place" is the place where you took the object from. Please also give your thought of what is the next place to check based on the plan.Thought: I accidentally took the tomato instead of the apple. I need to put it back, and then check diningtable 2.Action: put tomato 1 in/on diningtable 1 Thought: The object I want to take is a soapbar, but I took a soapbottle. I need to put it back, and then check the sinkbasin 1. Action: put soapbottle 4 in/on toilet 1 Process (Heat) ## Instructions You now take the object of interest with you. Now, please go to the microwave to heat the object. You must first go to the microwave with the "go to {microwave}" command. Then, use the "heat {obj} with {microwave}" command to heat the object. You don't need to open the microwave or put the object in the microwave.-If you just picked the object, go to the microwave first: Action: go to microwave 1 -Then heat the object: Action: heat apple 1 with microwave 1 Action: heat bread 1 with microwave 1 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. ', 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. We use AutoGen v0.2.17.https://github.com/princeton-nlp/intercodehttps://github.com/noahshinn/reflexionhttps://github.com/qingyun-wu/autogen-evalhttps://platform.openai.com/docs/deprecations 


Decision: This paper proposes a StateFlow framework to better control LLM to solve highly complex tasks. The method utilizes the concept of FSMs to model the task-solving process in LLMs, and proposes a few common components (observe, select, verify etc.) to help the model transit between different states, reaching a more correct final state for solving the task.

Pros:
- Reviewers agree that the proposed method is relatively novel and well-motivated: StateFlow helps LLMs break complex tasks into clearer, more manageable sub-steps. This could improve the controllability and interpretability of LLMs.
- The empirical gains are fairly significant over multiple tasks, with a reduced cost.

Cons:
- Most reviewers point out that the biggest weakness of this paper is that all the states need to be pre-defined and all the tasks experimented can be well-controlled. It is difficult to know whether such framework can be easily adapted to real-world complex tasks.

Minor:
- Some reviewers mentioned that the structure of this paper can be made more clear, like the description of FSMs can be condensed and the authors should provide more details and analysis for the method and experiments.

Reviews: review: paper_summary: paper_summary: The paper introduces StateFlow, a framework for enhancing task-solving processes in LLMs by using finite state machines (FSMs) to model complex workflows. The primary idea is the combination of state-driven control and dynamic interaction with external tools, thus improving the efficiency and interpretability of LLMs in multi-step problem-solving tasks. By structuring the LLM's task-solving process into distinct states and transitions, it enables better control and guidance, improving performance metrics over baseline methods like ReAct.
strength_weakness: strength_weakness: - For me, the main concern of this paper is that the core idea of applying state machines to manage LLM workflows seems to repackage a well-established concept without providing transformative novelty. In the context of LLMs, while the paper presents this as a novel methodology, lots of agent already consider the similar ideas, albeit without explicitly claiming the FSM label. 
- It seems that the demonstrated benefits of StateFlow are primarily shown in "controlled" benchmarks, which might not fully convince of its broad applicability or superiority in diverse real-world scenarios. 
- I can resonate with the authors' choice of baselines, as there are indeed many agent-based methods that are complex and difficult to implement. However, I feel that the choice of baselines might be slightly weak. I would have liked to see comparisons with other methods, many of which are referenced in the related work section. This would help to contextualize StateFlow's performance and innovative value more robustly within the current landscape.
questions: questions: - It seems that the states required to be pre-defined. Considering that human cognitive processes are not strictly confined to finite states, can you provide more insights on how StateFlow performs in highly dynamic environments where the tasks or the nature of the interactions change over time? Specifically, how does StateFlow adapt when faced with tasks that have evolving goals or when unexpected changes occur in the environment?
- Any thoughts or ideas on some more complex tasks, e.g., SWE-bench or real-world Web interaction?
paper_summary: paper_summary: StateFlow presents a structured approach by modeling task-solving as state machines, allowing for a systematic progression through tasks, which slightly enhances the efficiency and interpretability of LLMs. The method shows modest improvements in performance on benchmarks such as InterCode SQL and ALFWorld, suggesting potential benefits over existing models like ReAct.
strength_weakness: strength_weakness: To validate the effectiveness of the method, it is recommended to conduct more experiments using other models. How does this method perform with open-source LLMs such as LLaMA3 and Mistral (e.g., 7B and 70B versions)?
paper_summary: paper_summary: The paper addresses the broad topic of LLM prompt efficiency, specifically in the context of task-oriented interactions with external tools. The paper's main contribution is to propose structuring interactions as a task-specific finite state machine, where the task is decomposed into subtasks (states) with a dedicated instruction and criteria for transitioning out of the state. This formalism is evaluated on two LLM model checkpoints (GPT-4-Turbo, GPT-3.5-Turbo) across three broad tasks: SQL and Bash tasks from the InterCode benchmark and ALFWorld, a text-adventure environment. The proposed method is compared against the InterCode benchmark methods, ReAct and Plan & Solve, reporting on success rate, error rate, and LLM usage/cost.

The paper is generally easy to read and well motivated. The key innovation of the paper is the development of a state machine-inspired decomposition approach to LLM prompting. While motivated by and demonstrated on tool interaction tasks, this concept could be adapted to others where the the broader request can be decomposed into subtasks that have individual success criteria. The primary demonstrated benefit is efficiency -- fewer inference calls with fewer tokens, thus less cost, to achieve competitive or better results.

The primary weakness of the the paper is in its structure. It spends a lot of time describing finite state machines from a formal basis and attempting to match elements of the StateFlow method to this. However, the paper does not motivate why this is necessary or what value there is in doing so, especially as it has to modify the original FSM formalism to account for elements specific to the LLM interaction setting. There is an interesting result here, but the desire to mathematically align with the FSM definition gets in the way. It should be enough to say that StateFlow is inspired by FSMs, provide a brief schematic, and then move on to the actual details of the experiments.

The paper acknowledges that StateFlow's success is entirely dependent on the implementer to define an FSM with associated instructions and transition criteria for the specific task. In its current form, this makes it more of a strategy for structuring solutions to problems than a general method. Finally, in the appendix, there are details to enable reproducibility, including providing code in GitHub.

======

Edit: After rebuttal, the decision has changed to accept based on promised changes
strength_weakness: strength_weakness: The paper should be revised first in order to be stronger. Too much of the paper is spent reviewing the formal definition of finite state machines and attempting to adapt that to the LLM setting. This should be removed or relegated to the appendix, and replaced with content already in the appendix around the experimental details and analysis conducted.
paper_summary: paper_summary: This paper proposes a task-solving paradigm, StateFlow, which conceptualizes complex task-solving processes as a state machine. This approach separates the control of task decomposition from sub-task solving and achieves better performance with fewer interaction turns compared to baselines on the InterCode SQL and ALFWorld benchmarks.
strength_weakness: strength_weakness: 1. This workflow seems effective in complex task-solving, but for simpler tasks such as translations or reading comprehension, which are foundational abilities of language models, it may not offer significant improvements. This may also explain why the performance gain is greater on the ALFWorld benchmark than on the InterCode SQL benchmark.
2. This framework is not entirely independent of human efforts. To deploy StateFlow for a specific task, we must carefully define the States, which are central to adapting it for specific tasks, along with output functions and transitions. Designing states is challenging because it initially requires observing task-solving examples. With the basic workflow in mind, we must consider all possible scenarios that might arise during the process. Moreover, as the ablation experiments show, the omission of any essential state can lower performance. This task presents challenges not only for models but also for humans.
3. This framework primarily enhances process control and does not improve reasoning or subtask solving; therefore, common errors, such as tool parameter errors, still occur.

============================

After rebuttal:

Initially, I gave the paper a relatively high score due to its interesting method. If the authors can solve my questions, **I will raise the score to defend this work**. However, the authors just agree with my opinion but **do not make an effort to address my concerns**. Thus, I **decrease the score**.

After another rebuttal:

I have changed the score to 7 and did not raise the score due to the limitation of the paper in the method. However, I still think this work is interesting and deserves to be published.
questions: questions: See Reasons To Reject.

Comments: title: Thank you
Thank you
Thanks for your reply
Further Clarification on complex tasks
Thanks for your reply
Clarification to questions
Thank you for your response!
comment: Thank you for your review! We will incorporate this results in the next version.
Thank you for your review, please let us know if you have any other questions!
Thank you for your effort in communicating with us. Please let us know if you have any other questions!
Thank you for your response. Now, I think both are acceptable. Thank you for clarifying this time. I have changed the score to 7.
Thank you for responding. The promised changes should indeed improve the paper.
Thanks for your patience and allow us to clarify.

## Re 1st question:
1. Our method can solve complex tasks. That means solving the whole task.
2. We performed experiments on complex tasks. All the benchmarks we used are generally considered as complex benchmarks. They all require multiple steps and interactions with the environment.


## Re 3rd question:
**Example of a complex task (from ALFWorld, used in our experiment)**: Household setting: You are in the middle of a room. Looking quickly around you, you see a cabinet 6, a cabinet 5, a cabinet 4, a cabinet 3, a cabinet 2, a cabinet 1, …. Your task is to: heat some apple and put it in garbagecan

Note: to solve the task, we need to find the apple, heat it, and then put it garbagecan. During the process, the agent needs to interact with the environment, for example, go to a listed place and see if the apple is there. (Please refer to *Figure 10* in the Appendix for this example and solving process by our method)


**Your original point**: This framework primarily enhances process control and does not improve reasoning or subtask solving; therefore, common errors, such as tool parameter errors, still occur.

**Your question**: How do you plan to solve it?


**Our reply:**
1. Our framework **already improves** reasoning and subtask solving, as well as reducing tool parameter errors.  Let’s use the ALFWorld example above for illustration.

   - As noted, solving this task requires multi-steps, and the LLM needs to decide what to do next based on feedback from the environment. 
   - If you could take a look at Figure 4 in our paper, our method decomposes the process to different states. Within each state, a specific instruction is used to prompt the model. For example, In the “Pick” state, only instructions related to picking up the object are sent to LLM.
   - Compared to using one instruction that asks the model to perform all actions, we only ask the model to perform one action in a state. So the LLM can follow the instructions better, and we expect less common errors.

2. To further improve reasoning, iterative refining methods can be easily added to our framework. 
	- For example, *Reflexion* learns from past errors to improve reasoning, and we show that adding Reflexion can improve the performance with less incurred costs (See results in Figure 5).
What is the difference between “be limited in” and “be limited to”? I think it’s the same thing:) 
I would like us to stop dwelling on grammar and return to the questions in the paper. Does your response mean that your method can be applied to complex tasks but is the simple part of complex tasks? Or does it mean it works but you didn't experiment? The current reply is too confusing for me to understand. Could you explain it again?


As for the second question, I think it is acceptable. Thank you for your clarification this time.


As for the third question, your reply is very different from the first one, which makes me very confused. How do you plan to solve it? Now what you say seems to be a bunch of formulaic words, could you explain it with an example, which will help me better understand it?
Dear reviewer t4Kc,

Thank you for your comments and questions. We believe there may have been some misunderstandings regarding our previous rebuttal responses. To clarify, we have provided additional justifications below. Could you please kindly re-evaluate our method based on the replies?

> So, it can not be extended to real-world difficult tasks?

We are sorry for the misunderstanding. In the original rebuttal, we were trying to say that our method **focuses on** complex tasks that require tools and interactions but **"is limited in"** simple tasks (not “limited to”). That means our methods may not have obvious advantages on simple one-hop questions. However, it is suitable to real-world difficult tasks.

> How to improve it?

As mentioned in our previous reply, we provide clear guidance in Section 3.2 to simplify the construction process and minimize human effort. Also, we mentioned that it is not necessary to consider all possible scenarios when designing states, as shown by our Bash experiment. Finally, as mentioned in Section 6 of our paper, to further reduce human effort, we can access running trajectories from a StateFlow model, and employ another LLM to iteratively add or remove states to automate the process. 

> How to solve it?

As mentioned in our previous reply, our method actually improves the reasoning of LLMs and reduces tool parameter errors because the LLMs are instructed with specific instructions at each state, so that they can follow a single instruction at a time for more accurate and dedicated reply.

Thanks,

Authors
Thanks for the author's response and effort. It is recommended to incorporate the results into the next version.
> We admit that our method is limited to simple tasks, especially those that only require one single step.

So, it can not be extended to real-world difficult tasks?

> We agree that our method involves human effort and task observation.

How to improve it?

> We admit that our method focuses on process control by breaking down a complex workflow into state transitions and states.

How to solve it?

Overall, you just agree with my opinion but do not solve my concern. Thus, I decrease the score.