Symbolic Planning and Code Generation for Grounded Dialogue
Authors: Justin T Chiu
Wenting Zhao
Derek Chen
Saujas Vaduguru
Alexander M Rush
Daniel Fried
Venue: EMNLP 2023 Main (2023)
Keywords: dialogue
information
planning
code
grounding
TL;DR: A modular, grounded dialogue system that parses language to code and symbolically reasons over the results of code execution.

Abstract: Large language models (LLMs) excel at processing and generating 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.

Symbolic Planning and Code Generation for Grounded Dialogue
Justin T. Chiu
Wenting Zhao
Derek Chen
Cornell Tech j jtc257@cornell.co
Cornell University wz346@cornel1.cm
Columbia University dc3761 77761@columbia.... edu
Saujas Vaduguru Carnegie Mellon University svadugur@andrew. cmu. edu
Alexander M. Rush
Daniel Fried
Comeell Tech arush@cornell.cdm
Carnegie Mellon University dfriedêcs cmu edu
Abstract
Large language models (LLMs) excel pro- cessing and generating both text and code. However, LLMs have had limited applicabil- ity grounded task-oriented dialogue as they are difficult to steer toward task objectives and fail to handle novel grounding. We present 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 reader and planner: the reader leverages an L.LM to convert partner utterances into exe- cutable code, calling functions that perform grounding. The translated code's s output is stored to track dialogue state, while sym- bolic planner determines the next appropriate response. We evaluate our system's perfor- mance on the demanding ONECOMMON di- alogue task, involving collaborative reference resolution on abstract images scattered dots. Our system substantially outperforms the pre- vious state-of of-the-art including improving task success in human evaluations from 56% 69% in the most challenging setting.
SPC:
Do you see a pair dots, where the top left dot medium-sizee sizen and grey and bottom right dot is medium-sized and dark No
Human:
SPC:
Do you see a pair dots, where the top dot is small-sized and light and the bottom dot medium-sized and grey Yes I see them. Is there a small grey dot above the small light dot? No. Is there a large size and dark color dot to the left and below those?
Human:
SPC:
Human:
Yes and there is small grey dot helow them as well for me.
SPC:
Yes. Let's select the small size and light color
one.
SPC:
<select>
1 Introduction
Human:
<select>
Success in grounded task-oriented dialogue re- quires intentional communication guided by strate- gic planning (Cohen and Perrault, 1979; Traum, 1994; Walker et al., 2004; Rieser and Lemon, 2009; Bakhtin et al., 2022, inter alia). 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-to- end systems based solely on large language models (LLMs), this process is implicit and therefore diffi- cult to control, requiring extra supervision (Chris- tiano et al., 2023) expensive search (Lu al., 2022) improve. While recent work has taken steps to rectify implicit reasoning via planning in language space, where intermediate steps are gen- erated by an LLM (Wei et al., 2022), there is no
Figure I: An example grounded dialogue from ONECOMMON, Our dialogue agent, SPC. and human partner have difffernnt but overlapping circular views of shared board. The agent and partner must collaborate through dialogue order find and select a shared dot. ONECOMMON demands careful, grounded reasoning.
guarantee that these approaches result in plans that further task progress. Additionally, planning in lan- guage space is expensive, requiring inference in an LLM (Yarats and Lewis, 2017; Guez al., 2012).
Rather than implicit heuristic reasoning, are interested in explicit reasoning and planning over symbolic actions. Symbolic actions con- trollable by construction, allowing system design- ers to casily build task-specific knowledge (He et al., 2018; Bakhtin et al., 2022). This controlla-

---

bility is crucial for obtaining task-specific success using general tools, even with LLMs.
2 Related Work
Prior work collaborative reference games fo- cuses on building common ground (He et al., 2017; Haber et al., 2019; Khani et al., 2018). Prior work by Fried et al. (2021) implements an approxima- tion of pragmatic reasoning on ONECOMMON, but plans in language space and utilizes supervised models for mapping language to symbols. Khani et al. (2018) plan in symbolic space, but without natural language. We plan in symbolic space and map from language to symbols via code generation.
We provide an example from ONRCOMMON, a particularly challenging grounded dialogue game (Udagawa and Aizawa, 2019). The goal of ONECOMMON is to, through dialogue, identify one dot in common with your partner, who has an overlapping but different view of 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 gede-generttion for grounded language understanding (Dídac et al., 2023). 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 intermedi- ate representation: First, modern language models are trained mixture of code and natural lan- guage, affording them the capability of, with some accuracy, translating between the two (Chen et al., 2021). Second, code acts as a compositional knowl- edge representation. This allows code-gen sede-generation systems to perform grounded compositional rea- soning, provided a library of Python functions that perform grounding (Liang et al., 2022).
Dialogue systems have a long history of reason- ing with symbolic actions. When available, sym- bolic actions have been found to improve the per- formance of dialogue systems, especially in the set- ting of grounded dialogue (Winograd, 1971; Young, 2006; He et al., 2018; Andreas et al., 2020; Bakhtin et al., 2022). The closest work ours is CICERO, which utilizes symbolic planning in a system for DIPLOMACY, a dialogue and strategy game that requires negotiation and coordination between play- ers (Bakhtin et al., 2022). CICERO requires a su- pervised dataset to train their system. We use code LLMs which require minimal supervision beyond constructing small perceptual grounding API. Planning dialogue systems has recently es- chewed symbolic actions in favor of planning di- rectly in text, where systems either perform roll- outs, tree-search, or other forms of intermediate reasoning in language. This allows system design- ers to avoid manually defining symbolic actions (Yarats and Lewis, 2017; Jang et al., 2020; Gandhi et al., 2023). However, the accuracy of language- space planners is still low in many settings (Fried et al., 2021; Valmeekam et al., 2023). We focus on symbolic planning, where planning is defined in a space that ensures accuracy and controllability.
We present 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 (Yu al., 2019; White al., 2021; Chiu al., 2022). Symbolic planning allows SPC to explic- itly and efficiently optimize for task success while taking advantage of task-specific properties.
With the recent progress in large language mod- cling, code generation for modular grounded sys- tems 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 (Liang al., 2022; Didac et al., 2023; Gupta and Kembhavi, 2022; Gao al., 2023). This extends prior work on executable semantic parsing (Liang, 2016; Johnson et al., 2017: Cheng et al., 2018) with large language models. Concurrent work has also utilized code- onde-gennration to interpret language,
We evaluate our SPC system on the most chal- lenging subset of the ONECOMMON task, com- paring our system to the previous state-of-the art supervised system for the task (Fried et al., 2021). In both evaluations with human partners and auto- mated self-play evaluations, we find that our ap- proach substantially outperforms the previous state- of-the-art task accuracy, improving from 56% to 69% accuracy, and obtains comparable task accu- racy to human humann pairs on average.

---

integrated with symbolic reasoning (Wong et al., 2023). We apply these advances the setting of grounded task-oriented dialogue, where code gen- eration grounds language to symbolic actions for use in explicit planning.
n'. The agent then plans in symbolic space. The system uses reasoning to update its belief state, p(zlu) = (((l)))((()))) then produces a re- sponse y" of what to say next, which describes in language to the partner. There additionally a templated write module for generating response from y" described in Appendix C.
3 Overview: Reference Games
In ONECOMMON, given a set of dots D, the state {0, 1) represents which dots the agent be- lieves are contained (1) and not contained (0) in the partner's view, illustrated in Figure 3. We call set of dots configuration. The action representation of partner, æ and z', and agent utterances, y", alike is also a configuration {0, 13/2!, as well as any answers or confirmations to previous questions.
Collaborative reference games pair an agent and a partner in order to build common ground through natural language dialogue (Haber et al., 2019; Khani et al., 2018; He et al.. 2017; Udagawa and Aizawa, 2019). Mirroring realistic scenarios, many reference games are also partially observ- able, where the agent and partner have different perspectives, and so they must resolve ambiguity. ONECOMMON (Udagawa and Aizawa, 2019), as shown in Figure 1, is a reference game that exem- plifies two challenges: grounding and planning. In ONECOMMON, the agent and partner see different but overlapping views of set of dots, and the goal is to find and select one dot common to both play- ers' views. Grounding in ONECOMMON is particu- larly 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 complex referring expressions in order to avoid ambiguity. We focus on OnECOMMON due its simplicity and difficulty.
4 Reading: From Language to Symbols
Reading in SPC requires interpreting utterances to a grounded symbolic action, which in turn facili- tates the planning stage. Consider the following exchange:
Agent:
you see triangle of dark dots? Yes, is there small grey one below it?
Partner:
Reading has several challenges. First, reading requires grounding utterances in context, e.g. the shapes and relations. Second, utterances are com- positional. For example, the partner utterance builds on top of the previous utterance through coreference. Finally, reading system must act quickly, as real-time dialogue systems require rea- sonable response times.
Our approach to grounded reference games sep- arates 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 writ- ing. Reading and writing convert from language to symbols and vice versa, while planning reasons in purely symbolic space.
4.1 Code Generation
In SPC, reading is implemented as code generation. Given dialogue, we generate Python code2 which is then used meaning function to produce a distribution over all valid interpretations of the ut- terance's s symbolic action (Figure 2). The code calls perceptual library functions with grounded semantics, drawn from a task-specific API. This perceptual library allows the system to both ground elements of the utterance and compositionally build upon previous utterances. Consider the following abbreviated example, based ONECOMMON:
The agent maintains a belief distribution over possible worlds, representing task-specific un- knowns. The goal of dialogue is to gain informa- tion about until the agent is confident enough to end the game. At each turn, the agent reads the partner's s utterance u, converting into a symbolic action, p(z|z) u). This symbolic action potentially builds upon the action x' of previous utterance,
'The contexts in ONECOMMON were constructed to make referring expressions challenging and context-dependent. For example, if the agent sees only light dots, a relatively 'dark' dot for the agent may not be considered dark at all by the part- ner ONECOMMON is an ideal testbed for pragmatic methods that reason about contextual meaning. While our approach does not address pragmatics, we hope future work will.
We target Python as our code representation since is well-understood by large language models. However, in prin- ciple, our system could target other languages such as Prolog or SQL.

---

from perceptual_librat import is_small, dot1, dot2, dot3, ... get_dots()
ullerance:
big light a big
Agent: Do you
you see tringgee of dark dots?
Symbolio actions pix)
agent_configs set([
Config(dot1, dot2, dot3), Config(dot3, dot4, dot1)
})
Partner:
Ves, is there small grey one below it?
def
configs set()
Agant: "Yes. there smaler black one below them??
for prev_config in prev_configs:
for dot in (ugple__dottexcuddderreeo..ooooo
Partner utterance "No, but there is small grey dot below them..
if {
turn[prev_ddom
(d_tt)
and (5_try(ddot)
is_small...
and id_belowddot, prev_config)
is_grey-..
):
(e.beloo(dot, prev_dott)
add prev_config))
return configs
configs
partner_configs. turn(agent_confiss)
Symbcolic actions p(xuu
The code in the meaning function is imperative, but represents a set of declarative constraints represent- ing p(z/()))) u.. The meaning function for the partner turn, turn(prev__oott igs), takes input the dis- tribution symbolic actions of previous turn, p(x'), ), and yields of possible interpretations of the current turn, p(z|u) = Σx p(a) u, .r')'') p()))))") Because utterances can have multiple valid interpre- tations due to ambiguity, prev_configs represents a distribution."
Figure 2: Overview of Reading. The generated meaning function for utterance u takes the previous symbolic action distribution p(x') from prior turn and yields the interpretations p(z/u). using code as a compositional representation (Section 4).
Within turn, we consider all valid configura- tions while marginalizing over x', i.e. interpreta- tions in prev_configg. For each interpretation, each dot is considered. If the new dot satisfies the semantics of the utterance, checked step-by-step via grounded perceptual library functions such as is small (d), then it is valid interpretation of the current utterance and is used to create Config.
found here.
4.2 Prompting
Reading is implemented with large language model (LLM) code generation. While LLMs can generate accurate code, full code specifications (Section 4.1) are lengthy and therefore too slow to generate for real-time use. We break down code generation into four steps, where some steps do require any calls to an L.M.. Decreasing the number of output tokens guarantees a speedup, assuming consistent latency. See the code for details on the code LLM and prompts we use.
The perceptual library functions are drawn from a manually-defin library. For ONECOMMON, we define these functions using domain-specific knowledge:
def (d): return d.size < -0.3
Dialogue Act: Classify partner utterances three dialogue acts: Start a NEW line of questioning. ask FOLLOW-UP question, END the dialogue. Reference: Predict which previous turn x' the utter- ance is following up on, if any:
of
The perceptual library for ONECOMMON can be
"In ONECOMMON, the distribution over symbolic actions p(r/u) is represented as represented categorical distrihu- tion configurations with probabilities based on the size of the circumeircle.
Agent: Do you triangle?
'The symbolic action of previous turn x' may also depend other previous utterances u'. For simplicity, we omit that notation.
Pattnr: Yes, is there small grey dot below it?
dialogue act: follow-up
SSPC able to intentionally produce ambiguous descrip- tions if that improves task success, as illustrated in this exam- plc.
refer: turn
"We release the code here.

---

The system grounds the dots mentioned in the pre- vious turm: agent_configs, which is stored by the system. This allows referring to other turns besides the previous.
mate:
p(zlu)= = Σ p(2lx))p(olu)
Σ plalz)p(2) p(r|u)
Constraint Generation: Predict the new dots men- tioned in the partner utterance alongside code frag- ments that express the semantics, without the boil- erplate code, in the example above:
p(x)
(1)
p(zlz)p(z)
1 (x = x²)
p(x)
a
x p(x" =)p(z2),
Partner: Yes, there small grey one below it?
new dot is_ sm__smll(00 (dot) (dot)
where x² arginxx p(x]uu).
We give an example of this process in Figure 3. In this case, a 'big light dot next to a big dark one' could have two valid interpretations, the big light dot and the black dot to the left, or the other black dot to the right. We approximate this distribution with the most likely interpretation x². . In ONECOM- MON,
(ddtbelowddo,, prev_dats)
Compose: Finally, we utilize a template to com- pose all of this information back into the full code representation for execution.
the most compact' as x², yielding the black dot on the left. The belief state is then updated to p(zlu), shown in Figure 3 (center).
5 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 infor- mation has been gathered so far, well what to say next. SPC addresses these desiderata by plan- ning in symbolic space, over the symbolic actions produced by reading.
5.2 Planning
Given the updated belief, SPC then plans its next action. The challenge here to ensure task success, e.g. finding one dot in common. This requires both exploring by building common ground, then exploiting that knowledge to win the game.
We formalize exploration as the expected infor- mation gain, quantity that codifies how much the agent can expect to learn about possible worlds a after taking an action (Lindley, 1956). That action then elicits a response from the partner, providing information about the uncertain world state. For example, if the agent has asked about set of dots and already received a 'no', then asking further questions about those dots would not reduce uncer- tainty.
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 informa- tion, the system must decide either to end the game how improve the probability of success.
Planning requires us model the actions of the partner given the shared state. To do this we need task specific models of our partner, p(r 2). and our partner's reponse to us, p(0|z,8) v). In ONECOM- MON, we model both of these by a heuristic func- tion considering set overlap and dot proximity, de- scribed in Appendix D.
Formally, we optimize
y" = argmax H [z|u]] - Engly [H u, y, xyll
(2)
where H[2 u/] is the entropy of the current belief* and H[2 u, y, zyl the entropy of the posterior distribution. This second term is the key part of the objective. Assuming that we take action y. the expectation considers all hypothetical future
5.1 Belief update
Starting from prior over the previous belief p(z), we incorporate probabilistic evidence from the ut- terance p(x/1). This requires marginalizing over all valid symbolic actions æ from the reading step. practice, p(z|u) is sparse, and symbols with non-zero support are very similar. We therefore approximate this marginalization with a point esti-
We define the compactness a configuration as the radius of the circumeirele. An ideal approximation would take into account more context, such as the relative sizes.
"The belief entropy H [2| in the definition of information gain is constant with respect to the plan .r, and can be dropped from the objoctive.

---

Previous ballef state p(z)
Bellef state p(zlu)
Bellel update
Q.1
0.3
Partner eymbolic actiona pb(u)
Agent symbalic action
:
Read
Write
Partner ufterance u:: "Is there big light dot ned to a big dark one?"
Agent: "Yas. there a smaller black one bekow them??
Figure 3: Overview of Planning. Partner utterances are interpreted by meaning function generated by a code LLM (read), producing distribution valid symbolic interpretations, p(z This is used symbolically update the belief state, p(z(u), increasing the probability of worlds (shared dots) that are consistent with æ. This belief state is used to symbolically plan the agent's next utterance, y", by optimizing the expected information gain, which is described to the partner (write).
partner responses Ty. We are penalized if after sceing these responses, we are still uncertain about the common ground 2. This objective therefore encourages actions that reduce uncertainty. 9
utterances and a range of strategies of human part- ners. We recruit 19 workers from Amazon's s Me- chanical Turk to play with one of three partners: SPC, the most successful past system for the task (Fried et al., 2021), or another human. We pay $15 per hour, with $1.00 per game at average of 4 minutes per game. We additionally give bonus of $0.15 for every game. We 100 visual contexts from the most difficult partition of ONECOM- MON. We pay workers $1.00 per game, with a $0.15 bonus they win. We collect 287 completed dialogues in total, where both players selected a dot.
SPC chooses to exploit and end the game with the following heuristic: If the system is confident in success, i.e. the probability of task success is greater than hyperparameter 0 (set 0.8), SPC ends the game.
6 Experimental Setup
We conduct two evaluations of SPC on the ONECOMMON task. We compare to the state-of- the-art baseline system of Fried et al. (2021), which we refer to as Imitate. Imitate is pipelined system, where each part is fully supervised. Imitate uses neural representation of dialogue history in com- bination with neural-CRI reference resolution module to understand grounded language. In order to generate, Imitate relies on pragmatic planning procedure, which plans in a mixture of symbolic and language space, prioritizing descriptions of dots that are casily understood.
We secondarily evaluate systems in self-play, where systems are paired with 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! which gets two full human dia- logues examples. Each human dialogue example starts with description of the context the agent sees. The full prompts can be viewed here.
We first perform human evaluation, evaluating the task success of systems when paired with hu- man partners. This setting is challenging, requiring the system to handle both the linguistically diverse
For code generation, during the reading phase we use GPT-412 (OpenAI, 2023).
Parameterization
'Thhe number of shared dots is four.
"We do not include GPT4 2-shot in human evaluation, as its self-play evaluation is very poor. 12Specifically gpt-4-0613.
"The distribution p(>xly) = E. p(aylu. 2)p(z) also uses the partner response model p(x,1u..). 2).

---

Agent
Success
Turns
Games
100%
Human
SPC
68.8%
7.77
96
Imitate
SPC
Imitate
55.6%
6.61
117
Success Rate
Human 67.6%
5.03
74
80%
Human 65.8%
4.97
2,189
70%
Table 1:
The average success rate, average number turns, and total number of games between agents and human partners the hardest setting of ONECOM- MON, with 4 shared dots. indicates statistics from the ONECOMMON dataset (Udagawa and Aizawa, 2019).
60%
50%
0%
20%
40%
60%
80%
100%
Minimum Human-Human Success
Figure 4: Success rate of the different agent types with human partners, with progressive filtering of human partners by their success rate along the x-axis, Shaded regions give standard erros.
The symbolic actions in ONECOMMON consist of sets of dots and confirmations, while the belief over symbolic states, p(2), captures which dot con- figurations are shared and is designed to account for dot proximity. Further details on the prior are given in Appendix D. The symbolic partner models, p(z 2) and p( V, z), are drawn from Chiu et al. (2022), and incorporate similar bias based on dot proximity.
Agent
Avg |u]
Median [u]
SPC
6.95
Imitate
9.62
8
Human 15.06
14
Table 2: The average and median number of words per utterance by human partners for different agent types in human evaluation.
7 Results
Human evaluation In human evaluation, SPC obtains substantially higher task accuracy than the baseline model of Fried et al. (2021), and is com- parable to human performance on average. This demonstrates that the combination of symbolic information gain planning and code-generation in SPC is more effective than the baseline's language- space planning objective and supervised reference resolution.
the baseline and human- games. We hy- pothesize that this difference caused by shorter human partner responses to the system, and there- fore less information shared by the human partner. In Table 2, we confirm that the average and median number of words per human utterance are signifi- cantly lower for humans partnered with SPC than any other agent type.
We see a more nuanced story when conducting a skill-based analysis of the human evaluation results, presented in Figure 4. A worker's s skill is given by their average success rate with other human part- ners. The x-axis of the graph, the minimum success rate, increasingly filters workers from left right: the left side of the graph shows all workers, while the far right shows only those workers who won nearly of their human-human games. Skilled hu- man partners have a higher success rate with other humans, as opposed to when partnered with SPC. Additionally, the success rate of SPC improves with human skill, while the success rate of human partners with the baseline system, Imitate, remains relatively constant across skill levels, implying that SPC is more responsive than the baseline strate- gies used by humans.
Self-play Similarly to human evaluation, SPC outperforms the baseline Imitate system in self- play shown in Table 3. Compared to the baseline. SPC takes more turns average, but has higher success rate. We attribute both the longer games and higher success to symbolic planning, which ensures conservative playing. Interestingly, SPC self-play takes fewer turns on average than SPC- human pairings. We hypothesize that this is due to both copies of SPC communicating a consistent amount of information every turn. This also high- lights the importance of human evaluation, which evaluates with a large population of partners.
We also find that GPT4 2-shot performs poorly in self-play. We attribute this to werll--greeabble responses, where the agents choose a dot without
SPC also takes more turns on average than both

---

Agent
Success
Avg # turns
SPC
84.0%
4.83
Imitate 63.5%
3.31
GPT4 2-shot 19.0%
9.26
Human
65.8%
4.97
Table 3:
The success rate of different agents in 200 self- play games on the hardest setting of ONECOMMON, with 4 shared dots. A higher success human performance is from the ONECOMMON dataset (Udagawa and Aizawa, 2019).
better. The
Prompt style
Acc
Time (s)
Len
SPC:
Do you see a pair of dots, where the bottom dot is medium-sized and dark and the top dot is small-sized and light No. Do you see pair of medium sized dots, close together, one is dark grey the other light grey. The light grey one slightly above and the left of the dark one. No. Do you is mediium-sized and dark and the right dot
SPC
86.7%
5
36
Full
84.0%
18
176
Human:
Table 4: The average accuracy, speed, and output length (number of tokens) for the sequential and full code gen- eration methods our benchmark reading task.
SPC:
puir of dots, where the left dot
thorough verification reasoning. This occurs despite the much longer dialogues, in comparison all other agent types.
redium--sized and light
Human:
No, do see lonc medium sized grey dot? No. Do you pair of dots, where the left dot is medium-sizes and light and the right dot is small-sized and grey
SPC:
Human: No. do you see a pair where the right one is medium and grey and the left one smaller and lighter. The smaller medium sized Yes. Is there medium size and light color dot the right and below those?
8 Analysis
is slightly below the
Qualitative analysis We present a qualitative ex- ample of dialogue between SPC and 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 deduce the shared configu- rations. Eventually, a common set of dots is found and the game ends success. Without explicit planning, it would have been unlikely for SPC to have succeeded at the end of the conversation.
SPC:
Human: Yes
SPC: Lett' select the medium size and grey color
Human: <select>
SPC: <select>
Figure 5: An example dialogue between SPC and human partner.
Conclusion
Reading speed analysis We perform a speed ab- lation of the oode-generation prompt in SPC. SPC uses a sequence of steps for reading, involving dia- logue act classification, code fragment generation, and composing the full code representation based the output of these steps. We compare this to prompt that generates the full meaning function.
We present Symbolic Planning and Code- generation (SPC), a method that approaches grounded task-oriented dialogue by separating sym- bolic reasoning from language. Our approach uses an LLM to generate executable code functions which represent the meaning of utterances, map- ping 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. De- spite using minimal supervision, beyond a task- specific API and few-shot examples, our approach substantially outperforms the state-of-the-ar sys- tem for the ONECOMMON task in both human eval-
We evaluate both of these prompts in reading task, where the goal is to read utterances generated by SPC and recover the underlying plans, measured by accuracy. In Table we see that both styles of prompts have similar similar accuracy, but the sequential, decomposed approach is much faster due to shorter outputs.

---

uations and automatic self-play evaluations. Our work contrasts with recent work on plan- ning in language space, which rcasons implicitly (Wei et al., 2022; Yarats and Lewis, 2017; Guez et al., 2012), While less flexible than language rea- soning, symbolie reasoning is both interpretable and modular. Future work should seek to improve the flexibility of symbolic reasoning (Wong et al., 2023).
DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Christo- pher H. Lin, Ilya Lintsbakh, Andy McGovern, Alek- sandr Nisnevich, Adam Pauls, Dmitrij Petters, Brent Read, Dan Roth, Subhro Roy, Jesse Rusak, Beth Short, Div Slomin. Ben Snyder. Stephon Striplin, Yu Su, Zachary Tellman, Sam Thomson, Andrei Vorobev, Izabela Witoszko, Jason Andrew Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020. Task-oriented dialogue as dataflow synthesis. CoRR, abs/2009. 1423.
Our work also represents a first step toward us- ing 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 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.
Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Damiel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, Athul Paul Jacob, Mo- jtaba Komeili, Karthik Konath, Minae Kwon, Adam Lerer, Mike Lewis, Alexander H. Miller, Sasha Mitts, Adithya Renduchintala. Stephen Roller, Dirk Rowe, Weiyan Shi, Joe Spisak, Alexander Wei. David Wu. Hugh Zhang, and Markus Zijlstra. 2022. Human- level play in the game of diplomacy by combining language models with strategic reasoning. Science, 378(6624); 1067-1074.
Acknowledgements
We thank Vivian Chen, Sanjiban Choudhury, Ge Gao, Omer Gul, Sedrick Keh, Woojeong Kim, Ce- line Lee, Jack Morris, Chenran Ning, Jacob Sharf, Alane Suhr, Nicholas Tomlin, Anne Wu, and Jiawei Zhou for discussions, game-playing, and feedback various points in the process.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Ka- plan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman. Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sas- try, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder. Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter. Philippe Tillet, Felipe Petroski Such, Dave Cum- mings, Matthias Plappert, Fotios Chantzis, Eliza- beth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin. Suchir Balaji. Shantanu Jain. William Saunders. Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage. Mira Murati, Katie Mayer, Peter Welinder. Bob McGrew, Dario Amodei, Sam McCandlish, Πlya Sutskever, and Wojeiech Zaremba. 2021. Evaluating large language models trained code.
We also thank the Mechanical Turkers of Turker Nation for their efforts in same-playing
JC is supported by NSF #2242302. AMR is sup- ported by Sloan Fellowship and NSF CAREER #2037519. SV and DF were supported by gifts from Google and from Autodesk Research.
Limitations
Our system performs code execution given human input, opening our system to several risks, such as code injection and unauthorized access. Future work must strive to integrate code execution capa- bilities in a secure manner.
Jianpeng Cheng, Siva Reddy, Vijay Saraswat, and Mirella Lapata. 2018. Learning an executable neural semantic parser.
Our approach also requires the manual engineer- ing of a Nomainn-specifi API, as well as a symbolic representation. Future work should seek to alle- viate the amount of manual engineering in order improve flexibility. We hope that methods in program synthesis can provide a solution.
Justin T Chiu, Wenting Zhao, Daniel Fried, and Alexan- der M Rush. 2022. Modeling perspective-dependent ambiguity in collaborative dialogue. In The Thind Wordplay: When Language Meets Games Workshop.
Paul Christiano, Jan Leike, Tom B. Brown, Miljan Mar- tic, Shane Legg, and Dario Amodei. 2023. Deep reinforcement learning from human preferences.
References
Philip R. Cohen and C. Raymond Perrault. 1979. Ele- ments of a blan- theory of speech acts Cogni- live Science.
Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan

---

Surís Dídac, Sachit Menon, and Carl Vondrick. 2023. Vipergpt: Visual inference via python execution for reasoning. arXiv preprint ar 2303.2303..8
Percy Liang. 2016. Learning executable semantic parsers for natural language understanding.
D. Lindley. 1956. On a Measure of the Information Provided by an Experiment. The Annals of Mathe- matical Statistics, 27(4):986 1005.
Daniel Fried, Justin T. Chiu, and Dan Klein. 2021. Reference-centric models for grounded collaborative dialogue. In Proceedings of EMNLP.
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang. Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lian- hui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. 2022. Neurologic a aeequue decoding: Constrained text generation with lookahead heuris- tics.
Kanishk Gandhi. Dorsa Sadigh, and Noah D. Goodman. 2023. Strategic reasoning with language models.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Gra- ham Neubig. 2023. Pal: Program-aided language models.
OpenAL. 2023. Gpt-4 technical report.
Verena Rieser and Oliver Lemon. 2009. Natural lan- guage generation as planning under uncertainty for spoken dialogue systems. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACI 2009), pages 683-691, Athens, Greece, Asso- ciation for Computational Linguistics.
Arthur Guez, David Silver, and Peter Dayan. 2012. Ef- ficient bayes-adaptive reinforcement learning using sample-hased search. CoRR, abs/I 205.3
Tanmay Gupta and Aniruddha Kembhavi. 2022. Vi- sual programming: Compositional visual reasoning without training.
David Traum. 1994. A computational theory of grounding in natural language conversation. Techni- cal report, Rochester University Department of Com- puter Science.
Janosch Haber, Tim Baumgärtner, Ece Takmaz, Licke Gelderloos, Elia Bruni, and Raquel Fernández. 2019. The photobook dataset: Building common ground through visually- grounded dialogue. CoRR, abs/1906.01530.
Takuma Udagawa and Akiko Aizawa. 2019. natural language corpus of common grounding under contin- uous and purtially-obeerablle context. Proceedings of the AAAI Conference on Artificial Intelligence. (3(01))7120-7127.
He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. 2017. Learning symmetric collaborative dia- logue agents with dynamic knowledge graph embed- dings. CoRR, abs/1704.07130.
Karthik Valmeekam, Sarath Sreedharan, Matthew Mar- quez, Alberto Olmo, and Subbarao Kambhampati. 2023. On the planning abilities of large language models (a critical investigation with a proposed benchmark).
He He, Derek Chen, Anusha Balakrishnan, and Percy Liang. 2018. Decoupling strategy and generation in negotiation dialogues. CoRR, abs/1 (bss/180.000 09637.
Youngsoo Jang, Jongmin Lee, and Kee-Eungg Kim. 2020. Bayes-adaptive monte-carlo planning and learning for goal-oriented dialogues. In The F'urrty-Forrhh AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-1 2020, pages 7994-8001. AAAI Press.
M A Walker, S Whittaker, A Stent, P Maloor, Moore, M Johnston, and G Vasireddy. 2004. Generation and evaluation of user tailored responses in multimodal dialogue. Cognitive Science, 28(5):811-88)
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed H. Chi, Quoe Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. CORR, abs/2201.11903.
Julia White, Gabriel Poesia, Robert Hawkins, Dorsa Sadigh, and Noah Goodman. 2021. Open-domain clarification question generation without question ex- amples. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 563-570, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Judy Hoffman, Li Fei-Fei, C. Lawrence Zit- nick, and Ross Girshick. 2017. Inferring and execut- ing programs for visual reasoning.
Fereshte Khani, Noah Goodman, and Perey Liang. 2018. Planning, inference and pragmatics sequential lan- guage games. Transactions of the Association for Computational Linguistics, 6:543-555.
Terry Winograd. 1971. Procedures a representation for data in a computer program for understanding natural language.
Jacky Liang, Wenlong Huang. Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng, 2022. Code policies: Language model programs for embodied control. arXiv preprint arXiv:2209.0753..
Lionel Wong, Gabriel Grand, Alexander K. Lew, Noah D. Goodman, Vikash K. Mansinghka, Jacob Andreas, and Joshua B. Tenenbaum. 2023. From word models to world models: Translating from natu- ral language to the probabilistic language of thought.

---

Denis Yarats and Mike Lewis. 2017. Hierarchical text generation and planning for strategic dialogue. CoRR, abs/ 12.05846.
C Writing
We utilize three templates for writing, one for each dialogue act.
Steve Young. 2006. Using pomdps for dialog manage- ment. In 2006 IEEE Spoken Language Technology Workshop, pages 8-13.
START: Do you see pair of dots, where the (position) dot is (size)-sized and {color} and the (position] dot is (size)-sized and {color)?
Lili Yu, Howard Chen, Sida I. Wang, Yoav Artzi, and Tao Lei. 2019. Interactive classification by asking informative questions. CoRR, 10ss/1911033999
FOLLOW-UP: Is there {size} size and {color} color dot (position) those? SELECT: Let's select the {size} size and {color) color one. <selection>
A Prompt details
All prompts rely on few-shot prompting. Refor- mat has 5 few-shot examples, Classify has two dialogues with 15-turns total, Confirm has 9 exam- ples, and Understand has two dialogues with 15 turns total. All examples examples from the human-human games collected in OneCommon by Udagawa and Aizawa (2019). The same prompts were used in every context. The full prompts can be found here.
D Parameterization
We give the parameterization of the belief prior, p(z) for ONECOMMON.
based loosely 10
Our goal in designing the prior is to ensure that the closer dots are, the more likely they are to be the same state: either all shared or not. This reflects
the contiguity of ONECOMMON perspectives.
The prior is given by
B Prompt ablation
p(2) x exp(f(=)):
(3)
We present an additional experiment on how the choice of fho-shot examples affects the code con- straint generation prompt, which is key compo- nent of the reading step. The code constraints press the relationships between the mentioned dots, e.g. whether they form triangle or their relative positions, shapes, and colors.
where f(2) is given the sum of the edges of a mini- mum spanning tree for the dots in 2. The weights of this spanning tree are determined by the rank of how close the dots are each other. The edge between the nearest neighbor of dot and the dot itself gets assigned weight of O, the 2nd nearest neighbor a weight of 1, and so on.
We take the first human utterance from 20 games in human evaluation and examine whether the parsed answer changes when the prompt examples are changed. The 15 examples in the constraint generation prompt were labeled by hand. Since we cannot sample another examples, we instead sub-sample random examples out 15 for a 5-shot prompt. We report the average agreement between 5-shot prompts and the original 15-shot prompt across 5 trials: 99%, with standard devia- tion of 2%. This implies the constraint generation prompt is not sensitive to prompt example choice the 5-shot level and prompts could be further optimized.
E Relation to prior work in semantic parsing and dialogue state tracking
Prior work in semantic parsing for dialogue state tracking, such as in SMCalFlow (Andreas et al., 2020), does not ground in a visual context and also requires strategic, collaborative planning due to OneCommon's 's symmetric roles. Agents must both give and request information strategically. This type of strategic reasoning is not explored in prior works in semantic parsing and dialogue state tracking. Our technical contribution is unify- ing grounded language understanding and strategic symbolic reasoning with code generation. In par- ticular, the reading phase of SPC was designed for spatial reasoning in OneCommon.
We perform the same experiment with 5 trials of 1-shot prompts and see an average agreement rate of 34% with standard deviation of 42%. This implies that given single example, the prompt example matters.
We also find that a zero-shot prompt is unable to generate output in the correct format.


Reviews:
[{"review_id": "SBMWVcoqdu", "reviewer": "Reviewer_mUba", "summary": "", "questions": "- A.) In Fig. 4, the mean success rate of SPC seems to be constantly above 70%, and going above 80% with skilled partners. How come the mean success rate reported in Table 1 is 68.8%?\n- B.) Do you have a hypothesis for why the utterances of human partners were so much shorter when interacting with SPC than with Imitate? Does it have to do with the type of responses/questions each of these systems uses?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We are encouraged that reviewer mUba found that the examples and diagrams were helpful and made the task and method easy to understand. We will include all clarifications below in the next version:\n\n## Prompts\nWe apologize for not including examples of the prompts in the original submission. For reproducibility, the code and data for generating the prompts was included in the supplementary material. We provide anonymized links containing an example of each prompt and a pointer to the generating Jinja template in the supplementary material.\n\nFull prompt\n* Template: `oc-anon/oc/prompts/understand5.j2`\n* Link: https://pastebin.com/x8dxj4tz\n\nSPC prompts\n\nReformat: Rewrite partner utterances to correct typos and formatting.\n* Template: `oc-anon/oc/prompts/reformat.j2`\n* Example: https://pastebin.com/uTeP8nZE\n\nClassify: Classify the dialogue act and any reference to previous turns.\n* Template: `oc-anon/oc/prompts/classify2.j2`\n* Example: https://pastebin.com/FFY8APRX\n\nConfirm: Classify whether the partner said yes or no to a previous question.\n* Template: `oc-anon/oc/prompts/confirm.j2`\n* Example: https://pastebin.com/YpTiTkSD\n\nConstraint generation: Generate the constraints.\n* Template: `oc-anon/oc/prompts/understandshort2.j2`\n* Example: https://pastebin.com/ube83h3n\n\nExecution template: Take the output of previous prompts and turn them into a program.\n* Template: `oc-anon/oc/prompts/executeshort2.j2`\n* Example: https://pastebin.com/JJvGAtyU\n\n## Prompt details\nAll prompts rely on few-shot prompting. Reformat has 5 few-shot examples, Classify has two dialogues with 15-turns total, Confirm has 9 examples, and Understand has two dialogues with 15 turns total. All examples were based loosely on 10 examples from the human-human games collected in OneCommon by Udagawa and Aizawa. The same prompts were used in every context.\n\n## How the choice of prompt examples affects accuracy\nWe found that a zero-shot prompt was not able to generate output in the correct format, and therefore did not investigate further.\n\nWe ran an additional experiment to evaluate how the choice of examples affects the code constraint generation prompt. We take the first human utterance from 20 games in human evaluation and examine whether the parsed answer changes when the prompt examples are changed. The 15 examples in the constraint generation prompt were labeled by hand. Since we cannot sample another 15 examples, we instead sub-sample 5 random examples out of 15. We report the average agreement between 5-shot prompts and the original 15-shot prompt across 5 trials: 99%, with a standard deviation of 2%. This implies the constraint generation prompt is not sensitive to prompt example choice at the 5-shot level and prompts could be further optimized.\n\nWe perform the same experiment with 5 trials of 1-shot prompts, and see an average agreement rate of 34% with a standard deviation of 42%. This implies that given a single example, the prompt example matters.\n\n## 5 seconds per response is slow\nThe 5 second response time for SPC is comparable to the median typing time of 8.16 seconds per turn for humans in OneCommon, and could be further improved by running open models locally, such as StarCoder, for scenarios that require it.\n\n## Difference in median length of human responses with human-human games\nWe hypothesize that the difference in median length of human responses with human and SPC partners is caused by the template generation system in SPC. The template generation system asks questions that expect a yes or no answer without requesting other information from partners, allowing for shorter responses. A positive effect of SPC’s strategy is that humans require less effort overall to reach a similar success rate. We estimate human effort by the total number of human response words. The SPC strategy leads to shorter human responses and more turns, resulting in fewer human response words overall ($7.77$ turns $/ 2 * 6.95$ words $= 27.0 < 37.8 = 5.03$ turns $/ 2 * 15.06$ words, numbers from Tables 1 and 2).\n\n## Difference in length of human responses with Imitate\nWe hypothesize that the difference in human response length between SPC and the Imitate baseline was caused by the baseline requiring more effort and words from the partner in order to achieve success.\n\n## Success rate for SPC in Fig 4 exceeding Table 1\nThank you for catching this. The difference in the average success rate between the table and skill-based graph in Fig. 4 results from filtering out players who did not win any games for Fig. 4. This results in slightly higher success rates in Fig 4, which were greater than 70% opposed to 68.8% in Table 1. We will explain this in the next version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The proposed method goes seamlessly between language space and symbolic space while utilizing an LLM. Performing the planning/reasoning explicitly in symbolic space, maximizing an information gain objective, is more effective than planning performed in language space as previous work has done when employing language models for this task.\n- A lot of illustrative examples and diagrams that make the understanding of the task and the method easy.\n- Reducing the code generated by the LLM down to just the set of the necessary predicates representing the essential information, in order to speed up the generation.\n- Outperforming the previous SOTA approach by a large margin in a human evaluation (69% vs. 56% success rate).\n- The performance of SPC actually steadily improves with the increasing skill of the human partner (which is the opposite of the previous SOTA method's behavior).", "reasons_to_reject": "- There is no description whatsoever of how the LLM is prompted to produce the code fragments. Presumably, some examples are provided, as the LLM would probably not do a good job in a zero-shot setting. However, we don't know how many examples were provided in the prompt, how complex they were, and whether it was always the same set of examples or varied based on the context. The choice of examples in the prompt probably also affects the accuracy, but we don't know to what extent.\n- The reading phase (~ 5 seconds on average) is still rather slow for real-time application.\n- The median number of words per utterance by human partners interacting with SPC is merely a third of the median of the utterances in human-human interactions (4 vs. 14 words). While this does not necessarily mean anything bad, the large difference makes me wonder if the interaction with SPC feels very unnatural. Perhaps SPC is too controlling the way it asks questions (perhaps with most humans simply responding \"yes\" or \"no\") and could benefit from an improved response generation to allow for more user initiaitve.", "questions_to_authors": "- A.) In Fig. 4, the mean success rate of SPC seems to be constantly above 70%, and going above 80% with skilled partners. How come the mean success rate reported in Table 1 is 68.8%?\n- B.) Do you have a hypothesis for why the utterances of human partners were so much shorter when interacting with SPC than with Imitate? Does it have to do with the type of responses/questions each of these systems uses?", "paper_topic_and_main_contributions": "This paper introduces Symbolic Planning and Code-generation (SPC), a new method for grounded task-oriented dialogue. It is applied to the OneCommon task, which involves collaborative reference resolution on images of scattered dots, with each of the dialogue system and the human partner seeing a different subset of the dots (but overlapping). SPC utilizes an LLM (GPT-4 in this case) to understand the human partner's utterances and generate code that is subsequently used in the planning stage performed in symbolic space rather than language space. Templates are then used to go back from the symbolic space to language and generate a response. Human evaluation shows this method to greatly outperform the previous SOTA method. Self-play experiments show an even bigger performance difference between SPC and the previous SOTA method.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- L212: extra \"an\"\n- Footnote 1 on page 4: \"represented as\" repeated twice\n- L486: \"similar\" repeated twice"}, "extra_text": {}}, {"review_id": "GkNRaEZRKo", "reviewer": "Reviewer_soD2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We value reviewer soD2's positive perspective on the convincing human evaluation results and the promising aspect of not needing model training. We will include all clarifications below in the next version:\n\n## Prompts\nWe apologize for not including examples of the prompts in the original submission. For reproducibility, the code and data for generating the prompts was included in the supplementary material. We provide anonymized links containing an example of each prompt and a pointer to the generating Jinja template in the supplementary material.\n\nFull prompt\n* Template: `oc-anon/oc/prompts/understand5.j2`\n* Link: https://pastebin.com/x8dxj4tz\n\nSPC prompts\n\nReformat: Rewrite partner utterances to correct typos and formatting.\n* Template: `oc-anon/oc/prompts/reformat.j2`\n* Example: https://pastebin.com/uTeP8nZE\n\nClassify: Classify the dialogue act and any reference to previous turns.\n* Template: `oc-anon/oc/prompts/classify2.j2`\n* Example: https://pastebin.com/FFY8APRX\n\nConfirm: Classify whether the partner said yes or no to a previous question.\n* Template: `oc-anon/oc/prompts/confirm.j2`\n* Example: https://pastebin.com/YpTiTkSD\n\nConstraint generation: Generate the constraints.\n* Template: `oc-anon/oc/prompts/understandshort2.j2`\n* Example: https://pastebin.com/ube83h3n\n\nExecution template: Take the output of previous prompts and turn them into a program.\n* Template: `oc-anon/oc/prompts/executeshort2.j2`\n* Example: https://pastebin.com/JJvGAtyU\n\n## Real-world applications require context-dependent meaning\nWe agree that real-world applications require context-dependent meaning. OneCommon was designed as a testbed for context-dependent dialogue systems. In particular, size and color words in OneCommon refer to a wide and overlapping range of values that depend on context [1]. SPC does not take advantage of this directly, and we believe doing so would improve the accuracy of SPC. Future work could extend SPC with pragmatic meaning inference by moving from deterministic code as a meaning function to probabilistic programs, where size and color are represented as thresholds over a context-dependent random variable that must be inferred through interaction. Applying pragmatics through SPC would afford modularity, allowing the model to separately reason about size and color.\n\n## Marginalization over actions is intractable in real-world applications\nWe think there does exist important real-world tasks, such as image retrieval over a thousand candidate images, where exact marginalization over actions, images in the case of image retrieval, is indeed tractable. In more general settings, marginalization may be intractable. Prior work suggests that SPC like method could be generalized to such settings with approximate inference [2,3].\n\n## Generalization to richer tasks\nWe agree that future work should focus on applying the method to richer tasks, as well as decreasing the amount of manual effort required to craft a perception library. However, OneCommon is a challenging testbed for grounded dialogue as it is both simple and challenging. It emphasizes two important phenomena in grounded dialogue: spatial reasoning and context-dependent language understanding.\n\n## Relation to prior work in semantic parsing and dialogue state tracking\nOur technical contribution is unifying grounded language understanding and strategic symbolic reasoning with code generation. In particular, the reading phase of SPC was designed for OneCommon, which requires spatial reasoning. Prior work in semantic parsing for dialogue state tracking, such as in SMCalFlow [4], does not ground in a visual context and also requires strategic, collaborative planning due to OneCommon’s symmetric roles. Agents must both give and request information strategically. This type of strategic reasoning is not explored in prior works in semantic parsing and dialogue state tracking.\n\n## Python as a code representation\nWe target Python as it is more flexible than domain specific languages and is well-understood by large language models. However, our decomposed prompts in particular do not rely on knowledge of Python, and could target other languages such as SQL.\n\n[1] Takuma Udagawa, Takato Yamazaki, and Akiko Aizawa. 2020. “A Linguistic Analysis of Visually Grounded Dialogues Based on Spatial Expressions.” In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 750–765, Online. Association for Computational Linguistics.\n\n[2] Foster, Adam et al. “Deep Adaptive Design: Amortizing Sequential Bayesian Experimental Design.” International Conference on Machine Learning (2021).\n\n[3] Kevin Swersky, Yulia Rubanova, David Dohan, Kevin Murphy. “Amortized Bayesian Optimization over Discrete Spaces.” Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), PMLR 124:769-778, 2020.\n\n[4] Andreas, Jacob et al. “Task-Oriented Dialogue as Dataflow Synthesis.” Transactions of the Association for Computational Linguistics 8 (2020): 556-571.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The main reason to accept is that the method is effective for the proposed task, achieving near human performance across all partners, and showing that it can adapt to advanced strategies adopted by humans who are highly successful at this task. Additionally, the method leverages the intrinsic ability of modern LLMs and does not require any new training.", "reasons_to_reject": "The main weakness, which admittedly is also discussed as a limitation in the paper, is that the proposed method appears to only be realistically applicable to the OneCommon task, and not to more useful real-world grounding tasks.\nIn particular, the proposed method requires a hand-engineered library of primitive symbolic checks that can be efficiently computed in Python. It is unclear in which real-world settings this would be possible, for a number of reasons, including the inherent ambiguity and context dependence of concepts such as \"small\" or \"large\", and the fact that such a check might be non trivial to implement for, say, a picture of physical objects rather than an artificial collection of shapes.\nSecond, the proposed method requires all possible configurations of the shared state to be efficiently enumerable, as the generated code marginalizes over them (Section 4.1). In reality, this is probably intractable in all but the simplest artificial problems.\n\nTo be clear, as the method is effective on the stated task, this is a relatively minor weakness, but if the paper intends to show that the method is applicable to real-world tasks, then it needs an evaluation in a more realistic benchmark than just OneCommon.\n\nA separate but related weakness of the paper is the choice to generate Python directly, as opposed to a dedicated DSL or a more common declarative PL such as SQL. Given the code generation is the core contribution of this paper, there should be more discussion of what exactly is the expressive power of the generated code, and how this contribution is different from previous work in semantic parsing and dialogue state tracking.\n\nAfter rebuttal: Thanks for addressing all comments. I agree that extending the proposed approach to probabilistic programs rather than deterministic would greatly increase the applicability of the method. I also understand that such an extension could be out of scope for this work.\nI would recommend including such discussion, as well as well discussion of prompts and choice of target language, in the final version.\nOverall, I am satisfied that the concerns can be addressed in the final revision, and I updated my score.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes a new method for the task of grounded dialogue, in which an agent needs to achieve an objective together with the partner based on some shared state that needs to be communicated.\nThe proposed approach leverages executable semantic parsing (using a subset of Python, generated by the LLM) to interpret the utterances received by the agent. The formal representation is executed deterministically to compute the most likely interpretation of the utterance, which is used to update a probability distribution over all possible shared states. The new probability distribution is then used to choose a configuration of the shared state to test that maximizes information gain, which is then asked to the partner by generating a question following a template. The game continue until one configuration has an estimated probability above a threshold.\nThe approach is evaluated on the OneCommon task, where agent and partner operate on a board containing shapes. Each agent and partner are assigned one subset of the shapes, and they need to identify at least one shape they have in common.", "excitement": 3, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TITINd7Gj7", "reviewer": "Reviewer_pMuZ", "summary": "", "questions": "\n1) Would a data release for SPC be possible? The outputs from the human evaluation of SPC may be valuable for future researchers on the OneCommon benchmark, especially for future comparison. This also includes the human-to-human evaluation. \n", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We are encouraged that you found the system interesting and the results positive. We will include all clarifications below in the next version:\n\n## Prompts\nWe apologize for not including examples of the prompts in the original submission. For reproducibility, the code and data for generating the prompts was included in the supplementary material. We provide anonymized links containing an example of each prompt and a pointer to the generating Jinja template in the supplementary material.\n\nFull prompt\n* Template: `oc-anon/oc/prompts/understand5.j2`\n* Link: https://pastebin.com/x8dxj4tz\n\nSPC prompts\n\nReformat: Rewrite partner utterances to correct typos and formatting.\n* Template: `oc-anon/oc/prompts/reformat.j2`\n* Example: https://pastebin.com/uTeP8nZE\n\nClassify: Classify the dialogue act and any reference to previous turns.\n* Template: `oc-anon/oc/prompts/classify2.j2`\n* Example: https://pastebin.com/FFY8APRX\n\nConfirm: Classify whether the partner said yes or no to a previous question.\n* Template: `oc-anon/oc/prompts/confirm.j2`\n* Example: https://pastebin.com/YpTiTkSD\n\nConstraint generation: Generate the constraints.\n* Template: `oc-anon/oc/prompts/understandshort2.j2`\n* Example: https://pastebin.com/ube83h3n\n\nExecution template: Take the output of previous prompts and turn them into a program.\n* Template: `oc-anon/oc/prompts/executeshort2.j2`\n* Example: https://pastebin.com/JJvGAtyU\n\n## Prompt constraints and parsing\nWe do not impose any constraints on the GPT-4 output. If the generated code fails to execute or there is a malformed output, we ignore the partner utterance in that turn. Recent advances in constrained prompting should greatly improve such errors. For prompt parsing, we rely on the MiniChain library. The code can be found in `oc-anon/oc/prompt.py` in the supplementary material.\n\n## Input to the partner model\nThe partner model takes as input a query about whether a set of dots \"can be seen\", represented as a binary vector $\\\\{0,1\\\\}^7$ showing which dots are being referred to. The partner model’s output is a distribution over yes or no. The full code for the partner model can be found in `oc-anon/oc/belief/belief.py` in the supplementary material.\n\n## Step-by-step description of SPC\nWe expand upon the description in L186-200 below, and will include these clarifications in any future version of the paper, given extra space:\n* Reading: We map partner utterances to a set of dots they are asking about. We obtain the set of dots by prompting with either the full prompt (Section 4.1) or more efficient decomposed prompts (Section 4.2). We execute the generated code to return a set of dot referents. The parsing is performed via few-shot prompting, with the prompts given above. The code for reading can be found in `oc-anon/oc/agent2/reader.py` in the supplementary material.\n* Belief update: If SPC successfully resolves the set of dot referents, we update our belief (Section 5.1, Equation 1). The code for the belief update logic can be found in `oc-anon/oc/agent2/reader.py` in the supplementary material. The partner model code is in `oc-anon/oc/belief/belief.py`.\n* Planning: Given the updated belief, we consider all possible next actions (sets of dots to ask about) and reason about what would happen if we took those actions. We pick the action that would result in the most information gained about the shared dots (Section 5.2, equation 2). For dialogue games, computing the information gain from a particular action requires marginalizing over partner responses to said action. The code for planning can be found in `oc-anon/oc/agent2/planner.py` in the supplementary material.\n* Writing: We then describe the chosen action, a set of dots. We utilize one of three templates: a start template, follow-up template, or select template. The start template describes the set of dots, the follow-up template describes the new dots in relation to a previously mentioned set of dots, and the select template describes a single dot to select. We additionally add a “Yes” or “No” to the start of the response if the partner utterance contained a question that was successfully parsed and resolved. The templates refer to dots by their absolute size, color, and relative positions to other dots. The code for writing can be found in `oc-anon/oc/agent2/writer.py` in the supplementary material.\n## Contributions over Chiu et al 2022\nChiu et al 2022 [4] is a non-archival theoretical work that doe not have experiments on language selfplay or human evaluation. Our contribution, as you correctly describe, is combining the partner model-based symbolic planner with a semantic parser in order to perform grounded dialogue. This combination allows our system to generate and interpret language, allowing (1) self-play automatic evaluation that uses language (not just symbols) and (2) interacting successfully with human partners.\n## Comparison to ReACT\nReACT allows tool use, but still performs reasoning in language space. Compared to SPC, ReACT trades off correctness for flexibility. Language-space reasoning is not limited to pre-defined logical forms but can suffer from hallucinations. Planning in SPC is restricted to the manually defined symbolic space, but cannot hallucinate. We hypothesize that ReACT could potentially achieve similar performance to SPC by carefully describing OneCommon-specific heuristics and instructions in language, in combination with access to our grounded perceptual library. However, specifying the planning objective in symbolic space with SPC is more natural and allows us to take advantage of the theoretical partner model from Chiu et al 2022 [4].\n## The value of code generation\nCode generation has two properties that make it appealing in OneCommon. First, it allows for the integration of grounded perceptual libraries with the symbolic planner (L79-L92). The grounded perceptual library is important because OneCommon requires careful spatial reasoning, and the symbolic planner provides an interface for designing task-specific constraints. Second, it provides a compositional knowledge representation that naturally describes declarative constraints (L64-78). Referring expressions in OneCommon are compositional, referring to groups of dots as well as individual features of particular dots. Code naturally composes individual feature constraints into group descriptions. Additionally, large language models are accurate at parsing these referring expressions to constraints in code.\n## Alternative methods for connecting language and symbolic planning\nRather than generating code as an intermediate meaning function to translate from language to symbols, it is possible to directly predict grounded referents. The reading component of the baseline \"Imitate\" system takes this approach. In preliminary experiments, we used the direct prediction reading model from \"Imitate\" as the reader in SPC and found that it cannot generalize to the simple template generations in SPC: 4/25 for direct prediction versus 22/25 with SPC’s reader. In particular, direct prediction with Imitate frequently mis-classifies referring expressions that are rare in the training data but easily understood by a human. This implies that the direct prediction reading model conflates the semantics of a referring expression with biases in training data. We turn to code generation with LLMs to decouple semantics from biases in training data.\n## Missing references\nThank you for the references, we will include these in the next version.\n## Citation for information gain (Section 5.2, equation 2)\nOur citation for the planning objective is Lindley, 1956 [1] (L346). We will include two more references for this objective [2,3].\n## Data release\nWe will release the human evaluation data.\n\n[1] D. V. Lindley. 1956. On a Measure of the Information Provided by an Experiment. The Annals of Mathematical Statistics, 27(4):986 – 1005.\n\n[2] MacKay, David J. C. 1992. “Information-based Objective Functions for Active Data Selection”. Neural Computation 4 (4): 590–604.\n\n[3] Hennig, P., & Schuler, C.J. (2011). Entropy Search for Information-Efficient Global Optimization. J. Mach. Learn. Res., 13, 1809-1837.\n\n[4] Justin T. Chiu, Wenting Zhao, Daniel Fried, Alexander Rush. “Modeling Perspective-Dependent Ambiguity in Collaborative Dialogue.” NAACL 2022 Wordplay Workshop. Non-archival.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This paper demonstrates an interesting task-oriented dialog (TOD) system that follows a neuro-symbolic architecture, in which a neural component (GPT-4) converts from natural language into a probabilistic symbolic representation, which is then operated over by a dialog planning model to control the behavior of the agent towards playing OneCommon successfully. This is a burgeoning field in using LLMs, in terms of grounding them in environments and ensuring that there is an interpretable and grounded representation of its belief state, leading to a SOTA result on OneCommon.", "reasons_to_reject": "1. The specification for how SPC converts from its partner’s natural language utterances to a symbolic representation of the world is not very clear to me. This is described in Section 4.2 and Section 6 (L404-414), but there doesn’t appear to be a description of how GPT-4 is prompted to convert to the symbolic representation. From what I understand, the output of GPT-4 will resemble L290-292, which is then parsed by the “partner model” mentioned in L412. But there are still a lot of questions left unanswered — for example:\n\n    a. What does GPT-4’s prompt look like?\n\n    b. Are there few-shot examples in the prompt?\n\n    c. Is there any regulation on how GPT-4’s output is kept in a parseable format, and what rules does the parser follow?\n\n    d. What does the input to the partner model look like, and how is its output converted into a natural language utterance returned to the partner player?\n\n    e. Can you provide a step-by-step description of how a partner’s utterance is read, parsed, and fed into the partner model, and how the partner model’s output is converted into generated text?\n\nMuch more detail needs to be provided in SPC’s methodology, and I would find it hard to reproduce the SPC system described in the paper.\n\n2. The contribution that this paper makes over prior work done by Chiu et al., 2022 (https://openreview.net/pdf?id=PkHSHZLig5H) is unclear. This paper cites Chiu et al., 2022 and reuses its presented dialog planner, and indeed describes the same “information gain” approach when doing dialog planning on OneCommon. In particular, this paper’s Section 5.2 is identical to the theoretical decomposition described in Chiu et al.’s Section 3 (and there should be a citation here!).\n\n    a. Am I correct in saying that the major contribution is embedding Chiu et al.’s dialog planner with a prompted GPT-4 that also feeds into the dialog planner with code generation? If so, this also needs to be made more explicit, and again more detail needs to be provided on the code generation aspect (as mentioned in (1)). If this is true, I'm not sure what the value of this work is with respect to prior works that also prompt large pretrained LLM's to interact with some symbolic task (e.g. https://arxiv.org/abs/2210.03629)\n\n    b. What is the value of code generation from GPT-4 when interfacing with the partner model? Are there other ways to connect the partner model with some LM to do conversation?\n", "questions_to_authors": "\n1) Would a data release for SPC be possible? The outputs from the human evaluation of SPC may be valuable for future researchers on the OneCommon benchmark, especially for future comparison. This also includes the human-to-human evaluation. \n", "paper_topic_and_main_contributions": "The authors demonstrate “Symbolic Planning and Code-Generation” (SPC), a system combining a prompted LLM (GPT-4) to perform as a task-oriented dialogue agent, and a symbolic planner that uses code generation. SPC is built for the OneCommon benchmark, a reference game between two players. Each player is given a separate view of a cluster of dots, and the objective of the game is for both players to communicate in natural language on the dots that they see, and to select a dot that is within both players’ viewpoints.\n\nSPC is broken down into a pipelined set of behaviors. At each turn, the agent reads its partner’s utterance, and converts it into a probabilistic symbolic representation of the world state through code generation by a prompted GPT-4. This symbolic representation is then operated over by a partner model from Chiu et al. 2022 which updates SPC’s belief state about which dots are visible by both it and its partner. Outputs from the dialog planning model are converted into text utterances through templating.\n\nSPC demonstrates SOTA results on OneCommon over prior baselines, during human evaluation when playing the OneCommon game. \n", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "There have been prior works on TOD systems grounded on some symbolic environment, either through code generation or implementing logic as a symbolic program. SMCalFlow (https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00333/96470/Task-Oriented-Dialogue-as-Dataflow-Synthesis) generates “dataflow graphs” from natural language conversations, parsing semantic intents into executable programs. Shin et al., 2021 (https://arxiv.org/abs/2104.08768) use controlled decoding of a pretrained LLM on SMCalFlow. Zhao et al, 2022 (https://arxiv.org/abs/2212.09939) connect an LM to a symbolic dialog planner with arbitrary logic in order to perform enterprise-like TOD.\n\nThere is also much research being done in the field of “agentic LLMs”, which connect a LLM to a symbolic environment and have it act as its own agent, when predicting actions (https://arxiv.org/abs/2210.03629, https://arxiv.org/abs/2303.11366, inter alia). "}}]

Author rebuttal:

Meta-review: The paper presents a novel method termed Symbolic Planning and Code-generation (SPC) that is applied to the OneCommon task. This task-oriented dialogue system hinges on a blend of neural (GPT-4 Large Language Model) and symbolic techniques to comprehend human interactions and formulate responses. SPC reads human utterances, generates code from them, and uses the code in a symbolic space for planning, subsequently reverting to natural language for responses. The evaluations indicate that SPC considerably surpasses the state-of-the-art method in human evaluations, especially when partnered with skilled humans. However, there are concerns regarding the clarity of the methodology, the system's broader applicability, and its novelty relative to prior research. Further elaboration on the process and addressing the cited limitations would bolster the paper's impact. After the rebuttal, it seems most concerns regarding soundness have been addressed, but reviewers are generally not very excited about this work. The AC feels that it would be a nice work to appear in the conference without all the additional materials and discussions.
Decision: Accept-Main