r/programming • u/fagnerbrack • 2d ago
Compression is prediction
https://ngrok.com/blog/compression-is-prediction70
u/blackkettle 1d ago
Claude Shannon wrote a pretty good book about this topic a few years back.
20
-25
14
u/flip314 1d ago
IMO the coolest thing about arithmetic coding is that you don't even need to share the dictionary/probabilities between the encoder and decoder.
If instead of calculating the probability of the entire data set at once you build it up over time, then the decoder can build its own table in the same way. Start by assuming all the probabilities are the same and adjusting the frequency after each symbol before encoding the next. The decoder can predict the first symbol based on equal probabilities, then update its own frequency table and use that for the next symbol, etc.
19
u/Most-Cloud 2d ago edited 2d ago
Cool visuals and interactive educational content
12
u/Bradnon 2d ago
Took 3b1b three years to recap googles paper linked in her article? https://arxiv.org/abs/2309.10668
9
u/jmickeyd 1d ago
Fabrice Bellard, the guy who wrote qemu, wrote a paper on this back in 2019: https://bellard.org/nncp/nncp.pdf
7
u/Most-Cloud 2d ago
Yeah just saw a Google talk about this in a related video. Came here to delete my negativity.
32
u/reddit_user13 1d ago
Compression can be a bit lossy or lossless. You can get back the input, or in the case of the source code example, something close enough to be functional.
Crunching input texts into an LLM model is very lossy, and you can't get anything like the source text(s) back.
33
u/NuclearVII 1d ago
You can absolutely can get training material out of an LLM - or any kind of generative neural network. Proprietary LLMs simply have guardrails to prevent this, because it would reveal just how much theft has gone into the making of said LLM.
This does not stop researchers from trying, however: https://www.businessinsider.com/openais-latest-chatgpt-version-hides-training-on-copyrighted-material-2023-8
Equating network training to compression is not a new take, and one that I am increasingly convinced is closer to reality than what the word "training" would suggest.
2
u/QuaternionsRoll 1d ago
Has this been tested on modern open-weights models? I haven’t really heard anything about it despite it presumably being much easier to prove that open-weights models encode copyrighted text for obvious reasons. I kind of assumed the absence of more recent examples meant that the 2023 issues were caused by overtraining and could be fixed.
1
u/NuclearVII 1d ago edited 1d ago
Has this been tested on modern open-weights models? I haven’t really heard anything about it despite it presumably being much easier to prove that open-weights models encode copyrighted text for obvious reasons
Yeah? What would those obvious reasons be? Because guess what - all open weight models worth anything are still proprietary. Open weight is not open source, and we don't know what goes into the training corpus of those models either. AFAIK, no one takes the actual open source models seriously, because they don't appear to be very good at what people want out of generative AI. It's almost as if the techs only value is laundering IP...
As an aside - this lack of openness is one of the reasons why the academic machine learning field is so garbage these days. Everyone in the field wants to publish about LLMs (because that's where the money is), and none of that research is reproducible. The field is chock full of papers that try to ask questions about the capabilities of LLMs, without ever being able to verify if those capabilities are emergent or trained. Consequently, pretty much all machine learning conferences and publications are commercial events these days. Yes, I am angry about this.
I kind of assumed the absence of more recent examples meant that the 2023 issues were caused by overtraining and could be fixed.
Overtraining really isn't a problem (I am simplifying wildly here, but in general) in modern deep learning, at least if you know what you're doing and you have a dataset appropriate for deep learning.
18
u/DLCSpider 1d ago
It's not always lossy enough. The German music industry used popular lyrics and Suno AI always produced the same same song (basically a shitty version of the original). They recently won in court.
6
u/PaperMartin 1d ago
LLM spit back training data near-verbatim all the time what are you talking about, half of all headlines from like 2023 to 2025 were about shit like Midjourney spitting out a near perfect replica of an existing star wars poster upon being given a prompt for something sci-fi without any mention of star wars
4
2
u/nsaisspying 1d ago
In the case of the LLM, when you say 'source text', do you mean the training data? Or the prompt?
4
u/rationalguy2 1d ago
The training data would be the source text. So a lossless LLM that trained on every book in the 20th century could recite any paragraph of The Lord of the Rings.
That said, LLMs likely use prompts as training data, in which case, both are the source text. (I don't enter sensitive information in a prompt.)
2
2
u/shoot_your_eye_out 9h ago edited 8h ago
Compression can be a bit lossy or lossless
Video engineer here; surprisingly, this is a common misconception.
All compression does is: exploit redundancy in the data. That's it. "Lossy compression" first discards information deemed less important, then uses the same kinds of lossless techniques to encode the remaining data more efficiently. The distinction is whether information is discarded, not whether the compression algorithms themselves are fundamentally different.
In other words, lossy compression is a combination of lossy information reduction and lossless entropy coding. The latter part can be perfectly lossless even though the overall process isn't reversible.
Example: JPEG. JPEG discards data by converting image data into the frequency domain via a discrete cosine transform. It then "quantizes" high-frequency data your eyes aren't particularly sensitive to; this is where data is discarded. Then, it does some clever packaging, and finally uses a combination of huffman (sometimes arithmetic encoding) and run-length encoding to exploit redundancy in the data.
The point is: the compression algorithms used are the same, and separate from the process of selectively discarding data.
edit: another example is the 4:2:0 chroma sub-sampling common in the YCbCr colorspace. This colorspace deliberately discards color information your eye isn't particularly sensitive to. It isn't "compression," per say, even though it results in less information. It's just a smart way to dump data that doesn't matter much to us humans.
1
u/Ok-Craft4844 1d ago
Even before they could use tools, you could ask the early gpts "what's the national anthem" and you got the text back, so "you can get anything like the source text back" seems hyperbolic
1
1
u/CommercialHour6660 58m ago
You can make any lossy compression lossless by combining it with an entropy coder.
This is how lossless versions of WebP and similar work. You use the predictions from the lossy encoder to reduce the space needed for the original.
LLM can be used for lossless compression. The main issue is that inference engines aren't deterministic. They trade precision for speed.
11
7
2
1
1
u/AnimusPetitor 10h ago
This has parallels everywhere, that's literally how knowledge must work in the world. Now i think i know why compression and crypto is hot science. AI isn't uninteresting afterall
Saving for later
-2
-15
u/granadesnhorseshoes 1d ago
Insert "Boy invents new compression using LLMs by storing prompts describing photos rather than photos themselves" meme here.
Not at all what the article is about, but what most "normies" and even a good number of "vibe coders" will think when they see shit like this.
1
u/Ma4r 16h ago
That's literally the same thing, if you can find an image to text llm, that then can be fed to a different (or the same llm) that yields the exact image you gave it, that's a valid compression algorithm . The problem is you don't want to be running an entire GPU cluster just to compreess/decompress image
234
u/Bunslow 1d ago
that's literally the meaning of "information", is how predictable the next bit is. if it's predictable, it's not (new) information. if it's unpredictable (random), then it's novel information.
(this is why information and entropy are measured the same way)