On the Theoretical Limits of Post-Hoc Explanation Faithfulness

Post-hoc explanation methods are widely used to interpret machine-learning models, yet their faithfulness may be fundamentally limited by the trade-off between explanation simplicity and information preservation. Recent theoretical work establishes lower bounds on the error of explanations substantially simpler than the models they explain, and rate-distortion analyses show that finding optimal sparse explanations is $NP^{PP}$-complete. Whether these limits are observable in practice, or whether common methods approach the attainable optimum, remains unknown. We present an empirical audit connecting these theoretical results to measurable explanation performance. We operationalize the bounds with estimable proxies (compression-based approximations of Kolmogorov complexity, mutual-information estimates from multiple estimators, and intrinsic-dimension estimates of the data support), validate the pipeline on synthetic functions of known complexity, and, on problems small enough for exhaustive enumeration, compute exact optimal explanations as an estimation-free reference. In a pilot on planted sparse Boolean functions (d = 10, k = 3) with random-forest classifiers, TreeSHAP and LIME recovered the planted support on 100% of test instances and achieved 99.9% of the exhaustively optimal distortion reduction, yet retained residual distortion 1.4 to 1.7 times the per-instance optimum; contrary to our pre-registered prediction, the two methods performed equivalently. The ongoing audit extends to standard tabular benchmarks and tests whether explanation complexity is governed by the intrinsic rather than the ambient dimension of the data. All procedures are pre-registered, and negative results will be retained.