ACL Findings2021
Insertion-based Tree Decoding
Abstract
Sequences are typically decoded in a leftto-right fashion, requiring as many decoding steps as there are tokens in the sequence. Recently, several works have proposed nonautoregressive decoders that are sub-linear, allowing to decode a sequence using fewer decoding 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 semantic parsing and code generation. In this work, we present a novel general-purpose partially autoregressive tree decoder that uses treebased 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
- Non-autoregressive Machine Translation with Disentangled Context TransformerJungo Kasai, James Cross, Marjan Ghazvininejad, Jiatao GuICML 2020 · 113 citations
- AutoQA: From Databases To QA Semantic Parsers With Only Synthetic Training DataSilei Xu, Sina J. Semnani, Giovanni Campagna, Monica S. LamEMNLP 2020 · 33 citations
Related papers
- Treepiece: Faster Semantic Parsing via Tree TokenizationSid Wang, Akshat Shrivastava, Aleksandr LivshitsEMNLP Findings 2023 · 1 citation
- Tree-Structured Non-Autoregressive Decoding for Sequence-to-Sequence Text GenerationPengyu Ji, Yufei Liu, Xiang Hu, Kewei TuEMNLP Findings 2025
- Graph-Based Decoding for Task Oriented Semantic ParsingJeremy R. Cole, Nanjiang Jiang, Panupong Pasupat, Luheng He et al.EMNLP Findings 2021 · 1 citation
- Graph-to-Tree Neural Networks for Learning Structured Input-Output Translation with Applications to Semantic Parsing and Math Word ProblemShucheng Li, Lingfei Wu, Shiwei Feng, Fangli Xu et al.EMNLP Findings 2020 · 71 citations
- Compositional Generalization without Trees using Multiset Tagging and Latent PermutationsMatthias Lindemann, Alexander Koller, Ivan TitovACL 2023
