# Distribution-free calibration guarantees for histogram binning without sample splitting

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 10 May 2021.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Verified Uncertainty Calibration](https://mlsanity.com/paper/1909.10155/) (2019)
- [Mitigating Bias in Calibration Error Estimation](https://mlsanity.com/paper/2012.08668/) (2020)
- [Calibration tests in multi-class classification: A unifying framework](https://mlsanity.com/paper/1910.11385/) (2019)
- [Distribution-free binary classification: prediction sets, confidence intervals and calibration](https://mlsanity.com/paper/2006.10564/) (2020)

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

- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Top-label calibration and multiclass-to-binary reductions](https://mlsanity.com/paper/2107.08353/) (2021)
- [Human-Aligned Calibration for AI-Assisted Decision Making](https://mlsanity.com/paper/2306.00074/) (2023)
- [Restoring Calibration for Aligned Large Language Models: A Calibration-Aware Fine-Tuning Approach](https://mlsanity.com/paper/2505.01997/) (2025)
- [Improving Screening Processes via Calibrated Subset Selection](https://mlsanity.com/paper/2202.01147/) (2022)
- [Causal isotonic calibration for heterogeneous treatment effects](https://mlsanity.com/paper/2302.14011/) (2023)
- [Self-Calibrating Conformal Prediction](https://mlsanity.com/paper/2402.07307/) (2024)
- [QA-Calibration of Language Model Confidence Scores](https://mlsanity.com/paper/2410.06615/) (2024)
- [A Benchmark Study on Calibration](https://mlsanity.com/paper/2308.11838/) (2023)
- [Minimum-Risk Recalibration of Classifiers](https://mlsanity.com/paper/2305.10886/) (2023)
- [Information-theoretic Generalization Analysis for Expected Calibration Error](https://mlsanity.com/paper/2405.15709/) (2024)
- [Taking a Step Back with KCal: Multi-Class Kernel-Based Calibration for Deep Neural Networks](https://mlsanity.com/paper/2202.07679/) (2022)
- [Stabilized Inverse Probability Weighting via Isotonic Calibration](https://mlsanity.com/paper/2411.06342/) (2024)
- [Scaffolding Sets](https://mlsanity.com/paper/2111.03135/) (2021)
- [Online Platt Scaling with Calibeating](https://mlsanity.com/paper/2305.00070/) (2023)
- [Birds of a Feather Trust Together: Knowing When to Trust a Classifier via Adaptive Neighborhood Aggregation](https://mlsanity.com/paper/2211.16466/) (2022)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction](https://mlsanity.com/paper/2502.05676/) (2025)
- [Orthogonal Causal Calibration](https://mlsanity.com/paper/2406.01933/) (2024)
- [Same Answer, Different Confidence: Protocol Sensitivity in LLM Confidence Calibration](https://mlsanity.com/paper/2605.27752/) (2026)
- [Improving the Finite Sample Estimation of Average Treatment Effects using Double/Debiased Machine Learning with Propensity Score Calibration](https://mlsanity.com/paper/2409.04874/) (2024)
- [Faster online calibration without randomization: interval forecasts and the power of two choices](https://mlsanity.com/paper/2204.13087/) (2022)
- [Active Learning and Novel Model Calibration Measurements for Automated Visual Inspection in Manufacturing](https://mlsanity.com/paper/2209.05486/) (2022)
- [PAC-Bayes Analysis for Recalibration in Classification](https://mlsanity.com/paper/2406.06227/) (2024)
- [Pearls from Pebbles: Improved Confidence Functions for Auto-labeling](https://mlsanity.com/paper/2404.16188/) (2024)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (2025)
- [Bellman Calibration for V-Learning in Offline Reinforcement Learning](https://mlsanity.com/paper/2512.23694/) (2025)
- [Calibrating Model-Based Evaluation Metrics for Summarization](https://mlsanity.com/paper/2604.17200/) (2026)
- [Parity Calibration](https://mlsanity.com/paper/2305.18655/) (2023)
- [A Decision-driven Methodology for Designing Uncertainty-aware AI Self-Assessment](https://mlsanity.com/paper/2408.01301/) (2024)

## Abstract (arXiv)

We prove calibration guarantees for the popular histogram binning (also called uniform-mass binning) method of Zadrozny and Elkan [2001]. Histogram binning has displayed strong practical performance, but theoretical guarantees have only been shown for sample split versions that avoid 'double dipping' the data. We demonstrate that the statistical cost of sample splitting is practically significant on a credit default dataset. We then prove calibration guarantees for the original method that double dips the data, using a certain Markov property of order statistics. Based on our results, we make practical recommendations for choosing the number of bins in histogram binning. In our illustrative simulations, we propose a new tool for assessing calibration -- validity plots -- which provide more information than an ECE estimate. Code for this work will be made publicly available at https://github.com/aigen/df-posthoc-calibration.