5 ms·

Can anyone explain to me how a compression algorithm can beat an LLM at anything? Isn’t that like saying horses are better than graffiti? I’m sure the answer i

Can anyone explain to me how a compression algorithm can beat an LLM at anything? Isn’t that like saying horses are better than graffiti? I’m sure the answer is in there somewhere but I’m not well versed in AI and I simply can’t figure it out.

ozr 3y ago
The intuition about how the gzip method works goes like so: If you compress `ABC`, it will be X bytes. If you then compress `ABCABC`, it will not take 2x bytes. The more similar the two strings that you concatenate, the less bytes it will take. `ABCABD` will take more than `ABCABC`, but less than `ABCXYZ`. BERT is, by todays standards, a very small LLM, which we know has weaker performance than the billion-param scale models most of us are interacting with today.
- jabbany 3y ago
  > very small LLM Heh. So does that make it a MLM (medium)? I've always found it funny that we've settled on a term for a class of models that has a size claim... Especially given how fast things are evolving...
ks2048 3y ago
It's a very limited task: take a document and classify it into one of (for example) 10 or so categories. Things like detecting certain words can do pretty well in some cases. Things that compress well have the occurrence of common substrings.
kachnuv_ocasek 3y ago
One way to interpret/understand language models is as quite involved compression algorithms.
refulgentis 3y ago
Other reply is great, more in-depth on details from me here: https://news.ycombinator.com/item?id=36758681 https://news.ycombinator.com/item?id=36758681 Plain english TL;DR: - if you limit your task to binning snippets of text - and the snippets are very well-defined (ex. code vs. Filipino text) - the snippets _bytes_ could be compared and score well, no text understanding needed - size delta of a GZIP after adding one more sentence acts as an ersatz way to compare sets of bytes to eachother (ex. you can imagine a GZIP containing 0xFFABCDEF that has 0xFFABCDEF added to it will have a size delta of 0)
- fsmv 3y ago
  Did you read the recent Douglas Hofstadter article or do you just always use the word ersatz?
  - refulgentis 3y ago
    I was homeschooled till 12 and mostly left to my own devices as long as it was reading - I believe that has caused a lifelong issue where I sound like a tryhard unintentionally :( (TL;Dr I use it but IDK when, didn't see hofstader article but now I'm looking forward to it)
    - stavros 3y ago
      You can substitute the word "substitute" as an ersatz "ersatz".
      - refulgentis 3y ago
        It's honestly weird and annoying and I'd give it up in a second. There's two issues: - I don't have an ear for what's simple vocabulary versus tryhard, I go into a mad loop when I try - even if I actively notice it, substitution can seem very far away from intent. Simple wouldn't have occurred to me - I wanted to say something more akin to sloppy / stunt and ersatz is much closer to "hacky" in meaning than simple. Think MacGyver. But I should do the exercise of at least scanning for words more often and aim for wider audience - I would have known ersatz was an outlier and I shouldn't feel it's condescending or diluting meaning, it's broadening the audience who can parse it
        stavros 3y ago
        Eh, it's fine, it doesn't sound tryhard to me, just a bit hard to read.
        inimino 3y ago
        Why would you apologize for your vocabulary and try to sound like someone less well-read than you are? Just get over it and be yourself.
ajtulloch 3y ago
https://www.inference.org.uk/itprnn/book.pdf https://www.inference.org.uk/itprnn/book.pdf is a classic text on this connection.
awegio 3y ago
A language model estimates the probability of a sequence of words P(w_1, ..., w_n) or equivalently P(word | context). For compression, word sequences that have higher probability should be encoded with shorter codes, so there is a direct relationship. A well known method to construct such codes based on probabilities is Huffman coding. This works whether you use a statistical language model using word frequencies or an LLM to estimate probabilities. The better your language model (lower perplexity) the shorter the compressed output will be. Conversely, you can probably argue that a compression algorithm implicitly defines a language model by the code lengths, e.g., it assumes duplicate strings are more likely than random noise.
IKantRead 3y ago
LLMs and essentially all neural networks can be viewed as learning compression algorithms where the behavior of the compression algorithm is learned and subject to potential constraints beyond mere file reconstruction. Highly recommend reading Ted Chiang's "ChatGPT Is a Blurry JPEG of the Web"[0] to get a better sense of this. Keeping this fact in your mental model neural networks can also go a long way to demystify them. 0. https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web https://www.newyorker.com/tech/annals-of-technology/chatgpt-...
- FeepingCreature 3y ago
  (The human brain is also, in part, a blurry JPEG of the world.)
  - IKantRead 3y ago
    We currently have no reason to believe this, and information we do have seems to suggest that is very unlikely to be the case. I'm also guessing from my username you can infer that I don't think we even know enough to concretely say what is this "world" you are referencing.
    - famouswaffles 3y ago
      I don't know what exactly blurry jpeg means to you but we have every reason to believe we operate on shortcuts of reality, not reality. Nearly all your brain does with sense data is warp it to confirm to internal predictions in numerous ways. Memories are always part fabrications. You can't return to previous mental states (you only think you do) and we have no real clue what really informs decisions i.e preferences shape choices just as much as choices shape preferences. Your brain will happily fabricate rationals you sincerely believe for decision that couldn't possibly be true i.e split brain experiments
    - FeepingCreature 3y ago
      I for one massively compress my experience. I remember things on autocomplete. I have memories where different time periods are mixed together: my recollection of a room will have furniture in it that was only added later, for instance.
optimalsolver 3y ago
Compression is equivalent to intelligence: https://mattmahoney.net/dc/rationale.html https://mattmahoney.net/dc/rationale.html
GuB-42 3y ago
Generally, compression = model + entropy coding. The model's job is to predict what comes next. The entropy coder's job is to encode the difference between the prediction and what actually comes next so that the most likely outcome uses as few bits as possible. The more accurate the model is, the less the difference between reality and prediction, the less bits the entropy coder needs and the better the compression. Simple compression algorithms have simple models, like "if I see the same byte 10 times, the 11th is likely to be the same". But you can also use a LLM as your model, as completing text with the most likely word is what LLMs do. Here they did the opposite. Instead of using a model for compression, by using a few tricks, they used a compression algorithm as a model: the most likely outcome is when the compression algorithm uses less bits to encode the result. And the original authors have shown that, in some tasks, the simple model that can be extracted out of gzip beats much more complex LLMs.
- hoosieree 3y ago
  I almost feel like compression and embeddings are duals of each other, but I can't quite articulate it. Embeddings use fixed-size vectors to minimize the dot product between vectors of similar inputs. Compressors use a variable-length encoding to minimize the overall stored size.
  - naijaboiler 3y ago
    they are in a way. both encode representation of larger amounts of information on a smaller footprint.
- contravariant 3y ago
  Generally compression algorithm try to give structured data a distribution more similar to random data. If any byte sequence is a correct file (unlikely, but mostly because compression algorithms try to be robust against corruption), then this is easy to reverse, you just generate a random sequence of bytes and then decompress it. Basically you can turn a compression algorithm into a probability distribution by inserting random bytes wherever the decompression algorithm tries to read one, but sometimes not all bytes are allowed. You can then reason about this probability distribution and see what it's properties are. Typically something with a probability of 'p' will require -log(p)/log(2) bits.
stuartaxelowen 3y ago
Many other replies here are wrong - the primary reason is that the LLMs were used on completely out of distribution data (e.g. trained on English, evaluated on completely different language that shared some characters). The points about compression's relatedness to understanding are valid, but they are not the primary reason for LLMs underperforming relative to naive compression.

ozr 3y ago

The intuition about how the gzip method works goes like so: If you compress `ABC`, it will be X bytes. If you then compress `ABCABC`, it will not take 2x bytes. The more similar the two strings that you concatenate, the less bytes it will take. `ABCABD` will take more than `ABCABC`, but less than `ABCXYZ`. BERT is, by todays standards, a very small LLM, which we know has weaker performance than the billion-param scale models most of us are interacting with today.

jabbany 3y ago
> very small LLM Heh. So does that make it a MLM (medium)? I've always found it funny that we've settled on a term for a class of models that has a size claim... Especially given how fast things are evolving...

ks2048 3y ago

It's a very limited task: take a document and classify it into one of (for example) 10 or so categories. Things like detecting certain words can do pretty well in some cases. Things that compress well have the occurrence of common substrings.

kachnuv_ocasek 3y ago

One way to interpret/understand language models is as quite involved compression algorithms.

refulgentis 3y ago

Other reply is great, more in-depth on details from me here: https://news.ycombinator.com/item?id=36758681 https://news.ycombinator.com/item?id=36758681 Plain english TL;DR: - if you limit your task to binning snippets of text - and the snippets are very well-defined (ex. code vs. Filipino text) - the snippets _bytes_ could be compared and score well, no text understanding needed - size delta of a GZIP after adding one more sentence acts as an ersatz way to compare sets of bytes to eachother (ex. you can imagine a GZIP containing 0xFFABCDEF that has 0xFFABCDEF added to it will have a size delta of 0)

fsmv 3y ago
Did you read the recent Douglas Hofstadter article or do you just always use the word ersatz?
- refulgentis 3y ago
  I was homeschooled till 12 and mostly left to my own devices as long as it was reading - I believe that has caused a lifelong issue where I sound like a tryhard unintentionally :( (TL;Dr I use it but IDK when, didn't see hofstader article but now I'm looking forward to it)
  - stavros 3y ago
    You can substitute the word "substitute" as an ersatz "ersatz".
    - refulgentis 3y ago
      It's honestly weird and annoying and I'd give it up in a second. There's two issues: - I don't have an ear for what's simple vocabulary versus tryhard, I go into a mad loop when I try - even if I actively notice it, substitution can seem very far away from intent. Simple wouldn't have occurred to me - I wanted to say something more akin to sloppy / stunt and ersatz is much closer to "hacky" in meaning than simple. Think MacGyver. But I should do the exercise of at least scanning for words more often and aim for wider audience - I would have known ersatz was an outlier and I shouldn't feel it's condescending or diluting meaning, it's broadening the audience who can parse it
      - stavros 3y ago
        Eh, it's fine, it doesn't sound tryhard to me, just a bit hard to read.
      - inimino 3y ago
        Why would you apologize for your vocabulary and try to sound like someone less well-read than you are? Just get over it and be yourself.

ajtulloch 3y ago

https://www.inference.org.uk/itprnn/book.pdf https://www.inference.org.uk/itprnn/book.pdf is a classic text on this connection.

awegio 3y ago

A language model estimates the probability of a sequence of words P(w_1, ..., w_n) or equivalently P(word | context). For compression, word sequences that have higher probability should be encoded with shorter codes, so there is a direct relationship. A well known method to construct such codes based on probabilities is Huffman coding. This works whether you use a statistical language model using word frequencies or an LLM to estimate probabilities. The better your language model (lower perplexity) the shorter the compressed output will be. Conversely, you can probably argue that a compression algorithm implicitly defines a language model by the code lengths, e.g., it assumes duplicate strings are more likely than random noise.

IKantRead 3y ago

LLMs and essentially all neural networks can be viewed as learning compression algorithms where the behavior of the compression algorithm is learned and subject to potential constraints beyond mere file reconstruction. Highly recommend reading Ted Chiang's "ChatGPT Is a Blurry JPEG of the Web"[0] to get a better sense of this. Keeping this fact in your mental model neural networks can also go a long way to demystify them. 0. https://www.newyorker.com/tech/annals-of-technology/chatgpt-is-a-blurry-jpeg-of-the-web https://www.newyorker.com/tech/annals-of-technology/chatgpt-...

FeepingCreature 3y ago
(The human brain is also, in part, a blurry JPEG of the world.)
- IKantRead 3y ago
  We currently have no reason to believe this, and information we do have seems to suggest that is very unlikely to be the case. I'm also guessing from my username you can infer that I don't think we even know enough to concretely say what is this "world" you are referencing.
  - famouswaffles 3y ago
    I don't know what exactly blurry jpeg means to you but we have every reason to believe we operate on shortcuts of reality, not reality. Nearly all your brain does with sense data is warp it to confirm to internal predictions in numerous ways. Memories are always part fabrications. You can't return to previous mental states (you only think you do) and we have no real clue what really informs decisions i.e preferences shape choices just as much as choices shape preferences. Your brain will happily fabricate rationals you sincerely believe for decision that couldn't possibly be true i.e split brain experiments
  - FeepingCreature 3y ago
    I for one massively compress my experience. I remember things on autocomplete. I have memories where different time periods are mixed together: my recollection of a room will have furniture in it that was only added later, for instance.

optimalsolver 3y ago

Compression is equivalent to intelligence: https://mattmahoney.net/dc/rationale.html https://mattmahoney.net/dc/rationale.html

GuB-42 3y ago

Generally, compression = model + entropy coding. The model's job is to predict what comes next. The entropy coder's job is to encode the difference between the prediction and what actually comes next so that the most likely outcome uses as few bits as possible. The more accurate the model is, the less the difference between reality and prediction, the less bits the entropy coder needs and the better the compression. Simple compression algorithms have simple models, like "if I see the same byte 10 times, the 11th is likely to be the same". But you can also use a LLM as your model, as completing text with the most likely word is what LLMs do. Here they did the opposite. Instead of using a model for compression, by using a few tricks, they used a compression algorithm as a model: the most likely outcome is when the compression algorithm uses less bits to encode the result. And the original authors have shown that, in some tasks, the simple model that can be extracted out of gzip beats much more complex LLMs.

hoosieree 3y ago
I almost feel like compression and embeddings are duals of each other, but I can't quite articulate it. Embeddings use fixed-size vectors to minimize the dot product between vectors of similar inputs. Compressors use a variable-length encoding to minimize the overall stored size.
- naijaboiler 3y ago
  they are in a way. both encode representation of larger amounts of information on a smaller footprint.
contravariant 3y ago
Generally compression algorithm try to give structured data a distribution more similar to random data. If any byte sequence is a correct file (unlikely, but mostly because compression algorithms try to be robust against corruption), then this is easy to reverse, you just generate a random sequence of bytes and then decompress it. Basically you can turn a compression algorithm into a probability distribution by inserting random bytes wherever the decompression algorithm tries to read one, but sometimes not all bytes are allowed. You can then reason about this probability distribution and see what it's properties are. Typically something with a probability of 'p' will require -log(p)/log(2) bits.

stuartaxelowen 3y ago

Many other replies here are wrong - the primary reason is that the LLMs were used on completely out of distribution data (e.g. trained on English, evaluated on completely different language that shared some characters). The points about compression's relatedness to understanding are valid, but they are not the primary reason for LLMs underperforming relative to naive compression.