In 2023, a paper titled "Low-Resource" Text Classification: A Parameter-Free Classification Method with Compressors by Zhiying Jiang, Jimmy Lin, and colleagues caused a stir in the NLP community. They showed that a simple combination of gzip and a k-nearest-neighbor (kNN) classifier could outperform heavyweights like BERT on several benchmarks.
This wasn't a fluke. It was the latest application of a deep idea from information theory: that the best way to measure the similarity between two things is to see how well they compress together.
Compression is Pattern Discovery
To understand why this works, we have to rethink what a compressor like gzip actually does. A compressor's job is to find patterns. If it sees the word "transformer" repeated ten times, it doesn't store the word ten times; it stores it once and then records pointers to that first instance.
As Marcus Hutter explains in his guide to Algorithmic Information Theory, this is a practical approximation of Kolmogorov Complexity—the length of the shortest possible program that can produce a specific piece of data. While true Kolmogorov complexity is mathematically uncomputable, standard compression algorithms serve as a "good enough" proxy for identifying the structural regularity within data.
The Intuition of Joint Compression
The core mechanism used across these papers is the Normalized Compression Distance (NCD). The intuition is elegant:
- Compress object $A$ and measure its size: $C(A)$.
- Compress object $B$ and measure its size: $C(B)$.
- Concatenate $A$ and $B$ into one file and compress it: $C(AB)$.
If $A$ and $B$ are completely unrelated (e.g., a weather report and a snippet of C++ code), the compressor won't find any shared patterns. The size of the combined file $C(AB)$ will be roughly the sum of the individual parts: $C(A) + C(B)$.
However, if $A$ and $B$ are similar (e.g., two news articles about the same earthquake), the patterns found in $A$ will help the compressor represent $B$ more efficiently. In this case, $C(AB)$ will be significantly smaller than $C(A) + C(B)$.
This "compression gain" is a direct measure of the mutual information shared between the two objects. As Zhiying Jiang and Raphael Tang argue in Less is More, this allows for classification without any training, tokenization, or manual feature engineering.
A Universal, Feature-Blind Metric
Because compressors operate on raw bytes, this approach is "feature-blind." It doesn't care if it's looking at text, DNA, or seismic waves. This universality allows researchers to apply the same logic to wildly different fields:
- Phylogenetics: Researchers used Lempel-Ziv compression to build evolutionary trees by measuring the "directional information content" between protein sequences, bypassing the need for traditional sequence alignment.
- Seismic Monitoring: R. A. Field and Christina Ting developed Sliding Information Distance (SLID) to detect seismic events. By measuring the information distance between sliding windows of data, they can identify arrivals of seismic waves without a complex physical model of the earth.
- Computer Vision: Dongha Lee and Hwanjo Yu applied this to Out-of-Distribution (OOD) detection. They found that if a neural network's feature map for a new image can be efficiently compressed using patterns from the training data, the image is likely "in-distribution."
- Authorship and Spam: By looking for "compression signatures," researchers like Einat Amitay can link split identities of web authors, while Kyumin Lee uses it to catch Twitter spammers who post repetitive, highly compressible content.
Why It Works When Deep Learning Fails
Deep learning models are powerful but brittle. They rely on specific vocabularies and can struggle with "out-of-distribution" data—text in a language or domain they haven't seen before.
Compression-based methods are inherently robust to these shifts. As L. Venkata Subramaniam demonstrated in event detection for Twitter streams, compression metrics handle informal language, slang, and typos naturally because they look at byte-level statistical regularities rather than fixed dictionary definitions.
Furthermore, these methods are "parameter-free." There are no weights to update and no hyperparameters to tune. In IberLEF 2024, Michael Ibrahim used this approach to place 3rd in a Spanish hope speech detection challenge, proving that "low-tech" methods remain competitive even in the age of Large Language Models.
The Limits of the Analogy
While the intuition is powerful, the relationship between compression and intelligence is nuanced. John Hurwitz and Edward Raff recently explored the disconnect between compression and classification. They found that while LLMs can be turned into incredible compressors (using arithmetic coding), a better compression ratio doesn't always translate to better classification accuracy.
This suggests that while compression captures "regularity," classification often requires "relevance"—the ability to distinguish which patterns matter for a specific task and which are just noise. Nevertheless, as a domain-agnostic, parameter-free baseline, joint compression remains one of the most versatile tools in the researcher's kit.