Title: Neural Network Verification via Partial Multi-Neuron Relaxation

Abstract: As deep neural networks become increasingly embedded in safety-critical systems, there is growing theoretical and practical demand for formally verifying their behavioral safety. Current verification frameworks typically address this by computing linear relaxations for the non-linear activation functions inherent in these networks. Existing techniques for such relaxations generally adhere to one of two paradigms: single-neuron relaxation, which constrains each neuron based on its inputs, or multi-neuron relaxation, which establishes linear bounds encompassing multiple neurons and their sources simultaneously. However, current methodologies often struggle to balance verification tightness with computational scalability. Single-neuron bounds may lack the precision required to complete verification, while applying multi-neuron relaxation across all neurons imposes significant computational overhead.

In this study, we introduce an intermediate strategy termed partial multi-neuron relaxation. This approach generates multi-neuron bounds exclusively for a small, heuristically chosen subset of neurons. We enhance existing branching heuristics to effectively select these neurons and optimize the bounding hyper-planes for the resulting multi-neuron constraints. By integrating our proposed method into the Marabou verifier, we achieved promising results that outperform existing bound-tightening techniques. Our experimental findings demonstrate the significant potential of this technique for enhancing neural network verification.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC