💻 computer science

UMB: A Unified Markov Binary Format for Probabilistic Model Checking (extended version)

This paper introduces the Unified Markov Binary (UMB) format, an efficient and extensible binary file standard designed to overcome interoperability barriers in probabilistic model checking by providing a unified, low-level representation of probabilistic systems that is already adopted by prominent tools and supported by a comprehensive Python library.

Original authors: Roman Andriushchenko, Arnd Hartmanns, Joshua Jeppson, Sebastian Junges, Tobias Meggendorfer, David Parker, Tim Quatmann, Maximilian Weininger

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Roman Andriushchenko, Arnd Hartmanns, Joshua Jeppson, Sebastian Junges, Tobias Meggendorfer, David Parker, Tim Quatmann, Maximilian Weininger

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 build a massive, complex machine (like a self-driving car or a weather prediction system) using different teams of engineers. Each team speaks a slightly different language and uses their own unique set of blueprints.

Team A writes their plans in a long, detailed letter (text-based code).
Team B draws their plans on a whiteboard using a specific shorthand.
Team C uses a digital 3D model.

The problem is that when Team A wants to send their work to Team B, they have to rewrite the entire letter into Team B's shorthand. This takes forever, creates huge piles of paper, and often leads to mistakes. In the world of computer science, this is exactly what happens with Probabilistic Model Checking. These are tools used to mathematically prove that systems (like software or networks) will behave safely and correctly. Currently, these tools struggle to talk to each other because they don't share a common "low-level" file format.

This paper introduces UMB (Unified Markov Binary Format), a new solution to this communication breakdown.

The Core Idea: The "Universal Translator" Box

Think of UMB not as a language, but as a standardized shipping container.

Before UMB, if you wanted to move a model from one tool to another, you had to unpack the entire machine, rebuild it from scratch in the new tool's language, and then pack it up again. It was slow, messy, and inefficient.

UMB is a binary file format (a compact, computer-readable code) that acts as a universal container. It allows different tools to drop a model into the container, ship it instantly to another tool, and have that tool open it up and use it immediately without any rebuilding.

How It Works: The "Layer Cake" of Decisions

The paper explains that UMB is built on a clever mathematical idea called an Annotated Transition System. To understand this, imagine a choose-your-own-adventure book:

States (The Pages): These are the different situations the system can be in (e.g., "The car is moving," "The car is stopped").
Choices (The Decisions): At some pages, you have to make a choice (e.g., "Turn left" or "Turn right"). In the old days, different tools handled these choices differently. UMB treats them all as a standard "Choice" layer.
Branches (The Outcomes): Once a choice is made, there are specific outcomes (e.g., "Turn left leads to a park 50% of the time, or a street 50% of the time"). UMB treats these as "Branches."

The Magic of "Annotations":
What makes UMB special is that it doesn't just store the path; it allows you to stick stickers (annotations) on any part of the book.

You can stick a sticker on a page saying, "This is a safe state."
You can stick a sticker on a choice saying, "This is a human decision."
You can stick a sticker on an outcome saying, "There is a 0.5 probability of rain."

Because these "stickers" are separate from the main structure, UMB can handle all kinds of complex systems—from simple random walks to complex games with multiple players—without needing a new file format for each one.

Why Is It Better? (The Speed and Size)

The authors tested UMB against existing formats (like the .tra and .drn files used by popular tools). They found three major benefits:

It's Fast: Loading a model from a UMB file is like reading a barcode. It's significantly faster than reading the long, text-based letters (like the PRISM language or JANI) that tools usually use. The paper shows that UMB can load models in seconds that take much longer with other formats.
It's Compact: Because it uses binary code (1s and 0s) instead of human-readable text, the files are smaller. It's like sending a compressed zip file instead of a 500-page document.
It's Flexible: If a new type of system is invented tomorrow (one that hasn't been seen before), UMB can likely handle it just by adding new "stickers" (annotations) without changing the core container.

The Ecosystem: A Team Effort

This isn't just a theoretical idea; it's already being used. The paper highlights that major tools like PRISM, Storm, and mcsta have already adopted UMB. They even built a "test lab" (called the UMB Observatory) to ensure that when one tool saves a file, another tool can open it perfectly.

They also created a Python library (a set of pre-written code tools) that makes it easy for developers to read, write, and fix these files without needing to be experts in the low-level details.

Real-World Wins (According to the Paper)

The paper gives a few examples of how this helps researchers right now:

The Best of Both Worlds: One tool is great at building complex models, while another is great at solving them quickly. With UMB, you can build the model in the first tool, save it to the UMB container, and instantly hand it to the second tool to solve. You get the best of both without the waiting time.
Teamwork: You can now run the same model through multiple different tools simultaneously to see which one gives the best answer, something that was very difficult before because the tools couldn't easily share the raw data.
Future-Proofing: Researchers working on brand-new, experimental types of models can use UMB to test their ideas immediately, without waiting for a new file format to be invented.

Summary

In short, UMB is a new, super-efficient "universal shipping container" for probabilistic models. It replaces the slow, messy process of rewriting models between different software tools with a fast, compact, and flexible binary format. It allows different computer programs to talk to each other seamlessly, saving time and enabling researchers to solve harder problems faster.

Technical Summary: UMB – A Unified Markov Binary Format for Probabilistic Model Checking

Problem Statement

Probabilistic model checking (PMC) tools have matured over decades, supporting a wide range of models from Markov chains to stochastic games. While high-level modeling languages (e.g., PRISM, JANI) and formats (e.g., JSON-based JANI) facilitate the exchange of high-level descriptions, there is a critical lack of effective mechanisms for exchanging low-level, explicit-state model representations.

In practice, interoperability between tools is hindered by two inefficient approaches:

Re-encoding: Converting explicit-state models back into high-level textual formats (like PRISM language), which incurs massive storage overhead and parsing costs.
Tool-Specific Text Formats: Using ad-hoc, textual formats (e.g., .tra for PRISM, .drn for Storm) that are often limited to specific model types, lack metadata, and are inefficient to generate and parse.

This fragmentation prevents the seamless construction of toolchains that leverage the unique strengths of different PMC tools.

Methodology: The Unified Markov Binary (UMB) Format

The authors propose UMB, a unified, extensible, and efficient binary file format designed specifically for explicit-state probabilistic systems. The methodology rests on three pillars:

1. Unified Mathematical Representation (Annotated Transition Systems)

The format is grounded in a formal mathematical model called the Annotated Transition System (ATS). An ATS decomposes transitions into three layered entities:

States ( $S$ ): The system states.
Choices ( $C$ ): Nondeterministic choices available in a state.
Branches ( $B$ ): Probabilistic outcomes resulting from a choice.

This structure is augmented with annotations (mappings from entities to domains like probabilities, integers, or strings). This formalism is general enough to naturally encode:

Markov Chains (DTMCs, CTMCs)
Markov Decision Processes (MDPs)
Partially Observable MDPs (POMDPs)
Stochastic Games (turn-based and concurrent)
Models with interval probabilities or uncertain transitions
Non-probabilistic Labelled Transition Systems (LTS)

2. Binary File Structure

A .umb file is a (optionally compressed) tar archive containing:

index.json: A metadata file defining the model type, statistics, and a map of included annotations.
Binary Data Files: Three specific types of binary files used to store data efficiently:
- TO1: Fixed-size, integer-indexed arrays (e.g., for probabilities or integer IDs).
- SEQ: Lists of potentially variable-sized values (e.g., strings).
- CSR (Compressed Sparse Row): Indices into other files, mirroring standard sparse matrix storage schemes to allow constant-time lookups of branches by state/choice.

The format supports primitive types (Booleans, integers, doubles, rationals, intervals) and allows for arbitrary annotations (e.g., rewards, atomic propositions, valuations) attached to states, choices, or branches.

3. The UMB Ecosystem

To ensure adoption and consistency, the authors developed a supporting ecosystem:

umbi Library: A Python library serving as a reference implementation for reading, creating, manipulating, and validating UMB files. It provides a format-agnostic abstraction layer (ATS object model) to hide binary layout details.
Tool Support: Major PMC tools (PRISM, Storm, Modest Toolset's mcsta, Paynt, Stamina, Stormvogel) have integrated UMB import/export capabilities.
UMB Observatory: A shared test environment with continuous integration to ensure alignment between tools and the umbi library, detecting semantic inconsistencies early.

Key Contributions

A Universal Low-Level Format: UMB provides the first widely supported, efficient binary format for exchanging explicit-state probabilistic models across different toolchains.
Extensibility: The annotation-based design allows the format to support "exotic" or future model variants (e.g., partially observable stochastic games, interval continuous-time Markov chains) without requiring a new file format specification.
Efficiency: By using binary primitives and sparse storage schemes, UMB avoids the parsing overhead of textual formats and the bloat of re-encoding models into high-level languages.
Practical Tooling: The paper delivers not just a specification, but a working ecosystem including a Python library, Java/C++ bindings (via umbj), and a continuous integration framework.

Results and Performance

The authors evaluated UMB against 36 standard benchmark models (DTMC, CTMC, MDP) comparing it to high-level formats (PRISM, JANI) and existing explicit-state formats (DRN).

Loading Speed: Loading a UMB file to obtain an explicit-state representation is significantly faster than generating such representations from PRISM/JANI models or loading from DRN files.
Export Speed: Exporting to UMB is consistently and significantly faster than exporting to uncompressed DRN. While compression slows down both, UMB remains faster.
File Size: UMB and DRN (uncompressed) have comparable sizes. Compression (GZip, XZ) reduces size similarly for both, with XZ being more effective but slower.
Use Case Validation: The paper demonstrates practical toolchains, such as using mcsta to explore complex state spaces (with dynamic arrays) and exporting to UMB for Storm to perform fast model checking. In one case study (Bitcoin attack model), Storm minimized the state space and exported it to UMB in under 3 seconds, allowing mcsta to verify properties in 13 seconds—a task that timed out when attempted directly in Storm.

Significance and Claims

The paper claims that UMB addresses a fundamental gap in the probabilistic model checking community: the inability to efficiently exchange low-level models. Its significance lies in:

Enabling New Toolchains: It allows researchers and practitioners to combine the modeling strengths of one tool (e.g., mcsta's support for recursive data types) with the solving speed of another (e.g., Storm's algorithms).
Rapid Prototyping: Researchers can develop and test algorithms for new model classes (e.g., interval models) using umbi without needing to implement a full parser and state-space explorer from scratch.
Standardization: By providing a unified, binary standard, UMB reduces the overhead of writing and reading model files, facilitating more maintainable generation scripts and evaluation pipelines.

The authors note that while UMB currently excludes models with symbolic expressions (e.g., real-time clock guards), the format is designed to accommodate such features in future versions via JSON-based annotations. The work represents a shift from isolated tool development toward a modular, interoperable ecosystem for probabilistic verification.