# CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling

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

## Key facts

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

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

- [Analyzing Leakage of Personally Identifiable Information in Language Models](https://mlsanity.com/paper/2302.00539/) (2023)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [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)
- [Recent Advances in Deep Learning Based Dialogue Systems: A Systematic Survey](https://mlsanity.com/paper/2105.04387/) (2021)
- [MARS: Markov Molecular Sampling for Multi-objective Drug Discovery](https://mlsanity.com/paper/2103.10432/) (2021)
- [Aligning Language Models with Preferences through f-divergence Minimization](https://mlsanity.com/paper/2302.08215/) (2023)
- [Amortizing intractable inference in large language models](https://mlsanity.com/paper/2310.04363/) (2023)
- [Improving Coherence and Consistency in Neural Sequence Models with Dual-System, Neuro-Symbolic Reasoning](https://mlsanity.com/paper/2107.02794/) (2021)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [A Plug-and-Play Method for Controlled Text Generation](https://mlsanity.com/paper/2109.09707/) (2021)
- [Edit Flows: Flow Matching with Edit Operations](https://mlsanity.com/paper/2506.09018/) (2025)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [Space Group Informed Transformer for Crystalline Materials Generation](https://mlsanity.com/paper/2403.15734/) (2024)
- [Coherence boosting: When your pretrained language model is not paying enough attention](https://mlsanity.com/paper/2110.08294/) (2021)
- [Automatic Pseudo-Harmful Prompt Generation for Evaluating False Refusals in Large Language Models](https://mlsanity.com/paper/2409.00598/) (2024)
- [Impossible Distillation: from Low-Quality Model to High-Quality Dataset & Model for Summarization and Paraphrasing](https://mlsanity.com/paper/2305.16635/) (2023)
- [Learning to Model Editing Processes](https://mlsanity.com/paper/2205.12374/) (2022)
- [Faithfulness in Natural Language Generation: A Systematic Survey of Analysis, Evaluation and Optimization Methods](https://mlsanity.com/paper/2203.05227/) (2022)
- [Parallel Refinements for Lexically Constrained Text Generation with BART](https://mlsanity.com/paper/2109.12487/) (2021)
- [Sample, Don't Search: Rethinking Test-Time Alignment for Language Models](https://mlsanity.com/paper/2504.03790/) (2025)
- [Why is constrained neural language generation particularly challenging?](https://mlsanity.com/paper/2206.05395/) (2022)
- [Controllable Summarization with Constrained Markov Decision Process](https://mlsanity.com/paper/2108.03405/) (2021)
- [Text Revision by On-the-Fly Representation Optimization](https://mlsanity.com/paper/2204.07359/) (2022)
- [Constrained Discrete Diffusion](https://mlsanity.com/paper/2503.09790/) (2025)
- [Prompt-Based Editing for Text Style Transfer](https://mlsanity.com/paper/2301.11997/) (2023)
- [QUEST: Quality-Aware Metropolis-Hastings Sampling for Machine Translation](https://mlsanity.com/paper/2406.00049/) (2024)
- [NAREOR: The Narrative Reordering Problem](https://mlsanity.com/paper/2104.06669/) (2021)
- [Zero-shot Clarifying Question Generation for Conversational Search](https://mlsanity.com/paper/2301.12660/) (2023)
- [ConRPG: Paraphrase Generation using Contexts as Regularizer](https://mlsanity.com/paper/2109.00363/) (2021)

## Abstract (arXiv)

In real-world applications of natural language generation, there are often constraints on the target sentences in addition to fluency and naturalness requirements. Existing language generation techniques are usually based on recurrent neural networks (RNNs). However, it is non-trivial to impose constraints on RNNs while maintaining generation quality, since RNNs generate sentences sequentially (or with beam search) from the first word to the last. In this paper, we propose CGMH, a novel approach using Metropolis-Hastings sampling for constrained sentence generation. CGMH allows complicated constraints such as the occurrence of multiple keywords in the target sentences, which cannot be handled in traditional RNN-based approaches. Moreover, CGMH works in the inference stage, and does not require parallel corpora for training. We evaluate our method on a variety of tasks, including keywords-to-sentence generation, unsupervised sentence paraphrasing, and unsupervised sentence error correction. CGMH achieves high performance compared with previous supervised methods for sentence generation. Our code is released at https://github.com/NingMiao/CGMH