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 provided 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 - unparalleled better as it uses twice less disk.

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

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. :-)

.

Yes, but it is a useful insight that both methods try to solve the same mathematical problem. It's better than thinking of LLMs as magic.

When you say "cross-entropy loss" people without stats background go to Wikipedia, take a glance, and adjust their mental model to "inscrutable magic".

Thinking of the main difference as the trade-off in how much CPU, memory and storage is allowed is not really wrong.

The part that is wrong is to think of gzip as a method that might reach similar complexity or generalization. And more importantly, to ignore the advanced way how training data gets curated or generated for (instructed, chain-of-thought) LLMs. But even then. The mental model that the LLM's goal is text compression is not wrong. The question to ask next is what kind of text it is expecting to compress.

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.

Only if it can run DOOM.

Yes: you can classify a test file by topic with gzip as follows:

  gzip -9 sports.txt   testfile.txt

  gzip -9 politics.txt testfile.txt

  gzip -9 business.txt testfile.txt

(ass. sports.txt politics.txt and business.txt are text docs pertaining from the sports, politics and business domains, respectively, and have equal size)

The test file belongs to the topic with the smallest size *.gz file.

Witten's group at Waikato uni were perhaps the first to work on this.

Also check out the Hutter prize if you are interested in this.

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?

I was curious to see how this would work with bzip2 and zstd. The source is public at https://github.com/nathanrs/gzipt, and I asked MiMo-V2.6-Flash to fork and modify it. The answer is that bzip2 produces sequences that don't resemble human language:

  gzipt \
      --corpus data/tinyshakespeare.txt \  
      --prompt $'MENENIUS:\n' \
      --length 200 \
      ;
  
  MENENIUS:
  MtLUMSeptuttyyyxyxyxyxyvyyyxyxyxyxyvyyyxyxyxyxywyvzyxyxyx
  yyxyyyxyxyxyxyxPlyxyxyxyxyxyxyxyxyxtoxzfTUS.zxzzzyzzzvzzz
  vzzzxvzyvyxyxyxyvyxyxyxyvy--,Vdvyxyxyxyxyxyxyxyxyxxy!zFlx
  zzyyxyxyxyvyxyxyxyvyySPffuyuy

Line breaks added. This looks roughly optimized for the most repetitive Burrows-Wheeler transform (https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf...).

Zstandard produces whitespace with the occasional letter thrown in. To quote MiMo: "As you can see, zstd does not speak Shakespeare. ... zstd encodes a run of one repeated byte as a near-free run-length sequence, and space and newline are the cheapest literals in the corpus: ten newlines cost about the same to append ten bytes of genuine corpus text and less than nonsense does."

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.