# Causal Discovery using Compression-Complexity Measures

arXiv: https://arxiv.org/abs/2010.09336 · HTML: https://mlsanity.com/paper/2010.09336/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

## Built on by (most cited first, 5 of 5)

- [Algorithmic causal structure emerging through compression](https://mlsanity.com/paper/2502.04210/) (2025)
- [GT-CausIn: a novel causal-based insight for traffic prediction](https://mlsanity.com/paper/2212.05782/) (2022)
- [Permutation Decision Trees](https://mlsanity.com/paper/2306.02617/) (2023)
- [Causal Discovery and Classification Using Lempel-Ziv Complexity](https://mlsanity.com/paper/2411.01881/) (2024)
- [Dictionary Based Pattern Entropy for Causal Direction Discovery](https://mlsanity.com/paper/2603.04473/) (2026)

## Abstract (arXiv)

Causal inference is one of the most fundamental problems across all domains of science. We address the problem of inferring a causal direction from two observed discrete symbolic sequences X and Y. We present a framework which relies on lossless compressors for inferring context-free grammars (CFGs) from sequence pairs and quantifies the extent to which the grammar inferred from one sequence compresses the other sequence. We infer X causes Y if the grammar inferred from X better compresses Y than in the other direction. To put this notion to practice, we propose three models that use the Compression-Complexity Measures (CCMs) - Lempel-Ziv (LZ) complexity and Effort-To-Compress (ETC) to infer CFGs and discover causal directions without demanding temporal structures. We evaluate these models on synthetic and real-world benchmarks and empirically observe performances competitive with current state-of-the-art methods. Lastly, we present two unique applications of the proposed models for causal inference directly from pairs of genome sequences belonging to the SARS-CoV-2 virus. Using a large number of sequences, we show that our models capture directed causal information exchange between sequence pairs, presenting novel opportunities for addressing key issues such as contact-tracing, motif discovery, evolution of virulence and pathogenicity in future applications.