Tree-Structured Non-Autoregressive Decoding for Sequence-to-Sequence Text Generation (2025)

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 non-autoregressive 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 .

## introduction autoregressive transformer (at) has shown strong performance in both language modeling @xcite and sequence-tosequence (seq2seq) tasks @xcite thanks to its autoregressive decoding paradigm. however, its reliance on sequential token generation introduces significant inference latency bottlenecks. to tackle the inefficiency problem, non-autoregressive transformer (nat) @xcite has been proposed as a counterpart that generates all tokens simultaneously. though achieving substantial inference speedup, the non-autoregressive decoding paradigm neglects the contextual dependencies among generated tokens, resulting in the multimodality problem (i.e., mixing parts from different valid output sequences, thus lacking grammatical coherence) @xcite and suffering from notable degradation in generation quality. a balanced generation paradigm that bridges autoregressive and non-autoregressive decoding and reconciles the trade-offs in generation quality and efficiency remains underexplored. in this paper, we propose tree-structured non-autoregressive decoding (tnad) as a new text generation paradigm, which generates a sentence by top-down layer-wise expansion of its constituency parse tree, with all elements within a layer generated in parallel, as illustrated in fig. 1 . it theoretically relieves the inference latency burden of at by reducing inference steps from o(n) (n for sentence length) to o(log n) (log n for average tree height). moreover, this paradigm alleviates the multi-modality problem encountered by nat because preceding tree layers can be observed for later generations, creating conditional dependencies absent in nat. the experimental results on machine translation and paraphrase generation show that our proposed paradigm surpasses nat in generation quality and at in generation efficiency. in contrast to conventional paradigms that prioritize either quality or efficiency, tnad strikes a new balance between the two and offers a novel alternative to at and nat. ## method in this section, we first introduce the top-down layer-wise generation process and then how to implement the process with the transformer model. ## experiment following @xcite , we perform experiments on two seq2seq tasks: machine translation and paraphrase generation. we compare our model, tnad, primarily with at and vanilla-nat. note that there exist several approaches to improving the performance of nat, including training-based @xcite and model-based @xcite methods, but these approaches are orthogonal to and can be combined with tnad. a further discussion is provided in section 4. therefore, here we only include the performance of da-transformer (dat) @xcite , a representative improved nat model, for reference. ## conclusion we propose tnad, a new text generation paradigm that generates a sentence by iteratively expanding layers of its constituency parse tree from the top down, with all nodes within a layer predicted in parallel by performing branching prediction and node generation. experimental results on seq2seq tasks show that tnad outperforms nat in generation quality and at in generation efficiency, which demonstrates tnad as a balanced option between at and nat.