Restart Until the Same Diagnosis Appears: Multi-Start Search for Multi-Fault Circuit Diagnosis

When a digital circuit gives wrong outputs, diagnosis means finding which gates are broken. Older tools assumed exactly one gate had failed. That "single-fault assumption" keeps the search to one hypothesis per gate, but it breaks down when several faults hide or distort each other's symptoms. Without it, the candidate explanations are every subset of gates, and the best current solvers handle this with complete, systematic reasoning engines. These are MaxSAT solvers: they find a truth assignment that satisfies all hard logical constraints while violating as few soft constraints as possible. We propose a different engine. Run a fast, cheap local search many times from random starting points. Stop when the same smallest explanation has been found repeatedly, and when a simple statistic says few unexplored outcomes are likely to remain.

The real question is not whether restarts can find diagnoses. It is when repeated agreement among restarts can be trusted as evidence of optimality. Fault masking may create wrong explanations that attract many restarts. If so, "seen it twice" would stop the search with false confidence. We will measure exactly when that happens, how it relates to the circuit's structure, and what it costs compared with complete solvers. Each restart needs only memory linear in the formula, so the method also offers an alternative to search procedures whose memory grows exponentially.

Core Claim

On structurally compressed multi-fault diagnosis encodings of the ISCAS-85 and ITC-99 benchmark circuits, a repeat-until-redundant multi-start local search can do three things. It can reach the minimum number of faulty gates on most instances that complete MaxSAT solvers fail to finish within their time limits. Its stopping rule can carry a calibrated false-stop rate. And its runtime is predicted by the fraction of random starts that fall into the optimal solution's basin of attraction (the region of starting points from which local search reaches that solution).

We further claim this basin fraction shrinks in a measurable way with two quantities. The first is the number of injected faults. The second is the amount of reconvergent fanout, meaning places where signal paths split and later rejoin. That fanout is also where masking arises. This gives a structural account of when restarts work and when they do not.

The idea transfers the RUSSO rule ("restart until seen same optimum") from Secrets of Matrix Factorization to diagnosis. That paper showed fast local solvers restarted until the best value repeats beat slow monolithic solvers on non-convex matrix factorization. We strengthen the stopping rule with an estimate of how much probability mass sits in local optima that have not yet been seen. Let $N$ be the number of restarts so far and $n_1$ the number of distinct local optima, here diagnoses that cannot be improved by single-gate flips, that were reached exactly once. The chance that the next restart lands on a never-seen optimum is then estimated by the classical missing-mass estimate

$$\hat{M} = \frac{n_1}{N}.$$

We stop when the best diagnosis has been seen at least $r$ times and $\hat{M} < \epsilon$. If restarts are independent and the optimal basin has fraction $p$ of the starting distribution, the probability that all restarts miss it is $(1-p)^N$. This is the same geometric argument used in On Local Optimizers of Acquisition Functions in Bayesian Optimization. The difference here is that $p$ is estimated from the run itself rather than assumed. That paper names this unknowability of $p$ as an open problem.

Research Program

The base encoding is the dominator-oriented MaxSAT formulation of Efficient Model Based Diagnosis with Maximum Satisfiability. It prunes gates whose faults are always explained by a single dominating gate, fixes logically constant nodes, and removes insensitive paths. The result halves variable counts and cuts soft clauses by two-thirds. For multiple observations we also use the compacted D-CMMO encoding of Two Compacted Models for Efficient Model-Based Diagnosis. Both papers solve with systematic engines. We reuse their encodings unchanged, so any gain comes from the search strategy and not from the formulation.

The inner solver is a GSAT-style greedy local search over gate-health variables. It flips health assumptions to reduce the number of violated observation constraints plus the number of gates declared faulty. An Empirical Study of Greedy Local Search for Satisfiability Testing showed such searches spend most of their time on flat plateaus and need restarts to scale. We run it with three seeding distributions:

  • uniform random health assignments;
  • conflict-guided seeds, which pick one gate from each conflict found by a single fast consistency check;
  • low-discrepancy seeds over the conflict-guided distribution, motivated by the logarithmic speedup that A Rigorous Runtime Analysis for Quasi-Random Restarts and Decreasing Stepsize proved for quasi-random restarts. That result covers continuous landscapes only, so whether it carries over to Boolean diagnosis is an open question.

The analytic part has three pieces. First, on every instance a complete solver can finish, we compute the true minimum fault count. We then estimate the optimal basin fraction $p$ from thousands of restarts and regress $\log p$ on fault count, observation count, and a reconvergent-fanout measure. Second, we measure the false-stop rate of the redundancy rule across $r$ and $\epsilon$. A false stop means stopping on a diagnosis that is not minimum-cardinality. Third, we report wall-clock time, peak memory, and restarts-to-stop as a function of circuit size. This follows the call in Quantifying Computational Complexity in Algorithmic Design to replace qualitative efficiency claims with measured scaling.

We also test whether complete solvers show heavy-tailed runtimes on these instances, meaning a small share of runs take vastly longer than typical. Local Minima, Heavy Tails, and Search Effort for GBFS found such tails in planning and cut them with restarts. If diagnosis has heavy tails, that explains why restarts help. If it does not, the advantage must come from somewhere else, and we will say so.

Baselines

The naive reference point is diagnosis under the single-fault assumption. For each gate we test whether marking it alone as faulty explains the observations, and we report the failure rate. With 20 to 50 injected faults this should almost always fail. It is included to show how much the multi-fault formulation contributes, and because Tureis found that dropping single-failure assumptions improved localization F1 by up to 35.4% in a different setting, smart-home sensors.

The strongest complete competitors are D-CMMO and the dominator-oriented encoding with the core-guided MaxSAT solver wboinc. Two Compacted Models for Efficient Model-Based Diagnosis reports D-CMMO solving 92.1% of ISCAS-85 multi-fault instances within 1000 seconds, against 64.9% for the hitting-set algorithm HSD. Efficient Model Based Diagnosis with Maximum Satisfiability reports over 90% of ITC-99 instances solved within 600 seconds, against about 62.4% for the previous best. We regenerate their instance families: 300 cases per fault model (stuck-at-0, stuck-at-1, flipped), 20 to 50 faults, and up to 234 observations. We run every method on the same machines under the same time limits, 1000 seconds for ISCAS-85 and 600 seconds for ITC-99. Our method gets no extra tuning budget beyond a fixed grid over $r$ and $\epsilon$ chosen on a held-out set of circuits.

Beating these baselines means one of two things. Either we solve a substantial share of the instances they leave unsolved with zero observed false stops on the instances where ground truth exists, or we cut median time-to-optimal-diagnosis with a false-stop rate below 1%. Matching their solve rate at higher cost would count as a negative result.

The closest stochastic competitor is the OptLB strategy from Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach. It pairs a local-search hitting-set finder with an exact solver used only for lower bounds. On general pseudo-Boolean optimization, adding that local search gave 44 additional solved instances and 20% less memory for SCIP. No reported result was found on Lacuna for this method on circuit diagnosis, so we will run it ourselves on the same encodings.

For memory comparisons we include RBF-HS from Memory-Limited Model-Based Diagnosis. It enumerates diagnoses in linear space but paid a time overhead in 62% of its cases.

Two ablations isolate the key ingredients. In the first, a single long local search with random-walk noise gets the same total flip budget but no restarts. In the second, restarts run under a fixed budget without the redundancy and missing-mass stopping rule. This separates the value of restarting from the value of knowing when to stop.

Why not just…?

Why not just run the dominator-compressed MaxSAT solvers, which already solve over 90%? This is the main threat. If the remaining roughly 8% of instances are hard for local search too, our method adds nothing. The experiment settles it directly by reporting results on exactly the instances D-CMMO and wboinc fail to finish. We also report anytime quality, meaning the fault count reached at 10 and 100 seconds, since complete solvers may give no answer before they finish. If local search does no better on the hard residue, the contribution shrinks to the basin-structure analysis, and we will present it that way.

Why not just use local search inside the implicit hitting set loop, as OptLB already does? OptLB uses local search for upper bounds and still relies on an exact solver to prove optimality. The file reports that the proof-producing route costs a median 10.7% runtime overhead, reaching 100% at the 90th percentile, and checking those proofs can take longer than solving. Our proposal trades the proof for a statistical stopping rule. That trade only makes sense if the rule is well calibrated, so the false-stop measurement is the deciding evidence. We run OptLB side by side to show what the trade buys in time.

Why not just run one long noisy local search instead of restarts? GSAT's plateau behavior in An Empirical Study of Greedy Local Search for Satisfiability Testing and the failure of local exploration alone to remove heavy tails in Local Minima, Heavy Tails, and Search Effort for GBFS suggest restarts matter. Neither result concerns diagnosis, however, so the equal-budget single-run ablation decides it here.

Why not just assume a single fault? With 20 or more injected faults, a single gate cannot explain the observations. We include this only as the floor.

Proposed Experiments

The decisive check is calibration. On ISCAS-85 instances with known minimum fault counts, we plot the observed false-stop rate against the estimated missing mass $\hat{M}$ at stopping time. If masking-heavy circuits such as c6288, the 3600-gate multiplier that Critical Reasoning singles out for its reconvergent structure, show high false-stop rates at small $\hat{M}$, the redundancy rule is unreliable exactly where masking occurs. That would be an important negative finding about restart-based certification.

The second check is predictive. Does the basin fraction $p$, estimated from the first 50 restarts, predict total time-to-stop across circuits and fault counts? If it does, it gives the instance-adaptive restart budget that prior work leaves open.

The third check compares runtime distributions of wboinc and D-CMMO on the same instances against those of restarted local search. This tells us whether diagnosis inherits the heavy tails seen in planning.

The fourth check compares the three seeding schemes at equal restart counts. It tests whether the quasi-random advantage proved for continuous functions survives on Boolean diagnosis encodings.

Every result is reported with wall-clock time, peak memory, and restart counts as functions of gate count and fault count.