cs.LGNov 11, 2026

Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions

Authors: Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas Sundaram

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 47×47\times, cuts worst-case verification time by 15×15\times, and with region-wise partitioning, verifies on a single CPU 6.1×6.1\times faster than α, ⁣βα,\! β-CROWN on a GPU.

Figures & tables

Explore similar work

CardsList
  1. Shifting-based Optimizable Linear Relaxations for General Activation Functions

    Jun 18, 2026Philipp Kern, László Antal, Erika Ábráham +1Neural Network VerificationNeural Network Activation Functions

  2. Closing the Loop: Branch-and-Bound for Scalable Verification of Nonlinear Neural Feedback Systems

    Sep 14, 2026I. Samuel Akinwande, Mykel J. Kochenderfer, Clark BarrettNeural Network VerificationBranch and Bound