基于压缩的机器学习导论

# An Introduction to Compression-Based Machine Learning
Source: [https://arxiv.org/html/2609.21309](https://arxiv.org/html/2609.21309)
John Hurwitz1, Edward Raff123, Charles Nicholas1Affiliation:Affiliation:1University of Maryland, Baltimore CountyAffiliation:2CrowdStrikeAffiliation:3Syracuse 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\.

###### Index Terms:

Data compression, machine learning, normalized compression distance, minimum description length, Kolmogorov complexity, information theory, malware classification, text categorization

## IIntroduction

In 1999, Mahoney\[[1](https://arxiv.org/html/2609.21309#bib.bib1)\]posited that predicting the next character of a sentence with high accuracy should be the litmus test of AI, as improved prediction requires understanding the text semantically \(foreshadowing large language models\)\. He also noted that this task is equivalent to compression, and so he studied different compression algorithms likegzipand their ability to approach this next\-character prediction target, concluding:

> It is somewhat comforting to find that compression, like AI, is still unsolved\.

Despite a quarter\-century of progress, it is peculiar that AI is now much closer to being “solved” in the eyes of many compared to compression\. Today, a niche area of research has blossomed, directly connecting AI/ML and compression, often challenging our assumptions about the source of ML’s successes and failures\. In this article, we survey these compression\-based machine learning methods in light of the remarkable room for improvement and, at the same time, shed light on the insights that might still be extracted from Mahoney’s prognostications\.

Compression and prediction have long been recognized as closely related concepts, with MacKay famously noting that information theory and machine learning are “two sides of the same coin”\[[2](https://arxiv.org/html/2609.21309#bib.bib2)\]\. At the heart of data compression, the art of reducing the number of bits required to store information, is the prediction of future data\[[3](https://arxiv.org/html/2609.21309#bib.bib3)\]\. This connection has led to a growing body of machine learning literature on the use of compression algorithms for machine learning tasks\. To be specific, we are interested in the connections between lossless compression algorithms in the classical computer science sense, likegzip, and machine learning tasks\. A broad survey of all inspirations of “compression” \(e\.g\., like the hidden state of an auto\-encoder\) is beyond the scope of this article \(lossy compression, which allows less than perfect reconstruction of the input, is also beyond our scope\)\. Kolmogorov complexity\[[4](https://arxiv.org/html/2609.21309#bib.bib4)\]will be of particular theoretical foundation for our discussion, as it is the length of the shortest program that produces a given input\. This is an uncomputable function, but provides the basis of our interest ininformation distance\[[5](https://arxiv.org/html/2609.21309#bib.bib5),[6](https://arxiv.org/html/2609.21309#bib.bib6)\], an information\-theoretic notion of distance based onalgorithmicsimilarity\. By replacing the Kolmogorov complexity with an empirical compression algorithm, one obtains a*compression distance*\[[7](https://arxiv.org/html/2609.21309#bib.bib7)\], and along with it, practical methods for leveraging compression in machine learning\.

At a high level, compressed lengths can be interpreted in two distinct ways: either as a measure of similarity between objects, or as a proxy for likelihood under a model\. Viewed through the similarity lens, compressed lengths induce a compression distance function that can work for any byte sequence by leveraging the fact that two similar sequences should produce improved compression ratios if considered together\. This is the insight behind the seminal Normalized Compression Distance \(NCD\)\[[7](https://arxiv.org/html/2609.21309#bib.bib7)\]\. Viewed through the likelihood lens, we obtain another way of using compression for prediction inspired by the Minimum Description Length \(MDL\)\[[8](https://arxiv.org/html/2609.21309#bib.bib8)\]principle\. As there is a direct correspondence between code length and probability, a compression model that achieves the shortest code length when compressing a sample is equivalent to the model that maximizes its likelihood\. Since compressors operate over bytes, compression\-based ML approaches have been especially useful in the cybersecurity domain, where deep learning struggles to learn useful representations for executable files, resulting in various applications for malware classification\[[9](https://arxiv.org/html/2609.21309#bib.bib9),[10](https://arxiv.org/html/2609.21309#bib.bib10),[11](https://arxiv.org/html/2609.21309#bib.bib11),[12](https://arxiv.org/html/2609.21309#bib.bib12),[13](https://arxiv.org/html/2609.21309#bib.bib13),[14](https://arxiv.org/html/2609.21309#bib.bib14)\]\.

Scope\.Throughout this survey, we use the term compression in the classical lossless data compression sense: algorithms that reduce the number of bits required to represent data while preserving exact reconstruction\. Our focus is on how such compressors induce similarity measures, likelihood estimates, and predictive models for machine learning\. We do not survey model compression techniques whose goal is to reduce the size or computational cost of machine learning models themselves, including quantization, pruning, distillation, sparsification, low\-rank approximation, or related efficient\-inference methods\. Although these areas also involve compression, they address a fundamentally different question: how to compress a learned model rather than how to perform learning using compression\.

To properly position the reader to appreciate the unique connection between data compression and modern ML, we will begin with historical context and key terms in compression from §[II](https://arxiv.org/html/2609.21309#S2), including how probabilistic predictive models can be turned into a lossless compression algorithm through entropy coding\. This connection has only recently been leveraged by modern deep learning to develop better compression algorithms, as we highlight in §[III](https://arxiv.org/html/2609.21309#S3)\. We then introduce the theoretical foundations of the NCD and the MDL principle in §[IV](https://arxiv.org/html/2609.21309#S4), before unifying existing compression\-based ML methods into a common design framework in §[V](https://arxiv.org/html/2609.21309#S5)with empirical validation\. We will address current challenges and open questions in §[VI](https://arxiv.org/html/2609.21309#S6)\. Finally, we will conclude in §[VII](https://arxiv.org/html/2609.21309#S7)\.

## IICompression Fundamentals

Data compression refers to schemes that try to represent data using fewer bits than were used in the original file\.Losslesscompression refers to such schemes that guarantee perfect reconstruction of the input data\. Some examples of lossless compression programs are DEFLATE\[[15](https://arxiv.org/html/2609.21309#bib.bib15)\]\(as utilized ingzipand PNG\),bzip2,LZMA, andzstandard\.

Every compression technique can be viewed as a combination of two distinct stages:modelingandcoding\[[3](https://arxiv.org/html/2609.21309#bib.bib3)\]\. Modeling is the process of identifying regularities in the data, while coding converts the modeled representation into a compact binary representation\. There are two main forms of modeling: statistical and dictionary\-based\. A statistical model yields probabilities for each symbol, and these probabilities can be encoded in a manner where common symbols use fewer bits than do rare symbols\[[16](https://arxiv.org/html/2609.21309#bib.bib16)\]\. Therefore, any model which produces next\-symbol probabilities can be converted into a lossless compression scheme by performingentropy codingon the probabilities, converting each symbol into a binary representation\. Good compression is achieved when the model produces high as well as accurate probabilities\. In contrast, dictionary\-based models don’t explicitly model per\-symbol probabilities; rather, they search for regularity in data by identifying repeated substrings\[[3](https://arxiv.org/html/2609.21309#bib.bib3)\]\. Dictionaries of substrings can either be explicitly or implicitly maintained by keeping a sliding window of past symbols in memory, within which the program can search for matches\.

Most popular compression programs nowadays are descendants of LZ77\[[17](https://arxiv.org/html/2609.21309#bib.bib17)\], the dictionary\-based compression algorithm from Lempel and Ziv’s seminal paper on sequential data compression\. The core idea of the algorithm is to search for backreferences to previously seen substrings in the input stream\. Their subsequent work\[[18](https://arxiv.org/html/2609.21309#bib.bib18)\]introduced LZ78, a compression algorithm that explicitly maintained a dictionary of previously seen substrings rather than maintaining a sliding window over a portion of the input stream\. Many other techniques for compression exist, though most practical tools use LZ\-style algorithms\. For a deeper review of data compression techniques, see\[[3](https://arxiv.org/html/2609.21309#bib.bib3),[19](https://arxiv.org/html/2609.21309#bib.bib19)\]\.

### II\-AInformation Theory: Entropy and Kolmogorov complexity

Data compression has strong theoretical roots in information theory\. Let𝒳\\mathcal\{X\}be a discrete alphabet andppa distribution over it\. \(Throughout, logarithms are base two and information is measured in bits\.\) Theinformation contentof a symbolx∈𝒳x\\in\\mathcal\{X\}is−log⁡p⁡\(x\)\-\\log p\(x\), the ideal code length for that symbol\. Theentropyofppis the expected information content of its symbols,H\(p\):=−∑x∈𝒳p\(x\)logp\(x\)H\(p\):=\-\\sum\_\{x\\in\\mathcal\{X\}\}p\(x\)\\log p\(x\), and by Shannon’s Source Coding Theorem\[[20](https://arxiv.org/html/2609.21309#bib.bib20)\]is the ultimate lossless compression limit for a known distribution\. Encoding data drawn fromppwith a code optimal for some other distributionqqinstead costs thecross\-entropyH\(p,q\)=H\(p\)\+KL\(p∥q\),H\(p,q\)=H\(p\)\+\\mathrm\{KL\}\(p\\,\\\|\\,q\),which exceeds the entropy by the Kullback–Leibler divergence\.

*Entropy coding*refers to a class of algorithms which attempt to realize these ideal code lengths in practice, converting a model’s probabilities into a bit string whose length approaches−log⁡p⁡\(x\)\-\\log p\(x\)per symbol\. Two of the most common entropy coding techniques are Huffman coding\[[21](https://arxiv.org/html/2609.21309#bib.bib21)\], which assigns each symbol a unique integer\-length code where common symbols are represented with fewer bits than rare symbols, and arithmetic coding\[[22](https://arxiv.org/html/2609.21309#bib.bib22)\], which represents the entire sequence as a single real number of arbitrary precision\. Modern neural network\-based compression techniques often use arithmetic coding due to it being adaptive, as it can be used when the distribution changes on a per\-symbol basis\.

Kolmogorov complexity\[[4](https://arxiv.org/html/2609.21309#bib.bib4)\]K⁡\(x\)K\(x\)is the length of the shortest computer program that outputs the input stringxxand then halts\. While entropy gives the ultimate compression limit for probability distributions,KKgives such a limit for*individual objects*\. Conditional Kolmogorov complexityK⁡\(x\|y\)K\(x\|y\)is the length of the shortest program that outputs an input string given some second stringyyas input, formalizing the minimum amount of information needed to compute one object from another\. Though uncomputable,KKis upper semi\-computable\. Kolmogorov complexity formalizes the length of an object’s shortest effective description, and characterizes when a string is incompressible \(a program generating a high\-complexity string essentially encodes the string itself\)\. Conditional Kolmogorov complexity inspired theinformation distancemax⁡\{K⁡\(x\|y\),K⁡\(y\|x\)\}\\max\\\{K\(x\|y\),K\(y\|x\)\\\}and subsequently normalized information distanceNID​\(x,y\)=max⁡\{K⁡\(x\|y\),K⁡\(y\|x\)\}max⁡\{K⁡\(x\),K⁡\(y\)\}\\text\{NID\}\(x,y\)=\\frac\{\\max\\\{K\(x\|y\),K\(y\|x\)\\\}\}\{\\max\\\{K\(x\),K\(y\)\\\}\}, a metric in\[0,1\]\[0,1\]that theoretically captures “any effective resemblance between two objects”\[[6](https://arxiv.org/html/2609.21309#bib.bib6)\], in the sense that it minorizes all admissible distances\[[7](https://arxiv.org/html/2609.21309#bib.bib7)\]\. For a deep treatment of Kolmogorov complexity, see\[[23](https://arxiv.org/html/2609.21309#bib.bib23)\]\.

## IIIMachine learning for compression

Neural compression refers to the use of neural networks to perform data compression\. Neural compression techniques have in recent years become state\-of\-the\-art lossless compressors in domains such as text\[[24](https://arxiv.org/html/2609.21309#bib.bib24),[25](https://arxiv.org/html/2609.21309#bib.bib25),[26](https://arxiv.org/html/2609.21309#bib.bib26)\], images\[[27](https://arxiv.org/html/2609.21309#bib.bib27),[28](https://arxiv.org/html/2609.21309#bib.bib28)\], and driving video\[[29](https://arxiv.org/html/2609.21309#bib.bib29)\]due to the success of neural networks in complex data modeling\. The two primary lossless neural compression techniques are those based onautoregressive modelsand those based onlatent variable models\. For a comprehensive introduction to neural compression approaches, see\[[30](https://arxiv.org/html/2609.21309#bib.bib30)\]\.

Autoregressive models, such as Large Language Models \(LLMs\), predict the next symbol given previous symbols\. These probabilities can be encoded via entropy coding, and the better the model, the better the compression\. The negative log\-likelihood \(NLL\) of each symbol under the model provides a lower bound on the number of bits required to encode that symbol, illustrating that cross\-entropy loss can be interpreted as a compression objective\. This fact has resulted in a number of works applying autoregressive generative models directly to lossless text compression\[[31](https://arxiv.org/html/2609.21309#bib.bib31),[32](https://arxiv.org/html/2609.21309#bib.bib32),[33](https://arxiv.org/html/2609.21309#bib.bib33)\]and image compression\[[34](https://arxiv.org/html/2609.21309#bib.bib34)\]\. Latent variable models such as Variational Autoencoders \(VAEs\) can be combined with the “bits back coding” technique\[[35](https://arxiv.org/html/2609.21309#bib.bib35),[36](https://arxiv.org/html/2609.21309#bib.bib36)\]to implement a lossless compression scheme\.

Compression benchmarks have been introduced with the goal of spurring AI research\. The Hutter prize\[[37](https://arxiv.org/html/2609.21309#bib.bib37)\]is a challenge to losslessly compress 1GB of Wikipedia to the smallest file possible, under computational constraints\. The Large Text Compression Benchmark\[[24](https://arxiv.org/html/2609.21309#bib.bib24)\]is the same challenge but with relaxed computational constraints\. Both benchmarks are led by neural compression techniques, with the top entry of the Hutter prize a variant of CMIX\[[26](https://arxiv.org/html/2609.21309#bib.bib26)\], which uses an ensemble of neural networks to perform bit\-level prediction\. The top two entries of the Large Text Compression Benchmark are variants of CMIX and NNCP\[[25](https://arxiv.org/html/2609.21309#bib.bib25)\], the latter a neural network approach which trains over the sequence in an online fashion and compresses with arithmetic coding\. For illustration, as of September 2026,gzipcompresses 1 GB of Wikipedia to approximately 323 MB, while the top entry,fx2\-cmix\-transformer, compresses to approximately 97 MB\[[24](https://arxiv.org/html/2609.21309#bib.bib24)\], including the size of their respective programs\. Further, similar neural compression techniques lead the CommaVQ compression challenge to losslessly compress driving video frames tokenized by a VQ\-VAE\[[38](https://arxiv.org/html/2609.21309#bib.bib38)\]\.

## IVTheoretical Foundations of Compression for Machine Learning: Two Lenses

We now introduce the theoretical foundations of the compression\-as\-similarity lens and the compression\-as\-likelihood lens\. Existing compression\-based ML approaches differ primarily in how the compressor receives context and the interpretation of compressed lengths for prediction\. Similarity approaches treat individual data samples as context for a compression distance calculation, exemplified by NCD\. Likelihood approaches learn models from samples and treat those models as context, selecting the model which best compresses the data, exemplified by MDL\.

### IV\-ACompression as Similarity

Any lossless compression algorithm induces an information\-theoretic compression distance, capturing a notion of algorithmic \(dis\)similarity\. The fundamental insight of compression distance is that when two objects are compressed together, the resulting file size will be smaller if the compressor discovers shared information in one to help reconstruct the other\. LetC⁡\(x\)C\(x\)be the length of the compressed output in bytes when compressingxxwith some compression algorithm\. Then the Normalized Compression Distance \(NCD\) between two sequencesxxandyyis defined as follows:

NCD​\(x,y\)=C⁡\(x​y\)−min⁡\{C⁡\(x\),C⁡\(y\)\}max⁡\{C⁡\(x\),C⁡\(y\)\}\\textnormal\{NCD\}\(x,y\)=\\frac\{C\(xy\)\-\\min\\\{C\(x\),C\(y\)\\\}\}\{\\max\\\{C\(x\),C\(y\)\\\}\}\(1\)NCD is easier to understand if we assume \(without loss of generality\) thatC⁡\(y\)≥C⁡\(x\)C\(y\)\\geq C\(x\)\. Then the NCD becomesNCD​\(x,y\)=C⁡\(x​y\)−C⁡\(x\)C⁡\(y\)\\textnormal\{NCD\}\(x,y\)=\\frac\{C\(xy\)\-C\(x\)\}\{C\(y\)\}\. The numerator here represents the extra number of bits required to compressyy\(the sequence with the larger compressed representation\) given the information inxx\(the shorter compressed representation\), effectively testing how well the compressor can reuse information inxxto reconstructyy\. Effective reuse indicates information\-theoretic similarity\. The denominator is a normalizing factor enforcing a range of\[0,1\+ϵ\]\[0,1\+\\epsilon\]\. We provide an illustration of how NCD is used as a similarity measure in Fig\.[1](https://arxiv.org/html/2609.21309#S4.F1)\.

Three byte sequences:ababaxxbababyyabcefgzzStep 1: Compress eachC⁡\(CLOSEC\(ababaOPEN\)=\)=4 BC⁡\(CLOSEC\(bababOPEN\)=\)=4 BC⁡\(CLOSEC\(abcefgOPEN\)=\)=5 BCompressed size: shorter==more redundancy foundStep 2: Compress concatenationsC⁡\(CLOSEC\(abababababOPEN\)=\)=5 B\(shared\!\)C⁡\(CLOSEC\(ababaabcefgOPEN\)=\)=8 B\(no help\)Step 3: Compute NCDNCD​\(x,y\)=C⁡\(x​y\)−min⁡\{C⁡\(x\),C⁡\(y\)\}max⁡\{C⁡\(x\),C⁡\(y\)\}=5−44=0\.25\\text\{NCD\}\(x,y\)=\\dfrac\{C\(xy\)\-\\min\\\{C\(x\),C\(y\)\\\}\}\{\\max\\\{C\(x\),C\(y\)\\\}\}=\\dfrac\{5\-4\}\{4\}=\{\\color\[rgb\]\{0\.1797,0\.5469,0\.3398\}\\mathbf\{0\.25\}\}NCD​\(x,z\)=C⁡\(x​z\)−min⁡\{C⁡\(x\),C⁡\(z\)\}max⁡\{C⁡\(x\),C⁡\(z\)\}=8−45=0\.80\\text\{NCD\}\(x,z\)=\\dfrac\{C\(xz\)\-\\min\\\{C\(x\),C\(z\)\\\}\}\{\\max\\\{C\(x\),C\(z\)\\\}\}=\\dfrac\{8\-4\}\{5\}=\{\\color\[rgb\]\{0\.707,0\.2344,0\.2344\}\\mathbf\{0\.80\}\}0\.25≪0\.80\{\\color\[rgb\]\{0\.1797,0\.5469,0\.3398\}0\.25\}\\ll\{\\color\[rgb\]\{0\.707,0\.2344,0\.2344\}0\.80\}⇒\\Rightarrowcompressor confirmsxxandyyare more similar\.

Fig\. 1:Illustration of NCD between three byte sequences\. Sequencesxxandyyshare repeating sub\-patterns, so their joint compressionC⁡\(x​y\)C\(xy\)yields a small NCD\. Sequencezzshares little structure withxx, resulting in a large NCD\. Output block widths represent compressed sizes; diagonal stripes indicate the source sequences\.NCD is a realizable version of information distance which approximates Kolmogorov complexity using real compressors\. For a deeper treatment of Kolmogorov complexity, information distance, compression distance, and their applications, see\[[23](https://arxiv.org/html/2609.21309#bib.bib23)\]\.

Compression\-based ML has long shown a historical parallel to deep learning in that it eschews handcrafted feature engineering, allowing “the algorithm” to “figure it out”\. This compression\-as\-learning has been most widely applied to text categorization\[[39](https://arxiv.org/html/2609.21309#bib.bib39),[40](https://arxiv.org/html/2609.21309#bib.bib40),[41](https://arxiv.org/html/2609.21309#bib.bib41),[42](https://arxiv.org/html/2609.21309#bib.bib42),[7](https://arxiv.org/html/2609.21309#bib.bib7),[43](https://arxiv.org/html/2609.21309#bib.bib43),[44](https://arxiv.org/html/2609.21309#bib.bib44),[45](https://arxiv.org/html/2609.21309#bib.bib45)\], malware detection\[[46](https://arxiv.org/html/2609.21309#bib.bib46),[47](https://arxiv.org/html/2609.21309#bib.bib47),[10](https://arxiv.org/html/2609.21309#bib.bib10),[9](https://arxiv.org/html/2609.21309#bib.bib9),[11](https://arxiv.org/html/2609.21309#bib.bib11),[12](https://arxiv.org/html/2609.21309#bib.bib12)\], DNA sequence clustering\[[7](https://arxiv.org/html/2609.21309#bib.bib7)\], and data mining and anomaly detection\[[48](https://arxiv.org/html/2609.21309#bib.bib48),[49](https://arxiv.org/html/2609.21309#bib.bib49)\]\. A correspondence between compression distance approaches and traditional feature vector approaches has been established\[[50](https://arxiv.org/html/2609.21309#bib.bib50)\], with the mechanism of the compressor defining an implicit feature space\.

There exist variants of NCD that capture the same underlying notion of similarity\. The Chen\-Li Metric readsCLM​\(x,y\)=1−C⁡\(x\)−C⁡\(x\|y\)C⁡\(x​y\)\\textnormal\{CLM\}\(x,y\)=1\-\\frac\{C\(x\)\-C\(x\|y\)\}\{C\(xy\)\};\[[48](https://arxiv.org/html/2609.21309#bib.bib48)\]defines theCompression\-based Dissimilarity Measure\(CDM\):CDM​\(x,y\)=C⁡\(x​y\)C⁡\(x\)\+C⁡\(y\)\\textnormal\{CDM\}\(x,y\)=\\frac\{C\(xy\)\}\{C\(x\)\+C\(y\)\}; and\[[50](https://arxiv.org/html/2609.21309#bib.bib50)\]definescompression\-based cosine:CosS​\(x,y\)=1−C⁡\(x\)\+C⁡\(y\)−C⁡\(x​y\)C⁡\(x\)​C​\(y\)\\text\{CosS\}\(x,y\)=1\-\\frac\{C\(x\)\+C\(y\)\-C\(xy\)\}\{\\sqrt\{C\(x\)C\(y\)\}\}\. NCD, CDM, and CosS have all been shown to reduce to a canonical form\[[50](https://arxiv.org/html/2609.21309#bib.bib50)\]:1−C⁡\(x\)\+C⁡\(y\)−C⁡\(x​y\)f⁡\(x,y\)1\-\\frac\{C\(x\)\+C\(y\)\-C\(xy\)\}\{f\(x,y\)\}wheref⁡\(x,y\)f\(x,y\)is a normalizing term\. This helps to explain the highly similar experimental results regardless of the particular choice of these compression distance formulations\[[50](https://arxiv.org/html/2609.21309#bib.bib50),[51](https://arxiv.org/html/2609.21309#bib.bib51)\]\.

### IV\-BCompression as Likelihood

Machine learning is in the business of inductive inference, and the Minimum Description Length \(MDL\) principle\[[8](https://arxiv.org/html/2609.21309#bib.bib8)\]proposes a solution to the model selection problem through the lens of compression\. In MDL, the best model is the one that best compresses the data, considering the size of the model itself\. Often described as a formalization of Occam’s Razor, MDL explicitly ties learning to compression\. The minimization of the size of the encoding of the model plus the size of the encoding of the data, given the model, coincides with a natural take on practical data compression as balancing the compressed representation with the size of the compression program\. The MDL principle implies at least one way that learned compression models can yield classifications on data in an ML context: by learning a separate model per class, the class is chosen whose model best compresses the test sample\.

Formally, given a datasetDDand a set of candidate hypothesesℋ\\mathcal\{H\}, the MDL principle selects the hypothesisH∈ℋH\\in\\mathcal\{H\}that minimizes the total description lengthL⁡\(H\)\+L⁡\(D\|H\)L\(H\)\+L\(D\|H\)whereL⁡\(H\)L\(H\)represents the length of the description of the model, andL⁡\(D\|H\)L\(D\|H\)is the length of the data when encoded with the help of the model\. Using the well\-known correspondence between probability and code lengths that an event with probabilityppcan be encoded in−log2⁡p\-\\log\_\{2\}pbits, we see that the model which minimizes description length is equivalently the maximum a posteriori \(MAP\) estimate from Bayesian inference\. Therefore both the MDL and the MAP prediction rule select the hypothesis which maximizes the posterior probability of the hypothesis given the data:

arg​minH⁡L​\(H\)\+L⁡\(D\|H\)=arg​maxH⁡P​\(H\|D\)\\argmin\_\{H\}L\(H\)\+L\(D\|H\)=\\argmax\_\{H\}P\(H\|D\)\(2\)
Test samplexx, unknown classabababClass 1Class 2Step 1: build class modelsababababB1B\_\{1\}xyxyxyxyB2B\_\{2\}Step 2: compress each modelC⁡\(B1\)=10C\(B\_\{1\}\)=10BC⁡\(B2\)=10C\(B\_\{2\}\)=10BStep 3: appendxx, recompressC⁡\(B1​x\)=11C\(B\_\{1\}x\)=11BΔ1\\Delta\_\{1\}C⁡\(B2​x\)=16C\(B\_\{2\}x\)=16BΔ2\\Delta\_\{2\}Step 4: conditional code lengthΔ1=C⁡\(B1​x\)−C⁡\(B1\)=11−10=𝟏\\Delta\_\{1\}=C\(B\_\{1\}x\)\-C\(B\_\{1\}\)=11\-10=\{\\color\[rgb\]\{0\.1797,0\.5469,0\.3398\}\\mathbf\{1\}\}BΔ2=C⁡\(B2​x\)−C⁡\(B2\)=16−10=𝟔\\Delta\_\{2\}=C\(B\_\{2\}x\)\-C\(B\_\{2\}\)=16\-10=\{\\color\[rgb\]\{0\.707,0\.2344,0\.2344\}\\mathbf\{6\}\}By^=arg⁡mini⁡Δi\\hat\{y\}=\\arg\\min\_\{i\}\\Delta\_\{i\}: sinceΔ1=1≪6=Δ2\\Delta\_\{1\}=\{\\color\[rgb\]\{0\.1797,0\.5469,0\.3398\}1\}\\ll\{\\color\[rgb\]\{0\.707,0\.2344,0\.2344\}6\}=\\Delta\_\{2\}, predict Class 1\.

Fig\. 2:MDL classification \(compression as likelihood\)\. Two classes, each represented by a modelBiB\_\{i\}built from its training data, are compressed alone and then with the test samplexxappended\. The conditional code lengthΔi=C⁡\(Bi​x\)−C⁡\(Bi\)\\Delta\_\{i\}=C\(B\_\{i\}x\)\-C\(B\_\{i\}\)is the extra cost of encodingxxunder each model;xxis assigned to the class minimizing it\. Output block widths represent compressed sizes; the solid segment isΔi\\Delta\_\{i\}\.
### IV\-CWhen NCD and MDL coincide

Though a rigorous analysis of when a compression\-distance approach or an MDL approach is preferable remains an open challenge, we can make a simple but unifying observation: Both NCD and MDL ultimately rank candidates by how effectively a compressor can use side information to encode a test sample\. In NCD, this side information is another data sample, while in MDL it is a model\. Under a uniformity condition on the complexity of the side information, these two viewpoints induce the same ranking over candidates, allowing NCD to be interpreted as an MDL\-style conditional code length in which data points act as implicit models, and allowing MDL to be interpreted as selecting the model which minimizes its NCD to the test point under the same uniformity condition\. In particular, the context point minimizing the MDL objective also minimizes NCD\.

###### Proposition 1\.

LetΣ\\Sigmabe a set of symbols, letA:Σ∗×Σ∗→Σ∗A:\\Sigma^\{\*\}\\times\\Sigma^\{\*\}\\to\\Sigma^\{\*\}be an aggregation operation, letxxbe a fixed test sample, and let\{si\}\\\{s\_\{i\}\\\}be a set of context objects\. LetC⁡\(⋅\)C\(\\cdot\)denote compressed length under a fixed compressor\. AssumeC⁡\(si\)=LC\(s\_\{i\}\)=Lfor allii\(uniform compressed context length\)\. Then

arg⁡mini⁡\[C⁡\(A⁡\(si,x\)\)−C⁡\(si\)\]=arg⁡mini​NCD​\(si,x\)\.\\arg\\min\_\{i\}\[C\(A\(s\_\{i\},x\)\)\-C\(s\_\{i\}\)\]\\;=\\;\\arg\\min\_\{i\}\\text\{NCD\}\(s\_\{i\},x\)\.

###### Proof\.

The left hand side is equivalent toarg⁡mini⁡C⁡\(A⁡\(si,x\)\)\\arg\\min\_\{i\}C\(A\(s\_\{i\},x\)\)asC⁡\(si\)C\(s\_\{i\}\)is constant\. Expanding the right hand side,arg⁡mini​NCD​\(si,x\)=arg⁡mini​C⁡\(A⁡\(si,x\)\)−min⁡\{C⁡\(si\),C⁡\(x\)\}max⁡\{C⁡\(si\),C⁡\(x\)\}=arg⁡mini⁡C⁡\(A⁡\(si,x\)\)\\arg\\min\_\{i\}\\text\{NCD\}\(s\_\{i\},x\)=\\arg\\min\_\{i\}\\frac\{C\(A\(s\_\{i\},x\)\)\-\\min\\\{C\(s\_\{i\}\),C\(x\)\\\}\}\{\\max\\\{C\(s\_\{i\}\),C\(x\)\\\}\}=\\arg\\min\_\{i\}C\(A\(s\_\{i\},x\)\)asC⁡\(x\)C\(x\)is also constant\. ∎

WhenC⁡\(si\)C\(s\_\{i\}\)is not uniform, MDL and NCD differ in how they account for context complexity: MDL applies an explicit penalty, while NCD applies normalization\. We provide an illustration of how the MDL rule is used to classify a sample given per\-class compression models in Fig\.[2](https://arxiv.org/html/2609.21309#S4.F2)\.

### IV\-DWhen is compression\-based similarity meaningful?

As the theoretical justification for compression distance is an approximation to conditional Kolmogorov complexity, the mechanism and quality of a compressor affect the quality of the induced compression distance\. Below, we crystallize some previously informal considerations of the compression algorithm that affect NCD\.

Appropriate compressor for data:Clearly, the chosen compressor should be good at compressing the data at hand in order to define an effective distance\.

Window size:For the NCD to be meaningful, the compressor must be able to identify shared information across both sequences\. As traditional compressors tend to have a fixed\-size window \(for example,gzipusually operates with a 32KB sliding window\), the aggregated sequencex​yxyshould fit within this window\. NCD has been empirically shown to increase towards 1 when the sequence does not fit within the compressor’s window\[[52](https://arxiv.org/html/2609.21309#bib.bib52)\]\.

Effective compression ofx​yxy:NCD not only requires the compressor to be good at compressing individual samples, but it should also be good at compressing the aggregated sequencex​yxy\. The extent to which the compressor improves its ability to compressyywhen givenxx’s information is crucial to defining a meaningful NCD metric\. As a warning, in neural compression, LLMs compress text well but yield unpredictable results when performing NCD\-based classification, with a likely explanation that compressed concatenations result in out\-of\-distribution sequences, which worsens the model’s ability to identify semantic similarity\[[53](https://arxiv.org/html/2609.21309#bib.bib53),[54](https://arxiv.org/html/2609.21309#bib.bib54)\]\.

Given the superior compression ability of neural compressors, the natural question arises:do the improved compression ratios of neural compressors translate into improved predictive performance via compression distance?This is a new area of research, and there is much that is still unknown\. The first published work in the area of neural compressors for NCD\-based classification uses VAE neural compressors for few\-shot image classification\[[51](https://arxiv.org/html/2609.21309#bib.bib51)\], showing an improvement in accuracy over traditional compressors\. Another work applied LLMs to neural text compression for few\-shot text classification\[[53](https://arxiv.org/html/2609.21309#bib.bib53)\], presenting counterintuitive experimental evidence of a lack of correlation between compression ratio and NCD accuracy\. This is likely due to the different mechanism of theC⁡\(x​y\)C\(xy\)term when using neural compressors versus traditional compressors\. When using an LLM to compressx​yxy, shared information is successfully utilized if the probabilities assigned to the tokens inyyare higher than they would be when considered alone, as a result of having previously processed the tokens inxx\. There is much work yet to be done in the application of neural compressors to compression\-based ML\.

## VCompression\-Based Machine Learning

Having described the two paradigms of compression\-as\-similarity and compression\-as\-likelihood, we now formalize that much of the compression\-based ML literature can be understood as making a small number of design choices\. While methods differ in whether they rely on pairwise similarity or compression models, they share a common structure: a compressor induces code lengths, portions of training data are made available to the compressor as context, a scalar measure is derived from compressed lengths, and a prediction rule maps these quantities to outputs\. Our insight is that many prior works can be unified into a broader framework that characterizes these design choices which we describe as four factors: Compression algorithm, Context, Compression measure, and Prediction technique\. Examples of prior works encoded in this framework are given in Table[I](https://arxiv.org/html/2609.21309#S5.T1)\.

TABLE I:Papers in compression\-based ML and their settings under our framework\.We describe compression\-based ML in terms of four primary design choices: a compression algorithm inducing a compressed length functionCC, a contextSSderived from the training data which provides the compressor with side information, a compression measureMMdefined over code lengths, and a prediction techniquePP\. LetΣ\\Sigmabe a finite alphabet andΣ∗\\Sigma^\{\*\}the set of all finite strings overΣ\\Sigma\. Let the labeled training set be𝒯=\{\(zi,yi\)\}i=1N\\mathcal\{T\}=\\\{\(z\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{N\}withzi∈Σ∗,yi∈𝒴z\_\{i\}\\in\\Sigma^\{\*\},y\_\{i\}\\in\\mathcal\{Y\}\. For each classy∈𝒴y\\in\\mathcal\{Y\}, letDyD\_\{y\}denote its training data\. The design choices constituting this compression\-based ML framework are as follows\.

Compression algorithm \(CC\):Determines the length of compressed output and thus directly affects the induced distance or code length\. Given a particular compression algorithm, and optionally a class\-specific compression modelmm, we define a compressed\-length function:Cm:Σ∗→ℤC\_\{m\}:\\Sigma^\{\*\}\\to\\mathbb\{Z\}\.

Context \(SS\):The side information which is provided to the compressor prior to encoding a test sample and affects the output compressed length\. Depending on the method, context may take the form of another sample, an aggregation of multiple samples according to some aggregation operation, or an explicit learned compression model\. To cleanly separate the notions of the side information itself from how it is exposed to the compressor, we refer to the side information as the context source, while we refer to the mechanism by which this side information is exposed to the compressor as the context injection mechanism\.

For clarity, considerNCD​\(y,x\)\\text\{NCD\}\(y,x\)between a test samplexxand train sampleyy\. The context source isyy, while the context injection mechanism is the aggregation ofxxandyy, typically sequence concatenation, resulting in the compressor first compressing one then compressing the other with the benefit of whatever patterns the compressor has already discovered from the first sequence\. For MDL classification methods, the context is viewed as amodel\. This can either be anexplicitmodel constructed via an algorithm, or animplicitmodel which relies on the compressor’s state after compressing the contextual source data\. The context source is the learned compression model, while the context injection mechanism describes how the compressor uses that model to compress new data\.

Compression measure \(MM\):A scalar derived from compressed lengths that serves as the basis for prediction\. This may be a compression ratio, a normalized distance \(e\.g\. NCD, LZJD\), a conditional code length, or another code\-length\-based expression\. A compression measure mapsrrcompressed lengths to a scalar:M:ℤr→ℝM:\\mathbb\{Z\}^\{r\}\\to\\mathbb\{R\}\.

Prediction technique \(PP\):Maps compression measures to a prediction\. For distance\-based measures, this typically involveskk\-NN or clustering\. For code\-length\-based measures, prediction is typically made by selecting the class whose compression model best optimizes the compression measure\. Prediction mapsnnreal\-valued inputs to a label:P:ℝn→𝒴P:\\mathbb\{R\}^\{n\}\\to\\mathcal\{Y\}\.

CC: CompressorSS: ContextMM: MeasurePP: Predictiongzip,bzip2,LZMA,…zstandard \(dictionary\)PPM, DMCLZJD, BWMD\(extract representation\)VAE, LLM \+ entropy coding\(neural\)single sampleconcat / interleaveaggregatedclass dataper\-class learned modelcompression dictionary / compressor stateNCD, CDM, CosSLZJD distanceconditional code lengthC⁡\(Bi​x\)−C⁡\(Bi\)C\(B\_\{i\}x\)\{\-\}C\(B\_\{i\}\)Cmi​\(x\)C\_\{m\_\{i\}\}\(x\)kk\-NNclustering / treeMDLarg⁡min\\arg\\minuse compression ratio features with traditional ML techniquesCompression as similarity, e\.g\. NCD withkk\-NNCompression as likelihood, e\.g\. MDL classification

Fig\. 3:The compression\-based ML design space\. Every method in Table[I](https://arxiv.org/html/2609.21309#S5.T1)amounts to selecting one option per stage of the pipelineC→S→M→PC\\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\.We note an additional hyperparameter called compressors per class \(CPC\), utilized in\[[59](https://arxiv.org/html/2609.21309#bib.bib59)\], which partitions each class into a number of subsets via the aggregation operation\. The CPC is the number of subsets per class\. Each subset is now viewed as a single training sample, which is combined with the test point at prediction time\. When CPC is equal to the number of samples in the class, each original training sample is treated individually and the full pairwise compression distance matrix is computed between every train point and test point; the computational complexity of this isO⁡\(n2\)O\(n^\{2\}\)\. When CPC is11, each class becomes a single point by combining all of its constituent points via the aggregation operation\. This changes the computational complexity toO⁡\(n​\|𝒴\|\)O\(n\|\\mathcal\{Y\}\|\), a major improvement given a relatively small number of classes\|𝒴\|\|\\mathcal\{Y\}\|\. More generally, each class can be partitioned into an arbitrary number of subsets in order to facilitate chunking of class data\.

There are arguably two natural ways that one may attempt classification with compressors, and indeed some of the earliest works in compression\-based ML pursue either one or the other, with only one work that we are aware of explicitly comparing the two\[[42](https://arxiv.org/html/2609.21309#bib.bib42)\]\. The first way is to recognize that a pairwise compression distance matrix allows the use of distance\-based algorithms such askk\-nearest neighbors \(kk\-NN\) and clustering\. The second way is to obtain per\-class compression models and select the class of the model that best compresses a test point\. We thus argue that compression\-based ML approaches fall broadly into these two categories: compression\-distance\-based techniques\[[55](https://arxiv.org/html/2609.21309#bib.bib55),[44](https://arxiv.org/html/2609.21309#bib.bib44),[43](https://arxiv.org/html/2609.21309#bib.bib43),[7](https://arxiv.org/html/2609.21309#bib.bib7),[57](https://arxiv.org/html/2609.21309#bib.bib57),[48](https://arxiv.org/html/2609.21309#bib.bib48),[42](https://arxiv.org/html/2609.21309#bib.bib42),[49](https://arxiv.org/html/2609.21309#bib.bib49),[12](https://arxiv.org/html/2609.21309#bib.bib12),[9](https://arxiv.org/html/2609.21309#bib.bib9),[10](https://arxiv.org/html/2609.21309#bib.bib10),[46](https://arxiv.org/html/2609.21309#bib.bib46),[51](https://arxiv.org/html/2609.21309#bib.bib51),[40](https://arxiv.org/html/2609.21309#bib.bib40)\], which usually normalize compressed lengths to obtain a distance metric \(e\.g\. NCD\), though some instead derive distances from intermediate representations of the compressor\[[10](https://arxiv.org/html/2609.21309#bib.bib10),[46](https://arxiv.org/html/2609.21309#bib.bib46)\], and MDL\-inspired techniques\[[45](https://arxiv.org/html/2609.21309#bib.bib45),[56](https://arxiv.org/html/2609.21309#bib.bib56),[42](https://arxiv.org/html/2609.21309#bib.bib42),[59](https://arxiv.org/html/2609.21309#bib.bib59)\], which treat compressed lengths as code lengths and classify by selecting the class model yielding the shortest code length and thus assigning the maximum likelihood\. Both categories rely on compressor outputs, but differ in whether they interpret them as distances or as proxies for likelihood\.

### V\-ACompression\-distance\-based prediction

Given a compressor and classification task, one can perform compression\-based classification by computing the compression distance matrix between every pair of test points and train points, and using these distances forkk\-nearest neighbors\. Given a compressor,CCis the induced code length function, the contextSSis the second point injected typically via sequence concatenation, andMMis a chosen compression distance function such as NCD\. PredictionPPis then applied to the resulting distances \(e\.g\., viakk\-NN\)\. In compression\-distance\-based prediction, context injection is achieved by an aggregation operation that combines the test sample with the context sample:A:Σ∗×Σ∗→Σ∗A:\\Sigma^\{\*\}\\times\\Sigma^\{\*\}\\rightarrow\\Sigma^\{\*\}\. Throughout the NCD literature, aggregation is most often ordinary string concatenation\. The ultimate purpose ofAAis to integrate the information from two sequencesxxandyyin a manner which allows a good approximation of the information distance\.

For a test samplex∈Σ∗x\\in\\Sigma^\{\*\}, training samplez∈𝒯z\\in\\mathcal\{T\}, and an aggregation operationAA, our compression measureMMis the NCD\. For ease of reading, we introduce the short hand notation: letCx=C⁡\(x\)C\_\{x\}=C\(x\),Cz=C⁡\(z\)C\_\{z\}=C\(z\), andCz​x=C⁡\(A⁡\(z,x\)\)C\_\{zx\}=C\\\!\\big\(A\(z,x\)\\big\)\.

MNCD​\(Cx,Cz,Cz​x\)\\displaystyle M\_\{\\text\{NCD\}\}\(C\_\{x\},C\_\{z\},C\_\{zx\}\)=Cz​x−min⁡\{Cz,Cx\}max⁡\{Cz,Cx\}\.\\displaystyle=\\frac\{C\_\{zx\}\-\\min\\\{C\_\{z\},C\_\{x\}\\\}\}\{\\max\\\{C\_\{z\},C\_\{x\}\\\}\}\.Collecting over all training samples givesd⁡\(x\)=\(d⁡\(zi,x\)\)i=1N∈ℝN,d\(x\)=\\big\(d\(z\_\{i\},x\)\\big\)\_\{i=1\}^\{N\}\\in\\mathbb\{R\}^\{N\},and our predictiony^\\hat\{y\}is then given byy^=P⁡\(d⁡\(x\)\)\.\\hat\{y\}=P\(d\(x\)\)\.

As theC⁡\(x\)C\(x\)andC⁡\(y\)C\(y\)terms are reused across pairs, these can be precomputed in time linear in the number of samples \(in the case where the aggregation operation is string concatenation\)\. The complexity of the pairwise approach is dominated by the computation of the distance matrix, which requires𝒪⁡\(n2\)\\mathcal\{O\}\(n^\{2\}\)compressor calls\.

We note that in the context of sequential data compression and a string concatenation aggregation, there is redundant computation in the naive construction of the pairwise NCD matrix\. For allxxandyy, we must calculateC⁡\(x​y\)C\(xy\)\. For identicalxx, the state of the compressor after compressing thexxportion is identical no matter theyy\. For fast compressors and low data regimes, this may not be a hindrance\. However, where computational efficiency is a concern, an approach that is able to cachexx’s compression dictionary and initialize a compressor with it will work around this redundancy\.

Algorithm 1NCD\-KNN ClassificationPrecompute

C⁡\(yj\)C\(y\_\{j\}\)for all training samples

Precompute

C⁡\(xi\)C\(x\_\{i\}\)for all test samples

foreach test sample

xix\_\{i\}do

foreach training sample

yjy\_\{j\}do

Compute

C⁡\(xi​yj\)C\(x\_\{i\}y\_\{j\}\)
Compute NCD and store in distance matrix:

D​\[i\]​\[j\]=C⁡\(xi​yj\)−min⁡\(C⁡\(xi\),C⁡\(yj\)\)max⁡\(C⁡\(xi\),C⁡\(yj\)\)D\[i\]\[j\]=\\frac\{C\(x\_\{i\}y\_\{j\}\)\-\\min\(C\(x\_\{i\}\),C\(y\_\{j\}\)\)\}\{\\max\(C\(x\_\{i\}\),C\(y\_\{j\}\)\)\}
Apply

kk\-nearest neighbors using distance matrix

DD

Though it is most typical for the aggregation operation to be conventional string concatenation, aggregation generalizes any operation that combinesxxandyyinto a new representation\. In the image domain, pixel\-wise operations have been used to combine images for NCD\-basedkk\-NN classification\[[51](https://arxiv.org/html/2609.21309#bib.bib51)\]\. In malware detection on large files, interleaving/rearranging chunks of each file has been used to place the similar portions close to each other, allowing for more meaningful NCDs when simple concatenation would render the compressor’s sliding window too small to identify similarity across files\[[9](https://arxiv.org/html/2609.21309#bib.bib9)\]\. Another alternative to the high cost ofkk\-NN style NCD is to somehow “featurize” the result into a vector\.\[[11](https://arxiv.org/html/2609.21309#bib.bib11)\]used a randomly chosen reference set of exemplars from each class and created a feature vector for each sample by calculating the NCDs between the sample and each reference point\. In addition to the compression ratio, these features were used in decision trees and random forests for malware classification\.

Others have gone to a more direct path of vectorization\. Notice that a naive pairwise NCD matrix construction requires much redundant computation: for some fixed samplexx, the computationsC⁡\(x​y\)C\(xy\)are identical up to the moment they finish processingxx\. It would be more efficient to directly compare the compressor’s learned model for each sequence\. TheLempel\-Ziv Jaccard Distance\(LZJD\)\[[10](https://arxiv.org/html/2609.21309#bib.bib10)\]is an approach to mapping sequences to a smallersetrepresentation which can be directly compared via Jaccard similarity\. LZJD only implements the aspect of LZ compression which constructs the compression dictionariesAAandBBof two sequencesxxandyy, respectively, ignoring the extra steps involved in practical compression\. Here, a compression dictionary is a set of unique subsequences\. LZJD is defined as one minus the Jaccard similarity between the two sequences’ compression dictionaries:LZJD​\(x,y\)=1−\|A∩B\|\|A∪B\|\\textnormal\{LZJD\}\(x,y\)=1\-\\frac\{\|A\\cap B\|\}\{\|A\\cup B\|\}\[[10](https://arxiv.org/html/2609.21309#bib.bib10),[47](https://arxiv.org/html/2609.21309#bib.bib47)\]\. LZJD has been used in sequence classification, with particular success in malware classification involving long byte sequences\. Similarly, theBurrows Wheeler Transform Markov Distance\(BWMD\)\[[46](https://arxiv.org/html/2609.21309#bib.bib46)\]exploits the same idea of “extracting” the representation of the compressor to produce feature vectors, and instead applies the same trick to the Burrows Wheeler Transform \(or BWT, as used in thebzip2compression program\), which can be modeled as a Markov process since the BWT is meant to be used with run\-length encoding\.

### V\-BMDL\-inspired prediction with compression models

A compressor can be used to classify even without invoking a formal notion of distance\. Like NCD, approaches inspired by the Minimum Description Length principle have seen wide application to sequence prediction tasks such as text categorization\[[45](https://arxiv.org/html/2609.21309#bib.bib45),[56](https://arxiv.org/html/2609.21309#bib.bib56),[42](https://arxiv.org/html/2609.21309#bib.bib42),[41](https://arxiv.org/html/2609.21309#bib.bib41),[59](https://arxiv.org/html/2609.21309#bib.bib59)\]\. Imagine we have a classification problem with classesC1,…,CmC\_\{1\},\.\.\.,C\_\{m\}, along with a compressor\. Now consider, for each classCiC\_\{i\}, concatenating together all of its samples into a single sequenceBiB\_\{i\}\. With the intuition that popular dictionary\-based compression algorithms learn a model of the input as they compress, compressingBiB\_\{i\}will result in the compression program building a model unique to the data in that class\. Given a test pointxx, a simple classification scheme then is to compressBi​xB\_\{i\}xfor each class, and predict the class which minimizesC⁡\(Bi​x\)−C⁡\(Bi\)C\(B\_\{i\}x\)\-C\(B\_\{i\}\)\. This predicted class is the one that is most similar toxxaccording to the compressor’s model\. In other words, it is the class whose learned model best compressesxx\. For Lempel\-Ziv\-style compressors, similarity will be due to matching byte sequences\. We refer to this technique where class data and test data are aggregated and compressed together as implicit\-model MDL, as the compression model is built in an online fashion allowing the compressor to learn patterns within the class data prior to compressingxx\.

The procedure is as follows: given a test samplex∈Σ∗x\\in\\Sigma^\{\*\}, for each classii, construct the contextBiB\_\{i\}from that class’s training data by aggregating all \(or some subset\) of points from classiiaggregated according to a specified aggregation operation\. The compression measure is the conditional code lengthΔi​\(x\)=MMDL​\(C⁡\(Bi\),C⁡\(Bi​x\)\)=C⁡\(Bi​x\)−C⁡\(Bi\)\\Delta\_\{i\}\(x\)=M\_\{\\text\{MDL\}\}\\\!\\big\(C\(B\_\{i\}\),\\,C\(B\_\{i\}x\)\\big\)=C\(B\_\{i\}x\)\-C\(B\_\{i\}\)\. Prediction is then given byy^=arg⁡mini​Δi​\(x\)\\hat\{y\}=\\arg\\min\_\{i\}\\Delta\_\{i\}\(x\)\.

We give pseudocode for the implicit\-model MDL classification procedure in Algorithm[2](https://arxiv.org/html/2609.21309#alg2)\. The conditional code length is the compression cost of compressingxxwhen using the model learned from the class dataBiB\_\{i\}\. This approach treatsBiB\_\{i\}andxxnot as peer samples but as a class model and a sample, respectively\. This expression is rooted theoretically in conditional Kolmogorov complexity, approximatingK⁡\(x\|Bi\)K\(x\|B\_\{i\}\)\.

Algorithm 2Implicit\-Model MDL classificationAggregate all training samples in each class into

BjB\_\{j\}
Precompute

C⁡\(Bj\)C\(B\_\{j\}\)for each class

jj
foreach test sample

xix\_\{i\}do

foreach class

jjdo

Compute

Δi​j←C⁡\(Bj​xi\)−C⁡\(Bj\)\\Delta\_\{ij\}\\leftarrow C\(B\_\{j\}x\_\{i\}\)\-C\(B\_\{j\}\)
Predict

y^i←arg⁡minj⁡Δi​j\\hat\{y\}\_\{i\}\\leftarrow\\arg\\min\_\{j\}\\Delta\_\{ij\}

Some compressors allow the explicit construction/initialization of compression models \(e\.g\. dictionaries\), which allow for an MDL\-inspired classification technique which is able to cache the compression models, avoiding costly recomputation upon each new inference\. For example, thezstandard\[[60](https://arxiv.org/html/2609.21309#bib.bib60)\]compression algorithm allows for the explicit construction of compression dictionaries\. Here, the classification procedure is to assign the class whose compression model best compresses a test point\. We refer to this technique where a compression model is trained prior to inference as explicit\-model MDL\. In this case, the conditional code length is simply the compressed length when using the class\-specific model and we denote this lengthΔ∗\\Delta^\{\*\}:Δi⋆​\(x\)=MMDL​\(Cmi​\(x\)\)=Cmi​\(x\)\.\\Delta^\{\\star\}\_\{i\}\(x\)=M\_\{\\text\{MDL\}\}\\\!\\big\(C\_\{m\_\{i\}\}\(x\)\\big\)=C\_\{m\_\{i\}\}\(x\)\.We provide pseudocode for the explicit\-model MDL classification procedure in Algorithm[3](https://arxiv.org/html/2609.21309#alg3)\.

Algorithm 3Explicit\-Model MDL ClassificationGiven:

DiD\_\{i\}, the training data for class

ii
For each class

ii, build a class\-specific model

mim\_\{i\}from

DiD\_\{i\}
foreach test sample

xxdo

foreach class

iido

Δi⋆​\(x\)←Cmi​\(x\)\\Delta^\{\\star\}\_\{i\}\(x\)\\leftarrow C\_\{m\_\{i\}\}\(x\)

Predict

y^​\(x\)←arg⁡mini​Δi⋆​\(x\)\\hat\{y\}\(x\)\\leftarrow\\arg\\min\_\{i\}\\Delta^\{\\star\}\_\{i\}\(x\)

We compare runtime complexity of the approaches we have highlighted with respect to the number of compressor calls in Table[II](https://arxiv.org/html/2609.21309#S5.T2)\.

TABLE II:Computational cost of compression\-based ML approaches;nnis 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\.
### V\-CExperimental Results

We run a small set of representative experiments to both highlight the competitiveness of compression\-based prediction methods and to show the high performance variability when selecting the\(C,S,M,P\)\(C,S,M,P\)design choices of our compression\-based ML framework\. We choose one dataset per domain: text \(AGNews\[[61](https://arxiv.org/html/2609.21309#bib.bib61)\]\), malware \(Drebin\[[62](https://arxiv.org/html/2609.21309#bib.bib62)\]\), and images \(MNIST\[[63](https://arxiv.org/html/2609.21309#bib.bib63)\]\), and sweep across compression programs, context size, compression measure, aggregation operation, and prediction technique, organized around a standard NCD reference technique:gzipwith NCD and11\-NN, one context object per training sample, and string concatenation as the aggregation operation\. For compressors, we usegzip,bzip2,LZMA, andzstandardat their default settings, and additionally runzstandardat compression level 15 \(default is 3\) to separate compression effort from choice of program\. For compression measures we use NCD, CDM, CLM and CosS, together with the conditional code length, and forPPwe usekk\-NN withk∈\{1,3,5\}k\\in\\\{1,3,5\\\}, average distance to each class, and the MDL argmin rule\. We report accuracy in both few\-shot and full dataset settings, though due to the computational complexity of NCD, we only run it up to 1,000 training samples\. Few\-shot results are averaged over ten seeds and then=103n\{=\}10^\{3\}setting over three seeds where each seed redraws the training samples, the evaluation subset, and for Drebin, the 90/10 train/test split\. We evaluate on300300test samples for AG News and MNIST and100100for Drebin, except in the full\-corpus setting which uses the complete test sets\. EachΔ\\Deltais a difference of seed\-averaged accuracies for a single fixed configuration on each side; its standard error across seeds is at most0\.0240\.024in every setting\. NCD/MDL are compared on identical splits against conventional baselines: logistic regression, a linear SVM, and 1\-NN over TF\-IDF word 1–2\-grams \(text\), hashed byte 4\-grams \(malware\), and raw pixels \(images\)\. For text and malware, compression methods use string concatenation for aggregation\. For MNIST, aggregation sweeps across string concatenation and pixel\-wise addition as in\[[64](https://arxiv.org/html/2609.21309#bib.bib64)\]\. To illustrate the variability of compression\-based performance when sweeping across design choices, we show the accuracy span per choice in Figure[4](https://arxiv.org/html/2609.21309#S5.F4)\.

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\.We report our results in Table[III](https://arxiv.org/html/2609.21309#S5.T3)\. NCD and MDL perform competitively in the few\-shot setting, especially outperforming the baselines in few\-shot malware classification, by as much as 0\.27 points, indicating the high learning signal present in compression\-based methods even with only a few samples\. Takinggzipwith NCD and11\-NN as the reference configuration\[[40](https://arxiv.org/html/2609.21309#bib.bib40)\], the best configuration at the same training budget gains0\.0130\.013on Drebin,0\.1700\.170on AG News and0\.6190\.619on MNIST\. Raisingzstandardfrom level 3 to 15 improves accuracy in 82 of 110 configurations, by0\.0160\.016on average\. Overall, MDL requires far fewer compressor calls than NCD while often also obtaining higher accuracy in the text and malware domains\. Importantly, the image domain indicates the crucial role of aggregation, as aggregating via byte string concatenation does not aid in compression resulting in degenerate performance\. However, modifying the aggregation operation to pixel\-wise addition aids in compression of multiple samples and results in a non\-trivial MNIST accuracy of up to 0\.88 and competitive few\-shot learning accuracies\. NCD is not run on full MNIST due to computational constraints; at that scale, only MDL is affordable, however in the image domain a compression dictionary built from thousands of aggregated digits does not capture the class better than a single sample does\. We therefore stress that a domain\-aware aggregation operation is an important design choice worth considering\.

TABLE III:Compression\-based classification against standard feature\-based classifiers in both few\-shot and full dataset setting\.comp\.andbase\.report their best configurations\.methodreports winning compression\-based method\. NCD not run in full dataset setting\. Timings are single\-threaded on an Apple M1 Max \(10\-core, 64 GB\)\.From our experimental results we conclude that compression\-based ML essentially begs a hyperparameter optimization step across choice of compressor, compression measure, aggregator, and prediction technique, and there are immediate gains to be had over the conventionalgzip\+kk\-NN configuration popularized in\[[40](https://arxiv.org/html/2609.21309#bib.bib40)\]\. NCD/MDL are especially competitive in the malware setting, where strong featurization techniques are lacking and Lempel\-Ziv compression mechanisms essentially provide automatic feature extraction at variable\-length n\-grams\.

## VIOpen Questions and Challenges

The hypothesis that better compression yields better prediction is soundly supported when considering theoretically optimal compressors such as Kolmogorov complexity, but requires further empirical and theoretical justification when considering practical compressors\. The success of machine learning in improving data compression is a strong signal that learned compressors may provide novel and useful avenues in solving sequential ML tasks via compression\-based approaches\. State of the art approaches for lossless text compression, for example via the Large Text Compression Benchmark\[[24](https://arxiv.org/html/2609.21309#bib.bib24)\], are neural methods such as NNCP\[[25](https://arxiv.org/html/2609.21309#bib.bib25)\]and CMIX\[[26](https://arxiv.org/html/2609.21309#bib.bib26)\]\. And popular pre\-trained large language models themselves can be used for lossless compression\[[31](https://arxiv.org/html/2609.21309#bib.bib31)\]\. Some initial work has been done in studying the effects of using neural compressors for compression\-based ML\[[54](https://arxiv.org/html/2609.21309#bib.bib54),[51](https://arxiv.org/html/2609.21309#bib.bib51)\], however further study is warranted, especially as neural compressors, despite achieving superior compression, are currently much slower, hindering a larger scale study of their potential for compression\-based prediction\. Our framework separates the choice of compressor from its context mechanism, and our experiments show that simply modifying the aggregation operation moves MNIST accuracy from0\.270\.27to0\.850\.85\. In the neural compression setting, further study of alternative aggregation methods for NCD & MDL is a promising avenue for realizing improvements, as was previously demonstrated in the malware domain\[[9](https://arxiv.org/html/2609.21309#bib.bib9)\]\.

Techniques like LZJD and BWMD learn compressed representations of sequences for the goal of achieving good similarity scores, without the overhead required for decompression\. One area of future work is to continue to improve or invent new compressed representations with the end goal of machine learning in mind, to improve accuracy, runtime, and memory use\.

Further, improvements in lossless compression itself have long been hypothesized to yield insights in artificial intelligence, as was the impetus for the Hutter Prize\[[37](https://arxiv.org/html/2609.21309#bib.bib37)\]and Mahoney’s Large Text Compression Benchmark, and therefore remain an important target\.

## VIIConclusion

Despite machine learning having produced new state\-of\-the\-art in compression, and compression having been used for machine learning, the intersection of these two has yet to be fully understood\. By formalizing compression\-based ML into four key design choices, we find that the literature presents a refreshingly different approach to AI problems, still leaving a wide array of challenges to explore\.

## References

- \[1\]M\. V\. Mahoney, “Text compression as a test for artificial intelligence,” in*Proceedings of the AAAI\-99 Workshop on AI and Data Compression, Learning, and Information Retrieval*\. AAAI Press, 1999, copyright © 1999, AAAI \(www\.aaai\.org\)\.
- \[2\]D\. J\. C\. MacKay,*Information Theory, Inference and Learning Algorithms*\. Cambridge, UK: Cambridge University Press, 2003\.
- \[3\]M\. Nelson and J\.\-L\. Gailly,*The data compression book \(2nd ed\.\)*\. USA: MIS:Press, 1995\.
- \[4\]A\. N\. Kolmogorov, “On tables of random numbers,” in*Proceedings of the Symposium on the Theory of Numbers*, 1963, pp\. 369–376\.
- \[5\]C\. H\. Bennett, P\. Gács, M\. Li, P\. M\. B\. Vitányi, and W\. H\. Zurek, “Information distance,”*IEEE Transactions on Information Theory*, vol\. 44, no\. 4, pp\. 1407–1423, 1998\. \[Online\]\. Available:https://cs\.uwaterloo\.ca/~mli/informationdistance\.pdf
- \[6\]P\. M\. B\. Vitanyi, F\. J\. Balbach, R\. L\. Cilibrasi, and M\. Li, “Normalized information distance,” 2008\. \[Online\]\. Available:https://arxiv\.org/abs/0809\.2553
- \[7\]M\. Li, X\. Chen, X\. Li, B\. Ma, and P\. M\. Vitányi, “The similarity metric,”*IEEE Transactions on Information Theory*, vol\. 50, no\. 12, pp\. 3250–3264, 2004\.
- \[8\]J\. Rissanen, “Modeling by shortest data description,”*Automatica*, vol\. 14, no\. 5, pp\. 465–471, 1978\. \[Online\]\. Available:https://www\.sciencedirect\.com/science/article/pii/0005109878900055
- \[9\]R\. S\. Borbely, “On normalized compression distance and large malware,” 2015\. \[Online\]\. Available:https://arxiv\.org/abs/1509\.00689
- \[10\]E\. Raff and C\. Nicholas, “An alternative to ncd for large sequences, lempel\-ziv jaccard distance,” in*Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, ser\. KDD ’17\. New York, NY, USA: ACM, 2017, pp\. 1007–1015\. \[Online\]\. Available:http://doi\.acm\.org/10\.1145/3097983\.3098111
- \[11\]N\. Alshahwan, E\. T\. Barr, D\. Clark, and G\. Danezis, “Detecting malware with information complexity,” 2015\. \[Online\]\. Available:https://arxiv\.org/abs/1502\.07661
- \[12\]S\. Wehner, “Analyzing worms and network traffic using compression,”*J\. Comput\. Secur\.*, vol\. 15, pp\. 303–320, 2005\. \[Online\]\. Available:https://api\.semanticscholar\.org/CorpusID:13391901
- \[13\]E\. Raff and C\. Nicholas, “A Survey of Machine Learning Methods and Challenges for Windows Malware Classification,” in*NeurIPS 2020 Workshop: ML Retrospectives, Surveys & Meta\-Analyses \(ML\-RSA\)*, 2020, arXiv: 2006\.09271\. \[Online\]\. Available:http://arxiv\.org/abs/2006\.09271
- \[14\]E\. Raff, M\. Ashkenazi, S\. Samtani, D\. J\. Elkind, and S\. Krasser, “Cybersecurity is the True Frontier for Generative AI Success or Failure,” in*2026 IEEE European Symposium on Security and Privacy Workshops \(EuroS&PW\)*, Jul\. 2026, pp\. 242–252, iSSN: 2768\-0657\. \[Online\]\. Available:https://ieeexplore\.ieee\.org/document/11632077/authors
- \[15\]L\. P\. Deutsch, “DEFLATE Compressed Data Format Specification version 1\.3,” RFC 1951, May 1996\. \[Online\]\. Available:https://www\.rfc\-editor\.org/info/rfc1951
- \[16\]T\. Cover and J\. Thomas,*Elements of Information Theory*, 2nd ed\. Wiley, 2009\.
- \[17\]J\. Ziv and A\. Lempel, “A universal algorithm for sequential data compression,”*IEEE Transactions on Information Theory*, vol\. 23, no\. 3, pp\. 337–343, May 1977\.
- \[18\]——, “Compression of individual sequences via variable\-rate coding,”*IEEE Transactions on Information Theory*, vol\. 24, no\. 5, pp\. 530–536, 1978\.
- \[19\]M\. Mahoney, “Data compression explained,” 2013\. \[Online\]\. Available:http://mattmahoney\.net/dc/dce\.html
- \[20\]C\. E\. Shannon, “A mathematical theory of communication,”*Bell System Technical Journal*, vol\. 27, pp\. 379–423, 1948\.
- \[21\]D\. A\. Huffman, “A method for the construction of minimum\-redundancy codes,”*Proceedings of the Institute of Radio Engineers*, vol\. 40, no\. 9, pp\. 1098–1101, September 1952\.
- \[22\]I\. H\. Witten, R\. M\. Neal, and J\. G\. Cleary, “Arithmetic coding for data compression,”*Commun\. ACM*, vol\. 30, no\. 6, p\. 520–540, jun 1987\. \[Online\]\. Available:https://doi\.org/10\.1145/214762\.214771
- \[23\]M\. Li and P\. M\. B\. Vitányi,*An Introduction to Kolmogorov Complexity and Its Applications*, 3rd ed\. New York, NY: Springer, 2008\. \[Online\]\. Available:https://link\.springer\.com/book/10\.1007/978\-0\-387\-49820\-1
- \[24\]M\. Mahoney, “Large text compression benchmark,”https://www\.mattmahoney\.net/dc/text\.html, 2024\.
- \[25\]F\. Bellard, “Nncp v2: Lossless data compression with transformer,”https://bellard\.org/nncp/nncp\_v2\.1\.pdf, 2021\.
- \[26\]B\. Knoll, “CMIX version 21,”http://www\.byronknoll\.com/cmix\.html, 2024\.
- \[27\]F\. Mentzer, E\. Agustsson, M\. Tschannen, R\. Timofte, and L\. V\. Gool, “Practical full resolution learned lossless image compression,” 2020\. \[Online\]\. Available:https://arxiv\.org/abs/1811\.12817
- \[28\]D\. Li, Y\. Bai, K\. Wang, J\. Jiang, X\. Liu, and W\. Gao, “Callic: Content adaptive learning for lossless image compression,” 2024\. \[Online\]\. Available:https://arxiv\.org/abs/2412\.17464
- \[29\]comma\.ai, “commaVQ: A dataset of 100,000 minutes of driving video compressed using a vq\-vae\.”https://github\.com/commaai/commavq, 2024, leaderboard athttps://comma\.ai/leaderboard\. Accessed: 2026\-09\-05\.
- \[30\]Y\. Yang, S\. Mandt, and L\. Theis, “An introduction to neural data compression,” 2023\. \[Online\]\. Available:https://arxiv\.org/abs/2202\.06533
- \[31\]G\. Delétang, A\. Ruoss, P\.\-A\. Duquenne, E\. Catt, T\. Genewein, C\. Mattern, J\. Grau\-Moya, L\. K\. Wenliang, M\. Aitchison, L\. Orseau, M\. Hutter, and J\. Veness, “Language modeling is compression,” 2024\. \[Online\]\. Available:https://arxiv\.org/abs/2309\.10668
- \[32\]C\. S\. K\. Valmeekam, K\. Narayanan, D\. Kalathil, J\.\-F\. Chamberland, and S\. Shakkottai, “Llmzip: Lossless text compression using large language models,” 2023\. \[Online\]\. Available:https://arxiv\.org/abs/2306\.04050
- \[33\]M\. Goyal, K\. Tatwawadi, S\. Chandak, and I\. Ochoa, “Dzip: improved general\-purpose lossless compression based on novel neural network modeling,” 2020\. \[Online\]\. Available:https://arxiv\.org/abs/1911\.03572
- \[34\]A\. van den Oord, N\. Kalchbrenner, O\. Vinyals, L\. Espeholt, A\. Graves, and K\. Kavukcuoglu, “Conditional image generation with pixelcnn decoders,” 2016\. \[Online\]\. Available:https://arxiv\.org/abs/1606\.05328
- \[35\]C\. S\. Wallace, “Classification by minimum\-message\-length inference,” in*Proceedings of the International Conference on Advances in Computing and Information \(ICCI\)*, 1990, pp\. 72–81\.
- \[36\]B\. Frey and G\. Hinton, “Free energy coding,” in*Proceedings of the Data Compression Conference*, 1996\.
- \[37\]M\. Hutter, “Human knowledge compression prize,” 2006/2020, open ended, http://prize\.hutter1\.net/\.
- \[38\]A\. van den Oord, O\. Vinyals, and K\. Kavukcuoglu, “Neural discrete representation learning,” 2018\. \[Online\]\. Available:https://arxiv\.org/abs/1711\.00937
- \[39\]L\. Wan, T\. Alpcan, M\. Kuijper, and E\. Viterbo, “Lightweight conceptual dictionary learning for text classification using information compression,”*IEEE Transactions on Knowledge and Data Engineering*, vol\. 36, no\. 12, pp\. 8711–8717, 2024\.
- \[40\]Z\. Jiang, M\. Yang, M\. Tsirlin, R\. Tang, Y\. Dai, and J\. Lin, ““low\-resource” text classification: A parameter\-free classification method with compressors,” in*Findings of the Association for Computational Linguistics: ACL 2023*, A\. Rogers, J\. Boyd\-Graber, and N\. Okazaki, Eds\. Toronto, Canada: Association for Computational Linguistics, Jul\. 2023, pp\. 6810–6828\. \[Online\]\. Available:https://aclanthology\.org/2023\.findings\-acl\.426
- \[41\]A\. Bratko, G\. V\. Cormack, B\. Filipič, T\. R\. Lynam, and B\. Zupan, “Spam filtering using statistical data compression models,”*Journal of Machine Learning Research*, vol\. 7, pp\. 2673–2698, 2006\.
- \[42\]Y\. Marton, N\. Wu, and L\. Hellerstein, “On compression\-based text classification,” in*Advances in Information Retrieval*, ser\. Lecture Notes in Computer Science, D\. E\. Losada and J\. M\. Fernández\-Luna, Eds\. Springer, Berlin, Heidelberg, 2005, vol\. 3408, pp\. 300–314\. \[Online\]\. Available:https://doi\.org/10\.1007/978\-3\-540\-31865\-1\_22
- \[43\]R\. Cilibrasi and P\. M\. Vitányi, “Clustering by compression,”*IEEE Transactions on Information Theory*, vol\. 51, no\. 4, pp\. 1523–1545, 2005\.
- \[44\]D\. Benedetto, E\. Caglioti, and V\. Loreto, “Language trees and zipping,”*Physical Review Letters*, vol\. 88, no\. 4, Jan\. 2002\. \[Online\]\. Available:http://dx\.doi\.org/10\.1103/PhysRevLett\.88\.048702
- \[45\]E\. Frank, C\. Chui, and I\. H\. Witten, “Text categorization using compression models,” in*Proceedings of the Conference on Data Compression*, ser\. DCC ’00\. USA: IEEE Computer Society, 2000, p\. 555\.
- \[46\]E\. Raff, C\. Nicholas, and M\. McLean, “A new burrows wheeler transform markov distance,” in*Proceedings of the Thirty\-Fourth AAAI Conference on Artificial Intelligence \(AAAI\-20\)*, 2020, pp\. 5444–5453\.
- \[47\]E\. Raff and C\. K\. Nicholas, “Malware classification and class imbalance via stochastic hashed lzjd,”*Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security*, 2017\. \[Online\]\. Available:https://api\.semanticscholar\.org/CorpusID:32707746
- \[48\]E\. Keogh, S\. Lonardi, and C\. A\. Ratanamahatana, “Towards parameter\-free data mining,” in*Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, ser\. KDD ’04\. New York, NY, USA: Association for Computing Machinery, 2004, p\. 206–215\. \[Online\]\. Available:https://doi\.org/10\.1145/1014052\.1014077
- \[49\]E\. Keogh, S\. Lonardi, C\. A\. Ratanamahatana, L\. Wei, S\.\-H\. Lee, and J\. Handley, “Compression\-based data mining of sequential data,”*Data Min\. Knowl\. Discov\.*, vol\. 14, no\. 1, p\. 99–129, Feb\. 2007\. \[Online\]\. Available:https://doi\.org/10\.1007/s10618\-006\-0049\-3
- \[50\]D\. Sculley and C\. Brodley, “Compression and machine learning: a new perspective on feature space vectors,” in*Data Compression Conference \(DCC’06\)*, 2006, pp\. 332–341\.
- \[51\]Z\. Jiang, Y\. Dai, J\. Xin, M\. Li, and J\. Lin, “Few\-Shot Non\-Parametric Learning with Deep Latent Variable Model,” in*Advances in Neural Information Processing Systems*, S\. Koyejo, S\. Mohamed, A\. Agarwal, D\. Belgrave, K\. Cho, and A\. Oh, Eds\., vol\. 35\. Curran Associates, Inc\., 2022, pp\. 26 448–26 461\. \[Online\]\. Available:https://proceedings\.neurips\.cc/paper\_files/paper/2022/file/a92519f525c00085095fa41c5c46cdb5\-Paper\-Conference\.pdf
- \[52\]M\. Cebrián, M\. Alfonseca, and A\. Ortega, “Common pitfalls using the normalized compression distance: What to watch out for in a compressor,”*Communications in Information and Systems*, vol\. 5, no\. 4, pp\. 367–384, 2005\.
- \[53\]J\. Hurwitz, C\. Nicholas, and E\. Raff, “Neural normalized compression distance and the disconnect between compression and classification,” 2024, presented at the NeurIPS 2024 Workshop on Machine Learning and Compression\. \[Online\]\. Available:https://arxiv\.org/abs/2410\.15280
- \[54\]——, “Large language models and normalized compression distance: Better compression yet worse accuracy,” in*Frontiers in Artificial Intelligence and Applications, Volume 413: ECAI 2025*\. IOS Press, 2025, pp\. 4273–4280\.
- \[55\]M\. Li, J\. H\. Badger, X\. Chen, S\. Kwong, P\. Kearney, and H\. Zhang, “An information\-based sequence distance and its application to whole mitochondrial genome phylogeny,”*Bioinformatics*, vol\. 17, no\. 2, pp\. 149–154, 02 2001\.
- \[56\]W\. J\. Teahan and D\. J\. Harper, “Using compression\-based language models for text categorization,” in*Proceedings of the Workshop on Language Modeling and Information Retrieval*, 2001\.
- \[57\]X\. Chen, B\. Francia, M\. Li, B\. McKinnon, and A\. Seker, “Shared information and program plagiarism detection,” vol\. 50, no\. 7, pp\. 1545–1551, 2004\. \[Online\]\. Available:http://ieeexplore\.ieee\.org/document/1306552/
- \[58\]N\. Kasturi and I\. L\. Markov, “Text ranking and classification using data compression,”*CoRR*, vol\. abs/2109\.11577, 2021\. \[Online\]\. Available:https://arxiv\.org/abs/2109\.11577
- \[59\]C\. de Catheu, “FTCC: Fast text classification with compressors dictionary,”https://github\.com/cyrilou242/ftcc, 2023, accessed: 2025\-08\-19\.
- \[60\]Y\. Collet and M\. Kucherawy, “Zstandard Compression and the ’application/zstd’ Media Type,” RFC 8878, Feb\. 2021\. \[Online\]\. Available:https://www\.rfc\-editor\.org/info/rfc8878
- \[61\]X\. Zhang, J\. J\. Zhao, and Y\. LeCun, “Character\-level convolutional networks for text classification,” in*Advances in Neural Information Processing Systems 28 \(NeurIPS 2015\)*, C\. Cortes, N\. D\. Lawrence, D\. D\. Lee, M\. Sugiyama, and R\. Garnett, Eds\., Montreal, Quebec, Canada, December 7–12 2015, pp\. 649–657\. \[Online\]\. Available:https://proceedings\.neurips\.cc/paper/2015/hash/250cf8b51c773f3f8dc8b4be867a9a02\-Abstract\.html
- \[62\]D\. Arp, M\. Spreitzenbarth, M\. Hübner, H\. Gascon, and K\. Rieck, “Drebin: Effective and explainable detection of android malware in your pocket,” in*Proceedings of the Network and Distributed System Security Symposium \(NDSS\)*\. Internet Society, 2014\.
- \[63\]L\. Deng, “The MNIST database of handwritten digit images for machine learning research,”*IEEE Signal Processing Magazine*, vol\. 29, no\. 6, pp\. 141–142, 2012\.
- \[64\]J\. Serlier, “Solving MNIST with gzip,”https://jakobs\.dev/solving\-mnist\-with\-gzip/, 2023, accessed: 2026\-09\-05\.