Learn · Intermediate

Arithmetic coding: turning a model's probabilities into a compressed message

Arithmetic coding is a lossless method for turning a sequence of probability predictions into a compact string of bits. It matters for AI because it makes a deep claim precise: if a language model consistently assigns more probability to the text that actually appears, it can encode that text in fewer bits. That is why compression is a meaningful, though incomplete, lens for model quality.

Suppose a model is about to see one of four symbols. It predicts A with probability one half, B with one quarter, C with one eighth and D with one eighth. A conventional fixed-width code would use two bits for each symbol because four choices are possible. A good probability-aware code can use roughly one bit for A, two for B and three for C or D. Common things get short descriptions; surprising things need longer descriptions. This is not an arbitrary trick: the ideal length for an event with probability p is approximately -log2(p) bits.

Arithmetic coding improves on assigning a separate bit string to each token. It starts with the real-number interval from zero to one. The model's probability distribution divides that interval into pieces: perhaps A occupies [0, 0.5), B [0.5, 0.75), C [0.75, 0.875), and D [0.875, 1). After seeing B, the encoder keeps B's quarter of the interval. For the next symbol, it divides only that surviving interval in the same predicted proportions. After a whole message, any number inside the final tiny interval identifies the entire sequence. The encoder sends enough bits to identify such a number; the decoder repeats the same probability divisions and recovers every symbol exactly.

The best analogy is giving directions on a map. A one-token code gives every destination a separately labeled road sign. Arithmetic coding repeatedly zooms the map: first into the region the model expects, then into a neighborhood, then a street and a house. A very probable path occupies a wide region at each zoom and needs few instructions. An unexpected path ends in a narrow region and needs more precision. Crucially, no information is lost. Given the same probability model and the transmitted bits, the decoder takes exactly the same turns.

John Witten, Radford Neal and John Cleary's 1987 paper established arithmetic coding as a practical data-compression technique. Modern language-model discussions use the same principle in reverse: an autoregressive model produces a distribution for the next token; an arithmetic or range coder can turn that distribution into a compressed representation. If the model thinks the next token has probability 0.25, identifying it costs about two bits. If it gives the actual token probability 1/1024, the event costs about ten bits. The total negative log probability, often called cross-entropy, is therefore a code length. See softmax and cross-entropy for how those probabilities are produced and perplexity for the more familiar evaluation number derived from average code length.

This connection is central to the gzip experiment in today's news story. Nathan Barry's program uses a compressor's output length to rank continuations. The general idea is sound, and Delétang and colleagues explain that any compressor can induce a conditional generative model. But arithmetic coding also clarifies the limitation. It does not make a bad probability model good. A neural language model can assign probability using learned, distributed representations of syntax, meaning and faraway context; gzip uses a short window of repeated bytes. Both can yield a code length. Their code lengths reflect radically different predictive machinery.

A few practical subtleties matter. First, the encoder and decoder must share exactly the same model and numerical rules. Tiny differences in tokenization, floating-point rounding or model version can make decoding fail. Production systems often use integer-frequency range coders rather than literal real-number intervals so that arithmetic is stable and fast. Second, a sequence's compressed size includes enough information to reconstruct it, not an estimate of the model's parameter size or training cost. A huge model may compress a file well while itself requiring enormous storage. Third, text compression measures prediction on a particular distribution. A model can compress web prose well and still fail at truth, safety, planning or a specialized task.

This gives a disciplined way to read claims such as “compression is language modeling.” The claim is true at the level of prediction and code length: better calibrated next-symbol probabilities give shorter expected messages. It is false if turned into “every compressor has a language model's knowledge” or “one compression score captures intelligence.” Arithmetic coding is the bridge between the true statement and the overreach. It rewards a model for putting probability mass where reality goes, one symbol at a time; it does not tell us why the model made that prediction or whether its answer is useful in the world.

Ground Truth. (2026, September 23). Arithmetic coding: turning a model's probabilities into a compressed message. Ground Truth. https://groundtruth.day/learn/arithmetic-coding-probabilities-into-bits.html

@misc{groundtruth:arithmetic-coding-probabilities-into-bits,
  title  = {Arithmetic coding: turning a model's probabilities into a compressed message},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {sep},
  url    = {https://groundtruth.day/learn/arithmetic-coding-probabilities-into-bits.html}
}

Topics: compression · language-models · probability · information-theory · evaluation