Definition

A network built from piecewise-linear units (ReLU, leaky ReLU, absolute value, max-pooling) computes a continuous piecewise-affine function. Fixing an activation pattern (which side of its breakpoint each unit falls on, at every layer) restricts the network to a single affine map on the corresponding region of input space. Input space therefore decomposes into a finite arrangement of convex polyhedral cells — the linear regions — glued along shared facets into a polyhedral complex. Two regions sharing a facet differ in exactly one unit’s activation pattern.

Relative to the decision boundary

Decision boundary (as a codimension-1 hypersurface) catalogs a single codimension-1 level set — where the network’s output crosses a class threshold. The linear region arrangement is a different, larger object: it is the entire combinatorial partition induced by every unit’s breakpoint at every layer, most of which have nothing to do with the eventual output threshold. A network can have an extremely simple decision boundary while still inducing an astronomically complex region arrangement underneath it (this is precisely the gap that motivates counting/ bounding the number of regions). The decision boundary is a subset of region-boundary facets; the region arrangement is the ambient structure those facets are drawn from.

Combinatorial-complexity theory vs. real-network measurement

A large body of purely theoretical work counts or bounds the maximum possible number of linear regions as a function of depth and width (Montúfar et al. 2014; Raghu et al. 2017; Serra et al. 2018, among others) without measuring what real trained networks actually produce. This map only catalogs entries where the arrangement (or a property of it — density, connectivity-graph structure, region volumes) is measured on a real, gradient-trained network, not purely enumerated in the abstract.

Key evidence

Gaines & Bi (2026) treat the region arrangement as a graph — one node per polyhedral region, edges between regions sharing a facet — and prove the average degree of this connectivity graph is upper-bounded by $2d$ ($d$ = input dimension) independent of network width or depth, with graph diameter bounded independent of $d$. They then measure the real connectivity graph via exact BFS enumeration of the polyhedral complex on networks trained on MNIST (a small fully-connected net), CIFAR-10 (a CNN’s classifier sub-network after a fixed feature-split layer), and California Housing (a regression MLP), alongside synthetic data. Across these real-data-trained networks: average node degree climbs toward the $2d$ bound as network size increases; the per-region neighbor-count distribution is unimodal, right-skewed, and peaks just below $2d$; and regions containing training data points are, on average, more connected than regions that don’t. Purely observational/structural (no causal intervention on the arrangement itself). See gaines-bi-2026-a-real-relu-networks-connectivity-graph-of-polyhedral-linear-regions-converges-toward-its-2d-average-degree-bound-with-data-containing-regions-more-connected.

Patel & Montúfar (2024) define local complexity — the expected density of the region-boundary “nonlinear locus” near a data distribution, estimated via bias-noise perturbation — as a finer-grained, localized measurement of the same arrangement, rather than a global count or connectivity statistic. On a real 4-layer MLP (200 units/layer) trained on 1,000 real MNIST images, local complexity and total variation both drop sharply in the terminal phase of training, coinciding with an increase in adversarial robustness; the result is offered as empirical support for a related finding (Humayun et al. 2024) that the nonlinear locus of a trained ReLU classifier concentrates near the decision boundary and flattens near training data. Purely observational (training dynamics and a weight-decay hyperparameter are varied; the arrangement itself is only measured). See patel-montufar-2025-local-complexity-density-of-the-relu-linear-region-boundary-drops-during-the-terminal-phase-of-training-on-real-mnist-images-coinciding-with-increased-adversarial-robustness.

Balestriero & Baraniuk’s expanded “Mad Max” paper (arXiv:1805.06576, §6.4) gives an early, small-scale direct visualization: a real, gradient-trained 3-layer fully-connected network (2D input, 45→3→4 units, softmax output, trained with Adam and batch norm to 98% training accuracy on 20,000 synthetic 2D points from 4 classes) induces a region arrangement that is sampled and plotted directly over $\mathbb{R}^2$. Even in this simple network, the per-layer partition regions are shown to be neither convex nor connected once composed across layers — a direct visual counterexample to any assumption that the arrangement inherits simple (e.g. convex) shape from its individual linear layers. Purely observational. See balestriero-baraniuk-2018-a-real-trained-3-layer-relu-classifiers-composed-linear-region-partition-is-directly-visualized-on-2d-data-and-the-per-layer-regions-are-neither-convex-nor-connected.

How to detect it

Enumerate activation patterns reachable by a piecewise-linear network (exact BFS/traversal over the polyhedral complex, or Monte-Carlo/grid sampling of input space for a cheap approximation); for each sampled or enumerated region, record its polyhedral facets (shared boundaries with neighboring regions), volume, and which training/test points (if any) fall inside it. Local, distribution-weighted density of the region boundary near a data manifold can be estimated without full enumeration via a bias-noise perturbation estimator (Patel & Montúfar 2024).

Key papers

• Gaines, B. & Bi, J. (2026). Characterizing the Discrete Geometry of ReLU Networks. arXiv:2606.07728 — connectivity-graph degree/diameter bounds and their real-network measurement on MNIST/CIFAR-10/California Housing.
• Patel, N. & Montúfar, G. (2024). On the Local Complexity of Linear Regions in Deep ReLU Networks. arXiv:2412.18283 — local-complexity density estimator and its measured drop during late training on real MNIST data.
• Balestriero, R. & Baraniuk, R. (2018/expanded). Mad Max: Affine Spline Insights into Deep Learning (originally A Spline Theory of Deep Networks, ICML 2018). arXiv:1805.06576 — direct visualization (§6.4) of a real trained network’s composed, non-convex/non-connected region partition.