acceptodds
Under review as a conference paper at ICLR 2027

Hierarchical Utility Calibration for Structured Multiclass Decisions

Abstract

In multiclass probabilistic prediction, Utility Calibration (UC), which concentrates auditing on specified utilities, has recently received attention as a way to guarantee downstream decisions while controlling computational and sample burdens. At the same time, some multiclass problems have meaningful label hierarchies that play important roles in medicine and image classification, yet it remains insufficiently understood how UC evaluates utility in a hierarchy. We show that the difference between realized utility and predicted mean utility admits an exact decomposition into a sum of contributions from the internal nodes of the label tree in the hierarchical structure. This decomposition shows that positive and negative contributions from different nodes can cancel, and that even when UC is small, the utility errors remaining in parts of the hierarchy need not be small. To address this problem, we propose Hierarchical Utility Calibration (HUC), which evaluates each node contribution before summation while retaining the same target utility, subgroup, and predicted-utility interval. We further provide a finite-sample evaluation over all predicted-utility intervals and propose HUC Boost, which updates only violated internal nodes, with theoretical guarantees.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
calibration, Hierarchical classificatoin, multicalibration, utility, uncertainty quantification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_q1SDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies utility calibration for multiclass predictions with a fixed semantic label tree. It shows that the realized-minus-predicted utility residual decomposes exactly into internal-node contributions, whose expectations can cancel under ordinary Utility Calibration (UC). Hierarchical Utility Calibration (HUC) audits these contributions separately while retaining the same target utility, subgroup and predicted-utility interval. Experiments include an eight-leaf synthetic problem and five real-data benchmarks.

Critical strengths
  1. The paper provides a clear motivation for multiclass probabilistic prediction and Utility Calibration.
  2. The proposed method appears to be technically sound.
  3. HUC has been evaluated through extensive experiments.
Critical weaknesses
  1. The core idea of HUC needs to be clearly stated in the introduction.
  2. The findings in the paper need more solid support. For example, hierarchical auditing is illustrated through two examples, but its generality needs to be further supported by some essential explanations.
  3. The experimental analysis needs more convincing explanations.
Questions for authors
  1. The paper shows that the difference between realized utility and predicted mean utility can be exactly decomposed into a sum of contributions from the internal nodes of the label tree. Hierarchical auditing serves as the foundation of the paper. However, is hierarchical auditing generally applicable in this field?
  2. HUC-BOOST is similar to UC-Boost. What are the specific advantages of HUC-BOOST over UC-Boost?
10 comments

1. Weakness 1: The core idea of HUC

Thank you for reading our paper in detail and for your careful review and constructive comments. We also appreciate your recognition of the motivation, technical soundness, and breadth of the experiments. In response to your comments, we have strengthened the presentation of HUC's core idea, the generality of hierarchical auditing, the specific advantages of HUC-Boost, and the interpretation of the experimental results. The main additions and revisions are marked in red in the revised manuscript.

Summary of the concern: The core idea of HUC needs to be stated clearly in the Introduction.

In response to this comment, we have revised the Introduction (Section 1), with the changes marked in red, to first illustrate the problem through a concrete example and then explain what HUC audits, its applicability to general trees, and the idea connecting auditing to local correction.

Discrepancies that are invisible in the final mean. Consider a simplified medical example in which we first assess whether a patient has an infection requiring treatment and, if infection is confirmed, assess whether ICU care is needed. Suppose every patient receives the same prediction: the predicted probability of infection is 80%, and the predicted conditional probability of requiring ICU care given infection is 25%, whereas the corresponding true probabilities are 40% and 50%. The predicted and true probabilities of the final event, “having an infection and requiring ICU care,” agree because 0.8×0.25=0.4×0.5=0.20.8\times0.25=0.4\times0.5=0.2. Thus, UC for the indicator utility of this event is zero over the full population. Nevertheless, the overestimation of infection probability and the underestimation of the conditional probability of requiring ICU care given infection remain (the numerical example in Section 1 and the definition of UC in Section 2.1, Eq. (4)).

For example, suppose a hypothetical treatment threshold is set at an infection probability of 60%, and the threshold for ICU care after infection is confirmed is set at a conditional probability of 40%. At both stages, the decisions based on the true probabilities differ from those based on the predictions. The predicted infection probability of 80% exceeds the 60% threshold, whereas the true probability of 40% is below it, so the model chooses treatment that would not be chosen based on the true probability. After infection is confirmed, the predicted probability of requiring ICU care is 25%, below the 40% threshold, whereas the true probability of 50% exceeds it, so the model forgoes necessary ICU care. This cancellation structure is explained by the four-leaf tree decomposition in Section 2.2 (Eq. (5)).

Such cancellation of node contributions is also observed in real data (Section 5.2); we explain the details in our response to Weakness 3 below.

Auditing with HUC and extension to general hierarchies. We propose Hierarchical Utility Calibration (HUC), which decomposes the error in a specified utility into contributions associated with the branches of the label hierarchy and audits them before summation (Section 3.1, Eqs. (9)–(13)). In the example above, for the same target utility corresponding to “having an infection and requiring ICU care,” we separately evaluate the contributions from the branch distinguishing infection from no infection and the branch within infection distinguishing whether ICU care is needed. By keeping the target utility, subgroup, and interval of predicted mean utility the same, we can identify the branches where discrepancies remain even when they cancel in the final mean. Contributions from branches that do not affect the target utility are zero, allowing the audit to focus on the parts relevant to that utility (Eqs. (8), (12)).

This decomposition and auditing apply to general finite rooted trees. In trees with three or more children per node or with different depths across branches, positive and negative contributions associated with the same utility can likewise cancel when summed (Theorem 3.1, Appendix C.2). We further establish the connection to calibration when the original utility is aggregated at different levels of granularity along the hierarchy (Appendix G, Proposition G.3), and introduce HUC-Boost to connect detected violations to correction at the corresponding branches (Section 3.2, Algorithm 1). This provides a framework for detecting utility discrepancies while retaining their locations in the hierarchy and correcting them locally.

The differences from calibrating leaves or individual branches separately are explained in Section 2.2 and Appendices D.2–D.4. We explain the mathematical substance of the decomposition and the additional guarantees in our response to Weakness 2 and Question 1 next, and the mechanism and advantages of local correction in our response to Question 2.

2. Weakness 2 and Question 1: Generality, guarantees, and applications

Summary: Why does hierarchical auditing extend beyond the two examples, and how does it apply to hierarchical decisions?

In response, we added explanations of node contributions and calibration guarantees for aggregated utilities to Section 3.1, marked in red.

A general decomposition. Under the manuscript's assumptions, Theorem 3.1 applies to any finite rooted label tree and bounded utility, including unbalanced and multiway trees. The predictor need not be trained hierarchically: subtree and conditional branch probabilities follow from positive multiclass probabilities and the tree. Appendix K presents results on real-world datasets covering various tree structures and utilities.

Let μu,v(p)\mu_{u,v}(p) be the predicted mean utility within subtree vv. For yy in child subtree vjv_j,

=\mu_{u,v_j}(p)-\mu_{u,v}(p),$$ and $d_v=0$ outside the parent subtree. These changes telescope from root to leaf to give $u(p,y)-\mu_u(p)$ (Eq. (9)): each contribution measures how refining one branch changes the evaluation of the same utility. For $P=f(X)$, Eq. (8) gives $$\mathbb{E}[d_v(p,Y)\mid P=p] =\pi_v^\star(p)\sum_j(q_{v,j}^\star(p)-q_{v,j}(p))\mu_{u,v_j}(p).$$ Here, $\pi_v^\star$ is the actual parent-subtree reach probability. When it is positive, $q_{v,j}^\star,q_{v,j}$ are actual and predicted conditional branch probabilities: their discrepancy is weighted by child-subtree mean utilities and reach probability. At zero reach, the conditional mean is zero. Equal child means also make the contribution zero. For a fixed tree and predictive distribution, Appendix C.3 establishes uniqueness and orthogonality under locality, child-subtree constancy, and zero predictive mean. **What HUC adds to UC.** The audit moment is the weighted average of the per-observation contribution $d_v$, with the same utility, subgroup $c$, and predicted-utility interval $I$ across nodes (Eq. (10)): $$\Gamma_{c,u,I,v}(f):=\mathbb{E}[c(X)\mathbf{1}\\{\mu_u(P)\in I\\}d_v(P,Y)].$$ Thus, $$\begin{aligned} \mathrm{UC}(f;\mathcal{C},\\{u\\})&=\sup_{c,I}\left|\sum_v\Gamma_{c,u,I,v}(f)\right|,\\\\ \mathrm{HUC}(f;\mathcal{C},\\{u\\})&=\sup_{c,I,v}|\Gamma_{c,u,I,v}(f)|. \end{aligned}$$ UC audits after summation; HUC audits before cancellation (Eqs. (11), (13)). To see the additional guarantee, expand an ancestor-closed set $S$ of internal nodes and stop at its boundary. Let $b_S(y)$ be the first node outside $S$ on the root-to-$y$ path. Averaging unresolved leaf utilities within that subtree gives (Lemma G.1) $$\begin{aligned} u_S(p,y)&:=\mu_{u,b_S(y)}(p),\qquad \mu_{u_S}(p)=\mu_u(p),\\\\ u_S(p,y)-\mu_u(p)&=\sum_{v\in S}d_v(p,y). \end{aligned}$$ These residuals are partial sums, and the unchanged predicted mean allows comparison on **the same subgroup and predicted-utility interval**. In the Weakness 1 example, the root contributes $-0.1$ on average; the node within infection adds $+0.1$, making the final residual zero. Expanding one boundary node adds exactly its contribution, measuring consistency between successive utility evaluations on the same audit population. A small final sum need not imply small partial sums. For every fixed tree boundary, Proposition G.3 gives $$\mathrm{UC}(f;\mathcal{C},\\{u_S\\}) \le |S\cap\mathcal{V}_{\mathcal{T}}(u)|\\,\mathrm{HUC}(f;\mathcal{C},\\{u\\}),$$ where $\mathcal{V}_{\mathcal{T}}(u)$ contains utility-relevant internal nodes. HUC therefore controls calibration of the original utility aggregated at different hierarchical granularities. This concerns the specified aggregated utilities; other decisions require their own utilities. **Concrete applicability.** Utilities can evaluate correctness of final-class, internal-node, or node-set outputs, tree-distance losses, and prediction specificity. For an output rule $a(p)$ and loss $0\le L(a,y)\le L_{\max}$, $L_{\max} > 0$, $$u_a(p,y)=1-\frac{2L(a(p),y)}{L_{\max}}$$ allows auditing the model's expected utility for that decision. Appendix A.1 covers linear, rank-based, and decision-derived utilities; Appendices J and K include correctness, threshold decisions, abstention, and specificity across different trees. Appendix I, added in red, connects these choices to the hierarchical losses of Ramaswamy et al. (2015) and Cao et al. (2024), the metric-dependent output rules of Plaud et al. (2025), and the hierarchical correctness utility and confidence calibration conditions of Goren et al. (2024). Our response to Question 2 explains how the same audit moment also gives a direction for local correction.

3. Question 2: Specific advantages of HUC-Boost over UC-Boost

Summary of the question: HUC-Boost resembles UC-Boost, but what specific advantages does it offer?

Connecting the same audit quantity to correction at the corresponding branch

HUC-Boost can individually detect contributions that cancel in the sum and correct their corresponding branches. Both methods use the same utility and subgroup classes, but UC-Boost audits only the summed residual; canceled contributions do not trigger an update under those conditions.

The audit moment in our response to Weakness 2 and Question 1 provides a correction direction. Fix the direction defined by the current prediction,

hv(x)=c(x)1μu(f(x))∈IΔu,v(f(x)),\boldsymbol{h}_v(x)=c(x)\mathbf{1}\\{\mu_u(f(x))\in I\\}\boldsymbol{\Delta}_{u,v}(f(x)),

and let fαf_\alpha be the predictor obtained by updating only the logits of the corresponding node as zv↦zv+αhv\boldsymbol{z}_v\mapsto\boldsymbol{z}_v+\alpha\boldsymbol{h}_v. Then

=-\Gamma_{c,u,I,v}(f)$$ holds (Appendix E.2). Adjusting branch probabilities according to this moment's sign gives a descent direction for log loss. HUC-Boost updates when the absolute value of the audit moment $\Gamma_{c,u,I,v}(f)$ exceeds the prescribed threshold. This update preserves the parent subtree's total probability, each child subtree's conditional distribution, and leaf probabilities outside the subtree. With the prescribed step size and stopping threshold and finite initial population log loss, Theorem 3.5 and Appendix E.2 guarantee loss decrease and finite termination. Thus, **a single node contribution connects discrepancy localization, calibration guarantees at each granularity, and corresponding local correction**. These are HUC-Boost's additional guarantees and mechanism; empirical gains depend on the base predictor and initialization. Our response to Weakness 3 presents real-data cancellation and observed improvements. **Finite-sample guarantees with adaptive step sizes** We derive the adaptive step size $\alpha_t=\Gamma_t/\Lambda_t$ from the audit moment $\Gamma_t$ and a curvature upper bound $\Lambda_t$ along the update direction (Appendix E.2). The empirical step also uses the calibration sample, so repeated auditing and updating require control of sample dependence. Appendix H.7, added in red, analyzes independent multiplicative perturbations of the empirical step: $$\alpha_t=\Xi_t\\,\frac{\widehat\Gamma_t}{\widehat\Lambda_t}, \qquad \Xi_t\sim\operatorname{Unif}[1-\rho,1+\rho],\quad 0 < \rho < 1.$$ For an initial predictor independent of the calibration sample, under the manuscript's assumptions, we provide **a finite-sample population HUC guarantee at termination of adaptive HUC-Boost despite repeated sample reuse** (Theorem H.17), beyond empirical loss decrease and termination. **Guarantees for two-stage correction using the same sample** The first-stage parametric recalibrator and second-stage HUC-Boost can use the same calibration sample. By adding a small independent perturbation to the learned initial parameters to control sample dependence, we guarantee population HUC at termination of the two-stage method with a fixed step size, under the prescribed assumptions and sample-size conditions (Appendix H.2, Theorem H.5). We also provide a guarantee at termination for a two-stage method that additionally uses multiplicative perturbations of the adaptive step size (Appendix H.7, Corollary H.19). This two-stage analysis also applies to the corresponding UC-Boost via a star tree with all classes directly below the root. Thus, the analysis of sample reuse is a theoretical contribution applicable to both methods, whereas **the distinction specific to HUC-Boost is that it audits and corrects contributions within the hierarchy and obtains guarantees for those contributions**. For validation-based selection in the experiments, we added in red a population HUC guarantee relative to the best candidate within the selected path, under the prescribed candidate family, when selection uses HUC on an independent validation sample (Appendix H.8, Theorem H.23). For the perturbed method reaching natural termination under the prescribed sample-size conditions, this connects to an absolute HUC guarantee (Corollary H.24). With computational-budget truncation, the guarantee is the within-path comparison. **Fewer updates with curvature-based adaptive steps.** In response to Reviewer 2's request, we compared adaptive HUC-Boost, randomized adaptive HUC-Boost (RHUC), and fixed-step HUC-Boost (FHUC). In two-stage comparisons across many datasets, these methods achieved similar mean test HUC, while adaptive HUC-Boost and RHUC required substantially fewer updates than FHUC (Section 5.2 and Appendix K.9). These results support the benefit of curvature-based steps in achieving comparable performance with fewer updates.
Reviewer_1nyxOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies utility calibration for multiclass predictions with a fixed label hierarchy. It derives an exact decomposition of utility residuals into internal-node contributions, showing how aggregate calibration can conceal cancellation across nodes. It introduces Hierarchical Utility Calibration (HUC), which audits these contributions under shared subgroup and predicted-utility conditions, and HUC-Boost, which corrects individual branches. Theoretical results include uniform finite-sample estimation bounds, population loss-decrease and termination guarantees, and generalization guarantees for a fixed-step variant. Validation comprises controlled synthetic experiments and five real datasets, comparing against UC-Boost and standard recalibration methods.

Critical strengths
  1. A precise and interpretable calibration target.

The decomposition identifies where utility discrepancies arise while preserving the target utility, subgroup, and predicted-utility interval. This makes the cancellation issue concrete and distinguishes HUC from independently calibrating branch probabilities. The guarantees for aggregated utilities at fixed tree boundaries further establish that the criterion controls meaningful quantities beyond the final aggregate residual.

  1. A principled connection between auditing and correction.

HUC-Boost’s node-wise updates preserve valid probabilities and the conditional distributions within child subtrees. Connecting the audited violation to a descent direction for global log loss yields population loss-decrease and finite-termination guarantees. Together with uniform auditing bounds, this provides a coherent mathematical foundation for the proposed procedure.

Critical weaknesses
  1. The incremental empirical benefit over UC-Boost is mixed and incompletely isolated.

Although several two-stage configurations perform better, the reported tables lack corresponding parametric-calibration -> UC-Boost comparisons, despite their mention in the introduction. These omissions make it difficult to attribute the stronger results specifically to hierarchical correction.

  1. The finite-sample correction guarantees do not cover the main experimental procedure.

Appendix H analyzes a prescribed fixed-step schedule, whereas the primary experiments use the adaptive empirical ratio and return validation-selected checkpoints.

Questions for authors
  1. Where are the parametric-calibration -> UC-Boost comparisons mentioned in the introduction? Could you provide or identify comparisons against the corresponding HUC-Boost combinations using identical initializers and validation criteria?

  2. What guarantee applies to the adaptive, validation-selected predictor actually reported? Do the empirical conclusions persist under the fixed-step schedule?

5 comments

Question 1 / Weakness 1: Two-stage comparisons and the contribution of hierarchical correction

Concern. Can the missing parametric-calibration + UC comparisons be added, and can hierarchical correction be isolated using identical initial predictions and validation criteria?

Added comparisons. We apologize for the incomplete comparison of two-stage UC and HUC in the submission. We will add comparisons of temperature scaling, vector scaling, and Dirichlet calibration followed by UC-Boost alongside their HUC-Boost counterparts, together with standalone parametric calibration and direct UC/HUC correction. (Update: These experiments have now been completed, and we report the results below.)

Findings and the remaining controlled comparison. We will examine when additional correction helps, when the first stage leaves little room for improvement, and how the gains depend on the base predictor and initializer.

Comparisons sharing both the fitted initializer and validation criterion are underway; we will report them and revise the Results accordingly once completed. (Update: These experiments have now been completed, and we report the results below.)

Motivation and theory for two-stage correction. We introduced parametric initialization to reduce the number of subsequent HUC-Boost corrections. The original UC paper does not provide a systematic comparison of this specific composition or analyze reuse of the same calibration sample across both stages. We therefore also investigate the corresponding two-stage UC procedure.

Learning the initializer and correcting it on the same sample introduces dependence that an independent-initializer guarantee does not cover. Appendix H addresses this dependence through independent perturbations of the fitted initial parameters, under explicit assumptions. Corollary H.19 extends the analysis to randomized adaptive steps, with contributions from both initializer and step perturbations. The analysis also applies to our logit-based UC-Boost: on a star tree, with every class attached directly to the root, both the HUC criterion and update reduce to their UC counterparts, under the same assumptions and corresponding step rules.

What HUC contributes. Our central contribution is the decomposition, assessment, and correction of hierarchical utility errors. Positive and negative node contributions can cancel in UC; small aggregate UC therefore need not imply small node contributions. HUC-Boost corrects these node-level violations. Similar final scores in some experiments do not remove this distinction in the target or guarantee.

We now highlight the theoretical contributions in red in the Introduction: Contribution 2 describes curvature-based adaptive updates and their randomized finite-sample population HUC guarantee; Contribution 3 describes the two-stage guarantee under calibration-sample reuse. To our knowledge, these are the first guarantees for these specific HUC procedures under the stated perturbation assumptions. The two-stage analysis and systematic comparison support the central contribution above.

Question 2 / Weakness 2: Adaptive steps, validation selection, and fixed-step experiments

Concern. What guarantees cover adaptive steps and validation-selected checkpoints, and do the empirical conclusions persist with fixed steps?

Adaptive steps and sample reuse. We agree that the submitted fixed-step analysis did not adequately explain the guarantees for the empirical adaptive steps and validation-selected outputs used in the main experiments. We have added these analyses in Appendices H.7 and H.8, respectively.

The usual adaptive step already ensures empirical log-loss decrease and finite termination. However, computing its data-dependent magnitude also adaptively reuses the calibration sample, so the existing fixed-step generalization analysis does not apply directly. To control this dependence in our finite-sample analysis, we retain the update direction and audit selection and add small independent multiplicative perturbations:

\alpha_t=\Xi_t\frac{\widehat\Gamma_t}{\widehat\Lambda_t}, \qquad 0<\rho<1.$$ **Finite-sample population guarantee.** Each update decreases empirical log loss by at least $(1-\rho^2)\widehat\Gamma_t^2/(2\widehat\Lambda_t)$. If $D_{\mathrm{fix}}$ bounds the initial empirical log loss and $\tau$ is the audit stopping threshold, the number of updates is at most $$T_{\tau,\rho} =\left\lceil\frac{2D_{\mathrm{fix}}}{(1-\rho^2)\tau^2}\right\rceil.$$ Dominating the randomized step-path distribution by a sample-independent reference distribution then yields a high-probability population HUC guarantee at natural stopping, under the stated sample-size conditions (Theorem H.17). For fixed $0<\rho\le1/3$, the sufficient sample size scales as $\widetilde O(\varepsilon^{-4})$ in accuracy, holding other quantities fixed (Corollary H.18). This matches the accuracy dependence of the fixed-step guarantee in Theorem H.2, up to logarithmic factors. Corollary H.19 covers the learned, same-sample initializer as described above. The contribution is a finite-sample analysis of this continuous, empirical-ratio HUC update with multiplicative randomization and sample reuse. **Validation selection.** For saved predictors $f_0,\ldots,f_T$ constructed independently of the validation sample, selecting $f_{\widehat t}$ by minimum validation HUC gives, with probability at least $1-\delta$, $$\operatorname{HUC}(f_{\widehat t}) \le \min_{0\le t\le T}\operatorname{HUC}(f_t) +2r_{\mathrm{val}}(T,\delta),$$ $$r_{\mathrm{val}}(T,\delta) =\frac{16}{\sqrt{n_{\mathrm{val}}}} +4\sqrt{\frac{\log\\{\max(1,N_{\mathrm{cand}})(T+1)/\delta\\}} {2n_{\mathrm{val}}}}.$$ Here $n_{\mathrm{val}}$ is the validation sample size and $N_{\mathrm{cand}}$ is the audit candidate count defined in the paper (Theorem H.23). This oracle guarantee also applies to ordinary adaptive steps and to the saved HUC checkpoints: the initial predictor, completed-sweep endpoints, and final predictor. Because validation also selects regularization, we explicitly cover all saved predictors from the prespecified regularization and subgroup configurations, rather than treating only the selected path as independent of validation. For $M$ such predictors and the union of the prespecified audit candidates, uniform control has a $\log M$ dependence. The comparator remains the best checkpoint within the selected path. Under the sufficient sample-size and natural-stopping conditions, this combines with the randomized procedure's population HUC guarantee (Corollary H.24). **Randomized and fixed-step experiments with common validation criteria.** In response to your comment, we added fixed-step HUC-Boost and randomized adaptive HUC-Boost to the experimental comparisons under the same settings as UC-Boost and HUC-Boost. We also evaluated both common validation criteria: selecting checkpoints by validation NLL for all correction methods, and selecting them by validation HUC for all correction methods. These results are reported in Table 2 of the main paper and Appendix K. For details of these experiments, please refer to our reply below reporting the experimental results.

Follow-up to Weakness 1 / Question 1 and Weakness 2 / Question 2:

Comparisons with Shared Initial Predictions and Validation Criteria

We have completed the comparisons with shared initial predictions and common validation criteria that we described as ongoing in our previous response. We have also included the additional fixed-step two-stage experiments and incorporated the results and their interpretation into the revised manuscript.

Comparisons with shared initial predictions and common validation criteria

For direct correction, all methods start from the predictions of the same fitted base model. For two-stage correction, we share the fitted temperature scaling, vector scaling, or Dirichlet calibration model and apply UC-Boost, adaptive HUC-Boost, the randomized adaptive HUC-Boost described in our previous response (RHUC), and fixed-step HUC-Boost (FHUC) to exactly the same outputs. RHUC uses ρ = 0.1, and FHUC uses a fixed step magnitude of 0.05.

We conducted these comparisons on five datasets: iNaturalist, SUPPORT2, MASSIVE, NSL-KDD, and N-BaIoT. Within each dataset, the methods use the same utility class and subgroups. For checkpoint selection, we evaluated both common validation NLL and common validation HUC across all correction methods. This enables a unified comparison of all the settings you requested using shared initial predictions and common validation criteria.

The comparison protocol is described in Appendix K.1. For iNaturalist and SUPPORT2, the NLL-selected results appear in Table 2 of the main text, and the HUC-selected results appear in Table 8 of Appendix K.9. For the remaining three datasets, Tables 9–11 in Appendix K.9 present the results under NLL and HUC selection side by side.

These experiments also yielded the following new findings.

Findings from comparisons with two-stage UC

Even when UC-Boost receives the same parametric initialization, we observe a tendency for HUC-Boost to achieve lower mean test HUC in some settings on each of the five datasets. For example, under common NLL selection, HUC-Boost following temperature or vector scaling achieves lower mean test HUC than the corresponding two-stage UC-Boost on both iNaturalist and SUPPORT2.

Comparisons of adaptive, randomized, and fixed steps

Adaptive HUC-Boost and RHUC perform similarly in many settings. With parametric initialization, FHUC also achieves mean test HUC close to these methods in many settings. These results show that fixed-step correction can achieve performance close to adaptive correction when applied after suitable initialization. However, even in the two-stage setting, FHUC required more update steps than adaptive HUC-Boost on many datasets. This provides empirical evidence for the benefit of adaptive step sizes in achieving comparable performance with fewer updates.

We have incorporated these results and their interpretation into Section 5.2 and Appendix K.9, and the shared experimental protocol into Appendix K.1.

In addition, in response to a question from another reviewer, we quantitatively evaluated how much cancellation occurs among the internal-node residual contributions aggregated by UC (Eq. (11)), which motivates our study. On iNaturalist and SUPPORT2, we compared cancellation rates before correction and after UC-Boost. The summary appears in Table 1 of the main text, and the evaluation procedure and per-utility results are provided in Appendix K.8, Tables 6–7. We would appreciate your consideration of these results as well.

Reviewer_wBJTOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this work, the authors focus on probability calibration for multiclass classification with label hierarchies. They show that the canonical utility calibration that operates on the flat label hierarchy may overlook errors at individual nodes when labels possess tree hierarchies, since contributions from different nodes can offset each other in the overall utility residual. The authors then propose hierarchical utility calibration based on a tree decomposition of this residual. HUC evaluates the node contributions separately under the same target utility, allowing utility errors to propagate within the hierarchy. A finite-sample evaluation bound and a post-hoc correction method are further provided. Theoretical guarantees on the decrease of log-loss and finite termination is also provided. Experiments on synthetic and real-world datasets show the effectiveness of this method.

Critical strengths
  1. Compared with UC that ignores the label hierarchy in the calibration process, the integration of label hierarchies into utility calibration in HUC may lead to a probability that better aligns with the label hierarchy.

  2. The theoretical analysis is provided for both the evaluation of HUC and the proposed correction method. The evaluation bound holds over all predicted-utility intervals, and guarantees on the decrease of population log-loss and finite termination are further established for HUC-Boost.

  3. The synthetic experiment directly shows how UC may overlook errors when contributions from different nodes offset each other. Experiments on real-world datasets further compare the proposed method with UC-Boost and several typical recalibration methods.

Critical weaknesses
  1. The title uses “structured multiclass decisions”, which may cause confusion with structured prediction [1,2]. Since this term is not used much in the main text, I suggest removing “structured” from the title or explaining its meaning in a footnote.

  2. There are also works that generalize multiclass classification by incorporating the label hierarchy into the evaluation metric [3,4]. I think the related work could include more discussion of this topic.

[1] Anton Osokin, Francis Bach, and Simon Lacoste-Julien. On Structured Prediction Theory with Calibrated Convex Surrogate Losses. NIPS, 2017.

[2] Mathieu Blondel. Structured Prediction with Projection Oracles. NeurIPS, 2019.

[3] Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Convex Calibrated Surrogates for Hierarchical Classification. ICML, 2015.

[4] Yuzhou Cao, Lei Feng, and Bo An. Consistent Hierarchical Classification with A Generalized Metric. AISTATS, 2024.

Questions for authors

Please see the weaknesses.

3 comments

Thank you for your careful review and positive assessment of the paper's contributions. We also appreciate your specific suggestions on the title and related work.

Weakness 1. Could the title be revised to avoid confusion with structured prediction?

We agree that the original title could suggest a broader scope than the paper addresses. We study utility calibration for probabilistic multiclass predictions over the leaves of a given label hierarchy. We use this hierarchy to identify how different branches contribute to the error in a predicted utility. More general structured prediction tasks, such as predicting sequences or graphs, are outside the scope of this paper.

To make this scope clear, we removed "Structured" from the title. The revised title is Hierarchical Utility Calibration for Multiclass Decisions.

Weakness 2. How does HUC relate to prior work on hierarchical classification?

We agree that the original discussion of hierarchical classification was too brief. We expanded Appendix I.1, with the additions marked in red, to discuss the two papers you suggested and two additional studies. For each paper, we explain how its hierarchy setting relates to ours and how its calibration or consistency guarantees relate to HUC. We summarize the additions below.

  • Ramaswamy et al. (2015) allow both leaves and internal nodes as true labels and predictions, and use weighted tree distance as the classification loss. Our framework can represent internal-node outcomes by adding terminal leaves and retaining the original loss. Their surrogate calibration concerns consistency for the classification loss. HUC evaluates each node's contribution to the residual of a specified utility.
  • Cao et al. (2024) also allow any tree node as a true label or prediction and extend the tree-distance loss with a penalty based on the predicted node's depth. The same encoding accommodates their hierarchy setting. Their generalized loss can be represented by a bounded utility, allowing us to assess utility calibration for the loss for which they establish consistency.
  • Plaud et al. (2025) study optimal decoding for hierarchical evaluation metrics when true labels are leaves and predictions can be leaves, internal nodes, or sets of nodes. Their leaf-outcome setting matches ours, and their decoding rules and losses can be incorporated into our target utilities. Under our assumption of positive leaf probabilities, using the true conditional label distribution from their optimal-decoding analysis as the forecast yields zero HUC.
  • Goren et al. (2024) study hierarchical selective classification with leaf outcomes and allow predictions to retreat to ancestor nodes when uncertain. For a fixed output rule, we use the indicator that the true leaf lies in the returned node's subtree as the target utility. Its predicted mean is the reported node confidence. When this utility is audited over the full population and all intervals of reported confidence, zero HUC implies population confidence calibration. The converse can fail when node contributions cancel.

Dear Reviewer wBJT,

As we have not yet received any feedback on our rebuttal, we would like to kindly follow up. With just over two days remaining in the rebuttal and discussion period, we would greatly appreciate it if you could let us know whether our responses have sufficiently addressed your concerns. If any points remain unclear or unresolved, we would be happy to provide further clarification before the period closes.

Best regards,

Dear Reviewer wBJT,

We apologize for following up once more. With approximately 24 hours remaining in the rebuttal and discussion period, we would be grateful if you could let us know whether our response has addressed your main concerns.

If any point still needs clarification, even a brief note would help us address it before the discussion closes.

Thank you again for your time and consideration.

Best regards, The Authors

Comments on the paper

2 comments

Dear Reviewers,

Thank you for your careful reviews and constructive feedback. We will address your questions and comments individually in the corresponding review threads.

We have revised the manuscript in response to your feedback and submitted the revised version. We use red text in the revised manuscript to highlight revisions and additions for ease of review. If this use of color raises any formatting concerns, please let us know, and we will adjust the formatting accordingly.

As the rebuttal period ends today, we would greatly appreciate it if you could kindly re-assess our paper, as we believe our clarifications, responses, and revised manuscript (shown in red and blue) have addressed your concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.