How Is Compression Prediction?

Over the past few weeks, I have repeatedly encountered the same claim on Hacker News: compression is prediction. The recent discussion has approached it from both directions. Two 3Blue1Brown videos, Reinventing Entropy and But what is cross-entropy?, derive entropy and cross-entropy from the limits of source coding. An ngrok article follows the same mathematics through arithmetic coding and language models. Salvatore Sanfilippo asks how far the resulting identification between prediction and compression should be taken. These explanations meet at one fact. A probabilistic model assigns a conditional probability to every possible continuation, and an entropy coder converts the probability assigned to the observed continuation into bits. For a sequence x1:nx_{1:n}x1:n and a model QQQ, the resulting ideal payload length is up to the overhead introduced by the coding procedure. The quantity on the right is also the model’s cumulative logarithmic loss. In this setting, improving prediction under log-loss and reducing the encoded payload are the same optimization problem. None of the underlying correspondence is new. Its foundations belong to classical information theory: Shannon connected probability to optimal code length, adaptive statistical compressors turned conditional estimates into codes long before modern language models, and the relation between learning and compression has been developed through minimum description length, MacKay’s treatment of information theory and inference, and work such as the Hutter Prize. Recent language-model results just instantiate this older correspondence at a new scale. I have spent the last few years working on compression, information theory, and compressed data structures and wanted to give my two cents. I agree with the equivalence. What interests me is where it begins and where it ends. It describes the cost of encoding data under an agreed model, but a compression problem starts before that model can be applied and does not always end when the shortest bitstream has been produced. The encoder and decoder must agree on what kind of object is being represented, which alternatives remain possible, how the probability model is made available, and what the decoder must be able to do with the representation. Throughout this article, compression means lossless compression unless stated otherwise. Even within that scope, compression can be defined before introducing a sequential model. A finite family of admissible objects gives a counting lower bound without identifying a next symbol. A fixed or data-dependent code can later be interpreted probabilistically, and a distribution over serialized objects can be factored into next-symbol conditionals. That reinterpretation does not choose the family of objects, pay for information unavailable to the decoder, or enforce operations such as random access. The question is therefore not whether prediction and compression can be made mathematically equivalent. They can. The question is what must be fixed before the equivalence applies, which part of a complete representation its bit count measures, and what remains outside that measurement. A note on level. This article is a bit technical, it assumes familiarity with undergraduate mathematics and elementary proof-style arguments, but no prior background in information theory is really required, although it may help. A note on level. This article is a bit technical, it assumes familiarity with undergraduate mathematics and elementary proof-style arguments, but no prior background in information theory is really required, although it may help. Table of Contents Compression Before Probability Possibilities Have Different Probabilities When Compression Becomes Prediction The Source Is Unknown Fitting a Zero-Order Model Counting Sequences Instead Adding Context Fitting a Zero-Order Model Counting Sequences Instead Adding Context The Model Is Part of the Message The Shortest Bitstream May Be the Wrong Representation So, Is Compression Prediction? Compression Before Probability The ngrok article begins by distinguishing minification from what it calls “true” compression. A minifier removes comments, whitespace, and other parts of a source file that do not affect its execution. The resulting program is shorter, but the original source file cannot be reconstructed from it. Whether this operation is lossless depends on what the representation is required to preserve. If the object is the original sequence of source bytes, minification is lossy. If the object is the program’s behaviour and the decoder may return any behaviourally equivalent program, a semantics-preserving minifier is lossless relative to that different contract. The transformation has not changed. The object being represented has. This distinction precedes any probability model. Before asking how likely an object is, the encoder and decoder must agree on what counts as that object and when two decoded outputs count as equivalent. Only then does the length of a description become meaningful. Once an individual object xxx has been fixed, the most permissive effective descriptions are programs that produce it. After choosing a universal machine UUU, the Kolmogorov complexity of a binary string xxx is Thus, KU(x)K_U(x)KU(x) is the length of the shortest program that outputs xxx. Any regularity that can be expressed algorithmically may shorten this description. A string containing a billion zeros has a long literal representation but a short program that prints one billion zeros. The definition does not require the string to have been sampled from a source, and it does not require one symbol to be predicted from the symbols preceding it. The machine UUU is part of the description language. Choosing a different universal machine changes which programs are available and therefore changes the exact value of the complexity. The invariance theorem bounds this dependence. For two fixed universal machines UUU and VVV, there is a constant cU,Vc_{U,V}cU,V such that for every string xxx. The constant may depend on the two machines, but not on xxx. It accounts for the fixed program needed to simulate one description language in the other. The choice of machine is therefore part of the description language shared by whoever produces and interprets the program. This is the first instance of a recurring theme: the length of an object is meaningful only relative to information already fixed outside its description. Kolmogorov complexity gives a limit on the effective description of an individual object, but it does not provide a general compression algorithm. The function KUK_UKU is not computable. No procedure can determine the length of the shortest program for every string, much less construct that program. A practical compressor must restrict the descriptions it is willing and able to consider. One such restriction is that the object belongs to a finite family F\mathcal{F}F. Once F\mathcal{F}F has been fixed, a lossless representation must distinguish every member of that family from every other member. Consider a fixed-length encoding Lossless decoding requires CCC to be injective. Since only 2ℓ2^\ell2ℓ binary strings of length ℓ\ellℓ exist, injectivity implies and therefore An agreed enumeration of F\mathcal{F}F attains this bound by assigning each object an index and representing that index in binary. The quantity is the counting bound of the family. In the literature on succinct data structures, which studies representations whose space approaches information-theoretic lower bounds, the quantity log⁡2∣F∣\log_2|\mathcal{F}|log2∣F∣ is sometimes called the worst-case entropy of the family. I will use counting bound because its derivation assumes neither a uniform distribution nor any sampling process. It only counts the alternatives that the representation must distinguish. The family F\mathcal{F}F is part of the information shared by the encoder and decoder. If the decoder knows only that the object belongs to a larger family G\mathcal{G}G, then the representation must distinguish among the members of G\mathcal{G}G instead. The lower bound becomes A restriction from G\mathcal{G}G to F\mathcal{F}F saves bits only if the decoder already knows that restriction or if the representation communicates it. What counts as redundancy therefore depends on which alternatives have already been excluded. Kolmogorov complexity and the counting bound answer different versions of the same preliminary question. The first considers the shortest effective description of one object. The second considers the number of bits needed to distinguish every object in a fixed finite family. Neither requires a probability distribution or a next-symbol predictor. Possibilities Have Different Probabilities The counting bound treats every admissible object symmetrically. To assign shorter descriptions to some objects, we need a rule that determines which objects receive them and which objects pay with longer descriptions. A probability distribution supplies that rule. Let X\mathcal{X}X be a finite set of possible objects. For each x∈Xx\in\mathcal{X}x∈X, a source specifies a probability where P(x)>0P(x)>0P(x)>0 and A probability must be translated into a quantity measured in bits. If two independent outcomes occur with probabilities P(x)P(x)P(x) and P(y)P(y)P(y), their joint probability is the product P(x)P(y)P(x)P(y)P(x)P(y), while their bit costs should add. The logarithm performs this conversion. The information content of an outcome xxx is An event with probability 2−b2^{-b}2−b has information content bbb bits. More probable outcomes receive smaller values because fewer bits should be allocated to events that occur more often. Before the source produces an outcome, its information content is not known. Its expected value is This is the Shannon entropy of the source. When PPP is uniform, every object has information content so Shannon entropy equals the counting bound of the family. The values IP(x)I_P(x)IP(x) are ideal bit costs derived from the source distribution. To obtain a representation, we need a binary code with codeword lengths The expected number of bits used by the code is The source suggests the ideal real-valued lengths −log⁡2P(x)-\log_2P(x)−log2P(x), while an actual binary code must assign integer lengths. Before comparing their averages, we need to answer two questions. Which collections of integer lengths can form a decodable code? And, once such a code has been chosen, can its lengths themselves be interpreted probabilistically? Kraft–McMillan answers the first question and makes the second possible. Assigning a different binary string to each object is sufficient when each codeword is presented in isolation. It is not sufficient when codewords are concatenated. A concatenated bitstream could admit two decompositions into codewords and therefore two possible source sequences. A code is uniquely decodable when every concatenation of its codewords has only one decomposition. A prefix code guarantees this property by requiring that no codeword be a prefix of another. Its codewords can be placed at leaves of a binary tree. Each edge contributes one bit, and the depth of a leaf equals the length of its codeword. Let mmm be at least as large as the longest codeword. A codeword of length ℓC(x)\ell_C(x)ℓC(x) has descendants at depth mmm. Since no codeword is a prefix of another, the sets of descendants belonging to distinct codewords are disjoint. The complete binary tree contains only 2m2^m2m nodes at depth mmm, so Dividing by 2m2^m2m gives This is the Kraft–McMillan inequality. The tree argument proves it for prefix codes. The same inequality is necessary for every uniquely decodable code, even when its codewords do not form leaves of a prefix tree. Conversely, any collection of non-negative integer lengths satisfying the inequality can be realized by a prefix code. The diagram in Reinventing Entropy visualizes the prefix-code case of this inequality. A codeword of length ℓ\ellℓ excludes all of its descendants and therefore occupies a fraction 2−ℓ2^{-\ell}2−ℓ of the available binary coding space. The video uses this geometry to explain why assigning one symbol a shorter codeword leaves less space for the others; Kraft–McMillan makes the same constraint precise and extends it to every uniquely decodable code. The source probabilities satisfy a related identity. From the definition of information content, and therefore The ideal lengths IP(x)I_P(x)IP(x) satisfy the same constraint as codeword lengths, with equality. They may nevertheless be fractional, so they do not necessarily specify a binary code. So far, probability has produced ideal code lengths. The more important direction for our argument is the converse: a code chosen without any probabilistic model still determines probability weights through its lengths. Given a uniquely decodable code CCC, define its Kraft sum The Kraft–McMillan inequality gives SC≤1S_C\leq1SC≤1. The quantities 2−ℓC(x)2^{-\ell_C(x)}2−ℓC(x) may therefore sum to less than one, but normalization turns them into a probability distribution: Solving for the codeword length gives The code lengths are therefore information contents under the induced distribution QCQ_CQC, shifted by the same non-negative amount −log⁡2SC-\log_2S_C−log2SC. When the Kraft inequality is tight, so that SC=1S_C=1SC=1, the correspondence is exact: A fixed-length code is the simplest instance. If every object receives the same length, then every value 2−ℓC(x)2^{-\ell_C(x)}2−ℓC(x) is equal, and normalization produces the uniform distribution over the objects. A non-uniform code induces a non-uniform distribution in which shorter codewords correspond to more probable objects. This does not mean that a probability distribution was required to define the code. The counting argument in the previous section produced a fixed-length code without assuming a source. It means that once a uniquely decodable code has been chosen, its lengths can always be given a probabilistic interpretation. Codes constrain probability assignments, and probability assignments suggest code lengths. The induced distribution also proves that entropy lower-bounds expected code length. Averaging under the source distribution gives Subtracting the source entropy yields Both terms are non-negative. The first is the Kullback–Leibler divergence from the source distribution to the distribution induced by the code. The second is non-negative because SC≤1S_C\leq1SC≤1. Therefore every uniquely decodable code satisfies The excess length has two sources. The divergence measures how poorly the code lengths match the source probabilities. The term −log⁡2SC-\log_2S_C−log2SC measures unused coding capacity when the Kraft inequality is not tight. The lower bound can be approached by rounding each ideal length upward: Since 2−ℓ(x)≤P(x)2^{-\ell(x)}\leq P(x)2−ℓ(x)≤P(x), these lengths satisfy the Kraft–McMillan inequality and can therefore be realized by a prefix code. Moreover, so averaging under PPP gives This is the one-symbol form of Shannon’s Source Coding Theorem: entropy lower-bounds every uniquely decodable code, while a prefix code can always remain within one bit of it. For a block of rrr independent outcomes drawn from PPP, the same construction gives an expected block length smaller than rH(P)+1rH(P)+1rH(P)+1. The excess per source symbol is therefore less than 1/r1/r1/r and tends to zero as the block length grows. For dependent outcomes, the same statement applies to their joint block distribution, with rH(P)rH(P)rH(P) replaced by the corresponding block entropy. Up to this point, each value x∈Xx\in\mathcal{X}x∈X has been treated as a complete object. The equivalence between code lengths and probability assignments is already present, but no next symbol has appeared. Prediction enters only after an object is represented as an ordered sequence and its probability is factored into conditional probabilities for the successive symbols. When Compression Becomes Prediction Now suppose that the object is an ordered sequence over an alphabet Σ\SigmaΣ. Write for the prefix before position iii. The probability of the complete sequence satisfies the chain rule No independence assumption is involved. Each conditional distribution may depend on the complete prefix. Here, “next” means next in the agreed serialization. The complete sequence may already be available to the encoder, prediction refers to the conditional probabilities assigned along that serialization. Applying −log⁡2-\log_2−log2 turns the product into a sum: The information content of the complete sequence is therefore the sum of the conditional information contents of its symbols. Averaging over all possible sequences gives where measures the information that remains at position iii after the prefix is known. A compressor rarely knows the true conditional distributions. It instead uses a model QQQ that returns, for every prefix, a distribution over Σ\SigmaΣ, with Returning only the most likely symbol is not sufficient. The encoder already knows which symbol occurs and needs a code length for that symbol, whether or not it was the model’s first choice. Two models may select the same most likely continuation while assigning different probabilities to the observed symbol. The model defines a probability for the complete sequence: Its cumulative logarithmic loss is A high probability assigned to the observed symbol produces a small loss. A low probability produces a large loss. A model used for lossless coding must assign positive probability to every symbol that may occur, since probability zero would give an infinite code length. During generation, a model chooses or samples a symbol from this distribution. During compression, the actual symbol is already known. The distribution is used to determine how much of the code space that symbol receives. Prediction in this equivalence means assigning probabilities, not guessing one continuation and replacing the data with that guess. The model still does not produce a bitstream. An entropy coder must convert its probability assignments into a decodable representation. Arithmetic coding begins with the interval [0,1)[0,1)[0,1). At position iii, it partitions the current interval into adjacent subintervals whose widths are proportional to and retains the subinterval assigned to the observed symbol xix_ixi. If the current interval has width wi−1w_{i-1}wi−1, the selected interval has width Starting from w0=1w_0=1w0=1, the final width is The emitted binary prefix identifies a dyadic interval. To decode the sequence unambiguously, that dyadic interval must be contained in the final arithmetic-coding interval, together with an agreed termination convention. The number of required bits is therefore plus a bounded coding overhead in the ideal arithmetic-coding model. Decoding repeats the same subdivisions. After recovering x 0n_\omega>0nω>0. The same maximum-likelihood argument used in the zero-order case applies independently to each context. The smallest log-loss obtained by assigning one distribution to the symbols following ω\omegaω is Summing over the observed contexts gives which matches the kkk-th order empirical entropy under the boundary convention that only positions with a complete length- kkk context contribute to the sum. The first kkk symbols have no complete length- kkk context. They may be encoded separately as one block in bits, or handled through an agreed boundary convention. When k=0k=0k=0, there is only the empty context and the definition reduces to H0(S)\mathcal{H}_0(S)H0(S). Longer contexts divide the observed positions into smaller groups. Refining a group cannot increase the minimum fitted log-loss when both models are evaluated on the same set of positions, since the refined model can always reuse the distribution of the original group. More context can therefore reduce the empirical data term. This reduction eventually exposes a limitation of the measure. If every observed context is followed by only one distinct symbol, then every SωS_\omegaSω is constant and for all observed contexts. Consequently, This always occurs at k=n−1k=n-1k=n−1, where only one position has a complete context, and it may occur much earlier when sufficiently long contexts determine their observed continuations. The value Hk(S)=0\mathcal{H}_k(S)=0Hk(S)=0 does not give a zero-length lossless representation of SSS. It gives a zero data term after the fitted context distributions are available. A decoder can assign probability one to an observed continuation only if it already knows which continuation followed that context. As the empirical loss decreases, information may have moved from the encoded sequence into the fitted model. The complete description must account for how the decoder obtains that model. The Model Is Part of the Message That missing information is the model itself. Let MMM contain everything the decoder needs to reproduce the probabilities used by the encoder. A two-part description has length The term L(M)L(M)L(M) describes the model. The term L(S∣M)L(S\mid M)L(S∣M) encodes the sequence using that model. In a sufficiently expressive model family, minimizing only the second term rewards memorization. A more complex model improves the complete description only when the reduction in L(S∣M)L(S\mid M)L(S∣M) exceeds the additional cost of describing MMM. This is the basic two-part form of the minimum description length principle. For the order- kkk model above, this cost is concrete. A naïve dense table contains σk\sigma^kσk contexts and σ\sigmaσ continuation counts for each context. Storing every count in a fixed-width field gives an upper bound of bits. Sparse representations reduce this cost, but they must still identify which contexts and continuations occur. How the model is charged depends on what the encoder and decoder already share. There are three relevant cases: the model may be fixed in advance, transmitted with the data, or reconstructed online while decoding. If the model is fixed by a file format, built into the decoder, or otherwise shared in advance, it does not belong to the conditional description length of an individual message. It remains part of the system that makes that description meaningful, but charging its complete size to every message would also be misleading. If it is fitted offline and not already available to the decoder, a description of its tables, parameters, or weights must accompany the encoded data. Language Modeling Is Compression calls the ratio obtained without parameter size the raw compression rate. Its adjusted compression rate adds the parameter size to the compressed output. A larger model may obtain a lower log-loss while producing a worse adjusted rate when it is amortized over too little data. In prequential coding, encoder and decoder begin from the same initial state. Let Qi−1Q_{i-1}Qi−1 be the model available after the prefix s 0Q(x)>0Q(x)>0 whenever P(x)>0P(x)>0P(x)>0, the expected ideal data length is the cross-entropy Subtracting the source entropy gives and therefore For sequential distributions, relative entropy decomposes across positions: Each term is the expected number of additional bits paid at one position because the model’s conditional distribution differs from the source distribution. This distinction matters when discussing whether a better predictor “reduces entropy.” For a fixed source PPP, improving QQQ under expected logarithmic loss means reducing the cross-entropy H(P,Q)H(P,Q)H(P,Q), equivalently reducing the mismatch term DKL(P∥Q)D_{\mathrm{KL}}(P\mathbin\Vert Q)DKL(P∥Q). It does not change H(P)H(P)H(P). The ngrok article correctly associates better probability estimates with shorter encodings, but its final use of entropy merges these two quantities. The distribution used for evaluation also matters. If QSQ_SQS is fitted to an observed sequence SSS, minimizing its in-sample log-loss does not imply that it will minimize log-loss on future data. For a future distribution RRR, A model may therefore compress its training sequence more tightly while predicting future observations worse, either because it has overfit the sample or because the source has changed. Compression length and prediction log-loss remain the same quantity when evaluated on the same data, generalization between different samples or distributions is a separate question. The Shortest Bitstream May Be the Wrong Representation Every code considered so far has been judged by one operation: reconstructing the complete object. The two-part description length says nothing about what can be done with the encoded data before that reconstruction is complete. A bit-packed vector and an entropy-coded stream make this difference concrete. Nothing in this factorization requires the sequence order to represent physical time. Consider a vector I have implemented both bit-packed and entropy-coded representations of a vector in Rust, you can have a look here I have implemented both bit-packed and entropy-coded representations of a vector in Rust, you can have a look here whose values belong to {0,…,u−1}\{0,\ldots,u-1\}{0,…,u−1}. Let A bit-packed representation assigns exactly bbb consecutive bits to each value, using nbnbnb bits for the payload apart from alignment and metadata. The representation of aia_iai begins at bit position ibibib. If the storage-word width is w≥bw\geq bw≥b, recovering aia_iai requires reading at most two adjacent words, shifting their contents, and applying a mask. The addresses and shifts are computed directly from iii, so access takes O(1)O(1)O(1) time. This representation does not exploit differences in frequency. Every value receives the same number of bits. If the values follow a non-uniform distribution, or if their probabilities depend on earlier values, an entropy coder may produce a shorter stream: The shorter stream provides a different access contract. In an ordinary arithmetic-coded stream, the decoding state at position iii depends on the symbols that precede it. If the model also uses their context, its next distribution depends on the same prefix. Recovering aia_iai requires decoding from the beginning of the stream or from an earlier checkpoint whose coding and model states have been stored. The bit-packed vector may occupy more space while answering vector[i] directly. Its compression comes from restricting the possible value at each position to an alphabet of size uuu, rather than from predicting which value will occur. When all values remain equally plausible, fixed-width packing uses the information supplied by that restriction without requiring a non-uniform model. A compressed archive needs an encoding EEE and a decoder DDD satisfying Once the whole vector can be reconstructed, the encoding has fulfilled its contract. A compressed representation may be required to satisfy a stronger condition. It must support an access algorithm such that without first reconstructing all of AAA. Checkpoints can give an entropy-coded stream faster access, but each checkpoint occupies space. Smaller blocks reduce the amount of decoding required for an access and increase the number of stored states. Larger blocks save metadata and increase access time. The objective is no longer to minimize the bitstream without qualification. It becomes for a chosen access-time bound ttt. The operation need not be random access, and the object need not be a vector. The same issue arises whenever compressed data must be searched, traversed, compared, or partially decoded. The required operations constrain which short descriptions are useful and how much auxiliary information they need. Bitstream length alone answers only the bare reconstruction problem. A compressed representation must also encode enough structure for its required operations. The decoder contract now has three explicit parts: the objects it must distinguish, the information it already shares with the encoder, and the operations it must perform without full reconstruction. Prediction determines conditional code lengths inside this contract. It does not determine the contract itself. So, Is Compression Prediction? So, is compression prediction? Once the coding problem has been fixed, yes, but in a precise sense. The equivalence concerns the ideal length of the encoded payload under an agreed model. The qualification matters because a description-length problem can be posed before a next-symbol predictor exists. Kolmogorov complexity does so for an individual string, while the counting bound does so for a finite family of objects. What I felt the other explanations left implicit was the compression problem that must be fixed before the equivalence becomes meaningful. The encoder and decoder need an agreed family of objects, a serialization, a boundary between transmitted and shared information, and a decoding contract. None of these choices is determined by next-symbol prediction. Once those choices have been made, the equivalence is exact at the level of code lengths. A sequential probability model assigns ideal payload lengths through logarithmic loss. Conversely, every uniquely decodable code over a fixed object family induces the distribution and its codeword lengths satisfy After the objects have been serialized, the induced distribution can in turn be factored into next-symbol conditionals. That generality is also the limit of the slogan Compression is Prediction. Recasting a representation probabilistically does not explain why its objects were chosen, whether its model must be transmitted, or which operations it supports. A model with lower log-loss can produce a larger complete file after its parameters are included. An empirical entropy of zero can still leave the decoder without the model needed to reconstruct the sequence. Compression is therefore prediction after the coding problem has been fixed, and only at the level measured by the induced code lengths. For a shared sequential model, cumulative log-loss gives the ideal payload length up to coding overhead. It does not define what must be represented, what the decoder already knows, or what the representation must allow the decoder to do.