Scalable and Accurate Dialogue State Tracking via Hierarchical Sequence
Generation
Liliang Ren, Jianmo Ni and Julian McAuley
University of California, San Diego
La Jolla, CA92093{lren,jin018,jmcauley}@ucsd.edu

1

Abstract

DST Models

ITC

Existing approaches to dialogue state tracking rely on pre-defined ontologies consistingof a set of all possible slot types and values.
Though such approaches exhibit promising
performance on single-domain benchmarks,
they suffer from computational complexitythat increases proportionally to the number of
pre-defined slots that need tracking. This issue becomes more severe when it comes tomulti-domain dialogues which include larger
numbers of slots. In this paper, we investigate how to approach DST using a generation
framework without the pre-defined ontology
list. Given each turn of user utterance andsystem response, we directly generate a sequence of belief states by applying a hierarchical encoder-decoder structure. In this way, thecomputational complexity of our model will
be a constant regardless of the number of predefined slots. Experiments on both the multidomain and the single domain dialogue state
tracking dataset show that our model not only
scales easily with the increasing number of
pre-defined domains and slots but also reaches
the state-of-the-art performance.

NBT-CNN (Mrksic et al., 2017)
MD-DST (Rastogi et al., 2017)
GLAD (Zhong et al., 2018)
StateNet PSI (Ren et al., 2018)
TRADE (Wu et al., 2019)
HyST (Goel et al., 2019)
DSTRead (Gao et al., 2019)

O(mn)
O(n)
O(mn)
O(n)
O(n)
O(n)
O(n)

Introduction

A Dialogue State Tracker (DST) is a core component of a modular task-oriented dialogue system(Young et al., 2013). For each dialogue turn, a
DST module takes a user utterance and the dialogue history as input, and outputs a belief estimate of the dialogue state. Then a machine action
is decided based on the dialogue state according toa dialogue policy module, after which a machine
response is generated.
Traditionally, a dialogue state consists of a setof requests and joint goals, both of which are represented by a set of slot-value pairs (e.g. (request,
phone), (area, north), (food, Japanese)) (Henderson et al., 2014). In a recently proposed multi-

Table 1: The Inference Time Complexity (ITC) of previous DST models. The ITC is calculated based on how
many times inference must be performed to complete a
prediction of the belief state in a dialogue turn, wherem is the number of values in a pre-defined ontology list
and n is the number of slots.

domain dialogue state tracking dataset, MultiWoZ(Budzianowski et al., 2018), a representation of
dialogue state consists of a hierarchical structureof domain, slot, and value is proposed. This is amore practical scenario since dialogues often include multiple domains simultaneously.
Many recently proposed DSTs (Zhong et al.,2018; Ramadan et al., 2018) are based on predefined ontology lists that specify all possible slot
values in advance. To generate a distribution overthe candidate set, previous works often take eachof the slot-value pairs as input for scoring. However, in real-world scenarios, it is often not practical to enumerate all possible slot value pairs andperform scoring from a large dynamically changing knowledge base (Xu and Hu, 2018). To tackle
this problem, a popular direction is to build afixed-length candidate set that is dynamically updated throughout the dialogue development. Table 1 briefly summaries the inference time complexity of multiple state-of-the-art DST models
following this direction. Since the inference complexity of all of previous model is at least pro-

portional to the number of the slots, these models will struggle to scale to multi-domain datasetswith much larger numbers of pre-defined slots.
In this work, we formulate the dialogue state
tracking task as a sequence generation problem,
instead of formulating the task as a pair-wise prediction problem as in existing work. We propose the COnditional MEmory Relation Network(COMER), a scalable and accurate dialogue state
tracker that has a constant inference time complexity. 1
Specifically, our model consists of an encoderdecoder network with a hierarchically stacked decoder to first generate the slot sequences in the belief state and then for each slot generate the corresponding value sequences. The parameters areshared among all of our decoders for the scalability of the depth of the hierarchical structure of thebelief states. COMER applies BERT contextualized word embeddings (Devlin et al., 2018) andBPE (Sennrich et al., 2016) for sequence encoding to ensure the uniqueness of the representationsof the unseen words. The word embeddings forsequence generation are initialized with the static
word embeddings generated from BERT .

2

Motivation

Figure 1 shows a multi-domain dialogue in which
the user wants the system to first help book a train
and then reserve a hotel. For each turn, the DST
will need to track the slot-value pairs (e.g. (arrive by, 20:45)) representing the user goals as wellas the domain that the slot-value pairs belongs to(e.g. train, hotel). Instead of representing the belief state via a hierarchical structure, one can also
combine the domain and slot together to form a
combined slot-value pair (e.g. (train; arrive by,
20:45) where the combined slot is “train; arriveby”), which ignores the subordination relationshipbetween the domain and the slots.
A typical fallacy in dialogue state tracking
datasets is that they make an assumption that theslot in a belief state can only be mapped to a single value in a dialogue turn. We call this the single value assumption. Figure 2 shows an example of this fallacy from the WoZ2.0 dataset: Basedon the belief state label (food, seafood), it will be
impossible for the downstream module in the dialogue system to generate sample responses that1
The code is released at https://github.com/
renll/ComerNet

Figure 1: An example dialogue from the multi-domain
dataset, MultiWOZ. At each turn, the DST needs to
output the belief state, a nested tuple of (DOMAIN,(SLOT, VALUE)), immediately after the user utterance
ends. The belief state is accumulated as the dialogue
proceeds. Turns are separated by black lines.

Figure 2: An example in the WoZ2.0 dataset that invalidates the single value assumption. It is impossible forthe system to generate the sample response about the
Chinese restaurant with the original belief state (food,seafood). A correction could be made as (food, seafood> chinese) which has multiple values and a logical operator “>”.

return information about Chinese restaurants. A
correct representation of the belief state could be(food, seafood > chinese). This would tell thesystem to first search the database for information
about seafood and then Chinese restaurants. The
logical operator “>” indicates which retrieved information should have a higher priority to be returned to the user. Thus we are interested in building DST modules capable of generating structured
sequences, since this kind of sequence representation of the value is critical for accurately capturing
the belief states of a dialogue.

3

Hierarchical Sequence Generation for
DST

Given a dialogue D which consists of T turns ofuser utterances and system actions, our target is topredict the state at each turn. Different from pre-Figure 3: The general model architecture of the Hierarchical Sequence Generation Network. The Conditional
Memory Relation (CMR) decoders (gray) share all of their parameters.

vious methods which formulate multi-label stateprediction as a collection of binary prediction
problems, COMER adapts the task into a sequence
generation problem via a Seq2Seq framework.
As shown in Figure 3, COMER consists ofthree encoders and three hierarchically stacked decoders. We propose a novel Conditional Memory
Relation Decoder (CMRD) for sequence decoding. Each encoder includes an embedding layer
and a BiLSTM. The encoders take in the user utterance, the previous system actions, and the previous belief states at the current turn, and encodes
them into the embedding space. The user encoder
and the system encoder use the fixed BERT modelas the embedding layer.
Since the slot value pairs are un-ordered set elements of a domain in the belief states, we firstorder the sequence of domain according to theirfrequencies as they appear in the training set (Yanget al., 2018), and then order the slot value pairs in
the domain according to the slot’s frequencies ofas they appear in a domain. After the sorting of
the state elements, We represent the belief states
following the paradigm: (Domain1- Slot1, Value1;
Slot2, Value2; ... Domain2- Slot1, Value1; ...) fora more concise representation compared with thenested tuple representation.
All the CMRDs take the same representations
from the system encoder, user encoder and the belief encoder as part of the input. In the proce-dure of hierarchical sequence generation, the first
CMRD takes a zero vector for its condition input
c, and generates a sequence of the domains, D, as
well as the hidden representation of domains HD .
For each d in D, the second CMRD then takes thecorresponding hd as the condition input and generates the slot sequence Sd , and representations,HS,d . Then for each s in S, the third CMRD generates the value sequence Vd,s based on the corresponding hs,d . We update the belief state with thenew (d, (sd , Vd,s )) pairs and perform the procedure iteratively until a dialogue is completed. All
the CMR decoders share all of their parameters.
Since our model generates domains and slots instead of taking pre-defined slots as inputs, and thenumber of domains and slots generated each turnis only related to the complexity of the contents
covered in a specific dialogue, the inference timecomplexity of COMER is O(1) with respect to thenumber of pre-defined slots and values.
3.1

Encoding Module

Let X represent a user utterance or systemtranscript consisting of a sequence of words{w1 , . . . , wT }. The encoder first passes the sequence {[CLS ], w1 , . . . , wT , [SEP ]} into a pretrained BERT model and obtains its contextual
embeddings EX . Specifically, we leverage theoutput of all layers of BERT and take the average
to obtain the contextual embeddings.

For each domain/slot appeared in the training
set, if it has more than one word, such as ‘pricerange’, ‘leave at’, etc., we feed it into BERT andtake the average of the word vectors to form theextra slot embedding Es . In this way, we map eachdomain/slot to a static embedding, which allows
us to generate a domain/slot as a whole instead ofa token at each time step of domain/slot sequence
decoding. We also construct a static vocabularyembedding Ev by feeding each token in the BERT
vocabulary into BERT. The final static word embedding E is the concatenation of the Ev and Es .
After we obtain the contextual embeddings forthe user utterance, system action, and the static
embeddings for the previous belief state, we feedeach of them into a Bidirectional LSTM (Hochreiter and Schmidhuber, 1997).
hat = BiLSTM(eXat , hat−1 )hut = BiLSTM(eXut , hut−1 )hbt = BiLSTM(eXbt , hbt−1 )(1)

ha0 = hu0 = hb0 = c0 ,where c0 is the zero-initialized hidden state for
the BiLSTM. The hidden size of the BiLSTM isdm /2. We concatenate the forward and the backward hidden representations of each token fromthe BiLSTM to obtain the token representation
hkt ∈ Rdm , k ∈ {a, u, b} at each time step t.
The hidden states of all time steps are concatenated to obtain the final representation of Hk ∈RT ×dm , k ∈ {a, u, B}. The parameters are shared
between all of the BiLSTMs.
3.2

the model size, and ls is the generated sequencelength. The general structure of the CMR decoder
is shown in Figure 4. Note that the CMR decoder
can support additional memory sources by adding
the residual connection and the attention block,but here we only show the structure with threesources: belief state representation (HB ), systemtranscript representation (Ha ), and user utterance
representation (Hu ), corresponding to a dialogue
state tracking scenario. Since we share the parameters between all of the decoders, thus CMRD
is actually a 2-dimensional auto-regressive modelwith respect to both the condition generation andthe sequence generation task.
At each time step t, the CMR decoder first embeds the token xt with a fixed token embeddingE ∈ Rde ×dv , where de is the embedding size anddv is the vocabulary size. The initial token x0 is“[CLS]”. The embedded vector ext is then encoded with an LSTM, which emits a hidden representation h0 ∈ Rdm ,h0 = LSTM(ext , qt−1 ).
where qt is the hidden state of the LSTM. q0 is
initialized with an average of the hidden states ofthe belief encoder, the system encoder and the user
encoder which produces HB , Ha , Hu respectively.
h0 is then summed (element-wise) with the condition representation c ∈ Rdm to produce h1 ,which is (1) fed into the attention module; (2)used for residual connection; and (3) concatenatedwith other hi , (i > 1) to produce the concatenatedworking memory, r0 , for relation reasoning,

Conditional Memory Relation Decoder

Inspired by Residual Dense Networks (Zhang
et al., 2018), End-to-End Memory Networks(Sukhbaatar et al., 2015) and Relation Networks(Santoro et al., 2017), we here propose the Conditional Memory Relation Decoder (CMRD). Givena token embedding, ex , CMRD outputs the next
token, s, and the hidden representation, hs , withthe hierarchical memory access of different encoded information sources, HB , Ha , Hu , and therelation reasoning under a certain given conditionc,s, hs = CMRD(ex , c, HB , Ha , Hu ),the final output matrices S, Hs ∈ Rls ×dm are concatenations of all generated s and hs (respectively)
along the sequence length dimension, where dm is

h1 = h0 + c,h2 = h1 + Attnbelief (h1 , He ),h3 = h2 + Attnsys (h2 , Ha ),h4 = h3 + Attnusr (h3 , Hu ),r = h1 ⊕ h2 ⊕ h3 ⊕ h4 ∈ R4dm ,where Attnk (k ∈ {belief, sys, usr}) are the attention modules applied respectively to HB , Ha , Hu ,and ⊕ means the concatenation operator. The gradients are blocked for h1 , h2 , h3 during the backpropagation stage, since we only need them towork as the supplementary memories for the relation reasoning followed.
The attention module takes a vector, h ∈ Rdm ,and a matrix, H ∈ Rdm ×l as input, where l is thesequence length of the representation, and outputs

Figure 4: The general structure of the Conditional Memory Relation Decoder. The decoder output, s (e.g. “food”),
is refilled to the LSTM for the decoding of the next step. The blue lines in the figure means that the gradients areblocked during the back propagation stage.

ha , a weighted sum of the column vectors in H.
a = W1T h + b1

∈ Rdm ,

c = softmax(H T a)

∈ Rl ,

h = Hc∈ Rdm ,

ha = W2T h + b2

∈ Rdm ,

where the weights W1 ∈ Rdm ×dm , W2 ∈Rdm ×dm and the bias b1 ∈ Rdm , b2 ∈ Rdm are
the learnable parameters.
The order of the attention modules, i.e., first attend to the system and the user and then the belief, is decided empirically. We can interpret thishierarchical structure as the internal order for the
memory processing, since from the daily life experience, people tend to attend to the most contemporary memories (system/user utterance) first andthen attend to the older history (belief states). Allof the parameters are shared between the attention
modules.
The concatenated working memory, r0 , is thenfed into a Multi-Layer Perceptron (MLP) with four
layers,r1 = σ(W1T r0 + b1 ),r2 = σ(W2T r1 + b2 ),r3 = σ(W3T r2 + b3 ),hk = σ(W4T r3 + b4 ),where σ is a non-linear activation, and the weights
W1 ∈ R4dm ×dm , Wi ∈ Rdm ×dm and the bias
b1 ∈ Rdm , bi ∈ Rdm are learnable parameters,and 2 ≤ i ≤ 4. The number of layers for the MLP
is decided by the grid search.
The hidden representation of the next token, hk ,is first fed into a dropout layer with drop rate p,
and then (1) emitted out of the decoder as a representation; and (2) fed into a linear layer to generate
the next token,
hs = dropout(hk )∈ Rdm ,

ho = WkT hs + bs

∈ Rde ,

ps = softmax(E T ho )∈ Rdv ,

s = argmax(ps )∈ R,where the weight Wk ∈ Rdm ×de and the bias
bk ∈ Rde are learnable parameters. Since de isthe embedding size and the model parameters are
independent of the vocabulary size, the CMR decoder can make predictions on a dynamic vocabulary and implicitly supports the generation of unseen words. When training the model, we minimize the cross-entropy loss between the output
probabilities, ps , and the given labels.

4

Experiments

4.1

Experimental Setting

We first test our model on the single domain
dataset, WoZ2.0 (Wen et al., 2017). It consists

Metric

WoZ2.0MultiWoZ

Avg. # turns, t
Avg. tokens / turn, s
Number of Slots, n
Number of Values, mTraining set size
Validation set size
Test set size

7.45
11.24
3
99
600
200
400

13.68
13.18
35
4510
8438
1000
1000

only need to require the predicted belief dictionary to be exactly matched with the labels during model evaluation. We also did a simple postprocessing to remove the generated (DOMAIN,
SLOT, VALUE) triplets which have empty elements. In this work, the model with the highest
joint accuracy on the validation set is evaluated on
the test set for the test joint accuracy measurement.
4.2

Table 2: The statistics of the WoZ2.0 and the MultiWoZ datasets.

of 1,200 dialogues from the restaurant reservation
domain with three pre-defined slots: food, pricerange, and area. Since the name slot rarely occurs
in the dataset, it is not included in our experiments,
following previous literature (Ren et al., 2018; Liuand Perez, 2017). Our model is also tested on themulti-domain dataset, MultiWoZ (Budzianowski
et al., 2018). It has a more complex ontology with
7 domains and 25 predefined slots. Since the combined slot-value pairs representation of the belief
states has to be applied for the model with O(n)ITC, the total number of slots is 35. The statisticsof these two datsets are shown in Table 2.
Based on the statistics from these two datasets,
we can calculate the theoretical Inference TimeMultiplier (ITM), K, as a metric of scalability.
Given the inference time complexity, ITM measures how many times a model will be slower
when being transferred from the WoZ2.0 dataset,
d1 , to the MultiWoZ dataset, d2 ,K = h(t)h(s)h(n)h(m)(1O(x) = O(1),xd2
h(x) =
otherwise,xd1

where O(x) means the Inference Time Complexity (ITC) of the variable x. For a model having an
ITC of O(1) with respect to the number of slots
n, and values m, the ITM will be a multiplier of
2.15x, while for an ITC of O(n), it will be a multiplier of 25.1, and 1,143 for O(mn).
As a convention, the metric of joint goal accuracy is used to compare our model to previous work. The joint goal accuracy regards themodel making a successful belief state prediction
if all of the slots and values predicted are exactly
matched with the labels provided. Since our model
also generate un-ordered domains and slots, we

Implementation Details

We use the BERTlarge model for both contextual
and static embedding generation. All LSTMs in
the model are stacked with 2 layers, and only theoutput of the last layer is taken as a hidden representation. ReLU non-linearity is used for the activation function, σ.
The hyper-parameters of our model are identicalfor both the WoZ2.0 and the MultiwoZ datasets:
dropout rate p = 0.5, model size dm = 512, embedding size de = 1024. For training on WoZ2.0,
the model is trained with a batch size of 32 andthe ADAM optimizer (Kingma and Ba, 2015) for
150 epochs, while for MultiWoZ, the AMSGrad
optimizer (Reddi et al., 2018) and a batch size of
16 is adopted for 15 epochs of training. For both
optimizers, we use a learning rate of 0.0005 witha gradient clip of 2.0. We initialize all weights in
our model with Kaiming initialization (He et al.,2015) and adopt zero initialization for the bias. All
experiments are conducted on a single NVIDIAGTX 1080Ti GPU.
4.3

Results

To measure the actual inference time multiplier ofour model, we evaluate the runtime of the bestperforming models on the validation sets of boththe WoZ2.0 and MultiWoZ datasets. During evaluation, we set the batch size to 1 to avoid the influence of data parallelism and sequence padding. On
the validation set of WoZ2.0, we obtain a runtimeof 65.6 seconds, while on MultiWoZ, the runtime
is 835.2 seconds. Results are averaged across 5
runs. Considering that the validation set of MultiWoZ is 5 times larger than that of WoZ2.0, theactual inference time multiplier is 2.54 for ourmodel. Since the actual inference time multiplierroughly of the same magnitude as the theoreticalvalue of 2.15, we can confirm empirically that wehave the O(1) inference time complexity and thus
obtain full scalability to the number of slots andvalues pre-defined in an ontology.

DST Models
Baselines (Mrksic et al., 2017)
NBT-CNN (Mrksic et al., 2017)
StateNet PSI (Ren et al., 2018)
GLAD (Nouri and Hosseini-Asl, 2018)
HyST (ensemble) (Goel et al., 2019)
DSTRead (ensemble) (Gao et al., 2019)
TRADE (Wu et al., 2019)
COMER

Joint Acc.
WoZ 2.0

Joint Acc.
MultiWoZ

ITC

70.8%
84.2%
88.9%
88.5%
88.6%

25.83%
35.58%
44.22%
42.12%
48.62%
48.79%

O(mn)
O(mn)
O(n)
O(mn)
O(n)
O(n)
O(n)
O(1)

Table 3: The joint goal accuracy of the DST models on the WoZ2.0 test set and the MultiWoZ test set. We also
include the Inference Time Complexity (ITC) for each model as a metric for scalability. The baseline accuracy
for the WoZ2.0 dataset is the Delexicalisation-Based (DB) Model (Mrksic et al., 2017), while the baseline for theMultiWoZ dataset is taken from the official website of MultiWoZ (Budzianowski et al., 2018).

Model

Joint Acc.

Model

JD Acc.

JDS Acc.

JG Acc.

COMER- Hierachical-Attn- MLP

88.64%
86.69%
83.24%

COMER- moveDrop- postprocess- ShareParam- Order- Nested- BlockGrad

95.52%
95.34%
95.53%
94.96%
95.55%-

55.81%
55.08%
54.74%
54.40%
55.06%
49.58%
49.36%

48.79%
47.19%
45.72%
44.38%
42.84%
40.57%
39.15%

Table 4: The ablation study on the WoZ2.0 datasetwith the joint goal accuracy on the test set. For “Hierachical-Attn”, we remove the residual connections
between the attention modules in the CMR decoders
and all the attention memory access are based on the
output from the LSTM. For “- MLP”, we further replace the MLP with a single linear layer with the nonlinear activation.

Table 3 compares our model with the previous
state-of-the-art on both the WoZ2.0 test set and theMultiWoZ test set. For the WoZ2.0 dataset, we
maintain performance at the level of the state-ofthe-art, with a marginal drop of 0.3% comparedwith previous work. Considering the fact that
WoZ2.0 is a relatively small dataset, this small difference does not represent a significant big performance drop. On the muli-domain dataset, MultiWoZ, our model achieves a joint goal accuracy of
48.79%, which marginally outperforms the previous state-of-the-art.
4.4

Ablation Study

To prove the effectiveness of our structure of theConditional Memory Relation Decoder (CMRD),
we conduct ablation experiments on the WoZ2.0
dataset. The effectiveness of our hierarchical attention design is proved by an accuracy drop of
1.95% after removing residual connections and theTable 5:The ablation study on the MultiWoZ
dataset with the joint domain accuracy (JD Acc.), joint
domain-slot accuracy (JDS Acc.) and joint goal accuracy (JG Acc.) on the test set. For “- moveDrop”, wemove the dropout layer to be in front of the final linear layer before the Softmax. For “- postprocess”, we
further fix the decoder embedding layer and remove
the post-processing during model evaluation. For “ShareParam”, we further remove the parameter sharing mechanism on the encoders and the attention modules. For “- Order”, we further arrange the order of theslots according to its global frequencies in the training
set instead of the local frequencies given the domain
it belongs to. For “- Nested”, we do not generate domain sequences but generate combined slot sequences
which combines the domain and the slot together. For“- BlockGrad”, we further remove the gradient blocking mechanism in the CMR decoder.

hierarchical stack of our attention modules. The
accuracy drop of removing MLP is partly due tothe reduction of the number of model parameters,
but it also proves that stacking more layers in an
MLP can improve the relational reasoning performance given a concatenation of multiple representations from different sources.

We also conduct the ablation study on the MultiWoZ dataset for a more precise analysis on thehierarchical generation process. For joint domain
accuracy, we calculate the probability that all domains generated in each turn are exactly matchedwith the labels provided. The joint domain-slot
accuracy further calculate the probability that all
domains and slots generated are correct, while thejoint goal accuracy requires all the domains, slots
and values generated are exactly matched withthe labels. From Table 5, We can further calculate that given the correct slot prediction, COMER
has 87.42% chance to make the correct value prediction. While COMER has done great job on
domain prediction (95.52%) and value prediction(87.42%), the accuracy of the slot prediction given
the correct domain is only 58.43%. We suspectthat this is because we only use the previous belief state to represent the dialogue history, and theinter-turn reasoning ability on the slot prediction
suffers from the limited context and the accuracy
is harmed due to the multi-turn mapping problem(Wu et al., 2019). We can also see that the JDS
Acc. has an absolute boost of 5.48% when we
switch from the combined slot representation to
the nested tuple representation. This is because
the subordinate relationship between the domains
and the slots can be captured by the hierarchical sequence generation, while this relationship ismissed when generating the domain and slot together via the combined slot representation.
4.5

Qualitative Analysis

Figure 5 shows an example of the belief state prediction result in one turn of a dialogue on theMultiWoZ test set. The visualization includes the
CMRD attention scores over the belief states, system transcript and user utterance during the decoding stage of the slot sequence.
From the system attention (top right), since itis the first attention module and no previous context information is given, it can only find the information indicating the slot “departure” from thesystem utterance under the domain condition, andattend to the evidence “leaving” correctly during
the generation step of “departure”. From the user
attention, we can see that it captures the most helpful keywords that are necessary for correct prediction, such as “after” for “day” and “leave at”,
“to” for “destination”. Moreover, during the generation step of “departure”, the user attention suc-cessfully discerns that, based on the context, theword “leave” is not the evidence that need to beaccumulated and choose to attend nothing in thisstep. For the belief attention, we can see that the
belief attention module correctly attends to a previous slot for each generation step of a slot that has
been presented in the previous state. For the generation step of the new slot “destination”, since theprevious state does not have the “destination” slot,
the belief attention module only attends to the ‘-’mark after the ‘train’ domain to indicate that thegenerated word should belong to this domain.

5

Related Work

Semi-scalable Belief Tracker Rastogi et al.
(2017) proposed an approach that can generate
fixed-length candidate sets for each of the slots
from the dialogue history. Although they only
need to perform inference for a fixed number ofvalues, they still need to iterate over all slots defined in the ontology to make a prediction for agiven dialogue turn. In addition, their methodneeds an external language understanding module
to extract the exact entities from a dialogue to formcandidates, which will not work if the label value
is an abstraction and does not have the exact matchwith the words in the dialogue.
StateNet (Ren et al., 2018) achieves state-ofthe-art performance with the property that its parameters are independent of the number of slot values in the candidate set, and it also supports online
training or inference with dynamically changing
slots and values. Given a slot that needs tracking,it only needs to perform inference once to makethe prediction for a turn, but this also means thatits inference time complexity is proportional to thenumber of slots.
TRADE (Wu et al., 2019) achieves state-of-theart performance on the MultiWoZ dataset by applying the copy mechanism for the value sequence
generation. Since TRADE takes n combinationsof the domains and slots as the input, the inference time complexity of TRADE is O(n). The
performance improvement achieved by TRADE
is mainly due to the fact that it incorporates the
copy mechanism that can boost the accuracy on
the name slot, which mainly needs the ability incopying names from the dialogue history. However, TRADE does not report its performance on
the WoZ2.0 dataset which does not have the nameslot.

Figure 5: An example belief prediction of our model on the MultiWoZ test set. The attention scores for belief
states, system transcript and user utterance in CMRD is visualized on the right. Each row corresponds to theattention score of the generation step of a particular slot under the ‘train’ domain.

DSTRead (Gao et al., 2019) formulate the dialogue state tracking task as a reading comprehension problem by asking slot specified questions to
the BERT model and find the answer span in the
dialogue history for each of the pre-defined combined slot. Thus its inference time complexity is
still O(n). This method suffers from the fact thatits generation vocabulary is limited to the words
occurred in the dialogue history, and it has to doa manual combination strategy with another jointstate tracking model on the development set toachieve better performance.
Contextualized Word Embedding (CWE) was
first proposed by Peters et al. (2018). Based on theintuition that the meaning of a word is highly correlated with its context, CWE takes the complete
context (sentences, passages, etc.) as the input,
and outputs the corresponding word vectors thatare unique under the given context. Recently, withthe success of language models (e.g. Devlin et al.
(2018)) that are trained on large scale data, contextualizeds word embedding have been further
improved and can achieve the same performancecompared to (less flexible) finely-tuned pipelines.
Sequence Generation Models. Recently, sequence generation models have been successfully
applied in the realm of multi-label classification (MLC) (Yang et al., 2018). Different fromtraditional binary relevance methods, they proposed a sequence generation model for MLC tasks
which takes into consideration the correlations between labels. Specifically, the model follows theencoder-decoder structure with an attention mech-anism (Cho et al., 2014), where the decoder generates a sequence of labels. Similar to language
modeling tasks, the decoder output at each time
step will be conditioned on the previous predictions during generation. Therefore the correlation
between generated labels is captured by the decoder.

6

Conclusion

In this work, we proposed the Conditional Memory Relation Network (COMER), the first dialogue state tracking model that has a constant inference time complexity with respect to the number of domains, slots and values pre-defined in an
ontology. Besides its scalability, the joint goal accuracy of our model also achieve the similar performance compared with the state-of-the-arts on
both the MultiWoZ dataset and the WoZ dataset.
Due to the flexibility of our hierarchical encoderdecoder framework and the CMR decoder, abundant future research direction remains as applying the transformer structure, incorporating open
vocabulary and copy mechanism for explicit unseen words generation, and inventing better dialogue history access mechanism to accommodate
efficient inter-turn reasoning.
Acknowledgements. This work is partly supported by NSF #1750063. We thank all the reviewers for their constructive suggestions. We also
want to thank Zhuowen Tu and Shengnan Zhang
for the early discussions of the project.

References
Pawel Budzianowski, Tsung-Hsien Wen, Bo-Hsiang
Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gasic. 2018. Multiwoz - a largescale multi-domain wizard-of-oz dataset for taskoriented dialogue modelling. In EMNLP.
Kyunghyun Cho, Bart van Merrienboer, aglar Glehre,
Dzmitry Bahdanau, Fethi Bougares, Holger
Schwenk, and Yoshua Bengio. 2014. Learningphrase representations using rnn encoder-decoder
for statistical machine translation. In EMNLP.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, andKristina Toutanova. 2018. Bert: Pre-training of deep
bidirectional transformers for language understanding. In NAACL-HLT.
Shuyang Gao, Abhishek Sethi, Sanchit Agarwal, Tagyoung Chung, and Dilek Zeynep Hakkani. 2019. Dialog state tracking: A neural reading comprehension
approach. ArXiv, abs/1908.01946.
Rahul Goel, Shachi Paul, and Dilek Zeynep Hakkani.
2019.
Hyst: A hybrid approach for flexible
and accurate dialogue state tracking.
ArXiv,
abs/1907.00883.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian
Sun. 2015. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. 2015 IEEE International Conference on
Computer Vision (ICCV), pages 1026–1034.
Matthew Henderson, Blaise Thomson, and Jason D.
Williams. 2014. The second dialog state tracking
challenge. In SIGDIAL Conference.
Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long
short-term memory. Neural Computation, 9:1735–
1780.
Diederik P. Kingma and Jimmy Ba. 2015. Adam: A
method for stochastic optimization. CoRR.
Fei Liu and Julien Perez. 2017. Dialog state tracking,a machine reading approach using memory network.
In EACL.
Nikola Mrksic, Diarmuid Ó Séaghdha, Tsung-Hsien
Wen, Blaise Thomson, and Steve J. Young. 2017.
Neural belief tracker: Data-driven dialogue state
tracking. In ACL.
Elnaz Nouri and Ehsan Hosseini-Asl. 2018. Toward
scalable neural dialogue state tracking model. arXiv
preprint arXiv:1812.00899.
Matthew E. Peters, Mark Neumann, Mohit Iyyer,
Matt Gardner, Christopher Clark, Kenton Lee, andLuke S. Zettlemoyer. 2018. Deep contextualized
word representations. In NAACL-HLT.
Osman Ramadan, Pawel Budzianowski, and Milica
Gasic. 2018. Large-scale multi-domain belief tracking with knowledge sharing. In ACL.

Abhinav Rastogi, Dilek Hakkani-Tur, and Larry Heck.
2017. Scalable multi-domain dialogue state tracking. arXiv preprint arXiv:1712.10224.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar.
2018. On the convergence of adam and beyond. In
ICLR.
Liliang Ren, Kaige Xie, Lu Chen, and Kai Yu.
2018. Towards universal dialogue state tracking. In
EMNLP.
Adam Santoro, David Raposo, David G. T. Barrett,Mateusz Malinowski, Razvan Pascanu, Peter W.
Battaglia, and Timothy P. Lillicrap. 2017. A simple neural network module for relational reasoning.
In NIPS.
Rico Sennrich, Barry Haddow, and Alexandra Birch.
2016. Neural machine translation of rare words withsubword units. CoRR, abs/1508.07909.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston,and Rob Fergus. 2015. End-to-end memory networks. In NIPS.
Tsung-Hsien Wen, Milica Gasic, Nikola Mrksic,
Lina Maria Rojas-Barahona, Pei hao Su, Stefan
Ultes, David Vandyke, and Steve J. Young. 2017.
A network-based end-to-end trainable task-oriented
dialogue system. In EACL.
Chien-Sheng Wu, Andrea Madotto, Ehsan HosseiniAsl, Caiming Xiong, Richard Socher, and Pascale
Fung. 2019. Transferable multi-domain state generator for task-oriented dialogue systems. In ACL.
Puyang Xu and Qi Hu. 2018. An end-to-end approachfor handling unknown slot values in dialogue state
tracking. In ACL.
Pengcheng Yang, Xu Sun, Wei Li, Shuming Ma, Wei
Wu, and Houfeng Wang. 2018. Sgm: Sequence generation model for multi-label classification. In COLING.
Steve Young, Milica Gašić, Blaise Thomson, and Jason D Williams. 2013. Pomdp-based statistical spoken dialog systems: A review. Proceedings of theIEEE, 101(5):1160–1179.
Yulun Zhang, Yapeng Tian, Yu Kong, Bineng Zhong,and Yun Fu. 2018. Residual dense network for image super-resolution. 2018 IEEE/CVF Conference
on Computer Vision and Pattern Recognition, pages
2472–2481.
Victor Zhong, Caiming Xiong, and Richard Socher.
2018. Global-locally self-attentive dialogue state
tracker. CoRR, abs/1805.09655.