FLAP : Flow-Adhering Planning with Constrained Decoding in LLM s (2024)

Abstract: Planning is a crucial task for agents in task oriented dialogs (TODs). Human agents typically resolve user issues by following predefined workflows, decomposing workflow steps into actionable items, and performing actions by executing APIs in order; all of which require reasoning and planning. With the recent advances in LLMs, there have been increasing attempts to use them for task planning and API usage. However, the faithfulness of the plans to predefined workflows and API dependencies, is not guaranteed with LLMs. Moreover, workflows in real life are often custom-defined and prone to changes; hence, adaptation is desirable. To study this, we propose the problem of faithful planning in TODs that needs to resolve user intents by following predefined flows and preserving API dependencies. To solve this problem, we propose \textbf{FLAP} , a \textbf{Fl} ow- \textbf{A} dhering \textbf{P} lanning algorithm based on constrained decoding with lookahead heuristic for LLMs. Our algorithm alleviates the need for finetuning LLMs using domain specific (plan/dependency) data, enables quick adaptation to predefined flows, and outperforms other decoding and prompting-based baselines. Further, our algorithm empowers smaller LLMs ( \approx7 B) to perform at par larger LLMs ( \approx30 B-40B).

## introduction a successful task oriented dialog (tod) often involves interaction with internal or external world through tools or apis. for example, as shown in fig. 1 , booking a flight through a conversation may involve searching for flights, getting payment information, and so on. api usage is a difficult task for chatbot agents as it involves various reasoning and planning. beyond predicting the correct api to use in a particular scenario, it requires task decomposition and resolution of inter-api dependencies (e.g., searching for flights requires extracting airport codes) @xcite @xcite . moreover, ## task formulation in this section, we define the novel task of faithful planning in task oriented dialogues (tods) to resolve queries by adhering to predefined natural language (nl) flows and api dependencies. ## data collection in this section, we describe the data collection procedure for studying faithful plan generation. ## related work while api usage and planning have been studied as separate concepts in literature, we argue that these two are interdependent. recently, different approaches have been proposed to teach llms to use the correct api, however, the faithfulness of api usage to their dependencies is understudied @xcite . for correct api usage, one line of research considers pretraining of llms with large api data that are mostly augmented using self-instruction @xcite @xcite @xcite @xcite . in some cases, authors considered modular approaches and (b) generated plan with mistral-7b-instruct. in literature, planning is defined as decomposition of the end task and identifying intermediate executable actions or reasoning steps to achieve the goal where the decomposition is open-ended and does not require obeying instructions @xcite @xcite @xcite @xcite . however, in many applications, such as customer care service or physical robots, planning needs to strictly adhere to predefined instructions @xcite . to achieve this, we draw inspiration from decoding approaches @xcite ) that enable enforcement of lexical and parametric constraints during generation @xcite @xcite @xcite . we extend the idea to enforce constraints related to predefined instructions. ## conclusion in this paper, we study the novel problem of faithful planning for performing tasks in tods, that adheres to predefined flows and preserves api dependencies. to solve the task, we propose flap, a constrained decoding algorithm based on lookahead heuristic. flap outperforms promptingbased baselines with different decoding methods and applying flap on two smaller llms we achieve comparable performance to larger ones. our approach can be leveraged in accurate planning for various downstream applications such as next step prediction in conversations, user simulation, flow-following conversation data augmentation for training tod models, and so on.