The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy

arXiv:2605.02177v1 Announce Type: cross Abstract: Pearl's causal hierarchy shows that observational, interventional, and counterfactual queries are qualitatively distinct. We ask a quantitative version of this question: how many additional bits are needed to specify higher-rung causal answers once lower-rung answers are known? We formalize this via query-class description length, the Kolmogorov complexity of the answer oracle induced by an SCM for a class of queries. Our main construction gives binary acyclic SCMs whose observational distribution has constant description length, while the single-variable interventional answer oracle has description length Theta(n^2). A degree-sensitive upper bound shows that finite-gate-schema SCMs of indegree d have observational-interventional gap at most O(nd log(en/d) + n log n), making the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under arepsilon-accurate total-variation descriptions for every fixed arepsilon < 1/4. At the next rung, the full hard-do interventional oracle can still leave a Theta(n) counterfactual description gap. A general ambiguity-to-bits theorem and Shannon analogue show that these gaps equal the logarithm of residual higher-rung ambiguity up to lower-order terms.

Source: arXiv cs.LG | 2026-05-05