[HN Gopher] Herbie: Automatically improve imprecise floating poi...
___________________________________________________________________
Herbie: Automatically improve imprecise floating point formulas
Author : summarity
Score : 189 points
Date : 2026-03-31 10:53 UTC (4 days ago)
(HTM) web link (herbie.uwplse.org)
(TXT) w3m dump (herbie.uwplse.org)
| fluorinerocket wrote:
| How useful is this when you are using numbers in a reasonable
| range, like 10^-12 to 10^12? Generally I try to scale my numbers
| to be in this range, whether by picking the right units or
| scaling constraints and objectives when doing nonlinear
| programming/ optimization.
|
| Like looking at this example,
|
| https://herbie.uwplse.org/demo/b070b371a661191752fe37ce0321c...
|
| It is claimed that for the function f(x) =sqrt(x+1) -1
|
| Accuracy is increased by from 8.5% accuracy to 98% for
| alternative 5 Which has f(x) = 0.5x
|
| Ok so x=99, the right answer is sqrt(100) -1 = 9
|
| But 0.5 * 99 = 49.5 which doesn't seem too accurate to me.
| hmpc wrote:
| Check the specification at the top. The range for x is [-1, 1].
| For the range you provided the accuracy of the 0.5x alternative
| is reported as only 33%:
| https://herbie.uwplse.org/demo/570b973df0f1f4a78fe791858038a...
| fluorinerocket wrote:
| You're right I misread the graph. That said though I have
| played around with Herbie before, trying it out on a few of
| the more gnarly expressions I had in my code (analytical
| partial derivatives if equations of motion if launch vehicle
| in rotating spherical frame) and didn't see much appreciable
| improvement over the expected range of values, but then again
| I didn't check every single one.
|
| What would be cool is if you could some how have this kind of
| analysis done automatically for your whole program where it
| finds the needle in the haystack expression that can be
| improved, assuming you gave expected ranges for your
| variables
| pavpanchekha wrote:
| Author here. I've got a few papers about this problem
| (including one in submission), but it is very very hard to
| do, especially with acceptable overhead. The state of the
| art is maybe 100x overhead.
| yossi_peti wrote:
| The precondition on the link you shared has -1 <= x && x <= 1,
| so 99 is way outside of that range. But even so, testing for
| x=1, which is supposed to be inside that range, 0.5 doesn't
| seem tolerably close to 0.4142.
| LiamPowell wrote:
| I have a suspicion that the accuracy number is the mean of
| accuracies over all valid floats in the range (or something
| approximating that), which is going to be weighted towards
| zero where the accuracy is higher, and perhaps where sqrt
| near 1 has some artefacts.
| pavpanchekha wrote:
| It is, there's a page in the documentation about how errors
| are defined. Let me also add: Herbie generally gives the
| most accurate option it found first, and then the other
| stuff might be useful for speed (0.5x is way faster than
| two square roots and a divide!) but it's not as accurate
| Rexxar wrote:
| The input should be the range and the distribution of
| probability on this range. Intuitively we have a tendency
| to assume an uniform probability for range [-1, 1] which is
| not the case if we check every doubles.
| fluorinerocket wrote:
| You're right but still, big error. I get its averaging over
| the range, and the floats are not uniformly distributed.
|
| Maybe the thing to optimize the expression for is the
| minimize the maximum error, and not the average error. I
| think that's what I would care about
| bee_rider wrote:
| I wonder, is there a way to only request reformulations that
| don't involve branches? The tool already seems quite nice, but
| that might be a good feature.
|
| Also, I'm not sure I understand the speedup. Is it latency or
| throughput?
| pavpanchekha wrote:
| Author here. The speed up is modeled throughput, though the
| model is relatively naive. It's possible to disable branches by
| turning off the regimes flag, see
| https://herbie.uwplse.org/doc/1.0/options.html
| bee_rider wrote:
| Nice!
|
| What's uwplse mean? I mixed up the letters and misread it as
| ulp-wise which works for the project, haha.
| pavpanchekha wrote:
| University of Washington Programming Languages and Software
| Engineering (research group).
|
| I'm not at UW any more, I'm now at Utah, but some of the
| Herbie team is at UW and they provide the infrastructure
| reikonomusha wrote:
| This is an awesome piece of software, one of my favorite little
| pieces of magic. Finding more precise or more stable floating
| point formulas is often arduous and requires a lot of familiarity
| with the behavior of floats. This finds good formulas completely
| automatically. Super useful for numerical computation.
| yread wrote:
| Really cool, numerical stability can be tricky as errors can
| accumulate with each operation and suddenly 53 bits of precision
| is not enough.
|
| Also nice to see an article thats not about AI or politics
| notpushkin wrote:
| Some trivial cases produce... interesting results.
|
| For x in [-1.79e308, 1.79e308]:
|
| Initial Program: 100.0% accurate, 1.0x speedup
| def code(x): return math.sqrt((x + 1.0))
|
| Alternative 1: 67.5% accurate, 5.6x speedup def
| code(x): return 1.0
| lifthrasiir wrote:
| That _does_ make sense, because a half of all available fp
| numbers are less than 1 in their magnitude. In particular there
| should be a plenty of numbers x such that |x| << 1 so x + 1 ~=
| 1; in fact, the proportion should be just shy of 50%.
| cocoto wrote:
| But I guess using the density distribution of floating points
| is rarely useful in a problem. Your actual distribution will
| almost surely be way different. Imo, the tool presented here
| should provide a way to manually provide a custom density
| function (with some common presets like uniform and normal
| distributions).
| pavpanchekha wrote:
| Author here! Yes, the float distribution isn't what you
| want in practice, but distribution selector isn't really
| the right thing either, because a low probability bad
| result can still be pretty bad! Hence the range selector;
| the float distribution is good at picking extreme values
| that trigger FP error.
|
| We usually recommend looking for 90%+ accuracy or carefully
| examining the accuracy plot
| andrepd wrote:
| That is indeed one of the problems with IEEE floats. There
| are only 10^80 atoms in the universe, and a Planck length is
| 1^-60th of the radius of the universe. But 64-bit floats have
| an _absurd_ range of over 10^+-300! Worse than that, notice
| that there are as many bit patterns in the never-used range
| between 10^300 and 10^301 as there are in the super-important
| range between 1 and 10! Super wasteful. Not to mention the
| quadrillions of values reserved to represent "NaN"...
|
| This is one of the problems that alternative formats such as
| the Posit aim to solve. It's quite interesting: I've got an
| implementation in rust here if you want to play with it
| https://github.com/andrepd/posit-rust
| AlotOfReading wrote:
| Note that the logarithmic distribution of float density is
| also key to certain kinds of efficient hardware float
| implementations, because it means you can use the fixed
| mantissa bits alone as table indices. Unums have proven
| difficult to build efficient HW implementations for.
|
| IEEE floats have a few warts like any other 1980s standard,
| but they're a fantastic design.
| andrepd wrote:
| > Unums have proven difficult to build efficient HW
| implementations for
|
| Valid point, but not quite true anymore. It comes down
| basically to the latency of count_leading_ones/zeros for
| decoding the regime, on which everything else depends.
| But work has been done in the past ~2ish years and we can
| have posit units with lower latency than FP units of the
| same width! https://arxiv.org/abs/2603.01615
|
| > IEEE floats have a few warts like any other 1980s
| standard, but they're a fantastic design.
|
| Hmm I don't know if I would call it a fantastic design x)
| The "standard" is less a standard than a rough
| formalisation of _a specific FPU design_ from back in the
| 1980s, and that design was in turn not really the product
| of a forward thinking visionary but something to fit the
| technical and business constraints of that specific piece
| of hardware.
|
| It has more than a few warts and we can probably do much
| better nowadays. That's not really a diss on IEEE floats
| or their designers, it's just a matter of fact (which
| honestly applies to very many things which are 40 years
| old, let alone those designed under the constraints of
| IEEE754).
| AlotOfReading wrote:
| I'm sure you're much more knowledgeable about this than I
| am, but that's kind of my point. A month old preprint is
| the first thing to compare to implementations of a mildly
| evolved, warty old standard from 40 years ago. I consider
| that fantastic.
|
| Thanks for the paper though. Looking forward to reading
| it more closely when I have time.
| FabHK wrote:
| Not really. 1+x/2, however, would be a good approximation to
| sqrt(1+x) for small (in absolute value) x.
| irchans wrote:
| How about:
|
| (* Mathematica Notation, Assume x>0 _) If[ x < 10^(-10), 1+
| x/2, (_ order x^2 error _) If[ x > 10^10, Sqrt[x], (_ order
| 1/Sqrt[x] error _) (_ else _) Sqrt[x +1] ] ] (_ I guess the
| If statements take too much time. *)
| urschrei wrote:
| I resurrected the Rust Herbie lint (now using dylint) a while
| ago: https://github.com/urschrei/herbie-lint
| andrepd wrote:
| I don't quite understand how they define "accuracy".
| perching_aix wrote:
| Could you substantiate that a bit more? I don't see what'd be
| hard to understand about it at a skim.
| andrepd wrote:
| Is it an arithmetic average of relative error over the given
| range? Because if yes then it can be misleading, and
| potentially a bad meshes to rank alternatives (though the
| HTML report includes a graph over the input range, which is
| quite nice, so I'm talking only about the accuracy number).
|
| In the limit, an alternative with 10x better accuracy when
| x>10^150 and 10x worse in 1<x<10^150 would rank higher :) but
| more generally, not all inputs are equally important.
|
| Furthermore, floats have underflow to 0 and overflow to
| infinity, which screw all this up because it can lead to
| _infinite_ relative error.
|
| Because of this you have some of the funny cases reported
| elsewhere in this thread :p
|
| I'm not sure what would be a better approach though. Weigh
| the scores with a normal distribution around 0? Around 1?
| Exponents around 0?
| pavpanchekha wrote:
| Documented here but yes it's an average, of something
| similar to but not exactly the same as relative error:
| https://herbie.uwplse.org/doc/latest/error.html
|
| It's true that averages can be misleading but we encourage
| users to think about it instead as a percentage of inputs.
| In practice the error distribution is very bimodal, the two
| modes being "basically fine" (a few ulps of error) and
| "garbage" (usually 0 instead of some actual value)
| summarity wrote:
| I posted this and it picked up steam over night, so I thought I'd
| add how I'm using it:
|
| I work on 3D/4D math in F#. As part of the testing strategy for
| algorithms, I've set up a custom agent with an F# script that
| instruments Roslyn to find FP and FP-in-loop hotspots across the
| codebase.
|
| The agent then reasons through the implementation and writes core
| expressions into an FPCore file next to the existing tests,
| running several passes, refining the pres based on realistic
| caller input. This logs Herbie's proposed improvements as output
| FPCore transformations. The agent then reasons through solutions
| (which is required, Herbie doesn't know algorithm design intent,
| see e.g. this for a good case study:
| https://pavpanchekha.com/blog/herbie-rust.html), and once
| convinced of a gap, creates additional unit tests and property
| tests (FsCheck/QuickCheck) to prove impact. Then every once in a
| while I review a batch to see what's next.
|
| Generally there are multiple types of issues that can be flagged:
|
| a) Expression-level imprecision over realistic input ranges: this
| is Herbie's core strength. Usually this catches "just copied the
| textbook formula" instance of naive math. Cancellation, Inf/NaN
| propagation, etc. The fixes are consistently using fma for
| accumulation, biggest-factor scaling to prevent Inf, hypot use,
| etc.
|
| b) Ill-conditioned algorithms. Sometimes the text books lie to
| you, and the algorithms themselves are unfit for purpose,
| especially in boundary regions. If there are multiple expressions
| that have a <60% precision and only a 1 to 2% improvement across
| seeds, it's a good sign the algo is bad - there's no form that
| adequately performs on target inputs.
|
| c) Round-off, accumulation errors. This is more a consequence of
| agent reasoning, but often happens after an apparent "100% ->
| 100%" pass. The agent is able to, via failing tests, identify
| parts of an algorithm that can benefit from upgrading the context
| to e.g. double-word arithmetic for additional precision.
| Archit3ch wrote:
| > I work on 3D/4D math in F#. As part of the testing strategy
| for algorithms, I've set up a custom agent with an F# script
| that instruments Roslyn to find FP and FP-in-loop hotspots
| across the codebase.
|
| I don't know if there is an equivalent in Roslyn, but in Julia
| you can have the agent inspect the LLVM output to surface
| problems in hot loops.
| shiandow wrote:
| I wonder who decided to use a step function for the speed
| accuracy plot. They must have thought the convex hull would be
| wrong because you can't really make linear combinations of
| algorithms (you could, but you'd have to use time not speed to
| make it linear). So I get _why_ you would use step functions, but
| the step is the wrong way around. The current plot suggests
| accuracy doesn 't drop if you need higher speeds
| pavpanchekha wrote:
| It was me. Damn it you're right! Will fix!
| Archit3ch wrote:
| Thanks for reminding me to try this for audio approximations. :)
| fouronnes3 wrote:
| This is very interesting! I made an interval arithmetic
| calculator a few months ago [0]. I wonder if you could combine
| the two techs to make something even more powerful.
|
| [0] https://victorpoughon.github.io/interval-calculator/
| bhargavkk wrote:
| Herbie uses interval arithmetic a lot! The team has a in-house
| developed interval arithmetic library you can use at:
| https://crates.io/crates/rival3.
| fouronnes3 wrote:
| Working with tensor datatypes in numerical computing, I've been
| wondering if it would be possible to somehow add an extra
| dimension to tensors that would serve as the "floating point
| precision" dimension, instead of a data type. After all why
| couldn't the bit depth be one of the tensor dims? Maybe it would
| be possible to implement arbitrary floating point precision that
| way?
| summarity wrote:
| This is somewhat in line with the approach taken by some
| softfloat libraries, e.g.
| https://bigfloat.org/architecture.html
___________________________________________________________________
(page generated 2026-04-04 23:01 UTC)