Automatic prompt optimization is a promising approach for adapting large language models (LLMs) to downstream tasks, yet existing methods typically search for a specific prompt specialized to a fixed task. This paradigm limits generalization across heterogeneous queries and prevents models from accumulating reusable prompting knowledge over time. In this paper, we propose MemAPO, a memory-driven framework that reconceptualizes prompt optimization as generalizable and self-evolving experience accumulation. MemAPO maintains a dual-memory mechanism that distills successful reasoning trajectories into reusable strategy templates while organizing incorrect generations into structured error patterns that capture recurrent failure modes. Given a new prompt, the framework retrieves both relevant strategies and failure patterns to compose prompts that promote effective reasoning while discouraging known mistakes. Through iterative self-reflection and memory editing, MemAPO continuously updates its memory, enabling prompt optimization to improve over time rather than restarting from scratch for each task. Experiments on diverse benchmarks show that MemAPO consistently outperforms representative prompt optimization baselines while substantially reducing optimization cost.
Figures & tables
Figure 1: Comparison between MemAPO and existing works. (a) Existing paradigm: an external LLM iteratively refines prompts for one specific task. (b) MemAPO: self-organizes reusable memories across multiple tasks.
Figure 2: Comparison of performance and optimization costs across six automatic prompt optimization methods, six tasks, and two backbones. MemAPO achieves the best average performance across all datasets on both backbones, while notably reducing cost by approximately 57.2% compared to the strong baseline TextGrad.
Figure 3: Overall illustration of MemAPO. (I) Memory Retrieval: it first retrieves relevant strategies and failure patterns according to the given query. (II) Prompt Evaluation: Then, the augmented prompt is constructed and iteratively evaluated. (III) Memory Update: Newly acquired experiecnes are consolidated into memory.
Table 1: Main comparison results across three domains. Tasks from similar domains are merged into a unified training set, and the optimized prompt is evaluated separately on each task. All methods use the same model for both prompt optimization and evaluation, and experiments are conducted on Qwen3-8B and GPT-4o-mini, respectively. GeoShape refers to the “Geometric Shapes" task, Avg. Perf and Avg. Cost refers to the average performance and the average optimization cost, respectively.
Method
Gaokao MathQA
Gaokao History
IO
39.4
71.9
CoT
35.5
67.4
StepBack
41.8
60.7
Rephrase
38.6
58.5
ProTeGi
45.0
53.3
OPRO
56.2
67.4
Table 2: Cross-domain (Gaokao MathQA and Gaokao History) experiment using GPT-4o-mini.
Correct Template Memory
Error Pattern Memory
AQuA-RAT
Gaokao MathQA
✗
✗
61.7
39.4
✗
✓
77.9
60.2
✓
✗
80.5
61.0
✓
✓
82.5
62.2
Table 3: Ablation study on the effect of dual memory components in MemAPO using GPT-4o-mini.
Method
AQUA-RAT
Gaokao MathQA
GPT-4o-mini
GPT-5-Chat
GPT-4o-mini
GPT-5-Chat
ProTeGi
76.0
82.5
45.0
50.6
OPRO
79.2
79.2
49.4
47.0
TextGrad
79.9
81.8
56.2
60.2
PromptBreeder
78.6
80.5
46.6
36.3
SPO
77.9
79.2
47.0
63.3
Table 4: Ablation study on the effect of self-evolving paradigm. We compare performance across different LLMs for prompt optimization while adopting GPT-4o-mini for prompt evaluation.
Figure 4: Ablation study on the impact of template number with GPT-4o-mini.
Table 7: Comparison of averaged API calls, token consumption, and optimization costs across different methods and backbones on Qwen3-8B and GPT-4o-mini.