Model-Based Diagnosis (MBD) operates on a simple, elegant premise: given a formal description of how a system should behave and an observation of how it is behaving, identify the components whose failure explains any discrepancies.
However, a fundamental mathematical wall quickly complicates this premise. If a system contains $n$ components, and each component can either be healthy or faulty, there are $2^n$ possible system states. When we assume only a single component can fail at a time, the search space is linear and manageable. But in complex, real-world systems—such as large-scale digital circuits, distributed software networks, or patients with multiple overlapping conditions—multiple faults can and do occur simultaneously.
Accounting for multiple concurrent failures triggers a combinatorial explosion. Exhaustively searching through every possible combination of faulty components becomes computationally intractable. Over the decades, researchers have developed several core strategies to bypass this exponential bottleneck, transforming an impossible global search into a series of localized, highly optimized inferences.
The Root of the Explosion: Multi-Fault Hypotheses
The challenge of multi-fault diagnosis was recognized early in domains like medicine and hardware engineering. In medical diagnostics, Harry E. Pople demonstrated in The Formation of Composite Hypotheses in Diagnostic Problem Solving: An Exercise in Synthetic Reasoning that forming composite hypotheses for patients with multiple diseases causes traditional search methods to fail due to the astronomical number of symptom-to-cause combinations.
In the hardware domain, de Kleer et al. formalized this problem in their work on the General Diagnostic Engine (Reasoning about Multiple Faults). They showed that as the number of components grows, the possible combinations of faults and logical predictions scale exponentially. To avoid evaluating all $2^n$ combinations, early frameworks focused on identifying minimal conflict sets—the smallest groups of components that cannot all be functioning correctly given the observed data. A diagnosis is then a minimal hitting set that intersects every conflict set. While this narrows the scope, computing these hitting sets can still trigger an exponential explosion if the system is treated as a flat, unstructured collection of parts.
Exploiting Topology and Hierarchical Abstraction
The most effective way to defeat an exponential search space is to break it into independent pieces. Instead of treating a system as a flat bag of components, researchers exploit the physical or logical structure of the system.
Hierarchical Abstraction
Michael R. Genesereth introduced a hierarchical approach to hardware diagnosis in Diagnosis Using Hierarchical Design Models, demonstrating that analyzing a system at coarse structural levels before drilling down into gate-level details drastically reduces the computational cost of test generation.
This concept was scaled to multi-fault scenarios by Siddiqi et al. in Hierarchical Diagnosis of Multiple Faults. They abstracted sub-circuits into "cones" represented by a single health variable. If a cone's output matches expectations, the entire internal subsystem can be assumed healthy, instantly pruning thousands of potential fault combinations from the search space.
Flat Search Space: [C1] [C2] [C3] [C4] [C5] [C6] --> 2^6 = 64 combinations
Hierarchical Search: [ Cone A ] [ Cone B ] --> 2^2 = 4 combinations
(C1, C2, C3) (C4, C5, C6)
Topological Decomposition
If a circuit or system network can be arranged like a tree, the diagnostic complexity drops from exponential to linear. The authors of Diagnosing Tree-Decomposable Circuits proved that by leveraging the physical topology of a system, one can bound the diagnostic complexity based on its structural arrangement (such as tree-width) rather than the total number of components. This prevents the exponential explosion of identified conflicts even in massive systems.
Focusing and Lazy Evaluation
Another insight that makes MBD practical is that we rarely need to find every possible diagnosis upfront. Instead, we only need to find the most probable diagnoses or compute just enough information to guide the next physical test or observation.
In Focusing on Probable Diagnoses, Johan de Kleer introduced a "focusing" strategy that restricts the diagnostic engine's attention to the most likely fault combinations based on prior probabilities. By ignoring highly improbable multi-fault combinations (e.g., 5 independent components failing at the exact same millisecond), the algorithm can diagnose complex circuits with thousands of components in seconds.
Taking this a step further, Schekotihin et al. proposed a sequential localization method in Efficient Sequential Model-Based Fault-Localization with Partial Diagnoses. Traditional frameworks require fully mapping out all conflicts or leading diagnoses before generating a query or test for the user. The authors bypassed this by using partial diagnoses. By calculating only a small subset of conflicts necessary to determine the next best measurement, they achieved up to a 98% reduction in computation time without sacrificing accuracy.
Logical Compilation and Modern Solvers
Rather than inventing bespoke search algorithms, a highly successful branch of MBD offloads the combinatorial burden to modern, state-of-the-art Boolean reasoning engines. This is achieved by "compiling" the system description and observations into a standardized logical format.
Knowledge Compilation
Adnan Darwiche demonstrated in Model-Based Diagnosis using Structured System Descriptions that system descriptions can be compiled into Decomposable Negation Normal Form (DNNF). This offline compilation step shifts the computational complexity away from real-time troubleshooting. Once the system structure is compiled into a DNNF graph, running online diagnostic queries and calculating probabilities becomes linear relative to the size of the compiled network.
MaxSAT Encodings
Alternatively, MBD can be framed as a Maximum Satisfiability (MaxSAT) problem, where the goal is to find a truth assignment that satisfies the system logic while maximizing the number of "healthy" component assumptions.
Marques-Silva et al. advanced this approach in Efficient Model Based Diagnosis with Maximum Satisfiability by introducing Dominator-Oriented Encoding (DOE). Instead of passing a raw circuit description to a solver, they used structural circuit analysis—specifically identifying graph "dominators" (nodes through which all signals must pass)—to simplify how values propagate. This structural preprocessing allows MaxSAT solvers to implicitly prune massive branches of the multi-fault search space, yielding performance gains of up to three orders of magnitude.
Similarly, Raiman et al. utilized sensitivity analysis in their IMPLODE architecture (Critical Reasoning) to isolate "critical" assumptions. By mathematically determining which component assumptions actually impact the observed discrepancy, they prevent the diagnostic engine from wasting cycles enumerating irrelevant fault candidates.
Key Foundational Work
Diagnosis Using Hierarchical Design Models (1982) — contributed 2 concept elements to this direction.
The Formation of Composite Hypotheses in Diagnostic Problem Solving: An Exercise in Synthetic Reasoning (1977) — contributed 1 concept elements to this direction.
ARBY: Diagnosis With Shallow Causal Models (1982) — contributed 1 concept elements to this direction.