Arithmetic Coding, in depth: interval narrowing, integer renormalization with pending bits, a tested adaptive coder, models, termination and LLM-driven compression

A message is an interval

Give each symbol a slice of [0, 1) whose width equals its probability. With A = 1/2, B = 1/4 and C = 1/4, the slices are A [0, 0.5), B [0.5, 0.75) and C [0.75, 1). To encode a symbol, replace the current interval with that symbol's slice, scaled to fit inside the current interval.

Encode B, A, C. B narrows [0, 1) to [0.5, 0.75). A takes the first half of that: [0.5, 0.625). C takes the last quarter: [0.59375, 0.625). The final width is 1/4 × 1/2 × 1/4 = 1/32, the product of the probabilities. Any number inside the final interval identifies the message, given its length or an end marker. The binary fraction 0.10011 equals 0.59375 exactly, and every longer string that starts 10011 stays below 0.625, so five bits suffice. That matches the information content: −log₂(1/32) = 5 bits.

Decoding reverses it. The decoder sees 0.59375, which lies in B's slice of [0, 1), so the first symbol is B. It rescales to B's interval and asks again: 0.59375 lies in the A part of [0.5, 0.75). Then it is in the C part of [0.5, 0.625). The decoder must use exactly the same probabilities as the encoder at every step; that one requirement drives most of the engineering below.

From interval to bits

In general, a final interval of width W needs about −log₂ W bits, plus at most two to pick a binary number that lies safely inside it. Because W is the product of the probabilities, −log₂ W is the sum of each symbol's information content. Arithmetic coding therefore achieves the model's entropy within two bits for the whole message, not two bits per symbol. The coding is no longer the bottleneck; the model is. A better model, meaning better probabilities, directly gives smaller output.

Finite precision and renormalization

Real coders cannot keep an exact fraction that grows by a few bits per symbol. They use fixed-width integers: low and high hold the interval's ends as 32-bit values, and the coder renormalizes whenever it can, shifting out bits that are already decided. There are three cases, often called E1, E2 and E3.

• E1: the whole interval is in the lower half. The next output bit is 0 regardless of what follows, so emit 0 and double the interval.
• E2: the whole interval is in the upper half. Emit 1, subtract half, then double.
• E3: the interval straddles the midpoint but lies within the middle half, between one quarter and three quarters. The next bit is not known yet, but it will be followed by its opposite. Count a pending bit, subtract a quarter and double. When the next E1 or E2 bit comes out, write the pending opposites after it.

Without E3, an interval that straddles the midpoint could shrink until it is narrower than one integer unit, and the coder would lose the ability to distinguish symbols. That failure is called underflow, and the pending-bit counter is the cure.

After renormalization the interval is always wider than a quarter of the full range. That gives the precision contract: the model's total frequency must not exceed a quarter of the range, or a frequency-1 symbol could get a slice of width zero. With 32-bit registers the total must stay at or below 2³⁰, and products such as range * cum_freq need 64-bit arithmetic in C. The model in the code below halves all counts when the total grows past that limit.

The encoder

Here is a complete adaptive coder in Python. Python integers do not overflow, but the logic is the same as a C version with 64-bit products. An extra symbol marks end of file.

PREC = 32
FULL = (1 << PREC) - 1
HALF = 1 << (PREC - 1)
QUARTER = 1 << (PREC - 2)
MAX_TOTAL = QUARTER          # keeps every symbol's slice at least 1 wide

class AdaptiveModel:
    def __init__(self, nsym, step=32):
        self.freq = [1] * nsym   # start at 1: no symbol may ever have zero width
        self.step = step
    def total(self):
        return sum(self.freq)
    def interval(self, s):
        lo = sum(self.freq[:s])
        return lo, lo + self.freq[s], self.total()
    def find(self, target):
        lo = 0
        for s, f in enumerate(self.freq):
            if target < lo + f:
                return s, lo, lo + f
            lo += f
        raise ValueError("target outside total")
    def update(self, s):
        self.freq[s] += self.step
        if self.total() > MAX_TOTAL:
            self.freq = [max(1, f >> 1) for f in self.freq]

def encode(symbols, nsym):
    model, eof = AdaptiveModel(nsym + 1), nsym
    low, high, pending, out = 0, FULL, 0, []
    def emit(bit):
        nonlocal pending
        out.append(bit)
        out.extend([1 - bit] * pending)
        pending = 0
    for s in list(symbols) + [eof]:
        lo, hi, tot = model.interval(s)
        rng = high - low + 1
        high = low + rng * hi // tot - 1
        low = low + rng * lo // tot
        while True:
            if high < HALF:
                emit(0)
            elif low >= HALF:
                emit(1); low -= HALF; high -= HALF
            elif low >= QUARTER and high < HALF + QUARTER:
                pending += 1; low -= QUARTER; high -= QUARTER   # E3
            else:
                break
            low, high = 2 * low, 2 * high + 1
        model.update(s)
    pending += 1                  # two final bits pin a point inside [low, high]
    emit(0 if low < QUARTER else 1)
    return out

Note that high is inclusive, which is why the code adds 1 to the range and subtracts 1 from the new high. Mixing inclusive and exclusive conventions is the most common source of a coder that works on short inputs and fails on long ones.

The decoder

The decoder keeps the same low and high plus a value register holding the next 32 bits of input. At each step it computes which cumulative frequency value corresponds to, finds the symbol, and then performs the same narrowing and renormalization as the encoder, shifting in a new bit wherever the encoder shifted one out.

def decode(bits, nsym):
    model, eof = AdaptiveModel(nsym + 1), nsym
    it = iter(bits)
    nextbit = lambda: next(it, 0)          # past the end, read zeros
    low, high, value = 0, FULL, 0
    for _ in range(PREC):
        value = (value << 1) | nextbit()
    out = []
    while True:
        tot = model.total()
        rng = high - low + 1
        target = ((value - low + 1) * tot - 1) // rng
        s, lo, hi = model.find(target)
        if s == eof:
            return out
        out.append(s)
        high = low + rng * hi // tot - 1
        low = low + rng * lo // tot
        while True:
            if high < HALF:
                pass
            elif low >= HALF:
                low -= HALF; high -= HALF; value -= HALF
            elif low >= QUARTER and high < HALF + QUARTER:
                low -= QUARTER; high -= QUARTER; value -= QUARTER
            else:
                break
            low, high = 2 * low, 2 * high + 1
            value = 2 * value + nextbit()
        model.update(s)

Tested by round-tripping 304 messages, including the empty message, a single symbol, 5,000 repeats of one symbol, and random messages over 2- to 256-symbol alphabets with varied skew. On 100,000 binary symbols with P(0) = 0.95, it produced 0.286 bits per symbol, matching the source entropy of 0.286. Huffman would need a full bit per symbol for the same input unless symbols were grouped into blocks.

Models

The coder is generic; compression comes from the model. Three designs cover most uses.

• Adaptive frequency counts, as above. For large alphabets, the linear scans in interval and find become the bottleneck. A Fenwick tree gives both cumulative frequency and symbol search in O(log n).
• Context models: keep a separate count table per context, such as the previous one or two bytes. Prediction by partial matching tries the longest matching context first and escapes down to shorter ones; context mixing, as in PAQ, blends several models instead.
• Binary adaptive coders: turn every decision into a yes-or-no question with an adaptive probability, updated by a shift after each bit. CABAC in H.264 and HEVC and the range coder in LZMA work this way. Binary coding makes the arithmetic cheap and the models easy to combine.

Termination

The decoder must know where the message ends. The options are an end-of-file symbol, as in the code above, which costs a little probability on every step; a length written before the data; or a framing layer that stores the symbol count. The encoder must also flush enough bits to identify a point inside the final interval; the code emits two after the pending bits. The decoder reads zeros past the end of input, so the encoder's flush must remain valid if followed by zeros, which this flush is. Byte-oriented range coders flush whole bytes instead, and the container must record that those extra bytes belong to the stream.

Huffman, arithmetic and ANS compared

Zstandard is often mistaken for an arithmetic coder; it uses Huffman for literals and a table-based ANS variant called FSE for sequences. Choose arithmetic coding when the model adapts per symbol and compression ratio is worth more than throughput. Transforms such as the Burrows-Wheeler transform can feed any of these coders.

Language models as the model

Since a language model outputs a probability for every possible next token, it can drive an arithmetic coder directly. The 2023 paper Language Modeling Is Compression by Delétang and colleagues showed large models compressing text, and even image and audio data, better than general-purpose compressors, when the model's own size is not counted.

The catch is determinism. The decoder must reproduce the encoder's probabilities bit for bit. GPU inference often differs in the last bits between batch sizes, kernels, drivers or hardware, and a single changed probability makes the rest of the stream decode as garbage. Practical systems quantize each probability distribution to integer frequencies with a floor of 1, run the model with fixed kernels and batch size on both ends, and verify a checksum per block so a mismatch is detected rather than silently decoded.

Failure modes

• Model desynchronization: the encoder updates before coding, or the decoder after, or they round differently. Output is garbage from that point on. Share one model class between both directions.
• Zero frequency: a symbol with frequency 0 cannot be encoded. Start counts at 1 or use an escape symbol.
• Total too large: violating the precision contract makes slices collapse; rescale before the total reaches the limit.
• Overflow: range * cum_freq overflows 32-bit arithmetic; use 64-bit products.
• Bad termination: too few flush bits decode correctly only when trailing bytes happen to help. Test with the input truncated exactly at the end of the stream.
• Untrusted input: a decoder fed corrupted data can loop forever without an end-of-file symbol. Cap the output length.

What to do next

1. Run the encoder and decoder above on your own data with a round-trip test, including empty and single-symbol inputs.
2. Replace the linear scans with a Fenwick tree and measure throughput on a 256-symbol alphabet.
3. Add an order-1 context model, one table per previous byte, and compare output sizes.
4. Convert to a binary adaptive coder in the LZMA style and compare speed.
5. Compare against Huffman on skewed data, and read about succinct data structures for compressed structures that remain queryable.