When a machine learning model denies someone a loan or flags a medical scan, the most natural question is "why?" Formal explainability has spent years trying to answer that question with mathematical rigor. The dominant approach finds a small subset of features that, if fixed, guarantee the model's output does not change. These are called abductive explanations, and they come with hard logical guarantees. The problem is that they are often too large to be useful. A rule that fixes 15 features to explain a loan denial is technically correct but cognitively useless. Humans can hold about four or five interacting variables in working memory before cognitive overload sets in.
Probabilistic explanations were invented to fix this. Instead of demanding a guarantee that holds for all instances matching the explanation, they accept a small probability of failure. A probabilistic explanation says: "these two features explain the prediction, and among all instances sharing those two features, the model agrees with this prediction 98% of the time." The 2% failure rate is explicitly quantified. This trades absolute certainty for conciseness, and it matches how humans actually reason about evidence.
But probabilistic explanations have a significant limitation. They work only for categorical classification, where the model outputs a class label. In regression, where the model outputs a continuous number, the subset-based formulation breaks down. Knowing which features matter does not tell you how much they matter or whether they push the prediction up or down. A feature subset is a binary mask that shows support but not magnitude or direction.
Frédéric Koriche, Jean-Marie Lagniez, and Chi Tran at the University of Artois present a framework that fixes this. Their paper, "Probabilistic Linear Explanations," published as an extended version of a UAI 2025 Best Paper Award winner, unifies probabilistic explainability across classification and regression through sparse, anchored linear models. The key insight is that by representing explanations as sparse weight vectors rather than feature subsets, you capture magnitude and direction while retaining the cognitive simplicity of a small number of features.
From subsets to sparse linear functions
The framework maps every data instance to the Boolean hypercube {-1, +1}^d, where each coordinate represents an interpretable literal (a binary proposition like "Income >= 65k" or "Credit History < 10 yrs"). A linear explanation is a weight vector w in R^d that satisfies two constraints. First, anchoring: w dot x equals f(x), meaning the linear explanation exactly reproduces the black-box prediction at the reference instance. Second, sparsity: the number of nonzero coefficients in w is at most k, the user's cognitive budget.
This formulation strictly generalizes subset-based explanations. A feature subset S induces a weight vector that is nonzero only on S, but a sparse linear vector can assign different magnitudes and signs to features within S. In a regression task, say predicting a loan interest rate, a subset explanation tells you which features matter. A linear explanation tells you that a low debt-to-income ratio contributes -3 percentage points while a short credit history contributes +11, the two partially compensating. This is information that no subset-based explanation can convey.
The anchoring condition w dot x = f(x) is not new. It appears as the "local accuracy" property in Lundberg and Lee's SHAP framework and as the efficiency axiom in Shapley value explanations. What is new is enforcing this condition jointly with a hard sparsity budget. LIME uses LASSO regularization to encourage sparsity but does not guarantee a specific budget. MAPLE has no sparsity mechanism at all, assigning a weight to every feature. KernelSHAP satisfies anchoring but produces dense explanations, since Shapley values assign a value to every feature. None of these methods can guarantee that the explanation has at most k features while remaining anchored at the reference instance.
The optimization problem and its hardness
The central question is: among all k-sparse, anchored linear explanations, which one best approximates the black-box model? The paper measures this using two error metrics.
Relevance error measures the expected loss between the black-box model's output and the linear explanation's output, conditioned on instances that agree with the reference on the explanation's support. This is the right metric because it directly answers: "how often does this explanation fail?" But it is computationally intractable. The paper proves that minimizing relevance error is NP^PP-hard when the underlying model is a neural network. This places the problem well beyond the reach of any exact algorithm, even in principle.
Fidelity error measures the unconditional expected loss between the linear model and the black-box model over instances drawn from a local distribution. This is the standard metric used by LIME and MAPLE. It is easier to optimize because it does not involve conditioning, but it does not directly measure what the user cares about: how often the explanation is wrong.
The paper bridges these two metrics through a parameterized family of local distributions. The distribution over instances z is proportional to exp(-sigma/2 times the Hamming distance between z and the reference x), where sigma is a concentration parameter controlling locality. When sigma is zero, the distribution is uniform over the Boolean hypercube. When sigma is large, instances cluster tightly around x. For this family, the paper proves that the relevance error of any k-sparse explanation is at most (1 + e^{-sigma})^k times its fidelity error. The multiplicative factor remains small when sigma is large (meaning the explanation is local) or k is small (meaning the explanation is concise).
This bound is the theoretical core of the paper. It says that minimizing fidelity error is a reasonable proxy for minimizing relevance error, with a quantified approximation ratio that depends on the locality parameter and the sparsity budget. The tighter the neighborhood (larger sigma), the closer fidelity tracks relevance.
Two algorithms: exact and polynomial-time
The empirical optimization problem minimizes the average fidelity error over m sampled instances, subject to anchoring and sparsity constraints. This is a sparse regression problem, which is NP-hard in general. The paper offers two solution approaches with complementary trade-offs.
The Mixed Integer Programming (MIP) formulation encodes the problem exactly. Binary indicator variables select which features enter the explanation, and continuous variables determine their weights. The anchoring constraint and sparsity budget are encoded as linear constraints. MIP solvers can find provably optimal solutions for small and medium-sized problems. The paper shows that a sample size polynomial in k, 1/epsilon, and log d suffices for the empirical solution to approximate the true relevance error well, with the sample complexity independent of the locality parameter sigma. This is a practical advantage: MIP does not need more data as the explanation becomes more local.
The Iterative Hard Thresholding (IHT) algorithm is the polynomial-time alternative. At each iteration, it computes a gradient step, then projects onto the intersection of the k-sparsity constraint and the anchoring hyperplane. The projection is exact and computable in O(d log d + k^2) time. IHT produces k-sparse explanations whose relevance error is, with high probability, at most (1 + e^{-sigma})^k times (c times v* + epsilon), where c > 1 is a multiplicative approximation factor that depends on k and sigma, and v* is the optimal empirical fidelity.
The trade-off between the two methods is governed by the locality parameter sigma. In the localized regime (large sigma), the relevance bound is tight and MIP is preferred because its sample complexity does not grow with sigma. IHT faces a double penalty: its sample complexity grows as cosh^4(sigma/2), roughly e^{2sigma} for large sigma, and its approximation factor worsens as e^sigma. In the intermediate regime, where sigma is large enough for the relevance bound to be informative but small enough to keep sampling costs and approximation factors moderate, IHT becomes the practical choice. It is by far the fastest explainer and remains effective at every scale.
What the experiments show
The experimental evaluation benchmarks MIP and IHT against LIME and MAPLE on both classification and regression tasks across multiple datasets. The results are organized around three observations.
Admissibility comes first. MAPLE consistently exceeds the sparsity budget k and frequently violates the anchoring condition. LIME satisfies the sparsity budget but systematically deviates from anchoring, failing to reproduce the black-box prediction at the reference instance. Neither method satisfies both constraints by construction. The proposed methods do, by definition. This is not a minor point. An explanation that does not anchor at the reference instance is explaining a different prediction than the one the user asked about.
LIME's apparent advantage is an anchoring artifact. Because LIME operates over a strictly larger hypothesis space (it does not enforce anchoring), it sometimes achieves a lower empirical fidelity error. But the measurements show that this advantage results directly from the anchoring deviation. When LIME's explanation does not reproduce f(x), it can fit the local data more loosely, reducing the empirical loss on sampled instances while being wrong about the actual prediction. Once anchoring is enforced, the advantage disappears.
Relevance and fidelity do not rank explainers the same way. Fidelity error measures how well the linear model fits sampled data. Relevance error measures how often the explanation is actually wrong. These are different quantities, and optimizing one does not guarantee optimizing the other. The proposed methods consistently outperform LIME on relevance across variations in k, sigma, and m. Between MIP and IHT, relevance rarely differs by more than a few hundredths. The choice between them is essentially computational: MIP certifies optimality within seconds on small and medium benchmarks but loses this certificate on the largest ones, while IHT scales to high-dimensional datasets where MIP becomes intractable.
The experiments also vary the sparsity budget, locality parameter, and sample size to validate the theoretical predictions. As sigma increases (tighter locality), the relevance bound tightens and the gap between fidelity and relevance shrinks. As k increases (more features allowed), both errors decrease but the approximation factor grows. As m increases (more samples), the empirical fidelity converges to the true fidelity, and the relevance bound becomes more reliable. These trends match the theory precisely.
Limitations and open directions
The framework has several acknowledged limitations. The Boolean hypercube representation requires mapping continuous or categorical features to binary literals in advance, following standard practice in model-agnostic explainability. This binarization discards information and can produce explanations that are less expressive than the original feature space allows. The paper notes this as a direction for future work: extending the framework beyond binarized domains.
The hardness result (NP^PP-hard for neural networks) means that exact optimization is out of reach for large-scale problems. The MIP formulation handles moderate dimensions but becomes intractable for very high-dimensional feature spaces. IHT is polynomial-time but its approximation guarantee degrades as the explanation becomes more local. In the highly localized regime, the sample complexity and approximation factor may become impractical.
The anchoring constraint, while theoretically motivated, can be restrictive in practice. If the black-box model is highly nonlinear at the reference instance, a sparse linear function that anchors there may not generalize well to nearby instances. The paper addresses this by tuning the locality parameter sigma, but finding the right balance between locality (which tightens the relevance bound) and sample efficiency (which requires more data for tighter neighborhoods) remains a practical challenge.
The framework treats the black box as entirely opaque, accessible only through value queries. This is a strength for model-agnostic applicability but a limitation for white-box settings where gradient information or model structure could be exploited for more efficient optimization. The paper does not explore hybrid approaches that combine query-based optimization with gradient-based methods.
What this means for explainability practitioners
The practical message is clear. If you are explaining a regression model, or if you need explanations that capture both the magnitude and direction of feature contributions, the existing toolset (LIME, MAPLE, KernelSHAP) does not provide the guarantees you need. LIME violates anchoring. MAPLE violates sparsity. KernelSHAP produces dense explanations. None of them come with provable relevance bounds.
The proposed methods fill this gap. For moderate-dimensional problems, MIP provides provably optimal explanations with certified quality. For high-dimensional problems, IHT provides fast approximate explanations with quantifiable approximation guarantees. Both methods satisfy anchoring and sparsity by construction, which is not true of any standard baseline.
The theoretical contribution, connecting relevance error to fidelity error through the locality parameter, gives practitioners a principled way to choose between explanation locality and explanation quality. Setting sigma large makes the relevance bound tight but requires more samples. Setting sigma small makes the bound loose but reduces data requirements. The paper provides the formulas to make this trade-off explicit.
For anyone building explainability systems for high-stakes applications, this framework offers something rare: mathematical guarantees on explanation quality that hold for both classification and regression, with computable bounds on the probability that the explanation is wrong. That is a meaningful advance over the current state of the art.
Read the paper on arXiv