- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents ReAL-AHD, a framework for LLM-based automatic heuristic design that organizes discovered algorithms into a relational algorithm landscape. It maintains a derivation graph to capture evolutionary lineages and a similarity graph constructed using PreferSim, which measures algorithm similarity through action preferences on aligned decision states. Based on these relations, the framework introduces hierarchical graph planning to allocate search budgets across dynamic algorithm families and perform operator-conditioned parent selection. A graph-aware memory module further retrieves relevant evolutionary experiences to guide generation.
Experiments across five combinatorial optimization problems and three heuristic paradigms demonstrate competitive performance against existing AHD methods. The paper also includes component ablations, cross-size and out-of-distribution evaluations, analyses with different LLMs, and computational cost measurements.
Critical strengths
The paper presents a well-motivated relational representation that captures complementary aspects of algorithm search history. PreferSim offers a meaningful alternative to existing similarity measures by comparing action preferences on aligned decision states, and the ablation studies support the benefits of combining derivation and similarity relations. Another strength is the extensive empirical evaluation across multiple optimization problems and heuristic paradigms, with comparisons against competitive baselines, generalization tests, and efficiency analyses. These results provide encouraging evidence of the framework's effectiveness and applicability.
Critical weaknesses
The main concern is that the ablation studies do not fully isolate the contribution of the proposed planning mechanism. Removing node–operator planning changes both parent selection and operator expansion, while removing either graph also alters the associated operators' behavior. Although Tables 3 and 17 demonstrate the effectiveness of the overall framework, they do not clearly establish how much of the improvement comes from the individual mechanisms. The experimental evidence could also be strengthened in terms of statistical reliability and computational efficiency. Results are averaged over only three independent runs, with relatively small improvements over strong baselines in some settings. Moreover, relation maintenance accounts for 31.5% and 22.2% of total search time on constructive TSP and MKP-ACO, respectively.
Questions for authors
-
What motivates the operator-specific node values in Eq. (5)? How does the proposed approach compare with independently selecting nodes and operators under identical operators, prompts, and evaluation budgets?
-
Since removing either graph also changes the behavior of its associated operators, how can the authors isolate the contribution of relational information from that of the modified operators?
-
Why should action preferences on controller-generated states reliably reflect algorithm similarity during actual execution? How sensitive are the resulting neighborhoods to the choice of controller? Does this affect family assignments and downstream search performance?
-
Do the reported improvements remain consistent under matched wall-clock budgets and across additional independent runs, particularly in settings where the performance margins are small?
6 comments
Q3: PreferSim on controller-generated states
(1) Why controller-generated states. Comparing two heuristics on their own rollouts conflates decisions with state drift: one early disagreement changes every later state. Heuristic-independent states are therefore needed to compare preferences on equal footing, and preferences on them closely match those on actual execution states. In Fig. 7(c,d), top-1 / top-5 agreement between two heuristics is 94.9% / 100% on canonical states, versus 94.9% / 99.8% and 93.9% / 99.6% on the states visited by A and by B.
(2) Offline checks on constructive TSP archives (same , and number of states): real states compares canonical PreferSim with that computed on 1000 states actually visited by the archived programs; controller swap replaces the default nearest-neighbor (NN) controller with a random feasible controller or a mixture of the two.
| Archive | Real states: Spearman | Real states: top-5 Jaccard |
|---|---|---|
| EoH | 0.984 | 0.741 |
| MCTS-AHD | 0.971 | 0.829 |
| ReAL-AHD | 0.990 | 0.756 |
| Archive | Random: top-5 Jaccard | Random: family ARI | Mixed: top-5 Jaccard | Mixed: family ARI |
|---|---|---|---|---|
| EoH | 0.774 | 0.748 | 0.793 | 0.778 |
| MCTS-AHD | 0.782 | 0.681 | 0.806 | 0.610 |
| ReAL-AHD | 0.761 | 0.869 | 0.779 | 0.907 |
Canonical PreferSim reproduces the similarity ranking on real execution states (), and top-5 neighborhoods are largely preserved under a different controller (Jaccard 0.76–0.81). Family partitions vary more, but families are dynamic planning units that are periodically re-clustered (Sec. 3.2).
(3) Online checks on the full search (constructive TSP, reference gap ↓):
| Controller | N=50 | N=100 | N=200 |
|---|---|---|---|
| NN (default) | 7.55% | 9.40% | 11.30% |
| Random | 7.76% | 9.69% | 11.72% |
| Mixed | 7.77% | 9.56% | 10.93% |
No controller is systematically better, and all three stay ahead of the strongest baseline. For the ACO and GLS interfaces, the heuristic outputs its whole desirability matrix or vector independently of the controller, which only determines the compared rows and their feasibility masks.
Q4: Wall-clock budgets, maintenance cost and additional runs
(1) Wall-clock. Fig. 5 reports the total search time on TSP100 including all overhead: ReAL-AHD takes ≈204.6 min, versus ≈210.0 min for MCTS-AHD and ≈259.9 min for HiFo-Prompt, with the best final objective. As a stricter control, we converted ReAL-AHD's similarity computation time time into extra evaluations for each baseline.
TSP constructive (objective ↓)
| Method | Executor (s/eval) | Budget | N=50 | N=100 | N=200 |
|---|---|---|---|---|---|
| EoH | 5.32 | 500+719 | 6.251 | 8.615 | 11.970 |
| MCTS-AHD | 21.49 | 500+178 | 6.278 | 8.688 | 12.110 |
| HiFo-Prompt | 95.49 | 500+40 | 6.216 | 8.580 | 12.033 |
| Ours | – | 500 | 6.124 | 8.481 | 11.882 |
MKP-ACO (objective ↑)
| Method | Executor (s/eval) | Budget | N=100 | N=300 | N=500 |
|---|---|---|---|---|---|
| EoH | 6.63 | 500+221 | 22.523 | 64.258 | 106.478 |
| MCTS-AHD | 8.80 | 500+167 | 22.531 | 65.058 | 108.329 |
| HiFo-Prompt | 17.85 | 500+82 | 22.492 | 63.859 | 105.793 |
| Ours | – | 500 | 22.543 | 64.975 | 108.240 |
ReAL-AHD with 500 evaluations remains best at every TSP size; on MKP-ACO it is best at N=100 and within 0.13% of MCTS-AHD at N=300/500. We match executor time rather than total wall-clock because the latter also depends on LLM-API latency. This is also why the number of evaluations is the standard budget in LLM-based AHD.
(2) Maintenance cost. Preference capture accounts for 90.1% / 84.4% of the maintenance time on TSP / MKP-ACO, while graph and family updates take at most 0.24% of the search time (Table 4). On Online BPP, maintenance takes only 0.18%, yet ReAL-AHD is best in nearly all settings (Table 2), indicating that the gains do not rely on the extra computation.
(3) Additional runs. We report five independent runs (mean ± std) for ReAL-AHD, MCTS-AHD, and HiFo-Prompt on constructive TSP (objective ↓), Online BPP with (excess-bin ratio in %, ↓), and KP (objective ↑).
| Method | TSP50 | TSP100 | TSP200 |
|---|---|---|---|
| MCTS-AHD | 6.384 ± 0.113 | 8.707 ± 0.037 | 12.041 ± 0.152 |
| HiFo-Prompt | 6.296 ± 0.117 | 8.649 ± 0.081 | 12.124 ± 0.188 |
| Ours | 6.108 ± 0.025 | 8.453 ± 0.064 | 11.793 ± 0.150 |
| Method | BPP 5k | BPP 10k | BPP 100k |
|---|---|---|---|
| MCTS-AHD | 0.71 ± 0.02 | 0.45 ± 0.01 | 0.12 ± 0.00 |
| HiFo-Prompt | 0.83 ± 0.02 | 0.41 ± 0.00 | 0.03 ± 0.00 |
| Ours | 0.68 ± 0.03 | 0.34 ± 0.01 | 0.02 ± 0.00 |
| Method | KP50 | KP100 | KP200 | KP500 |
|---|---|---|---|---|
| MCTS-AHD | 20.163 ± 0.007 | 40.167 ± 0.003 | 58.018 ± 0.006 | 91.603 ± 0.008 |
| HiFo-Prompt | 20.159 ± 0.005 | 40.164 ± 0.006 | 58.021 ± 0.009 | 91.601 ± 0.006 |
| Ours | 20.171 ± 0.000 | 40.173 ± 0.002 | 58.032 ± 0.003 | 91.616 ± 0.004 |
ReAL-AHD has the best mean in all ten columns. On TSP, Welch's t-tests give in all six comparisons. On KP, all LLM-based methods are within 0.11% of the exact optimum (Table 1). We therefore present KP as evidence of cross-size stability rather than of a large margin.
We sincerely thank the reviewer for the careful assessment and for recognizing the relational representation, PreferSim, and the breadth of our evaluation. We address each concern below.
Q1: Operator-specific node values and independent selection
(1) Motivation. Prior AHD methods use one parent-selection rule for all operators. As with Q(s,a) versus V(s) in reinforcement learning, the value of a parent depends on the operator applied to it. Mutation and elite inspiration (m1, m2, e2) modify the parent or preserve its form, so the offspring is anchored to the parent's own fitness rv; lineage synthesis (s1) recombines the descendant lineage, whose quality is captured by Qv; cross-family bridging (s2) depends on the best foreign mechanism reachable from the node. For example (Table 20), node 124 has a poor objective (11.582) and would rarely be chosen by rv; s2 selects it for its foreign neighbors and produces node 299 (8.722), an ancestor of the later global best, node 386 (8.587).
(2) Controlled comparison. All rows use identical operators, prompts, and evaluation budget; only the selection rule differs. Shared: every operator uses the same operator-agnostic node value (Table 3). Independent: after a node is selected, a fixed number of operators are sampled independently, with probabilities equal to each operator's average usage frequency in the full method.
The operator-conditioned rule is best in every column and is the only one that is strong on both tasks: independent selection with Qv / rv comes close on TSP100 but not on BPP 10k, while the shared Qv / rv values are close on BPP but 1.45–2.23 points behind on TSP100.
Q2: Isolating relational information from the operators
We agree that the w/o derivation / w/o similarity rows of Table 3 measure the total effect of a relation: s1 / s2 keep their prompt templates, number of source programs, and invocation, but receive random inputs instead of relation-selected ones.
The contribution of the relational information itself is isolated by the variants in which the operators and their source-construction rules are untouched and only the relational information changes:
These changes cost 1.79–2.19 points on TSP100. Notably, a weaker similarity measure with intact operators (+1.99 to +2.19) costs as much as removing the similarity relation and randomizing s2 (+1.86), so the loss comes from the relational information rather than from the modified operator.