💻 computer science

KBSpec: LLM-driven Formal Specification Generation with Evolving Domain Knowledge Base

KBSpec is an LLM-driven framework that generates formal specifications by leveraging a self-evolving knowledge base of external documentation and internal verifier feedback, achieving significant improvements in verification pass rates without requiring parameter tuning or labeled training data.

Original authors: Wenhan Wang, Zeyu Sun

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenhan Wang, Zeyu Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot to Write Legal Contracts for Code

Imagine you have a very smart, creative robot (a Large Language Model, or LLM) that is great at writing stories and code. However, you want this robot to write formal specifications—which are like strict, mathematical legal contracts that prove a piece of software will never crash or behave badly.

The problem is that the robot has never read many of these "legal contracts" before. In the real world, most programmers don't write them; they just write code. So, when you ask the robot to write one, it often makes mistakes: it uses the wrong grammar, forgets important safety rules, or writes something that sounds good but is mathematically impossible to prove.

KBSpec is a new system designed to fix this. It gives the robot a "smart notebook" that helps it learn how to write these contracts correctly, without needing to retrain the robot's brain.

The Two-Source Knowledge System

The paper argues that to fix the robot, you need two types of information, like a student studying for a difficult exam:

The Textbook (External Knowledge): This is the official manual written by the experts who created the language. It tells the robot the basic rules and grammar.
- Analogy: Imagine giving the robot a dictionary and a grammar book. It knows the words, but it doesn't know how to use them in tricky situations.
The Coach's Notes (Internal Knowledge): This is the most unique part of KBSpec. It comes from watching the robot try, fail, get corrected, and try again.
- Analogy: Imagine the robot tries to write a contract, and a strict referee (a Formal Verifier) blows a whistle and says, "Error! You can't do that!" The robot then tries again, fixes the error, and succeeds. KBSpec saves this "success story" in the notebook. Next time, the robot can look at the notebook and say, "Oh, I remember! When I tried to do X, the referee got mad, but if I do Y instead, it works."

How KBSpec Works (The 3-Step Pipeline)

The paper describes a three-step process to build this system:

Step 1: The Initial Setup (Filling the Notebook)
The researchers start by putting the official manuals and examples into the robot's "notebook" (Knowledge Base). This gives the robot a basic starting point.

Step 2: The Training Loop (Learning by Doing)
This is where the magic happens. The system runs a loop many times:

The robot tries to write a specification for a piece of code.
The Verifier (the referee) checks it.
If it passes: The system saves the "recipe" of how it succeeded into the notebook.
If it fails: The system looks at the error message, asks the notebook for help, and tries to fix the mistake. If the fix works, that "repair recipe" is also saved.
The Filter: The notebook isn't just a pile of papers. The system constantly checks: "Did this piece of advice actually help us pass the test?" If a piece of advice from the official manual leads to failure, it gets downgraded. If a new trick learned from a repair works, it gets promoted.

Step 3: The Final Exam (Inference)
When the robot faces a new, unseen piece of code, it doesn't just guess. It looks up the most relevant "recipes" in its evolving notebook to help it write the specification. It uses the lessons learned from past failures to avoid making the same mistakes again.

Why This is Special

The paper highlights a few key points that make KBSpec different from other methods:

No Brain Surgery: Usually, to make an AI better, you have to "fine-tune" it, which is like performing expensive brain surgery on the model. KBSpec doesn't touch the robot's brain at all. It just updates the notebook. This makes it cheap and easy to use with any robot.
The "Self-Evolving" Notebook: The notebook isn't static. It gets smarter every time the robot practices. It learns which rules from the official manual are actually useful and which ones are too complex for the referee to handle.
Better Results: When they tested this on Java code (using a benchmark called FormalBench), KBSpec helped the robot pass the verification tests 10% to 25% more often than the best previous methods. It also produced more specifications that were not just "correct" but also "complete" (covering all the necessary details).

The Catch (What the Paper Found)

The researchers noticed something interesting about the "completeness" of the contracts. Sometimes, to get the robot to pass the test, the system had to make the contract slightly less strict (e.g., "This works for most numbers" instead of "This works for every number").

Analogy: It's like a lawyer realizing, "If I promise the client the moon, I'll get sued. But if I promise them a very large, very safe garden, I can prove it's true."
The paper found that while the average strictness dropped slightly, the system generated more contracts that were actually useful and verifiable. It traded a tiny bit of perfection for a lot more success.

Summary

KBSpec is like giving a student a textbook and a personal tutor who keeps a diary of every exam mistake and how it was fixed. By constantly updating this diary based on feedback from a strict grader, the student learns to pass the exam much more often, without needing to change how the student thinks—just by giving them better notes to study from.

Technical Summary: KBSpec

Problem Statement

Automated formal specification generation is a critical step for program understanding and formal verification. While Large Language Models (LLMs) have shown promise in code generation, their application to formal specification (e.g., Java Modeling Language, JML) faces a significant hurdle: the scarcity of formal specification corpora in training data. This "low-resource" status leads to frequent syntactic errors and semantic failures (e.g., missing boundary checks, incorrect invariants).

Existing attempts to augment LLMs with external knowledge (e.g., official documentation) are insufficient because formal specification resources are often incomplete, lack coverage of diverse verification patterns, or contain experimental features not fully supported by verifiers. Furthermore, relying solely on static external knowledge fails to capture the nuanced, verifier-specific constraints required for successful verification.

Methodology: KBSpec

The authors propose KBSpec (Knowledge Base-Augmented Specification Generation), a framework that augments LLMs with a dual-source, self-evolving knowledge base. The system operates without modifying LLM parameters or requiring labeled ground-truth data, relying instead on feedback from formal verifiers.

The KBSpec pipeline consists of three main stages:

1. Knowledge Base Initialization

The system initializes a specification knowledge base ( $M$ ) using external knowledge sourced from official documentation (e.g., OpenJML tutorials, examples, and exercises) and human-written repair guidelines. Each knowledge item is structured as a triplet: original content ( $c_i$ ), a summary ( $s_i$ ), and keywords ( $k_i$ ), generated by an LLM to facilitate retrieval.

2. Knowledge Base Evolution (Training Phase)

This is the core innovation. The knowledge base is dynamically updated through a generation-and-repair pipeline run over a "training" corpus of Java programs.

Generation: For a given program, the LLM generates a baseline specification. It then retrieves relevant knowledge items and generates new specifications based on different combinations of retrieved knowledge.
Verification & Scoring: Generated specifications are verified using a formal verifier (OpenJML). A helpfulness score is assigned to each retrieved knowledge item based on whether it helped the LLM pass verification when it previously failed, or caused failure when it previously passed.
Iterative Repair: For specifications that fail, the system performs up to three rounds of repair. The LLM uses the original specification, the verifier's error message, and retrieved knowledge to generate a fixed version. The helpfulness of the retrieved items is updated based on the reduction in errors or successful verification.
Update & Filtering: After each epoch, the knowledge base is updated. Items with low helpfulness scores are filtered out, and new successful trajectories (generation or repair) are added. Redundancy is managed via similarity checks.

3. Knowledge-Augmented Inference

During the evaluation phase, KBSpec uses the evolved knowledge base to assist specification generation. Unlike the training phase, which uses random sampling of knowledge groups, the inference stage employs an LLM-based selector. The LLM autonomously chooses the most relevant knowledge items (up to 3) from the retrieved set to guide the generation and subsequent repair of specifications.

Key Contributions

KBSpec Framework: A novel, parameter-free approach for formal specification generation that integrates a self-evolving knowledge base driven by verifier feedback.
Dual-Source Knowledge: The identification and validation that combining external documentation (for initial language understanding) with internal knowledge (distilled from verifier feedback on generation/repair trajectories) is essential for overcoming the limitations of LLMs in formal specification.
Empirical Validation: A comprehensive evaluation on the FormalBench benchmark (JML specification generation) demonstrating that KBSpec significantly outperforms state-of-the-art baselines, including SpecGen and various prompting strategies (Few-shot, Least-to-Most, Self-repair).

Results

Experiments were conducted using three LLM backends: GPT-5.2, GPT-5-mini, and DeepSeek-v3.2.

Pass Rate Improvement: KBSpec improved verification pass rates by 10–25% over state-of-the-art LLM-based approaches (e.g., SpecGen). On GPT-5.2, the pass rate increased from 43.35% (SpecGen) to 58.94%.
Failure Reduction: The framework substantially reduced failure rates (e.g., reducing the fail rate for GPT-5.2 to 20.6%).
Completeness: While average completeness scores showed some variance, KBSpec produced the largest number of high-completeness specifications (completeness $\ge$ 0.5). Analysis of mutually verified programs showed KBSpec maintained or improved completeness compared to SpecGen, indicating that the gains in pass rate were not achieved by generating trivially weak contracts.
Ablation Study: The study confirmed that the knowledge base evolving mechanism (internal knowledge) was the most critical component, contributing more to performance than the initial external documentation. Iterative repair was also identified as a major driver of success.

Significance and Claims

The paper claims that KBSpec addresses the "low-resource" nature of formal specification languages by creating a self-improving loop where the system learns from its own successes and failures via verifier feedback.

Model Agnostic: The approach is lightweight and can be applied to any LLM without fine-tuning.
Generalizability: While evaluated on JML, the authors claim the design is language-agnostic and can be adapted to any specification language with an automated verifier.
Pragmatic Engineering: The analysis of learned knowledge reveals that the system effectively learns pragmatic repair strategies (e.g., handling arithmetic overflows, removing unsupported constructs) rather than simply weakening specifications to pass verification.

The authors conclude that integrating documentation-derived knowledge with verifier-grounded memory evolution substantially enhances the capability of LLMs to generate syntactically correct and semantically verifiable formal specifications.