OCCAM: Towards Cost-Efficient and Accuracy-Aware Classification Inference
Authors: Dujian Ding
Bicheng Xu
Laks V. S. Lakshmanan
Venue: ICLR 2025 Poster (2025)
Keywords: Efficient ML
Hybrid ML Inference
Classification
Primary area: optimization
TL;DR: A principled approach, OCCAM, to compute the optimal ML model assignment over classification queries so that the aggregated accuracy is maximized, under user-specified cost budgets.

Abstract: Classification tasks play a fundamental role in various applications, spanning domains such as healthcare, natural language processing and computer vision. With the growing popularity and capacity of machine learning models, people can easily access trained classifiers as a service online or offline. However, model use comes with a cost and classifiers of higher capacity (such as large foundation models) usually incur higher inference costs. To harness the respective strengths of different classifiers, we propose a principled approach, OCCAM, to compute the best classifier assignment strategy over classification queries (termed as the optimal model portfolio) so that the aggregated accuracy is maximized, under user-specified cost budgets. Our approach uses an unbiased and low-variance accuracy estimator and effectively computes the optimal solution by solving an integer linear programming problem. On a variety of real-world datasets, OCCAM achieves 40% cost reduction with little to no accuracy drop.

Published as a conference paper at ICLR 2025
OCCAM: TOWARDS COST-EFFICIENT AND ACCURACY- AWARE CLASSIFICATION INFERENCE
Dujian Ding, Bicheng Xu, Laks S. Lakshmanan University of British Columbia du frojiancoe daingggmail..cm
(bichengx, laks] ubc.ca
ABSTRACT
Classification tasks play fundamental role various applications, spanning domains such as healthcare, natural language processing and computer vision. With the growing popularity and capacity of machine learning models, people can easily access trained classifiers use comes with a cost and classifiers higher capacity (such as large foundation models) usually incur higher inference costs. To harness the respective strengths of different classifiers, we propose a principled approach, OCCAM, to compute the best classifier assignment strategy over classification queries (termed the optimal model portfolio) so that the aggregated accuracy is maximized, under user-specified cost budgets. Our approach uses an unbiased and low-variance accuracy estimator and effectively computes the optimal solution by solving an integer linear programming problem. On variety of weal-world datasets, OCCAM achieves 40% cost reduction with little to accuracy drop.
service online offline. However, model
INTRODUCTION
Classification is fundamental task with numerous real-world applications, from medical diag- nosis (Abhisheka et al. 2024) to natural language processing (Kowsari et al., 2019) and object recognition (ou et al. 2023). In recent years, a wealth of pre-trained classifiers has become accessi- ble, both online and offline, at varying costs. For instance, Google's Facial Detection service (Google) charges $1.50 per 1,000 images, providing developers with a reliable solution for face recognition. Simultaneously, a variety of open-source models, such as ResNet (He et al.] (2016), Vision Trans- former (Dosovitskiy et al., 2020), and Swin Transformer (Liu et al. 2021). 1), have been made available for developers to integrate into their services.
On the one hand, empirical evaluations conducted in (Su et al. 2018) and our independent assessment (see Figure Lap, consistently indicate that smaller/cheaper models tend to exhibit gap in classification accuracy compared to their larger counterparts. On the other hand, though larger neural models are equipped with higher capacity, they often come with higher costs, c.g., hardware usage and latency, for both training and inference. This can potentially impose an enormous cost on both end users of classification services and the service providers (e.g., Google Amazor and Microsof
Confronted with the general trade-off between classification accuracy and inference cost, we advocate hybrid inference framework which seeks combine the advantages of both small and large models. Specifically, we study the problem, how to optimally select and assign models to different classification queries in order to achieve the highest accuracy while adhering to a limited cost budget? We formally refer to it as the optimal model portfolio problem (details in Section 3). Our approach is motivated by the observation that while small classifiers typically have reduced accuracy over the population, they can still agree with large classifiers on certain queries large proportion of the time, which suggests the existence of subset of "easy" queries on which even small classifiers can make the right prediction. This is also illustrated in Figure Tb where we plot the frequency with which different classifiers successfully make the right prediction on the same classification queries. Taking
"https///wss.mmaat http:://ww.aaaazz..ocoommmacccc com/maccinn-lcamin https//suuioo.zzrreee

---

Published as a conference paper at ICLR 2025
resneti8
089091009000 00000000030000000
Accuracy (%)
80-
resmet34
08P09109200000
92004433
3.95
resnet50
Accuracy (%6
2.90
75-
resee
091093094
75
swin 2
770830050000
0.550.5
0.65
70
swin_v2_s 75.0 950.0
2.00
65
swin_v2_B 75 360390000.000
Random OCCAM
resmett
resnet34
resne500
resn 001
swin v2_r
swin v2.5
swin V2
resnee
resmee14 menedo
meretts $2.5
0.2
0.4
0.6
0.8
100
Normalized Cost Budget
(a) Accuracy v/s classifier sizes. (b) Classifier agreement frequency.
(c) OCCAM results.
We investigate Tiny ImageNet dataset consisting of 200 classes (see Section 5 for details). We observe that (a) smaller classifiers (e.g.. ResNet-18) generally yield lower accuracy, (b) small classifiers can agree with large classifiers at high frequency (each entry indicates the percentage of queries on which the classifier on the row makes the right prediction and so does the classifier on the column), (c) our approach OCCAM achieves 20% cost reduction with less than 1 1% accuracy drop.
Figure I:
image classification as an example, a small classifier, ResNet- 18 (He al., 2016). can correctly classify 75% of the images on which the large classifier, SwinV2-B (Liu et al. 2022). makes the right prediction, suggesting that we can replace Swin with ResNet-18 on these image queries, saving significant inference costs without any accuracy drop (details in Section
With this insight, we propose a principled approach, Optimization with Cost Constraints for Accuracy Maximization (OCCAM), to effectively identify easy queries and assign classifiers to different user queries to maximize the overall classification accuracy subject to the given cost budgets. Previous work (Chen et al. 2022) trains ML models to select classifiers, which requires sophisticated con- figuration and lacks performance guarantees that are critical in real-world scenarios. In this paper, by leveraging weak assumptions, such the well-xeparation assumption (Yang et al. 2020), demonstrate that it is possible to compute optimal model assignments with statistical guarantees. As an example, in previous work (Yang et al., 2020),, the image classification task (Singh & Singh 2020), a critical and well-studied application of classification. has been observed to empirically satisfy the well-separation assumption, which is also corroborated by our own independent evaluation (see Appendix I. The intuition is that for well-separated classification problems such as image classification, we can learn robust classifiers that have similar performance on similar queries. By leveraging the specific structure of well-separated classification tasks, we develop an unbiased and low-variance estimator for classifier test accuracy with asymptotic guarantees. For each classification query, compute its nearest neighbours in pre-computed samples to estimate the test accuracy for each classifier. To our best knowledge, we are the first to open up the black box by developing white-box accuracy estimator for MI. classifiers with statistical guarantees. Next, armed with our classifier accuracy estimator, we compute the optimal classifier assignment strategy over all classification queries (optimal model portfolio) subject given cost budget by solving an integer linear programming (ILP) problem (see Section 4). As preview, Figure IC shows that OCCAM can achieve 20% cost reduction with less than 1% accuracy drop. We show even higher cost reduction with little to no accuracy drop various real-world datasets in Section [ Figure depicts the overall pipeline of OCCAM: (1) draw samples and pre-co the ML classifier accuracy for each sample, (2) for each test query, use its nearest neighbour from all samples to estimate the test accuracy of each classifier, (3) compute the optimal model portfolio w.r.t. cost budgets by solving the II.P problem.
Our main technical contributions are: (1) we formally define the optimal model portfolio problem to reduce overall inference costs while maintaining high performance subject to user-specified cost budgets (Section 3 ; (2) we propose novel and principled approach, OCCAM, to effectively compute the optimal model portfolio with statistical guarantees under weak assumptions (Section 4 and (3) an illustration of the usefulness of OCCAM, conduct extensive experiments the image classification task given its well-separation property and demonstrate the effectiveness of OCCAM on variety of real-world datasets (Section 5)
2

---

Published as a conference paper at ICLR 2025
Classification Queries
User
Cost Budgeta: $5589
OCCAM
ML Classifiars
ML Classifiars
Model Portfollo
Samples
User Queries
Nearest
Budget: $5555
Neighbour
Search
Capybara
(1) Pre-compute Samples
(2) Accuracy Estimation Using Nearest Neighbours (3) Compute Optimal Model Portfolio Under Budgets
Figure 2: OCCAM: Optimization with Cost Constraints towards Accuracy Maximization.
RELATED WORK
Efficient Machine Learning (MI.) Inference. Efficient MI. inference is crucial for real-time decision-
making in various applications such as autonomous vehicles (Tang et al. (002), healthcare (Miotto itt al. 2018), and fraud detection (Alghofaili et al., 2020). involves applying pre-trained ML model to make predictions, where the inference cost expected to dominate the overall cost incurred by the model. Model compression, which replaces large model with a smaller model comparable accuracy, is the most common approach employed for enhancing ML inference efficiency. Common techniques for model compression include model pruning (Hassibi et al. 1993 LeCun et al. 1989
Ding et al.), quantization (Jacob et 2018 Vanhoucke et 201 knowledge distillation (inton
et al.] 2015 [Uban et al. 2016), and neural architecture search (Elsken et al.
2019) Zoph & Le 2016))
These statie efficiency optimizations typically lead a fixed model with lower inference cost but also reduced accuracy compared to its larger counterpart, which may not suffice in highly sensitive applications like collision detection (Wang al., 2021) and prognosis prediction (Zhu et al. 2020).
This shortcoming is already evident in the inference platforms discussed in Section [] highlighting the need for more dynamic optimizations to effectively address the diverse demands users.
Hybrid ML Inference. Recent works (Kg et al. 2022 Ding et al. 2022 2024) have introduced a novel inference paradigm termed hybrid inference, which invokes models of different sizes on different queries, as opposed to employing single model on all inference queries. The smaller model generally incurs a lower inference cost but also exhibits reduced accuracy compared to the larger model. The key idea is to identify casy inference queries which the small models are likely to make correct predictions and invoke small models on them when cost budgets are limited, thereby reducing overall inference costs while preserving solution accuracy. By adjusting the cost budgets, users can dynamically trade off between accuracy and cost within the same inference setup. Kag al. (2022); Ding al. (2022 2024) consider simple setting of only one large and one small model and do not allow for explicit cost budget specification, which could be necessary for production scenarios. Chen al. (2020) studies a setup with multiple ML models and learns an adaptive strategy to generate predictions by calling a base model and sometimes an add-on model when the base model quality scores are lower than the learned thresholds. However, both base and add-on models are selected in a probabilistic manner and this approach fails to satisfy the user-specified cost budgets deterministically. Chen et al. (2022) studies a similar setup with multiple ML models and allocates cost budgets according model-based accuracy prediction. This approach requires separate training phase for the accuracy predictor, which needs large amount of training data, and provides no guarantee on the prediction quality. Mfxture-of-experts (MoE) (Shazeer et al. 2017) also involves dynamically deciding which model (or "expert") processes a given query based on specific criteria. However, MoE often assumes homogenous experts (Fedus al. 2022) with routing decisions made
3

---

Published as a conference paper at ICLR 2025
by learned gating functions that require significant computational resources to re-train if we want to add/update/delete experts. Unlike previous works, we propose an unbiased and low-variance accuracy estimator with asymptotic guarantees, based which we present a novel training-free approach, OCCAM, to effectively compute the optimal assignment of diverse classifiers to given queries, under the cost budgets specified by users. It is worth pointing out that OCCAM is an instance from the Algorithm Selection problem (Rice 1976) with specific focus on classification tasks and pre-trained classifiers.
Image Classification. Image classification is a fundamental task in computer vision, where given an image, label needs be predicted. serves as an essential building block for many high-level Al tasks, c.g., image captioning (Vinyals et al., 2015) and visual question answering (Antol et al. 2015). where objects need to be first recognized. With the growing capacity of deep learning models, from convolutional neural networks (CNN) (Krizhevsky et al., [012 (Simonyan & Zisserman 2014) to Transformer architectures (Dosovitskiy et al. 20l.]2220 Liu al. (022), the classification accuracy on standard image classification benchmarks (Russakovsky et al. 2015 has been greatly improved. In this work, we use the image classification task to illustrate and evaluate our proposed approach OCCAM given its well-separation property Yanng et al., 2020). We utilize both CNN (e.g.. ResNet models) and Transformer (e.g., Swin Transformers) image classifiers in our evaluation.
3 PROBLEM DEFINITION
Let C Rdd be instance space (e.g., images) equipped with metric dist: X' x X' -R-R R200 and [C] = f1.2. (1,2 ... C} be the set of possible labels with C 2 2. Let contain C' disjoint classes, x())).. ...., ((() where for each E [C], all x E x have label í. Let f1. f2.... ... fas be a of classifiers, with b; being the cost of single inference call of fi- Given query æ E X, each classifier Si outputs a single label from [C] at the cost by. We define a model portfolio as follows.
Definition 3.1 (Model Portfolio). Given queries X C X to be classified and classifiers fi, /2. JM, model portfolio y is mapping p X - [M] such that each E X is clas- sified by the classifier fu(z)-
We assume oracle classifier O: X' - [C] which outputs the ground truth label ((z) for all queries x X. Given a finite set of queries X C X. the accuracy of model portfolio μ on is the frequency of the ground truth labels correctly predicted by μ., i.e., Accuracyx (11) E.ex (=)(())))==(( |X] where 1 {condition) } is an indicator function that outputs 1 iff condition is satisfied. Similarly, the cost of model portfolio μ on X is the sum of all inference costs incurred by executing μ on X, i... Costx (f)) = =Exx (u(m)- We will use the notation Accuracy(μ)), Cost(j) when is clear from the context. We define our problem as follows.
Definition 3.2 (Optimal Model Portfolio). Given queries X X, cost budget B RR+, and classifiers f1, f2, "MM find the optimal model portfolio jr" such that Cost(r²) S B and Accuracy(u") Z Accuracy((4 for all model portfolios μ with Cost(u) S B.
4 METHODOLOGY
We describe the general framework to solve the optimal model portfolio problem in the next sections. Our overall strategy consists two steps. Firstly, we propose an unbiased low-variance estimator for the accuracy of any given model portfolio μ4 with asymptotic guarantees. Next, we describe how to determine the optimal model portfolio μ² by formulating it as an integer linear programming (ILP) problem, subject to user-specified budget constraints. All proofs can be found in Appendix
4.1 ESTIMATING Accuracy(и4)
Previous work Hybrid ML (Kag al. 2022 Chen et al. 2022 Ding et al. 2024) typically relies on training a neural router to predict the accuracy of a given set of classifiers for given user queries, based on which queries routed different classifiers. Such paradigm not only involves a non-trite trivial training configuration but also lacks estimation guarantees which can be critical in scientific and production settings. We propose a principled approach to estimate the test accuracy of
4

---

Published as a conference paper at ICLR 2025
given model portfolio for given user queries. By leveraging the specific structure of well- well-separated classification problems like image classification, we propose an unbiased low-variance estimator for the test accuracy with asymptotti guarantees.
Without loss of generality, we consider the wide class of seft classifiers in this study. Given query X. soft classifier first outputs distribution over all labels [C), based on which it then makes prediction at random. Given a soft classifier fi. we abuse the notation and let f((r)) denote the likelihood that Si predicts label j [C], that is, [(()][i]] =- Pr[fi(z) - j]. for query E X. Deterministic classifiers (e.g.. the oracle O) can be seen as special case of soft classifiers with one-hot distribution over all labels. In practice, from softmax classifiers (e.g.. ResNet), soft classifiers can be constructed by simply sampling w.r.t. the probability distribution output by the softmax layer.
Clearly, given a model portfolio μ4, Accuracy(u) is random variable due to the random nature of the soft classifiers. The expected accuracy of any given model portfolio j is,
B[Accuracy(u)) = E Exex (lfulo) (a) O(x))
Exex R[1 ([p(s O(2)]] ExEx (x)
[X|
[X|
[X|
(1
where the last equality follows from ([L(f(())( = O()) = 1 (x) = O(z)] =
(=)=))) Note that [O(=)) is the success probability that the classifier f; correctly
predicts the ground truth label for query x. For brevity, we define SP((z)) == (x)) and rewrite
the expected accuracy as ([[Accuracy(1))
Exex SPats)
[X]
The exact computation of success probability is intractable since the ground truth of user queries is unknown priori. We propose novel data-driven approach to estimate it for any classifier and show that our estimator is unbiased and low-variance with asymptotic guarantees, for well-separated classification problems like image classification. Based on this, we develop principled approach for estimating the expected accuracy of a given model portfolio.
Definition 4.1 (r-separation (Yang et al. 2020)). We say metric space (X, (isd)st) where X' UiEtcy x00 is r-separated, if there exists constant 0 such that (i x vi + j. where dist (2) x(0) min (x.
In words, in an r- r-separated metric space, there is a constant r > 0, such that the distance between instances from different classes least r. The key observation is that many real-world classification tasks comprise of distinct classes. For instance, images of different categories (e.g., gold fish, bullfrog, etc.) are very unlikely to sharply change their classes under minor image modification. It has been widely observed (Yang et al. (220)) that the classification problem real-world images empirically satisfies r-separation under standard metrics (e.g., lo norm). We also observe similar patterns on number of standard image datasets (e.g., Tiny ImageNet) and provide more empirical evidence in Appendix A. With this observation, we can show that the oracle classifier O is Lipschitz 4 continuous Eriksson et al., (2044).
Definition 4.2 (Lipschitz Continuity). Given two metric spaces (X, dx) and dv) where dx (resp. dv) is the metric on the set X (resp. Y), a function f: X + Y is Lipschitz continuous if there exists a constant L 2 0 s.t.
Vz, t' x dx(f()) S L- (xxx(z,2))
(2)
and the smallest L satisfying Equation is called the Lipschitz constant of f.
Lemma 4.3. There exists an oracle classifier O which is Lipschitz continuous if the metric space associated with the instances X is r-separated.
If we further choose the classifiers fi to be Lipschitz continuous (e.g., MLP (Bartlett et al. 2017). ResNet (Gouk et al. (02T). Lipschitz continuous Transformer (Qi et al. 2023)), we can show that the success probability function SP, (z) (i.e., the likelihood that a classifier f, successfully predicts the ground truth label for query x²) is also Lipschitz continuous.
Lemma 4.4. The success probability function (P, = [0())((zz) is Lipschitz continuous if fa(x) and (z)) are Lipschitz continuous.
An important implication of Lemma 4.4 is that, given a classifier, we can estimate its success probability on query by its success probability on similar query x'. Let La denote the Lipschitz
"The Lipschitz continuity for soft classifiers is defined w.r.t. the output distribution.
5

---

Published as a conference paper at ICLR 2025
Sx((x) constant for SP,- For any I, X, we have the estimation error bounded by - L dist(x, x²), which monotonically decreases as dist(z, x') approaches pre-compute a labelled sample S X' (e.g.. pre-compute classifier outputs sampled queries from the validation set) and compute N (T)),, the nearest neighbour of x in S, for success probability estimation. We show that the estimator is asymptotically unbiased, sample size increases.
In practice, we can
Lemma 4.5 (Asymptotically Unbiased Estimator). Given query a classifier fú, and uniformly sampled S C X.
lim [[))(( SP:(2))
(3)
where is the sample size and (N)(2:) arg min dist(xx,x)) is the nearest neighbour of in sample S.
In practice, we draw K i.i.d. samples, S1, S2, Sk. , and compute the average sample accuracy SP.(z) = K EE=ISP SP,NN (x)) as the estimator of the test accuracy on query 2, for each classifier fe. It follows from Lemma 4.5 that SP, is also an asymptotically unbiased estimator. We further show below that SP, is an asymptotically low-variance estimator to SP,, as K increases. Lemma 4.6 (Asymptotically Low- Varianee Estimator). Given query x, a classifier fú, and K i.i.d. uniformly drawn samples S2, ,K of size s, let of denote the variance of the estimator (P.( We have that of is asymptotically proportional to + as both and K increase.
/K
4.2 COMPUTING μº WITH Accuracy(μ)
In the previous section, we show how to estimate the accuracy for given model portfolio. For each classifier fa and query æ, we propose estimate its success probability (P,(x) based on similar queries from labelled samples (1)), which can be efficiently pre-computed.
With the estimator in place, we formulate the problem of finding the optimal model portfolio as an integer linear programming (ILP) problem as follows. Given a set of M classifiers f1, f....... far. user queries = {x1, ,2, ... .x pre-computed samples S2,S2, ... ,Sk, and budget E IR+, we have the following ILP problem
M IIRX ΣΣ ==
M
SP.(2s)
45 S.L. b. fijs S B and Σ
hi 1, for 1,,, (4)
where t. E 1) are boolean variables and t., = 1 iff the classifier fi is assigned to query Zz. Clearly, the optimal model portfolio μ² can be efficiently computed as (x,z = iff t for i E [M] and j E [N], where fi. the optimal solution to the ILP problem above. While ILP problems are NP-hard in general, we can use standard ILP solvers (e.g., HiGHS (Huangfu & Hall 2018) to efficiently compute the optimal solution practice.
The optimization problem aims to maximize the estimated model portfolio accuracy and is subject to the risk of overestimation due to selection bias, especially on large-scale problems. Intuitively, poor classifier with high- variance estimates performance on those queries overestimated. We address this by regularizing the accuracy estimate for each classifier by the corresponding estimator variance. Specifically, we optimize the objective X o,) tag in Equation (4), where o; the standard deviation of the estimator SP,, As og unknown priori, we use validation set estimate σ; for each classifier fa and tune À for the highest validation accuracy.
be mistakenly assigned to some queries if its
The overall algorithm is shown in Algorithm [ We first pre-compute the ML classifier accuracy for all samples (line 1-3). Next, for each test query, we use its nearest neighbour from all samples to estimate the test accuracy of each classifier (line 4-6). In line we compute the optimal model portfolio with the accuracy estimation subject to cost budgets by solving the ILP problem (see Equation 4
'ee evaluate the nearest neighbour distance and estimation error in Appendices A.2 and A.3
'Our problem can be rephrased as "selecting for each query, one item (i.c., ML classifier) from a collection
(the set of all classifiers) so as to maximize the total value (accuracy) while adhering to predefined weight limit (cost budget)", which is a classic multiple choice knapsack problem (MCKP) (Kellerer al. 2004) and the II.P formulation is the natural choice.

---

Published as a conference paper at ICLR 2025
Algorithm 1: OCCAM Algorithm.
Input: test query batch X; MI. classifiers fI. f2; ... J'M and costs c c2, :. CMi query
samples S1, S2,..... Sr: user cost budget B.
Output: optimal model portfolio μ
MM]
// Pre- the ML classifier accuracy for all samples for 8 E U..... for i 1,2, .M do
do
SampleAccuracylls i| Accuracy(ff(s), ground truth(s))
// Use samples to est imate the accuracy for each test query for E X do
for i E 1.2..... do
Waweer/rrreeeeeeeeeeiibbbbrrr// a), for s((
Compute the optimal model portfollio with the accuracy estimation subject to the cost budget (see Equation (4) μ = (AcrsuueetAcrrrcyyttttnntta C2, ,M,
return μ
5 EVALUATION
5.1 EVALUATION SETUP
Task. We consider the image classification task provided with its well-separation property Yang jet al. 2020): given an image, predict a class label from a set of predefined class categories. We assume that each image has unique ground-truth class label.
Datasets. We consider widely studied datasets for image classification: CIFAR-10 (10 classes) (Krizhevsky et al. 2009), CIFAR-100 (100 classes) (Krizhevsky et al., 2009), Tiny Im- ageNet (200 classes) (CS23In). and ImageNet-IK- (1000 classes) (Russakovsky et al. 2015). Details
of those datasets in Appendix C.I.
Models. We consider a total of classifiers: ResNet-[18, 34, 50, 101] (He et al. 2016 and SwinV2- (T, S, B] (Liu al. 2022 8 Among these classifiers, ResNet- 18 is the smallest (in terms of number of model parameters and training/inferece time) and thus has the least capacity, while SwinV2-2 is the largest and with the highest accuracy in general (see Figure Lap. We take the classifiers pre-trained on the ImageNet- 1K dataset (Russakovsky et al. 2015)) We directly use the pre-trained models on ImageNet- while on other datasets, we freeze everything but train only the last layer from scratch. Model training details are in Appendix C.2 All experiments are conducted with one NVIDIA V100 GPU of 32GB GPU RAM. Codes are available in httts://githhb..cm wwwiiihubb.ommmDee wttpii/...oom/Dpaiininnngggg DujiaanDin/OCCCMMMM.
Inference Cost. The absolute costs of running model may be expressed using a variety of metrics, including FLOPs, latency, dollars, etc. While FLOPs is an important metric that has the advantage of being hardware independent, it has been found to not correlate well with wall-clock latency, energy consumption, and dollar costs, which are of more practical interest to end users (Dao et al., 2022). In practice, dollar costs usually highly correlate with inference latency on GPUs. In our work, we define the cost of model inference in USD. We approximate the inference cost of computation by taking the cost per hour ($3.06) of the Azure Machine Learning (AML) NC6s v3 instance (AzureML. 2024), as summarized in Table [ The AML NC6s v3 instance contains a single V100 GPU and is commonly used for deep learning. Since CPU resources D2s v3 instance, equipped with two CPUs and no GPU, costs $0.096 per hour (AzureML. 2024) and all methods studied in this work typically finish in several CPU-seconds, incurring negligible expenses, we ignore the costs incurred by CPU in our comparison. In addition, since larger models typically have higher accuracy as well as higher costs (see Figure Iap. a practically interesting setting is to study how to deliver high quality answers with reduced costs in comparison to solely using the
significantly cheaper than GPU (e.g.,
NNumhers in bracket indicate the model's 's layer number. "Lttees bracket indicate the Swin Transformer V2's size. T/S/B means tiny/small/hase.
7

---

Published as a conference paper at ICLR 2025
Table 1: Model costs on the image classification task. Latency and prices are measured for 10,000 queries. Normalized cost is the fraction of the price w.r.t. SwinV2-B.
Models
Latency (s)
Prices ($)
Normalized Cost
ResNet-18
88.9
0.076
0.15
ResNet-34
135.9
0.116
0.22
ResNet-50
174.5
0.148
0.29
ResNet-101
317.4
0.270
0.52
SwinV2-T
326.4
0.277
0.53
Swin
600.7
0.511
0.98
SwinV2-B 610.6
0,519
1
largest model (e.g., SwinV2-BB Normalized cost directly indicates the percentage cost saved and has been widely adopted in previous works (Ding et al. 2024 Kag et al. 2022), following which we report results terms of the normalized cost of each classifier.
ILP Solver. While our approach is agnostic to the choice of the ILP solver, we choose the high- performance ILP solver, HiGHS (Huangiu Hall| 2018)) to solve the problem in Equation (4). given
its del-nnsemnttetted efficiency and effectiveness on public benchmarks (Gleixner et al. [202T). In nutshell, HiGHS solves II.P problems with branch-and-cut algorithms (Fischetti & Monaci 2020) and stops whenever the gap between the current solution and the global optimum is small enough (e.g.. le-6).
Baselines. We compare approach with three baselines: single best, random, and Fru- galMCT (Chen et al. 2022). Single best always chooses the strongest (i.e., most expensive) model for given cost budget. Random estimates classifier accuracy with random guesses (i.e., uniform samples from [0. 1)) and solves the problem Equation (4p with the same ILP solver as ours. Fru- galMCT (Chen al. 2022 is recent work which selects the best MI. models for given user budgets in an online setting, using model-based accuracy estimation. Following the same setting in (Chen al. 2022), we train random forest regressors on top of the model- features), as the accuracy predictor. The predicted accuracy is used in Equation (4), which is solved by the same ILP solver as ours to make fair comparison in terms of solution quality and costs.
features (e.g., ResNet- 18
Our Method. We evaluate OCCAM (see Section 4 under various metrics (i.e., 11, 12, and lce norms) and cost budgets. We consider images represented by model-based embeddings. Specifically, we extract the image feature 9 of the query image and all the validation images. The costs incurred by feature extraction are deducted from the user budget before we compute the optimal model portfolio. We report the test accuracy under different cost budgets for OCCAM and all baselines in Section 5.2 (Figure 3 and Table 2). validate that OCCAM is cost-aware and indeed selecting the most profitable ML models to deliver high accuracy solutions in Section
(Figure[4a) (.3g demonstrate the effectiveness of OCCAM with limited samples and various À values in Section (F4]ures Abarree///aaamnm
the nearest neighbour distance in Appendix A.2. show that the estimation 4b]and[4c). investigate estimator quickly decreases as the sample size increases in Appendix A..3
of our accuracy [A.3 test the generalizability of OCCAM with different feature extractors in Appendix A.4 provide more performance results under different metrics (see Appendix A.5)
and more classifiers (see Appendix (..6). show how to effectively perform overhead and upper bound performance analysis of and examine the classifier complementarity in Appendix A.10
choose K and in Appendix A.7
OCCAM in Appendices A.8 and A.9
For simplicity, unless otherwise stated, we report OCCAM performance using ResNet-18 features and L- metric with K 40 for all datasets (s = 500 for CIFAR 10, CIFAR100, and s = 1000 for Tiny ImageNet, ImageNet-1K)) We choose À 100 for ImageNet-IK and because ImageNet-1K KK contains a high variety of image classes (1000 classes) that leads to relatively high estimation errors and requires more regularization penalty via large values.
for all other datasets
5.2 PERFORMANCE RESULTS
We investigate the test accuracy achieved by OCCAM and all baselines under different cost budgets and depict the results in Figure 3 We can see that by trading little to no accuracy drop, OCCAM achieves significant cost savings and outperforms all baselines across a majority of experiment
9hhe image feature is the last layer output of a MI. model (e.g., ResNet- 18) trained on the target dataset, given an input image.
8

---

Published as a conference paper at ICLR 2025
Table Cost reduction v.s. accuracy drop by OCCAM and basclines. Cost reduction and accuracy drops are computed w.r.t. using the single largest model (i.e., SwinV2-B) for all queries. For example. on Tiny ImageNet, using V2-n to classify all 10, 000 test images achieves an accuracy of 82.5% and incurs a total cost of $0.519 (we take it as the normalized cost 1, see Table D. A 10% cost reduction equals cost budget of $0.467 (i.e., a normalized cost 0.9), under which we evaluate the achieved accuracy of OCCAM and all baselines and report the relative accuracy drops.
Accuracy Drop (%)
Cost
CIFAR1O
CIFARTOO
Reduction
Single Best
Frugal -MCT
Single Best
Frugal -MCT
Rand
OCCAM
Rand
OCCAM
(%)
10
2.22
2.86
0.97
0.56
3.18
3.29
0.52
0.34
20
2.22
2.86
1.13
0.50
3.18
3.29
0.79
0.36
40
2.22
2.86
1.22
0.51
3.18
3.29
1.98
0.62
Cost Reduction
Miny-ImaeNNet-200
ImageNet--l IK
Single Best
Frugal
Single Best
Frugal
Rand
OCCAM
Rand
OCCAM
(%)
-MCT
-MCT
10
4.01
7.03
0.86
0.17
2.53
5.98
0.59
0.51
20
4.01
7.03
1.49
0.61
2.53
5.98
1.12
1.05
40
4.01
7.03
3.88
2.75
2.53
5.98
2.35
2.24
CIFAR10
CIFAR100
TINY-MAGENET-200
IMAGENET-IK
76-
Accuracy (%6
82
Accuracy (%6
81-
Accuracy (96)
n2.
77-
80-
72
Accuracy:
Single Beet Handom
Single Best
73
Single Best Handom
Single Best
70-
Random
Random
TRigsIMCT
Prag
PrigstMCT
FrigalMCT
DCCAM
70
0.2
0.4
0.6
6.8
1.9
0.2
0.4
0.8
1.0
0.2
0.6
0a
1.0
0.2
0.4
0.8
Normalized Budget
Normalized
Budget
Normalized Cost Budget
Normalized Cost Budget
Figure 3: Accuracy-cost tradeoff's achieved by OCCAM and baselines, for different cost budgets.
settings. Results cost reduction accuracy drop for all approaches are summarized in Table 2 easy classification task (CIFAR-10 of 10 classes), OCCAM consistently outperforms baselines by achieving 40% cost reduction with up to 0.56% accuracy drop. Cost reduction and accuracy drop are computed w.r.t using the strongest model (i.c., SwinV2-B) for all queries. On moderate classification task (CIFAR-100 of 100 classes), OCCAM outperforms all baselines by trading up to 0.62% accuracy drop for 40% cost reduction. On hard classification task (Tiny ImageNet of 200 classes), OCCAM significantly outperforms all three baselines with at least 0.5% higher accuracy. Notably, on aggressive cost regimes (e.g., 40% cost reduction). the achieved accuracy of OCCAM 1.1% higher than FrugalMCT, 4.3% higher than random, and 1.3% higher than single best. On the most challenging classification task (ImageNet- IK of 1000 classes), OCCAM still consistently outperforms all three basclines with higher accuracy all cost budget levels. We believe that the above results demonstrate the generalized effectiveness of OCCAM in achieving non-trivial cost reduction for a small accuracy drop on classification tasks of different difficulty levels.
5.3 VALIDATION RESULTS
We validate that OCCAM functioning as intended, that is, it does select small-yes soclll-ytt-roofffe vet-profitable classifiers when budgets are limited and gradually switches to large-but-accural classifiers as cost budgets increase. In Figure 44 we plot the model usage for each classifier under different cost budgets on the Tiny ImageNet dataset. From the figure, it can be seen that when cost budgets are restricted, OCCAM mainly chooses ResNet-18 18 to resolve queries given its low costs and good accuracy (as seen in Table and Figure Tap. As budgets increase, OCCAM gradually switches to Swin and SwinV2-B, given their predominantly high accuracy (82% as seen in Figure Ta).
5.4 STABILITY ANALYSTS
OCCAM computes K labelled samples of size s to estimate the test accuracy at inference time and computes the optimal model portfolio by solving Equation (4 with regularized accuracy estimation,

---

Published as a conference paper at ICLR 2025
(P,(x) A of (see Section 4.2 We investigate OCCAM performance with different total sample
sizes (K s) by setting s = 1000 and changing K from 10 to 40 (see Figure 4b). and examine the
stability of OCCAM to the choice of (see Figure 4c
We report results Tiny ImageNet dataset.
In Figure 4b we plot
TINY-MAGENET-200
TINY-MAGGENET-20
TINY-MAGEENET-20
the achieved accuracy
82
of OCCAM under dif- ferent total sample sizes
Accuracy (96)
Accuracy (96)
Model Usage
resre11
OCCAN (B-0.8)
OCCAM (8-0.) 0.8)
(K 8) and normal- ized cost budgets (B).
PrugsiMCT (8-0.8)
08-0.01
reaner100
(8-0.6)
(B-
Swin.v2Lt
RugalMET (B-0.6)
RugaiMMT (8-0.6)
We also report Fru- galMCT performance using a maximum of 40, 000 sampled images to train its accuracy pre- dictor. With budget B = 0.8 (i.e., 20% cost reduction), OC-
FMin_V2_5
79
0.2 0.4 0.6
0.8
1.0
10000
20000 30000
Normalized Cost Budget
Total Sample Size
(a) Model usage.
(b) Sample size.
(c) A sensitivity.
Figure 4: (a) Model usage breakdown by OCCAM under different cost
budgets, (b) OCCAM accuracy with different sample sizes, and (c) OC- CAM performance with different À choices
CAM achieves comparable performance FrugalMCT at 25% samples and continues outperform FrugalMCT as the total sample size increases. With budget B = 0.6 (i.e., 40% cost reduction), OCCAM outperforms FrugalMCT by 0.7% higher accuracy with only 25% samples and achieves up to 1.3% higher accuracy as the total sample size increases, which demonstrates the sustained effectiveness of OCCAM even with limited samples.
In Figure 4c we plot the achieved accuracy of OCCAM with different À choices and cost budgets (B). Compared FrugalMCT, OCCAM achieves up 1.3% higher accuracy when budget = 0.6, and 0.8% higher accuracy when B = 0.8. Notably, OCCAM outperforms FrugalMCT under all settings even when and always achieves higher accuracy when > O, which justifies the preserved effectiveness of OCCAM even when À is not well-tuned.
LIMITATIONS
OCCAM assumes well-separated tasks. OCCAM assumes that the classification task is well separated (see Section[4.1), meaning intuitively that instances (e.g.. images) of the problem should not sharply change their class labels under minor modification. To adapt OCCAM other classification tasks such as sentiment analysis (Medhat et al., 2014), the challenge is how to choose the most suitable numeric representation so that the separation property preserved.
OCCAM assumes IID data. The validity of our theoretical guarantees relies on the assumption that underlying data is independent and identically distributed (IID). our evaluation, we uniformly sample training and validation splits from the same population to ensure the IID assumption. It is an interesting question how adapt our approach accommodate data drifts or muttof-diitribution data.
OCCAM optimizes the average accuracy. In sensitive applications such as healthcare or au- tonomous driving, optimizing the average accuracy may not adequate. Instead, optimizing the min accuracy is more appropriate. We can achieve this by changing the ILP objective (Equaatinn { to maximize the min accuracy of all queries, that is, min EM | (x;();)) lig for S N).
7 CONCLUSION
Motivated by the need to optimize the classifier assignment to different classification queries with pre-defined cost budgets, we have formulated the optimal model porifolio problem and proposed principled approach, Optimization with Cost Constraints for Accuracy Maximization (OCCAM), to effectively deliver high accuracy solutions. We present unbiased and low-variance estimator for classifier test accuracy with asymptotic guarantees, and compute an optimal classifier assignment with novel regularization techniques mitigating overestimation risks. Our experimental results variety of real-world classification datasets show that we can achieve up to 40% cost reduction with significant drop in classification accuracy.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like to thank Yuxi Feng and Chenyang Tao for helpful discussions. This work is supported in part by the Institute for Computing, Information and Cognitive Systems (ICICS) at UBC. Research by the first and last authors was supported by grant from the Natural Sciences and Engineering Research Council of Canada (NSERC), Grant Number RGPIN-2020-05408.
REFERENCES
Barsha Abhisheka, Saroj Kumar Biswas, Biswajit Purkayastha, Dolly Das, and Alexandre Escargueil. Recent trend in medical imaging modalities and their applications in disease diagnosis: a review. Multimedia Tools and Applications, 83(14):43035
2024.
Yara Alghofaili, Albatul Albattah, and Murad A Rassam. A financial fraud detection model based on Istm deep learning technique. Journal of Applied Security Research, 15(4):498-516, 2020.
Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. Vqa: Visual question answering. In Proceedings of the IEEE international conference on computer vision, pp. 2425-2433, 2015.
AzureMI.. Azure machine learning learning February 2024. URL https:t:s///auure i leereinggrnngggg
com/ en pttpaa/acccingg/eetalllssss///se
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. peeetrally-nomaalice margin bounds for neural networks. Advances neural information processing systems, 30, 2017.
Jinyuan Chang, Xiaohui Chen, and Mingcong Wu. Central limit theorems for high dimensional dependent data. Bernoulli, 30(1):712-742, 2024.
Lingjiao Chen, Matei Zaharia, and James Y Zou. Frugalml: How to use ml prediction apis more accurately and cheaply. Advances in neural information processing systems, 33: 33:10685-10696, 2020.
Lingjiao Chen, Matei Zaharia, and James Zou. Efficient online ml api selection for multi-label classification tasks. International Conference on Machine Learning, pp. 00.337113766 PMLR, 2022.
Stanford CS231n. Tiny imagenet dataset. Einy-ima Sanyy-imagneee220.
URL htEp://es2ln.sttaffor
Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. Advances in Neurul Information Processing Systems, 35:16344-16359, 2022.
Dujian Ding, Ganesh Jawahar, and Laks VS Lakshmanan. Pass: Pruning attention heads with almost-sure sparsity targets. Transactions on Machine Learning Research.
Dujian Ding, Sihem Yahia, and Laks Lakshmanan. On efficient approximate queries over machine learning models. Proceedings of the VLDB Endowment, 16(4):918-95) 2022.
Dujian Ding, Ankur Mallick, Chi Wang, Robert Sim, Subhabrata Mukherjee, Victor Rühle, Laks V. S. Lakshmanan, and Ahmed Hassan Awadallah. Hybrid LLM: Cost-efficient and quality-aware query routing. In The Twelfth International Conference on Learning Representations, 2024. URL bttts::/cppenrewee http:/eeeeeeeeeeeeeeeeeeeee
net forummid=02f 3mtt
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint 2rX11:2010.11929, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, (0(1):1997-2017 2019.
11

---

Published as a conference paper at ICLR 2025
Kenneth Eriksson, Donald Estep, Claes Johnson, Kenneth Eriksson, Donald Estep, and Claes Johnson. Lipschitz continuity. Applied Mathematics: Body and Soul: Volume Derivatives and Geometry in IR 3. pp. 149-164, 2004.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, Journal of Machine Learning Research, 23 (129)):-13,, 2022.
Matteo Fischetti and Michele Monaci. A branch-and-cu algorithm for mixed-integer bilinear programming. European Journal of Operational Research, 282(2):506 514, 2020.
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg. Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shi- nano. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. Mathematical Programming Computation, 2021. doi: 10. 10.10077512332-0000000020 pottps://doi.orgg
URL
1007/212233200200001122
Google. Cloud vision pricing.
Henry Gouk, Fibe Frank, Bernhard Pfahringer, and Michael J Cree. Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning, 110:333-46,, 2021.
Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference neural networks, pp. 293-299. IEEE, 1993.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pallern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals. Jeff Dean, al. Distilling the knowledge in a neural network. arXiv preprint 1003:v/5503025553 2(7), 2015.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Qi Huangfu and JA Julian Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):11-142, 2018.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-onn inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2704-2713, 2018
Anil Kag, Igor Fedorov, Aditya Gangrade, Paul Whatmough, and Venkatesh Saligrama. Efficient edge inference by selective query. In The Eleventh International Conference on Learning Repre- sentations, 2022.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Hans Kellerer, Ulrich Pferschy, and David Pisinger. The multiple-choice knapsack problem. Knapsack Problems, pp. 317-347, 2004.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA. May 7-9, 2015, Conference Track Proceedings. 2015. URL https //arxiv. org/ abs 11412..42 6980
Kamran Kowsari, Kiana Jafari Meimandi, Mojtaba Heidarysafa, Sanjana Mendu, Laura Barnes, and Donald Brown. Text classification algorithms: survey. Information, 10(4):150, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances in neural information processing systems, 25, 2012.
12

---

Published as a conference paper at ICLR 2025
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEF/CVF international conference on computer vision, pp. 10012-10022, 2021.
Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, al. Swin transformer v2: Scaling up capacity and resolution. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12009-12019, 2022.
Walaa Medhat, Ahmed Hassan, and Hoda Korashy. Sentiment analysis algorithms and applications: A survey. Ain Shams engineering journal, 5(4):1093-11133 2014.
Riccardo Miotto, Fei Wang, Shuang Wang. Xiaoqian Jiang, and Joel T Dudley, Deep learning for healthcare: review, opportunities and challenges. Briefings in bioinformatics, 1966):123-1226, 2018.
Xianbiao Qi, Jianan Wang, Yihao Chen, Yukai Shi, and Lei Zhang. Lipsformer: Introducing lipschitz continuity to vision transformers. arXiv preprint arXiv:2304.00 09856, 2023.
John R Rice. The algorithm selection problem. In Advances in computers, volume 15, pp. 65-1 18. Elsevier, 1976.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-252, 2015.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Lc, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely- gatee mixture-of-exper layer. arXiv preprint arxiv: 0177701116533 2017.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
Ankita Singh and Pawan Singh. Image classification: survey. Journal of Informatics Electrical and Electronics Engineering (JIEEE), 12):1-9, 2020.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy? ?-a comprehensive study on the robustness of 18 deep image classification models. In Proceedings of the European conference on computer vision (ECCV), pp. 631-648, 2018.
Mou Sun, Tao Li, and Wotao Yin. Mindopt adapter for cplex benchmarking performance analysis. arXiv preprint arXiv:2312.13522 2023.
Jigang Tang, Songbin Li, and Peng Liu. A review of lane detection methods based on deep learning.
Pattern Recognition, 111: 2021.
Gregor Urban, Krzysztof Geras, Samira Ebrahimi Kahou, Ozlem Aslan, Shengjie Wang, Rich Caruana, AbdeIrahman Mohamed, Matthai Philipose, and Matt Richardson. Do deep convolutional nets really need to be deep and convolutional? arXiv preprint arXiv: 2016.
Vincent Vanhoucke, Andrew Senior, and Mark Z Mao. Improving the speed neural networks on cpus. 2011.
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 3164, 2015.
Rongxia Wang, Malik Bader Alazzam, Fawaz Alassery, Ahmed Almulihi, and Marvin White. Inno- vative research of trajectory prediction algorithm based on deep learning in car network collision detection and early warning system. Mobile information systems, 2021:1-8, 2021.
13

---

Published as a conference paper at ICLR 2025
Yuo-Yunn Te Yang. Cyrus Rashtchian, Hongyang Zhang, Russ R Salakhutdinov, and Kamalika Chaud- huri. A closer look at accuracy vs. robustness. Advances in neural information processing systems, 33:8588-8601, 2020.
Wan Zhu, Longxiang Xie, Jianye Han, and Xiangqian Guo. The application of deep learning in cancer prognosis prediction. Cancers, 12(3)6603, 2020.
Yilun Zhu, Jianxin Zhang, Aditya Gangrade, and Clayton Scott. Label noise: Ignorance is bliss. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint 1r.15:1611.0157, 2016.
Zhengxia Zou, Keyan Chen, Zhenwei Shi, Yuhong Guo, and Jieping Ye, Object detection in 20 years: A survey. Proceedings of the IEEE, 111(3):257-276, 2023.
14

---

Published as a conference paper at ICLR 2025
Goldfish:
dist(xxx'== 0.99
x0=txxx"==.774
=0
Bullfrog:
Figure 5: Intuitive example of well separated images from Tiny ImageNet under to distance metric using ResNet-18 18 features. Images from different classes (e.g., "goldfish" and "bullfrog") are typically well separated by non-zero distance.
A
ADDITIONAL EXPERIMENTS
A.I REAL IMAGE DATASETS ARE WELL SEPARATED.
In Yang et al. 2020). authors have shown that many real image classification tasks comprise of separated classes in RGB-valued space. this section, we provide further empirical evidence to show that real image datasets (e.g.. Tiny ImageNet) are well separated (see Definition 4. in different feature spaces under various metrics (Figures and ().
In Figure we provide intuitive example to illustrate that images from different classes (c.g.. "goldfish" and "bullfrog") are typically well separated by a non-zero distance. In Figure 6 we investigate the distance distribution for images of different classes from Tiny ImageNet (200 classes). We observe that images of different classes are typically far from each other by a non-zero distance under different metrics (e.g., 4, 12, and (ec) in different feature spaces (e.g., image features extracted by ResNet-18, ResNet-50, and V2-T).
In addition, we that real image datasets subject to little label noises (Zhu et al. 2024). For example, on Tiny ImageNet, we investigate 40, 000 images from the training split and only find 4 duplicate images of different class labels. We also consider more standard image datasets (see Section S.Ty. J.. It turns out that CIFAR-10 contains no label noise, CIFAR-I00 contains 3 duplicate images of difterent class labels (out of 20, 000 images), and the noise frequency on ImageNet- IK is out of 40, 000 images. Our observation suggests that standard image datasets are quite clean (aligned with the observation (Yang et al. 2020)) that justifies the adoption of well-separation assumption.
A.2 NEAREST NEIGHBOUR DISTANCE APPROACHES 0 As SAMPLE SIZE INCREASES.
In this section, we conduct experiments investigate the changes of nearest neighbour distance (dist(æ, N (z)))) as sample size (s) increases. We report results using different feature extractors 18 ResNet-50, and SwinV2-11 well as different metrics (l,, 1z, and Tox) on the validation split of Tiny ImageNet dataset (Figure
can clearly seen 7 the distance the sampled nearest neighbour quickly approaches 0 as sample size increases. This could be attributable the fact that we are sampling from real images. With properly pre-trained feature extractors, the possible image embeddings could restricted to subspace rather than pervade the whole high-dimensional space, which can significantly reduce the required number of samples and give us mcaningfully small distances to the sampled nearest neighbours.
Another interesting observation that, in all investigated feature space, Iso always provides the smallest nearest neighbour distance with different sample sizes, followed by and 4, Such distinction mainly results from the fact that we use normalized image features where each dimension of the Consequently,
feature vector between 0 and 1, that is, 0 < x(ii < for any a[i)]
15

---

Published as a conference paper at ICLR 2025
Feature Extractor: resnet18
Extractor: resnet18
Feature Extractor: resnet
2.0
Examples
15
Examples
Examples
1.5
1.0
0.5
5
0.0
0.00
0.25
0.50
0.75
1.00
0.0
0.5
1,0
1.5
2.0
0.0
0.5
1.0
Distance (la)
Distance (6)
Distance (f2)
Feature Extractor: resnet50
Feature Extractor: resnet50
Feature Extractor: resnet50
35
30
30
Examples %
Examples
25
Examples
25
20
20
15
10
5-
0
0.00
0.25
0.50
0.75
1.00
0.0
0.5
1.0
1.5
2.0
0.0
1.0 Distance (l2)
0.5
Distance (1.)
Distance (4)
Feature Extracton: swin_v2.t v2_t
Feature Extractor: swin_v2. v2_________________
Feature Extractor: swin
50
30
Examples %
Examples %
Examples
30
20
10
0.25
0.75
1.00
0.0
0.5
1.0
1.5
2.0
1.0 Distance (fz)
Distance (1.)
Distance (f1)
Figure 6: Distance distribution between images different classes from Tiny Imagenet. We consider image representation derived by different feature extractors (ResNet-18, ResNet-50, and V2-TV as well as different metrics (l,, 12, and loc). Images of different classes are typically far from each other by non-zero distances.
Feature Extractor: resnet18
Feature Extractor: resnet50
Feature Extractor: swin ___2_
1.2
Nearest Neighbour Dist.
h
Nearest Neighbour Dist.
1.2
Nearest Neighbour
1.0
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Sample
(s)
Sample Size
Sample (s)
Figure 7: Nearest neighbour distance quickly approaches as the sample size increases using different image feature extractors (ResNet-18, ResNet-50, and SwinV2-T) and metries (l,, l2 and loo).
16

---

Published as a conference paper at ICLR 2025
Extractor: resnet18
Feature Extractor: resnet50
Feature Extractor: swin v2
0.50
0.425
resnet18
resnet18
0.400
resnet34
Estimation Error
0.45
resnet34
resnet50
resnet34
resnet101
0.40
resnet101
0.40
resnet101
Estimation
0.350
swin v2_r
_
0.35
swin, v2_5
swin, v2
Estimation
0.35
swin v2_s
v2_t
swin v2
swin, v2_b
swin v2
0.300
0.30
0.275
0.25
200
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
Sample Size
Sample Size (s)
Sample Size (8)
Figure 8: Estimation error for each ML classifier quickly decreases as the sample size increases using different image feature extractors (ResNet-18 18, ResNet-50, and SwinV2-T) under Le metries.
Table 3: Cost reduction v.s. accuracy drop by baselines and OCCAM using different feature extractors (ResNet-18 18, ResNet-50, and SwinV2-T) and Ss distance metric. Cost reduction and accuracy drops computed w.r.t. using the single largest model (i.e., SwinV2-B) for all queries.
Accuracy Drop (%)
Cost Reduction
Tiny- Mewy-mmageNet-200
Single Best
FrugalMCT (ResNet-
FrugalMCT (ResNet-50)
FrugalMCT (SwinV2-T)
OCCAM (ResNet-18)
OCCAM (ResNet-50)
OCCAM
(%%
Rand
(SwinV2-T)
10
4.01
7.03
0.86
0.84
1.18
0.48
0.40
0.29
20
4.01
7.03
1.49
1.45
1.60
1.02
0.74
0.58
40
4.01
7.03
3.88
4.12
3.22
3.24
2.56
2.81
we have the inequality that the 1oc (x) = max max [|=[||]][]]] E < S 12(x) VEritez [a]]]] <
2 (x) Exfejes [x]]]]- Recall that the OCCAM employs the classifier accuracy estimator which is asymptotically unbiased as nearest neighbour distance approaches O. The above observation suggests that lo0 is likely to provide smaller nearest neighbour distance and reduce the estimation error that leads to higher overall performance, especially in scenarios when sampling is expensive or labelled data is scarce.
A.3 ESTIMATION ERROR DECREASES AS SAMPLE SIZE INCREASES.
In this section, we investigate the estimation error (difference between real classifier accuracy and estimator results) for different ML classifiers, using different feature extractors (ResNet- ResNet-50, and SwinV2-T). For brevity, on Tiny ImageNet, we report the estimation error in the accuracy of all 7 classifiers (ResNet-[18, 34, 50, 101], and SwinV2-[T, S, BJ), under 4o metric (Figure The patterns are similar with other metrics and feature extractors.
is clear from Figure 8 that the estimation error of our accuracy estimator continues decrease for all ML classifiers as the sample size increases, which demonstrates the effectiveness our accuracy estimator design (see Section
A.4 GENERALIZING TO DIFFERENT FEATURE EXTRACTORS
further report the performance of OCCAM with different feature extractors (ResNet-Is 18, ResNet- 50, and SwinV2-T), TinylmageNet. As in illustrated in Section 5.1 the costs incurred by feature extraction are "deducted from the user budget before we compute the optimal model portfolio". Results are summarized in Table 3 It can be seen that OCCAM outperforms all baselines all experimental settings, which demonstrates the effectiveness and generalizability of OCCAM with different feature extractors.
17

---

Published as a conference paper at ICLR 2025
Table Cost reduction v.s. accuracy drop by OCCAM and baselines using ResNet-18 features and 1 distance metric. Cost reduction and accuracy drops are computed w.r.t. using the single largest model (i.e., V2-nV2-B) for all queries.
Accuracy Drop (%)
Cost Reduction
CIFARTO
CIFARTO0
Single Best
Frugal -MCT
Single
Frugal
Rand
OCCAM
Rand
OCCAM
(%)
Best
-MCT
2.22
2.86
0.97
0.38
3.18
3.29
0.52
0.50
20
2.22
2.86
1.13
0.38
3.18
3.29
0.79
0.50
40
2.22
2.86
1.22
0.37
3.18
3,29
1.98
0.99
Cost Reduction
Tiny- Iny-ImageNett-200
ImageNet-IK
Single Best
Frugal
Single Best
Frugal
Rand
OCCAM
Rand
OCCAM
(%)
-MCT
-MCT
10
4.01
7.03
0.86
0.48
2.53
5.98
0.59
0.86
20
4.01
7.03
1.49
1.02
2.53
5.98
1.12
1.51
40
4.01
7.03
3.88
3.24
2.53
5.98
2.35
3.32
CIFAR10
CIFAR110
TINY-IMAGEEFT-20
IMAGENET-1K
Accuracy (%6)
Accuracy (%)
77-
Accuracy
60-
Single Beet
Single
Single Best
Single Best
24
FrugsMCCT DCCAM
PragalMCT
69
Pruga/MC OCCAN
68-
GCCAM
0.6
1.b
0.9 Normallzed Cost B Budget
0.2
1.0
Normalized Cost Bet
Normalized Cost Budget
Normalized Cost Budget
Figure 9: Accuracy-cost tradcoffs achieved by OCCAM and baselines using 4 metric and ResNet-18 features, for different cost budgets.
A.5 MORE OCCAM PERFORMANCE RESULTS.
In this section, we provide more OCCAM performance results using l and l2 norm metrics, as shown in Figures and IO Qualitative comparison results are summarized in Tad which resemble our analysis in Section 5.2 Typically. by trading little to no performance drop, OCCAM can achieve significant cost reduction and outperform all baselines across majority of experiment settings.
However, we also note that FrugalMCT can sometimes outperform OCCAM on ImageNet- K using 1 and 12 metrics, while OCCAM outperforms FrugalMCT across all experiment settings using lo metric (see Section 5.2). This could be explained by the fact that / and l2 metrics are likely to provide higher nearest neighbour distance than (so metric (see Appendix (A.)) that implicitly increases OCCAM estimator error and leads to reduced overall performance, especially when the classification task is challenging and labelled data is scarce. Provided that, in practice, we would recommend applying OCCAM with To to achieve significant cost reduction with little to performance drop (see Section 5.2)
A.6 LARGE- SCALE EXPERIMENTS WITH 101 PRE-TRAINED CLASSIFIERS.
In this section, we investigate the capacity of OCCAM on ImageNet- IK dataset with 101 pre-trained models for image classification (c.g.. DenseNet (Huang et al. 2017). ResNet (He et al. 2016) to
VGG (Simonyan & Zisserman 2014). VIT (Dosovitskiy et al.) 2020 to Swin Transtormer V2 (Liu et al. 2022 )) that are available on Pytorch Hub To
We plot the validation accuracy and costs of the I0I pre-trained models in Figure [I] It can be clearly seen that majority of pre-trained models are Pareto- dominated by others, that is, there exist models which are more accurate yet cheaper. The subset of models that are not Pareto-dominated by any other models are termed as Pareto-efficient models. In practice, we can always replace a careto-dominated model with a corresponding Pareto-efficient
18

---

Published as a conference paper at ICLR 2025
Table Cost reduction v.s. accuracy drop by OCCAM and baselines using ResNet-18 features and 22 distance metric. Cost reduction and accuracy drops are computed w.r.t. using the single largest model (i.e., V2-nV2-B for all queries.
Accuracy Drop (%)
Cost Reduction
CIFARTO
CIFARTO0
Single Best
Frugal -MCT
Single
Frugal
Rand
OCCAM
Rand
OCCAM
(%)
Best
-MCT
2.22
2.86
0.97
0.24
3.18
3.29
0.52
0.34
20
2.22
2.86
1.13
0.25
3.18
3.29
0.79
0.40
40
2.22
2.86
1.22
0.27
3.18
3,29
1.98
0.71
Cost Reduction
Tiny- Iny-ImageNett-200
ImageNet-IK
Single Best
Frugal
Single Best
Frugal
Rand
OCCAM
Rand
OCCAM
(%)
-MCT
-MCT
10
4.01
7.03
0.86
0.21
2.53
5.98
0.59
1.06
20
4.01
7.03
1.49
0.81
2.53
5.98
1.12
1.65
40
4.01
7.03
3.88
2.75
2.53
5.98
2.35
3.10
CIFARLO
CIFAR100
TINY-IMAGENET-200
IMAGENET-IK
83
Accuracy (5%)
74-
Accuracy (%))
1981
Accuracy
78
Single
23
Single
Single
Random Phugs/NCT
70-
Random
Rendom
74
Rendom
88-
PrugalMCT
PCU
Frugs/MCT
OCCAM
OCGAM
OCCAN
DCCAM
65-
6.4
0.6
o.
1.
3.2
0.2
0.4
0.6
0.n
6.8 1.0
Normalized Cost Budget
Normalized Cost Budget
Normalized Cost Budget
Normalized Cost Bud
Figure 10: Accuracy-cost tradeoffs achieved by OCCAM and baselines using le metric and ResNet-18 features, for different cost budgets.
model to improve accuracy and reduce costs simultaneouslyy, which serve as the core set of models choose from. Specifically, there are 12 Pareto-efficient models from the 101 pre-trained models as summarized in in 6 In our evaluation, we examine OCCAM with the 12 Pareto-efficient models and compare it with baselines of access to all 101 pre-trained models. Note that FrugalMCT does not finish after running 5 hours and we exclude it from the comparison. Results are shown Figure 12 and Table 7 OCCAM consistently outperforms all baselines by achieving less than 1% accuracy drop at various cost reduction rates, while the accuracy drop for Random is up to 7.05%, and 15.00 5..0% for Single Best. It is worth noting that, Single Best, as defined in 5.1 always chooses the most expensive model for given cost budget. As shown in Figure [] in practice, more expensive models are not necessarily of higher accuracy. The performance of Single Best oscillates heavily due to the existence of expensive-ane srensive-and-ing and-inaccurate models, which suggests that blindly using hundreds of classifiers in practice may not eventually help the overall performance.
A.7 EFFECTS OF AND S ON OCCAM PERFORMANCE.
In this section, we examine the effects of K and on the performance of OCCAM (see Figure 13). As shown by Lemmas 4.5 and [4.6 our estimator is asymptotically unbiased and low-variance as both K (number of samples) and s (sample size) increase, which leads to better overall performance. We demonstrate this by increasing K from to 40 while keeping s fixed (1000), and increasing s from 400 to 1,000 while keeping K fixed (40), as illustrated in Figures 13a and 13b) We observe that the performance of OCCAM consistently dominates that of FrugalMCT and improves as both K and increase. In our evaluation, we pre-compute held-out dataset (e.g.. for TinyImageNet, we uniformly sample 40,000 images from the training split) from which we draw K samples of size With the maximal number of samples bounded (for TinylmageNet, K < 40000), there is trade-off between increasing and having larger s. As shown in Figure [3c though a larger K typically leads to better accuracy, it also limits the maximal value that take & 40000/K),
19

---

Published as a conference paper at ICLR 2025
85
Accuracy (%)
80
75
65
Pareto efficceeffi
55
10-1
10"
Cost ($)
Figure 11: Accuracy v.s. cost for the 101 pre-trained classifiers on ImageNet- 1K from Pytorch Hub.
Table 6: Accuracy and costs of the 12 Pareto-efficient models the image classification task.
Latency and prices are measured for 10,000 queries. Normalized cost is the fraction of the price w.r.t. RegNet 128GF (the most expensive model).
Models
Accuracy (%)
Latency (s)
Prices ($)
Normalized Cost
ResNet-18
67.1
75.5
0.064
0.14
VGG19
70.6
82.7
0.070
0.15
VGG19_BN
73.0
86.8
0.074
0.16
MNASNetL
75.7
113.0
0.096
0.21
RegNet X 8.00F
76.7
140.6
0.120
0.26
VIT B.16
81.6
149.6
0.127
0.27
ConvNeXt. Kiny
82.0
184.6
0.157
0.34
RegNet.X. X_I6GF
82.2
255.1
0.217
0.46
RegNet_X_32GF
82.3
259.3
0.220
0.47
ViT V6
84.7
263.2
0.224
0.48
VIT H 14
85.5
414.1
0.352
0.75
RegNet 128GF
86.0
549.7
0.467
1.00
IMAGENET-IK
85
Accuracy (%)
80
Single Best Random OCCAM
0.2
0.4
0.6
0.8
1.0
Normalized Cost Budget
Figure 12: Accuracy-cost tradeoff's by OCCAM and baselines using loo metric and ResNet-18 features with the 101 pre-trained classifiers on ImageNet-IK.
20

---

Published as a conference paper at ICLR 2025
Table 7: Cost reduction v.s. accuracy drop by baselines and OCCAM using 4cc metric and ResNet-18 features with the 101 pre-trained classifiers on ImageNet- 1K. Cost reduction and accuracy drops are computed w.r.t using the most expensive model (i.e., RegNet_ (_1GGFF) for all queries. FrugalMCT does not finish after 5 hours and is excluded from the comparison.
Accuracy Drop (%)
Cost
ImageNet-IK
Reduction
Single Best
Rand
FrugalMCT
OCCAM
(%)
10
15.09
7.05
N/A
0.17
20
3.27
7.05
N/A
0.37
40
9.15
7.05
N/A
0.80
TINY-IMAGENET-200
TINY-MAGENNET-200
82
IINY-
Accuracy (96)
Accuracy (%)
Accuracy
OCCAM
OCCAM [Bac
81.50
80-
OCCAM (8-0 6)
80-
(8m0.8)
PrugalMCT (8-0.6)
Frug WMMT (B-0.6)
81.00
>-100
79-
5-1000
** 5-000
80.50
K (s=1000)
5 (K-40)
K
(a)
(c)
Figure 13: OCCAM performance improves as (a) the number of samples K and (b) the sample size increase. (c) In practice when the total sample size fixed (e.g., 40,000 for Tiny ImageNet), there a trade-off between increasing K and having larger
which results in sub-optimal performance. We empirically choose K and s that give the best overall accuracy across different datasets, as discussed in Section 5.1
A.8 OVERHEAD ANALYSIS
In this section, we investigate the overheads incurred by OCCAM, which mainly result from nearest neighbour search and the use of the ILP solver, on the Tiny ImageNet dataset.
With 10,000 test images and 40,000 total samples, the nearest neighbor search takes 8.68 seconds to return all results, up to two orders of magnitude smaller than the model inference time (see Table [ which leads to negligible overheads. Such efficiency can be attributed to the linear time complexity of nearest neighbor search w.r.t. the total sample sizes. Specifically, let N denote the number of test images, 8 denote the sample size, K denote the number of samples, and d denote the image representation dimension; then the time complexity of nearest neighbor search is O(N
K d).
In our evaluation, we adopt HiGHS (Huangfu & Hall, 2018) as our ILP solver given its well- demonstrated efficiency and effectiveness public benchmarks (Gleixner et al. 2021). With 10,000 test images and 7 classifiers (equivalently an ILP instance with 70,000 variables and constraints, Equation (4)) the HiGHS IL. solvers takes 15.1 seconds to return the optimal assignment. It is worth noting that the latency overhead of ILP solver is only fractional to using the smallest model (ResNet-18 takes 88.9s process 10,000 test images, see Table T. and even less than 2.5% of always using the largest model (SwinV2--B V2-B takes 610.6s to process 10,000 test images, see Table I. which demonstrates the overhead incurred by ILP solver is negligible.
We note that there are other ILP solvers which are even more efficient than HiGHS. For example, Gurobi [1 is up to 20X faster than HiGHS on large scale MILP instances with up to 640K variables and constraints (Sun et al. 2023). which can be used as the ILP solver if the problem scale increases further.
I "htps://www.gurbiiccmm
21

---

Published as a conference paper at ICLR 2025
TINY-IMAGENET-200
90
Single Best
Accuracy (%)
Random
FrugaIMCT
OCCAM
80
Optimal
75
65
0.2
0.4
0.6
0.8
1.0
Normalized Cost Budget
Figure 14: Accuracy-cost tradeoff's by OCCAM and baselines using lo metric and ResNet-18 features. Optimal is computed using the true classification likelihood instead of estimation.
Overall, the latency overheads incurred by OCCAM are negligible. Since OCCAM only requires CPU support compute the optimal model assignment, the monetary overheads significantly small as well.
A.9 UPPER BOUND PERFORMANCE OF OCCAM.
In this section, we investigate the optimal performance that can reached with true classification
likelihood (no estimation errors) on the Tiny ImageNet dataset (see Figure 14). Note that, the underlying method of OCCAM and the Optimal is exactly the same. The performance difference between OCCAM and Optimal mainly comes from the estimation error and hints at huge room for further improvements which we will explore in our future work.
A.10 COMPLEMENTARITY BETWEEN DIFFERENT CLASSIFIERS.
In this section, examine the complementary behaviour between different classifiers, that is. different classifiers may suit the best for different subset of test queries. On the Tiny ImageNet dataset, plot the frequency that classifier makes the right prediction while the other fails (see Figure 15) For example, on 5% of test queries. ResNet-1e 18 is able to correctly classify the labels on which Swin fails, while on the other 24% of test queries, SwinV2-B is better than ResNet-18 18 in terms of making right predictions. The complementary nature of different classifiers implies the possibility of developing a model assignment strategy that effectively outperforms the single best classifier such as the Optimal approach shown in Figure 14 It can be seen that the Optimal performance significantly outperforms the Single Best baseline and suggests a huge room for further improvements by reducing the accuracy estimation errors.
B PROOFS
In this section, we provide proofs to Lemmas 4.3
4.6
Proof to Lemma 4.3
Proof. The proof is straightforward. Without loss of generality, we consider the I metric and assume (x is a r-separated metric space. For brevity, we abuse the notation and let O(x) denote the one-hot output distribution over all labels. For any x, E ,, if æ and x' belong to the same class, z' [|:: otherwise, |1(xx) Oxx))l
The Lipschitiz constant for O is 1
then (O(x) Ozz')l1 = 0 <
I|
< 2 || Il
Proof to Lemma 4.4
22

---

Published as a conference paper at ICLR 2025
resnet18
0.100.080.070..0
resnet34
0.16
0.100.080.07
0.05 0.05
0.20
resnet50
0.160.12
0.07
0.05
0.05
resnet101 0.190.140.12
0.08
0.06
0.10
swin v2_ 0.220.166..140.11
0.04
swin wwin_v2_s 0..44..99..1......
0.05
0.05
swin_v2_b 0.240.180.170.11
0.05
0.00
resnet18
resnet34
resnet50
resnet101
swin v2_t
swin v2_5
swin V2 b
Figure 15:
Classifier complementarity. Each entry indicates the percentage of queries on which the classifier on the row makes the right prediction while the classifier on the column fails.
Proof. Similarly, without loss of generality, we consider the I metric and let f((x), O(x) denote the output distribution over all labels. Let L, and Lo denote the Lipschitz constants for [x()) and (zr) respectively. For any 2, x' E X. if x and x' belong to the same class, then (T)
(P.( = [f(())(((z) - [(=')]((( & llf((z) f((2')11 S L, || æ'11 otherwise, - (<'"((0)))) S - 110) S Le -111--0
The Lipschitiz constant for (x) is ma. Le).
Proof to Lemma 4.5
Proof. The proof leverages the fact that, as the sample size increases, the expected distance between a and nearest neighbour monotonically decreases. Letting 14 denote the Lipschitz constant of SP,. we have the estimation error
SP:(xx) = ([N SP. L, E[dist([ (s( x)], which approaches as (N x)] decreases.
Proof to Lemma 4.6
Proof. Lemma 4.5 shows that each SN.: (I)) is an unbiased estimator of (P,(z), 1 1 K, as s approaches infinity. Let of² denote the variance SP.(N (x)) for each k. By the Central Limit Theorem, the distribution of the estimator K Σ k= (PN(NN approaches a normal distribution with variance
Chang et al. 2024).
C EXPERIMENT DETAILS
C.1 DATASETS
CIFAR-10 CIFAR-10 (Krizhevsky et al. 2009 contains 60, 000 images resolution 32 x 32, evenly divided into 10 classes, where 50, 000 images are for training and 10, 000 images are for testing. We randomly sample 20, 000 images from the training set as our validation set, and we use the remaining 30, 000 images train models.
CIFAR- 100 Same as CIFAR-10, CIFAR-100 Krizhevsky et al. 2009) has 50, 000 training and 10. 000 testing images. But they evenly separated into 100 classes. We randomly sample 20, 000 training images as our validation set.
23

---

Published as a conference paper at ICLR 2025
Tiny ImageNet" Tiny ImageNet (CS23In) is subset of the ImageNet-1K 1K dataset (Russakovsky eet al. 2013). It covers 200 class labels and all images are in resolution 64 x 64. It includes 100, 000 training I0, 000 validation, and 10, 000 testing images. The given test split does not have ground- truth labels, thus we discard this set and use the validation split as our testing data. We randomly sample 40, 000 training images the validation data and use the remaining 60, 000 ones to train the models.
We use the image classification dataset in the ImageNet Large Scale Visual Recogni- tion Challenge (ILSVRC) 2012 (Russakovsky et al. 2013). This dataset contains 1,281,167 training, 50,000 validation, and 100,000 testing images, covering I, 1,000 classes. Images are of various resolu- tions. Since the models we use are pre-trained on this dataset, we do not train the last linear layer of the models. The given test split comes without ground-truth labels; thus we use the validation split to evaluate our method and baselines. Among the 50,000 validation images, we randomly select 10,000 of them as our testing data and the remaining ones are treated as the validation data.
ImageNet-II 1.5
C.2 MODELS
We use ResNet (He et al. 2016) and Swin Transformer V2 (Swin (Liu et al. 2022 models on the image classification task because they are popular models for the task and many of their pre-trained weights on the ImageNet- IK dataset (Russakovsky al. 2015) are available online T6 where reasonable performance are achieved. On CIFAR-IO, CIFAR- 100, and Tiny ImageNet, we freeze everything of the pre- pre-trained models but only train the last linear layer of each model from scratch. The output dimension of the last layer is set to be the same as the number of image classes on the test dataset. We implement the soft classifier (see Section 4.1) by sampling w.r.t. the probability distribution output by the softmax layer, i... Pr[f(()) = jl exp(z,/T) exp(ss/T> where zn temperature controlling the randomness of
the logit for [C] and 7 is the Syper-paramenn predictions. We choose a small r (1e-3) to reduce the variance in predictions. At test time, to obtain consistent results, all classifiers make predictions by outputting the most likely class labels (i.e., arg max; [i)), equivalently to having soft classifiers with т O. For all seven models, use the Adam optimizer (Kingma Ba 2015) with 3, = 0.9 and B2 = 0.999, constant learning rate 0.00001, and a batch size of 500 for training. Models are trained till convergence.
htte:://cohhhssaaarrrooddhhhhhhh 200. pap.
For example, the pre-trained models use from httph:p::///ooorc.oorg//ssss
models html Specifically, the pre-trained weights we use are as follows.
ResNet-18: ResNet18 We Weights. IMAGENETIK Vi
ResNet-34; ResNett34..eiihtss... IMAGENET1K.VL .tt..eeei.ght....t...TTT.....
ResNet-52: Res.Net.50.Weigghttt... IMWGENTTT.........
ResNet-101: ResNet: weight.s. I
IMAGHNNTTK v1
SwinV2-T: hwan::/...wii.......eetttt..... IMA.EEEETT.........EEEE
Vwin wwwn_W2...eeigghhheeee F.A.EEEEI.......EEEEEE......
S2in Swin Swin_v2___weiights. IMAG*NRT1K.1
24


Reviews:
[{"review_id": "r4RBO2o5Zz", "reviewer": "Reviewer_DVtc", "summary": "This paper addresses the trade-off between classification accuracy and inference cost by proposing a framework that combines small and large models. The authors introduce OCCAM (Optimization with Cost Constraints for Accuracy Maximization), a framework that optimally assigns classifiers to queries within a cost budget, leveraging the insight that some “easy” queries can be accurately classified by smaller models. OCCAM uses a statistical accuracy estimator and solves an integer linear programming problem to create a model portfolio that minimizes costs while maintaining accuracy.", "questions": "- How does OCCAM fit into the literature of routing for Mixture-of-experts?\n\n- What is the reason for K = 40 being the maximal value?\n\n- How does OCCAM perform in scenarios with more than 7 classifiers? E.g. model selection literature [1] use more than 100 pretrained models for ImageNet.\n\n\n\n[1] Mohammad Reza Karimi, Nezihe Merve Gürel, Bojan Karlaš, Johannes Rausch, Ce Zhang, and Andreas Krause. Online active model selection for pre-trained classifiers. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 307–315. PMLR, April 2021.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper demonstrates statistical guarantees to compute optimal assignments with weak assumptions. \n\n- Experimental results on classification datasets show  up to 40% cost reduction with\nno significant drop in classification accuracy.", "weaknesses": "- Limited scope of experiments with pretrained classifiers:\nThe paper's most significant weakness is the limited number of pretrained classifiers used in the experiments. This scope may not provide a comprehensive evaluation of the proposed method and could affect the generalizability of the results.\n\n\n- Insufficient clarification on related work:\nThe paper lacks adequate clarification on how it builds upon or differentiates from existing research in the field. Providing a clearer context within the related work section (as highlighted in the Questions) would strengthen the paper by situating it more effectively within the current academic discourse.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "4vC86VPMRq", "reviewer": "Reviewer_gGnF", "summary": "The paper considers minimizing model inference cost by finding the best instance-classifier assignment. A novel method is proposed and there are some new ideas. However, the problem formulation ignores the extra cost induced by the proposed method, which is not discussed in the main text or evaluated in experiments. This is a critical point that might make the proposed method meaningless in some situations.", "questions": "1. what is the time complexity and empirical running time of the ILP solver? \n2. what is the cost of nearest neighbor search in the sample? \n3. Overall, what is the extra cost induced by the method? Would the gain from reduced inference time be significantly larger than the induced extra cost?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a new method to find the best instance-classifier assignment to minimize inference cost.\n2. The proposed method for accuracy estimation is asymptotically unbiased and the assignment problem can be solved with ILP solvers. \n3. Good results are show on a specific evaluation setting.", "weaknesses": "1. The problem formulation seems to be unreasonable. The paper aims to find the best instance-classifier assignment to minimize the overall classification inference cost. However, the problem formulation ignores the extra cost for finding the best assignment itself. If the extra cost of finding the best assignment is larger than the saved cost in inference from that assignment, there is no point using the proposed method. \n2. The running time and cost of the ILP Solver is not discussed. This is important as it impacts the applicability of the method in practice. \n3. The sample size can be as large as 40000, which might presents considerable cost in nearest cost, which however, is also not discussed or reported in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "D9gsm9jYmw", "reviewer": "Reviewer_K8Qp", "summary": "The authors propose a method for choosing a good set of classifiers that try to maximize classification accuracy while maintaining some cost constraints. Their method is based on estimating the expected accuracies of each classifier in the portfolio using nearest neighbor in a suitable embedding space, and then apply integer programming to find out the best classifier for each test example. Experiments show their method beats several state-of-art methods when tested on several image classification benchmarks.", "questions": "- Why are the results for Random the same for all cost reduction levels in Table 2 and Table 4, if it solves the same ILP problem as in Equation 4?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This problem of choosing a good set of classifiers to maximize accuracies under computational budget constraints is a very relevant and practical problem given the rising costs of running neural-network-based classifiers. \n\n- Empirically the method performs very well under various cost reductions when compared to other algorithms such as Frugal-MCT and single best, having higher accuracies at the same cost reduction levels. \n\n- The authors also provide theoretical justifications for their accuracy estimates of different classifiers for a new test sample, under the assumption of Lipschitz continuity and well-separatedness.", "weaknesses": "- Choosing the hyperparameter \\lambda for different datasets seems difficult. It is set to 100 for Imagenet-1K and 5 for other datasets, which is a large range. This can impact the practical performance of the method. \n\n- The results for unbiasedness and low-variance in Lemma 4.5 and 4.6 are asymptotic. In practice since we are training neural networks for embeddings, the underlying metric space and nearest neighbor function DEPENDS on the training set. For example, the data can be r-separated on the training set since the neural network embedding is trained on it, but not so on a separate validation set. If the samples S_1, ..., S_k in Section 4.2 comes from the training set, the estimates for accuracy can be biased. If they come from a separate validation set then we need a fairly well-represented validation set to estimate the accuracies, which can be a limitation of the method. \n\n- There is a big gap of costs between SwinV2-S and SwinV2-T with no intermediate models. This makes the 10%, 20%, and 40% cost reduction in Table 2 all use the same model for single best and the results for 10% and 20% cost reduction weak for single best since there is no model with intermediate costs available.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "5koOrJYZz2", "reviewer": "Reviewer_iJX4", "summary": "The authors present a method for cost-efficient classifier selection at inference time.\nThe proposed method uses an estimator of classifier accuracy, which is based on the assumption of well-separated classification instances (images) and utilizes samples of classification accuracy from the classifiers.\nGiven such an estimator, the construction of an optimal model portfolio is stated as an Integer Linear Programming problem. \nThe method is evaluated using established image classifiers and standard benchmark data.", "questions": "- Is it possible to have a strong (the strongest) baseline by solving the ILP not with an estimator of accuracy but the true classification likelihoods, as an upper bound of achievable performance given a predefined budget?\n\n- To me it seems like the proposed method quite naturally translated into an online setting. It particularly seems to resemble a contextual multi-armed bandit problem, in which each classifier is an arm and the context is given by the classification instances. The reward would be multi-criteria containing costs as well as performance. Would such an extension to online learning make sense?\n\n- The work considers an order of image classifiers, from cheap and less accurate to costly and more accurate. While the classifiers certainly can be ordered wrt accuracy, is there not also a kind of performance complimentarity, i.e. one classifier is better at classifying certain images while another classifier is better suited for other images? I think this may be another strength of OCCAM. Even in (hypothetical) settings in which classifiers have the same cost and the same accuracy on average, OCCAM may be able to identify the better classifer on a per-instance level, effectively outperforming the single best classifier. I am not sure whether these phenomena are present for the considered classifiers and data, however, the possibility should be discussed.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is well-motivated and of great practical relevance for users of image classification services.\n\n- The method sound under assumptions of well-separated instances and the findings are supported both empirically and theoretically", "weaknesses": "- The proposed method relies on precomputed samples of the classifiers under consideration. These are assumed to be given without any cost. However, this is typically not the case. In order to be able to use it in practice, these samples need to be collected which results in expenditure. A good contribution would be to analyse the following question:\nGiven a user-specified budget, how many samples should be acquired in order to maximize accuracy while adhering to the budget with overall cost (samples for accuracy estimation + classification instances).\n\n- Additionally, the use of the nearest-neighbor based accuracy estimator as well as the ILP solver are assumed to incur no cost, which does not hold in practice. \n\n- The considered problem setting is an instance of the (per-instance) Algorithm Selection (AS) problem (Rice 76). That is, given an instance of an algorithmic problem domain and a set of algorithms suitable to solve said instance, select the algorithm that optimizes a performance metric. For the submitted study, the problem domain is image classification, the problem instances are images, the algorithms are image classifiers and the performnace metric is a multi-criteria with cost and accuracy. There is a substantial corpus of literature concerned with AS and also the idea of using algorithm portfolios has been examined. Although the manuscript considers a very specific instantiation of this problem, I think a reference should be given. \n\nMinor remarks:\n- p 1. line 37: \"On the other (hand)\"\n\nLiterature: \nRice, J. R. (1976). The algorithm selection problem. In Advances in computers (Vol. 15, pp. 65-118). Elsevier.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)