ATLAS: Scaffold-Free Algorithm Synthesis by LLMs via Embedding-Guided Quality-Diversity Search

AI summary

Overview

Research area: Large language model (LLM)-driven automated algorithm design, with a focus on combinatorial optimization and quality-diversity (multimodal) search.

Technical level: Advanced.

Scope (one sentence): The paper introduces ATLAS, an embedding-guided quality-diversity framework in which an LLM synthesizes complete optimization algorithms — rather than designated components inside a human-written scaffold — and evaluates it on four NP-hard combinatorial optimization problems.

What This Paper Is About

Most LLM-based automated algorithm design methods ask the model to fill in one designated piece of a human-specified scaffold, such as a priority selector or construction heuristic, while the surrounding control flow, component inventory, and component interactions stay fixed. ATLAS instead gives the LLM only a problem specification, a minimal input/output interface, and a common execution protocol, and lets it design the entire algorithm, including which components exist, how they interact, and how the workflow is organized. The goal is to make this much larger — and potentially multimodal — design space practically searchable without collapsing to a single design region.

Key Contributions

1. Scaffold-free full-algorithm synthesis. ATLAS supplies the problem definition (objective and constraints) plus only the callable entry point and instance/solution I/O formats. Beyond those, the LLM controls the complete algorithmic artifact, with no prescribed component inventory, function-role partition, or internal control flow.

2. Embedding-guided quality-diversity search. A coverage-preserving "semantic repertoire" of executable algorithms is organized in a pretrained embedding space. Embedding distance drives retrieval, clustering, redundancy control, and reference selection, retaining multiple near-best algorithms across distinct embedding-space regions while the search keeps improving the strongest design. "Semantic" here means similarity in the embedding of an algorithm's name, description, and preprocessed source code — not program semantics defined by execution behavior.

3. Hierarchical three-layer search. Layer 1 concentrates refinement on the current best algorithm and its embedding neighborhood; Layer 2 gives non-elite cluster representatives dedicated refinement opportunities; Layer 3 performs cross-region synthesis that recombines components and their interactions from different regions to form hybrids.

4. Independent evaluation and failure-conditioned recovery. Because generated algorithms own solution construction and constraint handling, the evaluation must detect a wider failure surface: execution, interface, malformed-output, and feasibility failures. ATLAS independently verifies returned solutions and recomputes objectives, uses an all-or-nothing validity rule that records failures instead of converting them into finite penalties, and routes classified evidence to an error-conditioned Repair operator.

5. Empirical design insights. Controlled studies examine artifact scope, representation, initialization, grouping, and search allocation, and are reported to show that moving from component synthesis to full-algorithm synthesis through ATLAS improves performance in most tested settings.

Main Findings

• Full-algorithm synthesis is competitive. Across the four NP-hard problems, ATLAS is reported to outperform several state-of-the-art component-synthesis methods and a matched full-synthesis baseline (EoH-Full), while remaining competitive with strong human-designed, domain-specific algorithms.

• Multimodal retention. A single ATLAS run retains several algorithms with comparable performance drawn from distinct embedding-space regions, rather than converging on a single design.

• Code inspection of retained designs. Inspected multi-component designs differ in their primary construction heuristic or their global-search backbone. Code inspection of four released illustrative algorithms shows coordinated multi-function pipelines in which construction or seeding feeds problem-specific improvement and diversification mechanisms, together with an explicit policy for accepting non-improving candidates. The paper states that these examples do not quantify how frequently such structures occur across the complete archives.

• Two-phase initialization helps. Combining Create-based bootstrap generation at temperature T = 1.0 with reference-conditioned Diverge diversification is reported to substantially improve initial coverage compared with sampling solely with Create.

• Layer ablation. The complete three-layer configuration performs best among the four layer variants evaluated; a search-layer ablation evaluates the Layer 2 contribution conditional on Layer 3.

• Embedding strategy selection. The representation (name, description, and preprocessed source code concatenated) using mGTE-large-en-v1.5 was selected through systematic evaluation of multiple embedding strategies.

• Not reported in the available content. Specific numeric results — per-problem objective values, training or test instance counts, archive capacity N_max, the neighborhood size k, the number of clusters, deduplication thresholds τ_strict and τ_soft, and the tie tolerance ε — appear only as named parameters in the formulas and are not given numeric values in the content provided, which is truncated before the results tables.

Methodology in Plain English

ATLAS maintains a bounded archive of valid, executable algorithms. Each algorithm is represented as a name, a self-contained description, and full Python source code; these three fields are concatenated and embedded with mGTE-large-en-v1.5. Similarity is one minus cosine distance, kept in an incrementally updated distance matrix.

New algorithms come from a small suite of prompt-based operators, classified by how many reference algorithms they receive and whether they are triggered by a failure:

• Create (zero references) generates candidates from the problem specification and I/O requirements, with numerical example instances paired with valid solutions to clarify output structure. Used only for initialization.
• Improve, Tune, and Simplify refine one archived reference while preserving its paradigm (logic/efficiency, numerical parameters, and code parsimony respectively).
• Combine and Diverge take multiple references; nearby references give local context, embedding-distant references give cross-region context. Diverge asks for algorithms explicitly different from the references.
• Repair takes a rejected candidate plus classified failure evidence and regenerates the whole algorithm. Evidence is routed among six prompt modes: memory limit, partial failure, timeout, constraint violation, runtime error, and framework or interface violation.

Initialization runs in two phases: bootstrap generation with Create, then iterative Diverge from references sampled uniformly from the growing valid archive.

Every candidate is executed on all training instances under the resource limits; output and feasibility are verified and objectives independently recomputed. Any failure on any instance invalidates the candidate, and a failed candidate is regenerated with Repair and fully re-evaluated. The external evaluator never completes, modifies, or makes a solution feasible on the algorithm's behalf.

The archive is managed by two-tier deduplication (strict and performance-aware, with ties broken uniformly at random) and, when capacity is exceeded, by iteratively removing the lower-performing algorithm from the most similar pair, protecting the elite region. The elite region is the current best algorithm plus its k-nearest neighbors.

Each iteration, the archive is clustered using k-medoids with automatic K selection. The cluster containing the best algorithm is removed entirely for the non-elite region set, other elite members are removed from remaining clusters, empty clusters are discarded, and each remaining region's training-best survivor becomes its representative. Layer 1 schedules repeated refinement and local Combine around the best algorithm; Layer 2 schedules refinement and within-region Combine for each non-elite representative; Layer 3 schedules cross-region Combine (with and without the best algorithm as an anchor) and Diverge. The number of candidates each Layer 3 stream schedules scales with the surviving cluster count, subject to the global budget. After the budget is exhausted, the training-best archive member and one representative per cluster are returned.

Evaluation uses four NP-hard problems — CVRP, CVRPTW, FSS, and QAP — covering routing, scheduling, and assignment. Comparisons span three groups: human-designed domain-specific solvers (PyVRP, Google OR-Tools, VROOM for routing; NEH, Taillard-accelerated Iterated Greedy with idle-time tie-breaking, and Iterative Beam Search for FSS; Robust Tabu Search, Simulated Annealing, Breakout Local Search, and Memetic Search for QAP); component-based LLM methods (ReEvo, EoH, MCTS-AHD) run under a shared greedy-construction scaffold based on LLM4AD with matched token-budget-based termination; and EoH-Full, an adaptation of EoH's evolutionary framework to evolve full algorithms using ATLAS's problem- and interface-aware prompts.

Why This Matters

Impact on research. The paper argues that removing the human-specified scaffold enlarges the algorithm design space and makes it multimodal, and that embedding-guided quality-diversity search can make that enlarged space practically searchable. It offers an alternative to selection-driven evolutionary search by removing algorithms that contribute the least additional coverage rather than discarding them by global fitness ranking, and it shows that archive coverage has an operational role — supplying varied reference material for cross-region synthesis — not just insurance against premature convergence.

Real-world applications (the paper motivates optimization algorithms generally via logistics, scheduling, and resource allocation; the specific benchmarks map as follows):

• Vehicle routing under capacity limits (CVRP) and under customer time windows (CVRPTW).
• Production scheduling in a fixed machine order (FSS), where makespan is minimized.
• Facility-to-location assignment with flow-distance costs (QAP).
• General resource allocation and logistics planning, given the framework's problem specification plus minimal I/O interface design.

Industry relevance. Because ATLAS requires only a problem specification, an entry-point/solution format, and a common execution protocol, it targets settings where domain-specific solver engineering is expensive and where the algorithm's internal structure is not known in advance. The released implementation includes worker-process parallel evaluation with runtime and memory controls, plus lineage, resource, and failure records, which matters for teams that need to audit and reproduce generated solvers. The paper also notes that greater design freedom can increase synthesis cost, since it admits more complex, multi-stage algorithms whose execution and iterative refinement require greater computational effort.

Future Directions

1. Quantifying structural diversity. The paper notes that its code inspection of four illustrative algorithms does not quantify how frequently multi-component pipelines arise across complete archives; a systematic study could measure this.

2. Explicit structural guidance. The paper states that its evidence does not imply explicit structural guidance can never improve reliability or search efficiency, and that ATLAS can use operator instructions focused on a selected component or interaction without imposing a global decomposition — but such policies are not compared in this work.

3. Validation beyond the tested benchmarks and representation. Coverage of additional NP-hard problems, and of embedding strategies beyond the selected mGTE-large-en-v1.5 configuration, remains open.

4. Direct comparison with concurrent full-synthesis approaches. A2DEPT, developed concurrently with ATLAS, uses a program-lineage tree, an explicit function-level representation, hierarchical micro/macro operators, and dependency-aware repair; the paper does not report a head-to-head comparison.

5. Managing synthesis cost. Since scaffold freedom admits more complex algorithms with higher execution and refinement cost, cost-aware search allocation is an unresolved design question.

Target Audience

Researchers and practitioners in automated algorithm design, evolutionary and quality-diversity optimization, and LLM-based code generation; engineers building or auditing LLM-generated optimization solvers for routing, scheduling, and assignment problems; and readers already familiar with component-synthesis methods such as FunSearch, EoH, and ReEvo who want to understand what changes when the scaffold is removed.

Authors’ abstract

Most LLM-based automated algorithm design methods optimize a designated component within a human-specified scaffold, fixing overall organization and component interactions. We present ATLAS, an embedding-guided quality-diversity framework for scaffold-free full-algorithm synthesis in combinatorial optimization. The problem specification supplies objectives and constraints; a minimal I/O interface fixes only instance and solution formats; the LLM chooses and restructures components, interactions, and control flow. This freedom enlarges the search space, risking invalid candidates and premature convergence to one design region. ATLAS independently detects execution, interface, and feasibility failures, recomputes objectives, and applies error-conditioned repair; similarity-based archive management preserves algorithms across embedding-space regions to counter premature convergence. Its three-layer search refines the best design, gives other regions dedicated refinement opportunities, and performs cross-region synthesis to recombine components and their interactions. Across four NP-hard problems, ATLAS outperforms several state-of-the-art component-synthesis methods and a matched full-synthesis baseline while remaining competitive with strong human-designed algorithms. One ATLAS run retains several algorithms with comparable performance from distinct embedding-space regions rather than a single design. Code inspection finds that these multi-component designs differ in their primary construction or global-search backbone. Our results suggest that embedding-guided quality-diversity search can make the enlarged full-algorithm design space practically searchable. Source code and exact executable prompts are available at https://github.com/Danial-Yazdani/ATLAS .