Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions
Organizations: Purdue University, USA
Abstract
State-of-the-art neural network verifiers evaluate linear relaxations over axis-aligned bounding boxes. However, verification domains in cyber-physical systems are rarely boxes. Reachability specifications, obstacle-avoidance constraints, and neural Lyapunov certificates typically yield oblique or non-convex polyhedral regions, over which box-based bounds become extremely loose. This paper proposes Fit-LRP (Fitting Linear Relaxations to Polytopes), a framework the implements exact optimization of affine bounds over non-convex domains (represented by unions of polytopes) by solving a sequence of small, low-dimensional linear programs. Our approach seamlessly enhances the final optimization step of LiRPA and -CROWN branch-and-bound (BaB) algorithms. In BaB verification, approximating oblique constraints with axis-aligned splits causes severe combinatorial blowup and risks non-termination. By optimizing the final affine bound of a nonlinear function over the exact polyhedral state-space constraints our method eliminates box-induced over-approximations, enabling earlier search-tree pruning. On ARCH-COMP and neural Lyapunov benchmarks, Fit-LRP reduces branching on the hardest region by , cuts worst-case verification time by , and with region-wise partitioning, verifies on a single CPU faster than -CROWN on a GPU.
Figures & tables
| branches | time (s) | ||||
| System | Verifier | total | max | ||
| SPRE [1pt] 8 (8) | C&V, | 28 | 6 | 6.6 | 1.0 |
| C&V, GPU | 21 | – | 7.5 | – | |
| C&V, Fit-LRP | 8 | 1 | 5.1 | 0.7 | |
| Fit-LRP BaB | 8 | 1 | 3.0 | 0.5 | |
| TLPRA [1pt] 3,068 (756) | C&V, | 303,942 | 36,372 | 9,701 | 103 |
Neural Network Verification
Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.
See all 138 papers