# On Efficient Approximate Queries over Machine Learning Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 61 references that are in the map.
- First posted on arXiv 6 Jun 2022.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [You Only Look Once: Unified, Real-Time Object Detection](https://mlsanity.com/paper/1506.02640/) (2015)
- [YOLO9000: Better, Faster, Stronger](https://mlsanity.com/paper/1612.08242/) (2016)
- [Multi-Label Image Recognition with Graph Convolutional Networks](https://mlsanity.com/paper/1904.03582/) (2019)
- [BEHRT: Transformer for Electronic Health Records](https://mlsanity.com/paper/1907.09538/) (2019)
- [Doctor AI: Predicting Clinical Events via Recurrent Neural Networks](https://mlsanity.com/paper/1511.05942/) (2015)
- [Clipper: A Low-Latency Online Prediction Serving System](https://mlsanity.com/paper/1612.03079/) (2016)
- [Adaptive Neural Networks for Efficient Inference](https://mlsanity.com/paper/1702.07811/) (2017)
- [SIFT Meets CNN: A Decade Survey of Instance Retrieval](https://mlsanity.com/paper/1608.01807/) (2016)
- [TVM: An Automated End-to-End Optimizing Compiler for Deep Learning](https://mlsanity.com/paper/1802.04799/) (2018)
- [Focus: Querying Large Video Datasets with Low Latency and Low Cost](https://mlsanity.com/paper/1801.03493/) (2018)
- [NoScope: Optimizing Neural Network Queries over Video at Scale](https://mlsanity.com/paper/1703.02529/) (2017)
- [Scaling Video Analytics on Constrained Edge Nodes](https://mlsanity.com/paper/1905.13536/) (2019)
- [Amazon SageMaker Autopilot: a white box AutoML solution at scale](https://mlsanity.com/paper/2012.08483/) (2020)
- [Physical Representation-based Predicate Optimization for a Visual Analytics Database](https://mlsanity.com/paper/1806.04226/) (2018)
- [Extending Relational Query Processing with ML Inference](https://mlsanity.com/paper/1911.00231/) (2019)
- [Approximate Selection with Guarantees using Proxies](https://mlsanity.com/paper/2004.00827/) (2020)
- [Optimizing Machine Learning Inference Queries with Correlative Proxy Models](https://mlsanity.com/paper/2201.00309/) (2022)
- [Machine Learning at Microsoft with ML .NET](https://mlsanity.com/paper/1905.05715/) (2019)
- [26ms Inference Time for ResNet-50: Towards Real-Time Execution of all DNNs on Smartphone](https://mlsanity.com/paper/1905.00571/) (2019)
- [Efficiently Answering Durability Prediction Queries](https://mlsanity.com/paper/2103.12887/) (2021)

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

- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute](https://mlsanity.com/paper/2506.22716/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees](https://mlsanity.com/paper/2509.02896/) (2025)
- [OCCAM: Towards Cost-Efficient and Accuracy-Aware Classification Inference](https://mlsanity.com/paper/2406.04508/) (2024)
- [Exploration of Summarization by Generative Language Models for Automated Scoring of Long Essays](https://mlsanity.com/paper/2510.22830/) (2025)
- [HERA: Hybrid Edge-cloud Resource Allocation for Cost-Efficient AI Agents](https://mlsanity.com/paper/2504.00434/) (2025)

## Abstract (arXiv)

The question of answering queries over ML predictions has been gaining attention in the database community. This question is challenging because the cost of finding high quality answers corresponds to invoking an oracle such as a human expert or an expensive deep neural network model on every single item in the DB and then applying the query. We develop a novel unified framework for approximate query answering by leveraging a proxy to minimize the oracle usage of finding high quality answers for both Precision-Target (PT) and Recall-Target (RT) queries. Our framework uses a judicious combination of invoking the expensive oracle on data samples and applying the cheap proxy on the objects in the DB. It relies on two assumptions. Under the Proxy Quality assumption, proxy quality can be quantified in a probabilistic manner w.r.t. the oracle. This allows us to develop two algorithms: PQA that efficiently finds high quality answers with high probability and no oracle calls, and PQE, a heuristic extension that achieves empirically good performance with a small number of oracle calls. Alternatively, under the Core Set Closure assumption, we develop two algorithms: CSC that efficiently returns high quality answers with high probability and minimal oracle usage, and CSE, which extends it to more general settings. Our extensive experiments on five real-world datasets on both query types, PT and RT, demonstrate that our algorithms outperform the state-of-the-art and achieve high result quality with provable statistical guarantees.