Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version)

Jianlin Li, Nick Guo, Peter Ye, Yizhou Zhang ( 🖂 ) ​ · 2026

Read Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version) by Jianlin Li, Nick Guo, Peter Ye, Yizhou Zhang ( 🖂 ) ​ (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-2608-00374.txt.

Introduction

Li and co-authors recast probabilistic model checking of Markov chains as tensor computation. The target is step-bounded reachability probability. Standard routes encode the transition matrix explicitly or symbolically. Those routes scale poorly when transition dynamics turn dense. Dense tensors are the alternative representation here.

Checking maps onto tensor operations that compilers can optimize for accelerators. They prove the mapping's soundness. Their tool, Tessa, implements the approach. On selected benchmarks from the literature, Tessa unlocks massive speedups over top methods. The gain comes from off-the-shelf compiler toolchains for tensor work. Dense-regime verification gets a new engine from this shift.

Catalog record

CREATORJianlin Li, Nick Guo, Peter Ye, Yizhou Zhang ( 🖂 ) ​
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version) Jianlin Li, Nick Guo, Peter Ye, Yizhou Zhang ( 🖂 ) ​ Abstract We reexamine the problem of verifying Markov chains with respect to step-bounded reachability probabilities. Prevailing approaches rely on encoding the state-transition matrix using either explicit or symbolic representations. While these approaches are effective for sparse transition dynamics, they scale less favorably in the dense regime. Our insight is to cast probabilistic model checking of Markov chains as computations over dense tensors. This methodology enables the use of off-the-shelf compiler toolchains for optimized execution of these tensor computations on hardware accelerators. We prove the soundness of the methodology of mapping probabilistic model checking to tensor computations. We implement our approach in a tool called Tessa . Empirical evaluation shows that Tessa unlocks massive speedups over state-of-the-art methods on selected benchmarks from the literature. stmry"4C stmry"4D 1 Introduction Probabilistic model checking is a formal verification technique for verifying quantitative properties of systems exhibiting stochastic behavior. Given a mathematical model (such as a Markov chain) representing the behavior of a system over time, an algorithmic procedure determines whether the system satisfies properties of interest (such as step-bounded reachability). As an example, consider the problem of scheduling an urgent faculty meeting ( fig. 1 ) involving N professors by collecting their availability via a Doodle poll. At any time step, each professor i is in one of three states: Away , Doodling , or Done . A professor Away from their inbox may, with probability p_{i} , notice the Doodle poll email and transition to Doodling to answer the Doodle poll. However, the Doodling state is fragile: with probability q_{i} , they successfully complete the poll and reach Done ; but with probability 1-q_{i} , they are interrupted by a new email or a knock on their door, forcing them back to be Away without hitting submit. The dynamics capture the intermittent nature of professors’ attention. Each Markov chain in fig. 1(a) depicts the behavior of a professor. The quantitative property to verify is the probability that all N professors have reached Done within a horizon of H time steps. The program in fig. 1(b) models this system of stochastic processes, similarly to how one would structure it in the PRISM [ 1 ] and JANI [ 10 ] modeling languages. Each module P_{i} models the behavior of professor i : it declares a state variable s_{i} with domain \{0,1,2\} (indicating Away , Doodling , and Done , respectively), and three commands that update s_{i} according to the transition probabilities p_{i} and q_{i} . Each command is guarded by a Boolean expression (e.g., s_{i}=0 for the first command); a command is enabled only if its guard is satisfied in the current state. The goal clause of the global model specifies the target property that all professors are in state Done . ​​ Away s_{1}=0 Doodling s_{1}=1 Done s_{1}=2 1-p_{1} p_{1} 1-q_{1} q_{1} 1 \parallel \cdots \parallel ​​ Away s_{N}=0 Doodling s_{N}=1 Done s_{N}=2 1-p_{N} p_{N} 1-q_{N} q_{N} 1 (a) N parallel Markov chains capturing the stochastic behavior of N professors. ⬇ module P_{1} var s_{1} : [0 .. 2] init 0; [ a ] ( s_{1}=0 ) \rightarrow p_{1} : ( s_{1}\coloneqq 1 ) + ( 1-p_{1} ) : ( s_{1}\coloneqq 0 ); [ a ] ( s_{1}=1 ) \rightarrow q_{1} : ( s_{1}\coloneqq 2 ) + ( 1-q_{1} ) : ( s_{1}\coloneqq 0 ); [ a ] ( s_{1}=2 ) \rightarrow 1.0 : ( s_{1}\coloneqq 2 ); module \cdots // modules P_{2} \cdots P_{N} goal s_{1}=2\wedge\cdots\wedge s_{N}=2 (b) A model of N professors (in PRISM-like syntax). 6 8 10 12 14 0 100 200 300 N 0 200 400 0 100 200 300 H Storm (MTBDD) Dice Storm (Sparse) Tessa time (s) (c) Scaling plots. Figure 1 : Running example: collecting availability from N professors. The target property is the probability that all N professors reach Done within horizon H . Despite the semantic simplicity of this model, the verification problem is inherently computationally expensive due to state explosion. Since each process has 3 states, the global state-space size is 3^{N} . It is unlikely that any model checking tool on a classical computer can avoid this exponential blowup. Nevertheless, we would like to push the boundary of tractable instances as far as possible, especially given the raw speed of modern hardware accelerators at our disposal. State-of-the-art methods largely fall into two categories: • Probabilistic model checkers, such as PRISM [ 29 ] and Storm [ 16 ] , are the prevailing tools for such verification tasks. They represent the state-transition dynamics using either explicit (i.e., sparse matrices of size 3^{N}\,{\times}\,3^{N} in the N -professor model) or symbolic (i.e., multi-terminal binary decision diagrams, or MTBDDs) representations. Both representations are highly optimized for CPU execution in the situation of sparse transition dynamics. However, they are not as effective in the dense regime, and their irregular memory access patterns make it challenging to map them efficiently to modern hardware accelerators. • A recent development is the use of probabilistic inference for probabilistic model checking. Rubicon [ 19 ] compiles a DTMC into the Dice [ 18 ] probabilistic programming language; running the Dice program using Dice’s inference engine—weighted model counting on binary decision diagrams (BDDs)—computes the step-bounded reachability probability. Still, BDD operations are pointer-rich, so they involve indirection that does not map well to devices like GPUs. We present Tessa , a new methodology for verifying step-bounded reachability properties of DTMCs, by compiling DTMC models to dense tensor computations (i.e., array programs in an array programming language like JAX [ 9 ] ). As fig. 1(c) shows, Tessa exhibits markedly better scalability than existing tools on the N -professor model. The two plots show running times for different values of N (fixing the horizon H\,{=}\,10 ) and different values of H (fixing N\,{=}\,12 ), respectively. The first plot shows that, while Tessa does not change the asymptotic complexity of the problem (the state-space size still grows exponentially with N ), it aggressively pushes down the constant factor of the exponential growth compared to Storm and Dice . The second plot shows that while all tools appear to scale linearly with H , Tessa has a significantly smaller slope---the curve is nearly flat. 1 1 1 The comparison may make state-of-the-art tools look inefficient, but they are actually highly optimized for CPUs. The point is that a methodological shift unlocks massive speedups. A key reason for Tessa ’s scalability is its representation of state distributions as dense tensors, and state-transition dynamics as transformations on these tensors. The name Tessa evokes a tesseract—a high-dimensional cube—reflecting our insight: rather than eagerly materializing the state-transition dynamics as a sparse matrix or a decision diagram, we treat the joint distribution of N state variables as an order- N tensor, and the transition dynamics as a tensor program. A key advantage of this tensor representation is its amenability to optimization (by modern tensor compilers) and acceleration (by hardware such as GPUs). Because Tessa maps the verification problem to tensor operations, we can use an off-the-shelf tensor compiler (XLA [ 2 ] , in this case) to optimize the

Read the complete text