A paper submitted to arXiv on September 18 presents a framework for building machine learning classifiers directly from lossless compression algorithms. The core idea is older than modern deep learning, but the authors argue it has been underexploited. Their results show compression-based methods matching conventional baselines on standard tasks and outperforming them on malware detection.
The compression-classification connection
The relationship works in both directions. Any lossless compression algorithm, including simple tools like gzip, can become a classifier through Normalized Compression Distance or the Minimum Description Length principle. Normalized Compression Distance measures similarity between two strings by compressing them individually and together, then comparing the compressed sizes. Minimum Description Length treats the best model as the one that minimizes the total length needed to describe both the model and the data.
The reverse also holds. Any auto-regressive model, including large language models, can be converted into a lossless compressor through entropy coding. The model assigns probabilities to tokens, and those probabilities feed into an entropy coder like arithmetic coding to produce a compressed representation.
The authors describe this as a circular dependence. Compression produces classifiers. Classifiers produce compression. Both directions have been used separately, but the paper formalizes them together and introduces a design framework for choosing between them.
Empirical results
The framework was tested across standard classification benchmarks. Compression-based methods matched conventional baselines on general tasks. On malware detection, they performed decisively better. The authors attribute this to the nature of malware: binary executables and packed files have statistical properties that compression algorithms capture naturally, while traditional feature engineering struggles with the irregular structure.
Varying design choices within the framework, such as which compressor to use, how to handle preprocessing, and how to structure the distance calculations, produced accuracy gains of up to 0.62 on certain benchmarks. That range suggests the framework is not a single method but a family of approaches where the right configuration matters.
Why this matters now
The paper arrives at a moment when machine learning is dominated by large neural networks that require substantial compute for both training and inference. Compression-based classifiers run in milliseconds on a laptop. They need no GPU, no training loop, no labeled dataset beyond what the distance calculation requires. For applications where interpretability and speed matter more than squeezing out the last fraction of accuracy, this is a practical alternative.
Malware detection is the clearest case. Antivirus systems need to classify files quickly, handle adversarial inputs, and operate on machines with limited resources. A gzip-based classifier that outperforms a neural network on that task is not a curiosity. It is a tool that could ship in production.
The broader point is that the field may have spent two decades building increasingly complex models for tasks where simpler statistical methods, properly configured, already work. The framework gives practitioners a way to evaluate that tradeoff systematically rather than assuming neural networks are always the right choice.