Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning

Language models generate text one token at a time, choosing from their whole vocabulary at every step. That is fine for prose and a problem for structure. Ask a model to list facts using only entities from Wikidata and it will write a plausible name that is not in Wikidata. Ask it for a parse tree and the brackets may not balance. The usual fixes were fine-tuning a model per task or validating after the fact and retrying.

The EPFL team used grammar-constrained decoding instead. You write a formal grammar describing every valid output. At each step, an incremental parser looks at what has been generated so far and returns the set of tokens that could still lead to a valid output. Every other token is masked before the model chooses. The output is valid by construction.

Their contribution is showing how general this is and adding one idea: input-dependent grammars. Instead of one grammar for all inputs, build the grammar from the input, for example listing only the candidate entities for this particular mention. With four examples in the prompt and no fine-tuning, LLaMA models improved sharply on closed information extraction and entity disambiguation, and LLaMA-33B beat a purpose-built extractor on extraction F1. On constituency parsing, constraints guaranteed 100% valid trees, though accuracy stayed far below dedicated parsers.

They also found a problem nobody had described: under constraints, the model's highest-scoring output was often the empty string.

Most enterprise LLM work ends in structure: extracted fields that go into a database, function calls with typed arguments, JSON consumed by another service. Hosted APIs now offer "structured outputs" that constrain generation to a JSON Schema, and open-source servers support grammars. This paper explains what those features do and what they cannot do.

Valid is not correct. The constituency parsing results make the point starkly: constraints produced valid parse trees every time, and the trees were right about 55% of the time by F1, against 95% for supervised parsers. A schema guarantees that a field called amount contains a number. It does not guarantee that it is the right number. Your evaluation still has to check content.

Constrain to the input, not just the type. The biggest gains came from building the grammar from the input. Entity linking jumped from 68.2% with one grammar for all inputs to 80.3% when each input got its own candidate list. On a deployment, that means enums of the customer's actual product codes, account IDs from the record being processed, or the list of valid statuses for this workflow, rather than "any string".

Watch for valid but empty. If the schema allows an empty list or optional fields, constrained decoding can prefer the empty answer, because forcing the model through an unnatural structure lowers the probability of every full answer. The paper's fix is a decoding setting; the deployment fix is to monitor the rate of empty outputs.