[HN Gopher] Short Message Compression Using LLMs
___________________________________________________________________
Short Message Compression Using LLMs
Author : chunkles
Score : 140 points
Date : 2024-12-26 19:06 UTC (4 days ago)
(HTM) web link (bellard.org)
(TXT) w3m dump (bellard.org)
| kianN wrote:
| For 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/
| cyptus wrote:
| isn'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 wrote:
| Yeah 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 wrote:
| > ts_zip
|
| Discussed (once more) in a neighbor thread:
| https://news.ycombinator.com/item?id=42549083
| max_ wrote:
| Does this guy (Fabrice Bellard) have a podcast interview anyone
| would recommend?
| silisili wrote:
| AFAIK, 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 wrote:
| He seems to spend all time to write truly amazing software.
| antirez wrote:
| The 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 And so forth.
| Retr0id wrote:
| It'd be a fun experiment to try making it lossy.
|
| You could adjust tokens towards what's more statistically
| probable, and therefore more compressible (in your example,
| it'd be picking tomato instead of cheese)
| antirez wrote:
| Yep. For lossy what could work even better is an encoder-
| decoder model, so that it is possible to just save the
| embedding, and later the embedding will be turned back into
| the meaning.
| srush wrote:
| I've tried to build sort of model several times, but could
| never get it to work. The challenge is that small
| perturbations in encoder space lead to removing
| semantically important details (e.g. dates). You really
| want these to mess up syntax instead to get something more
| analogous to a lossy video encoder.
| antirez wrote:
| Yep, makes sense... Something like 20 years ago I
| experimented with encoder/decoder models for lossy images
| compression and it worked very well, but it's a
| completely different domain indeed, where there aren't
| single local concentration of entropy that messes with
| the whole result.
| lxgr wrote:
| I could see that as a plot point in a science fiction story:
| Intergalactic telegrams are prohibitively expensive, so
| before sending one you're offered various variants of your
| text that amount to the same thing but save data due to using
| more generic (per zeitgeist) language :)
|
| Compare also with commercial code [1], a close historical
| analog, albeit with handcrafted, as opposed to ML-derived,
| compression tables. (There was a single code point for
| "twins, born alive and well, one boy and one girl", for
| example! [2])
|
| [1] https://en.wikipedia.org/wiki/Commercial_code_(communicat
| ion...
|
| [2] https://archive.org/details/unicodeuniversa00unkngoog/
| duskwuff wrote:
| Comes up as a minor plot point in Vernor Vinge's _The
| Blabber_ (1988):
|
| > "And from your standpoint, Hamid, there's one big
| drawback. The mean bandwidth of this thing [ _an ansible,
| more or less_ ] is just under six bits per minute."
|
| > "Huh? Ten seconds to send a single bit?"
|
| > "Yup. Skandr left three protocols at the Lothlrimarre
| end: ASCII, a Hamming map to a subset of English, and an AI
| scheme that guesses what you'd say if you used more bits.
| The first is Skandr's idea of a joke, and I wouldn't trust
| the third more than wishful thinking."
|
| (Good advice at the end there.)
| dekhn wrote:
| A bit of an aside- in one of the sequels to A Fire Upon
| the Deep, somebody has to interpret some very lossy audio
| and video into the most likely explanation, but they are
| stuck with a stupider than usual AI and it misinterprets
| the results (it's implied if they had their full AI it
| would have gotten the interpretation correct even with
| the ambiguity). This episode in the book completely
| changed how I think about imputation under uncertainty.
| Often, I don't want a single high confidence prediction,
| I want a probability distribution of the most likely
| predictions, rank ordered.
| wat10000 wrote:
| _Fire_ has evocations, which are videos compressed down
| to something like just a description, then rendered at
| the receiving end in a way that hopefully has some
| resemblance to the original.
|
| One viewer stumbles onto a key insight about the struggle
| taking place, but they only have evocations so they're
| not sure. And they sound like a total kook so everyone
| ignores them.
| ai-christianson wrote:
| Seems like an ideal compression method for LoRa/Meshtastic-
| style communication. An LLM wouldn't run on an ESP32, but there
| are several that could run on a raspberry pi.
|
| It's not just natural language that could be compressed this
| way, either. Code (HTML, JS, etc) could be compressed with the
| same technique/models. I bet that the same general idea could
| work for image compression as well, using an image/diffusion
| model (or perhaps a multimodal model for everything.)
|
| This could lead to an entire internet of content using just a
| few bits.
| amelius wrote:
| This is very similar to how many compression schemes work. Look
| up Huffman coding to begin with.
|
| https://en.wikipedia.org/wiki/Huffman_coding
| nzach wrote:
| For anyone interested in this topic, Primeagen has a pretty
| great video on how he used several encoding schemes to save
| bandwidth in one of his projects.
|
| https://www.youtube.com/watch?v=3f9tbqSIm-E
| gliptic wrote:
| I'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 wrote:
| I 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 wrote:
| The 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."
| antirez wrote:
| Oh, that makes sense! So they use the probability of the
| next token itself. Thanks for clarifying. Also clever
| trick about the multiple potential tokens to represent
| the same text.
| gus_massa wrote:
| If you are going to zip the resulting file, it may be
| useful to have a lot of 0s.
|
| If you are going to send the result as is, Huffman coding
| (with some escape for unusal words(?)) will be better. I
| think even better than the other method that forgets the
| probabilities and then tries to compresd it.
| antirez wrote:
| Just to clarify: even storing ranking, here would likely
| produce good results, but not as good as storing the
| probability, since it exploits better the ability of
| arithmetic coding to store this fractional intervals. But
| here the fundamental trick is that the LLM can compress
| the "next in sequence" information in a distribution that
| is much better to compress than the initial data itself.
| gliptic wrote:
| This is especially true for instance when you have two or
| more tokens that are about equally likely, or one token
| that is virtually certain, which ranking would obscure.
| antirez wrote:
| Indeed.
| giovannibonetti wrote:
| Regarding 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#creati... [2]
| https://cloud.google.com/sql/docs/postgres/extensions
| brody_hamer wrote:
| I 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.
| Tostino wrote:
| TOAST compression is likely your best option for that data. You
| may need to lower the data size threshold for toast for that
| column.
| maccard wrote:
| I ended up with a similar problem. We replaced the data with a
| simple binary serialization format, gzip'ed that, and then
| base64 encoded the gzipped data. It's far from perfect but it
| was 250x saving in our case making it go from "stupidly large"
| to "we don't care" with an hours work.
| ianburrell wrote:
| Postgres supports toast (long record) compression. It seems to
| support enabling on columns. It looks like it supports LZ4 and
| Zstd now. Zstd has better compression at expense of more time.
| coder543 wrote:
| For compressing short (<100 bytes), repetitive strings, you
| could potentially train a zstd dictionary on your dataset, and
| then use that same dictionary for all rows. Of course, you'd
| want to disable several zstd defaults, like outputting the zstd
| header, since every single byte counts for short string
| compression.
| yalok wrote:
| What's the size of the model used here?
| GaggiX wrote:
| The model used is RWKV 169M v4.
| deadbabe wrote:
| Could this become an attack vector somehow? The greatest minds
| could probably find a way to get a malicious payload decompressed
| into the output.
| Retr0id wrote:
| It's lossless, at worst you'd make the compression ratio worse
| for certain inputs.
| deadbabe wrote:
| With LLM based compression, could we get something like the
| opposite of lossless, like hallucinatory? All the original
| content, plus more?
| Retr0id wrote:
| Not if the compression scheme is lossless, which it is
| here, per my previous comment.
| tshaddox wrote:
| Presuming 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 wrote:
| LLMs are deterministic at zero temperature.
| ychen306 wrote:
| How this works is the LLM predicts the probability of the
| next token and then an arithmetic coder turns that
| probability distribution into bits. So it will never
| hallucinate. In the worst case, when the LLM makes an
| outrageous prediction, you just use more bits, but it
| doesn't affect correctness.
| stabbles wrote:
| It's a bit confusing to show the output as multibyte utf-8
| characters and compare that to a base64 string
| Retr0id wrote:
| The comparison example uses base64 too
| stabbles wrote:
| Ah, my mistake. I thought that was meant to show a dictionary
| and brotli encoded string separately.
| Retr0id wrote:
| What's the throughput like, for both compression and
| decompression?
| tshaddox wrote:
| This 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
|
| 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 wrote:
| More 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 wrote:
| I 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 wrote:
| Not 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 wrote:
| Here's the submission that won the Hutter Prize in 2021:
| https://github.com/amargaritov/starlit It uses a LSTM to
| predict the next token lossily, then uses
| 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_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).
| willvarfar wrote:
| Yes, one way to think about arithmetic compression is
| encoding the difference between the prediction and
| reality.
|
| This isn't normally what people mean by lossy
| compression, though. In lossy compression (e.g.
| mainstream media compression like JPEG) you work out what
| the user doesn't value and throw it away.
| canjobear wrote:
| This is standard lossless compression. None of the
| concepts particular to lossy compression (like rate-
| distortion theory) are used.
| evertedsphere wrote:
| it's simpler: the hutter prize imposes a 110M constraint on the
| sum of the sizes of your program (including any data it needs
| to run) and the compressed data
|
| llms are generally large
| gliptic wrote:
| This could be circumvented by _training_ the LLM on the fly
| on the previously observed file data. This is what Bellard's
| other NN compressor, nncp, does [1], which is currently #1 on
| Mahoney's benchmark [2]. Unfortunately this is too slow,
| especially running on the CPU as Hutter's challenge
| stipulates IIRC.
|
| [1] https://bellard.org/nncp/
|
| [2] http://mattmahoney.net/dc/text.html
| willvarfar wrote:
| This compressor is by a certain Fabrice Bellard, an overactive
| overachiving powerhouse of a programmer who happens to be
| leading the Large Text Compression Benchmark
| https://www.mattmahoney.net/dc/text.html, which is maintained
| by Matt Mahoney who happens to run the Hutter Prize :)
|
| Fabrice also makes some programs you might use, like FFMEG and
| QEMU
|
| https://bellard.org/
| berbec wrote:
| > Fabrice also makes some programs you might use, like FFMEG
| and QEMU
|
| This would be the one sentence that wouldn't cause me to look
| down on somoene, if used as a third-person humble-brag.
| TacticalCoder wrote:
| > FFMEG
|
| For those unaware, it's a typo. willvarfar meant FFMPEG.
| mNovak wrote:
| I 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 wrote:
| At 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 wrote:
| That seems like a fun project to replicate independently. You
| didn't want to rebuild it?
| RandomThoughts3 wrote:
| It'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 wrote:
| If 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 wrote:
| If 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 wrote:
| Impressive!
|
| 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 wrote:
| What is this encoding scheme that produces Chinese characters
| from binary data? E.g. from the first example:
|
| > _myulgYao Shao Pu Ju Shao _
|
| I've never seen that before. The base64 below it, in contrast, is
| quite familiar.
| lxgr wrote:
| There'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
|
| 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
| mlok wrote:
| LLMs, 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
| bongodongobob wrote:
| I view it as a form of fraud. There's no way that worked or
| could have worked.
| mlok wrote:
| Yes 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 wrote:
| Perhaps 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).
| slater wrote:
| i 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?
| j_juggernaut wrote:
| Made a quick and dirt streamlit app to play around encrypt
| decrypt https://llmencryptdecrypt-
| euyfofcjh8bf2utuha2zox.streamlit.a...
| jonplackett wrote:
| Would 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!
___________________________________________________________________
(page generated 2024-12-30 23:00 UTC)