- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper introduces LLM2Cert, a framework that leverages Large Language Models (LLMs) to generate Lyapunov functions or barrier certificates for dynamical systems, subsequently verifying the resulting proof obligations using SMT solvers and the Lean theorem prover. The authors also developed DynaCertBench, a benchmark suite comprising 105 instances. The full framework successfully verified 81 of these instances, demonstrating the complementary nature of the two verification backends.
Critical strengths
- The approach decouples LLM-based candidate generation from formal verification—avoiding the pitfall of treating sampled "passes" or -satisfiability results as formal proofs—reflecting a clear commitment to reliability.
- The benchmark covers four categories of tasks across both continuous and discrete systems, including instances with non-polynomial dynamics and control constraints, offering significant value to the research community.
Critical weaknesses
- Table 3 reports that 81 out of 81 instances were verified, whereas Tables 9 and 10 in the appendix report 66 out of 81 for the same fixed set of certificates. Furthermore, the number of proof obligations discharged via SMT solvers is reported as 253 in one instance and 270 in another. Please clarify the experimental batches and the statistical criteria used; otherwise, it is difficult to assess the actual performance gains.
- In the main text and Appendix F.7, the center of the unsafe region for "System 88" is specified as , while the execution logs in Appendix D.3 use and incorporate additional boundary constraints. Please confirm the exact specifications used for verification and ensure they are consistent with the original problem definitions.
Questions for authors
-
Are the "one-shot" results presented in Table 2—reconstructed from successful execution logs—based on a consistent verification budget applied to the first candidate generated for each of the 105 instances? How was selection bias mitigated?
-
Regarding the "Structured Repair" results in Table 4: the text implies they follow the records from RQ1, yet Appendix E.4 suggests that all three strategies involved re-running the verification process. Were these three sets of results obtained from independent runs starting from the same initial conditions and using the same verification budget?
-
In Tables 3 and 10, the reported execution times only account for samples where each strategy succeeded; consequently, the sets of samples being compared are not identical. Could you provide the execution times based on a common set of samples, as well as the total cost that includes instances of failure and timeout?
5 comments
Response (2/2)
Q2. Were the three repair strategies in Table 4 independent runs from the same starting point and budget, or does Structured Repair reuse the RQ1 records?
They are independent runs with the same starting point and the same budget. All three results, including Structured Repair, come from re-running on the same 26 obligations, and all numbers in Table 4 come from this re-run. These 26 are the obligations described in line 461: in the Full runs over the 105 systems, they are the obligations, from 19 systems, whose first Lean proof failed and needed repair.
- Same starting point: for each obligation, the candidate certificate, the locked theorem statement and the first failed proof are taken from the RQ1 records and frozen, and the hashes match obligation by obligation across the three groups.
- Same budget: 900 s of repair time per obligation, at most 6 proof rounds (including the frozen first failure), and at most 600 s per model call. The three groups differ only in the feedback.
- Same running conditions: the three groups ran interleaved in the same period, and the three runs of the same obligation were never adjacent.
Why Structured Repair was re-run as well: Table 4 is a controlled experiment, so the three kinds of feedback should be compared under exactly the same settings. The other two kinds of feedback can only run in this setting, so we re-ran Structured Repair in the same setting instead of reusing the RQ1 records (in RQ1, repair happened inside the full pipeline and shared its budget with the other obligations of the same system). The re-run agrees with the original RQ1 records: both repair 21/26.
The footnote “Measured from the recorded RQ1 traces” (lines 447–448) does not make this clear. We will change it to: “All three strategies are re-run under the same conditions from the same starting point frozen from the RQ1 records. In the original RQ1 records, Structured Repair also repairs 21/26.” The description in Appendix E.4 is accurate (lines 1445–1446: each group calls the model again from the same first failure), and the revision adds the settings and the per-obligation results of the three groups there.
Q3. Times are averaged over different successful subsets. Please give a common subset and failure-inclusive totals.
We agree that averaging over the samples each strategy verifies mixes in differences between the sample sets. All times are recorded wall-clock times.
In the submission, the mean times in Tables 3 and 10 cover only the certificates that each strategy verifies. Following the reviewer's suggestion, we add the mean recorded wall-clock time over the 34 certificates verified by all three strategies and over all 81 certificates. The latter includes successful, failed and timed-out runs.
| Strategy | Verified certificates | 34 commonly verified certificates | All 81 certificates |
|---|---|---|---|
| All-SMT | 59/81 | 2.07 s | 224.99 s |
| All-Lean | 42/81 | 565.69 s | 930.03 s |
| Full | 81/81 | 32.66 s | 119.31 s |
All-Lean in this table is the original batch of Table 3 in the submission. Some certificates in this batch did not get a complete Lean proof attempt (including the 15 re-run in W1), so 42/81 only represents this batch. In this table, All-Lean proves the obligations of a certificate one after another, so its time per certificate is the sum over its obligations and can exceed the 900 s budget of a single obligation, while All-SMT and Full check the obligations of a certificate in parallel. If All-Lean also checked them in parallel, its mean time on the 34 common certificates would be 392.82 s, still far above the 32.66 s of Full. On the 34 common certificates, All-SMT is the fastest. On all 81 fixed certificates, Full verifies the most certificates and also has the lowest mean wall-clock time.
In the submission, Table 7 in Appendix E.2 covers only successful runs. Following the reviewer's suggestion, we add the mean recorded wall-clock time over the 48 systems verified by all three configurations and over all 105 systems. The latter includes successful, failed and timed-out runs.
| Configuration | Verified systems | 48 commonly verified systems | All 105 systems |
|---|---|---|---|
| LLM2Cert (SMT only) | 57/105 | 206.48 s | 643.31 s |
| LLM2Cert (Lean only) | 60/105 | 613.95 s | 1,383.87 s |
| LLM2Cert (Full) | 81/105 | 261.69 s | 903.78 s |
On the common systems, SMT only is the fastest. On all 105 systems, Full raises the number of verified systems from 57 to 81 compared with SMT only, while the mean wall-clock time rises from 643.31 s to 903.78 s. Compared with Lean only, Full verifies more systems and also has a lower mean wall-clock time. The 81 certificates of the fixed-candidate experiment come from the successful runs of Full, while the end-to-end experiment covers all 105 systems. These tables and the timing notes will be added to Appendix E.3.
Revised PDF Uploaded: Changes for Your Comments
Dear Reviewer o2na,
Greetings from the authors! Thank you for seeing the separation of generation and verification as "a clear commitment to reliability," and for cross-checking our tables, which found real gaps in our reporting. The revised PDF (changes in blue) now:
- labels Tables 10–12 as the SMT-first policy, separate from the router of Table 3, and gives both counts, 253 and 270 (Section 5.4, Appendix E.3.1);
- adds times on common subsets and over all runs (Tables 15–16);
- uses an independent one-shot run, clarifies how the three strategies in Table 4 were run, and fixes System 88 in Appendix D.3.
If anything still does not add up, please let us know.
Best regards,
The Authors
Response (1/2)
We thank the reviewer for noting that separating candidate generation from formal verification reflects a clear commitment to reliability, and for cross-checking the numbers across tables. Thank you also for your patience while we ran the new experiments. Short answers to W1 and Q1 are in General Response 4 and 2, and the full replies are below.
W1. Batch and cohort of each number: 253 vs 270.
The difference between 253 and 270 has the same source. In the main text we use the LLM router, so on the path the Full run actually took, SMT discharges 253 obligations. In the SMT-first composition, SMT discharges 270. The reason is that the LLM router sent 19 obligations that have an SMT encoding directly to Lean, and SMT could discharge 17 of them within 30 s. These 17 are exactly the difference. In detail:
Table 3 vs. Tables 9/10. Routed in Table 3 is the path the Full run actually took, with obligations dispatched by the LLM router. The 81 fixed certificates are the ones Full verified, so it is 81/81 by construction. Routed in Tables 9/10 is the SMT-first policy: each obligation first gets 30 s of SMT, unresolved obligations go to Lean, and the Lean results are taken from the All-Lean run in the main text. All-Lean runs certificate by certificate: as soon as one obligation is not proved, the certificate is marked unverified and its remaining obligations are not run. So when results are taken obligation by obligation, 17 obligations in 15 certificates have no valid Lean result, either because they were not run or because the attempt did not finish. The original count treated these obligations as failures and gave 66/81.
But 66/81 does not represent the SMT-first policy itself: these 17 obligations were counted as failures because the All-Lean records contain no complete Lean proof attempt for them. To compare the SMT-first policy, we therefore re-ran All-Lean on these 15 certificates, and SMT-first then verifies 80/81. The revision will correct the results in Appendix Tables 9/10 and label them as the SMT-first policy.
W2. The specification of System 88 differs between Appendix D.3 and the logs.
Verification uses the same specification as the main text and Appendix F.7 (line 2783): the unsafe set is the disc with center (2, 2) and radius 1. This is how the benchmark file defines it:
Appendix D.3 differs from it in two places:
The revision changes D.3 to XU={x:∥x−(2,2)∥≤1}, consistent with the main text.
Q1. Was the one-shot baseline run with the same budget, and how was selection bias mitigated?
Yes, the One-shot row of Table 2(b) is reconstructed (footnote, line 342). The rule was: a system counts as a one-shot success if the first successfully parsed candidate in the Full run is fully verified without using counterexamples or feedback on unresolved obligations. To make the contribution of feedback clear, an independent comparison on the same benchmark is needed. We have now run the no-feedback configuration independently on all 105 systems: one candidate only, the same limit on format repairs as Full, full SMT + Lean verification but a single proof attempt per Lean obligation, and the whole 2,400 s of each system for this one candidate. It verifies 64/105 (Literature-derived 55/80, Extended 5/11, New 4/14). The reconstructed value is 63/105 and the independent run gives 64/105, with 56 systems verified by both. The numbers are close, so the reconstruction did not overstate the one-shot result. Table 2(a) will report this independent result (Synthesis: LLM, Verification: SMT+Lean). The reconstructed value is kept only in Figure 3(c), marked as “derived from trajectories”, where it splits the gain of the full loop on the same initial candidates, and we think this result is still useful.