# NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics

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

## Key facts

- Cited by 154 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 67 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 30 of 33)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [CIDEr: Consensus-based Image Description Evaluation](https://mlsanity.com/paper/1411.5726/) (2014)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [SPICE: Semantic Propositional Image Caption Evaluation](https://mlsanity.com/paper/1607.08822/) (2016)
- [Plug and Play Language Models: A Simple Approach to Controlled Text Generation](https://mlsanity.com/paper/1912.02164/) (2019)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [A Corpus and Evaluation Framework for Deeper Understanding of Commonsense Stories](https://mlsanity.com/paper/1604.01696/) (2016)
- [Toward Controlled Generation of Text](https://mlsanity.com/paper/1703.00955/) (2017)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Challenges in Data-to-Document Generation](https://mlsanity.com/paper/1707.08052/) (2017)
- [Marian: Fast Neural Machine Translation in C++](https://mlsanity.com/paper/1804.00344/) (2018)
- [Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation](https://mlsanity.com/paper/1804.06609/) (2018)
- [NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints](https://mlsanity.com/paper/2010.12884/) (2020)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling](https://mlsanity.com/paper/1811.10996/) (2018)
- [Logical Natural Language Generation from Open-Domain Tables](https://mlsanity.com/paper/2004.10404/) (2020)
- [Comparison of Diverse Decoding Methods from Conditional Language Models](https://mlsanity.com/paper/1906.06362/) (2019)
- [The Radicalization Risks of GPT-3 and Advanced Neural Language Models](https://mlsanity.com/paper/2009.06807/) (2020)
- [Training Neural Machine Translation To Apply Terminology Constraints](https://mlsanity.com/paper/1906.01105/) (2019)
- [Non-Monotonic Sequential Text Generation](https://mlsanity.com/paper/1902.02192/) (2019)
- [Machine Translation Decoding beyond Beam Search](https://mlsanity.com/paper/2104.05336/) (2021)
- [Best-First Beam Search](https://mlsanity.com/paper/2007.03909/) (2020)
- [Neural Machine Translation Decoding with Terminology Constraints](https://mlsanity.com/paper/1805.03750/) (2018)
- [Pragmatically Informative Text Generation](https://mlsanity.com/paper/1904.01301/) (2019)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Findings of the E2E NLG Challenge](https://mlsanity.com/paper/1810.01170/) (2018)
- [Sequence-to-Sequence Generation for Spoken Dialogue via Deep Syntax Trees and Strings](https://mlsanity.com/paper/1606.05491/) (2016)
- [Multi-domain Neural Network Language Generation for Spoken Dialogue Systems](https://mlsanity.com/paper/1603.01232/) (2016)

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

- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Generating Sequences by Learning to Self-Correct](https://mlsanity.com/paper/2211.00053/) (2022)
- [A Contrastive Framework for Neural Text Generation](https://mlsanity.com/paper/2202.06417/) (2022)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [COLD-Attack: Jailbreaking LLMs with Stealthiness and Controllability](https://mlsanity.com/paper/2402.08679/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Controlled Decoding from Language Models](https://mlsanity.com/paper/2310.17022/) (2023)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Internet-augmented language models through few-shot prompting for open-domain question answering](https://mlsanity.com/paper/2203.05115/) (2022)
- [Branch-Solve-Merge Improves Large Language Model Evaluation and Generation](https://mlsanity.com/paper/2310.15123/) (2023)
- [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)
- [Language Generation Models Can Cause Harm: So What Can We Do About It? An Actionable Survey](https://mlsanity.com/paper/2210.07700/) (2022)
- [Sequential Monte Carlo Steering of Large Language Models using Probabilistic Programs](https://mlsanity.com/paper/2306.03081/) (2023)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [COLLIE: Systematic Construction of Constrained Text Generation Tasks](https://mlsanity.com/paper/2307.08689/) (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)
- [Improving Multi-turn Emotional Support Dialogue Generation with Lookahead Strategy Planning](https://mlsanity.com/paper/2210.04242/) (2022)
- [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)
- [DeAL: Decoding-time Alignment for Large Language Models](https://mlsanity.com/paper/2402.06147/) (2024)
- [Grammar-Aligned Decoding](https://mlsanity.com/paper/2405.21047/) (2024)
- [See, Think, Confirm: Interactive Prompting Between Vision and Language Models for Knowledge-based Visual Reasoning](https://mlsanity.com/paper/2301.05226/) (2023)
- [From task structures to world models: What do LLMs know?](https://mlsanity.com/paper/2310.04276/) (2023)
- [Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo](https://mlsanity.com/paper/2504.13139/) (2025)
- [KCTS: Knowledge-Constrained Tree Search Decoding with Token-Level Hallucination Detection](https://mlsanity.com/paper/2310.09044/) (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)

## Abstract (arXiv)

The dominant paradigm for neural text generation is left-to-right decoding from autoregressive language models. Constrained or controllable generation under complex lexical constraints, however, requires foresight to plan ahead feasible future paths. Drawing inspiration from the A* search algorithm, we propose NeuroLogic A*esque, a decoding algorithm that incorporates heuristic estimates of future cost. We develop efficient lookahead heuristics that are efficient for large-scale language models, making our method a drop-in replacement for common techniques such as beam search and top-k sampling. To enable constrained generation, we build on NeuroLogic decoding (Lu et al., 2021), combining its flexibility in incorporating logical constraints with A*esque estimates of future constraint satisfaction. Our approach outperforms competitive baselines on five generation tasks, and achieves new state-of-the-art performance on table-to-text generation, constrained machine translation, and keyword-constrained generation. The improvements are particularly notable on tasks that require complex constraint satisfaction or in few-shot or zero-shot settings. NeuroLogic A*esque illustrates the power of decoding for improving and enabling new capabilities of large-scale language models.