OCCAM: Towards Cost-Efficient and Accuracy-Aware Classification Inference

Authors: Dujian Ding, Bicheng Xu, Laks V. S. Lakshmanan
Primary area: optimization
Keywords: Efficient ML, Hybrid ML Inference, Classification

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730455048733

thread_type:
official_review

<thread_object>
creator: reviewer_ijx4

<content>
summary:
The authors present a method for cost-efficient classifier selection at inference time.
The 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.
Given such an estimator, the construction of an optimal model portfolio is stated as an Integer Linear Programming problem. 
The method is evaluated using established image classifiers and standard benchmark data.

strengths:
- The proposed method is well-motivated and of great practical relevance for users of image classification services.

- 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:
Given 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).

- 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. 

- 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. 

Minor remarks:
- p 1. line 37: "On the other (hand)"

Literature: 
Rice, J. R. (1976). The algorithm selection problem. In Advances in computers (Vol. 15, pp. 65-118). Elsevier.

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?

- 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?

- 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730471810991

thread_type:
official_review

<thread_object>
creator: reviewer_k8qp

<content>
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.

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. 

- 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. 

- 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. 

- 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. 

- 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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730577240588

thread_type:
official_review

<thread_object>
creator: reviewer_ggnf

<content>
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.

strengths:
1. The paper presents a new method to find the best instance-classifier assignment to minimize inference cost.
2. The proposed method for accuracy estimation is asymptotically unbiased and the assignment problem can be solved with ILP solvers. 
3. 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. 
2. 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. 
3. 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.

questions:
1. what is the time complexity and empirical running time of the ILP solver? 
2. what is the cost of nearest neighbor search in the sample? 
3. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730666892222

thread_type:
official_review

<thread_object>
creator: reviewer_dvtc

<content>
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.

strengths:
- The paper demonstrates statistical guarantees to compute optimal assignments with weak assumptions. 

- Experimental results on classification datasets show  up to 40% cost reduction with
no significant drop in classification accuracy.

weaknesses:
- Limited scope of experiments with pretrained classifiers:
The 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.


- Insufficient clarification on related work:
The 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.

questions:
- How does OCCAM fit into the literature of routing for Mixture-of-experts?

- What is the reason for K = 40 being the maximal value?

- 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.



[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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732405170944

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
We thank all the reviewers for their careful reviews and excellent comments. We have added a range of new experiments which address the concerns raised by the reviewers and we believe this has made the evaluation of our approach much more comprehensive. The changes are highlighted in blue in the updated draft and are summarized below:

1. We have discussed the related work pointed out by Reviewer DVtc and Reviewer iJX4 in Section 2 (Page 3).
2. We have shown that the computational overhead of OCCAM is negligible in Appendix A.8 (Page 20) as suggested by Reviewer gGnF and Reviewer iJX4.
3. We have conducted additional experiments to show how to apply OCCAM to more than 100 pre-trained classifiers, as suggested by Reviewer DVtc. These experiments are presented in Appendix A.6 (Page 17) and demonstrate the effectiveness of OCCAM. Specifically, with 40% cost reduction, OCCAM is able to achieve less than 1% accuracy drop while the baselines suffer from accuracy drops of 7% or more.
4. We have added experiments to clarify how to effectively choose K (number of samples) and s (sample size) in practice using a held-out set in Appendix A.7 (Page 18) as suggested by Reviewer DVtc.
5. We have included new baselines to present the upper bound performance that OCCAM can reach with perfect accuracy estimator in Appendix A.9 (Page 21) as suggested by Reviewer iJX4;
6. We have performed analysis on the complementarity between different classifiers in Appendix A.10 (Page 21) as suggested by Reviewer iJX4;

The details of revision are referred to the following official comments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1739284654449

thread_type:
public_comment

<thread_object>
creator: ~janek_haberer1

<content>
title:
Question about Feature Extractor

comment:
Congratulations on the acceptance of your paper! 

I had a question regarding the step “Accuracy Estimation Using Nearest Neighbors”. Are you doing the nearest neighbor search based on the raw input image or on a feature representation of the image? In the supplementary material, you have multiple figures showing the impact of different feature extractors, suggesting that you are using a network such as ResNet18/ResNet50/SwinV2-T as a feature extractor. However, this would cause extra cost as you can’t reuse the feature representations when routing to a different network, right?

I would appreciate it if you could clarify this part!
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes OCCAM, a principled approach to optimize classifier assignments across queries, maximizing accuracy under user-specified cost budgets by solving an integer linear programming problem. Experiments demonstrate that OCCAM reduces inference costs by up to 40% with minimal accuracy loss on real-world datasets. The overall review of the paper is positive, so the paper is recommended for acceptance at this time.