Abstract: Conditional masked language model (CMLM) training has proven successful for non-autoregressive and semi-autoregressive sequence generation tasks, such as machine translation. Given a trained CMLM, however, it is not clear what the best inference strategy is. We formulate masked inference as a factorization of conditional probabilities of partial sequences, show that this does not harm performance, and investigate a number of simple heuristics motivated by this perspective. We identify a thresholding strategy that has advantages over the standard "mask-predict" algorithm, and provide analyses of its behavior on machine translation tasks.
The Challenge of Non-Autoregressive Translation
Traditional Neural Machine Translation (NMT) models are autoregressive, generating text one token at a time from left to right. While highly accurate, this sequential nature creates a significant bottleneck in generation speed. Non-Autoregressive Translation (NAT) models attempt to predict all tokens in parallel to overcome this. However, pure NAT often suffers from "multimodality" issues, where the model predicts conflicting valid synonyms for the same slot, resulting in garbled or incoherent sentences.
Conditional Masked Language Models (CMLMs) offer a middle ground. They start with a fully masked sequence and iteratively "unmask" tokens. The standard approach, known as "mask-predict," typically uses a fixed number of iterations. This approach is often sub-optimal because it treats every sentence the same way—a simple five-word phrase receives the same computational budget as a complex fifty-word sentence.
Adaptive Inference via Thresholding
This paper proposes moving away from rigid, fixed-iteration schedules toward confidence-based thresholding. The authors introduce a fully probabilistic view of masked inference and propose a new strategy called comb-thresh.
Key components of the proposed methodology include:
- The
update-masked-subConstraint: Unlike the original mask-predict, once a token is unmasked in this framework, it stays unmasked. This allows the decoding process to be viewed as a valid probabilistic factorization of the target sequence. - The
comb-threshHeuristic: Instead of unmasking a fixed percentage of tokens, the model unmasks the largest set of tokens such that their joint probability (the product of their individual independent probabilities) remains above a threshold $\tau$.
This approach is inherently adaptive: if the model is confident, it unmasks many tokens at once to speed up; if it is uncertain, it unmasks only the most certain tokens, slowing down to ensure quality.
Performance and Quality Trade-offs
The researchers evaluated these strategies on standard benchmarks, including WMT14 English-German (En-De) and WMT17 Chinese-English (Zh-En), using knowledge distillation to simplify the learning signal.
As illustrated in Figure 2, the comb-thresh strategy consistently outperforms the standard mask-predict across various speed-quality settings. The model achieves a theoretical 4x speedup over a standard autoregressive Transformer while maintaining translation quality within 0.3 BLEU points.
Analysis of Adaptivity
A core insight of the paper is that adaptivity is essential for efficient inference. Fixed-iteration strategies are inherently inefficient because they do not account for sentence complexity.
Figure 3 demonstrates that thresholding strategies naturally spend more iterations on long, complex sentences and fewer on short ones. This linear scaling with sentence length is intuitively how an efficient algorithm should operate, resolving linguistic ambiguities (such as gender agreement in German) by waiting for sufficient context before committing to uncertain tokens.
Conclusion
By framing inference as a factorization of conditional probabilities, the authors provide a theoretical grounding for adaptive decoding in CMLMs. The comb-thresh strategy offers a superior balance of speed and quality, proving that flexible, confidence-based heuristics are key to unlocking the full potential of non-autoregressive machine translation.
Summary updated