Compression by prediction

A language model is a probability for what comes next, and an arithmetic coder turns a probability into bits. The better the prediction, the shorter the file. One example program of the library builds the whole chain and measures it.

0.937
bit per byte on a gigabyte of Wikipedia text
7.9 M
parameters in the network that predicts
107
context models that correct its prediction
1
source file for the compressor and the decompressor

A model that predicts well compresses well

Coding a symbol costs the logarithm of the probability the model gave it: the length of the archive is the cross-entropy of the model on the data. Training a network to predict the next token and compressing a text are therefore the same problem, and the size of the archive becomes an honest measure of what the network has learned.

From the text to the archive: the network, the context models and the coder.

Two programs, from bytes to tokens

Byte by byte, for any file

A small transformer predicts the next byte of any file. One bit says whether it was right, the misses are written in full, and the model can travel inside the archive, which then decompresses on its own.

slm_predictive_compressor_ex.cpp

Token by token, for text

A decoder of eight blocks predicts tokens, context models learn the text as it is coded, and both are compiled into the program with the tokenizer. This is the version measured below.

slm_tok_predictive_compressor_ex.cpp

From token to bits

  1. The network gives a probability to each of the 8,192 tokens of the vocabulary.
  2. The tokens are kept in the order of their bytes: each bit of the next byte splits a contiguous range, and the probability of a bit is computed exactly, with no approximation.
  3. 107 context models keep a history of the bits already coded, from the last byte to matches found far back in the text.
  4. Eight mixers, a final mixer and four adaptive maps combine these predictions, decision by decision.
  5. A binary arithmetic coder writes the result. Meanwhile the output biases of the network move after every token, and the decoder takes the same steps.

The same bits on every machine

A decoder must find every probability the encoder used, to the last bit, or it decodes something else. Floating-point results change with the processor, the library and the order of the sums. The coding path therefore has an arithmetic of its own.

  • Matrix products run on integers and are summed exactly in 32 bits: an integer sum does not depend on its order.
  • Exponentials, logarithms and rotations use the program's own routines, built from the basic IEEE operations.
  • The kernels for AVX-512 VNNI, AVX-VNNI and AVX2 write the same archive as the portable code.
  • Training runs on any hardware, a graphics card included: only the weights cross over.

Measured on a gigabyte of Wikipedia

The program compressed and decompressed enwik9 with the network of the repository and its default options, on one core of an Intel Core Ultra 9 275HX. The decompressed file is identical to the input, byte for byte.

enwik9, the gigabyte of English Wikipedia text of the Large Text Compression Benchmark
Archive117,169,624 bytes
Bits per byte0.937
Decompressor, tokenizer and network included7,063,888 bytes
Time per direction, one coreAbout 25 hours
Compression with the kernels chosen by the processor24 h 48 min instead of 30 h 18 min

The contents shipped with an archive

The tokenizer and the weights, quantized to 6 bits, are compiled into the program as data. The same source builds a decompressor alone, about 320 KB of code beside its data, with one compiler command and no library to install.

Lessons of the example, beyond compression

Bits per byte turn the next-token objective into a quantity anyone can check. And the method applies whenever a trained network must give identical results on two machines: train anywhere, ship the weights as data, and run inference in arithmetic whose every operation is fixed.

Compress your own files

The repository provides a trained network: once built, the program compresses right away.