# Viterbi Decoding of Directed Acyclic Transformer for Non-Autoregressive Machine Translation

arXiv: https://arxiv.org/abs/2210.05193 · HTML: https://mlsanity.com/paper/2210.05193/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 46 references that are in the map.
- First posted on arXiv 11 Oct 2022.

## Builds on (most cited first, 30 of 40)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [A Call for Clarity in Reporting BLEU Scores](https://mlsanity.com/paper/1804.08771/) (2018)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Sequence-Level Knowledge Distillation](https://mlsanity.com/paper/1606.07947/) (2016)
- [Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1711.02281/) (2017)
- [Levenshtein Transformer](https://mlsanity.com/paper/1905.11006/) (2019)
- [Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement](https://mlsanity.com/paper/1802.06901/) (2018)
- [Understanding Knowledge Distillation in Non-autoregressive Machine Translation](https://mlsanity.com/paper/1911.02727/) (2019)
- [On NMT Search Errors and Model Errors: Cat Got Your Tongue?](https://mlsanity.com/paper/1908.10090/) (2019)
- [Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine Translation](https://mlsanity.com/paper/2006.10369/) (2020)
- [Fast Decoding in Sequence Models using Discrete Latent Variables](https://mlsanity.com/paper/1803.03382/) (2018)
- [Glancing Transformer for Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/2008.07905/) (2020)
- [Fully Non-autoregressive Neural Machine Translation: Tricks of the Trade](https://mlsanity.com/paper/2012.15833/) (2020)
- [Non-Autoregressive Machine Translation with Latent Alignments](https://mlsanity.com/paper/2004.07437/) (2020)
- [FlowSeq: Non-Autoregressive Conditional Sequence Generation with Generative Flow](https://mlsanity.com/paper/1909.02480/) (2019)
- [End-to-End Non-Autoregressive Neural Machine Translation with Connectionist Temporal Classification](https://mlsanity.com/paper/1811.04719/) (2018)
- [Aligned Cross Entropy for Non-Autoregressive Machine Translation](https://mlsanity.com/paper/2004.01655/) (2020)
- [Fast Structured Decoding for Sequence Models](https://mlsanity.com/paper/1910.11555/) (2019)
- [Latent-Variable Non-Autoregressive Neural Machine Translation with Deterministic Inference Using a Delta Posterior](https://mlsanity.com/paper/1908.07181/) (2019)
- [Order-Agnostic Cross Entropy for Non-Autoregressive Machine Translation](https://mlsanity.com/paper/2106.05093/) (2021)
- [Semi-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1808.08583/) (2018)
- [Directed Acyclic Transformer for Non-Autoregressive Machine Translation](https://mlsanity.com/paper/2205.07459/) (2022)
- [Minimizing the Bag-of-Ngrams Difference for Non-Autoregressive Neural Machine Translation](https://mlsanity.com/paper/1911.09320/) (2019)
- [Guiding Non-Autoregressive Neural Machine Translation Decoding with Reordering Information](https://mlsanity.com/paper/1911.02215/) (2019)
- [Non-Autoregressive Translation by Learning Target Categorical Codes](https://mlsanity.com/paper/2103.11405/) (2021)
- [AligNART: Non-autoregressive Neural Machine Translation by Jointly Learning to Estimate Alignment and Translate](https://mlsanity.com/paper/2109.06481/) (2021)

## Built on by (most cited first, 13 of 13)

- [A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models](https://mlsanity.com/paper/2508.08712/) (2025)
- [Non-autoregressive Streaming Transformer for Simultaneous Translation](https://mlsanity.com/paper/2310.14883/) (2023)
- [Fuzzy Alignments in Directed Acyclic Graph for Non-Autoregressive Machine Translation](https://mlsanity.com/paper/2303.06662/) (2023)
- [DASpeech: Directed Acyclic Transformer for Fast and High-quality Speech-to-Speech Translation](https://mlsanity.com/paper/2310.07403/) (2023)
- [Non-autoregressive Text Editing with Copy-aware Latent Alignments](https://mlsanity.com/paper/2310.07821/) (2023)
- [Non-autoregressive Machine Translation with Probabilistic Context-free Grammar](https://mlsanity.com/paper/2311.07941/) (2023)
- [Rephrasing the Reference for Non-Autoregressive Machine Translation](https://mlsanity.com/paper/2211.16863/) (2022)
- [Diffusion Glancing Transformer for Parallel Sequence to Sequence Learning](https://mlsanity.com/paper/2212.10240/) (2022)
- [ExLM: Rethinking the Impact of [MASK] Tokens in Masked Language Models](https://mlsanity.com/paper/2501.13397/) (2025)
- [Control-DAG: Constrained Decoding for Non-Autoregressive Directed Acyclic T5 using Weighted Finite State Automata](https://mlsanity.com/paper/2404.06854/) (2024)
- [NumColor: Precise Numeric Color Control in Text-to-Image Generation](https://mlsanity.com/paper/2603.13547/) (2026)
- [RTGen: Real-Time Generative Detection Transformer](https://mlsanity.com/paper/2502.20622/) (2025)
- [DA-DLM: Explicitly Modeling Token Dependencies in Diffusion Language Models](https://mlsanity.com/paper/2609.15070/) (2026)

## Abstract (arXiv)

Non-autoregressive models achieve significant decoding speedup in neural machine translation but lack the ability to capture sequential dependency. Directed Acyclic Transformer (DA-Transformer) was recently proposed to model sequential dependency with a directed acyclic graph. Consequently, it has to apply a sequential decision process at inference time, which harms the global translation accuracy. In this paper, we present a Viterbi decoding framework for DA-Transformer, which guarantees to find the joint optimal solution for the translation and decoding path under any length constraint. Experimental results demonstrate that our approach consistently improves the performance of DA-Transformer while maintaining a similar decoding speedup.