How Taco works: a language model, a range coder, and no floats

Taco is a lossless compressor. A language model guesses what comes next in a file, and a range coder stores only what the model did not guess. A file Taco compresses on my Mac comes back, bit for bit, on a Linux PC with an NVIDIA GPU. That last part is the hard part, and it is why GPT-2 runs inside Taco on integer arithmetic only.

This is a walk through the whole thing, the way a course would teach it: information theory, coding, floating point, the maths of a neural network, and then how every step of that maths becomes integer arithmetic. The figures compute live in your browser; the integer ones use exact integer arithmetic with the same rules as Taco's code. Facts and measurements come from the Taco repository: its design plan, decision records, research notes and primer.

Part 1. Information: why a likely token costs few bits

A bit is one halving

One yes-or-no question halves the possibilities. Two questions leave a quarter, eight questions pick one of 256. To single out something of probability $p$, you need about

questions. A fair coin, $p = \tfrac12$: 1 bit. A face of a die, $p = \tfrac16$: 2.58 bits. One byte of 256: 8 bits. And in the other direction: if something is very likely, it takes almost no questions to confirm it. Each halving of the probability adds exactly one bit.

Entropy: the floor no code can beat

If symbols come from a distribution $p$, the average cost of coding them is at least the entropy, the expected number of bits:

A fair coin has $H = 1$ bit. A coin that lands heads 90% of the time has $H = 0.469$ bits: 1,000 of its tosses fit in about 469 bits.

A language model is a probability machine

GPT-2 reads the tokens so far and gives a probability for each of its 50,257 tokens. Here it is on a real sentence, with the same GPT-2 weights Taco uses:

The second "bit" in "bit for bit" is the idea in one token: GPT-2 gives it 93%, so it costs 0.10 bits. "compressed" right after "A file" surprised it: 18 bits. The whole 59-byte sentence needs about 100 bits, about 12.6 bytes.

Part 2. Coding: turning probabilities into bytes

Arithmetic coding by hand

Start with $[0, 1)$. For each symbol, split the current interval in proportion to the probabilities and keep the slice of the symbol that came. The width left is the product of the probabilities, so the bits needed are

exactly the sum of the symbol costs from Part 1. Here is BAC with $P(A) = 0.5$, $P(B) = 0.3$, $P(C) = 0.2$, first with fractions, then with integers:

With a model, the table changes every step

A language model gives a new table for every token, built from the tokens before it. The decoder has already decoded those tokens, so it can run the same model and build the same table. Here is the real GPT-2 table zooming into the sentence from Part 1:

Every token keeps a frequency of at least 1

The coder needs whole-number frequencies. Taco turns the model's weights $w_i$ (Part 5 shows where they come from) into a table with total $T = 2^{32}$:

and gives the remainder to the token with the largest weight. A frequency of 0 would make a token impossible to code; with a minimum of 1, any byte string can be compressed and no token costs more than about 32 bits. This mattered: GPT-2 gives some tab characters less than $2^{-32}$, and one tab cost 119 bits in the float model.

The decoder needs the exact same table

The decoder never sees the symbols, only the number. It decides each symbol by which slice the number falls in, so its slices must be the encoder's slices exactly. One unit off and it can pick a wrong symbol, feed it to the model, and get every later table wrong:

With $T = 2^{32}$, one unit is $2.3 \times 10^{-10}$ of probability. The decoder needs the same integers, not similar numbers. That is the requirement the rest of this post is about.

Part 3. Floating point: why two machines disagree

What a float actually is

IEEE 754 float32 packs a number into 32 bits: 1 sign bit $s$, 8 exponent bits $E$ and 23 fraction bits $f$. For normal numbers:

Multiply out the fraction and this is an integer times a power of two:

So a float32 is never "about 0.1". It is an exact binary fraction. Typing 0.1 stores the nearest one, $13{,}421{,}773 \times 2^{-27} = 0.100000001490116119384765625$. Flip the bits and see:

Keep this in mind for Part 6: because every float32 is exactly $m \times 2^e$, arithmetic on floats can be done exactly with integers. That observation is how Taco makes its model conversion exact.

Order matters

Each addition rounds, so two orders of the same additions are two different chains of roundings. These are exact float32 computations:

A neural network sums millions of products per token. The order depends on the CPU's vector width, the BLAS library (Apple Accelerate, OpenBLAS, cuBLAS), the thread count, the batch size, the compiler, and on a GPU, on which thread finishes first. Here is one long sum in three orders:

What it did to a float compressor

Taco measured it. The float GPT-2 computed the same four windows of text on the Mac (ARM, Accelerate) and on the Linux box (x86, OpenBLAS). The largest logit difference was 0.034 and the largest probability difference 0.00006; the compressed sizes matched to within a byte. And 0 of 4 windows decoded across the machines, in either direction. The tables differed at all 4,096 steps, from the very first token. Changing only the BLAS thread count on the Linux box broke every window too.

Floats are deterministic for one exact setup and different between setups. A float language-model compressor can pass every test on one machine and fail on the first file opened on another. Only a cross-machine decode shows it.

Part 4. The maths of a neural network

A layer: y = σ(Wx + b)

In course notation, a layer with input vector $x \in \mathbb{R}^n$ computes

where $W$ is an $m \times n$ weight matrix (one row per neuron), $b$ a bias vector, and $\sigma$ a non-linear activation function applied to each element. Each output is one dot product. Without $\sigma$, a stack of layers would collapse into one matrix; the non-linearity is what lets the network bend.

GPT-2 uses GELU as its activation: $\mathrm{GELU}(z) = z\,\Phi(z)$, where $\Phi$ is the standard normal distribution function, computed in GPT-2 with the approximation

It is close to 0 for negative inputs, close to $z$ for large positive ones, and smooth in between: $\mathrm{GELU}(-1) = -0.159$, $\mathrm{GELU}(1) = 0.841$.

Softmax: scores to probabilities

The last layer gives one score per token, a logit $\ell_i$. Softmax makes them positive and summing to 1:

The second form gives the same values, keeps every exponent at zero or below, and is what later lets an integer network use a table for $e^x$.

Attention: a weighted average of other tokens

For each token, three matrices make a query $q$, a key $k$ and a value $v$. A token scores every earlier token by $q \cdot k$, softmaxes the scores into weights, and outputs the weighted sum of their values:

Part 5. From a float network to an integer network

The idea: an integer and a scale

Store a real number $v$ as an integer $q$ and an agreed scale $s$, so that $v \approx s \cdot q$. Money does this: $3.25 is 325 cents, with scale $1/100$. The weights of each row get their own scale: the row's largest weight becomes $\pm127$, and every weight becomes $q = \operatorname{round}(w / s_w)$, an 8-bit integer.

Now the key algebra. If $w_i \approx s_w q_{w,i}$ and $x_i \approx s_x q_{x,i}$, then

The scales come out of the sum. The whole dot product is integer multiply-adds into an accumulator, and the accumulator means $s_w s_x$ times its value. The bias is stored in the same units, $q_b = \operatorname{round}(b / (s_w s_x))$, so it is just added to the accumulator.

To hand the result to the next layer, which expects its own scale $s_y$, multiply by the ratio $M = s_w s_x / s_y$. $M$ is a real number, so HardShell writes it as an integer $m$ over a power of two, $M \approx m / 2^s$, and computes

an integer multiply, an add and an arithmetic shift. The $+2^{s-1}$ makes it round half up.

Follow one network through, both ways

Here is a whole small network computed both ways: the float network, and the integer network built with exactly these rules. Click a neuron to see every number it computes: the integer weights and inputs, the accumulator, the bias, the rescale with its $m$ and $s$, the GELU table, and at the end the logits, the exp table and the frequencies the coder would get.

Things to notice. The integer accumulator is an exact integer, so it is the same on every machine. Its meaning, accumulator × scales, lands within a fraction of a percent of the float neuron. The GELU output is a table entry, not a computation. And the final probabilities agree closely, but the integer ones come out as exact frequencies out of 65,536, ready for the coder.

pub const fn rescale(x: i64, m: i32, s: u8) -> i128 {
    // INVARIANT: |x| <= 2^63 and |m| <= 2^31,
    // so |x * m| <= 2^94 and no step overflows i128.
    let product = (x as i128) * (m as i128);
    shift_round(product, s, RESCALE_MAX_SHIFT)
}

Here is the dot product and rescale on their own, with a shift you can change: a small $s$ gives a coarse $m$, a large $s$ a fine one.

LayerNorm in integers

LayerNorm needs a mean, a variance, a square root and a division. HardShell does each with integers. For a row $x$ of $n$ integers from the residual stream:

$\text{inv}$ is $1/\sigma$ as a fixed-point number: $2^K / (\sigma \cdot 2^J) = 2^{K-J}/\sigma$, so it carries $K - J$ fractional bits. The $2^{2J}$ inside the square root keeps $J$ extra bits for small variances.

Activation functions become tables

GELU has no integer formula, and it does not need one. Its input is an integer with a fixed range, so there are only so many possible inputs, and HardShell simply stores the output for every one of them. The table is computed once, before publication, and shipped in the model file. HardShell's GELU input is an i16: 65,536 entries per layer, with a measured maximum error of 0.502 of the output's last bit. The tiny network above uses the same kind of table.

Softmax and the exponential, as tables

After subtracting the maximum, every exponent in softmax is zero or negative, and with scores in whole steps of $2^{-8}$ there are only so many gaps below the top. So $e^x$ is a table too:

A gap of more than 8,191 steps takes the last entry. Each entry is below $2^{31}$ and a row has at most $2^{31}$ scores, so the sum stays below $2^{62}$.

The output logits use a second, wider table, $\operatorname{round}(2^{40} e^{-i/256})$ in 64-bit integers, to turn each of the 50,257 logits into a weight; the weights become frequencies with the rule from Part 2. With every entry at most $2^{40}$ and fewer than $2^{20}$ tokens, the weight sum stays below $2^{60}$.

The whole integer GPT-2

Put together, one step of HardShell is this chain, with no floating-point operation anywhere in it:

Part 6. How the idea came about

Testing the idea before building it

Language-model compressors already existed, and they shared one limit: they decode only on the same hardware and software that encoded. A published test of one decoded 0 files when the encoder was an M2 Pro and the decoder an M4 Max. Before writing any of Taco, I tested the idea with a small, pure-Python integer context model, no neural network:

The last row is the worrying one: a change of a billionth breaks a quarter of the decodes, sometimes thousands of bytes in. A short test can miss it.

Integers only

That decided the rule (ADR 0002): no floating-point arithmetic anywhere between the model file and the frequency table. The cost is a little precision and integer versions of LayerNorm, GELU and softmax. The benefit is that integer addition and multiplication give one result in any order, so every machine computes the same table. GPT-2 small was the model: open weights, a byte-level tokenizer that can encode any byte string, and only operations that published integer-only methods (I-BERT) already cover. The float GPT-2 measurement in Part 3 came next and confirmed it: 0 of 4 windows across the machines.

The last float: the converter

With HardShell running on integers, one float step was left: the converter that turns GPT-2's published float weights into the integer model file. The decoder never runs it, but if it could give different results on different machines, two people could build two different "GPT-2" models and fail to read each other's files. A weight whose scaled value is $89.5$ minus a hair on one machine and plus a hair on another rounds to 89 on one and 90 on the other.

The way out was in Part 3: a float32 is not an approximation of anything. Its bits say exactly $m \times 2^e$. So the converter does not compute with floats at all. It reads each weight's bits as the integer $m$ and the exponent $e$, computes $127 \cdot w / \max$ as an exact fraction of integers, and rounds once, half to even:

What it gets, and what it costs

All measured.

On alice29.txt Taco gives 2.05 bits per byte, against 2.55 for xz. On 16 server logs, a profile that mixes GPT-2 with a match model is 10.8% smaller than xz. And the point of it all: 12 of 12 test files decode across the Mac and the Linux box with byte-identical .taco files either way; native Windows matches; the CPU, CUDA and wgpu backends give the same bytes.

It is slow: about 85 to 129 KB/s to compress English on an RTX 3060, 26 to 31 KB/s to decompress, 0.3 to 2 KB/s on the CPU alone, where zstd does hundreds of MB/s. And it is not the best language-model compressor: Fabrice Bellard's ts_zip, with a larger model, makes alice29.txt 44% smaller. What Taco adds is the combination: an integer specification of GPT-2 anyone can read, a conversion anyone can repeat, several implementations, and tests that show they agree to the bit. It is an alpha. Keep a second copy of anything you fold with it.