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

Abstract: In a real-world dialogue system, generated text must be truthful and informative while remaining fluent and adhering to a prescribed style. Satisfying these constraints simultaneously isdifficult for the two predominant paradigms in language generation: neural language modeling and rule-based generation. We describe a hybrid architecture for dialogue response generation that combines the strengths of both paradigms. The first component of this architecture is 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 actions and their results (represented as dataflow graphs) into context-free grammars representing the space of contextually acceptable responses. The second component is a constrained decoding procedure that uses these grammars to constrain the output of a neural language model, which selects fluent utterances. Our experiments show that this system outperforms both rule-based and learned approaches in human evaluations of fluency, relevance, and truthfulness.

## 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 the user and agent interaction. 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. consider the dialogue shown in fig. 1 . in turn (1) of this dialogue, the user makes a request, which the dialogue agent correctly translates into agent: you have three events. ✘ (1) often responses should describe both the action and the result, e.g., to help users identify when the agent has misunderstood their request (c). these responses should be straightforward for system designers to inspect and modify. a computation-here represented as a dataflow graph (fig. 1a ) in the style of @xcite . the agent now needs to accurately describe this computation's return value @xcite . the wrong answer in fig. 1b shows it instead describing a different value that happens to appear elsewhere in the dataflow graph. turn (2) illustrates a more subtle risk: due to a speech recognition error, the agent has mistakenly created a meeting with tara smith rather than sarah smith. the wrong answer in fig. 1c shows it describing this result too briefly, which might lead the user to assume that their request was completed successfully. to avoid confusion, a system designer might wish to ensure that the agent instead echoes back to the user the details of the agent's action. this example highlights challenges in 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 conversations, a response as detailed as fig. 1c would be over-informative, violating grice's maxim of quantity @xcite . but for a speaker that is prone to mistakes, such as an ai agent, describing its own understanding can increase user trust when the understanding is accurate and provides an opportunity for correction when it is not. second, dialogue response generation systems must guarantee truthfulness: since the user often has no way to check the responses, even occasional errors could have disastrous consequences and would greatly undermine trust. yet truthful utterances might be low-probability under a domaingeneral language model (lm), particularly when they reflect errors in language understanding (as in fig. 1c ). finally, response generation systems must support declarative specification of agent behavior. when confusing or infelicitous responses are discovered, it should be possible to easily and precisely modify them without changing the dialogue agent's behavior in other contexts. in recent years, the main focus of academic dialogue research has been on "end-to-end" learned models for response generation, especially neural sequence models @xcite . but while such models excel at producing fluent and coherent output, research continues to find that they struggle in maintaining faithfulness @xcite @xcite @xcite . perhaps more fundamentally, because the behavior of such systems is encoded implicitly in their training data, designing a dialogue system 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 handwrite rules (e.g., in the form of a synchronous grammar) for transforming dialogue states into text, and these rules are applied directly during de-ployment. but such rule-based systems are also notoriously difficult to build and maintain @xcite . they require designers to anticipate every low-level question about surface realization, and to encode these in the same grammar that is responsible for enforcing highlevel properties like truthfulness. given the many strengths of modern lms, is there a way to leverage them while satisfying the numerous other demands on dialogue response generation systems? in this paper, we describe a hybrid approach that combines the advantages of end-to-end and rule-based approaches. this approach has two components: the mapping is defined by declarative rules. 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. this makes it possible to decompose language generation into a content selection model (implemented by the dataflow transducer) and a separate fluency model (implemented by the lm). hybrid generation systems of this kind have a long history in nlp, dating back to @xcite and @xcite . they mapped an abstract meaning representation (amr) to an acyclic finite-state automaton (fsa) and scored its paths with an n-gram lm.we replace amr with dataflow, replace their mapping rules with dataflow transduction rules, upgrade their fsa to a cfg, and upgrade their n-gram lm to a neural lm. in this way, we respectively support computation graphs, arbitrary tests and transductions, nested syntactically typed generation templates (already present in @xcite , and modern language models. together, dataflow transduction and constrained decoding allow a compact generation system to faithfully and fluently describe a complex and open-ended space of actions. we built such a hybrid system for calendar event queries in the smcalflow domain @xcite . when evaluated on a subset of annotated dialogues, it was consistently rated as more truthful, relevant, and fluent than either a rule-based or end-to-end neural system ( §5.2). results were similar on multiwoz dialogues @xcite ( §5.4). code, data, and trained models used in our experiments are released at https://github. com/microsoft/dataflow2text . ## 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 k, each consisting of a user utterance x k , one or more actions a k , and an agent response y k . the job of a dialogue agent is to predict an appropriate action and response from a dialogue history, i.e., , to map from ( how is this done? typically, a language understanding module maps the user utterance x k (in context) to a formal meaning representation. the agent reasons about this meaning representation to determine its own actions a k . finally, a response generation module maps these actions or their results (in context) to the agent utterance y k . the focus of this paper is the response generator. we assume that the formal meaning representation takes the form of an executable program, as is common in the semantic parsing literatureand that the actions are produced by evaluating this program, possibly with side effects. as described by @xcite , the program may be viewed as a dataflow graph 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 aim to implement a response generator that, when applied to an evaluated dataflow graph, satisfies the three properties outlined in §1: description of data and its provenance, guaranteed truthfulness, and declarative specification. in practice, for guidance when developing our generator, we refer to a development set of dialogues annotated with goldstandard dataflow graphs and agent responses. ## dataflow transduction given a dataflow graph g (e.g., fig. 1a ) rooted at a node v root (the return value of the program represented by the dataflow graph), our task is to generate a string that describes v 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 small 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 s is defined by a 4-tuple (t , σ, r, t start ) where t is a set of nonterminal types, foot_0 σ is the set of terminals (word types), r is a set of dataflow transduction rules (see §3.1), and t @xmath0. when applied to g, the dataflow transducer produces a qcfg. as a side effect, it may extend the graph with new computations. we use ḡ to denote the extended graph. a qcfg @xcite ) is a specialized cfg whose nonterminals include alignments to the nodes v ( ḡ) of ḡ. 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 @xmath1. a qcfg resulting from dataflow transduction is a 4-tuple (t ×v ( ḡ), σ, p, (t start , v root )) where t ×v ( ḡ) is the qcfg's set of nonterminals and p is its set of productions. a qcfg production has the form α → β 1 β 2 • • • β n where the left-hand-side α = (t, v) ∈ t × v ( ḡ) is a qcfg nonterminal, and each β i can be either a nonterminal (t i , v i ) or a terminal in σ. the v i of a right-hand-side nonterminal β i may have appeared in the original g, or may have been added to ḡ by the dataflow transducer. these production rules then derive a set of strings just as in any cfg. ## 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 will perform constrained decoding as in @xcite , generating re-sponse 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 event ⟨event⟩ starts on date ⟨date⟩ . may be realized as the product meeting 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 bur-den for system development and maintenance. our proposed approach instead uses a largescale pretrained lm (preferably fine-tuned) to select among truthful utterances produced by the qcfg. 4 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 even when that set is finite. instead, we follow @xcite and @xcite , who decode sentences from a given lm under the constraint that they must be valid under a given cfg. 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. the constrained decoding process is a special case of beam search. for each ℓ = 0, 1, . . ., it maintains up to k prefixes of the same length ℓ and tries to extend each in all legal ways to length ℓ + 1, pruning back to the k most probable extensions. for each prefix y 1 y 2 . . . y ℓ and each terminal symbol y ℓ+1 ∈ t , the extension y 1 y 2 . . . y ℓ+1 is only legal if it is a prefix of some legal complete response-i.e., some string that is grammatical under the qcfg. this check can be efficiently performed via an incremental contextfree parsing algorithm @xcite using the parsing state of the prefix y 1 y 2 . . . y ℓ . in other words, constrained decoding only considers a prefix if it could be extended into at least one legal complete response. note that the combinatorially many legal responses are never enumerated individually. rather, the set is compactly represented by the set of qcfg productions. ## experiments to evaluate the proposed approach, we conducted a set of detailed experiments ( §5.1- §5.3) on a subset of the smcalflow dataset @xcite , and a brief study ( §5.4) applying our approach to the multiwoz dataset @xcite . ## 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 @xcite , neural conversation models @xcite @xcite @xcite , and recent large-scale pretrained lms like dialogpt @xcite and gpt-3 @xcite . another line focuses on generating text from structured data, with applications beyond dialogue response generation. for example, the webnlg challenge @xcite generates natural language descriptions from relation tuples, and @xcite generate a biography from a structured "infobox" record. many recent dialogue response generation tasks adopt dialogue-act-based meaning representations, including the multiwoz dataset @xcite , the schema-guided dialogue dataset @xcite , and the e2e nlg challenge @xcite . 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 @xcite and logic2text @xcite . constrained decoding techniques for neural lms have been developed for text generation with different types of constraints @xcite @xcite . as §4 noted, we follow @xcite but choose our grammar constraints dynamically for each response. ## conclusion we have described a hybrid approach for building dialogue response generation systems. our approach introduces a new formalism for transducing a dataflow graph into a qcfg, which is then used in a constrained decoder that intersects the qcfg with a neural lm. this formal framework makes it possible to write rules to precisely and truthfully describe data and its provenance while deferring surface realization decisions to a flexible language model. this new approach outperforms unconstrained conditional language modeling in both automatic and human evaluations, especially on truthfulness. 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 hold almost equivalent value to a large volume of training data.