acceptodds
Under review as a conference paper at ICLR 2027

RouteRepair: Instance-Level Failure Diagnosis and Targeted Repair in LLM-Based Automated Heuristic Design for Routing Optimization

Abstract

Large language model (LLM)-based automated heuristic design usually ranks candidate programs according to an aggregate objective, even though a strong routing heuristic may fail repeatedly on a coherent subset of instances. We introduce RouteRepair, a fixed-backbone framework that retains the instance-wise performance profile of each competitive parent, constructs parent-specific failure, strength, and protection sets, and uses this evidence to define a bounded program repair. A Failure Diagnosis Expert produces a structured, risk-aware repair brief; a separate Targeted Repair Expert modifies only the designated scoring rule or edge-prior function. Parent and child programs are evaluated on matched instances, solver seeds, settings, and budgets, and both successful and unsuccessful interventions are recorded in outcome-aware memory. We evaluate five adapters covering constructive TSP, guided local search (GLS) for TSP, constructive CVRP, ant colony optimization (ACO) for TSP, and ACO for CVRP. RouteRepair-GLS reduces the mean TSP gap from 1.7476% to 0.7587%. Under identical 2-opt postprocessing, the constructive TSP rule achieves a 2.8805% mean gap. Constructive CVRP lowers average route cost by 1.91% relative to the Savings heuristic and by 2.06% relative to the strongest LLM-evolved baseline. The ACO priors also improve matched hand-designed priors and retain gains on larger transfer instances. These results support instance-level, evidence-constrained repair as a practical complement to aggregate evolutionary search.

Primary area:
optimization
Keywords:
Large Language Models, Automated Heuristic Design, Combinatorial Optimization, Hyper-Heuristics, Evolutionary Search

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_8kPvOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The submission used the wrong template. It should be desk rejected.

Critical strengths

The submission used the wrong template. It should be desk rejected.

Critical weaknesses

The submission used the wrong template. It should be desk rejected.

Questions for authors

The submission used the wrong template. It should be desk rejected.

Reviewer_7PZZOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Targeting the limitation that LLM-based automated heuristic design (AHD) ranks candidates only by an aggregate mean gap, thereby masking the repeated failure of a competitive rule on a coherent subset of instances, this paper proposes RouteRepair, a fixed-backbone framework. It retains the instance-wise performance profile of a competitive parent, builds a failure set F, a strength set S, and a protection set A; an independent Failure Diagnosis Expert produces a frozen, structured repair brief, after which a separate Targeted Repair Expert modifies only the designated scoring rule or edge-prior function. Under matched conditions, the intervention is accepted using normalized failure recovery RFR_F and one-sided collateral degradation CAC_A. The method is evaluated across five adapters (constructive TSP/CVRP, TSP-GLS, TSP-ACO, CVRP-ACO), reporting within-scale results, transfer, ablations, and instance-level win/loss distributions.

Critical strengths
  1. Well-motivated problem. The paper addresses a genuine pain point—a scalar mean cannot distinguish a uniformly mediocre rule from a competitive rule that repeatedly fails on a localized region.
Critical weaknesses
  1. No independent repeated runs or statistical significance tests, so gains cannot be separated from random noise. The main ablation is based on a single controlled seed (§4.4: "one controlled seed… rather than a claim about variance across independent campaigns"). It therefore remains unclear whether the reported gap/cost improvements stem from the method itself or from LLM sampling and evolutionary-path randomness.
  2. R_F and C_A are defined as acceptance gates but their measured values and contribution are never reported. Although normalized recovery RFR_F and one-sided collateral degradation CAC_A are defined in Eqs. (5)–(6) with thresholds RF>=0.05R_F >= 0.05, CA<=0.02C_A <= 0.02, neither the main text nor Tables report the measured RFR_F and CAC_A per candidate, their distribution, or the fraction meeting the threshold (verified repairs). The decomposition of how verified repairs contribute to final aggregate performance is also absent, so the actual enforcement of the acceptance gate—and whether repair genuinely drives the gains—is not verifiable.
Questions for authors
  1. Could the authors provide multiple independent search campaigns under different random seeds, report mean±standard deviation and paired significance tests, to demonstrate that the gains are robust to LLM sampling and evolutionary-path randomness rather than reflecting one favorable run?
  2. Could the authors report the measured R_F and C_A for each repair candidate, the fraction satisfying R_F >= 0.05 and C_A <= 0.02, and decompose how verified targeted repairs contribute to the final aggregate gap/cost improvement, as opposed to ordinary population survivors?
Reviewer_zBp6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers LLM-based automated heuristic design for routing problems. The authors argue that the usual pipeline, which ranks candidate heuristics by their mean gap over all instances, selects heuristics that are just good on average, but not on a group of structurally similar instances. They propose a new approach, RouteRepair, which keeps the per-instance results of each parent heuristic. It splits the instances into those where the parent does worst and all the others (failure set versus protection set). With one LLM prompt, the failures are diagnosed and a repair instruction is generated. With the second prompt, the single scoring function or the edge-prior matrix inside the fixed solver is modified. Importantly, a child is considered a verified repair only if it improves on the failure set exceeding a certain threshold, and its loss on the protection set stays below a certain threshold. The approach is evaluated on five fixed solvers and compared against classical heuristics and adapted LLM-evolved baselines. It uses transfer tests and one ablation.

Critical strengths

The evaluation protocol looks quite careful: parent and child are run on the same instances, seeds and budgets. Acceptance is decided by execution. The authors report also where their method is not the best, which puts some trust in the positive results.

The protection-set check looks like a good idea that might be applicable in other settings, like program repair loops, where candidates are scored on several instances.

Critical weaknesses

The main claim is that instance-level repair gives better heuristics than evolution (aggregate score). However, I do not see an experiment that isolates this claim. The "w/o repair" row of the ablation seems to use only the eight initial candidates. So this compares 176 LLM calls against 8, not repair against aggregate-score evolution, same budget. The "w/o failure attribution" row has the same number of calls, but it is not specified what that variant does. So it is unclear whether it is the budget-matched baseline. The paper also lacks any statistics on the repair mechanism itself. How many children pass the two thresholds? Or how large are the gains on the failure set and the losses on the protection set? It would be interesting to know how much of the final heuristic comes from verified repairs and not from children that stayed in the population based on the aggregate score alone.

BTW, the two reported results for the starting point of the ablation seem to be inconsistent. Section 4.2 has the best initial candidate with a gap under 1%, but Table 11 gives a much larger value. Are these different runs?

Questions for authors

See above.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.