Reliable Generation of Feature Models in the Universal Variability Language using Constrained LLMs

Abstract

Modern software systems are increasingly variant-rich, and feature models capture this variability formally. The Universal Variability Language (UVL) has emerged as a community-driven standard for expressing such models, but creating and maintaining UVL artifacts remains a manual, expert-driven task. Large Language Models (LLMs) can automate the translation from natural-language descriptions into formal models, yet they frequently produce syntactically invalid UVL, as the language is severely underrepresented in pre-training data. Grammar-constrained decoding (GCD) addresses this by restricting generation to a formal language. No GCD framework we are aware of, however, consumes ANTLR grammars, the format of the UVL reference grammar and of many other domain-specific languages. We therefore present Unconstrained-First GCD (UF-GCD), which integrates an ANTLR-based syntactic oracle directly into the decoding loop. The model samples freely at every step, each proposed token is validated against the grammar, and only a rejected token is resampled under the grammar. This avoids the semantic degradation caused by restricting the model at every step. With three open-weight LLMs, UF-GCD parses in 100% of runs while matching the semantic quality of unrestricted generation, constraining at most 2.1% of tokens.