New AI debugging method pinpoints faulty rules thousands of times faster

Every time you configure a car online, assemble a custom computer, or select options in a complex software product, an invisible engine of logic is working behind the scenes. These systems, known as configurators, rely on configuration knowledge bases: formal collections of constraints that define which combinations of features and components are allowed and which are forbidden. When those constraints are correct, the configurator behaves exactly as engineers intended. But when even a handful of rules go wrong, the consequences can be subtle, frustrating, and expensive, producing configurations that should be possible but are mysteriously rejected, or invalid combinations that slip through the net. A new study published in the Journal of Intelligent Information Systems tackles this problem head-on with an algorithmic innovation that promises to transform how engineers find and fix faulty constraints.

The research team, led by Alexander Felfernig of Graz University of Technology together with Viet-Man Le, Damian Garber, Sebastian Lubos, and Thi Ngoc Trang Tran, presents MSSDirect, a direct diagnosis approach for the automated testing and debugging of configuration knowledge bases. Configuration knowledge bases encode the commonality and variability properties of physical products and software artifacts, and they can grow to extraordinary sizes and complexity. The study’s experimental benchmarks ranged from compact knowledge bases of 64 constraints to industrial-scale models containing 13,972 constraints, including feature models drawn from real software ecosystems. As these artifacts grow, maintaining them becomes increasingly error-prone, driven by cognitive overload among knowledge engineers, gaps in product domain knowledge, and constraints that quietly become outdated as products evolve.

The core idea behind the new approach is elegantly simple in conception but technically demanding in execution. Engineers test knowledge bases using suites of test cases, some positive and some negative. Positive test cases specify configurations that the knowledge base must accept; negative test cases specify configurations that must be rejected. When a positive test case turns out to be inconsistent with the knowledge base, or a negative test case is unexpectedly accepted, something in the constraint set is wrong. The debugging task is to identify the minimal set of faulty constraints responsible for the observed misbehavior, since these constraints must be deleted or adapted to restore agreement between the knowledge base and its intended behavior.

Traditional methods follow a two-phase process rooted in the classical theory of model-based diagnosis introduced by Raymond Reiter in 1987. First, a conflict detection algorithm such as QuickXPlain identifies minimal conflict sets, which are groups of constraints that cannot all be satisfied together with a given test case. Second, a hitting set directed acyclic graph, or HSDAG, enumerates diagnoses as minimal sets of constraints that resolve all detected conflicts. This two-phase architecture has served the field for decades, but it carries a structural cost: the algorithm must repeatedly invoke conflict detection, and the coordination of sequential QuickXPlain calls and HSDAG navigation introduces overhead that grows painfully as knowledge bases and test suites expand. In the study’s benchmarks, this overhead frequently pushed the baseline approach past a 400-second timeout limit.

MSSDirect eliminates the intermediate conflict detection step entirely. Building on the concept of direct diagnosis, which the same research community pioneered in earlier work, the algorithm determines diagnoses directly using a divide-and-conquer strategy. It partitions the consideration set of constraints, checks which positive test cases remain inconsistent with each partition combined with background knowledge, and recursively narrows down the search. The output is a maximal satisfiable subset of the knowledge base, a set of constraints that cannot be extended without violating a test case. The diagnosis is simply the complement of this subset: the constraints excluded from the maximal satisfiable subset are exactly those held responsible for the faulty behavior. Because the method never constructs explicit conflict sets, it sidesteps the sequential bottleneck that plagues the classical approach.

The empirical results are striking. Across six real-world configuration knowledge bases, MSSDirect substantially outperformed the hitting-set baseline in the majority of evaluated scenarios. At a 20 percent rate of inconsistency-inducing test cases, speedups reached up to three orders of magnitude, and at higher inconsistency rates of 30 and 50 percent, they climbed to four orders of magnitude. In one representative scenario on a 233-constraint knowledge base with 500 test cases, the baseline required roughly 370 seconds while MSSDirect completed the same diagnosis in 179 milliseconds, a speedup exceeding 2,000 times. On larger models such as a CNN architecture with 1,637 constraints and a Linux kernel feature model with 13,972 constraints, the baseline timed out entirely for test suites of 250 or more cases, while MSSDirect returned results within milliseconds to seconds. Across 72 evaluated configurations, MSSDirect never exceeded the timeout, whereas the baseline did so in 15.

Importantly, the study also documents where the classical method retains an edge. For very large knowledge bases combined with small test suites, the baseline remains competitive, because its targeted conflict detection can resolve conflicts with fewer and more focused solver invocations when per-check costs dominate. The authors are candid about this complementary strength, noting that the advantage of direct diagnosis scales with the number of violated test cases: as more tests fail, joint divide-and-conquer diagnosis becomes increasingly efficient compared with sequential conflict resolution. This nuanced picture gives practitioners a practical decision rule rather than a blanket replacement recommendation.

Beyond raw speed, the researchers introduced a tunable parameter, lambda, that lets engineers explicitly trade off diagnosis minimality against computational efficiency. When lambda equals one, the algorithm returns subset-minimal diagnoses, the smallest possible explanations of the faulty behavior. Larger values of lambda cut runtime further by relaxing minimality guarantees. The team quantified this trade-off with a cognitive-load analysis measuring minimality, accuracy, and relevance of the extra constraints introduced. Their findings are reassuring on one front: the extra constraints almost never omit anything from the true minimal diagnosis, with accuracy values between 0.976 and 1.000. However, roughly three quarters of the added constraints appear in no subset-minimal diagnosis at all, meaning they are largely irrelevant noise. The authors therefore recommend lambda equal to one as the safe default, reserving lambda equal to two for interactive, time-critical debugging sessions on large knowledge bases where rapid feedback matters more than strict minimality, and advising against values above two.

Correctness was verified by cross-checking the diagnoses produced by MSSDirect against the enumeration of minimal diagnoses generated by the baseline. In 30 of 37 comparable scenarios, the two methods agreed on the first diagnosis, and in all remaining cases the MSSDirect diagnosis appeared later in the baseline’s enumeration, confirming that every answer was a valid minimal diagnosis rather than an approximation. The small divergence reflects a deliberate design choice: MSSDirect ranks diagnoses lexicographically by input constraint ordering, a preference previously validated in user studies where engineers favored diagnoses biased toward constraints they perceived as less essential to the product.

The implications extend well beyond constraint-based configuration. The authors emphasize that their approach is not tied to any single knowledge representation and is equally applicable to answer set programming, Boolean satisfiability solving, and description logic reasoning, formalisms that underpin feature models in software product lines, ontology debugging, and industrial configuration systems in domains ranging from telecommunications and automotive engineering to railway interlocking. Future research directions include learning-based constraint ordering, automated repair suggestions that go beyond fault localization, direct SAT and CSP encodings, and evaluation on test suites collected from real industrial projects. With source code and datasets publicly available, the work lowers a long-standing barrier in knowledge engineering: the diagnosis of large, complex knowledge bases that was once measured in minutes or hours, or simply abandoned as intractable, can now be accomplished in a fraction of a second.

Subject of Research: Automated testing and debugging of configuration knowledge bases using direct diagnosis algorithms

Article Title: Automated testing and debugging of configuration knowledge bases with direct diagnosis

Article References: Felfernig, A., Le, V.-M., Garber, D., Lubos, S., & Tran, T. N. T. (2026). Automated testing and debugging of configuration knowledge bases with direct diagnosis. Journal of Intelligent Information Systems. https://doi.org/10.1007/s10844-026-01090-3

Image Credits: AI Generated

DOI: 10.1007/s10844-026-01090-3

Keywords: configuration knowledge bases, direct diagnosis, automated testing, knowledge base debugging, model-based diagnosis, constraint satisfaction, software product lines, feature models, MSSDirect, QuickXPlain, fault localization, knowledge engineering