%0 Conference Proceedings %T NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics %A Lu, Ximing %A Welleck, Sean %A West, Peter %A Jiang, Liwei %A Kasai, Jungo %A Khashabi, Daniel %A Le Bras, Ronan %A Qin, Lianhui %A Yu, Youngjae %A Zellers, Rowan %A Smith, Noah A. %A Choi, Yejin %Y Carpuat, Marine %Y de Marneffe, Marie-Catherine %Y Meza Ruiz, Ivan Vladimir %S Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies %D 2022 %8 July %I Association for Computational Linguistics %C Seattle, United States %F lu-etal-2022-neurologic %X 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. %R 10.18653/v1/2022.naacl-main.57 %U https://aclanthology.org/2022.naacl-main.57 %U https://doi.org/10.18653/v1/2022.naacl-main.57 %P 780-799