Lune

EMNLP Findings2025

Tree-Structured Non-Autoregressive Decoding for Sequence-to-Sequence Text Generation

Pengyu Ji, Yufei Liu, Xiang Hu, Kewei Tu

Abstract

Autoregressive Transformer (AT) dominates sequence-to-sequence generation tasks but suffers from high inference latency due to sequential token generation. Non-Autoregressive Transformer (NAT) improves inference efficiency by parallelizing token prediction, yet degrades generation quality. To address these limitations, we propose Tree-structured Non-Autoregressive Decoding (TNAD), a novel paradigm that bridges autoregressive and nonautoregressive decoding. TNAD generates a sentence through a top-down, layer-wise expansion of its constituency parse tree, enabling parallel generation within each layer while preserving contextual dependencies across layers. Experimental results on machine translation and paraphrase generation demonstrate that TNAD outperforms AT in efficiency and NAT in generation quality, thus offering a new alternative to AT and NAT in the trade-off between efficiency and quality. Our code is publicly available at https://github.com/jipy0222/TNAD.

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Directed Acyclic Transformer for Non-Autoregressive Machine Translation cites Non-autoregressive Machine Translation with Disentangled Context Transformer
  • Non-autoregressive Machine Translation with Probabilistic Context-free Grammar cites Non-autoregressive Machine Translation with Disentangled Context Transformer
  • Non-autoregressive Machine Translation with Probabilistic Context-free Grammar cites Directed Acyclic Transformer for Non-Autoregressive Machine Translation
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on10

  1. Structured Denoising Diffusion Models in Discrete State-SpacesJacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow et al.NeurIPS 2021 · 2,256 citations
  2. Train Short, Test Long: Attention with Linear Biases Enables Input Length ExtrapolationOfir Press, Noah A. Smith, Mike LewisICLR 2022 · 1,168 citations
  3. Non-autoregressive Machine Translation with Disentangled Context TransformerJungo Kasai, James Cross, Marjan Ghazvininejad, Jiatao GuICML 2020 · 113 citations
  4. Directed Acyclic Transformer for Non-Autoregressive Machine TranslationFei Huang, Hao Zhou, Yang Liu, Hang Li et al.ICML 2022 · 82 citations
  5. Non-autoregressive Machine Translation with Probabilistic Context-free GrammarShangtong Gui, Chenze Shao, Zhengrui Ma, Xishan Zhang et al.NeurIPS 2023 · 16 citations

Related papers

  1. NAT4AT: Using Non-Autoregressive Translation Makes Autoregressive Translation Faster and BetterHuanran Zheng, Wei Zhu, Xiaoling WangWWW 2024 · 13 citations
  2. Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine TranslationJungo Kasai, Nikolaos Pappas, Hao Peng, James Cross et al.ICLR 2021 · 154 citations
  3. Treepiece: Faster Semantic Parsing via Tree TokenizationSid Wang, Akshat Shrivastava, Aleksandr LivshitsEMNLP Findings 2023 · 1 citation
  4. Cascaded Text Generation with Markov TransformersYuntian Deng, Alexander M. RushNeurIPS 2020 · 16 citations
  5. Non-autoregressive Streaming Transformer for Simultaneous TranslationZhengrui Ma, Shaolei Zhang, Shoutao Guo, Chenze Shao et al.EMNLP 2023 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines