Most automated diagnosis tools assume that one broken component explains a failure. The assumption keeps diagnosis tractable: checking $N$ single-component hypotheses is cheap, while checking every combination means $2^N$ candidates. In circuits, machines and service meshes, though, several components often fail at once. Engines that drop the assumption then hit a "cardinality wall." On standard circuit benchmarks, Conflict-Directed A (a best-first search over sets of suspect components) fails almost completely once more than five or six components must be blamed together, as reported in Exploring the Duality in Conflict-Directed Model-Based Diagnosis. Heuristic search has a separate tool for exactly this tension between being thorough early and committing later: dynamic heuristic weighting*, where the search changes how much it trusts its estimate of remaining cost as it progresses.
This note proposes treating the single-fault assumption not as a hard restriction but as the opening phase of a weighting schedule. The search would be careful and near-exhaustive over small candidate sets, where single and double faults live and where most real failures concentrate. It would then become progressively greedier as the candidate set grows, while keeping a guarantee that the reported diagnosis is at most $w$ times larger, or more costly, than the smallest one. Concretely, we would port the bounded-suboptimal priority functions and termination rules of Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search and Revisiting Suboptimal Search into the diagnosis side of the Switching Diagnostic Engine. Doing so requires solving one new technical problem: in diagnosis the heuristic itself keeps improving during the search.
Core Claim
In model-based diagnosis, a conflict is a set of components that cannot all be healthy given the observations. A diagnosis is a set of components that touches (or "hits") every conflict. Searching for small diagnoses is therefore a hitting-set search. Tree depth equals fault cardinality. The natural cost-to-go estimate $h$ is a lower bound on how many more components are needed to hit the conflicts not yet covered. This setting differs from the puzzles and grid maps where non-linear priority functions were developed in one essential way: conflicts are discovered lazily, so $h$ is computed from a growing conflict set. A node's priority computed at time $t$ becomes stale, and only ever in one direction, which is too low.
We write the priority as
$$f_t(n) = \Phi\big(g(n),\, h_t(n)\big),$$
where $g(n)$ is the cost of the candidate set at node $n$ (its cardinality, or the sum of negative log fault priors), $h_t(n)$ is the admissible lower bound computed from the conflicts known at time $t$, and $\Phi$ is a priority function in the family that Chen and Sturtevant characterized. Because adding conflicts can only raise the lower bound, $h_t(n)$ is nondecreasing in $t$. Admissibility with respect to the full, unknown conflict set holds at every $t$.
Our claim has two parts. The first is theoretical: the four conditions on $\Phi$ (monotonicity, slope, boundary and growth rate) still deliver a $w$-suboptimality bound without node re-expansions when $h$ grows monotonically, provided that open nodes are lazily re-scored when popped and the high-water-mark termination test of Improved Optimistic Search is applied to re-scored values. The second is empirical. Inside the Switching Diagnostic Engine, a schedule that is cautious at low cardinality and greedy at high cardinality should push the cardinality wall outward beyond what the engine's primal-dual switching already achieves. The direction of the best schedule should also be predictable from the true fault cardinality.
Position Relative to Prior Work
Two papers supply the method. Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search derives conditions under which a non-linear priority in the plane of $g$ and $h$ keeps a $w$-bound without re-opening nodes. It also introduces two parabolic schedules: one cautious early and greedy late, and one greedy early and cautious late. Revisiting Suboptimal Search builds Improved Optimistic Search on top of these schedules, adding a second focal list, a high-water-mark termination rule and solution updating. Both were evaluated only on grid maps, sliding tiles, pancake and racetrack domains, all with a fixed heuristic. We reuse their schedules and termination rule. Our additions are the extension to a monotonically sharpening heuristic and the application to hitting-set trees.
Exploring the Duality in Conflict-Directed Model-Based Diagnosis both motivates and constrains the work. It shows that conflicts hit diagnoses just as diagnoses hit conflicts, and its Switching Diagnostic Engine alternates between the two searches. That engine reaches diagnoses of cardinality 12 where Conflict-Directed A collapses. Its node ordering, however, is uniform best-first, and the authors list domain heuristics as future work. The paper's main lesson is that conflict discovery, not node ordering, drove its gains. This rules out the naive design of reweighting Conflict-Directed A alone and declaring victory. We therefore build inside the Switching Diagnostic Engine and require gains that add to its own.
Pohl's depth-dependent weighting in The Avoidance of (Relative) Catastrophe, Heuristic Competence, Genuine Dynamic Weighting and Computational Issues in Heuristic Problem Solving prescribes the opposite intuition, greedy early and cautious late. So do the goal-distance schedules used in robot planners such as Towards Path Planning Algorithm Combining with A-Star Algorithm and Dynamic Window Approach Algorithm. This disagreement with the empirical wins of the cautious-early schedule reported by Chen and colleagues is the open question we test directly. A hitting-set tree is a clean place to test it, because depth has a physical meaning: the number of simultaneous faults.
Research Program
The first component is the analysis. We would state and prove the monotone-heuristic version of the Chen–Sturtevant bound. The intended argument is that a stale priority underestimates the true one. Such a node is popped no later than it should be, so it causes extra re-scoring but never an unsafe termination, as long as the termination test uses re-scored values. We will also identify where the argument fails. In particular, if $\Phi$ violates the growth-rate condition, a large jump in $h$ might reorder already-closed nodes, and we want to know whether that can force re-expansion.
The second component is the engine. We would implement Optimistic Diagnostic Search as a replacement for the primal (diagnosis-finding) side of the Switching Diagnostic Engine, keeping its dual conflict-finding side and switching rule unchanged. The bound $h_t$ is the size of a greedy packing of pairwise-disjoint unhit conflicts, which is admissible because each disjoint conflict needs its own component. Under weighted costs, each conflict in the packing contributes its cheapest member. Priority functions tested are the two parabolic schedules, Pohl's linear depth schedule and static weighting. We also test one schedule specific to diagnosis, whose bend point is placed at the cardinality where the fault prior's cumulative mass reaches a set fraction. This last schedule is how a soft single-fault assumption enters the search.
The third component is the schedule study. We would pre-register the hypothesis that the cautious-early schedule wins when the true minimal cardinality is small (one to four) and the greedy-early schedule wins when it is large (eight to twelve), and measure where the crossover falls.
Baselines
The naive reference point is greedy single-fault peeling. The engine finds the best single-component explanation, marks that component as faulty, and repeats on the remaining discrepancy until the observations are explained. It costs almost nothing and is how many deployed tools behave. We run it on the same instances and time limit, and it is beaten if our engine finds smaller or correct diagnoses on instances where faults mask one another.
The original baseline is Conflict-Directed A* as described and benchmarked by Stern et al. It is the classical best-first answer to the cardinality wall and the method the wall was measured on. We run it with the same consistency checker and conflict extractor.
The strongest existing method is the Switching Diagnostic Engine from Exploring the Duality in Conflict-Directed Model-Based Diagnosis. Under a 30-second limit, it reports an 88% success rate on c432 against 33% for Conflict-Directed A*, and 9% on c1355 against 0%. It is the strongest competitor because it already crosses the cardinality wall by improving conflict discovery, which is where a skeptic would say all the leverage lies. We reimplement it in the same codebase, with the same SAT-based consistency checker, the same time limit and machine, and the same injected-fault instances, and we first confirm that our reimplementation roughly reproduces the reported success rates. Beating it means higher success on c432 and on c1355 at the 30-second limit. Alternatively, at equal success, it means significantly fewer consistency-checker calls, together with a reported cardinality within the promised factor $w$ of the best known.
Static weighted A inside the Switching Diagnostic Engine is the ablation that isolates the schedule itself. It uses the same bound $w$, the same heuristic and the same termination rule, and differs only in that $\Phi$ is linear. No reported result was found on Lacuna for static weighted A on hitting-set diagnosis, so this number is produced here. A second ablation isolates the monotone-heuristic contribution: it compares lazy re-scoring of stale nodes with recomputing all of OPEN whenever a conflict is added, and with ignoring staleness altogether. The third variant can violate the bound, and we will report whether it does. Every weighted variant receives the same tuning budget over $w$, namely a fixed grid of 1.25, 1.5, 2 and 3, selected on a held-out set of circuits.
Why not just…?
Why not just use static weighted A* with a well-chosen $w$? This is the most serious threat. With unit costs, hitting-set trees have huge plateaus of tied priorities, and on plateaus the shape of $\Phi$ may matter little. Chen and Sturtevant found the cautious-early schedule expanded about 185k nodes against about 318k for static weighting on the 15-puzzle at $w=1.5$. On grid maps, however, static weighting was competitive at low weights, so the advantage is domain-dependent and not guaranteed. The static-weight ablation decides this. If static weighting matches the schedules under both unit and prior-weighted costs, we will report that dynamic weighting does not transfer to diagnosis, and that the value lies only in the bounded-suboptimal termination rule.
Why not just keep the single-fault assumption and iterate? Peeling off one fault at a time fails exactly when faults interact. One fault can hide another's symptoms, and joint misconfigurations look valid parameter by parameter, as the masking and dilution results summarized in the research file indicate. Peeling also gives no bound on how far its answer is from the smallest diagnosis. We test it on instances built with deliberate masking, meaning faults injected on reconvergent paths of the same circuit. We also test it on random multi-fault instances, where it may do respectably, and we will say so if it does.
Why not just deepen cardinality one level at a time? Exhausting all single faults, then all pairs, and so on is the purest relaxation of the single-fault assumption, and it guarantees minimal cardinality. It corresponds to a schedule that is fully cautious at every depth. Our prior-mass schedule matches it at low cardinality by design, so it is a natural control. We expect it to stall where Conflict-Directed A* stalls, because the number of candidate sets grows combinatorially per level. Including it shows whether greediness at depth is what buys the gains.
Why not just improve conflict discovery, since that is what made the Switching Diagnostic Engine work? This may well be the larger lever, which is why we build inside that engine rather than compete with it. Additivity is the test. If our ordering helps Conflict-Directed A* but not the Switching Diagnostic Engine, then ordering and conflict learning are substitutes, and the honest conclusion is that dynamic weighting matters only for engines that lack good conflict discovery.
Proposed Experiments
The main testbed is the ISCAS85 and 74XXX circuits used by Stern et al., including c432 and c1355. On these circuits we inject faults with true minimal cardinality ranging from 1 to 12, using 100 instances per cardinality and circuit and a 30-second limit. We measure success rate, wall time, consistency-checker calls, nodes expanded and re-scored, and the ratio of reported cardinality, or cost, to the best known. Both unit costs and prior-weighted costs are run, because the shape of the schedule should matter more when costs are non-uniform.
The first decisive check is the success rate on c1355 at high cardinality, where every existing method is near zero. The second is the predicted schedule crossover: if the best schedule does not depend on true cardinality, the soft-single-fault framing is wrong. The third is the bound check. Across all instances, no variant that satisfies the extended conditions may ever report a diagnosis more than $w$ times the best known, and the staleness-ignoring ablation will show whether the bound is fragile in practice.
As a secondary, clearly exploratory transfer test, we would apply the same ordering to search over sets of joint interventions in the synthetic causal graphs used to evaluate Robust Root Cause Diagnosis using In-Distribution Interventions, injecting two root causes on the same causal path. That method assumes one root cause per path. It reports Recall@1 between 0.90 and 1.00 on single-cause PetShop categories, but no reported result was found on Lacuna for the two-causes-per-path setting. We would report both the original method and our search wrapper on that setting.
References
- Exploring the Duality in Conflict-Directed Model-Based Diagnosis
- Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search
- Revisiting Suboptimal Search
- The Avoidance of (Relative) Catastrophe, Heuristic Competence, Genuine Dynamic Weighting and Computational Issues in Heuristic Problem Solving
- Towards Path Planning Algorithm Combining with A-Star Algorithm and Dynamic Window Approach Algorithm
- Robust Root Cause Diagnosis using In-Distribution Interventions