🤖 machine learning

Graph-Free Root Cause Analysis

The paper introduces PRISM, a graph-free framework that overcomes the limitations of existing anomaly-score-based root cause analysis methods by providing theoretical guarantees and achieving significantly higher accuracy and speed across real-world datasets.

Original authors: Luan Pham

Published 2026-01-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Luan Pham

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, bustling hospital. Suddenly, the emergency room starts overflowing, the surgery lights flicker, and the pharmacy computers freeze. You need to find out why this is happening immediately, or the whole hospital could collapse.

This is the problem of Root Cause Analysis (RCA). In the digital world, "hospitals" are complex computer systems (like online shopping sites or banking apps) made of hundreds of tiny, connected programs called "microservices." When one breaks, it often breaks the others too.

The Old Way: Guessing by the Loudest Scream

Traditionally, when things go wrong, engineers look at a list of "anomaly scores." Think of this like a room full of people screaming. The old method assumes that the person screaming the loudest is the one who started the trouble.

The Paper's Problem: This assumption is often wrong.
Imagine a small leak in a pipe (the root cause) in the basement. It drips slowly. But because the water flows through a long, narrow pipe, it builds up pressure and bursts a massive floodgate in the lobby.

The Basement Leak (Root Cause): Drips quietly. Low "scream" (low anomaly score).
The Lobby Flood (Downstream Effect): A massive deluge. High "scream" (huge anomaly score).

If you just listen for the loudest scream, you'll rush to the lobby to fix the flood, missing the tiny leak in the basement that caused it all. The paper calls this the "fan-in" problem: small delays or errors can pile up and look huge downstream, tricking the system.

The New Solution: PRISM (The Detective with Two Eyes)

The authors propose a new framework called PRISM. Instead of just listening for the loudest scream, PRISM looks at two different types of "evidence" for every part of the system:

Internal Properties (The "Gut Feeling"): These are things happening inside a component that other components can't see. Examples: CPU usage, memory levels, or internal code states.
External Properties (The "Public Face"): These are things other components can see. Examples: How long it takes to reply (latency) or how often it crashes (error rate).

The Magic Insight:

The Real Culprit (Root Cause): Has a problem in BOTH its gut (internal) and its public face (external). It's sick inside, and it's acting weird outside.
The Innocent Bystanders (Affected Components): They look fine on the inside (their gut is healthy), but they are acting weird on the outside because they are reacting to the sick component.

The Analogy:
Think of a person with a fever.

The Sick Person (Root Cause): They feel hot inside (Internal) and their skin is burning red (External).
The Person Next to Them (Affected): They feel fine inside (Internal), but they are sweating and panicking because they are standing next to the fire (External).

PRISM looks for the component that is "sick" on the inside and the outside. It ignores the ones that are only "panicking" on the outside.

How It Works (Without a Map)

Usually, to solve these puzzles, you need a perfect map (a dependency graph) showing exactly how every piece connects to every other piece. But in huge, changing systems, nobody has a perfect map.

PRISM is special because it doesn't need the map. It just looks at the data: "Who is acting weird internally? Who is acting weird externally?" By combining these two signals, it can pinpoint the culprit even if the map is missing.

The Results: Fast and Accurate

The authors tested PRISM on 735 real-world failure cases from nine different systems (like online boutiques and ticket booking apps).

Accuracy: PRISM found the exact root cause as the #1 guess 68% of the time. The best previous method only got it right 19% of the time. That's a huge jump (258% improvement).
Speed: It's incredibly fast. It takes about 8 milliseconds (less than the blink of an eye) to diagnose a problem. Some other methods take seconds or even minutes.

Why This Matters

In the real world, when a system fails, every second counts. If you spend 30 seconds trying to figure out which computer is broken, you might lose thousands of dollars or, as the paper notes, even endanger lives (like in hospital systems).

PRISM offers a simple, fast, and highly accurate way to find the "leaky pipe" in the basement, even when the "flood" in the lobby is screaming the loudest, and even when you don't have a blueprint of the building.

Technical Summary: Graph-Free Root Cause Analysis via PRISM

Problem Statement

In complex, evolving IT systems (e.g., microservices), rapid Root Cause Analysis (RCA) is critical to prevent cascading failures. Existing RCA approaches face a fundamental dichotomy:

Graph-Based Methods: These assume a known dependency graph or attempt to construct one via causal discovery. However, dependency graphs are often unavailable in large systems, and causal discovery techniques have proven limited in accuracy and scalability.
Score-Based Methods (Graph-Free): These rank components by anomaly scores, operating under the assumption that the root cause exhibits the highest anomaly score. The paper argues this assumption is fundamentally flawed when faults propagate. In "fan-in" patterns (e.g., a service calling a backend $k$ times), a small delay at the root cause can accumulate into a massive downstream anomaly. Consequently, affected components often exhibit higher anomaly scores than the actual root cause, misleading score-based ranking.

Methodology: The PRISM Framework

The authors propose PRISM, a simple and efficient framework for RCA that operates without structural dependency knowledge. PRISM relies on a novel observation: a fundamental asymmetry between root causes and affected components regarding their internal and external properties.

1. The Component-Property Model

PRISM formalizes a class of systems using the Component-Property Model, which decomposes system properties into two distinct categories:

Internal Properties ( $I$ ): Local to a component and not directly observable by others (e.g., CPU usage, memory utilization, queue length, internal state variables).
External Properties ( $E$ ): Observable by other components through interactions (e.g., response latency, error rates).

The model is built on two axioms:

Axiom 2.5 (Intracomponent): Internal properties are causal ancestors of external properties within a component. Faults originate internally and manifest externally.
Axiom 2.6 (Intercomponent Isolation): Causal influence between components occurs only through external properties. A component cannot directly alter another component's internal state.

Key Insight: A root cause component exhibits anomalies in both its internal and external properties. In contrast, affected (downstream) components exhibit anomalies only in their external properties (due to propagation), while their internal properties remain at nominal levels.

2. The PRISM Pipeline

PRISM executes RCA in three stages:

Anomaly Scoring: Computes deviation-based anomaly scores (e.g., z-score, IQR-based) for all properties. The paper proves that deviation-based scorers satisfy monotonicity and injectivity, which are theoretically necessary to distinguish distinct deviation magnitudes. This contrasts with Information-Theoretic (IT) scorers, which suffer from saturation and lack injectivity when anomalies exceed historical bounds.
Score Pooling: Aggregates property-level scores into component-level scores:
- $S^I_i$ : Pooled internal score for component $C_i$ .
- $S^E_i$ : Pooled external score for component $C_i$ .
- The pooling function is monotonic and permutation-invariant (e.g., max, sum, mean).
Root Cause Ranking: Combines $S^I_i$ and $S^E_i$ into a final root cause score $M(C_i)$ . PRISM proposes two scoring functions:
- Additive Score ( $M_{add}$ ): $S^I + S^E - \log(1 + S^I + S^E)$ .
- Conjunctive Score ( $M_{conj}$ ): $\min(S^I, S^E)$ .
Both functions satisfy internal boundedness, ensuring that a component's final score is controlled by its internal anomaly score. This prevents affected components (which have high $S^E$ but nominal $S^I$ ) from outranking the root cause (which has high $S^E$ and high $S^I$ ).

Key Contributions

PRISM Framework: A graph-free RCA framework that effectively localizes root causes by exploiting the distinction between internal and external property anomalies.
Theoretical Guarantees: The paper formalizes the Component-Property Model and proves that under Axioms 2.5 and 2.6, PRISM correctly ranks the root cause above affected components. It also establishes that deviation-based scorers are necessary to avoid the saturation issues inherent in IT-based scorers.
Empirical Validation: Extensive experiments on 735 failure cases across 9 real-world datasets (RCAEval benchmark).

Results

Accuracy: PRISM achieves 68% Top-1 accuracy, a 258% improvement over the best baseline (BARO, which achieved 19%). It also achieves 91% Top-3 accuracy.
Efficiency: PRISM requires only 8ms per diagnosis (median), making it nearly as fast as the fastest baseline (BARO at 6.3ms) and orders of magnitude faster than graph-based or LLM-based methods (e.g., PC-PageRank at 1.2s, RCLAgent at 79s).
Robustness:
- PRISM is robust to different pooling strategies (max, sum, mean) and scoring functions.
- It performs exceptionally well on resource faults (100% Top-3 on CPU, MEM, DISK, SOCKET) and maintains strong performance on network faults.
- It achieves highest accuracy with early post-fault observations (81% Top-1 at 10% data), enabling immediate diagnosis before fault propagation accumulates noise.
Ablation: Removing the internal-external decomposition (e.g., ranking by marginal scores alone) drops Top-1 accuracy to 19%, confirming the necessity of the proposed approach.

Significance and Claims

The paper claims that PRISM addresses a critical gap in RCA: the inability to diagnose failures when dependency graphs are unknown and when downstream anomalies amplify beyond the root cause. By shifting the focus from "highest anomaly score" to "anomaly in both internal and external properties," PRISM provides a theoretically grounded, efficient, and highly accurate solution for modern microservice systems. The authors emphasize that this approach does not require causal discovery or structural knowledge, making it applicable to large, evolving systems where such information is often unavailable. The work demonstrates that simple, principled decomposition of observables can outperform complex causal inference and graph-based methods in both accuracy and speed.