mlsanityData to 14 Oct 2026

The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

arXiv 2505.16716 ↗First posted 22 May 2025cs.CC cs.DM cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different, non-equivalent definitions of what a linear region actually is. We systematically assess which papers use which definitions and discuss how they relate to each other. We then analyze the computational complexity of counting the number of such regions for the various definitions. Generally, this turns out to be an intractable problem. We prove NP- and #P-hardness results already for networks with one hidden layer and strong hardness of approximation results for two or more hidden layers. Finally, on the algorithmic side, we demonstrate that counting linear regions can at least be achieved in polynomial space for some common definitions.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 25 of its 38 references that are in the map. First posted on arXiv 22 May 2025.

Builds on

25 of 38 references.

References · 25

  1. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  2. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 415
  3. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  4. 2016On the Expressive Power of Deep Neural Networkscited by 306
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 257
  6. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  7. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 161
  8. 2020Exactly Computing the Local Lipschitz Constant of ReLU Networkscited by 102
  9. 2019Reverse-Engineering Deep ReLU Networkscited by 83
  10. 2021Towards Lower Bounds on the Depth of ReLU Neural Networkscited by 56
  11. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  12. 2021Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sumscited by 37
13 more
  1. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  2. 2022Improved Bounds on Neural Complexity for Representing Piecewise Linear Functionscited by 26
  3. 2023Training Neural Networks is NP-Hard in Fixed Dimensioncited by 23
  4. 2021The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionalitycited by 22
  5. 2022Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networkscited by 22
  6. 2022On the Number of Regions of Piecewise Linear Neural Networkscited by 21
  7. 2021On the Expected Complexity of Maxout Networkscited by 15
  8. 2022Training Fully Connected Neural Networks is existsℝ-Completecited by 15
  9. 2024Decomposition Polyhedra of Piecewise Linear Functionscited by 9
  10. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  11. 2025Bounds on the Number of Pieces in Continuous Piecewise Affine Functionscited by 2
  12. 2024A Computational Tropical Geometry Framework for Neural Networkscited by 1
  13. 2025Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2cited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 6.

7 papers.

  1. 2025Parameterized Hardness of Zonotope Containment and Neural Network Verificationcited by 5
  2. 2026ExLipBaB: Exact Lipschitz Constant Computation for Piecewise Linear Neural Networkscited by 1
  3. 2026Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networkscited by 1
  4. 2026Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networkscited by 1
  5. 2026Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Lossescited by 0
  6. 2026Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexitycited by 0
  7. 2026Towards an Expressivity-Normalized Energy-Demand Comparison of ANNs and SNNscited by 0