Multi-model Online Conformal Prediction with Graph-Structured Feedback
Authors: Erfan Hajihashemi
Yanning Shen
Venue: Accepted by TMLR ()

Abstract: Online conformal prediction has demonstrated its capability to construct a prediction set for each incoming data point that covers the true label with a predetermined probability. To cope with potential distribution shift, multi-model online conformal prediction has been introduced to select and leverage different models from a preselected candidate set. Along with the improved flexibility, the choice of the preselected set also brings challenges. A candidate set that includes a large number of models may increase the computational complexity. In addition, the inclusion of irrelevant models with poor performance may negatively impact the performance and lead to unnecessarily large prediction sets. To address these challenges, we propose a novel multi-model online conformal prediction algorithm that identifies a subset of effective models at each time step by collecting feedback from a bipartite graph, which is refined upon receiving new data. A model is then selected from this subset to construct the prediction set, resulting in reduced computational complexity and smaller prediction sets. Additionally, we demonstrate that using prediction set size as feedback, alongside model loss, can significantly improve efficiency by constructing smaller prediction sets while still satisfying the required coverage guarantee. The proposed algorithms are proven to ensure valid coverage and achieve sublinear regret. Experiments on real and synthetic datasets validate that the proposed methods construct smaller prediction sets and outperform existing multi-model online conformal prediction approaches.

Published in Transactions on Machine Learning Research (10/2025)
Multi-model Online Conformal Prediction with Graph-Structured Feedback
Erfan Hajihashemi
ehajihas@ruciccmm edu
Deportment of Electrical Engineering and Computer Science University of California, Irvine
Yanning Shen'
yanningss@uci.com edu
Deportment of Electrical Engineering and Computer Science University of California, Irvine
Reviewed on OpenReview: https: // openreview. net/ pormfo?mm? id= PuBugbissm
Abstract
Online conformal prediction has demonstrated its capability to construct a prediction set for each incoming data point that covers the truc label with predetermined probabil- ity. To cope with potential distribution shift, multi-model online conformal prediction has been introduced to select and leverage different models from a preselected candidate set. Along with the improved flexibility, the choice of the preselected set also brings challenges. candidate set that includes a large number of models may increase the computational complexity. In addition, the inclusion of irrelevant models with poor performance may neg- atively impact the performance and lead to unnccessarily large prediction sets. To address these challenges, we propose novel multi-model online conformal prediction algorithm that identifies a subset of effective models at each time step by collecting feedback from bi- partite graph, which is refined upon receiving new data. A model then selected from this subset to construct the prediction set, resulting in reduced computational complexity and smaller prediction sets. Additionally, we demonstrate that using prediction set size as feedback, alongside model loss, can significantly improve efficiency by constructing smaller prediction sets while still satisfying the required coverage guarantee. The proposod algo- rithms are proven to ensure valid coverage and achieve sublinear regret. Experiments on real and synthetic datasets validate that the proposed methods construct smaller prediction sets and outperform existing multi-model online conformal prediction approaches.
1 Introduction
Machine learning models are rapidly improving in providing accurate predictions; however, it remains chal- lenging to ensure that decisions inferred from these models reliable. To address this challenge, uncertainty quantification can be used lo ensure model reliability by providing interval predictions instead of point es- timates (Heskes
1996 Patel 1989) Reliable interval prediction is particularly important in safety-critical
applications such as autonomous driving (Doula et al. 2024 Dixit et al. 2023 and healthcare (Lu et al.
2022
Boger et al. 2025
Vazquez & Facelli 2022).
model-agnostic and distribution-fies uncertainty quantification framework that constructs prediction sets of candidate output values such that the true output is covered in the set with predefined probability (Vovk et al. 2005). Conventional conformal prediction algorithms achieve the desired coverage under the assumption of data exchangeability-ie..
Conformal prediction
sequence of random variables whose joint distribution remains invariant under any permutation of the indices (Balasubramanian et al.) 2014). The exchangeability assumption often fails to hold in practice particularly in online settings where data is
Corresponding author

---

Published in Transactions on Machine Learning Research (10/2025)
collected sequentially. Such violations can lead to failure to maintain the desired coverage. To address this, several lines of work have focused on online conformal prediction (Zaffran et al. 2022 Feldman et al. 2022). In the online conformal setting, a parameterized prediction set is constructed at each timestep. After observing the true label, the parameters are updated based on the algorithm's performance, such as whether the prediction set included the true label. Adaptive conformal prediction has also been rntuede,,, where prediction sets are constructed in a time-varying manner to cope with the challenges of online environments (Gibbs & Candès 2021). Even though adaptive conformal prediction algorithms can cover the true label with the desired probability, they may construct inefficient prediction sets (e.g., excessively large sets). The efficiency of conformal prediction algorithms depends on the underlying learning model, and a single model may not perform consistently well across all sequential data.
To address this issue, (Hajihashemi & Shen 2024 Gasparin & Ramdas 2024a proposed leveraging multiple learning models to provide diverse candidates for adaptive conformal prediction algorithms to select the ap- propriate model. However, their approaches are limited to a set of candidato models with good performance. The learning models used in their experiments are all high-perforning, which may not simulate real-world scenarios where lower-performin performing models are also present in the candidate set. Additionally, multi-model conformal prediction methods can suffer from high computational complexity when the number of candidate models is large, as it requires updating the adaptive conformal prediction parameters for each individual model. To address these limitations, we introduce a new multi-model online conformal prediction algorithm, which simulates the online model selection as graph-structured feedback. The proposed method dynamically selects a subset of effective learning models and prunes weak ones at each time step by constructing a graph. In addition, we propose an extension to the aforementioned algorithm, where the prediction set size of the effective models is used as feedback. This extension enables the construction of significantly smaller predic- tion sets while still achieving valid coverage of the true label, outperforming previously proposed multi-model conformal prediction approaches.
Related work: Conformal prediction is a powerful framework for uncertainty quantification that has been widely used to predict a set of candidate oulcomes for input data (Shaler & Vovk 2008 Vovk 2015 Pa-
padopoulos et al. 2002). The goal is to quantify the uncertainty of a given black- box machine learning model by constructing prediction set. Conformal prediction frameworks can be utilized on both classification Shi
et al. 2013 Romano et al.
2020
Ding et al. 2023) and regression (Romano et al. 2019 Boström et al. 2017
Papadopoulos et al.] 2011
lasks. Conformal prediction algorithms can be broadly categorized into split and 2023
In split conformal prediction, the training data is divided into two disjoint subsets: a proper training set and a calibration set. The proper training set is used to fit the point prediction model, while the calibration set is used to compute nonconformity scores (Oliveira et al. 2024p. In rastr full conformal prediction is significantly more computationally demanding, as it requires retraining or scoring the point prediction model for each test point and every possible candidate label (Angelopoulos et al. 2020).
full variants (Barber et al.
Hence, in this work, we only focus on split conformal prediction algorithms.
Employing standard conformal prediction in online environments, where the exchangeability assumption may be violated, does not achieve the desired coverage guarantee. To address this, (Gibbs & Candès 2021
introduced the use of a time-varying miscoverage probability. However, this approach has certain limitations
(e.g., the need to specify the learning rate in advance (Podkopaev et al. (024)). (Zaffran et al. 2022
Gibbs & Candès 2024) use expert learning techniques [Vovk] 1995 Cesa-Bianchi et al.
1997
Littlestone
& Warmuth 1994) to mitigate these limitations. (Lei & Candes 2021 Tibshirani et al.
Podkopaev & Ramdas 2021) utilized reweighting techniques to cope with changes in online settings. However, these
2019
methods often rely on some distributional assumptions. Despite achieving valid coverage guarantees, these methods may fail to construct efficient prediction sets that are both small and able to cover the true label. Some recent works propose using multiple learning models to enhance conformal prediction (Gasparin & Ramdas 2024a| b Yang & Kuchibhotla, 2025 Bhagwat et al. 2025 Hajihashemi & Shen 2024). Both (Yang & Kuchibhotla 2025 Bhagwat et al.] (025)) leverage multiple models in the full conformal prediction setting, which suffers from high computational cost. (Gasparin & Ramdas 2024a) proposes a majority-vote strategy
for aggregating conformal sets in the split conformal prediction setting. However, their method suffers from coverage loss and lacks a theoretical guarantee of achieving the desired 1 - coverage. (Hajihashemi & Shen,
2

---

Published in Transactions on Machine Learning Research (10/2025)
2024 proposed selecting a model from set of candidate models at each time step. This approach can incur high computational cost and reduced efficiency when the set includes poorly performing candidates.
Contributions. Overall, our contributions can be summarized as follows:
I) We introduce a novel multi-model online conformal prediction algorithm, Graph-struchured feedback Multimodel Ensemble Online Conformal Prediction (GMOCP), designed for online environments. At each time step, the algorithm selects a learning model to construct the prediction set from a subset of effective models identified using a graph structure.
II) An adaptive framework is proposed for generating the graph based on the performance of each learning model over previous time steps. It is proven that GMOCP achieves sublinear regret and guarantees valid coverage.
III) Experiments on real and synthetic datasets demonstrate the effectiveness of the GMOCP method in constructing more efficient prediction sets with lower computational complexity, while achieving a coverage probability closcly aligned with the target value.
2 Preliminaries
This section provides preliminaries on standard conformal prediction and adaptive conformal prediction. Given a learning model m and a set of historical data ((X,, Y)r where X, E X denotes the input data at time т and Ytrue E y is its corresponding true label, conformal prediction aims to construct a prediction set C (Xt) SY = (1,2..... Niabels) for new data Xt. Here, Maabel denotes the total number of unique labels. The prediction set C. (X,) is constructed such that it includes the true label Yuue with probability 1 - a, where denotes the given miscoverage probability. Upon receiving the true label Y the new data pair (Xt,ytre)) Y,tue) is added to the historical dataset. In the online setting, conformal prediction uses the evolving historical data as the calibration set to decide which candidate labels should be included in the prediction set. The decision to include each candidate label is based on a threshold determined basod on the calibration set. For each datum X, and its corresponding true label Y,tue, a non-conformily score (x"(X,, Ytrre) is calculated based on the learning model m. This score represents the disagreement between the ground-truh label Y!rue and predicted label f""(X,) A lower non-conformity score indicates a better match between the true label and the predicted label by model m. Upon calculating non-conformity scores for the entire historical dataset, {STH (X,, ytrue)) )==) threshold ta is obtained by:
[t(1 - a)] [[((1-a]]
G = Quantile
(1)
t f-1
where Quantile(...) sorts the nonconformity scores in ascending order and then outputs [(]-aa] quantile of sorted scores. Next, prediction set. for new data. X, is constructed as
empirical
t-1
CT (Xt) = (Y E y STh (X S 4
(2)
In online settings, employing a dime-invariant miscoverage probability to determine the threshold q"r may not achieve the desired coverage guarantee. To address this issue, adaptive conformal prediction has been developed, where a time- variant miscoverage probability as is utilized instead of a fixed to obtain the desired coverage. By replacing a with it's time- variant version a₃ in equation I the time-varying threshold @m, can be updated accordingly.
Even though employing time-variant miscoverage probability is useful in online environments, relying on a single learning model across all time steps may be suboptimal. To address this issue, the use of multiple learning models is considered in previous work (Hajihashemi & Shen 2024). At each time step, based on the performance of every learning model m E [M] over previous time steps, the model m is selected, and the prediction set is constructed according to threshold 4tt However, among M candidate learning models, some may exhibit poor performance due to, e.g., insufficient training data. Including such models may result in inefficiently large prediction sets. Morcover, employing a large number of lcarning models increases the computational complexity. To address these limitations, the present work develops a data-driven approach to select subset of effective models at each time step, and then choose ńà from this subset..
3

---

Published in Transactions on Machine Learning Research (10/2025)
3 Methodology
A data-driveu algorithm, Graph-struct leedback Multimodal Ensembll Ouline Conformal Prediction (GMOCP), which adaptively selects subsets of learning models, is detailed in Subsection 3.1 Subsection 3.2 then discusses the construction of the graph used to identify effective models each time step. Finally, Subsection 3.3 introduces Efficient GMOCP (EGMOCP), which incorporates prediction set size feedback to further reduce the size of the constructed prediction sets while maintaining coverage guarantees.
3.1 Data-driven Model Selection
To address the high computational complexity and inefficiency of large prediction sets, our first approach is proposed, in which subset of models is adaptively selected 'on the fly' upon receiving new data samples. To adaptively select subset of effective learning models, our proposed approach utilizes feedback from a graph that is generated in an online fashion based on the performance of each learning model in previous time steps. By doing this, the proposed approach avoids including learning models with weak performance in the candidate set for the conformal prediction task. The details of feedback graph construction will be presented in subsection 3.2
Consider a time-variant bipartite graph G, (Asratian et al. 1998 which includes two sets of nodes: M model nodes (o[",..,. "..,, and J selective nodes {u] ....,, (5) where (!) and v//) represents m-th learning model and j-th selective node respectively. The edges of the graph represent associations between model nodes and selective nodes. Increasing the number of model nodes connected to u/() can lead to higher computational complexity. Therefore, the graph generation approach should impose limitation on the maximum number of model nodes connected to each selective node. In this work, cach selective node is connected to at most N model nodes. Given G, at each time step I, one selective node is chosen and its associated model nodes, forming a subset denoted by S,, are used as the candidate set for the conformal prediction task. These selected model nodes can contribute to the conformal prediction task either through weighted sum or by selecting a single model according to a probability mass function (PMF). In this work, we focus the latter approach. The selection is guided by the weight. whf assigned to each model E [M], which influences both the generation of the graph G2 and the selection of model ń from the subset of effective models S.- Specifically, we normalize the weights of models in S₁ as wi""
Vm E Sp. Then, model is selected to create the prediction set according to the PMF defined by the normalized weights w = ("""")
Emes, with
After creating the prediction set at time I, the true label Y/rue is observed. The threshold 4 can be obtained according to equation | based on non-conformity score functions, where each score function depends on a specific learning model m. Given that different learning models yield different non-conformity scores, using a single adaptive miscoverage probability o, for all learning models is inadequate. To address this, each time step t assign specifie miscoverage probability af" to each learning model E [M]. Since the cardinality of S, is at most N, there are at most N distinct miscoverage probabilities, each updated independently. To update miscoverage probability a." for each m E [Sy], we adopt the pinball loss defined as (Koenker &
Bassett
1978):
L(ā, a.)) a(ō," a.") min(0, at" a.")
(3)
where
at = sup(a Y!ur CT (X.))
(4)
is the best possible value of miscoverage probability for model m time t, which constructs the smallest prediction set that covers Ytrue, The miscoverage probability a can be updated via scale free online
gradient descent (SF-OGD) (Orabona & Pál 2018 as
V
a L(at" a.
0141 = a
(5)
[ an L(āg (0mm).??))))))) )1
T=
4

---

Published in Transactions on Machine Learning Research (10/2025)
(
(8)
(E) V
(0 32
(
(8)
( M
2
1
22
(4)
(a)
Figure 1: (left): An illustrative example of the generated bipartite graph G2 with M learning models and J = 2 selective nodes. (right) The selective node (*) is chosen, and the subset S, includes all learning models connected to the selected node, highlighted by red edges.
which follows an online gradient descent update with a time-dependent decaying learning rate. The parameter 7j is the learning rate and
Vor "("",,)))) = T[a < <x," - =
e ax
(6)
with erră" = [[(true & C if the predicted set does not contain the true label Yfrue, and 0 otherwise.
According to equation 5 the adaptive miscoverage probability increased when the prediction set includes the true label. This allows the prediction set become smaller by excluding unnecessary labels := (Y' e Y 9% 55 Y') S [- in next step. Conversely, if the prediction set fails to include the true label, the adaptive miscoverage probability is decreased.
Additionally, the weights wt for m E St are updated after observing the true label Ytrue by leveraging a multiplicative update rule:
w = wi"h exp (-el," /2"),
(7)
where is the step size that controls weight update, b = [log2 JJ and 1.th denotes the importance sampling loss estimates (Alon et al., 2017)
L (a az 4THH
Imm Sel.
(8)
where ofth the probability that the learning model m is included in S,, which depends on how the graph G. generated.
Then, a weight u/41 assigned to each selective node j E [J] according to the model nodes' weights wiir Specifically, uit1 is calculated as the sum of the weights wit of all model nodes connected to the selective node j, as follows:
Σ
w
(9)
Vmmi -E
Moreover, the probability according to which selective node is chosen in the next time step, denoted by To sum up, each time step, all model nodes connected to the selected selective node form subset. of candidate learning models. This approach aims to avoid including low-performing models in the candidate set for the conformal prediction task. One model is then selected from this subset to construct the prediction set.
p't+1: can be updated pll+1 E af
of
3.2 Online Graph Generation
The generation of G, impacts both the selection of candidate learning models for the conformal prediction and the computational complexity. A well-designed graph should lead to the selection of selective node that is connected to a subset of model nodes, which construct small prediction sets while still covering the true label. Let A, represent the M x sub-adjacency matrix between two disjoint subsets {v .- 3.1,...., v(1) } and
5

---

Published in Transactions on Machine Learning Research (10/2025)
{v] 3.. J. The entry Az(m.. denoles the m-th row and j-th column of matrix A,, and it's value is if there is edge between model node m and selective node j in bipartite graph G otherwise it is 0. The probability of connecting model node ( each selective node is denoted by pt and can be obtained as:
Pt = (1 170)
W
+
Tl
(10)
M 2m=1 W
M
The second term in equation equation 10 allows exploration across all model nodes. Specially, each model node is connected to selective node U uniformly at random if 7e 1. Each selective node vi draws model nodes in N independent trials. In each trial, the selective node draws PMF pt (p"") 1m=1- According to the definition of pt" in equation 10 the probability that the m-th model node is connected to the j-th selective node is 1- (1 (1-p ),") where (1 - p(") represents the probability that mth model node is not selected by j-th selective node in any of N trials. Hence, the probability that the learning model m is included in St is given by
model node according to
Oi = Σ pi (1- (1)
(11)
for all m M, and is used for importance sampling loss estimate in equation The entire process for generating the graph Ge is detailed in Algorithm [ Given the graph Gt at each time step, one selective node is chosen according to the PMF p' = (F'))=>> where p't p²? =
Figure illustrates example of the constructed bipartite feedback graph and the selective node selection process. By considering the model nodes connected the selected selective node as the set of candidates, one learning model then selected according the PMF w (u="))sss construct the prediction set. The entire GMOCP method is summarized in Algorithm The per-iteration cost at time for GMOCP is O(Nt + JMNN, where the JMN term accounts for graph generation and the Nt term arises from computing at" for up to N selected models, using sorted calibration scores of length t. The per-iteration complexity of MOCP is O(Mt). Thus, GMOCP can reduce the per iteration complexity, especially in settings where N << M.
Algorithm Generating Graph G:
Require: Number of selective nodes J, exploration coefficient ne >> 0, the maximum number of connected models to each selective node N, M pre-trained models. Initialize A, = 0JxM- for m 1,... M do
Set p. = (1
7 M
end for for j 1,... J do
for = 1, 1.... N do
Select one of the models according to PMF p: ( Set A+(jm) = {m is selected model from PMF} end for end for
)==1
Let CovE(T) 1 ΣT B[errs] a represent the coverage error. The expected error is caleulated
E(err:] = " - (M N! (IIM (pmmimm bm.gg Emes., We err!" where the expectation is over every possible subset of effective models S,, (see Appendix A.2 for full definition of bm.g). Note that here w. = The following theorem demonstrates that GMOCP has bounded coverage error (See proof in
mg
A.I.

---

and Published in Transactions on Machine Learning Research (10/2025)
Theorem The coverage error of the GMOCP algorithm, for fized positive constants B1 and Bz, and 0, is bounded as
(RoE(T)STTE 2M 2v2M(1+m) 2M(1+ (1+ +
M log logT) a
(12)
"
For the regret analysis, we consider stochastic regret, which measures the difference between the expected loss of the online algorithm and that of the best fixed miscoverage probability in hindsight. Formally, the stochastic regret is defined as:
E ([R(T)) = Σ BIL(a a("]] Σ
Ma, ,a""
(13)
where
T
T
am
arg min far [M[]]] tml
Σ
L(a a)
with a = arg min
L(a a
(14)
tm
MMNN-1
M
(p bom
E IL (o a.")
N!
πI m=
Σ
W. L (0, o.t)).
(15)
bm.
q=1
mESL.
Based on the definitions above, establish the sublinear regret bound for the GMOCP algorithm in the following Theorem (see Appendix A.2 for detailed proof).
Theorem 2 GMOCP algorithm satisfies the following regret bound
IMT]
B(R(T)) S VT
(1 + 2n)) + 1 a
2 M (3 M2 M2-b- (1++))))))))
(16)
2n
Algorithm 2 Graph-Structured feedback Multi-model Ensemble Online Conformal Prediction (GMOCP)
Require: a [0, 1], M pre-trained models, and step size E (0, 1)
for t [T] do
Receive new datum
Generate graph G, using Algorithm
Obtain ui Emeny w [M]
for j l...., do
Set pd Σ.. 1
end for
Select one of the selective nodes according to the PMF p = (r't) Create set S, including connected models to the selected node. Obtain normalized weights by wh!h
Vm S, an
wm (wi mes.
Select model i according to the PMF wi
Obtain threshold gthh according to equation and construct prediction set Ct ( via equation
Observe the true label.
Calculates 4tth and update w and at" according to equation equation and equation Vm S, end for
3.3 Efficient GMOCP
In the previous subsection, a graph-structured feedback method was introduced select model m from subset of effective models St, instead of the entire set of M models. While GMOCP effectively prunes

---

Published in Transactions on Machine Learning Research (10/2025)
learning models that tend to construct inefficient prediction sets, its performance can be further improved by incorporating the size of the prediction sets an additional factor in model selection. In cases where all or most of the effective models cover the true label, the loss function may yield close values across models. In such scenarios, incorporating prediction set size helps differentiate between models by favoring those that achieve smaller sets. In this subsection, we propose EGMOCP to directly incorporate the prediction set size. Specifically, instead of relying solely on the loss-based term in the exponential update equation 7 we use a linear combination of the loss and the prediction set size to update the weights w for E St as:
(-e(11-8) 1 + BLen (a ( E (..))) s.i))
"'" exp
(17)
where Len(aa") is the length of the prediction set that has been created based on miscoverage probability of", and 3 E 1). The new update rule in equation 17 aims to reduce the probability of selecting models that result in large prediction sets. The following two Theorems show that the EGMOCP algorithm guarantoes bounded coverage error and sublinear regret. (Proofs can be found A.3 and A.4
Theorem The coverage ervor of the EGMOCP algoritlem, for fixed posilive constants Ci and B2, and 1) 0, is bounded as
CovE(T) S ST (M 2V2M(1+ 2M(1 + B201 +
M o3 log logT)
(18)
7
"
Theorem EGMOCP algorithm satisfies the following regret bound
!
E[R(T)] S VT
(1+ 2n)) (1+27)²² + - a
2n
VT
2b (In M + Natbols + + VT 1 M(L+n)² (1 (L+1) (1+m))Nu Mabblls
1
+ VT
VT
1
VT
25+1
+
VT
T T-VT
20
NN2
labels
(19)
4
Experiments
This section verifies how the proposed algorithms, GMOCP and EGMOCP, result in more efficient prediction sets while covering the true label with the desired probability in practice. We first explain the experimental settings used, and then compare the performance of our two proposed methods with multi-model confor- mal prediction algorithm. Note that throughout the experiments in this section, the desired miscoverage probability a is 0.1. All experiments were performed on workstation with NVIDIA RIX A4000 GPU.
4.1 Experiental Settings
Dataset: We utilize corrupted versions of CIFAR-10 and CIFAR-100 (Krizhessky et al. 2009. known CIFAR-10C and CIFAR-100C (Hendrycks & Dietterich 2019). These datasets consist of 15 corruption types (e.g., brightness, Gaussian noise, etc.) spanning 5 distinct levels of severity. To evaluate the effectiveness of the two proposed algorithms, we consider two distinct settings: gradual and sudden distribution shifts. In both settings, the severity of corruption changes (increases or decreases) after each batch of data. In the gradual setting, severity starts level 0 (uncorrupted data) and increases step-by-step with each batch until it reaches level 5. It then decreases back to level 0, contimuing this cycle throughout the experiment until time T. This setup simulates smooth, evolving shift in the data distribution. In the sudden setting, we evaluate the algorithms' ability to handle abrupt changes. Here, the severity alternates between uncorrupted data (severity level 0) and the most severely corrupted version (severity level 5) after each batch, representing an extreme case of distribution shift. For both settings, the data sequence is split into batches 500 data samples each. Each dataset divided into a training phase (50,000 samples) and test (6,000 samples). Additionally, separate set of 2,000 samples is used for hyperparameter selection in the conformal prediction task.
8

---

Published in Transactions on Machine Learning Research (10/2025)
Learning Models: We employ 6 candidate learning models: GoogLeNet (Szegedy et al. 2015). ResNet-50, ResNet-18 He et al. (2016), DenseNNet121 (Huang et al. 2017), MobileNet (Sandler et al. 2018 and
EfficientNee--O (Tan & Le 2019). To ensure a diverse range of performance across these models, each one is trained under 3 distinct scttings: High-performance setting (the model is trained for 120 epochs and initial- ized with default pretrained weights from ImageNet (Deng et al. 2009)); Mediumm-prfformann model trained for only 10 epochs and initialized with random weights, resulting in weaker performance). now-performance setting (the model is trained for just epoch with random weight initialization, yielding the weakest performance among the 3). For clarity, label each model according to its architecture and training setting. For example, the three versions of DenseNet are denoted as: DenseNet121-1207 (120 epochs, pretrained weights), DenseNet121-10N (10 epochs, random initialization), and NenseNet121-1N (1 epoch, random initialization). In all 3 settings, the learning rate is set to 10-3, and the batch size is fixed at 64.
setting (the
Score Functions: The nonconformity score defined in (Angelopoulos et al. 2020 is utilized to construct prediction sets. Let
0) + U. STh 5Tx(X = ///max((kx 0)
+ p(X,));
(20)
where fr (X) denotes the probability of predicting label Y for input X by model m, and U2 is a ran- dom variable sampled from a uniform distribution over the interval [0, 1]. The term by == H(Y e y' I (X) 2 f (X)H denotes the number of labels that have a higher or equal predicted proba- bility than label Y according to the model's output probability distribution, e.g., the softmax output. (( == Σy Eiaael fyr (X)I predicted probability than label Y. The hyperparameters and krog are set to 0.02 and 5 for CIFAR-100C,
(x)) sums up the probabilities of all labels that have higher and 0.1 and 1 for Cifar-10C, respectively.
Coverage measures the percentage of instances in which the true label is included in the prediction sets constructed by the conformal prediction algorithm over the period [T]. Avg Width represents the average size of the prediction sets constructed from = 1 to T. Run Time indicates the time required to complete the algorithun for one random seed. Lastly, Single Width measures the percentage that prediction sets contain exactly one element while accurately covering the true label, highlighting cases that are most informative for predictions.
Evaluation Metrics:
Baseline: The two proposed methods are compared with MOCP (Hajihashemi & Shen 2024 and COMA (Gasparin & Ramdas 2024a) algortihms. The MOCP algorithm employs M learning models and selects one model from the entire set at each time step t. The selection based on the weights assigned to each model, and the prediction set constructed using the selected model. The COMA algorithm obtains the prediction set according to each specific learning model and then creates the final prediction set as:
Σ w IYY E CTT (X,)) > U+t(t) }. m=1
=x)
(21)
where Ut) is a random variable uniformly distributed in [0, 1]. and the weights (wi 1M 1 are updated over time based on the performance of each model. Specifically, the weights are inversely proportional to the
exponential of the corresponding prediction set size.
Note that for all experiments conducted on CIFAR-10C and CIFAR-100C in this section, the parameters 1, and 3 were selected through grid search, with values of 0.5, 0.05, and 0.05, respectively. Additionally, we set T = 6000, indicating that the algorithm receives sequential data in an online manner over 6000 time steps.
4.2 Results
For this section, experiments are conducted using a candidate set of eight different learning models, including: DenscNet121-120DD, ResNett18-1222 120D, Goo0LeNet-120D, ResNet-50-120D, MobileNet EfficientNet- B0-120D, DenseNet121-106 and DenseNet121-1R. We evaluate performance across various configurations, varying the maximum number of learning models connected to each selective node N (1,3, 5), and setting
9

---

Published in Transactions on Machine Learning Research (10/2025)
the number of selective nodes J E (1, Table demonstrates how, in online setting where the data distribution experiences abrupt achieves better performance in terms of both average width and run time across all evaluated settings com- pared to MOCP, and has lower computational complexity compared to COMA when the number of selective nodes and model nodes small. EGMOCP, which specifically designed to further reduce prediction set sizes while maintaining valid coverage, achieves this goal effectively. As shown in the table, EGMOCP significantly reduces the average prediction set size and improves the single-width metric.
significant differences bet ween two successive batches, GMOCP
Table 1: Results on the CIFAR-100C datasct under sudden distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results in each column. GMOCP consistently achieves faster runtime compared to MOCP across all settings. EGMOCP constructs smaller prediction sets and higher proportion of single-width sets.
J
Method
Coverage (%)
Avg Width
Run Time
Single Width
мОCP COMA
89.71 +: 0.37
0.05
22.43
90.00 = 0.01
8.36 + 0.95
11.23 = 0.07
28.60 = 1.83
1
1
GMOCP
89.11 + 0.21
12.03 2,80
4.88 + 0.02
22.55 + 3.62
EGMOCT
89.10 1 0.28
6.91 1 0.25
6.01 1 0.02
28.62 1 0.93
2
GMOCP
89.10 + 0.19
12:07 0.45
4.97 0.02
23.55
0.63
EGMOCP
89.03 + 0.17
7.04 = 0.14
6.16 + 0.03
28.36
= 0.91
GMOCP
89.04 + 0.21
0.03
24.12 0.93
EGMOCP
88.99 = 0.21
6.92 = 0.19
6.87 0.02
28.00
0.80
3
1
GMOCP
89.55 + 0.28
10.68 1.05
6.05 0.04
23.45 + 2.53
EGMOCP
89.38 1 0.22
6.79 + 0.19
8.80 +: 0.12
29.04 + 0.69
2
GMOCP
89.50 0.26
10.93 0.53
6.63 0.04
24.49 0.63
EGMOCP
89.29 + 0.21
6.48 = 0.09
9.30 0.09
29.03 = 0.55
GMOCP
89.64 + 0.34
0.35
7.44 0.03
24.30 0.64
EGMOCP
89.38 = 0.31
6.26 = 0.14
10.29 0.03
29.62
0.68
1
GMOCP
89.55 1 0.30
11.05 1.24
6.91 0.07
23.78 1.90
EGMOCP
89.46 + 0.36
6.59 + 0.12
11.16 = 0.04
29. + 0.65
2
GMOCP
89.53 0.26
11.35 1.17
7.87 0.06
23.85 0.95
EGMOCP
89.41 + 0.28
6.30 - 0.13
12.03 = 0.35
29.81 = 0.46
GMOCP
89.73 + 0.31
11.65 0.81
8.94 0.07
23.62 0.62
EGMOCP
89.43 = 0.27
6.18 = 0.14
12.97 0.05
29.91 + 0.47
To enable selective nodes with different levels of exploration and exploitation as considered in Ghari & Shen we use different 7e values across selective nodes in equation 10 For the case / = 2, we use 7e (0.2, 0.8), and for 4, we use 7. = {0.1, 0.2, 0.3, 0.4). This set ensures that the last selective node places more emphasis on exploration compared to the first node. Table presents experimental results on CIFAR- 10C under gradual distribution shifts. Note that across all settings, GMOCP and EGMOCP algorithms achieve coverage close to the desired level of 90%. GMOCP consistently demonstrates lower computational complexity compared to MOCP while producing smaller prediction sets and higher proportion of single- width sets. GMOCP is also faster than COMA in cases where there are a small number of selective nodes and model nodes. Furthermore, EGMOCP consistently constructs significantly smaller prediction sets and yields higher proportion of single-width prediction sets compared all benchmarks. Note that even though COMA obtains the dcsired coverage experimentally, such coverage not guaranteed theorotically.
To demonstrate the effect of using prediction set size as feedback- enables EGMOCP to constructs more efficient prediction sets compared to GMOCP and MOCP-Fieee 2 illustrates the behavior of EGMOCP across the entire time horizon. To better visualize the differences among the 3 proposed training configurations, the figure shows results for three versions of DenseNet121 under the setting N = and 2. As observed, better-pent netter-perorriin models tend to construct smaller prediction sets. By incorporat- ing prediction size into the update rule equation 17 the algorithm assigns lower weights wi" to weaker models, reducing their chances of being selected. As a result, EGMOCP favors high-performing models and constructs significantly smaller prediction sets than the other two algorithms.
10

---

Published in Transactions on Machine Learning Research (10/2025)
Table 2: Results on the CIFAR-10C dataset under gradual distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results in each column. GMOCP consistently achieves laster runtime compared to MOCP across all settings. EGMOCP constructs smaller prediction sets and higher proportion of single-width sets.
N
Method
Coverage (%)
Avg Width
Run Time
Single Width
MOCP
90.03 0.30
2.07
0.35
8.83 0.04
48.00
7.84
COMA
90.02 = 0.02
1.19 0.07
10.76 + 0.01
61.39 = 2.92
1
GMOCP
89.36 1 0.21
1.90 0.27
4.32 1 0.01
48.14
4.22
EGMOCP
89.37 + 0.22
5.51
57.48
GMOCP
89.37 1 0.17
1.78 0.03
4.39
0.03
52.30
1.27
RGMOCP
89.35 + 0.21
0.02 1.50
5.58
+ 0.01
55.57
1.19
GMOCP
89.25 0.21
1.77
4.74
52.45
1.03
EGMOCP
89.28 + 0.16
0.02 1.55
5.91 + 0.01
56.69 + 1.11
1
GMOCP
89.79 + 0.25
1.78 0.17
5.41 + 0.06
50.97 1: 3.41
EGMOCP
89.83 + 0.30
1.50 0.02
58.98 1.07
GMOCP
89.78 0.32
1.78 0.04
6.06 1 0.05
52.64 1.23
EGMOCP
89.65 + 0.22
1.37 0.01
9.08 - 0.05
61.51
0.77
GMOCP
89.72
6.36 0.04
53.68
EGMOCP
89.60 + 0.35
1.41 0.02
9.73 + 0.02
60.68
1.21
GMOCP
89.72 + 0.17
1.85 0.15
6.71 + 0.11
51.02 + 2.96
EGMOCP
89.82 - 0.26
1.48 0.02
10.88 - 0.04
59.39
GMOCP
89.73 0.26
1.80
7.33 0.03
52.27
1.13
EGMOCP
89.87 + 0.36
1.35
0.01
11.66 - 0.03
62.23
0.57
GMOCP
EGMÖCP
89.99 1 0.24
1.38
0.02
12.84 1 0.11
61.84
0.55
30
Size
10
Weight of Densenec121 120D
weight of Denseneri 20
0.22
weight of Densenec1 21
0.70
Weglss
0.15
0.10
2000 2000
3000
4000 3000 8000
Epoche
Figure 2: Evaluation of prediction sets constructed by training configurations of DenseNet121 under = 5 and 2 over 6000 timesteps. The top plot shows the size of the prediction sets, while the bottom plot shows the corresponding model weights w over time. DenseNeel121-22D consistently receives the highest weight, indicating higher likelihood of being selected. Moreover, models with better performance (e.g.. DenseNet121-120D) create significantly smaller prediction sets.
5 Conclusion
In this paper, we proposed 2 multi-model online conformal prediction algorithms. By leveraging graph- based feedback, the proposed methods dynamically select subset of effective learning models at each time step for the conformal prediction task. Additionally, demonstrated that incorporating prediction set
11

---

Published in Transactions on Machine Learning Research (10/2025)
size aloobassk-alngiieeee the loss function into the model weight update rule significantly improves the efficiency of the constructed prediction sets. This results in smaller prediction sets while stiil satisfying the required coverage guarantee. It is proved theoretically that the 2 proposed algorithms guarantee valid coverage and achiove sublinear regret. Experimental results in an online setting, simulating real-world online environments, show that GMOCP consistently creales smaller prediction seis with lower computationa ional complexity compared to basclines. Furthermore, EGMOCP able to construct even smaller prediction sets by effectively selecting high-performance models.
6 Acknowledgments
Work in the paper is supported by NSF EECS 2207457, NSF ECCS 2412484 and NSF ECCS 2442964.
References
N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, and O. Shamir. Nonstochastic multi-armed bandits with staph-sr feedback. SIAM Journal on Computing, (6(6):1785-1822) 2017.
A.N. Angelopoulos, S. Bates, M. Jordan, and J. Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Represenlations, 2020.
Anastasios Nikolas Angelopoulos, Rina Barber, and Stephen Bates. Online conformal prediction with de- caying step sizes. In International Conference on Machine Learning, pp. 1616 16661660..06 PMLR, 2024.
Armen S Asratian, Tristan MJ Denley, and Roland Häggkvist. Bipartite graphs and their applications, volume 131. Cambridge university press, 1998.
V. Balasubramanian, S.S. Ho, and V. Vovk. Conformal prediction for reliable machine learning: theory, adaptations and applications. Newnes, 2014.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, (1)):816688) 845, 2023.
Pankaj Bhagwat, Linglong Kong, and Bei Jiang. Cbma: Improving conformal prediction through bayesian model averaging. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR), 2025. To appear.
Aadyot Bhatnagar, Huan Wang, Caiming Xiong, and Yu Bai. Improved online conformal prediction via strongly adaptive online learning. In International Conference on Machine Learning, pp. 2337-2363. PMLR, 2023.
R.S. Boger, S. Chithrananda, A.N. Angelopoulos, P.H. Yoon, M.I. Jordan, and J.A. Doudna. Functional protein mining with conformal guarantees. Nature Communications, 16(1):85, 2025.
H. Boström, H. Linusson, T. Löfström, and U. Johansson. Accelerating difficulty estimation for conformal regression forests. Annals of Mathematics and Artificial Intelligence, 81:125-144, 244,,4, 2017.
N. Cesa- Resa-Bianchi, Y. Freund, D. Haussler, D.P. Helmbold, R.E. Schapire, and M.K. Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427 485, 1997.
J. Deng, W. Dong, R. Socher, L.J. Li, K. Li, and Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, pp. 248 255. IEEE, 2009.
T. Ding, A. Angelopoulos, S. Bates, M. Jordan, and R.J. Tibshirani. Class-condiiional conformal prediction with many classes. In Advances in Neural Information Processing Systems 36, pp. 64555 64576, 2023.
A. Dixit, L. Lindemann, S.X. Wei, M. Cleaveland, G.J. Pappas, and J.W. Burdick. Adaptive conformal prediction for motion planning among dynamic agents. In Proceedings of the Learning for Dynamics and Control Conference, pp. 300-314 314. PMLR, 2023.
12

---

Conformal online model aggregation. arXiv preprint Published in Transactions on Machine Learning Research (10/2025)
A. Doula, T. Güdelhöfer, M. Mühlhäuser, and A.S. Guinea. Conformal prediction for semanticall--aware autoonomous perception in urban environments. In Proceedings of the 8th Anaual Conference on Robot Learning, 2024.
Shai Feldman, Liran Ringel, Stephen Bates, and Yaniv Romano, Achieving risk control in online learning settings. arXiv preprint 225::2205009995, 2022.
Matteo Gasparin and Aaditya Ramdas. (rXXi:2403.155211 2024a.
Matteo Gasparin and Aaditya Ramdas. Merging uncertainty sets via majority vote. arXiv preprint
(:Xxv:2401.09377 2024b.
Pouya M Ghari and Yanning Shen. Online multi-kernel learning with graph-structured feedback. In Inter- national Conference on Machine Learning, pp. 3474 3483. PMLR, 2020.
Gibbs and E.J. Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 25(162):1-36, 2024.
Jack Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift. Advances in Newral Information Processing Systems, 34:1660 1672, 2021.
Erfan Hajihashemi and Yanning Shen. Multi-model ensemble conformal prediction in dynamic environments. Advances in Newral Information Processing Systems, 37:118678-11888 2024.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pp. 770 778, 2016.
D. Hendryeks and T. Dictterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019.
Tom Heskes. Practical confidence and prediction intervals. In Advances in Neural Information Processing Systems 9, 1996.
G. Huang, Z. Liu, L. Van Der Maaten, and K.Q. Weinberger. Denscly connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
R. Koenker and G. Bassett, Regression quantiles. Econometrica: journal of the Econometric Sociely, pp. 33-50, 1978.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of fcatures from tiny images. 2009.
Yann Le and Xuan Yang. Tiny imagenct visual rocognition challenge. CS 231N, 7(7):3, 2015.
L. Lei and F.J. Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B: Statistical Methodology, 83(5):911 938, 2021.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-261, 1994.
C. Lu, A. Lemay, K. Chang, K. Höbel, and J. Kalpathy-Cramer. Fair conformal predictors for applications in medical imaging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 12016, 2022.
Roberto I Oliveira, Paulo Orenstcin, Thiago Ramos, and João Vitor Romano. Split conformal prediction and non-exchangeable data. Journal of Machine Learning Research, 25(225):1 111225))1333. --,, 2024.
F. Orabona and D. Pál. Scale-free online learning. Theoretical Computer Science, 716:50 69, 2018.
H. Papadopoulos, K. Procdrou, V. Vovk, and Gammerman. Inductive confidence machines for regression. In Proceedings of the 13th European Conference on Machine Learning (ECML), pp. 345-356, Berlin, Heidelberg, 2002. Springer.
13

---

Published in Transactions on Machine Learning Research (10/2025)
H. Papadopoulos, V. Vovk, and A. Gammerman. Regression conformal prediction with nearest neighbours. Journal of Arlificial Intelligence Research, 40:815 840, 2011.
J.K. Patel. Prediction intervals a review. Communications in Statistics- Theory and Methods, 18(7):2393 2463, 1989.
Podkopaev and A. Ramdas, Distribution-free uncertainty quantification for classification under label shift. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 844-853. PMLR, 2021.
A. Podkopaev, D. Xu, and K.C. Lee. Adaptive conformal inference by betting. In Proceedings of the International Conference on Machine Learning, pp. 40886-40907. PMLR, 2024.
Y. Romano, E. Patterson, and E. Candès. Conformalized quantile regression. In Advances in Newral Infor- mation Processing Systems 32, 2019.
Y. Romano, M. Sesia, and E. Candès. Classification with valid and adaptive coverage. In Advances in Neural Information Processing Systems 33, pp. 3581-3591, 2020.
M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.C. Chen. Mobilenetv2: Inverted residuals and lincar bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510 4520, 2018.
G. Shafer and V. Vovk. tutorial on conformal prediction. Journal of Machine Learning Research, 9(3.. 2008.
F. Shi, C.S. Ong, and C. Leckie. Applications of class-conditional conformal predictor in multi-class clas- sification. In Proceedings of the 12th International Conference on Machine Learning and Applications, volume 1, pp. 235 239. IEEE, 2013.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recogmition, pp. 1-9, 2015.
M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks In Proceedings of the International Conference on Machine Learning, pp. 6105-6114. PMLR, 2019.
R.J. Tibshirani, R. Foygel Barber, E. Candès, and A. Ramdas. Conformal prediction under covariate shift.
In Advances in Neural Information Processing Systems 32, 2019.
J. Vazquez and J.C. Facelli. Conformal prediction in clinical medical sciences. Journal of Healtheare Infor- matics Research, 6(3):241-252 2022.
V. Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intellgencc,, 74:9-20 28, 2015.
V. Vovk, A. Gammerman, and G. Shafer. Algorithmic learning in random world, volume 29. Springer, New York, 2005.
V.G. Vork. A game of prediction with expert advice. In Proceedings of the Eighth Annual Conference on Computational Learning Theory, pp. 51 60, 1995.
Yachong Yang and Arun Kumar Kuchibhotla. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, 120(549))435-447, 2025.
M. Zaffran, O. Féron, Y. Goude, J. Josse, and A. Dieuleveut. Adaptive conformal predictions for time scries. Proceedings of the International Conference on Machine Learning, pp. 25834 25866. PMLR, 2022.
14

---

Published in Transactions on Machine Learning Research (10/2025)
A Proofs
A.1 Proof of Theorem 1
Define at" := a erri". Suppose the sequence {ar he(r) I and satisfies a S |a4"l S 1 for 0 < a < 1. The
proof this lemma is based on a grouping argument. We start by defining new variables L and K as follows
T L L= K=
- +1,
where y E (0, is parameter to be chosen. The kth group out of all K groups is defined by
Gk = (4k-1 + [4) = {(k: - 1)L + 1,..., min(kL,T)
This results in UK G [T], with [G&l = L for all & E [K 1]. and |Gxl S L. For any 222 2, we define
(p pam)dmm bm.g!
mg
Sk
N!
Σ
W
tEGR
mESL.
(2
(p Bonis bm.g!
S =
N!
(22)
G 9=1
m==
mESt.
)a
For Sy and S3 we have
SS - Skl
< Σ e
Ad
(p Lome bm
N!
Σ
w a.'l
-- (am))
v 1 (am)
teGr 9=1
mESta
M
Σ Σr=da-1th 111 (am²)
1
< |G
T
m=1
+== (am))
1k
(a
m=1
2
1/- (apt)
(1)
M
L
L
M
L
2k - 1)L -te (am))
2a²
1)
aa² -1)L
m=1
m=1
ML
(23)
3k 1) 12-11 I)L
where (i) employed inequality 4 Vzty - بي for x, 2 Additionally (ii) considered two bounds
2x
Ety 1::1+1(00 (a < (tx 11) I L and Et'r (atr)² have:
a 2t a²(k 1)L. By using triangle inequality we
ML
S&p < |Sa| + 1S+
Sx - |Sal +
2a 1) (k (k-10 1)L
15

---

Published in Transactions on Machine Learning Research (10/2025)
For any & we have
M
(or mm
Σ
N!
Wi
m2 m
LEGN q=1
meSi,
(p bomi bm.o!
l 1-1 1 r=1
(am))
Σ
N!
Σ mESLi
_ 0t
LEGN q=1
m==
(a
M II m==
(ptt Bm..
N!
Σ meS
W.
m4
O2
vk - 1)L
bm.o!
c Σイ=
(am)²
N q=1
ML
< (1S& + 1Sk - Skl)
V(k 1---1)L- S SAA V(k - 1)L+ + 2n (1: - 1)
(24)
According to equation 5 and defining Am = Eg= N! (M...
(n2 Prn. om.o!
W
my for SS&] we have:
S
Σ
N!
II
M
W.
mg
(a
M
Apt a²
bm
"
BEG 1=1
mE31.
m= 1 LEG
12
1--1 + All a
A +2) + + ate (A A7T
1) m=1
( 1
2(1 1)) + +G B2 (cBie-1) 1)= M(1+ + 1) 1
(2+ B2 (eBie-1))
(25)
7
where (i) follows the upper bound obtained in Lemma 3
Also for k 1 we have
ELEG, Eg=t No (IIma (pm
M+N--1)
Emesi, Ti ard < M|G1| < ML. By summing bounds over
bmio!
A [K] we have
Q
(p Semryonee Denve um.g
N!
II
Th We Or
meStc
K
(wgt Umni
< MML+ +
N!
W oe
mh
bmig!
k=2
GEGN
MLL+
M + m)
(2 LB2 (6 (BBic
V(k 1)L
ML
K
1
"
203
k
k=
2M(1 +n) SML+
(VLK8- (ILK&+(KJ)) (KL) Bye +
ML
log K
20
2M + m))
+T - 11) + M M
< M[7
log 7 1-7
" 2M(1 +1)
2x3
(2T Bz T (Bi6)²
MT
2MT
2! + +..))
log T.
(26)
7
o3
16

---

Published in Transactions on Machine Learning Research (10/2025)
The exponential term is replaced with its Taylor series in (t). We can achieve convergence for coverage error by setting E (2: and = T- Choosing 7 and dividing by T, we obtain
1
T Q
-
N!
(pt ban.
Σ
T
bm.q.
q=1
mESt.
2v 2v2M(1 + m)
2M(1 1)
BIT
M
ST
2M
(1
...) +
logT
"
2!
a
2/2M (1 + m)
21 + 1)
= T 2M +
BBBi (1 + +0(1)) + a log T
(27)
17
1
A.2 Proof of Theorem 2
To prove regret bound for GMOCP, we first establish the following two lemmas as a stepstone.
Lemma 1 For miscoverage probability assigned to any model in E [M], we have the following bound
T
MVT (1 2n)² + nTT
Σ
L(a ax) - Σ
L(a th Th <
21me
where athh arrggming min Σt= L(at af")
Proof: We first begin with
V am L(a , at I E St}
(a - =² (at
Er= 11 L(ā o
Then define adaplive leurning rale tt. as
2
"
Er= | V L( )
where 71 S 1/2 S "
avi Then we have
V7
th
2 = (n V. az Maa af t Hm E S.))) + (a - a= - 21p((a - -a Laa," "att,, TT") E S.).
Therefore,
th (a"" aa L(a at I[m E St} (a 12 (a741
+ 17t
(V.
L(a t
at & JI e S. (28)
2n
Since the loss function equation is convex, we have the following inequality
L( ai)) L[a, a*)) s (a at " ag L(a (1))),a)))))
(29)
Combining equation 28 and equation 29 we arrive
(Maa ,0t m) - I(aa .at I(m E St}
(a n2
(a - n2
1h (V
(v Laa af M S,
(30)
21p
2
Taking the erpectation of left hand side of equation
30
with respect to I(m St), we obtain
E [LLaf ax - L(a a 11m E St}]
= (L(af a²)) - L(a t a a²)) x 1 x athh + (L(at" a - aa)))aa")))))) x0 x (1 - g²t))
= (L(a a()) L(a,t a)
(31)
17

---

Published in Transactions on Machine Learning Research (10/2025)
where qed is the probability that model mn is in the chosen subset of models. Moreover, for the expectation of right hand side of equation 30 we have
E
a t a
mm
(0,7) - )
+ The
(Vap
ap oa
oz Mm 5,))² Lag th
217
2
(a
mm (af a
nag
th
+
(Va :a))) a²²
(32)
21jt
2
Based on equation
In this setting we obtain
J (1 (1- (1- (1-17))) = Σ
Σ
p%
P m
(I+... + +(1 pp
j=1
I=1
Il
Nle M
Pi
(33)
M
j=1
j=1
From equation 30
equation
31
and equation 32
we can conclude that
(a 0 (aft1 - a² )2
L(o oo)) - L(a? th a=)) s
+
Yt (Va la,))
(34)
2n.
2
By summing equation 34 over = I,..,TT T, we have
Σ
(a at) - L )a))
(a c
a 12 (a - )2
T
Σ
The
V o
L(a , ((aataaaa)))
att)²
21 m
2
1=1
MvT
faf a2
th
1
T
2m
17c
2
[=1
T=l V Li a
M T
T
r
Σ
m - 2m 1-n (att1 - a 0
1
21/rle
2
Etm |I Maath (
t=1
t=
M MVT ((a - a01 - (a7++1 -1a7+1 13)
! Σ
a
+
21me
2
avi
MVT
T
(1 + 2n)2
(35)
21Mr.
a
where in (1) we use qehh >
Th
as in equation
33 and (ii) used at" E [[n,, 1 n] as proved by Lemma 2 in
M
(Hajthashemi & Shen 2024).
Lemma 2 For any model in E [M] following bound holds
T
[O m on Σ I (a an) S 2b In
T
M (1 + 1)
Σ
M + Tna + 1) + --1
(36)
22b
Proof: Defining W. = Σ EM m= win and !े
= U.
have
W+1
W
M
With
M
1
exp
-
W.
W.
We
We
2b
1=1
1=1
m=
m=
M
Pt
U1 M
1
cxp
-
(37)
1
nec
26
j=1
m=1
18

---

Published in Transactions on Machine Learning Research (10/2025)
Using the inequality exp(-2) 1 1
x² +
vx 2 0 leads to
2
Wi+1 W
1
M
Pt
Ue
M
1
4
2
1m
25
2
j=1
m=1
By taking the logarithm from both sides of above inequality we have
2
M
2
In
W+1
<
In
Pr
M
Im
+
2
W
1
17c
2
j=1
m=1
1
J
M
Pt 122
4
c2
M
1
1
25
2
1=1
m=l
J
M
2²
1.
2
(18)
Pt
4
+
(38)
1
1/c
25
2
3 ]=1
m=
(1)
where S follows 1 + x S expx x in case we replace x with In y which leads 1 + In S y, and follows
Σj=1 /7 m= pi vi
1. Summinng equation 38 over I from 1 to T result in
WT W
M
P
To M
1
2
2
(39)
Tle
26
2
t=1
m=1
Furthermore, recall the updating rule of with in equation
for any model in [M]
we have
Wr+1
2 In
WT +1
In thth cxp
Σ
T
c 2b
1th
In
-n In
T
p
(40)
W1
W1
2
combining equation 39 with equation 40
result in
M
P
M
Tee
1
2
1m
25
2
2 In M - Σ
T
1t
1
nee
26
2b
7m1
Multiplying
(1- both sides and rearrangement leads
Pt
mam
(1
17
1=1
m=1
t=1
21 ne)
In M +
T
J
M
(pt
m
Th
M
262b
pm
+
T
J
M
nec
2
26
M
1=1 j=1
==1
t=1
1=1
T=
In M + ΣΣ ( 2b
M
p.
2
J
M
Tee
+
(41)
2
25
M
W=1
1=1
m=1
Recall the probability of observing the loss of m-th model at time q. The expected first and second moments of 4m given the losses incurred up time instant. 1,
where (i) follows P. 2 since < ne <
19

---

Published in Transactions on Machine Learning Research (10/2025)
Le, {L (ar", )== can be written as
1 1 (1 (1-x7-)²)
L (af ,0""
E [.:)
Σ
p
(a, af")
j=1
pl 1- (1- )
1,2 (at ozg
1.2 (att aa
(1 + 1))
E
[4Th)
Σ
(42)
9.
q: T
Taking the expected value of equation
41 at each time we have
T
M
T
ΣΣ
p (a
L
a
- Σ
L
(att
at)
m=
t=
26
In
M
T
M
Ule
T
M
m
<2b
(1+1)*
2
M
2
t=1
j=1
m=1
1=1
j=1
m=1
2b
2 (1
1)
In M Tne (1 1)
Pt
(43)
22 gr.
Based on definition of qz we obtain
Σ vi
(1 (1-)"") ppT))))
Edie (1 (1+...+ + )rt) )
j=1
1=1
Pept m
Σ Tir = Pt m
(44)
5=1
So according to equation
44
we have
M Pi L (a a
- La a
1=1
m=1
1=1
2 h + +) - M ( (1+1)²
(45)
22b
According to the procedure of generating the groph G, which is presented in Algorithm 4 for each selective node a subset of models is chosen in N independent trials. In fact, a subset of models is assigned to each node in N independent trials and in each trial one model is assigned and its associated entry in the sub-adjacency matric becomes 1. Now let by represents the frequency that m-th model is chosen in N independent trials. LM Thus, 1 can be viewed the solution to the following linear equation
b2 + bas = s.l. bm 2 0, bm EN
(46)
There are (M++N-I) different solutions for above equation. Let { For the expected value of loss we have
MM denote the q-th set of solutions.
(Wm Jomii bmad
E L (a
Σ
N!
II
Σ me.
with L (a. o.?")
(M+N-1)
M
(p
N
Σ (af" o
(47)
bm.g!
1=1
4=1
mES..
Note that the number of ways to solve equation number of ways to solve the following problem.
46 when m-th kernel is chosen at first trial is equals to the
bn ba bN.m N 1, s.l. In.m 2 0, bn N.
(48)
20

---

Published in Transactions on Machine Learning Research (10/2025)
There (M++N-2) different solutions for equation 48 Let {6% M denotes the q-th set of solution for Therefore we can conclude the following quality.
equation 48
(MAN-1) 1)
M
fmi (p:
N!
Σ mESL.
L Lā, a,,
bm.g!
j=1
9=1
(M-N-2)
(pt Bi.. blam!
Pt
N!
L Laat ,
(49)
m=
m=
where
Eq=1
(M
No Im=i
(p Phom bn.m!
is the total probability of all (M++N-2) of equation 48 Therefore,
Σ
(MNN-2)
N!
[Tm=
(pt (pmry) bn.m!
=1.
We obtain
M
E a(')) S
Pi m L (a al
(50)
j=1
m=
So we have
T
2
In M Tn- + -- 1 + n1)
Σ Ea of
Σ
L (a (a,, ath
(51)
c
22h
which concludes to proof of Lemmal
Now, we define the best model in the static environment as
m arg min MEM
Then, we replace in with best model m² in Lemma and Lemma to:
Summing results of two lemmas lead
E (at", af")]] Euaa .am's VT
M
(1 + 2n) + 7 (K
21p1le
+ In M + Tne + 1) + T-2h-1 (1 1))
2b
22b
MT²
VT
(1 + 2n)
+ 2 In M T (1 M2- (2 +)²
(52)
2n
where in (i), we set E
1 and M/ = T
VT
Lemma 3 By defining A 2g N! (IIM 2(N + 1)ee(1 + 7) n Proof: Based on definition of ATt and Am have:
(p bmm bm.g!
w for any Gk, we can say |ATT
A 5
14TH
Am
N!
M II
mg
II
M
(p
bmi
w
my
Immn bm)g))
M
mm=
m=l
Q
N
II
M
(p. m Pmii
w
M
(pTt1)
bmig
wa
4=1
[mm=
Um
m=1
(53)
21

---

Published in Transactions on Machine Learning Research (10/2025)
By taking the in from each term in absolute value of equation 53
the equation can be rewritten
πI
(p:
th
Wi mg
In
II
(p++1)
bong
Wi+1
M
M
bm.
In Pt + In ui; mm
Σ
mm
pit1 + In 1n m
m=1
m=1
M
bm.
pi" - In p +
II1 wi
mg
In wi+11
mg
m=l
Σ
M
bm.q
In
+
In
W
mg
M
bm.q
In
(1 17c W.
+
In
w
P141
W
myy
(1 me)
M
mag
W
m=1
m=m
Well
(54)
According to the update rule equation
we have
M
bingg
In
(1 me Jus +i We
W.M.
In
We
124 W29
1+1
m=1
MF1 ne )op -te Wi
We+rh
exp W.
mg
-
W
M
W4+1
M me) De! The We
W 1+11
12
bm.gg
+ In
In
We
M(1
M1 Me + 1)c W++1
W
25
m=1
M
W++1
M
M(1 - 71 No?" 77 W
W
1
bm
In
Σ
bm.g
In
+
In
c+1
W.
M(1 No. nowut4 + 7/c W.
W
2
m=l
m=
(55)
A m== With exp
(-
1th
Σ Eg with
exp
(t 1
bm.
+ In
-mm=1 witt
Emer 10th
M
M(1 - uw
+ 1)c
ΣM
mm/l w
bmi
In
m=l
M(1 7e uf exp (-e
100
+ 1e
Em= m= W exp -C
M
25
M
Σ M
-m Th
exp (-f(c))
Σ Emen W exp (-f (c))
bm.g
AM with
Emer w
m=1
M
M(1 - Wo +1e S -m== With
+
bm.g
In
+ f
M(1 - me) uf exp (-f (c)) + 11 ΣM with exp (-f (c))
m=1
M
2
bm
+ f(c) = 2(N 1)f(c) 2(N + 1)c(1 17)
(56)
n.25
22

---

Published in Transactions on Machine Learning Research (10/2025)
Note that in (i) we replace the e terms with their mazimum value f(e). (ii) follows equation 33 and the fact that mazimum length of every prediction would be K. By defining B1 2 n.2" (1+ 1) we have:
M
M
In
II
(pt
Th
W.
in
II
mg
<= Bie
M
M
N
II m==
(ot)
Wig
mm
II
(pit1)
bmn
W
my
(()
[Im= bm.g!
q=1
mm=1
Q
N
(eBie- (188)
B3 (e 11),
(57)
II ben
-=1
where (it) follow lar yl <= e - In ll <= v10, 1]. (Hii follows the definition B₂
Σg
bm.g!)
A.3 Proof of Theorem 3
The proof of coverage for EGMOCP follows the same steps as the proof for the GMOCP algorithm up to the point where the upper bound in equation [5 is derived using Lemma 3 At this stage, we instead apply Lemma 3 where the constant C1 replace the original constant B1. As a result, the coverage error for EGMOCP is bounded follows:
M+N-1)
(p brniu
N!
πI
Σ
Wy dg
T
bmnaa
mE...
2 212M111 + +n)
2M + n)
M log
TT
2M +
B2Ci(1+ o(1) +
(58)
"
a
A.4 Proof of Theorem 4
To prove regret bound for EGMOCP, we first establish the following lemma.
Lemma 4 for any model m [M] following bound holds
T
Σ L (ā oz))
Σ
L
(m)
2
82
Niabeta T + MT 22
(1 (3) (1-3) (1+ 22b
+ (1 B)B (1 N
<
In M
+
(Niatets)))
(1 ()
(1 3)
26-
(59)
Proof: Defining W. = Em= with and iz
== m
we have
U.
W
Σ
T
W
1+1
W.
We
W
M
Wi
(1 - 9) pm
+ (( E
exp
-6
W
2
m=11
M
mm
+ Benn J{m (is
M
exp
- (1 3)
(60)
1 ne
26
m=1
23

---

Published in Transactions on Machine Learning Research (10/2025)
Using the inequality exp(-2) 1 1
+
x²
2
vx 2 0 leads to
W(+1
J
Pt
Th
The M
1 - (1- (11-B)
+ BLen(a, JI E 5:
Wi
f/e
2h
m=
M
2 (1 B) 2r + +BLen(a,")[mm Sil
Pt
(61)
1/e
2
m=1
By laking the logarillon from both sides of above inequality we have
W+1
M1
Pr
T
Tee MI
(1 c(11 - (3 1
In
S
In
(Len(ol") JTm e (.))
We
26
j=1
m=1
2²
((1-
3
+ (Len(a?")ll(m S.})
+
(8)
M
Pt
The M
1 1 (1 - 3) Im
+ Lenn(a [[ E Si)
2
Tle
/=1
m=1
M
Pt
M
T2e
2 (1 B) 25
+ BTen(a ([ 81}
+
7e
1=1
Pt
M
- (1 3)
m
+ BLen(a,))) E S.)
nc
2
1=1
M
p
n
2 (1
3
mm 25
+ BTen (0 T(m 8.))
M
(62)
Te
m=1
(1)
(8)
where < follows 1 + x S expx I in case we replace with In which leads to 1 + In S y, and S follows pr 2t 1. Summinng equalion 6% over from 1 to T resull in
Σ/ 1 Σ M
m=1 1-
WT+1
T
M
Pr
(-c (1 B) pm
+ ( tit
W1
1 1 17
26
[=1
j=1
m=1
T
(1 3) m
+
E 5.))
M
2
(63)
Te
m=1
Furthermore, recall the updating rule of with in equation
17
for any model m E [M] we have
Wr+1
w
1 - BLnn(a I{(m {mm e s.i) In 1 Σ -c (1-
T
In
> In
= In Rd exp
W1
W1
26
(1 - 3) t
--hM
+ 3Len(a. I[m E si)
(64)
1=1
24

---

Published in Transactions on Machine Learning Research (10/2025)
combining equation
63
with equation 64
result in
T
M
m
Us M
(-e (1 B)
1 25 + (ee E s.i))
1 Tle
m=1
M
é (1 3) 25 + BLenlaa") 5i)
Pi
1 1 77
2
j=
2 In
6
(1 3)
26
+
3Len(aaj) Mm E si}
(65)
Multiphying
n1 <(1 B)
both sides and rearrangement leads
2
ne)
Σ
Pt pm (1 No)
m
In M
<(1
3)
j=1
T
62% (1
Me)
T Σ
M
2 3(p
Th M
Len(a E St}
Len(a))) E St}
1-
B
1 1-3
1=
j=1
m=1
+
T
Σ
M
(p
2/ )22
1m (3 (1-
+ LLenn )mm E s.i) 2)0
25
2
+
+ΣΣ
T
pm
2(1
B)
M
1=1
j=1
m=1
j=l
m=l
(8)
2b
32b
MMM+ + Σ
Len(af al Mim E St}
<(1
3)
1 B
+
T
M
2(1 - B)
pf 22b
(1
2h
m
+
BLen(oa TTmE 5.)
T J
M
Te pm M
t
(66)
1=1
m=1
t=l
j=1
m=1
Taking the expected value of equation 60 at each time t we have
T
M
T
Pt
T.
L
(a
oz
1=1
1=1/=1
m=1
2b
T
32
In
M
Len
(a+ To )oE
De (1
(1+ + 1))
c(1 3)
1 B
M
(=1 j=1
m=1
M
(1-
- 3)2
(1+n)²
+ 2(( - -3 (1+n)Len(a 2
+ (B)) (oT"
+ ΣΣ
Σg
gr
Pt
2(11 5)
1=
m=1
2b
326
In M.M+ +
1- 8 Nlabels T + (n + 1)
c(1 - 3)
M
(1 1++m) 11)
(1 + Ntabets + (Niobets
+
Pt 1-
(1 3)2
22b 226gr yb
+ (1 - (1-3)
2
(67)
1=1
m=1
So according to equation 44 we have
J
M
Σ)
P
L (a,
m
)
(a ar
1=1j=1
m=1
2b
In M NuabeisT + Tne(n + 1) + T 22011
32b
83 (11 (1- 10- (1 7))
+11 - 833 (1 + Ntabett
<
(1-
+ (N (Ntobetss))
c1 - 3)
22b
26
(68)
25

---

Published in Transactions on Machine Learning Research (10/2025)
By following the same steps equation 46 equation
49
obtain
M
(a
a.") S Σ
1 Σ
Pi
P L (a," a("))
(69)
m=
So we have
T
2
B L (a, a("']
L .a, ax) S c(1 (1-8) In M
1=1
32d
22
(1-3) 11-3)22M- +)2
(1 N + (Niobeto
1 Nubeels T + (ne
(1 3)3 26-1
1 3
2
(70)
which concludes to proof of Lemma equation i
Then, we replace in with best model m² in Lemma and Lemma
Summing results of two lemmas lead
T
T
L(a ,a" vT ( M
L (a, t a.r)]]
Σ
(1 + 2n)² + 7 (1+2))²+
a NiabelsT + (Tm.. + 1)+
27m7
1=1
2b
82
In M +
<(1 B)
1-
(1 1)
+ (1 - (3)) (1 + 1)) Nlabels
T 1- 8
(1 - -3)2
+ (Nimbels
22h
1
(1)
K VT
M
(1+ 2n7) +
!
21)
a
+ VT
VT
2 In
M +
VI VT
2 Niablls (1+
VT- - 1M n)?
(1 17) Niabels
+
1
-
20-'Naablee
VT
VT
2b+1
T vT
(71)
where in (i), we set == B =
1 and ne = -
VT
Lemma 5 By defining AT = 2d N! (I
(pin) wh for any t Gk, we can say 14Th A S
bmgg
M 2(N +1) (11 (1 + 1) m.2 3K)
Proof of Lemma The proof begins with the same steps as in the proof of Lemma up to equation equation 54 However, since the weight update rule in EGMOCP differs from that in GMOCP, proceed
26

---

Published in Transactions on Machine Learning Research (10/2025)
by applying the update rule defined in equation 17
Therefore, we have:
M
M
In
π
(pt
jom.s
In
II
(pi+1)
mmg W+++
mm=1
vn==1
M
Pt
M
11
We
W. +
wi Th W 1+1
bm.g
In
+ In
Σ bmgg
In
+
In
Pi+1
#
(1 me)
will
+
2 W
m=11
m=1
We+1
M
M( n. J +o W. M
w." w.
6+1
bm.g
In
In
M1
Ne 10 the We+1 We41 M
wi exp -- (1 3) _ + BLen (af")) W
m=1
M
W
M + Σ
M(1 Me )e) + 11e We
bm.g
In
bm.g
In
M(1
7e m + T7 W++1
W
m
In
c (1 3)
+
L (a.")
(72)
WY
25
By expressing weights at time + 1 in termss of its value time t, we have:
M
Σ ΣM wi exp (-e (1 - B) 20 BLen (a (a.)))
bm.q
In
Σ M
m= with
M(1 Ne) + 11e E -m==1 w/
bm.g In
M(1 - exp
-E 31 1m + BLen (arT))
+ 17. Em= w exp - (1
B) 1mh
2 + B.e (a.
Σ mmnn
whth exp (-e (11 - B) $) + BLen (at)) ))
In
+e (11
1m 2b
+ BLEn (at"))
Emer w
(
M
with exp (-f
+ In Σ Emey W exp (-f(e))
bm.a
Dm=1 w
M
Σmeg witt
m=1
M
M M(1 Ne)u??" Me -m== with
bin.g
M(1 Me )w exp (-f (e)) Me Em= with exp (-f +((()
M
m=1
M
2
bm [s(e)] + (5(e)) + ((e) = 2(N + 1)f(c)
(i)
2(N + 1)e (1 (1- (1 + 1))
M
+ 3K
(73)
n.25
m=
Note that in (i) we replace the 6 (1- + Ben (at²) terms with their maximum value s(e). (ii)
follows equation 33 and the fact that maximum length of every prediction set would be K. By defining
C = 2(N + (1 B)( m) M
+)) we have:
n22"
M
M II
In
II
(p.
)
Omn
we
mg
(pit))
With <= Cie
m=1
mm=1
M II m==
M
N!
(pf
Wi
II
(p241)
Umo
W
mg
M um)g)
M
Am=1
N!
(e0re- 11 (ii)
B2 (c (c-1c-1) -1)
(74)
[IM bm.g!
where (i) follows 1x - yl <= eC
1 1---10
Inx Ingl
C, 200 1]. (ii) follows the definition B3
2e 1 mm b
27

---

Published in Transactions on Machine Learning Research (10/2025)
A.5 Set size Comparison between GMOCP and COMA
According to lemma 6 by replacing the loss function in equation 3 with Len(am) derive upper bound for the prediction set size. We find that the average size of the prediction set at each time constructed by GMOCP, is smaller than the weighted average across all candidate models. The COMA algorithm yields a prediction set size that never larger than twice the weighted average size of candidate models ,according Lemma 2.4 in (Gasparin & Ramdas 2024ab. Therefore, the maximum prediction set size of GMOCP each time & is half that of COMA.
Lemma 6 Expected size of prediction constructed by GMOCP at each time is smaller than or equal to the weighted average of the sizes of the prediction sels corresponding all candidale models.
Len (at")] S
Σ p p Len (a.")
(75)
Proof of Lemma 6 According to equation 50 which demonstrates that the expected loss of the online algorithm is smaller than equal to the weighted average over all models' prediction sets, we replace L (af a²")) with Len(a(n). Thus, it can be concluded that the expected prediction set size at each time is smaller than the weighted average all models.
B Additional Experiments
B.1 Equal Number of Models From Each Training Setting
To evaluate the performance of the proposed methods in scenarios with more weak-performing learning models, we conduct additional experiments using a new set of candidate models that includes three versions each of DenseNet121, GoogLeNet, 18,, and ResNet-50- 1000-mmmmnting to a total of 12 models. For these experiments, we use the CIFAR-100C dataset under gradual distribution shift. The results are reported Table 3 for J E 21, 4} and N (1,3, 5, 7). It can be observed that, across all settings, GMOCP constructs smaller prediction sets in less time while satisfying the desired coverage compared to MOCP. Additionally, EGMOCP achieves the smallest prediction sets compared to all benchmarks.
B.2 CIFAR-10C Dataset
For cases where different selective nodes have equal exploration ratios, experiments on CIFAR-10C with gradual distribution shifts provided. The results, presented in Table show that GMOCP achieves the fastest run time, while FGMOCP constructs the smallest prediction sets.
B.3 TinylmageNet Dataset
Here, we conduct experiments on dataset featuring a gradual distribution shift using TinyImageNet- C, a corrupted version of the TinylmageNet dataset (Le & Yang 2015 that contains 200 distinct classes. For this experiment, the hyperparameters & and kreg are set to 0.01 and 20, respectively. Additionally, the number of sequential data points is 2500, = 0.1, and 3 0.02. Note that since the number of candidate labels is large (200), we report the proportion of prediction sets that include the true label and have a size smaller than 40, instead focusing solely on prediction sets of length Table 5 shows that GMOCP consistently achieves smaller prediction in shorter time compared to MOCP, Additionally, EGMOCP is able to generate smaller prediction sets than both MOCP and GMOCP across all settings.
B.4 Synthetic Dataset
Additional experiments conducted sing synthetic data generated (Hajihashemi Shen 2024), which creates distribution shifts using two distinct transformation sequences. From each sequence, two datasets are generated with random variations to ensure uniqueness across samples. Each dataset. contains 3,000
28

---

Published in Transactions on Machine Learning Research (10/2025)
Table 3: Results on the CIFAR-100C dataset under gradual distribution shifts and utilizing 12 learning models, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results in each column. GMOCP consistently achieves faster runtime compared to MOCP across all
settings. EGMOCP constructs smaller prediction sets and a higher proportion of single-width sets.
Method
Coverage (%)
Avg Width
Run Time
Single Width
MOCP
89.98 + 0.26
27.28 4.34
13.11 0.15
8.25 + 1.93 27.39 = 0.69
COMA
90.01 = 0.01
7.12 = 0.54
16.89 = 0.11
1
1
GMOCP
88,92 1 0.19
25.41
3.12 10.86
5.80 1 0.02
9.22 1 1.15
EGMOCP
88.98 + 0.22
0.03
20.32
2
GMOCP
89.13 1 0.32
22.92
1.05
6.02 0.04
11.08 0.80
EGMOCP
89.12 + 0.14
11.78
0.26
7.29
0.02
19.05 + 0.70
GMOCP
88.94 0.17
22.46
0.58
6.31 0.04
11.04 0.43
EGMOCP
88.97 + 0.25
11.20 0.24
7,51 + 0.02
19.68 = 0.46
3
1
GMOCP
89.60 + 0.26
25.23 +: 2.45
7.29 + 0.06
8.37 1 0.99
EGMOCP
89.63 + 0.24
10.10
0.30
10.25 0.03
22.10 0.79
2
GMOCP
89.60 0.39
22.35
1.05
7.75 0.06
11.08 0.70
EGMOCP
89.74 + 0.23
9.27 + 0.23
10.73 - 0.04
23.26 = 0.54
GMOCP
89.61
8.47
11.19 0.62
EGMOCP
89.63 + 0.33
8.47 + 0.21
11.43 = 0.05
23.59 = 0.61
5
GMOCP
89.54 + 0.30
24.08 1.00
8.52 + 0.09
9.34 + 1.34
EGMOCP
89.72 = 0.38
8.95 + 0.25
12.91 0.06
23.97 0.58
2
GMOCP
89.75 0.38
23.87 1.36
9.09 0.05
9.95 1 0.74
EGMOCP
89.63 + 0.24
8.17 = 0.15
13.01 0.12
24.58 = 0.42
GMOCP
EGMOCP
89.97 + 0.16
7.82 1 0.23
15.73 0.09
24.93 0.47
7
1
GMOCP
89.79 + 0.29
22.72 + 2.99
9.18 0.41
10.36 + 1.82
EGMOCP
89.68 + 0.29
8.19 + 0.18
13.73 0.14
21.99 0.44
2
GMOCP
89.70 0.28
22.52 1.50
10.32
10.64 0.66
EGMOCP
89.75 + 0.35
7.60 = 0.13
0.09 11.92
25.66 = 0.38
GMOCP
EGMOCP
89.73 1 0.23
7.30 1 0.17
0.06 16.49
25.81
0.40
9
1
GMOCP
89.81 + 0.29
23.09
2.62
9.79
0.17
10.34 = 1.26
EGMOCP
89.73 + 0.29
7.32 + 0.10
14.41
0.22
25.97 0.46
2
GMOCP
89.69 1 0.30
25.23
2.44
11.35
0.17
8.70 1 1.53
EGMOCP
89.72 + 0.35
7.25
+ 0.19
16.27
= 0.10
26.07 = 0.43
GMOCP
EGMOCP
89.62 1 0.30
7.01 1 0.15
18.12
0.08
26.41 1 0.52
images across 20 classeswhich creates distribution shifts using distinel transformation sequences. From each sequence, two datasets are generated with random variations to ensure uniqueness across samples. Each dataset contains 3,000 images across 20 classes. Gradual shifts are simulated by sampling within a single transformation type, while sudden shifts are modeled by alternating between datasets from different transformations. Results are presented in Table G. Tt can be observed that the two algorithms proposed in this work, GMOCP and EGMOCP, achieve smaller prediction sets compared to the benchmarks across all settings. Please note that, in this set of experiments, there are no prediction sets of size one that cover the true label; therefore, this metric is equal to zero for every setting.
B.5 Comparison with single model based methods
In this subsection, we compare multi-model based methods with recent adaptive conformal prediction meth- ods designed for ouline environments. We include several single-model based methods in the comparison,
such ACI Giibss & Candès 2021), FACI (Gibbs & Candès 2024), DECAY (Angelopoulos al. 2024
and SAOCP [Bhatagar et al. 2023 To distinguish between different configurations of single-model meth- ods, we use specific suffixes. For instance, ACI-120D refers to the version using high-performance models, ACI-10R denotes a mediunn-errformance model, and ACI-IR represents a low-performing model. As ob- served from the table | both GMOCP and EGMOCP outperform the medium periiummeerfommnnce single-model basclines terms of average width and single-width ratio. Morcover, EGMOCP produces more efficient pre- diction sets smaller average widths and higher single-width ratios even compared to the high-performanee configurations of all single-model methods.
29

---

Published in Transactions on Machine Learning Research (10/2025)
Table 4: Results on the CIFAR-1OC dataset under gradual distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers indicate the best performance in each column. GMOCP consistently achieves faster runtime compared to MOCP across all settings. EGMOCP constructs smaller prediction sets and a higher proportion of single-width sets.
J
Method
Coverage (%)
Avg Width
Run Time
Single Width
MOCP
90.03 + 0.30
2.07 + 0.35
9.41 0.08
48.00 = 7.84
COMA
90.00 = 0.02
1.49 = 0.07
11.02 = 0.03
61.39 + 2.92
1
GMOCP
89.36 1 0.21
1.90 1 0.27
4.29 1 0.02
48.14 1 4.22
EGMOCP
89.37 + 0.22
1.52 0.03
0.02
57.48
1.58
2
GMOCP
89.39 1 0.29
1.79 1 0.03
4.48 0.02
52.06 0.72
EGMOCP
89.40 + 0.23
1.57 + 0.02
5.68 + 0.12
55.95 + 1.14
GMOCP
89.26 0.15
1.76 0.04
4.85 0.05
52.78 0.90
EGMOCP
89.27 + 0.12
1.53 - 0.02
6.13 + 0.08
56.74 = 0.96
3
GMOCP
89.79 + 0.26
1.78 + 0.17
5.51 + 0.06
50.97 + 3.41
EGMOCP
89.83 + 0.30
1.50 + 0.02
0.02
58.98 1.07
2
GMOCP
026
1.78 0.04
6.00 0.04
53.03 1.37
EGMOCP
89.76 + 0.36
1.48 + 0.01
9.04 0.03
59.13 = 0.86
GMOCP
89.69 0.28
0.04
6.80 0.05
54.26 1.25
EGMOCP
89.53 + 0.28
1.44 = 0.02
9.85 + 0.02
60.17 = 0.98
5
GMOCP
89.72 + 0.17
1.85 + 0.15
6.35 + 0.12
51.02 + 2.96
EGMOCP
89.82 - 0.26
1.48 = 0.02
10.91 0.03
59.39 0.83
2
GMOCP
89.80 0.35
1.78 0.06
7.24 0.05
52.62 1.72
EGMOCP
89.87 + 0.18
1.44 - 0.01
11.65 = 0.03
60.30 = 0.75
GMOCP
EGMOCP
89.97 + 0.28
1.43 1 0.01
12.86 0.04
60.67 1 0.59
Table 5: Results on the TinyImageNet dataset under gradual distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results each column. Bold numbers indicate the best performance in each column. GMOCP consistently achieves faster runtime compared to MOCP across all scttings. EGMOCP constructs smaller prediction sets.
Method
Coverage (%)
Avg Width
Run
Width < 40
MОCP
89.61 1 0.48
170.59 1 1.03
3.01 1 0.01
0.11 0.05
COMA
90.00 0.05
161.61 t 1.56
3.91 0.01
0.34 0.12
2.03
EGMOCP
87.67 = 0.35
164.51 + 1.16
2.31 = 0.01
0.15 + 0.06
2
GMOCP
87.81 = 0.40
165.37
+ 2.08
2.12 = 0.03
0.20 0.18
EGMOCP
87.95 1 0.36
165.43
1 1.33
2.44 0.04
0.20 0.10
GMOCP
87.54 + 0.27
165.28
1 1.77
2.26 + 0.01
0.16 1 0.11
EGMOCP
87.65
0.33
164.28 1.75
2.58 0.00
0.18 0.17
GMOCP
167.66
1.43
2.38 0.02
0.11
EGMOCP
88.86 = 0.12
166.97 + 1.73
3.12 0.01
0.16 H 0.09
2
GMOCP
88.98 + 0.38
168.01
+ 1.29
2.56 + 0.03
0.08 0.06
EGMOCP
89.04 0.53
167.07
1.50
3.34 0.05
0.19 0.12
4
GMOCP
88.98 - 0.34
168 98
4 1.01
2.85 0.02
0.12 0.07
EGMOCP
167.24 1.41
0.01
B.6 Candidate models with little variance analysis
In this subsection, we provide additional experiments evaluate how the proposed methods perform when all candidate models have similar quality. To do this, we select six high-performance models introduced in Section 4 As shown in Table GMOCP reduces the computational complexity, while EGMOCP still produces efficient prediction sets with smaller average widths and higher single- width ratios, even when there is little variance among the models.
Additionally, we note that "Variance introduced by model selection" and "instability under distribution shifi" can impact coverage. By comparing Table S and Table [ it can be observed that changing the distribution shift from sudden to gradual and employing candidate models with low variance in quality results in improved coverage. For example, for EGMOCP with (J n 1), the coverage improved from 88.99 (Table 1 89.43 (Table 8
30

---

Published in Transactions on Machine Learning Research (10/2025)
Table 6: Results on the Synthetic dataset, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results in cach column. GMOCP consistently achieves faster runtime compared to MOCP across all settings. EGMOCP constructs smaller prediction sets and higher proportion of single-width width sets.
N
Method
Coverage (%)
Arg Width
Run Time
Single Width
MOCP
89.92 0.28
18.00 + 0.01
13.57 0.18
0.00 # 0.00
COMA
$9.99 = 0.01
18.01 = 0.04
16.09
= 0.05
0.00 # 0.00
1
GMOCP
89.24 1 0.12
17.88 1 0.06
5.96 1. 0.05
0.00 1 0.00
EGMOCP
89.18 0.15
17.84 + 0.12
+ 0.00
GMOCP
89.26
0.15
17.86 1. 0.07
6.17
1. 0.05
0.00 1 0.00
EGMOCP
89.27 + 0.19
17.85 + 0.07
22.70
0.44
0.00 + 0.00
3
1
GMOCP
89.60 = 0.20
17.96 + 0.04
7.17 + 0.27
0.00 + 0.00
EGMOCP
89.53
17.92
2
GMOCP
89.60 + 0.17
17.96
+ 0.02
7.76 1 0.08
0.00 1 0.00
EGMOCP
89.47 0.22
17.93 0.04
28.37
0.00 = 0.00
5
1
GMOCP
89.77 = 0.27
17.95 + 0.02
7.88 + 0.45
0.00 + 0.00
EGMOCP
89.70
17.94
0.56
0.00 0.00
2
GMOCP
89.73 = 0.26
17.97 = 0.04
8.90
- 0.14
0.00 + 0.00
EGMOCP
0.03
32.90
0.60
0.00
Table 7: Results on the CIFAR-100C dataset under sudden distribution shifts, comparison of GMOCP(N
3. 1) and EGMOCP (N 5, J = 4) single model based algorithms. EGMOCP yields more efficient prediction sets smaller average widths and higher singlo-width ratios- even compared to high-performance single-model baselines.
Coverage (%)
Avg Width
Single Width
GMOCP EGMOCP
89.55 = 0.28
10.68 +: 1.05
6.05 + 0.04
23.45 2.53
89.43 0.27
6.18 0.14
12.97 0.05
29.91 0.47
MОCP
12.63 3.53
9.37 + 0.05
22.43
COMA
90.00 + 0.01
8.36 + 0.95
11.23 + 0.07
28.60 + 1.83
FACI-120D
89.66 0.36
6.97 1.07
4.49 + 0.02
27.82 + 0.91
FACI-1OR
89.64 1 0.34
12.88 1: 1.85
4.47 1 0.03
5.30 0.51
FACI-IR
89.75 0.29
49.81 + 0.65
4.48 + 0.04
0.00 0.01
ACI-120D
0.34
3.14 +
ACI-10Rt
89.95 = 0.02
15.52 1: 0.69
3.16 1: 0.03
5.43 1 0.46
ACI-R
89.96 = 0.03
51.76 1 0.72
3.15 1
DECAY-120D
89.76 - 0.01
6.42 0.10
1.41 1: 0.01
28.07 1: 0.53
DECAY-IOR
89.75 0.10
12.12 + 0.33
1.40 + 0.02
4.91 0.51
DECAY-1R
89.80 = 0.08
19.72 + 0.61
1.41 - 0.02
0.01 + 0.01
SAOCP-120D
88.65 1 0.15
7.26 0.18
25.52 1 0.03
26.99 1 0.66
SAOCP-IOR
88.50 = 0.18
13.27 + 0.38
25.52 0.07
SAOCP-1R
88.29 0.10
48.74 1 0.79
25.51 0.06
0.00 0.00
B.7 Local coverage comparison
In this subsection, we present a new set of experiments to evaluate the empirical coverage of our algorithms over small windows, rather than across the entire time horizon. Specifically, we report the local coverage using a window size of 100 in Table As shown, both of proposed algorithmss, GMOCP and EGMOCP, achieve local coverage close to the target level. This result validates the ability of methods to quickly adapt to abrupt distribution shifts.
B.8 Comparison of set size at each time step
We conducted an experiment compare the prodiction set sizes generated by each algorithm over the full time horizon (6000 data points). As shown in Figure FGMOCP achieves the smallest average prediction
31

---

Published in Transactions on Machine Learning Research (10/2025)
Table 8: Results on the CIFAR-100C dataset under gradual distribution shifts, where candidate models have little variance in quality. EGMOCP yields more efficient prediction scts, smaller average widths and higher single-width ratios.
Method
Coverage (%)
Avg Width
Run Time
Single Width
MOCP
89.89
COMA
90.00 + 0.02
7.21 + 0.31
9.05 + 0.08
28.84 + 1.67
2
GMOCP
89.49 + 0.13
5.62 + 0.13
4.53
0.02
29.83 = 0.54
EGMOCP
89.46 + 0.15
5.37 1 0.14
5.69
0.02
30.01 1 0.79
4
GMOCP
89.46 + 0.25
5.61
0.17
4.71
0.05
29.85 0.63
EGMOCP
89.43 + 0.19
5.61 + 0.14
5,80 + 0.02
30.05 = 0.64
3
2
GMOCP
89.86 + 0.23
5.06 + 0.14
6.99 + 0.03
29.06 + 0.68
EGMOCP
89.76 + 0.22
5.55
0.13
8.76 0.04
30.28 + 0.63
4
GMOCP
89.99 + 0.21
5.62 + 0.15
6.71 0.05
29.88 0.77
EGMOCT
89.81 1 0.25
5.58 1 0.19
9.49 1 0.03
30.13 1.03
Table 9: Results on the CIFAR-100C dataset under sudden distribution shifts, showing empirical coverage over local windows (window size 100). Both GMOCP and EGMOCP maintain local coverage close to the desired level %90
Method
Coverage (%)
Local Coverage (%)
МОCP
89.71
0.37
89.79 0.38
COMA
90.00 0.01
89.99 0.01
GMOCP
0.21
89.14 0.21
EGMOCP
89.10
0.28
89.14 + 0.30
GMOCP
RGMOCP
89.03
0.17
89.09
+ 0.18
GMOCP
89.04
0.21
89.08
0.23
EGMOCP
88.99 0.21
89.01
0.25
GMOCP
EGMOCP
89.38 0.22
89.46 1 0.22
89.59
EGMOCP
89.29 0.21
89.36
+ 0.23
GMOCP
89 61 0.34
89.72
0.33
EGMОCP
89.38 0.31
89.45
0.32
GMOCP
EGMOCP
89.46 0.36
89.54
1 0.37
89.61
EGMOCP
89.44 0.28
89.50
+ 0.29
GMOCP
89.73 0.31
89.82
0.33
EGMOCP
89.43 0.27
89.49
0.28
set size among all benchmarks. COMA exhibits significant. fluctuations, rosulting in large prediction sets
certain timesteps.
B.9 Experimental results for CIFAR10-C
We conducted experiments on the CIFAR-10C dataset under two different. settings. Table 10 corresponds to the sudden distribution shift scenario with equal exploration ratios across selective nodes. Table [I presents results for the gradual distribution shift scenario with unequal exploration ratios, as detailed in Section
32

---

Published in Transactions on Machine Learning Research (10/2025)
30
COMA
MOCP
25
GMOCP
EGMOCP
20
get Size
15
10
1000
2000
3000
4000
5000
6000
Epochs
Figure 3: Evaluation of prediction set sizes constructed by multi-model methods over 6000 timesteps. On average, EGMOCP produces smaller prediction sets compared to all other benchmarks. The average predic- tion set sizes for COMA, MOCP, GMOCP, and EGMOCP across the 6000 timesteps are 7.19, 13.26, 11.00, and 6.06, respectively.
Table 10: Results on the CIFAR-10C dataset under sudden distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results each column. GMÒCP consistently achieves faster runtime compared MOCP across all settings. EGMOCP constructs smaller prediction sets and higher proportion of single-width sets.
Method
Coverage (%)
Avg Width
Time
Single Width
89.63 + 0.26
1.94 0.30
9.49 0.06
50.04 6.54
COMA
89.99 = 0.01
1.63 = 0.10
10.89 = 0.02
57.56
2.35
GMOCP
89.09 +: 0.16
1.81 + 0.13
4.31 0.03
50.65 2.35
EGMOCP
88.99 + 0.17
1.53 + 0.03
5.51 + 0.02
57.04 + 1.41
GMOCP
1
0.03
EGMOCP
89.12 + 0.28
1.58 + 0.02
5.67 + 0.01
56.43 = 1.13
GMOCP
88.89 + 0.21
1.75 - 0.02
4.95 0.01
53.39
1.03
EGMOCP
88,91 + 0.18
1.54 + 0.02
6.22 0.09
57.01
1.20
GMOCP
89.56 + 0.29
1.74 0.16
5.41 0.11
52.03 3.45
EGMOCP
39.52 + 0.30
1.50 + 0.02
8.49 - 0.02
59.24
1.18
2
GMOCP
89.52 +
+ 0.04
53.27
EGMOCP
89.35 - 0.31
1.49 = 0.01
9.00 0.04
59.01
0.93
4
GMOCP
89.57 + 0.36
1.71 + 0.03
6.33 0.08
53.94
1.26
EGMOCP
89.36 0.17
1.45 0.02
9.72 0.04
59.97
0.89
GMOCP
89.72 + 0.24
1.82 0.22
6.72 0.07
52.13 5.11
EGMOCP
89.53 + 0.23
1.49 + 0.01
10.80 = 0.04
59.13 + 0.76
2
GMOCP
89.59 + 0.24
+ 0.05
0.07
52.32
EGMOCP
89.58 + 0.21
1.45 + 0.02
11.62 0.03
60.13 + 1.03
4
GMOCP
89.67 + 0.25
1.81 + 0.04
8.31 0.04
52.64 0.65
EGMOCT
89.55 1 0.27
1.44
0.01
12.65 0.04
60.00 0.53
33

---

Published in Transactions on Machine Learning Research (10/2025)
Table 11: Results on the CIFAR-10C dataset under gradual distribution shifts, evaluated across different values of N and J. The target coverage is 90%. Bold numbers denote the best results in each column. GMOCP consistently achieves faster runtime compared to MOCP across all settings. EGMOCP constructs smaller prediction sets and higher proportion of single-width sets.
N
Method
Coverage (%)
Avg Width
Run Time
Single Width
MOCP
90.03
2.07 0.35
8.83 0.04
48.00
7.84
COMA
90.02 = 0.02
1.49 0.07
10.76 + 0.04
61.39
2.92
GMOCP
89.36 + 0.21
1.90 0.27
4.32 + 0.01
48.14 +: 4.22
EGMOCP
89.37 + 0.22
1.52
5.51
57.48
2
GMOCP
89.37 = 0.17
1.78 0.03
4.39 + 0.03
52.30
1.27
EGMOCP
89.35 +: 0.21
1.59 0.02
5.58 0.01
$5.57
1.19
GMOCP
1.74
EGMÖCP
89.28 + 0.16
1.55 0.02
5.91 + 0.01
56.69 + 1.11
GMOCP
89.79 + 0.25
1.78 0.17
5.41 + 0.06
50.97 + 3.41
EGMOCP
89.83 + 0.30
1.50 0.02
8.44
58.98 1.07
GMOCP
89.78 + 0.32
1.78 0.04
6.06 = 0.05
52.64 1.23
EGMOCP
89.65 1 0.22
1.37 0.01
9.08 0.05
61.51 0.77
GMOCP
EGMÖCP
89.60 1 0.35
1.41 0.02
9.73 1 0.02
60.68 1.21
GMOCP
89.72 + 0.17
1.85 0.15
6.71 0.11
51.02 + 2.96
EGMOCP
89.82 + 0.26
1.48
0.02
10.88 + 0.01
59.39
0.83
GMOCP
89.73 1 0.26
1.80
0.03
7.33 1 0.03
52.27
1.13
EGMOCP
89.87 1 0.36
1.35
0.01
11.86 1 0.03
62.23
0.57
GMOCP
89.88 0.21
1.80
8.47
52.49
0.92
EGMOCP
89.99 1 0.24
0.02 1.38
12.84 1 0.11
61.84
0.55
34


Reviews:
[{"review_id": "uVJsKn4Dsw", "reviewer": "Reviewer_QDNW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengthes:**\n- Conformal prediction with multiple models is an interesting and relevant problem, especially as the use of diverse model ensembles becomes increasingly common. Proposing a method that improves computational efficiency is valuable, as it enables scaling to incorporate a larger number of models.\n- The paper provides a theoretical analysis of the coverage rate, supporting the validity of the proposed method.\n- The manuscript is well-structured.\n\n**Weaknesses:**\n- On computational efficiency: One of my main concerns about the paper is the significance of the computational improvement achieved by the proposed methods. As stated in Section 3.2, the computational cost of the GMOCP method is $O(MNJ)$. It is unclear to me how substantial the improvement is, given that the cost scales linearly with the number of candidate models $M$, and may still become prohibitive when $M$ is large.\n- About the Theorem 1: It seems to me that some parameters in the theorems are not clearly specified. For example, it is somewhat surprising that the bound appears to be independent of $J$ and $N$. Does this imply that the choices of $J$ and $N$ do not affect the coverage and regret guarantees of the proposed method? In addition, some algorithmic parameters are not well specified. For instance, is a particular design or selection of $\\epsilon$ (and $\\beta$ in Theorem 3) required to achieve the stated bounds?\n- About the experiments: The experiments are a bit counterintuitive to me. Regarding the running time of the EGMOCP method, the case with $J = 4$ shows even lower running time than $J = 2$, which does not align with the $O(MNJ)$ computational cost stated in the analysis. Could you explain why this is the case?\n- In Section 4.1, the paper mentions that \"the parameters $epsilon$, $eta$, and $beta$ are selected through grid search...\". I am wondering what data was used to perform the grid search. Since the problem is set in an online learning context, it is unclear whether an additional validation set was available for this purpose.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies online conformal prediction, where a prediction set is generated to ensure the desired coverage rate of the true label. It focuses on the case where there is a set of candidate models with varying qualities. The main contribution of the paper is a method that efficiently selects a model for constructing the prediction set, based on a bipartite graph and carefully designed feedback. Regret analysis shows that the proposed method can achieve the desired coverage guarantee, and experimental results validate its effectiveness.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Could you provide more evidence on how the proposed method is computationally efficient and can scale to situations where $M$ is large? (See the first point in the weaknesses section for more details.)\n* Could you discuss how $N$ and $J$ affect the theoretical guarantees of the proposed method?\n* Why does EGMOCP have lower running time for $J = 4$ than for $J = 2$?\n* How did you choose the parameters used in the experiments?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NnQaC6GwNC", "reviewer": "Reviewer_dmgy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe dynamic selection of the candidate set of models based on the online feedback seems quite interesting as it seems more flexible than prior methods, and able to adapt efficiently the candidate set based on the observed coverage error.  The work is well organized, clearly motivated and  appropriately placed into contemporary literature. The paper seems nicely written and clear. The theoretical and experimental results seem to sufficiently  support the proposed method. \n\n**Weaknesses**\n\nIn theorems 1 and 3 seems to allow for a negative initial miscoverage rate that seems somewhat counterintuitive, while it is unclear how is this applicable in practice. There are several typos and a few undefined terms throughout the manuscript (please refer to changes for details).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on the problem of adaptive online conformal prediction, where at each time step conformal prediction is deployed using a model chosen from a set of candidate models. The authors propose a dynamic graph-based selection schema to select the candidate set of models as well as the final model and its adaptive coverage probability at each time step. This schema consists of a bipartite time evolving graph representing multiple selections of models that can be chosen as the candidate set. The authors construct each selection of models as well as choose the final model using probabilistic rules that are updated per time step based on the realized coverage error. In addition, they suggest an extension of their update rule to encourage smaller prediction sets. The authors provide theoretical bounds on the coverage error and regret of both variants of their method and evaluate them against competitive baselines on several datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Definitions/Theory**\n1. In theorem 1,  the values of $\\eta$ seem to be positive according to the proof in appendix A.1, where $\\eta$ is the learning rate as defined in eq. 5. It would be helpful to clarify this on Theorem 1 as well (e.g., by adding a clarification that $\\eta > 0$) and also clarify what would mean--both intuitively and in practice--to select an initial miscoverage rate  that is negative, i.e., $\\alpha_{1}^{m} = -\\eta$ for some model $m$. Similarly, it would be helpful to clarify what would it mean to allow for a miscoverage rate that is larger than $1$ by setting $\\alpha_{1}^{m} = 1 + \\eta$.  The same applies for theorem 3. (critical)\n2. The authors use $K$ for the number of labels as well as in the proof of theorem 1. Using a different parameter would prevent ambiguity. (minor)\n3. The term $b_{m,q}$ first introduced above theorem 1, seems to be first defined below eq. 46 in the Appendix. This is rather confusing and the authors should either point to the appendix whenever $b_{m,q}$ is first introduced or define it inline. (minor)\n\n\n**Typos/Clarifications**\n\n1. It would be important to clarify the train/test splits used for the CIFAR  datasets. (critical)\n2. In page 3 end of introduction in section 3 there are double ‘.’ (minor)\n3. Above equation 6, the authors perhaps could write ‘The parameter $\\eta$’ instead of directly writing ‘. $\\eta$’ (minor)\n4. The authors should define epsilon in equation 7 (minor)\n5. In section 3.1 the authors should explain the acronyms they are using (e.g. PMF, SF-OGD) the first time they introduce them (minor)\n6. Throughout the manuscript ‘Miss coverage’ —> ‘miscoverage’ (minor)\n7. Theorem 3 typo ‘$C-1$’ —> $C_1$ (minor)\n8. In the caption of Table 1 there is a duplicate comment on the significance of bold text. (minor)\n\n**Suggestions for improvement** \n\n1. The title looks a bit hard to read. Perhaps ‘multimodel online conformal prediction with graph-structured feedback’ would be a bit easier to parse. \n2. In the experimental evaluation, the authors may like to present results on the same dataset \n3. In Figure 2, it would be helpful to show also the average size of the other baselines to be able to see the advantage of the proposed method.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "t7Xub6tQ7T", "reviewer": "Reviewer_djnH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\nThis paper introduces two algorithms, GMOCP and EGMOCP, for online conformal prediction. The key innovation lies in dynamically selecting a subset of models at each timestep. To the best of my knowledge, this is the first work to integrate graph-based combinatorial selection with conformal prediction in an online setting, making it a novel and well-motivated contribution. The authors support their approach with rigorous theoretical analysis, establishing valid marginal coverage guarantees and sublinear regret bounds, both of which are standard desiderata in the online conformal prediction literature. The empirical evaluation is conducted across multiple datasets (CIFAR-10C and CIFAR-100C), corruption types, and model architectures.  Results consistently show that GMOCP and EGMOCP outperform existing baselines such as MOCP and COMA in terms of average prediction set width and computational efficiency. Overall, this work represents a meaningful advancement in the field of online conformal prediction and is likely to be of strong interest to the TMLR community, particularly to researchers working on conformal prediciton. \n\n### Weaknesses\nIn my opinion, some of the claims in this paper is not well-supported. In particular, the authors propose to select a subset of effective models and incorporate the prediction set size as feedback, claiming that this reduces computational complexity and improves prediction efficiency. While this is a compelling intuition, the paper lacks a formal analysis or theoretical justification of these benefits. For instance, there is no analysis of prediction set efficiency comparing the proposed methods to existing ensemble conformal prediction baselines. Given the theoretical emphasis in the conformal prediction community, such guarantees are important and should be provided. \n\nBesides, the experiments results lack comparison with several important baseline methods such as standard adaptive conformal inference (ACI) with both constant learning rate [1] and dynamic learning rates [2] and Strongly Adaptive Online Conformal Prediction (SOACP) [3]. These methods, though are not multi-model algorithms, are important baselines in online conformal prediction. This lack of comprehensive baselines weakens the validity of the empirical superiority in a broader extent.\n\nIn addition, the empirical results raise concerns about the coverage validity of the proposed methods. A central claim of the paper is that both GMOCP and EGMOCP maintain valid coverage guarantees. In Tables 1 and 2, GMOCP and EGMOCP often produce coverage rates that deviate noticeably from the target level of 90%, unlike MOCP and COMA. For example, in Table 1, for $N=1$ and $J=4$, EGMOCP reports a coverage of only 88.99 $\\pm$ 0.21, which deviates significantly from the target level of 90. These discrepancies are not addressed or explained in the paper, raising questions about the practical reliability of the methods in achieving guaranteed coverage. \n\n### References\n[1] Gibbs I, et al. Adaptive conformal inference under distribution shift. NIPS 2021.\n\n[2] Angelopoulos A N, Barber R F, Bates S. Online conformal prediction with decaying step sizes. ICML 2024.\n\n[3] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces two novel online conformal prediction algorithms: Graph-structured feedback Multimodel Ensemble Online Conformal Prediction (GMOCP) and its extension, Efficient GMOCP (EGMOCP). In particular, GMOCP employs a bipartite graph structure to identify a subset of effective models at each time step, aiming to reduce computational cost and avoid using poor-performing models. EGMOCP enhances GMOCP by incorporating the prediction set size into the model selection process, resulting in small and informative prediction sets. The authors provide regret and coverage bounds for both methods, demonstrating sublinear regret and bounded deviation from target coverage. Experiments on CIFAR-10C and CIFAR-100C under both sudden and gradual distribution shifts show that GMOCP and EGMOCP achieve smaller prediction sets and lower runtime than several multi-model conformal prediction baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I remain open to being convinced if certain suggestions are not feasible or appropriate.\n\n1. A theoretical analysis of both computational complexity and prediction efficiency should be provided to substantiate the corresponding claims. This could involve comparing the proposed methods against full-model ensembles such as MOCP.\n2. The experimental evaluation should include additional baseline methods such as ACI and SOACP, to support the claimed improvements in computational complexity and prediction efficiency.\n3. The paper should offer a reasonable explanation for the observed coverage deviations of GMOCP and EGMOCP from the target level, such as variance introduced by model selection, instability under distribution shift. Additionally, I encourage the authors to discuss or propose strategies for mitigating these deviations.\n4. While the paper highlights that multi-model online conformal prediction methods can suffer due to the poor performance of some candidate models, it remains unclear how the proposed approach behaves when all candidate models perform similarly. I would like to see additional analysis or experiments examining the method's effectiveness in such scenarios, where there is little variance in model quality.\n5. The paper could benefit from an evaluation of the local performance of the proposed methods. One notable advantage of multi-model approaches is their ability to quickly adapt to dynamic environments, potentially achieving local coverage that is close to the target level of $1-\\alpha$ [1]. It would be insightful to see whether the proposed methods, GMOCP and EGMOCP, can achieve comparable local coverage performance to the baseline methods, especially in situations where models are exposed to rapidly changing distributions.\n6. The introduction currently provides an incomplete and somewhat high-level overview of online conformal prediction (OCP), which is difficult to follow for readers who are not already familiar with the topic. I recommend that the authors offer a more comprehensive introduction to the OCP framework.\n\n### References\n[1] Bhatnagar A, et al. Improved online conformal prediction via strongly adaptive online learning. ICML 2023.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)