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

Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 780 - 799 July 10-15, 2022 ©2022 Association for Computational Linguistics 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†‡ ‡Allen Institute for Artificial Intelligence †Paul G. Allen School of Computer Science & Engineering, University of Washington Abstract The dominant paradigm for neural text gen- eration is left-to-right decoding from autore- gressive language models. Constrained or con- trollable generation under complex lexical con- straints, however, requires foresight to plan ahead for feasible future paths. Drawing inspiration from the A* search algo- rithm, we propose NEUROLOGIC A⋆esque,1 a decoding algorithm that incorporates heuris- tic estimates of future cost. We develop looka- head 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 en- able constrained generation, we build on NEU- ROLOGIC decoding (Lu et al., 2021), combin- ing its flexibility in incorporating logical con- straints with A⋆esque estimates of future con- straint satisfaction. Our approach outperforms competitive base- lines on five generation tasks, and achieves new state-of-the-art performance on table-to- text generation, constrained machine trans- lation, and keyword-constrained generation. The improvements are particularly notable on tasks that require complex constraint satisfac- tion or in few-shot or zero-shot settings. NEU- ROLOGIC A⋆esque illustrates the power of de- coding for improving and enabling new capa- bilities of large-scale language models. 1 Introduction The dominant paradigm for neural text genera- tion is based on left-to-right decoding from au- toregressive language models such as GPT-2/3 (Radford et al., 2019; Brown et al., 2020). Un- der this paradigm, common decoding techniques such as beam search or top-k/p sampling (Holtz- man et al., 2020) determine which token to generate next based on what happened in the past, without explicitly looking ahead into the future. While 1Pronounced [ey stAr Esk]. summer on the road winter through the snow ✓ ✗ I drive my car during the Write a sentence with these concepts car drive snow p(w|past) = 0.4 A★ p(w|past) = 0.2 Figure 1: NEUROLOGIC⋆ leverages lookahead heuris- tics 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 win- ter results in a generation that incorporates unsatis- fied constraint snow with a higher probability later on. Thus, winter is preferred despite being lower probabil- ity than summer. this lack of foresight often suffices for open-ended text generation – where any coherent text can be acceptable – for constrained text generation, plan- ning ahead is crucial for incorporating all desired content in the generated output (Hu et al., 2017; Dathathri et al., 2019). Classical search algorithms such as A* …

Content truncated to 500 words