Room for the step, not the value

The far well in a byte computed the stationary distribution of a two-well birth–death chain in the two eight-bit formats and found that the deepest barrier its far well survives is set by headroom. Starting the recurrence at one, gradual underflow loses the far well at a median of seven octaves of barrier in E4M3 and sixteen in E5M2. Starting it at the largest power of two the format holds — 256 and 32,768 — adds the octaves of that start one for one, to seventeen and thirty. The subnormal band, two or three octaves wide, was worth exactly its width. And at E5M2’s three significant bits the same significand with no limit on its exponent still lost the far well on eight chains of nine, because the precision runs out before the range does.

Starting high spends the headroom once. Its last section proposed spending it repeatedly. “A recurrence that multiplies by an exact power of two whenever the running value falls below a threshold spends it repeatedly and never reaches the band, at the cost of one comparison per step and an exponent counter carried beside the vector. In half precision that is the unbounded route; in a byte it would remove every range failure on this page and leave exactly the precision noise.” The well on the far side of the band had said the same thing earlier and more briefly: an unbounded exponent is “what holding the values near unity by exact power-of-two rescaling delivers.”

The proposal is right about what a counter can deliver and wrong about the threshold that delivers it. The value is the wrong thing to watch.

A significand and an integer #

The chain is the earlier essays’ double well: $\sin^2(\pi s)$ plus a slight tilt, Metropolis rates, a temperature set so that the top of the barrier has probability $2^{-d}$ of the near well’s bottom, and nine chain lengths from 32 to 64 states. The stationary vector comes from detailed balance by forward substitution, $\pi_{i+1} = \pi_i\,p_i/q_i$, each multiplication and division rounded to the format with gradual underflow. The rates are stored in the format, the reference is the same recurrence in double precision on the stored rates, and the two sums that turn the vector into the far well’s share are accumulated in binary32, as eight-bit hardware accumulates. A far well counts as lost when its share is wrong by half.

The counter changes only what is stored. Each state keeps a value $v_i$ in the byte and an integer $E_i$ beside it, and the stationary entry is $v_i \cdot 2^{-E_i}$. A rescale multiplies $v$ by $2^k$ and adds $k$ to the counter. Multiplying a normal number by a power of two is exact as long as the result is normal too — the spacing what a float can hold draws is the same in every octave, scaled — so a rescale itself never rounds anything. What a rescale can do is decide where in the format the next operation happens, and that is the whole of the question.

The comparison is the strictest one available. The unbounded route of the earlier essay is the same significand with no exponent limit at all, and a rescaled run either reproduces it bit for bit, entry by entry, or it does not. Nothing in between counts as success, because anything in between is a run that rounded somewhere the unbounded exponent would not have.

A rule on the value #

The rule the proposal described, with the guard any implementation would add: after each step, if the value has fallen below the smallest normal times $2^m$ — a margin of $m$ octaves above the band — or risen above a ceiling, rescale it to between one and two. The figure at the top of the page uses a margin of six octaves and a ceiling of a quarter of the largest normal, 112 in E4M3.

In half precision it works: all nine chains keep their far well past sixty octaves, where gradual underflow from one lost them at 24 and from the top at 39. In E5M2 its survival depths are the unbounded exponent’s, chain for chain, a median of 34. In E4M3 it is better than both earlier remedies and nowhere near what it was supposed to be. The far well is lost at a median of 45 octaves, as early as 36, and survives sixty on one chain of nine. With no exponent limit, E4M3 keeps it on eight. Only 396 of the 531 runs — nine chain lengths times fifty-nine depths — reproduce the unbounded route.

The dial is where the failure is. At twenty and thirty octaves the two rules make the same run. At forty the floor rule’s values start to climb on the far side of the barrier and the two still agree to the last bit, with the far well wrong by 3.4 per cent — the significand’s own error, which the unbounded route makes too. At fifty and sixty the climb steepens, and the floor rule’s line rises into the dashed line at the top: at sixty octaves four quotients reach 448 and are clipped there, and the far well comes out wrong by 99.8 per cent. The window rule’s line never touches either dashed line, and its far well is wrong by 10.9 per cent, which is exactly the unbounded route’s error on that chain.

The climb, not the dip #

The obvious reading of a rescaled run that fails is that it was rescaled too late, so that some value had already fallen into the band and lost bits before the rule pulled it back up — the loss the numbers below the smallest one describes, a bit of significand for every octave of depth. That reading predicts that raising the floor cures it. It does not.

At a ceiling of a quarter, raising the floor from zero octaves to eight moves E4M3 from none of nine survivors to two. The two lines that matter are the ones at the ceiling. Lower it to a sixty-fourth of the largest normal — seven, in E4M3 — and the floor rule keeps eight chains of nine from a margin of four octaves upward, every one the unbounded exponent keeps — at a margin of four with 27 products in the band across its runs and not one quotient clipped, so a few products in the band cost nothing measurable. Over all 531 runs at a margin of six and a ceiling of a quarter, the floor rule produces 18 products in the subnormal band and 273 clipped quotients, spread over 149 runs. The losses are overflow, not underflow.

The reason is the shape of the chain. On the way down into the barrier every step multiplies the value by $p_i/q_i < 1$, and the deeper the barrier the smaller the factor, but each step is still only a fraction of an octave to a few octaves. On the way up, out of the barrier and into the far well, every factor is the reciprocal of one on the way down, and on a 32-state chain with a sixty-octave barrier the steepest of them is $2^{5.4}$, a factor of forty-two. The floor rule only acts after a step, and it leaves the value wherever that step put it as long as it is under the ceiling. A value of 100 is under 112; one step later it is 4,200, and E4M3, which has no infinity, saturates it to 448 and goes on. Nothing in the run signals that anything happened. The far well is assembled from those clipped values and comes out at a tenth of its size.

The format’s choice matters to how the failure looks. E4M3 as specified — the format eight bits, and a format that breaks the rules is named for — has no infinities and either saturates or returns its single NaN pattern on overflow, depending on the conversion mode. The runs here saturate, which is the quiet failure: a plausible probability that is wrong. Under the NaN convention the same 149 runs would return NaN — a louder failure, and a better one, since a run that announces itself can be repeated with a different rule. E5M2 has infinities and its floor-rule runs overflow 125 times without moving a single survival depth, because the values that overflow there belong to depths the precision has already lost.

One more line on that figure needs a warning rather than a reading. At a margin of four and a ceiling of a quarter, E5M2 keeps three far wells, two more than the unbounded exponent does. That is not a better computation. Those runs are not the unbounded runs, and a different sequence of roundings happened to land inside the tolerance where the reference’s did not. A survival count can be passed by luck; the bit-for-bit comparison cannot, and it is why the floor rule’s 396 of 531 is the number to believe.

A window read off the rates #

What a rescale has to guarantee is not that the value is a comfortable size. It is that the next step’s two operations happen inside the normal range. The step forms $p_i v_i$ and then divides by $q_i$, so the value before the step must be large enough that the product is not subnormal and small enough that the quotient does not pass the top:

$$\frac{\text{smallest normal}}{\min_i p_i} \;\le\; v \;\le\; \frac{\text{largest normal}\cdot \min_i q_i}{2\,\max_i p_i}.$$

Both ends are read off the chain’s own stored rates before the recurrence starts, and the factor of two keeps the quotient an octave clear of the top. The window rule rescales $v$ to the window’s geometric middle whenever it leaves the window, and otherwise does nothing.

On every format, on every one of the 531 runs, the window rule reproduces the unbounded exponent bit for bit. No product falls into the band and no quotient reaches the top. So does a third rule that aims every step — rescaling before each step so that $p_i v_i$ lies between one and two — which is exact for a simpler reason: the product then sits at one and the quotient at most a few octaves away, whatever the window would have been. The figure at the top of the page shows the window rule’s row equal to the unbounded route’s survival on every format, which it must be, since it is the same computation.

How narrow the window gets #

The window’s width is the format’s normal range less the octaves the chain’s rates span. In E4M3 the normal range is 14.8 octaves, from $2^{-6}$ to 448.

At a barrier of ten octaves every chain length leaves about eleven octaves of room — far more than any rule needs. The room falls as the barrier deepens, because a deeper barrier on the same number of states needs steeper steps, and it falls fastest on the shortest chain. At sixty octaves and 32 states the window runs from 2 to 5.25, an octave and two fifths wide. The value has to sit in that window before every step, and a step can move it five octaves; so the window rule rescales on most steps of the steep part of that chain, 28 times in 31 steps.

The trend is close to a straight line, and the 32-state line falls by about a fifth of an octave of room for every octave of barrier. It would meet zero near 67 octaves. A chain that steep has no window at all in E4M3: no single position of the value lets both operations of every step stay normal, and the window rule’s guarantee lapses. The aiming rule’s does not, because it chooses a position for each step separately; it needs only that each rate and each rate’s reciprocal is representable. That is the clean statement of what the counter costs at the limit: one rescale per step, and nothing less will do.

In E5M2 and half precision the window is wide everywhere. Their normal ranges are about thirty octaves, and on the steepest chain measured E5M2’s window is sixteen octaves, from $2^{-7}$ to 672. Neither format is ever close to closing it on these chains, and both make three to four rescales per run.

What the counter costs #

A rescale is an integer addition to the counter and an exponent adjustment to the value, which on hardware that exposes the exponent field is not even a multiplication. The comparison that decides whether to rescale is the cost paid every step. Over all 531 E4M3 runs the window rule rescales 11.8 times a run on average, the floor rule 21.3 and the aiming rule 34.5. At shallow barriers the window rule hardly acts — once at ten octaves on the 48-state chain — because the value never leaves a window eleven octaves wide; at sixty octaves it rescales 31 times in 47 steps, about as often as the floor rule, because the window has narrowed to a couple of octaves.

The floor rule is not cheaper for being simpler. It pays for more rescales than the window rule on average and is exact on three runs in four. The aiming rule pays for the most and is exact always. The window rule is the cheapest exact rule of the three, and its only extra cost over the floor rule is two divisions before the recurrence starts.

What E4M3’s limit was made of #

The earlier essay could not separate E4M3’s limit into range and precision, because its control — the unbounded exponent — was only a simulation. With a counter that reproduces the control bit for bit, the separation is a property of an implementable computation.

For E4M3 it comes out stark. The far well is lost at seven octaves from one and seventeen from the top of the range; with the counter it survives sixty octaves on eight chains of nine, and the one exception, a 52-state chain, fails at 38 octaves through its own significand. Its four bits cost the far well a typical eight per cent — the 3.4 and 10.9 per cent on the chain the dial shows are that error — but rarely more than a third. Essentially all of E4M3’s limit on this computation was range, and the range is removable.

For E5M2 the counter changes nothing that a high start had not already nearly done. Starting at the top it lost the far well at a median of thirty; with the counter, at 34, between 21 and 45, on eight chains of nine. The extra four octaves are the high start’s limit replaced by the significand’s, and the significand’s limit is a soft one. The precision noise the earlier essay measured is untouched, because a counter moves values around the format and three bits are three bits wherever the value sits.

That figure is the earlier essay’s, unchanged, and it now means something it did not. Then it was the error of a simulated format with an infinite exponent. Now it is the error of an eight-bit recurrence with an integer beside each value — so it is the honest statement of what each format can do for this computation. Half precision is accurate to a few units of its roundoff at every depth, which is the sense in which the exact answer to a nearby problem is all a stable method owes. E4M3 is accurate to about one significant figure. E5M2 is accurate to no significant figure reliably, at any depth, by any treatment of the exponent.

Why the proposal went wrong #

The proposal reasoned about the value, because in a half-precision run the value is the only thing near the edge of the range. Half precision has sixteen octaves above one and fourteen below, and a step of five octaves is a small fraction of either. A threshold placed anywhere sensible keeps both operations of the next step inside, which is why the floor rule is exact on every half-precision chain that does not saturate and still survives on all nine. The single-precision reasoning that puts a guard “near the bottom” and another “near the top” works because the margins are generous compared with any one step.

E4M3 has fewer than nine octaves above one. A ceiling of a quarter of its largest normal leaves two octaves of room, and a five-octave step does not fit in two. The proposal’s own phrase — “never reaches the band” — names the right risk for the descent and the wrong one for the ascent. In a byte the distance a single step travels is a significant fraction of the whole format, and a rule that does not know the step size cannot know whether the value has room.

The general form is short. A rescale has to leave room for the operation, and the operation’s reach is set by the operands it will meet. For a recurrence whose multipliers are known in advance — as the rates of a chain are — the room can be computed once and the rescaling rule can be exact. For one whose multipliers are not known in advance, the only exact rule is the per-step one, and that costs a comparison and a rescale at every step. A norm that overflows before it is a norm is the same lesson in a different operation: squaring doubles an exponent, so the safe range for a sum of squares is half the format’s, and the scaled norm works by keeping room for the square rather than for the value. The units that overflow before the answer does found the same thing one level up, in a change of variable whose intermediate needed more range than its result.

What 531 runs do not show #

One potential shape and one tilt, nine lengths, fifty-nine depths. A potential with a sharper barrier puts its steep steps closer together and would narrow the window faster than these lines; a gentler one would leave more room. The rates are stored once and every run shares them, so the window is computed from exactly the numbers the recurrence uses — a recurrence whose coefficients are computed as it goes would need the window bounded from what is known about them in advance, or would need aiming. The formats are simulated by rounding each operation’s exact result, which is how they are specified; a device that rounds a product in two stages could differ by a bit on the steps nearest the edges, which is exactly where the floor rule spends its time and where the window rule does not. The counter is an integer and is never at risk here; a chain long enough to overflow it would need $2^{31}$ octaves of barrier.

Still open: one exponent for a block, a window that closes, and a cheap certificate #

One exponent shared by a block. A counter per entry costs an integer per value, which is four times the storage of the value itself in a byte. The block formats in one exponent for thirty-two numbers share one exponent across a block instead, and found that a block tolerates about three octaves of spread inside it before an outlier costs its neighbours — exactly two to the significand’s width, as a bit buys an octave measured. Along this chain a block of consecutive states spans the steps between them, so a block of $b$ states on the steep part of a 32-state chain spans up to about $5b$ octaves. The prediction with a sign is that a shared exponent with the window rule applied to the block’s largest entry keeps the far well wherever the per-entry counter does for blocks of two states, and loses it at a barrier depth that falls in proportion to $b$ for longer blocks — so that the shared-exponent formats are a poor fit for exactly the vectors a counter rescues.

A window that closes. The 32-state line meets zero near 67 octaves. Beyond it the window rule has no position to rescale to and the aiming rule still does. The prediction is that the window rule’s runs stop reproducing the unbounded exponent at the depth where the computed width first goes negative, to within one octave, and that the aiming rule’s do not — a chain built past sixty octaves is the test.

A certificate in a byte. The earlier essay’s third question stands with its premise now stronger. A componentwise backward error computed for an E4M3 run with a counter is a statement about a computation whose only error is its four bits. Whether that number can tell a far well wrong by eight per cent from one wrong by a third — the only distinction E4M3 offers on this chain — decides whether a byte’s stationary vector can be shipped with any statement of its accuracy at all.