Large Text Compression Benchmark
mattmahoney.net
mattmahoney.net
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).
- 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 )
- zstd v1.5.6 -22 --ultra: 213,893,168 bytes (~0.826% smaller)
Since zstd's format is fixed, I doubt there will be massive changes in compression ratio.
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.
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.
Here was someone else with a similar pov in the 2000s: https://danburfoot.net/research.html
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:
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.
>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.
Is basically saying
> What's harder is defining a reconstruction process in terms of a "semantic group" i.e. an output encoding and associated group actions under which the loss is invariant, and having the group actions express the concept of two non-identical outputs being"equivalent for the purposes of downstream processing".
Taco Cohen is one of the pioneers of this line of research, and invariant, equivariant and approximately iv/ev architectures are a big thing in scientific and small data ml
What loss is that, exactly?
One of the difficulties in speech processing is that we generally don't have a great model for speech quality or equivalence. The human hearing system is a finicky and particular beast, and furthermore varies from beast to beast, depending both on physiology and culture. Good measures (eg, Visqol, a learned speech quality metric) tend to be helpful for measuring progress when iterating on a single system, but can give strange results when comparing different systems.
So it 's easy to imagine (say) pushing the generated speech into some representation space and measuring nearness in that space (either absolute or modulo a group action), but it begs the question of whether nearness in that space really represents semantic equivalence, and how to go about constructing it in the first place.
Let alone why one would bother allowing some group symmetries into the representation when we plan to define a loss invariant under those symmetries... Throwing group theory at speech representations feels like a solution in search of a problem, as someone who has worked a lot with group theory and speech compression.
All the stuff you mentioned is true, but thinking about it in an abstract sense, that means there's a set of universal symmetries and a set of highly context depending symmetries, and group theory is afaik our best method of thinking about them rigorously - as I say in the child comment, not the end point, but our current best starting point (in my opinion)
Happy to discuss more via email as well
The question I'd raise is why the route that got traction used more ad-hoc regularization schemes instead of the (decompressor + compressed) length from this contest and the book I linked.
Sure, but you can see it as two steps. Decide what doesn't matter at all, and throw it away. Then compress the rest losslessly (according to how surprising it is, basically the only way)
I think a theory of mind based on data compression is backwards, for this reason. When you have "data", you've already decided what's important. Every time you combine "A" and "B" into a set, you have already decided
1. That they are similar in some way you care about
2. That they're distinct in some way you care about (otherwise, it would be the same element!)
... and you do this every time you even add two numbers, or do anything remotely more interesting with "data". There is no "data" without making a-scientific statements about what's important, what's interesting, what's meaningful, what matters etc.
There is, at least for anything worth compressing. It’s called the halting sequence. And while it exists, it’s also uncomputable unfortunately haha.
If you had H, you could optimally compress any non-random string of data of length n in O(n) time. The rough sketch of how you would do this is to create brute-force search programs and then instead of actually running them just look up whether they halt or not via the halting sequence. By chaining together a few of these μ-operator functions, you can build up the whole compressed string 1 bit at a time.
Since we only have a few bits of H, we can’t compress at that level of magic, but what we do have still represents everything computable that ZFC can describe, which for the most part includes every algorithm we use in daily life.
Huh? I'm not referring to Chaitin's constant; the first few digits of that aren't going to help with much. I'm referring specifically to the halting sequence H as I mentioned in my post. See Vitányi's "Kolmogorov's Structure Functions and Model Selection" or any of Levin's papers on algorithmic complexity. (Vitányi uses a definition for H where a program's input is the empty tape rather than itself, but this is mainly a difference in convention).
You can take a formal logical theory F (e.g., Q, PA, ZFC, ...) and since the proofs are recursively enumerable, iterate over all proofs equivalent to the statement "p_i halts" or "p_i never halts" in the language of F for program p_i (as indexed lexicographically on a reference universal Turing machine).
As an example, for any halting program p, an unbounded search through PA will eventually find a proof that p halts (assuming soundness of PA). But there are certain non-halting programs for which PA cannot prove the non-halting behavior whereas ZFC can. So in terms of mutual algorithmic information I(a : b) = K(a) + K(b) - K(a, b), PA's inability to prove the non-halting behavior of p implies I(p : PA) = 0 whereas I(p : ZFC) > 0 since ZFC can prove this. More specifically K(p) - K(p | ZFC) > 0, given that the description of ZFC is minimal.
The above implies that I(ZFC : H) > I(PA : H), where H is the halting sequence, so we can say that ZFC is "more powerful" than PA in its ability to prove non-halting behavior of Turing machines. But a minimal description of ZFC and PA is still a finite amount of information, and in fact Chaitin's Incompleteness theorem states that for any formal logical system F, there is a constant C_F beyond which F cannot prove any string has higher Kolmogorov complexity than C_F. I suspect C_F is pretty close to K(F), but I haven't seen a proof of that fact anywhere. This is essentially another way to state Gödel's first incompleteness theorem, with additional detail about the limit of what formal system F can or cannot do.
So when I was referring to the few binary digits that correspond to "most of mathematics", I'm talking about the I(ZFC : H) bits of mutual algorithmic information between ZFC and H. We know there is a 745 state binary Turing machine that encompasses all of ZFC’s behavior (see Scott Aaronson's posts about this), but many people think the minimal size of a machine that computes all that ZFC can prove about the behavior of Turing machines is far smaller than that.
By comparison, the top contender clocks in at ~240,000 ns per byte (making your point).
c:> bsc.exe e "%~1" "%~1.bsc" -b1000 -m4e1t -M4H20
c:> nz.exe a -cd -p2 -m1024m "%~1.nz" "%~1"
Both of these smash zstd and 7-zip on compression and speed -- something like 2x better and 10x faster.
Of course it could also just be a very large “classical” shared dictionary (zstd and brotli can work in that mode, for example).
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).
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.
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?
(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.)
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.
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.