Diagnosing the Change: Minimal-Flip Model-Based Diagnosis for Streaming Multi-Fault Systems

Model-based diagnosis finds which components of a system are broken by searching for a set of "abnormal" components that makes a logical model of the system agree with what was observed. With $n$ components there are $2^n$ candidate fault sets. Current solvers handle 20 to 50 simultaneous faults in benchmark circuits, but they degrade quickly beyond that. They also treat every batch of observations as a fresh problem.

Real systems are not re-broken from scratch at every moment. A chip or production line usually carries a large, slowly changing set of faults, and between one diagnostic epoch and the next only a few faults appear or clear. This proposal borrows one idea from dynamic compressive sensing: when a signal changes sparsely over time, recover the change instead of the whole signal, so that cost scales with the size of the change. We apply this to logical diagnosis. At each epoch, the solver searches for the smallest set of health-status flips relative to the previous diagnosis that restores consistency with the new observations. It falls back to global re-diagnosis only when no small flip set exists.

Core Claim

We claim that re-posing streaming diagnosis as a search over changes has two effects. It shrinks the depth of the combinatorial search from the total number of faults $k$ to the number of changed faults $s_t$. It also improves diagnostic accuracy when faults are many but change slowly.

Concretely, let $h_c^t \in \{0,1\}$ mark component $c$ as abnormal at epoch $t$. Let $\hat h^{t-1}$ be the diagnosis carried from the previous epoch. Let $SD$ be the system model and $OBS_t$ the observations at epoch $t$. The per-epoch problem is

$$\min_{h^t} \sum_{c} \big[\, h_c^t \neq \hat h_c^{t-1} \,\big] \quad \text{s.t.} \quad SD \wedge OBS_{t} \wedge h^t \not\vdash \bot .$$

This is a MaxSAT problem whose soft clauses assert "keep the previous status," rather than the usual "assume healthy."

A hitting-set search over this objective, where each candidate must intersect every conflict set, stops at depth $s_t$. Its node count is therefore bounded by roughly $m^{s_t}$ rather than $m^{k}$, where $m$ is the typical size of a conflict set. This bound follows directly from the branching structure of hitting-set trees. When $k \approx 40$ and $s_t \approx 2$, the difference decides whether the problem is solvable at all.

The flip objective alone is fragile, because a wrong previous diagnosis is carried forward indefinitely. The method therefore has two further parts. First, it tracks a small beam of $K$ alternative previous diagnoses, in the spirit of a particle filter. Second, it adapts the change budget based on errors. The budget $s$ starts small and doubles whenever no consistent flip set of size $\le s$ exists. Past a ceiling, the epoch is declared a structural break and handed to a global solver.

Relation to Prior Work

The dynamic-sparsity work supplies the method template. Exact and Stable Recovery of Sequences of Signals with Sparse Increments via Differential _1-Minimization proves that when successive signals differ sparsely, minimizing the $\ell_1$ norm of the increments recovers the sequence, with measurement cost set by the increment sparsity. On the Suzie video sequence this beats frame-by-frame recovery by an average of 7 dB MSE. Dynamic Updating for ell1 Minimization shows that tracking a solution path across small support changes needs 3x to 10x fewer matrix-vector products than re-solving. It also warns that large support shocks erase the savings. Both papers work on continuous linear measurements, whereas we carry the "recover the increment" principle into propositional consistency, where there is no convex path to follow. Asif et al.'s warning motivates our explicit break detector.

The budget-doubling rule adapts the HARD-EST mechanism of Online Wideband Spectrum Sensing Using Sparsity, which grows its sparsity budget when residual error spikes. In our setting, the "residual" is logical inconsistency.

The closest existing work is Multi-Period Sparse Optimization for Proactive Grid Blackout Diagnosis. It adds a persistency prior across time to sparse vulnerability diagnosis and removes the step-to-step jitter of independent solves, finding a 100% persistent bus on CASE30. It differs from our proposal in three ways. It uses a continuous relaxation with thresholding, so it gives no consistency guarantee. It assumes faults only accumulate. It is a soft penalty added to an absolute sparsity objective, not a change-only search. We target discrete logical diagnosis in which faults both appear and clear, as in the multi-mode and intermittent settings studied by Fatemeh Hashemniya et al..

On the diagnosis side, three lines of work supply the machinery and motivate the gap.

All three solve batches offline under a cardinality-minimal objective. We reuse the D-CMMO encoding as our constraint store and change the objective and the temporal loop.

Efficient Sequential Model-Based Fault-Localization with Partial Diagnoses restricts hitting-set search to a small window of conflicts. That is localization in conflict space, and ours is localization in time; the two are complementary. Memory-Limited Model-Based Diagnosis (RBF-HS) attacks the memory cost of the search frontier. Bounding depth by $s_t$ attacks the same explosion from a different side.

Research Program

Encoding and solving. The system encoding comes from D-CMMO with dominator hardening. Observations for epoch $t$ are added through CMMO's selective re-encoding, and each epoch uses a short sliding window of $w$ observation vectors so that intermittent faults can be localized. The flip objective is expressed by replacing each unit soft clause $\neg h_c$ with the unit soft clause $h_c = \hat h_c^{t-1}$. The problem is solved with an incremental core-guided MaxSAT solver, retaining learned clauses across epochs. For each of the $K$ beam members we solve one flip problem and keep the $K$ lowest-cost consistent results. Their cost is the number of flips plus a small term favoring low absolute cardinality, which breaks ties.

Theory. We will prove soundness: every output is a consistent diagnosis. We will also give an exactness condition analogous to the differential-$\ell_1$ result. If the true epoch-$(t-1)$ diagnosis is in the beam, and the true change is the unique minimum-size consistent flip set for the window, the method recovers the true diagnosis at $t$. We will then characterize, empirically and where possible formally, how the uniqueness condition depends on window length $w$ and observation diversity. Finally, we will bound the total cost of budget doubling by a constant factor of the cost at the final budget level, as in iterative deepening.

Benchmarks. Streaming versions of ISCAS-85 and ITC-99 will follow the D-CMMO protocol. Each case starts with a base of 20 to 50 injected stuck-at-0, stuck-at-1, or flipped faults, and observations are random input vectors. Over 100 epochs, faults are added and cleared with Poisson rate $\rho$ per epoch; intermittent faults switch on and off. Occasional "shock" epochs change 10 or more faults at once, which tests the break detector. The main sweep varies base fault count up to 80, which is beyond the reported regime where current solvers degrade, and varies $\rho$.

Baselines

The naive reference carries the previous diagnosis forward unchanged. It re-diagnoses from scratch with D-CMMO only when the carried diagnosis becomes inconsistent. This shows how much of the gain comes simply from not recomputing.

The strongest existing competitor is per-epoch re-solving with D-CMMO over the same sliding window, using the same MaxSAT backend, time budget, and hardware. The file reports D-CMMO solving 92.1% of ISCAS-85 instances within 1000 seconds, against 64.9% for HSD, on batches with 20 to 50 faults and up to 234 observations (Two Compacted Models). On ITC-99 with up to 50 faults, DOE solves over 90% of instances within 600 s, against 62.4% for the previous tool (Efficient MBD with MaxSAT). No reported result was found on Lacuna for any method on a streaming or intermittent-fault version of these benchmarks, so all streaming numbers will be produced here. HSD will also be run per window as a second batch competitor.

Beating D-CMMO means two things. First, a higher fraction of epochs must finish within a fixed per-epoch budget (for example 10 s). Second, the average overlap (Jaccard) between the diagnosis and the injected fault set must be at least as high. We will report results separately for each base fault count, and expect the gap to widen past 50 faults.

Two further baselines use the same solver and the same D-CMMO encoding with a Ma-style persistency term: they minimize absolute cardinality plus $\lambda$ times the number of flips. One variant is re-solved from scratch each epoch, and the other uses incremental solving with phase hints from $\hat h^{t-1}$. The $\lambda$ values are tuned on held-out circuits with the same budget we give our own parameters: $K$, $w$, and the budget ceiling.

Two ablations isolate the proposal's ingredients. The first removes the beam ($K=1$), which measures the cost of error propagation. The second removes the break detector, which shows what happens on shock epochs.

Why not just…?

Why not just use an incremental MaxSAT solver warm-started with the last diagnosis? Warm starting changes where the solver begins, not what it must prove. Under a cardinality objective, the solver still has to certify that no smaller global diagnosis exists, which is a depth-$k$ argument. The incremental-with-phase-hints baseline tests this directly. If it matches our epoch completion rate at 50 to 80 faults, the change of objective is not what matters, and we would report that. Asif et al.'s finding that their path update was about 5x faster than warm-started GPSR is suggestive but comes from continuous solvers, so it is not evidence here.

Why not just re-run D-CMMO on a sliding window every epoch? This is the main threat, since D-CMMO is already fast on sparse observation differences. Zhou et al. note, however, that its savings erode when inputs differ substantially across observations, and it still searches at depth $k$. The fault-count sweep is designed to settle this. If D-CMMO keeps pace up to 80 base faults, our contribution reduces to an accuracy gain from temporal consistency, and we would claim only that.

Why not just add a persistency penalty, as Ma et al. do for power grids? A weighted penalty mixes the two objectives. At any finite $\lambda$ the solver still searches over absolute cardinality, and with a monotone prior it keeps flagging faults that have cleared. Our flip objective is the large-$\lambda$ limit plus explicit break handling. The $\lambda$-sweep baseline shows whether an intermediate value does as well. If it does, the simpler weighted method is the recommendation, and our remaining contribution is the depth analysis and break detection.

Why not just diagnose each epoch independently and combine the results? Model-Based Diagnosis with Multiple Observations already shows that post-hoc aggregation produces up to $10^5$ per-observation diagnoses when at most 100 aggregated ones exist, and loses by 2 to 4 orders of magnitude. Ma et al. show that independent solves jitter from step to step. We include independent per-epoch D-CMMO only as a jitter reference, measured by how many diagnosis changes it reports that do not correspond to injected changes.

Decisive Experiments

The first check is scaling. On streaming ISCAS-85 and ITC-99, we plot the fraction of epochs solved within the per-epoch budget against base fault count at a fixed change rate. The hypothesis predicts that our method stays flat, because its cost tracks $s_t$, while D-CMMO and HSD fall past about 50 faults. Plotting runtime against $s_t$ at fixed $k$ should show the reverse pattern.

The second check is accuracy. Jaccard overlap with the injected set, and the delay between a fault appearing or clearing and the diagnosis reflecting it, should be higher and shorter respectively than for per-epoch cardinality-minimal diagnosis. The reason is that change-minimality uses history to break the ties that masking creates among many-fault explanations.

The third check is the failure mode. On shock epochs, recovery time with the break detector should match a global D-CMMO solve. Without the detector, recovery should degrade, which would confirm Asif et al.'s support-shock warning in the discrete setting.

If the first check fails, meaning flip search is no faster than warm-started cardinality search at high $k$, the central claim is wrong, and the work reduces to a persistency heuristic.