acceptodds
Under review as a conference paper at ICLR 2027

PRISM: Representative Instance Selection for LLM-Driven Automated Algorithm Design

Abstract

A major bottleneck in LLM-based Automated Algorithm Design (AAD) lies in repeatedly evaluating candidate algorithms across a broad instance suite to guide search. However, evaluating candidate algorithms on a full, static suite often creates a major efficiency bottleneck: it incurs heavy computational costs while introducing evaluation noise and structural redundancy that can misguide search. In this paper, we show that full-suite evaluations contain substantial performance redundancy, which can be effectively uncovered by probing with a small set of reference algorithms. Inspired by this observation, we propose PRISM (Probe-guided Representative Instance Selection with Metric-aware feedback), a versatile plug-in for AAD. PRISM operates in two key steps: first, it uses initial algorithm responses as probes to evaluate instance representativeness and select a compact subset that generalizes to unseen algorithms. Second, it adapts the subset evaluations to downstream selection rules via metric-aware feedback, maintaining high selection resolution without requiring extra instance runs. Extensive experiments across diverse combinatorial optimization problems demonstrate that PRISM reduces physical algorithm-instance evaluations by a factor of up to 20 while preserving—and under scalar selection, often improving—search performance compared to full-suite evaluations.

Primary area:
optimization
Keywords:
Automated Algorithm Design, Large Language Models, Efficient Algorithm Search, Combinatorial Optimization

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_BhDtOpenReview ↗
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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

Response Part II (W2/Q2)

We will explain Ω\Omega using the illustration figure and a simple example. The three axes represent the three selected instances. Each coordinate direction, such as e1=(1,0,0)e_1=(1,0,0), uses the score on one instance. Each orange arrow represents a weight vector ω\omega, with ωi≥0\omega_i\geq0 and ∑iωi=1\sum_i\omega_i=1. It combines the same three measured scores into a weighted score, ω⊤y(h)\omega^\top y(h).

CPI takes the best score available in the algorithm set for each evaluation direction, then averages these best scores:

CPIΩ(S)=1∣Ω∣∑ω∈Ωmin⁡h∈Sω⊤y(h)CPI_{\Omega}(S)=\frac{1}{|\Omega|}\sum_{\omega\in\Omega}\min_{h\in S}\omega^\top y(h)

Consider three algorithms with loss vectors y(A1)=(0,1,1)y(A_1)=(0,1,1), y(A2)=(1,0,1)y(A_2)=(1,0,1), and y(A3)=(1,1,0)y(A_3)=(1,1,0), where lower is better. If CPI uses only the three axes (Ω={e1,e2,e3}\Omega=\{e_1,e_2,e_3\}), the best score on each axis is already 00. Adding a balanced algorithm BB, with y(B)=(0.4,0.4,0.4)y(B)=(0.4,0.4,0.4), 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 ω=(1/3,1/3,1/3)\omega=(1/3,1/3,1/3) to Ω\Omega. Along this direction, each existing algorithm scores 2/32/3, while BB scores 0.40.4. Adding BB therefore lowers the best score for this direction from 2/32/3 to 0.40.4. Because CPI averages the best scores across directions, its value also decreases, giving BB 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.

AuthorsOpenReview ↗

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 k=5k=5 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 k=5k=5 imposes a 2×2\times harsher compression ratio (~1.95% sampling rate), which bounds the representational capacity of any static 5-instance subset regardless of selection strategy.

Table 1

Method200/500500/1k1k/2k1k/2001k/5005k/2005k/50010k/20010k/500Mix-1Mix-2Mix-3Mix-4Mix-5Mix-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

MethodTSP–Training 10–200TSP–Testing 50100200500CVRP–Training 20–200CVRP–Testing 50100200500
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
Reviewer_gDiKOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper is part of the line of work that studies automated algorithm design (AAD) techniques like Evolution-of-Heuristics (EoH), AlphaEvolve, etc. These techniques use ideas from evolutionary search to evolve a set of heuristics (for example, for online bin packing or TSP) which are evaluated on a fixed set of instances. This paper develops methods for selecting a subset of instances from the initial set of instances to evaluate the heuristics at each evolutionary step. In doing so, it aims to speed up the overall runtime of existing AAD methods. The method works by evaluating an initial set of heuristics on the full set of instances and performing interpolative matrix decomposition to find the representative set of instances. It then provides a heuristic method to mitigate the distortion that may result from only evaluating the heuristics on this smaller, representative set. Although the experiments show modest improvements, I cannot tell if they are statistically significant.

Critical strengths
  • The paper’s methodology is described in a clear enough way that it seems reproducible. Overall, the paper was quite easy to read.
  • Speeding up evolutionary search methodologies for AAD is certainly an important problem. My understanding is that these techniques require substantial compute to evaluate the quality of the proposed algorithms at each evolutionary step.
Critical weaknesses
  • The paper’s novelty is on the low side. Interpolative matrix decomposition is a common method for determining representative subsets of a matrix’s rows (or columns). Moreover, the paper seems to build a new heuristic method for this type of matrix decomposition rather than relying on existing tools. For example, why not use scipy.linalg.interpolative?
  • There’s not enough information in Section 4 for me to evaluate the performance of this method. In particular, all tables and plots need to include confidence intervals.
    • I’m particularly interested in Table 3, which compares the performance of the paper’s method with existing baselines when both methods have the same fixed budget of total function evaluations. I can’t tell how often the paper’s method outperforms the baseline methods with statistical significance.
    • I am also particularly interested in the ablations in Table 4, such as the comparison with Random-5, which selects 5 random instances for evaluation, rather than selecting those 5 instances using the paper’s method. Random-5 and the paper’s method differ by only 0.005 (and I can’t tell whether this small difference is statistically significant). This seems like a very important ablation, so it would be useful to see the comparison between Random-5 and PRISM+EoH-S on TSP and CVRP as well.
Questions for authors
  • Can you please provide confidence intervals for all results in the main body?
  • Can you please provide an ablation with standard methods for interpolative matrix decomposition, such as scipy.linalg.interpolative?
  • Can you please provide an ablation that compares Random-5 and PRISM+EoH-S on TSP and CVRP?
4 comments
AuthorsOpenReview ↗

Response Part I (W1/Q2)

We thank the reviewer for this thoughtful question and the suggestion to compare with standard interpolative matrix decomposition (scipy.linalg.interpolative).

We fully acknowledge the conceptual similarity between standard ID and our instance selection module—both exploit the underlying low-rank structure of the performance matrix to identify representative subsets. In our ablation study, scipy.linalg.interpolative indeed achieves competitive performance close to PRISM (with PRISM holding a slight edge in mean performance, likely due to our LOAO criterion and ridge regularization). Rather than viewing this as a limitation, we believe the strong performance of scipy.linalg.interpolative provides independent validation for our core scientific hypothesis: leveraging low-rank preference directions is fundamentally superior for guiding evolutionary algorithm design.

We respectfully emphasize that our paper’s novelty extends beyond proposing a standalone matrix decomposition heuristic. Our core contributions lie in establishing a complete, metric-aligned evaluation framework for LLM-driven Automated Algorithm Design (AAD):

  • Our approach stems from a insight motivated by EoH-S's empirical findings: the fact that a compact algorithm portfolio can cover diverse instances implies that instance preferences share correlated, low-dimensional directions. Formulating instance selection as low-rank reconstruction naturally uncovers these dominant directions while filtering out evaluation noise—a connection previously unexplored in LLM-driven AAD.
  • Identifying the Right Selection Paradigm for AAD: Prior to this work, it was unclear which instance selection principle best preserves evolutionary gradients in continuous code spaces. By systematically contrasting different paradigms—including Pareto-dominance preservation (kk-EMOSS), high-variance discrimination, and macro-average preservation (mRMR, SparseEval), —we demonstrate that low-rank reconstruction is suited to filter evaluation noise while maintaining algorithmic rankings.
  • Bridging Dimension Reduction with Metric-Aware Feedback: Selecting a subset (whether via PRISM or scipy.linalg.interpolative) inevitably compresses the evaluation space. For portfolio-based metrics like EoH-S's CPI, a KK-instance subset inherently caps the number of effective algorithms at KK. Our Metric-Aware Feedback module is specifically designed to resolve this post-selection bottleneck—mitigating signal sparsity and expanding the pool of effective algorithms during evolution, which standard matrix decomposition tools alone cannot address.

We will include the scipy.linalg.interpolative ablation results and clarify this broader positioning of our contributions in the revised manuscript.

Method200/500500/1k1k/2k1k/2001k/5005k/2005k/50010k/20010k/500Mix-1Mix-2Mix-3Mix-4Mix-5Mix-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
AuthorsOpenReview ↗

Response Part II (W2/Q1)

We thank the reviewer for emphasizing statistical rigor. We have updated tables and figures to report the mean ±\pm 95% confidence intervals across independent runs.

Table 1

Method200/500500/1k1k/2k1k/2001k/5005k/2005k/50010k/20010k/500Mix-1Mix-2Mix-3Mix-4Mix-5Mix-6
FunSearch.0624 ± .0026.0299 ± .0023.0366 ± .0007.0213 ± .0051.0124 ± .0000.0159 ± .0032.0068 ± .0007.0152 ± .0030.0051 ± .0004.0602 ± .0100.1379 ± .0043.0806 ± .0090.1182 ± .0143.1340 ± .0065.0594 ± .0041
FunSearch Top10 ‡.0608 ± .0031.0289 ± .0026.0361 ± .0015.0207 ± .0038.0124 ± .0000.0152 ± .0016.0065 ± .0000.0145 ± .0015.0050 ± .0000.0568 ± .0012.1361 ± .0059.0783 ± .0060.1136 ± .0027.1304 ± .0046.0571 ± .0016
ReEvo.0609 ± .0025.0299 ± .0007.0363 ± .0014.0217 ± .0014.0133 ± .0036.0162 ± .0043.0068 ± .0014.0155 ± .0058.0053 ± .0009.0584 ± .0051.1368 ± .0020.0783 ± .0065.1167 ± .0043.1336 ± .0020.0594 ± .0047
ReEvo Top10.0581 ± .0067.0285 ± .0041.0349 ± .0032.0200 ± .0025.0124 ± .0000.0121 ± .0077.0063 ± .0007.0102 ± .0105.0049 ± .0007.0569 ± .0010.1352 ± .0025.0769 ± .0045.1134 ± .0018.1306 ± .0023.0561 ± .0046
EoH.0619 ± .0021.0307 ± .0005.0371 ± .0002.0220 ± .0000.0124 ± .0000.0162 ± .0008.0068 ± .0007.0153 ± .0004.0052 ± .0006.0590 ± .0017.1382 ± .0050.0816 ± .0043.1217 ± .0227.1350 ± .0090.0597 ± .0040
EoH Top10.0618 ± .0025.0299 ± .0021.0368 ± .0007.0216 ± .0014.0124 ± .0000.0158 ± .0010.0065 ± .0012.0152 ± .0005.0051 ± .0009.0583 ± .0029.1377 ± .0057.0813 ± .0045.1154 ± .0037.1327 ± .0010.0582 ± .0022
PRISM+EoH.0568 ± .0014.0278 ± .0013.0338 ± .0004.0180 ± .0043.0124 ± .0000.0143 ± .0015.0060 ± .0007.0134 ± .0016.0047 ± .0000.0569 ± .0009.1335 ± .0016.0735 ± .0027.1120 ± .0036.1324 ± .0047.0531 ± .0052
EoH-S.0515 ± .0025.0231 ± .0010.0314 ± .0014.0117 ± .0015.0124 ± .0000.0032 ± .0008.0025 ± .0000.0014 ± .0004.0010 ± .0000.0499 ± .0076.1287 ± .0021.0681 ± .0016.1045 ± .0023.1226 ± .0080.0475 ± .0028
PRISM+EoH-S.0564 ± .0042.0260 ± .0020.0327 ± .0006.0130 ± .0072.0124 ± .0000.0028 ± .0017.0025 ± .0025.0015 ± .0009.0010 ± .0016.0510 ± .0010.1314 ± .0031.0711 ± .0028.1095 ± .0006.1246 ± .0049.0477 ± .0029

Table 2

MethodTSP–Training 10–200TSP–Testing<br>50100200500CVRP–Training 20–200CVRP–Testing 50100200500
FunSearch.1563 ± .0103.1319 ± .0336.1503 ± .0172.1726 ± .0086.2069 ± .0699.2940 ± .0347.3182 ± .0656.3421 ± .0347.2467 ± .0177.1911 ± .0475
FunSearch Top10.1241 ± .0155.0931 ± .0469.1217 ± .0008.1423 ± .0067.1588 ± .0088.2454 ± .0462.2572 ± .0460.2931 ± .0595.2055 ± .0248.1827 ± .0435
ReEvo.1588 ± .0749.1296 ± .0902.1467 ± .0953.1649 ± .1243.1717 ± .0906.2661 ± .0563.3026 ± .0931.3186 ± .0547.2281 ± .0555.1762 ± .0309
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

Table 3

MethodOBP–Testing 1k/2001k/5005k/2005k/50010k/20010k/500TSP–Testing 50100200500CVRP–Testing 50100200500
EoH.0220 ± .0000.0124 ± .0000.0159 ± .0025.0067 ± .0032.0151 ± .0032.0050 ± .0000.0985 ± .1574.1192 ± .0454.1449 ± .0783.1542 ± .0814.2148 ± .0347.2817 ± .0440.2062 ± .0508.1665 ± .0856
PRISM+EoH.0180 ± .0043.0124 ± .0000.0143 ± .0015.0060 ± .0007.0134 ± .0016.0047 ± .0000.0845 ± .0111.1207 ± .0290.1238 ± .0189.1511 ± .0086.2078 ± .0937.2573 ± .0568.2033 ± .0042.1789 ± .0172
EoH-S.0210 ± .0000.0124 ± .0000.0123 ± .0000.0065 ± .0000.0109 ± .0000.0050 ± .0000.0899 ± .0590.1199 ± .0533.1569 ± .0398.1603 ± .0303.2297 ± .0464.2756 ± .1034.2110 ± .0191.1736 ± .0007
PRISM+EoH-S.0130 ± .0072.0124 ± .0000.0028 ± .0017.0025 ± .0025.0015 ± .0009.0010 ± .0016.0730 ± .0426.0916 ± .0420.1240 ± .0123.1406 ± .0354.2072 ± .0501.2475 ± .0358.1990 ± .0303.1525 ± .0334

Figure 2
Figure 2 - OBP, Figure 2 - TSP, Figure 2 - CVRP

Key Observations from the 95% CIs:

  • PRISM+EoH consistently outperforms standard EoH and EoH Top10 with non-overlapping 95% CIs across nearly all benchmarks, indicating that evaluating EoH directly on the full 128-instance suite can introduce substantial evaluation bias (or noise) that misleads the evolutionary search.
  • While requiring only a fraction of the instance evaluations, PRISM+EoH-S achieves statistically comparable performance to full-evaluation EoH-S
AuthorsOpenReview ↗

Response Part III (W2/Q3)

We thank the reviewer for this suggestion. We have extended the Random-5+EoH-S ablation to both TSP and CVRP.

Main Results

MethodTSP–Training 10–200TSP–Testing 50100200500CVRP–Training 20–200CVRP–Testing 50100200500
FunSearch.1563 ± .0103.1319 ± .0336.1503 ± .0172.1726 ± .0086.2069 ± .0699.2940 ± .0347.3182 ± .0656.3421 ± .0347.2467 ± .0177.1911 ± .0475
FunSearch Top10.1241 ± .0155.0931 ± .0469.1217 ± .0008.1423 ± .0067.1588 ± .0088.2454 ± .0462.2572 ± .0460.2931 ± .0595.2055 ± .0248.1827 ± .0435
ReEvo.1588 ± .0749.1296 ± .0902.1467 ± .0953.1649 ± .1243.1717 ± .0906.2661 ± .0563.3026 ± .0931.3186 ± .0547.2281 ± .0555.1762 ± .0309
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

Key findings:

  • Clear Advantage on OBP and TSP: Across both OBP and TSP benchmarks, PRISM+EoH-S consistently outperforms Random-5+EoH-S across every training and testing split. This confirming that random selection misses critical structural preference directions. Specifically, when the full suite spans distinct preference directions, random sampling can inadvertently draw redundant instances with overlapping preferences—introducing selection bias and causing the evolutionary search to overfit to a narrow subset of behaviors.
  • Comparable Performance on CVRP (Compression Bottleneck): On CVRP, PRISM+EoH-S and Random-5+EoH-S achieve comparable results (with PRISM slightly leading on CVRP-Training and CVRP-500). This occurs because CVRP contains 256 training instances—twice as many as OBP and TSP (128 instances). Fixing the subset size at k=5k=5 imposes a 2×2\times harsher compression ratio (~1.95% vs. ~3.9% sampling rate), which limits the representational capacity of static 5-instance subset.
Reviewer_KsY1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the high cost of candidate algorithm evaluation in LLM-driven Automated Algorithm Design (AAD) by proposing the representative instance selection framework PRISM. This method utilizes the response matrix constructed from initial probe algorithms, selects a small number of representative instances through Leave-One-Algorithm-Out (LOAO) reconstruction error and greedy forward selection, and introduces Metric-Aware Feedback to improve the algorithm selection feedback after instance compression. PRISM can be directly integrated into existing AAD frameworks.

Critical strengths

S1. This paper proposes a representative instance selection method based on LOAO reconstruction error. It uses the response matrix of the initial probe algorithms to evaluate the predictive ability of a subset of instances for algorithms not involved in the fitting process and constructs a compact evaluation instance set through greedy search, reducing reliance on manually added instance features.

S2. This paper proposes a Metric-Aware Feedback mechanism, employing different feedback strategies for scalar and set-based selection mechanisms. In particular, it improves the ability to distinguish complementary algorithms in low-dimensional space by augmenting preference directions, without requiring additional instance evaluation.

Critical weaknesses

W1. The core technology has limited innovation, and its differentiation from existing efficient evaluation methods is not clearly defined. Instance selection, regression reconstruction, and sparse evaluation based on performance matrices have been adopted in related research. PRISM mainly combines LOAO regression with greedy selection and designs a feedback adaptation mechanism for AAD. Furthermore, AdaEva has proposed an adaptive partial evaluation method for AAD. This paper lacks direct comparisons with these methods and has not fully demonstrated the unique technical advantages of LOAO and the overall framework.

[1] Bowyer et al., Efficient Benchmarking Is Just Feature Selection and Multiple Regression, 2026.

[2] Zhang et al., SparseEval: Efficient Evaluation of Large Language Models by Sparse Optimization, ICLR 2026.

[3] Nguyen et al., AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluation, 2026.

W2. LOAO's generalization ability is insufficient to support the representativeness assumption in dynamic algorithm search. LOAO only verifies the reconstruction ability between initial probe algorithms, but PRISM uses approximately 10 initial algorithms to select a fixed subset of instances, which is then applied to approximately 1,990 candidate evaluations. The behavior of subsequent algorithms may significantly deviate from the initial probe set. The paper lacks a ranking consistency analysis across evolutionary stages and cannot prove that low initial reconstruction error guarantees the reliability of subsequent algorithm selection.

W3. Metric-Aware Feedback lacks theoretical and experimental evidence for recovering complete evaluation behavior. This module constructs interior preference directions by weighting the scores of a small number of instances, but these directions do not incorporate information about unselected instances, thus failing to recover the algorithmic differences lost in the low-dimensional projection. This mechanism may improve selection discriminability within the compressed space, but it does not necessarily preserve the selection preferences of the full instance suite. The paper lacks direct verification of the consistency between the two evaluation mechanisms.

W4. Experimental comparisons are insufficient to demonstrate the advantage of PRISM over existing efficient evaluation methods. The paper primarily compares PRISM with complete evaluation and limited static instance selection strategies, lacking direct comparisons with adaptive partial evaluation methods under the same budget. Experiments use only three random seeds, and significant performance degradation occurs on some tasks. For example, in the CVRP 50-node test, the optimality gap for EoH-S is 0.1614, while for PRISM+EoH-S it is 0.2072. These results are insufficient to fully demonstrate its trade-off advantage between efficiency and search quality.

W5. The analysis of actual computational costs is insufficient. While the paper includes the cost of constructing the initial performance matrix, it does not fully quantify the time required for LOAO reconstruction, greedy instance selection, and feedback adaptation, nor does it provide a trade-off analysis between the number of probing algorithms and computational cost. Therefore, the reduction in the number of instance evaluations alone is insufficient to demonstrate PRISM's end-to-end efficiency advantage.

Questions for authors

Q1. Compared to existing methods such as mRMR, regression-based benchmark selection, and SparseEval, what are the unique advantages of LOAO instance selection? Why does minimizing the reconstruction error of the performance matrix ensure more accurate ranking and evolutionary selection of candidate algorithms?

Q2. PRISM uses only a small number of initial probe algorithms to select a fixed subset of instances. As the algorithm evolves, how do the authors ensure that these instances remain representative? Can you report the Spearman and Kendall correlations and Top-K selection consistency rates at different search stages, and analyze when the instance subset becomes invalid?

Q3. If two algorithms perform identically on selected instances but differ significantly on unselected instances, how does Metric-Aware Feedback distinguish them?

Q4. Can the authors prove that adding preference directions truly preserves the selection mechanism of the full instance suite, and not merely changes the evaluation rules in the compressed space?

Q5. Compared to adaptive partial evaluation methods such as AdaEva, why does PRISM use a fixed subset of instances? Can the authors compare the two methods under the same number of candidate algorithms, instance evaluation budget, and end-to-end runtime, and verify the advantages of a fixed subset in terms of search efficiency and generalization?

6 comments
AuthorsOpenReview ↗

Response Part I (comparison with existing efficient evaluation methods) (W1/Q1)

We thank the reviewer for the comments. We will clarify the fundamental differences between PRISM and existing efficient evaluation methods (such as SparseEval and mRMR), as well as to provide empirical evidence supporting our approach. We hope these results address your concerns and would be happy to discuss any remaining questions.

1 Problem Settings: Static Evaluation vs Evolutionary Dynamics
Existing methods like SparseEval and mRMR are primarily designed for static evaluation benchmarks, where a fixed, pre-defined set of candidate algorithms is evaluated. Their goal is to reduce the evaluation cost on a static testbed.

In contrast, LLM-for-AAD is an evolutionary process. In each generation, new candidate algorithms are iteratively generated by LLMs. The instance selection strategy directly determines the selection pressure and fitness ranking, which in turn steers the search dynamics and the distribution of subsequent generations. To the best of our knowledge, optimizing instance selection specifically to preserve the evolutionary dynamics of LLM-for-AAD remains largely unexplored.

2 Modeling Rationale & Comparison Results
Formulating a robust instance selection criterion is non-trivial, as different paradigms make fundamentally different assumptions about how instances drive evolution: (a) preserving global macro-average performance (mRMR, SparseEval); (b) treating instances as objectives to maintain Pareto-dominance relations (kk-EMOSS); (c) prioritizing high-resolution instances to maximize algorithmic discrimination; and (d) capturing shared latent "directions" across instance preferences (reconstruction-based methods like PRISM).

  • Macro-Average Preservation (mRMR, SparseEval): These methods select representative instances to approximate the global mean performance. However, scalar aggregation smooths out subtle algorithmic distinctions across heterogeneous instances, weakening selection pressure. Consequently, as shown in the following table, they have relatively high CPI than other methods.

  • Pareto-Dominance Preservation (kk-EMOSS): Treating instances as objectives to maintain Pareto dominance is theoretically appealing, yet in the continuous LLM code space, Pareto relations are often too sparse to offer evolutionary gradients. In the paper's Table 4, kk-EMOSS has 0.01823 training CPI and 0.047243 testing CPI, compared to our PRISM's CPI of 0.01592 and 0.044858.

  • High-Resolution / Discrimination Selection: Prioritizing high-variance instances aims to sharpen algorithmic discrimination, but over-weighting extreme cases causes LLM-guided search to overfit to outliers and noisy evaluations. Our experiments (also in Table 4 of the paper) show this leads to a CPI of 0.01623 and 0.046576.

  • Shared Latent Preference Directions (PRISM): Inspired by EoH-S, PRISM leverages the fact that instances share correlated preferences for algorithmic behaviors, capturing these latent "directions" via non-negative low-rank matrix reconstruction. This preserves fine-grained performance profiles while filtering out noise. Compared with different instance selection methods, PRISM has the best overall results.

Method200/500500/1k1k/2k1k/2001k/5005k/2005k/50010k/20010k/500Mix-1Mix-2Mix-3Mix-4Mix-5Mix-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
ID.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

3 Why minimizing the reconstruction error?

Our approach is built on a core hypothesis directly motivated by the empirical findings of EoH-S: the fact that a compact set of algorithms can effectively cover a broad spectrum of instances implies that instance preferences share correlated, low-dimensional "directions." Minimizing the non-negative low-rank reconstruction error naturally uncovers these dominant structural directions while filtering out noise. By aligning instance selection with the underlying low-rank manifold rather than noisy raw scores, PRISM preserves accurate relative rankings among candidate algorithms.

This formulation grants PRISM two advantages over existing selection paradigms:

  1. Resistance to Outliers and Noise: Unlike difficulty- or variance-based methods that can cause LLM-guided evolution to overfit to edge-case anomalies, PRISM’s low-rank regularization anchors selection to shared structural patterns, guaranteeing stable macro-generalization.
  2. Fine-Grained, Metric-Aware Selection Pressure: Unlike macro-average proxies (mRMR, SparseEval) that smooth out subtle algorithmic differences, or Pareto-based methods (kkEMOSS) that suffer from sparsity in continuous LLM code spaces, PRISM retains rich, metric-aware feedback across latent preference directions.

4 Discussion and Comparison with AdaEva
We thank the reviewer for pointing out AdaEva, which we will cite and discuss in our revision. Direct comparison under identical budgets is currently infeasible due to timeline and fundamental paradigm differences:

  • Concurrent Work: AdaEva was released on arXiv and GitHub after the ICLR submission deadline, making it a concurrent work unavailable at submission.
  • Task Mismatch (Algorithm Pruning vs. Instance Selection): AdaEva adaptively allocates budget by progressively evaluating and eliminating candidate algorithms, whereas PRISM explicitly selects representative instances. Thus, AdaEva does not provide an interchangeable instance-selection baseline.
  • Conflict with Complementary Search (EoH-S): EoH-S retains algorithms based on their portfolio-level contribution rather than aggregate averages. Applying AdaEva’s elimination rules directly would prematurely discard specialist algorithms that underperform on early general instances but excel on niche ones. A faithful comparison would require redesigning AdaEva with complementarity-aware pruning criteria, which goes beyond the scope of this work.
AuthorsOpenReview ↗

Response Part II (analysis of PRISM's dynamics) (W2/Q2)

We thank the reviewer for raising this question regarding the dynamic representativeness of the initially selected instance subset across evolutionary stages. To address W2 and Q2, we conducted a tracking analysis on the Online Bin Packing (OBP) benchmark.

1 Stage-wise Ranking Consistency Analysis (Spearman, Kendall, and Top-10)

As shown in Spearman, Kendall and Top-10 Results, the fixed instance subset selected from initial probe algorithms maintains high global ranking fidelity throughout the entire evolutionary trajectory:

  1. Stable Global Selection Pressure: Both Spearman ρ\rho (0.950–0.9610.950\text{--}0.961) and Kendall τb\tau_b (0.872–0.9090.872\text{--}0.909) remain consistently high from Stage 1 to Stage 5 with no degradation. This confirms that the low-rank structural directions captured by the initial probe set generalize well to unseen candidate algorithms and provide reliable macro-level evolutionary guidance across all stages.
  2. Interpreting Top-10 Overlap: While Top-10 overlap is moderate (0.067–0.3250.067\text{--}0.325), this reflects score convergence among top candidates rather than ranking failure. In mid-to-late stages (especially Stage 3), numerous elite heuristics achieve near-identical optimality gaps on the benchmark, causing minor tie-breaking permutations within the top 10.

2 Per-Instance Generalization & When the Subset Becomes Invalid (Heatmap Analysis) To examine fine-grained generalization and identify when the static subset begins to lose validity, we visualize the log-ratio optimality gap trajectory across all 128 OBP instances in EoH-S, PRISM, mRMR and SparseEval heatmap:

In each figure:

  • Each row represents one training instance, and columns track evolution from initialization to the final generation. The top panel shows the five selected instances; the bottom panel shows the remaining 123 instances.
  • Colors: Values show the log gap ratio relative to initialization. Blue indicates improvement, red indicates deterioration, and white indicates little or no change.

There are several key observations:

  • Cross-Instance Generalization: PRISM+EoH-S successfully improves performance on 59 out of 128 instances (4/5 selected and 55/123 unselected), closely matching the coverage of EoH-S (69/128 improved) at a fraction of the evaluation cost. Notably, PRISM even improves 3 instances that remained unchanged under full-dataset evaluation. This result demonstrates that focusing on core structural directions prevents the search from getting diluted by redundant instances.
  • When Invalidity / Overfitting Occurs: As highlighted at the bottom of the PRISM heatmap, the static subset remains valid through the early and middle stages (Generations 0–140), during which 0 instances worsen. However, in the late evolutionary stage (after ~Generation 150), mild overfitting emerges: 4 unselected instances exhibit performance degradation (worsened gaps compared to initialization) as the LLM continues to fine-tune heuristics exclusively against the 5 selected instances.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.