aiqbench analysis
This research advances the verification of Markov chains by mapping probabilistic model checking onto dense tensor computations, enabling efficient execution on hardware accelerators like GPUs and TPUs. By leveraging off-the-shelf compiler toolchains for these optimized calculations, the proposed Tessa framework achieves significant speedups over traditional methods in dense regimes. This work bridges formal logic with high-performance computing infrastructure to solve complex reachability problems more effectively than prior symbolic or explicit matrix approaches.
Tensor Probabilistic Model Checking of Finite-Horizon Markov Chains (Extended Version)
arXiv:2608.00374v1 Announce Type: cross 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-theart methods on selected benchmarks from the literature.
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-theart methods on selected benchmarks from the literature.
Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI); Mathematical Software (cs.MS); Programming Languages (cs.PL)
arXiv:2608.00374 [cs.LO]
(or arXiv:2608.00374v1 [cs.LO] for this version)
https://doi.org/10.48550/arXiv.2608.00374 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
https://doi.org/10.1007/978-3-032-32537-2_24 Focus to learn more DOI(s) linking to related resources
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 237 words
Related coverage
Spectral partitioning for $k$-block averaging kernels of finite Markov chains
arXiv · Aug 25, 2026
Your Probabilistic JEPA Is Secretly a Hidden Markov Model: A State-Space Interpretation of Joint-Embedding Predictive Learning
arXiv · Aug 17, 2026
News
Quantum Computing Report · Jul 25, 2026
[AINews] Reality Checks on AI News (Yegge shuts down Gas Town, Databricks’ +60% Astra cost)
Latent Space · Sep 17, 2026