Neural network verifiers stop assuming boxes: Fit-LRP fits final affine bounds to oblique polytopes, cutting branches on the hardest region
Synopsis
Neural network verifiers usually treat the input domain as an axis-aligned box, yet reachability, obstacle-avoidance and neural Lyapunov certificates in cyber-physical systems often live on oblique or non-convex polytopes, where box bounds become very loose. Fit-LRP optimizes the final affine bound from LiRPA or α-CROWN exactly over the true polyhedral constraints inside branch-and-bound, replacing the box approximation with a sequence of small linear programs. On the ARCH-COMP spacecraft rendezvous benchmark and two neural Lyapunov benchmarks, branching on the hardest region drops, and single-core CPU verification runs faster than α-CROWN on a GPU.
Interpretation
The input domain of neural network verification is no longer forced into an axis-aligned box; oblique or non-convex polyhedral constraints can directly tighten the final bound. Earlier verifiers assumed the input domain was a compact hyperrectangle, so an oblique region could only be replaced by its tightest enclosing box, which may be far larger than the actual region and makes the bound loose. On the ARCH-COMP spacecraft rendezvous velocity benchmark, all 8 regions were certified by Fit-LRP on the first bound with a maximum of 1 branch, whereas α-CROWN's Clip-and-Verify must approximate the octagonal region and triggers 6 branches per region.
The method computes, at the last step of branch-and-bound, the exact maximum of the affine upper bound over the true polytope instead of over the enclosing box. The affine bound from LiRPA holds only within a box, and concretizing it against a convex relaxation of the constraints stays sound but looser; Fit-LRP instead solves one small linear program per convex polytope piece and takes the maximum. The method plugs into LiRPA and α-CROWN's Clip-and-Verify and is evaluated on SPRE, a two-link planar robot arm and a networked SIS epidemic, whose regions are partitioned into 8, 3068 and 2710 polytopes respectively.
Exact concretization lets the search tree prune earlier, reducing branches and verification time. Approximating oblique constraints with axis-aligned splits causes combinatorial blowup and risks non-termination. Adding Fit-LRP to Clip-and-Verify reduces total branches by 23% to 71% across the three systems; on the two-link arm the hardest region falls from 36372 branches to 2198, and that region's verification time drops to 10.4 seconds.
Perspective
The demonstrated scope is the ARCH-COMP spacecraft rendezvous velocity benchmark and two continuous piecewise affine neural Lyapunov systems, where the goal is to prove a function strictly negative on a given region; regions are partitioned into polytopes and verified piece by piece.
The current implementation relies on CPU-centric linear programming and has no GPU support; reconciling massively parallel GPU intermediate bounds with CPU-based final affine bounds remains open. Optimal partitioning of the domain into polytopes also awaits automation, since enumerating activation regions and handling diverse hybrid-system tilings are complex.