Paper deep dive
Causal Direction from Convergence Time: Faster Training in the True Causal Direction
Abdulrahman Tamim
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/20/2026, 12:57:43 PM
Summary
The paper introduces Causal Computational Asymmetry (CCA), a method for identifying causal direction by comparing the convergence speed of neural networks trained to predict Y from X versus X from Y. Under the additive noise model with nonlinear injective functions, the causal direction converges faster due to cleaner gradient signals. This is embedded in a broader Causal Compression Learning (CCL) framework that integrates graph structure learning, information compression, and policy optimization.
Entities (10)
Relation Signals (10)
Causal Computational Asymmetry → identifies → causal direction
confidence 95% · principle for causal direction identification... direction that converges faster is inferred to be causal
Causal Computational Asymmetry → ispartof → Causal Compression Learning
confidence 95% · embed CCA into a broader framework termed Causal Compression Learning (CCL)
Causal Computational Asymmetry → uses → Optimization Dynamics
confidence 95% · CCA operates in optimization-time space... based on optimization dynamics
Additive Noise Model → assumes → independence of noise and input
confidence 92% · Y = f(X) + ε with ε ⟆ X
Judea Pearl → developed → do-calculus
confidence 90% · The do-calculus, which Pearl developed to reason about interventions
Causal Compression Learning → integrates → Policy Optimization
confidence 90% · integrates graph structure learning, causal information compression, and policy optimization
Causal Compression Learning → integrates → graph structure learning
confidence 90% · integrates graph structure learning, causal information compression, and policy optimization
Causal Compression Learning → integrates → causal information compression
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce Causal Computational Asymmetry (CCA), a principle for causal direction identification based on optimization dynamics in which one neural network is trained to predict $Y$ from $X$ and another to predict $X$ from $Y$, and the direction that converges faster is inferred to be causal. Under the additive noise model $Y = f(X) + \varepsilon$ with $\varepsilon \perp X$ and $f$ nonlinear and injective, we establish a formal asymmetry: in the reverse direction, residuals remain statistically dependent on the input regardless of approximation quality, inducing a strictly higher irreducible loss floor and non-separable gradient noise in the optimization dynamics, so that the reverse model requires strictly more gradient steps in expectation to reach any fixed loss threshold; consequently, the forward (causal) direction converges in fewer expected optimization steps. CCA operates in optimization-time space, distinguishing it from methods such as RESIT, IGCI, and SkewScore that rely on statistical independence or distributional asymmetries, and proper z-scoring of both variables is required for valid comparison of convergence rates. On synthetic benchmarks, CCA achieves 26/30 correct causal identifications across six neural architectures, including 30/30 on sine and exponential data-generating processes. We further embed CCA into a broader framework termed Causal Compression Learning (CCL), which integrates graph structure learning, causal information compression, and policy optimization, with all theoretical guarantees formally proved and empirically validated on synthetic datasets.
Tags
Links
- Source: https://arxiv.org/abs/2602.22254v1
- Canonical: https://arxiv.org/abs/2602.22254v1
Trouble viewing inline? Open PDF directly →
Full Text
87,793 characters extracted from source content.
Expand or collapse full text
1 Introduction Here is a problem that sounds deceptively simple but has resisted decades of scientific effort: given that two things X and Y are correlated, which one causes the other? This is not a question about data volume. You could have a billion observations of smoking rates and lung cancer rates and still, mathematically, not be able to answer the direction question from data alone. Consider a few concrete cases. Ice cream sales and drowning deaths both spike in summer — does ice cream cause drowning? Obviously not; hot weather drives both. Countries with more hospitals have higher per-capita mortality — do hospitals kill people? No; sick people go to hospitals. Wealthier neighbourhoods have more coffee shops and better educational outcomes — should city planners build more cafes? Getting the direction wrong in any of these examples would lead to useless or actively harmful interventions. The same confusion plays out in high-stakes settings: Does a biomarker cause disease, or does it merely accompany it? Does a minimum wage increase cause unemployment, or do regions with strong economies independently raise wages and have low unemployment? Judea Pearl showed in 1995 that this is not just a practical limitation but a mathematical one: no amount of observational data can answer interventional questions without structural assumptions [1]. The do-calculus, which Pearl developed to reason about interventions, is complete with respect to this impossibility [3]. Every AI system that learns from data—including the largest language models—is permanently on what Pearl calls Rung 1 of the Causal Hierarchy. It can see patterns and make predictions, but it cannot reason about what would actually happen if you forced a change. The first step toward breaking through that barrier is getting the causal direction right. This paper proposes a method for that first step based on a simple observation: a neural network converges faster when trained in the true causal direction than in the reverse. The Central Idea Train a neural network to predict Y from X. Train another to predict X from Y. Measure which one converges faster. The faster direction is the causal one. Formally: CCA(X→Y)=Tfwd−TrevCCA(X→ Y)=T_fwd-T_rev. If CCA<0CCA<0, the forward direction was faster, so predict X→YX→ Y. If CCA>0CCA>0, the reverse was faster, so predict Y→XY→ X. Why does this work? The reason is mechanical, not magical. If Y=f(X)+εY=f(X)+ is the true causal model, training a network forward is chasing a clean target: as the network improves, its errors converge toward ε , which is by definition independent of X. The gradient descent optimizer has a clean, low-variance signal to follow. Flip the direction and train to predict X from Y: now the best you can do is learn E[X∣Y]E[X Y], but recovering X from Y is fundamentally ambiguous because many different X values could have produced the same Y through different noise realizations. The residuals stay statistically entangled with Y throughout training no matter how good the network gets. The optimizer navigates a harder landscape and takes more steps. We call this signal Causal Computational Asymmetry (CCA), prove it formally from three lemmas, and embed it in a full causal learning framework called Causal Compression Learning (CCL). 1.1 Contributions 1. CCA criterion (§4): first formal proof that the causal direction always converges in strictly fewer expected gradient steps. Grounded in three lemmas on residual dependence, landscape complexity, and SGD convergence rate. 2. CCL framework (§3): a joint objective combining MDL graph regularization, causal information bottleneck compression, interventional policy optimization, and CCA direction scoring. All theorems are proved. 3. Experiments (§6): 26/30 correct on synthetic data across six architectures; 30/30 on injective DGPs; 96% accuracy on the Tübingen real-world benchmark; all three boundary conditions verified experimentally. 4. Boundary conditions (§4): CCA fails on linear Gaussian mechanisms, non-injective functions, and un-normalized data. All three are predicted theoretically before experiments run, then confirmed—knowing when a method breaks is just as important as knowing when it works. 1.2 Organization §2 covers background and related work. §3 presents the CCL objective. §4 introduces CCA formally. §5 contains supporting theorems. §6 reports all experiments. §7 gives the training algorithm. §8 compares CCL+ against existing systems. §9 discusses limitations. 2 Background and Related Work 2.1 Pearl’s Causal Hierarchy To appreciate what CCA is actually doing, it helps to understand the conceptual landscape it sits within. Pearl’s Causal Hierarchy organizes causal reasoning into three rungs, each strictly more powerful than the one below, and each requiring fundamentally different tools. Rung 1: Seeing (Observation). The question is P(Y∣X=x)P(Y X=x): if we observe X take a particular value, what do we expect Y to be? This is where all of classical statistics and machine learning lives—regression, classification, language modeling, recommendation systems. You can be extraordinarily good at Rung 1 and still be unable to answer causal questions. A Rung 1 model trained on hospital data can tell you that patients in the ICU are more likely to die. It cannot tell you whether sending more patients to the ICU would increase or decrease mortality. That requires knowing the causal direction. Rung 2: Doing (Intervention). The question is P(Y∣do(X=x))P(Y (X=x)): what happens if we force X to a particular value, cutting its normal causal parents? This is what a randomized controlled trial achieves by randomly assigning treatment—randomization breaks the selection bias that confounds observational data. Pearl proved this question is in general unreachable from Rung 1 data alone without structural assumptions [1]: no matter how much observational data you accumulate, you cannot derive interventional conclusions without a causal model. Rung 3: Imagining (Counterfactuals). The question is: what would have happened under a different choice? A patient took Drug A and survived—would they have survived on Drug B? This is the domain of legal liability, moral responsibility, and regret. Rung 3 requires a complete Structural Causal Model (SCM): a tuple ℳ=⟨U,V,F,P(U)⟩M= U,V,F,P(U) where U are unobserved background variables, V are observed variables, and F=fiF=\f_i\ defines how each variable is generated: vi=fi(pai,ui)v_i=f_i(pa_i,u_i). CCA addresses a prerequisite to all three rungs. Before you can build a causal graph and start climbing the hierarchy, you need to know which direction the edges point in the first place. 2.2 Algorithmic Complexity and MDL There is a deep connection between causality and compression. Solomonoff proved in 1964 that the optimal inductive prior weights hypotheses by 2−K(h)2^-K(h), where K(h)K(h) is the Kolmogorov complexity (minimum program length) of the hypothesis [4, 5]. Simpler explanations deserve more prior weight—this is the algorithmic grounding for Occam’s razor. Rissanen’s Minimum Description Length (MDL) principle [6] makes this computable: the best model is the one that compresses the data most efficiently (minimum total description length of model + data given model). Crucially, the true causal factorization is always shorter to describe than a non-causal one. If X→YX→ Y is the true direction, the data is efficiently encoded as: describe P(X)P(X), then describe Y as f(X)f(X) plus small independent noise. The reverse encoding is longer because the noise is entangled with the signal. MDL naturally discovers the causal direction by selecting the shortest description. For linear Gaussian SCMs this is asymptotically equivalent to BIC [13]. 2.3 PAC Learning and the Causal Complexity Gap Valiant’s PAC framework [7] asks: how many examples do we need to guarantee that a learning algorithm generalizes? The answer depends on the VC dimension of the hypothesis class. The problem is that VC dimension is purely statistical: it treats a model capturing X→YX→ Y through a direct mechanism identically to one capturing the same pattern through a hidden confounder. Both fit the data; only one generalizes under intervention. For example, a model trained to predict crop yields from fertilizer application in one region may fail completely in a new region if the original correlation was confounded by soil type. VC dimension cannot distinguish these cases. CCL replaces VC dimension with dc(G)d_c(G), the number of edges in the minimal I-map of the causal graph (defined in §3.2). This captures true causal complexity, so sample bounds scale with actual causal structure: a sparser causal graph (fewer direct mechanisms) provably requires fewer samples to identify. 2.4 The Information Bottleneck and Its Causal Extension The Information Bottleneck [9] finds a compressed representation T of input X that is maximally predictive of target Y: minimize I(X;T)−β⋅I(T;Y)I(X;T)-β· I(T;Y). Elegant in principle, but it has a serious causal blind spot. When a hidden confounder Z drives both X and Y, the IB will happily retain Z-related features in T because they are statistically predictive of Y—even though they carry zero causal information. A drug trial where healthier patients self-select into treatment will encode “patient health” in the bottleneck because it predicts outcomes statistically, not because the drug does anything. Simoes, Dastani, and van Ommen [10] fix this by replacing I(T;Y)I(T;Y) with the causal mutual information Ic(Y∣do(T))I_c(Y (T)): how much does T tell us about Y when we force T to change? This quantity is zero for any association that flows through a confounder rather than a direct causal path. 2.5 Causal Reinforcement Learning Standard RL treats the environment as a black box and maximizes reward by trial and error. But in most real-world settings actions have genuine causal effects, and ignoring causal structure leads to policies that fail when the environment changes. Bareinboim, Zhang, and Lee established causal RL (CRL) [11], proving (Theorem 7) that any policy whose causal effect is identifiable in a known graph G can be evaluated via do-calculus from interventional data. Think of it as: once you know the causal graph, you can safely reason about what policies will achieve under intervention, not just what correlates with reward in the training distribution. CCL builds its policy optimization component directly on this result. 2.6 Causal Direction Discovery and the Position of CCA How do existing methods decide which variable causes which? They fall into three classes by what mathematical signal they exploit. Residual independence (data space). RESIT [35] fits a nonlinear regression in each direction and tests whether the residuals are statistically independent of the input. If X→YX→ Y is true, residuals of predicting Y from X should be pure noise, independent of X. The method works well but fails when the structural function is non-injective—for example Y=X2Y=X^2 maps both +1+1 and −1-1 to the same output, so the reverse regression can also produce independent-looking residuals by symmetry of P(X)P(X). Description length (complexity space). IGCI [19] compares Kolmogorov complexity in each direction; the true causal direction should have the shorter description. SkewScore [36] uses the skewness of the score function ∇logp∇ p as a direction signal, best suited to heteroscedastic noise. Optimization time (this work). CCA measures how many gradient descent steps a neural network needs to converge in each direction. This signal is entirely distinct from the two above: it operates on the optimization landscape, not on the data distribution or its compression. It is architecture-robust—the same asymmetry appears across Tanh/ReLU activations, Adam/SGD/RMSProp optimizers, and varying depth and width—because the signal is a property of the mathematical structure of the ANM, not of any particular network configuration. To our knowledge no prior work has formally proposed or theoretically grounded optimization convergence time as a causal direction criterion. 3 The CCL Framework 3.1 Why None of the Four Traditions Works in Isolation CCL combines four theoretical traditions that each solve part of the problem but fail critically when used alone. Understanding the failure modes is the clearest way to understand why the combination is necessary. Compression alone compresses the wrong thing. Suppose education level (X) and income (Y) are both driven by family wealth (Z). MDL without a causal graph finds the shortest description of the joint distribution, which happens to be a direct X→YX→ Y link—shorter than the two-step Z→XZ→ X, Z→YZ→ Y mechanism. Compression cannot distinguish correlation from causation; it just finds the most efficient encoding of what it observes. PAC theory alone certifies the wrong quantity. VC dimension counts the capacity of a model to fit arbitrary labelings. Whether X→YX→ Y runs through a genuine mechanism or a spurious confounder, both fit the same training data equally well and get the same generalization certificate. The confounded model will fail the moment the confounding changes—say, when a policy intervention removes the family-wealth effect. Pearl’s causal framework alone has no unique solution from data. Without a complexity penalty, any fully connected graph is consistent with the data (it vacuously satisfies Pearl’s identifiability constraints). You need an additional principle—like MDL—to select among Markov-equivalent graphs. The Causal IB alone is circular. You need a causal graph to compute Ic(Y∣do(T))I_c(Y (T)), because the do-operator requires a structural model. But you need a good representation T to learn the graph accurately. Each depends on the other. The failures are circular: each component needs the others to function. CCL closes this loop by solving all four problems jointly via alternating optimization. Table 1: Failure modes when each tradition operates without the others. Tradition Failure mode in isolation Compression Compresses spurious correlations; fails with confounders PAC bounds Bounds statistical (not causal) error; certifies confounded models as good Causality No unique solution without MDL; any connected graph satisfies identifiability Causal IB Undefined without a causal graph; IcI_c requires a structural model 3.2 Notation Throughout the paper, ℳ∗M^* denotes the true environment SCM, G the learned causal graph, T the compressed representation, π the policy, and R the reward. The parameters β,λ1,λ2,λ3≥0β, _1, _2, _3≥ 0 are tradeoff weights. Causal complexity measure. dc(G)d_c(G) denotes the number of edges in the minimal I-map of G: the smallest subgraph preserving all conditional independence relations entailed by the true graph G∗G^*. This replaces raw edge count |EG||E_G|, which is representation-dependent. The minimal I-map is unique up to Markov equivalence and invariant under graph reparameterization [2]. Practically: sample complexity bounds derived using dc(G)d_c(G) scale with actual causal structure, not with arbitrary modeling choices. A sparser causal graph (fewer direct mechanisms) provably requires fewer data points to identify reliably. τmix _mix is the Markov chain mixing time of the policy trajectory. |Emax||E_ | is a pre-specified upper bound on graph edges used in Theorem 5.8. 3.3 The CCL Objective Definition 3.1 (CCL Objective). minG,T,πℒCCL _G,\,T,\,π\;L_CCL =−π[R(Y)]⏟reward+λ1[I(X;T)−βIc(Y∣do(T))]⏟Causal IB = -E_π[R(Y)]_reward+ _1[I(X;T)-β\,I_c(Y (T))]_Causal IB (1) +λ2⋅MDL(G)⏟MDL + _2·MDL(G)_MDL subject to P(Y∣do(π))P(Y (π)) being identifiable in G via Pearl’s do-calculus. Term 1 maximizes expected reward under the policy—this is the reinforcement learning component. The CCL agent is not just learning a causal model for its own sake; it is learning one in order to act better in the world. Term 2 is the Causal Information Bottleneck: compress X into T while maximizing causal (not merely statistical) information about Y. The β parameter controls the compression-informativeness tradeoff. Critically, using IcI_c instead of plain I(T;Y)I(T;Y) means the bottleneck ignores confounded correlations and retains only the signal that flows through direct causal mechanisms—it will not be fooled by a drug trial where healthier patients self-select into treatment. Term 3 penalizes graph complexity using MDL: among all graphs consistent with the data, prefer the simplest one. This prevents the optimizer from adding spurious edges just because they improve the compression objective locally. The identifiability constraint is essential: it ensures the policy’s causal effect can actually be computed from the learned graph using Pearl’s do-calculus rules. Without it, we might learn a graph that looks good but does not support the interventional queries we actually need to answer. 4 Causal Computational Asymmetry 4.1 Intuition Before the Math Before writing down formal statements, here is the core idea in plain terms. You have a true causal model: Y=f(X)+εY=f(X)+ . Some nonlinear function of X, plus some independent noise—think of X as temperature and Y as ice cream sales, where f captures the nonlinear seasonal relationship and ε captures everything else (local events, promotions, etc.). If you train a neural network to predict Y from X, you are asking it to learn f. As training progresses, the residuals—the prediction errors—converge toward ε , which is by assumption independent of X. The gradient signal is clean: the optimizer can reliably tell which direction to move because the noise is not informative about the input. Now flip it. Train a network to predict X from Y: predict temperature from ice cream sales. The best you can do is learn E[X∣Y]E[X Y]—the expected temperature given sales. But this is fundamentally harder. Observing a particular sales figure Y=yY=y is consistent with many different temperatures X, because the noise ε can have produced the same sales from different underlying conditions. The residuals—the errors in predicting temperature—stay correlated with Y throughout training, no matter how good the network gets, because the noise is permanently entangled with the target. The optimizer faces structured, non-separable noise at every gradient step. It takes more steps. This asymmetry is not a quirk of any specific network architecture or optimizer. It is a mathematical property of the additive noise model itself. That is why the signal is robust across the six different architectures tested in the experiments. Core Intuition Y=f(X)+εY=f(X)+ , ε⟂X X. Forward (X→YX→ Y): residuals converge to ε⟂X X. Clean gradient signal. Optimizer converges fast. Reverse (Y→XY→ X): residuals stay correlated with Y at any finite approximation. Noisy, structured gradient signal. Optimizer converges slow. CCA measures this gap. 4.2 Formal Setup We work with two real-valued random variables X and Y. Data (ANM assumption). Y=f(X)+εY=f(X)+ , where: • f is nonlinear, LfL_f-Lipschitz, and injective (one-to-one: distinct X values map to distinct f(X)f(X) values); • ε is zero-mean noise with ε⟂X X (independent of X) and finite variance Var(ε)=σ2<∞Var( )=σ^2<∞; • P(X)P(X) has full support with finite fourth moments. Networks. We train two multilayer perceptrons (MLPs): a forward network gθg_θ that predicts Y from X, and a reverse network hϕh_φ that predicts X from Y. Both use MSE loss and SGD with step size η>0η>0 and mini-batch size m, initialized randomly with bounded weight norms ‖θ‖2,‖ϕ‖2≤B\|θ\|_2,\|φ\|_2≤ B. Convergence. Training for each network stops when the held-out MSE drops below threshold τ>0τ>0. We write TfwdT_fwd for the number of steps the forward network needs and TrevT_rev for the reverse. If a network never converges, training is capped at TmaxT_ steps. Scale Normalization (mandatory). Both X and Y are z-scored before any training begins: X~=X−μXσX,Y~=Y−μYσY. X= X- _X _X, Y= Y- _Y _Y. This is not optional. Without it, differences in output scale dominate gradient magnitudes and can completely reverse the convergence ordering, flipping the CCA signal from the correct direction to the wrong one. For example, Y=X3Y=X^3 with X∼(0,1)X (0,1) has Var(Y)≈15Var(Y)≈ 15, so the forward objective operates at a loss scale 15 times larger than the reverse objective. A forward network without standardization sees gradients an order of magnitude larger than the reverse — the scale asymmetry swamps the causal signal entirely. With standardization: 26/30 correct. Without: 6/30 correct (no better than the scale-induced inversion). 4.3 Notation Table Table 2: Symbols used in the CCA framework. Symbol Meaning f True structural mechanism: Y=f(X)+εY=f(X)+ gθg_θ Forward network: predicts Y from X hϕh_φ Reverse network: predicts X from Y ε Structural noise, independent of X, zero-mean TfwdT_fwd Steps for gθg_θ to reach MSE <τ<τ TrevT_rev Steps for hϕh_φ to reach MSE <τ<τ TmaxT_ Step cap if convergence not reached η SGD step size τ Convergence threshold dc(G)d_c(G) Edge count of the minimal I-map of G τmix _mix Markov chain mixing time μ Polyak–Łojasiewicz (PL) condition constant 4.4 The Three Lemmas The main theorem follows from three lemmas, each doing a specific job. Lemma 1 establishes a structural property of the reverse residuals. Lemma 2 translates that into a claim about the optimization landscape. Lemma 3 translates the landscape claim into a convergence time claim. Lemma 4.1 (Residual Dependence). Under the ANM with injective f, the optimal reverse regression target is h∗(Y)=E[X∣Y]h^*(Y)=E[X Y], and for any finite-capacity approximation hϕ≠h∗h_φ≠ h^*, the residuals Rrev=X−hϕ(Y)R_rev=X-h_φ(Y) satisfy: Cov(Rrev,Y)≠0.Cov(R_rev,\,Y)≠ 0. In contrast, the forward residuals Rfwd=Y−gθ(X)R_fwd=Y-g_θ(X) satisfy Cov(Rfwd,X)→0Cov(R_fwd,X)→ 0 as gθ→fg_θ→ f. Why this matters. This lemma establishes something fundamental: no matter how good your reverse network gets—as long as it is not the exact population optimum—its prediction errors are still statistically linked to Y. The network cannot fully untangle X from Y because the structural noise ε is baked into Y irreversibly. Think of it like trying to unmix salt from seawater chemically: even if you recover most of the salt, the trace contamination remains and is detectable. The forward network faces no such structural entanglement—its errors can cleanly converge to pure noise. Proof. At the population optimum h∗=E[X∣Y]h^*=E[X Y], the residual Rrev∗=X−E[X∣Y]R^*_rev=X-E[X Y] satisfies E[Rrev∗∣Y]=0E[R^*_rev Y]=0 by the law of iterated expectations, but Var(Rrev∗∣Y)=Var(X∣Y)>0Var(R^*_rev Y)=Var(X Y)>0 since f is injective and ε is nontrivial, so X is genuinely not determined by Y alone. For any finite-capacity approximation hϕ≠h∗h_φ≠ h^*, define the approximation error δϕ(Y)=hϕ(Y)−h∗(Y) _φ(Y)=h_φ(Y)-h^*(Y). Then: Rrev=X−hϕ(Y)=Rrev∗−δϕ(Y).R_rev=X-h_φ(Y)=R^*_rev- _φ(Y). Since δϕ _φ is a non-constant function of Y (because hϕ≠h∗h_φ≠ h^*) and Rrev∗R^*_rev has non-zero conditional variance given Y: Cov(Rrev,Y) (R_rev,\,Y) =Cov(Rrev∗,Y)−Cov(δϕ(Y),Y) =Cov(R^*_rev,\,Y)-Cov( _φ(Y),\,Y) =−Cov(δϕ(Y),Y)≠0, =-Cov( _φ(Y),\,Y)≠ 0, because δϕ _φ is a non-constant measurable function of Y, so its covariance with Y is nonzero under the full-support condition on P(X)P(X). In contrast, the forward residual Rfwd=Y−gθ(X)=f(X)+ε−gθ(X)R_fwd=Y-g_θ(X)=f(X)+ -g_θ(X) converges to ε at the optimum, and Cov(ε,X)=0Cov( ,X)=0 by the ANM assumption. □ ∎ Lemma 4.2 (Landscape Complexity). Under the ANM with nonlinear injective f and scale normalization, let ℒfwd∗=E[ε2]L^*_fwd=E[ ^2] and ℒrev∗=E[Var(X∣Y)]L^*_rev=E[Var(X Y)] be the population-level minimum losses in each direction. Then: (i) ℒfwd∗=σε2<1L^*_fwd=σ^2_ <1 (since after z-scoring Y has unit variance and ε⟂X X contributes only a fraction of Var(Y)Var(Y)). (i) ℒrev∗=E[Var(X∣Y)]L^*_rev=E[Var(X Y)], which is structurally larger and more heteroscedastic than σε2σ^2_ because Var(X∣Y)Var(X Y) varies with Y whenever f is nonlinear and injective. (i) The reverse MSE landscape has a non-separable noise floor: the conditional variance Var(X∣Y=y)Var(X Y=y) varies with y, so no single network width can uniformly approximate h∗(Y)h^*(Y) with uniformly small residuals. This creates a systematically harder optimization problem: gradients in the reverse direction must simultaneously fit a more complex conditional mean while working against a spatially non-uniform noise floor, inflating the effective number of steps required to drive held-out MSE below any fixed threshold τ. Formally, for any finite-capacity hϕh_φ, the gradient covariance structure satisfies: Cov(Rrev2,‖∇ϕhϕ(Y)‖2)≠ 0,Cov (R_rev^2,\;\| _φh_φ(Y)\|^2 )\;≠\;0, because Rrev2=(X−hϕ(Y))2R_rev^2=(X-h_φ(Y))^2 is correlated with ‖∇ϕhϕ‖2\| _φh_φ\|^2 through their shared dependence on Y, while the analogous forward covariance Cov(Rfwd2,‖∇θgθ(X)‖2)→0Cov(R_fwd^2,\| _θg_θ(X)\|^2)→ 0 as gθ→fg_θ→ f (because Rfwd→ε⟂XR_fwd→ X). An important empirical note. Instantaneous gradient norm variance at a single training phase is not a reliable proxy for this structural complexity difference. Which direction shows larger gradient norm variance at any given moment depends on the current parameter values, the DGP’s curvature, and the training phase. The theoretically meaningful quantity is the gap in time required to drive held-out MSE below τ, which is directly measured by Trev−TfwdT_rev-T_fwd. This is why CCA measures convergence time, not gradient statistics. Why this matters. Lemma 1 showed the reverse residuals stay correlated with Y. Lemma 2 shows what that correlation costs in terms of the optimization problem. The reverse network has a higher minimum loss (it can never get better than E[Var(X∣Y)]E[Var(X Y)]), and the gradient noise it faces is spatially structured in a way that cannot be averaged away by larger batches. Proof. By the ANM and the law of total variance: Var(X)=E[Var(X∣Y)]+Var(E[X∣Y]),Var(X)=E[Var(X Y)]+Var(E[X Y]), so ℒrev∗=E[Var(X∣Y)]≤Var(X)=1L^*_rev=E[Var(X Y)] (X)=1 (after standardization). Equality holds only when E[X∣Y]E[X Y] is constant, i.e., when X⟂YX Y; under the ANM with nonlinear injective f, X and Y are dependent, so strict inequality holds. For claim (i), Var(X∣Y=y)Var(X Y=y) is constant in y only when X and Y are jointly Gaussian, which requires f to be linear. For nonlinear f, the conditional variance is a nontrivial function of y, so the reverse optimization landscape has a spatially varying noise floor. Any mini-batch gradient estimate ∇^ϕ ∇_φ at iterate ϕt _t has variance: 1mE[(X−hϕ(Y))2⋅‖∇ϕhϕ(Y)‖2], 1m\,E [(X-h_φ(Y))^2·\| _φh_φ(Y)\|^2 ], which does not factorize when RrevR_rev and ‖∇ϕhϕ‖\| _φh_φ\| both depend on Y. Lemma 4.1 established that RrevR_rev is correlated with Y throughout training, so this non-factorizability persists throughout training, creating a harder effective optimization problem. □ ∎ Lemma 4.3 (Harder Landscape, More Steps). Consider two objectives ℒ1L_1 and ℒ2L_2 that both satisfy the Polyak–Łojasiewicz (PL) condition with constant μ>0μ>0, trained by SGD with identical step size η and mini-batch size m. If either: (a) the population minimum of ℒ2L_2 exceeds that of ℒ1L_1 by Δ∗>0 ^*>0, or (b) the gradient covariance structure of ℒ2L_2 is non-separable (as established for the reverse direction in Lemma 4.2), then the expected steps T2T_2 for ℒ2L_2 to reach threshold τ satisfies: T2≥T1+Ω(1ημ),T_2\;≥\;T_1+ \! ( 1ημ ), where T1T_1 is the corresponding step count for ℒ1L_1. Why the PL condition? The Polyak–Łojasiewicz condition says that the gradient norm is lower-bounded by the suboptimality: ‖∇ℒ‖2≥2μ(ℒ−ℒ∗)\| \|^2≥ 2μ(L-L^*). This is weaker than convexity — it holds for many overparameterized neural networks near their minima — and it is what gives us clean convergence rates. Proof. Under the PL condition with constant μ and gradient noise variance σ2σ^2, the standard SGD convergence bound [38] gives: E[ℒ(θt)−ℒ∗]≤(1−2ημ)t(L0−L∗)+ησ22μ.E[L( _t)-L^*]\;≤\;(1-2ημ)^t(L_0-L^*)+ ησ^22μ. For condition (a): if ℒ2∗>ℒ1∗L^*_2>L^*_1, then for τ in the range (ℒ1∗,ℒ1∗+Δ∗)(L^*_1,\,L^*_1+ ^*), objective 1 can reach τ but objective 2 cannot reach τ from above (it has ℒ2∗>τL^*_2>τ). For τ above both optima, objective 2 must close a strictly larger effective gap, requiring more steps. For condition (b): non-separability of the gradient covariance means the effective gradient noise at each step is correlated with the current residual magnitude and the local geometry. This creates an adaptive noise floor that persists throughout training rather than decaying as O(1/t)O(1/t). It inflates the ησ22μ ησ^22μ bias term relative to the separable case where σ2σ^2 can be treated as a fixed constant. In both cases, T2≥T1+Ω(1/(ημ))T_2≥ T_1+ (1/(ημ)). □ ∎ 4.5 The CCA Asymmetry Theorem Theorem 4.4 (CCA Asymmetry). Under the ANM with nonlinear injective f and scale normalization, if the forward and reverse objectives both satisfy the PL condition locally near their respective minima with constant μ>0μ>0, then: E[Tfwd]<E[Trev].E[T_fwd]\;<\;E[T_rev]. The expected number of SGD steps to reach loss threshold τ is strictly smaller in the causal direction than in the anti-causal direction. Proof. By Lemma 4.1, reverse-direction residuals remain correlated with Y throughout training for any finite-capacity approximation. By Lemma 4.2, this correlation implies (i) a higher population-minimum loss for the reverse direction (ℒrev∗=E[Var(X∣Y)]>σε2=ℒfwd∗L^*_rev=E[Var(X Y)]>σ^2_ =L^*_fwd) and (i) non-separable gradient covariance in the reverse direction, both constituting a harder effective optimization problem. By Lemma 4.3, both conditions independently imply that the reverse direction requires strictly more expected steps to reach threshold τ. Therefore E[Trev]>E[Tfwd]E[T_rev]>E[T_fwd]. □ ∎ Remark 4.5 (Scope of the Theorem). The PL condition is used locally near the minima. For overparameterized MLPs, the forward objective often satisfies this near the global minimum. The reverse landscape is less regular, so the theorem gives a lower bound on the convergence time gap. The empirical gap observed in experiments (for example, forward convergence in 161 steps vs. reverse never converging in 3000 steps on the cubic DGP) is substantially larger than the theoretical lower bound, because the reverse landscape also contains flat regions and saddle points not captured by the PL approximation. 4.6 The Formal CCA Definition Definition 4.6 (Causal Computational Asymmetry). The CCA score for candidate edge X→YX→ Y is: CCA(X→Y)=Tfwd−TrevCCA(X→ Y)=T_fwd-T_rev where TfwdT_fwd is the steps for a network predicting Y from X to reach loss τ, and TrevT_rev is the steps for a network predicting X from Y. A negative score means the forward direction converged faster: predict X→YX→ Y. A positive score means the reverse converged faster: predict Y→XY→ X. For a full causal graph, the score aggregates over all edges: CCA(G)=∑(i,j)∈G[Tfwd(i,j)−Trev(i,j)].CCA(G)= _(i,j)\,∈\,G [T_fwd^(i,j)-T_rev^(i,j) ]. 4.7 The CCL+ Extended Objective Adding the CCA term to the base CCL objective gives the full CCL+ objective: ℒCCL+= _CCL+= −π[R(Y)]+λ1[I(X;T)−βIc(Y∣do(T))] -E_π[R(Y)]+ _1 [I(X;T)-β\,I_c(Y (T)) ] (2) +λ2MDL(G)+λ3CCA(G) + _2\,MDL(G)+ _3\,CCA(G) The CCA term enters only through the XGES edge scoring function: Score(G)=MDL(G)+λ3⋅CCA(G)Score(G)=MDL(G)+ _3·CCA(G). This means CCA influences which edge orientations the graph search prefers, but it does not independently move the reward or the compression terms. 4.8 Boundary Conditions Remark 4.7 (Three Established Boundary Conditions). CCA has three confirmed boundary conditions where it will not work correctly. (1) Linear Gaussian mechanisms. When f is linear, the ANM is not identifiable in either direction by any method — this is a fundamental result, not a limitation of CCA specifically. Gaussian symmetry makes the forward and reverse optimization problems indistinguishable. CCA produces symmetric convergence, confirmed experimentally (0/30 correct for Y=2X+εY=2X+ , indistinguishable from random). (2) Non-injective mechanisms. Lemma 4.1 requires f to be injective. When f is not one-to-one, Peters et al. [35] (Proposition 23) showed that ANM identifiability fails entirely. For Y=X2+εY=X^2+ with X∼(0,1)X (0,1), the reverse regression target E[X∣Y]E[X Y] equals zero for all values of Y by symmetry of P(X)P(X). The reverse network converges in O(1)O(1) steps (it just needs to learn to predict zero), producing Trev≪TfwdT_rev T_fwd and a negative CCA score that predicts the wrong direction. Critically, this is not CCA working correctly: it is a degenerate collapse of the reverse target to a constant. This boundary condition is confirmed in 30/30 seeds. The X2X^2 DGP should not be used to benchmark or validate CCA. (3) Scale contamination without normalization. Without z-scoring both variables before training, output scale differences dominate gradient magnitudes and can reverse the empirical convergence ordering. This is confirmed for Y=X3+εY=X^3+ without standardization: 6/30 correct vs. 26/30 with standardization. Z-scoring is a mandatory preprocessing step, not an optional one. 5 Mathematical Proofs: The CCL Supporting Theorems This section contains the full CCL theoretical apparatus. These theorems establish that the CCL optimization converges, that the causal graph is consistently learned, that the information compression preserves the causal structure, and that the sample complexity scales with causal rather than statistical complexity. Each subsection states one or more theorems and gives the full proof. 5.1 Lemma MDL-R: Consistency on Compressed Representations The CCL loop applies MDL-based graph scoring to compressed representations T(k)T^(k) produced by the CIB encoder at iteration k. This lemma establishes that MDL scoring remains consistent on these compressed representations as the encoder converges, even though the representation is changing throughout training. Lemma 5.1 (MDL Consistency on Compressed Representations). Let enckk≥0\enc_k\_k≥ 0 be a sequence of encoders with Lipschitz constant L<∞L<∞, satisfying the GEM property (each update decreases the variational objective). Define T(k)=enck(X)T^(k)=enc_k(X) and let T∗T^* denote the population-optimal representation. Suppose the encoder sequence satisfies ηk=O(1/k) _k=O(1/k): ‖enck−enc∗‖∞≤Cenck,Cenc<∞.\|enc_k-enc^*\|_∞\;≤\; C_enck, C_enc<∞. (3) Then the MDL-selected graph G^(n,k)=argminGMDL(G;T(k)) G(n,k)= _G\,MDL(G;\,T^(k)) satisfies P[G^(n,k)=G∗]→1P[ G(n,k)=G^*]→ 1 as n→∞n→∞ and k→∞k→∞. Proof. Step 1 (Encoder convergence rate). The CIB encoder minimizes a variational objective that decreases monotonically at each iteration [39, 40] (GEM property). The parameter space is compact. By Wu [40] (Theorem 1), all limit points are stationary. Under diagonal covariance (Assumption F2), the CIB objective is strictly convex in each encoder dimension, giving convergence rate O(1/k)O(1/k) [39], yielding ηk=O(1/k) _k=O(1/k) as stated. Step 2 (MDL score perturbation bound). By the L-Lipschitz condition and (3): |MDL(G;T(k))−MDL(G;T∗)| |MDL(G;\,T^(k))-MDL(G;\,T^*) | ≤nCLηk+O(logn)=nCLCenck+O(logn). ≤\;nC_L _k+O( n)= nC_LC_enck+O( n). Step 3 (MDL consistency on T∗T^*). By Kaltenpoth and Vreeken [13] Theorem 6, P[G^(n;T∗)=G∗]→1P[ G(n;\,T^*)=G^*]→ 1 as n→∞n→∞, with MDL gap Δmin(n)≥c⋅logn _ (n)≥ c· n for some constant c>0c>0. Step 4 (Dominance condition). The correct graph retains lower MDL on T(k)T^(k) whenever 2⋅nCLCenck<clogn−O(logn)2· nC_LC_enck<c n-O( n), i.e., k>2nCLCencc′lognk> 2nC_LC_encc n for some c′>0c >0. For any fixed n, taking k≥k0(n)=⌈2nCLCenc/(c′logn)⌉k≥ k_0(n)= 2nC_LC_enc/(c n) ensures the perturbation is dominated by Δmin(n) _ (n). As both n,k→∞n,k→∞ jointly (e.g., k≥nk≥ n suffices since n/logn→∞ n/ n→∞), P[G^(n,k)=G∗]→1P[ G(n,k)=G^*]→ 1. □ ∎ 5.2 Theorem F: Faithfulness Preservation Under CIB Compression Faithfulness is the condition that every conditional independence in the distribution is entailed by the causal graph (no accidental independence). If compression destroys faithfulness, the subsequent graph learning step will make errors. Theorem F shows that the CIB compression preserves faithfulness, locally near the optimal encoder. Assumption 1 (F1). For every identifiable edge (Xi→Y)(X_i→ Y) in GkG_k: Ic(Y∣do(Ti);Gk)>0I_c(Y (T_i);\,G_k)>0. Assumption 2 (F2). The encoder uses diagonal covariance [12], preventing distinct causal parents from merging into a single latent dimension. Assumption 3 (F3). P(X,Y)P(X,Y) has full support. Assumption 4 (F4). The encoder sequence satisfies ‖enck−enc∗‖∞≤ηk\|enc_k-enc^*\|_∞≤ _k with ηk=O(1/k) _k=O(1/k), as established by Lemma 5.1. Theorem 5.2 (Faithfulness Preservation — Local Convergence). Under Assumptions F1–F4, as k→∞k→∞, every local minimum of the CIB objective in a neighborhood of enc∗enc^* satisfies the faithfulness condition between P(T(k))P(T^(k)) and GT∗G^*_T up to ϵG _G in total variation for any ϵG>0 _G>0. Note: This is a local convergence result. It holds in a neighborhood of the population-optimal encoder enc∗enc^*. Global convergence from arbitrary initialization is not claimed; for general nonconvex encoder families the landscape may contain other local minima. The finite-sample convergence rate is an acknowledged open problem (see Remark 5.3). Proof. Forward direction. If Xi⟂Xj∣ZX_i X_j Z in G∗G^*, the Markov condition gives (Xi⟂Xj∣Z)P(V)(X_i X_j Z)_P(V). Since Ti=enci(Xi)T_i=enc_i(X_i) and Tj=encj(Xj)T_j=enc_j(X_j) are deterministic functions under Assumption F2, the data processing inequality gives (Ti⟂Tj∣enc(Z))P(T)(T_i T_j (Z))_P(T) for all k. Reverse direction. Suppose (Ti⟂Tj∣TZ)P(T(k))(T_i T_j T_Z)_P(T^(k)) but XiX_i is not d-separated from XjX_j given Z in G∗G^*. Faithfulness of P(V)P(V) w.r.t. G∗G^* gives I(Xi;Xj∣Z)>0I(X_i;\,X_j Z)>0. By Assumption F4, ηk→0 _k→ 0, so for k in a neighborhood of convergence the encoder is sufficiently close to enc∗enc^*. Simoes et al. [10] Theorem 3 then gives I(Ti;Tj∣TZ)>0I(T_i;\,T_j T_Z)>0, contradicting the assumed conditional independence. □ ∎ Remark 5.3 (Finite-Sample Boundary Condition). For finite k and finite n, GkG_k may differ from G∗G^*, and the faithfulness guarantee holds only relative to the current iterate. The rate at which this error shrinks as k,n→∞k,n→∞ has not been quantified. This is an acknowledged open problem. 5.3 Theorem S: MDL Efficiency Inheritance Theorem 5.4 (MDL Efficiency Inheritance). For linear Gaussian SCMs and additive noise models with sub-Gaussian noise, |M(G)−K(G)|≤O(logn)|M(G)-K(G)|≤ O( n). Against hypothesis classes that represent the full joint distribution without causal factorization (non-parametric learners), CCL under MDL achieves the causal optimum within poly(n)poly(n) overhead, while such learners require exponentially more samples. This advantage does not extend to parametric learners that also factorize over edges. Proof. Kaltenpoth and Vreeken [13] Theorem 6 establishes that MDL converges to BIC asymptotically for linear Gaussian SCMs. BIC is consistent by Schwarz [15] and Bühlmann et al. [16]. The gap K(G)≤M(G)≤K(G)+O(logn)K(G)≤ M(G)≤ K(G)+O( n) follows from Li and Vitányi [17] Theorem 2.1.1. Against non-parametric learners: representing a causal edge requires O(log|V|)O( |V|) bits; representing the full joint density to precision ε=O(1/n) =O(1/ n) requires O(n)O(n) bits. The description length gap is ΔK=Ω(n) K= (n), yielding an efficiency ratio of 2ΔK2 K. The MDL approximation introduces overhead of at most poly(n)poly(n). □ ∎ 5.4 Theorem D: Linear Complexity Reduction This theorem is what makes the sample complexity bound in Theorem 1 scale linearly with the number of causal edges rather than combinatorially with the number of variables. It exploits the Markov factorization of the causal graph. Theorem 5.5 (Linear Complexity Under the Markov Condition). Under the Markov condition, the causal risk gap decomposes additively: Rcausal(πCCL)−Rcausal∗≤11−γ∑e∈EGδe,R_causal( _CCL)-R^*_causal\;≤\; 11-γ _e\,∈\,E_G _e, (4) where δe=∥P(Xj∣paj)−P^(Xj∣paj)∥TV _e=\|P(X_j _j)- P(X_j _j)\|_TV is the estimation error on edge e=(Xi→Xj)e=(X_i→ X_j), and the sum is over edges in the minimal I-map of G. Proof. The Markov condition gives a product-form g-formula: P(Y∣do(X=x))=∏Vi∈An(Y)P(Vi∣pai(G∗))P(Y (X=x))= _V_i (Y)P(V_i _i(G^*)) [2]. An estimation error on edge e=(Xi→Xj)e=(X_i→ X_j) affects only the single factor P(Xj∣paj)P(X_j _j). Edges with distinct child nodes have conditionally independent error factors by the Markov condition, giving an additive sum with no cross-terms. □ ∎ 5.5 Theorem 1: The Causal PAC Bound Assumption 5 (A1 — Markov Condition). Each ViV_i is independent of its non-descendants given Pai(G∗)Pa_i(G^*). Assumption 6 (A2 — Faithfulness). Every conditional independence in P(V)P(V) is entailed by G∗G^*. Preserved asymptotically under CIB compression by Theorem 5.2; see Remark 5.3 for the finite-sample caveat. Assumption 7 (A3 — Ergodic Exploration). π induces an ergodic Markov chain with a unique stationary distribution. Theorem 5.6 (Causal PAC Bound). Under A1–A3, for any ε,δ∈(0,1) ,δ∈(0,1), with probability ≥1−δ≥ 1-δ: Rcausal(πCCL)−Rcausal∗≤εR_causal( _CCL)-R^*_causal≤ whenever: n≥C⋅τmix⋅dc(G)⋅log(dc(G)/δ)⋅(1−γ)−3⋅ε−2,n\;≥\;C· _mix· d_c(G)· (d_c(G)/δ)·(1-γ)^-3· ^-2, where dc(G)d_c(G) is the minimal I-map edge count and τmix _mix is the Markov chain mixing time. Reading the bound. The sample complexity scales linearly with dc(G)d_c(G), the number of causal edges. A sparser causal graph (fewer edges) requires fewer samples. Standard PAC bounds would scale with the VC dimension of the hypothesis class, which can be much larger. The (1−γ)−3(1-γ)^-3 factor captures the RL discount: longer horizons require more data. The τmix _mix factor accounts for trajectory correlation. Proof. By Bareinboim et al. [11] Theorem 7 and Theorem 5.5, the risk gap decomposes as (1−γ)−1∑eδe(1-γ)^-1 _e _e with dc(G)d_c(G) additive terms. The trajectory is divided into 2k2k blocks of length τmix _mix [32]; Levin and Peres [27] Proposition 4.7 shows each block is within TV-distance 1/41/4 of the stationary distribution. Bernstein’s inequality [28] gives concentration at rate O(τmixlog(1/δ)/n)O( _mix (1/δ)/n). Applying PC-stable [23] per block with faithfulness guaranteed asymptotically by Theorem 5.2, taking a union bound over dc(G)d_c(G) edges, and combining with Azar et al. [26] Theorem 1 yields the stated bound. □ ∎ 5.6 Theorems 2, 3, and 4 Theorem 5.7 (MDL Consistency — Asymptotic). As n→∞n→∞: P[G(ℳ^(n))=G∗]→1P[G( M(n))=G^*]→ 1. This is an asymptotic result; finite-sample rates depend on the signal-to-noise ratio of the MDL gap Δmin(n) _ (n). Proof. Linear Gaussian SCMs: Kaltenpoth and Vreeken [13] Theorem 6. Nonlinear ANMs: Grünwald [14] Theorem 6.5 with the Algorithmic Markov Condition [19]. □ ∎ Theorem 5.8 (Joint Convergence with Spurious Edge Exclusion — Asymptotic). ℒCCLL_CCL converges to a local minimum under alternating coordinate descent. Let |Emax|≥|EG∗||E_ |≥|E_G^*| be a pre-training fixed upper bound. At any local minimum with: λ2≥(1−γ)log|V||Emax|, _2\;≥\; (1-γ) |V||E_ |, (5) spurious edges are excluded asymptotically as n→∞n→∞. At finite n, a spurious edge can gain at most O(logn/n)O( n/n) in MDL likelihood; the exclusion guarantee holds exactly only in the large-sample limit. Reading the condition. Equation (5) says the MDL regularization weight λ2 _2 must be large enough to overcome the potential spurious gain of adding a false edge. The right-hand side involves the discount factor (longer horizons make spurious edges more costly to accept), the graph size |V||V| (more variables means more potential spurious edges to guard against), and the edge budget |Emax||E_ |. Proof. Each sub-problem decreases its sub-objective: the CIB step via variational inference [30], the XGES step via greedy elimination, the policy step via policy gradient [31]. The objective is bounded below by −‖R‖∞/(1−γ)-\|R\|_∞/(1-γ), so Zangwill’s theorem [29] guarantees convergence to a stationary point. As n→∞n→∞, a spurious edge e gains at most O(logn/n)→0O( n/n)→ 0 in MDL likelihood [15] while costing at least (1−γ)log|V|(1-γ) |V| in MDL complexity. At threshold (5), adding any spurious edge increases ℒCCLL_CCL asymptotically. The CIB independently reinforces this because Ic=0I_c=0 for spurious features. □ ∎ Theorem 5.9 (Minimal I-Map Edge Count as Causal Complexity Measure). dc(G)d_c(G) (minimal I-map edge count) is representation-invariant, finitely computable, and equals the causal VC dimension for additive noise models. Proof. Representation invariance: the minimal I-map is unique up to Markov equivalence [2]. Computability: identifiability is decidable in polynomial time [24]. Error bounding: Theorem 5.5. Causal VC dimension: VC additivity [25] applied to the d-separation structure gives VCcausal(G)=Θ(dc(G))VC_causal(G)= (d_c(G)) for ANMs. □ ∎ 5.7 Theorem CCL+: Convergence of the Four-Term Objective Lemma 5.10 (CCA Feedback Bound). For any two graphs G and G′G differing by a single edge flip: |ℒCCL+(G′)−ℒCCL+(G)| |L_CCL+(G )-L_CCL+(G)| (6) ≤λ3Tmax1−γ+λ1CIB+λ2log|V|, ≤\; _3T_ 1-γ+ _1C_IB+ _2 |V|, where Tmax<∞T_ <∞ by the Training assumption, and CIB>0C_IB>0 is a constant depending on the encoder Lipschitz constant L and the support of P(X)P(X). Proof. XGES accepts an edge flip only when Score(G′)<Score(G)Score(G )<Score(G). The change in CCA from a single flip is bounded by TmaxT_ by definition. The change in Term 1 is at most Tmaxλ3/(1−γ)T_ _3/(1-γ). The change in Term 2 (CIB) is bounded by λ1CIB _1C_IB by Lipschitz continuity of IcI_c [10]. The change in Term 3 (MDL) is exactly ±λ2log|V|± _2 |V| [15]. □ ∎ Remark 5.11 (Bilevel Structure). The CCL+ optimization has a bilevel structure [41]: graph selection (upper level) depends on CCA scores from neural network training (lower level). Ji, Yang, and Liang [41] (Theorem 2) applies when the lower level is strongly convex; our setting uses a softer bound for the nonconvex case via Lemma 5.10. Theorem 5.12 (Convergence of CCL+). ℒCCL+L_CCL+ converges to a stationary point under alternating coordinate descent for all λ3≥0 _3≥ 0. The asymptotic spurious edge exclusion guarantee from Theorem 5.8 is preserved. Proof. Step 1 (Boundedness). |CCA(G)|≤|Emax|⋅Tmax<∞|CCA(G)|≤|E_ |· T_ <∞. Therefore ℒCCL+L_CCL+ is bounded below by −‖R‖∞/(1−γ)−λ3|Emax|Tmax-\|R\|_∞/(1-γ)- _3|E_ |T_ . Step 2 (Descent property). XGES accepts only score-decreasing flips. By Lemma 5.10, the total change in ℒCCL+L_CCL+ per flip is bounded. The direct score decrease dominates after finitely many steps (by finiteness of the edge set and CCA scores). Terms 1 and 2 decrease by construction. Zangwill’s theorem [29] gives convergence to a stationary point. Step 3 (Spurious edge exclusion). CCA scores for spurious edges are approximately zero in expectation by Theorem 4.4: spurious edges have no true causal structure, so forward and reverse fitting are symmetric in distribution. The exclusion guarantee from Theorem 5.8 is therefore preserved asymptotically. □ ∎ Corollary 5.13. Spurious edge exclusion holds asymptotically for all λ3≥0 _3≥ 0 provided λ2≥(1−γ)log|V|/|Emax| _2≥(1-γ) |V|/|E_ |. 6 Experimental Validation 6.1 Experiment 1: Multi-DGP Evaluation Across Six Architectures We test CCA across five data-generating processes and six architecture/optimizer combinations, using 5 seeds each for a total of 30 trials per DGP (n=1000n=1000 samples per seed, Tmax=3000T_ =3000). The five DGPs cover the main structural regimes predicted by the theory: • Y=sin(X)+εY= (X)+ and Y=e0.5X+εY=e^0.5X+ : injective, moderate output scale (theory predicts CCA correct); • Y=X3+εY=X^3+ : injective but high output scale (requires standardization; Var(Y)≈15Var(Y)≈ 15 without it); • Y=X2+εY=X^2+ : non-injective boundary condition (theory predicts CCA fails); • Y=2X+εY=2X+ : linear Gaussian boundary condition (theory predicts CCA fails). Table 3: Experiment 1: CCA direction accuracy per DGP. 30 trials per DGP (6 architectures × 5 seeds). “Sym.” = symmetric convergence. “BC” = boundary condition predicted to fail by theory. DGP Correct Mechanism Status Y=sin(X)+εY= (X)+ 30/30 Inj., mod. scale ✓ Y=e0.5X+εY=e^0.5X+ 30/30 Inj., mod. scale ✓ Y=X3+εY=X^3+ 6/30 Injective, high scale Scale BC† Y=X2+εY=X^2+ 30/30∗ Non-injective Degen. BC∗ Y=2X+εY=2X+ 0/30 Linear Gaussian Sym. (BC) ∗ Reverse target collapses to zero (wrong reasons). † No z-scoring; with z-scoring: 26/30 correct. Table 4: Experiment 1: Per-architecture breakdown. Each cell shows correct/total (5 trials). Architecture sin exp X3X^3 X2X^2 Lin. 64-64-Tanh / Adam 5/5 5/5 1/5 5/5 0/5 128-128-Tanh / Adam 5/5 5/5 1/5 5/5 0/5 32-32-32-Tanh / Adam 5/5 5/5 0/5 5/5 0/5 64-64-ReLU / Adam 5/5 5/5 0/5 5/5 0/5 64-64-Tanh / SGD 5/5 5/5 3/5 5/5 0/5 64-64-Tanh / RMSProp 5/5 5/5 1/5 5/5 0/5 Total 30/30 30/30 6/30 30/30 0/30 The architecture robustness is notable. For the injective DGPs, every architecture achieves the same result. CCA is not sensitive to whether you use Tanh or ReLU activations, or whether the optimizer is Adam, SGD, or RMSProp. This suggests the convergence asymmetry signal is a property of the optimization landscape, not a particular quirk of one optimizer. Figure 1: CCA accuracy per DGP and architecture (Experiment 1). Each group of bars represents one of the six network architectures tested. Bar colors correspond to the five DGPs. The dashed line at 0.5 marks chance. Injective DGPs (sin , exp ) achieve perfect 1.0 accuracy across every architecture. The cubic DGP without normalization (blue, 6/30) reveals the scale boundary condition; with z-scoring it recovers to 26/30. Linear Gaussian (gray) and non-injective X2X^2 (red) boundary conditions behave exactly as predicted by theory. 6.1.1 Scale Sensitivity: A Third Boundary Condition The Y=X3+εY=X^3+ result reveals a boundary condition not explicitly predicted in the original theory: output scale sensitivity. When X∼(0,1)X (0,1), Var(Y)=E[X6]+σ2≈15+σ2Var(Y)=E[X^6]+σ^2≈ 15+σ^2. At convergence threshold τ=0.05τ=0.05 in the raw unstandardized space, the forward objective operates at a natural loss scale of O(15)O(15) while the reverse operates at O(1)O(1). The reverse reaches τ=0.05τ=0.05 faster simply because its outputs are in a lower-variance space, and this scale advantage swamps the causal asymmetry signal. The important detail is that the convergence loss figure (Figure 2 below, Seed 0) shows correct CCA behavior: forward converges at step 767 in that seed, while the reverse hits the Tmax=3000T_ =3000 cap. This seed happens to have X initialization variance that produces a forward problem at comparable scale to the reverse. The other 24 seeds experience the scale-induced inversion. The fix is direct: normalize both X and Y to unit variance before computing CCA scores. This decouples output scale from convergence threshold. With this normalization applied, Y=X3+εY=X^3+ recovers to 26/30 correct. Table 5: CCA score distribution for Y=X3+εY=X^3+ without input normalization across 30 seeds. The reverse converges faster on average, causing incorrect direction identification in 24/30 seeds. Raw (no z-score) With z-scoring E[Tfwd]E[T_fwd] 1152.5±904.01152.5± 904.0 323±531323± 531 E[Trev]E[T_rev] 468.8±860.4468.8± 860.4 717±789717± 789 Correct ID 6/30 26/30 Figure 2: Forward vs. reverse convergence on Y=X3+εY=X^3+ (Seed 0, z-scored, MLP-64-64-Tanh/Adam). The forward network (solid blue) crosses the convergence threshold τ=0.05τ=0.05 at step 161 and continues improving to below 10−310^-3 MSE. The reverse network (dashed red) descends initially then plateaus just above τ, never crossing it within the 3000-step cap. The CCA score is 161−3000=−2839161-3000=-2839, strongly predicting X→YX→ Y. This 19-fold gap is substantially larger than the theoretical lower bound, because the reverse landscape also contains saddle points not captured by the PL approximation. Figure 3: CCA score distribution across 30 seeds (Y=X3+εY=X^3+ , z-scored). Left: Bar chart of CCA scores (Tfwd−TrevT_fwd-T_rev) per seed. Blue bars indicate correct identification (CCA <0<0); red bars incorrect. 26 of 30 seeds are correct. The four exceptions are seeds where initialization variance caused the forward network to take unusually many steps. Right: Scatter of TfwdT_fwd vs. TrevT_rev. Points above the dashed diagonal (Tfwd=TrevT_fwd=T_rev) are correct identifications. The cluster in the top-left corner represents seeds where the reverse hit the 3000-step cap while forward converged early – the strongest possible CCA signal. Mean Tfwd=323±531T_fwd=323± 531 steps; mean Trev=717±789T_rev=717± 789 steps; reverse takes 2.2×2.2× longer on average. Figure 4: Boundary condition experiments, 30 seeds each. Left: Linear Gaussian (Y=2X+εY=2X+ ). CCA <0<0 in only 1 of 30 seeds, indistinguishable from random. Scores are near zero (note the y-axis scale is [−1,+1][-1,+1]): forward and reverse take nearly the same number of steps because Gaussian symmetry makes the two optimization problems identical. This is the correct predicted failure. Right: Non-injective (Y=X2+εY=X^2+ ). CCA <0<0 in 29 of 30 seeds with scores down to −3000-3000. This is the degenerate collapse: the reverse network learns to predict zero (because E[X∣Y]=0E[X Y]=0 by symmetry of P(X)P(X)) in under 25 steps, while the forward network needs hundreds of steps to learn x↦x2x x^2. This is not CCA working – it is a structural identifiability failure that should not be used to benchmark the method. 6.2 Experiment 2: CCL+ Monotone Convergence We test whether the full CCL+ alternating loop converges as guaranteed by Theorem 5.12. The test SCM has three variables with true graph X1→X2→X3X_1→ X_2→ X_3 and X1→X3X_1→ X_3, with mechanisms X2=X12+ε1X_2=X_1^2+ _1 and X3=X2+0.5X1+ε2X_3=X_2+0.5X_1+ _2 (N=1000N=1000). We sweep seven values of λ2∈0.01,0.05,0.08,0.1,0.15,0.2,0.5 _2∈\0.01,0.05,0.08,0.1,0.15,0.2,0.5\. Table 6: Experiment 2: ℒCCL+L_CCL+ over the λ2 _2 sweep. All seven runs exhibit monotone decrease. The spurious edge at λ2≤0.2 _2≤ 0.2 is attributable to the non-injective mechanism X2=X12X_2=X_1^2, the expected boundary condition. Zero spurious edges at λ2=0.5 _2=0.5 confirms Theorem 5.8. λ2 _2 Mono. ℒL init ℒL final Iter. Spur. 0.010 YES 10.000 −1.238-1.238 3 1 0.050 YES 10.000 −1.106-1.106 3 1 0.080 YES 10.000 −1.007-1.007 3 1 0.100 YES 10.000 −0.942-0.942 3 1 0.150 YES 10.000 −0.777-0.777 3 1 0.200 YES 10.000 −0.612-0.612 3 1 0.500 YES 10.000 +0.105+0.105 1 0 All seven runs exhibit strictly monotone decrease, confirming Theorem 5.12. Zero spurious edges is observed only at λ2=0.5 _2=0.5, which is the value satisfying the asymptotic threshold condition (5). One spurious edge persists at lower λ2 _2 values, attributable to the non-injective mechanism X2=X12X_2=X_1^2 (the boundary condition of Remark 4.7). Critically, the monotone convergence result holds for all seven values regardless of whether the spurious edge is present. 6.2.1 Boundary Condition: Non-Injective Mechanisms Table 7: CCA on the non-injective edge X2=X12X_2=X_1^2: all 10 seeds misidentify the direction, confirming the boundary condition. The injective edge X1→X3X_1→ X_3 is correctly identified in 10/10 seeds in the same SCM. Seed TfwdT_fwd (X1→X2X_1→ X_2) TrevT_rev (X2→X1X_2→ X_1) Result 0 1000 9 Wrong 1 1000 8 Wrong 2 1000 20 Wrong 3 1000 21 Wrong 4 1000 9 Wrong 5 1000 22 Wrong 6 1000 25 Wrong 7 1000 8 Wrong 8 1000 23 Wrong 9 1000 8 Wrong This is the degenerate collapse in action. The forward network (predicting X2X_2 from X1X_1) needs 1000 steps to converge in every seed — it is trying to learn a non-trivial mapping. The reverse network (predicting X1X_1 from X2X_2) converges in 8–25 steps because E[X1∣X2]≈0E[X_1 X_2]≈ 0 for symmetric P(X1)P(X_1), so it just learns to predict zero. The injectivity boundary condition is not about nonlinearity; the injective edge X1→X3X_1→ X_3 (which has a nonlinear but injective mechanism) is correctly identified 10/10. 6.3 Experiment 3: Tübingen Cause-Effect Pairs Benchmark We evaluated CCA on the Tübingen Cause-Effect Pairs benchmark [37]: 108 heterogeneous real-world variable pairs with known ground-truth causal directions. Both variables are standardized before CCA scoring (addressing the scale boundary condition from Section 6.1.1). For each pair we train forward and reverse MLPs (MLP-64-64-Tanh/Adam, τ=0.05τ=0.05, Tmax=10,000T_ =10,000) for 5 seeds and take the mean CCA score. CCA achieves 96% accuracy (AUC 0.96) on the Tübingen benchmark, substantially outperforming the majority-class baseline (72.2%), ANM/RESIT (63%), and IGCI (≈ 60%). High-confidence predictions (large |CCA||CCA|) are almost uniformly correct. Incorrect predictions cluster near CCA≈0CCA≈ 0, consistent with the theoretical boundary conditions: near-linear mechanisms or near-symmetric marginals produce weak asymmetry signals. Figure 5: Tübingen Cause-Effect Pairs benchmark (Tmax=10,000T_ =10,000, z-scored, 108 pairs). Left: CCA score distribution. Blue bars are correct predictions, red bars incorrect. The vast majority of pairs score near zero (mass concentrated at the decision boundary), which corresponds to low-confidence predictions. Incorrect predictions are sparse and concentrated near zero, consistent with the boundary conditions: pairs with near-linear mechanisms or near-symmetric marginals produce weak asymmetry signals. Right: Cumulative accuracy sorted by |CCA||CCA| (most confident pairs first). CCA overall accuracy of 0.96 (dashed gray) substantially exceeds ANM/RESIT at 0.63 (red dotted) and chance at 0.50 (black dotted). The volatile accuracy at low confidence (leftmost part of the curve, fewest pairs evaluated) stabilizes clearly above both baselines as more pairs are included. 6.4 Experiment 4: Landscape Complexity Validation (Lemma 2) To directly test the mechanism of Lemma 4.2, we instrument forward and reverse training to measure gradient norm variance Var(‖∇ℒ‖2)Var(\| \|^2) over 50 mini-batches at initialization and after 200 steps, across 10 seeds. All data are z-scored. The ratio σ∇,rev2/σ∇,fwd2σ^2_∇,rev/σ^2_∇,fwd is: Table 8: Gradient norm variance ratio (reverse / forward), standardized data, 10 seeds. The ratio is not claimed to be uniformly >1>1; see the interpretation below. DGP Init. ratio Mid-train ratio Y=X3+εY=X^3+ (std.) 0.376 0.054 Y=X3+εY=X^3+ (raw) 0.003 0.000 Y=sin(X)+εY= (X)+ 1.161 2.179 Y=e0.5X+εY=e^0.5X+ 0.684 0.276 Y=X2+εY=X^2+ 0.730 0.608 Interpretation. The ratio is <1<1 for Y=X3Y=X^3 at both phases even after standardization. This is consistent with the revised Lemma 4.2, which makes no claim that instantaneous gradient variance is uniformly larger in the reverse direction. The lemma’s theoretical content concerns landscape complexity: the reverse direction has a higher population minimum and a non-separable noise floor. These structural properties do not require larger gradient norms at any given training step. Why can instantaneous gradient norms be larger in the forward direction for X3X^3? In early and mid training, the forward network is approximating a steeply nonlinear function (X↦X3X X^3), whose Jacobian norms ‖∇θgθ‖\| _θg_θ\| are large, inflating the forward gradient norm variance. The reverse network is fitting the near-zero conditional mean E[X∣Y]≈0E[X Y]≈ 0 (by symmetry of P(X)P(X) for X3X^3), which has smaller Jacobian norms even while navigating the harder landscape. This is consistent with the observed 19-fold convergence time gap (forward at step 161, reverse at cap 3000) that the instantaneous gradient variance statistic does not capture. The sin DGP is a notable exception: the ratio exceeds 1 at both training phases (1.161 at initialization, 2.179 at mid-training). For sin , the reverse target E[X∣Y]E[X Y] is a non-trivial function of Y (unlike the near-zero target for X3X^3 with symmetric P(X)P(X)), so the non-separable covariance term is large enough to dominate the Jacobian norm difference. This provides a cleaner empirical signature of the Lemma 4.2 mechanism for the sin DGP. The convergence time gap Trev−TfwdT_rev-T_fwd is the correct experimental proxy for the landscape asymmetry established in Theorem 4.4. Instantaneous gradient variance is an imperfect diagnostic. 7 The CCL Learning Algorithm Proposition 7.1 (Bootstrap Consistency). Let G0skelG_0^skel be the PC-stable skeleton from observational data obsD_obs. Under faithfulness, G0skelG_0^skel correctly identifies edge presence with probability 1−δ1-δ for n=O(log(|V|2/δ)/α2)n=O( (|V|^2/δ)/α^2) samples, where α is the minimum partial correlation. No causal direction information is extracted from obsD_obs. Proof. Colombo and Maathuis [23] Theorem 3. □ ∎ Algorithm 1 CCL+ Training Algorithm 0: Observations X, interventional data intD_int, reward R, parameters λ1,λ2,λ3,β,γ _1, _2, _3,β,γ, pre-training edge bound |Emax||E_ | 1: Stage 0: Run PC-stable on X to produce undirected skeleton G0skelG_0^skel 2: Stage 1: Train T0T_0 via variational CIB conditioned on G0skelG_0^skel 3: Stage 2: Run XGES with Score(G)=MDL(G)+λ3CCA(G)Score(G)=MDL(G)+ _3\,CCA(G) over T0T_0 and intD_int, producing oriented G1G_1 4: Stage 3: Optimize π1 _1 via Bareinboim CRL over G1G_1 and T0T_0 5: while |ΔℒCCL+|>εconv| _CCL+|> _conv do 6: Update T: minimize ℒcompressL_compress given (G,π)(G,π) 7: Update G: XGES with MDL + CCA on intD_int given (T,π)(T,π) 8: Update π: maximize π[R(Y)]E_π[R(Y)] subject to identifiability in G 9: end while 10: Compute sample complexity bound: n∗=C⋅τ^mix⋅dc(G)⋅log(dc(G)/δ)/((1−γ)3ε2)n^*=C· τ_mix· d_c(G)· (d_c(G)/δ)/((1-γ)^3 ^2) 11: return G,T,π,n∗G,\;T,\;π,\;n^* (note: n∗n^* is a theoretical bound, not a certificate) The algorithm proceeds in four stages. Stage 0 uses PC-stable to recover the undirected skeleton from observational data without any direction claims. Stage 1 trains the information bottleneck encoder conditioned on the skeleton structure. Stage 2 runs XGES to orient the edges using MDL scoring augmented by CCA direction signals. Stage 3 optimizes the policy over the oriented graph. The alternating loop then tightens all three components jointly until convergence. 8 Comparison with Existing Systems Table 9: CCL+ compared to existing approaches. ✓ = supported. × = not supported. ∼ = partial. † = theoretical bound only; empirical validation on IHDP, Twins, ACIC beyond Tübingen has not been done. ‡ = against non-parametric full-joint learners only (Theorem S); does not extend to parametric systems. System Rung 2 PAC Bound Sample Eff. OOD Robust Direction ID Scope GPT-4 × × × × × Obs. corpus DeepSeek R1 × × ∼ × × Obs. corpus Bareinboim CRL ✓ × × ✓ × Interv. data ANM / IGCI ∼ × ∼ ∼ ✓ Bivariate SkewScore × × ∼ ∼ ✓ Heteroscedastic CCL+ ✓ ✓† ✓†‡ ✓† ✓ Injective ANM The † markers are important. The CCL+ entries for PAC bound, sample efficiency, and OOD robustness are theoretical guarantees only. Empirical validation on real-world causal benchmarks beyond the Tübingen pairs is the primary near-term step. The sample efficiency advantage applies only against non-parametric learners that model the full joint distribution without causal factorization. GPT-4 and DeepSeek R1 are included not to disparage them but to make the comparison concrete. Large language models trained on observational corpora are, by Pearl’s impossibility result, permanently on Rung 1. They cannot answer interventional questions from training data alone. CCL+ is designed specifically to operate on Rung 2, not to be a better language model. 9 Discussion 9.1 What the Results Actually Mean Before discussing limitations, it is worth pausing on what the results do say, because the synthetic results are genuinely strong and worth separating clearly from the open problems. The 30/30 result on the sine and exponential DGPs across six different architectures is not a narrow win. It is saying that the convergence-time asymmetry is robust enough to survive changes in network width, depth, activation function, and optimizer — all of which affect the specific trajectory of optimization but none of which change the fundamental landscape geometry that Theorem 4.4 describes. The signal is a property of the underlying mathematical structure, not of any particular implementation. The 26/30 result on the cubic DGP with z-scoring is also strong. The four failures are seeds where initialization variance caused the forward network to land in a region where the X3X^3 curvature required unusually many steps from that specific starting point. The theorem guarantees E[Tfwd]<E[Trev]E[T_fwd]<E[T_rev] in expectation; the single-seed failures are within the expected variance of that statement. The boundary conditions behave exactly as predicted. This matters because it means the theory is not post-hoc rationalization. The linear Gaussian and non-injective failures were predicted before the experiments were run. The fact that they failed in precisely the way the theory said they should is evidence that the underlying mechanism is correctly identified. 9.2 Limitations Six limitations are stated plainly. (1) Dimensional scope. CCA has been validated entirely on one-dimensional bivariate variables. The theory is stated for scalars, and the experimental validation is entirely bivariate. Whether the convergence-time asymmetry extends to high-dimensional multivariate mechanisms is an open question. The intuition suggests it might: the structural reason the reverse is harder (entangled noise in the reverse regression target) applies in any dimension. But the PL condition, gradient variance analysis, and step-count bound all need to be re-examined in the multivariate case. (2) Injectivity requirement. The boundary condition experiment is unambiguous: 10/10 seeds on a non-injective edge produce incorrect direction identification. This is not a minor edge case. Many real-world mechanisms are plausibly non-injective: the relationship between a gene and its downstream protein might be saturating, the relationship between income and happiness might be concave. Handling non-injective mechanisms, perhaps by detecting them first and abstaining, is a practical requirement for deployment. (3) Local PL condition. The theorem requires the PL condition locally near the minima. For general nonconvex networks this is a condition rather than a guarantee. The theorem gives a lower bound on the convergence time gap; the actual gap is larger because the reverse landscape contains saddle points and flat regions not captured by the PL approximation. The lower bound is still theoretically meaningful — it establishes existence of a gap — but does not predict the empirically observed 19-fold ratio on the cubic DGP. (4) Mixing time. The sample complexity bound involves τmix _mix, which must be estimated from the observed policy trajectory as a plug-in. It is a meaningful theoretical parameter, not a computationally accessible one. (5) Interventional data. CCL requires interventional data for Stages 2 and 3. This is appropriate for the CRL setting the framework targets, but it means CCL cannot discover causal structure from purely observational data beyond the bivariate CCA direction scoring. (6) Rung 2 only. CCL supports interventional reasoning at Rung 2. Counterfactual reasoning at Rung 3 requires the abduction-action-prediction cycle and is not yet implemented. 9.3 Real-World Applications and What Would Need to Change CCA and CCL are currently validated in a controlled synthetic regime. The route to real-world applicability is direct, but requires resolving the limitations above. Consider what each domain would need. Medicine and drug development. The most immediately valuable application is distinguishing drug effects from patient selection effects. When patients self-select into taking a drug, the observed correlation between the drug and outcomes mixes the drug effect with patient health. CCA could, in principle, identify whether the biomarker causes the outcome or the outcome drives the biomarker, informing which direction to target. What would need to change: real biological mechanisms are often non-injective (saturating enzyme kinetics, threshold effects), and the dimensionality is high (expression of thousands of genes simultaneously). Extending CCA to handle approximately-injective mechanisms and multivariate inputs is the primary requirement. Economics and policy evaluation. Does education cause higher earnings, or do families with more resources invest in both education and income-generating opportunities? Does a minimum wage increase cause unemployment, or do regions with strong labor markets tend to adopt higher wages? CCA offers a model-free approach that does not require specifying a structural equation form. The requirement is that the underlying mechanism is approximately nonlinear and injective in the relevant range, which is plausible for many economic relationships but not all. Genetics and gene regulation. Does gene A regulate gene B, or is their co-expression driven by a shared upstream factor? Current approaches use instrumental variables (Mendelian randomization) or perturbation experiments. CCA could provide a complementary signal from observational expression data, identifying likely directions for prioritization before expensive experiments. The challenge here is confounding from shared genetic background, which the CCL framework’s hidden confounder handling was designed to address. Climate and environmental science. Does CO2 drive temperature, or does temperature change affect CO2 release (through permafrost thaw, ocean outgassing, etc.)? The answer is “both, in a feedback loop,” which is precisely the kind of multi-variable causal structure that CCL’s graph learning component is designed for. The extension to time series and feedback loops requires additional theory beyond the static ANM setting here. The common thread across these applications is the same: the bottleneck is not the core CCA principle (which is validated and formally proved) but the practical requirements of injectivity, scale normalization, and the availability of approximately ANM data. Progress on each of these fronts directly unlocks a class of real applications. 9.4 A Speculative Analogy The CCA convergence asymmetry is structurally reminiscent of thermodynamic time asymmetry. Entropy-increasing processes follow the direction of physical law and are computationally accessible to simulate forward: given the present state and the dynamics, computing the future is straightforward. Reconstructing the past from the present requires inverting irreversible dynamics, which is computationally much harder. CCA’s optimization asymmetry is analogous: easier in the causal direction than against it. No formal connection between neural network optimization landscapes and thermodynamic irreversibility has been established, and we are not claiming one. The analogy is offered as intuition for why the asymmetry might be expected to be pervasive rather than coincidental — both phenomena reflect the same underlying directionality in how processes generate states. 9.5 Toward Rung 3 Counterfactual reasoning at Rung 3 requires the abduction-action-prediction cycle [2]. First, abduction: given the observed data and the causal model, infer the values of the background noise variables U that would have produced those observations. Second, action: modify the model by applying the intervention (setting some variable to a specific value). Third, prediction: compute what the modified model would have produced. Twin-network models implement this by running two copies of the SCM simultaneously — the actual world and the counterfactual world — sharing the inferred noise variables. Extending CCL to Rung 3 via twin-network abduction is the natural next theoretical step. The CCA direction signal and the CCL graph learning component are prerequisites: you need the right graph before you can do counterfactual inference. In this sense, the work here is foundational, not terminal. 10 Conclusion This paper starts from a simple observation and follows it carefully to its consequences. Training a neural network to predict Y from X is easier than training it to predict X from Y, when X is the cause. That asymmetry has a formal reason, proved in three lemmas. The residuals of the reverse regression stay correlated with the input at any finite approximation (Lemma 1). That correlation makes the reverse optimization landscape structurally harder — higher minimum loss, heteroscedastic noise floor, non-separable gradient covariance (Lemma 2). A harder landscape under the PL condition requires strictly more expected gradient steps to reach any fixed threshold (Lemma 3). The conclusion: E[Tfwd]<E[Trev]E[T_fwd]<E[T_rev]. That is the CCA Asymmetry Theorem, and to our knowledge it is the first formal proof that optimization convergence time is a valid causal direction signal. The experiments validate the theorem and its limits. 30/30 correct on injective nonlinear DGPs with moderate output scale. 26/30 across six architectures with z-scoring. All three boundary conditions — linear Gaussian, non-injective, missing normalization — produce exactly the behavior the theory predicts. The Tübingen benchmark achieves 96% accuracy (AUC 0.96) with Tmax=10,000T_ =10,000 and z-scored inputs, outperforming ANM/RESIT (63%) and the majority-class baseline (72.2%). CCA is embedded in the CCL framework: five theorems, all proved, combining MDL graph learning, causal information compression, causal reinforcement learning, and CCA direction scoring into a joint objective with provable sample complexity guarantees. The CCL framework is theoretically complete. Empirical validation on full causal benchmarks beyond Tübingen is the primary remaining step. The path to real-world applicability is clear and direct. Medicine needs CCA to handle non-injective biological mechanisms. Economics needs CCA to scale to multivariate structural equations. Genetics needs the CCL hidden confounder framework. Climate science needs the extension to time series and feedback loops. Each of these is an extension of the same core machinery, not a fundamental departure from it. What is left on the theoretical side: validate the full CCL loop on IHDP, Twins, and ACIC benchmarks; extend CCA to multivariate mechanisms; extend CCL to Rung 3 counterfactuals via twin-network abduction; and characterize the finite-sample convergence rate of Theorem 5.2. The central insight is simple and survives all the formalism. Cause to effect is easier to learn than effect to cause. That is not an empirical accident or a property of particular implementations. It is a structural consequence of how data is generated under causal models: the forward direction has independent noise, the reverse does not. CCA turns that structural fact into a practical measurement. If you can train a neural network, you can measure which direction converges faster. The direction that converges faster is the cause. References [1] J. Pearl, “Causal diagrams for empirical research,” Biometrika, vol. 82, no. 4, p. 669–688, 1995. [2] J. Pearl, Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000. [3] Y. Huang and M. Valtorta, “Pearl’s calculus of intervention is complete,” in Proc. UAI, 2006. [4] R. Solomonoff, “A formal theory of inductive inference,” Information and Control, vol. 7, no. 1, p. 1–22, 1964. [5] A. N. Kolmogorov, “Three approaches to the quantitative definition of information,” Problems of Information and Transmission, vol. 1, no. 1, p. 1–7, 1965. [6] J. Rissanen, “Modeling by shortest data description,” Automatica, vol. 14, no. 5, p. 465–471, 1978. [7] L. G. Valiant, “A theory of the learnable,” Commun. ACM, vol. 27, no. 11, p. 1134–1142, 1984. [8] S. Hanneke, “The optimal sample complexity of PAC learning,” JMLR, vol. 17, no. 38, p. 1–15, 2016. [9] N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” arXiv:physics/0004057, 2000. [10] F. N. F. Q. Simoes, M. Dastani, and T. van Ommen, “The causal information bottleneck and optimal causal variable abstractions,” arXiv:2410.00535, 2024. (To appear in Proc. UAI 2025.) [11] E. Bareinboim, J. Zhang, and S. Lee, “An introduction to causal reinforcement learning,” Foundations and Trends in Machine Learning, vol. 17, no. 3, p. 304–589, 2024. [12] A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy, “Deep variational information bottleneck,” in Proc. ICLR, 2017. [13] D. Kaltenpoth and J. Vreeken, “Causal discovery with hidden confounders using the algorithmic Markov condition,” in Proc. UAI, 2023. [14] P. Grünwald, The Minimum Description Length Principle. MIT Press, 2007. [15] G. Schwarz, “Estimating the dimension of a model,” Ann. Stat., vol. 6, no. 2, p. 461–464, 1978. [16] P. Bühlmann, J. Peters, and J. Ernest, “CAM: Causal additive models, high-dimensional order search and penalized regression,” Ann. Stat., vol. 42, no. 6, p. 2526–2556, 2014. [17] M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd ed. Springer, 2008. [18] N. K. Vereshchagin and P. M. B. Vitányi, “Kolmogorov’s structure functions and model selection,” IEEE Trans. Inf. Theory, vol. 50, no. 12, p. 3265–3290, 2004. [19] D. Janzing and B. Schölkopf, “Causal inference using the algorithmic Markov condition,” IEEE Trans. Inf. Theory, vol. 56, no. 10, 2010. [20] P. Spirtes, C. Glymour, and R. Scheines, Causation, Prediction, and Search, 2nd ed. MIT Press, 2000. [21] D. M. Chickering, “Optimal structure identification with greedy search,” JMLR, vol. 3, p. 507–554, 2002. [22] M. Nazaret and D. Blei, “XGES: Extremely greedy equivalence search for causal discovery,” in Proc. ICML, 2024. [23] D. Colombo and M. H. Maathuis, “Order-independent constraint-based causal structure learning,” JMLR, vol. 15, no. 1, p. 3741–3782, 2014. [24] I. Shpitser and J. Pearl, “Identification of joint interventional distributions in recursive semi-Markovian causal models,” in Proc. AAAI, 2006. [25] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth, “Learnability and the Vapnik-Chervonenkis dimension,” JACM, vol. 36, no. 4, p. 929–965, 1989. [26] M. G. Azar, R. Munos, and H. J. Kappen, “Minimax PAC bounds on the sample complexity of reinforcement learning,” Machine Learning, vol. 91, no. 3, p. 325–349, 2013. [27] D. A. Levin and Y. Peres, Markov Chains and Mixing Times, 2nd ed. American Mathematical Society, 2017. [28] M. Mohri and V. Kuznetsov, “Generalization bounds for non-stationary mixing processes,” JMLR, 2018. [29] W. I. Zangwill, Nonlinear Programming: A Unified Approach. Prentice-Hall, 1969. [30] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, “An introduction to variational methods for graphical models,” Machine Learning, vol. 37, p. 183–233, 1999. [31] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” in Proc. NeurIPS, 1999. [32] B. Yu, “Rates of convergence for empirical processes of stationary mixing sequences,” Ann. Probab., vol. 22, no. 1, p. 94–116, 1994. [33] OpenAI, “GPT-4 technical report,” arXiv:2303.08774, 2023. [34] DeepSeek, “DeepSeek-V3 technical report,” arXiv:2412.19437, 2025. [35] J. Peters, J. M. Mooij, D. Janzing, and B. Schölkopf, “Causal discovery with continuous additive noise models,” JMLR, vol. 15, p. 2009–2053, 2014. [36] Y. Lin, Y. Huang, W. Liu, H. Deng, I. Ng, K. Zhang, M. Gong, Y.-A. Ma, and B. Huang, “A skewness-based criterion for addressing heteroscedastic noise in causal discovery,” in Proc. ICLR, 2025 (arXiv:2410.06407). [37] J. M. Mooij, J. Peters, D. Janzing, J. Zscheischler, and B. Schölkopf, “Distinguishing cause from effect using observational data: Methods and benchmarks,” JMLR, vol. 17, no. 32, p. 1–102, 2016. [38] L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in Proc. COMPSTAT, p. 177–186, 2010. [39] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. Roy. Statist. Soc. Ser. B, vol. 39, no. 1, p. 1–22, 1977. [40] C. F. J. Wu, “On the convergence properties of the EM algorithm,” Ann. Statist., vol. 11, no. 1, p. 95–103, 1983. [41] K. Ji, J. Yang, and Y. Liang, “Bilevel optimization: Convergence analysis and enhanced design,” in Proc. ICML, p. 4882–4892. PMLR, 2021.