- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies the Tunable Prediction Set Size (TPSS) setting and proposes Tunable-sCP (TsCP) to obtain size-controlled prediction sets within split conformal prediction (sCP). The main idea is to split calibration data so that one part selects a data-dependent miscoverage level and the other performs quantile calibration, together with leave-one-out coverage estimation and related theory.
Critical strengths
- The paper gives a reasonably clear diagnosis of why directly choosing a data-dependent level in sCP can break the classical rank argument, and proposes a split-calibration remedy.
- It attempts to discuss coverage estimation and size control in one framework, with some theory-experiment alignment.
Critical weaknesses
- There appears to be a gap between the size constraint in the problem definition and what is actually proved/guaranteed: the theory looks more asymptotic/soft, and in that respect seems not fundamentally different from the eCP route. If the central pitch is “solving TPSS within sCP,” this gap weakens the case.
- The main-text experiments are incomplete: comparisons are narrow and focus mainly on one recent baseline; classification results, additional settings, and ablations are largely deferred to the appendix; more standard size-control or truncation controls are also missing.
- The overall presentation could be improved and polished a lot: the abstract mainly introduces the relavant background, but not their own work TsCP; the main text is not "self-contained" and repeatedly refer to appendix; three figures in the main text are hard to read in printed paper.
Questions for authors
- Why were Conformal Risk Control, standard sCP followed by truncation, and common set-optimization methods not compared? Would TsCP’s advantages still hold after these controls?
- How should the size constraint be accurately described to readers? Are theoretically suggested ranges consistent with empirically best , and how does affect the tightness of the guarantees?
- In practice, which metrics should be reported and how should they be interpreted when budget violations occur? What is the fallback behavior and frequency when the budget is infeasible?
5 comments
Reply [2/4]
Q1. There appears to be a gap between the size constraint in the problem definition and what is actually proved/guaranteed: the theory looks more asymptotic/soft, and in that respect seems not fundamentally different from the eCP route. If the central pitch is "solving TPSS within sCP," this gap weakens the case.
Answer: We thank the reviewer for raising this important concern. We acknowledge that, unlike Backward Conformal Prediction (BCP) [1], which satisfies the prescribed size constraint by construction, our theoretical analysis guarantees only an asymptotic version of the size constraint, as formally stated in Equation (4) and established in Theorem 4.4. Nevertheless, we would like to emphasize that TsCP achieves near-hard size control in practice, even with relatively small calibration datasets, as demonstrated by our empirical evaluation in Appendix D.4.
Specifically, we evaluate the proportion of test points satisfying the prescribed hard size constraint, i.e., , across six regression and classification datasets and varying calibration sizes. The results, reported in Table 1 (Appendix D.4), are reproduced below for the reviewer's convenience.
Table 1: Hard-constraint satisfaction rate (%) across different total calibration set sizes.
| Dataset | 1,000 | 2,000 | 3,000 | 4,000 | 5,000 | 6,000 |
|---|---|---|---|---|---|---|
| Synthetic Regression | 99.1 | 99.7 | 99.2 | 99.1 | 100 | 100 |
| California Housing | 95.7 | 100 | 95.4 | 96.1 | 97.8 | 100 |
| Superconductivity | 100 | 99.5 | 100 | 100 | 100 | 100 |
| Synthetic Classification | 100 | 96.6 | 100 | 100 | 99.6 | 99.6 |
| MNIST | 94.9 | 99.9 | 100 | 98.8 | 95.9 | 100 |
| Covertype | 99.9 | 100 | 100 | 99.9 | 100 | 99.9 |
As shown, even with only 1,000 calibration samples, TsCP satisfies the hard size constraint for at least 94.9% of test points across all six datasets, with four datasets exceeding 99%. At a calibration size of 6,000, four datasets achieve 100% satisfaction, while the remaining two achieve 99.6% and 99.9%, respectively. These results demonstrate that, although our theoretical guarantee is asymptotic, TsCP achieves behavior very close to hard size control in finite-sample settings.
Furthermore, we would like to clarify that the distinction between TsCP and the eCP-based approach extends beyond the type of size constraint guaranteed. As discussed in Appendix C.1, BCP leverages the flexibility of e-values to enforce hard size constraints, whereas TsCP addresses TPSS within the quantile-based sCP framework, preserving its structural properties. This difference enables us to establish an exact marginal coverage characterization with an explicit correction term (Theorem 4.2), together with consistency and variance guarantees for the corresponding LOO estimator (Theorems 5.2–5.3). As demonstrated in Figures 3, 8, and 9, these structural distinctions also translate into empirical advantages, including smaller prediction sets at comparable coverage and substantially more accurate LOO coverage estimation. Therefore, our contribution is not solely to enforce prediction set size constraints, but to establish a fundamentally different sCP-based approach to TPSS with its own theoretical and empirical advantages.
Nevertheless, we fully acknowledge that establishing a finite-sample hard size guarantee remains an important theoretical advantage of BCP. While our results demonstrate that TsCP closely approximates this behavior empirically, we recognize that this does not replace a formal hard-constraint guarantee. We will clarify the distinction between the original TPSS formulation and our asymptotic relaxation in the revised manuscript. Extending TsCP to provide finite-sample hard size guarantees while preserving the structural properties of sCP is an important direction for future research.
[1] Gauthier et al. Backward Conformal Prediction. NeurIPS 2025.
Reply [3/4]
Q2. How should the size constraint be accurately described to readers? Are theoretically suggested ranges consistent with empirically best, and how does affect the tightness of the guarantees?
Answer: We thank the reviewer for this important question. We would like to clarify the precise interpretation of our size constraint, the relationship between the theoretical and empirical choices of , and the role of the truncation parameter .
-
Interpretation of the size constraint. As formally stated in Equation (4), our method guarantees a soft size constraint, rather than a finite-sample hard constraint. Specifically, Theorem 4.4 establishes that as , under Assumptions 4.1 and 4.3, continuity of the population quantile function, and feasibility of the adaptive-level selection. We acknowledge that this distinction should be emphasized more clearly and will clarify it in the revised manuscript.
-
Theoretical and empirical choices of . As discussed in Section 4.2 and Appendix D.3, the slack parameter controls the trade-off between coverage and size-constraint satisfaction. In particular, Theorem 4.4 provides a sufficient theoretical range , where is the constant in Assumption 4.3 controlling local changes in prediction set size. This choice ensures that the slack is sufficient to absorb the discrepancy between the two independently estimated quantiles. On the other hand, smaller values of generally favor higher coverage, while larger values favor stricter size control. Consequently, the empirically preferred depends on the desired trade-off and need not coincide with the theoretically sufficient range. In particular, the asymptotic guarantee of Theorem 4.4 should not be interpreted as applying automatically to choices . This behavior is further supported by our ablation studies in Appendix D.3 (Figures 10 and 11), where we evaluate different values of across six regression and classification datasets. Consistently, we observe that increasing decreases empirical coverage and its theoretical counterpart, while improving the probability of satisfying the prescribed size constraint. These results support the interpretation of as a tunable hyperparameter governing the practical coverage–size trade-off.
-
Role of the truncation parameter . As discussed in detail in Appendix C.2, the primary purpose of is to ensure theoretical stability by restricting the adaptive miscoverage level to . In particular, the proof of Theorem 4.4 requires uniform convergence of the empirical quantiles over this compact interval. Without truncation, extreme order statistics near the endpoints may become unstable, preventing the same uniform convergence argument. Importantly, is not introduced as an additional approximation error or coverage slack. Its influence on the coverage characterization in Theorem 4.2 is indirect, through the selected adaptive level and its correction term. As explained in Appendix C.2, empirical conformal quantiles have an effective resolution of order . Therefore, choosing , such as in our experiments, has negligible practical impact on the resulting prediction sets. Thus, primarily serves a theoretical purpose, rather than introducing a meaningful additional source of conservativeness in our experimental setting.
Reply [1/4]
Thank you for your thoughtful review and constructive feedback. We have revised our manuscript in response to your suggestions, with all changes highlighted in blue. Below, we address each of your concerns in detail.
W2. The main-text experiments are incomplete: comparisons are narrow and focus mainly on one recent baseline; classification results, additional settings, and ablations are largely deferred to the appendix; more standard size-control or truncation controls are also missing.
Q1. How should the size constraint be accurately described to readers? Are theoretically suggested δ ranges consistent with empirically best δ, and how does ϵ affect the tightness of the guarantees?
Answer: We thank the reviewer for raising this important concern. We would like to clarify that our experimental comparison focuses on Backward Conformal Prediction (BCP) [1] because, to the best of our knowledge, it is the most directly comparable existing method specifically designed to address the TPSS problem. In particular, TPSS requires simultaneously (i) controlling the prediction set size according to a user-specified budget S(X) and (ii) providing a corresponding marginal coverage guarantee. While several related methods address prediction set efficiency or risk control, they do not directly satisfy both requirements under their standard formulations.
Conformal Risk Control (CRC). CRC [2] provides finite-sample control of the expected value of a monotone loss function. In particular, choosing the miscoverage indicator as the loss recovers a marginal coverage guarantee. However, this does not simultaneously guarantee that the prediction set satisfies a prescribed instance-wise size budget ∣C(X)∣≤S(X). Similarly, controlling a size-related expected loss does not imply an instance-wise hard size constraint. Therefore, CRC does not directly solve TPSS without additional methodological modifications.
Standard sCP followed by truncation. A natural alternative is to first construct a standard conformal prediction set and subsequently truncate it to satisfy the prescribed size budget. While this approach guarantees size control by construction, truncation generally invalidates the original coverage guarantee, since removing candidate labels may also remove the true label. Thus, this approach satisfies the first TPSS requirement but does not necessarily retain the second.
Standard set-optimization methods. Existing approaches to optimizing conformal prediction sets, such as [3], primarily seek to minimize prediction set size or volume while maintaining a coverage guarantee. However, optimizing prediction set efficiency is fundamentally different from enforcing a user-specified instance-wise maximum size. Consequently, these methods do not directly address the TPSS formulation considered in our work. Furthermore, while regression comparisons are presented in the main text due to space constraints, our experimental evaluation is not limited to these settings. Classification comparisons are provided in Appendix D.2, while additional ablations on the slack parameter, size constraint, budget function, underlying model, and computational efficiency are presented in Appendices D.3–D.7. Nevertheless, we acknowledge that further discussion of the aforementioned alternative approaches, their relationship to TPSS, and their potential adaptation to this setting would strengthen the paper. We will seek to incorporate such a discussion in the revised manuscript, alongside a clearer presentation of our existing experimental results.
We have added comparisons with Conformal Risk Control, post-hoc truncation, and prediction-set optimization at the end of Appendix C.1.2.
References
[1] Gauthier et al. Backward Conformal Prediction. NeurIPS 2025.
[2] Angelopoulos et al. Conformal Risk Control. ICLR 2024.
[3] Gao et al. Volume Optimality in Conformal Prediction with Structured Prediction Sets. ICML 2025.