# Pandora's Regret: A Proper Scoring Rule for Evaluating Sequential Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 3 May 2026.

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

- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [MedMNIST Classification Decathlon: A Lightweight AutoML Benchmark for Medical Image Analysis](https://mlsanity.com/paper/2010.14925/) (2020)
- [Overcoming Data Scarcity in Biomedical Imaging with a Foundational Multi-Task Model](https://mlsanity.com/paper/2311.09847/) (2023)
- [Weighted Brier Score -- an Overall Summary Measure for Risk Prediction Models with Clinical Utility Consideration](https://mlsanity.com/paper/2408.01626/) (2024)
- [From Classification Accuracy to Proper Scoring Rules: Elicitability of Probabilistic Top List Predictions](https://mlsanity.com/paper/2301.11797/) (2023)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)

## Abstract (arXiv)

In sequential search, alternatives are tested until the true class is found. Standard proper scoring rules like log loss are local, ignoring the ranking of competitors and misaligning model evaluation with search utility. We show that sequential search induces a pairwise structure that overcomes this. By analyzing the expected cost of optimal search under varying testing costs, we derive Pandora's Regret: a closed-form, pairwise-additive, and strictly proper scoring rule. Pandora's Regret both elicits true probabilities and penalizes rank-reversing miscalibrations where distractors outrank the true class. Our construction yields a one-parameter Beta family that balances penalties for rank-swapping versus probability magnitude, while retaining a grounded interpretation as expected search cost. We prove that log loss, accuracy, and macro-F1 rely on implicit decision models misaligned with sequential search. Across 597 MedMNIST models, Pandora-based metrics better predict clinical diagnostic costs than standard alternatives, extending decision-theoretic scoring rule construction to the multiclass setting.