acceptodds
Withdrawn from ICLR 2027

On the Cost of Certifying Neural Lyapunov Functions

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

A neural Lyapunov function certifies stability only where it is formally verified, and branch-and-bound verification can dominate the cost of current pipelines, varying by orders of magnitude between certificates of the same system. We show that this cost has two parts, both governed by the certified radius: the size of the largest box around a point that the verifier's bounding method can certify. The frontier part is geometric. Where the maximal level set touches the set on which the specification fails, the radius collapses: any verifier that checks the clauses separately on axis-aligned boxes needs boxes at slack , whatever its bounding method, with the dimension and the number of faces or kinks at the contact (for a nondegenerate contact and not flat along any coordinate). The bulk part, paid everywhere, scales with the integral of the inverse -th power of the radius, which a few thousand sampled points estimate without running branch-and-bound. On 25 certificates in two to six dimensions, the predicted exponents match at 22 contacts, and the estimate stays within a single-digit factor of the measured per-clause cost across five orders of magnitude. The decomposition turns the choice of the certified level into a computation, enlarging the certified region of a released quadrotor certificate -fold, and shows that certified training moves the frontier but not consistently the bulk.

Primary area:
learning on time series and dynamical systems
Keywords:
Lyapunov functions, verification-aware learning, formal verification, nonlinear control, stability certification, learning-based control

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_QFPxOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The computational cost of formally verifying neural Lyapunov functions is investigated. Rather than addressing how a Lyapunov function is learned, the work focuses on the subsequent formal verification step. The considered verifiers use branch-and-bound over axis-aligned boxes together with different bounding methods. The authors state that verification cost can be separated into a frontier component, which depends on the geometry close to the maximal certifiable level, and a bulk component, which is characterized through a so-called certified radius. The analysis is demonstrated on systems with two to six continuous state variables.

Critical strengths
  • Deriving the computational cost of formal verification is a relevant research direction.

  • The distinction between a frontier cost and a bulk cost is somewhat interesting.

  • The experiments demonstrate the difference between per-clause and conjunction-aware verification.

  • According to the experiments, useful predictions of the cost for the investigated certificates are obtained.

Critical weaknesses
  • The relevance of the contribution to machine learning and, consequently, to ICLR is not obvious. The paper itself states that what makes a learned Lyapunov certificate trustworthy is the formal check that follows training, which is the topic studied in this paper. Thus, the main contribution seems much closer to formal verification and computational geometry than to machine learning and probably better fits to conferences such as Computer Aided Verification (CAV).

  • All results are tied to a particular class of verification algorithms. The paper demonstrates that a different verification strategy can substantially alter the picture and the derived computational complexity is unfavorable as the number of continuous state variables increases. However, if this scaling is mainly a property of the selected algorithm and its axis-aligned representation, the natural conclusion appears to be that this verification approach should be replaced by algorithms that scale better with state dimension. In that case, the presented complexity characterization may become much less relevant once another verification algorithm is used.

  • A complexity result for the underlying certification problem itself would be substantially more relevnt. A lower bound that applies independently of a particular verifier or set representation would remain relevant when verification algorithms improve. In contrast, characterizing the cost of a specific branch-and-bound architecture risks characterizing a limitation of current implementations rather than a fundamental difficulty of certification.

  • Other set representations are extensively used in verification and reachability analysis, including polytopes, zonotopes, and constrained zonotopes. Such representations can capture correlations between state variables that axis-aligned boxes cannot. The manuscript does not establish how its conclusions change when such representations are used. Consequently, it is difficult to determine which part of the reported dimensional dependence is inherent to the problem and which part results from the selected representation and subdivision scheme.

  • Also, reachability analysis is largely absent from the discussion. This is surprising because the objective is ultimately to establish properties of the trajectories of a dynamical system. The paper should discuss how the proposed complexity analysis relates to reachability-based verification and under which circumstances neural Lyapunov verification is expected to be computationally preferable.

  • The system class is somewhat restrictive. The theoretical setting assumes discrete-time dynamics. However, many technical systems are naturally modeled by differential equations. It is unclear whether the proposed frontier and bulk analysis can be transferred to continuous-time systems.

  • The paper is rather difficult to read. Several substantial mathematical ideas are introduced in quick succession, while relatively little intuition and reader guidance are provided before the detailed results. Also, the language can be improved.

Questions for authors
  1. Which of the complexity results are properties of the certification problem itself, and which are properties of the particular branch-and-bound verification algorithms considered in the paper?

  2. Could a lower bound be obtained for the underlying problem of certifying the Lyapunov region rather than for a particular class of box-based verifiers?

  3. How would the complexity change if the verifier used a different set representation?

  4. How does the proposed analysis compare with reachability analysis? Why is this alternative not mentioned, and how would its computational complexity compare with the presented approach?

  5. Could the analysis be extended to continuous-time dynamics described by differential equations?

  6. What is the machine-learning-specific scientific question addressed by the paper?

  7. How should the scaling results be interpreted if future verification algorithms no longer rely on the analyzed subdivision scheme? Is there a part of the theory that the authors expect to remain unchanged under fundamentally different verification methods?

Reviewer_8YeQOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Neural Lyapunov certificates for the same system can have very different verification costs. The authors acknowledged this bottleneck and investigated this issue. The paper uses the certified radius to characterize frontier and bulk costs. The experiments suggest that certified training shifts the frontier without consistently reducing bulk cost.

Critical strengths
  • The problem studied is important.
  • The framework could help address this problem.
Critical weaknesses
  1. The paper is difficult to follow. Notations are used before they are defined.

  2. The abstract does not state a clear problem. It describes frontier and bulk costs and concludes that certified training “moves the frontier but not consistently the bulk.” What does this statement mean, and what is the contribution?

  3. The abstract reports matching exponents at 22 of 25 contacts. What about the remaining three cases? The one-shot certification result in Section 5 is illustrated by a single example.

Minor comments

  1. What is V? It appears in the abstract and introduction before it is defined.

  2. Is the certified radius simply a margin?

  3. The introduction states that the released certificates are verified 0.03% to 24% below the maximal certifiable level. How can a percentage be a distance?

Questions for authors

See weaknesses

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

This paper studies the computational cost of formally verifying neural Lyapunov certificates, motivated by the observation that verification complexity can differ substantially even among certificates for the same dynamical system. Rather than proposing a new certificate synthesis method, the authors investigate the factors governing the cost of branch-and-bound (BaB) verification of Lyapunov decrease and state-containment conditions. The analysis centers on the notion of a certified radius, which measures the size of a local box that can be verified using a given bounding procedure. The authors distinguish two sources of computational cost: a frontier component, determined by the geometry of the contact between the maximal certifiable level set and the violation set, and a bulk component, characterized through an integral involving the certified radius. They establish complexity bounds for certain classes of verifiers, propose a radius-based cost estimator and a procedure for selecting certification levels, and examine how certificate training affects verification complexity. The theoretical findings are evaluated on 25 certificates spanning two to six state dimensions, with additional experiments investigating the relationship between predicted and observed verification costs and the size of certified regions.

Critical strengths
  1. The paper addresses a meaningful computational challenge in the formal verification of learned certificates. The cost of verification is often a major obstacle to the practical use of neural certificates, and understanding why certain certificates are significantly more expensive to verify than others is an important research question. I particularly appreciate that the paper moves beyond reporting verification runtimes and seeks to explain the factors responsible for these differences. Such an understanding could provide useful guidance for developing certificates and learning procedures that are more amenable to formal verification.

  2. The distinction between frontier and bulk verification costs offers a useful perspective on the sources of computational complexity. In particular, connecting the geometry of the certification boundary and the local certified radius to the overall cost of verification is an interesting contribution. Although some of the underlying mathematical tools, including continuous amortization, are established, their application to this problem provides useful insights. The experimental evaluation is also a strength: the predicted contact exponents agree with measurements in 22 of the 25 cases, and the radius-based estimator captures variations in verification cost across a broad range of certificates. These results provide meaningful evidence for the proposed characterization within the evaluated settings.

Critical weaknesses
  1. One of the practical contributions of the paper is a procedure for selecting a near-maximal certifiable level under a computational budget. However, the experiments do not fully evaluate the complete procedure described in Algorithm 1. In particular, Section 6.4 reports experiments using a fixed slack and without the counterexample-search component. The full procedure, including budget-based slack selection and adjustments following unsuccessful verification attempts, is therefore not adequately assessed. While the reported improvements in certified-region size are encouraging, they do not establish how reliably or efficiently the complete procedure operates under a prescribed computational budget. This concern is particularly relevant given the sensitivity of the radius-based cost estimator near the maximal certifiable level. Appendix C.3 reports substantial variability between independent estimates for some quadrotor certificates. Since this is precisely the regime in which accurate cost prediction becomes important for level selection, a more complete evaluation of the proposed procedure would strengthen the practical contribution.

  2. The theoretical results provide useful insights, but their applicability depends on the verification procedures considered. In particular, Theorem 4 relies on assumptions that are not fully satisfied by the practical verifier, while the frontier lower bound is established for per-clause verification over axis-aligned boxes. Although the paper also investigates conjunction-aware verification and acknowledges these limitations, the connection between the theoretical cost characterization and the practical budget-aware level-selection procedure remains insufficiently validated. A clearer explanation of how the per-clause radius-based estimate supports the conjunction-aware verifier, especially near the maximal certifiable level, would strengthen the practical contribution.

Questions for authors

Q1. Section 6.4 reports fixed-slack runs without the attack component. What evidence supports the automatic budget-based slack selection in Algorithm 1 beyond these runs? A limited evaluation against fixed-slack selection under matched budgets, or a narrower statement of the practical claim, would address this concern.

Q2. How is the per-clause radius-based estimate calibrated for the conjunction-aware verifier used in Algorithm 1? In particular, how does the procedure account for the estimator variability near the maximal level reported in Appendix C.3?

Q3. Does the budget MM apply to each verification attempt or to the complete procedure? Please clarify how preliminary runs and unsuccessful attempts are accounted for, and report preprocessing costs separately where they are not included in the domain budget.

Q4. Could the authors clarify which aspects of the certified-radius and frontier–bulk analysis could extend to neural barrier verification methods [1, 2], and which depend specifically on deterministic Lyapunov geometry or the considered verification procedures? A brief discussion distinguishing these methods from scenario-, Lipschitz-, and conformal-based certification [3–5] would help clarify the scope and limitations of the framework.

References

[1] H. Zhang, Z. Qin, S. Gao, and A. Clark, “SEEV: Synthesis with Efficient Exact Verification for ReLU Neural Barrier Functions,” NeurIPS, 2024.

[2] F. B. Mathiesen, S. C. Calvert, and L. Laurenti, “Safety Certification for Stochastic Systems via Neural Barrier Functions,” IEEE Control Systems Letters, vol. 7, pp. 973–978, 2023.

[3] A. Salamati, A. Lavaei, S. Soudjani, and M. Zamani, “Data-driven verification and synthesis of stochastic systems via barrier certificates,” Automatica, vol. 159, Art. 111323, 2024.

[4] S. Taheri and M. Zamani, “Neural Barrier Certificates for Stochastic Control Systems,” IEEE CDC, pp. 7695–7700, 2025.

[5] M. Tayal, A. Singh, P. Jagtap, and S. Kolathaya, “CP-NCBF: A Conformal Prediction-based Approach to Synthesize Verified Neural Control Barrier Functions,” arXiv:2503.17395, 2025.

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

Related papers

Discussion (0)

Sign in to comment.