FR version is available. Content is displayed in original English for accuracy.
Advertisement
Advertisement
⚡ Community Insights
Discussion Sentiment
91% Positive
Analyzed from 2026 words in the discussion.
Trending Topics
#gzip#prompt#compression#text#language#context#https#length#txt#llm
Discussion (56 Comments)Read Original on HackerNews
The test file belongs to the topic with the smallest size *.gz file.
Witten's group at Waikato uni were perhaps the first to work on this.
Also check out the Hutter prize if you are interested in this.
Some models are reproducible, in that the same prompt will generate the same output. Say that we could wire up such a model to generate some code.
In that case, we could create a prompt that generates, say, an entire codebase, or a large piece of text. The prompt (or really, the tokens) would then be the compressed version of the codebase or the text.
I am not talking about an "AI agent", but really a model that we call in a reproducible manner. Preferably one call, with one prompt. An agent could just run `git clone` to "decompress" a codebase, which conflates the idea of compression. If that were compression, then the "compressed version of the git kernel" would be a single line of text: `git clone https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...`. I am really talking about having an LLM re-generate text based on a prompt.
Does that make sense? I can imagine that this is highly impractical and inefficient. But would this count as "compression" at all?
A large language model itself (the network) give you the probabilities for the next token given some prefix of tokens so far. You can use arithmetic coding to go from these probabilities to a deterministic compression / decompression algorithm.
When you use an LLM to generate text, you sample from that probability distribution. You can use a true random sample. Or you can make it trivially deterministic by using a seeded pseudo-random-number-generator or you just pick the highest probability each time. But that's all a red herring; really, what you want is arithmetic coding.
https://en.wikipedia.org/wiki/Arithmetic_coding
Zstandard produces whitespace with the occasional letter thrown in. To quote MiMo: "As you can see, zstd does not speak Shakespeare. ... zstd encodes a run of one repeated byte as a near-free run-length sequence, and space and newline are the cheapest literals in the corpus: ten newlines cost about the same to append ten bytes of genuine corpus text and less than nonsense does."
Looks pretty profitable to me.
That said, Windows users should use 7-Zip. Better compression format, unpacks more kinds of archives
So the result only gives us some lower bound of how well gzip works as a "plausibility tester" of a continuation of a text. The space of possible sequences is many orders of magnitude larger than what was searched. So there might be sequences in there that compress much better.
The text mentions beamsearch, but I don't see a discussion about how well beamsearch performs in finding the global optima when it comes to gzip compressibility of a text?
It's unclear if this is very useful.
The reason it may not be very useful is that one of Deflate's ingredients is a pass that replaces repeated substrings with backreferences to the earlier occurrence in the plaintext input stream.
E.g. suppose we want to find an n=200 byte sequence x that minimises len(gzip(context+prompt+x)).
If there exists any 200 byte sequence y such that prompt+y is a substring of context, then Deflate can encode prompt+y as a backreference to that earlier sequence - it needs to store a match-length & a distance-length, encoded using its Huffman trees. This candidate solution y may not be a global minima to our stated objective function, but if not, it's probably going to be a very good near-optimal approximate solution.
Taking a step back, repeating huge chunks of the input context produces something that's great for minimising compressed output size but doesn't seem particularly helpful as a generative model.
edit:
Yep, I tried it out by running an experiment. Searching for the prompt in the context & then copying the following text as the solution produces solutions that are much better, in the sense of minimising the compressed output length, than beam search, while also being unhelpful as a generative tool.
With the same example as the blog post:
Let x denote a solution, x is a string of length 200.Let L(x) denote len(gzip(context+prompt+x)), our objective function
Let's call the proposed search method of searching for the prompt in the input rfind (after python's str.rfind).
Then we have
So 'rfind' is finding a solution that does a better job of minimising the objective function -- it only takes 3 bytes more to encode than the infeasible emptystring solution, and costs 25 fewer bytes than the solution found by the beam search implemented by gzipt per the blog post.Here's the solution 'generated' by rfind copying and pasting from the input context, starting from the rightmost occurrence of "MENENIUS:"
Here's the code for 'rfind' - our complete 'generative algorithm': Can hook it into gzipt.py by adding this line after out is defined, but before the beam search beginsWhen you say "cross-entropy loss" people without stats background go to Wikipedia, take a glance, and adjust their mental model to "inscrutable magic".
Thinking of the main difference as the trade-off in how much CPU, memory and storage is allowed is not really wrong.
The part that is wrong is to think of gzip as a method that might reach similar complexity or generalization. And more importantly, to ignore the advanced way how training data gets curated or generated for (instructed, chain-of-thought) LLMs. But even then. The mental model that the LLM's goal is text compression is not wrong. The question to ask next is what kind of text it is expecting to compress.
Viz. if Language is compression (of thought / culture / the tacit je ne sait quois of being-to-being communication etc.), then definitionally, Language Modelling must also be Compression.
Except, language is an arbitrarily lossy compressor, who's "compression-prediction equivalence" is indeterminate and unstable, because Language co-evolves constantly; both as a function of or response to culture, as well as an influencer of culture.
So, the subjective-objective goodness of Language Models (of any kind of language) would be, at best, upper-bounded by the compression-prediction equivalence of the Languages corpus itself. And that is assuming the language corpus is perfect in every way---it captures all knowledge expressible by language and it is always in-sync with live evolution of all language expression and evolution (i.e. LLM training is not a batch job, but a real-time present continuous process).
For example, to my layperson eyes, the mathematical language of proofs actively weeds out ambiguity of subjective interpretation. Ideally, a proof ought to lead to the exact same conclusion on every single reading by any reader who can follow the steps. A proof also holds only if the rest of the formal, explicit, inviolable, internally-consistent set of axioms and results holds.
So it stands to reason that mathematical prose of proofs, being optimised as mechanical procedure of taking an open question to a deterministically closed solution, has better odds of approximating the tacit aspects of mathematical derivation.
Which makes an LLM able to construct a mathematical proof, which is mind-melting to say the least.
However, I wonder, can LLMs dream of mathematical sheep?
Some will say that I should 'judge the idea, not the form'.
But if the author didn't find enough strength to write alone a short ~700 words summary about his work, it means he himself isn't that interested or enthusiastic about it. Why should others bother then? Particularly since low-effort like that signals possibility the whole work is superficial and derivative.
Compression is a property of language.
A seemingly simple sentence like "I had lunch" has enormous amount of information compressed inside it.
The word lunch is a compressed form of "having food at noon" and "noon" in turn is a compressed form of "Sun's position against Earth's rotation" and so on and so forth.
Every sentence has layers of compressed sentences. How many layers one chooses to decompress is up to the person.
The fact that gzip is relatively fast should be your first clue that something important is missing.
Gzip is great at predicting the next token for one very specific narrative. LLMs can predict next tokens for entire universes of narratives. Searching for the correct next token across this space scales ~quadratically with the input size. Gzip scales linearly. I can gzip a one terabyte file. Imagine feeding that much into an LLM. These are wildly different animals that happen to overlap in a very small way. Equating compression to intelligence looks increasingly silly to me.
If we must compare language models to compression, they are much more like jpeg and mp3 than they are gzip and flac. I can go fuck with a jpeg file pretty severely at the bitstream level and still have something resembling performance on the other side. Gzip cannot remotely approach this.
In part because gzip only has a 32KiB window size, and I think it'd be at least quadratic within that window if you were going for optimal compression.
Show me an LLM that can run at 300 megabytes per second. Even dedicated ASICs with weights burned in will never move this fast.
Quite well. This project[1], by Fabrice Bellard of ffmpeg fame, is quite old in AI years and uses an ancient LLM, but still beats xz by a solid margin.
[1]: https://bellard.org/ts_zip/
And energy consumption.