Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search

By Chris Hokamp, Qun Liu. 2017

460 citations recorded by the source corpus.

We present Grid Beam Search (GBS), an algorithm which extends beam search to allow the inclusion of pre-specified lexical constraints. The algorithm can be used with any model which generates sequences token by token. Lexical constraints take the form of phrases or words that must be present in the output sequence. This is a very general way to incorporate auxillary knowledge into a model’s output without requiring any modification of the parameters or training data. We demonstrate the feasibility and flexibility of Lexically Constrained Decoding by conducting experiments on Neural Interactive-Predictive Translation, as well as Domain Adaptation for Neural Machine Translation. Experiments show that GBS can provide large improvements in translation quality in interactive scenarios, and that, even without any user input, GBS can be used to achieve significant gains in performance in domain adaptation scenarios.

Subfields: Artificial Intelligence, 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 Natural Language Processing

Citations in the corpus

ToxiGen: A Large-Scale Machine-Generated Dataset for Adversarial and Implicit Hate Speech Detection (2022, methodology): “Therefore, we also develop ALICE, a variant of constrained beam search (CBS; Anderson et al., 2017; Hokamp and Liu, 2017; Holtzman et al., 2018; Lu et al., 2021) during decoding that generates statements that are adversarial to a given pre-trained toxicity classifier.”
Discriminative Adversarial Search for Abstractive Summarization (2020, background): “Hokamp & Liu (2017) reported improvements when adding lexical constraints to beam search.”
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).”
Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction (2022, background): “In fact, better understanding the behavior and effect of beam search in seq2seq models remains an active research topic (Cohen and Beck, 2019; Koehn and Knowles, 2017; Hokamp and Liu, 2017), and we believe how to perform effective beam search in our setup could be an interesting research question th”
Survey of Hallucination in Natural Language Generation (2022, background): “Liu et al. [94] select training instances based on faithfulness ranking.”
Tailor: Generating and Perturbing Text with Semantic Controls (2021, methodology): “7For UD Parsing contrast set generation, we use constrained decoding (Hokamp and Liu, 2017) to prevent generation of the original prepositional phrase.”
CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning (2020, background): “Two related scenarios with our task is lexically constrained decoding and word ordering (Zhang and Clark, 2015; Hasler et al., 2018; Dinu et al., 2019; Hokamp and Liu, 2017; Puduppully et al., 2017; Miao et al., 2019).”
Text Modular Networks: Learning to Decompose Tasks in the Language of Existing Models (2021, methodology): “While a constrained-decoding approach (Hokamp and Liu, 2017; Hu et al., 2019a) could be used here to further promote the use of the vocabulary hints, this simple approach was effective and more generally applicable to other hints in our use-case.”
Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation (2018, background): “However, while theoretically sound, existing approaches have computational complexities that are either linear (Hokamp and Liu, 2017) or exponential (Anderson et al.”
CTRLsum: Towards Generic Controllable Text Summarization (2020, methodology): “We detail g control next, but describe the automatic keyword extraction later in §2.3.”
Lexically Constrained Neural Machine Translation with Levenshtein Transformer (2020, background): “Another approach focused on constrained beam search decoding (Hokamp and Liu, 2017; Post and Vilar, 2018; Hu et al., 2019).”
Don’t Say What You Don’t Know: Improving the Consistency of Abstractive Summarization by Constraining Beam Search (2022, background): “Our approach can be viewed as a version of constrained decoding (Hokamp and Liu, 2017) but with dynamically identiﬁed constraints and the ability to back-track.”
Parallel Sentence Mining by Constrained Decoding (2020, methodology): “The way we avoid pairwise scoring is inspired by constrained decoding in NMT, where the choice of output tokens is constrained to a pre-deﬁned list (Hokamp and Liu, 2017).”
Guided Generation of Cause and Effect (2020, background): “lexically-constrained decoding [Hokamp and Liu, 2017] is a modification of beam search originating in neural machine translation which allows the user to specify tokens that must (or must not) appear in the decoder’s output.”
Training Neural Machine Translation to Apply Terminology Constraints (2019, unknown): “Luong et al. (2015) and SYSTRANs Pure NMT system (Crego et al.”
Text Editing by Command (2020, background): “Hokamp and Liu (2017) and Zhang et al. (2020b) use lexical constraints, while Keskar et al. (2019) and Dathathri et al. (2020) control higher level attributes of text, such as style, tone, or topic.”
Empirical Analysis of Beam Search Performance Degradation in Neural Sequence Models (2019, background): “Hokamp & Liu (2017) proposed grid beam search to support lexical constraints.”
“Nice Try, Kiddo”: Investigating Ad Hominems in Dialogue Responses (2021, background): “Hokamp and Liu (2017); Post and Vilar (2018) propose variants of Grid Beam Search, which generate output that include lexical constraints.”
Dictionary-based Data Augmentation for Cross-Domain Neural Machine Translation (2020, background): “For example, Hokamp and Liu (2017) uses a domain-speciﬁc terminology to generate target-side constraints to enable a general domain model to adapt to a new domain with signiﬁcant performance gains.”
Towards Understanding Neural Machine Translation with Word Importance (2019, background): “• Interactive MT and Constraint Decoding (Foster et al., 1997; Hokamp and Liu, 2017): The model pays more attention to the detected unimportant words, which are possibly under-translated;”