Traditional formal verification operates under a strict Boolean paradigm: a system either satisfies a specification or it does not. In this classical view, a system that misses a critical deadline by a millisecond is lumped into the same "incorrect" category as a system that crashes entirely. Conversely, two systems that both satisfy a safety property are treated as equally correct, ignoring the fact that one might consume twice as much energy or exhibit significantly higher latency than the other.
As modern engineering shifts toward resource-constrained, stochastic, and cyber-physical systems, this all-or-nothing framing becomes a bottleneck. Engineers do not just need to know if a system works; they need to know how well it performs, how much energy it consumes, and what the probability of failure is under realistic environmental noise. To address this, a major research direction has emerged to transition formal verification from qualitative binary logic to quantitative, real-valued assessments.
From Languages to Weights: Automata for Quantitative Metrics
In classical verification, properties are represented as formal languages (sets of acceptable execution traces), and verification reduces to checking whether the system's behaviors form a subset of that language. To capture quantitative metrics like energy consumption or latency, this subset relation must be replaced by algebraic operations over real numbers.
Instead of simply accepting or rejecting a trace, a quantitative automaton assigns a numerical weight to each transition. The total value of an execution trace is then computed by aggregating these weights over time—such as calculating the sum, the average, or the maximum value encountered.
Classical (Boolean) Automaton:
[State A] --(action)--> [State B] ==> Verdict: True / False
Weighted Automaton:
[State A] --(action, cost: 5)--> [State B] ==> Verdict: Total Accumulated Cost
However, standard weighted automata are often insufficient for complex, nested performance metrics, such as evaluating the average response time within a window that itself varies dynamically. To overcome this limitation, Krishnendu Chatterjee et al. introduced Nested Weighted Automata. By nesting weighted automata inside one another, the authors created a framework capable of expressing complex quantitative properties while mapping out the "decidability frontier"—the mathematical boundary where these expressive power gains remain computationally solvable.
When verifying or comparing two quantitative systems, the core challenge is determining dominance: is the aggregate weight (e.g., latency) of every run in the implementation consistently less than or equal to the corresponding run in the specification? Suguman Bansal et al. addressed this by introducing Comparator Automata in Comparator Automata in Quantitative Verification. A comparator automaton reads the weights of two systems side-by-side and structurally determines dominance, effectively transforming a difficult quantitative comparison problem back into a classical language emptiness problem. Similarly, Rajeev Alur et al. advanced this space in Better Complexity Bounds for Cost Register Automata by refining the complexity bounds for Cost Register Automata, which utilize dedicated registers to compute precise numerical costs over data streams.
Generalizing Logic and Property Decomposition
Moving beyond binary outcomes requires rethinking the underlying specification logics. Instead of evaluating properties using classical temporal logics like CTL, researchers utilize probabilistic and metric-based variants. Early foundations were laid by Michael Huth et al. in Comparing CTL and PCTL on labeled Markov chains, which bridged the gap between qualitative logic and expectation-based evidence in probabilistic systems. For highly complex, branching behaviors, Junnan Xu et al. established a foundational logical framework in An axiom system of probabilistic Mu-calculus, providing a formal axiom system for reasoning about quantitative probability thresholds.
This shift also forces a re-examination of the bedrock principles of formal methods. In Boolean verification, a landmark theorem states that every linear property can be decomposed into a safety part ("nothing bad happens") and a liveness part ("something good eventually happens"). In Quantitative Safety and Liveness, Thomas A. Henzinger et al. proved that this classic decomposition generalizes to quantitative properties. By assigning continuous values (like distance or cost) to execution traces, the authors demonstrated that any quantitative property can be mathematically separated into quantitative safety and liveness components.
Furthermore, traditional quantitative verification typically measures single execution traces in isolation. To evaluate system-wide behaviors that depend on sets of traces—such as observational determinism or average performance across all possible executions—Thomas A. Henzinger et al. proposed Quantitative Language Automata, extending quantitative analysis to complex hyperproperties.
Managing Uncertainty in Stochastic Environments
Real-world systems rarely operate in a deterministic vacuum. As Marta Kwiatkowska highlights in Advances and challenges of quantitative verification and synthesis for cyber-physical systems, physical systems must routinely navigate sensor noise, network packet drops, and hardware degradation. Under these conditions, absolute binary guarantees are impossible; systems must be evaluated based on failure probabilities and operational costs.
Historically, verifying these systems relied on "almost-sure" verification—proving that a property holds with a probability of exactly one. However, an autonomous vehicle or medical device might operate acceptably if its failure probability is bounded below a microscopic threshold, even if it isn't zero.
To bridge this gap, Alessandro Abate et al. developed a certificate-based methodology in Stochastic Omega-Regular Verification and Control with Supermartingales and Quantitative Supermartingale Certificates. Supermartingales act as stochastic extensions of Lyapunov functions, proving that a system's state tends to move toward a safe target in expectation. The authors demonstrated how to upgrade these traditional "almost-sure" proof certificates into quantitative ones, providing strict mathematical upper and lower probability bounds for infinite-state systems against complex Linear Temporal Logic (LTL) specifications.
Almost-Sure Verification:
Proves Probability(Success) == 1.0
Quantitative Verification:
Proves Lower Bound <= Probability(Success) <= Upper Bound
(Allows for acceptable failure margins)
In the context of strategic synthesis, Tamajit Banerjee et al. designed a direct symbolic algorithm in A Direct Symbolic Algorithm for Solving Stochastic Rabin Games to synthesize controllers that satisfy arbitrary probability thresholds rather than just absolute certainty. When combining these random transitions with numerical costs, Krishnendu Chatterjee et al. mapped the trade-offs of Probabilistic Weighted Automata, proving that while combining probabilities and weights increases expressive power, it frequently pushes certain verification problems into undecidability.
Making Quantitative Verification Practical
Computing exact real-valued metrics over infinite state spaces is computationally expensive and frequently undecidable. To make these concepts practical for software engineering, researchers rely on three core strategies: bound functions, statistical estimation, and approximate monitoring.
1. Bounding the Infinite State Space
Infinite-state quantitative problems are often intractable because resource metrics can grow infinitely. Arindam Chakrabarti et al. resolved this in Verifying Quantitative Properties Using Bound Functions by introducing "bound functions"—designer-specified thresholds that signal when a value has effectively reached infinity. This bounds the state space, transforming undecidable problems into decidable ones with highly efficient algorithms.
2. Statistical Model Checking (SMC)
When exhaustive mathematical proofs fail due to state-space explosion, simulation offers an alternative. In Time for Statistical Model Checking of Real-Time Systems, Alexandre David et al. implemented statistical model checking for real-time systems. By shifting from exhaustive verification to simulation-based statistical estimation, SMC allows engineers to determine the probability of a resource failure within a specific confidence interval, bypassing traditional decidability limits. To evaluate these continuous-time stochastic processes precisely, Tomás Brázdil et al. demonstrated in Measuring Performance of Continuous-Time Stochastic Processes using Timed Automata how Deterministic Timed Automata can be deployed as "observers" to approximate performance metrics with arbitrary precision.
3. Approximate Runtime Monitoring
If a system must be monitored at runtime, tracking exact quantitative values can exhaust system memory. Thomas A. Henzinger et al. proved in Quantitative and Approximate Monitoring that if we tolerate a small margin of error, monitors can track continuous numerical estimations using strictly finite memory. Crucially, they established a direct hardware-precision trade-off: allocating more registers to the monitor directly increases the precision of the quantitative estimate.
Compositionality and Optimization
To scale quantitative verification to complex software architectures, the analysis must be modular. Engineers need to verify individual components independently and derive guarantees about the combined system.
Krishnendu Chatterjee et al. established a framework for this in Compositional Quantitative Reasoning, replacing binary logic with real-valued costs to compute quantitative bounds on how well an assembly of components satisfies a global specification. To handle non-determinism alongside these metrics, Uli Fahrenberg et al. introduced structured quantitative labels to modal transition systems in Compositionality for quantitative specifications.
This compositional mindset is particularly vital in multi-agent environments where agents must cooperate under unpredictable conditions. Rafael Dewes et al. proposed "Good-Enough Decomposition Contracts" (GEDC) in Contract-based Design and Verification of Multi-Agent Systems with Quantitative Temporal Requirements. Instead of demanding flawless execution, these contracts break down global quantitative goals into local agent tasks, allowing the system to be mathematically evaluated on how well it performs even when perfect satisfaction is unattainable.
Global Quantitative Goal (e.g., Total Latency <= 10ms)
│
├──> Agent 1 Contract: Local Latency Budget (Good-Enough)
└──> Agent 2 Contract: Local Latency Budget (Good-Enough)
Beyond verifying existing designs, quantitative frameworks enable optimal system synthesis. When multiple implementations satisfy a basic Boolean requirement, quantitative objectives allow a compiler to select the most efficient one. In Better Quality in Synthesis through Quantitative Objectives, Krishnendu Chatterjee developed algorithms to solve games with lexicographic mean-payoff conditions, automatically constructing implementations that are not just correct, but mathematically optimal. Similarly, Krishnendu Chatterjee et al. provided polynomial-time algorithms in Measuring and Synthesizing Systems in Probabilistic Environments to maximize expected environmental rewards while satisfying core $\omega$-regular safety properties.
Mitigating All-or-Nothing Tool Failures
This philosophy of avoiding binary outcomes also applies to the verification tools themselves. Traditional software verifiers often operate in an all-or-nothing manner: they either return a complete proof or fail entirely due to resource exhaustion (like a timeout), discarding all intermediate computational effort.
Dirk Beyer et al. introduced Conditional Model Checking in Conditional model checking: a technique to pass information between verifiers to eliminate this limitation. When a conditional model checker encounters a resource limit, it does not simply fail; instead, it outputs a precise description of the state space it did successfully verify. This conditional output allows subsequent verification tools to import this data and focus exclusively on the remaining, unproven parts of the program.
Conclusion
By replacing the rigid "true or false" of classical formal methods with real-valued metrics, distances, and probabilities, quantitative formal verification provides a framework suited to modern engineering. Whether through tracking energy costs via Cost Register Automata, bounding stochastic risks with Supermartingale Certificates, or decomposing global goals via Good-Enough Contracts, this paradigm allows developers to measure exactly how well a system operates within the messy, continuous, and uncertain real world.
Key Foundational Work
Verifying Quantitative Properties Using Bound Functions (2005) — contributed 1 concept elements to this direction.
Comparing CTL and PCTL on labeled Markov chains (1998) — contributed 1 concept elements to this direction.