Imagine watching a video of an ink drop falling into a glass of water and dispersing. If you run the video forward, the process is simple to describe: a concentrated drop enters, and standard physical laws of diffusion explain how it spreads. If you run the video backward, however, the description becomes incredibly complex. You would have to explain how billions of separate water and ink molecules spontaneously coordinate their movements to assemble into a perfect, isolated droplet.
This asymmetry is the core intuition behind using information theory and data compression for causal inference. In nature, generating an effect from a cause follows a forward physical mechanism that operates independently of the cause itself. Trying to reverse-engineer the cause from the effect forces us to "unscramble" this independent noise, resulting in a description that is highly complex and contrived.
By treating causal discovery as a data compression problem, we can determine the direction of causality simply by finding which configuration yields the shortest, most elegant description of the data.
The Principle of Independent Causal Mechanisms
To understand why compression reveals causality, we must look at how joint distributions are factored. If we have two variables, $X$ and $Y$, we can mathematically factor their joint distribution $P(X, Y)$ in two ways:
- $P(X)P(Y \mid X)$
- $P(Y)P(X \mid Y)$
Statistically, these factorizations are completely symmetric; standard correlation cannot tell them apart. However, the Principle of Independent Causal Mechanisms (ICM) states that if $X$ causes $Y$ ($X \to Y$), then the source distribution $P(X)$ and the conditional mechanism $P(Y \mid X)$ are algorithmically independent. They do not contain information about each other.
As a consequence, if we choose the true causal factorization $P(X)P(Y \mid X)$, the total algorithmic complexity—the length of the shortest program required to describe the system—is simply the sum of the complexities of its parts.
But what happens if we force the anti-causal factorization $P(Y)P(X \mid Y)$? Because $Y$ was physically generated by $X$ and some random noise, the marginal distribution $P(Y)$ inherently contains traces of both $X$ and the mechanism. To map backward from $Y$ to $X$, the conditional distribution $P(X \mid Y)$ must tightly depend on $P(Y)$ to cancel out that noise. This lack of independence means that describing $P(Y)$ and $P(X \mid Y)$ requires a more complex, highly coordinated mathematical explanation.
As Xiaohai Sun et al. observed, nature prefers smooth, natural mechanisms. When a cause is modeled as an effect, the resulting conditional distribution appears highly contrived and mathematically complex.
From Kolmogorov Complexity to Practical MDL
In an ideal world, we would measure this complexity using Kolmogorov complexity—the absolute shortest computer program that can output our data. However, because Kolmogorov complexity is mathematically uncomputable, we need a practical proxy. This is where the Minimum Description Length (MDL) and Minimum Message Length (MML) principles come in.
Instead of searching over all possible computer programs, MDL restricts the search to a specific family of statistical models. It evaluates a causal hypothesis using a two-part coding scheme:
$$\text{Total Length} = \text{Length}(\text{Model}) + \text{Length}(\text{Data} \mid \text{Model})$$
The first part is the number of bits needed to encode the model's parameters (its complexity), and the second part is the number of bits needed to encode the data using that model (its negative log-likelihood).
Bastian Steudel et al. demonstrated that practical compression algorithms (like Lempel-Ziv or grammar-based compression) can successfully serve as proxies for algorithmic information content, allowing researchers to perform causal discovery directly on data strings.
In practice, algorithms like SLOPE, developed by Alexander Marx et al., use regression models to compute these description lengths for continuous data. If encoding $X$ plus the regression residuals of $Y$ given $X$ takes fewer bits than the reverse, $X \to Y$ is selected.
True Direction (X → Y):
[ Encode X ] + [ Encode Smooth Mechanism Y|X ] = Shorter Codelength
Anti-Causal Direction (Y → X):
[ Encode Y ] + [ Encode Contrived Mechanism X|Y ] = Longer Codelength
This compression-based strategy avoids the pitfalls of traditional constraint-based causal discovery. Traditional methods rely on rigid frequentist significance tests with arbitrary p-value thresholds, which often fail on small datasets. By treating model selection strictly as a compression optimization problem, Honghua Dai 0001 et al. showed that MDL-based methods can accurately detect weak causal links using up to ten times less data than frequentist significance tests.
Breaking Statistical Symmetry
Why can't a complex model just overfit the anti-causal direction and achieve an artificially low description length? The answer lies in how MDL penalizes model complexity.
A highly complex, saturated model can fit any data distribution in any direction. However, under the MDL principle, the cost of encoding that complex model's parameters outweighs the gains in data fit. Yang Ni demonstrated this parsimony constraint in categorical data: while a full joint distribution is perfectly symmetric, a simpler model with fewer parameters will naturally yield a higher likelihood in the true causal direction, breaking the statistical symmetry.
To scale this to continuous and non-linear data, Quang-Duy Tran et al. introduced a variational Bayesian compression framework (COMIC). By using a variational objective that balances neural network parameter costs against data log-likelihood, the model naturally penalizes overfitting in the anti-causal direction, allowing the true causal path to emerge purely based on algorithmic simplicity.
Furthermore, this compression footprint is visible beyond simple averages. Natasa Tagasovska et al. showed that evaluating the compressibility of data across multiple conditional quantiles reveals causal asymmetries in the shape of the noise distribution—such as heteroscedasticity—that mean-based regression models completely miss.
Entropic Causal Inference
When dealing with discrete or categorical variables, the compression framework can be elegantly framed as Entropic Causal Inference.
Consider a structural causal model where an effect is generated by a deterministic function of its cause and an independent exogenous noise variable: $Y = f(X, E)$. The complexity of the mechanism is directly tied to the randomness of this noise. If the mechanism is simple and clean, the noise variable $E$ should have low Shannon entropy.
If we attempt to model the system in the wrong direction ($Y \to X$), the inferred noise variable must absorb the structural dependencies of the true forward function. This causes the entropy of the anti-causal noise to swell.
Alex Dimakis et al. established that this entropy gap serves as a highly reliable mathematical indicator for distinguishing cause from effect. As the system size grows, this gap becomes even more pronounced. Dmitriy Katz proved that as the number of states in categorical variables increases, the entropy required to model the incorrect direction grows continuously, while the true causal direction maintains low, constant noise entropy. This widening complexity gap makes the true direction increasingly identifiable.
Scaling to Graphs, Confounders, and Environments
While distinguishing a single cause and effect is instructive, real-world data involves complex networks, unmeasured variables, and changing environments. The MDL framework scales naturally to handle these challenges.
Multivariate Graphs
Instead of evaluating isolated pairs, algorithms can search for the global structure of an entire network. Sascha Xu developed a framework (TOPIC) that identifies the exact topological ordering of a system by finding the sequence that optimizes data compression across all variables. Similarly, Spencer Compton extended entropic causal inference to multivariate directed acyclic graphs (DAGs) by searching for the graph structure that minimizes the sum of conditional entropies for all variables.
Unearthing Hidden Confounders
One of the biggest hurdles in causal discovery is "causal sufficiency"—the assumption that you have measured every relevant variable. If an unmeasured variable (a hidden confounder) causes both $X$ and $Y$, standard methods can mistake their correlation for a direct causal link.
MDL solves this by asking a simple question: Does inventing a hidden variable make the overall system easier to describe? David Kaltenpoth et al. demonstrated that if introducing a latent variable reduces the total description length of the observed data, the system can reliably infer both the presence and the influence of a hidden confounder.
Leveraging Multiple Environments
When data is collected across multiple environments (e.g., different experimental conditions or hospitals), the true causal mechanism remains invariant or changes independently across those contexts. In contrast, because the anti-causal direction mixes the mechanism and the source distribution, any change in the environment forces the anti-causal model to require highly complex, non-independent explanations.
Michael Kamp et al. and David Kaltenpoth et al. leveraged this multi-environment asymmetry. By finding the graph configuration that yields the most compact, compressed representation of data across all contexts simultaneously, their frameworks can reconstruct global causal networks and pinpoint exactly where local interventions occurred without needing to be told which environments were altered.
Key Foundational Work
A Study of Causal Discovery With Weak Links and Small Samples (1997) — contributed 3 concept elements to this direction.
Causal Inference by Choosing Graphs with Most Plausible Markov Kernels (2006) — contributed 2 concept elements to this direction.