# Who Should Predict? Exact Algorithms For Learning to Defer to Humans

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 56 references that are in the map.
- First posted on arXiv 15 Jan 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution](https://mlsanity.com/paper/2202.10054/) (2022)
- [Automated Hate Speech Detection and the Problem of Offensive Language](https://mlsanity.com/paper/1703.04009/) (2017)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer](https://mlsanity.com/paper/1711.06664/) (2017)
- [Learning to Complement Humans](https://mlsanity.com/paper/2005.00582/) (2020)
- [The Algorithmic Automation Problem: Prediction, Triage, and Human Effort](https://mlsanity.com/paper/1903.12220/) (2019)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Differentiable Learning Under Triage](https://mlsanity.com/paper/2103.08902/) (2021)
- [Towards Unbiased and Accurate Deferral to Multiple Experts](https://mlsanity.com/paper/2102.13004/) (2021)
- [Calibrated Learning to Defer with One-vs-All Classifiers](https://mlsanity.com/paper/2202.03673/) (2022)
- [Understanding the Effect of Out-of-distribution Examples and Interactive Explanations on Human-AI Decision Making](https://mlsanity.com/paper/2101.05303/) (2021)
- [Classification with Rejection Based on Cost-sensitive Classification](https://mlsanity.com/paper/2010.11748/) (2020)
- [Sample Efficient Learning of Predictors that Complement Humans](https://mlsanity.com/paper/2207.09584/) (2022)
- [Regression Under Human Assistance](https://mlsanity.com/paper/1909.02963/) (2019)
- [Combining Human Predictions with Model Probabilities via Confusion Matrices and Calibration](https://mlsanity.com/paper/2109.14591/) (2021)
- [Selective Classification via One-Sided Prediction](https://mlsanity.com/paper/2010.07853/) (2020)
- [Teaching Humans When To Defer to a Classifier via Exemplars](https://mlsanity.com/paper/2111.11297/) (2021)
- [Preferential Mixture-of-Experts: Interpretable Models that Rely on Human Expertise as much as Possible](https://mlsanity.com/paper/2101.05360/) (2021)
- [Incorporating Uncertainty in Learning to Defer Algorithms for Safe Computer-Aided Diagnosis](https://mlsanity.com/paper/2108.07392/) (2021)
- [Improving Learning-to-Defer Algorithms Through Fine-Tuning](https://mlsanity.com/paper/2112.10768/) (2021)
- [Budget Learning via Bracketing](https://mlsanity.com/paper/2004.06298/) (2020)

## Built on by (most cited first, 30 of 70)

- [Learning to Decode Collaboratively with Multiple Language Models](https://mlsanity.com/paper/2403.03870/) (2024)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Learning to Defer to a Population: A Meta-Learning Approach](https://mlsanity.com/paper/2403.02683/) (2024)
- [In Defense of Softmax Parametrization for Calibrated and Consistent Learning to Defer](https://mlsanity.com/paper/2311.01106/) (2023)
- [Realizable H-Consistent and Bayes-Consistent Loss Functions for Learning to Defer](https://mlsanity.com/paper/2407.13732/) (2024)
- [When to Show a Suggestion? Integrating Human Feedback in AI-Assisted Programming](https://mlsanity.com/paper/2306.04930/) (2023)
- [Towards Human-AI Complementarity with Prediction Sets](https://mlsanity.com/paper/2405.17544/) (2024)
- [A Universal Growth Rate for Learning with Smooth Surrogate Losses](https://mlsanity.com/paper/2405.05968/) (2024)
- [Effective Human-AI Teams via Learned Natural Language Rules and Onboarding](https://mlsanity.com/paper/2311.01007/) (2023)
- [A Two-Stage Learning-to-Defer Approach for Multi-Task Learning](https://mlsanity.com/paper/2410.15729/) (2024)
- [Adversarial Robustness in Two-Stage Learning-to-Defer: Algorithms and Guarantees](https://mlsanity.com/paper/2502.01027/) (2025)
- [Mastering Multiple-Expert Routing: Realizable H-Consistency and Strong Guarantees for Learning to Defer](https://mlsanity.com/paper/2506.20650/) (2025)
- [Optimal Query Allocation in Extractive QA with LLMs: A Learning-to-Defer Framework with Theoretical Guarantees](https://mlsanity.com/paper/2410.15761/) (2024)
- [A Causal Framework for Evaluating Deferring Systems](https://mlsanity.com/paper/2405.18902/) (2024)
- [The Road to Artificial SuperIntelligence: A Comprehensive Survey of Superalignment](https://mlsanity.com/paper/2412.16468/) (2024)
- [Budgeted Multiple-Expert Deferral](https://mlsanity.com/paper/2510.26706/) (2025)
- [Cost-Sensitive Learning to Defer to Multiple Experts with Workload Constraints](https://mlsanity.com/paper/2403.06906/) (2024)
- [Strategic Tradeoffs Between Humans and AI in Multi-Agent Bargaining](https://mlsanity.com/paper/2509.09071/) (2025)
- [Why is plausibility surprisingly problematic as an XAI criterion?](https://mlsanity.com/paper/2303.17707/) (2023)
- [Controlling Counterfactual Harm in Decision Support Systems Based on Prediction Sets](https://mlsanity.com/paper/2406.06671/) (2024)
- [Fair Classifiers that Abstain without Harm](https://mlsanity.com/paper/2310.06205/) (2023)
- [AI, Meet Human: Learning Paradigms for Hybrid Decision Making Systems](https://mlsanity.com/paper/2402.06287/) (2024)
- [Learning to Complement and to Defer to Multiple Users](https://mlsanity.com/paper/2407.07003/) (2024)
- [Why Ask One When You Can Ask k? Learning-to-Defer to the Top-k Experts](https://mlsanity.com/paper/2504.12988/) (2025)
- [Towards Human-AI Complementarity in Matching Tasks](https://mlsanity.com/paper/2508.13285/) (2025)
- [When to Trust the Cheap Check: Weak and Strong Verification for Reasoning](https://mlsanity.com/paper/2602.17633/) (2026)
- [To Ask or Not to Ask: Learning to Require Human Feedback](https://mlsanity.com/paper/2510.08314/) (2025)
- [Learning-to-Defer in Non-Stationary Time Series via Switching State-Space Models](https://mlsanity.com/paper/2601.22538/) (2026)
- [Learning to Complement with Multiple Humans](https://mlsanity.com/paper/2311.13172/) (2023)

## Abstract (arXiv)

Automated AI classifiers should be able to defer the prediction to a human decision maker to ensure more accurate predictions. In this work, we jointly train a classifier with a rejector, which decides on each data point whether the classifier or the human should predict. We show that prior approaches can fail to find a human-AI system with low misclassification error even when there exists a linear classifier and rejector that have zero error (the realizable setting). We prove that obtaining a linear pair with low error is NP-hard even when the problem is realizable. To complement this negative result, we give a mixed-integer-linear-programming (MILP) formulation that can optimally solve the problem in the linear setting. However, the MILP only scales to moderately-sized problems. Therefore, we provide a novel surrogate loss function that is realizable-consistent and performs well empirically. We test our approaches on a comprehensive set of datasets and compare to a wide range of baselines.