2608.07395-PACE: Primitive-Aware Code Evolution for Automated Algorithm Design

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "PACE: Primitive-Aware Code Evolution for Automated Algorithm Design".

Jane: The paper was written by Zhuoliang Xie, Ruihao Zheng, Xiang Xu, Genghui Li and Zhengkun Wang from Southern University of Science and Technology and Shenzhen University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: The paper on the table this episode is about automated algorithm design with large language models, and it challenges a core assumption in that field. The standard search loop evolves complete programs and treats each one as a single indivisible unit, so when a program scores badly the whole thing gets thrown away, including chunks of logic that might be genuinely useful somewhere else.

Jane: So the search is losing good code along with the bad host program, and then it has to rediscover the same ideas later?

Tom: Exactly, and the paper calls that a direct waste of the evaluation budget. Their fix is to store useful local logic as separate callable functions, which they call executable algorithmic primitives. Those primitives live in a persistent set, and completely different algorithms can call them even after the program that produced them has been eliminated.

Lu: The selection machinery is what caught my attention. Each primitive keeps a Beta posterior that tracks how often it improves the child relative to its parent, and Thompson sampling decides which primitive gets injected into the next candidate.

Jane: So the evidence for a primitive is just whether the child beat its parent after the injection. That's remarkably cheap because it costs no extra evaluation budget.

Meng: And the numbers make the case. On Racing Car their approach reached 98 point 90 on test, beating the neural PPO baseline at 85 point 69. On Bipedal Walker the whole-program baselines mostly collapsed to near zero or negative scores, while their method reached 133 point 71 on test.

Lalam: Stepping back, this is a meaningful shift in philosophy for program search. Instead of evolving a monolithic program and hoping the good pieces survive, you compose systems from components that carry their own history and lifetime. The combinatorial optimization results support that framing, because their evolved TSP heuristics generalize to much larger instances than any baseline search method.

Tom: Right, on TSP-ACO at a thousand nodes they got 28 point 13, while MCTS-AHD, which was competitive in-domain, collapsed to over 50. Modular search isn't just competitive, it transfers.

Jane: That's the arc of the paper — persistent components plus evidence-based transfer. Over the next segments we'll look at how the authors actually built it, starting with their opening argument about why whole-program evolution keeps throwing good code away.

Page 1 of the paper: Tom: So we've established the headline — preserve useful code as primitives and the search stops wasting effort. Page one zooms into exactly how the waste happens, with a concrete example: a car controller that returns steering, gas, and brake.

Jane: That example hit me. One version scores 0 point 88 and gets eliminated, while a different version scores only 0 point 08. The evaluator can't see inside either program, so the 0 point 88 version disappears along with whatever made it good.

Tom: Right, and the authors press on that point the whole way through. Existing variation operators let the LLM edit the algorithm anywhere with no explicit boundaries, so nothing protects a useful local change from being deleted alongside a harmful one. That's the coarse-grained perspective they're arguing against.

Lu: They also make a sharp observation about the search dynamics. Because useful logic keeps getting discarded, the search has to rediscover it later, and that repetition burns budget and caps the final performance. It's a memory failure as much as a search failure.

Meng: The contrast figure says it all. In the existing approach, a low-scoring algorithm takes its local logic down with it. In theirs, a function from that program gets stored as a primitive, and a later algorithm calls the same function and scores better, even though the original program is long gone.

Jane: So the component becomes an evolvable object. At the code level it's just a callable function, but conceptually it's a unit the search can keep and accumulate evidence about.

Tom: And the paper sets the terms carefully from the start. A promising primitive enters the persistent set with an undetermined utility value, and that value updates as it competes with the primitives already there. Primitives with higher utility get included in newly generated algorithms more often, which means the whole set behaves like a shared toolbox for everything the search produces later.

Lalam: Notice that the evaluator still only sees complete algorithms. Nothing about the objective changes — what changes is what the search remembers between evaluations. That's a surprisingly light intervention with large consequences, and the next pages show where the idea sits in the literature.

Page 2 of the paper: Tom: Page two is the related work, but the authors use it to sharpen their own claim. They walk through the main lines of LLM-based algorithm design — reflective methods, tree search, diverse populations — and every one of them still evolves the complete program as the minimal unit.

Jane: So even the sophisticated frameworks carry the same limitation? The memory lives in reflections or search trees, but the algorithm itself stays atomic?

Tom: Exactly. Then they move to the reuse literature, and there the mismatch is different. Skill libraries like DreamCoder and Voyager do store reusable sub-programs, but they accept components based on binary pass-or-fail tests. Algorithm design doesn't work that way — quality is a continuous score and it depends heavily on the task context.

Lu: There's also a cluster of recent algorithm design methods that reuse structure, like EvoLattice and BEAM, and the paper's critique is that they rely on predefined candidate roles or heavy nested search loops. Their own approach instead treats primitives as independent evolutionary units with no extra search overhead.

Meng: Then comes the bandit connection. Credit assignment has been framed as a bandit problem before, but those setups put the arms over full programs or fixed operators. Their method does something different — the arm set is an open pool of primitives that grows during the search.

Jane: I appreciated that they name the core difficulty before offering the fix. When a primitive executes inside a host program, the host's quality can mask what the primitive actually contributed. So the reward has to be relative to the parent, not absolute.

Tom: That's the bridge to the method. They define a trial as a parent, a child, and one injected primitive, and the reward is whether the child improved over its fixed parent. No extra validation set, no additional evaluation calls.

Lalam: It's a classic credit assignment problem, but the interesting move is to make the primitive itself the arm in the bandit. That reframing is what allows evidence to accumulate across completely different host programs, and it sets up the formal machinery on page three.

Page 3 of the paper: Tom: So the related work sets up the gap, and page three makes the proposal precise. An executable primitive is defined as a pair — a textual description plus the executable function. And the implementation stays fixed when the primitive moves between algorithms; modifying it defines a different primitive.

Jane: That stable identity is what lets evidence accumulate. Every time that exact function gets transferred, the same object collects another data point about its transfer behavior.

Lu: The paper also separates availability from use. A primitive can sit in the set without being called by any current program, and a program only counts as using a primitive if it explicitly invokes it. That distinction keeps the accounting precise.

Meng: What I find reassuring is that the search objective doesn't change at all. You're still maximizing the evaluator score under a finite budget, and the evaluator only ever sees complete algorithms. Primitives have no separate objective of their own.

Tom: Right, the whole contribution lives in the search state — the population, the persistent primitive set, and the evidence history. The primitive set influences which functions get exposed to the next variation step, and nothing more. There's even a persistence guarantee written into the formalization: if a primitive is in the set at one step, it's still there at the next.

Jane: So population selection can eliminate the host algorithm, but the primitive survives. That's the property that makes cross-program transfer possible at all.

Lalam: The overview figure shows the two loops running side by side — complete algorithms go through parent selection, generation, and evaluation, while the primitive process handles discovery, selection, and evidence updates. The loops only couple through the evaluated algorithms, which is a clean architecture.

Tom: And that coupling is deliberately minimal, because the primitives never get evaluated directly — they only get exercised inside complete algorithms. The next page shows how those exercises turn into decisions about which primitives deserve another chance.

Page 4 of the paper: Tom: Page four builds the decision machinery. Each transfer trial produces a binary reward — one if the child strictly beats its parent, zero otherwise — and that outcome updates a Beta posterior for the primitive, starting from a uniform prior.

Jane: And then Thompson sampling draws one sample from each posterior and picks the primitive with the highest draw. So a primitive that often helps gets chosen often, but one with high uncertainty still gets explored.

Lu: There's a safeguard in the update rule that deserves attention. If the LLM fails to structurally integrate the primitive into the child, the trial is marked invalid and the posterior doesn't move. The system won't penalize a primitive for a generation failure it didn't cause.

Meng: New primitives also get a forced warm-up before they face normal selection. Otherwise a fresh primitive with an uninformative prior would rarely get chosen against established ones.

Tom: Then come the operators. Insertion brings in one primitive the parent wasn't using while preserving every primitive the parent already called. Replacement trades one called primitive for a different one, and the removal target is the called primitive with the lowest posterior mean.

Jane: Wait, so the replacement operator picks the weakest current primitive and lets a sampled challenger take its slot?

Tom: Yes, and because exactly one primitive was introduced, the parent-child comparison produces a focused observation for that single injection. That's what makes the credit assignment clean. The child also has to respect a maximum number of primitives per algorithm, so the context stays manageable.

Lalam: This is the whole philosophy in miniature. You engineer the variation so the attribution is unambiguous, rather than trying to evaluate the primitive in isolation. It's like running a controlled experiment inside the search, and page five carries that logic through the remaining operators.

Page 5 of the paper: Tom: Page five completes the toolkit. The third operator, refinement, fixes the primitive set and asks the LLM to improve how the algorithm uses it — the ordering of calls, the parameters, the interactions around them. Since nothing new enters, there's no posterior update.

Jane: So refinement separates two questions that could easily get tangled: which primitives to combine, and how to make the host algorithm work well with them. The ablations later show that distinction really matters.

Lu: The fourth operator is crossover. It takes two parents, exposes the union of their primitives, and the child must inherit at least one primitive from each parent while staying under the maximum capacity. The LLM can rebuild the surrounding structure, but the inheritance constraints are strict.

Meng: And those constraints are enforced programmatically with an AST verifier. The structural contracts aren't just prompts the model might follow — the system parses the generated code, checks the call sets, and discards anything that violates the contract before it can corrupt the evidence.

Tom: Then there's the discovery pipeline. Generation asks the LLM to synthesize a functionally distinct primitive, conditioned on the task description and the top-performing existing primitives. Extraction takes a newly found history-best algorithm and refactors one piece of its internal logic into a standalone function, without re-evaluating it.

Jane: And those two routes are mutually exclusive — at most one proposal per generation, with extraction getting priority. That cap keeps the primitive library compact and prevents the search from bloating.

Lalam: The governance detail is easy to overlook but genuinely important. A persistent library can be an asset and a liability at the same time; controlling how fast it grows is what keeps the search stable over a thousand evaluations. With the method fully assembled, page six runs it on four benchmarks.

Page 6 of the paper: Tom: Page six runs the full system against the field. All the LLM search methods share the same generation model, three independent runs, and a thousand evaluations each. Their method has exactly one parameter, k, set to three.

Jane: Racing Car jumps out first. Their approach trains to 92 point 40 and tests at 98 point 90, which beats every other program search baseline and even the neural PPO baseline at 85 point 69 on zero-shot generalization. The convergence curves show it pulling ahead within the first two hundred evaluations.

Lu: Bipedal Walker is the starker result. Program search struggles badly there — most baselines hover around zero or go negative, and EoH overfits from 48 point 06 in training down to minus 2 point 61 on test. Their method reaches 67 point 06 in training and 133 point 71 on test, far ahead of the specialized MLES cold-start at 15 point 42.

Meng: On TSP-ACO the pattern is different. In-domain at fifty nodes, their result is essentially tied with the best baseline — 5 point 795 against ReEvo's 5 point 774. But scale the same program to a thousand nodes and the gap opens dramatically: their cost is 28 point 130, while MCTS-AHD collapses to 50 point 291, worse than classical ant colony optimization.

Jane: And on TSP-Construct it leads at every scale, from 6 point 013 at fifty nodes to 26 point 596 at a thousand. So the primitives learned at small scale keep working when the problem grows.

Lalam: That transfer result is the most consequential part of the evaluation. The evolved components appear to capture something structural about the routing problem rather than memorizing the training instances. Modularity isn't just helping the search find good scores, it's helping the final programs generalize.

Tom: These control environments are notoriously hard for programmatic search in general, so the fact that the modular approach is the one that finally works on Bipedal Walker says something about the composition of primitives adding real robustness. But the paper also checks whether every piece of the design earns its place, and that's page seven.

Page 7 of the paper: Tom: Page seven checks whether every design choice earns its keep, starting with the selection rule. If you replace Thompson sampling with random primitive selection, Racing Car drops from 92 point 40 to 85 point 06. Preserving primitives isn't enough — you need to pick the right one to transfer.

Jane: The operator ablation is even more decisive. Removing any of the four operators hurts, but refinement is the critical one; without it, Racing Car crashes to 79 point 41. Finding the right primitive combination only pays off if you can tune how the surrounding algorithm uses it.

Lu: Both discovery routes matter too. Removing extraction degrades both tasks, and removing generation costs a noticeable chunk on Racing Car. The TSP score barely moves without generation — the paper flags that as within noise — but on at least one hard task the module earns its place.

Meng: The sensitivity analysis for k is clean. With one, the algorithms are too restricted. With five, the context gets cluttered with too many primitives. Three hits the balance.

Tom: Then there's the model robustness study, which I think is one of the most actionable results in the paper. They keep generation on the base model but upgrade only the primitive discovery model, and the score climbs to 94 point 60. Run the whole system on Gemini, and Racing Car hits 99 point 005, essentially the ceiling of a hundred.

Jane: And the discovery phase only consumes about 1 point 6 percent of the total tokens. A tiny share of the pipeline delivers a disproportionate gain. That's a very practical argument for separating discovery from generation.

Lalam: So the ablation story reinforces the architecture at every layer — the selection rule, the refinement operator, the discovery routes. The measurements support the modular design rather than just the rhetoric, and that sets up the closing argument nicely.

Conclusion: Tom: So to close the loop — the paper's proposal is simple at heart. Store useful algorithmic pieces as persistent callable functions, transfer them through carefully constrained operators, and let Thompson sampling decide which ones deserve more exposure.

Jane: And across two control tasks and two combinatorial optimization tasks, that modular strategy found better programs under the same evaluation budget, with notably better out-of-domain generalization. The ablations back up the design too, so the wins aren't coming from a single trick.

Lu: The limitation they flag is worth taking seriously. The framework assumes primitives can be evaluated and selected independently, but in algorithms with tightly coupled components, the joint interactions might not be captured by individual transfer trials.

Meng: Which points to the natural next step — modeling dependencies between primitives during the search. They mention primitive coupling metrics as the direction for future work.

Lalam: The broader impact is a change in mindset for program search. Instead of treating the algorithm as an atomic unit, you treat it as a composition of modules that can outlive their originating programs. That idea reaches well beyond algorithm design, into any setting where code is evolved against a score.

Tom: And the evidence that it works — beating neural policies on racing car, producing the strongest programmatic controller on bipedal walker, generalizing across problem scales — makes the case that the modular philosophy delivers real gains rather than just conceptual elegance.

Jane: Agreed. That's a good place to leave this one. We'll take a short break and come back with the next paper on the stack.