acceptodds
Under review as a conference paper at ICLR 2027

UCE: Uncertainty-Calibrated Evolution for Automatic Heuristic Design

Abstract

In iterative LLM-based heuristic design, evaluation scores serve not only to rank candidate implementations, but also to shape the search directions that an LLM continues to explore or abandons. However, a raw score evaluates only one implementation in isolation and can be misleading when interpreted without considering the performance of other candidates generated from the same parent. In particular, an isolated low score may cause the LLM to prematurely discard a potentially productive search direction. We introduce Uncertainty Calibrated Evolution (UCE), a stage-aware scoring paradigm that calibrates candidate evaluations according to the collective performance within each fixed-parent stage. Specifically, UCE contextualizes each candidate's score using the mean and dispersion of its stage-level candidate pool, transforming an isolated evaluation into a relative signal for subsequent selection and feedback. This design reduces the disproportionate influence of low or otherwise atypical scores on the LLM's iterative decisions, without modifying the program generator or requiring additional model training. We evaluate UCE across diverse operations-research datasets and LLM-AHD baselines. UCE improves overall performance and reduces premature acceptance and rejection in counterfactual replay, suggesting that stage-level score calibration can provide more reliable guidance for iterative heuristic search.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Automatic Heuristic Design, LLM Self-Evolution, Uncertainty Modeling

Reviews

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

This paper introduces Uncertainty Calibrated Evolution (UCE), a stage-aware scoring paradigm that calibrates candidate evaluations according to the collective performance within each fixed-parent stage. Specifically, UCE contextualizes each candidate’s score using the mean and dispersion of its stage-level candidate pool, transforming an isolated evaluation into a relative signal for subsequent selection and feedback. This design reduces the disproportionate influence of low or otherwise atypical scores on the LLM’s iterative decisions, without modifying the program generator or requiring additional model training.

Critical strengths
  1. The proposed two challenges are quite clear and well-presented.

  2. This paper is relatively well-written.

  3. The results in Table 3 are promising; the performance demonstrated on frontier models highlights the scaling ability of this approach.

Critical weaknesses
  1. As the greatest weakness, this paper is merely the same as a paper produced in 2024 [1]. Both Qube and UCE introduce uncertainty to judge the score. The author fails to compare against Qube or even discuss its existence, which is unacceptable. I require the author to provide clear comparative experiments and a discussion of related work before I will consider a higher score.

[1] Chen, Zijie, et al. "Qube: enhancing automatic heuristic design via quality-uncertainty balanced evolution." arXiv preprint arXiv:2412.20694 (2024).

  1. This paper exhibits several characteristics that fall short of standard academic research criteria: figures are provided as screenshots rather than vector graphics; experimental parameters are often vaguely defined; and instead of employing conventional constructive or ACO (Ant Colony Optimization) frameworks, the authors have opted for the OR-Tools suite.
Questions for authors
  1. Please provide a clearer description of the experimental setup for the main experiment.

  2. Which large language model (LLM) was used in the main experiment?

  3. Were the results for the main experiment obtained by averaging across multiple runs?

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

This paper proposes Uncertainty Calibrated Evolution (UCE), a stage-aware score adjustment method for LLM-based automatic heuristic design. UCE uses the mean and dispersion of candidate scores generated from a fixed parent to reduce the influence of low-scoring outcomes on subsequent selection and feedback. High-scoring candidates are further checked on an independent holdout set. Experiments across twelve operations-research tasks and several from-scratch heuristic design settings report improvements over existing AHD methods, supported by ablation studies and counterfactual replay analyses.

Critical strengths

The paper addresses an important aspect of LLM-based heuristic search by examining how evaluation outcomes influence subsequent search decisions. The proposed stage-aware adjustment is simple and potentially applicable across different evolutionary frameworks without retraining the underlying LLM. The extensive evaluation across diverse optimization tasks and LLM backbones is another strength. In particular, the counterfactual replay analysis provides useful insights into premature acceptance and rejection, extending the evaluation beyond final solution quality.

Critical weaknesses

The main methodological concern is that the proposed calibration mechanism is not sufficiently specified or justified. The weighting function (W) in Appendix B, which determines the actual score adjustment, is left abstract, and it is unclear how the holdout audit affects subsequent selection. More fundamentally, score dispersion across generated programs does not necessarily reflect uncertainty about an individual candidate's quality or future potential. The rationale for asymmetrically adjusting low scores therefore remains unclear, particularly in relation to conventional fitness scaling.

The experimental evaluation is broad, but the contribution of calibration itself is not fully isolated. Comparisons with different AHD methods do not establish whether the gains persist when UCE is added to the same underlying search procedure. Although the component ablations are useful, comparisons with simpler score-scaling strategies are missing. Several performance margins are small, while the counterfactual replay results lack uncertainty estimates. The additional evaluation costs associated with holdout auditing are also insufficiently characterized.

Questions for authors
  1. What is the explicit form of the weighting function (W) in Appendix B, and how are its parameters determined? How do the holdout audit results affect subsequent selection decisions?

  2. Under Eq. (6), nonnegative calibration weights leave the highest-scoring candidate within a stage unchanged. Which selection or retention decisions are actually affected by calibration, and how frequently do such changes occur?

  3. Since stage-level score dispersion reflects both differences in program quality and evaluation noise, what justifies using it to adjust individual candidate scores?

  4. The distribution of generated candidates may change as the LLM receives feedback within a stage. How reliable are the pooled mean and variance under this nonstationarity?

  5. Can the authors compare EoH and ReEvo with and without UCE under identical generation strategies, prompts, and evaluation budgets?

  6. How are replay continuations controlled to ensure comparable evaluations across methods? Are the reported reductions in premature acceptance and rejection robust to different replay horizons and random seeds?

  7. Given the small performance margins in some settings, can the authors report run-level variability and confidence intervals against the strongest baselines? Are the additional holdout evaluations fully accounted for in the computational budget?

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

This paper proposes Uncertainty Calibrated Evolution (UCE) for LLM-based automatic heuristic design. UCE pools raw evaluations obtained from a fixed parent, estimates their mean and dispersion, and adjusts below-mean scores before using them for selection and subsequent feedback. Above-mean candidates retain their raw scores and undergo a separate holdout audit. The evaluation covers twelve operations-research tasks, from-scratch heuristic design and transfer, multiple backbones, replay diagnostics, and component ablations.

Critical strengths
  1. The paper addresses a meaningful aspect of iterative program search: an evaluation score influences both candidate selection and subsequent LLM feedback. Contextualizing low scores using outcomes from the same parent is a plausible, training-free intervention.

  2. The empirical coverage is broad. UCE obtains the best reported results on 11 of 12 tasks in Table 1 and 7 of 9 transfer settings in Table 2. The attempt to examine selection decisions through counterfactual replay is also valuable.

Critical weaknesses
  1. The experimental weighting and audit rules require a concrete specification. Section 3.3 and Appendix B define b through W(r,z,H), but Equation (10) intentionally leaves the numerical weighting rule open. A general framework can allow such freedom; nevertheless, the particular W and parameters used to obtain the reported results are needed for reproduction and for interpreting the dispersion ablation. The paper does specify independent audit data and a generic audit step, so my concern is not the absence of a holdout set or evidence of test leakage. Rather, the agreement criterion and the way audit outcomes change search decisions are not explicit.

  2. The relationship between the reported implementation and the existing ablations remains unclear, and the main results need stronger uncertainty reporting. Algorithm 1 describes a generic integration loop, Appendix D supplies baseline settings, and Table 5 reports five-seed component ablations; these are meaningful disclosures. However, the concrete search rules behind the UCE rows in Tables 1-3 are not clearly mapped to those settings. Table 5 does not explicitly identify a complete score-correction-off control, and its mean and dispersion variants are not operationally defined, so I cannot determine whether one already serves this purpose. The main comparisons report a program selected across three searches rather than variability across independent searches, despite some small margins such as 5.804 versus 5.805 on TSP-50. Table 4 also needs the numerical replay horizon, additional-attempt budget, sampling and rate-denominator definitions, and correlation aggregation protocol to assess the strength of its mechanism evidence.

  3. The submission lacks the standard "Under review as a conference paper at ICLR 2027" header and therefore deviates from the expected anonymized submission format. We would appreciate the ACs confirming whether this affects double-blind compliance.

Questions for authors
  1. Please provide the exact function W, all its parameters, and the precise implementations of the mean and dispersion ablations. How does each term affect the scores used in the reported experiments?

  2. Sections 3 and 4 and Appendix C describe a separate holdout audit and independent final test data. What operational criterion defines train-holdout agreement, and how does an audit result affect candidate retention, parent replacement, or subsequent prompts? Algorithm 1 calls the audit but does not explicitly use its result.

  3. Algorithm 1 provides a generic search loop, Appendix D reports baseline configurations, and Table 5 includes component ablations. Please clarify the concrete generation, selection, and parent-update rules used for the UCE rows in Tables 1-3 and their relationship to Appendix D. Does any Table 5 variant completely disable score correction while retaining the same search procedure and holdout policy? If so, identify it and give its exact implementation; if not, a matched raw-score control would help isolate the correction effect. Please also report variability across independent searches for the main comparisons.

  4. Please specify the complete replay protocol and uncertainty estimates for Table 4. Please also clarify the backbone and evaluation protocol used in Figure 4 and whether its three default points correspond to the same configuration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.