NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics
This addresses the challenge of generating text under constraints for users of large language models, offering a drop-in replacement for existing decoding methods with notable improvements in complex scenarios.
The authors tackled the problem of constrained text generation with complex lexical constraints by proposing NeuroLogic A*esque, a decoding algorithm that incorporates lookahead heuristics, achieving new state-of-the-art performance on tasks like table-to-text generation and constrained machine translation.
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.