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

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

TL;DR

Fit-LRP (Fitting Linear Relaxations to Polytopes) is a new framework that significantly accelerates neural network verification by optimizing linear bounds over exact, non-convex polyhedral regions rather than loose axis-aligned boxes. By eliminating the "box-induced" over-approximation common in state-of-the-art verifiers, Fit-LRP reduces branching by up to 47× and can even outperform GPU-based verifiers using only a single CPU.

What Problem Does This Paper Address?

Formally verifying that a neural network behaves safely—for instance, ensuring a self-driving car avoids obstacles or a robot arm remains stable—is notoriously difficult (NP-hard). Current state-of-the-art verifiers like $\alpha,\beta$-CROWN typically approximate the input domain using axis-aligned bounding boxes.

However, real-world cyber-physical systems (CPS) rarely operate in "boxes." Safety specifications, obstacle boundaries, and stability certificates (like Lyapunov functions) often define "oblique" (tilted) or non-convex regions. When you force a tilted region into an axis-aligned box, you introduce significant "slack" or over-approximation. To compensate, verifiers must repeatedly split these boxes into smaller pieces (a process called Branch-and-Bound), leading to a combinatorial explosion of subproblems that can crash the verifier or take hours to solve.

Methods

The authors introduce Fit-LRP, which replaces the final "concretization" step of standard linear relaxation-based perturbation analysis (LiRPA).

Instead of calculating the maximum value of a neural network's output over a simple box, Fit-LRP solves a sequence of small, low-dimensional Linear Programs (LPs) over the exact polyhedral constraints of the region of interest.

Key technical highlights include:

  • Handling Non-Convexity: If a region is non-convex (e.g., a region excluding a central docking port), Fit-LRP represents it as a union of $K$ convex polytopes and solves an LP for each, taking the maximum result.
  • Efficiency: Rather than performing expensive LP optimizations for every single neuron in the network, Fit-LRP only applies this exact optimization to the final affine bound. This provides high precision where it matters most without the massive overhead of per-neuron LPs.
  • Seamless Integration: It acts as a drop-in enhancement for existing tools like $\alpha,\beta$-CROWN, enabling them to prune the search tree much earlier.

![Fig.

  1. Position cut of the spacecraft rendezvous region R. The octagonal switching guard is represented via affine constraints (solid black). Removing the docking cube (red, enlarged) makes R non-convex and forms the union of K= 4 disjoint convex tiles P_i (dashed) in a pinwheel configuration. The tightest axis-aligned root bounding box B0 (blue) over approximates the diagonal faces of R. Box-based concretization yields y_hat_0 = +23.1 (diamond) at a corner outside R, which fails to verify. Conversely, Fit-LRP computes exact values z_i (dots), taking the maximum y = z1 = -0.82, and the facet is verified.](/figures/art_101806853dcd4a9bbba483af77acff7e)

Datasets

The authors evaluated Fit-LRP on three challenging benchmarks:

  1. ARCH-COMP Spacecraft Rendezvous (SPRE): A hybrid system modeling planar spacecraft motion with octagonal guards and a non-convex exclusion zone.
  2. Two-Link Planar Robot Arm (TLPRA): A benchmark for certifying neural Lyapunov functions, featuring over 3,000 regions, hundreds of which are non-convex.
  3. Mitigated Epidemic (MSIS): A networked epidemic spreading model controlled by a neural network, involving 2,710 distinct regions.

Key Insights and Ideas

  • The "Box Tax" is Real: Figure 1 illustrates how a standard box-based approach can fail to verify a property simply because the box includes "empty space" outside the actual region of interest. Fit-LRP proves that staying true to the geometry of the problem is more important than raw parallel processing power.
  • Pruning Power: By getting a tighter bound at the very beginning (the root node), Fit-LRP can often verify a region immediately without any branching. In the SPRE benchmark, it verified regions in one step that took baseline methods multiple splits to resolve.
  • CPU vs. GPU Paradox: One of the most surprising findings is that Fit-LRP running on a single CPU core can be faster than a state-of-the-art GPU verifier. This is because the CPU version solves far fewer, higher-quality subproblems, whereas the GPU version wastes time processing millions of loose, box-based subproblems.

Key Results

As shown in the extracted data (Figure 2), Fit-LRP consistently outperforms the baselines across all metrics:

  • Branching Reduction: On the TLPRA benchmark, Fit-LRP reduced the maximum branches required for a single region from 36,372 down to just 1,853 (a ~20× reduction).
  • Speed: For the MSIS benchmark, Fit-LRP verified the system in 4,178 seconds on a CPU, compared to 25,665 seconds for $\alpha,\beta$-CROWN on a GPU—a 6.1× speedup.
  • Worst-Case Performance: It cut worst-case verification time by up to 15× on the hardest regions.
Extracted table from page 8 showing comparison of branching and time to verify systems.

Limitations and Future Work

  • CPU Bottleneck: Currently, the LP solver is CPU-centric. The authors note that reconciling the tension between massively parallel GPU intermediate bounds and CPU-based final exact bounds is a key challenge for future scaling.
  • Domain Partitioning: The method requires the input domain to be partitioned into polytopes. While this is natural for many CPS problems, automating "verification-optimized" partitioning for general neural networks remains an open research question.
  • GPU Integration: Developing GPU-native LP solvers or similar optimization techniques could further widen the performance gap.

Summary updated

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\times$, cuts worst-case verification time by $15\times$, and with region-wise partitioning, verifies on a single CPU $6.1\times$ faster than $α,\! β$-CROWN on a GPU.
BibTeX
@misc{yarbrough2026fit,
  author = {Brian Yarbrough and Jesse Wayment and Jingbo Wang and Philip E. Paré and Shreyas Sundaram},
  title = {{Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions}},
  year = {2026},
  eprint = {2611.16003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16003},
}
Figure