💻 computer science

A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees

A2DEPT is a novel framework that leverages Large Language Models as system-level architects within an evolutionary program tree search, combined with a feedback-driven repair mechanism, to autonomously synthesize complete, executable algorithms for combinatorial optimization problems, thereby overcoming the rigid template limitations of existing methods and achieving superior performance.

Original authors: Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you need to solve a massive, complex puzzle, like organizing a delivery route for 1,000 trucks or scheduling a factory with hundreds of machines. These are "Combinatorial Optimization Problems." Traditionally, humans had to sit down and hand-craft the rules (heuristics) for how to solve these puzzles. It was slow, required deep expertise, and the rules often broke if the problem changed slightly.

Recently, we started using Large Language Models (LLMs)—the same AI that writes essays and code—to help design these rules. However, most current methods are like giving the AI a Lego set with a fixed instruction manual. The AI can swap out a few bricks (tweak a specific rule), but it can't change the overall structure of the castle. If the manual says "build a tower," the AI can't decide to build a bridge instead, even if a bridge would work better.

Enter A2DEPT.

The authors propose a new system called A2DEPT (Automated Algorithm Design via Evolutionary Program Trees). Instead of giving the AI a fixed manual, they let it act as a master architect who can redesign the entire building from the ground up.

Here is how it works, using simple analogies:

1. The "Tree" of Ideas

Imagine a family tree, but instead of people, it's a tree of computer programs.

The Roots: The process starts with a few basic, working programs.
The Branches: The AI takes a program, makes a change (a mutation), and creates a "child" program.
The Selection: Just like in nature, some children are better at solving the puzzle than their parents. The system keeps the best ones and tries to improve them further.

2. The "Construction Crew" (The Three Workers)

To make sure the AI doesn't just make random, broken code, A2DEPT uses three specific types of "workers" to edit the programs:

The Tinkerer (Micro-tuning): This worker makes small, safe adjustments. They might tweak a number or fix a logic error inside a specific function, like sharpening a tool. They don't change the blueprint.
The Architect (Macro-mutation): This worker is bold. They can tear down a wall and build a new room. They can rewrite the main flow of the program, changing how the algorithm thinks from start to finish.
The Mixer (Crossover): This worker takes the best ideas from two different "parent" programs and mashes them together to create a hybrid child.

3. The "Safety Inspector" (Program Maintenance)

Here is the biggest challenge: When you let an AI redesign a whole program, it often creates code that doesn't run. It might call a function that doesn't exist or forget to import a library.

The Problem: In the past, if the code broke, the whole attempt was thrown away.
The A2DEPT Solution: They added a Safety Inspector. Before the new code is tested, this inspector scans it. If it's missing a piece (like a missing function), the inspector asks the AI to write that missing piece immediately. If the code has dead ends (parts that never get used), the inspector cuts them out.
The Result: This ensures that almost every new idea the AI generates is actually runnable, allowing the search to continue without getting stuck.

4. The "Smart Filter" (Hybrid Selection)

How does the system decide which programs to keep?

The "Good Enough" Rule: Sometimes, a new program is slightly worse than the parent, but it has a unique structure that might lead to a breakthrough later. A2DEPT uses a smart filter (based on a method called Simulated Annealing) that allows these "promising but currently worse" programs to survive, preventing the system from getting stuck in a local rut.
The "Diversity" Rule: It also randomly picks some older, interesting programs from the history tree to keep the search diverse, ensuring they don't all look the same.

What Did They Find?

The authors tested A2DEPT on various difficult puzzles (like routing trucks, scheduling jobs, and finding patterns in graphs).

Better Results: A2DEPT consistently found better solutions than previous AI methods that were stuck with fixed templates.
The Gap: On standard tests, it reduced the "gap" between the AI's solution and the perfect solution by nearly 10% compared to the next best method.
Robustness: It worked well even on very difficult problems with many strict rules (like electric vehicles with limited battery and tight time windows), where other methods often failed to find any valid solution.

The Bottom Line

A2DEPT is like upgrading from a paint-by-numbers kit (where you can only change the colors) to a full construction site (where you can change the walls, the roof, and the foundation). By combining a smart evolutionary search with a "safety inspector" that fixes broken code on the fly, it allows AI to invent entirely new ways to solve complex problems, rather than just tweaking old ones.

1. Problem Definition

The paper addresses the challenge of Automated Heuristic Design (AHD) for Combinatorial Optimization Problems (COPs).

Context: COPs (e.g., TSP, Vehicle Routing, Job Shop Scheduling) are typically NP-hard. Traditional manual heuristic design is labor-intensive, requires deep domain expertise, and often fails to generalize across problem variants.
Current Limitations: Recent Large Language Model (LLM)-based AHD methods (e.g., FunSearch, EoH, ReEvo) have shown promise but suffer from a critical bottleneck: they operate within fixed algorithmic templates. They only optimize isolated heuristic components (like scoring functions) while keeping the surrounding solver logic (control flow, backtracking, iteration structure) rigid.
The Gap: This "template-bound" approach limits system-level innovation. If the template is suboptimal for a specific problem, the heuristic cannot compensate. Furthermore, moving from optimizing a single component to designing a complete solver (Open-ended Automated Algorithm Design, or AAD) introduces massive challenges:
1. Executability Instability: Free-form code generation often leads to compilation errors, missing dependencies, or runtime failures.
2. Search Space Explosion: The space of valid, high-performing complete programs is vast and sparse.
3. Credit Assignment Opacity: It is difficult to attribute performance gains to specific code changes when the entire algorithm is evolving.

2. Methodology: A2DEPT Framework

The authors propose A2DEPT (Automated Algorithm Design via Evolutionary Program Trees), a framework that treats LLMs as system-level architects to evolve complete, executable solver programs.

Core Components:

Tree-Structured Evolutionary Search:
- Unlike population-based methods, A2DEPT maintains a global search tree where nodes represent executable programs, their scores, and generation metadata.
- Hybrid Selection Strategy:
  - Simulated Annealing (SA) Primary Selection: Uses the Metropolis criterion to accept parent-child pairs based on score improvement, preserving a "parent-child refinement" relationship.
  - Boltzmann Supplementary Selection: To prevent the search from collapsing into a greedy top-k selection and to preserve diversity, the system samples additional parents from the global tree history using Boltzmann probabilities. This allows "underperforming but structurally promising" branches to survive.
- Dynamic Re-annealing: If the search stagnates (no improvement for $N_{stall}$ generations), the temperature is increased to restore exploration capability.
Hierarchical Operators with Adaptive Scheduling:
To address credit assignment and enable structural changes, A2DEPT uses three tiers of operators, scheduled adaptively based on feedback:
- Micro-tuning ( $m_1$ ): Local edits to mutable strategy functions (e.g., refining a scoring formula) while preserving interfaces.
- Macro-mutation ( $m_2$ ): Top-down redesign of the solver's entry point and control flow. It allows the LLM to call undefined helper functions, which are filled in later.
- Semantic Crossover ( $e_1$ ): Synthesizes a hybrid program by integrating complementary mechanisms from two parents.
- Adaptive Scheduling: A node-specific weight vector is updated based on the performance change ( $\bar{r}$ ) of the child. Successful operators are reinforced, while unsuccessful ones are penalized, dynamically shifting search effort between micro-refinement and macro-restructuring.
Program Maintenance Mechanism (Executability Enforcement):
To make open-ended generation practical, A2DEPT includes a lightweight, feedback-driven repair loop:
- Structured Representation: Programs are split into an immutable "Preface" (imports, constants) and a mutable "Function Registry."
- Dependency Repair: When a generated program calls undefined functions (common in macro-mutation), a dependency graph is built. The LLM is iteratively prompted to implement missing functions until the program is "dependency-closed."
- Pruning: Unreachable code is pruned to prevent dead logic accumulation.

3. Key Contributions

Paradigm Shift: Moves from template-bound AHD (optimizing components) to Open-ended AAD (evolving complete solvers), unlocking a richer design space.
A2DEPT Framework: Introduces a tree-structured evolutionary search with hybrid selection (SA + Boltzmann) and hierarchical operators to navigate the vast program space.
Reliability Mechanisms: Proposes a program-maintenance loop for automated dependency repair and a structured representation to ensure executability during evolution.
Empirical Validation: Demonstrates consistent superiority over state-of-the-art LLM-based baselines across diverse NP-hard benchmarks.

4. Experimental Results

The authors evaluated A2DEPT on six NP-hard problems: MIS, CVRP, CFLP, FJSP (standard benchmarks) and CEVRPTW, MRCPSP (high-constraint benchmarks).

Performance on Standard Benchmarks:
- A2DEPT outperformed all LLM-based baselines (FunSearch, EoH, ReEvo, MCTS-AHD) on every task.
- Key Metric: On standard benchmarks, A2DEPT reduced the mean normalized optimality gap by 9.8% relative to the strongest competing AHD baseline.
- It achieved competitive results against non-LLM references (e.g., matching Gurobi on MIS).
High-Constraint Problems:
- On CEVRPTW and MRCPSP, A2DEPT achieved the lowest Infeasibility Rate (IR) and best optimality gaps, demonstrating robustness in fragmented search spaces where other methods often fail to find valid solutions.
Generalization:
- A2DEPT showed strong generalization across different design frameworks (e.g., Guided Local Search) and instance distributions.
- Ablation studies confirmed that removing any component (e.g., Boltzmann sampling, adaptive scheduling, or the maintenance loop) significantly degraded performance.
Continuous Optimization:
- The framework was also successfully applied to continuous domains (ODE solving, root-finding, control policies), discovering novel numerical solvers that outperformed specialized industrial baselines (e.g., LSODA) on stiff problems.

5. Significance and Impact

System-Level Innovation: A2DEPT proves that LLMs can act as "algorithm architects," not just code generators. By evolving the entire solver logic, it can discover structural paradigms (e.g., shifting from a constructive greedy heuristic to an Iterated Local Search framework) that component-level tuning cannot achieve.
Scalability: The framework addresses the "executability" bottleneck of open-ended code generation, making it feasible to evolve complex, multi-module programs without human intervention.
Future Directions: The paper suggests that while current methods are limited to research-prototype scale, the approach paves the way for automated synthesis of industrial-grade solvers, provided future work addresses modular management and static type-checking for large codebases.

In summary, A2DEPT represents a significant leap in automated algorithm design, moving beyond "filling in the blanks" of a fixed template to "writing the whole book," thereby achieving superior performance and robustness in solving complex combinatorial optimization problems.