Sleuth: A Trace-Based Root Cause Analysis System for Large-Scale Microservices with Graph Neural Networks

When a request through a cloud application is too slow, engineers find the culprit with rules of thumb — flag whatever is more than three standard deviations above normal — and those rules were validated on systems with tens of services; production systems have hundreds of services and thousands of calls per request, and this paper (Alibaba) shows by simulation from real production latency data that the rules decay to near-uselessness at that scale, with one common method falling from 29 percent to 6 percent accuracy, because any single service's contribution is diluted as the system grows; worse, every open-source benchmark is small enough that the rules still work there, so the failure was invisible; the answer is to ask a counterfactual instead — would this request have been fine if that service had behaved normally — answered by a network whose structure does not depend on the call graph, so it survives growth, service updates, and transplanting to an application it has never seen.

The argument in one glance

Problem

One slow request, a thousand suspects

Cloud applications are now built from hundreds of small services that call one another, so a single user request fans out into a tree of calls that can reach two thousand entries. When that request misses its latency target, someone has to determine which service was responsible — and reading the trace by hand is hopeless at that size. Production measurements from Alibaba report hundreds of services in one application and more than a thousand calls in a single request graph. This is daily work for site reliability engineers, and getting it wrong means either chasing the wrong team or shipping a fix that changes nothing.
What people did

Flag whatever looks unusual

The standard tools are threshold rules, and they are reasonable. Flag any step more than three standard deviations above its normal duration. Or take the longest step. Or use a percentile cut-off, or a correlation against end-to-end latency. These are cheap, need no training, are easy for an engineer to reason about, and they work — they have been the backbone of trace debugging for years, and remain in production use across the industry.
Why it fell short

The rules dissolve as the system grows, and no benchmark was big enough to notice

The authors simulate a system growing to 400 services, with each service latency drawn from heavy-tailed distributions LEARNED FROM A PRODUCTION APPLICATION. The accuracy of the three-standard-deviation rule falls away sharply, and the same happens to percentile, correlation and workload-aware thresholds. The reason is structural: as the system grows, any single service contributes a smaller share of the total, so its anomaly is diluted below the threshold. Three standard deviations also stops being the right constant, because the latency distribution is heavy-tailed rather than bell-shaped. And the largest open-source microservice benchmark has 41 services — every published benchmark sits in the region where the rules still look fine.
This paper's idea

Ask a counterfactual, with a model that does not depend on the call graph

This paper (Alibaba — Gan, Liu, Zhang, Zhou, Wu, Jiang) replaces the rule with a question that is operationally what you actually want: if this service had behaved normally, would the request still have missed its target? A graph neural network learns, without any labels, how each call's duration and errors propagate up to its caller, and answers that question by simulation. The critical property is that the network's structure does not depend on the shape of the call graph, so one model handles every request shape, keeps working when services are added, and transfers to an application it has never seen — at 1024 calls it holds 86 percent accuracy where the threshold rule reaches 6. To measure any of this, they also had to build a generator for production-scale benchmarks.

Why this problem is worth solving

The vocabulary here is worth pinning down, because the definition of the answer is itself part of the contribution.

DISTRIBUTED TRACING records the path of one request through a system of services. Each unit of work gets a SPAN carrying the service it ran in, the operation name, start and end timestamps and an error status, plus a pointer to the span that called it. Linked together those form a tree, sometimes thousands of spans deep and wide, which is the request’s CALL GRAPH. When the request misses its SERVICE-LEVEL OBJECTIVE — its latency or availability target — someone must find what caused that. This paper defines the answer precisely and usefully: a service is a ROOT CAUSE if restoring it to a normal state would have prevented the request from violating its target. That is a COUNTERFACTUAL — a claim about a world that did not happen — and it is exactly the thing an engineer wants to know, because it is the same as asking whether fixing this service would have helped

The failure of the existing tools is not a matter of tuning, and its cause is worth stating carefully.

A rule of thumb like “flag anything more than three standard deviations above normal” assumes the anomaly stands out against the total. In a small system that holds: if one of ten services doubles its time, the request visibly doubles. Grow the system to hundreds of services and the same absolute slowdown is a small fraction of the whole, so the signal is DILUTED below the threshold while remaining the genuine cause. Two further things break. Service latencies are HEAVY-TAILED, meaning extreme values occur far more often than a bell curve predicts, so three standard deviations stops being the right constant — the authors show the best value drifts as scale changes. And whether a given span causes a violation depends on the OTHER spans in that request, so no fixed threshold can be right for every trace. The same span may or may not push a request over its target depending on what else happened

What people did before, and where it broke

Threshold and heuristic rules. Flag the longest step, or anything past a percentile or a standard-deviation cut-off, or correlate each step against end-to-end latency. Cheap, untrained, explainable, and widely deployed.
But they decay with scale. Measured on the largest benchmark here, the percentile threshold reaches 6 percent accuracy and a published real-time correlation method 5 percent, against 48 and 15 percent respectively on the smallest. The rules are not wrong so much as scoped to a system size the industry has left behind.
Learn the causal graph from the data. Systems such as CauseInfer and Microscope discover causal structure statistically and then apply thresholds to it. Principled, but learning a causal graph from observational data is NP-hard, which rules it out at call-graph scale.
Bring in expert knowledge. eBay’s Groot combines rules, statistics and deep learning over an event graph, and works — but it needs site reliability engineers to curate the causal graph and rules, so it does not transfer between systems.
Train a supervised model. Seer and MEPFL learn to predict failures from labelled data. In production, labels are largely unavailable: the data is machine-generated at enormous volume and interpreting it takes expertise, so it cannot be crowdsourced the way images or text can.
Generate counterfactuals with a generative model. Sage builds a causal graph from the architecture and trains a variational autoencoder to answer the counterfactual — the right question, and the direct predecessor here. But it trains a SEPARATE model per node, so its parameters grow with the application, from 1.3MB to 84MB across the range tested.
The gap. Every approach was tied to the shape of the specific system: rules tuned to its scale, causal graphs curated for it, or a model with one component per service. Nothing could be trained once and reused, and nothing had been measured at the scale where the question actually gets hard, because no benchmark existed at that scale.

How a counterfactual gets answered at scale

Separate a span's own time, group the duplicates, learn the propagation, then simulate the fix

Collect the trace and flag the slow ones

Standard tracing collectors gather spans from every service and reconstruct each request call tree. A request that misses its target is picked up for analysis. Only the fields the tracing standard requires are used, so nothing depends on optional attributes, logs or metrics that may be missing.
↓ →
Separate each span own time from its waiting new

A caller duration includes waiting for the services it called, which hides how much time it is itself responsible for. Since traces cannot say whether a caller was idle or working while waiting, define the EXCLUSIVE duration as the time a span does not overlap any of its children, and the same for errors that did not come from below.
↓ →
Group traces that share a failure mode new

One incident produces thousands of similar failing traces with the same cause, so analysing each is wasted work. Compare traces cheaply, cluster them, and pick the most central member of each group to analyse on behalf of all of them.
↓ →
Learn how delay and errors travel upward new

Train a graph neural network to predict each span duration and error status from its children, with no labels — the training signal is simply reconstructing what the trace already shows. The chosen form encodes real behaviour: a child contributes nothing until it exceeds the time hidden by its siblings, and stops contributing once a timeout caps it.
↓ →
Simulate restoring a service and check the outcome new

Rank the services by how much unexplained delay and error they carry, then repeatedly ask the trained model what the request would have looked like if the top candidate had behaved normally. Stop when the model says the request would have met its target. Those services are the answer.
↓ →
Keep the model independent of the call graph new

Because the network aggregates from neighbours in a way that does not depend on their number or order, one model handles every request shape, keeps working when services are added or removed, and can be pre-trained on one application and applied to another.

Evaluated on SockShop and DeathStarBench SocialNetwork plus four generated benchmarks of 16 to 1024 calls, deployed on a 100-node Kubernetes cluster, with faults injected by chaos tooling to provide ground truth. Trained on eight V100 GPUs; inference runs on a 16-core CPU server with no GPU.

The idea

Replace the rule with the question the rule was approximating. A threshold rule is a proxy for something an engineer actually wants to know — would fixing this have helped? — and the paper goes back to that question directly. It defines a root cause as a service whose restoration to normal would have prevented the violation, then trains a model well enough to answer it by simulation: set the suspect span to its median duration with no errors, propagate the consequences upward through the learned model, and see whether the request would still have missed its target. This handles a case no threshold can, which the authors state plainly — the same span may or may not cause a violation depending on what else happened in that request, so a fixed cut-off is wrong for some traces by construction. Going back to the question a long-serving heuristic was approximating, once the heuristic stops tracking it, is the same measure-the-true-thing move covered elsewhere on this site where an accepted metric quietly stopped predicting the outcome it was adopted for, and the fix was to measure the outcome.

Make the model’s structure independent of what varies. The deepest design choice is architectural. Request shapes differ from one call to the next, and change again whenever services are deployed, so a model whose structure mirrors the call graph must be rebuilt constantly — the predecessor system needs neurons inserted and removed as services appear. A graph neural network instead aggregates from a node’s neighbours using functions that do not care how many neighbours there are or what order they come in, so a single fixed model handles any shape. The consequences compound: parameters stop growing with the application, so training and inference scale sublinearly; adding nine services mid-graph costs accuracy rather than a rebuild; and because the same model processes every node, what it learns about one service transfers to another, making a pre-trained model possible at all. Arranging a design so its structure does not depend on the dimension that varies is the same separate-what-changes-from-what-does-not principle covered elsewhere on this site where an accelerator is built from primitives rather than operations, and where the expensive tuning is placed on the part of a problem that the unknown does not reach.

Build the measuring instrument, then measure. The most quietly important contribution is that the paper could not have made its argument without first building a benchmark generator. The largest open-source microservice benchmark has 41 services; production has hundreds. Every published evaluation of these heuristics therefore took place in the regime where they work, which is why their collapse was not common knowledge. So the authors built a generator that produces runnable Kubernetes applications at arbitrary scale, with call graph statistics drawn from published production measurements, realistic service names, execution graphs distinguishing synchronous from asynchronous calls, and pluggable workloads that stress real hardware. They are candid that this does not fully mirror production and argue only that its scale and diversity exceed what was available. Noticing that the benchmark suite does not resemble the workloads the technique will meet, and that this hides a real failure, is the same check-your-benchmarks-against-reality lesson covered elsewhere on this site where a field optimised for structures that real inputs do not have.

Finding the culprit in one slow request

Following the pipeline on a request whose parent span calls two children

A caller P starts at t0 and ends at t5; it calls A over t1 to t3, and B over t2 to t4. Numbers from the paper's evaluation.

Step 1 of 5

Work out what each span is itself responsible for

The caller ran for the whole window, but most of that was waiting. The trace cannot say whether it was idle or working while its children ran, so instead of guessing, define its EXCLUSIVE duration as the time it overlapped no child at all — here the stretch before A started plus the stretch after B finished.

the same definition applies to errors: a span has an exclusive error only if the failure did not arrive from one of its children
the true self-duration is some unknown function of this quantity, which the model learns rather than the engineer assuming

Why it works

A root cause is defined as a service whose repair would have prevented the violation → the model is asked to simulate exactly that repair → so a span that matters in one request and not another is judged correctly in each, which no fixed threshold can do.
The network aggregates from neighbours regardless of their number or order → one fixed model fits every request shape → so parameters stop growing with the system, and training and inference rise only 3.3 and 16.3 times across a 64-fold increase in calls, against 39.5 and 33.9 for the predecessor.
The same model processes every node rather than one model per service → what it learns about one service applies to others → so a model pre-trained on 50 production applications runs on an unseen one with no fine-tuning at a cost of 4 to 5 percent accuracy.
Adding services changes the graph but not the model → no neurons need inserting when the system is updated → so adding nine services mid-graph leaves accuracy broadly intact where the predecessor falls to 29 percent.
Traces are compared as weighted sets keyed by span identity including ancestors → similarity costs time linear in trace size rather than quadratic or worse → making it affordable to analyse one representative per failure mode instead of thousands of traces.

What it costs (trade-offs and scope)

Grouping traces trades accuracy for speed. Clustering costs 6.1 to 9.5 percent accuracy, worst at the largest scale, where traces become so similar that the algorithm merges genuinely different causes into one group. It buys 6.4 to 15.3 times faster inference.
It tells you where, not why. The causal graph comes only from traces, with no logs or system metrics, so the answer is a service, pod or node — not a reason. The authors name this as the main limitation.
Pre-trained models can latch onto names. A model pre-trained on one dataset loses up to 19 percent accuracy when service names are replaced with unfamiliar ones, revealing it had partly memorised them. Training on more diverse data reduces this, and fine-tuning removes it.
Ground truth is injected, not observed. Accuracy is measured against faults the authors themselves injected. They justify this openly: production incidents are sometimes misdiagnosed by engineers, so real traces often have no trustworthy answer to check against.
The benchmarks are synthetic. The large-scale results rest on generated applications matched to published production statistics. The authors state they do not fully mirror production and claim only that they exceed what was available.

The evaluation

Testing covered two open-source applications — SockShop with 11 services and DeathStarBench’s SocialNetwork with 26 — plus four generated benchmarks of 16, 64, 256 and 1024 calls, the largest producing traces of up to 2,046 spans. All ran on a 100-node Kubernetes cluster. Faults were injected at container, pod and node level using chaos tooling, with the injection log serving as ground truth. Two metrics are reported: an F1 score, and a stricter accuracy requiring the predicted set of root causes to match the real set exactly. Training used eight V100 GPUs; inference deliberately runs on a 16-core CPU server to keep deployment cheap.

Finding which service caused a slow request

Property	Threshold and heuristic rules	One generative model per service	One graph model, counterfactual query
Exact-match accuracy at 11 services
Exact-match accuracy at 1024 calls
Model size as the system grows
When nine services are added
Moving to a new application

Against rule-based and correlation-based methods the improvement in accuracy ranges from 84 percent to 16.2 times. Across a 64-fold increase in call count, training and inference time rise 3.3 and 16.3 times against 39.5 and 33.9 for the predecessor, whose model grows from 1.3MB to 84MB. Clustering cuts inference time by 6.4 to 15.3 times for 6.1 to 9.5 percent accuracy. A model pre-trained on 50 production applications transfers to an unseen one with no fine-tuning at 4 to 5 percent cost, and a query on a thousand-span trace completes in under a second on a CPU.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The most important scoping point is what the answer contains: because the causal graph is built only from traces, with no logs or system metrics, the output is a service, pod or node rather than an explanation. The authors name this as the main limitation and suggest a broader causal graph informed by operations expertise would be needed to go further — so this narrows the search from a thousand suspects to one, and the diagnosis still starts there. Two evidence caveats deserve weight. Ground truth comes from faults the authors injected rather than incidents that occurred, which they justify openly on the grounds that production incidents are sometimes misdiagnosed by engineers and so provide no trustworthy answer to check against. And the large-scale results rest on generated applications matched to published production statistics, which the authors state plainly do not fully mirror production, claiming only that their scale exceeds anything available. Within the method there are real trades: grouping traces buys 6.4 to 15.3 times faster inference for 6.1 to 9.5 percent accuracy, and is worst at the largest scale precisely where it is most needed, because traces become so similar that different causes merge. A pre-trained model can also latch onto service names — swapping them for unfamiliar ones costs up to 19 percent — though training on more diverse data reduces this and fine-tuning removes it, which is itself a useful finding about what such models learn.

Background

When the rule stops tracking the thing it approximated, and the benchmark hides it

This paper sits in the site’s datacenter and cloud cluster and rhymes with several ideas covered elsewhere on this site. Its opening move is the clearest instance here of a pattern the site keeps meeting: a long-serving heuristic stopped predicting the outcome it was adopted for — the three-standard-deviation rule decaying from 29 percent to 6 percent accuracy as a system grows — and the fix is to go back and measure the outcome itself, the same correction the instruction-prefetching page makes when cache misses stop predicting stalls and the graph-mining page makes when network traffic stops predicting time. It adds a second failure the others do not have: every open-source benchmark is small enough that the rules still work there, so the field could not see the problem, a benchmarks-do-not-resemble-applications gap the quantum optimisation and recommendation-inference pages also exploit. Its architectural principle, that the model’s structure must not depend on the thing that varies, is exactly the reasoning the reconfigurable-accelerator page uses when it builds primitives rather than operations, and the dynamic-shape compilation page uses when it moves the expensive tuning onto the part of the problem the unknown does not reach — and here it buys three things at once: flat scaling, survival of service updates, and transfer to unseen applications. Its clustering step, analysing one representative per failure mode rather than every trace, is the same collapse-the-equivalent compression the program-analysis and recommendation pages use, and like them it reports the accuracy that compression costs rather than hiding it.

If you remember only three things

1. Cloud applications now fan a single request into thousands of service calls, and the tools engineers use to find which service caused a slow request are threshold rules developed when systems had tens of services. Simulating growth to 400 services with latency distributions learned from a production application shows those rules decaying badly, and measured on a 1024-call benchmark a percentile threshold reaches 6 percent exact-match accuracy against 29 on the smallest. The cause is structural: a single service contributes a shrinking share of a growing total, so its anomaly is diluted below any fixed cut-off, and latencies are heavy-tailed so no constant number of standard deviations is right at every scale.
2. The replacement is to ask the question the rule was approximating — would this request have met its target if that service had behaved normally — and answer it by simulation. A graph neural network learns, with no labels, how each call duration and errors propagate to its caller, trained simply to reconstruct traces the system already produced. Its form encodes real behaviour: a child contributes nothing to its caller until it exceeds what a sibling was hiding, and nothing beyond the point a timeout caps it, with asynchronous calls falling out as the case where those two thresholds coincide.
3. The property that makes it work at scale is that the model structure does not depend on the call graph, since it aggregates from neighbours regardless of their number or order. That single choice buys flat accuracy as the system grows, 86 percent at 1024 calls where the predecessor reaches 71; training and inference rising 3.3 and 16.3 times against 39.5 and 33.9 across a 64-fold growth, because parameters stop growing with the application; survival of service updates that force the predecessor to insert neurons and drop to 29 percent; and transfer to an unseen application with no fine-tuning for 4 to 5 percent accuracy. Making the argument at all required building a generator for production-scale benchmarks, because none existed.

Check yourself

Check your understanding

1. A rule flagging any step more than three standard deviations above normal works well on a small system and reaches 6 percent accuracy on a large one. Predict why growth breaks it.
2. The design uses a graph neural network specifically because its structure does not depend on the call graph. Predict what that single property buys.
3. Rather than measuring how much time a span spent on its own work, the design measures the time it did not overlap any child. Predict why the simpler quantity is unavailable.
4. Traces are trees, so tree-edit distance is the natural way to compare them, yet the design converts each trace into a weighted SET instead. Predict what that costs and how structure survives.

Sources

Sleuth: A Trace-Based Root Cause Analysis System for Large-Scale Microservices with Graph Neural Networks (ACM Digital Library, DOI 10.1145/3623278.3624758) — ASPLOS 2023; the full 14-page paper, read in full for this explainer.