Research map / Probabilistic and scientific modeling / Causal discovery
The Causal Description Gap: Information-Theoretic Separations Across Pearl's Hierarchy
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines query-class description length (Kolmogorov complexity of answer oracles) for Pearl's hierarchy and shows binary SCM constructions with constant observational description length but Theta(n log n), Theta(n^2) interventional and Theta(n) counterfactual gaps.
Problem
How many additional bits are needed to specify higher-rung causal answers (interventional, counterfactual) once lower-rung (observational, interventional) answers are known, quantitatively across Pearl's causal hierarchy.
Approach
Measure causal information gaps as conditional Kolmogorov complexity of the answer oracle induced by an SCM; hide a graph or hidden bits in mechanisms that are indistinguishable observationally (or under all hard interventions) so the residual ambiguity size lower-bounds the gap, with matching upper-bound encodings.
Key results
- Rooted-tree SCMs with constant observational description length have interventional gap Theta(n log n) (Cayley count n^{n-1}).
- Bipartite-graph SCMs give interventional gap Theta(n^2) (m^2 bits, m=(n-1)/2), robust to epsilon-TV error for epsilon<1/4.
- Modular-XOR SCMs: even full hard-do interventional oracle leaves a Theta(n) counterfactual gap (2^m ambiguity).
Surprising findings
- Observational data with any sample size carries zero Shannon information about the hidden graph in the bipartite family, so observational learners cannot beat 2^{-m^2} guessing.
Limitations
- Constructions are adversarial binary acyclic SCMs without positivity or faithfulness assumptions.
- Kolmogorov complexity is uncomputable; bounds are about existence/counting rather than practical encodings.
- Upper bounds are restricted to finite-gate-schema classes; general SCMs not covered.
Experimental setup
Metrics: description length (Kolmogorov complexity) conditional description gap
Builds on: Pearl's causal hierarchy Causal Hierarchy Theorem Cayley's formula Kolmogorov complexity
Closest papers by meaning
- From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy (ICLR 2025 · similarity 0.87)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.83)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.83)
- COLD: Causal reasOning in cLosed Daily activities (NeurIPS 2024 · similarity 0.83)
- Spectra of Cardinality Queries over Description Logic Knowledge Bases (AAAI 2025 · similarity 0.83)
- Operads for compositional reasoning in LLMs (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.