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 $x_{1:n}$ and a model $Q$, 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.

Table of Contents

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 $x$ has been fixed, the most permissive effective descriptions are programs that produce it. After choosing a universal machine $U$, the Kolmogorov complexity of a binary string $x$ is

Thus, $K_U(x)$ is the length of the shortest program that outputs $x$. 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 $U$ 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 $U$ and $V$, there is a constant $c_{U,V}$ such that

for every string $x$. The constant may depend on the two machines, but not on $x$. 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 $K_U$ 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 $\mathcal{F}$. Once $\mathcal{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 $C$ to be injective. Since only $2^\ell$ binary strings of length $\ell$ exist, injectivity implies

and therefore

An agreed enumeration of $\mathcal{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|\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 family $\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 family $\mathcal{G}$, then the representation must distinguish among the members of $\mathcal{G}$ instead. The lower bound becomes

A restriction from $\mathcal{G}$ to $\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.

Let $\mathcal{X}$ be a finite set of possible objects. For each $x\in\mathcal{X}$, a source specifies a probability

where $P(x)>0$ and

A probability must be translated into a quantity measured in bits. If two independent outcomes occur with probabilities $P(x)$ and $P(y)$, their joint probability is the product $P(x)P(y)$, while their bit costs should add. The logarithm performs this conversion. The information content of an outcome $x$ is

An event with probability $2^{-b}$ has information content $b$ 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 $P$ is uniform, every object has information content

so Shannon entropy equals the counting bound of the family.

The values $I_P(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)$, 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 $m$ be at least as large as the longest codeword. A codeword of length $\ell_C(x)$ has

descendants at depth $m$. Since no codeword is a prefix of another, the sets of descendants belonging to distinct codewords are disjoint. The complete binary tree contains only $2^m$ nodes at depth $m$, so

Dividing by $2^m$ 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^{-\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,

and therefore

The ideal lengths $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 code $C$, define its Kraft sum

The Kraft–McMillan inequality gives $S_C\leq1$. The quantities $2^{-\ell_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 $Q_C$, shifted by the same non-negative amount $-\log_2S_C$. When the Kraft inequality is tight, so that $S_C=1$, the correspondence is exact:

A fixed-length code is the simplest instance. If every object receives the same length, then every value $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

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 $S_C\leq1$. 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_2S_C$ 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^{-\ell(x)}\leq P(x)$, these lengths satisfy the Kraft–McMillan inequality and can therefore be realized by a prefix code. Moreover,

so averaging under $P$ 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 $r$ independent outcomes drawn from $P$, the same construction gives an expected block length smaller than $rH(P)+1$. The excess per source symbol is therefore less than $1/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)$ replaced by the corresponding block entropy.

Up to this point, each value $x\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

over an alphabet $\Sigma$. Write

for the prefix before position $i$. 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$ 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 $i$ after the prefix is known.

A compressor rarely knows the true conditional distributions. It instead uses a model $Q$ 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)$. At position $i$, it partitions the current interval into adjacent subintervals whose widths are proportional to

and retains the subinterval assigned to the observed symbol $x_i$.

If the current interval has width $w_{i-1}$, the selected interval has width

Starting from $w_0=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_{<i}$, the decoder evaluates the same distribution $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 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 under $Q$. It does not yet account for how $Q$ was chosen or how the decoder obtains it.

The Source Is Unknown

The identity above assumes that the model $Q$ is 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

be the observed sequence. Consider first the family of zero-order models, which use the same distribution at every position and ignore the preceding symbols. Let $q(a)$ be the probability assigned to a symbol $a\in\Sigma$. The model assigns the complete sequence the probability

If $n_a$ denotes the number of occurrences of $a$ in $S$, equal factors can be collected:

The corresponding logarithmic loss is

Once the sequence has been observed, the counts determine which distribution in this model family assigns it the smallest loss. Define the empirical distribution

For any distribution $q$ that assigns positive probability to every symbol occurring in $S$,

Under the empirical distribution, the probability assigned to the complete sequence is

Its logarithmic loss is

Subtracting the two quantities gives

Terms with $\widehat{P}_S(a)=0$ contribute zero. Since the divergence is non-negative, no zero-order distribution assigns the observed sequence a smaller log-loss than $\widehat{P}_S$. Equality holds exactly when

The 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:

with the convention that terms for which $n_a=0$ contribute zero. Multiplying by $n$ gives

Unlike Shannon entropy, $\mathcal{H}_0(S)$ is not defined from a source distribution that exists independently of the data. It is a property of the individual sequence $S$, 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 string $B$ of length $n$ containing exactly $m$ ones. If the decoder knows $n$ and $m$, then $B$ belongs to the family

A member of this family is determined by choosing which $m$ positions contain a one, so

The counting bound from the first section says that identifying an arbitrary member of this family requires

bits, up to integer rounding.

For $0<m<n$, set

The endpoint cases $m=0$ and $m=n$ contain only one binary string and have both counting bound and empirical entropy equal to zero. Under the zero-order model that assigns probability $p$ to a one, every member of $\mathcal{B}_{n,m}$ receives the same probability:

The total probability assigned to the family is therefore

Since this probability cannot exceed one,

and hence

For the reverse bound, consider the number of ones produced by the fitted Bernoulli model. This count can take only the $n+1$ values from $0$ to $n$. When $p=m/n$, the count $m$ is a mode of the resulting binomial distribution. Its probability is therefore at least the average probability of the possible counts:

Substituting the expression in terms of empirical entropy gives

Taking logarithms yields

Together,

The two routes therefore differ by at most $\log_2(n+1)$ bits. Dividing by $n$, their difference per symbol is at most

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.

If $n$ is known but $m$ is not, the value of $m$ must also be represented. There are $n+1$ possible values, so a fixed-width representation uses

bits. 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 of $S$ be the vector

and consider its type class

where $\sum_{a\in\Sigma}n_a=n$. A sequence in this class is obtained by choosing which positions contain each symbol, so

Every sequence in this type class receives the same probability under the empirical distribution:

The total probability assigned to the type class is

Since this probability cannot exceed one,

and therefore

For the reverse direction, there are at most

possible type vectors. Under the multinomial distribution $\widehat{P}_S$, the observed count vector $(n_a)_{a\in\Sigma}$ is a mode. Its probability must therefore be at least the reciprocal of the number of possible types:

Rearranging gives

Taking logarithms produces

This is the general form of the method of types. Thus the counting description and the fitted zero-order log-loss differ by at most $|\Sigma|\log_2(n+1)$ bits. For a fixed alphabet, the difference per symbol is at most

and therefore vanishes as $n$ grows. 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 count $n_a$ unchanged. To let the preceding symbols matter, fix a context length $0\leq k<n$. For each context $\omega\in\Sigma^k$, let $S_\omega$ be the sequence obtained by collecting, in their original order, all symbols that follow occurrences of $\omega$.

Each $S_\omega$ can be fitted independently with its own zero-order model. The resulting $k$-th order empirical entropy is

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, for $a\in\Sigma$ and $\omega\in\Sigma^k$ define

and let

be the number of symbols observed after $\omega$.

Within this group, the empirical conditional distribution is

for every observed context with $n_\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 $\omega$ is

Summing over the observed contexts gives

which matches the $k$-th order empirical entropy under the boundary convention that only positions with a complete length-$k$ context contribute to the sum.

The first $k$ symbols have no complete length-$k$ context. They may be encoded separately as one block in

bits, or handled through an agreed boundary convention. When $k=0$, there is only the empty context and the definition reduces to $\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 every $S_\omega$ is constant and

for all observed contexts. Consequently,

This always occurs at $k=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 $\mathcal{H}_k(S)=0$ does not give a zero-length lossless representation of $S$. 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 $M$ contain everything the decoder needs to reproduce the probabilities used by the encoder. A two-part description has length

The term $L(M)$ describes the model. The term $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 in $L(S\mid M)$ exceeds the additional cost of describing $M$. This is the basic two-part form of the minimum description length principle.

For the order-$k$ model above, this cost is concrete. A naïve dense table contains $\sigma^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 $Q_{i-1}$ be the model available after the prefix $s_{<i}$ has been processed. The ideal prequential length is

After decoding $s_i$, the decoder performs the same update as the encoder and reconstructs $Q_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 distribution $P$, while the compressor assigns probabilities according to $Q$. If $Q(x)>0$ whenever $P(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 $P$, improving $Q$ under expected logarithmic loss means reducing the cross-entropy $H(P,Q)$, equivalently reducing the mismatch term $D_{\mathrm{KL}}(P\mathbin\Vert Q)$. It does not change $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 $Q_S$ is fitted to an observed sequence $S$, minimizing its in-sample log-loss does not imply that it will minimize log-loss on future data. For a future distribution $R$,

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

whose values belong to $\{0,\ldots,u-1\}$. Let

A bit-packed representation assigns exactly $b$ consecutive bits to each value, using $nb$ bits for the payload apart from alignment and metadata. The representation of $a_i$ begins at bit position $ib$. If the storage-word width is $w\geq b$, recovering $a_i$ requires reading at most two adjacent words, shifting their contents, and applying a mask. The addresses and shifts are computed directly from $i$, so access takes $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 $i$ depends on the symbols that precede it. If the model also uses their context, its next distribution depends on the same prefix. Recovering $a_i$ 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 $u$, 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 $E$ and a decoder $D$ 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 $A$.

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 $t$.

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.