On: Gzip and KNN Outperforms Transformers on Text Classification

[nextos]

Something important to note is that the authors use normalized compression distance (NCD). NCD is a way to approximate Kolmogorov complexity.

This is a pretty old idea, see [1,2]. Old but still very useful, like perceptrons.

[1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications.

[2] Clustering by compression. https://arxiv.org/pdf/cs/0312044