Scalable Utility-Aware Multiclass Calibration

We thank the reviewer for their detailed feedback and positive assessment. We address the reviewer's points .

1. On the gap between theory and practice:

We thank the reviewer for this important comment. We agree that our paper does not provide prescriptive advice on how to design the optimal utility function for a specific application, such as in a particular biomedical context. Our goal is different but, we believe, equally practical.

Our framework's practicality lies in providing a robust and scalable toolkit for the crucial meta-task of benchmarking and comparing models. Practitioners are often faced with choosing between different models or post-hoc calibration methods, and existing metrics can be misleading (for example, due to binning artifacts) or computationally infeasible for high-dimensional problems. Our contribution is to provide a practical solution to this problem, while enabling the practitioner to choose the utility class, e.g. among the examples given in Sec 3.3. Our ``application-centric'' claim stems from the ability that we offer to choose the class of utilities - a choice that is certainly application dependent, and can only be performed by a domain expert.

For example, using our eCDF evaluation methodology (Section 4), across a whole class of potential downstream utilities (e.g., Rank-based in Fig. 1a and Linear in Fig. 1b), a user can rigorously compare many models (TS, Dirichlet, IR, VS, etc.), gaining a much deeper understanding of their relative reliability, for that specific choice of utilities (a choice that once again will depend on the application). In this sense, we believe our work is practical, not at the level of domain-specific consultation, but at the crucial level of model development, evaluation, and selection. We will clarify this positioning in the updated version of the paper.

However, we noticed that reviewer GhnP was puzzled by the use of "application centric" - we can rephrase as "application-dependent'', or more systematically `"utility-aware'' (as in the title) if the reviewer feels it makes the contribution clearer.

2. On the scope of experiments:

We appreciate the suggestion to explore more diverse domains. Our initial focus on image classification, particularly with CIFAR-100 and ImageNet-1K, was driven by the need to test our framework's scalability on problems with a large number of classes (C=100 and C=1000, respectively), for which numerous high-quality pre-trained models are readily available.

To demonstrate the versatility of our framework beyond computer vision, we commit to adding a new experiment on a text classification task in the final version of the paper. We plan to fine-tune a pre-trained BERT-based model on a standard text benchmark and apply our full utility calibration analysis.

3. On the impact of test set size:

This is an excellent question. Our theoretical analysis in Lemma 3.3 shows that our empirical estimator for a given utility function converges to the true value at a rate of $\tilde{O}(1/\sqrt{n})$, where $n$ is the test set size. The experiments in our paper use several thousand test samples, which, according to our theory, is a regime that ensures accurate estimation.

Nevertheless, the reviewer raises a very interesting point about the estimator's empirical behavior in lower-data regimes. We agree that investigating the estimator's bias and variance as a function of sample size is a valuable analysis for practitioners. To address this, we will add a new study to the appendix in the final version of the paper. In this study, we will vary the test set size and measure the stability (mean and standard deviation) of our metrics across multiple random subsamples.

Again, we thank you for your feedback and we are confident that addressing them will improve the manuscript. We remain available to answer additional questions.

We are grateful for the reviewer's feedback. We believe that integrating it will significantly strengthen our manuscript. We address the reviewer's questions and suggestions below.

Q1: Experiments on Sensitivity to Utility Class Structure

We thank the reviewer for this interesting suggestion. Following up on your question, and to better understand the dynamics of calibrating against different utility structures, we are currently conducting new experiments focused on the convergence speed of our patching algorithm (along with the performance) when faced with "aligned" versus "misaligned" non-linear utility classes. This experiment will provide another example of how the choice of the utility class $\mathcal{U}$ affects calibration. We hereafter detail this setup.

More precisely, our additional utility model is based on a user-defined gain matrix $R \in [0,1]^{C \times C}$, where $R_{ij}$ is the reward for predicting class $j$ when the true class is $i$. We set $R_{ii}=1$. Given a model's prediction $p$, a rational agent first chooses the action $j^\star(p)$ that maximizes their expected gain: $j^\star (p) = argmax_j \sum_i p_i R_{ij}$. The realized utility is then $u_R(p, y=e_i) = R_{i, j^\star(p)}$.

We constructed two distinct utility classes based on this model:

• Aligned Class: This models a group of users with a similar, low tolerance for any error. A gain matrix $R$ for this class has $R_{ii}=1$ and all off-diagonal entries ($i \neq j$) sampled independently from a $\text{Uniform}(0, 0.1)$ distribution.
• Misaligned Class: This models a mix of specialists with distinct biases. We partition the classes into disjoint subsets ($K_1, K_2, \dots$). A user specializing in subset $K_m$ has a gain matrix $R$ with $R_{ii}=1$, $R_{ij}=0.2$ for all $j \in K_m$ ($i \neq j$), and all other off-diagonal entries being zero. The final utility class is formed by sampling a mix of these different specialists.

We run our iterative patching/auditing style algorithm targeting each class. In addition, we are investigating the effect (if any) that other generic post-hoc calibration in the literature have on utility calibration in this case. We are currently conducting the experiments and expect to have the results by Friday 1st of August. Unfortunately, it is no longer possible to communicate plots, but we will be able to provide some of the results in table format (upon request, as we may not be able to post without answering a question).

Response to Q2: Comparative Discussion with Recent Literature

We thank the reviewer for pointing out several highly relevant papers. We agree that a detailed comparison is necessary to properly position our work. We will add a detailed discussion to our related work section.

• Comparison with Noarov et al. (2023): This work provides an online algorithm for the online adversarial setting, guaranteeing low regret for downstream agents who best-respond to its predictions. Its technical core is a bound on the cumulative signed error of its vector predictions, conditioned on events defined by the agent's best-response action regions. This guarantee is engineered to ensure the agent's policy achieves low regret over a sequence of interactions. In contrast, our work is designed for the batch evaluation of a given predictor and is agnostic to the agent's specific behavioral model. Our metric, ${UC}(f, u)$, is not a regret bound, guaranteeing the agent good utilities. Consequently, our guarantees are about the properties of the utility estimation rather than the agent policy. Both works start from the same principle—that predictions should be unbiased conditional on events determined by downstream utilities—but they calibrate different objects and thus yield different guarantees, consequences and applications. In Noarov et al., event-conditional unbiasedness is imposed coordinate-wise on the whole prediction vector $p_t$: $|\sum_t (p_{t,i}-y_{t,i})E(x_t,p_t)| \le \alpha(n_t(E))$ must hold for every coordinate $i$ and every event $E$. Our paper instead collapses $p_t$ to a task-specific scalar $v_u(X)$ and requires that its worst-case interval bias $\sup_{I\subseteq[-1,1]}|\mathbb E[(u(f(X),Y)-v_u(X))\mathbf{1}\{v_u(X)\in I\}]|$ be small. This difference can cause both settings to widely deviate. For example, in our class-wise setting, Noarov et al. formulation would force the entire averaged prediction vector to match the averaged outcomes.

• Comparison with Roth and Shi (2024): In a similar direction, this work also focuses on the online adversarial setting, designing a forecasting algorithm to ensure low swap regret for all downstream decision-making agents. Their primary objective is to achieve superior regret rates. To do this, they design predictions that are unbiased only on a chosen set of events, and their guarantees apply specifically to agents who adopt certain behavioral models (e.g., (smooth) best-response). To this end, for dimension $1$ and $2$, they relax the requirement that the utility functions be known in advance, only requiring them to be $L$ Lipschitz. For higher dimensions, they require the best-responding agents to have known number actions and to smoothly best-respond.

• Comparison with Hu and Wu (2024): This work focuses online (discrete/binned) binary prediction setting, proposing an efficient algorithm to minimize the Calibration Decision Loss (CDL), which is equivalent to worst-case swap regret of best-responding agents. Their primary contribution is an online algorithm with provably near-optimal error rates for CDL. Most interestingly, their work shows a separation in regret rates between CDL and the Expected Calibration Error, i.e., it is possible to achieve a rate for CDL that breaks the lower bound on ECE. In contrast, our framework aims at achieving a scalable assessment methodology for multiclass models.

• Comparison with Kimin et al (2023): In the binary setting, U-Calibration framework is designed for online, adversarial decision-making with the goal of providing an online forecasting algorithm that guarantees low external regret for any rational agent. Technically, its error is the maximum possible regret over the entire class of bounded proper scoring rules. While we clearly align with some of the methodological choice of U-cal, our work differs in setting, approach, and the decision-theoretic consequence implied.

Again, we are grateful for the reviewer suggestion to compare with this body of work and we will add a version of this detailed discussion to the related work section to clearly situate our contribution.

Response to Q3, Presentation, Focus, and Novelty

We appreciate the reviewer's feedback on this. We will revise the manuscript to improve its clarity and better articulate our contributions.

• Focus on Assessment: Indeed our primary goal is to propose a scalable framework for assessing multiclass calibration. We will revise the introduction and section transitions to make this narrative clearer. The decision-theoretic benefits (Sec 3.1) are included to demonstrate why our metric is meaningful, and the post-hoc methods are included to show that achieving good performance on our metric is possible. We will modify our manuscript to keep the assessment narrative more central while defining the metric, justifying its value, and showing it is achievable. We will edit the text to make this flow more explicit for the reader. To further clarify our focus, we will revise the title to "Scalable Evaluation of Utility-Aware Multiclass Calibration."

• Technical and Conceptual Novelty: We believe our core novelty lies in the synthesis and extension of existing tools to create a unified and scalable evaluation framework that was previously missing for multiclass models. While existing methods are often either computationally intractable in high dimensions or suffer from high bias, our framework bridges this critical gap. The concepts of "proactive" and "interactive" measurability are crucial for explaining why this gap exists and how our eCDF-based evaluation approach offers a practical and scalable solution. We will revise the manuscript to better highlight how this synthesis provides a valuable new perspective on the problem of multiclass calibration assessment.

Once again, we thank the reviewer for their constructive and insightful feedback. We are confident that these revisions will substantially improve the paper, and we are eager to answer any follow-up questions during the discussion period.

We thank the reviewer for their thoughtful feedback and positive assessment of our work. We appreciate the constructive questions, which we proceed to answer below.

Response to Q1 and Weakness 1: Clarification on Top-K Utility

As defined in Example 3.7, the class of top-K utilities, ${U_{TopK}}$, is a finite set of $C$ distinct utility functions: ${U_{TopK}} = \lbrace u_K \mid K \in [C]\rbrace$, where $u_K(p, e_j)$ is 1 if the rank of class $j$ for prediction $p$ is less than or equal to $K$, and 0 otherwise. This can be seen as a generalization of top-class calibration.

The metric reported in our tables as $UC_{TopK}$ is the worst-case utility calibration error over this entire finite set: $UC(f, U_{TopK}) = \sup_{K \in [C]} UC(f, u_K)$. Since this is a supremum over a finite set of size $C$, we can compute it directly by evaluating $UC(f, u_K)$ for each $K=1, \dots, C$ and taking the maximum. Thus, no sampling is required for this metric.

In contrast, the sampling-based eCDF evaluation described in Section 4 is used for the much richer, infinite utility classes like linear utilities, U_lin, and general rank-based utilities, U_rank. For these classes, computing the true supremum is computationally intractable, making the eCDF approach a practical and powerful tool for analysis. We will revise the text to make this distinction clearer.

Response to Weakness 2: Empirical Runtime

We thank the reviewer for the suggestion to discuss empirical runtime. While we did not include a dedicated table, we can confirm that our evaluation framework is highly scalable. The total compute for all experiments was approximately 80 GPU hours, but the vast majority of this was spent on fitting the various baseline post-hoc calibration methods.

Our evaluation framework itself is very efficient. For a given model, generating a full eCDF plot (by sampling 1000 utilities and evaluating the error for each) took approximately 60 minutes. This performance was achieved using a parallelized JAX implementation, which we will open-source.

Response to Weakness 3 and Q2: Deeper Experimental Analysis and Failure Cases

We appreciate the reviewer's push for a deeper analysis and are happy to elaborate on the insights from our framework.

Deeper Insights from Our Metrics: Our utility-aware metrics offer a more discerning analysis than standard ones. For instance, in Table 1 (ResNet20-CIFAR100), while Isotonic Regression (IR) and Temperature Scaling (T.S.) show similar improvements on top-class error (our UC_TCE metric), our more comprehensive UC_TopK metric reveals a key difference: T.S. calibrates well across all top-K ranks, whereas IR's benefit is largely confined to the top-1 prediction. In this case, UC_TopK provides a more complete picture of calibration reliability.

Failure Case for Standard Metrics and Practical Implications: Our eCDF analysis provides an example of a failure case where standard metrics can be misleading. As seen in Figure 1, some post-hoc methods perform worse than the uncalibrated model for the class of rank-based utilities, U_rank, even as standard metrics like binned TCE suggest improvement. This critical trade-off is not observable when looking at classical metrics alone.

This analysis underscores the practical takeaway from our work. By providing tools to evaluate calibration against specific utility classes or to visualize performance distributions via eCDFs, our framework empowers practitioners to make more informed choices about model reliability.

Again, we thank the reviewer for their valuable and constructive feedback. We are eager to answer any additional questions during the discussion period.

We thank the reviewer for their detailed and constructive feedback, which will help us significantly improve the clarity and impact of our work. We address each of the reviewer's points below.

Response to W1 & W2: Relationship to Decision Calibration [14]

We thank the reviewer for this important question. Our framework is indeed related to Decision Calibration (DC) [14], but differs conceptually and is designed to overcome its practical limitations.

1. Conceptual Difference: DC explicitly models a scenario where a user chooses from one of $K$ actions. Its guarantee is that for any utility function over outcomes and $K$ actions, the estimated loss of an optimal/best-response policy derived from the model (and some utility function) is unbiased. In contrast, our framework abstracts away the explicit action space. The utility function $u(f(X), Y)$ is designed to encapsulate the entire decision-making procedure and its resulting utility. Instead of providing unbiasedness estimation guarantees for a set of policies, we provide a guarantee on the predicted utility value itself, ensuring that it is calibrated against the realized utility, particularly for the worst-case range of predicted utility values.

2. Practicality and Empirical Comparison: We opted not to include DC in our empirical evaluation for two key reasons. First, as we cite from [11] Gopalan et al. (2024), formally measuring DC error is computationally intractable, with complexity scaling exponentially in the number of classes $C$, even for $K=2$. Second, while Zhao et al. (2021) propose a more tractable relaxation (Sec 4.4 in their paper), it involves solving a non-trivial optimization problem and comes with no formal guarantees that its solution corresponds to the true DC error. Given the lack of guarantees on the meaningfulness of this proxy, we opted not to compare against it. Our framework of utility calibration is motivated by these very challenges; we focus on interactively measurable utility classes to ensure our metrics are scalable and provide reliable assessments. We will clarify these points in the revised manuscript.

Response to W3, in particular W3.b & W3.c Empirical evidence and "Application-Centric" Nature

We thank the reviewer for their question, which touches on an important nuance of our work. We would like to clarify that utility calibration does not guarantee a model will achieve higher utility. Instead, it guarantees that a user's assessment of their expected utility is reliable and not systematically biased.

This is very much in the spirit of calibration itself. Standard calibration ensures that a model's stated probabilities are reflective of real frequencies, but it does not guarantee high accuracy. Similarly, utility calibration ensures that a model's predicted expected utility is trustworthy, but does not guarantee the utility itself will be high. A poorly performing classifier can be utility-calibrated if its low expected utility predictions accurately reflect the low utility that is actually realized.

The key benefit is preventing a user from being misled by overly optimistic (or pessimistic) forecasts about their strategy's performance. This provides a "what you see is what you get" guarantee. This reliability is the core of our "application-centric" claim.

Further, it is useful to clarify what we mean by application centric: indeed, we do not directly incorporate real-life applications, (that would require domain experts to choose the utility functions). But we show how our approach naturally incorporates any choice of utilities, and detail several such choices in Sec 3.3. Therein, we briefly discuss how some utility class can be relevant for particular domains. Figure 1 exactly illustrates our purpose: depending on the application and their choices, the users may have different utility classes, e.g. rank-based or linear. So depending on the application, user will be interested in the utility calibration given by Fig1a or by 1b (resp. 1c or 1d for ImageNet). Our eCDF plots then empirically demonstrate this by showing how this reliability holds or breaks down across various methods (Dirichlet, TS, etc). We will add this important clarification to Section 4.

However, as we noticed that reviewer GWKc was also puzzled by the use of "application centric" - we can rephrase as "application-dependent'', or more systematically `"utility-aware'' (as in the title) if the reviewer feels it makes the contribution clearer.

Response to W3.a: Superiority of Utility-Based CWE and TCE

We agree with the reviewer that one cannot deduce superiority from the numerical values in Table 1 alone. The superiority of our ${UC_{TCE}}$ and $UC_{CWE}$ metrics is methodological and theoretical. Binned estimators like $\mathrm{TCE}^{\mathrm{bin}}$ are known to be unstable and sensitive to heuristic choices, particularly the number of bins (e.g. Nixon et al. [20]), with different choices leading to conflicting conclusions. Our approach is binning-free; by taking the supremum over all possible intervals, we provide a single, worst-case error value that is robust to such arbitrary choices.

To make this point more concrete, we commit to adding a new experiment to the appendix. This experiment will illustrate how the reported binned estimators for a given model varies with the number of bins and binning strategy, in contrast to our stable, binning-free metric.

Response to W4: Recalibration Algorithm

We thank the reviewer for this question. A key advantage of our framework is its direct compatibility with established, provably convergent algorithms. By framing utility calibration as a form of weighted calibration, our framework allows the adaptation of existing algorithms to improve a model's utility calibration. We provide a concrete example of this procedure in Appendix A (Algorithm 1) and will emphasize this practical aspect more prominently in main body.

Response to Minor Points: we thank the reviewer for his feedback, that we will carefully take into account.

Limitations

The reviewer rightly points out the absence of a specific limitations section. If our paper is accepted, we will add a dedicated section in the final manuscript. We plan to use the additional page granted for the camera-ready version for this purpose. This section will discuss the computational challenges of proactive measurability for rich utility classes, our reliance on sampling for the eCDF evaluation, and directions for future work.

Again, we thank you for your feedback. We remain available to answer additional questions if needed.