Width-Independent Compressibility of Deep Neural Networks
Hong-Yi Wang, Mingze Wang, Liu Ziyin
cs.LG, cond-mat.dis-nn, cs.IT
2026-08-22
Analytic deep MLPs compress to width O((log 1/ε)^d_in), independent of original width; a trained [2,512^3,1] net keeps task MSE after a 304× parameter cut.
Well-trained networks can be pruned, quantized, or stripped of layers with little loss. The practice is routine; the theory is not. Most compression guarantees control generalization or empirical error under a calibration distribution. Uniform, data-free certificates for a fixed network that compose across layers were previously available only in narrow settings, such as two-layer permutation-symmetric nets.
The question is concrete. Given one trained deep MLP, can you build a same-depth, much narrower network that approximates the same function uniformly on a bounded input domain? If so, how does the retained width scale with the error budget?
The setting is deep MLPs with analytic activations (sigmoid, tanh, GELU). ReLU is out of scope. The teacher is one fixed finite network; input dimension \(d{\mathrm{in}}\) is treated as \(O(1)\), hidden layers as wide.
The mechanism is derivative matching. A hidden layer is a finite sum of neurons. If the activation and the upstream map extend holomorphically, matching all input derivatives at the origin through order \(k\) controls the Taylor remainder by a geometric factor \((R/\rho0)^{k+1}\). The matching condition is finite-dimensional: about \(\binom{d{\mathrm{in}}+k}{d{\mathrm{in}}}\) scalar constraints per output coordinate. A deterministic rank reduction on the derivative-feature matrix keeps at most that many original neurons and recomputes the outgoing weights.
The matching order needed is \(\Theta(\log(1/\varepsilon))\), so the compressed width is \(O((\log(1/\varepsilon))^{d{\mathrm{in}}})\), with no extra explicit factor of the original width \(d\ell\). A smaller admissible effective input dimension \(m\) replaces \(d{\mathrm{in}}\) in the exponent. An architectural bottleneck earlier in the net can play the same role.
To compress every hidden layer, work backward from the last hidden layer. Backward order keeps each step's analytic constants bounded by the original teacher; forward order inflates outgoing norms into the next holomorphic radius and loses a rigorous guarantee. Split the total error budget evenly across layers, absorbing downstream Lipschitz factors computed from the original net.
On a randomly initialized \([3,2048,2048]\) net, the hidden layer is reduced from 2048 neurons to \(\binom{3+k}{3}\). Both sigmoid and GELU show geometric decay in \(k\) at every tested radius \(R\). For \(R\le 1\), the error hits the float32 floor (\(\sim 10^{-6}\)) by \(k\approx 5\); at \(k=9\) it is below \(10^{-5}\) on the unit ball.
A deep random net \([2,1024\times 4,2]\) is compressed in all four hidden layers. At \(k=10\) each layer goes from 1024 to 66 neurons, about a \(15\times\) width cut. Sigmoid reaches the noise floor by \(k\approx 2\) for \(R\le 1\); GELU at \(k=10\) ends below \(10^{-7}\) for \(R\le 1\). Forward and backward orders are indistinguishable at float32 precision, even though only backward is certified.
After unconstrained training, five seeds of a \([2,512,512,512,1]\) sigmoid MLP are compressed with no fine-tuning. The predeclared preservation rule is compressed MSE at most \(1.05\times\) the teacher's. The median first width that meets it is 28, a \(\sim 304\times\) cut in parameter count. Test/train MSE ratios sit in \([0.99953,0.99980]\). Assumption 4 is violated in every trial (layer 2 has \(R/\rho\ge 3\)), yet error still drops over the tested range of \(k\).
This is an existence certificate at the function level, not a pruning recipe. For a fixed teacher, effective complexity tracks data dimension more than the width you chose. Do not treat it as a drop-in compressor for LLMs: high-order derivative features are expensive in compute and memory, and the authors say so. The useful scale estimate is this: image datasets often have empirical intrinsic dimension 10–50; matching through fifth derivatives would retain widths from \(10^3\) to \(10^6\). A near-manifold extension would be the step that actually touches large-model compression.
ReLU is not analytic, so the Cauchy argument does not apply. The theorem is for one fixed teacher; width can still enter through weight norms, and there is no uniform cap for a family of wider and wider nets. All numerics use \(d{\mathrm{in}}=2\) or \(3\) toy MLPs, with no conv, attention, or residual blocks. The trained experiments violate the radius assumption, which both suggests the bound is conservative and shows that the formal condition is not a practical prerequisite. The algorithm is not a practical compressor as written.