acceptodds
Under review as a conference paper at ICLR 2027

ReAL-AHD: Planning over Relational Algorithm Landscape for LLM-based Automatic Heuristic Design

Abstract

Large Language Models (LLMs) have enabled a new paradigm of Automatic Heuristic Design (AHD), in which heuristics for combinatorial optimization problems (COPs) are generated as executable programs and improved through performance feedback. Existing methods either compress the search history into an elite population, discarding the relations produced along the way, or impose a single structure that captures only one view of the algorithm space. Moreover, they underutilize this history, neither adaptively allocating evaluations across families of similar algorithms nor jointly selecting parents and operators. We propose ReAL-AHD, which represents the discovered algorithm space as a Relational Algorithm Landscape with two complementary relations: a derivation graph that records lineages and supports credit assignment, and a similarity graph that groups heuristics into dynamic algorithm families based on PreferSim, which compares action preferences under aligned decision states. On this landscape, hierarchical graph planning turns accumulated history into the explicit basis for search decisions: family planning allocates the evaluation budget across families, node–operator planning jointly selects the parent node and the operator of each expansion, and graph-aware memory reuses relevant past outcomes. Across five COPs and three heuristic paradigms, ReAL-AHD consistently outperforms state-of-the-art LLM-based AHD methods and converts the evaluation budget into improvement efficiently.

Primary area:
optimization
Keywords:
Large Language Models, Automated Heuristic Design, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6KWzOpenReview ↗
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
  1. 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?

  2. 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?

  3. 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?

  4. 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

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)Q(s,a) versus V(s)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 rvr_v; lineage synthesis (s1) recombines the descendant lineage, whose quality is captured by QvQ_v; 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 rvr_v; 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.

Node ruleOperatorsTSP100TSP200BPP 5kBPP 10k
Vo(v)V_o(v) (ours)coupled9.40%11.30%0.70%0.35%
randomshared12.24%13.49%0.97%0.67%
randomindependent11.93%12.89%0.93%0.60%
QvQ_vshared11.63%12.46%0.78%0.38%
QvQ_vindependent10.04%11.44%0.89%0.60%
rvr_vshared10.85%12.17%0.73%0.44%
rvr_vindependent9.93%12.12%0.87%0.68%

The operator-conditioned rule is best in every column and is the only one that is strong on both tasks: independent selection with QvQ_v / rvr_v comes close on TSP100 but not on BPP 10k, while the shared QvQ_v / rvr_v 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:

Change (operators untouched)TSP100TSP200BPP 5kBPP 10k
ReAL-AHD9.40%11.30%0.70%0.35%
Similarity measure: PreferSim → BehaveSim11.39%12.68%0.83%0.50%
Similarity measure: PreferSim → CodeBLEU11.59%13.40%0.98%0.49%
Families: dynamic → static11.19%12.47%0.80%0.48%

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.

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 MM, kk 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.

ArchiveReal states: Spearman ρ\rhoReal states: top-5 Jaccard
EoH0.9840.741
MCTS-AHD0.9710.829
ReAL-AHD0.9900.756
ArchiveRandom: top-5 JaccardRandom: family ARIMixed: top-5 JaccardMixed: family ARI
EoH0.7740.7480.7930.778
MCTS-AHD0.7820.6810.8060.610
ReAL-AHD0.7610.8690.7790.907

Canonical PreferSim reproduces the similarity ranking on real execution states (ρ≥0.971\rho \ge 0.971), 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 ↓):

ControllerN=50N=100N=200
NN (default)7.55%9.40%11.30%
Random7.76%9.69%11.72%
Mixed7.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 ↓)

MethodExecutor (s/eval)BudgetN=50N=100N=200
EoH5.32500+7196.2518.61511.970
MCTS-AHD21.49500+1786.2788.68812.110
HiFo-Prompt95.49500+406.2168.58012.033
Ours–5006.1248.48111.882

MKP-ACO (objective ↑)

MethodExecutor (s/eval)BudgetN=100N=300N=500
EoH6.63500+22122.52364.258106.478
MCTS-AHD8.80500+16722.53165.058108.329
HiFo-Prompt17.85500+8222.49263.859105.793
Ours–50022.54364.975108.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 C=100C=100 (excess-bin ratio in %, ↓), and KP (objective ↑).

MethodTSP50TSP100TSP200
MCTS-AHD6.384 ± 0.1138.707 ± 0.03712.041 ± 0.152
HiFo-Prompt6.296 ± 0.1178.649 ± 0.08112.124 ± 0.188
Ours6.108 ± 0.0258.453 ± 0.06411.793 ± 0.150
MethodBPP 5kBPP 10kBPP 100k
MCTS-AHD0.71 ± 0.020.45 ± 0.010.12 ± 0.00
HiFo-Prompt0.83 ± 0.020.41 ± 0.000.03 ± 0.00
Ours0.68 ± 0.030.34 ± 0.010.02 ± 0.00
MethodKP50KP100KP200KP500
MCTS-AHD20.163 ± 0.00740.167 ± 0.00358.018 ± 0.00691.603 ± 0.008
HiFo-Prompt20.159 ± 0.00540.164 ± 0.00658.021 ± 0.00991.601 ± 0.006
Ours20.171 ± 0.00040.173 ± 0.00258.032 ± 0.00391.616 ± 0.004

ReAL-AHD has the best mean in all ten columns. On TSP, Welch's t-tests give p<0.05p<0.05 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.

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

This paper studies LLM-based Automatic Heuristic Design (AHD) for combinatorial optimization problems (COPs), where an LLM generates executable heuristic programs and an evaluator returns verifiable fitness under a fixed evaluation budget. The authors observe that existing population-based methods (EoH, ReEvo, HSEvo, HiFo-Prompt) discard derivation relations when offspring are replaced, while structure-based methods model only one view of the algorithm space (lineage in MCTS-AHD, similarity niches in PartEvo), and that parents and operators are selected separately without family-aware budget allocation.
ReAL-AHD organizes all discovered heuristics into a dual-relation "relational algorithm landscape": a derivation DAG that records lineages and a recursive lineage value Q_v for credit assignment, and an undirected similarity graph built on the proposed PreferSim measure, which compares top-k action preferences of two heuristics on controller-generated aligned decision states rather than code or solution trajectories; spectral clustering partitions the graph into dynamic algorithm families. On this landscape, hierarchical graph planning allocates the evaluation budget across families with a UCB-inspired score and jointly selects a node and an operator under operator-conditioned node values (r_v for mutation/elite inspiration, Q_v for lineage synthesis, best foreign neighbor for cross-family bridging), while graph-aware memory retrieves EMA-updated positive lessons and negative pitfalls for each expansion.
Experiments cover five COPs across three paradigms with 500 evaluations over three runs, comparing against handcrafted rules, NCO methods, and eight LLM-AHD baselines, with OOD tests on TSPLIB/CVRPLIB and a second backbone (GPT-5-nano). ReAL-AHD reports the best objective among LLM-AHD methods on most settings.

Critical strengths
  1. Sound motivation backed by an empirical observation, with a method that directly answers it. The paper first documents, on the EoH and MCTS-AHD archives, that derivation distance correlates only weakly with CodeBLEU and BehaveSim dissimilarity, and that BehaveSim contains "false diversity" pairs. This justifies the dual view it proposes: a derivation graph for lineage/credit assignment plus a PreferSim similarity graph built on aligned action preferences, rather than reusing code- or trajectory-based similarity. The proposed dual-graph landscape and hierarchical planning directly follow from the diagnosed gaps.
  2. Broad and multi-setting empirical evaluation. ReAL-AHD is tested on five COPs (TSP, CVRP, KP, MKP, online/offline BPP) across three paradigms (constructive, ACO, GLS), with OOD evaluation on TSPLIB/CVRPLIB, a second LLM backbone (GPT-5-nano), a dedicated CALM(API, w/o GRPO) comparison, and component ablations.
Critical weaknesses
  1. PreferSim's capture cost is high and the reference setup must be re-adapted per problem. PreferSim requires a fixed reference problem set (M=8), controller-generated canonical states, and a task-specific adapter for each interface type; the reported capture cost reaches ~16.1 s per candidate on the TSP selector interface and relation maintenance consumes 31.5% of total search time on constructive TSP. No evidence shows that reference states, preference depth, or adapters transfer across problems, so the method currently incurs per-problem adaptation and an upfront execution cost that the token-based efficiency analysis does not fully account for.
  2. The TSP experimental protocol looks inconsistent with the original baseline reports and deserves reconciliation. On small scales (TSP N=50), all LLM-AHD methods show large reference gaps (EoH 13.35%, ReEvo 10.57%, HiFo-Prompt 9.28%, Ours 7.55%; Table 1), which are substantially higher than the gaps reported for these same baselines in their original papers. It is unclear whether this comes from evolving on N=100 and directly applying to N=50 without re-search, a different instance generator, reference solution, or run/evaluator setting, so the headline ranking may reflect protocol differences rather than method quality.
Questions for authors
  1. Why are the TSP50/100 gaps for EoH, ReEvo, HiFo-Prompt, and MCTS-AHD much larger than in their original papers?
3 comments

We thank the reviewer for the accurate summary of our motivation and dual-relation design, and for the constructive comments. We address each concern below.

Q1 & W2: TSP gaps compared with the original papers

(1) The near-zero gaps are GLS results. TSP can be solved under a constructive or a GLS framework. The near-zero TSP gaps in the EoH and ReEvo papers are obtained with GLS, and our GLS experiment reproduces them in Table 15. Table 1 instead evaluates step-by-step construction, for which prior papers report the same range as ours:

Gap (%) on TSP50 / 100 / 200PublishedOurs (Table 1)
Greedy (nearest neighbor)22.62 / 24.94 / 26.29 (MCTS-AHD, Tab. 1)22.15 / 24.93 / 26.34
EoH12.82 / 15.36 / 16.66 (HiFo-Prompt, Tab. 1)13.35 / 15.44 / 17.41
ReEvo10.24 / 12.58 / 14.89 (HiFo-Prompt, Tab. 1)10.57 / 12.52 / 14.53
MCTS-AHD9.69 / 11.79 / 13.71 (MCTS-AHD, Tab. 1); 10.64 / 12.52 / 13.51 (HiFo-Prompt, Tab. 1)10.76 / 12.39 / 13.78
HiFo-Prompt6.63 / 8.58 / 8.88 (HiFo-Prompt, Tab. 1)9.28 / 11.27 / 12.62

(2) Our protocol is the standard one for LLM-based AHD.

  • Scale: heuristics are evolved on TSP100 instances and applied to TSP50/100/200 without re-search, identically for all methods.
  • Instances and reference: coordinates are sampled uniformly from [0,1]2[0,1]^2 [1][2], and the reference is LKH-3.
  • Runs: all methods are evaluated over three independent runs using the same evaluator, test sets, LLM, and budget, so the ranking reflects method differences rather than protocol differences.

(3) Released baseline programs. As a further check, we ran the constructive TSP programs released in the baselines' official repositories with our evaluator and test sets:

MethodTSP50 Obj.TSP50 GapTSP100 Obj.TSP100 GapTSP200 Obj.TSP200 Gap
ReEvo6.27610.25%8.64511.51%12.04912.86%
MCTS-AHD6.1808.49%8.5229.91%11.89311.38%
HiFo-Prompt6.0496.24%8.3758.02%11.7169.72%
Ours (single)6.1397.78%8.4759.31%11.82810.77%

The released programs match the performance reported in their original papers, confirming the consistency of our evaluator. The only method whose original report differs notably from ours is HiFo-Prompt. Its original program takes 1,843 s / 16,099 s on 100 TSP100 / TSP200 instances, while we apply a 120 s per-candidate evaluation limit to all methods, so such costly programs are not accepted during search.

[1] Kool, W., van Hoof, H., and Welling, M. Attention, learn to solve routing problems! In International Conference on Learning Representations (ICLR), 2019.

[2] Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., and Zhang, Q. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.

W1: Cost of PreferSim and per-problem adaptation

The cost is fully counted, and it pays off. Beyond the token analysis, Fig. 5 reports total wall-clock with all overhead: ReAL-AHD achieves the best objective with a moderate runtime. Cheaper similarity measures sacrifice solution quality: replacing PreferSim with CodeBLEU or BehaveSim degrades the TSP100 gap from 9.40% to 11.59% and 11.39%, respectively (Table 3).

Adaptation is light. One shared configuration (M=8M=8, k=5k=5) is used in all task settings without per-problem tuning, and the reference problems come from the evolution split, so no extra data is needed. There are only two adapter types, score-based and selector-based (Appendix D.3). Adapting to a new task only requires a short deterministic controller (e.g., nearest-neighbor for TSP, best-fit for BPP), and the controller matters little.

Thank you for authors' response, but I will keep my original weak acceptance score.

Thank you for your positive feedback and for taking the time to review. We sincerely appreciate your support of our work.

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

The paper introduces ReAL-AHD, which organizes past heuristics using derivation and similarity graphs. It uses PreferSim to group similar heuristics and decide where to spend the search budget, which parents to select, and which past experiences to reuse. Across five optimization problems and three heuristic settings, it outperforms existing LLM-based methods.

Critical strengths
  1. Complementary relational modeling: Combining derivation and action-level similarity provides a sensible way to preserve and exploit more search history than other methods.
  2. Broad empirical validation: The method is evaluated across five optimization problems, three heuristic paradigms. It also includes ablation study and efficiency analysis.
Critical weaknesses
  1. Unfair compute comparison: PreferSim requires substantial additional heuristic executions that are excluded from the evaluation budget. It uses 31.5% of total search time. There is no matched wall-clock or executor-compute comparison. It is unclear whether the gains result from better search organization or additional computation.
  2. Insufficient statistical and reproducibility evidence: The performance margins are small. Most results and ablations use only three runs without variance or significance tests. The code is inconsistent with the reported ablations and similarity thresholds.
Questions for authors
  1. Do the gains remain under a matched wall-clock or executor-compute budget? PreferSim’s additional heuristic executions should be included.
  2. Please report confidence intervals for the main results and ablations, especially when improvements are small.
  3. Were the similarity thresholds and graph hyperparameters selected on a separate validation set?
  4. Why do some reported thresholds and ablations differ from the code?
  5. What are the test-time runtimes of the discovered constructive heuristics (especially those using rollouts, dynamic programming, or local search)?
6 comments

We sincerely thank the reviewer for the careful assessment. We address each concern below.

Q1 & W1: Do the gains hold when PreferSim's executions are included?

(1) Wall-clock. In total search time with all maintenance included (Fig. 5), ReAL-AHD takes ≈204.6 min, less than MCTS-AHD (≈210.0 min) and HiFo-Prompt (≈259.9 min), while reaching the best objective of all methods.

(2) Matched executor compute. We convert ReAL-AHD's similarity computation time (Table 4: 3,829 s on constructive TSP, 1,468 s on MKP-ACO) into Δ\Delta extra evaluations per baseline, at that baseline's own mean executor time per evaluation, and rerun it with budget 500+Δ500+\Delta.

TSP constructive (objective ↓)

MethodExecutor (s/eval)BudgetN=50N=100N=200
EoH5.32500+7196.2518.61511.970
MCTS-AHD21.49500+1786.2788.68812.110
HiFo-Prompt95.49500+406.2168.58012.033
Ours–5006.1248.48111.882

MKP-ACO (objective ↑)

MethodExecutor (s/eval)BudgetN=100N=300N=500
EoH6.63500+22122.52364.258106.478
MCTS-AHD8.80500+16722.53165.058108.329
HiFo-Prompt17.85500+8222.49263.859105.793
Ours–50022.54364.975108.240

On TSP, ReAL-AHD stays best at every size although the baselines receive 8%–144% more evaluations; on MKP-ACO, it is best at N=100 and within 0.13% of MCTS-AHD at N=300/500. This matching favors the baselines, whose extra evaluations also bring uncharged LLM generations (e.g., 36% more tokens for MCTS-AHD on MKP-ACO). The evaluation budget is the standard protocol in LLM-based AHD, and it is difficult to be fair under every criterion at once.

(3) Organization, not compute, drives the gain. PreferSim never generates or scores candidates; it only records the preferences of evaluated programs. On Online BPP, maintenance takes only 0.18% of search time (Table 4), yet ReAL-AHD is best in nearly all settings (Table 2); and replacing PreferSim with BehaveSim, which also executes the heuristics, worsens the gap from 9.40% to 11.39% (Table 3).

Q2 & W2: Statistical evidence

(1) Margins. On constructive TSP, ReAL-AHD reduces the gap over the strongest baseline by 1.73 / 1.87 / 1.32 points (Table 1), a relative reduction of 18.6% / 16.6% / 10.5%. This exceeds the spacing between the best and second-best baselines (1.29 / 0.99 / 1.16). Its standard deviation across runs is the smallest at TSP50 and the second smallest at TSP100/200.

(2) Confidence intervals. We extended ReAL-AHD, the two closest baselines, and the ablation variants to five independent runs. The tables report 95% Student's t confidence intervals (TSP: objective ↓; Online BPP with C=100C=100: excess-bin ratio ↓).

MethodTSP50TSP100TSP200BPP 5kBPP 10kBPP 100k
MCTS-AHD[6.243, 6.525][8.661, 8.753][11.852, 12.230][0.69%, 0.74%][0.43%, 0.46%][0.12%, 0.12%]
HiFo-Prompt[6.151, 6.441][8.548, 8.750][11.890, 12.358][0.81%, 0.84%][0.41%, 0.41%][0.03%, 0.03%]
Ours[6.077, 6.139][8.374, 8.532][11.606, 11.980][0.64%, 0.71%][0.33%, 0.35%][0.02%, 0.02%]
VariantTSP50TSP100TSP200BPP 5kBPP 10kBPP 100k
ReAL-AHD[6.077, 6.139][8.374, 8.532][11.606, 11.980][0.64%, 0.71%][0.33%, 0.35%][0.02%, 0.02%]
w/o derivation[6.180, 6.294][8.577, 8.751][12.005, 12.219][0.79%, 0.89%][0.44%, 0.48%][0.05%, 0.07%]
w/o similarity[6.260, 6.382][8.643, 8.825][12.070, 12.294][0.79%, 0.91%][0.50%, 0.56%][0.06%, 0.09%]
w/o family planning[6.102, 6.212][8.601, 8.773][12.009, 12.221][0.75%, 0.85%][0.42%, 0.46%][0.04%, 0.07%]
w/o node–operator planning[6.277, 6.404][8.667, 8.856][12.090, 12.321][0.88%, 1.02%][0.62%, 0.70%][0.07%, 0.11%]

Against the baselines, ReAL-AHD's intervals do not overlap with either baseline on TSP50,100, BPP 10k,100k, and are lower with a slight overlap on TSP200 and BPP 5k. Welch's t-tests confirm statistically significant gains (p<0.05p<0.05) across all six TSP comparisons (against HiFo-Prompt p=0.021/0.003/0.016p=0.021/0.003/0.016, against MCTS-AHD p=0.005/0.0002/0.032p=0.005/0.0002/0.032). Against the ablations, its interval lies entirely below the variant's in 23 of 24 cells.

(3) KP. All LLM-based methods are within 0.11% of the reference (Table 1), so differences are necessarily small. ReAL-AHD has the best mean at every size (mean ± std, ↑):

MethodKP50KP100KP200KP500
MCTS-AHD20.163 ± 0.00740.167 ± 0.00358.018 ± 0.00691.603 ± 0.008
HiFo-Prompt20.159 ± 0.00540.164 ± 0.00658.021 ± 0.00991.601 ± 0.006
Ours20.171 ± 0.00040.173 ± 0.00258.032 ± 0.00391.616 ± 0.004

Q3: How were τ\tau and knnk_{\mathrm{nn}} chosen?

They were chosen based on the similarity distribution and graph sparsity on the evolution set, without tuning on a separate validation set or touching the test set. As a concrete case, over the 93,096 heuristic pairs of a ReAL-AHD archive, PreferSim has a median of 0.636, a 75th percentile of 0.797, and a 95th percentile of 0.906. Hence τ=0.8\tau=0.8 retains about the strongest quarter of the relations, which keeps the graph sparse, while knn=3k_{\mathrm{nn}}=3 keeps the remaining nodes connected.

The conclusions do not hinge on these values. When varying τ\tau from 0.7 to 0.9 and knnk_{\mathrm{nn}} from 1 to 5 (Table 18), all five configurations outperform the strongest baseline (HiFo-Prompt) on TSP100 and TSP200, and outperform CodeBLEU and BehaveSim on all four ablation metrics.

Q4 & W2: Consistency between code and paper

We apologize for the confusion. The submitted code is a release of the main configuration. The ablation variants, including the measure-specific thresholds, were run from separate configuration files that were not merged into that release. We have updated the supplementary material to include the configuration and reproduction script of every ablation variant.

Q5: Test-time runtime of the discovered heuristics

All methods search under the same 120 s time limit per candidate evaluation, so overly slow programs are discarded during search. The function interface (Appendix B) is also identical, so rollouts, DP on small subproblems, and local refinement are available to every method rather than specific to ReAL-AHD.

Each cell is time / gap, where time is the total over the test set for the synthetic sizes and the time per instance for TSPLIB and CVRPLIB.

TSP constructive

MethodN=50N=100N=200TSPLIB
EoH1.44s / 13.35%8.19s / 15.44%61.40s / 17.41%1.82s / 17.52%
ReEvo1.95s / 10.57%9.43s / 12.52%64.18s / 14.53%0.36s / 15.49%
HSEvo10.59s / 11.87%137.30s / 13.80%1970.23s / 15.38%106.65s / 16.37%
HiFo-Prompt56.96s / 9.28%254.75s / 11.27%4655.57s / 12.62%449.42s / 12.53%
MCTS-AHD9.95s / 10.76%94.94s / 12.39%1340.93s / 13.78%95.81s / 13.64%
PartEvo5.04s / 10.78%31.55s / 12.26%299.13s / 14.09%9.97s / 18.97%
OpenEvolve53.77s / 10.64%184.37s / 13.16%3595.83s / 15.57%138.86s / 19.30%
Ours3.60s / 7.55%28.60s / 9.40%254.73s / 11.30%11.62s / 12.01%

CVRP constructive

MethodN=50N=100N=200CVRPLIB
EoH4.54s / 16.40%9.45s / 19.08%176.47s / 19.65%140.71s / 33.98%
ReEvo1.91s / 6.84%5.31s / 11.11%15.86s / 13.16%2.39s / 32.04%
HSEvo2.60s / 5.52%17.54s / 5.64%128.82s / 4.97%278.40s / 18.34%
HiFo-Prompt0.99s / 11.57%2.85s / 12.57%8.98s / 11.81%14.34s / 29.61%
MCTS-AHD1.06s / 14.34%8.64s / 17.02%71.06s / 15.68%46.74s / 31.65%
PartEvo4.52s / 3.14%30.74s / 2.71%248.86s / 1.78%254.71s / 18.87%
OpenEvolve15.77s / 3.06%208.67s / 3.02%1217.97s / 3.01%1054.47s / 20.46%
Ours1.54s / 2.21%13.77s / 2.05%135.42s / 1.47%141.79s / 18.11%

ReAL-AHD attains the lowest gap in every column at a moderate runtime. On TSP, it is 9–39× faster than the strongest baseline HiFo-Prompt and 3–8× faster than MCTS-AHD. On CVRP, it is 1.8–2.9× faster than PartEvo and 7–15× faster than OpenEvolve, the two closest baselines in quality on the synthetic sets. Therefore, although the heuristics discovered by ReAL-AHD can use such mechanisms (Appendix F), their quality gains are not obtained through heavier test-time computation than the baselines.

Reviewer_34BsOpenReview ↗

Response from Reviewer 34Bs

Thank you for the detailed response and the new experiments. Overall, the response improves my view of the paper. However, there are some open questions below. Thus, I will keep my score for now.

  1. Matched compute (Q1). On MKP-ACO, MCTS-AHD with the matched budget is better than ReAL-AHD at N = 300 and N = 500. This suggests that the advantage of ReAL-AHD can be explained by the extra computation rather than by better search organization. On Online BPP, the low maintenance cost does not show that the gain comes from PreferSim-based organization. In the code, BPP similarity comes from just 8 rankings on the same set of bins. That's too little to tell us the gain comes from the similarity structure.

  2. Statistics (Q2). Some of the new results are hard to understand:

    • Zero-width intervals. Several 95% intervals have zero width, e.g. MCTS-AHD at BPP 100k [0.12%, 0.12%], HiFo-Prompt at BPP 10k [0.41%, 0.41%], and ReAL-AHD at BPP 100k [0.02%, 0.02%]. ReAL-AHD also has std 0.000 on KP50. Five independent LLM-based runs should not give identical results.
    • Ablations at TSP100. If the 5 runs include the original 3 runs, the two new runs of ReAL-AHD are better than its original mean, while the two new runs of every ablation variant are clearly worse than their original means. This systematic shift does not appear in the BPP ablations. Please provide per-run values and confirm that all ablation runs used the same code and configuration.
  3. Code vs. paper (Q4). The released ablation settings do not exactly match the descriptions in the paper:

    • "w/o node–operator planning" is described as full operator expansion after random node selection. The code samples operators with replacement, so some operators can be skipped or repeated.
    • "w/o derivation" also replaces all UCB node selection with rank sampling, not only the s1 path.
    • "w/o similarity" also disables families, family planning, and pruning.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.