# Language Generation via Combinatorial Constraint Satisfaction: A Tree Search Enhanced Monte-Carlo Approach

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

## Key facts

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

## Built on by (most cited first, 3 of 3)

- [LayoutFormer++: Conditional Graphic Layout Generation via Constraint Serialization and Decoding Space Restriction](https://mlsanity.com/paper/2208.08037/) (2022)
- [Zero-shot Clarifying Question Generation for Conversational Search](https://mlsanity.com/paper/2301.12660/) (2023)
- [Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offs](https://mlsanity.com/paper/2112.05702/) (2021)

## Abstract (arXiv)

Generating natural language under complex constraints is a principled formulation towards controllable text generation. We present a framework to allow specification of combinatorial constraints for sentence generation. We propose TSMH, an efficient method to generate high likelihood sentences with respect to a pre-trained language model while satisfying the constraints. Our approach is highly flexible, requires no task-specific training, and leverages efficient constraint satisfaction solving techniques. To better handle the combinatorial constraints, a tree search algorithm is embedded into the proposal process of the Markov chain Monte Carlo (MCMC) to explore candidates that satisfy more constraints. Compared to existing MCMC approaches, our sampling approach has a better mixing performance. Experiments show that TSMH achieves consistent and significant improvement on multiple language generation tasks.