acceptodds
Under review as a conference paper at ICLR 2027

Beyond Surrogate Accuracy: Decision-Aligned Learning for Budgeted Exact Verification

Abstract

Many optimization pipelines can cheaply score far more candidates than they can exactly verify, so the scorer effectively allocates a scarce exact-evaluation budget. We formalize this setting as bounded exact-verification retrieval: rank a fixed pool, verify candidates, and return the best verified utility. We show a sharp prediction–decision separation: as the pool grows while remains small, normalized value error and pairwise ranking error can vanish while verification regret remains maximal. A layer-cake representation expresses regret through quality thresholds missed by the verified set; bounding each miss through predicted mass on the corresponding quality set yields decision-aligned regret envelopes and the smooth QualityHit loss. Decomposing QualityHit across thresholds shows how budget reweights competing objectives: all budgets share the same realizable zero-loss limit, while under finite capacity the restricted optimum can shift, with constructive ranking reversals across budgets. Across FJSP, CVRP, and TSP, QualityHit improves verification quality in point estimates across all tested family–budget settings, with graded utility explaining most of the gain and budget adaptation providing a smaller additional effect. These results shift surrogate learning from global predictive accuracy toward the decisions exposed to scarce exact evaluation.

Primary area:
optimization
Keywords:
combinatorial optimization, surrogate models, bounded verification, decision-focused learning

Reviews

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

This paper studies how to select a high-quality candidate under a limited budget for exact evaluation. The proposed QualityHit loss trains a scoring model using sets of candidates that meet different utility thresholds. At deployment, the model ranks the candidates, the highest-scoring candidates are evaluated exactly, and the best evaluated candidate is returned. Experiments on scheduling and routing tasks report improvements over regression and ranking baselines.

Critical strengths

The problem is natural, and the loss offers a simple way to align training with the quality of the final selection. The experiments compare several baseline families using the same model architecture and training budget. The consistently positive mean gains across tasks and budgets provide initial evidence that the loss can improve candidate selection.

Critical weaknesses
  1. The experimental data and task settings are insufficiently specified. Key details about instance sources, problem sizes, candidate generation, and input features are missing. The supplementary material also lacks the generators and exact evaluation procedures used in the reported experiments. These omissions prevent readers from reconstructing the test settings and assessing their difficulty and representativeness.

  2. The practical value of the reported improvements remains unclear. The experiments use controlled candidate pools without establishing how these pools reflect the data, constraints, and evaluation costs of real applications. For a contribution centered on a simple loss design, evidence from practically meaningful tasks is essential. Improvements on pools whose sources and construction are unclear do not adequately establish the method’s value for practical candidate screening.

The presentation also needs substantial improvement. The appendix repeatedly precedes short proofs of elementary facts with overviews that repeat the same reasoning. The normalization described for Figure 2 does not match the plotted quantities, and Figure 3 does not clearly define the comparison shown in panel (a). These issues seriously hinder interpretation of the experimental results. Using AI tools to assist with writing does not lessen the authors’ responsibility for the clarity and accuracy of the manuscript. The authors should thoroughly check the text, figures, and captions so that readers can understand the results without guessing or filling in missing explanations.

I see value in this simple loss design. Even modest gains on an important task using real data could constitute a worthwhile contribution. At present, the data description and experimental evidence are insufficient to establish that value. I would consider raising my recommendation to weak acceptance if the authors clarify the experimental settings and provide compelling evidence of practical benefits.

Questions for authors

Which datasets or generation procedures supply the instances for each task family? Please specify the problem sizes, candidate construction, input features, and exact evaluation procedures, and provide the corresponding materials.

What evidence demonstrates that the method improves performance on datasets from meaningful real applications? Please clarify the practical gains over appropriate baselines and the cost of exact evaluation in these settings.

Reviewer_yTVwOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

In the paper’s setting, a learned scorer ranks a fixed pool of candidates and only the top B get an exact and expensive evaluation. The system finally keeps the best one it verified. The paper shows that low full-pool value error and low pairwise ranking error do not guarantee low verification regret (Prop. 1). It writes regret as an integral of missed quality thresholds and derives a chain of upper bounds: R_B ≤ U_top ≤ L_hit (Thm. 2). It trains with the smooth bound L_hit (QualityHit) and studies how the budget B changes its weights (Prop. 7, Thm. 10, Props. 12-13). It finally reports gains over listwise, regression, LambdaRank@B and two top-k-aware baselines on FJSP, CVRP and TSP at B ∈ {4, 8}.

Critical strengths

The problem is useful and fits a real class of applications. Rewriting non-additive top-BB maximum-utility regret as an integral over nested utility-threshold set-miss events and bounding it via a sharp missed-set probability cap yields a O(n)O(n) closed-form surrogate loss (Lhit(B)\mathcal{L}_{\text{hit}}^{(B)}).

Critical weaknesses
  • The paper leaves out closely related work, and its novelty is overstated as a result.

    • Recall@k in metric learning is exactly the event "the top-k contains at least one positive." Patel et al. (CVPR 2022) built a smooth surrogate for it. The graded version here is a layer-cake integral of Recall@k over thresholds.
    • Best-of-N and pass@k-aware training for LLMs (e.g. Chow et al. 2024; pass@k policy optimization, 2025) optimize max-over-k objectives directly.
    • Batch Bayesian optimization and ranking-and-selection. Choosing q points from a discrete pool to maximize expected maximum utility is exactly this one-shot problem; screening procedures for large numbers of alternatives (e.g. Nelson et al. 2001) are also relevant. Calling Bayesian optimization "sequential" (Sec. 2) skips this.
    • The top-B restriction itself. The best set for expected maximum utility is generally not the top B of any single per-candidate score, because correlated candidates make diversity matter. The paper should acknowledge this limit of its decision rule.
  • The empirical evidence is thin and under-specified.

    • The tasks are never described. Neither the main text nor the appendix says what the candidate generators, cheap features, fallback b(x), utility V or "exact decoding" are for FJSP, CVRP or TSP. Nor does it give typical pool sizes. Without these, the results can't be interpreted or reproduced.
    • The effect sizes are small. QualityHit closes 2–6% of the remaining oracle headroom on FJSP and TSP. On TSP, all four confidence intervals against the top-k-aware baselines include zero (Table 4).
    • Two budgets cannot support claims about how results depend on B. A sweep over B (1 to 32) and over pool size n would test the theory far better.
  • The abstract's attribution of the gains contradicts Table 2. The abstract says graded utility explains "most of the gain," with budget adaptation "a smaller additional effect." In Table 2, removing the normalizer hurts more than switching to equal intervals in 5 of 6 cells: FJSP .253 vs .188 and .265 vs .217; CVRP@8 .0121 vs .0083; TSP .0018 vs .0015 and .0022 vs .0018. CVRP@4 is the only exception. Also, the Conclusion and Appendix B already say the normalizer results "do not justify a clean causal story." The abstract should match that.

  • The writing of the paper needs substantial improvement.

Questions for authors
  • What are the absolute oracle a* and baseline BestGain for each family, and what units is BestGain in?
  • What is the seed-to-seed standard deviation of each method's BestGain?
  • How does QualityHit perform at B=1 and at large B? At B=1 it should reduce to a weighted multi-positive log loss.
Reviewer_E6WjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces QualityHit, a ranking method designed to select the most promising candidates when only a limited number can be verified. It shows that accurate score predictions do not always lead to better candidate selection. Experiments on scheduling and routing tasks demonstrate improvements over existing ranking methods, although the evaluation is limited to a few tasks and verification budgets.

Critical strengths
  • The paper highlights an important gap between accurate score prediction and selecting the best candidates under a limited verification budget.

  • The proposed QualityHit objective is supported by theoretical regret bounds and experiments showing improvements over several ranking baselines.

Critical weaknesses
  • The proposed objective is closely related to existing learning-to-rank approaches, and its advantages over established ranking losses are not sufficiently distinguished.
  • Experiments cover only three optimization tasks and two verification budgets (B=4,8). Evaluation on standard learning-to-rank benchmarks and a wider range of budgets is missing.
  • Although the paper derives regret bounds, it does not empirically assess their tightness or demonstrate whether optimizing the tighter theoretical bound improves performance.
Questions for authors
  • Can the authors evaluate QualityHit on established learning-to-rank datasets, such as MSLR-WEB10K, MSLR-WEB30K, and Yahoo LTR, to demonstrate its effectiveness beyond scheduling and routing problems?

  • Can the authors extend the experiments to a wider range of verification budgets (e.g., B=1,2,16,32B=1, 2, 16, 32) and compare budget-specific training against a fixed-budget objective to better establish the importance of budget awareness?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.