5 ms·

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 netwo

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.
jeffbee 2y ago
It does seem as though the training cost of these models ought to be included in their times, because the compressors are useless for any purpose other than compressing English Wikipedia.
- gwern 2y ago
  In these cases, the models are so small, and have to run on very limited CPU, that the training time is going to be fairly negligible. The top-listed program, nncp, is just 0.06b parameters! https://bellard.org/nncp/nncp_v2.pdf#page=4 https://bellard.org/nncp/nncp_v2.pdf#page=4
- gliptic 2y ago
  The training cost is included because these NN compressors are running the training while they are compressing. They are general compressors, although the specific variants submitted here may be tuned a little to Wikipedia (e.g. the pre-processors).
Xcelerate 2y ago
> unless there's some standard compression dictionary that works for everything There is, at least for anything worth compressing. It’s called the halting sequence. And while it exists, it’s also uncomputable unfortunately haha.
- Vecr 2y ago
  Apparently there's ways of getting the first few binary digits, but it's useless at that length.
  - Xcelerate 2y ago
    Not useless. That’s most of mathematics right there.
    - HappMacDonald 2y ago
      What precisely are you lot referring to? I'm familiar with the Halting Problem, and glancingly familiar with Ω / Chaitin's constant(s). But I'm not familiar with any kind of uncomputable sequence which we know how to get the first few binary digits out of that has profound things to say about math and is somehow related to the Halting problem. And trying to Google it doesn't help as I just get search result noise about the Halting problem itself with no reference to any special kinds of sequence.
      - Vecr 2y ago
        It's Ω / Chaitin's constant for a particular encoding. It's uncomputable as a whole, but maybe we will get a couple more bits.
        HappMacDonald 2y ago
        Alright then how does that help anyone with text compression, and/or how would computing it's digits reveal any deep secrets of mathematics?
abecedarius 2y ago
The point of the contest was not compression tech for communication and storage. It was a belief that minimizing log loss on large corpora (i.e. message length) was key to AI progress. That should remind you of some pretty hot more-recent developments. Here was someone else with a similar pov in the 2000s: https://danburfoot.net/research.html https://danburfoot.net/research.html
- optimalsolver 2y ago
  The issue with this paradigm (see also: Hutter Prize) was its insistence on lossless compression. Intelligence is just as much about knowing what to throw away as what to keep. Any nontrivial cognitive system operating in a nontrivial physical environment will necessarily have a lossy model of the world it's embedded in. Also of interest, compressionism, a theory of mind based on data compression: https://ceur-ws.org/Vol-1419/paper0045.pdf https://ceur-ws.org/Vol-1419/paper0045.pdf
  - theendisney 2y ago
    You could throw away 95% of enwiki without losing anything of value. This sounds like a joke but it would make the result worth reading which sounds like it is worth the exercise.
  - sfink 2y ago
    I tend to agree, but is that really a fatal flaw? A lossy compression scheme that gets it 90% right only has to encode the delta for the remaining 10%. Which is a big cost, sure, but the alternative is evaluating how important the thrown-away stuff is, and that evaluation is rife with subjective value judgements. There are no right answers, only differing flavors of wrong ones. It's the question of what is important to generalize over, and nobody is ever going to agree on that.
  - sdenton4 2y ago
    You can turn any lossy compression scheme into a lossless scheme by encoding the error... The lossy scheme should be aiming for low error, making the error encoding progressively smaller as the lossy scheme improves. What's harder to deal with from a measurement perspective is sematic equivalence. calling some kinds of errors zero-cost, but not having a great way to categorize what the loss of, exactly. But it's kinda what you want for really extreme compression: the content is equivalent at a high level, but may be a very different byte stream.
GaggiX 2y ago
Read: https://opus-codec.org/demo/opus-1.5/ https://opus-codec.org/demo/opus-1.5/
londons_explore 2y ago
Imagine if we didn't have dedicated hardware for say caching - every CPU instruction or bit of data has to be read from SSD every use. We'd see a 100,000x slowdown I expect. But dedicated hardware (RAM, various cache levels) solved this. We could do the same for neural net compression if we needed to. But the question is do enough people care enough about a 2x data size reduction?
- wmf 2y ago
  Dedicated hardware isn't magic because there's an intrinsic cost that cannot be reduced. In the case of neural nets you have to store the weights somewhere and you have to perform the multiplications.
geysersam 2y ago
Depends on the application! For long term storage of rarely accessed text it might make sense
ezekiel68 2y ago
This is a good point, and yet -- as high as position 24 (out of 208) in the list, we have "bsc-m03 0.4.0" at only ~160ns per byte compressed (compared with most above it being two or three orders of magnitude slower). Below position 24, there's one in the 20s of ns per byte. Looks like the cost was in the size of the compression program. Not sure if there was any "cheating" going on, hunting for benchmark scores with these two famous test bodies of text. By comparison, the top contender clocks in at ~240,000 ns per byte (making your point).
- wqweto 2y ago
  We use bsc and nanozip for archiving DB backups (usually 1-100GB files) and have not found anything remotely close to these as CPU usage vs compression ratio. c:> bsc.exe e "%~1" "%~1.bsc" -b1000 -m4e1t -M4H20 This uses 3GB of RAM and compresses w/ about 300MB/s but is slow on decompression while c:> nz.exe a -cd -p2 -m1024m "%~1.nz" "%~1" uses about 1GB of RAM and compresses w/ about 250MB/s to worse compression ratios but is much faster than bsc on decompression. Both of these smash zstd and 7-zip on compression and speed -- something like 2x better and 10x faster.

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.

jeffbee 2y ago

It does seem as though the training cost of these models ought to be included in their times, because the compressors are useless for any purpose other than compressing English Wikipedia.

gwern 2y ago
In these cases, the models are so small, and have to run on very limited CPU, that the training time is going to be fairly negligible. The top-listed program, nncp, is just 0.06b parameters! https://bellard.org/nncp/nncp_v2.pdf#page=4 https://bellard.org/nncp/nncp_v2.pdf#page=4
gliptic 2y ago
The training cost is included because these NN compressors are running the training while they are compressing. They are general compressors, although the specific variants submitted here may be tuned a little to Wikipedia (e.g. the pre-processors).

Xcelerate 2y ago

> unless there's some standard compression dictionary that works for everything There is, at least for anything worth compressing. It’s called the halting sequence. And while it exists, it’s also uncomputable unfortunately haha.

Vecr 2y ago
Apparently there's ways of getting the first few binary digits, but it's useless at that length.
- Xcelerate 2y ago
  Not useless. That’s most of mathematics right there.
  - HappMacDonald 2y ago
    What precisely are you lot referring to? I'm familiar with the Halting Problem, and glancingly familiar with Ω / Chaitin's constant(s). But I'm not familiar with any kind of uncomputable sequence which we know how to get the first few binary digits out of that has profound things to say about math and is somehow related to the Halting problem. And trying to Google it doesn't help as I just get search result noise about the Halting problem itself with no reference to any special kinds of sequence.
    - Vecr 2y ago
      It's Ω / Chaitin's constant for a particular encoding. It's uncomputable as a whole, but maybe we will get a couple more bits.
      - HappMacDonald 2y ago
        Alright then how does that help anyone with text compression, and/or how would computing it's digits reveal any deep secrets of mathematics?

abecedarius 2y ago

The point of the contest was not compression tech for communication and storage. It was a belief that minimizing log loss on large corpora (i.e. message length) was key to AI progress. That should remind you of some pretty hot more-recent developments. Here was someone else with a similar pov in the 2000s: https://danburfoot.net/research.html https://danburfoot.net/research.html

optimalsolver 2y ago
The issue with this paradigm (see also: Hutter Prize) was its insistence on lossless compression. Intelligence is just as much about knowing what to throw away as what to keep. Any nontrivial cognitive system operating in a nontrivial physical environment will necessarily have a lossy model of the world it's embedded in. Also of interest, compressionism, a theory of mind based on data compression: https://ceur-ws.org/Vol-1419/paper0045.pdf https://ceur-ws.org/Vol-1419/paper0045.pdf
- theendisney 2y ago
  You could throw away 95% of enwiki without losing anything of value. This sounds like a joke but it would make the result worth reading which sounds like it is worth the exercise.
- sfink 2y ago
  I tend to agree, but is that really a fatal flaw? A lossy compression scheme that gets it 90% right only has to encode the delta for the remaining 10%. Which is a big cost, sure, but the alternative is evaluating how important the thrown-away stuff is, and that evaluation is rife with subjective value judgements. There are no right answers, only differing flavors of wrong ones. It's the question of what is important to generalize over, and nobody is ever going to agree on that.
- sdenton4 2y ago
  You can turn any lossy compression scheme into a lossless scheme by encoding the error... The lossy scheme should be aiming for low error, making the error encoding progressively smaller as the lossy scheme improves. What's harder to deal with from a measurement perspective is sematic equivalence. calling some kinds of errors zero-cost, but not having a great way to categorize what the loss of, exactly. But it's kinda what you want for really extreme compression: the content is equivalent at a high level, but may be a very different byte stream.

GaggiX 2y ago

Read: https://opus-codec.org/demo/opus-1.5/ https://opus-codec.org/demo/opus-1.5/

londons_explore 2y ago

Imagine if we didn't have dedicated hardware for say caching - every CPU instruction or bit of data has to be read from SSD every use. We'd see a 100,000x slowdown I expect. But dedicated hardware (RAM, various cache levels) solved this. We could do the same for neural net compression if we needed to. But the question is do enough people care enough about a 2x data size reduction?

wmf 2y ago
Dedicated hardware isn't magic because there's an intrinsic cost that cannot be reduced. In the case of neural nets you have to store the weights somewhere and you have to perform the multiplications.

geysersam 2y ago

Depends on the application! For long term storage of rarely accessed text it might make sense

ezekiel68 2y ago

This is a good point, and yet -- as high as position 24 (out of 208) in the list, we have "bsc-m03 0.4.0" at only ~160ns per byte compressed (compared with most above it being two or three orders of magnitude slower). Below position 24, there's one in the 20s of ns per byte. Looks like the cost was in the size of the compression program. Not sure if there was any "cheating" going on, hunting for benchmark scores with these two famous test bodies of text. By comparison, the top contender clocks in at ~240,000 ns per byte (making your point).

wqweto 2y ago
We use bsc and nanozip for archiving DB backups (usually 1-100GB files) and have not found anything remotely close to these as CPU usage vs compression ratio. c:> bsc.exe e "%~1" "%~1.bsc" -b1000 -m4e1t -M4H20 This uses 3GB of RAM and compresses w/ about 300MB/s but is slow on decompression while c:> nz.exe a -cd -p2 -m1024m "%~1.nz" "%~1" uses about 1GB of RAM and compresses w/ about 250MB/s to worse compression ratios but is much faster than bsc on decompression. Both of these smash zstd and 7-zip on compression and speed -- something like 2x better and 10x faster.