Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- Small world. I just did a podcast on this same topic, but coming at it from a different direction, ie. me and my neighbor trying to beat the hutter prize for compression.
Hutter Prize being where you are paid if you can compress wikipedia small enough. LLMs do very well at that, if, big if, you ignore the cost of initial weights.
A cool Claude Shannon story:
Sounds a lot like next token prediction to me.Shannon wanted to measure how much information is actually contained in ordinary English text. His 1948 theory said such a number must exist, but he had no way to calculate it, because the patterns in English reach across dozens of letters and no equation or frequency table captures all of them at once. So instead of calculating it, he ran an experiment on a person. He took a passage from a novel that the subject had not read, and covered it with a card so only the text already guessed was visible. He asked the subject to name the first letter. If the guess was wrong, he asked again, and kept asking until the subject named the correct letter. He wrote down how many guesses it had taken, revealed the letter, and moved the card one position to the right. Then he repeated the process for the next letter, and the next, through the whole passage. What this produced was not a sequence of letters but a sequence of numbers — one number per letter, recording how many guesses that letter required. Most of the numbers were 1, because someone fluent in English, seeing the preceding text, usually names the next letter correctly on the first attempt. Shannon then argued that this sequence of numbers contains exactly as much information as the original passage.https://corecursive.com/the-hutter-prize/
- > ignore the cost of initial weights
Well, then Wikipedia itself is a very good compression that only needs the title to perfectly predict the full article.
by JohnKemeny - This is a lot less surprising when you learn how non-LZ compressors work, that is, by modeling a probability distribution and using those probabilities to encode information in the minimum number of bits required to transmit the data. A less obvious conclusion is that LZ compressors do this to implicitly, the length of each symbol they could emit (literal or match, etc.) can be converted to the probability distribution the LZ compressor induces, since the number of bits to encode the symbol is related to its probability by the information content.by variadix
- A common design in compressors is to use LZ as a first step, but to then represent the constant data and/or offset-length pairs from LZ using an entropy coder.
Deflate (as used in gzip) uses a Huffman coder. LZMA (as used by xz) uses a predictive range coder. Zstandard can use either Huffman or FSE. Some high-speed compressors like LZ4 skip the entropy coding stage entirely at the expense of compression ratio.
Bzip2 is an interesting aversion of this pattern - it uses the Burrows-Wheeler transform as a first pass instead of LZ. Unfortunately, this is one of the major reasons why it's so slow.
by duskwuff - Prediction is compression, but I am not sure if it is true the other way around.
It's obvious that an accurate predictor enables encoding only the data that the predictor gets wrong.
But a compressor can encode patterns that defy prediction by looking at the data as a whole. It doesn't have to look at everything in sequence as it arrives.
Applying transformations prior to entropy encoding often isn't just 'rearranging into an easier to compresss format' the transformation can be doing the job of peeking into the future. That makes the encoding a whole lot easier, but it is much harder to call it prediction.
by Lerc - Indeed. If you're going for a catchy generalization, at least write it correctly. Most compression is history, and only extrapolates under the assumption that "nothing changes".by tgv
- https://arxiv.org/abs/2311.08768
>Three Conjectures on Unexpectedeness
>Unexpectedness is a central concept in Simplicity Theory, a theory of cognition relating various inferential processes to the computation of Kolmogorov complexities, rather than probabilities. Its predictive power has been confirmed by several experiments with human subjects, yet its theoretical basis remains largely unexplored: why does it work? This paper lays the groundwork for three theoretical conjectures. First, unexpectedness can be seen as a generalization of Bayes' rule. Second, the frequentist core of unexpectedness can be connected to the function of tracking ergodic properties of the world. Third, unexpectedness can be seen as constituent of various measures of divergence between the entropy of the world (environment) and the variety of the observer (system).
by Xmd5a - This perspective is a useful source of intuition against the “LLMs can’t have new ideas, they’re just next-token-predictors” style arguments. What if you shift your perspective to thinking of training as optimization over a vast parametrized family of compression algorithms? Well, it suddenly looks a lot more plausible that “new” “ideas” can emerge from that process!
- Incidentally, the relationship is bidirectional. You can try it out just for fun. zstd is a pretty crappy language model :)
- Prediction is literally what's allowed computers to make amazingly creative chess and go moves that a human would never have thought of.
More generally prediction allows you to path find towards a solution to reach some goal that no human might ever see.
If someone states "LLMs can't have new ideas because they only predict" you have to laugh. Prediction literally enables new ideas as you use those predictions to path find to a goal.
- There's another element to this that I almost never see discussed. Ideas are not facts. Neither LLMs nor humans can generate new knowledge, as opposed to ideas, by thinking alone. Physical investigation and experimentation is necessary.
The exception being pure mathematics since it exists solely in the realm of ideas. I'm willing to call that knowledge, but it's still a distinction, the old analytic/synthetic dichotomy of Kant.
by nonameiguess - > it suddenly looks a lot more plausible that “new” “ideas” can emerge from that process
This is not intuitive to me. It seems like a "new idea" is something that (almost by definition) isn't in the training set. Can you elaborate a bit?
Edit: but perhaps a good model could arise from training, which would be a good idea in the sense that parsimonious ideas are good scientific ideas.
by glial - Consider:
If you want to record the motion of the planets, naively you have large tables of positions.
To compress that, you may smoothly interpolate sparse positions.
To compress that, you encode the laws of gravity and simulate from a starting state.
Compression is literally understanding.
by qarl2 - Nice one.
Yes. Compression constitutes necessary conditions for understanding. But don't forget recomposition as well.
Add recursion to the mix and it results in recursive compression and recomposition - making understanding itself a self existing entity.
This is as close to an understanding god you can rigorously get to.
by elendilm - There is Compression done by Prediction by partial matching [0]
There is the Kolmogorov Complexity [1], Normalized Information Distance [2] and Normalized compression distance [3] that correlates those.
Finally, there's the Pre-Big Bang Informational Compression and the Delayed Release of Antimatter [4]
All big {rabbit/black} holes to lose some time, if you have any.
[0] https://en.wikipedia.org/wiki/Prediction_by_partial_matching
[1] https://en.wikipedia.org/wiki/Kolmogorov_complexity
[2] https://homepages.cwi.nl/~paulv/papers/chapter08.pdf
[3] https://en.wikipedia.org/wiki/Normalized_compression_distanc...
by woliveirajr - This is exactly why I think they are one and the same. It's relatively trivial to just plop a (lossy) machine learned markov chain instead of one learned (perfectly) from the data into PPM. With zero changes to the rest of the algorithm.by vrighter
- by Xmd5a
- I'll add Minimum Description Length to the mix. Under certain definitions and conditions, it equals the Bayesian Information Criterion plus an extra term, which I consider a very interesting result in this "two faces of the same coin" perspective.by brumar
- Nope; there is a bit more nuance and the distinction is important.
Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems. The story changes drastically if you want generalization -- because the test distribution could be arbitrarily different, even if it had the same support! Eg: you observe a rare edge case in your training data and (lossy) compression could simply ignore it. But if you wanted generalization in that particular part of the space -- either because an adversary was testing you, or for design freedom where you choose to build in that specific corner -- then you don't just want data compression, but good prediction performance on a test distribution which peaks in that corner.
Assuming that the training data distribution is exactly the distribution you will ever care for is implicitly doing a lot of the heavy lifting in the claim that compression = prediction, and I'm peeved at how much this statement is unthinkingly repeated like a manifesto.
There is nothing natural about the training data distribution, especially if the data generation process is exploratory while the downstream usage will be exploitative.
by ssivark - I'd approach this distinction differently. Prediction from compression is valid within the distribution of the compressed data. Which brings it much closer to LLMs in this case (can an LLM talk about a topic it has never seen in training? unlikely if it cannot be derived from other training data)by omneity
- > because the test distribution could be arbitrarily different,
In that case all bets are off for all machine learning algorithms anyway. If the changes are not arbitrarily different then some of the lost performance can be recovered.
You talk about generalization a lot, but perhaps you are not aware that the technical term is defined under the assumption that test and train distribution are the same.
by srean - Compression is still prediction, the predictions just might not be good.by canjobear
- The record setting file compressors are all very generalizable. This comes about because you score compression by adding the program size (including any training data or dictionary) to the compressed data. If they didn't score it this way you could just ship a dictionary of the test data and your program just prints that. So of course they combine it and effectively measure the Kolmorogov complexity.
This means that training data isn't that helpful to top of the line compressors. eg. Fabrice Bellards nncp that's currently the record holding compressor for enwik9 is an LLM that learns on the fly. It's 628KB as shipped (LLM code complexity is high) and it wins on data sets gigabytes in size due to it's ability to create the training data on the fly. No pre-trained LLM comes close when you measure it as above (program size + compressed result).
So it's really not worth that much concern. There's a reason we all say AI is compression and we dismiss comments like the above. They don't pan out. No one's shipping significant dictionaries or pre-trained data. You want to win competitive compression? You'd better have raw code that learns on the fly and is naturally generalizable.
- > Compression is functionally equivalent to prediction when the data distribution is exactly representative of all future problems.
At some level, nothing is representative of all future "problems".
I think as far as corner cases is concerned, people can optimize for what they think matters. Larger models, higher sensitivities, better filtering.
Beyond this, I don't know what you're peeved by. There's no manifesto, there's no claiming that any particular method to prediction is perfect yet.
by altcognito - You're just assuming a flawed implementation of a predictor and complain that it's flawed. That doesn't invalidate the general premise that predictors are compressors.
Predictors don't have to give you some corpus-average probability. They can give probabilities adjusted per symbol. The probability could even be exactly 1 for some symbol when the predictor is absolutely certain (and then it costs 0 bits to encode).
If you had a magic oracle predictor that already knew all the data you wanted to send, you'd have perfect compression.
by pornel - I’m not exactly sure what distinction you are trying to make, but a compressor that generalizes from currently observed day to potential future data _is_ a better compressor, as it will have better predictions as it observes more of the source data distribution. Maybe you are making a point about whether compressors can “learn” after compressing the input data, but this also isn’t a fundamental property of compressors. Also compressors do have to deal with non-stationary data sources, so it also isn’t correct to say a compressor only models stationary distributions.by variadix
- How does that invalidate the "compression is prediction"? If the future data is different and you failed to generalize, then the failure to predict means you got worse at compressing and have to spend more bits storing the new information. Conversely, if the future data is the same as that you've seen previously, you could predict it very well, and compress better as a result.by porphyra
- The page source appears to contain all the actual text within <p> tags, but structured in a completely illogical way. With JavaScript disabled, there are a bunch of shaded bars where the text should appear, which look like placeholders for something that hasn't loaded yet even though it was there from the beginning. The <p> tags don't even seem to show up in the DOM. (I didn't check closely, but maybe they're embedded in an inline script.)
This is actively user-hostile. The site is going out of its way to interfere with the most basic possible function of HTML, i.e., the presentation of minimally marked-up plain text. The needless complexity is especially ironic in the context of an article about compression.
by zahlman - I think every website should be support noscript with minimum requirements.by ErenayDev
- Hey, appreciate the feedback! This is definitely a bug. Will get it fixed asap!by dev_cprice