Sparse and Faithful Local Explanations with Piecewise Linear Surrogates

Yixin Wang, Yucheng DongICML 2026 · OpenReview

TL;DR: PL-LIME improves upon the popular LIME framework by replacing simple linear surrogates with instance-anchored piecewise linear functions. By decoupling feature estimation from a new, objective-consistent sparsification strategy, it delivers local explanations that are significantly more faithful to the underlying black-box model and far more stable across different samples.

The Challenge of Local Explanations

As machine learning models like deep neural networks and gradient-boosted trees (such as XGBoost) become increasingly complex, they operate as "black boxes"—highly accurate but opaque to human interpretation. Local Interpretable Model-agnostic Explanations (LIME) has become a standard tool for peering inside these models. LIME explains individual predictions by fitting a simple, interpretable linear model to a small neighborhood of data points generated around a specific instance.

However, standard LIME suffers from two major structural limitations:

  1. The Linearity Trap: LIME assumes that within a small local neighborhood, a feature's effect can be modeled as a single straight line. In reality, black-box models often exhibit heterogeneous or nonlinear ("curvy") behavior even at a local level.
  2. Misaligned Sparsity: To keep explanations interpretable, LIME selects a small number of important features. It typically does this using one method (like Lasso) and then fits the final explanation using another (like Ridge regression). This mismatch between the selection and fitting objectives often leads to unstable explanations, where minor changes in the local sampling result in wildly different feature rankings.

Introducing PL-LIME

To address these limitations, the authors propose PL-LIME, a two-stage sparse local explanation framework designed to ensure objective consistency and capture nonlinear local effects.

Piecewise Linear Surrogates

Instead of assuming a single slope per feature, PL-LIME utilizes two linear segments that meet—or are "anchored"—at the specific instance being explained. This approach adds just one extra degree of freedom per feature but allows the surrogate model to capture "bends" in the decision logic. For example, a feature might have a positive effect on one side of the data point and a negative effect on the other.

Decoupled yet Consistent Sparsification

To ensure stability, PL-LIME follows two core design principles. First, it estimates the local effects without sparsity constraints. Second, it applies a nonnegative shrinkage procedure (conceptually similar to the Nonnegative Garrote) to scale those estimated effects. This ensures that the feature selection process is directly aligned with the modeling objective, preventing the distortion of local effects that frequently plagues standard LIME.

Variance-Based Importance

Because the local effect is no longer a single coefficient, the authors introduce a new metric to quantify feature importance. This metric is based on the local variance of the piecewise functions, providing a more nuanced and accurate ranking than simple linear coefficients.

Key Insights

A fundamental insight of this research is that locality is granular. A local neighborhood is not a monolith; by partitioning it into sub-regions via piecewise functions, we can observe exactly how a model's logic shifts as we move away from the point of interest.

The paper mathematically proves that LIME’s single coefficient is essentially a weighted average of the true local slopes. Consequently, if a model has a sharp "V" shape locally, LIME might average it out to a flat line, entirely missing the feature's effect. PL-LIME's piecewise approach naturally resolves this "averaging" problem.

Experimental Validation

The researchers evaluated PL-LIME across a variety of settings, including a 20-dimensional synthetic regression task (to test ground-truth recovery) and several real-world UCI datasets (Breast Cancer, Ionosphere, Wine, Adult, Iris, and Bike Sharing). The explanations were tested against Random Forests, XGBoost, and Neural Networks to confirm the method's model-agnostic capabilities.

  • Higher Fidelity: PL-LIME consistently achieved higher local fidelity (measured by $R^2_w$) than LIME across all datasets. In some instances, it successfully captured sharp transitions—such as decision thresholds in the Breast Cancer dataset—that LIME completely ignored.
  • Superior Stability: By ensuring that the sparsity step uses the same objective as the fitting step, PL-LIME solves the "jitter" problem. The method demonstrated massive gains in rank stability. For example, on the Adult dataset under low sparsity, feature ranking stability increased by 51% compared to LIME.
  • Qualitative Nuance: In the Bike Sharing dataset, PL-LIME correctly identified a non-monotonic temperature effect, showing that bike usage increases with warmth but drops off during extreme heat. Restricted to a straight line, LIME could only depict a purely increasing trend.

Limitations and Future Work

While highly effective for tabular data, PL-LIME has limitations. The computational cost of piecewise modeling scales with the number of features. For extremely high-dimensional data, such as raw image pixels, a pre-processing step for feature screening or dimensionality reduction is necessary.

Additionally, the current default implementation uses a single "knot" anchored at the instance being explained. While this serves as a minimal yet principled extension, highly complex local regions might benefit from multiple knots. Developing an adaptive strategy for knot placement remains a promising direction for future research.

Summary updated

Abstract

Local post-hoc explanations are widely used to understand black-box models on tabular data, with Local Interpretable Model-agnostic Explanations (LIME) being a popular approach. LIME approximates a black-box model using a sparse linear surrogate in a local neighborhood, implicitly assuming feature-wise linear homogeneity. However, this assumption often fails when local feature effects exhibit heterogeneous or nonlinear behaviors, resulting in unfaithful and unstable explanations. Moreover, LIME relies on a decoupled feature selection procedure that is not aligned with the surrogate modeling objective, further exacerbating instability under local sampling. To address these limitations, we propose PL-LIME, a two-stage sparse local explanation framework that ensures objective consistency across stages. PL-LIME models feature-wise local effects using instance-anchored piecewise linear functions, providing a minimal yet principled extension beyond linear surrogates under a fixed explanation budget. Sparsity is enforced through a decoupled nonnegative shrinkage procedure that directly scales the estimated local effects, improving stability while preserving interpretability. Experiments on synthetic and real-world datasets demonstrate that PL-LIME achieves higher local fidelity and stability, and provides more reliable local explanations that capture finer-grained local effect structures than LIME.
BibTeX
@inproceedings{wang2026sparse,
  author = {Yixin Wang and Yucheng Dong},
  title = {{Sparse and Faithful Local Explanations with Piecewise Linear Surrogates}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=CxDqIqY5e9},
}
Figure