Does Compression Imply Generalization? A Minimum Description Length Perspective

Lincen Yang; Jiayang Shi; Nan Pu; Daniël M. Pelt; Matthijs van Leeuwen; Zhong Li; Shujian Yu

cs.LGOct 15, 2026

Does Compression Imply Generalization? A Minimum Description Length Perspective

Authors: Lincen Yang, Jiayang Shi, Nan Pu, Daniël M. Pelt, Matthijs van Leeuwen, Zhong Li, Shujian Yu

Organizations: Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands · Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands · Hefei University of Technology, Hefei, China · Great Bay University, Dongguan, China ·

Abstract

A central question in modern learning theory is what notion of compression, if any, explains why over-parameterized neural networks generalize. Existing answers measure complexity at different levels, ranging from weights to representations; however, estimating the associated quantities either requires held-out data in principle or relies on the challenging (ultra) high-dimensional mutual information estimation. To overcome these challenges, we approach the question through the minimum description length (MDL) principle, and specifically, we propose the prequential regret as a complementary signal that is computable from the training trajectory alone. We establish that, in the (nearly) interpolating regime, the expected prequential regret upper-bounds the description length of the trained parameter under the algorithm-induced distribution, and that this description length translates into a high-probability generalization bound in the PAC-MDL setting. Along the way, we show that the encoder-complexity correction recently added to the algorithm-level information bottleneck (IB) is upper-bounded by an MDL parameter description length, \new{bringing together} the two views of compression from MDL and IB. Empirically, the prequential regret tracks the generalization error on CIFAR-10 and CIFAR-100, with Pearson correlations exceeding 0.9.

Figures & tables

	Spearman corr.		Pearson corr.		Kendall corr.
Generalization gap:	Loss	Error	Loss	Error	Loss	Error
$\frac{1}{D}\sum_{l=1}^{D}\check{I}(X;Z_{l}^{s})$	0.8481	0.7410	0.2116	0.1831	0.6425	0.5436
$\min_{l\in[D]}\check{I}(X;Z_{l}^{s})$	0.7145	0.5602	0.7203	0.5719	0.4461	0.3404
$\frac{1}{D}\sum_{l=1}^{D}\check{I}(X;Z_{l}^{s}\mid Y)$	0.8481	0.7406	0.2140	0.1853	0.6427	0.5435
$\min_{l\in[D]}\check{I}(X;Z_{l}^{s}\mid Y)$	0.7004	0.5434	0.7062	0.5560	0.4386	0.3305
$\check{I}(S;\theta_{D+1}^{S})$	0.4688	0.3112	0.2512	0.0775	0.2121	0.1208

Table 1: Correlations between generalization-bound quantities and the empirical generalization gap on CIFAR-10, measured both in loss and in classification error. Notation follows the previous work on IB generalization bounds [ 25 ] . We write

S

for the training sample,

D

for the network depth,

\check{I}

for a finite-sample mutual-information estimator,

Z^{s}_{l}

for the activations at layer

l

on data subsample

s

\theta^{S}_{l}

for the parameters at layer

l

trained on

S

, and

\theta^{S}_{D+1}

for the full network parameter trained on

S

. The baseline

\check{I}(S;\theta^{S}_{D+1})

is the parameter-information quantity

I(S;W)

of the information-theoretic line [ 33 , 42 ] and is the only pure model-complexity baseline besides ours. Best results are bolded.

Figure 1: Correlation between the prequential regret and the generalization gaps on CIFAR-100.

Neural Network Generalization

Neural network generalization studies why trained models perform well on unseen data and how architecture, data, and training shape that ability.

See all 299 papers

Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data
Jul 13, 2026Shikai Qiu, Marc Finzi, Yujia Zheng +2Model Compression Neural Network Generalization
New York University · Carnegie Mellon University
Prediction Under Imperfect Compression: A Theory of Approximate MDL
Jun 3, 2026Qian Li, Xinyu Mao, Shang-Hua Teng +1Minimum Description Length Approximation Algorithms
Shenzhen Research Institute of Big Data · University of Southern California
Learning is Forgetting: LLM Training As Lossy Compression
Apr 8, 2026Henry C. Conklin, Tom Hosking, Tan Yi-Chern +5Language Model Pretraining LLM Compression
Princeton University · Cohere

Jul 13, 2026J/K move · Enter open · S save

Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data

Shikai Qiu, Marc Finzi, Yujia Zheng, Kun Zhang+1

New York University · Carnegie Mellon University

Model Compression Neural Network Generalization Language Model Generalization

Open paper AskPDF arXiv

Compression is fundamental to intelligence. A model that can represent its training data as a short code has discovered regularities that enable generalization. Large neural networks may learn functions far simpler than their parameter counts suggest, but it is challenging to construct codes that realize this simplicity. Parameter-based methods such as quantization produce code lengths that scale with model size, insensitive to how much information the parameters store. Prequential coding bypasses this issue by compressing the training trajectory, but codes the exact data sequence regardless of how much the model learns, yielding large codes when the data has high entropy. We introduce requential coding, where a teacher model selects training samples drawn from the student's own distribution. The student's code records only these selections, which cost bits only where teacher and student disagree. The resulting code length is independent of parameter count and data entropy, and often orders of magnitude shorter than the prequential counterpart, with an advantage that grows with scale. This compression sheds light on phenomena inaccessible to prior compressors. Holding loss fixed, larger models and ensembles compress to much smaller sizes despite more parameters. Plugged into a PAC-Bayes bound, the requential code yields state-of-the-art generalization guarantees for billion-parameter LLMs, outperforming bounds built on aggressive post-training quantization even granted zero error. The bound tightens with scale in the compute-optimal regime, as models become increasingly compressible relative to dataset size. The same code predicts that models gradually overfit when trained for multiple epochs. It also isolates the learnable information in a dataset from its unpredictable, random content, revealing that lower-entropy text holds far more learnable structure than higher-entropy image data.

Abstract

Neural Network Generalization

Explore similar work

Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data

Prediction Under Imperfect Compression: A Theory of Approximate MDL

Learning is Forgetting: LLM Training As Lossy Compression