The Causal Description Gap:
Information-Theoretic Separations Across Pearl’s Hierarchy
May 04, 2026
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 \(\varepsilon\)-accurate total-variation descriptions for every fixed \(\varepsilon<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.
1 Introduction↩︎
Predictive accuracy identifies what a system does under passive observation. Causal questions go further: interventional queries (“what if I set \(X\)?”) and counterfactual queries (“what would have happened if \(X\) had been different?”). Pearl’s causal hierarchy [1] formalizes these three levels (association, intervention, counterfactual), and the Causal Hierarchy Theorem [2] shows the hierarchy is generically strict: higher-rung queries cannot in general be answered from lower-rung information. But how large is the gap? Is the additional information bounded by a constant, or can it scale with system size?
We give a quantitative answer in bits. For a structural causal model \(M\), we define query-class description lengths \(\mathrm{DL}_1(M), \mathrm{DL}_2(M), \mathrm{DL}_3(M)\) as the Kolmogorov complexities (conditional on \(n\)) of the observational, interventional, and counterfactual answer objects, and causal description gaps \(\Delta_{2|1}, \Delta_{3|2}\) as the additional bits needed conditional on the lower rung. The framework lets us treat “how much causal information is missing” as a precise quantity.
1.0.0.1 Residual information after non-identification.
Existing hierarchy and identifiability results ask whether a higher-rung answer is determined by lower-rung information. We study the residual-information problem that remains when identification fails: among all SCMs that agree on the lower-rung answer, how many bits are still needed to specify the higher-rung answer oracle? Our separations refine non-identifiability from a Boolean obstruction into a quantitative information measure. The familiar two-variable ambiguity \(X \to Y\) versus \(X \leftarrow Y\) via deterministic copy is the one-bit version of this phenomenon; our main construction scales it to \(2^{\Theta(n^2)}\) residual mechanisms, forcing a \(\Theta(n^2)\)-bit gap.
1.0.0.2 Contributions.
Framework. We turn Pearl’s qualitative hierarchy into a quantitative information hierarchy by defining query-class description length and causal description gaps: the residual bits needed to specify higher-rung answer oracles after lower-rung answers are fixed (§3).
Observational–interventional separations and degree-sensitive optimality. Explicit SCM families with constant observational description length but \(\Theta(n \log n)\) and \(\Theta(n^2)\) interventional gaps (§4–§5); a matching upper bound \(O(nd \log(en/d) + n \log n)\) for finite-gate-schema SCMs of indegree \(d\), making the tree and bipartite constructions order-optimal at \(d = O(1)\) and \(d = \Theta(n)\) (§5.1).
Finite-precision and learning consequences. The quadratic gap survives \(\varepsilon\)-accurate total-variation descriptions for every \(\varepsilon < 1/4\) (§5.2); consequently no observational learner beats the \(2^{-m^2}\) guessing rate in our family (§7.1).
Counterfactual gap and unifying ambiguity principle. Mechanisms with identical full hard-do oracles can still differ by \(\Theta(n)\) counterfactual bits (§6); a general ambiguity-to-bits theorem and Shannon analogue show these gaps equal the log of residual higher-rung ambiguity up to lower-order terms (§7).
1.0.0.3 Summary of constructions.
Table 1 previews the three SCM families used to instantiate the framework. All three have constant-bit lower-rung descriptions; the gap in each row is at least the log of the higher-rung ambiguity (Theorem 6), and is matched by an explicit upper-bound encoding.
| Family | Lower rung | Higher rung | Ambiguity | Gap | Where |
|---|---|---|---|---|---|
| Rooted trees | \(\mathsf{Obs}\) | \(\mathsf{Int}_1\) | \(n^{n-1}\) | \(\Theta(n \log n)\) | §4 |
| Bipartite graphs | \(\mathsf{Obs}\) | \(\mathsf{Int}_1\) | \(2^{m^2}\) | \(\Theta(n^2)\) | §5 |
| Modular XOR | \(\mathsf{Int}_{\mathrm{all}}\) | \(\mathsf{CF}_1\) | \(2^m\) | \(\Theta(n)\) | §6 |
2 Related Work↩︎
2.0.0.1 Pearl’s causal hierarchy.
Pearl’s three-level hierarchy [1], [3] is generically strict: the Causal Hierarchy Theorem [2] establishes non-identifiability, showing that some higher-rung queries are not functions of lower-rung information. [4] give complete identification algorithms; [5] compare frameworks. We quantify the size of the residual answer set: even for simple binary acyclic SCMs, its description length can be \(\Theta(n^2)\).
2.0.0.2 Causal discovery.
Constraint- and score-based methods identify causal graphs up to Markov equivalence from observations [6]–[8]. [9] and [10] bound the number/sample complexity of interventions for identification. We give description-length lower bounds: even with infinite observational data, the obs–int information gap is \(\Theta(n^2)\) in our family.
2.0.0.3 Description length and MDL.
Kolmogorov complexity [11], [12] and MDL [13] measure the information needed to describe objects or models. Our use is different: the compressed object is neither the dataset nor the SCM parameterization, but the answer oracle for a query class. This distinction is what enables our separations: the observational answer oracle can have constant description length even when the corresponding interventional oracle requires \(\Theta(n^2)\) bits.
2.0.0.4 Causal reasoning in AI.
Recent benchmarks find uneven causal-reasoning performance in LLMs [14], [15]; our results give one information-theoretic reason why observational predictive training alone need not induce interventional competence in worst-case structured families.
2.0.0.5 Complexity across Pearl’s hierarchy.
[16] study satisfiability across probabilistic, interventional, and counterfactual languages in Pearl’s hierarchy, proving strictly increasing computational complexity for certain languages (e.g., NP\(^{\mathrm{PP}}\), PSPACE, and NEXP completeness under addition and marginalization). Their setting assumes the SCM is given and asks how hard it is to decide whether causal statements are jointly satisfiable; we bound the information content of higher-rung answer oracles given lower-rung ones, providing complementary views on the cost of climbing the hierarchy.
3 Framework: Query-Class Description Length↩︎
3.1 Structural Causal Models↩︎
Definition 1 (Structural Causal Model). A structural causal model (SCM) on binary variables \(X_1, \ldots, X_n \in \{0,1\}\) is a tuple \(M = (G, \{f_i\}, P_U)\) where:
\(G\) is a directed acyclic graph (DAG) on \([n] := \{1, \ldots, n\}\).
\(U_1, \ldots, U_n\) are independent exogenous (noise) variables with distribution \(P_U\).
Structural equations specify each variable as a function of its parents and noise: \[X_i = f_i\bigl( (X_j)_{j \in \mathrm{pa}_G(i)}, U_i \bigr).\]
We require \(f_i\) to be computable and \(P_U\) to have rational probabilities, ensuring all quantities are well-defined.
The SCM generates data as follows: sample \((U_1, \ldots, U_n) \sim P_U\), then compute \(X_i\) in topological order. The resulting distribution \(P_M(X_1, \ldots, X_n)\) is the observational distribution.
Definition 2 (Intervention). An intervention \(\mathop{\mathrm{do}}(X_i = x)\) modifies \(M\) by replacing the equation for \(X_i\) with the constant \(X_i := x\), leaving all other equations unchanged. The resulting distribution is \(P_M^{\mathop{\mathrm{do}}(X_i = x)}\).
Interventions are the formal model of “what happens if we force \(X_i\) to take value \(x\), breaking its dependence on its natural causes.”
Definition 3 (Counterfactual). For a fixed exogenous realization \(u = (u_1, \ldots, u_n)\), the counterfactual \(X^{(i \leftarrow b)}(u)\) is the value of the entire system \((X_1, \ldots, X_n)\) when we intervene with \(\mathop{\mathrm{do}}(X_i = b)\) but use the same noise realization \(u\).
Counterfactual queries ask about joint distributions like \(P(X, X^{(i \leftarrow 0)}, X^{(i \leftarrow 1)})\): the “parallel worlds” where we observe the actual outcome and both hypothetical interventions, all computed from the same underlying noise.
3.2 Query Families: What We Need to Specify↩︎
To measure information content at each level of the hierarchy, we define what must be specified to answer all queries at that level.
Definition 4 (Query Families). For an SCM \(M\) on \(n\) variables:
Observational: \(\mathsf{Obs}(M) := P_M\), the joint distribution over \((X_1, \ldots, X_n)\).
Single-node interventional: \[\mathsf{Int}_1(M) := \Bigl( P_M,\, \bigl(P_M^{\mathop{\mathrm{do}}(X_i = 0)}, P_M^{\mathop{\mathrm{do}}(X_i = 1)}\bigr)_{i=1}^n \Bigr).\] This lists the observational distribution plus the \(2n\) single-variable interventional distributions.
Single-node counterfactual: \[\mathsf{CF}_1(M) := \Bigl( P\bigl(X, X^{(i \leftarrow 0)}, X^{(i \leftarrow 1)}\bigr) \Bigr)_{i=1}^n.\] For each variable \(i\), this is the joint distribution of the actual world \(X\) and the two counterfactual worlds under \(\mathop{\mathrm{do}}(X_i = 0)\) and \(\mathop{\mathrm{do}}(X_i = 1)\), evaluated on the same exogenous noise.
3.3 Description Lengths and the Causal Gap↩︎
Definition 5 (Kolmogorov Complexity). Fix a universal prefix-free Turing machine. The Kolmogorov complexity \(K(z)\) of a string \(z\) is the length of the shortest program that outputs \(z\). The conditional complexity \(K(z \mid w)\) is the shortest program length when \(w\) is given as auxiliary input. All equalities hold up to an additive \(O(1)\) constant.
Distributions are encoded as the string of their (rational, lowest-terms) probabilities; the choice of computable encoding affects \(K\) only by \(O(1)\).
Definition 6 (Query-Class Description Length: General Form). Let \(Q\) be a query class with a computable answer encoding \(\mathrm{Ans}_Q(M)\) (a finite string summarizing the answers to all queries in \(Q\) when posed to SCM \(M\)). The query-class description length of \(M\) with respect to \(Q\) is \[\mathrm{DL}(Q;\, M) \;:=\; K\!\bigl(\mathrm{Ans}_Q(M) \mid n\bigr).\] The conditional gap between query classes \(Q_2\) and \(Q_1\) is \[\Delta(Q_2 \mid Q_1;\, M) \;:=\; K\!\bigl(\mathrm{Ans}_{Q_2}(M) \mid \mathrm{Ans}_{Q_1}(M),\, n\bigr).\]
Specializing to the three rungs of the causal hierarchy gives the canonical lengths \(\mathrm{DL}_1(M) := K(\mathsf{Obs}(M) \mid n)\), \(\mathrm{DL}_2(M) := K(\mathsf{Int}_1(M) \mid n)\), and \(\mathrm{DL}_3(M) := K(\mathsf{CF}_1(M) \mid n)\).
Lemma 1 (Counting bound for Kolmogorov complexity). Let \(z_1, \ldots, z_N\) be \(N\) distinct strings and let \(w\) be an arbitrary auxiliary string. Then:
At least one \(z_i\) satisfies \(K(z_i \mid w) \geq \log_2 N - O(1)\).
For every \(c \geq 0\), all but at most a \(2^{-c}\) fraction of the \(z_i\) satisfy \(K(z_i \mid w) \geq \log_2 N - c - O(1)\).
The unconditional version (\(w\) empty) is the special case. We apply this lemma with \(w = n\), \(w = (P, n)\), or \(w = (I, n)\) as needed.
Proof. For any fixed \(w\), there are at most \(2^k - 1\) programs of length less than \(k\) (summing over lengths \(0, 1, \ldots, k-1\)). Setting \(k = \lfloor \log_2 N \rfloor\) shows that fewer than \(N\) strings can have conditional complexity \(K(\cdot \mid w)\) below \(\log_2 N - O(1)\), so at least one must satisfy \(K(z_i \mid w) \geq \log_2 N - O(1)\). For part (2), at most \(2^{\log_2 N - c} = N \cdot 2^{-c}\) strings can have conditional complexity below \(\log_2 N - c - O(1)\), so the remaining fraction \(\geq 1 - 2^{-c}\) satisfies the bound. ◻
Definition 7 (The Causal Description Gap). The causal description gap is the additional information needed beyond observations: \[\Delta_{2|1}(M) := K(\mathsf{Int}_1(M) \mid \mathsf{Obs}(M), n).\] Similarly, \(\Delta_{3|2}(M) := K(\mathsf{CF}_1(M) \mid \mathsf{Int}_1(M), n)\).
Lemma 2 (Hierarchy Monotonicity). \(\mathrm{DL}_1(M) \leq \mathrm{DL}_2(M) + O(1) \leq \mathrm{DL}_3(M) + O(1)\).
Proof. Direct from Definition 4: \(\mathsf{Obs}(M)\) is a component of \(\mathsf{Int}_1(M)\), and \(\mathsf{Int}_1(M)\) is a marginal of \(\mathsf{CF}_1(M)\). Both reductions are computable. ◻
Our constructions show these inequalities can be far from tight: the rest of the paper exhibits explicit families with large gaps.
Lemma 3 (Conditioning on a constant-complexity object is free). If \(K(\mathsf{Obs}(M) \mid n) = O(1)\), then \(K(\mathsf{Int}_1(M) \mid \mathsf{Obs}(M), n) = K(\mathsf{Int}_1(M) \mid n) \pm O(1)\), and consequently \(\Delta_{2|1}(M) = \mathrm{DL}_2(M) \pm O(1)\).
Proof. The upper bound \(K(\mathsf{Int}_1 \mid \mathsf{Obs}, n) \leq K(\mathsf{Int}_1 \mid n) + O(1)\) holds by ignoring the auxiliary input. For the lower bound, concatenate the constant-length program that outputs \(\mathsf{Obs}(M)\) from \(n\) with a program that outputs \(\mathsf{Int}_1(M)\) from \((\mathsf{Obs}(M), n)\): this yields \(K(\mathsf{Int}_1 \mid n) \leq K(\mathsf{Int}_1 \mid \mathsf{Obs}, n) + O(1)\). ◻
In all our constructions \(\mathrm{DL}_1 = O(1)\), so by Lemma 3 the gap \(\Delta_{2|1}\) equals \(\mathrm{DL}_2 \pm O(1)\). Chain-rule overhead is \(O(\log n)\) when conditioning on a non-trivial object; we omit it from theorem statements except where it affects the leading order.
4 Warm-Up: The Rooted-Tree Family↩︎
For intuition, structure \(n\) binary variables as a hidden rooted tree \(T\) on \([n]\) with \(X_r := U_r \sim \mathrm{Bernoulli}(1/2)\) and \(X_v := X_{\mathrm{pa}_T(v)}\) for \(v \neq r\). All trees produce the same observational distribution \(P^\star\) on \(\{0^n, 1^n\}\), so \(\mathrm{DL}_1 = O(1)\), but \(\mathop{\mathrm{do}}(X_i = 0)\) deterministically forces every descendant of \(i\) to \(0\) (non-descendants remain \(\sim \mathrm{Bernoulli}(1/2)\)), so the \(n\) single-node interventions decode the descendant sets and hence \(T\).
Theorem 1 (Rooted-tree separation). Let \(\mathcal{M}_{\mathrm{tree}}^n\) be the family of rooted-tree SCMs \(M_T\) above. All members share \(\mathsf{Obs}(M_T) = P^\star\) with \(\mathrm{DL}_1(M_T) = O(1)\). Moreover:
Upper bound. For every \(T\), \(\mathrm{DL}_2(M_T) \leq (n-1)\log_2 n + O(\log n)\).
Lower bound. For uniformly random \(T\) on \([n]\) and every \(c \geq 0\), \[\Pr\!\bigl[\Delta_{2|1}(M_T) \geq (n-1)\log_2 n - c - O(\log n)\bigr] \;\geq\; 1 - 2^{-c}.\]
Proof idea. The upper bound uses the Prüfer encoding of \(T\) (\((n-2)\log_2 n\) bits plus \(O(\log n)\) for the root); the lower bound counts: by Cayley’s formula there are \(n^{n-1}\) rooted labeled trees, and the descendant decoding shows the map \(T \mapsto \mathsf{Int}_1(M_T)\) is injective. Full proof in Appendix 9.
The bound is order-tight in the bounded-indegree regime (§5.1); allowing larger indegree raises the gap quadratically.
5 Quadratic Separation: The Bipartite-Graph Construction↩︎
We now reach the headline result. The hidden parameter is a bipartite graph \(G \subseteq A \times B\) with \(|A| = |B| = m\), encoding \(m^2\) bits of structure: a quadratic upgrade over the \(O(n \log n)\) bits of a rooted tree.
Definition 8 (Bipartite-graph SCM). Let \(n = 2m + 1\). Partition the variables into a root \(r\), layer \(A = \{a_1, \dots, a_m\}\), and layer \(B = \{b_1, \dots, b_m\}\). For a bipartite graph \(G \subseteq A \times B\), the SCM \(M_G\) has \(U_r \sim \mathrm{Bernoulli}(1/2)\) as the only random exogenous, and structural equations \[X_r := U_r, \qquad X_{a_i} := X_r \;\;\text{for all } a_i \in A, \qquad X_{b_j} := X_r \wedge \!\!\bigwedge_{(a_i, b_j) \in G}\!\! X_{a_i} \;\;\text{for all } b_j \in B,\] where the empty AND is defined as \(1\).
When \(X_r = 1\), layer \(A\) is all-ones and every AND-gate in \(B\) outputs \(1\); when \(X_r = 0\), everything is \(0\). So observationally every \(G\) yields the same distribution on \(\{0^n, 1^n\}\). But \(\mathop{\mathrm{do}}(X_{a_i} = 0)\) forces every neighbor \(b_j\) of \(a_i\) to \(0\) deterministically, while non-neighbors remain \(\sim \mathrm{Bernoulli}(1/2)\), so the \(m\) row-interventions reveal the entire \(m \times m\) adjacency matrix, distinguishing all \(2^{m^2}\) choices of \(G\). Proofs of all lemmas and theorems in this section are in Appendix 10.
Lemma 4 (All Graphs Have the Same Observations). For every bipartite graph \(G \subseteq A \times B\), we have \(\mathsf{Obs}(M_G) = P^\star\), where \(P^\star\) assigns probability \(1/2\) to \(0^n\) and \(1/2\) to \(1^n\).
Lemma 5 (Interventions Reveal the Graph). For any \(a_i \in A\) and the intervention \(\mathop{\mathrm{do}}(X_{a_i} = 0)\): \[P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}(X_{b_j} = 0) = \begin{cases} 1 & \text{if } (a_i, b_j) \in G, \\ 1/2 & \text{if } (a_i, b_j) \notin G. \end{cases}\] Thus the neighborhood \(N_G(a_i) := \{b_j : (a_i, b_j) \in G\}\) is determined by \(P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}\).
Lemma 6 (The Map \(G \mapsto \mathsf{Int}_1(M_G)\) is Injective). Different bipartite graphs yield different interventional families.
Theorem 2 (Quadratic separation: \(\Theta(n^2)\)). Let \(n = 2m+1\) and \(\mathcal{M}_{\mathrm{bip}}^n := \{M_G : G \subseteq A \times B\}\) as in Definition 8. Then:
Upper bound. For every \(G\), \(\mathrm{DL}_2(M_G) \leq m^2 + O(1)\).
Lower bound. For \(G \sim \mathrm{Unif}(2^{A \times B})\) and every \(c \geq 0\), \[\Pr\bigl[ \Delta_{2|1}(M_G) \geq m^2 - c - O(\log n) \bigr] \geq 1 - 2^{-c}.\] In particular, taking \(c = m^2/2\) shows that a uniformly random graph has \(\Delta_{2|1}(M_G) = \Omega(n^2)\) except with probability \(\exp(-\Omega(n^2))\).
Proof idea. Upper bound: encode \(G\) as an \(m \times m\) binary adjacency matrix (\(m^2\) bits) and let a fixed program simulate \(M_G\). Lower bound: by Lemma 6 there are \(2^{m^2}\) distinct interventional families, all sharing \(\mathsf{Obs}= P^\star\) with \(\mathrm{DL}_1 = O(1)\), and the conditional counting bound gives the high-probability statement. Full proof in Appendix 10.
5.1 Degree-Sensitive Optimality↩︎
The quadratic separation in Theorem 2 uses layer-\(B\) nodes whose indegree can grow with \(n\). This is not an artifact: within natural finite-gate-schema SCM classes, the largest possible description gap scales with the number of possible parent choices.
Definition 9 (Finite-gate-schema bounded-indegree SCM class). A gate schema is a computable family \(\gamma = (\gamma_k)_{k \geq 0}\) with \(\gamma_k : \{0,1\}^k \times \mathcal{U}_\gamma \to \{0,1\}\), specified by a constant-length program independent of \(n\) and \(k\) (so the schema is defined uniformly across arities). Examples include the constant, copy, negation, parity, and unbounded-AND/OR schemas.
Fix a finite set \(\Gamma\) of gate schemas and a finite set \(\Pi\) of finite-support rational exogenous noise distributions. Let \(\mathcal{M}_{n,d}(\Gamma, \Pi)\) be the class of binary acyclic SCMs on \(n\) endogenous variables such that:
every endogenous variable has at most \(d\) endogenous parents;
each structural equation is obtained by choosing a schema \(\gamma \in \Gamma\) and applying its \(k\)-ary component \(\gamma_k\) to the chosen \(k \leq d\) parent values and local exogenous noise;
each local exogenous noise distribution is chosen from \(\Pi\).
The libraries \(\Gamma\) and \(\Pi\) are fixed independently of \(n\).
The bipartite-graph SCMs of Definition 8 belong to \(\mathcal{M}_{n,n-1}(\Gamma_{\mathrm{bip}}, \Pi_{\mathrm{bip}})\) for \(\Gamma_{\mathrm{bip}} = \{\mathrm{copy}, \mathrm{AND}\}\) and \(\Pi_{\mathrm{bip}} = \{\delta_0, \mathrm{Bernoulli}(1/2)\}\), since the AND schema applies uniformly at every arity. The rooted-tree SCMs belong to \(\mathcal{M}_{n,1}(\{\mathrm{copy}\}, \{\delta_0, \mathrm{Bernoulli}(1/2)\})\).
Theorem 3 (Degree-sensitive upper bound). For every fixed finite gate-schema library \(\Gamma\) and finite noise library \(\Pi\), and every \(1 \leq d \leq n-1\), there exists a constant \(C_{\Gamma,\Pi}\) such that every \(M \in \mathcal{M}_{n,d}(\Gamma,\Pi)\) satisfies \[\mathrm{DL}_2(M) \;\leq\; C_{\Gamma,\Pi} \cdot n + n \log_2\!\Bigl(\sum_{k=0}^{d} \binom{n-1}{k}\Bigr) + O(n \log n).\] In particular, \[\mathrm{DL}_2(M) = O\!\left( n d \log\frac{en}{d} + n \log n \right),\] and consequently \[\Delta_{2|1}(M) \;\leq\; O\!\left( n d \log\frac{en}{d} + n \log n \right).\]
Proof idea. Encode an \(M \in \mathcal{M}_{n,d}(\Gamma,\Pi)\) by a topological order, each variable’s parent set, and its gate/noise choices; the binomial-sum inequality \(\sum_{k=0}^{d}\binom{n-1}{k} \leq (d+1)(e(n-1)/d)^d\) for \(1 \leq d \leq n-1\) gives the asymptotic form. Full proof in Appendix 10.
Corollary 1 (Optimality of the tree and bipartite constructions). Within finite-gate-schema SCM classes: if \(d = O(1)\), every observational–interventional gap is at most \(O(n \log n)\), achieved by the rooted-tree construction (Theorem 1); if \(d = \Theta(n)\), the upper bound becomes \(O(n^2)\), achieved by the bipartite construction (Theorem 2). The transition from \(\Theta(n \log n)\) to \(\Theta(n^2)\) is exactly the transition from bounded-degree to dense mechanisms.
Proof. Substitute \(d = O(1)\) and \(d = \Theta(n)\) into Theorem 3; the rooted-tree and bipartite constructions lie in \(\mathcal{M}_{n,1}\) and \(\mathcal{M}_{n,n-1}\) under the gate-schema libraries identified after Definition 9, realizing the rates via Theorems 1 and 2. ◻
5.2 Finite-Precision Robustness↩︎
The previous results are stated for exact query answers. We now show that the quadratic separation is not an artifact of exact arithmetic: it persists even when interventional distributions only need to be specified up to constant total-variation error.
Definition 10 (Approximate query-class description length). Let \(d_Q\) be a metric on answer objects for query class \(Q\). For \(\varepsilon > 0\), define \[K_\varepsilon\bigl(\mathrm{Ans}_Q(M) \mid w\bigr) := \min\bigl\{ |p| \;:\; d_Q\!\bigl(U(p, w), \mathrm{Ans}_Q(M)\bigr) \leq \varepsilon \bigr\},\] where \(U\) is the fixed universal machine and \(w\) is an auxiliary input. The corresponding \(\varepsilon\)-approximate description gap is \[\Delta_\varepsilon(Q_2 \mid Q_1; M) := K_\varepsilon\bigl(\mathrm{Ans}_{Q_2}(M) \;\big|\; \mathrm{Ans}_{Q_1}(M), n\bigr).\] For interventional answer objects we use the metric \[d_{\mathsf{Int}}(I, I') := \max\!\left\{ \mathrm{TV}(P_I, P_{I'}),\; \max_{i \in [n],\, b \in \{0,1\}} \mathrm{TV}\!\bigl( P^{\mathop{\mathrm{do}}(X_i = b)}_I,\, P^{\mathop{\mathrm{do}}(X_i = b)}_{I'} \bigr) \right\},\] where \(\mathrm{TV}\) denotes total variation distance and \(P_I, P_{I'}\) are the observational components of \(I, I'\).
Theorem 4 (Approximate quadratic separation). Consider the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\) with \(n = 2m + 1\). For every fixed \(\varepsilon < 1/4\):
Upper bound. For every \(G\), \(\Delta_\varepsilon(\mathsf{Int}_1 \mid \mathsf{Obs};\, M_G) \leq m^2 + O(1)\).
Lower bound (existence). There exists \(G \subseteq A \times B\) such that \[\Delta_\varepsilon(\mathsf{Int}_1 \mid \mathsf{Obs};\, M_G) \;\geq\; m^2 - O(\log n).\]
Lower bound (high probability). For uniformly random \(G \sim \mathrm{Unif}(2^{A \times B})\) and every \(c \geq 0\), \[\Pr\!\left[\, \Delta_\varepsilon(\mathsf{Int}_1 \mid \mathsf{Obs};\, M_G) \geq m^2 - c - O(\log n) \,\right] \;\geq\; 1 - 2^{-c}.\]
Proof idea. For the upper bound, an exact \(m^2\)-bit encoding of \(G\) already lets a fixed program output \(\mathsf{Int}_1(M_G)\) exactly, hence \(\varepsilon\)-approximately. For the lower bound, distinct \(G\) differ on some edge \((a_i, b_j)\), and \(\mathop{\mathrm{do}}(X_{a_i}{=}0)\) shifts the marginal of \(X_{b_j}\) by exactly \(1/2\), so the \(\varepsilon\)-balls around the \(2^{m^2}\) answer oracles are pairwise disjoint for \(\varepsilon < 1/4\); the conditional counting bound applies. Full proof in Appendix 10.
6 Counterfactual Separation: The Modular-XOR Construction↩︎
The hierarchy continues: even the full hard-do interventional oracle (the joint specification of all hard atomic do-distributions on endogenous variables) can leave counterfactual queries underdetermined. The construction stacks \(m\) copies of the simplest 2-mechanism ambiguity: on a pair \((X, Y)\), the no-effect mechanism (\(X, Y\) independent uniform) and the XOR mechanism (\(X\) uniform, \(Y = X \oplus U_Y\) with independent \(U_Y\) uniform) are both uniform on \(\{0,1\}^2\) and behave identically under every intervention, but disagree on every counterfactual that fixes the noise: under no-effect \(Y^{\mathop{\mathrm{do}}(X=0)} = Y^{\mathop{\mathrm{do}}(X=1)}\) on the same \(U_Y\), while under XOR they always differ.
Definition 11 (Modular-XOR SCM). Let \(n = 2m\). For a hidden string \(s \in \{0,1\}^m\), the SCM \(M_s\) has \(m\) independent modules \((X_t, Y_t)\) with iid exogenous \(U_{X_t}, U_{Y_t} \sim \mathrm{Bernoulli}(1/2)\) and \[X_t := U_{X_t}, \qquad Y_t := \begin{cases} U_{Y_t} & \text{if } s_t = 0, \\ X_t \oplus U_{Y_t} & \text{if } s_t = 1. \end{cases}\]
Proofs of all lemmas and theorems in this section are in Appendix 11.
Lemma 7 (Observational Equivalence). For all \(s \in \{0,1\}^m\), the observational distribution of \(M_s\) is uniform on \(\{0,1\}^{2m}\).
Lemma 8 (Interventional Equivalence). For all \(s \in \{0,1\}^m\), the interventional family \(\mathsf{Int}_1(M_s)\) is identical.
Lemma 9 (Counterfactual Encoding). The map \(s \mapsto \mathsf{CF}_1(M_s)\) is injective.
Lemmas 7–9 already give a \(\Theta(n)\) gap conditional on \(\mathsf{Int}_1\). The next definition and lemma upgrade \(\mathsf{Int}_1\) to the full hard-do interventional oracle, so the counterfactual gap survives even complete knowledge of all hard atomic do-distributions.
Definition 12 (All finite interventions). For an SCM \(M\) on variables \(X_1, \ldots, X_n\), define \[\mathsf{Int}_{\mathrm{all}}(M) \;:=\; \bigl( P_M^{\mathop{\mathrm{do}}(X_S = x_S)} \bigr)_{S \subseteq [n],\, x_S \in \{0,1\}^{S}},\] the collection of post-interventional distributions under all finite atomic interventions. Clearly \(\mathsf{Int}_1(M)\) is computable from \(\mathsf{Int}_{\mathrm{all}}(M)\).
Lemma 10 (Modular-XOR is indistinguishable under all interventions). For all \(s, s' \in \{0,1\}^m\), \(\mathsf{Int}_{\mathrm{all}}(M_s) = \mathsf{Int}_{\mathrm{all}}(M_{s'})\).
Here “full hard-do interventional oracle” means \(\mathsf{Int}_{\mathrm{all}}(M)\) as in Definition 12: all hard atomic do-interventions on endogenous variables; it excludes soft, stochastic, edge, and exogenous interventions.
Theorem 5 (Counterfactual gap after the full hard-do interventional oracle). Let \(n = 2m\) and \(\mathcal{M}_{\mathrm{xor}}^n := \{M_s : s \in \{0,1\}^m\}\) as in Definition 11. Then:
\(\mathrm{DL}(\mathsf{Int}_{\mathrm{all}}; M_s) = O(1)\) for all \(s\).
Upper bound. For every \(s\), \(\mathrm{DL}_3(M_s) \leq m + O(1)\).
Lower bound. For \(s \sim \mathrm{Unif}(\{0,1\}^m)\) and every \(c \geq 0\), \[\Pr\!\left[ K\!\left(\mathsf{CF}_1(M_s) \mid \mathsf{Int}_{\mathrm{all}}(M_s), n\right) \geq m - c - O(1) \right] \geq 1 - 2^{-c}.\]
Thus even the full hard-do interventional oracle can leave a \(\Theta(n)\) counterfactual description gap.
Proof idea. By Lemma 10, \(\mathsf{Int}_{\mathrm{all}}(M_s)\) does not depend on \(s\), so conditioning on it is free. By Lemma 9, the map \(s \mapsto \mathsf{CF}_1(M_s)\) is injective on \(\{0,1\}^m\), giving \(2^m\) distinct counterfactual answer objects. The conditional counting bound then yields the lower bound; an \(m\)-bit encoding of \(s\) gives the upper bound. Full proof in Appendix 11.
Since \(\mathsf{Int}_1\) is computable from \(\mathsf{Int}_{\mathrm{all}}\), Theorem 5 implies the single-node statement \(\Delta_{3|2}(M_s) = \Theta(n)\) as a corollary.
7 Ambiguity-to-Bits: A General Principle↩︎
The three constructions instantiate a single template: hide a parameter inside the SCM that lower-rung queries cannot resolve but higher-rung queries can; the gap is at least the log of the number of distinct higher-rung answer oracles consistent with the lower-rung answer, and in our constructions this lower bound is matched up to lower-order terms. We formalize this in a Kolmogorov form (worst-case) and a Shannon form (average-case under any prior), stated for arbitrary query classes \(Q_1, Q_2\).
Definition 13 (General ambiguity class). For query classes \(Q_1, Q_2\), a finite SCM family \(\mathcal{M}\), and a lower-rung answer \(a\), define \[\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M}) := \{\mathrm{Ans}_{Q_2}(M) : M \in \mathcal{M},\, \mathrm{Ans}_{Q_1}(M) = a\}.\]
Theorem 6 (Ambiguity-to-bits, Kolmogorov form). For any finite family \(\mathcal{M}\), query classes \(Q_1, Q_2\), and lower-rung answer \(a\), \[\max_{M \in \mathcal{M}:\, \mathrm{Ans}_{Q_1}(M) = a} K\!\bigl(\mathrm{Ans}_{Q_2}(M) \mid a, n\bigr) \;\geq\; \log_2 |\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})| - O(1).\] Moreover, for every \(c \geq 0\), all but a \(2^{-c}\) fraction of the distinct strings in \(\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})\) have conditional complexity at least \(\log_2 |\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})| - c - O(1)\).
Proof. The set \(\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})\) is by construction a set of distinct finite strings. Apply the counting bound (Lemma 1) with auxiliary input \(w = (a, n)\). ◻
Theorem 7 (Ambiguity-to-entropy, Shannon form). Let \(\Theta\) be a random hidden parameter, \(M_\Theta\) the corresponding random SCM, and write \(L(\Theta) := \mathrm{Ans}_{Q_1}(M_\Theta)\) for the lower-rung answer and \(U(\Theta) := \mathrm{Ans}_{Q_2}(M_\Theta)\) for the higher-rung (“upper”) answer. If \(U\) is a deterministic injective function of \(\Theta\) on each level set of \(L\), then \(\mathsf{H}(U(\Theta) \mid L(\Theta) = \ell) = \mathsf{H}(\Theta \mid L(\Theta) = \ell)\), where \(\mathsf{H}\) denotes Shannon entropy. In particular, if \(\Theta\) is uniform over an ambiguity class of size \(N\), this conditional entropy equals \(\log_2 N\).
Proof. Conditional on \(L(\Theta) = \ell\), the map \(\Theta \mapsto U(\Theta)\) is a bijection on the support; bijections preserve Shannon entropy. ◻
Instantiating both theorems on the three families gives ambiguity-class sizes \(|\mathcal{F}_{\mathsf{Int}_1 \mid \mathsf{Obs}}(P^\star; \mathcal{M}_{\mathrm{tree}}^n)| = n^{n-1}\), \(|\mathcal{F}_{\mathsf{Int}_1 \mid \mathsf{Obs}}(P^\star; \mathcal{M}_{\mathrm{bip}}^n)| = 2^{m^2}\), and \(|\mathcal{F}_{\mathsf{CF}_1 \mid \mathsf{Int}_{\mathrm{all}}}(I^\star; \mathcal{M}_{\mathrm{xor}}^n)| = 2^m\), yielding lower bounds \(\Theta(n \log n)\), \(\Theta(n^2)\), and \(\Theta(n)\). In each construction these bounds are matched (up to lower-order terms) by an explicit upper-bound encoding (Prüfer sequence, adjacency matrix, hidden bit string), so the gap equals the log of the ambiguity in both Kolmogorov and Shannon senses. The causal description gap is therefore not a Kolmogorov-incompressibility artifact: under natural uniform priors it appears as a Shannon conditional-entropy gap of the same order.
7.1 Learning-Theoretic Consequence↩︎
Theorem 6 translates to a no-free-lunch result for observational learning.
Corollary 2 (No-free-lunch for observational learners). In the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\) all \(2^{m^2}\) mechanisms share the same observational distribution \(P^\star\). Hence for every sample size \(N\), an observational dataset \(D \sim (P^\star)^N\) satisfies \(I(G; D) = 0\) in the Shannon sense, and any learner that outputs an interventional oracle from \(D\) alone satisfies \[\Pr_{G \sim \mathrm{Unif}(2^{A \times B})}\!\bigl[\widehat{\mathsf{Int}}_1 = \mathsf{Int}_1(M_G)\bigr] \;\leq\; 2^{-m^2},\] while any per-query predictor has expected absolute error at least \(1/4\) (full statements and proofs in Appendix 12). The bound is information-theoretic, not computational: no amount of observational data closes the gap.
8 Conclusion↩︎
We turned Pearl’s qualitative hierarchy into a quantitative information hierarchy. Non-identifiability can be large in a precise description-length sense: with constant-bit observations the residual interventional information can be \(\Theta(n^2)\), robust to constant total-variation error and order-optimal for dense finite-gate-schema SCMs; even the full hard-do interventional oracle can leave a \(\Theta(n)\) counterfactual gap. The governing quantity throughout is the log of residual higher-rung ambiguity.
8.0.0.1 Scope and next steps.
Our SCMs are binary, acyclic, adversarial by design, and need not satisfy positivity or faithfulness; this is a deliberate scope showing that observational adequacy alone imposes no small causal-description bound without further structure. How sparsity, positivity/noise, smoothness, or faithfulness shrink the residual ambiguity, the active-intervention complexity of closing the gap, and extensions beyond binary SCMs are natural next steps.
9 Rooted-Tree Construction: Full Details↩︎
This appendix gives the formal construction and full proofs underlying the \(\Theta(n \log n)\) rooted-tree separation. Theorem 8 below restates and proves the main-text Theorem 1; together with Corollary 1 it shows the bound is order-optimal in the bounded-indegree regime.
Intuition: Hidden Information Flow↩︎
Consider \(n\) variables that are always perfectly correlated: either all \(0\) or all \(1\), with equal probability. A passive observer sees only this correlation. But how does the correlation arise?
Imagine the variables arranged in a tree, with one root variable \(X_r\) that is uniformly random, and all other variables copying their parent. The tree structure determines the direction of information flow, but this structure is invisible to passive observation: all trees produce the same “all equal” distribution.
Interventions reveal the hidden structure. If we force \(X_i = 0\), then:
All descendants of \(i\) in the tree become \(0\) (they copy from ancestors, and \(i\) is now \(0\)).
All non-descendants remain random (they don’t depend on \(i\)).
So interventions reveal the descendant structure, which determines the tree. Since there are \(n^{n-1}\) rooted labeled trees (by Cayley’s formula), there are \(n^{n-1}\) distinct interventional behaviors consistent with the same observations, and distinguishing among them requires \(\log_2(n^{n-1}) = (n-1) \log n\) bits.
Formal Construction↩︎
9.0.0.1 Notation.
For a rooted tree \(T\) on \([n]\) with root \(r\), we write \(\mathrm{pa}_T(v)\) for the parent of \(v\) in \(T\) (defined for all \(v \neq r\)), and \(\mathrm{Desc}_T(i)\) for the set of descendants of node \(i\) in \(T\), including \(i\) itself. That is, \(j \in \mathrm{Desc}_T(i)\) if and only if \(i\) lies on the unique path from \(j\) to \(r\).
Definition 14 (Rooted-Tree SCM). Let \(T\) be a rooted labeled tree on vertex set \([n]\) with root \(r\). Define the SCM \(M_T\):
Exogenous variables: \(U_r \sim \mathrm{Bernoulli}(1/2)\). All other \(U_i\) are constant (say, \(0\)) and play no role.
Structural equations: \[\begin{align} X_r &:= U_r, \\ X_v &:= X_{\mathrm{pa}_T(v)} \quad \text{for each } v \neq r, \end{align}\] where \(\mathrm{pa}_T(v)\) denotes the parent of \(v\) in the rooted tree \(T\).
In words: the root takes a random value in \(\{0,1\}\), and every other node copies its parent. Information flows from the root outward along the tree edges.
Lemma 11 (All Trees Have the Same Observations). For every rooted tree \(T\), the observational distribution of \(M_T\) is: \[P^\star(x_1, \ldots, x_n) = \begin{cases} 1/2 & \text{if } x_1 = x_2 = \cdots = x_n = 0, \\ 1/2 & \text{if } x_1 = x_2 = \cdots = x_n = 1, \\ 0 & \text{otherwise}. \end{cases}\] Consequently, \(\mathrm{DL}_1(M_T) = K(P^\star \mid n) = O(1)\).
Proof. Since \(T\) is a connected tree and every non-root node copies its parent, any value assigned to the root propagates to all nodes. Specifically:
If \(U_r = 0\): Then \(X_r = 0\). For any node \(v\) at distance \(1\) from \(r\), we have \(X_v = X_{\mathrm{pa}_T(v)} = X_r = 0\). By induction on distance from \(r\), all nodes have value \(0\).
If \(U_r = 1\): By the same argument, all nodes have value \(1\).
Since \(U_r \sim \mathrm{Bernoulli}(1/2)\), the outcome is \(0^n\) with probability \(1/2\) and \(1^n\) with probability \(1/2\).
The distribution \(P^\star\) can be specified by a constant-length program: “output \(1/2\) for \(0^n\) and \(1^n\), output \(0\) otherwise.” Thus \(K(P^\star \mid n) = O(1)\). ◻
Lemma 12 (Interventions Reveal Descendants). For any node \(i \in [n]\) and the intervention \(\mathop{\mathrm{do}}(X_i = 0)\): \[P_{M_T}^{\mathop{\mathrm{do}}(X_i = 0)}(X_j = 0) = \begin{cases} 1 & \text{if } j \in \mathrm{Desc}_T(i), \\ 1/2 & \text{if } j \notin \mathrm{Desc}_T(i), \end{cases}\] where \(\mathrm{Desc}_T(i)\) is the set of descendants of \(i\) in \(T\) (including \(i\) itself).
Proof. Under \(\mathop{\mathrm{do}}(X_i = 0)\), the equation for \(X_i\) becomes \(X_i := 0\). All other equations remain unchanged.
Case 1: \(j \in \mathrm{Desc}_T(i)\). Every descendant of \(i\) lies on a path from \(i\) going away from the root. Along this path, each node copies its parent. Since \(X_i = 0\) and descendants copy from ancestors (with \(i\) being an ancestor), we have \(X_j = 0\) deterministically.
Case 2: \(j \notin \mathrm{Desc}_T(i)\). If \(j\) is not a descendant of \(i\), then the path from the root \(r\) to \(j\) does not pass through \(i\). The value of \(X_j\) depends only on nodes along this path, which are unaffected by the intervention on \(X_i\). Thus \(X_j\) still equals \(X_r = U_r \sim \mathrm{Bernoulli}(1/2)\), so \(P(X_j = 0) = 1/2\). ◻
Lemma 13 (Descendant Sets Determine the Tree). The collection of descendant sets \(\{\mathrm{Desc}_T(i) : i \in [n]\}\) uniquely determines the rooted tree \(T\).
Proof. We show how to reconstruct \(T\) from the descendant sets.
Finding the root: The root \(r\) is the unique node with \(\mathrm{Desc}_T(r) = [n]\) (every node is a descendant of the root).
Finding parent-child relationships: For any non-root node \(v\), its parent \(\mathrm{pa}_T(v)\) is characterized as follows. Consider all nodes \(u \neq v\) such that \(v \in \mathrm{Desc}_T(u)\) (i.e., \(u\) is an ancestor of \(v\)). Among these, \(\mathrm{pa}_T(v)\) is the one with the smallest descendant set.
To see why: along the unique path from \(v\) to the root \(r\), descendant sets strictly increase: \[\mathrm{Desc}_T(v) \subsetneq \mathrm{Desc}_T(\mathrm{pa}_T(v)) \subsetneq \mathrm{Desc}_T(\mathrm{pa}_T(\mathrm{pa}_T(v))) \subsetneq \cdots \subsetneq \mathrm{Desc}_T(r) = [n].\] The strict inclusions hold because each step toward the root adds at least the current node to the descendant set. Thus the parent has the smallest descendant set among all ancestors.
This procedure reconstructs all parent-child edges, hence the entire tree. ◻
Theorem 8 (Rooted-Tree Separation: \(\Theta(n \log n)\)). Let \(\mathcal{M}_{\mathrm{tree}}^n := \{M_T : T \text{ is a rooted labeled tree on } [n]\}\). Then:
The map \(T \mapsto \mathsf{Int}_1(M_T)\) is injective on \(\mathcal{M}_{\mathrm{tree}}^n\).
Lower bound: There exists \(T\) with \(\Delta_{2|1}(M_T) \geq (n-1)\log_2 n - O(\log n)\).
Upper bound: For all \(T\), \(\mathrm{DL}_2(M_T) \leq (n-1)\log_2 n + O(\log n)\).
High probability: For uniformly random rooted labeled tree \(T\), \[\mathbb{P}\bigl[\Delta_{2|1}(M_T) \geq (n-1)\log_2 n - c - O(\log n)\bigr] \geq 1 - 2^{-c}.\]
Consequently, \(\Delta_{2|1}(M_T) = \Theta(n \log n)\) for all but an exponentially small fraction of trees.
Proof. Part 1 (Injectivity): By Lemma 12, from \(\mathsf{Int}_1(M_T)\) we can read off: \[\mathrm{Desc}_T(i) = \{j \in [n] : P_{M_T}^{\mathop{\mathrm{do}}(X_i = 0)}(X_j = 0) = 1\}\] for each \(i\). By Lemma 13, the descendant sets determine \(T\). Thus different trees yield different interventional families.
Part 2 (Lower bound): By Cayley’s formula, there are \(n^{n-1}\) rooted labeled trees on \([n]\). (Cayley’s formula gives \(n^{n-2}\) labeled unrooted trees on \([n]\); choosing a root from \(n\) vertices gives \(n^{n-1}\) rooted labeled trees.) By injectivity, there are \(n^{n-1}\) distinct elements in \(\{\mathsf{Int}_1(M_T) : T \in \mathcal{M}_{\mathrm{tree}}^n\}\).
By the counting bound for Kolmogorov complexity: among \(N\) distinct strings, at least one has complexity \(\geq \log_2 N - O(1)\). Applying this with \(N = n^{n-1}\): \[\max_T K(\mathsf{Int}_1(M_T) \mid n) \geq \log_2(n^{n-1}) - O(1) = (n-1)\log_2 n - O(1).\]
By Lemma 11, \(\mathrm{DL}_1(M_T) = O(1)\) for all \(T\). By Lemma 3, \(\Delta_{2|1}(M_T) = \mathrm{DL}_2(M_T) \pm O(\log n)\).
Part 3 (Upper bound): Given tree \(T\), we can encode it using a Prüfer sequence: a sequence of \(n-2\) labels from \([n]\), requiring \((n-2)\log_2 n\) bits, plus \(O(\log n)\) bits to specify the root. Total: \((n-1)\log_2 n + O(\log n)\) bits.
A constant-length program can then simulate \(M_T\) and output \(\mathsf{Int}_1(M_T)\). Thus \(K(\mathsf{Int}_1(M_T) \mid n) \leq (n-1)\log_2 n + O(\log n)\).
Part 4 (High probability): By part (2) of the counting bound (Lemma 1), among the \(n^{n-1}\) distinct strings \(\{\mathsf{Int}_1(M_T)\}\), all but a \(2^{-c}\) fraction satisfy \(K(\mathsf{Int}_1(M_T) \mid n) \geq (n-1)\log_2 n - c - O(1)\). Transferring to \(\Delta_{2|1}\) via Lemma 3 incurs an additional \(O(\log n)\) term. ◻
10 Bipartite-Graph Construction: Figures and Full Proofs↩︎
This appendix supports Section 5 of the main paper. Figure 1 illustrates Definition 8; Figure 2 compares the resulting bound to the rooted-tree warm-up. We then restate and prove, in order, Lemmas 4–6, Theorem 2 (quadratic separation), Theorem 3 (degree-sensitive upper bound), and Theorem 4 (finite-precision robustness).
Proof of Lemma 4. We analyze the two cases for the root’s value.
Case \(U_r = 0\): Then \(X_r = 0\). Since each \(X_{a_i} = X_r\), we have \(X_{a_i} = 0\) for all \(i\). For each \(b_j\), the equation is: \[X_{b_j} = X_r \wedge \bigwedge_{a_i : (a_i, b_j) \in G} X_{a_i} = 0 \wedge (\cdots) = 0.\] Thus all variables are \(0\).
Case \(U_r = 1\): Then \(X_r = 1\) and \(X_{a_i} = 1\) for all \(i\). For each \(b_j\): \[X_{b_j} = X_r \wedge \bigwedge_{a_i : (a_i, b_j) \in G} X_{a_i} = 1 \wedge 1 \wedge \cdots \wedge 1 = 1.\] (If \(b_j\) has no neighbors, the empty AND is \(1\), so \(X_{b_j} = 1 \wedge 1 = 1\).)
Thus all variables are \(1\).
Since \(U_r \sim \mathrm{Bernoulli}(1/2)\), the outcome is \(0^n\) or \(1^n\) each with probability \(1/2\). This is \(P^\star\), independent of \(G\). ◻
Proof of Lemma 5. Under \(\mathop{\mathrm{do}}(X_{a_i} = 0)\), the equation for \(X_{a_i}\) becomes \(X_{a_i} := 0\). The root \(X_r = U_r\) remains random, and all other layer-\(A\) nodes satisfy \(X_{a_k} = X_r\) for \(k \neq i\).
Case \((a_i, b_j) \in G\): The equation for \(X_{b_j}\) includes \(X_{a_i}\) as an AND input: \[X_{b_j} = X_r \wedge X_{a_i} \wedge \bigwedge_{a_k \neq a_i : (a_k, b_j) \in G} X_{a_k}.\] Since \(X_{a_i} = 0\), the AND evaluates to \(0\) regardless of other inputs. Thus \(X_{b_j} = 0\) deterministically, so \(P(X_{b_j} = 0) = 1\).
Case \((a_i, b_j) \notin G\): The equation for \(X_{b_j}\) does not include \(X_{a_i}\): \[X_{b_j} = X_r \wedge \bigwedge_{a_k : (a_k, b_j) \in G} X_{a_k}.\] All terms in this AND equal \(X_r\) (since \(X_{a_k} = X_r\) for \(k \neq i\)). If there are \(d\) such terms: \[X_{b_j} = X_r \wedge X_r \wedge \cdots \wedge X_r = X_r.\] (If \(b_j\) has no neighbors other than possibly \(a_i\), and \((a_i, b_j) \notin G\), then the AND is either empty (giving \(X_{b_j} = X_r\)) or involves only other \(a_k\) that equal \(X_r\).)
Thus \(X_{b_j} = X_r \sim \mathrm{Bernoulli}(1/2)\), so \(P(X_{b_j} = 0) = 1/2\). ◻
Proof of Lemma 6. By Lemma 5, from \(\mathsf{Int}_1(M_G)\) we can extract: \[N_G(a_i) = \{b_j \in B : P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}(X_{b_j} = 0) = 1\}\] for each \(a_i \in A\). The neighborhoods \(\{N_G(a_i)\}_{i=1}^m\) determine all edges of \(G\): \[(a_i, b_j) \in G \iff b_j \in N_G(a_i).\] Thus \(\mathsf{Int}_1(M_G)\) determines \(G\) uniquely. ◻
Proof of Theorem 2. Lower bound: There are \(2^{m^2}\) bipartite graphs \(G \subseteq A \times B\) (each of the \(m^2\) potential edges is present or absent). By Lemma 6, there are \(2^{m^2}\) distinct interventional families. By Lemma 4, all share \(\mathsf{Obs}(M_G) = P^\star\) with \(\mathrm{DL}_1 = O(1)\).
By the counting bound: among \(2^{m^2}\) distinct strings, at least one has Kolmogorov complexity \(\geq m^2 - O(1)\). By Lemma 3, \(\Delta_{2|1}(M_G) = \mathrm{DL}_2(M_G) \pm O(\log n)\).
The high-probability statement follows from the stronger counting bound: all but a \(2^{-c}\) fraction have complexity \(\geq m^2 - c - O(1)\).
Upper bound: The graph \(G\) can be encoded as an \(m \times m\) binary adjacency matrix, requiring \(m^2\) bits. Given \(G\) and \(n\), a constant-length program simulates \(M_G\) and outputs \(\mathsf{Int}_1(M_G)\). Thus \(K(\mathsf{Int}_1(M_G) \mid n) \leq m^2 + O(1)\). ◻
Proof of Theorem 3. An SCM in \(\mathcal{M}_{n,d}(\Gamma,\Pi)\) can be encoded by listing:
a topological ordering of the \(n\) variables, using \(O(n \log n)\) bits;
for each variable, its parent set, chosen from at most \(\sum_{k=0}^{d} \binom{n-1}{k}\) possibilities;
for each variable, a gate from the fixed library \(\Gamma\) and a noise distribution from the fixed library \(\Pi\), using \(O(1)\) bits per variable.
The entire SCM thus has a description of length \[O(n \log n) + n \log_2\!\Bigl(\sum_{k=0}^{d} \binom{n-1}{k}\Bigr) + O_{\Gamma,\Pi}(n).\] Given this description and \(n\), a fixed program can compute all single-node interventional distributions and output \(\mathsf{Int}_1(M)\). Hence the same expression upper-bounds \(K(\mathsf{Int}_1(M) \mid n) = \mathrm{DL}_2(M)\).
Finally, \[\sum_{k=0}^{d} \binom{n-1}{k} \;\leq\; (d+1) \left(\frac{e(n-1)}{d}\right)^d\] for \(1 \leq d \leq n-1\), yielding the stated asymptotic form. Since \(\Delta_{2|1}(M) \leq \mathrm{DL}_2(M) + O(1)\), the same upper bound applies to the gap. ◻
Proof of Theorem 4. Upper bound. An exact \(m^2\)-bit encoding of \(G\) as an \(m \times m\) binary adjacency matrix lets a fixed program output \(\mathsf{Int}_1(M_G)\) exactly, hence also \(\varepsilon\)-approximately for any \(\varepsilon \geq 0\). So \(K_\varepsilon(\mathsf{Int}_1(M_G) \mid \mathsf{Obs}(M_G), n) \leq m^2 + O(1)\).
Lower bound. Let \(G \neq G'\) be two distinct bipartite graphs. They differ on some edge \((a_i, b_j)\); WLOG \((a_i, b_j) \in G\) and \((a_i, b_j) \notin G'\). By Lemma 5, \[P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}(X_{b_j} = 0) = 1, \qquad P_{M_{G'}}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}(X_{b_j} = 0) = 1/2.\] Total variation distance does not increase under marginalization, so the full interventional distributions satisfy \[\mathrm{TV}\!\bigl( P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)},\; P_{M_{G'}}^{\mathop{\mathrm{do}}(X_{a_i} = 0)} \bigr) \;\geq\; \tfrac{1}{2}.\] Hence \(d_{\mathsf{Int}}(\mathsf{Int}_1(M_G), \mathsf{Int}_1(M_{G'})) \geq 1/2\). For \(\varepsilon < 1/4\), the open \(\varepsilon\)-balls around the \(2^{m^2}\) answer objects are pairwise disjoint, so any \(\varepsilon\)-accurate description must still distinguish among \(2^{m^2}\) possibilities. Applying the conditional counting bound (Lemma 1, part 2) with the common observation \(P^\star\) as side information yields the existence and high-probability lower bounds. ◻
11 Modular-XOR Construction: Full Proofs↩︎
This appendix supports Section 6. We prove, in order, Lemmas 7 (observational equivalence), 8 (single-node interventional equivalence), 9 (counterfactual encoding is injective in \(s\)), 10 (indistinguishability under all atomic interventions), and Theorem 5 (the \(\Theta(n)\) counterfactual gap conditional on \(\mathsf{Int}_{\mathrm{all}}\)).
Proof of Lemma 7. We show each module \((X_t, Y_t)\) is uniformly distributed on \(\{0,1\}^2\).
Case \(s_t = 0\): \(X_t = U_{X_t}\) and \(Y_t = U_{Y_t}\) are independent \(\mathrm{Bernoulli}(1/2)\) variables.
Case \(s_t = 1\): \(X_t = U_{X_t} \sim \mathrm{Bernoulli}(1/2)\). For \(Y_t = X_t \oplus U_{Y_t}\): for any fixed \(x \in \{0,1\}\), \[\mathbb{P}(Y_t = y \mid X_t = x) = \mathbb{P}(U_{Y_t} = x \oplus y) = 1/2.\] Thus \(Y_t\) is uniform and independent of \(X_t\). (Formally: \(\mathbb{P}(X_t = x, Y_t = y) = \mathbb{P}(X_t = x) \mathbb{P}(Y_t = y) = 1/4\).)
Since modules are independent and each is uniform on \(\{0,1\}^2\), the full distribution is uniform on \(\{0,1\}^{2m}\). ◻
Proof of Lemma 8. Consider any single-variable intervention \(\mathop{\mathrm{do}}(X_t = x)\) or \(\mathop{\mathrm{do}}(Y_t = y)\).
Intervention \(\mathop{\mathrm{do}}(X_t = x)\): The equation \(X_t := x\) replaces whatever \(X_t\) was. In module \(t\):
If \(s_t = 0\): \(Y_t = U_{Y_t}\), uniform.
If \(s_t = 1\): \(Y_t = x \oplus U_{Y_t}\), also uniform (since \(U_{Y_t}\) is uniform).
Either way, \(Y_t\) is uniform and independent of the intervention value. Other modules are unaffected.
Intervention \(\mathop{\mathrm{do}}(Y_t = y)\): The equation \(Y_t := y\) replaces whatever \(Y_t\) was. In both cases (\(s_t = 0\) or \(1\)), \(X_t = U_{X_t}\) remains uniform. Other modules unaffected.
Since all single-variable interventional distributions are the same across all \(s\), the entire family \(\mathsf{Int}_1(M_s)\) is independent of \(s\). ◻
Proof of Lemma 9. For each module \(t\), consider the counterfactual query: “What is \(\mathbb{P}(Y_t^{(X_t \leftarrow 0)} = Y_t^{(X_t \leftarrow 1)})\)?”
Let \(Y_t^{(X_t \leftarrow b)}\) denote the value of \(Y_t\) when we intervene with \(\mathop{\mathrm{do}}(X_t = b)\), evaluated on the same noise \(U_{Y_t}\).
Case \(s_t = 0\): \(Y_t^{(X_t \leftarrow 0)} = U_{Y_t}\) and \(Y_t^{(X_t \leftarrow 1)} = U_{Y_t}\). These are identical, so \(\mathbb{P}(Y_t^{(X_t \leftarrow 0)} = Y_t^{(X_t \leftarrow 1)}) = 1\).
Case \(s_t = 1\): \(Y_t^{(X_t \leftarrow 0)} = 0 \oplus U_{Y_t} = U_{Y_t}\) and \(Y_t^{(X_t \leftarrow 1)} = 1 \oplus U_{Y_t} = 1 - U_{Y_t}\). These are always different, so \(\mathbb{P}(Y_t^{(X_t \leftarrow 0)} = Y_t^{(X_t \leftarrow 1)}) = 0\).
Thus the counterfactual query for module \(t\) outputs \(1\) if \(s_t = 0\) and \(0\) if \(s_t = 1\). The \(m\) queries together determine \(s\).
Since \(\mathsf{CF}_1(M_s)\) contains \(P(X, X^{(t \leftarrow 0)}, X^{(t \leftarrow 1)})\) for all \(t\), which includes the joint distribution of \(Y_t^{(X_t \leftarrow 0)}\) and \(Y_t^{(X_t \leftarrow 1)}\), it determines \(s\). ◻
Proof of Lemma 10. It suffices to consider a single module \((X_t, Y_t)\), since modules are independent and interventions factor across modules. Fix an arbitrary intervention on any subset of \(\{X_t, Y_t\}\).
If \(Y_t\) is intervened on, then \(Y_t\) is fixed by the intervention. The remaining variable \(X_t\), if not intervened on, equals \(U_{X_t}\) and is uniform in both the no-effect and XOR mechanisms.
If \(Y_t\) is not intervened on but \(X_t\) is set to \(x\), then \[Y_t = \begin{cases} U_{Y_t}, & s_t = 0,\\ x \oplus U_{Y_t}, & s_t = 1. \end{cases}\] In either case \(Y_t\) is uniform Bernoulli and independent of all other modules.
Finally, if neither variable is intervened on, then for \(s_t = 0\) we have \((X_t, Y_t) = (U_{X_t}, U_{Y_t})\), uniform on \(\{0,1\}^2\); for \(s_t = 1\) we have \((X_t, Y_t) = (U_{X_t}, U_{X_t} \oplus U_{Y_t})\), also uniform on \(\{0,1\}^2\).
Thus every possible intervention produces the same distribution regardless of \(s_t\). Taking the product over independent modules proves the claim. ◻
Proof of Theorem 5. Part 1. By Lemma 10, \(\mathsf{Int}_{\mathrm{all}}(M_s)\) is identical for all \(s\). Its description is constant: every intervention fixes the intervened variables and leaves each non-intervened module uniformly distributed in the manner described in the proof of Lemma 10.
Part 2 (Upper bound). Given \(s\) (\(m\) bits) and \(n\), a constant-length program simulates \(M_s\) and outputs \(\mathsf{CF}_1(M_s)\). Thus \(K(\mathsf{CF}_1(M_s) \mid n) \leq m + O(1)\).
Part 3 (Lower bound). By Lemma 9, the map \(s \mapsto \mathsf{CF}_1(M_s)\) is injective. Hence there are \(2^m\) distinct counterfactual answer objects consistent with the same full hard-do interventional oracle. The conditional counting bound (Lemma 1, part 2), applied with \(w = (\mathsf{Int}_{\mathrm{all}}(M_s), n)\), yields the high-probability claim, since \(\mathsf{Int}_{\mathrm{all}}(M_s)\) is constant across \(s\) and contributes only \(O(1)\) to the conditioning. ◻
12 Learning-Theoretic Consequences↩︎
This appendix supports the brief discussion of §7.1 of the main paper. We give two no-free-lunch results for observational learners drawn from the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\) (Definition 8): one bounds the joint-recovery success rate, the other a per-query absolute error.
Corollary 3 (No-free-lunch for observational learners). Let \(G \sim \mathrm{Unif}(2^{A \times B})\) in the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\). Any learner \(\mathcal{A}\) that receives an i.i.d.sample of any size from \(\mathsf{Obs}(M_G)\) and outputs a prediction \(\widehat{\mathsf{Int}}_1\) satisfies \[\mathbb{P}[\widehat{\mathsf{Int}}_1 = \mathsf{Int}_1(M_G)] \;\leq\; 2^{-m^2}.\]
Proof. All \(M_G\) share the observational distribution \(P^\star\), so any sample from \(P^\star\) is statistically independent of \(G\). The learner’s output, a function of the sample, is therefore independent of \(G\). With \(2^{m^2}\) equiprobable targets \(\{\mathsf{Int}_1(M_G)\}\) (the map \(G \mapsto \mathsf{Int}_1(M_G)\) is injective by Lemma 6) and output independent of the true target, the success probability is at most \(2^{-m^2}\). ◻
Corollary 4 (Per-query prediction error). Let \(G \sim \mathrm{Unif}(2^{A \times B})\) in the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\). Let \(\hat{p}\) be any predictor (possibly depending on an i.i.d.sample of any size from \(\mathsf{Obs}(M_G)\)). For an independent uniformly random pair \((i,j) \in [m] \times [m]\), let \(p_{i,j}(G) := P_{M_G}^{\mathop{\mathrm{do}}(X_{a_i} = 0)}(X_{b_j} = 0)\). Then \[\mathbb{E}\bigl[|\hat{p}_{i,j} - p_{i,j}(G)|\bigr] \;\geq\; \tfrac{1}{4}.\]
Proof. By Lemma 5, \(p_{i,j}(G) \in \{1/2, 1\}\) depending on whether \((a_i, b_j) \in G\). For \(G \sim \mathrm{Unif}(2^{A \times B})\) the edge indicator is Bernoulli\((1/2)\), so \(p_{i,j}(G)\) equals \(1\) and \(1/2\) each with probability \(1/2\). The observational sample is independent of \(G\), hence so is the predictor output \(\hat{p}_{i,j}\). Condition on \(\hat{p}_{i,j} = a\): \[\mathbb{E}\bigl[|\hat{p}_{i,j} - p_{i,j}(G)| \,\big|\, \hat{p}_{i,j} = a\bigr] \;=\; \tfrac{1}{2} |a - 1| + \tfrac{1}{2} |a - \tfrac{1}{2}| \;\geq\; \tfrac{1}{4},\] where the last step uses the triangle inequality \(|a-1| + |a-\tfrac{1}{2}| \geq |1 - \tfrac{1}{2}| = \tfrac{1}{2}\). Averaging over \(a\) proves the claim. ◻
This is not a computational limitation; it is information-theoretic. No algorithm, however powerful, can reliably predict interventional outcomes from observations when the underlying mechanism is drawn from our family.
Remark 9 (Shannon Mutual Information is Zero). In the bipartite family \(\mathcal{M}_{\mathrm{bip}}^n\), a dataset \(D \sim (P^\star)^N\) of \(N\) i.i.d.observational samples is independent of the hidden graph \(G\), since all mechanisms share the same observational distribution. Therefore \(I(G; D) = 0\) in the Shannon sense for every sample size \(N\). The lower bounds in Corollary 3 and Corollary 4 follow from this information-theoretic independence and do not rely on uncomputability of Kolmogorov complexity.