CS Paper Radar

Partial Information Decomposition When Some Sources Are Known: A Source Chain Rule and a No-Go Theorem

Aaron J. Gutknecht

cs.IT ·submitted 2026-10-24 15:32 UTC · v1
theory

Abstract

Partial information decomposition (PID) splits the information that several sources carry about a target into atoms, distinguished by which collections of sources give access to them. We ask how such a decomposition should behave when some of the sources are already known. The access structure of the atoms suggests one answer: discard the atoms that the known sources provide and regroup the rest according to which further sources unlock them. The classical construction of conditional information suggests another: recompute the decomposition under the conditional distributions and average. We show that the two answers agree, atom by atom, exactly when redundant information obeys a source chain rule, an analogue of the chain rule of mutual information: when the same sources are added to several collections, the enlarged collections share everything the added sources provide and, beyond that, exactly what the original collections share once the added sources are known. The rule divides established measures of redundant information, so that adopting or rejecting it genuinely narrows the choice of measure. Our main result is a no-go theorem: for three or more sources, the source chain rule and local positivity, the requirement that all atoms be nonnegative, cannot hold together in any PID.

Comment
23 pages, 3 figures, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Between Hi-Fi and MMI: the overlap of redundancy and synergy in partial information decomposition

cs.IT physics.data-anstat.ME ·2026-11-05 ·Niels Van Santen, Yves Rosseel, Daniele Marinazzo
similarity 0.69
Abstract

Partial information decomposition (PID) splits the information that two sources carry about a target into redundant, unique and synergistic parts, with nonnegative decompositions lying on a segment where redundancy measures are bounded by the positive part of the co-information and the smaller source-target information. We parameterize this segment by the overlap, the common excess of redundancy and synergy over their net balance, and show that for many of the named PID measures, their redundancy can be written as the largest positive part of the co-information over a set of reference distributions. This common form induces an ordering of those PIDs on the segment. With the smallest redundancy and synergy and the largest unique atoms of any nonnegative PID, the information-theoretic version of Hi-Fi, a feature-importance method, is the zero-overlap end of the segment for two sources, with the maximum overlap bound given by the minimum mutual information (MMI) PID. We introduce, by splitting the co-information into a pairwise maximum- entropy part and the third-order connected information, a PID that sits at zero overlap except when pairwise redundancy and triadic synergy coexist. For three or more sources the bivariate results hold on every pair of merged source groups, and among all nonnegative solutions of the lattice equations MMI and Hi-Fi still give the smallest and largest unique atoms but zero overlap on all pairs at once is often unattainable. Two inequalities across pairs are necessary in general and sufficient for three sources. For identity targets zero overlap is possible exactly when the sources' information diagram is nonnegative. In random three- and four-source distributions zero overlap on all pairs fails in 21-100% of the cases.

0.15

Existence of an infinite family of substrates satisfying all the postulates of integrated information theory, exclusion included, with arbitrarily large integrated information

cs.IT q-bio.NC ·2026-09-09 ·A. Mayeux
similarity 0.57
Abstract

For infinitely many sizes we exhibit a cycle of binary units, each taking the exclusive-or of itself and its two clockwise neighbours, that is a complex in every state, no proper subsystem being more integrated, and whose integrated information grows as two raised to a power quadratic in the number of units.

0.24

Learning Rules, Memorizing Facts: An Information-Theoretic View of Hallucination

cs.IT ·2026-10-12 ·Gengze Xu, Anxin Guo, Yifei Hu, Xiangyu Wu, Yong Liu +1 more
similarity 0.56
Abstract

Understanding the relationship between generalization and hallucination requires clarifying the role of memorization. We study this relationship from an information-theoretic perspective through a Selector-Density Conditional Mutual Information (CMI) framework. In the sparse random-fact limit, a uniformly bounded information budget per fact forces a nonvanishing false-positive rate at recall bounded away from zero, even when all facts are observed during training. In a rules-and-facts setting, we decompose model-data mutual information into rule learning, atomic-fact memory, and excess memorization, revealing competition between rule learning and factual memory even without excess memorization. A joint budget bound quantifies the resulting constraint on atomic hallucination under perfect atomic recall. Moreover, an additive Gaussian model shows that maintaining high recall for atomic and composite facts incurs false positives even under optimal data mixing. Finally, controlled relational experiments hint how training exposure, rule complexity, and model capacity shape these trade-offs.

0.23

Constant-Loss Round-Preserving Direct Sums for Information Complexity

cs.CC cs.IT ·2026-10-11 ·Haoran Wang
theory similarity 0.55
Abstract

Strong direct-sum theorems relate the information needed to solve many independent instances of a communication problem to the information needed for one instance. For Gap-Majority composition, an optimal information bound was previously known, but preserving the number of communication rounds incurred an additional logarithmic loss. We prove a round-preserving Gap-Majority lemma with constant additive information loss, independent of both the number of instances and the number of rounds. More generally, we establish a variance direct-sum theorem for additive square-integrable observables over product distributions. For protocols with a bounded number of terminal answer values, the extracted single-coordinate protocols preserve the round budget, and their average information cost is at most the original information cost divided by the number of coordinates, plus a term depending only on the answer alphabet and the allowed variance loss. The proof uses centered counterfactual conditional means and a global variance amortization argument. Rather than encoding absolute conditional means for every possible terminal answer, we encode the information not already determined by the common view. The total squared innovation is controlled by a telescoping variance potential, yielding an information loss independent of the number of coordinates. We also derive same-round mean-square estimation bounds for arbitrary terminal outputs.

0.58

Residual-Information Generalization Bounds Under Selective Privacy: Extended Version

cs.IT ·2026-10-11 ·Amirreza Zamani, Parastoo Sadeghi, Mikael Skoglund
theory similarity 0.55
Abstract

Information-theoretic generalization bounds usually control dependence on the task sample, whereas selective privacy may constrain only a different, private coordinate. We study i.i.d. pairs $(X,Y)$, where a learner observes $(X^n,Y^n)$, leaks at most $ε_n$ nats about $X^n$, and incurs loss on $Y$. A chain-rule transfer converts this mismatched constraint into the closed-form universal certificate $I(W;Y^n)\leq\min\{nH(Y),nH(Y\mid X)+ε_n\}$. Combining the certificate with mutual-information generalization yields a bound governed by residual task uncertainty and normalized privacy leakage. We derive complementary task-compression and individual-sample refinements, identify a sharp obstruction showing why selective privacy alone need not give a vanishing certificate, and invert the bound to obtain the exact leakage allowance for a prescribed generalization tolerance. We prove exact information-level achievability for deterministic-task and independent-residual source families and show that the resulting $\sqrt{ε_n/n}$ generalization rate is tight up to a universal constant. We also give a fixed-horizon adaptive application in which conditional leakage costs add.

0.28

Learning from a Mixture of Information Sources

cs.GT econ.TH ·2026-09-27 ·Nicole Immorlica, Brendan Lucier, Yaroslav Mukhin, Clayton Thomas, Ruqing Xu
similarity 0.55
Abstract · Extended abstract to appear in WINE 2026 (The Conference on Web and Internet Economics)

We often learn from multiple sources that convey information in different ways. How informative is it to know the source of a signal, and how is this informativeness shaped by the distribution of sources? We extend the standard (binary-state, binary-signal) Blackwell experiment model by introducing a commonly known distribution over signaling schemes, representing the distribution of information sources. We compare learning under two information models: source-aware, where decision makers observe a signaling scheme and its realization (e.g., raw reviews, search results), and source-blind, where only the signal realization is observed (e.g., aggregate ratings, LLM-generated summaries). We show that a mean-preserving spread in the distribution of signaling schemes translates into Blackwell dominance for source-aware decision makers, implying they are "risk-loving" in information sources. In contrast, it has no impact on source-blind decision makers. When learning from repeated draws of signaling schemes, source-blind decision makers learn more slowly. However, as long as the average signaling scheme is $\varepsilon$ away from being completely uninformative, source-blind learning can match source-aware learning by using at most $O(1/\varepsilon)$ times more data.

0.28

Choosing What to Observe: Higher-Order Obstructions in Horn Abduction

cs.LO ·2026-10-23 ·Yukun Yang
similarity 0.55
Abstract · 9 pages, 1 figure

An explanation may exist in every complete context yet be impossible to select from the information observed. We study this distinction in finite propositional Horn abduction with integrity constraints. Observations are sufficient when each report admits one hypothesis set that is consistent and entails the manifestation in every compatible context. We characterize sufficiency by minimal context families with no common explanation. Their variable spans form a canonical hypergraph whose transversals are exactly the sufficient observation sets. The characterization recovers classical discernibility for unique explanations and supports composition across independent components. Minimal obstructions have unbounded cardinality even for acyclic rules, while rectangular explanation families admit a tight bound given by their largest choice domain. With circuit-defined contexts, sufficiency is $Π_3^P$-complete and selecting at most $k$ observable variables is $Σ_4^P$-complete, already for unrestricted contexts and acyclic rules. The selection reduction makes observation choices enforce globally fixed existential commitments. Explicit contexts reduce both tasks to NP-complete problems; tabulated explanation families make sufficiency polynomial. These results connect explanatory choice, information requirements, and representation cost.

0.31

Revisiting Shannon's Source Coding Theorem with Distributional Uncertainty under the Nonlinear Expectation Theory

cs.IT ·2026-08-17 ·Wen-Xuan Lang, Shaoshi Yang, Jianhua Zhang, Zhiming Ma
theory similarity 0.54
Abstract · 6 pages, 2 figures

In classical information theory, a source is modeled by a single, precisely known probability distribution. However, in the increasingly complex communication networks full of unanticipated, nonstationary, and heterogeneous random events, the assumption of precise and well-defined probability distributions to describe random variables appears somewhat idealized. Therefore, it is important to characterize the uncertainty of distributions of source messages, subject to relaxing the assumption of deterministic probability models for analyzing information sources in information theory. Based on the nonlinear expectation theory, a novel axiomatical system that extends classical probability theory, this paper investigates the information sources whose distributions themselves are uncertain, and refers to them as uncertain-distribution sources. We generalize the fundamental concept information entropy to nonlinear information entropy, which describes the measurement of the amount of information contained in a uncertain-distribution source. By using the strong law of large numbers under sublinear expectation, we establish a nonlinear source coding theorem, which not only shows that the nonlinear information entropy is the upper bound for the infimum of achievable coding rate of uncertain-distribution sources under the maximum error probability criterion, but also determines a cluster point of the coding rate of uncertain-distribution sources under the minimum error probability criterion. Our findings reveal that the introduction of nonlinear expectation theory allows for a more comprehensive understanding of information sources.

0.22