PACE: Primitive-Aware Code Evolution for Automated Algorithm Design

Large Language Model (LLM)-based automated algorithm design (AAD) typically evolves algorithms as complete, indivisible programs. The paper identifies a fundamental limitation of this approach: "While this whole-program perspective simplifies the search space, it fundamentally couples the useful local logic to its host program. Consequently, valuable code snippets vanish when the overall program is discarded, making it highly difficult to assess the contribution of individual algorithmic components. Existing AAD methods typically treat the designed algorithm as the minimal unit. Specifically, variation operators such as crossover and mutation place entire parent programs within the LLM context, allowing arbitrary edits to the algorithm without explicit boundary constraints. This coarse-grained perspective limits the LLM's ability to accurately distinguish between useful and harmful local logics within the algorithm. As shown in Figure 1a, eliminating a low-performing algorithm entails discarding all of its local logic, including components that could be valuable in a different algorithm. As a result, useful logic may be repeatedly discarded and rediscovered, wasting the search budget and limiting the performance of AAD methods."

To address this, the authors propose Primitive-Aware Code Evolution (PACE), which decouples local logic from complete programs by representing it as persistent units called Executable Algorithmic Primitives (EAPs). An EAP is defined as a callable function that is generated during search and retained independently of the complete algorithm in which it was created or first observed. Formally, an EAP e = (σe, ϕe), where σe specifies its textual description, and ϕe is its executable function. The implementation ϕe remains fixed when the EAP is transferred between algorithms; modifying it defines a different EAP.

The paper breaks down the EAP concept: "At the code level, EAP is an implemented callable function. During the AAD process, a promising EAP is extracted from an algorithm generated in an early iteration, stored in a persistent EAP set, and subsequently invoked by some candidates generated in later iterations. EAP enters the set with an undetermined utility value. It updates the utility values by continuously competing with the existing EAPs. EAPs with higher utility values are more likely to be included in the newly generated algorithm."

PACE maintains a search state St = (Pt, Et, Ht), where Pt is a population of complete algorithms, Et is the persistent EAP set, and Ht records evidence obtained when EAPs are transferred between algorithms. Critically, EAPs persist: For every admitted EAP, e ∈ Et =⇒ e ∈ Et+1. This persistence makes the local function available to algorithms that are generated after its source algorithm has disappeared.

PACE formulates EAP selection as a Multi-Armed Bandit problem solved using Thompson Sampling. "Let a trial consist of a parent algorithm A, a generated child A′, and the explicitly injected EAP e. The trial yields a binary reward: re = I[J(A′) > J(A)]. PACE models this as a Bernoulli random variable parameterized by an unknown success rate ρe, defined as the conditional probability of achieving a strict performance improvement given the explicit injection of e. Each EAP maintains a Beta posterior initialized as Beta(1,1), updated as (αe, βe) ← (αe + re, βe + 1 − re). A strictly improving child increments αe. A degradation, score tie, or runtime execution error increments βe. Notably, if the LLM fails to structurally integrate e into A′, the trial is deemed invalid, and the posterior remains unchanged to prevent biased penalty. Newly extracted EAPs undergo a brief, forced warm-up exposure before being subjected to standard Thompson selection."

PACE introduces four variation operators invoked with equal probability during the search:

• P1: Primitive Insertion — Thompson sampling selects a focus EAP e+ ∉ CV(A) that must be integrated while preserving all previously exposed parent EAPs, subject to a maximum capacity K.

• P2: Primitive Replacement — PACE selects one called EAP e− as the removal target and selects an absent EAP e+ by Thompson sampling where The removal target is the called EAP with the lowest posterior mean and credit is strictly assigned to the injected EAP e+.

• P3: Primitive-Preserving Refinement — optimizes how the current EAP composition is utilized without altering its membership, refining order, parameters, or interactions around the fixed EAP calls. No posterior update is triggered.

• P4: Primitive-Aware Crossover — selects two parents and requires the child to freely recombine a subset of this joint pool under the maximum capacity K, while strictly inheriting at least one primitive from each parent. This also does not trigger posterior updates as the simultaneous unconstrained recombination of multiple primitives fundamentally confounds credit assignment.

The call-set relations are enforced as "strict structural constraints rather than optional prompt. PACE programmatically verifies the required, preserved, and removed primitive calls via the AST verifier before validating a candidate as a realized operator outcome. Candidates failing to satisfy their assigned structural contracts are immediately discarded from the Thompson sampling update, ensuring that unverified LLM hallucinations do not corrupt the empirical transfer evidence."

PACE discovers new EAPs through two mutually exclusive mechanisms executed at the end of each generation, with at most one EAP proposed per generation, and EAP generation and extraction are strictly mutually exclusive, with extraction holding higher priority:

• EAP Generation — Conditioned on the task specification and the implementations of the top-k performing EAPs, the LLM is explicitly prompted to synthesize a functionally distinct EAP, forcing it to extrapolate beyond existing capabilities and avoid functional redundancy.

• EAP Extraction — refactors local logic from a newly evaluated historical best into a persistent EAP, strictly without altering or reevaluating the source program, acting as a preservation mechanism that rescues valuable local logic even after the source algorithm is discarded.

The paper highlights three contributions: (1) introducing EAPs to enable the explicit transfer of algorithmic local components, where an EAP is transferred across algorithms to accumulate evidence for updating its utility; (2) proposing PACE with offspring generated by primitive-aware variation operators are associated with specific EAPs, assigning credit to each EAP by comparing the corresponding offspring algorithms with their parents and using Thompson sampling, PACE selectively leverages effective EAPs to accelerate the discovery of high-performing algorithms; and (3) experimentally showing PACE finds better algorithms than existing LLM-based AAD methods under the same evaluation budget.

PACE was evaluated on four tasks spanning continuous control (Racing Car, Bipedal Walker) and combinatorial optimization (TSP-Construct, TSP-ACO), using GPT-4o-mini for algorithm generation, three independent runs of 1000 evaluations, and comparing against baselines including EoH, ReEvo, MCTS-AHD, HSEvo, MLES (cold-start), PPO, DeepACO, and classical ACO.

On Racing Car, PACE achieves a training score of 92.40 and a test score of 98.90. Remarkably, PACE outperforms not only all AAD baselines like HSEvo at 84.17, but also neural PPO at 85.688 in zero-shot test generalization. On Bipedal Walker, existing AAD methods struggle severely with baselines flatline near zero or negative test scores due to premature convergence, while PACE reaches a training score of 67.06 and an impressive test score of 133.71, outperforming the specialized control baseline MLES cold-start at 15.42 by a wide margin.

On TSP-ACO, PACE consistently achieves the best performance across all out-domain scales, reaching 11.645 at n = 200, 19.485 at n = 500, and 28.130 at n = 1000, while baselines exhibit performance degradation during scale transfer — e.g., MCTS-AHD suffers massive degradation as problem size increases, yielding a cost of 50.291 at n = 1000, which is worse than classical non-learning ACO. On TSP-Construct, PACE achieves the lowest tour cost across all problem sizes, with costs of 6.013 at n=50, 12.064 at n=200, 18.825 at n=500, and 26.596 at n=1000.

The paper reports ablations on components and parameters:

• Removing Thompson Sampling (select primitives randomly instead) causes a severe performance drop across both tasks. Preserving primitives alone is clearly insufficient.

• Removing any operator P1–P4 degrades performance; Operator P3 is particularly critical. Removing P3 causes the score on Racing Car to crash to 79.413, and degrades the TSP routing score to 5.832.

• Removing primitive extraction harms the final quality across both tasks.

• Removing primitive generation causes a noticeable performance drop on Racing Car though the TSP difference (0.009) easily falls within the natural noise.

• Parameter sensitivity: k=3 is optimal; k=1 restricts algorithmic expressiveness and k=5 introduces excessive context noise and degrades performance.

An additional ablation on LLM backbones shows that upgrading the EAP discovery model while keeping host algorithm generation on GPT-4o-mini produces substantial performance improvements, and notably EAP discovery accounts for on average only 1.6% of total token consumption during search.

The paper concludes: "In this paper, we introduce EAPs to decouple reusable local logic from complete algorithms. Building on this representation, we present PACE. PACE maintains a dynamic set of EAPs and applies specialized operators to structurally guarantee their cross-algorithm transfer. The framework leverages Thompson Sampling to guide EAP selection based on relative performance improvements. Experiments across continuous control and combinatorial optimization show that PACE achieves superior performance compared to existing baseline methods. The results confirm that preserving and transferring valuable local primitives can enhance final algorithmic performance... Ultimately, this work shifts automated algorithm design from full-program search toward modular composition."

The authors acknowledge a limitation: "PACE assumes that primitives can be evaluated and selected independently. In algorithms with extremely complex constraints, strong coupling may exist between different primitives. Evaluating primitives separately might not fully capture their joint interactions. Future work will investigate primitive coupling metrics to explicitly model dependencies between EAPs during search."

1. Persistent reusable components instead of whole-program evolution.

Improvement: Decouple local logic from complete programs by representing it as executable algorithmic primitives (EAPs) stored in a persistent library.

Capability: The AI system can retain valuable code snippets even after their source algorithm is discarded, preventing useful logic from being repeatedly lost and rediscovered, and enabling cross-generation reuse.

2. Component-level credit assignment via bandit feedback.

Improvement: Model the utility of each primitive as a Bernoulli success rate (likelihood of improving a child over its parent), updated with a Beta posterior and selected via Thompson Sampling.

Capability: The system can attribute performance improvements to specific algorithmic components, not just entire algorithms, allowing it to distinguish useful vs. harmful local logic and make evidence-based decisions about which primitives to inject next.

3. Structural verification of primitive integration.

Improvement: Enforce required, preserved, and removed primitive call-sets using programmatic AST verification; reject candidates that violate the structural contract.

Capability: The system can prevent LLM hallucinations from corrupting empirical evidence, ensuring that only correctly integrated primitives contribute to utility updates and that search remains grounded in real executable behavior.

4. Primitive-aware variation operators with explicit boundaries.

Improvement: Use four operators—primitive insertion, primitive replacement, primitive-preserving refinement, and primitive-aware crossover—while strictly preserving or recombining primitive calls.

Capability: The system can systematically explore algorithmic compositions without breaking beneficial local logic: it can add a promising primitive, swap out a poorly performing one, refine interactions among fixed primitives, and recombine primitives from two parent algorithms.

5. Adaptive exploration/exploitation of primitive selection.

Improvement: Treat primitive injection as a multi-armed bandit; selected primitives influence generated children, and rewards update their posterior distributions; new primitives receive forced warm-up exposure.

Capability: The system can balance trying new or uncertain primitives against leveraging proven ones, automatically focusing search on high-utility components as evidence accumulates.

6. Dual mechanisms for primitive discovery.

Improvement: Generate new, functionally distinct primitives via LLM synthesis conditioned on top-performing existing primitives, and extract reusable logic from a historical best program via refactoring without altering it.

Capability: The system can continuously expand its primitive library both by inventing novel function types and by rescuing valuable local code from successful algorithms before they fade from the population—improving final solution quality on tasks like continuous control and combinatorial optimization.

7. Decoupling primitive discovery from host algorithm generation.

Improvement: Allow a separate, potentially stronger model to handle EAP discovery while the host algorithm generator remains cheaper; empirically, this costs on average only 1.6% of total token consumption.

Capability: The system can achieve substantial performance gains by upgrading only the primitive discovery component, without proportionally increasing computational cost—making it more efficient in resource-constrained settings.

8. Explicit modeling of primitive coupling and dependencies.

Improvement: Go beyond the independence assumption by measuring joint interaction effects between primitives, as the paper suggests for future work.

Capability: The improved system can avoid overestimating the value of primitives that only work well in particular combinations, enabling more accurate selection and composition in algorithms with complex interdependencies, and better generalization across problem scales.