🤖 AI

GALA: Graph-Augmented LLM Agents for Root Cause Analysis and Incident Response in Microservices

The paper presents GALA+, a graph-augmented LLM agentic framework that leverages service dependency graphs and multi-modal telemetry to enhance root cause analysis and incident response in microservices, achieving superior performance over existing baselines and receiving high validation from industry experts.

Original authors: Yifang Tian, Yaming Liu, Zichun Chong, Zihang Huang, Yiran Li, Hans-Arno Jacobsen

Published 2026-08-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Yifang Tian, Yaming Liu, Zichun Chong, Zihang Huang, Yiran Li, Hans-Arno Jacobsen

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 a massive, bustling city where thousands of tiny, specialized shops (called "microservices") work together to run a giant online mall. Each shop handles one specific job, like taking orders, checking inventory, or processing payments. They talk to each other constantly through a complex web of phone lines and delivery routes. When everything works, the city runs smoothly. But when something breaks, it's a nightmare. A delay in the "payment shop" might look like a problem in the "order shop," even though the real trouble started miles away in the "inventory warehouse." This is the world of Root Cause Analysis (RCA). It's the detective work engineers do to figure out where a problem actually started, not just where it showed up. Traditionally, they've used math to spot patterns in numbers (like traffic speed) or looked at logs (like police reports). But these methods often get confused by the sheer complexity of the city. Recently, scientists have tried using Large Language Models (LLMs)—super-smart AI chatbots that can read and reason—to act as detectives. However, these AI detectives can sometimes get lost, chase wild goose chases, or make up facts (a problem called "hallucination") because they don't have a map of the city's layout.

This is where a new framework called GALA+ comes in, designed by researchers at the University of Toronto. Think of GALA+ as a team of AI detectives who are given a strict, detailed map of the city's delivery routes before they start their investigation. Instead of letting the AI wander aimlessly through the entire city, GALA+ forces the AI to only look at the specific shops connected to the one that first reported a problem. It's like telling a detective, "Don't check the whole city; just check the three shops this one called, and the three shops that called it." The system uses two different types of clues to start the hunt: one looks at the speed and volume of traffic (metrics), and the other, a new tool called STRIX, looks at the actual delivery routes and timing (traces) to spot who is acting suspiciously. Once the AI has a shortlist of suspects, it sends out specialized agents to investigate them one by one, checking their logs and performance data. If a suspect looks innocent, the agent moves to the next shop on the map. If they look guilty, the investigation stops there.

The paper finds that this "map-guided" approach is a game-changer. In tests using two different simulated city environments (one called OnlineBoutique and another called TrainTicket), GALA+ correctly identified the true source of the problem as the very first suspect in 74.44% of cases on the first dataset and 73.33% on the second. This is a massive improvement, beating the next-best AI method by more than 25 percentage points. The researchers also created a new way to grade the AI's reports, called SURE-Score, which checks if the AI's explanation makes sense to a real human engineer. GALA+ scored the highest on this test, proving it doesn't just guess the right answer but can also explain why and suggest exactly how to fix it. The study suggests that by keeping AI detectives focused on the logical connections between services rather than letting them roam free, we can solve digital emergencies much faster and with far fewer mistakes.

Technical Summary: GALA+ (Graph-Augmented LLM Agents for Root Cause Analysis and Incident Response in Microservices)

1. Problem Statement

Modern microservice architectures introduce significant operational complexity due to intricate dependency graphs and heterogeneous telemetry data (metrics, logs, and traces). When failures occur, Site Reliability Engineers (SREs) face three core challenges:

Fault Propagation: The observed symptom (e.g., high latency on Service A) often differs from the true root cause (e.g., CPU saturation on a downstream Service B), requiring reasoning over service dependencies rather than isolated inspection.
Multi-Modal Ambiguity: Different telemetry signals may point to conflicting suspects; accurate diagnosis requires fusing these modalities rather than relying on a single source.
Actionable Response: Identifying the faulty service is insufficient; engineers require a causal explanation of the failure propagation and stratified remediation steps (immediate mitigation, permanent fix, prevention).

Existing approaches fall short: statistical methods often rely on single modalities or static heuristics; multi-modal approaches may lose modality-specific signals; and recent Large Language Model (LLM) agents often suffer from unconstrained exploration, hallucination, and a lack of topological grounding, leading to excessive search overhead and degraded precision. Furthermore, standard evaluation metrics (BLEU, ROUGE) fail to assess the causal grounding and operational specificity required for RCA.

2. Methodology: GALA+ Framework

GALA+ is a graph-augmented LLM agentic framework designed to constrain reasoning within the service dependency graph. It operates in four coordinated phases:

Phase I: Initial Hypothesis Generation

GALA+ generates a coarse ranking of likely root-cause pods by fusing two complementary signals:

Metrics-Based Ranking (BARO): Uses Bayesian online change-point detection to identify anomalies and construct a causal DAG, scoring services by their causal influence on observed anomalies.
Trace-Based Ranking (STRIX): A novel module that analyzes distributed traces and service dependency topology. It computes three diagnostic dimensions:
- Instability ( $\phi_1$ ): The ratio of P99 to P50 latency, capturing resource contention.
- Centrality ( $\phi_2$ ): A weighted PageRank incorporating fan-in/fan-out ratios to identify structural bottlenecks.
- Impact ( $\phi_3$ ): A decomposition of latency to distinguish processing delays from downstream waiting times.
- Fusion: These rankings are combined via Reciprocal Rank Fusion (RRF). A Consolidation Agent then reasons over the asymmetric information (e.g., trace-only vs. metrics-only candidates) to produce a unified ranked list with confidence scores.

Phase II: Pod-Centric Context Synthesis

Raw telemetry is too voluminous for direct LLM processing. For each candidate pod, GALA+ distills a Diagnostic Bundle ( $D_i$ ) containing:

Serialized metrics (JSON format) within the incident window.
A 1-hop dependency subgraph with edge attributes (latency, call volume).
Distilled logs (error-level entries only, ordered by timestamp).

Phase III: Graph-Guided Agentic Investigation

To avoid unconstrained exploration, GALA+ employs Investigator Agents that perform a bounded search:

Agents start from the top- $k$ candidates in the initial ranking.
They reason over the diagnostic bundle to produce a structured assessment (confidence, evidence, causal explanation).
If local evidence is inconclusive (confidence < threshold $\theta$ ), the agent expands to a randomized batch of neighbors in the dependency graph.
This process continues until high-confidence evidence is found or all neighbors are exhausted, ensuring the search remains localized to structurally plausible paths.

Phase IV: Diagnostic Synthesis and Incident Response

An Evidence Synthesis Agent reconciles findings from all investigation branches. It applies two rules:

Signal Anchoring: Prevents hallucination by treating initial confidence scores as priors.
Chain Coherence: Promotes a candidate to the top rank only if its causal chain explains symptoms observed across all explored branches.
Finally, a Remediation Agent generates a structured incident summary and three stratified action recommendations (immediate, permanent, preventative).

3. Evaluation Framework: SURE-Score

Recognizing that standard NLG metrics fail to capture RCA quality, the authors introduce SURE-Score (Summarization Recommendation Score), a human-guided evaluation framework co-developed with industry SREs. It assesses reports on four dimensions:

Evidence Groundedness: Reasoning must be supported by concrete telemetry (logs, metrics, traces).
Operational Feasibility: Recommendations must be concrete and implementable.
Diagnostic Precision: Requires specific service/pod identifiers and quantitative metrics.
Triage Logic: The narrative must follow a professional flow from symptoms to root cause.

Evaluation involves both dual-LLM grading (using different models to avoid self-preference bias) and independent human SRE assessment.

4. Experimental Results

GALA+ was evaluated on two microservice benchmarks: OnlineBoutique (17 services) and TrainTicket (69 services), with an additional evaluation on the AegisLab benchmark.

Root Cause Ranking (RQ1): GALA+ achieved the highest accuracy across all datasets. On OnlineBoutique, it reached 74.44% AC@1 (vs. 48.35% for the best LLM baseline, Flow-of-Action). On TrainTicket, it achieved 73.33% AC@1 (vs. 47.78%). This represents an improvement of over 25 percentage points over the strongest LLM-based baseline. The improvement was statistically significant ( $p < 0.001$ ).
Incident Summarization (RQ2): Under SURE-Score, GALA+ consistently outperformed all baselines across all four dimensions. While traditional metrics (BERTScore, ROUGE) showed little differentiation, SURE-Score highlighted GALA+'s superior operational feasibility and diagnostic precision. Human SRE evaluations confirmed these rankings.
Ablation Studies (RQ3): Removing STRIX or the Graph-Guided Investigation phase significantly degraded performance, confirming that both trace-structure awareness and bounded agentic reasoning are critical.
LLM Selection (RQ4): GALA+ performs well across various LLMs. Open-source models like llama-4-maverick and Qwen3-80B achieved near-top-tier accuracy at a fraction of the cost of proprietary models.
Parameter Sensitivity (RQ5): The framework is robust across a range of parallel branches ( $k$ ), pruning thresholds ( $\theta$ ), and batch sizes ( $b$ ).

5. Key Contributions

Dual-Signal Hypothesis Generation: A mechanism fusing metrics-based causal ranking with STRIX, a novel trace- and graph-structure-aware scoring module, to produce a unified candidate set.
Graph-Guided Agentic Investigation: A topology-constrained parallel investigation framework where agents follow fault-propagation edges with confidence-driven, depth-bounded expansion, reducing the search space while preserving diagnostic completeness.
Incident Response and Evaluation: A pipeline producing ranked diagnoses, structured summaries, and stratified action recommendations, evaluated via SURE-Score, a human-guided framework that outperforms conventional text similarity metrics.

6. Significance and Claims

The paper claims that GALA+ addresses the limitations of existing RCA methods by constraining agentic reasoning to the service dependency graph, thereby preventing hallucination and excessive search overhead. The results demonstrate that topology-constrained reasoning is a promising alternative to unconstrained agentic exploration in domains with rich relational structures.

The authors modestly note that while GALA+ significantly improves diagnostic accuracy and operational utility, Evidence Groundedness remains a challenge for current LLM-based methods, as evaluators noted that LLMs often paraphrase telemetry rather than citing it verbatim. The work suggests that combining statistical hypothesis generation with graph-guided LLM reasoning offers a robust path toward automated, actionable incident response in microservices.