# ε-MemEvo: Adaptive Cross-Task Memory Transfer for LLM Program Evolution

> ε-MemEvo enables safe cross-task knowledge transfer in LLM-based program evolution via an adaptive Thompson-sampling gate, achieving 8/8 AUCC wins with +8.7% mean improvement while preventing catastrophic negative transfer.

- **Source:** [arXiv](https://arxiv.org/abs/2608.12522)
- **Published:** 2026-08-17
- **Permalink:** https://picx.dev/p/jnkmPQ
- **Whiteboard:** https://picx.dev/p/jnkmPQ/image

## Summary

## Summary (Overview)

- **ε-MemEvo** is a framework for cross-task knowledge transfer in LLM-based program evolution, addressing the "amnesic" behavior of existing systems like FunSearch and AlphaEvolve that discard search experience after each task.
- The framework introduces two key components: a **Tactic Memory Bank** storing task-agnostic natural-language strategy summaries (not raw code), and an **Adaptive Injection Gate** using Thompson sampling to decide whether/when to inject retrieved memories, primarily to prevent negative transfer.
- On 8 diverse optimization benchmarks, ε-MemEvo achieves higher AUCC on all 8 tasks (p = 0.0078) with +8.7% mean relative improvement on GPT-5 and +11.7% on Gemini-3-Pro, with early-stage convergence (AUC@20) improving by +9.4% on average.
- Ablations reveal that naive always-inject and rule-based stagnation policies cause catastrophic failures (AUCC = 0) on 2/5 tasks, while the adaptive gate remains safe on all tasks.
- The framework incurs < 1% computational overhead per iteration and reduces aggregate wall-clock time to 0.69× that of the AdaEvolve baseline.

## Introduction and Theoretical Foundation

LLM-based program evolution systems have demonstrated remarkable capability in automated algorithm discovery. Systems like FunSearch (Romera-Paredes et al. 2024) and AlphaEvolve (Novikov et al. 2025) iteratively generate, evaluate, and refine programs, achieving breakthroughs in combinatorial optimization and scientific computing. AdaEvolve (Cemri et al. 2026) further introduces adaptive island models and paradigm breakthroughs.

However, a fundamental limitation persists: **every task starts from scratch**. When an evolution system finishes one optimization task and moves to a related task, it retains no memory of which strategies worked, no intuition about search structure, and no reusable heuristics. This leads to:
- Redundant exploration across related tasks
- Slow cold-start convergence
- Wasted API budget

The key insight of ε-MemEvo is that **cross-task transfer in evolutionary coding is a safety problem, not a retrieval problem alone**. Naïvely injecting cross-task strategies can cause catastrophic negative transfer—in ablations, two of five tasks fail to produce any score-improving program under always-inject policies.

## Methodology

### Problem Formulation

The system solves tasks $\mathcal{T} = \{T_1, \ldots, T_N\}$, where each task $T_i$ has description $d_i$, evaluation function $f_i: \mathcal{P} \to \mathbb{R}$, and seed program $\bar{p}_i^0$. ε-MemEvo augments the standard setting with a persistent memory state $\mathcal{M} = (B, \pi)$ comprising:
- **Tactic Memory Bank B**: stores strategy summaries from prior tasks
- **Injection Policy π**: updated during each task, carried forward

### Tactic Memory Bank

**Strategy extraction** (after successful task completion):

$$
\operatorname{tactic}_i = \operatorname{LLM}_{\text{extract}}\left(d_i, p_i^{\text{best}}, f_i\left(p_i^{\text{best}}\right)\right)
\tag{1}
$$

The extraction prompt asks for general algorithmic descriptions (e.g., "two-phase optimization with greedy initialization followed by gradient descent") rather than task-specific code.

**Semantic retrieval** uses score-weighted cosine similarity:

$$
r_k = \cos(\mathbf{e}_j, \mathbf{e}_k) \cdot (1 + 0.3 \cdot \log(1 + \max(\Delta_k, 0.01)))
\tag{2}
$$

where $\Delta_k$ is the score improvement of entry k's strategy over its baseline; top-3 entries are returned.

### Adaptive Injection Gate

The gate is a **contextual bandit with Beta-distributed arms** updated by Thompson sampling, designed primarily as a gate against negative transfer.

**State space**: Six discrete states from two features:
- Search phase ∈ {improving, plateau, stagnating} from global improvement rate $\rho = \frac{\text{improvements}}{\text{evaluations}}$ (ρ > 0.1 ⇒ improving; 0.02 < ρ ≤ 0.1 ⇒ plateau; ρ ≤ 0.02 ⇒ stagnating)
- Task stage ∈ {early, late}, where t/M < 0.4 is early

**Action space** (three injection intensities):
- **skip**: no injection, base prompt
- **hint**: retrieved strategies as optional references
- **guide**: top strategy as recommended approach plus injection into paradigm breakthrough generation

**Informative priors**: Prior(improving, skip) = Beta(3, 1) and Prior(stagnating, guide) = Beta(3, 1), with Beta(1, 1) for other pairs.

**Decision and reward**: At each iteration, sample $\theta_{s,a} \sim \text{Beta}(\alpha_{s,a}, \beta_{s,a})$ and pick $a^* = \arg\max_a \theta_{s,a}$. The reward is delayed with window w = 5 iterations: $R_t = \mathbb{1}[f_{t+w}^* > f_{\text{pre}}^* + \epsilon]$ with $\epsilon = 10^{-8}$.

### Leave-One-Out (LOO) Evaluation Protocol

When evaluating on task $T_k$: (1) memory bank $B_{-k}$ excludes entries from $T_k$; (2) policy π retains its full posterior (task-agnostic state-action mappings); (3) all methods share the same seed program and evaluator.

## Empirical Validation / Results

### Main Results (Final Scores, Table 1)

| Task | ε-MemEvo (GPT-5) | AdaEvolve (GPT-5) | Δ% | ε-MemEvo (Gemini) | AdaEvolve (Gemini) | Δ% |
|------|------------------|-------------------|-----|--------------------|--------------------|-----|
| circle_packing | 0.9756 | 0.9524 | +2.4% | 0.9761 | 0.9534 | +2.4% |
| signal_processing | 0.7227 | 0.7057 | +2.4% | 0.6685 | 0.5998 | +11.5% |
| first_autocorr_ineq | 0.9936 | 0.9913 | +0.2% | 0.9191 | 0.8426 | +9.1% |
| uncertainty_ineq | 0.9024 | 0.8938 | +1.0% | 0.8347 | 0.7597 | +9.9% |
| eplb | 0.2171 | 0.1487 | **+46.0%** | 0.2260 | 0.1609 | **+40.5%** |
| llm_sql | 0.7247 | 0.7047 | +2.8% | 0.7232 | 0.7019 | +3.0% |
| prism | 26.256 | 26.266 | −0.04% | 26.230 | 26.213 | +0.06% |
| txn_scheduling | 4032.3 | 2777.8 | **+45.2%** | 3987.9 | 2716.0 | **+46.8%** |

### Convergence Efficiency (Table 2)

- **AUCC**: Wins on all 8 tasks (mean +8.7% GPT-5, +11.7% Gemini-3-Pro); largest gains on txn_scheduling (+37.3%/+38.8%) and EPLB (+17.9%/+13.3%)
- **AUC@20**: Cold-start improves on 7/8 tasks (mean +9.4%/+12.6%); largest GPT-5 gains: circle_packing (+26.0%), txn_scheduling (+27.2%)
- **T₉₀%**: On GPT-5, reaches 90% faster on circle_packing (3 vs. 9, 3.0×), PRISM (2 vs. 17, 8.5×), signal_processing (15 vs. 23, 1.5×)

### Statistical Significance

- Paired Wilcoxon signed-rank: p = 0.0078 (minimum possible at n=8)
- Bootstrap 95% BCa CI on mean relative improvement: [+2.9%, +21.4%]
- Cohen's $d_z = 0.675$ (medium effect)

### Ablation Study (Table 3)

| Task | ε-MemEvo | always | stagnation | AdaEvolve | TopK |
|------|----------|--------|------------|-----------|------|
| circle_pack | 0.928 (+9.9%) | 0.942 (+11.5%) | 0.957 (+13.4%) | 0.845 | 0.781 |
| eplb | 0.129 (+1.3%) | **0.000** | **0.000** | 0.127 | 0.122 |
| signal | 0.639 (+2.9%) | 0.599 (−3.5%) | 0.646 (+4.0%) | 0.621 | 0.421 |
| txn_sched | 3647 (+34.0%) | 4227 (+55.3%) | 3548 (+30.3%) | 2722 | — |
| llm_sql | 0.700 (+1.3%) | **0.000** | **0.000** | 0.691 | 0.652 |
| **Avg. Δ%** | **+9.9%** | −27.4% | −30.4% | 0% | −12.3% |
| Safe tasks | **5/5** | 3/5 | 3/5 | 5/5 | 4/4 |

**Red = catastrophic failure (AUCC = 0)**. Both naive always-inject and rule-based stagnation fail catastrophically on EPLB and LLM-SQL.

### Policy Analysis

- **Data-updated posterior hierarchy**: improving → skip, plateau_early → skip, plateau_late → hint; unobserved stagnating states retain prior-initialized guide action
- **Reward rates** (improving_early states): skip = 39.6% (99/250), hint = 34.0% (17/50), guide = 19.7% (15/76)—over-injection during productive search actively harms performance
- **Negative transfer avoided**: On EPLB, the closest retrievable memory (from LLM-SQL, cosine 0.481) prescribes SQL-style grouping; the adaptive gate's guide-arm posterior collapses after failures, reverting to skip

## Theoretical and Practical Implications

### Theoretical Safety Guarantee

Specializing the standard regret bound for Bernoulli Thompson sampling shows that when retrieved tactics are mismatched (so $p_{\text{skip}} > p_{\text{guide}}$ in a fixed search state), the expected number of guide pulls satisfies:

$$
\mathbb{E}[T_{\text{guide}}(T)] \leq C \log T / \Delta_{\text{guide}}^2 + o(\log T)
$$

so the per-round probability of injecting a harmful tactic decays as O(1/t). In synthetic validation over T=500 rounds, guide selection frequency falls below 5% by t ≈ 100 in the mismatched setting.

### Why Thompson Sampling?

The gate needs to support:
- Delayed binary rewards
- Informative Beta priors
- Rapid suppression of harmful actions

Fixed ε-greedy continues selecting every arm with nonzero probability even after repeated failures; UCB1 has no natural mechanism for incorporating state-specific priors. Thompson sampling is the only tested controller combining near-lowest regret in both matched and mismatched regimes with vanishing harmful-arm selection rate.

### When Does Transfer Help Most?

1. Memory bank contains strategies from semantically related tasks (similarity ≥ 0.5)
2. Target task has a smooth fitness landscape
3. Search is in early stages (AUC@20 gains exceed full-horizon AUCC gains)

### Computational Overhead

ε-MemEvo adds ~0.77 s per iteration (< 1% of the 80–140 s baseline). Wall-clock time is faster on 5/8 main tasks, with aggregate ratio of **0.69×** relative to AdaEvolve.

## Conclusion

ε-MemEvo formalizes cross-task knowledge transfer as an adaptive intervention problem in LLM-based program evolution. Key contributions:

1. **Tactic Memory Bank** enables content-level transfer via task-agnostic natural-language strategy summaries
2. **Adaptive Injection Gate** provides strategy-level transfer control, preventing catastrophic negative transfer
3. **Statistically significant improvements** across 8 benchmarks (p = 0.0078, 8/8 AUCC wins, +8.7% average improvement)
4. **Interpretable policy**: data favor skip in improving/early-plateau states, hint in late-plateau states, with unobserved stagnating states retaining prior-initialized guide action

**Limitations and future directions**:
- Only two LLM backbones evaluated (GPT-5, Gemini-3-Pro)
- Memory bank built at task level; scaling behavior to hundreds of entries unknown
- ε-MemEvo augments rather than replaces the base framework—cannot compensate for fundamental exploration failures
- A stronger rule-based control (stagnation-triggered injection with k-strike autodisable) is an important missing ablation
- Next steps: larger/diverse banks, hierarchical memory, transfer across base frameworks and weaker LLM backbones

---

_Markdown view of https://picx.dev/p/jnkmPQ, served by PicX — AI-generated visual whiteboard summaries of research papers._