Hyperlyve splits ReLU activation regions into parallel subtrees, enumerating 6.3 million regions in under 16 minutes
Synopsis
Hyperlyve turns activation-region enumeration for deep ReLU networks into parallel work over independent hidden-layer subtrees, then checks the Lyapunov conditions on the true nonlinear dynamics inside each affine region with sound and complete regional tests. Earlier enumerators were bottlenecked by per-neuron checks or network flattening: on Rejoin RL's 6.3 million 8-dimensional regions, RPM and Relucent both hit a one-hour timeout while Hyperlyve finished in under 16 minutes. It also characterizes verification of continuous piecewise-affine neural Lyapunov functions as co-NP-complete and embeds the verifier in a counterexample-guided synthesis loop.
Interpretation
Hyperlyve decomposes the hyperplane arrangement induced by a deep ReLU network into disjoint subtrees that worker threads advance concurrently, without a globally shared queue. Earlier ReLU region enumerators were bottlenecked by per-neuron evaluation or by network flattening, which limits parallelism; the GPU-accelerated Berzins approach is highly parallel but returns vertices rather than the half-space descriptions regional stability checks need. On the Rejoin RL network, Hyperlyve enumerated 6.3 million 8-dimensional regions in under 16 minutes, while RPM and Relucent both hit the one-hour timeout on the same task; on ACAS Xu, Hyperlyve took 8.0 seconds against 350.2 seconds for RPM and 1212.3 seconds for Relucent.
The stability check inside each activation region runs branch-and-bound on that region alone, removing the Lyapunov network's own nonlinearity from the subproblem so that the remaining nonlinearity comes only from the closed-loop dynamics. Holistic complete verifiers bound the composition of the Lyapunov network and the nonlinear dynamics together, and those coupled bounds loosen quickly across the whole domain, triggering extensive branching; Hyperlyve reasons region by region and tightens the affine upper bound from LiRPA with linear programs. Across AKP-10, AKP-100, IPNN, Lorenz, TLPRA and SIS-3 through SIS-10, Hyperlyve was faster than FOSSIL, LyZNet and the Li et al. method on most cases, and it certified TLPRA where the Li et al. method reported an error.
Perspective
The demonstrated setting is continuous-time dynamics on a compact convex polytope domain, with the Lyapunov function restricted to the continuous piecewise-affine form produced by a ReLU network and with pre-trained controllers; experiments ran on an AMD EPYC 7763 64-core processor without a GPU, with a one-hour limit per run.
Worst-case runtime remains exponential because both decision problems addressed are co-NP-complete; branch-and-bound termination has no input-independent finite worst-case guarantee; and a small ball around the origin must be excluded to avoid floating-point tolerances, so the certificate does not cover that ball.
