The Query Channel: Information-Theoretic Limits of Masking-Based Explanations

2026-04-12 · Source: cs.AI updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, extended

Summary

Masking-based post-hoc explanation methods like KernelSHAP and LIME are fundamentally limited by information-theoretic principles, according to new research. This work models explanation extraction as communication over a "query channel," where the latent explanation is a message and each masked evaluation is a channel use. It introduces concepts like explanation complexity (entropy of the hypothesis class) and query interface information rate (identification capacity). A strong converse theorem proves that if the explanation rate exceeds this capacity, exact recovery probability converges to one in error. Conversely, an achievability result shows a sparse maximum-likelihood decoder can reliably recover explanations when the rate is below capacity. Experiments reveal an "algorithmic gap" where information theory allows reliable explanations, but standard convex surrogates (Lasso, OLS) fail. The analysis also identifies a critical resolution for super-pixels and tokenization, beyond which explanations become information-theoretically unattainable due to channel degradation from noise and nonlinear curvature.

Key takeaway

For AI Scientists and Research Scientists designing or evaluating masking-based XAI, you must consider the information-theoretic limits of your query channel. If your explanation's entropy exceeds the channel's capacity, reliable recovery is mathematically impossible, regardless of computational power. You should carefully balance explanation resolution, sparsity, and query budget to remain within information-theoretically feasible regimes. Persistent instability or error floors often signal that you are operating beyond the channel's capacity, not merely facing algorithmic deficiencies.

Key insights

Masking-based explanations are fundamentally limited by information-theoretic rate-capacity tradeoffs, dictating recoverability.

Principles

• Reliable explanation requires explanation entropy to be below query channel capacity.
• Increasing explanation resolution beyond a critical point makes recovery impossible.
• Sparsity significantly reduces the query budget needed for reliable recovery.

Method

Formulate explanation as communication over a noisy "query channel," quantifying explanation complexity via entropy and query information via parameter-identification capacity. Compare explanation rate R=H(M)/T with C^(S).

In practice

• Evaluate query budget T against T_IT for reliable decoding.
• Adjust super-pixel resolution to stay below critical resolution d_crit.
• Consider noise and model non-linearity as channel degradations.

Topics

• Explainable AI
• Information Theory
• Masking-based Explanations
• Query Channel
• Sparse Recovery
• Critical Resolution

Best for: AI Scientist, Research Scientist

Related on AIssential

• Towards Intrinsic Interpretability of Large Language Models:A Survey of Design Principles and Architectures — Intrinsic interpretability builds transparency directly into LLM architectures to enhance trustworthiness and safety.
• Yes it's just doing compression. No it's not the diss you think it is. — Optimizing language models for next-word prediction via log-likelihood is a form of data compression, which can be linked to understanding.
• An Information-Theoretic Criterion for Efficient Data Synthesis — Synthetic data is effective only when external signals keep the training loop "information-open."
• Stabilising Explainability Fragility in Cybersecurity AI: The Impact and Mitigation of Multicollinearity in Public Benchmark Datasets — Multicollinearity in cybersecurity datasets inflates AI explanation variance, making attributions non-identifiable and impacting XAI trustworthiness.
• Cycle-Consistent Search: Question Reconstructability as a Proxy Reward for Search Agent Training — Cycle-Consistent Search trains search agents without gold supervision by reconstructing the original question from search trajectories.
• On Hallucinations in Inverse Problems: Fundamental Limits and Provable Assessment Methods — AI hallucinations in inverse problems are not just model artifacts but stem from the problem's inherent ill-posedness.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.