Source-linked AI summary
Task-Oriented Dialogue as Dataflow Synthesis
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, Alexander Zotov
TL;DR
Task-oriented dialogue systems must balance trainable structure with the flexibility to represent compositional, cross-domain user goals. This paper represents dialogue state as a dataflow graph and predicts graph-extending programs with explicit reference and revision operators, improving performance on complex dialogues and matching strong state tracking results on MultiWOZ.
Problem
Fixed symbolic states are easy to train but hard to extend, whereas unconstrained continuous states are flexible but do not reliably learn appropriate latent dialogue states.
Method
The framework represents dialogue state as a growing dataflow graph and has agents predict compositional programs with metacomputation operators for reference and revision.
Results
The approach improves challenging natural-dialogue modeling, including a 10.9% improvement on turns with a cross-turn reference, and enables an off-the-shelf seq2seq model to outperform a task-specific MultiWOZ state tracker.
Takeaways & Limitations
Dataflow representations make complex dialogue behaviors representable and learnable by keeping prior entities and computations available for explicit reuse.
Takeaways & Limitations
Coordinating many long-range dependencies remains challenging even for modern attentional architectures.
Abstract
from arXiv · showhide
We describe an approach to task-oriented dialogue in which dialogue state is represented as a dataflow graph. A dialogue agent maps each user utterance to a program that extends this graph. Programs include metacomputation operators for reference and revision that reuse dataflow fragments from previous turns. Our graph-based state enables the expression and manipulation of complex user intents, and explicit metacomputation makes these intents easier for learned models to predict. We introduce a new dataset, SMCalFlow, featuring complex dialogues about events, weather, places, and people. Experiments show that dataflow graphs and metacomputation substantially improve representability and predictability in these natural dialogues. Additional experiments on the MultiWOZ dataset show that our dataflow representation enables an otherwise off-the-shelf sequence-to-sequence model to match the best existing task-specific state tracking model. The SMCalFlow dataset and code for replicating experiments are available at https://www.microsoft.com/en-us/research/project/dataflow-based-dialogue-semantic-machines.
1 Introduction
The paper proposes dataflow graphs as structured yet flexible dialogue state, with programs that extend the graph and metacomputation operators that explicitly handle reference and revision. Experiments introduce SMCalFlow and show improved performance on challenging natural dialogues and traditional state tracking.
- Fixed symbolic states are easy to train but hard to extend, while unconstrained continuous states flexibly represent history but do not reliably learn appropriate latent states.
- Dataflow graphs provide an executable record of mentioned entities, actions, and computations that represents dialogue common ground.
- Agents predict compositional programs that extend the graph, using explicit metacomputation operators to retrieve and revise prior graph fragments.
- SMCalFlow contains around 40K English dialogues about calendars, locations, people, and weather, with turns annotated by programs.
- The framework supports challenging turns involving compositional actions, cross-domain interaction, complex anaphora, and exception handling.
- The approach improves performance on ordinary turns and by 10.9% on turns with a cross-turn reference.
2 Overview: Dialogue and Dataflow
Dialogue is modeled as interactive program synthesis: each user utterance becomes a program that extends and evaluates a growing dataflow graph. This representation preserves computation structure and shared context, supporting reference, revision, recovery, and response generation.
- At each turn, the agent translates the latest user utterance into a program that extends the dataflow graph and describes the resulting value.
- A basic example predicts findEvent applied to an EventSpec, producing a query whose evaluation returns the requested event information.
- Each function call becomes a graph node whose parents are its arguments, and nodes are evaluated in topological order.
- Reference: Reference retrieves salient nodes from dialogue history, allowing follow-up utterances such as “What day of the week is that?” to reuse prior results.
- Revision: Revision non-destructively replaces an upstream computation and returns a revised version of the surrounding computation, without specifying the reused subgraph in full.
- Response generation: The graph also records information introduced in generated responses, making mentioned values such as event duration available for future reference.
3 Reference resolution
Reference resolution treats prior dataflow nodes as retrievable dialogue entities, selecting salient nodes subject to type, property, and role constraints. Reified references can then feed new computations, while the same mechanism supports implicit and complex references.
- Dataflow nodes represent entities introduced in dialogue and remain eligible for later reference, with salience determining how expressions select them.
- The framework reifies refer as a graph node whose result supplies the prior DateTime value to a new computation, such as adding one day.
- The refer operation retrieves a node from dialogue history using an optional constraint on the returned node.
- Constraints can specify a node’s type, properties, or argument role, enabling expressions such as “the meeting,” “the Thursday meeting,” and “the month.”
- A follow-up such as “What do I have after that?” can resolve that to a salient Event and use it in a subsequent computation.
- A hard-coded heuristic ranks candidate nodes by recency and graph proximity, while the framework permits a learned salience model.
4 Revision
Revision lets later utterances reuse and modify earlier dataflow computations without destroying dialogue history, including when the revised value was previously omitted. The operator supports multi-turn, cross-turn updates by locating relevant graph fragments and constructing revised subgraphs.
- Dataflow graphs support references to previously executed computations, not only previously mentioned entities.
- A request to change planning to all-hands reuses the earlier meeting-time computation and returns the revised meeting time, even though the follow-up omits time.The example changes the event specification while retaining the time-oriented result.
- The revise operator replaces a constrained node within a prior computation while preserving the original computation and reusable shared nodes.It identifies the original root, the node to replace, and a new graph fragment.
- Revision can replace a missing argument, such as adding tomorrow’s date to an earlier lunch query whose date argument was absent.Missing arguments are represented implicitly and created on demand when an old-location constraint retrieves them.
- The more flexible reviseConstraint operation transforms an existing constraint while weakening it when necessary to preserve satisfiability.The dataset uses reviseConstraint extensively for directed constraint modifications.
- Real dialogues may build one request across as many as five turns with unrelated interruptions, making long-range revision chains a significant modeling challenge.Revisions can target other revise or refer nodes, producing longer chains of result edges.
5 Recovery
The recovery mechanism treats execution and discourse failures as graph exceptions that remain available for subsequent program synthesis. Users can then repair, refine, replace, or abandon problematic goals through the same reference and revision machinery.
- Incomplete requests and presupposition failures are represented as exceptions that let the agent explain the problem and guide the next exchange.This includes requests with missing information or no identifiable referent.
- The dialogue manager uses interactive repairs instead of a fixed scripted question order, allowing complex intents while reclaiming initiative when progress stalls.Users communicate repairs through the framework’s reference and revision mechanisms.
- Invalid date construction produces an exception node, which can trigger a prompt such as asking whether the user meant another date.Unevaluated descendants remain in the graph until the problem is repaired.
- Exception recovery becomes an ordinary revision step: a user can patch February 28 or March into the problematic date location.The same mechanism can also support a new request or a changed goal.
- Underspecified constructors can turn slot-filling into iterative exception handling, with each missing field eliciting a targeted repair.A missing name prompts the agent to ask what the meeting should be called, followed by a start-time question.
- The graph preserves the current goal across turns even when evaluation fails, so it remains accessible for reference and interactive refinement.Separating graph construction from evaluation lets policy react to exceptions without reasoning over full hand-written dialogue states.
6 Data
SMCalFlow is a large, richly annotated dataset of open-ended, cross-domain task-oriented dialogues whose turns are represented by executable programs. Its collection and annotation process supports complex compositions, exceptions, and grounded interactions, while a dataflow conversion also covers MultiWOZ.
- Agent responses are executable programs with API calls, function composition, and constraints over strings, numbers, dates, and times.They describe runtime behavior rather than key-value structures or database queries.
- The dataset is open-ended: crowdworkers were not constrained to scripts, and it includes out-of-scope requests requiring appropriate responses.Figure 2 illustrates a category-appropriate fencing response.
- SMCalFlow covers calendar, weather, places, and people, with pervasive cross-domain interaction.The dataset’s sample dialogue combines place finding, weather queries, references, and nested API calls.
- Dialogues are collected through a Wizard-of-Oz process across over 100 scenarios, with users adding turns and annotators labeling them with programs.The annotation interface uses autocomplete and supporting databases of people and events.
- The test set receives additional review, and 75% of turns pass double review without changes as an approximate measure of consensus on full programs.
- MultiWOZ 2.1 is additionally converted from turn-level dialogue-state annotations into dataflow programs for comparable evaluation.The conversion targets an executable representation of the original state-tracking task.
- SMCalFlow is described as the largest annotated task-oriented dialogue dataset to date, with a larger vocabulary and more complex state-manipulation primitives than MultiWOZ.Its programs include a long tail of function calls and deep composition.
7 Experiments
Experiments evaluate dataflow-based program prediction on SMCalFlow and MultiWOZ, showing gains from explicit metacomputation and competitive state tracking with standard sequence models.
- Experimental setup: SMCalFlow evaluates exact-match program accuracy after inlining metacomputation and compares explicit dataflow manipulation with contextual semantic parsing baselines.The experiments also include models trained on inlined metacomputation and a no-metacomputation baseline that can reuse prior computations through copying.
- SMCalFlow results: Around 73% development and 67% test turn-level exact match fell by 5.9% overall when metacomputation was inlined.Inlining reduced accuracy by 10.9% on reference turns and 9.1% on revision turns.
- SMCalFlow results: 10.9% accuracy loss on reference turns and 9.1% on revision turns shows the importance of explicit dataflow metacomputation.The reported differences are statistically significant, especially for turns involving reference or revision to earlier dialogue turns.
- MultiWOZ results: On MultiWOZ 2.1, program-based prediction is comparable to TRADE on Joint Goal and yields higher dialogue accuracy than TRADE.The paper notes that dialogue-level exact match and prefix length reveal clearer benefits than Joint Goal alone, while the dataflow model uses off-the-shelf sequence prediction tools.
- Error analysis: Manual analysis of 100 SMCalFlow errors identifies underprediction, entity linking, fencing, and ambiguity as major error categories.Underprediction omits program steps, while entity-linking errors misuse or hallucinate entities and fencing errors confuse in-scope and out-of-scope requests.
8 Related work
Related work contrasts fixed slot representations and unconstrained end-to-end systems with this paper’s richer explicit dataflow state for compositional dialogue.
- Contextual semantic parsing: Contextual semantic parsing addresses complex language understanding but generally does not reason about underspecified goals or agent initiative.Iterated question answering is presented as a prototypical example in which users ask sequences of database queries.
- Slot-filling approaches: Slot-filling systems use flat dialogue acts with fixed slots and are historically easier to predict and annotate.Their fixed structure limits the range of user intents they represent compared with richer compositional states.
- End-to-end dialogue agents: End-to-end neural agents map conversation histories directly to API calls and responses without explicit dialogue state, but prior systems failed to outperform rule- or template-driven baselines.The related work also notes promising results from generation-focused and hybrid neuro-symbolic approaches.
- Dataflow framework: The paper models full dialogues with explicit state while allowing arbitrary compositions of primitive operators for richer states and actions.This supports agents that ask questions, recover from errors, and take actions with side effects.
- Novelty: The authors identify this work as the first they know of using dataflow representations to model conversational context and dialogue.Dataflow representations are widely used for execution state in programming languages, but the paper applies them to dialogue context.
9 Conclusions
The paper presents task-oriented dialogue as compositional updates to a dataflow graph, enabling representation and learning of complex natural dialogues.
- Conclusion: Dialogue agents predict compositional updates to a graphical state representation rather than operating on a fixed dialogue-state schema.The conclusion frames the contribution as a representational framework based on dataflow graphs.
- Future work: Future work includes learned refer and revise implementations that evaluate hypotheses for syntactic, semantic, and pragmatic plausibility.The paper also suggests extending the framework with declarative user goals and preferences that persist across utterances.
- Implication: The authors expect the representations and dataset to encourage greater use of context and compositionality in learned task-oriented dialogue models.