Cost-Optimal Decision Diagrams: Zong et al. 2026 arXiv

Xia Zong, Tuomo Lehtonen and Jussi Rintanen released a paper titled "Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation" on arXiv (arXiv:2606.24672) submitted on 23 Jun 2026. The authors present a branch-and-bound algorithm, report experiments on random instances and a structured heart-disease diagnosis instance, and prove the underlying problem is #P-hard and contained in PSPACE.

What did the authors present?

The paper presents a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching that the authors describe as "the first practical exact algorithm for this level of generality." It formalizes the problem as constructing a deterministic evaluation strategy that minimizes expected cost given variable test costs and a probability distribution over truth assignments, and it establishes complexity: the problem is #P-hard and contained in PSPACE.

The submission is documented as arXiv:2606.24672, spans 11 pages and includes 4 figures. The authors also discuss a greedy beam-search variant and quantify an efficiency-quality trade-off for that heuristic in experiments.

How does the algorithm work?

It constructs deterministic evaluation strategies that minimize expected cost under variable per-variable costs and a distribution over truth assignments, using branch-and-bound search guided by variable-selection heuristics, with pruning and caching to reduce the search space. The authors implemented both the exact branch-and-bound solver and a greedy beam-search variant to explore performance trade-offs.

The core idea is to treat variable queries as costly observations and to search over decision diagrams (evaluation strategies) rather than fixed query orders; heuristics select which variable to branch on, pruning removes provably suboptimal branches, and caching reuses subproblems. The greedy beam-search is evaluated to show where practitioners might accept suboptimality for speed.

How did they evaluate it?

They evaluated the algorithms on random instances to demonstrate scalability and on a structured heart-disease diagnosis instance to show an applied example; the experiments are used to quantify the efficiency-quality trade-off of the greedy beam-search variant. The paper includes four figures that illustrate experimental results and trade-offs across the tested instances.

The authors report that experiments on random instances demonstrate scalability, and they explicitly single out a structured heart-disease diagnosis instance as an additional case study. The manuscript and supporting materials are presented on arXiv with DOI https://doi.org/10.48550/arXiv.2606.24672.

Why it matters

Minimizing the expected cost of information acquisition is a practical problem in domains where measurements or tests carry different costs, for example medical diagnosis. An exact algorithm that handles variable costs and probabilistic truth assignments fills a gap between theory and applied decision making, because it provides a concrete procedure and a documented complexity boundary (#P-hard, in PSPACE) for practitioners and researchers designing cost-aware testing policies.

What to watch

Look for follow-up work that scales the approach to larger structured real-world domains and for comparative studies that report numeric performance across public benchmarks. Also watch for implementations or code releases linked from the arXiv entry that enable reproduction of the reported experiments.