PaperlayerView exact revision on arXiv

Source-linked AI summary

Metamodel-Guided LLM Decoding for Consistent DSL Generation

Boqi Chen, Aren A. Babikian, José Antonio Hernández López

arXiv:2610.29749v1cs.SEcs.AI

TL;DR

LLMs can generate DSL instances that fail to satisfy metamodel and well-formedness requirements, while existing checks may be limited to syntax or completed outputs. MeMoDecode verifies partial models during decoding and retries from a completable snapshot; across four DSLs and six open-weight models, it improves consistency and alignment with modest runtime overhead.

  • Problem

    Generated DSL instances may violate their metamodel or well-formedness constraints, and post-hoc verification checks only after generation.

    Source: §I · p. 1

  • Method

    MeMoDecode incrementally maps generated text to a partial model, checks whether it remains completable consistently, and retries from a prior completable snapshot when needed.

    Source: §I · p. 2

  • Results

    Across four DSL benchmarks and six open-weight LLMs, MeMoDecode improves consistency and alignment while preserving syntactic validity and adding only modest runtime overhead.

    Source: §V · p. 10

  • Takeaways & Limitations

    Metamodel-level verification adds a layer of correctness beyond syntax and can improve alignment when invalid instances count as unusable.

    Source: F. Discussion · p. 9

    The evaluation covers open-weight LLMs, while effectiveness on DSLs with substantially richer constraints or much larger instances remains uninvestigated.

    Source: G. Threats to validity · p. 10

Abstract

from arXiv · show

Large language models (LLMs) are increasingly used to generate software engineering artifacts written in domain-specific languages (DSLs). Correct DSL instances usually must comply with not only the concrete syntax but also the abstract syntax defined by a metamodel augmented with semantic well-formedness constraints. Existing constrained decoding approaches typically guarantee compliance only with concrete syntax or with a limited set of semantic constraints expressed over the generated text, making metamodel-level constraint consistency difficult to enforce during generation. We present MeMoDecode: a decoding framework that enforces a DSL's concrete syntax, abstract syntax, and well-formedness constraints jointly. Specifically, whenever the LLM generates a complete metamodel concept, MeMoDecode incrementally maps the current output to a partial model and verifies whether it can still be completed into a consistent instance. We combine MeMoDecode with a simple retry mechanism that resumes decoding from the most recent completable snapshot whenever an inconsistency is detected. Under a sound backend verifier, MeMoDecode never performs worse than grammar-constrained decoding on alignment metrics satisfying natural assumptions. Across four DSLs and six open-weight LLMs ranging from 0.6B to 70B parameters, MeMoDecode achieves the highest consistency, improving consistency by 23% on average over unconstrained decoding and by 8% on average over grammar-constrained decoding. It also improves benchmark performance while incurring only modest runtime overhead. These results show that metamodel-guided decoding is an effective approach for enforcing DSL consistency during decoding across diverse DSLs and LLM scales.

I. INTRODUCTION

MeMoDecode checks generated DSLs against their metamodel and well-formedness constraints during decoding, addressing limits of syntax-only and text-based checks. The paper reports improved consistency and alignment across DSLs and models, with modest runtime overhead.

I. INTRODUCTION

  • LLMs can produce DSL outputs that violate grammar, metamodel, or well-formedness constraints, undermining their use in downstream analysis and automation.A DSL instance is consistent when it conforms to both the metamodel and its well-formedness constraints.Source: §I · p. 1
  • Post-hoc verification detects violations only after generation, potentially wasting decoding effort and leaving later tokens conditioned on an invalid prefix.Repair may require additional steps.Source: §I · p. 1
  • Grammar-constrained decoding guarantees syntactic validity but does not ensure metamodel conformity, while text-based semantic checks remain tied to a particular representation.The latter limits reasoning about metamodel properties such as multiplicity, referential integrity, and transitive relationships.Source: §I · p. 1
  • MeMoDecode checks whether each partial model can still be completed consistently, retrying from an earlier completable snapshot when it cannot.The framework jointly targets concrete syntax, abstract syntax, and semantic well-formedness constraints.Source: §I · p. 2
  • Under a sound verifier and natural assumptions on the alignment metric, MeMoDecode never produces an output less aligned than grammar-constrained decoding under identical conditions.The paper implements it by combining grammar-constrained decoding with Refinery and a lightweight retry mechanism.Source: §I · p. 2
  • Across four DSLs and six open-weight LLMs, MeMoDecode improves DSL consistency and alignment while incurring only modest runtime overhead.The evaluated models range from 0.6B to 70B parameters.Source: §I · p. 2

II. BACKGROUND AND RELATED WORK

The background defines DSLs through their domain-specific use and distinguishes concrete syntax, abstract syntax, and semantic well-formedness constraints. It illustrates these layers with a CLEVR program and its grammar-based notation.

1) Domain-Specific Languages:

  • A CLEVR program represents a natural-language image question as an executable sequence of operations, illustrated by querying the color of a cube.The example applies scene, shape filtering, uniqueness, and color-query operations.Source: 1) Domain-Specific Languages · p. 2

2) DSL specifications:

  • A DSL specification comprises a grammar for concrete syntax, a metamodel for abstract structure, and semantic constraints over that structure.The paper formalizes it as D = (G, M, C).Source: 2) DSL specifications · p. 2
  • A grammar defines textual forms and syntactic validity, while a metamodel defines permitted elements and relations, including attributes, references, multiplicities, and inheritance.Selected completed grammar derivations are called syntactic units.Source: 2) DSL specifications · p. 2
  • Well-formedness constraints express semantic rules that grammar and metamodel alone cannot capture; a valid instance must conform to the metamodel and satisfy every constraint.The CLEVR DSL includes single-root, type-correct-dataflow, and acyclicity constraints among its 17 constraints.Source: 2) DSL specifications · pp. 2–3

3) Partial models:

The background introduces partial models as incomplete metamodel instances and explains how LLM decoding selects tokens under unconstrained or external constraints. It reviews grammar-based and iterative semantic approaches, including their representational limits.

3) Partial models:

  • A partial model records known metamodel facts while leaving other facts unspecified, and can be completed by adding facts until objects, references, and attributes are determined.MeMoDecode uses Refinery as its backend solver for reasoning about such partial models.Source: 3) Partial models · p. 3

4) Large language models:

  • An LLM generates autoregressively by selecting tokens from a distribution conditioned on the preceding prompt and generated sequence.Generation continues until a termination condition such as an end-of-sequence token.Source: 4) Large language models · p. 3

5) Decoding strategies for LLMs:

  • Constrained decoding restricts token choices using external constraints, and grammar-constrained methods mask tokens that cannot lead to syntactically valid output.Grammar constraints alone do not ensure consistency of the resulting instance model.Source: 5) Decoding strategies for LLMs · p. 3
  • IterGen supports iterative backtracking and semantic checks, but exposes concrete-syntax fragments that tie checks to surface details rather than underlying model objects and references.This can require users to reimplement parsing and structural analysis.Source: 5) Decoding strategies for LLMs · pp. 3–4

6) LLMs for DSL Generation:

Prior DSL-generation work uses unconstrained generation, grammar constraints, or post-hoc verification, while MeMoDecode checks structural consistency during decoding. The problem is to generate syntactically valid instances whose induced models satisfy metamodel and constraint requirements.

6) LLMs for DSL Generation:

  • Prior DSL-generation approaches either focus mainly on concrete syntax or verify validity only after a complete artifact has been generated.Existing work evaluates outputs against a reference artifact or expected execution result using an alignment score.Source: 6) LLMs for DSL Generation · p. 4

7) Positioning:

  • MeMoDecode rejects inconsistent structural decisions during decoding and lifts semantic checks from text fragments to the metamodel, keeping verification independent of textual representation.It complements unconstrained generation and post-hoc repair approaches.Source: 7) Positioning · p. 4

1) Problem definition:

  • The problem is to generate an output in the grammar whose induced instance model is consistent with the metamodel and well-formedness constraints.Improving alignment is a secondary goal of enforcing these consistency properties during decoding.Source: 1) Problem definition · p. 4

2) Overview:

MeMoDecode preserves grammar-valid output while mapping completed syntactic units into a partial model and checking whether that model remains completable. Rejected units trigger a retry from the latest completable snapshot.

2) Overview:

3) Grammar-constrained decoding:

4) Syntactic unit extraction:

  • A syntactic unit is a completed derivation of a configured grammar non-terminal whose text encodes metamodel-relevant information.Language engineers configure these non-terminals; examples include node and edge declarations.Source: 4) Syntactic unit extraction · p. 4

5) Mapping syntax to partial models:

  • The mapping converts completed units into metamodel facts that can introduce objects, assign attributes, or create references.For example, node declarations induce node and type facts, while edge declarations induce source and target references.Source: 5) Mapping syntax to partial models · p. 4
  • The verifier rejects partial models that cannot be completed, while allowing fixable incompleteness; failed units are retried from the latest completable snapshot.The mapping can be manually specified or generated from language-framework information, and verification can enforce constraints such as multiplicities and acyclicity.Source: 5) Mapping syntax to partial models · p. 5

6) Semantic verification and retry:

MeMoDecode checks each candidate partial model for unfixable inconsistency with the metamodel and well-formedness constraints. Decoding stops under specified completion, length, or retry-budget conditions.

6) Semantic verification and retry:

  • Adding a completed unit u to the accepted partial model P creates candidate P′ = P ∪ µ(u), which is then checked semantically.The check seeks facts that make the partial model impossible to complete, rather than rejecting incompleteness that later tokens could fix.Source: 7) Termination conditions · p. 5
  • A partial model is completable when at least one complete consistent instance refines it while preserving its fixed facts.Refinement resolves unknowns by adding objects, attribute values, or references.Source: 7) Termination conditions · p. 5
  • Decoding stops at end-of-sequence, parser completion, or the token limit; if retries are exhausted, it falls back to grammar-guided decoding from the latest completable snapshot.This fallback is intended to terminate with syntactically valid output.Source: 7) Termination conditions · p. 5

8) Worst-case alignment score guarantee:

With a sound verifier and an alignment scorer meeting stated assumptions, MeMoDecode’s score is no lower than grammar-constrained decoding under identical conditions. The evaluation also asks about validity, consistency, efficiency, alignment, and runtime.

8) Worst-case alignment score guarantee:

  • The guarantee assumes a sound backend verifier and a nonnegative alignment score that is zero for inconsistent instances.If grammar-constrained output is consistent, soundness implies no rejection; if it is inconsistent, its score is zero under the precondition.Source: 8) Worst-case alignment score guarantee · p. 6
  • Under identical prompts, models, samplers, and random seeds, MeMoDecode achieves an equal or better alignment score than grammar-constrained decoding.The scores are equal whenever no rejection occurs.Source: 8) Worst-case alignment score guarantee · p. 6

IV. EVALUATION

  • The evaluation investigates syntactic validity and consistency, token efficiency, alignment scores, and runtime overhead.These are the four stated research questions.Source: §IV · p. 6

A. Setup

The setup evaluates four DSL benchmarks with unconstrained and grammar-constrained baselines, using six open-weight instruction-tuned LLMs. It measures validity, consistency, alignment, token use, and runtime under specified sampling conditions.

A. Setup

  • The four benchmarks cover non-executable DSLs, including taxonomy and flowchart tasks, and executable DSLs, including CLEVR and Block.The setup describes non-executable DSLs as structured artifacts and executable DSLs as programs that produce outputs.Source: A. Setup · p. 6, Table I · p. 6
  • The baselines are unconstrained sampling and grammar-constrained decoding, with the same model, prompt, sampler, and random seed across comparisons.Grammar decoding masks tokens that would violate the DSL context-free grammar.Source: A. Setup · p. 6
  • The six open-weight models span Qwen3, Gemma-4, and Llama3.3, from 0.6B to 70B parameters; GPT-5.5 is included only as an unconstrained reference.MeMoDecode is evaluated only on open-weight models because it requires direct access to decoding operations such as token masking and rejection.Source: A. Setup · pp. 6–7
  • Consistency measures outputs satisfying both the metamodel and well-formedness constraints, while syntactic validity measures outputs that parse according to the concrete syntax.For executable DSLs, execution accuracy measures denotation accuracy for Block and answer accuracy for CLEVR.Source: A. Setup · p. 7
  • Structural alignment uses Soft F1, while Hard-0 F1* assigns zero to inconsistent instances; efficiency measures average generated tokens and runtime per sample.Soft F1 is reported as a reference metric because it gives partial credit to inconsistent outputs.Source: A. Setup · p. 7
  • Experiments use few-shot prompts, temperature 0.7, a 5,096-token maximum, and up to 50 retries, with averages over three random seeds unless stated otherwise.Local-model experiments use a single NVIDIA RTX Pro 6000 GPU and an Intel Xeon Platinum 8470Q CPU.Source: A. Setup · p. 7

B. RQ1: Impact on consistency

MeMoDecode preserves near-perfect syntactic validity while achieving the highest consistency across evaluated LLMs and benchmarks. Despite retry overhead, it is at least as token-efficient as both baselines and notably more efficient on three of four benchmarks.

B. RQ1: Impact on consistency

  • MeMoDecode achieves the highest consistency for every LLM and benchmark combination, except a tie with Grammar at 97.2% on Flowchart with Qwen3-32B.For Qwen3-0.6B, consistency rises from 36.0% to 66.7% on Taxonomy and from 5.6% to 31.2% on CLEVR.Source: B. RQ1: Impact on consistency · p. 7
  • MeMoDecode’s consistency gains persist for larger LLMs: versus Grammar, Llama3.3-70B improves by 18.8% on CLEVR and 4.5% on Block.Unconstrained GPT-5.5 reaches 95.5% on Block and 82.9% on CLEVR, not perfect consistency.Source: B. RQ1: Impact on consistency · p. 7
  • MeMoDecode preserves Grammar’s near-perfect syntactic validity within 2% while achieving the highest consistency across LLMs and benchmarks.The largest reported syntactic-validity reduction is 2%: 92.7% versus 90.7% for Gemma4-E2B on Taxonomy.Source: B. RQ1: Impact on consistency · p. 7

C. RQ2: Token efficiency

  • For Qwen3-8B, MeMoDecode’s token-efficiency curve starts farther right at N = 1, reflecting retries; on Taxonomy it uses approximately 470 versus 350 output tokens.Figure 4 plots best-of-N consistency against expected output tokens per instance.Source: C. RQ2: Token efficiency · p. 8, Figure 4 · p. 8
  • The token-efficiency figure counts output tokens only, while post-hoc verification requires a new generation pass for every candidate instance.Prompt caching partially mitigates the input-token cost, though cached input tokens are still billed by most proprietary APIs.Source: C. RQ2: Token efficiency · p. 8
  • At equal token budgets, MeMoDecode is at least as token-efficient as both baselines and notably more efficient on three of four benchmarks.On Taxonomy, it exceeds Grammar by about 5% at the same budget, approximately 93% versus 88%; the CLEVR curves nearly overlap.Source: C. RQ2: Token efficiency · p. 8

D. RQ3: Alignment scores

MeMoDecode improves alignment metrics that satisfy Theorem 1’s assumptions, with gains in structural and executable DSL measures. It loses to Grammar on only one evaluated instance, due to an incorrect backend rejection.

D. RQ3: Alignment scores

  • MeMoDecode improves execution accuracy for every LLM and benchmark, with the largest gain on CLEVR for Llama3.3-70B, from 52.0% to 65.7% (+13.7%).The reported improvements arise from fixing inconsistent instances while preserving the quality of valid ones.Source: D. RQ3: Alignment scores · p. 8
  • Table III presents alignment scores (%) for each approach across four benchmarks, highlighting the best F1* or accuracy per benchmark and LLM, with GPT-5.5 as an unconstrained reference.Source: Table III · p. 9
  • None of the evaluated open-weight LLMs surpasses unconstrained GPT-5.5, indicating that LLM capability remains important for achievable alignment scores.The paper reports that MeMoDecode consistently improves alignment metrics satisfying Theorem 1’s assumptions.Source: D. RQ3: Alignment scores · p. 9
  • MeMoDecode records zero alignment losses on three benchmarks, with statistically significant improvements (p < 10^-4); the sole loss is one CLEVR instance.Manual inspection attributed that loss to an incorrect backend rejection caused by integer overflow from an excessively large generated identifier.Source: D. RQ3: Alignment scores · p. 9

E. RQ4: Runtime analysis

Verification itself contributes little to runtime; MeMoDecode’s overhead is dominated by additional LLM inference for retries. This relative overhead decreases as LLM capability increases.

E. RQ4: Runtime analysis

  • On Taxonomy with Llama3.3-70B, MeMoDecode takes around 11.8s per instance versus around 11.2s for Grammar.Across benchmarks and evaluated LLMs, verification contributes only a small fraction of total runtime.Source: E. RQ4: Runtime analysis · p. 9
  • On CLEVR, MeMoDecode’s runtime ratio versus Grammar falls from approximately 7× for Qwen3-0.6B to about 3× for Qwen3-8B and less than 2× for Llama3.3-70B.CLEVR has the largest retry overhead, while relative overhead is substantially smaller for stronger LLMs.Source: E. RQ4: Runtime analysis · p. 9
  • MeMoDecode’s runtime overhead is dominated by the additional LLM inference required for retries, not verification itself.The runtime comparison decomposes time into inference, sampling, syntax masking, verification, and HTTP transport to the backend verifier.Source: E. RQ4: Runtime analysis · p. 9

F. Discussion

MeMoDecode adds metamodel-level correctness beyond syntax, improving consistency and alignment, though larger models still produce inconsistent instances. The discussion identifies retry inference as the main runtime cost and notes evaluation and verifier limitations.

F. Discussion

  • MeMoDecode systematically improves consistency and alignment beyond syntax, but even GPT-5.5 reaches only 82.9% consistency on CLEVR.Larger LLMs improve consistency and alignment but do not eliminate inconsistent outputs.Source: F. Discussion · p. 9
  • Retrying rejected syntactic units accounts for most runtime overhead, while metamodel verification contributes only a small fraction.Fig. 5 shows average runtime breakdowns for Grammar and MeMoDecode on each benchmark.Source: Figure 5 · p. 10, F. Discussion · p. 10
  • MeMoDecode currently accepts partial models with fixable violations and focuses on final outputs rather than intermediate reasoning traces.Future work could use fixable violations as decoding-time heuristics and extend verification to reasoning LLMs.Source: F. Discussion · p. 10

G. Threats to validity

  • Token-level logit access limits evaluation to open-weight LLMs, and effectiveness on richer semantic constraints or much larger instances remains uninvestigated.The study evaluates four representative DSLs covering structural and executable semantics.Source: G. Threats to validity · p. 10
  • Consistency results depend on verifier correctness, while execution accuracy is an imperfect proxy for true alignment correctness.An incorrect executable DSL instance may occasionally produce the correct result by chance.Source: G. Threats to validity · p. 10

V. CONCLUSION

  • Under a sound verifier, MeMoDecode never performs worse than grammar-constrained decoding on alignment metrics satisfying natural assumptions.Across four DSL benchmarks and six open-weight LLMs, it improves consistency and alignment while preserving syntactic validity with modest runtime overhead.Source: §V · p. 10
Loading 2610.29749v1…