Root Cause Analysis of Failures in Microservices via Bayesian Root Cause Discovery

Kenneth Lee, Zihan Zhou, Murat KocaogluICML 2026 · OpenReview

TL;DR

This paper introduces Bayesian Root Cause Discovery (BRCD), a novel method for pinpointing failure origins in complex microservice systems. BRCD leverages a partial causal structure learned before failures occur, enabling efficient and statistically guaranteed root cause identification even with limited failure data, outperforming existing methods on synthetic and real-world benchmarks.

What Problem Does This Paper Address?

Modern cloud systems are built on microservices, offering scalability and flexibility. However, this interconnectedness creates intricate dependency chains that make diagnosing failures incredibly challenging. Traditional root cause analysis (RCA) methods often struggle with this complexity, requiring either complete knowledge of the system's causal graph or a large number of costly post-failure interventions. This sample inefficiency is a major bottleneck, especially in systems where failures are rare but impactful. The paper aims to bridge this gap by developing a sample-efficient, statistically sound RCA method for microservices that can operate with incomplete causal information.

Methods

The core innovation is Bayesian Root Cause Discovery (BRCD). Instead of learning the full causal graph from scratch, BRCD starts with a CPDAG (Completed Partially Directed Acyclic Graph), representing a partial causal structure learned from pre-failure observational data. This CPDAG is then used in conjunction with post-failure (interventional) data.

Key methodological contributions include:

  • Leveraging $\mathcal{I}$-MECs: BRCD groups causal graphs into Interventional Markov Equivalence Classes ($\mathcal{I}$-MECs). Since all graphs within an $\mathcal{I}$-MEC have the same interventional likelihood, this significantly reduces the search space for Bayesian inference.
  • Efficient Bayesian Inference: By avoiding the enumeration of all possible DAGs for each root cause candidate, BRCD performs more efficient posterior updates.
  • Uniform DAG Sampling: BRCD utilizes a recent framework for sampling DAGs from an $\mathcal{I}$-MEC, enabling statistical consistency guarantees.
  • Nonparametric Approach: The method does not rely on specific parametric assumptions about the underlying causal relationships or data distributions, making it more generalizable.
  • Theoretical Guarantees: The paper provides theoretical guarantees for identifiability and finite-sample posterior bounds, ensuring the method's reliability.

Datasets

The paper evaluates BRCD on:

  • Synthetic Benchmarks: Randomly generated DAGs of varying sizes (up to 1000 nodes) with simulated observational and interventional data.
  • Real-world Microservice Systems:
    • Online Boutique: A Google Cloud Platform demo application.
  • Sockshop: An e-commerce application.
  • Petshop: A benchmark dataset introduced by Hardt et al. (2023), known for its complexity with near-constant variables and missing values.

Key Insights and Ideas

  • Partial Causal Knowledge is Powerful: The paper demonstrates that even a partial causal structure (CPDAG) learned from pre-failure data is sufficient to significantly improve RCA performance, reducing the need for extensive post-failure data collection.
  • $\mathcal{I}$-MECs as a Smart Shortcut: Grouping causal graphs into $\mathcal{I}$-MECs is a crucial insight that dramatically prunes the search space for Bayesian inference, making the approach computationally feasible.
  • Bayesian Inference for Robustness: The Bayesian framework naturally handles uncertainty and provides principled posterior distributions for root cause candidates, which is vital in noisy and data-scarce microservice environments.
  • Sample Efficiency is Key: BRCD's effectiveness in low-failure-sample regimes highlights its practical relevance for real-world microservice systems where failures are infrequent but critical.

Key Results

  • State-of-the-Art Accuracy: BRCD consistently achieves the highest Top-$l$ accuracy across various synthetic benchmarks and real-world microservice systems (Online Boutique, Sockshop, Petshop), outperforming existing methods like RCD and RCG.
  • Scalability: BRCD scales efficiently to systems with up to 1000 nodes, demonstrating its practical applicability to large-scale microservice architectures.
  • Effectiveness with Limited Data: The method remains accurate even with very few anomalous samples, a critical advantage in real-world RCA scenarios. For instance, in the Petshop dataset with only 5 anomalous samples per case, BRCD shows strong performance.
  • Theoretical Guarantees: The paper provides the first theoretical guarantees for nonparametric RCA with partial causal structures, including identifiability and finite-sample posterior bounds.

Limitations and Future Work

  • Reliance on Partial Causal Structure: BRCD's performance is contingent on the availability of a partial causal structure (CPDAG). While the paper suggests this can be obtained via observational causal discovery, its quality can impact results.
  • Estimating Likelihoods: Practical implementation requires estimators for likelihoods, and while the paper provides guidance, challenges remain in achieving optimal performance with limited anomalous data.
  • Tighter Bounds: The authors suggest developing tighter bounds on sample complexity and exploring how various priors can further enhance BRCD's performance.
  • Exploring Other RCA Techniques: Future work could investigate how to integrate insights from other RCA techniques or expert knowledge into BRCD's prior.

Summary updated

Abstract

Modern cloud systems rely on architectures with many interconnected microservices, which enable scalability and flexibility but make troubleshooting failures difficult. Identifying the root cause requires navigating complex dependencies, often beyond the capacity of domain experts. Causal models offer a principled approach to root cause analysis (RCA), but prior methods are typically sample inefficient, as they assume access to the full causal graph or require large numbers of post-failure interventions. We introduce Bayesian Root Cause Discovery (BRCD), which leverages a partial causal structure (a CPDAG learned during the pre-failure period) and performs Bayesian inference without enumerating all DAGs from each interventional Markov equivalence class ($\mathcal{I}$-MEC) for each root cause candidate. Using a recent uniform DAG sampling framework (Wienöbst et al., 2023), BRCD provides the first statistical consistency guarantees for nonparametric RCA, with both identifiability and finite-sample posterior bounds under $\varepsilon$-vanishing approximation. Empirically, across synthetic benchmarks and three microservice systems (Online Boutique, Sockshop, Petshop), BRCD achieves state-of-the-art top-$l$ accuracy while remaining effective in low-failure-sample regimes and scaling to large graphs.
BibTeX
@inproceedings{lee2026root,
  author = {Kenneth Lee and Zihan Zhou and Murat Kocaoglu},
  title = {{Root Cause Analysis of Failures in Microservices via Bayesian Root Cause Discovery}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=EOSV5tlpqg},
}
Figure