Exact Safety Monitors That Pay for Rounding in False Alarms

A safety monitor for a physical system is a classifier. Given the current state, it says "continue," "hand over to a backup," or "stop." Its two kinds of error are very unequal. Calling a doomed state safe can cause a crash. Flagging a safe state only costs an unneeded intervention. Hybrid symbolic-numeric verification can in principle prove the dangerous error never happens. It works in two steps: a fast floating-point solver finds an approximate proof, and exact rational arithmetic then turns it into a certificate that can be checked with no rounding error at all. The catch is that the exact step needs slack. The approximate proof must sit strictly inside the feasible region so its coefficients can be rounded to fractions without breaking it. Cost-sensitive training removes exactly this slack, because it pushes the monitor's "continue" boundary as close to danger as the data allow.

This note proposes to decide where that slack goes. The requirement that no unsafe state is ever labelled "continue" is proved exactly. The rounding and absorption error is then deliberately pushed into the "hand over" band, never into the "continue" region. Exactness then has a measurable price, paid only in the cheap error: extra deferrals and false alarms. The contribution is an algorithm and an empirical study of that price. The algorithm places the slack asymmetrically, guided by the cost matrix, and brings a bound on how much false-alarm cost the exact certificate adds. The study measures the price on standard polynomial barrier and reachability benchmarks.

Core Claim

Consider a monitor $g$, a polynomial in the state $x$, with two thresholds $t_1 < t_2$. The monitor says "continue" when $g(x) \le t_1$, "defer" when $t_1 < g(x) \le t_2$, and "alarm" otherwise. There are three decisions and two outcomes: the state either stays safe over a horizon or does not. Of the six resulting cells, one is catastrophic: "continue" on a state that will become unsafe. We make that cell exactly zero by requiring $\{g \le t_1\}$ to be a certified invariant that avoids the unsafe set, which is essentially a barrier certificate. The remaining cells are handled as an ordinary cost-sensitive learning problem over a distribution of operating states.

The claim is threefold. First, when standard uniform-margin rational recovery is applied to cost-optimized monitors, it either fails outright or forces the "continue" region to shrink by more than necessary. Second, the rounding residual can be absorbed through the threshold and multiplier structure so that its entire effect moves $t_1$ downward into the defer band. Third, at matched soundness, this asymmetric allocation gives a lower empirical cost than uniform slack, and the gap grows exactly in the regime the costs create: boundaries pinned tight against the unsafe set.

For a discrete-time polynomial system $x^+ = f(x)$ with unsafe set $X_u = \{u(x) \ge 0\}$, the certified part is the pair of Putinar-style constraints

$$ t_1 - g(f(x)) - \sigma_1(x)\,(t_1 - g(x)) \in \Sigma, \qquad g(x) - t_1 - \delta - \sigma_2(x)\,u(x) \in \Sigma . $$

Here $\Sigma$ is the set of sum-of-squares polynomials, $\sigma_1, \sigma_2 \in \Sigma$ are multipliers, and $\delta > 0$ is the margin separating the continue region from the unsafe set. The first constraint says a state in the continue region stays there after one step. The second says every unsafe state has $g$ above $t_1$ by at least $\delta$. The learned part is the choice of $g$, $t_1$ and $t_2$ that minimizes the cost-matrix-weighted rate of deferrals and alarms on sampled operating states. The margin $\delta$ is the interior "breathing room" that rational recovery consumes. Only the certified constraints ever need it.

Relation to Prior Work

The exact-recovery machinery comes from the certification line. RealCertify and On Exact Polya and Putinar's Representations show how to round an interior floating-point sum-of-squares solution to rational numbers and absorb the leftover error into dominant positive terms, within singly exponential bit complexity. Exact safety verification of hybrid systems using sums-of-squares representation and Exact Safety Verification of Hybrid Systems Based on Bilinear SOS Representation carry this to exact polynomial invariants using Newton refinement and rational vector recovery.

We reuse these techniques as the verification back end. All of them, however, treat the certificate's slack as a uniform nuisance and have no notion of which side of the boundary is expensive. The same group of papers also constrains the design. The absorption step fails when the target touches the boundary of the cone, and that is precisely the regime that asymmetric costs produce. Property-based Polynomial Invariant Generation shows that property-driven invariant search works, but that it grows to roughly 18,000 variables and 370,000 constraints for a 4-dimensional degree-8 instance. Our experiments therefore stay in the 2 to 7 dimension range where exactness is realistic.

On the cost side, Analyzing Cost-Sensitive Surrogate Losses via ℋ-calibration proves that cost-agnostic training followed by threshold shifting is not consistent for restricted model classes. Low-degree polynomial monitors are exactly such a class. This paper motivates putting the cost matrix into the synthesis objective rather than adjusting thresholds after the fact.

Learning to Offload with Low Regret under Asymmetric Misclassification Costs shows that asymmetric costs call for a two-threshold policy with an ambiguous middle region. It sets the thresholds statistically and treats the model as a black box. We keep the two-threshold structure but make the catastrophic threshold a proven object. We also give the middle region a new role: it is where the rounding error is absorbed.

The closest work at the intersection is Asymmetric conformal prediction with penalized kernel sum-of-squares. It uses kernel sum-of-squares models to learn asymmetric prediction intervals, but its guarantees are statistical and numerical, with no rational certificate over a continuous state space. Certified Robust Control under Adversarial Perturbations explicitly motivates asymmetric danger, for example mistaking black ice for dry pavement. Its perception certificate is probabilistic, from randomized smoothing, and it handles a single scalar parameter. Fossil 2.0 synthesizes neural barrier certificates with solver-based checks, but treats safety as a crisp binary set with no cost structure.

Research Program

The work has three parts.

The synthesis problem. We pose the synthesis as a sum-of-squares program. The certified constraints above are hard constraints with an explicit margin $\delta$. The objective is a cost-weighted, sample-based surrogate for the deferral and alarm rates of $g$ on operating states. Because the product of $\sigma_1$ and $g$ is bilinear, we alternate between solving for $g$ and for the multipliers, following the bilinear formulation of the bilinear SOS paper cited above. The surrogate is a smooth cost-sensitive hinge on $g(x_i) - t_1$ and $g(x_i) - t_2$. The operating states $x_i$ are sampled from a stated distribution, for example stationary operation under a nominal controller.

Asymmetric recovery. After the floating-point solve, we round $g$ and the multipliers to rationals. We then compute exact residual polynomials for both certified constraints. The residuals are absorbed in two ways. One part goes into the diagonal of the Gram matrix, as in intsos. The other part goes into a downward shift of $t_1$, re-checked exactly. The key step is a lemma to be proved and tested. When the residual in the invariance constraint is bounded on a compact domain, a shift of $t_1$ combined with a rescaling of $\sigma_1$ restores exact feasibility. Because the shift is taken out of the defer band, the continue region only shrinks toward safety. We then bound the added cost as the probability mass of states with $g(x)$ in the interval $[t_1 - \Delta, t_1]$, where $\Delta$ is the shift, weighted by the cost of a needless deferral.

The boundary-contact regime. Contact with the unsafe set is the failure mode that cost-sensitive optimization creates. We handle it with a margin-continuation schedule: the solver starts at a large $\delta$ and decreases it, and we keep the smallest $\delta$ for which recovery succeeds. We record the resulting "price of exactness" curve, which plots the added cost against $\delta$.

Baselines

The naive reference point is the same cost-sensitive floating-point monitor, with thresholds taken directly from the floating-point solution and no rational recovery. We then check it exactly in rational arithmetic after the fact. This measures how often cost-optimized numerical certificates are actually unsound, which is the empirical content of the boundary-degeneracy concern. It uses identical data, degree bounds and solver.

The strongest existing exact method is uniform-margin exact recovery in the style of Exact safety verification of hybrid systems using sums-of-squares representation. It is run on the same monitor structure with a symmetric objective, followed by post-hoc tuning of the thresholds on the cost matrix using the same validation set. It gets the same degree bounds, the same SDP solver, and the same wall-clock budget for its margin search. On the cost-weighted monitor metric, no reported result was found on Lacuna for this method or any other exact method. The nearest published numbers concern feasibility and runtime, not cost. On Completeness of SDP-Based Barrier Certificate Synthesis over Unbounded Domains reports success on arch4-2 and nagumo-2 where incomplete methods failed, without runtimes. Property-based Polynomial Invariant Generation reports about 25 minutes for its 4-dimensional degree-8 SDP.

The strongest solver-based competitor is Fossil 2.0. It reports a 100% barrier synthesis success rate on its suite and 50 seconds for an inverted-pendulum reach-avoid-remain certificate. We run it with dReal as the verifier on the same systems and add a cost-weighted term to its learner loss, so that it competes on cost and not only on feasibility. We report its guarantee type honestly. dReal's δ-decision guarantee is exact only up to a user-chosen numerical tolerance δ, whereas our certificates are exact rational identities.

Two ablations isolate the key ingredient. The first uses uniform slack with a cost-sensitive objective; it separates asymmetric recovery from cost-aware training. The second uses asymmetric recovery with a cost-agnostic objective and post-hoc thresholds; it separates cost-aware training from the recovery step.

Beating the baselines means the following. The method must have zero exact-check failures, which the naive and dReal baselines may not achieve at matched δ. It must also show a statistically significant reduction in cost-weighted deferral and alarm rate relative to uniform-margin exact recovery, at equal degree and budget, averaged over seeds for the sampled operating states.

Why not just…?

Why not just check the floating-point certificate with interval arithmetic and skip rational recovery? This is a real threat in two dimensions. An interval bound on the sum-of-squares residual over a small box may be cheap and tight enough. It still needs a margin, so it faces the same question of where to spend that margin. It also becomes looser as dimension grows. We include it as an additional back end inside the asymmetric-allocation algorithm and compare the price-of-exactness curves on CVDP20 (4D) and LALO20 (7D) from the ARCH-COMP21 nonlinear suite. If interval checking matches rational recovery there, we report asymmetric allocation as the contribution independent of the back end.

Why not just certify a symmetric monitor and shift its thresholds using the cost matrix? Shifting $t_1$ downward preserves soundness, so this baseline is safe. However, Analyzing Cost-Sensitive Surrogate Losses via ℋ-calibration shows that post-hoc shifting cannot recover what cost-agnostic training loses in restricted hypothesis classes. On German Credit it reports a cost-sensitive loss of 0.589 ± 0.013 for the embeddings surrogate versus 0.796 ± 0.020 for cross-entropy with thresholding. Whether this carries over to low-degree certified monitors is exactly what the second ablation tests. A null result would show that the shape of $g$ does not matter and only the threshold does.

Why not just use a statistical guarantee, such as conformal or Neyman-Pearson thresholds, on the catastrophic error? These bound the miss rate over a sampled population, not over every reachable state. Certified Robust Control under Adversarial Perturbations shows how badly unverified perception fails under attack: accuracy drops to 0% and the instability measure rises to 200.0, against 6.36 when certified. We include a conformally calibrated two-threshold monitor built on the same $g$. We then search for "continue"-labelled states that reach the unsafe set, using falsification by optimization over initial states. A nonzero hit rate for the statistical monitor, together with zero for ours, settles the comparison. A zero hit rate for both on these benchmarks would weaken the practical case, and we would report it.

Proposed Experiments

Systems. We use the polynomial barrier instances from the unbounded-domain completeness paper: arch4-2, nagumo-2, vector-1/2 and barrier-1/2. We add the polynomial systems in the Fossil 2.0 suite and CVDP20 and LALO20 from ARCH-COMP21. Continuous-time instances are handled with the Lie-derivative analogue of the invariance constraint.

Data and labels. For each system we fix an operating-state distribution. Each sampled state is labelled by whether simulation under bounded disturbances reaches $X_u$ within a horizon. These labels are used only for the cheap-error cost. The catastrophic cell is handled formally.

Metrics. We report the exact-check pass rate; the cost-weighted deferral and alarm rate under several cost ratios (1:10, 1:100, 1:1000); certificate bit size; and runtime. We also report the price-of-exactness curve, defined as added cost versus the floating-point optimum.

Decisive checks. The first check tests whether the problem exists. Cost-optimized floating-point monitors should fail exact checking at a nonzero and cost-ratio-dependent rate. If they almost never fail, the tension around boundary contact is not practically important, and the proposal narrows to certifying already-safe monitors cheaply.

The second check is the core claim. At matched soundness, asymmetric allocation should reach lower cost than uniform slack, with the gap widening as the cost ratio grows. The mechanism predicts this, because higher ratios pin $t_1$ closer to $X_u$.

The third check tests the cost bound from the research program. The measured added cost should lie below the bound computed from the probability mass in $[t_1 - \Delta, t_1]$ on held-out operating states.

The fourth check is scaling. We report where rational recovery stops succeeding within a fixed budget as dimension and degree grow. We report this as the method's honest operating envelope, not something to hide.