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.
System prompt optimization improves agent behavior without modifying the underlying model, yielding human-readable, model-agnostic instructions. Existing methods build a prompt agent that refines task agents' system prompts, yet leave the prompt agent's own system prompt hand-engineered and fixed. We propose Self-Evolving Prompt Optimization (SePO), which treats the prompt agent's own system prompt as an optimization target alongside task agents' system prompts. SePO adopts a self-referential design. A single prompt agent improves both task agents' system prompts and its own under an open-ended evolutionary search that maintains an archive of candidate prompts as stepping stones. Training proceeds in two stages: pre-training evolves the prompt agent on a multi-task pool, and fine-tuning then applies it to a target task. Across five benchmarks spanning math (AIME'25), abstract reasoning (ARC-AGI-1), graduate-level science (GPQA), code generation (MBPP), and logic puzzles (Sudoku), SePO consistently outperforms Manual-CoT, TextGrad, and MetaSPO, improving the average accuracy by 4.49 points compared to Manual-CoT. The prompt optimization skill from pre-training also generalizes to tasks beyond the pre-training mixture, rather than memorizing per-task prompts.
Wangcheng Tao, Han Wu, Weng-Fai Wong
National University of Singapore · City University of Hong Kong
Large Language Models are highly sensitive to prompt formulation, necessitating automatic prompt optimization to unlock their full potential. While evolutionary algorithms have emerged as the dominant paradigm, they suffer from a critical bottleneck: data efficiency. Current methods treat the development dataset as a static benchmark, wasting significant compute budget on uninformative data. In this work, we introduce APEX (Automatic Prompt Engineering eXpert), a novel framework that optimizes the data usage alongside the prompt search. APEX dynamically stratifies the dataset into Easy, Hard, and Mixed tiers based on the optimization lineage. By prioritizing the Mixed tier, which identifies the data where the LLM has mixed performance, we identify two high-leverage subsets: the addressable frontier for generating informative mutations and the rank-sensitive frontier for distinguishing candidate quality. We evaluate APEX across three diverse benchmarks: IFBench, SimpleQA Verified, and FACTS Grounding. Under a fixed budget of 5,000 evaluation calls, due to its data efficiency, APEX outperforms the initial prompt by an average of 11.2% on Gemini 2.5 Flash and 6.8% on Gemma 3 27B, demonstrating that a data-centric approach is key to efficient and effective prompt optimization.
Prompt optimization has become a practical way to improve the performance of Large Language Models (LLMs) without retraining. However, most existing frameworks treat evaluation as a black box, relying solely on outcome scores without explaining why prompts succeed or fail. Moreover, they involve repetitive trial-and-error refinements that remain implicit, offering limited interpretability or actionable guidance for systematic improvement. In this paper, we propose MA-SAPO: a new Multi-Agent Reasoning for Score Aware Prompt Optimization framework that links evaluation outcomes directly to targeted refinements. Specifically, in the Training Phase, multiple agents interpret evaluation scores, diagnose weaknesses, and generate concrete revision directives, which are stored as reusable reasoning assets. In the Test Phase, an analyzer agent retrieves relevant exemplars and assets for a new prompt, and a refiner agent applies evidence-based edits to improve the prompt and its response. By grounding optimization in structured reasoning, MA-SAPO ensures edits are interpretable, auditable, and controllable. Experiments on the HelpSteer1/2 benchmarks show that our framework consistently outperforms single-pass prompting, retrieval-augmented generation, and prior multi-agent methods across multiple evaluation metrics.