Ts_zip: Text Compression Using Large Language Models
bellard.org
bellard.org
This is precisely because LLMs learn a representation of the nth-order Markov Chain, which by its nature is extraordinarily sparse. This allows for excellent compression, and I would assume (and have for a while, I suppose) the nearly-linear nature of LLMs allows for excellent interpolation between these very sparse states.
This lets us 'break' the hard-combinatorial problem into one that can be softly, albeit with the fuzzy error that comes with any estimator.
Since computers cannot tractably compress markov chains past a certain point, this allows LLMs some opportunity to outpace traditional methods for compression, at least in theory.
Also, this method technically cheats since you need the language model to decompress, which counts towards your dictionary size. In a truly unbounded case, I would be interested to see which method wins. I'm assuming it's the LLM.
Apologies for any factual inaccuracies or such, I am still learning many of these things. Many thanks and much love! <3 :))))
I think, perhaps, if inputs > outputs and there is some dimensionality reduction (though I think orthogonality would be a trait of an ideal system [i.e. an emergent property approached in the limit], not one that is explicitly enforced each step).
> The goal of the Hutter Prize is to encourage research in artificial intelligence (AI). The organizers believe that text compression and AI are equivalent problems. Hutter proved that the optimal behavior of a goal-seeking agent in an unknown but computable environment is to guess at each step that the environment is probably controlled by one of the shortest programs consistent with all interaction so far.
Similar to how metabolism in many ways is required for life, yet metabolism itself isn't life.
One of the challenges is that the minimum MDL (Minimum Descriptor Length -- https://en.wikipedia.org/wiki/Minimum_description_length) is intractable to prove directly, we can only prove that we are a bit closer to it than we were before. This of course becomes even more difficult in the temporal regime, as the amount of information to prove that an iterative mapping (i.e. a decision-making algorithm or what have you, in this case) over each time slice in a temporal system is nigh-impossible. We can tell _something_ about it because of the attractors generated by such a system, but even then, I think it's something basically impossible to do in a closed-form manner.
That being said, I do believe compression is required for intelligence, and that deliciously drags in all of the info theory stuff, which is very fun indeed. Just seems like it gets really messy with that time component, but that's just my 2 cents at least. :'(
I didn't know that was related to the Hutter Prize. Very cool. I'd read a little bit about that prize before, and I'll take another look at it now. Probably won't start any work on anything because I really, really, really do not want to Collatz Conjecture myself again.
"Must run in ≲50 hours using a single CPU core and <10GB RAM and <100GB HDD on our test machine." Which is an Intel Core i7-620M
For this, I'd look at comparable work in the audio codec space, including Lyra (https://arxiv.org/abs/2102.09660) and SoundStream (https://arxiv.org/abs/2107.03312).
For text compression, I think it would be novel if you could get a lossy but semantically equivalent decompression that was resilient to the exact hardware used for inference. I don't think that's what happened here, though, given the requirement for "exact same GPU and model".
He has also held the ‘world record’ for data compression since 2019 with nncp http://mattmahoney.net/dc/text.html#1085
Robert Metcalfe just won the award for Ethernet. Go scan through the list of Turing winners again. It is not just awarded to pure theorists. There’s a huge slant to academics who also found (or caused) massive commercial success, especially in recent years.
Bellard could get hit by a bus tomorrow and have
>the most important video tool ever
>the most important emulation tool ever
>the best text compression tool ever
…on his resume. And with those tools he’s not just wrapping algorithms cooked up by others, but also innovating on fundamental theory. VirtualBox and the Android emulator? That’s QEMU. Every video platform in existence? Thin wrappers to FFmpeg. Seems deserving to me, and certainly seems as or more impactful that many names on that winners list.
Or is it actly ok.
A summary is a form of lossy text compression, and it's extremely useful.
That's not what this is but if it can actually produce "semantically equivalent" decompressed text it's fascinating.
https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
>JBIG2 doesn't have scripting capabilities, but when combined with a vulnerability, it does have the ability to emulate circuits of arbitrary logic gates operating on arbitrary memory. So why not just use that to build your own computer architecture and script that!? That's exactly what this exploit does. Using over 70,000 segment commands defining logical bit operations, they define a small computer architecture with features such as registers and a full 64-bit adder and comparator which they use to search memory and perform arithmetic operations. It's not as fast as Javascript, but it's fundamentally computationally equivalent.
>The bootstrapping operations for the sandbox escape exploit are written to run on this logic circuit and the whole thing runs in this weird, emulated environment created out of a single decompression pass through a JBIG2 stream. It's pretty incredible, and at the same time, pretty terrifying.
Wow... that's really out of the box. They built their own VM from a JBIG compression stream vuln and wrote an exploit to run on it... Not bad.
NNCP: Lossless Data Compression with Neural Networks
https://news.ycombinator.com/item?id=27244004 (397 points | May 22, 2021 | 160 comments)
I try to compare with the results from the top 9 of this enwik8 compression test by Matt Mahoney: https://www.mattmahoney.net/dc/text.html
The durilca compressor by Dmitry Shkarin (what happened to him?) has been the fastest compressor in the top since it's debut in 2006.
The original size, enwik8, is 10^8 bytes. The compressed size is the compressend enwik8 plus the size of a zip archive containing the decompressor.
The bpb value of rwkv_430M on enwik8 is 0.948 bpb, the 7B models will be lower, perhaps around 0.800. So if my calculations are correct, the LLM's can perform 50% better then the best performing conventional compressors excluding the zipped LLM decompressor code (I am unsure about the size).
The bpb ratio for each existing program can be calculated as: bpb ratio=(Original size (enwik9)Total size (enwik9+prog) )×8
nncp v3.1: Given compressed size is not provided, we cannot calculate bpb for nncp v3.1 using enwik8.
cmix v19: bpb=(14,837,987+223,485108)×8bpb=(10814,837,987+223,485 )×8 bpb≈1.205
tensorflow-compress v4: bpb=(15,905,037+55,283108)×8bpb=(10815,905,037+55,283 )×8 bpb≈1.272
cmix-hp 10 Jun 2021: Given compressed size is not provided, we cannot calculate bpb for cmix-hp using enwik8.
fast-cmix: Given compressed size is not provided, we cannot calculate bpb for fast-cmix using enwik8.
starlit 31 May 2021: bpb=(15,215,107108)×8bpb=(10815,215,107 )×8 bpb≈1.217
phda9 1.8: bpb=(15,010,414+42,944108)×8bpb=(10815,010,414+42,944 )×8 bpb≈1.205
paq8px_v206fix1: bpb=(15,849,084+402,949108)×8bpb=(10815,849,084+402,949 )×8 bpb≈1.265
durilca'kingsize: bpb=(16,209,167+407,477108)×8bpb=(10816,209,167+407,477 )×8 bpb≈1.317
This is an unfair test, because the rwkv_430M model was almost certainly trained on wikipedia. Testing using training data is a big no-no in the ML world - you get unrealistically good results.
To test this properly, it needs to be run on a bit of newly written text which is nowhere on the internet. Obviously writing 100 MB of human written text which is not already on the internet is rather a big task...
If you were going to standardize on a foundational model that gets delivered to billions of devices to be used in network transfers (where you just transfer the compressed text and assume the other side already has the model), then it makes sense to optimize for generalizability. In that case it would make sense to exclude the model itself from the compressed size. Basically like how brotli gets to "cheat" by including a 120KB pre-defined dictionary.
Edit: Actually that can't be right. The numbers on https://www.mattmahoney.net/dc/text.html use that methodology, but the numbers in OP here can't be, since a zip compressed version of rwkv_430M is ~650 MB, so obviously it's not being included or Alice in Wonderland would have an abysmal ratio.
To know how the method performs on novel data, the authors have to come up with entirely new datasets, since anything already existing must be assumed probably contaminated.
The goal of compression, then, is to make common strings shorter while making uncommon strings longer. You can think of, say, UTF-8 as a simple compression algorithm: it would take 20 bits per character to encode all Unicode code points with a fixed-width encoding, but UTF-8 takes advantage of the fact that the most commonly used characters have a lot of leading zeroes (at least in English). So the characters of the English alphabet require only 8 bits to encode, but uncommon characters require up to 32 bits.
Thus, I would expect an LLM-based compression algorithm to do well on strings that were common in its training data, and make strings that were uncommon or absent slightly longer. If it did not do that, it would not be a lossless compression algorithm.
I'm saying more that if the compression algorithm is benchmarking against "Alice in Wonderland" and has consumed the entirety of "Alice in Wonderland" in training the LLM (along with popular paragraphs and sentences quoted elsewhere), then it might do particularly well at reciting lines from that book and thus be able to compress it extremely well. I'd be more interested in seeing the compression algorithm's performance on new or unreleased works that would have no way of being training data.
As an extreme hypothetical, I could make a compression algorithm that is a table mapping an ID to an entire book and fill it with all the popular works. "Alice in Wonderland" would be replaced with a single short identifier string and achieve a ~0.001% compression ratio. An unseen work would be replaced with an <unknown> ID followed by the entire work and be slightly bigger. Then, I benchmark only the popular works and show insanely impressive results!
I have no doubt the LLM compressor would do really well on unseen works based on what you said above, but it's not a fair look at its performance to run it on works it may have been explicitly trained on.
I think I'm missing a point here. Is it a provable fact that all lossless compression algorithms are neutral at best? Or just something that occurs in the real world?
I can't think of a good example, so I'll give a trivial example to explain my thinking.
It seems to me that you could have an algorithm which did not change any text, except the sentence "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo", which it encodes as something much shorter like "<Buffalo*8>". The algorithm would be (very marginally) better than neutral. If this is true, then surely other improvements would be possible to make a lossless algorithm with real reduction.
(Edited a typo)
This is due to the pigeonhole principle
It's a transformer that trains itself on the user's input and nothing else. The problem is that for the first N megabytes of input the compression ratio is going to be really bad because the model is only just starting to figure things out. Once you get a couple GB of training data things get much better. That's why in practice grabbing a pre-trained model is more practical.
"you will not go to space today"
> A brief note for the curious. "Lena" or "Lenna" is a digitized Buck centerfold. Lena Soderberg (nee Sjooblom) was be popped keep in her folk Sweden, well married and three boys and a an and the air grog lock. In 1988, she was seen by a Swedish computer akin tome, and she was fairly charmed by what had done to her art. That was the top she knew of the way of that oil in the computer job. The item in the January 1992 end of Optical Engineering (v. 31 no. 1) data how Buck has lastly caught at to the life that their claim on Lenna Sjooblom's slide is man bigly defied. It arms as if you wish get to nab grant from Stud to blaze it in the next.
Now, English is not my first language, but I can hardly grasp what this footnote is about. Is it due to my language barrier, or did the authors just applied their lossy compression method to this footnote?
Imagine you run a big email server for millions of users.
Any email that hasn't been accessed for a month is probably a good candidate for compressing with this method.
In the unlikely event the user wishes to read an old email again, I'm sure they won't mind waiting 0.1 seconds for 10 kilobytes of email (ie. a screenfull) to decompress.
You don't think "the same exact GPU model and program versions must be used for compression and decompression" rules it out as more than an interesting experiment, especially given that storage is cheap and continues to get cheaper?
Thats 400 kilobytes per second. And much of that is image attachments and stuff - perhaps only 10 kilobytes/second of text.
Maybe Google already does this?
LLMs are still being created and refined, token dictionaries are also changing. For this to work, you'd need something future proof, to avoid having and ultra efficiently compressed file that can never be opened because part of the decompressor is an extremely big and outdated data file that may or may not disappear from the most acessible sites for being heavy and obsolete.
That being said, if we ever make an "absolute" language model with a "definitive" dictionary or make a cheap and efficient way of grounding future models to make them "backwards compatible", this coould be used to preserve data for longevity. HDs and SSDs don't have the same durability of books, floppy discs can demagnetize, etc.
I think microsoft was working on a "true long term" storage medium using a crystal engraving technique to ensure the data could live for thousands of years and survive the elements. For that extreme case it might be useful.
In compression contest circles, there's long been this concept of "AI compression" (long before the current LLM wave), considered the upper limit of compression algorithms. This is based on the idea of the Dictionary... IIRC, some compression systems include the Dictionary as part of the decompressor, to save space in the payload, but then that Dictionary is fixed and may be suboptimal for the data. Others include it in the payload, so that it's optimal for the data, which most do.
But you could achieve incredible compression of, say, The Complete Works Of Shakespeare if you knew your peer knew about The Complete Works Of Shakespeare (had a rich enough dictionary) and just send them that designator of the payload! Or, you could send them a particular high-resolution picture of a wheat field with cypresses under a blue sky with an appropriately specific "description".
What Fabrice did is gone ahead and put this theoretical idea in practice. And that's hilarious.
This seems like a massive issue for actual use. Are there really not some workarounds to get deterministic output?
Compiler optimizations (and remember, GPU drivers each use their own compiler behind the scenes to translate to their actual hardware architecture) can alter rounding errors of each operation, and parallel execution - which differs from hardware to hardware - also affects it.
Some APIs (Cuda?) let you disable all optimizations and there are ways to get cross-platform determinism, but in general it's much much slower if you want bit-for-bit equality across different hardware.
SPIR-V/Vulkan for example[0] only define an error range based in ULP for some operations - not bit-for-bit equality.
[0] https://registry.khronos.org/vulkan/specs/1.2-extensions/htm...
Since this is not open-source, but seems simple to do, perhaps I'll make my own.
My potential issue with NNs for compression is that sometimes they predict near zero for some probabilities that actually occur in real data - in which case the number of bytes needed to encode would blow up. But that can be somewhat guarded against (perhaps by limiting the lower bound of output probabilities).
A quick experiment using a small selection of truncated texts yielded 1.8 bpb against alice29. I imagine other texts could do better.
This makes the whole approach really difficult to be useful in practice. Basically whenever you have a method that relies on 100% reproducible float numbers.
What are ways around that? Why do the quantized variants actually have the same problem?
Imagine the potential bandwidth savings. I bet this has applications as a modern "Dial-up accelerator" for people with slow connections and fast hardware.
Then if you want to decompress something that was archived 10 years ago you need to make sure you can find and install the old compression model.
The "(and hopefully decompress)" would usually make me think it was like when people would "compress" sequences into emoji using ChatGPT...but its bellard
I've been wondering this last year about the use case of compressing highly repetitive logs in a streaming fashion, and whether fine-tuning a model or combination of LLM / datastore might make a sort of adaptive online compression perform well (e.g. allowing central versioned coordination of compression steps/layers as they evolve)
In turn, that makes it far less interesting to me.
Especially since the majority of what he releases is more of a cool tech demo than a product in it's own right. A closed source tech demo really isn't of much use to anyone who doesn't have the source code to extend it.
But I stopped open sourcing some of my work when I got aggressive users demanding I support them for free. I realised I was pouring hours into triaging bugs, explaining why PR's weren't good enough, fixing other people's corner cases, and settling disputes, without really getting much back. Sure, my projects were getting a following and there were lots of happy users, but the actual benefit to me of that happening was negative.
One middle ground I used for a while was releasing my projects as a tar file only, not a git repo. Someone else can then make a git repo and maintain the project. Looks like Bellard did the same for some projects.
Q: Can I contribute?
A: Curio is not a community-based project seeking developers or maintainers. However, having it work reliably is important. If you've found a bug or have an idea for making it better, please file an issue.
Open Sourcing the tools lets others do their tasks. But you run the risk of becoming an unpaid toolmaker and unpaid tool maintainer, and getting none of your own tasks done.
In a way, github's biggest opensource committers are in a way the 'gig economy' workers of the tech world. Paid in just the occasional few bucks of donation for work which would otherwise be worth hundreds of thousands of dollars done with a salary.
Puzzled, he laid back down, but then he heard someone else yell out, "72!", followed by even more laughter.
"What's going on?" he asked his cellmate.
"Well, we've all heard every joke so many times, we've given them each a number to make it easier."
"Oh," he says, "can I try?"
"Sure, go ahead."
So, he yells out "102!" and the place goes nuts. People are whooping and laughing in a hysteria. He looks at his cellmate rolling on the ground laughing.
"Wow, good joke, huh?"
"Yeah! We ain't never heard that one before!"
So, he yells out "102!" and... Crickets.
"What'd I do wrong?"
"Ehh, you must not have told it right."
(...Or, in this case, "you're probably not using the right model GPU")
https://mattmahoney.net/dc/rationale.html
...which leads to the theory of mind known as "compressionism":
Zstd, while it might be better than gzip or bzip, is still a very poor compressor compared to an ideal compressor (which hasn't yet been discovered).
That is why zstd acts like a rather bad AI. Note that if you wanted to use zstd as an AI, you would patch out of the source code checksum checks, and you would then feed it a file to decompress (The cat sat on the mat), followed by a few bytes of random noise.
A great compressor would output: The cat sat on the mat. It was comfortable, so he then lay down to sleep.
A medium compressor would output: The cat sat on the mat. bat cat cat mat sat bat.
A terrible compressor would output: The cat sat on the mat. D7s"/r %we
See how each is using knowledge at different levels to generate a completion. Notice also how that few bytes generates different amounts of output depending on the compressors level of world understanding, and therefore compression ratio.
LLMs are sort of unable to do this because they use a fixed tokenizer instead of raw bytes. That means they won't output binary garbage even early on + saves a lot of memory, but it may hurt learning things like capitalization, rhyming, etc we think are obvious.
Intelligence _may arise_ from information. Information _necessarily arises_ from compression.
It is very similar, to me, to the concept of humors (https://en.wikipedia.org/wiki/Humorism). Empirically, it was observed that these things had some correlation, and they occurred together, but they are not directly causative. Similarly with the theory of spontaneous generation (https://en.wikipedia.org/wiki/Spontaneous_generation), which was another theory spawned (heh, as it were), from casual causal correlation (again, as it were).
This can be shown rather easily when you show that the time-dynamics of an exemplar system with high information diverge from the time dynamics of a system with high intelligence, i.e. there is a structural component to the information embedded in the system such that the temporal aspects of applied information are somehow necessary for intelligence.
I hope to release some work at least tangentially related to this within the next few years (though of course it is a bit more high-flying and depends on some other in-flight work). If we are to attempt to move towards AGI, I really think we need to stick with the mathematical basics. Neural networks, although they've been made out to be really complicated, are actually quite simple in terms of the concepts powering them, I believe. That's something I'm currently working on putting together and trying to distill to its essence. That will also be at least 1-2 years out, and likely before any temporally-related work, all going well. In my experience, this all is just a personal belief from a great deal of time and thought with the minutia of neural networks. That said, I could perhaps be biased with some notion of simplicity, since I've worked with them long enough for some concepts to feel comfortably second-nature.
To compress data, you have to derive some interesting insight about that data that allows the data to be projected into a lower-dimensional, lower-entropy embedding. (In pop-neurological terms, you have to "make a neuron" that represents a concept, so that you can re-phrase your dataset into a star-schema expressed in its connections to that concept.)
The more different kinds of things a single compressor can do that for — without the compressor itself being made larger — the more "intelligent" the compressor is, no?
Hence, the set vs superset argument.
Kolmogorov actually
Kolmogorov complexity is based directly off of Shannon's information theory. It's the definition of the shortest possible length of a program that can output a particular string.
It is an extension of information theory. If you just take either of the words 'Kolmogorov' or 'complexity' out of the phrase 'Kolmogorov complexity', it loses all meaning. We measure the programs for a given string against that string's Kolmogorov complexity by their entropy. Hence, why at the core, the very pith of the matter at hand is information, which is a measurable quantity. Additionally, K complexity is a lower bound, not a quantity.
This is a similar kind of swap to saying "No, those baked goods are not food, because goods == items bought and sold for currency", if this recontextualizes it a bit.
A highly advanced AI could compress the text and predict the next sequences easily.
This seems like a direct connection like electricity and magnetism.
And maybe that's why English needs to be about 1 bit because we're not very intelligent.
If I conclude from this that you mean that gzip is intelligent, will I be accused of bad faith?
As a direct refutation to what you're saying, I feel similarly about Jeff Dean at Google. His productivity is pretty legendary, and all of the stuff I know that he's done is private/proprietary (and very profitable) to Google.