Growing the Grammar While Decoding: Lazy Ontology Constraints for Domain Language Models

A domain language model, such as one trained further on biomedical abstracts, knows the vocabulary of its field but still produces structured outputs that are invalid. Examples are a clinical concept expression that pairs an attribute with a value the ontology forbids, or a logical formula that uses a predicate that does not exist. The standard fix is to compile the output grammar into an automaton and, at each step, mask every token the grammar disallows. That works when the grammar is small. It fails when the grammar comes from a large, changing ontology, because writing out every concrete rule ahead of time produces a combinatorial number of productions. Older parsing and machine translation research met this "rule explosion" decades ago and solved it with lazy expansion: build only the rules the current input actually reaches. This note proposes bringing that idea into neural decoding. The decoder's partial parse determines which ontology rules to fetch. The allowed-token mask is built from those rules on the fly. The domain model is trained with that lazily built mask active, so it learns to spread its probability over valid continuations only.

The central question is empirical and has two parts. Do lazily retrieved grammar constraints and domain pre-training fix different failures, validity for the first and semantic choice for the second, so that their gains add? And does lazy retrieval make three things possible that a static grammar cannot: validity guarantees at the scale of a full ontology, new rules usable without retraining, and cost that grows with the rules actually used rather than with the size of the ontology?

Core Claim

When a domain's output grammar is induced by an ontology, the grammar should be treated as an index that the decoder queries, not as an automaton compiled in advance. The query key is the parser's current state: the nonterminal on top of the stack plus the ontology context it carries, for example "attribute slot under a procedure concept". The index returns only the productions valid in that state. These are turned into a prefix tree over characters and intersected with the tokenizer's vocabulary to give the mask for the next token.

The second claim is that the model must be trained under this mask, not just decoded with it. Training under the mask means the language-modeling loss is renormalized over the allowed set:

$$\mathcal{L} = -\sum_t \log \frac{p_\theta(y_t \mid y_{<t})}{\sum_{v \in A_t} p_\theta(v \mid y_{<t})}$$

Here $y_t$ is the gold token at step $t$, $p_\theta$ is the model's next-token distribution, and $A_t$ is the set of tokens the lazily built grammar allows at that step. Masking only at test time forces the model to renormalize a distribution it learned without constraints. We expect that to distort choices among valid options. That distortion is the "valid but incorrect" failure reported for GRAMMAR-LLM.

Relation to Prior Work

Three recent papers come closest. Each leaves one piece fixed that we make dynamic.

GRAMMAR-LLM masks logits with a deterministic pushdown automaton, a stack-based recognizer. It compiles an "LL(prefix)" grammar class designed so that rules sharing subword prefixes still parse cleanly, and it reaches 100% validity on Web of Science hierarchical classification, sign-language gloss, and meaning-representation parsing. Its schema is static, pre-compiled per task, and applied only at inference. We reuse its prefix-tolerant grammar class, because it solves the subword-tokenizer mismatch. We replace its static compilation with lazy retrieval and add training under the constraint.

Grammar Prompting has a frozen general model first write the minimal grammar for an input, then generate conditioned on that grammar. This is lazy in spirit, but the model predicts the rules itself, so a rule it invents or omits breaks the output. The authors also report smaller gains for languages the model already knows from pre-training. Our rules come from an authoritative index, not from the model.

RING folds retrieval into a trainable memory expert and emits internal retrieval blocks. It works on unstructured news text, gives no validity guarantee, and needs another round of continued pre-training, supervised tuning, and reinforcement learning to absorb new knowledge. We keep the rules outside the weights so they can be edited.

The mechanism comes from classical lazy-expansion work. Dynamic Compilation of Weighted Context-Free Grammars expands grammar-derived automata on demand and handles grammar changes without full recompilation. Efficient Inference through Cascades of Weighted Tree Transducers generates productions lazily during search. Small Is Beautiful derives regular-tree-grammar rules on demand over SNOMED CT, GALEN and NCIT, reporting about eight orders of magnitude fewer applied rules than a static approach. That last result is our evidence that ontology-induced grammars do explode, and it gives us the rule representation.

Two lines of work constrain the design. On-demand rule extraction in machine translation (Baltescu and Blunsom; He, Lin and Lopez) found that once extraction is fast, the bottleneck moves to scoring, and that per-sentence latency suffers from transfer overhead. We therefore report per-token latency, not only batch throughput, and cache rule sets by parser state. RuleReasoner trains reasoning models with rules placed in the prompt. It had to shuffle rule order to fight position memorization, and it notes degradation when long or distracting rule lists are present. This argues against simply pasting retrieved rules into context.

The domain side motivates why pre-training should matter even under a constraint. The PEFT comparison on CoNaLa found that exposure to code during pre-training predicted code-generation quality better than any fine-tuning method did. MonoCoder showed that a small single-domain model competes with much larger general ones. BioBART showed that continued pre-training on 41GB of PubMed, with entity linking cast as generation, beats vanilla BART. BioBART also flags the tokenizer mismatch that the prefix-tolerant grammar addresses.

Research Program

We build a constraint engine with three parts:

  1. A rule index. The ontology's concept model, meaning which attributes may attach to which concept types and with which value ranges, is compiled into productions keyed by nonterminal and ontology context. New concepts or attributes are added by inserting keys.
  2. A lazy parser. It advances with each emitted token and asks the index only for productions reachable from its current state.
  3. A mask builder. It turns the retrieved productions into a character-level prefix tree and then into a vocabulary mask.

For the models, we continue pre-training a roughly 1B-parameter decoder, the size at which GRAMMAR-LLM saw its largest gains, on PubMed text, following BioBART's corpus choice. The general-domain checkpoint of the same model is the control. Both are then fine-tuned on the structured task in one of two ways: without constraints, or under the lazy mask using the loss above.

The main testbed is a new benchmark built from the ontologies used in Small Is Beautiful. The input is a concept's name and textual description. The target is its defining expression in the description logic EL, a logic that describes concepts by conjunctions and attribute restrictions. The split holds out entire concepts. We score with an ontology reasoner by checking logical equivalence to the gold definition, so paraphrased but equivalent expressions count as correct. This avoids string-match scoring. SNOMED CT's attribute-by-domain-by-range structure is what makes static compilation of the concrete grammar expensive. That cost is measured directly, not assumed.

Two secondary settings let us compare against reported numbers. The first is the NL-to-first-order-logic translation task in FOLIO, where the predicate vocabulary is lazily retrieved per story. The second is GeoQuery and SMILES using the grammar-prompting code.

Baselines

Naive reference. The same domain-pre-trained 1B model is fine-tuned on the task and decoded without constraints. It shows how much of the problem parametric domain knowledge already solves. The general-domain model under identical fine-tuning is the second naive point. The gap between them is the domain-pre-training effect we later test for additivity.

Strongest existing constrained-decoding method. This is GRAMMAR-LLM's static pushdown-automaton masking over a statically compiled grammar, run on the same fine-tuned checkpoints with the same decoding budget. We compile the full concrete grammar wherever memory allows. We expect this on GALEN and smaller ontologies, and report the compile size and time wherever it does not fit. We also run a static variant that compiles only the generic EL syntax plus a flat list of all concept names, which is feasible but ignores attribute-range rules. The closest reported figures are from GRAMMAR-LLM: 100% validity on Web of Science and a 30-percentage-point zero-shot gain for LLaMA-1B. No reported result was found on Lacuna for any method on ontology-definition generation. Beating this baseline therefore means two things. On ontologies where full static compilation is possible, we must match its validity and exceed its reasoner-equivalence accuracy. We must also scale to SNOMED CT, where it cannot run.

Grammar Prompting. We run its released code with the same backbone and a matched number of demonstrations. On GeoQuery it reports 88.9% execution accuracy against 81.5% for standard prompting, and nearly 98% SMILES validity (Grammar Prompting). On FOLIO translation, the reference is GPT-4's roughly 64% syntactic validity and 65.21% execution accuracy (FOLIO). Beating Grammar Prompting means higher execution or equivalence accuracy at 100% validity, with the gain concentrated on inputs where its predicted grammar is missing a needed rule.

Isolating ablations. Two ablations isolate the key ingredients. The first applies the lazy mask at test time only, with no constrained training, which isolates the renormalized loss. The second puts the retrieved productions into the prompt as text but does not mask, which isolates masking from retrieval. The proposal succeeds only if the constrained-training variant beats test-time-only masking on accuracy among valid outputs.

For fairness, every system uses the same checkpoints, training data, and hyperparameter search budget, and the same number of decoding samples.

Why not just…?

Why not just compile the grammar statically and use GRAMMAR-LLM? For flat label sets, such as the 134 Web of Science categories, static compilation is fine, and we concede that. Lazy retrieval would add nothing there. The case for laziness rests on the attribute-range structure of real clinical ontologies. Small Is Beautiful measured an eight-order-of-magnitude gap between static and on-demand rule application in exactly these ontologies. We report the static compile cost per ontology. If it turns out tractable for SNOMED CT, the scale claim fails, and the contribution reduces to live updates and constrained training.

Why not just sample several outputs and discard those the reasoner rejects? This is a real threat, because the reasoner is an exact verifier. We give it the same compute as our method: as many samples as fit in our decoding time budget. We expect it to degrade on long expressions, where the chance that a whole sample is valid shrinks with every attribute slot. We also expect it to miss correct answers the unconstrained model rarely proposes. If it matches our method at equal compute, we will say so and recommend it.

Why not just retrieve the relevant ontology fragment into the prompt? RuleReasoner documents sensitivity to long, distracting rule lists, and prompting gives no validity guarantee. The rules-in-prompt ablation measures this directly.

Why not just pre-train harder on domain text? MonoCoder and the PEFT study suggest pre-training is the strongest single lever. But pre-training cannot absorb a concept added after training without retraining, which RING also needs. The live-update test below addresses this. We also include a pre-training budget doubled relative to the main run, to see whether it closes the validity gap unaided.

Decisive Checks

The first check is a two-by-three grid: general versus domain pre-training, crossed with no mask, test-time mask, and trained mask. It is scored on validity and reasoner equivalence. Additivity would show up as domain pre-training raising equivalence accuracy by a similar margin with and without the mask, while the mask raises validity by a similar margin at both pre-training levels.

The second is a live-update test. We add held-out attributes and concepts to the index after training and measure accuracy on inputs that require them, comparing against a model fine-tuned on those additions.

The third is a cost profile. We report rules touched per output, per-token latency on single inputs, and cache hit rates. Following the machine-translation findings, it is not enough for rule retrieval to be fast. We must show that total decoding time stays within a small factor of unconstrained decoding.