Improving Top-K Decoding for Non-Autoregressive Semantic Parsing via Intent Conditioning

NAR sequence models have been an active research area across different fields of natural language processing for their fast inference speeds. While various designs of NAR decoders exist, recent works in machine translation use models with iterative refinements (Lee et al., 2018; Ghazvininejad et al., 2019, 2020), insertion-based (Stern et al., 2019), and latent alignment methods (Libovický and Helcl, 2018; Chan et al., 2020; Saharia et al., 2020).

The task of semantic parsing (SP) is similar to the machine translation task as they both translate input sentences from one representation to another. For this reason, recent studies in SP have adopted modeling techniques from machine translation. Zhu et al. (2020) leveraged the insertion-based seq2seq models for NAR semantic parsing and reduced the decoding time from $O(n)$ to $O(log(n))$ while matching the performance of AR models. Babu et al. (2021); Shrivastava et al. (2021) applied an iterative refinement method Mask-Predict to semantic parsing and brought the time complexity further down to $O(1)$ while performing comparably to the baseline AR models. As opposed to the original Mask-Predict model that performs multiple iterations of re-masking and prediction (Ghazvininejad et al., 2019), they only perform a single iteration of the masking and output prediction as they claim that task-oriented SP does not benefit much from iterative refinements (Babu et al., 2021; Shrivastava et al., 2021). In addition to the recent sequence-to-sequence NAR semantic parsers, traditional intent and slot filling model (Mesnil et al., 2014) is another approach with non-autoregressive decoding.

Span Pointer Network (Shrivastava et al., 2021), which is one of the two recent works that leveraged the mask-predict algorithm, showed the competitive performance to the AR parsers while significantly reducing their latency. For this reason, we utilize Span Pointer Network as a basis of our work and accordingly refer to it as baseline NAR to distinguish the NAR semantic parser we propose. It should be noted that we replicated Span Pointer Network as it is not publicly available.

The baseline NAR is built with a pre-trained encoder, a frame length module, and a Transformer decoder. The encoder is a language model such as BERT (Devlin et al., 2019) or RoBERTa (Liu et al., 2019) that takes input queries $x$ and outputs their encoded representations $e$.

where $l$ indicates the length of the source (i.e., input query). The frame length module takes the encoded representations and predicts the length of the frame (i.e., target parse) $n$ followed by the generation of $n$ mask tokens.

The transformer decoder takes the $N$ mask tokens as inputs and produce $h$ for each token.

Lastly, the pointer-generator mapping layer is used to convert $h$ to the target frame $y$ as follows.

where $y_{k}$ is either a token from the target vocab that consists of parse symbols (e.g., intents & slots) or copy of a source token. The output tokens are generated in parallel as they are conditionally independent given the source and frame length.

AR decoders produce multiple candidate output parses per source by employing the beam search algorithm (Wiseman and Rush, 2016). During the beam search with width $k$, the k most probable candidates are kept at each decoding step and less probable candidates are sorted out. The decoding process finishes when a special “[END]” token is encountered. For a decoding length $n$, the score of an AR parse is computed as follows.

Since the AR decoders consider multiple candidate tokens $y_{j}$ at each decoding step, they can generate a large number of unique parses.

In comparison, the baseline NAR only produces a single output parse per frame length. The baseline NAR mimics the beam search by generating top-k frame lengths, which results in $k$ outputs. The output parse is scored using the joint probability of the frame length and output parse as follows.

where $S_{NAR,baseline}(y)$ denotes the score of the baseline NAR output. $p(y|n,x)$ is obtained using the conditional independence of the output tokens given the frame length $n$ and source $x$.

The proposed NAR utilizes a pre-trained language model to obtain encoded source representation $e$. Then, it performs the top-level intent prediction, which is formulated as a multiclass classification of the size of the dimensionality of intent vocab.

where $y_{1}$ refers to the top-level intent of the semantic parse or the first token of the parse. As the top-level intent prediction is decoupled, the intent module works with a smaller vocabulary size. Compared to the output vocabulary that combines a target and copy index vocabulary, the intent vocabulary is approximately 4 times smaller with a source length 32 on TOP dataset. We use a randomly initialized Transformer as the intent module.

We use the logits of the top-level intent, as opposed to the discrete intent class variable, as the inputs to all subsequent modules. This is because the dense logits convey information about the uncertainty of the intent prediction for each intent class and help the subsequent modules to condition on richer information. We found that this resulted in better performance than the model conditioned on the 1-dimensional discrete intent.

Subsequent to the top-level intent prediction, the frame length module takes the logits of the intent $y_{1}$ and produces the decoding length followed by the creation of mask tokens. After that, the initial mask tokens together with the frame length pass through a positional encoding layer to compute the encoded mask tokens, $\mathrm{[MASK]}_{2:n}$.

The rest of the frame is generated using parallel decoding followed by the source token mapping via the pointer-generator mapping layer.

Finally, the output parse is obtained by concatenating the top-level intent and rest of the frame.

The loss is a weighted sum of top-level intent classification loss $\mathcal{L}_{int}$, frame length classification loss $\mathcal{L}_{len}$, and output loss $\mathcal{L}_{out}$ as follows.

We jointly optimize the three loss terms and employ label smoothing (LS) (Szegedy et al., 2016) as a regularizer to penalize overconfident predictions by computing negative log-likelihood (NLL) between the smoothed one-hot labels and predictions. That is, $\mathcal{L}_{int}=\mathrm{NLL}(\mathrm{LS}(y_{1,label}),y_{1,pred})$, $\mathcal{L}_{len}=\mathrm{NLL}(\mathrm{LS}(n_{label}),n_{pred})$, and $\mathcal{L}_{out}=\mathrm{NLL}(\mathrm{LS}(y_{2:n,label}),y_{2:n,pred})$.

The proposed intent-conditioned NAR produces multiple output parses per source via the sequential conditioning on the top-level intent and length. Precisely, the model first computes top-$k1$ top-level intents. For each top-level intent, the length model outputs top-$k2$ frame lengths. As a result, $k1\cdot k2$ pairs of top-level intents and lengths are produced. Finally, the decoder generates a single parse per pair, yielding a total of $k1\cdot k2$ output parses.

The proposed NAR performs a single decoder pass regardless of the beam size, $k1\cdot k2$. This is possible as we cast the $k1\cdot k2$ pairs as the batch dimension. As a result, the time complexity of the beam search remains constant, to the extent of the memory capacity. The memory increases linearly to the beam size.

The intent conditioning provides explicit control of the top-level intents via the selection of top-$k1$ unique intents. It also builds dependencies of the frame length and output on the top-level intents. We find that these help the model to improve diversity and quality of top-k output parses. To further validate the hypothesis, we devise two experiments to (1) identify the potential (i.e., upper limit of the accuracy) of the proposed NAR beam search and (2) examine the diversity and quality of the output parses compared to the baseline NAR beam search.

During our initial attempts to inspect the proposed model, we discovered that the inference performance is unstable. This was due to a discrepancy in the computation of the top-level intent during the training and inference. Recall that the outputs of the top-level intent module are logits (see Equation 8). In the inference, we use the logits to sample the top-$k1$ top-level intents, which are sparse one-hot vectors, and convert them back to the logits. Conversely, in the training, we do not sample top-level intents and instead use the direct outputs (dense logits) from the top-level intent module. We first attempted to resolve the problem with a teacher-forcing of the top-level intents. While this stabilized the inference, the training became unstable due to the sparsity of the teacher logits.

We address this problem by leveraging a sampling strategy depicted in Figure 2. The idea is to uniformly sample logits from a pair of teacher and model logits as follows.

We name this strategy as hybrid teacher forcing to reflect that the model leverages both teacher and model top-level intent logits. This sampling technique may be seen as a non-autoregressive variant of the scheduled sampling (Bengio et al., 2015).

A scoring method is used to select the top-k parses from the $k1\cdot k2$ pairs. We tested three methods. The first method $S_{1}$ uses the joint log probability of the top-level intent and frame length as the score.

The second method $S_{2}$ uses the joint log probability of the output, length, and top-level intent.

The last scoring method $S_{3}$ combines the joint probability $p(y_{1:n},n|x)$ and a length penalty.

where $lp$ is the length penalty (Wu et al., 2016).

Depending on $k1$, $k2$, and scoring method, the top-k outputs may consist of parses with multiple distinct lengths and intents or parses with a single intent with multiple lengths.

We represent semantic parses using the decoupled tree representation (Aghajanyan et al., 2020a) that is an extension of the compositional tree representation (Gupta et al., 2018). An example is depicted in Figure 3. Likewise, another query “What is happening in Boston on New Year’s Eve” is semantically parsed into “[in:get_event [sl:location Boston ] [sl:date_time on New Year’s Eve ] ]”.

An example of the decoupled tree representation is Index form that replaces the copy tokens with the indices to the corresponding source tokens. In this sense, the above semantic parse is represented as “[in:get_event [sl:location 4 ] [sl:date_time 5 6 7 8 ] ]”. Together with the pointer network, this significantly reduces the size of output vocabulary (Rongali et al., 2020). Another representation is Span form introduced in (Shrivastava et al., 2021). As opposed to specifying all indices of spans of copy tokens, the span form uses the start and end indices of the spans. That is, “[in:get_event [sl:location 4 4 ] [sl:date_time 5 8 ] ]”. The benefits of the span form include shorter target lengths and fixed number of leaf nodes that helps decoupling the syntax from the semantics. In addition, the number of valid frame length classes are halved as the frame lengths of parses in the span form are always even.

To quantify the benefits of our NAR parsers over the baseline NAR, we utilize two conversational semantic parsing datasets. The first dataset is TOP (Task Oriented Parsing) (Gupta et al., 2018), a collection of human-generated queries in English and the corresponding semantic parses that are represented as hierarchical trees. Another public dataset we explore is TOPv2 (Chen et al., 2020), which is an extension of TOP with six more domains.

We mainly utilize exact match (EM) to evaluate quality of both greedy decoding and beam decoding output. EM is defined as the percentage of queries whose label parses are correctly predicted.

Inference time is the metric we use to quantify the latency benefit of our model. We measure the model inference time on 1 TPU (Jouppi et al., 2017) from the Google Cloud TPUv2 and 1 CPU of the Intel Cascade Lake CPU platform with 8GB RAM. We used batch size 1 and computed latency on 1000 examples from the val set of the TOP dataset. We report per-example average latencies of these runs.

In addition, diversity of the output parses is computed to quantify the capability of the proposed NAR approach at producing distinct top-k outputs. We mainly compute two metrics: (1) number of unique top-level intents in top-k output parses and (2) the distinct n-grams (Li et al., 2016), which are commonly used diversity metrics in natural language processing (Vijayakumar et al., 2018; Xu et al., 2018). Specifically, we compute percentage of distinct n-grams by counting unique n-grams in top-k outputs, dividing the counts by the total number of output tokens, and scaling it by 100.

Table 3 presents the greedy decoding results. At each decoding step of AR models, the most probable token is selected. This repeats until an END token is produced. In NAR greedy decoding, beam width of 1 is used for both frame length and top-level intent. No scoring method is used.

The results indicate that our model improves the performance of baseline NAR by 0.4-0.5 EM while matching the latency of the prior NAR approach. Compared to AR baselines, our model cuts the greedy decoding inference time (i.e., latency of the semantic parser including both encoder and decoder) by 4.2-4.4x on CPU and 2.2x on TPU.

We designed an experiment to investigate the potential benefits of the proposed beam search. We aimed to empirically quantify the upper bound of the beam search performance of the baseline NAR and our intent-conditioned NAR. In the experiment, we first trained the baseline and proposed NAR parsers, then fed the oracle (i.e., gold) frame length to the baseline NAR or the oracle top-level intent to the proposed NAR during the inference. To ensure validity of the results, we ran the experiments with different model configurations.

As shown in Table 4, the proposed NAR consistently scored higher oracle EM across various model configurations. It should be noted that the proposed NARs only use the gold top-level intent (i.e., the gold length is not used for the inference with the proposed NARs). Table 5 confirms these results and shows that our NAR performs more effective beam-coding and achieves higher exact match for the top-k output.

In table 5, we report the beam search results on TOP dataset as top-k EM for $k={1,2,3}$. If the label parse matches with any of the top-k output parses, it counts towards the top-k EM. We also report top-level intent match (IM) percents. The top-k parses are selected from the $k1\cdot k2$ beam search outputs using the scoring method 3 (Equation 15). We used the same $k1\cdot k2$ for the fair comparison. Specifically, we used $k2=25$ for the baseline NAR and $k1=25$, $k2=1$ for our NAR as there exist 25 distinct length classes and 25 distinct intent classes in TOP dataset. For the proposed NAR, we observed that a higher $k2$ has minor impact on top-k EMs, compared to a higher $k1$. We note that the hybrid teacher forcing (Equation 12) was used for the training and helped the models achieve consistent test set accuracy.

The results demonstrate a large gap between AR and the existing NAR models in top-k outputs. Notably, the top-3 EM from the existing NAR model is outperformed by the baseline AR by 3.5 points. Secondly, the proposed NAR outperforms baseline NAR in top-3 EM by 2.4 and top-3 IM by 2.8 points. Lastly, we show that the proposed NAR reduces the performance gap from the autoregressive models. The inference time of our NAR beam search is 6.7x times shorter on CPU and 2.5x times shorter on TPU. Our AR baselines manage parallel compute loads better than NAR models and thus result in smaller latency gaps on TPU.

Table 6 elaborates on the diversity of the output parses with the baseline and proposed NAR models. Specifically, we compute their average numbers of unique top-level intents and distinct n-gram (Li et al., 2016) percentages in top-3 output parses. We find that top-k parses of the proposed NAR outperforms the baseline NAR in all diversity metrics.

We observed that the baseline NAR beam search often duplicates the most probable parse with repeated tokens and/or invalid syntax. This suggests that the frame length conditioning alone is not effective at producing top-k outputs (see Table 1 and 2 for examples). Table 6 quantitatively confirms the observation with lower sentence-wise and corpus-wise distinct n-gram scores of the baseline NAR, compared to the proposed NAR.