TOD-Flow: Modeling the Structure of Task-Oriented Dialogues
Authors: Sungryull Sohn
Yiwei Lyu
Anthony Zhe Liu
Lajanugen Logeswaran
Dong-Ki Kim
Dongsub Shim
Honglak Lee
Venue: EMNLP 2023 Main (2023)
Keywords: Task-oriented Dialogue
Dialog policy learning
interpretability
precondition inference
TL;DR: We introduce a TOD-flow graph, that enhances the transparency, controllability, and accuracy of task-oriented dialogue systems, outperforming previous dialog policy and end-to-end dialog models on SGD and MultiWOZ dataset.

Abstract: Task-Oriented Dialogue (TOD) systems have become crucial components in interactive artificial intelligence applications. While recent advances have capitalized on pre-trained language models (PLMs), they exhibit limitations regarding transparency and controllability. To address these challenges, we propose a novel approach focusing on inferring the TOD-flow graph from dialogue data annotated with dialog acts, uncovering the underlying task structure in the form of a graph. The inferred TOD-flow graph can be easily integrated with any dialogue model to improve its prediction performance, transparency, and controllability. Our TOD-flow graph learns what a model can, should, and should not predict, effectively reducing the search space and providing a rationale for the model's prediction. We show that the proposed TOD-flow graph better resemble human-annotated graphs compared to prior approaches. Furthermore, when combined with several dialogue policies and end-to-end dialogue models, we demonstrate that our approach significantly improves dialog act classification and end-to-end response generation performance in the MultiWOZ and SGD benchmarks.

TOD-Flow: Modeling the Structure of Task-Oriented Dialogues
Sungryull Sohn 1+
Yiwei Lyu²*
Anthony Zhe Liu?
Lajanugen Logeswaran'
Dong-Ki Kim
Dongsub Shim'
Honglak Lee
LG Al Research
2 University of Michigan, Ann Arbor
Abstract
Wang et al.. 2020) subjected to few-shot prompt- ing (Hudeček and Dušek, 2023; Labruna al., 2023) to adapt them to specific dialogue domains. While these approaches have yielded commend- able performance, they have limitations. Few-shot prompted models have been challenged by issues of transparency, controllability, and adaptability to specific domains, especially when working with only few examples. The lack of understand- ing of their decision-mann making processes and fine- grained control over their output often inade- quate, which can result in sub-optimal conversa- tional experiences. On the other hand, fine-tuned models are confronted with their own unique chal- lenges. While they offer improved performance by aligning the model with task-specific semanties, this approach typically requires large annotated datasets and resources which can be limiting fac- tor in practice. Furthermore, these models often lack transparency, making it challenging to under- stand the reasons behind their decisions or predic- tions.
Task-Oriented Dialogue (TOD) systems have become crucial components in interactive ar- tificial intelligence applications. While re- cent advances have capitalized pre-trained language models (PLMs), they exhibit limi- tations regarding transparency and controlla- bility. To address these challenges, pro- pose novel approach focusing on inferring the TOD-Flow graph from dialogue data an- notated with dialog acts, uncovering the un- derlying task structure in the form of graph. The inferred TOD-Flow graph can easily in- tegrated with any dialogue model to improve its prediction performance, transparency, and controllability. Our TOD-Flow graph learns what model can, should, and should not predict, effectively reducing the search space and providing a rationale for the model's pre- diction. We show that the proposed TOD- Flow graph better resembles human-annotee annotated graphs compared to prior approaches, Further- more, when combined with several dialogue policies and end-to-end dialogue models, demonstrate that our approach significantly im- proves dialog act classification and end-to-end response generation performance in the Multi- WOZ and SGD benchmarks. Code available at: https://gii thub. commssrsohn/TTOFFLI
Some prior works (Raghu et al., 2021; Laradji et al., 2023) introduced workflow- based dialog models to handle the challenges in existing TOD models. These methods aim to explicitly model the structure of dialog in graph format. Grounding the dialog in the graph offers benefits in terms of 1) elucidating the reasoning of system's decisions in terms the relationships (i.e., transparency): 2) allow human manipulation of the dialogue model via graph modification (i.e., controllability) with- out retraining the dialog model. However, real- world dialogues were often unstructured, making it non-trivial be modeled the necessity of manually designing the domain- specific workflow its elements limits its practical applicability.
1 Introduction
Task-Oriented Dialogue (TOD) systems have at- tracted significant attention due to their potential applications in personal assistants, customer sup- port, and other interactive systems that necessitate human-like conversation (Balaraman et al., 2021; Zhang et al., 2020). Many of the recent advances TOD have heavily leaned pre-trained lan- guage models (PLMs) (He et al., 2022b; Wu et al., 2020) that are first pre-trained on a large corpus of data in an unsupervised manner, and then ci- ther fune-tuned (He et al., 2022b; Chen et al., 2019;
workflow, and
To tackle these challenges, we propose to learn the subtask graph (Sohn et al., 2018) from task- oriented dialog data. Intuitively, the subtask graph
"Equal Contribution

---

FlD-Flow Graph
Next Dialog Act
Prediction Task
B
Confirm Information Book Hotel
Dialog
Filter & Modify With Graph
Confirm Information
Next Dialog
Book
Inform Price
D
Dialog Acts
Response Generation Task
Sampled Responses:
Ranked Response: The price ... Can you confirm?
Violation Check & Rank With Graph
CAN: required B
1. Booking complete
..;
SHOULD: After A, C aawwas follows
confirm?
Can you confirm
3. Can you confirm .
Booking is complete
SHOULD After follows
Figure I: (Left) Our TOD-Flow graph captures the causal dependency hetween dialog acts in terms of can, should, and should not relationships. (Right) Intuitively, given the TOD-Flow graph, we can predict the relevant and irrelevant dialog act responses based on the current dialog state. Based on the predicted relevance, can filter and rank the base model outputs to enhance the prediction performance in both dialog act classification and end-to-end response generation tasks.
can predict the affordance (i.e., availability) of the action from the status of environment and agent (i.e., the progress of completing task or the sub- tasks). The subtask graph framework has two major benefits: i) subtask graphs can be inferred from the demonstrations without any direct supervision (e.g.. video (Jang et al., 2023) or transcript (Logeswaran et al., 2023)), ii) subtask graphs can be combined with the base prediction model to improve its pre- diction since the subtask graph does not decide what to predict but instead suggests the affordable candidates of prediction.
implies a question. Third, we demonstrate that the inferred TOD-Flow graphs can enhance any dia- log policy or end-to-end dialog system, whether fine-tuned or prompted, without the necessity of retraining.
Background
Our main contribution, the TOD-Flow graph, is an extension of the subtask graph framework (Sohn et al., 2018, 2020), which describes the causal dependency structure of compositional task consisting of a of subtasks. In the context of task-oriented dialogue, dialog acts can be seen as subtasks. Each subtask has a precondition that must be satisfied before the subtask can be per- formed. Note that the precondition is not the only relationship between subtask, and in Section 3.2 we extend it by incorporating other types of relation- ships. Since precondition describes the causal rela- tionship between subtasks, it imposes constraint on the order in which subtasks can be performed (e.g., the system can make a payment only after the user confirms the payment). Formally, we define the precondition as a Boolean expression consisting of Boolean constants (e.g., True or False), Boolean variables and logical connectives (e.g., and (&), or ()). To illustrate, consider the precondition of sub- task C: Sc (A, B), where the subtasks and B must be completed before C completed. It can be equivalently viewed as a Boolean function where inputs are Boolean variables indicating whether subtasks A and B are completed, and the output
Contributions. The main contribution of this work is generalizing the subtask graph framework into task- lask-oriented dialog settings. To this end, we propose the TOD-Flow graph, which extends the subtask graph framework in three major aspects. First, we show that subtask graph can infer the rela- tionship between dialog state and dialog acts with- out requiring any manual definition of nodes and edges graphs. Second, in addition to the precon- dition (or can relationship), we present learning al- gorithms to model two novel relationships, should and should not, which provide more fine-grained control and improved prediction. For instance, can relationship may represent that the system can make payment only if the user confirms the pay- ment. The should relationship may learn that if user ask about the address of the hotel, the system should reply back. Conversely, a should not rela- tionship may dictate that the system usually does not predict a farewell if the user's last utterance

---

represents whether the precondition Sc is satisfied: fc(A- True, B False) True & False False. Also, the boolean expression fc = (A, B) can be viewed as a graph with vertices consisting of sub- tasks and logical operators V = {A, B, C, &) and edges E = {A + &, B - &z, & + C} that rep- resent preconditions. We will use these different views of the precondition (i.e., pression, graph or function) interchangeably. The subtask graph visualizes the preconditions f1.... of the subtasks (see Figure for examples). We note that the subtask graph has been adopted in various settings (Liu et al., 2022; Sohn et al., 2020, 2022) and subsumes other task graph formats (An- dreas et al., 2017; Boutilier et al., 1995; Sakaguchi et al., 2021), flowchart (Raghu et al., 2021), and workflow (Laradji et al., 2023).
a a[n]
Executed
Not executed
Cond
(a/n) 1)
(a [a/n]] 0) False positive
fihd
True positive
fShd
JShhnnt 1
False positive
True positive
SShdnt
fo
True positive
boolean ex-
Jn
False negative
fo
True positive
False positive
fbC
0
False negative
True negative
Table 1: Confusion matrix of the TOD-Flow graphs (Shd, Shdnt, Can) and the BC baseline with respect to the dialog act label afx]]. The empty cell (-) indicates that the label for each relationship is unavailable.
can, should, and should not be performed by the agent (user or system) at a given status. Similar to the precondition in subtask graph framework (see Section 2), each condition is defined as Boolean expression. Also, it can be equivalently viewed Boolean function fCan fShd, , fShdnt : > {0. 1) or graph (see Section 2), where c {0, 1N.. is the subtask completion (or dialog state) vector indicating whether 2thh subtask has been achieved (i.e., c(n] = 1) or not (i.e., c[n] = 0).
3 TOD-Flow Graph Learning
3.1 Problem Formulation
For dialogue turn f, let ut be the user input and rt be the corresponding system response. The user inputs and system responses are represented as a set of dialog acts that labels the raw language ut- terance at each turn according to its category of meaning: the Pe C A, where A is the set of dialog acts. Let de be the database query result that can be obtained through querying the database. Then, the dialog data DD is a set of dialog trajectories Given the dia- log data Dr, the goal is to generate the TOD-Flow graph G that models the dependency between sys- tem acts, user acts, and database results in graph format.
3.3 Learning TOD-Flow Graphs
Dataset. Given the dialogue data D { di, r:)), we aim to build the graph inference dataset Dg {(,,, at)]. from which we can infer the TOD-Flow graph fcan, fShd, and fShdnt, The action set a, the set of dialog acts that were performed at turn t: a, - uy r.. The comple- tion set Ct is the set of dialog acts and database query that has ever been performed before turn t: C C--1 -a U [di-1).
D {uo, To. da, U1, uj,...).....
Challenges. There are two main challenges in tackling this task. First, the information in the di- alogue is noisy due annotation errors such as missing or ambiguous dialog acts, slots, and values. Second, these dialog annotations only provide par- tial information about the underlying relationships between subtasks. Thus, we need to infer whether each relationship is satisfied or not from the dia- logue annotations. We describe how we overcome these challenges in Section 3.3.
Shd inference. When should condition is satis- fied (i.e., f {Shd (c)=1), the agent is required to per- form the nh dialog act (i.e., a[n] = 1). When the should condition is not satisfied (i.e., (c)=0), the should relationship has no effect on the policy, This relationship can be represented the confu- sion matrix shown in the first two rows in Table 1. Accordingly, we maximize the true positive, while minimizing the false positive by maximizing the objective Jshd in Equation (1).
3.2 TOD-Flow Graph
For each dialog act a. the TOD-Flow graph is de- fined in terms of three conditions: Can,, Shd,, and Shdnta. Intuitively, Cana, Shda and Shdnta condi- tion respectively defines whether the dialog act a
Jsnd = E(c,a(a)) [[a[[]] = Shd (c) = 1)] (1)

---

Dialog Model π
p 2
Multiple sampled predictions
Algorithm TOD-flow Graph-conditioned Dia- logue Model
af
(A, 8,
(A, C
Require:
Dialogue model π, TOD-flow graph fean, f frshdnt, Completion c
Completion Set
Can
Filter
[A, C, F.
B, Cy
f C,
Ensure: Sampled dialog acts a
Graph
a ~ π
P Sample dialog acts from и
Shd acts [G]
Add
2: a f a {a' [ SSd (c) = =
> Apply Shd
(A, C, FyC]
fA, G)
3: a + an aa Cannn-Shont (c) =
Shdnt acts
4:
4 Apply Can A SShdnt
Remove
(A)
return a
(h,
F,c
C
Graph-conditioned predictions
Final
Prediction
Ranking
by size
FC,F,G)
(c,G)
However, these approaches unavoidably introduces noise in learning, and require careful hyperparam- eter tuning to balance between objective and reg- ularization. Instead, inspired by the fact that Can and -Shdnt (i.e., negation of Shdnt) applies to the policy in the same manner (i.e., the dialog act can be performed if both _ = 1 and /--Shont 1), propose to infer Can and Shdnt simultancously as follows:
(C)
size=3 size=2
Figure 2: An illustration of our caaph-oondiiione dia- log policy. We sample multiple predictions from base dialog policy n, then use our graph to filter, add and re- move acts from each prediction following Algorithm I. Then we obtain final prediction by selecting the graph- conditioned prediction with the largest size.
Shdnt inference. Similar to Shd, when the shoud- not condition is satisfied, (i.e., fr (Shdnt(cc) (c) 1), the agent is required not to perform the nh dialog (i.e., [m]] 0), and agent has freedom to exe- cute the thth dialog act when the condition is not satisfied (i.e., fShdntt (c) = 0). Table 1 summarizes the relationship between Shdnt and a[n].. We learn 4Shdnt by maximizing the following objective: fn
JcanA-Shdnt
= E(aaf(n))
(c) 1|a[n] = =1] + a [ CCnn--Shdnt (c) O]a[n] 0]] (4)
where a determines the relative weight between Can and Shdnt in optimization. Intuitively, the agent can perform nh dialog act only if Can is satisfied and Shdnt is not satisfied.
Jshant = ((ea(n)) [[(a[n] = 00. Shdnt (c) = 1)]
Baseline. As an ablation model, we consider the behavioral cloning (BC) (Michie et al., 1990) ob- jective, which tries to mimic the demonstration behavior:
(2)
Can inference. By definition of Can (or precondi- tion), dialog act can only be performed (a.. 1) if its Can condition is satisfied (i.e., f(an(c) 1):
JBC ((ca(()) [I [ (c)
a[ni]]
(5)
true positive case in Table 1. On the contrary, it is a contradiction if dialog a, is performed while its Can not satisfied (i.e., pCan (c) = 0): false negative case in Table 1. Thus, the fcan can be learned by maximizing the following objective:
The confusion matrix shown at the bottom Table 1.
We can use any binary classification models to optimize the objectives (1), (4), and (5). We used the decision tree models in the experiment fol- lowing the previous works (Boutilier al., 1995; Huang al., 2019; Sohn al., 2020).
Jean E(c,oin)) [[[ (c) 1|a[n] 1]] (3)
However, different from Shd and Shdnt, inferring Can is nontrivial, because if maximize Jean- we get the trivial precondition: always true (i.e.. (Can(c) (c) for all c). Previous works handled this issue by either making additional assump- tions (Hayes and Scassellati, 2016; Huang et al., 2019) or applying regularization (Jang et al., 2023).
Graph-conditioned Dialog Modeling
We describe how the inferred TOD-flow graph G can enhance the prediction performance of any off- the-shelf dialogue policies and end-to-end dialog systems.

---

SYS Ask pickup city.
SYS Asked pickup city
Pickup city informed
SVS Ask piclup city....
SYS Askad pickup city
Plokup city informed
Intent Informmed CelCarsAviilabb
SVS Ask
SYS Asked pickup date
SYS Query GetCarsAaalaat
Intent informed GntCarssulllsbii
SVS Ask
SYS Asked pickup date
SPS Querry GelCursAvullage
pickup date
pickup date
Informed
SYS Ask
SYS Asked pickup time
Picioup time informed
SYS Ask
SYS Asked pickup time
Pickoup time informed
pickup timee/
pickup time
SYS Asked drapoff date
Dropoff titte informed
SYS Asked dropolf date
Dropoff date informed
dropolf date
Grapolf date
(o) Human-drawn Ground Truth
(b) BC
SYS Asked pickup city
Pickup city informed
SYS
SYS Asked pickup city
Pickup city informed
pickup city
piclup city
Intert, Infermed CalCarshvsillle
SVS Ask
SYS pickup date
Pickup date Informed
SYS Query GerCarstivllb
Intern Informed Gar
SVS Ask
SYS pickup date
Prckup
SYS Query GerCarstvaaaaa
plckup
plckeup
SYS Ask
SYS Asked pickup time
Picloup time Informed
SYS Ask
SYS Askad pickup time
Pickuup time Informed
pickup time
pickup time
SYS Asked drapatf date
Dropoft data Informed
SYS Askad drapoff data
Dropoft date Informed
draspotf date
drapott date
(e) MSG2
(d) FOD-Flow (Ours)
Dialog
Dislog (SYSTEM)
Positve edge
Redundant edges
Legend
block
Dialog State (USER)
Negative edge
Missing edges
Figure 3: Comparing baselines and our method against human dumann ground truth graph subpart of the RentalCars_1 domain of SGD. Dotted lines are negative edges (logical negations). Red edges are missing edges and blue edges are redundant edges compared to the ground truth. this scenario, the system allowed to ask for slot if user has informed the intent of finding available and has not yet informed this slot and the system have not yet asked for the slot; and the system can only query for a car when all 4 slots are informed. Our method perfectly matches the ground truth, while both baselines have incorrect edges (BC has redundant edges and 2 missing edges, while MSG² has 11 missing edges).
4.1 Graph-conditioned Dialog Policy
4.2 Graph-conditioned End-to-end Response Generation
The inferred TOD-flow graph (Shd and Can A -Shdnt) can propose the dialog acts that can, should, and should not be performed given the current dialog history (or completion set). Fig- ure 2 and Algorithm describes the entire process. Given a base dialogue policy DPP, we sample the system acts from the policy a DPP, and filter, add and remove acts from the sampled system acts according to the Can, Shd, and Shdnt, respectively.
End-to-end dialogue system directly reads and out- puts the utterances in natural language form. Given the base end-to-end model c2 we sample multi- ple system utterances from the base model (mostly via beam-search alternates, see Appendix A.2.1 for details). Then, we use a few-shot prompted APT-3.5-tures model to annotate each generated candidate utterance with the dialog act (see Ap- pendix A.2.3 for details). Finally, we use the in- ferred graph to choose the best utterance that has the least violation rate (i.e., portion of dialog acts that violates the inferred Can, Shd, and Shdnt con- ditions). Note that with this approach, all final responses still comes from the base end-to-end model, so the improvement is still by the capabilities of the model. Our graph simply presents a better candidate selection method.
We can further improve the prediction perfor- mance our baseline dialog model can be sampled multiple times with different results, as illustrated in Figure 2. We use the graph to condition each candidate result, then select the best one using a selection method such as most number of actions in set, candidate with least graph violations, etc. We empirically found that simply choosing the result with the most actions works best.

---

SGD (24 domains)
MultiWOZ (14 domains)
Models
FLAN-TS GPT-turbo
FLAN-T5
GPT-turbo
No Graph
49.9%
78.8%
21.6%
40.8%
+BC
57.2%
71.8%
23.5%
38.2%
+ MSG? (Jang et al., 2023)
52.4%
79.4%
23.8%
40.2%
TOD-Flow (ours)
83.1% %
89.2%
35.0% %
48.2%
Table 2: Average F-1 scores next system action prediction experiment on two datasets (SGD and MultiWOZ) and two large language models (FLAN-TS and GPT-turbo) few-shot predictors. We that while BC often damages performance, TOD-Flow consistently improves performance by significant amount.
5 Experiments
BC learns imitate the demonstration via behavioral cloning (see Section 3.3)
We perform experiments to show that (1) the TOD- flow graph can be accurately predicted without any supervision, (2) our graph can improve the accu- racy of dialog policy models, and (3) graph can improve the quality of response generation in end-to-end dialog models.
MSG² (Jang et al., 2023) learns the sub- task graph by optimizing the Jcan (see Equa- tion (3)) with complexity regularization.
TOD-Flow (ours) is our TOD-Flow graph learning algorithm.
5.1 Dataset
We used two standard TOD benchmarks. Schema- Guided Dialogue (SGD) (Rastogi al., 2020) has over 20k task-oriented simulated conversations based on human-designed schema. SGD covers a wide range of domains (i.e., different dialog acts and goals). We use 24 domains in SGD, and did not use the schema for experiment. Multi- WOZ (Budzianowski et al., 2020) has 10k human- human conversations on 14 domains. Since Mul- tWOZ is collected from human-human conversa- tions, the utterances much more linguistically diverse than SGD. Also, different from SGD where the annotations are generated from the schema, annotations in MultiWOZ are labeled by human. Therefore, the annotations in MultiWOZ are often noisy (Le., inconsistent, wrong, or missing), which present additional challenge compared to SGD. For both datasets, we obtain train/test splits of the dialogs within each domain (see Ap- pendix A.1.1 for details). The training is used for 1) inferring TOD-Flow graph, 2) building demonstration for few-shot prompted models, and 3) finetuning the finetuning- models. The test inference, we map the dialog act of user, database, and sys- tem to completion and dialog act vectors as described in Section 3.3.
For fair comparison, used the scikit-learn deci- sion model (Pedregosa al., 2011) 1) for all the graph inference algorithms.
5.3 TOD-Flow Graph Inference
We first qualitatively compare the inferred graphs with the human-drawn graphs on CentalCars_1 domain in SGD dataset. We found that in gen- eral TOD-Flow produces graphs that agree with the human-drawn graphs much more often com- pared to baselines (BC and MSG2). Figure 3 illus- trates the subpart of the inferred and human-drawn graph, where TOD-Flow inferred the graph per- feetly matches the human-drawn graph, while the baselines missed important information (such not requiring all 4 required slots to be informed before performing the query).
5,4 Task 1: Dialog Policy Learning
Base Models. We use two instruction-tune large language models (LLM) as baseline dialog policy: FLAN-T5-xxI (Chung et al., 2022) and GPTT-turbo
At each turn, we prompt the LLM with five demon- stration dialogues from train split of the same do- main followed by the dialogue history, and ask the model to predict next system dialog acts. See Ap- pendix A.1.2 for more details on prompting the LLM.
set only used for evaluation. For graph
5.2 Baselines
We compare three graph inference algorithms:

---

Can-Shdnt graph
Shd graph
Ranking method
SGD (24 domains)
MultiWOZ (14 domains)
FLAN-T5
GPT-turbo
FLAN-T5
GPT-turbo
No graph
X
Greedy
49,9%
78.8%
21.6%
40.8%
Graph
x
Compliance 70.4%
82.5%
26.1%
41.6%
ablations
/
x
Compliance 65.6%
83.5%
30.4%
44.5%
Greedy 80.9%
88.5%
26.2%
45.5%
Sampling
Majority 75.2%
88.1%
20.7%
45.0%
& ranking
Violation 76.2%
88.3%
23.7%
44.7%
ablations
Uniform 75.8%
88.0%
23.2%
45.2%
Ours
Compliance 83.1%
89.2%
35.0%
48.2%
Table 3: Ablation studies graphs and ranking methods for next system action prediction. The numbers shown are average F-1 scores. We see that both Can-Shdnt and Shd graphs have significant contributions towards the performance and our Compliance ranking method outperforms greedy sampling or other ranking methods.
Evaluation Protocol. We sample 10 candidate predictions from the base models, which is filtered and ranked based on the graph (see Section 4. to choose the best prediction.
compare the proposed ranking approach (i.e., Com- pliance) against various alternatives:
Greedy ranks by likelihood of base LLM.
Compliance ranks predictions by larger num- ber of actions complying with the graph (i.e. rank by size in Figure 2).
Metric. We measure F-1 score between the ground-trui truth and predicted system dialog acts at each turn and average over entire domains.
Majority chooses the majority prediction among the multi-sampled predictions.
Results. Table 2 summarizes the F-1 score of each model on SGD and MuluWOZ. Overall, we observe that TOD-Flow consistently improves the prediction accuracy with a significant margin com- pared other baselines BC and MSG² on all base models and all dataset. We also found that the improvements are bigger on FLAN-TS compared to GPT-turbo. This indicates that the GPT-turbo already models the Can, Shd, and Shdnt to some extent, so that augmenting it with the graph pro- vide less benefits. Since BC learns to mimic the exact behavior in demonstration, BC tends to dic- tate the base policy more aggressively and hurts the performance when combined with strong base model GPT-turbo. MSG² correctly models the pre- condition of dialog acts, but provides less benefit compared to TOD-Flow due to conservative graph learning (i.e., complexity regularization) and lacking the ability to model Shd and Shdnt rela- tions.
Violation ranks predictions by least number of actions filtered, added, and removed in graph conditioning.
Uniform randomly chooses one of the multi- sampled predictions.
The results are shown in Table 3, and TOD-Flow outperformed all ablations, showing the necessity of all graphs and ranking by largest set.
5.5 Task 2: End-to-end Response Generation
Base Models. We use the three SOTA end-to- end dialogue models finetuned on MultiWOZ: GALAXY (He al., 2022b), HDNO (Wang al., 2020), and HDSA (Chen et al., 2019) as base mod- els. Note that for GALAXY, since we were unable to reproduce the official prediction using the official repository, we report the result with both official prediction (GALAXY) and the greedy (i.e., beam search with beam width=1) prediction we obtained by rumning the official repository (GALAXY").
Ablations. To further justify design choices, we performed ablation studies on two key com- ponents of TOD-Flow: the graphs and the rank- ing method after graph-conditioning. For filtering graphs, we examined the effect of Can-Shdnt and Shd graphs. Regarding the ranking method, we
Evaluation protocol. From each model, we first sample five system response utterances: one from official prediction2 (Nekvinda and Dušck, 2021)
master/predictions

---

Graph
BLEU
Info
Suce
Score
Suce (percentage of dialogs where the task goals are achieved). The combined score is computed as Score =BLEU + (Info + S2cc)/2. See Ap- pendix A.2.2 for details on computing these met- rics. We report all four metrics of the compared methods.
HDSA
(no graph)
20.74
87.20
78.00
103.34
+BC
20.76
86.80
77.70
103.01
+MSG2
20.71
86.90
77.90
103.11
+TOD-Flow'
20.69
87.70
78.20
103.64
Result. We show the results in Table 4. We found that TOD-Flow can consistently improve Info and Suce metries for all the base end-to-end dialog mod- els. BLEU score fluctuates because it depends a lot on the exact wording of each response, which our graphs have no control over. The combined score consistently improves by 0.72, 0.49, 0.58, and 1 1.24 for HDSA, HDNO, GALAXY, and GALAXY*, respectively by conditioning with our TOD-Flow. Note that these score improvements are actually quite significant, as the difference between top and second top SOTA methods (GALAXY and HDNO) is only 0.74.
+TOD-Flow
20.51
88.10
79.00
104.06
HDNO
(no graph)
17.83
93.00
84.50
106.58
+BC
17.79
92.90
84.50
106.49
*MGG2
17.83
92.90
84.40
106.48
+TOD-Flow
18.08
93.10
85.10
107.18
+TOD-Flow
17.97
93.20
85.00
107.07
GALAXY
(no graph)
19.92
92.00
82.80
107.32
+BC
19.85
91.80
82.50
107.00
+MSG2
19.69
91.30
81.00
105.84
+TOD-Flow
19.86
92.40
83.30
107.71
Next, we compare different graph generation methods: BC. MSG?, and TOD-Flow. Overall, TOD-Flow consistently outperforms other base- lines, MSG and BC. In fact, the MSG" and BC often underperforms the greedy prediction with- out graph conditioning (i.e., (no graph). Since the sampled predictions are in general much worse than the greedy prediction, unless the graph-based ranking is highly accurate, it often samples the prediction that is worse than greedy prediction. On the contrary, TOD-Flow is often able to ac- curately pick out the non-greedy better alternative to outperform the greedy predictions. We show one such example in Table 5. We also found that excluding Shd graphs (i.e., TOD-Flow') signifi- cantly reduced the improvement in base models except HDNO. This shows that, while using only Can-Shdnt graphs also consistently improves per- formance of all base models, including Shd graphs can generally get even better results.
+TOD-Flow
19.85
92.40
83.70
107.90
GALAXY"
(no graph)
18.88
90.70
80.70
104.58
+BC
18.88
90.20
80.40
104.18
+MSG²
18.70
89.80
80.50
103.85
+TOD-Flow
19.04
91.10
81.40
105.29
+TOD-Flow
19.12
91.10
82.30
105.82
Table 4: Results from the response generation exper- iment with Galaxy (He et al., 2022b), HDNO (Wang et al., 2020) and HDSA (Chen et al., 2019) as base mod- els. The Score metric is computed by Score =BLEUU +(hyfo +Succ)/2. TOD-Flow stands for the ablation model that excludes Shd graph from our TOD-Flow. As see, our graphs consistently improves all met- rics except BLEU for all models, and we improve the official scores by a significant amount for each model.
and four from the model downloaded from the official implementation (see appendix A for details). The graph conditioning process follows Section 4.2. As an ablation, we also evaluated our method without conditioning on Shd graphs.
6 Related Work
Task-oriented Dialog Systems. There are two main classes of task-oriented dialog systems: pipeline systems and end-to-end systems. In pipeline approaches, the dialog system is seg- mented into various modules such natural lan- guage understanding (NLU), dialog state tracking (DST), dialog policy and natural language genera- tion (NI.) (Zhang al., 2020). The NLU module first converts user language input into standardized dialog acts, slots and values. The DST module
Metric. We follow the standard evaluation met- ric using the official code (Nekvinda and Dušck, 2021), which computes three metrics on the Mul- twOZ test set: BLEU (average BLEU (Papineni et al., 2002) scores between generated and ground truth response). Info (percentage of dialogs where the system presents an appropriate entity) and

---

(A chat between USER and SYSTEM)
History
USER: No, I'm not ready to book it yet. Thank you!
Utterance
Actions
SYSTEM:
The address is [value address], postcode posteodee the phone number [value ]
SYSTEM inform addr
GALAXY
SYSTEM inform post
SYSTEM inform phone
GALAXY
SYSTEM: Is there anything else cun help you with?
SYSTEM reqmore
+ TOD-Flow
SYSTEM: Just let us know when you are ready and we
SYSTEM reqmore
Ground truth
will be happy to assist you. Have a great day
SYSTEM offer booking
Table 5: Qualitative comparison of generated responses GALAXY and GALAXY+TOD-FOO on the fourth turn of dialogue SNG0772 in MultWWOZ. GALAXY's greedyy-ampled response informs information such phone number and postcode, which out of context. Instead, our TOD-Flow chooses an alternate response that does not violate Can (i.e., SYSTEM inform phone) and complies with Shd (i.e., SYSTEM reqmore), and it turns out to be better and closer to the ground truth.
keeps track of the current dialog state in terms of the dialog acts, slots and values. Based on the cur- rent dialog state, the dialog policy module predicts the next action. Previous works have viewed the dialog policy task as a Markov Decision Process (MDP) (K (Kwan et al., 2023). Common upproaches include reinforcement learning methods such as Q-learning. policy gradient (Lipton al., 2017; Zhou al., 2017; Gordon-Hall al., 2020) with experience-replay (Malviya et al., 2022), model- based planning (Peng et al., 2018). Lastly, given the current dialog states and the predicted dialog acts, the NLG module generates a response in natural language. We integrate the TOD-Flow graph into the dialogue policy module to improve its action prediction performance by learning what model can, should and should not predict.
2021). TGDM (Choi et al., 2016) attempted cre- ate dialog policy through manually constucted graphs, while a followup work (K won et al., 2018) proposed a rule-based system for automatically in- ferring these graphs given a working dialog policy. Raghu et al. (2021) tackles the task-oriented dia- logue problem where the system must ground dia- log utterances the manually-defined floweharts describing the procedure and adapt to unseen ones during testing. Laradji et al. (2023) aims to dis- cover the workflow, a sequence of dialog acts with their respective slot values, from unseen conversa- tion. Our TOD-Flow graph is constructed from labeled dialogue data without any human supervi- sion. And our graph models the relationship be- tween dialog acts and slots; e.g., what dialog act updates in slot values can happen or not.
On the other hand, end- mnd-to-end systems integrate all functionalities into one module. Many end-to- end models employ a singular language model to execute all four steps (He et al., 2022a). Alterna- tively, other methods bypass certain steps, gener- ating the final response directly (He al., 2022b; Wang et al., 2022). Pipeline systems more in- terpretable and modular, allowing independent up- dates for enhanced control. Ours work uses the TOD-Flow graph to enhance end-to-end model re- sponses by selecting the best one based on align- ment with learned Can, Shd and Shdnt conditions.
Conclusion
This work introduced a novel framework for im- proving the efficiency and predictive accuracy of task-oriented dialogues models. By leveraging the concept of subtask graph and generalizing it to TOD-flow graph, accurately inferred the la- tent task structure within dialogue. As show- cased through extensive experimentation with two public TOD datasets, the proposed technique has been proven to effectively generate accurate and numma-interpretabbe graphs. Importantly, we have integrated these inferred graphs with range of dialogue models, without necessitating retraining, resulting in substantial enhancement in perfor- mance in both dialog act classification and end-to- end response generation.
Graph-based Dialog Systems. There has also been previous works attempting integrate graphs into task-oriented dialog systems. Most of them focused on using graphs to represent or select infor- mation from a knowledge base (Yang et al., 2020,

---

Limitations
based on dialogue maps for computer assisted second language learning.
Although our method can be directly used when there are multiple domains involved in a single dia- log (by treating combination of domains as a single separate domain and creating graphs using dialogs that has the same combination of domains, similar what did for Multi this approach is limited in that (I) we need to infer a graph for ev- ery combination of domains that is present (such as the multi-domain dialogs in SGD, where there are 24 different single-domains alone), and (2) we cannot easily generalize to unseen domain combi- nations (even if we have graphs for each individual domain). In the future, we would like to explore ways to directly combine graphs for individual do- mains into multi-domain graphs and thus address the two limitations above.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghami, Siddhartha Brahma, Al- bert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdh- ery. Alex Castro-Ros. Roso Marie Pellat, Kevin Robinson, Dasha Valter, Sharan Narang, Gaurav Mishra, Adams Yu. Vincent Zhao, Yanping Huang. Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Ja- cob Devlin, Adam Roberts, Denny Zhou, Quoe V. Le, and Jason Wei. 2022. Scaling instruction-finttuned language models.
Gabriel Gordon-Hall, Philip John Gorinski, and Shay B. Cohen. 2020. Learning Dialog Policies from Weak Demonstrations. Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guisties, pages 1394-1405, Online. Association for Computational Linguistics.
We also relied on action annotations from the datasets to infer graphs, which limits the applica- bility of our approach. It would be interesting to extend our approach to unannotated raw dialogues.
Bradley Hayes and Brian Scassellati. 2016. Au- tonomously Constructing Hierarchical Task Net- works for Planning and In ICRA.
Collaboration.
Acknowledgments
Wanwei He, Yinpei Dai, Min Yang. Jian Sun, Fei Huang. Luo Si, and Yongbin Li. 2022a. Unified dialog model pre-training for task-oriented dialog understanding and generation. In Proceedings of the 45th Inter- national ACM SIGIR Conference Research and Development in Information Retrieval, SIGIR '22, page 187-200 New York, NY, USA. Association for Computing Machinery.
This work was supported part by grants from LG AT Research.
References
Jacob Andreas, Dan Klein, and Sergey Levine. 2017. Modular Multitask Reinforcement Learning with Pol- icy Sketches. In ICML.
Wanwei He, Yinpei Dai, Yinhe Zheng, Yuchuan Wu, Zheng Cao, Dermot Liu, Peng Jiang, Min Yang, Fei Huang, Luo Si, et al. 2022b. Galaxy: A generative pre-trained model for task-oriented dialog with semi- supervised learning and explicit policy injection. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 10749-10757.
Vevake Balaraman, Seyedmostafa Sheikhalishahi, and Bernardo Magnini. 2021. Recent neural methods on dialogue state tracking for task-oriented dialogue sys- tems: A survey. In Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue, pages 239-251, Singapore and Online. Association for Computational Linguistics.
De-An Huang. Suraj Nair, Danfei Xu, Yuke Zhu, Ani- mesh Garg, Li Fei-Fei, Silvio Savarese, and Juan Car- los Niebles. 2019. Neural task graphs: Generalizing to unseen tasks from a single video demonstration. In Proceedings of the IEEF/CVF conference com- puter vision and pattern recognition, pages 8565- 8574.
Craig Boutilier, Richard Dearden, Moisés Goldszmidt, al. 1995. Exploiting Structure Policy Construc- tion. In IJCAI.
Pawel Budzianowski, Tsung- -sien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ra- madan, and Milica Gašić, 2020. Multiwoz - large- scale multi-domain wizard-of-oz dataset for task- oriented dialogue modelling.
Vojtéch Hudeček and Ondiej Dušek. 2023. Are 1lms all you need for task-oriented dialogue? arXiv preprint arXiv:2304.06555
Yunseok Jang, Sungryull Sohn, Lajanugen Logeswaran, Tiange Luo, Moontae Lee, and Honglak Lee. 2023. Multimodal subtask graph generation from instruc- tional vidcos. arXiv preprint arXiv:2302.08662.
Wenhu Chen, Jianshu Chen, Pengda Qin, Xifeng Yan, and William Yang Wang. 2019. Semantically con- ditioned dialog response generation via hierarchical disentangled self-attention.
Wai-Chung Kwan, Hong-Ru Ru Wang, Hui-Min Wang, and Kam-Fai Wong 2023. A survey on recent advances and challenges in reinforcement learning methods
Sung-Kwon Kwon Choi, Oh- Woog Kwon, Young-Kil Kim, and Yun-Kyung Lee. 2016. Using a dialogue system

---

for task fask-oriented dialogue policy learning. Machine Intelligence Research, 20(3):318-333
Baolin Peng, Xiujun Li, Jianfeng Gao, Jingjing Liu, Kam-Fai Wong, and Shang- Yu Su. 2018, Deep dyna- q: Integrating planning for task-completion dialogue policy learning.
Oh- Woog Kwon, Young-Ki Mil Kim, and Yun- nun-Kyung Lee. 2018. Task graph based task-oriented dialogue sys- tem using dialogue map for second language learn- ing. Future- nnture-prroff CALL: language learning as ex- ploration and encounters short papers from EURO- CALI. 2018.
Dinesh Raghu, Shantanu Agarwal, Sachindra Joshi, et al. 2021. End-to-end learning of flowehart grounded task-oriented dialogs. In Proceedings of the 2021 Conference Empirical Methods in Natural Lan- guage Processing, pages 4348-4366.
Tiziano Labruna, Sofia Brenna, Andrea Zaninello, and Bernardo Magnini. 2023. Unraveling chatgpt: A crit- ical analysis of ai-generated goal-oriented dialogues and annotations.
Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghay 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, vol- ume 34, pages 8689-8696.
Issam H. Laradji, Stefania Raimondo, David Vazquez. Pau Rodriguez, Christopher Pal, et 2023. Work- flow discovery from dialogues in the low data regime. Transactions on Machine Learning Research.
Keisuke Sakaguchi, Chandra Bhagavatula, Ronan Le Bras, Niket Tandon, Peter Clark, and Yejin Choi. 2021. proScript: Partially Ordered Scripts Genera- tion. In Findings of EMNLP.
Zachary C. Lipton, Xiujun Li, Jianfeng Gao, Lihong Li, Faisal Ahmed, and Li Deng. 2017. nbg-networks: Efficient exploration in deep reinforcement learning for task-oriented dialogue systems.
Sungryull Sohn, Junhyuk Oh, and Honglak Lee. 2018. Hierarchical Reinforcement Learning Zero-shot Generalization with Subtask Dependencies. In NeurIPS.
Anthony Z. Liu, Sungryull Sohn, Mahdi Qazwini, and Honglak Lee. 2022. Learning Parameterized Task Structure for Generalization to Unseen Entities. In AAAL
Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. 2020. Meta Reinforcement Learning with Autonomous Inference of Subtask Dependen- cies. In ICLR.
Lajanugen Logeswaran, Sungryull Sohn, Yunseok Jang. Moontae Lee, and Honglak Lee. 2023. Unsupervised task graph generation from instructional video tran- scripts. arXiv preprint arXiv:2302.09175
Sungryull Sohn, Hyunjae Woo, Jongwook Choi, Lyub- ing Qiang. Izzeddin Gur, Aleksandra Faust, and Honglak Lee. 2022. Fast Inference and Transfer of Compositional Task Structures for Few-shot Task Generalization. In UA!.
Shrikant Malviya, Piyush Kumar, Suyel Namasudra, and Uma Shanker Tiwary. 2022. Experience replay- based deep reinforcement learning for dialogue man- agement optimisation. ACM Trans. Asian Low- Resour: Lang, Inf. Process. Just Accepted.
Jianhong Wang. Yuan Zhang, Tae-Kyun Kim, and Yun- jie Gu. 2020. Modelling hierarchical structure be- tween dialogue policy and natural language genera- tor with option framework for fask-oriented dialogue system. arXiv preprint arXiv:2006.068//
Donald Michie, Michael Bain, and Hayes-Micher 1990. Cognitive models from subcognitive skills. IEE control engineering series, 44:71-99.
Weizhi Wang. Zhirui Zhang. Junliang Guo, Yinpei Dai, Boxing Chen, and Weihua Luo. 2022. Task-oriented dialogue system as natural language generation. Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Infor- mation Retrieval, SIGIR '22, page 2698-2703, New York, NY, USA. Association for Computing Machin- ery.
Tomáš Nekvinda and Ondiej Dušek. 2021. Shades of bleu, flavours of success: The case of multiwoz.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei- Jing Zhu. 2002. Bleu: method for automatic evalu- ation of machine translation. In Proceedings of the 40th Annual Meeting of the Association for Compu- tational Linguistics, pages 311-318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
Chien-Sheng Wu, Steven Hoi, Richard Socher, and Caiming Xiong. 2020. Tod-bert: Pre-trained natural language understanding for task-oriented dialogue. arXiv preprint arXiv:2004.06877
Jen Cin-Chih Yang, Jia- Yan Wu, Sung- Chang, and Ya- Chieh Huang. 2021. Gks: Graph-based knowledge selector for task- dialog system.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duch- esnay. 2011. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2839
Shiquan Yang, Rui Zhang, and Sarah Erfani. 2020. GraphDialog: Integrating graph knowledge into end- to-end task-oriented dialogue systems. In Proceed- ings of the 2020 Conference on Empirical Methods

---

Natural Language Processing (EMNLP), pages 1978-1888, Online. Association for Computational Linguistics.
our set of all possible actions, but we did some re-naming and re-organization to remove some re- dundant combinations of acts and slots (for ex- ample, "SYSTEM Booking-Infee Informm <slot>" was changed into "SYSTEM OfferBook + SYSTEM inform <slot>"). Since there are no explicit anno- tation about database querying, we simply assume that the system looks up information before each "book/nobook" operation and add corresponding status update to the utterance before these actions. We do not explicitly add "query" actions or addi- tional turns to the trajectories.
Zheng Zhang, Ryuichi Takanobu, Qi Zhu, MinLie Huang, and Xiao Yan Zhu. 2020. Recent advances and challenges task-oriented dialog systems. Sci- ence China Technological Sciences, 63(10))2011 1- 2027.
Li Zhou, Kevin Small, Oleg Rokhlenko, and Charles Elkan. 2017. End-to-end offline goal-oriented dialog policy learning via policy gradient.
A Experiment Details
Then, within each domain, we will use the tra- jectories of the train split dialogs to obtain graphs and also act as demonstrations for LLMs, and use the graphs to improve next action predictions on the test dialogs.
A.1 Next Action Prediction
A.1.1 Dataset Preprocessing details
In the next action prediction experiment, we are using 2 datasets: MultiWOZ (Budzianowski et al., 2020) and SGD (Rastogi et al., 2020). We first split each dataset into domains and train/test splits. For MultiWOZ, the dataset has an official split- ting of train/val/test splits, so we follow the same splits; while MultWWOZ contains dialogs from 7 domains, 2 of them (police, hospital) have no test dialogs, thus we split MultWWOZ dialogs into 14 domains, including single-domains (i.e. dialogs that only involves one of the 5 domains) and 9 multi-domains (i.e. dialogs that involves multiple domains, such as Hotel+Train) For SGD, since the official train/val/test splits often involves test schemas that does not exist in the train set, we de- cided to create our own train/test splits from the official training set. There are 24 different schemas that have single-schema dialogs in the official train- ing set, so we treat cach of these schemas as a separate domain and randomly split dialogs within each domain into train/test splits at a 9:1 ratio.
A.1.2 Large Language Model Prompting Details
In this experiment, we used GPT-turbo-3.5 as well as FLAN-TS (Chung et al., 2022) as baseline next action predictors. We prompt the two LLMs us- ing the exact same prompting method. For each domain, we first randomly select 10 dialogs from the training split, and then use their trajectories (i.e. actions and statuses of each turn) as demon- strations. Then for every system utterance in the test-split dialogs in the domain, we include as many of the demonstration trajectories as possible with- out exceeding the max token limit of the LLMs, and then we include the partial trajectory of the test dialog up to the turn where the next system actions needs to be predicted. Lastly, we ask the LLM to predict the next system actions, and we programmatically parse the results into individual action items. See Figure for example prompt for SGD and MultiWOZ. dataset.
We then turn each dialog into trajectory (as defined in section 3.1). Below is how we define the dialog actions within each domain of each dataset: For SGD, since there are already very compre- hensive dialog acts and slot annotations, we directly use the acts defined in the dataset (with a few re- naming) plus the slot annotations to build our set of all possible actions. In addition, since SGD pro- vides explicit annotations about system's 's database queries, whenever the system queries database, we add additional turn in our trajectory with one action "SYSTEM query <intent>" and the status update would be either query success or query fail- ure.
When obtaining the baseline result for cach model, we use the top prediction by probability by setting temperature to zero (thus the language model's generation is deterministic). When we need to multiple predictions for graph filtering, for FLAM-T5-xXI
simply do beam-search of size 10; for GPT-turbo-3.5 we set temperature and sample 10 times.
A.2
Response Generation
A.2.1
Getting Alternates from each model
For Galaxy (He et al., 2022b), we used the top choice of beam-size-1 as well as the top 3 choices of beam-size-5 as alternates. The overall ranking
For MultiWOZ, we mostly also directly use the acts and slots the dataset annotation to build

---

of the 5 choices from highest lowest are baseline, beam-size-L, beam-size-5 top choice, beam-size-5 second choice, beam-size-5 third choice.
A.2.3 Using GPT NLU unit
We prompt GPT-turbo-3.5 to convert the candidate responses into action sets. For responses for di- alogs in each domain, We first provide randomly selected dialogs from the training split of the same domain together with their ground truth system actions as demonstrations. Then, we specify the desired output format and provide an example of the output format. Lastly, we provide the dialog history of the current candidate responses, and ask GPT to give actions all candidate responses (i.c. the baseline + sampled from the models). We start with demonstrations, and we reduce the number of demonstrations by one iteratively if the total number of tokens exceeds the maximum token limit of the model (4097). We show one example prompt for responses from Galaxy (He et al., 2022b) together with the GPT completion in Figure 5.
For HDNO (Wang et al., 2020), since the official prediction baseline is the top choice of beam-size- 5, we use the two choices from beam-size-2 and the second and third choice from beam-size-5 as alternates. The overall ranking of the 5 choices from highest to lowest are bascline (i.e. beam-size- 5 top choice), beam-size- top choice, beam-size- second choice, beam-size-2 second choice, beam- size-5 third choice.
For HDSA (Chen et al., 2019) the process is slightly different. HDSA model consists of 2 parts: the first part (predictor) predicts the actions the system will perform (although in very different format than what we do in our next action predic- tion experiment, so not directly comparable), and the second part (generator) uses the output of the predictor to generate the response. we fix the predictor output and do beam-search on the genera- tor only, the actions within the generated response will almost always be identical, which renders our method useless. Therefore, nates by tweaking hyperparameter in the predictor a little bit. The output of the predictor vector, and the post-sigmoid logits of the predictor is converted to the binary vector by a threshold. The HDSA official code repository has 0.4 as the default threshold, and we changed the threshold around that value and used the different generated vectors inputs to the generator obtain our alternates. The overall ranking of the 5 choices from highest to lowest are baseline, threshold-0.4, threshold-0.375. threshold-0.35, threshold-0.322
We evaluated the quality of this NLU process by using this process predict actions of the ground truth responses and compare the predicted actions to the ground truth actions on a subset of the test dialogs. We found that on average our NLU's pre- dicted actions achieves an average F-1 score of 77.6%, which is okay but far from perfect, and the imperfectness of our NLU brings additional challenge our task.
created our alter-
binary
B Human-drawn GT graphs for SGD
In order to perform qualitative assessment of the quality of our graphs, we manually drew graphs for 10 domains in SGD. We show 2 such graphs in Figure 6 for RideSharing__ I schema and Figure 7 for RentalCars_ schema respectively.
A.2.2 Evaluation Details
We use the official itory to evaluate the BLEUINFORRM/SSCCSSS metries. Since our policy-Icarning setting assumes that we have access the ground truth dialog state before the utterance, we use the ground truth di- alog state and active domains in the evaluation scripts (by removing dialog state / active domain predictions and only including the response in the prediction file). This is necessary because we found that active domain predictions affect the IN- FORM/SUCCESS metrics, and incorrect active do- main can increase/decrease INFORM/SUCCESS randomly. Therefore, to ensure fairness and con- sistency, we always use the ground truth active domain during evaluation.
Evaluation repos-

---

Demonstration:
USER Actions: Inform number of days, Inform Intent ReterveHotel
Status: Informed number of days, Intent Informed ReserveHotel
SYSTEM Actions: Request hotel name, Request check in date
Status: Requested hotel name, Requested check date
USER Actions: Inform number of rooms, Inform hotel name, Inform check in date
Status: Informed number of rooms, Informed hotel name, Informed check date
SYSTEM Actions: Confirm hotel name, Confirm check in date, Confirm number of days, Confirm number of rooms
Status: Confirmed hotel name, Confirmed check in date, Confirmed number days, Confirmed number of rooms
USER Actions: Request phone number, Request destination, Affirm
Status: Requested phone number, Requested destination, Affirmed
SYSTEM Actions: Query ReserveHotel
Status: DATABASE N=0 ReserveHotel
SYSTEM Actions: Inform phone number, Inform destination, Notify Success
Status: Informed phone number, Informed destination, Notified Success
USER Actions: Thank You, Goodbye
Status: Thanked, GOODBYE
SYSTEM Actions: Goodbye
Status: END OF DIALOG
Demonstration:
[... omitting demonstrations.. ...]
Based the demonstrations above, predict the next line of Action and Status below:
USER Actions: Inform Intent ReserveHotel
Status: Intent Informed ReserveHotel
SYSTEM Actions: Request hotel name, Request check date
Demonstration:
USER act: hotel-inform type, hotel-inform area, hotel-inform stars
Status: hotel-inform type, hotel-inform area, hotel-inform stars
SYSTEM act: hotel-inform name
Status: hotel-inform name
USER act: hotel-inform price
Status: hotel-inform price
SYSTEM act: booking-offerbbokk, hotel-inform price, hotel-inform stars
Status: booking-offerbook, hotel-inform price, hotel-inform stars
USER general-thank
Status: general-thank
SYSTEM act: general-bye
Status: general-bye
Demonstration:
[... omitting 5 demonstrations ...]
Based on the demonstrations above, predict the next line of SYSTEM Actions below:
USER act: hotel-inform area
Status: hotel-inform area
SYSTEM act: hotel-request type, hotel-request price
Figure 4: Example of using GPT-turbo-3.5 to do next system action prediction from the Hotels_ domain of SGD (top) and from the Hotel+Train domain of MultiWOZ (bottom). We first provide few demonstration trajectories the prompts, then we ask the large language model to complete the prompt. The text highlighted in green is the GPT completion, while everything before that is our input prompt. We give the exact same prompt to the other LLM (FLAN-T5-xXI)

---

Demonstration:
USER Utterance: am planning trip to pollue_departuee and looking for train get me there can you help me find
please
SYSTEM Utterance: we have many trains cambridge, where are you departing from
SYSTEM Actions: SYSTEM train-request depart SYSTEM train-inform num choices SYSTEM train-inform dest
departing from [value departure] and would like go [value_destingg destinattinn) would like my train to arrive by [value_arme arrive] and leave on [value_dale _uue___al_.___
USER Utterance:
SYSTEM Utterance: the [value_Ke __dd] arrives in [value_ destination] by [value_arrive] can book ticket for you
SYSTEM Actions: SYSTEM train-inform arrive SYSTEM train-inform dest SYSTEM train-inform id SYSTEM
train-offerbaok
[... omitting turns interactions... ...]
USER Utterance: not at this time. thank you for all the information. am all set goodbye.
SYSTEM Utterance: have nice day, goodbye
SYSTEM Actions: SYSTEM general-bye
Demonstration:
omitting more full dialog demonstrations ...]
Now, going to ask you to predict the actions from several candidate responses. Your answer format must fit the following example:
(1) [ is [value_food] restaurant
(2) there are [value choice] restaurant-s that meet your criteria serves [vadu food and the other serves [value food] food. you have a preference
(3) there are [value_choice] restaurant-s that meet that criteria serves [value_food] food and the other serves [value_food] food. which would you prefer ?
Your output should be:
(1) SYSTEM restaurant-infom name| SYSTEM restaurant-infomm food
(2) SYSTEM seseurrnttask-foo-eeeeee food SYSTEM restaurant-infomm num-choices SYSTEM restaurant-inform food
(3) SYSTEM restaurant-ask-for-seee food SYSTEM restaurant-inform num-cholces SYSTEM restaurant-infom food
Now consider the following partial dialog:
USER Utterance: am looking for a train that leaves on [value_dap] and arrives by 10.30
Based the demonstrations above, predict the SYSTEM Actions each of the following candidate SYSTEM response:
(1) can help you with that. where are you departing from and arriving
(2) where are you departing from and arriving to
(3) there are [valuee _choice] trains that meet that criteria where you departing from and arriving to
(4) are [value choice] trains available. where are you departing from arriving ?
(5) there are _cluuee_hhccee__ trains available. where are you departing from and arriving to
Your Answer:
(1) SYSTEM train-request depart SYSTEM train-request dest
2 SYSTEM train-request depart SYSTEM train-request dest
(3) SYSTEM train-inform num choices SYSTEM train-request depart SYSTEM train-request dest
SYSTEM train-inform choices SYSTEM train-request depart SYSTEM train-request dest
SYSTEM train-inform num choices SYSTEM train-request depart SYSTEM train-request dest
Figure 5: Example of using GPT-turbo-3. to obtain actions from candidate responses from Galaxy (He al., 2022b). The parts highlighted in green are completion from GPT, and everything before that our prompt.

---

T9R DHE
WEaDE Stade
TEES WITH
Que GOM
DHICK
Figure Human- -raann ground truth graph for RideSharing 1 domain SGD.

---

Figure 7: Human-drawe ground truth graph for RentalCars I domain in SGD.


Reviews:
[{"review_id": "iEEnY3hFij", "reviewer": "Reviewer_irFm", "summary": "", "questions": "1. Instead of inducting the graph automatically, are there any ways to manually design such a graph? If we use a finely curated graph, how would it affect the model's performance?", "limitations": "", "rating": 3, "confidence": 4, "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": "We thank the reviewer for the helpful feedback. We are encouraged that the reviewer found our work well motivated and is widely applicable to more domains/scenarios. We address the reviewer’s concerns below.\n\n> Novelty of TOD-Flow compared to previous works [Jang et al., 2023, Logeswaran et al., 2023]\n\nWe note that Logeswaran et al., 2023 used the graph inference algorithm proposed in MSG2 (Jang et al., 2023) as-is, so we will only compare with MSG2. \n1. Our method infers **Can**, **Shd**, and **Shdnt** relations while MSG2 only infers the precondition which is equivalent to **Can** relation. Note that **Shd**, and **Shdnt** relations can also be inferred and used for the next subtask prediction task in MSG2 setting. \n\n2. Ours and MSG2 optimize different objectives for precondition (or **Can**) inference. If we ignore minor implementation details, we can directly compare their objective functions as follows:\n$$\n\\begin{align}\nJ_\\text{ours}   &= P(f_n(c)=1, a[n]=1) + \\alpha P(f_n(c)=0, a[n]=0)\\newline\nJ_\\text{MSG2}&= P(f_n(c)=1, a[n]=1) / P(f_n(c)=1)+ \\beta C( f_n )\\newline\nJ_\\text{ILP}     &= P(f_n(c)=1, a[n]=1),\n\\end{align}\n$$\nwhere $f_n(\\cdot)$ is the n-th precondition function, $c$ is the completion set, $a[n]$ is whether the n-th action (\\ie, dialog act and slot) is performed, and $\\alpha$ and $\\beta$ are the hyperparameters.\nMSG2 and ours modify the original ILP objective ($J_\\text{ILP}$) differently. At a high level, MSG2 prevents overly optimistic preconditions by multiplying $1/P(f(c)=1)$, and adds complexity regularization $C(f)$ to prevent overfitting. Ours instead infers **Can** and **Shdnt** relationships *simultaneously* (see Section 3.3), where **Shdnt** regularizes the **Can** inference. Our experiments show ours produces a significantly better graph than MSG2.\n\n3. The implementations differ: ours learned a decision tree while MSG2 used beam search in the precondition space, as the complexity regularization term in MSG2 is hard to be incorporated into decision tree learning.\n\n> “The evaluation protocol using untuned base models on graph-augmented data raises doubts about potential gains from graph-informed training.”\n\nIn our experiment, all the models only use the given annotated dialogue data, and our graph is not used to augment or alter the data. Also, all the models use the same un-tuned base models: FLAN-T5 and GPT-turbo. Once the graph is inferred from given annotations in the training set, it is then used to filter, add, and remove predictions (see Figure 2 in the paper) of a base model during testing. Thus, we claim that the reported performance gains purely come from conditioning the dialogue model with our inferred graph.\n\n> Comparison with traditional BC or RL-based dialogue policy baselines\n\nOur base dialogue policies (GPT-turbo and FLAN-T5) observe only five dialogue trajectories as a part of the prompt. We observed that the BC or RL dialogue policies trained on five trajectories severely overfit to the training trajectories. Thus, we did not consider BC or RL-based baselines in a low-data regime.\n\n> Ablation experiment with hand-drawn graph\n\nWe manually curated **Can** and **Shdnt** conditions for the *RideSharing_1* domain in SGD by manually examining schemas and raw dialogs. We skipped the **Shd** condition due to its complexity. We then compared this to our inferred **Can** and **Shdnt** conditions by evaluating dialog policy. The results are summarized in the table below.\n\n|                       | FLAN-T5 | GPT-Turbo |\n|-----------------------|---------|-----------|\n| No Graph              | 0.574   | 0.800     |\n| Human-drawn           | 0.773   | 0.857     |\n| Ours (Can+Shdnt-only) | 0.780   | 0.864     |\nTable. Average F-1 scores of next system action prediction on *RideSharing_1* domain.\n\nSummary of observations:\n* The Human-drawn graph achieved similar improvements as ours (see Table above) in next system action prediction. Ours slightly outperforms the human-drawn graph.\n* Our inferred graph models more complex dialog relations than human-drawn graphs (226 vs 62 edges). Humans tend to simplify or miss minor relationships.\n* In general, Human-drawn graphs are costly and do not scale, taking our annotator 3 hours even for the simplest domain, *RideSharing_1*. Our automated inference is cheaper and more scalable, taking only around 2 seconds for graph inference.", "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": "1. Augmenting the dialogue policy with a graph structure is well-motivated, and is well-backed by the explorations on other tasks (e.g., videos and transcripts) as discussed in the paper.\n\n2. The task sub-graph is induced from raw dialogue data without introducing auxiliary annotation efforts. This promotes the availability of applying the proposed approach to more domains/scenarios.", "reasons_to_reject": "1. It is unclear how much novelty the proposed approach offers in comparison to existing sub-graph applications such as those by Jang et al. and Logeswaran et al. It seems the proposed approach is extending a well-established technique by introducing some TOD-tailored rules (should & shouldn't inference). An in-depth discussion should be added.\n\n2. The evaluation protocol for the experiments involving the policy w/ and w/o graph augmentation is confusing. An off-the-shelf model (either a trained T5 or ChatGPT) is used for evaluation. However, the base models have not been tuned using the graph-augmented TOD data. This raises doubts about whether considering graph structures during training could lead to performance gains.\n\n3. The selection of baselines might not be comprehensive. In Table 2, only prompting methods are considered. It is crucial to consider policy models that learn through traditional BC or RL rather than solely relying on a pre-trained LLM.", "questions_to_authors": "1. Instead of inducting the graph automatically, are there any ways to manually design such a graph? If we use a finely curated graph, how would it affect the model's performance?", "paper_topic_and_main_contributions": "The paper introduces TOD-Flow, a novel approach that models the structure of task-oriented dialogues by inferring TOD-flow graphs from annotated dialogue data. The main contributions include the development of a method that uncovers the underlying task structure in the form of a graph, leading to better transparency, controllability, and prediction performance in dialogue models, as well as providing a rationale for the model's predictions by effectively reducing the search space.", "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": {}}, {"review_id": "niQA6y8Cna", "reviewer": "Reviewer_CAsX", "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": "We thank the reviewer for the helpful comments. We are glad to see that the reviewer acknowledges that 1) our experiment shows the effectiveness of our graph inference method on two dialog tasks, 2) our work provides sufficient support for our main claim, and 3) the paper is well-written. We address reviewer concerns below.\n\n> Reasons for using the graph structure beyond performance gains\n\nRepresenting real-world tasks (e.g. videos, dialogs) as complex structures offers multiple benefits. First, it improves model transparency, as the graph explains predictions by showing actions the model can, should, and shouldn't take. Second, it enables controllability by modifying the graph to change model behavior. For example, a banking chatbot's loan criteria could be updated by editing the graph, without retraining the entire model. Third, the representation enhances accessibility of information to humans (Vicol et al. 2018; Wang and Gupta 2018; Zhao et al. 2022). Fourth, it provides downstream advantages like aiding planning and execution (Liu et al. 2022; Sohn et al. 2020).\n\n[1] Vicol, P.; Tapaswi, M.; Castrejo ́n, L.; and Fidler, S. 2018. MovieGraphs: Towards Understanding Human-Centric Situations from Videos. In CVPR.\n\n[2] Wang, X.; and Gupta, A. 2018. Videos as Space-Time Region Graphs . In ECCV.\n\n[3] Zhao, B.; Li, H.; Lu, X.; and Li, X. 2022. Reconstructive Sequence- Graph Network for Video Summarization. TPAMI.\n\n[4] Liu, A. Z.; Sohn, S.; Qazwini, M.; and Lee, H. 2022. Learning Pa- rameterized Task Structure for Generalization to Unseen Entities. In AAAI.\n\n[5] Sohn, S.; Woo, H.; Choi, J.; and Lee, H. 2020. Meta Reinforcement Learning with Autonomous Inference of Subtask Dependencies. In ICLR.\n\n> Novelty: how is the method different from previous works\n\nPlease refer to the first response to Reviewer irFm.\n\n> Comparison with learning latent dialogue structure [1, 2]\n\nWe thank the reviewer for suggesting relevant works [1, 2]. We agree that [1, 2] and ours share the high-level motivation: capturing the structure of dialog. However, there are several significant differences between our direction and [1, 2]. Here are the summary of differences:\n* The notion of “structure” differs significantly: ours model the dependency (or **Can**, **Shd**, **Shdnt** conditions) between dialog acts and slots, while [1, 2] tries to model the context, progress, persona, etc\n* In turn, the learning methodology also differs: ours use an inductive logic programming method to capture the logic rule, while [1, 2] uses variational inference and self-supervised learning to model the latent representations.\n* Our graph is independently inferred from the dialogue data; this inference process is independent of the base dialogue model used. Then the inferred graph works as an add-on to any base models, without any training. In [1, 2], the latent structure is a part of dialogue model, and the entire model is pre-trained (and finetuned) on large data.\n\n> Analysis: Efficiency of each method\n\nWe first measured the efficiency of each method in terms of the graph construction time (in seconds). Below is the graph construction time for the 5 domains (Attraction, Taxi, Train, Hotel, Restaurant) dialogs from MultiWOZ:\n\n| Domain | TOD-Flow No Shd | BC       | MSG2        |TOD-Flow    |\n|------------|--------------|-------------|-------------|-------------|\n| Attraction |  2.11 | 1.11 |  1.80 | 14.31 |\n| Taxi       |  2.65 | 2.82 | 1.76 | 28.96 |\n| Train      |  5.97 | 7.33 | 12.27 | 402.60 |\n| Hotel      |  30.72 | 26.26 | 49.72 |  540.16 |\n| Restaurant |  47.74 | 35.96 | 61.70 | 438.74 |\n\nNext, we measured the inference time for graph-based action ranking. For action ranking, it computes whether the **Can**, **Shd**, and **Shdnt** conditions are met for each action. Per each turn, all the graph inference methods took less than 0.002 second for evaluating the condition satisfaction, which is negligible compared to the response generation time: 0.46 sec for FLAN-T5 and 0.58 sec for GPT-turbo.", "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 propose method show its effectiveness in graph structure inference as well as two subtasks relevant to dialogues.\n- The writing of this paper is clear and the figure is illustrating.", "reasons_to_reject": "- This paper is not well motivated. Although the performance improved, it is not clear to me why using such structure how it is different from previous works.\n- Lack of comparison and baselines with works that focus on dialogue structures such as [1][2]\n- Although the efficiency is not the most focus of this paper, i believe it should be at least discussed.\n\n\n[1] Towards Efficient Dialogue Pre-training with Transferable and Interpretable Latent Structure\n[2] DialogVED: A Pre-trained Latent Variable Encoder-Decoder Model for Dialog Response Generation", "questions_to_authors": "", "paper_topic_and_main_contributions": "This study presents a new framework to enhance the efficiency and predictive accuracy of task-oriented dialogue models. By using the idea of a subtask graph and expanding it to a TOD-flow graph, the hidden task structure within a dialogue can be accurately determined. Extensive experiments with two public TOD datasets have demonstrated the effectiveness of this method in generating accurate and easily understandable graphs. Crucially, these inferred graphs have been integrated with various dialogue models without the need for retraining, leading to significant improvements in both dialogue act classification and end-to-end response generation.", "excitement": 3, "reproducibility": 4, "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": "oKJjqPIxNN", "reviewer": "Reviewer_uYLX", "summary": "", "questions": "In addition, I have several questions for the authors:\n\n1.In the 3.1 Problem Formulation section, the authors state that the goal of the TOD-flow graph learning task is to generate the TOD-flow graph G given dialog data D. Could the authors elaborate on how the model is trained to generate the TOD-flow graph? What is the structure of the model, and what is the format of the dataset used for training? Providing a concrete example would be helpful to understand the process better.\n\n2.In the \"Graph-conditioned End-to-end Response Generation\" section, the authors use the GPT-turbo model to annotate each generated candidate utterance with the dialogue act. How does the model ensure the accuracy of GPT-turbo's generated annotations? Additionally, how does the inferred graph guide the selection of the best response?", "limitations": "", "rating": 4, "confidence": 3, "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": "We thank the reviewer for the helpful comments. We are glad to see that the reviewer acknowledges that 1) our method is novel and exciting, and 2) the paper presents a rich set of experiments demonstrating the effectiveness of the method. We address reviewer concerns below.\n\n> Detailed process of graph inference: data and model\n\nLet $D_{G}=$ {($c_t, a_t$)} be the graph inference dataset, introduced in the first paragraph of Section 3.3. The action set $a_t$ is the set of dialog acts that were performed at turn $t$. The completion set $c_t$ is the set of dialog acts and database query that has ever been performed before turn $t$. Then, we construct the TOD-flow graph in terms of **Can**+**Shdnt** and **Shd** conditions from the dataset $D_{G}$. Intuitively, the goal is to find the binary function $f: c \\mapsto$ \\{0, 1\\} that maximizes the objectives in equation (1) and (4) for **Shd** and **Can**+**Shdnt**, respectively. We model the Boolean function with a binary decision tree, and use the Classification and regression tree (CART) algorithm to fit the binary decision tree to the dataset $D_{G}$. At each branching step of precondition inference for $n$-th action, the algorithm chooses the optimal feature (or each component of completion set $c_t$) that best discriminates the positive and negative samples (i.e., $a_t[n]=0$ or $1$) in terms of gini impurity [1]. The resulting decision tree (i.e., Boolean function) can be in turn represented as either Boolean expression or TOD-flow graph as explained in Section 2. We will include this detail in the revised paper.\n\n[1] Breiman, Leo; Friedman, J. H.; Olshen, R. A.; Stone, C. J., 1984, Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software\n\n> Accuracy of NLU module (i.e., GPT-turbo’s generated annotations) in end-to-end experiment\n\nWe reported the accuracy of GPT-turbo-based annotations in Appendix A.2.3. Our few-shot prompted GPT-turbo scored 77.6% accuracy on predicting the dialog act annotation in MultiWOZ, which is reasonable but still far from perfect. We believe that with a more sophisticated NLU module with higher annotation accuracy, our method will generate more accurate graph and provide bigger improvement on base models.\n\n> How does the inferred graph guide the selection of the best response?\n\nGiven the multiple responses sampled from the base end-to-end dialogue model, our graph can be used to select the best response among them. The process is described in Section 4.2, lines 309-312. Intuitively, we measure how many *violations* were made in each response with respect to the **Can**, **Shd**, and **Shdnt** conditions in the inferred graph. Specifically, given a response, we use a few-shot prompted GPT annotator to annotate the response with dialog acts and slots. Then, we examine the predicted annotation with respect to the **Can**, **Shd**, and **Shdnt** conditions in the inferred graph. For example, if the response contains a (dialog act, slot) pair whose **Can** condition is not satisfied, then it is a violation of **Can** condition. We choose the response with minimum violation rate (i.e., among all the predicted annotations, how many annotations violate the graph). We will include this detailed explanation in the revised 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": "1.The paper introduces a novel method for inferring the TOD-flow graph from annotated dialogue data, which enhances transparency and controllability in task-oriented dialogue systems.\n2. The paper includes a rich set of experiments, demonstrating the effectiveness of the proposed approach in improving dialog act classification and end-to-end response generation performance.", "reasons_to_reject": "Some aspects of the proposed model are not thoroughly described, leaving room for ambiguity.", "questions_to_authors": "In addition, I have several questions for the authors:\n\n1.In the 3.1 Problem Formulation section, the authors state that the goal of the TOD-flow graph learning task is to generate the TOD-flow graph G given dialog data D. Could the authors elaborate on how the model is trained to generate the TOD-flow graph? What is the structure of the model, and what is the format of the dataset used for training? Providing a concrete example would be helpful to understand the process better.\n\n2.In the \"Graph-conditioned End-to-end Response Generation\" section, the authors use the GPT-turbo model to annotate each generated candidate utterance with the dialogue act. How does the model ensure the accuracy of GPT-turbo's generated annotations? Additionally, how does the inferred graph guide the selection of the best response?", "paper_topic_and_main_contributions": "The paper proposes a novel approach to address the limitations of pre-trained language models (PLMs) in Task-Oriented Dialogue (TOD) systems regarding transparency and controllability. The approach focuses on inferring the TOD-flow graph from dialogue data annotated with dialogue acts, revealing the underlying task structure in a graph format. The inferred TOD-flow graph can be integrated with any dialogue model to enhance prediction performance, transparency, and controllability. The graph guides the model on what to predict, what not to predict, and provides a rationale for the model's predictions. The experiments demonstrate that the proposed TOD-flow graph closely resembles human-annotated graphs and significantly improves dialog act classification and end-to-end response generation performance in benchmark datasets.\n\nStrengths:\n\n1.The paper introduces a novel method for inferring the TOD-flow graph from annotated dialogue data, which enhances transparency and controllability in task-oriented dialogue systems.\n2. The paper includes a rich set of experiments, demonstrating the effectiveness of the proposed approach in improving dialog act classification and end-to-end response generation performance.\n\nWeaknesses:\n\nSome aspects of the proposed model are not thoroughly described, leaving room for ambiguity.", "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": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents TOD-flow, a new approach to extract conversation flow graphs from dialogue dataset annotated with dialogue acts. The paper is well-written with helpful illustrating figures. The propose method shows its effectiveness in graph structure inference as well as two subtasks relevant to dialogues. The selection of baseline in evaluation was challenged by reviewers -- which the authors agreed to and provided further comparison during rebuttal.
Decision: Accept-Main