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
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.
Fig. 2: MDL classification (compression as likelihood). Two classes, each represented by a model Bi built from its training data, are compressed alone and then with the test sample x appended. The conditional code length Δi=C(Bix)−C(Bi) 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 Δ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.
Fig. 3: The compression-based ML design space. Every method in Table I amounts to selecting one option per stage of the pipeline C→S→M→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.
TABLE II: Computational cost of compression-based ML approaches; n is the number of samples and ∣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.
Δ
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=103
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).
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.
The recent developments in machine learning have highlighted a conflict between online platforms and their users in terms of privacy. The importance of user privacy and the struggle for power over user data has been intensified as regulators and operators attempt to police online platforms. As users have become increasingly aware of privacy issues, client-side data storage, management, and analysis have become a favoured approach to large-scale centralised machine learning. However, state-of-the-art machine learning methods require vast amounts of labelled user data, making them unsuitable for models that reside client-side and only have access to a single user's data. State-of-the-art methods are also computationally expensive, which degrades the user experience on compute-limited hardware and also reduces battery life. A recent alternative approach has proven remarkably successful in classification tasks across a wide variety of data -- using a compression-based distance measure (called normalised compression distance) to measure the distance between generic objects in classical distance-based machine learning methods. In this work, we demonstrate that the normalised compression distance is actually not a metric; develop it for the wider context of kernel methods to allow modelling of complex data; and present techniques to improve the training time of models that use this distance measure. We demonstrate that the normalised compression distance works as well as and sometimes better than other metrics and kernels -- while requiring only marginally more computational costs and in spite of the lack of formal metric properties. The end results is a simple model with remarkable accuracy even when trained on a very small number of samples allowing for models that are small and effective enough to run entirely on a client device using only user-supplied data.
Charles Meyers, Aaron MacSween, Erik Elmroth +1
Institute for Experiential AI, Northeastern University, Boston, United States · Department of Computer Science, Umeå University, Umeå, Sweden
The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. Here we focus on settings in which that intuition can be made mathematically precise, surveying formal connections among learning algorithms, data compression, and computational complexity theory, with an emphasis on recent progress and current frontiers. We describe how techniques from complexity theory can guide the design of both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how learning algorithms can yield new insights and results in complexity theory. A central theme is the role of data compression as a bridge between learning and complexity, especially through an area called meta-complexity, which studies the computational difficulty of compression problems and time-bounded variants of Kolmogorov complexity.
Halley Goldberg, Mikito Nanashima, Igor C. Oliveira
Department of Computer Science, University of Oxford · School of Computing, Institute of Science Tokyo · Department of Computer Science, University of Warwick