Hyperlyve: Parallelized Enumeration and Exact Lyapunov Stability Certification for Deep ReLU Networks

Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas SundaramarXiv 2026 · arXiv

TL;DR

Hyperlyve is a new framework that formally proves the asymptotic stability of nonlinear systems, even those controlled by deep neural networks. By decomposing the neural network's complex behavior into a parallelized arrangement of simple geometric regions, it achieves a 150x speedup in verification and can certify complex systems that were previously considered intractable.

What Problem Does This Paper Address?

While neural networks are powerful controllers for autonomous systems, they are notoriously difficult to trust in safety-critical applications. To guarantee a system will always return to a stable equilibrium (asymptotic stability), control theorists use Lyapunov functions. If you can find a scalar function that is zero at the equilibrium, positive everywhere else, and always decreasing along the system's trajectories, you’ve proven stability.

The challenge is that finding these functions for nonlinear systems is incredibly hard. Recent "Neural Lyapunov" methods try to learn these functions using neural networks, but learning isn't the same as proving. Existing verification tools often struggle to scale to deep networks or rely on oversimplified linear approximations of the system's dynamics, which can lead to "proofs" that don't hold up in the real, nonlinear world.

Methods

The authors introduce Hyperlyve (Hyperplane Partitioned Lyapunov Verification and Enumeration), which operates within a Counterexample-Guided Inductive Synthesis (CEGIS) loop.

Fig. 1: The Hyperlyve counterexample-guided inductive syn- thesis (CEGIS) framework. A candidate ReLU neural Lya- punov function V is trained by a Learner (gray) on sampled states of f in the domain B before being passed to Hyperlyve verifier (blue). Hyperlyve enumerates the induced activation regions of V and checks Lyapunov stability conditions across each region in parallel. Hyperlyve returns counterexamples to the Learner, which adds them to the dataset and completes another round of training. This CEGIS loop continues until no counterexamples are found for V , certifying the asymptotic stability of the nonlinear dynamics over the region of interest.

The core technical innovations include:

  • Parallel Polyhedral Enumeration: ReLU neural networks are "piecewise-affine," meaning they partition the state space into a complex web of convex polyhedra. Hyperlyve uses a recursive "facet-crossing" algorithm to map these regions. Crucially, it recognizes that hidden layers form independent subtrees, allowing the problem to be split across many CPU cores simultaneously.
  • Exact Regional Certification: Once the space is partitioned, the Lyapunov function is just a simple linear (affine) function within each region. This allows the verifier to focus all its computational power on the actual nonlinear dynamics of the system, using branch-and-bound techniques (specifically LiRPA) to prove the stability conditions hold exactly.
  • Complexity Characterization: The paper provides the first formal proof that the Continuous Piecewise-Affine (CPA) neural Lyapunov verification problem is co-NP-complete, establishing a theoretical baseline for the field.

Datasets

The authors evaluated Hyperlyve on two fronts:

  1. Enumeration Benchmarks: They tested the speed of mapping regions in various well-known networks, including TaxiNet, ACAS Xu, and LunarLander RL.
  2. Stability Benchmarks: They certified stability for several nonlinear systems:
  3. AKP Dynamics: A polynomial system known to have no polynomial Lyapunov function.
  4. Lorenz System: A classic chaotic system.
  5. Networked SIS Epidemic Model: Modeling disease spread.
  6. Inverted Pendulum (IPNN): A standard control benchmark.
  7. Two-Link Planar Robot Arm (TLPRA): A complex, 4D robotic system.

Key Insights and Ideas

  • Divide and Conquer: The "aha moment" is that by explicitly calculating the affine regions of the neural network, you eliminate the network's own nonlinearity from the verification sub-problem. This makes the remaining task—verifying the system dynamics—far more tractable.
  • Embarrassing Parallelism: Because the activation regions of different "parent" regions in a deep network are independent, the verification can be scaled across massive compute clusters without the need for complex synchronization or global queues.
  • Architectural Enforcement: To satisfy the strict requirement that a Lyapunov function must be exactly zero at the origin, the authors force the first layer of the network to have zero bias. This ensures the origin is always a "vertex" in the geometric arrangement, making the proof much more robust.

Key Results

  • Massive Speedups: Hyperlyve enumerated ReLU networks over 150 times faster than competing state-of-the-art tools like RPM or Relucent. For the "Rejoin RL" benchmark, it processed 6.3 million regions in under 16 minutes, while other tools timed out after an hour.
  • Superior Certification: Hyperlyve successfully proved the stability of the TLPRA (Robot Arm) and AKP-100 systems. Competing verifiers like FOSSIL and LyZNet either timed out or produced errors on these more complex tasks.
  • High Precision: The tool can verify stability much closer to the equilibrium point (an exclusion radius of $10^{-6}$) than previous methods, which often required much larger "holes" in their proofs.
A candidate Lyapunov function failing verification. Hyperlyve identifies specific regions (hatched/red) where conditions are violated, providing precise counterexamples for retraining.

Limitations and Future Work

While Hyperlyve scales exceptionally well with the size of the neural network (depth and width), it still faces challenges as the state dimension ($p$) of the physical system increases. The number of geometric regions can grow exponentially with the number of variables in the system.

Future work suggested by the authors includes:

  • Integrating Hyperlyve into the training of optimal controllers, rather than just verifying pre-existing ones.
  • Improving the "tightness" of the bounds by using polyhedral constraints within the LiRPA framework instead of simple hyperrectangles.

Summary updated

Abstract

We introduce Hyperlyve (Hyperplane Partitioned Lyapunov Verification and Enumeration), a framework for proving the asymptotic stability of nonlinear dynamical systems, including those with neural network controllers. Hyperlyve learns and formally certifies continuous piecewise-affine (CPA) neural Lyapunov functions within a counterexample-guided inductive synthesis (CEGIS) loop. Hyperlyve's key innovation is a parallel algorithm that enumerates the hyperplane arrangement formed by the ReLU activations of deep networks and certifies that Lyapunov conditions hold within each polyhedral region. We derive sound and complete regional tests to verify the asymptotic stability of the exact smooth dynamics (rather than a piecewise-linear approximation) within a compact domain of interest. Furthermore, we formally characterize the computational complexity of the CPA neural Lyapunov verification problem as co-NP-complete, filling a key gap in the literature. Empirical results demonstrate that Hyperlyve enumerates ReLU networks over 150-times faster than competing tools, which contributes to Hyperlyve proving the asymptotic stability of systems that are currently intractable for state-of-the-art verifiers.
BibTeX
@misc{yarbrough2026hyperlyve,
  author = {Brian Yarbrough and Jesse Wayment and Jingbo Wang and Philip E. Paré and Shreyas Sundaram},
  title = {{Hyperlyve: Parallelized Enumeration and Exact Lyapunov Stability Certification for Deep ReLU Networks}},
  year = {2026},
  eprint = {2611.21599},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21599},
}
Figure