7 ms·
Short Message Compression Using LLMs
- kianN 2y agoFor those wondering how it works: > The language model predicts the probabilities of the next token. An arithmetic coder then encodes the next token according to the probabilities. [1] It’s also mentioned that the model is configured to be deterministic, which is how I would guess the decompression is able to map a set of token likelihoods to the original token? [1] https://bellard.org/ts_zip/ https://bellard.org/ts_zip/
- cyptus 2y agoisn’t a LLM itself basically a compression of the texts from the internet? you can download the model and decompress the (larger) content with compute power (lossy)
- kianN 2y agoYeah that’s exactly how I think of llms in my head: lossy compression that interpolates in order to fill in gaps. Hallucination is simply interpolation error. Which is guaranteed in lossy compression.
- kvemkon 2y ago> ts_zip Discussed (once more) in a neighbor thread: https://news.ycombinator.com/item?id=42549083 https://news.ycombinator.com/item?id=42549083
- max_ 2y agoDoes this guy (Fabrice Bellard) have a podcast interview anyone would recommend?
- silisili 2y agoAFAIK, he doesn't do videos or interviews. His web presence is pretty sparse. I remember trying to dig something up last year and coming up blank. Totally respect that, but a bummer for folks hoping to get a peek inside his mind. If nothing else, I hope he finds time to write his thoughts into a book at some point.
- usr1106 2y agoHe seems to spend all time to write truly amazing software.
- antirez 2y agoThe way this works is awesome. If I understand correctly, it's like that, given (part of) a sentence, the next token really in the sequence will be one predicted by the model among the top scoring ones, so most next tokens can be mapped to very low numbers (0 if the actual next token it's the best token in the LLM prediction, 1 if it is the second best, ...). This small numbers can be encoded very efficiently using trivial old techniques. And boom: done. So for instance: > In my pasta I put a lot of [cheese] LLM top N tokens for "In my pasta I put a lot of" will be [0:tomato, 1:cheese, 2:oil] The real next token is "cheese" so I'll store "1". Well, this is neat, but also very computationally expensive :D So for my small ESP32 LoRa devices I used this: https://github.com/antirez/smaz2 https://github.com/antirez/smaz2 And so forth.
- gliptic 2y agoI'm pretty sure it doesn't use ranking. That leaves a lot of performance on the table. Instead you would use the actual predicted token probabilities and arithmetic coding.
- antirez 2y agoI supposed it used arithmetic coding with the ranking bacause they have a distribution easy to exploit: zero more likely, one a bit less and so forth. What's your guess? Unfortunately Bellard is as smart as hermetic. We are here guessing what should be a README file.
- gliptic 2y agoThe model gives you a probability distribution over the tokens. You could use that directly with arithmetic coding, but there are ways to convert that to a distribution over e.g. the next byte instead which would improve efficiency further by removing the redundancy in alternative token encodings. ts_zip does this, and README says this works similar to ts_zip. EDIT: Hm, or maybe ts_zip uses just the token probabilities directly. I thought it was slightly more efficient about it. "The language model predicts the probabilities of the next token. An arithmetic coder then encodes the next token according to the probabilities."
- giovannibonetti 2y agoRegarding lossless text compression, does anyone know how a simple way to compress repetitive JSON(B) data in a regular Postgres table? Ideally I would use columnar compression [1], but I'm limited to the extensions supported by Google Cloud SQL [2]. Since my JSON(B) data is fairly repetitive, my bet would be to store some sort of JSON schema in a parent table. I'm storing the response body from a API call to a third-party API, so normalizing it by hand is probably out of the question. I wonder if Avro can be helpful for storing the JSON schema. Even if I had to create custom PL/SQL functions for my top 10 JSON schemas it would be ok, since the data is growing very quickly and I imagine it could be compressed at least 10x compared to regular JSON or JSONB columns. [1] https://github.com/citusdata/citus?tab=readme-ov-file#creating-tables-with-columnar-storage https://github.com/citusdata/citus?tab=readme-ov-file#creati... [2] https://cloud.google.com/sql/docs/postgres/extensions https://cloud.google.com/sql/docs/postgres/extensions
- brody_hamer 2y agoI haven’t played around with it too much myself, but I remember reading that gzip (or at least python’s compatible zlib library) supports a “seed dictionary” of expected fragments”. I gather that you’d supply the same “seed” during both compression and decompression, and this would reduce the amount of information embedded into the compressed result.
- duskwuff 2y agoMany other compression libraries, like zstd, support functionality along those lines. For that matter, brotli's big party trick is having a built-in dictionary, tuned for web content. It's easy to implement in LZ-style compressors - it amounts to injecting the dictionary as context, as if it had been previously output by the decompressor. (There's a striking parallel to how LLM prompting works.)
- Tostino 2y agoTOAST compression is likely your best option for that data. You may need to lower the data size threshold for toast for that column.
- 2y ago
- yalok 2y agoWhat’s the size of the model used here?
- GaggiX 2y agoThe model used is RWKV 169M v4.
- deadbabe 2y agoCould this become an attack vector somehow? The greatest minds could probably find a way to get a malicious payload decompressed into the output.
- Retr0id 2y agoIt's lossless, at worst you'd make the compression ratio worse for certain inputs.
- deadbabe 2y agoWith LLM based compression, could we get something like the opposite of lossless, like hallucinatory? All the original content, plus more?
- Retr0id 2y agoNot if the compression scheme is lossless, which it is here, per my previous comment.
- tshaddox 2y agoPresuming the software is implemented correctly, that can't happen (per the definition of "lossless"). I can imagine this happening with a careless implementation, e.g. if circumstances conspire to allow a slightly different version or configuration of the LLM to be used across compression and decompression.
- semiquaver 2y agoLLMs are deterministic at zero temperature.
- gloflo 2y agoDeterministically lossy/hallucinatory.
- deleted 2y ago
- stabbles 2y agoIt's a bit confusing to show the output as multibyte utf-8 characters and compare that to a base64 string
- Retr0id 2y agoWhat's the throughput like, for both compression and decompression?
- tshaddox 2y agoThis is obviously relevant to the Hutter Prize, which is intended to incentivize AI research by awarding cash to people who can losslessly compress a large English text corpus: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize From a cursory web search it doesn't appear that LLMs have been useful for this particular challenge, presumably because the challenge imposes rather strict size, CPU, and memory constraints.
- vlovich123 2y agoMore because lossy compression is what's been analogized to intelligence and this prize is doing a sleight of hand to insert lossless compression as if that doesn't make a difference. That's more why LLMs aren't really all that useful.
- tshaddox 2y agoI wouldn't call that a sleight of hand. Surely better lossy compression can be trivially used to implement better lossless compression, and the latter is just much easier to quantify for a benchmark.
- vlovich123 2y agoNot a single lossless compression technique I’m aware of starts of in lossy compression. They have different goals and utilize completely different techniques. At most lossy techniques leverage lossless techniques (eg to compress non-perceptual binary headers) not the other way round.
- leijurv 2y agoHere's the submission that won the Hutter Prize in 2021: https://github.com/amargaritov/starlit https://github.com/amargaritov/starlit It uses a LSTM to predict the next token lossily, then uses https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding to convert that to lossless compression. Lossless compression can definitely leverage a lossy compressor, such as via arithmetic coding. Also see: https://en.wikipedia.org/wiki/Context-adaptive_binary_arithmetic_coding https://en.wikipedia.org/wiki/Context-adaptive_binary_arithm... which has a simple "Example" section - imagine if the top prediction made by your neural network was correct, you emit "0", if the 2nd was correct, you emit "10", if the 3rd, "110", if the 4th, "1110". As you can see, this is lossless, but the fundamental prediction is lossy, and the better that prediction is, the better the compression. (In actuality, you wouldn't waste your 1 bits like this, you'd use arithmetic coding instead).
- mNovak 2y agoI recall someone using one of the image generation models for pretty impressive (lossy) compression as well -- I wonder if AI data compression/inflation will be a viable concept in the future; the cost of inference right now is high, but it feels similar to the way cryptographic functions were more expensive before they got universal hardware acceleration.
- hangonhn 2y agoAt a startup where I worked many years ago, they trained a model to take the image and screen size as the input and it would output the JPG compression level to use so that the image appears the same to people. It worked exceedingly well that a major software company offered to acquire the startup just for that. Alas, the founders were too ambitious/greedy and said no. It all burned down.
- kevmo314 2y agoThat seems like a fun project to replicate independently. You didn't want to rebuild it?
- RandomThoughts3 2y agoIt’s a very clever idea. I could see it becoming very useful if on device LLM becomes a thing. That might allow storing a lot of original sources for not much additional data. We might be able to get an on device chat bot sending you to a copy of Wikipedia/reference material all stored on device and working fully offline.
- lxgr 2y agoIf you like that idea, give Kiwix a try! Best ~60 GB I have stored on my phone :) And it comes in handy more often than initially expected.
- zamadatix 2y agoIf mobile phone conversations over the last 2 decades have taught me anything it's that people talk about anything but battery life and ultimately the crowd ends up doing "whatever means I don't have to put it on the charger twice a day". Especially when the base iPhone SE already has enough storage to fit more text than one could read in their life anyways.
- lxgr 2y agoImpressive! I wonder if this is at all similar to what Apple uses for their satellite iMessage/SMS service, as that's a domain where it's probably worth spending significant compute on both sides to shave off even a single byte to transmit.
- crazygringo 2y agoWhat is this encoding scheme that produces Chinese characters from binary data? E.g. from the first example: > 뮭䅰㼦覞㻪紹陠聚牊 I've never seen that before. The base64 below it, in contrast, is quite familiar.
- lxgr 2y agoThere's a family of encodings optimized for fitting the most information possible into an Unicode string of a given length, e.g. for gimmicks like fitting the most possible binary data into tweets. For example: https://github.com/qntm/base65536 https://github.com/qntm/base65536 For short messages in the mobile phone (i.e. GSM/3GPP) sense, which was my first association for "short message compression", it doubt that it works better than just sending binary messages with the appropriate header, but if that's not an option, it might just beat a custom alphabet based on the 7-bit GSM charset [1] (since that allows 100% of possible 7-bit characters to be used, whereas UTF-16 probably has at least some reserved codepoints that might be causing problems). [1] https://en.wikipedia.org/wiki/GSM_03.38 https://en.wikipedia.org/wiki/GSM_03.38
- mlok 2y agoLLMs, and now this, make me think of the (non-existant) "Sloot Digital Coding System" that could be viewed as a form of "compression". https://en.m.wikipedia.org/wiki/Sloot_Digital_Coding_System https://en.m.wikipedia.org/wiki/Sloot_Digital_Coding_System
- bongodongobob 2y agoI view it as a form of fraud. There's no way that worked or could have worked.
- mlok 2y agoYes that is why I specified it was non-existent. But the idea behind it is in the same vein somehow. Maybe what Sloot envisioned was something similar to LLMs.
- dekhn 2y agoPerhaps not literally, but you can easily imagine training an embedding on a large amount of existing video, and then delivering somebody "the point in space that decodes to the video with the least residual compared to the original". Conceptually, most modern movies are just linear combinations of basis tropes (tvtropes.org).
- perching_aix 2y agoI thought I had come up with something with a similar performance once. Then a couple hours later I realized that I just (still) suck at combinatorics :)
- deleted 2y ago[deleted]
- slater 2y agoi always wondered if e.g. telcos had special short codes for stuff people often send, like at xmas many people write "merry christmas" in an SMS, and the telco just sends out "[code:mx]" to all recipient phones, to save on bandwidth and disk space?
- qingcharles 2y agoNo, the systems are not that sophisticated, from having worked on them in the past.
- deleted 2y ago[deleted]
- j_juggernaut 2y agoMade a quick and dirt streamlit app to play around encrypt decrypt https://llmencryptdecrypt-euyfofcjh8bf2utuha2zox.streamlit.app/ https://llmencryptdecrypt-euyfofcjh8bf2utuha2zox.streamlit.a...
- jonplackett 2y agoWould this also work for video encoding using something like Sora? Get Sora to guess the next frame and then correct any parts that are wrong? I mean, it would be an absolutely insane waste of power, but maybe one day it’ll make sense!
- tdiff 2y agoHow is llm here better than Markov chains created from a corpus of English text? I guess similar idea must have been explored million times in traditional compression studies.
- userbinator 2y agoThe download is 153MB, compressed... didn't even bother to wait for it to finish once I saw the size. The brotli comparison is IMHO slightly misleading. Yes, it "embeds a dictionary to optimize the compression of small messages", but that dictionary is a few orders of magnitude smaller than the embedded "dictionary" which is the LLM in ts_sms. There's a reason the Hutter Prize (and the demoscene) counts the whole data necessary to reproduce its output. In other words, ts_sms took around 18 bytes + ~152MB while brotli took around 70 bytes + ~128KB (approximately size of its dictionary and decompressor.)
- f33d5173 2y agoYou can compress arbitrarily many messages with it, and the dictionary remains 153MB. Why it's worth pointing out that brotli already uses a dictionary is that otherwise it would be generating the dictionary as it compressed, meaning that short messages would be pessimized. So brotli is in some sense the state of the art for short messages.
- theamk 2y agoLife is more than that competitions? For example, antirez mentioned LoRa in the earlier thread - that's a cheap, license-free radio, which achieves a large range at the expense of low rate (250 bit/sec). That's 30 bytes/second, not including framing overhead and retransmission. If you wanted to build a communication system out of those, this compression method would be great. You'd have LORA device that connects to a regular cell phone and provides connectivity, and all the compression/decompression and UI happens on the cell phone. 150MB is nothing for modern phones, but you'd see a real improvement in message speed.
- SeptiumMMX 2y agoThe practical use for this could be satellite messaging (e.g. InReach) where a message is limited to ~160 characters, and costs about a dollar per message.
- the5avage 2y agoIs there a paper explaining it in more detail? I also saw on his website he has a similar algorithm for audio compression...
- deleted 2y ago[deleted]
- MPSimmons 2y agoCool, now all I need is the tiny encoded message and a 7+B weight model, plus some electricity. This is more like a book cipher than a compression algorithm.
- gcr 2y agoDecoding random gibberish into semantically meaningful sentences is fascinating. It's really fun to see what happens when you feed the model keysmash! Each part of the input space seems highly semantically meaningful. Here's a few decompressions of short strings (in base64): $ ./ts_sms.exe d -F base64 sAbC Functional improvements of the wva $ ./ts_sms.exe d -F base64 aBcDefGh In the Case of Detained Van Vliet {# $ ./ts_sms.exe d -F base64 yolo9000 Give the best tendering $ ./ts_sms.exe d -F base64 elonMuskSuckss= As a result, there are safety mandates on radium-based medical devices $ ./ts_sms.exe d -F base64 trump4Prezident= Order Fostering Actions Supported in May In our yellow $ ./ts_sms.exe d -F base64 harris4Prezident= Colleges Beto O'Rourke voted with Cher ¡La $ ./ts_sms.exe d -F base64 obama4Prezident= 2018 AFC Champions League activity televised live on Telegram: $ ./ts_sms.exe d -F base64 hunter2= All contact and birthday parties $ ./ts_sms.exe d -F base64 'correctHorseBatteryStaples=' --- author: - Stefano Vezzalini - Paolo Di Rio - Petros Maev - Chris Copi - Andreas Smit bibliography: $ ./ts_sms.exe d -F base64 'https//news/ycombinator/com/item/id/42517035' Allergen-specific Tregs or Treg used in cancer immunotherapy. Tregs are a critical feature of immunotherapies for cancer. Our previous studies indicated a role of Tregs in multiple cancers such as breast, liver, prostate, lung, renal and pancreatitis. Ten years ago, most clinical studies were positi ve, and zero percent response rates $ ./ts_sms.exe d -F base64 'helloWorld=' US Internal Revenue Service (IRS) seized $1.6 billion worth of bitcoin and In terms of compressions, set phrases are pretty short: $ ./ts_sms.exe c -F base64 'I love you' G5eY $ ./ts_sms.exe c -F base64 'Happy Birthday' 6C+g Common mutations lead to much shorter output than uncommon mutations / typos, as expected: $ ./ts_sms.exe c -F base64 'one in the hand is worth two in the bush' Y+ox+lmtc++G $ ./ts_sms.exe c -F base64 'One in the hand is worth two in the bush' kC4Y5cUJgL3s $ ./ts_sms.exe c -F base64 'One in the hand is worth two in the bush.' kC4Y5cUJgL3b $ ./ts_sms.exe c -F base64 'One in the hand .is worth two in the bush.' kC4Y5c+urSDmrod4 Note that the correct version of this idiom is a couple bits shorter: $ ./ts_sms.exe c -F base64 'A bird in the hand is worth two in the bush.' ERdNZC0WYw== Slight corruptions at different points lead to wildly different (but meaningful) output: $ ./ts_sms.exe d -F base64 FRdNZC0WYw== Dionis Ellison Dionis Ellison is an American film director, $ ./ts_sms.exe d -F base64 ERcNZC0WYw== A preliminary assessment of an endodontic periapical fluor $ ./ts_sms.exe d -F base64 ERdNYC0WYw== A bird in the hand and love of the divine $ ./ts_sms.exe d -F base64 ERdNZC1WYw== A bird in the hand is worth thinking about $ ./ts_sms.exe d -F base64 ERdNZD0WYw== A bird in the hand is nearly as big as the human body $ ./ts_sms.exe d -F base64 ERdNZC0wYw== A bird in the hand is worth something! Friday $ ./ts_sms.exe d -F base64 ERdNZC0XYw== A bird in the hand is worth two studies