Premise Set Caching for Enumerating Minimal Correction Subsets

Alessandro Previti, Carlos Mencía, Matti Järvisalo, João Marques-SilvaAAAI 2018 · DOI

Introduction

In complex systems—ranging from software debugging to hardware fault diagnosis and large-scale ontology management—we often encounter "overconstrained" scenarios where a set of rules or constraints cannot be simultaneously satisfied. To resolve these inconsistencies, researchers identify Minimal Correction Subsets (MCSes): the smallest sets of constraints whose removal restores system satisfiability.

In their AAAI 2018 paper, Alessandro Previti, Carlos Mencía, Matti Järvisalo, and Joao Marques-Silva introduced Premise Set Caching, a novel technique designed to accelerate the enumeration of these fixes by memoizing logical building blocks.

The Challenge of MCS Enumeration

The standard approach to finding MCSes involves repeatedly querying a Boolean Satisfiability (SAT) solver to determine if a specific subset of constraints is satisfiable. Given that SAT solving is NP-complete, these calls are the primary computational bottleneck. In a typical run, an algorithm might execute thousands of nearly identical queries.

Previous optimization efforts focused on "unsatisfiable core caching," which stores entire sets of conflicting constraints to avoid redundant proofs of failure. However, these cores are often large and highly specific to a particular search state. The authors identified that caching the reasons why specific variables are forced to take certain values—rather than just the fact that a whole set is broken—could yield broader benefits.

Premise Set Caching

The researchers introduced Premise Set (PS) Caching and integrated it into the LBX (Literal-Based eXtractor) algorithm.

What is a Premise Set?

A premise set $P$ is a subset of clauses that logically entails a specific literal $l$ (denoted $P \models l$). If the clauses in $P$ are satisfied, $l$ must necessarily be true. By caching these implications, the algorithm can skip expensive SAT solver calls.

Implementation and Integration

The authors developed a lightweight implementation using a "clause-PS occurrence list." This allows for extremely fast cache lookups: to check if a premise set $P$ is active, the algorithm only needs to verify that none of the clauses in $P$ are currently falsified.

LBX is particularly well-suited for this technique because it naturally identifies "backbone" literals—literals that must be true in any valid solution. When the SAT solver discovers a new backbone literal, the algorithm extracts the corresponding premise set and adds it to the cache for future use.

Experimental Evaluation

The approach was evaluated using 811 "hard" benchmark instances from hardware verification and automated reasoning. The primary metric was the number of MCSes enumerated within a 1800-second time limit.

Comparison of LBX with and without Premise Set caching.

Key Results

The empirical results demonstrate that Premise Set Caching provides a substantial performance boost:

  1. Direct Improvement: As shown in the comparison between standard LBX and LBX with PS caching, the caching mechanism consistently allows the algorithm to find more MCSes within the same time frame.
  2. Superiority over Core Caching: LBX with PS caching (LBX-CACHE) outperformed the previous state-of-the-art "core caching" approach (ELS) on the vast majority of benchmarks.
  3. High Efficiency: Cache hit rates reached up to 90% in many instances, effectively eliminating 9 out of 10 SAT solver calls.
  4. Scalability: The lightweight nature of the cache ensured that maintenance overhead remained negligible relative to the computational savings.
Performance comparison between PS caching (LBX) and core caching (ELS).

Conclusion

Premise Set Caching represents a significant advancement in MCS enumeration. By focusing on atomic logical implications rather than aggregate unsatisfiable cores, the technique achieves remarkable speedups and high hit rates. Future work may explore hybrid caching strategies and sophisticated cache eviction policies to further enhance scalability on even larger datasets.

Summary updated

BibTeX
@inproceedings{previti2018premise,
  author = {Alessandro Previti and Carlos Mencía and Matti Järvisalo and João Marques-Silva},
  title = {{Premise Set Caching for Enumerating Minimal Correction Subsets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12213},
}
Figure