Conformal Changepoint Localization and Root Cause Analysis with Corrupted Observations

Determining when a system’s behavior changes, and which component is the root cause, is a recurring and often safety-critical task across engineering. In telecommunications, abrupt shifts in traffic volume or flow statistics signal congestion, equipment failures, or intrusions, and detecting and localizing these shifts underpins network management, security monitoring, and the lifecycle of AI-based applications [1, 24, 31, 37]. In cybersecurity, a large class of intrusion-detection tasks is naturally cast as changepoint detection, where a denial-of-service attack or a compromised host manifests as an abrupt change in packet-rate or connection statistics [45]. In robotics, fault detection and isolation must determine both the onset time of a sensor or actuator fault and the specific faulty component, so that a controller can react before the fault propagates through the platform [19]. In multi-agent and distributed systems, from robot swarms to microservice architectures, a fault in a single agent or service can cascade through the collective, and the diagnostic problem is to detect the anomaly and trace it back to the agent or service that triggered it [39, 55, 5]. In all of these domains, the changepoint time is a proxy for the onset of a fault, and the root cause is the component whose change occurred first.

A defining feature of these applications is that the output of a changepoint or root-cause procedure drives a potentially costly downstream action: rerouting traffic, quarantining a host, halting a robot, or isolating a microservice. A single point estimate, reported without any statement of confidence, is therefore of limited value, because an operator cannot tell whether to trust it. Recent work [21] has shown that, for a risk-averse decision maker, it is optimal to adopt decisions that maximize the given utility function for a worst-case outcome consistent with the observations. Specifically, the appropriate interface between uncertainty quantification and decision making is a set of outcomes that provably contains the true one with probability at least $1-\alpha$, with probability $\alpha$ dictating the level of risk tolerance.

Returning a set of plausible changepoints or root causes thus allows a decision maker to control its risk by selecting actions that are robust across all elements of the set. For example, an operator may inspect all the plausible causes of a failure in telecommunication networks on the basis of a set prediction. However, in order for this process to be efficient, it is of critical importance that the predicted set be as small as possible.

Real observations are routinely contaminated by outliers, sensor faults, packet losses, or adversarial perturbations. Contamination can obscure the true change signal and true root cause of a change. Accordingly, even procedures whose coverage guarantee remains valid under contamination, such as conformal changepoint localization (CONCH) [14] and conformal root cause analysis (CROC) [15], can be forced to return confidence sets so large as to be uninformative. The goal of this paper is to introduce a methodology that, building on CONCH and CROC, preserves validity under contamination while restoring informativeness of set predictors for both single-stream changepoint localization and multi-stream root cause analysis.

This paper develops offline changepoint detection and root cause analysis methods that remain valid and efficient even when observations are contaminated under Huber’s model. Our contributions are as follows.

• •

  Weighted conformal changepoint localization. We propose weighted CONCH (W-CONCH), which builds on CONCH [14] by incorporating a weighting mechanism that downweights observations that are likely to be corrupted. W-CONCH hinges on a novel changepoint plausibility (CPP) score that is derived from a bound on the contaminated marginal likelihood, and is instantiated through an efficient classifier-based implementation.

• •

  Uncertainty-based and meta-learned weights. We introduce uncertainty-based weighting rules driven by classifier second-order uncertainty signals obtained from EDL or Bayesian learning. We also present a meta-learned variant, MW-CONCH, that directly optimizes a differentiable surrogate of the confidence set size, reducing dependence on hyperparameters.

• •

  Extension to root cause analysis. We extend the same weighting principle to multi-stream root-cause localization building on CROC [15]. This yields weighted CROC (W-CROC) and its meta-learned variant MW-CROC, which preserve the distribution-free coverage guarantee of CROC while sharpening the root-cause confidence set.

• •

  Empirical validation. On image-based changepoint and root-cause benchmarks, along with a real-world changepoint benchmark, we show that uncertainty-based weighting substantially reduces confidence set size under contamination while retaining empirical coverage, with meta-learning achieving performance comparable to oracle baselines that use the true contamination indicators to define the weights.

The remainder of the paper is organized as follows. Section II formalizes the contaminated changepoint localization and root-cause localization problems. Section III reviews CONCH and establishes its coverage guarantee under contaminated observations. Section IV presents W-CONCH, including the weighted changepoint-plausibility score, the uncertainty-based weighting rules, and the meta-learning procedure. Section V extends the weighting strategy to the multi-stream CROC framework. Section VI reports the experimental results, and the appendices contain proofs, implementation details, and additional experiments.

As illustrated in Fig. 1, let $\mathcal{X}$ denote the observation space, and let $\widetilde{\mathbf{X}}=(\widetilde{X}_{1},\dots,\widetilde{X}_{n})\in\mathcal{X}^{n}$ denote the clean data sequence. We assume that there exists a true changepoint $\xi\in\{1,\dots,n-1\}$ at which the distribution of the clean data $\widetilde{\mathbf{X}}$ changes. As in [14], we impose no parametric assumptions on the pre- and post-change distributions, requiring only the following exchangeability condition.

Let $Y_{1},\ldots,Y_{n}\overset{i.i.d.}{\sim}\mathrm{Bernoulli}(\varepsilon)$ be independent and identically distributed (i.i.d.) contamination indicators independent of the clean data $\widetilde{\mathbf{X}}$ for some corruption probability $\varepsilon\in(0,1)$. Furthermore, let $Z_{1},\dots,Z_{n}\overset{i.i.d.}{\sim}Q$ denote independent draws from a contamination distribution $Q$. Following Huber’s contamination model [17], each sample in the sequence of clean observations $\widetilde{\mathbf{X}}=(\widetilde{X}_{1},\ldots,\widetilde{X}_{n})$ is independently corrupted with probability $\varepsilon$, yielding the observation

Accordingly, with probability $1-\varepsilon$, the observed sample $X_{i}$ equals the clean sample $\widetilde{X}_{i}$, while with probability $\varepsilon$, the observed sample $X_{i}$ is given by the noisy sample $Z_{i}\sim Q$.

Given the noisy observed sequence $\mathbf{X}$ in (2), we aim to construct a confidence set $\mathcal{C}_{\alpha}(\mathbf{X})\subseteq\{1,\dots,n-1\}$ for the unknown changepoint $\xi$ that satisfies the finite-sample coverage guarantee

at a user-specified level $\alpha\in(0,1)$, while reducing as much as possible the set size $|\mathcal{C}_{\alpha}(\mathbf{X})|$. This problem is studied in Section III and Section IV.

As illustrated in Fig. 2, consider now $D$ data streams, each of length $n$. For stream $d\in\{1,\ldots,D\}$, let $\widetilde{\mathbf{X}}_{d}=(\widetilde{X}_{d,1},\ldots,\widetilde{X}_{d,n})$ denote the clean sequence, and let $\xi_{d}\in\{1,\ldots,n-1\}$ denote its changepoint. The vector of stream-wise changepoints is denoted by $\boldsymbol{\xi}=(\xi_{1},\ldots,\xi_{D})$. The root-cause index is defined as the index of the stream whose changepoint occurs first, i.e.,

where the minimizer is assumed to be unique. The rationale for this definition is that the first changepoint may be the root cause of the changes in the other sequences [15].

Generalizing the single-stream setting, following [15], we assume that, for each stream $d$ the clean sequence $\widetilde{\mathbf{X}}_{d}$ satisfies split exchangeability at its true changepoint $\xi_{d}$.

Each stream is corrupted independently through a stream-wise Huber contamination mechanism. Accordingly, let $Y_{d,1},\ldots,Y_{d,n}\overset{i.i.d.}{\sim}\mathrm{Bernoulli}(\varepsilon_{d})$ denote the contamination indicators for observation $i$ in stream $d$, and let $Z_{d,1},\ldots,Z_{d,n}\overset{i.i.d.}{\sim}Q_{d}$ denote an independent draw from a stream-specific contamination distribution $Q_{d}$. The $d$-th observed sequence is given by

for observation index $i=1,\ldots,n$ and stream index $d=1,\ldots,D$.

Let $\mathbf{X}=(\mathbf{X}_{1},\ldots,\mathbf{X}_{D})$ denote the collection of all observed streams. The goal of root cause analysis is to construct a confidence set $\mathcal{K}_{\alpha}(\mathbf{X})\subseteq\{1,\ldots,D\}$ for the unknown root-cause index $d^{\star}$ such that it includes the true index $d^{\star}$ in (4) with probability no smaller than the user-defined level $1-\alpha$, i.e.,

The root-cause localization problem is studied in Sec. V.

For each candidate changepoint $t\in\{1,\dots,n-1\}$, CONCH [14] evaluates a CPP score $S_{t}(\mathbf{X})$. This measures how likely time index $t$ is to be the true changepoint, with larger values indicating stronger evidence in favor of candidate $t$. The CPP score is treated here as fixed and arbitrary, and we will discuss the optimization of the CPP score in the next section.

Let $\Pi_{t}$ denote the set of permutations $\pi_{0,t}(\cdot)$ and $\pi_{1,t}(\cdot)$ that operate on the indices $\{1,\dots,t\}$ and $\{t+1,\dots,n\}$, respectively, as in Assumption 1. Furthermore, denote as $\pi_{t}(\mathbf{X})$ the permuted sequence $\big(X_{\pi_{0,t}(1)},\ldots,X_{\pi_{0,t}(t)},\allowbreak X_{\pi_{1,t}(t+1)},\ldots,X_{\pi_{1,t}(n)}\big)$ for some pair of permutations $\pi_{t}=(\pi_{0,t},\pi_{1,t})$. The conformal $p$-value for candidate changepoint $t$ is defined as the fraction of permutations $\pi_{t}\in\Pi_{t}$ for which the CPP score $S_{t}(\pi_{t}(\mathbf{X}))$ does not exceed the actual CPP score $S_{t}(\mathbf{X})$:

Intuitively, the statistic $p_{t}(\mathbf{X})$ in (8) tends to be large if the CPP score $S_{t}(\mathbf{X})$ is large, and thus there is evidence for $t$ being the true changepoint.

In practice, when the number of data points $n$ is sufficiently large, enumerating all the split permutations in set ${\Pi}_{t}$ is computationally infeasible. In this case, a Monte Carlo (MC) variant of CONCH, referred to as CONCH-MC, replaces the full average over set $\Pi_{t}$ in (8) with an average over randomly sampled split permutations.

The conformal $p$-value (8), and its MC version, are valid $p$-values for the null hypothesis $H_{0}:\xi=t$ that the true changepoint $\xi$ equals $t$. Accordingly, given a miscoverage level $\alpha\in(0,1)$, the changepoint confidence set is obtained by inverting the test with null hypothesis $H_{0}:\xi=t$ [32], i.e., by retaining all candidates whose $p$-values exceed the level $\alpha$:

In other words, the confidence set retains all candidate changepoints that cannot be rejected by the split-permutation test with $p$-value (8) at level $\alpha$.

Reference [14] shows that the CONCH set (9) satisfies the marginal coverage guarantee (3) as long as the sequence $\mathbf{X}$ is split-exchangeable at the true changepoint $\xi$. The following makes it possible to extend the coverage property also to the noisy observations (2) under Assumption 1, which assumes split-exchangeability only for the clean sequence $\widetilde{\mathbf{X}}$.

This result has the following immediate consequence.

Lemma 2 ensures that the CONCH set (9) meets the coverage requirement in (3) regardless of the contamination level $\varepsilon$. However, unless the CPP score $S_{t}(X)$ is properly designed, contaminated observations can obscure the changepoint signal and inflate the confidence set (see Fig. 1). We address this efficiency issue by introducing novel CPP scores in the next section.

In this section, we consider a simplified oracle-based setting in order to facilitate the derivation of an optimal CPP score under contamination. To this end, following [14], we specialize the data model in Sec. II to a standard i.i.d. changepoint model with known probability distribution [20, 30, 6].

As discussed in Sec. IV-A, the weight $w_{j}(x)$ used in the CPP score (14) or (18) should ideally capture the true probability that a sample $X\sim g_{j}(x)$ is clean. To approximate this probability, which depends on the unknown distribution (13), we propose to use classification uncertainty as a proxy. The rationale for this choice is that a classifier model $\hat{p}(j\mid x)$ trained on clean data should ideally be confident on clean in-distribution samples and uncertain on contaminated ones [16, 26]. With this approach, low-uncertainty observations $X_{i}$ receive larger weights, while high-uncertainty observations receive smaller weights.

To elaborate, as in Sec. IV-A3, consider a classifier $\hat{p}(j\mid x)$ pre-trained to distinguish between clean samples from the pre-change density $f_{0}(x)$, labeled with $j=0$ and the post-change density $f_{1}(x)$, labeled as $j=1$. In addition to the class posterior scores $\{\hat{p}(j\mid x)\}_{j=0,1}$, which are used to construct the classifier-based CPP score (18), we assume that the classifier provides an uncertainty signal

for some function $h:\mathcal{X}\to\mathbb{R}_{\geq 0}$, where larger values of $M_{i}$ indicate higher classification uncertainty. For example, the function $h(\cdot)$ can be obtained from an evidential classifier, which uses the parameters of a predictive Beta distribution to quantify second-order uncertainty [35], i.e., uncertainty about the predictive distribution, or using Bayesian methods, such as MC dropout [9], which estimate such uncertainty via ensembling [23, 38].

A natural choice is to assign weight $1$ to observations below an uncertainty threshold $\kappa_{j}$ and weight $0$ to those above, yielding the hard thresholding rule

for $j=0,1$. A smoother alternative replaces the hard threshold with a sigmoid function, yielding the soft weighting rule

where $\sigma(\cdot)$ is the sigmoid function and hyperparameter $\lambda$ controls the sharpness of the transition. As $\lambda\to 0$, the soft rule recovers the hard thresholding rule in (20).

The thresholds $\kappa_{j}$ for $j=0,1$ in (20) should ideally capture the transition between typical uncertainty signals for clean samples and for corrupted samples on either side of the changepoint. Accordingly, we propose to use side-specific empirical quantiles of the uncertainty signals. Formally, for a candidate changepoint $t$ and a quantile hyperparameter $\beta\in[0,1]$, we set

where $Q_{1-\beta}(\mathcal{S})$ returns the $\lfloor(1-\beta)|\mathcal{S}|\rfloor$ smallest element in set $\mathcal{S}$. The hyperparameter $\beta$ controls should ideally match the expected fraction $\varepsilon$ of contaminated observations. Based on this, we recommend setting hyperparameter $\beta$ to one’s best conservative estimate of the contamination probability $\varepsilon$.

Overall, specializing the CONCH set (9), the W-CONCH set is defined as follows.

The following proposition summarizes the properties of the W-CONCH set (23).

The W-CONCH set (23) in Sec. IV-B requires choosing the quantile hyperparameter $\beta$, as well as the threshold hyperparameter $\lambda$. As discussed in the previous subsection, when the contamination level $\varepsilon$ is known, the hyperparameter $\beta$ can be naturally set to $\varepsilon$, but a reasonable estimate of the probability $\varepsilon$ may not be available. Moreover, a pretrained uncertainty estimator $h(x)$ may not necessarily produce scores $M_{i}$ in (19) that are well aligned with the objective of minimizing the average set size $|\mathcal{C}_{\alpha}^{w}(\mathbf{X})|$. We address both issues by introducing a meta-learning strategy that optimizes a task-adapted uncertainty estimator from a collection of contaminated changepoint tasks, so that the induced weights directly minimize the size objective $|\mathcal{C}_{\alpha}^{w}(\mathbf{X})|$. We refer to this meta-learned variant of W-CONCH as MW-CONCH. Fig. 3 illustrates the overall pipeline of MW-CONCH.

To start, MW-CONCH selects a parameterized uncertainty estimator $h(\cdot;\theta):\mathcal{X}\to\mathbb{R}_{\geq 0}$ with trainable parameters $\theta$, replacing the pretrained model $h$ in Sec. IV-B. For example, the model $h(\cdot;\theta)$ may be a neural network trained via EDL [35]. EDL places a Dirichlet prior $\text{Dir}(\boldsymbol{e})$ over class probabilities and an uncertainty score $h(X_{i};\theta)=J/\sum_{j=1}^{J}e_{j}$, where $J$ is the number of classes and $\boldsymbol{e}=g(X_{i};\theta)$ are the predicted concentration parameters. The goal is to optimize the parameter $\theta$ so as to minimize the average size of the confidence set $|\mathcal{C}_{\alpha}^{w}(\mathbf{X})|$.

To this end, we fix the distributions $f_{0}(\cdot)$ and $f_{1}(\cdot)$ of the clean data, and we assume to have access to data $\mathbf{X}^{k}=(X_{1}^{k},\ldots,X_{n}^{k})$ generated i.i.d. from some distribution satisfying Assumption 1 and following the contamination model (2) for some randomly drawn contamination level $\varepsilon_{\mathrm{tr}}\sim\mu$ from some distribution $\mu$. The training distribution $\mu$ is itself a design choice: it may concentrate on a single reference contamination level $\varepsilon_{\mathrm{tr}}$, which is referred to as fixed-$\varepsilon_{\mathrm{tr}}$ meta-learning, or it may spread mass over multiple levels, which is referred to as mixed-$\varepsilon_{\mathrm{tr}}$ meta-learning. The meta-training loss is the average confidence set size of the W-CONCH set (23) over the samples $\{\mathbf{X}^{k}\}_{k=1}^{K}$:

where we have made explicit the dependence of the W-CONCH set $\mathcal{C}_{\alpha;\theta}^{w}(\mathbf{X})$ on the parametric uncertainty score $h(\cdot;\theta)$.

The meta-learning loss in (25) is not directly differentiable and a smooth approximation is derived in Appendix A-F by following an approach similar to [28, 43]. MW-CONCH optimizes this differentiable objective via gradient descent.

When prior information is available on which candidate locations are more likely to be the true changepoint $\xi$, it can be used to further concentrate the confidence set. We encode the prior as weights $v_{1},\dots,v_{n-1}\geq 0$ over the candidate locations. The weights are normalized as $\sum_{t=1}^{n-1}v_{t}=n-1$, so that values $v_{t}>1$ correspond to locations deemed more likely than under a uniform prior. Unlike the weights $w_{0}(X_{i}),w_{1}(X_{i})$ in (14), which act on the observations, the prior weights $\{v_{t}\}_{t=1}^{n-1}$ act on the candidate locations, entering through the significance level used to test each candidate.

Specifically, following the level-allocation strategy of weighted hypothesis testing [10], each candidate $t$ is tested at the level

where $\alpha_{\max}\in[\alpha,1)$ bounds the level applied to any single location, yielding the prior-informed confidence set

with the $p$-value $p_{t}^{w}(\mathbf{X})$ computed as in (23). By (26), a priori likely locations are tested at smaller levels, and are thus harder to exclude, while unlikely locations are more easily discarded. Under a uniform prior, i.e., $v_{t}=1$ for all $t$, all levels reduce to $\alpha_{t}=\alpha$, recovering the W-CONCH set (23).

The parameter $\alpha_{\max}$ controls the influence of the prior. The worst-case bound $1-\alpha_{\max}$ in (28) protects against misspecification of the prior, with the choice $\alpha_{\max}=\alpha$ recovering the guarantee (24) of Proposition 2.

Unlike the single-stream setting studied in the previous section, the unknown changepoint is now a vector $\boldsymbol{\xi}=(\xi_{1},\ldots,\xi_{D})$, and the root-cause index $d^{\star}$ in (7) is determined by the stream with the earliest changepoint. Let $\mathbf{t}=(t_{1},\ldots,t_{D})$ be a candidate changepoint configuration in a feasible set $\mathcal{R}$. The set $\mathcal{R}$ encodes prior structural constraints on the changepoints that may be a priori known to the detector. For instance, set $\mathcal{R}$ may consist of configurations in which a single stream changes first, i.e., $\mathcal{R}=\{(t_{1},\ldots,t_{D}):\exists d\in\{1,\ldots,D\}\ \text{such that}\ t_{d}<t_{m},\ \forall m\neq d\}$. For each candidate configuration $\mathbf{t}\in\mathcal{R}$, CROC evaluates a CPP score $S_{\mathbf{t}}(\mathbf{X})$ that measures the plausibility of $\mathbf{t}$ being the true changepoint configuration.

To calibrate this score, CROC applies split permutations within each stream $d$ using the candidate changepoint $t_{d}$. Let $\Pi_{\mathbf{t}}$ denote the corresponding split-permutation group, where each stream $d$ is permuted only within its candidate pre- and post-change segments determined by candidate $t_{d}$. The configuration-level conformal $p$-value is defined as

In practice, the average in (29) can be approximated using MC split permutations as explained in Sec. III-A.

To obtain a confidence set for the root-cause index, CROC aggregates the configuration-level $p$-values over all configurations that are consistent with each candidate root stream. To elaborate, for each $d\in\{1,\ldots,D\}$, define the set $\mathcal{I}_{d}=\{\mathbf{t}\in\mathcal{R}:t_{d}<t_{m}\text{ for all }m\neq d\},$ which contains all feasible configurations under which stream $d$ is the root-cause stream. The root-cause $p$-value for stream $d$ is then computed by taking the maximum over all feasible configurations in which stream $d$ changes first across all other streams, i.e.,

Then, stream $d$ is included in the confidence set $\mathcal{K}_{\alpha}(\mathbf{X})$ if at least one feasible configuration in which stream $d$ changes first is not rejected. Formally, given a miscoverage level $\alpha\in(0,1)$, the CROC confidence set for the root-cause index is

W-CROC specializes CROC by replacing the CPP score with the weighted classifier-based score developed in Sec. IV, in order to account for the contaminated observations in (6). Assume access to a pre-trained classifier for pre-change and post-change samples for each stream $d$, so that a log-posterior ratio $\Delta_{d,i}$, as in (15), can be computed for each stream $d$.

The weights in Definition 4 can be constructed using the hard or soft uncertainty-based weighting rules introduced in Sec. IV-B, or learned through the meta-learning procedure described in Sec. IV-D. When the uncertainty model is optimized via the meta-learning procedure, we refer to the resulting method as meta-learned weighted CROC (MW-CROC). The corresponding differentiable training objective and optimization procedure are summarized in Algorithm 1 in Appendix A-F.

When prior information is available on which streams are more likely to be the root cause $d^{\star}$, it can be incorporated via the level-allocation strategy described in Sec. IV-E. The prior is encoded as weights $v_{1},\dots,v_{D}\geq 0$ over the candidate streams, which are normalized as $\sum_{d=1}^{D}v_{d}=D$, so that values $v_{d}>1$ correspond to streams deemed more likely than under a uniform prior.

As in (26), each stream $d$ is tested at the level

with $\alpha_{\max}\in[\alpha,1)$, yielding the prior-informed root-cause confidence set

where the root-cause $p$-value $p_{(d)}$ in (30) is computed with the weighted score (32).

By (35), a priori likely streams are tested at smaller levels, and are thus harder to exclude, while unlikely streams are more easily discarded. Under a uniform prior, i.e., $v_{d}=1$ for all $d$, all levels reduce to $\alpha_{d}=\alpha$, recovering the W-CROC set (31), and the role of $\alpha_{\max}$ is as discussed in Sec. IV-E.