A neural controller can be proved safe with a certificate: a learned function that must satisfy an inequality at every state. For stability, this is a Lyapunov function whose value must decrease along every trajectory. For safety, it is a barrier function whose sign marks a region the system can never leave. Most practical systems find such certificates by alternating two steps. A learner fits the certificate, and a falsifier hunts for states where the inequality fails and feeds them back as training data. The loop ends when the falsifier gives up and an exact solver confirms there is nothing left to find. Everything depends on the falsifier. If it misses a violation, the loop either hands the exact solver an unfixable problem or stops with no verdict at all. The exact solvers themselves are slow and stop scaling somewhere around six to eight state dimensions.
This note argues that gradient-based falsifiers fail in a specific, predictable way. They stall at saddle points of the violation function, meaning places where the slope is zero but the function still rises along a few directions. These saddles come from the structure of the problem, not from bad luck. The equilibrium of any Lyapunov problem is always a stationary point of the violation. Points patched by earlier training rounds become new ones. Near the edge of the stable region, the unstable equilibria of the dynamics produce flat plateaus in trajectory-based attack losses. We propose a falsifier that follows curvature, computing Hessian-vector products to find rising directions at stalled points. We also propose a benchmark with planted violations to test whether this beats random restarts and random-noise perturbation once the state dimension grows.
Core Claim
Write the falsifier's objective for a Lyapunov candidate $V$ and closed-loop dynamics $\dot x = f(x)$ with equilibrium $f(0)=0$ as the violation function $g(x) = \nabla V(x)^\top f(x)$. A counterexample is any state with $g(x) \ge 0$. Because $\nabla V(0)=0$ and $f(0)=0$, the gradient of $g$ vanishes at the origin for every candidate. Its Hessian there is
$$H_0 = P A + A^\top P, \qquad P = \nabla^2 V(0),\; A = \partial f/\partial x\,(0).$$
Suppose $H_0$ has one small positive eigenvalue $\mu$ while the rest are at most $-\kappa$. Then violations exist arbitrarily close to the origin, but only inside a thin cone around one eigenvector. The cone's half-angle is set by $\sqrt{\mu/\kappa}$, so its share of a small sphere shrinks roughly like $(\mu/\kappa)^{(d-1)/2}$ in dimension $d$. That scaling comes from the solid-angle fraction of a cone of fixed half-angle.
This is the origin case, and it is the easy one: it motivates the proposal but does not justify it. A one-time eigenvalue check of $H_0$ settles it, which is essentially what linearization-based local certification already does. The claim with real content is that the same geometry recurs at stationary points of $g$ that nobody knows about in advance. These include points where an earlier training round patched a counterexample, leaving a local bump with thin violation ridges beside it, and saddle-shaped regions of trajectory losses near the boundary of the region of attraction (the set of starting states that eventually return to equilibrium). At such points, three standard tools struggle. First-order ascent stalls. Random restarts need exponentially many samples in $d$ to land in the cone. Isotropic noise escapes slowly when the rising curvature $\mu$ is small. A Lanczos or power iteration, driven by Hessian-vector products through $V$, $f$, and where needed an ODE solver, finds the rising direction in a number of products that grows only logarithmically with $d$. The falsifier then either returns a counterexample or ends at an approximate second-order stationary point and reports the curvature measured there. That report is a local statement, not a proof.
Relation to Prior Work
The motivating evidence comes from verification. Efficient Verification and Falsification of ReLU Neural Barrier Certificates reduces barrier checking to many small optimization problems, one per linear region of a ReLU network. It reports that on nonlinear dynamics these problems are non-convex, so its solvers settle at suboptimal points and return an inconclusive "?". The authors do not analyze why the solvers stall. We supply that analysis and a remedy for the falsification half of their pipeline, though a "?" on a truly safe certificate cannot be resolved by any falsifier. Revisiting PGD Attacks for Stability Analysis of Large-Scale Nonlinear Systems and Perception-Based Control searches for unstable starting states with first-order projected gradient attacks. It scales to a 1,000-dimensional cubic system and to pixel-based controllers. Its authors acknowledge it can miss isolated pockets of instability, and we treat it as the strongest existing falsifier. Neural Lyapunov Control, Automated and Formal Synthesis of Neural Barrier Certificates for Dynamical Models, and Fossil 2.0 set up the learner-plus-falsifier loop. In all three, an SMT solver does the falsifying, so the loop inherits the solver's dimension ceiling. We keep their loop and their final SMT check where it is feasible, and change only who proposes counterexamples.
The method comes from optimization. How to Escape Saddle Points Efficiently shows that isotropic perturbation escapes strict saddles in time that grows only polylogarithmically with dimension. Finding Approximate Local Minima for Nonconvex Optimization in Linear Time finds negative-curvature directions using only Hessian-vector products. We reuse the second technique on the falsification objective rather than on a training loss. We compare directly against the first, because its guarantee is strong enough to be a real competitor.
Constraints come from game dynamics. Local Saddle Point Optimization: A Curvature Exploitation Approach shows that in coupled min-max problems, gradient dynamics can be attracted to bad stationary points, so random noise drifts back into them. Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games shows that running the maximizing player on a faster timescale avoids such points, but only for unconstrained problems with a well-behaved maximizing side. The learner-falsifier loop has a compact state domain and a non-concave falsifier, so neither result transfers directly. This is why the coupled loop is a secondary question here rather than the core claim.
Towards Learning and Verifying Maximal Neural Lyapunov Functions already certifies a small ellipsoid around the origin with linear theory before growing outward. That is why we do not claim the origin case as new.
Research Program
The first component is analysis. We will characterize the stationary points of the violation function $g$ in three places: at the equilibrium, at locations patched in earlier training rounds, and, for trajectory losses $\|x(T)\|$ over starting state $x_0$, near stable manifolds of unstable closed-loop equilibria. For each, we will bound the distance to the nearest counterexample in terms of the local rising curvature and a Lipschitz constant of the third derivative. We will also bound the hit probability of uniform restarts. The degenerate case, where the rising curvature is exactly zero, falls outside these bounds. We will state that openly and measure how often it occurs on learned certificates rather than assume it away.
The second component is the falsifier itself. It runs projected gradient ascent on $g$, or on the trajectory loss, until the gradient is small. It then runs a few dozen Lanczos steps with Hessian-vector products. For trajectory losses, these products are backpropagated through a differentiable ODE solver. If a direction of rising curvature above a threshold exists, the falsifier steps along it with a length set by the curvature and resumes ascent. Otherwise it records the point and its curvature spectrum. Box and safe-set constraints are handled by projecting both the gradient and the curvature search onto the tangent space of the active constraints.
The third component plugs this falsifier into Fossil 2.0's loop in place of the SMT counterexample step during training. dReal and the boundary-propagation verifier are kept as the final judges in low dimensions. In high dimensions, no exact check is feasible. There we report falsification results only and make no safety claim.
Baselines
The naive reference is the first-order projected gradient attack of Revisiting PGD Attacks, rerun with our objective and constraints. On the 1,000-dimensional cubic system, the only figure the file gives for it is that the analysis finishes in under four hours on a laptop. The file reports no counterexample hit rate on Lacuna for this method, so we will measure its hit rate ourselves. Because it is the only method shown to run at high dimension and on pixels, it is the strongest existing competitor where exact solvers cannot go.
Second is multi-start local optimization with L-BFGS from uniformly random states. This is the obvious practitioner's fix. Third is perturbed gradient ascent in the style of How to Escape Saddle Points Efficiently. Fourth, in dimensions of eight or fewer, is the SMT falsifier as used in Fossil 2.0, which the file reports reaches 100% success on its barrier benchmarks. It serves as ground truth and as a wall-clock reference. Fifth, on ReLU barriers, is the boundary-propagation method of Efficient Verification and Falsification of ReLU Neural Barrier Certificates, whose Decay benchmark enumeration the file reports at about 31,000 seconds. Sixth, for the origin case only, is a one-time eigenvalue check of $H_0$.
Fairness is enforced by a shared budget counted in gradient-equivalent evaluations, with one Hessian-vector product counted as two gradients. All methods get the same wall-clock cap, the same step-size grid, and the same restart count. The key ablation replaces the Lanczos direction with a random direction of equal length, applied at the same stalled points. This isolates whether curvature information, rather than the extra kick, does the work. Beating the baselines means a higher fraction of planted violations found at matched budget, with the gap widening as $d$ grows. It also means fewer inconclusive outcomes on the Ren et al. suite without any false counterexamples. Every returned counterexample will be re-checked in exact arithmetic.
Why not just…?
Why not just use random restarts? In two to four dimensions, restarts will probably match our method, and we expect to report that. The case against restarts rests on the cone-volume scaling above. When violations occupy a thin cone or ridge, the chance that a uniform start lands in its basin falls exponentially with $d$. The planted-violation sweep from $d=2$ to $d=1{,}000$ measures exactly where restarts stop keeping up. If they keep up throughout, the proposal is wrong.
Why not just add isotropic noise at stalled points, as in Jin et al.? This is the most serious threat, because its escape rate is also nearly dimension-free. Its escape time scales inversely with the rising curvature $\mu$. Planted violations with small $\mu$, which are exactly the near-miss certificates the learner produces late in training, should separate the two methods. Inside the coupled learner-falsifier loop, Local Saddle Point Optimization reports that noise drifts back into stable bad points. We will test whether that happens here rather than assume it. If noise ties Lanczos across the $\mu$ sweep at matched budget, we will adopt noise and drop the second-order machinery.
Why not just let the SMT solver do the falsifying? Where it runs, it is exact and we keep it as judge. Neural Lyapunov Control reports certification up to six dimensions and calls 100-plus dimensions prohibitive. SMT also cannot ingest pixel-driven controllers, as Revisiting PGD Attacks notes. Our method targets the loop's training-time counterexample supply and the regimes SMT cannot reach, not the final proof.
Why not just check the linearization at the origin? For the origin saddle, that check is enough, and it is a baseline. The experiments count how many violations missed by first-order methods lie away from the origin, where no such check exists.
Proposed Experiments
The first check is a diagnostic that can kill the project. On learned certificates from Fossil 2.0's 17 benchmarks and from the pendulum, ducted fan, and humanoid systems of Neural Lyapunov Control, we will run the first-order falsifier and classify every point where it stops. Each is either a true local maximum or a saddle with a rising direction, as measured by Lanczos. If saddles are rare, stagnation is not the bottleneck and we stop.
The second is the planted-violation benchmark. We take a certified Lyapunov function and perturb its local curvature to insert thin violation cones of known location and width. Planting happens at the origin, at previously patched points, and on the synthetic cubic system scaled from 10 to 1,000 dimensions. We measure the fraction recovered against budget for every baseline.
The third converts inconclusive cases. On Arch3, Complex, Linear4d, and Decay from Efficient Verification and Falsification of ReLU Neural Barrier Certificates, we will count how many "?" outcomes become confirmed counterexamples. The rest are passed to exact enumeration.
The fourth runs the full loop. On the Fossil 2.0 suite, we will compare synthesis success, wall-clock time, and number of expensive SMT calls between the SMT-driven loop and our curvature-aware loop. Both loops use the same final dReal check. We will also compare simultaneous updates against faster-falsifier timescales.
The fifth applies trajectory attacks to the pixel pendulum and cart-pole from the DeepMind Control Suite. Here we test whether curvature steps through the perception network find unstable starts that the first-order attack misses.
References
- Efficient Verification and Falsification of ReLU Neural Barrier Certificates
- Revisiting PGD Attacks for Stability Analysis of Large-Scale Nonlinear Systems and Perception-Based Control
- Neural Lyapunov Control
- Automated and Formal Synthesis of Neural Barrier Certificates for Dynamical Models
- Fossil 2.0: Formal Certificate Synthesis for the Verification and Control of Dynamical Models
- How to Escape Saddle Points Efficiently
- Finding Approximate Local Minima Faster than Gradient Descent
- Local Saddle Point Optimization: A Curvature Exploitation Approach
- Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
- Towards Learning and Verifying Maximal Neural Lyapunov Functions