11 ms·
Ts_zip: Text Compression Using Large Language Models
- freedmand 3y agoWas it run on any text that was not feasibly training data for the LLMs? It wouldn't be a fair comparison otherwise
- thomasahle 3y agoExactly. This is id always a pitfall when benchmarking LLM based techniques. The enwiki8 dataset they use, for example, is for sure in the training data. 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.
- makapuf 3y agoBut doesn't the size in benchmarks include the size of the binary decoder ? So the embedded trained data is accounted for (preventing a plain copy of wikipedia to be included in the decoder)
- loeg 3y agoI don't think the compressed size statistics on this webpage include the size of the LLM needed to decode. Some of these inputs are only a few 100 kB -- LLMs absolutely dwarf that.
- NobodyNada 3y agoEvery lossless “compression” algorithm makes some strings shorter and other strings longer, such that the average space savings against all possible strings is neutral at best. This is a fundamental consequence of the way information works — there’s no way to losslessly map (say) 8 bits of input into 7 bits of output. 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.
- freedmand 3y agoI don't disagree with anything you said. 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.
- ant6n 3y agoWell, unless the weights are part of the compressed file.
- NobodyNada 3y agoGotcha, sorry I completely misunderstood what you were asking! That’s a really insightful question that didn’t cross my mind at all.
- red369 3y ago>Every lossless “compression” algorithm makes some strings shorter and other strings longer, such that the average space savings against all possible strings is neutral at best. This is a fundamental consequence of the way information works — there’s no way to losslessly map (say) 8 bits of input into 7 bits of output. 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)
- hnfong 3y agoA similar project by Bellard is https://bellard.org/nncp/ https://bellard.org/nncp/ 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.
- jandrese 3y agoI guess they've worked out to always get exactly the same text back? Hopefully this won't be a repeat of the photocopiers that used a similar compression technique and occasionally substituted letters in the copy. https://www.bbc.com/news/technology-23588202 https://www.bbc.com/news/technology-23588202
- wmf 3y agoYeah, using a probabilistic predictor to do lossless compression has been known for a few decades.
- stevefan1999 3y agohttps://en.m.wikipedia.org/wiki/Arithmetic_coding https://en.m.wikipedia.org/wiki/Arithmetic_coding
- cbhl 3y agoThe author, Fabrice Bellard, is well-known for his work on QEMU (among other things), but I'd treat the rest of the posts as "idea sharing" at an early stage. For example, while BPG (Better Portable Graphics) didn't take off, the core idea (image formats based on video codecs) can be found in WebP (VP8, VP9) and AVIF (AV1) and HEIF (HEVC/H.265). For this, I'd look at comparable work in the audio codec space, including Lyra (https://arxiv.org/abs/2102.09660 https://arxiv.org/abs/2102.09660) and SoundStream (https://arxiv.org/abs/2107.03312 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".
- wood_spirit 3y agoFabrice is also well known for creating Ffmpeg and discovering an algorithm for computing digits of PI https://en.m.wikipedia.org/wiki/Fabrice_Bellard https://en.m.wikipedia.org/wiki/Fabrice_Bellard He has also held the ‘world record’ for data compression since 2019 with nncp http://mattmahoney.net/dc/text.html#1085 http://mattmahoney.net/dc/text.html#1085
- optimalsolver 3y agoReminder that compression = intelligence: https://mattmahoney.net/dc/rationale.html https://mattmahoney.net/dc/rationale.html ...which leads to the theory of mind known as "compressionism": https://ceur-ws.org/Vol-1419/paper0045.pdf https://ceur-ws.org/Vol-1419/paper0045.pdf
- ks2048 3y agoI would say compression and intelligence are closely related, not equal. For example, zstd is a pretty good compressor, but does any one think it should be called a pretty good “AI”?
- dragonwriter 3y agoWasn't there a paper recently about a fairly simple wrapper around a common conpression algorithm beating LLMs on classification tasks?
- jmholla 3y agoI thought that was about LLMs being trained on compressed data. But I might be thinking about a different paper.
- dragonwriter 3y agoGzip + kNN for text classification: https://aclanthology.org/2023.findings-acl.426.pdf https://aclanthology.org/2023.findings-acl.426.pdf
- junipertea 3y agoNot LLM, just BERT, also did not actually outperform it. source: https://kenschutte.com/gzip-knn-paper/ https://kenschutte.com/gzip-knn-paper/
- willis936 3y agoSomeone in sales with a product that uses zstd.
- leumassuehtam 3y agoInteresting application for the RWKV family of models.
- ivzhh 3y agoWhen I first read about RWKV on zhihu and the author said Bellard was working with him on RWKV. I am so glad ts_zip is out and bring a new application to RWKV.
- londons_explore 3y agoThere are plenty of usecases for very slow and very good text compression. 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.
- otabdeveloper4 3y agoOld email needs to be indexed for search, and those indexes might be as large as the original text.
- CharlesW 3y ago> Any email that hasn't been accessed for a month is probably a good candidate for compressing with this method. 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?
- londons_explore 3y agoI think they mean the exact same model data (for the GPU). I don't think it requires the exact same model of GPU.
- CharlesW 3y agoI’m also reading it as "the same exact GPU [LLM] and program versions must be used for compression and decompression".
- eklitzke 3y agoAs soon as someone uses a POP or IMAP client to fetch all of their mail your server is going to catch on fire. Even if you had POP/IMAP disabled, the computation costs to decode data are enormous with this method, which is precisely why people don't use the most maximally compressing codecs for anything other than true archival applications (e.g. database backups which, unlike old email, really are expected to be accessed almost never).
- ttoinou 3y agoAren't the LLM supposed to have "seen" those text corpus before ? I would expect that a very small prompt could generate the whole requested text
- refulgentis 3y agoIntriguing promise, but I can't find technical details or source, only binary exectuables. Anyone else have luck? The "(and hopefully decompress)" would usually make me think it was like when people would "compress" sequences into emoji using ChatGPT...but its bellard
- MaximilianEmel 3y ago"The same exact GPU model ... must be used for compression and decompression." This seems like a massive issue for actual use. Are there really not some workarounds to get deterministic output?
- slimsag 3y agoUnfortunately GPUs (and even CPUs' SIMD) floating point math is riddled with cross-platform determinism issues; hardware manufacturers intentionally trade that in order to get faster math operations in general, because although behavior of floating point is defined in IEEE 754, you get rounding errors for each operation. 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/html/vkspec.html#spirvenv-precision-operation https://registry.khronos.org/vulkan/specs/1.2-extensions/htm...
- johndough 3y agoReproducible results across GPUs are theoretically possible, but it would take some effort to implement and be slower. At least the primitive operations (addition, multiplication, etc.) are there: https://docs.nvidia.com/cuda/floating-point/index.html https://docs.nvidia.com/cuda/floating-point/index.html
- Firadeoclus 3y agoOne way to get deterministic output is to use integer/fixed point math. Quantised models already do that for matrix multiplication, but things like softmax may still be implemented using some floating point math. It's possible to replace that, just takes a bit of extra work and is probably slower than using the GPU's native float ops.
- albertzeyer 3y ago> The same exact GPU model and program versions must be used for compression and decompression. 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?
- AceJohnny2 3y agoThis is hilarious. 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.
- sterlind 3y agoNotably, I think this would fail on the Wikipedia compression contest because that counts the size of the decompression program (model in this case), so that it measures Kolmogorov complexity. And RWKV is surely too big. A neat thing to think about though, and maybe a winning idea if a more space-efficient model can be found.
- deleted 3y ago[deleted]
- tysam_and 3y agoThe reason this works is because LLMs are trained to minimize the empirical risk over a large set of data (https://en.wikipedia.org/wiki/Empirical_risk_minimization https://en.wikipedia.org/wiki/Empirical_risk_minimization), and it is where the log-likelihood-based measure comes from, oftentimes represented simply as the perplexity. 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 :))))
- blovescoffee 3y agoIf you want to learn something cool and related, checkout Autoencoders (or VAEs). They effectively compress information by forming representations of some data.
- tysam_and 3y agoIndeed. They are extremely cool! <3 :) I think in a way, every neural network works on compression! Though AEs & VAEs are a bit more blatant in how they do it. It's just always turned around a little, here and there. I have a pet theory that no neural network can work without compression (even generative ones that have constantly increasing layer depths! :D :)))) )
- nerdponx 3y agoIn a very loose sense, even plain linear regression is a form of lossy compression in the form of an orthogonal projection.
- londons_explore 3y agoBellard still does great work... But no longer releases anything opensource. 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.
- DSingularity 3y agoWhy did he stop?
- londons_explore 3y agoI can't speak for him... 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.
- dakotasmith 3y agoI recently came across Curio (https://github.com/dabeaz/curio https://github.com/dabeaz/curio) & really appreciated their FAQ section on contributing. I plan to use it in any future open source 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.
- londons_explore 3y agoCode is a tool. Often you build a tool to complete a task. 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.
- elil17 3y agoIdea: lossy text compression, where the LLM replaces unlikely words with likelier synonyms.
- GaggiX 3y agoThis is actually a very interesting idea, I hope someone would implement it and how. Would be fun to read the same text with stronger and stronger lossy compression.
- dekhn 3y agoup-goer five: explained using only the ten hundred words people use the most often
- ant6n 3y agoCarried to us by the Podcaster of Phd comics!
- davidzweig 3y agoOh, this would be super neat for (our) language learning chatbot.. restricting the vocab the model uses.. if someone knows how this can be done. :)
- ducktective 3y agoMan fears AGI, AGI fears Fabrice Bellard.
- deleted 3y ago[deleted]
- optimalsolver 3y agoWoman inherits the Earth.
- sterlind 3y agoHow does this work? I know that LLMs predict the log-likelihood of the next token in a sequence.. so I guess you initialize the LLM from scratch, say that each token of the input text is the Nth most likely possibility, and record what N is for that token? And then you do some combination of run-length encoding and Huffman trees or something to record the Ns? Since this is not open-source, but seems simple to do, perhaps I'll make my own.
- Scene_Cast2 3y agoA slightly more elegant method would be to throw an arithmetic coder on the output vector (normalized and represented as an interval) and record the interval represented by the real token to be compressed. This would allow for better compression ratios than your approach, I think (due to arbitrary probability support). 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).
- fsiefken 3y agoImpressive! But an order of a magnitude slower then non-LLM compression techniques. 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 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
- londons_explore 3y ago> The bpb value of rwkv_430M on enwik8 is 0.948 bpb 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...
- etiam 3y agoNewly declassified material maybe? Or just newly digitized?
- hn_throwaway_99 3y agoMy hope is that one day I'll be reincarnated and the new me will produce 1/1000 of the output of Fabrice Bellard. Whenever I see new posts from him I just think "How can he do so much?"
- dekhn 3y agoThe SI unit for productivity is measured in millibellards
- deleted 3y ago[deleted]
- quickthrower2 3y agoBecause we believe in "I did this this big thing X, that computer scientists love, which is public" > "I worked on a team and contributed to big thing Y, which is profitable but meh, and is private"
- hn_throwaway_99 3y agoNot at all. I'm just in awe about the sheer amount of incredible code that Bellard is able to produce. 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.
- lwneal 3y agoA man goes to prison, and the first night while he's laying in bed, he hears someone yell out, "44!", followed by laughter from the other prisoners. 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!"
- deleted 3y ago[deleted]
- redsaz 3y agoI've not heard that version before, I like it. The way I usually hear it end: 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")
- TheMiddleMan 3y agoIs it reasonable to imagine a future where most devices come with a, say, 500MB file used for decompressing? Imagine the potential bandwidth savings. I bet this has applications as a modern "Dial-up accelerator" for people with slow connections and fast hardware.
- landgenoot 3y agoAnd could you use that file to compress itself?
- Vecr 3y agoIt's a bunch of weights, it's not really compressible. Obviously you can't decode the model without the model so it's useless as well.
- ilaksh 3y agoIt seems likely that to me we will eventually start using AI models for compression and decompression of text, images, 3d models, programs, video, and streaming. AI has the potential for much higher compression. It's actually quite feasible for most PCs and laptops to keep in memory multiple GBs models. And the typical PC game is dozens of GBs.
- Turskarama 3y agoYou run into a problem where the model needs to be exactly the same on both ends. If your model is a couple of MB then updating it on occasion is no problem, but if it's several GB then you DO have a problem. 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.
- dmillar 3y agoZstandard (zstd), with a properly trained dictionary, could do well against larger (than alice29) texts. I doubt you'd see ~0.4 bpb, but 1-1.5 seems achievable. And it would be ~100% accurate with no GPU or other overhead necessary. A quick experiment using a small selection of truncated texts yielded 1.8 bpb against alice29. I imagine other texts could do better.
- spiritplumber 3y agoI wrote a dictionary compression type thing a while ago, should I post it somewhere?
- bcjordan 3y agoI'd be curious to check it out! 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)
- spiritplumber 3y agohttps://github.com/RbtsEvrwhr-Riley/CellSol https://github.com/RbtsEvrwhr-Riley/CellSol here ya go it's on my SO's github
- luke-stanley 3y agoI'm curious how cmix 19 compares to rwkv_169M (the LLM with the fastest compression speed and also low GPU memory use), since cmix 19 still had a better compression ratio at the moment. Anyone know?
- asicsp 3y agoSee also: https://bellard.org/nncp/ https://bellard.org/nncp/ NNCP: Lossless Data Compression with Neural Networks https://news.ycombinator.com/item?id=27244004 https://news.ycombinator.com/item?id=27244004 (397 points | May 22, 2021 | 160 comments)
- N0YS 3y agoHere is a very basic attempt at implementation of the method idea in Python, successfully compressing and de-compressing a file without any neural weights available: https://github.com/Magnushhoie/weightless_NN_decompression https://github.com/Magnushhoie/weightless_NN_decompression
- ouraf 3y agoRight now it's more of an idea to keep on the back of your head than anything else. 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.
- scott-smith_us 3y agoIs there significantly more to this than just tokenizing a document's words and then ZIP-ing the stream of tokens?