Can gzip and K-nearest neighbors actually beat BERT at text classification? That was the bold claim of a research paper titled "Low-Resource Text Classification: A Parameter-Free Classification Method with Compressors" — and it sent the ML community into a frenzy. The short answer: not quite, but what it can do in 25 lines of code is genuinely shocking. We built it from scratch to understand exactly what's going on under the hood.
Can Gzip + KNN Actually Beat BERT at Text Classification?
The paper claimed that by using gzip compression distances as features fed into a K-nearest neighbors classifier, you could outperform BERT — a massive Transformer model — on sentiment analysis benchmarks. No neural network. No embeddings. No GPU. Just compression math and a simple classifier.
02:15
The core NCD formula explained with a live code example
Watch at 02:15 →
After building it from scratch and running tests, the real answer is: no, it doesn't beat BERT — but it also wasn't as far off as you might expect. There was a critical bug in the original paper: the authors used K=2 for neighbors and counted ties as correct without running a tiebreaker. That single mistake inflated their reported accuracy by roughly 5 percentage points — just enough to push the result above BERT's benchmark.
Even with that correction, achieving ~75% accuracy on sentiment classification with no model training, no embeddings, and only 500 samples is genuinely impressive. It's not beating BERT. But it's not 50% random guessing either. Something real is happening here.
What Is the 'Parameter-Free Text Classification' Paper?
The paper proposes a completely parameter-free approach to text classification. There are no weights to train, no embeddings to learn, and no deep learning frameworks required. Instead, it uses two components you almost certainly already have installed:
06:40
Running the 500-sample classifier and checking accuracy results
Watch at 06:40 →
- Gzip — a standard lossless compression algorithm based on statistical patterns in data
- K-Nearest Neighbors (KNN) — a classic ML algorithm that classifies based on proximity to labeled training examples
The core intuition is elegant: text with similar sentiment will compress to similar lengths because they share common vocabulary, syntax patterns, and phrasing. Angry reviews sound like other angry reviews. Positive reviews sound like other positive reviews. Gzip's statistical compression captures those patterns implicitly — and the length of the compressed output becomes your feature.
How Does Normalized Compression Distance Work in NLP?
The key concept here is the Normalized Compression Distance (NCD). Here's the formula broken down simply:
- Compress text sample A — get its compressed length
- Compress text sample B — get its compressed length
- Compress A + B concatenated together — get the combined compressed length
- NCD = (compressed(A+B) − min(compressed(A), compressed(B))) / max(compressed(A), compressed(B))
The idea is that if A and B are very similar, compressing them together won't add much new information — the compressor will find lots of shared patterns to exploit. The NCD score will be close to 0. If they're very different, the combined compression will be much larger, and the NCD will approach 1.
11:20
Multiprocessing pool setup for parallel NCD computation
Watch at 11:20 →
Each text sample gets compared against every sample in the training set, producing a vector of NCD values. That vector is the feature representation fed into KNN. There's no embedding model, no tokenizer, no vocabulary — just compression math.
How to Implement Gzip Text Classification in Python
The implementation really does fit in about 25 lines of meaningful code. Here's the core logic:
First, import your tools: gzip for compression, KNeighborsClassifier from scikit-learn, and pickle to load your dataset. Load your text samples paired with labels (e.g., 1 for positive sentiment, -1 for negative).
16:05
Histogram of sample lengths showing the 200-600 character sweet spot
Watch at 16:05 →
Next, define your NCD function. Compress each string with gzip.compress(string.encode()) and take the len() of the result. Compress the concatenation of both strings. Then apply the NCD formula above.
Then compute the NCD matrix: for every sample in your test set, calculate its NCD against every sample in your training set. This gives each test sample a vector of distances to all training samples.
Finally, train a KNeighborsClassifier on your training NCD matrix and evaluate on the test NCD matrix. That's it. The entire pipeline. No pretrained models. No cloud APIs. No GPU required.
One important note: the slowest part of this whole system is computing the NCD matrix, not the KNN classification itself. For 500 samples it's fast. For 10,000 samples, running it linearly will take hours — which brings us to the next problem to solve.
How to Speed Up NCD Calculation With Multiprocessing
To scale this to 10,000 samples, you need parallelism. The good news: every NCD calculation is completely independent of every other one, making this a perfect use case for Python's multiprocessing module.
The approach: initialize your NCD matrix with zeros upfront (preserving index order is critical). Use multiprocessing.Pool to map a helper function across all samples simultaneously, where each worker calculates the full NCD vector for a single sample. When results return, populate the pre-initialized matrix by index — not by append order — to guarantee the correct alignment between samples and their feature vectors.
With this approach, 10,000 samples becomes tractable on a modern multi-core machine. The result? A stable ~75.7% accuracy on sentiment classification. No neural network. No fine-tuning. Just compression distances and a nearest-neighbor vote.
Why Does Gzip Classification Fail on Short Text?
This is where things get practically important. Gzip is a statistical compression algorithm — it needs enough text to find repeating patterns and exploit them efficiently. Very short strings don't give the compressor enough material to work with, which means the compressed lengths won't meaningfully differentiate between positive and negative sentiment.
In testing, short strings — a few words or a single sentence — were almost always classified as negative regardless of their actual content. The classification was happening for the wrong reasons: pure length artifacts, not sentiment patterns.
Analyzing a histogram of training sample lengths reveals the sweet spot clearly: you want samples with at least 200 characters, ideally 600 or more. Anything shorter and you're essentially asking the algorithm to classify noise. This is a significant practical constraint — it means this method works best on longer-form text like reviews, articles, or detailed feedback, not tweets or short phrases.
When Should You Use KNN Instead of Deep Learning?
This experiment is a powerful reminder of something easy to forget in the age of LLMs and Transformers: deep learning is not always the right tool. A surprising number of real-world text classification problems don't require a fine-tuned BERT model, a GPU cluster, or thousands of labeled examples.
Consider reaching for simpler methods first when:
- Your labeled dataset is small (hundreds to low thousands of samples)
- Inference speed and compute cost matter
- Interpretability is important to stakeholders
- You need a quick baseline before investing in heavier infrastructure
The gzip + KNN method won't win Kaggle competitions. But hitting 75% accuracy on sentiment classification with zero training, zero embeddings, and 25 lines of Python is a genuinely remarkable result. It forces a useful question: how much of what a large language model learns about text is just statistical compression in disguise?
Nobody has a clean answer to that yet. But the fact that a compression algorithm with no understanding of language can get 75% of the way there on sentiment analysis is worth sitting with for a while.
