Compression is prediction

https://www.youtube.com/watch?v=B6u-FPskfAE

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.

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:

    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/

http://prize.hutter1.net/

https://github.com/hkust-nlp/llm-compression-intelligence

https://www.princeton.edu/~wbialek/rome/refs/shannon_51.pdf

Given a context (for LLMs, this would include the entire pretraining dataset, plus the prompt), you compress `context + next_token` for every possible next token. The tokens that co-compress best with the existing context are the 'least surprising' continuations. Choose one of them and iterate.

You can easily generate text with gzip this way. It won't be very good text, because gzip compression is not as sophisticated as a transformer + SGD, but the principle is the same.

The article itself has decision trees for the compression explanation, which is also a lookup index.

In each case you try to recognise (re)usable structure.

Self-indexing succinct data-structures are a good example of the third side of the coin.

So it's a trinity: compression, prediction, indexing