Thank you for your kind words and appreciation of our work! We are delighted that our code has been helpful.

1 (a) OOD Problem

Any input lying outside the training distribution is generally considered OOD. Since characterizing the training probability distribution is challenging, we can loosely define a node $X_i$ as taking an OOD value when its Z-Score is significantly high. The Z-Score measures how many standard deviations a sample lies from its mean. For example, the Petshop dataset by default declares values that are five standard deviations away from the mean as OOD.

1 (b) Illustrative Figure for In-Distribution and OOD Scenarios

We request the reviewer to refer to Figure 1 in the paper. We have updated the caption to explicitly mention the OOD scenario. Additionally, we have introduced a new Figure 2 in Section 3 that illustrates the RCD pipeline of IDI. We would be happy to incorporate further suggestions and answer any follow-up questions.

Q2: Details of the Oracle SCM

Please note that IDI only assumes knowledge of the dependency graph aka causal graph between nodes, and not the SCM.

For the Petshop dataset, we do not know the Oracle SCM. However, for our synthetic datasets, we constructed several types of Oracle SCMs. Detailed explanations of how these SCMs were designed are included in Appendix C.2 in the revised manuscript.

IDI trains the SCM using samples from the training data. Training the SCM involves fitting $n$ regression functions, one for each node. The second block in our new Figure 2 illustrates the SCM training process.

Q3: CIRCA description has minor issues

The authors of CIRCA made a very valuable observation in their paper that in RCD test cases, a root cause node drives its descendants to take on anomalous or OOD values. This insight led them to develop the descendant adjustment technique as an effective way to prevent predicting descendants of the root cause node as root causes. We leveraged this observation to support our claim that this phenomenon results in large $tvd$ terms in the CF bound in our theory. Therefore, the contributions of CIRCA complement our work. However, as noted by reviewer 7kui, this detail might be considered a distraction. In response, we have removed this comment from the remark in our revised manuscript.

Q4: Precise Overview of Algorithm and Pipeline Figure

In the revised draft, we have significantly condensed the methods section. Additionally, we included Figure 2 to provide a visual illustration of the IDI pipeline. We request the reviewer to take a look and share further feedback.

Q5 (a) Petshop details

We have added these details in Appendix C.1

Q5 (b) Why are three test cases different?

We reported low, high, and temporal latency separately because the nature of anomalies injected for each category is distinct (refer Sec. C.1). Low latency test cases involved fewer requests compared to high latency and temporal ones, making root cause identification more challenging for the low latency cases. Causal anomaly methods, such as traversal, achieved perfect recall on temporal test cases that exhibit more prominent anomaly behavior. To emphasize the efficacy of IDI in challenging low latency test cases, we presented the results separately.

Q6 Violations of Assumption 1

Our method, IDI, relies on this assumption to correctly identify root causes in multiple root cause test cases. Therefore, we evaluated its effectiveness when the assumption is violated. If the reviewer feels that this experiment is a distraction, we are open to moving it to the appendix.

Q7: SAGE

This paper is highly relevant to our work, and we sincerely thank the reviewer for pointing it out. SAGE is a counterfactual causal fix approach where the authors train CVAEs for each node during SCM training. To assess the fix condition, the method infers the posterior distribution over the exogenous variables $\epsilon$s (note that SAGE uses the notation $Z$ to denote the $\epsilon$) by conditioning the CVAE encoder on the root cause test features. As noted by CIRCA and other prior works, test samples in RCD often contain many anomalous values. Consequently, SAGE also incurs OOD evaluations of the SCM, unlike our approach, IDI. Unfortunately, we could not find the code and were unable to include a comparison with this baseline. However, we have cited and discussed it at line 122 in our related work section.

Thank you so much for appreciating our experiments and for providing a thorough and rigorous review of our work. We enjoyed writing the rebuttal.

Writing enhancement

We included examples for cloud KPIs in the intro. Thanks for this suggestion.

Weaknesses

We grouped answers for several questions here.

Q1,2: Novelty and Pre-existing Knowledge

We appreciate the reviewer’s acknowledgment of our theoretical contributions. In addition to the theoretical analysis, our proposed algorithm’s novelty lies in how we sequence the evaluation of the anomaly and fix conditions so as to avoid OOD estimates. The algorithm may seem simple in retrospect, but we explored several variants before finally arriving at the IDI algorithm, and precisely characterizing the condition under which it works. We are aware of no prior work on RCA that ensures robustness by avoiding OOD probing in the setting of multiple root causes and single cause per path. The robustness of IDI manifests in the consistently better results we obtain under diverse settings of complexity of SCM, variance of exogenous noise, and training set size. We request the reviewer to refer to Sec. E in the Appendix added during rebuttal for a fine-grained empirical analysis. Now, we answer in detail:

Pre-existing Knowledge: It is well-known that estimating counterfactuals (CFs) from observational samples often encounter impossibility results. In our setup, we assume the causal graph is available along with observational data, enabling CF estimation. Prior methods like DeepSCM [1] and Recourse under Imperfect Causal Knowledge [2] have demonstrated success in such scenarios. Hence, literature in Root Cause Diagnosis (RCD) widely regards counterfactual estimation as the correct approach to identify root causes [refer CF Attribution, [3]].

Novelty: Given that CF-based methods dominate the causal RCD literature, our findings are significant and can shift the field towards intervention-based RCD methods. The only work we found that acknowledges this OOD challenge is TOCA. Our work complements TOCA by providing a more detailed analysis, attributing the issue to the abduction step (lines 79–85). However, TOCA’s procedure to assess the fix condition performed poorly in our experiments—a limitation also noted by its authors. Our key novelty thus lies in designing an RCD algorithm that works exclusively with interventions, which is challenging given RCD's sensitivity to OOD estimation. Even algorithms that appear similar (e.g., IDI, TOCA both using interventions) can exhibit vastly different performance, as our results demonstrate (Tables 1, 2). Our algorithm is accurate and efficient, which is central to our contribution.

Furthermore, our theoretical results stem from how we characterize the root cause distribution (Definition 1). Unlike prior works (e.g., CF Attribution,[3]) that define root causes using counterfactual contributions, we adopt a probabilistic approach. This approach clarifies several aspects in our RCD procedure. For example:

• Why sampling residual errors from the validation dataset is crucial (line 918).
• Why fix values must be drawn from conditional distributions (lines 810–822).

References

[1] Pawlowski et al., Deep structural causal models for tractable counterfactual inference, NeurIPS, 33, pp.857–869.
[2] Karimi et al., Algorithmic recourse under imperfect causal knowledge: a probabilistic approach, NeurIPS, 33, pp.265–277.
[3] Sharma et al., The counterfactual-Shapley value: Attributing change in system metrics, arXiv preprint, arXiv:2208.08399.

Q1 Abduction as a probability distribution

As mentioned in line 180 of our paper, counterfactuals are point estimates as there is no randomness involved in predicting them, unlike interventions where exogenous variables must be sampled. To draw a probabilistic sampling analogy, we can assume that the learned SCM contains probabilistic functions, such as when each $f_i$ is a Gaussian Process, making $f_i(Pa_{X_i})$ predict a probability distribution over $X_i$ (see [2] above, sec. 4 for an example. Note that the noise $u$ there corresponds to $\epsilon$ in our context). While prior work has shown that such approaches work well in typical CF estimation problem settings, we highlight that this design would also lead to OOD estimation issues in the RCD setup. This is because a root cause test sample could require the posterior over $X_i$ to be predicted from OOD parents. SAGE [4] explores CVAEs to train probabilistic $f_i$s. We request the reviewer to refer to our response to Q7 of reviewer ERJh for more details.

References

[4] Gan et. Al. Sage: practical and scalable ML-driven performance debugging in microservices. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 135-151).

Q6 (a) Recall values close to 1

This was true for Linear datasets because linear functions generalize well to anomalous distributions allowing for efficient inference of the fix condition. We did see a significant dip in the recall for the most complex of our SCMs – non-linear and non-invertible. Regarding Petshop, the temporal cases were easy for baselines (Traversal methods achieve 1) and IDI because they were simulated by injecting too many requests at the root cause node, making the root cause nodes statistically stand out in the test cases.

Q6 (b) Details of Datasets

We have included this in our revised manuscript at Sec C.

Q6 (c) Report the Std Deviation of Recall

We chose not to report the std deviation as our tables are already quite dense. Many prior RCD works, such as BARO (https://arxiv.org/pdf/2405.09330), TOCA, or CF Attribution also do not include error bars. Further, the trend between high-performing and low-performing methods was clearly visible in our tables. If the reviewer prefers, we are open to include them.

Q6 (d): Bias Preferring IDI in Dataset

First, we note that the petshop dataset was not created by us, and IDI performs best when compared across the state-of-the-art baselines. For the synthetic datasets that we created, we believe the only bias in our dataset stems from enforcing that the synthetic graph satisfies Assumption 1. We had also conducted an ablation study in Sec. 6.3 to assess the implications of this assumption. Otherwise, our synthetic functions $f_i$s use random MLPs which are more general. We provide all details on our datasets in Sec. C in our revised paper. Further, we have explicitly added limitations in Sec. 7.

Q7 (a) Case studies for low variance

Please refer Q5 above.

Q7 (b) typically small in practice

We believe that this statement is in general true for a dataset with rich predictive features. However, we agree that this is unverifiable given training data. For example, in Petshop with latent exogenous variables and unknown Oracle SCM, we cannot comment on the variance($\epsilon$). Therefore, this phrase becomes subjective, and so we removed it.

Q8 Reduce verbosity

We made several passes over the paper to trim down the redundant points and added limitations.

Q9

• Theorem numbers: We apologize for this. The theorem labels were inadvertently carried over to the statements in the appendix. We corrected this now. Thanks for pointing it out.
• Notations We fixed the symbol $D^{trn}$ and expanded IDI in abstract.

Q10 Prior methods Sec 3.3

The Hierarchical RCD, CF Attribution, and other traversal approaches support this claim. However, we found this line to be redundant and removed it.

Q11 remark on page 6

We have revised this remark and removed the reference to CIRCA. Thanks for this suggestion.

Q12 Z-Score

We have included in our revised paper.

Questions

Q1 Auto-regressively

Apologies for the confusion. We should not have used that phrase. In our synthetic data, we generated i.i.d. samples by forward sampling in topological order. We have corrected this throughout the paper.

Q2 Is Additive noise only way for inverting $\epsilon$

The use of additive noise is indeed the most popular choice, and so we adopted it in our work. However, more sophisticated models exist. As an example, the PostNonLinear (PNL) model [5] provides an alternative. In this model, each $X_i = g(f(\text{Pa}_i) + \epsilon_i)$, where $g$ is a complex but invertible function, and $f$ is arbitrary.

[5] Zhang et. al. On the identifiability of the post-nonlinear causal model. arXiv:1205.2599. 2012 May 9.

Q3 fixes to any subset of

We have enhanced the clarity in our revised manuscript.

Q4 Disrupted mechanism/abnormal $\epsilon_j$

Yes, the reviewer’s understanding is correct. For a root cause $X_j$, since the parents are not anomalous, the OOD nature of $X_j$ can only stem from an abnormal $\epsilon_j$.

Q5 Important Question

We address this question for additive noise models:

• Interventions: No, interventions will not converge to the true counterfactual. In the worst case, the estimation error would plateau at the standard deviation of $\epsilon$ (refer Appendix E).
• Counterfactuals: Yes, under ideal conditions. When the learned $\hat{f_i}$ is perfect—e.g., in the limit of infinite training data and when $\hat{f_i}$ consistently estimates the true $f_i$—the counterfactual estimates converge to the true values. Thank you for this insightful question; we have incorporated this as a limitation in the revised manuscript.

Q6 Cloud KPIs are usually positive

Cloud KPIs are typically positive as they measure performance and reliability, including response time, query latency, throughput, CPU utilization, etc. We have added the reference to our manuscript. Notably, IDI does not need positivity of KPI. We explored using Gaussian noise in the toy experiment conducted during rebuttal, as discussed in Q6.

Dear Reviewer,

Thanks very much for your time and effort in reviewing our work. Please see below for the questions raised during the rebuttal.

Empirical validation of Paper’s Hypothesis

We reiterate, as stated in line 77 of our paper, that if the oracle values of $\epsilon$ are available, counterfactuals (CFs) are the optimal choice for RCD. The linear experiments in our paper in Figures 6, 7, 8 exemplify this ideal scenario, since the estimated $\hat{f}_i$ converges to the true $f_i$ in the Oracle SCM. We have clearly highlighted this in our conclusion in Sec. 7 of our revised paper, emphasizing the limitation that CFs outperform interventions when the estimated SCM closely approximates the true SCM, i.e., $\hat{f}_i \approx f_i$.

Moreover, in our proof, if additional assumptions are made about the gap between $f_i$ and $\hat{f}_i$ is small, the CF error analysis in Equations 10 and 11 could achieve much tighter bounds. In the absence of such knowledge, the goal of Theorem is to provide bounds for more general scenarios.

Additionally, we want to emphasize that the linear experiments presented in our work do not conclusively suggest that CFs will always outperform interventions in all linear settings. It is possible to construct examples where the Oracle SCM uses linear functions, yet even with extensive training data, the estimates $\hat{f}_i$ may exhibit low error in the training regime but high error when applied to the abnormal root cause regime. One such case is multicollinearity, which we explain in more detail below:

To explicitly show the dependence of the CF error on the gap between the prediction errors during training regime and the anomalous root cause regime, we extended the four-variable toy linear dataset presented during the rebuttal as follows:

• The input features were expanded to six dimensions. The first three features, $X[:, 0:3]$, were sampled i.i.d. from a standard Gaussian as earlier. The remaining three features were made correlated with the first three as follows: $$$$

X[:, 4] = X[:, 1] + \mathcal{N}(0, \rho), \quad X[:, 5] = X[:, 2] + \mathcal{N}(0, \rho), \quad X[:, 6] = X[:, 3] + \mathcal{N}(0, \rho)

Here, $\mathcal{N}$ is Gaussian distribution, and $\rho$ -- its variance takes values in \{0.01, 0.1, 0.5, 1\}. When $\rho = 0.01$, the fourth column is heavily correlated with the first, while for $\rho = 1$, the correlation coefficient is less pronounced. - We considered low training size with 50 samples and high training size with 1000 samples to study the impact of such correlated features on the intervention and counterfactual errors. We worked with the very high variance setting var($\epsilon_4$)=5, where interventions demonstrated poor performance earlier. We have updated the anonymized repository with the notebook for this specific experiment. The notebook can be accessed at the following link: https://anonymous.4open.science/r/petshop-BB8A/limitation_linear.ipynb. The results (Section E.1, the new figures 6e, 6f) reveal the following: 1. For high training size and high variance settings: - First, observe that the validation error remains close to zero across all $\rho$ settings, but the root cause test error blows up in the abnormal regime for smaller $\rho$s. This elucidates that even linear functions can have high out of domain error. - In high training size case, we observed that when $\rho$ is small, interventions outperform CFs because multicollinearity induces high error in the abnormal root cause regime for CFs. - As $\rho$ increases (e.g., $\rho > 0.5$), the effects of multicollinearity diminish, and CFs regain their dominance over interventions. 2. For low training size across all $\rho$ values: - Interventions consistently outperformed CFs. CF error escalates to as high as $10^3$, while interventions remain robust with their error bounded by the standard deviation of $\epsilon$. Thus, our observations in the toy dataset align with our theoretical analysis. The findings are not contradictory but highlight the nuanced conditions under which CFs or interventions dominate. We appreciate the reviewer’s acknowledgement that in complex non-linear cases, IDI generally outperforms CFs. - **General Insights:** The central thesis of our work is that while there are specific scenarios where counterfactuals (CFs) outperform interventions—such as when the abducted values are accurately estimated and closely align with the oracle values (e.g., when $\hat{f}_i \approx f_i$)—these cases are exceptions rather than the norm. When consolidating the performance across the diverse SCMs examined in our study, interventions surely emerge as the superior approach for RCD compared to CFs.

Number of Nodes

The bounds in our theoretical results are not affected by the total number of nodes in the SCM. Instead, they are determined by the number of nodes in the paths between the root cause node and the target. This is because our bounds include $n-i$ in the exponent, where $n$ represents the total number of nodes in the chain graph, and $i$ is the position of the root cause node. Consequently, $n-i$ corresponds to the path length from the root cause node $i$ to the target node $n$. Thank you for this question—it highlights an important experiment to demonstrate how the depth of the anomalous root cause node impacts the estimates of CFs and interventions.

We report the errors in the estimated CF values and the estimated interventional values when compared to the true CF values at nodes located at different depths from the root cause node. These results are computed for an example test case using a non-linear invertible synthetic dataset. We compute the percentage reduction in error is defined as:

$$\text{Reduction} = \left(\frac{\text{CF Error} - \text{Int Error}}{\text{CF Error}}\right) \times 100$$

The table below presents the errors for CFs and interventions (int) against their depth from the root cause node, alongside the percentage reductions:

We observed similar trends across various test cases. As the depth from the root cause node increases, the CF estimates show greater errors. However, the interventional estimates demonstrate a significant advantage, maintaining lower errors.

Petshop

Is petshop a benchmark dataset from literature?

Yes, Petshop is a dataset recently introduced in [Hardt et al., 2023]. We did not create it. It contains root cause test cases created by manually injecting faults into a real-world micro service application. This dataset addresses a key research gap in other RCD datasets by making the underlying dependency graph publicly available, which serves as the causal graph.

Why petshop?

This dataset focuses on root cause analysis of real-world anomalies occurring on a deployed website called Petshop. The target node in this dataset where anomalies are triggered is PetSite—the front-end interface where users interact to browse for the pets displayed in the website. An anomaly is triggered at Petsite upon a violation of the service level objective (SLO), such as when the website's response time exceeds 200 microseconds. Root cause test cases were manually injected by selecting a node and issuing an abnormally high number of requests through that node. This surge in traffic from the selected root cause node ultimately triggers an SLO violation at the Petsite node.

The dataset includes three types of root cause test cases: Low, High, and Temporal latency. On average, the request rates were 485 requests per second for Low latency, 690 for High latency, and 571 for Temporal latency cases. In the High and Temporal latency cases, the root cause nodes deviated significantly from the request patterns observed during training, allowing baseline methods such as traversal to perform well. However, for the more challenging Low latency cases, where the statistical discrepancy of the root cause nodes between the training regime and the abnormal root cause regime is less pronounced, IDI demonstrated the best performance.

Oracle Causal Graph vs. Oracle SCM

While the Oracle causal graph is available in Petshop, the Oracle SCM remains unavailable since the true structural equations $f_i$ underlying the Oracle SCM are unknown. To the best of our knowledge, no prior work has explicitly defined the Oracle SCM. We argue that obtaining the exact Oracle SCM (i.e., the precise $f_i$ functions) is infeasible for any real-world dataset, and rather only observed samples can be recorded. Previous studies leveraging Petshop, such as [TOCA], have adopted a learning-based approach, approximating the Oracle SCM by training the structural equations $\hat{f_i}$ on the collected finite samples. Our work also followed this same methodology.

Minor Issue

We had different numbers to ensure the continuity of numbers in the Appendix. We have now updated the theorem numbers.

Thanks so much for appreciating the theoretical and experimental contributions of our work.

Q1 Complex presentation

We have revised the paper considering your feedback and the suggestions from other reviewers. Specifically, we have:

• Explicitly highlighted the OOD challenge in Fig. 1
• Trimmed down Sec. 5.
• Added the pipeline illustration in Fig. 2.
• Included a simple toy experiment in Appendix E to improve understanding. We also updated the anonymized repository with a detailed explanatory notebook: https://anonymous.4open.science/r/petshop-BB8A/limitation.ipynb.
• Explicitly highlighted the limitations in Sec. 7.

We hope these additions address the concerns. We are open to further feedback to enhance the paper.

Q2 Validation in diverse real-world datasets4

We could not perform this experiment because for real-world industrial datasets because their dependency graphs are usually considered proprietary. Further, prior works like BARO (https://arxiv.org/pdf/2405.09330) have noted that causal approaches like CIRCA fail due to the improper recovery of the causal graphs. So to focus on just the root cause prediction efficacy, we solely experimented with benchmarks containing dependency graphs.

Q3 Timing Analysis

We request the reviewer to refer to Q2 of reviewer hq7T. We have added a very detailed timing analysis in the Sec. D in the Appendix of the revised manuscript.

Q4 When is CF method preferred over IDI

As a short answer, when the underlying true SCM allows for identifiability of the exogenous variables. In the limit of training size, when the estimated structural equations in the learned SCM become perfect, the estimates provided by the counterfactual methods converge to the true counterfactual values. On the contrary, the error using interventional estimates considered by IDI would plateau at the standard deviation of the exogenous variables. We request the reviewer to refer to Appendix Sec. E, or the code in our notebook for a detailed explanation. We have added this as an explicit limitation in Sec. 7 in our revised manuscript. Thanks very much for this question.

Q5 Sensitivity to anomaly thresholds

We have added this experiment in Appendix F. We performed the sensitivity analysis on the Petshop dataset. Our observations include:

• Robustness Across Thresholds: IDI and other baselines mostly demonstrated robustness across a wide range of anomaly thresholds from 2 to 7.
• Degradation at Low Thresholds: IDI showed a slight performance degradation only at the lowest threshold of 2, highlighting sensitivity to overly lenient anomaly definitions.
• Tuning Challenges: Determining the optimal threshold requires abnormal root cause test samples during training, which are often unavailable. In such cases, domain expertise is crucial for specifying this hyperparameter.

Thank you very much for appreciating our work and providing positive feedback. We are happy to engage with you for any follow-up questions.

Q1 Comparison with MicroCause

Thank you for pointing us to this prior work. The referenced paper (MicroCause) addresses the challenge of learning causal graphs for microservices datasets. MicroCause highlights that conventional graph discovery methods such as the PC algorithm, struggle to recover the true causal graph in RCD settings. To address this, the authors introduced a more sophisticated PCTS algorithm for causal graph learning. However, once the graph is learned, MicroCause employs a random walk traversal approach for root cause identification. In comparison, since the main focus of our work is to analyze and develop an algorithm for root cause prediction, we assumed access to the true dependency graph of the components. Therefore, the causal graph learning algorithm of MicroCause is complementary to our approach. Their root cause identification algorithm is a variant of the traversal-based approaches discussed in our paper (Sec. 6). This paper can thus be categorized as part of the traversal-based family of approaches. We have cited and discussed this paper at lines 114, 376 in our revised manuscript. We report the comparison with Traversal methods run on the true causal graph for reference on the petshop dataset.

What is the computational overhead when a fault is associated with many anomalies?

We assessed the running time of all the baseline used in our work. Please see below for the results. We request the reviewer to also refer to Sec. D in Appendix for a detailed answer.

Running Time for Unique Root Causes

1. The Correlation and Causal Anomaly methods demonstrate the best performance in terms of running time.
2. Causal Fix approaches are bottlenecked by the need to learn the Structural Causal Model (SCM), with linear methods taking less time compared to non-linear ones due to the latter's reliance on gradient-based training.
3. Ours (CF) and Ours do not require Shapley value computations for predicting unique root causes, significantly reducing running time.
4. The CF Attribution method performs Shapley analysis across all nodes, making it the slowest method.

Table: Running time (in seconds) for datasets with unique root causes. "--" indicates that the baseline was not executed on the corresponding dataset due to incompatible assumptions.