Monitoring Discounted Sum Properties

Filip Cano, Thomas A. Henzinger, Konstantin Kueffner, N. Ege Saraç

TL;DR

Runtime monitoring of quantitative signals faces a fundamental trade-off between noisy short-term spikes and over-smoothed long-term averages. This paper formalizes "discounted sums" as a principled middle ground, proves that exact monitoring is impossible with finite memory, and introduces an $\varepsilon$-approximate framework with tight resource and delay bounds for both deterministic and stochastic streams.

What Problem Does This Paper Address?

When monitoring real-time quantitative signals—such as CPU temperature, machine learning model accuracy, or algorithmic fairness metrics—engineers face a dilemma. Single data points are highly volatile and noisy, while long-run averages smooth out critical local anomalies (e.g., a temporary but dangerous spike in temperature).

"Localization measures" like discounted averages weight recent events more heavily, offering a natural middle ground. However, their properties haven't been rigorously formalized for runtime verification. Specifically, how much memory and time do you need to monitor a discounted sum accurately when both the past and future are theoretically infinite or unknown?

Methods

The authors tackle this problem by analyzing discounted sums from both deterministic and stochastic perspectives:

  1. Impossibility Proof: They mathematically prove that exact, sound monitoring of discounted sums cannot be achieved with finite memory due to the infinite horizon of unseen future values.
  2. $\varepsilon$-Approximate Monitoring: To bypass this limitation, they introduce a tolerance parameter ($\varepsilon$). They derive an explicit observation horizon ($\tau^*$) after which a monitor can guarantee a sound verdict within an $\varepsilon$-boundary.
  3. Statistical Extension: For stochastic processes, they introduce expected discounted sums evaluated over conditional expectations. They define three nested levels of statistical guarantees: pointwise, local, and uniform $(\varepsilon, \delta)$-soundness.
  4. Affine Register Machines (ARMs): They formalize the resource complexity of these monitors using ARMs (finite-state machines with real-valued registers and affine updates) to quantify exactly how many registers are needed to track pending timelines.
  5. Specification Language: They develop an expression language to handle arithmetic relations over multiple discounted sums, supporting both synchronous (time-driven) and asynchronous (event-driven) semantics.

Datasets

The authors evaluated their approach using a mix of real-world traces and synthetic benchmarks:

  • PowerData: A dataset of power usage traces from Google data centers, used to evaluate register usage efficiency.
  • Adult Dataset: Demographic parity traces produced by a fairness-aware neural network trained on the Adult census dataset, used to evaluate algorithmic fairness monitoring.
  • MNIST: Traces of neural network classification accuracy under an induced distribution shift (created by adding time-increasing Gaussian noise to the inputs).
  • Synthetic Beta Process: A piecewise-stationary stochastic process used to validate the power and behavior of the statistical monitors.

Key Insights and Ideas

  • The Epistemic Uncertainty Limit: Exact monitoring is impossible because unseen future values introduce an irreducible uncertainty. While this uncertainty decays geometrically over time, it never hits zero instantly, meaning a sound exact monitor must remain inconclusive indefinitely in worst-case scenarios.
  • Memory Equals Delay: In deterministic monitoring, the observation horizon $\tau$ serves a dual purpose: it defines the maximum delay before a verdict is guaranteed, and it dictates the maximum number of parallel running sums the monitor must maintain.
  • Synchronous vs. Asynchronous Efficiency: For multi-stream properties (like comparing acceptance rates between two groups for demographic parity), synchronous monitoring—where every clock tick advances discounting across all streams—is significantly more resource-efficient than asynchronous monitoring, where discounting only advances when a specific stream receives an event.

Key Results

  • Tight Resource Bounds: The authors proved a tight worst-case lower bound for future-only monitoring: for a horizon of $k$, a monitor requires exactly $k$ registers.
  • Empirical Memory Savings: In practical evaluations on the PowerData and MNIST datasets, the actual number of active registers needed was consistently under 60% of the theoretical upper bound and never exceeded 80%. This indicates that engineers can safely under-provision memory in real-world deployments.
  • Statistical Optimality: The deviation bounds used for the pointwise sound statistical monitors were proven to be minimax optimal, establishing a hard mathematical threshold beyond which statistical discounted monitoring is impossible.

Limitations and Future Work

  • The Bi-directional Memory Gap: While the tight register complexity bound is proven for the future-only setting ($r=0, s>0$), the exact register complexity for the general bi-directional case (discounting both past and future, $r>0, s>0$) remains an open question.
  • Asynchronous Unboundedness: Under asynchronous semantics, a stream can contain an arbitrary number of empty events for a given atom. This makes it impossible to guarantee a minimum required observation time without placing further structural assumptions on the input stream.

Summary updated

Abstract

Runtime monitoring of quantitative signals faces a fundamental trade-off between volatility and over-aggregation: instantaneous observations are noisy, while long-run averages obscure local structure. Localisation measures such as discounted averages offer a principled middle ground, yet remain poorly understood in runtime verification. This paper studies discounted sums from a monitoring perspective, in both deterministic and stochastic settings. We formalize the discounted monitoring problem and show that exact, sound monitoring of discounted sums cannot be achieved with finite memory. To overcome this impossibility, we introduce $\varepsilon$-approximately sound monitoring, deriving explicit bounds on memory and observation requirements. We then extend the framework to stochastic processes via expected discounted sums, defining pointwise and uniform $(\varepsilon,δ)$-soundness notions, establishing statistical optimality, and proving impossibility beyond a precision threshold. We also formalize the resource complexity of deterministic discounted monitoring via affine register machines and prove a tight worst-case lower bound. Finally, we present a specification language for arithmetic expressions over multiple discounted sums with synchronous and asynchronous semantics, and evaluate our approach on practical scenarios including algorithmic fairness.
BibTeX
@inproceedings{cano2026monitoring,
  author = {Filip Cano and Thomas A. Henzinger and Konstantin Kueffner and N. Ege Saraç},
  title = {{Monitoring Discounted Sum Properties}},
  booktitle = {CONCUR},
  year = {2026},
  doi = {10.4230/lipics.concur.2026.22},
}
Figure