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

会议: NeurIPS 2026
arXiv: 2605.02177
OpenReview: https://openreview.net/forum?id=EHJ28rBFTV
代码: 待确认
领域: 其他
关键词: 因果推理, 柯尔莫哥洛夫复杂度, 描述长度, 珍珠因果层级, 信息论分离

一句话总结¶

本文首次从算法信息论与香农信息论视角对珍珠因果层级（PCH）进行严格定量化，证明在仅具常数级观测描述长度的结构因果模型中，单变量干预答案与反事实答案的描述缺口在最坏情况和高概率下可分别达到 $\Theta(n^2)$ 比特，确立了跨层级因果查询的信息论分离界与紧界上界。

研究背景与动机¶

因果推理领域长期以 Judea Pearl 提出的三级因果层级（Pearl's Causal Hierarchy, PCH：关联/观测、干预、反事实）为理论基石。Bareinboim 等人的因果层级定理（CHT）在定性层面确立了层级间的严格性，即更高层级的因果查询在一般情况下无法单凭低层级信息判定（非可识别性）。然而，学界长期悬而未决的一个关键定量问题是：当低层级信息（如被动观测分布）已知时，完全确定更高层级答案（如干预分布或反事实联合分布）到底还需要多少额外的信息量？这种额外信息量是否能被常数限制，还是会随着变量规模 $n$ 迅速爆炸？

在经典因果发现与统计学习视角下，非可识别性往往被表述为定性的二元判断，即“可识别”或“不可识别”；即使在极小样本复杂度或实验次数的研究中，也未曾将整个查询类的答案系统性视作计算对象并度量其内在信息复杂度。随着大语言模型与基础模型在被动语料预测上的突破，大量工作发现单纯的观测预测预训练无法自发涌现可靠的因果推理能力，但缺乏从信息论底层给出的根本约束界限。

针对这一根本矛盾，本文跳出传统样本复杂度或连续参数估计的框架，创造性地引入基于柯尔莫哥洛夫复杂度的查询类描述长度（Query-Class Description Length），把因果模型输出的答案视为待压缩的因果预言机对象。核心 idea：将因果层级间的本质鸿沟严格形式化为条件柯尔莫哥洛夫复杂度定义的“因果描述缺口”，构建具有对称性与隐结构的有向无环结构因果模型族，证明从观测到干预以及从全量硬干预到反事实均存在 $\Theta(n^2)$ 比特的信息论分离，并建立度敏感的通用紧界与模糊度到比特的转换原理。

方法详解¶

整体框架¶

本文针对定义在 $n$ 个二元变量上的无环结构因果模型（SCM），系统形式化了三类查询类的答案预言机：观测查询类 $\mathsf{Obs}(M)$、单变量干预查询类 $\mathsf{Int}_1(M)$（包含 $2n$ 个单节点干预分布）、全量硬干预查询类 $\mathsf{Int}_{\mathrm{all}}(M)$ 以及单变量反事实联合查询类 $\mathsf{CF}_1(M)$。

因果描述缺口（Causal Description Gap）被定义为在已知系统规模 $n$ 及低层级查询答案 $Q_1$ 的辅助输入下，输出高层级查询答案 $Q_2$ 所需最短计算机程序长度的差值，即条件柯尔莫哥洛夫复杂度 $\Delta(Q_2 \mid Q_1; M) := K(\mathrm{Ans}_{Q_2}(M) \mid \mathrm{Ans}_{Q_1}(M), n)$。整个理论分析流沿着“基础隐结构构造 → 分离界与度敏感上界 → 鲁棒性与学习下界 → 因果假设消解”的脉络展开。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["二元变量结构因果模型 (SCM)"] --> B["查询类答案编码与描述长度定义"]
    B --> C["有向树构造：有界入度干预分离"]
    B --> D["二分图构造：稠密图二次干预分离"]
    C --> E["度敏感紧界理论：入度 d 约束"]
    D --> E
    E --> F["掩码奇偶校验构造：全干预到反事实二次分离"]
    F --> G["模糊度到比特原理与统计学习无免费午餐"]

关键设计¶

1. 有向树与二分图构造：从常数观测到 $\Theta(n^2)$ 干预信息爆炸 为了剥离观测复杂度本身的干扰并凸显层级鸿沟，构造的因果模型族必须在被动观测下产生完全相同的退化或均匀分布，从而使其观测描述长度保持为 $O(1)$ 常数。在有向树构造中，根节点取均匀随机伯努利噪声 $U_r \sim \mathrm{Bernoulli}(1/2)$，所有非根节点均直接复制其父节点。在被动观测下，变量始终同为全 0 或全 1（各占 $1/2$ 概率），因此 $K(\mathsf{Obs} \mid n) = O(1)$。但进行单变量干预 $\mathrm{do}(X_i = 0)$ 时，$X_i$ 及其所有后代节点均被确定性强制置 0，而非后代节点维持均匀随机。通过 Cayley 公式，有向标号树共有 $n^{n-1}$ 种拓扑，每个后代集合可精确逆向还原父节点与树拓扑，产生 $\Theta(n \log n)$ 比特的干预描述缺口。进一步为了达到理论极限的二次项，设计了层级二分图 SCM：分为根节点 $r$、第一层 $A=\{a_1,\dots,a_m\}$ 与第二层 $B=\{b_1,\dots,b_m\}$（总节点 $n=2m+1$），结构方程定义为 $X_{a_i} := X_r$，$X_{b_j} := X_r \wedge \bigwedge_{(a_i, b_j) \in G} X_{a_i}$。观测下所有变量依然全等于 $X_r$（$O(1)$ 描述长度）；但执行 $\mathrm{do}(X_{a_i}=0)$ 时，$b_j$ 是否置 0 严格取决于边 $(a_i, b_j)$ 是否存在。由于 $A \times B$ 间存在 $2^{m^2}$ 种可能的邻接子图，干预答案预言机与二分图邻接矩阵单射，直接迫使条件描述长度达到 $m^2 - O(1) = \Theta(n^2)$ 比特。

2. 度敏感上界与阶最优性匹配：刻画图拓扑对信息量的终极约束 仅有下界不足以证明 $\Theta(n^2)$ 是紧的。若允许无限制的门函数或任意连续噪声，因果缺口甚至可能无界。为此，论文引入了有限门模式库 $\Gamma$（如常数门、复制门、奇偶校验门、任意扇入 AND/OR 门）与有限有理概率噪声库 $\Pi$。在每个变量的内生入度至多为 $d$ 的约束下，证明了任何 SCM 及其干预答案都可以通过拓扑排序、父节点集合索引及门/噪声编号进行紧凑编码： $$\mathrm{DL}_2(M) \leq C_{\Gamma, \Pi} \cdot n + n \log_2 \left(\sum_{k=0}^d \binom{n-1}{k}\right) + O(n \log n) = O\left(nd \log \frac{en}{d} + n \log n\right)$$ 该上界不仅适用于单节点干预 $\mathsf{Int}_1$，还适用于全量子集硬干预 $\mathsf{Int}_{\mathrm{all}}$ 和反事实查询 $\mathsf{CF}_1$。当最大入度 $d=O(1)$ 时，上界退化为 $O(n \log n)$，与有向树构造匹配；当 $d=\Theta(n)$ 时，上界达到 $O(n^2)$，与二分图构造匹配。这在信息论意义上完全闭合了有界度因果模型在极疏和稠密两种极端状态下的紧界阶数。

3. 掩码奇偶校验构造：全量子集硬干预下的反事实不可见性 即便拥有全空间所有子集的硬干预答案 $\mathsf{Int}_{\mathrm{all}}$（即完全掌握整个因果图的因果干预流），反事实答案是否依然可以隐藏海量信息？针对这一更高级鸿沟，论文构造了掩码奇偶校验（Masked Parity）因果模型族：变量划分为输入组 $X_i$ 与输出组 $Y_j$（$n=2m$），结构方程为 $X_i := U_i$，$Y_j := \left(\bigoplus_{i \in S_j} X_i\right) \oplus V_j$，其中 $U_i, V_j$ 为独立均匀随机比特，而 $S_j \subseteq [m]$ 是大小不超过 $d$ 的隐藏父节点子集。由于每个输出端均被私有均匀随机噪声 $V_j$ 掩码，在任意子集变量的硬干预 $\mathrm{do}(X_T=x_T, Y_W=y_W)$ 下，未被钳制的变量始终呈现相互独立的均匀硬币分布，因此所有全量硬干预分布完全相同且复杂度仅为 $O(1)$。然而在反事实世界中，保持外生变量 $(u, v)$ 固定不变并对比 $\mathrm{do}(X_i=0)$ 与 $\mathrm{do}(X_i=1)$ 时，输出满足 $Y_j^{(X_i \leftarrow 0)} \oplus Y_j^{(X_i \leftarrow 1)} = \mathbf{1}[i \in S_j]$。这意味着反事实预言机可完全重构出所有父节点子集 $S_j$。可能的子集组合数达到 $N_{m, d} = \left(\sum_{k=0}^d \binom{m}{k}\right)^m$，对应的反事实描述缺口在 $d=\Theta(n)$ 时同样高达 $\Theta(n^2)$ 比特，打破了“掌握所有干预便掌握反事实”的经验直觉。

4. 模糊度到比特原理与统计学习无免费午餐 论文进一步将具体构造抽象为通用的“模糊度到比特转换原理（Ambiguity-to-Bits Theorem）”：对任意有限 SCM 族，若给定低层级答案 $a$ 对应的兼容高层级可能答案集合为 $\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})$，则最坏情况下的柯尔莫哥洛夫条件复杂度严格满足 $\max K(\mathrm{Ans}_{Q_2}(M) \mid a, n) \geq \log_2 |\mathcal{F}_{Q_2 \mid Q_1}(a; \mathcal{M})| - O(1)$，且在均匀隐藏参数下以指数级高概率成立；其香农熵形式满足条件熵恒等于残余参数熵 $H(\Theta \mid L(\Theta)=a) = \log_2 N$。基于该原理，证明了被动观测学习因果的“无免费午餐”定理：在二分图模型族下，任何观测样本集 $D$ 与图结构 $G$ 的互信息恒为 $I(G; D) = 0$；无论观测样本量多大，被动学习器完全恢复干预分布的概率不超过 $2^{-m^2}$，预测干预边际概率的期望绝对误差不低于 $1/4$。此外，在总变差距离 $\varepsilon < 1/4$ 的有限精度容差下，由于不同模型的干预边缘分布相差至少 $1/2$，$\varepsilon$-近似描述缺口依然牢固保持 $\Theta(n^2)$。

损失函数 / 训练策略¶

作为纯数学与信息论基础理论工作，本文不涉及经验梯度下降或模型训练策略。其核心分析手段基于柯尔莫哥洛夫复杂度的前缀码计数定理（Lemma 3.7）、图论组合计数（Cayley 公式、二项式系数和界限）、截断分解（Truncated Factorization）以及高维有理多项式代数簇测度论证（用于证明在连续忠实高斯或离散忠实分布下，非退化情形的测度为 1）。

实验关键数据¶

主实验¶

论文通过严格数学证明给出了 Pearl 因果层级各层级间在不同图族下的描述缺口分离结论，对比总结如下表所示：

| 模型族 | 给定低层级 ($Q_1$) | 待求解高层级 ($Q_2$) | 隐藏模型模糊度 ($|\mathcal{F}|$) | 描述缺口比特数 ($\Delta(Q_2 \mid Q_1)$) | 最大入度 $d$ | 阶最优性地位 | |---|---|---|---|---|---|---| | 有向树 (Rooted Trees) | $\mathsf{Obs}$ | $\mathsf{Int}_1$ | $n^{n-1}$ | $\Theta(n \log n)$ | $1$ | 有界度最坏情况紧界 | | 二分图族 (Bipartite Graphs) | $\mathsf{Obs}$ | $\mathsf{Int}_1$ | $2^{m^2}$ ($n=2m+1$) | $\Theta(n^2)$ | $\Theta(n)$ | 稠密图信息论上界匹配 | | 模块化异或 (Modular XOR) | $\mathsf{Int}_{\mathrm{all}}$ | $\mathsf{CF}_1$ | $2^m$ ($n=2m$) | $\Theta(n)$ | $1$ | 线性反事实分离界 | | 掩码奇偶校验 (Masked Parity) | $\mathsf{Int}_{\mathrm{all}}$ | $\mathsf{CF}_1$ | $\left(\sum_{k=0}^d \binom{m}{k}\right)^m$ | $\Theta\left(nd \log \frac{en}{d}\right)$ | $d \le m$ | 反事实度敏感最优质界 | | 混淆模块 (Confounded Modules) | $\mathsf{Obs}, \mathcal{G}$ (已知混合图) | $\mathsf{Int}_1$ | $2^m$ ($n=2m$) | $\Theta(n)$ | $1$ | 混淆存在下的图已知不可解 |

消融实验¶

论文在第 7 节详细分析了引入不同因果推断基础假设后，因果描述缺口的坍缩与维持情况（即关于因果公理与结构假设的理论“消融分析”）：

因果假设组合	变量类型 / 噪声假设	观测到干预的描述缺口 $\Delta(\mathsf{Int} \mid \mathsf{Obs})$	核心机制与定理出处	消除缺口所需代价
仅马尔可夫 SCM (无额外假设)	二元变量，局部独立噪声	$\Theta(n^2)$	存在同观测二分图族，Theorem 4.4	需介入至少 $m$ 次干预实验
已知真实因果图 $\mathcal{G}$ + 严格正性	二元变量，局部独立噪声	$O(1)$	截断分解公式直接计算，Proposition 7.1(1)	缺口彻底闭合至常数
已知因果图 $\mathcal{G}$，但无正性假设	二元变量，存在未访问配置	无界（可构造任意有理数 $q$）	零概率状态隐藏任意有理数噪声，Remark B.6	正性条件不可或缺
未知因果图 + 严格正性 + 忠实性	离散二元或线性高斯	$\Theta(n \log n)$	马尔可夫等价类规模至多 $n!$，Proposition 7.1(2)	忠实性将缺口从 $n^2$ 压缩至 $n \log n$
已知混合因果图 $\mathcal{G}$ + 存在隐变量混淆	半马尔可夫，共享外生隐根	$\Theta(n)$	响应类型 $R_t$ 无法被混合图消解，Theorem E.5	图已知仍无法弥合混淆造成的缺口
等误差方差线性高斯 (Identifiable SEM)	连续高斯，等方差独立误差	$O(1)$	LDL 分解唯一识别 DAG，Remark E.7	依靠强代数/统计参数假定识别

关键发现¶

被动观测的极端脆弱性：在二分图反例中，观测分布的互信息为零（$I(G; D)=0$）。这意味着无论被动观测数据量达到几百亿 token，都无法提供区分 $\Theta(n^2)$ 种干预模式的任何有效信息，从信息论底层给出了大语言模型无法单靠纯文本预训练完全自发掌握因果逻辑的有力证据。
实验次数与比特转换关系：根据 Proposition 6.6，若单次干预实验最多能区分 $R$ 种产出分布，则至少需要 $t \ge \lceil \log_2 N / \log_2 R \rceil$ 次实验。在二分图模型中，$N=2^{m^2}$ 且单次硬干预至多提供 $m$ 个比特（$R \le 2^m$），从而严格证明了至少需要 $m \approx n/2$ 次干预实验，且自适应实验策略也无法降低该最坏情况界限。
忠实性假设的定量价值：因果忠实性假设（Faithfulness）能够将未知的图搜索空间从 $2^{\Theta(n^2)}$ 剪枝至马尔可夫等价类上界 $n!$，进而将干预描述缺口牢牢限制在 $\Theta(n \log n)$。

亮点与洞察¶

将因果非可识别性提升至定量计算复杂度：巧妙地将因果答案系统作为计算预言机，引入柯尔莫哥洛夫复杂度，给出了 Pearl 因果层级三大台阶之间跨度到底有“多少比特”的首个严密刻画。
二分图与掩码奇偶校验的优雅反例设计：通过设计对称性与噪声掩码机制，使观测或全量硬干预分布完全退化为常数级别，而将所有因果结构全单射编码至高阶查询，实现了极为纯粹的阶数分离。
对现代因果表示学习与大模型的理论启示：明晰了因果推理能力的获取必须依赖干预或特定结构归纳偏置；任何声称仅通过增大被动语料自回归训练即可全面习得因果本质的论断，在最坏情况和复杂系统下面临根本性的信息论壁垒。

局限与展望¶

模型类别的离散性：主要分离界建立在二元变量和离散 SCM 上；虽然论文在第 7 节拓展到了线性高斯结构方程，但针对非线性加性噪声模型（ANM）和连续光滑动力学系统的描述缺口尚未完全展开。
软干预与随机干预：目前主要针对确定性硬干预 $\mathrm{do}(X=x)$；对于软干预（改变条件机制而非强制赋值）或随机干预下的描述缺口有待进一步形式化。
有限精度的理论拓展：虽然在总变差距离 $\varepsilon < 1/4$ 下证明了二次分离的鲁棒性，但在高维连续测度下的有限样本估计稳定性与信息缺口权衡仍需深入研究。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从算法信息论视角系统定量化 Pearl 因果层级鸿沟，构造精妙，理论奠基性极强。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论数学论证极其完整严密，附录给出了所有引理、定理、有限精度鲁棒性及拓展分析的完整推导。
写作质量: ⭐⭐⭐⭐⭐ 叙述极为清晰，动机明确，从具体模型族到抽象定理的推进层层递进，概念严谨。
价值: ⭐⭐⭐⭐⭐ 深刻揭示了观测与因果之间的信息本质壁垒，对因果发现、因果机器学习及基础模型评测具有深远指导意义。

因果假设组合	变量类型 / 噪声假设	观测到干预的描述缺口 \(\Delta(\mathsf{Int} \mid \mathsf{Obs})\)	核心机制与定理出处	消除缺口所需代价
仅马尔可夫 SCM (无额外假设)	二元变量，局部独立噪声	\(\Theta(n^2)\)	存在同观测二分图族，Theorem 4.4	需介入至少 \(m\) 次干预实验
已知真实因果图 \(\mathcal{G}\) + 严格正性	二元变量，局部独立噪声	\(O(1)\)	截断分解公式直接计算，Proposition 7.1(1)	缺口彻底闭合至常数
已知因果图 \(\mathcal{G}\)，但无正性假设	二元变量，存在未访问配置	无界（可构造任意有理数 \(q\)）	零概率状态隐藏任意有理数噪声，Remark B.6	正性条件不可或缺
未知因果图 + 严格正性 + 忠实性	离散二元或线性高斯	\(\Theta(n \log n)\)	马尔可夫等价类规模至多 \(n!\)，Proposition 7.1(2)	忠实性将缺口从 \(n^2\) 压缩至 \(n \log n\)
已知混合因果图 \(\mathcal{G}\) + 存在隐变量混淆	半马尔可夫，共享外生隐根	\(\Theta(n)\)	响应类型 \(R_t\) 无法被混合图消解，Theorem E.5	图已知仍无法弥合混淆造成的缺口
等误差方差线性高斯 (Identifiable SEM)	连续高斯，等方差独立误差	\(O(1)\)	LDL 分解唯一识别 DAG，Remark E.7	依靠强代数/统计参数假定识别