How Is Compression Prediction?

# How Is Compression Prediction? | Luca Lombardo Source: [https://lukefleed.xyz/posts/compression/](https://lukefleed.xyz/posts/compression/) 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*](https://youtu.be/l6DKRf-fAAM)and[*But what is cross\-entropy?*](https://youtu.be/GlYgs6v2YfU), derive entropy and cross\-entropy from the limits of source coding\. An[ngrok article](https://ngrok.com/blog/compression-is-prediction)follows the same mathematics through arithmetic coding and language models\.[Salvatore Sanfilippo](https://www.youtube.com/watch?v=UgRiVUce9sY)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 sequencex1:nx\_\{1:n\}and a modelQQ, the resulting ideal payload length is −log⁡2Q\(x1:n\)=∑i=1n−log⁡2Q\(xi∣x<i\)\-\\log\_2 Q\(x\_\{1:n\}\) = \\sum\_\{i=1\}^n \-\\log\_2 Q\(x\_i\\mid x\_\{<i\}\)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](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)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](https://en.wikipedia.org/wiki/Minimum_description_length),[MacKay’s](https://www.inference.org.uk/mackay/itila/book.html)treatment of information theory and inference, and work such as the[Hutter Prize](https://prize.hutter1.net/)\. 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\. ## Table of Contents Open Table of Contents- [Compression Before Probability](https://lukefleed.xyz/posts/compression/#compression-before-probability) - [Possibilities Have Different Probabilities](https://lukefleed.xyz/posts/compression/#possibilities-have-different-probabilities) - [When Compression Becomes Prediction](https://lukefleed.xyz/posts/compression/#when-compression-becomes-prediction) - [The Source Is Unknown](https://lukefleed.xyz/posts/compression/#the-source-is-unknown)- [Fitting a Zero\-Order Model](https://lukefleed.xyz/posts/compression/#fitting-a-zero-order-model) - [Counting Sequences Instead](https://lukefleed.xyz/posts/compression/#counting-sequences-instead) - [Adding Context](https://lukefleed.xyz/posts/compression/#adding-context) - [The Model Is Part of the Message](https://lukefleed.xyz/posts/compression/#the-model-is-part-of-the-message) - [The Shortest Bitstream May Be the Wrong Representation](https://lukefleed.xyz/posts/compression/#the-shortest-bitstream-may-be-the-wrong-representation) - [So, Is Compression Prediction?](https://lukefleed.xyz/posts/compression/#so-is-compression-prediction) ## Compression Before Probability The[ngrok article](https://ngrok.com/blog/compression-is-prediction)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 objectxxhas been fixed, the most permissive effective descriptions are programs that produce it\. After choosing a universal machineUU, the[Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity)of a binary stringxxis KU\(x\)=min⁡\{∣p∣:U\(p\)=x\}K\_U\(x\) = \\min \\left\\\{ \|p\| : U\(p\)=x \\right\\\}Thus,KU\(x\)K\_U\(x\)is the length of the shortest program that outputsxx\. 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 machineUUis 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 machinesUUandVV, there is a constantcU,Vc\_\{U,V\}such that ∣KU\(x\)−KV\(x\)∣≤cU,V\\left\| K\_U\(x\)\-K\_V\(x\) \\right\| \\leq c\_\{U,V\}for every stringxx\. The constant may depend on the two machines, but not onxx\. 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 functionKUK\_Uis 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 familyF\\mathcal\{F\}\. OnceF\\mathcal\{F\}has been fixed, a lossless representation must distinguish every member of that family from every other member\. Consider a fixed\-length encoding C:F⟶\{0,1\}ℓC : \\mathcal\{F\} \\longrightarrow \\\{0,1\\\}^\{\\ell\}Lossless decoding requiresCCto be injective\. Since only2ℓ2^\\ellbinary strings of lengthℓ\\ellexist, injectivity implies 2ℓ≥∣F∣2^\\ell \\geq \|\\mathcal\{F\}\|and therefore ℓ≥⌈log⁡2∣F∣⌉\\ell \\geq \\left\\lceil \\log\_2\|\\mathcal\{F\}\| \\right\\rceilAn agreed enumeration ofF\\mathcal\{F\}attains this bound by assigning each object an index and representing that index in binary\. The quantity log⁡2∣F∣\\log\_2\|\\mathcal\{F\}\|is the*counting bound*of the family\. In the literature on[succinct data structures](https://en.wikipedia.org/wiki/Succinct_data_structure), which studies representations whose space approaches information\-theoretic lower bounds, the quantitylog⁡2∣F∣\\log\_2\|\\mathcal\{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 familyF\\mathcal\{F\}is part of the information shared by the encoder and decoder\. If the decoder knows only that the object belongs to a larger familyG\\mathcal\{G\}, then the representation must distinguish among the members ofG\\mathcal\{G\}instead\. The lower bound becomes log⁡2∣G∣\\log\_2\|\\mathcal\{G\}\|A restriction fromG\\mathcal\{G\}toF\\mathcal\{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\. LetX\\mathcal\{X\}be a finite set of possible objects\. For eachx∈Xx\\in\\mathcal\{X\}, a source specifies a probability P\(x\)=Pr⁡\(X=x\)P\(x\)=\\Pr\(X=x\)whereP\(x\)\>0P\(x\)\>0and ∑x∈XP\(x\)=1\\sum\_\{x\\in\\mathcal\{X\}\}P\(x\)=1A probability must be translated into a quantity measured in bits\. If two independent outcomes occur with probabilitiesP\(x\)P\(x\)andP\(y\)P\(y\), their joint probability is the productP\(x\)P\(y\)P\(x\)P\(y\), while their bit costs should add\. The logarithm performs this conversion\. The[information content](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)of an outcomexxis IP\(x\)=−log⁡2P\(x\)I\_P\(x\) = \-\\log\_2P\(x\)An event with probability2−b2^\{\-b\}has information contentbbbits\. 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 H\(P\)=∑x∈XP\(x\)IP\(x\)=−∑x∈XP\(x\)log⁡2P\(x\)\\begin\{aligned\} H\(P\) &= \\sum\_\{x\\in\\mathcal\{X\}\}P\(x\)I\_P\(x\) \\\\ &= \-\\sum\_\{x\\in\\mathcal\{X\}\}P\(x\)\\log\_2P\(x\) \\end\{aligned\}This is the[Shannon entropy](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf)of the source\. WhenPPis uniform, every object has information content log⁡2∣X∣\\log\_2\|\\mathcal\{X\}\|so Shannon entropy equals the counting bound of the family\. The valuesIP\(x\)I\_P\(x\)are ideal bit costs derived from the source distribution\. To obtain a representation, we need a binary code C:X⟶\{0,1\}∗C : \\mathcal\{X\} \\longrightarrow \\\{0,1\\\}^\*with codeword lengths ℓC\(x\)=∣C\(x\)∣\\ell\_C\(x\) = \|C\(x\)\|The expected number of bits used by the code is LP\(C\)=∑x∈XP\(x\)ℓC\(x\)L\_P\(C\) = \\sum\_\{x\\in\\mathcal\{X\}\} P\(x\)\\ell\_C\(x\)The source suggests the ideal real\-valued lengths−log⁡2P\(x\)\-\\log\_2P\(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](https://en.wikipedia.org/wiki/Variable-length_code)when every concatenation of its codewords has only one decomposition\. A[prefix code](https://en.wikipedia.org/wiki/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\. Letmmbe at least as large as the longest codeword\. A codeword of lengthℓC\(x\)\\ell\_C\(x\)has 2m−ℓC\(x\)2^\{m\-\\ell\_C\(x\)\}descendants at depthmm\. Since no codeword is a prefix of another, the sets of descendants belonging to distinct codewords are disjoint\. The complete binary tree contains only2m2^mnodes at depthmm, so ∑x∈X2m−ℓC\(x\)≤2m\\sum\_\{x\\in\\mathcal\{X\}\} 2^\{m\-\\ell\_C\(x\)\} \\leq 2^mDividing by2m2^mgives ∑x∈X2−ℓC\(x\)≤1\\sum\_\{x\\in\\mathcal\{X\}\} 2^\{\-\\ell\_C\(x\)\} \\leq 1This is the[Kraft–McMillan inequality](https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_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*](https://youtu.be/l6DKRf-fAAM?t=518)visualizes the prefix\-code case of this inequality\. A codeword of lengthℓ\\ellexcludes all of its descendants and therefore occupies a fraction2−ℓ2^\{\-\\ell\}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, 2−IP\(x\)=P\(x\)2^\{\-I\_P\(x\)\} = P\(x\)and therefore ∑x∈X2−IP\(x\)=∑x∈XP\(x\)=1\\sum\_\{x\\in\\mathcal\{X\}\} 2^\{\-I\_P\(x\)\} = \\sum\_\{x\\in\\mathcal\{X\}\} P\(x\) = 1The ideal lengthsIP\(x\)I\_P\(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 codeCC, define its Kraft sum SC=∑x∈X2−ℓC\(x\)S\_C = \\sum\_\{x\\in\\mathcal\{X\}\} 2^\{\-\\ell\_C\(x\)\}The Kraft–McMillan inequality givesSC≤1S\_C\\leq1\. The quantities2−ℓC\(x\)2^\{\-\\ell\_C\(x\)\}may therefore sum to less than one, but normalization turns them into a probability distribution: QC\(x\)=2−ℓC\(x\)SCQ\_C\(x\) = \\frac\{2^\{\-\\ell\_C\(x\)\}\}\{S\_C\}Solving for the codeword length gives ℓC\(x\)=−log⁡2QC\(x\)−log⁡2SC\\ell\_C\(x\) = \-\\log\_2Q\_C\(x\)\-\\log\_2S\_CThe code lengths are therefore information contents under the induced distributionQCQ\_C, shifted by the same non\-negative amount−log⁡2SC\-\\log\_2S\_C\. When the Kraft inequality is tight, so thatSC=1S\_C=1, the correspondence is exact: ℓC\(x\)=−log⁡2QC\(x\)\\ell\_C\(x\) = \-\\log\_2Q\_C\(x\)A fixed\-length code is the simplest instance\. If every object receives the same length, then every value2−ℓC\(x\)2^\{\-\\ell\_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 ℓC\(x\)=−log⁡2QC\(x\)−log⁡2SC\\ell\_C\(x\) = \-\\log\_2Q\_C\(x\)\-\\log\_2S\_Cunder the source distribution gives LP\(C\)=−∑x∈XP\(x\)log⁡2QC\(x\)−log⁡2SCL\_P\(C\) = \-\\sum\_\{x\\in\\mathcal\{X\}\} P\(x\)\\log\_2Q\_C\(x\) \-\\log\_2S\_CSubtracting the source entropy yields LP\(C\)−H\(P\)=∑x∈XP\(x\)log⁡2P\(x\)QC\(x\)−log⁡2SC=DKL\(P∥QC\)−log⁡2SC\\begin\{aligned\} L\_P\(C\)\-H\(P\) &= \\sum\_\{x\\in\\mathcal\{X\}\} P\(x\) \\log\_2 \\frac\{P\(x\)\}\{Q\_C\(x\)\} \-\\log\_2S\_C \\\\ &= D\_\{\\mathrm\{KL\}\}\\left\(P\\mathbin\\Vert Q\_C\\right\) \-\\log\_2S\_C \\end\{aligned\}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 becauseSC≤1S\_C\\leq1\. Therefore every uniquely decodable code satisfies LP\(C\)≥H\(P\)L\_P\(C\) \\geq H\(P\)The excess length has two sources\. The divergence measures how poorly the code lengths match the source probabilities\. The term−log⁡2SC\-\\log\_2S\_Cmeasures unused coding capacity when the Kraft inequality is not tight\. The lower bound can be approached by rounding each ideal length upward: ℓ\(x\)=⌈−log⁡2P\(x\)⌉\.\\ell\(x\)=\\left\\lceil\-\\log\_2P\(x\)\\right\\rceil\.Since2−ℓ\(x\)≤P\(x\)2^\{\-\\ell\(x\)\}\\leq P\(x\), these lengths satisfy the Kraft–McMillan inequality and can therefore be realized by a prefix code\. Moreover, −log⁡2P\(x\)≤ℓ\(x\)<−log⁡2P\(x\)\+1,\-\\log\_2P\(x\)\\leq\\ell\(x\)<\-\\log\_2P\(x\)\+1,so averaging underPPgives H\(P\)≤LP\(C\)<H\(P\)\+1\.H\(P\)\\leq L\_P\(C\)<H\(P\)\+1\.This is the one\-symbol form of[Shannon’s Source Coding Theorem](https://en.wikipedia.org/wiki/Shannon%27s_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 ofrrindependent outcomes drawn fromPP, the same construction gives an expected block length smaller thanrH\(P\)\+1rH\(P\)\+1\. The excess per source symbol is therefore less than1/r1/rand tends to zero as the block length grows\. For dependent outcomes, the same statement applies to their joint block distribution, withrH\(P\)rH\(P\)replaced by the corresponding block entropy\. Up to this point, each valuex∈Xx\\in\\mathcal\{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 x1:n=x1,…,xn∈Σnx\_\{1:n\}=x\_1,\\ldots,x\_n\\in\\Sigma^nover an alphabetΣ\\Sigma\. Write x<i=x1,…,xi−1x\_\{<i\}=x\_1,\\ldots,x\_\{i\-1\}for the prefix before positionii\. The probability of the complete sequence satisfies the chain rule P\(x1:n\)=∏i=1nP\(xi∣x<i\)P\(x\_\{1:n\}\) = \\prod\_\{i=1\}^n P\(x\_i\\mid x\_\{<i\}\)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\_2turns the product into a sum: −log⁡2P\(x1:n\)=∑i=1n−log⁡2P\(xi∣x<i\)\-\\log\_2P\(x\_\{1:n\}\) = \\sum\_\{i=1\}^n \-\\log\_2P\(x\_i\\mid x\_\{<i\}\)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 H\(X1:n\)=∑i=1nH\(Xi∣X<i\)H\(X\_\{1:n\}\) = \\sum\_\{i=1\}^n H\(X\_i\\mid X\_\{<i\}\)where H\(Xi∣X<i\)=E\[−log⁡2P\(Xi∣X<i\)\]H\(X\_i\\mid X\_\{<i\}\) = \\mathbb\{E\}\\left\[\-\\log\_2P\(X\_i\\mid X\_\{<i\}\)\\right\]measures the information that remains at positioniiafter the prefix is known\. A compressor rarely knows the true conditional distributions\. It instead uses a modelQQthat returns, for every prefix, a distribution Q\(⋅∣x<i\)Q\(\\cdot\\mid x\_\{<i\}\)overΣ\\Sigma, with ∑a∈ΣQ\(a∣x<i\)=1\\sum\_\{a\\in\\Sigma\}Q\(a\\mid x\_\{<i\}\)=1Returning 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: Q\(x1:n\)=∏i=1nQ\(xi∣x<i\)Q\(x\_\{1:n\}\) = \\prod\_\{i=1\}^n Q\(x\_i\\mid x\_\{<i\}\)Its cumulative logarithmic loss is LQ\(x1:n\)=∑i=1n−log⁡2Q\(xi∣x<i\)=−log⁡2Q\(x1:n\)\\begin\{aligned\} \\mathcal\{L\}\_Q\(x\_\{1:n\}\) &= \\sum\_\{i=1\}^n \-\\log\_2Q\(x\_i\\mid x\_\{<i\}\) \\\\ &= \-\\log\_2Q\(x\_\{1:n\}\) \\end\{aligned\}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](https://en.wikipedia.org/wiki/Arithmetic_coding)begins with the interval\[0,1\)\[0,1\)\. At positionii, it partitions the current interval into adjacent subintervals whose widths are proportional to Q\(⋅∣x<i\)Q\(\\cdot\\mid x\_\{<i\}\)and retains the subinterval assigned to the observed symbolxix\_i\. If the current interval has widthwi−1w\_\{i\-1\}, the selected interval has width wi=wi−1Q\(xi∣x<i\)w\_i = w\_\{i\-1\}Q\(x\_i\\mid x\_\{<i\}\)Starting fromw0=1w\_0=1, the final width is wn=∏i=1nQ\(xi∣x<i\)=Q\(x1:n\)w\_n = \\prod\_\{i=1\}^n Q\(x\_i\\mid x\_\{<i\}\) = Q\(x\_\{1:n\}\)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 −log⁡2Q\(x1:n\)\-\\log\_2Q\(x\_\{1:n\}\)plus a bounded coding overhead in the ideal arithmetic\-coding model\. Decoding repeats the same subdivisions\. After recoveringx<ix\_\{<i\}, the decoder evaluates the same distributionQ\(⋅∣x<i\)Q\(\\cdot\\mid x\_\{<i\}\), partitions its interval in the same order, and determines which subinterval contains the encoded value\. Encoder and decoder must begin from the same state, perform the same updates, use the same symbol ordering, and agree on where the sequence ends\. This proves one direction of the equivalence: a sequential probabilistic model can be converted into a lossless compressor whose ideal payload length is the model’s cumulative log\-loss\. The converse also holds\. A uniquely decodable compressor assigns lengths to complete strings, and those lengths induce probability weights\. After normalization, the resulting distribution can be factored into next\-symbol conditionals\.[*Language Modeling Is Compression*](https://arxiv.org/html/2309.10668v2)also constructs predictors directly from changes in compressed length when candidate symbols are appended to a prefix\. The equivalence is therefore not limited to compressors explicitly implemented as a probability model followed by arithmetic coding\. At a mathematical level, codes and probability assignments can be translated into one another\. This generality also limits what the equivalence tells us\. It applies after the possible objects, their serialization, and the information available to the decoder have been fixed\. It does not determine any of them\. The log\-loss measures the data encoded underQQ\. It does not yet account for howQQwas chosen or how the decoder obtains it\. ## The Source Is Unknown The identity above assumes that the modelQQis already available\. In practice, however, the source distribution is usually unknown and must be estimated from the same sequence we want to encode\. This raises a question: does empirical entropy describe a genuine property of the sequence, or only the probabilistic model we have fitted to it? We will reach the answer in two independent ways\. First, we will find the zero\-order distribution that assigns the observed sequence the smallest log\-loss\. Then we will discard the generative interpretation, fix only the observed symbol counts, and count how many sequences remain possible\. The two description lengths will differ by only a logarithmic number of bits\. ### Fitting a Zero\-Order Model Let S=s1,…,sn∈Σn,n≥1S=s\_1,\\ldots,s\_n\\in\\Sigma^n,\\qquad n\\geq 1be the observed sequence\. Consider first the family of zero\-order models, which use the same distribution at every position and ignore the preceding symbols\. Letq\(a\)q\(a\)be the probability assigned to a symbola∈Σa\\in\\Sigma\. The model assigns the complete sequence the probability q\(S\)=∏i=1nq\(si\)q\(S\) = \\prod\_\{i=1\}^n q\(s\_i\)Ifnan\_adenotes the number of occurrences ofaainSS, equal factors can be collected: q\(S\)=∏a∈Σq\(a\)naq\(S\) = \\prod\_\{a\\in\\Sigma\} q\(a\)^\{n\_a\}The corresponding logarithmic loss is −log⁡2q\(S\)=∑a∈Σnalog⁡21q\(a\)\-\\log\_2q\(S\) = \\sum\_\{a\\in\\Sigma\} n\_a\\log\_2\\frac\{1\}\{q\(a\)\}Once the sequence has been observed, the counts determine which distribution in this model family assigns it the smallest loss\. Define the empirical distribution P^S\(a\)=nan\\widehat\{P\}\_S\(a\) = \\frac\{n\_a\}\{n\}For any distributionqqthat assigns positive probability to every symbol occurring inSS, −log⁡2q\(S\)=∑a∈Σnalog⁡21q\(a\)=n∑a∈ΣP^S\(a\)log⁡21q\(a\)\\begin\{aligned\} \-\\log\_2q\(S\) &= \\sum\_\{a\\in\\Sigma\} n\_a\\log\_2\\frac\{1\}\{q\(a\)\} \\\\ &= n\\sum\_\{a\\in\\Sigma\} \\widehat\{P\}\_S\(a\) \\log\_2\\frac\{1\}\{q\(a\)\} \\end\{aligned\}Under the empirical distribution, the probability assigned to the complete sequence is P^S\(S\):=∏i=1nP^S\(si\)\\widehat\{P\}\_S\(S\) := \\prod\_\{i=1\}^n \\widehat\{P\}\_S\(s\_i\)Its logarithmic loss is −log⁡2P^S\(S\)=n∑a∈ΣP^S\(a\)log⁡21P^S\(a\)\-\\log\_2\\widehat\{P\}\_S\(S\) = n\\sum\_\{a\\in\\Sigma\} \\widehat\{P\}\_S\(a\) \\log\_2 \\frac\{1\}\{\\widehat\{P\}\_S\(a\)\}Subtracting the two quantities gives −log⁡2q\(S\)\+log⁡2P^S\(S\)=n∑a∈ΣP^S\(a\)log⁡2P^S\(a\)q\(a\)=nDKL\(P^S∥q\)≥0\\begin\{aligned\} \-\\log\_2q\(S\) \+ \\log\_2\\widehat\{P\}\_S\(S\) &= n\\sum\_\{a\\in\\Sigma\} \\widehat\{P\}\_S\(a\) \\log\_2 \\frac\{\\widehat\{P\}\_S\(a\)\}\{q\(a\)\} \\\\ &= nD\_\{\\mathrm\{KL\}\}\\left\(\\widehat\{P\}\_S \\mathbin\\Vert q\\right\) \\\\ &\\geq 0 \\end\{aligned\}Terms withP^S\(a\)=0\\widehat\{P\}\_S\(a\)=0contribute zero\. Since the divergence is non\-negative, no zero\-order distribution assigns the observed sequence a smaller log\-loss thanP^S\\widehat\{P\}\_S\. Equality holds exactly when q=P^Sq=\\widehat\{P\}\_SThe empirical frequencies are therefore the maximum\-likelihood estimate within the family of zero\-order models\. Equivalently, they minimize the in\-sample logarithmic loss over that family\. The resulting cost per symbol is the[zero\-order empirical entropy](https://arxiv.org/abs/0708.2084): H0\(S\)=∑a∈Σnanlog⁡2nna\\mathcal\{H\}\_0\(S\) = \\sum\_\{a\\in\\Sigma\} \\frac\{n\_a\}\{n\} \\log\_2\\frac\{n\}\{n\_a\}with the convention that terms for whichna=0n\_a=0contribute zero\. Multiplying bynngives nH0\(S\)=∑a∈Σnalog⁡2nna=−log⁡2P^S\(S\)n\\mathcal\{H\}\_0\(S\) = \\sum\_\{a\\in\\Sigma\} n\_a\\log\_2\\frac\{n\}\{n\_a\} = \-\\log\_2\\widehat\{P\}\_S\(S\)Unlike Shannon entropy,H0\(S\)\\mathcal\{H\}\_0\(S\)is not defined from a source distribution that exists independently of the data\. It is a property of the individual sequenceSS, obtained by fitting a zero\-order model to its observed symbol frequencies\. It does not assert that the sequence was generated by independent draws from that distribution\. ### Counting Sequences Instead We now ask whether essentially the same cost can be recovered without treating the empirical frequencies as a source distribution\. The binary case makes the counting argument explicit\. Consider a binary stringBBof lengthnncontaining exactlymmones\. If the decoder knowsnnandmm, thenBBbelongs to the family Bn,m=\{B∈\{0,1\}n:Bcontains exactlymones\}\\mathcal\{B\}\_\{n,m\} = \\left\\\{ B\\in\\\{0,1\\\}^n : B\\text\{ contains exactly \}m\\text\{ ones\} \\right\\\}A member of this family is determined by choosing whichmmpositions contain a one, so ∣Bn,m∣=\(nm\)\|\\mathcal\{B\}\_\{n,m\}\| = \\binom\{n\}\{m\}The counting bound from the first section says that identifying an arbitrary member of this family requires log⁡2\(nm\)\\log\_2\\binom\{n\}\{m\}bits, up to integer rounding\. For0<m<n0<m<n, set p=mnp=\\frac\{m\}\{n\}The endpoint casesm=0m=0andm=nm=ncontain only one binary string and have both counting bound and empirical entropy equal to zero\. Under the zero\-order model that assigns probabilityppto a one, every member ofBn,m\\mathcal\{B\}\_\{n,m\}receives the same probability: pm\(1−p\)n−m=\(mn\)m\(n−mn\)n−m=2−nH0\(B\)\\begin\{aligned\} p^m\(1\-p\)^\{n\-m\} &= \\left\(\\frac\{m\}\{n\}\\right\)^m \\left\(\\frac\{n\-m\}\{n\}\\right\)^\{n\-m\} \\\\ &= 2^\{\-n\\mathcal\{H\}\_0\(B\)\} \\end\{aligned\}The total probability assigned to the family is therefore \(nm\)2−nH0\(B\)\\binom\{n\}\{m\} 2^\{\-n\\mathcal\{H\}\_0\(B\)\}Since this probability cannot exceed one, \(nm\)2−nH0\(B\)≤1\\binom\{n\}\{m\} 2^\{\-n\\mathcal\{H\}\_0\(B\)\} \\leq 1and hence log⁡2\(nm\)≤nH0\(B\)\\log\_2\\binom\{n\}\{m\} \\leq n\\mathcal\{H\}\_0\(B\)For the reverse bound, consider the number of ones produced by the fitted Bernoulli model\. This count can take only then\+1n\+1values from00tonn\. Whenp=m/np=m/n, the countmmis a mode of the resulting binomial distribution\. Its probability is therefore at least the average probability of the possible counts: \(nm\)pm\(1−p\)n−m≥1n\+1\\binom\{n\}\{m\} p^m\(1\-p\)^\{n\-m\} \\geq \\frac\{1\}\{n\+1\}Substituting the expression in terms of empirical entropy gives \(nm\)2−nH0\(B\)≥1n\+1\\binom\{n\}\{m\} 2^\{\-n\\mathcal\{H\}\_0\(B\)\} \\geq \\frac\{1\}\{n\+1\}Taking logarithms yields nH0\(B\)−log⁡2\(n\+1\)≤log⁡2\(nm\)n\\mathcal\{H\}\_0\(B\) \- \\log\_2\(n\+1\) \\leq \\log\_2\\binom\{n\}\{m\}Together, nH0\(B\)−log⁡2\(n\+1\)≤log⁡2\(nm\)≤nH0\(B\)n\\mathcal\{H\}\_0\(B\) \- \\log\_2\(n\+1\) \\leq \\log\_2\\binom\{n\}\{m\} \\leq n\\mathcal\{H\}\_0\(B\)The two routes therefore differ by at mostlog⁡2\(n\+1\)\\log\_2\(n\+1\)bits\. Dividing bynn, their difference per symbol is at most log⁡2\(n\+1\)n,\\frac\{\\log\_2\(n\+1\)\}\{n\},which tends to zero\. The counting argument fixes the number of ones and distinguishes the binary strings that remain possible\. The probabilistic argument fits that same frequency and evaluates the observed string under it\. They begin from different assumptions but asymptotically assign the same cost per symbol\. Ifnnis known butmmis not, the value ofmmmust also be represented\. There aren\+1n\+1possible values, so a fixed\-width representation uses ⌈log⁡2\(n\+1\)⌉\\left\\lceil \\log\_2\(n\+1\) \\right\\rceilbits\. Once this cost is included, the counting and probabilistic descriptions agree within the same lower\-order term\. The same relation holds over a general alphabet\. Let the composition ofSSbe the vector \(na\)a∈Σ\(n\_a\)\_\{a\\in\\Sigma\}and consider its type class T\(na\)=\{T∈Σn:Tcontains exactlynaoccurrences of eacha∈Σ\}\\mathcal\{T\}\(n\_a\) = \\left\\\{ T\\in\\Sigma^n : T\\text\{ contains exactly \}n\_a\\text\{ occurrences of each \}a\\in\\Sigma \\right\\\}where∑a∈Σna=n\\sum\_\{a\\in\\Sigma\}n\_a=n\. A sequence in this class is obtained by choosing which positions contain each symbol, so ∣T\(na\)∣=n\!∏a∈Σna\!\|\\mathcal\{T\}\(n\_a\)\| = \\frac\{n\!\}\{\\prod\_\{a\\in\\Sigma\}n\_a\!\}Every sequence in this type class receives the same probability under the empirical distribution: P^S\(T\)=∏a∈Σna\>0\(nan\)na=2−nH0\(S\)\\begin\{aligned\} \\widehat\{P\}\_S\(T\) &= \\prod\_\{\\substack\{a\\in\\Sigma \\\\ n\_a\>0\}\} \\left\(\\frac\{n\_a\}\{n\}\\right\)^\{n\_a\} \\\\ &= 2^\{\-n\\mathcal\{H\}\_0\(S\)\} \\end\{aligned\}The total probability assigned to the type class is ∣T\(na\)∣2−nH0\(S\)\|\\mathcal\{T\}\(n\_a\)\| 2^\{\-n\\mathcal\{H\}\_0\(S\)\}Since this probability cannot exceed one, ∣T\(na\)∣≤2nH0\(S\)\|\\mathcal\{T\}\(n\_a\)\| \\leq 2^\{n\\mathcal\{H\}\_0\(S\)\}and therefore log⁡2n\!∏a∈Σna\!≤nH0\(S\)\\log\_2 \\frac\{n\!\}\{\\prod\_\{a\\in\\Sigma\}n\_a\!\} \\leq n\\mathcal\{H\}\_0\(S\)For the reverse direction, there are at most \(n\+1\)∣Σ∣\(n\+1\)^\{\|\\Sigma\|\}possible type vectors\. Under the multinomial distributionP^S\\widehat\{P\}\_S, the observed count vector\(na\)a∈Σ\(n\_a\)\_\{a\\in\\Sigma\}is a mode\. Its probability must therefore be at least the reciprocal of the number of possible types: ∣T\(na\)∣2−nH0\(S\)≥1\(n\+1\)∣Σ∣\|\\mathcal\{T\}\(n\_a\)\|2^\{\-n\\mathcal\{H\}\_0\(S\)\} \\geq \\frac\{1\}\{\(n\+1\)^\{\|\\Sigma\|\}\}Rearranging gives ∣T\(na\)∣≥2nH0\(S\)\(n\+1\)∣Σ∣\|\\mathcal\{T\}\(n\_a\)\| \\geq \\frac\{2^\{n\\mathcal\{H\}\_0\(S\)\}\}\{\(n\+1\)^\{\|\\Sigma\|\}\}Taking logarithms produces nH0\(S\)−∣Σ∣log⁡2\(n\+1\)≤log⁡2n\!∏a∈Σna\!≤nH0\(S\)n\\mathcal\{H\}\_0\(S\) \- \|\\Sigma\|\\log\_2\(n\+1\) \\leq \\log\_2 \\frac\{n\!\}\{\\prod\_\{a\\in\\Sigma\}n\_a\!\} \\leq n\\mathcal\{H\}\_0\(S\)This is the general form of the[method of types](https://ieeexplore.ieee.org/document/720546/)\. Thus the counting description and the fitted zero\-order log\-loss differ by at most∣Σ∣log⁡2\(n\+1\)\|\\Sigma\|\\log\_2\(n\+1\)bits\. For a fixed alphabet, the difference per symbol is at most ∣Σ∣log⁡2\(n\+1\)n,\\frac\{\|\\Sigma\|\\log\_2\(n\+1\)\}\{n\},and therefore vanishes asnngrows\. This is the precise sense in which zero\-order empirical entropy has both a probabilistic and a combinatorial interpretation\. ### Adding Context Zero\-order empirical entropy ignores order: rearranging the symbols leaves every countnan\_aunchanged\. To let the preceding symbols matter, fix a context length0≤k<n0\\leq k<n\. For each contextω∈Σk\\omega\\in\\Sigma^k, letSωS\_\\omegabe the sequence obtained by collecting, in their original order, all symbols that follow occurrences ofω\\omega\. EachSωS\_\\omegacan be fitted independently with its own zero\-order model\. The resultingkk\-th order empirical entropy is Hk\(S\)=1n∑ω∈Σk∣Sω∣\>0∣Sω∣H0\(Sω\)\.\\mathcal\{H\}\_k\(S\) = \\frac\{1\}\{n\} \\sum\_\{\\substack\{\\omega\\in\\Sigma^k \\\\ \|S\_\\omega\|\>0\}\} \|S\_\\omega\| \\mathcal\{H\}\_0\(S\_\\omega\)\.In other words, positions are grouped by their preceding context, and the zero\-order analysis is repeated inside each group\. To express this explicitly in terms of counts, fora∈Σa\\in\\Sigmaandω∈Σk\\omega\\in\\Sigma^kdefine nωa=∣\{i∈\{k\+1,…,n\}:si−k:i−1=ω,si=a\}∣n\_\{\\omega a\} = \\left\| \\left\\\{ i\\in\\\{k\+1,\\ldots,n\\\} : s\_\{i\-k:i\-1\}=\\omega,\\ s\_i=a \\right\\\} \\right\|and let nω=∑a∈Σnωan\_\\omega = \\sum\_\{a\\in\\Sigma\} n\_\{\\omega a\}be the number of symbols observed afterω\\omega\. Within this group, the empirical conditional distribution is P^S\(a∣ω\)=nωanω\\widehat\{P\}\_S\(a\\mid\\omega\) = \\frac\{n\_\{\\omega a\}\}\{n\_\\omega\}for every observed context withnω\>0n\_\\omega\>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ω\\omegais ∑a∈Σnωa\>0nωalog⁡2nωnωa\\sum\_\{\\substack\{a\\in\\Sigma \\\\ n\_\{\\omega a\}\>0\}\} n\_\{\\omega a\} \\log\_2 \\frac\{n\_\\omega\}\{n\_\{\\omega a\}\}Summing over the observed contexts gives nHk\(S\)=∑ω∈Σknω\>0∑a∈Σnωa\>0nωalog⁡2nωnωan\\mathcal\{H\}\_k\(S\) = \\sum\_\{\\substack\{\\omega\\in\\Sigma^k \\\\ n\_\\omega\>0\}\} \\sum\_\{\\substack\{a\\in\\Sigma \\\\ n\_\{\\omega a\}\>0\}\} n\_\{\\omega a\} \\log\_2 \\frac\{n\_\\omega\}\{n\_\{\\omega a\}\}which matches the[kk\-th order empirical entropy](https://arxiv.org/abs/0708.2084)under the boundary convention that only positions with a complete length\-kkcontext contribute to the sum\. The firstkksymbols have no complete length\-kkcontext\. They may be encoded separately as one block in ⌈log⁡2∣Σ∣k⌉=⌈klog⁡2∣Σ∣⌉\\left\\lceil \\log\_2\|\\Sigma\|^k \\right\\rceil = \\left\\lceil k\\log\_2\|\\Sigma\| \\right\\rceilbits, or handled through an agreed boundary convention\. Whenk=0k=0, there is only the empty context and the definition reduces toH0\(S\)\\mathcal\{H\}\_0\(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 everySωS\_\\omegais constant and H0\(Sω\)=0\\mathcal\{H\}\_0\(S\_\\omega\)=0for all observed contexts\. Consequently, Hk\(S\)=0\\mathcal\{H\}\_k\(S\)=0This always occurs atk=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 valueHk\(S\)=0\\mathcal\{H\}\_k\(S\)=0does not give a zero\-length lossless representation ofSS\. 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\. LetMMcontain everything the decoder needs to reproduce the probabilities used by the encoder\. A two\-part description has length L\(M,S\)=L\(M\)\+L\(S∣M\)L\(M,S\) = L\(M\)\+L\(S\\mid M\)The termL\(M\)L\(M\)describes the model\. The termL\(S∣M\)L\(S\\mid 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 inL\(S∣M\)L\(S\\mid M\)exceeds the additional cost of describingMM\. This is the basic two\-part form of the[minimum description length principle](https://doi.org/10.7551/mitpress/1114.003.0005)\. For the order\-kkmodel above, this cost is concrete\. A naïve dense table containsσk\\sigma^kcontexts andσ\\sigmacontinuation counts for each context\. Storing every count in a fixed\-width field gives an upper bound of σk\+1⌈log⁡2\(n\+1\)⌉\\sigma^\{k\+1\}\\left\\lceil\\log\_2\(n\+1\)\\right\\rceilbits\. 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*](https://arxiv.org/html/2309.10668v2#S3.SS2)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\. LetQi−1Q\_\{i\-1\}be the model available after the prefixs<is\_\{<i\}has been processed\. The ideal prequential length is Lpreq\(S\)=∑i=1n−log⁡2Qi−1\(si∣s<i\)L\_\{\\mathrm\{preq\}\}\(S\) = \\sum\_\{i=1\}^n \-\\log\_2 Q\_\{i\-1\}\(s\_i\\mid s\_\{<i\}\)After decodingsis\_i, the decoder performs the same update as the encoder and reconstructsQiQ\_i\. The final parameters therefore need not be transmitted\. The model cost is paid through the online log\-loss rather than through a separate description of the final parameters\. Before sufficient data have been observed, the current model will typically predict less well than a model fitted to the complete sequence\. More generally, the difference appears as prequential regret relative to that offline fit\. The initialization, update rule, training procedure, numerical conventions, and any randomness affecting them must be shared or described\. Any unshared information needed to reproduce the learning procedure must be added to the prequential length\. The data term also separates uncertainty in the source from mismatch in the model\. Suppose objects are generated according to a distributionPP, while the compressor assigns probabilities according toQQ\. IfQ\(x\)\>0Q\(x\)\>0wheneverP\(x\)\>0P\(x\)\>0, the expected ideal data length is the cross\-entropy H\(P,Q\)=−∑xP\(x\)log⁡2Q\(x\)H\(P,Q\) = \-\\sum\_x P\(x\)\\log\_2 Q\(x\)Subtracting the source entropy gives H\(P,Q\)−H\(P\)=∑xP\(x\)log⁡2P\(x\)Q\(x\)=DKL\(P∥Q\)\\begin\{aligned\} H\(P,Q\)\-H\(P\) &= \\sum\_x P\(x\)\\log\_2\\frac\{P\(x\)\}\{Q\(x\)\} \\\\ &= D\_\{\\mathrm\{KL\}\}\(P\\mathbin\\Vert Q\) \\end\{aligned\}and therefore H\(P,Q\)=H\(P\)\+DKL\(P∥Q\)H\(P,Q\) = H\(P\)\+D\_\{\\mathrm\{KL\}\}\(P\\mathbin\\Vert Q\)For sequential distributions, relative entropy decomposes across positions: DKL\(P1:n∥Q1:n\)=∑i=1nEX<i∼P\[DKL\(P\(⋅∣X<i\)∥Q\(⋅∣X<i\)\)\]D\_\{\\mathrm\{KL\}\}\\left\(P\_\{1:n\}\\mathbin\\Vert Q\_\{1:n\}\\right\) = \\sum\_\{i=1\}^n \\mathbb\{E\}\_\{X\_\{<i\}\\sim P\} \\left\[ D\_\{\\mathrm\{KL\}\} \\left\( P\(\\cdot\\mid X\_\{<i\}\) \\mathbin\\Vert Q\(\\cdot\\mid X\_\{<i\}\) \\right\) \\right\]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 sourcePP, improvingQQunder expected logarithmic loss means reducing the cross\-entropyH\(P,Q\)H\(P,Q\), equivalently reducing the mismatch termDKL\(P∥Q\)D\_\{\\mathrm\{KL\}\}\(P\\mathbin\\Vert Q\)\. It does not changeH\(P\)H\(P\)\. The[ngrok article](https://ngrok.com/blog/compression-is-prediction)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\. IfQSQ\_Sis fitted to an observed sequenceSS, minimizing its in\-sample log\-loss does not imply that it will minimize log\-loss on future data\. For a future distributionRR, EX∼R\[−log⁡2QS\(X\)\]=H\(R\)\+DKL\(R∥QS\)\.\\mathbb\{E\}\_\{X\\sim R\}\\left\[\-\\log\_2 Q\_S\(X\)\\right\] = H\(R\)\+D\_\{\\mathrm\{KL\}\}\(R\\mathbin\\Vert Q\_S\)\.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](https://github.com/lukefleed/compressed-intvec) A=\(a0,…,an−1\)A=\(a\_0,\\ldots,a\_\{n\-1\}\)whose values belong to\{0,…,u−1\}\\\{0,\\ldots,u\-1\\\}\. Let b=⌈log⁡2u⌉b=\\lceil\\log\_2 u\\rceilA bit\-packed representation assigns exactlybbconsecutive bits to each value, usingnbnbbits for the payload apart from alignment and metadata\. The representation ofaia\_ibegins at bit positionibib\. If the storage\-word width isw≥bw\\geq b, recoveringaia\_irequires reading at most two adjacent words, shifting their contents, and applying a mask\. The addresses and shifts are computed directly fromii, so access takesO\(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: L\(A∣M\)≈∑i=0n−1−log⁡2Q\(ai∣a<i\)L\(A\\mid M\) \\approx \\sum\_\{i=0\}^\{n\-1\} \-\\log\_2 Q\(a\_i\\mid a\_\{<i\}\)The shorter stream provides a different access contract\. In an ordinary arithmetic\-coded stream, the decoding state at positioniidepends on the symbols that precede it\. If the model also uses their context, its next distribution depends on the same prefix\. Recoveringaia\_irequires 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 sizeuu, 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 encodingEEand a decoderDDsatisfying D\(E\(A\)\)=AD\(E\(A\)\)=AOnce 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 Access⁡\(R\(A\),i\)=ai\\operatorname\{Access\}\(R\(A\),i\)=a\_iwithout first reconstructing all ofAA\. 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 min⁡R∣R\(A\)∣subject toTAccess⁡\(R\)≤t\\min\_R \|R\(A\)\| \\qquad \\text\{subject to\} \\qquad T\_\{\\operatorname\{Access\}\}\(R\)\\leq tfor a chosen access\-time boundtt\. 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 QC\(x\)=2−ℓC\(x\)SC,Q\_C\(x\)=\\frac\{2^\{\-\\ell\_C\(x\)\}\}\{S\_C\},and its codeword lengths satisfy ℓC\(x\)=−log⁡2QC\(x\)−log⁡2SC\.\\ell\_C\(x\)=\-\\log\_2Q\_C\(x\)\-\\log\_2S\_C\.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\.