Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning
Open accessAbstract
Despite their impressive performance, large language models (LMs) still struggle with reliably generating complex output structures when not finetuned to follow the required output format exactly.To address this issue, grammarconstrained decoding (GCD) can be used to control the generation of LMs, guaranteeing that the output follows a given structure.Most existing GCD methods are, however, limited to specific tasks, such as parsing or code generation.In this work, we demonstrate that formal grammars can describe the output space for a much wider range of tasks and argue that GCD can serve as a unified framework for structured NLP tasks in general.For increased flexibility, we introduce input-dependent grammars, which allow the grammar to depend on the input and thus enable the generation of different output structures for different inputs.We then empirically demonstrate the power and flexibility of GCD-enhanced LMs on (1) information extraction, (2) entity disambiguation, and (3) constituency parsing.Our results indicate that grammar-constrained LMs substantially outperform unconstrained LMs or even beat task-specific finetuned models.Grammar constraints thus hold great promise for harnessing off-the-shelf LMs for a wide range of structured NLP tasks, especially where training data is scarce or finetuning is expensive.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Token sampling is constrained to tokens consistent with at least one accepting string in the specified grammar, following Geng et al. (2023).
“We follow the procedure described in Geng et al. (2023), constraining token sampling to only select tokens that consistent with at least one accepting string in the specified grammar.”
From PARTNR: A Benchmark for Planning and Reasoning in Embodied Multi-agent Tasks (2024) · cites this paper as Geng et al. (2023)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 37 · Cited by 74
Research works printed but not linked: 26
- Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2017. Guided open vocabulary im- age captioning with constrained beam search. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 936- 945, Copenhagen, Denmark. Association for Compu- tational Linguistics. · DOI
- Krasimir Angelov. 2009. Incremental parsing with par- allel multiple context-free grammars. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009), pages 69-76, Athens, Greece. Association for Computational Linguistics.
- Ben Athiwaratkun, Cicero Nogueira dos Santos, Jason Krone, and Bing Xiang. 2020. Augmented natu- ral language for generative sequence labeling. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 375-385, Online. Association for Computa- tional Linguistics. · DOI
- Tom Ayoola, Shubhi Tyagi, Joseph Fisher, Christos Christodoulopoulos, and Andrea Pierleoni. 2022. Re- FinED: An efficient zero-shot-capable approach to end-to-end entity linking. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Track, pages 209- 220, Hybrid: Seattle, Washington + Online. Associa- tion for Computational Linguistics. · DOI
- Daniel Deutsch, Shyam Upadhyay, and Dan Roth. 2019. A general-purpose algorithm for constrained sequen- tial inference. In Proceedings of the 23rd Confer- ence on Computational Natural Language Learning (CoNLL), pages 482-492, Hong Kong, China. Asso- ciation for Computational Linguistics. · DOI
- Zhaochen Guo and Denilson Barbosa. 2017. Robust named entity disambiguation with random walks. Se- mantic Web, 9:1-21. · DOI
- Johannes Hoffart, Mohamed Amir Yosef, Ilaria Bordino, Hagen Fürstenau, Manfred Pinkal, Marc Spaniol, Bilyana Taneva, Stefan Thater, and Gerhard Weikum. 2011. Robust disambiguation of named entities in text. In Proceedings of the 2011 Conference on Em- pirical Methods in Natural Language Processing, pages 782-792, Edinburgh, Scotland, UK. Associa- tion for Computational Linguistics.
- Chris Hokamp and Qun Liu. 2017. Lexically con- strained decoding for sequence generation using grid beam search. In Proceedings of the 55th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1535-1546, Vancouver, Canada. Association for Computational Linguistics. · DOI
- J. Edward Hu, Huda Khayrallah, Ryan Culkin, Patrick Xia, Tongfei Chen, Matt Post, and Benjamin Van Durme. 2019. Improved lexically constrained decoding for translation and monolingual rewriting. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 839-850, Minneapolis, Minnesota. Association for Computa- tional Linguistics. · DOI
- Pere-Lluís Huguet Cabot and Roberto Navigli. 2021. REBEL: Relation extraction by end-to-end language generation. In Findings of the Association for Com- putational Linguistics: EMNLP 2021, pages 2370- 2381, Punta Cana, Dominican Republic. Association for Computational Linguistics. · DOI · Paper page
- Bernal Jimenez Gutierrez, Nikolas McNeal, Clayton Washington, You Chen, Lang Li, Huan Sun, and Yu Su. 2022. Thinking about GPT-3 in-context learn- ing for biomedical IE? think again. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 4497-4512, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
- Martin Josifoski, Nicola De Cao, Maxime Peyrard, Fabio Petroni, and Robert West. 2022. GenIE: Gen- erative information extraction. In Proceedings of the 2022 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, pages 4626-4643, Seattle, United States. Association for Computational Linguistics. · DOI
- Martin Josifoski, Marija Sakota, Maxime Peyrard, and Robert West. 2023. Exploiting asymmetry for syn- thetic training data generation: SynthIE and the case of information extraction. arXiv preprint arXiv:2303.04132. · arXiv
- Phong Le and Ivan Titov. 2018. Improving entity link- ing by modeling latent relations between mentions. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1595-1604, Melbourne, Aus- tralia. Association for Computational Linguistics. · DOI
- Giovanni Paolini, Ben Athiwaratkun, Jason Krone, JIE MA, Alessandro Achille, Rishita Anubhai, Ci- cero Nogueira dos Santos, Bing Xiang, and Stefano Soatto. 2021. Structured prediction as translation be- tween augmented natural languages. In ICLR 2021.
- Matt Post and David Vilar. 2018. Fast lexically con- strained decoding with dynamic beam allocation for neural machine translation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, Volume 1 (Long Pa- pers), pages 1314-1324, New Orleans, Louisiana. Association for Computational Linguistics. · DOI
- Aarne Ranta. 2019. Grammatical framework: an inter- lingual grammar formalism. In Proceedings of the 14th International Conference on Finite-State Meth- ods and Natural Language Processing, pages 1-2, Dresden, Germany. Association for Computational Linguistics. · DOI
- Timo Schick and Hinrich Schütze. 2021. Exploiting cloze-questions for few-shot text classification and natural language inference. In Proceedings of the 16th Conference of the European Chapter of the Asso- ciation for Computational Linguistics: Main Volume, pages 255-269, Online. Association for Computa- tional Linguistics. pages 9895-9901, Online and Punta Cana, Domini- can Republic. Association for Computational Lin- guistics. · DOI · Paper page
- Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. 1991. On multiple context-free gram- mars. Theoretical Computer Science, 88(2):191-229. · DOI
- Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pages 1715-1725, Berlin, Germany. Association for Computational Lin- guistics. · DOI · Paper page
- Felix Stahlberg and Bill Byrne. 2019. On NMT search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Lan- guage Processing (EMNLP-IJCNLP), pages 3356- 3362, Hong Kong, China. Association for Computa- tional Linguistics. · DOI · Paper page
- Roy Tromble and Jason Eisner. 2006. A fast finite-state relaxation method for enforcing global constraints on sequence decoding. In Proceedings of the Hu- man Language Technology Conference of the NAACL, Main Conference, pages 423-430, New York City, USA. Association for Computational Linguistics.
- Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015b. Gram- mar as a foreign language. In Advances in Neural Information Processing Systems, volume 28.
- Curran Associates, Inc. Denny Vrandečić. 2012. Wikidata: A new platform for collaborative data collection. In Proceedings of the 21st International Conference on World Wide Web, WWW '12 Companion, pages 1063-1064, New York, NY, USA. Association for Computing Machinery. · DOI
- Ledell Wu, Fabio Petroni, Martin Josifoski, Sebastian Riedel, and Luke Zettlemoyer. 2020. Scalable zero- shot entity linking with dense entity retrieval. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6397-6407, Online. Association for Computa- tional Linguistics. · DOI
- Yu Zhang, Houquan Zhou, and Zhenghua Li. 2020. Fast and accurate neural CRF constituency parsing. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organi- zation. · DOI
- Authors
- Geng, S., Josifoski, M., Peyrard, M., & West, R.
- Affiliations
- Institut polytechnique de Grenoble (FR)
- Venue
- Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing
- Published
- 2023
- Pages
- 10932-10952
- OpenAlex
- W4389520385
- Cited by
- 74
- References
- 37
- Citations by year
- 2026: 42 · 2025: 26 · 2024: 6
- FWCI
- 13.11
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- Locations
- Conference on Empirical Methods in Natural Language Processing (EMNLP) (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion, cc-by)
- HAL (submittedVersion, other-oa)
- arXiv (Cornell University) (cc-by)
- Funders
- National Science Foundation
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (185043)
- Horizon 2020 Framework Programme (952215)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Speech and dialogue systems
- Keywords
- formal grammars, large language models, structured output generation, information extraction, entity disambiguation, constituency parsing, limited training data
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
