---
title: "NeuroLogic Decoding — paper by Lu et al. (2021)"
description: "The authors introduce NeuroLogic Decoding, an inference-time algorithm that works with supervised… 30 references, cited by 46 papers here."
authors: ["Ximing Lu", "Peter West", "Rowan Zellers", "Ronan Le Bras", "Chandra Bhagavatula", "Yejin Choi"]
year: 2021
venue: "Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies"
source: "https://aclanthology.org/2021.naacl-main.339/"
doi: "10.18653/v1/2021.naacl-main.339"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/lu-2021-neurologic-decoding-un-supervised-neural/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/lu-2021-neurologic-decoding-un-supervised-neural/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2021](https://md.research.elamur.ai/free/en/papers/2021/page/4/) / NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints

# NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints

**Authors:** [Ximing Lu](https://md.research.elamur.ai/free/en/authors/ximing-lu/), [Peter West](https://md.research.elamur.ai/free/en/authors/peter-west/), [Rowan Zellers](https://md.research.elamur.ai/free/en/authors/rowan-zellers/), [Ronan Le Bras](https://md.research.elamur.ai/free/en/authors/ronan-le-bras/), [Chandra Bhagavatula](https://md.research.elamur.ai/free/en/authors/chandra-bhagavatula/) and [Yejin Choi](https://md.research.elamur.ai/free/en/authors/yejin-choi/) · **Year:** 2021 · **Venue:** [Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies](https://md.research.elamur.ai/free/en/venues/naacl/) ([NAACL 2021](https://md.research.elamur.ai/free/en/venues/naacl/2021/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2021.naacl-main.339/) · [PDF](https://aclanthology.org/2021.naacl-main.339.pdf) · [DOI 10.18653/v1/2021.naacl-main.339](https://doi.org/10.18653/v1/2021.naacl-main.339) · [OpenAlex](https://openalex.org/W3171218751)

**Citations:** 60 citations (OpenAlex, 2026-10-14) · [46](https://md.research.elamur.ai/free/en/papers/lu-2021-neurologic-decoding-un-supervised-neural/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Large pretrained language models finetuned on task data still often ignore lexical constraints. A recipe generator, for example, may skip listed ingredients or invent new ones, and adding much more finetuning data barely helps. The authors introduce NeuroLogic Decoding, an inference-time algorithm that works with supervised or unsupervised models without changing their architecture or training. Constraints are written as predicate logic formulas in Conjunctive Normal Form. These formulas combine required and forbidden phrases with AND/OR, which also covers synonyms and inflections. The hard constraints are turned into a soft penalty in the decoding objective. A modified beam search then approximately optimizes this objective: it prunes candidates, groups them by which clauses they have permanently satisfied, and selects the best from each group. Clause states are tracked with prefix tries. The asymptotic runtime equals that of ordinary beam search. The method was tested on four tasks (COMMONGEN, recipe generation, data-grounded dialogue and gender-bias reduction in MT) and reached new state-of-the-art results. Unsupervised models using it often outperform larger supervised models with standard decoding, which points to inference-time control as a strong alternative to scaling.

## Key points
- Each clause is in one of four states (reversibly or irreversibly unsatisfied or satisfied). Two prefix tries (T+ and T−) track the open literals. The top-α (likelihood) and top-β (satisfied clauses) thresholds control the trade-off between fluency and constraint coverage.
- Zero-shot GPT-2 with NeuroLogic matches or beats finetuned GPT-2, BART and T5 on dialogue response generation. This uses the hotel/restaurant corpus of Wen et al. (2016), with 8 query types and 12 attribute types.
- On WinoMT (built from Winogender and WinoBias), the method raises gender accuracy of the Junczys-Dowmunt et al. model:
  - En-De: from 60.5% to 91.0%, ahead of the best commercial system (Microsoft Translator, 74.1%).
  - En-Fr: from 53.0% to 81.0%.
- With ground-truth gender, accuracy rises further to 95.0% (En-De) and 89.9% (En-Fr). The stereotype gap ∆S falls sharply, for example from 19.3 to 1.7 for En-Fr. Gender markers by default come from a RoBERTa coreference model finetuned on the Winograd Schema Challenge (78.4% accuracy).

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of Washington](https://md.research.elamur.ai/free/en/universities/university-of-washington/) — University, Seattle, United States · 263 works · 180,581 citations
- [Allen Institute for Artificial Intelligence](https://md.research.elamur.ai/free/en/labs/allen-institute-for-artificial-intelligence/) — Research institute, Seattle, United States · 219 works · 89,712 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

🧭 Topics (1): [✍️ Text generation](https://md.research.elamur.ai/free/en/topics/text-generation/) · 145 works

## Cite

Cite as: Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula and Yejin Choi. 2021. NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{lu2021neurologic,
  title = {{NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints}},
  author = {Ximing Lu, Peter West, Rowan Zellers, Ronan {Le Bras}, Chandra Bhagavatula and Yejin Choi},
  booktitle = {Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2021},
  doi = {10.18653/v1/2021.naacl-main.339},
  url = {https://doi.org/10.18653/v1/2021.naacl-main.339}
}
```

- [← previous Common Sense Beyond English: Evaluating and Improving Multilingual Language Models for Commonsense Reasoning](https://md.research.elamur.ai/free/en/papers/lin-2021-common-sense-beyond-english-evaluating/)
- [next → A Survey of Code-switching: Linguistic and Social Perspectives for Language Technologies](https://md.research.elamur.ai/free/en/papers/dogruoz-2021-survey-code-switching-linguistic-social/)
- [↑ back to papers of 2021](https://md.research.elamur.ai/free/en/papers/2021/page/4/)

## References

30 references, 19 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2017. [Guided open vocabulary image captioning with constrained beam search](https://md.research.elamur.ai/free/en/papers/anderson-2017-guided-open-vocabulary-image-captioning/). In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 936–945, Copenhagen, Denmark. Association for Computational L…
2. Anusha Balakrishnan, Jinfeng Rao, Kartikeya Upasani, Michael White, and Rajen Subba. 2019. [Constrained decoding for neural NLG from compositional representations in task-oriented dialogue](https://md.research.elamur.ai/free/en/papers/balakrishnan-2019-constrained-decoding-neural-nlg-compositional/). In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 831– 844, Flo…
3. Hangbo Bao, Li Dong, Furu Wei, Wenhui Wang, Nan Yang, Xiaodong Liu, Yu Wang, Songhao Piao, Jianfeng Gao, Ming Zhou, and Hsiao-Wuen Hon. 2020. [Unilmv2: Pseudo-masked language models for unified language model pre-training](https://md.research.elamur.ai/free/en/papers/bao-2020-unilmv2-pseudo-masked-language-models/).
4. Georgiana Dinu, Prashant Mathur, Marcello Federico, and Yaser Al-Onaizan. 2019. [Training neural machine translation to apply terminology constraints](https://md.research.elamur.ai/free/en/papers/dinu-2019-training-neural-machine-translation-apply/). In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3063–3068, Florence, Italy. Association for Computat…
5. Li Dong, Nan Yang, Wenhui Wang, Furu Wei, Xiaodong Liu, Yu Wang, Jianfeng Gao, Ming Zhou, and Hsiao-Wuen Hon. 2019. [Unified language model pre-training for natural language understanding and generation](https://md.research.elamur.ai/free/en/papers/dong-2019-unified-language-model-pre-training/). In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Ad…
6. A. Fiacco. 1976. Sensitivity analysis for nonlinear programming using penalty methods. Mathematical Programming, 10:287–311. [find](https://scholar.google.com/scholar?q=A%2E+Fiacco%2E+1976%2E+Sensitivity+analysis+for+nonlinear+programming+using+penalty+methods%2E+Mathematical+Programming%2C+10%3A287%E2%80%93311%2E)
7. Eva Hasler, Adrià de Gispert, Gonzalo Iglesias, and Bill Byrne. 2018. [Neural machine translation decoding with terminology constraints](https://md.research.elamur.ai/free/en/papers/hasler-2018-neural-machine-translation-decoding-terminology/). In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short P…
8. Chris Hokamp and Qun Liu. 2017. [Lexically constrained decoding for sequence generation using grid beam search](https://md.research.elamur.ai/free/en/papers/hokamp-2017-lexically-constrained-decoding-sequence-generation/). In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1535–1546, Vancouver, Canada. Association for Computational Linguis…
9. J. Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019a. [Improved lexically constrained decoding for translation and monolingual rewriting](https://md.research.elamur.ai/free/en/papers/hu-2019-improved-lexically-constrained-decoding-translation/). In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational…
10. J. Edward Hu, Rachel Rudinger, Matt Post, and Benjamin Van Durme. 2019b. Parabank: Monolingual bitext generation and sentential paraphrasing via lexically-constrained neural machine translation. In AAAI. [find](https://scholar.google.com/scholar?q=J%2E+Edward+Hu%2C+Rachel+Rudinger%2C+Matt+Post%2C+and+Benjamin+Van+Durme%2E+2019b%2E+Parabank%3A+Monolingual+bitext+generation+and+sentential+paraphrasing+via+lexically%2Dconstrained+neural+machine+translation%2E+In+AA)
11. Marcin Junczys-Dowmunt, Roman Grundkiewicz, Tomasz Dwojak, Hieu Hoang, Kenneth Heafield, Tom Neckermann, Frank Seide, Ulrich Germann, Alham Fikri Aji, Nikolay Bogoychev, André F. T. Martins, and Alexandra Birch. 2018. [Marian: Fast neural machine translation in C++](https://md.research.elamur.ai/free/en/papers/junczys-dowmunt-2018-marian-fast-neural-machine-translation/). In Proceedings of ACL 2018, System…
12. Tomoyuki Kajiwara. 2019. Negative lexically constrained decoding for paraphrase generation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 6047– 6052, Florence, Italy. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Tomoyuki+Kajiwara%2E+2019%2E+Negative+lexically+constrained+decoding+for+paraphrase+generation%2E+In+Proceedings+of+the+57th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+6047%E2%80%93+6052)
13. Chloé Kiddon, Luke Zettlemoyer, and Yejin Choi. 2016. [Globally coherent text generation with neural checklist models](https://md.research.elamur.ai/free/en/papers/kiddon-2016-globally-coherent-text-generation-neural/). In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 329–339, Austin, Texas. Association for Computational Linguistics.
14. Jonathan Krause, Benjamin Sapp, Andrew Howard, Howard Zhou, Alexander Toshev, Tom Duerig, James Philbin, and Li Fei-Fei. 2016. The unreasonable effectiveness of noisy data for fine-grained recognition. ArXiv, abs/1511.06789. — [arXiv:1511.06789](https://arxiv.org/abs/1511.06789) [find](https://scholar.google.com/scholar?q=Jonathan+Krause%2C+Benjamin+Sapp%2C+Andrew+Howard%2C+Howard+Zhou%2C+Alexander+Toshev%2C+Tom+Duerig%2C+James+Philbin%2C+and+Li+Fei%2DFei%2E+2016%2E+The+unreasonable+effectiveness+of+noisy+data+for+fine%2Dgrained+recognition)
15. H. Lee, Shu Ke, Palakorn Achananuparp, P. K. Prasetyo, Y. Liu, E. Lim, and L. R. Varshney. 2020. Recipegpt: Generative pre-training based cooking recipe generation and evaluation system. Companion Proceedings of the Web Conference 2020. [find](https://scholar.google.com/scholar?q=H%2E+Lee%2C+Shu+Ke%2C+Palakorn+Achananuparp%2C+P%2E+K%2E+Prasetyo%2C+Y%2E+Liu%2C+E%2E+Lim%2C+and+L%2E+R%2E+Varshney%2E+2020%2E+Recipegpt%3A+Generative+pre%2Dtraining+based+cooking+recipe+generation+and+evaluation+system%2E+Companion+Pro)
16. Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020. [BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension](https://md.research.elamur.ai/free/en/papers/lewis-2020-bart-denoising-sequence-sequence-pre/). In Proceedings of the 58th Annual Meeting of the…
17. Huayang Li, Guoping Huang, and Lemao Liu. 2019. Neural machine translation with noisy lexical constraints. [find](https://scholar.google.com/scholar?q=Huayang+Li%2C+Guoping+Huang%2C+and+Lemao+Liu%2E+2019%2E+Neural+machine+translation+with+noisy+lexical+constraints%2E)
18. Bill Yuchen Lin, Ming Shen, Wangchunshu Zhou, Pei Zhou, Chandra Bhagavatula, Yejin Choi, and Xiang Ren. 2020. Commongen: A constrained text generation challenge for generative commonsense reasoning. In Findings of EMNLP. [find](https://scholar.google.com/scholar?q=Bill+Yuchen+Lin%2C+Ming+Shen%2C+Wangchunshu+Zhou%2C+Pei+Zhou%2C+Chandra+Bhagavatula%2C+Yejin+Choi%2C+and+Xiang+Ren%2E+2020%2E+Commongen%3A+A+constrained+text+generation+challenge+for+generative+commonsense+reasoning%2E+I)
19. Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. 2019. Cgmh: Constrained sentence generation by metropolis-hastings sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 6834–6842. [find](https://scholar.google.com/scholar?q=Ning+Miao%2C+Hao+Zhou%2C+Lili+Mou%2C+Rui+Yan%2C+and+Lei+Li%2E+2019%2E+Cgmh%3A+Constrained+sentence+generation+by+metropolis%2Dhastings+sampling%2E+In+Proceedings+of+the+AAAI+Conference+on+Artificial+Intelligence%2C+volum)
20. Matt Post and David Vilar. 2018. [Fast lexically constrained decoding with dynamic beam allocation for neural machine translation](https://md.research.elamur.ai/free/en/papers/post-2018-fast-lexically-constrained-decoding-dynamic/). In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers),…
21. Tsung-Hsien Wen, Milica Gašić, Nikola Mrkšić, Lina M. Rojas-Barahona, Pei-Hao Su, David Vandyke, and Steve Young. 2016. [Multi-domain neural network language generation for spoken dialogue systems](https://md.research.elamur.ai/free/en/papers/wen-2016-multi-domain-neural-network-language/). In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computatio…
22. Tsung-Hsien Wen, Milica Gašić, Nikola Mrkšić, Pei-Hao Su, David Vandyke, and Steve Young. 2015. [Semantically conditioned LSTM-based natural language generation for spoken dialogue systems](https://md.research.elamur.ai/free/en/papers/wen-2015-semantically-conditioned-lstm-based-natural/). In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1711–1721, L…
23. Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018. [Gender bias in coreference resolution: Evaluation and debiasing methods](https://md.research.elamur.ai/free/en/papers/zhao-2018-gender-bias-coreference-resolution-evaluation/). In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,…
24. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019. Language models are unsupervised multitask learners. OpenAI Blog, 1(8):9. [find](https://scholar.google.com/scholar?q=Alec+Radford%2C+Jeffrey+Wu%2C+Rewon+Child%2C+David+Luan%2C+Dario+Amodei%2C+and+Ilya+Sutskever%2E+2019%2E+Language+models+are+unsupervised+multitask+learners%2E+OpenAI+Blog%2C+1%288%29%3A9%2E)
25. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019. [Exploring the limits of transfer learning with a unified text-to-text transformer](https://md.research.elamur.ai/free/en/papers/raffel-2019-exploring-limits-transfer-learning-unified/). ArXiv, abs/1910.10683.
26. Shaoqing Ren, Kaiming He, Ross B. Girshick, and Jian Sun. 2015. [Faster r-cnn: Towards real-time object detection with region proposal networks](https://md.research.elamur.ai/free/en/papers/ren-2015-faster-r-cnn-towards-real/). IEEE Transactions on Pattern Analysis and Machine Intelligence, 39:1137–1149.
27. Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme. 2018. [Gender bias in coreference resolution](https://md.research.elamur.ai/free/en/papers/rudinger-2018-gender-bias-coreference-resolution/). In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 8–1…
28. Lei Sha. 2020. Gradient-guided unsupervised lexically constrained text generation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8692–8703, Online. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Lei+Sha%2E+2020%2E+Gradient%2Dguided+unsupervised+lexically+constrained+text+generation%2E+In+Proceedings+of+the+2020+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%29%2C+pages+8692%E2%80%938703%2C+O)
29. Gabriel Stanovsky, Noah A. Smith, and Luke Zettlemoyer. 2019. [Evaluating gender bias in machine translation](https://md.research.elamur.ai/free/en/papers/stanovsky-2019-evaluating-gender-bias-machine-translation/). In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1679–1684, Florence, Italy. Association for Computational Linguistics.
30. Concept-Set {lose, board, balance, fall, ride} Supervised Setting [find](https://scholar.google.com/scholar?q=Concept%2DSet+%7Blose%2C+board%2C+balance%2C+fall%2C+ride%7D+Supervised+Setting)

*Updated 24 October 2026*