acceptodds
Under review as a conference paper at ICLR 2027

Runtime Monitoring of Supermartingale Certificates

Abstract

Supermartingale certificates formally guarantee temporal properties of discrete and continuous-time stochastic dynamical systems. However these guarantees rely and hold within a mathematical model of the world, leaving a sim-to-real gap that can render them invalid under the deployed system. We formulate the runtime monitoring problem for supermartingale certificates, in which a monitor observes a single system trajectory and raises an alarm when there is sufficient statistical evidence that the supermartingale certificate has been violated during execution. We present an algorithm to automatically construct a monitor using betting-based sequential tests that bound the probability of ever raising a false alarm at a user-specified level. Within this betting framework we formulate strategies that allow the monitor to exploit spatial regularity to improve detection power while preserving this statistical guarantee. We demonstrate the efficacy of our approach on supermartingale certificate benchmarks from the literature.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Supermartingale certificates, Runtime verification, Sequential hypothesis testing, Stochastic dynamical systems

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_nPRsOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the problems of detecting violations of barrier conditions expressed via supermartingales at runtime. Their approach combines existing results from runtime monitoring and betting-based sequential testing to address the specific problem. The approach is evaluated on several benchmarks.

Critical strengths
  • The paper considers a problem that, to the best of my knowledge, has not been much explored in the stochastic setting

  • The approach provided by the authors is sound, and the experiments show the effectivness of the approach

Critical weaknesses
  • Much of the statistical machinery follows established betting-based sequential-testing methodologies, such as those used by Timans et al. (UAI 2025). While this is not a weakness in itself, it limits the methodological novelty. In addition, [Feng et al. "Runtime safety and reach-avoid prediction of stochastic systems via observation-aware barrier functions." AAAI 2026] also develop barrier-based runtime safety and reach-avoid prediction for stochastic systems. Although the objective differs from that in this paper, this relevant work should be discussed and the distinction clarified.

  • Parts of Section 3, particularly Section 3.2, present the framework very generally, without consistently connecting the abstract construction to the specific monitoring problem. Making these connections more explicit would improve the readability of that Section, which is currently not easy to read, especially for readers unfamiliar with sequential testing. Furthermore, the authors should clarify how the parameters required by the theory are selected across the benchmarks and strategies.

  • The main text reports ground truth for the control benchmarks but does not provide a corresponding assessment for the neural experiments.

  • There are some typos in the notation. For instance, in the Supermartingale definition, l is used both as the extreme of the interval and as a drift bound and x_T_n is sometimes called x_n

Questions for authors
  • Can you clarify the differences with [Feng et al. "Runtime safety and reach-avoid prediction of stochastic systems via observation-aware barrier functions." AAAI 2026] and the main technical contributions compared to state of the art?

  • Can you clarify how how the parameters required by the theory are selected across the benchmarks and strategies?

  • Can you report the ground truth also for neural networks and also clearly discuss/report the conservativism of the approach in the various experiments?

2 comments

We thank the reviewer for the valuable feedback and comments.

[Q1] We clarify that [Feng et al., 2026] consider an orthogonal problem and use a different technique. [Feng et al., 2026] consider a given and known stochastic system model, and use observation-aware barrier functions to update bounds on the safety and reach-avoid probability with respect to that known model. Thus, they are concerned with the problem of refining the probability of satisfying a property in the given model at runtime. On the other hand, our framework is model-free and only takes as input a certificate that has been verified during the design stage. We then use runtime monitoring to detect certificate violations in an unknown deployment model (which may differ from the design model) at runtime. Thus, these are two different and orthogonal problems. We will discuss this in Related Work.

Our main technical contribution is that, to the best of our knowledge, we present the first framework for runtime monitoring and detecting violations in supermartingale certificates for stochastic systems. While our betting strategies build upon prior work, their application to runtime certificates is novel. Moreover, as discussed in l.112-118, our framework is applicable to all linear temporal logic and omega-regular properties, which is a significantly different and novel domain to which betting strategies have previously not been applied.

[Q2] We distinguish parameters relevant for soundness (l.287-300) and for detection power (l.302-314). We will clarify this and provide full parameter details in the final version:

Soundness: We choose the conventional false-alarm tolerance of 0.05. The loss bounds follow from certificate nonnegativity or known one-step bounds from the dynamics. We use the exact nominal drift for Hill, Ring and LQR. For Building and Tanks, we use independently verified upper bounds that retain some slack. For neural certificates, we test nonincrease and two decrease requirements motivated by the training parameter and reduced step size; these conditions are not verified for the adapted dynamics.

Power: Spatial and temporal scales affect detection power: small scales isolate local violations, while larger scales use more observations and reduce noise. For synthetic benchmarks, we calibrate scales on independent reference states or observation ages to target effective sample sizes from 32 to 8192. For control and neural benchmarks, we equally mix five scales spanning short to long histories and small to broad spatial neighbourhoods. These choices remain fixed for all benchmarks, to avoid tuning the monitor to a particular benchmark.

[Q3] We clarify that, for neural experiments, it is not possible to evaluate the ground truth for the expected value since there is no closed-form expression for the expected value of a neural network function. We will add a sentence to clarify this.

Regarding conservatism of the approach, the most significant source of conservatism is that when we bound the allowed drift, we may subtract more than necessary from the observed certificate change. In principle, this may make the certificate change harder to detect and require more observations than necessary. But we did not observe this to be an issue in our experiments. We will add this discussion.

We thank the reviewer again for the valuable feedback and comments.

We have now incorporated the changes described in our rebuttal into the revised paper, which we posted as an official comment. The changes are highlighted. Specifically:

  • [Q1] Related work: added the discussion of Feng et al. and the distinction from our monitoring problem in Section 5 (p. 10).

  • [Q2] Parameter selection: expanded Appendix E with the parameter choices, their rationale, and benchmark-specific score bounds (pp. 29–33).

  • [Q3] Neural ground truth: added the explanation in the main text (p. 8) and clarified the status of the monitored conditions under the adapted dynamics (p. 32).

  • [Q3] Conservatism: added discussion of drift slack and loss normalisation (p. 31), alongside the theoretical discussion (p. 27) and a CartPole comparison of certificate conditions (pp. 54–55).

Please let us know if any concerns remain or if we could clarify anything further. If our response and revisions address your concerns, we would be grateful if you would consider updating your score.

Reviewer_7ZPfOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a runtime monitor that uses a single observed trajectory to detect when a previously verified stochastic certificate stops satisfying its defining conditions after deployment. It converts certificate changes into a betting-based statistical test with a bound on the probability of ever raising a false alarm.

Critical strengths

The problem studied in this paper is very important as it establishes the connection between the often too theorized supermartingale safety certificates to the more complicated deployment scenarios. The theoretical results seem sound.

Critical weaknesses
  1. The comparison in the experiments are largely limited to different versions of the same betting structure. Adding comparison with additional structures as follows, plus some established sequential risk monitoring methods (e.g., Timans, Alexander, et al. "On continuous monitoring of risk violations under unknown shift." arXiv preprint arXiv:2506.16416 (2025).; Jiang, Rong, and Keming Yu. "Estimating means of bounded random variables by betting." JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY 86.1 (2024).), would further validate the claim.

Spatially partitioned betting monitor.

Fix regions R1,…,RJR_1,\ldots,R_J before evaluation and choose a finite set of stakes Λ⊆[0,1]\Lambda\subseteq[0,1]. For each region–stake pair, maintain Gj,λ,n=∏k=0n−1(1+λ1Xtk∈Rj∩SWk)G_{j,\lambda,n}=\prod_{k=0}^{n-1}\left(1+\lambda\mathbf{1}_{\\{X_{t_k}\in R_j\cap S\\}}W_k\right).

Combine these accounts as Gn=∑j=1J∑λ∈Λαj,λGj,λ,nG_n=\sum_{j=1}^{J}\sum_{\lambda\in\Lambda}\alpha_{j,\lambda}G_{j,\lambda,n}, using fixed weights satisfying αj,λ≥0\alpha_{j,\lambda}\geq0 and ∑j=1J∑λ∈Λαj,λ=1\sum_{j=1}^{J}\sum_{\lambda\in\Lambda}\alpha_{j,\lambda}=1. Raise an alarm when Gn≥1/δG_n\geq1/\delta.

Region membership is determined before observing the next transition, so under the paper's score assumptions this construction preserves the anytime false-alarm bound δ\delta. Regions may be selected using separate data and then fixed before evaluation.

Mixture of fixed-stake betting strategies.

Choose constant stakes, for example Λ=1,2−1,…,2−m\Lambda=\\{1,2^{-1},\ldots,2^{-m}\\}, and launch times T\mathcal{T}. For each stake λ\lambda and launch time ss, maintain Gλ,s,n=∏k=sn−1(1+λ1Xtk∈SWk)G_{\lambda,s,n}=\prod_{k=s}^{n-1}\left(1+\lambda\mathbf{1}_{\\{X_{t_k}\in S\\}}W_k\right) for n>sn > s, and set Gλ,s,n=1G_{\lambda,s,n}=1 for n≤sn\leq s.

Combine these accounts as Gn=∑s∈T∑λ∈Λβs,λGλ,s,nG_n=\sum_{s\in\mathcal{T}}\sum_{\lambda\in\Lambda}\beta_{s,\lambda}G_{\lambda,s,n}, using fixed weights satisfying βs,λ≥0\beta_{s,\lambda}\geq0 and ∑s∈T∑λ∈Λβs,λ=1\sum_{s\in\mathcal{T}}\sum_{\lambda\in\Lambda}\beta_{s,\lambda}=1. Capital assigned to future launches remains in reserve until launch.

Use the same launch times, funding schedule, score normalization, and alarm threshold as the proposed monitors. Under the same score assumptions, raising an alarm when Gn≥1/δG_n\geq1/\delta preserves the anytime false-alarm bound δ\delta.

  1. Further discussion about the entire line of work on robust and uncertainty aware safety certificates (e.g., Schön, Oliver, Zhengang Zhong, and Sadegh Soudjani. "Data-driven distributionally robust safety verification using barrier certificates and conditional mean embeddings." 2024 American Control Conference (ACC). IEEE, 2024. Wajid, Rameez, Asad Ullah Awan, and Majid Zamani. "Formal synthesis of safety controllers for unknown stochastic control systems using Gaussian process learning." Learning for Dynamics and Control Conference. PMLR, 2022.) is missing, as these methods can be used to solve the problem of inaccurate models for safety certificate constructions as well.
Questions for authors

See Critical Weaknesses.

3 comments

We thank the reviewer for the valuable feedback and comments.

[Q1] Comparison to sequential and other betting strategies. We implemented and experimentally compared our Spatial betting strategies with the four betting strategies proposed by the reviewer: (1) Timans-AGR (reference [Timans et al., 2025] in the review), (2) PrPl-EB (proposed in [Waudby-Smith et al. 2023], and discussed in the reference [Jiang et al., 2024] in the review), (3) the spatial-partition betting strategy proposed by the reviewer, and (4) the fixed-stake betting strategy proposed by the reviewer.

Our results show that our Spatial betting strategy generally offers better performance compared to all four of these betting strategies; see the summary of our experiments below. We believe that this is because our Spatial betting strategy exploits the spatial regularity of real-world processes. In contrast, the four betting strategies above have the following disadvantages:

  • Local Information: We observe that Timans-AGR (1), PrPl-EB (2), and fixed-stake (4) struggle with recurrent certificate violations because they do not exploit spatial information. For instance, in the recurrence example after 2,048 healthy observations, the fixed-stake mixtures detect 0/50 violations and Timans-AGR detects 0/50. In contrast, our Spatial betting strategy detects 44/50. In addition, PrPl-EB (2) is also restricted to bounded variables.
  • Dimensionality: We observe that the spatial-partition betting strategy (3) is sensitive to the choice of partition. Coarse cells may combine violating and nonviolating states, while finer partitions divide capital among more cells, which limits this betting approach to applications with low dimensionality. For instance, in Tanks at level-dependent inlet amplitude 0.3, both tested four-bin-per-coordinate partition variants detect 0/50 runs, compared with 50/50 for our Spatial betting, with an unconditional 50% detection delay of 644 observations. When we append coordinates that remain fixed along each trajectory, the uniformly weighted eight-bin-per-coordinate partition with periodic funding detects 24/50, 8/50, 0/50 and 0/50 runs in dimensions 2, 4, 8 and 16, respectively, while our Spatial strategy remains at 44/50.

We will add a remark in the final version of the paper to discuss this, and provide the full additional experiments in the dedicated section in the Appendix.

[Q2] Related work on robust and uncertainty-aware certificates. We agree that robust and uncertainty-aware safety certificates constitute related work that should be discussed, and we will include a paragraph in the Related Work section. However, we note that they consider a different and complementary problem. Robust certificates accommodate a fixed set of models at the design time, by requiring a certificate to be valid with respect to all models in the set. On the other hand, our runtime monitoring framework detects certificate violations at the deployment time. Hence, the two methods are complementary and target different stages of the certificate correctness assurance pipeline (design vs deployment stage). In particular, runtime monitoring can provide additional assurances when the model mismatch upon deployment is not covered by the set of models considered in the robust certificate design. We will include this discussion in the Related Work.

We thank the reviewer again for the valuable feedback and comments.

We have now incorporated the changes described in our rebuttal into the revised paper, which we posted as an official comment. The changes are highlighted. Specifically:

  • [Q1] Additional comparisons: added the four baseline comparisons and the experiments on partition sensitivity and dimensionality in Appendix I (pp. 49–52), with a summary of the findings on p. 9.

  • [Q2] Related work: added the discussion of robust and uncertainty-aware certificates and their relationship to deployment-time monitoring in Section 5 (p. 10).

Please let us know if any concerns remain or if we could clarify anything further. If our response and revisions address your concerns, we would be grateful if you would consider updating your score.

I am convinced of the author's update. The score is now raised.

Reviewer_1VhLOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper presents a runtime monitoring system of Supermartingale certificate, which provides guarantee to temporal properties of discrete and continuous-time stochastic dynamical systems. The limitation of such approaches is that the guarantee has been made within mathematical world models. Therefore, this work focuses on the real systems, creating a runtime monitoring system that tracks the system trajectory and check statistic evidences of Supermartingale certificate violation. This work also presents an algorithm that bounds the chances of false alarms.

Critical strengths
  • This work addresses an important practical problem by bridging the gap between theoretical guarantees and real-world deployment of stochastic systems.
  • The proposed spatial prediction strategy demonstrates substantial improvements in detection performance over the uniform and temporal prediction strategies in several evaluated benchmarks.
Critical weaknesses
  • Detection latency needs more clarification; detection delay is presented in number of observations only.
  • The evaluation compares different configurations of the proposed work. A comparison with existing sequential change-detection methods would help demonstrate the merit of the proposed work.
Questions for authors
  • This work relies on statistical evidence accumulated over multiple observations, which may introduce significant detection latency. As shown in Table 1, some cases require thousands or even tens of thousands of observations before detection. This could be a major challenge for safety-critical systems, where delayed detection may prevent timely corrective action. How do these observation-based detection delays translate into actual physical time? More importantly, are these delays acceptable for the targeted applications, considering that unsafe behavior could develop before a violation is detected?

  • Although this work is motivated by bridging the gap between theoretical guarantees and real-world deployment, the evaluation experiments are conducted in simulated environments with predefined disturbances. Moreover, as described in Appendix E.3, some system dynamics are artificially modified to obtain longer trajectories. Considering these factors, it remains unclear how representative the evaluation configurations are of realistic deployment scenarios. Additional evidence or discussion justifying the representativeness of these configurations would strengthen the evaluation.

2 comments

We thank the reviewer for the valuable feedback and comments.

[Q1] Detection delay. We agree that the detection delay may be problematic for highly time- and safety-critical settings, which is a general limitation of runtime monitoring methods for uncertain systems that is not specific to our method. However, we clarify that our method is not designed for such settings. We recall again the setting that we consider (see l.47-53 in the Introduction):

We assume that we are given a supermartingale certificate computed at design time. The goal is to detect certificate violations upon deployment in a black-box stochastic environment that may deviate from the design environment. The underlying assumption here is that the design environment provides a sufficiently faithful approximation of the deployment environment, as otherwise the computed supermartingale certificate is not useful in the first place. Hence, we do not expect certificate violations to happen immediately. Rather, they happen due to e.g. distribution shifts or gradual degradation of certain system components, which provides sufficient time to detect the violations.

We will expand the paragraph in l.47-53 to make this motivation clearer. In addition, to support this argument, we designed an additional experiment on the CartPole environment that models a cyberphysical system (CPS) control task with a supermartingale certificate. The continuous balancing of the CartPole naturally permits long trajectories. We consider deployment environment changes due to (1) abrupt actuator loss, and (2) force pulses to simulate wind. In both cases, we use an observation frequency of 100 Hz (0.01 seconds), which is a realistic assumption in CPS. Our experiments lead to the following results:

  • For the deployment environment modelling the abrupt total actuator loss which starts after 5 seconds upon deployment, the spatial monitor S-L requires 0.65 seconds to detect a certificate violation;
  • For the deployment environment modelling a force pulse due to wind which starts after 5 seconds upon deployment and lasts for 0.5 seconds, the spatial monitor S-L requires 0.16 seconds to detect a certificate violation.

This experiment supports the argument that our runtime monitoring framework provides a practical approach to detecting supermartingale certificate violations in CPS applications. We will add this experiment in the Appendix of the final version, and reference it in the paragraph in l.47-53, to support our argument.

[Q2] Experiments. We clarify that our modifications of neural control benchmarks are to delay system termination through reasonable disturbances, because the original benchmarks model systems that take only a few steps (ranging from 3-10) to solve the task. In real-world CPS, the systems have longer durations with an actuator that can act at a much higher frequency, e.g. 100 Hz (0.01 seconds) as in the CartPole example above.

[W2] Comparison with existing sequential change-detection methods. We performed additional experiments to compare our monitors against other existing sequential detectors. We consider the four approaches suggested by Reviewer 7ZPf. To summarise, our results show that our Spatial betting strategy generally offers better performance compared to the suggested approaches. See the response to Reviewer 7ZPf, question 1, for these additional experiments.

We thank the reviewer again for the valuable feedback and comments.

We have now incorporated the changes described in our rebuttal into the revised paper, which we posted as an official comment. The changes are highlighted. Specifically:

[Q1] Detection delay: expanded the deployment motivation and added the introductory reference to the physical-time experiments (pp. 1–2), with the full CartPole evaluation in Appendix J (pp. 51–56).

[Q2] Representativeness: added the CartPole experiments with naturally long trajectories, referenced on p. 9 and detailed in Appendix J.

[W2] Additional comparisons: added the four baseline comparisons in Appendix I (pp. 49–52), with a reference on p. 9.

Please let us know if any concerns remain or if we could clarify anything further. If our response and revisions address your concerns, we would be grateful if you would consider updating your score.

Comments on the paper

1 comment

We thank all reviewers for their valuable feedback and comments.

We have attached a revised version of the paper incorporating the additional experiments and clarifications described in our rebuttal. The changes are highlighted and include comparisons with alternative monitoring methods, CartPole experiments assessing detection delays in seconds, expanded related work, and further details on parameter selection and conservatism.

We provide reviewer-specific summaries of the revisions, with page references, in separate comments. Please let us know if there are any remaining concerns or points we could clarify.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.