Researchers have a new answer to the oldest complaint about AI explainability tools: the explanations are guesses dressed up as insight.
The method, called probabilistic linear explanations, generates sparse, anchored linear models that describe why a machine learning model made a specific prediction, for both classification and regression tasks. It works by mapping data points onto a Boolean hypercube, which lets it capture the size and direction of each feature's contribution while sticking to a fixed "budget" of features, denoted k. The researchers prove that finding the mathematically optimal version of this explanation is NP-PP-hard for neural networks, so they built two workarounds instead: a mixed integer programming approach that finds provably optimal answers on real data, and a faster polynomial-time algorithm with formal approximation guarantees.
This matters because today's dominant explanation tools, like LIME and MAPLE, don't actually promise you get a clean, human-sized explanation. They approximate feature importance without guaranteeing the result stays sparse or anchored to the actual prediction, which is how you end up with explanations listing thirty features when a person can hold about seven in their head. In testing, the new approach hit lower relevance error than those baselines while satisfying both constraints by construction, not by luck.
Still, this is a preprint, not a shipped tool, and the hard part of explainability was never the math. Even a provably optimal five-feature explanation is only useful if the five features it names are ones a person can actually reason about.