Depth, Width, and the Linear Regions of ReLU Networks

A network whose activations are rectifiers and whose output layer is affine computes a continuous piecewise-linear function of its input. The input space is cut into cells, and inside each cell the network is exactly an affine map; the cells are bounded by the surfaces where some unit’s pre-activation changes sign. Counting those cells turns the vague notion of model capacity into a combinatorial statement about depth and width, and it is one of the few capacity measures for which exact formulas exist.

From rectified units to a hyperplane arrangement

The first hidden layer’s $k$ units each contribute a hyperplane in input space, the set where $w_i^{\top}x + b_i = 0$. On either side of each hyperplane the corresponding unit is either the identity or zero, so the sign pattern of all first-layer pre-activations is constant on each cell of the arrangement these hyperplanes form, and inside a cell the layer’s output is an affine function of the input. That argument repeats: within a fixed cell, layer two’s pre-activations are affine functions of the input, so its kink surfaces are also hyperplanes, and by induction every layer’s output is affine on any cell where no unit changes sign. The whole function is therefore an affine map per cell of a partition generated by hyperplanes, and the number of distinct affine maps the network can realize is bounded by the number of cells.

The bias term decides whether the hyperplanes are affine or pass through the origin. Without biases every unit’s kink surface contains the origin, which is not a degenerate curiosity but a real constraint inherited from the forward pass: a network of affine-homogeneous layers with rectified activations and no biases is positively homogeneous, $f(\alpha x) = \alpha f(x)$ for $\alpha > 0$, so the origin is a cone point for every cell and the count of cells is halved. Biases are what allow the arrangement to be in general position.

What a single layer’s arrangement can hold

The number of cells of an arrangement of $k$ hyperplanes in general position in $\mathbb{R}^{n}$ is

$$\sum_{i=0}^{n}\binom{k}{i}$$

for $k \ge n$, which follows from counting by the dimension of the intersection of the hyperplanes. For fixed input dimension this is a polynomial in $k$ of degree $n$: a plane with 10 lines has at most $1 + 10 + 45 = 56$ cells, and an input space of dimension 4 with 64 units admits at most $1 + 64 + 2016 + 41664 + 635376 = 679121$ cells. Doubling the width of that layer from 64 to 128 units multiplies the cell count by roughly $(128/64)^{4} = 16$. That polynomial degree in width, with the exponent fixed by the number of inputs, is the ceiling on what a single hidden layer can do: the piecewise-linear function of a wide shallow network can have many pieces, but their number grows like a power of the width rather than like an exponential.

The arrangement picture also quantifies how much of the input space is actually used. Of the cells of an arrangement of $k$ hyperplanes in $\mathbb{R}^{n}$, the number that are bounded is $\binom{k-1}{n}$, which for the 64-line plane arrangement is $\binom{63}{2} = 1953$ out of 2081 total, while in four dimensions with 64 hyperplanes it is $\binom{63}{4} = 595665$ out of 679121. The bounded fraction is large at these densities but falls toward zero as width grows with the input dimension fixed: most cells of a dense arrangement extend to infinity, which means most of the distinct affine pieces of a wide network describe behaviour far from the region where the training data lives.

Why depth multiplies instead of adding

Composition is where the exponent appears. A layer with $n_l$ units maps the arrangement of the previous layer through its own weight matrix, and each of the previous layer’s cells can be cut independently by the new layer’s kinks, so the number of regions of a stack is governed by a product over layers rather than a sum. For a network with $n_0$ inputs and hidden widths $n_1, \ldots, n_{L-1}$ the maximum number of linear regions is of the form

$$\prod_{l=1}^{L-1}\sum_{j=0}^{n_{0}}\binom{n_l}{j}$$

which is attained for suitable weight configurations when the widths are at least the input dimension. The result is exponential in depth and polynomial in each layer’s width, so a deep network with the same total number of units as a shallow one can in principle realize far more affine pieces, and depth is what converts a fixed unit budget into a combinatorial count rather than an algebraic one. The bound is also useless as a literal number for any real network: with four inputs, ten layers of 64 units gives a factor of 679121 per composition, a product with nine factors, which exceeds the number of distinguishable sign patterns the network could ever produce. The qualitative reading, that the count multiplies across layers, is the part that carries information.

What the count does and does not measure

The count is a statement about the function class, and it is a bound rather than a description of any particular trained model. Several qualifications limit how far it can be pushed.

A network with weights at a given point in training realizes one particular arrangement, and that arrangement changes as the weights rotate, so the region count at initialization is not the count after convergence, and nothing in the counting argument says which arrangement gradient descent will select within the class.

Units whose weight vectors are linearly dependent contribute no new hyperplanes, so a layer with $k$ units realizes the arrangement of the distinct directions among them, and effective width can be much smaller than nominal width. This is the same linear dependence that makes a hidden layer narrower than its input a rank bottleneck, as noted for dense layers; the counting result adds that a layer narrower than the input dimension cannot increase the region count beyond what the width allows.

The count says nothing about generalization. A function with billions of linear regions is a function in a large class; whether a trained member of that class predicts well on unseen data is a different question about the data distribution, the optimization, and the constraints implicitly imposed by the parameterization. The approximation-theoretic results that motivate width, such as the classical statement that a single hidden layer with enough units can approximate any continuous function on a compact set to arbitrary accuracy, are statements about existence of a member of the class and are subject to the same limitation.

Finally, the analysis is specific to piecewise-linear activations. Smooth activations produce smooth functions whose kink surfaces become thin transition regions, and the arrangement count no longer applies; pooling operations that take maxima fold together cells that were previously distinct, reducing the count below what the unit count would suggest, while absolute value and other piecewise-linear operations add fold surfaces of their own. Residual blocks, whose output is the sum of a skip path and a branch, have regions that are intersections of the two terms’ partitions, which increases the count rather than decreasing it, as the accounting in residual connections implies.

import numpy as np

def relu(x):
    return np.maximum(0.0, x)

def sign_pattern(x, weights):
    pat, h = [], x
    for W, b in weights:                 # each layer appends its unit signs
        h = relu(h @ W.T + b)
        pat.append(h > 0.0)
    return np.concatenate(pat, axis=-1).astype(np.uint8)

def grid_regions(weights, lo=-4.0, hi=4.0, res=400):
    xs = np.linspace(lo, hi, res)
    gx, gy = np.meshgrid(xs, xs)
    pts = np.stack([gx.ravel(), gy.ravel()], axis=1)
    return len({bytes(p) for p in sign_pattern(pts, weights)})

rng = np.random.default_rng(0)
one_layer = [(rng.normal(size=(10, 2)), rng.normal(size=10))]
# a grid count is a lower bound: it misses cells outside the sampled window
print(grid_regions(one_layer), "<= 56 cells for 10 lines in the plane")

A grid estimate of this kind only ever produces a lower bound, since cells outside the sampled window and cells smaller than the grid spacing are invisible to it. The arrangement formulas give the exact count for the configuration they describe, and the gap between an exact formula and an enumerable lower bound is itself informative: it measures how much of the input space a given parameter setting actually partitions, as opposed to how much it could in principle.