mstlo : Efficient Online Monitoring of Signal Temporal Logic

Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen · 2026

Read mstlo : Efficient Online Monitoring of Signal Temporal Logic by Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26847.txt.

Introduction

Thomsen and five colleagues release mstlo, a Rust library for fast online monitoring of signal temporal logic, with Python bindings. It unifies several logic semantics, including robust satisfaction intervals and Boolean checks with early verdicts, and uses incremental dynamic programming with per-operator caching. An embedded domain-specific language adds static syntax checks in Rust. Benchmarks show strong scaling and speed gains over leading tools, especially on deeply nested formulas.

Catalog record

CREATORAndreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20967
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.26847

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

mstlo : Efficient Online Monitoring of Signal Temporal Logic Andreas Kaag Thomsen, Niels Viggo Stark Madsen, Valdemar Tang Evans, Thomas David Wright, Lukas Esterle, Peter Gorm Larsen Abstract We present mstlo ( mistletoe ), a Rust library for high-performance o nline m onitoring of s ignal t emporal l ogic (STL), with Python bindings. The library provides: (i) a unified interface for multiple STL semantics, including Robust Satisfaction Intervals (RoSI) and Boolean evaluation with early verdicts; (ii) an incremental monitoring algorithm based on bottom-up dynamic programming with per-operator caching and streaming extremum computation for temporal operators; and (iii) an embedded STL domain-specific language for both Rust and Python implementations, with procedural macros in Rust for static syntax checking. Benchmarks show scalability and performance improvements over state-of-the-art tools, especially for formulas with large temporal depth and deep nesting. 1 Introduction The growing deployment of Cyber-Physical Systems (CPSs) motivates the use of methods for ensuring correctness during operation [ 9 ] . One widely adopted approach is Runtime Verification (RV), in which a monitor observes the system’s behavior in real time and checks it against formally specified properties [ 11 ] . Among the specification languages used in this context, Signal Temporal Logic (STL) [ 12 ] is widely used for CPSs, enabling precise specification of timing constraints, safety requirements, and performance bounds over real-valued continuous-time signals. STL admits both qualitative and quantitative semantics, along with offline and online monitoring algorithms [ 2 , 12 ] . In online monitoring, an important goal is to produce a verdict as early as possible, without waiting for the full temporal depth of the specification to elapse. This capability is essential for real-time fault detection but imposes stringent performance requirements: the monitor must be highly efficient to minimize latency and ensure the verification process does not lag behind the system itself. In this paper, we present mstlo , a high-performance RV library implemented in Rust. Our tool provides a user-friendly interface for writing STL formulas and building monitors, while delivering the efficiency and performance required for production deployment. mstlo is the first dedicated tool for online monitoring of multiple STL semantics, which includes delayed verdicts, so-called Robust Satisfaction Intervals (RoSIs) as well as Boolean early verdicts. Our tool provides the following key features: • Unified Semantics Interface: We provide a unified framework supporting multiple online evaluation semantics via efficient stateful streaming algorithms. • Embedded Domain-Specific Language (DSL): We introduce a Rust macro-based DSL integrating STL specifications directly into source code, with parametrized formulas, syntactic sugar, and static syntax checking via procedural macros 1 1 1 https://github.com/rust-lang/rust-analyzer . • Efficiency and Benchmarking: We demonstrate that our incremental algorithm is scalable and achieves high throughput exceeding state-of-the-art tools, and provide a reproducible benchmark suite for hardware-specific performance evaluation. • Open-source Rust crate with Python bindings: Our library is available as an open-source Rust crate, ensuring accessibility and ease of integration. Additionally, we provide Python bindings to facilitate adoption within the widely-used Python ecosystem. The source code for mstlo is available at GitHub 2 2 2 https://github.com/INTO-CPS-Association/mstlo , along with documentation, installation instructions, examples and comprehensive tests. mstlo has also been successfully used in a teaching context in the course “Engineering Digital Twins” [ 5 ] where it has been used to teach students about how to use RV for monitoring in a practical setting 3 3 3 https://github.com/clagms/IncubatorDTCourse . 2 Preliminaries In the context of RV, we focus specifically on online monitoring , where the signal is observed incrementally as a stream of samples rather than as a complete trace available a priori . Additionally, batch processing is also supported, e.g., for post-hoc analysis of logged data. Signal Temporal Logic An STL formula \phi is defined recursively by the grammar: \phi::=\top\mid\mu(x)<c\mid\neg\phi\mid\phi\wedge\psi\mid\phi\mathop{\mathcal{U}_{[a,b]}}\psi , where \mu is an atomic predicate over the signal x , \top denotes Boolean truth, and \mathcal{U}_{[a,b]} is the time-bounded until operator, requiring \psi to hold at some time within [a,b] while \phi holds continuously beforehand. Standard derived operators include disjunction, implication, and the temporal operators eventually ( \Diamond ) and globally ( \Box ) 4 4 4 We restrict our attention to bounded temporal operators throughout this work, i.e., with finite intervals [a,b] . . The temporal depth H(\phi) [ 13 ] defines the maximum future horizon required to evaluate a formula, which dictates the worst-case buffering requirements for a monitor using delayed semantics. The expressiveness of STL allows for the compact specification of complex temporal properties, such as “within the next 100 minutes, whenever the temperature T exceeds 100 degrees, it must return below 90 degrees within 5 minutes” and can be expressed as: \Box_{[0,100]}\left((T>100)\rightarrow\Diamond_{[0,5]}(T<90)\right). Supported STL Semantics Existing tools often restrict users to a single evaluation strategy. mstlo , however, implements a unified interface for four distinct semantic definitions, allowing users to trade off between verdict expressiveness, verdict latency and performance: • Delayed Qualitative: The standard Boolean satisfaction (s,t)\models\phi [ 12 ] . This requires the signal to be fully resolved up to the temporal depth H(\phi) before a verdict is emitted. • Delayed Quantitative: The standard robustness semantics \rho(s_{t},\phi) [ 3 ] , which computes a real-valued score indicating the degree of satisfaction or violation. Similar to delayed qualitative semantics, this requires full signal availability up to H(\phi) . • Eager Qualitative: Inspired by [ 8 ] , this semantics leverages monotonicity in Boolean and temporal logic to emit early verdicts over partial traces via short-circuiting. For example, \Box_{[0,10]}\phi yields \bot (false) immediately upon the first violation of \phi , without waiting for the full interval to elapse. • RoSI: The RoSI semantics [\rho](\varphi,x_{[0,i]},t) [ 2 ] support quantitative reasoning over partial traces. Instead of a single robustness value \rho , the monitor computes an interval [\rho_{\text{min}},\rho_{\text{max}}] enclosing all possible future robustness values. A formula is definitively satisfied when \rho_{\text{min}}>0 and violated when \rho_{\text{max}}<0 . The interval is updated incrementally as new signal samples arrive and converges to \rho(s_{t},\phi) once the full horizon is observed. 3 Efficient Online Monitoring Algorithms A naive approach to STL monitoring involves re-evaluating the entire formula from scratch at every time step, a process that scales poorly with formula complexity and signal length. To address this, mstlo implements an incremental monitoring algorithm based on a bottom-up dynamic programming approach, enabling efficient reuse of intermediate results across timesteps. In our implementation, the specification is internally represented as an Abstract Syntax Tree (AST), in which each operator maintains its own cache of intermediate results from its child operators. While this provides a significant performance boost over the naive method, temporal operators can still require intensive searches over large caches to determine a verdict. To mitigate this for globally ( \Box ) and eventually ( \Diamond ) operators—which are essentially sliding window minimum and maximum computations—we incorporate a version of Lemire’s algorithm [ 10 ] . This optimization significantly reduces both the memory footprint of the caches and the computational time required to emit a verdict at each step. It is most effective for non-RoSI semantics; since RoSI intervals frequently overlap, particularly in nested formulas, the optimization applies less frequently and still requires a search over the entire cache, yielding comparatively modest gains. 4 The mstlo Tool mstlo is

Read the complete text