# PPL-MCTS: Constrained Textual Generation Through Discriminator-Guided MCTS Decoding

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 39 references that are in the map.
- First posted on arXiv 28 Sep 2021.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Models](https://mlsanity.com/paper/2009.11462/) (2020)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [CTRL: A Conditional Transformer Language Model for Controllable Generation](https://mlsanity.com/paper/1909.05858/) (2019)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [Texygen: A Benchmarking Platform for Text Generation Models](https://mlsanity.com/paper/1802.01886/) (2018)
- [GeDi: Generative Discriminator Guided Sequence Generation](https://mlsanity.com/paper/2009.06367/) (2020)
- [Why We Need New Evaluation Metrics for NLG](https://mlsanity.com/paper/1707.06875/) (2017)
- [Data Augmentation using Pre-trained Transformer Models](https://mlsanity.com/paper/2003.02245/) (2020)
- [FlauBERT: Unsupervised Language Model Pre-training for French](https://mlsanity.com/paper/1912.05372/) (2019)
- [Learning to Write with Cooperative Discriminators](https://mlsanity.com/paper/1805.06087/) (2018)
- [Language GANs Falling Short](https://mlsanity.com/paper/1811.02549/) (2018)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [DARE: Data Augmented Relation Extraction with GPT-2](https://mlsanity.com/paper/2004.13845/) (2020)
- [Discriminative Adversarial Search for Abstractive Summarization](https://mlsanity.com/paper/2002.10375/) (2020)
- [To Beam Or Not To Beam: That is a Question of Cooperation for Language GANs](https://mlsanity.com/paper/2106.06363/) (2021)

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

- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [ARGS: Alignment as Reward-Guided Search](https://mlsanity.com/paper/2402.01694/) (2024)
- [Transformer-based Planning for Symbolic Regression](https://mlsanity.com/paper/2303.06833/) (2023)
- [Don't throw away your value model! Generating more preferable text with Value-Guided Monte-Carlo Tree Search decoding](https://mlsanity.com/paper/2309.15028/) (2023)
- [WaterMax: breaking the LLM watermark detectability-robustness-quality trade-off](https://mlsanity.com/paper/2403.04808/) (2024)
- [When is Tree Search Useful for LLM Planning? It Depends on the Discriminator](https://mlsanity.com/paper/2402.10890/) (2024)
- [KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection](https://mlsanity.com/paper/2310.09044/) (2023)
- [Ensembling Large Language Models with Process Reward-Guided Tree Search for Better Complex Reasoning](https://mlsanity.com/paper/2412.15797/) (2024)
- [InfAlign: Inference-aware language model alignment](https://mlsanity.com/paper/2412.19792/) (2024)
- [Discrete Prompt Optimization via Constrained Generation for Zero-shot Re-ranker](https://mlsanity.com/paper/2305.13729/) (2023)
- [Training Turn-by-Turn Verifiers for Dialogue Tutoring Agents: The Curious Case of LLMs as Your Coding Tutors](https://mlsanity.com/paper/2502.13311/) (2025)
- [Faithful Question Answering with Monte-Carlo Planning](https://mlsanity.com/paper/2305.02556/) (2023)
- [Don't Rank, Combine! Combining Machine Translation Hypotheses Using Quality Estimation](https://mlsanity.com/paper/2401.06688/) (2024)
- [A Critical Look At Tokenwise Reward-Guided Text Generation](https://mlsanity.com/paper/2406.07780/) (2024)
- [Autoregressive Modeling with Lookahead Attention](https://mlsanity.com/paper/2305.12272/) (2023)
- [Best-k Search Algorithm for Neural Text Generation](https://mlsanity.com/paper/2211.11924/) (2022)
- [Entropy-Reinforced Planning with Large Language Models for Drug Discovery](https://mlsanity.com/paper/2406.07025/) (2024)
- [Language Model Decoding as Likelihood-Utility Alignment](https://mlsanity.com/paper/2210.07228/) (2022)
- [Towards Cost-Effective Reward Guided Text Generation](https://mlsanity.com/paper/2502.04517/) (2025)
- [How Sampling Affects the Detectability of Machine-written texts: A Comprehensive Study](https://mlsanity.com/paper/2510.13681/) (2025)
- [Monte Carlo Tree Search for Recipe Generation using GPT-2](https://mlsanity.com/paper/2401.05199/) (2024)
- [ScaffoldGPT: A Scaffold-based GPT Model for Drug Optimization](https://mlsanity.com/paper/2502.06891/) (2025)
- [Aligning Sentence Simplification with ESL Learner's Proficiency for Language Acquisition](https://mlsanity.com/paper/2502.11457/) (2025)
- [Which Discriminator for Cooperative Text Generation?](https://mlsanity.com/paper/2204.11586/) (2022)
- [Agentic AI: The Era of Semantic Decoding](https://mlsanity.com/paper/2403.14562/) (2024)
- [Constraints-of-Thought: A Framework for Constrained Reasoning in Language-Model-Guided Search](https://mlsanity.com/paper/2510.08992/) (2025)
- [TruncProof: A Guardrail for LLM-based JSON Generation under Token-Length Constraints](https://mlsanity.com/paper/2605.13076/) (2026)
- ["Honey, Tell Me What's Wrong", Global Explanation of Textual Discriminative Models through Cooperative Generation](https://mlsanity.com/paper/2310.18063/) (2023)

## Abstract (arXiv)

Large language models (LM) based on Transformers allow to generate plausible long texts. In this paper, we explore how this generation can be further controlled at decoding time to satisfy certain constraints (e.g. being non-toxic, conveying certain emotions, using a specific writing style, etc.) without fine-tuning the LM. Precisely, we formalize constrained generation as a tree exploration process guided by a discriminator that indicates how well the associated sequence respects the constraint. This approach, in addition to being easier and cheaper to train than fine-tuning the LM, allows to apply the constraint more finely and dynamically. We propose several original methods to search this generation tree, notably the Monte Carlo Tree Search (MCTS) which provides theoretical guarantees on the search efficiency, but also simpler methods based on re-ranking a pool of diverse sequences using the discriminator scores. These methods are evaluated, with automatic and human-based metrics, on two types of constraints and languages: review polarity and emotion control in French and English. We show that discriminator-guided MCTS decoding achieves state-of-the-art results without having to tune the language model, in both tasks and languages. We also demonstrate that other proposed decoding methods based on re-ranking can be really effective when diversity among the generated propositions is encouraged.