Abstract
Recent advancements in Large Language Models (LLMs) have shown significant promise in various coding tasks. This study explores their capability in the specialized domain of declarative specification using Alloy. By evaluating state-of-the-art models like OpenAI's o3-mini and DeepSeek R1, researchers demonstrate that LLMs can effectively synthesize, refactor, and complete complex relational logic, potentially lowering the barrier to formal software verification.
Introduction
Formal methods and declarative languages like Alloy are critical for developing high-assurance software systems where correctness is paramount. However, the steep learning curve associated with first-order logic and relational algebra often deters developers. Unlike imperative programming, declarative languages focus on what properties a system must satisfy rather than how to implement them. This paper investigates whether modern LLMs can bridge this gap by translating natural language requirements into formal Alloy specifications.
Methodology
The researchers evaluated two prominent models, OpenAI o3-mini and DeepSeek R1, across three primary workflows: translating English to Alloy, refactoring Alloy formulas for logical equivalence, and "sketching" (filling in missing pieces of partial specifications).
To ensure the validity of the generated code, the study employed the Alloy Analyzer. As shown in the workflow above, this SAT-based tool checked for syntax errors and performed exhaustive logical equivalence checks against a ground-truth reference. If the analyzer could not find a counterexample, the LLM's output was deemed correct.
Benchmarks and Datasets
The evaluation focused on 11 fundamental properties of graphs and binary relations, which serve as the building blocks for more complex specifications. These include relational properties like transitivity and antisymmetry, as well as graph-specific properties like acyclicity.
Key Insights
Zero-Shot Sketching
A significant finding was the models' proficiency in "sketching." While traditional tools require extensive test suites to fill code holes, LLMs successfully completed these tasks using only natural language hints. This was achieved without specific training on the sketching notation used in the prompts.
Logical Diversity and Reasoning
The models demonstrated a capacity for relational reasoning beyond simple memorization. In the "English to Alloy" task, they produced a variety of logically equivalent but structurally different formulas. Some solutions utilized universal quantification, while others leveraged succinct relational compositions, surprising the researchers with their elegance.
Automated Validation Loop
The study underscores the synergy between LLMs and formal methods. Alloy’s SAT-based backend provides an immediate, exhaustive feedback loop, allowing for the automated verification of AI-generated specifications and mitigating the risks of "hallucinations" in critical system design.
Results
Both models demonstrated high accuracy, finding at least one valid solution for every task. In the "English to Alloy" benchmark, DeepSeek R1 slightly outperformed o3-mini in generating unique correct solutions (e.g., 19/20 correct for the Antisymmetric property vs. 16/20). Sketching performance was nearly perfect for both models, with initial failures being minor syntax errors that were easily corrected upon feedback.
Conclusion and Future Work
While the study focused on foundational properties, the results are a promising step toward integrating LLMs into formal modeling IDEs. Future research will explore how these models handle large-scale, multi-signature specifications and their ability to explain counterexamples generated during the verification process.
Summary updated