- Rating
- 3
- Confidence
- 4(+1)
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposed a framework called FormalDisco, which use iterative loop to improve LLM's ability in generating verified code, by synthesizing formally verified programs with verifiers. FormalDisco leverages three types of agents (Initiator for initializing program with spec/doc, Fixer for fixing failed program with verifier feedback, and Extender for adding functions into verified code). It reports over 100k synthesized verified programs and demonstrated gain on downstream tasks.
Critical strengths
I really like this paper and feel even with such a clean and simple paradigm, it elegantly tackled a core issue in verified code generation and has potential to be applied to broader use cases or even adopted in industry deployment. The critical strengths:
-
The logic chain of initializing, fixing and extending is reasonable (especially extender): This loop efficiently leveraged the verification signals to generate program that can pass formal verification, and it increases the complexity of programs (i.e., programs with longer LOC due to the multiagent collaboration). This additive design is both intuitive and efficient. This is the foundation of my positive overall assessmenet,
-
It's inherently a plug-in styled data filtering/selection process: The authors are aware of potential diversity collapse and use program-feature entropy to make it tangible, which paves the way for filtering data in SFT. This incorporate diversity into a part of model training, making it more flexible in potential applications, and the authors have extensive experiments and downstream tasks (i.e., the Qwen Pass@1 results on multiple benchmarks) to validate it too. This consolidate my overall assessment as it supports the claims.
Critical weaknesses
While this paper has genuine value and advantage, there are some potential issues that may weaken its contribution:
-
There is no independent analysis of the specification quality of verified programs: This pipeline can theoretically generates specifications, implementations and proofs at the same time, but if there is no separate validation process, it cannot guanrantee the quality of generated specifications (i.e., they can be insignificant, off-track, or lack of constraints, etc). The current adopted metrics, like program length or complexity/entropy are a bit shallow and not directly relevant to spec quality. This wont harm the assessment but also constraint the positiveness to be weak acceptance.
-
Despite the performance gain, the evaluation has potential to be improved: Currently the authors adopted Dafny and Verus, but there is no claimed downstream result on Frama-C. In addition, some minor results issues include (1) Qwen has different sampling budget than Claude Opus so their results are not directly comparable, (2) in lemma proving the performance can be further improved, and (3) the lack of diversity/semantic analysis of the 100k data, etc. These minor issues also constraint the work to be weak acceptance.
Questions for authors
-
Since the specifications are generated, how do you make sure their quality is actually good (i.e., is the constraint strong enough, or actually functional as expected, etc)? Any spec quality assessment during the autospec process?
-
Is it possible to compare the performance of entropy-based filtering and random filtering and SFT given same data and budget, to show the independent advantage of entropy maximization?
-
Any results on Frama-C (since Dafny and Verus results were in place, but claimed Frama-C result is missing)?
Thank you for the detailed and positive review! We address your questions below.
Our current pipeline does not directly guarantee or maximize specification strength, though the diversity encouraged by some of the feature entropies (e.g., logical annotation templates) encourages specifications to not be trivial (since Z3 can generally prove trivial specs without help). While we can’t claim any intrinsic guarantees on the specs, the downstream evaluations show that they are at least extrinsically useful.
Yes, thanks for the suggestion. We completed a full run on Dafny, starting from the same Claude seed runs and repeating 5 iterations of self-improvement without the entropy filter (taking a random subset of the same fraction of the examples in each iteration, and training for the same number of SFT steps). We found that removing the entropy maximization makes the discovered Dafny programs markedly simpler, across all metrics we tracked. For instance, during the run, programs from the entropy-maximizing runs grow from 123 to 154 non-comment lines on average (median 96 -> 129) and from 6.8 to 12.0 assertions on average. The noent runs grow less, reaching 139 lines (median 107) and 9.6 assertions. Loop invariants rise from to 2.9 per program on average with entropy maximization, but this stays flat at about 1.2 per program without, so they contain roughly 2.5x fewer invariants by the last iteration. The noent workers also succeed more often, with initiator and extender success rates around 9-10% higher than without entropy maximization (fixer is also ahead but by a narrow margin, around 2%). This is consistent with the entropy term pushing workers toward harder and more novel tasks, whereas without it they settle on simpler programs they can already write/verify. The effect on downstream performance on DafnyBench is smaller, however. When we SFT a fixer on each agenda set and evaluate on DafnyBench, overall pass@32 is comparable: 42.2% vs 44.2% (with vs without). The two differ slightly more at pass@1 (22.4% without vs 25.8% with). Entropy maximization therefore gives richer programs and a model that is more often right immediately, while pass@k for high k largely hides the difference on DafnyBench at least. We will repeat this comparison for Verus and add both to the paper.
For Frama-C, despite being an active framework with industrial use, we could not find any existing suitable downstream evaluations in prior work (such as an equivalent "'FramaCBench"), so we only reported intrinsic evaluations on it. If the reviewer has suggestions of a downstream evaluation that would be informative here, we'd be happy to try our best on it before the rebuttal period ends.
Thank you again! We'd be happy to engage further if the reviewer has other questions.