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

arXiv: https://arxiv.org/abs/2604.16689 · HTML: https://mlsanity.com/paper/2604.16689/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 17 Apr 2026.

## Builds on (most cited first, 21 of 21)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [ByT5: Towards a token-free future with pre-trained byte-to-byte models](https://mlsanity.com/paper/2105.13626/) (2021)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [On the Robustness of Interpretability Methods](https://mlsanity.com/paper/1806.08049/) (2018)
- [On the (In)fidelity and Sensitivity for Explanations](https://mlsanity.com/paper/1901.09392/) (2019)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Information Dropout: Learning Optimal Representations Through Noisy Computation](https://mlsanity.com/paper/1611.01353/) (2016)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [TokenSHAP: Interpreting Large Language Models with Monte Carlo Shapley Value Estimation](https://mlsanity.com/paper/2407.10114/) (2024)
- [Why don't people use character-level machine translation?](https://mlsanity.com/paper/2110.08191/) (2021)
- [Large Vocabulary Size Improves Large Language Models](https://mlsanity.com/paper/2406.16508/) (2024)
- [The Limits of AI Explainability: An Algorithmic Information Theory Approach](https://mlsanity.com/paper/2504.20676/) (2025)

## Abstract (arXiv)

Masking-based post-hoc explanation methods, such as KernelSHAP and LIME, estimate local feature importance by querying a black-box model under randomized perturbations. This paper formulates this procedure as communication over a query channel, where the latent explanation acts as a message and each masked evaluation is a channel use. Within this framework, the complexity of the explanation is captured by the entropy of the hypothesis class, while the query interface supplies information at a rate determined by an identification capacity per query. We derive a strong converse showing that, if the explanation rate exceeds this capacity, the probability of exact recovery necessarily converges to one in error for any sequence of explainers and decoders. We also prove an achievability result establishing that a sparse maximum-likelihood decoder attains reliable recovery when the rate lies below capacity. A Monte Carlo estimator of mutual information yields a non-asymptotic query benchmark that we use to compare optimal decoding with Lasso- and OLS-based procedures that mirror LIME and KernelSHAP. Experiments reveal a range of query budgets where information theory permits reliable explanations but standard convex surrogates still fail. Finally, we interpret super-pixel resolution and tokenization for neural language models as a source-coding choice that sets the entropy of the explanation and show how Gaussian noise and nonlinear curvature degrade the query channel, induce waterfall and error-floor behavior, and render high-resolution explanations unattainable.