💻 computer science

Monitoring Data-aware Temporal Properties (Extended Version)

This paper presents a novel, formally verified framework for anticipatory monitoring of linear-time properties enriched with SMT theories (LTLfMT) by combining automata-theoretic methods with automated reasoning, thereby identifying decidable fragments relevant to data-aware systems and demonstrating feasibility through a prototype implementation.

Original authors: Alessandro Gianola, Marco Montali, Sarah Winkler

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro Gianola, Marco Montali, Sarah Winkler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a complex, black-box machine (like a sophisticated AI agent) perform a task. You can't see inside the machine to check its blueprints or code, but you can watch the stream of actions it takes. Your job is to act as a watchdog to ensure the machine is following the rules.

This paper introduces a new, super-smart kind of watchdog for AI systems that deal with data (like numbers, lists, or database records) over time.

Here is the breakdown of their work using simple analogies:

1. The Problem: The "Crystal Ball" Challenge

Most traditional watchdogs are like security cameras that only look at what has already happened. If a machine breaks a rule, the camera sees it and sounds the alarm.

However, the authors argue that in complex AI systems, you need a Crystal Ball. You need to know not just if the machine has broken a rule, but if it is doomed to break a rule no matter what it does next.

The Analogy: Imagine a hiker walking on a cliff edge.
- Old Watchdog: "You haven't fallen yet, so you are safe." (It only checks the past).
- New "Anticipatory" Watchdog: "Even though you haven't fallen yet, the path ahead is a dead end. No matter which way you turn, you will fall. I am declaring you 'permanently violated' right now, before you actually step off."

This is called Anticipatory Monitoring. It looks at the history and all possible futures to give a verdict immediately.

2. The Complexity: Data + Time

The machine isn't just moving; it's making decisions based on data.

The Example: Think of a concert ticket bot. It sees a new ticket offer every second. It has to decide: "Should I keep my current bookmarked ticket, or switch to this new one?"
The Rule: "Always pick the cheapest ticket for the specific concert I want."
The Challenge: The bot has to compare prices (math) and check concert names (data) at every step. If the bot picks a ticket that costs $100, but a $50 ticket for the same concert appears later, the bot must switch. If it doesn't, it's broken.

The authors created a language (a set of rules) to describe these complex, data-heavy rules. They call it LTLMTf.

3. The Solution: The "Backward Map"

The authors faced a huge problem: Predicting the future for a machine with infinite possibilities is usually impossible (mathematically "undecidable"). It's like trying to predict every possible move in a game of chess that never ends.

To solve this, they built a Backward Map (a technical tool called a Coreachability Graph).

The Analogy: Instead of trying to guess every path the hiker might take forward, imagine you start at the finish line (the goal) and work your way backward.
1. You mark the spots where the hiker successfully finishes the hike.
2. You ask: "What conditions must be true right now to reach those good spots?"
3. You keep walking backward, creating a map of "Safe Zones" and "Danger Zones."

By building this map backward, they can look at the hiker's current position and instantly know: "Is there any path forward that leads to success?"

If Yes: The system is currently safe, but might fail later (Current Satisfaction).
If No: The system is currently safe, but will fail no matter what (Permanent Satisfaction - wait, actually this means it's permanently safe? No, let's correct the analogy based on the paper's logic).

Correction on the Verdicts:
The paper defines four states for the watchdog:

Current Satisfaction (CS): You are good now, but you might mess up later.
Permanent Satisfaction (PS): You are good now, and you are guaranteed to stay good no matter what happens next.
Current Violation (CV): You messed up, but you might fix it later.
Permanent Violation (PV): You messed up, and there is no way to fix it. The game is over.

The "Anticipatory" part is the ability to spot PV (Permanent Violation) immediately, rather than waiting for the system to crash.

4. The Magic Trick: "Model Completion"

How did they make this backward map possible without getting lost in infinite math? They used a mathematical trick called Model Completion.

The Analogy: Imagine you are trying to solve a maze, but the maze keeps growing new walls.
- The authors found a way to "smooth out" the maze. They proved that for certain types of rules (specifically those involving databases and arithmetic like addition/subtraction), you can treat the growing maze as if it were a fixed, manageable size.
- They identified specific "safe zones" of rules (like DB-LTLf-MC) where the math behaves nicely. In these zones, the "Backward Map" is guaranteed to be finite and solvable.

5. The Result: A Working Prototype

They didn't just write theory; they built a prototype tool called MONTHE.

They tested it on the concert ticket example.
The tool successfully watched the "ticket bot" and could instantly say: "Hey, that bot picked a $100 ticket, but the concert is $50. It is Permanently Violated right now because it will never find the $50 ticket if it keeps ignoring the data."

Summary

This paper is about building a super-vigilant security guard for AI systems.

Old Guard: "You haven't broken the rule yet."
New Guard: "I see the future. You are currently breaking the rule, and there is no way for you to fix it. I am flagging you as 'Permanently Violated' immediately."

They achieved this by combining time-travel logic (looking at the past and future) with database math, but only for specific types of rules where the math doesn't get too crazy to solve. They proved it works and built a tool to do it.

Technical Summary: Monitoring Data-aware Temporal Properties

Problem Definition

The paper addresses the challenge of anticipatory runtime verification for complex, dynamic AI systems where internal specifications are inaccessible (black-box systems). Traditional design-time verification methods like model checking are often inapplicable in these scenarios. While Runtime Verification (RV) offers a solution by monitoring execution traces, existing approaches face two primary limitations:

Propositional Nature: Standard Linear-Time Temporal Logic over finite traces ( $LTL_f$ ) cannot express properties involving structured data (e.g., arithmetic, sets, uninterpreted functions), which are ubiquitous in modern AI agents and business processes.
Lack of Anticipation: Most monitors only evaluate the trace prefix seen so far. They fail to detect violations that are inevitable regardless of how the trace continues (e.g., if a system has already committed to a state that makes a future goal impossible).

The authors focus on $LTLMT_f$ (Linear-Time Temporal Logic over finite traces modulo theories), which enriches $LTL_f$ with arbitrary SMT theories. The specific problem is anticipatory monitoring: determining the monitoring state of a property $\psi$ after a trace $\tau$ by considering $\tau$ and all its possible finite continuations. The monitoring states are defined as:

Current Satisfaction (CS): $\tau$ satisfies $\psi$ , but a violation is possible in some extension.
Permanent Satisfaction (PS): $\tau$ satisfies $\psi$ , and no extension can violate it.
Current Violation (CV): $\tau$ violates $\psi$ , but satisfaction is possible in some extension.
Permanent Violation (PV): $\tau$ violates $\psi$ , and no extension can satisfy it.

The general monitoring problem for $LTLMT_f$ is undecidable, particularly when involving linear arithmetic over reals. The paper aims to identify decidable, practically relevant fragments of this logic.

Methodology

The proposed framework combines automata-theoretic methods for temporal reasoning with automated reasoning (SMT) techniques for the data dimension.

1. Logic and Semantics

The authors define $LTLMT_f$ over a multi-sorted signature $\Sigma$ containing data variables, functions, and predicates. A key semantic choice is the treatment of the underlying model $M$ :

Conservative Extension: The model underlying a trace is not fixed; rather, a continuation of the trace provides an extension of the model (via embeddings). Facts about previously seen elements remain fixed, but new elements and facts can be introduced. This aligns with scenarios like ticketing systems where past prices are fixed, but new tickets appear.
Lookback Operator: The logic uses a "lookback" operator ( $\triangleleft$ ) to refer to the previous value of a variable, rather than a lookahead operator.

2. Automata Construction

For a given quantifier-free $LTLMT_f$ property (referred to as dataLTLf), the authors construct a Non-deterministic Finite Automaton (NFA), $N_\psi$ .

The alphabet $\Theta$ consists of sets of first-order (FO) formulas (and their negations) found in the property.
The NFA tracks the temporal evolution of the property, accepting words that correspond to traces satisfying the property.
A "safe lookback" restriction is imposed to ensure that lookback variables do not constrain the initial state of the trace.

3. Coreachability Graphs and Regression

To handle the data dimension and determine anticipatory states, the authors introduce a coreachability graph ( $CG^+$ ) and a dual non-coreachability graph ( $CG^-$ ).

Regression: The core mechanism is the regress operation, which propagates verification obligations backward through the NFA transitions. Given a state formula $\phi$ and a transition constraint $C$ , regress( $\phi$ , $C$ ) computes the condition on the previous state required to satisfy $\phi$ after applying $C$ .
Model Completion: To ensure the regression results in quantifier-free formulas (essential for decidability), the framework relies on the theory $T$ having a model completion $T^*$ . This allows the elimination of existential quantifiers introduced during regression, converting them into equivalent quantifier-free formulas in $T^*$ .
Graph Construction: Nodes in the graph are pairs $(q, \phi)$ , where $q$ is an NFA state and $\phi$ is a quantifier-free formula representing the condition required to reach a final (or non-final) state from $q$ .

4. Monitoring Algorithm

The MONITOR procedure operates as follows:

Compute the NFA $N_\psi$ and the coreachability graphs $CG^+$ and $CG^-$ .
Simulate the trace $\tau$ on $N_\psi$ to identify the current state $q$ .
Evaluate the last assignment $\alpha_n$ $α_{n}$ against the formulas associated with state $q$ $q$ :
- If $q$ is accepting: Check if $EXTVIOL(q)$ (the condition for a future violation) is satisfied. If yes $\to$ CS; else $\to$ PS.
- If $q$ is non-accepting: Check if $EXTSAT(q)$ (the condition for a future satisfaction) is satisfied. If yes $\to$ CV; else $\to$ PV.

Key Contributions

Formalization of Anticipatory Monitoring for $LTLMT_f$ : This is the first work to formally define and tackle the anticipatory monitoring problem for linear-time properties enriched with SMT theories over finite traces.
Novel Framework: The authors present a foundational framework combining NFA-based temporal reasoning with SMT-based data reasoning. A key technical novelty is the use of model completion to handle quantifier elimination during the backward regression of verification obligations, enabling the construction of finite coreachability graphs.
Identification of Decidable Fragments: The paper identifies specific, practically relevant fragments of $LTLMT_f$ $L T L M T_{f}$ where the monitoring problem is solvable (guaranteed termination):
- DB-LTLf: Properties combining database references (modeled via Equality and Uninterpreted Functions - EUF) with arithmetic, under specific structural constraints.
- Acyclic Signatures: Ensures a finite number of terms.
- Monotonicity Constraints (MCs): Restricts arithmetic to simple comparisons ( $=, \neq, \leq, <$ ) between terms, common in business process monitoring.
- Local Finiteness: A broader condition ensuring a finite number of non-equivalent formulas.
- Bounded Lookback: A syntactic restriction on the interaction of constraints in the property, generalizing "feedback freedom."
Prototype Implementation: The feasibility of the approach is demonstrated through MONTHE, a prototype tool implemented in Python that utilizes the CVC5 SMT solver for data reasoning and quantifier elimination.

Results and Evaluation

Theoretical Results: The paper provides formal proofs for the correctness of the monitoring algorithm (Theorem 18) and establishes decidability for the identified fragments (Theorems 19–24).
Practical Application: The framework is shown to cover data-aware business processes and dynamic systems operating over read-only databases (e.g., the ticketing example where an agent selects the cheapest ticket).
Preliminary Evaluation: The authors report preliminary experiments using the MONTHE tool. The tool successfully processes properties and traces, outputting the correct monitoring state. The evaluation is described as preliminary, with extensive empirical evaluation left for future work.

Significance and Claims

The paper claims to be the first to address anticipatory monitoring for data-aware temporal properties. Its significance lies in bridging the gap between the expressive power required for modern AI systems (structured data, arithmetic) and the need for rigorous, real-time safety guarantees.

The authors emphasize that while general anticipatory monitoring is undecidable, their identification of DB-LTLf (combining arithmetic with database references) provides a "sweet spot" of expressiveness and decidability. This is particularly relevant for:

Data-aware Business Processes: Where transitions depend on database values and arithmetic constraints.
Dynamic Systems: Where agents interact with read-only databases (e.g., ticket markets, inventory systems).

The work is modest in its claims regarding immediate industrial deployment, noting that the current implementation is a prototype and that future work will explore dynamic systems where the data component changes over time (e.g., updating ticket prices), which requires handling controlled updates to the database.