CS Paper Radar

LLM2Cert: LLM Synthesis of Certificates with SMT/Lean Verification

Zhipeng Cao, Peiyang Song, Nikolaus Vertovec, Weiru Cui, Zhihao Yang, Mingkang Liu, Luxia Lin, Bai Xue, Alessandro Abate

eess.SY cs.AIcs.LGmath.OC ·submitted 2026-10-21 23:09 UTC · v1
benchmarkcode/data

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 ($77.1\%$), a $17.1$ percentage point improvement over one-shot proposal without feedback. On the 81 fixed certificates, LLM2Cert verifies 22 that All-SMT leaves unresolved. Code and data are available at https://github.com/FormalCert-AI/llm2cert.

Comment
59 pages, 3 figures. Equal contribution: Zhipeng Cao and Peiyang Song. Equal advising: Bai Xue and Alessandro Abate

Closest papers

Nearest neighbours by meaning across the whole index.

Unified Overview of Safety Certificate Functions: Techniques from Hamilton--Jacobi Reachability and Control Barrier Functions

cs.RO eess.SY ·2026-11-05 ·Hao Wang, Max Cohen, Zeyuan Feng, Donggeon David Oh, Oswin So +7 more
surveybenchmark similarity 0.59
Abstract

Safety is a central concern in modern autonomous systems. Safety certificates---functions whose existence guarantees that a system meets its safety specification---have long been used as a principled tool for rigorously reasoning about safety. Methods for synthesizing such certificates are scattered across research areas, with little guidance on when to use a particular approach. This tutorial provides a holistic treatment of safety certificate synthesis centered on two widely used families: Hamilton--Jacobi (HJ) reachability analysis and control barrier functions (CBFs). For each family of methods, we first introduce its general formulation, along with classical and learning-based tools for certificate synthesis. Next, we introduce two benchmark problems consisting of vehicle systems of differing complexity to assess the certificate quality of different synthesis methods and their effectiveness in safety-critical control. We use these benchmarks to compare various methods and provide practical guidance for selecting an approach.

0.24

LLM-Assisted Bi-Approximate CHC Solving

cs.LO cs.AI ·2026-10-16 ·Baiting Jiang
similarity 0.59
Abstract · 22 pages, 8 figures, 5 tables

Constrained Horn clause (CHC) solvers often struggle to discover deep counterexamples whose derivations may require extensive rule unfolding. Although large language models (LLMs) can propose long-range symbolic relations, prior work on formally checked LLM-assisted verification has mainly focused on generating inductive invariants and concrete traces. We exploit this broader capability through Derivation Power Under-approximations (DPUs). Each DPU is a solver-certified under-approximation of the relation induced by a multi-step CHC derivation. An LLM proposes each DPU with symbolic intermediate-state witnesses that enable SMT validation without introducing additional quantifiers. Validated DPUs can be composed and reused soundly. Building on this mechanism, our LLM-assisted framework HornCraft combines invariant generation for over-approximation with DPU generation for under-approximation in CHC solving. On 260 linear and nonlinear integer-arithmetic CHC-COMP benchmarks left unresolved by a 30-minute Spacer run, HornCraft returns certified verdicts for 228 instances. It certifies 42 instances as unsafe, compared with 22 when DPU construction and reuse are disabled.

0.23

Barrier Certificate Synthesis for Non-Polynomial Robotic Dynamics via Polynomial Lifting

cs.RO eess.SY ·2026-09-19 ·Shivam Chaubey, Francesco Verdoja, Shankar Deka, Ville Kyrki
similarity 0.59
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

Safe operation of robotic systems requires trajectories to remain within a prescribed safe set under admissible control inputs. Barrier certificates provide such guarantees by certifying a controlled-invariant region within that set. Sum-of-squares optimization offers a systematic way to synthesize such certificates, but its direct application requires polynomial dynamics, excluding common robotic nonlinearities, including trigonometric terms. We address this limitation using exact polynomial lifting, which replaces non-polynomial dynamics with polynomial-augmented dynamics subject to lifting-induced algebraic constraints, preserving nonlinear geometry without approximation. We formulate lifted-domain joint barrier synthesis that computes a certificate with a state-feedback control witness and develop a sampled-data safety filter for zero-order-hold implementation. To assess whether the benefits of lifting persist across synthesis frameworks, we also adapt a sample-guided successive-barrier method to the lifted representation. On coordinated-turn and planar multirotor models, exact lifting improves certified coverage in both methods: at matched sample sizes, lifted successive-barrier synthesis achieves higher coverage with fewer barriers and lower computational cost, while lifted joint barrier synthesis provides higher coverage and lower computational cost than the finest tested piecewise resolution. In closed-loop experiments, the safety filter maintains feasibility and safety across all evaluated trajectories, reduces spatial conservativeness, and requires less intervention for both models.

0.30

SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification

cs.AI cs.LGmath.OC ·2026-09-01 ·Swapnil Bhattacharyya, Mayank Baranwal
top venuebenchmark similarity 0.58
Abstract · Accepted to EMNLP 2026 Findings

Large Language Models (LLMs) have shown remarkable promise in translating and reformulating complex mathematical optimization problems across modeling languages. However, validating such transformations through empirical solver executions alone is unreliable, as solver outcomes may be affected by local minima, structural timeouts, numerical artifacts, and subtle semantic divergence between formulations. We introduce SOVER, an LLM-assisted SMT framework that separates semantic mapping from formal certification: Z3 checks domain cross-feasibility and global objective-order preservation for mixed-integer linear formulations, while dReal provides tolerance-aware feasibility/range and $ε$-argmin checks for continuous nonlinear formulations. We also introduce NLEquiv-150, a public benchmark of 100 equivalent and 50 deliberately hard non-equivalent nonlinear reformulation pairs. With LLM-extracted mappings, SOVER classifies 149/150 pairs (99.33%) correctly, including all 50 hard negatives; the sole error is an incomplete mapping extraction.

0.52

Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds

cs.LO ·2026-11-13 ·Xinyuan Guo, Andersen Ang
theory similarity 0.58
Abstract · 26 pages, 2 figures, 8 tables

Performance-estimation certificates describe worst-case bounds for optimization algorithms. Turning a certificate into a formal theorem requires exact verification of its algebra and a connection between its coordinates, constraints and objective and the intended function-level problem. Lean-PEP provides a reusable interface for this task. It checks a submitted source and exact certificate against a supported canonical finite model, and a parameterized analytic theorem transfers the resulting finite bound to every admissible algorithm trajectory. Generated computation proofs discharge the obligations that depend on each certificate. An additional capture entry checks the numerical record and reconstruction policy. The implemented two-step proximal-gradient consumer verifies a new input with normalized bound 62500/499999, and a fixed eight-configuration batch yields seven distinct payloads with accepted certificates and executed Lean proofs. PG/GD cases and one-step attainment witnesses establish the corresponding algorithmic conclusions, and a fresh installation reproduces consumption of the supplied input. These results show how new certificate data can reuse a proved analytic interface to obtain function-level bounds within the supported models.

0.51

Beyond the Answer Key: Robustness Evaluation of Large Language Models for Step-Level Mathematical Verification

cs.AI ·2026-08-28 ·Fateme Mazdarani, Carlos Toxtli
publishedbenchmark similarity 0.57
Abstract · Accepted to 2026 IEEE International Conference on Machine Learning and Applications (ICMLA)

Large language models (LLMs) are increasingly used as graders, verifiers, and process auditors, but most mathematical evaluations still emphasize final-answer accuracy. This can obscure whether a model can verify a non-canonical but valid solution trace. We introduce a controlled linear-equation benchmark for evaluating LLMs in the evaluator role. Each instance asks the model to judge final-answer correctness, step-level trace correctness, and the first incorrect step. Our evaluation of state-of-the-art open LLMs reveals a significant robustness gap: models that accurately evaluate canonical solutions often fail when presented with perturbed but logically equivalent variants. Across GPT-OSS 20B, Qwen3-14B, and Phi-4-Reasoning, base models perform well on canonical traces but degrade substantially on perturbed traces, especially for error localization. On valid perturbed traces, base-model false-rejection rates reach 75.6-85.3%, showing strong sensitivity to canonical solution form. Supervised fine-tuning, distillation, and test-time compute improve robustness in some settings, but gains are model dependent and can trade off against canonical performance. The results show that reliable process-level verification remains challenging, and evaluator robustness should be measured separately from solver accuracy, even in a simple algebraic domain with exact ground truth.

0.56

Scalable Neural Safety Certification via Monotonicity

eess.SY cs.LGmath.OC ·2026-11-08 ·Amirreza Alavi, Majid Zamani, Saber Jafarpour
similarity 0.57
Abstract

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems--monotonicity--can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.

0.13

Floating-point, exact and certified computation for control: paradigms, pitfalls, and how to combine them

cs.SC ·2026-11-11 ·Christina Katsamaki, Fabrice Rouillier
similarity 0.57
Abstract

Many questions in linear systems theory have a discrete answer: is a polynomial Hurwitz, is a 2-D system structurally stable, is the peak gain finite, which solution of a Riccati equation is stabilizing? Algorithms implemented in floating point usually answer such questions, but often with a limited, or even no, guarantee on the result, which depends on a tolerance fixed a priori. Computer algebra and interval arithmetic provide other ways of computing, which give guarantees on the result, but usually at a higher cost. In this paper, we propose a short guide to these approaches: floating-point, exact, multiprecision and interval arithmetic, certified root isolation and certified Newton methods. Using small examples from control theory (each of them runs in a few seconds), we show what each approach guarantees and in which situations it fails, and how several approaches can be combined, for example by certifying a numerical solution, or by reducing a problem exactly before solving it with certified real solving. We then revisit the structural stability of 2-D systems (with and without parameters) and the computation of the $H_\infty$ norm, and we list the available implementations. The main examples are given as reproducible worksheets based on the PACE ecosystem.

0.32