Generalizable Self-Evolving Memory for Automatic Prompt Optimization

Motivation

• Existing APO methods search for prompts specialized to fixed task distributions, making optimization brittle and limiting transferable knowledge reuse.Shared reasoning structures such as decomposition, verification, and step-by-step deduction are not accumulated across tasks.Source: §1 · pp. 1–2

MemAPO

• MemAPO stores successful reasoning strategies and recurrent failure signals in a dual-memory framework for future prompt construction.Successful trajectories become reusable strategies, while incorrect generations become structured failure rules that discourage repeated mistakes.Source: §1 · p. 2
• MemAPO dynamically retrieves experiences for each query and uses self-reflection to generate new strategies and update memory when existing guidance is insufficient.This transforms prompt optimization from externally supervised search into an internally evolving capability.Source: §1 · p. 2

Results

• MemAPO consistently outperforms representative APO baselines across diverse benchmarks and model backbones while substantially reducing optimization cost.The framework amortizes optimization through experience reuse, reducing token consumption and API calls.Source: §1 · p. 2

Contribution

• The paper frames prompt optimization as self-evolving experience accumulation rather than searching for a task-specific optimal prompt.This perspective is presented as a way to internalize, store, and reuse prompting experiences across tasks.Source: §1 · p. 2

2.1 Automatic Prompt Optimization

• Text-gradient, trajectory-based, and evolutionary methods automate prompt refinement but generally rely on stronger external LLMs as optimizers.This dependency limits scalability and practical deployment.Source: §2.1 · p. 3, Figure 2 · p. 3

2.2 Self-Evolving Agents

• Self-evolving agents bootstrap performance through self-correction, iterative refinement, and memory-augmented retrieval of historical insights.These approaches address whether models can optimize themselves without external guidance.Source: §2.2 · p. 3
• Memory-based self-learning methods store concrete interaction trajectories or abstract historical interactions into higher-level rules and guidelines.The two categories distinguish episodic memory from more generalized memory abstraction.Source: §2.2 · p. 3

3.1 Problem Definition

• MemAPO models a prompt as invariant task instructions plus query-dependent memory augmentation retrieved from historical experience.This reframes optimization as accumulating, organizing, and retrieving reusable prompting knowledge across heterogeneous queries.Source: §3.1 · pp. 3–4

3.2 MemAPO Overview

• The framework has three stages: retrieve relevant memories, iteratively evaluate an augmented prompt, and consolidate new experiences into memory.During inference, it can retrieve memory and generate a response in one pass without the reflection loop.Source: §3.2 · p. 4

3.3 Dual Memory Mechanism

• MemAPO uses Correct-Template Memory for reusable successful strategies and Error-Pattern Memory for generalized recurring failure modes.Together they provide positive guidance and negative constraints during prompt construction; templates include applicability indices, strategies, and supporting cases.Source: §3.3 · pp. 4–5

3.4 Memory Retrieval

• For each query, CTM retrieves top-k templates by query–index embedding similarity above θcorr, whereas EPM retrieves all stored error patterns as global constraints.Retrieved error patterns discourage reproducing previously observed failure modes.Source: §3.4 · p. 5

3.5 Prompt Evaluation

• The augmented prompt combines task instructions with retrieved positive strategies and negative error constraints, then undergoes iterative evaluation and corrective reflection.Failed attempts add reflections to the context, and generation retries continue until success or the maximum retry limit.Source: §3.5 · p. 5

3.6 Memory Update

• After reasoning, successful interactions create or enrich CTM templates, while failed attempts are abstracted into EPM rules and merged or refined using semantic similarity.Template operations include ADD, UPDATE, DELETE, and NONE; updates are verified on sampled stored cases, and consolidation limits repository growth.Source: §3.6 · pp. 5–6

4.2 Experimental Results and Analysis

• 70.7% average performance on GPT-4o-mini surpasses TextGrad by 7.1% across heterogeneous tasks, while Qwen3-8B reaches 70.6% average accuracy.MemAPO also performs best on most Qwen3-8B datasets, indicating similar behavior across proprietary and open-source backbones.Source: §4.2 · pp. 6–7, Table 1 · p. 7
• 58.6% and 55.7% cost reductions versus TextGrad accompany superior performance on Qwen3-8B and GPT-4o-mini, respectively.MemAPO ranks second in optimization efficiency across methods, with the cost reduction attributed to experience reuse.Source: §4.2 · p. 7
• MemAPO maintains improvements across mixed-domain Gaokao MathQA and Gaokao History tasks, whereas most baselines degrade substantially, including SPO's 11.1% drop on Gaokao MathQA.The experiment uses GPT-4o-mini and tests whether one optimized prompt can reconcile conflicting mathematical and knowledge-intensive reasoning demands.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 Ablation Study

• CTM improves AQuA-RAT and Gaokao MathQA by 18.8 and 21.6, while EPM improves them by 16.2 and 20.8; combining both adds 2.0 and 1.2 further gains.The ablation supports using retrieved strategies and failure patterns together for reasoning guidance and mistake avoidance.Source: §4.3 · p. 8, Table 3 · p. 8
• Using GPT-4o-mini as optimizer retains 98.4% and 96.4% of GPT-5-optimizer performance for MemAPO, while stronger optimizers improve performance in 9/12 comparisons overall.Some baselines instead degrade on Gaokao MathQA, including PromptBreeder from 46.6 to 36.3 and OPRO from 49.4 to 47.0.Source: §4.3 · p. 8, Table 4 · p. 8
• Top-3 retrieved templates maximize performance on AQuA-RAT and Gaokao MathQA, while increasing template counts steadily increase inference token usage.Performance first improves and then declines as templates become excessive, motivating the selected balance between guidance and cost.Source: §4.3 · p. 8, Figure 4 · p. 8

• MemAPO progressively accumulates and reuses prompting knowledge across heterogeneous tasks through structured memories of successful strategies and failure signals.Retrieved experiences guide prompt construction and are refined through iterative self-reflection.Source: §5 · p. 8

• MemAPO focuses on textual reasoning tasks and language-based prompt optimization rather than multimodal information.Source: Limitations · pp. 8–9
• The framework does not explicitly model visual, audio, or structured environment signals.Source: Limitations · p. 9
• Extending the memory architecture to multimodal experiences may improve generality in broader agentic environments.Source: Limitations · p. 9

Dataset documentation

• The appendix reports dataset sizes and splits in Table 5, while all listed datasets are open for academic research under MIT or Apache 2.0 licenses.Source: §A.1 · p. 10, Table 5 · p. 11

Logical reasoning

• BBH-Geometric Shapes requires determining generated geometric shapes from SVG path commands.Source: §A.1 · p. 11
• BBEH-Geometric Shapes is harder than BBH because commands can draw multiple shapes and include many useless commands.Its data are randomly split into training, validation, and test sets with a 50:50:100 ratio.Source: §A.1 · p. 11

AGIEval tasks

• AGIEval uses AQuA-RAT and Gaokao-Math for mathematical calculation, plus Gaokao-Geography and Gaokao-History for knowledge-intensive reasoning.The described split samples 100 training and development examples with remaining samples reserved for testing.Source: §A.1 · p. 11

Baseline configurations

• The compared baselines include ProTeGi, OPRO, TextGrad, PromptBreeder, and SPO.Source: §A.2 · pp. 11–12

Text-gradient optimization

• ProTeGi uses textual gradients, beam search, and bandit selection to iteratively edit prompts.Source: §A.2 · p. 11

Iterative optimization

• OPRO generates candidate prompts over repeated rounds from prior prompts and performance scores in a meta-prompt.Source: §A.2 · p. 11

Gradient refinement

• TextGrad refines prompts through optimizer feedback and discards updates that reduce validation performance.Source: §A.2 · p. 11

Evolutionary and self-supervised methods

• PromptBreeder evolves task and mutation prompts across generations, whereas SPO performs self-supervised optimization without external ground-truth labels.Source: §A.2 · pp. 11–12

Framework configuration

• MemAPO is implemented on GPT-4o-mini and Qwen3-8B, using vector databases and Qwen3-Embedding-8B for semantic retrieval.Source: §A.3 · p. 12

Retrieval and reflection

• CTM retrieves top-3 templates, EPM retrieves all recorded error patterns, and self-reflection allows at most three retries.Source: §A.3 · p. 12

Memory updates

• Updated templates must succeed on three sampled cases, the template store is capped at 30, and excess templates trigger merging.Source: §A.3 · p. 12

Initial prompts

• The experiments use original BBH prompts for logical reasoning and “Let’s solve the problem” for mathematical and knowledge-intensive tasks.Source: §A.3 · p. 12

Cost reporting

• Table 7 compares averaged API calls, token consumption, and optimization costs across methods and both backbones.Source: Table 7 · p. 12

A.4 Experimental Environments Details

• Experiments use official model APIs, including an 8B language model and an 8B embedding model, with total API compute below one thousand US dollars.The implementation uses ChromaDB-based vector stores on a Linux system.Source: §A.4 · p. 12

A.5 More Experiments

• Table 7 reports averaged API calls, token consumption, and optimization cost for the computation-consumption analysis.Source: §A.5 · p. 12

A.6 Meta Prompt

• The appendix provides meta prompts for answering queries, self-reflection, template creation, template updating and merging, and error summarization and updating.These prompts support the prompting and memory-management procedures described in the main method.Source: §A.6 · p. 12, Figure 5 · p. 13, Figure 6 · p. 14

A.7.1 Scientific Artifacts

• The experiments cover English and Chinese questions in logical reasoning, mathematics, and knowledge-intensive question answering, with data manually reviewed to exclude personal-privacy content.The authors state that data sources and models are referenced officially and that code and results will be released with documentation.Source: §A.7.1 · pp. 12–13

A.7.2 Potential Risks

• The authors warn that experiment results should not be over-interpreted as evidence of real-world deployment readiness and that the system could be misused to generate harmful or misleading content.Source: §A.7.2 · p. 13

A.8 Use of AI Assistants

• The template-update prompt asks a manager to keep the retrieved template library accurate, non-redundant, and useful after a correct solution, while the merge prompt consolidates overlapping templates without losing coverage.The error-summarization prompt similarly seeks one generalizable error pattern from failed attempts and reflections to prevent similar mistakes.Source: §A.8 · pp. 16–18