aiqbench analysis
This research quantifies the information-theoretic gap between Pearl's causal hierarchy rungs, demonstrating that specifying counterfactual answers can require quadratically more bits than observational data in worst-case structural causal models. By formalizing these separations via Kolmogorov complexity and query-class description length, the study establishes fundamental limits on how efficiently higher-order causal knowledge can be compressed from lower-order distributions. These findings are critical for understanding the intrinsic complexity of causal inference tasks in machine learning systems.
The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy
arXiv:2605.02177v2 Announce Type: replace-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 answers a structural causal model (SCM) gives to a class of queries, with system size given. Our main construction gives acyclic SCMs on $n$ binary variables whose common observational distribution has constant description length, while single-variable intervention answers can require $\Theta(n^2)$ additional bits. For SCMs with independent noises, fixed finite gate-schema and noise libraries, and at most $d$ parents per variable, a degree-sensitive upper bound gives an observational-interventional gap of at most $O(nd\log(en/d)+n\log n)$. This makes the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under $\varepsilon$-accurate total-variation descriptions for every fixed $\varepsilon<1/4$. At the next rung, even knowing every hard-intervention distribution can leave a $\Theta(n)$ counterfactual description gap; a masked-parity construction extends this to $\Theta(n^2)$. These separation rates hold in the worst case and with high probability under uniform hidden parameters. A general ambiguity-to-bits theorem and Shannon analogue, together with explicit encodings, show that the gaps in our constructions equal the logarithm of residual higher-rung ambiguity up to lower-order terms.
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 answers a structural causal model (SCM) gives to a class of queries, with system size given. Our main construction gives acyclic SCMs on $n$ binary variables whose common observational distribution has constant description length, while single-variable intervention answers can require $\Theta(n^2)$ additional bits. For SCMs with independent noises, fixed finite gate-schema and noise libraries, and at most $d$ parents per variable, a degree-sensitive upper bound gives an observational-interventional gap of at most $O(nd\log(en/d)+n\log n)$. This makes the quadratic construction order-optimal in the dense regime and a rooted-tree construction order-optimal for bounded indegree. The quadratic separation persists under $\varepsilon$-accurate total-variation descriptions for every fixed $\varepsilon<1/4$. At the next rung, even knowing every hard-intervention distribution can leave a $\Theta(n)$ counterfactual description gap; a masked-parity construction extends this to $\Theta(n^2)$. These separation rates hold in the worst case and with high probability under uniform hidden parameters. A general ambiguity-to-bits theorem and Shannon analogue, together with explicit encodings, show that the gaps in our constructions equal the logarithm of residual higher-rung ambiguity up to lower-order terms.
Accepted at NeurIPS 2026. 26 pages (10 main text, appendices A to E)
Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Information Theory (cs.IT); Machine Learning (cs.LG)
arXiv:2605.02177 [stat.ML]
(or arXiv:2605.02177v2 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2605.02177 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 335 words