An Introduction to Compression-Based Machine Learning

John Hurwitz; Edward Raff; Charles K. Nicholas

cs.LGSep 18, 2026

An Introduction to Compression-Based Machine Learning

Authors: John Hurwitz, Edward Raff, Charles K. Nicholas

Organizations: University of Maryland, Baltimore County · CrowdStrike · Syracuse University

Abstract

Any lossless compression algorithm (like gzip) may be converted into a machine learning method, via either Normalized Compression Distance or the Minimum Description Length principle. Any auto-regressive model may be converted into a lossless compression method via entropy coding. This seemingly circular dependence has unrealized potential in modern artificial intelligence and machine learning, and we survey and formalize the various strategies that have been used to leverage compression for machine learning. We introduce and empirically validate a design framework for compression-based ML, finding compression-based methods competitive with conventional baselines and decisively stronger on malware. We find that varying these design choices yields accuracy gains of up to 0.62.

Figures & tables

Panel of Figure 1 — Fig. 1: Illustration of NCD between three byte sequences. Sequences $x$ and $y$ share repeating sub-patterns, so their joint compression $C(xy)$ yields a small NCD. Sequence $z$ shares little structure with $x$ , resulting in a large NCD. Output block widths represent compressed sizes; diagonal stripes indicate the source sequences.

Panel of Figure 2 — Fig. 2: MDL classification (compression as likelihood). Two classes, each represented by a model $B_{i}$ built from its training data, are compressed alone and then with the test sample $x$ appended. The conditional code length $\Delta_{i}=C(B_{i}x)-C(B_{i})$ is the extra cost of encoding $x$ under each model; $x$ is assigned to the class minimizing it. Output block widths represent compressed sizes; the solid segment is $\Delta_{i}$ .

Work	Compressor	Measure	Context Source	Context Injection Mechanism	Prediction
[ 45 ]	PPM	conditional code length	probabilistic model	model-conditioned encoding	MDL
[ 55 ]	domain-specific (DNA)	NCD (variant)	single sample	string concat	tree-building
[ 44 ]	gzip	conditional code length	aggregated class data	string concat	1-NN, tree-building
[ 56 ]	PPM	conditional code length	probabilistic model	model-conditioned encoding	MDL
[ 7 ]	gzip, domain-specific (DNA)	NCD	single sample	string concat	tree-building
[ 48 ]	zip	CDM	single sample	string concat	1-NN, clustering

TABLE I: Papers in compression-based ML and their settings under our framework.

Panel of Figure 4 — Fig. 3: The compression-based ML design space. Every method in Table I amounts to selecting one option per stage of the pipeline $C\to S\to M\to P$ . Compression-as-similarity (blue) picks a single-sample context, a compression distance, and a distance-based predictor; compression-as-likelihood (orange) picks a learned class model such as a compression dictionary or compressor state, a conditional code length, and the MDL rule.

D[i][j]=\frac{C(x_{i}y_{j})-\min(C(x_{i}),C(y_{j}))}{\max(C(x_{i}),C(y_{j}))}

Algorithm 1 NCD-KNN Classification

Approach	Compressor calls	Input per call
NCD $+$ $k$ -NN	$\mathcal{O}(n^{2})$	train $+$ test sample
LZJD / BWMD	$\mathcal{O}(n)$	one sample
Implicit-model MDL	$\mathcal{O}(n\|\mathcal{Y}\|)$	class context $+$ test sample
Explicit-model MDL	$\mathcal{O}(n\|\mathcal{Y}\|)$	test sample only

TABLE II: Computational cost of compression-based ML approaches;

n

is the number of samples and

|\mathcal{Y}|

the number of classes. LZJD/BWMD transform single samples into a compressed representation which are directly comparable via their respective dissimilarity measures.

Fig. 4: Accuracy span across our compression-based ML design choices. Performance is highly variable, and the degree to which varying one particular design choice matters is domain-dependent.

Domain	Regime	method	Comp.	Base.	$\Delta$	ms/query
text	1-shot	NCD	0.344	0.314	+0.030	0.96
	5-shot	MDL	0.426	0.436	-0.011	0.08
	10-shot	MDL	0.513	0.509	+0.004	0.17
	$n{=}10^{3}$	MDL	0.800	0.816	-0.016	0.23
	full	MDL	0.906	0.927	-0.021	1.22
malware	1-shot	MDL	0.396	0.181	+0.215	17.93

TABLE III: Compression-based classification against standard feature-based classifiers in both few-shot and full dataset setting. comp. and base. report their best configurations. method reports winning compression-based method. NCD not run in full dataset setting. Timings are single-threaded on an Apple M1 Max (10-core, 64 GB).

Minimum Description Length

Minimum Description Length (MDL) selects models by minimizing the bits needed to encode both a model and the data it fails to explain.

See all 16 papers

Can Deep Neural Networks Improve Compression of Very Large Scientific Data?
Jun 12, 2026Muhannad Alhumaidi, Guozhong Li, Spiros Skiadopoulos +1Predictive Coding
King Abdullah University of Science and Technology · Thuwal, Saudi Arabia · University of the Peloponnese +1
Tiny, Hardware-Independent, Compression-based Classification
Mar 6, 2026Charles Meyers, Aaron MacSween, Erik Elmroth +1Kernel Methods Data-Efficient Learning
Institute for Experiential AI, Northeastern University, Boston, United States · Department of Computer Science, Umeå University, Umeå, Sweden
Learning, Compression, and Meta-Complexity
Oct 12, 2026Halley Goldberg, Mikito Nanashima, Igor C. OliveiraKolmogorov Complexity Statistical Learning Theory
Department of Computer Science, University of Oxford · School of Computing, Institute of Science Tokyo · Department of Computer Science, University of Warwick

Jun 12, 2026J/K move · Enter open · S save

Can Deep Neural Networks Improve Compression of Very Large Scientific Data?

Muhannad Alhumaidi, Guozhong Li, Spiros Skiadopoulos, Panos Kalnis

King Abdullah University of Science and Technology · Thuwal, Saudi Arabia · University of the Peloponnese+1

Predictive Coding

Open paper AskPDF arXiv

Error-bounded lossy compression is a fundamental technique for managing the rapidly growing volumes of scientific data produced by modern simulations and observational instruments. Most state-of-the-art-compressors follow a prediction-residual paradigm, where compression effectiveness depends on the quality of the predictor: more accurate predictions generate smaller residuals that are easier to compress. This observation raises a question: can modern machine learning models serve as superior predictors for scientific data compression? Answering this question directly is challenging because developing compression-specific ML predictors requires substantial resources. Instead, we leverage the climate domain where highly accurate pretrained weather forecasting foundation models already exist, making them an ideal testbed. We present a framework that integrates spatial and temporal deep learning models into a conventional error-bounded compression pipeline. The framework supports auto-regressive forecasting models and avoids error accumulation. Using ERA5 climate data as a representative large-scale scientific dataset, we evaluate three distinct ML predictors: a VAEformer-based codec (CRA5), a graph neural network forecaster (GraphCast), and a vision-transformer forecaster (Aurora), against the state-of-the-art compressor SZ3.1 under identical quantization and entropy-coding backends. Our evaluation over approximately 1.7 TB of data reveals a surprising result: although ML predictors generate more accurate predictions and can improve reconstruction quality by up to 91% while achieving up to 9.6x higher compression ratios for highly predictable variables, they do not improve overall dataset-level compression ratio. We show that prediction accuracy alone is insufficient: the spatial structure of the resulting residuals plays a decisive role in entropy coding efficiency.

Abstract

Minimum Description Length

Explore similar work

Can Deep Neural Networks Improve Compression of Very Large Scientific Data?

Tiny, Hardware-Independent, Compression-based Classification

Learning, Compression, and Meta-Complexity