When one component of a large system fails, the failure spreads to its neighbors and produces a flood of alarms. The engineer, or the algorithm, then has to work backwards to find the component where the fault began. The best current methods for this backward search treat the system's wiring diagram as a set of yes/no links: either service A depends on service B or it does not. Separately, there are good tools for measuring how strongly one component depends on another, for example how tightly a caller's latency tracks its callee's. These two lines of work have not been joined. This note proposes joining them in one specific way. Measured dependency strength becomes a probabilistic prior over which node is the root cause. That prior then decides which statistical tests the search runs first. It never removes edges from the graph.
The claim that makes this worth doing is a cost argument. Under a uniform prior, root-cause search must spend about $\log_2 n$ tests just to cover $n$ candidates. With an informative prior, that term should shrink toward the prior's entropy, which works like a Huffman code for where faults tend to start. Because the prior only sets the order of tests and never cuts edges, a wrong strength estimate costs a few extra tests rather than a missed root cause. We test this on microservice failure benchmarks, where strength comes from trace telemetry. We then test it on CRISPR perturbation screens, where the candidate strength signal is 3D chromatin contact. That second setting is a deliberate stress test, because physical contact is known to be a noisy stand-in for functional dependency.
Core Claim
Two lines of work set up the gap.
The first supplies a strength signal. AID measures how strongly a caller depends on a callee from per-minute call, error and latency series. Its method, Dynamic Status Warping, is a directed, lag-bounded relative of time warping. AID reduces error against expert labels by 61.1% in mean absolute error relative to Pearson, Spearman and Kendall correlation on Huawei Cloud traces. It stops at single-hop link weights and does no root-cause search.
The second supplies the search, but treats the graph as unweighted. RCG reduces single-root localization on a known causal graph to interactive graph search. It proves that $\Theta(\log_2 n + d\log_{1+d} n)$ invariance tests are necessary and sufficient, where $n$ is the number of nodes and $d$ the maximum out-degree. BRCD instead updates a Bayesian posterior over interventional equivalence classes, which are groups of causal graphs that cannot be told apart from the available data. This works from very few anomalous samples. Both methods learn binary skeletons and treat every adjacent node the same way.
Our claim is that calibrated dependency strength belongs in exactly one place: the prior over root causes. It does not belong in the graph structure. Concretely, let $w_{ij}\in[0,1]$ be the calibrated probability that an anomaly at $j$ produces an anomaly at $i$. Let $S$ be the set of components that raised alarms. We score each candidate root $r$ with an independent-cascade likelihood:
$$ \pi(r) \;\propto\; \Pr(S \mid r) \;=\; \prod_{i\in S}\Big(1-\prod_{j}(1-w_{ij}\,q_{rj})\Big)\prod_{i\notin S}\prod_{j}(1-w_{ij}\,q_{rj}), $$
Here $q_{rj}$ is the probability that the fault started at $r$ reaches $j$. It is computed by propagating the $w$ values from $r$, approximated by its value on the maximum-probability path to keep the cost near-linear in edges.
That prior $\pi$ is used in two ways. First, it replaces BRCD's uniform prior over roots. Second, it drives a weighted version of RCG's search, in which each invariance test is chosen to split the remaining prior mass as evenly as the graph allows. For binary search with priors, the classical result is an expected query count of about the entropy plus one. We therefore conjecture that the expected number of tests becomes
$$ \mathbb{E}[\#\text{tests}] \;\le\; H(\pi^\star) + O(d\log_{1+d} n), $$
where $\pi^\star$ is the true distribution of roots and $H$ its entropy. When $\pi$ is miscalibrated, the excess cost should be bounded by the KL divergence between $\pi^\star$ and $\pi$. Proving this inequality for RCG's search over directed acyclic graphs is part of the work. Showing it empirically is the main deliverable.
Research Program
The work has three parts.
The first part calibrates strength. AID's raw scores are not probabilities, so we map them to transmission probabilities $w_{ij}$ using isotonic regression on a small set of fault-injection runs. Injecting faults to grade dependencies as strong, medium or weak follows Bagchi et al.. We also report an uncalibrated variant to measure what calibration buys. AID is documented to degrade on asynchronous queues, so links passing through queues get a deliberately flattened weight near the population mean. That way the prior stays uninformative exactly where the strength signal is unreliable.
The second part is the search itself. We implement the prior-weighted test-selection rule on top of RCG's search and its conditional mutual information ranking, and plug $\pi$ into BRCD's posterior. We prove the entropy bound for trees, which is RCG's base case, and test whether it extends empirically to general directed acyclic graphs.
The third part is the biological transfer. In Perturb-seq data the "root cause" is the knocked-down gene. CDN already identifies it by comparing the gene-gene causal structures it infers from cells before and after the perturbation, ignoring spatial structure. We build $w$ from K562 chromatin contact between promoters and nearby regulatory elements. Where measured contact is sparse, we use contact maps predicted by MIX-HIC, which was evaluated on K562. The resulting $\pi$ is fed to CDN as a prior on its target scores.
We expect this transfer to be weak, and we state that in advance. Contact captures nearby, same-chromosome regulation, while most knockdown effects travel through transcription factors acting at a distance. Elements also collide in the nucleus without regulating each other. The genomic arm therefore asks a sharp question: does a noisy physical strength signal help or hurt, when it can only reorder tests and cannot delete edges?
Baselines
The naive reference point has two parts. The first is threshold alerting with a uniform prior over all alarming nodes, which is the alarm-storm regime documented by Characterizing and Mitigating Anti-patterns of Alerts. The second is personalized PageRank over the unweighted call graph. Both are run on the same incident windows as every other method.
The strongest existing methods are RCG and BRCD, run unchanged. The comparison is fair in four ways. They receive the same pre-failure normal data for learning the skeleton. They receive the same anomalous samples. They use the same conditional-independence test and significance level. The only difference is that our variant receives $\pi$.
The only reported number on the shared benchmark is RCG's 87% Top-1 accuracy on the 100-node microservice network, against 78% for RCD (RCG). For BRCD on Online Boutique and Petshop, no reported result was found on Lacuna. We will therefore rerun it ourselves rather than quote a figure.
On Perturb-seq the strongest baseline is CDN. Its reported normalized rank score reaches 0.98 on real K562 and RPE1 screens (CDN). That leaves almost no headroom at full data, so the comparison is made in a reduced-cells-per-perturbation regime where CDN's score falls.
Beating a baseline means one of two things. Either we match its Top-1 or Top-3 accuracy with at least 25% fewer invariance tests or anomalous samples, or we reach higher accuracy at equal budget. Gains must hold across five seeds and with confidence intervals that exclude zero.
The key ablations isolate how strength is used. Hard pruning cuts edges below a threshold, which is the tactic of Farinelli et al. and of operational practice (Managing Service Dependency); the threshold is tuned on the same validation incidents. The strength-only ranker sorts candidates by $\pi$ and runs no tests at all. The shuffled-weight control keeps the distribution of $w$ but permutes it across edges, which tests whether any gain comes from the weights' content rather than their marginal shape. In genomics, the extra control is a prior built from 1D genomic distance instead of 3D contact.
Why not just…?
Why not just prune weak edges and run RCG on what remains? This is the most serious threat. On clean synchronous call graphs it may match our method while running fewer tests. Its failure mode is that a root cause lying behind a link judged "weak" becomes unreachable. AID's documented problems with asynchronous queues make such links likely to be misjudged in practice. The synthetic sweep described below settles the question: if pruning matches the soft prior at every level of strength-signal noise, we drop the soft machinery and recommend pruning.
Why not just rank by intensity-weighted propagation and skip causal tests? It costs nothing at query time and could work when anomalies are cleanly separated. RCG's comparison against non-causal baselines (RUN, BARO) shows that methods without causal tests confuse parents with correlated descendants. The strength-only ablation measures directly how much the tests add on top of $\pi$.
Why not just feed contact maps or strengths as edge features to a learned model like CDN or GEARS? Learned feature use offers no guarantee of graceful degradation. Our design isolates strength as a prior whose cost under error is bounded by the KL divergence. Within the experimental design we test only the prior variant on CDN, comparing it with plain CDN under the same reduced cell budget. A head-to-head against a feature-augmented CDN would be a follow-up, and until it is run we do not claim the prior beats learned feature use.
Why not just use 1D distance instead of Hi-C? If the distance prior matches the contact prior, then 3D structure adds nothing for finding perturbation targets in this setting. We would report that as a negative result.
Proposed Experiments
The first experiment is the decisive synthetic sweep. We generate directed acyclic graphs of 100 to 1,000 nodes with heterogeneous true transmission strengths, matching BRCD's scale. The observed $w$ is a noisy copy of the true strength, with correlation $\rho$ swept from 0 to 1.
We plot tests-to-identify and Top-1 accuracy against $\rho$ for four arms: soft prior, hard pruning, strength-only ranking, and uniform RCG. The prediction is specific. The soft prior should approach the entropy bound as $\rho \to 1$, and should never fall below uniform RCG's accuracy as $\rho \to 0$. Hard pruning should lose accuracy sharply at low $\rho$. Strength-only ranking should plateau below the methods that run tests. If the soft prior is ever worse than uniform RCG in accuracy, the core claim fails.
The second experiment runs the real microservice benchmarks: Sock-shop, Online Boutique, Petshop and Train-Ticket. Train-Ticket is where AID's strength estimates were developed. We report Top-1 and Top-3 accuracy, invariance tests per incident, and accuracy as the number of anomalous samples shrinks to 5. We stratify results by whether the root sits behind an asynchronous link.
The third experiment is K562 Perturb-seq from the Replogle screens. We subsample to 5, 20 and 100 cells per perturbation and report CDN's normalized rank with and without the contact prior, the distance prior, and the shuffled prior. We also stratify by whether the downstream responders lie on the same chromosome as the knocked-down gene. A gain confined to same-chromosome responders, with nothing for responders elsewhere, is the expected and still informative outcome. A loss of accuracy in any stratum would show that physical proximity is too noisy to serve even as a soft prior.
References
- AID: Efficient Prediction of Aggregated Intensity of Dependency in Large-scale Cloud Systems
- Root Cause Analysis of Failures from Partial Causal Structures
- Root Cause Analysis of Failures in Microservices via Bayesian Root Cause Discovery
- Dependency Analysis in Distributed Systems using Fault Injection: Application to Problem Determination in an e-commerce Environment
- Predicting perturbation targets with causal differential networks
- Multimodal 3D Genome Pre-training
- Characterizing and Mitigating Anti-patterns of Alerts in Industrial Cloud Systems
- Bounded Approximate Decentralised Coordination using the Max-Sum Algorithm
- Managing Service Dependency for Cloud Reliability: The Industrial Practice
- Predicting transcriptional outcomes of novel multigene perturbations with GEARS