# Approximate Selection with Guarantees using Proxies

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2020.

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

- [Semantic Operators: A Declarative Model for Rich, AI-based Data Processing](https://mlsanity.com/paper/2407.11418/) (2024)
- [Cortex AISQL: A Production SQL Engine for Unstructured Data](https://mlsanity.com/paper/2511.07663/) (2025)
- [Cut Costs, Not Accuracy: LLM-Powered Data Processing with Guarantees](https://mlsanity.com/paper/2509.02896/) (2025)
- [On Efficient Approximate Queries over Machine Learning Models](https://mlsanity.com/paper/2206.02845/) (2022)
- [Using Sampling to Estimate and Improve Performance of Automated Scoring Systems with Guarantees](https://mlsanity.com/paper/2111.08906/) (2021)
- [Larch: Learned Query Optimization for Semantic Predicates](https://mlsanity.com/paper/2606.07923/) (2026)
- [ScaleDoc: Scaling LLM-based Predicates over Large Document Collections](https://mlsanity.com/paper/2509.12610/) (2025)
- [Streaming Model Cascades for Semantic SQL](https://mlsanity.com/paper/2604.00660/) (2026)
- [Fast LLM-Based Semantic Filtering: From a Unified Framework to an Adaptive Two-Phase Method](https://mlsanity.com/paper/2606.08090/) (2026)
- [Personalized Top-k Set Queries Over Predicted Scores](https://mlsanity.com/paper/2502.12998/) (2025)
- [Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm](https://mlsanity.com/paper/2603.04799/) (2026)
- [Hydro: Adaptive Query Processing of ML Queries](https://mlsanity.com/paper/2403.14902/) (2024)
- [Compositional Online Learning for Semantic Data Processing Systems](https://mlsanity.com/paper/2608.27244/) (2026)
- [Semantic Views: Certified Reuse of LLM Labels Across Semantic Queries](https://mlsanity.com/paper/2610.12768/) (2026)
- [Same Query, Different Answer: Run-to-Run Variance in Semantic Query Processing](https://mlsanity.com/paper/2610.13823/) (2026)

## Abstract (arXiv)

Due to the falling costs of data acquisition and storage, researchers and industry analysts often want to find all instances of rare events in large datasets. For instance, scientists can cheaply capture thousands of hours of video, but are limited by the need to manually inspect long videos to identify relevant objects and events. To reduce this cost, recent work proposes to use cheap proxy models, such as image classifiers, to identify an approximate set of data points satisfying a data selection filter. Unfortunately, this recent work does not provide the statistical accuracy guarantees necessary in scientific and production settings. In this work, we introduce novel algorithms for approximate selection queries with statistical accuracy guarantees. Namely, given a limited number of exact identifications from an oracle, often a human or an expensive machine learning model, our algorithms meet a minimum precision or recall target with high probability. In contrast, existing approaches can catastrophically fail in satisfying these recall and precision targets. We show that our algorithms can improve query result quality by up to 30x for both the precision and recall targets in both real and synthetic datasets.