DP-ES: Differentially Private Evolution Strategies for Prompt Optimization

Ziniu Liu; Aiping Li; Yue Han; Han Yu; Junjian Zhang; Dong Zhu; Changjian Li; Shiqiang Zhang

cs.CROct 5, 2026

DP-ES: Differentially Private Evolution Strategies for Prompt Optimization

Authors: Ziniu Liu, Aiping Li, Yue Han, Han Yu, Junjian Zhang, Dong Zhu, Changjian Li, Shiqiang Zhang

Organizations: National University of Defense Technology · CRRC Zhuzhou Electric Locomotive Research Institute Co., Ltd., China Academy of Railway Sciences

Abstract

Token-level differentially private (DP) prompt optimization methods such as DP-OPT can become unstable under tight privacy budgets: on GSM8K, DP-OPT obtains $49.5\pm28.5\%$ across 30 runs, and a logged search trajectory reveals prompt-template drift and noise-sensitive irreversible choices. We diagnose these as structural consequences of greedy token-by-token construction over privately aggregated counts. We then propose DP-ES (Differentially Private Evolution Strategies), a structurally cleaner alternative that maintains a population of full prompts, mutates them via LLM calls that never access the private dataset, and spends privacy only on sampled-Gaussian evaluation; deterministic or Gumbel-smoothed selection is post-processing. Under a conservative $(\varepsilon\leq1.0,δ=10^{-5})$ guarantee, DP-ES achieves 88.1% on GSM8K (+38.6 pp over DP-OPT, approximately 9 times lower standard deviation), 99.7% on MedQA, 73.5% on BANKING77, and 86.8% on Alpaca. It is also 2.5 times faster in wall-clock time and uses 3.3 times fewer logged private-data call groups than DP-OPT. Selection and population ablations, implementation-level noise checks, and a 200-profile exact-match memorization stress test complement the formal guarantee. Scope: Our experiments establish optimization robustness under DP noise, especially where prompt structure is critical; end-to-end validation on genuinely sensitive, non-saturated deployment data remains future work.

Figures & tables

Figure 1: DP-ES workflow and mechanism-level contrast with DP-OPT. Only sampled-Gaussian scoring accesses the private dataset. LLM mutation and deterministic or Gumbel-smoothed top- $M$ parent selection operate without further private-data access and add no privacy loss. Mechanism rows summarize canonical DP-OPT; the bottom panel reports our black-box adaptation’s GSM8K mean and standard deviation across 30 runs without imposing a post-hoc failure threshold.

Method	Priv.	Disc.	Mechanism
TextGrad	×	✓	LLM gradients
OPRO	×	✓	LLM scoring
EvoPrompt	×	✓	Evolutionary search
PromptBreeder	×	✓	Evolutionary search
DP-SGD	✓	×	Gaussian noise
DP-OPT	✓	✓	Histogram + Exp

Table 1: Comparison of prompt optimization methods. DP-ES adds formal record-level DP to evolutionary optimization over discrete prompts.

$\mathcal{D},n$	private data, size	$K,M,T$	candidates, parents, rounds
$b,q$	batch size, $q=b/n$	$z$	Gaussian noise multiplier
$u_{i}(p)$	per-record utility	$C_{\text{clip}}$	clipping bound
$\widetilde{s}_{p}$	privatized score	$\beta$	Gumbel smoothing scale

Table 2: Notation used in DP-ES.

Panel of Figure 2 — Figure 2: Performance and search dynamics. Left: Accuracy on GSM8K and MedQA under the conservative $(\varepsilon{\leq}1,\delta{=}10^{-5})$ guarantee. Right: Mean pairwise prompt-embedding distance, showing early population diversity followed by convergence.

Method	GSM8K	MedQA	BANK77	Alpaca †	Privacy
Non-DP	95.0 $\pm$ 0.9	100.0 $\pm$ 0.0	75.0 $\pm$ 2.8	91.7 $\pm$ 0.6	None
DP-OPT	49.5 $\pm$ 28.5	93.5 $\pm$ 12.0	75.3 $\pm$ 2.8	87.1 $\pm$ 1.4	(1.0, $10^{-5}$ )
DP-ES	88.1 $\pm$ 3.2	99.7 $\pm$ 0.5	73.5 $\pm$ 2.2	86.8 $\pm$ 0.8	( $\leq$ 0.71, $10^{-5}$ )
$\Delta$ (ES $-$ Opt)	+38.6	+6.2	$-$ 1.8	$-$ 0.3	–
$\Delta$ (ES $-$ Non)	$-$ 6.9	$-$ 0.3	$-$ 1.5	$-$ 4.9	–

Table 3: Main Results on the task evaluation sets in Section 4 (mean

\pm

std; 30 runs for GSM8K and three seeds for the other tasks). DP methods satisfy

(\varepsilon{\leq}1.0,\delta{=}10^{-5})

; DP-OPT is reported at its stated

\varepsilon=1

setting, while DP-ES’s recomputed RDP bounds are no larger than 0.71. † Alpaca scores are LLM-judge ratings scaled to percentages.

Panel of Figure 3 — Figure 3: DP-OPT trajectory drift vs. DP-ES population search on GSM8K. Top: selected prompts in an actual high-accuracy DP-OPT run (seed 42) omit the {question} placeholder as search progresses; the harness fallback appends the question, so omission is not treated as an accuracy-failure label. Middle: why irreversible noisy choices can redirect token-level construction. Bottom: a logged DP-ES prompt retains the placeholder while complete alternatives persist across rounds.

Selector	Accuracy (%)	Privacy
Gumbel-smoothed	$88.8\pm 3.4$	post-processing
Deterministic	$88.6\pm 2.9$	post-processing

Table 4: Selection ablation (five seeds). The two post-processing rules have comparable accuracy; neither changes the RDP bound established by the Gaussian scores.

Panel of Figure 4 — Figure 4: Exact-match memorization stress test on 200 synthetic profiles (1,200 sensitive strings). The intentionally adversarial Non-DP control is shown raw records and asked to embed a directory; its final prompt contains 40 strings (3.33%). DP-ES mutation never sees records, and its final prompt contains none of the listed strings. Excerpts and counts are reproduced from the saved run. This targeted diagnostic does not test semantic leakage or replace the formal guarantee.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	$n$	$q$	$\varepsilon$ at $\delta=10^{-5}$
All reported sampled-score runs	200	0.05	$\leq 0.71$

Appendix

Table 5: Recomputed worst-case privacy bound for at most 18 sampled-Gaussian score releases in the reported DP-ES configuration. We report the common conservative ceiling

\varepsilon\leq 1

Task	DP-OPT	DP-ES (Ours)	Speedup
DeepSeek API ( $\varepsilon\leq 1.0$ , 1,319 test examples, 3 iterations):
GSM8K	45.7 hours	17.9 hours	2.5 $\times$
MedQA	18.4 hours	7.0 hours	2.6 $\times$
Local Qwen2.5-7B ( $\varepsilon\leq 1.0$ , 200 examples):
GSM8K	14.60 hours	7.37 hours	1.98 $\times$
MedQA	3.24 hours	1.87 hours	1.73 $\times$

Appendix

Table 6: Efficiency Comparison (wall-clock). DP-ES is consistently faster than DP-OPT across both API and local deployments due to efficient population-based evaluation.

Cost component	DP-OPT	DP-ES	Ratio
Logged private-data call groups:
Mutation (token-level / privacy-free)	3 (DP)	0 (free)	—
Evaluation (Gaussian-noised)	30	10	3.0 $\times$ fewer
Total private-data groups	33	10	3.3 $\times$ fewer
Token usage:
Input tokens	1,309	6,120	4.7 $\times$ more

Appendix

Table 7: Efficiency breakdown by call purpose (GSM8K, seed 42,

\varepsilon\leq 1

, 200-example optimization set). Counts are logger-level call groups, not individual per-example model requests. DP-ES uses more tokens but fewer private-data round trips, yielding 2.5

\times

lower wall-clock time in this setting. Provider pricing and validation size can change the cost comparison.

Method / diagnostic	Runs	Accuracy	Observed structure
DP-OPT aggregate	30	$49.5{\pm}28.5\%$	high run-to-run variance
DP-ES aggregate	30	$88.1{\pm}3.2\%$	lower run-to-run variance
DP-OPT seed 42 trajectory	1	91.0%	21/33 candidates omit {question}

Appendix

Table 8: DP-OPT stability and trajectory diagnostics. The seed-42 trajectory is deliberately reported alongside its high final accuracy: the evaluation harness appends the question when {question} is absent, so placeholder omission is a structural-drift diagnostic rather than a direct failure criterion.

Method	GSM8K	MedQA
DP-ES	$53.8\pm 6.1$	$81.2\pm 1.3$
DP-OPT	$37.4\pm 11.6$	$83.0\pm 2.1$
PromptDPSGD	$20.0\pm 5.8$	$34.8\pm 19.0$
Non-DP	$26.2\pm 10.2$	$79.5\pm 4.2$

Appendix

Table 9: Local Qwen2.5-7B validation at the common

\varepsilon\leq 1

setting (three seeds; mean

\pm

std). Non-DP is a reference rather than an upper bound because the methods use different search procedures.

Population	Iterations	Accuracy	$\Delta$ vs Baseline
3	4	78.5%	-8.0 pp
6	3	86.5%	–
9	2	82.0%	-4.5 pp
12	2	82.0%	-4.5 pp

Appendix

Table 10: Population Size Ablation.

K=6

Iterations=3

provides an optimal diversity-depth tradeoff.

Explore similar work

ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize
Sep 3, 2026Lihao Liu, Peng Tang, Kunwar Yashraj Singh +1Automatic Prompt Optimization Instruction-Tuned Models
AWS Agentic AI
MAPLE: Metadata Augmented Private Language Evolution
Feb 26, 2026Eli Chien, Yuzheng Hu, Ryan McKenna +3Synthetic Data Alphaevolve
National Taiwan University · University of Illinois Urbana-Champaign · Google Research +1
DP-SelFT: Differentially Private Selective Fine-Tuning for Large Language Models
May 17, 2026Haichao Sha, Zihao Wang, Yuncheng Wu +2Large Language Model Fine-Tuning Continual Fine-Tuning
Renmin University of China · Nanyang Technological University

Sep 3, 2026, cs.CLJ/K move · Enter open · S save

ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize

Lihao Liu, Peng Tang, Kunwar Yashraj Singh, Shabnam Ghadar

AWS Agentic AI

Automatic Prompt Optimization Instruction-Tuned Models Prompt Optimization Natural Language Processing Model Selection Diagnosis

Open paper AskPDF arXiv

Evolutionary prompt optimizers such as GEPA suffer from prompt bloat: each iteration appends rules and caveats, producing prompts up to 3

\times

longer yet no more accurate. We trace this to three deficiencies - incomplete error observation, limited search diversity, and unreliable selection - and propose ESPO (Error-Structured Prompt Optimization), which decomposes prompt optimization into three phases: Diagnose clusters all training errors into structural patterns in one round; Propose generates candidates via four complementary strategies with independent biases; Select applies bootstrap stability selection. On seven public NLP benchmarks - Tweet, MMLU, GSM8K, HotpotQA, ScoNe, HoVer, and PUPA - ESPO improves average accuracy by

+

3.76 pp over the state-of-the-art (74.67% vs 70.91% for GEPA), matching or exceeding GEPA on every dataset while producing prompts 47% shorter (1,004 vs 1,878 chars) and faster at inference. Cross-model experiments across four additional student models (Gemma 3 12B, Mistral 14B, Qwen3 32B, Claude Haiku 4.5) show ESPO yields the best average accuracy on every model tested, with the largest gap on Qwen3 GSM8K (15.00%

\to

91.40%). A generalization bound (Appendix) grounds each phase in a corresponding term of the test-time gap, and the ablation confirms a key prediction: adding diversity without bootstrap selection actually hurts performance (

-

1.20%).

Abstract

Explore similar work

ESPO: Error-Structured Prompt Optimization via Diagnose, Diversify, and Stabilize

MAPLE: Metadata Augmented Private Language Evolution

DP-SelFT: Differentially Private Selective Fine-Tuning for Large Language Models