Analyzing Value Functions of States in Parametric Markov Chains

Kasper Engelen, Guillermo A. Pérez, Shrisha Rao

TL;DR

This paper tackles the high computational complexity of verifying Parametric Markov Chains (pMCs) by establishing a new theoretical link between parameter monotonicity and the "never-worse relation" (NWR). By leveraging this connection, the authors introduce a fast, graph-based state-space reduction algorithm that collapses equivalent states, significantly speeding up downstream verification tasks like monotonicity checking and parameter lifting.

What Problem Does This Paper Address?

Markov chains are widely used to analyze probabilistic systems, but in practice, exact transition probabilities are often unknown or variable. Parametric Markov Chains (pMCs) solve this by replacing concrete probabilities with formulas over parameters. However, verifying reachability properties in pMCs is notoriously difficult—specifically, it is $\text{coETR}$-complete (Existential Theory of the Reals).

To bypass this complexity, researchers look at structural properties like monotonicity (does increasing a parameter always increase the target reachability probability?) and the never-worse relation (NWR; is state A always at least as good as state B at reaching the target?).

Figure 1: Examples of pMCs with parameters p and r.

Prior work showed that NWR reduces to monotonicity, but the reverse relationship and efficient state-reduction techniques remained incomplete. This paper bridges that gap.

Methods

The authors make two main contributions to the theory and practice of pMCs:

  1. Theoretical Reduction via Derivatives: They prove that checking monotonicity can be reduced back to the NWR problem. To achieve this, they construct a "partial-derivative pMC" whose reachability values correspond to the derivatives of the original pMC's value functions. This relies on classical circuit complexity results to transform arithmetic circuits into algebraic branching programs (ABPs), and then into an acyclic pMC in quasi-polynomial time.
  2. State-Space Reduction Algorithm: Building on the NWR connection, they present an efficient $O(n^2)$ algorithm to find and collapse same-value equivalence classes (where states have identical reachability value functions across all parameter valuations). This acts as a fast preprocessing step before running heavy model-checking algorithms.

Datasets

The authors evaluated their approach using several benchmarks:

  • Standard Benchmarks: BRP (Bounded Retransmission Protocol) and Crowds from existing monotonicity studies, as well as the NRP (Network Routing Protocol) benchmark for parameter lifting.
  • Custom Benchmarks: Four scalable variants (Variants A, B, C, and D) specifically designed to test the limits of the equivalence-class collapse algorithm, featuring up to 1 million states and varying monotonicity behaviors.
  • Excluded Benchmarks: The Gambler, Zeroconf, Message Authentication, and Herman benchmarks were evaluated but excluded from full analysis because they yielded no state-space reductions.

Key Insights and Ideas

  • The Monotonicity-NWR Duality: Unifying these two problems under the same complexity umbrella shows that analyzing the derivative of a value function behaves structurally like comparing two different states within a modified Markov chain.
  • Circuits to the Rescue: Even though the standard sum-of-products representation of a pMC's value function can blow up exponentially, its arithmetic circuit representation remains small. This insight allows the authors to compute derivatives efficiently using circuit transformations.
  • Trivial Parameters, Non-Trivial Gains: Even if you simplify a complex pMC to a "trivially parameterized" version (treating every transition label as a unique variable) to find equivalence classes, any state collapse found in the simplified model remains perfectly valid for the original complex model.

Key Results

  • Massive State Reduction: On the custom benchmarks, the algorithm collapsed models from nearly 100,000 states down to just ~300 states. For massive models (up to 1 million states), the collapse completed successfully in a reasonable timeframe (~50 minutes).
  • Verification Speedups: Preprocessing with the NWR collapse turned "Timeout" (TO) results into sub-second executions for monotonicity checks and parameter lifting on several custom benchmarks.
  • Standard Benchmark Impact: For the BRP benchmark, the state space was cut by more than half (e.g., 1,818 states down to 702), though it didn't significantly alter the already-fast downstream analysis times. For Crowds, it reduced states from 6,905 to 3,782.

Limitations and Future Work

  • Quasi-Polynomial vs. Polynomial: The derivative pMC construction is currently quasi-polynomial time. The authors leave open the question of whether a strictly polynomial-sized derivative pMC can always be constructed.
  • Benchmark Sensitivity: The preprocessing step provides massive speedups when it successfully reduces the state space drastically, but for some existing benchmarks, the reduction is modest and doesn't translate to faster Storm model-checking times.
  • Cycles in Weighted Automata: Adapting the translation to handle cyclic structures in alternative representations (like parametric weighted automata) remains an open challenge due to the complications introduced by feedback loops.

Summary updated

Abstract

Parametric Markov chains (pMC) are used to model probabilistic systems with unknown or partially known probabilities. Although (universal) pMC verification for reachability properties is known to be coETR-complete, there have been efforts to approach it using potentially easier-to-check properties such as asking whether the pMC is monotonic in certain parameters. In this paper, we first reduce monotonicity to asking whether the reachability probability from a given state is never less than that of another given state. Recent results for the latter property imply an efficient algorithm to collapse same-value equivalence classes, which in turn preserves verification results and monotonicity. We implement our algorithm to collapse "trivial" equivalence classes in the pMC and show empirical evidence for the following: First, the collapse gives reductions in size for some existing benchmarks and significant reductions on some custom benchmarks; Second, the collapse speeds up existing algorithms to check monotonicity and parameter lifting, and hence can be used as a fast pre-processing step in practice.
BibTeX
@misc{engelen2024analyzing,
  author = {Kasper Engelen and Guillermo A. Pérez and Shrisha Rao},
  title = {{Analyzing Value Functions of States in Parametric Markov Chains}},
  year = {2024},
  eprint = {2504.17020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.17020},
}
Figure