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

By Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers and 2 more. 2021

200 citations recorded by the source corpus.

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 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.

Subfields: Artificial Intelligence, Natural Language Processing, Prompting & Reasoning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

In Prompting & Reasoning

Citations in the corpus

Language Generation Models Can Cause Harm: So What Can We Do About It? An Actionable Survey (2022, methodology): “One branch of work adopts logical controls, in which developers directly specify sets of words that should or should not appear in the output (Lu et al., 2021b; Pascual et al., 2021).”
Internet-augmented language models through few-shot prompting for open-domain question answering (2022, background): “Moreover, constrained decoding (Post & Vilar, 2018; Lu et al., 2021) could be another way to condition the model at inference-time, by explicitly grounding an answer in the provided evidence.”
Tree of Thoughts: Deliberate Problem Solving with Large Language Models (2023, methodology): “From this perspective, our method is also related to NeuroLogic A*esque decoding proposed in [16], which is inspired by A* search but introduces look-ahead heuristics that are efﬁcient for LMs to improve the beam-search or top-k sampling decoding.”
Planning with Large Language Models for Code Generation (2023, methodology): “Lu et al. (2021) consider the constrained text generation problem and integrate A* with the beam search algorithm.”
Gradient-based Constrained Sampling from Language Models (2022, methodology): “We use Lu et al. (2021a)”
See, Think, Confirm: Interactive Prompting Between Vision and Language Models for Knowledge-based Visual Reasoning (2023, unknown): “To make the regional captions more consistent with the question, we generate the regional caption with constrained decoding [45].”
Break the Sequential Dependency of LLM Inference Using Lookahead Decoding (2024, background): “It shows notable speedup without a draft model and can linearly decrease the decoding steps with exponential investment in per-step FLOPs.”