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

GALA+ is a graph-augmented LLM agentic framework for root cause analysis (RCA) and incident response in microservices. It addresses three core challenges: (1) the service where a problem is observed may differ from the true fault origin, requiring reasoning over service dependencies; (2) different telemetry signals may point to different suspects, requiring multi-modal fusion; and (3) identifying the faulty service alone is insufficient—engineers need an explanation of failure propagation and actionable steps.

The framework operates in four phases:

• Phase I (Initial Hypothesis Generation): Combines a metrics-based ranking using BARO (Bayesian online change-point detection and causal DAG construction) with a novel trace-based ranking module called STRIX (Structural Trace Ranking via Intermodal eXploration). STRIX constructs a weighted dependency graph from traces and evaluates three diagnostic dimensions per service: Instability (p99/p50 latency ratio), Centrality (PageRank weighted by fan-in/fan-out ratio), and Impact (own processing latency scaled by traffic volume). These are aggregated via Reciprocal Rank Fusion. A Consolidation Agent then fuses the two rankings into a unified candidate set with confidence scores, handling cross-modal consensus, trace-only candidates (inferring fault types), and metrics-only candidates (reduced confidence).

• Phase II (Pod-Centric Context Synthesis): Each candidate pod's metrics, logs, and traces are distilled into a compact diagnostic bundle preserving temporal patterns (JSON serialization), dependency context (1-hop subgraph), and error signals (log distillation retaining error-level entries).

• Phase III (Graph-Guided Agentic Investigation): Parallel Investigator Agents start from top-k candidates and reason over diagnostic bundles. If confidence is below a threshold (θ=0.6), they expand to dependency neighbors in random batches (size b=2), following fault-propagation edges with depth-bounded expansion. This keeps search localized while preserving diagnostic completeness. Assessments are stored in a shared investigation memory.

• Phase IV (Diagnostic Synthesis and Incident Response): An Evidence Synthesis Agent produces a final ranking governed by two arbitration rules: signal anchoring (initial confidence scores act as grounded priors) and chain coherence (top candidate must explain downstream symptoms). A Remediation Agent generates a structured incident summary and three stratified action recommendations: immediate mitigation, permanent fix, and preventative measure.

The paper also introduces SURE-Score, a human-guided evaluation framework co-developed with industry SRE experts, assessing four dimensions: Evidence Groundedness, Operational Feasibility, Diagnostic Precision, and Triage Logic. It uses a checklist constructed via Think-Aloud Elaboration from eight SRE experts and four LLMs, then evaluated by two independent LLMs (Qwen3 and Llama-4-Maverick) with human-validated reference reports.

Key results:

• On OnlineBoutique: 74.44% AC@1, 98.89% AC@3, 0.854 MRR

• On TrainTicket: 73.33% AC@1, 85.56% AC@3, 0.801 MRR

• Outperforms the best LLM-based baseline (Flow-of-Action) by over 25 percentage points in AC@1 on both datasets (statistically significant via McNemar's test, p < 0.001)

• Outperforms the best non-LLM baseline (CIRCA on OB, BARO on TT) by +7.77 and +6.66 AC@1 points respectively

• On AegisLab benchmark (25 fault types), achieves best MRR, AC@1, and AC@3, improving MRR over Flow-of-Action from 0.38 to 0.48

• GALA+ achieves the highest SURE-Score ratings across all four dimensions, confirmed by both dual-LLM grading and independent human SRE evaluation (Spearman ρ=0.92 between automated and human scores)

• Ablation studies show STRIX contributes significantly (removing it drops AC@1 from 74.44% to 35.56% on OB), and among STRIX dimensions, Instability is most discriminative (removing it drops AC@1 from 51.14% to 18.18% on OB)

• LLM choice matters: gpt-4.1 achieves highest AC@1 (78.9%), but llama-4-maverick offers near-top accuracy (77.8%) at lowest cost (0.003 per incident); GPT-4.1-mini is the default backbone (74.4% AC@1 at 0.022)

• Parameter study shows robustness: moderate parallel branches (k=6), pruning threshold θ=0.6, and batch size b=2 provide the best balance

The paper concludes that topology-constrained reasoning is a promising alternative to unconstrained agentic exploration in domains with rich relational structure, and identifies evidence groundedness as an open challenge for current LLM-based RCA methods.

Improvements to AI systems:

1. Add topology-constrained reasoning to agentic frameworks. Instead of letting LLM agents explore freely, constrain their search to a dependency graph with depth-bounded expansion and batch-based neighbor sampling. This prevents hallucinated or irrelevant investigation paths and improves diagnostic precision in systems with known relational structure (e.g., microservices, network topologies, supply chains).

2. Implement multi-modal fusion with reciprocal rank fusion (RRF). Combine heterogeneous signals (metrics, traces, logs) by ranking each modality separately and fusing via RRF, rather than concatenating raw data. This handles conflicting evidence gracefully and produces a unified candidate list with confidence scores, reducing false positives from single-signal overconfidence.

3. Add a consolidation agent for cross-modal consensus arbitration. When signals disagree (e.g., trace says service A, metrics say service B), the agent should explicitly reason about consensus, trace-only evidence (inferring fault type from propagation patterns), and metrics-only evidence (assigning lower confidence). This improves robustness to missing or noisy telemetry.

4. Introduce signal anchoring and chain coherence rules for final ranking. When generating a final diagnosis, anchor the ranking to initial confidence scores (grounded priors) and require that the top candidate explain downstream symptoms (chain coherence). This prevents the LLM from drifting to plausible but unsupported conclusions and ensures the explanation is causally consistent.

5. Use structured diagnostic bundles for context compression. Instead of feeding raw logs/metrics/traces to the LLM, distill them into compact, JSON-serialized bundles that preserve temporal patterns, 1-hop dependency context, and error-level log entries. This reduces token cost, improves focus, and makes the reasoning process more auditable.

6. Add stratified action recommendations (immediate mitigation, permanent fix, prevention). The AI should not just identify the fault but generate three-tier remediation plans, separating urgent containment from long-term fixes. This increases operational feasibility and aligns with real incident response workflows.

7. Implement a human-guided evaluation framework (SURE-Score) for RCA outputs. Use a checklist co-developed with domain experts (via think-aloud) to score AI-generated diagnoses on evidence groundedness, operational feasibility, diagnostic precision, and triage logic. This provides a reproducible, expert-aligned metric for comparing RCA systems beyond accuracy alone.

8. Enable cost-aware backbone selection. The system should dynamically choose between LLMs based on accuracy-cost tradeoffs (e.g., llama-4-maverick for near-top accuracy at 7x lower cost). This makes the framework deployable in production with budget constraints without sacrificing much performance.

9. Add fault-type inference from trace-only candidates. When metrics are missing or noisy, the AI should infer the likely fault type (e.g., latency spike, error burst, resource exhaustion) from structural trace patterns (instability, centrality, impact). This improves recall in partial observability scenarios.

10. Use shared investigation memory across parallel agents. When multiple agents explore different candidate services, store their intermediate assessments in a shared memory to avoid redundant exploration and enable cross-agent evidence aggregation. This improves efficiency and consistency in large dependency graphs.

What the improved AI system can do:

• Diagnose root causes in complex distributed systems (microservices, cloud infrastructure, IoT networks) with high accuracy (AC@1 > 74% on standard benchmarks) while explaining why the fault propagated and how to fix it.

• Handle conflicting or incomplete telemetry by fusing multiple signals with confidence weighting, and still produce actionable diagnoses even when one data source is unavailable.

• Operate cost-effectively at scale by selecting the cheapest LLM that meets accuracy thresholds, and by compressing context into structured bundles that reduce token usage.

• Provide human-auditable, expert-aligned incident reports with evidence grounding, triage logic, and three-tier remediation plans, making it usable by on-call engineers without deep ML expertise.

• Adapt to new relational domains (e.g., network fault localization, database query optimization, financial transaction tracing) by replacing the dependency graph with any known relational structure, without retraining.

• Benchmark itself against expert-defined quality criteria (SURE-Score) and improve over time based on feedback, rather than relying solely on accuracy metrics that may not reflect operational value.

Microservice root cause analysis (RCA) requires correlating failures across heterogeneous telemetry within complex service dependency graphs. Existing methods often rely on a single telemetry modality; recent LLM-based approaches can suffer from unconstrained exploration and hallucination; and most systems stop at fault ranking without producing actionable incident response. We present GALA+, a graph-augmented LLM agentic framework centered on graph-guided investigation, which uses service dependencies to bound exploration and refine diagnosis through localized multi-modal evidence. For initial hypothesis generation, GALA+ combines complementary telemetry signals with STRIX, a novel trace- and graph-structure-aware scoring module. GALA+ then produces ranked diagnoses, incident summaries, and stratified action recommendations. We further introduce SURE-Score, a human-guided evaluation framework co-developed with industry SRE experts for assessing RCA-specific output quality beyond conventional text similarity metrics. On two microservice benchmarks, GALA+ consistently achieves the strongest overall results, surpassing the best LLM-based baseline by more than 25 percentage points in AC@1, while also receiving the highest ratings from both SURE-Score and independent human SRE evaluation.