# Linear-Time Primitives for Algorithm Development in Graphical Causal Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 49 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 12 of 12)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Graphical Models for Processing Missing Data](https://mlsanity.com/paper/1801.03583/) (2018)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams)](https://mlsanity.com/paper/1301.7412/) (2013)
- [Separators and Adjustment Sets in Causal Graphs: Complete Criteria and an Algorithmic Framework](https://mlsanity.com/paper/1803.00116/) (2018)
- [Adjustment Identification Distance: A gadjid for Causal Structure Learning](https://mlsanity.com/paper/2402.08616/) (2024)
- [Finding and Listing Front-door Adjustment Sets](https://mlsanity.com/paper/2210.05816/) (2022)
- [Variable elimination, graph reduction and efficient g-formula](https://mlsanity.com/paper/2202.11994/) (2022)
- [Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs](https://mlsanity.com/paper/2211.16468/) (2022)
- [Deciding Morality of Graphs is NP-complete](https://mlsanity.com/paper/1303.1501/) (2013)
- [An Improved Combinatorial Algorithm for Boolean Matrix Multiplication](https://mlsanity.com/paper/1505.06811/) (2015)

## Abstract (arXiv)

We introduce CIfly, a framework for efficient algorithmic primitives in graphical causal inference that isolates reachability as a reusable core operation. It builds on the insight that many causal reasoning tasks can be reduced to reachability in purpose-built state-space graphs that can be constructed on the fly during traversal. We formalize a rule table schema for specifying such algorithms and prove they run in linear time. We establish CIfly as a more efficient alternative to the common primitives moralization and latent projection, which we show are computationally equivalent to Boolean matrix multiplication. Our open-source Rust implementation parses rule table text files and runs the specified CIfly algorithms providing high-performance execution accessible from Python and R. We demonstrate CIfly's utility by re-implementing a range of established causal inference tasks within the framework and by developing new algorithms for instrumental variables. These contributions position CIfly as a flexible and scalable backbone for graphical causal inference, guiding algorithm development and enabling easy and efficient deployment.