It's just the best general purpose compression algorithm, in terms of compression ratio to CPU used, for the vast majority of use cases

It's just this good.

On a more realistic note: few years back, I've added zstd compression to our log subsystem (hand written direct buffers, native code, in-process, java). For the same CPU utilization if provides twice dense compression compared to regular [-6] gzip (the topic in the title). Zstd is =much= faster on decompression as well, and it this case - unparalleledly better as it uses twice less disk.

zstd is 'silicon valley' (the tv show) - life imitates fiction, except entirely open source

Lzma. I did a simple test, same payload repeated with a gap. Lzma ruled it.

|gap |gzip |bz2 |lzma | |---------|----------|-----|--------| |0 |2.7% |18.9%|*0.9%*| |8 KB |2.4% |17.8%|0.9% | |*40 KB*|*94.4%* |17.7%|0.4% | |1 MB |*104.3%*|19.7%|*0.9%*|

You need to visit Japan...

Huh. I guess the warez kids grew up and have money, now?

The original author and also creator of the RAR format, Eugene Roshal, is Russian. I think he moved to the US way back in the day, but not sure about that. He has been very private with his life.

The company doing the software distribution, is located in Berlin. The Managing Directors for that company seem to have Turkish names, but I don't know if they're Turkish.

BTW, Looking for some info I just found a website [0], clearly AI generated (but not necessarily meaning the content is false) claiming Eugene Roshal had severe kidney failure this past month, and he's waiting for surgery. They're asking for donations. There are some names on who's theoretically behind it [1] but they don't link to any LinkedIn profile or personal site. I can't find any other references. The BTC wallet they're using for donations hasn't seen any traffic ever. BE WARY, SMELLS FISHY.

--

  0: https://eugeneroshal.org/
  1: https://eugeneroshal.org/about/

That's a fair question. Suppose we have a way to find a byte sequence x that globally minimises len(gzip(context + prompt + x)) over all sequences x of length n. Here + denotes string concatenation.

It's unclear if this is very useful.

The reason it may not be very useful is that one of Deflate's ingredients is a pass that replaces repeated substrings with backreferences to the earlier occurrence in the plaintext input stream.

E.g. suppose we want to find an n=200 byte sequence x that minimises len(gzip(context+prompt+x)).

If there exists any 200 byte sequence y such that prompt+y is a substring of context, then Deflate can encode prompt+y as a backreference to that earlier sequence - it needs to store a match-length & a distance-length, encoded using its Huffman trees. This candidate solution y may not be a global minima to our stated objective function, but if not, it's probably going to be a very good near-optimal approximate solution.

Taking a step back, repeating huge chunks of the input context produces something that's great for minimising compressed output size but doesn't seem particularly helpful as a generative model.

edit:

Yep, I tried it out by running an experiment. Searching for the prompt in the context & then copying the following text as the solution produces solutions that are much better, in the sense of minimising the compressed output length, than beam search, while also being unhelpful as a generative tool.

With the same example as the blog post:

  context: first 30,000 bytes of tinyshakespeare.txt
  prompt: 'MENENIUS:\n'

Let x denote a solution, x is a string of length 200.

Let L(x) denote len(gzip(context+prompt+x)), our objective function

Let's call the proposed search method of searching for the prompt in the input rfind (after python's str.rfind).

Then we have

   search method      soln               soln length   feasible?     objective value      search time (wall clock, s)
   -------------      ----               -----------   ---------     ---------------      ---------------------------
   emptystring        ""                          0          no              13,023                     0.04s
   gzipt beam search  see blog post             200         yes              13,051                    11.93s
   rfind              see below                 200         yes              13,026                     0.04s

So 'rfind' is finding a solution that does a better job of minimising the objective function -- it only takes 3 bytes more to encode than the infeasible emptystring solution, and costs 25 fewer bytes than the solution found by the beam search implemented by gzipt per the blog post.

Here's the solution 'generated' by rfind copying and pasting from the input context, starting from the rightmost occurrence of "MENENIUS:"

   MENENIUS:
   O, true-bred!
   
   First Senator:
   Your company to the Capitol; where, I know,
   Our greatest friends attend us.
   
   TITUS:
   
   COMINIUS:
   Noble Marcius!
   
   First Senator:
   
   MARCIUS:
   Nay, let them follow:
   The Volsces 

Here's the code for 'rfind' - our complete 'generative algorithm':

    def find_candidate_solution_from_context(context, prompt, length):
        n = len(context)
        i = context.rfind(prompt, 0, n-length)
        if i < 0:
            return b''
        i += len(prompt)
        return context[i:i+length]

Can hook it into gzipt.py by adding this line after out is defined, but before the beam search begins

    out += find_candidate_solution_from_context(corpus_window, prompt, length)

I wonder if, on an information theoretical level, compression radiates heat, and decompression absorbs it?

Any benchmarks using it?

A challenge as I understand it is reproducibility.

Normal LLM runtimes aren't typically fully reproducible even with same random seeds for distribution sampling, due to floating-point numbers, batching and such.

Though averaging over many runs could alleviate that I suppose.

While it would measure some aspects of intelligence, I'd argue it fails to capture other, more creative aspects.

Match-finding does not need to be quadratic. However, truly optimal gzip block splitting is very slow, indeed.

It won't move as fast as gzip provided the same resources, but to say that LLM's can never run at 300mbps on any hardware is ... a bold bet.

I agree, but also equating LLMs with intelligence is wrong.

Previous discussions of that specific page https://news.ycombinator.com/item?id=48557691

Even ignoring speed per GP, the Hutter Prize's metric includes the size of the decompressor. LLMs would be disqualified for being larger than 1GB.

And the hutter prize disallows GPU's. If you allow use of a powerful GPU, you can do quite a bit better.

0 bits is just a very small bloom filter.

hallucinations are lossy compression artefacts

I've used LZO as a spam classifier on chat. Spam tends to be very content-less and repetitive...

Check out "Text classification with Python 3.14's zstd module" (https://maxhalford.github.io/blog/text-classification-zstd/, https://news.ycombinator.com/item?id=46942864). I wanted to link it somewhere in the comments. :-)

.

Yep agree, good details, and this doesn't contradict my point above, about people going "overboard" with the comparison.

I do think when making these comparisons, it is worth emphasising that neural nets are really different. E.g. I used to see people equating LLMs to n-gram models, etc. which is overly simplistic, (especially in the early days when the models weren't as good).

3blue1brown did a series on this topic: https://www.youtube.com/watch?v=l6DKRf-fAAM https://www.youtube.com/watch?v=GlYgs6v2YfU (i think one more is yet to release)

Man,did that page load fast. It made me realize how slow the rest the (my) web is.

You sound a bit confused.

A large language model itself (the network) give you the probabilities for the next token given some prefix of tokens so far. You can use arithmetic coding to go from these probabilities to a deterministic compression / decompression algorithm.

When you use an LLM to generate text, you sample from that probability distribution. You can use a true random sample. Or you can make it trivially deterministic by using a seeded pseudo-random-number-generator or you just pick the highest probability each time. But that's all a red herring; really, what you want is arithmetic coding.

https://en.wikipedia.org/wiki/Arithmetic_coding

It makes a lot of sense. I thought about it in the context of pull requests or change sets: if the text-to-code process is reliable, why don't you give me prompts instead of code? Code becomes just an intermediate representation.

This was tried many times in the past for images, even before LLMs.

https://imalogic.com/blog/2024/06/03/image-compression-decom...

Sounds like an interesting way for future OS included apps to be distributed.

Like when you click the Calculator button on your android, it wouldn't actually exist yet, your click actually prompts it into existence. But naively that has problems because you don't want a different UI every time. There's something to your idea.

Only if it can run DOOM.

For anyone wanting an introductory text for information theory & that explores some of these connections & applications, it's worth checking out the late David MacKay's 2003 textbook Information Theory, Inference & Learning Algorithms https://www.inference.org.uk/itila/

3Blue1Brown has a good video about this: https://www.youtube.com/watch?v=l6DKRf-fAAM

Back in the day - maybe two decades ago - I implemented language detection like this.

I seeded gzip compressors’ dictionaries with Wikipedia articles in different languages.

I would then try to use said dictionaries on any random text, and the one that was best able to compress it, was the correct language.

Absolutely totally not the best approach, but very fast and super simple to implement.

aka Normalized compression distance (NCD). Its close cousin: Normalized Google distance (NGD) is also super interesting!

https://en.wikipedia.org/wiki/Normalized_compression_distanc...

I thought it was interesting.

R. Hendricks, D. Chugtai, and J. Dunn, "Lossless compression via optimized middle-out bitstream processing," Pied Piper Inc., Palo Alto, CA, Tech. Rep. 42, Apr. 2014.

I think language itself is compression, so the arxiv paper tracks for me.

Viz. if Language is compression (of thought / culture / the tacit je ne sait quois of being-to-being communication etc.), then definitionally, Language Modelling must also be Compression.

Except, language is an arbitrarily lossy compressor, who's "compression-prediction equivalence" is indeterminate and unstable, because Language co-evolves constantly; both as a function of or response to culture, as well as an influencer of culture.

So, the subjective-objective goodness of Language Models (of any kind of language) would be, at best, upper-bounded by the compression-prediction equivalence of the Languages corpus itself. And that is assuming the language corpus is perfect in every way---it captures all knowledge expressible by language and it is always in-sync with live evolution of all language expression and evolution (i.e. LLM training is not a batch job, but a real-time present continuous process).

For example, to my layperson eyes, the mathematical language of proofs actively weeds out ambiguity of subjective interpretation. Ideally, a proof ought to lead to the exact same conclusion on every single reading by any reader who can follow the steps. A proof also holds only if the rest of the formal, explicit, inviolable, internally-consistent set of axioms and results holds.

So it stands to reason that mathematical prose of proofs, being optimised as mechanical procedure of taking an open question to a deterministically closed solution, has better odds of approximating the tacit aspects of mathematical derivation.

Which makes an LLM able to construct a mathematical proof, which is mind-melting to say the least.

However, I wonder, can LLMs dream of mathematical sheep?

It depends on how you define "correctly". I read the code and saw that MiMo had replaced the zlib calls with a similar bz2 and compression.zstd call, removing the unavailable https://docs.python.org/3/library/zlib.html#zlib.Compress.co.... So what I did was check that MiMo had done what I would have for a quick experiment, not that the code was free from subtle bugs.

So, you had an AI write code you don't understand, then posted output you don't understand in a comment on the internet for other humans to read?

Good article.

Compression is a property of language.

A seemingly simple sentence like "I had lunch" has enormous amount of information compressed inside it.

The word lunch is a compressed form of "having food at noon" and "noon" in turn is a compressed form of "Sun's position against Earth's rotation" and so on and so forth.

Every sentence has layers of compressed sentences. How many layers one chooses to decompress is up to the person.

Would this work with video compression? Video codecs encode a lot of meaning; they use motion vectors to track the movement of objects on screen, for example.