✨ TL;DR
This paper presents an efficient symbolic computation algorithm for determining whether causal effects can be identified from observational data with latent confounders in linear structural causal models. The algorithm finds the lowest-degree identifying formulas in quasi-polynomial time, making causal identifiability analysis practical for larger problems.
Determining identifiability of causal effects from observational data when latent confounders are present is a fundamental problem in causal inference. For linear structural causal models, this is theoretically decidable through symbolic computation, but existing approaches based on Gröbner bases have doubly exponential complexity, making them computationally infeasible beyond small problem instances. There is a need for practical algorithms that can efficiently determine rational identifiability without this prohibitive computational burden.
The paper develops an efficient algorithm for deciding rational identifiability in linear structural causal models through symbolic computation. Rather than relying on standard Gröbner basis methods, the approach is designed to find the lowest degree identifying formulas for a given causal effect. The algorithm is guaranteed to return an identifying formula of a prespecified maximal degree if one exists, and achieves this in quasi-polynomial time complexity.
What the paper shows.
The paper presents an algorithm that provably finds the lowest degree identifying formulas for causal effects in linear structural causal models. For any causal effect of interest with a prespecified maximal degree, the algorithm returns an identifying formula in quasi-polynomial time if one exists, significantly improving upon the doubly exponential complexity of standard Gröbner basis methods.
The paper focuses specifically on linear structural causal models and rational identifiability, which may limit applicability to nonlinear causal systems. The practical performance on real-world problems of varying sizes is not empirically evaluated in the abstract. The prespecification of a maximal degree parameter may require prior knowledge or multiple runs to determine appropriate bounds.
✨ Generated by Claude · Apr 25, 2026 · Read the PDF for authoritative content.