# Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 29 Feb 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Empirical Bounds on Linear Regions of Deep Rectifier Networks](https://mlsanity.com/paper/1810.03370/) (2018)
- [Dissecting Deep Neural Networks](https://mlsanity.com/paper/1910.03879/) (2019)
- [Any Deep ReLU Network is Shallow](https://mlsanity.com/paper/2306.11827/) (2023)
- [Fast and Exact Enumeration of Deep Networks Partitions Regions](https://mlsanity.com/paper/2401.11188/) (2024)
- [mplrs: A scalable parallel vertex/facet enumeration code](https://mlsanity.com/paper/1511.06487/) (2015)
- [A parallel framework for reverse search using mts](https://mlsanity.com/paper/1610.07735/) (2016)
- [mts: A light framework for parallelizing tree search codes](https://mlsanity.com/paper/1709.07605/) (2017)

## Abstract (arXiv)

A feedforward neural network using rectified linear units constructs a mapping from inputs to outputs by partitioning its input space into a set of convex regions where points within a region share a single affine transformation. In order to understand how neural networks work, when and why they fail, and how they compare to biological intelligence, we need to understand the organization and formation of these regions. Step one is to design and implement algorithms for exact region enumeration in networks beyond toy examples. In this work, we present parallel algorithms for exact enumeration in deep (and shallow) neural networks. Our work has three main contributions: (1) we present a novel algorithm framework and parallel algorithms for region enumeration; (2) we implement one of our algorithms on a variety of network architectures and experimentally show how the number of regions dictates runtime; and (3) we show, using our algorithm's output, how the dimension of a region's affine transformation impacts further partitioning of the region by deeper layers. To our knowledge, we run our implemented algorithm on networks larger than all of the networks used in the existing region enumeration literature. Further, we experimentally demonstrate the importance of parallelism for region enumeration of any reasonably sized network.