- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper proposes an approach to making AAD more efficient by reducing the cost of evaluating each candidate algorithm, by reducing the size of the set of instances they are run on. The authors describe their approach and evaluate it empirically.
Critical strengths
The paper studies an interesting problem...
Critical weaknesses
...but I am unconvinced that the evaluation cost is as much of an issue as the authors claim. One of the advantages of AAD is that algorithms can be targeted to smaller sets of instances, as it is easier to optimise new ones for different sets. It is unclear to me that existing approaches really overlook this and the effect of choice of evaluation instances on the search trajectory, or whether this is not an implicit feature of the process. It would be useful to provide some empirical evidence of the evaluation cost in other approaches. The authors provide this for their own work, but it is unclear whether this is representative of other approaches in the literature.
The section explaining the metric-aware feedback was unclear to me. In particular, I did not understand where the coordinate directions Omega come from, what they represent, or why and how they are useful. As this is one of the main contributions of the paper, it needs to be clearer -- an example would help.
It would be good to consider an approach that subsamples instances for a similar evaluation cost as a baseline. It is unclear whether the proposed targeted way of selecting instances improves over random subsampling.
Questions for authors
See above.
4 comments
Response Part II (W2/Q2)
We will explain using the illustration figure and a simple example. The three axes represent the three selected instances. Each coordinate direction, such as , uses the score on one instance. Each orange arrow represents a weight vector , with and . It combines the same three measured scores into a weighted score, .
CPI takes the best score available in the algorithm set for each evaluation direction, then averages these best scores:
Consider three algorithms with loss vectors , , and , where lower is better. If CPI uses only the three axes (), the best score on each axis is already . Adding a balanced algorithm , with , changes none of these best scores. Its marginal contribution to CPI is therefore zero, even though it performs reasonably well on all three instances.
Now add the direction to . Along this direction, each existing algorithm scores , while scores . Adding therefore lowers the best score for this direction from to . Because CPI averages the best scores across directions, its value also decreases, giving a positive contribution.
Additional directions thus allow CPI to reward algorithms with useful trade-offs that the three axes alone would miss. They reuse the measured scores and require no extra instance evaluations.
Thank you for the clarification.
Response Part III (W3/Q3)
We thank the reviewer for this comment. We evaluate Random-5—a random subsampling baseline operating under the exact same evaluation budget—across both OBP (Table 1) and TSP/CVRP (Table 2) to directly verify the advantage of targeted instance selection over random subsampling:
- Superior Mean Performance & Tighter Confidence Intervals on OBP (Table 1): PRISM outperforms Random-5 on 14 out of 15 test splits (tying on 1k/500), achieving the best overall performance on 12 splits. Crucially, PRISM exhibits substantially narrower 95% confidence intervals than Random-5. When the full instance suite spans distinct preference directions, random sampling risks drawing redundant instances with overlapping preferences—introducing selection bias and high cross-seed variance.
- Consistent Gains on TSP and Generalization Stability (Table 2): Extending this comparison to routing problems confirms the same trend. On TSP, PRISM+EoH-S consistently beats Random-5+EoH-S across every training and testing split.
- Performance under Extreme Compression on CVRP (Table 2): On CVRP, PRISM+EoH-S and Random-5+EoH-S yield comparable results (with PRISM leading on CVRP-Training and CVRP-500). Unlike OBP and TSP (128 instances), CVRP contains 256 training instances; fixing imposes a harsher compression ratio (~1.95% sampling rate), which bounds the representational capacity of any static 5-instance subset regardless of selection strategy.
Table 1
| Method | 200/500 | 500/1k | 1k/2k | 1k/200 | 1k/500 | 5k/200 | 5k/500 | 10k/200 | 10k/500 | Mix-1 | Mix-2 | Mix-3 | Mix-4 | Mix-5 | Mix-6 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PRISM | .0564 ± .0034 | .0260 ± .0011 | .0327 ± .0004 | .0130 ± .0014 | .0124 ± 1e-16 | .0028 ± .0006 | .0025 ± 1e-16 | .0015 ± .0001 | .0010 ± 3.5e-17 | .0510 ± .0081 | .1314 ± .0047 | .0711 ± .0060 | .1095 ± .0006 | .1246 ± .0117 | .0477 ± .0060 |
| scipy.linalg.interpolative | .0558 ± .0051 | .0264 ± .0032 | .0335 ± .0030 | .0163 ± .0100 | .0124 ± .0000 | .0066 ± .0131 | .0045 ± .0050 | .0050 ± .0147 | .0027 ± .0047 | .0553 ± .0033 | .1317 ± .0033 | .0721 ± .0017 | .1090 ± 0063 | .1291 ± .0049 | .0522 ± .0043 |
| SparseEval | .0627 ± .0000 | .0307 ± .0010 | .0372 ± .0000 | .0220 ± .0000 | .0124 ± .0000 | .0161 ± .0000 | .0070 ± .0000 | .0154 ± .0000 | .0050 ± .0000 | .0579 ± .0017 | .1397 ± .0000 | .0815 ± .0022 | .1147 ± .0000 | .1326 ± .0000 | .0578 ± .0000 |
| mRMR | .0575 ± .0134 | .0279 ± .0047 | .0341 ± .0096 | .0200 ± .0002 | .0124 ± .0000 | .0131 ± .0127 | .0065 ± .0000 | .0126 ± .0139 | .0047 ± .0000 | .0542 ± .0073 | .1301 ± .0106 | .0733 ± .0048 | .1111 ± .0111 | .1303 ± .0173 | .0537 ± .0343 |
| Random-5 | .0569 ± .0061 | .0270 ± .0016 | .0346 ± .0049 | .0157 ± .0052 | .0124 ± .0000 | .0067 ± .0134 | .0052 ± .0054 | .0040 ± .0054 | .0025 ± .0049 | .0565 ± .0039 | .1344 ± .0119 | .0749 ± .0151 | .1117 ± .0072 | .1307 ± .0057 | .0545 ± .0074 |
Table 2
| Method | TSP–Training 10–200 | TSP–Testing 50 | 100 | 200 | 500 | CVRP–Training 20–200 | CVRP–Testing 50 | 100 | 200 | 500 |
|---|---|---|---|---|---|---|---|---|---|---|
| FunSearch Top10 | .1241 ± .0155 | .0931 ± .0469 | .1217 ± .0008 | .1423 ± .0067 | .1588 ± .0088 | .2454 ± .0462 | .2572 ± .0460 | .2931 ± .0595 | .2055 ± .0248 | .1827 ± .0435 |
| ReEvo Top10 | .1190 ± .0862 | .0836 ± .0975 | .1066 ± .0879 | .1315 ± .1012 | .1498 ± .0757 | .2428 ± .1001 | .2743 ± .1074 | .2903 ± .1146 | .2056 ± .0972 | .1607 ± .0542 |
| EoH | .1525 ± .0051 | .1328 ± .0254 | .1481 ± .0144 | .1663 ± .0124 | .1939 ± .0152 | .2765 ± .0675 | .2838 ± .0723 | .3101 ± .1083 | .2426 ± .0267 | .2054 ± .0236 |
| EoH Top10 | .1282 ± .0333 | .0985 ± .0429 | .1259 ± .0407 | .1447 ± .0441 | .1699 ± .0340 | .2303 ± .0834 | .2166 ± .1145 | .2664 ± .1383 | .2060 ± .0677 | .1743 ± .0329 |
| PRISM+EoH | .1259 ± .0084 | .0845 ± .0111 | .1207 ± .0290 | .1238 ± .0189 | .1511 ± .0086 | .2128 ± .0477 | .2078 ± .0937 | .2573 ± .0568 | .2033 ± .0042 | .1789 ± .0172 |
| EoH-S | .1006 ± .0835 | .0674 ± .0825 | .0932 ± .0681 | .1221 ± .0799 | .1479 ± .0891 | .1754 ± .0516 | .1614 ± .0420 | .2066 ± .0702 | .1686 ± .0566 | .1535 ± .0563 |
| PRISM+EoH-S | .1166 ± .0306 | .0730 ± .0426 | .0916 ± .0420 | .1240 ± .0123 | .1406 ± .0354 | .2105± .0366 | .2072 ± .0501 | .2475 ± .0358 | .1990 ± .0303 | .1525 ± .0334 |
| Random-5+EoH-S | .1253 ± .0330 | .0812 ± .0019 | .1081 ± .0235 | .1332 ± .0612 | .1618 ± .0742 | .2127 ± .0179 | .2026 ± .0119 | .2478 ± .0306 | .1953 ± .0272 | .1658 ± .0285 |
Response Part I (W1/Q1)
We thank the reviewer for raising this question regarding our motivation and whether evaluation cost is a genuine bottleneck in LLM-based AAD. We provide empirical evidence and clarify our broader scientific motivation below:
1 Empirical Evidence of Evaluation Cost
To quantify the evaluation cost in existing literature, in our local experimental environment, running full-suite EoH-S (128 instances) takes 464 minutes, whereas PRISM+EoH-S reduces this wall-clock time to 95 minutes.
Heavy parallel instance evaluations are active during 99.89% of EoH-S's total execution time, making evaluation a persistent operational bottleneck. In contrast, PRISM+EoH-S restricts parallel evaluations to only 26.26% of the execution time, successfully shifting the primary bottleneck to the LLM sampler.
2 The Generalization of Small-Set Training
While existing approaches can technically target smaller instance sets (e.g., ~5 instances), researchers also care about the out-of-sample generalization of the discovered algorithms across the full problem distribution.
As demonstrated by our Random-5 ablation, blindly tuning on a small subset without principled selection may leads to overfitting and suboptimal performance. More importantly, frequently retraining or re-searching via LLMs from scratch for different instance sets in practice is computationally prohibitive.
3 Unveiling the Low-Rank Instance-Algorithm Space
Beyond operational efficiency, our work is driven by a fundamental scientific question: verifying the low-rank structure of instance preferences.
Given the dual empirical observation in AAD that a compact set of algorithms can cover broad problem spaces, we investigate whether a compact set of representative instances can faithfully reflect full-suite algorithm preferences. PRISM is designed not merely as a cost-cutting heuristic, but as a tool to understand the underlying behavioral space and dynamics of LLM-driven AAD.