Width-Independent Compressibility of Deep Neural Networks

Hong-Yi Wang; Mingze Wang; Liu Ziyin

cs.LGAug 22, 2026

Width-Independent Compressibility of Deep Neural Networks

Authors: Hong-Yi Wang, Mingze Wang, Liu Ziyin

Organizations: Princeton University Princeton, NJ 08544 · Peking University Beijing, China 100871 · Massachusetts Institute of Technology Cambridge, MA 02139

Abstract

It has long been known that well-trained neural networks can be compressed very strongly without affecting their performance, an important phenomenon that remains poorly understood. We prove a uniform compressibility theorem for deep multilayer perceptrons with analytic activations. For a deep, wide fixed teacher network, there exists a narrow (same depth) network that approximately represents the same function as the original. The reachable compressed width is strikingly independent of the original width, but is $O((\log(1/\varepsilon))^{d_{in}})$ , where $\varepsilon$ is the error budget and $d_{in}$ is the effective input dimension. Our construction involves a novel derivative-matching technique which is aware of the low-dimensional input, and a layer-wise reweighting that preserves the input-output mapping.

Figures & tables

Figure 1: Single-layer compression error versus derivative-matching order

k

on a randomly initialized

[3,2048,2048]

network, for sigmoid (left) and GELU (right) activations. Each curve is one input radius

R

. Both panels exhibit geometric decay in

k

at every

R

, with the per-step rate slowing as

R

grows — the qualitative behavior predicted by the

(R/\rho_{0})^{k+1}

rate of Theorem 6 . For

R\leq 1

the curves saturate at the float32 noise floor (

\sim\!10^{-6}

) by

k\approx 5

; at

k=9

the error is below

10^{-5}

uniformly in the unit ball for both activations.

Figure 2: Composed compression error versus per-step derivative-matching order

k

on a randomly initialized

[2,1024,1024,1024,1024,2]

network, for sigmoid (left) and GELU (right). Each panel shows eight curves: four input radii

R\in\{0.3,0.5,1,2\}

in four colors, with backward order (compress the deepest hidden layer first) drawn solid with circles and forward order (shallowest first) drawn dotted with triangles. The two orders are essentially indistinguishable at every

(k,R)

. Each compression step reduces its hidden layer to

D_{k}=\binom{2+k}{2}\in\{1,3,6,\dots,66\}

neurons.

Figure 3: Compression of all three hidden layers of a trained

[2,512,512,512,1]

sigmoid MLP, without fine-tuning. Thin curves are the five seeds and bold curves their medians. Left: empirical maximum teacher–compression discrepancy on the held-out set and projected local searches; frozen random controls are shown for comparison. Right: target MSE, with the median uncompressed-teacher MSE dashed.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: End-to-end runtime of backward compression with the practical pivoted-QR implementation. The timed region includes derivative-feature evaluation, basis selection, the coefficient solve, weight reconstruction for every hidden layer, and the implementation’s numerical diagnostics; teacher construction and a small library warm-up are excluded. We use randomly initialized float64 sigmoid networks on CPU with one Torch/BLAS thread. Points are medians of three complete compressions and bars span their minima and maxima. Left: teachers

[3,d,d,1]

for

k=3,5,7

. Right: teachers

[3,1024,\ldots,1024,1]

with one through eight hidden layers at

k=5

Seed	Teacher MSE	$\rho_{1}$	$\widehat{q}_{2}$	First task-preserving $D_{k}$ (reduction)
0	$2.3490\!\times\!10^{-4}$	1.2632	7.87	66 ( $57.9\times$ )
1	$3.6973\!\times\!10^{-4}$	1.2829	7.00	21 ( $522.7\times$ )
2	$2.4447\!\times\!10^{-4}$	1.0715	14.46	36 ( $187.7\times$ )
3	$2.3616\!\times\!10^{-4}$	1.2011	8.32	28 ( $303.6\times$ )
4	$3.0791\!\times\!10^{-4}$	1.0520	13.81	21 ( $522.7\times$ )

Appendix

Table 1: Per-seed diagnostics after backward compression of all three hidden layers. The original network has

527{,}361

parameters. Layer 1 passes the radius check, while the sampled layer-2 diagnostic fails for every seed.

Explore similar work

Empirical Minimal-Realisation Compression of Deep Neural Networks via Controllability-Observability Tests
Jul 5, 2026Anis Hamadouche, Amir HussainReduced-Order Modeling Neural Network Compression
The School of Engineering & Physical Sciences Heriot-Watt University Edinburgh EH14 4AS, UK · SDAIA-KFUPM Joint Research Centre for Artificial Intelligence King Fahd University of Petroleum and Minerals Dhahran, Saudi Arabia
Universality in Deep Neural Networks: An approach via the Lindeberg exchange principle
May 4, 2026Filippo Giovagnini, Sotirios Kotitsas, Marco RomitoNeural Network Approximation Theory Wasserstein Distance
Approximation Theory for Neural Networks: Old and New
May 20, 2026Soumendu Sundar Mukherjee, Himasish TalukdarUniversal Approximation Neural Network Approximation Theory
Statistics and Mathematics Unit, Indian Statistical Institute, Kolkata

Jul 5, 2026, cs.LGJ/K move · Enter open · S save

Empirical Minimal-Realisation Compression of Deep Neural Networks via Controllability-Observability Tests

Anis Hamadouche, Amir Hussain

The School of Engineering & Physical Sciences Heriot-Watt University Edinburgh EH14 4AS, UK · SDAIA-KFUPM Joint Research Centre for Artificial Intelligence King Fahd University of Petroleum and Minerals Dhahran, Saudi Arabia

Reduced-Order Modeling Neural Network Compression

Open paper AskPDF arXiv

Deep neural networks often contain substantial hidden-state redundancy, but most compression methods operate directly on weights, neurons, or quantised representations without explicitly characterising the dynamical role of internal states. This paper proposes a controllability-observability framework for empirical state-order reduction of deep neural networks. By viewing a trained network as a depth-indexed nonlinear dynamical system, we construct data-driven reachability, observability, and balanced Gramians from hidden-state snapshots and output Jacobians. The resulting A/B/C tests estimate layer-wise reachable, observable, and jointly reachable--observable ranks. These ranks are then used not only as diagnostic measures of hidden-state redundancy, but also as actual compressed layer widths for realised reduced networks. Experiments on MNIST and CIFAR-10 compare the proposed balanced realisation against projection-based reduction, unstructured pruning, structured pruning, low-rank SVD, dynamic INT8 quantisation, and linear baselines. On MNIST, a four-layer SiLU DNN is reduced from state order 1024 to 277, giving 72.95% state compression and 73.48% parameter compression, while maintaining 95.45% accuracy compared with 96.60% for the full model. On CIFAR-10, a larger SiLU DNN is reduced from state order 4608 to 1339, giving 70.94% state compression and 83.09% parameter compression, while preserving accuracy from 54.45% to 54.44% and reducing CUDA inference latency by approximately 3X. The results show that balanced reachable-observable ranks provide a principled empirical minimal-realisation criterion for designing compact neural architectures with little or no loss in accuracy.

Abstract

Explore similar work

Empirical Minimal-Realisation Compression of Deep Neural Networks via Controllability-Observability Tests

Universality in Deep Neural Networks: An approach via the Lindeberg exchange principle

Approximation Theory for Neural Networks: Old and New