Root Cause Analysis of Outliers with Missing Structural Knowledge
Authors: William Roy Orchard
Nastaran Okati
Sergio Hernan Garrido Mejia
Patrick Blöbaum
Dominik Janzing
Venue: NeurIPS 2025 poster ()
Keywords: root cause analysis
causality
contribution analysis
actual causation
outliers
anomalies
Primary area: probabilistic_methods

Abstract: The goal of Root Cause Analysis (RCA) is to explain why an anomaly occurred by identifying where the fault originated. Several recent works model the anomalous event as resulting from a change in the causal mechanism at the root cause, i.e., as a soft intervention. RCA is then the task of identifying which causal mechanism changed. In real-world applications, one often has either few or only a single sample from the post-intervention distribution: a severe limitation for most methods, which assume one knows or can estimate the distribution. However, even those that do not are statistically ill-posed due to the need to probe regression models in regions of low probability density. In this paper, we propose simple, efficient methods to overcome both difficulties in the case where there is a single root cause and the causal graph is a polytree. When one knows the causal graph, we give guarantees for a traversal algorithm that requires only marginal anomaly scores and does not depend on specifying an arbitrary anomaly score cut-off. When one does not know the causal graph, we show that the heuristic of identifying root causes as the variables with the highest marginal anomaly scores is causally justified. To this end, we prove that anomalies with small scores are unlikely to cause those with larger scores in polytrees and give upper bounds for the likelihood of causal pathways with non-monotonic anomaly scores.

Root Cause Analysis of Outliers with Missing Structural Knowledge
William Roy Orchard'
Nastaran Okati" Max Planck Institute for Software Systems Kaiserslautem, Germany
University of Cambridge Cambridge, UK
wo223@cam. ac. uk
Sergio Hernan Garrido Mejia Max Planck Institute for Intelligent Systems
Amazon Tübingen, Germany
Patrick Blöbaum
Dominik Janzing
Amazon Tübingen, Germany
Amazon Tübingen, Germany
Abstract
The goal of Root Cause Analysis (RCA) is to explain why an anomaly occurred by identifying where the fault originated. Several recent works model the anomalous event as resulting from a change in the causal mechanism at the root cause, i.e., as soft intervention. RCA is then the task of identifying which causal mechanism changed. In real-world applications, one often has either few or only single sample from the post-intervention distribution; severe limitation for most methods, which assume one knows or can estimate the distribution. However, even those that do not are statistically ill ill-posed due the need to probe regression models in regions of low probability density. In this paper, we propose simple, efficient methods to overcome both difficulties in the case where there single root cause and the causal graph is polytree. When one knows the causal graph, we give guarantees for traversal algorithm that requires only marginal anomaly scores and does not depend on specifying an arbitrary anomaly score cut-off. When one does not know the causal graph, we show that the heuristic of identifying root causes as the variables with the highest marginal anomaly scores is causally justified. To this end, we prove that anomalies with small scores are unlikely to cause those with larger scores in polytrees and give upper bounds for the likelihood of causal pathways with non non-monotonic anomaly scores.
Introduction
When an anomaly occurs, it is essential to identify its root cause so that action can be taken to resolve it. As such, Root Cause Analysis (RCA), has become rich and rapidly developing area of research, with wide ranging applications from meteorology II, monitoring health 2
3), industrial
fabrication [), fraud detection [5], credit scoring (6). cloud applications 7
10
I2 and
more 13 14 15 16 17). Although many previous works have adopted a purely statistical approach to
RCA 18
19 20
21 22 relying on correlations, the fact that the goal is to take action distinguishes
"Authors contributed equally.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

it as a necessarily causal problem. The predominant choice in causal literature is to model the observed anomaly as being the result of change in the causal mechanism at the root cause, i.c. as a soft intervention. RCA can then be broadly understood as the task of identifying the variable whose mechanism changed. Budhathoki et al. [23 give a formalisation of RCA as a quantitative contribution analysis based on counterfactuals asking. "would the observed anomaly still be anomalous had this mechanism been as normal?" - but its dependence on knowing the full structural causal model is severe bottleneck to its practical application. As such, from a causal perspective, work on RCA is broadly categorised into two groups: those that require the causal DAG, and those that do not or try to infer it from data. With the causal DAG, widely used class of methods is traversal-basee in [2 25 9 26 wherein a variable is identified as a root cause if is anomalous, none of its parents anomalous, and it is linked to the target variable through path of anomalous variables. For example, Hardt et al. (27 apply such a traversal algorithm to data from cloud computing to identify the root cause of performance drops in a microservice-basse application [12 28 29] When the causal DAG is unknown, the main idea behind the second line of work is that the anomalies themselves can support causal discovery. For example, Ikram al. [TO] treat RCA causal discovery problem where the goal is to find the target(s) of a soft intervention [30]. Likewise, [31 32) describe how to use heavy-tailed distributions infer the causal DAG for linear models. In sense, this also amounts
as
to using anomalies for causal discovery - if one counts points in the tail as anomalies.
1.1 Our contributions
Most methods assume one knows can estimate the post-intervention, "anomalous", distribution, but in real-world scenarios, it is not uncommon to have only a single sample from the distribution. In business applications, faults must be resolved rapidly, leaving no time collect further samples. In personalised medicine, the goal is to treat each individual patient according to the unique root causes of their disease, and so while one has many samples of the healthy population, one assumes a priori that each diseased patient is unique. Even those methods that do not assume access to more than one sample from the anomalous distribution are often statistically ill-posed due to the need estimate causal conditional probabilities or else to probe regression models in regions with low probability density. In this paper, we argue that these challenges can be overcome when the task is to identify a single root cause, and propose two simple and efficient methods for doing so. In section 2 we give the preliminaries to causal RCA and introduce 'information theoretic' (IT) anomaly scores upon which our methods are based. In section 3 we show that marginal anomaly scores are already sufficient for drawing conclusions about the causal relationships between anomalies: first for cause-effect pairs and then more generally when the causal DAG is polytree. We show that marginal anomaly score 'jump'' along causal paths can enable identification of the root cause and propose SMOOTH TRAVERSAL, for when one knows the causal graph. We conclude Section 3 by arguing that the heuristic of selecting the variables with the highest IT anomaly scores as candidate root causes is causally justified in polytrees, and propose SCORE ORDERING, for when one does not know the causal graph. We also discuss its theoretical limitations. Finally, in Section 4 we compare existing approaches to RCA to our own proposals on both synthetic and real-world data, demonstrating that despite their simplicity, our approaches are competitive. To our knowledge, no other methods operate with causal guarantees in an RCA setting general as we address in this paper.
2 Preliminaries
We consider the scenario in which the value 2n of target variable Xn, has been flagged as an anomaly by an anomaly detection algorithm. We have jointly observed values (ri,,.., 2n) of variables (XI,..., Our goal is to identify a unique root cause of the anomaly 2n from among the variables X,,
We assume the causal relationships between Xi...., .,, are given by a Causal Bayesian Network (CBN) (33), so that their joint distribution factorises into causal conditionals according to an underly- ing causal DAG:
P(X X.,) II P(X, PA),
where each P(X; PA.)) corresponds to the causal mechanism of variable X, given its parents P.,, in the causal DAG. We then model the anomaly In having arisen due to one of the causal
2

---

mechanisms having been 'corrupted'. We observe only the single sample (#1...., drawn from the 'anomalous' distribution
" P( Xn) = P(XX) PAJ) II P(X: PAA,,
(2)
wherein the 'normal' mechanism P(x; PAş) has been replaced by a corrupted one P(X; PAj) the root cause. Identifying the root cause is then matter of identifying which causal conditional changed from the normal period based on a single sample from the anomalous one. While we can never exclude the case where several mechanisms are corrupted, we always start with the working hypothesis that there has been only one. If this does not work, we can still try hypotheses with more than one, but with the strong inductive bias of preferring explanations where most mechanisms worked as expected, in agreement with the so-called 'sparse mechanism shift hypothesis" [34 35 It also important to note that although we have adopted the language of CBNs, our results can be recast in terms of the counterfactual contribution analysis introduced in 23 (see Appendix Indeed, is noteworthy in itself that the counterfactual description can simplified to an interventional one for the case of identifying single root cause.
2.1 Anomaly score
We next define anomaly score, which we use in the following sections. Let X - TR be an appropriate feature map, which can be any existing anomaly score function, mapping elements of X to real values, for example, the z-score. Further, define the event
E (T(,,, 2 r(x.)),
of being at least as extreme as the observed event In according to the feature function т. As the goal of RCA identify which causal mechanism has been corrupted, an important interpretation of is as test statistic for the null hypothesis that I, was drawn from P(X,), i.e., Ho : X,, ~ P(X,). with (XT( 2 T(xx))
P(E) as the corresponding p-value. Small P(E) indicates that the null hypothesis is rejected with high confidence" and we assume rather that the usual mechanism generating samples from P(X,)) has been corrupted for that specific statistical unit. Since small p-values correspond to strong anomalies, we define the marginal anomaly score by
S(xn) == log ((T(X,) 2 T(z,)) = log P(E).
Since the logarithm of the probability of an event measures its surprise information theory 13 15 as in 233, we call anomaly scores with the above calibration IT scores for information theoretic. Given & observations ,,....,,y I including the single anomalous one, we will use the following simple e
5(x)) == - log 1 E E
(1,....,A) A)) with T(x))) 2 (-)))---
(5)
It is important to note that this value can be at most log k i.c.. the estimated score can attain the value s only when least e" samples have been used. We provide detailed sample complexity results for IT anomaly score estimation in Appendix B
In addition the marginal anomaly score, we also introduce the conditional IT anomaly score (as in the arXiv version of (23]): S(In pa,) == -og log P(T(X.) 2 T(2,)) PA, = pp.);
(6)
where now 7 becomes a test statistic for the null hypothesis that In was drawn according to its causal mechanism P(X,. PA,, = pa,) for that particular statistical unit. Although suppressed notationally, we allow variable-dependent feature functions т;, but they must coincide between marginal and conditional anomaly scores. As the goal of RCA, stated, is to identify which causal mechanism was corrupted, the conditional anomaly score is instrumental to what follows. To illustrate the difference between marginal and conditional anomaly scores, consider the following example:
"This interpretation is certainly invalid in a standard anomaly detection scenario where Eq. 3 is repeatedly computed for every observation in sequence. However, so-called anytime p-values (36) outside of the scope of this paper.
'This estimator is not just a finite sample approximation of 4 but also the negative logarithm of conformal p-value [37 for the null hypothesis of exchangeability.
3

---

Example 1 (Linear cause-effecc model). Consider causal model Y := N. N X. For
strictly increasing (e.g. the 2-score, T(y) = (y ( and observation (z, y), the marginal anomaly score S
log P(Y 2 y) is simply the 'surprise' of the one-sided tail event for Y. However, the conditional anomaly score Sty
log P(Y 2 X = = -log P(bx + N z y) - -log P(N 2 y - ba:), is a marginal anomaly score of the residual after accounting for X.
For the following sections, all proofs can be found in Appendix C Cunless otherwise indicated.
3 Root cause analysis when conditional probability estimation is ill ill-posed
To answer the question of which causal mechanism was corrupted for the sample (I1, Tn). we need to determine which value I; cannot be "explained" by the values of its parents according to its normal causal conditional, P(X; PA.). However, inferring the causal conditional statistically ill-posed, particularly when the number of parents is large. One could, for example, make the additive noise assumption [3 33 and thereby reduce the problem to that of estimating conditional expectations, but the problem remains ill ill-posed because analysing anomalies amounts to probing regression models in regions with low probability density. In this section, we show that causal relationships can be inferred between anomalies with given causal DAG together with only marginal anomaly scores {S(x)),... is a polytree. However, to introduce the ideas will need, start first with cause-effect pairs, then discuss the problem more generally in DAGs, and then lastly restrict our attention to polytrees.
S(x,) }, using the simple estimator in Eq. 5 in the case the causal DAG
3.1 Anomalies in cause and effect pairs
Let the causal DAG be X Y for two variables X, Y, and we observe (x, v) with anomaly scores S(x), S(y). We define two null hypotheses that state that each causal mechanism, P(X) or P(Y X). worked as normal: H. was drawn from P(X), and H1 y was drawn from P(Y X x). Note that Hy does not impose a constraint on X, it allows x to be drawn from an arbitrary distribution instead of P(X), only the mechanism generating y from æ assumed to have remained 'normal'. We show that whether one should reject one or both hypotheses can be determined from a comparison of (xx) and S(y) alone. To see how, we first need introduce definition which we will justify shortly:
Definition 3.1 (Bivariate score typicality). We say that observation (x, v) for X, Y satisfies score rypicality if
Sly x) 2 (5()) 5(x)
where|
. I+ denotes the positive part.
We then have the following criteria for rejecting Hº and Hy
Lemma 3.2 (p-value bound for marginal anomaly event.). H² can be rejected at level p S e- e5(x).
This follows immediately from the definition IT scores in Eq. On the other hand, we obtain: Lemma 3.3 (Anomalies rarely cause larger anomalies). Subject to score typicality, Hy can be rejected at level < -(()))
Proof. That HY can rejected at level p p (((yla) follows from the definition of conditional IT scores in Eq. the result then follows immediately, subject to score typicality.
O
Lemma 3.3 therefore states that, subject to score typicality, an anomaly of strength S(x) causes an anomaly of strength S(y) only with probability at most (--((s))((a))) i.e. an anomaly at X is unlikely cause much stronger anomaly at Y (see also Corollary 3.3 in 40 for an algorithmic information theoretic view of this result).
Score typicality, therefore, gives criterion for rejecting Hy using only marginal scores, but the question remains whether we should expect it to be satisfied. The following lemma shows that for any given y. although we cannot guarantec score typicality is satisfied for any particular x, we can conclude that the bound is likely to hold approximately for a randomly chosen z:
Lemma 3.4 (Score typicality probably holds approximately). Let the distribution of (possibly multivariate) be absolutely continuous with respect to the Lebesgue measure. For any sx S S(y) -

---

let x be chosen at random according to P(X | S(X) E (ex,S(y)) Then we obtain, with probability at least - 2/c, an x. for which the following inequality holds:
Syy x) 2 (S( - S(x)++ loge.
(8)
There are also non-trivial cases where score typicality holds exactly:
Lemma 3.5 (Injectivity and monotonicity imply score typicality). Let the mapping x: + S(x)) be
one-to-one, and P(S(Y) 2 S(y) S(X) = -(x)) s P(S(Y) 2 S(y) S(X) 2 S(x)). Then observation (x,y) v) satisfiex score typicality.
The first condition is the injectivity of S. The second is monotonicity condition, it says: increasing the anomaly score of X does not decrease the probability of anomaly event at Y. Both assumptions are satisfied for all (2, y). for example, for real-valued variables when := == f(X,N) where N is an independent noise term. f is monotonic X and N and 7 = =id.
In the following sections, wc state our results subject to score typicality for case of exposition, but we should keep in mind that Lemmas 3.4 and 3.5 show that could avoid it entirely, at the expense of having slightly weaker bounds holding for most samples, or by assuming injectivity and monotonicity.
Returning to our bivariate case, there is also third hypothesis, namely that x and y are causally unrelated. Even if there is a causal connection between X and Y. in this case X - Y, it could happen that æ being anomalous was irrelevant for the anomaly y because P(Y = x) P(Y). In other words, although æ is anomalous, happens to be an anomaly that does not render an anomaly at Y more likely. The corresponding null hypothesis is H x was drawn from P(X) and from P(Y). We find:
Lemma 3.6 (Bound on p-value for independent anomalies). HgY can be rejected level p S e- S(i( [1 + S(x) S(y)]-
The lemma follows from the fact that for independent variables X, Y, the corrected sum +(z)+ log[1 + Sxx) + S(y) =: (( y)) is a valid IT score for pairs and thus satisfies P(Š((X,Y)) 2
[((2, v))) < e (((a.a)) (see Theorem 1 in the arXiv version of [23
Lemmas 3.2 to 3.6 illustrate some of the ideas that will be of use in the case the causal graph is a polytree: in particular, Lemma 3.3 is noteworthy as it shows that we can test hypotheses concerning conditional distributions using differences between marginal anomaly scores, so long as we have the causal graph. However, they also entail interesting consequences for the case where the causal direction is not known. For example, let S(x) = 10, S(y) = 5 and significance level a = 0.01. For X + Y can only reject H. while the mechanism P(Y (X) possibly worked as expected. However, for Y + X, we would reject both hypotheses, that P(Y)) and that P(X YY) worked as expected with p-value e each. Following the working hypothesis that at most one mechanism was corrupted, we thus prefer X > Y. Note that the third alternative of causally independent generation of x and y can be rejected even level p S (- + + 10).
3.2 Anomalies in DAGs
Before restricting our attention to the case where the causal DAG a polytree, let us first consider the problem in full generality in DAGs. To infer for which variable the causal mechanism has been corrupted, we start with the hypothesis that all mechanisms worked as expected except for P(X, PAy): Hg: for the anomaly event (zi,..., Ix) all æ; with i * j have been drawn from P(X, PA, = pa.). We will return to marginal anomaly scores shortly, but first, define test statistics, we focus on conditional anomaly scores. We also need to make the assumption:
1. Continuity: all variables X; continuous with density w.r.t. the Lebesgue measure, and also all conditional distributions P(X,IPA, = pa,) have such a density.
Referring to Eq. 6 conditional scores with variable inputs X,, PAA, define random variables S(X; P.,). Continuity ensures that all conditional anomaly scores are distributed according to the density p(s) = e-x for 2 0, and entails a property that will be convenient for testing H/:- Lemma 3.7 (Conditional anomaly scores are independent). Subject to the continuity assumption, (S(), "((X,, (An)) are independent random variables.
5

---

Independence of conditional scores enables the definition of simple test statistic that is obtained by summing over them" together with a correction term. With Sam := Σit, (P.)) we define the joint anomaly score
S = Sum log
sum
1!
I=0
To understand Eq. 9 note that Sam no longer has the properties of an IT anomaly score: the sum of independent IT scores is likely to be large because it is not unlikely that the set contains at least one large term. The second term is therefore needed to 'recalibrate' the sum and is akin to a multiple testing correction. The following result states that this is quantitatively the right correction:
Lemma 3.8 (The joint score is an IT anomaly score). If H. holds, Eq. 9 is distributed according to the density p(s)
for s 2 O.
As direct result of the above lemmas, we have: Theorem 3.9 (p-value for joint anomaly event). Hg can be rejected for the observation (I1,..., Tnn
with p-value p = e SSum Σn-2 St
The theorem justifies choosing the index j with the maximal conditional anomaly score as the root cause, whenever follow the working hypothesis that only one mechanism is corrupted.
With our framework in place. we can return to our original goal: to show how RCA is possible, without the estimation of conditional probabilities, using only marginal anomaly scores. In order to do so, we restrict our attention to the case where the causal DAG is a polytree.
3.3 Anomalies in polytrees
Polytrees are DAGs where the underlying skeleton is a tree (see Fig. 2 in Appendix D). The key prop- erty of polytrees that we exploit is that the parents of any given variable are marginally independent. This allows us to replace conditional anomaly scores with bounds derived from marginal anomaly scores, following the ideas from the bivariate case. To this end, note that, as they are independent, we may use the same construction as we did in Eq. 9 to define a joint score over the parents of a given variable. For variable X,, with parents PA ...., PAY, and event pa;:
* 1- S(pa)))
Sjoine (pa;) = Σ S(na)) log
(10)
J=1
1=0
That this is indeed an IT score for joint event pa, follows from the same proof as for Lemma 3.8 For brevity, drop the subscript and simply write S(pa,) to mean the joint anomaly score of multivariate event pa,, as it will be clear from context whether we refer to a marginal score or a joint score. By using the joint score over the parents of each variable, we have effectively reduced the polytree case to the bivariate one with respect to each variable and its parents. In particular, we generalise score typicality:
Definition 3.10 (Score typicality). We say that observation (x. for X, PA, satisfies score typicality if
S(x; pa.) 2 [S(x:) - S(pa:)]+.
(11)
Subject to the continuity assumption, Lemma 3.4 apppppiis directly, in statement and proof, to score typicality as defined above, simply substituting Y for X, and X for PA, We can therefore say that for observation F; score typicality likely to hold approximately for a randomly chosen pa,, the sense given by Lemma 3.4
As result, we obtain the following bound on the joint statistics introduced in the previous subsection:
Theorem 3.11. (Bound on value for joint anomaly event using only marginal anomaly scores). With Smmm = Eitj [S(;;) - (pa:))+ it holds that subject to score typicality, H3 can be rejected with p-value
p
(12)
'Note that this corresponds to Fisher's method 41 for aggregating p-values, which also considers the sum of independent, log-transformed valuues.

---

We conclude that HJJ needs to be rejected whenever the anomaly score increases significantly along path of anomalies at any * j. This justifies inferring the index j that maximises the score difference (S(r - (paa)) 1 as the unique root cause (with the difference being [S(x;) - 0|+ = S(x,) ) for any node with no parents) because this yields the weakest bound Eq. [2 Motivated by these bounds, we propose the algorithm SMOOTH TR TRAVERSAI? which selects the node as the root cause that shows the strongest increase in anomaly score compared to its parents (as a heuristic we consider the score difference with the most anomalous parent of each node, see Algorithm bellow).. In the usual traversal approach [24] 25 [), a variable is identified as a root cause if it anomalous, none of its parents are, and it is linked to the target variable through path of anomalous variables. However, this requires the user to choose threshold above which a node is considered anomalous. SMOOTH TRAVERSAL avoids having to make any such arbitrary choice. We can prove that if the maximum score difference is large, then the node at which the difference is maximised is likely to be the root cause. To this end: for anomaly event (x1 -.l..
F.n) and anomaly score differences
6 (5(,,) S(pa,)
i=
define null hypothesis Mij for anomaly event (#1...., En) and j = argmax, 6;, Iy was drawn from P(X, PAj pay), i.e. the anomaly with the largest score difference with its parents is not the root cause.
Theorem 3.12 (Bound on p-value for anomaly with biggest jump not being the root cause). Subject to score rypicality, when there is a single root cause, Ho can be rejected for observation (Z1...., ), and maximum score difference Smax = max (81,...,,8 8,) with p-value
p S 1 (1 Smnx yn-1
(13)
The theorem follows from the fact that if the node maximising the score difference from its parent not the root cause, it implies that at least one conditional anomaly score, of the (n 1) non-root
causes, is at least mmax G
Algorithm 1 (Smooth Traversal) Returns the variable with the largest positive score difference its highest scoring parent
Require: Scores ", causal DAG G of variables XI...., Xn Ensure: Variable X2 with the largest positive score difference to its highest- parent -00 2: Initialize candidate root cause + None
1: Initialize max min difference
3: for each ancestor X; of X,, in G do
4: Let PA; be the set of parents of X, in G
5: if PA, * 0 then
6:
max_pprret_score +
max S(x;)
EPE
7: else
8: max Boae_ttrett___ score + 0
9:
end if
10: score diiffeeeffeeeeeeee + |S(x;) - max parent_ score||
11: if score difference > max_min diifeedefeeeeeeeee then
12: max min defeedefffeeeeeeeee t- score_ dife__iifeeeece
madidate_rrot_____ couse < X; 14: end if
15:
end for 16: return candidate_root_cant
3.4 Shortlist of root causes via ordering anomaly scores
We have shown that a unique root cause can be identified using only marginal anomaly scores if the causal graph is known. We now drop the assumption that the causal graph is known and ask, can
'e thank Elke Kirschbaum for suggesting this name. 'The approach for deriving this p-vulue broadly resembles Tippett's 's method 42 for combining independent values.
7

---

we find the root cause given only the marginal anomaly scores ((z1),.... S(xn) We argue that the top-scoring anomalies constitute good shortlist for the root cause.
To see this, assume again that the (unknown) causal DAG for variables XI...., X, is a polytree as before, and for illustration, first consider particular causal path through the graph,
X
X
X
If we 'coarsen' the graph, marginalising out all the intermediate variables between X, and X so that we collapse the whole path into a single edge X,, - Xix, application of Lemma (.33 shows that we reject the hypothesis that the new 'coarse' mechanism P(X,, X,, Tie worked as expected at level p e-1S(22y)-8100 - However, note that the coarse mechanism for X implicitly encompasses each of the intermediate mechanisms that connected X;, to Xi, in the full graph. In other words, the anomaly zi, is unlikely to cause a much larger anomaly Ii, anywhere downstream, unless we allow that any of the intermediate mechanisms connecting them has been corrupted.
With this in mind, consider the full graph on ,I,..., and let æ be a permutation of (I...., such that
((*=(1)) 2 ((x(2)) 2 ... S(x)(n))-
We define the null hypothesis that the mechanisms worked as expected for all of the top-k scoring anomalies: Hoop- for anomaly event ..,, (((()) with S have been drawn from P(Xa()) ()) = (a)) Under the null hypothesis, we know that the score for (((()) must have been greater by at least A& : S(x)(1)) ((xx((++1) compared an ancestral node, despite its mechanism, and the mechanisms of any intermediates, working as expected. This is because whether or not any of the variables X (2): ..... xx())) are intermediates, their mechanisms, by assumption, worked as expected under the null. If any of the variables (x)++)) (x(()) are intermediates (or (1) has no ancestors). then its score increased by an even greater amount than Ag. Applying the same coarsening idea as above, and accounting for multiple testing, we therefore have:
Theorem 3.13. (Bound likelihood root cause not in top-k highest scoring anomalies). Subject to score typicality, where dmax denotes the maximum in-degree among all nodes in the graph, we can reject Hopp at level S n dmaxx C At,
These bounds motivate SCORE ORDERING which, given the marginal anomaly scores and an assumed upper bound on the in-degree of nodes in the causal graph, returns the set of top-k highest scoring anomalies with the guarantee that the root cause is among them with at least the desired confidence level 1 (see Algorithm 2. Note that one could just well specify desired number of variables, h; and SCORE ORDERING would then return a confidence level for each possible dmax so that the latter is not strict input requirement.
Algorithm 2 (Score Ordering) Returns the top-k scoring anomalies such that the root cause is among them with confidence at least 1
Require: Scores S(x1), )
S(x,), maximum in-degree dmax, confidence level 1 Ensure: A set L C (XI,..,, X,)
1: Let n be permutation of nI,...,n) such that S(xx(1)) S(xx(2)) 2 S(xx(n)
2: Initialize <- 0
3: for k = to n do
4: L <- LU (Xx())
5: i m then
6: return L
7:
end if
8: A S(I+(1)) ((zx(e+1))
9:
if n dmax e < a then
10: return L
11: end if
12:
end for

---

3.5 Beyond polytrees:
limitations of score ordering
Most of the theory developed in this section has depended on the assumption that the causal graph is a polytree. While this assumption appears in causal literature (e.g. [43] 44 45)), it is nonetheless a strong structural assumption. One of the strengths of both of the algorithms we propose, SMOOTH TRAVERSAL and SCORE ORDERING, is their simplicity and efficiency. SCORE ORDERING in particular demands very weak input requirements, and so the fact that it comes with any causal guarantees at all might be a surprise. As a minimum, this might justify its use as a 'first pass' heuristic in settings beyond those we study here. However, the question remains as to what extent we might expect our proposed algorithms to perform well in settings that do not meet the structural assumptions (we empirically assess this question in the next section). The key observation on which SCORE ORDERING depends in the proof of Theorem 3. 13 is that an anomaly H; is unlikely to cause much larger anomaly downstream. Li et al. [46] describe a condition under which the sc-sc of an effect X, can be larger than the 2² -soore of the root cause X, in a DAG with linear structural equations. Although our results refer to IT scores rather than =²-scores, their example nonetheless applies to us as the -score can be turned into an IT score by a monotonic recalibration. They show (see Corollary 2.1 in (46) that a sufficient condition for such case not to occur is that the DAG be polytree, and so their results do not contradict our own. However, in addition, we show in Appendix that in DAGs (with linear structural equations) more generally such cases are 'rare' in the sense that, under reasonable assumptions, it will hold for only a 'small' fraction of root causes. Despite, then, exceptions occurring, we believe our results nonetheless give confidence that SCORE ORDERING can be applied as a useful first heuristic even beyond polytrees.
4 Experiments
We evaluate SMOOTH TRAVERSAL and SCORE ORDERING against range of existing RCA methods, that can also operate with a single anomalous sample, on both synthetic and real world data. In particular we evaluate our methods against:
'Cholesky' [46] Assumes linear structural causal models, but does not require the causal graph. Makes use of the Cholesky decomposition of the covariance matrix of observed variables, exploiting an invariance property across permutations to identify the root cause.
'Traversal' 99 24 [25 Requires the causal graph. Identifies nodes which are anomalous, have no anomalous parents, and are linked to the target node via path of anomalous nodes root causes. Circa (47 Requires the causal graph. Fits a linear structural causal model to the data from the normal period and returns the node with the largest residual, given its parents, in the anomalous period. "Counterfactual" [23) Requires the structural causal model. Finds the counterfactual Shapley contribution of each node the anomalousness of the target event and outputs the node with the highest contribution.
We also evaluate against RCD [10] and E- --Diagnosis ||| in Appendix F. however, neither method operates in the single anomalous sample setting, and so we do not recommend direct comparison.
Synthetic data generation: full details are provided in Appendix FF In brief, to generate data, we sample a random DAG (not restricted a polytree) of n nodes. Structural equations are randomly assigned as simple feed-forward neural networks or as linear models of the parents and noise variables. In all experiments, 1000 observations are drawn according to the randomly assigned model in the nor- mal period. To produce an anomalous sample, root cause is chosen at random from among the nodes and a target node from among its descendants (including itself). An anomaly then injected at the root cause by adding x multiples of its standard deviation to its value, and propagated through the causal model. In each experiment, this process is repeated 100 times per data point. Unless otherwise stated, each algorithm is evaluated by its top-1 recall. With synthetic data, answer the following questions:
How does performance vary with anomaly strength? E 2.2. SMOOTH TRAVERSAL, Traversal, and Counterfactual, all of which outperform SCORE ORDERING. Circa and Cholesky perform considerably worse than the other approaches. apparently due to the assumption of linearity (see Fig. 5 in Appendix F.. The performance of SCORE ORDERING improves slightly as the anomaly strength increases, but performance is approximately constant for the other approaches. We extend this analysis in Appendix [22 to RCA and e-Diagnosis (Fig.) 4 using only linear SCMs (Fig. 5. and restricting the DAG to being polytree (Fig 6)
We display results for in Fig. [ We find that the strongest performing algorithms are

---

Pet. corvelyy stoutified RC
0.9
07
06-
SOORE ORDERING
SMOOTH TRAVERSAL
Traornal
Commteefort
05-
Chalasky
Circo
0.1
02
20
2.5
3.0
Anomaly strength (Nr. standard deviations)
Figure I: True positive rate for identifying the root cause against anomaly strength injected the root cause.
How do runtimes scale with increasing graph size? For fixed x 3, we measure the runtime of each algorithm for graphs with an increasing number of nodes, generated described above. We observe that (see Fig. in Appendix F). Traversal and SMOOTH TRAVERSAL are the fastest, with the remaining approaches having comparable average runtimes.
How does performance vary with increasing graph size? We generate causal models with E {20, 40, ... 100} and fixed anomaly strength of x 3 (see Fig. 7. While the performance of SMOOTH TRAVERSAL, Traversal and Counterfactual seems to remain constant, the performances of SCORE ORDERING, Cholesky, and Circa all begin to decrease the graph increases in size.
How robust are the methods misspecification of the causal graph? For the approaches that require a causal graph, we investigated how their performances varied as an increasing number of random edge addtions/removalssiverrrsl were introduced to the given graph (see Appendix F.4). For n = 50 and r = 3.0, we see SMOOTH TRAVERSAL, Traversal and Counterfactual are similarly robust, showing similar delays in performance, while the performance of Circa decayed more rapidly,
Real world data evaluation: We additionally performed a comprehensive evaluation with two 'real-world' datasets: the PetShop (27) dataset (see Appendix (F.6) and the Sock-shop 2 dataset 22 (see Appendix F.7). as well as 'semi-synthetic' datasets generated using the ProRCA package [48
(see Appendix F.8 In these evaluations, the picture can be quite different from that in the synthetic
data experiments. SCORE ORDERING often performs well across the datasets, but both of our
algorithms are variously outperformed by Cholesky, Circa Counterfactual in certain settings.
Code: httpp///ttttooooooooeee///////et
Conclusion
We have explored several directions in which the practical limitations of RCA can be addressed: first by avoiding estimation of conditional distributions in the setting that the causal graph known, and second by avoiding needing the causal graph at all, in the setting that it is a polytree. To do so, we lever- age information-
(IT) anomaly scores and prove general laws about their typical decay along causal paths without any parametric assumptions. Using our results, then propose novel algo- rithms: SMOOTH TRAVERSAL and SCORE ORDERING, give probabilistic guarantees for the cor- rectness of their outputs, and show they have competitive performance in both synthetic and real- world data despite their simplicity. To our knowledge. our work is the only which provides non- non-parametric guarantees for RCA with single anomalous point without requiring the full structural causal model.
Acknowledgments and Disclosure of Funding
We would like to thank Manuel Gomez-Rodrigne for fruitful discussions during different stages of this project. W. R. Orchard would like thank Peterhouse, Cambridge, and Cancer Research UK for their support for this work.
10

---

References
[1] S Wibisono, MT Anwar, Aji Supriyanto, and IHA Amin. Multivariate weather anomaly detection using dbscan clustering algorithm. In Journal of Physics: Conference Series, volume 1869, page 012077. IOP Publishing, 2021.
[2] Eric V Strobl and Thomas A Lasko. Identifying patient-specifie root causes with the het- eroscedastic noise model. Journal of Computational Science, 72:102099, 2023.
[3] Eric V Strobl. Counterfactual formulation of patient-specific root causes of disease. Journal of Biomedical Informatics, page 104585, 2024.
[4] Gian Antonio Susto, Matteo Terzi, and Alessandro Beghi. Anomaly detection approaches for semiconductor manufacturing. Procedia Manufacturing,
2017.
[5] Jellis Vanhoeyveld, David Martens, and Bruno Pecters. Value-added tax fraud detection with scalable anomaly detection techniques. Applied Soft Computing, 86: 86: 2020.
[6] Sanjiv Das, Richard Stanton, and Nancy Wallace. Algorithmic fairness. Annual Review of Financial Economics, 15:565-593, 2023.
[7] Dongjie Wang, Zhengzhang Chen, Jingchao Ni, Liang Tong, Zheng Wang, Yanjie Fu, and Haifeng Chen. Hierarchical graph neural networks for causal discovery and root cause localiza- tion. arXiv preprint arXiv:2302.01982 2023.
[8] Cheng-Ming Lin, Ching Chang, Yao Wang, Kuang-Da Wang, and Wen-Chih Peng. Root cause analysis in microservice using neural granger causal discovery. arXiv preprint arXiv:2402.01 140, 2024.
[9] Dewei Liu, Chuan He, Xin Peng Fan Lin, Chenxi Zhang, Shengfang Gong, Ziang Li, Jiayu Ou, and Zheshun Wu. Microhecl: high-efficient root cause localization in large-scale microservice systems. In Proceedings of the 43rd International Conference on Software Engineering: Software Engineering in Practice, ICSE-SEIP '21, page 338-347. IEEE Press, 2021.
[10] Azam Ikram, Sarthak Chakraborty, Subrata Mitra, Shiv Saini, Saurabh Bagchi, and Murat Kocaoglu. Root cause analysis of failures in microservices through causal discovery. Advances in Neural Information Processing Systems, 11311558-11700 2022.
[11] Huasong Shan, Yuan Chen, Haifeng Liu, Yunpeng Zhang, Xiao Xiao, Xiaofeng He, Min Li, and Wei Ding. e-diagnosis: Unsupervised and real-time diagnosis of small-window long-tail latency in large-scale microservice platforms. In The World Wide Web Conference, pages 3215-3222,
2019.
[12] Meng Ma, Jingmin Xu, Yuan Wang, Pengfei Chen, Zonghua Zhang, and Ping Wang. Automap: Diagnose your microservice-based web applications automatically. In Proceedings of The Web Conference 2020, pages 246-258, 2020.
[13] Douglas Hawkins. Identification of outliers, volume 11. Springer, 1980.
[14] Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey, ACM computing surveys (CSUR), 41(3):1-58, 2009.
[15] Charu C Aggarwal. An introduction to outlier analysis. Springer, 2017.
[16] Ane Blázquez- Garzquez-Garcia, lier/anomaly detection time series data. ACM Computing Surveys (CSUR), 54(3):1-33, 2021.
García, Angel Conde, Usue Mori, and Jose A Lozano. A review out-
[17] Leman Akoglu. Anomaly mining: Past, present and future. Proceedings of the 30th ACM International Conference Information & Knowledge Management, pages 1-2, 2021.
[18] Edwin M Knorr and Raymond T Ng. Finding intensional knowledge of distance-based outliers. In Vldb, volume 99, pages 211-222, 1999.

---

[19] Barbora Micenková, Raymond T Ng, Xuan-Hong Dang, and Ira Assent. Explaining outliers by subspace separability. 2013 IEEE 13th international conference on data mining, pages 518-527. IEFE, 2013.
[20] Ninghao Liu, Donghwa Shin, and Xia Hu. Contextual outlier interpretation. arXiv preprint arXiv:1711.10588 2017.
[21] Meghanath Macha and Leman Akoglu. Explaining anomalies in groups with characterizing subspace rules. Data Mining and Knowledge Discovery, 32:1444-1453 2018.
[22] Nikhil Gupta, Dhivya Eswaran, Neil Shah, Leman Akoglu, and Christos Faloutsos. Beyond outlier detection:
Lookout for pictorial explanation. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2018, Dublin, Ireland, September 10-14, 2018, Proceedings, Part 18, pages 122-138. Springer, 2019.
[23] Kailash Budhathoki, Lenon Minorics, Patrick Bloebaum, and Dominik Janzing. Causal structure- based root cause analysis of outliers. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 2357-2369. PMLR, 17-23 Jul 2022.
[24] Pengfei Chen, Yong Qi, Pengfei Zheng, and Di Hou. Causeinfer: Automatic and distributed performance diagnosis with hierarchical causality graph in large distributed systems. In IEEE INFOCOM 2014 IEEE Conference on Computer Communications, pages 1887-1895, 2014.
[25] JinJin Lin, Pengfei Chen, and Zibin Zheng. Microscope: Pinpoint performance issues with causal graphs in micro-service environments. In International Conference Service Oriented Computing, 2018
[26] Luan Pham, Huong Ha, and Hongyu Zhang. Root cause analysis for microservice system based on causal inference: How far are we? In Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering, ASE '24, page 706-715, New York, NY, USA, 2024. Association for Computing Machinery.
[27] Michaela Hardt, William Roy Orchard, Patrick Blöbaum, Elke Kirschbaum, and Shiva Ka- siviswanathan. The petshop dataset finding causes of performance issues across microservices. In Francesco Locatello and Vanessa Didelez, editors, Proceedings of the Third Conference on Causal Learning and Reasoning, volume 236 of Proceedings of Machine Learning Research, pages 957-978. PMLR, 01-03 Apr 2024.
[28] Yu Gan, Mingyu Liang, Sundar Dev. David Lo, and Christina Delimitrou. Sage: practical and scalable mI-driven performance debugging in microservices. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS '21, page 135-151, New York, NY, USA, 2021. Association for Computing Machinery.
[29] Azam Ikram. Sock-shop data. httpss//ithubbcom/aaaaaikanr hwt.a/aammmmddtteeemmmmmeess/soo data, 2023.
[30] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Barcinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9551 15511. Curran Associates, Inc., 2020.
[31] Nicola Gnecco, Nicolai Meinshausen, Jonas Peters, and Sebastian Engelke. Causal discovery in heavy-tailed models. The Annals of Statistics, 4953): 1778, 2021.
[32] Carlos Améndola. Benjamin Hollering, Seth Sullivant, and Ngoc Tran. Markov equivalence of max-linear Bayesian networks. In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Seirth-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 1746-1755. PMLR, 27-30 Jul 2021.
[33] J. Pearl. Causality. Cambridge University Press, 2000.
12

---

[34] Jonas Peters, Peter Bühlmann, and Nicolai Meinshausen. Causal inference by using invariant prediction: Identification and confidence intervals. Journal of the Royal Statistical Society Series B: Statistical Methodology, 78(5):947-1012, 10 2016.
[35] B. Schölkopf, F. Locatello, Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio. Toward causal representation learning. Proceedings of the IEEE, 109(5):612 634-644,, 2021.
[36] Akash Maharaj. Ritwik Sinha, David Arbour, Ian Waudby-Smith, Simon Z. Liu, Moumita Sinha, Raghavendra Addanki, Aaditya Ramdas, Manas Garg, and Viswanathan Swaminathan. Anytime-van -aaid confidence sequences in an enterprise a/b testing platform. In Companion Proceedings of the ACM Web Conference 2023, WWW '23 Companion, page 996-400, New York, NY, USA, 2023. Association for Computing Machinery.
[37] Stephen Bates, Emmanuel J. Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 2021.
[38] Patrik Hoyer, Dominik Janzing, Joris M Mooij. Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008
[39] Jonas Peters, Joris M. Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15(58):000-2055. 2014.
[40] Aram Ebtekar, Yuhao Wang, and Dominik Janzing, Toward universal laws of outlier propagation. In Proceedings of the Forty-First Conference on Uncertainty Artificial Intelligence, UAI '25. JMLR.org, 2025.
[41] R. A. Fisher. Statistical Methods for Research Workers. Oliver and Boyd, 1925.
[42] L. H. C. Tippett. The Methods of Statistics: An Introduction Mainly for Workers in the Biological Sciences. Williams and Norgate Ltd., London, UK, 1931.
[43] Daniele Tramontano, Anthea Monod, and Mathias Drton. Learning linear non-Gaussian polytree models. In James Cussens and Kun Zhang, editors, Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, volume 180 of Proceedings of Machine Learning Research, pages 1960-1969. PMLR, 01-05 Aug 2022.
[44] Martin E. Jakobsen, Rajen D. Shah, Peter Bühlmann, and Jonas Peters. Structure learning for directed trees. Journal of Machine Learning Research, 23(159): 2022.
[45] Davin Choo, Joy Qiping Yang, Amab Bhattacharyya, and Clément I. Canonne. Learning bounded-degree polytrees with known skeleton. In Claire Vernade and Daniel Hsu, editors, Proceedings of The 35th International Conference Algorithmic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 402-443. PMLR, 25-28 Feb 2024.
[46] Jinzhou Li, Benjamin B. Chu, lnes Scheller, Julien Gagneur, and Marloes H. Maathuis. Root cause discovery via permutations and cholesky decomposition, 2024.
[47] Mingjie Li, Zeyan Li, Kanglin Yin, Xiaohui Nie, Wenchi Zhang, Kaixin Sui, and Dan Pei. Causal inference-based root cause analysis for online service systems with intervention recognition. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3230-3240, 2022.
[48] Ahmed Dawoud and Shravan Talupula. Prorca: A causal python package for actionable root cause analysis in real-world business scenarios. arXiv preprini arXiv:2503.01475. 2025.
[49] Kun Zhang, Zhikun Wang, Jiji Zhang, and Bernhard Schölkopf. On estimation of functional causal models: general results and application to the post-nonlinear causal model. ACM Transactions on Intelligent Systems and Technology (TIST), 7(2): 1-22, 2015.
13

---

[50] Julius Von Kügelgen, Abdirisak Mohamed, and Sander Beckers. Backtracking counterfactuals. In Mihaela van der Schaar, Cheng Zhang, and Dominik Janzing, editors, Proceedings of the Second Conference on Causal Learning and Reasoning, volume 213 of Proceedings of Machine Learning Research, pages 177-196. PMIR, 11-14 Apr 2023.
[51] A. Balke and J. Pearl. Counterfactual probabilities: Computational methods, bounds, and applications. In R. Lopez D. Mantaras and D. Poole, editors, Uncertainty in Artifical Intelligence, volume 10. Morgan Kaufmann, San Matco, 1994.
[52] Dominik Janzing, Patrick Blöbaum, Atalanti A Mastakouri, Philipp M Faller, Lenon Minorics, and Kailash Budhathoki. Quantifying intrinsic causal contributions via structure preserving interventions. In International Conference on Artificial Intelligence and Statistics, pages 1188-21966 PMLR, 2024.
[53] Oliver lbe. Markov Processes for Stochastic Modelling. Elsevier, 2nd edition edition, 2013.
[54] Alexander G. Reisach, Myriam Tami, Christof Seiler, Antoine Chambaz, and Sehastian We- ichwald. A scale-invariant sorting criterion to find a causal order in additive noise models. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[55] J. D. Hunter. Matplotlib: A 2d graphics environment, Computing in Science & Engineering, 933):00-95 2007.
[56] Chenghao Liu, Wenzhuo Yang. Himanshu Mittal, Manpreet Singh, Doyen Sahoo, and Steven C. H. Hoi. Pyrea: A library for metric-based root cause analysis, 2023.
[57] Silvia Acid and Luis M. de Campos. Searching for bayesian network structures in the space of restricted acyclic partially directed graphs. J. Artif. Int. Res., 18(1):445-490, May 2003.
[58] Ioannis Tsamardinos, Laura E. Brown, and Constantin F. Aliferis. The max-min hill-climbing bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, Oct 2006.
[59] Elias Eulig, Atalanti A. Mastakouri, Patrick Blöbaum, Michaela Hardt, and Dominik Janzing. Toward falsifying causal graphs using permutation- based test. In Proceedings of the Thirty- Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence,
AAAI Press, 2025.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All the theoretical claims in the abstract and introduction are part of the main article.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Most of the limitations come from theoretical assumptions made to obtain the results. These limitations are discussed in the main article.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer:
[Yes]
Justification: Most of the article is given over to theoretical results and their proofs. We clearly state all assumptions, and proofs of every lemma and theorem in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We give a detailed description of the set-up for experiments performed. and point to 3rd party Python libraries where applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification: We provide a link to the complete code for reproducing our experimental results at the end of the article.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines for more details.
(https://nips.. (https://nips.cc/pubbiie hipppbiccuuddds/ooeeiiiiiiiiiiio
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines http:://nips.cc/ppuliccggg http://giiissSooeeeeuubiiiiioiio
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, as in answer questions and above.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In all figures where error bars are necessary and large enough to be visible, they are displayed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The work requires very modest compute resources, but details have been provided in the appendix nonetheless.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::///eurrrssscccuuu////iieee
Answer: [Yes]
Justification: Due to the paper being entirely theoretical, the paper adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There no broad societal impacts of the application of the ideas outlined in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No major risks posed by the paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The only assets used by the paper are public datasets. We cite all original papers and URL to access it alonside licensing information.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets. paperswithoode.cmmii licenses for some datasets. Their licensing guide can help determine the license of dataset.
has curated
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The only assets are code for running the experiments (to be released on acceptance the latest). This code is well documented. The paper otherwise released no new assets.
Justification:
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The paper does not involve the use nor development of LLMs in any way.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httpss//eeeriissscccccceeeeeeeer for what should or should not be described.
21

---

A Relationship to contribution analysis
We first sketch the causal framework adopted by Budhathoki et al. 133. In particular, they assume that the causal relationships between X1, X1..... Xn are described by Structural Causal Model (SCM). In an SCM, each variable X; is function fi of its parents PA, in the causal graph, and an unobserved noise term N₁:
X, = f((A,,,
(14)
where the noise variables Ni...., N₂ are jointly independent 33 In addition, it assumed that the SCM is invertible [49]. That is, the noise value nj of N, can be recovered from the value xy of its corresponding observed variable X, and the values pa, of its parents.
As in our case, the value T,, is flagged as an anomaly, and we wish to identify its root cause from among the variables (X1,..., Xn). Treating (without loss of generality) Xn as a sink node in the causal DAG, iterative application of Eq. results in the representation
(15) in which the structural information is implicit in the function F. By Eq. 1. we therefore have that Vn = F(n1....... .7p) where (RI...., n2,) := n denote the corresponding values of the noise variables for sample (II...., TIn). This representation makes clear that node X;'s contribution to the anomaly In is ultimately attributable to the contribution of its noise term 23 50)
X, = F(NI........ N,),
If you consider our presentation of RCA, wherein we attribute the anomaly to one of the causal mechanisms being corrupted, the characterisation in terms of noise terms may appear quite different. However, we can connect the two perspectives by noting that one can think of each value n, as randomly switching between deterministic mechanisms (:(:.))) so-called response functions [51] If a noise term is "corrupted" and takes unusual value nij, the corresponding mechanism generating Ty from its parents pa, will be unusual as well. The goal of finding which causal mechanism did not work as expected, then is common between the two perspectives. The intuition behind the approach of Budhathoki et al. is that if for the root cause X, the unusual value of its noise term n, were replaced by "normal" one, then In would change to a non-anomaly with high probability. This gives the basis for defining how much each variable contributed to the observed anomaly. We explain how this is formalised next.
A.1 Contribution analysis
To compute the contribution of each noise N; to the anomaly In. Budhathoki et al. 2 measure how replacing the observed value nu (originating from a potentially corrupted mechanism) with a random "normal" value, sampled from its regular distribution P(N.), changes the likelihood of the anomaly event, F- = (r(X,) 2 T (..)). Intuitively, this shows us the extent to which n. was responsible for the extremeness of Zn.-
Note, however, that the influence of the value n4 on the likelihood of the anomaly event will also depend on the values of the other noise variables. In order to assess the contribution of n, we therefore also need to consider how it depends on the context, i.e. how changes depending on which other noise variables we similarly replace with random "normal" values. To formalise this, for any subset of the index set, S S U := (1.....,o n). first note that the probability of the anomaly event when all nodes in S are set to their observed value and all the nodes in S u \ S are randomised is P(E [ = ns). Now the contribution of node g given the context S is defined as
C(iS) = log Ns = ns. N, ny)
(16)
P(F = ns)
To give a "fair" attribution among the noise variables, the authors adopt Shapley values. Let II U > 24 be the set of all possible permutations of the nodes and E II be any permutation. One then defines the contribution of node j given permutation as C* (j) = (*)))= where fa3f denotes the set of nodes that appear before j with respect to n, iee., [ = (i ei u 7(1) < x.)). We easily see that for each permutation n, S(.,) decomposes into the contributions of each node,
"Note the difference in the definition of C(((S) compared to 23 In our case S is the set for which N₂ = while in (3 Nuss
nay.s.
22

---

i.e., S(x,) = [ee(t.....)) (²)) The Shapley contribution of node is then given by averaging over all the possible permutations in II:
Sh ( = n!
Σ C WEl
(17)
This approach therefore provides full quantitative contribution analysis of root causes. However, suffers from some practical issues. Firstly, the Shapley contribution a node is expensive to compute 23 More fundamentally, however, for most permutations the contributions C* rely on knowing the structural equations (14.. As the SCM cannot generally be inferred even with interventional data, this is serious bottleneck for the application of this approach. As the approaches we propose in this paper do not depend on knowing the structural equations (or even the causal graph in the case of SCORE ORDERING), explain next how we can nonetheless recast results in terms of the contribution approach just presented.
A.2
Interventional vs counterfactual RCA
The key result we will need is that so long as æ is topological ordering of the nodes in the causal graph, then all contributions ("(j) do not require knowing the SCM. To illustrate this, first consider the bivariate case X + Y with structural equations X == Nx and Y == J(X, Ny-). and anomaly sample (xr y). determine the contribution of Ny to the anomaly, we consider randomising Ny and fixing Nx = nx v. This generates Y according to the observational distribution P(Y Ix),
so its estimation does not require knowledge the SCM. On the other hand, randomising Nx and fixing Ny ny cannot be resolved into any observational term (see also Section 5 in [52]
The following result generalises this insight: Proposition A.1. Whenever is topological order of the causal DAG, i.e., there are no arrows X; + for (i) > T(j), all contributions C* (j) can be computed from observational conditional distributions.
This will allow connect our approach to that of Budhathoki al. (33 in the following sense: if our goal is to simply identify a single root cause, then as long as it is "dominating" in the sense that has the largest contribution of any variable regardless of the order chosen, Proposition A. says can identify without knowing the SCM.
It will prove instructive to generalise the notion of the contribution of single node in 16 to the contribution of a set C 2 \ (S of nodes, given the context S, i.e.,
C(R(S) = log P = DR. Ns
(18)
NS =NN=MM =
This notion becomes rather intuitive after observing that it is given by the sum of the contributions of all the elements in R when they are one by one added to the context S:
Lemma A.2. For any set R C u \ S, it holds that C(R(S) == C(isS) + E C(iSS U
..-....,j+..)) with R (j (j.....,jkk j.k.
Next, the following result shows that a set of nodes are unlikely to obtain a high contribution when the noise values are randomly drawn from their usual distributions, i.e., have the following proposition:
Proposition A.3. Whenever all noise variable in some R sampled from P(NR), it holds that P (C(R)S) a) e
Note that the proposition allows that the variables N, not in R. are drawn from different distribution. Thus, Proposition states that it is unlikely that set that only contains non-corrupted nodes has high contribution.
Next, will show how our main results can be recast in terms of bounds contributions, rather than on values..
"This can be checked by an SCM with two binaries where y := X e Ny. with unbiased Ny, which induces the same distribution as the SCM Y == Ny, where X and Y are disconnected and thus X has a contribution of zero.
23

---

A.3 Bounds on contributions
Consider, for illustration, the setting discussed in subsection 3.1 wherein the causal DAG is X + Y. we observe (z. y) with anomaly scores S(x), S(y), and we wish to find the root cause of anomaly Under the same assumptions as stated there we have the following proposition:
Proposition A.4. Subject to score rypicality, the contributions of y and x on the anomaly y satisfy:
C(a) & ((x)) and Cly ( 2 (S(g)) - S(x)1+
Proof. Proposition A. permits rewriting contributions in terms of observational probabilities, so that, together with score typicality, we have:
Cly æ) == log P(r(Y) 2 ((y) Y y,x= x)
P(T(Y) 2 T()) X = x)
log P(r(Y) T()) X x)
S(y x) 2 ( - S(x))++
and using C(x) + Cly x) = Sly) we obtain the bound for C(x)).
We can now further interpret the conclusions drawn in subsection 3.1 in terms of contributions. For example, suppose we have Syy > S(x). In the case that + Y. Proposition A.4 says that must have a large contribution to the anomaly, while x must have smaller one. We would therefore favour y as the root cause. Alternatively, if S(x) >> S(y), then we cannot conclude that y has a large contribution. but would reject the hypothesis that the mechanism generating worked as normal (from Lemma 3.2). and its contribution may be large. Under the working hypothesis that there is only single root cause, we would favour Following the extensions from the bivariate case in subsections 3.2 and 3.3 we can similarly recast the results in terms of contributions as above. Naturally, this does not alter any of the conclusions, but rather demonstrates that our results do not depend strictly on our adopted formalisation of the RCA problem in terms of CBNs, but additionally admits interpretation in terms of contributions.
B Sample complexity of information-theorrtii anomaly score estimation
To reliably tell whether the IT anomaly score of one anomaly exceeds that of another, we need to estimate each score up to an error of at least half their difference. We investigate how many samples are required to estimate the scores
())) up to an error level 5:
Lemma B.1. If we use at least
Smar
2n
k
log
(19)
82
samples from the 'normal' period, the score estimates $(z1).... ... S(xx) using the estimator in Equation satisfy (8(x)) - S(xa) < for all E (1,...,m) n. with probability at least 1 -a.
and estimate P. = 1/ E 1T(x;)) 2 r(xx)} so that S(x,) = -log Pt and S(z;) = 1o-log log P. as in Equations and (5) respectively. 1$(xz) S(x:)) < is equivalent to.
Proof. Let := =et(x==((r(.)+ 2 T (xx)))
log p. - -oogpp < 8
(20)
P
Rearranging, we have (e(e-t 8__ -11 1) 5 > 0, we have
p. - ps < pi (c 1), and noting e 1 -5 for all
1/: pil < G == (e 1)p;,
(21)
so that when 5 is small we have 6 R 5p;. We can then the multiplicative form of the Chernoff bound for 0 < < to say,
(- 82p.k
P(Le - pal 2 8p:) < 2exp
(-3 3
(22)
24

---

Noting that min, p; min, e S(m,) = max; 5(z.) = e -max and applying the union bound,
8e Samx k
Ulli- - pil 2 Spi}
eneep
(23)
so that finally,
8 8me-mmexk"
30
2n
exexp
<a
h:
log
82
a
C Proofs
C.1
Proof of Lemma 3.4
Since we assume that S(X) is continuous variable with density with respect to the Lebesgue measure, it follows from the properties of IT scores that it is distributed according to the density p(S(X)= s) e for 2 0. Accordingly. the conditional distribution of S(X), given S(X) [sx, S(y) has the density p(S(X)=
S(X) E S()))) e =<>>/(e"x e eeS())). We want to
compare averages of the expressions
P(S(Y) 2 (()) s) versus -1)
over the interval [sx, S(v)]. Averaging the difference of the two expressions with respect to the above-mentioned density yields
S(n) (P(S(Y) 2 (())S((X) =) --19(0)-ol+)) p(s S(y) S(X) 2 )ds
P(S(V) 2 S(v)(S()) 2 S(X)= 2 2x) - (S(D)
36x 6 e=-5(v) 5(v) e
e- S(y) ds
S(v)
S(y) e ((y)
E S(y)
ds
- S(w) (1 - Sly) + 8x) S 0.
-- - S(y)
- -Syl)
ix
The first inequality holds because P(B) A) S P(B) ((B))((A) (AA) for any two events A, B and the second because we have assumed S S(y) 1.
Applying Markov's inequality, we therefore have
(x|s(X)e(sxx,5)) ((y))))())) [P(S(Y) 2 S S(X) 2 c. - I l/c.
(24)
As X may in general be multivariate, S will not in general be injective, and so we cannot substitute conditioning on a particular value of the score for conditioning on the associated x, which is required to give bound on the conditional score. As such. note that
P(S(Y) Z Sty) ((X) 5) / P(S(Y) 2 S(y) xx= = 2) p(a ((X) s) dx,
so that applying Markov's inequality for any given 8, Px s(x) (P))(Y) 2 S(v) X 2 c- P(S(Y) 2 S(y) | 5())) I 1/c. As the inequality holds for all we can take the average of the LHS with respect to
(25)
p(S(X== = s S(X) E [sx, (yy)) to say,
Pxis(x) (Sw) (P(S(Y) 2 S(y) |X) c P(S(Y) 2 S(y) S(X)) s 1/c.
(26)
Applying the union bound to the events in equations 24 and 26 the joint event
P(S(Y) 2 5(y) 5(X)) < c. Slt -
and
P(S(Y) S(y) x) S c- P(S(Y) 2 S(y) S(X))
occurs with probability at least 2/c, and such case the following inequality holds:
P(S(Y) 2 S(y) X =x) < c e -S()))((s))-
-1S())
(27)
Finally, noting we can exchange S(Y) 2 S(y) for r(Y) 2 r(y) due to the properties of IT scores, and taking the negative logarithm of both sides, for sampled at random according to P(X = x S(X) [sx, S(y))).
S(y () 2 (S(y) S(x)1+ - 2 loge,
(28)
holds with probability at least 1 - 2/c, desired.
25

---

C.2 Proof of Lemma
3.5
P(T(M) 2 x = 2 ((y) X 2) = P(S(Y) 2 S ((X) = S(x)
P(S(Y) 2 5(v) e
S P(((()) S(U) S(X) 2 S(x)) & P(S(X)= S(z)) S(x)
Where the first equality follows from the definition IT scores and the second from injectivity. The first inequality follows from monotonicity, and the second because P(B AA) < P(B)/P(A) for any two events A, B. The final cquality again follows from the definition of IT scores. Taking the negative logarithm of both sides, and remembering that anomaly scores non-negative, prove the lemma.
C.3 Proof of Lemma 3.7
Assume without loss of generality that XI...., X, is a topological ordering of the DAG. Then s(X, = ((X,(PA)) holds due to the local Markov condition. Since = paz) has density e for all pa,, also S(X;|X; Tı, Xi-1 24-1) has density for all 21,...,;;-1 Hence, S(X; PA.) is independent of Xi...., X,-1-
C.4 Proof of Lemma
From Lemma 3.7 and the properties of IT scores, if HJ holds then S(X; PA.) for i * are independent, standard Exponential random variables. The sum of n independent, standard Exponential random variables is Erlang distributed [33 with CDF
F(x) = -
and such, Saum is Erlang distributed. By the probability integral transform U F (S is uniformly distributed on [0, 1]. and so by symmetry, so is 1 U. Again by the probability interral transform, llogl1 U) is standard Exponential, so finally noting that S log(11 - (Saum))
we have the result.
C.5 Proof of Theorem 3.9
The theorem is a direct result of Lemma 3.7 and Lemma 3.8
C.6 Proof of Theorem 3.11
Saum
Σ S(x;(pa.) N iラj
Σ (S(x:))S(ppa) Seum, 151
(29)
where the inequality follows from score typicality of event (æ1,..., In), and Saum and Samm are the realisations of Saum and Saum. respectively. The theorem then follows directly from Theorem 3.9 with Samn in place of Saum-
C.7 Proof of Theorem 3.12
From Lemma 3.7 we have that the conditional anomaly score for the anomaly with the maximum score gap must be at least 6max- From Lemma 3.4, and the properties of IT anomaly scores, the conditional anomaly scores are independent and each distributed according to density p(s) = e e Under Hm assume without loss of generality that z,, corresponds to the true root cause. Then the remaining (n 1) conditional scores are i...d. Exp(1), and
P(S(X; PA.) d for all i < n) (P(S(X, PA.) 6)) = --))===))0000 -1---55p
Therefore, the probability of observing at least one conditional anomaly score of at least δmax among the (n - 1) non-root causes 1 (1 -mmmmx e--max)n-1 n- This probability upper bounds the probability of observing at least one score gap of 6max greater as gaps lower bound conditional scores.
26

---

C.8 Proof of Theorem 3.13
The proof of the theorem is already almost complete, following the argument in the main text. As noted there, Ho implics that along the causal path the score =1) must be higher than an ancestral node by at least Ag. Lemma 3.3 along with the coarsening argument, implies that, individually, the hypothesis that the mechanism generating I worked as expected, where S(x) is higher than the score of ancestral node by As: can be rejected at level p Σ e e-A,, Therefore, along the causal path, the probability that the score of any of the (maximum of) n nodes exceeds an ancestral node by A is at most e- Ax, applying the union bound. However, note that need to reapply this argument for each of the chains incident on X=(1) in the graph. The number of incident chains most dmax, and again applying the union bound, we arrive at the final bound given in the theorem.
C.9 Proof of Proposition A.1
With the event E' as in Eq. 3 and (T) ((G) we have
P(E FIEINRRjUR u() PISSUU)) log
P(E Xicju())
C (j) = log
P(E[Nasi DT<s))
P(E Xx<s))
Po X Ui1 = Xz<jU()
log
(30)
PX nej Xx<i))
(i) and (ii) are seen as follows:
P(E = P(E P(E)do(Xx)).
(31)
The first equality in Eq. 31 follows from X, I Xz NN and because X is a function of Nz. The second one follows because conditioning on all ancestors blocks all backdoor paths. Note that since is a topological ordering of the nodes, all < j are ancestors of j.
C.10 Proof of Lemma A.2
Denote (88) P Ns ns) then have that
C(R = log ( U R) log (S)
(log (S U R) log q R \ (ixt)) +...
(log U R \ {j+}) - log (SUR (kk, ....
k
+ (log (SUU {f1 - log = C(1(S) + Σ c(isS (o......--.).
C.11 Proof of Proposition A.3
By definition, we have that
C(RIS) = log PR = nR. DR. Ns = ns)
Ps ns)
and we use P(E(ns) instead of P(E|Ns ns) when it is clear from the context.
Further, C(RSS) is actually a function of nn and ng. For fixed ng, define the set B (nn (C()))) a). It can equivalently be described by
B = [n log P(E nR ng) 2 a) (P(E ns) 2 P(E[ns) ed).
P(F
We thus have
P(E E Bs) 2 P(Elns).c ea
Hence,
P(E,nR Blns)
> P(Enns) ea.
P(ng E Blns)
27

---

Using
P(Enns) 2 P(E, nn Blns)
obtain
P(nR E Blns) Se
D
Visualising polytrees
X1
X1
X2
X3
X3
X4
X4
(a) General DAG
(b) Polytree
Figure 2: (a) A general DAG may contain undirected cycles, as between X1 -1xx,, X2 X3 - X1- (b) A
polytree cannot contain undirected cycles could not have edge between X1 and X2 without first removing another.
E Is increase of scores along causal pathways rare?
Li al. [46] describe a condition under which the x² -core of the effect X, can be larger than the 2²-score from the cause X; in DAG with linear struetural equations. Their Theorem 2.1 states that this happens (in the limit of large perturbations, see the details further below) if and only if the variances of o3 of X., X, satisfy
< <5
(32)
where az= denotes the structural coefficient for the effect from X, to X, (which consists of the sum over the product of all direct influences along the paths from to j). Although our results refer to IT scores instead of =--scosss it is at the same time example for increasing IT scores since the 2²-score can be turned into an score by a monotonic recalibration. It is therefore understand if we expect SCORE ORDERING
important that understand this result if we to be applicable in cases beyond polytrees. For an intuitive understanding we should first note that (32) describes the regime of strong negative confounding. This is because unconfounded causal influence X, = Oj-aj X; + Ej with independent error term E, results in of a o + Var Eş). We are therefore in the regime where the noise is strongly negatively correlated with the cause that decreases the variance instead of increasing it.
Let us now discuss whether this phenomenon is rare not when X, and X3 variables in larger network (note that the following working is strongly inspired by [46)). To this end let XI...., ".....,,,, X, be causally ordered with structural equations
X = AX +
(33)
where is a strictly lower triangular matrix and N is the vector of independent noise variables. To simplify notation, let all variables have zero mean.
The covariance matrix Exx can be derived by well-known algebra:
Σxx (T A) ([]----)- A)-T,
where ENN denotes the covariance matrix of the noise, which is diagonal by assumption. Defining
L : (I - 1/2 N -N
we obtain the unique Cholesky decomposition of Σxx since Exx I.I.T. where is lower diagonal
(with non-zero diagonal by construction if assume non-zero noise variance). The matrix L has
28

---

interesting interpretations:
(i) L generates the observations from independent noise variables as sources, formally X = LN,
where Ñ = 2N N is the standardized version of the noise from the original structural equation (33)
(ii The squared row sums of L thus show the variance of the observed variables, that is. Σ, 1 of. Henceforth, will assume it to be 1 without loss of generality.
(iii) The ith column of L describes how shifting the noise ñu to n; + 1 changes the observations Ln is changed to x + Les, where e; denotes the ith canonical basis
x, that is, the observation vector.
Since all the X, are standardized and centered, their 2² score is simply their squared value 2/. If we shift the noise ñ, by a large value, the =--scores x² of the root cause X; versus the score 2² of the effect Xj satisfies the ratio / L2, in the limit of infinitely strong perturbation. The question of whether scores of effects are typically smaller than scores of their root causes now boils down to the following question: Given a lower triangular matrix L whose row vectors have norm 1. Is L "typically" smaller than 2 We will discuss this question for the assumption that ni is large and that p := min; { (L2,) is much larger than 1/n. This assumption simply formalizes the idea that no X, is close to be deterministic function of its ancestors. It may seem strong, but we could easily extend the below discussion to the case where only most of the variables satisfy this condition We conclude:
S1 p. 15K3
Σ
Hence, the number Is of i with i < j for which L3, < Lij is at most (1 - p)/p. Using p >> 1/n we conclude k & n. Thus, only for a small fraction k/n of root causes i, the score Lł of the root cause is smaller than the score Li, of the downstream effect j. In this sense, we may consider effects with larger score than the root cause as rare phenomenon, even for fixed causal structural equations, not only as a statistical statement over multiple randomly generated structures.
F Experimental details and further experiments
F1 Experimental details
To run Circa and Counterfactual, we used the implementations available in [27 using default parameters. We wrote our own implementation of Traversal (with anomaly score threshold of 3), and our own algorithms, SMOOTH TRAVERSAL AND SCORE ORDERING. The code for Cholesky is available at [46), however, there are in fact three different algorithms. For all experiments involving real-world data (see subsection [6 beloww we applied their "main" algorithm, using default parameters. For the synthetic experiments, we had to opt for the "highdim" version as the alternatives had already become prohibitively slow for the graph sizes considered. To generate an SCM for the experiments in Section. (see Fig. D. we first uniformly sample between 10 and 20 root nodes (20% to 40% of the total nodes of the graph) and uniformly assign to each either standard Gaussian, uniform, or mixture of Gaussians as its noise distribution. As a second step, we recursively sample non-root nodes. Non-root nodes need not be sink nodes. The number of parent nodes that each non-root node is conditioned on is randomly chosen following a distribution that assigns a lower probability to higher number of parents. In total, the causal graph is composed of 50 nodes. The parametric forms of the structural equations are randomly assigned to be either a simple ferr-fd neural network with a probability of 0.8 (to account for non-linear models) and linear model. The feed-forward neural network has three layers (input layer, hidden layer, and output layer) where the hidden layer has a number of nodes chosen randomly between and 100. All the parameters of the neural network are sampled from a uniform distribution between -5 and 5. For the linear model, we sample the coefficients of the linear model from uniform distribution between -1 and 1 and set the intercept to O. In both cases, we use additive Gaussian noise as the relation between the noise and the variables.
"oote that simulated data can easily violate this assumption since many simulation schemes result in artifacts where variables that are late in the causal order can be almost perfectly reconstructed from others, phenomenon called It2 sortability in (54)
29

---

To generate data for the non -onaaooaaouus regime, we sample the noise of each of the variables and propagate the noise forward using the previously sampled structural equations. As mentioned in the main text, to produce anomalous data, we choose root cause at random from the list of all nodes and a target node from the set of its descendants (including itself). Then we sample the noise of all variables and modify the noise of the root cause by adding r-times standard deviations (of its marginal distribution), where I [2,2.1, 2.2,.. ...,.,,,... 3). and propagate the modified noise through the SCM to obtain realisation of each variable. We repeat this process 100 times for each value added to the standard deviation and consider the algorithm successful if its result coincides with the chosen root cause.
Computing Infrastructure. All the experiments were run on a MacBook Pro with 16GB of memory with an Apple MI processor.
Figure 3: Runtimes of the algorithms for the experiment in Fig. D that is 50 nodes (left), an SCM with 100 nodes (center) and one with Ik nodes (right) (refer to the generation process above). The boxplots are produced using the default implementation in Matplotlib [55]. Note the log scale in the vertical axis.
F.2 Further experiments varying root cause anomaly strength
Methods which require multiple samples from the anomalous regime Most RCA approaches
require multiple samples from the anomalous regime. For completeness, we extended the evaluation in Figure Ito to include two such methods: RCD (29) and e-Diagnosis [I]], as neither require the causal graph (see Figure 4). For both methods we made use of the implementations available in the PyRCA library [56) using default parameters. While all other methods were provided with only single sample from the anomalous regime, both RCD and e-Diagnosis were provided with 100, and so we believe that direct comparison is not appropriate. The experiment was otherwise identical to that described above Appendix FF Nonetheless, we see that while RCD has very strong performance, with top-1 recall close to one at all anomaly strengths, e-Diagnosis is the opposite, with a recall close zero for all anomaly strengths. is worth noting that the original authors of the RCD method [TO] show in their supplemental material that performance is very poor in the low-sample regime (<100 anomalous samples, see Figure therein). We conclude that RCD could preferable in scenarios where one has access to many samples in the anomalous period, but that in the low-sample regime SCORE ORDERING is preferable.
How do the algorithms perform when the structural causal model is linear? To test whether the performance of Circa and Cholesky in Fig. was poor compared to the other algorithms due to the assumption of linearity, above, with the only change being that now all structural equations were sampled to be linear. Indeed, Fig. 5 showws that Circa now becomes one of the best performing algorithms, alongside SMOOTH TRAVERSAR Traversal, and Counterfactual. Similarly, although Cholesky remains below the top performers, its performance notably improved at all anomaly strengths, even now outperforming SCORE ORDERING.
reproduced the experiment as detailed in Section 4 and Appendix [F]
How do the algorithms perform when the causal graph a polytree? all synthetic exper- iments, we placed no restrictions on the structure of the causal graph other than that it be DAG. Our main theorems are stated, however, for polytrees. We therefore repeated the experiments from Figure with with the single change constraining the simulated causal graphs to be polytrees (see F) Unsurprisingly, methods which do not make use of the causal graph have unchanged performance, and and those that do are either unchanged or show improvement, including SMOOTH TRAVERSAL.
30

---

Theennl
Cholesky
Pet. corvetly identifted RC
TRAVERSAL
Comttefuctua
red
Anomaly strength (Nr. standard deviations)
Figure 4: True positive for identifying the root cause against anomaly strength injected at the root cause, including RCD and e-Diagnosis. Note that both RCD and e-Diagnosis are given 100 samples from the anomalous period, while all other methods are given only one.
1.0
Pot. correctly identified RC
0.8-
0.6
0.-
0.2
SCORE ORDERING
SMOOTH TRAVERSAL
Traversul
Counterfactul
Cholesky
Circa
0.01
2.0
2.2
24
2.6
28
3.0
Anomaly strength (Nr. standard deviations)
Figure 5: True positive rate for identifying the root cause against anomaly strength injected at the root cause, when all structural equations are linear.
Interestingly, Cirea shows marked improvement in performance despite not depending the polytree assumption.
F33
Further experiments by varying the number of nodes in the graph
We also run experiments by fixing the number of standard deviations added (x in Section. 4 to 3 and varying the number of nodes in the SCM. Here, have chosen the numbers (20, 40, 60, 80, 100). We observe in Fig. (ig.77tte that the performance for Traversal, SMOOTH TRAVERSAL. and Counterfactual does not change much for different graph sizes, whereas the performance of SCORE ORDERING, Cholesky and Circa decreases slightly for larger graph sizes.
F.4 How does performance change when the given causal graph is misspecified
To mimic the scenario where one has access to an imperfect causal graph, we investigate how robust the performance each the algorithms (which require causal graph) its misspecification (8) The data were generated described the beginning of Appendix F but with a fixed anomaly
31

---

Pct. correctly identified RC
0.6
ORDERING
Counterfactual
Traversal
Circa
Cholesky
SMOOTH TRAVERSAL
epsilon diegnusis
0.0
2.0
2.2
2.4
2.6
2.8
3.0
Anomaly strength (Nr. standard deviations)
Figure 6: True positive rate for identifying the root cause against anomaly strength injected at the root cause, when all causal graphs are polytrees. Note that RCD and e-Diagnosis are given 100 samples from the anomalous period, while all other algorithms are given only one.
1.0
Pot. correctly identiffed RC
0.9
0.8
0.7
SCORE ORDERING
SMOOTH TRAVERSAL
Thuversol
Counterfartual
0.6-
Cholesky
Ciren
0.5
0.4
0.3
30
Number nodes
Figure 7:
True positive rate of the compared algorithms in identifying the root cause with increasing numbers of nodes.
strength of 3.0, all structural equations linear, and the graph provided to each algorithm randomly altered to introduce mismatches with the true causal graph.
Starting from the sampled, true causal graph, random edge additions, removals and reversals were introduced according to a desired target Structural Hamming Distance [57 58 from the true graph. To control for the density of the graph, equal number of edges are randomly added as removed. In particular, for true causal graph G = (V, E). the total number of edges added and removed is sampled (SHD(G, Gatt) [E,, edges flipped пiipp = SHD 2 Radd/rem.- Of the edges in G. Radd//rnm /rem are randomly selected for removal, and an equal number of 'missing' edges selected for addition. Of the remaining 'un-removed" edges in G. nalp are reversed. If the resulting graph not a DAG, the whole process is repeated until is. The procedure for generating randomly misspecified graph given ground truth matches the "edge domain expert" procedure described in [59].
uniformly at random from Faddd/rem
with the number of
We chose to sample all linear structural equations the relationship between top-1 recall and SHD was the same as when sampling non-linear structural equations for SMOOTH TRAVERSAL, Traversal and Counterfactual, but was more noteworthy for Circa. The reason being that the performance for
32

---

Circa is already so low for non- non-linear structural equations, that a considerable drop in performance was not easily perceptible.
We observe that all four evaluated algorithms show a considerable drop performance as the SHI) of the given graph from the true causal graph increased, with the most pronounced drop occurring for Circa. However, even when half of all edges are removed//lipped or added elsewhere in the graph (SHD/ || 1). SMOOTH TRAVERSAL, Traversal and Counterfactual still achieve top-1 recall of approximately 0.6 to 0.7, showing that all three algorithms are relatively robust to graph misspecification.
0.9
Top-1 recall
0.8
0.7
0.6
0.5
Thaverad
Circa
SMOOTH TRAVERSAL
Commerfaatuul
0.4
0.0
0.2
0.4
0.6
0.8
1.0
SHD (number of edges)
Figure 8: Top-1 I recall for identifying the root cause using a graph with an increasing SHD (average per edge) from the true causal graph.
F,5 How do the algorithms compare in terms of their practicality?
is important to keep in mind when interpreting the performances of each of the algorithms their different input requirements. Counterfactual either needs to provided the SCM must attempt to learn it from data. Traversal, Circa and SMOOTH TRAVERSAL require the causal graph as input but with differing assumptions on its structure. Traversal makes no assumptions, Circa assumes the SCM is linear and attempts to learn it from data, given the graph, and SMOOTH TRAVERSAL has guarantees only for the case the graph a polytree (though may be applied even if this assumption is not met). Traversal, however, requires an additional tuning parameter: the anomaly score threshold, while SMOOTH TRAVERSAL does not have any such free parameter. Both SCORE ORDERING and Cholesky do not even require the causal graph, however, Cholesky assumes the underlying SCM is linear. synthetic data experiments, SCORE ORDERING consistently outperformed Cholesky other than when the SCM was restricted to be linear (see Fig. abovve) Cholesky also scales more poorly in terms of run- cun-time (see Fig. 3 due to the need to estimate the covariance matrix. comparison, SCORE ORDERING makes very weak demands on the input, is efficient, and consistently performs well across experiments.
F.6 PetShop dataset
introduce dataset from cloud computing, specifically designed for evaluating root cause analyses in microserriccc-bsee applications. The dataset is collected from a microservice application and includes 68 injected performance issues, which increase latency and reduce availability throughout the system. Latency and availability are so-called 'metrics" of the microservice application, and measure the length of time it takes for request the service be processed, and the fraction of the time request returns an error, respectively. The dataset also encompasses three traffic scenarios: low, high, and temporal. These correspond to the amount and periodicity of user traffic to the application. This presents challenging task due to high missingness, low sample sizes, and near-constant variables. Furthermore, the ground truth causal graph only partially known, as we must treat the edge-inverted call graph as proxy for the causal graph.
Hardt et al. 2r
33

---

In addition to the approaches evaluated by Hardt et al. (see [27 for more details), which we have reproduced below, we evaluated our algorithms in both top-1 recall (Table. [ and top-3 recall (Table. 2). In addition, we included, as an additional baseline, the Traversal algorithm as described in Section 4 This added as although the evaluation already includes "Traversal' algorithm implemented by Hardt et al., here called 'petshop Traversal', their algorithm does not match the standard approach as described in [9] 24 25]. Instead, 'petshop Traversal' has been designed for use on the PetShop dataset, takes into account particular aspects of that data, and contrary to standard traversal algorithms, scores potential root causes according to anomalousness of whole paths of nodes from root cause to target node. 'Petshop Traversal' should not, therefore, be treated as "out-of-the- boxe baseline.
We observe that SMOOTH TRAVERSAL and SCORE ORDERING perform very well in top-1 1 and top-3 recall, often being the best performing algorithms, and clearly outperforming simple Traversal and Cholesky. However, while SMOOTH TRAVERSAL. always matches or exceeds the performance of simple Traversal in top-1 recall, on latency issues nonetheless tends perform relatively poorly compared to SCORE ORDERING.
Table 1: Top-1* recall, with ties. "Multiple anomalies can receive the same, highest, anomaly score.
The root cause being in the top-1 means that it is among the variables receiving the highest score.
given
not given
this paper
taffii
matric
petshop Towersal
Cires
ediagnosis
rol
conelation
Triercal
Cholesty
SCORE ORDERING
SMOOTH TRAVERSAI.
sornriia
factiaal
Tow
Iatency
0.57
0.36
0.36
0.00
0.07
0.43
0.14
0.20
1.00
0.14
Jow
availabiliy
0.42
0.00
0.58
0.75
0.42
0.00
0.75
0.75
high
lasency
0.50
0.00
0.00
0.64
0.14
0.14
1,00
0.14
high
ovailabilay
0.00
0.00
0.00
0.83
0.00
1,001
1.00
semporal
0.25
0.50
0.75
semporal
maiilbbility
Table Top-3" recall, with ties. MMulipple anomalies can receive the same, highest, anomaly score. The root cause being in the top-3 means that it is among the variables ranked in the top three including all variables tied the top.
gives
not given
This
traflic
metric
petshop Travessal
Cires
counter- Tactual
i-diagaosis
red
conclation
Traverial
Cholesky
SCORE ORDERING
SMOUTH TRAVERSAL
sccnario
Jaw
latency
0.57
0.86
0.71
0.00
0.21
0.57
0.14
0.57
1.001
11.5
low
mailsbilliy
1.00
1.00
0.43
0.00
0.75
0.92
0.50
0.00
1.00
1.00
high
latency
0.79
1.00
0.36
0.00
0.07
0.70
0.14
0.57
1.00
0.91
high
aviilabiiyy
0.00
0.33
0.00
0.92
0.33
0.00
1.00
1.00
temporal
latency
1.00
0.12
0.75
0.75
0.25
0.53
1.00
0.75
semporal
1,00
0.75
0,30
1.000
Note, however, the caveat that owing to the small sample size in the normal period the PetShop dataset, it is frequently the case that multiple anomalies receive the same highest IT anomaly score (see Table 3 for numbers and proportions of nodes with tied scores in cah traffic scenario). In the most severe cases there can be many as 20 nodes tied with the maximum score (in the high traffic scenario), but it is typically fewer than 10. The multiplicity of highest scores is due to the fact that for the issue at hand all these metrics were more extreme than ever sampled in the normal period. In this case, the root cause being in the top-1 means that it is among the variables receiving the highest score. This problem should become less severe for datasets where anomaly scorers are trained on a longer history. Since root cause analysis without any graphical information is notoriously hard problem, returning short lists of potential root causes, even they contain 10 or more candidates, can still result in drastic reduction of the search space, and so is of vital use in real applications.
34

---

Table 3: Average number and proportion of nodes in each traffic scenario and metric with tied
marginal anomaly score
Traffic scenario
Metric
Average number
Average proportion
high traffic
Latency
18.26
41.50%
high traffic
Availability
16.46
37.41%
low traffic
Latency
9.96
23.72%
low traffic
Availability
6.54
15.57%
temporal traffic
Latency
5.75
14.02%
temporal traffic
Availability
7.00
17.07%
temporal traffic2
Latency
5.75
14.02%
temporal traffic2
Availability
7.12
17.38%
We, nonetheless, also report the top-1 (Table. and top-3 (Table. 5 recall after randomly selecting among the nodes tied with the highest anomaly score. As expected, we observe approx. 10x decrease in top-1 recall for Traversal, SCORE ORDERING and SMOOTH TRAVERSAL, corre- sponding selecting at random from among the approx. 10 candidate scores. Similar decreases are present in top-3 recalls for Traversal and SCORE ORDERING when- ever the true root cause is among those with the tied highest score. Note, however, that SMOOTH TRAVERSAL generally still has high top-3 recall even after random selection of the top-1 node, outperforming both Traversal. SCORE ORDERING and Cholesky in all but one evaluation. Note that the performance of Cholesky does not considerably drop after random selection of ties, as variables rarely receive the same score.
causes with tied highest
Table 4: Top-1 recall, with random selection among ties.
this paper
traffic scenario
metric
Traversal
Cholesky
SCORE ORDERING
SMOOTH TRAVERSAL
low low
latency
0.02
0.29
0.10
0.02
availability
0.06
0.00
0.10
0.10
high
latency
0.01
0.14
0.06
0.01
high
availability
0.03
0.00
0.06
0.09
temporal temporal
latency
0.04
0.50
0.10
0.04
availability
0.04
0.00
0.13
0.14
Table Top-3 recall, with random selection among ties
this paper
Iraffic
metric
Traversal
Cholesky
SCORE ORDERING
SMOOTH TRAVERSAL
scenario
low low
latency
0.02
0.57
0.10
0.73
availability
0.10
0.00
0.31
0.31
high
latency
0.01
0.50
0.06
0.80
high
availability
0.03
0.00
0.06
0.09
temporal
latency
0.04
0.63
0.18
0.54
temporal
availability
0.04
0.00
0.13
0.14
F.7
Sock-shop dataset
Similar to the PetShop dataset described above, Pham et al. (26 introduces another dataset from cloud computing for evaluating root cause analyses. The dataset includes 125 injected performance issues encompassing five types of common faults: CPU hog 'cpu'. memory leak 'mem', disk IO stress 'disk', network delay- 'delay', and packet loss 'loss'. We again used the edge-inverted call graph for the Sock-shop application as proxy for the causal graph. We evaluated the performance
35

---

of our algorithms in top-1 (Table 6 and top-3 (Table 7 recall. It is important to note that while for most algorithms we provided only single anomalous sample (the first sample from the anomalous period) for RCD and e-Diagnosis we provided all 361 anomaly samples and so direct comparison is not recommended: both algorithms were included rather for completeness of evaluation.
We observe that on three out of five issue types (delay, disk and loss), SCORE ORDERING is the top performing approach for top-1 and top-3 recall. In each instance, SMOOTH TRAVERSAL also performed competitively. For issue types cpu and mem, however, both SCORE ORDERING and SMOOTH TRAVERSAL performed poorly, although performance was comparable among all algorithms which were provided with only a single anomalous sample. Given both RCD and D-Diagnssis performed considerably better for both issues, this would suggest that the effect of the fault was not easily discernible from only single sample in the anomaly period.
As for PetShop, we also report the top-1 (Table and top-3 (Table 9 recall after randomly select- ing among nodes with tied ranks. Here we observe that although the performance of SMOOTH TRAVERSAL is competitive for delay, disk and loss issues, both SCORE ORDERING and SMOOTH TRAVERSAL are outperformed by Circa and/or Cholesky. As both algorithms assume linear causal models, and that both algorithms struggled in non-linear settings in our simulation studies (see Figure T. this may suggest that the causal relationships in Sock-shop are well modelled by linear relationships. As before, for epu and mem issues, while all methods which use only a single anomaly sample perform very poorly, RCD performs well.
Table 6: Top-1* recall, with ties. "Multiple anomalies can receive the same, highest, anomaly score. The root cause being in the top-1 means that it is among the variables receiving the highest score. Theese methods were provided with all samples from the anomaly period, whereas all else were given only
cpu
delay
disk
loss
mem
SCORE ORDERING
0.08
0.80
0.84
0.72
0.08
SMOOTH TRAVERSAL
0.00
0.72
0.76
0.60
0.00
Cholesky
0.04
0.56
0.48
0.40
0.12
Circa
0.04
0.52
0.68
0.64
0.16
Counterfactual
0.04
0.28
0.00
0.12
0.04
Traversal
0.04
0.80
0.76
0.72
0.12
red
0.88
0.52
0.52
0.44
0.36
epsilon diagnosis
0.24
0.08
0.16
0.20
0.00
Table 7: Top-3* recall, with ties. "Multiple anomalies can receive the same, highest, anomaly score. The root cause being in the top-3 means that it among the variables ranked the top three, including tied ranks. *These methods were provided with all samples from the anomaly period, whereas all else were given only one.
cpu
delay
disk
loss
SCORE ORDERING
0.24
0.92
0.92
0.88
0.16
SMOOTH TRAVERSAL
0.12
0.80
0.84
0.72
0.12
Cholesky
0.16
0.88
0.88
0.84
0.24
Circa
0.28
0.72
0.80
0.80
0.28
Counterfactual
0.24
0.76
0.52
0.64
0.40
Traversal
0.04
0.80
0.76
0.72
0.12
red
1.00
0.52
0,56
0.44
0.52
epsilon diagnosis
0.56
0.52
0.28
0.48
0.00
36

---

Table 8: Top-1 recall, with random selection among ties. 'hese methods were provided with all samples from the anomaly period, whereas all else given only
cpu
delay
disk
loss
mem
SCORE ORDERING
0.08
0.24
0.29
0.26
0.04
SMOOTH TRAVERSAL
0.00
0.49
0.50
0.47
0.00
Cholesky
0.04
0.56
0.48
0.40
0.12
Circa
0.04
0.52
0.68
0.64
0.16
Counterfactual
0.04
0.28
0.00
0.12
0.00
Traversal
0.02
0,41
0.37
0,47
0.02
red
0.88
0.56
0.48
0.40
0.36
epsilon diagnosis?
0.24
0.08
0.16
0.20
0.00
Table 9: Top-3 recall, with random selection among ties. Thesse methods were provided with all samples from the anomaly period, whereas all else were given only one.
cpu
delay
disk
loss
mem
SCORE ORDERING
0.24
0.67
0.70
0.68
0.14
SMOOTH TRAVERSAL
0.12
0.76
0.83
0.72
0.04
Cholesky
0.16
0.88
0.92
0.84
0.24
Circa
0.28
0.72
0.80
0.80
0.28
Counterfactual
0.24
0.80
0.48
0.64
0.28
Traversal
0.04
0.79
0.75
0.72
0.07
red
1.00
0.56
0.56
0.44
0.48
epsilon diagnosis
0.56
0.52
0.28
0.48
0.00
F8 ProRCA
To provide evaluations of the algorithms in semi-synthetic setting, used the ProRCA package, introduced in [48]. ProRCA consists of a hand-crafted model of a retail service, with a known causal graph, allowing synthesis of data from real-world business scenarios, into which different types of anomalies can be introduced.
There are five types of anomalies that can be injected in the process, affecting different variables. We synthesised data following the introduction of four of these anomaly types, as listed the first column in Table I0 performing 100 replicates of each. We excluded the "COGs' anomaly type, which introduces an anomaly at the variable 'UNIT COST', as for a range of strengths of the anomaly, were unable to produce changes in the data that were statistically distinct from those in the non-anomalous regime.
We removed from consideration variables in the graph that had plain text values, such as 'PROMO CODE' these are unsuitable for RCA, but doing so introduced no unmeasured con- founding and does not affect the analysis. For each anomaly, we considered 'PROFIT" to be the target variable. 'PROFIT" not a leaf node in the causal graph and the length of paths between the root cause and the target variable varies between two and three. We applied Circa, Counterfactual, Traversal, and SMOOTH TRAVERSAL algorithms for which we are able to provide (the marginalised) causal graph, and the Cholesky algorithm and SCORE ORDERING, which only requires data from the observational and the anomalous regime. Only one anomalous sample was provided in each case. The resulting Top-1 recall of the algorithms is reported in Table IO
The results are mixed. SCORE ORDERING performs well for two types anomaly. both cases, the methods that require the graph also perform well. However, requiring the graph for the RCA algorithm might constraining in most real-world scenarios. There are two types of anomaly where SCORE ORDERING does not perform well: In "ExcessiveDiscounn" only the Counterfactual method provides Top-1 recall above 30%, even for those methods requiring the graph as input. In "ReturnSurge' the Cholesky method performs well (66%) and those methods for which the graph
37

---

Table 10: Top-1 recall, with random selection among ties.
graph given
graph not given
this paper
SCORE ORDERING
SMOOTH TRAVERSAL
Type of anomaly
Circa
Counterfactual
Traversal
Cholesky
ExcessiveDiscount
0.04
0.89
0.30
0.00
0.04
0.04
Fulfllmmnttpikk
0.96
0.98
0,94
0.74
0.94
0.28
ReturnSurge
1.00
0.88
0.97
0.66
0,00
0.18
Shipping
0.94
0.94
0.94
0.47
0.95
0.27
given provide recall above 85%. In all types of anomalies, SMOOTH TRAVERSAL has performance below 30%.
38


Reviews:
[{"review_id": "Lgd6joxzW8", "reviewer": "Reviewer_D5Fu", "summary": "The paper presents a method for Root Cause Analysis that is based on analyzing the anomaly scores of variables. Assuming a single abnormal variable and a causal graph that is a polytree, the paper develops algorithms for discovering the abnormal variable for cases when the causal graph is known and unknown. It also establishes a connection between the abnormality of conditional probabilities (soft interventions) and marginal/conditional anomaly scores based on statistical tests.", "questions": "1. What prevents the estimation of conditional anomaly scores as shown in Section 3.2?\n2. Theorem 3.9: It is unclear whether the equations $S(x_j)-S(pa_j) \\geq S(x_n)/2$, $S(x_i) - S(pa_i) \\leq S(x_n)/4$ are derived from the structural property of the DAG being a tree, or if they are stated as assumptions.\n3. How difficult would it be to generalize the result to multiple root causes? A brief discussion on this can be quite helpful.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The idea of identifying root causes based on anomaly scores is interesting. While the approach builds on [Budhathoki et al., 2022], the contributions are novel.\n2. The paper offers rigorous theoretical results, with complete proofs in the appendix, and presents reproducible pseudocode. It also includes simulation results on randomly generated SCMs.\n3. Overall, the paper is well-structured, and the writing is mostly clear.\n\nWeaknesses:\n1. I could not find any soundness/completeness results on the Smooth Traversal and Score Ordering algorithms when the causal graph is a polytree (lower-bound is only provided for tree structures), which is central to the paper’s contributions. The provided lower bound applies only to tree structures. Are there scenarios in which these algorithms are guaranteed to be sound and complete? Please let me know if I missed something.\n2. Lines 56-58: I would not consider the polytree assumption to be \"weak.\" Moreover, the methods also rely on assumptions about the anomaly scoring function, which should be clearly stated in the introduction.\n3. Lines 134-135: What's the definition of N and id?\n4. In Section 3.3, is the Continuity assumption still required for marginal anomaly scores? This should be clarified at the beginning of the subsection. \n5. Line 248: Instead of referring to \"this final assumption,\" please name the specific assumption to improve clarity.\n6. I recommend including concrete examples to illustrate key graphical concepts (e.g., polytree vs. tree), as well as the notions of marginal/conditional anomaly scores and how the two main algorithms perform root cause selection.\n7. The conclusion section appears incomplete.", "was_revised": true, "final_justification": "My concerns have been addressed.", "rebuttal": "> Addressing weaknesses:\n\n1. Thank you for raising this point. Let’s say a root cause analysis algorithm is sound if every variable it returns is a root cause, and say it is complete if every root cause among the input variables is returned. As our algorithms take marginal anomaly scores, which are only defined with respect to particular samples, it is not possible to define soundness/completeness independently of sample variation during the anomalous period. In this sense we cannot guarantee soundness/completeness. Literature on algorithms for causal discovery often define an oracle with respect to which soundness/completeness are defined in order to circumvent this caveat, but it is not clear what a suitable oracle would be in our setting. Nonetheless, Theorem 3.10 can be interpreted as a soundness result for SCORE ORDERING as it shows that if the largest anomaly score exceeds the next largest by a large amount, then the probability that the top-scoring variable is not the root cause is small—i.e. SCORE ORDERING is sound with high probability in this case. For SCORE ORDERING to be complete we would need to show that any root cause variable will have (with high probability) a larger score than non-root causes (as otherwise SCORE ORDERING will not return every root cause with high probability). As such, a priori we cannot expect completeness without further assumptions as in deterministic causal systems, anomalies are perfectly propagated, so downstream nodes will receive the same score as the root cause. To guarantee the anomaly score decays, we need to postulate constraints on the minimal noise level. For instance, for a linear Gaussian cause-effect relation, $X \\to Y$, with Pearson correlation $\\rho$, the $z^2$ score of $Y$ is with high probability close to $\\rho^2$ times the $z^2$ of $X$, which can be translated into a decay of IT anomaly scores by recalibration. We are happy to include such model-dependent guarantees for score differences, but we currently have no idea for a concise general constraint on the noise level. For SMOOTH TRAVERSAL, we have shown (Lemma 3.7) that the score of a non-root cause is unlikely to exceed that of its parent by a large amount, i.e. if the score difference is large, SMOOTH TRAVERSAL is likely to be sound. Completeness would mean that every root cause exceeds the score of its parents by a large amount, which also requires additional assumptions. It is not obvious to find an assumption that does not trivially imply what is supposed to be shown.\n\n2. Our apologies, you are quite right of course that the polytree assumption is not weak. Indeed on lines 282–283 we note that it is a strong assumption. Lines 56-58 were rather poorly phrased: the intention was to say that the assumptions on the anomaly scores are weak, first applied to cause-effect pairs and then to polytrees, but we accept that this was unintentionally misleading. We will remove the word “weak” and state explicitly that our results require so-called “information theoretic (IT)” anomaly scores as well as additional assumptions on them.\n\n3. N is an independent noise variable, as in a structural causal model, and id is the identity function. We will alter the text to define both as suggested.\n\n4. Thank you for raising this issue, we admit that it is often not clear which assumptions are required for which results. In the revised manuscript we will state next to each assumption exactly which Lemmas and Theorems rely on them. For the question of continuity in particular: yes we still use the continuity assumption for the results concerning marginal anomaly scores in subsection 3.3. This is because to obtain the bound on the p-value in Theorem 3.8, we need (in addition to Lemma 3.7) Theorem 3.6 which itself follows from Lemmas 3.4 and 3.5 under the assumption of continuity in the previous subsection. However, continuity is not strictly necessary: we use it as a concise condition as it is sufficient to ensure conditional anomaly scores are statistically independent (Lemma 3.4). More generally, any condition which is also sufficient would do. Note we do not use continuity in subsection 3.4 for the results concerning using marginal anomaly scores for SCORE ORDERING.\n\n5. On line 248 the assumption in question is that we know the causal graph, stated in the previous sentence, but we agree this should be clarified: we will change the text accordingly.\n\n6. Thank you for the recommendation, we agree that this would improve understanding of the paper. To illustrate the difference between conditional and marginal score we will introduce an example where we consider a linear Gaussian cause-effect pair. This is because in the linear Gaussian setting, marginal IT anomaly scores can be derived via re-calibrating $z^2$ scores on the variables themselves, while conditional scores are derived from $z^2$ scores of the regression residual. To illustrate the key graphical concepts, we will add an additional figure showing an example of a polytree, collider-free polytree and a DAG, and highlight their differences.\n\n7. Thank you for raising this, you are right, the conclusion is unhelpfully brief. This was an unfortunate mistake arising from cutting text to meet the page limit. We will expand the conclusion, and suggest the following: “We have explored several directions in which the practical limitations of RCA can be addressed: first by avoiding estimation of conditional distributions in the setting that the causal graph is known, and second by avoiding needing the causal graph at all, in the setting that it is a polytree. To do so, we leverage information theoretic (IT) anomaly scores, and prove general laws about their typical decay along causal paths. Using our results, we then propose two novel algorithms: SMOOTH TRAVERSAL and SCORE ORDERING, give probabilistic guarantees for the correctness of their outputs, and show they have competitive performance in both synthetic and real-world data despite their simplicity. To our knowledge, our work is the only which provides guarantees for RCA in the non-linear setting from a single anomalous point without requiring knowing the full structural causal model.”\n\n> Addressing questions:\n\n1. Estimating conditional anomaly scores is hard as it requires estimation of conditional probabilities, which is statistically ill-posed, as noted on lines 111-112 at the top of Section 3. We will clarify this point at the end of subsection 3.2 to motivate the approach followed in subsection 3.3.\n\n2. We agree this is unclear. The inequalities are neither derived from structural properties nor are they assumptions, rather, when the inequalities hold, the root cause is the unique node which maximises the score difference with its parent from among the ancestors of the target node. The theorem then establishes a lower bound on the probability that the inequalities hold (and thus the root cause is correctly identified) subject to the structural assumptions on the DAG and the previously stated assumptions on the anomaly scores. We will rephrase the theorem to avoid confusion and suggest the following: “Let the causal DAG for $X_1,\\dots,X_n$ be a collider-free polytree and node $j\\in \\{1,\\dots,n\\}$ be the unique root cause of the anomaly $x_n$, then the following inequalities hold with probability at least $1 - (n-1)\\cdot e^{-\\frac{1}{4}S(x_n)}$: $S(x_j) - S(pa_j) \\geq S(x_n)/2$, $S(x_{i}) - S(pa_i) \\leq S(x_n)/4 \\forall i\\neq j$, and hence root cause $j$ is the unique node that maximises the anomaly score difference with its parent.”\n\n3. This is a very good question and we agree it’s important that we include a discussion as suggested. The results in subsection 3.4, concerning SCORE ORDERING, already apply to the case of having multiple root causes (i.e. more than one variable whose causal mechanism is corrupted for the single sample from the anomalous regime). This is because Theorem 3.10 is stated in terms of rejecting the hypothesis that none of the top-k highest scoring anomalies, as such, rejecting this hypothesis does not imply that there is only a single root cause among the top-k, but rather at least one. SCORE ORDERING therefore remains a suitable approach in this more general setting. We can say something similar concerning SMOOTH TRAVERSAL by slightly altering the null hypothesis given at the beginning of subsection 3.2 (lines 174-175). Instead of rejecting the hypothesis that all causal mechanisms worked as normal, except possibly the one for $X_j$, we can reject the hypothesis that all causal mechanisms worked as normal except for possibly $X_j$ and $X_l$. Following exactly the same steps as before in subsections 3.2 and 3.3 (i.e. defining the joint anomaly score but now excluding both $X_j$ and $X_l$ from $S_{\\rm sum}$), we will arrive at a corresponding version of Theorem 3.8 wherein the bound on the likelihood is weakest if we infer the top two variables with the largest score difference from their parents as root causes. Similarly we could do the same for three root causes and so on. In other words, Theorem 3.8 justifies taking the top-k variables with the largest score differences from their parents whenever one suspects there are k root causes. The important caveat here is that while this approach for selecting k is suitable for small k, one incurs a larger multiple testing burden as k increases, and this would need to be accounted for. It would also be possible to adapt Theorem 3.9, but this is more intricate. In a similar spirit to SCORE ORDERING, when k is unknown, one could choose the minimum k for which the likelihood bound in Theorem 3.8 is now “acceptably” weak for some combination of k variables."}, {"review_id": "nvKIBtVdvI", "reviewer": "Reviewer_P4jd", "summary": "This paper presents a novel approach to Root Cause Analysis (RCA) for outliers, focusing on the challenging yet practical scenario where only a single anomalous data sample is available and the causal graph may be unknown. The authors introduce two efficient methods based on information-theoretic anomaly scores. For cases with a known tree-structured causal graph, the SMOOTH TRAVERSAL algorithm identifies the root cause by finding the largest increase in anomaly score between a node and its parents. When the graph is unknown, the SCORE ORDERING heuristic is proposed, providing a causally-justified method for shortlisting root causes by simply ranking variables by their marginal anomaly scores. Experiments demonstrate that SMOOTH TRAVERSAL is competitive with more complex, state-of-the-art methods, while SCORE ORDERING provides a robust and simple heuristic.", "questions": "Why does Assumption Continuity in section 3.2 (line 182) hold? More justification will help.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n1. The methods proposed are simple but effective without strong assumption and requirement on the input. The proposed methods are practical and easy for implementation.\n2. Through simplicity, the authors provide theoretical justification of the methods under certain assumptions. Moreover, the authors point out the key insights behind both methods as an anomaly is unlikely to cause a much larger one downstream.\n3. The authors carry out empirical experiments on synthetic causal graphs with comparison to several state-of-art methods.\n\nWeakness\n1. The paper's primary theoretical guarantees for both the SMOOTH TRAVERSAL and SCORE ORDERING methods are developed under the assumption that the causal graph is a polytree (a tree-like structure). It would be great to see experiments on how the violation of the property impacts the performance of the proposed method.\n2. The methodology is designed around the hypothesis that there is only a single root cause for the observed anomaly. It would be interesting to see how the results generalize if multiple anomalies exist.", "was_revised": true, "final_justification": "I have read authors' rebuttal and will remain my initial evaluation", "rebuttal": "> Addressing weaknesses\n\n1. Thank you for this suggestion, this is indeed an interesting question to address. It is worth noting that in all experiments presented in the manuscript (both synthetic and real-world), we do not constrain the causal graph to be a polytree and already both of our proposed algorithms have competitive performance. In particular, it will be difficult to detect any improvements in the performance of SMOOTH TRAVERSAL were we to constrain the causal graphs to be polytrees, however, it remains an open question as to how much SCORE ORDERING could benefit (and whether any benefit exceed that for the other algorithms against which we compare). We will therefore repeat the experiments in figure 1 for polytrees and collider-free polytrees and include two extra figures in the manuscript should it be accepted.\n\n2. We agree this is definitely an interesting question! Please see the detailed reply we gave to reviewer D5Fu to their question three at the end of our reply to them as it concerns exactly the same question of how to generalise to the cases of multiple root causes (and apologies for sending you to look at our replies to other reviewers!)\n\n> Addressing questions\n\n1. Thank you for raising this issue, we admit that it is often not clear which assumptions are required for which results. In the revised manuscript we will state next to each assumption exactly which Lemmas and Theorems rely on them. For the question of continuity in particular: we use continuity as a concise condition as it is sufficient to ensure conditional anomaly scores are statistically independent (Lemma 3.4). We need this for Theorem 3.6 later in the section and again for Theorem 3.8. However, continuity is not actually strictly necessary, more generally, any condition which would sufficient to ensure the conditional anomaly scores are statistical independent would do. We will clarify this in the text following the statement of the assumption."}, {"review_id": "66Uv0XdAbK", "reviewer": "Reviewer_Mb8b", "summary": "This paper proposes two simple and efficient algorithms, Smooth Traversal and Score Ordering, to perform root cause analysis (RCA) of anomalies when the causal structure is either known (a tree) or unknown. It builds on the idea of modeling anomalies as soft interventions in a CBN and focuses on the regime where only a single sample from the anomalous setting is available. The experiments on synthetic data and PetStop dataset show the value of the proposed methods.", "questions": "1. Could you include a comparison with methods such as $\\epsilon$-Diagnosis and RCD in a regime where more than one anomalous sample is available (e.g.,100 samples)?\n\n2. For the PetShop dataset (Tables 1 and 3), how many nodes are typically flagged as potential root causes? What proportion of the total graph do these represent?\n\nI find the paper really intriguing and I think it has value. I am willing to increase my score if the authors can address my questions.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The theoretical contributions are well-developed and remove the need for selecting arbitrary p-value thresholds.\n- The proposed use of marginal anomaly scores in both known and unknown causal settings is elegant and supported by strong theoretical guarantees.\n\nWeaknesses:\n\n- Limited evaluation on diverse real-world scenarios\n- I could not find any link to the source code.\n\nDetailed Feedback:\n\nI found the theoretical contributions really interesting, especially the principled treatment of anomaly scores and the avoidance of arbitrary thresholds. This is a refreshing alternative to many existing RCA approaches. However, I have concerns about the limited scope of the empirical evaluation and the real-world applicability of the proposed methods.\n\nThe justification for excluding comparisons with RCA methods like $\\epsilon$-Diagnosis and RCD is that those methods assume access to multiple anomalous samples, whereas this work operates in the single-sample regime. While this is a valid distinction, in many real-world systems it is often feasible to collect a small number of anomalous samples (e.g., 50–100). Therefore, I believe the comparison with the existing approaches in the area of multiple anomalous samples is crucial for the work.\n\nThe motivation for this suggestion stems from a concern that, in complex systems, even with access to more than a single anomalous sample, the anomaly scores for most (if not all) nodes may remain very low. In such cases, the algorithm might end up flagging a large number of nodes as anomalous, hence diminishing its practical utility. This issue is evident in Table 3 of the Appendix, where the proposed method achieves only 14% top-1 recall. Furthermore, the justification provided in Tables 1 and 2—treating multiple nodes with identical scores as equally valid root causes—seems unrealistic in real-world scenarios. This raises an important question: how many nodes (and what proportion of the total) are typically flagged as potential root causes? As it stands, the evaluation does not fully convince me that the proposed methods can be reliably applied in large, noisy, or complex environments where more than one anomalous event or a broader root cause structure is involved.", "was_revised": true, "final_justification": "I have considered the discussion with the authors and have decided to increase my score Borderline Accept. I would have wanted transparent discussion on when the anomaly score is tied and evaluation when more than one anomalous sample is given.", "rebuttal": "> Addressing weaknesses\n\n1. You are right that we could do more to evaluate on a wider variety of real-world scenarios. To expand our evaluation to more real-world scenarios, we will in addition to the experiments we have already included using the PetShop dataset and the ProRCA package, we will evaluate each of the algorithms on the Sock-shop 2 dataset (Pham et al, 2024, “Root Cause Analysis for Microservice System based on Causal Inference: How Far Are We?”), and additional Top-1 and Top-3 recall performance tables in the Appendix.\n\n2. We apologise for its omission upon submission. We would have shared it as part of our rebuttal if it were not this year’s changes to the rebuttal format. We will include a link to the source code should the paper be accepted.\n\n> Addressing detailed feedback\n\nYou raise an important point regarding our algorithms flagging up many potential root causes. This occurs due anomalies receiving tied anomaly score estimates, however, the issue actually stems not from too few samples in the anomalous period (but too few samples in the normal period), nor from anomaly scores being too low (in fact rather when anomalies are too strong). As noted on line 105 below Equation 5, the maximum (estimated) IT anomaly score that can be achieved in a sample of size k is $\\log k$. This corresponds to the case where the sample being scored is more anomalous than any sample observed in the normal period. As such, a very strong anomaly at the root cause may not only receive the maximum anomaly score, but also cause anomalies in its descendants which also receive the maximum score (even if the caused events are considerably less rare) if the sample size in the normal period is too low. For example, if one has 1000 samples in the normal period, a 1/1000 anomaly event will receive the same (maximum) estimated score as an 1/10,000 event. Note that this is not an issue with the anomaly score itself, but with the estimates given by the estimator in Equation 5. For example, if one had a parametric estimate of the tail of the distribution, then tied score estimates would not occur. Tied score estimates are less of an issue in settings where many samples are available from the normal period, but are prohibitive in our real-world PetShop experiments wherein there are no more than ~600 normal period samples (and often far fewer due to missingness). Regarding low anomaly scores, note that we assume that we are performing root cause analysis due to a (sufficiently) large anomaly being detected at a target node. Such an anomaly could not be explained if all nodes received a low score. Finally, it is important to note that in noisy systems the problem is actually also less pronounced. In a highly deterministic system, anomalies will propagate (close to) perfectly from root cause to descendants, resulting in anomaly scores which decay slowly along paths. In more noisy systems, anomaly scores decay rapidly along paths, further reducing the risk of descendants receiving the maximum possible estimated score even if the root cause does. Interestingly then our results may be expected to actually perform better in larger, more noisy systems when more normal period data is available.\n\n\n> Addressing questions\n\n1. This is an important point you are right to raise as although the single-sample setting is more challenging, and is the focus of the work, it is nonetheless true that in many settings one may have access to more than one sample. Note that we do compare our algorithms to RCD and epsilon-Diagnosis in Tables 1 and 2 on the PetShop data wherein all methods that require multiple anomalous samples are given access to between two and five samples in the anomalous period (depending on how many samples were missing in the dataset). However, we will extend the comparisons made using synthetic data to RCD and epsilon-diagnosis as you have suggested. It is important to note, however, that RCD is a conditional independence-based and as such performs poorly when the sample size in the anomalous period is too small. For example, Figure 2 in the supplementary material for the paper presenting RCD (Ikram et al, 2022, ​​Root Cause Analysis of Failures in Microservices through Causal Discovery) shows that in synthetic data the recall for RCD only becomes competitive (>0.7) once there are thousands of samples for the anomalous period, whereas both SCORE ORDERING and SMOOTH TRAVERSAL exceed this recall in our own experiments (Figure 1 of our paper) for only a single anomalous sample, but we agree a combined comparison with our own algorithms should certainly be done nonetheless.\n\n2. This is certainly an important question, and as noted above, the issue is exacerbated in the PetShop dataset due to the relatively low sample size in the normal period (due to high missingness) and relatively strong anomalies at the root cause. Below is a table summarising the average number of nodes which receive the same maximum estimated IT anomaly score, therefore will all be flagged by SCORE ORDERING, split according to issue type in the PetShop dataset. Note that the PetShop graph contains 41 nodes. We will include this table in Appendix E alongside Table 3 and 4. The table reveals what a challenge tied maximum estimated scores are in the PetShop dataset. \n\n| Scenario          | Metric       | Avg Nodes | Avg Proportion |\n|--------------------|-------------|---------------|----------------|\n| high_traffic       | Latency      | 18.26         | 41.50%         |\n| high_traffic       | Availability | 16.46         | 37.41%         |\n| low_traffic        | Latency      | 9.96          | 23.72%         |\n| low_traffic        | Availability | 6.54          | 15.57%         |\n| temporal_traffic1  | Latency      | 5.75          | 14.02%         |\n| temporal_traffic1  | Availability | 7.00          | 17.07%         |\n| temporal_traffic2  | Latency      | 5.75          | 14.02%         |\n| temporal_traffic2  | Availability | 7.12          | 17.38%         |"}, {"review_id": "KBBmxkYoDc", "reviewer": "Reviewer_RvMn", "summary": "The paper addresses the problem of RCA in scenarios where only a single sample from the anomalous distribution is available, relying on information-theoretic anomaly scores. The author acknowledges that, in practice, anomalies often have multiple root causes; however, they argue that these can be addressed sequentially, one at a time. Two methods are proposed: (1) Smooth Traversal – Applicable when the causal graph is known and structured as a polytree. This method identifies the root cause by selecting the variable that shows the largest increase in anomaly score relative to its parents. (2) Score Ordering – Designed for settings where the causal graph is unknown. It assumes that the top-k variables with the highest marginal anomaly scores are likely to be root causes. The paper provides theoretical guarantees for both methods under specific assumptions. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of the proposed.", "questions": "1. From the results of the experiments, baselines Traversal and Counterfactual have comparable performance with Smooth Traversal, maybe more complex dataset is needed.\n2. Please add more detail about the difference of this work from the following work: ‘[23] Kailash Budhathoki, Lenon Minorics, Patrick Bloebaum, and Dominik Janzing. Causal structure based root cause analysis of outliers’ \n3. Could the authors clarify how Equation (5) is computed or estimated in practice?\n4. In real-world scenarios, it is common to observe multiple anomalous samples rather than just a single one, as this helps reduce false alarms. Given this, how should the proposed method be applied when multiple anomalous samples are available? Since different samples might lead to different conclusions,", "limitations": "The authors have addressed key limitations of their method. They also suggest that their methods could serve as heuristics in broader contexts. However, the author could include a brief discussion on potential societal consequences, especially in high-stakes fields like healthcare or finance, where erroneous root cause identification could lead to harm.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n(1) It addresses a practical challenge by focusing on RCA with a single anomalous sample, a scenario very close to real-world settings.\n(2) The methods are computationally simple and efficient.\n(3) The structure of the paper is clear and logical, progressing smoothly from background material to theoretical results and empirical validation.\n\n\nWeaknesses:\n(1) The assumption of polytree is a kind of restrictive, as real-world causal structures are often more complex (e.g., containing cycles or multiple parents).\n(2) Experimental results show that baseline methods such as Traversal and Counterfactual perform comparably to Smooth Traversal (authors’), suggesting that more complex or varied datasets may be needed to demonstrate clearer advantages.\n(3) The difference of this work from the following work in the case where the causal graph is known or unknown could be more clearly articulated, ‘[23] Kailash Budhathoki, Lenon Minorics, Patrick Bloebaum, and Dominik Janzing. Causal structure based root cause analysis of outliers’", "was_revised": true, "final_justification": "The problem setting of identifying the root cause from a single anomalous sample is interesting. In the rebuttal, the authors shared some promising ideas for extending the approach to handle multiple anomalies; however, I still find the underlying assumption somewhat restrictive. Overall, I will maintain my score.", "rebuttal": "> Addressing weaknesses\n\n1. You are right, the polytree assumption is indeed restrictive (though note that it does not restrict nodes to having only a single parent, it rather means there are no undirected cycles, but you are right that for Theorem 3.9 we additionally assume only a single parent). In subsection 3.5 and Appendix D we give some justification for the application of our algorithms even in cases where this assumption is violated, and in all experiments we do not restrict the causal graph to be a polytree, and both of our algorithms show competitive performance. Note also that the only other root cause analysis approach which operates in the setting we study (Li et al, 2025, “Root cause discovery via permutations and Cholesky decomposition”), the method we refer to as “Cholesky” in the Experiments section, assumes that the causal model is linear, while our approach does not. As such, we still believe that our work is an important contribution to the current state of root cause analysis research. To better highlight are discussion of the polytree assumption, we will move some of the discussion from Appendix D into the main text as there we show that we expect SCORE ORDERING to fail only rarely when the polytree assumption is violated (at least in the linear setting).\n\n2. This is a good observation. Generating challenging synthetic data that is both realistic, but whose simulation parameters are interpretable (so that we can study why and when our algorithms fail), is often a challenge, but note that we do see considerable performance differences between even the top performing algorithms when applied to real-world (and semi-synthetic) datasets in Appendix E. Nonetheless, we will expand the synthetic data experiments to address this shortcoming. In particular, we propose comparing the performance of each of the algorithms which depend on being given the causal graph (i.e. Traversal, Counterfactual, SMOOTH TRAVERSAL, and Circa) after introducing an increasing number of random edge additions/deletions/reversals to the graph they are given, simulating the case where the assumed graph does not perfectly match the true graph. This will not affect the performances of SCORE ORDERING and Cholesky which do not rely on the causal graph, but should allow us to test how robust SMOOTH TRAVERSAL is to misspecification of the graph compared to the other algorithms, and to assess at what point it is preferable to use a method which does not rely on the causal graph, such as SCORE ORDERING, compared to one that does.\n\n3. Thank you for raising this point as it is of particular importance to our work. Budhathoki et al not only assumes that you know the causal graph, but assumes you know the full structural causal model. Such an assumption is extremely prohibitive as in practice the structural causal model cannot be estimated from either observational or interventional data. We will better emphasise the differences of our work from that of Budhathoki et al in the introduction. Note that we devote Appendix A to showing how our work relates to that of Budhathoki et al even though we do not need the structural causal model (or even the causal graph in the case of SCORE ORDERING).\n\n> Addressing questions\n\n1. Please see answer to point 2 in \"Addressing weaknesses\" above\n2. Please see answer to point 3 in \"Addressing weaknesses\" above\n3. The estimator in Equation 5 corresponds to applying the $\\tau$ feature map to each sample in the normal period, and to the single sample from the anomalous distribution, and counting the number of points which are equal or greater in the normal period, to the anomalous sample, followed by taking the negative logarithm. In other words, it is the negative log of the quantile with respect to the empirical distribution. We will include this additional description following Equation 5 in the text to aid with clarity.\n4. This is a good question. Although we have focused on the case where there is only a single anomalous sample, as this is a more difficult setting, the theory we present is equally suitable in the setting where one has more than one anomalous sample. One must instead define multi-dimensional feature maps ($\\tau$ in Equation 3), $\\tau: \\mathcal{X}^{m} \\rightarrow \\mathbb{R}$ where $m$ is the number of anomalous samples. In this case, in effect one treats the collection of anomalous samples as being a single multi-dimensional sample and so the subsequent theory is unchanged. The advantage in this setting is that an appropriately defined feature map can enable the detection of more general distribution changes than are possible from a single sample. For example, if the anomalous distribution for a variable were to reduce in variance, but be unchanged in mean, each individual sample drawn from it would not appear anomalous, but together multiple samples would have an “unusually” low variance, and so collectively the samples would receive a high anomaly score for an appropriately defined feature map. Alternatively, if one assumes that samples are drawn iid from the anomalous distribution, as is often assumed in RCA literature, then one can define joint anomaly scores (joint over the $m$ samples) for each variable, similarly to Equation 7 in subsection 3.2 (or in the arXiv version of Budhathoki et al, which you have cited above) by taking the convolution of the individual sample anomaly scores. Although defining a multi-dimensional feature map would be preferable, another option as a simple heuristic in practice could be to apply our algorithms to each sample individually, and then pick a variable as root cause according to a rule such as majority-vote."}, {"review_id": "rQTUlVsHPq", "reviewer": "Reviewer_juNp", "summary": "Root Cause Analysis of Outliers with Missing Structural Knowledge tackles the challenge of identifying root causes from a single anomaly when the full causal graph is unknown. The authors define each variable’s ‘surprise’ as the negative log tail-probability of a chosen statistic, forming an information-theoretic (IT) anomaly score derived solely from background data. In directed-tree (polytree) structures, sharp increases in these scores indicate the origin of change. Building on this, Smooth Traversal traces back from the anomalous node to its highest-scoring ancestor using a known DAG. When the graph is unknown, they introduce Score Ordering, which ensures the true root ranks among the top-k scorers under a mild in-degree assumption. Experiments on synthetic and real-world data show these efficient methods outperform stronger baselines with significantly less structural knowledge and computation.", "questions": "1) If the authors are constrained by the page limit, it may be helpful to adjust the formatting to save space and allow for a more comprehensive conclusion, clearer discussion, and better-organized experimental section?\n2) Would it be possible to include more comprehensive experiments using additional real-world datasets, as well as scenarios where the proposed methods might fail?\n3) Would it be possible to expand the conclusion and reorganize the introduction to improve clarity and readability?", "limitations": "No. While the paper clearly names several technical caveats—e.g., dependence on a polytree structure, the single-fault setting, and the need for sufficient background data (Sec. 3–4)—it does not meaningfully discuss (i) how these assumptions limit real-world deployment, or (ii) Sample-complexity guidance.\n1) While the authors acknowledge the limitations of these strong assumptions, they do not thoroughly discuss their implications in practical applications and real-world scenarios.\n2) Sample-complexity guidance. Provide empirical or theoretical bounds on the amount of background data required for stable information-theoretic scores, so practitioners can gauge feasibility before adoption.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n1) Timely problem setting with clear practical impact – the paper tackles RCA when only one anomalous sample is available and conditional densities are ill-posed to learn, a scenario common in fast-moving operations and personalised medicine .\n2) Conceptual originality. They re-casting outlier “surprise” as an information-theoretic (IT) anomaly score that needs only background data removes the hardest estimation bottleneck.\n3) Algorithmic simplicity & efficiency – SMOOTH TRAVERSAL and SCORE ORDERING run in near-linear time and need either the DAG or just an in-degree bound; experiments show they are the fastest among tested methods while matching or exceeding stronger baselines on accuracy .\n\nWeaknesses\n1) The overall presentation is difficult to follow without close reading. For example, in the experimental section, it is not easy to clearly identify the model, dataset, and settings used, or what the author aims to demonstrate. It would be beneficial to organize these components with clearer logic and structure. It appears that the author may be constrained by the page limit—yet there are formatting inefficiencies, such as on lines 243, 213, and 67, where single words occupy entire lines. These could be optimized to save space. Additionally, the Introduction and Conclusion are very brief but not in a concise or effective way that helps readers quickly grasp the paper's core contributions and content.\n2) While the authors repeatedly state in the methodology section that the 'Monotonicity Assumption' is not required, they continue to rely on it for demonstrations. It would be beneficial, if possible, to present general results in main paper without this assumption, as it is often unrealistic in practical settings.\n3) The experiment part can be expand if more real word dataset can be evaluated to show the robustness of the methods proposed by author. And if possible, further analysis on case study when will the methods fails to guide practical application since this is one of the main motivation brought by authors.", "was_revised": true, "final_justification": "The authors have addressed my concerns; however, the novelty and technical quality still do not warrant a higher score, so I am maintaining my original rating.", "rebuttal": "> Addressing weaknesses\n\n1. Thank you for raising this issue, it’s of course very important that the paper is as easy to follow as possible. For the Experiments section we propose stating, in bullet points, for each experiment: how it is performed, why it is performed, the range of synthetic parameters used and the methods compared including the assumptions each makes. In addition, we propose including a new table which summarises this information and where to find the corresponding results figures. Thank you as well for pointing out where we can optimise space. For the Introduction, we propose reorganising Subsection 1.1 to give a more detailed breakdown of the following sections, including a summary of the main results from each, and the motivations for each. We hope this will better motivate the work and allow the reader to better anticipate what results are coming and why. Finally, you are absolutely right that the Conclusion is unhelpfully brief. This was an unfortunate mistake arising from last minute changes to meet the page limit. We will expand the conclusion, and suggest the following: “We have explored several directions in which the practical limitations of RCA can be addressed: first by avoiding estimation of conditional distributions in the setting that the causal graph is known, and second by avoiding needing the causal graph at all, in the setting that it is a polytree. To do so, we leverage information theoretic (IT) anomaly scores, and prove general laws about their typical decay along causal paths. Using our results, we then propose two novel algorithms: SMOOTH TRAVERSAL and SCORE ORDERING, give probabilistic guarantees for the correctness of their outputs, and show they have competitive performance in both synthetic and real-world data despite their simplicity. To our knowledge, our work is the only which provides guarantees for RCA in the non-linear setting from a single anomalous point without requiring knowing the full structural causal model.”\n\n2. You are absolutely right that monotonicity is unrealistic in practical settings, and you have noticed how important it was to us to stress that this assumption is not required, hence the repeated statements throughout Section 3. We felt it was very unfortunate that we had to reserve the theory without the assumption for Appendix B. This was done because we worried that the theory would become more difficult to follow as all of the Lemmas and Theorems following the assumption must be stated more intricately, and the bounds presented become slightly less concise as the inequalities hold up to some small $\\epsilon$. We accept your criticism nonetheless. We propose instead to move Lemma B.2 from Appendix B into the main text so as to explain why the inequalities hold up to some $\\epsilon$, and subsequently state the results as they are currently presented but without monotonicity and using the slightly less concise inequalities. We will then continue to refer to the Appendix for the full detail for each Lemma and Theorem without monotonicity. This should be possible with the extra space afforded by the camera-ready version of the manuscript, should it be accepted, without significant loss of clarity.\n\n3. You are right to raise the issue of robustness. To expand our evaluation to more real-world scenarios, we will in addition to the experiments we have already included using the PetShop dataset and the ProRCA package, we will evaluate each of the algorithms on the Sock-shop 2 dataset (Pham et al, 2024, Root Cause Analysis for Microservice System based on Causal Inference: How Far Are We?). We will also expand the synthetic experiments in two ways: first we will repeat the experiments, but restricting the causal graph to be polytree or a collider-free polytree (as currently in no experiment to impose this constraint) to see how performance may be affected when this assumption is met, second, we propose comparing the performance of each of the algorithms which depend on being given the causal graph (i.e. Traversal, Counterfactual, SMOOTH TRAVERSAL, and Circa) after introducing an increasing number of random edge additions/deletions/reversals to the graph they are given, simulating the case where the assumed graph does not perfectly match the true graph. This will not affect the performances of SCORE ORDERING and Cholesky which do not rely on the causal graph, but should allow us to test how robust SMOOTH TRAVERSAL is to misspecification of the graph compared to the other algorithms, and to assess at what point it is preferable to use a method which does not rely on the causal graph, such as SCORE ORDERING, compared to one that does. Finally, we will include an expanded discussion on when we expect our proposed algorithms to fail with a focus on guiding practical application. In particular, we will discuss what our theory shows about the difficulty of RCA in settings where the causal graph is very large (as note that both the bounds in Theorem 3.9 and Theorem 3.10 become weaker for larger $n$, though note as well that this challenge is not unique to our algorithms), and when the sample size for the normal period is low. Note that in Subsection 3.5 and Appendix D we discuss one particularly important case where the polytree assumption is violated and there is strong confounding, and why in practice it may not pose a significant problem. We will move some of the discussion from Appendix D into the main text as there we show that we expect SCORE ORDERING to fail only rarely when the polytree assumption is violated (at least in the linear setting).\n\n> Addressing questions\n\n1. Please see our reply to point 1 in \"Addressing weaknesses\" above\n2. Please see our reply to point 3 in \"Addressing weaknesses\" above\n3. Please see our reply to point 1 \"Addressing weaknesses\" above\n\n> Addressing limitations\n\n1. This is a very important point, I hope that you will feel that our reply to point 3 in \"Addressing weaknesses\" above already largely  encompasses the issue you raise here. Nonetheless, let us provide some further information on two points. First, the polytree assumption: the polytree assumption is indeed restrictive ). In subsection 3.5 and Appendix D we give some justification for the application of our algorithms even in cases where this assumption is violated, and in all experiments we do not restrict the causal graph to be a polytree, and both of our algorithms show competitive performance. Note also that the only other Root Cause Analysis approach which operates in the setting we study (Li et al, 2025, “Root cause discovery via permutations and Cholesky decomposition”), the method we refer to as “Cholesky” in the Experiments section, assumes that the causal model is linear, while our approach does not. As such, we still believe that our work is an important contribution to the current state of root cause analysis research, despite this assumption. Regarding the single fault setting: if this is referring to our assumption that there is only a single root cause, in fact our theory readily generalises to the case where there are multiple. Olease see the detailed reply we gave to reviewer D5Fu above concerning this (and sorry for sending you to one of our replies to another reviewer, they raised the same point, and we are running out of characters!).\n\n2. Thank you for raising the point of sample-complexity guidance. Given as low sample sizes in the normal period can pose issues for use of estimated IT anomaly scores in practice, it would certainly be worth providing some guidance on this. We propose including the following additional result in the appendix, with proof: if we use at least $k =\\frac{3 e^{S_{\\max}}}{\\delta^2} \\log\\left(\\frac{2n}{\\alpha}\\right)$ samples, then the estimated anomaly scores $\\hat{S}(x_i)$ satisfy $P\\left(|\\hat{S}(x_i) - S(x_i)| < \\delta \\right) \\quad \\forall i \\in \\{1, \\dots, n\\}$ with probability at least $1 - \\alpha$, where $S_{\\max} := \\max_i S(x_i)$, and $S(x_i)$ and $\\hat{S}(x_i)$ are as defined in Equations 4 and 5 in the main text. The result follows from applying the (multiplicative form of) the Chernoff bound for small $\\delta$, the full proof of which we will provide in the appendix."}]

Author rebuttal:

Meta-review: This paper addresses the problem of root cause analysis (RCA) in the single-sample setting, introducing two efficient methods based on information-theoretic anomaly scores: Smooth Traversal (for known polytrees) and Score Ordering (for unknown graphs). The theoretical development is solid, with proofs and guarantees under specific assumptions, and the algorithms are simple yet competitive with more complex baselines.

Reviewers highlighted the novelty of the approach, the clarity of the theoretical contributions, and the practical relevance of studying RCA with limited data. Concerns focused mainly on the restrictiveness of the polytree assumption, the limited empirical evaluation on diverse real-world settings, the need for clearer exposition and broader comparisons, and insufficient literature review (some recent works in this direction were not discussed). The authors’ rebuttal addressed many of these points, clarifying assumptions, promising expanded experiments, and strengthening the discussion of limitations. Several reviewers increased their scores after the discussion.

Overall, while some limitations remain, the paper makes a timely and meaningful contribution to RCA research. I recommend Accept, as the theoretical insights and methodological simplicity outweigh the concerns, and the paper is likely to stimulate further work in this area.
Decision: Accept (poster)