Source-linked AI summary
NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics
Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, Noah A. Smith, Yejin Choi
TL;DR
Constrained neural generation needs foresight beyond left-to-right decoding to plan feasible future paths. NeuroLogic A*esque adds efficient A*-like lookahead heuristics to common decoding methods and NeuroLogic’s logical constraints, outperforming baselines across five tasks, particularly in low-data settings.
Problem
Constrained generation requires foresight to plan future paths that satisfy complex lexical constraints, which standard left-to-right decoding does not explicitly provide.
Method
NeuroLogic A*esque combines efficient A*-like future-cost and constraint-satisfaction heuristics with common decoding algorithms and NeuroLogic’s logical constraints.
Results
NeuroLogic A*esque outperforms competitive decoding baselines across five generation tasks, with especially pronounced gains in zero-shot and few-shot settings and state-of-the-art results in several settings.
Takeaways & Limitations
Lookahead decoding supports constrained and unconstrained generation while reducing reliance on costly labeled data for inference-time control.
Takeaways & Limitations
Exact future-cost computation is difficult, and the space of future trajectories is prohibitively large, requiring approximate lookahead heuristics.
Abstract
from arXiv · showhide
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.
1 Introduction
NeuroLogic A*esque extends left-to-right neural decoding with efficient lookahead heuristics that estimate future cost and constraint satisfaction. It combines these estimates with logical constraints and common decoding strategies, improving generation across diverse tasks, especially low-data settings.
- Motivation: Left-to-right decoding chooses tokens from the generated past, but constrained generation requires planning ahead to incorporate all desired content.This limitation is less consequential for open-ended generation, where many coherent outputs may be acceptable.
- Approach: NeuroLogic A*esque combines A*-like future-cost estimates with beam search and top-k sampling while preserving large-model decoding efficiency.Its lookahead heuristics approximate future cost using continuations of the sequence-so-far because exact optimization is NP-complete.
- Approach: The method builds on NeuroLogic Decoding by adding future constraint-satisfaction heuristics and unconstrained variants that operate with empty constraint sets.This extends logical lexical-constraint control to both constrained and unconstrained generation.
- Results: Five-task experiments show that NeuroLogic A*esque outperforms competitive baselines, with especially pronounced gains in zero-shot and few-shot settings.The experiments include both supervised and unsupervised models.
- Results: The method achieves state-of-the-art performance on constrained English-German translation and few-shot table-to-text generation.An off-the-shelf language model with the proposed decoder also outperforms supervised baselines on COMMONGEN.
- Implications: Inference-time constraint handling broadens task applicability and can reduce reliance on costly manually annotated datasets.The paper presents this flexibility as a consequence of applying constraints during decoding rather than requiring task-specific supervision.
2 NEUROLOGIC A⋆esque Decoding
NEUROLOGIC⋆ frames decoding as discrete search and uses A⋆-like lookahead heuristics to estimate future sequence quality and constraint satisfaction. It extends NEUROLOGIC for constrained generation while supporting efficient unconstrained and constrained variants.
- Decoding as search: NEUROLOGIC⋆ treats prefixes as search states, tokens as actions, and decoding as expanding, scoring, and pruning candidate next-states.Common decoding methods score candidates from the sequence history, whereas NEUROLOGIC⋆ estimates future outcomes during selection.
- Limitations and approximation: Exact future optimization is difficult because the objective may be unknown or costly to compute and the future-trajectory space is prohibitively large.Lookahead heuristics address these computational difficulties by approximating future costs from continuations of the sequence-so-far.
- A⋆esque decoding: A⋆esque decoding combines beam-style expansion and pruning with heuristic estimates of future score.The objective can combine sequence log probability with a constraint-satisfaction score, while a lightweight heuristic approximates future cost.
- Lookahead heuristics: Greedy and soft lookaheads efficiently explore a single continuation, while beam lookahead returns top-k continuations to trade efficiency for exploration.Soft lookahead interpolates between greedy-token inputs and a uniform token mixture through temperature; beam lookahead runs beam search for ℓ steps.
- Constrained generation: NEUROLOGIC accepts positive or negative lexical constraints in CNF and uses pruning and grouping to promote constraint satisfaction and candidate diversity.Its approximate search targets fluent sequences satisfying all clauses, while candidates violating constraints are pruned before selection.
- Constrained generation: NEUROLOGIC⋆ extends NEUROLOGIC by estimating future constraint satisfaction in lookahead continuations.The added heuristic adjusts candidate scores according to the probability of satisfying additional constraints, including multi-token constraints and future constraints.
3 Experiments: Constrained Generation
Experiments evaluate NEUROLOGIC⋆ across constrained and unconstrained generation settings, supervision regimes, tasks, and lookahead strategies. The method consistently improves over prior approaches, especially in zero-shot and few-shot settings, while different heuristics expose practical accuracy–efficiency trade-offs.
- Experimental scope: Experiments cover COMMONGEN, constrained machine translation, table-to-text generation, and interrogative sentence generation across zero-shot, few-shot, and full-shot settings.Both constrained and unconstrained tasks are studied, using automatic metrics including BLEU, ROUGE, METEOR, CIDEr, SPICE, and NIST.
- Overall results: NEUROLOGIC⋆ consistently outperforms NEUROLOGIC and previous approaches, with especially substantial improvements in zero-shot and few-shot cases.The paper attributes the harder search problem in these settings to limited supervision and larger output spaces.
- COMMONGEN: On COMMONGEN, NEUROLOGIC⋆ outperforms previous constrained-decoding methods in supervised and zero-shot settings while maintaining high constraint satisfaction and improving generation quality.The unsupervised variant even outperforms supervised methods on human evaluation; only greedy NEUROLOGIC⋆ was tested unsupervised because of computational cost.
- Lookahead analysis: Increasing greedy lookahead improves performance through approximately 5–7 steps, after which performance decreases, likely because long-horizon approximation becomes difficult.Soft lookahead performs well at τ = 0.0, with only slight gains from careful temperature selection.
- Lookahead analysis: Beam lookahead improves performance as beam width increases up to 11, while sampling lookahead improves with more than one sample before reaching an inflection point.Across strategies, beam lookahead slightly outperforms others in human evaluation, whereas greedy lookahead has the lowest runtime.
- Task-specific results: In constrained machine translation and few-shot table-to-text generation, NEUROLOGIC⋆ improves quality and constraint coverage, including strong results with off-the-shelf or minimally supervised models.It outperforms prior translation methods in BLEU and term coverage, achieves 96.5 versus 93.7 term coverage compared with NEUROLOGIC in one setting, and surpasses table-to-text approaches by a large margin.
4 Experiments: Unconstrained Generation
The experiments test A*esque lookahead for unconstrained story generation by applying it to beam search and top-k sampling. The heuristics improve story quality and can guide decoding toward favorable output spaces across decoding settings.
- Approach: A*esque decoding is applied to beam search and top-k sampling for RocStories story continuation generation.The task uses the first sentence as a prompt, and top-k scores are adjusted and renormalized with the heuristic.
- Results: A*esque heuristics improve fluency, coherence, and interestingness for both beam search and top-k sampling.For top-k sampling, the improvement occurs while maintaining comparable diversity.
- Results: 2.32 to 2.63: beam-search human evaluation scores improve with the A*esque heuristic.The same intervention also boosts generation diversity, measured by unique n-grams.
- Results: Beam lookahead works best for beam search, whereas greedy lookahead works best for top-k sampling.The paper attributes this pattern to how closely each heuristic estimates the future path of its decoding method.
- Ablations: A*esque decoding guides generation toward a more favorable output space regardless of decoding hyperparameters.The ablation varies beam size and top-k value while examining likelihood-based fluency and unique 3-gram diversity.
5 Related Work
Related work covers A* search in structured NLP and decoding methods for diversity, fluency, and constraints. NeuroLogic A*esque extends this line by estimating future text viability during constrained decoding.
- A* search in NLP: A* search has been applied effectively to structured NLP problems such as parsing, text alignment, and high-probability alignment search.Applying informed heuristic search to autoregressive text generation remains underexplored in the cited work.
- Decoding strategies for text generation: Prior decoding research addresses diversity, fluency, or constraints in autoregressive text generation.Constrained beam search and grid beam search extend beam search to satisfy lexical constraints during generation.
- Decoding strategies for text generation: Other approaches edit full generations, optimize continuously, or encode constraints as generated contexts.The cited methods include Metropolis-Hastings editing, gradient-based updates, and conditioning on generated contexts.
- Decoding strategies for text generation: NeuroLogic A*esque explicitly samples future text to estimate the viability of paths toward satisfying constraints.It builds on NeuroLogic's CNF constraints and extends them into the future with lookahead heuristics.
6 Conclusion
The paper introduces NeuroLogic A*esque decoding, which adds A*-like future-cost heuristics to common left-to-right neural text-generation algorithms. Its lookahead improves decoding across constrained and unconstrained tasks by incorporating information from both past and future.
- 6 Conclusion: NeuroLogic A*esque brings A*-like heuristic estimates of future cost to common left-to-right decoding algorithms.The method is presented as a way to move beyond unidirectional decoding for neural text generation.
- 6 Conclusion: Lookahead heuristics improve NeuroLogic, beam, greedy, and sampling methods across constrained and unconstrained settings.The conclusion describes these improvements across a wide spectrum of tasks.
- 6 Conclusion: The approach uses bidirectional information from past and future to generate more globally compatible text.This consequence is stated as the paper's broader conclusion about moving beyond unidirectional decoding.
A Human Evaluation
The appendix includes screenshots of human-evaluation templates for the CommonGen, Interrogative Sentence Generation, and RocStories tasks.
- Human-evaluation templates: Human-evaluation templates are provided for the CommonGen task.
- Human-evaluation templates: Human-evaluation templates are provided for the Interrogative Sentence Generation task.
- Human-evaluation templates: A human-evaluation template is provided for the RocStories task.