A mathematical preprint reports an exponential width gap across adjacent fixed depths in ReLU networks. For every input dimension of at least 2 and every shallower depth of at least 2, the construction produces a target that a network one layer deeper can realize with width at most a constant times the fourth power of the dimension. A shallower network at or below the theorem's stated width threshold has expected squared L2 error, a measure of average squared difference under the chosen distribution, of at least 1/24 under a specially constructed, absolutely continuous distribution.
Depth is the number of layers, while width is the number of units available in a layer. The result says that adding one layer can change the size of the network needed to represent the same target from an exponential burden for the shallower model to a polynomial-width construction for the deeper one. For widths at or below the theorem's threshold, the shallower model's average squared error stays above a fixed constant. The authors also state that this L2 lower bound yields the corresponding exact-computation hierarchy across adjacent depths.
How the width gap is built
The proof is a constructive induction. It recursively copies a preceding hard function, places copy centers in general position, and uses the resulting hyperplane-intersection property to obtain a lower bound for shallower networks. The perturbation step makes the relevant augmented-coordinate determinants nonzero, putting the perturbed vertices in general position.
The induction works by finding outer cubes that the first layer's activation hyperplanes miss. On a missed cube, the first layer is affine, so that part can be absorbed into the next layer. The problem then reduces to the lower-bound statement for the preceding depth, allowing the argument to repeat. A supporting proposition supplies a vector-valued depth-2 ReLU map from a dimension-d input to a dimension-d output with width at most a constant times the fourth power of the dimension.
A strong result with a geometric catch
The L2 construction is not loose in every respect. Its target is globally 1-Lipschitz, meaning its output changes no faster than the distance between inputs, and its values lie between 0 and 1. The distribution is uniform on pairwise disjoint, axis-aligned open cubes. Those features provide the setting for the error lower bound, while the support itself is arranged on an exponentially scaled range of radii.
That exponential support scale is the main unresolved regularity issue. The paper leaves open whether a comparable exponential hierarchy can be proved with polynomial or constant support radius within the Vardi-Shamir regularity regime. The stronger question is therefore not answered by the L2 construction under those more restrictive geometric conditions.
A separate exact test
A separate construction tests exact agreement rather than average error. For dimensions of at least 3, it builds a globally bounded, continuous piecewise-linear target whose values range from 0 to 1, with Lipschitz constant no greater than two times the square root of the dimension. On the cube whose coordinates run from -1 to 1, the target's image is the full interval from 0 to 1. A depth-4 ReLU network computes it globally with hidden-layer widths no larger than a constant times the fourth power of the dimension, twice the dimension, and one. Any depth-3 network that agrees with the target on the unit hypercube requires exponentially many units in its first layer, even with unrestricted weights.
The exact lower bound comes from placing exponentially many depth-2 hard points in general position. A single first-layer activation hyperplane can contain at most as many of those points as the dimension, so covering the full set requires exponentially many activation hyperplanes and first-layer neurons. This geometric counting argument is why the lower bound remains in force even when the network's weights are unrestricted.
What remains unresolved
The two constructions should not be read as the same kind of evidence. The first is a distributional squared-error statement; the second is a pointwise exact-agreement statement on a domain. The authors explicitly note that the exact lower bound does not by itself establish hardness of approximation. They describe that comparison as a statement about geometric normalization, not as an approximation result.
Within its stated scope, the paper presents an exponential hierarchy across adjacent fixed ReLU depths and says the L2 lower bound also gives an exact-computation hierarchy. The document is identified as the preprint arXiv:2608.23877v2, dated 30 Aug 2026. Its acknowledgments say the research was supported by Israel Science Foundation Grant 1753/25.
Paper data and sources
Original title: Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks
Authors: Itay Safran
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-24
DOI: Not available
Original paper · Full text