Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery

The gist: EMO-STA, a shared-then-adapt framework, improves over matched-compute single-task evolution by evolving a reusable program archive across related tasks and then adapting selected candidates to individual tasks.

How it works

EMO-STA is introduced as an Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery, which addresses the limitation of existing methods that typically optimize each task independently, even when related tasks share reusable structure The paper introduces EMO-STA (Shared-Then-Adapt), a two-stage framework that first evolves a shared archive of executable programs across a task family and then adapts selected shared candidates to each target task This framework is applicable whenever related tasks can be expressed through a shared executable interface, which is enforced by defining a unified entry-point function and prompting the LLM to implement that format

The process involves two main phases: Shared Evolution and Adaptation Evolution. In the shared phase, the system optimizes against an aggregated family-level objective defined as sshared(p) = 1/K Σ si(p), which rewards generalizable programs This produces a shared archive of programs denoted by Ashared, where the goal is to obtain a set of candidate programs that can later be converted into task-local initializations for adaptation

In the adaptation evolution phase, EMO-STA constructs task-local initialization checkpoints from the shared archive using three variants:

1. STA Warmstart: transfers the entire shared program archive into the task-local archive and continues evolution from that population

2. STA Best-Shared: uses the program with the best average shared score across the family as the initial program for adaptation evolution

3. STA Best-Local: selects, for each target task, the shared program with the highest target-task score before adaptation and uses it as the initial program for adaptation

Empirical Evaluation and Results

EMO-STA was evaluated across eight task families spanning continuous optimization, geometric construction, modeling, and algorithmic optimization Across these families, EMO-STA improves over matched-compute single-task evolution in most settings Specifically, STA Best-Local is shown to be the most reliable in-distribution adaptation strategy across 23/40 cells Furthermore, allocating a substantial—and often roughly balanced—fraction of compute to shared evolution yields strong performance

The paper demonstrates that shared evolution can mitigate overfitting in low-evidence settings, such as ARC tasks and time-series feature engineering, by favoring programs that generalize across all tasks rather than exploiting task-specific brittle artifacts In the ARC case study, EMO-STA variants recover a substantial fraction of failed single-task cases when joint evolution is used over transformed task variants Similarly, in time-series feature engineering, STA Best-Shared without adaptation improves test MASE and wQL by 13.24% and 32.56%, suggesting that shared evolution acts as a regularizer by selecting transformations that must work across many related series

Compute Allocation and Generalization

The study investigates how a fixed family-level compute budget can be used more efficiently by comparing shared-then-adapt search against K independent single-task runs Results show that equal shared/adaptation compute splits are consistently strong, with a particularly effective allocation recipe being to split compute roughly evenly between shared evolution and adaptation

Regarding generalization to held-out task sizes, the paper finds that STA Best-Shared gives the strongest held-out transfer across geometric families This suggests that the best shared evolution program often captures the most transferable family-level structure, even when STA Best-Local is stronger for in-distribution adaptation

Program Structure and Adaptation Modes

The paper illustrates two distinct adaptation modes through representative program examples, showing how shared evolution discovers a reusable geometric solver scaffold while task-local adaptation calibrates it to the target task For circle packing, the adapted program retains the main computational template discovered during shared evolution but makes the search more specialized for the target circle count In signal processing, adaptation refines behavioral trade-off adjustments encoded in the algorithm rather than refining a geometric optimizer

The paper concludes that EMO-STA offers an effective multi-task evolutionary search method that converts shared structure across related problems into stronger and more generalizable LLM-discovered programs The framework is most appropriate when tasks share meaningful program structure, and it would be desirable to handle arbitrary task sets by automatically grouping them

Related Work Context

EMO-STA is positioned as closest in spirit to evolutionary multitasking literature, but it differs in the object being transferred, evolving full executable programs rather than shared vectors or chromosomes It connects to adaptation literature by performing adaptation at the level of executable programs after shared evolution identifies reusable candidates The framework builds on prior work in evolutionary search over programs and multi-task learning that focuses on sharing inductive biases or representations, but its contribution is organizing related discovery tasks around a shared program interface

The paper's experiments are grounded in specific task families, including function minimization (e.g., Rastrigin), signal processing (e.g.

1. Shared Program Discovery for Multi-Task Efficiency: The EMO-STA framework can discover reusable program structure across a task family by running shared evolution with aggregate objective sshared(p) = 1/K sum i=1 si(p), producing a shared archive Ashared of programs. This allows the system to learn a general-purpose solution as it requires the LLM to write a single program that applies to all tasks simply by varying task-specific parameters.

2. Optimized Task Specialization: The system can achieve superior performance on individual tasks by employing STA Best-Local, which selects, for each target task, the shared program with the highest target-task score before adaptation and uses it as the initial program for local evolution. This results in a final score that is often significantly higher than single-task baselines, as shown by the example where adaptation raises the family average far above the matched single-task baseline.

3. Robust Transfer to Unseen Tasks: By utilizing STA Best-Shared, the system can achieve robust transfer to unseen tasks because it uses the program with the best average shared score across the family as the initial program for task-local evolution. This strategy is highlighted as being particularly strong in out-of-distribution evaluations, suggesting that the best shared evolution program often captures the most transferable family-level structure.

4. Overfitting Mitigation in Low-Evidence Settings: The system can mitigate overfitting by favoring generalizability by showing that "shared evolution can mitigate overfitting in low-evidence settings (e.g. few training data), including ARC tasks and time-series feature engineering, by favoring programs that generalize across all tasks rather than exploiting task-specific brittle artifacts. This regularization effect is demonstrated when EMO-STA variants recover a substantial fraction of failed single-task cases" in the ARC case study.

Recent LLM-guided evolutionary search methods have shown that iterative program mutation can discover strong algorithms, but they typically optimize each task independently, even when related tasks share reusable structure. We study evolutionary multitask optimization (EMO) for LLM-guided program discovery and propose EMO-STA (Shared-Then-Adapt), a two-stage framework that first evolves a shared archive of executable programs across a task family and then adapts selected shared candidates to each target task. Within EMO-STA, we explore multiple adaptation strategies, including warm-starting from the shared archive, adapting the best average shared program, and adapting the shared program that performs best on each target task. Across eight task families spanning continuous optimization, geometric construction, modeling, and algorithmic optimization, EMO-STA improves over single-task evolution under matched evolutionary-iteration budgets in most settings, with STA Best-Local providing the strongest in-distribution adaptation and STA Best-Shared yielding robust transfer to unseen tasks. Iteration-allocation experiments show that devoting a substantial fraction of the family-level iteration budget to shared evolution is effective, with roughly balanced shared and aggregate adaptation budgets often yielding the best performance. ARC and time-series feature-engineering case studies further suggest that shared evolution can mitigate overfitting in low-evidence settings by favoring programs that perform well across related tasks rather than exploiting brittle task-specific artifacts.