The Bound Dominates the Budget: Certified Explanations for Additive Models

How stable a minimal explanation of an additive model is depends far more on which sound bound certifies it than on how many features it names. A greedy minimal explainer stops the instant its error budget is met, spending 85.2–98.7% of the tolerance ε under its own unsigned acceptance test; certified against that test the radius is near zero, and buying 0.8 extra features moves it from 0.009 to 0.29 on heart at r_max = 0.5. But that test is not the predicate the explanation makes. The displayed surrogate's error is a sum of signed one-dimensional terms whose worst case over the ball is attained in closed form for main effects (Prop. 4); certified against it, the same minimal explanations have spent 32–38% and already reach 0.34 on heart, and the knob buys a further 1.2×, not 31.7 (at the wider r_max = 2.0 error table, 0.45 and 1.5×, not 14.9). The free change is worth more than the one we sell. Measuring this needs a certificate rather than a sampled sensitivity score, and additive structure makes one cheap: for ŷ = Σ_i f_i(x_i) the L∞ worst-case output change decomposes exactly across features, so a sound per-input radius is d one-dimensional interval problems. We make that practical for continuous neural shape functions — dense-grid extrema padded by a certified analytic operator-norm Lipschitz bound — and pair it with a per-feature worst-case error table, so the certified object is the displayed surrogate: a subset and its functional forms. The same holds one level up: what a backbone leaves after minimality differs up to 11× across model classes unsigned and 1.3–1.4× signed — both off the censoring ceiling, and only on heart is there an order-of-magnitude gap for the bound to close — so the choice of backbone is worth an order of magnitude less than the choice of bound — though which backbone leads is not stable, and EBM keeps heart. We instantiate on VIB-NAM, a bottleneck+bypass additive net, and are explicit that the bottleneck carries none of the results. Scope, costs and the failed tests are stated in §1; a provenance gate recomputes every headline number from the shipped artifacts.