# Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation

arXiv: https://arxiv.org/abs/2606.24672 · HTML: https://mlsanity.com/paper/2606.24672/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 41 references that are in the map.
- First posted on arXiv 23 Jun 2026.

## Builds on (most cited first, 6 of 6)

- [Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover](https://mlsanity.com/paper/1303.0726/) (2013)
- [A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree](https://mlsanity.com/paper/1906.11385/) (2019)
- [A Simple Approximation Algorithm for Optimal Decision Tree](https://mlsanity.com/paper/2505.15641/) (2025)
- [Query strategies for priced information, revisited](https://mlsanity.com/paper/2010.11381/) (2020)
- [The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions](https://mlsanity.com/paper/2111.08793/) (2021)
- [Sequential testing problem: A follow-up review](https://mlsanity.com/paper/2511.15742/) (2025)

## Abstract (arXiv)

In many decision-making scenarios, acquiring information incurs different costs. We consider the problem of constructing a deterministic evaluation strategy that minimizes the expected cost of evaluating a propositional formula under variable costs and a probability distribution over truth assignments. We present a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching. To the best of our knowledge, it is the first practical exact algorithm for this level of generality. Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant. We additionally evaluate a structured heart-disease diagnosis instance. Finally, we prove that the problem is #P-hard and contained in PSPACE.