7 ms·
Fabrice Bellard's TS Zip (2024)
- publicdebates 9mo agoBellard finally working with his true colleague.
- dmitrygr 9mo ago"compressed size" does not seem to include the size of the model and the code to run it. According to the rules of Large Text Compression Benchmark, total size of those must be counted, otherwise a 0-byte "compressed" file with a decompressor containing the plaintext would win.
- underdeserver 9mo agoTechnically correct, but a better benchmark would be a known compressor with an unknown set of inputs (that come from a real-world population, e.g. coherent English text).
- eru 9mo agoYes, definitely. Alas, it's just harder to run these kinds of challenges completely fairly and self-administered, than the ones where you have a fixed texts as the challenge and add the binary size of the decompressor.
- paufernandez 9mo agoYeah, but the xz algorithm is also not counted in the bytes... Here the "program" is the LLM, much like your brain remembers things by coding them compressed and then reconstructs them. It is a different type of compression: compression by "understanding", which requires the whole corpus of possible inputs in some representation. The comparison is not fair to classical algorithms yet that's how you can compress a lot more (given a particular language): by having a model of it.
- wrs 9mo ago“Compressors are ranked by the compressed size of enwik9 (10^9 bytes) plus the size of a zip archive containing the decompresser.” [0] [0] https://www.mattmahoney.net/dc/text.html https://www.mattmahoney.net/dc/text.html
- deleted 9mo ago[deleted]
- FartyMcFarter 9mo agoTrue for competitions, but if your compression algorithm is general purpose then this matters less (within reason - no one wants to lug around a 1TB compression program).
- MisterTea 9mo agoThis is something I have been curious about in terms of how an LLM's achieves compression. I would like to know what deviations are in the output as this almost feels like a game of telephone where each re-compression results in a loss of data which is then incorrectly reconstructed. Sort of like misremembering a story and as you tell it over time the details change slightly.
- Scaevolus 9mo agoWhen LLMs predict the next token, they actually produce a distribution of the probability of each of the possible next tokens, and the sampler chooses one of them, and not necessarily the most likely one! If instead you run LLM prediction and then encode the probability of the next token of the input text you want to encode (from the cumulative distribution, a number in [0, 1]) using arithmetic coding, you can run the same operation in reverse to achieve lossless compression. The tricky part is ensuring that your LLM executes absolutely deterministically, because you need to make sure that the encoder and decoder have the same probability distribution map at each step.
- AnotherGoodName 9mo agoYes. The secret is in understanding arithmetic coding. https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding Arithmetic coding takes a prediction of the next bit and writes out exactly as many bits as needed to correct that prediction. The amazing part is that you can write out fractional bits. Eg. You predict the next bit is '1' with 75% probability? If it is 1 you only need to write out 1/2 of a bit (correcting that 25% portion). If it's 0 you need to write out 2.4bits. It may seem strange to work with 1/2 a bit but it works! (essentially the other half of the bit represents other future correction required). You might have heard of huffman coding which can't deal with fractional bits, arithmetic coding is a generalization of huffman coding that can deal with this. Arithmetic coding is mathematically perfect at what it does. You will not waste a single bit using this algorithm to encode data given a prediction of that data. So the entirety of modern compression techniques don't deal with the encoding/decoding side at all. What they deal with is modelling the data so far and making the most accurate prediction possible on the next bit of data (next byte also works, but working 1 bit at a time is easier to comprehend when learning arithmetic coding). Incidentally the encoders and decoders essentially work exactly the same. Given the data read or data decoded so far predict the next bit. This part is exactly the same either way. The decoder would read the compressed file for the correction and the encoder would read the input file and write out the correction. The important part is "predict the next bit". This is what separates all the different compressors. This is also where those of us experienced in this area try to correct people on the wrong track. A compression algorithm is never about the encoding side but instead 100% always about the prediction of the data. Can you build a model that can accurately predict what the next data to come is? That's what you need to do to make a better file compressor. The entropy encoding part is a completely solved problem already, don't bother re-solving that.
- wewewedxfgdf 9mo ago>> The ts_zip utility can compress (and hopefully decompress) text files Hopefully :-)
- hamandcheese 9mo agoReading data is overrated. I highly recommend S4: http://www.supersimplestorageservice.com/ http://www.supersimplestorageservice.com/
- deleted 9mo ago[deleted]
- fcantournet 9mo agoIt's particularly well suited for backups
- benatkin 9mo agoI propose the name tokables for the compressed data produced by this. A play on tokens and how wild it is.
- fancyswimtime 9mo agoplease pass the tokables to the left hand side
- shawnz 9mo agoAnother fun application of combining LLMs with arithmetic coding is steganography. Here's a project I worked on a while back which effectively uses the opposite technique of what's being done here, to construct a steganographic transformation: https://github.com/shawnz/textcoder https://github.com/shawnz/textcoder
- akoboldfrying 9mo agoCool! It creates very plausible encodings. > The Llama tokenizer used in this project sometimes permits multiple possible tokenizations for a given string. Not having tokens be a prefix code is thoroughly unfortunate. Do the Llama team consider it a bug? I don't see how to rectify the situation without a full retrain, sadly.
- shawnz 9mo agoI can't imagine they consider it a bug, it is a common and beneficial property of essentially every LLM today. You want to be able to represent common words with single tokens for efficiency, but at the same time you still need to be able to represent prefixes of those words in the cases where they occur separately
- akoboldfrying 9mo agoI find this surprising, but I suppose it must be more efficient overall. Presumably parsing text into tokens is done in some deterministic way. If it is done by greedily taking the longest-matching prefix that is a token, then when generating text it should be possible to "enrich" tokens that are prefixes of other tokens with additional constraints to force a unique parse: E.g., if "e" is a token but "en" is too, then after generating "e" you must never generate a token that begins with "n". A text generated this way can be deterministically parsed by the greedy parser. Alternatively, it would suffice to restrict to a subset of tokens that are a prefix code. This would be simpler, but with lower coding efficiency.
- shawnz 9mo ago
- deleted 9mo ago[deleted]
- meisel 9mo agoLooks like it beats everything in the large text compression benchmark for enwik8, but loses to several programs for enwik9. I wonder why that is.
- AnotherGoodName 9mo agoIt's actually not the best at enwik8 or 9. The results at https://www.mattmahoney.net/dc/text.html https://www.mattmahoney.net/dc/text.html explicitly add the size of the compressor itself to the result. Note the "enwik9+prog" column. That's what it's ranked on. The reason to do this is that it's trivial to create a compressor that 'compresses' a file to 0 bytes. Just have an executable with a dictionary of enwik9 that writes that out given any input. So we always measure what is effectively the Kolmogorov complexity. The data+program as a whole that produces the result we want. So those results add in the compressor size. The programs there generally have no dictionary built in or in the case of LLM based compressors, no pre-trained data. They effectively build the model as they process data. Not compressing much at all at the start and slowly compressing better and better as they go. This is why these programs do better and better with larger data sets. They start with 0 knowledge. After a GB or so they have very good knowledge of the corpus of human language. This program here however is pre-trained and shipped with a model. It's 150MB in size! This means it has 150MB of extra starting knowledge over those models in that list. The top models in that list are the better compressors, they'll quickly out learn and overtake this compressor but they just don't have that headstart. Of course measuring fairly this should be listed with that 150MB program size added to the results when doing a comparison.
- srcreigh 9mo agoAs an aside, I wonder how to account for the information content embedded in the hardware itself. A Turing Machine compressor program would likely have more bytes than the amd64 binary. So how to evaluate KolmogorovComplexity(amd64)? The laws of physics somehow need to be accounted for too, probably.
- d_burfoot 9mo ago
- rurban 9mo agoSo did beat his own leading program from 2019, nncp, finally.
- egl2020 9mo agoWhen Jeff Dean gets stuck, he asks Bellard for help...
- ok_dad 9mo agoJeff Dean uses Fabrice Bellard as a rubber duck for debugging, and vice versa. Amazingly, neither says a thing for several minutes, staring into each other's eyes, and then they just start typing the solution to the problem on a single keyboard together.
- jl6 9mo agoShannon approaches the Bellard limit.
- SnowProblem 9mo agoI love this because it gets to the heart of information theory. Shannon's foundational insight was that information is surprise. A random sequence is incompressible by definition. But what counts as surprise depends on context, and for text, we know a large amount of it is predictable slop. I suspect there's a lot of room to go along this style of compression. For example, maybe you could store an upfront summary that makes prediction more accurate. Or perhaps you could encode larger sequences or some kind of hierarchical encoding. But this is great.
- bambax 9mo agoYes! information is surprise, and that's why a measure of intelligence is the ability to predict.
- oxag3n 9mo agoCompression and intelligence reminded me of the https://www.hutter1.net/prize https://www.hutter1.net/prize I've encountered it >10 years ago and it felt novel that compression is related to intelligence and even AGI.
- eru 9mo agoYes. When you train your neural network to minimise cross-entropy that's literally the same as making it better as a building block in an arithmetic coding data compressor. See https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding See also https://learnandburn.ai/p/an-elegant-equivalence-between-llms https://learnandburn.ai/p/an-elegant-equivalence-between-llm...
- senderista 9mo agoIndeed, KL-divergence can be seen as the difference between the average number of bits required to arithmetically encode a sample from a given distribution, using symbol probabilities from both the original distribution and an approximating distribution. https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_divergence https://en.wikipedia.org/wiki/Kullback%E2%80%93Leibler_diver...
- omoikane 9mo agoCurrent leader of the Large Text Compression Benchmark is NNCP (compression using neural networks), also by Fabrice Bellard: https://bellard.org/nncp/ https://bellard.org/nncp/ Also, nncp-2024-06-05.tar.gz is just 1180969 bytes, unlike ts_zip-2024-03-02.tar.gz (159228453 bytes, which is bigger than uncompressed enwiki8).
- smusamashah 9mo agoDoesn't this fit the Hutter Prize conditions that is mentioned in other comment here https://news.ycombinator.com/item?id=46595109 https://news.ycombinator.com/item?id=46595109
- WithinReason 9mo agoIt's too slow for that. The Hutter prize is CPU only so neural network solutions (which are the most interesting IMO) are effectively excluded. You need to generate 11 574 characters per second on the CPU only for decompression, and the compression time also counts and has to be below 24 hours in total.
- cztomsik 9mo agoIIRC all the cmix submissions are using NN (and were for long time)
- WithinReason 9mo agowell yes, small LSTMs I think, which is far from LLM territory
- wiz21c 9mo agowhile impressive, it's a very specific case of compression: english text. It may be in use in many places but there are many more things to compress. It'd be nice to have a comparison here: https://morotti.github.io/lzbench-web/?dataset=silesia/sao&machine=desktop https://morotti.github.io/lzbench-web/?dataset=silesia/sao&m...
- gmuslera 9mo agoReminded me of pi filesystem (https://github.com/philipl/pifs https://github.com/philipl/pifs), with enough digits of pi precalculated you might be able to do a decent compression program. The trick is in the amount of reasonable digits for that, if it’s smaller or bigger than that trained LLM.
- GuB-42 9mo agoI suspect that the length of the offset of your input data in pi is equal to the length of the input data itself, plus or minus a few bytes at most, regardless of the size of the input data. That is: no compression, but it won't make things worse either. Unless the input data is the digits of pi, obviously, or the result of some computation involving pi.
- MrLeap 9mo agoYou could express the offset with scientific notation, tetration, and other big math number things. You probably don't need the whole offset number all at once!
- GuB-42 9mo agoActually, you do. You can use all the math stuff like scientific notation, tetration, etc... but it won't help you make things smaller. Math notation is a form of compression. 10^9 is 1000000000, compressed. But the offset into pi is effectively a random number, and you can't compress random numbers no matter what technique you use, including math notation. This can be formalized and mathematically proven. The only thing wrong here is that pi is not a random number, but unless you are dealing with circles, it looks a lot like it, so while unproven, I think it is a reasonable shortcut.
- noctune 9mo agoSome patterns must happen to repeat, so I would assume the offset to be larger, no?
- gmuslera 9mo ago
- jokoon 9mo agoso barely 2 or 3 times better than xz not really worth it
- amelius 9mo agoI didn't think about it much but I'm surprised it gives only a 50% reduction wrt normal compression.
- bob1029 9mo agoPPMd is the most exotic compressor I've actually used in production. The first time I saw it in action I thought it was lossy or something was broken. I had never seen structured text compress that well.
- voidUpdate 9mo ago> The ts_zip utility can compress (and hopefully decompress) Ah yes, write-only memory
- sylware 9mo agoMaybe one day, for some data to compress, "AGI" with a semantic understanding of this data, will be able to write some this-very-data-to-compress specific code predictor and to generate the related compressed data stream (lossless and why not lossy). :P
- sylware 9mo agoIs that emoticon not explicit enough to tag irony and jokes? (well, "AGI" is still not a thing though, if ever).
- nailer 9mo agoSilly queston: what does the 'ts' stand for?
- nilstycho 9mo agoI believe it's "TextSynth". https://bellard.org/ts_server/ https://bellard.org/ts_server/