PaperlayerView exact revision on arXiv

Source-linked AI summary

Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning

Saibo Geng, Martin Josifoski, Maxime Peyrard, Robert West

arXiv:2305.13971v6cs.CLcs.AIcs.LG

TL;DR

Large language models struggle to generate reliably structured outputs, while existing grammar-constrained decoding methods cover only limited tasks. This paper generalizes GCD with formal and input-dependent grammars, and finds that few-shot grammar-constrained LMs substantially improve structured-task performance, rivaling finetuned models on some tasks.

  • Problem

    Large language models struggle with structured tasks requiring predefined formats and restricted vocabularies, especially when few demonstrations cannot convey extensive output vocabularies.

  • Method

    The paper uses formal grammars and incremental-parser completion engines to constrain pretrained LMs during decoding, including input-dependent grammars for input-conditioned output spaces.

  • Results

    Grammar-constrained few-shot LMs substantially improve structured-task performance and can rival task-specific finetuned models on closed information extraction and entity disambiguation.

  • Takeaways & Limitations

    GCD offers a unified, training-free way to obtain reliable structured outputs from pretrained LMs across a wider range of NLP tasks.

  • Takeaways & Limitations

    GCD cannot be used with cloud-hosted LMs whose APIs do not provide control over the decoding process, and constraints can increase latency for complex grammars.

Abstract

from arXiv · show

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.

1 Introduction

The paper proposes grammar-constrained decoding (GCD) as a unified way to generate valid structured NLP outputs with pretrained language models. It extends this framework with input-dependent grammars and reports strong few-shot results without finetuning.

  • Motivation: Structured tasks such as closed information extraction, entity disambiguation, and constituency parsing require predefined formats and restricted vocabularies.These requirements demand both structural coherence and vocabulary compliance, unlike free-form text generation.
  • Motivation: Few-shot LMs struggle with closed information extraction because its output vocabulary contains 2.7 million Wikidata entities and approximately 1,000 relations.The vocabulary is too large to convey through only a few demonstrations.
  • Motivation: Finetuning can support structured prediction, but it requires an expensive task-specific pipeline and bespoke training data.Prior constrained-decoding approaches instead used finite-state automata or trie-based structures for selected tasks.
  • Approach: GCD describes structured-task output spaces with formal grammars and uses an incremental parser to provide valid next-token continuations during decoding.The language model selects plausible sequences while the completion engine enforces grammatical validity.
  • Approach: Input-dependent grammars allow the valid output structure to vary with the input, extending GCD to tasks such as entity disambiguation and entity linking.The paper presents this as a broader framework than fixed constraints.
  • Results: Few-shot GCD produces remarkable improvements and can rival task-specific finetuned models without finetuning.The experiments target structured tasks where training data or finetuning resources may be limited.

2 Method

The method represents structured NLP output spaces with formal grammars and constrains autoregressive decoding through an incremental parser. It supports tokenizer-specific grammars and input-dependent output spaces while separating grammar specification from decoding implementation.

  • NLP tasks as formal languages: Formal grammars provide a unified description of output spaces for many structured NLP tasks, including 14 illustrated tasks.All 14 example grammars are context-free, mostly regular.
  • Grammar compilation: An abstract character-level grammar is automatically translated into a tokenizer-dependent token-level grammar for direct LM decoding.The token-level grammar uses the LM vocabulary as terminal symbols while preserving the character-level language.
  • Limitations: The authors identify tokenization ambiguity as a limitation and propose principled token-level grammar design as future work.Byte-pair tokenization can represent the same string in multiple ways, making spacing-based fixes tokenizer-specific.
  • Input-dependent grammars: Input-dependent grammars condition valid outputs on the input, as required for candidate-restricted entity disambiguation and input-token-preserving constituency parsing.For entity disambiguation, input-dependent constraints reduce the search space more than input-independent grammars.
  • Grammar-constrained decoding: GCD prunes the language model’s token probabilities so that only continuations allowed by the grammar remain.An incremental parser acts as a completion engine using the partial sequence and grammar to determine allowed next tokens.

3 Experimental setup

The experiments evaluate few-shot GCD on closed information extraction, entity disambiguation, and constituency parsing using pretrained LLaMA and Vicuna models without downstream finetuning. The setup uses task-specific formal grammars, input-dependent constraints where needed, and task-appropriate datasets and metrics.

  • Tasks: The study evaluates GCD on closed information extraction, entity disambiguation, and constituency parsing, three challenging few-shot structured tasks.The first two restrict outputs to predefined entities and relations, while the third requires a complex tree structure.
  • Closed information extraction: Closed information extraction maps fact-triplet sets to structured sequences whose entities and relations come from Wikidata.The grammar allows any number of triplets, including zero, with 2.7M entities and 888 relations.
  • Closed information extraction: The cIE evaluation uses SynthIE-text, comprising 10K validation samples and 50K test samples.The dataset is synthetic and is described as larger, more diverse, and higher quality than earlier REBEL data according to human ratings.
  • Entity disambiguation: Entity disambiguation outputs each mention followed by an entity selected from its input-specific candidate set in square brackets.The grammar is regular and input-dependent, and ED performance is measured with micro-accuracy across six datasets.
  • Constituency parsing: Constituency parsing uses an input-dependent grammar that reproduces input words in order while enforcing completeness, balanced brackets, and label consistency.Evaluation uses Penn Treebank test sentences with gold trees shorter than 64 tokens and reports bracketing F1.
  • Models and prompting: Experiments use LLaMA and Vicuna backbones without downstream finetuning, with LLaMA-{7B, 13B, 33B} and Vicuna-{7B, 13B} evaluated.Prompts are manually crafted from randomly selected training examples for each task.

4 Experimental results

Grammar-constrained decoding substantially improves few-shot LLM performance across closed information extraction, entity disambiguation, and constituency parsing, though parsing remains below supervised methods.

  • Grammar-constrained LLaMA and Vicuna models significantly outperform their unconstrained versions across the evaluated structured NLP tasks.The experiments cover closed information extraction, entity disambiguation, and constituency parsing.
  • LLaMA-33B with input-dependent grammars achieves the best performance among tested few-shot-prompted models on all tasks and rivals finetuned models on cIE and ED.
  • Closed information extraction (cIE): Constraining cIE generation to valid entities and relations significantly improves performance, with LLaMA-33B beating the weakly supervised GenIE T5-base model in F1-score.GenIE has higher precision, while grammar-constrained LLaMA models achieve higher F1 through a better precision–recall balance.
  • Entity disambiguation (ED): In entity disambiguation, both input-dependent and input-independent grammars improve LLaMA performance, while input-dependent grammars outperform input-independent grammars.Input-dependent grammars use an input-specific candidate set rather than the entire knowledge base.
  • Constituency parsing (CP): Grammar-constrained models improve constituency parsing over unconstrained LLaMA models, but remain below supervised methods that achieve F1-scores of 95% and above.The tested LLMs perform worse than bespoke methods, partly because their outputs are often syntactically incorrect.
  • Grammar-constrained decoding adds negligible latency for entity disambiguation and constituency parsing, while adding modest latency for closed information extraction.

5 Likelihood misalignment in GCD

The section explains why grammar-constrained decoding can favor empty outputs despite valid non-empty sequences, and describes length normalization and instruction tuning as mitigations.

  • In cIE and CP, the top generation is consistently an empty string, while subsequent generations are non-empty output sequences.This issue occurs regardless of model size and is not unique to a particular LLM.
  • The authors hypothesize that empty outputs result from likelihood misalignment between the grammar and the language model.For cIE, the model compares an immediately complete end-of-sequence output against longer generations whose likelihood can decrease as decoding proceeds.
  • Length normalization penalizes short strings through the score S/m^α, where larger α favors longer sequences.The authors report that this fix solves the empty-string problem for LLaMA-13B.
  • Instruction tuning alleviates the issue: Vicuna-13B produces non-empty top generations 46% of the time, whereas LLaMA-13B always outputs the empty string.Vicuna-7B still always outputs the empty string as its top generation.

6 Related work

Prior work applies autoregressive generation and constrained decoding to structured outputs, including parsing, code generation, semantic parsing, and meaning representations.

  • Autoregressive structured prediction in NLP: Autoregressive generative models have been used for structured prediction because this matches language-model training and strengths.Examples include dependency parsing with LSTMs and autoregressive approaches to other structured NLP tasks.
  • Constrained decoding: Constrained decoding guides generation toward valid outputs by pruning or restricting the search space according to task-specific constraints.Prior methods include lexical constraints, finite constraints, and beam-search extensions.
  • Grammar-constrained decoding: Grammar-constrained decoding has been applied to parsing, code generation, semantic parsing, and meaning-representation generation.Existing approaches use pushdown automata, grammars, or grammar-constrained decoding toolkits.

7 Conclusion

The paper presents GCD as a way to improve few-shot structured prediction with pretrained LLMs, including tasks whose valid outputs depend on the input. It also identifies practical boundaries involving task suitability, model choice, and training-data availability.

  • 7 Conclusion: GCD formulates many NLP output spaces as formal grammars and improves LLM performance on challenging structured tasks.The experiments cover closed information extraction, entity disambiguation, and constituency parsing.
  • 7 Conclusion: Input-dependent grammars broaden GCD to tasks where valid output structures are constrained by the input.This extends the framework beyond fixed output spaces.
  • Best practices for GCD: GCD is more effective with larger LLMs, so the authors recommend using the largest available model when possible.
  • Best practices for GCD: Grammars should be as restrictive as possible, with input-dependent grammars considered when appropriate.
  • Best practices for GCD: Tasks requiring syntactic understanding of the input, such as constituency parsing, are less suitable for GCD.The authors characterize GCD as broadly applicable but not a silver bullet.
  • Best practices for GCD: When task-specific training data exists, finetuning a small model may achieve better performance, though with decreased convenience.

Limitations

GCD has practical constraints involving model access, latency, and grammar construction. The framework separates human-readable abstract grammars from tokenization-dependent concrete grammars to improve portability.

  • GCD cannot be used with cloud-hosted LLM APIs that do not provide control over decoding.
  • Large grammars can substantially increase latency because incremental parsing determines allowed next tokens from the current prefix.For simple grammars, the overhead is negligible relative to LM latency; grammars with millions of rules are slower.
  • Token-level constraints make grammars dependent on each LM’s tokenization scheme, requiring separate concrete grammars and creating debugging challenges.The method addresses this by defining a tokenization-independent abstract grammar and automatically translating it into concrete grammars.
  • GF grammars separate abstract syntax from concrete syntax, with linearization rules defining strings as functions of their variables.
  • GF supports multilingual grammars with one abstract syntax and multiple concrete syntaxes, a structure that also suits different LM tokenizers.

D ED Task Settings

The entity-disambiguation experiments use few-shot prompts, restricted context, and filtered knowledge-base candidates. Evaluation uses accuracy, while constrained beam search selects the most probable non-empty output.

  • Dataset preprocessing: ED inputs retain only 10 tokens of left and right context around each entity mention.This preprocessing limits contextual information because LM performance was observed to degrade with long contexts.
  • Dataset filtering: Mentions whose target entities are absent from YAGO_KB are filtered from input-independent-grammar experiments.The appendix reports dataset-specific counts of filtered out-of-knowledge-base mentions.
  • Dataset filtering: Input-dependent-grammar experiments also remove examples with empty candidate sets.
  • Evaluation: ED performance is evaluated with micro-accuracy using the top-1 prediction.Because each mention has one target entity, accuracy, precision, recall, and F1 are equivalent in this setting.
  • Prompt construction: Prompts combine a task instruction with demonstration examples, and the better-performing prompt is selected separately for each dataset.Two prompt-construction variants are compared for ED, including entity-name and canonical-name instructions.
  • Decoding: Constrained beam search uses beam size 2 and length penalty 1.0, selecting the most probable non-empty generation.The authors report that larger beams did not improve performance and could reduce it.

G.1 Information Extraction

In information extraction, constrained decoding improves performance over unconstrained decoding across LM sizes, while subject-collapsed linearization is more compact but slightly weaker than fully expanded output.

  • Subject-collapsed linearization is more token-efficient but yields slightly lower performance than fully expanded linearization.
  • Constrained decoding significantly improves information-extraction performance over unconstrained decoding for LMs of all sizes.
  • Adding all 888 relations to the prompt provides only a small improvement over the baseline.The experiment tests whether copying relations from the prompt helps relation extraction.
  • Vicuna’s constituency-parsing performance is even worse than LLaMA’s under the reported experimental setting.

H Latency

Grammar constraints add decoding latency through incremental parsing, with the overhead depending on grammar size and parser complexity. Measurements show a small delay for WikiNER but a much larger delay for REBEL.

  • GCD latency comes from the completion step, which uses the current prefix and grammar to determine allowed next tokens.The incremental parser runs on CPU without multithreading or other optimization techniques in these measurements.
  • 0.05s latency for the WikiNER grammar is comparable to the LM’s GPU latency.The WikiNER grammar contains 279K entities and 158 relations.
  • 0.5s latency for the REBEL grammar is significantly higher than the LM’s latency.The REBEL grammar contains 5.9M entities and 857 relations.

I Error Examples of Constituency Parsing

Free-form constituency-parsing generation exposes a gap between plausible-looking outputs and structurally or linguistically correct parse trees. Instruction-tuned Vicuna-13B produces seemingly reasonable examples, while LLaMA-13B repeatedly fails to follow the instruction.

  • Free-form generation: Vicuna-13B can generate parse trees that look reasonable but are incorrect on closer inspection.One example has unbalanced bracketing, while another is a valid tree that differs from the golden parse.
  • Free-form generation: LLaMA-13B fails to follow the constituency-parsing instruction across the shown examples.The failure is reported for the PTB examples in Figures 5–9.
  • Error types: Vicuna-13B’s output for PTB instance No.29 contains missing and extra words together with incorrect bracketing.The same error pattern appears in another sampling of the instance.
  • Reference parses: The examples compare generated trees against golden PTB trees, including a long-sentence instance and shorter instances such as Nos.12 and 29.The displayed golden trees provide the reference structures for evaluating generated outputs.
Loading 2305.13971v6…