Source-linked AI summary
Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search
Chris Hokamp, Qun Liu
TL;DR
Neural sequence generators may need inference-time lexical information, such as corrections or domain terminology, while preserving the model’s learned distribution. The paper introduces Grid Beam Search, which enforces specified token or phrase constraints during decoding, and reports large interactive-translation improvements and significant domain-adaptation gains without retraining.
Problem
Inference-time user corrections, confident predictions, and domain terminology may need to force specific subsequences into generated outputs without changing model parameters or training data.
Method
Grid Beam Search extends beam search with a grid indexed by decoding timestep and covered constraint tokens, retaining hypotheses that can start or continue arbitrary constraints.
Results
Large translation-quality improvements occurred in interactive scenarios, while domain-specific terminology produced significant gains for domain adaptation without retraining, including approximately +2 BLEU points for En-De and En-Fr and almost 14 for En-Pt.
Takeaways & Limitations
GBS provides a flexible way to incorporate arbitrary subsequences into token-by-token sequence generators and can adapt a general-domain translation model to a new domain without retraining.
Takeaways & Limitations
The paper leaves evaluation with models outside machine translation, such as summarization, image captioning, and dialog generation, to future work.
Abstract
from arXiv · showhide
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 that generates a sequence $ \mathbf{\hat{y}} = \{y_{0}\ldots y_{T}\} $, by maximizing $ p(\mathbf{y} | \mathbf{x}) = \prod\limits_{t}p(y_{t} | \mathbf{x}; \{y_{0} \ldots y_{t-1}\}) $. 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 additional knowledge into a model's output without requiring any modification of the model 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.
1 Introduction
Many NLP systems generate text sequences, but inference-time information such as user corrections or domain terminology may need to guide their outputs. The paper formalizes lexical constraints and proposes decoding that forces specified tokens or phrases into generated sequences.
- Inference-time information, including user corrections, confident predictions, or domain terminology, can inform the search for an optimal output sequence.
- In machine translation, post-editing and interactive-predictive workflows can treat user inputs as lexical constraints guiding the search.
- The proposed algorithm requires specified subsequences to appear in the output, supporting single-token or multi-word constraints and any number of simultaneous constraints.
- Lexically constrained decoding applies to sequence-generation scenarios including machine translation, image description, dialog generation, abstractive summarization, and question answering.
2 Background: Beam Search for Sequence Generation
Sequence generation searches over exponentially many possible outputs, so decoding methods balance tractability against the risk of locally optimal but globally poor decisions. Beam search retains multiple hypotheses and organizes them according to task structure, while neural sequence models commonly organize beams by output timestep.
- A sequence model’s output space contains |v|^T possible sequences, making exhaustive search intractable and motivating factorized decoding.
- Greedy decoding can make locally optimal decisions that are globally sub-optimal, whereas heuristic search discards poor options early to improve tractability.
- Beam search maintains k-best hypothesis lists and adapts beam organization to task structure, such as source coverage in PB-SMT or chart cells in CYK decoding.
- In timestep-based neural decoding, a hypothesis is complete only after generating an end-of-sequence symbol.
- Neural sequence-model beams are organized by output timesteps rather than explicit input coverage, and GBS extends this timestep-based structure.
3 Grid Beam Search
Grid Beam Search organizes constrained decoding in a timestep-by-constraint grid, combining model-generated tokens with mechanisms that start and continue required constraints. Completed top-level hypotheses cover every constraint, while coverage tracking supports multi-token and discontinuous phrases.
- Grid organization: Grid Beam Search indexes beams by timestep and covered constraint tokens, with the top level representing hypotheses that cover all constraints.The total constraint-token count determines the grid’s highest coverage level.
- Hypothesis states: Open hypotheses may generate model continuations or start unused constraints, whereas closed hypotheses continue the current constraint.This distinction permits arbitrary multi-token phrases while preserving constrained search paths.
- Candidate construction: Each grid beam receives candidates by generating ordinary continuations, starting available constraints, or continuing unfinished constraints.These operations are implemented through the model interface’s generate, start, and continue functions.
- Termination: The highest-scoring hypothesis that generates EOS from the fully covered top level is selected as the best sequence satisfying all constraints.Finished hypotheses are collected only after reaching the top level and generating EOS.
- Constraint handling: Coverage vectors prevent constraints from being repeated, and filters can impose ordering conditions for discontinuous constraints such as “ask ⟨someone⟩out.”Constraints may combine individual tokens and phrases, while filters control when separated constraint parts become available.
- Efficiency: GBS has naive runtime complexity O(ktc), compared with O(kt) for standard time-based beam search, but independent columns permit parallelization.Keeping the beam size small can also reduce the time spent computing hypothesis states.
4 Experiments
The experiments evaluate Grid Beam Search for interactive post-editing and terminology-based domain adaptation in neural machine translation. Results show that lexical constraints improve translation quality and can be derived automatically from domain data.
- 4.1 Pick-Revise for Interactive Post Editing: Table 1 reports four simulated editing cycles on WMT test data for EN-DE, EN-FR, and EN-PT.EN-DE uses newstest2013, EN-FR uses newstest2014, and EN-PT uses the Autodesk corpus.
- 4.1 Pick-Revise for Interactive Post Editing: Pick-Revise uses user-provided corrections as lexical constraints in repeated decoding cycles.Each cycle adds a missing phrase of up to three words under strict or relaxed simulation settings.
- 4.2 Domain Adaptation via Terminology: Placeholder-based terminology adaptation requires preprocessing changes, training data containing test-time placeholders, and loses direct modeling of terminology tokens.The alternative is to provide term mappings directly as constraints.
- 4.2 Domain Adaptation via Terminology: The Autodesk Post-Editing corpus supplies approximately 100,000 training sentences and 1,000 test segments for software-localization domain adaptation.Terminology candidates are source-target n-grams of lengths 2-5 selected using PMI.
- 4.2 Domain Adaptation via Terminology: Terminology candidates are retained when normalized PMI is at least 0.9 and both phrases occur at least five times.Matching source phrases in test data trigger the corresponding target phrases as decoding constraints.
- 4.2 Domain Adaptation via Terminology: +2 BLEU points for EN-DE and EN-FR, and almost +14 points for EN-PT, were obtained without human intervention using automatically created terminology with GBS.The authors attribute the larger EN-PT improvement partly to a mismatch between training data and the IT domain.
- 4.3 Analysis: Constrained phrases were placed correctly and produced global effects on translation quality in subjective analysis.The analysis suggests that users can bootstrap quality by adding the most critical constraints first.
5 Related Work
Prior work largely addressed constrained machine translation through alignment- or phrase-boundary-dependent methods. This paper presents general token-level lexical constraint decoding for sequence-generating models without input-output alignments.
- Interactive machine translation treats user-specified target prefixes as lexical constraints guiding the search for an optimal suffix.
- Multiple-constraint SMT methods support iterative user corrections, preserving earlier constraints while adding new ones across edit cycles.
- Earlier SMT approaches constrain output through aligned source-target phrases and therefore depend on phrase boundaries or explicit input coverage.
- Constraint-aware neural models for dialog and recipe generation are complementary to GBS and can be used with it without changing the underlying models.
- GBS is presented as the first general constrained decoding approach for sequence-generating models that avoids alignments and input-coverage-organized search.
6 Conclusion
The conclusion presents GBS as a flexible way to impose arbitrary subsequences during token-level generation. Experiments show benefits for interactive translation and terminology-based domain adaptation without retraining, while evaluation beyond MT remains future work.
- GBS incorporates arbitrary subsequences into token-by-token outputs and should be straightforward to use with models that already use beam search.
- Translator corrections can serve as constraints, producing a new output after each correction and yielding large translation-quality improvements at each simulated iteration.
- Domain-specific terminology can generate target-side constraints that adapt a general translation model to a new domain without retraining.
- The paper proposes future evaluation of GBS with automatic summarization, image captioning, and dialog-generation models outside machine translation.
A NMT System Configurations
The NMT systems use bidirectional GRU encoders and GRU decoders, with language-pair-specific dimensions, vocabularies, and batch sizes. Training uses AdaDelta and gradient clipping alongside regularization and dropout.
- Training runs for 500000 iterations with validation every 5000 steps, selecting the best validated single model for each language pair.
- All systems use bidirectional GRUs for source representation and GRUs for decoder transitions, with AdaDelta updates and gradients clipped to 1.0.
- The configurations vary by language pair in embedding size, recurrent-layer size, source and target vocabulary sizes, and batch size.EN-DE uses 300-dimensional embeddings, 1000 recurrent units, 80000/90000 vocabularies, and batch size 50; EN-FR and EN-PT use separate settings.
A.1 English-German
The English-German training corpus contains 4.4 Million segments drawn from Europarl and CommonCrawl.
- 4.4 Million segments from Europarl and CommonCrawl comprise the English-German training corpus.
A.2 English-French
The English-French training corpus contains 4.9 million segments drawn from Europarl and CommonCrawl.
- 4.9 million segments comprise the English-French training corpus.
- The corpus draws from Europarl.
- The corpus also draws from CommonCrawl.
A.3 English-Portuguese
The English-Portuguese training corpus consists of 28.5 million segments from Europarl, JRC-Aquis, and OpenSubtitles5.
- 28.5 million segments comprise the English-Portuguese training corpus.
- The corpus includes Europarl and JRC-Aquis data.
- The corpus includes OpenSubtitles5 data.