6 ms·

Large Text Compression Benchmark

97 points by redeux 2y ago

pmayrgundter 2y ago
The very notable thing here is that the best method uses a Transformer, and no other entry does
- wmf 2y ago
  Text compression and text generation are both based on modeling so the best approach to text modeling works for both.
  - sfink 2y ago
    Not if part of your definition of "best" includes codebook/model size. The best text generator will use a massive model. That won't help compression beyond a certain point, since the cost of lookup indexes grows with the size of the model. "Monkey #384714...872 typewriter output" doesn't help when the monkey number is longer than the input.
- londons_explore 2y ago
  Transformers run well on GPU's or other hardware accelerators. This benchmark doesn't allow GPU's. That makes it more of a "can I use unsuitable hardware to get the job done fast and accurately enough" challenge, rather than a pure math puzzle of how to encode data with fewer bytes. I suspect that's why there is only 1 Transformer entry, and to me raises the question whether the rules should be updated to allow GPU's now they are fairly commonplace.
  - HybridCurve 2y ago
    I think it might be a moot point since the transformer run times scale very poorly and the algorithm has a symmetric run time.
hyperpape 2y ago
It's worth noting that the benchmark has not been updated as frequently for the past several years, and some versions of compressors are quite far behind the current implementations (http://www.mattmahoney.net/dc/text.html#history http://www.mattmahoney.net/dc/text.html#history). The one instance I double-checked (zstd) I don't recall it making a massive difference, but it did make a difference (iirc, the current version was slightly smaller than what was listed in the benchmark).
- pella 2y ago
  agree, - in the benchmark "zstd 0.6.0" ( Apr 13, 2016 ) - vs. latest zstd v1.5.6 ( Mar 30, 2024 https://github.com/facebook/zstd/releases https://github.com/facebook/zstd/releases )
  - londons_explore 2y ago
    Only really worth updating if the results are meaningfully different though. Since zstd's format is fixed, I doubt there will be massive changes in compression ratio.
    - namibj 2y ago
      Ehhh, it's the decompressor that's specified, and there's considerable wiggle room a'la Trellis modulation in radio line coding, due to the interplay of the dictionary coder with the entropy coder. Basically, there are many moments the dictionary coder has to make non-obvious decisions about how to code a sequence, and what matters is that the whole content overall has the least entropy, not the least length when fed to the entropy coder. For simple codings like the TLV bitstream in QR codes (the L field bit length depends on the T and the QR code size (i.e., the max bitstream length possible))[0], you can afford to solve for all possibilities via e.g. dynamic programming with some mild heuristics to terminate search branches that can't possibly code shorter due to the TL overhead. But with an entropy coder like zstd's fst/tANS, that's not remotely as trivial. Making a choice will change the symbol/byte histogram for the entropy coder's input sequence, which, if after quantization by tANS still different, can change the length of the coded bitstream. The problem is the non-local effect on a symbol's coding size from making any individual residency coding decision. BTW, friendly reminder that all-caps URLs will code shorter into QR codes, so the code will have larger pixels or be smaller. [0]: there are 5 main modes (i.e., T values): ([0-9])+ coded by stuffing 3 digits into 10 bit and trailing 2/1 digits into 7/4 bits, respectively; ([0-9]|[A-Z]|[:space:]|[\$\%*\+\−\/\.,\:])+ coded by stuffing 2 characters into 11 bits; ISO-8859-1 coded by stuffing one character into 8 bits; Kanji by stuffing each into 13 bits; and a ECI mode for iirc generic Unicode codepoints. I think the other 3 code points in T are used for legacy barcode FNC1 and FNC2, as well as an end-of-content marker.
pama 2y ago
It would be nice to also have a competition of this type where within ressonable limits the size of the compressor does not matter and the material to be compressed is hidden and varied over time. For example up to 10GB compressor size and the dataset is a different random chunk of fineweb every week.
- stephantul 2y ago
  That’s an interesting idea. I wonder whether it would actually lead to radically different solutions, bit with bigger codebooks.
nick238 2y ago
Double your compression ratio for the low, low price of 100,000x slower decompression (zstd: 215GB, 2.2 ns/byte vs. nncp: 106GB, 230 µs/byte)! The neural network architectures are technically impressive, but unless there's some standard compression dictionary that works for everything (so the training/compression costs amortize down to nil), and silicon architecture dramatically changes to compute-on-memory, I don't know if this would ever take off. Lossy compression would probably provide huge advantages, but then you need to be domain specific, and can't slap it on anything.
- lxgr 2y ago
  One interesting application could be instant messaging over extremely bandwidth constrained paths. I wouldn’t be surprised if Apple were doing something like this for their satellite-based iMessage implementation. Of course it could also just be a very large “classical” shared dictionary (zstd and brotli can work in that mode, for example).
  - londons_explore 2y ago
    Unfortunately, while you want to have encryption on your messages, the required encryption signature eclipses the message size. Without signing the messages (and just using a stream cipher), you could do it, but an adversary can send garbage pretending to be you, which I don't think is acceptable in the modern world. Also, the message headers (message length, from, to) also start to dominate and compressing them is hard (usually depending on various hardware tricks like differing CDMA keys).
    - lxgr 2y ago
      For such low-bandwidth applications, you'll usually want to do the key exchange while you have a faster connection, as well as build a dictionary of expected recipients etc. Once you have a pre-exchanged symmetric key pair and IVs etc., encryption can be done with zero overhead, and you can choose your own trade-off between authentication security and message size. Even 4 bytes go a long way (an attacker would need to send 2^31 messages over a very bandwidth-constrained channel to impersonate you), and 8 bytes make it safe enough for practically all applications. That way, you can keep the authentication overhead very small (on the order of a few bytes), similar to how it's done for e.g. SRTP.
sfink 2y ago
I'd kind of like to see some sample LLM entries in the list (as in, at the bottom of the list). Not because they'd ever be competitive, but because it would underscore how they burn massive amounts of space for the model with little concern for how much of it is "necessary" for predicting text. (I'm not sure how you would optimally use an LLM for a lossless compression task. I guess you could convert the input to a stream of single-bit "yes, it guessed right" tokens and multi-bit "no, the actual token is X" tokens, and then compress that stream with a more traditional entropy encoder? That way the LLM decompressor would always be working off a valid prefix. But there are probably more clever ways.)
- Sesse__ 2y ago
  > I'm not sure how you would optimally use an LLM for a lossless compression task. You have the model output probabilities for each token, and then use arithmetic encoding using that model. (This uses optimally few bits per token, under the assumption that your model is right.) This is how all the winning models work, AFAIK, except they frequently work per-bit instead of per-token.
  - sfink 2y ago
    Oh duh, that makes a lot more sense. Thanks!
- jonas21 2y ago
  The top entry is based on a Transformer architecture. It's basically an LLM, but trained on the input instead.
stjo 2y ago
The current best solution is written by Fabrice Bellard, probably more famous for his other works like FFMPEG, QEMU and TCC - https://bellard.org/ https://bellard.org/. Check him, pretty much everything coming from him is pure gold.
- TacticalCoder 2y ago
  When people say there are no 10x programmer, I name Fabrice Bellard. Him being a 100x programmer invalidates the logic of those trying to explain there aren't 10x programmers.

97 points by redeux 2y ago

pmayrgundter 2y ago

The very notable thing here is that the best method uses a Transformer, and no other entry does

wmf 2y ago
Text compression and text generation are both based on modeling so the best approach to text modeling works for both.
- sfink 2y ago
  Not if part of your definition of "best" includes codebook/model size. The best text generator will use a massive model. That won't help compression beyond a certain point, since the cost of lookup indexes grows with the size of the model. "Monkey #384714...872 typewriter output" doesn't help when the monkey number is longer than the input.
londons_explore 2y ago
Transformers run well on GPU's or other hardware accelerators. This benchmark doesn't allow GPU's. That makes it more of a "can I use unsuitable hardware to get the job done fast and accurately enough" challenge, rather than a pure math puzzle of how to encode data with fewer bytes. I suspect that's why there is only 1 Transformer entry, and to me raises the question whether the rules should be updated to allow GPU's now they are fairly commonplace.
- HybridCurve 2y ago
  I think it might be a moot point since the transformer run times scale very poorly and the algorithm has a symmetric run time.

hyperpape 2y ago

It's worth noting that the benchmark has not been updated as frequently for the past several years, and some versions of compressors are quite far behind the current implementations (http://www.mattmahoney.net/dc/text.html#history http://www.mattmahoney.net/dc/text.html#history). The one instance I double-checked (zstd) I don't recall it making a massive difference, but it did make a difference (iirc, the current version was slightly smaller than what was listed in the benchmark).

pella 2y ago
agree, - in the benchmark "zstd 0.6.0" ( Apr 13, 2016 ) - vs. latest zstd v1.5.6 ( Mar 30, 2024 https://github.com/facebook/zstd/releases https://github.com/facebook/zstd/releases )
- londons_explore 2y ago
  Only really worth updating if the results are meaningfully different though. Since zstd's format is fixed, I doubt there will be massive changes in compression ratio.
  - namibj 2y ago
    Ehhh, it's the decompressor that's specified, and there's considerable wiggle room a'la Trellis modulation in radio line coding, due to the interplay of the dictionary coder with the entropy coder. Basically, there are many moments the dictionary coder has to make non-obvious decisions about how to code a sequence, and what matters is that the whole content overall has the least entropy, not the least length when fed to the entropy coder. For simple codings like the TLV bitstream in QR codes (the L field bit length depends on the T and the QR code size (i.e., the max bitstream length possible))[0], you can afford to solve for all possibilities via e.g. dynamic programming with some mild heuristics to terminate search branches that can't possibly code shorter due to the TL overhead. But with an entropy coder like zstd's fst/tANS, that's not remotely as trivial. Making a choice will change the symbol/byte histogram for the entropy coder's input sequence, which, if after quantization by tANS still different, can change the length of the coded bitstream. The problem is the non-local effect on a symbol's coding size from making any individual residency coding decision. BTW, friendly reminder that all-caps URLs will code shorter into QR codes, so the code will have larger pixels or be smaller. [0]: there are 5 main modes (i.e., T values): ([0-9])+ coded by stuffing 3 digits into 10 bit and trailing 2/1 digits into 7/4 bits, respectively; ([0-9]|[A-Z]|[:space:]|[\$\%*\+\−\/\.,\:])+ coded by stuffing 2 characters into 11 bits; ISO-8859-1 coded by stuffing one character into 8 bits; Kanji by stuffing each into 13 bits; and a ECI mode for iirc generic Unicode codepoints. I think the other 3 code points in T are used for legacy barcode FNC1 and FNC2, as well as an end-of-content marker.

pama 2y ago

It would be nice to also have a competition of this type where within ressonable limits the size of the compressor does not matter and the material to be compressed is hidden and varied over time. For example up to 10GB compressor size and the dataset is a different random chunk of fineweb every week.

stephantul 2y ago
That’s an interesting idea. I wonder whether it would actually lead to radically different solutions, bit with bigger codebooks.

nick238 2y ago

Double your compression ratio for the low, low price of 100,000x slower decompression (zstd: 215GB, 2.2 ns/byte vs. nncp: 106GB, 230 µs/byte)! The neural network architectures are technically impressive, but unless there's some standard compression dictionary that works for everything (so the training/compression costs amortize down to nil), and silicon architecture dramatically changes to compute-on-memory, I don't know if this would ever take off. Lossy compression would probably provide huge advantages, but then you need to be domain specific, and can't slap it on anything.

lxgr 2y ago
One interesting application could be instant messaging over extremely bandwidth constrained paths. I wouldn’t be surprised if Apple were doing something like this for their satellite-based iMessage implementation. Of course it could also just be a very large “classical” shared dictionary (zstd and brotli can work in that mode, for example).
- londons_explore 2y ago
  Unfortunately, while you want to have encryption on your messages, the required encryption signature eclipses the message size. Without signing the messages (and just using a stream cipher), you could do it, but an adversary can send garbage pretending to be you, which I don't think is acceptable in the modern world. Also, the message headers (message length, from, to) also start to dominate and compressing them is hard (usually depending on various hardware tricks like differing CDMA keys).
  - lxgr 2y ago
    For such low-bandwidth applications, you'll usually want to do the key exchange while you have a faster connection, as well as build a dictionary of expected recipients etc. Once you have a pre-exchanged symmetric key pair and IVs etc., encryption can be done with zero overhead, and you can choose your own trade-off between authentication security and message size. Even 4 bytes go a long way (an attacker would need to send 2^31 messages over a very bandwidth-constrained channel to impersonate you), and 8 bytes make it safe enough for practically all applications. That way, you can keep the authentication overhead very small (on the order of a few bytes), similar to how it's done for e.g. SRTP.

sfink 2y ago

I'd kind of like to see some sample LLM entries in the list (as in, at the bottom of the list). Not because they'd ever be competitive, but because it would underscore how they burn massive amounts of space for the model with little concern for how much of it is "necessary" for predicting text. (I'm not sure how you would optimally use an LLM for a lossless compression task. I guess you could convert the input to a stream of single-bit "yes, it guessed right" tokens and multi-bit "no, the actual token is X" tokens, and then compress that stream with a more traditional entropy encoder? That way the LLM decompressor would always be working off a valid prefix. But there are probably more clever ways.)

Sesse__ 2y ago
> I'm not sure how you would optimally use an LLM for a lossless compression task. You have the model output probabilities for each token, and then use arithmetic encoding using that model. (This uses optimally few bits per token, under the assumption that your model is right.) This is how all the winning models work, AFAIK, except they frequently work per-bit instead of per-token.
- sfink 2y ago
  Oh duh, that makes a lot more sense. Thanks!
jonas21 2y ago
The top entry is based on a Transformer architecture. It's basically an LLM, but trained on the input instead.

stjo 2y ago

The current best solution is written by Fabrice Bellard, probably more famous for his other works like FFMPEG, QEMU and TCC - https://bellard.org/ https://bellard.org/. Check him, pretty much everything coming from him is pure gold.

TacticalCoder 2y ago
When people say there are no 10x programmer, I name Fabrice Bellard. Him being a 100x programmer invalidates the logic of those trying to explain there aren't 10x programmers.