$A_2$DEPT: Large Language Model–Driven Automated Algorithm Design via Evolutionary Program Trees

Introduction

$A_2$DEPT shifts the paradigm of automated algorithm design from simply filling in "heuristic slots" to empowering Large Language Models (LLMs) to act as full-scale algorithm architects. By combining tree-structured evolutionary search with a self-healing code maintenance loop, $A_2$DEPT evolves complete, executable solver programs that outperform state-of-the-art baselines by nearly 10% across complex optimization tasks.

The Problem: Beyond Template-Bound Design

Combinatorial Optimization Problems (COPs)—such as routing delivery trucks or scheduling factory floors—are notoriously difficult NP-hard challenges. Traditionally, experts hand-craft heuristics to find good solutions quickly.

Recently, researchers have leveraged LLMs for Automated Heuristic Design (AHD). However, most existing AHD methods are "template-bound": human developers provide a fixed code skeleton, and the LLM only fills in specific functions, such as a scoring rule. This creates a "framework bottleneck." If the human-provided skeleton is suboptimal, the LLM cannot fix it.

Moving toward true Automated Algorithm Design (AAD), where the LLM redesigns the entire algorithmic workflow, is significantly harder due to three main challenges:

1. Executability Instability: Free-form code is fragile; a single minor error can crash the entire program.
2. Search Space Explosion: The space of all possible programs is effectively infinite.
3. Credit Assignment Opacity: When dozens of lines of code are changed simultaneously, it is difficult to isolate which specific modification improved performance.

Methodology: How $A_2$DEPT Works

To address these challenges, the authors introduce $A_2$DEPT (Automated Algorithm Design via Evolutionary Program Trees), which treats the LLM as a system-level architect. The framework relies on several key innovations:

• Evolutionary Program Trees: Instead of maintaining a simple "population" of code snippets, $A_2$DEPT builds a global search tree. This preserves the lineage of every attempt, allowing the system to revisit and branch off from promising ideas that may have temporarily underperformed.
• Hybrid Selection: The system uses a mix of Simulated Annealing (to evaluate if a child is a worthy successor to its parent) and Boltzmann Sampling (to select diverse candidates from the entire history). This prevents the search from stagnating in local optima.
• Hierarchical Operators: $A_2$DEPT applies three levels of edits:
• Micro-tuning: Small logic or parameter tweaks.
• Macro-mutation: Complete rewrites of the main workflow.
• Semantic Crossover: Merging logic from two different successful programs.
• Program Maintenance Loop: To solve the fragility problem, $A_2$DEPT features a self-healing mechanism. It performs dependency analysis on generated code. If the LLM calls a function that does not yet exist, the system automatically prompts the LLM to implement the missing dependency before execution.

Datasets and Evaluation

The framework was rigorously evaluated across a diverse set of NP-hard benchmarks:

• Standard Benchmarks (FrontierCO): Maximum Independent Set (MIS), Capacitated Vehicle Routing (CVRP), Capacitated Facility Location (CFLP), and Flexible Job-Shop Scheduling (FJSP).
• High-Constraint Benchmarks: Electric Vehicle Routing with Time Windows (CEVRPTW) and Multi-Mode Resource Constrained Project Scheduling (MRCPSP).
• Continuous Optimization: To demonstrate generality, $A_2$DEPT was also tested on numerical ODE integration, root-finding, and feedback control tasks.

Key Insights and Results

• Superior Optimality: On standard benchmarks, $A_2$DEPT reduced the mean normalized optimality gap by 9.8% relative to the strongest LLM-based AHD baselines (such as ReEvo and MCTS-AHD).
• Robustness in Constraints: In highly constrained problems like CEVRPTW, the framework achieved a 0.00% gap and the lowest infeasibility rate, proving its ability to navigate fragmented search spaces where valid solutions are rare.
• Cross-Domain Success: Beyond discrete mathematics, $A_2$DEPT outperformed specialized industrial solvers (like LSODA) on "stiff" differential equations, demonstrating that its algorithm design logic transfers across mathematical domains.
• Paradigm Shifts: In case studies, $A_2$DEPT successfully evolved a solver from a simple "greedy" approach into a sophisticated Iterated Local Search (ILS) framework, complete with advanced data structures like heaps for efficiency. This is a leap that template-bound methods simply cannot make.
• The "Self-Healing" Enabler: Open-ended algorithm design is only viable with a robust way to handle broken code. The dependency-repair loop significantly increased the yield of executable candidates.

Limitations and Future Directions

While groundbreaking, $A_2$DEPT has a few limitations. The authors noted a "Partial Migration" trap, where the LLM sometimes performs incomplete refactoring—such as changing a data structure to a bitmask in one function but forgetting to update interacting functions, leading to type errors that simple dependency repair cannot fix.

Additionally, $A_2$DEPT currently operates on modular, single-file prototypes. Scaling this to industrial-scale codebases with thousands of files will require more advanced architectural management and incremental compilation. Finally, running and evaluating hundreds of candidate programs is computationally expensive. Future work will focus on reducing these verification costs, potentially through static analysis or cheaper proxy evaluations.