# Efficiently Explaining CSPs with Unsatisfiable Subset Optimization

arXiv: https://arxiv.org/abs/2105.11763 · HTML: https://mlsanity.com/paper/2105.11763/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 82 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 8 of 8)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Survey on Computational Propaganda Detection](https://mlsanity.com/paper/2007.08024/) (2020)
- [Explainable Planning](https://mlsanity.com/paper/1709.10256/) (2017)
- [A framework for step-wise explaining how to solve constraint satisfaction problems](https://mlsanity.com/paper/2006.06343/) (2020)
- [Finding Good Proofs for Description Logic Entailments Using Recursive Quality Measures (Extended Technical Report)](https://mlsanity.com/paper/2104.13138/) (2021)

## Abstract (arXiv)

We build on a recently proposed method for explaining solutions of constraint satisfaction problems. An explanation here is a sequence of simple inference steps, where the simplicity of an inference step is measured by the number and types of constraints and facts used, and where the sequence explains all logical consequences of the problem. We build on these formal foundations and tackle two emerging questions, namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently. To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms. The method is also applicable to other problems that require finding cost-optimal unsatiable subsets. We specifically show that this approach can be used to effectively find sequences of optimal explanation steps for constraint satisfaction problems like logic grid puzzles.