acceptodds
Desk rejected at ICLR 2027

Evolutionary AI Agents for Automated Combinatorial Optimization

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Recent advances in large language models (LLMs) and AI agents have opened up new opportunities for automated combinatorial optimization. However, existing LLM/agent-based automated algorithm/heuristic design methods heavily rely on users to manually configure problem-dependent tools, heuristics, and iterative pipelines. To go beyond such design-level automation, we introduce Automated Problem Solving (APS), which enables AI agents to autonomously discover and organize the entire problem-solving process for combinatorial optimization. We further propose EvoAge, a self-evolving agentic framework for APS that explores, composes, and evolves reusable skills via evolutionary optimization. Inspired by natural evolution, EvoAge treats problem-solving trajectories, rather than individual heuristics or algorithms, as evolvable units and employs evolutionary search to automatically discover novel problem-solving strategies. It further distills successful experience into reusable skills and continuously evolves its skill library, enabling capabilities to accumulate, adapt, and expand across diverse tasks in an open-ended environment. Experiments across four classes of combinatorial optimization problems show that EvoAge obtains skills that can autonomously solve them without any human design or intervention and consistently outperforms state-of-the-art LLM/agent-based methods, demonstrating the effectiveness and huge potential of APS as a new paradigm for combinatorial optimization.

Primary area:
optimization
Keywords:
AI Agent, Combinatorial Optimization, Evolutionary Optimization, Automated Problem Solving, Agentic Skill

Reviews

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

This paper proposes EvoAge, an evolutionary framework for automated problem solving (APS) in combinatorial optimization that extends automated heuristic design beyond individual heuristics to the organization and optimization of complete problem-solving workflows. EvoAge jointly evolves instance-specific plans and a persistent skill library: plan evolution optimizes the composition, ordering, parameters, and control flow of operations, while skill evolution extracts and refines reusable experience across instances, with paired validation to assess skill modifications. The resulting workflows can express conditional operation selection, execution order, and stopping rules. Experiments on four combinatorial optimization problem families show that EvoAge achieves competitive performance across the evaluated instances.

Critical strengths
  1. This paper proposes a meaningful extension from a single heuristic design to a complete problem-solving workflow design. In complex combinatorial optimization, solution quality can depend not only on the choice of an individual operator but also on how different operations are composed and when they are executed. EvoAge explicitly optimizes these decisions. This broader design space may also help explain its reported advantages over AHD baselines.

  2. The final output skills include conditional operation selection, execution sequence, and stopping rules, making it reasonably checkable and reusable.

Critical weaknesses
  1. Insufficiently established novelty relative to existing agent-based AHD and self-evolving agents. Although APS is a meaningful framing, the paper does not clearly establish the technical boundary between EvoAge and existing approaches that combine tool-using agents, iterative plan refinement, persistent memory, and experience reuse. In particular, the paper needs to clarify which capabilities arise from a fundamentally new method rather than from integrating these mechanisms into a unified framework. Without a sharper comparison and clearer identification of the methodological novelty, the central contribution remains insufficiently established.

  2. Insufficient ablation studies and incomplete accounting of computational costs. The experiments do not adequately isolate the contributions of plan evolution, skill evolution, persistent memory, and skill validation. Consequently, it is difficult to determine whether the reported gains come from the proposed dual-evolution mechanism, accumulated experience, or simply a more flexible workflow with access to multiple operations. In addition, the reported per-instance execution budget does not capture the cost of constructing and refining the skill library. Without matched-budget ablations and a clear accounting of training and validation costs, the paper cannot establish the effectiveness of its central mechanisms or support broader conclusions about efficiency.

Questions for authors
  1. What are the essential algorithmic differences between EvoAge and existing self-evolving agent frameworks that already support iterative planning, tool use, and persistent experience? Which specific capabilities or mechanisms constitute the methodological novelty of EvoAge, rather than an integration of existing components?

  2. Under matched LLM-call and execution budgets, how much performance improvement is attributable to plan evolution and skill evolution individually? In particular, do the authors have ablation results comparing the full framework against variants without skill evolution, without plan evolution, with a fixed skill library, and without skill validation? Without such evidence, it is difficult to determine whether the proposed mechanisms are responsible for the reported gains.

  3. What are the total computational costs of building and refining the skill library, including LLM calls or tokens, plan evaluations, validation runs, and wall-clock time? Are these costs included in the reported budgets, and are the total computational resources allocated to EvoAge and the AHD baselines comparable? A complete accounting is important for assessing both the fairness of the performance comparisons and the practical efficiency of the proposed framework.

  4. Do the compared AHD and agent-based baselines have access to the same underlying operations and solver tools as EvoAge? If not, how much of the performance difference can be attributed to workflow evolution rather than to EvoAge's broader set of available operations? A comparison against a non-evolving planner using the same toolbox would help isolate the contribution of the proposed evolution mechanisms.

  5. The presented skills appear to primarily combine and coordinate existing optimization techniques, rather than introduce fundamentally new solving operators or tools. How do the authors distinguish workflow-level innovation from the autonomous discovery of new problem-solving capabilities? More specifically, what evidence supports the claims about expanding beyond predefined capabilities, given that the framework appears to operate within an available set of operations and tools?

8 comments
AuthorsOpenReview ↗

Response to Paper Summary and Critical Strengths

Thank you for recognizing workflow-level APS and interpretable Skills. We clarify below the algorithmic differences between EvoAge and agent-based AHD and self-evolving agents. We have justified the effects of Plan and Skill evolution through additional ablation studies, with execution trajectories as the evidence used by Plan evolution. The solver-only versus offline cost accounting has also reported in appendix. The new controlled comparisons in the ablation study directly test the value of learned Skills under unchanged tool access.


Thank you for recognizing workflow-level optimization and the interpretable decision rules encoded in the learned Skills.

AuthorsOpenReview ↗

Response to Critical Weaknesses

Thanks for your comments.

W1: The key distinction lies in the research objective, optimization target, and evolutionary mechanism, rather than simply integrating existing agent components. Agent-based AHD methods, such as RefineEvo and PathWise, primarily aim to improve heuristic design through planning, feedback, and experience. In contrast, APS aims to autonomously solve optimization problems by discovering and optimizing complete problem-solving processes, rather than treating heuristic generation as the final objective.

Compared with existing self-evolving agents, EvoAge introduces a coupled two-level evolutionary mechanism specifically for combinatorial optimization: (1) Plan–Trajectory Evolution, where LLM-driven agents analyze execution trajectories and autonomously guide crossover, mutation, and refinement of executable solving workflows; and (2) Skill Evolution, where successful cross-instance experience is distilled into reusable conditional Skills, whose updates are selected through paired, outcome-based validation. The methodological contribution is this explicit evolutionary optimization of both problem-solving processes and persistent solving capabilities, connecting instance-level strategy discovery with cross-instance knowledge accumulation. We will clarify these distinctions in Related Work and Methodology.


W2: On 12 common TSP instances with Qwen3.6-27B (four each at 100, 500, and 1,000 cities), removing Plan evolution and Skill learning increases mean tour length by 3.20% and 2.80% relative to Full. No-Plan-Evolution still constructs a Plan but removes parent selection, crossover, and mutation; Skill learning remains enabled in that settings.

Separately, in Qwen3.8-27B controlled public-benchmark tests, the full learned library improves TSPLIB feasibility from 60/77 to 77/77 and paired mean gap from 5.77% to 4.27%; CVRP decreases from 5.53% to 5.20%. In a separate CVRP evaluation, No Skill Validation yields 5.38% versus 5.20% for Full. These experiments use different backbones and are not pooled. We use the same tool access and test solver cap in each within-framework comparison and report offline LLM calls and evaluations separately.

AuthorsOpenReview ↗

Response to Questions for Authors (Part 1/2): Q1–Q3

Thanks for your questions.

Q1: EvoAge differs in (i) its optimization object—an executable multi-operator solving workflow rather than a single heuristic program; (ii) its evolutionary search—structural variation plus agent-guided revisions based on executed Plan records; and (iii) its persistent knowledge update—conditional Skills accepted through matched, outcome-based library validation. This makes the evolutionary selection of solving strategies and reusable Skills explicit for combinatorial optimization, rather than relying solely on LLM reflection or memory editing. The trajectory is execution evidence, not a third evolved object.


Q2: The Qwen3.6-27B TSP ablations show that removing Plan evolution and Skill learning increases mean tour length by 3.20% and 2.80%, respectively, relative to Full. Complementary Qwen3.8-27B tests on CVRPLIB report 5.20% mean gap for Full, 5.53% without the learned library, and 5.38% without Skill Validation. These quantify component effects under the same registered toolbox and test-time execution cap; detailed LLM-call counts, Plan evaluations, and exact ablation definitions accompany the revised appendix. Results from distinct experiments are reported separately rather than pooled. There is no separate “Trajectory Evolution” settings; trajectory is the evidence used by Plan evolution.

TSP Ablation Results

TSP settingΔ tour length vs EvoAge
EvoAge—
without Plan Evolution+3.20%
without Skill Learning+2.80%

CVRP Ablation Results

CVRP settingMean gap
EvoAge5.20%
without learned library5.53%
without Skill Validation5.38%

Q3: The 60-second Table 1 limit applies to deployment-time solver execution and excludes offline evolution and online LLM orchestration, which we measure separately. For a representative single Qwen3.8-27B run, EvoAge uses 500 LLM calls / 2.30M tokens on TSP and 515 / 2.96M on CVRP, versus 501–1,579 and 510–1,593 calls across five AHD baselines, respectively. We followed RefineEvo/PathWise-style iteration and training-time limits and will report actual Plan/heuristic evaluations, Skill-validation runs, tokens, wall-clock time, and solver-only/end-to-end latency by method in the revised appendix. Independent repeat seeds are accounted for separately from one training run.

SettingTSP callsTSP tokensCVRP callsCVRP tokens
EvoAge Qwen3.8-27B5002.30M5152.96M
Five AHD baselines (range)501–1,5790.85–7.51M510–1,5930.84–11.10M
Reviewer_bk5GOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

EvoAge searches over plans that compose optimization tools, then turns experience from the resulting trajectories into reusable skills. Proposed skill edits are evaluated against the current library on paired validation instances. At test time the library is frozen and the planner produces one plan per instance. The paper evaluates this approach on TSP, CVRP, bin packing, and multiple knapsack problems, reporting high feasibility rates and competitive solution gaps under a nominal 60-second budget.

Critical strengths
  1. The framework treats successful execution as evidence for skill updates and uses paired validation before admitting changes. Freezing the library for testing also makes the intended transfer setting clear. These choices are more convincing than judging skill quality from an LLM's own explanation.
  2. The evaluation covers four different optimization families and provides per-instance results rather than only aggregate scores. EvoAge finds feasible solutions throughout the reported panels, and its TSP/CVRP results are promising. The interpretable skill examples show concrete decisions about construction, local search, and stopping, which helps explain what the library stores.
Critical weaknesses
  1. The experiments do not establish how much the learned skills add to the supplied tools. EvoAge can call strong conventional construction and improvement routines, while the main comparisons use separately generated heuristics or other agent systems. Figures 3–5 show progress and examples, but do not isolate persistent skill learning from the underlying toolbox and plan search on held-out problems. Reporting those existing results would be especially valuable: they address the central contribution more directly than the broad claim that APS is superior to AHD. Table 1 also has a clear exception to the blanket superiority claim: on BPP, EoH and CP-SAT have smaller gaps at the same 100% success rate.
  2. The shared 60-second budget is not an established end-to-end comparison. The released implementation describes this limit as solver time excluding LLM planning, and separately records API service time and execution time. The paper does not map these quantities to the runtime numbers in the tables or explain the corresponding accounting for DRAGON and the other methods. This matters because the headline comparison is explicitly about solving under a limited computational budget. The archive also lacks the reported run outputs and learned library, and Appendix A.2 uses one selected AHD training seed per method and family without explaining the selection. These gaps make the scale and reliability of the claimed advantage difficult to assess.
Questions for authors
  1. What are the held-out learned-versus-empty-library results, including feasibility, quality, and variation across runs? How much of the Table 1 gain remains when the toolbox and planner are held fixed?
  2. Do Table 1 and the per-instance runtime tables include profiling, LLM planning and repair, startup, and solution verification? Please report the solver-only and end-to-end costs using a consistent convention across methods, and summarize the offline cost of producing the skill library.
  3. How was the single AHD training seed selected? Can you provide the final learned library and the evaluation records needed to connect the released implementation to the reported results?
5 comments
AuthorsOpenReview ↗

Response to Paper Summary and Critical Strengths

Thank you for the detailed review and for recognizing execution-grounded Skill learning and paired validation. We have added same-Planner, same-Toolbox learned-versus-empty-library comparisons: on TSP, feasibility improves from 60/77 to 77/77, while the paired mean gap decreases from 5.77% to 4.27% on 60 commonly solved instances. We also clarify the 60-second execution budget, offline costs, seed protocol, and reproducibility materials below.


Thank you for highlighting execution-based Skill validation, frozen-library testing, and interpretable decisions. We now quantify the learned library's contribution on held-out benchmarks under controlled tool access.

AuthorsOpenReview ↗

Response to Critical Weaknesses

Thanks for your comments.

W1: We isolated the learned library's contribution using Qwen3.8-27B with the same Planner, Toolbox, and 60-second solver-execution budget. On TSPLIB, feasibility improves from 60/77 to 77/77; on 60 commonly solved instances, the paired mean gap drops from 5.77% to 4.27%. On CVRPLIB, both settings solve 20/20 instances, while mean gap drops from 5.53% to 5.20%, with 18/20 instances improving. Equal-length irrelevant-prompt controls do not reproduce the learned-Skill gains, supporting the value of Skill content rather than prompt length. Full four-family and repeated-run results are given in Q1 and the revised appendix.

On BPP, the evaluated Weibull instances are relatively tractable for classical packing techniques, so several methods already approach the lower bound. CP-SAT achieves a 0.02% gap, EoH reports 0.14%, and EvoAge achieves 0.31%. While existing methods demonstrate strong performance on BPP, EvoAge's advantages lies in its APS capability and generality: it autonomously organizes and adapts solving strategies across heterogeneous problems within a unified agent framework, achieving 100% feasibility across TSP, CVRP, BPP, and MKP. We include BPP for comparability with AHD studies and will clarify this distinction between performance on individual benchmarks and cross-family problem-solving capability in the revised manuscript.


W2: The common 60-second limit covers actual solver/workflow execution, not the entire online pipeline. LLM calls and network latency fluctuate, so planning and orchestration time are recorded separately; DRAGON is shown under both 60-second and original one-hour settings. Offline AHD implementations use different native settings; we followed RefineEvo/PathWise-style iteration and training-time limits and recorded actual evaluations, LLM calls/tokens, and Skill-validation work. Additional AHD runs at seeds 0, 1, and 2 quantify variability. The revised appendix and GitHub release will provide timing definitions, per-run costs, final Skill Libraries, run logs, evaluation records, and seed comparisons.

AuthorsOpenReview ↗

Response to Questions for Authors

Thanks for your questions.

Q1: Under identical Planner, Toolbox, and per-instance solver budgets, learned Skills improve both feasibility and paired solution quality on held-out benchmarks. Each test instance receives one Plan without test-time evolution. The following Qwen3.8-27B results separate full-benchmark feasibility from paired gap measurements.

ProblemFeasible, Empty → LearnedPaired mean gap, Empty → LearnedImproved
TSP (77)60 → 775.77% → 4.27%35/60
CVRP (20)20 → 205.53% → 5.20%18/20
BPP (5)5 → 50.82% → 0.33%1/5
MKP (10)10 → 100.03% → 0.03%3/10

The 5.77% → 4.27% TSP comparison is restricted to 60 jointly feasible instances; across all 77 feasible learned-library runs, its mean gap is 5.21%. Three independently trained CVRP libraries yield empty → learned gaps of 5.55% → 5.36%, 5.48% → 5.24%, and 5.51% → 5.51%, respectively all 20/20 feasible.

Thus, even with the Planner, Toolbox, and test-time search effort fixed, learned Skills yield 17 additional feasible TSP solutions and a 1.50-percentage-point reduction in paired mean gap, alongside a 0.33-percentage-point reduction on CVRP. These results directly demonstrate the independent contribution of accumulated Skills beyond the underlying tools and LLM planning capabilities.


Q2: No, Table 1 and the per-instance runtime tables are solver-only; they exclude profiling, LLM planning/repair, startup, and post-execution verification. We report the components separately because the cost boundaries differ across paradigms: EvoAge combines offline library construction, per-instance planning, and solver execution; AHD combines offline heuristic search with solver-only inference; DRAGON performs online optimization inside its runtime budget.

A single total would mix one-time offline cost, per-instance planning, and solver time, and would change with the number of test instances used for amortization. Under the common 60-second solver cap, the median TSP planning stage is 10.6 s with an empty library and 15.3 s with a learned library; AHD solver-only medians are 1.87–60.09 s on TSP and about 60 s on CVRP, i.e. cap-limited, so they do not establish an end-to-end advantage.

For offline cost, a representative single Qwen3.8-27B run uses 500 calls / 2.30M tokens on TSP and 515 / 2.96M on CVRP, with 348 / 354 Plan evaluations (156 / 162 training, 128 validation, 64 frozen); AHD uses 501–1,593 calls per seed. A multi-seed archive is not treated as one trained library; stage-level timing, offline evaluation, and Skill-validation costs are reported separately in the appendix, with DRAGON-60s and DRAGON-1h distinguished.


Q3: The original AHD comparison used training seed 0 fixed before evaluation, not chosen as the best of several seeds. We additionally ran seeds 0, 1, and 2 for five AHD methods on TSP and CVRP (30 method–family–seed runs), retaining their final algorithms, training logs, and evaluation records.

Representative EvoAge Skills appear in Appendix A.4 (Interpretable Skill Examples), covering TSP, CVRP, BPP, and MKP. Complete Skill Libraries, run manifests, per-instance results, and reproducibility instructions are included in the anonymous release and summarized in Appendix A.2; the final AHD algorithms are included in the release as well. The original Table 1 uses seed 0, and its seed-to-result mapping and multi-seed results are summarized in Appendix A.2.

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

The integration of evolutionary search and reusable skill learning for combinatorial optimization is promising. However, the claimed trajectory evolution is not reflected in the evolutionary operators, while the predefined toolbox limits the discovery of new capabilities. Missing ablations and incomplete cost accounting further weaken the empirical evidence.

Critical strengths

The two-level evolutionary framework provides a structured approach to optimizing solving workflows while accumulating reusable knowledge across instances.

Critical weaknesses
  1. Algorithms 1 and 3 apply selection, crossover, and mutation to Plans rather than trajectories, which serve only as execution feedback, undermining the central trajectory-evolution claim.
  2. Eq. (1) restricts operations to a predefined toolbox, making EvoAge primarily a recombination of existing heuristics rather than an open-ended discovery of new optimization capabilities.
  3. The lack of ablations isolating Plan Evolution, Skill Evolution, and LLM-based planning leaves it unclear whether the gains arise from the proposed mechanisms or simply improved heuristic selection and increased search effort.
  4. The computational comparison emphasizes a 60-second inference budget without reporting cumulative costs from offline evolution, solver evaluations, LLM calls, and Skill validation, raising concerns about computational fairness.
  5. The exclusive use of DeepSeek-V4-Flash leaves the framework’s sensitivity to LLM backbones unexplored.
  6. The main GitHub repository contains only a README, while the implementation is provided through a separate release. The accessibility, completeness, and reproducibility of the released code remain insufficiently verified.
Questions for authors
  1. How are trajectories explicitly represented and evolved, and how do the crossover and mutation operators differ from conventional evolutionary optimization of heuristic workflows?
  2. How can EvoAge transfer learned skills to unseen problem families without introducing additional problem-specific tools?
5 comments
AuthorsOpenReview ↗

Response to Paper Summary and Critical Strengths

Thank you for the constructive review. In EvoAge, Plan Evolution uses execution trajectories as evidence to revise executable Plans, while cross-instance Skill Evolution retains execution-verified decisions for subsequent instances. The trajectory is the record that connects the two levels; it is not a third evolved object.

We clarify three points:

(1) Trajectory Evolution. Although the evolutionary operators formally modify Plans, a Trajectory is the concrete execution process of a Plan. Crossover and mutation alter the Plan, and the new Plan must be re-executed to produce a new Trajectory. Thus, although trajectory evolution is not explicitly represented in the operators, trajectories evolve through Plan modification and subsequent execution.

(2) Capability Discovery. A predefined toolbox does not prevent the discovery of new problem-solving capabilities. New capabilities are not limited to inventing new algorithms. They also include novel combinations of existing algorithms, solving workflows, parameter configurations, and execution strategies autonomously discovered by the agent, beyond the solving procedures predefined by human experts.

(3) Ablation Studies and Computational Costs. We added controlled Skill and training-component evaluations as additional ablation studies. With Qwen3.8-27B, learned Skills improve TSP feasibility from 60/77 to 77/77 and reduce the mean gap on the 60 jointly solved instances from 5.77% to 4.27%; the CVRP mean gap improves from 5.53% to 5.20%. Additional experiments examine Plan offspring search, Skill Validation, and library freezing.

We also report offline LLM usage for representative training runs (TSP: 500 calls / 2.30M tokens; CVRP: 515 calls / 2.96M tokens) and clarify that the 60-second limit applies to final solver execution, rather than the entire pipeline.


Thank you for recognizing the two-level design.

AuthorsOpenReview ↗

Response to Critical Weaknesses

Thanks for your comments.

W1: Trajectory evolution is implemented through changes to the executable Plan and re-execution, rather than by editing an already recorded trajectory. A trajectory is the concrete execution of its Plan; when crossover or mutation changes a Plan, the offspring is executed to generate a new trajectory. Existing trajectories also guide the next modification through their recorded operations, state transitions, improvements, failures, and runtime. The operators therefore change the Plan explicitly and its realized trajectory through execution. We will state this relationship directly in Section 3.2 and Algorithms 1 and 3.


W2: A fixed set of tools does not imply a fixed set of solving strategies. EvoAge can discover how to select and combine available algorithms, configure parameters, transfer incumbent solutions, and adjust execution conditions and budgets, all relying on the agent's reasoning and planning capabilities. A newly discovered, effective combination is a workflow-level solving capability even when its atomic operators already exist. Eq. (1) fixes the operations available in the reported experiments, not these decisions. Additional solvers, AHD-generated algorithms, and NCO modules can also be added; in experimental exploration, the agent tends to select existing heuristics and solvers, since these already solve the problems quite well. We will clarify this meaning of capability discovery in the Introduction and Methodology.


W3: We report two ablation studies as follows:

First, on 12 common TSP instances with Qwen3.6-27B, removing Plan Evolution increases mean tour length by 3.20%, while removing Skill Learning increases it by 2.80%, under the same Planner, registered Toolbox, and 60-second per-Plan execution budget. Regarding the ablation setting without LLM Planning, Table 1 directly reports solver baselines that solve problem instances without requiring agent-generated Plans.

Second, with Qwen3.8-27B, under the same Planner and Toolbox, each test instance receives only one Plan without test-time evolution. The learned Skill Library improves TSP feasibility from 60/77 to 77/77 and reduces the mean gap on the 60 jointly solved instances from 5.77% to 4.27%. On CVRP, the mean gap decreases from 5.53% to 5.20%.

These results confirm the contributions of Plan Evolution and Skill Learning, demonstrating that EvoAge's improvements stem from evolving effective solving workflows and accumulating reusable Skills, rather than merely stronger heuristic selection or increased search effort.


W4: The 60-second limit is a solver-execution limit, not a limit on offline training or total online latency. At the paper-budget per-run level, a Qwen3.8-27B run uses 500 calls / 2.30M tokens on TSP and 515 / 2.96M on CVRP, with 348 and 354 solver evaluations including candidate validation and frozen evaluation. The five AHD baselines use 501–1,579 TSP calls and 510–1,593 CVRP calls per seed. This is a per-run/per-seed comparison, not a global efficiency claim; the 12-run archive is reported separately. Planning, startup, Skill validation, and offline library construction are reported as separate categories in Appendix A.2. Thus, all methods are evaluated under the same test-time solver-execution budget, with offline computational costs explicitly accounted for providing a transparent and fair basis for performance comparison.


W5: We extended backbone evaluation beyond the original DeepSeek setting. The DeepSeek-V4.1-Flash row is an additional backbone run, distinct from the main-table DeepSeek-V4-Flash run (CVRP 5.43% in Table 1). The following public-benchmark results report feasibility and the mean gap among all feasible instances for each model/run.

BackboneTSP (77)CVRP (20)BPP (5)MKP (10)
DeepSeek-V4.1-Flash100% / 2.92%100% / 5.33%100% / 0.31%100% / 0.03%
Qwen3.8-27B100% / 5.21%100% / 5.20%100% / 0.33%100% / 0.03%
GLM-5.3-Flash100% / 2.07%100% / 5.24%100% / 0.33%100% / 0.03%

For Qwen3.8-27B, 5.21% is the mean over all 77 feasible learned-library runs; on the 60 instances solved by both settings, the paired mean gap is 4.27%. Same-family cross-model reuse is supported: Qwen3.8→Qwen3.6 raises TSP feasibility from 67.5% to 96.1% and reduces CVRP gap from 87.68% to 5.83%; reverse transfer raises TSP feasibility from 76.6% to 98.7%.


W6: The implementation is available through the repository's Release archive. We organized the four-family Skill Libraries, run manifests, configurations, training/evaluation scripts, final AHD algorithms, and per-instance records. The revised README and reproducibility statement provide table-to-run mappings and commands for the reported results.

AuthorsOpenReview ↗

Response to Questions for Authors

Thanks for your questions.

Q1: Representation: An execution trajectory is serialized as JSON and records the executed operation sequence, search states, observations, solution changes, runtimes, and outcomes of a Plan. The Plan, trajectory, and measured outcome are archived together (Eqs. 2–3).

Plan variation and trajectory generation: Crossover and mutation change Plan operations, parameters, ordering, or control logic. Executing the offspring generates a new trajectory. Because an offspring may change only selected steps, EvoAge can preserve compatible completed steps and resume from saved execution state to complete the modified part, producing an updated execution record.

Distinction from conventional evolution: Rather than using a fixed set of hand-designed search operators, the LLM agent analyzes parent execution trajectories and decides which steps to preserve, recombine, replace, or retune. This trajectory-conditioned, agent-directed modification distinguishes EvoAge from workflow evolution driven only by predefined crossover/mutation rules and final fitness.


Q2: EvoAge transfers both algorithmic Skills and higher-level solving-strategy Skills. Its hierarchical Family–Strategy–Algorithm Library includes reusable principles for construction, improvement, repair, diversification, incumbent preservation, stopping, and budget allocation. Moreover, tools such as greedy or nearest-neighbor construction, iterated/local-neighborhood search, and OR-Tools can be adapted to multiple problem families through suitable interfaces and constraints, rather than being intrinsically tied to one benchmark. For a new family, EvoAge first analyzes the problem and then retrieves applicable Skills level by level to compose and parameterize a solving Plan from compatible registered tools. This supports cross-family reuse of solving knowledge and tool capabilities within the same APS framework.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

We sincerely thank all Reviewers, Area Chairs, Senior Area Chairs, and Program Chairs for their valuable time and constructive feedback. We have addressed the concerns through additional experiments, methodological clarifications, and cost analyses, all incorporated into the revised manuscript.

1. Methodological Novelty and Evolutionary Mechanism (P5qR: W1, W2, Q1; hn2G: W1, Q1, Q5)

Concern: What distinguishes EvoAge from existing AHD and self-evolving agents?

Response: EvoAge explores Automated Problem Solving (APS) beyond individual heuristic design through coupled Plan–Trajectory Evolution and Skill Evolution. Execution trajectories guide agent-directed workflow evolution, while validated experience is accumulated as reusable Skills. EvoAge discovers workflow-level capabilities through autonomous operator composition, conditional execution, and strategy optimization, connecting instance-level evolution with cross-instance knowledge accumulation.


2. Ablation Studies and Component Contributions (P5qR: W3; bk5G: W1, Q1; hn2G: W2, Q2, Q4)

Concern: Do evolution and learned Skills improve performance beyond the underlying tools?

Response: Removing Plan Evolution or Skill Learning increases mean tour length by 3.20% and 2.80% on 12 TSP instances. With the same Planner and Toolbox, learned Skills improve TSP feasibility from 60/77 to 77/77 and paired mean gap from 5.77% to 4.27% on 60 jointly feasible instances. CVRP gap decreases from 5.53% to 5.20%, while removing Skill Validation yields 5.38%. A same-Toolbox non-evolving Planner comparison further supports evolutionary optimization. See Section 4.5 (Tables 2–3) and Appendix A.2.1 (Table 5).


3. Computational Costs and Deployment (P5qR: W4; bk5G: W2, Q2; hn2G: W2, Q3 and follow-up)

Concern: What are the training and deployment costs, and does evolution continue at inference?

Response: The 60-second limit applies to solver execution, not end-to-end latency. A representative TSP run evaluated 156 Plans, consuming 1.34 cumulative solver-hours for Plan execution. We report costs across 12 independent runs, including Skill validation. Deployment uses a frozen Skill Library and one Plan per instance, without further evolution. Median solver/end-to-end times are 6.86/22.81 s (TSP) and 25.09/53.01 s (CVRP). Full-run elapsed times include frozen evaluation; offline-only time was not separately measured. See Appendix A.2.4 (Tables 11–14).


4. Generality and Skill Transfer (P5qR: W5, Q2; bk5G: W1)

Concern: Does EvoAge generalize across problem families and LLM backbones?

Response: Additional evaluations with Qwen3.8-27B and GLM-5.3-Flash achieve 100% feasibility across the reported TSP, CVRP, BPP, and MKP benchmarks. Transferring Qwen3.8-learned Skills to Qwen3.6 improves TSP feasibility from 67.5% to 96.1%. EvoAge supports heterogeneous problems through reusable strategies and compatible tools, while specialized methods remain stronger on certain benchmarks.


5. Reproducibility and Experimental Reliability (P5qR: W6; bk5G: W2, Q3)

Concern: Are the results reproducible, and how were seeds selected?

Response: The original AHD comparisons used seed 0 fixed before evaluation, not post-hoc selection. We added 30 AHD training runs across five methods, two problem families, and three seeds. The released materials include Skill Libraries, algorithms, configurations, logs, evaluation records, and reproduction instructions.


In summary, EvoAge explores an evolutionary APS paradigm that autonomously improves solving workflows and accumulates reusable Skills. We believe the additional evidence strengthens its methodological contributions and practical effectiveness. We sincerely hope these revisions address the reviewers' concerns and thank everyone again for their valuable consideration.

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

Related papers

Discussion (0)

Sign in to comment.