A compressor has a stage act and a back office.

The stage act finds repeated strings, predicts pixels, learns token contexts, builds dictionaries, transforms blocks, and decides what the data is trying to be. The back office does colder work. It receives a sequence of probabilities and has to turn them into bits exactly.

That second part is entropy coding.

It is easy to underappreciate because it sounds like bookkeeping. But the bookkeeping is the contract. If a predictor says the next symbol has probability \(p\), the ideal price of observing that symbol is

\[\log_2 \frac{1}{p}\]

bits. Common symbols are cheap. Surprises are expensive. Shannon’s 1948 theory made this average price precise through entropy, and that number remains the center of gravity for lossless compression.1

Then the awkward part arrives: bits are integers, while surprise is not.

If the model says \(p=0.3\), the price is about \(1.737\) bits. No one can write 0.737 of a bit after a symbol in an ordinary prefix code. Huffman coding solves the best integer-length prefix-code problem for a known distribution, but each individual codeword still has an integer length.2 Arithmetic coding and ANS take a stranger route: stop assigning a separate little bit string to each symbol. Let the whole message share the fractional accounting.

This post is about where those fractional bits go.

Three Bills on the Table

A useful way to look at a compressor is to put three bills on the table.

The first bill comes from the source. This is the actual process generating data. It may be English text, sensor deltas, token IDs, transformed image residuals, or something uglier. It has some true distribution \(P\), even if no one knows it.

The second bill comes from the model. This is what the compressor believes. Call it \(Q\). If the model is wrong, the expected number of ideal bits is not \(H(P)\) but the cross entropy

\[H(P, Q) = -\sum_x P(x)\log_2 Q(x).\]

The gap

\[H(P,Q)-H(P)=D_{\mathrm{KL}}(P \| Q)\]

is the price of using the wrong probabilities. The coder cannot rescue that mistake. It can only spend the probabilities it is given.

The third bill belongs to the coder. It has to represent the sequence in a finite bitstream and decode it exactly. This is where Huffman, arithmetic coding, range coding, and asymmetric numeral systems live.

The distinction matters because people often say “compression” when they mean all three bills at once. A better predictor reduces cross entropy. A better entropy coder reduces the overhead between the probability bill and the bits that actually hit disk.

Those are different wins.

The Half-Bit Problem

Suppose a four-symbol source has probabilities:

A: 0.5
B: 0.25
C: 0.125
D: 0.125

This distribution is friendly to binary prefix codes. The ideal prices are 1, 2, 3, and 3 bits. Huffman can hit them exactly.

Now change the probabilities:

A: 0.56
B: 0.18
C: 0.10
D: 0.07
E: 0.05
F: 0.04

The ideal prices are no longer integers. Huffman still builds the optimal prefix code for the symbol alphabet, but it has to pour the distribution into whole codeword lengths. Coding blocks of two or three symbols can reduce the rounding, because the fractional parts average out across a larger object. That is real and useful. It is also a hint: per-symbol codewords are the wrong primitive once the model is good enough to deserve fractional prices.

Arithmetic coding replaces codewords with a shrinking interval. Each symbol selects a subinterval whose width is proportional to its probability. After the whole message, any binary fraction inside the final interval identifies the message. Witten, Neal, and Cleary’s classic exposition emphasized this separation between the statistical model and the channel encoding: the model supplies probabilities, while the arithmetic coder turns those probabilities into a compact representation.3

The idea had already been developed through Rissanen and Langdon’s arithmetic coding work, and Howard and Vitter later gave a careful implementation-oriented treatment of how finite-precision coders keep the overhead negligible in practice.45

The final interval width is essentially

\[\prod_{t=1}^{n} Q(x_t),\]

so the number of bits needed is close to

\[-\sum_{t=1}^{n} \log_2 Q(x_t).\]

The fractional bits did not disappear. They were allowed to pool.

A Workbench for Tiny Surprises

The lab below uses deterministic synthetic sources. It builds a coder model, quantizes it into integer frequencies, encodes the sampled sequence with a byte-renormalized rANS coder, decodes it, and compares the result with ideal cross entropy and Huffman baselines.

The rANS implementation is intentionally small, but it is doing the real move: a single integer state is updated by the symbol’s cumulative frequency and renormalized by flushing bytes. The test is unforgiving. If the decoder does not reproduce the exact original sequence, the round-trip metric turns red.

Source probabilities Coder probabilities Arithmetic and rANS accounting Huffman and byte flushes

The rANS stream stores payload bytes plus a 32-bit final state. Short messages visibly pay that state overhead; longer messages reveal the asymptotic code rate.

Try four moves.

First, choose Dyadic toy and set model mismatch to zero. Huffman looks nearly smug here because the probabilities match powers of two. There is little fractional accounting to pool.

Second, switch back to Service log. The single-symbol Huffman code spends integer lengths, while the ideal and rANS ledgers can track fractional surprise across the whole message. The block Huffman rows show why grouping helps: a larger alphabet lets integer codeword lengths approximate fractional prices more finely.

Third, raise model mismatch. The source entropy barely moves because the source did not change. Cross entropy rises because the coder is now budgeting against the wrong distribution. This is the cleanest place to see the predictor-coder separation. A perfect entropy coder cannot undo a bad probability forecast.

Fourth, lower frequency table precision. ANS and arithmetic coders are usually implemented with integer frequency tables, not Platonic real-valued probabilities. Coarse tables perturb the model. The penalty is often small, but it is not zero, and rare symbols are where the quantization hurts first.

ANS Loads the Stack Backward

Arithmetic coding is often explained with intervals. ANS is often explained with a state.

The rANS variant used in the lab keeps a single integer \(x\). To encode a symbol \(s\) with frequency \(f_s\) and cumulative count \(c_s\) in a table of size \(M\), the core update has the shape

\[x' = M\left\lfloor \frac{x}{f_s}\right\rfloor + (x \bmod f_s) + c_s.\]

The details around this formula keep \(x\) in a fixed range by flushing low bytes into the bitstream. But the information-theoretic meaning is simple: encoding a symbol with probability about \(f_s/M\) increases the log-size of the state by roughly

\[\log_2 \frac{M}{f_s}.\]

That is the same surprise ledger.

Duda’s ANS papers framed the method as a way to combine arithmetic-coding-like compression rates with a simpler single-state mechanism.6 The bargain is beautifully odd. rANS encoding runs backward through the message, and decoding recovers symbols forward. The bitstream behaves like a stack: bytes flushed while encoding later symbols are consumed when decoding earlier state transitions.

This is not just a toy curiosity. Zstandard’s format uses Huffman coding for literals and finite state entropy, an ANS-family method, for other symbol streams and for Huffman headers. The RFC explicitly notes that FSE carries a state across symbols and is decoded in the opposite direction from encoding.7

The back office is everywhere.

The Coder Is Not the Prophet

The entropy coder is only as good as its probabilities. That sounds like a limitation, but it is also why compression keeps reappearing as a lens on machine learning.

A next-token language model is a probability model. If both encoder and decoder can reproduce the same conditional probabilities, an entropy coder can turn the observed token sequence into about

\[\sum_t -\log_2 p_\theta(x_t \mid x_{<t})\]

bits. This is the mechanical bridge behind the phrase “language modeling is compression.” Del’etang et al. used that equivalence to evaluate large models as general-purpose compressors, not because a Transformer is secretly a zip file, but because prediction quality can be cashed out through a lossless coder.8

The bridge has conditions. The decoder must see the same context and reproduce the same probabilities. Tokenization matters. Numerical determinism matters. The model itself is not free to transmit. And a compressor that burns enormous compute to save a few bits may be scientifically interesting while being economically silly.

Still, the equivalence is clarifying. Cross-entropy loss is not just a training metric with a nice gradient. It is the expected code length of the data under the model, up to the mechanics of the coder.

The Receipt Has to Decode

Entropy coding has a precise kind of humility.

It cannot discover structure that the model failed to assign probability to. It cannot make a wrong distribution cheap. It cannot compress uniform randomness. It cannot make finite messages ignore headers, states, tables, checksums, or container overhead.

What it can do is more exact:

given the same probability ledger on both sides,
turn surprise into a reversible bitstream

That is why the lab’s round trip is the most important metric. Compression is not a mood. Every saved bit must still leave enough information for the decoder to walk the machine backward.

Huffman makes the receipt out of prefix codewords. Arithmetic coding makes it out of a nested interval. ANS makes it out of a state that grows when it absorbs surprise and shrinks when it gives bytes back.

Different machines. Same bill.

  1. Claude E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal, 1948. ↩

  2. David A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the IRE, 1952. ↩

  3. Ian H. Witten, Radford M. Neal, and John G. Cleary, “Arithmetic Coding for Data Compression”, Communications of the ACM, 1987. ↩

  4. Jorma Rissanen and Glen G. Langdon Jr., “Arithmetic Coding”, IBM Journal of Research and Development, 1979. ↩

  5. Paul G. Howard and Jeffrey Scott Vitter, “Arithmetic Coding for Data Compression”, Proceedings of the IEEE, 1994. ↩

  6. Jarek Duda, “Asymmetric Numeral Systems: Entropy Coding Combining Speed of Huffman Coding with Compression Rate of Arithmetic Coding”, arXiv, 2013. ↩

  7. Yann Collet and Murray Kucherawy, “Zstandard Compression and the ‘application/zstd’ Media Type”, RFC 8878, 2021. ↩

  8. Gregoire Del’etang et al., “Language Modeling Is Compression”, ICLR 2024. ↩