Why can one long string be described in a few words while another must be copied almost character by character? Compression replaces repetition or other regularity with a shorter description. A short description suggests that some structure has been captured; a long one may reflect structure the chosen method cannot express, or randomness that cannot be shortened. section 8.3
Three 10,000-bit strings
The string 0001 repeated 2,500 times needs only a repetition rule. Fair coin flips offer no comparable shortcut. A string with roughly four zeros for every one lies between them: it lacks a fixed pattern, but its statistical bias can help compress it. section 8.3
Kolmogorov complexity names the length of the shortest program that generates an object, but its exact value cannot be computed in general. In the coffee automaton, researchers instead average and quantize neighborhoods of cells, compress the resulting coarse-grained array with tools such as gzip or bzip2, and call its compressed size an estimate of apparent complexity. Coarse-graining deliberately sets aside fine randomness to examine visible boundaries and mixtures. section 8.1.1
Figure 8.2 Illustration of the construction of the coarse-grained array using an example grain size of 3. The values of the shaded cells on the left are averaged to produce the value of the shaded cell on the right. Used with permission granted by the lead author (Scott Aaronson).
The figure shows how averaging neighboring cells produces the coarse-grained array whose compressed size is measured. section 8.1.1
Minimum description length (MDL) turns the same intuition into a model-selection rule: seek a short combined description of the model and the data it leaves unexplained. A model that fits every training point can still waste bits describing noise; one that is too simple leaves too much data unexplained. Practical MDL depends on the available model class, so it cannot capture every possible regularity. section 8.3
Figure 8.6 A simple polynomial (left) underfits the data, a complex polynomial (middle) can achieve zero training error but wastes bits describing noise, and a tradeoff polynomial (right) identifies the broad trend without including the noise. Used with permission granted by the lead author (Peter Grünwald).
The polynomial comparison makes the code-length trade-off concrete: underfitting misses the trend, while a perfect training fit spends complexity on noise. section 8.3
For neural networks, shrinking a weight file is not the only aim. A compression scheme can treat networks with nearly identical predictions as equivalent even when their parameters differ. Weight quantization maps floating-point values to a small set of codes, with training that anticipates rounding errors; low-rank approximation replaces a large matrix with thinner factors when its patterns are redundant. These methods preserve useful behavior within a tolerance rather than every microscopic detail. section 8.5.1
Prediction offers a broader reason to care about compression. A character-predicting model trained on product reviews developed a neuron tracking sentiment: encoding that hidden factor helped it predict what came next. This motivates viewing a language model as a compact abstraction rather than a backup copy of the web. The distinction does not make every generated answer reliable, especially when it lacks grounding. section 8.0 section 8.6
