📊 statistics

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

This paper quantifies the information-theoretic gaps between Pearl's causal hierarchy levels by demonstrating that specifying higher-rung causal answers (interventions and counterfactuals) can require significantly more bits than lower-rung answers (observational data), with proven quadratic separations for interventions and linear separations for counterfactuals in specific structural causal models.

Original authors: Seyed Morteza Emadi

Published 2026-05-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Seyed Morteza Emadi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a complex machine, like a giant, mysterious clockwork toy. You can look at it from the outside, you can push some buttons, and you can even ask, "What would have happened if I had pushed a different button?"

This paper asks a very specific question: How much extra information do you need to answer the "What if?" questions if you already know the answers to the "What happens?" questions?

The authors, led by Seyed Morteza Emadi, use a concept called "bits" (the basic units of information) to measure this gap. They found that for certain types of machines, the gap is massive. Knowing what the machine does doesn't tell you much about why it does it, or what it would do in a different scenario.

Here is a breakdown of their findings using simple analogies:

1. The Three Levels of Understanding (Pearl's Ladder)

The paper builds on a famous idea by Judea Pearl that causal reasoning has three rungs:

Rung 1 (Observation): "What do I see?" (e.g., The light is on.)
Rung 2 (Intervention): "What happens if I do X?" (e.g., If I flip the switch, will the light stay on?)
Rung 3 (Counterfactual): "What would have happened if I had done Y?" (e.g., If I had flipped the switch yesterday, would the light be on now?)

The paper proves that you cannot simply "calculate" the answer to Rung 2 or 3 just by looking at Rung 1. But how much more information is missing?

2. The "Hidden Blueprint" Analogy

The authors created three specific types of "machines" (mathematical models) to test this. In all three cases, the machine looks exactly the same from the outside (Rung 1). It's like looking at a black box that always outputs the same pattern of lights.

However, inside the box, the wiring is different. To figure out the wiring (which determines the answers to Rung 2 and 3), you need a lot of extra data.

Case A: The Tree Family (The "Family Tree" Analogy)

The Setup: Imagine a group of people where everyone copies their parent's behavior. If the "root" person is happy, everyone is happy. If they are sad, everyone is sad.
The Observation: From the outside, you just see that everyone is always happy or always sad together. You can't tell who is the parent of whom.
The Gap: To figure out the family tree (who is the parent of whom), you need to push buttons (interventions). The amount of information needed to describe the tree grows with the size of the family. It's like needing a map to navigate a forest. The paper shows this gap grows roughly as $n \log n$ (where $n$ is the number of people).

Case B: The Bipartite Graph (The "Party Guest" Analogy)

The Setup: Imagine a party with two groups of people, Group A and Group B. Everyone in Group A copies the host. Everyone in Group B only turns on their light if all their specific friends in Group A are on.
The Observation: From the outside, the lights are either all off or all on. It looks like a simple switch.
The Gap: But inside, there is a secret "friendship map" (a graph) connecting Group A to Group B. There are billions of possible friendship maps that all look the same from the outside.
The Result: To figure out the exact friendship map, you need to push buttons on Group A and see who in Group B reacts. The authors found that the amount of extra information needed here is quadratic ( $n^2$ $n^{2}$ ).
- Analogy: If you have 100 people, the "Tree" gap might be like reading a 700-page book. The "Party" gap is like reading a 10,000-page book. The complexity explodes as the system gets bigger.

Case C: The Modular XOR (The "Secret Code" Analogy)

The Setup: Imagine a row of pairs of switches. Some pairs are wired so they always match; others are wired so they always flip.
The Observation & Intervention: No matter how you flip the switches or look at the results, the pairs look identical. Even if you know every possible outcome of pushing buttons, you still can't tell the difference.
The Gap: The only way to know the secret wiring is to ask a "Counterfactual" question: "If I had flipped switch A while keeping the internal noise the same, what would happen?"
The Result: Even with perfect knowledge of all button-pushing results, you still need extra information (about $n$ bits) to solve the counterfactual puzzle.

3. The "No Free Lunch" for Learners

The paper makes a crucial point for anyone trying to use AI or data to predict the future: You cannot learn the "Why" just by watching the "What."

If you have a machine where the hidden wiring is chosen randomly from billions of possibilities, and you only get to watch it run (observational data), you are completely blind to the wiring.

The Analogy: Imagine trying to guess the secret recipe of a cake just by tasting the final product. If two different recipes (one with chocolate, one with vanilla) produce a cake that tastes exactly the same, no amount of tasting will ever tell you which recipe was used.
The Math: The authors prove that if you only have observational data, your chance of guessing the correct "interventional" outcome is essentially zero (like guessing a coin flip in a room with a billion coins).

4. Why This Matters (In the Paper's Context)

The paper doesn't talk about medical cures or self-driving cars directly. Instead, it focuses on the mathematical limits of information.

It quantifies the "Causal Gap": Before this, we knew there was a gap between observation and causation. Now we know exactly how wide that gap is in bits.
It proves "Order-Optimality": They showed that for dense, complex systems, the gap is as big as it possibly can be (quadratic). You can't compress the information any further.
It warns against overconfidence: If an AI model is trained only on observational data (what happened in the past), it fundamentally lacks the information to answer "What if?" questions for complex systems. It's not a bug in the AI; it's a law of information.

Summary

Think of the universe as a giant, hidden puzzle.

Observation is looking at the finished puzzle picture.
Intervention is taking a piece out to see what's underneath.
Counterfactual is asking, "What if I had taken a different piece out?"

This paper proves that for many complex puzzles, looking at the picture (Observation) tells you almost nothing about the pieces underneath. To understand the mechanics, you need a massive amount of extra information—specifically, an amount that grows with the square of the system's size. You cannot deduce the hidden mechanics just by watching the show; you have to know the script.

Technical Summary: The Causal Description Gap

Problem Statement

Pearl's causal hierarchy establishes that observational, interventional, and counterfactual queries are qualitatively distinct, with the Causal Hierarchy Theorem proving that higher-rung queries cannot generally be answered from lower-rung information. However, existing literature treats this non-identifiability as a binary obstruction: either a higher-rung answer is determined by lower-rung data, or it is not.

This paper asks a quantitative version of this question: How many additional bits of information are required to specify a higher-rung causal answer once the lower-rung answers are known? The authors formalize this "causal description gap" to measure the residual information needed to resolve ambiguity when identification fails.

Methodology

The authors introduce a framework based on Kolmogorov complexity to quantify the information content of causal answer oracles.

Query-Class Description Length: For a Structural Causal Model (SCM) $M$ and a query class $Q$ (e.g., observational, single-node interventional, counterfactual), the description length $DL(Q; M)$ is defined as the Kolmogorov complexity of the answer oracle $Ans_Q(M)$ , conditioned on the system size $n$ .
Causal Description Gap: The gap $\Delta(Q_2 | Q_1; M)$ is the conditional Kolmogorov complexity of the higher-rung answer given the lower-rung answer:
$\Delta(Q_2 | Q_1; M) := K(Ans_{Q_2}(M) \mid Ans_{Q_1}(M), n)$
Ambiguity-to-Bits Principle: The paper establishes a general theorem linking description gaps to the size of the ambiguity set. If a lower-rung answer $a$ is consistent with $N$ distinct higher-rung answer oracles, the description gap is at least $\log_2 N$ (up to lower-order terms). This holds in both worst-case (Kolmogorov) and average-case (Shannon entropy) settings.

The authors construct specific families of binary, acyclic SCMs to instantiate these gaps, demonstrating that the gaps can scale polynomially with the system size $n$ .

Key Contributions and Results

1. Observational–Interventional Separations

The paper constructs SCM families where the observational distribution has constant description length ( $O(1)$ ), yet the interventional answer oracle requires significantly more bits.

Rooted-Tree Construction ( $\Theta(n \log n)$ ):
- Setup: Variables form a hidden rooted tree where the root is random and children copy parents.
- Result: All trees produce the same observational distribution (perfect correlation). However, single-node interventions reveal the descendant sets, uniquely identifying the tree structure.
- Gap: The gap is $\Theta(n \log n)$ , matching the information required to encode a labeled tree (via Prüfer sequences). This is order-optimal for SCMs with bounded indegree ( $d=O(1)$ ).
Bipartite-Graph Construction ( $\Theta(n^2)$ ):
- Setup: A hidden bipartite graph $G$ between layers $A$ and $B$ . Layer $A$ copies the root; Layer $B$ computes AND-gates based on edges in $G$ .
- Result: Observationally, all graphs yield the same distribution (all 0s or all 1s). Interventions on layer $A$ nodes reveal their neighbors in layer $B$ , effectively decoding the adjacency matrix of $G$ .
- Gap: The gap is $\Theta(n^2)$ (specifically $\approx m^2$ where $n=2m+1$ ). This is order-optimal for dense mechanisms where indegree $d = \Theta(n)$ .
- Robustness: This quadratic separation persists even under $\epsilon$ -accurate total-variation descriptions for any fixed $\epsilon < 1/4$ .
Degree-Sensitive Optimality:
The authors prove a general upper bound for finite-gate-schema SCMs with indegree $d$ :
$\Delta_{2|1} \le O\left( nd \log \frac{en}{d} + n \log n \right)$
This confirms that the $\Theta(n \log n)$ tree construction is optimal for bounded degree, and the $\Theta(n^2)$ bipartite construction is optimal for dense degree.

2. Counterfactual Separation

Even with full knowledge of all "hard-do" interventional distributions (the full interventional oracle), counterfactual queries may remain ambiguous.

Modular-XOR Construction ( $\Theta(n)$ ):
- Setup: $m$ independent modules, each being either a "no-effect" mechanism (independent variables) or an "XOR" mechanism ( $Y = X \oplus U$ ).
- Result: Both mechanisms produce identical observational and interventional distributions. However, they differ in counterfactuals: under the no-effect mechanism, $Y$ remains unchanged if $X$ is intervened upon; under XOR, $Y$ flips.
- Gap: The gap between the full interventional oracle and the counterfactual oracle is $\Theta(n)$ , corresponding to the hidden string $s \in \{0,1\}^m$ determining the mechanism type.

3. Learning-Theoretic Consequences

The paper derives a "no-free-lunch" result for observational learning. In the bipartite family, since all mechanisms share the same observational distribution, the mutual information between the hidden graph and any observational dataset is zero. Consequently:

No observational learner can identify the interventional oracle with probability better than random guessing ( $2^{-m^2}$ ).
Any predictor based solely on observational data has an expected absolute error of at least $1/4$ for interventional queries.

Significance and Claims

The paper claims to transform Pearl's qualitative hierarchy into a quantitative information hierarchy. Its primary significance lies in:

Refining Non-Identifiability: It moves beyond the Boolean question of "is it identifiable?" to a precise measure of "how much information is missing?"
Order-Optimal Bounds: It provides explicit constructions showing that the information gap can scale quadratically with system size ( $\Theta(n^2)$ ) for dense mechanisms and linearly ( $\Theta(n)$ ) for counterfactuals, even when observational data is perfect.
Information-Theoretic Limits: It demonstrates that these gaps are not artifacts of computational hardness or finite data; they are fundamental information-theoretic barriers. Even with infinite observational data, the residual ambiguity remains, necessitating interventions to close the gap.
General Principle: The "Ambiguity-to-Bits" theorem unifies these results, showing that the description gap is fundamentally the logarithm of the residual ambiguity set size.

The authors note that their constructions are adversarial (binary, acyclic, potentially violating positivity or faithfulness) to demonstrate that observational adequacy alone imposes no small causal-description bound without further structural assumptions. They suggest that future work should investigate how sparsity, noise, or faithfulness assumptions might shrink these residual ambiguities.