# Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search

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

## Key facts

- Cited by 237 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2017.

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

- [Survey of Hallucination in Natural Language Generation](https://mlsanity.com/paper/2202.03629/) (2022)
- [ToxiGen: A Large-Scale Machine-Generated Dataset for Adversarial and Implicit Hate Speech Detection](https://mlsanity.com/paper/2203.09509/) (2022)
- [Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning](https://mlsanity.com/paper/2305.13971/) (2023)
- [Constrained Language Models Yield Few-Shot Semantic Parsers](https://mlsanity.com/paper/2104.08768/) (2021)
- [COLD Decoding: Energy-based Constrained Text Generation with Langevin Dynamics](https://mlsanity.com/paper/2202.11705/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Recent Advances in Deep Learning Based Dialogue Systems: A Systematic Survey](https://mlsanity.com/paper/2105.04387/) (2021)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Reversing the Forget-Retain Objectives: An Efficient LLM Unlearning Framework from Logit Difference](https://mlsanity.com/paper/2406.08607/) (2024)
- [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)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [Controlled Text Generation as Continuous Optimization with Multiple Constraints](https://mlsanity.com/paper/2108.01850/) (2021)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (2023)
- [Tailor: Generating and Perturbing Text with Semantic Controls](https://mlsanity.com/paper/2107.07150/) (2021)
- [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)
- [Augmenting Operations Research with Auto-Formulation of Optimization Models from Problem Descriptions](https://mlsanity.com/paper/2209.15565/) (2022)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [Domain Adaptation and Multi-Domain Adaptation for Neural Machine Translation: A Survey](https://mlsanity.com/paper/2104.06951/) (2021)
- [Learning to Reason Deductively: Math Word Problem Solving as Complex Relation Extraction](https://mlsanity.com/paper/2203.10316/) (2022)
- [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)
- [Plansformer: Generating Symbolic Plans using Transformers](https://mlsanity.com/paper/2212.08681/) (2022)
- [A Comprehensive Survey on Data Augmentation](https://mlsanity.com/paper/2405.09591/) (2024)
- [Guided Generation of Cause and Effect](https://mlsanity.com/paper/2107.09846/) (2021)
- [Inference-Time Policy Adapters (IPA): Tailoring Extreme-Scale LMs without Fine-tuning](https://mlsanity.com/paper/2305.15065/) (2023)
- [Should We Rely on Entity Mentions for Relation Extraction? Debiasing Relation Extraction with Counterfactual Analysis](https://mlsanity.com/paper/2205.03784/) (2022)
- [Faithfulness in Natural Language Generation: A Systematic Survey of Analysis, Evaluation and Optimization Methods](https://mlsanity.com/paper/2203.05227/) (2022)

## Abstract (arXiv)

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  mathbfhaty = y0ldots yT , by maximizing  p(y | x) = prodlimitstp(yt | x; y0 ldots yt-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.