N euro L ogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics (2022)

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

## introduction the dominant paradigm for neural text generation is based on left-to-right decoding from autoregressive language models such as gpt-2/3 @xcite . under this paradigm, common decoding techniques such as beam search or top-k/p sampling @xcite figure 1: neurologic leverages lookahead heuristics to guide generations towards those that satisfy the given task-specific constraints. in this example from the commongen task, although summer is a more likely next word given the already-generated past, neurologic looks ahead to see that selecting winter results in a generation that incorporates unsatisfied constraint snow with a higher probability later on. thus, winter is preferred despite being lower probability than summer. classical search algorithms such as a* search @xcite @xcite address the challenge of planning ahead by using heuristic estimation of future cost when making decisions. drawing inspiration from a* search, we develop neurologic a esque (shortened to neurologic ), which combines a*-like heuristic estimates of future cost (e.g., perplexity, constraint satisfaction) with common decoding algorithms for neural text generation (e.g., beam search, top-k sampling), while preserving the efficiency demanded by large-scale neural language models. as selecting the next token to generate based on the optimal future cost is np-complete @xcite , we develop lookahead heuristics, which approximate cost at each decoding step based on con-tinuations of the sequence-so-far. figure 1 shows an example, where neurologic a esque guides generation towards a decision that would have been ignored based on the past alone, but is selected after looking ahead and incorporating the probability that constraints are satisfied in the future. our approach builds on neurologic decoding of @xcite , a variation of beam-search for controlling generation through rich logic-based lexical constraints expressed in conjunctive normal form (cnf). our work generalizes @xcite by (1) incorporating novel lookahead heuristics to estimate future contraint satisfaction, and (2) developing additional unconstrained variants that can work with an empty set of constraints. these new algorithm variants support broad applications of neurologic , including unconstrained generation, as demonstrated in our experiments. our experiments across five generation tasks demonstrate that our approach outperforms competitive baselines. we test neurologic in conjunction with both supervised and unsupervised models and find that the performance gain is pronounced especially in zero-shot or few-shot settings. on the commongen benchmark, using neurologic with an off-the-shelf language model outperforms a host of supervised baselines with conventional decoding algorithms, demonstrating that a strong inference-time algorithm such as neurologic can alleviate the need for costly annotated datasets. moreover, neurologic achieves state-of-the-art performance in various settings, including wmt17 english-german machine translation with lexical constraints @xcite and few-shot e2enlg table-to-text generation @xcite . in summary, we develop neurologic a esque, a new decoding algorithm for effective and efficient text generation. to our knowledge this is the first a*-like algorithm for guided text generation via lookahead heuristics. our algorithm is versatile, as it can be applied to a variety of tasks via inference-time constraints, reducing the need for costly labeled data. extensive experiments show its effectiveness on several important generation benchmarks. ## neurologic a esque decoding we describe neurologic a esque decoding (shortened as neurologic ), our decoding algorithm motivated by a * search @xcite ), a best-first search algorithm that finds high-scoring paths using a heuristic estimate of future return. we first introduce the decoding problem, and then describe our heuristics with a novel lookahead procedure for adapting neurologic search to unconstrained and constrained generation with largescale autoregressive models. ## experiments we first consider constrained generation benchmarks: commongen ( §3.1), constrained machine translation ( §3.2), table-to-text generation ( §3.3), and constrained question generation ( §3.4). neurologic consistently outperforms previous approaches, especially in zero-shot and fewshot cases. these low-resource settings are particularly important, as many practical tasks face data scarcity. finally, we find that a esque lookahead is useful even without constraints, as shown in unconstrained story generation task ( §3.5). ## conclusion inspired by the a* search algorithm, we introduce neurologic a esque decoding, which brings a*-like heuristic estimates of the future to common left-to-right decoding algorithms for neural text generation. a esque lookahead heuristics improve over existing decoding methods (e.g., neu-rologic, beam, greedy, sample decoding methods) in both constrained and unconstrained settings across a wide spectrum of tasks. our work demonstrates the promise of moving beyond the current paradigm of unidirectional decoding for text generation, by taking bidirectional information from both the past and future into account to generate more globally coherent text.