4 ms·

So has anyone tried lossless compression with an LLM? Method: create a list of next token predictions, ordered by describing probability, and encode the actual

So has anyone tried lossless compression with an LLM? Method: create a list of next token predictions, ordered by describing probability, and encode the actual token as its position in the ordered list (so, eg, the most likely token is encoded as zero, second most likely as 1, etc). If the LLM is good, this should provide an excellent encoding.

atorodius 3y ago
Yes, next token prediction is exactly what you need for compression. Many papers on this, recent one https://arxiv.org/pdf/2309.10668.pdf https://arxiv.org/pdf/2309.10668.pdf
- sdenton4 3y ago
  Lovely paper, thanks!
duskwuff 3y ago
> If the LLM is good, this should provide an excellent encoding. For the purposes of compression "contests" like this one, the size of the model would count against your compressed data size. You're going to have a hard time fitting a useful model into <100 MB.
- sdenton4 3y ago
  The thing is, we typically have three parts of a compression scheme: the data, the model (dictionary, Huffman tree, etc), and the program. The model is typically learned from the data at compression time. The program itself is general, however, and as far as I know, doesn't count against the total. Ie, the size of the gzip binary isn't part of the total for the purposes of the contest. So if an LLM is genuinely useful without fine tuning on the target data, you should make it part of the program. The data-specific model could be a self-prompt produced from reading and summarizing the data, which would help with the initial context-free predictions... {Edit} Ha, looking at the competition, it does indeed include the full size of the gzip binary in the metric. Weird.
  - duskwuff 3y ago
    > {Edit} Ha, looking at the competition, it does indeed include the full size of the gzip binary in the metric. Weird. The competition is specific to one corpus of test data; it doesn't include testing on other data. If the size of the program weren't included, you could hard-code all of the test data into it and claim victory with an infinite compression ratio. Fun fact: the idea of using an AI language model as compression has existed since at least 1988. It was mentioned in passing by Vernor Vinge in his short story The Blabber.
DeathArrow 3y ago
Using llm doesn't help with loseless compression.
- mistercow 3y ago
  Of course it can. A typical structure for a lossless compressor is a predictor feeding into an entropy encoder. Your predictor tells you how likely each next token is, and the entropy encoder uses that information to encode more likely tokens with fewer bits. As long as the compressor and decompressor make the same predictions, you’ll be able to reconstruct the original data exactly. And if the predictions are good, you’ll compress the data well. An LLM (specifically the type people usually mean, like ChatGPT) uses a big transformer network to assign probabilities* to the all possible next tokens. To generate text, you randomly pick from the most likely next tokens, then repeat. But you can just leave out that second part, and use the transformer as your predictor for compression. * Actually the log of the probability, and in modern, RLHF tuned models, they don’t quite represent probabilities anymore, but anyway
- sp332 3y ago
  The top prize winners so far are neural networks (but smaller ones).
zimpenfish 3y ago
Didn't Fabrice Bellard make something along these lines? https://bellard.org/nncp/ https://bellard.org/nncp/

atorodius 3y ago

Yes, next token prediction is exactly what you need for compression. Many papers on this, recent one https://arxiv.org/pdf/2309.10668.pdf https://arxiv.org/pdf/2309.10668.pdf

sdenton4 3y ago
Lovely paper, thanks!

duskwuff 3y ago

> If the LLM is good, this should provide an excellent encoding. For the purposes of compression "contests" like this one, the size of the model would count against your compressed data size. You're going to have a hard time fitting a useful model into <100 MB.

sdenton4 3y ago
The thing is, we typically have three parts of a compression scheme: the data, the model (dictionary, Huffman tree, etc), and the program. The model is typically learned from the data at compression time. The program itself is general, however, and as far as I know, doesn't count against the total. Ie, the size of the gzip binary isn't part of the total for the purposes of the contest. So if an LLM is genuinely useful without fine tuning on the target data, you should make it part of the program. The data-specific model could be a self-prompt produced from reading and summarizing the data, which would help with the initial context-free predictions... {Edit} Ha, looking at the competition, it does indeed include the full size of the gzip binary in the metric. Weird.
- duskwuff 3y ago
  > {Edit} Ha, looking at the competition, it does indeed include the full size of the gzip binary in the metric. Weird. The competition is specific to one corpus of test data; it doesn't include testing on other data. If the size of the program weren't included, you could hard-code all of the test data into it and claim victory with an infinite compression ratio. Fun fact: the idea of using an AI language model as compression has existed since at least 1988. It was mentioned in passing by Vernor Vinge in his short story The Blabber.

DeathArrow 3y ago

Using llm doesn't help with loseless compression.

mistercow 3y ago
Of course it can. A typical structure for a lossless compressor is a predictor feeding into an entropy encoder. Your predictor tells you how likely each next token is, and the entropy encoder uses that information to encode more likely tokens with fewer bits. As long as the compressor and decompressor make the same predictions, you’ll be able to reconstruct the original data exactly. And if the predictions are good, you’ll compress the data well. An LLM (specifically the type people usually mean, like ChatGPT) uses a big transformer network to assign probabilities* to the all possible next tokens. To generate text, you randomly pick from the most likely next tokens, then repeat. But you can just leave out that second part, and use the transformer as your predictor for compression. * Actually the log of the probability, and in modern, RLHF tuned models, they don’t quite represent probabilities anymore, but anyway
sp332 3y ago
The top prize winners so far are neural networks (but smaller ones).

zimpenfish 3y ago

Didn't Fabrice Bellard make something along these lines? https://bellard.org/nncp/ https://bellard.org/nncp/