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

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

## Key facts

- Cited by 182 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Apr 2018.

## Built on by (most cited first, 30 of 182)

- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [Accelerating scientific discovery with Co-Scientist](https://mlsanity.com/paper/2502.18864/) (2025)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [COLD-Attack: Jailbreaking LLMs with Stealthiness and Controllability](https://mlsanity.com/paper/2402.08679/) (2024)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Internet-augmented language models through few-shot prompting for open-domain question answering](https://mlsanity.com/paper/2203.05115/) (2022)
- [Pretrained Language Models for Text Generation: A Survey](https://mlsanity.com/paper/2201.05273/) (2022)
- [Controlled Text Generation with Natural Language Instructions](https://mlsanity.com/paper/2304.14293/) (2023)
- [Dictionary-based Phrase-level Prompting of Large Language Models for Machine Translation](https://mlsanity.com/paper/2302.07856/) (2023)
- [Evaluating Large Language Models on Controlled Generation Tasks](https://mlsanity.com/paper/2310.14542/) (2023)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Gradient-Based Constrained Sampling from Language Models](https://mlsanity.com/paper/2205.12558/) (2022)
- [Adaptive Machine Translation with Large Language Models](https://mlsanity.com/paper/2301.13294/) (2023)
- [A Plug-and-Play Method for Controlled Text Generation](https://mlsanity.com/paper/2109.09707/) (2021)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [ProoFVer: Natural Logic Theorem Proving for Fact Verification](https://mlsanity.com/paper/2108.11357/) (2021)
- [Gotta be SAFE: A New Framework for Molecular Design](https://mlsanity.com/paper/2310.10773/) (2023)
- [LayoutFormer++: Conditional Graphic Layout Generation via Constraint Serialization and Decoding Space Restriction](https://mlsanity.com/paper/2208.08037/) (2022)
- [Controllable Text Generation with Neurally-Decomposed Oracle](https://mlsanity.com/paper/2205.14219/) (2022)
- [Constrained Decoding for Secure Code Generation](https://mlsanity.com/paper/2405.00218/) (2024)
- [Guided Generation of Cause and Effect](https://mlsanity.com/paper/2107.09846/) (2021)
- [Faithfulness in Natural Language Generation: A Systematic Survey of Analysis, Evaluation and Optimization Methods](https://mlsanity.com/paper/2203.05227/) (2022)
- [Escaping the sentence-level paradigm in machine translation](https://mlsanity.com/paper/2304.12959/) (2023)
- [Denevil: Towards Deciphering and Navigating the Ethical Values of Large Language Models via Instruction Learning](https://mlsanity.com/paper/2310.11053/) (2023)
- [Parallel Refinements for Lexically Constrained Text Generation with BART](https://mlsanity.com/paper/2109.12487/) (2021)
- [Mixture of Soft Prompts for Controllable Data Generation](https://mlsanity.com/paper/2303.01580/) (2023)
- [Gender Neutralization for an Inclusive Machine Translation: from Theoretical Foundations to Open Challenges](https://mlsanity.com/paper/2301.10075/) (2023)
- [A Pseudo-Semantic Loss for Autoregressive Models with Logical Constraints](https://mlsanity.com/paper/2312.03905/) (2023)
- [Can You Traducir This? Machine Translation for Code-Switched Input](https://mlsanity.com/paper/2105.04846/) (2021)

## Abstract (arXiv)

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 algorithms 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.