# The Whole Truth and Nothing But the Truth:
Faithful and Controllable Dialogue Response Generation
with Dataflow Transduction and Constrained Decoding

Hao Fang Anusha Balakrishnan∗ Harsh Jhamtani∗
John Bufe Jean Crawford Jayant Krishnamurthy
Adam Pauls Jason Eisner Jacob Andreas Dan Klein
Microsoft Semantic Machines<EMAIL_ADDRESS>Equal contribution.

###### Abstract

In a real-world dialogue system, generated responses must satisfy several
interlocking constraints: being informative, truthful, and easy to control.
The two predominant paradigms in language generation—neural language modeling
and rule-based generation—both struggle to satisfy these constraints. Even the
best neural models are prone to hallucination and omission of information,
while existing formalisms for rule-based generation make it difficult to write
grammars that are both flexible and fluent. We describe a hybrid architecture
for dialogue response generation that combines the strengths of both
approaches. This architecture has two components. First, a rule-based content
selection model defined using a new formal framework called _dataflow
transduction_ , which uses declarative rules to transduce a dialogue agent’s
computations (represented as dataflow graphs) into context-free grammars
representing the space of contextually acceptable responses. Second, a
constrained decoding procedure that uses these grammars to constrain the
output of a neural language model, which selects fluent utterances. The
resulting system outperforms both rule-based and learned approaches in human
evaluations of fluency, relevance, and truthfulness.

##  1 Introduction

In a task-oriented dialogue system, response generation is naturally posed as
a conditional language modeling problem: dialogue agents must produce a
contextually appropriate natural language string conditioned on the history of
user and agent utterances. But unlike many language generation problems, a
good dialogue response generation model is not just a model of typical _human_
utterances in context. Instead, effective dialogue agents must balance fluent
generation with a set of much stricter constraints.

Figure 1:  Interaction between a user and a dialogue agent. Once the user’s
request is translated into an agent action—expressible as a program or
dataflow graph (a)—the agent must generate a response. Agent responses might
simply state the result of the agent’s action (b–c), but often should describe
both the action and the result, _e.g._ , to help users identify when the agent
has misunderstood their request (d). In all cases, these responses must be
truthful and produced by rules that are straightforward for system designers
to revise.

Consider the dialogue shown in Fig. 1. In the first turn of this dialogue, the
user makes a request, the dialogue agent correctly translates it into a
computation, here represented as a dataflow graph (Fig. 1a), and then
accurately describes this computation’s return value (Fig. 1b). But in the
second step, the dialogue agent makes a mistake: perhaps because of a speech
recognition error, it creates a meeting with _Tara Smith_ rather than _Sarah
Smith_. Simply describing the result of its action (Fig. 1c) might cause a
user to incorrectly conclude that their request was completed successfully.
Seeing this error, a system designer might wish to ensure that the dialogue
agent instead echoes back to the user the details of the agent’s action (Fig.
1d). This example highlights several of the challenges central to building
real-world dialogue response generation systems.

First, response generation is not simply a problem of describing the result of
a computation in natural language. In some cases, response generators may also
usefully describe the provenance of that result—the computation itself and its
intermediate values. In many human-to-human conversational contexts, a
response as detailed and redundant as Fig. 1d would be over-informative,
violating Grice’s maxim of quantity (1975). But Gricean cooperative speakers
may sometimes deem it useful to convey information about their mental state.
For a speaker that is prone to mistakes, such as an AI agent, revealing its
own understanding and/or reasoning as in Fig. 1d can increase user trust when
its computation was appropriate, and can provide an opportunity for correction
when it was not.

Second, dialogue response generation systems must guarantee truthfulness: as
the primary source of information about the action that a dialogue agent took,
a response generator that describes even a small fraction of these
computations incorrectly can produce disastrous results. Importantly, truthful
utterances might be low-probability under a domain-general language model
(LM), particularly when they reflect errors in language understanding (as in
Fig. 1c–d).

Finally, response generation systems must support declarative specification of
agent behavior. When confusing or infelicitious responses are discovered, it
should be possible to easily and precisely modify them without changing the
dialogue agent’s behavior in other contexts.

How might we build a generation system with all these properties? In recent
years, the main focus of academic dialogue research has been on “end-to-end”
learned models for response generation, especially neural sequence-to-sequence
models Vinyals and Le (2015); Zhang et al. (2020b). But while such models
excel at producing fluent and coherent output, research continues to find that
they struggle in maintaining faithfulness Wiseman et al. (2017); Maynez et al.
(2020). Perhaps more fundamentally, because the behavior of such systems is
encoded implicitly in their training data, designing a user experience
requires system builders to write and edit a large number of training examples
whose final effect may be difficult to predict.

As a result, many dialogue systems in the real world remain rule-based: system
builders hand-write rules (_e.g._ , in the form of a synchronous grammar) for
transforming dialogue states into text, and these rules are applied directly
during deployment. But such rule-based systems are also notoriously difficult
to build and maintain Walker et al. (2002); Reiter (2022). They require
designers to anticipate every low-level question about surface realization
(does _your meeting about “product”_ sound more or less natural than _your
“product” meeting_?), and to encode these in the same grammar that is
responsible for enforcing high-level properties like truthfulness.

Given the many strengths of modern LMs, is there a way to leverage them while
preserving the numerous other properties that dialogue response generation
systems must satisfy? In this paper, we describe a hybrid approach to building
dialogue systems that combines the advantages of end-to-end and rule-based
approaches. This approach has two components:

  * •

A dataflow transduction procedure, based on a new formalism that uses
declarative rules to map a computation (represented as a dataflow graph) into
a context-free grammar (CFG) that defines the space of all responses allowed
for the given computation. This formal framework makes it possible to write
rules to precisely and truthfully describe both data and its provenance, while
performing supplementary computation where needed to produce informative
responses.

  * •

A constrained decoding procedure that intersects a CFG with a neural LM,
making it possible to decompose language generation into a content selection
model (implemented by the grammar) and a separate fluency model (implemented
by an LM).

Together, dataflow transduction and constrained decoding make it possible to
build a faithful generation system capable of describing a complex, open-
ended, space of tasks. Using a subset of SMCalFlow dialogues Semantic Machines
et al. (2020) and only 187 declarative rules, our hybrid system is
consistently rated as more truthful, relevant, and fluent than either a rule-
based or end-to-end neural system.111Code, data, and trained models will be
released.

##  2 Problem Formulation

We study the problem of response generation for task-oriented dialogue. A
dialogue, like the one in Fig. 1, consists of a sequence of turns, each
consisting of a user utterance $x_{i}$, one or more actions $a_{i}$, and an
agent response $y_{i}$. The job of a dialogue agent is to predict an
appropriate action and response from a dialogue history, i.e., mapping from
$(x_{1},a_{1},y_{1},x_{2},a_{2},y_{2},\ldots,x_{n})\mapsto(a_{n},y_{n})$.

A common approach to building dialogue agents decomposes this prediction
process into several steps. First, a language understanding module maps from a
user utterance (and possibly other components of the dialogue history) to a
meaning representation (_e.g._ , a structured user intent, API request or
other executable program). This meaning representation is then evaluated,
producing actions $a$; these are finally passed to a response generation
module that produces an agent utterance $y$.

The focus of this paper is the response generator. We assume that we have a
pre-specified language understanding module that maps from conversation
histories to computations, in the form of short programs, which are then
executed to produce actions $a$. As described by Semantic Machines et al.
(2020), these computations may equivalently be viewed as dataflow graphs in
which each node is labeled with a function, constructor, or primitive value,
as well as a return value once the node is executed. We additionally assume
access to a dataset of dialogues containing gold-standard user and agent
utterances. Given a language understanding module and a dataset of dialogues,
we aim to implement a response generator that, when applied to a dataflow
graph, satisfies the three properties outlined in § 1: description of data and
its provenance, guaranteed truthfulness, and declarative specification.

Our response generation system is built from two pieces: (1) a dataflow
transduction procedure for transducing dataflow graphs into CFGs, and (2) a
constrained decoding procedure for intersecting a CFG with a neural LM,
described in § 3 and § 4, respectively. Hybrid generation systems of this kind
have a long history in natural language generation Langkilde and Knight
(1998). Our aim in this paper is to show the benefits of a new generation
paradigm based on dataflow transduction, and offer new rule-writing formalisms
and decoding algorithms tailored to modern language models in this setting.
The combination of declarative rules for content selection and learned models
for fluency offers a powerful framework for building dialogue systems that are
ready for the real world.

##  3 Dataflow Transduction

Given a dataflow graph $G$ (_e.g._ , Fig. 1a) rooted at a node
$v_{\texttt{root}}$ (the return value of the program represented by the
dataflow graph), our task is to generate a string that describes
$v_{\texttt{root}}$ and its provenance. To achieve this, we propose a new
formal framework for generation based on dataflow transduction. At a high
level, the formalism uses declarative rules that describe how to transform a
dataflow graph into a graph-specific grammar (specifically a quasi-synchronous
context-free grammar, or QCFG) that defines the space of allowed responses.
These rules walk along the graph, introduce new computations (dataflow
subgraphs) as needed, and add rules to the grammar.

Formally, a dataflow transducer $\mathcal{S}$ is defined by a 4-tuple
$(\mathcal{T},\Sigma,\mathcal{R},t_{\texttt{start}})$ where $\mathcal{T}$ is a
set of nonterminal symbols,222In practice, nonterminal types often correspond
to syntactic categories such as NP (noun phrase) or to semantic categories
such as EVENT. This is up to the designer. $\Sigma$ is the set of terminal
symbols (word types), $\mathcal{R}$ is a set of dataflow transduction rules
(see § 3.1), and $t_{\texttt{start}}$ is the start nonterminal. When applied
to $G$ the dataflow transducer expands the graph, yielding a new graph
$\bar{G}$, and produces a QCFG.

A QCFG (Smith and Eisner, 2006) is a specialized CFG whose nonterminals
include alignments to the nodes $V(\bar{G})$ of $\bar{G}$. Where an ordinary
CFG might specify ways to generate an NP (noun phrase) or a DATE, a QCFG would
specify ways to generate an NP or DATE that describes the result and
provenance of $v$, for each appropriately typed node $v\in V(\bar{G})$. A QCFG
resulting from dataflow transduction is a 4-tuple $(\mathcal{T}\times
V(\bar{G}),\Sigma,\mathcal{P},t_{\texttt{start}})$ where $\mathcal{T}\times
V(\bar{G})$ is the QCFG’s set of nonterminal symbols and $\mathcal{P}$ is its
set of productions. A QCFG production has the form

$\alpha\rightarrow\beta_{1}\beta_{2}\cdots\beta_{N}$

where the left-hand-side $\alpha=(t,v)\in\mathcal{T}\times V(\bar{G})$ is a
QCFG nonterminal, and each $\beta_{i}$ can be either a nonterminal
$(t_{i},v_{i})$ or a terminal in $\Sigma$. The $v_{i}$ of a right-hand-side
nonterminal $\beta_{i}$ may have appeared in the original $G$, or may have
been added to $\bar{G}$ by the dataflow transducer. These production rules
then derive a set of strings as in an ordinary CFG.

###  3.1 Dataflow Transduction Rules

Figure 2: A dataflow transduction rule with head S, a body (expressed in
Python), and a response template (which queries the dictionary returned by the
body).

Each dataflow transduction rule can be applied to a node $v\in\bar{G}$ (if $v$
has appropriate properties) to create a single QCFG production
$(t,v)\to\cdots$ that could be used to describe $v$. Since several dataflow
tranductions might apply to $v$, we may get multiple QCFG productions that
could produce alternative descriptions of $v$.

Such a rule has three components: (1) a head, namely the nonterminal
$t\in\mathcal{T}$; (2) a body, which is a piece of code that determines
whether the rule can apply to $v$, and which may look up or add nodes that are
related to $v$; and (3) a response template, which specifies the right-hand
side of the QCFG production in terms of the related nodes that were identified
by the body. (The related nodes will then be transduced into QCFG productions
of their own.) An example is shown in Fig. 2.

Rule Head. This nonterminal characterizes the type of node that the
transduction rule is able to describe and the type of description that it will
produce.2 When a rule with head $t$ is successfully applied to the node $v$,
the resulting QCFG production has left-hand-side $(t,v)$.

Rule Body. A rule body declares the condition when the rule can be applied by
examining the dataflow graph $\bar{G}_{v}$ rooted at $v$. It can contain
executable logic that identifies additional computation nodes that will be
recursively described.333Note that the nodes added by the body may represent
further computations on existing nodes of $\bar{G}_{v}$ or may be completely
disjoint from the existing nodes. For example, the rule body in Fig. 2 checks
whether $\bar{G}_{v}$ has the form findEventsOnDate(date). If so, it binds the
variable date accordingly, and introduces new nodes into $\bar{G}$, bound to
the variables num and event, which compute the number of events and the first
event. All three of these variables will be referenced in the response
template.

Response Template. The response template is a sequence of terminals and
nonterminals that the QCFG rule should produce. This can be used to copy
information verbatim from the dataflow graph (_e.g._ , for simple values like
strings and numbers), as well as to create more complex descriptions. Every
QCFG nonterminal $\beta_{i}$ in the template specifies another node $v_{i}$
that needs to be described as well as a dataflow nonterminal $t_{i}$; that
node can be recursively described by any rule with head $t_{i}$. In our
template syntax, the QCFG nonterminal $(\texttt{EVENT},\texttt{v4})$ would be
constructed using the notation `{EVENT <event>}`, where the variable event is
bound to the node v4. The syntax is illustrated in Fig. 2, where the response
template constructs three QCFG nonterminals with types LEX, PP, and EVENT,
respectively.

We note here that (1) transduction rules are selected via their head
nonterminal but also condition on the computation graph through their body;
and (2) all QCFG nonterminals are grounded in concrete computations. Together,
this provides a means to ensure truthfulness when generating responses from
this system.

Figure 3: The hybrid response generation approach using dataflow transduction
and constrained decoding. Given a computation
nonEmpty(findEventsOnDate(tomorrow())) for the user utterance “Do I have any
meetings tomorrow”, we first derive QCFG productions by applying the dataflow
transducer to the dataflow graph $G$ using the procedure described in § 3.2.
This procedure also expands the dataflow graph into $\bar{G}$: for example,
the nodes v3 and v4 were added by the third transducer rule. Then we extract
candidate responses from a LM, constrained by the QCFG. The varying
descriptions of the date v2 and the event v4 are permitted because the QCFG
can choose different productions while expanding the
$(\texttt{PP},\texttt{v2})$ and $(\texttt{EVENT},\texttt{v4})$ nonterminals.
(Those productions and the transducer rules that created them are not shown in
the figure. The nodes added by those transducer rules and used by those
productions are also not shown, except for v5.)

###  3.2 Dataflow Transduction Procedure

Given a dataflow transducer $\mathcal{S}$ and a dataflow graph $G$ rooted at
node $v_{\texttt{root}}$, we can transduce the graph into a QCFG as follows.
The system starts by creating QCFG productions that can expand the start
nonterminal $(t_{\texttt{start}},v_{\texttt{root}})$. For each transduction
rule in $\mathcal{R}$ whose head is $t_{\texttt{start}}$, it executes the
body, which checks any additional conditions for whether the rule can be
applied to $v_{\texttt{root}}$, binds variables, and uses the response
template to create a QCFG production. For any new nonterminals that appear on
the right-hand-sides of these productions, the system then recursively creates
further QCFG productions, in the same way, that can expand those nonterminals.
This recursive process continues until productions have been created for every
nonterminal that appears in the QCFG. The resulting QCFG compactly represents
a combinatorial space of possible responses.

##  4 Constrained Decoding

In this section, we describe how to integrate the formal framework above with
a general LM to perform response generation, as illustrated in Fig. 3. Given a
derived QCFG of the kind described in §3.2, we perform constrained decoding as
in Shin et al. (2021); Roy et al. (2022), generating response candidates from
a pretrained LM.

The QCFG resulting from dataflow transduction implicitly represents a set of
possible derivation trees and the agent responses they yield. As long as
transduction rules faithfully describe the nodes they apply to, every
derivation in this set will correspond to a truthful agent utterance. But
these utterances may not always be grammatical or natural. For example, the
response template in Fig. 2 may be realized as “I found 2 event on Monday”
since the rule body does not check whether the value of num is 1. Similarly,
the response template

$\bigl{\\{}$EVENT $\langle$event$\rangle$$\bigr{\\}}$ starts on
$\bigl{\\{}$DATE $\langle$date$\rangle$$\bigr{\\}}$.

may be realized as “The event starting on Monday starts on Monday” if the
grammar permits identifying events by their dates. With carefully engineered
and highly specialized rules (_e.g._ , using extremely fine-grained
nonterminal types), it would be possible to ensure that the responses are
always fluent and even that there is always a single possible outcome from the
top-down search procedure. However, this would usually require much a more
complicated set of rules, which creates a burden for system development and
maintenance.

Our proposed approach uses a large-scale pretrained (and preferably fine-
tuned) language model to serve as a fluency model. One option is to use the LM
to re-rank all strings that can be produced by the QCFG, but that would be
very computationally expensive. Instead, we follow Shin et al. (2021) and Roy
et al. (2022), who decode sentences from a given LM under the constraint that
they must be valid under a given CFG. This constrained decoding method uses
Earley’s algorithm (1970) to incrementally parse the sentence as it is
generated and determine the set of words that could grammatically serve as the
next token. In contrast to these prior papers, which used a static CFG, we
derive a new CFG each time the dialogue agent needs to generate a response, by
applying the dataflow transducer to the current dataflow graph.

##  5 Experiments

To evaluate this approach, we conducted a set of experiments on the SMCalFlow
dataset Semantic Machines et al. (2020). The data and evaluation metrics are
described in § 5.1. In § 5.2, we present the main evaluation results, followed
by an ablation study in § 5.3.

System | Automatic Metrics | Human Evaluation
---|---|---
BLEU | ROUGE | BERTSc. | R@1 | R@5 | Grammatical | Relevant | Truthful
QCFG Random Sampling | $.35$ | $.58$ | $.50$ | $.02$ | $.06$ | $.623$ | $.909$ | $.923$
Unconstrained Decoding | $.77$ | $.86$ | $.86$ | $.48$ | $.66$ | $.990$ | $.940$ | $.798$
QCFG-Constrained Decoding | $.79$ | $.87$ | $.85$ | $.56$ | $.79$ | $.993$ | $.973$ | $.916$
Gold | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $1.0$ | $.990$ | $.980$ | $.923$
Table 1: Evaluation results on SMCalFlow. Automatic metrics are calculated
against the gold responses on the full validation set. Human evaluation is
conducted on 297 randomly sampled validation examples.

###  5.1 Data and Evaluation Metrics

SMCalFlow is a large-scale task-oriented dialogue dataset, in which each user
utterance is annotated with a correct dataflow program (i.e., computation) and
a “gold” response that would be desirable for the agent to produce. We use the
v2.0 release processed by Platanios et al. (2021). We focus on a subset of
SMCalFlow involving calendar event queries. This subset contains 8938 training
examples and 1041 validation examples. We found that 187 transduction rules,
written by some of us in a matter of hours, were sufficient to cover all gold
system responses in these examples.444Some of our rule bodies chose to expand
the dataflow graph by calling functions, so we also had to implement those
functions. In an end-to-end dialogue system, most of those functions would
already have been implemented to support agent actions, not just natural
language responses.

Automatic Metrics. For automatic evaluation, we use several reference-based
metrics , including BLEU-4 Papineni et al. (2002), ROUGE-L Lin (2004), and
BERTScore-F1 Zhang et al. (2020a), computed using the GEM-metrics
tool.555https://github.com/GEM-benchmark/GEM-metrics Following the
recommendation in Zhang et al. (2020a), we use the re-scaled version of
BERTScore which is easier to interpret. We additionally consider exact match
scores, i.e., R@K, which measure whether one of the top $K$ response
candidates exactly matches the reference. Both R@1 and R@5 scores are
reported. We lowercase all the strings and remove any extra spaces while
computing the exact match between two strings.

Human Evaluation. It is well-known that popular automatic evaluation metrics
may not always reflect the true quality of the generated responses Celikyilmaz
et al. (2021). Thus, we further carry out human evaluation on 297 examples
randomly sampled from the validation data. Specifically, for each generated
response, we collect human judgments on three questions: grammaticality (“has
the virtual assistant made any grammar errors?”), relevance (“has the virtual
assistant misunderstood the user’s request?”), and truthfulness (“has the
virtual assistant provided any incorrect information as judged using the
database and timestamp?”). Three judgments are collected for each question,
and we report the percentage of examples where “no” is the majority-voted
answer. Higher percentages are better. Crowdworkers are recruited from Amazon
Mechanical Turk with qualification requirements such as having a work approval
rate higher than $80\%$ and having performed a minimum of $100$ annotations.
They are paid at the rate of $0.15$ cents per judgment. The inter-annotator
agreements for the three questions are around $90\%$, $80\%$ and $75\%$,
respectively, as measured by the percentage of examples where all three
workers choose the same answer.

###  5.2 Main Results

Our main evaluation results on SMCalFlow are shown in Table 1. The first
baseline we considered is QCFG random sampling, which is similar to the top-
down search process described in § 3.2 except that at each step we randomly
choose an applicable transduction rule. The other baseline is unconstrained LM
decoding without using dataflow transduction. We also report results on the
gold agent responses serving as the upper bound.

For both unconstrained and constrained decoding, we prompt the LM with a
string representation of the computation graph (i.e., the lispress format
released in SMCalFlow v2.0), followed by its execution result rendered as a
JSON string. We use beam search with a beam size $K=5$. The LM is initialized
from CodeT5-base Wang et al. (2021) and fine-tuned on all training examples.

As expected, the QCFG random sampling baseline struggles on all the automatic
metrics, since the dataflow transduction rules are written with an emphasis on
truthfulness rather than fluency, which is reflected in the grammaticality
score from the human evaluation as well. However, the truthfulness score is as
high as $92.3\%$, indicating the generated responses are rarely incorrect. We
observe that the generated responses sometimes are generic and do not contain
relevant information for the user request, which partially contributes to the
high truthfulness score. This is also reflected in the relevance score, which
is the lowest among all compared approaches.

In contrast, unconstrained decoding without dataflow transduction achieves
impressive scores on automatic evaluation. Human evaluation also suggests that
the generated responses are grammatically correct and relevant to the user’s
request in most cases. However, unconstrained decoding scores low on the
truthfulness dimension, making false statements in about one-fifth of the
generated responses. This high error rate is usually unacceptable in real-
world applications. This high rate of factual errors from neural LMs is
consistent with findings in prior work Wiseman et al. (2017); Maynez et al.
(2020).

Compared with unconstrained decoding, our proposed QCFG-constrained decoding
achieves significantly better scores on exact match, relevance and
truthfulness, while maintaining similar scores on BLUE, ROUGE, BERTScore and
grammar. In particular, human evaluation results indicate that the quality of
generated responses is very close to that of the gold responses.

Since even the gold responses did not achieve 100% on human evaluation scores,
we manually inspect those problematic examples. There are 4 examples for which
the majority-voted answer to the grammar question is “yes but understandable”,
and others are all rated as not containing any grammar errors. For the
relevance question, 4 examples are due to arguably bad data and 2 examples
receive tied votes. For the truthfulness question, 9 examples are due to
arguably bad data, 8 examples are due to to crowd worker mistakes, and 6
examples receive tied votes.

###  5.3 Ablation Study

| BLEU | ROUGE | BERTSc. | R@1 | R@5
---|---|---|---|---|---
1\. LM without fine-tuning
✗ | $.45$ | $.03$ | $-.29$ | $.00$ | $.00$
✓ | $.38$ | $.22$ | $.07$ | $.02$ | $.02$
2\. LM fine-tuned on 3% training data
✗ | $.67$ | $.82$ | $.80$ | $.27$ | $.39$
✓ | $.74$ | $.83$ | $.82$ | $.40$ | $.61$
3\. LM fine-tuned on full training data
✗ | $.77$ | $.86$ | $.86$ | $.48$ | $.66$
✓ | $.79$ | $.87$ | $.85$ | $.56$ | $.79$
4\. LM input without execution results
✗ | $.58$ | $.70$ | $.72$ | $.27$ | $.41$
✓ | $.78$ | $.85$ | $.84$ | $.53$ | $.77$
5\. LM input with user utterance
✗ | $.77$ | $.88$ | $.87$ | $.46$ | $.66$
✓ | $.78$ | $.85$ | $.85$ | $.55$ | $.79$
Table 2: SMCalFlow ablation results, varying the amount of fine-tuning data
(groups 1–3) and the context used in the input sequence (groups 4–5). ✗ and ✓
on the first column use unconstrained and QCFG-constrained decoding,
respectively.

We carry out an ablation study on SMCalFlow to analyze how the amount of fine-
tuning data and the context used in the input sequence impact the quality of
the generated responses for both unconstrained and QCFG-constrained LM
decoding. Results are summarized in Table 2.

Impact of fine-tuning: Without fine-tuning the LM, neither unconstrained nor
constrained decoding works well. This is likely due to the mismatch between
the pre-training tasks and the response generation task. However, after fine-
tuning on only 3% randomly sampled training data, both approaches achieve
significantly better scores, with larger gains on QCFG-constrained decoding.
This suggests that QCFG-constrained decoding is much more data-efficient in
the low-data regime. Moreover, using 3% of the training data, QCFG-constrained
decoding is on par with the unconstrained decoding when it uses 100% of the
training data, indicating that several expert hours spent on creating dataflow
transduction rules can dramatically reduce the cost of collecting training
data. Finally, we observe that increasing the data from 3% to 100% can yield
further improvements, although the gains are diminishing and QCFG-constrained
decoding benefits less from this. Note that despite the fact that the gaps in
BLEU, ROUGE and BERTScore between unconstrained and QCFG-constrained decoding
are tiny in the full training data setting, as we observed in Table 1, the
unconstrained decoding approach still performs poorly on the truthfulness
evaluation. Thus, it is unlikely that we can solve the truthfulness issue for
the unconstrained decoding method by simply scaling up the training data. In
other words, using QCFG-constrained decoding is a much more effective way to
achieve faithful response generation.

Impact of context: Results in groups 3–5 in Table 2 all use the full training
data to fine-tune the LM. The difference is in the context used in the input
sequence to the LM. For group 3, the input sequence is the computation
concatenated with the execution result, which is the same setup used in § 5.2.
For group 4, we omit the execution result, whereas for group 5, we add the
user utterance (prefixed to the computation). Comparing group 3 and group 4,
we observe that omitting execution results significantly harms the performance
of unconstrained decoding; we believe that unconstrained decoding heavily
relies on copying tokens from execution results into the agent response. In
contrast, the dataflow transduction rules can execute the computation
internally, so the proposed QCFG-constrained decoding does not necessarily
need to see the execution results in the LM input sequence, allowing a shorter
LM prompt. Comparing group 3 and group 5, we see that the user utterance in
the prompt does not bring any additional benefits to both unconstrained or
QCFG-constrained decoding. This is expected because it is redundant with the
computation, which is also in the prompt.

##  6 Related Work

One line of response generation research focuses on generating fluent and
coherent responses directly from user utterances without any intermediate
structured representation. This paradigm is mostly used for chatbots, as in
early rule-based systems Weizenbaum (1966); Wallace (2009), neural
conversation models Vinyals and Le (2015); Shang et al. (2015); Sordoni et al.
(2015); Li et al. (2017); Serban et al. (2016), and recent large-scale
pretrained LMs like DialoGPT Zhang et al. (2020b) and GPT-3 Brown et al.
(2020).

Another line focuses on generating text from structured data, with
applications beyond dialogue response generation. For example, the WebNLG
challenge Gardent et al. (2017) generates natural language descriptions from
relation tuples, and Lebret et al. (2016) generate a biography from a
structured “infobox” record. Many recent dialogue response generation tasks
adopt dialogue-act-based meaning representations, including the MultiWOZ
dataset Budzianowski et al. (2018), the Schema-Guided dialogue dataset Rastogi
et al. (2020), and the E2E NLG challenge Dusek et al. (2020). In contrast, our
response generation task uses computations as the input, which do not directly
encode the dialogue acts of the responses. This is a more challenging task, as
the system needs to perform extra reasoning to obtain the derived information.
In this sense, our task is similar to the one in CoSQL Yu et al. (2019) and
Logic2Text Chen et al. (2020), but the computations used in our task are
semantically richer.

Constrained decoding techniques for neural LMs have been developed for text
generation with different types of constraints Balakrishnan et al. (2019);
Dathathri et al. (2020); Lu et al. (2021, 2022). Shin et al. (2021) develop a
constrained decoding approach for semantic parsing by restricting the LM
output at each step according to a given grammar. Differently, the grammar
production rules in our case are derived dynamically for each input.

##  7 Conclusion

In this paper, we have described a hybrid approach for building dialogue
response generation systems that combines the advantages of both end-to-end
and rule-based approaches. This approach introduces a new formalism for
transducing dataflow graphs into a QCFG, which can be then used in a
constrained decoding procedure that intersects the QCFG with a neural LM. This
formal framework makes it possible to write rules to precisely and truthfully
describe both data and its provenance.

Experiments show that this hybrid approach outperforms the neural LM
unconstrained decoding counterpart in both automatic evaluation and human
evaluation, especially in the truthfulness dimension. Moreover, using 3% of
the training data, the constrained decoding approach is on par with the
unconstrained decoding approach when it uses 100% of the training data,
indicating that several expert hours spent on authoring rules can dramatically
reduce the cost of collecting training data.

## Acknowledgements

We would like to thank Ben Van Durme, Baoling Peng, Subhro Roy, Richard Shin,
and Patrick Xia for valuable discussions and feedback on this paper.

## References

  * Balakrishnan et al. (2019) Anusha Balakrishnan, Jinfeng Rao, Kartikeya Upasani, Michael White, and Rajen Subba. 2019.  Constrained decoding for neural NLG from compositional representations in task-oriented dialogue.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers_ , pages 831–844. Association for Computational Linguistics.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 1877–1901. Curran Associates, Inc.
  * Budzianowski et al. (2018) Pawel Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gasic. 2018.  MultiWOZ – a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling.  In _Proc. Conference on Empirical Methods in Natural Language Processing (EMNLP)_.
  * Celikyilmaz et al. (2021) Asli Celikyilmaz, Elizabeth Clark, and Jianfeng Gao. 2021.  Evaluation of text generation: A survey.  _arXiv:2006.14799v2 [cs.CL]_.
  * Chen et al. (2020) Zhiyu Chen, Wenhu Chen, Hanwen Zha, Xiyou Zhou, Yunkai Zhang, Sairam Sundaresan, and William Yang Wang. 2020.  Logic2Text: High-fidelity natural language generation from logical forms.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2096–2111, Online. Association for Computational Linguistics.
  * Dathathri et al. (2020) Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2020.  Plug and play language models: A simple approach to controlled text generation.  In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.
  * Dusek et al. (2020) Ondrej Dusek, Jekaterina Novikova, and Verena Rieser. 2020.  Evaluating the state-of-the-art of end-to-end natural language generation: The E2E NLG challenge.  _Comput. Speech Lang._ , 59:123–156.
  * Earley (1970) Jay Earley. 1970.  An efficient context-free parsing algorithm.  _Communications of the ACM_ , 13(2):94–102.
  * Gardent et al. (2017) Claire Gardent, Anastasia Shimorina, Shashi Narayan, and Laura Perez-Beltrachini. 2017.  The WebNLG challenge: Generating text from RDF data.  In _Proceedings of the 10th International Conference on Natural Language Generation, INLG 2017, Santiago de Compostela, Spain, September 4-7, 2017_ , pages 124–133. Association for Computational Linguistics.
  * Grice (1975) Paul Grice. 1975.  Logic and conversation.  In _Syntax and semantics_ , volume 3, pages 41–58. Academic Press.
  * Langkilde and Knight (1998) Irene Langkilde and Kevin Knight. 1998.  Generation that exploits corpus-based statistical knowledge.  In _COLING 1998 Volume 1: The 17th International Conference on Computational Linguistics_.
  * Lebret et al. (2016) Rémi Lebret, David Grangier, and Michael Auli. 2016.  Neural text generation from structured data with application to the biography domain.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016_ , pages 1203–1213. The Association for Computational Linguistics.
  * Li et al. (2017) Jiwei Li, Will Monroe, Alan Ritter, Jianfeng Gao Michel Galley, and Dan Jurafsky. 2017.  Deep reinforcement learning for dialogue generation.  In _Proc. Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1192–1202.
  * Lin (2004) Chin-Yew Lin. 2004.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pages 74–81.
  * Lu et al. (2022) Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, and Yejin Choi. 2022.  NeuroLogic a*esque decoding: Constrained text generation with lookahead heuristics.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 780–799, Seattle, United States. Association for Computational Linguistics.
  * Lu et al. (2021) Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2021.  NeuroLogic decoding: (un)supervised neural text generation with predicate logic constraints.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 4288–4299, Online. Association for Computational Linguistics.
  * Maynez et al. (2020) Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. 2020.  On faithfulness and factuality in abstractive summarization.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1906–1919, Online. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  BLEU: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics ACL 2002_.
  * Platanios et al. (2021) Emmanouil Antonios Platanios, Adam Pauls, Subhro Roy, Yuchen Zhang, Alex Kyte, Alan Guo, Sam Thomson, Jayant Krishnamurthy, Jason Wolfe, Jacob Andreas, and Dan Klein. 2021.  Value-agnostic conversational semantic parsing.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics_ , Online. Association for Computational Linguistics.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020.  Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 8689–8696.
  * Reiter (2022) Ehud Reiter. 2022.  What are the problems with rule-based NLG?  https://ehudreiter.com/2022/01/26/problems-with-rule-based-nlg/.
  * Roy et al. (2022) Subhro Roy, Sam Thomson, Tongfei Chen, Richard Shin, Adam Pauls, Jason Eisner, and Benjamin Van Durme. 2022.  BenchCLAMP: A benchmark for evaluating language models on semantic parsing.
  * Semantic Machines et al. (2020) Semantic Machines, Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan 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, Christopher H. Lin, Ilya Lintsbakh, Andy McGovern, Aleksandr 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 Wolfe, Abby Wray, Yuchen Zhang, and Alexander Zotov. 2020.  Task-oriented dialogue as dataflow synthesis.  _Transactions of the Association for Computational Linguistics_ , 8:556–571.
  * Serban et al. (2016) Iulian V. Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, and Joelle Pineau. 2016.  Building end-to-end dialogue systems using generative hierarchical neural network models.  In _Proc. AAAI Conf. on Artificial Intelligence (AAAI)_.
  * Shang et al. (2015) Lifeng Shang, Zhengdong Lu, and Hang Li. 2015.  Neural responding machine for short-text conversation.  In _Proc. Annual Meeting of the Association for Computational Linguistics (ACL)_ , pages 1577–1586.
  * Shin et al. (2021) Richard Shin, Christopher H. Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. 2021.  Constrained language models yield few-shot semantic parsers.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021_ , pages 7699–7715. Association for Computational Linguistics.
  * Smith and Eisner (2006) David Smith and Jason Eisner. 2006.  Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies.  In _Proceedings on the Workshop on Statistical Machine Translation_ , pages 23–30, New York City. Association for Computational Linguistics.
  * Sordoni et al. (2015) Alessandro Sordoni, Michel Galley, Michael Auli, Chris Brockett, Yangfeng Ji, Margaret Mitchell, Jian-Yun Nie, Jianfeng Gao, and Bill Dolan. 2015.  A neural network approach to context-sensitive generation of conversational responses.  In _Proc. Conf. of the North American Chapter of the Association for Computational Linguistics (NAACL)_ , pages 196–205.
  * Vinyals and Le (2015) Oriol Vinyals and Quoc Le. 2015.  A neural conversation model.  In _Proc. ICML Deep Learning Workshop_.
  * Walker et al. (2002) Marilyn A. Walker, Owen C. Rambow, and Monica Rogati. 2002.  Training a sentence planner for spoken dialogue using boosting.  _Computer Speech & Language_, 16(3):409–433.  Spoken Language Generation.
  * Wallace (2009) Richard S. Wallace. 2009.  _The Anatomy of A.L.I.C.E._, chapter Parsing the Turing Test. Springer, Dordrecht.
  * Wang et al. (2021) Yue Wang, Weishi Wang, Shafiq Joty, and Steven C.H. Hoi. 2021.  CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 8696–8708, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Weizenbaum (1966) Joseph Weizenbaum. 1966.  ELIZA – a computer program for the study of natural language communication between man and machine.  _Commun. ACM_ , 9(1):36–45.
  * Wiseman et al. (2017) Sam Wiseman, Stuart Shieber, and Alexander Rush. 2017.  Challenges in data-to-document generation.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 2253–2263, Copenhagen, Denmark. Association for Computational Linguistics.
  * Yu et al. (2019) Tao Yu, Rui Zhang, Heyang Er, Suyi Li, Eric Xue, Bo Pang, Xi Victoria Lin, Yi Chern Tan, Tianze Shi, Zihan Li, Youxuan Jiang, Michihiro Yasunaga, Sungrok Shim, Tao Chen, Alexander Fabbri, Zifan Li, Luyao Chen, Yuwen Zhang, Shreya Dixit, Vincent Zhang, Caiming Xiong, Richard Socher, Walter Lasecki, and Dragomir Radev. 2019.  CoSQL: A conversational text-to-SQL challenge towards cross-domain natural language interfaces to databases.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1962–1979, Hong Kong, China. Association for Computational Linguistics.
  * Zhang et al. (2020a) Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. 2020a.  BERTScore: Evaluating text generation with BERT.  In _8th International Conference on Learning Representations, ICLR 2020_. OpenReview.net.
  * Zhang et al. (2020b) Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and Bill Dolan. 2020b.  DIALOGPT : Large-scale generative pre-training for conversational response generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 270–278, Online. Association for Computational Linguistics.