Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation

By Matt Post, David Vilar. 2018

367 citations recorded by the source corpus.

The end-to-end nature of neural machine translation (NMT) removes many ways of manually guiding the translation process that were available in older paradigms. Recent work, however, has introduced a new capability: lexically constrained or guided decoding, a modification to beam search that forces the inclusion of pre-specified words and phrases in the output. However, while theoretically sound, existing approaches have computational complexities that are either linear (Hokamp and Liu, 2017) or exponential (Anderson et al., 2017) in the number of constraints. We present a algorithm for lexically constrained decoding with a complexity of O(1) in the number of constraints. We demonstrate the algorithm’s remarkable ability to properly place these constraints, and use it to explore the shaky relationship between model and BLEU scores. Our implementation is available as part of Sockeye.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Natural Language Processing

Citations in the corpus

Internet-augmented language models through few-shot prompting for open-domain question answering (2022, neutral): “…if we remain within the few-shot paradigm, more accurate prompt optimization, like in-context example selection, can further boost results [23], while, constrained decoding [35, 36] can be a way to condition the model at inference-time, by explicitly grounding an answer in the provided evidence.”
ProoFVer: Natural Logic Theorem Proving for Fact Verification (2021, methodology): “Therefore, we perform dynamically constrained markup decoding, a modified form of lexically constrained decoding (Post and Vilar, 2018), introduced by De Cao et al.”
Autoregressive Entity Retrieval (2020, methodology): “Lexically constrained decoding has been used to force the inclusion of pre-speciﬁed words for machine translation (Hokamp & Liu, 2017; Post & Vilar, 2018), and image captioning (Anderson et al., 2017).”
Survey of Hallucination in Natural Language Generation (2022, methodology): “[33, 70, 146, 171, 177, 214] and [213] use constrained decoding to incorporate specific terminology into MT, but the above methods can be repurposed to mitigate hallucinations.”
CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning (2020, methodology): “Note that the models are the same as in Table 3 while only the decoding method is changed to DBA.”
Constrained Decoding for Neural NLG from Compositional Representations in Task-Oriented Dialogue (2019, methodology): “Constrained decoding in MT (Post and Vilar, 2018, i.a.) has been used to enforce the use of specific words in the output, rather than constraints on tree structures.”
CTRLsum: Towards Generic Controllable Text Summarization (2020, methodology): “We detail g control next, but describe the automatic keyword extraction later in §2.3.”
Pre-Trained Language Models for Text Generation: A Survey (2022, background): “In addition, when it comes to the tasks that we can predefine some words that must be included in the output text, constraint beam search can be employed considering the constraint words [187].”
FELIX: Flexible Text Editing Through Tagging and Insertion (2020, methodology): “To realize the pointers, we use constrained beam search (Post and Vilar, 2018).”
Revision in Continuous Space: Unsupervised Text Style Transfer without Adversarial Learning (2019, result): “Note that controlling such ﬁne-grained attributes has already been studied in the previous works for other tasks (Post and Vilar 2018; Makino et al. 2019), which only serves as a case study to demonstrate the generality of our method.”
Guided Generation of Cause and Effect (2020, methodology): “To support this output diversity when conditioned on a single shared input sentence, we turn to lexically-constrained decoding [Post and Vilar, 2018; Hu et al. , 2019a], which allows for efﬁciently forcing a model to produce output containing one or more provided phrases.”
Code-Switching for Enhancing NMT with Pre-Specified Translation (2019, background): “In addition, decoding speed is significantly reduced (Post and Vilar, 2018).”
Controlling Text Edition by Changing Answers of Specific Questions (2021, methodology): “The basic methods of lexically constrained decoding can be divided into enhanced beam search (Hokamp and Liu, 2017; Post and Vilar, 2018) and stochastic search (Miao et al.”
CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling (2018, background): “Additionally, researchers pro-pose grid beam search to incorporate constraints in machine translation (Post and Vilar 2018; Hasler et al. 2018; Hokamp and Liu 2017).”
Large-Scale, Diverse, Paraphrastic Bitexts via Sampling and Clustering (2019, background): “They are not formally described in the literature, but an implementation was provided with the associated positive constraints (Post and Vilar, 2018).”
Lexically Constrained Neural Machine Translation with Levenshtein Transformer (2020, methodology): “We proposed a non-autoregressive decoding approach to integrate lexical constraints for NMT.”
Constrained Abstractive Summarization: Preserving Factual Consistency with Constrained Generation (2020, methodology): “At a high level, DBA divides the beam during beam search to store hypotheses satisfying different numbers of constraints and adds unmet constraints at each decoding step.”
Rule-based Morphological Inflection Improves Neural Terminology Translation (2021, methodology): “, 2019; Xu and Carpuat, 2021) or hard constraints (Hokamp and Liu, 2017; Post and Vilar, 2018).”