# Approximate Model-Based Diagnosis Using Greedy Stochastic Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2014.

## Built on by (most cited first, 3 of 3)

- [Evaluating Large Language Models for Real-World Engineering Tasks](https://mlsanity.com/paper/2505.13484/) (2025)
- [On a Uniform Causality Model for Industrial Automation](https://mlsanity.com/paper/2209.09618/) (2022)
- [A More General Theory of Diagnosis from First Principles](https://mlsanity.com/paper/2309.16180/) (2023)

## Abstract (arXiv)

We propose a StochAstic Fault diagnosis AlgoRIthm, called SAFARI, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, that SAFARI achieves several orders-of-magnitude speedup over two well-known deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses; further, SAFARI can compute a range of multiple-fault diagnoses that CDA* and HA* cannot. We also prove that SAFARI is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of SAFARI in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diagnosis computed. SAFARI also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.