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.

Datasets
The authors evaluated Fit-LRP on three challenging benchmarks:
- ARCH-COMP Spacecraft Rendezvous (SPRE): A hybrid system modeling planar spacecraft motion with octagonal guards and a non-convex exclusion zone.
- Two-Link Planar Robot Arm (TLPRA): A benchmark for certifying neural Lyapunov functions, featuring over 3,000 regions, hundreds of which are non-convex.
- 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.
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