We used a similar technique for a class project (N decades ago) to test this:

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

By looking at mutual information from different authors on the same topic vs same author on different topics. As I recall, it convincingly disproved the hypothesis.

That's a bit of a stretch. The LZ77 algorithm merely finds repeated items within a sliding window and encodes them into Huffman codes. A basic model should at least be capable of classification and prediction, like very early-stage machine models. The former is a fixed, quantifiable algorithm, whereas the latter becomes difficult to quantify and understand once the scale of neurons grows large. It's not very reasonable to regard the two as the same thing.

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.

There would be some overlap with business sports analogies - eg team huddle.

I seem to remember it being shown for character recognition via JBIG. Maybe in Managing Gigabytes?

There are some deep connections between machine learning, compression, and cryptography with information theory as a common thread.

Also, I’ve never seen “ass.” Used to shorten “aside” — I typically use N.B. but perhaps only for important ones.

Nitpick: Doing it exactly like this is flawed because you let the compressibility of your references taint the result; what you would prefer is the compressed size of testfile given sports.txt/... as a dictionary without accounting for the compressed size of that, no?

Really interesting approach though.

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

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

[dead]

winrar is profitable? sure? well, on the other hand, they sure don't make losses

  |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%*|

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

Read to the end: they aren't actually looking for the best-compressing output, because this quickly devolves into aaaaaaaaaaa. They keep a sliding window over a small portion of recent text and use that.

Basically I think the entire premise falls apart due to that choice--they forced an interesting-looking outcome by adjusting the algorithm until gzip started picking random slabs of letters instead of ever-larger repeating runs.

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)

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.

Language is compression of a sort. A dictionary is a decompressor. You look up one word, and you may get a paragraph about its meaning. An encyclopedia can be thought of as roughly the same with more detail for some nouns.

It makes a lot of sense why dictionary-based compression is named the way it is. A shorter symbol is used to store information that would take more symbols in the uncompressed corpus, if the shorter symbol hadn't been assigned to represent it. That's in a way just what an actual dictionary on your English professor's shelf does. The big difference is your compressor is coining new short symbols all the time.

You're describing https://bellard.org/ts_zip/ ("Text Compression using Large Language Models") ?

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

>I've been pondering on something related: can an LLM be a chat?

A chat?

>I am not talking about an "AI agent", but really a model that we call in a reproducible manner.

An LLM is just as deterministic as any other computer program. For identical inputs (which includes the PRNG seed) it produces identical outputs.

>compressed version of the git kernel

The git kernel, got it.

>But would this count as "compression" at all?

Yes. The decompressor is several tens of gigabytes though.

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.

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

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

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.