Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning (2023)

Abstract: 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, grammar-constrained 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. Code and data: https://github.com/epfl-dlab/GCD.

## introduction pretrained language models (lms) have achieved impressive results across a range of tasks, such as machine translation, summarization, and dialogue generation @xcite . all of these models are pretrained on nexttoken prediction task, encouraging researchers to cast other nlp tasks in the same autoregressive generation framework. by framing tasks as autoregressive generation, pretrained language models * work done while at epfl. certain important tasks, however, such as closed information extraction (cie), entity disambiguation (ed), or constituency parsing (cp), require the output to follow a predefined format and adhere to a restricted vocabulary (entities, relations, senses, dependency labels, etc.). whereas lms excel at generating free-form text, they are not specifically designed for structured prediction tasks where only a small subset of the output space is valid. consequently, structured prediction tasks present unique challenges because constrained output spaces demand both structural coherence and compliance with a predefined vocabulary. for instance, @xcite have demonstrated that few-shotprompted large language models such as gpt-3.5 struggle with tasks such as cie. this difficulty is primarily due to the extensive output vocabulary, which includes 2.7 million wikidata entity names and approximately 1,000 wikidata relation names, which is too vast to be conveyed with just a few demonstration examples. one way forward is to finetune lms for specific tasks, which involves linearizing the desired output format into a string format, thus enabling training through standard next-token prediction. for instance, de @xcite and @xcite successfully applied this technique to ed and cie, respectively. however, this approach has limitations: it necessitates an expensive finetuning pipeline for each new task, which lacks flexibility and requires bespoke training data. orthogonally, constrained decoding @xcite is a technique that can be used to enforce constraints on the output space of an autoregressive language model during inference. constrained decoding has been used in semantic role labeling @xcite , constituency parsing @xcite , code generation @xcite , and entity disambiguation @xcite . the constraints have been expressed in the form of finite-state automata @xcite or trie-based data structures for fast lookup @xcite . in this work, we show that, for a much wider range of nlp tasks, the respective output space can be described with a formal grammar, giving rise to a unified framework for structured nlp tasks. given an appropriately defined grammar, we use an incremental parser to play the role of a completion engine, which determines the set of valid next tokens given the current prefix. we integrate this completion engine with a pretrained language model to iteratively generate sequences that are valid according to the grammar and plausible according to the lm (cf. fig. 1 ). from a practical perspective, the grammar-constrained decoding (gcd) framework allows researchers to focus on writing the grammar while ignoring the implementation details of the constrained decoding process. this is in contrast to previous work, where the constraints were expressed in the form of finite-state automata or trie-based data structures, which require a significant engineering effort to implement. we envision gcd to be as simple to use as regular expressions, in the sense that the user can specify a desired output structure in a declarative way, and the lm-generated sequences will be guaranteed to be valid. with the introduction of input-dependent grammars, the scope of tasks that can be tackled with gcd can be further extended to tasks such as entity disambiguation and entity linking, where the output space is not fixed but depends on the input. we show that, by combining gcd with powerful llms, we achieve remarkable improvements with few-shot learning, even rivaling the performance of finetuned task-specific models. this is particularly exciting because it shows that lms can be used to solve a much wider range of structured tasks than before, without the need for finetuning. our contributions can be summarized as follows: ## method we now describe gcd and how it can constrain the output of lms at decoding time based on a formal grammar. we first explain how to specify the output spaces of various nlp tasks via formal grammars. then we show how an incremental parser can be used as a completion engine to constrain the lm's generation process to produce grammatically valid outputs only. ); c i, @xmath3, . . . , x n-1 ⟩ are sequences of lexical units (e.g., words); 0 ≤ @xmath4; single capital letters are non-terminal symbols; s or s 0 is the start symbol; ε is the empty string; [ and ] are special terminal symbols. ## experimental setup although gcd can be applied to many tasks, we concentrate on three tasks in order to showcase its effectiveness: closed information extraction (cie), entity disambiguation (ed), and constituency parsing (cp). the first two tasks are examples where the output is restricted to a predefined set of entities and relations, while the third is an example of a task where the output is a complex tree structure. all three tasks are challenging for llms in the few-shot setting, and we show that gcd can significantly improve llm performance. ## experimental results next, we present the results for each task, showing that, whereas the unconstrained llama and vicuna models perform poorly, the grammarconstrained versions perform significantly better. we also show input-dependent grammars to be crucial for performance, as they allow the models to adapt to the input and generate more accurate outputs. out of the tested few-shot-prompted models, llama-33b with input-dependent grammars achieves the best performance on all tasks, even rivaling finetuned models on cie and ed. ## likelihood misalignment in gcd in the cie and cp tasks, regardless of model size, the top generation is consistently an empty string (technically, a string "@xmath0". the latter denotes the situation where no triplets can be extracted from the input. with a beam size @xmath5, both "[" and "@xmath1" is q. since "@xmath2", resulting in the latter being returned as the top generation. this intuition gives rise to a simple fix: penalize the model for generating short strings, e.g., by adjusting the length normalization parameter α in the length-adjusted sentence score s/m α , where s is the unadjusted score for the sentence and m is the number of tokens in the sentence. as shown in we also observed that the empty-string issue can be alleviated by using instruction-tuned models. while, without applying the aforementioned length normalization fix, llama-13b always outputs the length normalization α 1.0 1.5 2.0 2.5 3.0 3.5 top @xmath6 autoregressive structured prediction in nlp. it has become popular to use autoregressive generative models for structured prediction tasks, as this fits the training mode and specific strengths of language models @xcite @xcite . for instance, vinyals et al. (2015b) modeled dependency parsing as a sequence generation problem and leveraged lstms to tackle it effectively. de cao et al. (2021) proposed autoregressive language models to address entity linking, entity disambiguation, and document retrieval tasks. constrained decoding. for tasks where the output needs to satisfy certain constraints, constrained decoding has been proposed to guide the generation process to produce valid outputs. for instance, hokamp and liu (2017); hu et al. (2019); post and vilar (2018) proposed lexically-constrained sequence decoding for generation tasks. anderson et al. (2017) extended the beam search algorithm by pruning the search space based on constraints. scholak et al. (2021) leveraged an incremental parsing technique to generate approximately valid sql queries. de cao et al. (2021) addressed entity disambiguation with trie-based lexical constraints at decoding time to force outputs to be valid entities. josifoski et al. (2022) addressed closed information extraction by combining trie-based lexical constraints with state-based constraints to force the output to be valid triplet sequences. wang et al. (2023) used earley parser-based constraints to force outputs to lie in a domain-specific language. grammar-constrained decoding. deutsch et al. (2019) proposed a general framework for pushdown automata-based constraints and applied it to parsing tasks, which is equivalent to cfg-based constraints in terms of expressiveness. yin and neubig (2017) proposed a grammar-powered neural architecture for general-purpose code generation. shin et al. (2021) proposed to use grammarconstraints to solve semantic parsing tasks with gpt-3 and envisioned that a semantic parser can be built by combining a large language model with a carefully designed grammar. roy et al. (2022) released a toolkit for grammar-constrained decoding to generate valid meaning representations. finally, stengel-eskin et al. (2023) tested the ability of llms to solve parsing task under ambiguity and used grammar constraints to ensure the grammaticality of the output. ## conclusion this work introduces grammar-constrained decoding (gcd) for enhancing the few-shot performance of llms on challenging structured nlp tasks. we showed that many nlp tasks can be formulated as formal grammars, and that gcd can enhance the performance of llms on these tasks. with inputdependent grammars, we further broaden the scope of gcd to accommodate tasks where the set of valid output structures is constrained by the given input. our experiments indicate that, whereas unconstrained llms have difficulty tackling tasks requiring structured outputs, gcd can significantly bolster the performance of llms on such tasks. we envision gcd as a swift and cost-efficient adaptation strategy, allowing llms to generate reliable structured outputs without the necessity for costly and cumbersome finetuning. given the fast pace of llm evolution, we anticipate the usefulness of gcd for boosting pretrained llms to further increase over time. best practices for gcd. we conclude with considerations regarding the effective use of gcd.