TL;DR
Modern SAT solvers learn many clauses to speed up problem-solving, but too many clauses can slow them down. This paper investigates various "unlearning" strategies for clause removal in the state-of-the-art KISSAT solver, finding that while keeping all clauses is detrimental, periodically removing all clauses is surprisingly effective for satisfiable instances. Crucially, retaining "critical" clauses (those most likely to be useful) is more important than the specific ranking metric used.
What Problem Does This Paper Address?
Conflict-Driven Clause Learning (CDCL) is a cornerstone of modern SAT solvers. When a solver encounters a conflict (a contradiction in its current assignment of truth values), it learns a new clause that encodes this conflict. This learned clause helps prune the search space by preventing the solver from exploring similar unsatisfiable branches in the future. While effective, CDCL solvers can accumulate a vast number of learned clauses over time. This massive database of clauses can become a performance bottleneck, as algorithms for managing and querying these clauses (e.g., for propagation or conflict analysis) become slower with larger datasets. The problem, therefore, is how to selectively remove learned clauses ("unlearn") to maintain solver efficiency without sacrificing its problem-solving power. This paper explores various strategies for achieving this balance.
Methods
The authors evaluate several clause unlearning strategies within the KISSAT SAT solver, a state-of-the-art solver. Their experimental setup involves modifying the unlearning function (as outlined in Algorithm 1) and comparing different configurations against a baseline KISSAT version. Key strategies investigated include:
- No-unlearn: Retaining all learned clauses.
- Unlearn-all: Periodically removing all learned clauses.
- Activity-based unlearning: Removing clauses based on how often they have been used in conflict analysis (similar to the MINISAT approach).
- LBD (Literal Block Distance) based unlearning: Retaining "critical" clauses, defined by a low LBD score (a measure of clause complexity related to decision levels).
- Size-based unlearning: Retaining clauses below a certain size threshold.
- Used flag: A binary indicator of whether a clause has been used recently in conflict analysis. This is combined with other strategies.
- Dynamic tier systems: Using adaptive thresholds for identifying critical clauses based on LBD or size.
The experiments systematically vary these parameters, such as the fraction of clauses to remove (f) and the criteria for identifying critical clauses.
Datasets
The experiments were conducted on the 400 problems from the SAT Competition 2024. These problems are categorized into satisfiable (SAT) and unsatisfiable (UNSAT) instances. The authors note that they use a subset of these problems for specific analyses (e.g., 96 shared UNSAT instances). No new benchmarks were introduced.
Key Insights and Ideas
- The "unlearn-all" paradox: Surprisingly, for satisfiable instances, periodically removing all learned clauses (unlearn-all) yields performance close to state-of-the-art. This suggests that for satisfiable problems, learned clauses primarily serve as local guidance towards a model and are not essential for long-term problem-solving.
- Critical clauses are key: Retaining "critical" clauses (defined by low LBD or small size) is paramount for good performance, especially on unsatisfiable instances. The specific metric (LBD vs. size) for defining "critical" is less important than the act of retaining them.
- The "used" flag is a strong indicator: Clauses that have been recently used in conflict analysis are highly valuable. Incorporating a "used" flag consistently improves the performance of most unlearning strategies, acting as a crucial secondary criterion.
- Activity is less important than expected: Activity-based unlearning, a common strategy in older solvers like MINISAT, performs poorly in modern KISSAT compared to other methods. This suggests that simple usage counts are not as predictive of future usefulness as more sophisticated metrics like LBD or recent usage.
- Dynamic thresholds are not always better: While intuitive, dynamic tier systems for identifying critical clauses did not outperform static thresholds in their experiments, suggesting that absolute clause quality (absolute LBD/size) is more critical than relative quality within a dynamic context.
Key Results
- Unlearn-all on SAT: Achieved near state-of-the-art performance on satisfiable instances.
- No-unlearn impact: Keeping all clauses (no-unlearn) significantly degrades performance on both SAT and UNSAT instances, with a notable increase in memory usage.
- Activity-based unlearning: Performed worse than the baseline on both SAT and UNSAT instances, mirroring the performance of unlearn-all on SAT and no-unlearn on UNSAT.
- Critical clauses (LBD/size) vs. Rank: Retaining clauses up to size 10 or with LBD <= 3 provided the best results, outperforming rank-based strategies.
- "Used" flag impact: Combining the "used" flag with critical clause retention significantly improved performance across configurations. For example,
critical@size<=10 + usedsolved 328 instances, compared to 322 forcritical@size<=10alone. - Overall best configurations: Combinations like
critical@size<=10 + usedandcritical@lbd<=3 + usedconsistently performed very well, often surpassing the baseline.
Limitations and Future Work
- Benchmark diversity: The authors acknowledge that the diversity of solved instances might be limited by the benchmark set, suggesting future work could explore extensions to other SAT solvers and benchmark sets.
- Scheduling: The paper mentions that the scheduling of unlearning calls (how often it occurs) is a complex factor that was kept constant for most experiments and is deferred for further analysis.
- Dynamic tier limitations: The dynamic unlearning scheme did not achieve the same performance as static schemes, indicating that absolute clause quality might be more important than relative quality.
- Future work: The authors suggest investigating whether these findings generalize to other SAT solvers and benchmark sets. They also note that observed outliers in LBD distributions from previous SAT competition benchmarks warrant further investigation.
Summary updated