Research map / Learning theory and algorithms / Prediction and decision losses
Towards Human-AI Complementarity with Prediction Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that conformal prediction sets are suboptimal for human-AI accuracy, proves finding optimal prediction sets is NP-hard and hard to approximate, and proposes a greedy algorithm that provably beats conformal prediction under a mixture-of-MNL expert model.
Problem
Decision support systems that show human experts prediction sets (from conformal prediction) may not maximize expert accuracy; the optimal prediction set maximizing average expert accuracy is unknown and computationally hard to find.
Approach
Model the expert's prediction distribution over a set with a mixture of multinomial logit models parameterized by the expert's confusion matrix, then select prediction sets with a greedy marginal-gain algorithm over top-k label prefixes; this is guaranteed to match or exceed conformal sets with rank-consistent nonconformity scores.
Key results
- On synthetic tasks (L=10), the greedy algorithm achieves e.g. 0.364 vs 0.340 for Naive at P(Y'=Y)=0.3 with noise 0.3, matching brute force search.
- On ImageNet16H, greedy reaches 0.874 vs best conformal 0.860 (Naive) at noise omega=125 and 0.925 vs 0.918 at omega=110.
- Finding optimal prediction sets is NP-hard and hard to approximate to a factor |Y|^(1-epsilon) under the mixture-of-MNL expert model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy prediction sets instead of conformal prediction | Simulated human expert with VGG-19 classifier · ImageNet16H (ω=95, ω=110, ω=125) | average test accuracy: 0.946 \,\scriptstyle\pm 0.008 -> 0.951 \,\scriptstyle\pm 0.009; 0.919 \,\scriptstyle\pm 0.006 -> 0.925 \,\scriptstyle\pm | Helped |
| Use greedy prediction sets instead of Naive conformal prediction | Simulated human expert with VGG-19 classifier · ImageNet16H (ω=80) | average test accuracy: 0.957 \,\scriptstyle\pm 0.006 -> 0.957 \,\scriptstyle\pm 0.007 | No clear effect |
| Use greedy prediction sets instead of conformal prediction | Simulated experts · Synthetic classification tasks (L=10) | average test accuracy: 0.341 \,\scriptstyle\pm 0.013 -> 0.364 \,\scriptstyle\pm 0.015 | Helped |
| Use greedy prediction sets instead of conformal prediction | Simulated experts · Synthetic classification tasks (L=25) | average test accuracy: 0.399 \,\scriptstyle\pm 0.012 -> 0.431 \,\scriptstyle\pm 0.010 | Helped |
| Use greedy prediction sets instead of conformal prediction | Simulated experts · Synthetic classification tasks (L=50) | average test accuracy: 0.435 \,\scriptstyle\pm 0.014 -> 0.477 \,\scriptstyle\pm 0.016 | Helped |
| Use greedy prediction sets instead of brute-force search | Simulated expert · Synthetic and ImageNet16H | average test accuracy | No clear effect |
Surprising findings
- Conformal prediction sets can be strictly suboptimal for expert accuracy even with a perfectly calibrated classifier, with a 0.49 vs 0.6 accuracy gap in a simple example.
- Average empirical coverage can be a poor proxy for expert accuracy under prediction sets.
Limitations
- Greedy assumes the expert follows the mixture of MNL model; mismatch may degrade performance.
- Hardness suggests no polynomial approximation beyond factor |Y|^(1-epsilon) in general, so guarantees only hold relative to conformal prediction.
- Real-data experiments use majority-vote ground truth and simulated experts rather than live human subjects.
Experimental setup
Datasets: ImageNet16H ILSVRC 2012 scikit-learn make_classification synthetic tasks
Benchmarks: ImageNet16H synthetic classification tasks (L=10, 25, 50)
Metrics: average expert test accuracy per-image accuracy cCDF empirical coverage
Baselines: Naive conformal prediction APS RAPS SAPS brute force search expert alone (None)
Builds on: conformal prediction Straitouri et al. prediction-set decision support APS RAPS SAPS
Closest papers by meaning
- Conformal Prediction Sets Improve Human Decision Making (ICML 2024 · similarity 0.91)
- Designing Decision Support Systems using Counterfactual Prediction Sets (ICML 2024 · similarity 0.90)
- Human Expertise in Algorithmic Prediction (NeurIPS 2024 · similarity 0.87)
- A No Free Lunch Theorem for Human-AI Collaboration (AAAI 2025 · similarity 0.86)
- Learning to Decide with AI Assistance under Human-Alignment (NeurIPS 2026 · similarity 0.86)
- Conformal Prediction for Deep Classifier via Label Ranking (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.