# Efficient Online ML API Selection for Multi-Label Classification Tasks

arXiv: https://arxiv.org/abs/2102.09127 · HTML: https://mlsanity.com/paper/2102.09127/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 63 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale](https://mlsanity.com/paper/1811.00982/) (2018)
- [PP-OCR: A Practical Ultra Lightweight OCR System](https://mlsanity.com/paper/2009.09941/) (2020)
- [ICDAR 2019 Robust Reading Challenge on Reading Chinese Text on Signboard](https://mlsanity.com/paper/1912.09641/) (2019)
- [ICDAR 2019 Competition on Large-scale Street View Text with Partial Labeling -- RRC-LSVT](https://mlsanity.com/paper/1909.07741/) (2019)
- [Google's Cloud Vision API Is Not Robust To Noise](https://mlsanity.com/paper/1704.05051/) (2017)
- [Model-based Pricing for Machine Learning in a Data Marketplace](https://mlsanity.com/paper/1805.11450/) (2018)
- [FrugalML: How to Use ML Prediction APIs More Accurately and Cheaply](https://mlsanity.com/paper/2006.07512/) (2020)
- [Learning Complexity-Aware Cascades for Deep Pedestrian Detection](https://mlsanity.com/paper/1507.05348/) (2015)
- [Boosted Cascaded Convnets for Multilabel Classification of Thoracic Diseases in Chest Radiographs](https://mlsanity.com/paper/1711.08760/) (2017)
- [CascadeML: An Automatic Neural Network Architecture Evolution and Training Algorithm for Multi-label Classification](https://mlsanity.com/paper/1904.10551/) (2019)
- [A multi-criteria approach to approximate solution of multiple-choice knapsack problem](https://mlsanity.com/paper/1712.06723/) (2017)

## Built on by (most cited first, 11 of 11)

- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [A Unified Approach to Routing and Cascading for LLMs](https://mlsanity.com/paper/2410.10347/) (2024)
- [MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs](https://mlsanity.com/paper/2407.10834/) (2024)
- [CARROT: A Cost Aware Rate Optimal Router](https://mlsanity.com/paper/2502.03261/) (2025)
- [Adaptive LLM Routing under Budget Constraints](https://mlsanity.com/paper/2508.21141/) (2025)
- [Are LLMs Correctly Integrated into Software Systems?](https://mlsanity.com/paper/2407.05138/) (2024)
- [HAPI: A Large-scale Longitudinal Dataset of Commercial ML API Predictions](https://mlsanity.com/paper/2209.08443/) (2022)
- [OCCAM: Towards Cost-Efficient and Accuracy-Aware Classification Inference](https://mlsanity.com/paper/2406.04508/) (2024)
- [MemSpec: Memory-Aware Runtime for Adaptive Draft Scheduling in Speculative Decoding on Edge Devices](https://mlsanity.com/paper/2608.10362/) (2026)
- [Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints](https://mlsanity.com/paper/2608.16375/) (2026)
- [Optimal Model Activation Policies for Inference Networks of Large Language Models](https://mlsanity.com/paper/2609.15992/) (2026)

## Abstract (arXiv)

Multi-label classification tasks such as OCR and multi-object recognition are a major focus of the growing machine learning as a service industry. While many multi-label prediction APIs are available, it is challenging for users to decide which API to use for their own data and budget, due to the heterogeneity in those APIs' price and performance. Recent work shows how to select from single-label prediction APIs. However the computation complexity of the previous approach is exponential in the number of labels and hence is not suitable for settings like OCR. In this work, we propose FrugalMCT, a principled framework that adaptively selects the APIs to use for different data in an online fashion while respecting user's budget. The API selection problem is cast as an integer linear program, which we show has a special structure that we leverage to develop an efficient online API selector with strong performance guarantees. We conduct systematic experiments using ML APIs from Google, Microsoft, Amazon, IBM, Tencent and other providers for tasks including multi-label image classification, scene text recognition and named entity recognition. Across diverse tasks, FrugalMCT can achieve over 90% cost reduction while matching the accuracy of the best single API, or up to 8% better accuracy while matching the best API's cost.