💻 computer science

noDice: Inference for Discrete Probabilistic Programs with Nondeterminism and Conditioning

This paper introduces noDice, a system that extends the discrete probabilistic inference engine Dice to support nondeterminism by constructing Markov Decision Processes and utilizing decision diagrams to efficiently infer distributions over schedulers in loop-free programs.

Original authors: Tobias Gürtler, Benjamin Lucien Kaminski

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tobias Gürtler, Benjamin Lucien Kaminski

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 complex system, like a self-driving car navigating a busy city or a robot trying to catch a moving target. You know some things are random (like a sudden gust of wind), but other things are completely unknown or up to a "bad actor" (like a pedestrian who might suddenly run into the street).

This is the problem noDice solves. It is a new tool for computer scientists to calculate the worst-case scenario for systems that mix randomness (probability) with unknown choices (nondeterminism).

Here is a simple breakdown of how it works, using everyday analogies.

1. The Problem: The "Unknown Driver"

Most computer programs that deal with chance (like predicting weather or stock markets) assume they know the odds. They say, "There is a 70% chance of rain."

But in the real world, sometimes we don't know the odds. Maybe a driver is erratic. Maybe a hacker is trying to break in. In computer science, we call this nondeterminism. It's like a driver who could go left or right, but we don't know their strategy. They might be a cautious driver, a reckless one, or they might change their mind every second.

When you add conditioning (looking at evidence, like "The car did swerve left") to this mix, things get incredibly messy. Traditional tools either ignore the unknown driver or get overwhelmed trying to check every single possibility, crashing the computer.

2. The Solution: The "noDice" Detective

The authors created noDice, a tool that acts like a super-smart detective. Instead of trying to guess what the unknown driver will do, it asks: "What is the absolute worst thing that could happen, given the evidence we have?"

It doesn't just guess; it calculates the maximum possible probability of a bad outcome across all possible strategies the "unknown driver" could use.

3. How It Works: The Three-Step Magic Trick

The paper describes a clever three-step process to solve this without the computer exploding:

Step 1: The Translation (Boolean Compilation)

Imagine you have a messy story about a car chase. noDice first translates this story into a giant, complex logic puzzle made of True/False switches.

It separates the story into two parts:
1. The Action: What the car actually does.
2. The Clues: What the sensors saw (e.g., "The car was at the intersection").
It turns the whole scenario into a massive equation of "If this switch is on, then that happens."

Step 2: The Compression (Decision Diagrams)

If you tried to write out every possible path the car could take, you'd end up with a book longer than the Encyclopedia Britannica. This is where Decision Diagrams come in.

Think of this as a smart map. Instead of drawing every single road, the map merges roads that look the same.
If two different paths lead to the same traffic jam, the map draws them as one single line.
This shrinks a massive, impossible-to-read book into a tiny, manageable pamphlet. This is the secret sauce that makes noDice fast.

Step 3: The Game Board (Markov Decision Process)

Finally, noDice turns that compressed map into a board game called a Markov Decision Process (MDP).

Imagine a board game where some moves are determined by rolling a die (randomness), and other moves are chosen by a player trying to win (the unknown driver).
noDice uses a special algorithm to ask: "If the player plays the worst possible game against us, what are the odds we lose?"
It calculates this "worst-case" probability efficiently, ignoring all the redundant paths it already compressed in Step 2.

4. Why It Matters: The "Plane Landing" Example

The paper uses a great example: A plane trying to land while a car is crossing the runway.

The Randomness: The car's sensors are fuzzy. Sometimes they see the car, sometimes they don't.
The Nondeterminism: The car's driver is unpredictable. They might speed up, slow down, or stop. We don't know their plan.
The Question: "Given that our sensors saw the car at specific spots, what is the maximum probability that the car is still on the runway when the plane lands?"

Old tools would either give up or take hours to calculate. noDice does it in seconds. It tells the pilot: "Even if the driver is trying their hardest to cause a crash, there is only a 3.6% chance they succeed." That gives the pilot confidence to land.

5. The Result: Faster and Smarter

The authors tested noDice against other top-tier tools.

On simple problems: It's just as fast as the best tools.
On complex, high-stakes problems: It is much faster. While other tools get stuck trying to count billions of possibilities, noDice uses its "smart map" (Decision Diagrams) to skip the boring parts and focus on the critical ones.

Summary

noDice is a new way to predict the future when you have both luck (randomness) and mystery (unknown choices). It translates complex code into logic puzzles, compresses them into a tiny map, and then runs a game simulation to find the worst-case scenario. It helps engineers build safer AI, better networks, and more reliable robots by answering the question: "What is the absolute worst that could go wrong?"

1. Problem Statement

Probabilistic Programming Languages (PPLs) are powerful tools for modeling complex probability distributions, particularly in fields like AI and network verification. However, existing state-of-the-art discrete PPLs (such as Dice) lack support for nondeterminism.

Nondeterminism is crucial for modeling:

Unknown information: Situations where details are unspecified (e.g., an adversary's strategy or a vehicle's movement pattern).
Markov Decision Processes (MDPs): Essential for reinforcement learning and verification.

The Core Challenge: Combining nondeterminism with conditioning (Bayesian inference via observe statements) creates a significant theoretical and computational gap:

Non-Compositionality: In the presence of nondeterminism, the maximum conditional probability of a program cannot be inferred simply by composing the maximum probabilities of its subprograms. Local optimal choices do not necessarily lead to a global optimal solution.
State Space Explosion: The only current alternative is to manually encode the program's operational semantics into an MDP and use a model checker (like Storm). However, this often leads to an exponential explosion in the state space, making inference infeasible for large programs.
Lack of Tools: No existing PPL natively supports both nondeterminism and conditioning simultaneously in a scalable way.

2. Methodology: The noDice Framework

The authors introduce noDice, a new inference engine that extends the discrete probabilistic engine Dice. Instead of directly simulating the program or building a raw operational MDP, noDice uses a three-stage pipeline to construct a compact MDP:

A. Boolean Compilation

noDice compiles the source program (a loop-free, first-order functional language with discrete randomness and nondeterminism) into a pair of Boolean formulas:

Model Formula ( $\phi$ ): Represents the program's output behavior, ignoring observations.
Accepting Formula ( $\gamma$ ): Represents the condition that all observe statements succeed.

Trace: Crucially, the compiler generates an annotated trace of flip operations. This trace distinguishes between probabilistic flips (with specific probabilities) and nondeterministic flips (marked as $n$ ), preserving the execution order required for correct semantics.

B. Decision Diagram Construction (ADDs)

The compiled Boolean formulas are converted into Algebraic Decision Diagrams (ADDs):

BDDs to ADDs: While Dice uses Binary Decision Diagrams (BDDs) for purely probabilistic programs, noDice uses ADDs. ADDs generalize BDDs to allow non-binary terminal values.
Unification: The model formula and the accepting formula are combined into a single ADD. This structure exploits the program's internal structure (e.g., conditional independence) to compactly represent the behavior.
Redundancy Removal: The ADD construction automatically removes redundant nodes (e.g., if a branch is unreachable due to a guard), drastically reducing the representation size compared to a raw state enumeration.

C. Lifting to Markov Decision Processes (MDPs)

The final step lifts the ADD into an MDP:

State Mapping: Each node in the ADD becomes a state in the MDP.
Transition Logic:
- Probabilistic Nodes: If the ADD node corresponds to a probabilistic flip, the MDP state has probabilistic transitions to its children.
- Nondeterministic Nodes: If the node corresponds to a nondeterministic flip, the MDP state has a choice of actions (e.g., "Left" or "Right") leading to children, representing the scheduler's choice.
Conditioning via Reachability: The inference query (maximum probability of output $v$ given observations) is transformed into a conditional reachability problem in the MDP: What is the maximum probability of reaching a state labeled with $v$ , conditioned on reaching an "Accepting" state (where observations succeeded)?
Algorithm: The system uses a bisection-based algorithm (implemented in the Storm model checker) to solve for conditional reachability probabilities efficiently on acyclic MDPs.

3. Key Contributions

The noDice Language: A conservative extension of the Dice language that introduces nflip() (nondeterministic choice) alongside flip() (probabilistic choice) and observe(), supporting first-class conditioning in the presence of nondeterminism.
Novel Inference Algorithm: A method that compiles programs to Boolean formulas, converts them to ADDs, and lifts them to MDPs. This approach avoids the exponential blow-up of direct operational semantics by exploiting program structure.
Theoretical Foundation: Formal semantics based on convex sets of distributions (to handle the combination of probability and nondeterminism) and a soundness proof showing that the maximum conditional reachability probability in the constructed MDP equals the maximum probability in the program's semantics.
Optimizations:
- State Compression: A technique to remove states with a single enabled action (probabilistic nodes) by merging transitions, further reducing MDP size.
- Boolean Reduction: Transforming multi-valued output queries into boolean queries to simplify the inference task.

4. Results and Evaluation

The authors implemented a prototype in OCaml and evaluated it against the Storm model checker (using direct MDP encoding) and Dice (on purely probabilistic subsets) across various benchmarks:

Benchmarks: Included vehicle tracking (Runway), Coupon Collector, Network Reachability, Fair Exchange (Rabin), Bayesian Networks, and 3SAT problems with varying degrees of nondeterminism.
State Space Reduction: noDice consistently generated significantly smaller MDPs than direct encoding. For example, in the "Coupon" benchmarks, noDice's ADD-based approach reduced the state space by orders of magnitude compared to Storm's explicit enumeration.
Performance:
- High Dimensionality: noDice outperformed Storm on problems with high dimensionality (many variables), such as the Coupon Collector and Runway benchmarks. Storm struggled with the state space explosion in these cases.
- Low Dimensionality: On problems with few variables but complex logic (e.g., Network benchmarks), Storm was faster because the overhead of compiling to ADDs and lifting to MDPs outweighed the benefits of state reduction.
- Nondeterminism Impact: The runtime of noDice was largely insensitive to the amount of nondeterminism, as the compilation phase (ADD construction) is agnostic to the nature of the flips.
Scalability: noDice successfully solved benchmarks that caused Storm to time out (e.g., 3SAT instances with 100 variables).

5. Significance

Bridging the Gap: noDice is the first tool to provide efficient, exact inference for discrete probabilistic programs that combine nondeterminism and conditioning.
Scalability: By leveraging the structural properties of programs via Decision Diagrams, it overcomes the state-space explosion problem that plagues traditional model checking approaches for PPLs.
Practical Application: It enables the verification and analysis of complex systems (like autonomous vehicle tracking or network protocols) where uncertainty is both probabilistic (sensor noise) and nondeterministic (adversarial behavior or unknown parameters).
Future Direction: The work opens the door for integrating nondeterminism into other PPLs and suggests that decision diagram-based compilation is a viable path for scaling probabilistic inference in complex, hybrid systems.

In summary, noDice demonstrates that by treating nondeterminism as a scheduler choice within a compactly represented MDP derived from program structure, one can perform exact inference on problems that were previously intractable for existing PPLs.