CVaR-RMD: CVaR Selection Pressure for Robust Metaheuristic Discovery

Ruodai Cui; Li Niu

cs.AIOct 19, 2026

CVaR-RMD: CVaR Selection Pressure for Robust Metaheuristic Discovery

Authors: Ruodai Cui, Li Niu

Organizations: Qualcomm Technologies, Inc. · The Hong Kong Polytechnic University · Department of Computer Science and Engineering, MoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University

Abstract

Large language models have recently been used to discover heuristics through iterative program search, offering a promising approach to automated algorithm design. However, candidates selected by average performance may degrade across instance families, random seeds, and problem scales because mean-based objectives can obscure rare but severe failures. We propose CVaR-RMD, a risk-sensitive evolutionary framework that uses an LLM to mutate executable heuristic programs and ranks candidates by empirical conditional value-at-risk over heterogeneous evaluation conditions. Across three combinatorial optimization domains, CVaR-based selection improves upper-tail performance and reduces failure rates while maintaining competitive mean performance. These gains persist on larger unseen instances and independently curated within-domain benchmarks

Figures & tables

Figure 1: Motivation for CVaR-RMD. Mean-based fitness in LLM-driven metaheuristic discovery rewards strong average performance while tolerating severe failures on rare instances or seeds. CVaR shifts selection pressure toward worst-quantile behavior, discouraging heuristics that depend on favorable evaluation conditions.

Figure 2: Architecture of the CVaR-guided program search method. Notations are defined in Sec. 3 .

Method	Bin Packing		CVRP		Flow-Shop
	Mean $\downarrow$	CVaR 0.90 $\downarrow$	Mean $\downarrow$	CVaR 0.90 $\downarrow$	Mean $\downarrow$	CVaR 0.90 $\downarrow$
Handcrafted heuristic	$7.41{\pm}0.08$	$11.79{\pm}0.24$	$8.12{\pm}0.10$	$12.96{\pm}0.27$	$6.76{\pm}0.09$	$10.84{\pm}0.21$
Direct LLM sampling	$7.03{\pm}0.13$	$11.18{\pm}0.31$	$7.80{\pm}0.15$	$12.47{\pm}0.35$	$6.49{\pm}0.11$	$10.29{\pm}0.28$
FunSearch-style	$6.66{\pm}0.09$	$10.51{\pm}0.23$	$7.37{\pm}0.11$	$11.62{\pm}0.26$	$6.16{\pm}0.08$	$9.78{\pm}0.21$
EoH-style	$6.42{\pm}0.06$	$10.03{\pm}0.18$	$7.18{\pm}0.08$	$11.21{\pm}0.21$	$5.99{\pm}0.05$	$9.39{\pm}0.16$
Mean-RMD	$6.56{\pm}0.06$	$9.88{\pm}0.15$	$7.20{\pm}0.06$	$11.04{\pm}0.17$	$5.95{\pm}0.04$	$9.26{\pm}0.13$

Table 1: Held-out performance across

15

discovery seeds. Values are mean

\pm

standard deviation. Lower is better.

Method	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Max loss $\downarrow$	Failure rate (%) $\downarrow$
Mean-RMD	$7.59{\pm}0.08$	$12.61{\pm}0.24$	$18.34{\pm}0.51$	$3.5{\pm}0.5$
CVaR-RMD	$7.48{\pm}0.06$	$11.63{\pm}0.18$	$16.61{\pm}0.42$	$2.0{\pm}0.3$

Table 2: Transfer evaluation on larger held-out instances across

15

discovery seeds.

Setting	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Failure rate (%) $\downarrow$
Batch size $32$	$6.50{\pm}0.06$	$9.91{\pm}0.17$	$2.0{\pm}0.3$
Batch size $64$	$6.45{\pm}0.04$	$9.50{\pm}0.11$	$1.4{\pm}0.2$
Batch size $128$	$6.43{\pm}0.04$	$9.42{\pm}0.10$	$1.3{\pm}0.2$
Failure penalty $\ell_{\mathrm{fail}}=20$	$6.44{\pm}0.05$	$9.63{\pm}0.13$	$1.7{\pm}0.3$
Failure penalty $\ell_{\mathrm{fail}}=30$	$6.47{\pm}0.05$	$9.51{\pm}0.12$	$1.3{\pm}0.2$

Table 3: Sensitivity analysis across tasks using

15

discovery seeds.

Panel of Figure 3 — Figure 3: Sensitivity analysis across tasks using $15$ discovery seeds. Error bars denote standard deviations; filled markers indicate the best value for each metric, including tied best values.

Method	Mean loss $\downarrow$	$\operatorname{CVaR}_{0.90}$ $\downarrow$	Max loss $\downarrow$	Failure rate $\downarrow$
Mean-RMD	6.47	10.03	15.72	2.3%
Mean+Std-RMD	6.44	9.70	15.12	1.7%
Quantile-RMD	6.49	9.71	14.98	1.6%
Hard-Mining-RMD	6.46	9.66	14.81	1.5%
Max-RMD	6.61	9.62	14.32	1.3%
CVaR-RMD	6.45	9.50	14.55	1.4%

Table 4: Comparison with alternative risk-aware selection objectives. Values are equally weighted macro-averages across bin packing, CVRP, and flow-shop scheduling. All methods use matched candidate-generation and program-execution budgets. Lower is better.

External benchmark	Mean-RMD	CVaR-RMD	Relative change
OR-Library bin packing	12.41	11.63	$-6.3\%$
CVRPLIB	14.62	13.31	$-9.0\%$
Taillard flow shop	12.78	11.94	$-6.6\%$

Table 5: Transfer performance on independently curated public benchmark instances. The metric is

\operatorname{CVaR}_{0.90}

, and lower values are better. Programs are frozen before external evaluation.

Variant	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Failure rate (%) $\downarrow$
Full CVaR-RMD	$6.45{\pm}0.04$	$9.50{\pm}0.11$	$1.4{\pm}0.2$
Mean ranking	$6.47{\pm}0.05$	$10.06{\pm}0.15$	$2.3{\pm}0.3$
No accumulated losses	$6.53{\pm}0.06$	$10.22{\pm}0.17$	$2.7{\pm}0.4$
No tail records in prompt	$6.48{\pm}0.05$	$9.81{\pm}0.14$	$1.9{\pm}0.3$
Tail level $q=0.80$	$6.48{\pm}0.05$	$9.87{\pm}0.14$	$1.8{\pm}0.3$
Tail level $q=0.95$	$6.57{\pm}0.06$	$9.56{\pm}0.13$	$1.5{\pm}0.2$

Table 6: Ablation results averaged over tasks across

15

discovery seeds.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Task	Method	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Max loss $\downarrow$	Failure rate (%) $\downarrow$
Bin Packing	Mean-RMD	$7.18{\pm}0.09$	$11.82{\pm}0.27$	$17.41{\pm}0.55$	$2.8{\pm}0.5$
Bin Packing	CVaR-RMD	$7.08{\pm}0.07$	$10.96{\pm}0.20$	$15.92{\pm}0.44$	$1.7{\pm}0.3$
CVRP	Mean-RMD	$8.34{\pm}0.11$	$13.91{\pm}0.31$	$20.46{\pm}0.68$	$4.9{\pm}0.7$
CVRP	CVaR-RMD	$8.18{\pm}0.09$	$12.69{\pm}0.24$	$18.12{\pm}0.53$	$2.8{\pm}0.5$
Flow-Shop	Mean-RMD	$7.25{\pm}0.08$	$12.10{\pm}0.24$	$17.16{\pm}0.49$	$2.7{\pm}0.4$
Flow-Shop	CVaR-RMD	$7.19{\pm}0.07$	$11.25{\pm}0.19$	$15.78{\pm}0.41$	$1.6{\pm}0.3$

Appendix

Table 7: Per-task transfer results on larger held-out instances across

15

discovery seeds. Values are mean

\pm

standard deviation.

Task	Inst. family	Method	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Failure rate (%) $\downarrow$
Bin Packing	Uniform	Mean-RMD	$5.94{\pm}0.05$	$8.84{\pm}0.14$	$1.3{\pm}0.2$
	Uniform	CVaR-RMD	$5.90{\pm}0.04$	$8.42{\pm}0.11$	$0.9{\pm}0.2$
	Truncated normal	Mean-RMD	$6.21{\pm}0.06$	$9.47{\pm}0.16$	$1.7{\pm}0.3$
	Truncated normal	CVaR-RMD	$6.15{\pm}0.05$	$8.89{\pm}0.13$	$1.1{\pm}0.2$
	Heavy-tailed beta	Mean-RMD	$6.92{\pm}0.08$	$11.33{\pm}0.22$	$2.9{\pm}0.4$
	Heavy-tailed beta	CVaR-RMD	$6.87{\pm}0.07$	$10.55{\pm}0.17$	$1.8{\pm}0.3$

Appendix

Table 8: Held-out robustness by instance family across

15

discovery seeds.

Method	Bin Packing		CVRP		Flow-Shop
	CVaR 0.80 $\downarrow$	CVaR 0.95 $\downarrow$	CVaR 0.80 $\downarrow$	CVaR 0.95 $\downarrow$	CVaR 0.80 $\downarrow$	CVaR 0.95 $\downarrow$
Mean-RMD	$8.71{\pm}0.12$	$10.87{\pm}0.19$	$9.74{\pm}0.14$	$12.29{\pm}0.23$	$8.18{\pm}0.11$	$10.21{\pm}0.17$
CVaR-RMD	$8.29{\pm}0.09$	$10.06{\pm}0.15$	$9.25{\pm}0.12$	$11.47{\pm}0.20$	$7.84{\pm}0.09$	$9.61{\pm}0.14$

Appendix

Table 9: Evaluation with alternative CVaR tail levels across

15

discovery seeds. Programs are the same frozen programs used in the main held-out evaluation.

Generation	Mean-RMD			CVaR-RMD
	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Failure rate (%) $\downarrow$	Mean loss $\downarrow$	CVaR 0.90 $\downarrow$	Failure rate (%) $\downarrow$
$10$	$6.78{\pm}0.08$	$10.71{\pm}0.19$	$3.0{\pm}0.4$	$6.72{\pm}0.07$	$10.29{\pm}0.17$	$2.5{\pm}0.4$
$20$	$6.59{\pm}0.06$	$10.32{\pm}0.17$	$2.6{\pm}0.4$	$6.54{\pm}0.06$	$9.83{\pm}0.14$	$1.9{\pm}0.3$
$30$	$6.51{\pm}0.05$	$10.12{\pm}0.16$	$2.4{\pm}0.3$	$6.46{\pm}0.05$	$9.60{\pm}0.12$	$1.6{\pm}0.3$
$40$	$6.47{\pm}0.05$	$10.03{\pm}0.15$	$2.3{\pm}0.3$	$6.42{\pm}0.04$	$9.48{\pm}0.11$	$1.4{\pm}0.2$

Appendix

Table 10: Discovery progress averaged across tasks and

15

discovery seeds.

Task	Method	Median CVaR 0.90 $\downarrow$	IQR $\downarrow$	Worst-seed CVaR 0.90 $\downarrow$	Best-seed CVaR 0.90 $\downarrow$
Bin Packing	Mean-RMD	$9.86$	$0.21$	$10.17$	$9.61$
Bin Packing	CVaR-RMD	$9.28$	$0.15$	$9.52$	$9.09$
CVRP	Mean-RMD	$11.02$	$0.25$	$11.41$	$10.76$
CVRP	CVaR-RMD	$10.40$	$0.19$	$10.72$	$10.18$
Flow-Shop	Mean-RMD	$9.25$	$0.18$	$9.52$	$9.06$
Flow-Shop	CVaR-RMD	$8.80$	$0.15$	$9.05$	$8.63$

Appendix

Table 11: Run-to-run stability of held-out

\mathrm{CVaR}_{0.90}

across

15

discovery seeds.

Metric	Task	Mean-RMD	CVaR-RMD	Relative change	Cohen’s $d$
Mean loss	Bin Packing	$6.56{\pm}0.06$	$6.31{\pm}0.04$	$-3.8\%$	$0.58$
	CVRP	$7.20{\pm}0.06$	$7.08{\pm}0.05$	$-1.7\%$	$0.64$
	Flow-Shop	$5.95{\pm}0.04$	$5.96{\pm}0.04$	$+0.2\%$	$-0.18$
CVaR 0.90	Bin Packing	$9.88{\pm}0.15$	$9.29{\pm}0.11$	$-6.0\%$	$1.21$
	CVRP	$11.04{\pm}0.17$	$10.41{\pm}0.14$	$-5.7\%$	$1.08$
	Flow-Shop	$9.26{\pm}0.13$	$8.81{\pm}0.11$	$-4.9\%$	$0.94$

Appendix

Table 12: Additional statistical comparison between Mean-RMD and CVaR-RMD across

15

discovery seeds. Relative change is computed with respect to Mean-RMD; pp denotes percentage points.

Panel of Figure 4 — Figure 4: Main CVaR-RMD mutation prompt.

Panel of Figure 5 — Figure 5: Direct LLM sampling prompt.

Panel of Figure 6 — Figure 6: Mean-RMD mutation prompt difference. All other fields are identical to Figure 4 .

Panel of Figure 7 — Figure 7: Archive-conditioned prompt used by mean-selection evolutionary baselines.

Panel of Figure 8 — Figure 8: Mutation prompt for the no-tail-records ablation.

Panel of Figure 9 — Figure 9: Prompt substitution for tail-level ablations.

Panel of Figure 10 — Figure 10: Prompt substitution for the no-accumulated-losses ablation.

Automated Heuristic Design

Automated heuristic design creates or adapts problem-solving rules for optimization, planning, scheduling, and related search tasks.

See all 81 papers

Bayesian Optimization of CVaR with Unknown Hyperparameters
Oct 13, 2026Valentin Margraf, Jonas Hanselle, Viktor Bengs +3Bayesian Optimization Conditional Value-at-Risk
LMU Munich · Munich Center for Machine Learning (MCML) · German Research Center for Artificial Intelligence (DFKI) +3
RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
Jun 30, 2026Fei Liu, Alessio Figalli, Patrick Owen +1Distribution Shift Robustness Automated Algorithm Discovery
University of Zurich · 2ETH Zurich
SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution
Apr 27, 2026Sichun Luo, Yi Huang, Haochen Luo +7Automated Algorithm Discovery Evolutionary Optimization
1The University of Hong Kong · 2JIUTIAN Research, China Mobile · 3City University of Hong Kong

Oct 13, 2026J/K move · Enter open · S save

Bayesian Optimization of CVaR with Unknown Hyperparameters

Valentin Margraf, Jonas Hanselle, Viktor Bengs, Serafima Lebedeva+2

LMU Munich · Munich Center for Machine Learning (MCML) · German Research Center for Artificial Intelligence (DFKI)+3

Bayesian Optimization Conditional Value-at-Risk Black-Box Optimization Stochastic Optimization Gaussian Processes

Open paper AskPDF arXiv

We study Bayesian optimization of the Conditional Value-at-Risk (CVaR) of an expensive black-box function that depends on a decision and an environmental variable. Existing no-regret algorithms assume that the correct Gaussian process (GP) kernel and its hyperparameters are known. In practice, however, they must be estimated from limited data, often yielding a misspecified surrogate. This is especially damaging for CVaR because misspecification can distort the estimated tail-risk and thus lead to catastrophic decisions. We propose HE-CV-UCB, the first no-regret algorithm for CVaR Bayesian optimization with unknown GP hyperparameters. Given a finite candidate set containing a well-specified model, HE-CV-UCB adaptively eliminates those inconsistent with the observed data, actively queries where the survivors disagree, and returns a design that is robust across the surviving candidates. We prove that it attains cumulative regret matching the oracle rate of CV-UCB up to a factor depending only on the candidate set's size. Across synthetic benchmarks and three real-world applications, HE-CV-UCB achieves competitive performance and frequently outperforms existing CVaR Bayesian optimization methods.

Abstract

Automated Heuristic Design

Explore similar work

Bayesian Optimization of CVaR with Unknown Hyperparameters

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution