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

Pengyu Ji, Yufei Liu, Xiang Hu, Kewei TuEMNLP 2025

TL;DR

This paper introduces Tree-structured Non-Autoregressive Decoding (TNAD), a novel approach to sequence generation that balances the speed of non-autoregressive models with the quality of autoregressive ones. By leveraging the hierarchical structure of constituency parse trees, TNAD generates sentences in a layer-wise, parallel fashion, significantly reducing inference latency while maintaining grammatical coherence.

What Problem Does This Paper Address?

Traditional autoregressive (AR) models, like the Transformer, excel at generating high-quality text but suffer from slow inference due to their sequential, token-by-token generation process. Non-autoregressive (NAR) models, on the other hand, generate all tokens in parallel, offering substantial speedups. However, this parallelization often leads to a "multimodality problem," where generated sentences lack grammatical coherence and quality degrades. The challenge, therefore, is to bridge this gap, achieving both efficiency and high generation quality.

Methods

TNAD tackles this by adopting a top-down, layer-wise generation process guided by the structure of a constituency parse tree. Instead of generating tokens sequentially or all at once, TNAD expands the parse tree layer by layer. Each layer's generation involves two parallel steps:

  1. Branching Prediction: For each non-terminal node in the previous layer, TNAD predicts how many child nodes it will have (its branching factor).
  2. Node Generation: Based on the predicted branching factors, TNAD generates the labels for these child nodes (either non-terminals or tokens) in parallel.

This process continues until the entire tree is expanded, with the leaf nodes forming the final sentence. The model uses a shared decoder for both branching prediction and node generation, built upon the BART architecture. A key innovation is the "layer-wise causal attention mask," which allows nodes within the same layer to attend to each other, preserving contextual dependencies across layers while still enabling parallel processing within a layer.

Datasets

The paper evaluates TNAD on two main types of tasks:

  • Machine Translation: IWSLT14 German-English (De-En), IWSLT14 English-German (En-De), and WMT16 Romanian-English (Ro-En).
  • Paraphrase Generation: ParaNMT-Small.

The datasets were preprocessed using BPE for tokenization, and silver constituency parse trees were obtained using the Berkeley Parser.

Key Insights and Ideas

  • Syntax as a Scaffold for Parallelism: TNAD demonstrates that leveraging syntactic structure (specifically, constituency parse trees) can provide a natural hierarchy for parallel generation, mitigating the quality degradation often seen in purely non-autoregressive models.
  • Layer-wise Parallelism: By expanding the tree layer by layer, TNAD achieves parallel generation within each layer while maintaining dependencies across layers, offering a more structured approach than flat NAR models.
  • Balancing Act: The results suggest that TNAD successfully strikes a balance between the speed of NAR and the quality of AR models, offering a compelling alternative for sequence generation tasks.
  • Importance of Syntactic Structure: Ablation studies show that the performance gains of TNAD over vanilla NAR models are significantly attributed to the incorporation of syntactic structures and non-terminal labels, rather than just computational cost reduction.

Key Results

  • Machine Translation: TNAD outperforms vanilla-NAT and even a strong NAR baseline (DAT) in generation quality across all tested datasets. It also consistently surpasses the autoregressive (AT) baseline in generation efficiency. For instance, on IWSLT14 En-De, TNAD achieves a speedup of 23.33x over AT while maintaining a competitive BLEU score.
  • Paraphrase Generation: TNAD again surpasses vanilla-NAT and DAT in BLEU and ROUGE scores, while providing a speedup of 1.2x over AT.
  • Efficiency: TNAD's inference speedup is directly related to the "flatness" of the parse trees; flatter trees lead to more parallelization and higher speedups.

Limitations and Future Work

  • Dependency on Parsers: TNAD's reliance on constituency parse trees for training means its effectiveness might be limited in languages with scarce high-quality parsers.
  • Shared Decoder: The paper notes that using a shared decoder for branching prediction and node generation might not be optimal, as branching prediction is arguably an easier task. Future work could explore layer skipping for branching prediction to further improve efficiency.
  • Broader Applicability: While tested on seq2seq tasks, the authors suggest TNAD could be adapted for other architectures and tasks, such as decoder-only Transformers for language modeling.

Summary updated

BibTeX
@inproceedings{ji2025tree,
  author = {Pengyu Ji and Yufei Liu and Xiang Hu and Kewei Tu},
  title = {{Tree-Structured Non-Autoregressive Decoding for Sequence-to-Sequence Text Generation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure