What Makes a Hull Approximation Useful
Why exact local bounds can still lose joint information, and how the useful precision of an approximation depends on the property and the work needed to use it.
A good approximation is not merely a shape that looks close to the true one. It is a description that retains enough information to answer a question at an acceptable cost.
There are two scales to keep in view. A local bound may describe one neuron exactly while a collection of those bounds still permits impossible combinations. This is not a choice between relations and precision: losing a relation is one way the joint description loses precision. The question is which information the present verification task needs.
This note uses WraLU and WraAct as worked examples. The WraLU note explains how a function’s own pieces become the faces of a polytope. The WraAct note covers the containment contract: what has to survive conversion into a constraint matrix a solver reads. This note connects those constructions to the broader question of what information is useful and what it costs to keep.
A tight description of one piece says nothing about their combination
Bound propagation works neuron by neuron. For each activation you compute a region that contains every value that activation can take, given the input region. Every neuron gets one, and the network’s behaviour is then bounded through them.
Here is the problem, and it is not a subtlety — it is the reason the whole area exists. Each of those per-neuron regions is correct, and their composition can still be far too loose, because a set of individually valid statements about separate variables does not determine which combinations are actually reachable. The variables are not independent: they are outputs of the same input.
The natural example is a pair of ReLUs whose pre-activations are correlated. If one is large positive the other cannot be independently large negative, and a relaxation that treats them separately permits a combination that no input produces. Nothing is wrong with either per-neuron bound. What is missing is the relationship between them.
So there are two different things to preserve. What each neuron is allowed to do, which is what per-neuron bounds describe. And which combinations of those behaviours can occur together, which is a strictly larger amount of information and the part a loose relaxation throws away.
This gives the useful way to talk about tightness. A relaxation can be locally exact on every neuron and still describe a set of joint behaviours that no input reaches. The soundness and completeness chapter works through what that costs: a method can find a point that looks reachable and is not, then report UNKNOWN on a property that is actually true. The issue is not that relations oppose precision; the local description was precise while the joint description was not.
More information is available, and it is not free
If relations are what a relaxation is short of, the obvious response is to add them, and there are more ways to do that than a practitioner has time to implement. Some of them are worth understanding on their own terms, because each fails in a way that is instructive.
The exact hull. For ReLU over an interval, the convex hull is exactly describable, so an exact over-approximation exists and is cheap. That case is unusually friendly, and it is worth naming why: the function is piecewise linear, so the hull is a polytope with finitely many facets and can be written down. For a smooth activation it is not, and computing it is a hard geometric problem that is intractable in many cases. The useful distinction is between joint dependency across coordinates and function curvature: ReLU already supplies its linear pieces as known faces, while S-shaped and saturating functions require additional constraints because they lack flat regions, making the hull approximation depend on the analytic properties of the function rather than its discrete structure.
Worth being precise about what makes a description the hull, because it is easy to get this wrong in the direction of over-confidence. A polytope can touch the function at every one of its facets and still strictly contain it, since containment is an interior property: the curve can run through the middle without meeting a face at all. Take the unit circle and circumscribe a square — every facet is tangent, the square is convex, it contains the circle, and it is still not the convex hull, which is the disc. So the condition that characterises the hull is not tangency, and not convexity-plus-containment either, since the square satisfies both. It is minimality: the smallest convex set containing the graph. A relaxation that contains the graph and is convex is a valid outer approximation, which is a weaker thing than being the hull, and every construction below is aiming at the weaker thing on purpose.
A hull of sampled points. Compute the convex hull of a fine grid of points on the graph. This is tighter than a coarse construction and it is not sound: the graph bulges between the samples, and the sampled polytope does not contain those bulges. This is worth dwelling on because sampling is exactly the kind of method that looks rigorous in a plot and fails in a way no plot reveals. Validating on a sample does not discharge the problem either — the sample is the wrong kind of object, and the WraAct note works through why.
Every facet you can afford. Once you have a valid outer approximation you may keep adding facets to shrink the gap; each is sound if it lies above the graph, and each costs a constraint. The stopping point here is a budget decision dressed up as a geometric one.
A more expensive bound can save search
What makes the choice hard is that the price of adding information is not well described by counting constraints. Some constraints can be constructed once and reused. Others are recomputed or tightened when the input domain is split. Richer constraints may increase the cost of an individual solve while reducing the number of subproblems that remain. There is no general rule that a larger description is always slower, or that a faster construction always produces a faster verifier.
The practical questions are straightforward. Does the construction preserve every behaviour it is intended to cover? Does the information it keeps help decide this property? Does its benefit justify the total cost in the chosen verification process? These questions connect geometry to use without turning one size or runtime measurement into a universal ranking.
Two constructions that spend accuracy on purpose
The pattern appears twice here, and it is worth naming rather than illustrating twice.
WraLU reuses ReLU’s own linear pieces as the lower faces of the polytope and constructs upper faces adjacent to them, so the construction becomes bookkeeping over the function’s existing edges and vertices rather than a geometry search. The WraLU note has the construction and the scope condition that comes with it.
WraAct takes the S-shaped case directly, replacing the graph on with a double-linear-piece function: two affine pieces, combined by a maximum or a minimum. “A lower line and an upper line” is a different object. The max or min chooses the piecewise shape; it does not by itself prove that the result is above or below the target. Two affine pieces provide simple piecewise-linear geometry, but the appropriate enclosure inequality still has to be proved over the specified domain. Reported against SBLM+PDDM on Sigmoid, Tanh and MaxPool, it is more precise and much faster to construct, with about half the constraints. The WraAct note works through the definition, the tangent that licenses each piece, and what the library’s containment contract has to establish.
The shared move is not that tightness is bad. Each takes a construction whose cost is predictable and whose validity is checkable over a whole interval, and spends accuracy to get it. The accuracy given up is chosen rather than incidental, which is what makes it a design decision rather than a limitation — and it is also why the useful question is what an approximation keeps rather than how close it is.
The three questions
Whether a relaxation is worth using is not a property of the polytope. It is a property of the polytope composed with the solver, the network and the budget — and the three questions that decide it are answerable separately.
- Is it sound? This one is about the construction rather than about the assembled system, and the WraAct note sets out what discharges it — every emitted constraint justified over the whole domain, as a property of the function rather than of how many samples were drawn. It is not negotiable, and it is the only one of the three that can make a verifier unsound rather than merely unhelpful.
- Does it preserve the relations that decide this property? A relaxation can be locally exact on every neuron and describe joint behaviours no input reaches.
- Does the constructed system finish?
A construction can answer 1 and 3 while failing 2, and be right. One answering all three can still be too expensive for the chosen workflow, because practicality is not soundness. What is not available is answering 3 while ignoring 1: that is how unsound verifiers ship.
Further Reading
- Ma, Li, Bai. ReLU Hull Approximation (POPL’24) — reusing the function’s own linear pieces as lower faces.
- Ma, Wang, Bai. Convex Hull Approximation for Activation Functions (OOPSLA’25) — the double-linear-piece framework for S-shaped and saturating functions.
- Why Reusing ReLU’s Own Pieces Makes Hull Approximation Cheap — the WraLU construction in detail.
- Activation Hulls: What Makes an Approximation Sound? — the containment contract, and what validation actually has to establish.
- Soundness, Completeness, and UNKNOWN — why a tighter bound that cannot be computed in budget buys nothing.
Where to go next
Related research
- ReLU Hull Approximation
Discussed in this article alongside WraAct.
- Convex Hull Approximation for Activation Functions
Discussed in this article alongside WraLU.
Continue reading
- Why Reusing ReLU's Own Pieces Makes Hull Approximation Cheap
The short explanation of the ReLU case.
- Activation Hulls: What Makes an Approximation Sound?
The engineering side of the same geometry.
- Soundness, Completeness, and UNKNOWN
Worth reading next.