The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity

• URL: http://arxiv.org/abs/2605.21492v1
• Date: Wed, 08 Apr 2026 10:11:45 GMT
• Title: The Attribution Impossibility: No Feature Ranking Is Faithful, Stable, and Complete Under Collinearity
• Abstract summary: No feature ranking can be simultaneously faithful, stable, and complete when features are collinear.<n>We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems.<n>The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: No feature ranking can be simultaneously faithful, stable, and complete when features are collinear. For collinear pairs, ranking reduces to a coin flip. We prove this impossibility, quantify it for four model classes, resolve it via ensemble averaging (DASH), and machine-verify it with 305 Lean 4 theorems. We characterize the complete attribution design space: exactly two families of methods exist -- faithful-complete methods (unstable, with rankings that flip up to 50% of the time) and ensemble methods like DASH (stable, reporting ties for symmetric features) -- and no method lies outside this dichotomy. The impossibility is quantitative: the attribution ratio diverges as 1/(1-rho^2) for gradient boosting, is infinite for Lasso, and converges for random forests. DASH (Diversified Aggregation of SHAP) is provably Pareto-optimal among unbiased aggregations, achieving the Cramer-Rao variance bound with a tight ensemble size formula. In a survey of 77 public datasets, 68% exhibit attribution instability. Switching to conditional SHAP does not escape the impossibility when features have equal causal effects. The framework includes practical diagnostics -- a Z-test workflow and single-model screening tool -- and has direct consequences for fairness auditing: SHAP-based proxy discrimination audits are provably unreliable under collinearity. The design space theorem, diagnostics, and impossibility are mechanically verified in Lean 4 (305 theorems from 16 axioms, 0 sorry) -- to our knowledge, the first formally verified impossibility in explainable AI.

Related papers

• What Accuracy and Gradient Cosine Miss: Evaluating Feedback Alignment via Scale Stability, Reference Validity, and Depth Utility [48.10132234701036]
  We propose a diagnostic evaluation protocol based on three checks -- scale stability, reference validity, and depth utility -- together with per-layer rather than aggregate cosine reporting.<n>Across multiple architectures and methods, our protocol identifies all failures with wide calibration margins.
  arXiv  Detail & Related papers  (2026-06-19T06:04:17Z)
• Distributional Energy-Based Models for Uncertainty-Aware Structured LLM Reasoning [40.342912574072024]
  Large Language Models produce structured outputs such as travel plans or code solutions.<n>Individual reasoning steps may appear correct while the output as a whole violates budgets, fails test cases, or contradicts earlier deductions.<n>We propose a learned quality scorer with deterministic analytical constraint penalties for verifying structured LLM outputs.
  arXiv  Detail & Related papers  (2026-05-15T17:08:27Z)
• When Are Trade-Off Functions Testable from Finite Samples? [4.706977254727891]
  We study finite-sample inference for the trade-off function of two unknown probability distributions.<n>By inverting the test, we also obtain simultaneous confidence bands for the whole trade-off curve.
  arXiv  Detail & Related papers  (2026-05-11T16:07:48Z)
• The Pokémon Theorem and other Fairness Impossibility Results [6.291388054687868]
  We show that fairness criteria are linear constraints on conditional mean embeddings.<n>We also show that unequal base rates make the law of total expectation overdetermine those constraints.
  arXiv  Detail & Related papers  (2026-05-09T23:37:10Z)
• PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data [0.0]
  We introduce PAIR-CI, a nonparametric conditional independence (CI) test that restores calibration by integrating multiple imputation directly into the inferential procedure.<n>A provably consistent variance estimator jointly accounts for uncertainty arising from cross-validation and multiple imputation.
  arXiv  Detail & Related papers  (2026-05-06T12:34:37Z)
• Exact Structural Abstraction and Tractability Limits [0.0]
  Exact correctness depends only on the induced classes $s sim_R simation' iff mathrmAdm_R(s)$.<n>Decision, search, approximation, statistical, randomized horizon, and distributional guarantees all reduce to this same quotient-recovery problem.
  arXiv  Detail & Related papers  (2026-04-08T17:59:47Z)
• The Digital Twin Counterfactual Framework: A Validation Architecture for Simulated Potential Outcomes [0.0]
  Digital Twin Counterfactual Framework (DTCF)<n>Five-level validation architecture converts unfalsifiable claim that simulator produces correct counterfactuals into falsifiable tests against observable data.<n> decomposition separates causal quantities into those that are marginally validated.<n>Joint causal claims become explicitly assumption-indexed.
  arXiv  Detail & Related papers  (2026-04-01T19:04:15Z)
• Ensemble-Based Uncertainty Estimation for Code Correctness Estimation [36.53771380869671]
  We propose Ensemble Semantic Entropy (ESE), which estimates uncertainty by evaluating the consistency of samples aggregated across an ensemble of models.<n>Experiments on LiveCodeBench demonstrate that ESE correlates more strongly with program correctness than single-model semantic entropy.<n>We also propose a cascading test-time scaling framework Cas, which maintains performance while reducing FLOPs by 64.9% compared to single-model scaling.
  arXiv  Detail & Related papers  (2026-03-28T02:37:36Z)
• Hallucinations Live in Variance [0.0]
  Benchmarks measure whether a model is correct. They do not measure whether a model is reliable.<n>Hallucinations live in variance: they arise when semantically equivalent prompts activate inconsistent internal pathways, producing divergent outputs.<n>We formalize this through Semantic Stability (SS), measured via Paraphrase Consistency (PC@k): generate k paraphrases, greedy decode each, compute mode agreement.<n>We show that a dense Qwen3-0.6B agrees with itself only 23.8% of the time; at 32% sparsity, agreement jumps to 55.9%.
  arXiv  Detail & Related papers  (2026-01-11T20:41:51Z)
• Detecting Unobserved Confounders: A Kernelized Regression Approach [46.52607207396279]
  Kernel Regression Confounder Detection (KRCD) is a novel method for detecting unobserved confounding in nonlinear observational data under single-environment conditions.<n>Test statistic whose significant deviation from zero indicates unobserved confounding.<n>Experiments on synthetic benchmarks and the Twins dataset demonstrate that KRCD not only outperforms existing baselines but also achieves superior computational efficiency.
  arXiv  Detail & Related papers  (2026-01-01T04:26:02Z)
• Solving Inequality Proofs with Large Language Models [42.667163027148916]
  Inequality proving is crucial across diverse scientific and mathematical fields.<n>This makes it a demanding frontier for large language models (LLMs)<n>We release IneqMath, an expert-curated dataset of Olympiad-level inequalities.
  arXiv  Detail & Related papers  (2025-06-09T16:43:38Z)
• Towards Self-Supervised Covariance Estimation in Deep Heteroscedastic Regression [102.24287051757469]
  We study self-supervised covariance estimation in deep heteroscedastic regression.<n>We derive an upper bound on the 2-Wasserstein distance between normal distributions.<n>Experiments over a wide range of synthetic and real datasets demonstrate that the proposed 2-Wasserstein bound coupled with pseudo label annotations results in a computationally cheaper yet accurate deep heteroscedastic regression.
  arXiv  Detail & Related papers  (2025-02-14T22:37:11Z)
• SimPro: A Simple Probabilistic Framework Towards Realistic Long-Tailed Semi-Supervised Learning [49.94607673097326]
  We propose a highly adaptable framework, designated as SimPro, which does not rely on any predefined assumptions about the distribution of unlabeled data. Our framework, grounded in a probabilistic model, innovatively refines the expectation-maximization algorithm. Our method showcases consistent state-of-the-art performance across diverse benchmarks and data distribution scenarios.
  arXiv  Detail & Related papers  (2024-02-21T03:39:04Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  We provide the first type-I-error and expected-rejection-time guarantees under general non-data generating processes. We show how to apply our results to inference on parameters defined by estimating equations, such as average treatment effects.
  arXiv  Detail & Related papers  (2022-12-29T18:37:08Z)
• Distribution-free binary classification: prediction sets, confidence intervals and calibration [106.50279469344937]
  We study three notions of uncertainty quantification -- calibration, confidence intervals and prediction sets -- for binary classification in the distribution-free setting. We derive confidence intervals for binned probabilities for both fixed-width and uniform-mass binning. As a consequence of our 'tripod' theorems, these confidence intervals for binned probabilities lead to distribution-free calibration.
  arXiv  Detail & Related papers  (2020-06-18T14:17:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.