# Bisimulations for Neural Network Reduction

arXiv: https://arxiv.org/abs/2110.03726 · HTML: https://mlsanity.com/paper/2110.03726/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 20 references that are in the map.
- First posted on arXiv 7 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [A Survey of Model Compression and Acceleration for Deep Neural Networks](https://mlsanity.com/paper/1710.09282/) (2017)
- [Output Reachable Set Estimation and Verification for Multi-Layer Neural Networks](https://mlsanity.com/paper/1708.03322/) (2017)
- [An Abstraction-Based Framework for Neural Network Verification](https://mlsanity.com/paper/1910.14574/) (2019)
- [Abstraction based Output Range Analysis for Neural Networks](https://mlsanity.com/paper/2007.09527/) (2020)
- [DeepAbstract: Neural Network Abstraction for Accelerating Verification](https://mlsanity.com/paper/2006.13735/) (2020)
- [Verification for Machine Learning, Autonomy, and Neural Networks Survey](https://mlsanity.com/paper/1810.01989/) (2018)
- [Abstract Neural Networks](https://mlsanity.com/paper/2009.05660/) (2020)
- [A Survey of Safety and Trustworthiness of Deep Neural Networks: Verification, Testing, Adversarial Attack and Defence, and Interpretability](https://mlsanity.com/paper/1812.08342/) (2018)
- [A Unified View of Piecewise Linear Neural Network Verification](https://mlsanity.com/paper/1711.00455/) (2017)

## Built on by (most cited first, 6 of 6)

- [Verifying Generalization in Deep Learning](https://mlsanity.com/paper/2302.05745/) (2023)
- [Fully Automatic Neural Network Reduction for Formal Verification](https://mlsanity.com/paper/2305.01932/) (2023)
- [DelBugV: Delta-Debugging Neural Network Verifiers](https://mlsanity.com/paper/2305.18558/) (2023)
- [Neural Networks Reduction via Lumping](https://mlsanity.com/paper/2209.07475/) (2022)
- [Syntactic vs Semantic Linear Abstraction and Refinement of Neural Networks](https://mlsanity.com/paper/2307.10891/) (2023)
- [Architecture Before the Formula: Training-Dependent Computational Semantics in Transformers](https://mlsanity.com/paper/2601.11618/) (2026)

## Abstract (arXiv)

We present a notion of bisimulation that induces a reduced network which is semantically equivalent to the given neural network. We provide a minimization algorithm to construct the smallest bisimulation equivalent network. Reductions that construct bisimulation equivalent neural networks are limited in the scale of reduction. We present an approximate notion of bisimulation that provides semantic closeness, rather than, semantic equivalence, and quantify semantic deviation between the neural networks that are approximately bisimilar. The latter provides a trade-off between the amount of reduction and deviations in the semantics.