Causal Discovery via Data Compression Asymmetry

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 268 papers119 conceptsfrozen 2026-10-04

In classical statistics, correlation does not imply causation. If we observe that two variables $X$ and $Y$ are correlated, the data itself seems symmetric; we cannot tell if $X \to Y$, $Y \to X$, or if a hidden confounder $Z$ drives both. However, a growing body of research suggests that while the statistical relationship may be symmetric, the algorithmic relationship is not.

The core intuition is that nature is "lazy": the mechanism that generates an effect from a cause is typically simpler to describe than the mathematical "unscrambling" required to map the effect back to its cause. By treating causal discovery as a data compression problem, researchers can identify the true direction of influence by finding which orientation allows for the most succinct description of the data.

The Algorithmic Markov Condition

The theoretical foundation of this direction is Algorithmic Information Theory (AIT). As Bernhard Schölkopf explains in Causality for Machine Learning, the Principle of Independent Causal Mechanisms (ICM) posits that the source (the cause) and the process (the mechanism) are independent entities in the real world.

In terms of Kolmogorov complexity—the length of the shortest computer program that can produce a dataset—this independence creates a measurable asymmetry. If $X$ causes $Y$, the shortest description of the joint distribution $P(X, Y)$ is simply the sum of the shortest description of $X$ plus the shortest description of the mechanism $P(Y|X)$. In the anti-causal direction ($Y \to X$), the description of the "cause" $Y$ and the "mechanism" $P(X|Y)$ must "conspire" or become algorithmically dependent to fit the observed data, resulting in a longer total description.

From Theory to Practice: Minimum Description Length

Since Kolmogorov complexity is uncomputable, researchers use the Minimum Description Length (MDL) principle as a practical proxy. MDL suggests that the best model for a dataset is the one that leads to the best compression.

Jilles Vreeken and Kailash Budhathoki pioneered this approach with frameworks like Origo and cisc. Their work demonstrates that by comparing the "stochastic complexity" of two variables in both directions, one can identify the causal arrow with high accuracy. For instance, the SLOPE algorithm by Alexander Marx and Jilles Vreeken uses local regression and MDL to break the "70% accuracy barrier" on real-world benchmarks, proving that the simplest compression is a robust signal for truth.

Why the Anti-Causal Direction is Complex

Why exactly is the wrong direction harder to compress? Consider a simple linear relationship with noise: $Y = f(X) + \epsilon$.

  1. Functional Simplicity: In the true direction, the mapping $f$ is often a smooth, low-rank function. In the reverse direction, the mapping becomes a "contrived" non-linear mess to account for the noise distribution of the original cause. Xiaohai Sun and Dominik Janzing showed in Causal Inference by Choosing Graphs with Most Plausible Markov Kernels that the true causal mechanism typically exhibits a "smoother" structure.
  2. Noise Propagation: Patrick Blöbaum and colleagues found that comparing regression errors serves as a proxy for complexity. Simple models (like low-degree polynomials) can easily fit the causal direction but fail to overfit the complex noise patterns in the anti-causal direction, making the true direction "easier" to fit.
  3. Distributional Footprints: Methods like bQCD by Natasa Tagasovska look at the compressibility of different "slices" (quantiles) of the data. They find that causal footprints are often hidden in the shape of the conditional distribution, which becomes more complex when viewed in reverse.

Scaling to Networks and Environments

While early work focused on bivariate pairs ($X, Y$), recent advances scale these principles to complex systems:

  • Fully Oriented Graphs: The GLOBE algorithm extends MDL to orient entire causal networks, resolving edges that traditional statistical tests (which only find Markov Equivalence Classes) leave undirected.
  • Multiple Environments: ORION and LINC leverage the idea that across different settings (e.g., different labs or time periods), the causal mechanism $P(Effect|Cause)$ remains stable and simple, while the anti-causal mapping must change in complex, non-independent ways to explain the shifts.
  • Event Sequences: CASCADE by Joscha Cüppers et al. applies these principles to discrete event logs, using MDL to distinguish between delayed and instantaneous triggers.

The Future: The Artificial Scientist

The ultimate goal of this research direction is to move beyond pattern recognition toward autonomous discovery. As argued by Héctor Zenil and Jesper Tegnér in The Future of Fundamental Science Led by Generative Closed-Loop Artificial Intelligence, integrating algorithmic information dynamics allows AI to identify the simplest generative laws of a system. By seeking the shortest algorithmic description, these "Artificial Scientists" can distinguish between mere correlation and the underlying structural mechanisms of the physical world.

Papers in this version

Showing 60 of 68 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 82 papers
  2. Version 1 · 2026-10-04 · 68 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_minimum_description_length_causal_infere_871fbe77,
  title = {minimum description length causal inference},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimum-description-length-causal-inference/rdr_871fbe77b49040f8acbbc8e63302d79b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_causal_discovery_via_data_compression_as_871fbe77_v1,
  title = {Causal Discovery via Data Compression Asymmetry},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-discovery-via-data-compression-asymmetry/rdr_871fbe77b49040f8acbbc8e63302d79b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}