Symbolic Planning and Code Generation for Grounded Dialogue (2023)

Abstract: Large language models (LLMs) excel at processing and generating both text and code. However, LLMs have had limited applicability in grounded task-oriented dialogue as they are difficult to steer toward task objectives and fail to handle novel grounding. We present a modular and interpretable grounded dialogue system that addresses these shortcomings by composing LLMs with a symbolic planner and grounded code execution. Our system consists of a reader and planner: the reader leverages an LLM to convert partner utterances into executable code, calling functions that perform grounding. The translated code’s output is stored to track dialogue state, while a symbolic planner determines the next appropriate response. We evaluate our system’s performance on the demanding OneCommon dialogue task, involving collaborative reference resolution on abstract images of scattered dots. Our system substantially outperforms the previous state-of-the-art, including improving task success in human evaluations from 56% to 69% in the most challenging setting.

## introduction success in grounded task-oriented dialogue requires intentional communication guided by strategic planning @xcite @xcite @xcite . dialogue agents must read partner utterances, update their beliefs, then make a plan that furthers their goal. these plans must take into account both dialogue history and grounding, such as in an image. in end-toend systems based solely on large language models (llms), this process is implicit and therefore difficult to control, requiring extra supervision @xcite or expensive search @xcite to improve. while recent work has taken steps to rectify implicit reasoning via planning in language space, where intermediate steps are generated by an llm @xcite , there is no @xcite do you see a pair of dots, where the top left dot is medium-sized and grey and the bottom right dot is medium-sized and dark human: do you see a pair of dots, where the top dot is small-sized and light and the bottom dot is medium-sized and grey human: yes i see them. is there a small grey dot above the small light dot? spc: no. is there a large size and dark color dot to the left and below those? human: yes and there is a small grey dot below them as well for me. spc: yes. let's select the small size and light color one. spc: <@xmath2: <@xmath3: an example grounded dialogue from onecommon. our dialogue agent, spc, and a human partner have different but overlapping circular views of a shared board. the agent and partner must collaborate through dialogue in order to find and select a shared dot. onecommon demands careful, grounded reasoning. we provide an example from onecommon, a particularly challenging grounded dialogue game @xcite . the goal of onecommon is to, through dialogue, identify one dot in common with your partner, who has an overlapping but different view of an underlying set of dots, illustrated in figure 1 . the challenge in onecommon is grounding the contextual spatial relationships described in language to dots. recent work has utilized code-generation for grounded language understanding @xcite . in particular, they translate natural language questions to code as an intermediate representation, then execute that code to obtain an answer. code has a couple appealing properties as an intermediate representation: first, modern language models are trained on a mixture of code and natural language, affording them the capability of, with some accuracy, translating between the two @xcite . second, code acts as a compositional knowledge representation. this allows code-generation systems to perform grounded compositional reasoning, provided a library of python functions that perform grounding @xcite . we present a system, symbolic planning and code-generation (spc), that reads by translating partner utterances into code and plans based on symbolic reasoning over what to say next. code as a compositional knowledge representation closely mirrors the compositional nature of utterances, which are composed of grounded parts. spc plans by optimizing expected information gain, which has been shown to be effective at building a key aspect of collaborative dialogue: common ground @xcite @xcite . symbolic planning allows spc to explicitly and efficiently optimize for task success while taking advantage of task-specific properties. we evaluate our spc system on the most challenging subset of the onecommon task, comparing our system to the previous state-of-the-art supervised system for the task @xcite . in both evaluations with human partners and automated self-play evaluations, we find that our approach substantially outperforms the previous stateof-the-art in task accuracy, improving from 56% to 69% accuracy, and obtains comparable task accuracy to human-human pairs on average. ## related work prior work on collaborative reference games focuses on building common ground @xcite @xcite . prior work by @xcite implements an approximation of pragmatic reasoning on onecommon, but plans in language space and utilizes supervised models for mapping language to symbols. @xcite plan in symbolic space, but without natural language. we plan in symbolic space and map from language to symbols via code generation. dialogue systems have a long history of reasoning with symbolic actions. when available, symbolic actions have been found to improve the performance of dialogue systems, especially in the setting of grounded dialogue @xcite @xcite @xcite . the closest work to ours is cicero, which utilizes symbolic planning in a system for diplomacy, a dialogue and strategy game that requires negotiation and coordination between players @xcite . cicero requires a supervised dataset to train their system. we use code llms which require minimal supervision beyond constructing a small perceptual grounding api. planning in dialogue systems has recently eschewed symbolic actions in favor of planning directly in text, where systems either perform rollouts, tree-search, or other forms of intermediate reasoning in language. this allows system designers to avoid manually defining symbolic actions @xcite @xcite . however, the accuracy of languagespace planners is still low in many settings @xcite . we focus on symbolic planning, where planning is defined in a space that ensures accuracy and controllability. with the recent progress in large language modeling, code generation for modular grounded systems has quickly gained interest. grounded code generation systems do not require task-specific training data, making them cheap to apply. a body of work utilizes a large language model for instruction following by generating python code that makes calls to lower-level perception libraries @xcite @xcite . this extends prior work on executable semantic parsing @xcite @xcite with large language models. concurrent work has also utilized code-generation to interpret language, integrated with symbolic reasoning @xcite . we apply these advances to the setting of grounded task-oriented dialogue, where code generation grounds language to symbolic actions for use in explicit planning. ## overview: reference games collaborative reference games pair an agent and a partner in order to build common ground through natural language dialogue @xcite @xcite . mirroring realistic scenarios, many reference games are also partially observable, where the agent and partner have different perspectives, and so they must resolve ambiguity. onecommon @xcite , as shown in figure 1 , is a reference game that exemplifies two challenges: grounding and planning. in onecommon, the agent and partner see different but overlapping views of a set of dots, and the goal is to find and select one dot common to both players' views. grounding in onecommon is particularly difficult due to the dot-based visual context, which requires abstract spatial reasoning. planning is complicated by the partial observability caused by differing perspectives, which require agents to use complex referring expressions in order to avoid ambiguity. 1 we focus on onecommon due to its simplicity and difficulty. our approach to grounded reference games separates symbolic reasoning from language, allowing explicit steering. our system, symbolic planning and code-generation (spc), breaks down a turn into three procedures: reading, planning, and writing. reading and writing convert from language to symbols and vice versa, while planning reasons in purely symbolic space. the agent maintains a belief distribution over possible worlds, z, representing task-specific unknowns. the goal of dialogue is to gain information about z until the agent is confident enough to end the game. at each turn, the agent reads the partner's utterance u, converting it into a symbolic action, p(x|u). this symbolic action potentially builds upon the action x ′ of a previous utterance, u ′ . the agent then plans in symbolic space. the system uses reasoning to update its belief state, p(z|u) = in onecommon, given a set of dots d, the state @xmath4, 1} |d| represents which dots the agent believes are contained (1) and not contained (0) in the partner's view, illustrated in figure 3 . we call a set of dots a configuration. the action representation of partner, x and x ′ , and agent utterances, y * , alike is also a configuration in {0, 1} |d| , as well as any answers or confirmations to previous questions. ## reading: from language to symbols reading in spc requires interpreting utterances to a grounded symbolic action, which in turn facilitates the planning stage. consider the following exchange: do you see a triangle of dark dots? partner: yes, is there a small grey one below it? reading has several challenges. first, reading requires grounding utterances in context, e.g. the shapes and relations. second, utterances are compositional. for example, the partner utterance builds on top of the previous utterance through coreference. finally, a reading system must act quickly, as real-time dialogue systems require reasonable response times. ## planning: from symbols to responses to perform well in collaborative reference games, it is essential to build common ground quickly and accurately by carefully reasoning about what information has been gathered so far, as well as what to say next. spc addresses these desiderata by planning in symbolic space, over the symbolic actions produced by reading. we have two challenges: first, to incorporate the new information from the partner's utterance while accounting for task-specific grounding as well as dialogue history. second, given this new information, the system must decide either to end the game or how to improve the probability of success. planning requires us to model the actions of the partner given the shared state. to do this we need task specific models of our partner, p(x | z), and our partner's reponse to us, p(x|z, y). in onecom-mon, we model both of these by a heuristic function considering set overlap and dot proximity, described in appendix d. ## experimental setup we conduct two evaluations of spc on the onecommon task. we compare to the state-ofthe-art baseline system of @xcite , which we refer to as imitate. imitate is a pipelined system, where each part is fully supervised. imitate uses a neural representation of dialogue history in combination with a neural-crf reference resolution module to understand grounded language. in order to generate, imitate relies on a pragmatic planning procedure, which plans in a mixture of symbolic and language space, prioritizing descriptions of dots that are easily understood. we first perform human evaluation, evaluating the task success of systems when paired with human partners. this setting is challenging, requiring the system to handle both the linguistically diverse utterances and a range of strategies of human partners. we recruit 19 workers from amazon's mechanical turk to play with one of three partners: spc, the most successful past system for the task @xcite , or another human. we pay @xmath01.00 per game at an average of 4 minutes per game. we additionally give a bonus of @xmath11.00 per game, with a $0.15 bonus if they win. we collect 287 completed dialogues in total, where both players selected a dot. we secondarily evaluate systems in self-play, where systems are paired with a copy of themselves. this isolates strategic efficiency by ensuring the agent's partner has the same skill as the agent. the 200 games share the same contexts across systems. we include an additional system in self-play, gpt4 2-shot foot_10 , which gets two full human dialogues as examples. each human dialogue example starts with a description of the context the agent sees. the full prompts can be viewed here. parameterization for code generation, during the reading phase we use gpt-4 foot_11 (openai, 2023). 7 results ## analysis qualitative analysis we present a qualitative example of a dialogue between spc and a human partner in figure 5 . this long dialogue illustrates the benefits of explicit belief updates and planning: the conversation starts off with many rejections, which the agent uses to deduce the shared configurations. eventually, a common set of dots is found and the game ends in a success. without explicit planning, it would have been unlikely for spc to have succeeded at the end of the conversation. ## conclusion we present symbolic planning and codegeneration (spc), a method that approaches grounded task-oriented dialogue by separating symbolic reasoning from language. our approach uses an llm to generate executable code functions which represent the meaning of utterances, mapping from language to symbolic actions. we then symbolically track task progress using bayesian reasoning, and explicitly plan the best actions to take next using an information gain objective. despite using minimal supervision, beyond a taskspecific api and few-shot examples, our approach substantially outperforms the state-of-the-art system for the onecommon task in both human eval-uations and automatic self-play evaluations. our work contrasts with recent work on planning in language space, which reasons implicitly @xcite @xcite . while less flexible than language reasoning, symbolic reasoning is both interpretable and modular. future work should seek to improve the flexibility of symbolic reasoning @xcite . our work also represents a first step toward using general-purpose code as a representation for downstream dialogue and interaction tasks. future work might explore code-based representations that afford more flexible interaction with people, e.g., representing a broader range of user actions, both linguistic and grounded, to construct broadly useful interactive systems. an ideal system would be able to synthesize these representations with minimal manual intervention.