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

• URL: http://arxiv.org/abs/2604.16689v1
• Date: Fri, 17 Apr 2026 20:46:25 GMT
• Title: The Query Channel: Information-Theoretic Limits of Masking-Based Explanations
• Abstract summary: Masking-based post-hoc explanation methods, such as KernelSHAP and LIME, estimate local feature importance by querying a black-box model.<n>This paper formulates this procedure as communication over a query channel, where the latent explanation acts as a message.
• Score: 0.17188280334580197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Noisy-Channel Minimum Bayes Risk Decoding [58.87954687016989]
  Minimum Bayes Risk (MBR) decoding yields more robust and higher-quality text generation than maximum a posteriori (MAP) decoding.<n>There exists a discrepancy in the design: hypothesis selection calculates expected utility scores conditioned on given pseudo-references.<n>It is important to consider both hypothesis-to-reference and reference-to-hypothesis directional effects.
  arXiv  Detail & Related papers  (2026-07-06T15:14:13Z)
• Neural Information Causality [0.0]
  We develop a framework called neural information causality (Neural-IC)<n>We show that Neural-IC is an operational diagnostic for query leakage, precision leakage, and episode-specific memory.<n>We also provide an exact one-bit classical RAC benchmark, showing explicitly that the relevant quantum enhancement is not total information beyond the bottleneck.
  arXiv  Detail & Related papers  (2026-05-10T04:25:11Z)
• Rate-Distortion Analysis of Compressed Query Delegation with Low-Rank Riemannian Updates [0.5729426778193398]
  We study compressed query delegation (CQD)<n>CQD is a constrained program with a query-budget functional and an oracle modeled as a noisy operator.
  arXiv  Detail & Related papers  (2026-01-02T14:04:58Z)
• Topic Identification in LLM Input-Output Pairs through the Lens of Information Bottleneck [0.0]
  We develop a principled topic identification method grounded in the Deterministic Information Bottleneck (DIB) for geometric clustering.<n>Our key contribution is to transform the DIB method into a practical algorithm for high-dimensional data by substituting its intractable KL divergence term with a computationally efficient upper bound.
  arXiv  Detail & Related papers  (2025-08-26T20:00:51Z)
• Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization [35.16750653336608]
  We introduce the likelihood ratio regularized quantile regression algorithm, which combines the pinball loss with a novel choice of regularization.<n>We show that the LR-QR method has coverage at the desired level in the target domain, up to a small error term.<n>Our experiments demonstrate that the LR-QR algorithm outperforms existing methods on high-dimensional prediction tasks.
  arXiv  Detail & Related papers  (2025-02-18T16:46:44Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Cycles of Thought: Measuring LLM Confidence through Stable Explanations [53.15438489398938]
  Large language models (LLMs) can reach and even surpass human-level accuracy on a variety of benchmarks, but their overconfidence in incorrect responses is still a well-documented failure mode. We propose a framework for measuring an LLM's uncertainty with respect to the distribution of generated explanations for an answer.
  arXiv  Detail & Related papers  (2024-06-05T16:35:30Z)
• Decomposing Uncertainty for Large Language Models through Input Clarification Ensembling [69.83976050879318]
  In large language models (LLMs), identifying sources of uncertainty is an important step toward improving reliability, trustworthiness, and interpretability. In this paper, we introduce an uncertainty decomposition framework for LLMs, called input clarification ensembling. Our approach generates a set of clarifications for the input, feeds them into an LLM, and ensembles the corresponding predictions.
  arXiv  Detail & Related papers  (2023-11-15T05:58:35Z)
• What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalization [111.55277952086155]
  We study In-Context Learning (ICL) by addressing several open questions. We show that, without updating the neural network parameters, ICL implicitly implements the Bayesian model averaging algorithm. We prove that the error of pretrained model is bounded by a sum of an approximation error and a generalization error.
  arXiv  Detail & Related papers  (2023-05-30T21:23:47Z)
• Scalable Vector Gaussian Information Bottleneck [19.21005180893519]
  We study a variation of the problem, called scalable information bottleneck, in which the encoder outputs multiple descriptions of the observation. We derive a variational inference type algorithm for general sources with unknown distribution; and show means of parametrizing it using neural networks.
  arXiv  Detail & Related papers  (2021-02-15T12:51:26Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)

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.