acceptodds
Under review as a conference paper at ICLR 2027

LLM2Cert: LLM Synthesis of Certificates with SMT/Lean Verification

Abstract

Lyapunov functions and barrier certificates give state-space guarantees of stability and safety, but synthesizing and verifying them—especially for nonlinear, high-dimensional systems—remains an open challenge. Existing pipelines verify candidates with numerical solvers (sum-of-squares programs), interval methods, or satisfiability-modulo-theories (SMT) solvers, which often require relaxations, are conservative, or scale poorly with model dimension and nonlinearity. These limitations have also shaped benchmark design: standard test suites are dominated by low-dimensional polynomial systems chosen to suit what solvers can handle rather than what engineering applications require. We address both sides of this challenge. First, we introduce DynaCertBench, a benchmark of 105 instances: 80 non-redundant systems curated from the literature, extended with high-dimensional and control-constrained variants and new nonlinearly coupled systems, comprehensively spanning stability, region-of-attraction, forward-invariance, and safety tasks. Second, we present LLM2Cert, an LLM-driven framework that synthesizes candidate certificates and verifies them against their proof obligations: each obligation is routed to an SMT solver or directly to the Lean Proof-Repair agent. On DynaCertBench, LLM2Cert verifies 81 of 105 instances (), a percentage point improvement over one-shot proposal without feedback. On the 81 fixed certificates, LLM2Cert verifies 22 that All-SMT leaves unresolved.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
dynamical systems, Lyapunov functions, barrier certificates, formal verification, Lean, SMT solving, LLM, agents, reasoning, neurosymbolic AI, safety verification, benchmark

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_o2naOpenReview ↗
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
  1. The approach decouples LLM-based candidate generation from formal verification—avoiding the pitfall of treating sampled "passes" or δ\delta-satisfiability results as formal proofs—reflecting a clear commitment to reliability.
  2. 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
  1. 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.
  2. In the main text and Appendix F.7, the center of the unsafe region for "System 88" is specified as (2,2)(2, 2), while the execution logs in Appendix D.3 use (1/2,1/2)(1/2, 1/2) 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
  1. 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?

  2. 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?

  3. 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
AuthorsOpenReview ↗

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:

"unsafe_set": {"type": "ball", "center": ["2", "2"], "radius": "1"}

Appendix D.3 differs from it in two places:

  1. The center is written as (1/2, 1/2). This is a typo, and it should be (2, 2).
  2. It adds x1,x2∈[1,3]x_1, x_2 \in [1, 3]. This range does not change the set: every point of the disc already satisfies x1,x2∈[1,3]x_1, x_2 \in [1, 3]. With or without this range it is the same disc, so the verification result is the same.

The revision changes D.3 to XU={x:∥x−(2,2)∥≤1}X_U = \{x : \|x - (2, 2)\| \le 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.

AuthorsOpenReview ↗

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.

StrategyVerified certificates34 commonly verified certificatesAll 81 certificates
All-SMT59/812.07 s224.99 s
All-Lean42/81565.69 s930.03 s
Full81/8132.66 s119.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.

ConfigurationVerified systems48 commonly verified systemsAll 105 systems
LLM2Cert (SMT only)57/105206.48 s643.31 s
LLM2Cert (Lean only)60/105613.95 s1,383.87 s
LLM2Cert (Full)81/105261.69 s903.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.

AuthorsOpenReview ↗

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

Reviewer_xZMMOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

LLM2Cert proposes an LLM-based framework for synthesizing Lyapunov and barrier certificates, combining SMT verification with Lean proof generation and repair to verify the resulting proof obligations. The framework routes obligations between the two verification backends and uses verification feedback to refine candidate certificates. It also introduces DynaCertBench, a benchmark of 105 instances spanning stability, region-of-attraction, invariance, and safety tasks. The full framework reports successful synthesis and verification on 81 of 105 instances (~78%), compared with 57 for its SMT-only configuration and 60 for its Lean-only configuration. The core approach is technically coherent and offers a useful integration of complementary verification tools, but the methodological novelty over existing LLM-based synthesis pipelines appears incremental and its significance is insufficiently demonstrated.

Critical strengths
  1. The framework uses SMT and Lean at the level of individual proof obligations, allowing it to retain successful SMT checks and reserve Lean proof search for unresolved conditions. This provides a practical way to extend verification coverage without requiring a complete Lean proof for every obligation, as illustrated by the running example. The experiments show a clear benefit from combining SMT and Lean: the full framework succeeds on 81 systems, compared with 57 using SMT alone and 60 using Lean alone.

  2. The proposed proof interface has sensible safeguards, where candidate expressions, theorem statements, and hypotheses are fixed during verification and generated proofs are checked and audited for placeholders and unexpected axioms. Quick screening is explicitly not treated as verification, and a dReal delta-sat result is treated as inconclusive for the original query. These distinctions are well designed for an LLM-based verification system.

  3. DynaCertBench enables evaluation across different use cases including stability, region-of-attraction, invariance, and safety tasks, extending beyond safety-only benchmarks such as BarrierBench. Higher-dimensional and nonlinearly coupled systems also test the framework beyond low-dimensional examples.

Critical weaknesses
  1. The paper does not establish how much its method improves over existing LLM-based certificate synthesis. BarrierBench already uses an LLM to generate and refine certificates with SMT feedback, so the main methodological addition is Lean proof generation and repair. However, the experiments compare against an SMT-only version of LLM2Cert rather than BarrierBench’s complete pipeline. This shows that Lean helps within the proposed framework, but leaves unclear whether the framework outperforms its closest predecessor under comparable budgets.

  2. The benefit of the LLM router is unclear. A simple policy could try SMT first and send unresolved obligations to Lean. Comparing the hybrid framework with SMT-only and Lean-only shows that combining the backends helps, but does not show that an LLM is needed to choose between them. A comparison with this simple routing policy, measuring both verification success and total cost, is needed to justify the router’s additional complexity and LLM calls.

Illustrating alternative routing heuristics, such as rules based on obligation type, expression complexity, or solver compatibility, would also help identify which routing decisions improve the success–cost tradeoff.

  1. Some of the reported verification results appear inconsistent. Table 3 reports that Routed verifies all 81 fixed certificates, while Tables 9 and 10 report 66/81. These discrepancies should be clarified.

  2. The one-shot baseline is not evaluated independently. The footnote to Table 2(b) on page 7, states that it is reconstructed from successful runs that did not require feedback. However, Section 5.3 and Figure 3(c) on page 8, shows this result to assess the improvement from feedback and proof repair. It is unclear whether this reconstruction is equivalent to running a separate no-feedback configuration. An independent comparison on the same benchmark, with the verifier and budgets specified, would make the contribution of feedback clearer.

  3. Benchmark difficulty could also be quantified through baseline success rates, timeout-inclusive runtime, and certificate complexity, rather than dimensionality alone. Tests on unseen system variations would better assess generalization.

Questions for authors
  1. How does the full framework compare with BarrierBench's complete LLM-based retrieval and refinement pipeline under matched models, budgets, and verification targets? What advance remains beyond adding Lean proof repair?
  2. What decisions does the LLM router make beyond compatibility checks and timeout-based fallback? Does it improve verified-system counts or total cost over a deterministic SMT-first policy, after including router calls and failed attempts?
8 comments
AuthorsOpenReview ↗

Response (1/4)

Thank you for your patience while we ran the new experiments. Short answers to W1/Q1 are in General Response 1 and 3, to W3 in General Response 4, and to W4 in General Response 2. The full replies are below.

W1 / Q1. There is no comparison with BarrierBench's full pipeline. Beyond Lean proof repair, what is the advance?

(1) We agree, and we have now run this comparison. SMT-only is our framework with Lean turned off, and it measures what Lean brings inside the framework.

Comparison with BarrierBench's full pipeline. We ran BarrierBench's released code without changing its method, and only matched the following settings to ours: the model (gpt-5.6-sol, reasoning effort high), the output limit per call, 2,400 s per instance, and 30 s per SMT query. DynaCertBench has 54 safety instances, and the comparison uses 42 of them. The other 12 are left out: BarrierBench cannot run 9 of them, and 3 are Extended instances with input constraints (Systems 87, 88, 89). BarrierBench's input format cannot express input constraints, so on these 3 it would solve a different problem. This follows the rule of Table 2(a), where each baseline is compared on the systems it supports. LLM2Cert verifies 10 of these 12.

Method32 instances from BarrierBench42 instances supported by both
BarrierBench, single prompt1415
BarrierBench, full pipeline (released solution library)2425
LLM2Cert, One-shot Proposal2732
LLM2Cert (Full)3035

Both methods verify all 22 instances that the BarrierBench paper reports as solved, so this run reproduces their results. LLM2Cert also verifies 8 of the 10 instances that the BarrierBench paper reports as unsolved, as stated in line 401. On the 42 instances, the one-shot setting gives 32 against 15, and the full pipeline gives 35 against 25.

Every baseline success is re-verified against the exact specification. Each baseline in Table 2(a) reports two numbers: Native is the number of systems it verifies under its own conditions, and Strict is the number of those certificates that still hold when re-checked in the LLM2Cert verification framework against the original DynaCertBench specification (lines 344–346). Under their own conditions (for example, an excluded ball around the origin, or δ\delta-sat counted as a pass), the five baselines of the submission verify 19 systems, and only 11 of them hold under the original specification: 4 certificates are only δ\delta-sat, and 4 SynNLF certificates fail the strict conditions (lines 371–373). On the same 51 systems, LLM2Cert verifies 39.

BarrierBench is re-checked in the same way. On its Z3 path, its verifier replaces sin and cos by Taylor polynomials before deciding, an approximation that the exact specification of DynaCertBench does not allow. Of the 25 certificates from its full pipeline, 6 contain sin or cos, and 3 of them (Systems 50, 53, 55) were accepted on its Z3 path, that is, after the Taylor substitution. We therefore re-verified every certificate BarrierBench accepted in the LLM2Cert verification framework, against the exact functions and the original sets. Of the 6 certificates with sin or cos, 5 are discharged by exact cvc5 queries. For System 55, cvc5 cannot decide the Lie obligation within 30 s, and the obligation is discharged by a Lean proof. All 25 certificates of the full pipeline and all 15 of the single prompt hold. Both sides of the table are therefore judged by the same exact specification.

The revision adds BarrierBench's full pipeline as Method 6 in Table 2(a) (synthesis: LLM, verification: SMT): Systems 42, Native 25/42, Strict 25/25, LLM2Cert 35/42.

(2) A short answer is in General Response 3.

Our contributions are DynaCertBench, a verification scheme that combines SMT and Lean, and the LLM2Cert agentic framework (lines 63–84). The differences are as follows.

1. DynaCertBench covers more tasks and system features.

DynaCertBench contains 105 systems covering stability, region of attraction, forward invariance and safety, for both continuous-time and discrete-time systems. It includes high-dimensional state spaces, control-input constraints, strong nonlinear coupling and parameterized systems, and every instance is posed with exact, unrelaxed certificate conditions. 25 systems have state dimension n≥5n \ge 5: 7 Literature-derived, 4 Extended and 14 New. Of the 11 Extended instances, 7 have input constraints, and the other 4 extend the domain to the whole space or raise the dimension. These numbers show how the benchmark extends task coverage and system composition.

AuthorsOpenReview ↗

Response (2/4)

2. A verification scheme that combines SMT and Lean.

The differences from the related work in Appendix B are as follows.

Prior workWhere the certificate or proof comes fromHow it is verified
Abate et al. (2021), Edwards et al. (2024), Taheri et al. (2025)Candidate certificates generated by a neural network or an LLMSMT, in some configurations with an excluded neighborhood of the origin or with Taylor approximations
Fulton et al. (2015), Rouhling (2018), Devadze et al. (2025), Doll & Shames (2026), George et al. (2026)Proofs constructed for a given system, or certificates of a specific form such as exact SOSDeductive verification, exact certificate checking, or a proof assistant
LLM2CertCandidate certificates and the required Lean proofs, both generated by an LLMEach exact, unrelaxed obligation is discharged by SMT or Lean

LLM2Cert connects automatic certificate synthesis with automatic proof generation. To our knowledge, it is the first to bring Lean into the end-to-end synthesis and verification of Lyapunov and barrier certificates for continuous-time and discrete-time dynamical systems. For obligations on which SMT times out, returns δ\delta-sat, or has no SMT encoding, the LLM writes a Lean proof that is checked by the kernel. The candidate certificate, the theorem statement and the hypotheses stay fixed during proof search. The framework therefore verifies the exact certificate conditions under explicit assumptions, without Taylor approximation or an excluded neighborhood of the origin, and never counts δ\delta-sat as verified. The “first” in contribution 2 refers only to this combination.

3. An agentic framework that uses the complementary strengths of the two verification backends.

LLM2Cert runs candidate generation, verification feedback, and proof generation and repair as one end-to-end pipeline. SMT discharges obligations quickly and returns counterexamples, and Lean handles the obligations that SMT leaves unresolved. The framework therefore combines the two backends at the level of individual obligations, keeps the obligations already discharged, and uses the feedback to search for new candidates or to repair proofs. Contribution 3 is this complete pipeline and the coverage and efficiency it brings.

W2 / Q2 / W3. Is the LLM router better than SMT-first? Why do Table 3 and Tables 9/10 disagree?

We thank the reviewer for suggesting a comparison with a deterministic SMT-first + Lean policy. It helps separate the effect of combining the two backends from the effect of how obligations are dispatched. The three questions are related, so we answer them together.

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.

What the LLM router does beyond that. Besides checking solver compatibility and moving to Lean after a timeout, the LLM router can skip SMT and send an obligation directly to Lean. The Full run made 19 such decisions (line 454), mostly because the obligation contains transcendental functions. SMT could in fact discharge 17 of these obligations within 30 s, and could not discharge the other 2 even within 900 s. In other words, sending these 17 obligations directly to Lean increased the verification time.

AuthorsOpenReview ↗

Response (3/4)

How we compare.

  • What is compared: the 81 fixed certificates and their 296 obligations. The certificates and the obligations stay fixed, and the five settings only change where each obligation goes first and how long it waits.
  • Five settings:
    • SMT 10 s + Lean
    • SMT 30 s + Lean
    • SMT 120 s + Lean
    • Dispatch by obligation type: dynamic conditions whose transcendental functions involve two or more state variables go directly to Lean, and the other obligations first get 30 s of SMT
    • LLM router: obligations are dispatched as the router actually decided in the Full run.
  • Time per obligation: all five settings use the same records. The SMT time comes from the All-SMT records and the Lean time from the All-Lean records (including the additional runs on the 15 certificates above). The differences between the settings therefore come only from the dispatch rule.
  • Time per certificate: as in the Full run, the obligations are checked in parallel, and the time of a certificate is the time until all of its obligations finish. It includes the time spent waiting for SMT when SMT does not discharge an obligation. For the LLM router, we also report the time including the router calls.

Results. All five settings verify the same 80 systems. The remaining system, System 81, has a radial-unboundedness obligation with no SMT encoding, so every setting sends it to Lean, and the All-Lean records do not prove it. The five settings therefore do not differ in how many systems they verify, only in time. Of the 80 systems, 50 take the same time under all five settings. Representative results for the other 30 are shown below.

Representative systemKey obligationSMT 10 s + LeanSMT 30 s + LeanSMT 120 s + LeanDispatch by typeLLM router
System 92Not discharged by SMT. The transcendental functions involve 4 state variables124144234114144
System 4Not discharged by SMT. The transcendental functions involve 1 state variable97117207117117
System 76Discharged by SMT at 10.6 s788111177811
System 104Discharged by SMT at 102 s416436102406436
System 71Discharged by SMT at 1.3 s. The transcendental functions involve 4 state variables1.31.31.3894894
Mean over the 80 systems99.494.3112.7116.9106.5

Times are in seconds, and bold marks the shortest time in each row. Including the router calls, the mean time of the LLM router is 111.6 s.

On this benchmark, the LLM router does not verify more systems, and its mean time is not shorter than that of SMT 30 s + Lean. At the same time, no setting is the fastest on every system: sending obligations to Lean early saves the time spent waiting for SMT, but sending an obligation that SMT could discharge quickly to Lean can cost several hundred seconds. SMT 30 s + Lean has the shortest mean time because almost all obligations that SMT can discharge finish within 13 s. For obligations like the one of System 104, where SMT needs longer, a 120 s cutoff is better. For obligations that SMT never discharges, a shorter cutoff or direct dispatch to Lean is better. The right dispatch rule and cutoff therefore depend on the structure of the obligations. We also note that in our paper, routing is a replaceable part of the framework. What the contributions stress is the gain the framework gets from the complementary roles of SMT and Lean.

Revisions

  • Section 3.2 states the SMT cutoff and that the LLM router can send obligations directly to Lean.
  • In Appendix Tables 9/10, Routed is renamed SMT-first + Lean and updated with the completed records.
  • Appendix E.3 adds the comparison of the five settings above.

We thank the reviewer for suggesting this comparison, which lets us show more clearly what combining the backends gains and how the dispatch rule matters.

Reviewer_XpqqOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces LLM2Cert, a framework that uses LLM-guided search for functional certificates and combines SMT solvers with Lean to verify the resulting proof obligations. It also presents DynaCertBench, a collection of 105 dynamical-system instances covering stability, region-of-attraction, forward-invariance, and safety specifications. The search of suitable functional certificates is an important and difficult problem. Building on existing LLM-based synthesis and verification approaches, the paper integrates LLM-generated Lean proofs, proof repair guided by the Lean compiler, and routing of obligations between SMT and Lean. This allows the framework to verify some obligations that SMT alone leaves unresolved.

Critical strengths
  • Combining SMT verification with LLM-generated, Lean-checked proofs is interesting, particularly for non-polynomial obligations that SMT solvers struggle to discharge.
  • The paper reports solving eight of the ten previously unresolved BarrierBench systems, demonstrating improved overall coverage.
  • DynaCertBench brings together over 100 instances covering several verification tasks, including systems with control constraints and nonlinear coupling.
  • The proof-repair ablation is useful. Structured feedback resolves 21 of 26 initially failed obligations, compared with 17 using raw compiler diagnostics, showing some benefit from targeted feedback.
Critical weaknesses
  • The methodological contribution beyond existing LLM-based certificate-synthesis frameworks needs clearer justification. The main addition appears to be Lean proof generation, repair, and routing between verification backends.
  • The evaluation does not clearly separate improvements due to the framework from those due to the underlying LLM and computational budget. The SMT-only ablation is useful, but it is not clear whether it faithfully reproduces the capabilities of prior LLM-based synthesis methods.
  • The benchmark curation requires stronger justification. In particular, excluding systems under Rule 4 because feedback can cancel nonlinearities may discount a meaningful controller-synthesis task.
  • It is unclear how the faithfulness of the generated Lean statements to the original verification problems is established. Lean checks proofs against these statements, but this does not establish that the dynamics, domains, certificate derivatives, and assumptions were correctly translated. The paper should clarify which parts of this translation are verified, independently validated, or trusted.
Questions for authors
  1. Table 3 and Appendix E.3 provide several breakdowns of Lean’s additional successes. How many involve no trigonometric functions? Could you discuss the mathematical features responsible for SMT difficulties?
  2. Which components of prior LLM-based certificate-synthesis methods are retained in the SMT-only baseline? Could you compare against a complete prior method using the same LLM and computational budget, reporting both success rate and runtime?
  3. How do you validate the translation into Lean definitions and theorem statements? In particular, are generated Lie-derivative expressions proved to equal the actual Lie derivatives of the encoded certificates along the encoded dynamics?
  4. Of the 21 obligations resolved through structured proof repair, how many required a substantive change in the mathematical argument, rather than corrections to syntax, lemma names, or type errors? Could you provide representative examples?
9 comments
AuthorsOpenReview ↗

Response (1/6)

Thank you for your patience while we ran the new experiments. Short answers to W1 and W2/Q2 are in General Response 3 and 1, and the full replies are below.

W1. What is new beyond the propose–verify–repair loop?

A short answer is in General Response 3.

Our contributions are DynaCertBench, a verification scheme that combines SMT and Lean, and the LLM2Cert agentic framework (lines 63–84). We are also encouraged by the experimental results. The differences are as follows.

1. DynaCertBench covers more tasks and system features.

DynaCertBench contains 105 systems covering stability, region of attraction, forward invariance and safety, for both continuous-time and discrete-time systems. It includes high-dimensional state spaces, control-input constraints, strong nonlinear coupling and parameterized systems, and every instance is posed with exact, unrelaxed certificate conditions. 25 systems have state dimension n ≥ 5: 7 Literature-derived, 4 Extended and 14 New. Of the 11 Extended instances, 7 have input constraints, and the other 4 extend the domain to the whole space or raise the dimension. These numbers show how the benchmark extends task coverage and system composition.

2. A verification scheme that combines SMT and Lean.

The differences from the related work in Appendix B are as follows.

Prior workWhere the certificate or proof comes fromHow it is verified
Abate et al. (2021), Edwards et al. (2024), Taheri et al. (2025)Candidate certificates generated by a neural network or an LLMSMT, in some configurations with an excluded neighborhood of the origin or with Taylor approximations
Fulton et al. (2015), Rouhling (2018), Devadze et al. (2025), Doll & Shames (2026), George et al. (2026)Proofs constructed for a given system, or certificates of a specific form such as exact SOSDeductive verification, exact certificate checking, or a proof assistant
LLM2CertCandidate certificates and the required Lean proofs, both generated by an LLMEach exact, unrelaxed obligation is discharged by SMT or Lean

LLM2Cert connects automatic certificate synthesis with automatic proof generation. To our knowledge, it is the first to bring Lean into the end-to-end synthesis and verification of Lyapunov and barrier certificates for continuous-time and discrete-time dynamical systems. For obligations on which SMT times out, returns δ-sat, or has no SMT encoding, the LLM writes a Lean proof that is checked by the kernel. The candidate certificate, the theorem statement and the hypotheses stay fixed during proof search. The framework therefore verifies the exact certificate conditions under explicit assumptions, without Taylor approximation or an excluded neighborhood of the origin, and never counts δ-sat as verified. The “first” in contribution 2 refers only to this combination.

3. An agentic framework that uses the complementary strengths of the two verification backends.

LLM2Cert runs candidate generation, verification feedback, and proof generation and repair as one end-to-end pipeline. SMT discharges obligations quickly and returns counterexamples, and Lean handles the obligations that SMT leaves unresolved. The framework therefore combines the two backends at the level of individual obligations, keeps the obligations already discharged, and uses the feedback to search for new candidates or to repair proofs. Contribution 3 is this complete pipeline and the coverage and efficiency it brings.

W2 / Q2. Does SMT-only represent prior methods, and how does LLM2Cert compare with a complete prior method under the same model and budget?

To the first question: SMT-only does not represent BarrierBench. It is our framework with Lean removed, an ablation that answers how much Lean contributes inside our framework. It keeps the loop shared by prior LLM methods (the model proposes a certificate and a controller, SMT checks them, and counterexamples are fed back to the next candidate), and it differs from BarrierBench in three ways:

  1. BarrierBench retrieves solutions of similar problems from a solution library and puts them in the prompt. SMT-only has no library.
  2. BarrierBench's Z3 and Yices paths replace sin, cos and exp by Taylor polynomials of order 5 or 7. SMT-only encodes every obligation exactly.
  3. BarrierBench does not check input constraints. SMT-only checks them as obligations.

Section 5.3 of the submission (lines 397–399) says “The SMT-only configuration corresponds to the setup of BarrierBench”. This sentence is misleading, and the revision removes it.

AuthorsOpenReview ↗

Response (2/6)

Comparison with BarrierBench's full pipeline. We ran BarrierBench's released code without changing its method, and only matched the following settings to ours: the model (gpt-5.6-sol, reasoning effort high), the output limit per call, 2,400 s per instance, and 30 s per SMT query. DynaCertBench has 54 safety instances, and the comparison uses 42 of them. The other 12 are left out: BarrierBench cannot run 9 of them, and 3 are Extended instances with input constraints (Systems 87, 88, 89). BarrierBench's input format cannot express input constraints, so on these 3 it would solve a different problem. This follows the rule of Table 2(a), where each baseline is compared on the systems it supports. LLM2Cert verifies 10 of these 12.

Method32 instances from BarrierBench42 instances supported by both
BarrierBench, single prompt1415
BarrierBench, full pipeline (released solution library)2425
LLM2Cert, One-shot Proposal2732
LLM2Cert (Full)3035

Both methods verify all 22 instances that the BarrierBench paper reports as solved, so this run reproduces their results. LLM2Cert also verifies 8 of the 10 instances that the BarrierBench paper reports as unsolved, as stated in line 401. On the 42 instances, the one-shot setting gives 32 against 15, and the full pipeline gives 35 against 25.

Every baseline success is re-verified against the exact specification. Each baseline in Table 2(a) reports two numbers: Native is the number of systems it verifies under its own conditions, and Strict is the number of those certificates that still hold when re-checked in the LLM2Cert verification framework against the original DynaCertBench specification (lines 344–346). Under their own conditions (for example, an excluded ball around the origin, or δ-sat counted as a pass), the five baselines of the submission verify 19 systems, and only 11 of them hold under the original specification: 4 certificates are only δ-sat, and 4 SynNLF certificates fail the strict conditions (lines 371–373). On the same 51 systems, LLM2Cert verifies 39.

BarrierBench is re-checked in the same way. On its Z3 path, its verifier replaces sin and cos by Taylor polynomials before deciding, an approximation that the exact specification of DynaCertBench does not allow. Of the 25 certificates from its full pipeline, 6 contain sin or cos, and 3 of them (Systems 50, 53, 55) were accepted on its Z3 path, that is, after the Taylor substitution. We therefore re-verified every certificate BarrierBench accepted in the LLM2Cert verification framework, against the exact functions and the original sets. Of the 6 certificates with sin or cos, 5 are discharged by exact cvc5 queries. For System 55, cvc5 cannot decide the Lie obligation within 30 s, and the obligation is discharged by a Lean proof. All 25 certificates of the full pipeline and all 15 of the single prompt hold. Both sides of the table are therefore judged by the same exact specification.

The revision adds BarrierBench's full pipeline as Method 6 in Table 2(a) (synthesis: LLM, verification: SMT): Systems 42, Native 25/42, Strict 25/25, LLM2Cert 35/42.

Running time (full pipeline, the same 42 instances).

BarrierBenchLLM2Cert
Verified instances (after strict re-check)2535
24 instances verified by both: mean time (median)28.5 s (14.5 s)153.4 s (81.1 s)
11 instances verified only by LLM2Cert: mean time (median)—635.6 s (288.9 s)

On the instances both methods verify, BarrierBench is faster. Almost all of the difference is in model calls: on these 24 instances, 147.3 s of LLM2Cert's mean 153.4 s are model calls and the solvers take 0.35 s. Its model outputs 4,350 tokens per instance on average, against 1,740 for BarrierBench. The 11 instances verified only by LLM2Cert are harder: they take 636 s on average, and 5 of them use Lean. On unverified instances, BarrierBench stops after 221 s on average (it runs out of refinement rounds), while LLM2Cert uses the full 2,400 s on each of its 7 unverified instances. BarrierBench's times are those of its own pipeline with its own verifier. The strict re-check is our audit after the runs and is counted in neither side's time. For the 25 BarrierBench certificates, it took 159 s in total, 6.4 s per certificate on average.

AuthorsOpenReview ↗

Response (3/6)

We think the difference in model time comes mainly from what the two prompts ask for. BarrierBench's prompt asks the model to “be concise ... without long explanations” and to output only two lines, BARRIER: and CONTROLLER:. On these 24 instances, a reply has 52 characters on average. Our prompt asks the model to write in construction_summary how it built the candidate, including the closed-loop Lie derivative, and to separate what holds algebraically from what the verifier still has to check. This derivation is not used in verification, only for feedback and human inspection. On these 24 instances, it has 673 characters on average.

W3. Rule 4 excludes systems where feedback cancels the nonlinearity, which may drop meaningful controller-synthesis tasks

We agree that designing a controller that cancels the nonlinearity is itself a meaningful controller-synthesis task. The submission did not explain the purpose and the effect of this rule, so we give the details below.

What was excluded. Rule 4 excludes 54 records (Table 14), all from BarrierBench and all among the 90 problems that the BarrierBench paper reports as solved. They include all 9 BarrierBench records with n ≥ 5 (lines 1559–1563). There are three reasons for exclusion (line 1563): feedback cancels the nonlinear terms completely (feedback linearization), the dynamics split into decoupled linear chains (linear-chain decoupling), or the dimension is padded with passive states that take no part in the dynamics (passive state padding).

Why they were excluded. Both DynaCertBench and BarrierBench aim to test the synthesis and verification of certificates on nonlinear closed loops. For example, in BarrierBench's first record S000, the released controller u₀ = −x₂x₃ − 4x₁, u₁ = −x₁x₃ − 4x₂, u₂ = −5 + x₁x₂ − 5x₃ turns the closed loop into ẋ = −diag(6.5, 6.5, 5)x. The certificate x₁² + x₂² + x₃² − 0.25 is then enough, and verification reduces to polynomial inequalities. Existing methods all solve such problems, so they do not separate the verification ability of different methods. We therefore excluded these feedback-controlled systems.

Controller synthesis is not removed. Of the 32 retained BarrierBench instances, 18 still require both a controller and a certificate. The Extended tier adds the input constraints |u| ≤ 1 or |u| ≤ 5 to 3 BarrierBench systems (S002, S011, S024), so the nonlinear terms can no longer be cancelled directly. BarrierBench's input format cannot express input constraints, so it can only run without them, and the controllers it returns on these 3 instances all exceed the bounds. This shows that adding input constraints really changes the task, and these 3 instances are therefore left out of the comparison with BarrierBench (see W2). LLM2Cert verifies all 3.

Effect on the scope of the evaluation. Rule 4 does not remove all systems with controllers. It only excludes records whose nonlinearity can be cancelled completely or whose dimension is padded with passive states. Our results therefore do not cover systems in which “every state has its own input and the system is fully feedback-linearizable”. We think that removing some of these systems while bringing others back with control constraints adds to the diversity of the benchmark. This is also why DynaCertBench is split into the Literature-derived, Extended and New tiers.

W4 / Q3. Is the Lean statement faithful to the original problem, and are the generated Lie-derivative expressions proved to equal the actual Lie derivatives?

Q3: The submission did not prove this, but we now prove it for every reported certificate. 71 of the 81 verified certificates are continuous-time, and the lemmas for all 71 pass the Lean kernel. The other 10 are discrete-time certificates and have no Lie derivative. The lemmas are generated by a program from the expression tree, with no model call.

W4: We agree. This is a recognized problem in formal verification and an active research topic. Lean and SMT can only check the encoded statement, not whether the encoding is faithful to the original problem. Recent work points out this problem and tries to address it:

  • Formal statements in Lean benchmarks disagree with the original problems. Ospanov et al. (2025) found that in more than half of the miniF2F problems the formal statement disagrees with the original problem, and they corrected these problems one by one and released miniF2F-v2. Ammanamanchi et al. (2026) audited five widely used Lean benchmarks and point out that the Lean kernel only confirms that a proof holds for the given statement, not that the statement is faithful to the original problem.
  • Checking whether a formal statement keeps the original meaning. FormalAlign (Lu et al., 2025) trains a model to judge whether an informal and a formal statement agree, and CLEVER (Thakur et al., 2025) asks a model to prove that the specification it writes is equivalent to a human-written one.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response (1/2)

We thank the reviewers for their careful reading, and we apologize for the late response: the reviewers asked for several meaningful and well-founded new experiments (a comparison with the full BarrierBench pipeline, an independent one-shot run, and strict re-checks of baseline certificates), and we wanted to report their complete results. We are encouraged that they find the combination of SMT and Lean “interesting” (Xpqq) with “a clear benefit” (xZMM), and the benchmark of “significant value to the research community” (o2na). We will revise the paper accordingly. Four shared points are answered below and details are in the individual replies.

1. Comparison with the full BarrierBench pipeline (Xpqq-W2/Q2, xZMM-W1/Q1). Our SMT-only ablation is not BarrierBench's pipeline, so we ran BarrierBench's released code, unmodified, with the same model, reasoning effort and 2,400 s budget as LLM2Cert. Of the 54 safety instances in DynaCertBench, BarrierBench can run 45. Three of them are Extended instances with input bounds, which BarrierBench's input format cannot express, so we compare on the remaining 42. This follows the rule of Table 2(a), where each baseline is compared on the systems it supports. By its own verifier, BarrierBench's full pipeline verifies 25 of the 42 (15 for its single-prompt baseline), and LLM2Cert verifies 35 (32 for its one-shot run). BarrierBench's verifier is not exact: on its Z3 path it replaces sin and cos by Taylor polynomials, an approximation that DynaCertBench does not allow, and 3 of its 25 certificates (Systems 50, 53, 55) were accepted on this path. We therefore re-verified every BarrierBench certificate in the LLM2Cert verification framework (exact SMT queries, and kernel-checked Lean proofs where SMT cannot decide), against the exact functions and the original sets, and all of them hold. Among the 6 certificates of its full pipeline that contain sin or cos, 5 are discharged by exact cvc5 queries and 1 needs a Lean proof. Both sides are thus judged by the same exact specification. Both methods verify all 22 originally solved instances retained from BarrierBench, and, as reported in the paper (line 401), LLM2Cert also verifies 8 of the 10 instances that BarrierBench reports as unsolved. BarrierBench is added as Method 6 in Table 2(a), where every baseline is re-checked in the same way by the LLM2Cert verification framework: the five original baselines verify 19 systems under their own conditions, only 11 of these hold under the exact conditions, and LLM2Cert verifies 39 of the same 51 systems (lines 371–373).

2. Independent one-shot run (xZMM-W4, o2na-Q1). The One-shot row of Table 2(b) was reconstructed from the Full trajectories, where the first candidate shares the 2,400 s budget with later rounds. We have now run the no-feedback configuration independently: one candidate per system, one Lean attempt per obligation, and the whole budget for that candidate. It verifies 64/105, against 81/105 for Full. Because this configuration turns off both new candidates and Lean repair, the gap measures the whole feedback loop. The effect of proof repair alone is measured in Table 4. Table 2(a) now reports the independent value as a separate row (Synthesis: LLM, Verification: SMT+Lean). Figure 3(c) is kept, because it shows how the Full run progresses round by round.

AuthorsOpenReview ↗

General Response (2/2)

3. What we think is new (Xpqq-W1, xZMM-W1/Q1). We agree the propose–verify–repair loop is not new. FOSSIL, FOSSIL 2.0 and BarrierBench all use it, and we don't claim it. What we claim is narrower. First, DynaCertBench: 105 systems over four tasks, all posed with the exact conditions, with no excluded ball around the origin and no Taylor surrogate. Second, deciding each obligation either by an exact SMT query or by a kernel-checked Lean proof. On the same 81 frozen certificates, SMT alone verifies 59 even with 900 s per obligation. The other 22 need Lean, and 11 of the 25 obligations SMT leaves open contain no sin or cos at all, so this is not only a trigonometry issue. Third, running this end to end. Against BarrierBench's released pipeline with the same model and budget, both methods solve every instance BarrierBench reports as solved. The difference is on the ten it reports as unsolved, where LLM2Cert verifies eight. We were glad that xZMM found the obligation-level split between SMT and Lean practical, and that o2na read the separation of proposal and verification as a commitment to reliability.

4. Two quantities shared the label “Routed” (xZMM-W3, o2na-W1). Table 3 reports the path of the end-to-end Full run with the LLM router. It is 81/81 by construction, because the 81 fixed certificates are the ones Full verified. Tables 9/10 report a fixed SMT-first policy composed from the All-SMT and All-Lean records. In the submission, 17 obligations in 15 certificates had no complete Lean attempt in the All-Lean records, which gave 66/81. We re-ran All-Lean on these 15 certificates to obtain complete Lean attempts, and recomputed the SMT-first composition from the completed records: it verifies 80/81. The rows in the appendix will be “SMT-first + Lean”.

We welcome any further questions.

AuthorsOpenReview ↗

Revised PDF Uploaded: Summary of Changes

Dear Reviewers and AC,

Greetings from the authors! Thank you for the careful reviews. Most of our discussion time went into the experiments you asked for. The revised PDF (changes in blue) adds:

  • BarrierBench's complete pipeline as a baseline, run with the same model and budget (Method 6, Fig. 3(a), Appendix E.6);
  • an independent one-shot run (64/105) and the completed SMT-first policy (80/81, Tables 10–13);
  • appendix analyses of the trust boundary, SMT failures, and common-subset times (Tables 5, 14–16).

The conclusions are unchanged, and the stronger baseline makes the gap clearer. Counting only strict results, LLM2Cert verifies 54.9, 47.6, and 31.0 percentage points more systems than the non-LLM baselines, BarrierBench with one proposal, and BarrierBench's full pipeline. The gain comes from combining SMT with Lean, and the router is replaceable.

Two notes. BarrierBench's Strict entry is now 22/25 rather than the 25/25 in our earlier replies: all 25 certificates hold, but its verifier accepted 3 of them only through a Taylor approximation, so we no longer count them as proved by BarrierBench. Also, new tables are numbered in sequence, so appendix table numbers differ from the submission (Tables 1–4 are unchanged), and our replies use the new numbers.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.