🤖 AI

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

This paper introduces Tessa, a novel approach that casts finite-horizon Markov chain model checking as dense tensor computations to leverage hardware accelerators and achieve massive speedups over existing methods, particularly in dense transition regimes.

Original authors: Jianlin Li, Nick Guo, Peter Ye, Yizhou Zhang

Published 2026-08-04

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jianlin Li, Nick Guo, Peter Ye, Yizhou Zhang

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 trying to predict the future of a chaotic system, like a massive game of "telephone" played by thousands of people, or a city where every traffic light changes based on the mood of the drivers. In the world of computer science, this is called probabilistic model checking. It's a way to mathematically prove how likely a system is to reach a specific goal (like "all professors finish their meeting") within a certain time, even when the system is full of randomness and chance. The problem is that as you add more people or parts to the system, the number of possible scenarios explodes. It's like trying to count every single grain of sand on a beach while the beach is also growing; the math gets so heavy that even the fastest supercomputers can get stuck, running out of memory or time before they can give you an answer.

For years, the best tools to solve this have been like trying to navigate a maze by looking at a detailed, hand-drawn map of every single dead end. These tools are great when the maze has lots of empty space (sparse dynamics), but they struggle when the maze is packed tight with paths (dense dynamics). They rely on old-school methods that don't play well with the super-fast, parallel processors found in modern graphics cards (GPUs), which are the engines behind today's video games and AI.

Enter a new approach called Tessa, developed by researchers at the University of Waterloo. Instead of trying to draw a map of every single possibility, Tessa decides to treat the entire system like a giant, multi-dimensional block of data, known in math as a tensor. Think of a tensor not as a boring spreadsheet, but as a hyper-cube of numbers that can be squished, stretched, and spun all at once. By translating the problem of "will the system reach the goal?" into a language that these modern graphics cards understand perfectly, Tessa can crunch the numbers for massive, complex systems in a fraction of the time it takes older tools.

The researchers didn't just guess this would work; they proved it mathematically to be sound and then built a tool to test it. When they ran Tessa against the current state-of-the-art tools on some tricky, crowded scenarios (like a model with 17 processors or 10 queues), Tessa was over 100 times faster. In one specific test involving a horizon of 500 steps, it was more than 300 times faster. The paper shows that by shifting how we represent the problem—from a sparse map to a dense, parallelizable block of data—we can unlock the ability to verify systems that were previously too big to check. It's not a magic wand that fixes everything (it works best on dense, crowded systems, not sparse ones), but it opens up a whole new playground for solving problems that were previously out of reach.

The Story of Tessa: Turning Chaos into a Dance

Let's dive deeper into how Tessa pulls off this magic trick. Imagine you are watching a group of N professors trying to finish a poll on their phones. Each professor is in one of three states: Away (ignoring the phone), Doodling (looking at the poll), or Done (finished). Every second, a professor might notice the email, get distracted, or finally hit submit. The catch? They can all get interrupted at any time.

To figure out the chance that everyone finishes within a certain time limit, traditional tools try to list every single combination of states. If you have 10 professors, that's $3^{10}$ (59,049) combinations. If you have 20, that's over 3 billion. Traditional tools try to store these combinations in a giant, sparse list (like a dictionary with mostly blank pages). This works okay for small groups, but when the group gets big and the interactions get messy (dense), the list becomes too huge to fit in memory, and the computer chokes.

Tessa's Insight: The Hyper-Cube
Tessa looks at this problem differently. Instead of a list, it sees the professors' states as a dense tensor—a multi-dimensional grid. If you have 10 professors, Tessa doesn't make a list of 59,049 items; it creates a 10-dimensional cube where each side has 3 slots. It's like a Rubik's cube, but with 10 layers instead of 3.

Why is this cool? Because modern graphics cards (GPUs) are built to handle these cubes. They are designed to perform the same math operation on millions of numbers simultaneously. Tessa translates the rules of the professors (the "if-then" logic of the Markov chain) into a set of instructions for this cube. Instead of walking through the maze step-by-step, Tessa tells the GPU to "squish" the whole cube at once.

The "Compiler" Magic
The paper highlights that Tessa uses a tool called JAX and a compiler called XLA. Think of JAX as a translator that turns the professor's rules into a language the GPU speaks fluently. XLA is the conductor that tells the GPU how to play the music most efficiently. It fuses many small steps into one big, smooth motion, so the GPU doesn't waste time stopping and starting. This is why Tessa is so fast; it stops fighting the hardware and starts dancing with it.

The Results: Speeding Up Time
The researchers tested Tessa on three famous "hard" problems from the literature:

Queues: Imagine 10 different lines of people waiting for service. Tessa was over 100 times faster than the next best tool.
Weather Factories: A model where factories switch between working and striking based on the weather. Again, Tessa was over 100 times faster.
Herman's Protocol: A classic problem about processors trying to agree on a leader. Here, Tessa was over 300 times faster than the competition when looking at 500 steps into the future.

The paper is very clear about the limits, too. Tessa isn't a silver bullet for every problem. If the system is very sparse (lots of empty space, few connections), the old tools might still be better because they use less memory. Tessa shines when the system is "dense"—when everything is connected to everything else, creating a massive web of possibilities.

Beyond Just Checking: Finding the Perfect Settings
There's one more cool thing Tessa can do. Because it turns the problem into a smooth, mathematical function (a tensor program), it can use gradient descent. This is the same math used to train AI to recognize cats or drive cars. It means Tessa can not only check if a system works, but it can also search for the perfect settings to make it work.

In the paper, they used this to solve a "Knuth-Yao die roller" problem. They wanted to find the perfect bias for two coins (values $p$ and $q$ ) to make a computer roll a fair die. Tessa treated the coin biases as knobs it could turn. It calculated how changing the knobs affected the result, and then automatically adjusted them to minimize the error. It found the perfect values ( $p=0.5$ and $q=0.5$ ) in just a few seconds, showing that Tessa can be used for optimization, not just verification.

The Bottom Line
The paper proves that by changing how we represent the problem—from a sparse list to a dense tensor—we can unlock the massive power of modern hardware. It's a shift from "counting every grain of sand" to "using a bulldozer to move the whole beach at once." While it doesn't solve the problem of state explosion (the number of states still grows exponentially), it pushes the boundary of what we can solve much further, making it possible to verify systems that were previously impossible to check. The authors are confident in their math (they proved it sound) and their results (they measured it on real benchmarks), offering a powerful new tool for the toolbox of computer scientists.

Technical Summary: Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains

Problem Statement

The paper addresses the verification of step-bounded reachability probabilities in Discrete-Time Markov Chains (DTMCs). The core challenge lies in the state explosion problem: as the number of system components (e.g., $N$ professors in the running example) increases, the global state space grows exponentially ( $3^N$ for $N$ components with 3 states each).

Existing state-of-the-art tools, such as PRISM and Storm, rely on explicit sparse matrices or symbolic Multi-Terminal Binary Decision Diagrams (MTBDDs). While effective for systems with sparse transition dynamics, these approaches struggle in the dense regime. Furthermore, their irregular memory access patterns hinder efficient mapping to modern hardware accelerators like GPUs. Recent probabilistic programming approaches (e.g., Dice, Rubicon) utilize Binary Decision Diagrams (BDDs) for inference, but BDD operations remain pointer-heavy and indirection-rich, making them ill-suited for GPU parallelization.

Methodology

The authors propose Tessa, a methodology that reframes probabilistic model checking as dense tensor computations. Instead of materializing the state-transition matrix as data (a sparse matrix or decision diagram), Tessa treats the joint distribution of state variables as an order- $N$ tensor and the transition dynamics as a tensor transformer (i.e., code).

Core Technical Components:

Core Language (PML): The authors define a high-level, modular specification language (PML) similar to PRISM's dtmc dialect. This allows systems to be described as interacting modules with state variables, guards, and probabilistic updates.
Tensor Semantics:
- State Distributions: Represented as dense tensors where dimensions correspond to state variables.
- Transition Dynamics: Modeled as tensor operations (transformers) rather than static matrices. The transition function is compiled into an array program that transforms the current-state tensor into the next-state tensor.
- Reachability: Step-bounded reachability is computed via the repeated application of this tensor transformer. The algorithm iteratively:
  1. Extracts the probability mass of goal states from the current tensor.
  2. Masks out the goal states.
  3. Applies the tensor transformer to the remaining mass to generate the next-step distribution.
Compilation and Acceleration:
- Tessa compiles DTMC models into JAX (a high-performance array programming language).
- The generated code is optimized by XLA (Accelerated Linear Algebra), a domain-specific compiler.
- XLA performs kernel fusion, merging multiple element-wise operations into single GPU kernels. This eliminates intermediate memory writes, reduces memory bandwidth pressure, and fully saturates the parallelism of GPUs.
Differentiability: Because the verification process is compiled into differentiable tensor programs, Tessa supports parameter synthesis. Users can compute gradients of reachability properties with respect to model parameters using automatic differentiation (JAX), enabling gradient-based optimization.

Key Contributions

The paper makes both theoretical and practical contributions:

Theoretical Soundness: The authors formally prove that the tensor interpretation of PML models is sound with respect to standard DTMC semantics. They establish a commutative diagram showing that applying the tensor transformer to a distribution tensor yields the same result as applying the standard transition function to the distribution.
Implementation (Tessa): A tool that automatically compiles high-level DTMC specifications into optimized tensor programs for GPU execution.
Empirical Evaluation: Extensive benchmarks on dense transition models (Queues, Weather Factories, Herman's protocol) demonstrate that Tessa achieves massive speedups over existing tools.

Experimental Results

The evaluation compares Tessa against Storm (Sparse), Storm (MTBDD), and Dice on a machine with an NVIDIA RTX 2080 Ti GPU.

Queues Benchmark: Tessa showed over 100× speedup over the next fastest method on the hardest solvable instance ( $K=10$ ).
Weather Factories: Tessa demonstrated over 100× speedup over Geni (a probabilistic programming baseline) and Storm (Sparse).
Herman's Protocol: Tessa achieved over 100× speedup over Storm (MTBDD) and over 300× speedup over Storm (Sparse) on the hardest instance ( $N=17$ ).
Scalability: While the asymptotic complexity remains exponential with respect to the number of variables (due to state space size), Tessa aggressively reduces the constant factor. It scales linearly with the horizon $H$ with a significantly smaller slope than CPU-based methods.
Parameter Synthesis: In a Knuth–Yao die roller experiment, Tessa successfully used gradient descent to find optimal coin biases ( $p, q$ ) within 100 steps, demonstrating its utility beyond simple verification.

Significance and Claims

The paper positions Tessa not as a replacement for existing tools but as a complementary addition to the probabilistic model checking toolbox.

Niche: It is specifically targeted at dense transition dynamics, a regime where traditional sparse matrix or BDD approaches are inefficient.
Hardware Alignment: The primary significance is the methodological shift from irregular, pointer-based data structures to dense, regular tensor operations. This unlocks the massive parallelism of modern hardware accelerators (GPUs) without requiring users to write custom GPU kernels.
Future Potential: The authors claim that by offloading optimization to mature compiler stacks (XLA), Tessa can benefit automatically from future hardware and compiler improvements. Additionally, the differentiable nature of the approach opens new avenues for optimizing model parameters directly.

The authors acknowledge limitations: Tessa is less space-efficient than sparse methods for sparse models and is constrained by GPU VRAM. However, for the class of dense models it targets, it significantly extends the boundary of tractable verification instances.