Probabilities of Causation and Root Cause Analysis with Quasi-Markovian Models

Eduardo R. Laurentino, Fábio Gagliardi Cozman, Denis Deratani Mauá, Daniel Angelo Esteves Lawand, Davi Goncalves Bezerra Coelho, Lucas Martins MarquesarXiv 2025 · DOI · arXiv

Introduction

In the realm of Site Reliability Engineering (SRE), identifying the root cause of a system failure is often a race against time. Modern microservices exacerbate this challenge; a single bottleneck can trigger a chain reaction of errors across dozens of services. Traditional correlation-based monitoring often fails because of "latent confounders"—unobserved factors like background system processes or network jitter that influence multiple observed variables simultaneously.

Causal inference provides a rigorous framework for Root Cause Analysis (RCA) through metrics like the Probability of Necessity (PN) and Probability of Sufficiency (PS). PN asks: "Would the failure have been avoided if this specific event hadn't occurred?" while PS asks: "Is this event enough to cause the failure on its own?" However, calculating these probabilities in complex, quasi-Markovian models (models with latent confounders) is computationally intensive, often requiring the solution of multilinear optimization problems just to find probability bounds.

Algorithmic Pruning and Counterfactual Graphs

To address the computational complexity of counterfactual reasoning, the authors propose a two-step simplification process. First, they construct counterfactual graphs that represent the system's state under hypothetical scenarios.

Construction of a counterfactual graph from original and interventional models.

The core innovation lies in Theorems 1 and 2, which provide the mathematical basis for "pruning" these graphs. By identifying and removing variables that are either not ancestors of the target node or are d-separated from it, the researchers can significantly reduce the degree of the multilinear objective function. For instance, a problem that would normally require degree-6 optimization can be reduced to a bilinear (degree-2) problem, allowing solvers like Gurobi to find solutions in under 10 milliseconds.

Causal Narrative Ranking

Beyond individual variables, the paper introduces Causal Narrative Ranking (Algorithm 1). Instead of presenting an engineer with a single suspect node, the system identifies and ranks entire causal paths—or "narratives"—leading to the failure. Using a pruned Depth-First Search (DFS) starting from the incident node, the algorithm calculates a Path Significance score ($S(\pi)$). This score accounts for both the likelihood of the root cause and the strength of the causal links throughout the chain (e.g., Database Update → Increased Latency → Service Timeout → Frontend Error).

Results and Insights

The framework was evaluated on three synthetic models of increasing complexity, simulating real-world microservice failures. The researchers found that the Probability of Necessity (PN) is far superior to sufficiency-based metrics for RCA. While PS often identifies factors that could cause a problem, PN accurately identifies the specific trigger that did cause it in a particular instance.

Pruning a complex counterfactual graph to simplify the optimization objective.

As shown in the figure above, the pruning technique is essential for scalability. Complex graphs representing large-scale architectures can be stripped down to their essential causal components, turning a "hard" optimization problem into one that can be solved in milliseconds without losing accuracy in the probability bounds. In all test cases, PN and its interventional variant (w-PN) correctly identified the ground-truth root cause.

Conclusion

By combining counterfactual graph pruning with path-based ranking, this research transforms causal inference from a theoretical exercise into a practical tool for real-time system monitoring. While currently limited to binary variables (e.g., service UP vs. DOWN), the ability to provide actionable "causal narratives" in milliseconds marks a significant step forward for automated root cause analysis. Future work will focus on extending the framework to handle the continuous telemetry data typical of industrial environments.

Summary updated

BibTeX
@misc{laurentino2025probabilities,
  author = {Eduardo R. Laurentino and Fábio Gagliardi Cozman and Denis Deratani Mauá and Daniel Angelo Esteves Lawand and Davi Goncalves Bezerra Coelho and Lucas Martins Marques},
  title = {{Probabilities of Causation and Root Cause Analysis with Quasi-Markovian Models}},
  year = {2025},
  eprint = {2509.02535},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.02535},
}
Figure