# Provably Minimum-Length Conformal Prediction Sets for Ordinal Classification

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 50 references that are in the map.
- First posted on arXiv 20 Nov 2025.

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

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Photo Aesthetics Ranking Network with Attributes and Content Adaptation](https://mlsanity.com/paper/1606.01621/) (2016)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [API Is Enough: Conformal Prediction for Large Language Models Without Logit-Access](https://mlsanity.com/paper/2403.01216/) (2024)
- [Improving Expert Predictions with Conformal Prediction](https://mlsanity.com/paper/2201.12006/) (2022)
- [Conformal Prediction for Deep Classifier via Label Ranking](https://mlsanity.com/paper/2310.06430/) (2023)
- [Improving Conditional Coverage via Orthogonal Quantile Regression](https://mlsanity.com/paper/2106.00394/) (2021)
- [Moving Window Regression: A Novel Approach to Ordinal Regression](https://mlsanity.com/paper/2203.13122/) (2022)
- [Improving Trustworthiness of AI Disease Severity Rating in Medical Imaging with Ordinal Conformal Prediction Sets](https://mlsanity.com/paper/2207.02238/) (2022)
- [On the Consistency of Ordinal Regression Methods](https://mlsanity.com/paper/1408.2327/) (2014)
- [Probabilistic Conformal Prediction with Approximate Conditional Validity](https://mlsanity.com/paper/2407.01794/) (2024)
- [An Information Theoretic Perspective on Conformal Prediction](https://mlsanity.com/paper/2405.02140/) (2024)
- [ConR: Contrastive Regularizer for Deep Imbalanced Regression](https://mlsanity.com/paper/2309.06651/) (2023)
- [Ord2Seq: Regarding Ordinal Regression as Label Sequence Prediction](https://mlsanity.com/paper/2307.09004/) (2023)
- [CLIP-DR: Textual Knowledge-Guided Diabetic Retinopathy Grading with Ranking-aware Prompting](https://mlsanity.com/paper/2407.04068/) (2024)
- [Robust Image Ordinal Regression with Controllable Image Generation](https://mlsanity.com/paper/2305.04213/) (2023)
- [Conformal Risk Control for Ordinal Classification](https://mlsanity.com/paper/2405.00417/) (2024)
- [The Pitfalls and Promise of Conformal Inference Under Adversarial Attacks](https://mlsanity.com/paper/2405.08886/) (2024)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Improve Representation for Imbalanced Regression through Geometric Constraints](https://mlsanity.com/paper/2503.00876/) (2025)
- [ConformalSAM: Unlocking the Potential of Foundational Segmentation Models in Semi-Supervised Semantic Segmentation with Conformal Prediction](https://mlsanity.com/paper/2507.15803/) (2025)
- [Distribution-free Conformal Prediction for Ordinal Classification](https://mlsanity.com/paper/2404.16610/) (2024)

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

- [CHOIR: heterogeneity-aware conformal prediction for crash injury severity across driver safety strata](https://mlsanity.com/paper/2609.11592/) (2026)

## Abstract (arXiv)

Ordinal classification has been widely applied in many high-stakes applications, e.g., medical imaging and diagnosis, where reliable uncertainty quantification (UQ) is essential for decision making. Conformal prediction (CP) is a general UQ framework that provides statistically valid guarantees, which is especially useful in practice. However, prior ordinal CP methods mainly focus on heuristic algorithms or restrictively require the underlying model to predict a unimodal distribution over ordinal labels. Consequently, they provide limited insight into coverage-efficiency trade-offs, or a model-agnostic and distribution-free nature favored by CP methods. To this end, we fill this gap by propose an ordinal-CP method that is model-agnostic and provides instance-level optimal prediction intervals. Specifically, we formulate conformal ordinal classification as a minimum-length covering problem at the instance level. To solve this problem, we develop a sliding-window algorithm that is optimal on each calibration data, with only a linear time complexity in K, the number of label candidates. The local optimality per instance further also improves predictive efficiency in expectation. Moreover, we propose a length-regularized variant that shrinks prediction set size while preserving coverage. Experiments on four benchmark datasets from diverse domains are conducted to demonstrate the significantly improved predictive efficiency of the proposed methods over baselines (by 15% decrease on average over four datasets).