SimCert: Probabilistic Certification for Behavioral Similarity in Deep Neural Network Compression

Jingyang Li; Fu Song; Guoqiang Li

cs.SEMar 16, 2026

SimCert: Probabilistic Certification for Behavioral Similarity in Deep Neural Network Compression

Authors: Jingyang Li, Fu Song, Guoqiang Li

Organizations: Shanghai Jiao Tong University, Shanghai 200240, China · Institute of Software, Chinese Academy of Sciences, Beijing 100190, China

Abstract

Deploying Deep Neural Networks (DNNs) on resource-constrained embedded systems requires aggressive model compression techniques like quantization and pruning. However, ensuring that the compressed model preserves the behavioral fidelity of the original design is a critical challenge in the safety-critical system design flow. Existing verification methods often lack scalability or fail to handle the architectural heterogeneity introduced by pruning. In this work, we propose SimCert, a probabilistic certification framework for verifying the behavioral similarity of compressed neural networks. Unlike worst-case analysis, SimCert provides quantitative safety guarantees with adjustable confidence levels. Our framework features: (1) A dual-network symbolic propagation method supporting both quantization and pruning; (2) A variance-aware bounding technique using Bernstein's inequality to tighten safety certificates; and (3) An automated verification toolchain. Experimental results on ACAS Xu and computer vision benchmarks demonstrate that SimCert outperforms state-of-the-art baselines.

Figures & tables

Figure 1: Diagram of network notations

Panel of Figure 2 — Figure 2: The pair of neural networks of the original one and the quantized one.

Figure 3: Naive encoding to compute the difference of the two neural networks

Panel of Figure 4 — Figure 4: Conceptual illustration of Dual-Network Symbolic Error Propagation.

Figure 5: Comparison of width reduction between Bernstein’s (Our approach) and Hoeffding’s (PROVEN) inequalities

Network	Method	Certification Confidence
Network	Method	5%	25%	50%	75%	99.99%
MNIST3x[1024]	PROVEN	0.09323	$0.079\,39$	$0.064\,83$	$0.050\,92$	$0.021\,22$
MNIST3x[1024]	Our approach	0.15277	0.13035	0.10604	0.08276	0.03241
	Improvement (%)	63.86	$64.18$	$63.56$	$62.52$	$52.73$
MNIST4x[1024]	PROVEN	0.05650	$0.046\,80$	$0.037\,35$	$0.028\,96$	$0.011\,93$
MNIST4x[1024]	Our approach	0.09240	0.07624	0.06037	0.04619	0.01715

Table 1: Average certified radii comparison between PROVEN [ 37 ] and Bernstein’s methods (Our approach)

Network	pruning_ratio	$\epsilon$	$r_{\text{wc}}$	$r^{P}_{0.9999}$	$r^{B}_{0.9999}$
5x[2048]	$0.01$	$0.015$	$0.459\,902$	$0.467\,462$	0.499966
	$0.05$	$0.075$	$0.309\,517$	$0.330\,092$	0.371502
	$0.10$	$0.1$	$0.299\,285$	$0.324\,073$	0.349674
	$0.15$	$0.12$	$0.368\,071$	$0.400\,997$	0.439278

Table 2: Certified radii comparison for pruned CIFAR-10 network under different compression intensities

Neural Network Verification

Neural network verification develops methods to prove whether networks satisfy properties such as robustness, safety, and bounded output behavior.

See all 121 papers

$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks
Aug 25, 2026Hanna Jiamei Zhang, Alan Papalia, Michael Everett +1Neural Network Verification ReLU Neural Networks
Departments of Computer Science, Electrical and Computer Engineering, and Mathematics Northeastern University, Boston, MA. · Department of Naval Architecture and Marine Engineering, University of Michigan, Ann Arbor, MI.
Verifying Neural Networks with Reinforcement Learning
Sep 28, 2026Hai Duong, Thanh Le, ThanhVu NguyenNeural Network Verification Branch and Bound
Department of Computer Science George Mason University Fairfax, VA, USA · Unaffiliated Yokosuka, Japan
Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications
Jun 22, 2026Merkouris Papamichail, Konstantinos Varsos, Giorgos Flouris +1Neural Network Verification Neural Network Robustness
Foundation for Reasearch and Technology - Hellas, Heraklion, Greece · University of Crete, Heraklion, Greece · Catalan Institution for Research and Advanced Studies, Barcelona, Spain +1

Aug 25, 2026J/K move · Enter open · S save

$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks

Hanna Jiamei Zhang, Alan Papalia, Michael Everett, David M. Rosen

Departments of Computer Science, Electrical and Computer Engineering, and Mathematics Northeastern University, Boston, MA. · Department of Naval Architecture and Marine Engineering, University of Michigan, Ann Arbor, MI.

Neural Network Verification ReLU Neural Networks Semidefinite Programming Nonconvex Optimization

Open paper AskPDF arXiv

Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach

(\text{DNN})^2

produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.

Abstract

Neural Network Verification

Explore similar work

(DNN)2(\text{DNN})^2(DNN)2: Doubly Non-Negative Relaxations for Deep Neural Networks

Verifying Neural Networks with Reinforcement Learning

Are Safety Guarantees in Neural Networks Safe? How to Compute Trustworthy Robustness Certifications

$(\text{DNN})^2$ : Doubly Non-Negative Relaxations for Deep Neural Networks