Fix the Tree, Free the Schedule

A spec language for arithmetic, where rounding is explicit and the hardware cannot reorder a sum

To write down what a kernel computes, bit for bit, you need surprisingly little: exact numbers, one operator that loses information, and a way to say in which order things are added. The interesting part is what the language refuses to say.

Exact until you say round

Every finite floating-point number is a fraction with a power-of-two denominator: an integer times 2 to some power. Numbers of this kind are closed under addition, subtraction and multiplication, so a computer can add and multiply them exactly, using big integers, without ever approximating. The fp32 value nearest to 0.1 is not 0.1; it is exactly 0.100000001490116119384765625. The imprecision is not in the number. It is in the step that chose this number to stand for 0.1.

So the language separates the two. Its core arithmetic is exact, and a float appears only through one operator, round[format, mode, policy]. The format says which grid to snap to, the mode says which neighbor to pick, and the policy covers what happens to zero signs, NaNs and tiny results. Every bit a kernel loses, it loses at a round.

There are no defaults. A round without a mode does not type-check. This is the most important rule in the language, because the default is exactly what differs between chips: the H100’s tensor core rounds toward zero and the Trainium 2 matrix unit rounds to nearest even, and both vendors call it fp32 accumulation.

Formats, in turn, are not keywords. A format is a small record: exponent bits, fraction bits, and a few flags. This paid off quickly. Probing showed that Trainium’s matrix unit adds in a format no manual names, with fp32’s precision but a wider exponent, so huge terms cancel instead of overflowing. In the language that discovery is one new row in a table, not a new construct.

One more primitive is needed for tensor cores, which do not round each add. They line up a group of terms against the largest one and cut every term to a fixed window of bits below it. A small product next to a large one loses bits it would have kept on its own. Rounding cannot describe that, so the core gets a trunc alongside round. The next chapter shows why that one primitive matters so much.

The order is part of the answer

Add three fp32 numbers, 10⁸, 1 and −10⁸. Left to right gives 0, because 10⁸ + 1 rounds back to 10⁸. Add the outer two first and you get 1. Every addition was correctly rounded, and the answers still differ. Floating-point addition is not associative, so “the sum of these numbers” is not a specification once the additions round.

A GPU kernel summing a row of 4,096 values picks one order out of an astronomical number. Usually that order is written down nowhere. It falls out of how many threads there are, how the loop is strided, and how the warp shuffles combine lanes.

The language makes the order a value. A reduction names its tree, built from a handful of combinators: a sequential fold, adjacent pairs level by level, a butterfly across a warp, contiguous blocks combined by another tree. They nest. Probing found that Trainium’s matrix unit adds in four blocks of 32, sequentially within each block, and combines the four block sums pairwise. In the language that sentence is blocked(32, seq, pairwise). The vocabulary for specifying hardware and for reporting it turns out to be the same.

The bug everyone has filed

Anyone who has served an LLM has seen some version of this report: the same prompt gives different logits depending on what else is in the batch. Nothing random is going on. The matrix library looked at the batch size and the number of SMs, decided to split the sum a different number of ways, and so added in a different tree. Or a reduction used floating-point atomics, and the order in which thread blocks finished decided the order of the adds.

Both failures have the same shape. A quantity that should only affect speed reached the reduction tree and changed the value.

The language fixes this with a typing rule rather than a ban. Every expression belongs to one of two stages. The shape stage holds everything known before any tensor value is read: shapes, constants, loop bounds, and the trees. The data stage holds everything that depends on values. Trees must be shape-stage. And the launch configuration, the grid, the SM count, the warp width, is not in the language at all. A spec cannot name the SM count, the way a pure function cannot read the clock.

Batch invariance then falls out as a typing property. Row 3’s output cannot depend on whether row 7 exists, because nothing in row 3’s expression mentions row 7 or the batch size. Banning atomics would not have been enough: a split-K heuristic has no atomics and still changes the answer when the batch changes. The requirement is that the tree be a function of shapes only, and staging states it once. In the terms of an earlier post, this is binding time applied to arithmetic: the order of a sum binds when the shapes are known, not when the kernel launches.

Data may still make choices. A softmax takes a running maximum. But data chooses which value, through a select with a declared total order that covers ±0 and NaN, never which tree.

What the language gives up

Put together, these rules split a kernel into two parts. The algorithm is fixed to the bit: the trees, the rounding points, the constants. The schedule is free: tiling, threads, memory placement, pipelining. A compiler may do anything it likes to the second part and nothing to the first.

That has a cost: a different reduction tree is a different program. The freedom every numerical library takes for granted, to reassociate a sum when it is faster, is gone. There is exactly one exception, a sum of terms that are all exact, where every order gives the same bits. The last chapter of this series turns that exception into the foundation of cross-chip replay.

Fix the tree, free the schedule. The first half is the expensive one, and the language pays it on purpose. Without it, the spec could not say what the hardware computes, only what it computes on a good day.