Insertion-based Tree Decoding

Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 3201–3213 August 1–6, 2021. ©2021 Association for Computational Linguistics 3201 Insertion-based Tree Decoding Denis Lukovnikov Ruhr University Bochum, Bochum, Germany denis.lukovnikov@rub.de Asja Fischer Ruhr University Bochum, Bochum, Germany asja.fischer@rub.de Abstract Sequences are typically decoded in a left- to-right fashion, requiring as many decoding steps as there are tokens in the sequence. Recently, several works have proposed non- autoregressive decoders that are sub-linear, al- lowing to decode a sequence using fewer de- coding steps than the length of the sequence, and thus substantially speed up inference. In contrast, non-autoregressive decoding of trees is less well-analysed, even though trees are used in important applications like seman- tic parsing and code generation. In this work, we present a novel general-purpose par- tially autoregressive tree decoder that uses tree- based insertion operations to generate trees in sub-linear time. We evaluate our approach on semantic parsing and compare it against strong baselines, including an insertion-based sequence decoder. The results demonstrate that the partially autoregressive tree decoder reaches competitive accuracies while clearly reducing the number of decoding steps. 1 Introduction Sequence generation is usually based on a left-to- right autoregressive decoder that decomposes the probability of the entire sequence y conditioned on x (x can be empty) as the product p(y|x) = �N i=0 p(yi|y<i, x). At each decoding step, the de- coder model predicts the next token yi based on the previously generated outputs y<i and the in- put x. This approach to decoding sequences is linear in sequence length: the number of decoding steps necessary to produce the sequence is equal to the length of the sequence. However, recently, several works have proposed non-autoregressive decoders that are sub-linear. This allows to decode a sequence using fewer decoding steps than the length of the sequence and can thus greatly speed up inference, especially for longer sequences (Stern et al., 2019; Ma et al., 2019; Ghazvininejad et al., 2019; Gu et al., 2017; Kasai et al., 2020). In par- ticular, the Insertion Transformer of Stern et al. (2019) uses insertion operations to iteratively ex- pand the sequence, achieving a best-case number of O(log2 N) decoding steps. In this work, we extend insertion-based decoding of sequences to insertion-based decoding of trees. Insertion-based sequence decoder can also be ap- plied to decoding trees (Zhu et al., 2020). However, this requires linearizing trees into sequences, and requires the explicit decoding of subtree termina- tion tokens (e.g. closing parentheses “)”). This results in larger structures, which for the Inser- tion Transformer increases the minimum necessary number of decoding steps and increases the com- putational requirements per step. In contrast, the insertion-based tree decoder that we propose here does not need to explicitly decode structure tokens. Moreover, it can achieve a best-case complexity below O(log2 N)1 in terms of the number of de- coding steps and guarantees that all intermediate outputs are valid trees. To the best of our knowl- edge, no existing research focuses on insertion- based non-autoregressive decoding of …

Content truncated to 500 words